Context Navigation

source: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreBiHierarchy.cpp @ 2361

Revision 2361, 58.4 KB checked in by mattausch, 17 years ago (diff)

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 "OgreBiHierarchy.h"
11	#include "OgreBihRenderable.h"
12	#include "OgreBiHierarchySceneNode.h"
13	#include "OgreBiHierarchySceneManager.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
27	enum BihIntersection
28	{
29	OUTSIDE=0,
30	INSIDE=1,
31	INTERSECT=2
32	};
33
34	static BihIntersection intersect( const Ray &one, const AxisAlignedBox &two )
35	{
36	// Null box?
37	if (two.isNull()) return OUTSIDE;
38
39	bool inside = true;
40	const Vector3* pCorners = two.getAllCorners();
41	Vector3 origin = one.getOrigin();
42	Vector3 dir = one.getDirection();
43
44	Vector3 maxT(-1, -1, -1);
45
46	int i = 0;
47	for(i=0; i<3; i++ )
48	{
49	if( origin[i] < pCorners[0][i] )
50	{
51	inside = false;
52	if( dir[i] > 0 )
53	{
54	maxT[i] = (pCorners[0][i] - origin[i])/ dir[i];
55	}
56	}
57	else if( origin[i] > pCorners[4][i] )
58	{
59	inside = false;
60	if( dir[i] < 0 )
61	{
62	maxT[i] = (pCorners[4][i] - origin[i]) / dir[i];
63	}
64	}
65	}
66
67	if( inside )
68	{
69	return INTERSECT;
70	}
71	int whichPlane = 0;
72	if( maxT[1] > maxT[whichPlane])
73	whichPlane = 1;
74	if( maxT[2] > maxT[whichPlane])
75	whichPlane = 2;
76
77	if( ((int)maxT[whichPlane]) & 0x80000000 )
78	{
79	return OUTSIDE;
80	}
81	for(i=0; i<3; i++ )
82	{
83	if( i!= whichPlane )
84	{
85	float f = origin[i] + maxT[whichPlane] * dir[i];
86	if ( f < (pCorners[0][i] - 0.00001f) \|\|
87	f > (pCorners[4][i] +0.00001f ) )
88	{
89	return OUTSIDE;
90	}
91	}
92	}
93
94	return INTERSECT;
95
96	}
97
98
99	/** Checks how the second box intersects with the first.
100	*/
101	static BihIntersection intersect( const PlaneBoundedVolume &one, const AxisAlignedBox &two )
102	{
103	// Null box?
104	if (two.isNull()) return OUTSIDE;
105
106	// Get corners of the box
107	const Vector3* pCorners = two.getAllCorners();
108
109	// For each plane, see if all points are on the negative side
110	// If so, object is not visible.
111	// If one or more are, it's partial.
112	// If all aren't, full
113	int corners[ 8 ] = {0, 4, 3, 5, 2, 6, 1, 7};
114	bool all_inside = true;
115	PlaneList::const_iterator i, iend;
116	iend = one.planes.end();
117	for (i = one.planes.begin(); i != iend; ++i)
118	{
119	const Plane& plane = *i;
120	bool all_outside = true;
121
122	float distance = 0;
123
124	for ( int corner = 0; corner < 8; ++corner )
125	{
126	distance = plane.getDistance( pCorners[ corners[ corner ] ] );
127	all_outside = all_outside && ( distance < 0 );
128	all_inside = all_inside && ( distance >= 0 );
129
130	if ( !all_outside && !all_inside )
131	break;
132	}
133
134	if ( all_outside )
135	return OUTSIDE;
136	}
137
138	if ( all_inside )
139	return INSIDE;
140	else
141	return INTERSECT;
142
143	}
144
145
146	/** Checks how the second box intersects with the first.
147	*/
148	static BihIntersection intersect( const AxisAlignedBox &one, const AxisAlignedBox &two )
149	{
150	// Null box?
151	if (one.isNull() \|\| two.isNull()) return OUTSIDE;
152
153	const Vector3 * outside = one.getAllCorners();
154	const Vector3 *inside = two.getAllCorners();
155
156	if ( inside[ 4 ].x < outside[ 0 ].x \|\|
157	inside[ 4 ].y < outside[ 0 ].y \|\|
158	inside[ 4 ].z < outside[ 0 ].z \|\|
159	inside[ 0 ].x > outside[ 4 ].x \|\|
160	inside[ 0 ].y > outside[ 4 ].y \|\|
161	inside[ 0 ].z > outside[ 4 ].z )
162	{
163	return OUTSIDE;
164	}
165
166	bool full = ( inside[ 0 ].x > outside[ 0 ].x &&
167	inside[ 0 ].y > outside[ 0 ].y &&
168	inside[ 0 ].z > outside[ 0 ].z &&
169	inside[ 4 ].x < outside[ 4 ].x &&
170	inside[ 4 ].y < outside[ 4 ].y &&
171	inside[ 4 ].z < outside[ 4 ].z );
172
173	if ( full )
174	return INSIDE;
175	else
176	return INTERSECT;
177
178	}
179
180	/** Checks how the box intersects with the sphere.
181	*/
182	static BihIntersection intersect( const Sphere &one, const AxisAlignedBox &two )
183	{
184	// Null box?
185	if (two.isNull()) return OUTSIDE;
186
187	float sradius = one.getRadius();
188
189	sradius *= sradius;
190
191	Vector3 scenter = one.getCenter();
192
193	const Vector3 *corners = two.getAllCorners();
194
195	float s, d = 0;
196
197	Vector3 mndistance = ( corners[ 0 ] - scenter );
198	Vector3 mxdistance = ( corners[ 4 ] - scenter );
199
200	if ( mndistance.squaredLength() < sradius &&
201	mxdistance.squaredLength() < sradius )
202	{
203	return INSIDE;
204	}
205
206	//find the square of the distance
207	//from the sphere to the box
208	for ( int i = 0 ; i < 3 ; i++ )
209	{
210	if ( scenter[ i ] < corners[ 0 ][ i ] )
211	{
212	s = scenter[ i ] - corners[ 0 ][ i ];
213	d += s * s;
214	}
215
216	else if ( scenter[ i ] > corners[ 4 ][ i ] )
217	{
218	s = scenter[ i ] - corners[ 4 ][ i ];
219	d += s * s;
220	}
221
222	}
223
224	bool partial = ( d <= sradius );
225
226	if ( !partial )
227	{
228	return OUTSIDE;
229	}
230
231	else
232	{
233	return INTERSECT;
234	}
235	}
236
237	Real BihPlaneEvent::KT = 2.0;
238	Real BihPlaneEvent::KI = 2.0;
239
240	//----------------------------------------------------------------------------
241	// determine if this event is left or right of the reference event
242	// if the absolute flag is set, we decide by the objectcenter wether the
243	// event goes to left or right.
244	void BihPlaneEvent::classify(const BihPlaneEvent& e, BihPlaneEvent::Side side, bool absolute)
245	{
246	// only classify events of the same dimension
247	if (mDimension == e.mDimension)
248	{
249	if (!absolute)
250	{
251	if (mType == PET_END && mPosition[mDimension] <= e.mPosition[e.mDimension])
252	{
253	mRenderable->setSide(PES_LEFT);
254	return;
255	}
256	else if (mType == PET_START && mPosition[mDimension] >= e.mPosition[e.mDimension])
257	{
258	mRenderable->setSide(PES_RIGHT);
259	return;
260	}
261	else if (mType == PET_ON)
262	{
263	if (mPosition[mDimension] < e.mPosition[e.mDimension] \|\|
264	(mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_LEFT))
265	{
266	mRenderable->setSide(PES_LEFT);
267	return;
268	}
269	if (mPosition[mDimension] > e.mPosition[e.mDimension] \|\|
270	(mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_RIGHT))
271	{
272	mRenderable->setSide(PES_RIGHT);
273	return;
274	}
275	}
276	} else
277	{
278	// The object lies on the splitting plane
279	// we decide with the object center if it goes right or left.
280	Vector3 mMid=mRenderable->getBoundingBox().getCenter();
281	float mMidDimension=0;
282	switch (mDimension)
283	{
284	case BihPlaneEvent::PED_X:
285	mMidDimension=mMid.x;
286	break;
287	case BihPlaneEvent::PED_Y:
288	mMidDimension=mMid.y;
289	break;
290	case BihPlaneEvent::PED_Z:
291	mMidDimension=mMid.z;
292	break;
293	}
294	if (mMidDimension <= e.mPosition[e.mDimension])
295	{
296	mRenderable->setSide(PES_LEFT);
297	return;
298	}
299	else if (mMidDimension > e.mPosition[e.mDimension])
300	{
301	mRenderable->setSide(PES_RIGHT);
302	return;
303	}
304	}
305
306
307
308
309	}
310	}
311
312	//----------------------------------------------------------------------------
313	// clip this event to an aabb (move it so that the plane on one of the box planes)
314	BihPlaneEvent BihPlaneEvent::clip(AxisAlignedBox& box, BihPlaneEvent::Dimension dim)
315	{
316	Vector3 newpos = mPosition, min = box.getMinimum(), max = box.getMaximum();
317	if (newpos[dim] < min[dim])
318	newpos[dim] = min[dim];
319	else if (newpos[dim] > max[dim])
320	newpos[dim] = max[dim];
321
322	return BihPlaneEvent(mRenderable, newpos, mDimension, mType);
323	}
324
325	//----------------------------------------------------------------------------
326	// the surface area heuristic to determine the cost of splitting the parent aabb
327	// along the plane represented by this event
328	void BihPlaneEvent::SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, BihSplitInfo& split)
329	{
330	Real mu = splitBox(parent, split.bleft, split.bright);
331	Real sav = surfaceArea(parent);
332	Real pl = surfaceArea(split.bleft) / sav;
333	Real pr = surfaceArea(split.bright) / sav;
334	Real costl = splitCost(pl, pr, nLeft + nPlane, nRight, mu);
335	Real costr = splitCost(pl, pr, nLeft, nPlane + nRight, mu);
336
337	if (costl < costr)
338	{
339	split.cost = costl;
340	split.side = PES_LEFT;
341	split.nleft = nLeft + nPlane;
342	split.nright = nRight;
343	}
344	else
345	{
346	split.cost = costr;
347	split.side = PES_RIGHT;
348	split.nleft = nLeft;
349	split.nright = nPlane + nRight;
350
351	}
352	split.event = *this;
353	}
354
355	//----------------------------------------------------------------------------
356	// the surface area heuristic to determine the cost of splitting the parent aabb
357	// along the plane represented by this event modified for BV
358
359	void BihPlaneEvent::SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, BihSplitInfo& split,AxisAlignedBox left,AxisAlignedBox right)
360	{
361	//Real mu = splitBox(parent, split.bleft, split.bright);
362	split.bleft=left;
363	split.bright=right;
364	Vector3 bmin = parent.getMinimum();
365	Vector3 bmax = parent.getMaximum();
366	Real mu=lookupPenalty(
367	(mPosition[mDimension] - bmin[mDimension]) /
368	(bmax[mDimension] - bmin[mDimension]));
369	Real sav = surfaceArea(parent);
370	Real pl = surfaceArea(split.bleft) / sav;
371	Real pr = surfaceArea(split.bright) / sav;
372	Real costl = splitCost(pl, pr, nLeft + nPlane, nRight, mu);
373	Real costr = splitCost(pl, pr, nLeft, nPlane + nRight, mu);
374
375	if (costl < costr)
376	{
377	split.cost = costl;
378	split.side = PES_LEFT;
379	split.nleft = nLeft + nPlane;
380	split.nright = nRight;
381	}
382	else
383	{
384	split.cost = costr;
385	split.side = PES_RIGHT;
386	split.nleft = nLeft;
387	split.nright = nPlane + nRight;
388
389	}
390	split.event = *this;
391	}
392
393	//----------------------------------------------------------------------------
394	// split the parent aabb with the plane in this event
395	Real BihPlaneEvent::splitBox(const AxisAlignedBox& parent, AxisAlignedBox& left, AxisAlignedBox& right)
396	{
397	Vector3 bmin = parent.getMinimum();
398	Vector3 bmax = parent.getMaximum();
399	// calculate the penalty for spliting the box that way
400	Real mu = lookupPenalty(
401	(mPosition[mDimension] - bmin[mDimension]) /
402	(bmax[mDimension] - bmin[mDimension]));
403	// set corners which are the same as parent AABB
404	left.setMinimum(bmin);
405	right.setMaximum(bmax);
406	// modify "inner" corners
407	bmin[mDimension] = mPosition[mDimension];
408	bmax[mDimension] = mPosition[mDimension];
409	// set the corners on the split plane
410	left.setMaximum(bmax);
411	right.setMinimum(bmin);
412
413	return mu;
414	}
415
416	//----------------------------------------------------------------------------
417	// compute surface area of a box ... DUH!
418	Real BihPlaneEvent::surfaceArea(const AxisAlignedBox& box)
419	{
420	Vector3 sides = box.getMaximum() - box.getMinimum();
421	return 2 * sides.x * sides.y +
422	2 * sides.y * sides.z +
423	2 * sides.z * sides.x;
424	}
425
426	//----------------------------------------------------------------------------
427	// lookup the penalty for placing the splitting plane near to the edge of the AABB
428	// 0.0 <= p <= 1.0, p = 0.5 means the plane divides the aabb in half
429	Real BihPlaneEvent::lookupPenalty(Real p)
430	{
431	// precomputed table of {x^6 + 1\|0 <= x <= 1}
432	static Real mPenaltyLookupTable[PLT_SIZE];
433	static bool init_done = false;
434
435	if (!init_done)
436	{
437	Real step = 1.0 / (PLT_SIZE - 1);
438	Real x = 0.0;
439	//LogManager::getSingleton().logMessage("### Calculating Lookup Table ###");
440	for (int i = 0; i < PLT_SIZE; i++)
441	{
442	mPenaltyLookupTable[i] = Math::Pow(x, 6) + 1.0;
443	x += step;
444	//LogManager::getSingleton().logMessage("### mPenaltyLookupTable[" + StringConverter::toString(i,3) + "]=" + StringConverter::toString(mPenaltyLookupTable[i]));
445	}
446	init_done = true;
447	//LogManager::getSingleton().logMessage("### Lookup Table Calculated ###");
448	}
449
450	// normalize p to [0,1]
451	Real x = Math::Abs(p * 2 - 1);
452	// compute index
453	int i = Math::IFloor(x * (PLT_SIZE - 1));
454
455	return mPenaltyLookupTable[i];
456	}
457
458	//----------------------------------------------------------------------------
459	// compute cost of the split, reward splitting of empty space (lambda, const),
460	// penalize splitting off 'thin' slices (mu, const)
461	Real BihPlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight)
462	{
463	// reward splitting off chunks of empty space
464	Real lambda = 1.0;
465	if (nLeft == 0 \|\| nRight == 0)
466	{
467	lambda = 0.8;
468	}
469
470	// penalize splitting off small chunks (thin slices)
471	Real mu = 1.0;
472	if (pLeft < 0.1 \|\| pRight < 0.1 \|\| pLeft > 0.9 \|\| pRight > 0.9)
473	{
474	mu = 1.5;
475	}
476	return lambda * mu * (KT + (KI * (pLeftnLeft + pRightnRight)));
477	}
478
479	//----------------------------------------------------------------------------
480	// compute cost of the split, reward splitting of empty space (lambda, const),
481	// penalize splitting off 'thin' slices (mu, parameter)
482	Real BihPlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
483	{
484	// reward splitting off chunks of empty space
485	Real lambda = 1.0;
486	if (nLeft == 0 \|\| nRight == 0)
487	{
488	lambda = 0.8;
489	}
490
491	return lambda * mu * (KT + (KI * (pLeftnLeft + pRightnRight)));
492	}
493
494	//----------------------------------------------------------------------------
495	// surface area heuristic modified for the priority queue method of building
496	// the probabilities (p, pl, pr) are relative to the global (all enclosing) aabb
497	void BihPlaneEvent::pqSAH(Real globalSA,
498	Real parentSA,
499	int nLeft,
500	int nPlane,
501	int nRight,
502	AxisAlignedBox& parentBox,
503	BihSplitInfo& split)
504	{
505	Real mu = splitBox(parentBox, split.bleft, split.bright);
506	Real p = parentSA / globalSA;
507	Real pl = surfaceArea(split.bleft) / globalSA;
508	Real pr = surfaceArea(split.bright) / globalSA;
509	Real costl = pqSplitCost(p, pl, pr, nLeft + nPlane, nRight, mu);
510	Real costr = pqSplitCost(p, pl, pr, nLeft, nPlane + nRight, mu);
511
512	if (costl < costr)
513	{
514	split.cost = costl;
515	split.side = PES_LEFT;
516	split.nleft = nLeft + nPlane;
517	split.nright = nRight;
518	}
519	else
520	{
521	split.cost = costr;
522	split.side = PES_RIGHT;
523	split.nleft = nLeft;
524	split.nright = nPlane + nRight;
525
526	}
527	split.event = *this;
528	}
529
530	//----------------------------------------------------------------------------
531	// compute split cost without any penalties
532	Real BihPlaneEvent::pqSplitCost(Real pParent, Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
533	{
534	return pParent * KT + (KI * (pLeft * nLeft + pRight * nRight));
535	}
536
537	//----------------------------------------------------------------------------
538	// DEBUG
539	String BihPlaneEvent::print()
540	{
541	String dim, type;
542	if (mDimension == PED_X)
543	dim = "X";
544	if (mDimension == PED_Y)
545	dim = "Y";
546	if (mDimension == PED_Z)
547	dim = "Z";
548	if (mType == PET_END)
549	type = "END ";
550	if (mType == PET_ON)
551	type = "ON ";
552	if (mType == PET_START)
553	type = "START";
554	//return StringConverter::toString(mPosition[mDimension]) + " " + dim + " " + type;
555	return type + " " + dim + " " + StringConverter::toString(mPosition[mDimension]);
556	};
557
558	//----------------------------------------------------------------------------
559	String BihSplitInfo::print()
560	{
561	String sside;
562	if (side == BihPlaneEvent::PES_BOTH)
563	sside = "BOTH ";
564	if (side == BihPlaneEvent::PES_LEFT)
565	sside = "LEFT ";
566	if (side == BihPlaneEvent::PES_RIGHT)
567	sside = "RIGHT";
568	return "nLeft: " + StringConverter::toString(nleft, 4) + " nRight: " +
569	StringConverter::toString(nright, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
570	" Side: " + sside + " Event: " + event.print() + " Leftbox: " +
571	StringConverter::toString(bleft.getMinimum()) + ", " +
572	StringConverter::toString(bleft.getMaximum()) + " Rightbox: " +
573	StringConverter::toString(bright.getMinimum()) + ", " +
574	StringConverter::toString(bright.getMaximum());
575	};
576
577	//----------------------------------------------------------------------------
578	String BiHierarchy::BihSubdivisionCandidate::print()
579	{
580	String sside;
581	if (side == BihPlaneEvent::PES_BOTH)
582	sside = "BOTH ";
583	if (side == BihPlaneEvent::PES_LEFT)
584	sside = "LEFT ";
585	if (side == BihPlaneEvent::PES_RIGHT)
586	sside = "RIGHT";
587	return "List: " + StringConverter::toString(events->size(), 4) + " Objects: " +
588	StringConverter::toString(nObjects, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
589	" Decrease: " + StringConverter::toString(decrease, 8, 9) + " Side: " + sside + " Best: " +
590	best->print() + " Box: " + StringConverter::toString(aabb.getMinimum()) + ", "
591	+ StringConverter::toString(aabb.getMaximum());
592
593	};
594
595	//----------------------------------------------------------------------------
596	//----------------------------------------------------------------------------
597	//----------------------------------------------------------------------------
598
599	BiHierarchy::BiHierarchy(int maxdepth, BuildMethod bm):
600	mMaxDepth(maxdepth),
601	mBuildMethod(bm),
602	mHiLiteLevel(0),
603	mShowAllBoxes(false),
604	mShowNodes(true),
605	mBihRoot(0),
606	mBuildLog(0),
607	mAlgorithm(BIHAL_SAH)
608	{
609	init();
610	}
611
612	BiHierarchy::BiHierarchy(int maxdepth, BuildMethod bm, int hilite, bool allboxes, bool shownodes):
613	mMaxDepth(maxdepth),
614	mBuildMethod(bm),
615	mHiLiteLevel(hilite),
616	mShowAllBoxes(allboxes),
617	mShowNodes(shownodes),
618	mBihRoot(0),
619	mBuildLog(0),
620	mAlgorithm(BIHAL_SAH)
621	{
622	init();
623	}
624
625	BiHierarchy::~BiHierarchy()
626	{
627	delete mBihRoot;
628	}
629
630	void BiHierarchy::init()
631	{
632	MaterialPtr mat;
633	TextureUnitState *tex;
634
635	// init visualization materials (unlit solid green/yellow)
636	mat = MaterialManager::getSingleton().getByName("BiHierarchy/BoxHiLite");
637	if (mat.isNull())
638	{
639	ColourValue green(0, 1, 0);
640	mat = MaterialManager::getSingleton().create("BiHierarchy/BoxHiLite", "General");
641	//mat->setAmbient(green);
642	//mat->setDiffuse(green);
643	mat->setLightingEnabled(false);
644	tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
645	tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, green, green);
646	}
647
648	mat = MaterialManager::getSingleton().getByName("BiHierarchy/BoxLeft");
649	if (mat.isNull())
650	{
651	ColourValue red(1, 0, 0);
652	mat = MaterialManager::getSingleton().create("BiHierarchy/BoxLeft", "General");
653	//mat->setAmbient(green);
654	//mat->setDiffuse(green);
655	mat->setLightingEnabled(false);
656	tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
657
658	tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, red, red);
659	}
660
661	mat = MaterialManager::getSingleton().getByName("BiHierarchy/BoxRight");
662	if (mat.isNull())
663	{
664	ColourValue green(0, 1, 0);
665	mat = MaterialManager::getSingleton().create("BiHierarchy/BoxRight", "General");
666	//mat->setAmbient(green);
667	//mat->setDiffuse(green);
668	mat->setLightingEnabled(false);
669	tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
670	tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, green, green);
671	}
672	mat = MaterialManager::getSingleton().getByName("BiHierarchy/BoxLeftDark");
673	if (mat.isNull())
674	{
675	ColourValue red(0.5, 0, 0);
676	mat = MaterialManager::getSingleton().create("BiHierarchy/BoxLeftDark", "General");
677	//mat->setAmbient(green);
678	//mat->setDiffuse(green);
679	mat->setLightingEnabled(false);
680	tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
681
682	tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, red, red);
683	}
684
685	mat = MaterialManager::getSingleton().getByName("BiHierarchy/BoxRightDark");
686	if (mat.isNull())
687	{
688	ColourValue green(0, 0.5, 0);
689	mat = MaterialManager::getSingleton().create("BiHierarchy/BoxRightDark", "General");
690	//mat->setAmbient(green);
691	//mat->setDiffuse(green);
692	mat->setLightingEnabled(false);
693	tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
694	tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, green, green);
695	}
696
697	mat = MaterialManager::getSingleton().getByName("BiHierarchy/BoxViz");
698	if (mat.isNull())
699	{
700	ColourValue yellow(1, 1, 0);
701	mat = MaterialManager::getSingleton().create("BiHierarchy/BoxViz", "General");
702	//mat->setAmbient(yellow);
703	//mat->setDiffuse(yellow);
704	mat->setLightingEnabled(false);
705	tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
706	tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, yellow, yellow);
707	}
708	mat = MaterialManager::getSingleton().getByName("BaseWhiteNoLighting");
709	if (mat.isNull())
710	{
711	ColourValue white(1, 1, 0);
712	mat = MaterialManager::getSingleton().create("BaseWhiteNoLighting", "General");
713	//mat->setAmbient(yellow);
714	//mat->setDiffuse(yellow);
715	mat->setLightingEnabled(false);
716	tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
717	tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, white, white);
718	}
719
720	// retrieve or create build log
721	try
722	{
723	mBuildLog = LogManager::getSingleton().getLog(BiHierarchy_LOGNAME);
724	}
725	catch (Exception&)
726	{
727	mBuildLog = LogManager::getSingleton().createLog(BiHierarchy_LOGNAME);
728	}
729
730	setEnhancedVis(false);
731	}
732
733	/************************************************************************/
734	/* BiHierarchy insert/delete functions */
735	/************************************************************************/
736
737	void BiHierarchy::remove(BihRenderable * rend)
738	{
739	// DEBUG
740	//LogManager::getSingleton().logMessage("-- Removing SceneNode: " + (static_cast<BiHierarchySceneNode *>(rend))->getName());
741	std::queue<LeafPtr> cleanup;
742	LeafPtr leaf;
743	LeafSet ls = rend->getLeaves();
744	LeafSet::iterator it = ls.begin();
745	LeafSet::iterator end = ls.end();
746	while (it != end)
747	{
748	cleanup.push(*it);
749	it++;
750	}
751	while (!cleanup.empty())
752	{
753	leaf = cleanup.front();
754	cleanup.pop();
755	leaf->remove(rend);
756	bool gone = rend->detachFrom(leaf);
757	assert(gone && "Failed to detach leave which is abso-fuckin-lutely impossible!!!");
758	//dump();
759	recDelete(leaf);
760	//dump();
761	}
762	}
763
764	void BiHierarchy::recDelete(BiHierarchy::Node * node)
765	{
766	if (node == 0) // DEBUG
767	{
768	OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
769	"SNAFU while inserting BihRenderable into BiHierarchy.",
770	"BiHierarchy::recInsert" );
771	return;
772	}
773
774	if (node->isEmpty())
775	{
776	if (node == mBihRoot)
777	{
778	OGRE_DELETE(mBihRoot);
779	}
780	else
781	{
782	BiHierarchy::Branch * parent = BIHBRANCHPTR_CAST(node->getParent());
783	if (node == parent->mLeft)
784	{
785	OGRE_DELETE(parent->mLeft);
786	}
787	else if (node == parent->mRight)
788	{
789	OGRE_DELETE(parent->mRight);
790	}
791	recDelete(parent);
792	}
793	}
794	}
795
796	void BiHierarchy::insert(BihRenderable * rend)
797	{
798	// make sure the tree exists
799	if (mBihRoot)
800	{
801	// make sure the renderable is inside the world bounding box
802	AxisAlignedBox aabb = rend->getBoundingBox();
803	AxisAlignedBox isect = mBihRoot->mAABB.intersection(aabb);
804	if (isect.getMinimum() == aabb.getMinimum() && isect.getMaximum() == aabb.getMaximum())
805	{
806	recInsert(mBihRoot, rend);
807	}
808	else
809	{
810	//LogManager::getSingleton().logMessage("Inserted node outside of world AABB.");
811	BihRenderableList nodelist;
812	nodelist.push_back(rend);
813	addRendToList(mBihRoot, nodelist);
814	OGRE_DELETE(mBihRoot);
815	mBihRoot = buildFromList(nodelist, 0, AxisAlignedBox());
816	}
817	}
818	// otherwise build a new one
819	else
820	{
821	build(rend);
822	}
823	}
824
825	void BiHierarchy::recInsert(BiHierarchy::Node * node, BihRenderable * rend)
826	{
827	if (node == 0) // DEBUG
828	{
829	OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
830	"SNAFU while inserting BihRenderable into BiHierarchy.",
831	"BiHierarchy::recInsert" );
832	return;
833	}
834
835	// rebuild the leaf/replace with subtree ...
836	if (node->isLeaf())
837	{
838	//LogManager::getSingleton().logMessage("## Replacing leaf.");
839	rebuildSubtree(node, rend);
840	}
841	else
842	{
843	BiHierarchy::Branch * branch = BIHBRANCHPTR_CAST(node);
844	AxisAlignedBox aabb = rend->getBoundingBox();
845	Plane::Side smin = branch->mSplitPlane->getSide(aabb.getMinimum());
846	Plane::Side smax = branch->mSplitPlane->getSide(aabb.getMaximum());
847	if (smin == smax)
848	{
849	if (smax == Plane::NEGATIVE_SIDE \|\|
850	(smax == Plane::NO_SIDE && branch->mPlaneSide == BihPlaneEvent::PES_LEFT))
851	{
852	if (branch->mLeft)
853	recInsert(branch->mLeft, rend);
854	else
855	recInsertNew(branch, BihPlaneEvent::PES_LEFT, rend);
856	}
857	else if (smin == Plane::POSITIVE_SIDE \|\|
858	(smin == Plane::NO_SIDE && branch->mPlaneSide == BihPlaneEvent::PES_RIGHT))
859	{
860	if (branch->mRight)
861	recInsert(branch->mRight, rend);
862	else
863	recInsertNew(branch, BihPlaneEvent::PES_RIGHT, rend);
864	}
865	}
866	else
867	{
868	if (smin == Plane::NEGATIVE_SIDE && smax == Plane::NO_SIDE)
869	{
870	if (branch->mLeft)
871	recInsert(branch->mLeft, rend);
872	else
873	recInsertNew(branch, BihPlaneEvent::PES_LEFT, rend);
874	}
875	else if (smax == Plane::POSITIVE_SIDE && smin == Plane::NO_SIDE)
876	{
877	if (branch->mRight)
878	recInsert(branch->mRight, rend);
879	else
880	recInsertNew(branch, BihPlaneEvent::PES_RIGHT, rend);
881	}
882	else
883	{
884	// to avoid SNAFUs, rebuild whole subtree
885	//LogManager::getSingleton().logMessage("## Rebuilding subtree for insertion");
886	rebuildSubtree(node, rend);
887	}
888	}
889	}
890	}
891
892	void BiHierarchy::recInsertNew(BiHierarchy::Branch * parent, BihPlaneEvent::Side side, BihRenderable * rend)
893	{
894	//LogManager::getSingleton().logMessage("## Inserting into new subtree");
895
896	AxisAlignedBox left, rigth, aabb;
897	BihPlaneEventList events;
898	int nObjects;
899
900	rend->computeScene(events, aabb, nObjects, false);
901
902	// override aabb
903	splitBox(*parent, left, rigth);
904	if (side == BihPlaneEvent::PES_LEFT)
905	{
906	aabb = left;
907	if (mBuildMethod == BIHBM_RECURSIVE)
908	parent->mLeft = recBuild(events, nObjects, aabb, parent);
909	else if (mBuildMethod == BIHBM_PRIORITYQUEUE)
910	parent->mLeft = pqBuild(events, nObjects, aabb, parent);
911	else
912	{
913	OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
914	"Invalid build method for the BiHierarchy.",
915	"BiHierarchy::buildFromList");
916	parent->mLeft = 0;
917	}
918
919	}
920	else if (side == BihPlaneEvent::PES_RIGHT)
921	{
922	aabb = rigth;
923	if (mBuildMethod == BIHBM_RECURSIVE)
924	parent->mRight = recBuild(events, nObjects, aabb, parent);
925	else if (mBuildMethod == BIHBM_PRIORITYQUEUE)
926	parent->mRight = pqBuild(events, nObjects, aabb, parent);
927	else
928	{
929	OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
930	"Invalid build method for the BiHierarchy.",
931	"BiHierarchy::buildFromList");
932	parent->mRight = 0;
933	}
934	}
935	}
936
937	void BiHierarchy::rebuildSubtree(BiHierarchy::Node * node, BihRenderable * rend)
938	{
939	//LogManager::getSingleton().logMessage("## Rebuilding subtree");
940
941	AxisAlignedBox aabb = node->mAABB;
942
943	BihRenderableList nodelist;
944	nodelist.push_back(rend);
945	addRendToList(node, nodelist);
946
947	if (node == mBihRoot)
948	{
949	OGRE_DELETE(mBihRoot);
950	mBihRoot = buildFromList(nodelist, 0, aabb);
951	}
952	else
953	{
954	BiHierarchy::Branch * parent = BIHBRANCHPTR_CAST(node->getParent());
955
956	if (node == parent->mLeft)
957	{
958	OGRE_DELETE(parent->mLeft);
959	parent->mLeft = buildFromList(nodelist, parent, aabb);
960	}
961	else if (node == parent->mRight)
962	{
963	OGRE_DELETE(parent->mRight);
964	parent->mRight = buildFromList(nodelist, parent, aabb);
965	}
966	else
967	{
968	OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
969	"SNAFU while inserting BihRenderable into BiHierarchy.",
970	"BiHierarchy::recInsert" );
971	}
972	}
973	}
974
975	// compute both AABB then return the requested one.
976	void BiHierarchy::splitBox(const BiHierarchy::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right)
977	{
978	Vector3 bmin = parent.mAABB.getMinimum();
979	Vector3 bmax = parent.mAABB.getMaximum();
980	Real pos = - parent.mSplitPlane->d;
981	int dim = static_cast<int>(parent.mSplitPlane->normal.dotProduct(Vector3(0,1,2)));
982	// set corners which are the same as parent AABB
983	left.setMinimum(bmin);
984	right.setMaximum(bmax);
985	// modify "inner" corners
986	bmin[dim] = pos;
987	bmax[dim] = pos;
988	// set the corners on the split plane
989	left.setMaximum(bmax);
990	right.setMinimum(bmin);
991	}
992
993	void BiHierarchy::addRendToList(BiHierarchy::Node * node, BihRenderableList& nodelist)
994	{
995	if (node->isLeaf())
996	{
997	BiHierarchy::Leaf * leaf = BIHLEAFPTR_CAST(node);
998	BihRenderableList::iterator it = leaf->mBihRenderables.begin();
999	BihRenderableList::iterator end = leaf->mBihRenderables.end();
1000	while (it != end)
1001	{
1002	nodelist.push_back(*it);
1003	it++;
1004	}
1005	}
1006	else
1007	{
1008	BiHierarchy::Branch * branch = BIHBRANCHPTR_CAST(node);
1009	if (branch->mLeft)
1010	addRendToList(branch->mLeft, nodelist);
1011	if (branch->mRight)
1012	addRendToList(branch->mRight, nodelist);
1013	}
1014	}
1015
1016	/************************************************************************/
1017	/* BiHierarchy build functions */
1018	/************************************************************************/
1019
1020	void BiHierarchy::build(BihRenderable * sceneRoot)
1021	{
1022	Timer *timer = Root::getSingleton().getTimer();
1023	unsigned long t1, t2, t3, t4;
1024
1025	mTreeStats.clear();
1026
1027	// data we want to collect
1028	BihPlaneEventList events;
1029	AxisAlignedBox aabb;
1030	int nObjects = 0;
1031
1032	t1 = timer->getMicroseconds(); // DEBUG
1033	sceneRoot->computeScene(events, aabb, nObjects);
1034	t2 = timer->getMicroseconds(); // DEBUG
1035	events.sort();
1036	t3 = timer->getMicroseconds(); // DEBUG
1037
1038	mTreeStats.mNumSceneNodes = nObjects;
1039
1040	assert(! aabb.isNull() && "Teh stubid worldAABB iz NULL ... waht now?");
1041	// hack to avoid SNAFU with "2-dimensional" scene
1042	aabb.merge(aabb.getMaximum()+Vector3(1,1,1));
1043	aabb.merge(aabb.getMinimum()+Vector3(-1,-1,-1));
1044
1045	if (mBuildMethod == BIHBM_RECURSIVE)
1046	mBihRoot = recBuild(events, nObjects, aabb, 0);
1047	else if (mBuildMethod == BIHBM_PRIORITYQUEUE)
1048	mBihRoot = pqBuild(events, nObjects, aabb, 0);
1049	else
1050	{
1051	OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
1052	"Invalid build method for the BiHierarchy.",
1053	"BiHierarchy::build");
1054	mBihRoot = 0;
1055	}
1056
1057	t4 = timer->getMicroseconds(); // DEBUG
1058
1059	String method = "Invalid";
1060	if (mBuildMethod == BIHBM_RECURSIVE)
1061	method = "Recursive";
1062	else if (mBuildMethod == BIHBM_PRIORITYQUEUE)
1063	method = "Priority Queue";
1064
1065	mBuildLog->logMessage("######## SAH Statistics ########");
1066	mBuildLog->logMessage("Build Method: " + method);
1067	mBuildLog->logMessage("Time for events build: " + StringConverter::toString(t2 - t1) + "µs");
1068	mBuildLog->logMessage("Time for events sort: " + StringConverter::toString(t3 - t2) + "µs");
1069	mBuildLog->logMessage("Time for tree build: " + StringConverter::toString(t4 - t3) + "µs");
1070	mBuildLog->logMessage("Total time: " + StringConverter::toString(t4 - t1) + "µs");
1071	mBuildLog->logMessage("Tree Depth: " + StringConverter::toString(mMaxDepth));
1072	mBuildLog->logMessage("Number of Objects: " + StringConverter::toString(mTreeStats.mNumSceneNodes));
1073	mBuildLog->logMessage("Number of Leaves: " + StringConverter::toString(mTreeStats.mNumLeaves));
1074	mBuildLog->logMessage("Number of Nodes: " + StringConverter::toString(mTreeStats.mNumNodes));
1075	mBuildLog->logMessage("Total cost: " + StringConverter::toString(calcCost()));
1076	mBuildLog->logMessage("################################");
1077	}
1078
1079	BiHierarchy::Node * BiHierarchy::buildFromList(BihRenderableList& nodelist, BiHierarchy::Branch * parent, AxisAlignedBox& aabb)
1080	{
1081	// data we want to collect
1082	BihPlaneEventList events;
1083	AxisAlignedBox nodeaabb;
1084	int nObjects = 0;
1085
1086	BihRenderableList::iterator it = nodelist.begin();
1087	BihRenderableList::iterator end = nodelist.end();
1088	while (it != end)
1089	{
1090	(*it)->computeScene(events, nodeaabb, nObjects, false);
1091	it++;
1092	}
1093
1094	events.sort();
1095
1096	// HACK
1097	if (aabb.isNull())
1098	{
1099	aabb = nodeaabb;
1100	}
1101
1102	if (mBuildMethod == BIHBM_RECURSIVE)
1103	return recBuild(events, nObjects, aabb, parent);
1104	else if (mBuildMethod == BIHBM_PRIORITYQUEUE)
1105	return pqBuild(events, nObjects, aabb, parent);
1106	else
1107	{
1108	OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
1109	"Invalid build method for the BiHierarchy.",
1110	"BiHierarchy::buildFromList");
1111	return 0;
1112	}
1113	}
1114
1115	BiHierarchy::Node * BiHierarchy::recBuild(BihPlaneEventList& events, int nObjects, AxisAlignedBox& aabb, BiHierarchy::Branch * parent)
1116	{
1117	// determine the depth we are on
1118	int level = 0;
1119	if (parent)
1120	{
1121	level = parent->getLevel() + 1;
1122	}
1123
1124	/************************************************/
1125	/************** BEGIN FINDPLANE *************/
1126	/************************************************/
1127	// find optimal split plane and split node accordingly
1128
1129	// initialize
1130	const int dim = 3;
1131	int pStart, pOn, pEnd;
1132	int nLeft[dim], nPlane[dim], nRight[dim];
1133	int nObjectCount[dim];
1134	float LeftOffset[dim],RightOffset[dim];
1135	for (int i = 0; i < dim; i++)
1136	{
1137	nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
1138	nObjectCount[i]=0;
1139	}
1140
1141	BihSplitInfo split, best;
1142	best.cost = Math::POS_INFINITY;
1143
1144	BihPlaneEventList::iterator begin = events.begin();
1145	BihPlaneEventList::iterator end = events.end();
1146	BihPlaneEventList::iterator it = begin;
1147
1148	BihPlaneEventList::iterator it_a = begin; // iterator for adjusting the bounding box
1149
1150	AxisAlignedBox minLefts[dim];
1151	AxisAlignedBox minRights[dim];
1152
1153	AxisAlignedBox minLeft;
1154	AxisAlignedBox minRight;
1155
1156
1157	// try all planes to find the best one for the given set of objects
1158
1159	// Use SAH method
1160	if (mAlgorithm==BIHAL_SAH)
1161	{
1162	while (it != end)
1163	{
1164	BihPlaneEventList::iterator p = it;
1165	pStart = pOn = pEnd = 0;
1166
1167	while (it != end && p->equalsType(*it, BihPlaneEvent::PET_END))
1168	{
1169	it++; pEnd++;
1170	}
1171	while (it != end && p->equalsType(*it, BihPlaneEvent::PET_ON))
1172	{
1173	it++; pOn++;
1174	}
1175	while (it != end && p->equalsType(*it, BihPlaneEvent::PET_START))
1176	{
1177	it++; pStart++;
1178	}
1179
1180
1181	int d = p->getDimension();
1182	nPlane[d] = pOn;
1183	//nRight[d] -= pOn; nRight[d] -= pEnd;
1184
1185	// find the corrected offsets for the left and right bounding box
1186	it_a = begin;
1187	LeftOffset[d]=0;
1188	RightOffset[d]=0;
1189	minLefts[d].setNull();
1190	minRights[d].setNull();
1191	nRight[d]=0;
1192	nLeft[d]=0;
1193
1194
1195	while (it_a != end)
1196	{
1197	if (it_a->getDimension()==d)
1198	{
1199	it_a->getRenderable()->setSide(BihPlaneEvent::PES_BOTH);
1200	it_a->getRenderable()->setClassified(false);
1201	it_a->classify(*p, split.side,true);
1202	if (it_a->getRenderable()->getSide() == BihPlaneEvent::PES_RIGHT)
1203	{
1204	if (!it_a->getRenderable()->isClassified())
1205	{
1206	it_a->getRenderable()->setClassified(true);
1207	nRight[d]++;
1208	}
1209	minRights[d].merge(it_a->getRenderable()->getBoundingBox());
1210
1211	}
1212	// left-only nodes go in left list
1213	else if (it_a->getRenderable()->getSide() == BihPlaneEvent::PES_LEFT)
1214	{
1215	if (!it_a->getRenderable()->isClassified())
1216	{
1217	it_a->getRenderable()->setClassified(true);
1218	nLeft[d]++;
1219	}
1220	minLefts[d].merge(it_a->getRenderable()->getBoundingBox());
1221
1222	}
1223	}
1224
1225
1226	it_a++;
1227	}
1228
1229
1230	p->SAH(aabb, nLeft[d], nPlane[d], nRight[d], split,minLefts[d],minRights[d]);
1231	mBuildLog->logMessage("SAH " + StringConverter::toString(best.cost)+ " " + StringConverter::toString(split.cost) +
1232	"dim: " + StringConverter::toString(d));
1233	if (split.cost < best.cost)
1234	{
1235	best = split;
1236	}
1237
1238
1239	//nLeft[d] += pStart; nLeft[d] += pOn;
1240
1241	nPlane[d] = 0;
1242	}
1243	} else
1244	{
1245
1246	int d;
1247	while (it != end)
1248	{
1249	BihPlaneEventList::iterator p = it;
1250	d = p->getDimension();
1251	//if ((p->equalsType(it, BihPlaneEvent::PET_START)) \|\| (p->equalsType(it, BihPlaneEvent::PET_ON)))
1252	nObjectCount[d]++;
1253	it++;
1254	}
1255
1256	int MaxDimension=1;
1257	for (int i = 1; i < dim; i++)
1258	{
1259	if (nObjectCount[i]>nObjectCount[i-1]) MaxDimension=i;
1260	}
1261	it = begin;
1262
1263	nObjectCount[MaxDimension]/=2;
1264	while ((it != end) && (nObjectCount[MaxDimension]))
1265	{
1266	BihPlaneEventList::iterator p = it;
1267	if (p->getDimension()== MaxDimension)
1268	{
1269	nObjectCount[MaxDimension]--;
1270	best.event=*it;
1271	best.cost=0;
1272
1273	}
1274	it++;
1275	}
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285	}
1286
1287
1288	/************************************************/
1289	/************** BEGIN TERMINATE *************/
1290	/************************************************/
1291	// check terminating condition
1292	if (/best.cost > BihPlaneEvent::KInObjects \|\|*/ level >= mMaxDepth \|\| nObjects<20 )
1293	{
1294	// Terminating condition reached, create leaf and add renderables to list
1295	mBuildLog->logMessage("Terminate " + StringConverter::toString(best.cost)+ " o:" + StringConverter::toString(nObjects) +
1296	" ki: " + StringConverter::toString(BihPlaneEvent::KI*nObjects)+ " dim: " + StringConverter::toString(best.event.getDimension()));
1297	BiHierarchy::Leaf * leaf = new BiHierarchy::Leaf(this, level, aabb, parent);
1298	if (parent->GetSide()==1) leaf->SetToLeft(); else leaf->SetToRight();
1299
1300
1301	BihRenderable *rend;
1302	it = begin;
1303	while (it != end)
1304	{
1305	rend = it->getRenderable();
1306	rend->setClassified(false);
1307	if (rend->attachTo(leaf, this))
1308	{
1309	leaf->insert(rend);
1310	}
1311	it++;
1312	}
1313	// update stats
1314	++ mTreeStats.mNumNodes;
1315	++ mTreeStats.mNumLeaves;
1316	// update bounding box
1317	leaf->_updateBounds(false);
1318	return leaf;
1319	}
1320
1321	/************************************************/
1322	/************** BEGIN CLASSIFY **************/
1323	/************************************************/
1324	// split the event list in left and right sub-lists
1325	else
1326	{
1327	BihPlaneEventList eventsRight, eventsLeft;
1328	it = begin;
1329	// slightly redundant, since we mark each renderable up to 6 times
1330	while (it != end)
1331	{
1332	it->getRenderable()->setSide(BihPlaneEvent::PES_BOTH);
1333	it->getRenderable()->setClassified(false);
1334	it++;
1335	}
1336	// now classify all renderables. do they belong to the left child, the right child or both?
1337	it = begin;
1338	while (it != end)
1339	{
1340	it->classify(best.event, best.side,true);
1341	it++;
1342	}
1343	// divide the event lists
1344	int nLeftS = 0, nRightS = 0, nBothS = 0;
1345	it = begin;
1346
1347	minLeft.setNull();
1348	minRight.setNull();
1349
1350
1351
1352	while (it != end)
1353	{
1354	// right-only nodes go in right list
1355	if (it->getRenderable()->getSide() == BihPlaneEvent::PES_RIGHT)
1356	{
1357	if (!it->getRenderable()->isClassified())
1358	{
1359	it->getRenderable()->setClassified(true);
1360	nRightS++;
1361	}
1362	minRight.merge(it->getRenderable()->getBoundingBox());
1363	//mBuildLog->logMessage("merge right " + StringConverter::toString(minRight.volume()));
1364	eventsRight.push_back(*it);
1365	}
1366	// left-only nodes go in left list
1367	else if (it->getRenderable()->getSide() == BihPlaneEvent::PES_LEFT)
1368	{
1369	if (!it->getRenderable()->isClassified())
1370	{
1371	it->getRenderable()->setClassified(true);
1372	nLeftS++;
1373	}
1374	minLeft.merge(it->getRenderable()->getBoundingBox());
1375	//mBuildLog->logMessage("merge left " + StringConverter::toString(minLeft.volume()));
1376	eventsLeft.push_back(*it);
1377	}
1378	// remaining nodes go in both lists, bust must be clipped to prevent
1379	// events from lying outside the new nodes aabb
1380	else
1381	{
1382	if (!it->getRenderable()->isClassified())
1383	{
1384	it->getRenderable()->setClassified(true);
1385	nBothS++;
1386	}
1387
1388	// calculate the intersecting box for the right side
1389
1390
1391	minRight.merge(best.bright.intersection(it->getRenderable()->getBoundingBox()));
1392
1393
1394	//mBuildLog->logMessage("merge Right Overlap " + StringConverter::toString(minRight.volume()));
1395	eventsRight.push_back(it->clip(best.bright, best.event.getDimension()));
1396
1397	minLeft.merge(best.bleft.intersection(it->getRenderable()->getBoundingBox()));
1398
1399	//mBuildLog->logMessage("merge Left Overlap " + StringConverter::toString(minLeft.volume()));
1400	eventsLeft.push_back(it->clip(best.bleft, best.event.getDimension()));
1401	}
1402	it++;
1403	}
1404
1405	mBuildLog->logMessage("Split R:" + StringConverter::toString(nRightS)+ " L:" + StringConverter::toString(nLeftS) +
1406	" O: " + StringConverter::toString(nObjects));
1407
1408
1409	// calculate minimum of the left bounding box
1410	/*
1411	AxisAlignedBox minimum;
1412	minimum.setNull();
1413	it=eventsLeft.begin();
1414	while (it!=eventsLeft.end())
1415	{
1416	minimum.merge(it->getRenderable()->getBoundingBox());
1417	it++;
1418	}
1419	*/
1420
1421
1422
1423	// create a new branch node and continue recursion
1424	BiHierarchy::Branch * branch = new BiHierarchy::Branch(this, level, aabb, parent,
1425	best.event.getSplitPlane(), best.side);
1426
1427	// now create the child nodes and continue recursion
1428	/*
1429	if (best.bleft.volume()>minLeft.volume())
1430	{
1431	mBuildLog->logMessage("Volume Smaller Left " + StringConverter::toString(minLeft.volume()) + " " + StringConverter::toString(best.bleft.volume(),3,3));
1432	}
1433
1434	if (best.bright.volume()>minRight.volume())
1435	{
1436	mBuildLog->logMessage("Volume Smaller Right " + StringConverter::toString(minRight.volume()) + " " + StringConverter::toString(best.bright.volume(),3,3));
1437	}
1438	*/
1439
1440	if (eventsLeft.size() > 0)
1441	{
1442
1443	branch->mLeft = recBuild(eventsLeft, nLeftS + nBothS, /best.bleft/minLeft, branch);
1444	branch->mLeft->SetToLeft();
1445	mBuildLog->logMessage("SetToLeft");
1446	//branch->mLeft = recBuild(eventsLeft, nLeftS + nBothS, best.bleft, branch);
1447	}
1448	if (eventsRight.size() > 0)
1449	{
1450
1451	branch->mRight = recBuild(eventsRight, nBothS + nRightS, /best.bright/ minRight, branch);
1452	branch->mRight->SetToRight();
1453	mBuildLog->logMessage("SetToRight");
1454
1455
1456	//branch->mRight = recBuild(eventsRight, nBothS + nRightS, best.bright, branch);
1457	}
1458
1459	// update stats
1460	++ mTreeStats.mNumNodes;
1461
1462	// update bounding box
1463	branch->_updateBounds(false);
1464
1465	return branch;
1466	}
1467	}
1468
1469	BiHierarchy::Node * BiHierarchy::pqBuild(BihPlaneEventList& events,
1470	int nObjects, AxisAlignedBox& aabb,
1471	BiHierarchy::Branch * parent)
1472	{
1473	SplitCandidatePQ pqueue;
1474	Real globalTreeCost;
1475	Real globalSA;
1476
1477	BiHierarchy::Node * newNode = 0, * topNode = 0;
1478	// init global tree cost
1479	globalTreeCost = BihPlaneEvent::KI * nObjects;
1480	globalSA = BihPlaneEvent::surfaceArea(aabb);
1481
1482	BihPlaneEventList * e = new BihPlaneEventList(events);
1483
1484	// inital split candidate
1485	BihSplitInfo * best = pqFindPlane(e, nObjects, aabb, globalSA);
1486	BihSubdivisionCandidate splitcandidate(e, nObjects, aabb, parent, globalTreeCost,
1487	globalTreeCost - best->cost, best, BihPlaneEvent::PES_BOTH);
1488	pqueue.push(splitcandidate);
1489
1490
1491	/* BEGIN ITERATIVE BUILD */
1492	while (!pqueue.empty())
1493	{
1494	BihSubdivisionCandidate sc = pqueue.top();
1495	pqueue.pop();
1496
1497	// determine the depth we are on
1498	int level = 0;
1499	if (sc.parent)
1500	{
1501	level = sc.parent->getLevel() + 1;
1502	}
1503
1504	/************************************************/
1505	/************** BEGIN TERMINATE *************/
1506	/************************************************/
1507	// check terminating condition
1508	if (sc.decrease < 0.0 \|\| level >= mMaxDepth)
1509	{
1510	// Terminating condition reached, create leaf and add renderables to list
1511	BiHierarchy::Leaf * leaf = new BiHierarchy::Leaf(this, level, sc.aabb, sc.parent);
1512	BihRenderable *rend;
1513	BihPlaneEventList::iterator begin = sc.events->begin();
1514	BihPlaneEventList::iterator end = sc.events->end();
1515	BihPlaneEventList::iterator it = begin;
1516	while (it != end)
1517	{
1518	rend = it->getRenderable();
1519	rend->setClassified(false);
1520	if (rend->attachTo(leaf, this))
1521	{
1522	leaf->insert(rend);
1523	}
1524	it++;
1525	}
1526	newNode = leaf;
1527	if (!topNode)
1528	topNode = leaf;
1529	// update stats
1530	++ mTreeStats.mNumNodes;
1531	++ mTreeStats.mNumLeaves;
1532	}
1533
1534	/************************************************/
1535	/************** BEGIN CLASSIFY **************/
1536	/************************************************/
1537	else
1538	{
1539	BihPlaneEventList * eventsLeft = new BihPlaneEventList();
1540	BihPlaneEventList * eventsRight = new BihPlaneEventList();
1541	BihPlaneEventList::iterator begin = sc.events->begin();
1542	BihPlaneEventList::iterator end = sc.events->end();
1543	BihPlaneEventList::iterator it = begin;
1544	// slightly redundant, since we mark each renderable up to 6 times
1545	while (it != end)
1546	{
1547	it->getRenderable()->setSide(BihPlaneEvent::PES_BOTH);
1548	it->getRenderable()->setClassified(false);
1549	it++;
1550	}
1551
1552	// now classify all renderables. do they belong to the left child, the right child or both?
1553	it = begin;
1554	while (it != end)
1555	{
1556	it->classify(sc.best->event, sc.best->side,false);
1557	it++;
1558	}
1559
1560	// divide the event lists
1561	int nLeftS = 0, nRightS = 0, nBothS = 0;
1562	it = begin;
1563	while (it != end)
1564	{
1565	// right-only events go in the right list
1566	if (it->getRenderable()->getSide() == BihPlaneEvent::PES_RIGHT)
1567	{
1568	if (!it->getRenderable()->isClassified())
1569	{
1570	it->getRenderable()->setClassified(true);
1571	nRightS++;
1572	}
1573
1574	eventsRight->push_back(*it);
1575	}
1576	// left-only events go in the left list
1577	else if (it->getRenderable()->getSide() == BihPlaneEvent::PES_LEFT)
1578	{
1579	if (!it->getRenderable()->isClassified())
1580	{
1581	it->getRenderable()->setClassified(true);
1582	nLeftS++;
1583	}
1584	eventsLeft->push_back(*it);
1585	}
1586	// the rest goes in both lists after being clipped
1587	else
1588	{
1589	if (!it->getRenderable()->isClassified())
1590	{
1591	it->getRenderable()->setClassified(true);
1592	nBothS++;
1593	}
1594
1595	eventsRight->push_back(it->clip(sc.best->bright, sc.best->event.getDimension()));
1596	eventsLeft->push_back(it->clip(sc.best->bleft, sc.best->event.getDimension()));
1597	}
1598	it++;
1599	}
1600
1601	// create a new branch node
1602	BiHierarchy::Branch * branch = new BiHierarchy::Branch(this, level, sc.aabb, sc.parent,
1603	sc.best->event.getSplitPlane(), sc.best->side);
1604
1605	globalTreeCost -= sc.decrease;
1606
1607
1608	// now for each potential child node, compute the split plane and the cost decrease
1609	// and place them in the queue
1610	if (eventsLeft->size() > 0)
1611	{
1612	best = pqFindPlane(eventsLeft, nLeftS + nBothS, sc.best->bleft, globalSA);
1613	Real old = BihPlaneEvent::surfaceArea(sc.best->bleft)/globalSABihPlaneEvent::KI(nLeftS + nBothS);
1614	BihSubdivisionCandidate scleft(eventsLeft, nLeftS + nBothS, sc.best->bleft,
1615	branch, old, old - best->cost, best, BihPlaneEvent::PES_LEFT);
1616	pqueue.push(scleft);
1617	}
1618	// cleanup
1619	else
1620	{
1621	delete eventsLeft;
1622	}
1623
1624	if (eventsRight->size() > 0)
1625	{
1626	best = pqFindPlane(eventsRight, nBothS + nRightS, sc.best->bright, globalSA);
1627	Real old = BihPlaneEvent::surfaceArea(sc.best->bright)/globalSABihPlaneEvent::KI(nBothS + nRightS);
1628	BihSubdivisionCandidate scright(eventsRight, nBothS + nRightS, sc.best->bright,
1629	branch, old, old - best->cost, best, BihPlaneEvent::PES_RIGHT);
1630	pqueue.push(scright);
1631	}
1632	// cleanup
1633	else
1634	{
1635	delete eventsRight;
1636	}
1637
1638	newNode = branch;
1639	if (!topNode)
1640	topNode = branch;
1641
1642
1643	// update stats
1644	++ mTreeStats.mNumNodes;
1645	}
1646
1647	// attach new node to parent
1648	if (sc.parent)
1649	{
1650	if (sc.side == BihPlaneEvent::PES_LEFT)
1651	{
1652	sc.parent->mLeft = newNode;
1653	}
1654	else if (sc.side == BihPlaneEvent::PES_RIGHT)
1655	{
1656	sc.parent->mRight = newNode;
1657	}
1658	else
1659	{
1660	OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
1661	"PQBUILD SNAFU - CHILD I AM NOT LEFT NOR RIGHT","BiHierarchy::pqBuild");
1662	}
1663	}
1664
1665	// update bounding boxes when geometry (leaf) was added
1666	if (newNode->isLeaf())
1667	newNode->_updateBounds();
1668
1669	//cleanup
1670	OGRE_DELETE(sc.events);
1671	OGRE_DELETE(sc.best);
1672	}
1673	mBuildLog->logMessage("Cost after PQBUILD " + StringConverter::toString(globalTreeCost));
1674	return topNode;
1675	}
1676
1677	//-------------------------------------------------------------------------
1678	BihSplitInfo * BiHierarchy::pqFindPlane(BihPlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA)
1679	{
1680	static const int dim = 3;
1681	int pStart, pOn, pEnd;
1682	int nLeft[dim], nPlane[dim], nRight[dim];
1683	for (int i = 0; i < dim; i++)
1684	{
1685	nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
1686	}
1687
1688	BihSplitInfo split, best;
1689	best.cost = Math::POS_INFINITY;
1690
1691	Real parentSA = BihPlaneEvent::surfaceArea(aabb);
1692
1693	BihPlaneEventList::iterator begin = events->begin();
1694	BihPlaneEventList::iterator end = events->end();
1695	BihPlaneEventList::iterator it = begin;
1696	// try all planes to find the best one for the given set of objects
1697	while (it != end)
1698	{
1699	BihPlaneEventList::iterator p = it;
1700	pStart = pOn = pEnd = 0;
1701	while (it != end && p->equalsType(*it, BihPlaneEvent::PET_END))
1702	{
1703	it++; pEnd++;
1704	}
1705	while (it != end && p->equalsType(*it, BihPlaneEvent::PET_ON))
1706	{
1707	it++; pOn++;
1708	}
1709	while (it != end && p->equalsType(*it, BihPlaneEvent::PET_START))
1710	{
1711	it++; pStart++;
1712	}
1713	int d = p->getDimension();
1714	nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
1715	p->pqSAH(globalSA, parentSA, nLeft[d], nPlane[d], nRight[d], aabb, split);
1716	if (split.cost < best.cost)
1717	{
1718	best = split;
1719	}
1720	nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
1721	}
1722	return new BihSplitInfo(best);
1723	}
1724
1725
1726
1727	/************************************************************************/
1728	/* BiHierarchy rendering functions */
1729	/************************************************************************/
1730
1731
1732	//-------------------------------------------------------------------------
1733	void BiHierarchy::queueVisibleObjects(BiHierarchyCamera* cam, RenderQueue* queue, bool onlyShadowCasters,
1734	bool showBoxes, BiHierarchy::NodeList& visibleNodes)
1735	{
1736	mFrameStats.clear();
1737	cam->mNumVisQueries = 0;
1738
1739	if (mBihRoot)
1740	recQueueVisibleObjects(mBihRoot, Root::getSingleton().getCurrentFrameNumber(),
1741	cam, queue, onlyShadowCasters, showBoxes, visibleNodes);
1742
1743	mFrameStats.mTraversedNodes = cam->mNumVisQueries;
1744	}
1745
1746	//-------------------------------------------------------------------------
1747	void BiHierarchy::recQueueVisibleObjects(BiHierarchy::Node * node, unsigned long currentFrame,
1748	BiHierarchyCamera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes,
1749	BiHierarchy::NodeList& visibleNodes, bool fullVis)
1750	{
1751	BiHierarchyCamera::NodeVisibility vis = BiHierarchyCamera::BIHNV_PART;
1752	// test visibility
1753	//if (cam->isVisible(node->mAABB))
1754	if (fullVis \|\|
1755	((vis = (cam->*getVisibility)(node->mAABB)) != BiHierarchyCamera::BIHNV_NONE))
1756	{
1757	visibleNodes.push_back(node);
1758
1759	bool v = (fullVis \|\| vis == BiHierarchyCamera::BIHNV_FULL);
1760
1761	node->queueVisibleObjects(currentFrame, cam, queue, onlyShadowCasters, showBoxes, v);
1762
1763	if (v \|\| node->isLeaf())
1764	++ mFrameStats.mRenderedNodes;
1765
1766	if (!v)
1767	{
1768
1769	if (node->getLeftChild())
1770	recQueueVisibleObjects(node->getLeftChild(), currentFrame,
1771	cam, queue, onlyShadowCasters, showBoxes, visibleNodes, v);
1772	if (node->getRightChild())
1773	recQueueVisibleObjects(node->getRightChild(), currentFrame,
1774	cam, queue, onlyShadowCasters, showBoxes, visibleNodes, v);
1775	}
1776	}
1777	else
1778	{
1779	++ mFrameStats.mFrustumCulledNodes;
1780	}
1781	}
1782
1783	//-------------------------------------------------------------------------
1784	void BiHierarchy::setEnhancedVis(bool enh)
1785	{
1786	if (enh)
1787	getVisibility = &BiHierarchyCamera::getVisibilityEnhanced;
1788	else
1789	getVisibility = &BiHierarchyCamera::getVisibilitySimple;
1790	}
1791
1792	//-------------------------------------------------------------------------
1793	bool BiHierarchy::getEnhancedVis()
1794	{
1795	return getVisibility == &BiHierarchyCamera::getVisibilityEnhanced;
1796	}
1797
1798	//-------------------------------------------------------------------------
1799	//void BiHierarchy::findVisibleNodes(NodeList& visibleNodes, Camera * cam)
1800	//{
1801	// if (mBihRoot)
1802	// recFindVisibleNodes(mBihRoot, visibleNodes, cam);
1803	//}
1804
1805	////-------------------------------------------------------------------------
1806	//void BiHierarchy::recFindVisibleNodes(BiHierarchy::Node * node, NodeList& visibleNodes, Camera * cam)
1807	//{
1808	// // test visibility
1809	// if (cam->isVisible(node->mAABB))
1810	// {
1811	// visibleNodes.push_back(node);
1812
1813	// if (node->getLeftChild())
1814	// recFindVisibleNodes(node->getLeftChild(), visibleNodes, cam);
1815	// if (node->getRightChild())
1816	// recFindVisibleNodes(node->getRightChild(), visibleNodes, cam);
1817	// }
1818	//}
1819
1820	void BiHierarchy::findNodesIn(const AxisAlignedBox &box, std::list<SceneNode > &list, SceneNode exclude)
1821	{
1822	if (mBihRoot)
1823	recFindNodesIn(box, list, exclude, mBihRoot);
1824	}
1825
1826	void BiHierarchy::findNodesIn(const Sphere &sphere, std::list<SceneNode > &list, SceneNode exclude)
1827	{
1828	if (mBihRoot)
1829	recFindNodesIn(sphere, list, exclude, mBihRoot);
1830	}
1831
1832	void BiHierarchy::findNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode > &list, SceneNode exclude)
1833	{
1834	if (mBihRoot)
1835	recFindNodesIn(volume, list, exclude, mBihRoot);
1836	}
1837
1838	void BiHierarchy::findNodesIn(const Ray &ray, std::list<SceneNode > &list, SceneNode exclude)
1839	{
1840	if (mBihRoot)
1841	recFindNodesIn(ray, list, exclude, mBihRoot);
1842	}
1843
1844	void BiHierarchy::recFindNodesIn(const AxisAlignedBox &box, std::list<SceneNode > &list, SceneNode exclude, Node * node, bool full)
1845	{
1846	// check intersection
1847	if ( !full )
1848	{
1849	BihIntersection isect = intersect(box, node->_getWorldAABB());
1850
1851	if ( isect == OUTSIDE )
1852	return ;
1853
1854	full = ( isect == INSIDE );
1855	}
1856
1857	if (node->isLeaf())
1858	{
1859	LeafPtr leaf = BIHLEAFPTR_CAST(node);
1860	for (BihRenderableList::iterator it = leaf->mBihRenderables.begin();
1861	it != leaf->mBihRenderables.end(); it ++)
1862	{
1863	SceneNode sn = static_cast<BiHierarchySceneNode >(*it);
1864
1865	if (sn != exclude)
1866	{
1867	if (full)
1868	{
1869	list.push_back(sn);
1870	}
1871	else
1872	{
1873	BihIntersection nsect = intersect(box, sn->_getWorldAABB());
1874
1875	if ( nsect != OUTSIDE )
1876	{
1877	list.push_back(sn);
1878	}
1879	}
1880	}
1881	}
1882	}
1883	else
1884	{
1885	if (node->getLeftChild())
1886	recFindNodesIn(box, list, exclude, node->getLeftChild(), full);
1887	if (node->getRightChild())
1888	recFindNodesIn(box, list, exclude, node->getRightChild(), full);
1889	}
1890	}
1891
1892
1893	void BiHierarchy::recFindNodesIn(const Sphere &sphere, std::list<SceneNode > &list, SceneNode exclude, Node * node, bool full)
1894	{
1895	// TODO
1896	}
1897
1898
1899	void BiHierarchy::recFindNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode > &list, SceneNode exclude, Node * node, bool full)
1900	{
1901	// TODO
1902	}
1903
1904
1905	void BiHierarchy::recFindNodesIn(const Ray &ray, std::list<SceneNode > &list, SceneNode exclude, Node * node, bool full)
1906	{
1907	// TODO
1908	}
1909
1910
1911	/************************************************************************/
1912	/* BiHierarchy debug & helper functions */
1913	/************************************************************************/
1914
1915	//-------------------------------------------------------------------------
1916	void BiHierarchy::dump()
1917	{
1918	//LogManager::getSingleton().logMessage("#@#@#@#@ Dumping BiHierarchy #@#@#@#@");
1919	mBuildLog->logMessage("#@#@#@#@ Dumping BiHierarchy #@#@#@#@");
1920	if (mBihRoot)
1921	dump(mBihRoot);
1922	}
1923
1924	//-------------------------------------------------------------------------
1925	void BiHierarchy::dump(BiHierarchy::Node * node)
1926	{
1927	//LogManager * log = LogManager::getSingletonPtr();
1928	BiHierarchySceneNode * scenenode;
1929	String pad;
1930	int p;
1931
1932	pad = "";
1933	for (p = 0; p < node->getLevel(); p++)
1934	{
1935	pad += " ";
1936	}
1937
1938	if (node->isLeaf())
1939	{
1940	BiHierarchy::Leaf * leaf = BIHLEAFPTR_CAST(node);
1941	BihRenderableList::iterator it = leaf->mBihRenderables.begin();
1942	BihRenderableList::iterator end = leaf->mBihRenderables.end();
1943	while (it != end)
1944	{
1945	scenenode = static_cast<BiHierarchySceneNode >(it);
1946	mBuildLog->logMessage(pad + "# Leaf level " +
1947	StringConverter::toString(node->getLevel()) +
1948	" SceneNode " + scenenode->getName());
1949	mBuildLog->logMessage(pad + "## Objects: " + scenenode->dumpToString());
1950	it++;
1951	}
1952	}
1953	else
1954	{
1955	BiHierarchy::Branch * branch = BIHBRANCHPTR_CAST(node);
1956	if (branch->mLeft)
1957	{
1958	mBuildLog->logMessage(pad + "# Branch level " +
1959	StringConverter::toString(node->getLevel()) + " Left Child");
1960	dump(branch->mLeft);
1961	}
1962	if (branch->mRight)
1963	{
1964	mBuildLog->logMessage(pad + "# Branch level " +
1965	StringConverter::toString(node->getLevel()) + " Right Child");
1966	dump(branch->mRight);
1967	}
1968	}
1969	}
1970
1971	//-------------------------------------------------------------------------
1972	Real BiHierarchy::calcCost()
1973	{
1974	if (mBihRoot)
1975	return calcCost(mBihRoot, BihPlaneEvent::surfaceArea(mBihRoot->mAABB));
1976	else
1977	return 0;
1978	}
1979
1980	//-------------------------------------------------------------------------
1981	Real BiHierarchy::calcCost(BiHierarchy::Node * node, Real vs)
1982	{
1983	if (node == 0)
1984	return 0.0;
1985
1986	if (node->isLeaf())
1987	{
1988	BiHierarchy::Leaf * leaf = BIHLEAFPTR_CAST(node);
1989	return (BihPlaneEvent::surfaceArea(node->mAABB)/vs) *
1990	BihPlaneEvent::KI * leaf->mBihRenderables.size();
1991	}
1992	else
1993	{
1994	BiHierarchy::Branch * branch = BIHBRANCHPTR_CAST(node);
1995	return (BihPlaneEvent::surfaceArea(node->mAABB)/vs) * BihPlaneEvent::KT +
1996	calcCost(branch->mLeft, vs) + calcCost(branch->mRight, vs);
1997	}
1998	}
1999
2000	/************************************************************************/
2001	/* BiHierarchy::Node/Branch/Leaf functions */
2002	/************************************************************************/
2003
2004	//-------------------------------------------------------------------------
2005	BiHierarchy::Leaf::~Leaf()
2006	{
2007	// detach all scene nodes in the case that we are rebuilding
2008	// the tree but not the scene
2009	BihRenderableList::iterator it = mBihRenderables.begin();
2010	BihRenderableList::iterator end = mBihRenderables.end();
2011	while (it != end)
2012	{
2013	(*it)->detachFrom(this);
2014	it++;
2015	}
2016	mBihRenderables.clear();
2017	}
2018
2019	//-------------------------------------------------------------------------
2020	void BiHierarchy::Leaf::queueVisibleObjects(unsigned long currentFrame,
2021	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis)
2022	{
2023	BihRenderableList::iterator it = mBihRenderables.begin();
2024	BihRenderableList::iterator end = mBihRenderables.end();
2025	while (it != end)
2026	{
2027	if (!(*it)->isQueued(currentFrame, cam))
2028	{
2029	(*it)->queueObjects(cam, queue, onlyShadowCasters);
2030	}
2031	it++;
2032	}
2033
2034	if (showBoxes)
2035	{
2036	if (mLevel == mOwner->getHiLiteLevel()\|\| (mLevel-1) == mOwner->getHiLiteLevel() \|\| mOwner->getShowAllBoxes())
2037	queue->addRenderable(getWireBoundingBox());
2038	/*
2039	if (mLevel == mOwner->getHiLiteLevel() \|\| mOwner->getShowAllBoxes())
2040	queue->addRenderable(getWireBoundingBox());
2041	*/
2042	}
2043
2044	}
2045
2046	//-------------------------------------------------------------------------
2047	void BiHierarchy::Leaf::getGeometryList(GeometryVector *geometryList)
2048	{
2049	BihRenderableList::iterator it = mBihRenderables.begin();
2050	BihRenderableList::iterator end = mBihRenderables.end();
2051	while (it != end)
2052	{
2053	(*it)->getGeometryList(geometryList);
2054	it++;
2055	}
2056	}
2057
2058	//-------------------------------------------------------------------------
2059	// update the world aabb based on the contained geometry
2060	void BiHierarchy::Leaf::_updateBounds(bool recurse)
2061	{
2062	// reset box
2063	mWorldAABB.setNull();
2064
2065	// merge boxes from attached geometry
2066	BihRenderableList::iterator it = mBihRenderables.begin();
2067	BihRenderableList::iterator end = mBihRenderables.end();
2068	while (it != end)
2069	{
2070	//(*it)->_updateBounds();
2071	mWorldAABB.merge((*it)->getBoundingBox());
2072	it++;
2073	}
2074
2075	// update parent recursively
2076	if (recurse && mParent)
2077	mParent->_updateBounds(recurse);
2078	}
2079
2080	} // namespace Ogre

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

Download in other formats: