/*
 *  Collision plugin for Renderware.
 */

/*
 *  File : ctworld.c
 *
 *  The code is broken up into 4 sections:-
 *
 *  1) World sector intersections
 *  2) Polygon intersections in world sectors
 *  3) Atomic intersections in world sectors
 *  4) API interface
 */

/******************************************************************************
 *  Include files
 */
#include <rwcore.h>
#include <rpworld.h>
#include <rtintsec.h>

#include "rpplugin.h"
#include <rpdbgerr.h>
#include "rpcollis.h"

#include "ctbsp.h"
#include "ctbuild.h"
#include "ctdef.h"
#include "ctworld.h"

#if (!defined(DOXYGEN))
static const char rcsid[] __RWUNUSED__ =
    "@@@@(#)$Id: ctworld.c,v 1.19 2001/05/24 08:03:31 johns Exp $";
#endif /* (!defined(DOXYGEN)) */


/******************************************************************************
 *  Local types
 */

/*
 *  Structures for storing precalc data
 */
typedef struct TestLine TestLine;
struct TestLine
{
    RwLine             *line;
    RwV3d               dir;
    RwReal              length;
    RwReal              recipLength;
};

typedef struct TestSphere TestSphere;
struct TestSphere
{
    RwSphere           *sphere;
    RwReal              recipRadius;
};

/*
 *  Top level call back parameters
 */
typedef union IntersectionCallBack IntersectionCallBack;
union IntersectionCallBack
{
    RpIntersectionCallBackWorldSector sectorCB;
    RpIntersectionCallBackWorldTriangle worldCB;
    RpIntersectionCallBackAtomic atomicCB;
};

typedef struct CallBackParam CallBackParam;
struct CallBackParam
{
    RpIntersection     *intersection;
    IntersectionCallBack u;
    void               *data;
};

/*
 *  Polygon intersection test parameters
 */

typedef struct PolyTestParam PolyTestParam;
struct PolyTestParam
{
    /* Bounding box for walking object down BSP tree */
    RwBBox              bbox;

    /* Leaf test data */
    RpWorldSector      *worldSector;
    RpCollBSPLeafCB     leafTest;
    RpCollBSPLeafCB     v303leafTest; /* For backward compatibility */
    void               *leafTestData;

    /* Polygon callback */
    CallBackParam      *cbParam;
};

typedef struct PolyLineTestParam PolyLineTestParam;
struct PolyLineTestParam
{
    /* Gradient for fast clipping line to BSP */
    RpV3dGradient       grad;
    RwLine              clippedLine;

    /* Leaf test data */
    RpWorldSector      *worldSector;
    RwV3d              *start;
    RwV3d               delta;

    /* Polygon callback */
    CallBackParam      *cbParam;
};

/*
 *  Atomic intersection test parameters
 */

typedef struct AtomicTestParam AtomicTestParam;
struct AtomicTestParam
{
    CallBackParam       cbParam;
    RpWorldSector      *worldSector;
    RpAtomicCallBack    atomicCallBack;
    RpAtomic           *testAtomic; /* For type rpINTERSECTATOMIC */
    void               *testData;
};

/******************************************************************************
 *  Macros
 */

#define INTERVALDIST(inf, sup, val) \
     ((val<inf) ? (inf-val) : ((val>sup) ? (val-sup) : 0.0f))

/* BBoxSphereDistanceMacro: get squared distance of sphere centre from a
 * bounding box, or zero if inside.
 */
#define BBoxSphereDistanceMacro(distSq, bbox, sphere)                       \
MACRO_START                                                                 \
{                                                                           \
    RwV3d   dist;                                                           \
    dist.x = INTERVALDIST((bbox)->inf.x, (bbox)->sup.x, (sphere)->center.x);\
    dist.y = INTERVALDIST((bbox)->inf.y, (bbox)->sup.y, (sphere)->center.y);\
    dist.z = INTERVALDIST((bbox)->inf.z, (bbox)->sup.z, (sphere)->center.z);\
    distSq = RwV3dDotProduct(&dist, &dist);                                 \
}                                                                           \
MACRO_STOP

/******************************************************************************
 */

/*
 * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 *
 *      WORLD SECTOR INTERSECTIONS
 *
 *  Finding world sectors that intersect a line, bounding box, or sphere
 *  primitive.
 *
 * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 */

/******************************************************************************
 *
 *  Line intersections.
 *
 *  Walk lines down world BSP, and pass to callBack for each world
 *  sector intersection.
 *
 *  If clippedLineOut pointer is non-NULL, then the line portion as clipped
 *  to the current sector is copied to this location, and so may be
 *  propagated to the callback if required.
 */
static RpWorld     *
WorldForAllLineWorldSectorIntersections(RpWorld * world,
                                        RwLine * testLine,
                                        RpV3dGradient * grad,
                                        RpWorldSectorCallBack callBack,
                                        void *data,
                                        RwLine * clippedLineOut)
{
    /* Need stack for walking down sector BSP tree */
    RwInt32             nStack;
    RpSector           *sector, *sectorStack[rpWORLDMAXBSPDEPTH];
    RwLine              line, lineStack[rpWORLDMAXBSPDEPTH];

#define STACK_PUSH(sector, lineStart, lineEnd)      \
    MACRO_START                                     \
    {                                               \
        nStack++;                                   \
        sectorStack[nStack] = (sector);             \
        lineStack[nStack].start = (lineStart);      \
        lineStack[nStack].end   = (lineEnd);        \
    }                                               \
    MACRO_STOP

    RWFUNCTION(RWSTRING("WorldForAllLineWorldSectorIntersections"));
    RWASSERT(world);
    RWASSERT(testLine);
    RWASSERT(grad);
    RWASSERT(callBack);

    /* Start at the top */
    nStack = 0;
    sector = world->rootSector;
    line = *testLine;

    while (nStack >= 0)
    {
        if (sector->type < 0)
        {
            /* It's a world sector, propagate clipped line if required */
            if (clippedLineOut)
            {
                *clippedLineOut = line;
            }

            /* Do callback */
            if (!callBack((RpWorldSector *) sector, data))
            {
                /* Early out */
                RWRETURN(world);
            }

            /* Stack back */
            sector = sectorStack[nStack];
            line = lineStack[nStack];
            nStack--;
        }
        else
        {
            /* Its a dividing plane, find out which way we need to go */
            RpPlaneSector      *plane = (RpPlaneSector *) sector;
            RwSplitBits         lStart, lEnd;
            RwSplitBits         rStart, rEnd;

            /* Find out where line end points are in relation to the plane */
            lStart.nReal =
                GETCOORD(line.start, plane->type) - plane->leftValue;
            lEnd.nReal =
                GETCOORD(line.end, plane->type) - plane->leftValue;
            rStart.nReal =
                GETCOORD(line.start, plane->type) - plane->rightValue;
            rEnd.nReal =
                GETCOORD(line.end, plane->type) - plane->rightValue;

            /* First test if it's entirely one side or the other */
            if (rStart.nInt < 0 && rEnd.nInt < 0)
            {
                /* Totally left */
                sector = plane->leftSubTree;
            }
            else if (lStart.nInt >= 0 && lEnd.nInt >= 0)
            {
                /* Totally right */
                sector = plane->rightSubTree;
            }
            else if (!((lStart.nInt ^ lEnd.nInt) & 0x80000000) &&
                     !((rStart.nInt ^ rEnd.nInt) & 0x80000000))
            {
                /* Doesn't cross either, sat in overlap regions */
                if (rStart.nInt < rEnd.nInt)
                {
                    /* Stack right, go left */
                    STACK_PUSH(plane->rightSubTree, line.start,
                               line.end);
                    sector = plane->leftSubTree;
                }
                else
                {
                    /* Stack left, go right */
                    STACK_PUSH(plane->leftSubTree, line.start,
                               line.end);
                    sector = plane->rightSubTree;
                }
            }
            else
            {
                if (((lStart.nInt ^ lEnd.nInt) & 0x80000000) &&
                    (rStart.nInt >= 0 && rEnd.nInt >= 0))
                {
                    /* Crosses left and totally in right */
                    RwV3d               vTmp;

                    _rpLinePlaneIntersectMacro(&vTmp, &line, grad,
                                               plane->type,
                                               plane->leftValue);

                    if (lStart.nInt < 0)
                    {
                        /* Stack right, go left */
                        STACK_PUSH(plane->rightSubTree, line.start,
                                   line.end);
                        sector = plane->leftSubTree;
                        line.end = vTmp;
                    }
                    else
                    {
                        /* Stack left, go right */
                        STACK_PUSH(plane->leftSubTree, vTmp, line.end);
                        sector = plane->rightSubTree;
                    }
                }
                else if (((rStart.nInt ^ rEnd.nInt) & 0x80000000) &&
                         (lStart.nInt < 0 && lEnd.nInt < 0))
                {
                    /* Crosses right and totally in left */
                    RwV3d               vTmp;

                    /* Calculate an intersection point for right plane */
                    _rpLinePlaneIntersectMacro(&vTmp, &line, grad,
                                               plane->type,
                                               plane->rightValue);

                    if (rStart.nInt < 0)
                    {
                        /* Stack right, go left */
                        STACK_PUSH(plane->rightSubTree, vTmp, line.end);
                        sector = plane->leftSubTree;
                    }
                    else
                    {
                        /* Stack left, go right */
                        STACK_PUSH(plane->leftSubTree, line.start,
                                   line.end);
                        sector = plane->rightSubTree;
                        line.end = vTmp;
                    }
                }
                else
                {
                    /* Crosses both planes */
                    RwV3d               vLeft, vRight;

                    /* Get plane intersections */
                    _rpLinePlaneIntersectMacro(&vRight, &line, grad,
                                               plane->type,
                                               plane->rightValue);
                    _rpLinePlaneIntersectMacro(&vLeft, &line, grad,
                                               plane->type,
                                               plane->leftValue);

                    if (lStart.nInt < 0)
                    {
                        /* Stack right, go left */
                        STACK_PUSH(plane->rightSubTree, vRight,
                                   line.end);
                        sector = plane->leftSubTree;
                        line.end = vLeft;
                    }
                    else
                    {
                        /* Stack left, go right */
                        STACK_PUSH(plane->leftSubTree, vLeft, line.end);
                        sector = plane->rightSubTree;
                        line.end = vRight;
                    }
                }
            }
        }
    }

    /* All done */
    RWRETURN(world);
}

/****************************************************************************
 *
 *  Box intersections.
 */
static RpWorld     *
WorldForAllBoxWorldSectorIntersections(RpWorld * world,
                                       RwBBox * box,
                                       RpWorldSectorCallBack callBack,
                                       void *data)
{
    RwInt32             nStack;
    RpSector           *sector, *sectorStack[rpWORLDMAXBSPDEPTH];

    RWFUNCTION(RWSTRING("WorldForAllBoxWorldSectorIntersections"));
    RWASSERT(world);
    RWASSERT(box);
    RWASSERT(callBack);

    /* Start at the top */
    nStack = 0;
    sector = world->rootSector;

    while (nStack >= 0)
    {
        if (sector->type < 0)
        {
            /* Its a world sector, call the callback */
            if (!callBack((RpWorldSector *) sector, data))
            {
                /* Early out */
                RWRETURN(world);
            }

            /* Stack back */
            sector = sectorStack[nStack--];
        }
        else
        {
            /* It's a dividing plane */
            RpPlaneSector      *plane = (RpPlaneSector *) sector;

            if (GETCOORD(box->inf, plane->type) < plane->leftValue)
            {
                /* Go left */
                sector = plane->leftSubTree;

                if (GETCOORD(box->sup, plane->type) >=
                    plane->rightValue)
                {
                    /* Also in right, so stack */
                    sectorStack[++nStack] = plane->rightSubTree;
                }
            }
            else
            {
                /* Must be completely in right */
                sector = plane->rightSubTree;
            }
        }
    }

    /* All done */
    RWRETURN(world);
}

/******************************************************************************
 *
 *  Sphere intersections. Uses precise test of sphere against the world
 *  sector bounding boxes.
 */
static RpWorld     *
WorldForAllSphereWorldSectorIntersections(RpWorld * world,
                                          RwSphere * sphere,
                                          RpWorldSectorCallBack
                                          callBack, void *data)
{
    RwInt32             nStack;
    RwBBox              bbox, bboxStack[rpWORLDMAXBSPDEPTH];
    RpSector           *sector, *sectorStack[rpWORLDMAXBSPDEPTH];
    RwReal              sphereRadSq;

    RWFUNCTION(RWSTRING("WorldForAllSphereWorldSectorIntersections"));
    RWASSERT(world);
    RWASSERT(sphere);
    RWASSERT(callBack);
    RWASSERT(sphere->radius >= 0.0f);

    sphereRadSq = sphere->radius * sphere->radius;

    /* Start at the top */
    nStack = 0;
    sector = world->rootSector;
    bbox = world->boundingBox;

    while (nStack >= 0)
    {
        RwReal              distSq;

        BBoxSphereDistanceMacro(distSq, &bbox, sphere);

        if (distSq > sphereRadSq)
        {
            /* Sphere is outside bounding box, recurse back a level */
            sector = sectorStack[nStack];
            bbox = bboxStack[nStack];
            nStack--;
        }
        else
        {
            if (sector->type < 0)
            {
                /* Its an atomic sector -> do the callback */
                if (!callBack((RpWorldSector *) sector, data))
                {
                    /* Early out */
                    RWRETURN(world);
                }

                /* Stack back */
                sector = sectorStack[nStack];
                bbox = bboxStack[nStack];
                nStack--;
            }
            else
            {
                /* Its a plane */
                RpPlaneSector      *plane = (RpPlaneSector *) sector;

                /* Stack right */
                nStack++;
                sectorStack[nStack] = plane->rightSubTree;
                bboxStack[nStack] = bbox;
                SETCOORD(bboxStack[nStack].inf, plane->type,
                         plane->rightValue);

                /* Go left */
                SETCOORD(bbox.sup, plane->type, plane->leftValue);
                sector = plane->leftSubTree;
            }
        }
    }

    RWRETURN(world);
}

/*
 * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 *
 *      POLYGON INTERSECTIONS IN WORLD SECTORS
 *
 *  Finding intersections of the world's static geometry polygons with
 *  line, sphere and box primitives. This uses the collision BSP tree
 *  of a world sector. Backward compatibility functions are provided for
 *  processing old-style v3.03 collision trees.
 *
 * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 */

/******************************************************************************
 *
 *  World sector line intersections (using v3.03 collision BSPs).
 */
static RpWorldSector *
OldWorldSectorForAllLinePolyIntersections(RpWorldSector * worldSector,
                                          PolyLineTestParam * isData)
{
    RWFUNCTION(RWSTRING("OldWorldSectorForAllLinePolyIntersections"));
    RWASSERT(worldSector);
    RWASSERT(isData);

    /* We can't handle sectors without collision trees */
    if (worldSector->colSectorRoot)
    {
        CallBackParam      *cbParam = isData->cbParam;
        RpCollSector       *collSector = worldSector->colSectorRoot;
        RwV3d              *vertices = worldSector->vertices;
        RwInt32             nStack;
        RwInt32             cut, cutStack[16];
        RwLine              line, lineStack[16];

        /* Start at top of BSP tree */
        cut = 1;
        line = isData->clippedLine;
        nStack = 0;
        while (nStack >= 0)
        {
            RwInt32             numPolygons;
            RwInt32             polyOffset;
            RpPolygon          *poly;

            if (RWCOLLSECTORGETTYPE(collSector[cut]))
            {
                /* We have a dividing plane */
                RwInt32             plane;
                RwReal              value;
                RwSplitBits         start, end;

                plane = RWCOLLSECTORGETPLANE(collSector[cut]);
                value =
                    GETCOORD(vertices
                             [RWCOLLSECTORGETVERTEX(collSector[cut])],
                             plane);
                start.nReal = GETCOORD(line.start, plane) - value;
                end.nReal = GETCOORD(line.end, plane) - value;

                /* Get polygons lying on the plane */
                numPolygons = RWCOLLSECTORGETON(collSector[cut]);
                polyOffset = RWCOLLSECTORGETSTART(collSector[cut]);

                if ((start.nInt ^ end.nInt) & 0x80000000)
                {
                    /* Line is split across the plane, get intersection */
                    RwV3d               vTmp;

                    _rpLinePlaneIntersectMacro(&vTmp, &line,
                                               &isData->grad, plane,
                                               value);

                    /* Stack end piece of line, keep first piece */
                    nStack++;
                    cutStack[nStack] = (start.nInt < 0) ?
                        (cut + cut + 1) : (cut + cut);
                    lineStack[nStack].start = vTmp;
                    lineStack[nStack].end = line.end;
                    line.end = vTmp;
                }

                cut = (start.nInt < 0) ? (cut + cut) : (cut + cut + 1);
            }
            else
            {
                /* We have a leaf node - get polygons */
                numPolygons = RWCOLLSECTORGETNOPOLYS(collSector[cut]);
                polyOffset = RWCOLLSECTORGETSTART(collSector[cut]);

                /* Unstack for next time */
                cut = cutStack[nStack];
                line = lineStack[nStack];
                nStack--;
            }

            /* Now do fine test on polygons */
            poly = worldSector->polygons + polyOffset;
            while (numPolygons--)
            {
                RwV3d              *v0, *v1, *v2;
                RwReal              distance;
                RwBool              result;

                v0 = vertices + poly->vertIndex[0];
                v1 = vertices + poly->vertIndex[1];
                v2 = vertices + poly->vertIndex[2];

                RtIntersectionLineTriangleMacro(result, isData->start,
                                                &isData->delta, v0, v1,
                                                v2, &distance);

                if (result)
                {
                    RpCollisionTriangle collTri;

                    collTri.point = (*v0);
                    collTri.index = polyOffset;
                    _rpTriangleNormalMacro(&collTri.normal, v0, v1, v2);
                    collTri.vertices[0] = v0;
                    collTri.vertices[1] = v1;
                    collTri.vertices[2] = v2;

                    if (!cbParam->u.worldCB(cbParam->intersection,
                                            worldSector, &collTri,
                                            distance, cbParam->data))
                    {
                        /* Early out */
                        RWRETURN(NULL);
                    }
                }

                polyOffset++;
                poly++;
            }
        }
    }

    RWRETURN(worldSector);
}

/******************************************************************************
 *
 *  Box intersections with world sector polygons.
 *
 *  For v3.03 collision BSPs (numPolygons, nOffset) reference sector polygons
 *  directly.
 */
static              RwBool
OldLeafNodeForAllBoxPolyIntersections(RwInt32 numPolygons,
                                      RwInt32 polyOffset, void *data)
{
    PolyTestParam      *isData = (PolyTestParam *) data;
    CallBackParam      *cbParam = isData->cbParam;
    RpWorldSector      *worldSector = isData->worldSector;
    RwV3d              *vertices = worldSector->vertices;
    RpPolygon          *poly;

    RWFUNCTION(RWSTRING("OldLeafNodeForAllBoxPolyIntersections"));
    RWASSERT(numPolygons >= 0);
    RWASSERT(polyOffset >= 0);
    RWASSERT(isData);

    poly = worldSector->polygons + polyOffset;
    while (numPolygons--)
    {
        RwV3d              *v0, *v1, *v2;
        RpCollisionTriangle collTri;

        v0 = vertices + poly->vertIndex[0];
        v1 = vertices + poly->vertIndex[1];
        v2 = vertices + poly->vertIndex[2];

        if (RtIntersectionBBoxTriangle(&isData->bbox, v0, v1, v2))
        {
            collTri.point = (*v0);
            collTri.index = polyOffset;
            _rpTriangleNormalMacro(&collTri.normal, v0, v1, v2);
            collTri.vertices[0] = v0;
            collTri.vertices[1] = v1;
            collTri.vertices[2] = v2;

            /* Note: distance not defined */
            if (!cbParam->u.worldCB(cbParam->intersection,
                                    worldSector, &collTri, 0.0f,
                                    cbParam->data))
            {
                /* Early out */
                RWRETURN(FALSE);
            }
        }

        polyOffset++;
        poly++;
    }

    RWRETURN(TRUE);
}

/******************************************************************************
 *
 *  Sphere intersections with world sector polygons.
 *
 *  For v3.03 collision BSPs (numPolygons, polyOffset) reference sector polygons
 *  directly.
 */
static              RwBool
OldLeafNodeForAllSpherePolyIntersections(RwInt32 numPolygons,
                                         RwInt32 polyOffset, void *data)
{
    PolyTestParam      *isData = (PolyTestParam *) data;
    TestSphere         *testSphere =
        (TestSphere *) isData->leafTestData;
    CallBackParam      *cbParam = isData->cbParam;
    RpWorldSector      *worldSector = isData->worldSector;
    RwV3d              *vertices = worldSector->vertices;
    RpPolygon          *poly;

    RWFUNCTION(RWSTRING("OldLeafNodeForAllSpherePolyIntersections"));
    RWASSERT(numPolygons >= 0);
    RWASSERT(polyOffset >= 0);
    RWASSERT(isData);

    poly = worldSector->polygons + polyOffset;
    while (numPolygons--)
    {
        RwV3d              *v0, *v1, *v2;
        RwReal              distance;
        RpCollisionTriangle collTri;

        v0 = vertices + poly->vertIndex[0];
        v1 = vertices + poly->vertIndex[1];
        v2 = vertices + poly->vertIndex[2];

        if (RtIntersectionSphereTriangle(testSphere->sphere,
                                         v0, v1, v2, &collTri.normal,
                                         &distance))
        {
            /* Got one */
            collTri.point = (*v0);
            collTri.index = polyOffset;
            collTri.vertices[0] = v0;
            collTri.vertices[1] = v1;
            collTri.vertices[2] = v2;

            /* Normalize distance with precalculated reciprocal radius */
            distance *= testSphere->recipRadius;

            if (!cbParam->u.worldCB(cbParam->intersection, worldSector,
                                    &collTri, distance, cbParam->data))
            {
                /* Early out */
                RWRETURN(FALSE);
            }
        }

        polyOffset++;
        poly++;
    }

    RWRETURN(TRUE);
}

/******************************************************************************
 *
 *  World sector boxed primitive intersections (using v3.03 collision trees).
 *
 *  The first stage is to propagate the bounding box of the object (box,
 *  sphere, or atomic) down the BSP tree. The detailed polygon tests are done
 *  using the appropriate callBack set in isData.
 */
static RpWorldSector *
OldWorldSectorForAllBoxedPrimitivePolyIntersections(RpWorldSector * worldSector,
                                                    PolyTestParam * isData)
{
    RWFUNCTION(RWSTRING("OldWorldSectorForAllBoxedPrimitivePolyIntersections"));
    RWASSERT(worldSector);
    RWASSERT(isData);

    /* We can't handle sectors without collision trees */
    if (worldSector->colSectorRoot)
    {
        RpCollSector       *collSector = worldSector->colSectorRoot;
        RwV3d              *vertices = worldSector->vertices;
        RwInt32             nStack;
        RwInt32             cut, cutStack[16];

        cut = 1;
        nStack = 0;
        while (nStack >= 0)
        {
            RwInt32             numPolygons;
            RwInt32             polyOffset;

            if (RWCOLLSECTORGETTYPE(collSector[cut]))
            {
                /* We have a dividing plane */
                RwInt32             plane;
                RwReal              value;
                RwSplitBits         left, right;

                plane = RWCOLLSECTORGETPLANE(collSector[cut]);
                value =
                    GETCOORD(vertices
                             [RWCOLLSECTORGETVERTEX(collSector[cut])],
                             plane);
                left.nReal = GETCOORD(isData->bbox.inf, plane) - value;
                right.nReal = value - GETCOORD(isData->bbox.sup, plane);

                /* Polygons lying on the plane */
                numPolygons = RWCOLLSECTORGETON(collSector[cut]);
                polyOffset = RWCOLLSECTORGETSTART(collSector[cut]);

                if (left.nInt < 0)
                {
                    if (right.nInt < 0)
                    {
                        cutStack[++nStack] = cut + cut + 1;
                    }
                    /* Go left */
                    cut = cut + cut;
                }
                else
                {
                    if (right.nInt < 0)
                    {
                        /* Go right */
                        cut = cut + cut + 1;
                    }
                }
            }
            else
            {
                /* We have a leaf node - get polygons */
                numPolygons = RWCOLLSECTORGETNOPOLYS(collSector[cut]);
                polyOffset = RWCOLLSECTORGETSTART(collSector[cut]);

                /* Unstack */
                cut = cutStack[nStack--];
            }

            /* Do fine test on polygons */
            if (!isData->v303leafTest(numPolygons, polyOffset, isData))
            {
                /* Early out */
                RWRETURN(NULL);
            }
        }
    }

    RWRETURN(worldSector);
}

/******************************************************************************
 *
 *  Line test with polygons in BSP leaf node
 */
static              RwBool
LeafNodeForAllLinePolyIntersections(RwInt32 numPolygons,
                                    RwInt32 polyOffset, void *data)
{
    PolyLineTestParam  *isData = (PolyLineTestParam *) data;
    CallBackParam      *cbParam = isData->cbParam;
    RpWorldSector      *worldSector = isData->worldSector;
    RwV3d              *vertices = worldSector->vertices;
    RpPolygon          *polygons = worldSector->polygons;
    RwUInt16           *polyIndex =
        (*RPWORLDSECTORCOLLISIONDATA(worldSector))->triangleMap +
        polyOffset;

    RWFUNCTION(RWSTRING("LeafNodeForAllLinePolyIntersections"));
    RWASSERT(numPolygons >= 0);
    RWASSERT(polyOffset >= 0);
    RWASSERT(isData);

    while (numPolygons--)
    {
        RpPolygon          *poly;
        RwV3d              *v0, *v1, *v2;
        RwReal              distance;
        RwBool              result;

        poly = polygons + *polyIndex;
        v0 = vertices + poly->vertIndex[0];
        v1 = vertices + poly->vertIndex[1];
        v2 = vertices + poly->vertIndex[2];

        /* Test for collision */
        RtIntersectionLineTriangleMacro(result,
                                        isData->start, &isData->delta,
                                        v0, v1, v2, &distance);

        if (result)
        {
            RpCollisionTriangle collisionTri;

            /* We've got one */
            collisionTri.point = (*v0);
            collisionTri.index = *polyIndex;
            _rpTriangleNormalMacro(&collisionTri.normal, v0, v1, v2);
            collisionTri.vertices[0] = v0;
            collisionTri.vertices[1] = v1;
            collisionTri.vertices[2] = v2;

            if (!cbParam->u.worldCB(cbParam->intersection, worldSector,
                                    &collisionTri, distance,
                                    cbParam->data))
            {
                /* Early out */
                RWRETURN(FALSE);
            }
        }

        polyIndex++;
    }

    RWRETURN(TRUE);
}

/******************************************************************************
 *
 *  Sphere test with polygons in leaf.
 */
static              RwBool
LeafNodeForAllSpherePolyIntersections(RwInt32 numPolygons,
                                      RwInt32 polyOffset, void *data)
{
    PolyTestParam      *isData = (PolyTestParam *) data;
    CallBackParam      *cbParam = isData->cbParam;
    TestSphere         *testSphere =
        (TestSphere *) isData->leafTestData;
    RpWorldSector      *worldSector = isData->worldSector;
    RwV3d              *vertices = worldSector->vertices;
    RpPolygon          *polygons = worldSector->polygons;
    RwUInt16           *polyIndex =
        (*RPWORLDSECTORCOLLISIONDATA(worldSector))->triangleMap +
        polyOffset;

    RWFUNCTION(RWSTRING("LeafNodeForAllSpherePolyIntersections"));
    RWASSERT(numPolygons >= 0);
    RWASSERT(polyOffset >= 0);
    RWASSERT(isData);

    while (numPolygons--)
    {
        RpPolygon          *poly;
        RwV3d              *v0, *v1, *v2;
        RwReal              distance;
        RpCollisionTriangle collisionTri;

        poly = polygons + *polyIndex;
        v0 = vertices + poly->vertIndex[0];
        v1 = vertices + poly->vertIndex[1];
        v2 = vertices + poly->vertIndex[2];

        /* Test for collision */
        if (RtIntersectionSphereTriangle(testSphere->sphere,
                                         v0, v1, v2,
                                         &collisionTri.normal,
                                         &distance))
        {
            /* We've got one */
            collisionTri.point = (*v0);
            collisionTri.index = *polyIndex;
            collisionTri.vertices[0] = v0;
            collisionTri.vertices[1] = v1;
            collisionTri.vertices[2] = v2;

            /* Normalize distance with precalculated reciprocal radius */
            distance *= testSphere->recipRadius;

            if (!cbParam->u.worldCB(cbParam->intersection, worldSector,
                                    &collisionTri, distance,
                                    cbParam->data))
            {
                /* Early out */
                RWRETURN(FALSE);
            }
        }

        polyIndex++;
    }

    RWRETURN(TRUE);
}

/******************************************************************************
 *
 *  Box test with polygons in leaf.
 */
static              RwBool
LeafNodeForAllBoxPolyIntersections(RwInt32 numPolygons,
                                   RwInt32 polyOffset, void *data)
{
    PolyTestParam      *isData = (PolyTestParam *) data;
    CallBackParam      *cbParam = isData->cbParam;
    RpWorldSector      *worldSector = isData->worldSector;
    RwV3d              *vertices = worldSector->vertices;
    RpPolygon          *polygons = worldSector->polygons;
    RwUInt16           *polyIndex =
        (*RPWORLDSECTORCOLLISIONDATA(worldSector))->triangleMap +
        polyOffset;

    RWFUNCTION(RWSTRING("LeafNodeForAllBoxPolyIntersections"));
    RWASSERT(numPolygons >= 0);
    RWASSERT(polyOffset >= 0);
    RWASSERT(isData);

    while (numPolygons--)
    {
        RpPolygon          *poly;
        RwV3d              *v0, *v1, *v2;
        RpCollisionTriangle collisionTri;

        poly = polygons + *polyIndex;
        v0 = vertices + poly->vertIndex[0];
        v1 = vertices + poly->vertIndex[1];
        v2 = vertices + poly->vertIndex[2];

        /* Test for collision */
        if (RtIntersectionBBoxTriangle(&isData->bbox, v0, v1, v2))
        {
            /* We've got one */
            collisionTri.point = (*v0);
            collisionTri.index = *polyIndex;
            _rpTriangleNormalMacro(&collisionTri.normal, v0, v1, v2);
            collisionTri.vertices[0] = v0;
            collisionTri.vertices[1] = v1;
            collisionTri.vertices[2] = v2;

            /* Note: distance not defined */
            if (!cbParam->u.worldCB(cbParam->intersection, worldSector,
                                    &collisionTri, 0.0f, cbParam->data))
            {
                /* Early out */
                RWRETURN(FALSE);
            }
        }

        polyIndex++;
    }

    RWRETURN(TRUE);
}

/******************************************************************************
 *
 *  Line intersections with polygons in world sector.
 *
 *  Propagate line down world sector collision BSP, and test polygons in leaf
 *  nodes via callback.
 */
static RpWorldSector *
WorldSectorForAllLinePolyIntersections(RpWorldSector * worldSector,
                                       void *data)
{
    PolyLineTestParam  *isData = (PolyLineTestParam *) data;
    RpCollisionData    *collData;

    RWFUNCTION(RWSTRING("WorldSectorForAllLinePolyIntersections"));
    RWASSERT(worldSector);
    RWASSERT(isData);

    collData = *RPWORLDSECTORCOLLISIONDATA(worldSector);

    /* Leaf callback needs world sector */
    isData->worldSector = worldSector;

    /* Check for collision data */
    if (!collData)
    {
        /* Pass on to check for v3.03 BSP trees */
        RWRETURN(OldWorldSectorForAllLinePolyIntersections
                 (worldSector, isData));
    }

    if (!_rpCollBSPTreeForAllLineLeafNodeIntersections(collData->tree,
                                                       &isData->
                                                       clippedLine,
                                                       &isData->grad,
                                                       LeafNodeForAllLinePolyIntersections,
                                                       isData))
    {
        /* Early out */
        RWRETURN(NULL);
    }

    RWRETURN(worldSector);
}

/******************************************************************************
 *
 *  Boxed primitive intersections.
 *
 *  Walk the bounding box down the world sector collision BSP, and test
 *  polygons in leaf nodes via callback.
 */
static RpWorldSector *
WorldSectorForAllBoxedPrimitivePolyIntersections(RpWorldSector * worldSector,
                                                 void *data)
{
    PolyTestParam      *isData = (PolyTestParam *) data;
    RpCollisionData    *collData;

    RWFUNCTION(RWSTRING("WorldSectorForAllBoxedPrimitivePolyIntersections"));
    RWASSERT(worldSector);
    RWASSERT(isData);

    collData = *RPWORLDSECTORCOLLISIONDATA(worldSector);

    /* Leaf callback needs world sector */
    isData->worldSector = worldSector;

    /* Check for collision data */
    if (!collData)
    {
        /* Pass on to check for v3.03 BSP trees */
        RWRETURN(OldWorldSectorForAllBoxedPrimitivePolyIntersections
                 (worldSector, isData));
    }

    if (!_rpCollBSPTreeForAllBoxLeafNodeIntersections(collData->tree,
                                                      &isData->bbox,
                                                      isData->leafTest,
                                                      isData))
    {
        /* Early out */
        RWRETURN(NULL);
    }

    RWRETURN(worldSector);
}

/*
 * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 *
 *      ATOMIC INTERSECTIONS IN WORLD SECTORS (USING BOUNDING SPHERES)
 *
 *  Find atomics in a world sector whose bounding spheres intersect a line,
 *  sphere or box primitive.
 *
 * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 */

/*****************************************************************************
 *
 *  Line intersections
 */
static RpAtomic    *
AtomicLineTest(RpAtomic * atomic, void *data)
{
    RWFUNCTION(RWSTRING("AtomicLineTest"));
    RWASSERT(atomic);
    RWASSERT(data);

    /* Check whether this atomic is flagged for collision tests and that we
     * haven't already tested it via another sector.
     */
    if ((RPATOMICCOLLISIONREF(atomic) !=
         RPCOLLISIONGLOBAL(collisionRef))
        && (RpAtomicGetFlags(atomic) & rpATOMICCOLLISIONTEST))
    {
        AtomicTestParam    *testParam = (AtomicTestParam *) data;
        TestLine           *testLine = (TestLine *) testParam->testData;
        const RwSphere     *boundingSphere;
        RwV3d               vE0;
        RwReal              atomicRadiusSq;
        RwReal              atomicDistance;
        RwReal              hypSq;

        /* Mark it as examined */
        RPATOMICCOLLISIONREF(atomic) = RPCOLLISIONGLOBAL(collisionRef);

        /* Get bounding sphere of atomic */
        boundingSphere = RpAtomicGetWorldBoundingSphere(atomic);
        RWASSERT(boundingSphere);
        atomicRadiusSq =
            boundingSphere->radius * boundingSphere->radius;

        /* Get atomic center relative to line start */
        RwV3dSub(&vE0, &boundingSphere->center, &testLine->line->start);

        /* Project atomic's center distance along line */
        atomicDistance = RwV3dDotProduct(&vE0, &testLine->dir);

        /* Squared distance to atomic center */
        hypSq = RwV3dDotProduct(&vE0, &vE0);

        if (hypSq < atomicRadiusSq)
        {
            /* Start of line is inside the atomic */
            if (!testParam->cbParam.u.
                atomicCB(testParam->cbParam.intersection,
                         testParam->worldSector, atomic,
                         (atomicDistance * testLine->recipLength),
                         testParam->cbParam.data))
            {
                /* Early out at immediate callback level and above */
                testParam->worldSector = NULL;
                RWRETURN(NULL);
            }
        }
        else if (atomicDistance > 0.0f)
        {
            /* It's in front of the line */
            RwReal              disc;

            /* Do pythagoras to see if line trajectory hits sphere */
            disc = atomicRadiusSq -
                (hypSq - (atomicDistance * atomicDistance));
            if (disc >= 0.0f)
            {
                RwReal              rel;

                /* Does line reach sphere? */
                rel = atomicDistance - testLine->length;
                if ((rel < 0.0f) || ((rel * rel) < disc))
                {
                    /* Intersection with bounding sphere */
                    if (!testParam->cbParam.u.
                        atomicCB(testParam->cbParam.intersection,
                                 testParam->worldSector, atomic,
                                 (atomicDistance *
                                  testLine->recipLength),
                                 testParam->cbParam.data))
                    {
                        /* Early out at immediate callback level and above */
                        testParam->worldSector = NULL;
                        RWRETURN(NULL);
                    }
                }
            }
        }
    }

    RWRETURN(atomic);
}

/*****************************************************************************
 *
 *  Sphere intersections (also used for points, and atomics)
 */
static RpAtomic    *
AtomicSphereTest(RpAtomic * atomic, void *data)
{
    AtomicTestParam    *testParam = (AtomicTestParam *) data;

    RWFUNCTION(RWSTRING("AtomicSphereTest"));
    RWASSERT(atomic);
    RWASSERT(data);

    /* Check whether this atomic is flagged for collision tests and that we
     * haven't already tested it via another sector.
     * Also check that we're not intersecting an atomic with itself.
     */
    if (RPATOMICCOLLISIONREF(atomic) != RPCOLLISIONGLOBAL(collisionRef)
        && (RpAtomicGetFlags(atomic) & rpATOMICCOLLISIONTEST)
        && (testParam->testAtomic != atomic))
    {
        const RwSphere     *testSphere =
            (const RwSphere *) testParam->testData;
        const RwSphere     *boundingSphere;
        RwV3d               vDist;
        RwReal              distSq;
        RwReal              sumRadiusSq;

        /* Mark it as examined */
        RPATOMICCOLLISIONREF(atomic) = RPCOLLISIONGLOBAL(collisionRef);

        /* Get the world space bounding sphere */
        boundingSphere = RpAtomicGetWorldBoundingSphere(atomic);
        RWASSERT(boundingSphere);

        sumRadiusSq = testSphere->radius + boundingSphere->radius;
        sumRadiusSq = sumRadiusSq * sumRadiusSq;

        /* Figure out distance between two geometry center points */
        RwV3dSub(&vDist, &boundingSphere->center, &testSphere->center);
        distSq = RwV3dDotProduct(&vDist, &vDist);

        /* Check if it's in range */
        if (distSq < sumRadiusSq)
        {
            RwReal              dist;

            /* Get normalized distance */
            dist = distSq / sumRadiusSq;
            rwSqrtMacro(dist, dist);

            /* Do callback */
            if (!testParam->cbParam.u.
                atomicCB(testParam->cbParam.intersection,
                         testParam->worldSector, atomic, dist,
                         testParam->cbParam.data))
            {
                /* Early out at immediate and next callback level up */
                testParam->worldSector = NULL;
                RWRETURN(NULL);
            }
        }
    }

    RWRETURN(atomic);
}

/******************************************************************************
 *
 *  Box intersections
 */
static RpAtomic    *
AtomicBoxTest(RpAtomic * atomic, void *data)
{
    RWFUNCTION(RWSTRING("AtomicBoxTest"));
    RWASSERT(atomic);
    RWASSERT(data);

    /* Check whether this atomic is flagged for collision tests and that we
     * haven't already tested it via another sector.
     */
    if (RPATOMICCOLLISIONREF(atomic) != RPCOLLISIONGLOBAL(collisionRef)
        && (RpAtomicGetFlags(atomic) & rpATOMICCOLLISIONTEST))
    {
        AtomicTestParam    *testParam = (AtomicTestParam *) data;
        RwBBox             *box = (RwBBox *) testParam->testData;
        const RwSphere     *boundingSphere;
        RwReal              distSq;

        /* Mark it as examined */
        RPATOMICCOLLISIONREF(atomic) = RPCOLLISIONGLOBAL(collisionRef);

        /* Get the world space bounding sphere */
        boundingSphere = RpAtomicGetWorldBoundingSphere(atomic);
        RWASSERT(boundingSphere);

        /* Test for intersection */
        BBoxSphereDistanceMacro(distSq, box, boundingSphere);

        if (distSq < (boundingSphere->radius * boundingSphere->radius))
        {
            if (!testParam->cbParam.u.atomicCB(testParam->cbParam.intersection, testParam->worldSector, atomic, ((RwReal) 0), /* distance undefined */
                                               testParam->cbParam.data))
            {
                /* Early out at immediate callback level and above */
                testParam->worldSector = NULL;
                RWRETURN(NULL);
            }
        }
    }

    RWRETURN(atomic);
}

/******************************************************************************
 *
 *  Generic intersections with atomics in world sector.
 */
static RpWorldSector *
WorldSectorForAllPrimitiveAtomicIntersections(RpWorldSector * worldSector,
                                              void *data)
{
    AtomicTestParam    *testParam = (AtomicTestParam *) data;

    RWFUNCTION(RWSTRING("WorldSectorForAllPrimitiveAtomicIntersections"));
    RWASSERT(worldSector);
    RWASSERT(data);

    testParam->worldSector = worldSector;

    RpWorldSectorForAllCollisionAtomics(worldSector,
                                        testParam->atomicCallBack,
                                        testParam);

    /* Atomic callback sets testParam->worldSector to NULL for early out */
    RWRETURN(testParam->worldSector);
}

/******************************************************************************
 *
 *  _rpCollisionWorldRemoveOffset()
 *
 *  Stealth function for removing offset in v3.04 worlds, so as to resemble
 *  v3.10 worlds.
 */
static RpWorldSector *
CollisionWorldSectorTranslate(RpWorldSector *worldSector, void *data)
{
    RpCollisionData    *collData = *RPWORLDSECTORCOLLISIONDATA(worldSector);
    RwV3d              *offset = (RwV3d *) data;

    RWFUNCTION(RWSTRING("CollisionWorldSectorTranslate"));
    RWASSERT(worldSector);
    RWASSERT(data);

    if (collData)
    {
        /* Translate the positions of the BSP planes */
        _rpCollBSPTreeTranslate(collData->tree, offset);
    }

    RWRETURN(worldSector);
}

RwBool
_rpCollisionWorldRemoveOffset(RpWorld *world)
{
    const RwV3d     *origin;
    RwV3d           tr;

    RWFUNCTION(RWSTRING("_rpCollisionWorldRemoveOffset"));

    origin = RpWorldGetOrigin(world);
    if ((origin->x != 0.0f) || (origin->y != 0.0f) || (origin->z != 0.0f))
    {
        /* We must translate all collision trees */
        RwV3dNegate(&tr, origin);
        RpWorldForAllWorldSectors(world, CollisionWorldSectorTranslate, &tr);
    }

    RWRETURN(TRUE);
}


/*
 * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 *
 *      API INTERFACE
 *
 * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 */

/******************************************************************************
 *
 *  RpWorldForAllWorldSectorIntersections:-
 *
 *  First, a wrapper function to map internal callbacks to type
 *  RpIntersectionCallBack...
 */
static RpWorldSector *
WorldSectorIntersectionCallBack(RpWorldSector * worldSector, void *data)
{
    CallBackParam      *cbParam = (CallBackParam *) data;

    RWFUNCTION(RWSTRING("WorldSectorIntersectionCallBack"));
    RWASSERT(worldSector);
    RWASSERT(data);

    /* Pass to external callback */
    RWRETURN(cbParam->u.
             sectorCB(cbParam->intersection, worldSector,
                      cbParam->data));
}

/**
 * \ingroup rpcollis
 * \ref RpWorldForAllWorldSectorIntersections is used to test for
 * intersections of the given primitive with all world sectors in the
 * specified world based on their bounding boxes. For each intersection found
 * the given callback function (of type \ref RpIntersectionCallBackWorldSector)
 * is executed. The callback may return NULL to terminate intersection testing.
 *
 * The world plugin must be attached before using this function.
 * The header file rpcollis.h and rpcollis library are required.
 *
 * \param world  Pointer to the world.
 * \param intersection  Pointer to an \ref RpIntersection value describing
 *        the intersection primitive. Supported intersection types are:
 *
 * \li rpINTERSECTPOINT        Point intersections.
 * \li rpINTERSECTLINE         Line intersections.
 * \li rpINTERSECTSPHERE       Sphere intersections.
 * \li rpINTERSECTBOX          Box intersections.
 * \li rpINTERSECTATOMIC       Atomic intersections based on bounding sphere.
 *
 * \param callBack  Pointer to the callback function.
 * \param data  Pointer to user supplied data to pass to the callback function.
 *
 * \return Returns NULL if there is an error, or otherwise a pointer to the
 * world, even if no intersections were found.
 *
 * \see RpWorldForAllAtomicIntersections
 * \see RpAtomicForAllIntersections
 * \see RpCollisionWorldForAllIntersections
 * \see RpCollisionGeometryForAllIntersections
 * \see RpWorldPluginAttach
 *
 */
RpWorld            *
RpWorldForAllWorldSectorIntersections(RpWorld * world,
                                      RpIntersection * intersection,
                                      RpIntersectionCallBackWorldSector
                                      callBack, void *data)
{
    CallBackParam       cbParam;

    RWAPIFUNCTION(RWSTRING("RpWorldForAllWorldSectorIntersections"));
    RWASSERT(world);
    RWASSERT(intersection);
    RWASSERT(callBack);

    cbParam.intersection = intersection;
    cbParam.u.sectorCB = callBack;
    cbParam.data = data;

    switch (intersection->type)
    {
        case (rpINTERSECTPOINT):
            {
                RwBBox              box;

                /* Use degenerate box to represent point */
                box.inf = intersection->t.point;
                box.sup = intersection->t.point;

                /* Intersect point with sectors in the world */
                WorldForAllBoxWorldSectorIntersections(world, &box,
                                                       WorldSectorIntersectionCallBack,
                                                       &cbParam);

                RWRETURN(world);
            }
        case (rpINTERSECTLINE):
            {
                RwLine             *line = &intersection->t.line;
                RpV3dGradient       grad;
                RwV3d               delta;

                /* Calculate line gradient for fast clipping */
                RwV3dSub(&delta, &line->end, &line->start);
                _rpV3dGradientMacro(&grad, &delta);

                /* Intersect line with sectors in the world */
                WorldForAllLineWorldSectorIntersections(world, line,
                                                        &grad,
                                                        WorldSectorIntersectionCallBack,
                                                        &cbParam, NULL);

                RWRETURN(world);
            }
        case (rpINTERSECTSPHERE):
            {
                /* Intersect sphere with sectors in the world */
                WorldForAllSphereWorldSectorIntersections(world,
                                                          &intersection->
                                                          t.sphere,
                                                          WorldSectorIntersectionCallBack,
                                                          &cbParam);

                RWRETURN(world);
            }
        case (rpINTERSECTBOX):
            {
                /* Intersect box with sectors in the world */
                WorldForAllBoxWorldSectorIntersections(world,
                                                       &intersection->t.
                                                       box,
                                                       WorldSectorIntersectionCallBack,
                                                       &cbParam);

                RWRETURN(world);
            }
        case (rpINTERSECTATOMIC):
            {
                RpAtomic           *atomic =
                    (RpAtomic *) intersection->t.object;

                RWASSERT(atomic);
                RWASSERTISTYPE(atomic, rpATOMIC);

                /* Intersect atomic with sectors in the world */
                RpAtomicForAllWorldSectors(atomic,
                                           WorldSectorIntersectionCallBack,
                                           &cbParam);

                RWRETURN(world);
            }
        default:
            {
                /* Unknown or unsupported primitive type */
                RWERROR((E_RP_COLLIS_INV_INTERSECTION));
                RWRETURN(NULL);
            }
    }
}

/**
 * \ingroup rpcollis
 * \ref RpCollisionWorldForAllIntersections is used to test for
 * intersections of the given primitive with all triangles in the static
 * geometry of the specified world.
 *
 * For each intersection found the given callback function is executed,
 * which may return NULL to terminate intersection testing. See
 * \ref RpIntersectionCallBackWorldTriangle for full details of the information
 * passed to the callback.
 *
 * The world and collision plugins must be attached before using this
 * function. The header file rpcollis.h is required along with the
 * rpcollis and rtintsec libraries.
 *
 * Note that collision data must exist for the world. This would normally
 * be generated by an exporter or through a direct call to
 * \ref RpCollisionWorldBuildData in an offline tool. The intersection test
 * uses the world BSP structure and the additional collision data to quickly
 * isolate triangles that potentially intersect the primitive before
 * individually testing them.
 *
 * \param world  Pointer to the world.
 * \param intersection  Pointer to an \ref RpIntersection value describing
 *        the intersection primitive. Supported intersection types are:
 *
 * \li rpINTERSECTLINE         Line intersections.
 * \li rpINTERSECTSPHERE       Sphere intersections.
 * \li rpINTERSECTBOX          Box intersections.
 * \li rpINTERSECTATOMIC       Atomic intersections. Only the
 *     atomic’s world-space bounding sphere is tested against triangles
 *     in the world. Determination of fine-grained intersections between
 *     the atomic’s triangles and the world is not performed.
 *
 * \param callBack  Pointer to the callback function.
 * \param data  Pointer to user supplied data to pass to the callback function.
 *
 * \return Returns NULL if there is an error, or otherwise a pointer to the
 * world, even if no intersections were found.
 *
 * \see RpWorldForAllWorldSectorIntersections
 * \see RpWorldForAllAtomicIntersections
 * \see RpAtomicForAllIntersections
 * \see RpCollisionGeometryForAllIntersections
 * \see RpCollisionWorldBuildData
 * \see RpCollisionPluginAttach
 * \see RpWorldPluginAttach
 */
RpWorld            *
RpCollisionWorldForAllIntersections(RpWorld * world,
                                    RpIntersection * intersection,
                                    RpIntersectionCallBackWorldTriangle
                                    callBack, void *data)
{
    CallBackParam       cbParam;

    RWAPIFUNCTION(RWSTRING("RpCollisionWorldForAllIntersections"));
    RWASSERT(world);
    RWASSERT(intersection);
    RWASSERT(callBack);
    RWASSERT(_rpCollisionNumInstances);

    /* Store callback data */
    cbParam.intersection = intersection;
    cbParam.u.worldCB = callBack;
    cbParam.data = data;

    switch (intersection->type)
    {
        case (rpINTERSECTPOINT):
            {
                /* Invalid type */
                RWERROR((E_RP_COLLIS_INV_INTERSECTION));
                RWRETURN(NULL);
            }
        case (rpINTERSECTLINE):
            {
                PolyLineTestParam   isData;
                RwLine             *line = &intersection->t.line;

                /* Get data for polygon testing */
                isData.start = &intersection->t.line.start;
                RwV3dSub(&isData.delta, &line->end, &line->start);
                isData.cbParam = &cbParam;

                /* Get gradient for fast line clipping */
                _rpV3dGradientMacro(&isData.grad, &isData.delta);

                /* Intersect line with static polygons in the world */
                WorldForAllLineWorldSectorIntersections(world, line,
                                                        &isData.grad,
                                                        WorldSectorForAllLinePolyIntersections,
                                                        &isData,
                                                        &isData.
                                                        clippedLine);

                RWRETURN(world);
            }
        case (rpINTERSECTSPHERE):
            {
                PolyTestParam       isData;
                TestSphere          testSphere;

                /* Get the bounding box */
                _rpSphereBBoxMacro(&isData.bbox,
                                   &intersection->t.sphere);

                /* Set up data for polygon testing */
                testSphere.sphere = &intersection->t.sphere;
                testSphere.recipRadius =
                    1.0f / testSphere.sphere->radius;
                isData.leafTest = LeafNodeForAllSpherePolyIntersections;
                isData.v303leafTest =
                    OldLeafNodeForAllSpherePolyIntersections;
                isData.leafTestData = (void *) &testSphere;
                isData.cbParam = &cbParam;

                /* Intersect sphere with static polygons in the world */
                WorldForAllBoxWorldSectorIntersections(world,
                                                       &isData.bbox,
                                                       WorldSectorForAllBoxedPrimitivePolyIntersections,
                                                       &isData);

                RWRETURN(world);
            }
        case (rpINTERSECTBOX):
            {
                PolyTestParam       isData;

                /* Get bounding box */
                isData.bbox = intersection->t.box;

                /* Set up the polygon test */
                isData.leafTest = LeafNodeForAllBoxPolyIntersections;
                isData.v303leafTest =
                    OldLeafNodeForAllBoxPolyIntersections;
                isData.cbParam = &cbParam;

                /* Intersect box with static polygons in the world */
                WorldForAllBoxWorldSectorIntersections(world,
                                                       &isData.bbox,
                                                       WorldSectorForAllBoxedPrimitivePolyIntersections,
                                                       &isData);

                RWRETURN(world);
            }
        case (rpINTERSECTATOMIC):
            {
                PolyTestParam       isData;
                TestSphere          testSphere;
                RwSphere            sphere;
                RpAtomic           *atomic =
                    (RpAtomic *) intersection->t.object;

                RWASSERT(atomic);
                RWASSERTISTYPE(atomic, rpATOMIC);

                /* Get the bounding sphere */
                sphere = *RpAtomicGetWorldBoundingSphere(atomic);
                testSphere.sphere = &sphere;
                testSphere.recipRadius = 1.0f / sphere.radius;

                /* Get the bounding box */
                _rpSphereBBoxMacro(&isData.bbox, &sphere);

                /* Set up data for polygon test */
                isData.leafTest = LeafNodeForAllSpherePolyIntersections;
                isData.v303leafTest =
                    OldLeafNodeForAllSpherePolyIntersections;
                isData.leafTestData = (void *) &testSphere;
                isData.cbParam = &cbParam;

                /* Intersect atomic bounding sphere with static world geometry */
                RpAtomicForAllWorldSectors(atomic,
                                           WorldSectorForAllBoxedPrimitivePolyIntersections,
                                           &isData);

                RWRETURN(world);
            }
        default:
            {
                /* Unknown or unsupported primitive type */
                RWERROR((E_RP_COLLIS_INV_INTERSECTION));
                RWRETURN(NULL);
            }
    }
}

