784 lines
32 KiB
C++
784 lines
32 KiB
C++
|
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
|
||
|
|
/*
|
||
|
|
* 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 const 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 = (size_t)&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 = (size_t)&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 = (size_t)&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(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 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;
|
||
|
|
ConversionArea VC;
|
||
|
|
Point Min,Max;
|
||
|
|
Point Min_,Max_;
|
||
|
|
udword Index = mNbNodes;
|
||
|
|
while(Index--)
|
||
|
|
{
|
||
|
|
AABBNoLeafNode& Current = mNodes[Index];
|
||
|
|
|
||
|
|
if(Current.HasPosLeaf())
|
||
|
|
{
|
||
|
|
mesh_interface->GetTriangle(VP, Current.GetPosPrimitive(), VC);
|
||
|
|
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(), VC);
|
||
|
|
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 */ \
|
||
|
|
Point CMax(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT); \
|
||
|
|
Point 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 */ \
|
||
|
|
Point CQuantCoeff, EQuantCoeff; \
|
||
|
|
CQuantCoeff.x = !_equal(CMax.x, 0.0f) ? float((1<<nbc)-1)/CMax.x : 0.0f;\
|
||
|
|
CQuantCoeff.y = !_equal(CMax.y, 0.0f) ? float((1<<nbc)-1)/CMax.y : 0.0f;\
|
||
|
|
CQuantCoeff.z = !_equal(CMax.z, 0.0f) ? float((1<<nbc)-1)/CMax.z : 0.0f;\
|
||
|
|
EQuantCoeff.x = !_equal(EMax.x, 0.0f) ? float((1<<nbe)-1)/EMax.x : 0.0f;\
|
||
|
|
EQuantCoeff.y = !_equal(EMax.y, 0.0f) ? float((1<<nbe)-1)/EMax.y : 0.0f;\
|
||
|
|
EQuantCoeff.z = !_equal(EMax.z, 0.0f) ? float((1<<nbe)-1)/EMax.z : 0.0f;\
|
||
|
|
/* Compute and save dequantization coeffs */ \
|
||
|
|
mCenterCoeff.x = !_equal(CQuantCoeff.x, 0.0f) ? 1.0f / CQuantCoeff.x : 0.0f;\
|
||
|
|
mCenterCoeff.y = !_equal(CQuantCoeff.y, 0.0f) ? 1.0f / CQuantCoeff.y : 0.0f;\
|
||
|
|
mCenterCoeff.z = !_equal(CQuantCoeff.z, 0.0f) ? 1.0f / CQuantCoeff.z : 0.0f;\
|
||
|
|
mExtentsCoeff.x = !_equal(EQuantCoeff.x, 0.0f) ? 1.0f / EQuantCoeff.x : 0.0f;\
|
||
|
|
mExtentsCoeff.y = !_equal(EQuantCoeff.y, 0.0f) ? 1.0f / EQuantCoeff.y : 0.0f;\
|
||
|
|
mExtentsCoeff.z = !_equal(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 */ \
|
||
|
|
Point Max = Nodes[i].mAABB.mCenter + Nodes[i].mAABB.mExtents; \
|
||
|
|
Point 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 */ \
|
||
|
|
size_t Nb = (Data - size_t(Nodes))/Nodes[i].GetNodeSize(); \
|
||
|
|
Data = (size_t) &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
|
||
|
|
size_t 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
|
||
|
|
size_t 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;
|
||
|
|
}
|