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

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

Powered by vBulletin® Version 4.2.5 Copyright © 2018 vBulletin Solutions Inc. All rights reserved.