/*
 * Potentially Visible Set plug-in
 */

/**********************************************************************
 *
 * File :     rppvsgen.c
 *
 * Abstract : Handle culling of WSector in RenderWare
 *
 **********************************************************************
 *
 * This file is a product of Criterion Software Ltd.
 *
 * This file is provided as is with no warranties of any kind and is
 * provided without any obligation on Criterion Software Ltd. or
 * Canon Inc. to assist in its use or modification.
 *
 * Criterion Software Ltd. will not, under any
 * circumstances, be liable for any lost revenue or other damages arising
 * from the use of this file.
 *
 * Copyright (c) 1998 Criterion Software Ltd.
 * All Rights Reserved.
 *
 * RenderWare is a trademark of Canon Inc.
 *
 ************************************************************************/

/*--- Include files ---*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <math.h>

#include "rpplugin.h"

#include <rwcore.h>
#include <rtworld.h>
#include <rtray.h>
#include <rpcollis.h>

#include <rpdbgerr.h>
#include <rppvs310.h>

#include "rppvsgen.h"
#include "rppvsdef.h"

#include  "nodePVSWorldSector.h"

#if (!defined(DOXYGEN_SHOULD_SKIP_THIS))
static const char   rcsid[] __RWUNUSED__ =
    "@@(#)$Id: rppvsgen.c,v 1.61 2001/10/05 08:45:47 adamj Exp $";
#endif /* (!defined(DOXYGEN_SHOULD_SKIP_THIS)) */

#ifndef NO_PVS_CREATE

/****************************************************************************
 External functions
 */

/****************************************************************************
 Local (static) Globals
 */

/****************************************************************************
 Local Defines
 */

/* for debugging define these to something useful */

#define PvsMarkersInit(MAXID)
#define PvsLineAdd(ID, P1, P2, R,G,B)
#define PvsMarkerAdd(ID,P,R,G,B)
#define PvsBBoxAdd(ID,BBox,R,G,B)

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

#ifdef SKY
#define __RWUNUSEDUNLESSSKY__  /* No op */
static RwUInt8     *oldCamPixels;
#endif /*  SKY */

#if (!defined(__RWUNUSEDUNLESSSKY__))
#define __RWUNUSEDUNLESSSKY__ __RWUNUSED__
#endif /* (!defined(__RWUNUSEDUNLESSSKY__)) */

static void
raslock(RwImage * img, RwRaster * ras)
{
    RWFUNCTION(RWSTRING("raslock"));
    RWASSERT(ras);

#ifdef SKY
    /* If we are on PS2, we must give the Camera a data area */
    /* Ordinarily, PS2 camera rasters have no in memory image */
    /* Under normal conditions it is impossible to lock the camera */
    /* raster on PS2 as its a real performance problem. However, */
    /* by setting the cpPixel pointer the driver will assume that */
    /* you know what you are doing and are willing to take the hit */

    /* We know that malloc aligns on qw */
    oldCamPixels = ras->cpPixels;
    ras->cpPixels = RwImageGetPixels(img);

    /* Lock the camera raster for read. This will do what ever is */
    /* required to get the data into memory */

    /* The PS2 driver doesn't do this for you */
    if (!RwRasterLock(ras, 0, rwRASTERLOCKREAD))
    {
        ras->cpPixels = oldCamPixels;
    }
#else
    RwImageSetFromRaster(img, ras);
#endif

    RWRETURNVOID();
}

static void
rasunlock(RwRaster * ras __RWUNUSEDUNLESSSKY__)
{
    RWFUNCTION(RWSTRING("rasunlock"));

#ifdef SKY
    RwRasterUnlock(ras);
    ras->cpPixels = oldCamPixels;
#endif
    RWRETURNVOID();
}

#if (defined(_WINDOWS))
#define RWCDECL__cdecl
#endif /* (defined(_WINDOWS)) */

#if (!defined(RWCDECL))
#define RWCDECL                /* No op */
#endif /* (!defined(RWCDECL)) */

/**********************************************************************/
static RpWorldSector *
PVSRenderImmediate(RpWorldSector * spSector, void *__RWUNUSED__ data)
{
    const RpWorld      *world;
    RpPolygon          *rwPoly;
    RwV3d              *rwVert;
    RwRGBA              rwCol;
    RwInt32             numVert, numPoly;
    RpPVS              *ppCur;
    const RpPVSCache   *pvsCache;
    RwIm3DVertex       *im3DVert;
    RwImVertexIndex    *imVertIndex;
    RwInt32             i, j;

    RWFUNCTION(RWSTRING("PVSRenderImmediate"));

    world = rpPVSGlobals.world;

    RWASSERT(spSector);
    RWASSERT(world);

    numVert = RpWorldSectorGetNumVertices(spSector);
    numPoly = RpWorldSectorGetNumPolygons(spSector);

    if (numVert > 0)
    {
        /*
         * Encode the sector ID from from a 32 bit to 5x5x5,
         * The 5bit number occupies the most sig bits in the 8bit store.
         */
        ppCur = PVSFROMWORLDSECTOR(spSector);
        pvsCache = PVSCACHEFROMCONSTWORLD(world);

        im3DVert = pvsCache->im3DVert;
        imVertIndex = pvsCache->imVertIndex;

        PVSENCODEID(&rwCol, ppCur->sectorID);

        /* Get the world sector's verts and polys. */
        rwVert = spSector->vertices;
        rwPoly = spSector->polygons;

        /* Assign the pos and colour. */

        RWASSERT(numVert <= pvsCache->maxNumVert);

        for (i = 0; i < numVert; i++)
        {
            RwIm3DVertexSetPos(&im3DVert[i], rwVert[i].x, rwVert[i].y,
                               rwVert[i].z);
            RwIm3DVertexSetRGBA(&im3DVert[i], rwCol.red, rwCol.green,
                                rwCol.blue, rwCol.alpha);
        }

        /* Assign the vertex index, checking for translucency. */
        j = 0;
        for (i = 0; i < numPoly; i++)
        {
            RpMaterial         *mat;
            const RwRGBA       *color;
            RwTexture          *tex;
            RwInt32             matid;

            matid = spSector->matListWindowBase + rwPoly[i].matIndex;
            mat = rpMaterialListGetMaterial(&world->matList, matid);
            color = RpMaterialGetColor(mat);
            tex = RpMaterialGetTexture(mat);

            if (color->alpha < 255 || (tex && tex->mask[0]))
            {
                /* not a reliable occluder, so ignore */
            }
            else
            {
                imVertIndex[j] =
                    (RwImVertexIndex) rwPoly[i].vertIndex[0];
                j++;

                imVertIndex[j] =
                    (RwImVertexIndex) rwPoly[i].vertIndex[1];
                j++;

                imVertIndex[j] =
                    (RwImVertexIndex) rwPoly[i].vertIndex[2];
                j++;
            }
        }

        /* Do we have anything to render ? */
        if (j > 0)
        {
            if (RwIm3DTransform(im3DVert, numVert,
                                (RwMatrix *)NULL, 0))
            {
                RwIm3DRenderIndexedPrimitive(rwPRIMTYPETRILIST,
                                             imVertIndex, j);
                RwIm3DEnd();
            }
        }
    }

    RWRETURN(spSector);
}

/****************************************************************************/
static void
PVSRenderVisMap(RpPVSCache * pvsCache)
{
    RwUInt32            x, y, stride, id;
    RwRGBA              bkcol;

#ifdef PVS_DEBUG
    RwBool              dither = 0;
#endif /* PVS_DEBUG */

    RWFUNCTION(RWSTRING("PVSRenderVisMap"));

    RwFrameUpdateObjects(RwCameraGetFrame(rpPVSGlobals.camera));

    PVSENCODEID(&bkcol, pvsCache->nextID);
    RwCameraClear(rpPVSGlobals.camera, &bkcol,
                  rwCAMERACLEARIMAGE | rwCAMERACLEARZ);
    if (RwCameraBeginUpdate(rpPVSGlobals.camera))
    {
        /* Setup the rendering state for flat and Z-buffer. */
        RwRenderStateSet(rwRENDERSTATESHADEMODE,
                         (void *) rwSHADEMODEFLAT);
        RwRenderStateSet(rwRENDERSTATEZTESTENABLE, (void *) TRUE);
        RwRenderStateSet(rwRENDERSTATETEXTURERASTER, (void *) NULL);

        /* Render the world sector. */
        RwCameraForAllSectorsInFrustum(rpPVSGlobals.camera,
                                       PVSRenderImmediate, pvsCache);
        RwCameraEndUpdate(rpPVSGlobals.camera);
    }

    if (pvsCache->sectorVismap)
    {
        RwRGBA              col, *pix;

        /* Copy the raster into the image. */
        raslock(rpPVSGlobals.image,
                RwCameraGetRaster(rpPVSGlobals.camera));

        /* what sectors can we see? */
        pix = (RwRGBA *) RwImageGetPixels(rpPVSGlobals.image);
        stride = RwImageGetStride(rpPVSGlobals.image) >> 2;
        y = RwImageGetHeight(rpPVSGlobals.image);

        while (y--)
        {
            RwUInt32            lastid = 0xffffff;

            /* This processes line backwards, but that's OK */
            x = RwImageGetWidth(rpPVSGlobals.image);
            while (x--)
            {
                col = pix[x];

                /* Decode the sector ID from the colour quad. */
                PVSDECODEID(id, &col);

#ifdef PVS_DEBUG
                if ((col.red & 15) || (col.green & 15)
                    || (col.blue & 15))
                {
                    dither = TRUE;
                    pix[x].red = 255;
                    pix[x].green = 255;
                    pix[x].blue = 255;
                }
#endif /* PVS_DEBUG */

                if (id == lastid)
                {
                    /* The re-formed ID should not exceed the max ID. */
                    /* NB we clear to nextID so we allow it */
                    RWASSERT((id <= pvsCache->nextID));
                    if (id <= pvsCache->nextID)
                    {
                        PVSVISMAPSETSECTOR(pvsCache->sectorVismap, id);
                    }
                }

                /* must be >1 ID in a row to mark as visible (crap geometry) */
                lastid = id;
            }
            pix += stride;
        }

#ifdef PVS_DEBUG
        if (dither)
        {
            char                filename[80];
            RpPVS              *ppCur;

            ppCur = PVSFROMWORLDSECTOR(pvsCache->spCOP);
            sprintf(filename, "sector%d.bmp", ppCur->sectorID);
            RwImageWriteBMP(rpPVSGlobals.image, filename);
        }
#endif /* PVS_DEBUG */

        rasunlock(RwCameraGetRaster(rpPVSGlobals.camera));
    }

    RWRETURNVOID();
}

/*****************************************************************************/
static RpCollisionTriangle *
PVSSphereCollision(RpIntersection * __RWUNUSED__ is,
                   RpWorldSector * __RWUNUSED__ sector,
                   RpCollisionTriangle * __RWUNUSED__ collPlane,
                   RwReal __RWUNUSED__ distance, void *pData)
{
    RwBool             *hitcount = (RwBool *) pData;

    RWFUNCTION(RWSTRING("PVSSphereCollision"));

    *hitcount = TRUE;

    RWRETURN((RpCollisionTriangle *)NULL);
}

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

/*                                                                      */

/* Function:   TrianglePointNearestPoint                                */

/* Purpose:    given a point and a description of a triangle,           */

/*             return the point within the triangle that is closest to  */

/*             that point                                               */

/* On entry:   triangle's vertex array,                                 */

/*             triangle's normal,                                       */

/*             reference point                                          */

/* On exit:    return value is the distance from the                    */

/*             triangle to the supplied reference point,                */

/*             vpPt now holds the near point of the                     */

/*             triangle to the input point                              */

/*                                                                      */

/************************************************************************/
#define CONSTREALASINT(r)   ( ((const RwSplitBits *)&(r))->nInt )
#define REALSIGNSNEQ(a, b)  ( (CONSTREALASINT(a) ^ CONSTREALASINT(b)) < 0 )

#define TRIAREA(vpA, vpB, vpC, _X, _Y)                                   \
    ( (((vpB)->_X) - ((vpA)->_X)) * (((vpC)->_Y) - ((vpA)->_Y)) -        \
      (((vpB)->_Y) - ((vpA)->_Y)) * (((vpC)->_X) - ((vpA)->_X)) )

#define RWSNAPEDGE(_rResult, _A, _B, _X, _Y, _Z)                         \
MACRO_START                                                              \
{                                                                        \
    RwV3d               vEdge;                                           \
                                                                         \
    vEdge._X = vpaVertices[_B]->_X -  vpaVertices[_A]->_X;               \
    vEdge._Y = vpaVertices[_B]->_Y -  vpaVertices[_A]->_Y;               \
                                                                         \
    MACRO_START                                                          \
    {                                                                    \
        const RwReal        rSubtend =                                   \
            ( vEdge._X * ((vProj._Y) - (vpaVertices[_A]->_Y)) -          \
              vEdge._Y * ((vProj._X) - (vpaVertices[_A]->_X)) );         \
        const RwBool        outsideEdge =                                \
            REALSIGNSNEQ(rSubtend, rTriangle);                           \
                                                                         \
        if (outsideEdge)                                                 \
        {                                                                \
            RwReal              mu;                                      \
            RwV3d               vCandidate;                              \
                                                                         \
            vEdge._Z = vpaVertices[_B]->_Z -  vpaVertices[_A]->_Z;       \
                                                                         \
            mu = RwV3dDotProduct(&vProj, &vEdge) -                       \
                 RwV3dDotProduct(vpaVertices[_A], &vEdge);               \
                                                                         \
            if (mu <= 0)                                                 \
            {                                                            \
                vCandidate = *vpaVertices[_A];                           \
            }                                                            \
            else                                                         \
            {                                                            \
                RwReal       denom = RwV3dDotProduct(&vEdge, &vEdge);    \
                                                                         \
                bEdgeInternal = ((0 < denom) && (mu < denom));           \
                if (bEdgeInternal)                                       \
                {                                                        \
                    mu /= denom;                                         \
                    RwV3dScale(&vCandidate, &vEdge, mu);                 \
                    RwV3dAdd(&vCandidate, &vCandidate, vpaVertices[_A]); \
                }                                                        \
                else                                                     \
                {                                                        \
                    vCandidate = *vpaVertices[_B];                       \
                }                                                        \
            }                                                            \
                                                                         \
            RwV3dSub(&vEdge, &vPtAsPassed, &vCandidate);                 \
            rDist2 = RwV3dDotProduct(&vEdge, &vEdge);                    \
                                                                         \
            if ((!bSnapped) || ((_rResult) > rDist2))                    \
            {                                                            \
                *vpPt = vCandidate;                                      \
                (_rResult) = rDist2;                                     \
            }                                                            \
        }                                                                \
        bSnapped |= outsideEdge;                                         \
    }                                                                    \
    MACRO_STOP;                                                          \
}                                                                        \
MACRO_STOP

#define RWPLANEPROCESS(_result, _X, _Y, _Z)                              \
MACRO_START                                                              \
{                                                                        \
    RwBool              bEdgeInternal = 0;                               \
    RwReal              rTriangle = TRIAREA(vpaVertices[0],              \
                                            vpaVertices[1],              \
                                            vpaVertices[2],              \
                                            _X, _Y);                     \
                                                                         \
    RWSNAPEDGE(_result, 1, 2, _X, _Y, _Z);                               \
    if (!bEdgeInternal)                                                  \
    {                                                                    \
        RWSNAPEDGE(_result, 2, 0, _X, _Y, _Z);                           \
        if (!bEdgeInternal)                                              \
        {                                                                \
            RWSNAPEDGE(_result, 0, 1, _X, _Y, _Z);                       \
        }                                                                \
    }                                                                    \
}                                                                        \
MACRO_STOP

static              RwReal
TrianglePointNearestPoint(RwV3d * vpaVertices[3],
                          RwV3d * vpNormal, RwV3d * vpPt)
{
    RwReal              rResult = (RwReal) 0;
    RwV3d               vPtAsPassed;
    RwV3d               vProj;
    RwReal              rDistPt2Plane;
    RwBool              bSnapped = 0;
    RwReal              rDist2;

    /* work in 2-D plane of greatest projection */
    const RwInt32       nAbsX =
        CONSTREALASINT(vpNormal->x) & 0x7FFFFFFF;
    const RwInt32       nAbsY =
        CONSTREALASINT(vpNormal->y) & 0x7FFFFFFF;
    const RwInt32       nAbsZ =
        CONSTREALASINT(vpNormal->z) & 0x7FFFFFFF;

    RWFUNCTION(RWSTRING("TrianglePointNearestPoint"));

    vPtAsPassed = *vpPt;

    /* project point onto plane of triangle */
    /* (cost of using two dot products vs. V3dSub and one is 3 multiplies,
     * but loss of precision is minimized ) */
    rDistPt2Plane =
        RwV3dDotProduct(vpaVertices[0], vpNormal) -
        RwV3dDotProduct(vpPt, vpNormal);

    RwV3dScale(&vProj, vpNormal, rDistPt2Plane);
    RwV3dAdd(&vProj, &vProj, vpPt);

    if (nAbsZ > nAbsY)
    {
        if (nAbsZ > nAbsX)
        {
            RWPLANEPROCESS(rResult, x, y, z);
        }
        else
        {
            RWPLANEPROCESS(rResult, y, z, x);
        }
    }
    else
    {
        if (nAbsY > nAbsX)
        {
            RWPLANEPROCESS(rResult, z, x, y);
        }
        else
        {
            RWPLANEPROCESS(rResult, y, z, x);
        }
    }

    if (!bSnapped)
    {
        *vpPt = vProj;
        rDist2 = rDistPt2Plane * rDistPt2Plane;
        rResult = rDist2;
    }

    RWRETURN(rResult);
}

/****************************************************************************/
static RpCollisionTriangle *
colltest(RpIntersection * is,
         RpWorldSector * __RWUNUSED__ sector,
         RpCollisionTriangle * collPlane,
         RwReal __RWUNUSED__ distance, void *pData)
{
    GridCollTri        *colltri = (GridCollTri *) pData;
    RwReal              dist;
    RwV3d               pos;

    RWFUNCTION(RWSTRING("colltest"));

    /* find nearest point of polygon to collision sphere centre */
    pos = is->t.sphere.center;
    dist =
        TrianglePointNearestPoint(collPlane->vertices,
                                  &collPlane->normal, &pos);
    if (dist < colltri->dist)
    {
        RwReal              angle;
        RwV3d               toward;

        /* is it facing center? */
        RwV3dSub(&toward, collPlane->vertices[0], &is->t.sphere.center);
        RwV3dNormalize(&toward, &toward);
        angle = RwV3dDotProduct(&toward, &collPlane->normal);

        /* ignore oblique faces... */
        if (angle < -0.05f || angle > 0.05f)
        {
            colltri->facing = angle < 0.0f;

            /* bias against facing polygons (back facing should 'win') */
            if (colltri->facing)
            {
                dist *= 1.005f;
            }

            colltri->dist = dist;
        }
    }

    RWRETURN(collPlane);
}

static              RwBool
inouttest(RwV3d * pos, RwReal radius)
{
    RpIntersection      isSphere;
    GridCollTri         neartri;

    RWFUNCTION(RWSTRING("inouttest"));

    if (radius >  rpPVSGlobals.inout_tol)
    {
        RWRETURN(FALSE);
    }

    isSphere.type = rpINTERSECTSPHERE;
    isSphere.t.sphere.center = *pos;
    isSphere.t.sphere.radius = radius;
    neartri.dist = radius * radius;

    RpCollisionWorldForAllIntersections(rpPVSGlobals.world, &isSphere,
                                        colltest, &neartri);
    if (neartri.dist < radius * radius)
    {
        RWRETURN(neartri.facing);
    }
    else
    {
        /* enlarge the search */
        RWRETURN(inouttest(pos, radius * 2.0f));
    }
}

/****************************************************************************/
static void
PVScreatecam(RpWorld * world, RwRaster * raster, RwRaster * zraster,
             RwReal mindist, RwReal maxdist)
{
    RpPVSCache         *pvsCache;
    RwRect              subRect;
    RwRaster           *subRas, *subZRas;
    RwV2d               viewwin;
    RwCamera           *cameraCheck;

    RWFUNCTION(RWSTRING("PVScreatecam"));

    RWASSERT(world);
    RWASSERT(mindist > 0.0f);
    RWASSERT(maxdist > 0.0f);
    RWASSERT(mindist < maxdist);

    /* cache the world pointer. */
    rpPVSGlobals.world = world;
    pvsCache = PVSCACHEFROMWORLD(world);

    /* create a camera to use */
    rpPVSGlobals.camera = RwCameraCreate();
    cameraCheck = RwCameraSetFrame(rpPVSGlobals.camera, RwFrameCreate());

    subRect.x = 0;
    subRect.y = 0;
    subRect.w = rpPVSGlobals.rasterW;
    subRect.h = rpPVSGlobals.rasterH;

    if (raster)
    {
        subRas = RwRasterCreate(0, 0, 0, rwRASTERTYPECAMERA);
        RwRasterSubRaster(subRas, raster, &subRect);
    }
    else
    {
        subRas =
            RwRasterCreate(rpPVSGlobals.rasterW, rpPVSGlobals.rasterH, 0,
                           rwRASTERTYPECAMERA);
    }
    if (RwRasterGetDepth(subRas) < 24)
    {
        RWMESSAGE(("Using pixel formats of less than 888 for PVS generation may result in dithering errors"));
    }

    cameraCheck = RwCameraSetRaster(rpPVSGlobals.camera, subRas);

    if (zraster)
    {
        subZRas = RwRasterCreate(0, 0, 0, rwRASTERTYPEZBUFFER);
        RwRasterSubRaster(subZRas, zraster, &subRect);
    }
    else
    {
        subZRas =
            RwRasterCreate(rpPVSGlobals.rasterW, rpPVSGlobals.rasterH, 0,
                           rwRASTERTYPEZBUFFER);
    }

    cameraCheck = RwCameraSetZRaster(rpPVSGlobals.camera, subZRas);

    RwCameraSetFarClipPlane(rpPVSGlobals.camera, maxdist);
    RwCameraSetNearClipPlane(rpPVSGlobals.camera, mindist);
    viewwin.x = 1.0f;
    viewwin.y = 1.0f;
    RwCameraSetViewWindow(rpPVSGlobals.camera, &viewwin);
    RpWorldAddCamera(world, rpPVSGlobals.camera);

    /* images we use to sample world */
    rpPVSGlobals.image =
        RwImageCreate(rpPVSGlobals.rasterW, rpPVSGlobals.rasterH, 32);
    RwImageAllocatePixels(rpPVSGlobals.image);

    RWRETURNVOID();
}

/****************************************************************************/
static void
PVSdestroycam(RpWorld * world)
{
    RpPVSCache         *pvsCache;
    RwCamera           *cameraCheck;

    RWFUNCTION(RWSTRING("PVSdestroycam"));

    pvsCache = PVSCACHEFROMWORLD(world);

    RwImageFreePixels(rpPVSGlobals.image);
    RwImageDestroy(rpPVSGlobals.image);

    RpWorldRemoveCamera(world, rpPVSGlobals.camera);
    RwFrameDestroy(RwCameraGetFrame(rpPVSGlobals.camera));
    cameraCheck = RwCameraSetFrame(rpPVSGlobals.camera, (RwFrame *)NULL);

    RwRasterDestroy(RwCameraGetZRaster(rpPVSGlobals.camera));
    cameraCheck = RwCameraSetZRaster(rpPVSGlobals.camera, (RwRaster *)NULL);
    RwRasterDestroy(RwCameraGetRaster(rpPVSGlobals.camera));
    cameraCheck = RwCameraSetRaster(rpPVSGlobals.camera, (RwRaster *)NULL);

    RwCameraDestroy(rpPVSGlobals.camera);

    RWRETURNVOID();
}

/**
 * \ingroup rppvs310
 * \ref RpPVSAddWorldSector
 * is to mark the given world sector as visible in the current visiliblity
 * map. Can be used as a peer to the RpPVSAddPOV call from a create callback.
 *
 * The include file rppvs310.h and the library file rppvs310.lib are
 * required to use this function. The library file rpworld.lib is also
 * required.
 *
 * \param spSect  A pointer to a RpWorldSector.
 *
 * \return RpWorldSector if sucessful, NULL otherwise.
 *
 * \see RpPVSAddPOV
 * \see RpPVSGeneric
 * \see RpPVSCreate
 * \see RpPVSAddExtraPOV
 */
RpWorldSector      *
RpPVSAddWorldSector(RpWorldSector * spSect)
{
    RpPVS              *ppCur;
    const RpPVSCache   *pvsCache;

    RWAPIFUNCTION(RWSTRING("RpPVSAddWorldSector"));

    RWASSERT(spSect);
    RWASSERT(rpPVSGlobals.world);

    ppCur = PVSFROMWORLDSECTOR(spSect);
    pvsCache = PVSCACHEFROMCONSTWORLD(rpPVSGlobals.world);

    PVSVISMAPSETSECTOR(pvsCache->sectorVismap, ppCur->sectorID);

    RWRETURN(spSect);
}

/**
 * \ingroup rppvs310
 * \ref RpPVSAddPOV is used to generate PVS visibility data for
 * the specified world sector using the given viewpoint position.
 * Typically used with RpPVSCreate to specify viewpoints within a
 * world from which to test for world sector visiblity.
 *
 * This function is used by the RpPVSCallBack function to collect samples.
 *
 * The PVS plugin must be attached before using this function.
 *
 * The include file rppvs310.h and the library file rppvs310.lib are
 * required to use this function. The library file rpworld.lib is also
 * required.
 *
 * \param pos  A pointer to a RwV3d specifying the sampling position.
 *
 * \see RpPVSAddWorldSector
 * \see RpPVSGeneric
 * \see RpPVSCreate
 * \see RpPVSAddExtraPOV
 */
void
RpPVSAddPOV(RwV3d * pos)
{
    RwMatrix           *cameraMat;
    RwFrame            *cameraFrame;
    RwInt32             i;
    RpPVSCache         *pvsCache;

    RWAPIFUNCTION(RWSTRING("RpPVSAddPOV"));

    RWASSERT(rpPVSGlobals.world);
    RWASSERT(pos);

    pvsCache = PVSCACHEFROMWORLD(rpPVSGlobals.world);

    cameraFrame = RwCameraGetFrame(rpPVSGlobals.camera);
    cameraMat = RwFrameGetMatrix(cameraFrame);

    RwMatrixTranslate(cameraMat, pos, rwCOMBINEREPLACE);

    for (i = 0; i < 4; i++)
    {
        /* render from viewpoint and test visibility */
        PVSRenderVisMap(pvsCache);

        RwMatrixRotate(cameraMat, RwMatrixGetUp(cameraMat), 90.0f,
                       rwCOMBINEPOSTCONCAT);
        *RwMatrixGetPos(cameraMat) = *pos;
    }

    RwMatrixRotate(cameraMat, RwMatrixGetRight(cameraMat), 90.0f,
                   rwCOMBINEPOSTCONCAT);
    *RwMatrixGetPos(cameraMat) = *pos;
    for (i = 0; i < 2; i++)
    {
        /* render from viewpoint and test visibility */
        PVSRenderVisMap(pvsCache);

        RwMatrixRotate(cameraMat, RwMatrixGetRight(cameraMat), 180.0f,
                       rwCOMBINEPOSTCONCAT);
        *RwMatrixGetPos(cameraMat) = *pos;
    }

    RWRETURNVOID();
}

static RpCollisionTriangle *
PVSLOSCollision(RpIntersection * __RWUNUSED__  is,
                RpWorldSector * __RWUNUSED__ sector,
                RpCollisionTriangle * collPlane,
                RwReal distance, void *pData)
{
    RpCollisionTriangle *result;
    RwBool *hit;

    RWFUNCTION(RWSTRING("PVSLOSCollision"));

    result = collPlane;

    hit = (RwBool *) pData;

    if (distance < (RwReal) 0.999)
    {
        *hit = TRUE;

        result = (RpCollisionTriangle *) NULL;
    }

    RWRETURN(result);
}

/*
 * $ingroup rppvs310
 * $ref PVSAddLOS is used to generate PVS visibility data for
 * the specified world sector using the given viewpoint position.
 * Typically used with RpPVSCreate to specify viewpoints within a
 * world from which to test for world sector visiblity.
 *
 * This function is used by the RpPVSCallBack function to collect samples.
 *
 * The PVS plugin must be attached before using this function.
 *
 * The include file rppvs310.h and the library file rppvs310.lib are
 * required to use this function. The library file rpworld.lib is also
 * required.
 *
 * $param pos  A pointer to a RwV3d specifying the sampling position.
 *
 * $see RpPVSAddWorldSector
 * $see RpPVSGeneric
 * $see RpPVSCreate
 * $see RpPVSAddExtraPOV
 */
static RpWorldSector *
PVSAddLOS(RpWorldSector * spSect, void *pData)
{
    RwV3d              *pos, *vert;
    RpPVSCache         *pvsCache;
    RpPVS              *ppCur;
    RpIntersection     isLine;
    RwBool             done, hit;
    RwInt32            i;

    RWFUNCTION(RWSTRING("PVSAddLOS"));

    RWASSERT(rpPVSGlobals.world);

    pos = (RwV3d *) pData;

    pvsCache = PVSCACHEFROMWORLD(rpPVSGlobals.world);
    ppCur = PVSFROMWORLDSECTOR(spSect);

    /* Ignore this sector if its the current sector. */
    if (spSect == pvsCache->spCOP)
        RWRETURN(spSect);

    /* Ignore this sector is it's empty. */
    if (spSect->numPolygons == 0)
        RWRETURN(spSect);

    /* Early out. Do not test if this sector is already marked as
     * visible.
     */
    if (PVSVISMAPGETSECTOR(pvsCache->sectorVismap, ppCur->sectorID))
        RWRETURN(spSect);

    /* Do intersection test with all the sector's verts.
     * Early out once one is visible.
     */
    isLine.type = rpINTERSECTLINE;
    isLine.t.line.start = *pos;

    vert = spSect->vertices;
    i = 0;
    done = FALSE;
    while ((!done) && (i < spSect->numVertices))
    {
        hit = FALSE;
        isLine.t.line.end = *vert;

        RpCollisionWorldForAllIntersections(rpPVSGlobals.world, &isLine,
                                            PVSLOSCollision, &hit);

        /* Check if the vert is directly visible,  if so, mark the sector and
         * exit.
         */
        if (hit == FALSE)
        {
           PVSVISMAPSETSECTOR(pvsCache->sectorVismap, ppCur->sectorID);

           done = TRUE;
        }

        i++;
        vert++;
    }

    RWRETURN(spSect);
}


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

/********************************************************************
 * For space filling sectors we use sample 3 planes through the sector
 * in the X,Y and Z planes rather than space filling as we do for PVSGeneric
 * because we know there are no occluders in the sector.
 */
static RpWorldSector *
XYZPlane(RpWorldSector * spSect, const RwBBox * box, RwReal gran)
{
    RwReal              oogran, progress;
    RwBBox              bbox;
    RwV3d               anchor, center, delta;
    RwInt32             x, y, z, w, h, d;
    RpPVSCache         *pvsCache;

    RWFUNCTION(RWSTRING("XYZPlane"));

    RWASSERT(rpPVSGlobals.world);

    pvsCache = PVSCACHEFROMWORLD(rpPVSGlobals.world);

    progress =
        (RwReal) (rpPVSGlobals.progress_count) /
        (RwReal) pvsCache->sectorCache.viscount *
        (RwReal) 100.0f;

    /* drive sample granularity from fraction of world size */
    bbox = *RpWorldGetBBox(rpPVSGlobals.world);
    RwV3dSub(&delta, &bbox.sup, &bbox.inf);
    gran = gran * RwV3dLength(&delta);
    oogran = 1.0f / gran;

    /* snap to integrals of "gran" */
    RwV3dScale(&bbox.inf, &box->inf, oogran);
    x = 1 + (RwInt32) bbox.inf.x;
    y = 1 + (RwInt32) bbox.inf.y;
    z = 1 + (RwInt32) bbox.inf.z;
    bbox.inf.x = x * gran;
    bbox.inf.y = y * gran;
    bbox.inf.z = z * gran;

    RwV3dScale(&bbox.sup, &box->sup, oogran);
    w = (RwInt32) bbox.sup.x;
    h = (RwInt32) bbox.sup.y;
    d = (RwInt32) bbox.sup.z;
    bbox.sup.x = w * gran;
    bbox.sup.y = h * gran;
    bbox.sup.z = d * gran;

    /* if a dimension is <gran use center */
    RwV3dAdd(&center, &box->inf, &box->sup);
    RwV3dScale(&center, &center, 0.5f);

    w = w - x + 1;
    if (w <= 0)
    {
        bbox.inf.x = center.x;
        w = 1;
    }

    h = h - y + 1;
    if (h <= 0)
    {
        bbox.inf.y = center.y;
        h = 1;
    }

    d = d - z + 1;
    if (d <= 0)
    {
        bbox.inf.z = center.z;
        d = 1;
    }

    /* X plane */
    anchor.x = center.x;
    anchor.z = bbox.inf.z;
    for (z = 0; z < d; z++, anchor.z += gran)
    {
        anchor.y = bbox.inf.y;
        for (y = 0; y < h; y++, anchor.y += gran)
        {
            RpPVSAddPOV(&anchor);
            PvsMarkerAdd(PVSFROMWORLDSECTOR(spSect)->sectorID,
                         &anchor, 0, 255, 0);
        }
    }

    if (pvsCache->progressCallBack)
    {
        if (!(pvsCache->progressCallBack
             (rpPVSPROGRESSUPDATE, progress)))
        {
            RWRETURN((RpWorldSector *)NULL);
        }
    }


    /* Y plane */
    anchor.y = center.y;
    anchor.z = bbox.inf.z;
    for (z = 0; z < d; z++, anchor.z += gran)
    {
        anchor.x = bbox.inf.x;
        for (x = 0; x < w; x++, anchor.x += gran)
        {
            RpPVSAddPOV(&anchor);
            PvsMarkerAdd(PVSFROMWORLDSECTOR(spSect)->sectorID,
                         &anchor, 0, 255, 0);
        }
    }

    if (pvsCache->progressCallBack)
    {
        if (!(pvsCache->progressCallBack
             (rpPVSPROGRESSUPDATE, progress)))
        {
            RWRETURN((RpWorldSector *)NULL);
        }
    }

    /* Z plane */
    anchor.z = center.z;
    anchor.y = bbox.inf.y;
    for (y = 0; y < h; y++, anchor.y += gran)
    {
        anchor.x = bbox.inf.x;
        for (x = 0; x < w; x++, anchor.x += gran)
        {
            RpPVSAddPOV(&anchor);
            PvsMarkerAdd(PVSFROMWORLDSECTOR(spSect)->sectorID,
                         &anchor, 0, 255, 0);
        }
    }

    /* progress */
    if (pvsCache->progressCallBack)
    {
        if (!(pvsCache->progressCallBack
            (rpPVSPROGRESSUPDATE, progress)))
        {
            RWRETURN((RpWorldSector *)NULL);
        }
    }

    RWRETURN(spSect);
}

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

RpWorldSector      *
_rpPVSLineOfSight(RpWorldSector * spSect, const RwBBox * box, void *pData)
{
    RwReal              gran = *(RwReal *) pData;
    RwReal              oogran, progress, granx, grany, granz;
    RwBBox              bbox;
    RwV3d               anchor;
    RwInt32             x, y, z, w, h, d;
    RpPVSCache         *pvsCache;

    RWFUNCTION(RWSTRING("_rpPVSLineOfSight"));

    RWASSERT(rpPVSGlobals.world);

    pvsCache = PVSCACHEFROMWORLD(rpPVSGlobals.world);

    /* Progress */
    progress =
        (RwReal) (rpPVSGlobals.progress_count) /
        (RwReal) pvsCache->sectorCache.viscount *
        (RwReal) 100.0f;

    /* drive sample granularity from fraction of world size */
    gran = gran * rpPVSGlobals.diag;
    oogran = 1.0f / gran;

    /* Find how many samples per dimension */
    w = (RwInt32) (((box->sup.x - box->inf.x) / gran) + 0.5f);

    if (w <= 0)
    {
        granx = gran;
        bbox.inf.x = (box->sup.x + box->inf.x) * (RwReal) 0.5f;
        w = 0;
    }
    else
    {
        granx = ((box->sup.x - box->inf.x) / (RwReal) w);
        bbox.inf.x = box->inf.x;
    }

    h = (RwInt32) (((box->sup.y - box->inf.y) / gran) + 0.5f);

    if (h <= 0)
    {
        grany = gran;
        bbox.inf.y = (box->sup.y + box->inf.y) * 0.5f;
        h = 0;
    }
    else
    {
        grany = ((box->sup.y - box->inf.y) / (RwReal) h);
         bbox.inf.y = box->inf.y;
    }

    d = (RwInt32) (((box->sup.z - box->inf.z) / gran) + 0.5f);

    if (d <= 0)
    {
        granz = gran;
        bbox.inf.z = (box->sup.z + box->inf.z) * 0.5f;
        d = 0;
    }
    else
    {
        granz = ((box->sup.z - box->inf.z) / (RwReal) d);
        bbox.inf.z = box->inf.z;

    }

    anchor.z = bbox.inf.z;
    for (z = 0; z <= d; z++, anchor.z += granz)
    {
        anchor.y = bbox.inf.y;
        for (y = 0; y <= h; y++, anchor.y += grany)
        {
            anchor.x = bbox.inf.x;
            for (x = 0; x <= w; x++, anchor.x += granx)
            {
                if (inouttest(&anchor, gran))
                {
                    /* add Line Of Sight */
                    RpWorldForAllWorldSectors(rpPVSGlobals.world,
                            PVSAddLOS, (void *) &anchor);

                    PvsMarkerAdd(PVSFROMWORLDSECTOR(spSect)->
                                    sectorID, &anchor, 0, 255, 0);
                }
                else
                {
                    PvsMarkerAdd(PVSFROMWORLDSECTOR(spSect)->
                                    sectorID, &anchor, 0, 0, 0);
                }

                /* progress */
                if (pvsCache->progressCallBack)
                {
                    if (!(pvsCache->progressCallBack
                        (rpPVSPROGRESSUPDATE, progress)))
                    {
                        RWRETURN((RpWorldSector *)NULL);
                    }
                }
            }
        }
    }

    RWRETURN(spSect);
}

/**
 * \ingroup rppvs310
 * \ref RpPVSGeneric
 * is the RenderWare supplied function for sampling within a world sector. The
 * samples are distributed in a uniform grid.
 *
 * This requires the private data to be a pointer to a RwReal, ranged from 0 to 1,
 * to specify the sampling distance between two points. The number is the fraction
 * of the diagional length of the world's bounding box.
 *
 * The include file rppvs310.h and the library file rppvs310.lib are
 * required to use this function. The library file rpworld.lib is also
 * required.
 *
 * \param spSect  A pointer to the RpWorldSector being sampled.
 * \param box  A pointer to a RwBBox specifying the sampling volume.
 * \param pData  A pointer to private data for the sampling function.
 *
 * \return RpWorldSector if successful or NULL if there is an error.
 *
 * \see RpPVSAddWorldSector
 * \see RpPVSAddPOV
 * \see RpPVSCreate
 * \see RpPVSAddExtraPOV
 */
