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