• Advertisement
Sign in to follow this  

Find out Y when intersecting a polygon

This topic is 3317 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I know questions like this have been asked and I have searched but haven't been able to find a simple solution to my problem. What I want is this. I have X and Z value of my checkpoint. I want to find it it's Y value by checking the polygons X Y Z values. How do I do this fast and simple? For example Checkpoint X:5 Z:7 Polygon X:0 Y:1 Z:0 X:10 Y:2 Z:0 X:10 Y:0 Z:10 X:0 Y:0 Z:10 How do I calculate checkpoint Y value. Thanks in advance!

Share this post


Link to post
Share on other sites
Advertisement
Well the simplest method is using barycentric coordinates.

How this works is you find your check point in terms of each of the other points.

In this case you have four points
A = (0,1,0)
B = (10,2,0)
C = (10,0,10)
D = (0,0,10)


So in this case if you drop the y value for your polygon points you have
A' = (0,0)
B' = (10,0)
C' = (10,10)
D' = (0,10)


then you can calculate the check point is in terms of A',B',C' and D':
CheckPoint = (0.5*0.3) * A + (0.5*0.3) * B + (0.5*0.7) * C + (0.5*0.7) * D
= 0.15 * A + 0.15 * B + 0.35 * C + 0.35 * D


NB: Notice that the coefficients must always add up to 1.0
0.15 + 0.15 + 0.35 + 0.35 = 1.0


So you have
0.15 * A + 0.15 * B + 0.35 * C + 0.35 * D
= 0.15 * (0,1,0) + 0.15 * (10,2,0) + 0.35 * (10,0,10) + 0.35 * (0,0,10)
= (0,0.15,0) + (1.5,0.3,0) + (3.5,0,3.5) + (0,0,3.5)
= (5,0.45,7)


In other words your Y = 0.45. Cool huh? Of course you can just calculate the y values, you don't need to add up the vector like I did (you already know that x = 5 and z = 7).
I'll leave calculating those coefficients to someone else to explain. I can't quite remember it out of my head.

[Edited by - errantkid on January 24, 2009 5:48:03 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by errantkid
CheckPoint = (0.5*0.3) * A + (0.5*0.3) * B + (0.5*0.7) * C + (0.5*0.7) * D
= 0.15 * A + 0.15 * B + 0.35 * C + 0.35 * D


Thanks for starting to steer me in the right direction!

I'm wondering though where you got the numbers 0.15 0.35 etc from?

Share this post


Link to post
Share on other sites
Okay, that's the second part of the explanation. Since nobody else is jumping in I'll try and finish.

Say you have a line A to B starting from 0 and ending at 10 (like the top edge of your polygon). Then a point CP at 5 will be exactly halfway between A and B right?
so

-----------------------
^ ^ ^
A=0 CP=5 B=10


So
CP = 0.5 *(A + B) = 0.5 * (0 + 10) = 5

In other words you can write
CP = 0.5 * A + 0.5 * B


These two coefficients (0.5, 0.5) are called barycentric coordinates.

It works the same for a rectangle:

0.5
v
A-----------------------B
| . |
| . |
| . |
| . |
| . |
| +...........|< 0.7
| CP |
| |
D-----------------------C


So A and D contribute 50% (0.5) of the x coordinate and B and C contribute the other 50%.

But A and B contribute only 30% (0.3) of the y coordinate whereas D and C contribute 70% (0.7).


CPab = 0.5 * A + 0.5 * B
A-----------+-----------B
| . |
| . |
| . |
| . |
| . CP |
|...........+...........|
| . |
| . |
D-----------+-----------C
CPdc = 0.5 * D + 0.5 * C


So now you should be able to see that
CP = 0.3 * CPab + 0.7 * CPdc
= 0.3 * (0.5 * A + 0.5 * B) + 0.7 * (0.5 * D + 0.5 * C)
= (0.3*0.5) * A + (0.3*0.5) * B + (0.7*0.5) * D + (0.7*0.5) * C
= 0.15 * A + 0.15 * B + 0.35 * D + 0.35 * C

Right?

Doing it for any polygon (unlike the nice one you gave me) is going to be slightly more tricky so I'll just have to look it up quickly...

Share this post


Link to post
Share on other sites
The polygon you're referring to is a quad which is really 2 triangles, that may or may not be coplanar. In either case, given any point inside the quad you can calculate the plane equation from the 3 surrounding points, and then solve for the value of the other coordinate on the plane.

I'm not sure that Barycentric coordinates will accomplish what you want in this case. I haven't really thought about it but my suspicion is that it would result in the same kind of distortion issues that you get from using Barycentric coordinates to interpolate (u,v) coordinates for texture mapping.

Share this post


Link to post
Share on other sites
Yes, yahastu is right of course, you're going to end up with distortion (In fact, the polygon you gave is not flat). However, as far as I can tell a polygon that is not co-planar is not well-defined (the surface needs to "bend" somehow to fit in the shape). This basically means you'll have to live with the distortion. I don't think there's any other way than using barycentric coordinates in this case, so I'll give you a short explanation of more-or-less how it works. (you could also look at http://www.devmaster.net/wiki/Barycentric_coordinates)

Basically it goes something like this: Take one point (e.g. A) and then use two vectors from originating from this point (e.g AB = B-A and AD = D-A).

Find c1 and c2 such that CP = A + c1 * AB + c2 * AD.
You can do this by cleverly projecting a vector from A to CP onto AB and AD.
E.g.
Let ACP = CP - A
c1 = ACP * normalize(AB)
c2 = ACP * normalize(AD)

now
CP = A + c1 * (B - A) + c2 * (D - A)
CP = A - c1 * A - c2 * A + c1 * B + c2 * D
CP = (1-c1-c2)*A + c1*B + c2*D

We only found the barycentric coordinates of A, B and D. However, this is good enough if your polygon is flat. Getting C in there so that you have the "distortion" should be possible too, but I'll give my hands a rest for a bit. ;)

Share this post


Link to post
Share on other sites
The plane you have described is non-planar, so you'll have to split it in two.

Using the general plane equation: ax + by + cz + d = 0:
The cross-product of two edges on the triangle (p3 - p2, p4 - p3) gives you a, b and c (the plane's normal).

Calculate d by plugging one point into the equation.
d = -(a * 10 + b * 2 + c * 0)

y = -(a * 5 + c * 7 + d) / b
So that would say y = 0.6

But, there are multiple answers since there are two ways to cut the polygon resulting in different triangles.

[Edited by - eppo on January 24, 2009 11:36:28 AM]

Share this post


Link to post
Share on other sites
Thank you for that long explanation errantkid!

Sorry for giving you guys a nonplanar, it will be planar only.

Will try it and return with the results.

Share this post


Link to post
Share on other sites
No prob! By the way, eppo's technique is much more elegant (and faster), so I recommend doing it his way. It should give you the same solution with a lot fewer computations. Sorry about the unnecessary long winded explanation, but hopefully you can use barycentric for something else in the future :)

Share this post


Link to post
Share on other sites
Ratings++ to errantkid for the good explanation and decent ASCII art!

I'd just like to point out that in general, you might not calculate a point that is actually inside the polygon, so you'd have to do more checks on the result if that's important.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement