ColIntersect.cpp File Reference

Functions for polygon intersection testing; entry point is intersectPolygons. More...

Include dependency graph for ColIntersect.cpp:


Namespaces

namespace  col

Defines

#define COL_EXPORT
#define COL_EDGE_EDGE(__V0, __U0, __U1)
#define COL_EDGE_AGAINST_TRI(_V0, _V1, _U0, _U1, _U2)

Functions

bool computeIntervals (float vv0, float vv1, float vv2, float d0, float d1, float d2, float d0d1, float d0d2, float &isect0, float &isect1, float epsilon)
bool col::intersectPolygons (const Pnt3f *poly1, int plSize1, const Pnt3f *poly2, int plSize2, const unsigned int *index1, const unsigned int *index2, const osg::Matrix *cxform)
 Check if two polygons intersect.
bool col::intersectQuadrangles (const osg::Pnt3f &polyVv0, const osg::Pnt3f &polyVv1, const osg::Pnt3f &polyVv2, const osg::Pnt3f &polyVv3, const osg::Pnt3f &polyUv0, const osg::Pnt3f &polyUv1, const osg::Pnt3f &polyUv2, const osg::Pnt3f &polyUv3, const osg::Vec3f &normal1V, const osg::Vec3f &normal2V)
 Checks whether two quadrangles intersect.
bool col::intersectTriangles (const Pnt3f &polyVv0, const Pnt3f &polyVv1, const Pnt3f &polyVv2, const Pnt3f &polyUv0, const Pnt3f &polyUv1, const Pnt3f &polyUv2)
 Checks if two triangles intersect.
bool col::intersectTriangles (const Pnt3f &polyVv0, const Pnt3f &polyVv1, const Pnt3f &polyVv2, const Pnt3f &polyUv0, const Pnt3f &polyUv1, const Pnt3f &polyUv2, const Vec3f &n1V, const Vec3f &n2V)
 Checks if two triangles intersect.
bool col::intersectCoplanarEdges (const Pnt3f &v0V, const Pnt3f &v1V, const Pnt3f &u0V, const Pnt3f &u1V, unsigned int x, unsigned int y)
 Checks if the edges intersect in 2D.
bool col::intersectEdgePolygon (const Pnt3f &v1, const Pnt3f &v2, const Pnt3f *poly, unsigned int plSize, const Vec3f &normalV, unsigned int x, unsigned int y)
 Checks, if edge intersects polygon.
bool col::intersectEdgePolygon (const Pnt3f &v1, const Pnt3f &v2, const Pnt3f *poly, unsigned int plSize)
 This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
bool col::intersectArbPolygons (const Pnt3f *poly1, unsigned int plSize1, const Pnt3f *poly2, unsigned int plSize2, const Vec3f &normal1V, const Vec3f &normal2V)
 Checks if two polygons intersect.
bool col::intersectArbPolygons (const Pnt3f *poly1, unsigned int plSize1, const Pnt3f *poly2, unsigned int plSize2)
 This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Detailed Description

Functions for polygon intersection testing; entry point is intersectPolygons.

Optimization:
1) For arbitrary collision testing, intersectPolygons automatically chooses the fastest algorithm, either the intersectEdgePolygon or intersectTriangles 2) intersectPolygons seems to be the fastest version for intersection tests of arbitrary polygons. If you know that you have only triangles or convex quadrangles, then it is probably faster to bypass this wrapper routine, and call intersectTriangles directly. If you know that you have only 5-gons or more vertices, then you can call intersectArbPolygons directly. 4) intersectArbPolygons: all polygons (incl. triangles) are passed directly to intersectEdgePolygon.
Todo:
Implementation:
Warning:
It's assumed, that the class Pnt3f has no virtual function table! We use uninitialized memory to store an array of Pnt3f in intersectPolygons!!
Bug:
Cannot handle degenerate polygons (line or point)!
Author:
Alexander Rettig (arettig@igd.fhg.de)

Define Documentation

#define COL_EDGE_AGAINST_TRI ( _V0,
_V1,
_U0,
_U1,
_U2   ) 

Value:

{                                                                   \
                                    /* temporary variables, also for    */  \
                                    /* interaction with COL_EDGE_EDGE   */  \
            float _Ax, _Ay, _Bx, _By, _Cx, _Cy, _EE, _DD, _FF;              \
            _Ax = _V1 [i] - _V0 [i];                                        \
            _Ay = _V1 [j] - _V0 [j];                                        \
                                    /* test edge U0,U1 against V0,V1    */  \
            COL_EDGE_EDGE(_V0, _U0, _U1);                                   \
                                    /* test edge U1,U2 against V0,V1    */  \
            COL_EDGE_EDGE(_V0, _U1, _U2);                                   \
                                    /* test edge U2,U1 against V0,V1    */  \
            COL_EDGE_EDGE(_V0, _U2, _U0);                                   \
        }

#define COL_EDGE_EDGE ( __V0,
__U0,
__U1   ) 

Value:

_Bx = __U0 [i] - __U1 [i];                                          \
        _By = __U0 [j] - __U1 [j];                                          \
        _Cx = __V0 [i] - __U0 [i];                                          \
        _Cy = __V0 [j] - __U0 [j];                                          \
        _FF = _Ay * _Bx - _Ax * _By;                                        \
        _DD = _By * _Cx - _Bx * _Cy;                                        \
        if((_FF > 0 && _DD >= 0 && _DD <= _FF) ||                           \
           (_FF < 0 && _DD <= 0 && _DD >= _FF))                             \
        {                                                                   \
            _EE = _Ax * _Cy - _Ay * _Cx;                                    \
            if(_FF > 0)                                                     \
            {                                                               \
                if(_EE >= 0 && _EE <= _FF) return true;                     \
            }                                                               \
            else                                                            \
            {                                                               \
                if(_EE <= 0 && _EE >= _FF) return true;                     \
            }                                                               \
        }

Generated on Tue Oct 16 18:12:33 2007 for CollDet by  doxygen 1.5.2