1 /*

     2 * Copyright (c) 2003 Nokia Corporation and/or its subsidiary(-ies).

     3 * All rights reserved.

     4 * This component and the accompanying materials are made available

     5 * under the terms of the License "Eclipse Public License v1.0"

     6 * which accompanies this distribution, and is available

     7 * at the URL "http://www.eclipse.org/legal/epl-v10.html".

     8 *

     9 * Initial Contributors:

    10 * Nokia Corporation - initial contribution.

    11 *

    12 * Contributors:

    13 *

    14 * Description: SkinnedMesh implementation

    15 *

    16 */

    17 

    18 

    19 /*!

    20  * \internal

    21  * \file

    22  * \brief SkinnedMesh implementation

    23  */

    24 

    25 #ifndef M3G_CORE_INCLUDE

    26 #   error included by m3g_core.c; do not compile separately.

    27 #endif

    28 

    29 #include "m3g_skinnedmesh.h"

    30 #include "m3g_memory.h"

    31 #include "m3g_animationtrack.h"

    32 

    33 /*----------------------------------------------------------------------

    34  * Internal structures

    35  *--------------------------------------------------------------------*/

    36 

    37 struct BoneRecord

    38 {

    39     Node *node;

    40 

    41     /*! \internal \brief "At-rest" transformation from skinned mesh to bone */

    42     Matrix toBone;

    43 

    44     /*! \internal \brief Cached animated transformation for positions */

    45     M3Gshort baseMatrix[9];

    46     M3Gshort posVec[3];

    47     M3Gshort baseExp, posExp, maxExp;

    48 

    49     /*! \internal \brief Cached animated transformation for normals */

    50     M3Gshort normalMatrix[9];

    51 };

    52 

    53 /*----------------------------------------------------------------------

    54  * Internal functions

    55  *--------------------------------------------------------------------*/

    56 

    57 /*!

    58  * \internal

    59  * \brief Destroys this SkinnedMesh object.

    60  *

    61  * \param obj SkinnedMesh object

    62  */

    63 static void m3gDestroySkinnedMesh(Object *obj)

    64 {

    65     SkinnedMesh *mesh = (SkinnedMesh *) obj;

    66     M3G_VALIDATE_OBJECT(mesh);

    67     {

    68         int i;

    69         Interface *m3g = M3G_INTERFACE(mesh);

    70         

    71         m3gDeleteVertexBuffer(mesh->morphedVB);

    72 

    73         for (i = 0; i < mesh->bonesPerVertex; ++i) {

    74             m3gFree(m3g, mesh->boneIndices[i]);

    75             m3gFree(m3g, mesh->boneWeights[i]);

    76             m3gFree(m3g, mesh->normalizedWeights[i]);

    77         }

    78         m3gFree(m3g, mesh->weightShifts);

    79         

    80         for (i = 0; i < m3gArraySize(&mesh->bones); ++i) {

    81             m3gFree(m3g, m3gGetArrayElement(&mesh->bones, i));

    82         }

    83         m3gDestroyArray(&mesh->bones, m3g);

    84         

    85         if (mesh->skeleton != NULL) {

    86             m3gSetParent((Node*) mesh->skeleton, NULL);

    87             M3G_ASSIGN_REF(mesh->skeleton, NULL);

    88         }

    89     }

    90     m3gDestroyMesh(obj);

    91 }

    92 

    93 

    94 /*!

    95  * \internal

    96  * \brief Get a bone index for a given node

    97  *

    98  * This finds an existing record if the bone has been added

    99  * previously, or creates a new one if no record exists yet.

   100  *

   101  * \note Inline because only called from AddTransform.

   102  */

   103 static M3G_INLINE M3Gint m3gBoneIndex(SkinnedMesh *mesh, Node *node)

   104 {

   105     PointerArray *boneArray = &mesh->bones;

   106     const int numBones = m3gArraySize(boneArray);

   107     

   108     /* First look for an existing record in the array */

   109     {

   110         int i;

   111         

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

   113             Bone *b = m3gGetArrayElement(boneArray, i);

   114             if (b->node == node) {

   115                 return i;

   116             }

   117         }

   118     }

   119 

   120     /* Not found; create a new one, append to the array, and set up

   121      * the "at-rest" transformation for the bone. Note, however, that

   122      * we can only store a maximum of 256 bones with byte indices! */

   123     {

   124         Interface *m3g = M3G_INTERFACE(mesh);

   125         

   126         if (numBones >= 256) {

   127             /* Out of available bone indices */

   128             m3gRaiseError(m3g, M3G_OUT_OF_MEMORY);

   129             return -1;

   130         }

   131         else {

   132             M3Gint idx;

   133             Bone *bone = (Bone*) m3gAllocZ(m3g, sizeof(Bone));

   134             if (!bone || !m3gGetTransformTo((Node*) mesh, node,

   135                                             &bone->toBone)) {

   136                 m3gFree(m3g, bone);

   137                 return -1; /* out of memory or singular transform */

   138             }

   139             bone->node = node;

   140 

   141             idx = m3gArrayAppend(boneArray, bone, m3g);

   142             if (idx < 0) {

   143                 m3gFree(m3g, bone);

   144                 return -1; /* out of memory */

   145             }

   146             return idx;

   147         }

   148     }

   149 }

   150 

   151 /*!

   152  * \internal

   153  * \brief Reallocate the per-vertex data if necessary.

   154  *

   155  * \note Inline because only called from AddTransform.

   156  */

   157 static M3G_INLINE M3Gbool m3gEnsureVertexCount(SkinnedMesh *mesh, M3Gint count)

   158 {

   159     /* Reallocate only if vertex count increased */

   160     

   161     if (count > mesh->weightedVertexCount) {

   162         

   163         Interface *m3g = M3G_INTERFACE(mesh);

   164 

   165         int i;

   166 

   167         /* Reallocate the weight shift array */

   168         {

   169             M3Gubyte *pNew = (M3Gubyte*) m3gAllocZ(m3g, count);

   170             if (!pNew) {

   171                 return M3G_FALSE;

   172             }

   173             m3gCopy(pNew, mesh->weightShifts, mesh->weightedVertexCount);

   174             m3gFree(m3g, mesh->weightShifts);

   175             mesh->weightShifts = pNew;

   176         }

   177 

   178         /* Reallocate each of the bone index and weight arrays */

   179         

   180         for (i = 0; i < mesh->bonesPerVertex; ++i) {

   181             

   182             M3Gubyte *pNew;

   183             

   184             /* Weights */

   185             pNew = (M3Gubyte*) m3gAllocZ(m3g, count);

   186             if (!pNew) {

   187                 return M3G_FALSE; /* out of memory */

   188             }

   189             m3gCopy(pNew, mesh->boneWeights[i], mesh->weightedVertexCount);

   190             m3gFree(m3g, mesh->boneWeights[i]);

   191             mesh->boneWeights[i] = pNew;

   192             

   193             pNew = (M3Gubyte*) m3gAllocZ(m3g, count);

   194             if (!pNew) {

   195                 return M3G_FALSE; /* out of memory */

   196             }

   197             m3gCopy(pNew, mesh->normalizedWeights[i],

   198                     mesh->weightedVertexCount);

   199             m3gFree(m3g, mesh->normalizedWeights[i]);

   200             mesh->normalizedWeights[i] = pNew;

   201 

   202             /* Indices */

   203             pNew = (M3Gubyte*) m3gAllocZ(m3g, count);

   204             if (!pNew) {

   205                 return M3G_FALSE; /* out of memory */

   206             }

   207             m3gCopy(pNew, mesh->boneIndices[i], mesh->weightedVertexCount);

   208             m3gFree(m3g, mesh->boneIndices[i]);

   209             mesh->boneIndices[i] = pNew;

   210         }

   211 

   212         mesh->weightedVertexCount = count;

   213     }

   214     return M3G_TRUE;

   215 }

   216     

   217 /*!

   218  * \internal

   219  * \brief Reallocate the per-vertex data if necessary.

   220  *

   221  * \note Inline because only called from AddTransform.

   222  */

   223 static M3G_INLINE M3Gbool m3gEnsureBonesPerVertex(SkinnedMesh *mesh,

   224                                                   M3Gint count)

   225 {

   226     M3G_ASSERT(count <= M3G_MAX_VERTEX_TRANSFORMS);

   227 

   228     /* Allocate only if per-vertex bone count increased */

   229     

   230     if (count > mesh->bonesPerVertex) {

   231         

   232         Interface *m3g = M3G_INTERFACE(mesh);

   233         

   234         const M3Gint vertexCount = mesh->weightedVertexCount;

   235         M3Gubyte *pNew;

   236         

   237         int i;

   238 

   239         /* Allocate new arrays for bone indices and weights until

   240          * we're satisfied */

   241         

   242         for (i = mesh->bonesPerVertex; i < count; ++i) {

   243             pNew = (M3Gubyte*) m3gAllocZ(m3g, vertexCount);

   244             if (!pNew) {

   245                 goto AllocFailed; /* out of memory */

   246             }

   247             mesh->boneIndices[i] = pNew;

   248             

   249             pNew = (M3Gubyte*) m3gAllocZ(m3g, vertexCount);

   250             if (!pNew) {

   251                 goto AllocFailed; /* out of memory */

   252             }

   253             mesh->boneWeights[i] = pNew;

   254             

   255             pNew = (M3Gubyte*) m3gAllocZ(m3g, vertexCount);

   256             if (!pNew) {

   257                 goto AllocFailed; /* out of memory */

   258             }

   259             mesh->normalizedWeights[i] = pNew;

   260         }

   261 

   262         mesh->bonesPerVertex = count;

   263         return M3G_TRUE;

   264 

   265         /* In case of failure, clean up to keep the bonesPerVertex

   266          * counter in sync with the actual number of arrays

   267          * allocated */

   268     

   269     AllocFailed:

   270         for (i = mesh->bonesPerVertex; i < count; ++i) {

   271             m3gFree(m3g, mesh->boneIndices[i]);

   272             m3gFree(m3g, mesh->boneWeights[i]);

   273             m3gFree(m3g, mesh->normalizedWeights[i]);

   274 

   275             mesh->boneIndices[i] = NULL;

   276             mesh->boneWeights[i] = NULL;

   277             mesh->normalizedWeights[i] = NULL;

   278         }

   279         return M3G_FALSE;

   280     }

   281     return M3G_TRUE;

   282 }

   283     

   284 /*!

   285  * \internal

   286  * \brief Add a new bone influence to a vertex

   287  *

   288  * If the target vertex is already affected by

   289  * M3G_MAX_VERTEX_TRANSFORMS bones, the one with the lowest weight is

   290  * discarded.

   291  */

   292 static M3G_INLINE void m3gAddInfluence(SkinnedMesh *mesh,

   293                                        M3Gint vertexIndex,

   294                                        M3Gint boneIndex,

   295                                        M3Gint weight) 

   296 {

   297     M3Gint bonesPerVertex = mesh->bonesPerVertex;

   298     M3Guint minWeight = weight;

   299     M3Gint minWeightIndex = -1;

   300     int i;

   301 

   302     /* Shift the weight into the same scale with the other weights for

   303      * this vertex. */

   304 

   305     weight >>= mesh->weightShifts[vertexIndex];

   306 

   307     /* Look for an existing weight for our bone, or find the index

   308      * with the lowest weight if not found, and store it in

   309      * minWeightIndex.  Note that we're not separately tagging indices

   310      * as used/unused; unused ones will merely have a weight of

   311      * zero. */

   312         

   313     for (i = 0; i < bonesPerVertex; ++i) {

   314 

   315         /* If we find an existing weight for our bone, just add to

   316          * that and break out. Otherwise, keep track of the minimum

   317          * weight encountered so far. */

   318         

   319         if (mesh->boneIndices[i][vertexIndex] == boneIndex) {

   320             weight += mesh->boneWeights[i][vertexIndex];

   321             minWeightIndex = i;

   322             break;

   323         }

   324         else {

   325             M3Guint tempWeight = mesh->boneWeights[i][vertexIndex];

   326             if (tempWeight < minWeight) {

   327                 minWeight = tempWeight;

   328                 minWeightIndex = i;

   329             }

   330         }

   331     }

   332 

   333     /* Check whether our total weight exceeds the allocated range,

   334      * shifting all existing weights down if necessary */

   335 

   336     while (weight >= (1 << 8)) { /* byte range */

   337         weight >>= 1;

   338         mesh->weightShifts[vertexIndex] += 1;

   339         for (i = 0; i < bonesPerVertex; ++i) {

   340             mesh->boneWeights[i][vertexIndex] >>= 1;

   341         }

   342         M3G_ASSERT(mesh->weightShifts[vertexIndex] <= 31);

   343     }

   344 

   345     /* Add the index and weight contribution of the new

   346      * transformation, provided that the minimum weight found was

   347      * indeed smaller than the one we're adding */

   348         

   349     if (minWeightIndex >= 0) {

   350         mesh->boneIndices[minWeightIndex][vertexIndex] = (M3Gubyte) boneIndex;

   351         mesh->boneWeights[minWeightIndex][vertexIndex] = (M3Gubyte) weight;

   352 

   353         /* Need an update of the normalizing scales, too, as well as

   354          * the actual transformed vertices */

   355         

   356         mesh->weightsDirty = M3G_TRUE;

   357         m3gInvalidateNode((Node*) mesh, NODE_TRANSFORMS_BIT|NODE_BBOX_BIT);

   358     }

   359 }

   360 

   361 /*!

   362  * \internal

   363  * \brief Computes the normalization scales for vertex weights

   364  */

   365 static void m3gNormalizeWeights(SkinnedMesh *mesh)

   366 {

   367     const M3Gint bonesPerVertex = mesh->bonesPerVertex;

   368     const M3Gint vertexCount = mesh->weightedVertexCount;

   369     M3Gint vi;

   370 

   371     for (vi = 0; vi < vertexCount; ++vi) {

   372         M3Gint k;

   373         

   374         /* Sum up the 8-bit (possibly downshifted) weights */

   375         

   376         M3Guint sum = 0;

   377         for (k = 0; k < bonesPerVertex; ++k) {

   378             sum += mesh->boneWeights[k][vi];

   379         }

   380 

   381         /* Compute an 8.24 reciprocal of the weights, then scale with

   382          * that to normalize, and shift to 1.7 fixed point */

   383         {

   384             M3Guint s = (sum > 0 ? (1U << 24) / sum : 0);

   385 

   386             sum = 0;

   387             for (k = 0; k < bonesPerVertex; ++k) {

   388                 M3Guint normalized = (s * mesh->boneWeights[k][vi]) >> 17;

   389                 M3G_ASSERT(m3gInRange((M3Gint)normalized, 0, 128));

   390                 sum += normalized;

   391                 mesh->normalizedWeights[k][vi] = (M3Gubyte) normalized;

   392             }

   393             

   394             /* NOTE there is a maximum of ½ rounding error per

   395              * component, plus the rounding error from the reciprocal

   396              * calculation, so the sum of weights will often not sum

   397              * to 128 exactly! We therefore only assert against

   398              * clearly out-of-range values here */

   399             

   400             M3G_ASSERT(sum == 0 || m3gInRange((M3Gint) sum, 96, 128));

   401         }

   402     }

   403 

   404     mesh->weightsDirty = M3G_FALSE;

   405 }

   406 

   407 /*!

   408  * \internal

   409  * \brief Computes an optimal exponent value for a fixed point

   410  * transformation

   411  *

   412  * This scales the translation exponent up to optimally utilize the

   413  * 32-bit intermediate precision if the matrix exponent is smaller.

   414  */

   415 static M3Gint m3gOptimalExponent(M3Gint matrixExp, M3Gint transExp)

   416 {

   417     M3Gint maxExp = matrixExp;

   418     M3Gint shift = transExp - matrixExp;

   419     if (shift > 0) {

   420 

   421         /* The matrix part will always occupy less than half of the

   422          * available range if shifted down by at least one bit, so we

   423          * can shift the translation up by a maximum of 15 bits.  If

   424          * the matrix is shifted by more than 31 bits, it will always

   425          * flush to zero, freeing the full 32-bit range for the

   426          * translation alone. */

   427 

   428         if (shift >= 32) {      /* matrix will flush to zero */

   429             shift = 16;

   430         }

   431         else if (shift >= 16) { /* matrix always < half of the range */

   432             shift = 15;

   433         }

   434         else {

   435             shift -= 1;     /* shift matrix by at least one bit */

   436         }

   437         

   438         maxExp = transExp - shift;

   439     }

   440     

   441     M3G_ASSERT(maxExp >= matrixExp && maxExp >= transExp - 16);

   442     return maxExp;

   443 }

   444 

   445 /*

   446  * \brief Fixed point vertex transformation

   447  *

   448  * \param mtx        pointer to a 3x3 16-bit matrix

   449  * \param mtxExp     exponent for the matrix elements (upshift from int)

   450  * \param trans      pointer to 3-element 16-bit translation vector

   451  * \param transExp   exponent for the translation vector

   452  * \param maxExp     precalculated "optimal" exponent

   453  * \param vx         vertex X coordinate (16-bit range)

   454  * \param vy         vertex Y coordinate (16-bit range)

   455  * \param vz         vertex Z coordinate (16-bit range)

   456  * \param out        output vertex, 25 bits of precision

   457  * \return exponent value for \c out

   458  */

   459 static M3Gint m3gFixedPointTransform(const M3Gshort *mtx, M3Gint mtxExp,

   460                                      const M3Gshort *trans, M3Gint transExp,

   461                                      M3Gint maxExp,

   462                                      M3Gint vx, M3Gint vy, M3Gint vz,

   463                                      M3Gint *out)

   464 {

   465     M3Gint shift;

   466     M3Gint ox = 0, oy = 0, oz = 0;

   467     

   468     /* First put in the translation part, upscaled to the optimal

   469      * range for this bone */

   470 

   471     if (trans) {

   472         shift = maxExp - (transExp - 16);

   473         M3G_ASSERT(shift >= 0);

   474         if (shift < 32) {

   475             ox += ((M3Gint) trans[0] << 16) >> shift;

   476             oy += ((M3Gint) trans[1] << 16) >> shift;

   477             oz += ((M3Gint) trans[2] << 16) >> shift;

   478         }

   479     }

   480         

   481     /* Add the input multiplied with the base 3x3 matrix and shifted

   482      * to the "maxExp" scale, provided that it has any effect on the

   483      * outcome */

   484     

   485     shift = maxExp - mtxExp;

   486     M3G_ASSERT(shift >= 0);

   487     if (shift < 32) {

   488         

   489 #       if defined(M3G_DEBUG)

   490         M3Gint iMin = (-1 << 31) + (65535 * 32768 >> shift);

   491         M3Gint iMax = (M3Gint)((1u << 31)-1) - (65535 * 32768 >> shift);

   492         M3G_ASSERT(m3gInRange(ox, iMin, iMax));

   493         M3G_ASSERT(m3gInRange(oy, iMin, iMax));

   494         M3G_ASSERT(m3gInRange(oz, iMin, iMax));

   495 #       endif /* M3G_DEBUG */

   496         

   497         ox += (mtx[0] * vx + mtx[3] * vy + mtx[6] * vz) >> shift;

   498         oy += (mtx[1] * vx + mtx[4] * vy + mtx[7] * vz) >> shift;

   499         oz += (mtx[2] * vx + mtx[5] * vy + mtx[8] * vz) >> shift;

   500     }

   501 

   502     /* Shift the output down to fit into 25 bits; we're dropping 7

   503      * bits of precision here, so adjust the exponent accordingly */

   504 

   505     out[0] = ox >> 7;

   506     out[1] = oy >> 7;

   507     out[2] = oz >> 7;

   508     return maxExp + 7;

   509 }

   510 

   511 /*!

   512  * \internal

   513  * \brief Applies scale and bias to a vertex

   514  *

   515  * This is required for vertices that have no bones attached.

   516  * 

   517  * \param mesh    the SkinnedMesh object

   518  * \param vx      vertex X coordinate (16-bit range)

   519  * \param vy      vertex Y coordinate (16-bit range)

   520  * \param vz      vertex Z coordinate (16-bit range)

   521  * \param upshift scaling value for the input coordinates and the

   522  *                translation component of the transformation

   523  * \param vertex  output vertex position

   524  * \return exponent value for \c vertex

   525  */

   526 static M3Gint m3gScaleAndBiasVertex(const SkinnedMesh *mesh,

   527                                     M3Gint vx, M3Gint vy, M3Gint vz,

   528                                     M3Gint upshift,

   529                                     M3Gshort *vertex)

   530 {

   531     M3Gint temp[3];

   532     M3Gint expo;

   533 

   534     M3G_ASSERT(m3gInRange(vx, -1 << 15, (1 << 15) - 1));

   535     M3G_ASSERT(m3gInRange(vy, -1 << 15, (1 << 15) - 1));

   536     M3G_ASSERT(m3gInRange(vz, -1 << 15, (1 << 15) - 1));

   537     

   538     expo = m3gFixedPointTransform(mesh->scaleMatrix, mesh->scaleExp,

   539                                   mesh->biasVector, mesh->biasExp + upshift,

   540                                   mesh->scaleBiasExp,

   541                                   vx << upshift, vy << upshift, vz << upshift,

   542                                   temp) - upshift;

   543 

   544     /* Scale down from 25 to 16 bits, adjusting the exponent

   545      * accordingly */

   546     

   547     vertex[0] = (M3Gshort)(temp[0] >> 9);

   548     vertex[1] = (M3Gshort)(temp[1] >> 9);

   549     vertex[2] = (M3Gshort)(temp[2] >> 9);

   550     expo += 9;

   551     

   552     M3G_ASSERT(m3gInRange(expo, -127, 127));

   553     return expo;

   554 }

   555 

   556 /*!

   557  * \internal

   558  * \brief Computes the blended position for a single vertex

   559  *

   560  * \param mesh    the SkinnedMesh object

   561  * \param vidx    vertex index (for accessing bone data)

   562  * \param vx      vertex X coordinate (16-bit range)

   563  * \param vy      vertex Y coordinate (16-bit range)

   564  * \param vz      vertex Z coordinate (16-bit range)

   565  * \param upshift scaling value for the input coordinates and the

   566  *                translation component of the transformation

   567  * \param vertex  output vertex position

   568  * \return exponent value for \c vertex

   569  */

   570 static M3Gint m3gBlendVertex(const SkinnedMesh *mesh,

   571                              M3Gint vidx,

   572                              M3Gint vx, M3Gint vy, M3Gint vz,

   573                              M3Gint upshift,

   574                              M3Gshort *vertex)

   575 {

   576     const M3Gint boneCount = mesh->bonesPerVertex;

   577     const PointerArray *boneArray = &mesh->bones;

   578     M3Gint i;

   579     

   580     M3Gint outExp = -128;

   581     M3Gint sumWeights = 0;

   582     

   583     M3Gint ox = 0, oy = 0, oz = 0;

   584     

   585     vx <<= upshift;

   586     vy <<= upshift;

   587     vz <<= upshift;

   588 

   589     M3G_ASSERT(m3gInRange(vx, -1 << 15, (1 << 15) - 1));

   590     M3G_ASSERT(m3gInRange(vy, -1 << 15, (1 << 15) - 1));

   591     M3G_ASSERT(m3gInRange(vz, -1 << 15, (1 << 15) - 1));

   592 

   593     /* Loop over the bones and sum the contribution from each */

   594     

   595     for (i = 0; i < boneCount; ++i) {

   596         

   597         M3Gint weight = (M3Gint) mesh->normalizedWeights[i][vidx];

   598         sumWeights += weight;

   599 

   600         /* Skip bones with zero weights */

   601         

   602         if (weight > 0) {

   603             

   604             const Bone *bone = (const Bone *)

   605                 m3gGetArrayElement(boneArray, mesh->boneIndices[i][vidx]);

   606             M3Gint temp[3];

   607             M3Gint shift;

   608 

   609             shift = m3gFixedPointTransform(bone->baseMatrix, bone->baseExp,

   610                                            bone->posVec, bone->posExp + upshift,

   611                                            bone->maxExp,

   612                                            vx, vy, vz,

   613                                            temp);

   614 

   615             shift = outExp - shift;

   616             if (shift < 0) {

   617                 shift = -shift;

   618                 if (shift < 31) {

   619                     ox >>= shift;

   620                     oy >>= shift;

   621                     oz >>= shift;

   622                 }

   623                 else {

   624                     ox = oy = oz = 0;

   625                 }

   626                 outExp += shift;

   627                 shift = 0;

   628             }

   629 

   630             /* Apply the vertex weights: 1.7 * 25.0 -> 26.7, but since

   631              * the weights are positive and sum to 1, we should stay

   632              * within the 32-bit range */

   633             

   634             if (shift < 31) {

   635                 

   636                 M3G_ASSERT(m3gInRange(temp[0], -1 << 24, (1 << 24) - 1));

   637                 M3G_ASSERT(m3gInRange(temp[1], -1 << 24, (1 << 24) - 1));

   638                 M3G_ASSERT(m3gInRange(temp[2], -1 << 24, (1 << 24) - 1));

   639                 

   640                 ox += (weight * temp[0]) >> shift;

   641                 oy += (weight * temp[1]) >> shift;

   642                 oz += (weight * temp[2]) >> shift;

   643             }

   644         }

   645     }

   646 

   647     /* Before returning, we still need to check for the special case

   648      * of all-zero weights, and shift the values from the post-scaling

   649      * 32-bit precision back into the 16-bit range; we're essentially

   650      * dropping the (25 - 16) bits of the blended result, so the

   651      * exponent must change accordingly */

   652 

   653     if (sumWeights > 0) {

   654         vertex[0] = (M3Gshort)(ox >> 16);

   655         vertex[1] = (M3Gshort)(oy >> 16);

   656         vertex[2] = (M3Gshort)(oz >> 16);

   657         outExp = outExp - upshift + 9;

   658 

   659         M3G_ASSERT(m3gInRange(outExp, -127, 127));

   660         return outExp;

   661     }

   662     else {

   663         vx >>= upshift;

   664         vy >>= upshift;

   665         vz >>= upshift;

   666         return m3gScaleAndBiasVertex(mesh, vx, vy, vz, upshift, vertex);

   667     }

   668 }

   669 

   670 /*!

   671  * \internal

   672  * \brief Computes the blended normal vector for a single vertex

   673  *

   674  * \param mesh    the SkinnedMesh object

   675  * \param vidx    vertex index (for accessing bone data)

   676  * \param nx      normal X coordinate (16-bit range)

   677  * \param ny      normal Y coordinate (16-bit range)

   678  * \param nz      normal Z coordinate (16-bit range)

   679  * \param upshift scaling for input coordinates to increase precision

   680  * \param normal  output normal vector (8-bit range!)

   681  * \return a shift value for the output vertex (scale from integer)

   682  */

   683 static void m3gBlendNormal(const SkinnedMesh *mesh,

   684                            M3Gint vidx,

   685                            M3Gint nx, M3Gint ny, M3Gint nz,

   686                            M3Gint upshift,

   687                            M3Gbyte *normal)

   688 {

   689     const M3Gint boneCount = mesh->bonesPerVertex;

   690     const PointerArray *boneArray = &mesh->bones;

   691     M3Gint i;

   692     

   693     M3Gint outExp = -128;

   694     M3Gint sumWeights = 0;

   695     

   696     M3Gint ox = 0, oy = 0, oz = 0;

   697 

   698     nx <<= upshift;

   699     ny <<= upshift;

   700     nz <<= upshift;

   701     

   702     M3G_ASSERT(m3gInRange(nx, -1 << 15, (1 << 15) - 1));

   703     M3G_ASSERT(m3gInRange(ny, -1 << 15, (1 << 15) - 1));

   704     M3G_ASSERT(m3gInRange(nz, -1 << 15, (1 << 15) - 1));

   705 

   706     /* Loop over the bones and sum the contribution from each */

   707     

   708     for (i = 0; i < boneCount; ++i) {

   709         

   710         M3Gint weight = (M3Gint) mesh->normalizedWeights[i][vidx];

   711         sumWeights += weight;

   712 

   713         /* Skip bones with zero weights */

   714         

   715         if (weight > 0) {

   716             

   717             const Bone *bone = (const Bone *)

   718                 m3gGetArrayElement(boneArray, mesh->boneIndices[i][vidx]);

   719             M3Gint temp[3];

   720             M3Gint shift;

   721 

   722             shift = m3gFixedPointTransform(bone->normalMatrix, 0,

   723                                            NULL, 0,

   724                                            0,

   725                                            nx, ny, nz,

   726                                            temp);

   727 

   728             shift = outExp - shift;

   729             if (shift < 0) {

   730                 shift = -shift;

   731                 if (shift < 31) {

   732                     ox >>= shift;

   733                     oy >>= shift;

   734                     oz >>= shift;

   735                 }

   736                 else {

   737                     ox = oy = oz = 0;

   738                 }

   739                 outExp += shift;

   740                 shift = 0;

   741             }

   742 

   743             /* Apply the vertex weights: 1.7 * 25.0 -> 26.7, but since

   744              * the weights are positive and sum to 1, we should stay

   745              * within the 32-bit range */

   746             

   747             if (shift < 31) {

   748                 

   749                 M3G_ASSERT(m3gInRange(temp[0], -1 << 24, (1 << 24) - 1));

   750                 M3G_ASSERT(m3gInRange(temp[1], -1 << 24, (1 << 24) - 1));

   751                 M3G_ASSERT(m3gInRange(temp[2], -1 << 24, (1 << 24) - 1));

   752                 

   753                 ox += (weight * temp[0]) >> shift;

   754                 oy += (weight * temp[1]) >> shift;

   755                 oz += (weight * temp[2]) >> shift;

   756             }

   757         }

   758     }

   759 

   760     /* Before returning, we still need to check for the special case

   761      * of all-zero weights, and shift the values from the post-scaling

   762      * 32-bit precision down into the 8-bit range */

   763 

   764     if (sumWeights > 0) {

   765         normal[0] = (M3Gbyte)(ox >> 24);

   766         normal[1] = (M3Gbyte)(oy >> 24);

   767         normal[2] = (M3Gbyte)(oz >> 24);

   768     }

   769     else {

   770         normal[0] = (M3Gbyte)(ox >> 8);

   771         normal[1] = (M3Gbyte)(oy >> 8);

   772         normal[2] = (M3Gbyte)(oz >> 8);

   773     }

   774 }

   775 

   776 /*!

   777  * \internal

   778  * \brief Updates internal vertex buffer

   779  *

   780  * \param mesh SkinnedMesh object

   781  *

   782  * \retval M3G_TRUE VertexBuffer is up to date

   783  * \retval M3G_FALSE Failed to update VertexBuffer, out of memory exception raised

   784  */

   785 static M3Gbool m3gSkinnedMeshUpdateVB(SkinnedMesh *mesh)

   786 {

   787     M3Gint vbTimestamp;

   788     M3G_ASSERT(mesh->mesh.vertexBuffer != NULL);

   789     M3G_ASSERT(mesh->morphedVB != NULL);

   790     

   791     /* Source vertex buffer array configuration changed since last

   792      * update? */

   793 

   794     vbTimestamp = m3gGetTimestamp(mesh->mesh.vertexBuffer);

   795     

   796     if (mesh->vbTimestamp != vbTimestamp) {

   797         Interface *m3g = M3G_INTERFACE(mesh);

   798         VertexArray *array;

   799         M3Gint vcount = m3gGetVertexCount(mesh->mesh.vertexBuffer);

   800 

   801         /* Must ensure that our internal morphing buffer matches the

   802          * configuration of the source buffer, with dedicated arrays

   803          * for the morphed positions and normals */

   804         

   805         if (!m3gMakeModifiedVertexBuffer(mesh->morphedVB,

   806                                          mesh->mesh.vertexBuffer,

   807                                          M3G_POSITION_BIT|M3G_NORMAL_BIT,

   808                                          M3G_FALSE)) {

   809             return M3G_FALSE; /* out of memory */

   810         }

   811 

   812         /* We always have the vertex positions as shorts, but the

   813          * array may not be actually initialized yet, so we must check

   814          * whether to create a copy or not */

   815 

   816         if (mesh->mesh.vertexBuffer->vertices) {

   817             array = m3gCreateVertexArray(m3g, vcount, 3, M3G_SHORT);

   818             if (!array) {

   819                 return M3G_FALSE;

   820             }

   821             m3gSetVertexArray(mesh->morphedVB, array, 1.f, NULL, 0);

   822         }

   823 

   824         /* Normals (always bytes) only exist if in the original VB */

   825         

   826         if (mesh->mesh.vertexBuffer->normals) {

   827             array = m3gCreateVertexArray(m3g, vcount, 3, M3G_BYTE);

   828             if (!array) {

   829                 return M3G_FALSE;

   830             }

   831             m3gSetNormalArray(mesh->morphedVB, array);

   832         }

   833     

   834         mesh->vbTimestamp = vbTimestamp;

   835     }

   836     

   837     /* The default color must always be updated, because it can be

   838      * animated (doesn't affect timestamp) */

   839     

   840     mesh->morphedVB->defaultColor = mesh->mesh.vertexBuffer->defaultColor;

   841     return M3G_TRUE;

   842 }

   843 

   844 

   845 /*!

   846  * \internal

   847  * \brief Gets the transformation(s) for a single bone record

   848  *

   849  * Also stores the normal transformation matrix if needed.

   850  *

   851  * \param mesh       pointer to the mesh object

   852  * \param bone       pointer to the bone record

   853  * \param hasNormals flag indicating whether the normals transformation

   854  *                   should be computed and cached in the bone record

   855  * \param mtx        matrix to store the vertex transformation in

   856  */

   857 static M3G_INLINE M3Gbool m3gGetBoneTransformInternal(SkinnedMesh *mesh,

   858                                               Bone *bone,

   859                                               M3Gbool hasNormals,

   860                                               Matrix *mtx)

   861 {

   862     const VertexBuffer *vb = mesh->mesh.vertexBuffer;

   863 

   864     /* Get the vertex transformation and concatenate it with the

   865      * at-rest matrix and the vertex scale and bias transformations.

   866      * The resulting 3x4 transformation matrix is then split into a

   867      * fixed point 3x3 matrix and translation vector */

   868     

   869     if (!m3gGetTransformTo(bone->node, (Node*) mesh, mtx)) {

   870         return M3G_FALSE; /* no path or singular transform */

   871     }

   872     m3gMulMatrix(mtx, &bone->toBone);

   873 

   874     /* If normals are enabled, compute and store the inverse transpose

   875      * matrix for transforming normals at this stage */

   876     

   877     if (hasNormals) {

   878         Matrix t;

   879         if (!m3gInverseTranspose(&t, mtx)) {

   880             m3gRaiseError(M3G_INTERFACE(mesh), M3G_ARITHMETIC_ERROR);

   881             return M3G_FALSE; /* singular transform */

   882         }

   883         m3gGetFixedPoint3x3Basis(&t, bone->normalMatrix);

   884     }

   885 

   886     /* Apply the vertex bias and scale to the transformation */

   887     

   888     m3gTranslateMatrix(

   889         mtx, vb->vertexBias[0], vb->vertexBias[1], vb->vertexBias[2]);

   890     m3gScaleMatrix(mtx, vb->vertexScale, vb->vertexScale, vb->vertexScale);

   891     

   892     return M3G_TRUE;

   893 }

   894 

   895 /*!

   896  * \internal

   897  * \brief Compute and cache the bone transformations for morphing

   898  *

   899  * \param mesh     the SkinnedMesh object

   900  * \param posShift vertex position value "gain"

   901  */

   902 static M3Gbool m3gPreComputeTransformations(SkinnedMesh *mesh,

   903                                             M3Gint posShift,

   904                                             M3Gbool hasNormals)

   905 {

   906     M3Gint boneCount = m3gArraySize(&mesh->bones);

   907     M3Gint i;

   908     Matrix *tBone = NULL;

   909 

   910     /* First, just compute the floating point transformation matrices

   911      * for the bones, caching them in a temp array */

   912 

   913     if (boneCount > 0) {

   914         tBone = m3gAllocTemp(M3G_INTERFACE(mesh), boneCount * sizeof(Matrix));

   915         if (!tBone) {

   916             return M3G_FALSE; /* out of memory */

   917         }    

   918         for (i = 0; i < boneCount; ++i) {

   919             Bone *bone = m3gGetArrayElement(&mesh->bones, i);

   920             if (!m3gGetBoneTransformInternal(mesh, bone, hasNormals, &tBone[i])) {

   921                 return M3G_FALSE;

   922             }

   923         }

   924     }

   925 

   926     /* Find the value range of the bone translations, and offset the

   927      * bones to center output vertex values (roughly) around the

   928      * origin */

   929     {

   930         const VertexBuffer *vb = mesh->mesh.vertexBuffer;

   931         M3Gfloat min[3], max[3], bias[3];

   932         M3Gint maxExp;

   933         Vec4 t;

   934 

   935         /* Find the minimum and maximum values; start with the plain

   936          * vertex bias for non-weighted bones */

   937         

   938         min[0] = max[0] = vb->vertexBias[0];

   939         min[1] = max[1] = vb->vertexBias[1];

   940         min[2] = max[2] = vb->vertexBias[2];

   941         

   942         for (i = 0; i < boneCount; ++i) {

   943             m3gGetMatrixColumn(&tBone[i], 3, &t); 

   944             min[0] = M3G_MIN(min[0], t.x);

   945             max[0] = M3G_MAX(max[0], t.x);

   946             min[1] = M3G_MIN(min[1], t.y);

   947             max[1] = M3G_MAX(max[1], t.y);

   948             min[2] = M3G_MIN(min[2], t.z);

   949             max[2] = M3G_MAX(max[2], t.z);

   950         }

   951         

   952         /* Divide to get the mean translation, store in the

   953          * destination VB, and invert for de-biasing the bones */

   954         

   955         for (i = 0; i < 3; ++i) {

   956             bias[i] = m3gMul(0.5f, m3gAdd(min[i], max[i]));

   957             mesh->morphedVB->vertexBias[i] = bias[i];

   958             bias[i] = m3gNegate(bias[i]);

   959         }

   960         

   961         /* Offset bones by the (now inverted) bias vector, and store

   962          * the fixed point matrix & vector parts in the bone record;

   963          * also set the maximum bone exponent into the mesh */

   964 

   965         maxExp = -128;

   966         for (i = 0; i < boneCount; ++i) {

   967             Bone *bone = m3gGetArrayElement(&mesh->bones, i);

   968             m3gPreTranslateMatrix(&tBone[i], bias[0], bias[1], bias[2]); /*lint !e613 tBone not null if boneCount > 0 */

   969             

   970             bone->baseExp = (M3Gshort)

   971                 m3gGetFixedPoint3x3Basis(&tBone[i], bone->baseMatrix); /*lint !e613 tBone not null if boneCount > 0 */

   972             bone->posExp = (M3Gshort)

   973                 m3gGetFixedPointTranslation(&tBone[i], bone->posVec); /*lint !e613 tBone not null if boneCount > 0 */

   974             bone->maxExp = (M3Gshort)

   975                 m3gOptimalExponent(bone->baseExp, bone->posExp + posShift);

   976 

   977             maxExp = M3G_MAX(maxExp, bone->maxExp);

   978         }

   979 

   980         /* Make a fixed-point matrix for applying the scale and bias as

   981          * well, for vertices not attached to any bone (this is not the

   982          * optimal way to store the information, but we can just reuse

   983          * existing code this way) */

   984         {

   985             Matrix sb;

   986             m3gTranslationMatrix(&sb,

   987                                  m3gAdd(bias[0], vb->vertexBias[0]),

   988                                  m3gAdd(bias[1], vb->vertexBias[1]),

   989                                  m3gAdd(bias[2], vb->vertexBias[2]));

   990             m3gScaleMatrix(&sb,

   991                            vb->vertexScale, vb->vertexScale, vb->vertexScale);

   992             

   993             mesh->scaleExp = (M3Gshort)

   994                 m3gGetFixedPoint3x3Basis(&sb, mesh->scaleMatrix);

   995             mesh->biasExp = (M3Gshort)

   996                 m3gGetFixedPointTranslation(&sb, mesh->biasVector);

   997             mesh->scaleBiasExp = (M3Gshort)

   998                 m3gOptimalExponent(mesh->scaleExp, mesh->biasExp + posShift);

   999         

  1000             maxExp = M3G_MAX(mesh->scaleBiasExp, maxExp);

  1001         }

  1002 

  1003         /* Compute the maximum post-blending exponent and store it as the

  1004          * morphed vertex buffer scale -- this is dependent on the

  1005          * implementations of m3gBlendVertex, m3gScaleAndBiasVertex, and

  1006          * m3gFixedPointTransform! */

  1007 

  1008         maxExp = maxExp + 16 - posShift;

  1009         M3G_ASSERT(m3gInRange(maxExp, -127, 127));

  1010         *(M3Gint*)&mesh->morphedVB->vertexScale = (maxExp + 127) << 23;

  1011         mesh->maxExp = (M3Gshort) maxExp;

  1012     }

  1013     

  1014     if (boneCount > 0) {

  1015         m3gFreeTemp(M3G_INTERFACE(mesh));

  1016     }

  1017     

  1018     return M3G_TRUE;

  1019 }

  1020 

  1021 /*!

  1022  * \internal

  1023  * \brief Computes derived data required for bounding volumes and skinning

  1024  */

  1025 static M3Gbool m3gSkinnedMeshPreMorph(SkinnedMesh *mesh)

  1026 {

  1027     const VertexBuffer *srcVB = mesh->mesh.vertexBuffer;

  1028     M3Gint posShift = 0, normalShift = 0;

  1029     

  1030     /* Compute upscaling shift values for positions and normals so

  1031      * that we can maximize precision even for absurdly small

  1032      * vertex values */

  1033     {

  1034         M3Gint minVal, maxVal;

  1035         

  1036         if (srcVB->normals) {

  1037             m3gGetArrayValueRange(srcVB->normals, &minVal, &maxVal);

  1038             maxVal = M3G_MAX(-minVal, maxVal);

  1039             M3G_ASSERT(maxVal >= 0);

  1040             if (maxVal) {

  1041                 while ((maxVal << normalShift) < (1 << 14)) {

  1042                     ++normalShift;

  1043                 }

  1044             }

  1045         }

  1046             

  1047         m3gGetArrayValueRange(srcVB->vertices, &minVal, &maxVal);

  1048         maxVal = M3G_MAX(-minVal, maxVal);

  1049         M3G_ASSERT(maxVal >= 0);

  1050         if (maxVal) {

  1051             while ((maxVal << posShift) < (1 << 14)) {

  1052                 ++posShift;

  1053             }

  1054         }

  1055         

  1056         mesh->posShift    = (M3Gshort) posShift;

  1057         mesh->normalShift = (M3Gshort) normalShift;

  1058     }

  1059 

  1060     /* Now that we can compute the optimized exponents for the

  1061      * transformations based on the position upshift value, let's

  1062      * resolve the bone transformations; this will also cache the

  1063      * maximum bone exponent in mesh->maxExp */

  1064 

  1065     if (!m3gPreComputeTransformations(mesh,

  1066                                       posShift,

  1067                                       srcVB->normals != NULL)) { 

  1068         return M3G_FALSE; /* invalid transform */

  1069     }

  1070     

  1071     return M3G_TRUE;

  1072 }

  1073 

  1074 /*!

  1075  * \internal

  1076  * \brief Does the actual vertex morphing into the internal vertex buffer

  1077  *

  1078  * \param mesh   SkinnedMesh object

  1079  * \retval M3G_TRUE     skinning ok

  1080  * \retval M3G_FALSE    skinning failed, exception raised

  1081  */

  1082 static void m3gSkinnedMeshMorph(SkinnedMesh *mesh)

  1083 {

  1084     const VertexBuffer *srcVB = mesh->mesh.vertexBuffer;

  1085     const void *srcPositions;

  1086     const void *srcNormals = NULL;

  1087     VertexBuffer *dstVB = mesh->morphedVB;

  1088     M3Gshort *dstPositions;

  1089     M3Gbyte *dstNormals = NULL;

  1090     M3Gint vertexCount = mesh->weightedVertexCount;

  1091     M3Gint maxExp = mesh->maxExp;

  1092     M3Gint posShift = mesh->posShift, normShift = mesh->normalShift;

  1093     M3Gint i;

  1094 

  1095     M3G_ASSERT(!((Node*) mesh)->dirtyBits);

  1096     

  1097     /* Let's update the vertex weights if we need to */

  1098         

  1099     if (mesh->weightsDirty) {

  1100         m3gNormalizeWeights(mesh);

  1101     }

  1102 

  1103     /* Get pointers to source and destination position and normal

  1104      * data; the latter will always be shorts and bytes,

  1105      * respectively, while the former can be either */

  1106         

  1107     srcPositions = m3gMapVertexArrayReadOnly(srcVB->vertices);

  1108     dstPositions = (M3Gshort*) m3gMapVertexArray(dstVB->vertices);

  1109     if (srcVB->normals) {

  1110         srcNormals = m3gMapVertexArrayReadOnly(srcVB->normals);

  1111         dstNormals = (M3Gbyte*) m3gMapVertexArray(dstVB->normals);

  1112     }

  1113         

  1114     /* Transform the vertices that are affected by bones */

  1115     {

  1116         M3Gshort *dst = dstPositions;

  1117             

  1118         if (srcVB->vertices->elementType == GL_BYTE) {

  1119             const M3Gbyte *src = (const M3Gbyte*) srcPositions;

  1120             for (i = 0; i < vertexCount; ++i) {

  1121                 M3Gint shift =

  1122                     maxExp - m3gBlendVertex(mesh, i,

  1123                                             src[0], src[1], src[2],

  1124                                             posShift,

  1125                                             dst);

  1126                 if (shift > 31) {

  1127                     *dst++ = 0;

  1128                     *dst++ = 0;

  1129                     *dst++ = 0;

  1130                 }

  1131                 else {

  1132                     *dst++ >>= shift;

  1133                     *dst++ >>= shift;

  1134                     *dst++ >>= shift;

  1135                 }