Context Navigation

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

Revision 1312, 19.9 KB checked in by szydlowski, 18 years ago (diff)
per-frame-stats with internal rendering - use depth pass issue unresolved

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
34
35	namespace Ogre
36	{
37	class KdTreeCamera;
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:
199	Node(KdTree * owner, int level, AxisAlignedBox& aabb, Branch * parent):
200	mOwner(owner),
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;
214	virtual bool hasGeometry() const = 0;
215
216	virtual void mergeLeaves(std::set<Leaf *>& leaves) = 0;
217
218	// Gets this node's parent (NULL if this is the root).
219	KdTree::Node *getParent(void) const { return mParent; };
220
221	// Gets the nodes left & right child nodes, or NULL if not present or node is leaf
222	virtual KdTree::Node *getLeftChild(void) const = 0;
223	virtual KdTree::Node *getRightChild(void) const = 0;
224
225	// add contained objects to render queue
226	virtual void queueVisibleObjects(unsigned long currentFrame,
227	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis = false) = 0;
228
229	// add contained geometry (Entities) to list
230	virtual void getGeometryList(GtpVisibility::GeometryVector *geometryList) = 0;
231
232	// create (when necessary), setup and return wire bounding box representing the node
233	WireBoundingBox * getWireBoundingBox()
234	{
235	if (mWBB == 0)
236	mWBB = new WireBoundingBox();
237
238	if (mOwner->getShowNodes())
239	mWBB->setupBoundingBox(mAABB);
240	else
241	mWBB->setupBoundingBox(mWorldAABB);
242
243	if (mOwner->getHiLiteLevel() == mLevel)
244	mWBB->setMaterial("KdTree/BoxHiLite");
245	else
246	mWBB->setMaterial("BaseWhiteNoLighting");
247
248	return mWBB;
249	}
250
251	// returns the level the node is on
252	int getLevel(void) const { return mLevel; };
253
254	// functions for the CHC hierarchy interface
255
256	/** Returns last visited frame id. */
257	unsigned int lastVisited(void) { return mLastVisited; };
258	/** Set to current frame id.
259	@param current frame id.
260	*/
261	void setLastVisited(unsigned int frameid) { mLastVisited = frameid; };
262	/** Makes this octree become visible / invisble.
263	@param visible Whether this node is to be made visible or invisible
264	*/
265	void setNodeVisible(bool visible) { mVisible = visible; };
266	/** Returns true if this node is marked visible, false otherwise.
267	*/
268	bool isNodeVisible(void) { return mVisible; };
269	/** Frame id when this octree was last rendered.
270	@return last rendered frame id
271	*/
272	unsigned int lastRendered(void) { return mLastRendered; };
273	/** Sets frame id when this octree was last rendered.
274	@param last rendered frame id
275	*/
276	void setLastRendered(unsigned int frameid) { mLastRendered = frameid; };
277	/** Returns real extent of the kdtree, i.e., the merged extent of the bounding boxes.
278	*/
279	AxisAlignedBox _getWorldAABB(void) const { return mAABB; };
280	/** Updates bound of the real aabb of kdtree
281	*/
282	virtual void _updateBounds(bool recurse = true) = 0;
283
284	/ bounding box of the node/
285	AxisAlignedBox mAABB;
286
287	/** mounding box of all objects inside the node */
288	AxisAlignedBox mWorldAABB;
289	protected:
290	KdTree * mOwner;
291	Branch * mParent;
292	int mLevel;
293
294	WireBoundingBox * mWBB;
295
296	// for the CHC hierarchy interface
297	unsigned int mLastRendered;
298	unsigned int mLastVisited;
299	bool mVisible;
300	};
301
302	class Branch : public Node
303	{
304	public:
305	Branch(KdTree * owner, int level, AxisAlignedBox& aabb, Branch * parent,
306	Plane * splitplane, PlaneEvent::Side side):
307	Node(owner, level, aabb, parent),
308	mSplitPlane(splitplane),
309	mLeft(0),
310	mRight(0),
311	mPlaneSide(side)
312	{ };
313
314	virtual ~Branch()
315	{
316	delete mLeft;
317	delete mRight;
318	delete mSplitPlane;
319	};
320
321	// a branch is not a leaf
322	virtual bool isLeaf() const { return false; };
323
324	// s branch is empty when it does not have children
325	virtual bool isEmpty() const { return (mLeft == 0 && mRight == 0); }
326
327	// a branch never has geometry
328	virtual bool hasGeometry() const { return false; };
329
330	virtual void mergeLeaves(std::set<Leaf *>& leaves)
331	{
332	for (std::set<Leaf *>::iterator it = mLeaves.begin(); it != mLeaves.end(); it++)
333	leaves.insert(*it);
334	}
335
336	// a branch should have at least one child
337	virtual KdTree::Node * getLeftChild() const { return mLeft; };
338	virtual KdTree::Node * getRightChild() const { return mRight; };
339
340	virtual void queueVisibleObjects(unsigned long currentFrame,
341	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis = false)
342	{
343	if (showBoxes)
344	if (mLevel == mOwner->getHiLiteLevel() \|\| mOwner->getShowAllBoxes())
345	queue->addRenderable(getWireBoundingBox());
346
347	if (fullVis)
348	for (std::set<Leaf *>::iterator it = mLeaves.begin(); it != mLeaves.end(); it ++)
349	(*it)->queueVisibleObjects(currentFrame, cam, queue, onlyShadowCasters, showBoxes, fullVis);
350	}
351
352	// a branch has no geometry, do nothing
353	virtual void getGeometryList(GtpVisibility::GeometryVector *geometryList) { }
354
355	// branches do not posses geometry => just merge child aabbs
356	virtual void _updateBounds(bool recurse = true)
357	{
358	// reset box
359	mWorldAABB.setNull();
360
361	// merge box & leaves
362	if (mLeft)
363	{
364	mWorldAABB.merge(mLeft->mWorldAABB);
365	mLeft->mergeLeaves(mLeaves);
366	}
367	if (mRight)
368	{
369	mWorldAABB.merge(mRight->mWorldAABB);
370	mRight->mergeLeaves(mLeaves);
371	}
372
373	// update parent recursively
374	if (recurse && mParent)
375	mParent->_updateBounds(recurse);
376	}
377
378	Node * mLeft;
379	Node * mRight;
380	Plane * mSplitPlane;
381	PlaneEvent::Side mPlaneSide;
382	protected:
383	std::set<Leaf *> mLeaves;
384	};
385
386	class Leaf : public Node
387	{
388	public:
389	Leaf(KdTree * owner, int level, AxisAlignedBox& aabb, Branch * parent):
390	Node(owner, level, aabb, parent)
391	{};
392
393	virtual ~Leaf();
394
395	// a leaf is a leaf, dammit
396	virtual bool isLeaf() const { return true; }
397
398	// a leaf is empty when it does not posses renderables
399	virtual bool isEmpty() const { return mKdRenderables.empty(); }
400
401	// a leaf has geometry when it has renderables
402	virtual bool hasGeometry() const { return !mKdRenderables.empty(); }
403
404	// a leaf adds itself to the leaf set
405	virtual void mergeLeaves(std::set<Leaf *>& leaves) { leaves.insert(this); }
406
407	// a leaf never has children
408	virtual KdTree::Node * getLeftChild() const { return 0; };
409	virtual KdTree::Node * getRightChild() const { return 0; };
410
411	virtual void queueVisibleObjects(unsigned long currentFrame,
412	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis = false);
413
414	virtual void getGeometryList(GtpVisibility::GeometryVector *geometryList);
415
416	// update the world aabb based on the contained geometry
417	virtual void _updateBounds(bool recurse = true);
418
419	virtual void remove(KdRenderable * rend)
420	{
421	mKdRenderables.remove(rend);
422	//mKdRenderables.erase(find(mKdRenderables.begin(), mKdRenderables.end(), rend));
423	};
424
425	virtual void insert(KdRenderable * rend)
426	{
427	mKdRenderables.push_back(rend);
428	};
429
430	KdRenderableList mKdRenderables;
431	};
432
433	struct SplitCandidate
434	{
435	SplitCandidate(PlaneEventList * e, int n, AxisAlignedBox& a,
436	KdTree::Branch * p, Real c, Real d, SplitInfo * b, PlaneEvent::Side s):
437	events(e), nObjects(n), aabb(a), parent(p), cost(c), decrease(d), best(b), side(s)
438	{ };
439
440	bool operator < (const SplitCandidate& rhs) const
441	{
442	return decrease < rhs.decrease;
443	};
444
445	void operator = (const SplitCandidate& rhs)
446	{
447	decrease = rhs.decrease;
448	cost = rhs.cost;
449	nObjects = rhs.nObjects;
450	side = rhs.side;
451	aabb = rhs.aabb;
452	events = rhs.events;
453	parent = rhs.parent;
454	best = rhs.best;
455	};
456
457	// DEBUG
458	String print();
459
460	Real decrease;
461	Real cost;
462	int nObjects;
463	PlaneEvent::Side side;
464	AxisAlignedBox aabb;
465	PlaneEventList * events;
466	KdTree::Branch * parent;
467	SplitInfo * best;
468	};
469
470	// typedef std::stack<SplitCandidate> SplitCandidatePQ;
471	typedef std::priority_queue<SplitCandidate> SplitCandidatePQ;
472
473	// nodestack for the stack-based rendering function
474	typedef std::stack<KdTree::Node *> NodeStack;
475	public:
476	friend class KdTreeHierarchyInterface;
477
478	typedef KdTree::Node * NodePtr;
479	typedef KdTree::Branch * BranchPtr;
480	typedef KdTree::Leaf * LeafPtr;
481
482	typedef std::list<NodePtr> NodeList;
483	typedef std::set<LeafPtr> LeafSet;
484
485	struct TreeStats
486	{
487	unsigned int mNumNodes;
488	unsigned int mNumLeaves;
489	unsigned int mNumSceneNodes;
490
491	void clear(void)
492	{
493	mNumNodes = 0;
494	mNumLeaves = 0;
495	mNumSceneNodes = 0;
496	}
497	};
498
499	struct FrameStats
500	{
501	unsigned int mTraversedNodes;
502	unsigned int mRenderedNodes;
503	unsigned int mFrustumCulledNodes;
504
505	void clear(void)
506	{
507	mTraversedNodes = 0;
508	mRenderedNodes = 0;
509	mFrustumCulledNodes = 0;
510	}
511	};
512
513	enum RenderMethod
514	{
515	KDRM_INTERNAL,
516	KDRM_GTP_VFC,
517	KDRM_GTP_SWC,
518	KDRM_GTP_CHC,
519	// invalid modes, just for convenience
520	KDRM_SIZE,
521	KDRM_NOTSET
522	};
523
524	enum BuildMethod
525	{
526	KDBM_RECURSIVE,
527	KDBM_PRIORITYQUEUE,
528	// invalid modes, just for convenience
529	KDBM_SIZE,
530	KDBM_NOTSET
531	};
532
533
534	const static int HILITE_OFF = -1;
535
536	KdTree(int maxdepth, BuildMethod bm);
537	KdTree(int maxdepth, BuildMethod bm, int hilite, bool allboxes, bool shownodes);
538	virtual ~KdTree();
539
540	// DEBUG
541	void dump(void);
542	Real calcCost(void);
543
544	// sets the level to highlight or turns it off (when hilite < 0)
545	inline void setHiLiteLevel(int hilite) { mHiLiteLevel = hilite; };
546	inline int getHiLiteLevel(void) { return mHiLiteLevel; };
547
548	// toggles displaying the kdtree boxes
549	inline void setShowAllBoxes(bool show) { mShowAllBoxes = show; };
550	inline bool getShowAllBoxes(void) { return mShowAllBoxes; };
551
552	// toggles between displaying the bounding box of the node and
553	// the box of the contained scene nodes
554	inline void setShowNodes(bool show = true) { mShowNodes = show; };
555	inline bool getShowNodes(void) { return mShowNodes; };
556
557	// changes vis mode (simple/enhanced with NONE/PART/FULL vis)
558	void setEnhancedVis(bool enh);
559	bool getEnhancedVis(void);
560
561	NodePtr getRoot(void) const { return mKdRoot; };
562
563	// insert a new scene node into an existing kd-tree
564	void insert(KdRenderable * rend);
565	// remove a scene node from the tree
566	void remove(KdRenderable * rend);
567	// function to initialize a kd-tree based on the contents of the scene
568	void build(KdRenderable * sceneRoot);
569
570	// test visibility of objects and add to render queue
571	void queueVisibleObjects(KdTreeCamera* cam, RenderQueue* queue, bool onlyShadowCasters,
572	bool showBoxes, KdTree::NodeList& visibleNodes);
573
574	// find visible nodes & place in list
575	//void findVisibleNodes(NodeList& visibleNodes, Camera * cam);
576
577	/** Recurses the kdtree, adding any nodes intersecting with the
578	box/sphere/volume/ray into the given list.
579	It ignores the exclude scene node.
580	*/
581	void findNodesIn(const AxisAlignedBox &box, std::list<SceneNode > &list, SceneNode exclude = 0);
582	void findNodesIn(const Sphere &sphere, std::list<SceneNode > &list, SceneNode exclude = 0);
583	void findNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode > &list, SceneNode exclude = 0);
584	void findNodesIn(const Ray &ray, std::list<SceneNode > &list, SceneNode exclude = 0);
585
586	// self-explanatory ...
587	int getMaxDepth(void) { return mMaxDepth; }
588	const TreeStats& getTreeStats(void) const { return mTreeStats; }
589	const FrameStats& getFramesStats(void) const { return mFrameStats; }
590	AxisAlignedBox getBox(void) { if (mKdRoot) return mKdRoot->mAABB; else return AxisAlignedBox(); }
591	void setBuildMethod(BuildMethod bm) { mBuildMethod = bm; }
592	protected:
593	// init materials, logs and stuff
594	void init();
595	// recursive insert funciton
596	void recInsert(KdTree::Node * node, KdRenderable * rend);
597	// helper functions for insert
598	void recInsertNew(KdTree::Branch * parent, PlaneEvent::Side side, KdRenderable * rend);
599	void splitBox(const KdTree::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right);
600	void rebuildSubtree(KdTree::Node * node, KdRenderable * rend);
601	// build scene from a list of nodes rather than a hierarchy
602	KdTree::Node * buildFromList(KdRenderableList& nodelist, KdTree::Branch * parent, AxisAlignedBox& aabb);
603	void addRendToList(KdTree::Node * node, KdRenderableList& nodelist);
604
605	// recursively delete empty nodes
606	void recDelete(KdTree::Node * node);
607
608	// find the best plane for node division
609	SplitInfo * pqFindPlane(PlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA);
610
611	// priority queue based build function
612	KdTree::Node * pqBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent);
613	// recursive build function
614	KdTree::Node * recBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent);
615
616	// recursive rendering function
617	void recQueueVisibleObjects(KdTree::Node * node, unsigned long currentFrame, KdTreeCamera* cam,
618	RenderQueue* queue, bool onlyShadowCasters, bool showBoxes,
619	KdTree::NodeList& visibleNodes, bool fullVis = false);
620
621	// recursively find visible nodes
622	//void recFindVisibleNodes(KdTree::Node * node, NodeList& visibleNodes, Camera * cam);
623
624	/** Recurses the kdtree, adding any nodes intersecting with the
625	box/sphere/volume/ray into the given list.
626	It ignores the exclude scene node.
627	*/
628	void recFindNodesIn(const AxisAlignedBox &box, std::list<SceneNode > &list, SceneNode exclude, Node * node, bool full = false);
629	void recFindNodesIn(const Sphere &sphere, std::list<SceneNode > &list, SceneNode exclude, Node * node, bool full = false);
630	void recFindNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode > &list, SceneNode exclude, Node * node, bool full = false);
631	void recFindNodesIn(const Ray &ray, std::list<SceneNode > &list, SceneNode exclude, Node * node, bool full = false);
632
633	// the root node of the kdtree
634	KdTree::Node * mKdRoot;
635	// Maximum depth of the tree
636	int mMaxDepth;
637
638	// how to build the tree
639	BuildMethod mBuildMethod;
640
641	// logfile for tree creation
642	Log * mBuildLog;
643
644	// statistical information on the tree
645	TreeStats mTreeStats;
646
647	// statistical info on a single rendered frame
648	FrameStats mFrameStats;
649
650	/ Visualization flags /
651	// show/highlight selected level in kdtree
652	int mHiLiteLevel;
653	// show whole kd-tree
654	bool mShowAllBoxes;
655	// show node or object boxes
656	bool mShowNodes;
657
658	// function pointer to the getVisibility function
659	// allows choosing between regular vis (NONE/PART, same es isVisible)
660	// and enhaced vis (NONE/PART/FULL) for early traversal abort
661	KdTreeCamera::NodeVisibility (KdTreeCamera::*getVisibility)(const AxisAlignedBox& box) const;
662
663	// DEBUG
664	void KdTree::dump(KdTree::Node * node);
665	Real KdTree::calcCost(KdTree::Node * node, Real vs);
666	}; // class KdTree
667
668	} // namespace Ogre
669
670	#endif // _OgreKdTree_H__

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

Download in other formats: