aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/ode-0.9/OPCODE/OPC_TreeBuilders.h
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/ode-0.9/OPCODE/OPC_TreeBuilders.h')
-rw-r--r--libraries/ode-0.9/OPCODE/OPC_TreeBuilders.h173
1 files changed, 173 insertions, 0 deletions
diff --git a/libraries/ode-0.9/OPCODE/OPC_TreeBuilders.h b/libraries/ode-0.9/OPCODE/OPC_TreeBuilders.h
new file mode 100644
index 0000000..b9a2a98
--- /dev/null
+++ b/libraries/ode-0.9/OPCODE/OPC_TreeBuilders.h
@@ -0,0 +1,173 @@
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__
generated by cgit v1.1 at 2024-11-11 19:05:32 +0000