Ray-Polygon Inside/Outside tests

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]

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]

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 ?

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...

these functions above are not optimized
*gonna add some ASM code soon* and make variables static