Context Navigation

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

Revision 1192, 41.3 KB checked in by szydlowski, 18 years ago (diff)
pre-major-changes-backup (TM) fixed node vis issues 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	#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(HILITE_OFF),
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	// init visualization materials
338	MaterialPtr mphi = MaterialManager::getSingleton().getByName("KdTree/BoxHiLite");
339	if (mphi.isNull())
340	{
341	ColourValue green(0, 1, 0);
342	mphi = MaterialManager::getSingleton().create("KdTree/BoxHiLite", "General");
343	mphi->setAmbient(green);
344	mphi->setDiffuse(green);
345	mphi->setLightingEnabled(true);
346	mphi->getTechnique(0)->getPass(0)->removeAllTextureUnitStates();
347	}
348
349	MaterialPtr mpviz = MaterialManager::getSingleton().getByName("KdTree/BoxViz");
350	if (mpviz.isNull())
351	{
352	ColourValue yellow(1, 1, 0);
353	mpviz = MaterialManager::getSingleton().create("KdTree/BoxViz", "General");
354	mpviz->setAmbient(yellow);
355	mpviz->setDiffuse(yellow);
356	mpviz->setLightingEnabled(true);
357	mpviz->getTechnique(0)->getPass(0)->removeAllTextureUnitStates();
358	}
359
360	// retrieve or create build log
361	try
362	{
363	mBuildLog = LogManager::getSingleton().getLog(KDTREE_LOGNAME);
364	}
365	catch (Exception&)
366	{
367	mBuildLog = LogManager::getSingleton().createLog(KDTREE_LOGNAME);
368	}
369	}
370
371	/************************************************************************/
372	/* KdTree insert/delete functions */
373	/************************************************************************/
374
375	void KdTree::remove(KdRenderable * rend)
376	{
377	// DEBUG
378	//LogManager::getSingleton().logMessage("-- Removing SceneNode: " + (static_cast<KdTreeSceneNode *>(rend))->getName());
379	std::queue<LeafPtr> cleanup;
380	LeafPtr leaf;
381	LeafSet ls = rend->getLeaves();
382	LeafSet::iterator it = ls.begin();
383	LeafSet::iterator end = ls.end();
384	while (it != end)
385	{
386	cleanup.push(*it);
387	it++;
388	}
389	while (!cleanup.empty())
390	{
391	leaf = cleanup.front();
392	cleanup.pop();
393	leaf->remove(rend);
394	bool gone = rend->detachFrom(leaf);
395	assert(gone && "Failed to detach leave which is abso-fuckin-lutely impossible!!!");
396	//dump();
397	recDelete(leaf);
398	//dump();
399	}
400	}
401
402	void KdTree::recDelete(KdTree::Node * node)
403	{
404	if (node == 0) // DEBUG
405	{
406	OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
407	"SNAFU while inserting KdRenderable into KdTree.",
408	"KdTree::recInsert" );
409	return;
410	}
411
412	if (node->isEmpty())
413	{
414	if (node == mKdRoot)
415	{
416	OGRE_DELETE(mKdRoot);
417	}
418	else
419	{
420	KdTree::Branch * parent = KDBRANCHPTR_CAST(node->getParent());
421	if (node == parent->mLeft)
422	{
423	OGRE_DELETE(parent->mLeft);
424	}
425	else if (node == parent->mRight)
426	{
427	OGRE_DELETE(parent->mRight);
428	}
429	recDelete(parent);
430	}
431	}
432	}
433
434	void KdTree::insert(KdRenderable * rend)
435	{
436	// make sure the tree exists
437	if (mKdRoot)
438	{
439	// make sure the renderable is inside the world bounding box
440	AxisAlignedBox aabb = rend->getBoundingBox();
441	AxisAlignedBox isect = mKdRoot->mAABB.intersection(aabb);
442	if (isect.getMinimum() == aabb.getMinimum() && isect.getMaximum() == aabb.getMaximum())
443	{
444	recInsert(mKdRoot, rend);
445	}
446	else
447	{
448	//LogManager::getSingleton().logMessage("Inserted node outside of world AABB.");
449	KdRenderableList nodelist;
450	nodelist.push_back(rend);
451	addRendToList(mKdRoot, nodelist);
452	OGRE_DELETE(mKdRoot);
453	mKdRoot = buildFromList(nodelist, 0, AxisAlignedBox());
454	}
455	}
456	// otherwise build a new one
457	else
458	{
459	build(rend);
460	}
461	}
462
463	void KdTree::recInsert(KdTree::Node * node, KdRenderable * rend)
464	{
465	if (node == 0) // DEBUG
466	{
467	OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
468	"SNAFU while inserting KdRenderable into KdTree.",
469	"KdTree::recInsert" );
470	return;
471	}
472
473	// rebuild the leaf/replace with subtree ...
474	if (node->isLeaf())
475	{
476	//LogManager::getSingleton().logMessage("## Replacing leaf.");
477	rebuildSubtree(node, rend);
478	}
479	else
480	{
481	KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
482	AxisAlignedBox aabb = rend->getBoundingBox();
483	Plane::Side smin = branch->mSplitPlane->getSide(aabb.getMinimum());
484	Plane::Side smax = branch->mSplitPlane->getSide(aabb.getMaximum());
485	if (smin == smax)
486	{
487	if (smax == Plane::NEGATIVE_SIDE \|\|
488	(smax == Plane::NO_SIDE && branch->mPlaneSide == PlaneEvent::PES_LEFT))
489	{
490	if (branch->mLeft)
491	recInsert(branch->mLeft, rend);
492	else
493	recInsertNew(branch, PlaneEvent::PES_LEFT, rend);
494	}
495	else if (smin == Plane::POSITIVE_SIDE \|\|
496	(smin == Plane::NO_SIDE && branch->mPlaneSide == PlaneEvent::PES_RIGHT))
497	{
498	if (branch->mRight)
499	recInsert(branch->mRight, rend);
500	else
501	recInsertNew(branch, PlaneEvent::PES_RIGHT, rend);
502	}
503	}
504	else
505	{
506	if (smin == Plane::NEGATIVE_SIDE && smax == Plane::NO_SIDE)
507	{
508	if (branch->mLeft)
509	recInsert(branch->mLeft, rend);
510	else
511	recInsertNew(branch, PlaneEvent::PES_LEFT, rend);
512	}
513	else if (smax == Plane::POSITIVE_SIDE && smin == Plane::NO_SIDE)
514	{
515	if (branch->mRight)
516	recInsert(branch->mRight, rend);
517	else
518	recInsertNew(branch, PlaneEvent::PES_RIGHT, rend);
519	}
520	else
521	{
522	// to avoid SNAFUs, rebuild whole subtree
523	//LogManager::getSingleton().logMessage("## Rebuilding subtree for insertion");
524	rebuildSubtree(node, rend);
525	}
526	}
527	}
528	}
529
530	void KdTree::recInsertNew(KdTree::Branch * parent, PlaneEvent::Side side, KdRenderable * rend)
531	{
532	//LogManager::getSingleton().logMessage("## Inserting into new subtree");
533
534	AxisAlignedBox left, rigth, aabb;
535	PlaneEventList events;
536	int nObjects;
537
538	rend->computeScene(events, aabb, nObjects, false);
539
540	// override aabb
541	splitBox(*parent, left, rigth);
542	if (side == PlaneEvent::PES_LEFT)
543	{
544	aabb = left;
545	if (mBuildMethod == KDBM_RECURSIVE)
546	parent->mLeft = recBuild(events, nObjects, aabb, parent);
547	else if (mBuildMethod == KDBM_PRIORITYQUEUE)
548	parent->mLeft = pqBuild(events, nObjects, aabb, parent);
549	else
550	{
551	OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
552	"Invalid build method for the KdTree.",
553	"KdTree::buildFromList");
554	parent->mLeft = 0;
555	}
556
557	}
558	else if (side == PlaneEvent::PES_RIGHT)
559	{
560	aabb = rigth;
561	if (mBuildMethod == KDBM_RECURSIVE)
562	parent->mRight = recBuild(events, nObjects, aabb, parent);
563	else if (mBuildMethod == KDBM_PRIORITYQUEUE)
564	parent->mRight = pqBuild(events, nObjects, aabb, parent);
565	else
566	{
567	OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
568	"Invalid build method for the KdTree.",
569	"KdTree::buildFromList");
570	parent->mRight = 0;
571	}
572	}
573	}
574
575	void KdTree::rebuildSubtree(KdTree::Node * node, KdRenderable * rend)
576	{
577	//LogManager::getSingleton().logMessage("## Rebuilding subtree");
578
579	AxisAlignedBox aabb = node->mAABB;
580
581	KdRenderableList nodelist;
582	nodelist.push_back(rend);
583	addRendToList(node, nodelist);
584
585	if (node == mKdRoot)
586	{
587	OGRE_DELETE(mKdRoot);
588	mKdRoot = buildFromList(nodelist, 0, aabb);
589	}
590	else
591	{
592	KdTree::Branch * parent = KDBRANCHPTR_CAST(node->getParent());
593
594	if (node == parent->mLeft)
595	{
596	OGRE_DELETE(parent->mLeft);
597	parent->mLeft = buildFromList(nodelist, parent, aabb);
598	}
599	else if (node == parent->mRight)
600	{
601	OGRE_DELETE(parent->mRight);
602	parent->mRight = buildFromList(nodelist, parent, aabb);
603	}
604	else
605	{
606	OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
607	"SNAFU while inserting KdRenderable into KdTree.",
608	"KdTree::recInsert" );
609	}
610	}
611	}
612
613	// compute both AABB then return the requested one.
614	void KdTree::splitBox(const KdTree::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right)
615	{
616	Vector3 bmin = parent.mAABB.getMinimum();
617	Vector3 bmax = parent.mAABB.getMaximum();
618	Real pos = - parent.mSplitPlane->d;
619	int dim = static_cast<int>(parent.mSplitPlane->normal.dotProduct(Vector3(0,1,2)));
620	// set corners which are the same as parent AABB
621	left.setMinimum(bmin);
622	right.setMaximum(bmax);
623	// modify "inner" corners
624	bmin[dim] = pos;
625	bmax[dim] = pos;
626	// set the corners on the split plane
627	left.setMaximum(bmax);
628	right.setMinimum(bmin);
629	}
630
631	void KdTree::addRendToList(KdTree::Node * node, KdRenderableList& nodelist)
632	{
633	if (node->isLeaf())
634	{
635	KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
636	KdRenderableList::iterator it = leaf->mKdRenderables.begin();
637	KdRenderableList::iterator end = leaf->mKdRenderables.end();
638	while (it != end)
639	{
640	nodelist.push_back(*it);
641	it++;
642	}
643	}
644	else
645	{
646	KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
647	if (branch->mLeft)
648	addRendToList(branch->mLeft, nodelist);
649	if (branch->mRight)
650	addRendToList(branch->mRight, nodelist);
651	}
652	}
653
654	/************************************************************************/
655	/* KdTree build functions */
656	/************************************************************************/
657
658	void KdTree::build(KdRenderable * sceneRoot)
659	{
660	Timer *timer = Root::getSingleton().getTimer();
661	unsigned long t1, t2, t3, t4;
662
663	mStats.clear();
664
665	// data we want to collect
666	PlaneEventList events;
667	AxisAlignedBox aabb;
668	int nObjects = 0;
669
670	t1 = timer->getMicroseconds(); // DEBUG
671	sceneRoot->computeScene(events, aabb, nObjects);
672	t2 = timer->getMicroseconds(); // DEBUG
673	events.sort();
674	t3 = timer->getMicroseconds(); // DEBUG
675
676	mStats.mNumSceneNodes = nObjects;
677
678	assert(! aabb.isNull() && "Teh stubid worldAABB iz NULL ... waht now?");
679	// hack to avoid SNAFU with "2-dimensional" scene
680	aabb.merge(aabb.getMaximum()+Vector3(1,1,1));
681	aabb.merge(aabb.getMinimum()+Vector3(-1,-1,-1));
682
683	if (mBuildMethod == KDBM_RECURSIVE)
684	mKdRoot = recBuild(events, nObjects, aabb, 0);
685	else if (mBuildMethod == KDBM_PRIORITYQUEUE)
686	mKdRoot = pqBuild(events, nObjects, aabb, 0);
687	else
688	{
689	OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
690	"Invalid build method for the KdTree.",
691	"KdTree::build");
692	mKdRoot = 0;
693	}
694
695	t4 = timer->getMicroseconds(); // DEBUG
696
697	String method = "Invalid";
698	if (mBuildMethod == KDBM_RECURSIVE)
699	method = "Recursive";
700	else if (mBuildMethod == KDBM_PRIORITYQUEUE)
701	method = "Priority Queue";
702
703	mBuildLog->logMessage("######## SAH Statistics ########");
704	mBuildLog->logMessage("Build Method: " + method);
705	mBuildLog->logMessage("Time for events build: " + StringConverter::toString(t2 - t1) + "µs");
706	mBuildLog->logMessage("Time for events sort: " + StringConverter::toString(t3 - t2) + "µs");
707	mBuildLog->logMessage("Time for tree build: " + StringConverter::toString(t4 - t3) + "µs");
708	mBuildLog->logMessage("Total time: " + StringConverter::toString(t4 - t1) + "µs");
709	mBuildLog->logMessage("Tree Depth: " + StringConverter::toString(mMaxDepth));
710	mBuildLog->logMessage("Number of Objects: " + StringConverter::toString(mStats.mNumSceneNodes));
711	mBuildLog->logMessage("Number of Leaves: " + StringConverter::toString(mStats.mNumLeaves));
712	mBuildLog->logMessage("Number of Nodes: " + StringConverter::toString(mStats.mNumNodes));
713	mBuildLog->logMessage("Total cost: " + StringConverter::toString(calcCost()));
714	mBuildLog->logMessage("################################");
715	}
716
717	KdTree::Node * KdTree::buildFromList(KdRenderableList& nodelist, KdTree::Branch * parent, AxisAlignedBox& aabb)
718	{
719	// data we want to collect
720	PlaneEventList events;
721	AxisAlignedBox nodeaabb;
722	int nObjects = 0;
723
724	KdRenderableList::iterator it = nodelist.begin();
725	KdRenderableList::iterator end = nodelist.end();
726	while (it != end)
727	{
728	(*it)->computeScene(events, nodeaabb, nObjects, false);
729	it++;
730	}
731
732	events.sort();
733
734	// HACK
735	if (aabb.isNull())
736	{
737	aabb = nodeaabb;
738	}
739
740	if (mBuildMethod == KDBM_RECURSIVE)
741	return recBuild(events, nObjects, aabb, parent);
742	else if (mBuildMethod == KDBM_PRIORITYQUEUE)
743	return pqBuild(events, nObjects, aabb, parent);
744	else
745	{
746	OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
747	"Invalid build method for the KdTree.",
748	"KdTree::buildFromList");
749	return 0;
750	}
751	}
752
753	KdTree::Node * KdTree::recBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent)
754	{
755	// determine the depth we are on
756	int level = 0;
757	if (parent)
758	{
759	level = parent->getLevel() + 1;
760	}
761
762	/************************************************/
763	/************** BEGIN FINDPLANE *************/
764	/************************************************/
765	// find optimal split plane and split node accordingly
766
767	// initialize
768	const int dim = 3;
769	int pStart, pOn, pEnd;
770	int nLeft[dim], nPlane[dim], nRight[dim];
771	for (int i = 0; i < dim; i++)
772	{
773	nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
774	}
775
776	SplitInfo split, best;
777	best.cost = Math::POS_INFINITY;
778
779	PlaneEventList::iterator begin = events.begin();
780	PlaneEventList::iterator end = events.end();
781	PlaneEventList::iterator it = begin;
782	// try all planes to find the best one for the given set of objects
783	while (it != end)
784	{
785	PlaneEventList::iterator p = it;
786	pStart = pOn = pEnd = 0;
787	while (it != end && p->equalsType(*it, PlaneEvent::PET_END))
788	{
789	it++; pEnd++;
790	}
791	while (it != end && p->equalsType(*it, PlaneEvent::PET_ON))
792	{
793	it++; pOn++;
794	}
795	while (it != end && p->equalsType(*it, PlaneEvent::PET_START))
796	{
797	it++; pStart++;
798	}
799	int d = p->getDimension();
800	nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
801	p->SAH(aabb, nLeft[d], nPlane[d], nRight[d], split);
802	if (split.cost < best.cost)
803	{
804	best = split;
805	}
806	nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
807	}
808
809	/************************************************/
810	/************** BEGIN TERMINATE *************/
811	/************************************************/
812	// check terminating condition
813	if (best.cost > PlaneEvent::KI*nObjects \|\| level >= mMaxDepth)
814	{
815	// Terminating condition reached, create leaf and add renderables to list
816	KdTree::Leaf * leaf = new KdTree::Leaf(this, level, aabb, parent);
817	KdRenderable *rend;
818	it = begin;
819	while (it != end)
820	{
821	rend = it->getRenderable();
822	rend->setClassified(false);
823	if (rend->attachTo(leaf, this))
824	{
825	leaf->insert(rend);
826	}
827	it++;
828	}
829	// update stats
830	++ mStats.mNumNodes;
831	++ mStats.mNumLeaves;
832	// update bounding box
833	leaf->_updateBounds(false);
834	return leaf;
835	}
836
837	/************************************************/
838	/************** BEGIN CLASSIFY **************/
839	/************************************************/
840	// split the event list in left and right sub-lists
841	else
842	{
843	PlaneEventList eventsRight, eventsLeft;
844	it = begin;
845	// slightly redundant, since we mark each renderable up to 6 times
846	while (it != end)
847	{
848	it->getRenderable()->setSide(PlaneEvent::PES_BOTH);
849	it->getRenderable()->setClassified(false);
850	it++;
851	}
852	// now classify all renderables. do they belong to the left child, the right child or both?
853	it = begin;
854	while (it != end)
855	{
856	it->classify(best.event, best.side);
857	it++;
858	}
859	// divide the event lists
860	int nLeftS = 0, nRightS = 0, nBothS = 0;
861	it = begin;
862	while (it != end)
863	{
864	// right-only nodes go in right list
865	if (it->getRenderable()->getSide() == PlaneEvent::PES_RIGHT)
866	{
867	if (!it->getRenderable()->isClassified())
868	{
869	it->getRenderable()->setClassified(true);
870	nRightS++;
871	}
872	eventsRight.push_back(*it);
873	}
874	// left-only nodes go in left list
875	else if (it->getRenderable()->getSide() == PlaneEvent::PES_LEFT)
876	{
877	if (!it->getRenderable()->isClassified())
878	{
879	it->getRenderable()->setClassified(true);
880	nLeftS++;
881	}
882	eventsLeft.push_back(*it);
883	}
884	// remaining nodes go in both lists, bust must be clipped to prevent
885	// events from lying outside the new nodes aabb
886	else
887	{
888	if (!it->getRenderable()->isClassified())
889	{
890	it->getRenderable()->setClassified(true);
891	nBothS++;
892	}
893	eventsRight.push_back(it->clip(best.bright, best.event.getDimension()));
894	eventsLeft.push_back(it->clip(best.bleft, best.event.getDimension()));
895	}
896	it++;
897	}
898
899	// create a new branch node and continue recursion
900	KdTree::Branch * branch = new KdTree::Branch(this, level, aabb, parent,
901	best.event.getSplitPlane(), best.side);
902
903	// now create the child nodes and continue recursion
904	if (eventsLeft.size() > 0)
905	{
906	branch->mLeft = recBuild(eventsLeft, nLeftS + nBothS, best.bleft, branch);
907	}
908	if (eventsRight.size() > 0)
909	{
910	branch->mRight = recBuild(eventsRight, nBothS + nRightS, best.bright, branch);
911	}
912
913	// update stats
914	++ mStats.mNumNodes;
915
916	// update bounding box
917	branch->_updateBounds(false);
918
919	return branch;
920	}
921	}
922
923	KdTree::Node * KdTree::pqBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent)
924	{
925	SplitCandidatePQ pqueue;
926	Real globalTreeCost;
927	Real globalSA;
928
929	KdTree::Node * newNode = 0, * topNode = 0;
930	// init global tree cost
931	globalTreeCost = PlaneEvent::KI * nObjects;
932	globalSA = PlaneEvent::surfaceArea(aabb);
933
934	PlaneEventList * e = new PlaneEventList(events);
935
936	// inital split candidate
937	SplitInfo * best = pqFindPlane(e, nObjects, aabb, globalSA);
938	SplitCandidate splitcandidate(e, nObjects, aabb, parent, globalTreeCost,
939	globalTreeCost - best->cost, best, PlaneEvent::PES_BOTH);
940	pqueue.push(splitcandidate);
941
942
943	/* BEGIN ITERATIVE BUILD */
944	while (!pqueue.empty())
945	{
946	SplitCandidate sc = pqueue.top();
947	pqueue.pop();
948
949	// determine the depth we are on
950	int level = 0;
951	if (sc.parent)
952	{
953	level = sc.parent->getLevel() + 1;
954	}
955
956	/************************************************/
957	/************** BEGIN TERMINATE *************/
958	/************************************************/
959	// check terminating condition
960	if (sc.decrease < 0.0 \|\| level >= mMaxDepth)
961	{
962	// Terminating condition reached, create leaf and add renderables to list
963	KdTree::Leaf * leaf = new KdTree::Leaf(this, level, sc.aabb, sc.parent);
964	KdRenderable *rend;
965	PlaneEventList::iterator begin = sc.events->begin();
966	PlaneEventList::iterator end = sc.events->end();
967	PlaneEventList::iterator it = begin;
968	while (it != end)
969	{
970	rend = it->getRenderable();
971	rend->setClassified(false);
972	if (rend->attachTo(leaf, this))
973	{
974	leaf->insert(rend);
975	}
976	it++;
977	}
978	newNode = leaf;
979	if (!topNode)
980	topNode = leaf;
981	// update stats
982	++ mStats.mNumNodes;
983	++ mStats.mNumLeaves;
984	}
985
986	/************************************************/
987	/************** BEGIN CLASSIFY **************/
988	/************************************************/
989	else
990	{
991	PlaneEventList * eventsLeft = new PlaneEventList();
992	PlaneEventList * eventsRight = new PlaneEventList();
993	PlaneEventList::iterator begin = sc.events->begin();
994	PlaneEventList::iterator end = sc.events->end();
995	PlaneEventList::iterator it = begin;
996	// slightly redundant, since we mark each renderable up to 6 times
997	while (it != end)
998	{
999	it->getRenderable()->setSide(PlaneEvent::PES_BOTH);
1000	it->getRenderable()->setClassified(false);
1001	it++;
1002	}
1003
1004	// now classify all renderables. do they belong to the left child, the right child or both?
1005	it = begin;
1006	while (it != end)
1007	{
1008	it->classify(sc.best->event, sc.best->side);
1009	it++;
1010	}
1011
1012	// divide the event lists
1013	int nLeftS = 0, nRightS = 0, nBothS = 0;
1014	it = begin;
1015	while (it != end)
1016	{
1017	// right-only events go in the right list
1018	if (it->getRenderable()->getSide() == PlaneEvent::PES_RIGHT)
1019	{
1020	if (!it->getRenderable()->isClassified())
1021	{
1022	it->getRenderable()->setClassified(true);
1023	nRightS++;
1024	}
1025
1026	eventsRight->push_back(*it);
1027	}
1028	// left-only events go in the left list
1029	else if (it->getRenderable()->getSide() == PlaneEvent::PES_LEFT)
1030	{
1031	if (!it->getRenderable()->isClassified())
1032	{
1033	it->getRenderable()->setClassified(true);
1034	nLeftS++;
1035	}
1036	eventsLeft->push_back(*it);
1037	}
1038	// the rest goes in both lists after being clipped
1039	else
1040	{
1041	if (!it->getRenderable()->isClassified())
1042	{
1043	it->getRenderable()->setClassified(true);
1044	nBothS++;
1045	}
1046
1047	eventsRight->push_back(it->clip(sc.best->bright, sc.best->event.getDimension()));
1048	eventsLeft->push_back(it->clip(sc.best->bleft, sc.best->event.getDimension()));
1049	}
1050	it++;
1051	}
1052
1053	// create a new branch node
1054	KdTree::Branch * branch = new KdTree::Branch(this, level, sc.aabb, sc.parent,
1055	sc.best->event.getSplitPlane(), sc.best->side);
1056
1057	globalTreeCost -= sc.decrease;
1058
1059
1060	// now for each potential child node, compute the split plane and the cost decrease
1061	// and place them in the queue
1062	if (eventsLeft->size() > 0)
1063	{
1064	best = pqFindPlane(eventsLeft, nLeftS + nBothS, sc.best->bleft, globalSA);
1065	Real old = PlaneEvent::surfaceArea(sc.best->bleft)/globalSAPlaneEvent::KI(nLeftS + nBothS);
1066	SplitCandidate scleft(eventsLeft, nLeftS + nBothS, sc.best->bleft,
1067	branch, old, old - best->cost, best, PlaneEvent::PES_LEFT);
1068	pqueue.push(scleft);
1069	}
1070	// cleanup
1071	else
1072	{
1073	delete eventsLeft;
1074	}
1075
1076	if (eventsRight->size() > 0)
1077	{
1078	best = pqFindPlane(eventsRight, nBothS + nRightS, sc.best->bright, globalSA);
1079	Real old = PlaneEvent::surfaceArea(sc.best->bright)/globalSAPlaneEvent::KI(nBothS + nRightS);
1080	SplitCandidate scright(eventsRight, nBothS + nRightS, sc.best->bright,
1081	branch, old, old - best->cost, best, PlaneEvent::PES_RIGHT);
1082	pqueue.push(scright);
1083	}
1084	// cleanup
1085	else
1086	{
1087	delete eventsRight;
1088	}
1089
1090	newNode = branch;
1091	if (!topNode)
1092	topNode = branch;
1093
1094
1095	// update stats
1096	++ mStats.mNumNodes;
1097	}
1098
1099	// attach new node to parent
1100	if (sc.parent)
1101	{
1102	if (sc.side == PlaneEvent::PES_LEFT)
1103	{
1104	sc.parent->mLeft = newNode;
1105	}
1106	else if (sc.side == PlaneEvent::PES_RIGHT)
1107	{
1108	sc.parent->mRight = newNode;
1109	}
1110	else
1111	{
1112	OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
1113	"PQBUILD SNAFU - CHILD I AM NOT LEFT NOR RIGHT","KdTree::pqBuild");
1114	}
1115	}
1116
1117	// update bounding boxes when geometry (leaf) was added
1118	if (newNode->isLeaf())
1119	newNode->_updateBounds();
1120
1121	//cleanup
1122	OGRE_DELETE(sc.events);
1123	OGRE_DELETE(sc.best);
1124	}
1125	mBuildLog->logMessage("Cost after PQBUILD " + StringConverter::toString(globalTreeCost));
1126	return topNode;
1127	}
1128
1129	//-------------------------------------------------------------------------
1130	SplitInfo * KdTree::pqFindPlane(PlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA)
1131	{
1132	static const int dim = 3;
1133	int pStart, pOn, pEnd;
1134	int nLeft[dim], nPlane[dim], nRight[dim];
1135	for (int i = 0; i < dim; i++)
1136	{
1137	nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
1138	}
1139
1140	SplitInfo split, best;
1141	best.cost = Math::POS_INFINITY;
1142
1143	Real parentSA = PlaneEvent::surfaceArea(aabb);
1144
1145	PlaneEventList::iterator begin = events->begin();
1146	PlaneEventList::iterator end = events->end();
1147	PlaneEventList::iterator it = begin;
1148	// try all planes to find the best one for the given set of objects
1149	while (it != end)
1150	{
1151	PlaneEventList::iterator p = it;
1152	pStart = pOn = pEnd = 0;
1153	while (it != end && p->equalsType(*it, PlaneEvent::PET_END))
1154	{
1155	it++; pEnd++;
1156	}
1157	while (it != end && p->equalsType(*it, PlaneEvent::PET_ON))
1158	{
1159	it++; pOn++;
1160	}
1161	while (it != end && p->equalsType(*it, PlaneEvent::PET_START))
1162	{
1163	it++; pStart++;
1164	}
1165	int d = p->getDimension();
1166	nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
1167	p->pqSAH(globalSA, parentSA, nLeft[d], nPlane[d], nRight[d], aabb, split);
1168	if (split.cost < best.cost)
1169	{
1170	best = split;
1171	}
1172	nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
1173	}
1174	return new SplitInfo(best);
1175	}
1176
1177	/************************************************************************/
1178	/* KdTree rendering functions */
1179	/************************************************************************/
1180
1181	//-------------------------------------------------------------------------
1182	void KdTree::queueVisibleObjects(Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes)
1183	{
1184	if (mKdRoot)
1185	recQueueVisibleObjects(mKdRoot, Root::getSingleton().getCurrentFrameNumber(),
1186	cam, queue, onlyShadowCasters, showBoxes);
1187	}
1188
1189	//-------------------------------------------------------------------------
1190	void KdTree::recQueueVisibleObjects(KdTree::Node * node, unsigned long currentFrame,
1191	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes)
1192	{
1193	// test visibility
1194	if (cam->isVisible(node->mAABB))
1195	{
1196	#if 0
1197	node->queueVisibleObjects(currentFrame, cam, queue, onlyShadowCasters, showBoxes);
1198
1199	if (node->getLeftChild())
1200	recQueueVisibleObjects(node->getLeftChild(), currentFrame, cam, queue, onlyShadowCasters, showBoxes);
1201	if (node->getRightChild())
1202	recQueueVisibleObjects(node->getRightChild(), currentFrame, cam, queue, onlyShadowCasters, showBoxes);
1203	#else
1204	#ifdef KDTREE_DEBUG
1205	WireBoundingBox * wbb = 0;
1206	if (showBoxes)
1207	wbb = node->getWireBoundingBox();
1208	#endif
1209
1210	if (node->isLeaf())
1211	{
1212	KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
1213	KdRenderableList::iterator it = leaf->mKdRenderables.begin();
1214	KdRenderableList::iterator end = leaf->mKdRenderables.end();
1215	while (it != end)
1216	{
1217	if (!(*it)->isQueued(currentFrame, cam))
1218	{
1219	(*it)->queueObjects(cam, queue, onlyShadowCasters);
1220	}
1221	it++;
1222	}
1223	#ifdef KDTREE_DEBUG
1224	if (wbb)
1225	queue->addRenderable(wbb);
1226	#else
1227	if (showBoxes)
1228	queue->addRenderable(leaf->getWireBoundingBox());
1229	#endif
1230	}
1231	else
1232	{
1233	KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
1234	#ifdef KDTREE_DEBUG
1235	if (wbb)
1236	queue->addRenderable(wbb);
1237	#else
1238	if (showBoxes)
1239	queue->addRenderable(branch->getWireBoundingBox());
1240	#endif
1241
1242	if (branch->mLeft)
1243	recQueueVisibleObjects(branch->mLeft, currentFrame, cam, queue, onlyShadowCasters, showBoxes);
1244	if (branch->mRight)
1245	recQueueVisibleObjects(branch->mRight, currentFrame, cam, queue, onlyShadowCasters, showBoxes);
1246	}
1247	#endif
1248	}
1249	}
1250
1251	/************************************************************************/
1252	/* KdTree debug & helper functions */
1253	/************************************************************************/
1254
1255	//-------------------------------------------------------------------------
1256	void KdTree::dump()
1257	{
1258	LogManager::getSingleton().logMessage("#@#@#@#@ Dumping KdTree #@#@#@#@");
1259	if (mKdRoot)
1260	dump(mKdRoot);
1261	}
1262
1263	//-------------------------------------------------------------------------
1264	void KdTree::dump(KdTree::Node * node)
1265	{
1266	LogManager * log = LogManager::getSingletonPtr();
1267	KdTreeSceneNode * scenenode;
1268	String pad;
1269	int p;
1270
1271	pad = "";
1272	for (p = 0; p < node->getLevel(); p++)
1273	{
1274	pad += " ";
1275	}
1276
1277	if (node->isLeaf())
1278	{
1279	KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
1280	KdRenderableList::iterator it = leaf->mKdRenderables.begin();
1281	KdRenderableList::iterator end = leaf->mKdRenderables.end();
1282	while (it != end)
1283	{
1284	scenenode = dynamic_cast<KdTreeSceneNode >(it);
1285	log->logMessage(pad + "# Leaf level " +
1286	StringConverter::toString(node->getLevel()) +
1287	" SceneNode " + scenenode->getName());
1288	log->logMessage(pad + "## Objects: " + scenenode->dumpToString());
1289	it++;
1290	}
1291	}
1292	else
1293	{
1294	KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
1295	if (branch->mLeft)
1296	{
1297	log->logMessage(pad + "# Branch level " +
1298	StringConverter::toString(node->getLevel()) + " Left Child");
1299	dump(branch->mLeft);
1300	}
1301	if (branch->mRight)
1302	{
1303	log->logMessage(pad + "# Branch level " +
1304	StringConverter::toString(node->getLevel()) + " Right Child");
1305	dump(branch->mRight);
1306	}
1307	}
1308	}
1309
1310	//-------------------------------------------------------------------------
1311	Real KdTree::calcCost()
1312	{
1313	if (mKdRoot)
1314	return calcCost(mKdRoot, PlaneEvent::surfaceArea(mKdRoot->mAABB));
1315	else
1316	return 0;
1317	}
1318
1319	//-------------------------------------------------------------------------
1320	Real KdTree::calcCost(KdTree::Node * node, Real vs)
1321	{
1322	if (node == 0)
1323	return 0.0;
1324
1325	if (node->isLeaf())
1326	{
1327	KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
1328	return (PlaneEvent::surfaceArea(node->mAABB)/vs) *
1329	PlaneEvent::KI * leaf->mKdRenderables.size();
1330	}
1331	else
1332	{
1333	KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
1334	return (PlaneEvent::surfaceArea(node->mAABB)/vs) * PlaneEvent::KT +
1335	calcCost(branch->mLeft, vs) + calcCost(branch->mRight, vs);
1336	}
1337	}
1338
1339	/************************************************************************/
1340	/* KdTree::Node/Branch/Leaf functions */
1341	/************************************************************************/
1342
1343	//-------------------------------------------------------------------------
1344	KdTree::Leaf::~Leaf()
1345	{
1346	// detach all scene nodes in the case that we are rebuilding
1347	// the tree but not the scene
1348	KdRenderableList::iterator it = mKdRenderables.begin();
1349	KdRenderableList::iterator end = mKdRenderables.end();
1350	while (it != end)
1351	{
1352	(*it)->detachFrom(this);
1353	it++;
1354	}
1355	mKdRenderables.clear();
1356	}
1357
1358	void KdTree::Leaf::queueVisibleObjects(unsigned long currentFrame,
1359	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes)
1360	{
1361	KdRenderableList::iterator it = mKdRenderables.begin();
1362	KdRenderableList::iterator end = mKdRenderables.end();
1363	while (it != end)
1364	{
1365	if (!(*it)->isQueued(currentFrame, cam))
1366	{
1367	(*it)->queueObjects(cam, queue, onlyShadowCasters);
1368	}
1369	it++;
1370	}
1371
1372	if (showBoxes)
1373	if (mLevel == mOwner->getHiLiteLevel() \|\| mOwner->getShowAllBoxes())
1374	queue->addRenderable(getWireBoundingBox());
1375	}
1376
1377	//-------------------------------------------------------------------------
1378	// update the world aabb based on the contained geometry
1379	void KdTree::Leaf::_updateBounds(bool recurse)
1380	{
1381	// reset box
1382	mWorldAABB.setNull();
1383
1384	// merge boxes from attached geometry
1385	KdRenderableList::iterator it = mKdRenderables.begin();
1386	KdRenderableList::iterator end = mKdRenderables.end();
1387	while (it != end)
1388	{
1389	//(*it)->_updateBounds();
1390	mWorldAABB.merge((*it)->getBoundingBox());
1391	it++;
1392	}
1393
1394	// update parent recursively
1395	if (recurse && mParent)
1396	mParent->_updateBounds(recurse);
1397	}
1398	} // namespace Ogre

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

Download in other formats: