Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

source: code/branches/ode/ode-0.9/OPCODE/OPC_AABBTree.h @ 237

Last change on this file since 237 was 216, checked in by mathiask, 18 years ago
[Physik] add ode-0.9
File size: 6.8 KB

Rev	Line
[216]	1	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	2	/*
	3	* OPCODE - Optimized Collision Detection
	4	* Copyright (C) 2001 Pierre Terdiman
	5	* Homepage: http://www.codercorner.com/Opcode.htm
	6	*/
	7	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	8
	9	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	10	/**
	11	* Contains code for a versatile AABB tree.
	12	* \file OPC_AABBTree.h
	13	* \author Pierre Terdiman
	14	* \date March, 20, 2001
	15	*/
	16	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	17
	18	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	19	// Include Guard
	20	#ifndef __OPC_AABBTREE_H__
	21	#define __OPC_AABBTREE_H__
	22
	23	#ifdef OPC_NO_NEG_VANILLA_TREE
	24	//! TO BE DOCUMENTED
	25	#define IMPLEMENT_TREE(base_class, volume) \
	26	public: \
	27	/* Constructor / Destructor */ \
	28	base_class(); \
	29	~base_class(); \
	30	/* Data access */ \
	31	inline_ const volume* Get##volume() const { return &mBV; } \
	32	/* Clear the last bit */ \
	33	inline_ const base_class* GetPos() const { return (const base_class*)(mPos&~1); } \
	34	inline_ const base_class* GetNeg() const { const base_class* P = GetPos(); return P ? P+1 : null;} \
	35	\
	36	/* We don't need to test both nodes since we can't have one without the other */ \
	37	inline_ bool IsLeaf() const { return !GetPos(); } \
	38	\
	39	/* Stats */ \
	40	inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \
	41	protected: \
	42	/* Tree-independent data */ \
	43	/* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/ \
	44	/* Whatever happens we need the two children and the enclosing volume.*/ \
	45	volume mBV; /* Global bounding-volume enclosing all the node-related primitives */ \
	46	size_t mPos; /* "Positive" & "Negative" children */
	47	#else
	48	//! TO BE DOCUMENTED
	49	#define IMPLEMENT_TREE(base_class, volume) \
	50	public: \
	51	/* Constructor / Destructor */ \
	52	base_class(); \
	53	~base_class(); \
	54	/* Data access */ \
	55	inline_ const volume* Get##volume() const { return &mBV; } \
	56	/* Clear the last bit */ \
	57	inline_ const base_class* GetPos() const { return (const base_class*)(mPos&~1); } \
	58	inline_ const base_class* GetNeg() const { return (const base_class*)(mNeg&~1); } \
	59	\
	60	/* inline_ bool IsLeaf() const { return (!GetPos() && !GetNeg()); } */ \
	61	/* We don't need to test both nodes since we can't have one without the other */ \
	62	inline_ bool IsLeaf() const { return !GetPos(); } \
	63	\
	64	/* Stats */ \
	65	inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \
	66	protected: \
	67	/* Tree-independent data */ \
	68	/* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/ \
	69	/* Whatever happens we need the two children and the enclosing volume.*/ \
	70	volume mBV; /* Global bounding-volume enclosing all the node-related primitives */ \
	71	size_t mPos; /* "Positive" child */ \
	72	size_t mNeg; /* "Negative" child */
	73	#endif
	74
	75	typedef void (CullingCallback) (udword nb_primitives, udword node_primitives, BOOL need_clipping, void* user_data);
	76
	77	class OPCODE_API AABBTreeNode
	78	{
	79	IMPLEMENT_TREE(AABBTreeNode, AABB)
	80	public:
	81	// Data access
	82	inline_ const udword* GetPrimitives() const { return mNodePrimitives; }
	83	inline_ udword GetNbPrimitives() const { return mNbPrimitives; }
	84
	85	protected:
	86	// Tree-dependent data
	87	udword* mNodePrimitives; //!< Node-related primitives (shortcut to a position in mIndices below)
	88	udword mNbPrimitives; //!< Number of primitives for this node
	89	// Internal methods
	90	udword Split(udword axis, AABBTreeBuilder* builder);
	91	bool Subdivide(AABBTreeBuilder* builder);
	92	void _BuildHierarchy(AABBTreeBuilder* builder);
	93	void _Refit(AABBTreeBuilder* builder);
	94	};
	95
	96	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	97	/**
	98	* User-callback, called for each node by the walking code.
	99	* \param current [in] current node
	100	* \param depth [in] current node's depth
	101	* \param user_data [in] user-defined data
	102	* \return true to recurse through children, else false to bypass them
	103	*/
	104	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	105	typedef bool (WalkingCallback) (const AABBTreeNode current, udword depth, void* user_data);
	106
	107	class OPCODE_API AABBTree : public AABBTreeNode
	108	{
	109	public:
	110	// Constructor / Destructor
	111	AABBTree();
	112	~AABBTree();
	113	// Build
	114	bool Build(AABBTreeBuilder* builder);
	115	void Release();
	116
	117	// Data access
	118	inline_ const udword* GetIndices() const { return mIndices; } //!< Catch the indices
	119	inline_ udword GetNbNodes() const { return mTotalNbNodes; } //!< Catch the number of nodes
	120
	121	// Infos
	122	bool IsComplete() const;
	123	// Stats
	124	udword ComputeDepth() const;
	125	udword GetUsedBytes() const;
	126	udword Walk(WalkingCallback callback, void* user_data) const;
	127
	128	bool Refit(AABBTreeBuilder* builder);
	129	bool Refit2(AABBTreeBuilder* builder);
	130	private:
	131	udword* mIndices; //!< Indices in the app list. Indices are reorganized during build (permutation).
	132	AABBTreeNode* mPool; //!< Linear pool of nodes for complete trees. Null otherwise. [Opcode 1.3]
	133	// Stats
	134	udword mTotalNbNodes; //!< Number of nodes in the tree.
	135	};
	136
	137	#endif // __OPC_AABBTREE_H__

Note: See TracBrowser for help on using the repository browser.

Download in other formats: