OPC_OptimizedTree.h

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

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Contains code for optimized trees.
 *	\file		OPC_OptimizedTree.h
 *	\author		Pierre Terdiman
 *	\date		March, 20, 2001
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Include Guard
#ifndef __OPC_OPTIMIZEDTREE_H__
#define __OPC_OPTIMIZEDTREE_H__

	//! Common interface for a node of an implicit tree
	#define IMPLEMENT_IMPLICIT_NODE(base_class, volume)														\
		public:																								\
		/* Constructor / Destructor */																		\
		inline_								base_class() : mData(0)	{}										\
		inline_								~base_class()			{}										\
		/* Leaf test */																						\
		inline_			BOOL				IsLeaf()		const	{ return mData&1;					}	\
		/* Data access */																					\
		inline_			const base_class*	GetPos()		const	{ return (base_class*)mData;		}	\
		inline_			const base_class*	GetNeg()		const	{ return ((base_class*)mData)+1;	}	\
		inline_			udword				GetPrimitive()	const	{ return (mData>>1);				}	\
		/* Stats */																							\
		inline_			udword				GetNodeSize()	const	{ return SIZEOFOBJECT;				}	\
																											\
						volume				mAABB;															\
						udword				mData;

	//! Common interface for a node of a no-leaf tree
	#define IMPLEMENT_NOLEAF_NODE(base_class, volume)														\
		public:																								\
		/* Constructor / Destructor */																		\
		inline_								base_class() : mPosData(0), mNegData(0)	{}						\
		inline_								~base_class()							{}						\
		/* Leaf tests */																					\
		inline_			BOOL				HasPosLeaf()		const	{ return mPosData&1;			}	\
		inline_			BOOL				HasNegLeaf()		const	{ return mNegData&1;			}	\
		/* Data access */																					\
		inline_			const base_class*	GetPos()			const	{ return (base_class*)mPosData;	}	\
		inline_			const base_class*	GetNeg()			const	{ return (base_class*)mNegData;	}	\
		inline_			udword				GetPosPrimitive()	const	{ return (mPosData>>1);			}	\
		inline_			udword				GetNegPrimitive()	const	{ return (mNegData>>1);			}	\
		/* Stats */																							\
		inline_			udword				GetNodeSize()		const	{ return SIZEOFOBJECT;			}	\
																											\
						volume				mAABB;															\
						udword				mPosData;														\
						udword				mNegData;

	class OPCODE_API AABBCollisionNode
	{
		IMPLEMENT_IMPLICIT_NODE(AABBCollisionNode, CollisionAABB)

		inline_			float				GetVolume()		const	{ return mAABB.mExtents.x * mAABB.mExtents.y * mAABB.mExtents.z;	}
		inline_			float				GetSize()		const	{ return mAABB.mExtents.SquareMagnitude();	}
		inline_			udword				GetRadius()		const
											{
												udword* Bits = (udword*)&mAABB.mExtents.x;
												udword Max = Bits[0];
												if(Bits[1]>Max)	Max = Bits[1];
												if(Bits[2]>Max)	Max = Bits[2];
												return Max;
											}

		// NB: using the square-magnitude or the true volume of the box, seems to yield better results
		// (assuming UNC-like informed traversal methods). I borrowed this idea from PQP. The usual "size"
		// otherwise, is the largest box extent. In SOLID that extent is computed on-the-fly each time it's
		// needed (the best approach IMHO). In RAPID the rotation matrix is permuted so that Extent[0] is
		// always the greatest, which saves looking for it at runtime. On the other hand, it yields matrices
		// whose determinant is not 1, i.e. you can't encode them anymore as unit quaternions. Not a very
		// good strategy.
	};

	class OPCODE_API AABBQuantizedNode
	{
		IMPLEMENT_IMPLICIT_NODE(AABBQuantizedNode, QuantizedAABB)

		inline_			uword				GetSize()		const
											{
												const uword* Bits = mAABB.mExtents;
												uword Max = Bits[0];
												if(Bits[1]>Max)	Max = Bits[1];
												if(Bits[2]>Max)	Max = Bits[2];
												return Max;
											}
		// NB: for quantized nodes I don't feel like computing a square-magnitude with integers all
		// over the place.......!
	};

	class OPCODE_API AABBNoLeafNode
	{
		IMPLEMENT_NOLEAF_NODE(AABBNoLeafNode, CollisionAABB)
	};

	class OPCODE_API AABBQuantizedNoLeafNode
	{
		IMPLEMENT_NOLEAF_NODE(AABBQuantizedNoLeafNode, QuantizedAABB)
	};

	//! Common interface for a collision tree
	#define IMPLEMENT_COLLISION_TREE(base_class, node)																\
		public:																										\
		/* Constructor / Destructor */																				\
													base_class();													\
		virtual										~base_class();													\
		/* Builds from a standard tree */																			\
		override(AABBOptimizedTree)	bool			Build(AABBTree* tree);											\
		/* Refits the tree */																						\
		override(AABBOptimizedTree)	bool			Refit(const MeshInterface* mesh_interface);						\
		/* Walks the tree */																						\
		override(AABBOptimizedTree)	bool			Walk(GenericWalkingCallback callback, void* user_data) const;	\
		/* Data access */																							\
		inline_						const node*		GetNodes()		const	{ return mNodes;					}	\
		/* Stats */																									\
		override(AABBOptimizedTree)	udword			GetUsedBytes()	const	{ return mNbNodes*sizeof(node);		}	\
		private:																									\
									node*			mNodes;

	typedef		bool				(*GenericWalkingCallback)	(const void* current, void* user_data);

	class OPCODE_API AABBOptimizedTree
	{
		public:
		// Constructor / Destructor
											AABBOptimizedTree() :
												mNbNodes	(0)
																							{}
		virtual								~AABBOptimizedTree()							{}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/**
		 *	Builds the collision tree from a generic AABB tree.
		 *	\param		tree			[in] generic AABB tree
		 *	\return		true if success
		 */
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		virtual			bool				Build(AABBTree* tree)											= 0;

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/**
		 *	Refits the collision tree after vertices have been modified.
		 *	\param		mesh_interface	[in] mesh interface for current model
		 *	\return		true if success
		 */
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		virtual			bool				Refit(const MeshInterface* mesh_interface)						= 0;

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/**
		 *	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
		 */
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		virtual			bool				Walk(GenericWalkingCallback callback, void* user_data) const	= 0;

		// Data access
		virtual			udword				GetUsedBytes()		const										= 0;
		inline_			udword				GetNbNodes()		const						{ return mNbNodes;	}

		protected:
						udword				mNbNodes;
	};

	class OPCODE_API AABBCollisionTree : public AABBOptimizedTree
	{
		IMPLEMENT_COLLISION_TREE(AABBCollisionTree, AABBCollisionNode)
	};

	class OPCODE_API AABBNoLeafTree : public AABBOptimizedTree
	{
		IMPLEMENT_COLLISION_TREE(AABBNoLeafTree, AABBNoLeafNode)
	};

	class OPCODE_API AABBQuantizedTree : public AABBOptimizedTree
	{
		IMPLEMENT_COLLISION_TREE(AABBQuantizedTree, AABBQuantizedNode)

		public:
						Point				mCenterCoeff;
						Point				mExtentsCoeff;
	};

	class OPCODE_API AABBQuantizedNoLeafTree : public AABBOptimizedTree
	{
		IMPLEMENT_COLLISION_TREE(AABBQuantizedNoLeafTree, AABBQuantizedNoLeafNode)

		public:
						Point				mCenterCoeff;
						Point				mExtentsCoeff;
	};

#endif // __OPC_OPTIMIZEDTREE_H__