Extras/CDTestFramework/Opcode/OPC_TreeBuilders.h

   1 /*
   2  *      OPCODE - Optimized Collision Detection
   3  * http://www.codercorner.com/Opcode.htm
   4  *
   5  * Copyright (c) 2001-2008 Pierre Terdiman,  pierre@codercorner.com
   6
   7 This software is provided 'as-is', without any express or implied warranty.
   8 In no event will the authors be held liable for any damages arising from the use of this software.
   9 Permission is granted to anyone to use this software for any purpose,
  10 including commercial applications, and to alter it and redistribute it freely,
  11 subject to the following restrictions:
  12
  13 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
  14 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
  15 3. This notice may not be removed or altered from any source distribution.
  16 */
  17
  18 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  19 /**
  20  *      Contains code for tree builders.
  21  *      \file           OPC_TreeBuilders.h
  22  *      \author         Pierre Terdiman
  23  *      \date           March, 20, 2001
  24  */
  25 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  26
  27 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  28 // Include Guard
  29 #ifndef __OPC_TREEBUILDERS_H__
  30 #define __OPC_TREEBUILDERS_H__
  31
  32         //! Tree splitting rules
  33         enum SplittingRules
  34         {
  35                 // Primitive split
  36                 SPLIT_LARGEST_AXIS              = (1<<0),               //!< Split along the largest axis
  37                 SPLIT_SPLATTER_POINTS   = (1<<1),               //!< Splatter primitive centers (QuickCD-style)
  38                 SPLIT_BEST_AXIS                 = (1<<2),               //!< Try largest axis, then second, then last
  39                 SPLIT_BALANCED                  = (1<<3),               //!< Try to keep a well-balanced tree
  40                 SPLIT_FIFTY                             = (1<<4),               //!< Arbitrary 50-50 split
  41                 // Node split
  42                 SPLIT_GEOM_CENTER               = (1<<5),               //!< Split at geometric center (else split in the middle)
  43                 //
  44                 SPLIT_FORCE_DWORD               = 0x7fffffff
  45         };
  46
  47         //! Simple wrapper around build-related settings [Opcode 1.3]
  48         struct OPCODE_API BuildSettings
  49         {
  50                 inline_ BuildSettings() : mLimit(1), mRules(SPLIT_FORCE_DWORD)  {}
  51
  52                 udword  mLimit;         //!< Limit number of primitives / node. If limit is 1, build a complete tree (2*N-1 nodes)
  53                 udword  mRules;         //!< Building/Splitting rules (a combination of SplittingRules flags)
  54         };
  55
  56         class OPCODE_API AABBTreeBuilder
  57         {
  58                 public:
  59                 //! Constructor
  60                                                                                                         AABBTreeBuilder() :
  61                                                                                                                 mNbPrimitives(0),
  62                                                                                                                 mNodeBase(null),
  63                                                                                                                 mCount(0),
  64                                                                                                                 mNbInvalidSplits(0)             {}
  65                 //! Destructor
  66                 virtual                                                                         ~AABBTreeBuilder()                      {}
  67
  68                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  69                 /**
  70                  *      Computes the AABB of a set of primitives.
  71                  *      \param          primitives              [in] list of indices of primitives
  72                  *      \param          nb_prims                [in] number of indices
  73                  *      \param          global_box              [out] global AABB enclosing the set of input primitives
  74                  *      \return         true if success
  75                  */
  76                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  77                 virtual                                         bool                    ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box)   const   = 0;
  78
  79                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  80                 /**
  81                  *      Computes the splitting value along a given axis for a given primitive.
  82                  *      \param          index                   [in] index of the primitive to split
  83                  *      \param          axis                    [in] axis index (0,1,2)
  84                  *      \return         splitting value
  85                  */
  86                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  87                 virtual                                         float                   GetSplittingValue(udword index, udword axis)    const   = 0;
  88
  89                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  90                 /**
  91                  *      Computes the splitting value along a given axis for a given node.
  92                  *      \param          primitives              [in] list of indices of primitives
  93                  *      \param          nb_prims                [in] number of indices
  94                  *      \param          global_box              [in] global AABB enclosing the set of input primitives
  95                  *      \param          axis                    [in] axis index (0,1,2)
  96                  *      \return         splitting value
  97                  */
  98                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  99                 virtual                                         float                   GetSplittingValue(const udword* primitives, udword nb_prims, const AABB& global_box, udword axis)       const
 100                                                                                                         {
 101                                                                                                                 // Default split value = middle of the axis (using only the box)
 102                                                                                                                 return global_box.GetCenter(axis);
 103                                                                                                         }
 104
 105                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 106                 /**
 107                  *      Validates node subdivision. This is called each time a node is considered for subdivision, during tree building.
 108                  *      \param          primitives              [in] list of indices of primitives
 109                  *      \param          nb_prims                [in] number of indices
 110                  *      \param          global_box              [in] global AABB enclosing the set of input primitives
 111                  *      \return         TRUE if the node should be subdivised
 112                  */
 113                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 114                 virtual                                         BOOL                    ValidateSubdivision(const udword* primitives, udword nb_prims, const AABB& global_box)
 115                                                                                                         {
 116                                                                                                                 // Check the user-defined limit
 117                                                                                                                 if(nb_prims<=mSettings.mLimit)  return FALSE;
 118
 119                                                                                                                 return TRUE;
 120                                                                                                         }
 121
 122                                                                         BuildSettings   mSettings;                      //!< Splitting rules & split limit [Opcode 1.3]
 123                                                                         udword                  mNbPrimitives;          //!< Total number of primitives.
 124                                                                         void*                   mNodeBase;                      //!< Address of node pool [Opcode 1.3]
 125                 // Stats
 126                 inline_                                         void                    SetCount(udword nb)                             { mCount=nb;                            }
 127                 inline_                                         void                    IncreaseCount(udword nb)                { mCount+=nb;                           }
 128                 inline_                                         udword                  GetCount()                              const   { return mCount;                        }
 129                 inline_                                         void                    SetNbInvalidSplits(udword nb)   { mNbInvalidSplits=nb;          }
 130                 inline_                                         void                    IncreaseNbInvalidSplits()               { mNbInvalidSplits++;           }
 131                 inline_                                         udword                  GetNbInvalidSplits()    const   { return mNbInvalidSplits;      }
 132
 133                 private:
 134                                                                         udword                  mCount;                         //!< Stats: number of nodes created
 135                                                                         udword                  mNbInvalidSplits;       //!< Stats: number of invalid splits
 136         };
 137
 138         class OPCODE_API AABBTreeOfVerticesBuilder : public AABBTreeBuilder
 139         {
 140                 public:
 141                 //! Constructor
 142                                                                                                         AABBTreeOfVerticesBuilder() : mVertexArray(null)        {}
 143                 //! Destructor
 144                 virtual                                                                         ~AABBTreeOfVerticesBuilder()                                            {}
 145
 146                 override(AABBTreeBuilder)       bool                    ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box)   const;
 147                 override(AABBTreeBuilder)       float                   GetSplittingValue(udword index, udword axis)                                                                    const;
 148                 override(AABBTreeBuilder)       float                   GetSplittingValue(const udword* primitives, udword nb_prims, const AABB& global_box, udword axis)       const;
 149
 150                 const                                           Point*                  mVertexArray;           //!< Shortcut to an app-controlled array of vertices.
 151         };
 152
 153         class OPCODE_API AABBTreeOfAABBsBuilder : public AABBTreeBuilder
 154         {
 155                 public:
 156                 //! Constructor
 157                                                                                                         AABBTreeOfAABBsBuilder() : mAABBArray(null)     {}
 158                 //! Destructor
 159                 virtual                                                                         ~AABBTreeOfAABBsBuilder()                                       {}
 160
 161                 override(AABBTreeBuilder)       bool                    ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box)   const;
 162                 override(AABBTreeBuilder)       float                   GetSplittingValue(udword index, udword axis)                                                                    const;
 163
 164                 const                                           AABB*                   mAABBArray;                     //!< Shortcut to an app-controlled array of AABBs.
 165         };
 166
 167         class OPCODE_API AABBTreeOfTrianglesBuilder : public AABBTreeBuilder
 168         {
 169                 public:
 170                 //! Constructor
 171                                                                                                         AABBTreeOfTrianglesBuilder() : mIMesh(null)                                                                             {}
 172                 //! Destructor
 173                 virtual                                                                         ~AABBTreeOfTrianglesBuilder()                                                                                                   {}
 174
 175                 override(AABBTreeBuilder)       bool                    ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box)   const;
 176                 override(AABBTreeBuilder)       float                   GetSplittingValue(udword index, udword axis)                                                                    const;
 177                 override(AABBTreeBuilder)       float                   GetSplittingValue(const udword* primitives, udword nb_prims, const AABB& global_box, udword axis)       const;
 178
 179                 const                           MeshInterface*                  mIMesh;                 //!< Shortcut to an app-controlled mesh interface
 180         };
 181
 182 #endif // __OPC_TREEBUILDERS_H__