Context Navigation

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

Revision 1173, 44.4 KB checked in by szydlowski, 18 years ago (diff)
Finished kdtree hierarchy interface, started modifications to kdtree scene manager

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

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

Download in other formats: