opc_hybridmodel.cpp

opcode是功能强大

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
 *	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 "Opcode/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;
		IceMaths::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)	OpcodeLog("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 = (size_t(current->GetPrimitives()) - size_t(Data->mBase))/sizeof(size_t);
				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