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 AABB of a set of primitives.
101 * \param primitives [in] list of indices of primitives
102 * \param nb_prims [in] number of indices
103 * \param global_box [out] global AABB enclosing the set of input primitives
104 * \return true if success
105 */
106 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ComputeGlobalBox(const dTriIndex * primitives,udword nb_prims,AABB & global_box) const107 bool AABBTreeOfTrianglesBuilder::ComputeGlobalBox(const dTriIndex* primitives, udword nb_prims, AABB& global_box) const
108 {
109 // Checkings
110 if(!primitives || !nb_prims) return false;
111
112 // Initialize global box
113 Point Min(MAX_FLOAT, MAX_FLOAT, MAX_FLOAT);
114 Point Max(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);
115
116 // Loop through triangles
117 VertexPointers VP;
118 ConversionArea VC;
119 while(nb_prims--)
120 {
121 // Get current triangle-vertices
122 mIMesh->GetTriangle(VP, *primitives++, VC);
123 // Update global box
124 Min.Min(*VP.Vertex[0]).Min(*VP.Vertex[1]).Min(*VP.Vertex[2]);
125 Max.Max(*VP.Vertex[0]).Max(*VP.Vertex[1]).Max(*VP.Vertex[2]);
126 }
127 global_box.SetMinMax(Min, Max);
128 return true;
129 }
130
131 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
132 /**
133 * Computes the splitting value along a given axis for a given primitive.
134 * \param index [in] index of the primitive to split
135 * \param axis [in] axis index (0,1,2)
136 * \return splitting value
137 */
138 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
GetSplittingValue(udword index,udword axis) const139 float AABBTreeOfTrianglesBuilder::GetSplittingValue(udword index, udword axis) const
140 {
141 /* // Compute center of triangle
142 Point Center;
143 mTriList[index].Center(mVerts, Center);
144 // Return value
145 return Center[axis];*/
146
147 // Compute correct component from center of triangle
148 // return (mVerts[mTriList[index].mVRef[0]][axis]
149 // +mVerts[mTriList[index].mVRef[1]][axis]
150 // +mVerts[mTriList[index].mVRef[2]][axis])*INV3;
151
152 VertexPointers VP;
153 ConversionArea VC;
154 mIMesh->GetTriangle(VP, index, VC);
155
156 // Compute correct component from center of triangle
157 return ((*VP.Vertex[0])[axis]
158 +(*VP.Vertex[1])[axis]
159 +(*VP.Vertex[2])[axis])*INV3;
160 }
161
162 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
163 /**
164 * Computes the splitting value along a given axis for a given node.
165 * \param primitives [in] list of indices of primitives
166 * \param nb_prims [in] number of indices
167 * \param global_box [in] global AABB enclosing the set of input primitives
168 * \param axis [in] axis index (0,1,2)
169 * \return splitting value
170 */
171 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
GetSplittingValue(const dTriIndex * primitives,udword nb_prims,const AABB & global_box,udword axis) const172 float AABBTreeOfTrianglesBuilder::GetSplittingValue(const dTriIndex* primitives, udword nb_prims, const AABB& global_box, udword axis) const
173 {
174 if(mSettings.mRules&SPLIT_GEOM_CENTER)
175 {
176 // Loop through triangles
177 float SplitValue = 0.0f;
178 VertexPointers VP;
179 ConversionArea VC;
180 for(udword i=0;i<nb_prims;i++)
181 {
182 // Get current triangle-vertices
183 mIMesh->GetTriangle(VP, primitives[i], VC);
184 // Update split value
185 SplitValue += (*VP.Vertex[0])[axis];
186 SplitValue += (*VP.Vertex[1])[axis];
187 SplitValue += (*VP.Vertex[2])[axis];
188 }
189 return SplitValue / float(nb_prims*3);
190 }
191 else return AABBTreeBuilder::GetSplittingValue(primitives, nb_prims, global_box, axis);
192 }
193
194 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
195 /**
196 * Computes the AABB of a set of primitives.
197 * \param primitives [in] list of indices of primitives
198 * \param nb_prims [in] number of indices
199 * \param global_box [out] global AABB enclosing the set of input primitives
200 * \return true if success
201 */
202 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ComputeGlobalBox(const dTriIndex * primitives,udword nb_prims,AABB & global_box) const203 bool AABBTreeOfVerticesBuilder::ComputeGlobalBox(const dTriIndex* primitives, udword nb_prims, AABB& global_box) const
204 {
205 // Checkings
206 if(!primitives || !nb_prims) return false;
207
208 // Initialize global box
209 global_box.SetEmpty();
210
211 // Loop through vertices
212 for(udword i=0;i<nb_prims;i++)
213 {
214 // Update global box
215 global_box.Extend(mVertexArray[primitives[i]]);
216 }
217 return true;
218 }
219
220 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
221 /**
222 * Computes the splitting value along a given axis for a given primitive.
223 * \param index [in] index of the primitive to split
224 * \param axis [in] axis index (0,1,2)
225 * \return splitting value
226 */
227 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
GetSplittingValue(udword index,udword axis) const228 float AABBTreeOfVerticesBuilder::GetSplittingValue(udword index, udword axis) const
229 {
230 // For a vertex, the splitting value is simply the vertex coordinate.
231 return mVertexArray[index][axis];
232 }
233
234 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
235 /**
236 * Computes the splitting value along a given axis for a given node.
237 * \param primitives [in] list of indices of primitives
238 * \param nb_prims [in] number of indices
239 * \param global_box [in] global AABB enclosing the set of input primitives
240 * \param axis [in] axis index (0,1,2)
241 * \return splitting value
242 */
243 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
GetSplittingValue(const dTriIndex * primitives,udword nb_prims,const AABB & global_box,udword axis) const244 float AABBTreeOfVerticesBuilder::GetSplittingValue(const dTriIndex* primitives, udword nb_prims, const AABB& global_box, udword axis) const
245 {
246 if(mSettings.mRules&SPLIT_GEOM_CENTER)
247 {
248 // Loop through vertices
249 float SplitValue = 0.0f;
250 for(udword i=0;i<nb_prims;i++)
251 {
252 // Update split value
253 SplitValue += mVertexArray[primitives[i]][axis];
254 }
255 return SplitValue / float(nb_prims);
256 }
257 else return AABBTreeBuilder::GetSplittingValue(primitives, nb_prims, global_box, axis);
258 }
259