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) {} 42 43 udword mLimit; //!< Limit number of primitives / node. If limit is 1, build a complete tree (2*N-1 nodes) 44 udword mRules; //!< Building/Splitting rules (a combination of SplittingRules flags) 45 }; 46 47 class OPCODE_API AABBTreeBuilder 48 { 49 public: 50 //! Constructor AABBTreeBuilder()51 AABBTreeBuilder() : 52 mNbPrimitives(0), 53 mNodeBase(null), 54 mCount(0), 55 mNbInvalidSplits(0) {} 56 //! Destructor ~AABBTreeBuilder()57 virtual ~AABBTreeBuilder() {} 58 59 /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 60 /** 61 * Computes the AABB of a set of primitives. 62 * \param primitives [in] list of indices of primitives 63 * \param nb_prims [in] number of indices 64 * \param global_box [out] global AABB enclosing the set of input primitives 65 * \return true if success 66 */ 67 /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 68 virtual bool ComputeGlobalBox(const dTriIndex* primitives, udword nb_prims, AABB& global_box) const = 0; 69 70 /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 71 /** 72 * Computes the splitting value along a given axis for a given primitive. 73 * \param index [in] index of the primitive to split 74 * \param axis [in] axis index (0,1,2) 75 * \return splitting value 76 */ 77 /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 78 virtual float GetSplittingValue(udword index, udword axis) const = 0; 79 80 /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 81 /** 82 * Computes the splitting value along a given axis for a given node. 83 * \param primitives [in] list of indices of primitives 84 * \param nb_prims [in] number of indices 85 * \param global_box [in] global AABB enclosing the set of input primitives 86 * \param axis [in] axis index (0,1,2) 87 * \return splitting value 88 */ 89 /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// GetSplittingValue(const dTriIndex * primitives,udword nb_prims,const AABB & global_box,udword axis)90 virtual float GetSplittingValue(const dTriIndex* primitives, udword nb_prims, const AABB& global_box, udword axis) const 91 { 92 // Default split value = middle of the axis (using only the box) 93 return global_box.GetCenter(axis); 94 } 95 96 /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 97 /** 98 * Validates node subdivision. This is called each time a node is considered for subdivision, during tree building. 99 * \param primitives [in] list of indices of primitives 100 * \param nb_prims [in] number of indices 101 * \param global_box [in] global AABB enclosing the set of input primitives 102 * \return TRUE if the node should be subdivised 103 */ 104 /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ValidateSubdivision(const dTriIndex * primitives,udword nb_prims,const AABB & global_box)105 virtual BOOL ValidateSubdivision(const dTriIndex* primitives, udword nb_prims, const AABB& global_box) 106 { 107 // Check the user-defined limit 108 if(nb_prims<=mSettings.mLimit) return FALSE; 109 110 return TRUE; 111 } 112 113 BuildSettings mSettings; //!< Splitting rules & split limit [Opcode 1.3] 114 udword mNbPrimitives; //!< Total number of primitives. 115 void* mNodeBase; //!< Address of node pool [Opcode 1.3] 116 // Stats SetCount(udword nb)117 inline_ void SetCount(udword nb) { mCount=nb; } IncreaseCount(udword nb)118 inline_ void IncreaseCount(udword nb) { mCount+=nb; } GetCount()119 inline_ udword GetCount() const { return mCount; } SetNbInvalidSplits(udword nb)120 inline_ void SetNbInvalidSplits(udword nb) { mNbInvalidSplits=nb; } IncreaseNbInvalidSplits()121 inline_ void IncreaseNbInvalidSplits() { mNbInvalidSplits++; } GetNbInvalidSplits()122 inline_ udword GetNbInvalidSplits() const { return mNbInvalidSplits; } 123 124 private: 125 udword mCount; //!< Stats: number of nodes created 126 udword mNbInvalidSplits; //!< Stats: number of invalid splits 127 }; 128 129 class OPCODE_API AABBTreeOfVerticesBuilder : public AABBTreeBuilder 130 { 131 public: 132 //! Constructor AABBTreeOfVerticesBuilder()133 AABBTreeOfVerticesBuilder() : mVertexArray(null) {} 134 //! Destructor ~AABBTreeOfVerticesBuilder()135 virtual ~AABBTreeOfVerticesBuilder() {} 136 137 override(AABBTreeBuilder) bool ComputeGlobalBox(const dTriIndex* primitives, udword nb_prims, AABB& global_box) const; 138 override(AABBTreeBuilder) float GetSplittingValue(udword index, udword axis) const; 139 override(AABBTreeBuilder) float GetSplittingValue(const dTriIndex* primitives, udword nb_prims, const AABB& global_box, udword axis) const; 140 141 const Point* mVertexArray; //!< Shortcut to an app-controlled array of vertices. 142 }; 143 144 class OPCODE_API AABBTreeOfAABBsBuilder : public AABBTreeBuilder 145 { 146 public: 147 //! Constructor AABBTreeOfAABBsBuilder()148 AABBTreeOfAABBsBuilder() : mAABBArray(null) {} 149 //! Destructor ~AABBTreeOfAABBsBuilder()150 virtual ~AABBTreeOfAABBsBuilder() {} 151 152 override(AABBTreeBuilder) bool ComputeGlobalBox(const dTriIndex* primitives, udword nb_prims, AABB& global_box) const; 153 override(AABBTreeBuilder) float GetSplittingValue(udword index, udword axis) const; 154 155 const AABB* mAABBArray; //!< Shortcut to an app-controlled array of AABBs. 156 }; 157 158 class OPCODE_API AABBTreeOfTrianglesBuilder : public AABBTreeBuilder 159 { 160 public: 161 //! Constructor AABBTreeOfTrianglesBuilder()162 AABBTreeOfTrianglesBuilder() : mIMesh(null) {} 163 //! Destructor ~AABBTreeOfTrianglesBuilder()164 virtual ~AABBTreeOfTrianglesBuilder() {} 165 166 override(AABBTreeBuilder) bool ComputeGlobalBox(const dTriIndex* primitives, udword nb_prims, AABB& global_box) const; 167 override(AABBTreeBuilder) float GetSplittingValue(udword index, udword axis) const; 168 override(AABBTreeBuilder) float GetSplittingValue(const dTriIndex* primitives, udword nb_prims, const AABB& global_box, udword axis) const; 169 170 const MeshInterface* mIMesh; //!< Shortcut to an app-controlled mesh interface 171 }; 172 173 #endif // __OPC_TREEBUILDERS_H__ 174