/*
 *  The world structure is an Axis aligned BSP tree - essentially
 *  a median K-D tree.
 *  It is constructed automatically from the TkWorldImport structure.
 *  It is also a 'compressed' format such that the world storage is
 *  approximately 10th of the normal size.
 *
 * See
 *     http://www.cs.sunysb.edu/~algorith/files/kd-trees.shtml
 * and
 *
 *    * Naive k-d -- the original kd-tree defined by Bentley,
 *      "Multidimensional Binary Search Trees Used for Associative Searching"
 *      ACM Sept. 1975 Vol. 18. No. 9
 *    * Median k-d -- A refined kd-tree, using median cuts and bucketing,
 *      discussed in J.H. Friedman, J.L. Bentley, R.A. Finkel "An Algorithm
 *      for Finding Best Matches in Logarithmic Expected Time" ACM
 *      Transactions of Mathematical Software Vol 3 No. 3 Sept. 1977 pp.
 *      209-226
 *    * Sproull k-d -- Sproull's variant of the kd-tree. The choice of
 *      partition plane is not orthogonal, rather, it is selected by the
 *      principal eigenvector of the covariance matrix of the points. R.F.
 *      Sproull "Refinements to Nearest-Neighbor Searching in k-Dimensional
 *      Trees" J. Algorithmica 1990. pp. 579-589
 *    * VP-tree - The vantage point tree is a data structure that chooses
 *      vantage points to perform a spherical decomposition of the search
 *      space. Yianilos claims this method is suited for non-Minkowski metrics
 *      (unlike kd-trees) and for lower dimensional objects embedded in a
 *      higher dimensional space. P.N. Yianilos "Data Structures and
 *      Algorithms for Nearest Neighbor Search in General Metric Spaces" SODA
 *      '93
 *
 */

/*  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 * Splitting code - essentially a K-D tree partition
 */

/****************************************************************************
 Includes
 */

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

#include "rwcore.h"
#include "rpworld.h"

#include "rpdbgerr.h"

#include "nhsstats.h"
#include "nhsutil.h"
#include "nhsworld.h"
#include "nhscond.h"
#include "nhswing.h"

#include "nhssplit.h"

#if (!defined(DOXYGEN))
static const char __RWUNUSED__ rcsid[] =
    "@@@@(#)$Id: nhssplit.c,v 1.19 2001/08/29 14:07:44 Markj Exp $";
#endif /* (!defined(DOXYGEN)) */

/* Splitting up the world */
typedef struct _rwCut _rwCut;
struct _rwCut
{
    RwLLLink            lAll;
    RtWorldImportVertex *v1, *v2;
    RwReal              delta;
    RtWorldImportVertex vInterp;
};

typedef struct _rwCutVertex _rwCutVertex;
struct _rwCutVertex
{
    RtWorldImportVertex vpVert;
    RwInt32             plane;
    RwReal              value;
};

/* In splitting the world we weight on how much [in units of vertices]
 * it costs to process higher level structures.
 * Tweak these to reflect approximate costs on platforms.
 * eg MESHCOST reflects how many vertices we could have processed in the
 * time it takes to begin a new Mesh.
 */

#define MESHCOST        100
#define SECTORCOST      400

#if (defined(_WINDOWS))
#define RWCDECL __cdecl
#endif /* (defined(_WINDOWS)) */

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

#if (!defined(SPLIT_EPSILON))
#define SPLIT_EPSILON (((RwReal)1)/((RwReal)(1<<10)))
#endif /* (!defined(SPLIT_EPSILON)) */

#define EQ(a,b) (a - b < SPLIT_EPSILON && a - b > -SPLIT_EPSILON)

#define _rwSListGetNumEntriesMacro(_sList)     \
    ((_sList)->numElementsFilled)

#define CLIPV3D(out, in1, in2, t)               \
    MACRO_START                                 \
    {                                           \
        RwV3dSub((out), (in2), (in1));          \
        RwV3dScale((out), (out), (t));          \
        RwV3dAdd((out), (out), (in1));          \
    }                                           \
    MACRO_STOP

/* Clipping */
#define CLIPREAL(out, in1, in2, t)              \
    (out) = (((in2) - (in1)) * (t)) + (in1);

#define CLIPCOLOR(out, in1, in2, t)                     \
    MACRO_START                                         \
    {                                                   \
        RwRGBAReal       clippedCol, inpA;              \
                                                        \
        RwRGBARealFromRwRGBA(&inpA, (in1));             \
        RwRGBARealFromRwRGBA(&clippedCol, (in2));       \
        RwRGBARealSub(&clippedCol, &clippedCol, &inpA); \
        RwRGBARealScale(&clippedCol, &clippedCol, (t)); \
        RwRGBARealAdd(&clippedCol, &clippedCol, &inpA); \
        RwRGBAFromRwRGBAReal((out), &clippedCol);       \
    }                                                   \
    MACRO_STOP

/* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

   Fuzzy rules for splitting the world

   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */

/****************************************************************************
 FuzzyWorldExtent

 On entry   : Extent
            : MaxExtent
 On exit    : Value between 0 and 1

 |      *******
 |    **
 |  **
 |**
 |
 |
 --------------
0.0    0.5    1.0

 */

#define FuzzyWorldExtentMacro(_result, _extent, _maxExtent)     \
MACRO_START                                                     \
{                                                               \
    (_result) = (_extent) / (_maxExtent);                       \
    (_result) = ( ((_result) > 0.6f) ?                          \
                  (1.0f):                                       \
                  /* bias against cutting small extent */       \
                  ( 0.5f + (_result / 0.6f) * (1.0f-0.6f)) );   \
}                                                               \
MACRO_STOP

#define BuildSectorSetWorldClipCodes(buildSector, plane, value)         \
MACRO_START                                                             \
{                                                                       \
    RwInt32             nI;                                             \
                                                                        \
    for (nI = 0; nI < buildSector->numVertices; nI++)                   \
    {                                                                   \
        RtWorldImportVertex *const vpVert = &buildSector->vertices[nI]; \
        const RwReal test = GETCOORD(vpVert->OC, plane) - value;        \
                                                                        \
        vpVert->state.clipFlags = 0;                                    \
                                                                        \
        /*                                                              \
         *  NOTE: if the vertex is within the plane it                  \
         *  will be classifed as being on both sides of the plane,      \
         *  this is intentional.                                        \
         */                                                             \
        if (test <= 0.0f)                                               \
        {                                                               \
            vpVert->state.clipFlags |= rwCLIPVERTEXLEFT;                \
        }                                                               \
                                                                        \
        if (test >= 0.0f)                                               \
        {                                                               \
            vpVert->state.clipFlags |= rwCLIPVERTEXRIGHT;               \
        }                                                               \
    }                                                                   \
}                                                                       \
MACRO_STOP

static              RwBool
ImportBuildSectorAccept(RtWorldImportBuildSector * buildSector,
                        RtWorldImportParameters * conversionParams)
{
    RwV3d               vSize;

    RWFUNCTION(RWSTRING("ImportBuildSectorAccept"));

    /* 65536 vertices imposed by the RwUInt16 index in polygons */
    if (buildSector->numVertices > 65536)
    {
        RWRETURN(FALSE);
    }

    /* In the ballpark for max triangles imposed
     * by the conversion parameters */
    if (buildSector->numPolygons >
        conversionParams->maxWorldSectorPolygons)
    {
        RWRETURN(FALSE);
    }

    /* Ok, so do an accurate test of number of triangles (after fanning) */
    if (_rtImportBuildSectorFindNumTriangles(buildSector) >
        conversionParams->maxWorldSectorPolygons)
    {
        RWRETURN(FALSE);
    }

    /* Worldspace size imposed by the conversion parameters */
    RwV3dSub(&vSize, &buildSector->boundingBox.sup,
             &buildSector->boundingBox.inf);
    if (vSize.x > conversionParams->worldSectorMaxSize)
    {
        RWRETURN(FALSE);
    }
    if (vSize.y > conversionParams->worldSectorMaxSize)
    {
        RWRETURN(FALSE);
    }
    if (vSize.z > conversionParams->worldSectorMaxSize)
    {
        RWRETURN(FALSE);
    }

    RWRETURN(TRUE);
}

static RtWorldImportBuildVertex *
ImportAddVertToBoundaries(RtWorldImportBuildSector * buildSector,
                          RtWorldImportVertex * vpVert, RwInt32 index)
{
    RwInt32             i;
    RtWorldImportBuildVertex *newBoundaries;
    RtWorldImportVertex *newVertices;
    RtWorldImportBuildVertexMode *mode;

    RWFUNCTION(RWSTRING("ImportAddVertToBoundaries"));

    newBoundaries = (RtWorldImportBuildVertex *)
        RwMalloc(sizeof(RtWorldImportBuildVertex) *
                 (buildSector->numBoundaries + 1));
    newVertices = (RtWorldImportVertex *)
        RwMalloc(sizeof(RtWorldImportVertex) *
                 (buildSector->numVertices + 1));

    memcpy(newVertices, buildSector->vertices,
           sizeof(RtWorldImportVertex) * buildSector->numVertices);

    for (i = 0; i < buildSector->numVertices; i++)
    {
        buildSector->vertices[i].state.vpVert = &(newVertices[i]);
    }

    for (i = 0; i < buildSector->numBoundaries; i++)
    {
        RtWorldImportBuildVertex *boundary =
            &buildSector->boundaries[i];
        RtWorldImportBuildVertexMode *const mode = &boundary->mode;

        if (mode->vpVert)
        {
            mode->vpVert = mode->vpVert->state.vpVert;
        }
    }

    RwFree(buildSector->vertices);
    buildSector->vertices = newVertices;

    buildSector->vertices[buildSector->numVertices] = *vpVert;
    buildSector->numVertices++;

    for (i = 0; i < index; i++)
    {
        newBoundaries[i] = buildSector->boundaries[i];
    }

    mode = &newBoundaries[index].mode;
    mode->vpVert = &buildSector->vertices[buildSector->numVertices - 1];

    for (i = index; i < buildSector->numBoundaries; i++)
    {
        newBoundaries[i + 1] = buildSector->boundaries[i];
    }

    buildSector->numBoundaries++;
    RwFree(buildSector->boundaries);
    buildSector->boundaries = newBoundaries;
    RWRETURN(newBoundaries);
}

/* We use this version when the vertex is being added as the
   2nd vertex in the boundary since we fan on vertex 1 and the
   standard insertion would cause degenerate triangles */
static RtWorldImportBuildVertex *
ImportAddVertToBoundariesAfter1stVert(RtWorldImportBuildSector *
                                      buildSector,
                                      RtWorldImportVertex * vpVert,
                                      RwInt32 index)
{
    RwInt32             i;
    RwInt32             lastVert;
    RwInt32             numVertices;
    RtWorldImportVertex *vertices;
    RtWorldImportVertex *newVertices;
    RwInt32             numBoundaries;
    RtWorldImportBuildVertex *boundaries;
    RtWorldImportBuildVertex *newBoundaries;
    RtWorldImportBuildVertexMode *mode;

    RWFUNCTION(RWSTRING("ImportAddVertToBoundariesAfter1stVert"));

    numVertices = buildSector->numVertices;
    vertices = buildSector->vertices;
    newVertices = (RtWorldImportVertex *)
        RwMalloc(sizeof(RtWorldImportVertex) * (numVertices + 1));

    numBoundaries = buildSector->numBoundaries;
    boundaries = buildSector->boundaries;
    newBoundaries = (RtWorldImportBuildVertex *)
        RwMalloc(sizeof(RtWorldImportBuildVertex) *
                 (numBoundaries + 1));

    memcpy(newVertices, vertices,
           sizeof(RtWorldImportVertex) * numVertices);

    for (i = 0; i < numVertices; i++)
    {
        vertices[i].state.vpVert = &(newVertices[i]);
    }

    for (i = 0; i < numBoundaries; i++)
    {
        RtWorldImportBuildVertex *const boundary = &boundaries[i];

        mode = &boundary->mode;

        if (mode->vpVert)
        {
            mode->vpVert = mode->vpVert->state.vpVert;
        }
    }
    RwFree(vertices);
    buildSector->vertices = newVertices;

    buildSector->vertices[buildSector->numVertices] = *vpVert;
    buildSector->numVertices++;

    for (i = 0; i < index; i++)
    {
        newBoundaries[i] = boundaries[i];
    }

    /* find last vertex in boundary */
    lastVert = index;

    for (mode = &boundaries[lastVert + 1].mode;
         mode->vpVert; mode = &boundaries[lastVert + 1].mode)
    {
        lastVert++;
    }

    newBoundaries[index] = boundaries[lastVert];
    newBoundaries[index + 1] = boundaries[index];

    mode = &newBoundaries[index + 2].mode;
    mode->vpVert = &buildSector->vertices[buildSector->numVertices - 1];

    for (i = index + 1; i < lastVert; i++)
    {
        newBoundaries[i + 2] = boundaries[i];
    }

    for (i = lastVert + 1; i < buildSector->numBoundaries; i++)
    {
        newBoundaries[i + 1] = boundaries[i];
    }

    buildSector->numBoundaries++;
    RwFree(boundaries);
    buildSector->boundaries = newBoundaries;

    RWRETURN(newBoundaries);
}

/* We use this version when the vertex is being added as the
   1st vertex in the boundary since we fan on vertex 1 and the
   standard insertion would cause degenerate triangles */
static RtWorldImportBuildVertex *
ImportAddVertToBoundariesBefore1stVert(RtWorldImportBuildSector *
                                       buildSector,
                                       RtWorldImportVertex * vpVert,
                                       RwInt32 index)
{
    RwInt32             i;
    RwInt32             lastVert;
    RtWorldImportBuildVertexMode *mode;
    RtWorldImportBuildVertex *newBoundaries;
    RtWorldImportVertex *newVertices;

    RWFUNCTION(RWSTRING("ImportAddVertToBoundariesBefore1stVert"));

    newBoundaries = (RtWorldImportBuildVertex *)
        RwMalloc(sizeof(RtWorldImportBuildVertex) *
                 (buildSector->numBoundaries + 1));
    newVertices = (RtWorldImportVertex *)
        RwMalloc(sizeof(RtWorldImportVertex) *
                 (buildSector->numVertices + 1));

    memcpy(newVertices, buildSector->vertices,
           sizeof(RtWorldImportVertex) * buildSector->numVertices);
    for (i = 0; i < buildSector->numVertices; i++)
    {
        buildSector->vertices[i].state.vpVert = &(newVertices[i]);
    }
    for (i = 0; i < buildSector->numBoundaries; i++)
    {
        RtWorldImportBuildVertex *const boundary =
            &buildSector->boundaries[i];
        RtWorldImportBuildVertexMode *const mode = &boundary->mode;

        if (mode->vpVert)
        {
            mode->vpVert = mode->vpVert->state.vpVert;
        }
    }
    RwFree(buildSector->vertices);
    buildSector->vertices = newVertices;

    buildSector->vertices = ((RtWorldImportVertex *)
                             RwRealloc(buildSector->vertices,
                                       sizeof(RtWorldImportVertex) *
                                       (buildSector->numVertices + 1)));
    buildSector->vertices[buildSector->numVertices] = *vpVert;
    buildSector->numVertices++;

    for (i = 0; i < index; i++)
    {
        newBoundaries[i] = buildSector->boundaries[i];
    }

    /* find last vertex in boundary */
    lastVert = index;

    for (mode = &buildSector->boundaries[lastVert + 1].mode;
         mode->vpVert;
         mode = &buildSector->boundaries[lastVert + 1].mode)
    {
        lastVert++;
    }

    newBoundaries[index] = buildSector->boundaries[lastVert - 1];
    newBoundaries[index + 1] = buildSector->boundaries[lastVert];

    mode = &newBoundaries[index + 2].mode;
    mode->vpVert = &buildSector->vertices[buildSector->numVertices - 1];
    for (i = index; i < lastVert - 1; i++)
    {
        newBoundaries[i + 3] = buildSector->boundaries[i];
    }

    for (i = lastVert + 1; i < buildSector->numBoundaries; i++)
    {
        newBoundaries[i + 1] = buildSector->boundaries[i];
    }

    buildSector->numBoundaries++;
    RwFree(buildSector->boundaries);
    buildSector->boundaries = newBoundaries;
    RWRETURN(newBoundaries);
}

static void
ImportCutVertFixupTJunctions(_rwCutVertex * cutVert,
                             RtWorldImportBuildSector * buildSector,
                             RtWorldImportParameters  * conversionParams,
                             RtWorldImportUserdataCallBacks *
                             UserDataCallBacks)
{
    RwInt32             firstVertInBoundary = 0;
    RwInt32             nI;

    RWFUNCTION(RWSTRING("ImportCutVertFixupTJunctions"));

    for (nI = 0; nI < buildSector->numBoundaries; nI++)
    {
        RwInt32             vert2;
        RtWorldImportBuildVertexMode *modenI;
        RtWorldImportBuildVertexMode *modevert2;

        modenI = &buildSector->boundaries[nI].mode;
        if (!modenI->vpVert)
        {
            firstVertInBoundary = nI + 1;
            continue;
        }

        modevert2 = &buildSector->boundaries[nI + 1].mode;
        if (modevert2->vpVert)
        {
            vert2 = nI + 1;
        }
        else
        {
            vert2 = firstVertInBoundary;
        }
        modevert2 = &buildSector->boundaries[vert2].mode;

        if ((GETCOORD(modenI->vpVert->OC, cutVert->plane) <
             cutVert->value &&
             GETCOORD(modevert2->vpVert->OC, cutVert->plane) >
             cutVert->value) ||
            (GETCOORD(modenI->vpVert->OC, cutVert->plane) >
             cutVert->value &&
             GETCOORD(modevert2->vpVert->OC, cutVert->plane) <
             cutVert->value))
        {
            /* ok it's an edge crossing the plane which the split
             * vertex was split by. Are they along the same line?
             * First check for differing vertices so we actually
             * have 2 edges */
            if ((!EQ(modenI->vpVert->OC.x, modevert2->vpVert->OC.x) ||
                 !EQ(modenI->vpVert->OC.y, modevert2->vpVert->OC.y) ||
                 !EQ(modenI->vpVert->OC.z, modevert2->vpVert->OC.z)) &&
                (!EQ(modenI->vpVert->OC.x, cutVert->vpVert.OC.x) ||
                 !EQ(modenI->vpVert->OC.y, cutVert->vpVert.OC.y) ||
                 !EQ(modenI->vpVert->OC.z, cutVert->vpVert.OC.z)))
            {
                RwV3d               lineVector, lineVector2;
                RwV3d               normalizedLineVector;
                RwV3d               normalizedLineVector2;
                RwReal              val1, val2;

                RwV3dSub(&lineVector,
                         &modevert2->vpVert->OC, &modenI->vpVert->OC);
                val1 =
                    RwV3dNormalize(&normalizedLineVector, &lineVector);

                RwV3dSub(&lineVector2, &cutVert->vpVert.OC,
                         &modenI->vpVert->OC);
                val2 = RwV3dNormalize(&normalizedLineVector2,
                                      &lineVector2);

                if (val2 < val1 && val2 > 0.0f &&
                    EQ(normalizedLineVector.x,
                       normalizedLineVector2.x) &&
                    EQ(normalizedLineVector.y,
                       normalizedLineVector2.y) &&
                    EQ(normalizedLineVector.z, normalizedLineVector2.z))
                {
                    RwInt32     nJ;

                    /* along the line, splitting the verts,
                     * so this is a T-Junction */
                    RtWorldImportVertex *const vpVertnI =
                        modenI->vpVert;
                    RtWorldImportVertex *const vpVertvert2 =
                        modevert2->vpVert;
                    RwReal              delta = val2 / val1;
                    RtWorldImportVertex newVert;

                    RtWorldImportInterpVertexUserdataCallBack
                        interpVertexUserdata;

                    /* ensure it has the same (identical)
                     * position as the cut */
                    newVert.OC = cutVert->vpVert.OC;
                    CLIPV3D(&newVert.normal,
                            &vpVertnI->normal,
                            &vpVertvert2->normal, delta);
                    CLIPCOLOR(&newVert.preLitCol,
                              &vpVertnI->preLitCol,
                              &vpVertvert2->preLitCol, delta);

                    for (nJ=0; nJ<conversionParams->numTexCoordSets; nJ++)
                    {
                        CLIPREAL(newVert.texCoords[nJ].u,
                                 vpVertnI->texCoords[nJ].u,
                                 vpVertvert2->texCoords[nJ].u, delta);
                        CLIPREAL(newVert.texCoords[nJ].v,
                                 vpVertnI->texCoords[nJ].v,
                                 vpVertvert2->texCoords[nJ].v, delta);
                    }

                    newVert.pUserdata = NULL;

                    interpVertexUserdata =
                        UserDataCallBacks->interpVertexUserdata;
                    if (interpVertexUserdata)
                    {
                        interpVertexUserdata(&newVert.pUserdata,
                                             &vpVertnI->pUserdata,
                                             &vpVertvert2->pUserdata,
                                             delta);
                    }

                    if (nI == firstVertInBoundary)
                    {
                        buildSector->boundaries =
                            ImportAddVertToBoundariesAfter1stVert
                            (buildSector, &newVert,
                             firstVertInBoundary);
                        /* and jump back to retest whole boundary */
                        nI = firstVertInBoundary - 1;
                    }
                    else if (vert2 == firstVertInBoundary)
                    {
                        buildSector->boundaries =
                            ImportAddVertToBoundariesBefore1stVert
                            (buildSector, &newVert,
                             firstVertInBoundary);
                        /* and jump back to retest whole boundary */
                        nI = firstVertInBoundary - 1;
                    }
                    else
                    {
                        buildSector->boundaries =
                            ImportAddVertToBoundaries(buildSector,
                                                      &newVert, vert2);
                    }
                }
            }
        }
    }

    RWRETURNVOID();
}

/****************************************************************************
 ImportBuildSectorSpaceCutPlane

 Finds if there is a plane which will cut up the world in such a way
 so that the space with the polygons in it can be separated out.
 This weighted by the largest extent

 On entry   : Build sector
            : Plane (OUT)
            : Value (OUT)
 On exit    : TRUE if found
 */

static              RwBool
ImportBuildSectorSpaceCutPlane(RtWorldImportBuildSector * buildSector,
                               RwInt32 * plane, RwReal * value)
{
    RwBBox              boundingBox;
    RwInt32             tryPlane;
    RwInt32             bestPlane = (RwInt32) 0;
    RwInt32             maxExtent;
    RwReal              bestValue = (RwReal) 0;
    RwV3d               vSize;
    RwReal              bestScore = (RwReal) 0;

    RWFUNCTION(RWSTRING("ImportBuildSectorSpaceCutPlane"));

    RWASSERT(buildSector);
    RWASSERT(plane);
    RWASSERT(value);

    /* Find the maximum extent for this sector */
    RwV3dSub(&vSize, &buildSector->boundingBox.sup,
             &buildSector->boundingBox.inf);
    maxExtent = 0;
    for (tryPlane = 0; tryPlane < 12; tryPlane += sizeof(RwReal))
    {
        if (GETCOORD(vSize, tryPlane) > GETCOORD(vSize, maxExtent))
        {
            maxExtent = tryPlane;
        }
    }

    /* just split it iff spacefilling */
    if (!buildSector->vertices)
    {
        (*plane) = maxExtent;
        (*value) =
            ( GETCOORD(buildSector->boundingBox.inf, maxExtent) + 
              GETCOORD(vSize, maxExtent) * 0.5f );
        RWRETURN(TRUE);
    }

    /* determine vertex extent (may be different from inherited BBox) */
    _rtImportBuildSectorFindBBox(buildSector, &boundingBox);

    /* choose an axis to split along */
    for (tryPlane = 0; tryPlane < 12; tryPlane += sizeof(RwReal))
    {
        RwReal              extentScore, propOfSectorRemoved, score;

        FuzzyWorldExtentMacro(extentScore,
                              GETCOORD(vSize, tryPlane),
                              GETCOORD(vSize, maxExtent));

        /* We add a guard band of 0.001 around the geometry.
         * In the case of (near)planar geometry this makes
         * propOfSectorRemoved comparatively large and so chooses
         * to repeatedly slice off the guard band
         *  (and then re-add the guard band).
         */
        if (GETCOORD(vSize, tryPlane) > (SPLIT_EPSILON + SPLIT_EPSILON))
        {
            RwReal              recip =
                1.0f / GETCOORD(vSize, tryPlane);

            /* Calculate the proportion of the world that would be chopped off at the top end
             *                                  <---------->        Proportion of this bit
             *                  ****************                    (Vertex bounding box)
             *  ********************************************        (Sector bounding box)
             *
             *  NB bump bestValue toward spacefill to avoid including any vertices
             */
            propOfSectorRemoved =
                ( GETCOORD(buildSector->boundingBox.sup,tryPlane) - 
                  GETCOORD(boundingBox.sup, tryPlane) );
            propOfSectorRemoved = propOfSectorRemoved * recip;

            score = extentScore * propOfSectorRemoved;
            if (score > bestScore)
            {
                bestScore = score;
                bestPlane = tryPlane;
                bestValue =
                    GETCOORD(boundingBox.sup, tryPlane) + 
                    SPLIT_EPSILON;
            }

            /* Calculate the proportion of the world that would be chopped off at the bottom end
             *  <-------------->                                    Proportion of this bit
             *                  ****************                    (Vertex bounding box)
             *  ********************************************        (Sector bounding box)
             *
             *  NB bump bestValue toward spacefill to avoid including any vertices
             */
            propOfSectorRemoved =
                ( GETCOORD(boundingBox.inf, tryPlane) -
                  GETCOORD(buildSector->boundingBox.inf, tryPlane) );
            propOfSectorRemoved = propOfSectorRemoved * recip;

            score = extentScore * propOfSectorRemoved;
            if (score > bestScore)
            {
                bestScore = score;
                bestPlane = tryPlane;
                bestValue =
                    GETCOORD(boundingBox.inf, tryPlane) - 
                    SPLIT_EPSILON;
            }
        }
    }

    if (bestScore > 0.25f)
    {
        (*plane) = bestPlane;
        (*value) = bestValue;
        RWRETURN(TRUE);
    }
    else
    {
        RWRETURN(FALSE);
    }
}

/* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

   Deciding where to split it

   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */

static int          RWCDECL
ImportSortVertexCmp(const void *a, const void *b)
{
    const _rwSortVertex *sortVertA = (const _rwSortVertex *) a;
    const _rwSortVertex *sortVertB = (const _rwSortVertex *) b;

    RWFUNCTION(RWSTRING("ImportSortVertexCmp"));
    RWASSERT(sortVertA);
    RWASSERT(sortVertB);

    if (sortVertA->dist < sortVertB->dist)
    {
        RWRETURN(-1);
    }
    else if (sortVertA->dist > sortVertB->dist)
    {
        RWRETURN(1);
    }
    else
    {
        RWRETURN(0);
    }
}

/****************************************************************************
 ImportBuildSectorSplittingCutPlane

 The basic algorithm is as follows

 For each of X Y and Z

 1) Find the median value
 2) Find the first n different values closest to the median value
    For each of the n values
    3) Mark each vertex as left, right or on plane
    4) Use fuzzy scaling factors (non linear) to weight division in favor of:
        a) Division of the geometry into two equal pieces.
        b) Division of the fattest dimension of the bounding box (extent score)
        c) As few polygons on the splitting plane as possible
    5) Choose the best weighting

 On entry   : Build sector
            : Plane (OUT)
            : Value (OUT)
 On exit    : TRUE if alls ok
 */

static              RwBool
ImportBuildSectorSplittingCutPlane(RtWorldImportBuildSector *
                                   buildSector, RwInt32 * plane,
                                   RwReal * value,
                                   RtWorldImportParameters *
                                   conversionParams,
                                   RtBuildSectorClipStatistics * stats)
{
    RwReal              bestScore = RwRealMAXVAL; /* Havent found any */
    RwInt32             bestPlane = (RwInt32) 0;
    RwReal              bestValue = (RwReal) 0;
    RtBuildSectorClipStatistics bestStats;
    RwInt32             nI;
    RwInt32             tryPlane;
    RwV3d               vSize;
    RwInt32             maxExtent;
    _rwSortVertex      *sortVerts;

    RWFUNCTION(RWSTRING("ImportBuildSectorSplittingCutPlane"));

    RWASSERT(buildSector);
    RWASSERT(plane);
    RWASSERT(value);
    RWASSERT(stats);

    /* Find the maximum extent for this sector */
    RwV3dSub(&vSize, &buildSector->boundingBox.sup,
             &buildSector->boundingBox.inf);
    maxExtent = 0;
    for (tryPlane = 0; tryPlane < 12; tryPlane += sizeof(RwReal))
    {
        if (GETCOORD(vSize, tryPlane) > GETCOORD(vSize, maxExtent))
        {
            maxExtent = tryPlane;
        }
    }

    sortVerts = (_rwSortVertex *)
        RwMalloc(sizeof(_rwSortVertex) * buildSector->numVertices);
    for (nI = 0; nI < buildSector->numVertices; nI++)
    {
        sortVerts[nI].vpVert = &buildSector->vertices[nI];
    }

    /* Go through the planes -> try and find the best one */
    for (tryPlane = 0; tryPlane < 12; tryPlane += sizeof(RwReal))
    {
        RwReal              quantThresh;
        RwReal              extentScore;
        RwReal              median;
        RwReal              interIndexRange;
        RwInt32             lastquantValue;
        RwInt32             lowerIndex;
        RwInt32             upperIndex;

        /* we use extent just as a tiebreak only */
        FuzzyWorldExtentMacro(extentScore,
                              GETCOORD(vSize, tryPlane),
                              GETCOORD(vSize, maxExtent));
        RWASSERT(0.0 != extentScore);

        extentScore = (1.0f / extentScore);

        /* find median of population */
        for (nI = 0; nI < buildSector->numVertices; nI++)
        {
            sortVerts[nI].dist =
                GETCOORD(sortVerts[nI].vpVert->OC, tryPlane);
        }

        qsort((void *) sortVerts,
              buildSector->numVertices,
              sizeof(_rwSortVertex), ImportSortVertexCmp);

        /* value that bisects population in tryPlane axis */
        median = sortVerts[nI >> 1].dist;
        lowerIndex = (nI * 40) / 100; /* 40% */
        upperIndex = (nI * 60) / 100; /* 60% */

        /* granularity by which we move plane around +/-25% of median */
        interIndexRange =
            sortVerts[upperIndex].dist - sortVerts[lowerIndex].dist;
        quantThresh =
            ((RwReal) conversionParams->maxClosestCheck) /
            interIndexRange;

#if 0
        /* sort just this subarray on abs dist from median */
        for (nI = lowerIndex; nI <= upperIndex; nI++)
        {
            RwReal              dist = median - sortVerts[nI].dist;

            if (dist < 0.0f)
            {
                sortVerts[nI].dist = -dist;
            }
            else
            {
                sortVerts[nI].dist = dist;
            }
        }
        qsort((void *) &sortVerts[lowerIndex],
              upperIndex - lowerIndex + 1, sizeof(_rwSortVertex),
              ImportSortVertexCmp);
#endif

        /* score test planes  */
        lastquantValue = -1;
        for (nI = lowerIndex; nI <= upperIndex; nI++)
        {
            RwReal              score, tryValue;
            RwInt32             quantValue;

            /* fetch the next unique distance */
            tryValue = GETCOORD(sortVerts[nI].vpVert->OC, tryPlane);
            quantValue = (RwInt32) (tryValue * quantThresh);
            if (quantValue != lastquantValue)
            {
                /* Set the clip codes */
                BuildSectorSetWorldClipCodes(buildSector, tryPlane,
                                             tryValue);

                /* Check what would be resultant polygons with this clip plane
                 * Including a look at overlaps and alpha distances */
                _rtImportBuildSectorGetClipStatistics(buildSector,
                                                      stats, tryPlane,
                                                      tryValue);

                /* does it actually divide the geometry? */
                if (stats->numMaterialLeft && stats->numMaterialRight)
                {
                    RwReal              leftscore;
                    RwReal              rightscore;
                    RwReal              clipCost;
                    RwReal              diff;
                    RwInt32             leftsectors, rightsectors;

                    /* if there's alpha we need to really clip */
                    clipCost = stats->alphaInOverlap ? 1024.0f : 256.0f;

                    leftsectors =
                        (stats->nLeft +
                         conversionParams->maxWorldSectorPolygons -
                         1) / conversionParams->maxWorldSectorPolygons;
                    leftscore =
                        (RwReal) (stats->nLeft) +
                        (RwReal) (stats->nSplit) * clipCost +
                        (RwReal) (stats->numMaterialLeft * MESHCOST) +
                        (RwReal) (leftsectors * SECTORCOST);

                    /* bigger overlaps means proportionally more work */
                    leftscore +=
                        leftscore * (stats->overlapLeft /
                                     GETCOORD(vSize, tryPlane));

                    rightsectors =
                        (stats->nRight +
                         conversionParams->maxWorldSectorPolygons -
                         1) / conversionParams->maxWorldSectorPolygons;
                    rightscore =
                        (RwReal) (stats->nRight) +
                        (RwReal) (stats->nSplit) * clipCost +
                        (RwReal) (stats->numMaterialRight * MESHCOST) +
                        (RwReal) (rightsectors * SECTORCOST);

                    /* bigger overlaps means proportionally more work */
                    rightscore +=
                        rightscore * (stats->overlapRight /
                                      GETCOORD(vSize, tryPlane));

                    /* score is total work if we use this split */
                    score = leftscore + rightscore;

                    /* we implicitly bias to a balanced tree because
                     * we test from the median outward;
                     * however we'll bias a bit more
                     */
                    diff = leftscore - rightscore;
                    score += ((diff < 0) ? -diff : diff);

                    /* both leaf node biasing */
                    if ((leftsectors == 1) && (rightsectors == 1))
                    {
                        score *= 0.5f;
                    }

                    /* extent biasing */
                    score *= extentScore;

                    /* is it a winner? */
                    if (score < bestScore)
                    {
                        bestScore = score;
                        bestPlane = tryPlane;
                        bestValue = tryValue;
                        bestStats = *stats;
                    }
                }

                /* onto next test plane */
                lastquantValue = quantValue;
            }
        }
    }

    /* clean up */
    RwFree(sortVerts);

    /* Check if a suitable plane was found at all */
    if (bestScore < RwRealMAXVAL)
    {
        (*plane) = bestPlane;
        (*value) = bestValue;
        (*stats) = bestStats;
        RWRETURN(TRUE);
    }

    RWRETURN(FALSE);
}

/****************************************************************************
 ImportBuildSectorSplit

 Partitions the polygon set amongst
 two new BuildSectors
 according to the previous setup clip Flags

*/

static void
ImportAddCut(RwFreeList * flpCuts, RwLinkList * cuts,
             RtWorldImportBuildVertex * v1,
             RtWorldImportBuildVertex * v2, RwInt32 plane, RwReal value,
             RtWorldImportBuildVertex * vpInterp,
             RtWorldImportParameters  * conversionParams,
             RtWorldImportUserdataCallBacks * UserDataCallBacks)
{
    RtWorldImportBuildVertexMode *mode;
    RwLLLink           *cur, *end;
    _rwCut             *cut;

    RWFUNCTION(RWSTRING("ImportAddCut"));

    /* condition endpoints */
    if (v1 > v2)
    {
        RtWorldImportBuildVertex *vTmp;

        vTmp = v1;
        v1 = v2;
        v2 = vTmp;
    }

    /* first see if we've done this edge already */
    cut = (_rwCut *) NULL;
    cur = rwLinkListGetFirstLLLink(cuts);
    end = rwLinkListGetTerminator(cuts);
    while (cur != end)
    {
        RtWorldImportBuildVertexMode const *modev1 = &v1->mode;
        RtWorldImportBuildVertexMode const *modev2 = &v2->mode;

        cut = rwLLLinkGetData(cur, _rwCut, lAll);
        if ((cut->v1 == modev1->vpVert) && (cut->v2 == modev2->vpVert))
        {
            break;
        }
        cut = (_rwCut *) NULL;

        /* Onto the next cut */
        cur = rwLLLinkGetNext(cur);
    }

    /* ok so create a new one */
    if (!cut)
    {
        RwInt32     nI;

        RtWorldImportBuildVertexMode const *modev1 = &v1->mode;
        RtWorldImportBuildVertexMode const *modev2 = &v2->mode;
        RtWorldImportInterpVertexUserdataCallBack interpVertexUserdata;

        cut = (_rwCut *) RwFreeListAlloc(flpCuts);
        rwLLLinkInitialize(&cut->lAll);
        rwLinkListAddLLLink(cuts, &cut->lAll);

        cut->v1 = modev1->vpVert;
        cut->v2 = modev2->vpVert;
        cut->delta = (value - GETCOORD(modev1->vpVert->OC, plane)) /
            (GETCOORD(modev2->vpVert->OC, plane) -
             GETCOORD(modev1->vpVert->OC, plane));

        /* clip vertex data */
        CLIPV3D(&cut->vInterp.OC,
                &modev1->vpVert->OC, &modev2->vpVert->OC, cut->delta);
        CLIPV3D(&cut->vInterp.normal,
                &modev1->vpVert->normal, &modev2->vpVert->normal,
                cut->delta);
        CLIPCOLOR(&cut->vInterp.preLitCol,
                  &modev1->vpVert->preLitCol,
                  &modev2->vpVert->preLitCol, cut->delta);

        nI = conversionParams->numTexCoordSets;
        while(nI--)
        {
            CLIPREAL(cut->vInterp.texCoords[nI].u,
                     modev1->vpVert->texCoords[nI].u,
                     modev2->vpVert->texCoords[nI].u, cut->delta);
            CLIPREAL(cut->vInterp.texCoords[nI].v,
                     modev1->vpVert->texCoords[nI].v,
                     modev2->vpVert->texCoords[nI].v, cut->delta);
        }

        cut->vInterp.pUserdata = NULL;
        interpVertexUserdata = UserDataCallBacks->interpVertexUserdata;

        if (interpVertexUserdata)
        {
            interpVertexUserdata(&cut->vInterp.pUserdata,
                                 &modev1->vpVert->pUserdata,
                                 &modev2->vpVert->pUserdata,
                                 cut->delta);
        }
    }

    mode = &vpInterp->mode;
    mode->vpVert = &cut->vInterp;

    RWRETURNVOID();
}

static RtWorldImportVertex *
ImportRemapVertices(RwSList * boundaries, RwInt32 * total,
                    RtWorldImportUserdataCallBacks * UserDataCallBacks)
{
    RwInt32             nI, vcount;
    RtWorldImportBuildVertex *vpTmp;
    RtWorldImportVertex *vertices;
    RtWorldImportCloneVertexUserdataCallBack cloneVertexUserdata;

    RWFUNCTION(RWSTRING("ImportRemapVertices"));

    if (_rwSListGetNumEntriesMacro(boundaries) == 0)
    {
        *total = 0;
        RWRETURN((RtWorldImportVertex *) NULL);
    }

    /* clear all */
    vpTmp = (RtWorldImportBuildVertex *) rwSListGetEntry(boundaries, 0);
    for (nI = 0; nI < _rwSListGetNumEntriesMacro(boundaries);
         nI++, vpTmp++)
    {
        RtWorldImportBuildVertexMode *const mode = &vpTmp->mode;

        if (mode->vpVert)
        {
            mode->vpVert->state.forwardingAddress = -1;
        }
    }

    /* mark and count */
    vcount = 0;
    vpTmp = (RtWorldImportBuildVertex *) rwSListGetEntry(boundaries, 0);
    for (nI = 0; nI < _rwSListGetNumEntriesMacro(boundaries);
         nI++, vpTmp++)
    {
        RtWorldImportBuildVertexMode *const mode = &vpTmp->mode;

        if (mode->vpVert)
        {
            if (mode->vpVert->state.forwardingAddress < 0)
            {
                mode->vpVert->state.forwardingAddress = vcount++;
            }
        }
    }
    *total = vcount;

    vertices = (RtWorldImportVertex *)
        RwMalloc(sizeof(RtWorldImportVertex) * vcount);
    vpTmp = (RtWorldImportBuildVertex *) rwSListGetEntry(boundaries, 0);

    cloneVertexUserdata = UserDataCallBacks->cloneVertexUserdata;

    if (cloneVertexUserdata)
    {
        for (nI = 0; nI < _rwSListGetNumEntriesMacro(boundaries);
             nI++, vpTmp++)
        {
            RtWorldImportBuildVertexMode *const mode = &vpTmp->mode;

            if (mode->vpVert)
            {
                /* copy over vertex */
                vertices[mode->vpVert->state.forwardingAddress] =
                    *mode->vpVert;

                /* clone the userdata */
                cloneVertexUserdata(&vertices
                                    [mode->vpVert->state.
                                     forwardingAddress].pUserdata,
                                    &mode->vpVert->pUserdata);

                /* point to new vertex */
                mode->vpVert =
                    &vertices[mode->vpVert->state.forwardingAddress];
            }
        }
    }
    else
    {
        for (nI = 0; nI < _rwSListGetNumEntriesMacro(boundaries);
             nI++, vpTmp++)
        {
            RtWorldImportBuildVertexMode *const mode = &vpTmp->mode;

            if (mode->vpVert)
            {
                /* copy over vertex */
                vertices[mode->vpVert->state.forwardingAddress] =
                    *mode->vpVert;

                /* point to new vertex */
                mode->vpVert =
                    &vertices[mode->vpVert->state.forwardingAddress];
            }
        }
    }

    RWRETURN(vertices);
}

static void
ImportDestroyCuts(RwFreeList * flpCuts, RwLinkList * list,
                  RtWorldImportUserdataCallBacks * UserDataCallBacks)
{
    RwLLLink           *cur, *end;
    RtWorldImportDestroyVertexUserdataCallBack destroyVertexUserdata;

    RWFUNCTION(RWSTRING("ImportDestroyCuts"));
    RWASSERT(flpCuts);
    RWASSERT(list);

    cur = rwLinkListGetFirstLLLink(list);
    end = rwLinkListGetTerminator(list);
    destroyVertexUserdata = UserDataCallBacks->destroyVertexUserdata;

    if (destroyVertexUserdata)
    {
        while (cur != end)
        {
            _rwCut             *cut =
                rwLLLinkGetData(cur, _rwCut, lAll);

            destroyVertexUserdata(&cut->vInterp.pUserdata);

            cur = rwLLLinkGetNext(cur);
            RwFreeListFree(flpCuts, cut);
        }
    }
    else
    {
        while (cur != end)
        {
            _rwCut             *cut =
                rwLLLinkGetData(cur, _rwCut, lAll);

            cur = rwLLLinkGetNext(cur);
            RwFreeListFree(flpCuts, cut);
        }
    }

    RWRETURNVOID();
}

static              RwBool
ImportBuildSectorSplit(RtWorldImportBuildSector * buildSector,
                       RwInt32 plane, RwReal value,
                       RtWorldImportBuildSector ** buildSectorOutLeft,
                       RtWorldImportBuildSector ** buildSectorOutRight,
                       RtWorldImportParameters * conversionParams,
                       RwSList * cutVertexList,
                       RtBuildSectorClipStatistics * stats,
                       RtWorldImportUserdataCallBacks *
                       UserDataCallBacks)
{
    RwInt32             nI;
    RtWorldImportBuildSector *newleft;
    RtWorldImportBuildSector *newright;
    RtWorldImportBuildVertex *vpFirst;
    RtWorldImportBuildVertex *vpCurr;
    RtWorldImportBuildVertex *vpPrev;
    RtWorldImportBuildVertex *vpTri;
    RtWorldImportBuildVertex *vpTmp;
    RwSList            *leftboundaries, *rightboundaries;
    RwFreeList         *flpLeftCuts, *flpRightCuts;
    RwLinkList          leftcuts, rightcuts;
    RwBBox              bbox;
    RwInt32             clip, leftcount, rightcount;
    RwReal              distLeft, distRight;
    RwReal              extentLeft, extentRight;
    RwInt32             side;
    RwReal              leftClipExtent, rightClipExtent;
    RwBool              mustClipAll = FALSE;

    RWFUNCTION(RWSTRING("ImportBuildSectorSplit"));

    extentLeft = value - GETCOORD(buildSector->boundingBox.inf, plane);
    extentRight = GETCOORD(buildSector->boundingBox.sup, plane) - value;
    leftClipExtent = extentLeft * conversionParams->maxOverlapPercent;
    rightClipExtent = extentRight * conversionParams->maxOverlapPercent;

    if (conversionParams->noAlphaInOverlap)
    {
        if (stats->alphaInOverlap)
        {
            mustClipAll = TRUE;
        }
    }

    leftboundaries = rwSListCreate(sizeof(RtWorldImportBuildVertex));
    rightboundaries = rwSListCreate(sizeof(RtWorldImportBuildVertex));

    flpLeftCuts = RwFreeListCreate(sizeof(_rwCut), 100, 0);
    flpRightCuts = RwFreeListCreate(sizeof(_rwCut), 100, 0);
    rwLinkListInitialize(&leftcuts);
    rwLinkListInitialize(&rightcuts);

    leftcount = rightcount = 0;
    distLeft = distRight = 0.0f;
    clip = rwCLIPVERTEXLEFT | rwCLIPVERTEXRIGHT;
    vpFirst = vpCurr = buildSector->boundaries;
    for (nI = 0; nI < buildSector->numBoundaries; nI++, vpCurr++)
    {
        RtWorldImportBuildVertexMode *const modevpCurr = &vpCurr->mode;

        if (modevpCurr->vpVert)
        {
            RwReal              dist =
                GETCOORD(modevpCurr->vpVert->OC, plane) - value;

            /* track total clip flags */
            clip &= modevpCurr->vpVert->state.clipFlags;

            /* track distances from plane */
            if (modevpCurr->vpVert->state.clipFlags == rwCLIPVERTEXLEFT)
            {
                if (-dist > distLeft)
                {
                    distLeft = -dist;
                }
            }
            else if (modevpCurr->vpVert->state.clipFlags ==
                     rwCLIPVERTEXRIGHT)
            {
                if (dist > distRight)
                {
                    distRight = dist;
                }
            }
            continue;
        }

        /* ok we've got to end of polygon's vertices */
        switch (clip)
        {
                /* wholly on the left */
            case rwCLIPVERTEXLEFT:

                vpTri = vpFirst;
                while (vpTri != vpCurr)
                {
                    vpTmp = (RtWorldImportBuildVertex *)
                        rwSListGetNewEntry(leftboundaries);
                    *vpTmp = *vpTri;
                    vpTri++;
                }
                vpTmp = (RtWorldImportBuildVertex *)
                    rwSListGetNewEntry(leftboundaries);
                *vpTmp = *vpCurr;
                leftcount++;
                break;

                /* wholly on the right */
            case rwCLIPVERTEXLEFT | rwCLIPVERTEXRIGHT:
            case rwCLIPVERTEXRIGHT:

                vpTri = vpFirst;
                while (vpTri != vpCurr)
                {
                    vpTmp = (RtWorldImportBuildVertex *)
                        rwSListGetNewEntry(rightboundaries);
                    *vpTmp = *vpTri;
                    vpTri++;
                }
                vpTmp = (RtWorldImportBuildVertex *)
                    rwSListGetNewEntry(rightboundaries);
                *vpTmp = *vpCurr;
                rightcount++;
                break;

                /* its a split */
            case 0:

                /* which side should we stick it on */
                if (mustClipAll ||
                    (distLeft > leftClipExtent &&
                     distRight > rightClipExtent))
                {
                    side = -1;
                }
                else
                {
                    if (distLeft > distRight)
                    {
                        if (distRight > rightClipExtent)
                        {
                            side = -1;
                        }
                        else
                        {
                            side = 0;
                        }
                    }
                    else
                    {
                        if (distLeft > leftClipExtent)
                        {
                            side = -1;
                        }
                        else
                        {
                            side = 1;
                        }
                    }
                }

                if (side == 0) /* left */
                {
                    vpTri = vpFirst;
                    while (vpTri != vpCurr)
                    {
                        vpTmp = (RtWorldImportBuildVertex *)
                            rwSListGetNewEntry(leftboundaries);
                        *vpTmp = *vpTri;
                        vpTri++;
                    }
                    vpTmp = (RtWorldImportBuildVertex *)
                        rwSListGetNewEntry(leftboundaries);
                    *vpTmp = *vpCurr;
                    leftcount++;
                }
                else if (side == 1) /* right */
                {
                    vpTri = vpFirst;
                    while (vpTri != vpCurr)
                    {
                        vpTmp = (RtWorldImportBuildVertex *)
                            rwSListGetNewEntry(rightboundaries);
                        *vpTmp = *vpTri;
                        vpTri++;
                    }
                    vpTmp = (RtWorldImportBuildVertex *)
                        rwSListGetNewEntry(rightboundaries);
                    *vpTmp = *vpCurr;
                    rightcount++;
                }
                else
                {
                    RtWorldImportBuildVertexMode *const modevpFirst =
                        &vpFirst->mode;
                    RtWorldImportBuildVertexMode *modevpPrev;
                    RtWorldImportBuildVertexMode *modevpTri;

                    RtWorldImportSplitPolygonUserdataCallBack
                        splitPolygonUserdata;

                    /* sticks out too much so split it on plane */
                    clip = 0;

                    vpPrev = vpFirst;
                    vpTri = vpFirst + 1;
                    while (vpTri != vpCurr)
                    {
                        modevpPrev = &vpPrev->mode;
                        modevpTri = &vpTri->mode;

                        clip |= modevpPrev->vpVert->state.clipFlags;
                        if (modevpPrev->vpVert->state.clipFlags &
                            rwCLIPVERTEXLEFT)
                        {
                            vpTmp = (RtWorldImportBuildVertex *)
                                rwSListGetNewEntry(leftboundaries);
                            *vpTmp = *vpPrev;
                        }
                        if (modevpPrev->vpVert->state.clipFlags &
                            rwCLIPVERTEXRIGHT)
                        {
                            vpTmp = (RtWorldImportBuildVertex *)
                                rwSListGetNewEntry(rightboundaries);
                            *vpTmp = *vpPrev;
                        }
                        if (!(modevpPrev->vpVert->state.clipFlags &
                              modevpTri->vpVert->state.clipFlags))
                        {
                            vpTmp = (RtWorldImportBuildVertex *)
                                rwSListGetNewEntry(leftboundaries);
                            ImportAddCut(flpLeftCuts, &leftcuts,
                                         vpPrev, vpTri, plane, value,
                                         vpTmp, conversionParams,
                                         UserDataCallBacks);
                            vpTmp = (RtWorldImportBuildVertex *)
                                rwSListGetNewEntry(rightboundaries);
                            ImportAddCut(flpRightCuts, &rightcuts,
                                         vpPrev, vpTri, plane, value,
                                         vpTmp, conversionParams,
                                         UserDataCallBacks);

                            /* track all cuts */
                            {
                                _rwCutVertex       *temp =
                                    (_rwCutVertex *)
                                    rwSListGetNewEntry(cutVertexList);
                                RtWorldImportBuildVertexMode *const
                                    modevpTmp = &vpTmp->mode;

                                temp->plane = plane;
                                temp->value = value;
                                temp->vpVert = *(modevpTmp->vpVert);
                            }

                        }
                        vpPrev++;
                        vpTri++;
                    }

                    /* do closing edge too */
                    modevpPrev = &vpPrev->mode;

                    clip |= modevpPrev->vpVert->state.clipFlags;
                    if (modevpPrev->vpVert->state.
                        clipFlags & rwCLIPVERTEXLEFT)
                    {
                        vpTmp = (RtWorldImportBuildVertex *)
                            rwSListGetNewEntry(leftboundaries);
                        *vpTmp = *vpPrev;
                    }
                    if (modevpPrev->vpVert->state.
                        clipFlags & rwCLIPVERTEXRIGHT)
                    {
                        vpTmp = (RtWorldImportBuildVertex *)
                            rwSListGetNewEntry(rightboundaries);
                        *vpTmp = *vpPrev;
                    }
                    if (!(modevpPrev->vpVert->state.clipFlags &
                          modevpFirst->vpVert->state.clipFlags))
                    {
                        vpTmp = (RtWorldImportBuildVertex *)
                            rwSListGetNewEntry(leftboundaries);
                        ImportAddCut(flpLeftCuts, &leftcuts, vpPrev,
                                     vpFirst, plane, value, vpTmp,
                                     conversionParams,
                                     UserDataCallBacks);

                        vpTmp = (RtWorldImportBuildVertex *)
                            rwSListGetNewEntry(rightboundaries);
                        ImportAddCut(flpRightCuts, &rightcuts, vpPrev,
                                     vpFirst, plane, value, vpTmp,
                                     conversionParams,
                                     UserDataCallBacks);

                        /* track all cuts */
                        {
                            _rwCutVertex       *temp =
                                (_rwCutVertex *)
                                rwSListGetNewEntry(cutVertexList);
                            RtWorldImportBuildVertexMode *const
                                modevpTmp = &vpTmp->mode;

                            temp->plane = plane;
                            temp->value = value;
                            temp->vpVert = *(modevpTmp->vpVert);
                        }
                    }

                    splitPolygonUserdata =
                        UserDataCallBacks->splitPolygonUserdata;

                    /* mark end of polygons (if we created any) */
                    if (splitPolygonUserdata
                        && (clip & rwCLIPVERTEXLEFT)
                        && (clip & rwCLIPVERTEXRIGHT)
                        && vpCurr->pinfo.pUserdata)
                    {
                        /* if splitting the polygon and the callback is
                         * set split the polyinfo */
                        vpTmp = (RtWorldImportBuildVertex *)
                            rwSListGetNewEntry(leftboundaries);
                        *vpTmp = *vpCurr;
                        vpTmp->pinfo.pUserdata = NULL;
                        splitPolygonUserdata(&vpTmp->pinfo.
                                             pUserdata,
                                             &vpCurr->pinfo.pUserdata);
                        leftcount++;

                        vpTmp = (RtWorldImportBuildVertex *)
                            rwSListGetNewEntry(rightboundaries);
                        *vpTmp = *vpCurr;
                        vpTmp->pinfo.pUserdata = NULL;
                        splitPolygonUserdata(&vpTmp->pinfo.
                                             pUserdata,
                                             &vpCurr->pinfo.pUserdata);
                        rightcount++;

                    }
                    else
                    {
                        if (clip & rwCLIPVERTEXLEFT)
                        {
                            vpTmp = (RtWorldImportBuildVertex *)
                                rwSListGetNewEntry(leftboundaries);
                            *vpTmp = *vpCurr;
                            leftcount++;
                        }
                        if (clip & rwCLIPVERTEXRIGHT)
                        {
                            vpTmp = (RtWorldImportBuildVertex *)
                                rwSListGetNewEntry(rightboundaries);
                            *vpTmp = *vpCurr;
                            rightcount++;
                        }
                    }
                }
                break;

        }

        vpFirst = vpCurr + 1;
        clip = rwCLIPVERTEXLEFT | rwCLIPVERTEXRIGHT;
        distLeft = distRight = 0.0f;
    }

    /* new left build sector */
    newleft = _rtImportBuildSectorCreate();
    newleft->vertices =
        ImportRemapVertices(leftboundaries, &newleft->numVertices,
                            UserDataCallBacks);
    newleft->numBoundaries = _rwSListGetNumEntriesMacro(leftboundaries);
    newleft->boundaries =
        (RtWorldImportBuildVertex *) rwSListToArray(leftboundaries);
    newleft->numPolygons = leftcount;
    newleft->boundingBox = buildSector->boundingBox;
    SETCOORD(newleft->boundingBox.sup, plane, value);
    _rtImportBuildSectorFindBBox(newleft, &bbox);
    if (GETCOORD(bbox.sup, plane) >
        GETCOORD(newleft->boundingBox.sup, plane))
    {
        newleft->overlap = (GETCOORD(bbox.sup, plane) -
                            GETCOORD(newleft->boundingBox.sup, plane));
        SETCOORD(newleft->boundingBox.sup, plane,
                 GETCOORD(bbox.sup, plane));
    }
    else
    {
        newleft->overlap = 0.0f;
    }
    *buildSectorOutLeft = newleft;

    /* new right build sector */
    newright = _rtImportBuildSectorCreate();
    newright->vertices =
        ImportRemapVertices(rightboundaries, &newright->numVertices,
                            UserDataCallBacks);
    newright->numBoundaries =
        _rwSListGetNumEntriesMacro(rightboundaries);
    newright->boundaries =
        (RtWorldImportBuildVertex *) rwSListToArray(rightboundaries);

    newright->numPolygons = rightcount;
    newright->boundingBox = buildSector->boundingBox;
    SETCOORD(newright->boundingBox.inf, plane, value);
    _rtImportBuildSectorFindBBox(newright, &bbox);
    if (GETCOORD(bbox.inf, plane) <
        GETCOORD(newright->boundingBox.inf, plane))
    {
        newright->overlap =
            ( GETCOORD(newright->boundingBox.inf, plane) - 
              GETCOORD(bbox.inf, plane) );
        SETCOORD(newright->boundingBox.inf, plane,
                 GETCOORD(bbox.inf, plane));
    }
    else
    {
        newright->overlap = 0.0f;
    }
    *buildSectorOutRight = newright;

    /* Increase poly in world count */
    _rtWorldImportTotalPolysInWorld +=
        (leftcount + rightcount) - buildSector->numPolygons;

    /* clean up */
    ImportDestroyCuts(flpLeftCuts, &leftcuts, UserDataCallBacks);
    ImportDestroyCuts(flpRightCuts, &rightcuts, UserDataCallBacks);
    RwFreeListDestroy(flpLeftCuts);
    RwFreeListDestroy(flpRightCuts);

    RWRETURN(TRUE);
}

/****************************************************************************
 ImportBuildSectorSplitRecurse

  Cuts up a world such that the sectors to satisfy ImportBuildSectorAccept()

 On entry       : World (Containing only _rtBuild sectors)
 On exit        : Sectorized tree
 */

static RtWorldImportBuildPlaneSector *
ImportBuildSectorSplitRecurse(RtWorldImportBuildSector * buildSector,
                              RtWorldImportParameters *
                              conversionParams, RwInt32 currentBSPDepth,
                              RwSList * cutVertexList,
                              RwBool * ExitRequested,
                              RtWorldImportUserdataCallBacks *
                              UserDataCallBacks)
{
    RwInt32             plane;
    RwReal              value;
    RtWorldImportBuildPlaneSector *buildPlaneSector;
    RtWorldImportBuildSector *newLeftBuildSector;
    RtWorldImportBuildSector *newRightBuildSector;
    RtBuildSectorClipStatistics stats;

    RWFUNCTION(RWSTRING("ImportBuildSectorSplitRecurse"));

    RWASSERT(buildSector);

    if (*ExitRequested)
    {
        RWRETURN((RtWorldImportBuildPlaneSector *) NULL);
    }

    /* Keep track of the maximum BSP depth */
    if (currentBSPDepth > rpWORLDMAXBSPDEPTH)
    {
        RWERROR((E_RW_MAXBSPDEPTHEXCEEDED));
        RWRETURN((RtWorldImportBuildPlaneSector *) NULL);
    }

    /* Have we reached our acceptance criteria for the sectors yet? */
    if (ImportBuildSectorAccept(buildSector, conversionParams))
    {
        /* generate a tight bbox */
        if (buildSector->numVertices)
        {
            RwInt32             i;
            RwBBox              bbox;

            RwBBoxInitialize(&bbox, &buildSector->vertices[0].OC);
            for (i = 1; i < buildSector->numVertices; i++)
            {
                RwBBoxAddPointMacro(&bbox,
                                    &buildSector->vertices[i].OC);
            }
            buildSector->boundingBox = bbox;
        }

        /* Got a good sector */
        _rtWorldImportNumPolysInLeaves += buildSector->numPolygons;
        _rtImportWorldSendProgressMessage
            (rtWORLDIMPORTPROGRESSBSPBUILDUPDATE,
             ((RwReal) _rtWorldImportNumPolysInLeaves /
              (RwReal) _rtWorldImportTotalPolysInWorld) * 100);

        RWRETURN((RtWorldImportBuildPlaneSector *) buildSector);
    }

#ifdef RWDEBUG
    /* sanity check */
    _rtImportBuildSectorCheck(buildSector);
#endif /* RWDEBUG */

    /* Can we cut to remove open spaces? */
    if (conversionParams->spaceFillingSectors)
    {
        /* is there a slab of space to remove? */
        if (!ImportBuildSectorSpaceCutPlane
            (buildSector, &plane, &value))
        {
            /* OK, so find a good cutting plane */
            if (!ImportBuildSectorSplittingCutPlane
                (buildSector, &plane, &value, conversionParams, &stats))
            {
                /* Ooops */
                RWRETURN((RtWorldImportBuildPlaneSector *) NULL);
            }
        }
    }
    else
    {
        /* find a good cutting plane */
        if (!ImportBuildSectorSplittingCutPlane
            (buildSector, &plane, &value, conversionParams, &stats))
        {
            /* Ooops */
            RWRETURN((RtWorldImportBuildPlaneSector *) NULL);
        }
    }

    /* Split the build sector in two */
    BuildSectorSetWorldClipCodes(buildSector, plane, value);
    if (!ImportBuildSectorSplit(buildSector, plane, value,
                                &newLeftBuildSector,
                                &newRightBuildSector, conversionParams,
                                cutVertexList, &stats,
                                UserDataCallBacks))
    {
        /* Ooops */
        RWRETURN((RtWorldImportBuildPlaneSector *) NULL);
    }

    /* Create a new plane sector */
    buildPlaneSector = _rtImportBuildPlaneSectorCreate(plane, value);
    if (!buildPlaneSector)
    {
        /* Ooops */
        _rtImportBuildSectorDestroy(newLeftBuildSector,
                                    UserDataCallBacks);
        _rtImportBuildSectorDestroy(newRightBuildSector,
                                    UserDataCallBacks);
        RWRETURN((RtWorldImportBuildPlaneSector *) NULL);
    }
    buildPlaneSector->planeSector.leftValue =
        buildPlaneSector->planeSector.value +
        newLeftBuildSector->overlap;
    buildPlaneSector->planeSector.rightValue =
        buildPlaneSector->planeSector.value -
        newRightBuildSector->overlap;

    /* Recurse left */
    buildPlaneSector->planeSector.leftSubTree =
        (RpSector *) ImportBuildSectorSplitRecurse(newLeftBuildSector,
                                                   conversionParams,
                                                   currentBSPDepth + 1,
                                                   cutVertexList,
                                                   ExitRequested,
                                                   UserDataCallBacks);
    if (buildPlaneSector->planeSector.leftSubTree == NULL)
    {
        /* An error has occurred -> destroy it */
        _rtImportBuildSectorDestroy(newLeftBuildSector,
                                    UserDataCallBacks);
        _rtImportBuildSectorDestroy(newRightBuildSector,
                                    UserDataCallBacks);
        _rtImportPlaneSectorDestroy(buildPlaneSector);
        RWRETURN((RtWorldImportBuildPlaneSector *) NULL);
    }

    /* Recurse right */
    buildPlaneSector->planeSector.rightSubTree =
        (RpSector *) ImportBuildSectorSplitRecurse(newRightBuildSector,
                                                   conversionParams,
                                                   currentBSPDepth + 1,
                                                   cutVertexList,
                                                   ExitRequested,
                                                   UserDataCallBacks);
    if (buildPlaneSector->planeSector.rightSubTree == NULL)
    {
        /* An error has occurred -> destroy it */

        RtWorldImportBuildPlaneSector *leftSubTree =
            (RtWorldImportBuildPlaneSector *)
            buildPlaneSector->planeSector.leftSubTree;

        _rtImportPlaneSectorDestroyTree(leftSubTree, UserDataCallBacks);
        _rtImportBuildSectorDestroy(newRightBuildSector,
                                    UserDataCallBacks);
        _rtImportPlaneSectorDestroy(buildPlaneSector);
        RWRETURN((RtWorldImportBuildPlaneSector *) NULL);
    }

    /* only now destroy the original */
    _rtImportBuildSectorDestroy(buildSector, UserDataCallBacks);

    /* Return the sector */
    RWRETURN(buildPlaneSector);
}

static RpSector    *
ImportWorldFixupTJunctions(RpSector * rootSector,
                           RwSList * cutVertexList,
                           RtWorldImportParameters * conversionParams,
                           RwBool * resplit,
                           RwBool * ExitRequested,
                           RtWorldImportUserdataCallBacks *
                           UserDataCallBacks)
{
    RWFUNCTION(RWSTRING("ImportWorldFixupTJunctions"));

    if (rootSector->type >= 0)
    {
        RpPlaneSector      *planeSector = (RpPlaneSector *) rootSector;

        planeSector->leftSubTree =
            ImportWorldFixupTJunctions(planeSector->leftSubTree,
                                       cutVertexList, conversionParams,
                                       resplit, ExitRequested,
                                       UserDataCallBacks);
        planeSector->rightSubTree =
            ImportWorldFixupTJunctions(planeSector->rightSubTree,
                                       cutVertexList, conversionParams,
                                       resplit, ExitRequested,
                                       UserDataCallBacks);
    }
    else
    {
        RwInt32             cut;
        RtWorldImportBuildSector *buildSector =
            (RtWorldImportBuildSector *) rootSector;

        for (cut = 0; cut < _rwSListGetNumEntriesMacro(cutVertexList);
             cut++)
        {

            _rwCutVertex       *cutVert = (_rwCutVertex *)
                rwSListGetEntry(cutVertexList, cut);

            ImportCutVertFixupTJunctions(cutVert,
                                         buildSector,
                                         conversionParams,
                                         UserDataCallBacks);

        }

        /* potentially split buildsector if no longer acceptable */
        if (!ImportBuildSectorAccept(buildSector, conversionParams))
        {
            rootSector = (RpSector *)
                ImportBuildSectorSplitRecurse(buildSector,
                                              conversionParams,
                                              1,
                                              cutVertexList,
                                              ExitRequested,
                                              UserDataCallBacks);
            *resplit = TRUE;
        }
    }

    RWRETURN(rootSector);
}

static void
ImportBuildSectorFindNormals(RtWorldImportBuildSector * buildSector)
{
    RwInt32             nI;
    RtWorldImportVertex *v0, *v1, *v2;
    RwV3d               edge[3];
    RwV3d               triNormal;
    RwReal              recip;
    RwReal              EFsinTheta;
    RwReal              EFcosTheta;

    RtWorldImportBuildVertex *boundaries;

    RWFUNCTION(RWSTRING("ImportBuildSectorFindNormals"));

    /*
     * Wipe vertex normals
     */
    for (nI = 0; nI < buildSector->numVertices; nI++)
    {
        RtWorldImportVertex *const vpVert = &buildSector->vertices[nI];
        RwV3d              *const normal = &vpVert->normal;

        normal->x = 0.0f;
        normal->y = 0.0f;
        normal->z = 0.0f;

        /*
         */

        vpVert->state.vpBuildVert = (RtWorldImportBuildVertex *) NULL;
    }

    /*
     * Accumulate normal contributions from polygons
     */
    boundaries = buildSector->boundaries;
    for (nI = 0; nI < buildSector->numPolygons; nI++)
    {
        RtWorldImportBuildVertex *const relative = boundaries;
        RwReal              angle[3];
        RwV3d               scaledNormal;

        /* Calculate the normal */
        v0 = boundaries++->mode.vpVert;
        v1 = boundaries++->mode.vpVert;
        v2 = boundaries++->mode.vpVert;

        RWASSERT(NULL == boundaries->mode.vpVert);
        boundaries++;

        RwV3dSub(&edge[0], &v1->OC, &v0->OC);
        RwV3dSub(&edge[1], &v2->OC, &v1->OC);
        RwV3dSub(&edge[2], &v0->OC, &v2->OC);

        /* Calculate the polygon normal */
        RwV3dCrossProduct(&triNormal, &edge[0], &edge[1]);

        EFsinTheta = RwV3dDotProduct(&triNormal, &triNormal);
        EFsinTheta = ((RwReal) sqrt(EFsinTheta));

        if (EFsinTheta <= (RwReal) 0)
            continue;

        recip = ((RwReal) 1) / EFsinTheta;

        RwV3dScale(&triNormal, &triNormal, recip);

        /*
         * Calculate internal angles
         */

        EFcosTheta = -RwV3dDotProduct(&edge[0], &edge[2]);
        angle[0] = (RwReal) RwATan2(EFsinTheta, EFcosTheta);

        EFcosTheta = -RwV3dDotProduct(&edge[1], &edge[0]);
        angle[1] = (RwReal) RwATan2(EFsinTheta, EFcosTheta);

        EFcosTheta = -RwV3dDotProduct(&edge[2], &edge[1]);
        angle[2] = (RwReal) RwATan2(EFsinTheta, EFcosTheta);

#if (0 && 1)
        RWMONITOR(("Internal angles %g %g %g sum %g",
                   RWRAD2DEG(angle[0]),
                   RWRAD2DEG(angle[1]),
                   RWRAD2DEG(angle[2]),
                   RWRAD2DEG(angle[0] + angle[1] + angle[2])));
#endif /* (0 && 1) */

        /*
         * Add the normal to all of the triangle's vertices
         * and remember most recent contributor in case
         * final sum turns out to be degenerate
         */
        RwV3dScale(&scaledNormal, &triNormal, angle[0]);
        RwV3dAdd(&v0->normal, &v0->normal, &scaledNormal);
        v0->state.vpBuildVert = relative;

        RwV3dScale(&scaledNormal, &triNormal, angle[1]);
        RwV3dAdd(&v1->normal, &v1->normal, &scaledNormal);
        v1->state.vpBuildVert = relative;

        RwV3dScale(&scaledNormal, &triNormal, angle[2]);
        RwV3dAdd(&v2->normal, &v2->normal, &scaledNormal);
        v2->state.vpBuildVert = relative;
    }

    /*
     * Make vertex normals of unit length;
     */

    for (nI = 0; nI < buildSector->numVertices; nI++)
    {
        RtWorldImportVertex *const vpVert = &buildSector->vertices[nI];
        RwV3d              *const normal = &vpVert->normal;

        EFsinTheta = RwV3dDotProduct(normal, normal);
        EFsinTheta = ((RwReal) sqrt(EFsinTheta));

        if (EFsinTheta > ((RwReal) 0))
        {
            recip = ((RwReal) 1) / EFsinTheta;

            RwV3dScale(normal, normal, recip);
        }
        else
        {
            /*
             * degenerate sum --
             * find the most recent contributor
             * and use norm lfrom that
             */
            RtWorldImportBuildVertex *const relative =
                vpVert->state.vpBuildVert;

#if (0)
            RWMONITOR(("Degenerate total normal - %p relative",
                       relative));
#endif /* (0) */

            if (relative)
            {

                /* Calculate the normal */
                v0 = relative[0].mode.vpVert;
                v1 = relative[1].mode.vpVert;
                v2 = relative[2].mode.vpVert;

                RwV3dSub(&edge[0], &v1->OC, &v0->OC);
                RwV3dSub(&edge[1], &v2->OC, &v1->OC);

                /* Calculate the polygon normal */
                RwV3dCrossProduct(&triNormal, &edge[0], &edge[1]);
                EFsinTheta = RwV3dDotProduct(&triNormal, &triNormal);
                /*
                 * Only non-degenerate normals were remembered
                 */
                RWASSERT(EFsinTheta > 0.0f);
                recip = ((RwReal) 1) / ((RwReal) sqrt(EFsinTheta));
                RwV3dScale(normal, &triNormal, recip);
            }
        }
    }

    RWRETURNVOID();
}

/****************************************************************************
 _rtImportBuildSectorCreateFromNoHSWorld

 On entry   : NoHSWorld
 On exit    : Build sector
 */

RtWorldImportBuildSector *
_rtImportBuildSectorCreateFromNoHSWorld(RtWorldImport * wpNoHS,
                                        RtWorldImportParameters *
                                        conversionParams,
                                        RpMaterialList * matList,
                                        RtWorldImportUserdataCallBacks *
                                        UserDataCallBacks)
{
    RtWorldImportBuildSector *buildSector;
    RtWorldImportBuildVertex *boundaries;
    RwInt32             nI, nJ;

    RWFUNCTION(RWSTRING("_rtImportBuildSectorCreateFromNoHSWorld"));

    RWASSERT(wpNoHS);

    buildSector = _rtImportBuildSectorCreate();
    if (!buildSector)
    {
        RWRETURN((RtWorldImportBuildSector *) NULL);
    }

    /* copy over the vertices */
    buildSector->numVertices = wpNoHS->numVertices;
    if (wpNoHS->numVertices)
    {
        buildSector->vertices = (RtWorldImportVertex *)
            RwMalloc(sizeof(RtWorldImportVertex) *
                     buildSector->numVertices);
        if (!buildSector->vertices)
        {
            RWERROR((E_RW_NOMEM,
                     sizeof(RtWorldImportVertex) *
                     buildSector->numVertices));
            _rtImportBuildSectorDestroy(buildSector, UserDataCallBacks);
            RWRETURN((RtWorldImportBuildSector *) NULL);
        }
        memcpy(buildSector->vertices, wpNoHS->vertices,
               sizeof(RtWorldImportVertex) * buildSector->numVertices);
        /* does not have preliting */

        /* Clear any texture coordinates that aren't being used */
        if (conversionParams->numTexCoordSets < rwMAXTEXTURECOORDS)
        {
            for (nI = 0; nI < buildSector->numVertices; nI++)
            {
                for (nJ = conversionParams->numTexCoordSets; nJ < rwMAXTEXTURECOORDS; nJ++)
                {
                    buildSector->vertices[nI].texCoords[nJ].u = 0.0f;
                    buildSector->vertices[nI].texCoords[nJ].v = 0.0f;
                }
            }
        }

        if ((conversionParams->flags & rpWORLDPRELIT) == 0)
        {
            for (nI = 0; nI < buildSector->numVertices; nI++)
            {
                buildSector->vertices[nI].preLitCol.red = 0;
                buildSector->vertices[nI].preLitCol.green = 0;
                buildSector->vertices[nI].preLitCol.blue = 0;
                buildSector->vertices[nI].preLitCol.alpha = 0;
            }
        }

        /* initialise material indices */
        for (nI = 0; nI < buildSector->numVertices; nI++)
        {
            buildSector->vertices[nI].matIndex = -1;
        }
    }

    /* build polygon boundaries */
    buildSector->numPolygons = wpNoHS->numPolygons;
    buildSector->numBoundaries = wpNoHS->numPolygons * (3 + 1);
    if (wpNoHS->numPolygons)
    {
        buildSector->boundaries = (RtWorldImportBuildVertex *)
            RwMalloc(sizeof(RtWorldImportBuildVertex) *
                     buildSector->numBoundaries);
        if (!buildSector->boundaries)
        {
            RWERROR((E_RW_NOMEM,
                     sizeof(RtWorldImportBuildVertex) *
                     buildSector->numBoundaries));
            _rtImportBuildSectorDestroy(buildSector, UserDataCallBacks);
            RWRETURN((RtWorldImportBuildSector *) NULL);
        }
        boundaries = buildSector->boundaries;

#if (0 && defined(RWVERBOSE))
        {
            RwInt32             matIndex =
                wpNoHS->matList.numMaterials - 1;
            for (nI = 0; nI < wpNoHS->numPolygons; nI++)
                wpNoHS->polygons[nI].matIndex = matIndex;
        }
#endif /* (0 && defined(RWVERBOSE)) */

        for (nI = 0; nI < wpNoHS->numPolygons; nI++)
        {
            /* From RtWorldImportTriangle */
            RwInt32             matIndex =
                wpNoHS->polygons[nI].matIndex;
            RpMaterial         *mat = rpMaterialListGetMaterial(matList,
                                                                matIndex);
            RwTexture          *tex = RpMaterialGetTexture(mat);
            RwChar             *tname = (tex ?
                                         RwTextureGetMaskName(tex) :
                                         (char *) NULL);

            for (nJ = 0; nJ < 3; nJ++)
            {
                RtWorldImportBuildVertexMode *const mode =
                    &boundaries->mode;
                const RwInt32       index =
                    wpNoHS->polygons[nI].vertIndex[nJ];

                mode->vpVert = &buildSector->vertices[index];
                boundaries++;
            }

            /* mark end of polygon boundary (and store polygon info) */
            boundaries->mode.vpVert = (RtWorldImportVertex *) NULL;
            boundaries->pinfo.matIndex =
                (RwInt16) wpNoHS->polygons[nI].matIndex;
            boundaries->pinfo.hasAlpha =
                (mat->color.alpha != 255) || (tex && tname && tname[0]);
            /* assign the userdata pointer to the boundaries and
             * remove it from the polygons */
            boundaries->pinfo.pUserdata =
                wpNoHS->polygons[nI].pUserdata;
            wpNoHS->polygons[nI].pUserdata = NULL;

            boundaries++;
        }

        /* condition geometry */
        if (conversionParams->calcNormals)
        {
            ImportBuildSectorFindNormals(buildSector);
        }

        if (conversionParams->conditionGeometry)
        {
            _rtImportBuildSectorConditionGeometry(wpNoHS, buildSector,
                                                  conversionParams,
                                                  matList);
        }

        /* Calculate the bounding box */
        _rtImportBuildSectorFindBBox(buildSector,
                                     &buildSector->boundingBox);

        if (conversionParams->userSpecifiedBBox)
        {
            RwBBox             *const sectorBox =
                &buildSector->boundingBox;
            const RwBBox       *const userBox =
                &conversionParams->userBBox;

            if (sectorBox->sup.x < userBox->sup.x)
            {
                sectorBox->sup.x = userBox->sup.x;
            }
            if (sectorBox->sup.y < userBox->sup.y)
            {
                sectorBox->sup.y = userBox->sup.y;
            }
            if (sectorBox->sup.z < userBox->sup.z)
            {
                sectorBox->sup.z = userBox->sup.z;
            }
            if (sectorBox->inf.x > userBox->inf.x)
            {
                sectorBox->inf.x = userBox->inf.x;
            }
            if (sectorBox->inf.y > userBox->inf.y)
            {
                sectorBox->inf.y = userBox->inf.y;
            }
            if (sectorBox->inf.z > userBox->inf.z)
            {
                sectorBox->inf.z = userBox->inf.z;
            }
        }
    }
    else if (conversionParams->userSpecifiedBBox)
    {
        buildSector->boundingBox = conversionParams->userBBox;
    }

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

RpWorld            *
_rtImportWorldCreateWorld(RtWorldImport * nohsworld,
                          RtWorldImportParameters *
                          conversionParams,
                          RwBool * ExitRequested,
                          RtWorldImportUserdataCallBacks
                          * UserDataCallBacks)
{
    RtWorldImportBuildSector *buildSector;
    RpSector           *rootSector, *rootWorldSector;
    RpWorld            *world;
    RwInt32             nI;
    RwBool              newSplits = TRUE;
    RwSList            *cutVertexList = (RwSList *) NULL;

    RWFUNCTION(RWSTRING("_rtImportWorldCreateWorld"));
    RWASSERT(nohsworld);
    RWASSERT(conversionParams);

    /* reset ExitRequested to FALSE */
    *ExitRequested = FALSE;

    /* verify RtWorldImport */
    for (nI = 0; nI < nohsworld->numPolygons; nI++)
    {
        RwInt32             nK;
        const RwInt32       matIndex = nohsworld->polygons[nI].matIndex;
        RwInt32            *const vertIndex =
            nohsworld->polygons[nI].vertIndex;
        if (matIndex < 0)
        {
            RWRETURN((RpWorld *) NULL);
        }
        if (matIndex >=
            rpMaterialListGetNumMaterials(&nohsworld->matList))
        {
            RWRETURN((RpWorld *) NULL);
        }

        for (nK = 0; nK < 3; nK++)
        {
            if (vertIndex[nK] < 0)
            {
                RWRETURN((RpWorld *) NULL);
            }
            if (vertIndex[nK] >= nohsworld->numVertices)
            {
                RWRETURN((RpWorld *) NULL);
            }
        }
    }

    _rtImportSetWeldThresholdPositional
        (conversionParams->weldThreshold);
    _rtImportSetWeldThresholdAngular
        (conversionParams->angularThreshold);

    /* Create a sector ready for some partitioning */
    buildSector =
        _rtImportBuildSectorCreateFromNoHSWorld(nohsworld,
                                                conversionParams,
                                                &nohsworld->matList,
                                                UserDataCallBacks);

    if (!buildSector)
    {
        RWRETURN((RpWorld *) NULL);
    }

    /*
     * * create a world to store the tree
     * * (trash default single sector at root)
     */
    world = RpWorldCreate(&buildSector->boundingBox);

    /* Reset the progress counts */
    _rtWorldImportTotalPolysInWorld = 0;
    _rtWorldImportNumPolysInLeaves = 0;
    _rtWorldImportNumPolysInCompressedLeaves = 0;
    cutVertexList = rwSListCreate(sizeof(_rwCutVertex));

    /* Start splitting up the world */
    _rtWorldImportTotalPolysInWorld = buildSector->numPolygons;
    _rtImportWorldSendProgressMessage
        (rtWORLDIMPORTPROGRESSBSPBUILDSTART, 0.0f);
    rootSector = (RpSector *)
        ImportBuildSectorSplitRecurse(buildSector,
                                      conversionParams,
                                      1,
                                      cutVertexList,
                                      ExitRequested, UserDataCallBacks);
    if (!rootSector)
    {

        /* Hasn't been able to split the world */
        RpWorldDestroy(world);
        _rtImportBuildSectorDestroy(buildSector, UserDataCallBacks);
        RWRETURN((RpWorld *) NULL);
    }

    /* check on T-Junctions created and fix 'em up */
    if (conversionParams->fixTJunctions)
    {
        while (newSplits)
        {
            newSplits = FALSE;
            rootSector =
                ImportWorldFixupTJunctions(rootSector,
                                           cutVertexList,
                                           conversionParams,
                                           &newSplits,
                                           ExitRequested,
                                           UserDataCallBacks);
        }
    }

#ifdef RWDEBUG

    /* In case anyone is tracking SList entry allocations */
    while (_rwSListGetNumEntriesMacro(cutVertexList))
    {
        rwSListDestroyEntry(cutVertexList,
                            _rwSListGetNumEntriesMacro(cutVertexList) -
                            1);
    }
#endif
    /* RWDEBUG */
    rwSListDestroy(cutVertexList);
    _rtImportWorldSendProgressMessage
        (rtWORLDIMPORTPROGRESSBSPBUILDEND, 0.0f);

    /* Compress into the use format */
    _rtImportWorldSendProgressMessage
        (rtWORLDIMPORTPROGRESSBSPCOMPRESSSTART, 0.0f);
    RpWorldSetFlags(world, conversionParams->flags);
    world->numTexCoordSets = conversionParams->numTexCoordSets;
    rootWorldSector =
        _rtImportWorldSectorCompressTree
        (rootSector, world, &nohsworld->matList, UserDataCallBacks);

    if (!rootWorldSector)
    {

        /* Hasn't been able to compress the world */
        RpWorldDestroy(world);
        _rtImportPlaneSectorDestroyTree
            ((RtWorldImportBuildPlaneSector *) rootSector,
             UserDataCallBacks);
        RWRETURN((RpWorld *) NULL);
    }
    _rtImportWorldSendProgressMessage
        (rtWORLDIMPORTPROGRESSBSPCOMPRESSEND, 0.0f);

    /* ok so kill default sector in world */
    rwPluginRegistryDeInitObject(&sectorTKList, world->rootSector);
    RwFree(world->rootSector);
    world->rootSector = rootWorldSector;

    /* Store the bounding box */
    rpWorldFindBBox(world, &world->boundingBox);

    /* Set up other miscellaneous things */
    RpWorldSetSurfaceProperties
        (world, RtWorldImportGetSurfaceProperties(nohsworld));

    /* Make it usable (create meshes, etc) */
    rpWorldUnlock(world);

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