OPC_HybridModel.cpp
Go to the documentation of this file.
00001 
00002 /*
00003  *      OPCODE - Optimized Collision Detection
00004  *      Copyright (C) 2001 Pierre Terdiman
00005  *      Homepage: http://www.codercorner.com/Opcode.htm
00006  */
00008 
00010 
00016 
00017 
00019 
00081 
00082 
00084 // Precompiled Header
00085 #include "Stdafx.h"
00086 
00087 using namespace Opcode;
00088 
00090 
00093 
00094 HybridModel::HybridModel() :
00095         mNbLeaves               (0),
00096         mNbPrimitives   (0),
00097         mTriangles              (null),
00098         mIndices                (null)
00099 {
00100 }
00101 
00103 
00106 
00107 HybridModel::~HybridModel()
00108 {
00109         Release();
00110 }
00111 
00113 
00116 
00117 void HybridModel::Release()
00118 {
00119         ReleaseBase();
00120         DELETEARRAY(mIndices);
00121         DELETEARRAY(mTriangles);
00122         mNbLeaves               = 0;
00123         mNbPrimitives   = 0;
00124 }
00125 
00126         struct Internal
00127         {
00128                 Internal()
00129                 {
00130                         mNbLeaves       = 0;
00131                         mLeaves         = null;
00132                         mTriangles      = null;
00133                         mBase           = null;
00134                 }
00135                 ~Internal()
00136                 {
00137                         DELETEARRAY(mLeaves);
00138                 }
00139 
00140                 udword                  mNbLeaves;
00141                 AABB*                   mLeaves;
00142                 LeafTriangles*  mTriangles;
00143                 const udword*   mBase;
00144         };
00145 
00147 
00152 
00153 bool HybridModel::Build(const OPCODECREATE& create)
00154 {
00155         // 1) Checkings
00156         if(!create.mIMesh || !create.mIMesh->IsValid()) return false;
00157 
00158         // Look for degenerate faces.
00159         udword NbDegenerate = create.mIMesh->CheckTopology();
00160         if(NbDegenerate)        Log("OPCODE WARNING: found %d degenerate faces in model! Collision might report wrong results!\n", NbDegenerate);
00161         // We continue nonetheless.... 
00162 
00163         Release();      // Make sure previous tree has been discarded
00164 
00165         // 1-1) Setup mesh interface automatically
00166         SetMeshInterface(create.mIMesh);
00167 
00168         bool Status = false;
00169         AABBTree* LeafTree = null;
00170         Internal Data;
00171 
00172         // 2) Build a generic AABB Tree.
00173         mSource = new AABBTree;
00174         CHECKALLOC(mSource);
00175 
00176         // 2-1) Setup a builder. Our primitives here are triangles from input mesh,
00177         // so we use an AABBTreeOfTrianglesBuilder.....
00178         {
00179                 AABBTreeOfTrianglesBuilder TB;
00180                 TB.mIMesh                       = create.mIMesh;
00181                 TB.mNbPrimitives        = create.mIMesh->GetNbTriangles();
00182                 TB.mSettings            = create.mSettings;
00183                 TB.mSettings.mLimit     = 16;   // ### Hardcoded, but maybe we could let the user choose 8 / 16 / 32 ...
00184                 if(!mSource->Build(&TB))        goto FreeAndExit;
00185         }
00186 
00187         // 2-2) Here's the trick : create *another* AABB tree using the leaves of the first one (which are boxes, this time)
00188         struct Local
00189         {
00190                 // A callback to count leaf nodes
00191                 static bool CountLeaves(const AABBTreeNode* current, udword depth, void* user_data)
00192                 {
00193                         if(current->IsLeaf())
00194                         {
00195                                 Internal* Data = (Internal*)user_data;
00196                                 Data->mNbLeaves++;
00197                         }
00198                         return true;
00199                 }
00200 
00201                 // A callback to setup leaf nodes in our internal structures
00202                 static bool SetupLeafData(const AABBTreeNode* current, udword depth, void* user_data)
00203                 {
00204                         if(current->IsLeaf())
00205                         {
00206                                 Internal* Data = (Internal*)user_data;
00207 
00208                                 // Get current leaf's box
00209                                 Data->mLeaves[Data->mNbLeaves] = *current->GetAABB();
00210 
00211                                 // Setup leaf data
00212                                 udword Index = (udword(current->GetPrimitives()) - udword(Data->mBase))/sizeof(udword);
00213                                 Data->mTriangles[Data->mNbLeaves].SetData(current->GetNbPrimitives(), Index);
00214 
00215                                 Data->mNbLeaves++;
00216                         }
00217                         return true;
00218                 }
00219         };
00220 
00221         // Walk the tree & count number of leaves
00222         Data.mNbLeaves = 0;
00223         mSource->Walk(Local::CountLeaves, &Data);
00224         mNbLeaves = Data.mNbLeaves;     // Keep track of it
00225 
00226         // Special case for 1-leaf meshes
00227         if(mNbLeaves==1)
00228         {
00229                 mModelCode |= OPC_SINGLE_NODE;
00230                 Status = true;
00231                 goto FreeAndExit;
00232         }
00233 
00234         // Allocate our structures
00235         Data.mLeaves = new AABB[Data.mNbLeaves];                CHECKALLOC(Data.mLeaves);
00236         mTriangles = new LeafTriangles[Data.mNbLeaves]; CHECKALLOC(mTriangles);
00237 
00238         // Walk the tree again & setup leaf data
00239         Data.mTriangles = mTriangles;
00240         Data.mBase              = mSource->GetIndices();
00241         Data.mNbLeaves  = 0;    // Reset for incoming walk
00242         mSource->Walk(Local::SetupLeafData, &Data);
00243 
00244         // Handle source indices
00245         {
00246                 bool MustKeepIndices = true;
00247                 if(create.mCanRemap)
00248                 {
00249                         // We try to get rid of source indices (saving more ram!) by reorganizing triangle arrays...
00250                         // Remap can fail when we use callbacks => keep track of indices in that case (it still
00251                         // works, only using more memory)
00252                         if(create.mIMesh->RemapClient(mSource->GetNbPrimitives(), mSource->GetIndices()))
00253                         {
00254                                 MustKeepIndices = false;
00255                         }
00256                 }
00257 
00258                 if(MustKeepIndices)
00259                 {
00260                         // Keep track of source indices (from vanilla tree)
00261                         mNbPrimitives = mSource->GetNbPrimitives();
00262                         mIndices = new udword[mNbPrimitives];
00263                         CopyMemory(mIndices, mSource->GetIndices(), mNbPrimitives*sizeof(udword));
00264                 }
00265         }
00266 
00267         // Now, create our optimized tree using previous leaf nodes
00268         LeafTree = new AABBTree;
00269         CHECKALLOC(LeafTree);
00270         {
00271                 AABBTreeOfAABBsBuilder TB;      // Now using boxes !
00272                 TB.mSettings            = create.mSettings;
00273                 TB.mSettings.mLimit     = 1;    // We now want a complete tree so that we can "optimize" it
00274                 TB.mNbPrimitives        = Data.mNbLeaves;
00275                 TB.mAABBArray           = Data.mLeaves;
00276                 if(!LeafTree->Build(&TB))       goto FreeAndExit;
00277         }
00278 
00279         // 3) Create an optimized tree according to user-settings
00280         if(!CreateTree(create.mNoLeaf, create.mQuantized))      goto FreeAndExit;
00281 
00282         // 3-2) Create optimized tree
00283         if(!mTree->Build(LeafTree))     goto FreeAndExit;
00284 
00285         // Finally ok...
00286         Status = true;
00287 
00288 FreeAndExit:    // Allow me this one...
00289         DELETESINGLE(LeafTree);
00290 
00291         // 3-3) Delete generic tree if needed
00292         if(!create.mKeepOriginal)       DELETESINGLE(mSource);
00293 
00294         return Status;
00295 }
00296 
00298 
00302 
00303 udword HybridModel::GetUsedBytes() const
00304 {
00305         udword UsedBytes = 0;
00306         if(mTree)               UsedBytes += mTree->GetUsedBytes();
00307         if(mIndices)    UsedBytes += mNbPrimitives * sizeof(udword);    // mIndices
00308         if(mTriangles)  UsedBytes += mNbLeaves * sizeof(LeafTriangles); // mTriangles
00309         return UsedBytes;
00310 }
00311 
00312 inline_ void ComputeMinMax(Point& min, Point& max, const VertexPointers& vp)
00313 {
00314         // Compute triangle's AABB = a leaf box
00315 #ifdef OPC_USE_FCOMI    // a 15% speedup on my machine, not much
00316         min.x = FCMin3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
00317         max.x = FCMax3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
00318 
00319         min.y = FCMin3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
00320         max.y = FCMax3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
00321 
00322         min.z = FCMin3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
00323         max.z = FCMax3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
00324 #else
00325         min = *vp.Vertex[0];
00326         max = *vp.Vertex[0];
00327         min.Min(*vp.Vertex[1]);
00328         max.Max(*vp.Vertex[1]);
00329         min.Min(*vp.Vertex[2]);
00330         max.Max(*vp.Vertex[2]);
00331 #endif
00332 }
00333 
00335 
00341 
00342 bool HybridModel::Refit()
00343 {
00344         if(!mIMesh)     return false;
00345         if(!mTree)      return false;
00346 
00347         if(IsQuantized())       return false;
00348         if(HasLeafNodes())      return false;
00349 
00350         const LeafTriangles* LT = GetLeafTriangles();
00351         const udword* Indices = GetIndices();
00352 
00353         // Bottom-up update
00354         VertexPointers VP;
00355         Point Min,Max;
00356         Point Min_,Max_;
00357         udword Index = mTree->GetNbNodes();
00358         AABBNoLeafNode* Nodes = (AABBNoLeafNode*)((AABBNoLeafTree*)mTree)->GetNodes();
00359         while(Index--)
00360         {
00361                 AABBNoLeafNode& Current = Nodes[Index];
00362 
00363                 if(Current.HasPosLeaf())
00364                 {
00365                         const LeafTriangles& CurrentLeaf = LT[Current.GetPosPrimitive()];
00366 
00367                         Min.SetPlusInfinity();
00368                         Max.SetMinusInfinity();
00369 
00370                         Point TmpMin, TmpMax;
00371 
00372                         // Each leaf box has a set of triangles
00373                         udword NbTris = CurrentLeaf.GetNbTriangles();
00374                         if(Indices)
00375                         {
00376                                 const udword* T = &Indices[CurrentLeaf.GetTriangleIndex()];
00377 
00378                                 // Loop through triangles and test each of them
00379                                 while(NbTris--)
00380                                 {
00381                                         mIMesh->GetTriangle(VP, *T++);
00382                                         ComputeMinMax(TmpMin, TmpMax, VP);
00383                                         Min.Min(TmpMin);
00384                                         Max.Max(TmpMax);
00385                                 }
00386                         }
00387                         else
00388                         {
00389                                 udword BaseIndex = CurrentLeaf.GetTriangleIndex();
00390 
00391                                 // Loop through triangles and test each of them
00392                                 while(NbTris--)
00393                                 {
00394                                         mIMesh->GetTriangle(VP, BaseIndex++);
00395                                         ComputeMinMax(TmpMin, TmpMax, VP);
00396                                         Min.Min(TmpMin);
00397                                         Max.Max(TmpMax);
00398                                 }
00399                         }
00400                 }
00401                 else
00402                 {
00403                         const CollisionAABB& CurrentBox = Current.GetPos()->mAABB;
00404                         CurrentBox.GetMin(Min);
00405                         CurrentBox.GetMax(Max);
00406                 }
00407 
00408                 if(Current.HasNegLeaf())
00409                 {
00410                         const LeafTriangles& CurrentLeaf = LT[Current.GetNegPrimitive()];
00411 
00412                         Min_.SetPlusInfinity();
00413                         Max_.SetMinusInfinity();
00414 
00415                         Point TmpMin, TmpMax;
00416 
00417                         // Each leaf box has a set of triangles
00418                         udword NbTris = CurrentLeaf.GetNbTriangles();
00419                         if(Indices)
00420                         {
00421                                 const udword* T = &Indices[CurrentLeaf.GetTriangleIndex()];
00422 
00423                                 // Loop through triangles and test each of them
00424                                 while(NbTris--)
00425                                 {
00426                                         mIMesh->GetTriangle(VP, *T++);
00427                                         ComputeMinMax(TmpMin, TmpMax, VP);
00428                                         Min_.Min(TmpMin);
00429                                         Max_.Max(TmpMax);
00430                                 }
00431                         }
00432                         else
00433                         {
00434                                 udword BaseIndex = CurrentLeaf.GetTriangleIndex();
00435 
00436                                 // Loop through triangles and test each of them
00437                                 while(NbTris--)
00438                                 {
00439                                         mIMesh->GetTriangle(VP, BaseIndex++);
00440                                         ComputeMinMax(TmpMin, TmpMax, VP);
00441                                         Min_.Min(TmpMin);
00442                                         Max_.Max(TmpMax);
00443                                 }
00444                         }
00445                 }
00446                 else
00447                 {
00448                         const CollisionAABB& CurrentBox = Current.GetNeg()->mAABB;
00449                         CurrentBox.GetMin(Min_);
00450                         CurrentBox.GetMax(Max_);
00451                 }
00452 #ifdef OPC_USE_FCOMI
00453                 Min.x = FCMin2(Min.x, Min_.x);
00454                 Max.x = FCMax2(Max.x, Max_.x);
00455                 Min.y = FCMin2(Min.y, Min_.y);
00456                 Max.y = FCMax2(Max.y, Max_.y);
00457                 Min.z = FCMin2(Min.z, Min_.z);
00458                 Max.z = FCMax2(Max.z, Max_.z);
00459 #else
00460                 Min.Min(Min_);
00461                 Max.Max(Max_);
00462 #endif
00463                 Current.mAABB.SetMinMax(Min, Max);
00464         }
00465         return true;
00466 }


openhrp3
Author(s): AIST, General Robotix Inc., Nakamura Lab of Dept. of Mechano Informatics at University of Tokyo
autogenerated on Sun Apr 2 2017 03:43:55