Context Navigation

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

Revision 2383, 64.8 KB checked in by vizrt_christian_seidl, 17 years ago (diff)
some smaller changes

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

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

Download in other formats: