OPC_HybridModel.cpp
Go to the documentation of this file.
1 /*
3  * OPCODE - Optimized Collision Detection
4  * Copyright (C) 2001 Pierre Terdiman
5  * Homepage: http://www.codercorner.com/Opcode.htm
6  */
8 
10 
16 
19 
81 
84 // Precompiled Header
85 #include "Stdafx.h"
86 
87 using namespace Opcode;
88 
90 
95  mNbLeaves (0),
96  mNbPrimitives (0),
97  mTriangles (null),
98  mIndices (null)
99 {
100 }
101 
103 
108 {
109  Release();
110 }
111 
113 
118 {
119  ReleaseBase();
122  mNbLeaves = 0;
123  mNbPrimitives = 0;
124 }
125 
126  struct Internal
127  {
129  {
130  mNbLeaves = 0;
131  mLeaves = null;
132  mTriangles = null;
133  mBase = null;
134  }
136  {
137  DELETEARRAY(mLeaves);
138  }
139 
143  const udword* mBase;
144  };
145 
147 
154 {
155  // 1) Checkings
156  if(!create.mIMesh || !create.mIMesh->IsValid()) return false;
157 
158  // Look for degenerate faces.
159  udword NbDegenerate = create.mIMesh->CheckTopology();
160  if(NbDegenerate) Log("OPCODE WARNING: found %d degenerate faces in model! Collision might report wrong results!\n", NbDegenerate);
161  // We continue nonetheless....
162 
163  Release(); // Make sure previous tree has been discarded
164 
165  // 1-1) Setup mesh interface automatically
166  SetMeshInterface(create.mIMesh);
167 
168  bool Status = false;
169  AABBTree* LeafTree = null;
170  Internal Data;
171 
172  // 2) Build a generic AABB Tree.
173  mSource = new AABBTree;
175 
176  // 2-1) Setup a builder. Our primitives here are triangles from input mesh,
177  // so we use an AABBTreeOfTrianglesBuilder.....
178  {
180  TB.mIMesh = create.mIMesh;
181  TB.mNbPrimitives = create.mIMesh->GetNbTriangles();
182  TB.mSettings = create.mSettings;
183  TB.mSettings.mLimit = 16; // ### Hardcoded, but maybe we could let the user choose 8 / 16 / 32 ...
184  if(!mSource->Build(&TB)) goto FreeAndExit;
185  }
186 
187  // 2-2) Here's the trick : create *another* AABB tree using the leaves of the first one (which are boxes, this time)
188  struct Local
189  {
190  // A callback to count leaf nodes
191  static bool CountLeaves(const AABBTreeNode* current, udword depth, void* user_data)
192  {
193  if(current->IsLeaf())
194  {
195  Internal* Data = (Internal*)user_data;
196  Data->mNbLeaves++;
197  }
198  return true;
199  }
200 
201  // A callback to setup leaf nodes in our internal structures
202  static bool SetupLeafData(const AABBTreeNode* current, udword depth, void* user_data)
203  {
204  if(current->IsLeaf())
205  {
206  Internal* Data = (Internal*)user_data;
207 
208  // Get current leaf's box
209  Data->mLeaves[Data->mNbLeaves] = *current->GetAABB();
210 
211  // Setup leaf data
212  udword Index = (udword(current->GetPrimitives()) - udword(Data->mBase))/sizeof(udword);
213  Data->mTriangles[Data->mNbLeaves].SetData(current->GetNbPrimitives(), Index);
214 
215  Data->mNbLeaves++;
216  }
217  return true;
218  }
219  };
220 
221  // Walk the tree & count number of leaves
222  Data.mNbLeaves = 0;
223  mSource->Walk(Local::CountLeaves, &Data);
224  mNbLeaves = Data.mNbLeaves; // Keep track of it
225 
226  // Special case for 1-leaf meshes
227  if(mNbLeaves==1)
228  {
230  Status = true;
231  goto FreeAndExit;
232  }
233 
234  // Allocate our structures
235  Data.mLeaves = new AABB[Data.mNbLeaves]; CHECKALLOC(Data.mLeaves);
237 
238  // Walk the tree again & setup leaf data
239  Data.mTriangles = mTriangles;
240  Data.mBase = mSource->GetIndices();
241  Data.mNbLeaves = 0; // Reset for incoming walk
242  mSource->Walk(Local::SetupLeafData, &Data);
243 
244  // Handle source indices
245  {
246  bool MustKeepIndices = true;
247  if(create.mCanRemap)
248  {
249  // We try to get rid of source indices (saving more ram!) by reorganizing triangle arrays...
250  // Remap can fail when we use callbacks => keep track of indices in that case (it still
251  // works, only using more memory)
253  {
254  MustKeepIndices = false;
255  }
256  }
257 
258  if(MustKeepIndices)
259  {
260  // Keep track of source indices (from vanilla tree)
264  }
265  }
266 
267  // Now, create our optimized tree using previous leaf nodes
268  LeafTree = new AABBTree;
269  CHECKALLOC(LeafTree);
270  {
271  AABBTreeOfAABBsBuilder TB; // Now using boxes !
272  TB.mSettings = create.mSettings;
273  TB.mSettings.mLimit = 1; // We now want a complete tree so that we can "optimize" it
274  TB.mNbPrimitives = Data.mNbLeaves;
275  TB.mAABBArray = Data.mLeaves;
276  if(!LeafTree->Build(&TB)) goto FreeAndExit;
277  }
278 
279  // 3) Create an optimized tree according to user-settings
280  if(!CreateTree(create.mNoLeaf, create.mQuantized)) goto FreeAndExit;
281 
282  // 3-2) Create optimized tree
283  if(!mTree->Build(LeafTree)) goto FreeAndExit;
284 
285  // Finally ok...
286  Status = true;
287 
288 FreeAndExit: // Allow me this one...
289  DELETESINGLE(LeafTree);
290 
291  // 3-3) Delete generic tree if needed
292  if(!create.mKeepOriginal) DELETESINGLE(mSource);
293 
294  return Status;
295 }
296 
298 
304 {
305  udword UsedBytes = 0;
306  if(mTree) UsedBytes += mTree->GetUsedBytes();
307  if(mIndices) UsedBytes += mNbPrimitives * sizeof(udword); // mIndices
308  if(mTriangles) UsedBytes += mNbLeaves * sizeof(LeafTriangles); // mTriangles
309  return UsedBytes;
310 }
311 
313 {
314  // Compute triangle's AABB = a leaf box
315 #ifdef OPC_USE_FCOMI // a 15% speedup on my machine, not much
316  min.x = FCMin3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
317  max.x = FCMax3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
318 
319  min.y = FCMin3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
320  max.y = FCMax3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
321 
322  min.z = FCMin3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
323  max.z = FCMax3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
324 #else
325  min = *vp.Vertex[0];
326  max = *vp.Vertex[0];
327  min.Min(*vp.Vertex[1]);
328  max.Max(*vp.Vertex[1]);
329  min.Min(*vp.Vertex[2]);
330  max.Max(*vp.Vertex[2]);
331 #endif
332 }
333 
335 
341 bool HybridModel::Refit()
343 {
344  if(!mIMesh) return false;
345  if(!mTree) return false;
346 
347  if(IsQuantized()) return false;
348  if(HasLeafNodes()) return false;
349 
350  const LeafTriangles* LT = GetLeafTriangles();
351  const udword* Indices = GetIndices();
352 
353  // Bottom-up update
354  VertexPointers VP;
355  Point Min,Max;
356  Point Min_,Max_;
357  udword Index = mTree->GetNbNodes();
358  AABBNoLeafNode* Nodes = (AABBNoLeafNode*)((AABBNoLeafTree*)mTree)->GetNodes();
359  while(Index--)
360  {
361  AABBNoLeafNode& Current = Nodes[Index];
362 
363  if(Current.HasPosLeaf())
364  {
365  const LeafTriangles& CurrentLeaf = LT[Current.GetPosPrimitive()];
366 
367  Min.SetPlusInfinity();
368  Max.SetMinusInfinity();
369 
370  Point TmpMin, TmpMax;
371 
372  // Each leaf box has a set of triangles
373  udword NbTris = CurrentLeaf.GetNbTriangles();
374  if(Indices)
375  {
376  const udword* T = &Indices[CurrentLeaf.GetTriangleIndex()];
377 
378  // Loop through triangles and test each of them
379  while(NbTris--)
380  {
381  mIMesh->GetTriangle(VP, *T++);
382  ComputeMinMax(TmpMin, TmpMax, VP);
383  Min.Min(TmpMin);
384  Max.Max(TmpMax);
385  }
386  }
387  else
388  {
389  udword BaseIndex = CurrentLeaf.GetTriangleIndex();
390 
391  // Loop through triangles and test each of them
392  while(NbTris--)
393  {
394  mIMesh->GetTriangle(VP, BaseIndex++);
395  ComputeMinMax(TmpMin, TmpMax, VP);
396  Min.Min(TmpMin);
397  Max.Max(TmpMax);
398  }
399  }
400  }
401  else
402  {
403  const CollisionAABB& CurrentBox = Current.GetPos()->mAABB;
404  CurrentBox.GetMin(Min);
405  CurrentBox.GetMax(Max);
406  }
407 
408  if(Current.HasNegLeaf())
409  {
410  const LeafTriangles& CurrentLeaf = LT[Current.GetNegPrimitive()];
411 
412  Min_.SetPlusInfinity();
413  Max_.SetMinusInfinity();
414 
415  Point TmpMin, TmpMax;
416 
417  // Each leaf box has a set of triangles
418  udword NbTris = CurrentLeaf.GetNbTriangles();
419  if(Indices)
420  {
421  const udword* T = &Indices[CurrentLeaf.GetTriangleIndex()];
422 
423  // Loop through triangles and test each of them
424  while(NbTris--)
425  {
426  mIMesh->GetTriangle(VP, *T++);
427  ComputeMinMax(TmpMin, TmpMax, VP);
428  Min_.Min(TmpMin);
429  Max_.Max(TmpMax);
430  }
431  }
432  else
433  {
434  udword BaseIndex = CurrentLeaf.GetTriangleIndex();
435 
436  // Loop through triangles and test each of them
437  while(NbTris--)
438  {
439  mIMesh->GetTriangle(VP, BaseIndex++);
440  ComputeMinMax(TmpMin, TmpMax, VP);
441  Min_.Min(TmpMin);
442  Max_.Max(TmpMax);
443  }
444  }
445  }
446  else
447  {
448  const CollisionAABB& CurrentBox = Current.GetNeg()->mAABB;
449  CurrentBox.GetMin(Min_);
450  CurrentBox.GetMax(Max_);
451  }
452 #ifdef OPC_USE_FCOMI
453  Min.x = FCMin2(Min.x, Min_.x);
454  Max.x = FCMax2(Max.x, Max_.x);
455  Min.y = FCMin2(Min.y, Min_.y);
456  Max.y = FCMax2(Max.y, Max_.y);
457  Min.z = FCMin2(Min.z, Min_.z);
458  Max.z = FCMax2(Max.z, Max_.z);
459 #else
460  Min.Min(Min_);
461  Max.Max(Max_);
462 #endif
463  Current.mAABB.SetMinMax(Min, Max);
464  }
465  return true;
466 }
virtual udword GetUsedBytes() const =0
virtual udword GetUsedBytes() const =0
inline_ void ComputeMinMax(Point &min, Point &max, const VertexPointers &vp)
inline_ void GetMin(Point &min) const
Get min point of the box.
Definition: Opcode.h:42
inline_ float FCMin2(float a, float b)
A global function to find MIN(a,b) using FCOMI/FCMOV.
Definition: IceFPU.h:244
inline_ void SetData(udword nb, udword index)
Definition: Opcode.h:44
udword mNbLeaves
Special case for 1-node models.
Definition: Opcode.h:48
bool mKeepOriginal
true => keep a copy of the original tree (debug purpose)
Definition: Opcode.h:37
#define null
our own NULL pointer
Definition: IceTypes.h:57
AABBTree * mSource
Original source tree.
Definition: Opcode.h:169
udword mModelCode
Model code = combination of ModelFlag(s)
Definition: Opcode.h:168
inline_ udword GetNbPrimitives() const
Definition: Opcode.h:90
inline_ udword GetNbTriangles() const
Definition: Opcode.h:35
virtual bool Build(const OPCODECREATE &create)=0
static int min(int a, int b)
udword mNbLeaves
Number of leaf nodes in the model.
Definition: Opcode.h:98
#define DELETEARRAY(x)
Deletes an array.
inline_ const udword * GetIndices() const
Definition: Opcode.h:95
#define inline_
inline_ void SetMeshInterface(const MeshInterface *imesh)
Definition: Opcode.h:164
const AABB * mAABBArray
Shortcut to an app-controlled array of AABBs.
Definition: Opcode.h:156
const Point * Vertex[3]
Definition: Opcode.h:26
udword Walk(WalkingCallback callback, void *user_data) const
bool Build(AABBTreeBuilder *builder)
bool mCanRemap
true => allows OPCODE to reorganize client arrays
Definition: Opcode.h:38
Model creation structure.
Definition: Opcode.h:25
bool mQuantized
true => quantize the tree (else use a normal tree)
Definition: Opcode.h:33
Leaf descriptor.
Definition: Opcode.h:25
inline_ Point & SetMinusInfinity()
Definition: OPC_IceHook.h:50
inline_ const udword * GetIndices() const
Catch the indices.
Definition: Opcode.h:125
inline_ const udword * GetPrimitives() const
Definition: Opcode.h:89
inline_ const LeafTriangles * GetLeafTriangles() const
Definition: Opcode.h:87
unsigned int udword
sizeof(udword) must be 4
Definition: IceTypes.h:65
inline_ void GetMax(Point &max) const
Get max point of the box.
Definition: Opcode.h:44
virtual bool Refit()
bool RemapClient(udword nb_indices, const udword *permutation) const
#define DELETESINGLE(x)
Deletes an instance of a class.
#define CHECKALLOC(x)
udword mNbPrimitives
Total number of primitives.
Definition: Opcode.h:115
inline_ float Min() const
Returns MIN(x, y, z);.
Definition: OPC_IceHook.h:200
LeafTriangles * mTriangles
Array of mNbLeaves leaf descriptors.
Definition: Opcode.h:99
inline_ void GetTriangle(VertexPointers &vp, udword index) const
Definition: Opcode.h:119
virtual bool Build(AABBTree *tree)=0
inline_ udword GetNbNodes() const
Definition: Opcode.h:187
udword * mIndices
Array of primitive indices.
Definition: Opcode.h:101
bool mNoLeaf
true => discard leaf nodes (else use a normal tree)
Definition: Opcode.h:32
virtual ~HybridModel()
inline_ Point & SetPlusInfinity()
Definition: OPC_IceHook.h:48
AABBOptimizedTree * mTree
Optimized tree owned by the model.
Definition: Opcode.h:170
inline_ void CopyMemory(void *dest, const void *src, udword size)
udword mLimit
Limit number of primitives / node. If limit is 1, build a complete tree (2*N-1 nodes) ...
Definition: Opcode.h:44
inline_ float FCMin3(float a, float b, float c)
A global function to find MIN(a,b,c) using FCOMI/FCMOV.
Definition: IceFPU.h:281
const MeshInterface * mIMesh
User-defined mesh interface.
Definition: Opcode.h:167
const udword * mBase
inline_ float FCMax3(float a, float b, float c)
A global function to find MAX(a,b,c) using FCOMI/FCMOV.
Definition: IceFPU.h:261
inline_ float Max() const
Returns MAX(x, y, z);.
Definition: OPC_IceHook.h:202
MeshInterface * mIMesh
Mesh interface (access to triangles & vertices) (*)
Definition: Opcode.h:30
#define Log
Definition: OPC_IceHook.h:28
const MeshInterface * mIMesh
Shortcut to an app-controlled mesh interface.
Definition: Opcode.h:171
inline_ BOOL IsQuantized() const
Definition: Opcode.h:132
LeafTriangles * mTriangles
udword mNbPrimitives
Number of primitives in the model.
Definition: Opcode.h:100
static BodyCustomizerHandle create(BodyHandle bodyHandle, const char *modelName)
bool CreateTree(bool no_leaf, bool quantized)
inline_ udword GetTriangleIndex() const
Definition: Opcode.h:43
BuildSettings mSettings
Builder's settings.
Definition: Opcode.h:31
inline_ float FCMax2(float a, float b)
A global function to find MAX(a,b) using FCOMI/FCMOV.
Definition: IceFPU.h:227
inline_ BOOL HasLeafNodes() const
Definition: Opcode.h:124
static int max(int a, int b)
inline_ udword GetNbTriangles() const
Definition: Opcode.h:61
BuildSettings mSettings
Splitting rules & split limit [Opcode 1.3].
Definition: Opcode.h:114


openhrp3
Author(s): AIST, General Robotix Inc., Nakamura Lab of Dept. of Mechano Informatics at University of Tokyo
autogenerated on Thu Sep 8 2022 02:24:04