/*
 * Converting no hs worlds to real binary worlds (with bsps).
 * No HS worlds are used in the generation process of worlds
 *
 * Copyright (c) 1998 Criterion Software Ltd.
 */

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

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

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

#include "nhsbary.h"
#include "nhswing.h"
#include "nhscond.h"

#if (!defined(DOXYGEN))
static const char   rcsid[] __RWUNUSED__ =
    "@@@@(#)$Id: nhscond.c,v 1.101 2001/10/03 10:30:02 markf Exp $";
#endif /* (!defined(DOXYGEN)) */

#if (!defined(BuildSectorWrite))
#define BuildSectorWrite(_limit, _name) /* No op */
#endif /* (!defined(BuildSectorWrite)) */

/****************************************************************************
 Local Types
 */

typedef struct _rwUVSortVertex _rwUVSortVertex;
struct _rwUVSortVertex
{
    RtWorldImportVertex *vpVert;
    RwReal              u;
    RwReal              v;
    RwInt32             boundary;
};

typedef struct RwRGBAUInt32 RwRGBAUInt32;
struct RwRGBAUInt32
{
    RwUInt32            red, green, blue, alpha;
};

typedef struct RtWorldImportCongruentVertex
    RtWorldImportCongruentVertex;

/*  maintained in Bin-tree  */
#define CONGRUENTVERTEXCHILDREN 2

struct RtWorldImportCongruentVertex
{
    RwInt32             destIdx;
    RtWorldImportVertex vertex;
    RtWorldImportVertex Mean;
    RwRGBAUInt32        preLitMean;
    RwInt32             refCount;
    RtWorldImportCongruentVertex *child[CONGRUENTVERTEXCHILDREN];
};

/*  maintained in Quad-tree  */
#define WELDVERTEXCHILDREN 4
struct RtWorldImportWeldVertex
{
    RtWorldImportVertex *sourcePtr;
    RtWorldImportCongruentVertex *CongruentVertex;
    RtWorldImportWeldVertex *child[WELDVERTEXCHILDREN];
};

typedef struct RtWeldVertexHash RtWeldVertexHash;
struct RtWeldVertexHash
{
    RtWorldImportWeldVertex *root;
};

#if (defined(_MSC_VER) && defined (RWVERBOSE) && defined(RWDEBUG))
static RwUInt32    *vert_hash_hit = (RwUInt32 *) NULL;

#define VERT_HASH_HIT(_hash_val)  vert_hash_hit[_hash_val]++;
#endif /* (defined(_MSC_VER) && defined (RWVERBOSE) && defined(RWDEBUG)) */

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

typedef struct RtWeldPolygonVerticesState RtWeldPolygonVerticesState;
struct RtWeldPolygonVerticesState
{
    RtWeldVertexHash   *hash;
    RtWorldImportVertex *vertices;
    RwFreeList         *CongruentFreeList;
    RwFreeList         *WeldFreeList;
    RtWorldImportParameters *conversionParams;
    RwInt32             PreNumVertices;
    RwInt32             PostNumVertices;
    RwInt32             translations;
};

typedef struct RwCentroidSort RwCentroidSort;
struct RwCentroidSort
{
    RwV3d               point;
    RwInt32             index;
};

/* A union which permits us to convert between a RwReal and a 32 bit
   int.  */

typedef union _rtFloatIntUnion _rtFloatIntUnion;
union _rtFloatIntUnion
{
    RwReal              value;
    RwUInt32            word;
};

/****************************************************************************
 Local (Static) Prototypes
 */

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

#if (defined(__ICL))
#if (500 <=__ICL)
#define ImportFloor(_x)  ImportFloorf(_x)
#endif /* (500 <=__ICL) */
#endif /* (defined(__ICL)) */

#if (!defined(ImportFloor))
#define ImportFloor(_x)  ((RwReal)RwFloor(_x))
#endif /* (!defined(ImportFloor)) */

#define _TEXCOORD_EPSILON (((RwReal)1)/((RwReal)(1<<4)))
#define _TEXCOORD_EPSILON_2 (_TEXCOORD_EPSILON + _TEXCOORD_EPSILON)

#define ABSOLUTE_TEX(_X)       /* No op */

#define RELATIVE_TEX(_X)                                              \
MACRO_START                                                           \
{                                                                     \
    RwReal fraction = (_X) - ImportFloor(_X);                         \
                                                                      \
    (_X)= fraction;                                                   \
}                                                                     \
MACRO_STOP

#define CmpTexCoordsMacro(result, VertA, VertB, CONGRUENCE)           \
MACRO_START                                                           \
{                                                                     \
    RwSplitBits coord;                                                \
                                                                      \
    /* on UV */                                                       \
    coord.nReal = ( _TEXCOORD_EPSILON +                               \
                    VertA->texCoords[0].u -                           \
                    VertB->texCoords[0].u );                          \
    CONGRUENCE(coord.nReal);                                          \
    if ( (coord.nReal < (RwReal)0) ||                                 \
         (coord.nReal > _TEXCOORD_EPSILON_2) )                        \
    {                                                                 \
        result = coord.nInt;                                          \
    }                                                                 \
    else                                                              \
    {                                                                 \
        coord.nReal = ( _TEXCOORD_EPSILON +                           \
                        VertA->texCoords[0].v -                       \
                        VertB->texCoords[0].v );                      \
        CONGRUENCE(coord.nReal);                                      \
        if ( (coord.nReal < (RwReal)0) ||                             \
             (coord.nReal > _TEXCOORD_EPSILON_2) )                    \
        {                                                             \
            result = coord.nInt;                                      \
        }                                                             \
        else                                                          \
        {                                                             \
            /* on UV2 */                                              \
            coord.nReal = ( _TEXCOORD_EPSILON +                       \
                            VertA->texCoords[1].u -                   \
                            VertB->texCoords[1].u );                  \
            CONGRUENCE(coord.nReal);                                  \
            if ( (coord.nReal < (RwReal)0) ||                         \
                 (coord.nReal > _TEXCOORD_EPSILON_2) )                \
            {                                                         \
                result = coord.nInt;                                  \
            }                                                         \
            else                                                      \
            {                                                         \
                coord.nReal = ( _TEXCOORD_EPSILON +                   \
                                VertA->texCoords[1].v -               \
                                VertB->texCoords[1].v );              \
                CONGRUENCE(coord.nReal);                              \
                if ( (coord.nReal < (RwReal)0) ||                     \
                     (coord.nReal > _TEXCOORD_EPSILON_2) )            \
                {                                                     \
                    result = coord.nInt;                              \
                }                                                     \
            }                                                         \
        }                                                             \
    }                                                                 \
}                                                                     \
MACRO_STOP

#define CmpPropertiesMacro(result, VertA, VertB)                      \
MACRO_START                                                           \
{                                                                     \
    RwInt32 texDiff = 0;                                              \
                                                                      \
    /* on UV */                                                       \
    CmpTexCoordsMacro(texDiff, VertA, VertB, RELATIVE_TEX);           \
    if (texDiff)                                                      \
    {                                                                 \
        result = texDiff;                                             \
    }                                                                 \
    else                                                              \
    {                                                                 \
        /* on preLit colour */                                        \
        RwInt32 nDelta;                                               \
        nDelta = ( VertA->preLitCol.red -                             \
                   VertB->preLitCol.red );                            \
        if (nDelta < -1)                                              \
        {                                                             \
            result = (-1);                                            \
                                                                      \
        }                                                             \
        else if (nDelta > 1)                                          \
        {                                                             \
            result = (1);                                             \
                                                                      \
        }                                                             \
        else                                                          \
        {                                                             \
            nDelta = ( VertA->preLitCol.green -                       \
                       VertB->preLitCol.green );                      \
            if (nDelta < -1)                                          \
            {                                                         \
                result = (-1);                                        \
            }                                                         \
            else if (nDelta > 1)                                      \
            {                                                         \
                result = (1);                                         \
            }                                                         \
            else                                                      \
            {                                                         \
                nDelta = ( VertA->preLitCol.blue -                    \
                           VertB->preLitCol.blue );                   \
                if (nDelta < -1)                                      \
                {                                                     \
                    result = (-1);                                    \
                }                                                     \
                else if (nDelta > 1)                                  \
                {                                                     \
                    result = (1);                                     \
                }                                                     \
                else                                                  \
                {                                                     \
                    nDelta = ( VertA->preLitCol.alpha -               \
                               VertB->preLitCol.alpha);               \
                    if (nDelta < -1)                                  \
                    {                                                 \
                        result = (-1);                                \
                    }                                                 \
                    if (nDelta > 1)                                   \
                    {                                                 \
                        result = (1);                                 \
                    }                                                 \
                }                                                     \
            }                                                         \
        }                                                             \
    }                                                                 \
}                                                                     \
MACRO_STOP

#define CmpPositionsMacro(result, VertA, VertB)                       \
MACRO_START                                                           \
{                                                                     \
    /* Compare Position */                                            \
    RwSplitBits shift;                                                \
                                                                      \
    shift.nReal = ( VertA->OC.x - VertB->OC.x );                      \
    if ( (shift.nReal < -WeldThresholdPositional) ||                  \
         (shift.nReal > (WeldThresholdPositional)) )                  \
    {                                                                 \
        result = shift.nInt;                                          \
    }                                                                 \
    else                                                              \
    {                                                                 \
        shift.nReal = ( VertA->OC.y - VertB->OC.y );                  \
        if ( (shift.nReal < -WeldThresholdPositional) ||              \
             (shift.nReal > (WeldThresholdPositional)) )              \
        {                                                             \
            result = shift.nInt;                                      \
        }                                                             \
        else                                                          \
        {                                                             \
            shift.nReal = ( VertA->OC.z - VertB->OC.z );              \
            if ( (shift.nReal < -WeldThresholdPositional) ||          \
                 (shift.nReal > (WeldThresholdPositional)) )          \
            {                                                         \
                result = shift.nInt;                                  \
            }                                                         \
        }                                                             \
    }                                                                 \
}                                                                     \
MACRO_STOP

#define CmpNormalsMacro(result, VertA, VertB)                           \
MACRO_START                                                             \
{                                                                       \
    RwSplitBits cone;                                                   \
                                                                        \
    cone.nReal = RwV3dDotProduct(&VertA->normal,                        \
                                 &VertB->normal);                       \
                                                                        \
    result = (cone.nReal < WeldThresholdAngular);                       \
                                                                        \
    if (result)                                                         \
    {                                                                   \
        cone.nReal = ( VertA->normal.x - VertB->normal.x);              \
        if (cone.nInt)                                                  \
        {                                                               \
            result = cone.nInt;                                         \
        }                                                               \
        else                                                            \
        {                                                               \
            cone.nReal = ( VertA->normal.y - VertB->normal.y);          \
            if (cone.nInt)                                              \
            {                                                           \
                result = cone.nInt;                                     \
            }                                                           \
            else                                                        \
            {                                                           \
                cone.nReal = ( VertA->normal.z - VertB->normal.z);      \
                result = cone.nInt;                                     \
            }                                                           \
        }                                                               \
    }                                                                   \
}                                                                       \
MACRO_STOP

#define ImportUVSortVertexCmpMacro(result, _a, _b)                    \
MACRO_START                                                           \
{                                                                     \
    RwSplitBits         _difference;                                  \
    const _rwUVSortVertex *const sortVertA =                          \
        (const _rwUVSortVertex *) (_a);                               \
    const _rwUVSortVertex *const sortVertB =                          \
        (const _rwUVSortVertex *) (_b);                               \
                                                                      \
    _difference.nInt = (sortVertA->vpVert - sortVertB->vpVert);       \
    if (!_difference.nInt)                                            \
    {                                                                 \
        _difference.nReal = (sortVertA->u - sortVertB->u);            \
        if (!_difference.nInt)                                        \
        {                                                             \
            _difference.nReal = (sortVertA->v - sortVertB->v);        \
        }                                                             \
    }                                                                 \
    result = _difference.nInt;                                        \
}                                                                     \
MACRO_STOP

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

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

#define  _RHUGE   ((RwReal) 1.0000000000e+30)

/* Get a 32 bit int from a float.  */

#define GET_FLOAT_WORD(i,d)                                           \
MACRO_START                                                           \
{                                                                     \
  _rtFloatIntUnion gf_u;                                              \
  gf_u.value = (d);                                                   \
  (i) = gf_u.word;                                                    \
}                                                                     \
MACRO_STOP

/* Set a RwReal from a 32 bit int.  */

#define SET_FLOAT_WORD(d,i)                                           \
MACRO_START                                                           \
{                                                                     \
  _rtFloatIntUnion sf_u;                                              \
  sf_u.word = (i);                                                    \
  (d) = sf_u.value;                                                   \
}                                                                     \
MACRO_STOP

#if (defined(RWDEBUG))
#define RWASSERTBOUNDARIES(buildSector)                         \
MACRO_START                                                     \
{                                                               \
    RwInt32 nI;                                                \
    for (nI = 0; nI < buildSector->numBoundaries; nI += 4)      \
    {                                                           \
        RtWorldImportBuildVertex *const boundary =              \
            &buildSector->boundaries[nI];                       \
                                                                \
        RWASSERT(boundary[0].mode.vpVert->matIndex ==           \
                 boundary[3].pinfo.matIndex);                   \
        RWASSERT(boundary[1].mode.vpVert->matIndex ==           \
                 boundary[3].pinfo.matIndex);                   \
        RWASSERT(boundary[2].mode.vpVert->matIndex ==           \
                 boundary[3].pinfo.matIndex);                   \
    }                                                           \
}                                                               \
MACRO_STOP
#endif /* (defined(RWDEBUG)) */

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

/****************************************************************************
 Globals (across program)
 */

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

static RwReal       WeldThresholdPositional = WELDTHRESHOLDPOSITIONAL;
static RwReal       WeldThresholdAngular = WELDTHRESHOLDANGULAR;

/****************************************************************************
 Functions
 */

#if (defined(__ICL))
#if (500 <=__ICL)

/*
 * Work around for Intel 5.0 compiler
 * problems with "floor()"
 */
static              RwReal
ImportFloorf(RwReal x)
{
    RwInt32             i0, j0;
    RwUInt32            i;

    RWFUNCTION(RWSTRING("ImportFloorf"));

    GET_FLOAT_WORD(i0, x);
    j0 = ((i0 >> 23) & 0xff) - 0x7f;
    if (j0 < 23)
    {
        if (j0 < 0)
        {                      /* raise inexact if x != 0 */
            if (_RHUGE + x > (RwReal) 0.0)
            {                  /* return 0*sign(x) if |x|<1 */
                if (i0 >= 0)
                {
                    i0 = 0;
                }
                else if ((i0 & 0x7fffffff) != 0)
                {
                    i0 = 0xbf800000;
                }
            }
        }
        else
        {
            i = (0x007fffff) >> j0;
            if ((i0 & i) == 0)
                RWRETURN(x);   /* x is integral */
            if (_RHUGE + x > (RwReal) 0.0)
            {                  /* raise inexact flag */
                if (i0 < 0)
                    i0 += (0x00800000) >> j0;
                i0 &= (~i);
            }
        }
    }
    else
    {
        if (j0 == 0x80)
            RWRETURN(x + x);   /* inf or NaN */
        else
            RWRETURN(x);       /* x is integral */
    }
    SET_FLOAT_WORD(x, i0);
    RWRETURN(x);
}

#endif /* (500 <=__ICL) */
#endif /* (defined(__ICL)) */

/***************************************************************************
 ***************************************************************************
                          Geometry Conditioning
 ***************************************************************************
 ***************************************************************************/

static              RwBool
ImportZeroAreaPolygon(const RwV3d * const c0,
                      const RwV3d * const c1, const RwV3d * const c2)
{
    RwBool              zero_area;
    RwDReal             area2;
    RwDV3d              e0, e1;
    RwDV3d              n;

    RWFUNCTION(RWSTRING("ImportZeroAreaPolygon"));

    RwV3dSubMacro(&e0, c1, c2);
    RwV3dSubMacro(&e1, c2, c0);

    RwV3dCrossProductMacro(&n, &e0, &e1);
    area2 = RwV3dDotProductMacro(&n, &n);
    zero_area = !(_AREA2_EPSILON < area2);

    RWRETURN(zero_area);
}

static void
ImportCullZeroAreaPolygons(RtWorldImportBuildSector * buildSector)
{
    RtWorldImportBuildVertex *boundaries;
    RwInt32             numBoundaries;
    RwInt32             numPolygons;
    RwInt32             PreNumPolygons;
    RwInt32             nI;
    RwInt32             bytes;

    RWFUNCTION(RWSTRING("ImportCullZeroAreaPolygons"));
    RWASSERT(NULL != buildSector);

    RWASSERT((buildSector->numPolygons * 4) ==
             (buildSector->numBoundaries));

    boundaries = buildSector->boundaries;

    numBoundaries = buildSector->numBoundaries;
    numPolygons = buildSector->numPolygons;
    PreNumPolygons = numPolygons;

    RWMONITOR(("%d == PreNumPolygons", (int) PreNumPolygons));

    nI = 0;
    while (nI < numBoundaries)
    {
        RwV3d              *const v0 =
            &boundaries[nI + 0].mode.vpVert->OC;
        RwV3d              *const v1 =
            &boundaries[nI + 1].mode.vpVert->OC;
        RwV3d              *const v2 =
            &boundaries[nI + 2].mode.vpVert->OC;
        const RwBool        ZeroArea =
            ImportZeroAreaPolygon(v0, v1, v2);

        if (ZeroArea)
        {
            numBoundaries -= 4;
            bytes =
                (numBoundaries - nI) * sizeof(RtWorldImportBuildVertex);

            memcpy(&boundaries[nI + 0], &boundaries[nI + 4], bytes);
            --numPolygons;
        }
        else
        {
            nI += 4;
        }
    }

    buildSector->numPolygons = numPolygons;
    buildSector->numBoundaries = numBoundaries;

    RWASSERT((buildSector->numPolygons * 4) ==
             (buildSector->numBoundaries));

    RWMONITOR(("%d == Post buildSector->numPolygons",
               (int) buildSector->numPolygons));

    RWMONITOR(("%d == delta [%d%%]\n",
               (int) (PreNumPolygons - buildSector->numPolygons),
               (PreNumPolygons ?
                ((100 *
                  (int) (PreNumPolygons -
                         buildSector->numPolygons)) /
                 (int) PreNumPolygons) : 0)));

    bytes = (numBoundaries) * sizeof(RtWorldImportBuildVertex);
    boundaries = (RtWorldImportBuildVertex *)
        RwRealloc(boundaries, bytes);

    if (boundaries)
    {
        buildSector->boundaries = boundaries;
    }

    RWRETURNVOID();
}

static void
ImportCullUnusedVertices(RtWorldImportBuildSector * buildSector)
{
    RtWorldImportBuildVertex *boundaries;
    RwInt32             numBoundaries;
    RwInt32             PreNumVertices;
    RwInt32             PostNumVertices;
    RwInt32             nI;

    RWFUNCTION(RWSTRING("ImportCullUnusedVertices"));
    RWASSERT(NULL != buildSector);

    numBoundaries = buildSector->numBoundaries;

    PreNumVertices = buildSector->numVertices;
    RWMONITOR(("%d == PreNumVertices", (int) PreNumVertices));

    /* unmark vertices */
    for (nI = 0; nI < PreNumVertices; nI++)
    {
        buildSector->vertices[nI].state.forwardingAddress = -1;
    }

    /* mark used */
    PostNumVertices = 0;

    boundaries = buildSector->boundaries;
    nI = numBoundaries;
    while (--nI >= 0)
    {

        RtWorldImportBuildVertexMode *const mode = &boundaries->mode;

        if ((mode->vpVert)
            && (mode->vpVert->state.forwardingAddress < 0))
        {
            mode->vpVert->state.forwardingAddress = PostNumVertices++;
        }
        boundaries++;
    }

    /* are there redundant vertices? */
    RWASSERT(PostNumVertices <= PreNumVertices);

    if (PostNumVertices != PreNumVertices)
    {
        const RwUInt32      bytes =
            sizeof(RtWorldImportVertex) * PostNumVertices;
        RtWorldImportVertex *vertices =
            (RtWorldImportVertex *) RwMalloc(bytes);

        /* copy across vertex iff used */
        for (nI = 0; nI < PreNumVertices; nI++)
        {
            const RwInt32       forwardingAddress =
                buildSector->vertices[nI].state.forwardingAddress;

            if (forwardingAddress >= 0)
            {
                vertices[forwardingAddress] = buildSector->vertices[nI];
            }

        }

        /* point boundaries to new vertex pool */
        boundaries = buildSector->boundaries;

        nI = numBoundaries;
        while (--nI >= 0)
        {
            RtWorldImportBuildVertexMode *const mode =
                &boundaries->mode;
            if (mode->vpVert)
            {
                const RwInt32       forwardingAddress =
                    mode->vpVert->state.forwardingAddress;
                mode->vpVert = &vertices[forwardingAddress];
            }
            boundaries++;
        }

        RwFree(buildSector->vertices);
        buildSector->vertices = vertices;
        buildSector->numVertices = PostNumVertices;
    }

    RWMONITOR(("%d == Post buildSector->numVertices",
               (int) buildSector->numVertices));

    RWMONITOR(("%d == delta [%d%%]\n",
               (int) (PreNumVertices - buildSector->numVertices),
               (PreNumVertices ?
                ((100 *
                  (int) (PreNumVertices -
                         buildSector->numVertices)) /
                 (int) PreNumVertices) : 0)));

    RWRETURNVOID();
}

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

static void
ImportNewVertex(RtWorldImportBuildSector * buildSector,
                RwInt32 nI, RwInt32 nJ)
{
    /* introduce new vertex */
    RwInt32             nK;

    RtWorldImportVertex *oldVert;
    RwInt32             PreNumVertices;
    RtWorldImportBuildVertexMode *mode;

    RWFUNCTION(RWSTRING("ImportNewVertex"));
    RWASSERT(NULL != buildSector);
    PreNumVertices = buildSector->numVertices;
    RWMONITOR(("%d == Pre buildSector->numVertices",
               (int) PreNumVertices));

    mode = &buildSector->boundaries[nI + nJ].mode;

    oldVert = mode->vpVert;

    buildSector->vertices[PreNumVertices] = *mode->vpVert;

    mode->vpVert = &buildSector->vertices[PreNumVertices];

    buildSector->numVertices++;

    mode->vpVert->matIndex =
        buildSector->boundaries[nI + 3].pinfo.matIndex;

    /* remap any other similar vertices using
     * this matIndex */
    for (nK = nI + nJ + 1; nK < buildSector->numBoundaries; nK++)
    {
        RtWorldImportBuildVertexMode *const modenK =
            &buildSector->boundaries[nK].mode;

        if (modenK->vpVert == oldVert &&
            buildSector->boundaries[((nK / 4) * 4) +
                                    3].pinfo.matIndex ==
            buildSector->boundaries[nI + 3].pinfo.matIndex)
        {
            modenK->vpVert = mode->vpVert;
        }
    }

    RWMONITOR(("%d == Post buildSector->numVertices",
               (int) buildSector->numVertices));
    RWMONITOR(("%d == delta [%d%%]\n",
               (int) (PreNumVertices - buildSector->numVertices),
               (PreNumVertices ?
                ((100 *
                  (int) (PreNumVertices -
                         buildSector->numVertices)) /
                 (int) PreNumVertices) : 0)));

    RWRETURNVOID();
}

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

static void
ImportUnshareVertex(RtWorldImportBuildSector * buildSector, RwInt32 nI)
{
    RwInt32             nJ;

    RWFUNCTION(RWSTRING("ImportUnshareVertex"));
    RWASSERT(NULL != buildSector);

    /* RWMONITOR(("%d == buildSector->numVertices",
     * (int) buildSector->numVertices)); */

    for (nJ = 0; nJ < 3; nJ++)
    {

        RtWorldImportBuildVertexMode *const mode =
            &buildSector->boundaries[nI + nJ].mode;

        if (mode->vpVert->matIndex == -1)
        {
            mode->vpVert->matIndex =
                buildSector->boundaries[nI + 3].pinfo.matIndex;
        }
        else if (mode->vpVert->matIndex !=
                 buildSector->boundaries[nI + 3].pinfo.matIndex)
        {
            ImportNewVertex(buildSector, nI, nJ);
        }

    }

    /* RWMONITOR(("%d == buildSector->numVertices",
     * (int) buildSector->numVertices)); */

    RWRETURNVOID();
}

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

    ImportUnshareVerticesOnMaterialBoundaries

    Ensure that vertices aren't shared between two polygons
    which have different materials

    Note: only works on triangle data
 */
static void
ImportUnshareVerticesOnMaterialBoundaries(RtWorldImportBuildSector
                                          * buildSector)
{
    RwInt32             nI;
    RtWorldImportVertex *newVertices;
    RwInt32             PreNumVertices;
    RwInt32             instanceCount;
    RwUInt32            bytes;

    RWFUNCTION(RWSTRING("ImportUnshareVerticesOnMaterialBoundaries"));

    PreNumVertices = buildSector->numVertices;
    RWMONITOR(("%d == PreNumVertices", (int) PreNumVertices));

    /* Move vertices into an array big enough for numTris * 3 verts
     * and remap the polygons */

    instanceCount = ((buildSector->numBoundaries / 4) * 3);

    bytes = sizeof(RtWorldImportVertex) * instanceCount;
    newVertices = (RtWorldImportVertex *) RwMalloc(bytes);

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

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

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

        RtWorldImportBuildVertexMode *const mode = &boundary->mode;

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

    /* now we'll unshare */
    for (nI = 0; nI < buildSector->numBoundaries; nI += 4)
    {
        ImportUnshareVertex(buildSector, nI);
    }

    /* Move vertices into an array of the actual size needed
     * and remap the polygons */
    bytes = sizeof(RtWorldImportVertex) * buildSector->numVertices;
    newVertices = (RtWorldImportVertex *) RwMalloc(bytes);
    memcpy(newVertices, buildSector->vertices, bytes);

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

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

        RtWorldImportBuildVertexMode *const mode = &boundary->mode;

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

    RWMONITOR(("%d == Post buildSector->numVertices",
               (int) buildSector->numVertices));

    RWMONITOR(("%d == delta [%d%%]\n",
               (int) (PreNumVertices - buildSector->numVertices),
               (PreNumVertices ?
                ((100 *
                  (int) (PreNumVertices -
                         buildSector->numVertices)) /
                 (int) PreNumVertices) : 0)));

    RWASSERTBOUNDARIES(buildSector);

    RWRETURNVOID();
}

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

static void
ImportSortVerticesOnMaterial(RtWorldImportBuildSector * buildSector,
                             RpMaterialList * matList)
{
    RwInt32             nI, nJ;
    RwInt32             vertIndex = 0;
    RtWorldImportVertex *newVertices;
    RwInt32             PreNumVertices;
    RwUInt32            bytes;

    RWFUNCTION(RWSTRING("ImportSortVerticesOnMaterial"));
    RWASSERT(NULL != buildSector);

    PreNumVertices = buildSector->numVertices;
    RWMONITOR(("%d == PreNumVertices", (int) PreNumVertices));

    bytes = sizeof(RtWorldImportVertex) * PreNumVertices;
    newVertices = (RtWorldImportVertex *) RwMalloc(bytes);

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

    for (nI = 0; nI < rpMaterialListGetNumMaterials(matList); nI++)
    {
        for (nJ = 0; nJ < PreNumVertices; nJ++)
        {
            if (buildSector->vertices[nJ].matIndex == nI)
            {
                newVertices[vertIndex] = buildSector->vertices[nJ];
                buildSector->vertices[nJ].state.vpVert =
                    (&newVertices[vertIndex]);
                vertIndex++;
            }
        }
    }

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

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

    RwFree(buildSector->vertices);
    buildSector->vertices = newVertices;
    RWMONITOR(("%d == Post buildSector->numVertices",
               (int) buildSector->numVertices));
    RWMONITOR(("%d == delta [%d%%]\n",
               (int) (PreNumVertices - buildSector->numVertices),
               (PreNumVertices
                ? ((100 *
                    (int) (PreNumVertices -
                           buildSector->numVertices)) /
                   (int) PreNumVertices) : 0)));


    RWASSERTBOUNDARIES(buildSector);

    RWRETURNVOID();
}

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

static int          RWCDECL
ImportUVSortVertexCmp(const void *a, const void *b)
{
    int                 result;

    RWFUNCTION(RWSTRING("ImportUVSortVertexCmp"));

    ImportUVSortVertexCmpMacro(result, a, b);

    RWRETURN(result);
}

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

static void
ImportNonNegativeUVs(RtWorldImportBuildSector * buildSector)
{
    RwInt32             numVertices;

    RWFUNCTION(RWSTRING("ImportNonNegativeUVs"));
    RWASSERT(NULL != buildSector);

    /* RWMONITOR(("Shift all of the texcoord values into positive space")); */

    numVertices = buildSector->numVertices;

    if (0 < numVertices)
    {
        RtWorldImportVertex *const vertices = buildSector->vertices;
        const RwTexCoords  *const firstCoords = &vertices[0].texCoords[0];
        RwInt32             nI;
        RwTexCoords         minCoord;
        RwTexCoords         shift;

        minCoord.u = firstCoords->u;
        minCoord.v = firstCoords->v;

        for (nI = 1; nI < numVertices; nI++)
        {
            const RwTexCoords  *const texCoords =
                &vertices[nI].texCoords[0];

            minCoord.u = RwRealMin2(minCoord.u, texCoords->u);
            minCoord.v = RwRealMin2(minCoord.v, texCoords->v);
        }

        shift.u = -ImportFloor(minCoord.u);
        shift.v = -ImportFloor(minCoord.v);

        RWASSERT(0 <= (minCoord.u + shift.u));
        RWASSERT(0 <= (minCoord.v + shift.v));

        if (((shift.u > (RwReal) 0.0) || (shift.v > (RwReal) 0.0)))
        {
            for (nI = 0; nI < numVertices; nI++)
            {
                RwTexCoords         oldCoords;
                RwTexCoords        *const texCoords =
                    &vertices[nI].texCoords[0];

                oldCoords.u = texCoords->u;
                oldCoords.v = texCoords->v;
                texCoords->u = oldCoords.u + shift.u;
                texCoords->v = oldCoords.v + shift.v;
                RWASSERT(0 <= texCoords->u);
                RWASSERT(0 <= texCoords->v);
            }
        }
    }

    RWRETURNVOID();

}

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

static void
ImportLimitUVs(RtWorldImportBuildSector * buildSector, RwReal uvLimit)
{
    RtWorldImportVertex *newVertices;
    RwInt32             instanceCount;
    RwInt32             nI;
    RwInt32             numBoundaries;
    RtWorldImportBuildVertex *boundaries;
    RwInt32             numVerts;
    RwInt32             vertIndex;
    RwTexCoords         maxCoord;
    RwTexCoords         minCoord;
    RwUInt32            bytes;
    _rwUVSortVertex    *sortVerts;

    RWFUNCTION(RWSTRING("ImportLimitUVs"));
    RWASSERT(NULL != buildSector);

    ImportNonNegativeUVs(buildSector);

    boundaries = buildSector->boundaries;
    numBoundaries = buildSector->numBoundaries;
    instanceCount = (numBoundaries / 4) * 3;

    /* RWMONITOR(("Limit according to the upper bound")); */
    /* NOTE: this will fail to limit polygons which have
     * a UV range greater than uvLimit
     */
    vertIndex = 0;

    bytes = sizeof(_rwUVSortVertex) * instanceCount;
    sortVerts = (_rwUVSortVertex *) RwMalloc(bytes);

    for (nI = 0; nI < numBoundaries; nI++)
    {
        const RwInt32       firstVertInBoundary = nI;
        const RtWorldImportBuildVertex *const v0 = &boundaries[nI++];
        const RwTexCoords  *const v0_Coords =
            &v0->mode.vpVert->texCoords[0];
        const RtWorldImportBuildVertex *const v1 = &boundaries[nI++];
        const RwTexCoords  *const v1_Coords =
            &v1->mode.vpVert->texCoords[0];
        const RtWorldImportBuildVertex *const v2 = &boundaries[nI++];
        const RwTexCoords  *const v2_Coords =
            &v2->mode.vpVert->texCoords[0];
        RwInt32             modu = 0;
        RwInt32             modv = 0;
        RwInt32             nJ;

        RWASSERT(NULL == boundaries[nI].mode.vpVert);

        minCoord.u = v0_Coords->u;
        maxCoord.u = v0_Coords->u;
        minCoord.v = v0_Coords->v;
        maxCoord.v = v0_Coords->v;

        minCoord.u = RwRealMin2(minCoord.u, v1_Coords->u);
        maxCoord.u = RwRealMax2(maxCoord.u, v1_Coords->u);
        minCoord.v = RwRealMin2(minCoord.v, v1_Coords->v);
        maxCoord.v = RwRealMax2(maxCoord.v, v1_Coords->v);

        minCoord.u = RwRealMin2(minCoord.u, v2_Coords->u);
        maxCoord.u = RwRealMax2(maxCoord.u, v2_Coords->u);
        minCoord.v = RwRealMin2(minCoord.v, v2_Coords->v);
        maxCoord.v = RwRealMax2(maxCoord.v, v2_Coords->v);

        /* Neilb / See code above
         * - can't do the divide as this stops you using
         * the value at the limit, which is valid
         * ( also the code is broken
         * if (minCoord.u-modu<0) { modu -= uvLimit; }
         * is correct I think ).
         */
        while (minCoord.u > uvLimit)
        {
            minCoord.u -= uvLimit;
            maxCoord.u -= uvLimit;
            modu -= (RwInt32) uvLimit;
        }
        while (minCoord.v > uvLimit)
        {
            minCoord.v -= uvLimit;
            maxCoord.v -= uvLimit;
            modv -= (RwInt32) uvLimit;
        }

        /*
         * shift to bottom of range..
         * NOTE: this will lead to a row of polygons which
         * will break the stripping if the polygons
         * are not @ integer UV values.. solution - walk the triangles!
         */
        if (maxCoord.u > uvLimit)
        {
            const RwReal        floor_min_u = (RwReal)
                ((RwInt32) (minCoord.u));

            modu -= (RwInt32) floor_min_u;
        }
        if (maxCoord.v > uvLimit)
        {
            const RwReal        floor_min_v = (RwReal)
                ((RwInt32) (minCoord.v));

            modv -= (RwInt32) floor_min_v;
        }

        for (nJ = firstVertInBoundary; nJ < nI; nJ++)
        {
            _rwUVSortVertex    *const dest = &sortVerts[vertIndex];
            RtWorldImportBuildVertexMode *const mode =
                &boundaries[nJ].mode;

            dest->vpVert = mode->vpVert;
            dest->u = dest->vpVert->texCoords[0].u + modu;
            dest->v = dest->vpVert->texCoords[0].v + modv;
            dest->boundary = nJ;
            vertIndex++;
        }

    }

    /* RWMONITOR(("QuickSorting")); */

    qsort(sortVerts, instanceCount,
          sizeof(_rwUVSortVertex), ImportUVSortVertexCmp);

    numVerts = 0;
    /* Now count the number of unique vertices */

    if (instanceCount)
    {
        numVerts++;
        for (nI = 1; nI < instanceCount; nI++)
        {
            RwBool              difference;

            ImportUVSortVertexCmpMacro(difference,
                                       &sortVerts[nI - 1],
                                       &sortVerts[nI]);
            if (difference)
            {
                numVerts++;
            }

        }
    }

    /* RWMONITOR(("%d == numVerts ", (int) numVerts)); */

    bytes = sizeof(RtWorldImportVertex) * numVerts;
    newVertices = (RtWorldImportVertex *) RwMalloc(bytes);
    vertIndex = 0;

    if (instanceCount)
    {
        RtWorldImportBuildVertexMode *modenI;

        nI = 0;
        newVertices[vertIndex] = *(sortVerts[nI].vpVert);
        newVertices[vertIndex].texCoords[0].u = sortVerts[nI].u;
        newVertices[vertIndex].texCoords[0].v = sortVerts[nI].v;
        vertIndex++;

        modenI = &boundaries[sortVerts[nI].boundary].mode;

        modenI->vpVert = &(newVertices[vertIndex - 1]);

        for (nI = 1; nI < instanceCount; nI++)
        {
            RwBool              difference;

            modenI = &boundaries[sortVerts[nI].boundary].mode;

            ImportUVSortVertexCmpMacro(difference,
                                       &sortVerts[nI - 1],
                                       &sortVerts[nI]);
            if (difference)
            {
                newVertices[vertIndex] = *(sortVerts[nI].vpVert);
                newVertices[vertIndex].texCoords[0].u = sortVerts[nI].u;
                newVertices[vertIndex].texCoords[0].v = sortVerts[nI].v;
                vertIndex++;
            }

            modenI->vpVert = &(newVertices[vertIndex - 1]);
        }
    }

    /* RWMONITOR(("Reordered")); */
    RwFree(sortVerts);
    RwFree(buildSector->vertices);
    buildSector->vertices = newVertices;
    buildSector->numVertices = numVerts;

    RWRETURNVOID();

}

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

static void
ImportNonNegativeUV2s(RtWorldImportBuildSector * buildSector)
{
    RwInt32             numVertices;

    RWFUNCTION(RWSTRING("ImportNonNegativeUV2s"));
    RWASSERT(NULL != buildSector);

    /* RWMONITOR(("Shift all of the texcoord values into positive space")); */

    numVertices = buildSector->numVertices;

    if (0 < numVertices)
    {
        RtWorldImportVertex *const vertices = buildSector->vertices;
        const RwTexCoords  *const firstCoords2 =
            &vertices[0].texCoords[1];
        RwInt32             nI;
        RwTexCoords         minCoord;
        RwTexCoords         shift;

        minCoord.u = firstCoords2->u;
        minCoord.v = firstCoords2->v;

        for (nI = 1; nI < numVertices; nI++)
        {
            const RwTexCoords  *const texCoords2 =
                &vertices[nI].texCoords[1];

            minCoord.u = RwRealMin2(minCoord.u, texCoords2->u);
            minCoord.v = RwRealMin2(minCoord.v, texCoords2->v);
        }

        shift.u = -ImportFloor(minCoord.u);
        shift.v = -ImportFloor(minCoord.v);

        RWASSERT(0 <= (minCoord.u + shift.u));
        RWASSERT(0 <= (minCoord.v + shift.v));

        if (((shift.u > (RwReal) 0.0) || (shift.v > (RwReal) 0.0)))
        {
            for (nI = 0; nI < numVertices; nI++)
            {
                RwTexCoords         oldCoords2;
                RwTexCoords        *const texCoords2 =
                    &vertices[nI].texCoords[1];

                oldCoords2.u = texCoords2->u;
                oldCoords2.v = texCoords2->v;
                texCoords2->u = oldCoords2.u + shift.u;
                texCoords2->v = oldCoords2.v + shift.v;
                RWASSERT(0 <= texCoords2->u);
                RWASSERT(0 <= texCoords2->v);
            }
        }
    }

    RWRETURNVOID();

}

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

static void
ImportLimitUV2s(RtWorldImportBuildSector * buildSector, RwReal uvLimit)
{
    RtWorldImportVertex *newVertices;
    RwInt32             instanceCount;
    RwInt32             nI;
    RwInt32             numBoundaries;
    RtWorldImportBuildVertex *boundaries;
    RwInt32             numVerts;
    RwInt32             vertIndex;
    RwTexCoords         maxCoord;
    RwTexCoords         minCoord;
    RwUInt32            bytes;
    _rwUVSortVertex    *sortVerts;

    RWFUNCTION(RWSTRING("ImportLimitUV2s"));
    RWASSERT(NULL != buildSector);

    ImportNonNegativeUV2s(buildSector);

    boundaries = buildSector->boundaries;
    numBoundaries = buildSector->numBoundaries;
    instanceCount = (numBoundaries / 4) * 3;

    /* RWMONITOR(("Limit according to the upper bound")); */
    /* NOTE: this will fail to limit polygons which have
     * a UV range greater than uvLimit
     */
    vertIndex = 0;

    bytes = sizeof(_rwUVSortVertex) * instanceCount;
    sortVerts = (_rwUVSortVertex *) RwMalloc(bytes);

    for (nI = 0; nI < numBoundaries; nI++)
    {
        const RwInt32       firstVertInBoundary = nI;
        const RtWorldImportBuildVertex *const v0 = &boundaries[nI++];
        const RwTexCoords  *const v0_Coords =
            &v0->mode.vpVert->texCoords[1];
        const RtWorldImportBuildVertex *const v1 = &boundaries[nI++];
        const RwTexCoords  *const v1_Coords =
            &v1->mode.vpVert->texCoords[1];
        const RtWorldImportBuildVertex *const v2 = &boundaries[nI++];
        const RwTexCoords  *const v2_Coords =
            &v2->mode.vpVert->texCoords[1];
        RwInt32             modu = 0;
        RwInt32             modv = 0;
        RwInt32             nJ;

        RWASSERT(NULL == boundaries[nI].mode.vpVert);

        minCoord.u = v0_Coords->u;
        maxCoord.u = v0_Coords->u;
        minCoord.v = v0_Coords->v;
        maxCoord.v = v0_Coords->v;

        minCoord.u = RwRealMin2(minCoord.u, v1_Coords->u);
        maxCoord.u = RwRealMax2(maxCoord.u, v1_Coords->u);
        minCoord.v = RwRealMin2(minCoord.v, v1_Coords->v);
        maxCoord.v = RwRealMax2(maxCoord.v, v1_Coords->v);

        minCoord.u = RwRealMin2(minCoord.u, v2_Coords->u);
        maxCoord.u = RwRealMax2(maxCoord.u, v2_Coords->u);
        minCoord.v = RwRealMin2(minCoord.v, v2_Coords->v);
        maxCoord.v = RwRealMax2(maxCoord.v, v2_Coords->v);

        /* Neilb / See code above
         * - can't do the divide as this stops you using
         * the value at the limit, which is valid
         * ( also the code is broken
         * if (minCoord.u-modu<0) { modu -= uvLimit; }
         * is correct I think ).
         */
        while (minCoord.u > uvLimit)
        {
            minCoord.u -= uvLimit;
            maxCoord.u -= uvLimit;
            modu -= (RwInt32) uvLimit;
        }
        while (minCoord.v > uvLimit)
        {
            minCoord.v -= uvLimit;
            maxCoord.v -= uvLimit;
            modv -= (RwInt32) uvLimit;
        }

        /*
         * shift to bottom of range..
         * NOTE: this will lead to a row of polygons which
         * will break the stripping if the polygons
         * are not @ integer UV values.. solution - walk the triangles!
         */
        if (maxCoord.u > uvLimit)
        {
            const               RwReal
                floor_min_u = (RwReal) ((RwInt32) (minCoord.u));
            modu -= (RwInt32) floor_min_u;
        }
        if (maxCoord.v > uvLimit)
        {
            const               RwReal
                floor_min_v = (RwReal) ((RwInt32) (minCoord.v));
            modv -= (RwInt32) floor_min_v;
        }

        for (nJ = firstVertInBoundary; nJ < nI; nJ++)
        {
            _rwUVSortVertex    *const dest = &sortVerts[vertIndex];
            RtWorldImportBuildVertexMode *const mode =
                &boundaries[nJ].mode;

            dest->vpVert = mode->vpVert;
            dest->u = dest->vpVert->texCoords[1].u + modu;
            dest->v = dest->vpVert->texCoords[1].v + modv;
            dest->boundary = nJ;
            vertIndex++;
        }

    }

    /* RWMONITOR(("QuickSorting")); */
    qsort(sortVerts, instanceCount,
          sizeof(_rwUVSortVertex), ImportUVSortVertexCmp);

    /* Now count the number of unique vertices */
    numVerts = 0;
    if (instanceCount)
    {
        numVerts++;

        for (nI = 1; nI < instanceCount; nI++)
        {
            RwBool              difference;

            ImportUVSortVertexCmpMacro(difference,
                                       &sortVerts[nI - 1],
                                       &sortVerts[nI]);
            if (difference)
                numVerts++;
        }
    }

    /* RWMONITOR(("%d == numVerts ", (int) numVerts)); */

    bytes = sizeof(RtWorldImportVertex) * numVerts;
    newVertices = (RtWorldImportVertex *) RwMalloc(bytes);

    vertIndex = 0;

    if (instanceCount)
    {
        RtWorldImportBuildVertexMode *modenI;

        nI = 0;
        newVertices[vertIndex] = *(sortVerts[nI].vpVert);
        newVertices[vertIndex].texCoords[1].u = sortVerts[nI].u;
        newVertices[vertIndex].texCoords[1].v = sortVerts[nI].v;
        vertIndex++;
        modenI = &boundaries[sortVerts[nI].boundary].mode;

        modenI->vpVert = &(newVertices[vertIndex - 1]);

        for (nI = 1; nI < instanceCount; nI++)
        {
            RwBool              difference;

            ImportUVSortVertexCmpMacro(difference,
                                       &sortVerts[nI - 1],
                                       &sortVerts[nI]);

            if (difference)
            {
                newVertices[vertIndex] = *(sortVerts[nI].vpVert);
                newVertices[vertIndex].texCoords[1].u = sortVerts[nI].u;
                newVertices[vertIndex].texCoords[1].v = sortVerts[nI].v;
                vertIndex++;
            }

            modenI = &boundaries[sortVerts[nI].boundary].mode;

            modenI->vpVert = &(newVertices[vertIndex - 1]);
        }
    }

    /* RWMONITOR(("Reordered")); */
    RwFree(sortVerts);
    RwFree(buildSector->vertices);
    buildSector->vertices = newVertices;
    buildSector->numVertices = numVerts;
    RWRETURNVOID();
}

#if (0 && defined(RWDEBUG))

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

static void
ImportPrintCongruentTree(RtWorldImportCongruentVertex * root)
{
    RWFUNCTION(RWSTRING("ImportPrintCongruentTree"));
    if (NULL != root)
    {
        RtWorldImportVertex *const sourcePtr = root->sourcePtr;

        ImportPrintCongruentTree(root->child[0]);

        RWMONITOR(("%p ptr %f %f %f pos %f %f texcords",
                   sourcePtr,
                   sourcePtr->OC.x, sourcePtr->OC.y, sourcePtr->OC.z,
                   sourcePtr->texCoords[0].u, sourcePtr->texCoords[0].v));

        ImportPrintCongruentTree(root->child[1]);
    }

    RWRETURNVOID();
}

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

static              RwInt32
ImportCountCongruentTree(RtWorldImportCongruentVertex * root,
                         RwInt32 count)
{
    RWFUNCTION(RWSTRING("ImportCountCongruentTree"));
    if (NULL != root)
    {
        RwInt32             i;

        /* Count children */
        for (i = 0; i < CONGRUENTVERTEXCHILDREN; i++)
        {
            count = ImportCountCongruentTree(root->child[i], count);
        }
        ++count;
    }

    RWRETURN(count);
}

#endif /* (0 && defined(RWDEBUG)) */

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

static RtWorldImportCongruentVertex *
ImportPurgeCongruentTree(RtWorldImportCongruentVertex * root,
                         RtWeldPolygonVerticesState *
                         WeldPolygonVerticesState)
{
    RWFUNCTION(RWSTRING("ImportPurgeCongruentTree"));
    RWASSERT(WeldPolygonVerticesState);

    RWASSERT((NULL == root) || (0 < root->refCount));

    if (NULL != root)
    {
        /* Synchronize vertex */
        RtWorldImportVertex *const vertices =
            WeldPolygonVerticesState->vertices;
        const RtWorldImportVertex *const srcPtr = &root->Mean;
        RtWorldImportVertex *const dstPtr = &vertices[root->destIdx];
        RwRGBAUInt32       *const preLitMean = &root->preLitMean;
        const RwReal        recip =
            (((RwReal) 1) / ((RwReal) (root->refCount)));
        const RwReal        length2 =
            (RwV3dDotProduct(&srcPtr->normal, &srcPtr->normal));
        const RwReal        factor = ((0 < length2) ?
                                      ((RwReal) 1) /
                                      ((RwReal) sqrt(length2))
                                      : ((RwReal) 0));
        RwInt32             i;

        /* Purge children */
        for (i = 0; i < CONGRUENTVERTEXCHILDREN; i++)
        {
            root->child[i] =
                ImportPurgeCongruentTree(root->child[i],
                                         WeldPolygonVerticesState);
        }

        /* copy all fields */
        *dstPtr = root->vertex;

        /* RWMONITOR(("%d == root->destIdx", root->destIdx)); */


        RwV3dScale(&dstPtr->OC, &srcPtr->OC, recip);
        RwV3dScale(&dstPtr->normal, &srcPtr->normal, factor);

        dstPtr->texCoords[0].u = srcPtr->texCoords[0].u * recip;
        dstPtr->texCoords[0].v = srcPtr->texCoords[0].v * recip;

        dstPtr->texCoords[1].u = srcPtr->texCoords[1].u * recip;
        dstPtr->texCoords[1].v = srcPtr->texCoords[1].v * recip;

        dstPtr->preLitCol.red = (RwUInt8)
            (recip * (RwReal) preLitMean->red);
        dstPtr->preLitCol.green = (RwUInt8)
            (recip * (RwReal) preLitMean->green);
        dstPtr->preLitCol.blue = (RwUInt8)
            (recip * (RwReal) preLitMean->blue);
        dstPtr->preLitCol.alpha = (RwUInt8)
            (recip * (RwReal) preLitMean->alpha);

        RwFreeListFree(WeldPolygonVerticesState->CongruentFreeList,
                       root);

        root = (RtWorldImportCongruentVertex *) NULL;
    }

    RWRETURN(root);
}

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

static RtWorldImportWeldVertex *
ImportPurgeWeldTree(RtWorldImportWeldVertex * root,
                    RtWeldPolygonVerticesState *
                    WeldPolygonVerticesState)
{
    RWFUNCTION(RWSTRING("ImportPurgeWeldTree"));
    RWASSERT(WeldPolygonVerticesState);
    if (NULL != root)
    {
        /* Synchronize vertex */
        RwInt32             i;

        /* Purge children */
        for (i = 0; i < WELDVERTEXCHILDREN; i++)
        {
            root->child[i] =
                ImportPurgeWeldTree(root->child[i],
                                    WeldPolygonVerticesState);
        }

#if (0 && defined(RWDEBUG))
        {
            RwInt32             count = 0;

            count =
                ImportCountCongruentTree(root->CongruentVertex, count);

            if (1 < count)
            {
                RWMONITOR(("%d == count", (int) count));
                ImportPrintCongruentTree(root->CongruentVertex);
            }
        }
#endif /* (0 && defined(RWDEBUG)) */

        root->CongruentVertex =
            ImportPurgeCongruentTree(root->CongruentVertex,
                                     WeldPolygonVerticesState);

        RwFreeListFree(WeldPolygonVerticesState->WeldFreeList, root);

        root = (RtWorldImportWeldVertex *) NULL;
    }

    RWRETURN(root);
}

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

static RtWorldImportCongruentVertex **
ImportCongruentPolygonVertex(RtWorldImportVertex * const vpMatch,
                             RtWorldImportCongruentVertex ** result)
{
    RtWorldImportCongruentVertex *candidate =
        (RtWorldImportCongruentVertex *) NULL;

    RWFUNCTION(RWSTRING("ImportCongruentPolygonVertex"));

    RWASSERT(result);

    /* Sort into Bin-tree */
    for (candidate = *result; candidate; candidate = *result)
    {
        RtWorldImportVertex *vertPtr;
        RwInt32             difference = 0;

        vertPtr = &candidate->vertex;

#if (defined(RWDEBUG))
        CmpPositionsMacro(difference, vpMatch, vertPtr);
        RWASSERT(!difference);
        difference = 0;

#if (0)
        CmpPropertiesMacro(difference, vpMatch, vertPtr);
        RWASSERT(!difference);
        difference = 0;
#endif /* (0) */

#endif /* (defined(RWDEBUG)) */

        CmpTexCoordsMacro(difference, vpMatch, vertPtr, ABSOLUTE_TEX);

        if (difference)
        {
            const RwInt32       index = (difference >= 0);

            result = &candidate->child[index];
        }
        else
            break;
    }

    RWRETURN(result);
}

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

static RtWorldImportWeldVertex *
ImportWeldPolygonVertex(RtWeldPolygonVerticesState *
                        const WeldPolygonVerticesState,
                        RtWorldImportVertex * const vpMatch)
{
    RtWorldImportWeldVertex *result = (RtWorldImportWeldVertex *) NULL;
    RtWorldImportParameters *conversionParams;
    RwBool              retainCreases;
    RwUInt32            hash_val;
    RtWeldVertexHash   *hash;
    RtWorldImportWeldVertex **parent;

    RWFUNCTION(RWSTRING("ImportWeldPolygonVertex"));
    RWASSERT(WeldPolygonVerticesState);
    RWASSERT(vpMatch);

    conversionParams = WeldPolygonVerticesState->conversionParams;
    RWASSERT(conversionParams);
    retainCreases = conversionParams->retainCreases;

    hash_val = vpMatch->matIndex;
    VERT_HASH_HIT(hash_val);
    hash = &(WeldPolygonVerticesState->hash[hash_val]);
    parent = &hash->root;

    /* Sort into Quad-tree */
    for (result = *parent; result; result = *parent)
    {
        RtWorldImportVertex *const sourcePtr = result->sourcePtr;
        RwInt32             difference_geometric = 0;
        RwInt32             difference_properties = 0;

        CmpPositionsMacro(difference_geometric, vpMatch, sourcePtr);
        if (retainCreases && !difference_geometric)
        {
            CmpNormalsMacro(difference_geometric, vpMatch, sourcePtr);
        }

        CmpPropertiesMacro(difference_properties, vpMatch, sourcePtr);

        if (difference_geometric | difference_properties)
        {
            const RwInt32       index =
                (((difference_geometric >= 0) << 1) |
                 ((difference_properties >= 0) << 0));

            parent = &result->child[index];
        }
        else
            break;
    }

    /* New vertex ? */

    if (!result)
    {
        RwInt32             i;

        result = (RtWorldImportWeldVertex *)
            RwFreeListAlloc(WeldPolygonVerticesState->WeldFreeList);

        RWASSERT(result);

        result->sourcePtr = vpMatch;
        result->CongruentVertex = (RtWorldImportCongruentVertex *) NULL;

        for (i = 0; i < WELDVERTEXCHILDREN; i++)
        {
            result->child[i] = (RtWorldImportWeldVertex *) NULL;
        }

        *parent = result;
    }

    RWRETURN(result);
}

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

static int          RWCDECL
ImportCentroidAlphabeticalCmp(const void *a, const void *b)
{
    int                 result;

    RwSplitBits         diff;
    const RwV3d        *const pointA =
        &((const RwCentroidSort *) a)->point;
    const RwV3d        *const pointB =
        &((const RwCentroidSort *) b)->point;

    RWFUNCTION(RWSTRING("ImportCentroidAlphabeticalCmp"));

    diff.nReal = pointA->x - pointB->x;
    result = diff.nInt;
    if (!result)
    {
        diff.nReal = pointA->y - pointB->y;
        result = diff.nInt;
        if (!result)
        {
            diff.nReal = pointA->z - pointB->z;
            result = diff.nInt;
        }
    }

    RWRETURN(result);
}

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

static void
ImportSortPolygonsByCentroid(RtWorldImportBuildSector * buildSector)
{
    RwInt32             numPolygons;

    RWFUNCTION(RWSTRING("ImportSortPolygonsByCentroid"));
    RWASSERT(NULL != buildSector);

    numPolygons = buildSector->numPolygons;

    /* RWMONITOR(("%d == numPolygons", numPolygons)); */

    if (0 < numPolygons)
    {
        RtWorldImportBuildVertex *const source =
            buildSector->boundaries;
        RtWorldImportBuildVertex *dest;
        const RwInt32       numBoundaries = buildSector->numBoundaries;
        RwUInt32            bytes;
        RwCentroidSort     *CentroidSort = (RwCentroidSort *) NULL;
        RwInt32             nI;
        RwInt32             nP;
        RwInt32             numVertices;

        bytes = sizeof(RwCentroidSort) * numPolygons;

        CentroidSort = (RwCentroidSort *) RwMalloc(bytes);

        /* RWMONITOR(("Generating Input CentroidSort Array")); */

        nP = 0;
        nI = 0;
        CentroidSort[nP].index = nI;
        CentroidSort[nP].point.x = 0;
        CentroidSort[nP].point.y = 0;
        CentroidSort[nP].point.z = 0;
        numVertices = 0;

        while (nI < numBoundaries)
        {
            RtWorldImportBuildVertexMode *const mode =
                &source[nI++].mode;
            const RtWorldImportVertex *const vpVert = mode->vpVert;

            if (vpVert)
            {
                RwV3dAdd(&CentroidSort[nP].point,
                         &vpVert->OC, &vpVert->OC);
                numVertices++;
            }
            else
            {
                const RwReal        recip = (0 < numVertices) ?
                    ((RwReal) 1) / ((RwReal) numVertices) :
                    ((RwReal) 1);

                RwV3dScale(&CentroidSort[nP].point,
                           &CentroidSort[nP].point, recip);

                if (++nP < numPolygons)
                {
                    CentroidSort[nP].index = nI;
                    CentroidSort[nP].point.x = 0;
                    CentroidSort[nP].point.y = 0;
                    CentroidSort[nP].point.z = 0;
                    numVertices = 0;
                }
            }
        }

        /* RWMONITOR(("Sorting Input CentroidSort Array")); */

        qsort(CentroidSort, numPolygons,
              sizeof(RwCentroidSort), ImportCentroidAlphabeticalCmp);

        bytes = sizeof(RtWorldImportBuildVertex) * numBoundaries;
        dest = (RtWorldImportBuildVertex *) RwMalloc(bytes);

        /* RWMONITOR(("Generating Output")); */

        nI = 0;
        for (nP = 0; nP < numPolygons; nP++)
        {
            RwInt32             index = CentroidSort[nP].index;

            while (source[index].mode.vpVert)
            {
                dest[nI++] = source[index++];
            }
            dest[nI++] = source[index++];
        }

        /* RWMONITOR(("Tidying up")); */

        buildSector->boundaries = dest;

        RwFree(CentroidSort);
        RwFree(source);
    }

    RWRETURNVOID();
}

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

static void
ImportCullDegenerateTriangles(RtWorldImportBuildSector * buildSector)
{
    RtWorldImportBuildVertex *head;
    RtWorldImportBuildVertex *tail;
    RwInt32             PreNumPolygons;

#if (0)
    RwInt32             nI;
#endif /* (0) */

    RWFUNCTION(RWSTRING("ImportCullDegenerateTriangles"));
    RWASSERT(NULL != buildSector);

    PreNumPolygons = buildSector->numPolygons;
    RWMONITOR(("%d == PreNumPolygons", (int) PreNumPolygons));
    head = buildSector->boundaries;
    tail = &head[PreNumPolygons * 4];
    while (head < tail)
    {
        RtWorldImportVertex *const v0 = head[0].mode.vpVert;
        RtWorldImportVertex *const v1 = head[1].mode.vpVert;
        RtWorldImportVertex *const v2 = head[2].mode.vpVert;
        const RwBool        reject = (v0 == v1 || v1 == v2 || v2 == v0);

        RWASSERT(NULL == head[3].mode.vpVert);

        if (reject)
        {
            /* caterplillar track last elmenent over rejected triangle */
            head[3] = *--tail;
            head[2] = *--tail;
            head[1] = *--tail;
            head[0] = *--tail;
            RWASSERT(NULL == head[3].mode.vpVert);

            buildSector->numBoundaries -= 4;
            buildSector->numPolygons--;
        }
        else
        {
            head += 4;
        }
    }
    RWMONITOR(("%d == Post buildSector->numPolygons",
               (int) buildSector->numPolygons));
    RWMONITOR(("%d == delta [%d%%]\n",
               (int) (PreNumPolygons - buildSector->numPolygons),
               (PreNumPolygons
                ? ((100 *
                    (int) (PreNumPolygons -
                           buildSector->numPolygons)) /
                   (int) PreNumPolygons) : 0)));
    RWRETURNVOID();
}

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

static RtWorldImportCongruentVertex *
ImportResolveVertex(RtWorldImportCongruentVertex ** parent,
                    RtWeldPolygonVerticesState *
                    const WeldPolygonVerticesState,
                    RtWorldImportVertex * const vpMatch)
{
    RtWorldImportCongruentVertex *candidate;

    RWFUNCTION(RWSTRING("ImportResolveVertex"));

    candidate = *parent;

    if (candidate)
    {
        /* Duplication -- weld vertex */
        RtWorldImportVertex *const Mean = &candidate->Mean;
        RwRGBAUInt32       *const preLitMean = &candidate->preLitMean;

        RwV3dAdd(&Mean->OC, &Mean->OC, &vpMatch->OC);
        RwV3dAdd(&Mean->normal, &Mean->normal, &vpMatch->normal);
        Mean->texCoords[0].u += vpMatch->texCoords[0].u;
        Mean->texCoords[0].v += vpMatch->texCoords[0].v;
        Mean->texCoords[1].u += vpMatch->texCoords[1].u;
        Mean->texCoords[1].v += vpMatch->texCoords[1].v;
        preLitMean->red += vpMatch->preLitCol.red;
        preLitMean->green += vpMatch->preLitCol.green;
        preLitMean->blue += vpMatch->preLitCol.blue;
        preLitMean->alpha += vpMatch->preLitCol.alpha;

        candidate->refCount++;
    }
    else
    {
        /* New -- fresh vertex */
        RwInt32             j;
        RwRGBAUInt32       *preLitMean;
        RwInt32             PostNumVertices =
            WeldPolygonVerticesState->PostNumVertices;

        RWASSERT(NULL != WeldPolygonVerticesState->WeldFreeList);

        candidate = (RtWorldImportCongruentVertex *)
            RwFreeListAlloc(WeldPolygonVerticesState->
                            CongruentFreeList);

        RWASSERT(NULL != candidate);
        RWASSERT(0 <= PostNumVertices);

        candidate->destIdx = PostNumVertices++;
        WeldPolygonVerticesState->PostNumVertices = PostNumVertices;

#if (0)
        RWMONITOR(("%d == PostNumVertices", PostNumVertices));
        RWMONITOR(("%d == WeldPolygonVerticesState->PreNumVertices",
                   WeldPolygonVerticesState->PreNumVertices));
#endif /* (0) */

        candidate->vertex = *vpMatch;
        candidate->Mean = *vpMatch;
        preLitMean = &candidate->preLitMean;
        preLitMean->red = vpMatch->preLitCol.red;
        preLitMean->green = vpMatch->preLitCol.green;
        preLitMean->blue = vpMatch->preLitCol.blue;
        preLitMean->alpha = vpMatch->preLitCol.alpha;
        candidate->refCount = 1;

        for (j = 0; j < CONGRUENTVERTEXCHILDREN; j++)
        {
            candidate->child[j] = (RtWorldImportCongruentVertex *) NULL;
        }

        *parent = candidate;
    }

    RWRETURN(candidate);
}

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

