Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

source: code/branches/ode/ode-0.9/OPCODE/OPC_TreeBuilders.h @ 218

Last change on this file since 218 was 216, checked in by mathiask, 18 years ago
[Physik] add ode-0.9
File size: 8.7 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 tree builders.
	12	* \file OPC_TreeBuilders.h
	13	* \author Pierre Terdiman
	14	* \date March, 20, 2001
	15	*/
	16	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	17
	18	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	19	// Include Guard
	20	#ifndef __OPC_TREEBUILDERS_H__
	21	#define __OPC_TREEBUILDERS_H__
	22
	23	//! Tree splitting rules
	24	enum SplittingRules
	25	{
	26	// Primitive split
	27	SPLIT_LARGEST_AXIS = (1<<0), //!< Split along the largest axis
	28	SPLIT_SPLATTER_POINTS = (1<<1), //!< Splatter primitive centers (QuickCD-style)
	29	SPLIT_BEST_AXIS = (1<<2), //!< Try largest axis, then second, then last
	30	SPLIT_BALANCED = (1<<3), //!< Try to keep a well-balanced tree
	31	SPLIT_FIFTY = (1<<4), //!< Arbitrary 50-50 split
	32	// Node split
	33	SPLIT_GEOM_CENTER = (1<<5), //!< Split at geometric center (else split in the middle)
	34	//
	35	SPLIT_FORCE_DWORD = 0x7fffffff
	36	};
	37
	38	//! Simple wrapper around build-related settings [Opcode 1.3]
	39	struct OPCODE_API BuildSettings
	40	{
	41	inline_ BuildSettings() : mLimit(1), mRules(SPLIT_FORCE_DWORD) {}
	42
	43	udword mLimit; //!< Limit number of primitives / node. If limit is 1, build a complete tree (2*N-1 nodes)
	44	udword mRules; //!< Building/Splitting rules (a combination of SplittingRules flags)
	45	};
	46
	47	class OPCODE_API AABBTreeBuilder
	48	{
	49	public:
	50	//! Constructor
	51	AABBTreeBuilder() :
	52	mNbPrimitives(0),
	53	mNodeBase(null),
	54	mCount(0),
	55	mNbInvalidSplits(0) {}
	56	//! Destructor
	57	virtual ~AABBTreeBuilder() {}
	58
	59	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	60	/**
	61	* Computes the AABB of a set of primitives.
	62	* \param primitives [in] list of indices of primitives
	63	* \param nb_prims [in] number of indices
	64	* \param global_box [out] global AABB enclosing the set of input primitives
	65	* \return true if success
	66	*/
	67	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	68	virtual bool ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box) const = 0;
	69
	70	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	71	/**
	72	* Computes the splitting value along a given axis for a given primitive.
	73	* \param index [in] index of the primitive to split
	74	* \param axis [in] axis index (0,1,2)
	75	* \return splitting value
	76	*/
	77	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	78	virtual float GetSplittingValue(udword index, udword axis) const = 0;
	79
	80	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	81	/**
	82	* Computes the splitting value along a given axis for a given node.
	83	* \param primitives [in] list of indices of primitives
	84	* \param nb_prims [in] number of indices
	85	* \param global_box [in] global AABB enclosing the set of input primitives
	86	* \param axis [in] axis index (0,1,2)
	87	* \return splitting value
	88	*/
	89	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	90	virtual float GetSplittingValue(const udword* primitives, udword nb_prims, const AABB& global_box, udword axis) const
	91	{
	92	// Default split value = middle of the axis (using only the box)
	93	return global_box.GetCenter(axis);
	94	}
	95
	96	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	97	/**
	98	* Validates node subdivision. This is called each time a node is considered for subdivision, during tree building.
	99	* \param primitives [in] list of indices of primitives
	100	* \param nb_prims [in] number of indices
	101	* \param global_box [in] global AABB enclosing the set of input primitives
	102	* \return TRUE if the node should be subdivised
	103	*/
	104	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	105	virtual BOOL ValidateSubdivision(const udword* primitives, udword nb_prims, const AABB& global_box)
	106	{
	107	// Check the user-defined limit
	108	if(nb_prims<=mSettings.mLimit) return FALSE;
	109
	110	return TRUE;
	111	}
	112
	113	BuildSettings mSettings; //!< Splitting rules & split limit [Opcode 1.3]
	114	udword mNbPrimitives; //!< Total number of primitives.
	115	void* mNodeBase; //!< Address of node pool [Opcode 1.3]
	116	// Stats
	117	inline_ void SetCount(udword nb) { mCount=nb; }
	118	inline_ void IncreaseCount(udword nb) { mCount+=nb; }
	119	inline_ udword GetCount() const { return mCount; }
	120	inline_ void SetNbInvalidSplits(udword nb) { mNbInvalidSplits=nb; }
	121	inline_ void IncreaseNbInvalidSplits() { mNbInvalidSplits++; }
	122	inline_ udword GetNbInvalidSplits() const { return mNbInvalidSplits; }
	123
	124	private:
	125	udword mCount; //!< Stats: number of nodes created
	126	udword mNbInvalidSplits; //!< Stats: number of invalid splits
	127	};
	128
	129	class OPCODE_API AABBTreeOfVerticesBuilder : public AABBTreeBuilder
	130	{
	131	public:
	132	//! Constructor
	133	AABBTreeOfVerticesBuilder() : mVertexArray(null) {}
	134	//! Destructor
	135	virtual ~AABBTreeOfVerticesBuilder() {}
	136
	137	override(AABBTreeBuilder) bool ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box) const;
	138	override(AABBTreeBuilder) float GetSplittingValue(udword index, udword axis) const;
	139	override(AABBTreeBuilder) float GetSplittingValue(const udword* primitives, udword nb_prims, const AABB& global_box, udword axis) const;
	140
	141	const Point* mVertexArray; //!< Shortcut to an app-controlled array of vertices.
	142	};
	143
	144	class OPCODE_API AABBTreeOfAABBsBuilder : public AABBTreeBuilder
	145	{
	146	public:
	147	//! Constructor
	148	AABBTreeOfAABBsBuilder() : mAABBArray(null) {}
	149	//! Destructor
	150	virtual ~AABBTreeOfAABBsBuilder() {}
	151
	152	override(AABBTreeBuilder) bool ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box) const;
	153	override(AABBTreeBuilder) float GetSplittingValue(udword index, udword axis) const;
	154
	155	const AABB* mAABBArray; //!< Shortcut to an app-controlled array of AABBs.
	156	};
	157
	158	class OPCODE_API AABBTreeOfTrianglesBuilder : public AABBTreeBuilder
	159	{
	160	public:
	161	//! Constructor
	162	AABBTreeOfTrianglesBuilder() : mIMesh(null) {}
	163	//! Destructor
	164	virtual ~AABBTreeOfTrianglesBuilder() {}
	165
	166	override(AABBTreeBuilder) bool ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box) const;
	167	override(AABBTreeBuilder) float GetSplittingValue(udword index, udword axis) const;
	168	override(AABBTreeBuilder) float GetSplittingValue(const udword* primitives, udword nb_prims, const AABB& global_box, udword axis) const;
	169
	170	const MeshInterface* mIMesh; //!< Shortcut to an app-controlled mesh interface
	171	};
	172
	173	#endif // __OPC_TREEBUILDERS_H__

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

Download in other formats: