#error "BREAKME - Yeah, I'm just checking this in so nothing is checked out; RWSDK being shipped  - 31.3.2000, IDBS"

/*
 * {doc} nodeCullTriangleByTriPlane
 * @topic Culling back-facing triangles based on object-space triangle normals |
 * @index | nodeCullTriangleByTriPlane
 * @normal Copyright (c) Criterion Software Limited
 */
/****************************************************************************
 *                                                                          *
 * module : nodeCullTriangleByTriPlane.c                                    *
 *                                                                          *
 * purpose: Culls back-facing triangles based on object-space               *
 *          triangle normals in a RxTriPlanes cluster                       *
 *                                                                          *
 ****************************************************************************/

/****************************************************************************
 includes
 */

/* #include <assert.h> */
#include <float.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "rwcore.h"

#include "baworld.h"

#include "p2stdclsw.h"

#include "nodeCullTriangleByTriPlane.h"

static const char rcsid[] __RWUNUSED__ = "@@(#)$Id: nodeCullTriangleByTriPlane.c,v 1.39 2001/07/12 10:05:21 johns Exp $";


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

#define CODEDNORMAL2INTEGERTRIPLE()                     \
{                                                       \
    RxTriPlane *_triPlane =                             \
        RxClusterGetCursorData(clTriPlanes, RxTriPlane);\
    RwInt32 sign;                                       \
                                                        \
    sign = ((RwInt32) (_triPlane->N << 2)) >> 31;       \
    _x   =  _triPlane->N        & 0xFFU;                \
    _x   = (_x ^ sign) + (sign & 1);                    \
                                                        \
    sign = ((RwInt32) (_triPlane->N << 1)) >> 31;       \
    _y   = (_triPlane->N >>  8) & 0xFFU;                \
    _y   = (_y ^ sign) + (sign & 1);                    \
                                                        \
    sign = ((RwInt32)  _triPlane->N      ) >> 31;       \
    _z   = (_triPlane->N >> 16) & 0xFFU;                \
    _z   = (_z ^ sign) + (sign & 1);                    \
}

#define MESSAGE(string)                                                      \
    RwDebugSendMessage(rwDEBUGMESSAGE, "CullTriangleByTriPlane.csl", string)

/****************************************************************************
 local (static) globals
 */

static RwInt32      gTagTableLength;
static RwUInt32    *gTagTable;

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

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

   functions

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

/****************************************************************************
 CullTriangleByTriPlaneNodeInitFn

 called when the first pipeline that "CullTriangleByTriPlane.csl" is in is
 unlocked
*/

static              RwBool
CullTriangleByTriPlaneNodeInitFn(RxNodeDefinition * self __RWUNUSED__)
{
    RWFUNCTION(RWSTRING("CullTriangleByTriPlaneNodeInitFn"));

    RWASSERT(gTagTableLength == 0);
    RWASSERT(gTagTable == NULL);

    RWRETURN(TRUE);
}

/****************************************************************************
 CullTriangleByTriPlaneNodeTermFn

 called when node registry destroyed (i.e. normally once during application
 termination)
*/

static void
CullTriangleByTriPlaneNodeTermFn(RxNodeDefinition * self __RWUNUSED__)
{
    RWFUNCTION(RWSTRING("CullTriangleByTriPlaneNodeTermFn"));

    if (gTagTable != NULL)
    {
        RwFree(gTagTable);
        gTagTable = NULL;
    }

    gTagTableLength = 0;

    RWRETURNVOID();
}

/****************************************************************************
 ResizeTagTable

 grow gTagTable; this piece of code will likely be executed a handful of
 times at application startup & then never again
*/

static              RwBool
ResizeTagTable(RwInt32 newLength)
{

    void               *reallocResult =
        RwRealloc(gTagTable,
                  newLength * sizeof(RwUInt32));
    RWFUNCTION(RWSTRING("ResizeTagTable"));


    if (reallocResult == NULL)
    {
        RWRETURN(FALSE);
    }

    gTagTable = (RwUInt32 *) reallocResult;

    /* zero elements wot we have just added */

    memset(&gTagTable[gTagTableLength], 0x00U,
           (newLength - gTagTableLength) * sizeof(RwUInt32));

    gTagTableLength = newLength;

    RWRETURN(TRUE);
}

/****************************************************************************
 CullTriangleByTriPlaneNodePacket
*/

static              RwBool
CullTriangleByTriPlaneNodePacket(RxPacket * packet,
                                    RxPipelineNodeInstance * self)
{
    RxCluster          *clIndices;
    RxCluster          *clTriPlanes;
    RxCluster          *clVSteps;
    RxCluster          *clMeshState;
    RwV3d               vObjSpaceCamPos;
    RwMatrix           *matCam2Obj;
    RxMeshStateVector  *meshState;

    RWFUNCTION(RWSTRING("CullTriangleByTriPlaneNodePacket"));

    RWASSERT(NULL != packet);
    RWASSERT(NULL != self);

    clIndices = RxClusterLockWrite(packet, 0, self);
    clTriPlanes = RxClusterLockRead( packet, 1);
    clVSteps    = RxClusterLockWrite(packet, 2, self);
    clMeshState = RxClusterLockWrite(packet, 3, self);

    RWASSERT((NULL != clTriPlanes) && (clTriPlanes->numUsed > 0));
    RWASSERT((NULL != clIndices)   && (clIndices->numUsed   > 0));
    RWASSERT( NULL != clVSteps);
    RWASSERT((NULL != clMeshState) && (clMeshState->numUsed > 0));

    /* Important to set this up! */
    clVSteps->stride = (RwUInt16) sizeof(RxVStep);

    meshState = RxClusterGetCursorData(clMeshState, RxMeshStateVector);
    RWASSERT(NULL != meshState);

    /* there are cheaper ways of doing this, i know! */
    matCam2Obj = RwMatrixCreate();
    RwMatrixInvert(matCam2Obj, &meshState->Obj2Cam);
    vObjSpaceCamPos = matCam2Obj->pos;
    RwMatrixDestroy(matCam2Obj);

    RWASSERT(meshState->NumElements > 0);

    {
        RwUInt32    n                = meshState->NumElements,
                    numTrisAfterCull = meshState->NumElements;
        RxTriPlane *lastTriPlane, *curTriPlane;
        RxVertexIndex *lastIndices, *curIndices;
        RwInt32     _x, _y, _z;

        RwInt32 tagTableLengthRqd =
            ((meshState->NumVertices - 1) >> 5) + 1;

        if (tagTableLengthRqd > gTagTableLength)
        {
            if (!ResizeTagTable(tagTableLengthRqd + 32))
            {
                RWRETURN(FALSE);
            }
        }

        /* Note that these packed normals sacrifice accuracy, so we
           should add a fudge-factor here to cull slightly
           conservatively. This could bite us however with transparent
           geometry */

        lastIndices =
            RxClusterGetIndexedData(clIndices, RxVertexIndex,
                (meshState->NumElements - 1) * 3);
        RWASSERT(NULL != lastIndices);

        lastTriPlane =
            RxClusterGetIndexedData(clTriPlanes, RxTriPlane,
                meshState->NumElements - 1);
        RWASSERT(NULL != lastTriPlane);

        curIndices =
            RxClusterGetIndexedData(clIndices, RxVertexIndex, 0);
        RWASSERT(NULL != curIndices);
        curTriPlane =
            RxClusterGetIndexedData(clTriPlanes, RxTriPlane, 0);
        RWASSERT(NULL != curTriPlane);

        while (n--)
        {
            RwReal      t;

            CODEDNORMAL2INTEGERTRIPLE();

            /* DECODED INTEGERS -> REALS */
            t = (vObjSpaceCamPos.x * (RwReal) _x) +
                (vObjSpaceCamPos.y * (RwReal) _y) +
                (vObjSpaceCamPos.z * (RwReal) _z) -
                triPlane->w;

            if (!(*(RwInt32 *) & t < 0)) /* check for absence of sign bit */
            {
                /* Overwrite this culled tri with one from the end of the array */
                curIndices[0] = lastIndices[0];
                curIndices[1] = lastIndices[1];
                curIndices[2] = lastIndices[2];
               *curTriPlane = *lastTriPlane;

                lastIndices -= 3;
                lastTriPlane--;

                n--;
                numTrisAfterCull--;
            }
            else
            {
                RxVertexIndex v0 = indices[0],
                              v1 = indices[1],
                              v2 = indices[2];

                gTagTable[v0 >> 5] |= 1U << (v0 & 31);
                gTagTable[v1 >> 5] |= 1U << (v1 & 31);
                gTagTable[v2 >> 5] |= 1U << (v2 & 31);

                curTriPlane++;
                curIndices += 3;
            }
        }

        clIndices->numUsed   = numTrisAfterCull * 3;
        meshState->NumElements = numTrisAfterCull;

        if (numTrisAfterCull == 0)
        {
            /* The second output is (usually) left unconnected, so the
               now empty packet will die */
            RxPacketDispatch(packet, 1, self);

            /* won't need to zero tag table neivah; all culled => all zeroes! */
        }
        else
        {
            RxVStep *vstep;
            RwUInt32 step;

            clVSteps =
                RxClusterInitializeData(
                    clVSteps, meshState->NumVertices + 1, sizeof(RxVStep));
            RWASSERT(NULL != clVSteps);

            vstep = RxClusterGetCursorData(clVSteps, RxVStep);
            RWASSERT(NULL != vstep);
            step = 0;

            for (n = 0; n < meshState->NumVertices; n++)
            {
                /* can't encode step of > 255, so write step now */
                /* (will result in t/l of an extra vertex in rare circumstances!) */
                if ((gTagTable[n >> 5] & (1U << (n & 31)))
                    || (step == 255))
                {
                    (vstep++)->step = (unsigned char) step;
                    step = 0;
                }

                step++;
            }

            clVSteps->numUsed =
                vstep - RxClusterGetCursorData(clVSteps, RxVStep);

            /* In case step is requested from last vertex */
            vstep->step = (unsigned char) 1;

            RxPacketDispatch(packet, 0, self);
        }
    }

    RWRETURN(TRUE);
}

static              RwBool
CullTriangleByTriPlaneNodeFn(
    RxPipelineNodeInstance * self,
    const RxPipelineNodeParam * params __RWUNUSED__)
{
    RxPacket     *packet;
    RWFUNCTION(RWSTRING("CullTriangleByTriPlaneNodeFn"));

    RWASSERT(NULL != self);

    packet = RxPacketFetch(self);
    RWASSERT(NULL != packet);

    if (CullTriangleByTriPlaneNodePacket(packet, self) == FALSE)
    {
        RWRETURN(FALSE);
    }

    RWRETURN(TRUE);
}


/**
 * \ingroup rpworldp2generic
 * \ref RxNodeDefinitionGetCullTriangleByTriPlane returns a pointer to a node
 * to cull back-facing triangles based on object-space triangle normals
 *
 * The RxTriPlane cluster is present only when rendering RpWorldSectors,
 * which contain normals in this packed format. The world sector instancing
 * node should create and fill in this cluster. As well as culling triangles
 * (this disrupts the order of the triangles, which is assumed to be
 * unimportant), this node works out which vertices are used only by
 * back-facing triangles. It then generates a RxVStep cluster which allows
 * subsequent nodes to skip per-vertex operations on these vertices (such as
 * transformation and lighting). The RxVStep struct consists only of an
 * 8-bit unsigned 'step' value which tells you, when processing the vertices
 * in order, how many vertices to skip after the current one (the first value
 * being how many vertices to skip at the beginning of the array).
 *
 * If a packet is fully back-face culled then the packet is output to the
 * second output of the node (which is usually left disconnected, resulting
 * in the packet's destruction).
 *
 * The node has two outputs.
 * The input requirements of this node:
 *      \li RxClIndices            - required
 *      \li RxClTriPlanes          - required
 *      \li RxClVSteps             - don't want
 *      \li RxClMeshState          - required
 *
 * The characteristics of the first of this node's outputs:
 *      \li RxClIndices            - valid
 *      \li RxClTriPlanes          - no change
 *      \li RxClVSteps             - valid
 *      \li RxClMeshState          - valid
 *
 * The characteristics of the second of this node's outputs:
 *      \li RxClIndices            - invalid
 *      \li RxClTriPlanes          - no change
 *      \li RxClVSteps             - invalid
 *      \li RxClMeshState          - valid
 *
 * \return pointer to a node to cull back-facing triangles based on
 * object-space triangle normals.
 *
 * \see RxNodeDefinitionGetAtomicEnumerateLights
 * \see RxNodeDefinitionGetAtomicInstance
 * \see RxNodeDefinitionGetFastPathSplitter
 * \see RxNodeDefinitionGetLight
 * \see RxNodeDefinitionGetMaterialScatter
 * \see RxNodeDefinitionGetPostLight
 * \see RxNodeDefinitionGetPreLight
 *
 * \see RxNodeDefinitionGetWorldSectorEnumerateLights
 * \see RxNodeDefinitionGetWorldSectorInstance
 */
RxNodeDefinition *
RxNodeDefinitionGetCullTriangleByTriPlane(void)
{

    static RxClusterRef gNodeClusters[] = { /* */
        {&RxClIndices,   rxCLALLOWABSENT, rxCLRESERVED},
        {&RxClTriPlanes, rxCLALLOWABSENT, rxCLRESERVED},
        {&RxClVSteps,    rxCLALLOWABSENT, rxCLRESERVED},
        {&RxClMeshState, rxCLALLOWABSENT, rxCLRESERVED} };

    #define NUMCLUSTERSOFINTEREST \
        ((sizeof(gNodeClusters))/(sizeof(gNodeClusters[0])))


    static RxClusterValidityReq gNodeReqs[NUMCLUSTERSOFINTEREST] = { /* */
        rxCLREQ_REQUIRED,
        rxCLREQ_REQUIRED,
        rxCLREQ_DONTWANT,
        rxCLREQ_REQUIRED };

    static RxClusterValid gNodeOut1[NUMCLUSTERSOFINTEREST] = { /* */
        rxCLVALID_VALID,
        rxCLVALID_NOCHANGE,
        rxCLVALID_VALID,
        rxCLVALID_VALID };

    static RxClusterValid gNodeOut2[NUMCLUSTERSOFINTEREST] = { /* */
        rxCLVALID_INVALID,
        rxCLVALID_NOCHANGE,
        rxCLVALID_INVALID,
        rxCLVALID_VALID };

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

    static RxOutputSpec gNodeOuts[] = { /* */
        {_Output,                  /* Name */
         gNodeOut1,                /* OutputClusters */
         rxCLVALID_NOCHANGE },     /* AllOtherClusters */
        {_BackFaceCulled,          /* Name */
         gNodeOut2,                /* OutputClusters (triangles invalid) */
         rxCLVALID_NOCHANGE } };   /* AllOtherClusters */

    #define NUMOUTPUTS \
        ((sizeof(gNodeOuts))/(sizeof(gNodeOuts[0])))

    static RwChar _CullTriangleByTriPlane_csl[] = RWSTRING("CullTriangleByTriPlane.csl");

    static RxNodeDefinition nodeCullTriangleByTriPlaneCSL = { /* */
        _CullTriangleByTriPlane_csl,         /* Name */
        {                                    /* nodemethods */
         CullTriangleByTriPlaneNodeFn,     /* +-- nodebody */
         CullTriangleByTriPlaneNodeInitFn, /* +-- nodeinit */
         CullTriangleByTriPlaneNodeTermFn, /* +-- nodeterm */
         NULL,
         NULL,
         NULL,
         NULL},
        {                          /* Io */
         NUMCLUSTERSOFINTEREST,    /* +-- NumClustersOfInterest */
         gNodeClusters,            /* +-- ClustersOfInterest */
         gNodeReqs,                /* +-- InputRequirements */
         NUMOUTPUTS,               /* +-- NumOutputs */
         gNodeOuts                 /* +-- Outputs */
         },
        0,
        FALSE,
        0 };

    RWAPIFUNCTION(RWSTRING("RxNodeDefinitionGetCullTriangleByTriPlane"));

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

    RWRETURN(&nodeCullTriangleByTriPlaneCSL);
}

