Z-index of point on a polygon
I've got a polygon defined by an array of vectors:
Vector3 [] v ;
.
Given the x and y coordinates of a point on the surface, I need to find the corresponding z coordinate.
Perhaps cast a vector from (x,y,0) in the direction of (0,0,-1), and then find how far it travels prior to hitting the surface.
I need the fastest solution - with as little overhead as possible, as I'm likely to be performing this operation potentially tens of thousands of times per second (if not more)..
Thanks very much.
Vector3 [] v ;
.
Given the x and y coordinates of a point on the surface, I need to find the corresponding z coordinate.
Perhaps cast a vector from (x,y,0) in the direction of (0,0,-1), and then find how far it travels prior to hitting the surface.
I need the fastest solution - with as little overhead as possible, as I'm likely to be performing this operation potentially tens of thousands of times per second (if not more)..
Thanks very much.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
If you're going to to it many times for the same polygon, you can pre-compute
| 0-x0 0-y0 Z00-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
| 0-x0 1-y0 Z01-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
| 1-x0 0-y0 Z10-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
then
| x-0 y-0 z-Z00 |
| 0-0 1-0 Z01-Z00 | = 0
| 1-0 0-0 Z10-Z00 |
or z = Z00 + x*(Z10-Z00) + y*(Z01-Z00)
| 0-x0 0-y0 Z00-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
| 0-x0 1-y0 Z01-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
| 1-x0 0-y0 Z10-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
then
| x-0 y-0 z-Z00 |
| 0-0 1-0 Z01-Z00 | = 0
| 1-0 0-0 Z10-Z00 |
or z = Z00 + x*(Z10-Z00) + y*(Z01-Z00)
ASKER
Does this account for if the given x,y coordinate do not have a corresponding z position on the polygon?
No.
But you can check if the point
x,y lies in the polygon (x0,y0),(x1,y1),(x2,y2),(x
But you can check if the point
x,y lies in the polygon (x0,y0),(x1,y1),(x2,y2),(x
ASKER
Oh yes, excellent :)
Okay, so let me just check this ...
I solve Z00, Z01, and Z10, in the below for each surface (precompute):
| 0-x0 0-y0 Z00-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
| 0-x0 1-y0 Z01-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
| 1-x0 0-y0 Z10-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
Once I've concluded that x,y has a corresponding z on the polygon at hand, I use this:
z = Z00 + x*(Z10-Z00) + y*(Z01-Z00)
to find the corresponding z value?
Okay, so let me just check this ...
I solve Z00, Z01, and Z10, in the below for each surface (precompute):
| 0-x0 0-y0 Z00-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
| 0-x0 1-y0 Z01-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
| 1-x0 0-y0 Z10-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
Once I've concluded that x,y has a corresponding z on the polygon at hand, I use this:
z = Z00 + x*(Z10-Z00) + y*(Z01-Z00)
to find the corresponding z value?
That looks right
ASKER
Actually.... for what I'm doing, the polygons are always changing, so precomputing those variables wouldn't really help (in my case), in which case, I just use your first solution, of solving:
| x-x0 y-y0 z-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
Which comes to:
z = - ((x-x0)(y-y0)(z2-z0) - (x-x0)(z1-z0)(y2-y0) - (y-y0)(x1-x0)(x2-x0) + (y-y0)(z1-z0)(x2-x0)) / ( (x1-x0)(y2-y0)-(y1-y0)(x2-
Correct? :)
(heh, don't worry, I don't expect you to check if my equation is definitely correct - but I at least seem on the right track, yer?)
Thanks very much
| x-x0 y-y0 z-z0 |
| x1-x0 y1-y0 z1-z0 | = 0
| x2-x0 y2-y0 z2-z0 |
Which comes to:
z = - ((x-x0)(y-y0)(z2-z0) - (x-x0)(z1-z0)(y2-y0) - (y-y0)(x1-x0)(x2-x0) + (y-y0)(z1-z0)(x2-x0)) / ( (x1-x0)(y2-y0)-(y1-y0)(x2-
Correct? :)
(heh, don't worry, I don't expect you to check if my equation is definitely correct - but I at least seem on the right track, yer?)
Thanks very much
ASKER
Hey ozo,
just thought I'd let you know that I've got round to testing it now, and it's brilliant!
It calculates the correct z coordinate for a random coordinate on an arbitrary polygon 1,000,000 times in 0.16 seconds approximately (in Java as well!). Which I'm very happy with. :)
So, another big thank you !
just thought I'd let you know that I've got round to testing it now, and it's brilliant!
It calculates the correct z coordinate for a random coordinate on an arbitrary polygon 1,000,000 times in 0.16 seconds approximately (in Java as well!). Which I'm very happy with. :)
So, another big thank you !
ASKER