RpWorldSector      *
RpPVSGeneric(RpWorldSector * spSect, const RwBBox * box, void *pData)
{
    RwReal              gran = *(RwReal *) pData;
    RwReal              oogran, radius, progress, granx, grany, granz;
    RwBBox              bbox;
    RwV3d               anchor;
    RwInt32             x, y, z, w, h, d, hitcount;
    RpPVSCache         *pvsCache;
    RpIntersection      isSphere;

    RWAPIFUNCTION(RWSTRING("RpPVSGeneric"));

    RWASSERT(rpPVSGlobals.world);

    pvsCache = PVSCACHEFROMWORLD(rpPVSGlobals.world);

    if (spSect->numPolygons == 0)
    {
        /* treated specially - see function comment */
        if (XYZPlane(spSect, box, gran) != spSect)
        {
            RWRETURN(((RpWorldSector *)NULL));
        }

        RWRETURN(spSect);
    }

    /* Progress */
    progress =
        (RwReal) (rpPVSGlobals.progress_count) /
        (RwReal) pvsCache->sectorCache.viscount *
        (RwReal) 100.0f;

    /* drive sample granularity from fraction of world size */
    gran = gran * rpPVSGlobals.diag;
    oogran = 1.0f / gran;

    /* Find how many samples per dimension */
    w = (RwInt32) (((box->sup.x - box->inf.x) / gran) + 0.5f);

    if (w <= 0)
    {
        granx = gran;
        bbox.inf.x = (box->sup.x + box->inf.x) * (RwReal) 0.5f;
        w = 0;
    }
    else
    {
        granx = ((box->sup.x - box->inf.x) / (RwReal) w);
        bbox.inf.x = box->inf.x;
    }

    h = (RwInt32) (((box->sup.y - box->inf.y) / gran) + 0.5f);

    if (h <= 0)
    {
        grany = gran;
        bbox.inf.y = (box->sup.y + box->inf.y) * 0.5f;
        h = 0;
    }
    else
    {
        grany = ((box->sup.y - box->inf.y) / (RwReal) h);
         bbox.inf.y = box->inf.y;
    }

    d = (RwInt32) (((box->sup.z - box->inf.z) / gran) + 0.5f);

    if (d <= 0)
    {
        granz = gran;
        bbox.inf.z = (box->sup.z + box->inf.z) * 0.5f;
        d = 0;
    }
    else
    {
        granz = ((box->sup.z - box->inf.z) / (RwReal) d);
        bbox.inf.z = box->inf.z;

    }

    isSphere.type = rpINTERSECTSPHERE;
    radius = RwCameraGetNearClipPlane(rpPVSGlobals.camera);
    rwSqrtMacro(isSphere.t.sphere.radius, radius * radius * 2.0f);

    anchor.z = bbox.inf.z;
    for (z = 0; z <= d; z++, anchor.z += granz)
    {
        isSphere.t.sphere.center.z = anchor.z;

        anchor.y = bbox.inf.y;
        for (y = 0; y <= h; y++, anchor.y += grany)
        {
            isSphere.t.sphere.center.y = anchor.y;

            anchor.x = bbox.inf.x;
            for (x = 0; x <= w; x++, anchor.x += granx)
            {
                isSphere.t.sphere.center.x = anchor.x;

                hitcount = FALSE;
                RpCollisionWorldForAllIntersections(rpPVSGlobals.world,
                                                    &isSphere,
                                                    PVSSphereCollision,
                                                    &hitcount);

                if (!hitcount)
                {
                    if (inouttest(&anchor, gran))
                    {
                        /* add POV */
                        RpPVSAddPOV(&anchor);
                        PvsMarkerAdd(PVSFROMWORLDSECTOR(spSect)->
                                     sectorID, &anchor, 0, 255, 0);
                    }
                    else
                    {
                        PvsMarkerAdd(PVSFROMWORLDSECTOR(spSect)->
                                     sectorID, &anchor, 0, 0, 0);
                    }
                }
                else
                {
                    PvsMarkerAdd(PVSFROMWORLDSECTOR(spSect)->sectorID,
                                 &anchor, 255, 0, 0);
                }

                /* progress */
                if (pvsCache->progressCallBack)
                {
                    if (!(pvsCache->progressCallBack
                        (rpPVSPROGRESSUPDATE, progress)))
                    {
                        RWRETURN((RpWorldSector *)NULL);
                    }
                }
            }
        }
    }

    RWRETURN(spSect);
}

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

/**
 * \ingroup rppvs310
 * \ref RpPVSAddExtraPOV
 * is used to update the current visibility map with a sample using the given
 * position.
 *
 * It is possible for the PVS to drop sectors incorrectly due to insufficient
 * sampling. RpPVSAddExtraPOV can be used to repair such errors by adding
 * extra samples at specific position.
 *
 * This functions assumes PVS data is already present in a world.
 *
 * The include file rppvs310.h and the library file rppvs310.lib are
 * required to use this function. The library file rpworld.lib is also
 * required.
 *
 * \param wpWorld  A pointer to a RpWorld with PVS.
 * \param raster  A Pointer to a RwRaster for the frame buffer.
 * \param zraster  A Pointer to a RwRaster for the z-buffer.
 * \param mindist  A RwReal specifying the near clipping distance.
 * \param maxdist  A RwReal specifying the far clipping distance.
 * \param mat  A pointer to a RwMatrix specifying the sampling position.
 *
 * \return RpWorld if successful or NULL if there is an error.
 *
 * \see RpPVSAddWorldSector
 * \see RpPVSAddPOV
 * \see RpPVSGeneric
 * \see RpPVSCreate
 */
RpWorld            *
RpPVSAddExtraPOV(RpWorld * wpWorld,
                 RwRaster * raster, RwRaster * zraster,
                 RwReal mindist, RwReal maxdist, RwMatrix * mat)
{
    RpPVSCache         *pvsCache;
    RpIntersection      isSphere;
    RwBool              hitcount;

    RWAPIFUNCTION(RWSTRING("RpPVSAddExtraPOV"));

    RWASSERT(wpWorld);
    RWASSERT(mindist > 0.0f);
    RWASSERT(maxdist > 0.0f);
    RWASSERT(mindist < maxdist);

    pvsCache = PVSCACHEFROMWORLD(wpWorld);

    /* cache it */
    rpPVSGlobals.world = wpWorld;

    /* Create the vertex buffer for immediate mode. */
    pvsCache->im3DVert =
        (RwIm3DVertex *) RwMalloc(pvsCache->maxNumVert *
                                  sizeof(RwIm3DVertex));
    pvsCache->imVertIndex =
        (RwImVertexIndex *) RwMalloc(pvsCache->maxNumPoly * 3 *
                                     sizeof(RwImVertexIndex));

    PVScreatecam(wpWorld, raster, zraster, mindist, maxdist);
    RpPVSSetViewPosition(wpWorld, RwMatrixGetPos(mat));

    isSphere.type = rpINTERSECTSPHERE;
    rwSqrtMacro(isSphere.t.sphere.radius, mindist * mindist * 2.0f);
    isSphere.t.sphere.center = *RwMatrixGetPos(mat);
    hitcount = FALSE;
    RpCollisionWorldForAllIntersections(wpWorld, &isSphere,
                                        PVSSphereCollision, &hitcount);
    if (hitcount == FALSE)
    {
        RwFrame            *cameraFrame;
        RwMatrix           *cameraMat;
        RwV3d               pos;

        cameraFrame = RwCameraGetFrame(rpPVSGlobals.camera);
        cameraMat = RwFrameGetMatrix(cameraFrame);

        RwMatrixCopy(cameraMat, mat);
        pos = *RwMatrixGetPos(mat);

        RpPVSAddPOV(&pos);
    }

    PVSdestroycam(wpWorld);

    RwFree(pvsCache->im3DVert);
    RwFree(pvsCache->imVertIndex);

    RWRETURN(wpWorld);
}

