diff options
Diffstat (limited to 'third-party/Opcode/OPC_OptimizedTree.cpp')
| -rw-r--r-- | third-party/Opcode/OPC_OptimizedTree.cpp | 782 |
1 files changed, 782 insertions, 0 deletions
diff --git a/third-party/Opcode/OPC_OptimizedTree.cpp b/third-party/Opcode/OPC_OptimizedTree.cpp new file mode 100644 index 0000000..a84ac5a --- /dev/null +++ b/third-party/Opcode/OPC_OptimizedTree.cpp @@ -0,0 +1,782 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/* + * OPCODE - Optimized Collision Detection + * Copyright (C) 2001 Pierre Terdiman + * Homepage: http://www.codercorner.com/Opcode.htm + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for optimized trees. Implements 4 trees: + * - normal + * - no leaf + * - quantized + * - no leaf / quantized + * + * \file OPC_OptimizedTree.cpp + * \author Pierre Terdiman + * \date March, 20, 2001 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * A standard AABB tree. + * + * \class AABBCollisionTree + * \author Pierre Terdiman + * \version 1.3 + * \date March, 20, 2001 +*/ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * A no-leaf AABB tree. + * + * \class AABBNoLeafTree + * \author Pierre Terdiman + * \version 1.3 + * \date March, 20, 2001 +*/ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * A quantized AABB tree. + * + * \class AABBQuantizedTree + * \author Pierre Terdiman + * \version 1.3 + * \date March, 20, 2001 +*/ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * A quantized no-leaf AABB tree. + * + * \class AABBQuantizedNoLeafTree + * \author Pierre Terdiman + * \version 1.3 + * \date March, 20, 2001 +*/ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "StdAfx.h" + +using namespace Opcode; + +//! Compilation flag: +//! - true to fix quantized boxes (i.e. make sure they enclose the original ones) +//! - false to see the effects of quantization errors (faster, but wrong results in some cases) +static bool gFixQuantized = true; + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Builds an implicit tree from a standard one. An implicit tree is a complete tree (2*N-1 nodes) whose negative + * box pointers and primitive pointers have been made implicit, hence packing 3 pointers in one. + * + * Layout for implicit trees: + * Node: + * - box + * - data (32-bits value) + * + * if data's LSB = 1 => remaining bits are a primitive pointer + * else remaining bits are a P-node pointer, and N = P + 1 + * + * \relates AABBCollisionNode + * \fn _BuildCollisionTree(AABBCollisionNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node) + * \param linear [in] base address of destination nodes + * \param box_id [in] index of destination node + * \param current_id [in] current running index + * \param current_node [in] current node from input tree + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +static void _BuildCollisionTree(AABBCollisionNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node) +{ + // Current node from input tree is "current_node". Must be flattened into "linear[boxid]". + + // Store the AABB + current_node->GetAABB()->GetCenter(linear[box_id].mAABB.mCenter); + current_node->GetAABB()->GetExtents(linear[box_id].mAABB.mExtents); + // Store remaining info + if(current_node->IsLeaf()) + { + // The input tree must be complete => i.e. one primitive/leaf + ASSERT(current_node->GetNbPrimitives()==1); + // Get the primitive index from the input tree + udword PrimitiveIndex = current_node->GetPrimitives()[0]; + // Setup box data as the primitive index, marked as leaf + linear[box_id].mData = (PrimitiveIndex<<1)|1; + } + else + { + // To make the negative one implicit, we must store P and N in successive order + udword PosID = current_id++; // Get a new id for positive child + udword NegID = current_id++; // Get a new id for negative child + // Setup box data as the forthcoming new P pointer + linear[box_id].mData = (udword)&linear[PosID]; + // Make sure it's not marked as leaf + ASSERT(!(linear[box_id].mData&1)); + // Recurse with new IDs + _BuildCollisionTree(linear, PosID, current_id, current_node->GetPos()); + _BuildCollisionTree(linear, NegID, current_id, current_node->GetNeg()); + } +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Builds a "no-leaf" tree from a standard one. This is a tree whose leaf nodes have been removed. + * + * Layout for no-leaf trees: + * + * Node: + * - box + * - P pointer => a node (LSB=0) or a primitive (LSB=1) + * - N pointer => a node (LSB=0) or a primitive (LSB=1) + * + * \relates AABBNoLeafNode + * \fn _BuildNoLeafTree(AABBNoLeafNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node) + * \param linear [in] base address of destination nodes + * \param box_id [in] index of destination node + * \param current_id [in] current running index + * \param current_node [in] current node from input tree + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +static void _BuildNoLeafTree(AABBNoLeafNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node) +{ + const AABBTreeNode* P = current_node->GetPos(); + const AABBTreeNode* N = current_node->GetNeg(); + // Leaf nodes here?! + ASSERT(P); + ASSERT(N); + // Internal node => keep the box + current_node->GetAABB()->GetCenter(linear[box_id].mAABB.mCenter); + current_node->GetAABB()->GetExtents(linear[box_id].mAABB.mExtents); + + if(P->IsLeaf()) + { + // The input tree must be complete => i.e. one primitive/leaf + ASSERT(P->GetNbPrimitives()==1); + // Get the primitive index from the input tree + udword PrimitiveIndex = P->GetPrimitives()[0]; + // Setup prev box data as the primitive index, marked as leaf + linear[box_id].mPosData = (PrimitiveIndex<<1)|1; + } + else + { + // Get a new id for positive child + udword PosID = current_id++; + // Setup box data + linear[box_id].mPosData = (udword)&linear[PosID]; + // Make sure it's not marked as leaf + ASSERT(!(linear[box_id].mPosData&1)); + // Recurse + _BuildNoLeafTree(linear, PosID, current_id, P); + } + + if(N->IsLeaf()) + { + // The input tree must be complete => i.e. one primitive/leaf + ASSERT(N->GetNbPrimitives()==1); + // Get the primitive index from the input tree + udword PrimitiveIndex = N->GetPrimitives()[0]; + // Setup prev box data as the primitive index, marked as leaf + linear[box_id].mNegData = (PrimitiveIndex<<1)|1; + } + else + { + // Get a new id for negative child + udword NegID = current_id++; + // Setup box data + linear[box_id].mNegData = (udword)&linear[NegID]; + // Make sure it's not marked as leaf + ASSERT(!(linear[box_id].mNegData&1)); + // Recurse + _BuildNoLeafTree(linear, NegID, current_id, N); + } +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Constructor. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +AABBCollisionTree::AABBCollisionTree() : mNodes(null) +{ +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Destructor. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +AABBCollisionTree::~AABBCollisionTree() +{ + DELETEARRAY(mNodes); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Builds the collision tree from a generic AABB tree. + * \param tree [in] generic AABB tree + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBCollisionTree::Build(AABBTree* tree) +{ + // Checkings + if(!tree) return false; + // Check the input tree is complete + udword NbTriangles = tree->GetNbPrimitives(); + udword NbNodes = tree->GetNbNodes(); + if(NbNodes!=NbTriangles*2-1) return false; + + // Get nodes + if(mNbNodes!=NbNodes) // Same number of nodes => keep moving + { + mNbNodes = NbNodes; + DELETEARRAY(mNodes); + mNodes = new AABBCollisionNode[mNbNodes]; + CHECKALLOC(mNodes); + } + + // Build the tree + udword CurID = 1; + _BuildCollisionTree(mNodes, 0, CurID, tree); + ASSERT(CurID==mNbNodes); + + return true; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Refits the collision tree after vertices have been modified. + * \param mesh_interface [in] mesh interface for current model + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBCollisionTree::Refit(const MeshInterface* mesh_interface) +{ + ASSERT(!"Not implemented since AABBCollisionTrees have twice as more nodes to refit as AABBNoLeafTrees!"); + return false; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Walks the tree and call the user back for each node. + * \param callback [in] walking callback + * \param user_data [in] callback's user data + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBCollisionTree::Walk(GenericWalkingCallback callback, void* user_data) const +{ + if(!callback) return false; + + struct Local + { + static void _Walk(const AABBCollisionNode* current_node, GenericWalkingCallback callback, void* user_data) + { + if(!current_node || !(callback)(current_node, user_data)) return; + + if(!current_node->IsLeaf()) + { + _Walk(current_node->GetPos(), callback, user_data); + _Walk(current_node->GetNeg(), callback, user_data); + } + } + }; + Local::_Walk(mNodes, callback, user_data); + return true; +} + + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Constructor. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +AABBNoLeafTree::AABBNoLeafTree() : mNodes(null) +{ +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Destructor. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +AABBNoLeafTree::~AABBNoLeafTree() +{ + DELETEARRAY(mNodes); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Builds the collision tree from a generic AABB tree. + * \param tree [in] generic AABB tree + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBNoLeafTree::Build(AABBTree* tree) +{ + // Checkings + if(!tree) return false; + // Check the input tree is complete + udword NbTriangles = tree->GetNbPrimitives(); + udword NbNodes = tree->GetNbNodes(); + if(NbNodes!=NbTriangles*2-1) return false; + + // Get nodes + if(mNbNodes!=NbTriangles-1) // Same number of nodes => keep moving + { + mNbNodes = NbTriangles-1; + DELETEARRAY(mNodes); + mNodes = new AABBNoLeafNode[mNbNodes]; + CHECKALLOC(mNodes); + } + + // Build the tree + udword CurID = 1; + _BuildNoLeafTree(mNodes, 0, CurID, tree); + ASSERT(CurID==mNbNodes); + + return true; +} + +inline_ void ComputeMinMax(IcePoint& min, IcePoint& 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 tree after vertices have been modified. + * \param mesh_interface [in] mesh interface for current model + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBNoLeafTree::Refit(const MeshInterface* mesh_interface) +{ + // Checkings + if(!mesh_interface) return false; + + // Bottom-up update + VertexPointers VP; + IcePoint Min,Max; + IcePoint Min_,Max_; + udword Index = mNbNodes; + while(Index--) + { + AABBNoLeafNode& Current = mNodes[Index]; + + if(Current.HasPosLeaf()) + { + mesh_interface->GetTriangle(VP, Current.GetPosPrimitive()); + ComputeMinMax(Min, Max, VP); + } + else + { + const CollisionAABB& CurrentBox = Current.GetPos()->mAABB; + CurrentBox.GetMin(Min); + CurrentBox.GetMax(Max); + } + + if(Current.HasNegLeaf()) + { + mesh_interface->GetTriangle(VP, Current.GetNegPrimitive()); + ComputeMinMax(Min_, Max_, VP); + } + 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; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Walks the tree and call the user back for each node. + * \param callback [in] walking callback + * \param user_data [in] callback's user data + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBNoLeafTree::Walk(GenericWalkingCallback callback, void* user_data) const +{ + if(!callback) return false; + + struct Local + { + static void _Walk(const AABBNoLeafNode* current_node, GenericWalkingCallback callback, void* user_data) + { + if(!current_node || !(callback)(current_node, user_data)) return; + + if(!current_node->HasPosLeaf()) _Walk(current_node->GetPos(), callback, user_data); + if(!current_node->HasNegLeaf()) _Walk(current_node->GetNeg(), callback, user_data); + } + }; + Local::_Walk(mNodes, callback, user_data); + return true; +} + +// Quantization notes: +// - We could use the highest bits of mData to store some more quantized bits. Dequantization code +// would be slightly more complex, but number of overlap tests would be reduced (and anyhow those +// bits are currently wasted). Of course it's not possible if we move to 16 bits mData. +// - Something like "16 bits floats" could be tested, to bypass the int-to-float conversion. +// - A dedicated BV-BV test could be used, dequantizing while testing for overlap. (i.e. it's some +// lazy-dequantization which may save some work in case of early exits). At the very least some +// muls could be saved by precomputing several more matrices. But maybe not worth the pain. +// - Do we need to dequantize anyway? Not doing the extents-related muls only implies the box has +// been scaled, for example. +// - The deeper we move into the hierarchy, the smaller the extents should be. May not need a fixed +// number of quantization bits. Even better, could probably be best delta-encoded. + + +// Find max values. Some people asked why I wasn't simply using the first node. Well, I can't. +// I'm not looking for (min, max) values like in a standard AABB, I'm looking for the extremal +// centers/extents in order to quantize them. The first node would only give a single center and +// a single extents. While extents would be the biggest, the center wouldn't. +#define FIND_MAX_VALUES \ + /* Get max values */ \ + IcePoint CMax(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT); \ + IcePoint EMax(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT); \ + for(udword i=0;i<mNbNodes;i++) \ + { \ + if(fabsf(Nodes[i].mAABB.mCenter.x)>CMax.x) CMax.x = fabsf(Nodes[i].mAABB.mCenter.x); \ + if(fabsf(Nodes[i].mAABB.mCenter.y)>CMax.y) CMax.y = fabsf(Nodes[i].mAABB.mCenter.y); \ + if(fabsf(Nodes[i].mAABB.mCenter.z)>CMax.z) CMax.z = fabsf(Nodes[i].mAABB.mCenter.z); \ + if(fabsf(Nodes[i].mAABB.mExtents.x)>EMax.x) EMax.x = fabsf(Nodes[i].mAABB.mExtents.x); \ + if(fabsf(Nodes[i].mAABB.mExtents.y)>EMax.y) EMax.y = fabsf(Nodes[i].mAABB.mExtents.y); \ + if(fabsf(Nodes[i].mAABB.mExtents.z)>EMax.z) EMax.z = fabsf(Nodes[i].mAABB.mExtents.z); \ + } + +#define INIT_QUANTIZATION \ + udword nbc=15; /* Keep one bit for sign */ \ + udword nbe=15; /* Keep one bit for fix */ \ + if(!gFixQuantized) nbe++; \ + \ + /* Compute quantization coeffs */ \ + IcePoint CQuantCoeff, EQuantCoeff; \ + CQuantCoeff.x = CMax.x!=0.0f ? float((1<<nbc)-1)/CMax.x : 0.0f; \ + CQuantCoeff.y = CMax.y!=0.0f ? float((1<<nbc)-1)/CMax.y : 0.0f; \ + CQuantCoeff.z = CMax.z!=0.0f ? float((1<<nbc)-1)/CMax.z : 0.0f; \ + EQuantCoeff.x = EMax.x!=0.0f ? float((1<<nbe)-1)/EMax.x : 0.0f; \ + EQuantCoeff.y = EMax.y!=0.0f ? float((1<<nbe)-1)/EMax.y : 0.0f; \ + EQuantCoeff.z = EMax.z!=0.0f ? float((1<<nbe)-1)/EMax.z : 0.0f; \ + /* Compute and save dequantization coeffs */ \ + mCenterCoeff.x = CQuantCoeff.x!=0.0f ? 1.0f / CQuantCoeff.x : 0.0f; \ + mCenterCoeff.y = CQuantCoeff.y!=0.0f ? 1.0f / CQuantCoeff.y : 0.0f; \ + mCenterCoeff.z = CQuantCoeff.z!=0.0f ? 1.0f / CQuantCoeff.z : 0.0f; \ + mExtentsCoeff.x = EQuantCoeff.x!=0.0f ? 1.0f / EQuantCoeff.x : 0.0f; \ + mExtentsCoeff.y = EQuantCoeff.y!=0.0f ? 1.0f / EQuantCoeff.y : 0.0f; \ + mExtentsCoeff.z = EQuantCoeff.z!=0.0f ? 1.0f / EQuantCoeff.z : 0.0f; \ + +#define PERFORM_QUANTIZATION \ + /* Quantize */ \ + mNodes[i].mAABB.mCenter[0] = sword(Nodes[i].mAABB.mCenter.x * CQuantCoeff.x); \ + mNodes[i].mAABB.mCenter[1] = sword(Nodes[i].mAABB.mCenter.y * CQuantCoeff.y); \ + mNodes[i].mAABB.mCenter[2] = sword(Nodes[i].mAABB.mCenter.z * CQuantCoeff.z); \ + mNodes[i].mAABB.mExtents[0] = uword(Nodes[i].mAABB.mExtents.x * EQuantCoeff.x); \ + mNodes[i].mAABB.mExtents[1] = uword(Nodes[i].mAABB.mExtents.y * EQuantCoeff.y); \ + mNodes[i].mAABB.mExtents[2] = uword(Nodes[i].mAABB.mExtents.z * EQuantCoeff.z); \ + /* Fix quantized boxes */ \ + if(gFixQuantized) \ + { \ + /* Make sure the quantized box is still valid */ \ + IcePoint Max = Nodes[i].mAABB.mCenter + Nodes[i].mAABB.mExtents; \ + IcePoint Min = Nodes[i].mAABB.mCenter - Nodes[i].mAABB.mExtents; \ + /* For each axis */ \ + for(udword j=0;j<3;j++) \ + { /* Dequantize the box center */ \ + float qc = float(mNodes[i].mAABB.mCenter[j]) * mCenterCoeff[j]; \ + bool FixMe=true; \ + do \ + { /* Dequantize the box extent */ \ + float qe = float(mNodes[i].mAABB.mExtents[j]) * mExtentsCoeff[j]; \ + /* Compare real & dequantized values */ \ + if(qc+qe<Max[j] || qc-qe>Min[j]) mNodes[i].mAABB.mExtents[j]++; \ + else FixMe=false; \ + /* Prevent wrapping */ \ + if(!mNodes[i].mAABB.mExtents[j]) \ + { \ + mNodes[i].mAABB.mExtents[j]=0xffff; \ + FixMe=false; \ + } \ + }while(FixMe); \ + } \ + } + +#define REMAP_DATA(member) \ + /* Fix data */ \ + Data = Nodes[i].member; \ + if(!(Data&1)) \ + { \ + /* Compute box number */ \ + udword Nb = (Data - udword(Nodes))/Nodes[i].GetNodeSize(); \ + Data = udword(&mNodes[Nb]); \ + } \ + /* ...remapped */ \ + mNodes[i].member = Data; + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Constructor. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +AABBQuantizedTree::AABBQuantizedTree() : mNodes(null) +{ +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Destructor. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +AABBQuantizedTree::~AABBQuantizedTree() +{ + DELETEARRAY(mNodes); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Builds the collision tree from a generic AABB tree. + * \param tree [in] generic AABB tree + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBQuantizedTree::Build(AABBTree* tree) +{ + // Checkings + if(!tree) return false; + // Check the input tree is complete + udword NbTriangles = tree->GetNbPrimitives(); + udword NbNodes = tree->GetNbNodes(); + if(NbNodes!=NbTriangles*2-1) return false; + + // Get nodes + mNbNodes = NbNodes; + DELETEARRAY(mNodes); + AABBCollisionNode* Nodes = new AABBCollisionNode[mNbNodes]; + CHECKALLOC(Nodes); + + // Build the tree + udword CurID = 1; + _BuildCollisionTree(Nodes, 0, CurID, tree); + + // Quantize + { + mNodes = new AABBQuantizedNode[mNbNodes]; + CHECKALLOC(mNodes); + + // Get max values + FIND_MAX_VALUES + + // Quantization + INIT_QUANTIZATION + + // Quantize + udword Data; + for(udword i=0;i<mNbNodes;i++) + { + PERFORM_QUANTIZATION + REMAP_DATA(mData) + } + + DELETEARRAY(Nodes); + } + + return true; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Refits the collision tree after vertices have been modified. + * \param mesh_interface [in] mesh interface for current model + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBQuantizedTree::Refit(const MeshInterface* mesh_interface) +{ + ASSERT(!"Not implemented since requantizing is painful !"); + return false; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Walks the tree and call the user back for each node. + * \param callback [in] walking callback + * \param user_data [in] callback's user data + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBQuantizedTree::Walk(GenericWalkingCallback callback, void* user_data) const +{ + if(!callback) return false; + + struct Local + { + static void _Walk(const AABBQuantizedNode* current_node, GenericWalkingCallback callback, void* user_data) + { + if(!current_node || !(callback)(current_node, user_data)) return; + + if(!current_node->IsLeaf()) + { + _Walk(current_node->GetPos(), callback, user_data); + _Walk(current_node->GetNeg(), callback, user_data); + } + } + }; + Local::_Walk(mNodes, callback, user_data); + return true; +} + + + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Constructor. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +AABBQuantizedNoLeafTree::AABBQuantizedNoLeafTree() : mNodes(null) +{ +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Destructor. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +AABBQuantizedNoLeafTree::~AABBQuantizedNoLeafTree() +{ + DELETEARRAY(mNodes); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Builds the collision tree from a generic AABB tree. + * \param tree [in] generic AABB tree + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBQuantizedNoLeafTree::Build(AABBTree* tree) +{ + // Checkings + if(!tree) return false; + // Check the input tree is complete + udword NbTriangles = tree->GetNbPrimitives(); + udword NbNodes = tree->GetNbNodes(); + if(NbNodes!=NbTriangles*2-1) return false; + + // Get nodes + mNbNodes = NbTriangles-1; + DELETEARRAY(mNodes); + AABBNoLeafNode* Nodes = new AABBNoLeafNode[mNbNodes]; + CHECKALLOC(Nodes); + + // Build the tree + udword CurID = 1; + _BuildNoLeafTree(Nodes, 0, CurID, tree); + ASSERT(CurID==mNbNodes); + + // Quantize + { + mNodes = new AABBQuantizedNoLeafNode[mNbNodes]; + CHECKALLOC(mNodes); + + // Get max values + FIND_MAX_VALUES + + // Quantization + INIT_QUANTIZATION + + // Quantize + udword Data; + for(udword i=0;i<mNbNodes;i++) + { + PERFORM_QUANTIZATION + REMAP_DATA(mPosData) + REMAP_DATA(mNegData) + } + + DELETEARRAY(Nodes); + } + + return true; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Refits the collision tree after vertices have been modified. + * \param mesh_interface [in] mesh interface for current model + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBQuantizedNoLeafTree::Refit(const MeshInterface* mesh_interface) +{ + ASSERT(!"Not implemented since requantizing is painful !"); + return false; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Walks the tree and call the user back for each node. + * \param callback [in] walking callback + * \param user_data [in] callback's user data + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBQuantizedNoLeafTree::Walk(GenericWalkingCallback callback, void* user_data) const +{ + if(!callback) return false; + + struct Local + { + static void _Walk(const AABBQuantizedNoLeafNode* current_node, GenericWalkingCallback callback, void* user_data) + { + if(!current_node || !(callback)(current_node, user_data)) return; + + if(!current_node->HasPosLeaf()) _Walk(current_node->GetPos(), callback, user_data); + if(!current_node->HasNegLeaf()) _Walk(current_node->GetNeg(), callback, user_data); + } + }; + Local::_Walk(mNodes, callback, user_data); + return true; +} |