Converting 2D coordinates from multiple viewpoints into 3D coordinates

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.