Archived

This topic is now archived and is closed to further replies.

MindCode

Ray-Polygon Inside/Outside tests

Recommended Posts

MindCode    122
I''m sure that I''m the millionth person to ask this question. I hope none of you mind me asking again. I''m having trouble finding a "good" article on this topic. I just need a (preferably simple) method of testing if a ray which intersects a polygons plane lies within the polygons area (actually intersects, or just passes outside the edge). Most of the articles I''ve read deal with the "projection" method where the polygon is projected into 2d before the test. This really doesn''t help me. The polygons are triangular and the plane is precalculated already. Any links/sugestions would be helpful.

Share this post


Link to post
Share on other sites
Xtremehobo    820
clicky
Thats a really nice one- Even I (a math illiterate person) was able to create a working engine that tested if rays intersected with triangles.



-----


[edited by - Xtremehobo on May 28, 2003 9:36:42 PM]

Share this post


Link to post
Share on other sites
MindCode    122
I'm sorry but I don't see what your getting at. I know all about vector normals and the plane equation, but I'm pretty sure they have little to do with determining if a point is inside a polygon. Am I missing something?

[edit]

OOOHHHHH! Ok, I've checked the rest of the site. Thanks.

[edited by - MindCode on May 28, 2003 11:49:44 PM]

Share this post


Link to post
Share on other sites
v71    100
MindCode, if you would have known everything about vectors and normals, surely you would have used edge normals or antinormals for point test, don''t assume you know everything because everything was written in some tutorial , do you know that tutorials are always the same ?

Share this post


Link to post
Share on other sites
Basiror    241
here is an ray plane intersection function
actually it should be called edge plane intersection

edge because it returns true when your intersection point lies between the 2 vertices which define the edge i use this to create my own CSG algorithm

BOOL LinePlaneIntersection(vec3_t normal, float d, vec3_t s, vec3_t e,vec3_t point)
{
float p;
float length;
float div;
vec3_t dir;
VectorSubtract(e,s,dir);

p=(-DotProduct(s,normal)-d)/DotProduct(dir,normal);
length=Length(dir);

div=p/length;
if(div<(1+EPSILON) && div>-EPSILON)
{
point[0]=s[0]+dir[0]*p;
point[1]=s[1]+dir[1]*p;
point[2]=s[2]+dir[2]*p;
return TRUE;
}
return FALSE;
}


the next function checks whether a POINT is inside the polygon by summing up all the corner-point-corner angles

the sum needs to be 360° the fabs(angle-360)<0.5 is due to precision issues

if(VectorEqual(p->p,point))
return TRUE;
checks if the point is an edge vertex since the angle function wouldn t work properly anymore when the point is very near to an corner vertex





BOOL CRPolygon::InsidePolygon(vec3_t point)
{
if(!vertices)
return FALSE;
CRVertex *p=vertices;
vec3_t a;
vec3_t b;
float angle=0;
while(p)
{
if(VectorEqual(p->p,point))
return TRUE;
VectorSubtract(point,p->p,a);
VectorNormalize(a);
if(p->next)
{
VectorSubtract(point,p->next->p,b);
}
else
{
VectorSubtract(point,vertices->p,b);
}
VectorNormalize(b);
angle+=(float)((acos(DotProduct(a,b)))*180/M_PI);
}

if(fabs(angle - 360)<0.5)
return TRUE;

/*if(fabs(angle - 180)<0.5)
return TRUE;*/

return FALSE;
}

another note:
all the formulas/ideas in those functions have been derived by me without looking through tutorials so i am of the opinion that it is some kind of lazyness to ask for solution for these kind of easy problems especially when you
...know all about vector normals and the plane equation, but I''m pretty sure they have little to do with determining if a point is inside a polygon...

Share this post


Link to post
Share on other sites