/*
 * Skin plugin
 */

/**********************************************************************
 *
 * File : rpskbone.c
 *
 * Abstract : RpBone-dependant module of RpSkin
 *
 **********************************************************************
 *
 * This file is a product of Criterion Software Ltd.
 *
 * This file is provided as is with no warranties of any kind and is
 * provided without any obligation on Criterion Software Ltd. or
 * Canon Inc. to assist in its use or modification.
 *
 * Criterion Software Ltd. will not, under any
 * circumstances, be liable for any lost revenue or other damages arising
 * from the use of this file.
 *
 * Copyright (c) 1999 Criterion Software Ltd.
 * All Rights Reserved.
 *
 * RenderWare is a trademark of Canon Inc.
 *
 ************************************************************************/

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

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

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

#include <rwcore.h>
#include <rpworld.h>
#include <rtslerp.h>
#include <rtquat.h>
#include <rpanim.h>
#include <rpbone.h>
#include <rpskin310.h>

#include "matblend.h"
#include "skinpriv.h"
#include "rpskbone.h"

#if (!defined(DOXYGEN_SHOULD_SKIP_THIS))
static const char   rcsid[] __RWUNUSED__ =
    "@@(#)$Id: rpskbone.c,v 1.10 2001/09/25 09:19:29 johns Exp $";
#endif /* (!defined(DOXYGEN_SHOULD_SKIP_THIS)) */

/****************************************************************************
 Defines
 */

/* Defines from rpbone.c */

#define rpBONEFLAGNONE              0x00
#define rpBONEFLAGSKINDIRTY         0x01
#define rpBONEFLAGSKINWASDIRTY      0x02
#define rpBONEFLAGANIMATE           0x04

#define RPBONEFRAMEGETDATA(frame)                               \
    ((RpBone **)(((RwUInt8 *)frame) +                           \
                 RpBoneFrameDataOffset))

#define RPBONEFRAMEGETCONSTDATA(frame)                          \
    ((const RpBone **)(((const RwUInt8 *)frame) +               \
                       RpBoneFrameDataOffset))

#define RPBONEGEOMGETDATA(geom)                                 \
    ((rpBoneGeomData **)(((RwUInt8 *)geom) +                    \
                         RpBoneGeomBoneListOffset))

#define RPBONEGEOMGETCONSTDATA(geom)                            \
    ((const rpBoneGeomData **)(((const RwUInt8 *)geom) +        \
                               RpBoneGeomBoneListOffset))

#define ROUNDUP16(x)      (((RwUInt32)(x) + 16 - 1) & ~(16 - 1))

#define DEFAULTTAG  -1

/* Maximum number of bones we can handle in a single model */
#define MAXBONES 64

#define _EPSILON          ((RwReal)(0.001))

/****************************************************************************
 Local types
 */

/* From rpbone.c */

typedef struct RpBone RpBone;
struct RpBone
{
    RwFrame            *frame;  /* The frame we are attached to */
    RwMatrix            skinToBone; /* Skin->Bone space matrix */
    RwMatrix            skinMatrix; /* Matrix to update skin vertices */
    RwInt32             flags;  /* Bone flags (eg skin dirty) */
};

typedef struct rpBoneList rpBoneList;
struct rpBoneList
{
    RwUInt32            start, length;
    RwInt32             boneTag;
    RpBone             *bone;
};

typedef struct rpBoneGeomData rpBoneGeomData;
struct rpBoneGeomData
{
    rpBoneList         *boneList; /* Bone list */
    RwV3d              *vertices; /* Original vertices */
    RwV3d              *normals; /* Original normals */
};

typedef struct RpSkBoneState RpSkBoneState;
struct RpSkBoneState
{
    int                 CurrentLevel /* = 0 */ ;
    int                 LastLevel /* = 0 */ ;
    RwBool              bChildren;
    RpSkinBoneInfo     *pCurrentBone;
    RpSkinBoneInfo     *pLastBone;
    RwInt32             ExtractSequenceFrameNumber;
    RwChar             *pExtractSequenceName /* = NULL */ ;
    RpAnimSequence     *pTranslateSequences[MAXBONES];
    RpAnimSequence     *pRotateSequences[MAXBONES];
    RwFrame            *pDefaultFrames[MAXBONES];
};

/****************************************************************************
 Local (static) globals
 */


static RpSkBoneState *SkBone;

/****************************************************************************
 Globals
 */


/****************************************************************************
 Local Function Prototypes
 */

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

/****************************************************************************
SkinGenerateCountBonesCallback

 Callback to perform first part of skin generation - counting the bones.

 Inputs :   RwFrame *       A pointer to a frame in the skeletal hierarchy
            void *          A pointer to the skin we're generating

 Outputs:   RwObject *      The frame pointer passed in
 */

static RwFrame     *
SkinGenerateCountBonesCallback(RwFrame * pFrame, void *pData)
{
    RpSkin             *pSkin = (RpSkin *) pData;

    RWFUNCTION(RWSTRING("SkinGenerateCountBonesCallback"));
    RWASSERT(pFrame);
    RWASSERT(pData);

    /* First, count the number of bones. */

    pSkin->numBones++;

    RwFrameForAllChildren(pFrame, SkinGenerateCountBonesCallback,
                          pData);

    RWRETURN(pFrame);

}

/****************************************************************************
SkinGenerateHierarchyCallback

 Callback to generate the bones heirarchy - we use an array of animation
 frames with PUSH and POP flags to infer the heirarchy, rather than explicit
 pointers.

 Inputs :   RwFrame *       A pointer to a frame in the skeletal hierarchy
            void *          A pointer to the skin we're generating

 Outputs:   RwObject *      The frame pointer passed in
 */

static RwFrame     *
SkinGenerateHierarchyCallback(RwFrame * pFrame, void *pData)
{
    RpSkinBoneInfo     *pBoneInfo;

    RWFUNCTION(RWSTRING("SkinGenerateHierarchyCallback"));
    RWASSERT(pFrame);
    RWASSERT(pData);

    pBoneInfo = SkBone->pCurrentBone++;
    pBoneInfo->flags = rpSKINANIMATEVERTEXGROUP;
    pBoneInfo->boneTag = _rpAnimSeqGetFrameTag(pFrame);

    if (SkBone->CurrentLevel > SkBone->LastLevel)
    {
        /* Found a child - need to push parent matrix */
        pBoneInfo->flags |= rpSKINPUSHPARENTMATRIX;
    }

    SkBone->LastLevel = SkBone->CurrentLevel;

    SkBone->CurrentLevel++;

    SkBone->bChildren = FALSE;

    RwFrameForAllChildren(pFrame, SkinGenerateHierarchyCallback, pData);

    SkBone->CurrentLevel--;

    SkBone->LastLevel = SkBone->CurrentLevel - 1;

    if (SkBone->bChildren == FALSE)
    {
        /* No children - must pop matrix */
        pBoneInfo->flags |= rpSKINPOPPARENTMATRIX;
    }
    else
    {
        /* Last child does not push the matrix */

        SkBone->pLastBone->flags &= ~rpSKINPUSHPARENTMATRIX;
    }

    SkBone->pLastBone = pBoneInfo;

    SkBone->bChildren = TRUE;

    RWRETURN(pFrame);

}

/*******************************************************************
 * The below have been stolen from RW main source to customize for
 * sorting skinned data. Only change is to maintain and return a
 * pointer to the vertexmap allowing us to sort the skinning data
 */

/* Used to sort geoemtry vertices by material */
typedef struct SortVert SortVert;
struct SortVert
{
    /* Top 2 bits hold which vert of the face this was (0, 1, 2) */
    RwUInt32            faceIndex;
    RwInt16             matIndex;
    RwUInt16            origIndex;
};

static int
SortVertsByMaterialCB(const void *data1, const void *data2)
{
    const SortVert     *vert1 = (const SortVert *) data1;
    const SortVert     *vert2 = (const SortVert *) data2;
    RwInt16             matIndex1, matIndex2;
    RwUInt16            origIndex1, origIndex2;

    RWFUNCTION(RWSTRING("SortVertsByMaterialCB"));
    RWASSERT(vert1 != NULL);
    RWASSERT(vert2 != NULL);

    matIndex1 = vert1->matIndex;
    matIndex2 = vert2->matIndex;

    /* Any verts found to be different (on material even if not original
     * vertIndex) will eventually end up as different verts in the new
     * geometry, so verts will be duplicated at material boundaries. This sort
     * takes place before the sort on indices, so verts should end up index-
     * sorted within material runs */
    if (matIndex1 > matIndex2)
    {
        RWRETURN(1);
    }
    else if (matIndex1 < matIndex2)
    {
        RWRETURN(-1);
    }

    /* Sort on vertIndex so SortVerts generated from the same original vertex
     * (i.e by all the triangles which share that vertex) are grouped and we
     * get verts sorted on index within materials (i.e when the above two tests
     * don't find a difference, we sort on index) */
    origIndex1 = vert1->origIndex;
    origIndex2 = vert2->origIndex;

    if (origIndex1 > origIndex2)
    {
        RWRETURN(1);
    }
    else if (origIndex1 < origIndex2)
    {
        RWRETURN(-1);
    }

    RWRETURN(0);
}

static RpGeometry  *
SkinGeometrySortByMaterial(const RpGeometry * source,
                           RwUInt16 ** vertexMapPtr)
{
    RpGeometry         *newGeom = (RpGeometry *) NULL;
    RwUInt32            flags = RpGeometryGetFlags(source);
    RwBool              preLit, textured, normals;
    SortVert           *sortVerts = (SortVert *) NULL;
    RwUInt16           *vertexMap = (unsigned short *) NULL;
    RwInt32             currentIndex;
    RwInt32             i;
    RwRGBA             *preLitSrc = (RwRGBA *) NULL;
    RwRGBA             *preLitDest = (RwRGBA *) NULL;
    RwTexCoords        *uvSrc = (RwTexCoords *) NULL;
    RwTexCoords        *uvDest = (RwTexCoords *) NULL;
    RwV3d             **normalsSrc = (RwV3d **) NULL;
    RwV3d             **normalsDest = (RwV3d **) NULL;
    RwV3d             **posSrc = (RwV3d **) NULL;
    RwV3d             **posDest = (RwV3d **) NULL;
    RwInt32             numNewVerts;
    RwUInt32            bytes;

    /* This sorts the vertices in a geometry by material, duplicating
     * vertices at material boundaries, and outputs a new RpGeometry */
    RWFUNCTION(RWSTRING("SkinGeometrySortByMaterial"));
    RWASSERT(source != NULL);

#if (0)
    numNewVerts = (RwInt32) (1.25f * source->numVertices);
#endif /* (0) */

    bytes = source->numMorphTargets * sizeof(RwV3d *);
    normalsSrc = (RwV3d **) RwMalloc(bytes);
    memset(normalsSrc, 0, bytes);

    bytes = source->numMorphTargets * sizeof(RwV3d *);
    normalsDest = (RwV3d **) RwMalloc(bytes);
    memset(normalsDest, 0, bytes);

    bytes = source->numMorphTargets * sizeof(RwV3d *);
    posSrc = (RwV3d **) RwMalloc(bytes);
    memset(posSrc, 0, bytes);

    bytes = source->numMorphTargets * sizeof(RwV3d *);
    posDest = (RwV3d **) RwMalloc(bytes);
    memset(posDest, 0, bytes);

    bytes = 3 * source->numTriangles * sizeof(SortVert);
    sortVerts = (SortVert *) RwMalloc(bytes);
    memset(sortVerts, 0, bytes);

    if ((((flags & rpGEOMETRYNORMALS) == rpGEOMETRYNORMALS) &&
         ((normalsSrc == NULL) || (normalsDest == NULL))) ||
        (posSrc == NULL) || (posDest == NULL) || (sortVerts == NULL))
    {
        if (sortVerts != NULL)
            RwFree(sortVerts);
        if (posDest != NULL)
            RwFree(posDest);
        if (posSrc != NULL)
            RwFree(posSrc);
        if (normalsDest != NULL)
            RwFree(normalsDest);
        if (normalsSrc != NULL)
            RwFree(normalsSrc);
        RWRETURN((RpGeometry *) NULL);
    }

    /* Set up the sortVerts */
    currentIndex = 0;
    for (i = 0; i < source->numTriangles; i++)
    {
        RwInt16             matIndex = (source->triangles[i]).matIndex;
        RwUInt32            j;

        for (j = 0; j < 3; j++)
        {
            sortVerts[currentIndex].matIndex = matIndex;
            sortVerts[currentIndex].origIndex =
                (source->triangles[i]).vertIndex[j];
            sortVerts[currentIndex].faceIndex =
                ((RwUInt32) i) | (j << 30);
            currentIndex++;
        }
    }

    /* Sort the sortVerts by material and then index (so sortVerts coming
     * * from the same initial vertex are grouped together (they're created
     * * by the triangles that share this vertex) and verts are sorted on
     * * index within materials) */
    qsort(sortVerts, 3 * source->numTriangles, sizeof(SortVert),
          SortVertsByMaterialCB);

    /* Find out how many unique vertices there are (verts having been
     * duplicated at material boundaries) so we can allocate the new
     * geometry */
    currentIndex = -1;
    for (i = 0; i < 3 * source->numTriangles; i++)
    {
        SortVert           *curSortVert = &(sortVerts[i]);

        if ((i == 0) ||
            (SortVertsByMaterialCB
             ((void *) (curSortVert - 1), (void *) curSortVert) != 0))
        {
            /* We've found a new unique vertex */
            currentIndex++;
        }
    }
    numNewVerts = currentIndex + 1;

    bytes = (RwUInt32) (numNewVerts * sizeof(RwUInt16));
    vertexMap = (RwUInt16 *) RwMalloc(bytes);
    memset(vertexMap, 0, bytes);

    newGeom =
        RpGeometryLock(RpGeometryCreate(numNewVerts,
                                        source->numTriangles,
                                        flags), rpGEOMETRYLOCKALL);
    if ((vertexMap == NULL) || (newGeom == NULL))
    {
        RwFree(sortVerts);
        RwFree(posDest);
        RwFree(posSrc);
        RwFree(posDest);
        RwFree(posSrc);
        if (vertexMap != NULL)
            RwFree(vertexMap);
        if (newGeom != NULL)
            RpGeometryDestroy(newGeom);

        RWRETURN((RpGeometry *) NULL);
    }

    /* Map new triangle faces to new vertices and generate a vertex map
     * * to map new to old (to get at the original data when constructing
     * * the new geometry) */
    currentIndex = -1;
    for (i = 0; i < 3 * source->numTriangles; i++)
    {
        RpTriangle         *triangle;
        SortVert           *curSortVert;
        RwUInt32            faceIndex, triVert;

        curSortVert = &(sortVerts[i]);

        /* The top 2 bits of sortVert->faceIndex contain (0, 1, 2), which
         * is the index into triangle->vertIndex[] */
        faceIndex = curSortVert->faceIndex;
        triVert = faceIndex & (3 << 30);
        faceIndex = faceIndex & ~triVert;
        triVert >>= 30;

        if ((i == 0) ||
            (SortVertsByMaterialCB
             ((void *) (curSortVert - 1), (void *) curSortVert) != 0))
        {
            /* We've found a new unique vertex */
            currentIndex++;
        }
        triangle = &(newGeom->triangles[faceIndex]);
        /* Remap the triangle to the new vertices */
        triangle->vertIndex[triVert] = (RwUInt16) currentIndex;
        triangle->matIndex = source->triangles[faceIndex].matIndex;
        vertexMap[currentIndex] = curSortVert->origIndex;
    }
    RwFree(sortVerts);
    sortVerts = (SortVert *) NULL;

    for (i = 0; i < (source->numMorphTargets - 1); i++)
    {
        RpGeometryAddMorphTarget(newGeom);
    }
    if (newGeom->numMorphTargets != source->numMorphTargets)
    {
        RpGeometryDestroy(newGeom);

        RwFree(posDest);
        RwFree(posSrc);
        RwFree(posDest);
        RwFree(posSrc);
        RwFree(vertexMap);

        RWRETURN((RpGeometry *) NULL);
    }

    for (i = 0; i < source->numMorphTargets; i++)
    {
        posSrc[i] =
            RpMorphTargetGetVertices(RpGeometryGetMorphTarget
                                     (source, i));
        posDest[i] =
            RpMorphTargetGetVertices(RpGeometryGetMorphTarget
                                     (newGeom, i));
    }
    if ((flags & rpGEOMETRYNORMALS) == rpGEOMETRYNORMALS)
    {
        normals = TRUE;
        for (i = 0; i < source->numMorphTargets; i++)
        {
            normalsSrc[i] =
                RpMorphTargetGetVertexNormals
                (RpGeometryGetMorphTarget(source, i));
            normalsDest[i] =
                RpMorphTargetGetVertexNormals
                (RpGeometryGetMorphTarget(newGeom, i));
        }
    }
    else
    {
        normals = FALSE;
    }
    if ((flags & rpGEOMETRYPRELIT) == rpGEOMETRYPRELIT)
    {
        preLit = TRUE;
        preLitSrc = RpGeometryGetPreLightColors(source),
            preLitDest = RpGeometryGetPreLightColors(newGeom);
    }
    else
    {
        preLit = FALSE;
    }
    if ((flags & rpGEOMETRYTEXTURED) == rpGEOMETRYTEXTURED)
    {
        textured = TRUE;
        uvSrc =
            RpGeometryGetVertexTexCoords(source,
                                         rwTEXTURECOORDINATEINDEX0),
            uvDest =
            RpGeometryGetVertexTexCoords(newGeom,
                                         rwTEXTURECOORDINATEINDEX0);
    }
    else
    {
        textured = FALSE;
    }

    /* Copy data across using the remapping array */
    for (i = 0; i < numNewVerts; i++)
    {
        RwUInt32            origVertex = vertexMap[i];
        RwInt32             j;

        /* Copy data common to all keyframes */
        if (preLit)
        {
            preLitDest[i] = preLitSrc[origVertex];
        }
        if (textured)
        {
            uvDest[i] = uvSrc[origVertex];
        }
        for (j = 0; j < source->numMorphTargets; j++)
        {
            /* Copy data per morphtarget */
            posDest[j][i] = posSrc[j][origVertex];
            if (normals)
            {
                normalsDest[j][i] = normalsSrc[j][origVertex];
            }
        }
    }

    /* Calculate bounding spheres for newGeom's morphtarget(s) */
    for (i = 0; i < newGeom->numMorphTargets; i++)
    {
        RpMorphTarget      *curTarget =
            RpGeometryGetMorphTarget(newGeom, i);
        RwSphere            sphere;

        RpMorphTargetCalcBoundingSphere(curTarget, &sphere);
        RpMorphTargetSetBoundingSphere(curTarget, &sphere);
    }

    RwFree(posDest);
    RwFree(posSrc);
    RwFree(normalsDest);
    RwFree(normalsSrc);

    if (rpMaterialListCopy
        (&(newGeom->matList), &(source->matList)) == NULL)
    {
        RwFree(vertexMap);
        RpGeometryDestroy(newGeom);
        RWRETURN((RpGeometry *) NULL);
    }

    /* materials Refcounts */
    {
        RwInt32             i;
        RwInt16             matIndex;

        for (i = 0; i < newGeom->numTriangles; i++)
        {
            matIndex = (newGeom->triangles)[i].matIndex;
            RWASSERT(matIndex < newGeom->matList.numMaterials);
            RpMaterialAddRef(_rpMaterialListGetMaterial
                             (&newGeom->matList, matIndex));
        }
    }

    *vertexMapPtr = vertexMap;

    if (RpGeometryUnlock(newGeom) != NULL)
    {
        RWRETURN(newGeom);
    }
    else
    {
        /* So near and yet... */
        RpGeometryDestroy(newGeom);
        RWRETURN((RpGeometry *) NULL);
    }
}

/****************************************************************************
SkinSort

 Function to sort skin extension data given a vertex mapping which was
 used to sort the geometry

 Inputs :   RpSkin *      A pointer to the skin to sort
            RwUInt16 *    A pointer to the vertex mapping info
            RpGeometry *  A pointer to the sorted geometry

 Outputs:   RpSkin *      Pointer to the newly sorted skin data
 */

static RpSkin      *
SkinSort(RpSkin * pSkin, RwUInt16 * vertexMap, RpGeometry * geom)
{
    RpSkin             *pNewSkin;
    RwUInt32            bytes;

    RWFUNCTION(RWSTRING("SkinSort"));
    RWASSERT(pSkin);
    RWASSERT(vertexMap);
    RWASSERT(geom);

    pNewSkin = (RpSkin *) RwFreeListAlloc(RpSkinAtomicGlobals.SkinFreeList);
    memset(pNewSkin, 0, sizeof(RpSkin));

    pNewSkin->numBones = pSkin->numBones;
    pNewSkin->pGeometry = geom;
    pNewSkin->pPlatformData = NULL;
    pNewSkin->pCurrentSkeleton = (RpSkinSkeleton *) NULL;
    pNewSkin->pCurrentHierarchy = (RpHAnimHierarchy *) NULL;

    /* Allocate an array for the bone data */
    bytes = pNewSkin->numBones * sizeof(RpSkinBoneInfo) + 15;
    pNewSkin->pBoneInfoUnaligned = RwMalloc(bytes);
    memset(pNewSkin->pBoneInfoUnaligned, 0, bytes);

    pNewSkin->pBoneInfo =
        (RpSkinBoneInfo *) ROUNDUP16(pNewSkin->pBoneInfoUnaligned);

    memset(pNewSkin->pBoneInfo, 0,
           pNewSkin->numBones * sizeof(RpSkinBoneInfo));

    /* Now we need to fill in the bone infos */

    pNewSkin->totalVertices = RpGeometryGetNumVertices(geom);

    {
        RpSkinBoneInfo     *pBoneInfo;
        RpSkinBoneInfo     *pOldBoneInfo;
        RwInt32             i;

        pBoneInfo = pNewSkin->pBoneInfo;
        pOldBoneInfo = pSkin->pBoneInfo;

        for (i = 0; i < pNewSkin->numBones; i++)
        {
            pBoneInfo->boneIndex = pOldBoneInfo->boneIndex;
            pBoneInfo->pFrame = (RwFrame *) NULL;
            pBoneInfo->boneTag = pOldBoneInfo->boneTag;
            pBoneInfo->flags = pOldBoneInfo->flags;
            pBoneInfo->boneToSkinMat = pOldBoneInfo->boneToSkinMat;
            pBoneInfo++;
            pOldBoneInfo++;
        }

        bytes = pNewSkin->totalVertices * sizeof(RwUInt32);
        pNewSkin->pMatrixIndexMap = (RwUInt32 *) RwMalloc(bytes);
        memset(pNewSkin->pMatrixIndexMap, 0, bytes);

        bytes = pNewSkin->totalVertices * sizeof(RwMatrixWeights);
        pNewSkin->pMatrixWeightsMap =
            (RwMatrixWeights *) RwMalloc(bytes);
        memset(pNewSkin->pMatrixWeightsMap, 0, bytes);

        for (i = 0; i < pNewSkin->totalVertices; i++)
        {
            pNewSkin->pMatrixIndexMap[i] =
                pSkin->pMatrixIndexMap[vertexMap[i]];
            pNewSkin->pMatrixWeightsMap[i] =
                pSkin->pMatrixWeightsMap[vertexMap[i]];
        }
    }

    RWRETURN(pNewSkin);
}

/****************************************************************************
SkinAtomicSort

 Function to sort the geometry and skinning data to support PowerPipe
 requirements. This function creates a new geometry leaving the original
 unsorted geometry (ref counts allowing)

 Inputs :   RpAtomic *      A pointer to an atomic

 Outputs:   RpAtomic *      Pointer to the atomic with sorted data
 */

static RpAtomic    *
SkinAtomicSort(RpAtomic * pAtomic, RpSkin * pSkin)
{
    RwUInt16           *vertexMapPtr = (RwUInt16 *) NULL;
    RpGeometry         *pOrigGeom, *pNewGeom;
    RpSkin             *pNewSkin;

    RWFUNCTION(RWSTRING("SkinAtomicSort"));
    RWASSERT(pAtomic);

    pOrigGeom = RpAtomicGetGeometry(pAtomic);

    pNewGeom = SkinGeometrySortByMaterial(pOrigGeom, &vertexMapPtr);

    /* Destroy any old skin which references any old geometry */
    if (*RPSKINATOMICGETDATA(pAtomic))
    {
        RpSkinDestroy(*RPSKINATOMICGETDATA(pAtomic));
    }

    /* Set new geometry (derefs any old geometry) */
    RpAtomicSetGeometry(pAtomic, pNewGeom, 0);

    /* Remove our reference - owned exclusively by the atomic */
    RpGeometryDestroy(pNewGeom);

    /* Create and set the new sorted skin */
    pNewSkin = SkinSort(pSkin, vertexMapPtr, pNewGeom);
    *RPSKINATOMICGETDATA(pAtomic) = pNewSkin;

    /* Cleanup */
    RwFree(vertexMapPtr);

    RWRETURN(pAtomic);
}

/****************************************************************************
SkinFindFirstAtomicCallback

 Callback to find the first atomic in a skin clump.

 Inputs :   RpAtomic *      A pointer to an atomic
            void *          A pointer to a skin we're generating

 Outputs:   RpAtomic *      Always NULL
 */

static RpAtomic    *
SkinFindFirstAtomicCallback(RpAtomic * pAtomic, void *pData)
{
    RpAtomic          **ppAtomic = (RpAtomic **) pData;

    RWFUNCTION(RWSTRING("SkinFindFirstAtomicCallback"));
    RWASSERT(pAtomic);
    RWASSERT(pData);

    *ppAtomic = pAtomic;

    RWRETURN((RpAtomic *) NULL);

}

/****************************************************************************
_rpSkinFindFirstAtomicSkinCallback

 Callback to find the first atomic's skin in a skin clump.

 Inputs :   RpAtomic *      A pointer to an atomic
            void *          A pointer to a pointer to a skin to fill in

 Outputs:   RpAtomic *      Always NULL
 */

RpAtomic           *
_rpSkinFindFirstAtomicSkinCallback(RpAtomic * pAtomic, void *pData)
{
    RpSkin            **ppSkin = (RpSkin **) pData;

    RWFUNCTION(RWSTRING("_rpSkinFindFirstAtomicSkinCallback"));
    RWASSERT(pAtomic);
    RWASSERT(pData);

    *ppSkin = *RPSKINATOMICGETDATA(pAtomic);

    RWRETURN((RpAtomic *) NULL);
}

/**
 * \ingroup rpskin310
 * \ref RpSkinCreateAtomicFromBoneClump
 * creates a skinned atomic from an rpbone-style skin-and-bone clump.
 *
 * \param pClump  A pointer to the clump to set up
 *
 * \return  pointer to the newly created atomic on success
 *
 * \see RpSkinExtractAnimFromClumpSequence
 */
RpAtomic           *
RpSkinCreateAtomicFromBoneClump(RpClump * pClump)
{
    RpSkin             *pSkin;
    RpSkin              tempSkin;
    RwV3d              *pVertices;
    RwV3d              *pNormals;
    RpAtomic           *pAtomic;
    RpAtomic           *pNewAtomic;
    RwUInt32            bytes;

    RWAPIFUNCTION(RWSTRING("RpSkinCreateAtomicFromBoneClump"));
    RWASSERT(pClump);

    /* Initialize the skbone state block */
    _rpSkBoneStateConstructor();

    /* Set up a temporary skin for us to fill in 
     * until we know how big the final data needs to be */

    tempSkin.numBones = 0;
    tempSkin.pGeometry = (RpGeometry *) NULL;
    tempSkin.pBoneInfo = (RpSkinBoneInfo *) NULL;
    tempSkin.pPlatformData = NULL;

    RpClumpForAllAtomics(pClump, SkinFindFirstAtomicCallback,
                         (void *) &pAtomic);

    /* Count the number of bones in the model */

    RwFrameForAllChildren(RpClumpGetFrame(pClump),
                          SkinGenerateCountBonesCallback,
                          (void *) &tempSkin);

    /* Allocate an array for the bone data */
    bytes = tempSkin.numBones * sizeof(RpSkinBoneInfo) + 15;
    tempSkin.pBoneInfoUnaligned = RwMalloc(bytes);
    memset(tempSkin.pBoneInfoUnaligned, 0, bytes);

    tempSkin.pBoneInfo =
        (RpSkinBoneInfo *) ROUNDUP16(tempSkin.pBoneInfoUnaligned);

    memset(tempSkin.pBoneInfo, 0,
           tempSkin.numBones * sizeof(RpSkinBoneInfo));

    /* Now we need to fill in the bone infos */

    SkBone->CurrentLevel = 0;
    SkBone->LastLevel = 0;
    SkBone->pCurrentBone = tempSkin.pBoneInfo;

    tempSkin.pGeometry = RpAtomicGetGeometry(pAtomic);
    tempSkin.totalVertices =
        RpGeometryGetNumVertices(tempSkin.pGeometry);

    RwFrameForAllChildren(RpClumpGetFrame(pClump),
                          SkinGenerateHierarchyCallback,
                          (void *) &tempSkin);

    {
        rpBoneList         *boneList;
        RpSkinBoneInfo     *pBoneInfo;
        RwInt32             i;
        rpBoneGeomData     *geomData;

        geomData = *RPBONEGEOMGETDATA(tempSkin.pGeometry);

        boneList = geomData->boneList;
        pVertices = geomData->vertices;
        pNormals = geomData->normals;

        pBoneInfo = tempSkin.pBoneInfo;

        for (i = 0; i < tempSkin.numBones; i++)
        {
            pBoneInfo->boneIndex = i;
            pBoneInfo->pFrame = (RwFrame *) NULL;
            pBoneInfo++;
        }

        bytes = tempSkin.totalVertices * sizeof(RwUInt32);
        tempSkin.pMatrixIndexMap = (RwUInt32 *) RwMalloc(bytes);
        memset(tempSkin.pMatrixIndexMap, 0, bytes);

        bytes = tempSkin.totalVertices * sizeof(RwMatrixWeights);
        tempSkin.pMatrixWeightsMap =
            (RwMatrixWeights *) RwMalloc(bytes);
        memset(tempSkin.pMatrixWeightsMap, 0, bytes);

        /* Initialise all matrices to identity */

        for (pBoneInfo = tempSkin.pBoneInfo;
             pBoneInfo->boneTag != boneList->boneTag; pBoneInfo++)
        {
            pBoneInfo->boneToSkinMat.right.y =
                pBoneInfo->boneToSkinMat.right.z =
                pBoneInfo->boneToSkinMat.up.x =
                pBoneInfo->boneToSkinMat.up.z =
                pBoneInfo->boneToSkinMat.at.x =
                pBoneInfo->boneToSkinMat.at.y =
                pBoneInfo->boneToSkinMat.pos.x =
                pBoneInfo->boneToSkinMat.pos.y =
                pBoneInfo->boneToSkinMat.pos.z = (RwReal) 0.0;

#if (0)
            pBoneInfo->boneToSkinMat.rw =
                pBoneInfo->boneToSkinMat.uw =
                pBoneInfo->boneToSkinMat.aw =
#endif /* (0) */
                pBoneInfo->boneToSkinMat.right.x =
                pBoneInfo->boneToSkinMat.up.y =
                pBoneInfo->boneToSkinMat.at.z = (RwReal) 1.0;

#if (0)
            pBoneInfo->boneToSkinMat.pw = (RwReal) 1.0;
#endif /* (0) */
        }

        while (boneList->length)
        {
            /* Find the correct boneInfo for this bone */
            RwMatrix           *source = &boneList->bone->skinToBone;
            RwMatrix           *dest;

            /* RWASSERT(rwMatrixValidFlags(source, _EPSILON)); */

            for (pBoneInfo = tempSkin.pBoneInfo;
                 pBoneInfo->boneTag != boneList->boneTag; pBoneInfo++) ;

            dest = &pBoneInfo->boneToSkinMat;

            dest->right.x = source->right.x;
            dest->right.y = source->right.y;
            dest->right.z = source->right.z;

            dest->up.x = source->up.x;
            dest->up.y = source->up.y;
            dest->up.z = source->up.z;

            dest->at.x = source->at.x;
            dest->at.y = source->at.y;
            dest->at.z = source->at.z;

            dest->pos.x = source->pos.x;
            dest->pos.y = source->pos.y;
            dest->pos.z = source->pos.z;

#if (0)
            dest->rw = 0.0f;
            dest->uw = 0.0f;
            dest->aw = 0.0f;
            dest->pw = 1.0f;
#endif /* (0) */

            /* RWASSERT(rwMatrixValidFlags(dest, _EPSILON)); */

            /* Generate vertex weights and indices */

#if (0)
            RWMESSAGE((RWSTRING
                       ("Bone start %d, length %d, index %d, tag %d\n"),
                       (int) (boneList->start),
                       (int) (boneList->length),
                       (int) (boneList->boneTag),
                       (int) (pBoneInfo->boneIndex)));
#endif /* (0) */

            for (i = boneList->start;
                 i < (RwInt32) (boneList->start + boneList->length);
                 i++)
            {
                tempSkin.pMatrixIndexMap[i] =
                    0xFFFFFF00 | (pBoneInfo->boneIndex);
                tempSkin.pMatrixWeightsMap[i].w0 = 1.0f;
                tempSkin.pMatrixWeightsMap[i].w1 = 0.0f;
                tempSkin.pMatrixWeightsMap[i].w2 = 0.0f;
                tempSkin.pMatrixWeightsMap[i].w3 = 0.0f;
            }

            boneList++;
        }

    }

    /* Allocate a structure for the Skin */

    pSkin = (RpSkin *) RwFreeListAlloc(RpSkinAtomicGlobals.SkinFreeList);
    memset(pSkin, 0, sizeof(RpSkin));

    *pSkin = tempSkin;

    *RPSKINATOMICGETDATA(pAtomic) = pSkin;

    /* Create the new atomic */

    pNewAtomic = RpAtomicClone(pAtomic);

    SkinAtomicSort(pNewAtomic, pSkin);

    _rpSkinMBInitAtomic(pNewAtomic);

    /* destroy the skbone state block */
    _rpSkBoneStateDestructor();

    RWRETURN(pNewAtomic);
}

/****************************************************************************
 SkinMakeTransKey

 Makes a new translation key frame for an rpanim sequence.

 Inputs :   RwV3d *         A pointer to the newly interpolated 
                            translation data
            RpAnimSequnce * A pointer to the animation sequence
            RwReal          The time for the new key frame

 Outputs:   None
 */

static void
SkinMakeTransKey(RwV3d * pV, RpAnimSequence * pAnimSeq, RwReal time)
{
    RwInt32             nInt;
    RwReal              rITime = (RwReal) 0.0;
    RwReal              alpha;
    RwReal              beta;
    RwV3d              *pKey1;
    RwV3d              *pKey2;

    RWFUNCTION(RWSTRING("SkinMakeTransKey"));
    RWASSERT(pV);
    RWASSERT(pAnimSeq);

    /* Find the keyframes to interpolate between */
    nInt = 0;

    for (nInt = 0; nInt < pAnimSeq->numInterpolators; nInt++)
    {
        rITime += pAnimSeq->interps[nInt].time;
        if (rITime > time)
        {
            /* Found it */
            break;
        }
    }

    if (nInt == pAnimSeq->numInterpolators)
    {
        /* Just need the last key */
        *pV = ((RwV3d *) pAnimSeq->keys)[pAnimSeq->numKeys - 1];
        RWRETURNVOID();
    }

    /* nInt is the interpolator we're after... */

    time -= (rITime - pAnimSeq->interps[nInt].time);
    beta = time / pAnimSeq->interps[nInt].time;
    alpha = (RwReal) 1.0 - beta;

    pKey1 =
        &((RwV3d *) pAnimSeq->keys)[pAnimSeq->
                                    interps[nInt].startKeyFrame];
    pKey2 =
        &((RwV3d *) pAnimSeq->keys)[pAnimSeq->
                                    interps[nInt].endKeyFrame];

    pV->x = (alpha * pKey1->x) + (beta * pKey2->x);
    pV->y = (alpha * pKey1->y) + (beta * pKey2->y);
    pV->z = (alpha * pKey1->z) + (beta * pKey2->z);

    RWRETURNVOID();
}

/****************************************************************************
 SkinMakeTransKey

 Makes a new rotation key frame for an rpanim sequence.

 Inputs :   RtQuat *        A pointer to the newly interpolated rotation data
            RpAnimSequnce * A pointer to the animation sequence
            RwReal          The time for the new key frame

 Outputs:   None
 */

static void
SkinMakeRotKey(RtQuat * pQuat, RpAnimSequence * pAnimSeq, RwReal time)
{
    RpSkinFrame         f1;
    RpSkinFrame         f2;
    RpSkinFrame         fr;
    RwInt32             nInt;
    RwInt32             startKeyFrame;
    RwInt32             endKeyFrame;
    RwReal              rITime = (RwReal) 0.0;

    RWFUNCTION(RWSTRING("SkinMakeRotKey"));
    RWASSERT(pQuat);
    RWASSERT(pAnimSeq);

    /* Find the keyframes to interpolate between */
    nInt = 0;

    for (nInt = 0; nInt < pAnimSeq->numInterpolators; nInt++)
    {
        rITime += pAnimSeq->interps[nInt].time;
        if (rITime > time)
        {
            /* Found it */
            break;
        }
    }

    if (nInt == pAnimSeq->numInterpolators)
    {
        /* Just need the last key */
        *pQuat = ((RtQuat *) pAnimSeq->keys)[pAnimSeq->numKeys - 1];
        RWRETURNVOID();
    }

    /* nInt is the interpolator we're after - let's use
     * the RpSkinFrame interpolation
     * routine, as we don't care about speed right now */

    startKeyFrame = pAnimSeq->interps[nInt].startKeyFrame;
    f1.q.imag.x = ((RtQuat *) pAnimSeq->keys)[startKeyFrame].imag.x;
    f1.q.imag.y = ((RtQuat *) pAnimSeq->keys)[startKeyFrame].imag.y;
    f1.q.imag.z = ((RtQuat *) pAnimSeq->keys)[startKeyFrame].imag.z;
    f1.q.real = ((RtQuat *) pAnimSeq->keys)[startKeyFrame].real;
    f1.time = rITime - pAnimSeq->interps[nInt].time;

    endKeyFrame = pAnimSeq->interps[nInt].endKeyFrame;
    f2.q.imag.x = ((RtQuat *) pAnimSeq->keys)[endKeyFrame].imag.x;
    f2.q.imag.y = ((RtQuat *) pAnimSeq->keys)[endKeyFrame].imag.y;
    f2.q.imag.z = ((RtQuat *) pAnimSeq->keys)[endKeyFrame].imag.z;
    f2.q.real = ((RtQuat *) pAnimSeq->keys)[endKeyFrame].real;
    f2.time = rITime;

    RpSkinFrameInterpolate(&fr, &f1, &f2, time);

    pQuat->imag.x = fr.q.imag.x;
    pQuat->imag.y = fr.q.imag.y;
    pQuat->imag.z = fr.q.imag.z;
    pQuat->real = fr.q.real;

    RWRETURNVOID();
}

/****************************************************************************
 _rpSkinExtractSequence

 Retrieve an anim sequence for a frame, making sure that it has the same number
 of rotation and translation key frames and that they all match up in time

 Inputs :   RwFrame *       A pointer to the frame we're interested in
            void *          A pointer to the skin this animation 
                            will play back on

 Outputs:   None
 */

RwFrame            *
_rpSkinExtractSequence(RwFrame * pFrame, void *pData)
{
    RpSkin             *pSkin = (RpSkin *) pData;
    RpAnimSequence     *pAnimSeq;
    RpAnimSequence     *pRotateSeq;
    RpAnimSequence     *pTranslateSeq;
    RwInt32             i;

    RWFUNCTION(RWSTRING("_rpSkinExtractSequence"));
    RWASSERT(pFrame);
    RWASSERT(pData);

    SkBone->pDefaultFrames[SkBone->ExtractSequenceFrameNumber] = pFrame;
    SkBone->pTranslateSequences[SkBone->ExtractSequenceFrameNumber] =
        RpAnimFrameGetTranslationSequence(pFrame,
                                          SkBone->pExtractSequenceName);
    SkBone->pRotateSequences[SkBone->ExtractSequenceFrameNumber] =
        RpAnimFrameGetRotationSequence(pFrame,
                                       SkBone->pExtractSequenceName);

    /* Make sure the two sequences have the same number of keyframes */

    pRotateSeq =
        SkBone->pRotateSequences[SkBone->ExtractSequenceFrameNumber];

    if (!pRotateSeq)
    {
        pTranslateSeq =
            SkBone->
            pTranslateSequences[SkBone->ExtractSequenceFrameNumber];

        if (pTranslateSeq)
        {
            /* No rotations, 
             * assume everything to be identity and fill in 
             * from the translation keys */
            RtQuat              rotKey = { {0.0f, 0.0f, 0.0f}
            , 1.0f
            };
            RpAnimSequence    **ptr;
            RwInt32             idx;

            pAnimSeq =
                RpAnimSequenceCreate(SkBone->pExtractSequenceName,
                                     rpROTATE, pTranslateSeq->numKeys,
                                     pTranslateSeq->numInterpolators);

            for (i = 0; i < pTranslateSeq->numKeys; i++)
            {
                RpAnimSequenceSetRotateKey(pAnimSeq, i, &rotKey);
            }

            for (i = 0; i < pTranslateSeq->numInterpolators; i++)
            {
                RpAnimSequenceSetInterpolator(pAnimSeq, i, i, i + 1,
                                              pTranslateSeq->
                                              interps[i].time);
            }
            ptr = SkBone->pRotateSequences;
            idx = SkBone->ExtractSequenceFrameNumber;

            ptr[idx] = pAnimSeq;
            RpAnimFrameAddSequence(pFrame, ptr[idx]);
        }
        else
        {
            /* Haven't got any translations or rotations here 
             * - let's just make them up then */
            RtQuat              rotKey = { {0.0f, 0.0f, 0.0f}
            , 1.0f
            };
            RpAnimSequence    **ptr;
            RwInt32             idx;

            pAnimSeq =
                RpAnimSequenceCreate(SkBone->pExtractSequenceName,
                                     rpROTATE, 2, 1);
            RpAnimSequenceSetRotateKey(pAnimSeq, 0, &rotKey);
            RpAnimSequenceSetRotateKey(pAnimSeq, 1, &rotKey);
            RpAnimSequenceSetInterpolator(pAnimSeq, 0, 0, 1,
                                          (RwReal) 0.00001);

            ptr = SkBone->pRotateSequences;
            idx = SkBone->ExtractSequenceFrameNumber;

            ptr[idx] = pAnimSeq;
            RpAnimFrameAddSequence(pFrame, ptr[idx]);

            pAnimSeq =
                RpAnimSequenceCreate(SkBone->pExtractSequenceName,
                                     rpTRANSLATE, 2, 1);
            RpAnimSequenceSetTranslateKey(pAnimSeq, 0,
                                          &RwFrameGetMatrix
                                          (pFrame)->pos);
            RpAnimSequenceSetTranslateKey(pAnimSeq, 1,
                                          &RwFrameGetMatrix
                                          (pFrame)->pos);
            RpAnimSequenceSetInterpolator(pAnimSeq, 0, 0, 1,
                                          (RwReal) 0.00001);

            ptr = SkBone->pTranslateSequences;
            idx = SkBone->ExtractSequenceFrameNumber;
            ptr[idx] = pAnimSeq;

            RpAnimFrameAddSequence(pFrame, ptr[idx]);
        }
    }
    else
    {

        pTranslateSeq =
            SkBone->
            pTranslateSequences[SkBone->ExtractSequenceFrameNumber];

        if (!pTranslateSeq)
        {
            /* No translations, 
             * get them from the frame and fill in 
             * from the rotation keys */
            RpAnimSequence    **ptr;
            RwInt32             idx;

            pAnimSeq =
                RpAnimSequenceCreate(SkBone->pExtractSequenceName,
                                     rpTRANSLATE,
                                     pRotateSeq->numKeys,
                                     pRotateSeq->numInterpolators);

            for (i = 0; i < pRotateSeq->numKeys; i++)
            {
                RpAnimSequenceSetTranslateKey(pAnimSeq, i,
                                              &RwFrameGetMatrix
                                              (pFrame)->pos);
            }

            for (i = 0; i < pRotateSeq->numInterpolators; i++)
            {
                RpAnimSequenceSetInterpolator(pAnimSeq, i, i, i + 1,
                                              pRotateSeq->
                                              interps[i].time);
            }

            ptr = SkBone->pTranslateSequences;
            idx = SkBone->ExtractSequenceFrameNumber;
            ptr[idx] = pAnimSeq;
            RpAnimFrameAddSequence(pFrame, ptr[idx]);
        }
        else
        {
        }
    }

    /* Make sure the two sequences match up in time... */
    {
        RwInt32             currentRotateInterp = 0;
        RwInt32             currentRotateKey = 0;
        RwInt32             currentTranslateInterp = 0;
        RwInt32             currentTranslateKey = 0;
        RtQuat             *pRotateKeys;
        RwInt32             numRotateKeys = 0;
        RwV3d              *pTranslateKeys;
        RwInt32             numTranslateKeys = 0;
        rpAnimInterpolator *pInterpolators;
        RwInt32             numInterpolators = 0;
        RwInt32             numTempKeys;
        RwReal              nextRotation = (RwReal) 0.0;
        RwReal              nextTranslation = (RwReal) 0.0;
        RwReal              lastTime = (RwReal) 0.0;
        RpAnimSequence    **ptr;
        RwInt32             idx;
        RwUInt32            bytes;

        /* Allocate some temporary lists of keys 
         * - we'll generate new sequences in here */

        if (SkBone->
            pRotateSequences[SkBone->
                             ExtractSequenceFrameNumber]->numKeys >
            SkBone->
            pTranslateSequences
            [SkBone->ExtractSequenceFrameNumber]->numKeys)
        {
            numTempKeys =
                SkBone->
                pRotateSequences
                [SkBone->ExtractSequenceFrameNumber]->numKeys * 2;
        }
        else
        {
            numTempKeys =
                SkBone->pTranslateSequences
                [SkBone->ExtractSequenceFrameNumber]->numKeys * 2;
        }

        bytes = numTempKeys * sizeof(RtQuat);
        pRotateKeys = (RtQuat *) RwMalloc(bytes);
        memset(pRotateKeys, 0, bytes);

        bytes = numTempKeys * sizeof(RwV3d);
        pTranslateKeys = (RwV3d *) RwMalloc(bytes);
        memset(pTranslateKeys, 0, bytes);

        bytes = numTempKeys * sizeof(rpAnimInterpolator);
        pInterpolators = (rpAnimInterpolator *) RwMalloc(bytes);
        memset(pInterpolators, 0, bytes);

        /* Copy first key frames */

        pRotateSeq =
            SkBone->pRotateSequences[SkBone->
                                     ExtractSequenceFrameNumber];
        pTranslateSeq =
            SkBone->pTranslateSequences[SkBone->
                                        ExtractSequenceFrameNumber];
        pRotateKeys[numRotateKeys++] =
            ((RtQuat *) (pRotateSeq->keys))[0];
        pTranslateKeys[numTranslateKeys++] =
            ((RwV3d *) (pTranslateSeq->keys))[0];

        /* Get next keys */
        RWASSERT(0 <= currentRotateInterp);
        RWASSERT(currentRotateInterp < pRotateSeq->numInterpolators);
        currentRotateKey =
            pRotateSeq->interps[currentRotateInterp].endKeyFrame;
        RWASSERT(0 <= currentRotateKey);

        RWASSERT(0 <= currentTranslateInterp);
        RWASSERT(currentTranslateInterp <
                 pTranslateSeq->numInterpolators);
        currentTranslateKey =
            pTranslateSeq->interps[currentTranslateInterp].endKeyFrame;
        RWASSERT(0 <= currentTranslateKey);

        /* Get times of next keys */
        RWASSERT(0 <= currentRotateInterp);
        nextRotation += pRotateSeq->interps[currentRotateInterp].time;

        RWASSERT(0 <= currentRotateInterp);
        nextTranslation +=
            pTranslateSeq->interps[currentRotateInterp].time;

        /* While there are interpolators that we haven't looked at... */
        while ((currentRotateInterp <
                SkBone->
                pRotateSequences
                [SkBone->ExtractSequenceFrameNumber]->numInterpolators)
               || (currentTranslateInterp <
                   SkBone->
                   pTranslateSequences
                   [SkBone->ExtractSequenceFrameNumber]->
                   numInterpolators))
        {
            /* See if the next rotation and translation keys match up */
            RWASSERT(0 <= currentRotateInterp);

            if (nextRotation < nextTranslation)
            {
                /* Rotation comes before translation,
                 * so we'll need another translation key to match it */
                SkinMakeTransKey(&pTranslateKeys[numTranslateKeys++],
                                 SkBone->pTranslateSequences
                                 [SkBone->ExtractSequenceFrameNumber],
                                 nextRotation);

                RWASSERT(0 <= currentRotateKey);
                pRotateKeys[numRotateKeys++] =
                    ((RtQuat
                      *) (SkBone->pRotateSequences
                          [SkBone->ExtractSequenceFrameNumber]->keys))
                    [currentRotateKey];

                pInterpolators[numInterpolators].startKeyFrame =
                    numTranslateKeys - 2;
                pInterpolators[numInterpolators].endKeyFrame =
                    numTranslateKeys - 1;
                pInterpolators[numInterpolators++].time =
                    nextRotation - lastTime;
                lastTime = nextRotation;

                currentRotateInterp++;

                if (currentRotateInterp <
                    SkBone->
                    pRotateSequences
                    [SkBone->ExtractSequenceFrameNumber]->
                    numInterpolators)
                {

                    RWASSERT(0 <= currentRotateInterp);
                    RWASSERT(currentRotateInterp <
                             SkBone->
                             pRotateSequences
                             [SkBone->ExtractSequenceFrameNumber]->
                             numInterpolators);
                    currentRotateKey =
                        SkBone->pRotateSequences[SkBone->
                                                 ExtractSequenceFrameNumber]->
                        interps[currentRotateInterp].endKeyFrame;

                    RWASSERT(0 <= currentRotateKey);

                    nextRotation +=
                        SkBone->pRotateSequences
                        [SkBone->ExtractSequenceFrameNumber]->interps
                        [currentRotateInterp].time;

                }
                else
                {
                    nextRotation = nextTranslation;
                }

                continue;
            }

            if (nextTranslation < nextRotation)
            {
                /* Rotation comes after translation,
                 * so we'll need another rotation key to match it */
                SkinMakeRotKey(&pRotateKeys[numRotateKeys++],
                               SkBone->pRotateSequences
                               [SkBone->ExtractSequenceFrameNumber],
                               nextTranslation);

                RWASSERT(0 <= currentTranslateKey);
                pTranslateKeys[numTranslateKeys++] =
                    ((RwV3d
                      *) (SkBone->pTranslateSequences
                          [SkBone->ExtractSequenceFrameNumber]->keys))
                    [currentTranslateKey];

                pInterpolators[numInterpolators].startKeyFrame =
                    numRotateKeys - 2;
                pInterpolators[numInterpolators].endKeyFrame =
                    numRotateKeys - 1;
                pInterpolators[numInterpolators++].time =
                    nextTranslation - lastTime;
                lastTime = nextTranslation;

                currentTranslateInterp++;

                if (currentTranslateInterp <
                    SkBone->pTranslateSequences
                    [SkBone->
                     ExtractSequenceFrameNumber]->numInterpolators)
                {

                    RpAnimSequence    **ptr;
                    RwInt32             idx;

                    RWASSERT(0 <= currentTranslateInterp);
                    RWASSERT(currentTranslateInterp <
                             SkBone->
                             pTranslateSequences
                             [SkBone->ExtractSequenceFrameNumber]->
                             numInterpolators);

                    ptr = SkBone->pTranslateSequences;
                    idx = SkBone->ExtractSequenceFrameNumber;

                    RWASSERT(ptr);

                    currentTranslateKey =
                        ptr[idx]->interps[currentTranslateInterp].
                        endKeyFrame;

                    RWASSERT(0 <= currentTranslateKey);

                    nextTranslation +=
                        SkBone->pTranslateSequences
                        [SkBone->ExtractSequenceFrameNumber]->interps
                        [currentTranslateInterp].time;
                }
                else
                {
                    nextTranslation = nextRotation;
                }

                continue;
            }

            if (nextRotation == nextTranslation)
            {
                /* Rotation and translation at the same time 
                 * - just copy them */
                RWASSERT(0 <= currentTranslateKey);
                pTranslateKeys[numTranslateKeys++] =
                    ((RwV3d
                      *) (SkBone->pTranslateSequences
                          [SkBone->ExtractSequenceFrameNumber]->keys))
                    [currentTranslateKey];

                RWASSERT(0 <= currentRotateKey);
                pRotateKeys[numRotateKeys++] =
                    ((RtQuat
                      *) (SkBone->pRotateSequences
                          [SkBone->ExtractSequenceFrameNumber]->keys))
                    [currentRotateKey];

                pInterpolators[numInterpolators].startKeyFrame =
                    numTranslateKeys - 2;
                pInterpolators[numInterpolators].endKeyFrame =
                    numTranslateKeys - 1;
                pInterpolators[numInterpolators++].time =
                    nextRotation - lastTime;
                lastTime = nextRotation;

                currentRotateInterp++;

                if (currentRotateInterp <
                    SkBone->pRotateSequences
                    [SkBone->
                     ExtractSequenceFrameNumber]->numInterpolators)
                {

                    RWASSERT(0 <= currentRotateInterp);
                    RWASSERT(currentRotateInterp <
                             SkBone->
                             pRotateSequences
                             [SkBone->ExtractSequenceFrameNumber]->
                             numInterpolators);
                    currentRotateKey =
                        SkBone->pRotateSequences[SkBone->
                                                 ExtractSequenceFrameNumber]->
                        interps[currentRotateInterp].endKeyFrame;

                    RWASSERT(0 <= currentRotateKey);

                    nextRotation +=
                        SkBone->pRotateSequences
                        [SkBone->ExtractSequenceFrameNumber]->interps
                        [currentRotateInterp].time;
                }
                else
                {
                    currentTranslateInterp++;

                    if (currentTranslateInterp <
                        SkBone->pTranslateSequences
                        [SkBone->
                         ExtractSequenceFrameNumber]->numInterpolators)
                    {

                        RpAnimSequence    **ptr;
                        RwInt32             idx;

                        RWASSERT(0 <= currentTranslateInterp);
                        RWASSERT(currentTranslateInterp <
                                 SkBone->
                                 pTranslateSequences
                                 [SkBone->ExtractSequenceFrameNumber]->
                                 numInterpolators);

                        ptr = SkBone->pTranslateSequences;
                        idx = SkBone->ExtractSequenceFrameNumber;

                        currentTranslateKey =
                            ptr[idx]->interps[currentTranslateInterp].
                            endKeyFrame;

                        RWASSERT(0 <= currentTranslateKey);

                        nextTranslation +=
                            SkBone->pTranslateSequences
                            [SkBone->ExtractSequenceFrameNumber]->
                            interps[currentTranslateInterp].time;

                        nextRotation = nextTranslation;
                        continue;
                    }
                }

                currentTranslateInterp++;

                if (currentTranslateInterp <
                    SkBone->pTranslateSequences
                    [SkBone->
                     ExtractSequenceFrameNumber]->numInterpolators)
                {
                    RpAnimSequence    **ptr;
                    RwInt32             idx;

                    RWASSERT(0 <= currentTranslateInterp);
                    RWASSERT(currentTranslateInterp <
                             SkBone->
                             pTranslateSequences
                             [SkBone->ExtractSequenceFrameNumber]->
                             numInterpolators);

                    ptr = SkBone->pTranslateSequences;
                    idx = SkBone->ExtractSequenceFrameNumber;

                    currentTranslateKey =
                        ptr[idx]->interps[currentTranslateInterp].
                        endKeyFrame;

                    RWASSERT(0 <= currentTranslateKey);

                    nextTranslation +=
                        SkBone->pTranslateSequences
                        [SkBone->ExtractSequenceFrameNumber]->interps
                        [currentTranslateInterp].time;

                }
                else
                {
                    nextTranslation = nextRotation;
                }
            }

        }

        /* Copy new sequences into place */

        RWASSERT(numTranslateKeys == numRotateKeys);

        pAnimSeq =
            RpAnimSequenceCreate(SkBone->pExtractSequenceName,
                                 rpTRANSLATE, numTranslateKeys,
                                 numInterpolators);

        /* Fill in the new sequence */

        for (i = 0; i < numTranslateKeys; i++)
        {
            RpAnimSequenceSetTranslateKey(pAnimSeq, i,
                                          &pTranslateKeys[i]);
        }

        for (i = 0; i < numInterpolators; i++)
        {
            RpAnimSequenceSetInterpolator(pAnimSeq, i,
                                          pInterpolators
                                          [i].startKeyFrame,
                                          pInterpolators[i].endKeyFrame,
                                          pInterpolators[i].time);
        }

        RpAnimFrameRemoveSequence(pFrame,
                                  SkBone->pTranslateSequences
                                  [SkBone->ExtractSequenceFrameNumber]);
        RpAnimSequenceDestroy(SkBone->pTranslateSequences
                              [SkBone->ExtractSequenceFrameNumber]);

        ptr = SkBone->pTranslateSequences;
        idx = SkBone->ExtractSequenceFrameNumber;

        ptr[idx] = pAnimSeq;
        RpAnimFrameAddSequence(pFrame, ptr[idx]);

        pAnimSeq =
            RpAnimSequenceCreate(SkBone->pExtractSequenceName, rpROTATE,
                                 numRotateKeys, numInterpolators);

        /* Fill in the new sequence */

        for (i = 0; i < numRotateKeys; i++)
        {
            RpAnimSequenceSetRotateKey(pAnimSeq, i, &pRotateKeys[i]);
        }

        for (i = 0; i < numInterpolators; i++)
        {
            RpAnimSequenceSetInterpolator(pAnimSeq, i,
                                          pInterpolators
                                          [i].startKeyFrame,
                                          pInterpolators[i].endKeyFrame,
                                          pInterpolators[i].time);
        }

        RpAnimFrameRemoveSequence(pFrame,
                                  SkBone->pRotateSequences
                                  [SkBone->ExtractSequenceFrameNumber]);
        RpAnimSequenceDestroy(SkBone->pRotateSequences
                              [SkBone->ExtractSequenceFrameNumber]);
        SkBone->pRotateSequences[SkBone->ExtractSequenceFrameNumber] =
            pAnimSeq;
        RpAnimFrameAddSequence(pFrame,
                               SkBone->
                               pRotateSequences
                               [SkBone->ExtractSequenceFrameNumber]);

        RwFree(pRotateKeys);
        RwFree(pTranslateKeys);
        RwFree(pInterpolators);

    }

    SkBone->ExtractSequenceFrameNumber++;

    RwFrameForAllChildren(pFrame, _rpSkinExtractSequence,
                          (void *) pSkin);

    RWRETURN(pFrame);
}

/****************************************************************************
 _rpSkinDestroySequence

 Destroy an anim sequence and remove it from its frame.

 Inputs :   RwFrame *       A pointer to the frame we're interested in
            void *          A pointer to the skin this animation 
                            will play back on

 Outputs:   None
 */

RwFrame            *
_rpSkinDestroySequence(RwFrame * pFrame, void *pData)
{
    RpAnimSequence     *RotSeq;
    RpAnimSequence     *TrnSeq;

    RWFUNCTION(RWSTRING("_rpSkinDestroySequence"));
    RWASSERT(pFrame);

#if (0)
    RWMESSAGE(("SkBone->ExtractSequenceFrameNumber %d",
               (int) SkBone->ExtractSequenceFrameNumber));
#endif /* (0) */

    RotSeq =
        SkBone->pRotateSequences[SkBone->ExtractSequenceFrameNumber];
    TrnSeq =
        SkBone->pTranslateSequences[SkBone->ExtractSequenceFrameNumber];

    RpAnimFrameRemoveSequence(pFrame, TrnSeq);
    RpAnimSequenceDestroy(TrnSeq);

    RpAnimFrameRemoveSequence(pFrame, RotSeq);
    RpAnimSequenceDestroy(RotSeq);

    SkBone->ExtractSequenceFrameNumber++;

    RwFrameForAllChildren(pFrame, _rpSkinDestroySequence,
                          (void *) pData);

    RWRETURN(pFrame);

}

/****************************************************************************
 SkinAnimMakeFrame

 Build an animation from for the given time and bone

 Inputs :   RpSkinFrame *   A pointer to the skin frame we're interested in
            RwInt32         frame index
            RwInt32         key index
            RwReal          time

 Outputs:   None
 */

static void
SkinAnimMakeFrame(RpSkinFrame * pFrame, RwInt32 frame,
                  RwInt32 key, RwReal time)
{
    RwMatrix           *pMatrix;

    RWFUNCTION(RWSTRING("SkinAnimMakeFrame"));
    RWASSERT(pFrame);

    if (SkBone->pRotateSequences[frame])
    {
        pFrame->q.imag.x =
            (((RpRotateKey
               *) SkBone->pRotateSequences[frame]->keys)[key]).imag.x;
        pFrame->q.imag.y =
            (((RpRotateKey
               *) SkBone->pRotateSequences[frame]->keys)[key]).imag.y;
        pFrame->q.imag.z =
            (((RpRotateKey
               *) SkBone->pRotateSequences[frame]->keys)[key]).imag.z;
        pFrame->q.real =
            -(((RpRotateKey *) SkBone->pRotateSequences[frame]->keys)
              [key]).real;
    }
    else
    {
        pFrame->q.imag.x = (RwReal) 0.0;
        pFrame->q.imag.y = (RwReal) 0.0;
        pFrame->q.imag.z = (RwReal) 0.0;
        pFrame->q.real = (RwReal) 1.0;
        pMatrix = RwFrameGetMatrix(SkBone->pDefaultFrames[frame]);

        /* RWASSERT(rwMatrixValidFlags(pMatrix, _EPSILON)); */

        RtQuatConvertFromMatrix(&pFrame->q, pMatrix);
    }

    if (SkBone->pTranslateSequences[frame])
    {
        pFrame->t.x =
            (((RpTranslateKey
               *) SkBone->pTranslateSequences[frame]->keys)[key]).x;
        pFrame->t.y =
            (((RpTranslateKey
               *) SkBone->pTranslateSequences[frame]->keys)[key]).y;
        pFrame->t.z =
            (((RpTranslateKey
               *) SkBone->pTranslateSequences[frame]->keys)[key]).z;
    }
    else
    {
        pMatrix = RwFrameGetMatrix(SkBone->pDefaultFrames[frame]);
        /* RWASSERT(rwMatrixValidFlags(pMatrix, _EPSILON)); */

        pFrame->t.x = pMatrix->pos.x;
        pFrame->t.y = pMatrix->pos.y;
        pFrame->t.z = pMatrix->pos.z;
    }

    pFrame->time = time;

    RWRETURNVOID();
}

/****************************************************************************
 SkinLinkPrevFrames

 Link animation frames to their the previous frame in 
 an animation for the same bone

 Inputs :   RpSkin *        A pointer to the skin the animation is used on
            RpSkinAnim *    A pointer to the anim to process

 Outputs:   None
 */

static void
SkinLinkPrevFrames(RpSkin * pSkin, RpSkinAnim * pAnim)
{
    RwInt32             i, j;
    RpSkinFrame        *pCurrentFrame;
    RpSkinFrame        *pPrevFrame = (RpSkinFrame *) NULL;

    RWFUNCTION(RWSTRING("SkinLinkPrevFrames"));
    RWASSERT(pAnim);

    if (pSkin)
    {
        for (i = 0; i < pSkin->numBones; i++)
        {
            pCurrentFrame = pAnim->pFrames;
            pPrevFrame = (RpSkinFrame *) NULL;

            for (j = 0; j < pAnim->numFrames; j++)
            {
                if (pCurrentFrame->prevFrame ==
                    (RpSkinFrame *) (0x30000000 | i))
                {
                    pCurrentFrame->prevFrame = pPrevFrame;
                    pPrevFrame = pCurrentFrame;
                }

                pCurrentFrame++;
            }
        }
    }
    else
    {
        pCurrentFrame = pAnim->pFrames;
        pPrevFrame = (RpSkinFrame *) NULL;

        for (j = 0; j < pAnim->numFrames; j++)
        {
            if (pCurrentFrame->prevFrame ==
                (RpSkinFrame *) (0x30000000))
            {
                pCurrentFrame->prevFrame = pPrevFrame;
                pPrevFrame = pCurrentFrame;
            }

            pCurrentFrame++;
        }
    }

    RWRETURNVOID();
}

/**
 * \ingroup rpskin310
 * \ref RpSkinExtractAnimFromClumpSequence
 * extracts a named animation from a bone clump
 *
 * \param pClump  The clump from which to extract the animation
 * \param pSequenceName  The name of the animation
 *
 * \return pointer to the animation that has been extracted
 *
 * \see RpSkinCreateAtomicFromBoneClump
 */
RpSkinAnim         *
RpSkinExtractAnimFromClumpSequence(RpClump * pClump,
                                   RwChar * pSequenceName)
{
    RwInt32             currentKeys[64];
    RwReal              currentTimes[64];
    RwReal              totalTimes[64];
    RwReal              totalSequenceTime;
    RwReal              minTime;
    RwInt32             totalFrames, framesAdded;
    RpSkinFrame        *pRpSkinFrame;
    RpSkinFrame        *pCurrentRpSkinFrame;
    RwInt32             i, j;
    RpSkinAnim         *pRpSkinAnim;
    RpSkin             *pSkin = (RpSkin *) NULL;
    RwInt32             numBones;
    RwUInt32            bytes;

    RWAPIFUNCTION(RWSTRING("RpSkinExtractAnimFromClumpSequence"));
    RWASSERT(pClump);
    RWASSERT(pSequenceName);

    /* Initialize the skbone state block */
    _rpSkBoneStateConstructor();

    SkBone->pExtractSequenceName = pSequenceName;

    SkBone->ExtractSequenceFrameNumber = 0;

    /* Find the skin */

    RpClumpForAllAtomics(pClump, _rpSkinFindFirstAtomicSkinCallback,
                         (void *) &pSkin);

    /* Get the rotation and translation sequences for all frames */

    if (pSkin)
    {
        numBones = pSkin->numBones;
        RwFrameForAllChildren(RpClumpGetFrame(pClump),
                              _rpSkinExtractSequence, (void *) pSkin);
    }
    else
    {
        /* No skin 
         * - maybe we're just trying to animate a non-skinned clump then */
        numBones = 1;
        RwFrameForAllChildren(RpClumpGetFrame(pClump),
                              _rpSkinExtractSequence, (void *) NULL);
    }

    /* Sum the length of the sequence 
     * - assuming they're all the same, which they should be */

    totalSequenceTime = 0.0f;

    for (j = 0; j < numBones; j++)
    {
        totalTimes[j] = 0.0f;

        if (SkBone->pRotateSequences[j])
        {
            RWASSERT(SkBone->pTranslateSequences[j]->numInterpolators ==
                     SkBone->pRotateSequences[j]->numInterpolators);

            for (i = 0;
                 i < SkBone->pRotateSequences[j]->numInterpolators; i++)
            {
                totalTimes[j] +=
                    SkBone->pRotateSequences[j]->interps[i].time;
            }

            if (totalTimes[j] > totalSequenceTime)
            {
                totalSequenceTime = totalTimes[j];
            }
        }
        else
        {
            if (SkBone->pTranslateSequences[j])
            {
                for (i = 0;
                     i <
                     SkBone->pTranslateSequences[j]->numInterpolators;
                     i++)
                {
                    totalTimes[j] +=
                        SkBone->pTranslateSequences[j]->interps[i].time;
                }

                if (totalTimes[j] > totalSequenceTime)
                {
                    totalSequenceTime = totalTimes[j];
                }
            }
        }
    }

    /* Find total number of frames */

    totalFrames = 0;

    for (i = 0; i < numBones; i++)
    {
        if (SkBone->pRotateSequences[i])
        {
            totalFrames += SkBone->pRotateSequences[i]->numKeys;
        }
        else
        {
            if (SkBone->pTranslateSequences[i])
            {
                totalFrames += SkBone->pTranslateSequences[i]->numKeys;
            }
            else
            {
                /* If there's no rot/trans sequences, 
                 * we'll have frames at the start and end of the sequence */
                totalFrames += 2;
                totalTimes[i] = totalSequenceTime;
            }
        }

        if (totalTimes[i] < totalSequenceTime)
        {
            /* If the sequence for this bone does not last
             * the whole sequence time, add a further terminating frame */
            totalFrames++;
        }
    }

    /* Allocate memory for RpSkinFrame sequence */

    bytes = sizeof(RpSkinAnim) + (totalFrames * sizeof(RpSkinFrame));
    pRpSkinAnim = (RpSkinAnim *) RwMalloc(bytes);
    memset(pRpSkinAnim, 0, bytes);
    pRpSkinAnim->pFrames = (RpSkinFrame *) ((RwUInt8 *)pRpSkinAnim + sizeof(RpSkinAnim));
    pRpSkinFrame = pRpSkinAnim->pFrames;

    /* Add starting frames */

    pCurrentRpSkinFrame = pRpSkinFrame;

    for (i = 0; i < numBones; i++)
    {
        SkinAnimMakeFrame(pCurrentRpSkinFrame, i, 0, 0.0f);
        /* Temporarily store the bone number so 
         * we can link up the previous frame lists */
        pCurrentRpSkinFrame->prevFrame =
            (RpSkinFrame *) (0x30000000 | i);
        pCurrentRpSkinFrame++;
    }

    for (i = 0; i < numBones; i++)
    {

        if (SkBone->pRotateSequences[i])
        {
            currentTimes[i] =
                SkBone->pRotateSequences[i]->interps[0].time;
        }
        else
        {
            if (SkBone->pTranslateSequences[i])
            {
                currentTimes[i] =
                    SkBone->pTranslateSequences[i]->interps[0].time;
            }
            else
            {
                currentTimes[i] = totalSequenceTime;
            }
        }

        SkinAnimMakeFrame(pCurrentRpSkinFrame, i, 1, currentTimes[i]);
        /* Temporarily store the bone number 
         * so we can link up the previous frame lists */
        pCurrentRpSkinFrame->prevFrame =
            (RpSkinFrame *) (0x30000000 | i);
        pCurrentRpSkinFrame++;

        currentKeys[i] = 1;
    }

    /* Sort the frames into "JIT" order... */

    framesAdded = numBones * 2;

    while (framesAdded < totalFrames)
    {
        /* Find the smallest time left for any keyframe */

        minTime = 99999.9f;

        for (i = 0; i < numBones; i++)
        {
            if (currentTimes[i] < minTime)
            {
                minTime = currentTimes[i];
            }
        }

        /* Found the smallest time 
         * - add new frames for all sequences with this time */

        for (i = 0; i < numBones; i++)
        {
            if (currentTimes[i] == minTime)
            {

                if (currentTimes[i] == totalTimes[i])
                {
                    /* Add last key again */
                    currentTimes[i] = totalSequenceTime;
                    SkinAnimMakeFrame(pCurrentRpSkinFrame, i,
                                      currentKeys[i], currentTimes[i]);
                    currentKeys[i]++;
                }
                else
                {
                    currentKeys[i]++;
                    if (SkBone->pRotateSequences[i])
                    {
                        currentTimes[i] +=
                            SkBone->
                            pRotateSequences[i]->interps[currentKeys[i]
                                                         - 1].time;
                    }
                    else
                    {
                        currentTimes[i] +=
                            SkBone->pTranslateSequences[i]->interps
                            [currentKeys[i] - 1].time;
                    }
                    SkinAnimMakeFrame(pCurrentRpSkinFrame, i,
                                      currentKeys[i], currentTimes[i]);
                }

                /* Temporarily store the bone number 
                 * so we can link up the previous frame lists */
                pCurrentRpSkinFrame->prevFrame =
                    (RpSkinFrame *) (0x30000000 | i);

                pCurrentRpSkinFrame++;
                framesAdded++;
            }
        }
    }

    pRpSkinAnim->flags = 0;
    pRpSkinAnim->numFrames = totalFrames;
    pRpSkinAnim->duration = totalSequenceTime;

    SkinLinkPrevFrames(pSkin, pRpSkinAnim);

    /* Destroy the temporary anim sequences */

    SkBone->ExtractSequenceFrameNumber = 0;

    RwFrameForAllChildren(RpClumpGetFrame(pClump),
                          _rpSkinDestroySequence, (void *) pSkin);

    /* destroy the skbone state block */
    _rpSkBoneStateDestructor();

    RWRETURN(pRpSkinAnim);
}

void
_rpSkBoneStateDestructor(void)
{
    RWFUNCTION(RWSTRING("_rpSkBoneStateDestructor"));

    if (SkBone)
    {
        RwFree(SkBone);
        SkBone = (RpSkBoneState *) NULL;
    }

    RWASSERT(NULL == SkBone);

    RWRETURNVOID();
}

void
_rpSkBoneStateConstructor(void)
{
    RWFUNCTION(RWSTRING("_rpSkBoneStateConstructor"));

    if (NULL == SkBone)
    {
        const RwUInt32      bytes = sizeof(RpSkBoneState);

        SkBone = (RpSkBoneState *) RwMalloc(bytes);
        memset(SkBone, 0, bytes);
    }

    RWRETURNVOID();
}
