OPC_HybridModel.cpp

Go to the documentation of this file.

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







// Precompiled Header
#include "Stdafx.h"

using namespace Opcode;



HybridModel::HybridModel() :
        mNbLeaves               (0),
        mNbPrimitives   (0),
        mTriangles              (null),
        mIndices                (null)
{
}



HybridModel::~HybridModel()
{
        Release();
}



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;
        };



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(current->GetPrimitives()) - udword(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;
}



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
}



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;
}