#include <OPC_HybridModel.h>

Inheritance diagram for HybridModel:

Public Member Functions
inline_ const udword *	GetIndices () const
inline_ const LeafTriangles *	GetLeafTriangles () const
	HybridModel ()
	override (BaseModel) bool Build(const OPCODECREATE &create)
	override (BaseModel) udword GetUsedBytes() const
	override (BaseModel) bool Refit()
virtual	~HybridModel ()
Private Member Functions
void	Release ()
Private Attributes
udword *	mIndices
	Array of primitive indices.
udword	mNbLeaves
	Number of leaf nodes in the model.
udword	mNbPrimitives
	Number of primitives in the model.
LeafTriangles *	mTriangles
	Array of mNbLeaves leaf descriptors.

Detailed Description

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)

Author:: Pierre Terdiman

Version:: 1.3

Date:: May, 18, 2003

Definition at line 46 of file OPC_HybridModel.h.

Constructor & Destructor Documentation

HybridModel::HybridModel ( )

virtual HybridModel::~HybridModel ( ) [virtual]

Member Function Documentation

inline_ const udword* HybridModel::GetIndices ( ) const [inline]

Gets array of indices.

Returns:: array of indices

Definition at line 94 of file OPC_HybridModel.h.

inline_ const LeafTriangles* HybridModel::GetLeafTriangles ( ) const [inline]

Gets array of triangles.

Returns:: array of triangles

Definition at line 86 of file OPC_HybridModel.h.

HybridModel::override ( BaseModel ) const

Builds a collision model.

Parameters:

create [in] model creation structure

Returns:: true if success

HybridModel::override ( BaseModel ) const

Gets the number of bytes used by the tree.

Returns:: amount of bytes used

HybridModel::override ( BaseModel )

Refits the collision model. This can be used to handle dynamic meshes. Usage is: 1. modify your mesh vertices (keep the topology constant!) 2. refit the tree (call this method)