Context Navigation

source: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreKdTree.cpp @ 1195

Revision 1195, 41.7 KB checked in by szydlowski, 18 years ago (diff)
visualization workin' fine (TM) demo recording/playback 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	#include <OgreCamera.h>
11	#include "OgreKdTree.h"
12	#include "OgreKdRenderable.h"
13	#include "OgreKdTreeSceneNode.h"
14	#include "OgreKdTreeSceneManager.h"
15
16	#include <OgreStringConverter.h>
17	#include <OgreLogManager.h>
18	#include <OgreRoot.h>
19	#include <OgreTimer.h>
20
21	#include <OgreMaterialManager.h>
22
23	#define KDTREE_LOGNAME "KdTreeBuild.log"
24	#define PLT_SIZE 101
25
26	namespace Ogre
27	{
28	Real PlaneEvent::KT = 2.0;
29	Real PlaneEvent::KI = 1.0;
30
31	//----------------------------------------------------------------------------
32	// determine if this event is left or right of the reference event
33	void PlaneEvent::classify(const PlaneEvent& e, PlaneEvent::Side side)
34	{
35	// only classify events of the same dimension
36	if (mDimension == e.mDimension)
37	{
38	if (mType == PET_END && mPosition[mDimension] <= e.mPosition[e.mDimension])
39	{
40	mRenderable->setSide(PES_LEFT);
41	}
42	else if (mType == PET_START && mPosition[mDimension] >= e.mPosition[e.mDimension])
43	{
44	mRenderable->setSide(PES_RIGHT);
45	}
46	else if (mType == PET_ON)
47	{
48	if (mPosition[mDimension] < e.mPosition[e.mDimension] \|\|
49	(mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_LEFT))
50	{
51	mRenderable->setSide(PES_LEFT);
52	}
53	if (mPosition[mDimension] > e.mPosition[e.mDimension] \|\|
54	(mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_RIGHT))
55	{
56	mRenderable->setSide(PES_RIGHT);
57	}
58	}
59	}
60	}
61
62	//----------------------------------------------------------------------------
63	// clip this event to an aabb (move it so that the plane on one of the box planes)
64	PlaneEvent PlaneEvent::clip(AxisAlignedBox& box, PlaneEvent::Dimension dim)
65	{
66	Vector3 newpos = mPosition, min = box.getMinimum(), max = box.getMaximum();
67	if (newpos[dim] < min[dim])
68	newpos[dim] = min[dim];
69	else if (newpos[dim] > max[dim])
70	newpos[dim] = max[dim];
71
72	return PlaneEvent(mRenderable, newpos, mDimension, mType);
73	}
74
75	//----------------------------------------------------------------------------
76	// the surface area heuristic to determine the cost of splitting the parent aabb
77	// along the plane represented by this event
78	void PlaneEvent::SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, SplitInfo& split)
79	{
80	Real mu = splitBox(parent, split.bleft, split.bright);
81	Real sav = surfaceArea(parent);
82	Real pl = surfaceArea(split.bleft) / sav;
83	Real pr = surfaceArea(split.bright) / sav;
84	Real costl = splitCost(pl, pr, nLeft + nPlane, nRight, mu);
85	Real costr = splitCost(pl, pr, nLeft, nPlane + nRight, mu);
86
87	if (costl < costr)
88	{
89	split.cost = costl;
90	split.side = PES_LEFT;
91	split.nleft = nLeft + nPlane;
92	split.nright = nRight;
93	}
94	else
95	{
96	split.cost = costr;
97	split.side = PES_RIGHT;
98	split.nleft = nLeft;
99	split.nright = nPlane + nRight;
100
101	}
102	split.event = *this;
103	}
104
105	//----------------------------------------------------------------------------
106	// split the parent aabb with the plane in this event
107	Real PlaneEvent::splitBox(const AxisAlignedBox& parent, AxisAlignedBox& left, AxisAlignedBox& right)
108	{
109	Vector3 bmin = parent.getMinimum();
110	Vector3 bmax = parent.getMaximum();
111	// calculate the penalty for spliting the box that way
112	Real mu = lookupPenalty(
113	(mPosition[mDimension] - bmin[mDimension]) /
114	(bmax[mDimension] - bmin[mDimension]));
115	// set corners which are the same as parent AABB
116	left.setMinimum(bmin);
117	right.setMaximum(bmax);
118	// modify "inner" corners
119	bmin[mDimension] = mPosition[mDimension];
120	bmax[mDimension] = mPosition[mDimension];
121	// set the corners on the split plane
122	left.setMaximum(bmax);
123	right.setMinimum(bmin);
124
125	return mu;
126	}
127
128	//----------------------------------------------------------------------------
129	// compute surface area of a box ... DUH!
130	Real PlaneEvent::surfaceArea(const AxisAlignedBox& box)
131	{
132	Vector3 sides = box.getMaximum() - box.getMinimum();
133	return 2 * sides.x * sides.y +
134	2 * sides.y * sides.z +
135	2 * sides.z * sides.x;
136	}
137
138	//----------------------------------------------------------------------------
139	// lookup the penalty for placing the splitting plane near to the edge of the AABB
140	// 0.0 <= p <= 1.0, p = 0.5 means the plane divides the aabb in half
141	Real PlaneEvent::lookupPenalty(Real p)
142	{
143	// precomputed table of {x^6 + 1\|0 <= x <= 1}
144	static Real mPenaltyLookupTable[PLT_SIZE];
145	static bool init_done = false;
146
147	if (!init_done)
148	{
149	Real step = 1.0 / (PLT_SIZE - 1);
150	Real x = 0.0;
151	//LogManager::getSingleton().logMessage("### Calculating Lookup Table ###");
152	for (int i = 0; i < PLT_SIZE; i++)
153	{
154	mPenaltyLookupTable[i] = Math::Pow(x, 6) + 1.0;
155	x += step;
156	//LogManager::getSingleton().logMessage("### mPenaltyLookupTable[" + StringConverter::toString(i,3) + "]=" + StringConverter::toString(mPenaltyLookupTable[i]));
157	}
158	init_done = true;
159	//LogManager::getSingleton().logMessage("### Lookup Table Calculated ###");
160	}
161
162	// normalize p to [0,1]
163	Real x = Math::Abs(p * 2 - 1);
164	// compute index
165	int i = Math::IFloor(x * (PLT_SIZE - 1));
166
167	return mPenaltyLookupTable[i];
168	}
169
170	//----------------------------------------------------------------------------
171	// compute cost of the split, reward splitting of empty space (lambda, const),
172	// penalize splitting off 'thin' slices (mu, const)
173	Real PlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight)
174	{
175	// reward splitting off chunks of empty space
176	Real lambda = 1.0;
177	if (nLeft == 0 \|\| nRight == 0)
178	{
179	lambda = 0.8;
180	}
181
182	// penalize splitting off small chunks (thin slices)
183	Real mu = 1.0;
184	if (pLeft < 0.1 \|\| pRight < 0.1 \|\| pLeft > 0.9 \|\| pRight > 0.9)
185	{
186	mu = 1.5;
187	}
188	return lambda * mu * (KT + (KI * (pLeftnLeft + pRightnRight)));
189	}
190
191	//----------------------------------------------------------------------------
192	// compute cost of the split, reward splitting of empty space (lambda, const),
193	// penalize splitting off 'thin' slices (mu, parameter)
194	Real PlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
195	{
196	// reward splitting off chunks of empty space
197	Real lambda = 1.0;
198	if (nLeft == 0 \|\| nRight == 0)
199	{
200	lambda = 0.8;
201	}
202
203	return lambda * mu * (KT + (KI * (pLeftnLeft + pRightnRight)));
204	}
205
206	//----------------------------------------------------------------------------
207	// surface area heuristic modified for the priority queue method of building
208	// the probabilities (p, pl, pr) are relative to the global (all enclosing) aabb
209	void PlaneEvent::pqSAH(Real globalSA, Real parentSA, int nLeft, int nPlane, int nRight,
210	AxisAlignedBox& parentBox, SplitInfo& split)
211	{
212	Real mu = splitBox(parentBox, split.bleft, split.bright);
213	Real p = parentSA / globalSA;
214	Real pl = surfaceArea(split.bleft) / globalSA;
215	Real pr = surfaceArea(split.bright) / globalSA;
216	Real costl = pqSplitCost(p, pl, pr, nLeft + nPlane, nRight, mu);
217	Real costr = pqSplitCost(p, pl, pr, nLeft, nPlane + nRight, mu);
218
219	if (costl < costr)
220	{
221	split.cost = costl;
222	split.side = PES_LEFT;
223	split.nleft = nLeft + nPlane;
224	split.nright = nRight;
225	}
226	else
227	{
228	split.cost = costr;
229	split.side = PES_RIGHT;
230	split.nleft = nLeft;
231	split.nright = nPlane + nRight;
232
233	}
234	split.event = *this;
235	}
236
237	//----------------------------------------------------------------------------
238	// compute split cost without any penalties
239	Real PlaneEvent::pqSplitCost(Real pParent, Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
240	{
241	return pParent * KT + (KI * (pLeft * nLeft + pRight * nRight));
242	}
243
244	//----------------------------------------------------------------------------
245	// DEBUG
246	String PlaneEvent::print()
247	{
248	String dim, type;
249	if (mDimension == PED_X)
250	dim = "X";
251	if (mDimension == PED_Y)
252	dim = "Y";
253	if (mDimension == PED_Z)
254	dim = "Z";
255	if (mType == PET_END)
256	type = "END ";
257	if (mType == PET_ON)
258	type = "ON ";
259	if (mType == PET_START)
260	type = "START";
261	//return StringConverter::toString(mPosition[mDimension]) + " " + dim + " " + type;
262	return type + " " + dim + " " + StringConverter::toString(mPosition[mDimension]);
263	};
264
265	//----------------------------------------------------------------------------
266	String SplitInfo::print()
267	{
268	String sside;
269	if (side == PlaneEvent::PES_BOTH)
270	sside = "BOTH ";
271	if (side == PlaneEvent::PES_LEFT)
272	sside = "LEFT ";
273	if (side == PlaneEvent::PES_RIGHT)
274	sside = "RIGHT";
275	return "nLeft: " + StringConverter::toString(nleft, 4) + " nRight: " +
276	StringConverter::toString(nright, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
277	" Side: " + sside + " Event: " + event.print() + " Leftbox: " +
278	StringConverter::toString(bleft.getMinimum()) + ", " +
279	StringConverter::toString(bleft.getMaximum()) + " Rightbox: " +
280	StringConverter::toString(bright.getMinimum()) + ", " +
281	StringConverter::toString(bright.getMaximum());
282	};
283
284	//----------------------------------------------------------------------------
285	String KdTree::SplitCandidate::print()
286	{
287	String sside;
288	if (side == PlaneEvent::PES_BOTH)
289	sside = "BOTH ";
290	if (side == PlaneEvent::PES_LEFT)
291	sside = "LEFT ";
292	if (side == PlaneEvent::PES_RIGHT)
293	sside = "RIGHT";
294	return "List: " + StringConverter::toString(events->size(), 4) + " Objects: " +
295	StringConverter::toString(nObjects, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
296	" Decrease: " + StringConverter::toString(decrease, 8, 9) + " Side: " + sside + " Best: " +
297	best->print() + " Box: " + StringConverter::toString(aabb.getMinimum()) + ", "
298	+ StringConverter::toString(aabb.getMaximum());
299
300	};
301
302	//----------------------------------------------------------------------------
303	//----------------------------------------------------------------------------
304	//----------------------------------------------------------------------------
305
306	KdTree::KdTree(int maxdepth, BuildMethod bm):
307	mMaxDepth(maxdepth),
308	mBuildMethod(bm),
309	mHiLiteLevel(0),
310	mShowAllBoxes(false),
311	mShowNodes(true),
312	mKdRoot(0),
313	mBuildLog(0)
314	{
315	init();
316	}
317
318	KdTree::KdTree(int maxdepth, BuildMethod bm, int hilite, bool allboxes, bool shownodes):
319	mMaxDepth(maxdepth),
320	mBuildMethod(bm),
321	mHiLiteLevel(hilite),
322	mShowAllBoxes(allboxes),
323	mShowNodes(shownodes),
324	mKdRoot(0),
325	mBuildLog(0)
326	{
327	init();
328	}
329
330	KdTree::~KdTree()
331	{
332	delete mKdRoot;
333	}
334
335	void KdTree::init()
336	{
337	MaterialPtr mat;
338	TextureUnitState *tex;
339
340	// init visualization materials (unlit solid green/yellow)
341	mat = MaterialManager::getSingleton().getByName("KdTree/BoxHiLite");
342	if (mat.isNull())
343	{
344	ColourValue green(0, 1, 0);
345	mat = MaterialManager::getSingleton().create("KdTree/BoxHiLite", "General");
346	//mat->setAmbient(green);
347	//mat->setDiffuse(green);
348	mat->setLightingEnabled(false);
349	tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
350	tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, green, green);
351	}
352
353	mat = MaterialManager::getSingleton().getByName("KdTree/BoxViz");
354	if (mat.isNull())
355	{
356	ColourValue yellow(1, 1, 0);
357	mat = MaterialManager::getSingleton().create("KdTree/BoxViz", "General");
358	//mat->setAmbient(yellow);
359	//mat->setDiffuse(yellow);
360	mat->setLightingEnabled(false);
361	tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
362	tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, yellow, yellow);
363	}
364
365	// retrieve or create build log
366	try
367	{
368	mBuildLog = LogManager::getSingleton().getLog(KDTREE_LOGNAME);
369	}
370	catch (Exception&)
371	{
372	mBuildLog = LogManager::getSingleton().createLog(KDTREE_LOGNAME);
373	}
374	}
375
376	/************************************************************************/
377	/* KdTree insert/delete functions */
378	/************************************************************************/
379
380	void KdTree::remove(KdRenderable * rend)
381	{
382	// DEBUG
383	//LogManager::getSingleton().logMessage("-- Removing SceneNode: " + (static_cast<KdTreeSceneNode *>(rend))->getName());
384	std::queue<LeafPtr> cleanup;
385	LeafPtr leaf;
386	LeafSet ls = rend->getLeaves();
387	LeafSet::iterator it = ls.begin();
388	LeafSet::iterator end = ls.end();
389	while (it != end)
390	{
391	cleanup.push(*it);
392	it++;
393	}
394	while (!cleanup.empty())
395	{
396	leaf = cleanup.front();
397	cleanup.pop();
398	leaf->remove(rend);
399	bool gone = rend->detachFrom(leaf);
400	assert(gone && "Failed to detach leave which is abso-fuckin-lutely impossible!!!");
401	//dump();
402	recDelete(leaf);
403	//dump();
404	}
405	}
406
407	void KdTree::recDelete(KdTree::Node * node)
408	{
409	if (node == 0) // DEBUG
410	{
411	OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
412	"SNAFU while inserting KdRenderable into KdTree.",
413	"KdTree::recInsert" );
414	return;
415	}
416
417	if (node->isEmpty())
418	{
419	if (node == mKdRoot)
420	{
421	OGRE_DELETE(mKdRoot);
422	}
423	else
424	{
425	KdTree::Branch * parent = KDBRANCHPTR_CAST(node->getParent());
426	if (node == parent->mLeft)
427	{
428	OGRE_DELETE(parent->mLeft);
429	}
430	else if (node == parent->mRight)
431	{
432	OGRE_DELETE(parent->mRight);
433	}
434	recDelete(parent);
435	}
436	}
437	}
438
439	void KdTree::insert(KdRenderable * rend)
440	{
441	// make sure the tree exists
442	if (mKdRoot)
443	{
444	// make sure the renderable is inside the world bounding box
445	AxisAlignedBox aabb = rend->getBoundingBox();
446	AxisAlignedBox isect = mKdRoot->mAABB.intersection(aabb);
447	if (isect.getMinimum() == aabb.getMinimum() && isect.getMaximum() == aabb.getMaximum())
448	{
449	recInsert(mKdRoot, rend);
450	}
451	else
452	{
453	//LogManager::getSingleton().logMessage("Inserted node outside of world AABB.");
454	KdRenderableList nodelist;
455	nodelist.push_back(rend);
456	addRendToList(mKdRoot, nodelist);
457	OGRE_DELETE(mKdRoot);
458	mKdRoot = buildFromList(nodelist, 0, AxisAlignedBox());
459	}
460	}
461	// otherwise build a new one
462	else
463	{
464	build(rend);
465	}
466	}
467
468	void KdTree::recInsert(KdTree::Node * node, KdRenderable * rend)
469	{
470	if (node == 0) // DEBUG
471	{
472	OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
473	"SNAFU while inserting KdRenderable into KdTree.",
474	"KdTree::recInsert" );
475	return;
476	}
477
478	// rebuild the leaf/replace with subtree ...
479	if (node->isLeaf())
480	{
481	//LogManager::getSingleton().logMessage("## Replacing leaf.");
482	rebuildSubtree(node, rend);
483	}
484	else
485	{
486	KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
487	AxisAlignedBox aabb = rend->getBoundingBox();
488	Plane::Side smin = branch->mSplitPlane->getSide(aabb.getMinimum());
489	Plane::Side smax = branch->mSplitPlane->getSide(aabb.getMaximum());
490	if (smin == smax)
491	{
492	if (smax == Plane::NEGATIVE_SIDE \|\|
493	(smax == Plane::NO_SIDE && branch->mPlaneSide == PlaneEvent::PES_LEFT))
494	{
495	if (branch->mLeft)
496	recInsert(branch->mLeft, rend);
497	else
498	recInsertNew(branch, PlaneEvent::PES_LEFT, rend);
499	}
500	else if (smin == Plane::POSITIVE_SIDE \|\|
501	(smin == Plane::NO_SIDE && branch->mPlaneSide == PlaneEvent::PES_RIGHT))
502	{
503	if (branch->mRight)
504	recInsert(branch->mRight, rend);
505	else
506	recInsertNew(branch, PlaneEvent::PES_RIGHT, rend);
507	}
508	}
509	else
510	{
511	if (smin == Plane::NEGATIVE_SIDE && smax == Plane::NO_SIDE)
512	{
513	if (branch->mLeft)
514	recInsert(branch->mLeft, rend);
515	else
516	recInsertNew(branch, PlaneEvent::PES_LEFT, rend);
517	}
518	else if (smax == Plane::POSITIVE_SIDE && smin == Plane::NO_SIDE)
519	{
520	if (branch->mRight)
521	recInsert(branch->mRight, rend);
522	else
523	recInsertNew(branch, PlaneEvent::PES_RIGHT, rend);
524	}
525	else
526	{
527	// to avoid SNAFUs, rebuild whole subtree
528	//LogManager::getSingleton().logMessage("## Rebuilding subtree for insertion");
529	rebuildSubtree(node, rend);
530	}
531	}
532	}
533	}
534
535	void KdTree::recInsertNew(KdTree::Branch * parent, PlaneEvent::Side side, KdRenderable * rend)
536	{
537	//LogManager::getSingleton().logMessage("## Inserting into new subtree");
538
539	AxisAlignedBox left, rigth, aabb;
540	PlaneEventList events;
541	int nObjects;
542
543	rend->computeScene(events, aabb, nObjects, false);
544
545	// override aabb
546	splitBox(*parent, left, rigth);
547	if (side == PlaneEvent::PES_LEFT)
548	{
549	aabb = left;
550	if (mBuildMethod == KDBM_RECURSIVE)
551	parent->mLeft = recBuild(events, nObjects, aabb, parent);
552	else if (mBuildMethod == KDBM_PRIORITYQUEUE)
553	parent->mLeft = pqBuild(events, nObjects, aabb, parent);
554	else
555	{
556	OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
557	"Invalid build method for the KdTree.",
558	"KdTree::buildFromList");
559	parent->mLeft = 0;
560	}
561
562	}
563	else if (side == PlaneEvent::PES_RIGHT)
564	{
565	aabb = rigth;
566	if (mBuildMethod == KDBM_RECURSIVE)
567	parent->mRight = recBuild(events, nObjects, aabb, parent);
568	else if (mBuildMethod == KDBM_PRIORITYQUEUE)
569	parent->mRight = pqBuild(events, nObjects, aabb, parent);
570	else
571	{
572	OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
573	"Invalid build method for the KdTree.",
574	"KdTree::buildFromList");
575	parent->mRight = 0;
576	}
577	}
578	}
579
580	void KdTree::rebuildSubtree(KdTree::Node * node, KdRenderable * rend)
581	{
582	//LogManager::getSingleton().logMessage("## Rebuilding subtree");
583
584	AxisAlignedBox aabb = node->mAABB;
585
586	KdRenderableList nodelist;
587	nodelist.push_back(rend);
588	addRendToList(node, nodelist);
589
590	if (node == mKdRoot)
591	{
592	OGRE_DELETE(mKdRoot);
593	mKdRoot = buildFromList(nodelist, 0, aabb);
594	}
595	else
596	{
597	KdTree::Branch * parent = KDBRANCHPTR_CAST(node->getParent());
598
599	if (node == parent->mLeft)
600	{
601	OGRE_DELETE(parent->mLeft);
602	parent->mLeft = buildFromList(nodelist, parent, aabb);
603	}
604	else if (node == parent->mRight)
605	{
606	OGRE_DELETE(parent->mRight);
607	parent->mRight = buildFromList(nodelist, parent, aabb);
608	}
609	else
610	{
611	OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
612	"SNAFU while inserting KdRenderable into KdTree.",
613	"KdTree::recInsert" );
614	}
615	}
616	}
617
618	// compute both AABB then return the requested one.
619	void KdTree::splitBox(const KdTree::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right)
620	{
621	Vector3 bmin = parent.mAABB.getMinimum();
622	Vector3 bmax = parent.mAABB.getMaximum();
623	Real pos = - parent.mSplitPlane->d;
624	int dim = static_cast<int>(parent.mSplitPlane->normal.dotProduct(Vector3(0,1,2)));
625	// set corners which are the same as parent AABB
626	left.setMinimum(bmin);
627	right.setMaximum(bmax);
628	// modify "inner" corners
629	bmin[dim] = pos;
630	bmax[dim] = pos;
631	// set the corners on the split plane
632	left.setMaximum(bmax);
633	right.setMinimum(bmin);
634	}
635
636	void KdTree::addRendToList(KdTree::Node * node, KdRenderableList& nodelist)
637	{
638	if (node->isLeaf())
639	{
640	KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
641	KdRenderableList::iterator it = leaf->mKdRenderables.begin();
642	KdRenderableList::iterator end = leaf->mKdRenderables.end();
643	while (it != end)
644	{
645	nodelist.push_back(*it);
646	it++;
647	}
648	}
649	else
650	{
651	KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
652	if (branch->mLeft)
653	addRendToList(branch->mLeft, nodelist);
654	if (branch->mRight)
655	addRendToList(branch->mRight, nodelist);
656	}
657	}
658
659	/************************************************************************/
660	/* KdTree build functions */
661	/************************************************************************/
662
663	void KdTree::build(KdRenderable * sceneRoot)
664	{
665	Timer *timer = Root::getSingleton().getTimer();
666	unsigned long t1, t2, t3, t4;
667
668	mStats.clear();
669
670	// data we want to collect
671	PlaneEventList events;
672	AxisAlignedBox aabb;
673	int nObjects = 0;
674
675	t1 = timer->getMicroseconds(); // DEBUG
676	sceneRoot->computeScene(events, aabb, nObjects);
677	t2 = timer->getMicroseconds(); // DEBUG
678	events.sort();
679	t3 = timer->getMicroseconds(); // DEBUG
680
681	mStats.mNumSceneNodes = nObjects;
682
683	assert(! aabb.isNull() && "Teh stubid worldAABB iz NULL ... waht now?");
684	// hack to avoid SNAFU with "2-dimensional" scene
685	aabb.merge(aabb.getMaximum()+Vector3(1,1,1));
686	aabb.merge(aabb.getMinimum()+Vector3(-1,-1,-1));
687
688	if (mBuildMethod == KDBM_RECURSIVE)
689	mKdRoot = recBuild(events, nObjects, aabb, 0);
690	else if (mBuildMethod == KDBM_PRIORITYQUEUE)
691	mKdRoot = pqBuild(events, nObjects, aabb, 0);
692	else
693	{
694	OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
695	"Invalid build method for the KdTree.",
696	"KdTree::build");
697	mKdRoot = 0;
698	}
699
700	t4 = timer->getMicroseconds(); // DEBUG
701
702	String method = "Invalid";
703	if (mBuildMethod == KDBM_RECURSIVE)
704	method = "Recursive";
705	else if (mBuildMethod == KDBM_PRIORITYQUEUE)
706	method = "Priority Queue";
707
708	mBuildLog->logMessage("######## SAH Statistics ########");
709	mBuildLog->logMessage("Build Method: " + method);
710	mBuildLog->logMessage("Time for events build: " + StringConverter::toString(t2 - t1) + "µs");
711	mBuildLog->logMessage("Time for events sort: " + StringConverter::toString(t3 - t2) + "µs");
712	mBuildLog->logMessage("Time for tree build: " + StringConverter::toString(t4 - t3) + "µs");
713	mBuildLog->logMessage("Total time: " + StringConverter::toString(t4 - t1) + "µs");
714	mBuildLog->logMessage("Tree Depth: " + StringConverter::toString(mMaxDepth));
715	mBuildLog->logMessage("Number of Objects: " + StringConverter::toString(mStats.mNumSceneNodes));
716	mBuildLog->logMessage("Number of Leaves: " + StringConverter::toString(mStats.mNumLeaves));
717	mBuildLog->logMessage("Number of Nodes: " + StringConverter::toString(mStats.mNumNodes));
718	mBuildLog->logMessage("Total cost: " + StringConverter::toString(calcCost()));
719	mBuildLog->logMessage("################################");
720	}
721
722	KdTree::Node * KdTree::buildFromList(KdRenderableList& nodelist, KdTree::Branch * parent, AxisAlignedBox& aabb)
723	{
724	// data we want to collect
725	PlaneEventList events;
726	AxisAlignedBox nodeaabb;
727	int nObjects = 0;
728
729	KdRenderableList::iterator it = nodelist.begin();
730	KdRenderableList::iterator end = nodelist.end();
731	while (it != end)
732	{
733	(*it)->computeScene(events, nodeaabb, nObjects, false);
734	it++;
735	}
736
737	events.sort();
738
739	// HACK
740	if (aabb.isNull())
741	{
742	aabb = nodeaabb;
743	}
744
745	if (mBuildMethod == KDBM_RECURSIVE)
746	return recBuild(events, nObjects, aabb, parent);
747	else if (mBuildMethod == KDBM_PRIORITYQUEUE)
748	return pqBuild(events, nObjects, aabb, parent);
749	else
750	{
751	OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
752	"Invalid build method for the KdTree.",
753	"KdTree::buildFromList");
754	return 0;
755	}
756	}
757
758	KdTree::Node * KdTree::recBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent)
759	{
760	// determine the depth we are on
761	int level = 0;
762	if (parent)
763	{
764	level = parent->getLevel() + 1;
765	}
766
767	/************************************************/
768	/************** BEGIN FINDPLANE *************/
769	/************************************************/
770	// find optimal split plane and split node accordingly
771
772	// initialize
773	const int dim = 3;
774	int pStart, pOn, pEnd;
775	int nLeft[dim], nPlane[dim], nRight[dim];
776	for (int i = 0; i < dim; i++)
777	{
778	nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
779	}
780
781	SplitInfo split, best;
782	best.cost = Math::POS_INFINITY;
783
784	PlaneEventList::iterator begin = events.begin();
785	PlaneEventList::iterator end = events.end();
786	PlaneEventList::iterator it = begin;
787	// try all planes to find the best one for the given set of objects
788	while (it != end)
789	{
790	PlaneEventList::iterator p = it;
791	pStart = pOn = pEnd = 0;
792	while (it != end && p->equalsType(*it, PlaneEvent::PET_END))
793	{
794	it++; pEnd++;
795	}
796	while (it != end && p->equalsType(*it, PlaneEvent::PET_ON))
797	{
798	it++; pOn++;
799	}
800	while (it != end && p->equalsType(*it, PlaneEvent::PET_START))
801	{
802	it++; pStart++;
803	}
804	int d = p->getDimension();
805	nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
806	p->SAH(aabb, nLeft[d], nPlane[d], nRight[d], split);
807	if (split.cost < best.cost)
808	{
809	best = split;
810	}
811	nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
812	}
813
814	/************************************************/
815	/************** BEGIN TERMINATE *************/
816	/************************************************/
817	// check terminating condition
818	if (best.cost > PlaneEvent::KI*nObjects \|\| level >= mMaxDepth)
819	{
820	// Terminating condition reached, create leaf and add renderables to list
821	KdTree::Leaf * leaf = new KdTree::Leaf(this, level, aabb, parent);
822	KdRenderable *rend;
823	it = begin;
824	while (it != end)
825	{
826	rend = it->getRenderable();
827	rend->setClassified(false);
828	if (rend->attachTo(leaf, this))
829	{
830	leaf->insert(rend);
831	}
832	it++;
833	}
834	// update stats
835	++ mStats.mNumNodes;
836	++ mStats.mNumLeaves;
837	// update bounding box
838	leaf->_updateBounds(false);
839	return leaf;
840	}
841
842	/************************************************/
843	/************** BEGIN CLASSIFY **************/
844	/************************************************/
845	// split the event list in left and right sub-lists
846	else
847	{
848	PlaneEventList eventsRight, eventsLeft;
849	it = begin;
850	// slightly redundant, since we mark each renderable up to 6 times
851	while (it != end)
852	{
853	it->getRenderable()->setSide(PlaneEvent::PES_BOTH);
854	it->getRenderable()->setClassified(false);
855	it++;
856	}
857	// now classify all renderables. do they belong to the left child, the right child or both?
858	it = begin;
859	while (it != end)
860	{
861	it->classify(best.event, best.side);
862	it++;
863	}
864	// divide the event lists
865	int nLeftS = 0, nRightS = 0, nBothS = 0;
866	it = begin;
867	while (it != end)
868	{
869	// right-only nodes go in right list
870	if (it->getRenderable()->getSide() == PlaneEvent::PES_RIGHT)
871	{
872	if (!it->getRenderable()->isClassified())
873	{
874	it->getRenderable()->setClassified(true);
875	nRightS++;
876	}
877	eventsRight.push_back(*it);
878	}
879	// left-only nodes go in left list
880	else if (it->getRenderable()->getSide() == PlaneEvent::PES_LEFT)
881	{
882	if (!it->getRenderable()->isClassified())
883	{
884	it->getRenderable()->setClassified(true);
885	nLeftS++;
886	}
887	eventsLeft.push_back(*it);
888	}
889	// remaining nodes go in both lists, bust must be clipped to prevent
890	// events from lying outside the new nodes aabb
891	else
892	{
893	if (!it->getRenderable()->isClassified())
894	{
895	it->getRenderable()->setClassified(true);
896	nBothS++;
897	}
898	eventsRight.push_back(it->clip(best.bright, best.event.getDimension()));
899	eventsLeft.push_back(it->clip(best.bleft, best.event.getDimension()));
900	}
901	it++;
902	}
903
904	// create a new branch node and continue recursion
905	KdTree::Branch * branch = new KdTree::Branch(this, level, aabb, parent,
906	best.event.getSplitPlane(), best.side);
907
908	// now create the child nodes and continue recursion
909	if (eventsLeft.size() > 0)
910	{
911	branch->mLeft = recBuild(eventsLeft, nLeftS + nBothS, best.bleft, branch);
912	}
913	if (eventsRight.size() > 0)
914	{
915	branch->mRight = recBuild(eventsRight, nBothS + nRightS, best.bright, branch);
916	}
917
918	// update stats
919	++ mStats.mNumNodes;
920
921	// update bounding box
922	branch->_updateBounds(false);
923
924	return branch;
925	}
926	}
927
928	KdTree::Node * KdTree::pqBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent)
929	{
930	SplitCandidatePQ pqueue;
931	Real globalTreeCost;
932	Real globalSA;
933
934	KdTree::Node * newNode = 0, * topNode = 0;
935	// init global tree cost
936	globalTreeCost = PlaneEvent::KI * nObjects;
937	globalSA = PlaneEvent::surfaceArea(aabb);
938
939	PlaneEventList * e = new PlaneEventList(events);
940
941	// inital split candidate
942	SplitInfo * best = pqFindPlane(e, nObjects, aabb, globalSA);
943	SplitCandidate splitcandidate(e, nObjects, aabb, parent, globalTreeCost,
944	globalTreeCost - best->cost, best, PlaneEvent::PES_BOTH);
945	pqueue.push(splitcandidate);
946
947
948	/* BEGIN ITERATIVE BUILD */
949	while (!pqueue.empty())
950	{
951	SplitCandidate sc = pqueue.top();
952	pqueue.pop();
953
954	// determine the depth we are on
955	int level = 0;
956	if (sc.parent)
957	{
958	level = sc.parent->getLevel() + 1;
959	}
960
961	/************************************************/
962	/************** BEGIN TERMINATE *************/
963	/************************************************/
964	// check terminating condition
965	if (sc.decrease < 0.0 \|\| level >= mMaxDepth)
966	{
967	// Terminating condition reached, create leaf and add renderables to list
968	KdTree::Leaf * leaf = new KdTree::Leaf(this, level, sc.aabb, sc.parent);
969	KdRenderable *rend;
970	PlaneEventList::iterator begin = sc.events->begin();
971	PlaneEventList::iterator end = sc.events->end();
972	PlaneEventList::iterator it = begin;
973	while (it != end)
974	{
975	rend = it->getRenderable();
976	rend->setClassified(false);
977	if (rend->attachTo(leaf, this))
978	{
979	leaf->insert(rend);
980	}
981	it++;
982	}
983	newNode = leaf;
984	if (!topNode)
985	topNode = leaf;
986	// update stats
987	++ mStats.mNumNodes;
988	++ mStats.mNumLeaves;
989	}
990
991	/************************************************/
992	/************** BEGIN CLASSIFY **************/
993	/************************************************/
994	else
995	{
996	PlaneEventList * eventsLeft = new PlaneEventList();
997	PlaneEventList * eventsRight = new PlaneEventList();
998	PlaneEventList::iterator begin = sc.events->begin();
999	PlaneEventList::iterator end = sc.events->end();
1000	PlaneEventList::iterator it = begin;
1001	// slightly redundant, since we mark each renderable up to 6 times
1002	while (it != end)
1003	{
1004	it->getRenderable()->setSide(PlaneEvent::PES_BOTH);
1005	it->getRenderable()->setClassified(false);
1006	it++;
1007	}
1008
1009	// now classify all renderables. do they belong to the left child, the right child or both?
1010	it = begin;
1011	while (it != end)
1012	{
1013	it->classify(sc.best->event, sc.best->side);
1014	it++;
1015	}
1016
1017	// divide the event lists
1018	int nLeftS = 0, nRightS = 0, nBothS = 0;
1019	it = begin;
1020	while (it != end)
1021	{
1022	// right-only events go in the right list
1023	if (it->getRenderable()->getSide() == PlaneEvent::PES_RIGHT)
1024	{
1025	if (!it->getRenderable()->isClassified())
1026	{
1027	it->getRenderable()->setClassified(true);
1028	nRightS++;
1029	}
1030
1031	eventsRight->push_back(*it);
1032	}
1033	// left-only events go in the left list
1034	else if (it->getRenderable()->getSide() == PlaneEvent::PES_LEFT)
1035	{
1036	if (!it->getRenderable()->isClassified())
1037	{
1038	it->getRenderable()->setClassified(true);
1039	nLeftS++;
1040	}
1041	eventsLeft->push_back(*it);
1042	}
1043	// the rest goes in both lists after being clipped
1044	else
1045	{
1046	if (!it->getRenderable()->isClassified())
1047	{
1048	it->getRenderable()->setClassified(true);
1049	nBothS++;
1050	}
1051
1052	eventsRight->push_back(it->clip(sc.best->bright, sc.best->event.getDimension()));
1053	eventsLeft->push_back(it->clip(sc.best->bleft, sc.best->event.getDimension()));
1054	}
1055	it++;
1056	}
1057
1058	// create a new branch node
1059	KdTree::Branch * branch = new KdTree::Branch(this, level, sc.aabb, sc.parent,
1060	sc.best->event.getSplitPlane(), sc.best->side);
1061
1062	globalTreeCost -= sc.decrease;
1063
1064
1065	// now for each potential child node, compute the split plane and the cost decrease
1066	// and place them in the queue
1067	if (eventsLeft->size() > 0)
1068	{
1069	best = pqFindPlane(eventsLeft, nLeftS + nBothS, sc.best->bleft, globalSA);
1070	Real old = PlaneEvent::surfaceArea(sc.best->bleft)/globalSAPlaneEvent::KI(nLeftS + nBothS);
1071	SplitCandidate scleft(eventsLeft, nLeftS + nBothS, sc.best->bleft,
1072	branch, old, old - best->cost, best, PlaneEvent::PES_LEFT);
1073	pqueue.push(scleft);
1074	}
1075	// cleanup
1076	else
1077	{
1078	delete eventsLeft;
1079	}
1080
1081	if (eventsRight->size() > 0)
1082	{
1083	best = pqFindPlane(eventsRight, nBothS + nRightS, sc.best->bright, globalSA);
1084	Real old = PlaneEvent::surfaceArea(sc.best->bright)/globalSAPlaneEvent::KI(nBothS + nRightS);
1085	SplitCandidate scright(eventsRight, nBothS + nRightS, sc.best->bright,
1086	branch, old, old - best->cost, best, PlaneEvent::PES_RIGHT);
1087	pqueue.push(scright);
1088	}
1089	// cleanup
1090	else
1091	{
1092	delete eventsRight;
1093	}
1094
1095	newNode = branch;
1096	if (!topNode)
1097	topNode = branch;
1098
1099
1100	// update stats
1101	++ mStats.mNumNodes;
1102	}
1103
1104	// attach new node to parent
1105	if (sc.parent)
1106	{
1107	if (sc.side == PlaneEvent::PES_LEFT)
1108	{
1109	sc.parent->mLeft = newNode;
1110	}
1111	else if (sc.side == PlaneEvent::PES_RIGHT)
1112	{
1113	sc.parent->mRight = newNode;
1114	}
1115	else
1116	{
1117	OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
1118	"PQBUILD SNAFU - CHILD I AM NOT LEFT NOR RIGHT","KdTree::pqBuild");
1119	}
1120	}
1121
1122	// update bounding boxes when geometry (leaf) was added
1123	if (newNode->isLeaf())
1124	newNode->_updateBounds();
1125
1126	//cleanup
1127	OGRE_DELETE(sc.events);
1128	OGRE_DELETE(sc.best);
1129	}
1130	mBuildLog->logMessage("Cost after PQBUILD " + StringConverter::toString(globalTreeCost));
1131	return topNode;
1132	}
1133
1134	//-------------------------------------------------------------------------
1135	SplitInfo * KdTree::pqFindPlane(PlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA)
1136	{
1137	static const int dim = 3;
1138	int pStart, pOn, pEnd;
1139	int nLeft[dim], nPlane[dim], nRight[dim];
1140	for (int i = 0; i < dim; i++)
1141	{
1142	nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
1143	}
1144
1145	SplitInfo split, best;
1146	best.cost = Math::POS_INFINITY;
1147
1148	Real parentSA = PlaneEvent::surfaceArea(aabb);
1149
1150	PlaneEventList::iterator begin = events->begin();
1151	PlaneEventList::iterator end = events->end();
1152	PlaneEventList::iterator it = begin;
1153	// try all planes to find the best one for the given set of objects
1154	while (it != end)
1155	{
1156	PlaneEventList::iterator p = it;
1157	pStart = pOn = pEnd = 0;
1158	while (it != end && p->equalsType(*it, PlaneEvent::PET_END))
1159	{
1160	it++; pEnd++;
1161	}
1162	while (it != end && p->equalsType(*it, PlaneEvent::PET_ON))
1163	{
1164	it++; pOn++;
1165	}
1166	while (it != end && p->equalsType(*it, PlaneEvent::PET_START))
1167	{
1168	it++; pStart++;
1169	}
1170	int d = p->getDimension();
1171	nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
1172	p->pqSAH(globalSA, parentSA, nLeft[d], nPlane[d], nRight[d], aabb, split);
1173	if (split.cost < best.cost)
1174	{
1175	best = split;
1176	}
1177	nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
1178	}
1179	return new SplitInfo(best);
1180	}
1181
1182	/************************************************************************/
1183	/* KdTree rendering functions */
1184	/************************************************************************/
1185
1186	//-------------------------------------------------------------------------
1187	void KdTree::queueVisibleObjects(Camera* cam, RenderQueue* queue, bool onlyShadowCasters,
1188	bool showBoxes, KdTree::NodeList& visibleNodes)
1189	{
1190	if (mKdRoot)
1191	recQueueVisibleObjects(mKdRoot, Root::getSingleton().getCurrentFrameNumber(),
1192	cam, queue, onlyShadowCasters, showBoxes, visibleNodes);
1193	}
1194
1195	//-------------------------------------------------------------------------
1196	void KdTree::recQueueVisibleObjects(KdTree::Node * node, unsigned long currentFrame,
1197	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, KdTree::NodeList& visibleNodes)
1198	{
1199	// test visibility
1200	if (cam->isVisible(node->mAABB))
1201	{
1202	visibleNodes.push_back(node);
1203
1204	node->queueVisibleObjects(currentFrame, cam, queue, onlyShadowCasters, showBoxes);
1205
1206	if (node->getLeftChild())
1207	recQueueVisibleObjects(node->getLeftChild(), currentFrame,
1208	cam, queue, onlyShadowCasters, showBoxes, visibleNodes);
1209	if (node->getRightChild())
1210	recQueueVisibleObjects(node->getRightChild(), currentFrame,
1211	cam, queue, onlyShadowCasters, showBoxes, visibleNodes);
1212	}
1213	}
1214
1215	////-------------------------------------------------------------------------
1216	//void KdTree::findVisibleNodes(NodeList& visibleNodes, Camera * cam)
1217	//{
1218	// if (mKdRoot)
1219	// recFindVisibleNodes(mKdRoot, visibleNodes, cam);
1220	//}
1221
1222	////-------------------------------------------------------------------------
1223	//void KdTree::recFindVisibleNodes(KdTree::Node * node, NodeList& visibleNodes, Camera * cam)
1224	//{
1225	// // test visibility
1226	// if (cam->isVisible(node->mAABB))
1227	// {
1228	// visibleNodes.push_back(node);
1229
1230	// if (node->getLeftChild())
1231	// recFindVisibleNodes(node->getLeftChild(), visibleNodes, cam);
1232	// if (node->getRightChild())
1233	// recFindVisibleNodes(node->getRightChild(), visibleNodes, cam);
1234	// }
1235	//}
1236
1237	/************************************************************************/
1238	/* KdTree debug & helper functions */
1239	/************************************************************************/
1240
1241	//-------------------------------------------------------------------------
1242	void KdTree::dump()
1243	{
1244	LogManager::getSingleton().logMessage("#@#@#@#@ Dumping KdTree #@#@#@#@");
1245	if (mKdRoot)
1246	dump(mKdRoot);
1247	}
1248
1249	//-------------------------------------------------------------------------
1250	void KdTree::dump(KdTree::Node * node)
1251	{
1252	LogManager * log = LogManager::getSingletonPtr();
1253	KdTreeSceneNode * scenenode;
1254	String pad;
1255	int p;
1256
1257	pad = "";
1258	for (p = 0; p < node->getLevel(); p++)
1259	{
1260	pad += " ";
1261	}
1262
1263	if (node->isLeaf())
1264	{
1265	KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
1266	KdRenderableList::iterator it = leaf->mKdRenderables.begin();
1267	KdRenderableList::iterator end = leaf->mKdRenderables.end();
1268	while (it != end)
1269	{
1270	scenenode = dynamic_cast<KdTreeSceneNode >(it);
1271	log->logMessage(pad + "# Leaf level " +
1272	StringConverter::toString(node->getLevel()) +
1273	" SceneNode " + scenenode->getName());
1274	log->logMessage(pad + "## Objects: " + scenenode->dumpToString());
1275	it++;
1276	}
1277	}
1278	else
1279	{
1280	KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
1281	if (branch->mLeft)
1282	{
1283	log->logMessage(pad + "# Branch level " +
1284	StringConverter::toString(node->getLevel()) + " Left Child");
1285	dump(branch->mLeft);
1286	}
1287	if (branch->mRight)
1288	{
1289	log->logMessage(pad + "# Branch level " +
1290	StringConverter::toString(node->getLevel()) + " Right Child");
1291	dump(branch->mRight);
1292	}
1293	}
1294	}
1295
1296	//-------------------------------------------------------------------------
1297	Real KdTree::calcCost()
1298	{
1299	if (mKdRoot)
1300	return calcCost(mKdRoot, PlaneEvent::surfaceArea(mKdRoot->mAABB));
1301	else
1302	return 0;
1303	}
1304
1305	//-------------------------------------------------------------------------
1306	Real KdTree::calcCost(KdTree::Node * node, Real vs)
1307	{
1308	if (node == 0)
1309	return 0.0;
1310
1311	if (node->isLeaf())
1312	{
1313	KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
1314	return (PlaneEvent::surfaceArea(node->mAABB)/vs) *
1315	PlaneEvent::KI * leaf->mKdRenderables.size();
1316	}
1317	else
1318	{
1319	KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
1320	return (PlaneEvent::surfaceArea(node->mAABB)/vs) * PlaneEvent::KT +
1321	calcCost(branch->mLeft, vs) + calcCost(branch->mRight, vs);
1322	}
1323	}
1324
1325	/************************************************************************/
1326	/* KdTree::Node/Branch/Leaf functions */
1327	/************************************************************************/
1328
1329	//-------------------------------------------------------------------------
1330	KdTree::Leaf::~Leaf()
1331	{
1332	// detach all scene nodes in the case that we are rebuilding
1333	// the tree but not the scene
1334	KdRenderableList::iterator it = mKdRenderables.begin();
1335	KdRenderableList::iterator end = mKdRenderables.end();
1336	while (it != end)
1337	{
1338	(*it)->detachFrom(this);
1339	it++;
1340	}
1341	mKdRenderables.clear();
1342	}
1343
1344	//-------------------------------------------------------------------------
1345	void KdTree::Leaf::queueVisibleObjects(unsigned long currentFrame,
1346	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes)
1347	{
1348	KdRenderableList::iterator it = mKdRenderables.begin();
1349	KdRenderableList::iterator end = mKdRenderables.end();
1350	while (it != end)
1351	{
1352	if (!(*it)->isQueued(currentFrame, cam))
1353	{
1354	(*it)->queueObjects(cam, queue, onlyShadowCasters);
1355	}
1356	it++;
1357	}
1358
1359	if (showBoxes)
1360	if (mLevel == mOwner->getHiLiteLevel() \|\| mOwner->getShowAllBoxes())
1361	queue->addRenderable(getWireBoundingBox());
1362	}
1363
1364	//-------------------------------------------------------------------------
1365	void KdTree::Leaf::getGeometryList(GtpVisibility::GeometryVector *geometryList)
1366	{
1367	KdRenderableList::iterator it = mKdRenderables.begin();
1368	KdRenderableList::iterator end = mKdRenderables.end();
1369	while (it != end)
1370	{
1371	(*it)->getGeometryList(geometryList);
1372	it++;
1373	}
1374	}
1375
1376	//-------------------------------------------------------------------------
1377	// update the world aabb based on the contained geometry
1378	void KdTree::Leaf::_updateBounds(bool recurse)
1379	{
1380	// reset box
1381	mWorldAABB.setNull();
1382
1383	// merge boxes from attached geometry
1384	KdRenderableList::iterator it = mKdRenderables.begin();
1385	KdRenderableList::iterator end = mKdRenderables.end();
1386	while (it != end)
1387	{
1388	//(*it)->_updateBounds();
1389	mWorldAABB.merge((*it)->getBoundingBox());
1390	it++;
1391	}
1392
1393	// update parent recursively
1394	if (recurse && mParent)
1395	mParent->_updateBounds(recurse);
1396	}
1397	} // namespace Ogre

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

Download in other formats: