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