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