/* PRIVATE: */
/* as for RpPVSAddExtraPOV but returns pvsImage [LookAt direction] */
RpWorld            *
_rpPVSAddExtraPOV(RpWorld * wpWorld,
                  RwRaster * raster, RwRaster * zraster,
                  RwReal mindist, RwReal maxdist,
                  RwMatrix * mat, RwRaster * ras)
{
    RpPVSCache         *pvsCache;
    RpIntersection      isSphere;
    RwBool              hitcount;
    RwInt32             i;

    RWFUNCTION(RWSTRING("_rpPVSAddExtraPOV"));

    RWASSERT(wpWorld);
    RWASSERT(mindist > 0.0f);
    RWASSERT(maxdist > 0.0f);
    RWASSERT(mindist < maxdist);

    pvsCache = PVSCACHEFROMWORLD(wpWorld);

    /* cache it */
    rpPVSGlobals.world = wpWorld;

    /* Create the vertex buffer for immediate mode. */
    pvsCache->im3DVert =
        (RwIm3DVertex *) RwMalloc(pvsCache->maxNumVert *
                                  sizeof(RwIm3DVertex));
    pvsCache->imVertIndex =
        (RwImVertexIndex *) RwMalloc(pvsCache->maxNumPoly * 3 *
                                     sizeof(RwImVertexIndex));

    PVScreatecam(wpWorld, raster, zraster, mindist, maxdist);
    RpPVSSetViewPosition(wpWorld, RwMatrixGetPos(mat));

    isSphere.type = rpINTERSECTSPHERE;
    rwSqrtMacro(isSphere.t.sphere.radius, mindist * mindist * 2.0f);
    isSphere.t.sphere.center = *RwMatrixGetPos(mat);
    hitcount = FALSE;
    RpCollisionWorldForAllIntersections(wpWorld, &isSphere,
                                        PVSSphereCollision, &hitcount);
    if (hitcount == FALSE)
    {
        RwFrame            *cameraFrame;
        RwMatrix           *cameraMat, flipmat;
        RwV3d               pos;

        cameraFrame = RwCameraGetFrame(rpPVSGlobals.camera);
        cameraMat = RwFrameGetMatrix(cameraFrame);

        /* we flip the matrix so the last image generated is the LookAt one */
        /* NB we can't use RpPVSAddPOV because it uses an axis-aligned matrix */
        RwMatrixCopy(&flipmat, mat);
        RwV3dScale(&flipmat.right, &mat->right, 1.0f);
        RwV3dScale(&flipmat.up, &mat->at, 1.0f);
        RwV3dScale(&flipmat.at, &mat->up, -1.0f);
        RwV3dScale(&flipmat.pos, &mat->pos, 1.0f);

        RwMatrixCopy(cameraMat, &flipmat);
        pos = *RwMatrixGetPos(cameraMat);

        for (i = 0; i < 4; i++)
        {
            /* render from viewpoint and test visibility */
            PVSRenderVisMap(pvsCache);

            RwMatrixRotate(cameraMat, RwMatrixGetUp(cameraMat), 90.0f,
                           rwCOMBINEPOSTCONCAT);
            *RwMatrixGetPos(cameraMat) = pos;
        }

        RwMatrixRotate(cameraMat, RwMatrixGetRight(cameraMat), 90.0f,
                       rwCOMBINEPOSTCONCAT);
        *RwMatrixGetPos(cameraMat) = pos;
        for (i = 0; i < 2; i++)
        {
            /* render from viewpoint and test visibility */
            PVSRenderVisMap(pvsCache);

            RwMatrixRotate(cameraMat, RwMatrixGetRight(cameraMat),
                           180.0f, rwCOMBINEPOSTCONCAT);
            *RwMatrixGetPos(cameraMat) = pos;
        }

        if (ras)
        {
            RwRasterSetFromImage(ras, rpPVSGlobals.image);
        }
    }

    PVSdestroycam(wpWorld);

    RwFree(pvsCache->im3DVert);
    RwFree(pvsCache->imVertIndex);

    RWRETURN(wpWorld);
}

/****************************************************************************/
static RpWorldSector *
PVSDispatch(RpWorldSector * worldSector, void *voidbundlecb)
{
    RpWorld            *world;
    RpPVS              *ppCur;
    RpPVSCache         *pvsCache;
    const RwBBox       *sectorBBox;
    _RpPVSCallBack     *bundlecb = (_RpPVSCallBack *) voidbundlecb;

    RWFUNCTION(RWSTRING("PVSDispatch"));
    RWASSERT(worldSector);
    RWASSERT(rpPVSGlobals.world);

    world = rpPVSGlobals.world;
    ppCur = PVSFROMWORLDSECTOR(worldSector);
    pvsCache = PVSCACHEFROMWORLD(world);

    sectorBBox = RpWorldSectorGetBBox(worldSector);

    /* we're sampling this sector */
    pvsCache->spCOP = worldSector;
    pvsCache->sectorVismap = ppCur->vismap;

    if (worldSector->numPolygons == 0)
    {
        if (bundlecb->callback(worldSector, sectorBBox,
                                bundlecb->pData) !=
            worldSector)
        {
            /* halt pvs generation */
            RpPVSDestroy(world);
            RWRETURN((RpWorldSector *)NULL);
        }

        /* Progress */
        if (pvsCache->progressCallBack)
        {
            RwReal progress;

            progress =
                (RwReal) (rpPVSGlobals.progress_count) /
                (RwReal) pvsCache->sectorCache.viscount *
                (RwReal) 100.0f;

            if (!(pvsCache->progressCallBack
                (rpPVSPROGRESSUPDATE, progress)))
            {
                RWRETURN((RpWorldSector *)NULL);
            }
        }

        /* Progress */
        rpPVSGlobals.progress_count++;
    }
    else
    {
        RwBBox              testBBox;
        RwReal              maxdim;
        RwInt32             x, y, z;

        maxdim = 1.0f / pvsCache->sectorCache.oomaxdim;

        /* enum vismaps for this sector? */
        testBBox.inf.z = sectorBBox->inf.z;
        for (z = 0; z < ppCur->z_segs; z++, testBBox.inf.z += maxdim)
        {
            testBBox.inf.y = sectorBBox->inf.y;
            for (y = 0; y < ppCur->y_segs;
                 y++, testBBox.inf.y += maxdim)
            {
                testBBox.inf.x = sectorBBox->inf.x;
                for (x = 0; x < ppCur->x_segs;
                     x++, testBBox.inf.x += maxdim)
                {
                    /* bbox of region */
                    testBBox.sup.x = testBBox.inf.x + maxdim;
                    testBBox.sup.y = testBBox.inf.y + maxdim;
                    testBBox.sup.z = testBBox.inf.z + maxdim;
                    if (testBBox.sup.x > sectorBBox->sup.x)
                        testBBox.sup.x = sectorBBox->sup.x;
                    if (testBBox.sup.y > sectorBBox->sup.y)
                        testBBox.sup.y = sectorBBox->sup.y;
                    if (testBBox.sup.z > sectorBBox->sup.z)
                        testBBox.sup.z = sectorBBox->sup.z;

                    /* Add vismap bounding bpx. */
                    PvsBBoxAdd(ppCur->sectorID, &testBBox, 0, 0, 255);

                    if (bundlecb->callback(worldSector, &testBBox,
                                           bundlecb->pData) !=
                        worldSector)
                    {
                        /* halt pvs generation */
                        RpPVSDestroy(world);
                        RWRETURN((RpWorldSector *)NULL);
                    }

                    /* Progress */
                    if (pvsCache->progressCallBack)
                    {
                        RwReal progress;

                        progress =
                            (RwReal) (rpPVSGlobals.progress_count) /
                            (RwReal) pvsCache->sectorCache.viscount *
                            (RwReal) 100.0f;

                        if (!(pvsCache->progressCallBack
                            (rpPVSPROGRESSUPDATE, progress)))
                        {
                            RWRETURN((RpWorldSector *)NULL);
                        }
                    }

                    rpPVSGlobals.progress_count++;

                    /* bump vismap */
                    pvsCache->sectorVismap +=
                        pvsCache->sectorCache.vislen;
                }
            }
        }
    }

    RWRETURN(worldSector);
}

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

static RpWorldSector *
PVSmaxedge(RpWorldSector * spSect, void *pData)
{
    RwReal             *maxdim = (RwReal *) pData;
    const RwBBox       *bbox = RpWorldSectorGetBBox(spSect);
    RwV3d               delta;

    RWFUNCTION(RWSTRING("PVSmaxedge"));

    RwV3dSub(&delta, &bbox->sup, &bbox->inf);
    if (delta.x > *maxdim)
    {
        *maxdim = delta.x;
    }
    if (delta.y > *maxdim)
    {
        *maxdim = delta.y;
    }
    if (delta.z > *maxdim)
    {
        *maxdim = delta.z;
    }

    RWRETURN(spSect);
}

static RpWorldSector *
PVSsinit(RpWorldSector * spSect, void *pData)
{
    RpPVSCache         *pvsCache = (RpPVSCache *) pData;
    RpPVS              *ppCur = PVSFROMWORLDSECTOR(spSect);
    const RwBBox       *bbox = RpWorldSectorGetBBox(spSect);
    RwV3d               delta;

    RWFUNCTION(RWSTRING("PVSsinit"));

    /* ID each sector */
    ppCur->sectorID = pvsCache->nextID;
    pvsCache->nextID++;

    /* at least 1 vismap for each sector */
    ppCur->x_segs = 1;
    ppCur->y_segs = 1;
    ppCur->z_segs = 1;

    if (spSect->numPolygons > 0)
    {
        /* how many vismaps we'll use for this sector */
        RwV3dSub(&delta, &bbox->sup, &bbox->inf);
        RwV3dScale(&delta, &delta, pvsCache->sectorCache.oomaxdim);
        ppCur->x_segs += (RwUInt8) delta.x;
        ppCur->y_segs += (RwUInt8) delta.y;
        ppCur->z_segs += (RwUInt8) delta.z;
    }

    /* bump to next set of vismaps */
    pvsCache->sectorCache.viscount +=
        ppCur->x_segs * ppCur->y_segs * ppCur->z_segs;

    RWRETURN(spSect);
}

static RpWorldSector *
PVSclear(RpWorldSector * spSect, void *pData)
{
    RpPVSCache         *pvsCache = (RpPVSCache *) pData;
    RpPVS              *ppCur = PVSFROMWORLDSECTOR(spSect);
    RwInt32             i;

    RWFUNCTION(RWSTRING("PVSclear"));

    /* assume everything occluded */
    i = ppCur->x_segs * ppCur->y_segs * ppCur->z_segs;
    memset(ppCur->vismap, 0,
           pvsCache->sectorCache.vislen * i * sizeof(RpPVSVisMap));

    /* ..but yourself */
    while (--i >= 0)
    {
        RpPVSVisMap        *vismap;

        vismap = ppCur->vismap + pvsCache->sectorCache.vislen * i;
        PVSVISMAPSETSECTOR(vismap, ppCur->sectorID);
    }

    RWRETURN(spSect);
}

/**
 * \ingroup rppvs310
 * \ref RpPVSCreate
 * is used to create a Potential Visibility Set, PVS, for the world. The PVS is
 * created by taking samples within each world sector to build a visibility map.
 * This map indicates which other world sectors are visible from within its
 * boundary.
 *
 * The RpPVSCallBack callback function is used for sampling within a world sector.
 * This can be \ref RpPVSGeneric or a user own private function for specific
 * samples distribution.
 *
 * Each world sector may have more than one visibility map to allow finer culling
 * by having different visibility map for different regions within a world sector.
 * The subdepth determines the number subdivision where each depth splits the
 * region by its longest side.
 *
 * The frame-buffer and z-buffer are used for storing the results from each
 * sample for building the visiblilty map. They can be user supplied or NULL.
 *
 * The format for RpPVSCallBack is
 *
 * RpWorldSector *(*RpPVSCallBack)
 *     (RpWorldSector * worldSector, const RwBBox * box, void *pData);
 *
 * The include file rppvs310.h and the library file rppvs310.lib are
 * required to use this function. The library file rpworld.lib is also
 * required.
 *
 * \param wpWorld  A pointer to a RpWorld with PVS.
 * \param raster  A Pointer to a RwRaster for the frame buffer.
 * \param zraster  A Pointer to a RwRaster for the z-buffer.
 * \param mindist  A RwReal specifying the near clipping distance.
 * \param maxdist  A RwReal specifying the far clipping distance.
 * \param maxdepth  A RwInt32 specifying the division depth of the sector.
 * \param callback  A pointer to the RpPVSCallBack function for sampling a world sector.
 * \param pData  A pointer to private data for the callback.
 *
 * \return RpWorld if successful or NULL if there is an error.
 *
 * \see RpPVSAddWorldSector
 * \see RpPVSAddPOV
 * \see RpPVSGeneric
 * \see RpPVSAddExtraPOV
 */

RpWorld            *
RpPVSCreate(RpWorld * wpWorld,
            RwRaster * raster,
            RwRaster * zraster,
            RwReal mindist, RwReal maxdist,
            RwInt32 maxdepth, RpPVSCallBack callback, void *pData)
{
    RpPVSCache         *pvsCache;
    RwReal              maxdim;
    const RwBBox       *bbox;
    RwV3d               v;
    RwInt32             len;
    RwBool              collData;
    _RpPVSCallBack      bundlecb;

    RWAPIFUNCTION(RWSTRING("RpPVSCreate"));

    RWASSERT(wpWorld);
    RWASSERT(mindist > 0.0f);
    RWASSERT(maxdist > 0.0f);
    RWASSERT(mindist < maxdist);

    /* Clear the progress count. */
    rpPVSGlobals.progress_count = 0;

    /* cache the world pointer. */
    rpPVSGlobals.world = wpWorld;
    pvsCache = PVSCACHEFROMWORLD(rpPVSGlobals.world);

    /* Any collision data ? Build them if none. */
    collData = RpCollisionWorldQueryData(wpWorld);
    if (collData == FALSE)
        RpCollisionWorldBuildData(wpWorld, 
                                  (RpCollisionBuildParam *) NULL);

    /* setup inout test tol */
    bbox = RpWorldGetBBox(wpWorld);
    RwV3dSub(&v, &bbox->sup, &bbox->inf);
    rpPVSGlobals.diag = RwV3dLength(&v);
    rpPVSGlobals.inout_tol = rpPVSGlobals.diag;
    rpPVSGlobals.inout_tol = (rpPVSGlobals.inout_tol > (RwReal) PVSINOUT_TOL) ?
                              rpPVSGlobals.inout_tol : (RwReal) PVSINOUT_TOL;

    /* setup sector parameters */

    /* find the largest sector edge */
    maxdim = 0.0f;
    RpWorldForAllWorldSectors(wpWorld, PVSmaxedge, &maxdim);
    maxdim = maxdim / (RwReal) (1 << maxdepth);

    pvsCache->sectorCache.version = PVSVERSION;
    pvsCache->sectorCache.oomaxdim = 1.0f / maxdim;
    pvsCache->sectorCache.viscount = 0;
    len =
        ((RtWorldGetNumWorldSectors(wpWorld) + 31) >> 3) /
        sizeof(RpPVSVisMap);
    pvsCache->sectorCache.vislen = len;
    pvsCache->nextID = 0;
    RpWorldForAllWorldSectors(wpWorld, PVSsinit, pvsCache);

    /* allocate all the vismap as one block */
    len = pvsCache->sectorCache.viscount * pvsCache->sectorCache.vislen;
    pvsCache->sectorBlocks =
        (char *) RwMalloc(len * sizeof(RpPVSVisMap));

    /* Give each sector x_seg*y_seg*z_seg VisMaps */
    pvsCache->nextID = 0;
    pvsCache->ppNext = pvsCache->sectorBlocks;
    RpWorldForAllWorldSectors(wpWorld, _rpPVSAlloc, pvsCache);

    /* clear down vismaps */
    RpWorldForAllWorldSectors(wpWorld, PVSclear, pvsCache);

    /* Create the vertex buffer for immediate mode. */
    pvsCache->im3DVert =
        (RwIm3DVertex *) RwMalloc(pvsCache->maxNumVert *
                                  sizeof(RwIm3DVertex));
    pvsCache->imVertIndex =
        (RwImVertexIndex *) RwMalloc(pvsCache->maxNumPoly * 3 *
                                     sizeof(RwImVertexIndex));

    if (callback)
    {
        /* so we can pass a single pointer */
        bundlecb.callback = callback;
        bundlecb.pData = pData;

        PVScreatecam(wpWorld, raster, zraster, mindist, maxdist);

        /* determine visibility */
        if (pvsCache->progressCallBack)
        {
            pvsCache->progressCallBack(rpPVSPROGRESSSTART, 0.0f);
        }

        PvsMarkersInit(pvsCache->nextID);
        RpWorldForAllWorldSectors(wpWorld, PVSDispatch, &bundlecb);

        if (pvsCache->progressCallBack)
        {
            pvsCache->progressCallBack(rpPVSPROGRESSEND, 100.0f);
        }

        PVSdestroycam(wpWorld);
    }

    RwFree(pvsCache->im3DVert);
    RwFree(pvsCache->imVertIndex);

    /* Destroy collision data if it was generated by the pvs. */
    if (collData == FALSE)
        RpCollisionWorldDestroyData(wpWorld);

    RWRETURN(wpWorld);
}

#endif /* NO_PVS_CREATE */