/**
 * \ingroup rpcollis
 * \ref RpWorldForAllAtomicIntersections is used to test for
 * intersections of the given primitive with atomics in the specified
 * world based on their bounding spheres.
 *
 * Only collision atomics (which have their rpATOMICCOLLISIONTEST flag set) are
 * tested (see \ref RpAtomicFlag). Also, since this function relies on the
 * internal ties between world sectors and atomics, the results may be invalid
 * if any atomics have been relocated since the last synchronization phase
 * (which occurs during an \ref RwCameraBeginUpdate).
 *
 * For each atomic intersection found the given callback function is executed,
 * which may return null to terminate intersection testing. See
 * \ref RpIntersectionCallBackAtomic for full details of the information passed
 * to the callback.
 *
 * For a more precise intersection test with the triangles of an atomic's
 * geometry, use \ref RpAtomicForAllIntersections or
 * \ref RpCollisionGeometryForAllIntersections.
 *
 * The world and collision plugins must be attached before using this
 * function. The header file rpcollis.h is required.
 *
 * \param world  Pointer to the world containing atomics.
 * \param intersection  Pointer to an \ref RpIntersection value describing the
 *        intersection primitive. Supported intersection types are:
 *
 * \li rpINTERSECTPOINT    Point intersections.
 * \li rpINTERSECTLINE     Line intersections.
 * \li rpINTERSECTSPHERE   Sphere intersections.
 * \li rpINTERSECTATOMIC   Atomic intersections based on bounding sphere.
 * \li rpINTERSECTBOX      Box intersections.
 *
 * \param callBack  Pointer to the callback function.
 * \param data  Pointer to user supplied data to pass to the call back function.
 *
 * \return Returns NULL if there is an error, or otherwise a pointer to
 * the world, even if no intersections are found.
 *
 * \see RpWorldForAllWorldSectorIntersections
 * \see RpCollisionWorldForAllIntersections
 * \see RpAtomicForAllIntersections
 * \see RpCollisionGeometryForAllIntersections
 * \see RpCollisionPluginAttach
 * \see RpAtomicSetFlags
 * \see RpWorldPluginAttach
 */
RpWorld            *
RpWorldForAllAtomicIntersections(RpWorld * world,
                                 RpIntersection * intersection,
                                 RpIntersectionCallBackAtomic callBack,
                                 void *data)
{
    AtomicTestParam     testParam;

    RWAPIFUNCTION(RWSTRING("RpWorldForAllAtomicIntersections"));
    RWASSERT(world);
    RWASSERT(intersection);
    RWASSERT(callBack);
    RWASSERT(_rpCollisionNumInstances);

    testParam.cbParam.intersection = intersection;
    testParam.cbParam.u.atomicCB = callBack;
    testParam.cbParam.data = data;
    testParam.testAtomic = NULL; /* Only defined for type rpINTERSECTATOMIC */

    /* Increment the collision reference ID which is used to tag atomics
     * so that they are only tested once.
     */
    RPCOLLISIONGLOBAL(collisionRef)++;

    switch (intersection->type)
    {
        case (rpINTERSECTPOINT):
            {
                RwBBox              box;
                RwSphere            sphere;

                /* Use degenerate box to test against world sectors */
                box.inf = intersection->t.point;
                box.sup = intersection->t.point;

                /* Use degenerate sphere to test against atomics */
                sphere.center = intersection->t.point;
                sphere.radius = 0.0f;
                testParam.atomicCallBack = AtomicSphereTest;
                testParam.testData = (void *) &sphere;

                /* Intersect point with atomics (bounding spheres) in the world */
                WorldForAllBoxWorldSectorIntersections(world, &box,
                                                       WorldSectorForAllPrimitiveAtomicIntersections,
                                                       &testParam);

                RWRETURN(world);
            }
        case (rpINTERSECTLINE):
            {
                RwLine             *line = &intersection->t.line;
                RpV3dGradient       grad;
                TestLine            testLine;
                RwReal              lengthSq;
                RwV3d               delta;

                /* Calculate line gradient for fast clipping to BSP */
                RwV3dSub(&delta, &line->end, &line->start);
                _rpV3dGradientMacro(&grad, &delta);

                /* Set up atomic test parameters */
                testLine.line = line;
                lengthSq = RwV3dDotProduct(&delta, &delta);
                rwSqrtInvSqrtMacro(testLine.length,
                                   testLine.recipLength, lengthSq);
                RwV3dScale(&testLine.dir, &delta, testLine.recipLength);
                testParam.atomicCallBack = AtomicLineTest;
                testParam.testData = (void *) &testLine;

                /* Intersect line with atomics (bounding spheres) in the world */
                WorldForAllLineWorldSectorIntersections(world, line,
                                                        &grad,
                                                        WorldSectorForAllPrimitiveAtomicIntersections,
                                                        &testParam,
                                                        NULL);

                RWRETURN(world);
            }
        case (rpINTERSECTSPHERE):
            {
                /* Set up atomic test parameters */
                testParam.atomicCallBack = AtomicSphereTest;
                testParam.testData = (void *) &intersection->t.sphere;

                /* Intersect sphere with atomics (bounding spheres) in the world */
                WorldForAllSphereWorldSectorIntersections(world,
                                                          &intersection->
                                                          t.sphere,
                                                          WorldSectorForAllPrimitiveAtomicIntersections,
                                                          &testParam);

                RWRETURN(world);
            }
        case (rpINTERSECTBOX):
            {
                /* Set up atomic test parameters */
                testParam.atomicCallBack = AtomicBoxTest;
                testParam.testData = (void *) &intersection->t.box;

                /* Intersect box with atomics (bounding spheres) in the world */
                WorldForAllBoxWorldSectorIntersections(world,
                                                       &intersection->t.
                                                       box,
                                                       WorldSectorForAllPrimitiveAtomicIntersections,
                                                       &testParam);

                RWRETURN(world);
            }
        case (rpINTERSECTATOMIC):
            {
                RwSphere            sphere;
                RpAtomic           *atomic =
                    (RpAtomic *) intersection->t.object;

                RWASSERT(atomic);
                RWASSERTISTYPE(atomic, rpATOMIC);

                /* Set up atomic test parameters */
                sphere = *RpAtomicGetWorldBoundingSphere(atomic);
                testParam.atomicCallBack = AtomicSphereTest;
                testParam.testData = (void *) &sphere;

                /* Store test atomic so we can eliminate collision with itself */
                testParam.testAtomic = atomic;

                /* Get intersections */
                RpAtomicForAllWorldSectors(atomic,
                                           WorldSectorForAllPrimitiveAtomicIntersections,
                                           &testParam);

                RWRETURN(world);
            }
        default:
            {
                /* Unknown or unsupported primitive type */
                RWERROR((E_RP_COLLIS_INV_INTERSECTION));
                RWRETURN(NULL);
            }
    }
}

/**
 * \ingroup rpcollis
 * \ref RpCollisionWorldSectorBuildData is called to generate
 * collision data for a world sector. Alternatively, collision data can be
 * generated for all world sectors in a world with a single call to
 * \ref RpCollisionWorldBuildData. Both these functions are intended for offline
 * use in custom exporters and tools. The collision data can otherwise
 * be generated by the standard RenderWare exporters.
 *
 * Collision data allows fast intersection tests with the triangles
 * of a world's static geometry. See \ref RpCollisionWorldForAllIntersections.
 *
 * The collision and world plug-ins must be attached before using this
 * function. The header file rpcollis.h is required.
 *
 * \param worldSector   Pointer to the world sector
 * \param param   Pointer to the build parameters. This should be set to NULL as
 *        no user parameters are currently supported. A NULL setting will
 *        cause default parameters to be used in future versions.
 *
 * \return Pointer to the world sector if successful, NULL otherwise.
 *
 * \see RpCollisionPluginAttach
 * \see RpCollisionWorldBuildData
 * \see RpCollisionWorldForAllIntersections
 * \see RpCollisionGeometryBuildData
 */
RpWorldSector      *
RpCollisionWorldSectorBuildData(RpWorldSector * worldSector,
                                RpCollisionBuildParam *
                                __RWUNUSED__ param)
{
    RpCollisionData   **extData;

    RWAPIFUNCTION(RWSTRING("RpCollisionWorldSectorBuildData"));
    RWASSERT(worldSector);
    RWASSERT(_rpCollisionNumInstances);

    extData = RPWORLDSECTORCOLLISIONDATA(worldSector);

    /* Destroy any previous collision data */
    if (*extData)
    {
        _rpCollisionDataDestroy(*extData);
    }

    /* Check that sector actually contains something */
    if (worldSector->numPolygons && worldSector->polygons)
    {
        RpCollisionData    *collData;
        RpCollBSPTriangle  *tris;
        RwInt32             memSize;

        /* Create temporary array for BSP triangles */
        memSize = worldSector->numPolygons * sizeof(RpCollBSPTriangle);
        tris = (RpCollBSPTriangle *) RwMalloc(memSize);
        if (!tris)
        {
            RWERROR((E_RW_NOMEM, memSize));
            RWRETURN(NULL);
        }

        /* Copy sector polygons over to BSP triangle format */
        {
            RwInt32             nPoly = worldSector->numPolygons;
            RpPolygon          *poly = worldSector->polygons;
            RpCollBSPTriangle  *tri = tris;

            while (nPoly--)
            {
                tri->vertIndex[0] = poly->vertIndex[0];
                tri->vertIndex[1] = poly->vertIndex[1];
                tri->vertIndex[2] = poly->vertIndex[2];
                tri++;
                poly++;
            }
        }

        /* Now do generic build of data */
        collData =
            _rpCollisionDataBuild(worldSector->numVertices,
                                  worldSector->vertices,
                                  worldSector->numPolygons, tris);

        /* Free temporary triangle array */
        RwFree(tris);

        /* Was collision data created successfully? */
        if (!collData)
        {
            RWRETURN(NULL);
        }

        /* Attach to world sector via extension data */
        *extData = collData;
    }

    RWRETURN(worldSector);
}

/**
 * \ingroup rpcollis
 * \ref RpCollisionWorldSectorDestroyData is called to destroy
 * collision data for a world sector.
 *
 * The collision and world plug-ins must be attached before using this
 * function. The header file rpcollis.h is required.
 *
 * \param worldSector   Pointer to the world sector
 *
 * \return Pointer to the world sector if successful, NULL otherwise.
 *
 * \see RpCollisionPluginAttach
 * \see RpCollisionWorldBuildData
 * \see RpCollisionWorldDestroyData
 * \see RpCollisionWorldSectorBuildData
 *
 */
RpWorldSector      *
RpCollisionWorldSectorDestroyData(RpWorldSector * worldSector)
{
    RpCollisionData   **extData;

    RWAPIFUNCTION(RWSTRING("RpCollisionWorldSectorDestroyData"));
    RWASSERT(worldSector);

    extData = RPWORLDSECTORCOLLISIONDATA(worldSector);

    /* Destroy any collision data */
    if (*extData)
    {
        _rpCollisionDataDestroy(*extData);
    }

    *extData = NULL;

    RWRETURN(worldSector);
}

/**
 * \ingroup rpcollis
 * \ref RpCollisionWorldSectorQueryData is called to query if
 * collision data exist for the given world sector.
 *
 * The collision and world plug-ins must be attached before using this
 * function. The header file rpcollis.h is required.
 *
 * \param worldSector   Pointer to the world sector
 *
 * \return TRUE if collision are present, FALSE otherwise.
 *
 * \see RpCollisionPluginAttach
 * \see RpCollisionWorldBuildData
 * \see RpCollisionWorldQueryData
 * \see RpCollisionWorldSectorBuildData
 *
 */
RwBool
RpCollisionWorldSectorQueryData(RpWorldSector * worldSector)
{
    RwBool              result;
    RpCollisionData   **extData;

    RWAPIFUNCTION(RWSTRING("RpCollisionWorldSectorQueryData"));
    RWASSERT(worldSector);

    extData = RPWORLDSECTORCOLLISIONDATA(worldSector);
    result = FALSE;

    /* Any collision data ? */
    if (*extData)
    {
        result = TRUE;
    }
    else
    {
        /* Old collision data ? */
        if (worldSector->colSectorRoot)
            result = TRUE;
    }

    RWRETURN(result);
}

/******************************************************************************
 *
 *  RpCollisionWorldBuildData:-
 *
 *  worldsector callback and callback data.
 */
typedef struct buildCallBackData buildCallBackData;
struct buildCallBackData
{
    RpCollisionBuildParam *param;
    RwBool              error;
};

static RpWorldSector *
WorldSectorBuildDataCallBack(RpWorldSector * worldSector, void *data)
{
    buildCallBackData  *buildData = (buildCallBackData *) data;

    RWFUNCTION(RWSTRING("WorldSectorBuildDataCallBack"));
    RWASSERT(worldSector);
    RWASSERT(buildData);

    /* Skip empty sectors */
    if (worldSector->numPolygons)
    {
        if (!RpCollisionWorldSectorBuildData
            (worldSector, buildData->param))
        {
            /* Failed to build collision tree */
            buildData->error = TRUE;
            RWRETURN(NULL);
        }
    }

    RWRETURN(worldSector);
}

static RpWorldSector *
WorldSectorDestroyDataCallBack(RpWorldSector * worldSector, 
                               void * __RWUNUSED__ data)
{
    RWFUNCTION(RWSTRING("WorldSectorDestroyDataCallBack"));
    RWASSERT(worldSector);

    /* Skip empty sectors */
    if (worldSector->numPolygons)
    {
        RpCollisionWorldSectorDestroyData(worldSector);
    }

    RWRETURN(worldSector);
}

static RpWorldSector *
WorldSectorQueryDataCallBack(RpWorldSector * worldSector, void *data)
{
    RwBool    *result = (RwBool *) data;

    RWFUNCTION(RWSTRING("WorldSectorQueryDataCallBack"));
    RWASSERT(worldSector);

    /* Skip empty sectors */
    if (worldSector->numPolygons)
    {
        *result |= RpCollisionWorldSectorQueryData(worldSector);
    }

    RWRETURN(worldSector);
}

/**
 * \ingroup rpcollis
 * \ref RpCollisionWorldBuildData is called to generate
 * collision data for all world sectors in the given world, and is intended
 * for use in custom exporters and tools. The collision data can otherwise
 * be generated by the standard RenderWare exporters.
 *
 * The collision data allows fast intersection tests with the triangles
 * of a world's static geometry. See \ref RpCollisionWorldForAllIntersections.
 *
 * The collision and world plug-ins must be attached before using this
 * function. The header file rpcollis.h is required.
 *
 * \param world   Pointer to the world
 * \param param   Pointer to the build parameters. This should be set to NULL as
 *        no user parameters are currently supported. A NULL setting will
 *        cause default parameters to be used in future versions.
 *
 * \return Pointer to the world if successful, NULL otherwise.
 *
 * \see RpCollisionPluginAttach
 * \see RpCollisionWorldSectorBuildData
 * \see RpCollisionWorldForAllIntersections
 * \see RpCollisionGeometryBuildData
 */
RpWorld            *
RpCollisionWorldBuildData(RpWorld * world,
                          RpCollisionBuildParam * param)
{
    buildCallBackData   buildData;

    RWAPIFUNCTION(RWSTRING("RpCollisionWorldBuildData"));
    RWASSERT(world);
    /* Note: param may be NULL */
    RWASSERT(_rpCollisionNumInstances);

    buildData.param = param;
    buildData.error = FALSE;

    /* Build collision tree for all sectors */
    RpWorldForAllWorldSectors(world,
                              WorldSectorBuildDataCallBack, &buildData);

    /* Check for any errors */
    if (buildData.error)
    {
        RWRETURN(NULL);
    }

    RWRETURN(world);
}

/**
 * \ingroup rpcollis
 * \ref RpCollisionWorldDestroyData is called to destroy the attached
 * collision data for the given world.
 *
 * The collision and world plug-ins must be attached before using this
 * function. The header file rpcollis.h is required.
 *
 * \param world   Pointer to the world
 *
 * \return Pointer to the world if successful, NULL otherwise.
 *
 * \see RpCollisionPluginAttach
 * \see RpCollisionWorldBuildData
 * \see RpCollisionWorldSectorBuildData
 * \see RpCollisionWorldSectorDestroyData
 */

RpWorld *
RpCollisionWorldDestroyData(RpWorld *world)
{
    RWAPIFUNCTION(RWSTRING("RpCollisionWorldDestroyData"));

    RWASSERT(world);

    /* Destroy collision tree for all sectors */
    RpWorldForAllWorldSectors(world,
                              WorldSectorDestroyDataCallBack, NULL);

    RWRETURN(world);
}

/**
 * \ingroup rpcollis
 * \ref RpCollisionWorldQueryData is called to query for collision data for
 * the given world.
 *
 * The result is TRUE if any world sectors contains collision data. FALSE if
 * no world sectors contains collision data.
 *
 * The collision and world plug-ins must be attached before using this
 * function. The header file rpcollis.h is required.
 *
 * \param world   Pointer to the world
 *
 * \return TRUE if collision data are present. FALSE otherwise.
 *
 * \see RpCollisionPluginAttach
 * \see RpCollisionWorldBuildData
 * \see RpCollisionWorldSectorBuildData
 * \see RpCollisionWorldSectorQueryData
 */

RwBool
RpCollisionWorldQueryData(RpWorld *world)
{
    RwBool        result;

    RWAPIFUNCTION(RWSTRING("RpCollisionWorldQueryData"));

    RWASSERT(world);

    /* Assume no data. */
    result = FALSE;

    /* Query the collision tree for all sectors */
    RpWorldForAllWorldSectors(world,
                              WorldSectorQueryDataCallBack, &result);

    RWRETURN(result);
}

