Context Navigation

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

Revision 1285, 42.8 KB checked in by szydlowski, 18 years ago (diff)
saving and loading entities to file

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 "OgreKdTree.h"
11	#include "OgreKdRenderable.h"
12	#include "OgreKdTreeSceneNode.h"
13	#include "OgreKdTreeSceneManager.h"
14
15	#include <OgreStringConverter.h>
16	#include <OgreLogManager.h>
17	#include <OgreRoot.h>
18	#include <OgreTimer.h>
19
20	#include <OgreMaterialManager.h>
21
22	#define PLT_SIZE 101
23
24	namespace Ogre
25	{
26	Real PlaneEvent::KT = 2.0;
27	Real PlaneEvent::KI = 1.0;
28
29	//----------------------------------------------------------------------------
30	// determine if this event is left or right of the reference event
31	void PlaneEvent::classify(const PlaneEvent& e, PlaneEvent::Side side)
32	{
33	// only classify events of the same dimension
34	if (mDimension == e.mDimension)
35	{
36	if (mType == PET_END && mPosition[mDimension] <= e.mPosition[e.mDimension])
37	{
38	mRenderable->setSide(PES_LEFT);
39	}
40	else if (mType == PET_START && mPosition[mDimension] >= e.mPosition[e.mDimension])
41	{
42	mRenderable->setSide(PES_RIGHT);
43	}
44	else if (mType == PET_ON)
45	{
46	if (mPosition[mDimension] < e.mPosition[e.mDimension] \|\|
47	(mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_LEFT))
48	{
49	mRenderable->setSide(PES_LEFT);
50	}
51	if (mPosition[mDimension] > e.mPosition[e.mDimension] \|\|
52	(mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_RIGHT))
53	{
54	mRenderable->setSide(PES_RIGHT);
55	}
56	}
57	}
58	}
59
60	//----------------------------------------------------------------------------
61	// clip this event to an aabb (move it so that the plane on one of the box planes)
62	PlaneEvent PlaneEvent::clip(AxisAlignedBox& box, PlaneEvent::Dimension dim)
63	{
64	Vector3 newpos = mPosition, min = box.getMinimum(), max = box.getMaximum();
65	if (newpos[dim] < min[dim])
66	newpos[dim] = min[dim];
67	else if (newpos[dim] > max[dim])
68	newpos[dim] = max[dim];
69
70	return PlaneEvent(mRenderable, newpos, mDimension, mType);
71	}
72
73	//----------------------------------------------------------------------------
74	// the surface area heuristic to determine the cost of splitting the parent aabb
75	// along the plane represented by this event
76	void PlaneEvent::SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, SplitInfo& split)
77	{
78	Real mu = splitBox(parent, split.bleft, split.bright);
79	Real sav = surfaceArea(parent);
80	Real pl = surfaceArea(split.bleft) / sav;
81	Real pr = surfaceArea(split.bright) / sav;
82	Real costl = splitCost(pl, pr, nLeft + nPlane, nRight, mu);
83	Real costr = splitCost(pl, pr, nLeft, nPlane + nRight, mu);
84
85	if (costl < costr)
86	{
87	split.cost = costl;
88	split.side = PES_LEFT;
89	split.nleft = nLeft + nPlane;
90	split.nright = nRight;
91	}
92	else
93	{
94	split.cost = costr;
95	split.side = PES_RIGHT;
96	split.nleft = nLeft;
97	split.nright = nPlane + nRight;
98
99	}
100	split.event = *this;
101	}
102
103	//----------------------------------------------------------------------------
104	// split the parent aabb with the plane in this event
105	Real PlaneEvent::splitBox(const AxisAlignedBox& parent, AxisAlignedBox& left, AxisAlignedBox& right)
106	{
107	Vector3 bmin = parent.getMinimum();
108	Vector3 bmax = parent.getMaximum();
109	// calculate the penalty for spliting the box that way
110	Real mu = lookupPenalty(
111	(mPosition[mDimension] - bmin[mDimension]) /
112	(bmax[mDimension] - bmin[mDimension]));
113	// set corners which are the same as parent AABB
114	left.setMinimum(bmin);
115	right.setMaximum(bmax);
116	// modify "inner" corners
117	bmin[mDimension] = mPosition[mDimension];
118	bmax[mDimension] = mPosition[mDimension];
119	// set the corners on the split plane
120	left.setMaximum(bmax);
121	right.setMinimum(bmin);
122
123	return mu;
124	}
125
126	//----------------------------------------------------------------------------
127	// compute surface area of a box ... DUH!
128	Real PlaneEvent::surfaceArea(const AxisAlignedBox& box)
129	{
130	Vector3 sides = box.getMaximum() - box.getMinimum();
131	return 2 * sides.x * sides.y +
132	2 * sides.y * sides.z +
133	2 * sides.z * sides.x;
134	}
135
136	//----------------------------------------------------------------------------
137	// lookup the penalty for placing the splitting plane near to the edge of the AABB
138	// 0.0 <= p <= 1.0, p = 0.5 means the plane divides the aabb in half
139	Real PlaneEvent::lookupPenalty(Real p)
140	{
141	// precomputed table of {x^6 + 1\|0 <= x <= 1}
142	static Real mPenaltyLookupTable[PLT_SIZE];
143	static bool init_done = false;
144
145	if (!init_done)
146	{
147	Real step = 1.0 / (PLT_SIZE - 1);
148	Real x = 0.0;
149	//LogManager::getSingleton().logMessage("### Calculating Lookup Table ###");
150	for (int i = 0; i < PLT_SIZE; i++)
151	{
152	mPenaltyLookupTable[i] = Math::Pow(x, 6) + 1.0;
153	x += step;
154	//LogManager::getSingleton().logMessage("### mPenaltyLookupTable[" + StringConverter::toString(i,3) + "]=" + StringConverter::toString(mPenaltyLookupTable[i]));
155	}
156	init_done = true;
157	//LogManager::getSingleton().logMessage("### Lookup Table Calculated ###");
158	}
159
160	// normalize p to [0,1]
161	Real x = Math::Abs(p * 2 - 1);
162	// compute index
163	int i = Math::IFloor(x * (PLT_SIZE - 1));
164
165	return mPenaltyLookupTable[i];
166	}
167
168	//----------------------------------------------------------------------------
169	// compute cost of the split, reward splitting of empty space (lambda, const),
170	// penalize splitting off 'thin' slices (mu, const)
171	Real PlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight)
172	{
173	// reward splitting off chunks of empty space
174	Real lambda = 1.0;
175	if (nLeft == 0 \|\| nRight == 0)
176	{
177	lambda = 0.8;
178	}
179
180	// penalize splitting off small chunks (thin slices)
181	Real mu = 1.0;
182	if (pLeft < 0.1 \|\| pRight < 0.1 \|\| pLeft > 0.9 \|\| pRight > 0.9)
183	{
184	mu = 1.5;
185	}
186	return lambda * mu * (KT + (KI * (pLeftnLeft + pRightnRight)));
187	}
188
189	//----------------------------------------------------------------------------
190	// compute cost of the split, reward splitting of empty space (lambda, const),
191	// penalize splitting off 'thin' slices (mu, parameter)
192	Real PlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
193	{
194	// reward splitting off chunks of empty space
195	Real lambda = 1.0;
196	if (nLeft == 0 \|\| nRight == 0)
197	{
198	lambda = 0.8;
199	}
200
201	return lambda * mu * (KT + (KI * (pLeftnLeft + pRightnRight)));
202	}
203
204	//----------------------------------------------------------------------------
205	// surface area heuristic modified for the priority queue method of building
206	// the probabilities (p, pl, pr) are relative to the global (all enclosing) aabb
207	void PlaneEvent::pqSAH(Real globalSA, Real parentSA, int nLeft, int nPlane, int nRight,
208	AxisAlignedBox& parentBox, SplitInfo& split)
209	{
210	Real mu = splitBox(parentBox, split.bleft, split.bright);
211	Real p = parentSA / globalSA;
212	Real pl = surfaceArea(split.bleft) / globalSA;
213	Real pr = surfaceArea(split.bright) / globalSA;
214	Real costl = pqSplitCost(p, pl, pr, nLeft + nPlane, nRight, mu);
215	Real costr = pqSplitCost(p, pl, pr, nLeft, nPlane + nRight, mu);
216
217	if (costl < costr)
218	{
219	split.cost = costl;
220	split.side = PES_LEFT;
221	split.nleft = nLeft + nPlane;
222	split.nright = nRight;
223	}
224	else
225	{
226	split.cost = costr;
227	split.side = PES_RIGHT;
228	split.nleft = nLeft;
229	split.nright = nPlane + nRight;
230
231	}
232	split.event = *this;
233	}
234
235	//----------------------------------------------------------------------------
236	// compute split cost without any penalties
237	Real PlaneEvent::pqSplitCost(Real pParent, Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
238	{
239	return pParent * KT + (KI * (pLeft * nLeft + pRight * nRight));
240	}
241
242	//----------------------------------------------------------------------------
243	// DEBUG
244	String PlaneEvent::print()
245	{
246	String dim, type;
247	if (mDimension == PED_X)
248	dim = "X";
249	if (mDimension == PED_Y)
250	dim = "Y";
251	if (mDimension == PED_Z)
252	dim = "Z";
253	if (mType == PET_END)
254	type = "END ";
255	if (mType == PET_ON)
256	type = "ON ";
257	if (mType == PET_START)
258	type = "START";
259	//return StringConverter::toString(mPosition[mDimension]) + " " + dim + " " + type;
260	return type + " " + dim + " " + StringConverter::toString(mPosition[mDimension]);
261	};
262
263	//----------------------------------------------------------------------------
264	String SplitInfo::print()
265	{
266	String sside;
267	if (side == PlaneEvent::PES_BOTH)
268	sside = "BOTH ";
269	if (side == PlaneEvent::PES_LEFT)
270	sside = "LEFT ";
271	if (side == PlaneEvent::PES_RIGHT)
272	sside = "RIGHT";
273	return "nLeft: " + StringConverter::toString(nleft, 4) + " nRight: " +
274	StringConverter::toString(nright, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
275	" Side: " + sside + " Event: " + event.print() + " Leftbox: " +
276	StringConverter::toString(bleft.getMinimum()) + ", " +
277	StringConverter::toString(bleft.getMaximum()) + " Rightbox: " +
278	StringConverter::toString(bright.getMinimum()) + ", " +
279	StringConverter::toString(bright.getMaximum());
280	};
281
282	//----------------------------------------------------------------------------
283	String KdTree::SplitCandidate::print()
284	{
285	String sside;
286	if (side == PlaneEvent::PES_BOTH)
287	sside = "BOTH ";
288	if (side == PlaneEvent::PES_LEFT)
289	sside = "LEFT ";
290	if (side == PlaneEvent::PES_RIGHT)
291	sside = "RIGHT";
292	return "List: " + StringConverter::toString(events->size(), 4) + " Objects: " +
293	StringConverter::toString(nObjects, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
294	" Decrease: " + StringConverter::toString(decrease, 8, 9) + " Side: " + sside + " Best: " +
295	best->print() + " Box: " + StringConverter::toString(aabb.getMinimum()) + ", "
296	+ StringConverter::toString(aabb.getMaximum());
297
298	};
299
300	//----------------------------------------------------------------------------
301	//----------------------------------------------------------------------------
302	//----------------------------------------------------------------------------
303
304	KdTree::KdTree(int maxdepth, BuildMethod bm):
305	mMaxDepth(maxdepth),
306	mBuildMethod(bm),
307	mHiLiteLevel(0),
308	mShowAllBoxes(false),
309	mShowNodes(true),
310	mKdRoot(0),
311	mBuildLog(0)
312	{
313	init();
314	}
315
316	KdTree::KdTree(int maxdepth, BuildMethod bm, int hilite, bool allboxes, bool shownodes):
317	mMaxDepth(maxdepth),
318	mBuildMethod(bm),
319	mHiLiteLevel(hilite),
320	mShowAllBoxes(allboxes),
321	mShowNodes(shownodes),
322	mKdRoot(0),
323	mBuildLog(0)
324	{
325	init();
326	}
327
328	KdTree::~KdTree()
329	{
330	delete mKdRoot;
331	}
332
333	void KdTree::init()
334	{
335	MaterialPtr mat;
336	TextureUnitState *tex;
337
338	// init visualization materials (unlit solid green/yellow)
339	mat = MaterialManager::getSingleton().getByName("KdTree/BoxHiLite");
340	if (mat.isNull())
341	{
342	ColourValue green(0, 1, 0);
343	mat = MaterialManager::getSingleton().create("KdTree/BoxHiLite", "General");
344	//mat->setAmbient(green);
345	//mat->setDiffuse(green);
346	mat->setLightingEnabled(false);
347	tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
348	tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, green, green);
349	}
350
351	mat = MaterialManager::getSingleton().getByName("KdTree/BoxViz");
352	if (mat.isNull())
353	{
354	ColourValue yellow(1, 1, 0);
355	mat = MaterialManager::getSingleton().create("KdTree/BoxViz", "General");
356	//mat->setAmbient(yellow);
357	//mat->setDiffuse(yellow);
358	mat->setLightingEnabled(false);
359	tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
360	tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, yellow, yellow);
361	}
362
363	// retrieve or create build log
364	try
365	{
366	mBuildLog = LogManager::getSingleton().getLog(KDTREE_LOGNAME);
367	}
368	catch (Exception&)
369	{
370	mBuildLog = LogManager::getSingleton().createLog(KDTREE_LOGNAME);
371	}
372
373	setEnhancedVis(false);
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(KdTreeCamera* cam, RenderQueue* queue, bool onlyShadowCasters,
1188	bool showBoxes, KdTree::NodeList& visibleNodes)
1189	{
1190	// debug
1191	//cam->mNumVisQueries = 0;
1192
1193	if (mKdRoot)
1194	recQueueVisibleObjects(mKdRoot, Root::getSingleton().getCurrentFrameNumber(),
1195	cam, queue, onlyShadowCasters, showBoxes, visibleNodes);
1196
1197	//mBuildLog->logMessage("Frame # " + StringConverter::toString(Root::getSingleton().getCurrentFrameNumber()) +
1198	// " ," + StringConverter::toString(cam->mNumVisQueries) + " vis queries");
1199	}
1200
1201	//-------------------------------------------------------------------------
1202	void KdTree::recQueueVisibleObjects(KdTree::Node * node, unsigned long currentFrame,
1203	KdTreeCamera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes,
1204	KdTree::NodeList& visibleNodes, bool fullVis)
1205	{
1206	KdTreeCamera::NodeVisibility vis = KdTreeCamera::KDNV_PART;
1207	// test visibility
1208	//if (cam->isVisible(node->mAABB))
1209	if (fullVis \|\|
1210	((vis = (cam->*getVisibility)(node->mAABB)) != KdTreeCamera::KDNV_NONE))
1211	//((vis = (cam->*getVisibility)(node->mAABB)) != KdTreeCamera::KDNV_NONE))
1212	{
1213	visibleNodes.push_back(node);
1214
1215	bool v = (fullVis \|\| vis == KdTreeCamera::KDNV_FULL);
1216	node->queueVisibleObjects(currentFrame, cam, queue, onlyShadowCasters, showBoxes, v);
1217
1218	if (!v)
1219	{
1220
1221	if (node->getLeftChild())
1222	recQueueVisibleObjects(node->getLeftChild(), currentFrame,
1223	cam, queue, onlyShadowCasters, showBoxes, visibleNodes, v);
1224	if (node->getRightChild())
1225	recQueueVisibleObjects(node->getRightChild(), currentFrame,
1226	cam, queue, onlyShadowCasters, showBoxes, visibleNodes, v);
1227	}
1228	}
1229	}
1230
1231	//-------------------------------------------------------------------------
1232	void KdTree::setEnhancedVis(bool enh)
1233	{
1234	if (enh)
1235	getVisibility = &KdTreeCamera::getVisibilityEnhanced;
1236	else
1237	getVisibility = &KdTreeCamera::getVisibilitySimple;
1238	}
1239
1240	//-------------------------------------------------------------------------
1241	bool KdTree::getEnhancedVis()
1242	{
1243	return getVisibility == &KdTreeCamera::getVisibilityEnhanced;
1244	}
1245
1246	//-------------------------------------------------------------------------
1247	//void KdTree::findVisibleNodes(NodeList& visibleNodes, Camera * cam)
1248	//{
1249	// if (mKdRoot)
1250	// recFindVisibleNodes(mKdRoot, visibleNodes, cam);
1251	//}
1252
1253	////-------------------------------------------------------------------------
1254	//void KdTree::recFindVisibleNodes(KdTree::Node * node, NodeList& visibleNodes, Camera * cam)
1255	//{
1256	// // test visibility
1257	// if (cam->isVisible(node->mAABB))
1258	// {
1259	// visibleNodes.push_back(node);
1260
1261	// if (node->getLeftChild())
1262	// recFindVisibleNodes(node->getLeftChild(), visibleNodes, cam);
1263	// if (node->getRightChild())
1264	// recFindVisibleNodes(node->getRightChild(), visibleNodes, cam);
1265	// }
1266	//}
1267
1268	/************************************************************************/
1269	/* KdTree debug & helper functions */
1270	/************************************************************************/
1271
1272	//-------------------------------------------------------------------------
1273	void KdTree::dump()
1274	{
1275	//LogManager::getSingleton().logMessage("#@#@#@#@ Dumping KdTree #@#@#@#@");
1276	mBuildLog->logMessage("#@#@#@#@ Dumping KdTree #@#@#@#@");
1277	if (mKdRoot)
1278	dump(mKdRoot);
1279	}
1280
1281	//-------------------------------------------------------------------------
1282	void KdTree::dump(KdTree::Node * node)
1283	{
1284	//LogManager * log = LogManager::getSingletonPtr();
1285	KdTreeSceneNode * scenenode;
1286	String pad;
1287	int p;
1288
1289	pad = "";
1290	for (p = 0; p < node->getLevel(); p++)
1291	{
1292	pad += " ";
1293	}
1294
1295	if (node->isLeaf())
1296	{
1297	KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
1298	KdRenderableList::iterator it = leaf->mKdRenderables.begin();
1299	KdRenderableList::iterator end = leaf->mKdRenderables.end();
1300	while (it != end)
1301	{
1302	scenenode = dynamic_cast<KdTreeSceneNode >(it);
1303	mBuildLog->logMessage(pad + "# Leaf level " +
1304	StringConverter::toString(node->getLevel()) +
1305	" SceneNode " + scenenode->getName());
1306	mBuildLog->logMessage(pad + "## Objects: " + scenenode->dumpToString());
1307	it++;
1308	}
1309	}
1310	else
1311	{
1312	KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
1313	if (branch->mLeft)
1314	{
1315	mBuildLog->logMessage(pad + "# Branch level " +
1316	StringConverter::toString(node->getLevel()) + " Left Child");
1317	dump(branch->mLeft);
1318	}
1319	if (branch->mRight)
1320	{
1321	mBuildLog->logMessage(pad + "# Branch level " +
1322	StringConverter::toString(node->getLevel()) + " Right Child");
1323	dump(branch->mRight);
1324	}
1325	}
1326	}
1327
1328	//-------------------------------------------------------------------------
1329	Real KdTree::calcCost()
1330	{
1331	if (mKdRoot)
1332	return calcCost(mKdRoot, PlaneEvent::surfaceArea(mKdRoot->mAABB));
1333	else
1334	return 0;
1335	}
1336
1337	//-------------------------------------------------------------------------
1338	Real KdTree::calcCost(KdTree::Node * node, Real vs)
1339	{
1340	if (node == 0)
1341	return 0.0;
1342
1343	if (node->isLeaf())
1344	{
1345	KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
1346	return (PlaneEvent::surfaceArea(node->mAABB)/vs) *
1347	PlaneEvent::KI * leaf->mKdRenderables.size();
1348	}
1349	else
1350	{
1351	KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
1352	return (PlaneEvent::surfaceArea(node->mAABB)/vs) * PlaneEvent::KT +
1353	calcCost(branch->mLeft, vs) + calcCost(branch->mRight, vs);
1354	}
1355	}
1356
1357	/************************************************************************/
1358	/* KdTree::Node/Branch/Leaf functions */
1359	/************************************************************************/
1360
1361	//-------------------------------------------------------------------------
1362	KdTree::Leaf::~Leaf()
1363	{
1364	// detach all scene nodes in the case that we are rebuilding
1365	// the tree but not the scene
1366	KdRenderableList::iterator it = mKdRenderables.begin();
1367	KdRenderableList::iterator end = mKdRenderables.end();
1368	while (it != end)
1369	{
1370	(*it)->detachFrom(this);
1371	it++;
1372	}
1373	mKdRenderables.clear();
1374	}
1375
1376	//-------------------------------------------------------------------------
1377	void KdTree::Leaf::queueVisibleObjects(unsigned long currentFrame,
1378	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis)
1379	{
1380	KdRenderableList::iterator it = mKdRenderables.begin();
1381	KdRenderableList::iterator end = mKdRenderables.end();
1382	while (it != end)
1383	{
1384	if (!(*it)->isQueued(currentFrame, cam))
1385	{
1386	(*it)->queueObjects(cam, queue, onlyShadowCasters);
1387	}
1388	it++;
1389	}
1390
1391	if (showBoxes)
1392	if (mLevel == mOwner->getHiLiteLevel() \|\| mOwner->getShowAllBoxes())
1393	queue->addRenderable(getWireBoundingBox());
1394	}
1395
1396	//-------------------------------------------------------------------------
1397	void KdTree::Leaf::getGeometryList(GtpVisibility::GeometryVector *geometryList)
1398	{
1399	KdRenderableList::iterator it = mKdRenderables.begin();
1400	KdRenderableList::iterator end = mKdRenderables.end();
1401	while (it != end)
1402	{
1403	(*it)->getGeometryList(geometryList);
1404	it++;
1405	}
1406	}
1407
1408	//-------------------------------------------------------------------------
1409	// update the world aabb based on the contained geometry
1410	void KdTree::Leaf::_updateBounds(bool recurse)
1411	{
1412	// reset box
1413	mWorldAABB.setNull();
1414
1415	// merge boxes from attached geometry
1416	KdRenderableList::iterator it = mKdRenderables.begin();
1417	KdRenderableList::iterator end = mKdRenderables.end();
1418	while (it != end)
1419	{
1420	//(*it)->_updateBounds();
1421	mWorldAABB.merge((*it)->getBoundingBox());
1422	it++;
1423	}
1424
1425	// update parent recursively
1426	if (recurse && mParent)
1427	mParent->_updateBounds(recurse);
1428	}
1429	} // namespace Ogre

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

Download in other formats: