/*
 * Potentially Visible Set plug-in
 */

/**********************************************************************
 *
 * file :     rppvs.c
 *
 * abstract : handle culling of worldsectors 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) 2001 Criterion Software Ltd.
 * All Rights Reserved.
 *
 * RenderWare is a trademark of Canon Inc.
 *
 ************************************************************************/

#include "string.h"
#include "rwcore.h"
#include "rpworld.h"
#include "rtworld.h"
#include "rprandom.h"
#include "rtintsec.h"
#include "rpcollis.h"

#include "rpplugin.h"
#include "rpdbgerr.h"

#include "rtcharse.h"

#include "rppvs.h"
#include "rppvsaux.h"

#if (!defined(DOXYGEN))
static const char rcsid[] __RWUNUSED__ =
    "@@@@(#)$Id: rppvs.c,v 1.32 2001/10/05 14:13:22 adamj Exp $";
#endif /* (!defined(DOXYGEN)) */

RpPVSGlobalVars     rpPVSGlobals;


#define PVSVerticesEqual(_a, _b)                                        \
     (((((_a).x - (_b).x) < SMALL) && (((_a).x - (_b).x) > -SMALL)) &&  \
      ((((_a).y - (_b).y) < SMALL) && (((_a).y - (_b).y) > -SMALL)) &&  \
      ((((_a).z - (_b).z) < SMALL) && (((_a).z - (_b).z) > -SMALL)))

#define PVSIsBackFace(Cand, ViewPoint)                                  \
    ((RwV3dDotProduct(&(Cand)->plane, ViewPoint) + (Cand)->plane.w) <= SMALL)

static void
PVSAssignPolygonAttrs(PolyRecord * mypoly, PolyPtr geom, PlaneEq plane,
                       RwReal priority, RwBool original, RwInt32 home,
                       PolyListPtr parent, RwBool translucent,
                       RpWorldSector * homeaddr, RwBool done,
                       RwV3d centroid, RwReal radius, RwV3d extreme)
{
    RWFUNCTION(RWSTRING("PVSAssignPolygonAttrs"));

    /* Description */
    mypoly->geom = geom;
    mypoly->translucent = translucent;

    /* Precalcs */
    mypoly->plane = plane;
    mypoly->centroid = centroid;
    mypoly->radius = radius;
    mypoly->extreme = extreme;

    /* For sorting */
    mypoly->priority = priority;

    /* For splitting */
    mypoly->original = original;
    mypoly->parent = parent;

    /* Sector info */
    mypoly->home = home;
    mypoly->homeaddr = homeaddr;

    /* Algorithm info */
    mypoly->hasbeenclipper = done;

    RWRETURNVOID();
}

static PlaneEq
PVSGeneratePlaneEquationFromThreePoints(RwV3d * a, RwV3d * b,
                                         RwV3d * c)
{
    RwV3d               v1, v2, normal;
    PlaneEq             Plane;
    RwReal              D;

    RWFUNCTION(RWSTRING("PVSGeneratePlaneEquationFromThreePoints"));

    RwV3dSub(&v1, b, a);
    RwV3dSub(&v2, c, b);
    RwV3dCrossProduct(&normal, &v1, &v2);

    Plane.x = normal.x;
    Plane.y = normal.y;
    Plane.z = normal.z;

    D = -RwV3dDotProduct(&normal, a);
    Plane.w = D;
    Plane.l = ((RwReal)1) / RwV3dLength(&normal);

    RWRETURN(Plane);
}


static void
PVSRemoveBackFaces(PolyListPtr * Tlist, RwV3d * ViewPoint)
{
    PolyListPtr         temp = *Tlist, post = NULL, prev = NULL, todel;
    RpPVS             *pvsCur;

    RWFUNCTION(RWSTRING("PVSRemoveBackFaces"));

    while (temp != NULL)
    {
        post = temp->next;
        if (PVSIsBackFace(&(temp->data), ViewPoint))
        {
            /* Do not destroy polygon, 
             * because it is referenced by 
             * the root ("rpPVSGlobals.polygons") list */
            /* extract temp from Tlist */
            todel = temp;

            pvsCur = PVSFROMWORLDSECTOR(temp->data.homeaddr);

            if (prev != NULL)
                prev->next = temp->next;
            else
                *Tlist = temp->next;
            RwFree(todel);
            todel = NULL;
            /* prev=prev */
        }
        else
        {
            prev = temp;
        }
        temp = post;
    }
    RWRETURNVOID();
}

static RwBool
PVSPointOnPlane2(RwV3d * Cand, PlaneEq * Root, RwReal Zero)
{
    RwReal              scalar;

    RWFUNCTION(RWSTRING("PVSPointOnPlane2"));

    scalar =( RwV3dDotProduct(Root, Cand) +  Root->w) * Root->l;

    if (scalar <= Zero && scalar >= -Zero)
        RWRETURN(TRUE);
    else
        RWRETURN(FALSE);
}

static PartitionId
PVSPointWRTPlane2(RwV3d * Cand, PlaneEq * Root, RwReal Zero)
{
    RwReal              scalar;

    RWFUNCTION(RWSTRING("PVSPointWRTPlane2"));

    scalar =( RwV3dDotProduct(Root, Cand) +  Root->w) * Root->l;

    if (scalar >= Zero)
        RWRETURN(FRONT);
    if (scalar <= -Zero)
        RWRETURN(BACK);

    RWRETURN(SPLIT);
}

#define PVSSphereWRTPlaneMACRO(_centre, _radius, _plane)                    \
MACRO_START                                                                 \
{                                                                           \
    RwReal scalar;                                                          \
                                                                            \
    PVSFindScalarMacro( (_centre.x), (_centre.y), (_centre.z),              \
                        (_plane.x), (_plane.y), (_plane.z), (_plane.w),     \
                        (scalar));                                          \
    scalar*=_plane.l;                                                       \
                                                                            \
    if (scalar>=_radius) _plane.lastresult=FRONT;                           \
    else if (scalar<=-_radius) _plane.lastresult=BACK;                      \
    else _plane.lastresult=SPLIT;                                           \
}                                                                           \
MACRO_STOP

#define PVSPolygonWRTPlaneMACRO(_polygon, _plane, _result)                  \
MACRO_START                                                                 \
{                                                                           \
    RwReal scalar;                                                          \
    PolyPtr temp;                                                           \
    RwBool isonback=FALSE, isonfront=FALSE;                                 \
                                                                            \
    temp=_polygon;                                                          \
    while (temp!=NULL)                                                      \
    {                                                                       \
        PVSFindScalarMacro( (temp->v.x), (temp->v.y), (temp->v.z),          \
                            (_plane.x), (_plane.y), (_plane.z), (_plane.w), \
                            (scalar));                                      \
        scalar*=_plane.l;                                                   \
                                                                            \
        if (scalar>SMALL) isonfront=TRUE;                                   \
        else if (scalar<-SMALL) isonback=TRUE;                              \
                                                                            \
                                                                            \
        if ((isonback) && (isonfront)) break;                               \
                                                                            \
        temp=temp->next;                                                    \
    }                                                                       \
    if (isonfront && isonback) _result=SPLIT;                               \
    else if (isonback) _result=BACK;                                        \
    else if (isonfront) _result=FRONT;                                      \
    else _result=COPLANAR;                                                  \
}                                                                           \
MACRO_STOP

static PartitionId
PVSClassifyPolygonWRTPlane(PolyRecord * t, PlaneEq * ClipPlane)
{
    /* Returns back if polygon is behind, on or very close; split; or front */

    /* biggest time waster - make more efficient */
    RwBool              isonback = FALSE, isonfront = FALSE;
    PolyPtr             temp;
    PlaneEq             Clip = *ClipPlane;
    RwReal              scalar;
    RwV3d               vert;

    RWFUNCTION(RWSTRING("PVSClassifyPolygonWRTPlane"));

    /* check and assign the signed distance 
     * of each vertex to the clipping plane... */
    temp = t->geom;
    while (temp != NULL)
    {
        vert = temp->v;

        PVSFindScalarMacro((vert.x), (vert.y), (vert.z), (Clip.x),
                            (Clip.y), (Clip.z), (Clip.w), (scalar));

        scalar *= Clip.l;

        temp->scalar = scalar;
        temp->pscalar = PVSPNZ(scalar);

        if (scalar > SMALL)
            isonfront = TRUE;
        else if (scalar < -SMALL)
            isonback = TRUE;

        /* Assign values for subsequent clipping */
        temp = temp->next;
    }

    if ((isonfront) && (isonback))
    {
        RWRETURN(SPLIT);
    }
    else if (isonback)
    {
        RWRETURN(BACK);
    }
    else if (isonfront)
    {
        RWRETURN(FRONT);
    }

    RWRETURN(COPLANAR);
}

static void
PVSFindCentroidandRadius(PolyPtr * t, RwV3d * centroid,
                          RwReal * radius, RwV3d * extreme)
{
    PolyPtr             temp;
    RwInt32             Count = 0;
    RwReal              lensq = ((RwReal)0);

    RWFUNCTION(RWSTRING("PVSFindCentroidandRadius"));

    *radius = ((RwReal)0);
    centroid->x = ((RwReal)0);
    centroid->y = ((RwReal)0);
    centroid->z = ((RwReal)0);

    temp = *t;
    while (temp != NULL)
    {
        centroid->x += temp->v.x;
        centroid->y += temp->v.y;
        centroid->z += temp->v.z;
        Count++;

        temp = temp->next;
    }
    centroid->x /= Count;
    centroid->y /= Count;
    centroid->z /= Count;

    temp = *t;
    while (temp != NULL)
    {
        lensq = (temp->v.x - centroid->x) * (temp->v.x - centroid->x) +
            (temp->v.y - centroid->y) * (temp->v.y - centroid->y) +
            (temp->v.z - centroid->z) * (temp->v.z - centroid->z);

        if (lensq > *radius)
        {
            *radius = lensq;
            *extreme = temp->v;
        }
        temp = temp->next;
    }
    *radius = (RwReal) sqrt(*radius);

    RWRETURNVOID();
}

static PartitionId
PVSDivide(PolyRecord * t, PlaneEq ClipPlane __RWUNUSED__, 
           PolyRecord * inPart, PolyRecord * outPart)
{
    RwInt32             i, s, fill;
    PolyPtr             end = NULL, inend = NULL;
    PolyPtr             outend = NULL, traverse, tnxt, temp, previn, prevout;
    PolyPtr             superPoly = NULL;
    RwV3d               intersection;
    PolyPtr             in = NULL, out = NULL;
    RwInt32             invct = 0, outvct = 0;
    RwReal              radius;
    RwV3d               centroid, extreme;

    RWFUNCTION(RWSTRING("PVSDivide"));
    /* polygon needs to be divided since
     * some parts are on the front and 
     * some on the back of the clipper */

    /* firstly, create one polygon of points that is 
     * the union of the subsequent rpPVSGlobals.polygons 
     * with colicloses verts intact... */
    traverse = t->geom;
    superPoly = NULL;
    i = 0;
    s = 0;

    /* memory TIME WASTER */
    while (traverse != NULL)
    {
        /* assign first vertex from clippee polygon to superPoly... */
        _rpPVSaddendIIp(&end, &(traverse->v));
        if (superPoly == NULL)
            superPoly = end;

        /* assign scalar to pscalar array... */
        end->scalar = traverse->scalar;
        end->pscalar = traverse->pscalar;

        i++;

        if (traverse->next != NULL)
            tnxt = traverse->next;
        else
            tnxt = t->geom;

        if (end->pscalar * tnxt->pscalar < -SMALL * SMALL)
        {
            /* Before we reach the next vertex, we have a split */
            RwReal              tv =
                (ABS(tnxt->scalar)) /
                ((ABS(traverse->scalar) + ABS(tnxt->scalar)));

            intersection.x =
                ((traverse->v.x - tnxt->v.x) * tv) + tnxt->v.x;
            intersection.y =
                ((traverse->v.y - tnxt->v.y) * tv) + tnxt->v.y;
            intersection.z =
                ((traverse->v.z - tnxt->v.z) * tv) + tnxt->v.z;

            /* assign intersection to next superPoly point... */
            _rpPVSaddendIIp(&end, &(intersection));

            end->scalar = ((RwReal)0);
            end->pscalar = 0;

            i++;
        }
        s++;

        traverse = traverse->next;
    }

    /* we now have to put parts of super polygon into two next parts... */

    fill = 0;
    previn = NULL, prevout = NULL;
    temp = superPoly;
    while (temp != NULL)
    {
        if (temp->pscalar <= 0)
        {
            _rpPVSaddendIIp(&inend, &(temp->v));
            inend->pscalar = temp->pscalar;
            inend->scalar = temp->scalar;

            if (in == NULL)
                in = inend;
            invct++;
            previn = temp;
        }
        if (temp->pscalar >= 0)
        {
            _rpPVSaddendIIp(&outend, &(temp->v));
            outend->pscalar = temp->pscalar;
            outend->scalar = temp->scalar;

            if (out == NULL)
                out = outend;
            outvct++;
            prevout = temp;
        }
        temp = temp->next;
        fill++;
    }

    PVSFindCentroidandRadius(&in, &centroid, &radius, &extreme);
    if (invct >= 3)
        PVSAssignPolygonAttrs(inPart, in, t->plane, t->priority, FALSE,
                               t->home, t->parent, t->translucent,
                               t->homeaddr, t->hasbeenclipper, centroid,
                               radius, extreme);

    PVSFindCentroidandRadius(&out, &centroid, &radius, &extreme);
    if (outvct >= 3)
        PVSAssignPolygonAttrs(outPart, out, t->plane, t->priority,
                               FALSE, t->home, t->parent,
                               t->translucent, t->homeaddr,
                               t->hasbeenclipper, centroid, radius,
                               extreme);

    _rpPVSDestroyPoly(&superPoly);

    RWASSERT(invct >= 3 && outvct >= 3);

    RWRETURN(SPLIT);
}

static RwBool
PVSPolygonTrivByVolume(PolyListPtr * t, PolyRecord * Clipper)
{
    /* time waster - make more efficient */
    PartitionId         Slice;
    PolyPtr             shadowsPtr;
    RwBool              Split = FALSE;

    RWFUNCTION(RWSTRING("PVSPolygonTrivByVolume"));

    /* Triv clip against shadow face... */
    PVSSphereWRTPlaneMACRO(((*t)->data.centroid), ((*t)->data.radius),
                            (Clipper->plane));
    Slice = Clipper->plane.lastresult;

    if (Slice == FRONT)
        RWRETURN(TRUE);

    /* Triv clip against shadow edges... */
    shadowsPtr = Clipper->geom;
    while (shadowsPtr != NULL)
    {
        PVSSphereWRTPlaneMACRO(((*t)->data.centroid),
                                ((*t)->data.radius),
                                (shadowsPtr->shadowPlane));
        Slice = shadowsPtr->shadowPlane.lastresult;

        if (Slice == FRONT)
            RWRETURN(TRUE);
        else if (Slice == SPLIT)
            Split = TRUE;
        shadowsPtr = shadowsPtr->next;
    }

    if (!Split)                /* BACK */
    {
        if (!(*t)->data.original)
            _rpPVSDestroyPoly(&((*t)->data.geom)); /* memory time waster */
        RwFree(*t);
        *t = NULL;

        RWRETURN(TRUE);
    }
    else
    {
        Split = FALSE;

        /* True clip against shadow face... */
        if (Clipper->plane.lastresult != SPLIT)
            Slice = Clipper->plane.lastresult;
        else
            PVSPolygonWRTPlaneMACRO(((*t)->data.geom),
                                     (Clipper->plane), (Slice));

        if (Slice == FRONT)
            RWRETURN(TRUE);

        /* True clip against shadow edges... */
        shadowsPtr = Clipper->geom;
        while (shadowsPtr != NULL)
        {
            if (shadowsPtr->shadowPlane.lastresult != SPLIT)
            {
                Slice = shadowsPtr->shadowPlane.lastresult;
            }
            else
                PVSPolygonWRTPlaneMACRO(((*t)->data.geom),
                                         (shadowsPtr->shadowPlane),
                                         (Slice));

            if (Slice == FRONT)
                RWRETURN(TRUE);
            else if (Slice == SPLIT)
                Split = TRUE;
            shadowsPtr = shadowsPtr->next;
        }
        if (!Split)            /* BACK */
        {
            if (!(*t)->data.original)
                _rpPVSDestroyPoly(&((*t)->data.geom)); /* memory time waster */
            RwFree(*t);
            *t = NULL;

            RWRETURN(TRUE);
        }
        else
        {
            RWRETURN(FALSE);
        }
    }

}

static void
PVSPolygonClipByVolume(PolyListPtr * t, PolyRecord * Clipper,
                        PolyListPtr * inList, PolyListPtr * inListTail,
                        PolyListPtr * outList,
                        PolyListPtr * outListTail, RwInt32 side)
{
    /* Volume to clip against will be based on 
     * the semi-infinite frustrum created by
     * each edge of the Clipper and the ViewPoint */

    PartitionId         Slice;
    PolyRecord          inPart, outPart;
    RwInt32             i = 0;
    PolyPtr             shadowsPtr;

    RWFUNCTION(RWSTRING("PVSPolygonClipByVolume"));

    /* Now clip against shadow edges... */
    shadowsPtr = Clipper->geom;
    while (i++ < side)
    {
        shadowsPtr = shadowsPtr->next;
    }

    Slice =
        PVSClassifyPolygonWRTPlane(&((*t)->data),
                                    &(shadowsPtr->shadowPlane));

    if (Slice == FRONT)
    {
        PVSaddendSupremeMacro((*outList), (*outListTail), (*t));
    }
    else if (Slice == BACK || Slice == COPLANAR)
    {

        if (shadowsPtr->next != NULL) /* otherwise all clip edges are done */
        {
            /* Recursively call... */
            PVSPolygonClipByVolume(t, Clipper, inList, inListTail,
                                    outList, outListTail, side + 1);
        }
        else
        {
            PVSaddendSupremeMacro((*inList), (*inListTail), (*t));
        }
    }
    else                       /* Slide==SPLIT */
    {

        PolyListPtr         tmpi = NULL, tmpo = NULL;

        PVSDivide(&((*t)->data), shadowsPtr->shadowPlane, &inPart,
                   &outPart);

        if (!(*t)->data.original)
            _rpPVSDestroyPoly(&((*t)->data.geom)); /* memory time waster */
        RwFree(*t);
        *t = NULL;

        tmpo = _rpPVScreateNode(&outPart);
        PVSaddendSupremeMacro((*outList), (*outListTail), (tmpo));

        tmpi = _rpPVScreateNode(&inPart);

        if (shadowsPtr->next != NULL) /* otherwise all clip edges are done */
        {
            /* Recursively call... */
            PVSPolygonClipByVolume(&tmpi, Clipper, inList, inListTail,
                                    outList, outListTail, side + 1);
        }
        else
        {
            PVSaddendSupremeMacro((*inList), (*inListTail), (tmpi));
        }
    }

    RWRETURNVOID();
}

static RpWorldSector *
PVSWAClassifyPotOccSector(RpWorldSector * sector, void *data)
{
    RpPVS             *ppTo = PVSFROMWORLDSECTOR(sector);
    RwV3d               sup, inf, Corner[8];
    RwInt32             i;
    PolyPtr             shadowsPtr;
    RwBool              OnFront = FALSE, OnBack = FALSE;
    PartitionId         test;
    PolyRecord         *Clipper = (PolyRecord *) data;

    RWFUNCTION(RWSTRING("PVSWAClassifyPotOccSector"));

    if (ppTo->numpols <= SECTORCULLTOL)
    {
        /* Does not matter about assignment, 
         * since there few or no polygons */
        ppTo->potential = SPLIT; 
        RWRETURN(sector);
    }

    if (PVSVISMAPGETSECTOR(rpPVSGlobals.CurrPVS->vismap, ppTo->sectorID)) 
    {
        /* Already known visible, so treat as front */
        ppTo->potential = FRONT;
        RWRETURN(sector);
    }

    if (Clipper->homeaddr == sector)
    {
        /* This is the current sector so it must be split by definition */
        ppTo->potential = SPLIT; 
        RWRETURN(sector);
    }

    sup = ppTo->envelope->sup;
    inf = ppTo->envelope->inf;

    Corner[0].x = sup.x;
    Corner[0].y = sup.y;
    Corner[0].z = sup.z;
    Corner[1].x = sup.x;
    Corner[1].y = sup.y;
    Corner[1].z = inf.z;
    Corner[2].x = sup.x;
    Corner[2].y = inf.y;
    Corner[2].z = sup.z;
    Corner[3].x = sup.x;
    Corner[3].y = inf.y;
    Corner[3].z = inf.z;
    Corner[4].x = inf.x;
    Corner[4].y = sup.y;
    Corner[4].z = sup.z;
    Corner[5].x = inf.x;
    Corner[5].y = sup.y;
    Corner[5].z = inf.z;
    Corner[6].x = inf.x;
    Corner[6].y = inf.y;
    Corner[6].z = sup.z;
    Corner[7].x = inf.x;
    Corner[7].y = inf.y;
    Corner[7].z = inf.z;

    /* Sector clip against shadow face */
    OnFront = FALSE;
    OnBack = FALSE;
    for (i = 0; i < 8; i++)
    {
        test =
            PVSPointWRTPlane2(&(Corner[i]), &(Clipper->plane), SMALL);
        if (test == BACK)
            OnBack = TRUE;
        else
            OnFront = TRUE;
    }

    if (OnFront == TRUE && OnBack == FALSE)
    {
        ppTo->potential = FRONT;
        RWRETURN(sector);
    }
    else if (OnFront == TRUE && OnBack == TRUE)
    {
        ppTo->potential = SPLIT; /* Complex */
        RWRETURN(sector);
    }
    /* else cant be sure yet */

    /* Sector clip against shadow volume edges */
    shadowsPtr = Clipper->geom;
    while (shadowsPtr != NULL)
    {
        OnFront = FALSE;
        OnBack = FALSE;
        for (i = 0; i < 8; i++)
        {
            test =
                PVSPointWRTPlane2(&(Corner[i]),
                                   &(shadowsPtr->shadowPlane), SMALL);
            if (test == BACK)
                OnBack = TRUE;
            else
                OnFront = TRUE;
        }
        shadowsPtr = shadowsPtr->next;

        if (OnFront == TRUE && OnBack == FALSE)
        {
            ppTo->potential = FRONT;
            RWRETURN(sector);
        }
        else if (OnFront == TRUE && OnBack == TRUE)
        {
            ppTo->potential = SPLIT; /* Complex */
            RWRETURN(sector);
        }
        /* else cant be sure yet */
    }

    /* Can be sure of back, now */
    ppTo->potential = BACK;
    RWRETURN(sector);
}

