- Main Page
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# 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:
  - Return intersection point.

Implementation:
  - All "functions" beginning with "col_" are macros defined in ColUtils.h.
  - Based upon routines from y/arbcoll.c and work done by Andreas Hess in 1998.

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;                     \
                }                                                               \
            }