Archived

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

Ray-Polygon Inside/Outside tests

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

Recommended Posts

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 on other sites
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 on other sites
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?

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

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

Share on other sites
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 on other sites
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 on other sites
these functions above are not optimized
*gonna add some ASM code soon* and make variables static

1. 1
2. 2
3. 3
Rutin
19
4. 4
5. 5

• 14
• 30
• 13
• 11
• 11
• Forum Statistics

• Total Topics
631780
• Total Posts
3002314
×