/*
 * 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 "rtimport.h"

#include "nhsworld.h"
#include "nhsmerge.h"

static const char   rcsid[] __RWUNUSED__ =
    "@@(#)$Id: nhsmerge.c,v 1.10 2001/07/02 13:10:26 johns Exp $";

#if (0 && defined(MERGECOPLANAR))

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

typedef struct _rwSortPolygon _rwSortPolygon;
struct _rwSortPolygon
{
    RtWorldImportBuildVertex *vpFirst, *vpLast;
    RwReal              absMaxDelta;
    RwBool              merged;
    RwV3d               normal;
};

typedef struct _rwEdge _rwEdge;
struct _rwEdge
{
    RtWorldImportBuildVertex *start;
    RtWorldImportBuildVertex *end;
};

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

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

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

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

#define theMaxPlaneError   (((RwReal)1)/((RwReal)(1<<3)))

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

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

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

static void
ImportGraft(_rwSortPolygon * sortA, _rwEdge * edgeA,
            _rwSortPolygon * sortB, _rwEdge * edgeB, RwSList * scratch)
{
    RtWorldImportBuildVertex *srcbnd, *dstbnd, *vpCurr;

    RWFUNCTION(RWSTRING("ImportGraft"));

    for (srcbnd = sortA->vpFirst; srcbnd < sortA->vpLast; srcbnd++)
    {
        if (srcbnd == edgeA->start)
        {
            dstbnd = edgeB->end;
            while (dstbnd != edgeB->start)
            {
                vpCurr =
                    (RtWorldImportBuildVertex *)
                    rwSListGetNewEntry(scratch);
                *vpCurr = *dstbnd;
                dstbnd++;
                if (dstbnd == sortB->vpLast)
                {
                    dstbnd = sortB->vpFirst;
                }
            }
        }
        else
        {
            vpCurr =
                (RtWorldImportBuildVertex *)
                rwSListGetNewEntry(scratch);
            *vpCurr = *srcbnd;
        }
    }

    /* terminate boundary */
    vpCurr = (RtWorldImportBuildVertex *) rwSListGetNewEntry(scratch);
    *vpCurr = *srcbnd;
    sortA->vpFirst =
        (RtWorldImportBuildVertex *) rwSListGetEntry(scratch, 0);
    sortA->vpLast = vpCurr;
}

static int          RWCDECL
ImportSortPolygonCmp(const _rwSortPolygon * sortA,
                     const _rwSortPolygon * sortB, RwReal * absMaxDelta)
{
    RwV3d               vec;
    RwReal              rDelta;
    RtWorldImportBuildVertex *boundaries;

    RWFUNCTION(RWSTRING("ImportSortPolygonCmp"));
    /* must have the same material */
    if (sortA->vpLast->pinfo.matIndex != sortB->vpLast->pinfo.matIndex)
    {
        RWRETURN(1);
    }

    /* does sortB lie in the plane of sortA? */
    *absMaxDelta = 0.0f;
    boundaries = sortB->vpFirst;
    while (boundaries->vpVert)
    {
        RwV3dSub(&vec, &boundaries->vpVert->OC,
                 &sortA->vpFirst->vpVert->OC);
        rDelta = RwV3dDotProduct(&sortA->normal, &vec);
        if (rDelta > theMaxPlaneError)
        {
            RWRETURN(1);
        }
        if (rDelta < -theMaxPlaneError)
        {
            RWRETURN(-1);
        }

        /* track worse error */
        if (RAbs(rDelta) > *absMaxDelta)
        {
            *absMaxDelta = RAbs(rDelta);
        }

        boundaries++;
    }

    /* does sortA lie in the plane of sortB? */
    boundaries = sortA->vpFirst;
    while (boundaries->vpVert)
    {
        RwV3dSub(&vec, &boundaries->vpVert->OC,
                 &sortB->vpFirst->vpVert->OC);
        rDelta = RwV3dDotProduct(&sortB->normal, &vec);
        if (rDelta > theMaxPlaneError)
        {
            RWRETURN(1);
        }
        if (rDelta < -theMaxPlaneError)
        {
            RWRETURN(-1);
        }

        /* track worse error */
        if (RAbs(rDelta) > *absMaxDelta)
        {
            *absMaxDelta = RAbs(rDelta);
        }

        boundaries++;
    }

    RWRETURN(0);
}

static int
ImportBuildSectorVertexCompare(RtWorldImportBuildVertex * sortVertA,
                               RtWorldImportBuildVertex * sortVertB)
{
    RWFUNCTION(RWSTRING("ImportBuildSectorVertexCompare"));
    if (sortVertA->vpVert != sortVertB->vpVert)
    {
        RWRETURN(1);
    }

    RWRETURN(0);
}

#include <rprandom.h>

static int
ImportGroup(_rwSortPolygon * array, int elements,
            int cmp(const _rwSortPolygon * a,
                    const _rwSortPolygon * b,
                    RwReal * max), RwSList * newboundaries)
{
    _rwSortPolygon     *sortA, *sortB;

    _rwEdge             edgeA, edgeB;
    int                 i, j, nPcount;
    RwReal              absMaxDelta;
    RtWorldImportBuildVertex *srcbnd, *dstbnd, *boundaries;
    RwSList            *scratch, *scratch1, *scratch2;
    RtWorldImportBuildVertex *vpCurr =
        (RtWorldImportBuildVertex *) NULL;

    RWFUNCTION(RWSTRING("ImportGroup"));
    /* build the new boundary in scratchpad until we're done */
    scratch1 = rwSListCreate(sizeof(RtWorldImportBuildVertex));
    scratch2 = rwSListCreate(sizeof(RtWorldImportBuildVertex));
    scratch = scratch1;
    nPcount = 0;
    for (i = 0; i < elements; i++)
    {
        sortA = array + i;
        if (!sortA->merged)
        {
            /* for each vertex used by sortA */
            for (boundaries = sortA->vpFirst;
                 boundaries < sortA->vpLast; boundaries++)
            {

                RwSList            *slist =
                    boundaries->vpVert->state.slist;

                /* for each polygon using that vertex */
                for (j = 0; j < rwSListGetNumEntries(slist); j++)
                {
                    sortB =
                        *(_rwSortPolygon **) rwSListGetEntry(slist, j);
                    if (!sortB->merged && sortB != sortA)
                    {
                        /* in same plane */
                        if (cmp(sortA, sortB, &absMaxDelta) == 0)
                        {
                            /* find a common edge */
                            rwSListEmpty(scratch);
                            for (srcbnd = sortA->vpFirst;
                                 srcbnd < sortA->vpLast; srcbnd++)
                            {
                                edgeA.start = srcbnd;
                                edgeA.end = srcbnd + 1;
                                if (edgeA.end == sortA->vpLast)
                                {
                                    edgeA.end = sortA->vpFirst;
                                }

                                for (dstbnd = sortB->vpFirst;
                                     dstbnd < sortB->vpLast; dstbnd++)
                                {
                                    edgeB.start = dstbnd;
                                    edgeB.end = dstbnd + 1;
                                    if (edgeB.end == sortB->vpLast)
                                    {
                                        edgeB.end = sortB->vpFirst;
                                    }

                                    /* share an edge */
                                    if (ImportBuildSectorVertexCompare
                                        (edgeA.start, edgeB.end) == 0)
                                        if (ImportBuildSectorVertexCompare(edgeB.start, edgeA.end) == 0)
                                        {
                                            /* add sortB to sortA */
                                            ImportGraft(sortA, &edgeA,
                                                        sortB, &edgeB,
                                                        scratch);
                                            scratch =
                                                scratch ==
                                                scratch1 ? scratch2 :
                                                scratch1;
                                            sortB->merged = TRUE;
                                            /* force termination of enclosing loops */
                                            dstbnd = sortB->vpLast;
                                            srcbnd = sortA->vpLast;
                                            j = rwSListGetNumEntries
                                                (slist);
                                            /* we're gonna go through again as a result of this */
                                            boundaries = sortA->vpFirst;
                                        }
                                }
                            }
                        }
                    }
                }

                if (sortA->vpLast - sortA->vpFirst == 4)
                {
                    break;
                }
            }

            /* write sortA to newboundaries */
            j = rwSListGetNumEntries(newboundaries);
            for (srcbnd = sortA->vpFirst; srcbnd <= sortA->vpLast;
                 srcbnd++)
            {
                vpCurr =
                    (RtWorldImportBuildVertex *)
                    rwSListGetNewEntry(newboundaries);
                *vpCurr = *srcbnd;
            }
            sortA->vpFirst =
                (RtWorldImportBuildVertex *)
                rwSListGetEntry(newboundaries, j);
            sortA->vpLast = vpCurr;
            sortA->merged = TRUE;
#ifdef AMB_SPECIFIC
            if (1)
            {
                char                buffer[256];

                sprintf(buffer,
                        "%08lx: %d sides\n",
                        sortA, sortA->vpLast - sortA->vpFirst);
                PiDisplayMessage(buffer);
            }
#endif

            nPcount++;
        }
    }

    rwSListDestroy(scratch2);
    rwSListDestroy(scratch1);
    RWRETURN(nPcount);
}

static void
ImportBuildSectorMergeCoplanarTriangles(RtWorldImportBuildSector *
                                        buildSector)
{
    _rwSortPolygon     *sortPolygons;
    RwSList            *newboundaries;
    RtWorldImportBuildVertex *boundaries, *fbound;
    RwInt32             nI, nJ, nPcount;
    RwBool              bFirst;

    RWFUNCTION(RWSTRING("ImportBuildSectorMergeCoplanarTriangles"));
#ifndef AMB_SPECIFIC
    RWRETURNVOID();
#endif
    /* vertex usedby lists */
    for (nI = 0; nI < buildSector->numVertices; nI++)
    {
        buildSector->vertices[nI].state.slist =
            rwSListCreate(sizeof(_rwSortPolygon *));
    }

    /* merge triangles into 1-boundary convex polygons */
    sortPolygons =
        (_rwSortPolygon *)
        RwMalloc(sizeof(_rwSortPolygon) * buildSector->numPolygons);
    boundaries = buildSector->boundaries;
    nPcount = 0;
    bFirst = TRUE;
    for (nI = 0; nI < buildSector->numBoundaries; nI++, boundaries++)
    {
        if (boundaries->vpVert)
        {
            _rwSortPolygon    **usedby;

            if (bFirst)
            {
                fbound = boundaries;
                bFirst = FALSE;
            }

            /* add polygon to vertex usedby list */
            usedby =
                rwSListGetNewEntry(boundaries->vpVert->state.slist);
            *usedby = &sortPolygons[nPcount];
        }
        else
        {
            _rwSortPolygon     *apoly;
            RwV3d               edge[2], normal;
            RwReal              length, maxlength;
            RwInt32             sides, prev, next;

            sides = boundaries - fbound;
            apoly = &sortPolygons[nPcount];
            apoly->vpFirst = fbound;
            apoly->vpLast = boundaries;
            apoly->absMaxDelta = 10000.0f;
            apoly->merged = FALSE;
            /* use the jaw with the largest area */
            prev = sides - 1;
            next = 1;
            maxlength = -1.0f;
            for (nJ = 0; nJ < sides; nJ++)
            {
                RwV3dSub(&edge[0],
                         &fbound[prev].vpVert->OC,
                         &fbound[nJ].vpVert->OC);
                RwV3dSub(&edge[1], &fbound[next].vpVert->OC,
                         &fbound[nJ].vpVert->OC);
                RwV3dCrossProduct(&normal, &edge[1], &edge[0]);
                length = RwV3dLength(&normal);
                if (length > maxlength)
                {
                    maxlength = length;
                    apoly->normal = normal;
                }

                /* skip very skinny triangles */
                _rwV3dNormalize(&edge[0], &edge[0]);
                _rwV3dNormalize(&edge[1], &edge[1]);
                length = RwV3dDotProduct(&edge[0], &edge[1]);
                if (length > 0.9999f) /* 0.81 degrees */
                {
                    apoly->normal.x = 0.0f;
                    apoly->normal.y = 0.0f;
                    apoly->normal.z = 0.0f;
                    maxlength = 0.0f;
                    break;
                }

                prev = nJ;
                next = next == sides - 1 ? 0 : next + 1;
            }
            if (maxlength > 0.0f)
            {
                RwV3dScale(&apoly->normal, &apoly->normal,
                           1.0f / maxlength);
            }

            bFirst = TRUE;
            nPcount++;
        }
    }

#ifdef AMB_SPECIFIC
    for (nI = 0; nI < buildSector->numPolygons; nI++)
    {
        RwReal              dummy;

        if (ImportSortPolygonCmp
            (&sortPolygons[nI], &sortPolygons[nI], &dummy) != 0)
        {
            RtWorldImportBuildVertex *srcbnd;

            PiDisplayMessage("failed plane test with self\n");
            ImportSortPolygonCmp(&sortPolygons[nI], &sortPolygons[nI],
                                 &dummy);
            srcbnd = sortPolygons[nI].vpFirst;
            while (srcbnd != sortPolygons[nI].vpLast)
            {
                char                buffer[128];

                sprintf(buffer,
                        "%08lx: (%f %f %f)\n",
                        srcbnd->vpVert,
                        srcbnd->vpVert->OC.x,
                        srcbnd->vpVert->OC.y, srcbnd->vpVert->OC.z);
                PiDisplayMessage(buffer);
                srcbnd++;
            }
        }
    }
#endif

    /* build a single boundary for each ImportGroup */
    newboundaries = rwSListCreate(sizeof(RtWorldImportBuildVertex));
    /* we don't want reallocs here as our rwSortPolygons reference it */
    nI = buildSector->numBoundaries;
    while (nI--)
    {
        rwSListGetNewEntry(newboundaries);
    }
    rwSListEmpty(newboundaries);
    /* ImportGroup like polygons together */
    nPcount =
        ImportGroup((void *) sortPolygons,
                    buildSector->numPolygons, ImportSortPolygonCmp,
                    newboundaries);
    /* clean up */
    RwFree(sortPolygons);
    for (nI = 0; nI < buildSector->numVertices; nI++)
    {
        rwSListDestroy(buildSector->vertices[nI].state.slist);
    }

    /* blow away old boundaries */
    RwFree(buildSector->boundaries);
    /* install our new merged boundaries */
    buildSector->numBoundaries = rwSListGetNumEntries(newboundaries);
    buildSector->boundaries = rwSListToArray(newboundaries);
    buildSector->numPolygons = nPcount;
    RWRETURNVOID();
}

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