Converting 2D coordinates from multiple viewpoints into 3D coordinates

Here's the situation. I've got a set of 2D coordinates that specify a point on an image. These 2D coordinates relate to an event that happened in a 3D space (video game).

I have 5 images with the same event point on it, so I have 5 sets of 2D coordinates for a single 3D coordinate. I've tried everything I can think to translate these 2D coordinates into 3D coordinates, but the math just escapes me. I have a good estimate of the coordinates from which each image was taken, they're not perfect but they're close.

I tried simplifying this and opening up Cinema 4D, a 3D modeling application. I placed 5 cameras at the coordinates where the pictures were taken and lined up the pictures with the event points for each one and tried to find a link, but nothing was forthcoming. I know it's a math question, but like I said, I just can't get it. I took physics in high school 6 years ago, but we didn't deal with a whole lot of this sort of thing.

Any help will be very much appreciated, I've been thinking on it for quite a while and I just can't come up with anything.

• It's just a set of equations for several unknowns, isn't it? Why don't you write them down and solve them? The solution is not trivial at the verbal level so that it would require no maths. Obviously, your information is overdetermined, so you will have to choose the optimum way to find the 3D coordinates.
– Luboš Motl
Feb 28 '11 at 19:17
• There is no physics in this, it's just geometry. Try math.SE or SO (things like these are often done in computer graphics) instead.
– Marek
Feb 28 '11 at 19:29

You really only need two viewpoints to locate the point. From each viewpoint, you have a camera location and a direction; that is, you have everything you need to uniquely define a line in 3d Cartesian space. All this amounts to is finding the intersection of two lines.

• You only need two viewpoints under certain constraints. Feb 28 '11 at 22:57
• The only constraint is that the two viewpoints are not collinear with the object. Mar 1 '11 at 4:09

It depends just how much freedom you have with this scenario. In the worst case you will need to set up some 3x3 matrices and do some coordinate transformations between different coordinate systems.

However if you have control over the layout, then the simplest situation would arise if three of those five projection angles happen to be mutually perpendicular. Then each just corresponds to different planes: x-y, y-z, x-z. So if the coordinates in the x-y plane are (a,b) and in the y-z plane are (b,c) then the coordinates should be (a,b,c). Of course this means that the coordinates in the x-z plane are (a,c), as we are assuming that they are perpendicular and there is no scale change between planes. You will also be choosing origins appropriately etc.

However if you have an independent coordinate system for the 3D space (X,Y,Z) then you will need to find the transformation matrix between the various coordinate systems: M(a,b,c) = (X,Y,Z).

In the general case you are looking for 3 (or 5) projection 3x3 matrices $P_1$, $P_2$, $P_3$ which will have the property that $P_{i}^2 = P_i$ and they are of rank two. The 2 eigenvectors of P will correspond to the two axes of the projection plane. If you need to know more about this then a book on 3D geometry for computer modelling will be required. Some of the maths can be quite sophisticated - a subject called "Geometric Algebra" has recently become quite popular in this area, to assist with visualising and efficiently calculating the various formulae involved.

just looking at vision.middlebury.edu has a bunch of stuff. I used to have an old text with the stereo to 3d algorithm in BASIC ! long gone. There is quite a bit on the web.

If you have projection matrices of each image, you can use triangulation (for example here). It works for two cameras and generates one 3D point.

Hey thanks for all the answers. Unfortunately, I have no control over the scene. The images have been taken from fixed points and I had to do a lot of visual comparisons to get a decent approximation of where they were taken from.

Basically what happens is an event happens within the game (a kill or a death) and the event is sent to the server when the game ends. The software behind the server takes the 3D coordinates from that event and maps it to a 2D image that you can look at and see where that kill or death happened. Those coordinates are relative to the image, though, not the actual game space. All I know about the images is an estimate of the coordinates where it was taken at (in game space) and the field of view (78°). Here are the position and rotation coordinates for 3 of the images in (X, Z, Y) / (yaw, pitch):

1: (15.894, 152.263, 43.839) / (53.34, -14.61)
2: (27.205, 170.375, 72.500) / (0.00, -85.50)
3: (51.987, 184.236, 41.290) / (206.38, -14.07)

And here are the coordinates that the server is calculating for those 3 points of view, remember they're relative to the image, (X, Y):

1: (322, 205)
2: (389, 232)
3: (240, 109)

And finally, the actual in-game cordinates where this event happened, (X, Z, Y):

(25, 164, 039)

Hopefully someone here can lend me their brain for a bit, I'm completely at a loss.

Edit: Perhaps I should have used the same name I posted the original question with. My mistake, I am the original poster.

• I'm assuming the second set of coordinates is a set of screen coordinates. It would be helpful to know the resolution of the images. But here's what you do: calculate the direction of the vector between each viewpoint and the event point. You can get cartesian coordinates by just subtracting, and you can compare these direction vectors to the rotation vectors of your viewpoints. That should give you a start at the very least. Mar 2 '11 at 1:50
• As long as you have used the same OpenID to sign up for both Physics and Game Dev and you associate your accounts you will regain ownership of the question. You can still associate accounts even if you have used different OpenID's - I'm just not sure of the exact process. Mar 2 '11 at 12:52
• @Tristan: Sorry about that, the images are 640x360. And I'll look into that Chris, thanks.
– user5800
Mar 3 '11 at 21:52
• Sorry for the double comment, it won't let me edit. I didn't sign up at Physics, I posted as an unregistered user with my real name. I just used my OpenID to sign up there but it didn't associate the accounts, the question stil shows as being asked by the unregistered account (my real name). Oh well, not a big deal.
– user5800
Mar 3 '11 at 22:00