1
\$\begingroup\$

Say I have a coordinate system that goes from (0,0) to (1,1). We'll call this screen_space.

Within this coordinate system, I have 4 points that I would like to define another coordinate system. One such point I have defined as the (0,0) of this coordinate system (which we'll call world_space), might exist at (0.3,0.2) screen_space. The next point I have defined as the (1,0) of world_space, could be at (0.7,0.3). And so on.

The trick is that there are no few constraints on where in screen_space the world_space-defining points are: they needn't be axis aligned, nor affine, etc... The constraints I've been able to think of are: -There must be a non-zero distance between any two world_space defining points. -If there are 'paralell-in-world_space' axes that cross in screen_space, the fifth point musn't be past that cross (honestly, I don't know the mathematically rigorous way to express that constraint...).

The Question: Given a fifth point in screen_space, how can I find it's world_space equivalent? Is this even possible?

Example conversion table of the four world_space-defining points:

world_space | screen_space
--------------------------
  (0,0)     |  (0.3,0.2)
  (1,0)     |  (0.7,0.3)
  (0,1)     |  (0.4,0.9)
  (1,1)     |  (0.6,0.4)
  (?,?)     |  (0.4,0.5)
[the solution I came up with for this example is (0.172353,1.203769)]

Note- the point may not necessarily fall between 0-1 in world_space.

My Solution, with which I am unsatisfied: lerp along the (0,0) to (0,1) line of world_space in screen_space, at t = 0.5. lerp also along the (1,0) to (1,1) line of world_space. construct a line between these two derived points in screen_space, and test whether the screen_space point in question is on the left or the right of that line. If to the left, repeat for t = 0.25, and if to the right, repeat for t = 0.75. Keep repeating this binary search until you are satisfactorily close. You now have the world_space_x = t coordinate. Repeat process along (0,0) to (1,0) and (0,1) to (1,1) to find world_space_y.

The problems with this solution are: This is ridiculous. It's more processing to convert coordinate spaces than I can afford. It's just enough to convince me that it's at least possible (I think). Also, this method will only work for points within 0-1 x and y of world_space. However, to escape that, I'd change from a binary search to a more hill-climby algorithm (and, given that there can't [I don't think] be non-global local maxima I think that should be exhaustive...). But again, that's just getting more ridiculous...

But why do you need this? I'm creating a 3d game, where you need to be able to 'touch' the 3d objects. So the question becomes "this has been solved! just use the inverse of the matrix you used to get the global points into screen space, to convert the screen_space touch into world_space! then, ray cast from the camera to that point and do collision testing with the world_space geometry to find a touch!" But, (and I'm still a bit shakey on linear algebra...) the projection computations (divide-by-w shenanigans) yield a non-affine transformation, which means there isn't simply an inverse matrix... right? Also, my game "logically" takes place more-or-less on a 2d plane, and all that collision detection 'n stuff seems overkill. So I've simply transformed 4 on-the-2d-plane-of-interactivity points from world space to screen space (by emulating basic transforms in my vertex shader + opengl stuff on cpu), hoping that that should be enough to quickly convert a screen_space touch to world space by using those as reference.

tl;dr of "but why": trying a clever hack based on known restrictions in my game to more quickly/easily compute this kind of thing.

would prefer an answer to the question I asked rather than "you should try this library".

Thanks a ton!

Edit: Ok. So I after implementing the hill-climbing algo, I realized that I had the 'solvable' equation pretty much already in use: The check to see "which side of the line" a point is on (https://stackoverflow.com/questions/1560492/how-to-tell-whether-a-point-is-to-the-right-or-left-side-of-a-line) returns 0 for "on the line". So, I could set the points in that equation to the lerp equation deriving the endpoints (isolating for x and y separately), set it all equal to 0, and solve for t. The result is a ridiculously complicated monstrosity of an equation that involves a square root, but, it actually yields accurate results (read: "the same results as the iterative algorithm").

Here is this monster equation:

fv2 coordSystemTranslate(fv2 p00, fv2 p10, fv2 p01, fv2 p11, fv2 p)
{
  fv2 result;

  //convert to single-letter vars for *slightly* better readability
  float a = p00.x;
  float b = p00.y;
  float c = p01.x;
  float d = p01.y;
  float e = p10.x;
  float f = p10.y;
  float g = p11.x;
  float h = p11.y;
  float i = p.x;
  float j = p.y;

  result.x = (0.5*(-sqrt(pow((2*a*d-a*h-a*j-2*b*c+b*g+b*i+c*f+c*j-d*e-d*i+e*j-f*i-g*j+h*i),2)-4*(-a*d+a*j+b*c-b*i-c*j+d*i)*(-a*d+a*h+b*c-b*g-c*f+d*e-e*h+f*g))-2*a*d+a*h+a*j+2*b*c-b*g-b*i-c*f-c*j+d*e+d*i-e*j+f*i+g*j-h*i))/(-a*d+a*h+b*c-b*g-c*f+d*e-e*h+f*g);
  result.y = (0.5*(-sqrt(pow((2*e*b-e*d-e*j-2*f*a+f*c+f*i+a*h+a*j-b*g-b*i+g*j-h*i-c*j+d*i),2)-4*(-e*b+e*j+f*a-f*i-a*j+b*i)*(-e*b+e*d+f*a-f*c-a*h+b*g-g*d+h*c))-2*e*b+e*d+e*j+2*f*a-f*c-f*i-a*h-a*j+b*g+b*i-g*j+h*i+c*j-d*i))/(-e*b+e*d+f*a-f*c-a*h+b*g-g*d+h*c);

  return result;
}

And here's the bad news- it still doesn't work for what I wanted... Unfortunately, my initial assumption that world space coordinates can be derived from 4 screen space reference points given the constraints to my system listed above, was wrong. At least partially. I think I need at least one more reference point, and then some clever math. The reasoning is that in world space, "distance" can't be linearly interpolated equivalently in screen space. As things go further away in world space, the distance between them gets more densely represented in screen space. The good news is that I also have reference z points (which I left out before because I assumed they would be unnecessary). I think all I should need is a fifth reference point within the defined plane to compare the rate at which I should interpolate...

But it's getting late, and this is getting even more crazy than it was before... If there's some simpler way to go about all this, I'd greatly appreciate it!

\$\endgroup\$
  • \$\begingroup\$ Just to check, what is the right answer for your example? \$\endgroup\$ – wondra Sep 2 '15 at 18:24
  • \$\begingroup\$ So, in randomly typing out numbers for the example, I guess I picked some invalid inputs- if the "paralell-in-world-space" axes cross, and the point exists beyond that cross, the hill climbing fails (the code detecting whether the point is on one side of the line or the other gets flipped and it starts running away forever...). So, I've edited the post and switched the last two plane-defining points, and have posted an answer. I will also edit it to include that there are more constraints than I had initially thought... \$\endgroup\$ – Phildo Sep 3 '15 at 5:00
  • \$\begingroup\$ So if I understand correctly you have a polygon with 4 edges where each edge maps to a 0,0-1,1 rectangle edge? ...but this also doesn't suit your goal as the rectangle is the 2D outline of a plane in perspective- thus linear interpolation doesn't work? \$\endgroup\$ – Felsir Sep 3 '15 at 11:34
  • \$\begingroup\$ @Felsir exactly. concisely put. \$\endgroup\$ – Phildo Sep 3 '15 at 13:51
  • \$\begingroup\$ To be honest, it will probably be much simpeler to actually use a 3D transformation matrix to create the perspective plane than throwing math at it to solve it using interpolation techniques. From what I understand your game logic operates in 2D. So you can still use that for the internals such as collision detection. The matrices goal would be to aquire the coordinates you try to calculate as in the interpolation function. \$\endgroup\$ – Felsir Sep 3 '15 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.