Context Navigation

OgreBiHierarchy.cpp @ 2390

Revision 2390, 64.8 KB checked in by vizrt_christian_seidl, 18 years ago (diff)
ADDED: Faster method for building BIH Tree BUGFIX: Termination criteria for BIH Tree works now

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]));*/ 1;
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	#undef OLD_METHOD
1118	#undef DEBUG_BUILD_TREE
1119
1120	// determine the depth we are on
1121	int level = 0;
1122	if (parent)
1123	{
1124	level = parent->getLevel() + 1;
1125	}
1126
1127	/************************************************/
1128	/************** BEGIN FINDPLANE *************/
1129	/************************************************/
1130	// find optimal split plane and split node accordingly
1131
1132	// initialize
1133	const int dim = 3;
1134	// int pStart, pOn, pEnd;
1135	int nLeft[dim], nPlane[dim], nRight[dim];
1136	int nObjectCount[dim];
1137	float LeftOffset[dim],RightOffset[dim];
1138	for (int i = 0; i < dim; i++)
1139	{
1140	nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
1141	nObjectCount[i]=0;
1142	}
1143
1144	BihSplitInfo split, best;
1145	best.cost = Math::POS_INFINITY;
1146
1147	BihPlaneEventList::iterator begin = events.begin();
1148	BihPlaneEventList::iterator end = events.end();
1149	BihPlaneEventList::iterator it = begin;
1150
1151	BihPlaneEventList::iterator it_a = begin; // iterator for adjusting the bounding box
1152
1153	// hold the minimum left and right bounding box
1154	AxisAlignedBox minLefts[dim];
1155	AxisAlignedBox minRights[dim];
1156
1157
1158
1159	Vector3 LastPosition=aabb.getMinimum(); // needed to remember the last split plane position
1160
1161	// needed for the final sort before splitting
1162	AxisAlignedBox minLeft;
1163	AxisAlignedBox minRight;
1164
1165	// the border which seperates finished and unfinished events
1166	BihPlaneEventList::iterator LeftBorder[dim];
1167
1168	for (int i=0; i<dim; i++)
1169	{
1170	minLefts[i].setNull(); // left aabb starts with null
1171	minRights[i]=aabb; // right aabb contains all objects
1172	nRight[i]=nObjects; // all objects are on the right side
1173	nLeft[i]=0;
1174	LeftBorder[i]=it; // set the left border to the first event
1175	}
1176	// try all planes to find the best one for the given set of objects
1177
1178	// Use SAH method
1179	//mBuildLog->logMessage("------------NewRun:" + StringConverter::toString(nObjects));
1180	if (mAlgorithm==BIHAL_SAH)
1181	{
1182
1183	// slow implementation. for every event the left and right bounding boxes are calculated.
1184	#ifdef OLD_METHOD
1185	it = begin;
1186
1187	while (it != end)
1188	{
1189	BihPlaneEventList::iterator p = it;
1190
1191
1192	pStart = pOn = pEnd = 0;
1193
1194	while (it != end && p->equalsType(*it, BihPlaneEvent::PET_END))
1195	{
1196	it++; pEnd++;
1197	}
1198	while (it != end && p->equalsType(*it, BihPlaneEvent::PET_ON))
1199	{
1200	it++; pOn++;
1201	}
1202	while (it != end && p->equalsType(*it, BihPlaneEvent::PET_START))
1203	{
1204	it++; pStart++;
1205	}
1206
1207
1208	int d = p->getDimension();
1209
1210	nPlane[d] = pOn;
1211	nRight[d] -= pOn; nRight[d] -= pEnd;
1212
1213
1214	// find the corrected offsets for the left and right bounding box
1215	it_a = begin;
1216	LeftOffset[d]=0;
1217	RightOffset[d]=0;
1218
1219
1220
1221
1222	nRight[d]=0;
1223	nLeft[d]=0;
1224	minLefts[d].setNull();
1225	minRights[d].setNull();
1226
1227	if (minLefts[d].isNull() && minRights[d].isNull())
1228	{
1229	while (it_a != end)
1230	{
1231	if ((it_a->getDimension()==d) && (it_a->GetType() == BihPlaneEvent::PET_START))
1232	{
1233	it_a->getRenderable()->setSide(BihPlaneEvent::PES_BOTH);
1234	it_a->getRenderable()->setClassified(false);
1235	it_a->classify(*p, split.side,true);
1236	if (it_a->getRenderable()->getSide() == BihPlaneEvent::PES_RIGHT)
1237	{
1238	if (!it_a->getRenderable()->isClassified())
1239	{
1240	it_a->getRenderable()->setClassified(true);
1241	nRight[d]++;
1242	}
1243	minRights[d].merge(it_a->getRenderable()->getBoundingBox());
1244
1245	}
1246	// left-only nodes go in left list
1247	else if (it_a->getRenderable()->getSide() == BihPlaneEvent::PES_LEFT)
1248	{
1249
1250	if (!it_a->getRenderable()->isClassified())
1251	{
1252	it_a->getRenderable()->setClassified(true);
1253	nLeft[d]++;
1254	}
1255	minLefts[d].merge(it_a->getRenderable()->getBoundingBox());
1256
1257	}
1258	}
1259
1260
1261	it_a++;
1262	}
1263	}
1264
1265
1266
1267
1268	#endif
1269
1270	///////////////////////////////////////////////////////////////////////////
1271
1272	#ifndef OLD_METHOD
1273	it = begin;
1274	while (it != end)
1275	{
1276	for (int i=0; i<dim; i++)
1277	{
1278	it->getRenderable()->setDecided(i,false);
1279	it->getRenderable()->setActualSide(i,BihPlaneEvent::PES_RIGHT);
1280	}
1281	it->ClearGrowBB();
1282	it++;
1283	}
1284	it = end;
1285	AxisAlignedBox tempBB[3];
1286	for (int i=0; i<dim; i++) tempBB[i].setNull();
1287
1288	while (it != begin)
1289	{
1290	it--;
1291	if ((it->getRenderable())) //&& (it->equalsType(*it, BihPlaneEvent::PET_START)))
1292	{
1293	tempBB[it->getDimension()].merge(it->getRenderable()->getBoundingBox());
1294	it->GrowBB(tempBB[it->getDimension()]);
1295	}
1296
1297
1298
1299	}
1300
1301	it = begin;
1302
1303
1304	while (it != end)
1305	{
1306
1307
1308	BihPlaneEventList::iterator p = it;
1309
1310	int d = p->getDimension();
1311
1312
1313	// find the corrected offsets for the left and right bounding box
1314
1315	LeftOffset[d]=0;
1316	RightOffset[d]=0;
1317
1318
1319
1320
1321
1322
1323
1324
1325	bool foundLeft[3];
1326	foundLeft[0]=false; foundLeft[1]=false; foundLeft[2]=false;
1327
1328
1329	// set the right border
1330	it_a=it;
1331	while (it_a!=end)
1332	{
1333	if ((it_a->getDimension()==d) && (it_a->GetType() == BihPlaneEvent::PET_START))
1334	{
1335
1336
1337	minRights[d]=it_a->GetGrowBB();
1338	#ifdef DEBUG_BUILD_TREE
1339	mBuildLog->logMessage("Found Right side: d" + StringConverter::toString(d)+ " " + StringConverter::toString(pos[d]) );
1340	#endif
1341	break;
1342	}
1343	it_a++;
1344	}
1345
1346
1347	it_a=LeftBorder[d];
1348	while (it_a!=it)
1349	{
1350	if (it_a->getRenderable())
1351	{
1352
1353	if ((it_a->getDimension()==d) && (!it_a->getRenderable()->isDecided(d)))
1354	{
1355	it_a->classify(*it, split.side,true);
1356	if (it_a->getRenderable()->getSide() == BihPlaneEvent::PES_RIGHT)
1357	{
1358	// right side
1359
1360	minRights[d].merge(it_a->getRenderable()->getBoundingBox());
1361	#ifdef DEBUG_BUILD_TREE
1362	mBuildLog->logMessage("Move to Right side: d" + StringConverter::toString(d)+ " " + StringConverter::toString(pos[d]) );
1363	#endif
1364
1365	} else
1366	{
1367	minLefts[d].merge(it_a->getRenderable()->getBoundingBox());
1368	it_a->getRenderable()->setDecided(d,true);
1369	it_a->getRenderable()->setActualSide(d,BihPlaneEvent::PES_LEFT);
1370
1371
1372	Vector3 pos=minLefts[d].getMaximum();
1373	nLeft[d]++; nRight[d]--;
1374	#ifdef DEBUG_BUILD_TREE
1375	mBuildLog->logMessage("Move to Left side: d" + StringConverter::toString(d)+ " " + StringConverter::toString(pos[d]) );
1376	#endif
1377	if ((it_a->getPosition()[d]>LeftBorder[d]->getPosition()[d]) && (!foundLeft[d]))
1378	{
1379	LeftBorder[d]=it_a;
1380	#ifdef DEBUG_BUILD_TREE
1381	mBuildLog->logMessage("Adjust left to d" + StringConverter::toString(d)+ " " + StringConverter::toString(it_a->getPosition()[d]) );
1382	#endif
1383	} else
1384	{
1385	#ifdef DEBUG_BUILD_TREE
1386	mBuildLog->logMessage("Found left d" + StringConverter::toString(d)+ " " + StringConverter::toString(it_a->getPosition()[d]) );
1387	#endif
1388	foundLeft[d]=true;
1389	}
1390
1391
1392	}
1393	}
1394
1395	}
1396	else
1397	{
1398	#ifdef DEBUG_BUILD_TREE
1399	mBuildLog->logMessage("------No renderable " + StringConverter::toString(d)+ " " + StringConverter::toString(it_a->getPosition()[d]) );
1400	#endif
1401	}
1402	it_a++;
1403	}
1404
1405	#endif
1406	if (it!=end) it++;
1407	#ifdef OLD_METHOD
1408	p->SAH(aabb, nLeft[d], nPlane[d], nRight[d], split,minLefts[d],minRights[d]);
1409	if (split.cost < best.cost)
1410	{
1411	if ((nLeft[d]!=0) && (nRight[d]!=0))
1412	best = split;
1413	}
1414	#ifdef DEBUG_BUILD_TREE
1415	mBuildLog->logMessage("SAH " + StringConverter::toString(best.cost)+ " " + StringConverter::toString(split.cost) +
1416	"dim: " + StringConverter::toString(d)+ "Elements: " + StringConverter::toString(nLeft[d]) +
1417	" " + StringConverter::toString(nRight[d])+ "Planes: "+ StringConverter::toString(minLefts[d].getMaximum()[d]) +
1418	" " + StringConverter::toString(it->getPosition()[d]) +" " + StringConverter::toString(minRights[d].getMinimum()[d])
1419	+" " + StringConverter::toString(LeftBorder[d]->getPosition()[d]));
1420
1421	mBuildLog->logMessage(" BOXES " + StringConverter::toString(minLefts[d].getMaximum()[d]-minLefts[d].getMinimum()[d]) +
1422	" " + StringConverter::toString(minRights[d].getMaximum()[d]-minRights[d].getMinimum()[d]));
1423	#endif // DEBUG_BUILD_TREE
1424
1425	#endif // OLD_METHOD
1426
1427
1428
1429	#ifndef OLD_METHOD
1430	if (it!=end)
1431	{
1432	if ((it->getPosition()[it->getDimension()]!=LastPosition[it->getDimension()]))
1433	{
1434	LastPosition[it->getDimension()]=it->getPosition()[it->getDimension()];
1435	p->SAH(aabb, nLeft[d], nPlane[d], nRight[d], split,minLefts[d],minRights[d]);
1436	if (split.cost < best.cost)
1437	{
1438	if ((nLeft[d]!=0) && (nRight[d]!=0))
1439	{
1440	best = split;
1441
1442	it_a=begin;
1443	while (it_a!=end)
1444	{
1445	if (it_a->getRenderable()) it_a->getRenderable()->FinalizeSide(d);
1446	it_a++;
1447	}
1448	#ifdef DEBUG_BUILD_TREE
1449	mBuildLog->logMessage("SAH " + StringConverter::toString(best.cost)+ " " + StringConverter::toString(split.cost) +
1450	"dim: " + StringConverter::toString(d)+ "Elements: " + StringConverter::toString(nLeft[d]) +
1451	" " + StringConverter::toString(nRight[d])+ "Planes: "+ StringConverter::toString(minLefts[d].getMaximum()[d]) +
1452	" " + StringConverter::toString(it->getPosition()[d]) +" " + StringConverter::toString(minRights[d].getMinimum()[d])
1453	+" " + StringConverter::toString(LeftBorder[d]->getPosition()[d])+ " " + StringConverter::toString(it->getPosition()[it->getDimension()]));
1454
1455	mBuildLog->logMessage("BOXES Left " + StringConverter::toString(minLefts[d].getMaximum()[d]-minLefts[d].getMinimum()[d]) +
1456	" " + StringConverter::toString(minRights[d].getMaximum()[d]-minRights[d].getMinimum()[d]));
1457	#endif
1458	}
1459
1460	}
1461
1462
1463
1464
1465	} else
1466	{
1467	#ifdef DEBUG_BUILD_TREE
1468	mBuildLog->logMessage("Cancel " + StringConverter::toString(it->getPosition()[it->getDimension()]));
1469	#endif
1470	}
1471
1472	} else
1473	{
1474	p->SAH(aabb, nLeft[d], nPlane[d], nRight[d], split,minLefts[d],minRights[d]);
1475	if (split.cost < best.cost)
1476	{
1477	if ((nLeft[d]!=0) && (nRight[d]!=0))
1478	{
1479	best = split;
1480	it_a=begin;
1481	while (it_a!=end)
1482	{
1483	if (it_a->getRenderable()) it_a->getRenderable()->FinalizeSide(d);
1484	it_a++;
1485	}
1486	}
1487	}
1488	#ifdef DEBUG_BUILD_TREE
1489	mBuildLog->logMessage("SAH " + StringConverter::toString(best.cost)+ " " + StringConverter::toString(split.cost) +
1490	"dim: " + StringConverter::toString(d)+ "Elements: " + StringConverter::toString(nLeft[d]) +
1491	" " + StringConverter::toString(nRight[d])+ "Planes: "+ StringConverter::toString(minLefts[d].getMaximum()[d]) +
1492	" " + StringConverter::toString(it->getPosition()[d]) +" " + StringConverter::toString(minRights[d].getMinimum()[d])
1493	+" " + StringConverter::toString(LeftBorder[d]->getPosition()[d])+ " " + StringConverter::toString(it->getPosition()[it->getDimension()]));
1494	#endif
1495	}
1496
1497	#endif
1498
1499
1500
1501
1502
1503
1504	#ifdef OLD_METHOD
1505	nLeft[d] += pStart; nLeft[d] += pOn;
1506	#endif
1507
1508	nPlane[d] = 0;
1509	}
1510	} else
1511	{
1512
1513	int d;
1514	while (it != end)
1515	{
1516	BihPlaneEventList::iterator p = it;
1517	d = p->getDimension();
1518	//if ((p->equalsType(it, BihPlaneEvent::PET_START)) \|\| (p->equalsType(it, BihPlaneEvent::PET_ON)))
1519	nObjectCount[d]++;
1520	it++;
1521	}
1522
1523	int MaxDimension=1;
1524	for (int i = 1; i < dim; i++)
1525	{
1526	if (nObjectCount[i]>nObjectCount[i-1]) MaxDimension=i;
1527	}
1528	it = begin;
1529
1530	nObjectCount[MaxDimension]/=2;
1531	while ((it != end) && (nObjectCount[MaxDimension]))
1532	{
1533	BihPlaneEventList::iterator p = it;
1534	if (p->getDimension()== MaxDimension)
1535	{
1536	nObjectCount[MaxDimension]--;
1537	best.event=*it;
1538	best.cost=0;
1539
1540	}
1541	it++;
1542	}
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552	}
1553
1554
1555	/************************************************/
1556	/************** BEGIN TERMINATE *************/
1557	/************************************************/
1558	// check terminating condition
1559
1560	if (best.cost > BihPlaneEvent::KI*nObjects \|\| level >= mMaxDepth \|\| nObjects<2 )
1561	{
1562	// Terminating condition reached, create leaf and add renderables to list
1563	#ifdef DEBUG_BUILD_TREE
1564	mBuildLog->logMessage("Terminate " + StringConverter::toString(best.cost)+ " o:" + StringConverter::toString(nObjects) +
1565	" ki: " + StringConverter::toString(BihPlaneEvent::KI*nObjects)+ " dim: " + StringConverter::toString(best.event.getDimension()));
1566	#endif
1567	BiHierarchy::Leaf * leaf = new BiHierarchy::Leaf(this, level, aabb, parent);
1568	if (parent->GetSide()==1) leaf->SetToLeft(); else leaf->SetToRight();
1569
1570
1571	BihRenderable *rend;
1572	it = begin;
1573	while (it != end)
1574	{
1575	rend = it->getRenderable();
1576	rend->setClassified(false);
1577	if (rend->attachTo(leaf, this))
1578	{
1579	leaf->insert(rend);
1580	}
1581	it++;
1582	}
1583	// update stats
1584	++ mTreeStats.mNumNodes;
1585	++ mTreeStats.mNumLeaves;
1586	// update bounding box
1587	leaf->_updateBounds(false);
1588	return leaf;
1589	}
1590
1591	/************************************************/
1592	/************** BEGIN CLASSIFY **************/
1593	/************************************************/
1594	// split the event list in left and right sub-lists
1595	else
1596	{
1597	BihPlaneEventList eventsRight, eventsLeft;
1598	it = begin;
1599	// slightly redundant, since we mark each renderable up to 6 times
1600	while (it != end)
1601	{
1602	it->getRenderable()->setSide(BihPlaneEvent::PES_BOTH);
1603	it->getRenderable()->setClassified(false);
1604	it++;
1605	}
1606	// now classify all renderables. do they belong to the left child, the right child or both?
1607	it = begin;
1608	while (it != end)
1609	{
1610	it->classify(best.event, best.side,true);
1611	it++;
1612	}
1613	// divide the event lists
1614	int nLeftS = 0, nRightS = 0, nBothS = 0;
1615	it = begin;
1616
1617	minLeft.setNull();
1618	minRight.setNull();
1619
1620
1621
1622	while (it != end)
1623	{
1624	// right-only nodes go in right list
1625	if (it->getRenderable())
1626	{
1627	if (it->getRenderable()->GetFinalSide(best.event.getDimension()) == BihPlaneEvent::PES_RIGHT)
1628	{
1629	if (!it->getRenderable()->isClassified())
1630	{
1631	it->getRenderable()->setClassified(true);
1632	nRightS++;
1633	}
1634	minRight.merge(it->getRenderable()->getBoundingBox());
1635	eventsRight.push_back(*it);
1636	}
1637	// left-only nodes go in left list
1638	else if (it->getRenderable()->GetFinalSide(best.event.getDimension()) == BihPlaneEvent::PES_LEFT)
1639	{
1640	if (!it->getRenderable()->isClassified())
1641	{
1642	it->getRenderable()->setClassified(true);
1643	nLeftS++;
1644	}
1645	minLeft.merge(it->getRenderable()->getBoundingBox());
1646	eventsLeft.push_back(*it);
1647	}
1648	}
1649
1650	it++;
1651	}
1652	#ifdef DEBUG_BUILD_TREE
1653	mBuildLog->logMessage("Split " + StringConverter::toString(best.cost)+ " o:" + StringConverter::toString(nObjects) +
1654	" ki: " + StringConverter::toString(BihPlaneEvent::KI*nObjects)+ " dim: " + StringConverter::toString(best.event.getDimension()));
1655	#endif
1656
1657
1658
1659
1660
1661
1662
1663
1664	// create a new branch node and continue recursion
1665	BiHierarchy::Branch * branch = new BiHierarchy::Branch(this, level, aabb, parent,
1666	best.event.getSplitPlane(), best.side);
1667
1668	// now create the child nodes and continue recursion
1669
1670	if (eventsLeft.size() > 0)
1671	{
1672
1673	branch->mLeft = recBuild(eventsLeft, nLeftS + nBothS, minLeft, branch);
1674	branch->mLeft->SetToLeft();
1675
1676	}
1677	if (eventsRight.size() > 0)
1678	{
1679
1680	branch->mRight = recBuild(eventsRight, nBothS + nRightS, /best.bright/ minRight, branch);
1681	branch->mRight->SetToRight();
1682
1683	}
1684
1685	// update stats
1686	++ mTreeStats.mNumNodes;
1687
1688	// update bounding box
1689	branch->_updateBounds(false);
1690
1691	return branch;
1692	}
1693	}
1694
1695	BiHierarchy::Node * BiHierarchy::pqBuild(BihPlaneEventList& events,
1696	int nObjects, AxisAlignedBox& aabb,
1697	BiHierarchy::Branch * parent)
1698	{
1699	SplitCandidatePQ pqueue;
1700	Real globalTreeCost;
1701	Real globalSA;
1702
1703	BiHierarchy::Node * newNode = 0, * topNode = 0;
1704	// init global tree cost
1705	globalTreeCost = BihPlaneEvent::KI * nObjects;
1706	globalSA = BihPlaneEvent::surfaceArea(aabb);
1707
1708	BihPlaneEventList * e = new BihPlaneEventList(events);
1709
1710	// inital split candidate
1711	BihSplitInfo * best = pqFindPlane(e, nObjects, aabb, globalSA);
1712	BihSubdivisionCandidate splitcandidate(e, nObjects, aabb, parent, globalTreeCost,
1713	globalTreeCost - best->cost, best, BihPlaneEvent::PES_BOTH);
1714	pqueue.push(splitcandidate);
1715
1716
1717	/* BEGIN ITERATIVE BUILD */
1718	while (!pqueue.empty())
1719	{
1720	BihSubdivisionCandidate sc = pqueue.top();
1721	pqueue.pop();
1722
1723	// determine the depth we are on
1724	int level = 0;
1725	if (sc.parent)
1726	{
1727	level = sc.parent->getLevel() + 1;
1728	}
1729
1730	/************************************************/
1731	/************** BEGIN TERMINATE *************/
1732	/************************************************/
1733	// check terminating condition
1734	if (sc.decrease < 0.0 \|\| level >= mMaxDepth)
1735	{
1736	// Terminating condition reached, create leaf and add renderables to list
1737	BiHierarchy::Leaf * leaf = new BiHierarchy::Leaf(this, level, sc.aabb, sc.parent);
1738	BihRenderable *rend;
1739	BihPlaneEventList::iterator begin = sc.events->begin();
1740	BihPlaneEventList::iterator end = sc.events->end();
1741	BihPlaneEventList::iterator it = begin;
1742	while (it != end)
1743	{
1744	rend = it->getRenderable();
1745	rend->setClassified(false);
1746	if (rend->attachTo(leaf, this))
1747	{
1748	leaf->insert(rend);
1749	}
1750	it++;
1751	}
1752	newNode = leaf;
1753	if (!topNode)
1754	topNode = leaf;
1755	// update stats
1756	++ mTreeStats.mNumNodes;
1757	++ mTreeStats.mNumLeaves;
1758	}
1759
1760	/************************************************/
1761	/************** BEGIN CLASSIFY **************/
1762	/************************************************/
1763	else
1764	{
1765	BihPlaneEventList * eventsLeft = new BihPlaneEventList();
1766	BihPlaneEventList * eventsRight = new BihPlaneEventList();
1767	BihPlaneEventList::iterator begin = sc.events->begin();
1768	BihPlaneEventList::iterator end = sc.events->end();
1769	BihPlaneEventList::iterator it = begin;
1770	// slightly redundant, since we mark each renderable up to 6 times
1771	while (it != end)
1772	{
1773	it->getRenderable()->setSide(BihPlaneEvent::PES_BOTH);
1774	it->getRenderable()->setClassified(false);
1775	it++;
1776	}
1777
1778	// now classify all renderables. do they belong to the left child, the right child or both?
1779	it = begin;
1780	while (it != end)
1781	{
1782	it->classify(sc.best->event, sc.best->side,false);
1783	it++;
1784	}
1785
1786	// divide the event lists
1787	int nLeftS = 0, nRightS = 0, nBothS = 0;
1788	it = begin;
1789	while (it != end)
1790	{
1791	// right-only events go in the right list
1792	if (it->getRenderable()->getSide() == BihPlaneEvent::PES_RIGHT)
1793	{
1794	if (!it->getRenderable()->isClassified())
1795	{
1796	it->getRenderable()->setClassified(true);
1797	nRightS++;
1798	}
1799
1800	eventsRight->push_back(*it);
1801	}
1802	// left-only events go in the left list
1803	else if (it->getRenderable()->getSide() == BihPlaneEvent::PES_LEFT)
1804	{
1805	if (!it->getRenderable()->isClassified())
1806	{
1807	it->getRenderable()->setClassified(true);
1808	nLeftS++;
1809	}
1810	eventsLeft->push_back(*it);
1811	}
1812	// the rest goes in both lists after being clipped
1813	else
1814	{
1815	if (!it->getRenderable()->isClassified())
1816	{
1817	it->getRenderable()->setClassified(true);
1818	nBothS++;
1819	}
1820
1821	eventsRight->push_back(it->clip(sc.best->bright, sc.best->event.getDimension()));
1822	eventsLeft->push_back(it->clip(sc.best->bleft, sc.best->event.getDimension()));
1823	}
1824	it++;
1825	}
1826
1827	// create a new branch node
1828	BiHierarchy::Branch * branch = new BiHierarchy::Branch(this, level, sc.aabb, sc.parent,
1829	sc.best->event.getSplitPlane(), sc.best->side);
1830
1831	globalTreeCost -= sc.decrease;
1832
1833
1834	// now for each potential child node, compute the split plane and the cost decrease
1835	// and place them in the queue
1836	if (eventsLeft->size() > 0)
1837	{
1838	best = pqFindPlane(eventsLeft, nLeftS + nBothS, sc.best->bleft, globalSA);
1839	Real old = BihPlaneEvent::surfaceArea(sc.best->bleft)/globalSABihPlaneEvent::KI(nLeftS + nBothS);
1840	BihSubdivisionCandidate scleft(eventsLeft, nLeftS + nBothS, sc.best->bleft,
1841	branch, old, old - best->cost, best, BihPlaneEvent::PES_LEFT);
1842	pqueue.push(scleft);
1843	}
1844	// cleanup
1845	else
1846	{
1847	delete eventsLeft;
1848	}
1849
1850	if (eventsRight->size() > 0)
1851	{
1852	best = pqFindPlane(eventsRight, nBothS + nRightS, sc.best->bright, globalSA);
1853	Real old = BihPlaneEvent::surfaceArea(sc.best->bright)/globalSABihPlaneEvent::KI(nBothS + nRightS);
1854	BihSubdivisionCandidate scright(eventsRight, nBothS + nRightS, sc.best->bright,
1855	branch, old, old - best->cost, best, BihPlaneEvent::PES_RIGHT);
1856	pqueue.push(scright);
1857	}
1858	// cleanup
1859	else
1860	{
1861	delete eventsRight;
1862	}
1863
1864	newNode = branch;
1865	if (!topNode)
1866	topNode = branch;
1867
1868
1869	// update stats
1870	++ mTreeStats.mNumNodes;
1871	}
1872
1873	// attach new node to parent
1874	if (sc.parent)
1875	{
1876	if (sc.side == BihPlaneEvent::PES_LEFT)
1877	{
1878	sc.parent->mLeft = newNode;
1879	}
1880	else if (sc.side == BihPlaneEvent::PES_RIGHT)
1881	{
1882	sc.parent->mRight = newNode;
1883	}
1884	else
1885	{
1886	OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
1887	"PQBUILD SNAFU - CHILD I AM NOT LEFT NOR RIGHT","BiHierarchy::pqBuild");
1888	}
1889	}
1890
1891	// update bounding boxes when geometry (leaf) was added
1892	if (newNode->isLeaf())
1893	newNode->_updateBounds();
1894
1895	//cleanup
1896	OGRE_DELETE(sc.events);
1897	OGRE_DELETE(sc.best);
1898	}
1899	mBuildLog->logMessage("Cost after PQBUILD " + StringConverter::toString(globalTreeCost));
1900	return topNode;
1901	}
1902
1903	//-------------------------------------------------------------------------
1904	BihSplitInfo * BiHierarchy::pqFindPlane(BihPlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA)
1905	{
1906	static const int dim = 3;
1907	int pStart, pOn, pEnd;
1908	int nLeft[dim], nPlane[dim], nRight[dim];
1909	for (int i = 0; i < dim; i++)
1910	{
1911	nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
1912	}
1913
1914	BihSplitInfo split, best;
1915	best.cost = Math::POS_INFINITY;
1916
1917	Real parentSA = BihPlaneEvent::surfaceArea(aabb);
1918
1919	BihPlaneEventList::iterator begin = events->begin();
1920	BihPlaneEventList::iterator end = events->end();
1921	BihPlaneEventList::iterator it = begin;
1922	// try all planes to find the best one for the given set of objects
1923	while (it != end)
1924	{
1925	BihPlaneEventList::iterator p = it;
1926	pStart = pOn = pEnd = 0;
1927	while (it != end && p->equalsType(*it, BihPlaneEvent::PET_END))
1928	{
1929	it++; pEnd++;
1930	}
1931	while (it != end && p->equalsType(*it, BihPlaneEvent::PET_ON))
1932	{
1933	it++; pOn++;
1934	}
1935	while (it != end && p->equalsType(*it, BihPlaneEvent::PET_START))
1936	{
1937	it++; pStart++;
1938	}
1939	int d = p->getDimension();
1940	nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
1941	p->pqSAH(globalSA, parentSA, nLeft[d], nPlane[d], nRight[d], aabb, split);
1942	if (split.cost < best.cost)
1943	{
1944	best = split;
1945	}
1946	nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
1947	}
1948	return new BihSplitInfo(best);
1949	}
1950
1951
1952
1953	/************************************************************************/
1954	/* BiHierarchy rendering functions */
1955	/************************************************************************/
1956
1957
1958	//-------------------------------------------------------------------------
1959	void BiHierarchy::queueVisibleObjects(BiHierarchyCamera* cam, RenderQueue* queue, bool onlyShadowCasters,
1960	bool showBoxes, BiHierarchy::NodeList& visibleNodes)
1961	{
1962	mFrameStats.clear();
1963	cam->mNumVisQueries = 0;
1964
1965	if (mBihRoot)
1966	recQueueVisibleObjects(mBihRoot, Root::getSingleton().getCurrentFrameNumber(),
1967	cam, queue, onlyShadowCasters, showBoxes, visibleNodes);
1968
1969	mFrameStats.mTraversedNodes = cam->mNumVisQueries;
1970	}
1971
1972	//-------------------------------------------------------------------------
1973	void BiHierarchy::recQueueVisibleObjects(BiHierarchy::Node * node, unsigned long currentFrame,
1974	BiHierarchyCamera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes,
1975	BiHierarchy::NodeList& visibleNodes, bool fullVis)
1976	{
1977	BiHierarchyCamera::NodeVisibility vis = BiHierarchyCamera::BIHNV_PART;
1978	// test visibility
1979	//if (cam->isVisible(node->mAABB))
1980	if (fullVis \|\|
1981	((vis = (cam->*getVisibility)(node->mAABB)) != BiHierarchyCamera::BIHNV_NONE))
1982	{
1983	visibleNodes.push_back(node);
1984
1985	bool v = (fullVis \|\| vis == BiHierarchyCamera::BIHNV_FULL);
1986
1987	node->queueVisibleObjects(currentFrame, cam, queue, onlyShadowCasters, showBoxes, v);
1988
1989	if (v \|\| node->isLeaf())
1990	++ mFrameStats.mRenderedNodes;
1991
1992	if (!v)
1993	{
1994
1995	if (node->getLeftChild())
1996	recQueueVisibleObjects(node->getLeftChild(), currentFrame,
1997	cam, queue, onlyShadowCasters, showBoxes, visibleNodes, v);
1998	if (node->getRightChild())
1999	recQueueVisibleObjects(node->getRightChild(), currentFrame,
2000	cam, queue, onlyShadowCasters, showBoxes, visibleNodes, v);
2001	}
2002	}
2003	else
2004	{
2005	++ mFrameStats.mFrustumCulledNodes;
2006	}
2007	}
2008
2009	//-------------------------------------------------------------------------
2010	void BiHierarchy::setEnhancedVis(bool enh)
2011	{
2012	if (enh)
2013	getVisibility = &BiHierarchyCamera::getVisibilityEnhanced;
2014	else
2015	getVisibility = &BiHierarchyCamera::getVisibilitySimple;
2016	}
2017
2018	//-------------------------------------------------------------------------
2019	bool BiHierarchy::getEnhancedVis()
2020	{
2021	return getVisibility == &BiHierarchyCamera::getVisibilityEnhanced;
2022	}
2023
2024	//-------------------------------------------------------------------------
2025	//void BiHierarchy::findVisibleNodes(NodeList& visibleNodes, Camera * cam)
2026	//{
2027	// if (mBihRoot)
2028	// recFindVisibleNodes(mBihRoot, visibleNodes, cam);
2029	//}
2030
2031	////-------------------------------------------------------------------------
2032	//void BiHierarchy::recFindVisibleNodes(BiHierarchy::Node * node, NodeList& visibleNodes, Camera * cam)
2033	//{
2034	// // test visibility
2035	// if (cam->isVisible(node->mAABB))
2036	// {
2037	// visibleNodes.push_back(node);
2038
2039	// if (node->getLeftChild())
2040	// recFindVisibleNodes(node->getLeftChild(), visibleNodes, cam);
2041	// if (node->getRightChild())
2042	// recFindVisibleNodes(node->getRightChild(), visibleNodes, cam);
2043	// }
2044	//}
2045
2046	void BiHierarchy::findNodesIn(const AxisAlignedBox &box, std::list<SceneNode > &list, SceneNode exclude)
2047	{
2048	if (mBihRoot)
2049	recFindNodesIn(box, list, exclude, mBihRoot);
2050	}
2051
2052	void BiHierarchy::findNodesIn(const Sphere &sphere, std::list<SceneNode > &list, SceneNode exclude)
2053	{
2054	if (mBihRoot)
2055	recFindNodesIn(sphere, list, exclude, mBihRoot);
2056	}
2057
2058	void BiHierarchy::findNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode > &list, SceneNode exclude)
2059	{
2060	if (mBihRoot)
2061	recFindNodesIn(volume, list, exclude, mBihRoot);
2062	}
2063
2064	void BiHierarchy::findNodesIn(const Ray &ray, std::list<SceneNode > &list, SceneNode exclude)
2065	{
2066	if (mBihRoot)
2067	recFindNodesIn(ray, list, exclude, mBihRoot);
2068	}
2069
2070	void BiHierarchy::recFindNodesIn(const AxisAlignedBox &box, std::list<SceneNode > &list, SceneNode exclude, Node * node, bool full)
2071	{
2072	// check intersection
2073	if ( !full )
2074	{
2075	BihIntersection isect = intersect(box, node->_getWorldAABB());
2076
2077	if ( isect == OUTSIDE )
2078	return ;
2079
2080	full = ( isect == INSIDE );
2081	}
2082
2083	if (node->isLeaf())
2084	{
2085	LeafPtr leaf = BIHLEAFPTR_CAST(node);
2086	for (BihRenderableList::iterator it = leaf->mBihRenderables.begin();
2087	it != leaf->mBihRenderables.end(); it ++)
2088	{
2089	SceneNode sn = static_cast<BiHierarchySceneNode >(*it);
2090
2091	if (sn != exclude)
2092	{
2093	if (full)
2094	{
2095	list.push_back(sn);
2096	}
2097	else
2098	{
2099	BihIntersection nsect = intersect(box, sn->_getWorldAABB());
2100
2101	if ( nsect != OUTSIDE )
2102	{
2103	list.push_back(sn);
2104	}
2105	}
2106	}
2107	}
2108	}
2109	else
2110	{
2111	if (node->getLeftChild())
2112	recFindNodesIn(box, list, exclude, node->getLeftChild(), full);
2113	if (node->getRightChild())
2114	recFindNodesIn(box, list, exclude, node->getRightChild(), full);
2115	}
2116	}
2117
2118
2119	void BiHierarchy::recFindNodesIn(const Sphere &sphere, std::list<SceneNode > &list, SceneNode exclude, Node * node, bool full)
2120	{
2121	// TODO
2122	}
2123
2124
2125	void BiHierarchy::recFindNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode > &list, SceneNode exclude, Node * node, bool full)
2126	{
2127	// TODO
2128	}
2129
2130
2131	void BiHierarchy::recFindNodesIn(const Ray &ray, std::list<SceneNode > &list, SceneNode exclude, Node * node, bool full)
2132	{
2133	// TODO
2134	}
2135
2136
2137	/************************************************************************/
2138	/* BiHierarchy debug & helper functions */
2139	/************************************************************************/
2140
2141	//-------------------------------------------------------------------------
2142	void BiHierarchy::dump()
2143	{
2144	//LogManager::getSingleton().logMessage("#@#@#@#@ Dumping BiHierarchy #@#@#@#@");
2145	mBuildLog->logMessage("#@#@#@#@ Dumping BiHierarchy #@#@#@#@");
2146	if (mBihRoot)
2147	dump(mBihRoot);
2148	}
2149
2150	//-------------------------------------------------------------------------
2151	void BiHierarchy::dump(BiHierarchy::Node * node)
2152	{
2153	//LogManager * log = LogManager::getSingletonPtr();
2154	BiHierarchySceneNode * scenenode;
2155	String pad;
2156	int p;
2157
2158	pad = "";
2159	for (p = 0; p < node->getLevel(); p++)
2160	{
2161	pad += " ";
2162	}
2163
2164	if (node->isLeaf())
2165	{
2166	BiHierarchy::Leaf * leaf = BIHLEAFPTR_CAST(node);
2167	BihRenderableList::iterator it = leaf->mBihRenderables.begin();
2168	BihRenderableList::iterator end = leaf->mBihRenderables.end();
2169	while (it != end)
2170	{
2171	scenenode = static_cast<BiHierarchySceneNode >(it);
2172	mBuildLog->logMessage(pad + "# Leaf level " +
2173	StringConverter::toString(node->getLevel()) +
2174	" SceneNode " + scenenode->getName());
2175	mBuildLog->logMessage(pad + "## Objects: " + scenenode->dumpToString());
2176	it++;
2177	}
2178	}
2179	else
2180	{
2181	BiHierarchy::Branch * branch = BIHBRANCHPTR_CAST(node);
2182	if (branch->mLeft)
2183	{
2184	mBuildLog->logMessage(pad + "# Branch level " +
2185	StringConverter::toString(node->getLevel()) + " Left Child");
2186	dump(branch->mLeft);
2187	}
2188	if (branch->mRight)
2189	{
2190	mBuildLog->logMessage(pad + "# Branch level " +
2191	StringConverter::toString(node->getLevel()) + " Right Child");
2192	dump(branch->mRight);
2193	}
2194	}
2195	}
2196
2197	//-------------------------------------------------------------------------
2198	Real BiHierarchy::calcCost()
2199	{
2200	if (mBihRoot)
2201	return calcCost(mBihRoot, BihPlaneEvent::surfaceArea(mBihRoot->mAABB));
2202	else
2203	return 0;
2204	}
2205
2206	//-------------------------------------------------------------------------
2207	Real BiHierarchy::calcCost(BiHierarchy::Node * node, Real vs)
2208	{
2209	if (node == 0)
2210	return 0.0;
2211
2212	if (node->isLeaf())
2213	{
2214	BiHierarchy::Leaf * leaf = BIHLEAFPTR_CAST(node);
2215	return (BihPlaneEvent::surfaceArea(node->mAABB)/vs) *
2216	BihPlaneEvent::KI * leaf->mBihRenderables.size();
2217	}
2218	else
2219	{
2220	BiHierarchy::Branch * branch = BIHBRANCHPTR_CAST(node);
2221	return (BihPlaneEvent::surfaceArea(node->mAABB)/vs) * BihPlaneEvent::KT +
2222	calcCost(branch->mLeft, vs) + calcCost(branch->mRight, vs);
2223	}
2224	}
2225
2226	/************************************************************************/
2227	/* BiHierarchy::Node/Branch/Leaf functions */
2228	/************************************************************************/
2229
2230	//-------------------------------------------------------------------------
2231	BiHierarchy::Leaf::~Leaf()
2232	{
2233	// detach all scene nodes in the case that we are rebuilding
2234	// the tree but not the scene
2235	BihRenderableList::iterator it = mBihRenderables.begin();
2236	BihRenderableList::iterator end = mBihRenderables.end();
2237	while (it != end)
2238	{
2239	(*it)->detachFrom(this);
2240	it++;
2241	}
2242	mBihRenderables.clear();
2243	}
2244
2245	//-------------------------------------------------------------------------
2246	void BiHierarchy::Leaf::queueVisibleObjects(unsigned long currentFrame,
2247	Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis)
2248	{
2249	BihRenderableList::iterator it = mBihRenderables.begin();
2250	BihRenderableList::iterator end = mBihRenderables.end();
2251	while (it != end)
2252	{
2253	if (!(*it)->isQueued(currentFrame, cam))
2254	{
2255	(*it)->queueObjects(cam, queue, onlyShadowCasters);
2256	}
2257	it++;
2258	}
2259
2260	if (showBoxes)
2261	{
2262	/*
2263	if (mLevel == mOwner->getHiLiteLevel()\|\| (mLevel-1) == mOwner->getHiLiteLevel() \|\| mOwner->getShowAllBoxes())
2264	queue->addRenderable(getWireBoundingBox());
2265	*/
2266
2267	if (mLevel == mOwner->getHiLiteLevel() \|\| mOwner->getShowAllBoxes())
2268	queue->addRenderable(getWireBoundingBox());
2269
2270	}
2271
2272	}
2273
2274	//-------------------------------------------------------------------------
2275	void BiHierarchy::Leaf::getGeometryList(GeometryVector *geometryList)
2276	{
2277	BihRenderableList::iterator it = mBihRenderables.begin();
2278	BihRenderableList::iterator end = mBihRenderables.end();
2279	while (it != end)
2280	{
2281	(*it)->getGeometryList(geometryList);
2282	it++;
2283	}
2284	}
2285
2286	//-------------------------------------------------------------------------
2287	// update the world aabb based on the contained geometry
2288	void BiHierarchy::Leaf::_updateBounds(bool recurse)
2289	{
2290	// reset box
2291	mWorldAABB.setNull();
2292
2293	// merge boxes from attached geometry
2294	BihRenderableList::iterator it = mBihRenderables.begin();
2295	BihRenderableList::iterator end = mBihRenderables.end();
2296	while (it != end)
2297	{
2298	//(*it)->_updateBounds();
2299	mWorldAABB.merge((*it)->getBoundingBox());
2300	it++;
2301	}
2302
2303	// update parent recursively
2304	if (recurse && mParent)
2305	mParent->_updateBounds(recurse);
2306	}
2307
2308	} // namespace Ogre

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

Context Navigation

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

Download in other formats: