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: Node implementation

    15 *

    16 */

    17 

    18 

    19 /*!

    20  * \internal

    21  * \file

    22  * \brief Node 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_node.h"

    30 #include "m3g_memory.h"

    31 #include "m3g_animationtrack.h"

    32 #include "m3g_skinnedmesh.h"

    33 #include "m3g_tcache.h"

    34 #include "m3g_transformable.h"

    35 

    36 #define TARGET_NONE   0

    37 #define TARGET_X_AXIS 1

    38 #define TARGET_Y_AXIS 2

    39 #define TARGET_Z_AXIS 3

    40 #define TARGET_ORIGIN 4

    41 

    42 /*----------------------------------------------------------------------

    43  * Private functions

    44  *--------------------------------------------------------------------*/

    45 

    46 static M3Guint internalTarget(M3Genum target)

    47 {

    48     switch (target) {

    49     case M3G_NONE:

    50         return TARGET_NONE;

    51     case M3G_ORIGIN:

    52         return TARGET_ORIGIN;

    53     case M3G_X_AXIS:

    54         return TARGET_X_AXIS;

    55     case M3G_Y_AXIS:

    56         return TARGET_Y_AXIS;

    57     case M3G_Z_AXIS:

    58         return TARGET_Z_AXIS;

    59     default:

    60         M3G_ASSERT(M3G_FALSE);

    61         return TARGET_NONE;

    62     }

    63 }   

    64 

    65 static M3Guint externalTarget(M3Genum target)

    66 {

    67     switch (target) {

    68     case TARGET_NONE:

    69         return M3G_NONE;

    70     case TARGET_ORIGIN:

    71         return M3G_ORIGIN;

    72     case TARGET_X_AXIS:

    73         return M3G_X_AXIS;

    74     case TARGET_Y_AXIS:

    75         return M3G_Y_AXIS;

    76     case TARGET_Z_AXIS:

    77         return M3G_Z_AXIS;

    78     default:

    79         M3G_ASSERT(M3G_FALSE);

    80         return M3G_NONE;

    81     }

    82 }   

    83 

    84 /*----------------------------------------------------------------------

    85  * Constructor & destructor

    86  *--------------------------------------------------------------------*/

    87 

    88 /*!

    89  * \internal

    90  * \brief Initializes a Node object. See specification

    91  * for default values.

    92  *

    93  * \param m3g           M3G interface

    94  * \param node          Node object

    95  * \param vfTable       virtual function table

    96  */

    97 static void m3gInitNode(Interface *m3g, Node *node, M3GClass classID)

    98 {

    99 	/* Node is derived from Transformable */

   100 	m3gInitTransformable(&node->transformable, m3g, classID);

   101     

   102     /* Set default values */

   103     

   104     node->enableBits = (NODE_RENDER_BIT|NODE_PICK_BIT);

   105 	node->alphaFactor = (1u << NODE_ALPHA_FACTOR_BITS) - 1;

   106 	node->scope = -1;

   107     node->zTarget = TARGET_NONE;

   108     node->yTarget = TARGET_NONE;

   109 }

   110 

   111 /*!

   112  * \internal

   113  * \brief Destroys this Node object.

   114  *

   115  * \param obj Node object

   116  */

   117 static void m3gDestroyNode(Object *obj)

   118 {

   119     Node *node = (Node *) obj;

   120     M3G_VALIDATE_OBJECT(node);

   121     M3G_ASSERT(node->parent == NULL);

   122     m3gDestroyTransformable((Object *) node);

   123 }

   124 

   125 /*----------------------------------------------------------------------

   126  * Internal functions

   127  *--------------------------------------------------------------------*/

   128 

   129 /*!

   130  * \internal

   131  * \brief Checks if node is a child of the parent.

   132  *

   133  * \param parent    assumed parent Node object

   134  * \param child     Node object to check

   135  * \retval          M3G_TRUE is a child

   136  * \retval          M3G_FALSE is not a child

   137  */

   138 static M3Gbool m3gIsChildOf(const Node *parent, const Node *child)

   139 {

   140 	const Node *n;

   141 	

   142 	for (n = child; n != NULL; n = n->parent) {

   143 		if (n->parent == parent) return M3G_TRUE;

   144 	}

   145 	

   146 	return M3G_FALSE;

   147 }

   148 

   149 /*!

   150  * \internal

   151  * \brief Executes the given function for each node in a subtree

   152  *

   153  * The function \c func is executed recursively in each branch,

   154  * starting from the leaves. That is, the function is called for the

   155  * children of each group before the group itself.

   156  *

   157  * \param node   the node containing the subtree to process

   158  * \param func   pointer to the function to all for each node

   159  * \param params pointer to function-dependent arguments to pass

   160  * to each \c func invokation; this may be e.g. a structure

   161  * modified by \c func

   162  *

   163  * \return The return value of the top-level call to \c func

   164  */

   165 static void m3gForSubtree(Node *node, NodeFuncPtr func, void *params)

   166 {

   167     M3GClass nodeClass;

   168     M3G_VALIDATE_OBJECT(node);

   169     

   170     /* Recurse into the children first */

   171     

   172     nodeClass = M3G_CLASS(node);

   173     

   174     if (nodeClass == M3G_CLASS_SKINNED_MESH) {

   175         m3gForSubtree((Node*)((SkinnedMesh*)node)->skeleton, func, params);

   176     }

   177     else if (nodeClass == M3G_CLASS_GROUP ||

   178              nodeClass == M3G_CLASS_WORLD) {

   179         Group *group = (Group*) node;

   180         Node *child = group->firstChild;

   181         if (child) {

   182             do {

   183                 Node *next = child->right;

   184                 m3gForSubtree(child, func, params);

   185                 child = next;

   186             } while (child != group->firstChild);

   187         }

   188     }

   189 

   190     /* Execute function on self */

   191     

   192     (*func)(node, params);

   193 }

   194 

   195 /*!

   196  * \internal

   197  * \brief Overloaded Object3D method

   198  *

   199  * \param property      animation property

   200  * \retval M3G_TRUE     property supported

   201  * \retval M3G_FALSE    property not supported

   202  */

   203 static M3Gbool m3gNodeIsCompatible(M3Gint property)

   204 {

   205     switch (property) {

   206     case M3G_ANIM_ALPHA:

   207     case M3G_ANIM_PICKABILITY:

   208     case M3G_ANIM_VISIBILITY:

   209         return M3G_TRUE;

   210     default:

   211         return m3gTransformableIsCompatible(property);

   212     }

   213 }

   214 

   215 /*!

   216  * \internal

   217  * \brief Overloaded Object3D method

   218  *

   219  * \param self          Node object

   220  * \param property      animation property

   221  * \param valueSize     size of value array

   222  * \param value         value array

   223  */

   224 static void m3gNodeUpdateProperty(Object *self,

   225                                   M3Gint property,

   226                                   M3Gint valueSize,

   227                                   const M3Gfloat *value)

   228 {

   229     Node *node = (Node *)self;

   230     M3G_VALIDATE_OBJECT(node);

   231     M3G_ASSERT_PTR(value);

   232 

   233     switch (property) {

   234     case M3G_ANIM_ALPHA:

   235         M3G_ASSERT(valueSize >= 1);

   236         node->alphaFactor =

   237             m3gRoundToInt(

   238                 m3gMul(m3gClampFloat(value[0], 0.f, 1.f),

   239                        (float)((1 << NODE_ALPHA_FACTOR_BITS) - 1)));

   240         break;

   241     case M3G_ANIM_PICKABILITY:

   242         M3G_ASSERT(valueSize >= 1);

   243         node->enableBits &= ~NODE_PICK_BIT;

   244         if (value[0] >= 0.5f) {

   245             node->enableBits |= NODE_PICK_BIT;

   246         }

   247         break;

   248     case M3G_ANIM_VISIBILITY:

   249         M3G_ASSERT(valueSize >= 1);

   250         node->enableBits &= ~NODE_RENDER_BIT;

   251         if (value[0] >= 0.5f) {

   252             node->enableBits |= NODE_RENDER_BIT;

   253         }

   254         break;

   255     default:

   256         m3gTransformableUpdateProperty(self, property, valueSize, value);

   257     }

   258 }

   259 

   260 /*!

   261  * \internal

   262  * \brief Overloaded Object3D method

   263  *

   264  * \param originalObj original Node object

   265  * \param cloneObj pointer to cloned Node object

   266  * \param pairs array for all object-duplicate pairs

   267  * \param numPairs number of pairs

   268  */

   269 static M3Gbool m3gNodeDuplicate(const Object *originalObj,

   270                                 Object **cloneObj,

   271                                 Object **pairs,

   272                                 M3Gint *numPairs)

   273 {

   274     Node *original = (Node *)originalObj;

   275     Node *clone = (Node *)*cloneObj;

   276     M3G_ASSERT_PTR(*cloneObj); /* abstract class, must be derived */

   277 

   278     /* Duplicate base class data */

   279     

   280     if (!m3gTransformableDuplicate(originalObj, cloneObj, pairs, numPairs)) {

   281         return M3G_FALSE;

   282     }

   283 

   284     /* Duplicate our own data */

   285     

   286     clone->zReference  = original->zReference;

   287     clone->yReference  = original->yReference;

   288     clone->zTarget     = original->zTarget;

   289     clone->yTarget     = original->yTarget;

   290     clone->enableBits  = original->enableBits;

   291     clone->alphaFactor = original->alphaFactor;

   292     clone->scope       = original->scope;

   293     clone->hasBones    = original->hasBones;

   294     clone->hasRenderables = original->hasRenderables;

   295     

   296     return M3G_TRUE;

   297 }

   298 

   299 /*!

   300  * \internal

   301  * \brief Find corresponding duplicate for a Node

   302  *

   303  * \param node Node object

   304  * \param pairs array for all object-duplicate pairs

   305  * \param numPairs number of pairs

   306  */

   307 static Node *m3gGetDuplicatedInstance(Node *node, Object **pairs, M3Gint numPairs)

   308 {

   309     M3Gint i;

   310     for (i = 0; i < numPairs; i++)

   311         if (pairs[i * 2] == (Object *)node)

   312             return (Node *)pairs[i * 2 + 1];

   313     return NULL;

   314 }

   315 

   316 /*!

   317  * \internal

   318  * \brief Updates references of the duplicate object.

   319  *

   320  * When objects are duplicated scenegraph references

   321  * must be updated to equivalent duplicated references.

   322  * This function is overloaded by objects that have

   323  * references that has to be updated.

   324  *

   325  * \param self Node object

   326  * \param pairs array for all object-duplicate pairs

   327  * \param numPairs number of pairs

   328  */

   329 static void m3gNodeUpdateDuplicateReferences(Node *self, Object **pairs, M3Gint numPairs)

   330 {

   331     if (self->zTarget != TARGET_NONE && self->zReference != NULL) {

   332         Node *duplicatedInstance = m3gGetDuplicatedInstance(self, pairs, numPairs);

   333         Node *duplicatedRef = m3gGetDuplicatedInstance(self->zReference, pairs, numPairs);

   334         if (duplicatedRef != NULL

   335             && m3gIsChildOf(m3gGetRoot(duplicatedInstance), duplicatedRef)) {

   336             duplicatedInstance->zReference = duplicatedRef;

   337         }

   338     }

   339     if (self->yTarget != TARGET_NONE && self->yReference != NULL) {

   340         Node *duplicatedInstance = m3gGetDuplicatedInstance(self, pairs, numPairs);

   341         Node *duplicatedRef = m3gGetDuplicatedInstance(self->yReference, pairs, numPairs);

   342         if (duplicatedRef != NULL

   343             && m3gIsChildOf(m3gGetRoot(duplicatedInstance), duplicatedRef)) {

   344             duplicatedInstance->yReference = duplicatedRef;

   345         }

   346     }

   347 }

   348 

   349 /*!

   350  * \internal

   351  * \brief Gets size of the subtree

   352  *

   353  * \param node Node object

   354  * \param numRef number of references

   355  */

   356 static void m3gDoGetSubtreeSize(Node *node, void *numRef)

   357 {

   358     M3Gint *num = (M3Gint *)numRef;

   359     M3G_UNREF(node);

   360     (*num)++;

   361 }

   362 

   363 /*!

   364  * \internal

   365  * \brief Default function for non-pickable objects

   366  *

   367  * \param self      Camera object

   368  * \param mask      pick scope mask

   369  * \param ray       pick ray

   370  * \param ri        RayIntersection object

   371  * \param toGroup   transform to originating group

   372  * \retval M3G_TRUE always return success

   373  */

   374 static M3Gbool m3gNodeRayIntersect(Node *self,

   375                                    M3Gint mask,

   376                                    M3Gfloat *ray,

   377                                    RayIntersection *ri,

   378                                    Matrix *toGroup)

   379 {

   380     M3G_UNREF(self);

   381     M3G_UNREF(mask);

   382     M3G_UNREF(ray);

   383     M3G_UNREF(ri);

   384     M3G_UNREF(toGroup);

   385 

   386     return M3G_TRUE;

   387 }

   388 

   389 /*!

   390  * \internal

   391  * \brief Computes the bounding box for this node

   392  *

   393  * \param self  node pointer

   394  * \param bbox  bounding box structure filled in for non-zero return values

   395  * 

   396  * \return The "yield" factor for the node, i.e. the approximate

   397  * rendering cost of the node \em including any internal bounding box

   398  * checks; the yield factor is used to estimate the benefit of adding

   399  * enclosing bounding boxes at higher levels in the scene tree

   400  */

   401 static M3Gint m3gNodeGetBBox(Node *self, AABB *bbox)

   402 {

   403     M3G_UNREF(self);

   404     M3G_UNREF(bbox);

   405     return 0;

   406 }

   407 

   408 /*!

   409  * \internal

   410  * \brief Updates the bounding box for this node

   411  */

   412 static M3Gbool m3gNodeValidate(Node *self, M3Gbitmask stateBits, M3Gint scope)

   413 {

   414     M3G_UNREF(stateBits);

   415     M3G_UNREF(scope);

   416 

   417     /* Invalidate parent state in case we've encountered a previously

   418      * disabled node, then reset the dirty bits */

   419     

   420     if (self->dirtyBits && self->parent) {

   421         m3gInvalidateNode(self->parent, self->dirtyBits);

   422     }

   423     self->dirtyBits = 0;

   424     return M3G_TRUE;

   425 }

   426 

   427 /*!

   428  * \internal

   429  * \brief Gets a vector according to alignment target

   430  * and transforms it with a given transform.

   431  *

   432  * \param target        alignment target

   433  * \param transform     transform to be applied

   434  * \param out           vector to fill in

   435  */

   436 static void m3gTransformAlignmentTarget(M3Genum target,

   437                                         const Matrix *transform,

   438                                         Vec4 *out)

   439 {

   440 	switch (target) {

   441     case TARGET_ORIGIN:

   442 		*out = Vec4_ORIGIN;

   443 	    break;

   444 	case TARGET_X_AXIS:

   445 		*out = Vec4_X_AXIS;

   446 	    break;

   447 	case TARGET_Y_AXIS:

   448 		*out = Vec4_Y_AXIS;

   449 	    break;

   450 	case TARGET_Z_AXIS:

   451 		*out = Vec4_Z_AXIS;

   452 	    break;

   453 	default:

   454 		M3G_ASSERT(M3G_FALSE);

   455 	}

   456 

   457 	m3gTransformVec4(transform, out);

   458 }

   459 

   460 /*!

   461  * \internal

   462  * \brief Computes a single alignment rotation for a node.

   463  *

   464  * \param node              Node object

   465  * \param srcAxis           source axis

   466  * \param targetNode        Node object

   467  * \param targetAxisName    target axis name

   468  * \param constraint        constraint

   469  */

   470 static M3Gbool m3gComputeAlignmentRotation(Node *node,

   471                                            const Vec3 *srcAxis,

   472                                            const Node *targetNode,

   473                                            M3Genum targetAxisName,

   474                                            M3Genum constraint)

   475 {

   476     const Node *parent = node->parent;

   477     Matrix transform;

   478     Vec4 targetAxis;

   479     

   480     M3G_VALIDATE_OBJECT(parent);

   481     M3G_ASSERT(constraint == TARGET_NONE || constraint == TARGET_Z_AXIS);

   482 

   483     /* Get the transformation from the reference target node to the

   484      * current node, omitting all components except translation.

   485      * Rotation is also applied if this is a constrained alignment. */

   486     {

   487         const Transformable *tf = &node->transformable;

   488         

   489         if (!m3gGetTransformTo((M3GNode) targetNode, (M3GNode) parent,

   490                                &transform)) {

   491             return M3G_FALSE;

   492         }

   493         m3gPreTranslateMatrix(&transform, -tf->tx, -tf->ty, -tf->tz);

   494         

   495         if (constraint != TARGET_NONE) {

   496             Quat rot = tf->orientation;

   497             rot.w = -rot.w;

   498             m3gPreRotateMatrixQuat(&transform, &rot);

   499         }

   500     }

   501 

   502     m3gTransformAlignmentTarget(targetAxisName, &transform, &targetAxis);

   503 

   504     /* Apply the Z constraint if enabled; this is done by simply

   505      * zeroing the Z component of the target vector.  If the X and Y

   506      * alone don't span a non-zero vector, just exit as there's

   507      * nothing defined to rotate about. */

   508 

   509     if (constraint == TARGET_Z_AXIS) {

   510         M3Gfloat norm = m3gAdd(m3gMul(targetAxis.x, targetAxis.x),

   511                                m3gMul(targetAxis.y, targetAxis.y));

   512         if (norm < 1.0e-5f) {

   513             return M3G_TRUE;

   514         }

   515         norm = m3gRcpSqrt(norm);

   516         

   517         targetAxis.x = m3gMul(targetAxis.x, norm);

   518         targetAxis.y = m3gMul(targetAxis.y, norm);

   519         targetAxis.z = 0.0f;

   520                                 

   521         M3G_ASSERT(srcAxis->z == 0.0f);

   522     }

   523     else {

   524         m3gNormalizeVec3((Vec3*)&targetAxis); /* srcAxis will be unit length */

   525     }

   526 

   527     if (constraint != TARGET_NONE) {

   528         Quat rot;

   529         m3gSetQuatRotation(&rot, srcAxis, (const Vec3*) &targetAxis);

   530         m3gMulQuat(&node->transformable.orientation, &rot);

   531     }

   532     else {

   533         m3gSetQuatRotation(&node->transformable.orientation,

   534                            srcAxis, (const Vec3*) &targetAxis);

   535     }

   536 

   537     /* Invalidate transformations and bounding boxes after setting

   538      * node orientation */

   539     

   540     m3gInvalidateTransformable((Transformable*)node);

   541 

   542     return M3G_TRUE;

   543 }

   544 

   545 /*!

   546  * \internal

   547  * \brief Computes alignment for a single node.

   548  *

   549  * \param node              Node object

   550  * \param refNode           Node object

   551  * \retval                  M3G_TRUE alignment ok

   552  * \retval                  M3G_FALSE alignment failed

   553  */

   554 static M3Gbool m3gComputeAlignment(Node *node, const Node *refNode)

   555 {

   556     const Node *root = m3gGetRoot(node);

   557     const Node *zRef = node->zReference;

   558     const Node *yRef = node->yReference;

   559     const M3Genum zTarget = node->zTarget;

   560     const M3Genum yTarget = node->yTarget;

   561     M3G_VALIDATE_OBJECT(node);

   562 

   563     /* Quick exit if nothing to do */

   564     

   565     if (zTarget == TARGET_NONE && yTarget == TARGET_NONE) {

   566         return M3G_TRUE;

   567     }

   568         

   569     /* Check scene graph state */

   570     

   571     if (zRef != NULL && (m3gIsChildOf(node, zRef) || m3gGetRoot(zRef) != root)) {

   572         m3gRaiseError(M3G_INTERFACE(node), M3G_INVALID_OPERATION);

   573         return M3G_FALSE;

   574     }

   575     if (yRef != NULL && (m3gIsChildOf(node, yRef) || m3gGetRoot(yRef) != root)) {

   576         m3gRaiseError(M3G_INTERFACE(node), M3G_INVALID_OPERATION);

   577         return M3G_FALSE;

   578     }

   579 

   580     /* Compute the alignment rotations for Z and Y */

   581     {

   582         if (node->zTarget != TARGET_NONE) {

   583             if (zRef == NULL && refNode == node) {

   584                 m3gRaiseError(M3G_INTERFACE(node), M3G_INVALID_OPERATION);

   585                 return M3G_FALSE;

   586             }

   587             if (!m3gComputeAlignmentRotation(

   588                     node,

   589                     (const Vec3*) &Vec4_Z_AXIS,

   590                     zRef != NULL ? zRef : refNode,

   591                     zTarget,

   592                     TARGET_NONE)) {

   593                 return M3G_FALSE;

   594             }

   595         }

   596         if (node->yTarget != TARGET_NONE) {

   597             if (yRef == NULL && refNode == node) {

   598                 m3gRaiseError(M3G_INTERFACE(node), M3G_INVALID_OPERATION);

   599                 return M3G_FALSE;

   600             }

   601             if (!m3gComputeAlignmentRotation(

   602                     node,

   603                     (const Vec3*) &Vec4_Y_AXIS,

   604                     yRef != NULL ? yRef : refNode,

   605                     yTarget,

   606                     zTarget != TARGET_NONE ? TARGET_Z_AXIS : TARGET_NONE)) {

   607                 return M3G_FALSE;

   608             }

   609         }

   610     }   

   611     return M3G_TRUE;

   612 }

   613 

   614 /*!

   615  * \internal

   616  * \brief Gets the transformation to an ancestor node

   617  */

   618 static void m3gGetTransformUpPath(const Node *node, const Node *ancestor, Matrix *transform)

   619 {

   620     M3G_ASSERT(node);

   621     

   622     if (node == ancestor) {

   623         m3gIdentityMatrix(transform);

   624     }

   625     else {

   626         TCache *tc;

   627         M3G_ASSERT(!ancestor || m3gIsChildOf(ancestor, node));

   628     

   629         /* Look for a cached path */

   630 

   631         tc = m3gGetTransformCache(M3G_INTERFACE(node));

   632         if (m3gGetCachedPath(tc, node, ancestor, transform)) {

   633             return;

   634         }

   635     

   636         /* No dice -- do a recursive search and cache the result */

   637 

   638         if (node->parent == ancestor) {

   639             m3gGetCompositeNodeTransform(node, transform);

   640         }

   641         else {

   642             m3gGetTransformUpPath(node->parent, ancestor, transform);

   643             {

   644                 Matrix mtx;

   645                 m3gGetCompositeNodeTransform(node, &mtx);

   646                 m3gMulMatrix(transform, &mtx);

   647             }

   648         }

   649         m3gCachePath(tc, node, ancestor, transform);

   650     }

   651 }

   652 

   653 /*!

   654  * \internal

   655  * \brief Gets depth of a node in the scenegraph.

   656  *

   657  * \param node              Node object

   658  * \return                  Depth of the node

   659  */

   660 static M3Gint m3gGetDepth(const Node *node)

   661 {

   662 	const Node *n = node;

   663 	M3Gint depth = 0;

   664 

   665 	while (n->parent != NULL) {

   666 	    n = n->parent;

   667 	    depth++;

   668 	}

   669 

   670 	return depth;

   671 }

   672 

   673 /*!

   674  * \internal

   675  * \brief Gets root of a node in the scenegraph.

   676  *

   677  * \param node              Node object

   678  * \return                  root Node object

   679  */

   680 static Node *m3gGetRoot(const Node *node)

   681 {

   682     const Node *n = node;

   683 

   684     while (n->parent != NULL) {

   685         n = n->parent;

   686     }

   687 

   688     return (Node *)n;

   689 }

   690 

   691 /*!

   692  * \internal

   693  * \brief Gets total alpha factor.

   694  *

   695  * \param node              Node object

   696  * \param root              root Node object

   697  */

   698 static M3Guint m3gGetTotalAlphaFactor(Node *node, const Node *root)

   699 {

   700     const Node *n = node;

   701     M3Guint f = node->alphaFactor;

   702     

   703     while (n->parent != NULL && n != root) {

   704         n = n->parent;

   705         f = ((f + 1) * n->alphaFactor) >> NODE_ALPHA_FACTOR_BITS;

   706     }

   707     return f;

   708 }

   709 

   710 /*!

   711  * \internal

   712  * \brief Checks if node is enabled for rendering from the root.

   713  *

   714  * \param node              Node object

   715  * \param root              root Node object

   716  * \retval                  M3G_TRUE node is visible

   717  * \retval                  M3G_FALSE node is not visible

   718  */

   719 static M3Gbool m3gHasEnabledPath(const Node *node, const Node *root)

   720 {

   721 	const Node *n;

   722 	

   723 	for (n = node; n != NULL; n = n->parent) {

   724 	    if (!(n->enableBits & NODE_RENDER_BIT)) {

   725             return M3G_FALSE;

   726         }

   727 	    if (n == root) {

   728             break;

   729         }

   730 	}

   731 

   732     return M3G_TRUE;

   733 }

   734 

   735 /*!

   736  * \internal

   737  * \brief Checks if node is pickable from the root.

   738  *

   739  * \param node              Node object

   740  * \param root              root Node object

   741  * \retval                  M3G_TRUE node is pickable

   742  * \retval                  M3G_FALSE node is not pickable

   743  */

   744 static M3Gbool m3gHasPickablePath(const Node *node, const Node *root)

   745 {

   746 	const Node *n;

   747 	

   748 	for (n = node; n != NULL; n = n->parent) {

   749 	    if (!(n->enableBits & NODE_PICK_BIT)) {

   750             return M3G_FALSE;

   751         }

   752 	    if (n == root) {

   753             break;

   754         }

   755 	}

   756 

   757     return M3G_TRUE;

   758 }

   759 

   760 #if defined(M3G_ENABLE_VF_CULLING)

   761 /*!

   762  * \brief Invalidates the bounding box hierarchy from a node upwards

   763  */

   764 static void m3gInvalidateNode(Node *node, M3Gbitmask flags)

   765 {

   766     Interface *m3g = M3G_INTERFACE(node);

   767     M3G_BEGIN_PROFILE(m3g, M3G_PROFILE_VFC_UPDATE);

   768 

   769     while (node && (node->dirtyBits & flags) != flags) {

   770         node->dirtyBits |= flags;

   771         node = node->parent;

   772     }

   773     M3G_END_PROFILE(m3g, M3G_PROFILE_VFC_UPDATE);

   774 }

   775 #endif /*M3G_ENABLE_VF_CULLING*/

   776 

   777 /*!

   778  * \internal

   779  * \brief Aligns a node.

   780  *

   781  * \param node              Node object

   782  * \param ref               reference Node object

   783  *

   784  * \retval M3G_TRUE continue align

   785  * \retval M3G_FALSE abort align

   786  */

   787 static M3Gbool m3gNodeAlign(Node *node, const Node *ref) 

   788 {

   789     if (ref == NULL) {

   790         return m3gComputeAlignment(node, node);

   791     }

   792     else {

   793         M3G_VALIDATE_OBJECT(ref);

   794         return m3gComputeAlignment(node, ref);

   795     }

   796 }

   797 

   798 /*!

   799  * \internal

   800  * \brief Updates node counters when moving nodes around

   801  */

   802 static void m3gUpdateNodeCounters(Node *node,

   803                                   M3Gint nonCullableChange,

   804                                   M3Gint renderableChange)

   805 {

   806     Interface *m3g = M3G_INTERFACE(node);

   807     M3Gbool hasRenderables = (renderableChange > 0);

   808     M3G_BEGIN_PROFILE(m3g, M3G_PROFILE_VFC_UPDATE);

   809     while (node) {

   810         M3GClass nodeClass = M3G_CLASS(node);

   811         if (nodeClass == M3G_CLASS_GROUP || nodeClass == M3G_CLASS_WORLD) {

   812             Group *g = (Group *) node;

   813             g->numNonCullables = (M3Gushort)(g->numNonCullables + nonCullableChange);

   814             g->numRenderables  = (M3Gushort)(g->numRenderables + renderableChange);

   815             hasRenderables = (g->numRenderables > 0);

   816         }

   817         node->hasRenderables = hasRenderables;

   818         node = node->parent;

   819     }

   820     M3G_END_PROFILE(m3g, M3G_PROFILE_VFC_UPDATE);

   821 }

   822 

   823 /*!

   824  * \internal

   825  * \brief Sets the parent link of this node to a new value

   826  *

   827  * Relevant reference counts are updated accordingly, so note that

   828  * setting the parent to NULL may lead to either the node or the

   829  * parent itself being destroyed.

   830  *

   831  * \param node Node object

   832  * \param parent parent Node object

   833  */

   834 static void m3gSetParent(Node *node, Node *parent)

   835 {

   836     M3GClass nodeClass;

   837     M3Gint nonCullableChange = 0, renderableChange = 0;

   838     M3G_VALIDATE_OBJECT(node);

   839 

   840     /* Determine the number of various kinds of nodes being moved around */

   841 

   842     M3G_BEGIN_PROFILE(M3G_INTERFACE(node), M3G_PROFILE_VFC_UPDATE);

   843     nodeClass = M3G_CLASS(node);

   844     switch (nodeClass) {

   845     case M3G_CLASS_GROUP:

   846     {

   847         const Group *g = (const Group *) node;

   848         nonCullableChange = g->numNonCullables;

   849         renderableChange  = g->numRenderables;

   850         break;

   851     }

   852     case M3G_CLASS_SPRITE:

   853         renderableChange = 1;

   854         if (m3gIsScaledSprite((M3GSprite) node)) {

   855             break;

   856         }

   857         /* conditional fall-through! */

   858     case M3G_CLASS_LIGHT:

   859         nonCullableChange = 1;

   860         break;

   861     case M3G_CLASS_SKINNED_MESH:

   862     {

   863         const SkinnedMesh *mesh = (const SkinnedMesh *) node;

   864         nonCullableChange += mesh->skeleton->numNonCullables;

   865         renderableChange  += mesh->skeleton->numRenderables + 1;

   866         break;

   867     }

   868     case M3G_CLASS_MESH:

   869     case M3G_CLASS_MORPHING_MESH:

   870         renderableChange = 1;

   871         break;

   872     default:

   873         ;

   874     }

   875     M3G_END_PROFILE(M3G_INTERFACE(node), M3G_PROFILE_VFC_UPDATE);

   876 

   877     /* Invalidate any cached transformation paths through this node

   878      * *before* we move the node */

   879     

   880     m3gInvalidateCachedPaths(m3gGetTransformCache(M3G_INTERFACE(node)), node);

   881     

   882     /* Update bookkeeping for the old parent tree */

   883 

   884     if (node->parent) {

   885         m3gUpdateNodeCounters(node->parent,

   886                               -nonCullableChange, -renderableChange);

   887         if (renderableChange) {

   888             m3gInvalidateNode(node->parent, NODE_BBOX_BIT|NODE_TRANSFORMS_BIT);

   889         }

   890     }

   891 

   892     /* Change the parent link */

   893     

   894     if (node->parent == NULL && parent != NULL) {

   895         node->parent = parent;

   896         m3gAddRef((Object *) node);

   897     }

   898     else if (node->parent != NULL && parent == NULL) {

   899         node->parent = parent;

   900         m3gDeleteRef((Object *) node);

   901     }

   902 

   903     /* Update bookkeeping for the new parent tree */

   904 

   905     if (parent) {

   906         M3Gbitmask dirtyBits = node->dirtyBits;

   907         if (renderableChange) {

   908             dirtyBits |= NODE_BBOX_BIT;

   909         }

   910         if (node->hasBones) {

   911             dirtyBits |= NODE_TRANSFORMS_BIT;

   912         }

   913         m3gUpdateNodeCounters(parent, nonCullableChange, renderableChange);

   914         m3gInvalidateNode(parent, dirtyBits);

   915     }

   916 }

   917 

   918 /*!

   919  * \brief Computes the "near" and "far" box vertices

   920  * for plane testing

   921  */

   922 static M3G_INLINE void m3gGetTestPoints(const Vec3 *planeNormal,

   923                                         const AABB *box,

   924                                         Vec3 *vNear, Vec3 *vFar)

   925 {

   926     const M3Gfloat *fNormal = (const M3Gfloat*) planeNormal;

   927     M3Gfloat *fNear = (M3Gfloat*) vNear;

   928     M3Gfloat *fFar  = (M3Gfloat*) vFar;

   929     int i;

   930     

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

   932         M3Gfloat n = *fNormal++;

   933         if (IS_NEGATIVE(n)) {

   934             *fNear++ = box->max[i];

   935             *fFar++ = box->min[i];

   936         }

   937         else {

   938             *fNear++ = box->min[i];

   939             *fFar++ = box->max[i];

   940         }

   941     }

   942 }

   943 

   944 #if defined(M3G_ENABLE_VF_CULLING)

   945 /*!

   946  * \internal

   947  * \brief Update the frustum culling mask for one level of an AABB hierarchy

   948  *

   949  * \param s    the current traversal state

   950  * \param bbox the bounding box to check against

   951  */

   952 static void m3gUpdateCullingMask(SetupRenderState *s,

   953                                  const Camera *cam, const AABB *bbox)

   954 {

   955     M3Gbitmask cullMask = s->cullMask;

   956     M3G_BEGIN_PROFILE(M3G_INTERFACE(cam), M3G_PROFILE_VFC_TEST);

   957 

   958     /* First, check whether any planes are previously marked as

   959      * intersecting */

   960     

   961     if (cullMask & CULLMASK_ALL) {

   962                 

   963         /* We need to do some culling, so let's get the planes and the

   964          * transformation matrix; note that the "toCamera" matrix is

   965          * the inverse of the camera-to-node matrix, so we only need

   966          * to transpose */

   967 

   968         M3Gbitmask planeMask;

   969         const Vec4 *camPlanes = m3gFrustumPlanes(cam);

   970         

   971         Matrix t;

   972         m3gMatrixTranspose(&t, &s->toCamera);

   973         

   974         /* Loop over the active frustum planes, testing the ones we've

   975          * previously intersected with */

   976 

   977         planeMask = CULLMASK_INTERSECTS;

   978         while (planeMask <= cullMask) {

   979             if (cullMask & planeMask) {

   980                 

   981                 /* Transform the respective frustum plane into the node

   982                  * local space our AABB is in */

   983                 

   984                 Vec4 plane;

   985                 plane = *camPlanes++;

   986                 m3gTransformVec4(&t, &plane);

   987                 

   988                 /* Test the AABB against the plane and update the mask

   989                  * based on the result */

   990                 

   991                 m3gIncStat(M3G_INTERFACE(cam), M3G_STAT_CULLING_TESTS, 1);

   992                 {

   993                     /* Get the "near" and "far" corner points of the box */

   994                     

   995                     const Vec3* normal = (Vec3*) &plane;

   996                     Vec3 vNear, vFar;

   997                     m3gGetTestPoints(normal, bbox, &vNear, &vFar);

   998 

   999                     /* Our normals point inside, so flip this */

  1000                     

  1001                     plane.w = m3gNegate(plane.w);

  1002                     

  1003                     /* "Far" point behind plane? */

  1004                     

  1005                     if (m3gDot3(normal, &vFar) < plane.w) {

  1006                         /* All outside, no need to test further! */

  1007                         cullMask = 0;

  1008                         break;

  1009                     }

  1010                     

  1011                     /* "Near" point in front of plane? */

  1012 

  1013                     if (m3gDot3(normal, &vNear) > plane.w) {

  1014                         cullMask &= ~planeMask;

  1015                         cullMask |= planeMask >> 1; /* intersects->inside */

  1016                     }

  1017                 }

  1018             }

  1019             planeMask <<= 2; /* next plane */

  1020         }

  1021         s->cullMask = cullMask; /* write the output mask */

  1022     }

  1023     M3G_END_PROFILE(M3G_INTERFACE(cam), M3G_PROFILE_VFC_TEST);

  1024 }

  1025 #endif /*M3G_ENABLE_VF_CULLING*/

  1026 

  1027 /*----------------------------------------------------------------------

  1028  * Public API functions

  1029  *--------------------------------------------------------------------*/

  1030 

  1031 /*!

  1032  * \brief Gets transform from node to another.

  1033  *

  1034  * \param handle            Node object

  1035  * \param hTarget           target Node object

  1036  * \param transform         transform to fill in

  1037  * \retval                  M3G_TRUE success

  1038  * \retval                  M3G_FALSE failed

  1039  */

  1040 M3G_API M3Gbool m3gGetTransformTo(M3GNode handle,

  1041                                   M3GNode hTarget,

  1042                                   M3GMatrix *transform)

  1043 {

  1044     const Node *node = (Node *) handle;

  1045 	const Node *target = (Node *) hTarget;

  1046     TCache *tc;

  1047 	

  1048     M3G_VALIDATE_OBJECT(node);

  1049     M3G_BEGIN_PROFILE(M3G_INTERFACE(node), M3G_PROFILE_TRANSFORM_TO);

  1050 

  1051     /* Look for quick exits first */

  1052     

  1053     tc = m3gGetTransformCache(M3G_INTERFACE(node));

  1054 

  1055     if (node == target) {

  1056         m3gIdentityMatrix(transform);

  1057         M3G_END_PROFILE(M3G_INTERFACE(node), M3G_PROFILE_TRANSFORM_TO);

  1058         return M3G_TRUE;

  1059     }

  1060     else if (m3gGetCachedPath(tc, node, target, transform)) {

  1061         M3G_END_PROFILE(M3G_INTERFACE(node), M3G_PROFILE_TRANSFORM_TO);

  1062         return M3G_TRUE;

  1063     }

  1064     else {

  1065 

  1066         /* No luck, must recompute the whole thing -- begin by finding

  1067          * a common ancestor node for the pivot point of the path */

  1068         

  1069         const Node *pivot = NULL;

  1070         {

  1071             const Node *s = node;

  1072             const Node *t = target;

  1073 	

  1074             /* First traverse to the same depth */

  1075             {

  1076                 int sd = m3gGetDepth(s);

  1077                 int td = m3gGetDepth(t);

  1078             

  1079                 while (sd > td) {

  1080                     s = s->parent;

  1081                     --sd;

  1082                 }

  1083                 while (td > sd) {

  1084                     t = t->parent;

  1085                     --td;

  1086                 }

  1087             }

  1088 

  1089             /* Then traverse until we reach a common node or run out of

  1090              * ancestors in both branches, meaning there is no path

  1091              * between the nodes */

  1092         

  1093             while (s != t) {

  1094                 s = s->parent;	

  1095                 t = t->parent;

  1096             }

  1097             pivot = s;

  1098         }

  1099         if (!pivot) {

  1100             M3G_END_PROFILE(M3G_INTERFACE(node), M3G_PROFILE_TRANSFORM_TO);

  1101             return M3G_FALSE;

  1102         }

  1103         

  1104         /* Now, fetch the transformations for both branches and

  1105          * combine into the complete transformation; optimize by

  1106          * skipping most of that altogether for paths where the target

  1107          * node is the topmost node of the path */

  1108         

  1109         if (pivot != target) {

  1110             Matrix targetPath;

  1111             Matrix sourcePath;

  1112 

  1113             /* Look for a cached version of the to-target path to

  1114              * avoid the inversion if possible */

  1115             

  1116             if (!m3gGetCachedPath(tc, pivot, target, &targetPath)) {

  1117                 m3gGetTransformUpPath(target, pivot, &targetPath);

  1118             

  1119                 /* Invert the target-side path since we want the

  1120                  * downstream transformation for that one */

  1121             

  1122                 M3G_BEGIN_PROFILE(M3G_INTERFACE(node), M3G_PROFILE_TRANSFORM_INVERT);

  1123                 if (!m3gInvertMatrix(&targetPath)) {    

  1124                     M3G_END_PROFILE(M3G_INTERFACE(node), M3G_PROFILE_TRANSFORM_TO);

  1125                     m3gRaiseError(M3G_INTERFACE(node), M3G_ARITHMETIC_ERROR);

  1126                     return M3G_FALSE;

  1127                 }

  1128 

  1129                 /* Cache the inverse for future use */

  1130                 m3gCachePath(tc, pivot, target, &targetPath);

  1131             }

  1132             

  1133             M3G_ASSERT(m3gIsWUnity(&targetPath));

  1134 

  1135             /* Paste in the from-source path to get the complete