| 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 | { |
|---|
| 41 | 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 |
|---|
| 51 | AABBTreeBuilder() : |
|---|
| 52 | mNbPrimitives(0), |
|---|
| 53 | mNodeBase(null), |
|---|
| 54 | mCount(0), |
|---|
| 55 | mNbInvalidSplits(0) {} |
|---|
| 56 | //! Destructor |
|---|
| 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 udword* 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 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
|---|
| 90 | virtual float GetSplittingValue(const udword* 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 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
|---|
| 105 | virtual BOOL ValidateSubdivision(const udword* 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 |
|---|
| 117 | inline_ void SetCount(udword nb) { mCount=nb; } |
|---|
| 118 | inline_ void IncreaseCount(udword nb) { mCount+=nb; } |
|---|
| 119 | inline_ udword GetCount() const { return mCount; } |
|---|
| 120 | inline_ void SetNbInvalidSplits(udword nb) { mNbInvalidSplits=nb; } |
|---|
| 121 | inline_ void IncreaseNbInvalidSplits() { mNbInvalidSplits++; } |
|---|
| 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 |
|---|
| 133 | AABBTreeOfVerticesBuilder() : mVertexArray(null) {} |
|---|
| 134 | //! Destructor |
|---|
| 135 | virtual ~AABBTreeOfVerticesBuilder() {} |
|---|
| 136 | |
|---|
| 137 | override(AABBTreeBuilder) bool ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box) const; |
|---|
| 138 | override(AABBTreeBuilder) float GetSplittingValue(udword index, udword axis) const; |
|---|
| 139 | override(AABBTreeBuilder) float GetSplittingValue(const udword* 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 |
|---|
| 148 | AABBTreeOfAABBsBuilder() : mAABBArray(null) {} |
|---|
| 149 | //! Destructor |
|---|
| 150 | virtual ~AABBTreeOfAABBsBuilder() {} |
|---|
| 151 | |
|---|
| 152 | override(AABBTreeBuilder) bool ComputeGlobalBox(const udword* 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 |
|---|
| 162 | AABBTreeOfTrianglesBuilder() : mIMesh(null) {} |
|---|
| 163 | //! Destructor |
|---|
| 164 | virtual ~AABBTreeOfTrianglesBuilder() {} |
|---|
| 165 | |
|---|
| 166 | override(AABBTreeBuilder) bool ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box) const; |
|---|
| 167 | override(AABBTreeBuilder) float GetSplittingValue(udword index, udword axis) const; |
|---|
| 168 | override(AABBTreeBuilder) float GetSplittingValue(const udword* 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__ |
|---|
