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.cpp
13 * \author Pierre Terdiman
14 * \date March, 20, 2001
15 */
16 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
17
18 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
19 /**
20 * A builder for AABB-trees of vertices.
21 *
22 * \class AABBTreeOfVerticesBuilder
23 * \author Pierre Terdiman
24 * \version 1.3
25 * \date March, 20, 2001
26 */
27 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
28
29 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
30 /**
31 * A builder for AABB-trees of AABBs.
32 *
33 * \class AABBTreeOfAABBsBuilder
34 * \author Pierre Terdiman
35 * \version 1.3
36 * \date March, 20, 2001
37 */
38 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
39
40 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
41 /**
42 * A builder for AABB-trees of triangles.
43 *
44 * \class AABBTreeOfTrianglesBuilder
45 * \author Pierre Terdiman
46 * \version 1.3
47 * \date March, 20, 2001
48 */
49 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
50
51 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
52 // Precompiled Header
53 #include "Stdafx.h"
54
55 using namespace Opcode;
56
57 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
58 /**
59 * Computes the AABB of a set of primitives.
60 * \param primitives [in] list of indices of primitives
61 * \param nb_prims [in] number of indices
62 * \param global_box [out] global AABB enclosing the set of input primitives
63 * \return true if success
64 */
65 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ComputeGlobalBox(const dTriIndex * primitives,udword nb_prims,AABB & global_box) const66 bool AABBTreeOfAABBsBuilder::ComputeGlobalBox(const dTriIndex* primitives, udword nb_prims, AABB& global_box) const
67 {
68 // Checkings
69 if(!primitives || !nb_prims) return false;
70
71 // Initialize global box
72 global_box = mAABBArray[primitives[0]];
73
74 // Loop through boxes
75 for(udword i=1;i<nb_prims;i++)
76 {
77 // Update global box
78 global_box.Add(mAABBArray[primitives[i]]);
79 }
80 return true;
81 }
82
83 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
84 /**
85 * Computes the splitting value along a given axis for a given primitive.
86 * \param index [in] index of the primitive to split
87 * \param axis [in] axis index (0,1,2)
88 * \return splitting value
89 */
90 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
GetSplittingValue(udword index,udword axis) const91 float AABBTreeOfAABBsBuilder::GetSplittingValue(udword index, udword axis) const
92 {
93 // For an AABB, the splitting value is the middle of the given axis,
94 // i.e. the corresponding component of the center point
95 return mAABBArray[index].GetCenter(axis);
96 }
97
98 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
99 /**
100 * Computes the splitting value along a given axis for a given primitive.
101 * \param index [in] index of the primitive to split
102 * \return splitting value
103 */
104 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
GetSplittingValues(udword index) const105 Point AABBTreeOfAABBsBuilder::GetSplittingValues(udword index) const
106 {
107 // For an AABB, the splitting value is the middle of the given axis,
108 // i.e. the corresponding component of the center point
109 Point p;
110 mAABBArray[index].GetCenter(p);
111 return p;
112 }
113
114 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
115 /**
116 * Computes the AABB of a set of primitives.
117 * \param primitives [in] list of indices of primitives
118 * \param nb_prims [in] number of indices
119 * \param global_box [out] global AABB enclosing the set of input primitives
120 * \return true if success
121 */
122 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ComputeGlobalBox(const dTriIndex * primitives,udword nb_prims,AABB & global_box) const123 bool AABBTreeOfTrianglesBuilder::ComputeGlobalBox(const dTriIndex* primitives, udword nb_prims, AABB& global_box) const
124 {
125 // Checkings
126 if(!primitives || !nb_prims) return false;
127
128 // Initialize global box
129 Point Min(MAX_FLOAT, MAX_FLOAT, MAX_FLOAT);
130 Point Max(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);
131
132 // Loop through triangles
133 VertexPointers VP;
134 ConversionArea VC;
135 while(nb_prims--)
136 {
137 // Get current triangle-vertices
138 mIMesh->GetTriangle(VP, *primitives++, VC);
139 // Update global box
140 Min.Min(*VP.Vertex[0]).Min(*VP.Vertex[1]).Min(*VP.Vertex[2]);
141 Max.Max(*VP.Vertex[0]).Max(*VP.Vertex[1]).Max(*VP.Vertex[2]);
142 }
143 global_box.SetMinMax(Min, Max);
144 return true;
145 }
146
147 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
148 /**
149 * Computes the splitting value along a given axis for a given primitive.
150 * \param index [in] index of the primitive to split
151 * \return splitting value
152 */
153 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
GetSplittingValues(udword index) const154 Point AABBTreeOfTrianglesBuilder::GetSplittingValues(udword index) const
155 {
156 VertexPointers VP;
157 ConversionArea VC;
158 mIMesh->GetTriangle(VP, index, VC);
159
160 return ( *VP.Vertex[0] + *VP.Vertex[1] + *VP.Vertex[2] ) * INV3;
161 }
162
163
164 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
165 /**
166 * Computes the splitting value along a given axis for a given primitive.
167 * \param index [in] index of the primitive to split
168 * \param axis [in] axis index (0,1,2)
169 * \return splitting value
170 */
171 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
GetSplittingValue(udword index,udword axis) const172 float AABBTreeOfTrianglesBuilder::GetSplittingValue(udword index, udword axis) const
173 {
174 /* // Compute center of triangle
175 Point Center;
176 mTriList[index].Center(mVerts, Center);
177 // Return value
178 return Center[axis];*/
179
180 // Compute correct component from center of triangle
181 // return (mVerts[mTriList[index].mVRef[0]][axis]
182 // +mVerts[mTriList[index].mVRef[1]][axis]
183 // +mVerts[mTriList[index].mVRef[2]][axis])*INV3;
184
185 VertexPointers VP;
186 ConversionArea VC;
187 mIMesh->GetTriangle(VP, index, VC);
188
189 // Compute correct component from center of triangle
190 return ((*VP.Vertex[0])[axis]
191 +(*VP.Vertex[1])[axis]
192 +(*VP.Vertex[2])[axis])*INV3;
193 }
194
195 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
196 /**
197 * Computes the splitting value along a given axis for a given node.
198 * \param primitives [in] list of indices of primitives
199 * \param nb_prims [in] number of indices
200 * \param global_box [in] global AABB enclosing the set of input primitives
201 * \param axis [in] axis index (0,1,2)
202 * \return splitting value
203 */
204 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
GetSplittingValue(const dTriIndex * primitives,udword nb_prims,const AABB & global_box,udword axis) const205 float AABBTreeOfTrianglesBuilder::GetSplittingValue(const dTriIndex* primitives, udword nb_prims, const AABB& global_box, udword axis) const
206 {
207 if(mSettings.mRules&SPLIT_GEOM_CENTER)
208 {
209 // Loop through triangles
210 float SplitValue = 0.0f;
211 VertexPointers VP;
212 ConversionArea VC;
213 for(udword i=0;i<nb_prims;i++)
214 {
215 // Get current triangle-vertices
216 mIMesh->GetTriangle(VP, primitives[i], VC);
217 // Update split value
218 SplitValue += (*VP.Vertex[0])[axis];
219 SplitValue += (*VP.Vertex[1])[axis];
220 SplitValue += (*VP.Vertex[2])[axis];
221 }
222 return SplitValue / float(nb_prims*3);
223 }
224 else return AABBTreeBuilder::GetSplittingValue(primitives, nb_prims, global_box, axis);
225 }
226
227 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
228 /**
229 * Computes the AABB of a set of primitives.
230 * \param primitives [in] list of indices of primitives
231 * \param nb_prims [in] number of indices
232 * \param global_box [out] global AABB enclosing the set of input primitives
233 * \return true if success
234 */
235 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ComputeGlobalBox(const dTriIndex * primitives,udword nb_prims,AABB & global_box) const236 bool AABBTreeOfVerticesBuilder::ComputeGlobalBox(const dTriIndex* primitives, udword nb_prims, AABB& global_box) const
237 {
238 // Checkings
239 if(!primitives || !nb_prims) return false;
240
241 // Initialize global box
242 global_box.SetEmpty();
243
244 // Loop through vertices
245 for(udword i=0;i<nb_prims;i++)
246 {
247 // Update global box
248 global_box.Extend(mVertexArray[primitives[i]]);
249 }
250 return true;
251 }
252
253 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
254 /**
255 * Computes the splitting value along a given axis for a given primitive.
256 * \param index [in] index of the primitive to split
257 * \param axis [in] axis index (0,1,2)
258 * \return splitting value
259 */
260 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
GetSplittingValue(udword index,udword axis) const261 float AABBTreeOfVerticesBuilder::GetSplittingValue(udword index, udword axis) const
262 {
263 // For a vertex, the splitting value is simply the vertex coordinate.
264 return mVertexArray[index][axis];
265 }
266
267
268 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
269 /**
270 * Computes the splitting value along a given axis for a given primitive.
271 * \param index [in] index of the primitive to split
272 * \param axis [in] axis index (0,1,2)
273 * \return splitting value
274 */
275 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
GetSplittingValues(udword index) const276 Point AABBTreeOfVerticesBuilder::GetSplittingValues(udword index) const
277 {
278 // For a vertex, the splitting value is simply the vertex coordinate.
279 return mVertexArray[index];
280 }
281
282 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
283 /**
284 * Computes the splitting value along a given axis for a given node.
285 * \param primitives [in] list of indices of primitives
286 * \param nb_prims [in] number of indices
287 * \param global_box [in] global AABB enclosing the set of input primitives
288 * \param axis [in] axis index (0,1,2)
289 * \return splitting value
290 */
291 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
GetSplittingValue(const dTriIndex * primitives,udword nb_prims,const AABB & global_box,udword axis) const292 float AABBTreeOfVerticesBuilder::GetSplittingValue(const dTriIndex* primitives, udword nb_prims, const AABB& global_box, udword axis) const
293 {
294 if(mSettings.mRules&SPLIT_GEOM_CENTER)
295 {
296 // Loop through vertices
297 float SplitValue = 0.0f;
298 for(udword i=0;i<nb_prims;i++)
299 {
300 // Update split value
301 SplitValue += mVertexArray[primitives[i]][axis];
302 }
303 return SplitValue / float(nb_prims);
304 }
305 else return AABBTreeBuilder::GetSplittingValue(primitives, nb_prims, global_box, axis);
306 }
307