?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Cosmetic: Premake script fixed to avoid adding outest.cpp to the project being generated
[ode.git] / OPCODE / OPC_TreeBuilders.h
blob9e75627d777dcbde8182b4fc9fe944e539570fdb
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 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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
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
118 inline_ void SetCount(udword nb) { mCount=nb; }
119 inline_ void IncreaseCount(udword nb) { mCount+=nb; }
120 inline_ udword GetCount() const { return mCount; }
121 inline_ void SetNbInvalidSplits(udword nb) { mNbInvalidSplits=nb; }
122 inline_ void IncreaseNbInvalidSplits() { mNbInvalidSplits++; }
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
134 AABBTreeOfVerticesBuilder() : mVertexArray(null) {}
135 //! Destructor
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
150 AABBTreeOfAABBsBuilder() : mAABBArray(null) {}
151 //! Destructor
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
165 AABBTreeOfTrianglesBuilder() : mIMesh(null) {}
166 //! Destructor
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__
Open Dynamics Engine