static RtWorldImportBuildVertex *
ImportProcessPolygonVertices(RtWorldImportBuildVertex * head,
                             RtWeldPolygonVerticesState *
                             WeldPolygonVerticesState)
{
    RtWorldImportVertex *vertices;
    RtWorldImportWeldVertex *const weld0 =
        ImportWeldPolygonVertex(WeldPolygonVerticesState,
                                head[0].mode.vpVert);
    RtWorldImportWeldVertex *const weld1 =
        ImportWeldPolygonVertex(WeldPolygonVerticesState,
                                head[1].mode.vpVert);
    RtWorldImportWeldVertex *const weld2 =
        ImportWeldPolygonVertex(WeldPolygonVerticesState,
                                head[2].mode.vpVert);
    RtWorldImportVertex v0 = *head[0].mode.vpVert;
    RtWorldImportVertex v1 = *head[1].mode.vpVert;
    RtWorldImportVertex v2 = *head[2].mode.vpVert;
    RtWorldImportCongruentVertex **parent0;
    RtWorldImportCongruentVertex **parent1;
    RtWorldImportCongruentVertex **parent2;
    RtWorldImportCongruentVertex *candidate;
    RwBool              fixed;
    RtWorldImportParameters *conversionParams;

    RWFUNCTION(RWSTRING("ImportProcessPolygonVertices"));

    RWASSERT(WeldPolygonVerticesState);
    vertices = WeldPolygonVerticesState->vertices;

    RWASSERT(weld0);
    parent0 =
        ImportCongruentPolygonVertex(&v0, &weld0->CongruentVertex);
    RWASSERT(weld1);
    parent1 =
        ImportCongruentPolygonVertex(&v1, &weld1->CongruentVertex);
    RWASSERT(weld2);
    parent2 =
        ImportCongruentPolygonVertex(&v2, &weld2->CongruentVertex);

    conversionParams = WeldPolygonVerticesState->conversionParams;
    RWASSERT(conversionParams);

    fixed = ((rwTEXTUREADDRESSWRAP != conversionParams->mode) ||
             (*parent0 || *parent1 || *parent2));

    if (!fixed)
    {
        RtWorldImportVertex *vertPtr;
        RwTexCoords         texDelta;
        RwTexCoords         texDelta2;

        /* No absolute matches  -- potentially a moveable feast */
        if (weld0->CongruentVertex)
        {
            vertPtr = &weld0->CongruentVertex->vertex;

            texDelta.u = (vertPtr->texCoords[0].u - v0.texCoords[0].u);
            texDelta.v = (vertPtr->texCoords[0].v - v0.texCoords[0].v);
            texDelta2.u = (vertPtr->texCoords[1].u - v0.texCoords[1].u);
            texDelta2.v = (vertPtr->texCoords[1].v - v0.texCoords[1].v);

            v0.texCoords[0].u = vertPtr->texCoords[0].u;
            v0.texCoords[0].v = vertPtr->texCoords[0].v;
            v0.texCoords[1].u = vertPtr->texCoords[1].u;
            v0.texCoords[1].v = vertPtr->texCoords[1].v;
            RWASSERT(weld0);
            parent0 = &weld0->CongruentVertex;

            v1.texCoords[0].u += texDelta.u;
            v1.texCoords[0].v += texDelta.v;
            v1.texCoords[1].u += texDelta2.u;
            v1.texCoords[1].v += texDelta2.v;
            RWASSERT(weld1);
            parent1 =
                ImportCongruentPolygonVertex(&v1,
                                             &weld1->CongruentVertex);

            v2.texCoords[0].u += texDelta.u;
            v2.texCoords[0].v += texDelta.v;
            v2.texCoords[1].u += texDelta2.u;
            v2.texCoords[1].v += texDelta2.v;
            RWASSERT(weld2);
            parent2 =
                ImportCongruentPolygonVertex(&v2,
                                             &weld2->CongruentVertex);

            /*
             * RWMONITOR(("Translated for v0 [%.1f %.1f] [%.1f %.1f]",
             * texDelta.u, texDelta.v,
             * texDelta2.u, texDelta2.v));
             */

            WeldPolygonVerticesState->translations += 3;

        }
        else if (weld1->CongruentVertex)
        {
            vertPtr = &weld1->CongruentVertex->vertex;

            texDelta.u = (vertPtr->texCoords[0].u - v1.texCoords[0].u);
            texDelta.v = (vertPtr->texCoords[0].v - v1.texCoords[0].v);
            texDelta2.u = (vertPtr->texCoords[1].u - v1.texCoords[1].u);
            texDelta2.v = (vertPtr->texCoords[1].v - v1.texCoords[1].v);

            v0.texCoords[0].u += texDelta.u;
            v0.texCoords[0].v += texDelta.v;
            v0.texCoords[1].u += texDelta2.u;
            v0.texCoords[1].v += texDelta2.v;
            RWASSERT(weld0);
            parent0 =
                ImportCongruentPolygonVertex(&v0,
                                             &weld0->CongruentVertex);

            v1.texCoords[0].u = vertPtr->texCoords[0].u;
            v1.texCoords[0].v = vertPtr->texCoords[0].v;
            v1.texCoords[1].u = vertPtr->texCoords[1].u;
            v1.texCoords[1].v = vertPtr->texCoords[1].v;
            RWASSERT(weld1);
            parent1 = &weld1->CongruentVertex;

            v2.texCoords[0].u += texDelta.u;
            v2.texCoords[0].v += texDelta.v;
            v2.texCoords[1].u += texDelta2.u;
            v2.texCoords[1].v += texDelta2.v;
            RWASSERT(weld2);
            parent2 =
                ImportCongruentPolygonVertex(&v2,
                                             &weld2->CongruentVertex);

            /*
             * RWMONITOR(("Translated for v1 [%.1f %.1f] [%.1f %.1f]",
             * texDelta.u, texDelta.v,
             * texDelta2.u, texDelta2.v));
             */

            WeldPolygonVerticesState->translations += 3;

        }
        else if (weld2->CongruentVertex)
        {
            vertPtr = &weld2->CongruentVertex->vertex;

            texDelta.u = (vertPtr->texCoords[0].u - v2.texCoords[0].u);
            texDelta.v = (vertPtr->texCoords[0].v - v2.texCoords[0].v);
            texDelta2.u = (vertPtr->texCoords[1].u - v2.texCoords[1].u);
            texDelta2.v = (vertPtr->texCoords[1].v - v2.texCoords[1].v);

            v0.texCoords[0].u += texDelta.u;
            v0.texCoords[0].v += texDelta.v;
            v0.texCoords[1].u += texDelta2.u;
            v0.texCoords[1].v += texDelta2.v;
            RWASSERT(weld0);
            parent0 =
                ImportCongruentPolygonVertex(&v0,
                                             &weld0->CongruentVertex);

            v1.texCoords[0].u += texDelta.u;
            v1.texCoords[0].v += texDelta.v;
            v1.texCoords[1].u += texDelta2.u;
            v1.texCoords[1].v += texDelta2.v;
            RWASSERT(weld1);
            parent1 =
                ImportCongruentPolygonVertex(&v1,
                                             &weld1->CongruentVertex);

            v2.texCoords[0].u = vertPtr->texCoords[0].u;
            v2.texCoords[0].v = vertPtr->texCoords[0].v;
            v2.texCoords[1].u = vertPtr->texCoords[1].u;
            v2.texCoords[1].v = vertPtr->texCoords[1].v;
            RWASSERT(weld2);
            parent2 = &weld2->CongruentVertex;

            /*
             * RWMONITOR(("Translated for v2 [%.1f %.1f] [%.1f %.1f]",
             * texDelta.u, texDelta.v,
             * texDelta2.u, texDelta2.v));
             */

            WeldPolygonVerticesState->translations += 3;
        }

    }

    candidate = ImportResolveVertex(parent0, WeldPolygonVerticesState, &v0);
    head[0].mode.index = candidate->destIdx;

    candidate = ImportResolveVertex(parent1, WeldPolygonVerticesState, &v1);
    head[1].mode.index = candidate->destIdx;

    candidate = ImportResolveVertex(parent2, WeldPolygonVerticesState, &v2);
    head[2].mode.index = candidate->destIdx;

    RWASSERT(head[3].mode.vpVert == ((RtWorldImportVertex *) NULL));

    head = &head[4];

    RWRETURN(head);
}

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

static void
ImportWeldPolygonVertices(RtWorldImportBuildSector * buildSector,
                          RtWorldImportParameters * conversionParams,
                          RpMaterialList * matList)
{
    RtWorldImportBuildVertex *head;
    RtWorldImportBuildVertex *tail;
    RwInt32             PreNumVertices;
    RwInt32             NumPolygons;
    RwInt32             numMaterials;
    RwInt32             nI;
    RwUInt32            bytes;
    RtWeldPolygonVerticesState WeldPolygonVerticesState;

    RWFUNCTION(RWSTRING("ImportWeldPolygonVertices"));
    RWASSERT(NULL != buildSector);

    /* RWMONITOR(("%d == retainCreases", (int) retainCreases)); */
    PreNumVertices = buildSector->numVertices;

    numMaterials = rpMaterialListGetNumMaterials(matList);

    bytes = sizeof(RtWeldVertexHash) * numMaterials;
    WeldPolygonVerticesState.hash = (RtWeldVertexHash *)
        RwMalloc(bytes);

    for (nI = 0; nI < numMaterials; nI++)
    {
        WeldPolygonVerticesState.hash[nI].root =
            (RtWorldImportWeldVertex *) NULL;
    }

#if (defined(_MSC_VER) && defined (RWVERBOSE) && defined(RWDEBUG))
    bytes = sizeof(RwUInt32) * numMaterials;
    vert_hash_hit = (RwUInt32 *) RwMalloc(bytes);
    memset(vert_hash_hit, 0, bytes);
#endif /* (defined(_MSC_VER) && defined (RWVERBOSE) && defined(RWDEBUG)) */

    WeldPolygonVerticesState.vertices = buildSector->vertices;
    WeldPolygonVerticesState.CongruentFreeList =
        RwFreeListCreate(sizeof(RtWorldImportCongruentVertex), 20, 0);
    WeldPolygonVerticesState.WeldFreeList =
        RwFreeListCreate(sizeof(RtWorldImportWeldVertex), 20, 0);
    WeldPolygonVerticesState.conversionParams = conversionParams;
    WeldPolygonVerticesState.PreNumVertices = PreNumVertices;
    WeldPolygonVerticesState.PostNumVertices = 0;
    WeldPolygonVerticesState.translations = 0;

    RWMONITOR(("%d == PreNumVertices", (int) PreNumVertices));
    /* Build vertex tree */
    RWASSERT(NULL != buildSector);

    NumPolygons = buildSector->numPolygons;
    RWMONITOR(("%d == NumPolygons", (int) NumPolygons));

    RWASSERTBOUNDARIES(buildSector);

    head = buildSector->boundaries;
    tail = &head[NumPolygons * 4];
    while (head < tail)
    {
        head = ImportProcessPolygonVertices(head,
                                            &WeldPolygonVerticesState);
    }

    RWMONITOR(("%d ==  buildSector->numVertices",
               (int) buildSector->numVertices));
    RWMONITOR(("%d == WeldPolygonVerticesState.PostNumVertices",
               (int) WeldPolygonVerticesState.PostNumVertices));

    RWASSERT(0 <= WeldPolygonVerticesState.PostNumVertices);

    if (buildSector->numVertices !=
        WeldPolygonVerticesState.PostNumVertices)
    {
        const RwUInt32      bytes =
            (sizeof(RtWorldImportVertex) *
             WeldPolygonVerticesState.PostNumVertices);

        buildSector->numVertices =
            (WeldPolygonVerticesState.PostNumVertices);

        WeldPolygonVerticesState.vertices = (RtWorldImportVertex *)
            (RwRealloc(WeldPolygonVerticesState.vertices, bytes));

        buildSector->vertices = WeldPolygonVerticesState.vertices;
    }

    /* Relink Polygon vertex pointers */
    head = buildSector->boundaries;
    tail = &head[NumPolygons * 4];
    while (head < tail)
    {
        RtWorldImportBuildVertexMode *mode;

        mode = &head[0].mode;
        mode->vpVert = &WeldPolygonVerticesState.vertices[mode->index];

        mode = &head[1].mode;
        mode->vpVert = &WeldPolygonVerticesState.vertices[mode->index];

        mode = &head[2].mode;
        mode->vpVert = &WeldPolygonVerticesState.vertices[mode->index];

        RWASSERT(head[3].mode.vpVert == ((RtWorldImportVertex *) NULL));

        head = &head[4];
    }

    for (nI = 0; nI < numMaterials; nI++)
    {
        WeldPolygonVerticesState.hash[nI].root =
            ImportPurgeWeldTree(WeldPolygonVerticesState.hash[nI].root,
                                &WeldPolygonVerticesState);
        RWASSERT(NULL == WeldPolygonVerticesState.hash[nI].root);

    }

    RWASSERTBOUNDARIES(buildSector);

    if (NULL != WeldPolygonVerticesState.CongruentFreeList)
    {
        RwFreeListDestroy(WeldPolygonVerticesState.CongruentFreeList);
        WeldPolygonVerticesState.CongruentFreeList =
            (RwFreeList *) NULL;
    }

    if (NULL != WeldPolygonVerticesState.WeldFreeList)
    {
        RwFreeListDestroy(WeldPolygonVerticesState.WeldFreeList);
        WeldPolygonVerticesState.WeldFreeList = (RwFreeList *) NULL;
    }

    RWASSERT(buildSector->numVertices >=
             WeldPolygonVerticesState.PostNumVertices);

    RWMONITOR(("%d == WeldPolygonVerticesState.translations",
               (int) WeldPolygonVerticesState.translations));

    RWMONITOR(("%d == Post buildSector->numVertices",
               (int) buildSector->numVertices));

    RWMONITOR(("%d == delta [%d%%]\n",
               (int) (PreNumVertices - buildSector->numVertices),
               (PreNumVertices
                ? ((100 *
                    (int) (PreNumVertices -
                           buildSector->numVertices)) /
                   (int) PreNumVertices) : 0)));
#if (defined(_MSC_VER) && defined (RWVERBOSE) && defined(RWDEBUG))
    {
        FILE               *fp;
        RwInt32             nI;

        fp = fopen("verthash.plt", "w");

        fprintf(fp, "set title \"Find Vertex Hash hits\"\n");
        fprintf(fp, "set xtics 0,32,%d\n", numMaterials);
        fprintf(fp, "plot \"verthash.dat\" notitle with points, ");
        fprintf(fp, " \"verthash.dat\" title 'hash' with steps\n");
        fprintf(fp, "\n");
        fprintf(fp, "pause -1 \"Press return to continue\"\n");
        fprintf(fp, "reset\n");

        fclose(fp);

        fp = fopen("verthash.dat", "w");

        for (nI = 0; nI < numMaterials; nI++)
        {
            fprintf(fp, " %3d %12d\n", nI, vert_hash_hit[nI]);
        }

        fclose(fp);
    }
    RwFree(vert_hash_hit);
    vert_hash_hit = (RwUInt32 *) NULL;

#endif /* (defined(_MSC_VER) && defined (RWVERBOSE) && defined(RWDEBUG)) */

    RwFree(WeldPolygonVerticesState.hash);
    WeldPolygonVerticesState.hash = (RtWeldVertexHash *) NULL;

    RWRETURNVOID();
}

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

RwReal
_rtImportGetWeldThresholdPositional(void)
{
    RwReal              componentThreshold = WeldThresholdPositional;

    RWFUNCTION(RWSTRING("_rtImportGetWeldThresholdPositional"));

    RWRETURN(componentThreshold);
}

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

void
_rtImportSetWeldThresholdPositional(RwReal componentThreshold)
{
    RWFUNCTION(RWSTRING("_rtImportSetWeldThresholdPositional"));

    WeldThresholdPositional = componentThreshold;
    RWRETURNVOID();
}

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

RwReal
_rtImportGetWeldThresholdAngular(void)
{
    RwReal              cosineThreshold = WeldThresholdAngular;

    RWFUNCTION(RWSTRING("_rtImportGetWeldThresholdAngular"));
    RWRETURN(cosineThreshold);
}

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

void
_rtImportSetWeldThresholdAngular(RwReal cosineThreshold)
{
    RWFUNCTION(RWSTRING("_rtImportSetWeldThresholdAngular"));
    WeldThresholdAngular = cosineThreshold;
    RWRETURNVOID();
}

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

void
_rtImportBuildSectorConditionGeometry(RtWorldImport * wpNoHS,
                                      RtWorldImportBuildSector *
                                      buildSector,
                                      RtWorldImportParameters *
                                      conversionParams,
                                      RpMaterialList * matList)
{

    RWFUNCTION(RWSTRING("_rtImportBuildSectorConditionGeometry"));
    RWMONITOR(("Conditioning Geometry ...\n"));

    /* RWCRTCHECKMEMORY(); */
    RWASSERT((buildSector->numPolygons * 4) ==
             (buildSector->numBoundaries));

    if (conversionParams->cullZeroAreaPolygons)
    {
        BuildSectorWrite(1024, "stage0");
        ImportCullZeroAreaPolygons(buildSector);

        /* RWCRTCHECKMEMORY(); */
        RWASSERT((buildSector->numPolygons * 4) ==
                 (buildSector->numBoundaries));
    }

    /* RWCRTCHECKMEMORY(); */
    BuildSectorWrite(1024, "stage1");
    ImportCullUnusedVertices(buildSector);
    RWASSERT((buildSector->numPolygons * 4) ==
             (buildSector->numBoundaries));

    /* RWCRTCHECKMEMORY(); */
    BuildSectorWrite(1024, "stage2");
    ImportUnshareVerticesOnMaterialBoundaries(buildSector);
    RWASSERT((buildSector->numPolygons * 4) ==
             (buildSector->numBoundaries));

    /* RWCRTCHECKMEMORY(); */
    BuildSectorWrite(1024, "stage3");
    ImportSortVerticesOnMaterial(buildSector, matList);
    RWASSERT((buildSector->numPolygons * 4) ==
             (buildSector->numBoundaries));

    /* RWCRTCHECKMEMORY(); */
    BuildSectorWrite(1024, "stage4");
    ImportLimitUVs(buildSector, conversionParams->uvLimit);
    RWASSERT((buildSector->numPolygons * 4) ==
             (buildSector->numBoundaries));

    /* RWCRTCHECKMEMORY(); */
    BuildSectorWrite(1024, "stage4.5");
    ImportLimitUV2s(buildSector, conversionParams->uvLimit);
    RWASSERT((buildSector->numPolygons * 4) ==
             (buildSector->numBoundaries));

    /* RWCRTCHECKMEMORY(); */
    if (conversionParams->sortPolygons)
    {

        BuildSectorWrite(1024, "sortPolygons");
        ImportSortPolygonsByCentroid(buildSector);
        RWASSERT((buildSector->numPolygons * 4) ==
                 (buildSector->numBoundaries));
    }

    /* RWCRTCHECKMEMORY(); */
    BuildSectorWrite(1024, "stage6");
    ImportWeldPolygonVertices(buildSector, conversionParams, matList);
    RWASSERT((buildSector->numPolygons * 4) ==
             (buildSector->numBoundaries));

    if (conversionParams->weldPolygons)
    {
        RwInt32             pcountDiff;
        RwInt32             weldCycles = 0;
        RwInt32             PreNumPolygons;

        PreNumPolygons = buildSector->numPolygons;
        RWMONITOR(("%d == PreNumPolygons", (int) PreNumPolygons));

        do
        {
            /* RWCRTCHECKMEMORY(); */

            pcountDiff = buildSector->numPolygons;
            BuildSectorWrite(1024, "stage7");
            ImportCullDegenerateTriangles(buildSector);
            BuildSectorWrite(1024, "stage8");
            _rtImportBuildSectorWeldPolygons(buildSector, wpNoHS,
                                             weldCycles);
            RWASSERT((buildSector->numPolygons * 4) ==
                     (buildSector->numBoundaries));

            pcountDiff -= buildSector->numPolygons;
            /* RWASSERT( !(weldCycles && pcountDiff) ); */

            weldCycles++;
            RWMONITOR(("%d == Post buildSector->numPolygons %d == weldCycles", (int) buildSector->numPolygons, (int) weldCycles));
            RWMONITOR((" %d == delta [%d%%]\n",
                       (int) (PreNumPolygons -
                              buildSector->numPolygons),
                       PreNumPolygons
                       ? ((100 *
                           (int) ((PreNumPolygons -
                                   buildSector->numPolygons))) /
                          (int) PreNumPolygons) : 0));
        }
        while (pcountDiff);

#if (0 && defined(WIN_OSTYPES_H) && defined(RWDEBUG) && defined(RWVERBOSE))
        {
            char                buffer[256];
            const               RwInt32
                PostNumPolygons = buildSector->numPolygons;
            const RwInt32       Delta =
                PreNumPolygons - buildSector->numPolygons;
            _snprintf(buffer, sizeof(buffer),
                      "%s(%d): %d == weldCycles\n%d == PrePolys %d == PostPolys\n%d == Delta %d == %%age Delta",
                      __FILE__, __LINE__,
                      (int) weldCycles,
                      (int) PreNumPolygons,
                      (int) PostNumPolygons,
                      (int) Delta,
                      (int) (PreNumPolygons
                             ? ((100 * Delta) / PreNumPolygons) : 0));
            MessageBox(NULL, buffer, "Polygon Welding", MB_OK);
        }
#endif /* (0&& defined(WIN_OSTYPES_H) && defined(RWDEBUG) && defined(RWVERBOSE)) */

    }

    /* RWCRTCHECKMEMORY(); */
    BuildSectorWrite(1024, "stage9");
    ImportCullDegenerateTriangles(buildSector);
    RWASSERT((buildSector->numPolygons * 4) ==
             (buildSector->numBoundaries));

    /* RWCRTCHECKMEMORY(); */
    BuildSectorWrite(1024, "stage10");
    ImportWeldPolygonVertices(buildSector, conversionParams, matList);
    RWASSERT((buildSector->numPolygons * 4) ==
             (buildSector->numBoundaries));

    /* RWCRTCHECKMEMORY(); */
    RWASSERT((buildSector->numPolygons * 4) ==
             (buildSector->numBoundaries));

    if (conversionParams->cullZeroAreaPolygons)
    {
        BuildSectorWrite(1024, "stage11");
        ImportCullZeroAreaPolygons(buildSector);

        /* RWCRTCHECKMEMORY(); */
        RWASSERT((buildSector->numPolygons * 4) ==
                 (buildSector->numBoundaries));
    }

    RWRETURNVOID();
}

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