///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
 *	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(baseclass, volume)													\
		public:																							\
		/* Constructor / Destructor */																	\
		inline_								baseclass() : mData(0)	{}									\
		inline_								~baseclass()			{}									\
		/* Leaf test */																					\
		inline_			BOOL				IsLeaf()		const	{ return mData&1;				}	\
		/* Data access */																				\
		inline_			const baseclass*	GetPos()		const	{ return (baseclass*)mData;		}	\
		inline_			const baseclass*	GetNeg()		const	{ return ((baseclass*)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(baseclass, volume)													\
		public:																							\
		/* Constructor / Destructor */																	\
		inline_								baseclass() : mData(0), mData2(0)	{}						\
		inline_								~baseclass()						{}						\
		/* Leaf tests */																				\
		inline_			BOOL				HasLeaf()		const	{ return mData&1;				}	\
		inline_			BOOL				HasLeaf2()		const	{ return mData2&1;				}	\
		/* Data access */																				\
		inline_			const baseclass*	GetPos()		const	{ return (baseclass*)mData;		}	\
		inline_			const baseclass*	GetNeg()		const	{ return (baseclass*)mData2;	}	\
		inline_			udword				GetPrimitive()	const	{ return (mData>>1);			}	\
		inline_			udword				GetPrimitive2()	const	{ return (mData2>>1);			}	\
		/* Stats */																						\
		inline_			udword				GetNodeSize()	const	{ return SIZEOFOBJECT;			}	\
																										\
						volume				mAABB;														\
						udword				mData;														\
						udword				mData2;

	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(baseclass, volume)														\
		public:																								\
		/* Constructor / Destructor */																		\
											baseclass();													\
		virtual								~baseclass();													\
		/* Build from a standard tree */																	\
		virtual			bool				Build(AABBTree* tree);											\
		/* Data access */																					\
		inline_			const volume*		GetNodes()		const	{ return mNodes;					}	\
		/* Stats */																							\
		virtual			udword				GetUsedBytes()	const	{ return mNbNodes*sizeof(volume);	}	\
		private:																							\
						volume*				mNodes;

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

		// Data access
		inline_			udword				GetNbNodes()	const	{ return mNbNodes;	}

		virtual			udword				GetUsedBytes()	const	= 0;
		virtual			bool				Build(AABBTree* tree)	= 0;
		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__