OPCODE/OPC_HybridModel.cpp

   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 hybrid models.
  12  *      \file           OPC_HybridModel.cpp
  13  *      \author         Pierre Terdiman
  14  *      \date           May, 18, 2003
  15  */
  16 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  17
  18 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  19 /**
  20  *      An hybrid collision model.
  21  *
  22  *      The problem :
  23  *
  24  *      Opcode really shines for mesh-mesh collision, especially when meshes are deeply overlapping
  25  *      (it typically outperforms RAPID in those cases).
  26  *
  27  *      Unfortunately this is not the typical scenario in games.
  28  *
  29  *      For close-proximity cases, especially for volume-mesh queries, it's relatively easy to run faster
  30  *      than Opcode, that suffers from a relatively high setup time.
  31  *
  32  *      In particular, Opcode's "vanilla" trees in those cases -can- run faster. They can also use -less-
  33  *      memory than the optimized ones, when you let the system stop at ~10 triangles / leaf for example
  34  *      (i.e. when you don't use "complete" trees). However, those trees tend to fragment memory quite a
  35  *      lot, increasing cache misses : since they're not "complete", we can't predict the final number of
  36  *      nodes and we have to allocate nodes on-the-fly. For the same reasons we can't use Opcode's "optimized"
  37  *      trees here, since they rely on a known layout to perform the "optimization".
  38  *
  39  *      Hybrid trees :
  40  *
  41  *      Hybrid trees try to combine best of both worlds :
  42  *
  43  *      - they use a maximum limit of 16 triangles/leaf. "16" is used so that we'll be able to save the
  44  *      number of triangles using 4 bits only.
  45  *
  46  *      - they're still "complete" trees thanks to a two-passes building phase. First we create a "vanilla"
  47  *      AABB-tree with Opcode, limited to 16 triangles/leaf. Then we create a *second* vanilla tree, this
  48  *      time using the leaves of the first one. The trick is : this second tree is now "complete"... so we
  49  *      can further transform it into an Opcode's optimized tree.
  50  *
  51  *      - then we run the collision queries on that standard Opcode tree. The only difference is that leaf
  52  *      nodes contain indices to leaf nodes of another tree. Also, we have to skip all primitive tests in
  53  *      Opcode optimized trees, since our leaves don't contain triangles anymore.
  54  *
  55  *      - finally, for each collided leaf, we simply loop through 16 triangles max, and collide them with
  56  *      the bounding volume used in the query (we only support volume-vs-mesh queries here, not mesh-vs-mesh)
  57  *
  58  *      All of that is wrapped in this "hybrid model" that contains the minimal data required for this to work.
  59  *      It's a mix between old "vanilla" trees, and old "optimized" trees.
  60  *
  61  *      Extra advantages:
  62  *
  63  *      - If we use them for dynamic models, we're left with a very small number of leaf nodes to refit. It
  64  *      might be a bit faster since we have less nodes to write back.
  65  *
  66  *      - In rigid body simulation, using temporal coherence and sleeping objects greatly reduce the actual
  67  *      influence of one tree over another (i.e. the speed difference is often invisible). So memory is really
  68  *      the key element to consider, and in this regard hybrid trees are just better.
  69  *
  70  *      Information to take home:
  71  *      - they use less ram
  72  *      - they're not slower (they're faster or slower depending on cases, overall there's no significant
  73  *      difference *as long as objects don't interpenetrate too much* - in which case Opcode's optimized trees
  74  *      are still notably faster)
  75  *
  76  *      \class          HybridModel
  77  *      \author         Pierre Terdiman
  78  *      \version        1.3
  79  *      \date           May, 18, 2003
  80 */
  81 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  82
  83 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  84 // Precompiled Header
  85 #include "Stdafx.h"
  86
  87 using namespace Opcode;
  88
  89 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  90 /**
  91  *      Constructor.
  92  */
  93 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  94 HybridModel::HybridModel() :
  95         mNbLeaves               (0),
  96         mTriangles              (null),
  97         mNbPrimitives   (0),
  98         mIndices                (null)
  99 {
 100 }
 101
 102 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 103 /**
 104  *      Destructor.
 105  */
 106 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 107 HybridModel::~HybridModel()
 108 {
 109         Release();
 110 }
 111
 112 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 113 /**
 114  *      Releases everything.
 115  */
 116 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 117 void HybridModel::Release()
 118 {
 119         ReleaseBase();
 120         DELETEARRAY(mIndices);
 121         DELETEARRAY(mTriangles);
 122         mNbLeaves               = 0;
 123         mNbPrimitives   = 0;
 124 }
 125
 126         struct Internal
 127         {
 128                 Internal()
 129                 {
 130                         mNbLeaves       = 0;
 131                         mLeaves         = null;
 132                         mTriangles      = null;
 133                         mBase           = null;
 134                 }
 135                 ~Internal()
 136                 {
 137                         DELETEARRAY(mLeaves);
 138                 }
 139
 140                 udword                  mNbLeaves;
 141                 AABB*                   mLeaves;
 142                 LeafTriangles*  mTriangles;
 143                 const dTriIndex*        mBase;
 144         };
 145
 146 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 147 /**
 148  *      Builds a collision model.
 149  *      \param          create          [in] model creation structure
 150  *      \return         true if success
 151  */
 152 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 153 bool HybridModel::Build(const OPCODECREATE& create)
 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;
 174         CHECKALLOC(mSource);
 175
 176         // 2-1) Setup a builder. Our primitives here are triangles from input mesh,
 177         // so we use an AABBTreeOfTrianglesBuilder.....
 178         {
 179                 AABBTreeOfTrianglesBuilder TB;
 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((size_t(current->GetPrimitives()) - size_t(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         {
 229                 mModelCode |= OPC_SINGLE_NODE;
 230                 Status = true;
 231                 goto FreeAndExit;
 232         }
 233
 234         // Allocate our structures
 235         Data.mLeaves = new AABB[Data.mNbLeaves];                CHECKALLOC(Data.mLeaves);
 236         mTriangles = new LeafTriangles[Data.mNbLeaves]; CHECKALLOC(mTriangles);
 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)
 252                         if(create.mIMesh->RemapClient(mSource->GetNbPrimitives(), mSource->GetIndices()))
 253                         {
 254                                 MustKeepIndices = false;
 255                         }
 256                 }
 257
 258                 if(MustKeepIndices)
 259                 {
 260                         // Keep track of source indices (from vanilla tree)
 261                         mNbPrimitives = mSource->GetNbPrimitives();
 262                         mIndices = new udword[mNbPrimitives];
 263                         CopyMemory(mIndices, mSource->GetIndices(), mNbPrimitives*sizeof(udword));
 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
 297 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 298 /**
 299  *      Gets the number of bytes used by the tree.
 300  *      \return         amount of bytes used
 301  */
 302 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 303 udword HybridModel::GetUsedBytes() const
 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
 312 inline_ void ComputeMinMax(Point& min, Point& max, const VertexPointers& vp)
 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
 334 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 335 /**
 336  *      Refits the collision model. This can be used to handle dynamic meshes. Usage is:
 337  *      1. modify your mesh vertices (keep the topology constant!)
 338  *      2. refit the tree (call this method)
 339  *      \return         true if success
 340  */
 341 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 342 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         ConversionArea VC;
 356         Point Min,Max;
 357         Point Min_,Max_;
 358         udword Index = mTree->GetNbNodes();
 359         AABBNoLeafNode* Nodes = const_cast<AABBNoLeafNode *>(static_cast<const AABBNoLeafNode *>(static_cast<AABBNoLeafTree *>(mTree)->GetNodes()));
 360         while(Index--)
 361         {
 362                 AABBNoLeafNode& Current = Nodes[Index];
 363
 364                 if(Current.HasPosLeaf())
 365                 {
 366                         const LeafTriangles& CurrentLeaf = LT[Current.GetPosPrimitive()];
 367
 368                         Min.SetPlusInfinity();
 369                         Max.SetMinusInfinity();
 370
 371                         Point TmpMin, TmpMax;
 372
 373                         // Each leaf box has a set of triangles
 374                         udword NbTris = CurrentLeaf.GetNbTriangles();
 375                         if(Indices)
 376                         {
 377                                 const udword* T = &Indices[CurrentLeaf.GetTriangleIndex()];
 378
 379                                 // Loop through triangles and test each of them
 380                                 while(NbTris--)
 381                                 {
 382                                         mIMesh->GetTriangle(VP, *T++, VC);
 383                                         ComputeMinMax(TmpMin, TmpMax, VP);
 384                                         Min.Min(TmpMin);
 385                                         Max.Max(TmpMax);
 386                                 }
 387                         }
 388                         else
 389                         {
 390                                 udword BaseIndex = CurrentLeaf.GetTriangleIndex();
 391
 392                                 // Loop through triangles and test each of them
 393                                 while(NbTris--)
 394                                 {
 395                                         mIMesh->GetTriangle(VP, BaseIndex++, VC);
 396                                         ComputeMinMax(TmpMin, TmpMax, VP);
 397                                         Min.Min(TmpMin);
 398                                         Max.Max(TmpMax);
 399                                 }
 400                         }
 401                 }
 402                 else
 403                 {
 404                         const CollisionAABB& CurrentBox = Current.GetPos()->mAABB;
 405                         CurrentBox.GetMin(Min);
 406                         CurrentBox.GetMax(Max);
 407                 }
 408
 409                 if(Current.HasNegLeaf())
 410                 {
 411                         const LeafTriangles& CurrentLeaf = LT[Current.GetNegPrimitive()];
 412
 413                         Min_.SetPlusInfinity();
 414                         Max_.SetMinusInfinity();
 415
 416                         Point TmpMin, TmpMax;
 417
 418                         // Each leaf box has a set of triangles
 419                         udword NbTris = CurrentLeaf.GetNbTriangles();
 420                         if(Indices)
 421                         {
 422                                 const udword* T = &Indices[CurrentLeaf.GetTriangleIndex()];
 423
 424                                 // Loop through triangles and test each of them
 425                                 while(NbTris--)
 426                                 {
 427                                         mIMesh->GetTriangle(VP, *T++, VC);
 428                                         ComputeMinMax(TmpMin, TmpMax, VP);
 429                                         Min_.Min(TmpMin);
 430                                         Max_.Max(TmpMax);
 431                                 }
 432                         }
 433                         else
 434                         {
 435                                 udword BaseIndex = CurrentLeaf.GetTriangleIndex();
 436
 437                                 // Loop through triangles and test each of them
 438                                 while(NbTris--)
 439                                 {
 440                                         mIMesh->GetTriangle(VP, BaseIndex++, VC);
 441                                         ComputeMinMax(TmpMin, TmpMax, VP);
 442                                         Min_.Min(TmpMin);
 443                                         Max_.Max(TmpMax);
 444                                 }
 445                         }
 446                 }
 447                 else
 448                 {
 449                         const CollisionAABB& CurrentBox = Current.GetNeg()->mAABB;
 450                         CurrentBox.GetMin(Min_);
 451                         CurrentBox.GetMax(Max_);
 452                 }
 453 #ifdef OPC_USE_FCOMI
 454                 Min.x = FCMin2(Min.x, Min_.x);
 455                 Max.x = FCMax2(Max.x, Max_.x);
 456                 Min.y = FCMin2(Min.y, Min_.y);
 457                 Max.y = FCMax2(Max.y, Max_.y);
 458                 Min.z = FCMin2(Min.z, Min_.z);
 459                 Max.z = FCMax2(Max.z, Max_.z);
 460 #else
 461                 Min.Min(Min_);
 462                 Max.Max(Max_);
 463 #endif
 464                 Current.mAABB.SetMinMax(Min, Max);
 465         }
 466         return true;
 467 }