PDA

View Full Version : How to detect "vector primitives intersection"?



firegun9
02-03-2005, 09:33 AM
Say an arbitrary vector and a polygon, how do I know if they have intersection?
And if the have, how to get the intersection point?

I think it's kinda like mouse selection, but I need the intersection point, and it seems not exists in the selection buffer.
It's also kinda like ray-plane intersection, but it's not the whole plane, only a restrict region on that plane.

iznogoud
02-03-2005, 01:37 PM
I think I had answered this in the past in more detail,
but here is the idea:

Every polygon that lies on a plane can be triangulated,
so you do that first -- subdivide your polygon into
as many triangles as it takes. Every vector not parallel
to the plane in which your polygon lies will intersect
that plane at some point P. You can find P by writting
the equation of the line of the vector (the direction
cosines are the three slopes) and parametrize it
my a parameter t by choosing any point on the line
and measuring distance between it and any other
point on that line. Concequently, there is a distance
t0 between the arbitrary point on the line that
you have picked and the point of intersection with
the plane. Substitute the components of the line
equation in the plane equation and solver for t.
That t is t0 and from the line equation and t0 you
can compute the coordinates of the point of intersection.

Now there are two posibilities: the point P lies
either inside one of the triangles (or on their
edges) or outside. You perform the "area test" for
all triangles. The area test involves a substantial
amount of computation but works well. Simply, you
compute the area of each triangle and store it.
Then for each of these triangles, compute the area
of the three triangles that are formed by the
point P and each of the three pairs of vertex of
eahc triangle. If the sum of the three areas of
the three newly generated triangles is equal to
the triangles whose vertex pairs you used, then P
lies inside of that triangle, and concequently
inside of your polygon.

Leangthy, but I hope it helps.

endash
02-03-2005, 01:38 PM
This isn't an OpenGL topic directly, so it would go better on the algorithms board.

That said, you just do a line-plane intersection test, then see if the point you find is in the portion of the plane you are interested in.

Aeluned
02-03-2005, 01:40 PM
if the polygon and vector are coplaner the problem is trivial:

for all edges of the polygon:
find the intersection point (if any) of the vector with that edge.
if the intersection point lies on the edge, that's your intersection point, if not, it missed that edge.
keep this up until you find an intersection point lying on an edge or you're out of edges.

I'm assuming you mean for a non-coplaner case in which case it becomes a bit more complicated and we would actually need to think :p

Dirk
02-05-2005, 02:46 PM
For these kinds of non-OpenGL related, more general graphics questions http://www.realtimerendering.com is a good resource. For intersections see http://www.realtimerendering.com/int

Hope it helps