Context Navigation

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

Revision 1206, 16.9 KB checked in by szydlowski, 18 years ago (diff)
enhanced visibility partially implemented

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

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

Download in other formats: