OPC_OptimizedTree.h

Go to the documentation of this file.

/*
 *      OPCODE - Optimized Collision Detection
 *      Copyright (C) 2001 Pierre Terdiman
 *      Homepage: http://www.codercorner.com/Opcode.htm
 */




// Include Guard
#ifndef __OPC_OPTIMIZEDTREE_H__
#define __OPC_OPTIMIZEDTREE_H__

#if (defined __x86_64) || (defined __aarch64__)
#define EXWORD uqword
#else
#define EXWORD udword
#endif

        #define IMPLEMENT_IMPLICIT_NODE(base_class, volume)                                                                                                             \
                public:                                                                                                                                                                                         \
                /* Constructor / Destructor */                                                                                                                                          \
                inline_                                                         base_class() : mData(0) {}                                                                              \
                inline_                                                         ~base_class()                   {}                                                                              \
                /* Leaf test */                                                                                                                                                                         \
                inline_                 BOOL                            IsLeaf()                const   { return mData&1;                                       }       \
                /* Data access */                                                                                                                                                                       \
                inline_                 const base_class*       GetPos()                const   { return (base_class*)mData;            }       \
                inline_                 const base_class*       GetNeg()                const   { return ((base_class*)mData)+1;        }       \
                /* Modified by S-cubed, Inc. */                                                                                                                                         \
                inline_                 const base_class*       GetB()                  const   { return                                mB;             }       \
                inline_                 udword                          GetPrimitive()  const   { return (mData>>1);                            }       \
                /* Stats */                                                                                                                                                                                     \
                inline_                 udword                          GetNodeSize()   const   { return SIZEOFOBJECT;                          }       \
                                                                                                                                                                                                                        \
                                                volume                          mAABB;                                                                                                                  \
                                                EXWORD                          mData;                                                                                                                  \
                /* Modified by S-cubed, Inc. */                                                                                                                                         \
                                                base_class*                     mB;                                                                                                                             

        #define IMPLEMENT_NOLEAF_NODE(base_class, volume)                                                                                                               \
                public:                                                                                                                                                                                         \
                /* Constructor / Destructor */                                                                                                                                          \
                inline_                                                         base_class() : mPosData(0), mNegData(0) {}                                              \
                inline_                                                         ~base_class()                                                   {}                                              \
                /* Leaf tests */                                                                                                                                                                        \
                inline_                 BOOL                            HasPosLeaf()            const   { return mPosData&1;                    }       \
                inline_                 BOOL                            HasNegLeaf()            const   { return mNegData&1;                    }       \
                /* Data access */                                                                                                                                                                       \
                inline_                 const base_class*       GetPos()                        const   { return (base_class*)mPosData; }       \
                inline_                 const base_class*       GetNeg()                        const   { return (base_class*)mNegData; }       \
                /* Modified by S-cubed, Inc. */                                                                                                                                         \
                inline_                 const base_class*       GetB()                          const   { return                                mB;             }       \
                inline_                 udword                          GetPosPrimitive()       const   { return (mPosData>>1);                 }       \
                inline_                 udword                          GetNegPrimitive()       const   { return (mNegData>>1);                 }       \
                /* Stats */                                                                                                                                                                                     \
                inline_                 udword                          GetNodeSize()           const   { return SIZEOFOBJECT;                  }       \
                                                                                                                                                                                                                        \
                                                volume                          mAABB;                                                                                                                  \
                                                EXWORD                          mPosData;                                                                                                               \
                                                EXWORD                          mNegData;                                                                                                               \
                /* Modified by S-cubed, Inc. */                                                                                                                                         \
                                                base_class*                     mB;                                                                                                                             

        class OPCODE_API AABBCollisionNode
        {
                IMPLEMENT_IMPLICIT_NODE(AABBCollisionNode, CollisionAABB)

                inline_                 float                           GetVolume()             const   { return mAABB.mExtents.x * mAABB.mExtents.y * mAABB.mExtents.z;        }
                inline_                 float                           GetSize()               const   { return mAABB.mExtents.SquareMagnitude();      }
                inline_                 udword                          GetRadius()             const
                                                                                        {
                                                                                                udword* Bits = (udword*)&mAABB.mExtents.x;
                                                                                                udword Max = Bits[0];
                                                                                                if(Bits[1]>Max) Max = Bits[1];
                                                                                                if(Bits[2]>Max) Max = Bits[2];
                                                                                                return Max;
                                                                                        }

                // NB: using the square-magnitude or the true volume of the box, seems to yield better results
                // (assuming UNC-like informed traversal methods). I borrowed this idea from PQP. The usual "size"
                // otherwise, is the largest box extent. In SOLID that extent is computed on-the-fly each time it's
                // needed (the best approach IMHO). In RAPID the rotation matrix is permuted so that Extent[0] is
                // always the greatest, which saves looking for it at runtime. On the other hand, it yields matrices
                // whose determinant is not 1, i.e. you can't encode them anymore as unit quaternions. Not a very
                // good strategy.
        };

        class OPCODE_API AABBQuantizedNode
        {
                IMPLEMENT_IMPLICIT_NODE(AABBQuantizedNode, QuantizedAABB)

                inline_                 uword                           GetSize()               const
                                                                                        {
                                                                                                const uword* Bits = mAABB.mExtents;
                                                                                                uword Max = Bits[0];
                                                                                                if(Bits[1]>Max) Max = Bits[1];
                                                                                                if(Bits[2]>Max) Max = Bits[2];
                                                                                                return Max;
                                                                                        }
                // NB: for quantized nodes I don't feel like computing a square-magnitude with integers all
                // over the place.......!
        };

        class OPCODE_API AABBNoLeafNode
        {
                IMPLEMENT_NOLEAF_NODE(AABBNoLeafNode, CollisionAABB)
        };

        class OPCODE_API AABBQuantizedNoLeafNode
        {
                IMPLEMENT_NOLEAF_NODE(AABBQuantizedNoLeafNode, QuantizedAABB)
        };

        #define IMPLEMENT_COLLISION_TREE(base_class, node)                                                                                                                              \
                public:                                                                                                                                                                                                         \
                /* Constructor / Destructor */                                                                                                                                                          \
                                                                                                        base_class();                                                                                                   \
                virtual                                                                         ~base_class();                                                                                                  \
                /* Builds from a standard tree */                                                                                                                                                       \
                override(AABBOptimizedTree)     bool                    Build(AABBTree* tree);                                                                                  \
                /* Refits the tree */                                                                                                                                                                           \
                override(AABBOptimizedTree)     bool                    Refit(const MeshInterface* mesh_interface);                                             \
                /* Walks the tree */                                                                                                                                                                            \
                override(AABBOptimizedTree)     bool                    Walk(GenericWalkingCallback callback, void* user_data) const;   \
                /* Data access */                                                                                                                                                                                       \
                inline_                                         const node*             GetNodes()              const   { return mNodes;                                        }       \
                /* Stats */                                                                                                                                                                                                     \
                override(AABBOptimizedTree)     udword                  GetUsedBytes()  const   { return mNbNodes*sizeof(node);         }       \
                private:                                                                                                                                                                                                        \
                                                                        node*                   mNodes;

        typedef         bool                            (*GenericWalkingCallback)       (const void* current, void* user_data);

        class OPCODE_API AABBOptimizedTree
        {
                public:
                // Constructor / Destructor
                                                                                        AABBOptimizedTree() :
                                                                                                mNbNodes        (0)
                                                                                                                                                                                        {}
                virtual                                                         ~AABBOptimizedTree()                                                    {}



                virtual                 bool                            Build(AABBTree* tree)                                                                                   = 0;



                virtual                 bool                            Refit(const MeshInterface* mesh_interface)                                              = 0;



                virtual                 bool                            Walk(GenericWalkingCallback callback, void* user_data) const    = 0;

                // Data access
                virtual                 udword                          GetUsedBytes()          const                                                                           = 0;
                inline_                 udword                          GetNbNodes()            const                                           { return mNbNodes;      }

                protected:
                                                udword                          mNbNodes;
        };

        class OPCODE_API AABBCollisionTree : public AABBOptimizedTree
        {
                IMPLEMENT_COLLISION_TREE(AABBCollisionTree, AABBCollisionNode)
        };

        class OPCODE_API AABBNoLeafTree : public AABBOptimizedTree
        {
                IMPLEMENT_COLLISION_TREE(AABBNoLeafTree, AABBNoLeafNode)
        };

        class OPCODE_API AABBQuantizedTree : public AABBOptimizedTree
        {
                IMPLEMENT_COLLISION_TREE(AABBQuantizedTree, AABBQuantizedNode)

                public:
                                                Point                           mCenterCoeff;
                                                Point                           mExtentsCoeff;
        };

        class OPCODE_API AABBQuantizedNoLeafTree : public AABBOptimizedTree
        {
                IMPLEMENT_COLLISION_TREE(AABBQuantizedNoLeafTree, AABBQuantizedNoLeafNode)

                public:
                                                Point                           mCenterCoeff;
                                                Point                           mExtentsCoeff;
        };

#endif // __OPC_OPTIMIZEDTREE_H__