Context Navigation

source: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdTree.h @ 1220

Revision 1220, 17.4 KB checked in by szydlowski, 18 years ago (diff)

Rev	Line
[1163]	1	/*
	2	-----------------------------------------------------------------------------
	3	This source file is part of the GameTools Project
	4	http://www.gametools.org
	5
	6	Author: Martin Szydlowski
	7	-----------------------------------------------------------------------------
	8	*/
	9
	10	#ifndef _OgreKdTree_H__
	11	#define _OgreKdTree_H__
	12
[1170]	13	#define KDNODE_CAST(a) (static_cast<KdTree::Node>(a))
	14	#define KDBRANCH_CAST(a) (static_cast<KdTree::Branch>(a))
	15	#define KDLEAF_CAST(a) (static_cast<KdTree::Leaf>(a))
	16	#define KDNODEPTR_CAST(a) (static_cast<KdTree::Node *>(a))
	17	#define KDBRANCHPTR_CAST(a) (static_cast<KdTree::Branch *>(a))
	18	#define KDLEAFPTR_CAST(a) (static_cast<KdTree::Leaf *>(a))
	19
[1203]	20	#define KDTREE_LOGNAME "KdTreeBuild.log"
	21
[1163]	22	#include <OgreAxisAlignedBox.h>
	23	#include <OgreWireBoundingBox.h>
	24	#include <OgrePlane.h>
	25	#include <OgreVector3.h>
	26
	27	#include <OgreRoot.h>
	28
	29	#include <stack>
	30
[1211]	31	#include "OgreKdTreeCamera.h"
[1195]	32	#include "HierarchyInterface.h"
[1165]	33
[1170]	34
[1163]	35	namespace Ogre
	36	{
[1206]	37	class KdTreeCamera;
[1163]	38	class KdRenderable;
	39	struct SplitInfo;
	40
	41	class PlaneEvent
	42	{
	43	public:
	44	enum Type
	45	{
	46	PET_END,
	47	PET_ON,
	48	PET_START
	49	};
	50
	51	enum Dimension
	52	{
	53	PED_X,
	54	PED_Y,
	55	PED_Z
	56	};
	57
	58	enum Side
	59	{
	60	PES_LEFT = 0x01,
	61	PES_RIGHT = 0x02,
	62	PES_BOTH = PES_LEFT \| PES_RIGHT
	63	};
	64
	65	PlaneEvent(): mRenderable(0), mPosition(Vector3()), mDimension(PED_X), mType(PET_ON)
	66	{ };
	67
	68	PlaneEvent(KdRenderable *rend, const Vector3& pos, PlaneEvent::Dimension dim, PlaneEvent::Type type):
	69	mRenderable(rend), mPosition(pos), mDimension(dim), mType(type)
	70	{ };
	71
	72	~PlaneEvent() {};
	73
	74	// the less operator for plane events
	75	// first sort by position, then by dimension and finally by type
	76	bool operator < (const PlaneEvent& e) const
	77	{
	78	if(mPosition[mDimension] < e.mPosition[e.mDimension])
	79	{
	80	return true;
	81	}
	82
	83	if(mPosition[mDimension] == e.mPosition[e.mDimension])
	84	{
	85	if (mDimension < e.mDimension)
	86	{
	87	return true;
	88	}
	89	if (mDimension == e.mDimension)
	90	{
	91	if (mType < e.mType)
	92	{
	93	return true;
	94	}
	95	}
	96	}
	97
	98	return false;
	99	};
	100
	101	// the equals operator for tree events
	102	bool operator == (const PlaneEvent& e) const
	103	{
	104	return (mPosition[mDimension] == e.mPosition[e.mDimension]) &&
	105	(mDimension == e.mDimension) &&
	106	(mType == e.mType);
	107	};
	108
	109	bool equalsType(const PlaneEvent& e, PlaneEvent::Type t)
	110	{
	111	return (mPosition[mDimension] == e.mPosition[e.mDimension]) &&
	112	(mDimension == e.mDimension) &&
	113	(mType == t);
	114	};
	115
	116	void classify(const PlaneEvent& e, PlaneEvent::Side side);
	117
	118	PlaneEvent clip(AxisAlignedBox& box, PlaneEvent::Dimension dim);
	119
	120	Plane * getSplitPlane() const
	121	{
	122	Vector3 normal(0,0,0);
	123	normal[mDimension] = 1;
	124	return new Plane(normal, mPosition);
	125	}
	126
	127	KdRenderable * getRenderable() const //??
	128	{
	129	return mRenderable;
	130	};
	131
	132	PlaneEvent::Dimension getDimension() const //??
	133	{
	134	return mDimension;
	135	};
	136
	137	// DEBUG
	138	String print();
	139	protected:
	140	// event info
	141	KdRenderable * mRenderable;
	142	Vector3 mPosition;
	143	PlaneEvent::Dimension mDimension;
	144	PlaneEvent::Type mType;
	145
	146	// ------------------------------------------------------------------------------//
	147	// functions to determine the cost of splitting the node parent with the plane
	148	// represented by this event
	149	// TODO discuss if these functions really belong here, OO & SE - wise
	150	// pros: convenient, don't have to pass internal data to the outside
	151	// cons: SplitInfo ...
	152	public:
	153	// compute "global" surface area heuristic (SAH) for the plane represented by this event
	154	// use only with priority queue build method
	155	void pqSAH(Real globalSA, Real parentSA, int nLeft, int nPlane, int nRight, AxisAlignedBox& parentBox, SplitInfo& split);
	156	static Real pqSplitCost(Real p, Real pl, Real pr, int nLeft, int nRight, Real mu);
	157
	158	// compute the surface area heuristic (SAH) for the plane represented by this event
	159	void SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, SplitInfo& split);
	160	// the variables determining the cost of a branch traversal (KT) and a leaf intersection (KI)
	161	static Real KT;
	162	static Real KI;
	163	// helper functions
	164	static Real splitCost(Real pl, Real pr, int nLeft, int nRight);
	165	static Real splitCost(Real pl, Real pr, int nLeft, int nRight, Real mu);
	166	static Real surfaceArea(const AxisAlignedBox& box);
	167	static Real lookupPenalty(Real p);
	168	protected:
	169	Real splitBox(const AxisAlignedBox& parent, AxisAlignedBox& left, AxisAlignedBox& right);
	170	};
	171
	172	// Holds all the important information on a split
	173	struct SplitInfo
	174	{
	175	AxisAlignedBox bleft;
	176	AxisAlignedBox bright;
	177	int nleft;
	178	int nright;
	179	Real cost;
	180	PlaneEvent::Side side;
	181	PlaneEvent event;
	182
	183	// DEBUG
	184	String print();
	185	};
	186
	187	typedef std::list<PlaneEvent> PlaneEventList;
	188	typedef std::list<KdRenderable *> KdRenderableList;
	189
	190	class KdTree
	191	{
	192	protected:
	193	class Branch;
	194	class Leaf;
	195
	196	class Node
	197	{
	198	public:
[1192]	199	Node(KdTree * owner, int level, AxisAlignedBox& aabb, Branch * parent):
	200	mOwner(owner),
[1163]	201	mLevel(level),
	202	mAABB(aabb),
	203	mParent(parent),
	204	mWBB(0)
	205	{ };
	206
	207	virtual ~Node()
	208	{
	209	delete mWBB;
	210	};
	211
	212	virtual bool isLeaf() const = 0;
	213	virtual bool isEmpty() const = 0;
[1170]	214	virtual bool hasGeometry() const = 0;
[1187]	215
[1192]	216	// Gets this node's parent (NULL if this is the root).
[1195]	217	KdTree::Node *getParent(void) const { return mParent; };
[1192]	218
[1195]	219	// Gets the nodes left & right child nodes, or NULL if not present or node is leaf
	220	virtual KdTree::Node *getLeftChild(void) const = 0;
	221	virtual KdTree::Node *getRightChild(void) const = 0;
	222
	223	// add contained objects to render queue
[1187]	224	virtual void queueVisibleObjects(unsigned long currentFrame,
	225	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes) = 0;
[1195]	226
	227	// add contained geometry (Entities) to list
	228	virtual void getGeometryList(GtpVisibility::GeometryVector *geometryList) = 0;
[1163]	229
[1195]	230	// create (when necessary), setup and return wire bounding box representing the node
[1192]	231	WireBoundingBox * getWireBoundingBox()
[1163]	232	{
	233	if (mWBB == 0)
	234	mWBB = new WireBoundingBox();
	235
[1192]	236	if (mOwner->getShowNodes())
[1183]	237	mWBB->setupBoundingBox(mAABB);
	238	else
	239	mWBB->setupBoundingBox(mWorldAABB);
[1192]	240
	241	if (mOwner->getHiLiteLevel() == mLevel)
	242	mWBB->setMaterial("KdTree/BoxHiLite");
	243	else
	244	mWBB->setMaterial("BaseWhiteNoLighting");
[1163]	245
	246	return mWBB;
	247	}
	248
[1195]	249	// returns the level the node is on
	250	int getLevel(void) const { return mLevel; };
	251
[1170]	252	// functions for the CHC hierarchy interface
	253
	254	/** Returns last visited frame id. */
	255	unsigned int lastVisited(void) { return mLastVisited; };
	256	/** Set to current frame id.
	257	@param current frame id.
	258	*/
	259	void setLastVisited(unsigned int frameid) { mLastVisited = frameid; };
	260	/** Makes this octree become visible / invisble.
	261	@param visible Whether this node is to be made visible or invisible
	262	*/
	263	void setNodeVisible(bool visible) { mVisible = visible; };
	264	/** Returns true if this node is marked visible, false otherwise.
	265	*/
	266	bool isNodeVisible(void) { return mVisible; };
	267	/** Frame id when this octree was last rendered.
	268	@return last rendered frame id
	269	*/
	270	unsigned int lastRendered(void) { return mLastRendered; };
	271	/** Sets frame id when this octree was last rendered.
	272	@param last rendered frame id
	273	*/
	274	void setLastRendered(unsigned int frameid) { mLastRendered = frameid; };
[1173]	275	/** Returns real extent of the kdtree, i.e., the merged extent of the bounding boxes.
[1170]	276	*/
[1182]	277	AxisAlignedBox _getWorldAABB(void) const { return mAABB; };
[1173]	278	/** Updates bound of the real aabb of kdtree
	279	*/
[1183]	280	virtual void _updateBounds(bool recurse = true) = 0;
[1195]	281
	282	/ bounding box of the node/
[1163]	283	AxisAlignedBox mAABB;
[1170]	284
[1195]	285	/** mounding box of all objects inside the node */
[1173]	286	AxisAlignedBox mWorldAABB;
[1187]	287	protected:
[1192]	288	KdTree * mOwner;
	289	Branch * mParent;
	290	int mLevel;
	291
[1187]	292	WireBoundingBox * mWBB;
[1173]	293
[1195]	294	// for the CHC hierarchy interface
[1170]	295	unsigned int mLastRendered;
	296	unsigned int mLastVisited;
	297	bool mVisible;
[1163]	298	};
	299
	300	class Branch : public Node
	301	{
	302	public:
[1192]	303	Branch(KdTree * owner, int level, AxisAlignedBox& aabb, Branch * parent,
	304	Plane * splitplane, PlaneEvent::Side side):
	305	Node(owner, level, aabb, parent),
	306	mSplitPlane(splitplane),
	307	mLeft(0),
	308	mRight(0),
	309	mPlaneSide(side)
[1163]	310	{ };
	311
	312	virtual ~Branch()
	313	{
	314	delete mLeft;
	315	delete mRight;
	316	delete mSplitPlane;
	317	};
	318
[1170]	319	// a branch is not a leaf
[1163]	320	virtual bool isLeaf() const { return false; };
	321
[1170]	322	// s branch is empty when it does not have children
[1163]	323	virtual bool isEmpty() const { return (mLeft == 0 && mRight == 0); }
[1170]	324
	325	// a branch never has geometry
	326	virtual bool hasGeometry() const { return false; };
[1173]	327
[1192]	328	// a branch should have at least one child
[1195]	329	virtual KdTree::Node * getLeftChild() const { return mLeft; };
	330	virtual KdTree::Node * getRightChild() const { return mRight; };
[1192]	331
[1187]	332	virtual void queueVisibleObjects(unsigned long currentFrame,
	333	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes)
	334	{
	335	if (showBoxes)
[1192]	336	if (mLevel == mOwner->getHiLiteLevel() \|\| mOwner->getShowAllBoxes())
	337	queue->addRenderable(getWireBoundingBox());
[1187]	338	}
	339
[1195]	340	// a branch has no geometry, do nothing
	341	virtual void getGeometryList(GtpVisibility::GeometryVector *geometryList) { }
	342
[1173]	343	// branches do not posses geometry => just merge child aabbs
[1183]	344	virtual void _updateBounds(bool recurse = true)
[1173]	345	{
	346	// reset box
	347	mWorldAABB.setNull();
	348
	349	if (mLeft)
[1187]	350	mWorldAABB.merge(mLeft->mWorldAABB);
[1173]	351	if (mRight)
[1187]	352	mWorldAABB.merge(mRight->mWorldAABB);
[1173]	353
	354	// update parent recursively
[1183]	355	if (recurse && mParent)
	356	mParent->_updateBounds(recurse);
[1173]	357	}
[1163]	358
	359	Node * mLeft;
	360	Node * mRight;
	361	Plane * mSplitPlane;
	362	PlaneEvent::Side mPlaneSide;
	363	};
	364
	365	class Leaf : public Node
	366	{
	367	public:
[1192]	368	Leaf(KdTree * owner, int level, AxisAlignedBox& aabb, Branch * parent):
	369	Node(owner, level, aabb, parent)
[1163]	370	{};
	371
	372	virtual ~Leaf();
	373
[1170]	374	// a leaf is a leaf, dammit
[1163]	375	virtual bool isLeaf() const { return true; };
	376
[1170]	377	// a leaf is empty when it does not posses renderables
[1163]	378	virtual bool isEmpty() const { return mKdRenderables.empty(); };
	379
[1170]	380	// a leaf has geometry when it has renderables
	381	virtual bool hasGeometry() const { return !mKdRenderables.empty(); };
	382
[1192]	383	// a leaf never has children
[1195]	384	virtual KdTree::Node * getLeftChild() const { return 0; };
	385	virtual KdTree::Node * getRightChild() const { return 0; };
[1192]	386
[1187]	387	virtual void queueVisibleObjects(unsigned long currentFrame,
	388	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes);
	389
[1195]	390	virtual void getGeometryList(GtpVisibility::GeometryVector *geometryList);
	391
[1173]	392	// update the world aabb based on the contained geometry
[1183]	393	virtual void _updateBounds(bool recurse = true);
[1173]	394
[1163]	395	virtual void remove(KdRenderable * rend)
	396	{
	397	mKdRenderables.remove(rend);
	398	//mKdRenderables.erase(find(mKdRenderables.begin(), mKdRenderables.end(), rend));
	399	};
	400
	401	virtual void insert(KdRenderable * rend)
	402	{
	403	mKdRenderables.push_back(rend);
	404	};
	405
	406	KdRenderableList mKdRenderables;
	407	};
	408
	409	struct SplitCandidate
	410	{
[1195]	411	SplitCandidate(PlaneEventList * e, int n, AxisAlignedBox& a,
	412	KdTree::Branch * p, Real c, Real d, SplitInfo * b, PlaneEvent::Side s):
	413	events(e), nObjects(n), aabb(a), parent(p), cost(c), decrease(d), best(b), side(s)
	414	{ };
[1163]	415
	416	bool operator < (const SplitCandidate& rhs) const
	417	{
	418	return decrease < rhs.decrease;
	419	};
	420
	421	void operator = (const SplitCandidate& rhs)
	422	{
	423	decrease = rhs.decrease;
	424	cost = rhs.cost;
	425	nObjects = rhs.nObjects;
	426	side = rhs.side;
	427	aabb = rhs.aabb;
	428	events = rhs.events;
	429	parent = rhs.parent;
	430	best = rhs.best;
	431	};
	432
	433	// DEBUG
	434	String print();
	435
	436	Real decrease;
	437	Real cost;
	438	int nObjects;
	439	PlaneEvent::Side side;
	440	AxisAlignedBox aabb;
	441	PlaneEventList * events;
	442	KdTree::Branch * parent;
	443	SplitInfo * best;
	444	};
	445
[1170]	446	// typedef std::stack<SplitCandidate> SplitCandidatePQ;
[1163]	447	typedef std::priority_queue<SplitCandidate> SplitCandidatePQ;
	448
[1170]	449	// nodestack for the stack-based rendering function
	450	typedef std::stack<KdTree::Node *> NodeStack;
[1163]	451	public:
[1170]	452	friend class KdTreeHierarchyInterface;
[1165]	453
[1182]	454	typedef KdTree::Node * NodePtr;
	455	typedef KdTree::Branch * BranchPtr;
[1163]	456	typedef KdTree::Leaf * LeafPtr;
[1187]	457
	458	typedef std::list<NodePtr> NodeList;
[1163]	459	typedef std::set<LeafPtr> LeafSet;
	460
[1182]	461	typedef struct Stats_
	462	{
	463	unsigned int mNumNodes;
	464	unsigned int mNumLeaves;
	465	unsigned int mNumSceneNodes;
	466
	467	void clear(void)
	468	{
	469	mNumNodes = 0;
	470	mNumLeaves = 0;
	471	mNumSceneNodes = 0;
	472	};
	473	} Stats;
	474
[1170]	475	enum RenderMethod
	476	{
[1177]	477	KDRM_INTERNAL,
	478	KDRM_GTP_VFC,
	479	KDRM_GTP_SWC,
[1220]	480	KDRM_GTP_CHC,
	481	// invalid modes, just for convenience
	482	KDRM_SIZE,
	483	KDRM_NOTSET
[1170]	484	};
	485
[1163]	486	enum BuildMethod
	487	{
	488	KDBM_RECURSIVE,
[1220]	489	KDBM_PRIORITYQUEUE,
	490	// invalid modes, just for convenience
	491	KDBM_SIZE,
	492	KDBM_NOTSET
[1163]	493	};
[1192]	494
[1220]	495
[1192]	496	const static int HILITE_OFF = -1;
[1163]	497
[1192]	498	KdTree(int maxdepth, BuildMethod bm);
	499	KdTree(int maxdepth, BuildMethod bm, int hilite, bool allboxes, bool shownodes);
[1163]	500	virtual ~KdTree();
	501
	502	// DEBUG
[1182]	503	void dump(void);
	504	Real calcCost(void);
[1163]	505
[1192]	506	// sets the level to highlight or turns it off (when hilite < 0)
	507	inline void setHiLiteLevel(int hilite) { mHiLiteLevel = hilite; };
	508	inline int getHiLiteLevel(void) { return mHiLiteLevel; };
[1183]	509
[1192]	510	// toggles displaying the kdtree boxes
	511	inline void setShowAllBoxes(bool show) { mShowAllBoxes = show; };
	512	inline bool getShowAllBoxes(void) { return mShowAllBoxes; };
	513
	514	// toggles between displaying the bounding box of the node and
	515	// the box of the contained scene nodes
	516	inline void setShowNodes(bool show = true) { mShowNodes = show; };
	517	inline bool getShowNodes(void) { return mShowNodes; };
	518
[1211]	519	// changes vis mode (simple/enhanced with NONE/PART/FULL vis)
	520	void setEnhancedVis(bool enh);
	521	bool getEnhancedVis(void);
	522
[1182]	523	NodePtr getRoot(void) const { return mKdRoot; };
	524
[1163]	525	// insert a new scene node into an existing kd-tree
	526	void insert(KdRenderable * rend);
	527	// remove a scene node from the tree
	528	void remove(KdRenderable * rend);
	529	// function to initialize a kd-tree based on the contents of the scene
	530	void build(KdRenderable * sceneRoot);
	531
	532	// test visibility of objects and add to render queue
[1206]	533	void queueVisibleObjects(KdTreeCamera* cam, RenderQueue* queue, bool onlyShadowCasters,
[1195]	534	bool showBoxes, KdTree::NodeList& visibleNodes);
[1163]	535
[1195]	536	// find visible nodes & place in list
	537	//void findVisibleNodes(NodeList& visibleNodes, Camera * cam);
	538
[1163]	539	// self-explanatory ...
[1182]	540	int getMaxDepth(void) { return mMaxDepth; };
	541	Stats getStats(void) const { return mStats; };
	542	AxisAlignedBox getBox(void) { if (mKdRoot) return mKdRoot->mAABB; else return AxisAlignedBox(); };
[1163]	543	void setBuildMethod(BuildMethod bm) { mBuildMethod = bm; }
	544	protected:
[1192]	545	// init materials, logs and stuff
	546	void init();
[1163]	547	// recursive insert funciton
	548	void recInsert(KdTree::Node * node, KdRenderable * rend);
	549	// helper functions for insert
	550	void recInsertNew(KdTree::Branch * parent, PlaneEvent::Side side, KdRenderable * rend);
	551	void splitBox(const KdTree::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right);
	552	void rebuildSubtree(KdTree::Node * node, KdRenderable * rend);
	553	// build scene from a list of nodes rather than a hierarchy
	554	KdTree::Node * buildFromList(KdRenderableList& nodelist, KdTree::Branch * parent, AxisAlignedBox& aabb);
	555	void addRendToList(KdTree::Node * node, KdRenderableList& nodelist);
	556
	557	// recursively delete empty nodes
	558	void recDelete(KdTree::Node * node);
	559
	560	// find the best plane for node division
	561	SplitInfo * pqFindPlane(PlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA);
	562
	563	// priority queue based build function
	564	KdTree::Node * pqBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent);
	565	// recursive build function
	566	KdTree::Node * recBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent);
	567
	568	// recursive rendering function
[1206]	569	void recQueueVisibleObjects(KdTree::Node * node, unsigned long currentFrame, KdTreeCamera* cam,
	570	RenderQueue* queue, bool onlyShadowCasters, bool showBoxes,
	571	KdTree::NodeList& visibleNodes, bool fullVis = false);
[1163]	572
[1195]	573	// recursively find visible nodes
	574	//void recFindVisibleNodes(KdTree::Node * node, NodeList& visibleNodes, Camera * cam);
	575
[1163]	576	// the root node of the kdtree
	577	KdTree::Node * mKdRoot;
	578	// Maximum depth of the tree
	579	int mMaxDepth;
	580
	581	// how to build the tree
	582	BuildMethod mBuildMethod;
	583
	584	// logfile for tree creation
	585	Log * mBuildLog;
	586
[1182]	587	// statistical information
	588	Stats mStats;
	589
[1192]	590	/ Visualization flags /
	591	// show/highlight selected level in kdtree
	592	int mHiLiteLevel;
	593	// show whole kd-tree
	594	bool mShowAllBoxes;
	595	// show node or object boxes
	596	bool mShowNodes;
[1183]	597
[1211]	598	// pointer zur getVisibility function (simple oder enhanced)
	599	KdTreeCamera::NodeVisibility (KdTreeCamera::*getVisibility)(const AxisAlignedBox& box) const;
[1183]	600
[1163]	601	// DEBUG
	602	void KdTree::dump(KdTree::Node * node);
	603	Real KdTree::calcCost(KdTree::Node * node, Real vs);
	604	}; // class KdTree
	605
	606	} // namespace Ogre
	607
	608	#endif // _OgreKdTree_H__

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

Download in other formats: