/*
 * 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 "nhsbary.h"
#include "nhswing.h"
#include "nhssmplx.h"

typedef             RwReal
    (*ImportTriangleDepthFunction) (RtSimplexVertexPtr curr);

static const char   rcsid[] __RWUNUSED__ =
    "@@(#)$Id: nhssmplx.c,v 1.51 2001/08/28 10:28:52 mattt Exp $";

#if (!defined(OFFSET_EPSILON))
    /* #define OFFSET_EPSILON ( ((RwReal)1) / ((RwReal)(1<<3)) ) */
#define OFFSET_EPSILON ( ((RwReal)1) / ((RwReal)(1<<8)) )
#endif /* (!defined(OFFSET_EPSILON)) */

#if (defined(RWVERBOSE) && defined(RWDEBUG))

static void
ImportValidateTriangleFunc(RtSimplexState * simplexState,
                           const RtSimplexVertexPtr cut)
{
    const RtSimplexVertexPtr head = cut->next;
    const RwV3d        *const v0 = &head->vpVert->OC;
    const RtSimplexVertexPtr curr = head->next;
    const RwV3d        *const v1 = &curr->vpVert->OC;
    const RtSimplexVertexPtr next = curr->next;
    const RwV3d        *const v2 = &next->vpVert->OC;
    RwDReal             signedArea;
    RwDV3d              candidate;
    RwDV3d              e0;
    RwDV3d              e1;
    RwDV3d             *const normal = &simplexState->normal;

    RWFUNCTION(RWSTRING("ImportValidateTriangleFunc"));

    RwV3dSubMacro(&e0, v1, v0);
    RwV3dSubMacro(&e1, v2, v1);

    RwV3dCrossProductMacro(&candidate, &e0, &e1);

    signedArea = RwV3dDotProductMacro(&candidate, normal);

    if (signedArea < -OFFSET_EPSILON)
    {
        static int          inverted = 0;

        ++inverted;

        RWMESSAGE(("%d inverted %f [%f %f %f] [%f %f %f]",
                   inverted, signedArea,
                   candidate.x, candidate.y, candidate.z,
                   normal->x, normal->y, normal->z));
    }

#if (0)
    {
        RwDRealx            offset;
        const RwDReal       normal_w = simplexState->normal_w;

        offset = (RwDV3dDotProduct(v0, normal) + normal_w);
        RWASSERT(WithinEpsilonOfZero(offset, OFFSET_EPSILON));

        offset = (RwDV3dDotProduct(v1, normal) + normal_w);
        RWASSERT(WithinEpsilonOfZero(offset, OFFSET_EPSILON));

        offset = (RwDV3dDotProduct(v2, normal) + normal_w);
        RWASSERT(WithinEpsilonOfZero(offset, OFFSET_EPSILON));
    }

#endif /* (0) */

    RWRETURNVOID();
}

#define ValidateTriangle(_simplexState, _head) \
    ImportValidateTriangleFunc(_simplexState, _head)

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

#if (!defined(ValidateTriangle))
#define ValidateTriangle(_simplexState, _head) /* No op */
#endif /* (!defined(ValidateTriangle)) */

#if (!defined(BARYNORMALIZATIONSUPPRESSED))

static void
ImportBarycentricNormalize(RtDM4d bary)
{
    RwDReal             length2;

    RWFUNCTION(RWSTRING("ImportBarycentricNormalize"));

    length2 = (bary[0][0] * bary[0][0] +
               bary[1][0] * bary[1][0] + bary[2][0] * bary[2][0]);
    if (0 < length2)
    {
        RwDReal             factor;

        RWASSERT(0 < length2);
        factor = (RwDReal) sqrt(1 / length2);
        bary[0][0] *= factor;
        bary[1][0] *= factor;
        bary[2][0] *= factor;
        bary[3][0] *= factor;
    }

    length2 = (bary[0][1] * bary[0][1] +
               bary[1][1] * bary[1][1] + bary[2][1] * bary[2][1]);
    if (0 < length2)
    {
        RwDReal             factor;

        RWASSERT(0 < length2);
        factor = (RwDReal) sqrt(1 / length2);
        bary[0][1] *= factor;
        bary[1][1] *= factor;
        bary[2][1] *= factor;
        bary[3][1] *= factor;
    }

    length2 = (bary[0][2] * bary[0][2] +
               bary[1][2] * bary[1][2] + bary[2][2] * bary[2][2]);

    if (0 < length2)
    {
        RwDReal             factor;

        RWASSERT(0 < length2);
        factor = (RwDReal) sqrt(1 / length2);
        bary[0][2] *= factor;
        bary[1][2] *= factor;
        bary[2][2] *= factor;
        bary[3][2] *= factor;
    }

    RWRETURNVOID();
}

#define BARYCENTRICNORMALIZE(_bary) ImportBarycentricNormalize(_bary)

#endif /* (!defined(BARYNORMALIZATIONSUPPRESSED)) */

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

static void
ImportBarycentricFromCartesianMatrix(RtSimplexVertexPtr head)
{
    RtSimplexVertexPtr  curr;
    RtSimplexVertexPtr  next;
    RwReal              area;

    RWFUNCTION(RWSTRING("ImportBarycentricFromCartesianMatrix"));

    RWASSERT(NULL != head);
    curr = head->next;
    RWASSERT(NULL != curr);
    next = curr->next;
    RWASSERT(NULL != next);

    _rtImportBarycentricFromCartesianMatrix(head->bary,
                                            &area,
                                            &head->vpVert->OC,
                                            &curr->vpVert->OC,
                                            &next->vpVert->OC);

    BARYCENTRICNORMALIZE(head->bary);

    RWRETURNVOID();
}

static void
ImportFindBarycentricMatrices(RtSimplexState *
                              __RWUNUSED__ simplexState,
                              RtSimplexVertexPtr head)
{
    RtSimplexVertexPtr  curr;

    RWFUNCTION(RWSTRING("ImportFindBarycentricMatrices"));

    curr = head;
    do
    {
        RtSimplexVertexPtr  next;

        next = curr->next;
        ImportBarycentricFromCartesianMatrix(curr);
        curr = next;
    }
    while (curr != head);

    RWRETURNVOID();
}

static void
ImportFindEdges(RtSimplexState * __RWUNUSED__ simplexState,
                RtSimplexVertexPtr head)
{

    RtSimplexVertexPtr  curr;
    const RwV3d        *currV3d;

    RWFUNCTION(RWSTRING("ImportFindEdges"));

    curr = head;
    currV3d = &curr->vpVert->OC;

    do
    {
        const RtSimplexVertexPtr next = curr->next;
        const RwV3d        *const nextV3d = &next->vpVert->OC;

        RwV3dSubMacro(&curr->edge, nextV3d, currV3d);
        curr = next;
        currV3d = nextV3d;
    }
    while (curr != head);

    RWRETURNVOID();
}

static void
ImportFindSignedAreas(RtSimplexState * simplexState,
                      RtSimplexVertexPtr head)
{
    RtSimplexVertexPtr  curr;

    RWFUNCTION(RWSTRING("ImportFindSignedAreas"));

    curr = head;
    do
    {
        const RtSimplexVertexPtr next = curr->next;
        RwDV3d              cross;

        RwV3dCrossProductMacro(&cross, &curr->edge, &next->edge);
        curr->signedArea =
            RwV3dDotProductMacro(&cross, &simplexState->normal);
        /* concave |= (curr->signedArea < 0); */

#if (defined(VERBOSE_TRIANGULATION))
        LWD3DMESSAGE(("%s:%d:%s curr->signedArea is %g\n",
                      __FILE__, __LINE__, __Function__,
                      curr->signedArea));
#endif /* (defined(VERBOSE_TRIANGULATION)) */

        curr = next;
    }
    while (curr != head);

    RWRETURNVOID();
}

static              RwBool
ImportCutTriangle(RtSimplexState * simplexState, RtSimplexVertexPtr cut)
{
    RwBool              result = FALSE;
    PolyInfo           *pinfo;
    RtSimplexVertexPtr  curr;
    RtSimplexVertexPtr  head;
    RtSimplexVertexPtr  next;
    RtWingPoly         *WingPoly;
    RtWorldImport      *wpNoHS;
    RtWorldImportBuildVertex *boundaries;
    RwInt32             nI;
    RwDV3d              cross;
    RtWorldImportBuildVertexMode *mode;

    RWFUNCTION(RWSTRING("ImportCutTriangle"));

    wpNoHS = simplexState->wpNoHS;

    WingPoly = simplexState->WingPoly;
    pinfo = &WingPoly->pinfo;
    nI = WingPoly->nI;

#if (0)
    RWASSERT(pinfo->matIndex ==
             (RwInt16) wpNoHS->polygons[nI].matIndex);
#endif /* (0) */

    RWASSERT(NULL != cut);
    head = cut->next;
    RWASSERT(NULL != head);
    curr = head->next;
    RWASSERT(NULL != curr);
    next = curr->next;
    RWASSERT(NULL != next);

    boundaries = simplexState->boundaries;

    RWASSERT(NULL != head->vpVert);
    mode = &boundaries->mode;
    mode->vpVert = head->vpVert;
    boundaries->pinfo = *pinfo;
    boundaries++;

    RWASSERT(NULL != curr->vpVert);
    mode = &boundaries->mode;
    mode->vpVert = curr->vpVert;
    boundaries->pinfo = *pinfo;
    boundaries++;

    RWASSERT(NULL != next->vpVert);
    mode = &boundaries->mode;
    mode->vpVert = next->vpVert;
    boundaries->pinfo = *pinfo;
    boundaries++;

    /* mark end of polygon boundary and store polygon info */
    mode = &boundaries->mode;
    mode->vpVert = (RtWorldImportVertex *) NULL;
    boundaries->pinfo = *pinfo;
    boundaries++;

    simplexState->boundaries = boundaries;
    simplexState->numBoundaries += 4;
    simplexState->numPolygons++;

    /*
     * Unlink triangle
     */
    curr->next = (RtSimplexVertex *) NULL;
    cut->next = head;
    head->next = next;

    simplexState->vertexCount = simplexState->vertexCount - 1;

    /*
     * Maintain state
     */

    RwV3dSubMacro(&head->edge, &next->vpVert->OC, &head->vpVert->OC);

    RwV3dCrossProductMacro(&cross, &cut->edge, &head->edge);
    cut->signedArea =
        RwV3dDotProductMacro(&cross, &simplexState->normal);
    ImportBarycentricFromCartesianMatrix(cut);

    RwV3dCrossProductMacro(&cross, &head->edge, &next->edge);
    head->signedArea =
        RwV3dDotProductMacro(&cross, &simplexState->normal);
    ImportBarycentricFromCartesianMatrix(head);

    RWRETURN(result);
}

static              RwReal
ImportTriangleClosestVertex(RtSimplexState * simplexState,
                            RtSimplexVertexPtr head)
{
    RwReal              result = -RwRealMAXVAL;
    RtSimplexVertexPtr  curr;
    RtSimplexVertexPtr  next;
    RtSimplexVertexPtr  candidate;
    RtSimplexVertexPtr  vert = (RtSimplexVertex *) NULL;
    RtDV4d             *bary;
    RwInt32             count;

    RWFUNCTION(RWSTRING("ImportTriangleClosestVertex"));

    count = simplexState->vertexCount - 3;

    RWASSERT(0 < count);

    bary = head->bary;

    curr = head->next;
    next = curr->next;

    for (candidate = next->next; --count >= 0;
         candidate = candidate->next)
    {
        const RwV3d        *const position = &candidate->vpVert->OC;
        RtDV4d              weight;
        RwReal              manhattan;

        _rtImportWorldBaryFromCart(weight, bary, position);
        manhattan = RwRealMin3(weight[0], weight[1], weight[2]);

        if ((!vert) || (result < manhattan))
        {
            vert = candidate;
            result = manhattan;
        }

    }

    RWRETURN(result);
}

static              RwReal
ImportTrianglePositionDepth(RtSimplexVertexPtr curr)
{
    RwReal              result;
    RwReal              PositionDepth;
    const RwV3d        *Position;

    RWFUNCTION(RWSTRING("ImportTrianglePositionDepth"));

    RWASSERT(curr);
    Position = &curr->vpVert->OC;
    PositionDepth = (Position->x + Position->y + Position->z);
    result = PositionDepth;

    curr = curr->next;
    Position = &curr->vpVert->OC;
    PositionDepth = (Position->x + Position->y + Position->z);
    result = RwRealMax2(PositionDepth, result);

    curr = curr->next;
    Position = &curr->vpVert->OC;
    PositionDepth = (Position->x + Position->y + Position->z);
    result = RwRealMax2(PositionDepth, result);

    RWRETURN(result);
}

static              RwReal
ImportTriangleTexCoordsDepth(RtSimplexVertexPtr curr)
{

    RwReal              result;
    RwReal              texCoordsDepth;
    const RwTexCoords  *texCoords;

    RWFUNCTION(RWSTRING("ImportTriangleTexCoordsDepth"));

    RWASSERT(curr);
    texCoords = &curr->vpVert->texCoords[0];
    texCoordsDepth = (texCoords->u + texCoords->v);
    result = texCoordsDepth;

    curr = curr->next;
    texCoords = &curr->vpVert->texCoords[0];
    texCoordsDepth = (texCoords->u + texCoords->v);
    result = RwRealMax2(texCoordsDepth, result);

    curr = curr->next;
    texCoords = &curr->vpVert->texCoords[0];
    texCoordsDepth = (texCoords->u + texCoords->v);
    result = RwRealMax2(texCoordsDepth, result);
    RWRETURN(result);
}

static void
ImportBestTriangleCut(RtSimplexState * simplexState,
                      RtSimplexVertexPtr cut)
{
    RtSimplexVertexPtr  head;

    RWFUNCTION(RWSTRING("ImportBestTriangleCut"));

    RWASSERT(simplexState != ((RtSimplexState *) NULL));
    RWASSERT(cut != ((RtSimplexVertexPtr) NULL));

    ValidateTriangle(simplexState, cut);
    ImportCutTriangle(simplexState, cut);

    simplexState->head = cut;
    head = simplexState->head;

    RWRETURNVOID();
}

static void
ImportBestTriangleFind(RtSimplexState * simplexState)
{
    RtSimplexVertexPtr  cutInterior = (RtSimplexVertex *) NULL;
    RtSimplexVertexPtr  cutDeep = (RtSimplexVertex *) NULL;
    RtSimplexVertexPtr  cut;
    RtSimplexVertexPtr  head;

    RWFUNCTION(RWSTRING("ImportBestTriangleFind"));

    head = simplexState->head;

    if (head)
    {
        RtWorldImport      *const nohsworld = simplexState->wpNoHS;
        const RwInt32       matInd = head->vpVert->matIndex;
        const RpMaterial   *const material =
            RtWorldImportGetMaterialMacro(nohsworld, matInd);
        const RwBool        hasTexture = (material
                                          && material->texture);
        const ImportTriangleDepthFunction ImportTriangleDepth =
            (hasTexture ?
             ImportTriangleTexCoordsDepth :
             ImportTrianglePositionDepth);
        RwReal              mostInterior = RwRealMAXVAL;
        RwReal              mostDeep = RwRealMAXVAL;
        RtSimplexVertexPtr  curr = head;

#if (0)
        RWMONITOR(("%d == hasTexture %p == material %p == material->texture", 
                   hasTexture, material, material ? material->texture : NULL));
#endif /* (0) */

        do
        {
            const RtSimplexVertexPtr next = curr->next;

            if (next->signedArea >= 0)
            {
                /* The candidate triangle is convex ..  */
                const RwReal        closest =
                    ImportTriangleClosestVertex(simplexState, next);

                if ((!cutInterior) || (mostInterior > closest))
                {
                    cutInterior = curr;
                    mostInterior = closest;
                }

                if ( (-_AREA_EPSILON) > closest)
                {
                    /* No other vertices within the candidate triangle ..  */
                    const RwReal        depth = ImportTriangleDepth(next);

                    if ((!cutDeep) || (mostDeep > depth))
                    {
                        cutDeep = curr;
                        mostDeep = depth;
                    }

                }
            }

            curr = next;
        }
        while (curr != head);

        /* RWASSERT((!cutInterior) || (mostInterior < BARY_EPSILON)); */

#if (defined(RWVERBOSE) && defined(RWDEBUG))
        if (!((!cutInterior) || (mostInterior < BARY_EPSILON)))
        {
            RWMESSAGE(("%p == cutInterior", cutInterior));
            RWMESSAGE(("%f == mostInterior", mostInterior));
        }
#endif /* (defined(RWVERBOSE) && defined(RWDEBUG)) */

#if (0 && defined(PREFERINTERIOR) )
        cut = (cutInterior ? cutInterior : (cutDeep ? cutDeep : head));
#else /* (0 && defined(PREFERINTERIOR) ) */
        cut = (cutDeep ? cutDeep : (cutInterior ? cutInterior : head));
#endif /* (0 && defined(PREFERINTERIOR) ) */

        ImportBestTriangleCut(simplexState, cut);
    }

    RWRETURNVOID();
}

static              RwBool
ImportStorePolygon(RtSimplexState * simplexState)
{
    RwBool              result = FALSE;
    RtSimplexVertexPtr  head;

    RWFUNCTION(RWSTRING("ImportStorePolygon"));
    RWASSERT(NULL != simplexState);

    head = simplexState->head;

    if (head)
    {

        /* prime edges */
        ImportFindEdges(simplexState, head);

        /* find signed area */
        ImportFindSignedAreas(simplexState, head);

        /* prime Barycentric Matrices */
        ImportFindBarycentricMatrices(simplexState, head);

        while (simplexState->vertexCount > 3)
        {
            ImportBestTriangleFind(simplexState);
        }

        if (simplexState->vertexCount > 2)
        {
            head = simplexState->head;
            ValidateTriangle(simplexState, head);
            ImportCutTriangle(simplexState, head);
        }

    }

    simplexState->head = (RtSimplexVertex *) NULL;
    RWASSERT(2 >= simplexState->vertexCount);
    simplexState->vertexCount = 0;

    RWRETURN(result);
}

static RtWingEdgeReference *
ImportSimplexInitialize(RtWingEdgeReference * curr, void *state)
{
    RtSimplexState     *simplexState = (RtSimplexState *) state;
    RtSimplexVertexPtr  target;
    RtWing             *currWing;
    RtWing             *nextWing;
    RtWingEdgeReference *next;
    RtWingPoly         *OtherPoly;
    RtWingPoly         *WingPoly;
    RtWorldImportVertex *b;
    RwBool              storeEdge;

    RWFUNCTION(RWSTRING("ImportSimplexInitialize"));
    RWASSERT(NULL != curr);
    RWASSERT(NULL != simplexState);

    WingPoly = simplexState->WingPoly;

    currWing = curr->pEdge;
    b = currWing[curr->sense].Vert;

    next = &currWing[curr->sense].Next;
    RWASSERT(NULL != next);
    nextWing = next->pEdge;

    RWASSERT(WingPoly == currWing[curr->sense].WingPoly);
    RWASSERT(WingPoly == nextWing[next->sense].WingPoly);

    OtherPoly = currWing[1 - curr->sense].WingPoly;
    storeEdge = (nextWing[1 - next->sense].WingPoly != OtherPoly);

    if (storeEdge)
    {
        target = simplexState->head++;
        target->vpVert = b;
        target->next = simplexState->head;
    }
    else
    {
        RtWorldImportVertex *a = currWing[1 - curr->sense].Vert;
        RtWorldImportVertex *c = nextWing[1 - next->sense].Vert;
        RtWorldImportVertex *d = nextWing[next->sense].Vert;
        const RtBarySupport *const support = &WingPoly->support;
        const RtDV4d       *const bary = &support->bary[0];
        RwDReal             signedArea;
        RwDV3d              F, E, cross;
        RwDV3d              normal;
        RwDReal             normal_w;

        normal.x = bary[0][3];
        normal.y = bary[1][3];
        normal.z = bary[2][3];
        normal_w = bary[3][3];

        RWASSERT(c == b);

        RwV3dSubMacro(&E, &b->OC, &a->OC);
        RwV3dSubMacro(&F, &d->OC, &c->OC);

        RwV3dCrossProductMacro(&cross, &E, &F);
        signedArea = RwV3dDotProductMacro(&cross, &normal);

        storeEdge = !WithinEpsilonOfZero(signedArea, BARY_EPSILON);

        if (storeEdge)
        {
            target = simplexState->head++;
            target->vpVert = b;
            target->next = simplexState->head;
        }
    }

    RWRETURN(curr);
}

void
_rtImportWingPolyTriangulate(RtSimplexState * simplexState,
                             RtWingPoly * WingPoly)
{

    RwInt32             vertexCount;
    RtBarySupport      *support;

    RWFUNCTION(RWSTRING("_rtImportWingPolyTriangulate"));

    RWASSERT(NULL != simplexState);
    RWASSERT(NULL != WingPoly);

    simplexState->WingPoly = WingPoly;

    support = &WingPoly->support;

    simplexState->normal.x = support->bary[0][3];
    simplexState->normal.y = support->bary[1][3];
    simplexState->normal.z = support->bary[2][3];
    simplexState->normal_w = support->bary[3][3];

    simplexState->head = simplexState->simplexBuffer;

    _rtImportWingPolyForAllEdges(WingPoly, ImportSimplexInitialize,
                                 simplexState);

    vertexCount = simplexState->head - simplexState->simplexBuffer;

    simplexState->vertexCount = vertexCount;

#if (0)
    RWMONITOR(("%d == vertexCount", vertexCount));
#endif /* (0) */

    if (2 < vertexCount)
    {
        simplexState->head[-1].next = simplexState->simplexBuffer;
        simplexState->head = simplexState->simplexBuffer;

        ImportStorePolygon(simplexState);

    }

    RWRETURNVOID();

}

#if (0 && defined (RWUNUSED))

static              RwReal
ImportFacedness(RtSimplexVertexPtr head, RwV3d * normal)
{
    RwReal              result = 0.0;
    RtSimplexVertexPtr  curr;
    RtSimplexVertexPtr  next;
    RwV3d               head_edge;
    RwV3d               curr_edge;
    RwV3d               cross;

    RWFUNCTION(RWSTRING("ImportFacedness"));

    RWASSERT(NULL != head);
    curr = head->next;
    RWASSERT(NULL != curr);
    next = curr->next;
    RWASSERT(NULL != next);

    RwV3dSub(&head_edge, &curr->vpVert->OC, &head->vpVert->OC);
    RwV3dSub(&curr_edge, &next->vpVert->OC, &curr->vpVert->OC);

    RwV3dCrossProduct(&cross, &head_edge, &curr_edge);

    result = RwV3dDotProduct(&cross, normal);

    RWRETURN(result);
}

static RwV3d       *
ImportBestFitNormal(RtSimplexVertexPtr head, RwV3d * normal)
{

    RtSimplexVertexPtr  curr;
    RtSimplexVertexPtr  next;
    RwReal              area_squared;
    RwV3d              *head_position;
    RwV3d              *position;
    RwV3d              *curr_edge;

    RWFUNCTION(RWSTRING("ImportBestFitNormal"));
    RWASSERT(NULL != head);
    RWASSERT(NULL != normal);

    normal->x = 0;
    normal->y = 0;
    normal->z = 0;

    head_position = &head->vpVert->OC;

    curr = head->next;
    curr_edge = &curr->edge;

    position = &curr->vpVert->OC;
    RwV3dSub(curr_edge, position, head_position);

    for (next = curr->next; next != head; next = next->next)
    {
        RwV3d               cross;
        RwV3d              *next_edge;

        next_edge = &next->edge;
        position = &next->vpVert->OC;
        RwV3dSub(next_edge, position, head_position);
        RwV3dCrossProduct(&cross, curr_edge, next_edge);
        RwV3dAdd(normal, &cross, normal);
        curr_edge = next_edge;
    }

    area_squared = RwV3dDotProduct(normal, normal);

    if (0 < area_squared)
    {
        const RwReal        factor = (RwReal) sqrt(1 / area_squared);

        RwV3dScale(normal, normal, factor);
    }
    else
    {
        normal = NULL;
    }

    RWRETURN(normal);
}
#endif /* (0) */