static void
PVSWASubdivide(PolyRecord * ClipperElement, PolyListPtr * Tlist)
{
    /* Using a Clipper polygon, Clips all rpPVSGlobals.polygons in Tlist
     */

    PolyListPtr         temp = NULL, post = NULL, prev, todel, end;
    PolyListPtr         ttt = NULL;
    PolyListPtr         inList = NULL, outList = NULL, inListTail =
        NULL, outListTail = NULL;

    RWFUNCTION(RWSTRING("PVSWASubdivide"));

    /* Classify each sector as definately invisible (in), 
     * definately visibile (out), or not sure (split) - more work */
    if (SECTORCULL)
        RpWorldForAllWorldSectors(rpPVSGlobals.World,
                                  PVSWAClassifyPotOccSector,
                                  ClipperElement);

    ClipperElement->hasbeenclipper = TRUE;
    /* Clip t against Clipper, 
     * and add to inList or outList, or parts to both... */
    temp = *Tlist;
    prev = NULL;

    while (temp != NULL)      
    {
        /* for each poly in Tlist, 
         * check whether it is visible wrt clipper element */
        RpPVS             *ppTo =
            PVSFROMWORLDSECTOR(temp->data.homeaddr);

        /* If clippee is in visible sector or 
         * cannot be obscured since it resides in an 'out' sector,
         * don't bother clipping, and jump to next sectors polygons */
        if (JUMP)
        {
            while (temp != NULL
                   &&
                   ((PVSVISMAPGETSECTOR
                     (rpPVSGlobals.CurrPVS->vismap, temp->data.home))
                    || (ppTo->potential != SPLIT)))
            {
                if (ppTo->potential == BACK)
                {
                    end = ppTo->sectailpoly->next;
                    while (temp != NULL && temp != end)
                    {
                        if (!temp->data.original)
                            _rpPVSDestroyPoly(&(temp->data.geom));

                        todel = temp;
                        if (*Tlist == todel)
                            *Tlist = temp->next;
                        temp = temp->next;
                        RwFree(todel);
                        todel = NULL;
                    }

                    if (prev != NULL)
                        prev->next = temp;
                    if (temp != NULL)
                        ppTo = PVSFROMWORLDSECTOR(temp->data.homeaddr);
                }
                else
                {

                    prev = ppTo->sectailpoly;

                    RWASSERT(prev != NULL);

                    temp = ppTo->sectailpoly->next;

                    if (temp != NULL)
                        ppTo = PVSFROMWORLDSECTOR(temp->data.homeaddr);
                }
            }

        }
        if (temp != NULL)
        {
            RwBool              tempisend = FALSE;

            post = temp->next;
            if (temp == ppTo->sectailpoly)
                tempisend = TRUE;

            /* Test to see if clipping is necessary.  It is necessary if... */
            if ((ClipperElement->parent != temp->data.parent) && /* temp is not be clipper */
                (!PVSPolygonTrivByVolume(&temp, ClipperElement))) /* is not be trivial.  (this processes 'in' polygons correctly) */
            {
                inList = NULL, outList = NULL, inListTail =
                    NULL, outListTail = NULL;

                PVSPolygonClipByVolume(&temp, ClipperElement, &inList,
                                        &inListTail, &outList,
                                        &outListTail, 0);
                /* else, split - orig removed */

                /* Remove things in inlist */
                ttt = inList;
                while (ttt != NULL)
                {
                    if (!ttt->data.original)
                    {
                        /* memory time waster */
                        _rpPVSDestroyPoly(&(ttt->data.geom));
                    }
                    
                    todel = ttt;
                    ttt = ttt->next;
                    RwFree(todel);
                    todel = NULL;
                }

                /* Put new (outlist) fragments onto list */

                if (prev != NULL)
                {
                    prev->next = outList;
                }
                else
                {
                    *Tlist = outList;
                }
                outListTail->next = post;
                prev = outListTail;

                /* Check jump info.... */
                if (tempisend && temp == NULL) 
                {
                    /* temp polygon was at end of 
                     * the polygon list for that sector */
                    ppTo->sectailpoly = prev; 
                    /* assign end fragment (from original) as sector tail  */
                }

            }
            else
            {
                /* Check jump info.... */
                if (tempisend && temp == NULL)
                {
                    /* temp polygon was at end of 
                     * the polygon list for that sector */
                    if (prev != NULL)
                    {
                        if (PVSFROMWORLDSECTOR(prev->data.homeaddr) == ppTo)
                        {
                            /* assign the previous cell as the end  */
                            ppTo->sectailpoly = prev; 
                        }
                        else
                        {
                            /* no more polygons in this sector! */
                            ppTo->sectailpoly = NULL; 
                        }

                    }
                    else
                    {
                        /* no more polygons in this sector 
                         * (we're at head too)! */
                        ppTo->sectailpoly = NULL; 
                    }
                }

                if (temp != NULL)
                {
                    prev = temp;
                }
                else
                {
                    if (prev != NULL)
                    {
                        prev->next = post;
                    }
                    else
                    {
                        *Tlist = post;
                    }

                }
            }
            temp = post;

        }
    }

    RWRETURNVOID();
}

static void
PVSAssignPriorities(PolyListPtr * Tlist, RwV3d * ViewPoint)
{
    RwV3d               Vec;
    RwReal              reciplarge = ((RwReal)1)/((RwReal)10000);
    RwInt32             lasthome = -1;
    RwReal              lastpriority = ((RwReal)0);
    RwReal              addpri;
    PolyListPtr         temp;

    RWFUNCTION(RWSTRING("PVSAssignPriorities"));

    temp = *Tlist;
    while (temp != NULL)       /* assign priorities to each polygon */
    {
        if (temp->data.home != lasthome)
        {
            /* Sort by sector first (make most significant) */

            RpPVS             *pvsCur =
                PVSFROMWORLDSECTOR(temp->data.homeaddr);

            if (pvsCur != rpPVSGlobals.CurrPVS)
            {
                RwV3dSub(&Vec, &pvsCur->centre, ViewPoint);
                /*Zsort - nearest z */
                temp->data.priority = RwV3dDotProduct(&Vec, &Vec); 
            }
            else
                temp->data.priority = -((RwReal)1);

            lasthome = temp->data.home;
            lastpriority = temp->data.priority;
        }
        else
        {
            /* Subsort by polygon (make least significant) */
            temp->data.priority = lastpriority;

            RwV3dSub(&Vec, &temp->data.centroid, ViewPoint);
            /*Zsort - nearest z */
            addpri = RwV3dDotProduct(&Vec, &Vec); 

            temp->data.priority += addpri / reciplarge;

        }
        temp = temp->next;

    }

    RWRETURNVOID();
}

static void
PVSAssignJumpInfo(PolyListPtr * data)
{
    PolyListPtr         temp = *data;
    RwInt32             currid;

    RWFUNCTION(RWSTRING("PVSAssignJumpInfo"));

    while (temp != NULL)
    {
        currid = temp->data.home;
        if (temp->next == NULL || temp->next->data.home != currid)
        {
            RpPVS             *pvsCur =
                PVSFROMWORLDSECTOR(temp->data.homeaddr);
            pvsCur->sectailpoly = temp;
        }
        temp = temp->next;
    }

    RWRETURNVOID();
}

static void
PVSSortList(PolyListPtr * Tlist, PolyListPtr * end)
{
    /* find last element in list */
    RwBool              sorted;
    PolyListPtr         tempa, tempb, preva, postb, last, newlast;

    RWFUNCTION(RWSTRING("PVSSortList"));

    last = *end;
    newlast = last;

    /* sort through to last position that was swapped */

    do
    {
        sorted = TRUE;
        tempa = *Tlist;
        tempb = tempa->next;
        postb = tempb->next, preva = NULL;

        while (tempa != last)
        {
            if (tempb->data.priority < tempa->data.priority)
            {
                sorted = FALSE;

                if (preva == NULL)
                {
                    (*Tlist) = tempb;
                }
                else
                {
                    preva->next = tempb;
                }
                newlast = tempa;
                preva = tempb;

                tempb->next = tempa;
                tempa->next = postb;

                tempa = tempb->next;
                tempb = tempa->next;

                if (tempa->next == NULL)
                {
                    last = tempa;
                    *end = tempa;
                }
                if (postb != NULL)
                    postb = postb->next; /* else last interation anyway */
            }
            else
            {
                preva = tempa;
                tempa = tempa->next;
                tempb = tempb->next;
                if (postb != NULL)
                    postb = postb->next; /* else last interation anyway */
            }
        }
        last = newlast;
    }
    while (!sorted);

    RWRETURNVOID();
}

static void
PVSSortSectors(PolyListPtr * Tlist)
{
    PolyListPtr         last = (PolyListPtr)NULL;
    PolyListPtr         newlast;
    PolyListPtr         nexthead;
    PolyListPtr         nexttail;
    PolyListPtr         nexttailnext;
    PolyListPtr         prevtemphead;
    PolyListPtr         temphead;
    PolyListPtr         temptail;
    RwBool              sorted;

    RWFUNCTION(RWSTRING("PVSSortSectors"));

    /* find last element in list */
    temphead = *Tlist;
    while (temphead != NULL)
    {
        temphead =
            PVSFROMWORLDSECTOR(temphead->data.homeaddr)->sectailpoly->
            next;
        if (temphead != NULL)
            last = temphead;
    }
    newlast = last;

    do
    {
        sorted = TRUE;

        prevtemphead = NULL;
        temphead = *Tlist;     /* temp points to head of list */
        while (temphead != last)
        {
            temptail =
                PVSFROMWORLDSECTOR(temphead->data.homeaddr)->
                sectailpoly;
            nexthead = temptail->next;
            if (nexthead == NULL)
                break;         /* We reached the end of swappability */
            nexttail =
                PVSFROMWORLDSECTOR(nexthead->data.homeaddr)->
                sectailpoly;
            nexttailnext = nexttail->next;

            if (nexthead->data.priority < temphead->data.priority) 
            {
                /* swap span neighbours */
                sorted = FALSE;
                if (prevtemphead == NULL)
                    (*Tlist) = nexthead;
                else
                    prevtemphead->next = nexthead;
                nexttail->next = temphead;
                temptail->next = nexttailnext;
                /* temphead=temphead; */
                prevtemphead = nexttail;
            }
            else
            {
                prevtemphead = temptail;
                temphead = nexthead;
            }
        }
        last = newlast;
    }
    while (!sorted);

    RWRETURNVOID();
}

static void
PVSSortSubSectors(PolyListPtr * Tlist)
{
    PolyListPtr         head, tail, prev = NULL, temp;

    RWFUNCTION(RWSTRING("PVSSortSubSectors"));

    head = *Tlist;
    while (head != NULL)
    {
        tail = PVSFROMWORLDSECTOR(head->data.homeaddr)->sectailpoly;

        temp = tail->next;
        tail->next = NULL;
        PVSSortList(&head, &tail);
        tail->next = temp;

        if (prev != NULL)
            prev->next = head;
        else
            *Tlist = head;

        prev = tail;
        head = tail->next;
    }

    RWRETURNVOID();
}

static void
PVSDeleteColinearsAndSlivers(PolyPtr * polygon)
{
    PolyPtr             Pnext, Pnn, todel, P, ttt;
    RwV3d               v1, v2;

    /* Now go round and delete colinears.... */
    RwInt32             top = 0;

    RWFUNCTION(RWSTRING("PVSDeleteColinearsAndSlivers"));

    P = *polygon;

    /* First rid identical polygons */
    while (P != NULL)          /* go round polygon */
    {
        Pnext = P->next;
        if (Pnext == NULL)
            Pnext = *polygon;
        Pnn = Pnext->next;
        if (Pnn == NULL)
            Pnn = *polygon;
        if (PVSVerticesEqual(P->v, Pnext->v))
        {
            /* Identical vertices */
            top = 1;
            todel = Pnext;
            if (P->next != NULL)
                P->next = Pnext->next;
            else
            {
                *polygon = Pnn;
                P = NULL;      /* we're at the end so can quit */
            }
            RwFree(todel);
            todel = NULL;

            if (top && (_rpPVSLinkCardinality2(*polygon) < 3))
            {
                /* During our efforts, we seem to have found a sliver;
                 * we shall remove it */
                ttt = *polygon;
                while (ttt != NULL)
                {
                    todel = ttt;
                    ttt = ttt->next;
                    RwFree(todel);
                    todel = NULL;
                }
                *polygon = NULL;
                return;
            }

        }
        else
            P = P->next;
    }
    top = 0;
    /* now rid colinears */
    P = *polygon;
    while (P != NULL)          /* go round polygon */
    {
        Pnext = P->next;
        if (Pnext == NULL)
            Pnext = *polygon;
        Pnn = Pnext->next;
        if (Pnn == NULL)
            Pnn = *polygon;

        RwV3dSub(&v1, &(Pnext->v), &(P->v));
        RwV3dNormalize(&v1, &v1);
        RwV3dSub(&v2, &(Pnn->v), &(Pnext->v));
        RwV3dNormalize(&v2, &v2);
        if (PVSVerticesEqual(v1, v2))
        {
            /* Same gradient and attached: 
             * Pnext is a relative colinear point and is redundant */
            top = 1;
            todel = Pnext;
            if (P->next != NULL)
                P->next = Pnext->next;
            else
            {
                *polygon = Pnn;
                P = NULL;      /* we're at the end so can quit */
            }
            RwFree(todel);
            todel = NULL;
        }
        else
            P = P->next;
    }
    if (top && (_rpPVSLinkCardinality2(*polygon) < 3))
    {
        /* During our efforts, we seem to have found a sliver;
           we shall remove it */
        ttt = *polygon;
        while (ttt != NULL)
        {
            todel = ttt;
            ttt = ttt->next;
            RwFree(todel);
            todel = NULL;
        }
        *polygon = NULL;
    }

    RWRETURNVOID();
}

/*
 * Given a polygon and a polygon, 
 * test if they can be merged into a single polygon;
 * if so, do it, put result back into polygon and
 * return true, else false
 */
static RwBool
PVSMergeGeometry2(PolyRecord * polygonA, PolyRecord * polygonB)
{
    PolyPtr             geom = NULL, pend = NULL;
    RwV3d               testpt, StartPoint;
    PolyPtr             TG, PG, T, P, temp, outer, outern, inner;
    PartitionId         refside = SPLIT, oppside = SPLIT;
    RwBool              concave;
    PlaneEq             shadowplane;
    RwInt32             switches = 0;
    RwV3d               swPoint[2];

    RWFUNCTION(RWSTRING("PVSMergeGeometry2"));

    testpt.x = polygonB->centroid.x + polygonB->plane.x;
    testpt.y = polygonB->centroid.y + polygonB->plane.y;
    testpt.z = polygonB->centroid.z + polygonB->plane.z;

    if (polygonA->translucent != polygonB->translucent)
    {
        /* polygonB and polygonA have different opacity */        
        RWRETURN(FALSE);       
    }
    

    /* to do, expand functionality to trivial... */
    if (PVSPointWRTPlane2(&testpt, &(polygonB->plane), ((RwReal)0)) !=
        PVSPointWRTPlane2(&testpt, &(polygonA->plane), ((RwReal)0)))
        RWRETURN(FALSE);
    /* polygonB not facing same way as polygonA */
    if ((!PVSPointOnPlane2
         (&(polygonB->geom->v), &(polygonA->plane), SMALL))
        ||
        (!PVSPointOnPlane2
         (&(polygonB->geom->next->v), &(polygonA->plane), SMALL))
        ||
        (!PVSPointOnPlane2
         (&(polygonB->geom->next->next->v), &(polygonA->plane), SMALL)))
        RWRETURN(FALSE);       /* polygonB not coplanar with polygonA */

    TG = polygonB->geom;
    PG = polygonA->geom;

    /* must start on a non-common vertex! */
    T = TG;
    P = PG;
    switches = 0;

    do
    {
        switches = 0;
        T = TG;
        while (T != NULL)      /* go round tri */
        {
            if ((T != P) && (PVSVerticesEqual(P->v, T->v)))
                switches = 1;
            T = T->next;
        }
        if (switches)
            P = P->next;
        if (P == NULL && switches)
            RWRETURN(FALSE);   /* identical polygons exist */
    }
    while (switches);

    StartPoint = P->v;

    do                         /* go round polygonA */
    {

        _rpPVSaddendIIp(&pend, &(P->v));
        if (geom == NULL)
            geom = pend;
        T = TG;
        while (T != NULL)      /* go round tri */
        {
            if (PVSVerticesEqual(P->v, T->v))
            {
                if (switches < 2)
                    swPoint[switches] = P->v;
                switches++;
                temp = TG;
                TG = PG;
                PG = temp;
                P = T;

                T = NULL;
            }
            else
                T = T->next;
        }
        P = P->next;
        if (P == NULL)
            P = PG;
    }
    while (!PVSVerticesEqual(P->v, StartPoint));

    if (switches != 2 || PVSVerticesEqual(swPoint[0], swPoint[1]))
    {
        _rpPVSDestroyPoly(&geom);
        RWRETURN(FALSE);
    }

    /* Check geom is not concave... */
    while (refside == SPLIT)
    {
        refside = PVSPointWRTPlane2(&testpt, &polygonB->plane, ((RwReal)0));
    }

    if (refside == FRONT)
        oppside = BACK;
    else
        oppside = FRONT;

    RWASSERT(refside != SPLIT);

    outer = geom;
    concave = FALSE;
    while (outer != NULL && !concave) /* go round polygon */
    {
        outern = outer->next;
        if (outern == NULL)
            outern = geom;
        shadowplane =
            PVSGeneratePlaneEquationFromThreePoints(&testpt,
                                                     &(outern->v),
                                                     &(outer->v));

        inner = geom;
        while (inner != NULL && !concave)
        {
            if ((inner != outer)
                &&
                (PVSPointWRTPlane2(&(inner->v), &shadowplane, SMALL))
                == oppside)
                concave = TRUE;
            inner = inner->next;
        }
        outer = outer->next;
    }

    if (!concave && _rpPVSLinkCardinality2(geom) >= 3)
    {
        _rpPVSDestroyPoly(&polygonA->geom);
        _rpPVSDestroyPoly(&polygonB->geom);

        polygonA->geom = geom;
        T = polygonA->geom;

        RWRETURN(TRUE);
    }
    else
    {
        _rpPVSDestroyPoly(&geom);
        RWRETURN(FALSE);
    }
}

static RpWorldSector *
PVSCopyAndTag(RpWorldSector * sector, void *__RWUNUSED__ data)
{
    /* Number of iterations for detesselator (done just once) */
    RwInt32             numiters = 5; 
    PolyRecord          mypoly;
    RwInt32             ply;
    PolyPtr             geom = NULL, pend = NULL;
    PolyListPtr         PolygonsEnd, TailOfLastSectorsPolys;
    RpPolygon          *rwPoly;
    RwV3d              *rwVert;
    RwInt32             numPoly, numVert;
    RwInt32             fixiters;
    RpPVS             *pvsCur = PVSFROMWORLDSECTOR(sector);
    RpPVSCache        *pvsCache =
        PVSCACHEFROMWORLD(rpPVSGlobals.World);
    PolyListPtr         temp = NULL, post = NULL, todel = NULL, prev =
        NULL;

    RWFUNCTION(RWSTRING("PVSCopyAndTag"));

    PolygonsEnd = pvsCache->polygons;
    if (PolygonsEnd != NULL)
        while (PolygonsEnd->next != NULL)
            PolygonsEnd = PolygonsEnd->next;
    TailOfLastSectorsPolys = PolygonsEnd;

    numVert = (RwInt32) (RpWorldSectorGetNumVertices(sector));
    numPoly = (RwInt32) (RpWorldSectorGetNumPolygons(sector));

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

    /* Assign the vertices */
    for (ply = 0; ply < numPoly; ply++)
    {
        RpMaterial         *mat;
        const RwRGBA       *color;
        RwTexture          *tex;
        RwInt32             matid;
        RwBool              translucent = FALSE;
        PlaneEq             myplaneeq;
        RwReal              radius;
        RwV3d               centroid, extreme;

        matid = sector->matListWindowBase + rwPoly[ply].matIndex;
        mat =
            rpMaterialListGetMaterial(&rpPVSGlobals.World->matList,
                                      matid);
        color = RpMaterialGetColor(mat);
        tex = RpMaterialGetTexture(mat);

        if (TRANSLUCENCY
            && (color->alpha < 255 || (tex && tex->mask[0])))
            translucent = TRUE;

        pend = NULL;

        _rpPVSaddendIIp(&pend, &(rwVert[rwPoly[ply].vertIndex[0]]));
        geom = pend;
        _rpPVSaddendIIp(&pend, &(rwVert[rwPoly[ply].vertIndex[1]]));
        _rpPVSaddendIIp(&pend, &(rwVert[rwPoly[ply].vertIndex[2]]));

        PVSDeleteColinearsAndSlivers(&geom);
        if (geom != NULL)
        {
            myplaneeq =
                PVSGeneratePlaneEquationFromThreePoints(&(geom->v),
                                                         &(geom->next->
                                                           v),
                                                         &(geom->next->
                                                           next->v));

            PVSFindCentroidandRadius(&geom, &centroid, &radius,
                                      &extreme);
            PVSAssignPolygonAttrs(&mypoly, geom, myplaneeq, -1, TRUE,
                                   pvsCur->sectorID, NULL, translucent,
                                   sector, FALSE, centroid, radius,
                                   extreme);

            _rpPVSaddendII(&PolygonsEnd, &mypoly);
            if (pvsCache->polygons == NULL)
                pvsCache->polygons = PolygonsEnd;

            PolygonsEnd->data.parent = PolygonsEnd;
        }
    }

    /* Detesselation... */
    for (fixiters = 0; fixiters <= numiters; fixiters++)
    {
        if (DETESS && pvsCache->polygons != NULL)
        {
            PolyListPtr         outer = NULL, innerprev = NULL, inner =
                NULL;
            PolyListPtr         todel = NULL;

            if (TailOfLastSectorsPolys != NULL)
                outer = TailOfLastSectorsPolys->next;
            else
                outer = pvsCache->polygons;

            while (outer != NULL) 
            {
                /* initially point to first polygon in current sector */
                innerprev = outer;
                inner = outer->next;
                while (inner != NULL)
                {
                    if (outer != inner
                        &&
                        (PVSMergeGeometry2
                         (&(outer->data), &(inner->data))))
                    {

                        /* outer now holds merged shape, inner is redundant */
                        todel = inner;
                        innerprev->next = inner->next;
                        RwFree(todel);
                        todel = NULL;
                        inner = innerprev->next;
                        /* innerprev=innerprev; */

                        /* reassign some attrs... */
                        PVSFindCentroidandRadius(&(outer->data.geom),
                                                  &(outer->data.
                                                    centroid),
                                                  &(outer->data.radius),
                                                  &(outer->data.
                                                    extreme));
                    }
                    else
                    {
                        inner = inner->next;
                        innerprev = innerprev->next;
                    }

                }
                outer = outer->next;
            }

            pvsCur->numpols =
                _rpPVSLinkCardinality(TailOfLastSectorsPolys);
        }
        else
        {
            pvsCur->numpols = numPoly;
        }
    }

    /* Decolinearizer... */
    if (DECOLINEAR)
    {
        if (TailOfLastSectorsPolys != NULL)
            temp = TailOfLastSectorsPolys->next;
        else
            temp = pvsCache->polygons;
        while (temp != NULL)
        {
            post = temp->next;

            PVSDeleteColinearsAndSlivers(&(temp->data.geom));
            if (temp->data.geom == NULL)
            {
                todel = temp;
                if (prev != NULL)
                    prev->next = temp->next;
                else
                    pvsCache->polygons = temp->next;
                free(todel);
                temp = post;
            }
            else
            {
                prev = temp;
                temp = post;
            }
        }
    }

    if (numPoly == 0)
        pvsCur->sectailpoly = NULL;

    RWRETURN(sector);
}
FILE* ofp;
static RpWorldSector *
PVSCopyAndTagSectors(RpWorldSector * sector, void *__RWUNUSED__ data)
{
    RpPVS             *pvsCur = PVSFROMWORLDSECTOR(sector);
    RwV3d v;
    
    RWFUNCTION(RWSTRING("PVSCopyAndTagSectors"));

    pvsCur->envelope = RpWorldSectorGetBBox(sector);
    pvsCur->centre.x =
        (pvsCur->envelope->sup.x + pvsCur->envelope->inf.x) / ((RwReal)2);
    pvsCur->centre.y =
        (pvsCur->envelope->sup.y + pvsCur->envelope->inf.y) / ((RwReal)2);
    pvsCur->centre.z =
        (pvsCur->envelope->sup.z + pvsCur->envelope->inf.z) / ((RwReal)2);

    RwV3dSub(&v, &pvsCur->envelope->sup, &pvsCur->envelope->inf);
    pvsCur->diagonal = RwV3dLength(&v);

    PVSVISMAPLENGTH(pvsCur->vismaplength,
                     rpPVSGlobals.NumWorldSectors);

    pvsCur->sampleKey=0; /* Unused field, at the moment */
    
    RWRETURN(sector);
}

static void
PVSScalePolygon(PolyRecord * t, RwReal scale)
{
    PolyPtr             temp;

    RWFUNCTION(RWSTRING("PVSScalePolygon"));

    temp = t->geom;
    while (temp != NULL)
    {
        temp->v.x =
            ((temp->v.x - t->centroid.x) * scale) + t->centroid.x;
        temp->v.y =
            ((temp->v.y - t->centroid.y) * scale) + t->centroid.y;
        temp->v.z =
            ((temp->v.z - t->centroid.z) * scale) + t->centroid.z;
        temp = temp->next;
    }

    RWRETURNVOID();
}

static void
PVSGenerateShadowPlanes(PolyRecord * poly, RwV3d * ViewPoint)
{
    RwReal              scalepercent = ((RwReal)5); 
    /* percentage increase in size of shadow caster - 
     * avoids 'cracks' and 'light escape' */
    PolyPtr             ptemp, ptempn;

    RWFUNCTION(RWSTRING("PVSGenerateShadowPlanes"));

    PVSScalePolygon(poly, ((RwReal)1) + (scalepercent / ((RwReal)100)));
    poly->hasbeenclipper = FALSE;
    ptemp = poly->geom;
    while (ptemp != NULL)      /* for each vertex */
    {
        ptempn = ptemp->next;
        if (ptempn == NULL)
            ptempn = poly->geom;
        /* non-memory time waster */
        ptemp->shadowPlane = 
            PVSGeneratePlaneEquationFromThreePoints(ViewPoint, 
                                                    &(ptemp->v), 
                                                    &(ptempn->v)); 
        ptemp = ptemp->next;
    }
    PVSScalePolygon(poly, ((RwReal)1) / (((RwReal)1) + (scalepercent / ((RwReal)100))));

    RWRETURNVOID();
}

static void
PVSWeilerAtherton(PolyListPtr * Tlist, RwV3d * ViewPoint)
{
    PolyListPtr         head, temp;

    RWFUNCTION(RWSTRING("PVSWeilerAtherton"));

    /* Before Calling WA subdivide, 
     * we can assign the shadow planes, 
     and store one in each vertex */
    temp = *Tlist;
    while (temp != NULL)       /* for each polygon */
    {
        PVSGenerateShadowPlanes(&temp->data, ViewPoint);
        temp = temp->next;
    }

    head = *Tlist;
    while (head != NULL)       /* for each polygon */
    {
        /* do PVSWeilerAtherton subdivision 
         * with head one tlist (containing all polygons) */
        if (!head->data.parent->data.hasbeenclipper
            && !head->data.parent->data.translucent)
        {
            PVSWASubdivide(&(head->data.parent->data), Tlist);
        }
        head = head->next;
    }
    rpPVSGlobals.VisibilityStack = *Tlist;

    RWRETURNVOID();
}

static void
PVSInitialize(void)
{
    RwInt32             id = 0;
    RpPVSCache        *pvsCache =
        PVSCACHEFROMWORLD(rpPVSGlobals.World);

    RWFUNCTION(RWSTRING("PVSInitialize"));

    /* Create and classify the data from each sector */
    RpWorldForAllWorldSectors(rpPVSGlobals.World, PVSCopyAndTag, &id);

    pvsCache->formatted = TRUE;

    RWRETURNVOID();
}

static void
PVSInitializeSectors(void)
{
    RwInt32             id = 0;

    RWFUNCTION(RWSTRING("PVSInitializeSectors"));

    rpPVSGlobals.NumWorldSectors = 
        RtWorldGetNumWorldSectors(rpPVSGlobals.World);

    /* Create and classify the data from each sector */
    RpWorldForAllWorldSectors(rpPVSGlobals.World,
                              PVSCopyAndTagSectors, &id);
    

    RWRETURNVOID();
}

static void
PVSDeinitialize(void)
{
    RpPVSCache        *pvsCache =
        PVSCACHEFROMWORLD(rpPVSGlobals.World);
    PolyListPtr         temp = pvsCache->polygons;

    RWFUNCTION(RWSTRING("PVSDeinitialize"));

    while (temp != NULL)
    {
        _rpPVSDestroyPoly(&(temp->data.geom));
        temp = temp->next;
    }
    _rpPVSDestroyPolyList(&pvsCache->polygons);
    pvsCache->formatted = FALSE;

    RWRETURNVOID();
}

/* 
 * Creates PVS data for a given ViewPoint and
 * assigns the new data to the current sector
 */
static void
PVSCreateViewPointPVS(RwV3d * ViewPoint, RpPVS * pvsCur)
{
    RwInt32             w;
    PolyListPtr         temp, copyList = NULL, copyListTail = NULL;
    RpPVSCache        *pvsCache =
        PVSCACHEFROMWORLD(rpPVSGlobals.World);

    RWFUNCTION(RWSTRING("PVSCreateViewPointPVS"));

    rpPVSGlobals.ViewPos.x = ViewPoint->x;
    rpPVSGlobals.ViewPos.y = ViewPoint->y;
    rpPVSGlobals.ViewPos.z = ViewPoint->z;

    /* Prioritize by sector distance and polygon distance */
    PVSAssignPriorities(&pvsCache->polygons, ViewPoint);

    /* Sort list by sector */
    PVSAssignJumpInfo(&pvsCache->polygons);
    PVSSortSectors(&pvsCache->polygons);

    /* Sort list within each sector */
    PVSAssignJumpInfo(&pvsCache->polygons);
    PVSSortSubSectors(&pvsCache->polygons);

    /* Copy data, since it will be destroyed 'en route' 
     * and we need to keep original */
    copyList = NULL;
    copyListTail = NULL;
    temp = pvsCache->polygons;
    while (temp != NULL)
    {
        _rpPVSaddendII(&copyListTail, &(temp->data));
        if (copyList == NULL)
            copyList = copyListTail;

        temp->data.hasbeenclipper = FALSE;
        temp = temp->next;

    }

    /* Remove backfaces since they are invisible - 
     * no need to cull & cannot be cullers */
    PVSRemoveBackFaces(&copyList, ViewPoint);

    PVSAssignJumpInfo(&copyList);

    /* Do the PVS using WA algorithm */
    rpPVSGlobals.VisibilityStack = NULL;
    PVSWeilerAtherton(&copyList, ViewPoint);

    /* Identify visible world sectors */
    for (w = 0; w < rpPVSGlobals.NumWorldSectors; w++)
    {
        temp = rpPVSGlobals.VisibilityStack;
        while (temp != NULL)   /* for each poly in vis list */
        {
            if (temp->data.home == w)
            {
                temp = NULL;
                PVSVISMAPSETSECTOR(pvsCur->vismap, w);
            }
            else
            {
                temp = temp->next;
            }

        }
    }

    /* Remove the FRAGMENTS on the vis list 
     * (all other frags should have been deleted) */
    temp = rpPVSGlobals.VisibilityStack;
    while (temp != NULL)       /* for each geom in vis list */
    {
        if (!temp->data.original)
            _rpPVSDestroyPoly(&(temp->data.geom));
        temp = temp->next;
    }
    _rpPVSDestroyPolyList(&rpPVSGlobals.VisibilityStack);

    RWRETURNVOID();
}

typedef struct
{
    RwReal              dist;
    RwBool              facing;
}
GridCollTri;

/*
 * 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              cosAngle;
        RwV3d               toward;

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

        /* ignore oblique faces... */
        if ( (cosAngle < ((RwReal)-0.05)) ||
             (cosAngle > ((RwReal)0.05)) ) 
        {
            colltri->facing = cosAngle < ((RwReal)0);

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

            colltri->dist = dist;
        }
    }

    RWRETURN(collPlane);
}

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

    RWFUNCTION(RWSTRING("inouttest"));

    if (radius > 100000.0)
    {
        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 * ((RwReal)2)));
    }
}

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

/**
 * \ingroup rppvs
 * \ref RpPVSGeneric
 * is the RenderWare supplied function for sampling within a world
 * sector. The samples are non-uniformly distributed in a regular 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 length of the world's bounding box.
 * 
 * The include file rppvs.h and the library file rppvs.lib are required
 * to use this function. The library file rpworld.lib is also required.
 *
 * \param sector  A pointer to the \ref RpWorldSector being sampled.
 * \param box  Unused.
 * \param pData  A pointer to private data for the sampling function.
 *
 * \return RpWorldSector if successful or NULL if there is an error.
 *
 * \see RpPVSSetWorldSectorVisibility
 * \see RpPVSCreate
 * \see RpPVSSamplePOV
 */
RpWorldSector      *
RpPVSGeneric(RpWorldSector * sector, const RwBBox __RWUNUSED__ * box,
              void *data)
{
    RwReal              xsamp, ysamp, zsamp, realysamp, realzsamp;
    RwReal              sampmin = ((RwReal)0.01);
    RwReal              sampmax = ((RwReal)0.99);
    RwReal              sampscale = sampmax - sampmin; 
    /* min/max s.t. we sample the extremes, without clipping problems */
    RwV3d               ViewPoint;
    RpPVS             *pvsCur = PVSFROMWORLDSECTOR(sector);
    RpPVSCache        *pvsCache = PVSCACHEFROMWORLD(rpPVSGlobals.World);
    RwReal              sd = *((RwReal *) data);

    RWAPIFUNCTION(RWSTRING("RpPVSGeneric"));

    for (xsamp = sampmin; xsamp <= sampmax; xsamp += sd * sampscale) 
    {
        /* For x-axis samples */
        ViewPoint.x =
            pvsCur->envelope->inf.x * xsamp +
            pvsCur->envelope->sup.x * (((RwReal)1) - xsamp);

        for (ysamp = sampmin; ysamp <= sampmax; ysamp += sd * sampscale) 
        {
            /* For y-axis samples */
            if (((RwInt32)
                 ((xsamp - sampmin) / (sd * sampscale) + SMALL)) % 2 !=
                0)
                realysamp = ((RwReal)1) - ysamp;
            else
                realysamp = ysamp;

            ViewPoint.y =
                pvsCur->envelope->inf.y * realysamp +
                pvsCur->envelope->sup.y * (((RwReal)1) - realysamp);

            for (zsamp = sampmin; zsamp <= sampmax; zsamp += sd * sampscale) 
            {
                /* For z-axis samples */
                if (((RwInt32)
                     ((ysamp - sampmin) / (sd * sampscale) +
                      SMALL)) % 2 != 0)
                    realzsamp = ((RwReal)1) - zsamp;
                else
                    realzsamp = zsamp;

                ViewPoint.z =
                    pvsCur->envelope->inf.z * realzsamp +
                    pvsCur->envelope->sup.z * (((RwReal)1) - realzsamp);

               /* set curr sector */
                RpPVSSetViewPosition(rpPVSGlobals.World, 
                                     &ViewPoint); /* changes insector */

                if (rpPVSGlobals.InSector == pvsCur->sectorID)
                {

                    RpPVSSamplePOV(&ViewPoint, TRUE);

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

                        progress =
                            (RwReal) (rpPVSGlobals.
                                      progress_count) /
                            (RwReal) (pvsCache->viscount *
                                      rpPVSGlobals.
                                      NumWorldSectors) *
                            (RwReal) ((RwReal)100);

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

                    }
                }
                        /* else the point is not in the current sector */
                rpPVSGlobals.progress_count++;
            }
        }
    }                          /* End of sampling sector */

    RWRETURN(sector);
}

/* 
 * Gets the current sector from the current viewpoint
 */
static RpWorldSector *
GetSector(RpWorldSector * sector, void *data)
{
    RpPVS             *PVSSector = PVSFROMWORLDSECTOR(sector);
    RwInt32            *index = (RwInt32 *) (data);

    RWFUNCTION(RWSTRING("GetSector"));

    if ((rpPVSGlobals.InSector == -1) || /* Set default to sector zero */
        ((rpPVSGlobals.ViewPos.x < PVSSector->envelope->sup.x &&
          rpPVSGlobals.ViewPos.x > PVSSector->envelope->inf.x) &&
         (rpPVSGlobals.ViewPos.y < PVSSector->envelope->sup.y &&
          rpPVSGlobals.ViewPos.y > PVSSector->envelope->inf.y) &&
         (rpPVSGlobals.ViewPos.z < PVSSector->envelope->sup.z &&
          rpPVSGlobals.ViewPos.z > PVSSector->envelope->inf.z)))
    {
        rpPVSGlobals.InSector = *index;
        rpPVSGlobals.CurrPVS = PVSFROMWORLDSECTOR(sector);
    }
    PVSFROMWORLDSECTOR(sector)->sectailpoly = NULL;

    (*index)++;

    RWRETURN(sector);
}

/**
 * \ingroup rppvs
 * \ref RpPVSSetViewPosition
 * is used to set the viewing position for subsequent PVS culling. It
 * selects the appropriate visibility map for PVS culling. This function
 * must be called before any render function otherwise incorrect culling
 * will occur.
 * 
 * RpPVSSetViewPosition is typically used immediately prior to a frame
 * render by setting the view position equal to that of the current
 * camera.
 * 
 * The PVS plugin must be attached before using this function.
 * 
 * The include file rppvs.h and the library file rppvs.lib are required
 * to use this function. The library file rpworld.lib is also required.
 *
 * \param wpWorld  A pointer to the RpWorld containing the PVS data.
 * \param pos  A pointer to a RwV3d which specifies 
 *             the current viewing position.
 *
 * \return RpWorld if sucessful, NULL otherwise.
 *
 * \see RpPVSAtomicVisible
 * \see RpPVSDestroy
 * \see RpPVSGetProgressCallBack
 * \see RpPVSHook
 * \see RpPVSPluginAttach
 * \see RpPVSQuery
 * \see RpPVSSetProgressCallBack
 * \see RpPVSStatisticsGet
 * \see RpPVSUnhook
 * \see RpPVSWorldSectorVisible
 */
RpWorld            *
RpPVSSetViewPosition(RpWorld * wpWorld, RwV3d * pos)
{
    RwInt32             id = 0;

    RWAPIFUNCTION(RWSTRING("RpPVSSetViewPosition"));

    rpPVSGlobals.ViewPos = *pos;
    rpPVSGlobals.InSector = -1;
    RpWorldForAllWorldSectors(wpWorld, GetSector, &id);

    RWRETURN(wpWorld);
}

/**
 * \ingroup rppvs
 * \ref RpPVSWorldSectorVisible
 * is used to determine if the sector is visible using 
 * the current visibility map.
 *
 * The include file rppvs.h and the library file rppvs.lib are
 * required to use this function. The library file rpworld.lib is also
 * required.
 *
 * \param sector  A pointer to a RpWorldSector to be determined.
 *
 * \return TRUE if visible, FALSE otherwise.
 *
 * \see RpPVSAtomicVisible
 * \see RpPVSDestroy
 * \see RpPVSGetProgressCallBack
 * \see RpPVSHook
 * \see RpPVSPluginAttach
 * \see RpPVSQuery
 * \see RpPVSSetProgressCallBack
 * \see RpPVSSetViewPosition
 * \see RpPVSStatisticsGet
 * \see RpPVSUnhook
 */
RwBool
RpPVSWorldSectorVisible(RpWorldSector * sector)
{
    RpPVS             *pvsCur = rpPVSGlobals.CurrPVS;
    RpPVS             *ppOther = PVSFROMWORLDSECTOR(sector);

    RWAPIFUNCTION(RWSTRING("RpPVSWorldSectorVisible"));

    RWRETURN(PVSVISMAPGETSECTOR(pvsCur->vismap, ppOther->sectorID));
}


/**
 * \ingroup rppvs
 * \ref RpPVSSetWorldSectorVisibility
 * is to mark the given world sector with the given Boolean value.
 *
 * The include file rppvs.h and the library file rppvs.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 RpPVSGeneric
 * \see RpPVSCreate
 * \see RpPVSSamplePOV
 */
RpWorldSector      *
RpPVSSetWorldSectorVisibility(RpWorldSector * sector, RwBool visible)
{
    RpPVS             *pvsCur = rpPVSGlobals.CurrPVS;
    RpPVS             *ppOther = PVSFROMWORLDSECTOR(sector);

    RWAPIFUNCTION(RWSTRING("RpPVSSetWorldSectorVisibility"));

    PVSVISMAPSETSECTOR(pvsCur->vismap, 
                       ppOther->sectorID); /* make sure it is set */
    if (!visible) 
    {
        PVSVISMAPUNSETSECTOR(pvsCur->vismap, 
                             ppOther->sectorID); /* set it to zero */
    }
    

    RWRETURN(sector);
}

static RpWorldSector *
_rpPVSAlloc(RpWorldSector * sect, void __RWUNUSED__ * data)
{
    RpPVS             *pvsCur = PVSFROMWORLDSECTOR(sect);
    RpPVSCache        *PVSCache =
        PVSCACHEFROMWORLD(rpPVSGlobals.World);

    RWFUNCTION(RWSTRING("_rpPVSAlloc"));

    /* assign room for vismap */
    pvsCur->sectorID = PVSCache->nextID;

    pvsCur->vismap =
        (RpPVSVisMap *) RwMalloc(pvsCur->vismaplength *
                                  sizeof(RpPVSVisMap));

    memset(pvsCur->vismap, 0,
           pvsCur->vismaplength * sizeof(RpPVSVisMap));

    PVSCache->nextID++;

    RWRETURN(sect);
}

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

    RWFUNCTION(RWSTRING("PVSDispatch"));

    world = rpPVSGlobals.World;
    pvsCur = PVSFROMWORLDSECTOR(worldSector);

    sectorBBox = pvsCur->envelope;

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

    /* Progress */
    RWRETURN(worldSector);
}

/**
 * \ingroup rppvs
 * \ref RpPVSCreate
 * is used to create 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.
 *
 * The format for RpPVSCallBack is
 *
 * RpWorldSector *(*RpPVSCallBack)
 *     (RpWorldSector * worldSector, const RwBBox * box, void *pData);
 *
 * The include file rppvs.h and the library file rppvs.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. (Unused.)
 * \param zraster  A Pointer to a RwRaster for the z-buffer. (Unused.)
 * \param mindist  A RwReal specifying the near clipping distance. (Unused.)
 * \param maxdist  A RwReal specifying the far clipping distance. (Unused.)
 * \param maxdepth  A RwInt32 specifying the division depth of the sector. (Unused.)
 * \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 RpPVSSetWorldSectorVisibility
 * \see RpPVSGeneric
 * \see RpPVSSamplePOV
 */
RpWorld            *
RpPVSCreate(RpWorld * wpWorld,
             RwRaster __RWUNUSED__ * raster,
             RwRaster __RWUNUSED__ * zraster,
             RwReal __RWUNUSED__ mindist, RwReal __RWUNUSED__ maxdist,
             __RWUNUSED__ RwInt32 maxdepth, RpPVSCallBack callback,
             void *data)
{
    RpPVSCache        *pvsCache = PVSCACHEFROMWORLD(wpWorld);
    RwBool              collData;
    _RpPVSCallBack     bundlecb;

    bundlecb.callback = callback;
    bundlecb.data = data;

    RWAPIFUNCTION(RWSTRING("RpPVSCreate"));

    rpPVSGlobals.NumWorldSectors = 0;
    rpPVSGlobals.InSector = -1;
    rpPVSGlobals.VisibilityStack = NULL;

    pvsCache->polygons = NULL;

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

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

    rpPVSGlobals.World = wpWorld;
    rpPVSGlobals.gran = *((RwReal *) data);
    pvsCache->viscount =
        (RwInt32) (((((RwReal)1) / rpPVSGlobals.gran) +
                    ((RwReal)1)) * ((((RwReal)1) / rpPVSGlobals.gran) +
                             ((RwReal)1)) * ((((RwReal)1) / rpPVSGlobals.gran) +
                                      ((RwReal)1)));
    pvsCache->nextID = 0;

    PVSInitializeSectors();

    /* assign space and clear down for a vismap for each sector */
    RpWorldForAllWorldSectors(wpWorld, _rpPVSAlloc, NULL);

    if (!pvsCache->formatted)
        PVSInitialize();      /* Put the data into PVS useable form */

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

        /* determine visibility */
        if (pvsCache->progressCallBack)
        {
            pvsCache->progressCallBack(rpPVSPROGRESSSTART, ((RwReal)0));
        }
        RpWorldForAllWorldSectors(wpWorld, PVSDispatch, &bundlecb);

        if (pvsCache->progressCallBack)
        {
            pvsCache->progressCallBack(rpPVSPROGRESSEND, ((RwReal)100));
        }

    }

    pvsCache->processed = TRUE;

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

    RWRETURN(wpWorld);
}



/**
 * \ingroup rppvs
 * \ref RpPVSSamplePOV
 * 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. RpPVSSamplePOV can be used to repair such errors by adding
 * extra samples at specific positions.
 *
 * This functions assumes PVS data is already present in a world.
 *
 * The include file rppvs.h and the library file rppvs.lib are
 * required to use this function. The library file rpworld.lib is also
 * required.
 *
 * \param pos  A pointer to a RwV3d which specifies the current viewing position.
 * \param colltest If TRUE, it only used the viewpoint if it is inside the geometry of the sector.
 *
 * \return RpWorld if successful or NULL if there is an error.
 *
 * \see RpPVSSetWorldSectorVisibility
 * \see RpPVSSamplePOV
 * \see RpPVSGeneric
 * \see RpPVSCreate
 */
void
RpPVSSamplePOV(RwV3d * pos, RwBool colltest)
{
    RpPVSCache        *pvsCache = PVSCACHEFROMWORLD(rpPVSGlobals.World);
    RpIntersection      isSphere;
    RwInt32             hitcount;


    RWAPIFUNCTION(RWSTRING("RpPVSSamplePOV"));

    if (!pvsCache->formatted)
        PVSInitialize();

    if (colltest)
    {
        isSphere.type = rpINTERSECTSPHERE;
        isSphere.t.sphere.center = *pos;
        isSphere.t.sphere.radius = ((RwReal)0.1);

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

        if (!hitcount)
        {

            if (inouttest(pos, isSphere.t.sphere.radius))
            {
                /* set curr sector */
                RpPVSSetViewPosition(rpPVSGlobals.World, pos);
                PVSCreateViewPointPVS(pos, rpPVSGlobals.CurrPVS);
            }
        }
    }
    else
    {
        /* set curr sector */
        RpPVSSetViewPosition(rpPVSGlobals.World, pos);
        PVSCreateViewPointPVS(pos, rpPVSGlobals.CurrPVS);
    }
}



static RpWorldSector *
PVSnull(RpWorldSector * sect, void *__RWUNUSED__ data)
{
    RpPVS             *PVS = PVSFROMWORLDSECTOR(sect);

    RWFUNCTION(RWSTRING("PVSnull"));

    RwFree(PVS->vismap);

    PVS->vismap = (RpPVSVisMap *) NULL;

    RWRETURN(sect);
}

/**
 * \ingroup rppvs
 * \ref RpPVSDestroy
 * is used to destroy the PVS for the given world.
 *
 * The include file rppvs.h and the library file rppvs.lib are
 * required to use this function. The library file rpworld.lib is also
 * required.
 *
 * \param wpWorld  A pointer to a RpWorld containing the PVS data.
 *
 * \return RpWorld if sucessful, NULL otherwise.
 *
 * \see RpPVSAtomicVisible
 * \see RpPVSGetProgressCallBack
 * \see RpPVSHook
 * \see RpPVSPluginAttach
 * \see RpPVSQuery
 * \see RpPVSSetProgressCallBack
 * \see RpPVSSetViewPosition
 * \see RpPVSStatisticsGet
 * \see RpPVSUnhook
 * \see RpPVSWorldSectorVisible
 */
RpWorld            *
RpPVSDestroy(RpWorld * wpWorld)
{
    RpPVSCache        *pvsCache;

    RWAPIFUNCTION(RWSTRING("RpPVSDestroy"));

    RpPVSUnhook(wpWorld);

    pvsCache = PVSCACHEFROMWORLD(wpWorld);

    PVSDeinitialize();

    if (pvsCache->processed)
    {
        RpWorldForAllWorldSectors(wpWorld, PVSnull, NULL);
        pvsCache->processed = FALSE;
    }
    rpPVSGlobals.World = (RpWorld *) NULL;

    RWRETURN(wpWorld);
}

static void *
PVSWorldConstructor(RpWorld * wpWorld,
                     RwInt32 offset __RWUNUSED__,
                     RwInt32 size  __RWUNUSED__)
{
    RpPVSCache        *pvsCache = PVSCACHEFROMWORLD(wpWorld);

    RWFUNCTION(RWSTRING("PVSWorldConstructor"));

    /* pipeline hooking */
    pvsCache->hooked = FALSE;

    /* used during vismap allocation */
    pvsCache->nextID = 0;

    pvsCache->progressCallBack = (RpPVSProgressCallBack) NULL;;

    pvsCache->ptotal = 0;
    pvsCache->paccept = 0;

    pvsCache->formatted = 0;

    pvsCache->viscount = 0;
    pvsCache->polygons = NULL;

    rpPVSGlobals.World = wpWorld;
    rpPVSGlobals.NumWorldSectors = RtWorldGetNumWorldSectors(wpWorld);

    RWRETURN(wpWorld);
}

static void *
PVSWorldDestructor(RpWorld * wpWorld,
                    RwInt32 offset __RWUNUSED__,
                    RwInt32 size  __RWUNUSED__)
{
    RWFUNCTION(RWSTRING("PVSWorldDestructor"));

    RWRETURN(wpWorld);
}

static void *
PVSSectorConstructor(RpWorldSector * sector,
                      RwInt32 offset __RWUNUSED__,
                      RwInt32 size  __RWUNUSED__)
{
    RpPVS             *pvsCur = PVSFROMWORLDSECTOR(sector);

    RWFUNCTION(RWSTRING("PVSSectorConstructor"));

    pvsCur->sectorID = ~0;
    pvsCur->sectailpoly = NULL;
    pvsCur->potential = SPLIT;
    pvsCur->sampleKey = 0;

    RWRETURN(sector);
}

static void *
PVSSectorDestructor(RpWorldSector * sector,
                     RwInt32 offset __RWUNUSED__,
                     RwInt32 size  __RWUNUSED__)
{
    RpPVS             *pvsCur = PVSFROMWORLDSECTOR(sector);

    RWFUNCTION(RWSTRING("PVSSectorDestructor"));

    pvsCur->sectorID = ~0;

    RWRETURN(sector);
}

/**
 * \ingroup rppvs
 * \ref RpPVSHook is used to enable rendering of the specified world
 * using the world's PVS data.  Typically used prior to a frame render
 * (and followed afterwards by \ref RpPVSUnhook) but may be permanently
 * enabled if PVS rendering is always required.  If \ref RpPVSHook is not used
 * all world sectors in the current camera's view frustum are rendered.
 * 
 * Note that this function overrides the world sector render callback
 * which is only returned to its original form when \ref RpPVSUnhook is
 * called.
 * 
 * The PVS plugin must be attached before using this function.
 * 
 * The include file rppvs.h and the library file rppvs.lib are required
 * to use this function. The library file rpworld.lib is also required.
 *
 * \param wpWorld  A pointer to a RpWorld with PVS data.
 *
 * \return RpWorld if sucessful, NULL otherwise.
 *
 * \see RpPVSAtomicVisible
 * \see RpPVSDestroy
 * \see RpPVSGetProgressCallBack
 * \see RpPVSPluginAttach
 * \see RpPVSQuery
 * \see RpPVSSetProgressCallBack
 * \see RpPVSSetViewPosition
 * \see RpPVSStatisticsGet
 * \see RpPVSUnhook
 * \see RpPVSWorldSectorVisible
 */
RpWorld            *
RpPVSHook(RpWorld * wpWorld)
{
    RpPVSCache        *pvsCache = PVSCACHEFROMWORLD(wpWorld);

    RWAPIFUNCTION(RWSTRING("RpPVSHook"));
    RWASSERT(wpWorld);

    if (pvsCache->processed)
    {
        if (!pvsCache->hooked)
        {
            pvsCache->hooked = TRUE;
            rpPVSGlobals.World = wpWorld;
        }
    }

    RWRETURN(wpWorld);
}

/**
 * \ingroup rppvs
 * \ref RpPVSUnhook is used to disable rendering of the
 * specified world using the world's PVS data.  Typically used just after
 * to a frame render (which followed a call to \ref RpPVSHook) but may be
 * permanently disabled if PVS rendering is not required.
 * 
 * Note that the function \ref RpPVSHook overrides the world sector
 * render callback which is only returned to its original form when
 * RpPVSUnhook is called.  The PVS plugin must be attached before using
 * this function.
 * 
 * The include file rppvs.h and the library file rppvs.lib are required
 * to use this function. The library file rpworld.lib is also required.
 *
 * \param wpWorld  A pointer to a RpWorld containing PVS data.
 *
 * \return RpWorld if sucessful, NULL otherwise.
 *
 * \see RpPVSAtomicVisible
 * \see RpPVSDestroy
 * \see RpPVSGetProgressCallBack
 * \see RpPVSHook
 * \see RpPVSPluginAttach
 * \see RpPVSQuery
 * \see RpPVSSetProgressCallBack
 * \see RpPVSSetViewPosition
 * \see RpPVSStatisticsGet
 * \see RpPVSWorldSectorVisible
 */
RpWorld            *
RpPVSUnhook(RpWorld * wpWorld)
{
    RpPVSCache        *pvsCache = PVSCACHEFROMWORLD(wpWorld);

    RWAPIFUNCTION(RWSTRING("RpPVSUnhook"));

    if (pvsCache->hooked)
    {
        pvsCache->hooked = FALSE;
        rpPVSGlobals.World = (RpWorld *) NULL;
    }

    RWRETURN(wpWorld);
}

/**
 * \ingroup rppvs
 * \ref RpPVSGetProgressCallBack is used to retrieve PVS creation
 * progress callback function of the specified world.  The callback is
 * called from \ref RpPVSGeneric every time it has processed a single
 * world sector, enabling an application to monitor how the generation of
 * PVS data is progressing and, possibly, to provide feedback to the
 * user.
 * 
 * The format of the callback function is:
 * 
 * \verbatim
   RwBool (*RpPVSProgressCallBack) (RwInt32 message, RwReal value);

   where message is one of the following:

   rpPVSPROGRESSSTART
   The PVS creation process is about to start.  The argument value is equal to 0.0.

   rpPVSPROGRESSUPDATE
   The PVS creation process has finished processing a subsection of the world.
   The argument value is equal to the percentage of the world processed up to this point.

   rpPVSPROGRESSEND
   The PVS creation process has ended.  All world sectors have been processed.
   The argument value is equal to 100.0.

   The progress callback may return FALSE to indicate that the generation of PVS data
   should terminate. Otherwise, return TRUE to continue.

   The PVS plugin must be attached before using this function.
   \endverbatim
 *
 * \param world  A pointer to a RpWorld.
 *
 * \return The RpPVSProgressCallBack function if sucessful, NULL otherwise.
 *
 * \see RpPVSAtomicVisible
 * \see RpPVSDestroy
 * \see RpPVSHook
 * \see RpPVSPluginAttach
 * \see RpPVSQuery
 * \see RpPVSSetProgressCallBack
 * \see RpPVSSetViewPosition
 * \see RpPVSStatisticsGet
 * \see RpPVSUnhook
 * \see RpPVSWorldSectorVisible
 */
RpPVSProgressCallBack
RpPVSGetProgressCallBack(RpWorld * world)
{
    RpPVSCache        *pvsCache = PVSCACHEFROMWORLD(world);

    RWAPIFUNCTION(RWSTRING("RpPVSGetProgressCallBack"));
    RWASSERT(world);

    if (world)
    {
        RWRETURN(pvsCache->progressCallBack);

        RWERROR((E_RW_NULLP));
        RWRETURN((RpPVSProgressCallBack) NULL);
    }

    RWERROR((E_RW_NULLP));
    RWRETURN((RpPVSProgressCallBack) NULL);
}

/**
 * \ingroup rppvs
 * \ref RpPVSSetProgressCallBack is used to define a PVS creation
 * progress callback function for the specified world.  The callback is
 * called from \ref RpPVSGeneric every time it has processed a single
 * world sector, enabling an application to monitor how the generation of
 * PVS data is progressing and, possibly, to provide feedback to the
 * user.
 * 
 * The format of the callback function is:
 * \verbatim
   RwBool (*RpPVSProgressCallBack) (RwInt32 message, RwReal value);

   where message is one of the following:

   rpPVSPROGRESSSTART
   The PVS creation process is about to start. The argument value is equal to 0.0.

   rpPVSPROGRESSUPDATE
   The PVS creation process has finished processing a subsection of the world.
   The argument value is equal to the percentage of the world processed up to this point.

   rpPVSPROGRESSEND
   The PVS creation process has ended.  All world sectors have been processed.
   The argument value is equal to 100.0.

   The progress callback may return FALSE to indicate that the generation of
   PVS data should terminate.  Otherwise, return TRUE to continue.

   The PVS plugin must be attached before using this function.
   \endverbatim
 *
 * \param world  A pointer to a RpWorld.
 * \param callback  A pointer to the RpPVSProgressCallBack function.
 *
 * \return RpWorld if sucessful, NULL otherwise.
 *
 * \see RpPVSAtomicVisible
 * \see RpPVSDestroy
 * \see RpPVSGetProgressCallBack
 * \see RpPVSHook
 * \see RpPVSPluginAttach
 * \see RpPVSQuery
 * \see RpPVSSetViewPosition
 * \see RpPVSStatisticsGet
 * \see RpPVSUnhook
 * \see RpPVSWorldSectorVisible
 */
RpWorld            *
RpPVSSetProgressCallBack(RpWorld * world,
                          RpPVSProgressCallBack callback)
{
    RpPVSCache        *pvsCache = PVSCACHEFROMWORLD(world);

    RWAPIFUNCTION(RWSTRING("RpPVSSetProgressCallBack"));
    RWASSERT(world);

    if (world)
    {
        if (pvsCache)
        {
            pvsCache->progressCallBack = callback;
            RWRETURN(world);
        }

        RWERROR((E_RW_NULLP));
        RWRETURN((RpWorld *) NULL);
    }

    RWERROR((E_RW_NULLP));
    RWRETURN((RpWorld *) NULL);
}

/* Serialization for the sectors...*/
static RwInt32
PVSSectorGetChunkSize(const RpWorldSector * spSect,
                       RwInt32 offset __RWUNUSED__,
                       RwInt32 size  __RWUNUSED__)
{
    RwInt32             len;
    const RpPVS       *pvsCur = PVSFROMCONSTWORLDSECTOR(spSect);

    RWFUNCTION(RWSTRING("PVSSectorGetChunkSize"));

    len =  ( sizeof(pvsCur->sectorID) + 
             sizeof(pvsCur->vismaplength) + 
             sizeof(pvsCur->sampleKey) + 
             pvsCur->vismaplength * /* Plus the single vismap */
             sizeof(RpPVSVisMap) );

    RWRETURN(len);

}

static RwStream *
PVSSectorWriteChunk(RwStream * s,
                     RwInt32 len __RWUNUSED__,
                     const RpWorldSector * spSect,
                     RwInt32 offset  __RWUNUSED__,
                     RwInt32 size __RWUNUSED__)
{
    const RpPVS       *pvsCur = PVSFROMCONSTWORLDSECTOR(spSect);

    RWFUNCTION(RWSTRING("PVSSectorWriteChunk"));
    /* sector's data.... */

    RwStreamWriteInt32(s, &pvsCur->sectorID, sizeof(pvsCur->sectorID));

    RwStreamWriteInt32(s, &pvsCur->vismaplength,
                       sizeof(pvsCur->vismaplength));

    RwStreamWriteInt32(s, &pvsCur->sampleKey,
                       sizeof(pvsCur->sampleKey));

    /* and the vismap.... */
    RwStreamWrite(s, pvsCur->vismap,
                  pvsCur->vismaplength * sizeof(RpPVSVisMap));

    RWRETURN(s);
}

static RwStream *
PVSSectorReadChunk(RwStream * s,
                    RwInt32 len __RWUNUSED__,
                    RpWorldSector * spSect,
                    RwInt32 offset  __RWUNUSED__,
                    RwInt32 size  __RWUNUSED__)
{
    RpPVS             *pvsCur = PVSFROMWORLDSECTOR(spSect);

    RWFUNCTION(RWSTRING("PVSSectorReadChunk"));

    /* sector's data.... */
    RwStreamReadInt32(s, &pvsCur->sectorID, sizeof(pvsCur->sectorID));
    RwStreamReadInt32(s, &pvsCur->vismaplength,
                      sizeof(pvsCur->vismaplength));
    RwStreamReadInt32(s, &pvsCur->sampleKey,
                      sizeof(pvsCur->sampleKey));

    /* allocate space */
    pvsCur->vismap = (RpPVSVisMap *)
        RwMalloc(pvsCur->vismaplength * sizeof(RpPVSVisMap));

    /* read the vismap... */
    RwStreamRead(s, pvsCur->vismap,
                 pvsCur->vismaplength * sizeof(RpPVSVisMap));

    RWRETURN(s);
}

/* Serialization for the world (cache)...*/
static RwInt32
PVSWorldGetChunkSize(const RpWorld * wpWorld,
                      RwInt32 offset __RWUNUSED__,
                      RwInt32 size  __RWUNUSED__)
{
    const RpPVSCache  *pvsCache = PVSCACHEFROMCONSTWORLD(wpWorld);

    RWFUNCTION(RWSTRING("PVSWorldGetChunkSize"));

    RWRETURN(sizeof(pvsCache->processed) + sizeof(pvsCache->hooked));
}

static RwStream *
PVSWorldWriteChunk(RwStream * s,
                    RwInt32 len __RWUNUSED__,
                    RpWorld * wpWorld,
                    RwInt32 offset __RWUNUSED__,
                    RwInt32 size  __RWUNUSED__)
{
    const RpPVSCache  *pvsCache = PVSCACHEFROMCONSTWORLD(wpWorld);

    RWFUNCTION(RWSTRING("PVSWorldWriteChunk"));

    /* set current world */
    rpPVSGlobals.World = (RpWorld *) wpWorld;

    RwStreamWriteInt32(s, &pvsCache->processed,
                       sizeof(pvsCache->processed));
    RwStreamWriteInt32(s, &pvsCache->hooked, sizeof(pvsCache->hooked));

    RWRETURN(s);
}

static RwStream *
PVSWorldReadChunk(RwStream * s,
                   RwInt32 len __RWUNUSED__,
                   RpWorld * wpWorld,
                   RwInt32 offset __RWUNUSED__ ,
                   RwInt32 size __RWUNUSED__)
{
    RpPVSCache   *pvsCache = PVSCACHEFROMWORLD(wpWorld);

    RWFUNCTION(RWSTRING("PVSWorldReadChunk"));

    RwStreamReadInt32(s, &pvsCache->processed, sizeof(pvsCache->processed));
    RwStreamReadInt32(s, &pvsCache->hooked, sizeof(pvsCache->hooked));

    PVSInitializeSectors();

    RWRETURN(s);
}

/**
 * \ingroup rppvs 
 * \ref RpPVSPluginAttach is used to attach the PVS
 * plugin to the RenderWare system to enable the building and use of
 * potentially visible sets.  The PVS plugin must be attached between
 * initializing the system with \ref RwEngineInit and opening it with
 * \ref RwEngineOpen.
 * 
 * Note that the PVS plugin requires the world plugin to be attached.
 * 
 * The include file rppvs.h is also required and must be included by an
 * application wishing to use PVS.  Note also that when linking the PVS
 * plugin library, rppvs.lib, into an application, make sure the
 * following RenderWare libraries are made available to the linker:
 * rtray.lib and rtworld.lib.
 * 
 * \return TRUE if successful or FALSE if there is an error.
 *
 * \see RpPVSAtomicVisible
 * \see RpPVSDestroy
 * \see RpPVSGetProgressCallBack
 * \see RpPVSHook
 * \see RpPVSQuery
 * \see RpPVSSetProgressCallBack
 * \see RpPVSSetViewPosition
 * \see RpPVSStatisticsGet
 * \see RpPVSUnhook
 * \see RpPVSWorldSectorVisible
 * \see RpWorldPluginAttach
 * \see RwEngineInit
 * \see RwEngineOpen
 * \see RwEngineStart
 */
RwBool
RpPVSPluginAttach(void)
{
    /* Note the plugin id is should be rwID_GPVSPLUGIN to avoid
     * problems with the retired PVS plugin */
    
    RwInt32             offset;

    RWAPIFUNCTION(RWSTRING("RpPVSPluginAttach"));

    rpPVSGlobals.World = (RpWorld *) NULL;

    rpPVSGlobals.worldOffset =
        RpWorldRegisterPlugin(sizeof(RpPVSCache),
                              rwID_GPVSPLUGIN,
                              (RwPluginObjectConstructor)
                              PVSWorldConstructor,
                              (RwPluginObjectDestructor)
                              PVSWorldDestructor,
                              (RwPluginObjectCopy) NULL);
    if (rpPVSGlobals.worldOffset < 0)
    {
        RWRETURN(FALSE);
    }

    offset =
        RpWorldRegisterPluginStream(rwID_GPVSPLUGIN,
                                    (RwPluginDataChunkReadCallBack)
                                    PVSWorldReadChunk,
                                    (RwPluginDataChunkWriteCallBack)
                                    PVSWorldWriteChunk,
                                    (RwPluginDataChunkGetSizeCallBack)
                                    PVSWorldGetChunkSize);

    if (offset < 0)
    {
        RWRETURN(FALSE);
    }

    rpPVSGlobals.sectorOffset =
        RpWorldSectorRegisterPlugin(sizeof(RpPVS),
                                    rwID_GPVSPLUGIN,
                                    (RwPluginObjectConstructor)
                                    PVSSectorConstructor,
                                    (RwPluginObjectDestructor)
                                    PVSSectorDestructor,
                                    (RwPluginObjectCopy) NULL);
    if (rpPVSGlobals.sectorOffset < 0)
    {
        RWRETURN(FALSE);
    }

    offset =
        RpWorldSectorRegisterPluginStream(rwID_GPVSPLUGIN,
                                          (RwPluginDataChunkReadCallBack)
                                          PVSSectorReadChunk,
                                          (RwPluginDataChunkWriteCallBack)
                                          PVSSectorWriteChunk,
                                          (RwPluginDataChunkGetSizeCallBack)
                                          PVSSectorGetChunkSize);

    if (offset < 0)
    {
        RWRETURN(FALSE);
    }

    RWRETURN(TRUE);
}

/**
 * \ingroup rppvs
 * \ref RpPVSQuery is used to determine whether the specified world
 * contains PVS data, that is, if it has already been processed using
 * \ref RpPVSCreate.
 *
 * The PVS plugin must be attached before using this function.
 *
 * The include file rppvs.h and the library file rppvs.lib are
 * required to use this function. The library file rpworld.lib is also
 * required.
 *
 * \param wpWorld  A pointer to a RpWorld to be queried.
 *
 * \return TRUE if PVS data is present, FALSE otherwise.
 *
 * \see RpPVSAtomicVisible
 * \see RpPVSDestroy
 * \see RpPVSGetProgressCallBack
 * \see RpPVSHook
 * \see RpPVSPluginAttach
 * \see RpPVSSetProgressCallBack
 * \see RpPVSSetViewPosition
 * \see RpPVSStatisticsGet
 * \see RpPVSUnhook
 * \see RpPVSWorldSectorVisible
 */
RwBool
RpPVSQuery(RpWorld * world)
{
    RpPVSCache        *pvsCache = PVSCACHEFROMWORLD(world);

    RWAPIFUNCTION(RWSTRING("RpPVSQuery"));

    rpPVSGlobals.World = world;
    RWRETURN(pvsCache->processed);
}

static RpWorldSector *
PVSSectorVis(RpWorldSector * sector, void *data)
{
    RwBool             *isvisible = (RwBool *) data;

    RWFUNCTION(RWSTRING("PVSSectorVis"));

    if (RpPVSWorldSectorVisible(sector))
    {
        (*isvisible) = TRUE;
    }

    RWRETURN(sector);
}

/**
 * \ingroup rppvs
 * \ref RpPVSAtomicVisible
 * is used to determine if the atomic is visible from the current visibility
 * map.
 *
 * The include file rppvs.h and the library file rppvs.lib are
 * required to use this function. The library file rpworld.lib is also
 * required.
 *
 * \param atom  A pointer to a RpAtomic.
 *
 * \return TRUE if visible, FALSE otherwise.
 *
 * \see RpPVSDestroy
 * \see RpPVSGetProgressCallBack
 * \see RpPVSHook
 * \see RpPVSPluginAttach
 * \see RpPVSQuery
 * \see RpPVSSetProgressCallBack
 * \see RpPVSSetViewPosition
 * \see RpPVSStatisticsGet
 * \see RpPVSUnhook
 * \see RpPVSWorldSectorVisible
 */
RwBool
RpPVSAtomicVisible(RpAtomic * atom)
{
    RwBool              isvisible;

    RWAPIFUNCTION(RWSTRING("RpPVSAtomicVisible"));

    isvisible = FALSE;
    RpAtomicForAllWorldSectors(atom, PVSSectorVis, &isvisible);
    RWRETURN(isvisible);
}

/**
 * \ingroup rppvs
 * \ref RpPVSStatisticsGet is used to retrieve statistics relating to the
 * rendering perfomance of the PVS data in the specified world.  The figures
 * obtained from this function are:
 * (a) the total number of triangles that would have been rendered if PVS data
 *     was not used, and
 * (b) the total number of triangles that have been rendered using the PVS data.
 * Typically used immediately after a frame render.
 *
 * The PVS plugin must be attached before using this function.
 *
 * \param wpWorld  A pointer to a RpWorld with PVS data.
 * \param ptotal  A pointer to a RwInt32 to return number of polygons before PVS culling.
 * \param paccept  A pointer to a RwInt32 to return number of polygons after PVS culling.
 *
 * \return RpWorld if sucessful, NULL otherwise.
 *
 * \see RpPVSAtomicVisible
 * \see RpPVSDestroy
 * \see RpPVSGetProgressCallBack
 * \see RpPVSHook
 * \see RpPVSPluginAttach
 * \see RpPVSQuery
 * \see RpPVSSetProgressCallBack
 * \see RpPVSSetViewPosition
 * \see RpPVSUnhook
 * \see RpPVSWorldSectorVisible
 */
RpWorld            *
RpPVSStatisticsGet(RpWorld * wpWorld, RwInt32 * ptotal,
                    RwInt32 * paccept)
{
    RpPVSCache        *pvsCache = PVSCACHEFROMWORLD(wpWorld);

    RWAPIFUNCTION(RWSTRING("RpPVSStatisticsGet"));

    RWASSERT(wpWorld);
    RWASSERT(ptotal);
    RWASSERT(paccept);

    rpPVSGlobals.World = wpWorld;

    /* read tally.. */
    *ptotal = pvsCache->ptotal;
    *paccept = pvsCache->paccept;

    /* and zero them */
    pvsCache->ptotal = 0;
    pvsCache->paccept = 0;

    RWRETURN(wpWorld);
}

/****************************************************************************
 local defines
 */

#define NUMCLUSTERSOFINTEREST                   1
#define NUMOUTPUTS                              1

#define MESSAGE(_string)                                            \
    RwDebugSendMessage(rwDEBUGMESSAGE, "PVSWorldSectorCSL", _string)

 
 /****************************************************************************
 local (static) prototypes
 */
static              RwInt32
PVSWorldSectorNodeFn(RxPipelineNodeInstance * __RWUNUSED__ self,
                     const RxPipelineNodeParam * params)
{
    RwBool              visible;
    RpPVSCache         *pvsCache;
    RpPVS              *pvs;
    RpWorldSector      *worldSector;
    RpWorld            *world;

    RWFUNCTION(RWSTRING("PVSWorldSectorNodeFn"));

    RWASSERT(NULL != self);

    worldSector = (RpWorldSector *) RxPipelineNodeParamGetData(params);
    RWASSERT(NULL != worldSector);

    world = rpPVSGlobals.World;

    pvs = PVSFROMWORLDSECTOR(worldSector);
    RWASSERT(NULL != pvs);
    pvsCache = PVSCACHEFROMWORLD(world);
    RWASSERT(NULL != pvsCache);

    /* Don't reject empty sectors since they may contain visible atomics. */

    visible = TRUE;

    if ((worldSector->numPolygons > 0) &&
        (NULL != pvs->vismap))
    {
        RwInt32             sectorID = pvs->sectorID;

        pvsCache->ptotal += worldSector->numPolygons;

        if (PVSVISMAPGETSECTOR(pvs->vismap, sectorID))
        {
            visible = TRUE;
        }
        else
        {
            visible = FALSE;
        }
    }

    if (visible)
    {
        pvsCache->paccept += worldSector->numPolygons;

        /* Make the rest of the pipe execute */
        RxPacketDispatch(NULL, 0, self);
    }

    /* If we're not visible, we didn't dispatch, so the pipe will unwind
     * (without error) without going beyond this point */
    RWRETURN(TRUE);
}

/**
 * \ingroup rppvs
 * \ref RxNodeDefinitionGetPVSWorldSectorCSL
 * returns a pointer to a node implementing PVS culling in custom pipelines.
 *
 * This nodes removes world sectors from rendering if they are culled by the
 * PVS visilibility map.
 *
 * This node is to be used as early as possible and before the world sector
 * instance nodes. If a world sector is visible, execution continues to
 * the next node otherwise the pipeline is stop at this point.
 *
 * \verbatim
   The node has one outputs.
   The input requirements of this node:

   N/A.

   The characteristics of this node's outputs:

   N/A.
   \endverbatim
 *
 * \return pointer to node for PVS  culling in custom pipelines on success,
 * NULL otherwise
 *
 */
RxNodeDefinition   *
RxNodeDefinitionGetPVSWorldSectorCSL(void)
{
    static RwChar       _PVSData_csl[] = RWSTRING("PVSData.csl");

    static RxClusterDefinition clusterPVSData =
        { _PVSData_csl,
          0,
          0,
          (const RwChar *)NULL };

    /* TODO: can you not have nodes without any clusters of interest?
     *       This cluster is entirely useless... */
    static RxClusterRef gPVSNodeClusters[NUMCLUSTERSOFINTEREST] = {
        {&clusterPVSData, rxCLALLOWABSENT, rxCLRESERVED}
    };

    static RxClusterValidityReq gPVSNodeReqs[NUMCLUSTERSOFINTEREST] = {
        rxCLREQ_DONTWANT,
    };

    static RxClusterValid gPVSNodeValid[NUMCLUSTERSOFINTEREST] = {
        rxCLVALID_VALID,
    };

    static RwChar       _Output[] = RWSTRING("Output");

    static RxOutputSpec gPVSNodeOutputs[NUMOUTPUTS] = {
        {_Output, gPVSNodeValid, rxCLVALID_INVALID}
    };

    static RwChar       _PVSWorldSector_csl[] =
        RWSTRING("PVSWorldSector.csl");

    static RxNodeDefinition nodePVSWorldSectorCSL = { /* */
        _PVSWorldSector_csl,    /* Name */
        {                      /* nodemethods */
         PVSWorldSectorNodeFn, /* +-- nodebody */
         (RxNodeInitFn)NULL,
         (RxNodeTermFn)NULL,
         (RxPipelineNodeInitFn)NULL,
         (RxPipelineNodeTermFn)NULL,
         (RxPipelineNodeConfigFn)NULL,
         (RxConfigMsgHandlerFn)NULL },
        {                      /* Io */
         NUMCLUSTERSOFINTEREST, /* +-- NumClustersOfInterest */
         gPVSNodeClusters,     /* +-- ClustersOfInterest */
         gPVSNodeReqs,         /* +-- InputRequirements */
         NUMOUTPUTS,           /* +-- NumOutputs */
         gPVSNodeOutputs       /* +-- Outputs */
         },
        0,
        (RxNodeDefEditable)FALSE,
        0
    };

    RxNodeDefinition   *result = &nodePVSWorldSectorCSL;

    RWAPIFUNCTION(RWSTRING("RxNodeDefinitionGetPVSWorldSectorCSL"));

    /*RWMESSAGE((RWSTRING("Pipeline II node"))); */

    RWRETURN(result);
}
