source: code/branches/ode/ode-0.9/OPCODE/OPC_HybridModel.cpp @ 216

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
 *      OPCODE - Optimized Collision Detection
 *      Copyright (C) 2001 Pierre Terdiman
 *      Homepage: http://www.codercorner.com/Opcode.htm
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *      Contains code for hybrid models.
 *      \file           OPC_HybridModel.cpp
 *      \author         Pierre Terdiman
 *      \date           May, 18, 2003
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *      An hybrid collision model.
 *      
 *      The problem :
 *      
 *      Opcode really shines for mesh-mesh collision, especially when meshes are deeply overlapping
 *      (it typically outperforms RAPID in those cases).
 *      
 *      Unfortunately this is not the typical scenario in games.
 *      
 *      For close-proximity cases, especially for volume-mesh queries, it's relatively easy to run faster
 *      than Opcode, that suffers from a relatively high setup time.
 *      
 *      In particular, Opcode's "vanilla" trees in those cases -can- run faster. They can also use -less-
 *      memory than the optimized ones, when you let the system stop at ~10 triangles / leaf for example
 *      (i.e. when you don't use "complete" trees). However, those trees tend to fragment memory quite a
 *      lot, increasing cache misses : since they're not "complete", we can't predict the final number of
 *      nodes and we have to allocate nodes on-the-fly. For the same reasons we can't use Opcode's "optimized"
 *      trees here, since they rely on a known layout to perform the "optimization".
 *      
 *      Hybrid trees :
 *      
 *      Hybrid trees try to combine best of both worlds :
 *      
 *      - they use a maximum limit of 16 triangles/leaf. "16" is used so that we'll be able to save the
 *      number of triangles using 4 bits only.
 *      
 *      - they're still "complete" trees thanks to a two-passes building phase. First we create a "vanilla"
 *      AABB-tree with Opcode, limited to 16 triangles/leaf. Then we create a *second* vanilla tree, this
 *      time using the leaves of the first one. The trick is : this second tree is now "complete"... so we
 *      can further transform it into an Opcode's optimized tree.
 *      
 *      - then we run the collision queries on that standard Opcode tree. The only difference is that leaf
 *      nodes contain indices to leaf nodes of another tree. Also, we have to skip all primitive tests in
 *      Opcode optimized trees, since our leaves don't contain triangles anymore.
 *      
 *      - finally, for each collided leaf, we simply loop through 16 triangles max, and collide them with
 *      the bounding volume used in the query (we only support volume-vs-mesh queries here, not mesh-vs-mesh)
 *      
 *      All of that is wrapped in this "hybrid model" that contains the minimal data required for this to work.
 *      It's a mix between old "vanilla" trees, and old "optimized" trees.
 *
 *      Extra advantages:
 *
 *      - If we use them for dynamic models, we're left with a very small number of leaf nodes to refit. It
 *      might be a bit faster since we have less nodes to write back.
 *
 *      - In rigid body simulation, using temporal coherence and sleeping objects greatly reduce the actual
 *      influence of one tree over another (i.e. the speed difference is often invisible). So memory is really
 *      the key element to consider, and in this regard hybrid trees are just better.
 *      
 *      Information to take home:
 *      - they use less ram
 *      - they're not slower (they're faster or slower depending on cases, overall there's no significant
 *      difference *as long as objects don't interpenetrate too much* - in which case Opcode's optimized trees
 *      are still notably faster)
 *
 *      \class          HybridModel
 *      \author         Pierre Terdiman
 *      \version        1.3
 *      \date           May, 18, 2003
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Precompiled Header
#include "Stdafx.h"

using namespace Opcode;

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *      Constructor.
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
HybridModel::HybridModel() :
        mNbLeaves               (0),
        mNbPrimitives   (0),
        mTriangles              (null),
        mIndices                (null)
{
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *      Destructor.
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
HybridModel::~HybridModel()
{
        Release();
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *      Releases everything.
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void HybridModel::Release()
{
        ReleaseBase();
        DELETEARRAY(mIndices);
        DELETEARRAY(mTriangles);
        mNbLeaves               = 0;
        mNbPrimitives   = 0;
}

        struct Internal
        {
                Internal()
                {
                        mNbLeaves       = 0;
                        mLeaves         = null;
                        mTriangles      = null;
                        mBase           = null;
                }
                ~Internal()
                {
                        DELETEARRAY(mLeaves);
                }

                udword                  mNbLeaves;
                AABB*                   mLeaves;
                LeafTriangles*  mTriangles;
                const udword*   mBase;
        };

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *      Builds a collision model.
 *      \param          create          [in] model creation structure
 *      \return         true if success
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool HybridModel::Build(const OPCODECREATE& create)
{
        // 1) Checkings
        if(!create.mIMesh || !create.mIMesh->IsValid()) return false;

        // Look for degenerate faces.
        udword NbDegenerate = create.mIMesh->CheckTopology();
        if(NbDegenerate)        Log("OPCODE WARNING: found %d degenerate faces in model! Collision might report wrong results!\n", NbDegenerate);
        // We continue nonetheless.... 

        Release();      // Make sure previous tree has been discarded

        // 1-1) Setup mesh interface automatically
        SetMeshInterface(create.mIMesh);

        bool Status = false;
        AABBTree* LeafTree = null;
        Internal Data;

        // 2) Build a generic AABB Tree.
        mSource = new AABBTree;
        CHECKALLOC(mSource);

        // 2-1) Setup a builder. Our primitives here are triangles from input mesh,
        // so we use an AABBTreeOfTrianglesBuilder.....
        {
                AABBTreeOfTrianglesBuilder TB;
                TB.mIMesh                       = create.mIMesh;
                TB.mNbPrimitives        = create.mIMesh->GetNbTriangles();
                TB.mSettings            = create.mSettings;
                TB.mSettings.mLimit     = 16;   // ### Hardcoded, but maybe we could let the user choose 8 / 16 / 32 ...
                if(!mSource->Build(&TB))        goto FreeAndExit;
        }

        // 2-2) Here's the trick : create *another* AABB tree using the leaves of the first one (which are boxes, this time)
        struct Local
        {
                // A callback to count leaf nodes
                static bool CountLeaves(const AABBTreeNode* current, udword depth, void* user_data)
                {
                        if(current->IsLeaf())
                        {
                                Internal* Data = (Internal*)user_data;
                                Data->mNbLeaves++;
                        }
                        return true;
                }

                // A callback to setup leaf nodes in our internal structures
                static bool SetupLeafData(const AABBTreeNode* current, udword depth, void* user_data)
                {
                        if(current->IsLeaf())
                        {
                                Internal* Data = (Internal*)user_data;

                                // Get current leaf's box
                                Data->mLeaves[Data->mNbLeaves] = *current->GetAABB();

                                // Setup leaf data
                                udword Index = udword((size_t(current->GetPrimitives()) - size_t(Data->mBase)) / sizeof(udword));
                                Data->mTriangles[Data->mNbLeaves].SetData(current->GetNbPrimitives(), Index);

                                Data->mNbLeaves++;
                        }
                        return true;
                }
        };

        // Walk the tree & count number of leaves
        Data.mNbLeaves = 0;
        mSource->Walk(Local::CountLeaves, &Data);
        mNbLeaves = Data.mNbLeaves;     // Keep track of it

        // Special case for 1-leaf meshes
        if(mNbLeaves==1)
        {
                mModelCode |= OPC_SINGLE_NODE;
                Status = true;
                goto FreeAndExit;
        }

        // Allocate our structures
        Data.mLeaves = new AABB[Data.mNbLeaves];                CHECKALLOC(Data.mLeaves);
        mTriangles = new LeafTriangles[Data.mNbLeaves]; CHECKALLOC(mTriangles);

        // Walk the tree again & setup leaf data
        Data.mTriangles = mTriangles;
        Data.mBase              = mSource->GetIndices();
        Data.mNbLeaves  = 0;    // Reset for incoming walk
        mSource->Walk(Local::SetupLeafData, &Data);

        // Handle source indices
        {
                bool MustKeepIndices = true;
                if(create.mCanRemap)
                {
                        // We try to get rid of source indices (saving more ram!) by reorganizing triangle arrays...
                        // Remap can fail when we use callbacks => keep track of indices in that case (it still
                        // works, only using more memory)
                        if(create.mIMesh->RemapClient(mSource->GetNbPrimitives(), mSource->GetIndices()))
                        {
                                MustKeepIndices = false;
                        }
                }

                if(MustKeepIndices)
                {
                        // Keep track of source indices (from vanilla tree)
                        mNbPrimitives = mSource->GetNbPrimitives();
                        mIndices = new udword[mNbPrimitives];
                        CopyMemory(mIndices, mSource->GetIndices(), mNbPrimitives*sizeof(udword));
                }
        }

        // Now, create our optimized tree using previous leaf nodes
        LeafTree = new AABBTree;
        CHECKALLOC(LeafTree);
        {
                AABBTreeOfAABBsBuilder TB;      // Now using boxes !
                TB.mSettings            = create.mSettings;
                TB.mSettings.mLimit     = 1;    // We now want a complete tree so that we can "optimize" it
                TB.mNbPrimitives        = Data.mNbLeaves;
                TB.mAABBArray           = Data.mLeaves;
                if(!LeafTree->Build(&TB))       goto FreeAndExit;
        }

        // 3) Create an optimized tree according to user-settings
        if(!CreateTree(create.mNoLeaf, create.mQuantized))      goto FreeAndExit;

        // 3-2) Create optimized tree
        if(!mTree->Build(LeafTree))     goto FreeAndExit;

        // Finally ok...
        Status = true;

FreeAndExit:    // Allow me this one...
        DELETESINGLE(LeafTree);

        // 3-3) Delete generic tree if needed
        if(!create.mKeepOriginal)       DELETESINGLE(mSource);

        return Status;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *      Gets the number of bytes used by the tree.
 *      \return         amount of bytes used
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
udword HybridModel::GetUsedBytes() const
{
        udword UsedBytes = 0;
        if(mTree)               UsedBytes += mTree->GetUsedBytes();
        if(mIndices)    UsedBytes += mNbPrimitives * sizeof(udword);    // mIndices
        if(mTriangles)  UsedBytes += mNbLeaves * sizeof(LeafTriangles); // mTriangles
        return UsedBytes;
}

inline_ void ComputeMinMax(Point& min, Point& max, const VertexPointers& vp)
{
        // Compute triangle's AABB = a leaf box
#ifdef OPC_USE_FCOMI    // a 15% speedup on my machine, not much
        min.x = FCMin3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
        max.x = FCMax3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);

        min.y = FCMin3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
        max.y = FCMax3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);

        min.z = FCMin3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
        max.z = FCMax3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
#else
        min = *vp.Vertex[0];
        max = *vp.Vertex[0];
        min.Min(*vp.Vertex[1]);
        max.Max(*vp.Vertex[1]);
        min.Min(*vp.Vertex[2]);
        max.Max(*vp.Vertex[2]);
#endif
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *      Refits the collision model. This can be used to handle dynamic meshes. Usage is:
 *      1. modify your mesh vertices (keep the topology constant!)
 *      2. refit the tree (call this method)
 *      \return         true if success
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool HybridModel::Refit()
{
        if(!mIMesh)     return false;
        if(!mTree)      return false;

        if(IsQuantized())       return false;
        if(HasLeafNodes())      return false;

        const LeafTriangles* LT = GetLeafTriangles();
        const udword* Indices = GetIndices();

        // Bottom-up update
        VertexPointers VP;
        Point Min,Max;
        Point Min_,Max_;
        udword Index = mTree->GetNbNodes();
        AABBNoLeafNode* Nodes = (AABBNoLeafNode*)((AABBNoLeafTree*)mTree)->GetNodes();
        while(Index--)
        {
                AABBNoLeafNode& Current = Nodes[Index];

                if(Current.HasPosLeaf())
                {
                        const LeafTriangles& CurrentLeaf = LT[Current.GetPosPrimitive()];

                        Min.SetPlusInfinity();
                        Max.SetMinusInfinity();

                        Point TmpMin, TmpMax;

                        // Each leaf box has a set of triangles
                        udword NbTris = CurrentLeaf.GetNbTriangles();
                        if(Indices)
                        {
                                const udword* T = &Indices[CurrentLeaf.GetTriangleIndex()];

                                // Loop through triangles and test each of them
                                while(NbTris--)
                                {
                                        mIMesh->GetTriangle(VP, *T++);
                                        ComputeMinMax(TmpMin, TmpMax, VP);
                                        Min.Min(TmpMin);
                                        Max.Max(TmpMax);
                                }
                        }
                        else
                        {
                                udword BaseIndex = CurrentLeaf.GetTriangleIndex();

                                // Loop through triangles and test each of them
                                while(NbTris--)
                                {
                                        mIMesh->GetTriangle(VP, BaseIndex++);
                                        ComputeMinMax(TmpMin, TmpMax, VP);
                                        Min.Min(TmpMin);
                                        Max.Max(TmpMax);
                                }
                        }
                }
                else
                {
                        const CollisionAABB& CurrentBox = Current.GetPos()->mAABB;
                        CurrentBox.GetMin(Min);
                        CurrentBox.GetMax(Max);
                }

                if(Current.HasNegLeaf())
                {
                        const LeafTriangles& CurrentLeaf = LT[Current.GetNegPrimitive()];

                        Min_.SetPlusInfinity();
                        Max_.SetMinusInfinity();

                        Point TmpMin, TmpMax;

                        // Each leaf box has a set of triangles
                        udword NbTris = CurrentLeaf.GetNbTriangles();
                        if(Indices)
                        {
                                const udword* T = &Indices[CurrentLeaf.GetTriangleIndex()];

                                // Loop through triangles and test each of them
                                while(NbTris--)
                                {
                                        mIMesh->GetTriangle(VP, *T++);
                                        ComputeMinMax(TmpMin, TmpMax, VP);
                                        Min_.Min(TmpMin);
                                        Max_.Max(TmpMax);
                                }
                        }
                        else
                        {
                                udword BaseIndex = CurrentLeaf.GetTriangleIndex();

                                // Loop through triangles and test each of them
                                while(NbTris--)
                                {
                                        mIMesh->GetTriangle(VP, BaseIndex++);
                                        ComputeMinMax(TmpMin, TmpMax, VP);
                                        Min_.Min(TmpMin);
                                        Max_.Max(TmpMax);
                                }
                        }
                }
                else
                {
                        const CollisionAABB& CurrentBox = Current.GetNeg()->mAABB;
                        CurrentBox.GetMin(Min_);
                        CurrentBox.GetMax(Max_);
                }
#ifdef OPC_USE_FCOMI
                Min.x = FCMin2(Min.x, Min_.x);
                Max.x = FCMax2(Max.x, Max_.x);
                Min.y = FCMin2(Min.y, Min_.y);
                Max.y = FCMax2(Max.y, Max_.y);
                Min.z = FCMin2(Min.z, Min_.z);
                Max.z = FCMax2(Max.z, Max_.z);
#else
                Min.Min(Min_);
                Max.Max(Max_);
#endif
                Current.mAABB.SetMinMax(Min, Max);
        }
        return true;
}