Context Navigation

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

Revision 1211, 17.2 KB checked in by szydlowski, 18 years ago (diff)
enhanced visibility (none/full/partial) implemented for internal culling

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	// Gets this node's parent (NULL if this is the root).
217	KdTree::Node *getParent(void) const { return mParent; };
218
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
224	virtual void queueVisibleObjects(unsigned long currentFrame,
225	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes) = 0;
226
227	// add contained geometry (Entities) to list
228	virtual void getGeometryList(GtpVisibility::GeometryVector *geometryList) = 0;
229
230	// create (when necessary), setup and return wire bounding box representing the node
231	WireBoundingBox * getWireBoundingBox()
232	{
233	if (mWBB == 0)
234	mWBB = new WireBoundingBox();
235
236	if (mOwner->getShowNodes())
237	mWBB->setupBoundingBox(mAABB);
238	else
239	mWBB->setupBoundingBox(mWorldAABB);
240
241	if (mOwner->getHiLiteLevel() == mLevel)
242	mWBB->setMaterial("KdTree/BoxHiLite");
243	else
244	mWBB->setMaterial("BaseWhiteNoLighting");
245
246	return mWBB;
247	}
248
249	// returns the level the node is on
250	int getLevel(void) const { return mLevel; };
251
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; };
275	/** Returns real extent of the kdtree, i.e., the merged extent of the bounding boxes.
276	*/
277	AxisAlignedBox _getWorldAABB(void) const { return mAABB; };
278	/** Updates bound of the real aabb of kdtree
279	*/
280	virtual void _updateBounds(bool recurse = true) = 0;
281
282	/ bounding box of the node/
283	AxisAlignedBox mAABB;
284
285	/** mounding box of all objects inside the node */
286	AxisAlignedBox mWorldAABB;
287	protected:
288	KdTree * mOwner;
289	Branch * mParent;
290	int mLevel;
291
292	WireBoundingBox * mWBB;
293
294	// for the CHC hierarchy interface
295	unsigned int mLastRendered;
296	unsigned int mLastVisited;
297	bool mVisible;
298	};
299
300	class Branch : public Node
301	{
302	public:
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)
310	{ };
311
312	virtual ~Branch()
313	{
314	delete mLeft;
315	delete mRight;
316	delete mSplitPlane;
317	};
318
319	// a branch is not a leaf
320	virtual bool isLeaf() const { return false; };
321
322	// s branch is empty when it does not have children
323	virtual bool isEmpty() const { return (mLeft == 0 && mRight == 0); }
324
325	// a branch never has geometry
326	virtual bool hasGeometry() const { return false; };
327
328	// a branch should have at least one child
329	virtual KdTree::Node * getLeftChild() const { return mLeft; };
330	virtual KdTree::Node * getRightChild() const { return mRight; };
331
332	virtual void queueVisibleObjects(unsigned long currentFrame,
333	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes)
334	{
335	if (showBoxes)
336	if (mLevel == mOwner->getHiLiteLevel() \|\| mOwner->getShowAllBoxes())
337	queue->addRenderable(getWireBoundingBox());
338	}
339
340	// a branch has no geometry, do nothing
341	virtual void getGeometryList(GtpVisibility::GeometryVector *geometryList) { }
342
343	// branches do not posses geometry => just merge child aabbs
344	virtual void _updateBounds(bool recurse = true)
345	{
346	// reset box
347	mWorldAABB.setNull();
348
349	if (mLeft)
350	mWorldAABB.merge(mLeft->mWorldAABB);
351	if (mRight)
352	mWorldAABB.merge(mRight->mWorldAABB);
353
354	// update parent recursively
355	if (recurse && mParent)
356	mParent->_updateBounds(recurse);
357	}
358
359	Node * mLeft;
360	Node * mRight;
361	Plane * mSplitPlane;
362	PlaneEvent::Side mPlaneSide;
363	};
364
365	class Leaf : public Node
366	{
367	public:
368	Leaf(KdTree * owner, int level, AxisAlignedBox& aabb, Branch * parent):
369	Node(owner, level, aabb, parent)
370	{};
371
372	virtual ~Leaf();
373
374	// a leaf is a leaf, dammit
375	virtual bool isLeaf() const { return true; };
376
377	// a leaf is empty when it does not posses renderables
378	virtual bool isEmpty() const { return mKdRenderables.empty(); };
379
380	// a leaf has geometry when it has renderables
381	virtual bool hasGeometry() const { return !mKdRenderables.empty(); };
382
383	// a leaf never has children
384	virtual KdTree::Node * getLeftChild() const { return 0; };
385	virtual KdTree::Node * getRightChild() const { return 0; };
386
387	virtual void queueVisibleObjects(unsigned long currentFrame,
388	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes);
389
390	virtual void getGeometryList(GtpVisibility::GeometryVector *geometryList);
391
392	// update the world aabb based on the contained geometry
393	virtual void _updateBounds(bool recurse = true);
394
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	{
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	{ };
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
446	// typedef std::stack<SplitCandidate> SplitCandidatePQ;
447	typedef std::priority_queue<SplitCandidate> SplitCandidatePQ;
448
449	// nodestack for the stack-based rendering function
450	typedef std::stack<KdTree::Node *> NodeStack;
451	public:
452	friend class KdTreeHierarchyInterface;
453
454	typedef KdTree::Node * NodePtr;
455	typedef KdTree::Branch * BranchPtr;
456	typedef KdTree::Leaf * LeafPtr;
457
458	typedef std::list<NodePtr> NodeList;
459	typedef std::set<LeafPtr> LeafSet;
460
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
475	enum RenderMethod
476	{
477	KDRM_INTERNAL,
478	KDRM_GTP_VFC,
479	KDRM_GTP_SWC,
480	KDRM_GTP_CHC
481
482	};
483
484	enum BuildMethod
485	{
486	KDBM_RECURSIVE,
487	KDBM_PRIORITYQUEUE
488	};
489
490	const static int HILITE_OFF = -1;
491
492	KdTree(int maxdepth, BuildMethod bm);
493	KdTree(int maxdepth, BuildMethod bm, int hilite, bool allboxes, bool shownodes);
494	virtual ~KdTree();
495
496	// DEBUG
497	void dump(void);
498	Real calcCost(void);
499
500	// sets the level to highlight or turns it off (when hilite < 0)
501	inline void setHiLiteLevel(int hilite) { mHiLiteLevel = hilite; };
502	inline int getHiLiteLevel(void) { return mHiLiteLevel; };
503
504	// toggles displaying the kdtree boxes
505	inline void setShowAllBoxes(bool show) { mShowAllBoxes = show; };
506	inline bool getShowAllBoxes(void) { return mShowAllBoxes; };
507
508	// toggles between displaying the bounding box of the node and
509	// the box of the contained scene nodes
510	inline void setShowNodes(bool show = true) { mShowNodes = show; };
511	inline bool getShowNodes(void) { return mShowNodes; };
512
513	// changes vis mode (simple/enhanced with NONE/PART/FULL vis)
514	void setEnhancedVis(bool enh);
515	bool getEnhancedVis(void);
516
517	NodePtr getRoot(void) const { return mKdRoot; };
518
519	// insert a new scene node into an existing kd-tree
520	void insert(KdRenderable * rend);
521	// remove a scene node from the tree
522	void remove(KdRenderable * rend);
523	// function to initialize a kd-tree based on the contents of the scene
524	void build(KdRenderable * sceneRoot);
525
526	// test visibility of objects and add to render queue
527	void queueVisibleObjects(KdTreeCamera* cam, RenderQueue* queue, bool onlyShadowCasters,
528	bool showBoxes, KdTree::NodeList& visibleNodes);
529
530	// find visible nodes & place in list
531	//void findVisibleNodes(NodeList& visibleNodes, Camera * cam);
532
533	// self-explanatory ...
534	int getMaxDepth(void) { return mMaxDepth; };
535	Stats getStats(void) const { return mStats; };
536	AxisAlignedBox getBox(void) { if (mKdRoot) return mKdRoot->mAABB; else return AxisAlignedBox(); };
537	void setBuildMethod(BuildMethod bm) { mBuildMethod = bm; }
538	protected:
539	// init materials, logs and stuff
540	void init();
541	// recursive insert funciton
542	void recInsert(KdTree::Node * node, KdRenderable * rend);
543	// helper functions for insert
544	void recInsertNew(KdTree::Branch * parent, PlaneEvent::Side side, KdRenderable * rend);
545	void splitBox(const KdTree::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right);
546	void rebuildSubtree(KdTree::Node * node, KdRenderable * rend);
547	// build scene from a list of nodes rather than a hierarchy
548	KdTree::Node * buildFromList(KdRenderableList& nodelist, KdTree::Branch * parent, AxisAlignedBox& aabb);
549	void addRendToList(KdTree::Node * node, KdRenderableList& nodelist);
550
551	// recursively delete empty nodes
552	void recDelete(KdTree::Node * node);
553
554	// find the best plane for node division
555	SplitInfo * pqFindPlane(PlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA);
556
557	// priority queue based build function
558	KdTree::Node * pqBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent);
559	// recursive build function
560	KdTree::Node * recBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent);
561
562	// recursive rendering function
563	void recQueueVisibleObjects(KdTree::Node * node, unsigned long currentFrame, KdTreeCamera* cam,
564	RenderQueue* queue, bool onlyShadowCasters, bool showBoxes,
565	KdTree::NodeList& visibleNodes, bool fullVis = false);
566
567	// recursively find visible nodes
568	//void recFindVisibleNodes(KdTree::Node * node, NodeList& visibleNodes, Camera * cam);
569
570	// the root node of the kdtree
571	KdTree::Node * mKdRoot;
572	// Maximum depth of the tree
573	int mMaxDepth;
574
575	// how to build the tree
576	BuildMethod mBuildMethod;
577
578	// logfile for tree creation
579	Log * mBuildLog;
580
581	// statistical information
582	Stats mStats;
583
584	/ Visualization flags /
585	// show/highlight selected level in kdtree
586	int mHiLiteLevel;
587	// show whole kd-tree
588	bool mShowAllBoxes;
589	// show node or object boxes
590	bool mShowNodes;
591
592	// pointer zur getVisibility function (simple oder enhanced)
593	KdTreeCamera::NodeVisibility (KdTreeCamera::*getVisibility)(const AxisAlignedBox& box) const;
594
595	// DEBUG
596	void KdTree::dump(KdTree::Node * node);
597	Real KdTree::calcCost(KdTree::Node * node, Real vs);
598	}; // class KdTree
599
600	} // namespace Ogre
601
602	#endif // _OgreKdTree_H__

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

Download in other formats: