Context Navigation

OgreKdTree.h @ 2280

Revision 2280, 19.9 KB checked in by mattausch, 17 years ago (diff)
removed dependency on ogre in gtpvisibility

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

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

Context Navigation

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

Download in other formats: