5

I have a 3D math problem which I just can't seem to solve.

I have data of 3 points. The data is a (2D) coordinate on a plane, floating somewhere in 3D space. I also know the (2D) coordinate of the projection. That results in the following array of data:

[[[x1,y1], [px1,py1],
 [[x2,y2], [px2,py2],
 [[x3,y3], [px3,py3]]

Where the normal (x1 etc.) coordinates stand for the coordinates on the plane and the other (px1 etc.) for the projected coordinates.

What I would like to do is project a new 2D coordinate ([x4,y4]).

.

What I tried so far:

Ofcourse you need an eye for projection, so I set that to [xe,ye,-1]. The xe and ye are known. (It is photo referencing, so I just placed the eye in the center of the photograph.)

Beneath the eye I placed the projection surface (z=0). That gives the following projection coordinates:

[[[x1,y1], [px1,py1,0],
 [[x2,y2], [px2,py2,0],
 [[x3,y3], [px3,py3,0]]

I can't do the same for the coordinates on the plane, since I don't know anything about that plane.

I also figured that I could make a parameterized formula of the lines running from the eye through the projection coordinates. For line1 that would be:

line1x = xe+(px1-xe)*t1
line1y = ye+(py1-ye)*t1
line1z = -1+t1 // = -1+(0--1)*t1

I also know the distance between the points in 3D. That's the same as in 2D. That means the distance between point1 and point2 would be sqrt((x1-x2)^2+(y1-y2)^2).

I also know the distance between the lines (line1 and line2) at any time. That is sqrt((line1x-line2x)^2+(line1y-line2y)^2+(line1z-line2z)^2).

However, I don't really know how to go from here... Or even whether this is the right route to take.

.

I hope you understand what I want to be able to do, and that you can help me.

Thanks in advance!

Mr.Wizard
  • 24,179
  • 5
  • 44
  • 125
Pieter Jongsma
  • 3,365
  • 3
  • 27
  • 30
  • Are you saying that you are given three points (xn,yn) which are projected onto a plane at points (pxn, pyn) - and you want to work out how to map a new point (x4, y4) onto the plane? – Joel Goodwin Jul 02 '09 at 11:53
  • Yes, goodgai, that is what I am saying. However, when I use the term 'plane' in my question, I mean the plane on which the (xn,yn) points are located (which I think is significant when trying to map the fourth point). Sorry for the confusion. – Pieter Jongsma Jul 02 '09 at 12:00
  • You have three points on a plane (xn,yn) which are projected onto projection plane (pxn,pyn). This is also a central (perspective) projection, so all points are projected through rays from a single point. You want to know how to reverse the projection: that is, if you are given a projected point (px4,py4) how to get (x4,y4)? What I don't get is your original points don't have any z co-ordinates whatsoever. Why are they x/y only - do you know the z co-ordinate or are these x/y co-ordinates within the plane's own co-ordinate system...? – Joel Goodwin Jul 02 '09 at 12:17
  • "I also know the distance between the points in 3D. That's the same as in 2D." --> It shocked me, how do you know that ? – Cyril Gandon Jul 02 '09 at 12:18
  • @goodgai The (xn,yn) coordinates are indeed coordinates on the plane's own coordinate system. And I get (x4,y4), I want to produce (px4,py4). – Pieter Jongsma Jul 02 '09 at 14:12
  • Is it a school problem ? And I repeat myself, is "I also know the distance between the points in 3D. That's the same as in 2D." a hypothesis ? to me it sounds like a big condition ! – Cyril Gandon Jul 02 '09 at 15:47
  • @ Scorpi0 No, not a school problem. And I don't think you understand what I mean. I have 3 points of which I have a 2D coordinate AND a projected (2D) coordinate. The first 2D coordinate is on a plane in a arbitrary position in 3D space. I want to reconstruct the scene, so that when I get a new 2D coordinate, I can project it. Do you understand? – Pieter Jongsma Jul 02 '09 at 16:09
  • You may want to experiment using a software like Cabri 3D, http://www.cabri.com/ – Eric Bainville Jul 02 '09 at 16:55
  • I tried to do the problem in 2D : given two points with only x-coordinate, x1 and x2, and the projection on the x-axes, px1 and px2, what is the formula of px3, such as x3 is on the line of ((x1,y1),(x2,y2)). Seems unresovable to me... – Cyril Gandon Jul 02 '09 at 21:13
  • @Scorpi0 Note that when you get a fourth coordinate, you also know the distance from the other three points (in the 3D plane's own coordinate system). There is just one position possible then. But without any information of how the plane's coordinate system is position, it isn't very helpful. – Pieter Jongsma Jul 02 '09 at 22:35

5 Answers5

2

There is a function Projection, which can transform points so that Projection([x1, y1]) = [px1, py1] , Projection([x2, y2]) = [px2, py2], Projection([x3, y3]) = [px3, py3]. If I understand correctly, author wants to know how to find this Projection function, so that he can trasnform [x4, y4] into [px4, py4].

Since we are dealing with planes here, the Projection function looks like this:

Proj([ix, iy]) :
    return [ax*ix + bx*iy + cx,
            ay*iy + by*iy + cy];

Using that we can make 2 equation systems to solve.

The first one
x1 * ax + y1 * bx + cx = px1
x2 * ax + y2 * bx + cx = px2
x3 * ax + y3 * bx + cx = px3

Solving for ax, bx and cx gives us

ax = (px1 * (y3 - y2) - px2*y3 + px3*y2 + (px2 - px3) * y1) /
     (x1 * (y3 - y2) - x2*y3 + x3*y2 + (x2 - x3) * y1)
bx = - (px1 * (x3 - x2) - px2*x3 + px3*x2 + (px2 - px3) * x1) /
     (x1 * (y3 - y2) - x2*y3 + x3*y2 + (x2 - x3) * y1)
cx = (px1 * (x3*y2 - x2*y3) + x1 * (px2*y3 - px3*y2) + (px3*x2 - px2*x3) * y1) /
     (x1 * (y3 - y2) - x2*y3 + x3*y2 + (x2 - x3) * y1)

The second one x1 * ay + y1 * by + cy = py1
x2 * ay + y2 * by + cy = py2
x3 * ay + y3 * by + cy = py3

Solving for ay, by and cy gives us

ay = (py1 * (y3 - y2) - py2*y3 + py3*y2 + (py2 - py3) * y1) /
     (x1 * (y3 - y2) - x2*y3 + x3*y2 + (x2 - x3) * y1)
by = - (py1 * (x3 - x2) - py2*x3 + py3*x2 + (py2 - py3) * x1) /
     (x1 * (y3 - y2) - x2*y3 + x3*y2 + (x2 - x3) * y1)
cy = (py1 * (x3*y2 - x2*y3) + x1 * (py2*y3 - py3*y2) + (py3*x2 - py2*x3) * y1) /
     (x1 * (y3 - y2) - x2*y3 + x3*y2 + (x2 - x3) * y1)

Note: I used this tool to solve equation systems.

Juozas Kontvainis
  • 9,461
  • 6
  • 55
  • 66
  • Wow, thanks for the extensive answer, however, I think this solution is a little shady since the method you use isn't really related to projection. There is, for instance, no eye. I therefore doubt it will work properly... Nevertheless I will definetly give it a try. I'll let you know whether it worked. Thank you! – Pieter Jongsma Jul 04 '09 at 15:55
  • This solution won't give you an eye or any information about original triangle's plane, but it should solve your problem. – Juozas Kontvainis Jul 04 '09 at 16:27
1

Write

(x4,y4,1) = A1*(x1,y1,1) + A2*(x2,y2,1) + A3*(x3,y3,1),

solving for A1,A2,A3. Then

(xp4,yp4) = A1*(px1,py1) + A2*(px2,py2) + A3*(px3,py3).

1st edit.

(A1,A2,A3) is the solution of the linear system Mat*(A1,A2,A3)=(x4,y4,1).

      ( x1  x2  x3 )
Mat = ( y1  y2  y3 )
      (  1   1   1 )

This can be solved in various ways. For example using Cramer's rules.

2nd edit.

The 1's I inserted are not Z coordinates, but homogeneous extensions of the input coordinates (which must be Euclidean coordinates). (A1,A2,A3) are homogeneous coordinates in the basis formed by the triangle vertices.

3rd edit.

The correspondence between the 3D plane and the projection plane is a projective transformation. It can be defined as a 3x3 matrix T operating on homogeneous coordinates in the input plane (x,y,1) (in your coordinate system) and producing coordinates (u,v,t) in the projection plane. Then px=u/t and py=v/t.

If a point has homogeneous coordinates (A1,A2,A3) in the basis formed by three points of the input plane (not on the same line) then its projection has the same homogeneous coordinates in the projected basis.

It seemed quite clear to me 1 hour ago, but now I'm beginning to doubt: maybe knowing one additional pair of points is needed to have a single solution to the problem... If you can find it, have a look at the book "Algebraic Projective Geometry" by J.G. Semple and G.T. Kneebone.

Eric Bainville
  • 9,738
  • 1
  • 25
  • 27
1

You should use homographic functions and homogeneous coordinates, which are generaly used for 3D perspective operations.

fa.
  • 2,456
  • 16
  • 17
0

I don't really understand the problem? Are you trying to locate an object in 3d-space that you know is located on a plane (a wall or floor for example) and the only input you have is 3 points(of which you know the distances between in 3d-space) from a camera-image?

In that case you will have 3 equations like this where localCoordinates is the points coordinates in objectspace(gives the known distance between the points) and world is the objects position in 3d-space.

cameraCoordinates = world*view*projection*localCoordinates

This will yield an equation system with 6 unknown(rotation and position in 3d) and 6 equations (2 for every point). It will however be non linear so you have to solve it using numerical methods. Try the Newton Rapson method.

0

A "bit" late here, but the highest rated answer doesn't take into account the 3D-space of the problem. We have a perspective projection problem, with three points on a plane (actually any 3 3D points) being projected (as in projective geometry) on the surface of a camera.

It is not possible to give an unambiguous solution to this problem (multiple solutions exist). The general problem of finding a camera position and pose given 3 3D points and their respective 2D perspective projections can be solved using the P3P (Perspective-3-Point) algorithm from the original RANSAC paper, which give up to four possible feasible solutions (with the points in front of the camera).

Given a camera pose, it is trivial to calculate the projection of additional plane points.

digitalvision
  • 2,552
  • 19
  • 23