/*
 * Particle System plug-in
 */

/****************************************************************************
 *                                                                          *
 *  Module  :   nodeParticleExpand.c                                        *
 *                                                                          *
 *  Purpose :   Expands screen-space vertices into particles (triangles)    *
 *                                                                          *
 ****************************************************************************/

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

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

#include "rpplugin.h"
#include <rpdbgerr.h>
#include "rpprtcls.h"

#if (!defined(DOXYGEN_SHOULD_SKIP_THIS))
static const char   rcsid[] __RWUNUSED__ =
    "@@(#)$Id: nodeParticleExpand.c,v 1.47 2001/07/23 12:50:38 Markj Exp $";
#endif /* (!defined(DOXYGEN_SHOULD_SKIP_THIS)) */

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

#define PRIVATEDATATYPE RxPipelineNodeParticleExpandData

#define MESSAGE(_string)                                                 \
    RwDebugSendMessage(rwDEBUGMESSAGE, "nodeParticleExpandCSL", _string)

/****************************************************************************
 Local Prototypes
 */
static void         ParticleExpandUVDealloc(RxPipelineNode * node);

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

   Functions

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

/*****************************************************************************
 _ParticleExpandNodePipelineNodeInitFn

 Initialises the private data (sets particles ON with colour (0, 0, 0, 0),
 a don't-change-the-colour special case, a NULL texture, additive blend modes
 and default (NULL) UV pointers)

 If drawn as a triangle, each particle will look like:
  <--xsize-->
   ___________________
 y|         |        /
 s|         |      /
 i|    P    |    /
 z|         |  /
 e|_________|/
  |        /
  |      /
  |    /
  |  /
  |/

 ...and if drawn as a quad:
  <--xsize-->
   _________
 y|         |
 s|         |
 i|    P    |
 z|         |
 e|_________|

 ...where P is the particle texture and the position of the particle
 (the vertex as it comes into this node). We don't use texture address
 clamping to prevent tiling of the texture within the triangle (no
 point if there are multiple frames of animation within the texture and
 not all hardware supports region clamping yet), so the texture must be
 transparent black where you don't want anything to show.
 */

static              RwBool
_ParticleExpandNodePipelineNodeInitFn(RxPipelineNode * self)
{

    RWFUNCTION(RWSTRING("_ParticleExpandNodePipelineNodeInitFn"));

    if (self)
    {
        PRIVATEDATATYPE     data;
        RwRGBA              defaultColour = { 0, 0, 0, 0 };

        data.particlesOn = TRUE;
        data.useQuads = TRUE;
        data.xSize = 1;
        data.ySize = 1;
        data.numFrames = 1;
        /* Default to no animation */
        data.animFlags = rxNODEPTEXANIMFLAGZERO;
        data.srcBlend = rwBLENDSRCALPHA;
        data.destBlend = rwBLENDONE;
        data.zWrite = FALSE;
        data.texture = (RwTexture *)NULL;
        /* Yes, they'll look like little triangles by default */
        data.color = defaultColour;
        /* {0, 0, 0, 0} means "leave devvert colours as they are" */
        data.U = (RwReal *)NULL;
        /* Default, means assume [0,0], [0,2], [2,0] for tris */
        data.V = (RwReal *)NULL;
        /* ...and [0,0], [0,1], [1,1], [1,0] for quads        */
        data.animRate = 33;
        /* ~30 fps animation when active */

        *(PRIVATEDATATYPE *) (self->privateData) = data;
        RWRETURN(TRUE);
    }
    RWRETURN(FALSE);
}

/*****************************************************************************
 _ParticleExpandNodePipelineNodeTermFn

 Free the U and V arrays if they've been allocated

 */
static void
_ParticleExpandNodePipelineNodeTermFn(RxPipelineNode * self)
{
    RWFUNCTION(RWSTRING("_ParticleExpandNodePipelineNodeTermFn"));

    if (self != NULL)
    {
        ParticleExpandUVDealloc(self);
    }
    RWRETURNVOID();
}

/* Related function - you must use this to allocate the UVs, it just makes
   sure everything is done right (and allocating memory in one module but
   freeing it in another is considered bad by the MSVC debug heap, and maybe
   others, and causes an assert on exit) */

/**
 * \ingroup rpprtcls
 * \ref RxPipelineNodeParticleExpandUVMalloc allocates memory for
 * U and V coordinate arrays for use with animated particles in
 * ParticleExpand.csl.
 *
 * The U and V coordinate arrays will be held in a ParticleExpand.csl
 * pipeline node's \ref RxPipelineNodeParticleExpandData private data once they
 * have been allocated. In order to ensure that memory gets cleaned up
 * correctly when pipelines are destroyed, this memory is to be allocated
 * through this function and deallocated automatically when the pipeline
 * node is destroyed.
 *
 * \param node  A pointer to a ParticleExpand.csl pipeline node
 * \param numFrames  \ref RwInt32 number of frames of animation for the particles
 * \param useQuads  \ref RwBool whether or to draw particles as quads or tris
 * \param Us  \ref RwReal ** pointer to receive a reference to the U-coord allocation
 * \param Vs  \ref RwReal ** pointer to receive a reference to the V-coord allocation
 *
 * \return TRUE on success, FALSE on failure
 *
 * \see RxNodeDefinitionGetParticleExpandCSL
 */
RwBool
RxPipelineNodeParticleExpandUVMalloc(RxPipelineNode * node,
                                     RwInt32 numFrames, RwBool useQuads,
                                     RwReal ** Us, RwReal ** Vs)
{
    RWAPIFUNCTION(RWSTRING("RxPipelineNodeParticleExpandUVMalloc"));

    if (node == NULL)
    {
        MESSAGE("NULL pointer passed to ParticleExpandUVMalloc");
        RWRETURN(FALSE);
    }

    if (numFrames > 0)
    {
        RwUInt32            vertsPerParticle =
            (useQuads == FALSE) ? (3) : (4);
        RwReal             *mem, *Umem, *Vmem;
        PRIVATEDATATYPE    *data;

        data = (PRIVATEDATATYPE *) (node->privateData);
        if (data == NULL)
        {
            MESSAGE
                ("Node has no private data allocated, cannot store texture animation UVs");
            RWRETURN(FALSE);
        }

        /* Get rid of any previously alloced UVs */
        ParticleExpandUVDealloc(node);

        mem =
            (RwReal *) RwMalloc(2 * numFrames * vertsPerParticle *
                                sizeof(RwReal));
        if (mem == NULL)
            RWRETURN(FALSE);

        Umem = mem;
        Vmem = &(mem[numFrames * vertsPerParticle]);

        data->U = Umem;
        data->V = Vmem;
        data->numFrames = numFrames; /* Make sure this is in synch */

        if (Us != NULL)
            *Us = Umem;
        if (Vs != NULL)
            *Vs = Vmem;

        RWRETURN(TRUE);
    }
    else
    {
        MESSAGE
            ("Particles cannot have less than one frame of texture animation");
        RWRETURN(FALSE);
    }
}

static void
ParticleExpandUVDealloc(RxPipelineNode * node)
{
    RWFUNCTION(RWSTRING("ParticleExpandUVDealloc"));

    if (node != NULL)
    {
        PRIVATEDATATYPE    *data =
            (PRIVATEDATATYPE *) node->privateData;

        if (data->U != NULL)
        {
            /* Data was allocated in one block not two
             * (see ParticleExpandUVMalloc() above...) */
            RwFree(data->U);
        }
        data->U = (RwReal *)NULL;
        data->V = (RwReal *)NULL;
        data->numFrames = 1;   /* Back to the default */
        RWRETURNVOID();
    }
    MESSAGE("NULL pointer passed to ParticleExpandUVDealloc()");
    RWRETURNVOID();
}

/*****************************************************************************
 _ParticleExpandNode

 Takes projected vertices and expands them into screenspace quads, so that
 particles are really cheap.
*/

#define RWSTRIDEDPTRINC(_ptr, _stride) \
   (((RwUInt8 *)(_ptr)) + _stride)

/* Swap top/bottom bits each time */
#define SRAND(_seed) \
   (_seed = ( (_seed >> 16) | (_seed << 16) )*1103515245 + 12345)
   /* (_seed = _seed*1103515245 + 12345) */

static              RwBool
_ParticleExpandNode(RxPipelineNodeInstance * self,
                    const RxPipelineNodeParam * params)
{
    PRIVATEDATATYPE    *particlesData;
    RwReal              defaultTriU[3] = { 0, 0, 2 }, defaultTriV[3] =
    {
    0, 2, 0}
    , defaultQuadU[4] =
    {
    0, 0, 1, 1}
    , defaultQuadV[4] =
    {
    0, 1, 1, 0};
    RwReal             *U = (RwReal *)NULL, *V = (RwReal *)NULL;
    RwReal              xRes, xResScaled, yRes, yResScaled;
    RwReal              minScreenX, minScreenY, maxScreenX, maxScreenY;
    RwV2d               vertCoordsTri[3] =
        { {-1, -1}, {-1, 3}, {3, -1} }, vertCoordsQuad[4] =
    {
        {
        -1, -1}
        ,
        {
        -1, 1}
        ,
        {
        1, 1}
        ,
        {
        1, -1}
    }
    , *vertCoords;
    RwUInt32            red = 0;
    RwUInt32            green = 0;
    RwUInt32            blue = 0;
    RwUInt32            alpha = 0;
    RwUInt32            numFrames;
    RwUInt32            vertsPerParticle;
    RwUInt32            i;
    RwUInt32            j;
    static RwUInt32     counter;
    RwUInt32            seed, randMask, frameMask;
    RwBool              changeColour, useQuads;
    RxPacket           *packet;
    RxHeap             *heap;
    RwCamera           *curCamera;
    RxVertexIndex      *remap = (RxVertexIndex *) NULL;
    RwUInt8            *rands = (RwUInt8 *) NULL, fakeRand = 0;
    RwUInt32            remapArraySize = 0, randsArraySize = 0;
    RwInt32             width;
    RwInt32             height;
    RpParticle          fakeParticle = { {0, 0, 0}, 
                                         0, 
                                         {0, 0, 0} };
    RxCluster           FakeParticles;
    RxCluster          *DevVerts;
    RxCluster          *CamVerts;
    RxCluster          *MeshState;
    RxCluster          *RenderState;
    RxCluster          *Indices;
    RxCluster          *Particles;
    RxMeshStateVector  *meshData;
    RxVertexIndex       oldNumVerts;
    RwUInt32            numDrawnParticles;
    RxRenderStateVector *rsvp;
    RxScrSpace2DVertex *srcVert, *dstVert, *emptyDevVert;
    RxCamSpace3DVertex *camVert;
    RpParticle         *particle;
    RwInt32             devVertStride;
    RwReal              recipZ, x, y, xSize, ySize;
    RxVertexIndex       srcVertNum, emptySrcVertNum, unMap;

    RWFUNCTION(RWSTRING("_ParticleExpandNode"));

    FakeParticles.flags = rxCLFLAGS_NULL;
    FakeParticles.stride = 0;
    FakeParticles.data = &fakeParticle;
    FakeParticles.currentData = &fakeParticle;
    FakeParticles.numAlloced = 0;
    FakeParticles.numUsed = 0;
    FakeParticles.clusterRef = (RxPipelineCluster *)NULL;
    FakeParticles.attributes = 0;

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

    RWASSERT(NULL != params);
    heap = RxPipelineNodeParamGetHeap(params);
    RWASSERT(NULL != heap);

    /* Cheap early-out */
    particlesData = (PRIVATEDATATYPE *) (self->privateData);
    RWASSERT(NULL != particlesData);
    if (particlesData->particlesOn == FALSE)
    {
        RxPacketDispatch(packet, 0, self);
        RWRETURN(TRUE);
    }

    useQuads = particlesData->useQuads;

    /* Animation defaults */
    numFrames = 1;
    counter = 0;
    randMask = 0;
    if (useQuads == FALSE)
    {
        vertsPerParticle = 3;
        vertCoords = vertCoordsTri;
        U = defaultTriU;
        V = defaultTriV;
    }
    else
    {
        vertsPerParticle = 4;
        vertCoords = vertCoordsQuad;
        U = defaultQuadU;
        V = defaultQuadV;
    }
    /* User-specified animation info */
    if ((particlesData->U != NULL) && (particlesData->V != NULL))
    {
        numFrames = particlesData->numFrames;
        U = particlesData->U;
        V = particlesData->V;
    }
    if (particlesData->animFlags & rxNODEPTEXANIMFLAGINC)
    {
        counter = (RpParticleSystemTimer() /
                   particlesData->animRate) % numFrames;
    }
    if (particlesData->animFlags & rxNODEPTEXANIMFLAGRANDOM)
    {
        randMask = 0xFFFFFFFF;
    }
    else
    {
        rands = (RwUInt8 *) & fakeRand;
    }

    if (*(RwUInt32 *) & (particlesData->color) == 0)
    {
        changeColour = FALSE;
    }
    else
    {
        changeColour = TRUE;
        red = particlesData->color.red;
        green = particlesData->color.green;
        blue = particlesData->color.blue;
        alpha = particlesData->color.alpha;
    }

    curCamera = RwCameraGetCurrentCamera();
    RWASSERT(NULL != curCamera);

    width = RwRasterGetWidth(RwCameraGetRaster(curCamera));
    xRes = (RwReal) width;
    height = RwRasterGetHeight(RwCameraGetRaster(curCamera));
    yRes = (RwReal) height;
    xResScaled = (0.5f * xRes) / RwCameraGetViewWindow(curCamera)->x;
    yResScaled = (0.5f * yRes) / RwCameraGetViewWindow(curCamera)->y;
#ifdef SKY2_DRVMODEL_H
    /* There's the lovely overdraw allowance on PS2
     * so particles needn't pop at the edges
     *  of the screen! Wahey! :) */
    minScreenX = -(2048.0f - (xRes * 0.5f));
    minScreenY = -(2048.0f - (yRes * 0.5f));
    maxScreenX = 4096.0f + minScreenX;
    maxScreenY = 4096.0f + minScreenY;
#else
    minScreenX = 0.0f;
    minScreenY = 0.0f;
    maxScreenX = xRes;
    maxScreenY = yRes;
#endif

    /* Initialise rand per packet */
    seed = 0;

    DevVerts = RxClusterLockWrite(packet, 0, self);
    CamVerts = RxClusterLockWrite(packet, 1, self);
    MeshState = RxClusterLockWrite(packet, 2, self);
    RenderState = RxClusterLockWrite(packet, 3, self);

    /* If we're rendering one tri per particle, we will
     * kill off Triangles and submit an unindexed trilist */
    Indices = RxClusterLockWrite(packet, 4, self);

    /* We can use particles data if it's present */
    Particles = RxClusterLockRead(packet, 5);
    frameMask = 0;
    if ((Particles != NULL) && (Particles->numAlloced > 0))
    {
        if (particlesData->animFlags & rxNODEPTEXANIMFLAGOVERRIDE)
            frameMask = 0xFFFFFFFF;
    }
    else
    {
        /* Create a fake cluster (it's read only, don't worry) so we use
         * fewer conditionals in the main loop
         * (I love this kinda stuff :) ) */
        Particles = &FakeParticles;
    }

    RWASSERT((DevVerts != NULL) && (DevVerts->numUsed > 0));
    devVertStride = DevVerts->stride;
    RWASSERT((CamVerts != NULL) && (CamVerts->numUsed > 0));
    RWASSERT((MeshState != NULL) && (MeshState->numUsed > 0));
    RWASSERT(RenderState != NULL);

    /* We NEED the indices cluster if we're drawing quads */
    RWASSERT((useQuads == FALSE) || (Indices != NULL));

    meshData = RxClusterGetCursorData(MeshState, RxMeshStateVector);
    oldNumVerts = (RxVertexIndex) meshData->NumVertices;
    numDrawnParticles = 0;

    /* Resize renderstate if it doesn't have any data already */
    if (RenderState->numUsed <= 0)
    {
        RxRenderStateVector *sv;

        RenderState = RxClusterInitializeData
            (RenderState, 1, sizeof(RxRenderStateVector));
        RWASSERT(NULL != RenderState);
        sv = RxClusterGetCursorData(RenderState, RxRenderStateVector);
        RWASSERT(NULL != sv);
        RxRenderStateVectorSetDefaultRenderStateVector(sv);
    }

    /* Because of the shuffling around of vertices,
     * a remap array is useful */
    if (remapArraySize < vertsPerParticle * oldNumVerts)
    {
        RwUInt32            bytes;

        /* No need to preserve last packet's data,
         * so don't risk a copy */
        if (remap != NULL)
            RxHeapFree(heap, remap);
        bytes = sizeof(RxVertexIndex) * vertsPerParticle * oldNumVerts;

        remap = (RxVertexIndex *) RxHeapAlloc(heap, bytes);
        RWASSERT(NULL != remap);
        remapArraySize = vertsPerParticle * oldNumVerts;
    }

    /* For the same reason,
     * it's good to store a rands array in parallel */
    if (randMask && (randsArraySize < oldNumVerts))
    {
        /* No need to preserve last packet's data,
         * so don't risk a copy */
        if (rands != NULL)
            RxHeapFree(heap, rands);
        rands =
            (RwUInt8 *) RxHeapAlloc(heap,
                                    sizeof(RwUInt8) * oldNumVerts);
        RWASSERT(NULL != rands);
        randsArraySize = oldNumVerts;
    }

    DevVerts =
        RxClusterResizeData(DevVerts, vertsPerParticle * oldNumVerts);
    RWASSERT(NULL != DevVerts);
    CamVerts =
        RxClusterResizeData(CamVerts, vertsPerParticle * oldNumVerts);
    RWASSERT(NULL != CamVerts);

    /* For particles as triangles, we submit an *unindexed*
     * trilist, else we alloc enough triangles */
    if (useQuads != FALSE)
    {
        RwUInt32            newSize =
            (vertsPerParticle - 2) * oldNumVerts * 3;
        if (Indices->numAlloced < newSize)
        {
            Indices =
                RxClusterInitializeData(Indices, newSize,
                                        sizeof(RxVertexIndex));
            RWASSERT(NULL != Indices);
        }
    }

    /* Set appropriate renderstate */
    rsvp = RxClusterGetCursorData(RenderState, RxRenderStateVector);
    RWASSERT(NULL != rsvp);
    rsvp->SrcBlend = particlesData->srcBlend;
    rsvp->DestBlend = particlesData->destBlend;
    if (particlesData->texture != NULL)
    {
        rsvp->TextureRaster =
            RwTextureGetRaster(particlesData->texture);
        rsvp->FilterMode =
            RwTextureGetFilterMode(particlesData->texture);
        rsvp->AddressModeU =
            RwTextureGetAddressingU(particlesData->texture);
        rsvp->AddressModeV =
            RwTextureGetAddressingV(particlesData->texture);
    }
    if (particlesData->zWrite == FALSE)
    {
        /* Turn off ZBuffer writing to avoid order-dependence */
        rsvp->Flags &= ~rxRENDERSTATEFLAG_ZWRITEENABLE;
    }
    else
    {
        rsvp->Flags |= rxRENDERSTATEFLAG_ZWRITEENABLE;
    }

    /* Do stuff! Groovy expantzhion bebbeh. */
    RxClusterResetCursor(DevVerts);
    RxClusterResetCursor(CamVerts);
    RxClusterResetCursor(Particles);

    /* The initial order of the vertices prior to shuffling.
     * There should be no need to clear/initialise
     * the whole array if our code works :o) */
    for (i = 0; i < oldNumVerts; i++)
    {
        remap[i] = (RxVertexIndex) i;
    }

    /* Initialise random numbers prior to shuffling too! */
    if (randsArraySize >= oldNumVerts)
    {
        for (i = 0; i < oldNumVerts; i++)
        {
            rands[i] = (RwUInt8) SRAND(seed);
        }
    }

    /* The vert we're currently converting into a triangle */
    srcVert = RxClusterGetCursorData(DevVerts, RxScrSpace2DVertex);
    RWASSERT(NULL != srcVert);
    /* The first vertex of the current triangle */
    dstVert = srcVert;
    /* The first free vertex at the end of the array */
    emptyDevVert =
        RxClusterGetIndexedData(DevVerts, RxScrSpace2DVertex,
                                oldNumVerts);

    srcVertNum = 0;
    emptySrcVertNum = oldNumVerts;
    for (i = 0; i < oldNumVerts; i++)
    {
        RwUInt32            frame;

        unMap = remap[srcVertNum];
        particle = RxClusterGetIndexedData(Particles,
                                           RpParticle, unMap);
        frame = particle->state;
        if ((frame != rpPARTICLEDEAD) &&
            (RxClusterGetIndexedData(CamVerts,
                                     RxCamSpace3DVertex,
                                     unMap)->clipFlags == 0))
        {
            RxScrSpace2DVertex  cachedVert;
            RwBool              clipped = FALSE;

            /* Cache values we'll need to construct the triangle */
            recipZ = RwIm2DVertexGetRecipCameraZ(srcVert);
            xSize = 0.4f * (particlesData->xSize * xResScaled * recipZ);
            ySize = 0.4f * (particlesData->ySize * yResScaled * recipZ);
            x = RwIm2DVertexGetScreenX(srcVert);
            y = RwIm2DVertexGetScreenY(srcVert);
            /* Copy the whole vert so
             * we don't miss any of its values when copying
             to the three destination verts */
            cachedVert = *srcVert;

            if (x + vertCoords[0].x * xSize < minScreenX)
                clipped = TRUE;
            if (y + vertCoords[0].y * ySize < minScreenY)
                clipped = TRUE;
            if (x + vertCoords[2].x * xSize > maxScreenX)
                clipped = TRUE;
            if (y + vertCoords[1].y * ySize > maxScreenY)
                clipped = TRUE;

            if (clipped == FALSE)
            {
                if (changeColour == FALSE)
                {
                    red = RwIm2DVertexGetRed(srcVert);
                    green = RwIm2DVertexGetGreen(srcVert);
                    blue = RwIm2DVertexGetBlue(srcVert);
                    alpha = RwIm2DVertexGetAlpha(srcVert);
                }

                seed = rands[randMask & (remap[srcVertNum])];

                /* Copy the next two verts
                 * out of the way if they're not clipped
                 * (and if we're not on the last vertex -
                 * yeah yeah, inefficient, blah) */
                if ((i + 1) != oldNumVerts)
                {
                    for (j = 0; j < (vertsPerParticle - 1); j++)
                    {
                        srcVert = (RxScrSpace2DVertex *)
                            RWSTRIDEDPTRINC(srcVert, devVertStride);
                        srcVertNum++;
                        unMap = remap[srcVertNum];
                        camVert =
                            RxClusterGetIndexedData(CamVerts,
                                                    RxCamSpace3DVertex,
                                                    unMap);
                        particle =
                            RxClusterGetIndexedData(Particles,
                                                    RpParticle, unMap);
                        if ((particle->state != rpPARTICLEDEAD)
                            && (camVert->clipFlags == 0))
                        {
                            *emptyDevVert = *srcVert;
                            remap[emptySrcVertNum++] =
                                remap[srcVertNum];
                            emptyDevVert = (RxScrSpace2DVertex *)
                                RWSTRIDEDPTRINC(emptyDevVert,
                                                devVertStride);
                        }
                        else
                        {
                            /* Clipped vertex culled,
                             * doesn't need turning into a particle */
                            i++;
                        }
                    }
                    srcVert = (RxScrSpace2DVertex *)
                        RWSTRIDEDPTRINC(srcVert, devVertStride);
                    srcVertNum++;
                }

                frame = vertsPerParticle *
                    (((seed & randMask) + (frame & frameMask) + counter)
                     % numFrames);

                RwIm2DVertexSetIntRGBA(&cachedVert,
                                       red, green, blue, alpha);

                /* Use srcVert to construct the triangle in the three verts just cleared */
                for (j = 0; j < vertsPerParticle; j++)
                {
                    *dstVert = cachedVert;
                    RwIm2DVertexSetScreenX(dstVert,
                                           x + vertCoords[j].x * xSize);
                    RwIm2DVertexSetScreenY(dstVert,
                                           y + vertCoords[j].y * ySize);
                    RwIm2DVertexSetU(dstVert, U[frame], recipZ);
                    RwIm2DVertexSetV(dstVert, V[frame], recipZ);
                    dstVert = (RxScrSpace2DVertex *)
                        RWSTRIDEDPTRINC(dstVert, devVertStride);
                    frame++;
                }

                numDrawnParticles++;
            }
            else
            {
                /* Clipping would reduce throughput lots and lots
                 * and with the presence of guard-bad clipping
                 * regions on most good hardware (PS2/nVidia/etc)
                 * culling should be sufficient - esp when
                 * particles are small and numerous */

                /* This vertex was clipped, 
                 * overwrite it with one from the end */
                emptyDevVert = (RxScrSpace2DVertex *)
                    RWSTRIDEDPTRINC(emptyDevVert, -devVertStride);
                emptySrcVertNum--;
                unMap = remap[emptySrcVertNum];
                camVert =
                    RxClusterGetIndexedData(CamVerts,
                                            RxCamSpace3DVertex, unMap);
                particle =
                    RxClusterGetIndexedData(Particles, RpParticle,
                                            unMap);
                while ((particle->state == rpPARTICLEDEAD)
                       && (camVert->clipFlags != 0))
                {
                    /* If all verts are clipped, we need to break out some time! */
                    if ((++i) >= oldNumVerts)
                        break;
                    emptyDevVert = (RxScrSpace2DVertex *)
                        RWSTRIDEDPTRINC(emptyDevVert, -devVertStride);
                    emptySrcVertNum--;
                    camVert =
                        RxClusterGetIndexedData(CamVerts,
                                                RxCamSpace3DVertex,
                                                remap[emptySrcVertNum]);
                    particle =
                        RxClusterGetIndexedData(Particles, RpParticle,
                                                unMap);
                }
                *srcVert = *emptyDevVert;
                remap[srcVertNum] = remap[emptySrcVertNum];
            }
        }
        else
        {
            /* This vertex was clipped, overwrite it with one from the end */
            emptyDevVert = (RxScrSpace2DVertex *)
                RWSTRIDEDPTRINC(emptyDevVert, -devVertStride);
            emptySrcVertNum--;
            unMap = remap[emptySrcVertNum];
            camVert =
                RxClusterGetIndexedData(CamVerts, RxCamSpace3DVertex,
                                        unMap);
            particle =
                RxClusterGetIndexedData(Particles, RpParticle, unMap);
            while ((particle->state == rpPARTICLEDEAD)
                   && (camVert->clipFlags != 0))
            {
                if ((++i) >= oldNumVerts)
                    break;
                emptyDevVert = (RxScrSpace2DVertex *)
                    RWSTRIDEDPTRINC(emptyDevVert, -devVertStride);
                emptySrcVertNum--;
                camVert = RxClusterGetIndexedData(CamVerts,
                                                  RxCamSpace3DVertex,
                                                  remap
                                                  [emptySrcVertNum]);
                particle =
                    RxClusterGetIndexedData(Particles, RpParticle,
                                            unMap);
            }
            *srcVert = *emptyDevVert;
            remap[srcVertNum] = remap[emptySrcVertNum];
        }
    }
    meshData->NumElements = numDrawnParticles * (vertsPerParticle - 2);
    meshData->NumVertices = numDrawnParticles * vertsPerParticle;

    DevVerts->numUsed = meshData->NumVertices;
    CamVerts->numUsed = meshData->NumVertices;
    Indices->numUsed = meshData->NumElements * 3;

    if (numDrawnParticles == 0)
    {
        /* Send the particles down the fourth ("AllParticlesCulled") output
         * (which is most likely left unconnected so that the packet will
         * be destroyed). Note that DevVerts, CamVerts and Triangles are
         * all flagged as INVALID on this output, so there's no need to
         * explicitly kill them here */
        RxPacketDispatch(packet, 3, self);
    }
    else
    {
        /* Set up triangles */
        if (useQuads == FALSE)
        {
            /* We kill off the indices cluster here (if
             * it was used) and submit an unindexed trilist
             * [currently (numAlloced == 0)|(data == NULL)
             *  is the sign of a dead cluster] */
            if (Indices->data != NULL)
                RxClusterDestroyData(Indices);
        }
        else
        {
            RxVertexIndex      *idxPtr1, *idxPtr2;

            j = 0;
            RxClusterResetCursor(Indices);

            idxPtr1 = RxClusterGetCursorData(Indices, RxVertexIndex);

            idxPtr2 = idxPtr1 + 3;

            for (i = 0; i < meshData->NumElements; i += 2)
            {
                idxPtr1[0] = (RxVertexIndex) j++;
                idxPtr1[1] = (RxVertexIndex) j;
                idxPtr2[2] = (RxVertexIndex) j++;
                idxPtr2[0] = (RxVertexIndex) j++;
                idxPtr1[2] = (RxVertexIndex) j;
                idxPtr2[1] = (RxVertexIndex) j++;

                idxPtr1 = idxPtr2 + 3;
                idxPtr2 = idxPtr1 + 3;
            }
        }

        /* Kill off camverts (if present), they no longer correspond to the mesh */
        RxClusterDestroyData(CamVerts);

        if (useQuads == FALSE)
        {
            /* Send the particles down the third
             * ("ParticlesOutWithoutTriangles") output */
            RxPacketDispatch(packet, 2, self);
        }
        else
        {
            /* Send the particles down the second
             * ("ParticlesOutWithTriangles") output */
            RxPacketDispatch(packet, 1, self);
        }
    }

    if (remap != NULL)
        RxHeapFree(heap, remap);
    if ((rands != NULL) && (rands != &fakeRand))
        RxHeapFree(heap, rands);

    RWRETURN(TRUE);
}

/**
 * \ingroup rpprtcls
 * \ref RxNodeDefinitionGetParticleExpandCSL returns a pointer to
 * a node to expand vertices into sprites.
 *
 * This node takes each input screen-space vertex and explodes it into
 * either three (if the node is drawing particles as triangles) or four
 * (if quads) vertices. Performing this operation right at the end of the
 * pipeline, beyond transformation, is very efficient.
 *
 * The node is capable of treating a specified particle texture as a
 * series of embedded frames and doing animation by modifying UV
 * coordinates over time and on a per-particle basis. The flags for
 * choosing animation mode are described at \ref RxPipelineNodePtExAnimFlag.
 * This flag, the texture to use, whether to draw tris or quads,
 * world-space particle size, blend mode, ZWrite enabling, an override
 * colour and speed of animation are all specifiable in the node's
 * \ref RxPipelineNodeParticleExpandData private data.
 *
 * This node has four outputs. The first is used when particle expansion
 * is turned off in the pipeline node's private data (packets are passed
 * straight to this output without modification). The second is used when
 * particles are output as quads and must this have indices included with
 * them. The third is used when particles are output as triangles which
 * can be rendered as an unindexed priimitive and so do not need indices
 * with them. The fourth output is used when all the particles are clipped
 * from the screen (note that particles just need to touch the clipping
 * planes to be clipped - this is not noticeable on most modern hardware
 * which has a guard band clipping region).
 *
 * \verbatim
   The node has four outputs
   The input requirements of this node:
  
   RxClScrSpace2DVertices  - required
   RxClCamSpace3DVertices  - required
   RxClMeshState           - required
   RxClRenderState         - optional
   RxClIndices             - don't want
   clusterRpParticles      - optional
  
   The characteristics of the first of this node's outputs:
  
   RxClScrSpace2DVertices  - no change
   RxClCamSpace3DVertices  - no change
   RxClMeshState           - no change
   RxClRenderState         - no change
   RxClIndices             - no change
   clusterRpParticles      - no change
  
   The characteristics of the second of this node's outputs:
  
   RxClScrSpace2DVertices  - valid
   RxClCamSpace3DVertices  - invalid
   RxClMeshState           - no change
   RxClRenderState         - valid
   RxClIndices             - valid
   clusterRpParticles      - no change
  
   The characteristics of the third of this node's outputs:
 
   RxClScrSpace2DVertices  - valid
   RxClCamSpace3DVertices  - invalid
   RxClMeshState           - no change
   RxClRenderState         - valid
   RxClIndices             - invalid
   clusterRpParticles      - no change
  
   The characteristics of the fourth of this node's outputs:
 
   RxClScrSpace2DVertices  - invalid
   RxClCamSpace3DVertices  - invalid
   RxClMeshState           - no change
   RxClRenderState         - valid
   RxClIndices             - invalid
   clusterRpParticles      - no change
  \endverbatim
 *
 * \return pointer to a node to expand vertices into sprites.
 *
 * \see RxPipelineNodeParticleExpandUVMalloc
 * \see RxNodeDefinitionGetParticleSystemInstanceCSL
 */
RxNodeDefinition   *
RxNodeDefinitionGetParticleExpandCSL(void)
{

    static RxClusterRef N1clofinterest[] = /* */
    { {&RxClScrSpace2DVertices, rxCLALLOWABSENT, 0},
    {&RxClCamSpace3DVertices, rxCLALLOWABSENT, 0},
    {&RxClMeshState, rxCLALLOWABSENT, 0},
    {&RxClRenderState, rxCLALLOWABSENT, 0},
    {&RxClIndices, rxCLALLOWABSENT, 0},
    {&clusterRpParticles, rxCLALLOWABSENT, 0}
    };

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

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

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

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

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

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

    static RwChar       _NoParticles[] = RWSTRING("NoParticles");
    static RwChar       _ParticlesOutTri[] =
        RWSTRING("ParticlesOutWithTriangles");
    static RwChar       _ParticlesOutNoTri[] =
        RWSTRING("ParticlesOutWithoutTriangles");
    static RwChar       _AllParticlesCulled[] =
        RWSTRING("AllParticlesCulled");

    static RxOutputSpec N1outputs[] = /* */
    { {_NoParticles,
       N1outclNoParticles,
       rxCLVALID_NOCHANGE},
    {_ParticlesOutTri,
     N1outclParticlesOutTri,
     rxCLVALID_NOCHANGE},
    {_ParticlesOutNoTri,
     N1outclParticlesOutNoTri,
     rxCLVALID_NOCHANGE},
    {_AllParticlesCulled,
     N1outclAllParticlesClipped,
     rxCLVALID_NOCHANGE}
    };

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

    static RwChar       _ParticleExpand_csl[] =
        RWSTRING("ParticleExpand.csl");

    static RxNodeDefinition nodeParticleExpandCSL = /* */
    { _ParticleExpand_csl,
        {_ParticleExpandNode,
         (RxNodeInitFn)NULL,
         (RxNodeTermFn)NULL,
         _ParticleExpandNodePipelineNodeInitFn,
         _ParticleExpandNodePipelineNodeTermFn,
         (RxPipelineNodeConfigFn)NULL,
         (RxConfigMsgHandlerFn)NULL },
        {NUMCLUSTERSOFINTEREST, N1clofinterest, N1inputreqs, NUMOUTPUTS,
         N1outputs},
        sizeof(PRIVATEDATATYPE),
        (RxNodeDefEditable) FALSE,
        0
    };

    RWAPIFUNCTION(RWSTRING("RxNodeDefinitionGetParticleExpandCSL"));

    RWRETURN(&nodeParticleExpandCSL);
}
