Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp @ 555

Revision 555, 78.8 KB checked in by mattausch, 18 years ago (diff)
fixed bug in finalizeviewcells when loading view cells

Line
1	#include <stack>
2	#include <time.h>
3	#include <iomanip>
4
5	#include "Plane3.h"
6	#include "VspBspTree.h"
7	#include "Mesh.h"
8	#include "common.h"
9	#include "ViewCell.h"
10	#include "Environment.h"
11	#include "Polygon3.h"
12	#include "Ray.h"
13	#include "AxisAlignedBox3.h"
14	#include "Exporter.h"
15	#include "Plane3.h"
16	#include "ViewCellBsp.h"
17	#include "ViewCellsManager.h"
18	#include "Beam.h"
19
20	//-- static members
21
22	/** Evaluates split plane classification with respect to the plane's
23	contribution for a minimum number of ray splits.
24	*/
25	const float VspBspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
26	/** Evaluates split plane classification with respect to the plane's
27	contribution for balanced rays.
28	*/
29	const float VspBspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
30
31	int BspMergeCandidate::sMaxPvsSize = 0;
32
33	int VspBspTree::sFrontId = 0;
34	int VspBspTree::sBackId = 0;
35	int VspBspTree::sFrontAndBackId = 0;
36
37	float BspMergeCandidate::sOverallCost = 0;
38	bool BspMergeCandidate::sUseArea = false;
39
40	/********************************************************************/
41	/* class VspBspTree implementation */
42	/********************************************************************/
43
44	VspBspTree::VspBspTree():
45	mRoot(NULL),
46	mUseAreaForPvs(false),
47	mCostNormalizer(Limits::Small),
48	mViewCellsManager(NULL),
49	mOutOfBoundsCell(NULL),
50	mStoreRays(false)
51	{
52	bool randomize = false;
53	environment->GetBoolValue("VspBspTree.Construction.randomize", randomize);
54	if (randomize)
55	Randomize(); // initialise random generator for heuristics
56
57	//-- termination criteria for autopartition
58	environment->GetIntValue("VspBspTree.Termination.maxDepth", mTermMaxDepth);
59	environment->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs);
60	environment->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays);
61	environment->GetFloatValue("VspBspTree.Termination.minProbability", mTermMinProbability);
62	environment->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
63	environment->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
64	environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
65	environment->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
66
67	//-- factors for bsp tree split plane heuristics
68	environment->GetFloatValue("VspBspTree.Factor.balancedRays", mBalancedRaysFactor);
69	environment->GetFloatValue("VspBspTree.Factor.pvs", mPvsFactor);
70	environment->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi);
71
72	//-- max cost ratio for early tree termination
73	environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
74
75	//-- partition criteria
76	environment->GetIntValue("VspBspTree.maxPolyCandidates", mMaxPolyCandidates);
77	environment->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates);
78	environment->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy);
79
80	environment->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon);
81	environment->GetIntValue("VspBspTree.maxTests", mMaxTests);
82
83	// maximum and minimum number of view cells
84	environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
85
86	environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
87
88	//-- merge options
89	environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells);
90	environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
91	environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge);
92
93
94	//-- termination criteria for axis aligned split
95	environment->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution",
96	mTermMaxRayContriForAxisAligned);
97	environment->GetIntValue("VspBspTree.Termination.AxisAligned.minRays",
98	mTermMinRaysForAxisAligned);
99
100	//environment->GetFloatValue("VspBspTree.maxTotalMemory", mMaxTotalMemory);
101	environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
102
103
104	mStats.open("bspStats.log");
105
106	//-- debug output
107	Debug << "***** VSP BSP options ****** " << endl;
108	Debug << "max depth: " << mTermMaxDepth << endl;
109	Debug << "min PVS: " << mTermMinPvs << endl;
110	Debug << "min probabiliy: " << mTermMinProbability << endl;
111	Debug << "min rays: " << mTermMinRays << endl;
112	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
113	//Debug << "VSP BSP mininam accumulated ray lenght: ", mTermMinAccRayLength) << endl;
114	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
115	Debug << "miss tolerance: " << mTermMissTolerance << endl;
116	Debug << "max view cells: " << mMaxViewCells << endl;
117	Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
118	Debug << "max plane candidates: " << mMaxRayCandidates << endl;
119	Debug << "randomize: " << randomize << endl;
120	Debug << "minimum view cells: " << mMergeMinViewCells << endl;
121	Debug << "using area for pvs: " << mUseAreaForPvs << endl;
122	Debug << "Split plane strategy: ";
123	if (mSplitPlaneStrategy & RANDOM_POLYGON)
124	{
125	Debug << "random polygon ";
126	}
127	if (mSplitPlaneStrategy & AXIS_ALIGNED)
128	{
129	Debug << "axis aligned ";
130	}
131	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
132	{
133	mCostNormalizer += mLeastRaySplitsFactor;
134	Debug << "least ray splits ";
135	}
136	if (mSplitPlaneStrategy & BALANCED_RAYS)
137	{
138	mCostNormalizer += mBalancedRaysFactor;
139	Debug << "balanced rays ";
140	}
141	if (mSplitPlaneStrategy & PVS)
142	{
143	mCostNormalizer += mPvsFactor;
144	Debug << "pvs";
145	}
146
147
148	mSplitCandidates = new vector<SortableEntry>;
149
150	Debug << endl;
151	}
152
153	BspViewCell *VspBspTree::GetOutOfBoundsCell()
154	{
155	return mOutOfBoundsCell;
156	}
157
158
159	BspViewCell *VspBspTree::GetOrCreateOutOfBoundsCell()
160	{
161	if (!mOutOfBoundsCell)
162	{
163	mOutOfBoundsCell = new BspViewCell();
164	mOutOfBoundsCell->SetId(-1);
165	mOutOfBoundsCell->SetValid(false);
166	}
167
168	return mOutOfBoundsCell;
169	}
170
171
172	const BspTreeStatistics &VspBspTree::GetStatistics() const
173	{
174	return mStat;
175	}
176
177
178	VspBspTree::~VspBspTree()
179	{
180	DEL_PTR(mRoot);
181	DEL_PTR(mSplitCandidates);
182	}
183
184	int VspBspTree::AddMeshToPolygons(Mesh *mesh,
185	PolygonContainer &polys,
186	MeshInstance *parent)
187	{
188	FaceContainer::const_iterator fi;
189
190	// copy the face data to polygons
191	for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
192	{
193	Polygon3 poly = new Polygon3((fi), mesh);
194
195	if (poly->Valid(mEpsilon))
196	{
197	poly->mParent = parent; // set parent intersectable
198	polys.push_back(poly);
199	}
200	else
201	DEL_PTR(poly);
202	}
203	return (int)mesh->mFaces.size();
204	}
205
206	int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
207	PolygonContainer &polys,
208	int maxObjects)
209	{
210	int limit = (maxObjects > 0) ?
211	Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
212
213	int polysSize = 0;
214
215	for (int i = 0; i < limit; ++ i)
216	{
217	if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
218	{
219	mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
220	polysSize +=
221	AddMeshToPolygons(viewCells[i]->GetMesh(),
222	polys,
223	viewCells[i]);
224	}
225	}
226
227	return polysSize;
228	}
229
230	int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
231	PolygonContainer &polys,
232	int maxObjects)
233	{
234	int limit = (maxObjects > 0) ?
235	Min((int)objects.size(), maxObjects) : (int)objects.size();
236
237	for (int i = 0; i < limit; ++i)
238	{
239	Intersectable object = objects[i];//it;
240	Mesh *mesh = NULL;
241
242	switch (object->Type()) // extract the meshes
243	{
244	case Intersectable::MESH_INSTANCE:
245	mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
246	break;
247	case Intersectable::VIEW_CELL:
248	mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
249	break;
250	// TODO: handle transformed mesh instances
251	default:
252	Debug << "intersectable type not supported" << endl;
253	break;
254	}
255
256	if (mesh) // copy the mesh data to polygons
257	{
258	mBox.Include(object->GetBox()); // add to BSP tree aabb
259	AddMeshToPolygons(mesh, polys, NULL);
260	}
261	}
262
263	return (int)polys.size();
264	}
265
266	void VspBspTree::Construct(const VssRayContainer &sampleRays,
267	AxisAlignedBox3 *forcedBoundingBox)
268	{
269	mStat.nodes = 1;
270	mBox.Initialize(); // initialise BSP tree bounding box
271
272	if (forcedBoundingBox)
273	mBox = *forcedBoundingBox;
274
275	PolygonContainer polys;
276	RayInfoContainer *rays = new RayInfoContainer();
277
278	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
279
280	long startTime = GetTime();
281
282	cout << "Extracting polygons from rays ... ";
283
284	Intersectable::NewMail();
285
286	int numObj = 0;
287
288	//-- extract polygons intersected by the rays
289	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
290	{
291	VssRay ray = rit;
292
293	if ((mBox.IsInside(ray->mTermination) \|\| !forcedBoundingBox) &&
294	ray->mTerminationObject &&
295	!ray->mTerminationObject->Mailed())
296	{
297	ray->mTerminationObject->Mail();
298	MeshInstance obj = dynamic_cast<MeshInstance >(ray->mTerminationObject);
299	AddMeshToPolygons(obj->GetMesh(), polys, obj);
300	++ numObj;
301	//-- compute bounding box
302	if (!forcedBoundingBox)
303	mBox.Include(ray->mTermination);
304	}
305
306	if ((mBox.IsInside(ray->mOrigin) \|\| !forcedBoundingBox) &&
307	ray->mOriginObject &&
308	!ray->mOriginObject->Mailed())
309	{
310	ray->mOriginObject->Mail();
311	MeshInstance obj = dynamic_cast<MeshInstance >(ray->mOriginObject);
312	AddMeshToPolygons(obj->GetMesh(), polys, obj);
313	++ numObj;
314
315	//-- compute bounding box
316	if (!forcedBoundingBox)
317	mBox.Include(ray->mOrigin);
318	}
319	}
320
321	Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mViewCellsManager->GetMaxPvsSize() << endl;
322	//-- store rays
323	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
324	{
325	VssRay ray = rit;
326
327	float minT, maxT;
328
329	// TODO: not very efficient to implictly cast between rays types
330	if (mBox.GetRaySegment(*ray, minT, maxT))
331	{
332	float len = ray->Length();
333
334	if (!len)
335	len = Limits::Small;
336
337	rays->push_back(RayInfo(ray, minT / len, maxT / len));
338	}
339	}
340
341	if (mUseAreaForPvs)
342	mTermMinProbability *= mBox.SurfaceArea(); // normalize
343	else
344	mTermMinProbability *= mBox.GetVolume();
345
346	mStat.polys = (int)polys.size();
347
348	cout << "finished" << endl;
349
350	Debug << "\nPolygon extraction: " << (int)polys.size() << " polys extracted from "
351	<< (int)sampleRays.size() << " rays in "
352	<< TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
353
354	Construct(polys, rays);
355
356	// clean up polygons
357	CLEAR_CONTAINER(polys);
358	}
359
360
361	// return memory usage in MB
362	float VspBspTree::GetMemUsage() const
363	{
364	return
365	(sizeof(VspBspTree) +
366	mStat.Leaves() * sizeof(BspLeaf) +
367	mStat.Interior() * sizeof(BspInterior) +
368	mStat.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
369	}
370
371
372
373	void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
374	{
375	VspBspTraversalStack tStack;
376
377	mRoot = new BspLeaf();
378
379	// constrruct root node geometry
380	BspNodeGeometry *geom = new BspNodeGeometry();
381	ConstructGeometry(mRoot, *geom);
382
383	const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
384
385	VspBspTraversalData tData(mRoot,
386	new PolygonContainer(polys),
387	0,
388	rays,
389	ComputePvsSize(*rays),
390	prop,
391	geom);
392
393	tStack.push(tData);
394
395	mStat.Start();
396	cout << "Contructing vsp bsp tree ... \n";
397
398	long startTime = GetTime();
399	// used for intermediate time measurements
400	long interTime = GetTime();
401
402	mOutOfMemory = false;
403
404	int nleaves = 500;
405
406	while (!tStack.empty())
407	{
408	tData = tStack.top();
409	tStack.pop();
410
411	if (0 && !mOutOfMemory)
412	{
413	float mem = GetMemUsage();
414
415	if (mem > mMaxMemory)
416	{
417	mOutOfMemory = true;
418	Debug << "memory limit reached: " << mem << endl;
419	}
420	}
421
422	// subdivide leaf node
423	BspNode *r = Subdivide(tStack, tData);
424
425	if (r == mRoot)
426	Debug << "VSP BSP tree construction time spent at root: "
427	<< TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
428
429	if (mStat.Leaves() >= nleaves)
430	{
431	nleaves += 500;
432
433	cout << "leaves=" << mStat.Leaves() << endl;
434	Debug << "needed "
435	<< TimeDiff(interTime, GetTime())*1e-3 << " secs to create 500 leaves" << endl;
436	interTime = GetTime();
437	}
438	}
439
440	Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
441	cout << "finished\n";
442
443	mStat.Stop();
444	}
445
446
447	bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const
448	{
449	return
450	(((int)data.mRays->size() <= mTermMinRays) \|\|
451	(data.mPvs <= mTermMinPvs) \|\|
452	(data.mProbability <= mTermMinProbability) \|\|
453	(mStat.Leaves() >= mMaxViewCells) \|\|
454	(data.GetAvgRayContribution() > mTermMaxRayContribution) \|\|
455	(data.mDepth >= mTermMaxDepth));
456	}
457
458
459	BspNode *VspBspTree::Subdivide(VspBspTraversalStack &tStack,
460	VspBspTraversalData &tData)
461	{
462	BspNode *newNode = tData.mNode;
463
464	if (!mOutOfMemory && !TerminationCriteriaMet(tData))
465	{
466	PolygonContainer coincident;
467
468	VspBspTraversalData tFrontData;
469	VspBspTraversalData tBackData;
470
471	// create new interior node and two leaf nodes
472	// or return leaf as it is (if maxCostRatio missed)
473	newNode = SubdivideNode(tData, tFrontData, tBackData, coincident);
474
475	if (!newNode->IsLeaf()) //-- continue subdivision
476	{
477	// push the children on the stack
478	tStack.push(tFrontData);
479	tStack.push(tBackData);
480
481	// delete old leaf node
482	DEL_PTR(tData.mNode);
483	}
484	}
485
486	//-- terminate traversal and create new view cell
487	if (newNode->IsLeaf())
488	{
489	BspLeaf leaf = dynamic_cast<BspLeaf >(newNode);
490	BspViewCell *viewCell = new BspViewCell();
491
492	leaf->SetViewCell(viewCell);
493
494	//-- update pvs
495	int conSamp = 0, sampCon = 0;
496	AddToPvs(leaf, *tData.mRays, conSamp, sampCon);
497
498	mStat.contributingSamples += conSamp;
499	mStat.sampleContributions += sampCon;
500
501	//-- store additional info
502	if (mStoreRays)
503	{
504	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
505	for (it = tData.mRays->begin(); it != it_end; ++ it)
506	leaf->mVssRays.push_back((*it).mRay);
507	}
508
509	if (!mViewCellsManager->CheckValid(viewCell))
510	{
511	viewCell->SetValid(false);
512
513	leaf->SetTreeValid(false);
514	PropagateUpValidity(leaf);
515
516	++ mStat.invalidLeaves;
517	}
518
519	viewCell->mLeaves.push_back(leaf);
520
521	if (mUseAreaForPvs)
522	viewCell->SetArea(tData.mProbability);
523	else
524	viewCell->SetVolume(tData.mProbability);
525
526	leaf->mProbability = tData.mProbability;
527
528	EvaluateLeafStats(tData);
529	}
530
531	//-- cleanup
532	tData.Clear();
533
534	return newNode;
535	}
536
537
538
539
540	BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
541	VspBspTraversalData &frontData,
542	VspBspTraversalData &backData,
543	PolygonContainer &coincident)
544	{
545	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
546
547	// select subdivision plane
548	Plane3 splitPlane;
549
550	int maxCostMisses = tData.mMaxCostMisses;
551
552	const bool success =
553	SelectPlane(splitPlane, leaf, tData, frontData, backData);
554
555	if (!success)
556	{
557	++ maxCostMisses;
558
559	if (maxCostMisses > mTermMissTolerance)
560	{
561	// terminate branch because of max cost
562	++ mStat.maxCostNodes;
563	return leaf;
564	}
565	}
566
567	mStat.nodes += 2;
568
569	//-- subdivide further
570	BspInterior *interior = new BspInterior(splitPlane);
571
572	#ifdef _DEBUG
573	Debug << interior << endl;
574	#endif
575
576	//-- the front and back traversal data is filled with the new values
577	frontData.mDepth = tData.mDepth + 1;
578	frontData.mPolygons = new PolygonContainer();
579	frontData.mRays = new RayInfoContainer();
580
581	backData.mDepth = tData.mDepth + 1;
582	backData.mPolygons = new PolygonContainer();
583	backData.mRays = new RayInfoContainer();
584
585	// subdivide rays
586	SplitRays(interior->GetPlane(),
587	*tData.mRays,
588	*frontData.mRays,
589	*backData.mRays);
590
591	// subdivide polygons
592	SplitPolygons(interior->GetPlane(),
593	*tData.mPolygons,
594	*frontData.mPolygons,
595	*backData.mPolygons,
596	coincident);
597
598
599	// how often was max cost ratio missed in this branch?
600	frontData.mMaxCostMisses = maxCostMisses;
601	backData.mMaxCostMisses = maxCostMisses;
602
603	// compute pvs
604	frontData.mPvs = ComputePvsSize(*frontData.mRays);
605	backData.mPvs = ComputePvsSize(*backData.mRays);
606
607	// split front and back node geometry and compute area
608
609	// if geometry was not already computed
610	if (!frontData.mGeometry && !backData.mGeometry)
611	{
612	frontData.mGeometry = new BspNodeGeometry();
613	backData.mGeometry = new BspNodeGeometry();
614
615	tData.mGeometry->SplitGeometry(*frontData.mGeometry,
616	*backData.mGeometry,
617	interior->GetPlane(),
618	mBox,
619	mEpsilon);
620
621	if (mUseAreaForPvs)
622	{
623	frontData.mProbability = frontData.mGeometry->GetArea();
624	backData.mProbability = backData.mGeometry->GetArea();
625	}
626	else
627	{
628	frontData.mProbability = frontData.mGeometry->GetVolume();
629	backData.mProbability = backData.mGeometry->GetVolume();
630	}
631	}
632
633
634	//-- create front and back leaf
635
636	BspInterior *parent = leaf->GetParent();
637
638	// replace a link from node's parent
639	if (parent)
640	{
641	parent->ReplaceChildLink(leaf, interior);
642	interior->SetParent(parent);
643	}
644	else // new root
645	{
646	mRoot = interior;
647	}
648
649	// and setup child links
650	interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
651
652	frontData.mNode = interior->GetFront();
653	backData.mNode = interior->GetBack();
654
655	//DEL_PTR(leaf);
656	return interior;
657	}
658
659
660	void VspBspTree::AddToPvs(BspLeaf *leaf,
661	const RayInfoContainer &rays,
662	int &sampleContributions,
663	int &contributingSamples)
664	{
665	sampleContributions = 0;
666	contributingSamples = 0;
667
668	RayInfoContainer::const_iterator it, it_end = rays.end();
669
670	ViewCell *vc = leaf->GetViewCell();
671
672	// add contributions from samples to the PVS
673	for (it = rays.begin(); it != it_end; ++ it)
674	{
675	int contribution = 0;
676	VssRay ray = (it).mRay;
677
678	if (ray->mTerminationObject)
679	contribution += vc->GetPvs().AddSample(ray->mTerminationObject);
680
681	if (ray->mOriginObject)
682	contribution += vc->GetPvs().AddSample(ray->mOriginObject);
683
684	if (contribution)
685	{
686	sampleContributions += contribution;
687	++ contributingSamples;
688	}
689	//leaf->mVssRays.push_back(ray);
690	}
691	}
692
693	void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis)
694	{
695	mSplitCandidates->clear();
696
697	int requestedSize = 2 * (int)(rays.size());
698	// creates a sorted split candidates array
699	if (mSplitCandidates->capacity() > 500000 &&
700	requestedSize < (int)(mSplitCandidates->capacity()/10) )
701	{
702	delete mSplitCandidates;
703	mSplitCandidates = new vector<SortableEntry>;
704	}
705
706	mSplitCandidates->reserve(requestedSize);
707
708	// insert all queries
709	for(RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
710	{
711	bool positive = (*ri).mRay->HasPosDir(axis);
712	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
713	(ri).ExtrapOrigin(axis), (ri).mRay));
714
715	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
716	(ri).ExtrapTermination(axis), (ri).mRay));
717	}
718
719	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
720	}
721
722	float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
723	const AxisAlignedBox3 &box,
724	const int pvsSize,
725	const int &axis,
726	float &position)
727	{
728	int raysBack;
729	int raysFront;
730	int pvsBack;
731	int pvsFront;
732
733	SortSplitCandidates(rays, axis);
734
735	// go through the lists, count the number of objects left and right
736	// and evaluate the following cost funcion:
737	// C = ct_div_ci + (qlrl + qrrr)/queries
738
739	int rl = 0, rr = (int)rays.size();
740	int pl = 0, pr = pvsSize;
741
742	float minBox = box.Min(axis);
743	float maxBox = box.Max(axis);
744	float sizeBox = maxBox - minBox;
745
746	float minBand = minBox + 0.1f*(maxBox - minBox);
747	float maxBand = minBox + 0.9f*(maxBox - minBox);
748
749	float sum = rr*sizeBox;
750	float minSum = 1e20f;
751
752	Intersectable::NewMail();
753
754	// set all object as belonging to the fron pvs
755	for(RayInfoContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
756	{
757	if ((*ri).mRay->IsActive())
758	{
759	Intersectable object = (ri).mRay->mTerminationObject;
760
761	if (object)
762	{
763	if (!object->Mailed())
764	{
765	object->Mail();
766	object->mCounter = 1;
767	}
768	else
769	++ object->mCounter;
770	}
771	}
772	}
773
774	Intersectable::NewMail();
775
776	for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin();
777	ci < mSplitCandidates->end(); ++ ci)
778	{
779	VssRay *ray;
780
781	switch ((*ci).type)
782	{
783	case SortableEntry::ERayMin:
784	{
785	++ rl;
786	ray = (VssRay ) (ci).ray;
787
788	Intersectable *object = ray->mTerminationObject;
789
790	if (object && !object->Mailed())
791	{
792	object->Mail();
793	++ pl;
794	}
795	break;
796	}
797	case SortableEntry::ERayMax:
798	{
799	-- rr;
800	ray = (VssRay ) (ci).ray;
801
802	Intersectable *object = ray->mTerminationObject;
803
804	if (object)
805	{
806	if (-- object->mCounter == 0)
807	-- pr;
808	}
809
810	break;
811	}
812	}
813
814	// Note: sufficient to compare size of bounding boxes of front and back side?
815	if ((ci).value > minBand && (ci).value < maxBand)
816	{
817	sum = pl((ci).value - minBox) + pr(maxBox - (ci).value);
818
819	// cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
820	// cout<<"cost= "<<sum<<endl;
821
822	if (sum < minSum)
823	{
824	minSum = sum;
825	position = (*ci).value;
826
827	raysBack = rl;
828	raysFront = rr;
829
830	pvsBack = pl;
831	pvsFront = pr;
832
833	}
834	}
835	}
836
837	float oldCost = (float)pvsSize;
838	float newCost = mCtDivCi + minSum / sizeBox;
839	float ratio = newCost / oldCost;
840
841	//Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
842	// <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
843
844	return ratio;
845	}
846
847
848	float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
849	const VspBspTraversalData &tData,
850	int &axis,
851	BspNodeGeometry **frontGeom,
852	BspNodeGeometry **backGeom,
853	float &pFront,
854	float &pBack,
855	const bool useKdSplit)
856	{
857	const bool useCostHeuristics = false;
858
859	//-- regular split
860	float nPosition[3];
861	float nCostRatio[3];
862	float nProbFront[3];
863	float nProbBack[3];
864
865	BspNodeGeometry *nFrontGeom[3];
866	BspNodeGeometry *nBackGeom[3];
867
868	int bestAxis = -1;
869
870	// create bounding box of node geometry
871	AxisAlignedBox3 box;
872	box.Initialize();
873
874	//TODO: for kd split geometry already is box
875	if (1)
876	{
877	PolygonContainer::const_iterator it, it_end = tData.mGeometry->mPolys.end();
878
879	for(it = tData.mGeometry->mPolys.begin(); it < it_end; ++ it)
880	box.Include((it));
881	}
882	else
883	{
884	RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end();
885
886	for(ri = tData.mRays->begin(); ri < ri_end; ++ ri)
887	box.Include((*ri).ExtrapTermination());
888	}
889
890	const int sAxis = box.Size().DrivingAxis();
891
892	for (axis = 0; axis < 3; ++ axis)
893	{
894	nFrontGeom[axis] = new BspNodeGeometry();
895	nBackGeom[axis] = new BspNodeGeometry();
896
897	if (!mOnlyDrivingAxis \|\| (axis == sAxis))
898	{
899	if (!useCostHeuristics)
900	{
901	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
902	Vector3 normal(0,0,0); normal[axis] = 1.0f;
903
904	// allows faster split because we have axis aligned kd tree boxes
905	if (useKdSplit)
906	{
907	nCostRatio[axis] = EvalAxisAlignedSplitCost(tData,
908	box,
909	axis,
910	nPosition[axis],
911	nProbFront[axis],
912	nProbBack[axis]);
913
914	Vector3 pos;
915
916	pos = box.Max(); pos[axis] = nPosition[axis];
917	AxisAlignedBox3 bBox(box.Min(), pos);
918	bBox.ExtractPolys(nBackGeom[axis]->mPolys);
919
920	pos = box.Min(); pos[axis] = nPosition[axis];
921	AxisAlignedBox3 fBox(pos, box.Max());
922	fBox.ExtractPolys(nFrontGeom[axis]->mPolys);
923	}
924	else
925	{
926	nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]),
927	tData, nFrontGeom[axis], nBackGeom[axis],
928	nProbFront[axis], nProbBack[axis]);
929	}
930	}
931	else
932	{
933	nCostRatio[axis] =
934	BestCostRatioHeuristics(*tData.mRays,
935	box,
936	tData.mPvs,
937	axis,
938	nPosition[axis]);
939	}
940
941	if (bestAxis == -1)
942	{
943	bestAxis = axis;
944	}
945
946	else if (nCostRatio[axis] < nCostRatio[bestAxis])
947	{
948	bestAxis = axis;
949	}
950
951	}
952	}
953
954	//-- assign values
955	axis = bestAxis;
956	pFront = nProbFront[bestAxis];
957	pBack = nProbBack[bestAxis];
958
959	// assign best split nodes geometry
960	*frontGeom = nFrontGeom[bestAxis];
961	*backGeom = nBackGeom[bestAxis];
962
963	// and delete other geometry
964	delete nFrontGeom[(bestAxis + 1) % 3];
965	delete nBackGeom[(bestAxis + 2) % 3];
966
967	//-- split plane
968	Vector3 normal(0,0,0); normal[bestAxis] = 1;
969	plane = Plane3(normal, nPosition[bestAxis]);
970
971	return nCostRatio[bestAxis];
972	}
973
974
975	float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
976	const AxisAlignedBox3 &box,
977	const int axis,
978	const float &position,
979	float &pFront,
980	float &pBack) const
981	{
982	int pvsTotal = 0;
983	int pvsFront = 0;
984	int pvsBack = 0;
985
986	// create unique ids for pvs heuristics
987	GenerateUniqueIdsForPvs();
988
989	const int pvsSize = data.mPvs;
990
991	// this is the main ray classification loop!
992	for(RayInfoContainer::iterator ri = data.mRays->begin();
993	ri != data.mRays->end(); ++ ri)
994	{
995	if (!(*ri).mRay->IsActive())
996	continue;
997
998	// determine the side of this ray with respect to the plane
999	float t;
1000	int side = (*ri).ComputeRayIntersection(axis, position, t);
1001
1002	AddObjToPvs((*ri).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
1003	AddObjToPvs((*ri).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
1004	}
1005
1006	//-- pvs heuristics
1007	float pOverall;
1008
1009	// -- simplified computation for mid split
1010
1011
1012	pOverall = data.mProbability;
1013
1014	if (!mUseAreaForPvs)
1015	{ // volume
1016	pBack = pFront = pOverall * 0.5f;
1017
1018	#if 0
1019	// box length substitute for probability
1020	const float minBox = box.Min(axis);
1021	const float maxBox = box.Max(axis);
1022
1023	pBack = position - minBox;
1024	pFront = maxBox - position;
1025	pOverall = maxBox - minBox;
1026	#endif
1027	}
1028	else //-- area substitute for probability
1029	{
1030	const int axis2 = (axis + 1) % 3;
1031	const int axis3 = (axis + 2) % 3;
1032
1033	const float faceArea =
1034	(box.Max(axis2) - box.Min(axis2)) *
1035	(box.Max(axis3) - box.Min(axis3));
1036
1037	pBack = pFront = pOverall * 0.5f + faceArea;
1038	}
1039
1040	//Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1041	//Debug << pFront << " " << pBack << " " << pOverall << endl;
1042
1043	const float newCost = pvsBack * pBack + pvsFront * pFront;
1044	const float oldCost = (float)pvsSize * pOverall;
1045
1046	return (mCtDivCi + newCost) / oldCost;
1047	}
1048
1049
1050
1051	bool VspBspTree::SelectPlane(Plane3 &bestPlane,
1052	BspLeaf *leaf,
1053	VspBspTraversalData &data,
1054	VspBspTraversalData &frontData,
1055	VspBspTraversalData &backData)
1056	{
1057	// simplest strategy: just take next polygon
1058	if (mSplitPlaneStrategy & RANDOM_POLYGON)
1059	{
1060	if (!data.mPolygons->empty())
1061	{
1062	const int randIdx =
1063	(int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
1064	Polygon3 nextPoly = (data.mPolygons)[randIdx];
1065
1066	bestPlane = nextPoly->GetSupportingPlane();
1067	return true;
1068	}
1069	}
1070
1071	//-- use heuristics to find appropriate plane
1072
1073	// intermediate plane
1074	Plane3 plane;
1075	float lowestCost = MAX_FLOAT;
1076
1077	// decides if the first few splits should be only axisAligned
1078	const bool onlyAxisAligned =
1079	(mSplitPlaneStrategy & AXIS_ALIGNED) &&
1080	((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
1081	((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
1082
1083	const int limit = onlyAxisAligned ? 0 :
1084	Min((int)data.mPolygons->size(), mMaxPolyCandidates);
1085
1086	float candidateCost;
1087
1088	int maxIdx = (int)data.mPolygons->size();
1089
1090	for (int i = 0; i < limit; ++ i)
1091	{
1092	//-- assure that no index is taken twice
1093	const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
1094	Polygon3 poly = (data.mPolygons)[candidateIdx];
1095
1096	// swap candidate to the end to avoid testing same plane
1097	std::swap((data.mPolygons)[maxIdx], (data.mPolygons)[candidateIdx]);
1098	//Polygon3 poly = (data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
1099
1100	// evaluate current candidate
1101	BspNodeGeometry fGeom, bGeom;
1102	float fArea, bArea;
1103	plane = poly->GetSupportingPlane();
1104	candidateCost = SplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
1105
1106	if (candidateCost < lowestCost)
1107	{
1108	bestPlane = plane;
1109	lowestCost = candidateCost;
1110	}
1111	}
1112
1113	//-- evaluate axis aligned splits
1114	int axis;
1115	BspNodeGeometry fGeom, bGeom;
1116	float pFront, pBack;
1117
1118	candidateCost = SelectAxisAlignedPlane(plane, data, axis,
1119	&fGeom, &bGeom,
1120	pFront, pBack,
1121	onlyAxisAligned);
1122
1123	if (candidateCost < lowestCost)
1124	{
1125	bestPlane = plane;
1126	lowestCost = candidateCost;
1127
1128	// assign already computed values
1129	// we can do this because we always save the
1130	// computed values from the axis aligned splits
1131
1132	frontData.mGeometry = fGeom;
1133	backData.mGeometry = bGeom;
1134
1135	frontData.mProbability = pFront;
1136	backData.mProbability = pBack;
1137
1138	//! error also computed if cost ratio is missed
1139	++ mStat.splits[axis];
1140	}
1141	else
1142	{
1143	DEL_PTR(fGeom);
1144	DEL_PTR(bGeom);
1145	}
1146
1147	#ifdef _DEBUG
1148	Debug << "plane lowest cost: " << lowestCost << endl;
1149	#endif
1150
1151	// cost ratio miss
1152	if (lowestCost > mTermMaxCostRatio)
1153	return false;
1154
1155	return true;
1156	}
1157
1158
1159	Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
1160	{
1161	const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1162
1163	const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
1164	const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
1165
1166	const Vector3 pt = (maxPt + minPt) * 0.5;
1167	const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
1168
1169	return Plane3(normal, pt);
1170	}
1171
1172
1173	Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
1174	{
1175	Vector3 pt[3];
1176
1177	int idx[3];
1178	int cmaxT = 0;
1179	int cminT = 0;
1180	bool chooseMin = false;
1181
1182	for (int j = 0; j < 3; ++ j)
1183	{
1184	idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
1185
1186	if (idx[j] >= (int)rays.size())
1187	{
1188	idx[j] -= (int)rays.size();
1189
1190	chooseMin = (cminT < 2);
1191	}
1192	else
1193	chooseMin = (cmaxT < 2);
1194
1195	RayInfo rayInf = rays[idx[j]];
1196	pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
1197	}
1198
1199	return Plane3(pt[0], pt[1], pt[2]);
1200	}
1201
1202	Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
1203	{
1204	Vector3 pt[3];
1205
1206	int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1207	int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1208
1209	// check if rays different
1210	if (idx1 == idx2)
1211	idx2 = (idx2 + 1) % (int)rays.size();
1212
1213	const RayInfo ray1 = rays[idx1];
1214	const RayInfo ray2 = rays[idx2];
1215
1216	// normal vector of the plane parallel to both lines
1217	const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
1218
1219	// vector from line 1 to line 2
1220	const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
1221
1222	// project vector on normal to get distance
1223	const float dist = DotProd(vd, norm);
1224
1225	// point on plane lies halfway between the two planes
1226	const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
1227
1228	return Plane3(norm, planePt);
1229	}
1230
1231
1232	inline void VspBspTree::GenerateUniqueIdsForPvs()
1233	{
1234	Intersectable::NewMail(); sBackId = ViewCell::sMailId;
1235	Intersectable::NewMail(); sFrontId = ViewCell::sMailId;
1236	Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;
1237	}
1238
1239
1240	float VspBspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1241	const VspBspTraversalData &data,
1242	BspNodeGeometry &geomFront,
1243	BspNodeGeometry &geomBack,
1244	float &pFront,
1245	float &pBack) const
1246	{
1247	float cost = 0;
1248
1249	float sumBalancedRays = 0;
1250	float sumRaySplits = 0;
1251
1252	int pvsFront = 0;
1253	int pvsBack = 0;
1254
1255	// probability that view point lies in back / front node
1256	float pOverall = 0;
1257	pFront = 0;
1258	pBack = 0;
1259
1260	int raysFront = 0;
1261	int raysBack = 0;
1262	int totalPvs = 0;
1263
1264	int limit;
1265	bool useRand;
1266
1267	// choose test rays randomly if too much
1268	if ((int)data.mRays->size() > mMaxTests)
1269	{
1270	useRand = true;
1271	limit = mMaxTests;
1272	}
1273	else
1274	{
1275	useRand = false;
1276	limit = (int)data.mRays->size();
1277	}
1278
1279	for (int i = 0; i < limit; ++ i)
1280	{
1281	const int testIdx = useRand ?
1282	(int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
1283	RayInfo rayInf = (*data.mRays)[testIdx];
1284
1285	float t;
1286	VssRay *ray = rayInf.mRay;
1287	const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
1288
1289	if (cf >= 0)
1290	++ raysFront;
1291	if (cf <= 0)
1292	++ raysBack;
1293
1294	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1295	{
1296	sumBalancedRays += cf;
1297	}
1298
1299	if (mSplitPlaneStrategy & BALANCED_RAYS)
1300	{
1301	if (cf == 0)
1302	++ sumRaySplits;
1303	}
1304
1305	if (mSplitPlaneStrategy & PVS)
1306	{
1307	// find front and back pvs for origing and termination object
1308	AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
1309	AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
1310	}
1311	}
1312
1313	const float raysSize = (float)data.mRays->size() + Limits::Small;
1314
1315	if (mSplitPlaneStrategy & PVS)
1316	{
1317	// create unique ids for pvs heuristics
1318	GenerateUniqueIdsForPvs();
1319
1320	// construct child geometry with regard to the candidate split plane
1321	data.mGeometry->SplitGeometry(geomFront,
1322	geomBack,
1323	candidatePlane,
1324	mBox,
1325	mEpsilon);
1326
1327	pOverall = data.mProbability;
1328
1329	if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
1330	{
1331	pFront = geomFront.GetVolume();
1332	pBack = pOverall - geomFront.GetVolume();
1333	}
1334	else
1335	{
1336	pFront = geomFront.GetArea();
1337	pBack = geomBack.GetArea();
1338	}
1339	}
1340
1341
1342	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1343	cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
1344
1345	if (mSplitPlaneStrategy & BALANCED_RAYS)
1346	cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
1347
1348	// pvs criterium
1349	if (mSplitPlaneStrategy & PVS)
1350	{
1351	const float oldCost = pOverall * (float)totalPvs + Limits::Small;
1352	cost += mPvsFactor * (pvsFront * pFront + pvsBack * pBack) / oldCost;
1353	}
1354
1355	#ifdef _DEBUG
1356	Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
1357	<< " frontpvs: " << pvsFront << " pFront: " << pFront
1358	<< " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
1359	#endif
1360
1361	// normalize cost by sum of linear factors
1362	return cost / (float)mCostNormalizer;
1363	}
1364
1365
1366	void VspBspTree::AddObjToPvs(Intersectable *obj,
1367	const int cf,
1368	int &frontPvs,
1369	int &backPvs,
1370	int &totalPvs) const
1371	{
1372	if (!obj)
1373	return;
1374
1375	if ((obj->mMailbox != sFrontId) &&
1376	(obj->mMailbox != sBackId) &&
1377	(obj->mMailbox != sFrontAndBackId))
1378	{
1379	++ totalPvs;
1380	}
1381
1382	// TODO: does this really belong to no pvs?
1383	//if (cf == Ray::COINCIDENT) return;
1384
1385	// object belongs to both PVS
1386	if (cf >= 0)
1387	{
1388	if ((obj->mMailbox != sFrontId) &&
1389	(obj->mMailbox != sFrontAndBackId))
1390	{
1391	++ frontPvs;
1392
1393	if (obj->mMailbox == sBackId)
1394	obj->mMailbox = sFrontAndBackId;
1395	else
1396	obj->mMailbox = sFrontId;
1397	}
1398	}
1399
1400	if (cf <= 0)
1401	{
1402	if ((obj->mMailbox != sBackId) &&
1403	(obj->mMailbox != sFrontAndBackId))
1404	{
1405	++ backPvs;
1406
1407	if (obj->mMailbox == sFrontId)
1408	obj->mMailbox = sFrontAndBackId;
1409	else
1410	obj->mMailbox = sBackId;
1411	}
1412	}
1413	}
1414
1415
1416	void VspBspTree::CollectLeaves(vector<BspLeaf *> &leaves,
1417	const bool onlyUnmailed,
1418	const int maxPvsSize) const
1419	{
1420	stack<BspNode *> nodeStack;
1421	nodeStack.push(mRoot);
1422
1423	while (!nodeStack.empty())
1424	{
1425	BspNode *node = nodeStack.top();
1426	nodeStack.pop();
1427
1428	if (node->IsLeaf())
1429	{
1430	// test if this leaf is in valid view space
1431	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
1432	if (leaf->TreeValid() &&
1433	(!onlyUnmailed \|\| !leaf->Mailed()) &&
1434	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
1435	{
1436	leaves.push_back(leaf);
1437	}
1438	}
1439	else
1440	{
1441	BspInterior interior = dynamic_cast<BspInterior >(node);
1442
1443	nodeStack.push(interior->GetBack());
1444	nodeStack.push(interior->GetFront());
1445	}
1446	}
1447	}
1448
1449
1450	AxisAlignedBox3 VspBspTree::GetBoundingBox() const
1451	{
1452	return mBox;
1453	}
1454
1455
1456	BspNode *VspBspTree::GetRoot() const
1457	{
1458	return mRoot;
1459	}
1460
1461
1462	void VspBspTree::EvaluateLeafStats(const VspBspTraversalData &data)
1463	{
1464	// the node became a leaf -> evaluate stats for leafs
1465	BspLeaf leaf = dynamic_cast<BspLeaf >(data.mNode);
1466
1467	// store maximal and minimal depth
1468	if (data.mDepth > mStat.maxDepth)
1469	mStat.maxDepth = data.mDepth;
1470
1471	if (data.mPvs > mStat.maxPvs)
1472	mStat.maxPvs = data.mPvs;
1473
1474	if (data.mDepth < mStat.minDepth)
1475	mStat.minDepth = data.mDepth;
1476
1477	if (data.mDepth >= mTermMaxDepth)
1478	++ mStat.maxDepthNodes;
1479	// accumulate rays to compute rays / leaf
1480	mStat.accumRays += (int)data.mRays->size();
1481
1482	if (data.mPvs < mTermMinPvs)
1483	++ mStat.minPvsNodes;
1484
1485	if ((int)data.mRays->size() < mTermMinRays)
1486	++ mStat.minRaysNodes;
1487
1488	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1489	++ mStat.maxRayContribNodes;
1490
1491	if (data.mProbability <= mTermMinProbability)
1492	++ mStat.minProbabilityNodes;
1493
1494	// accumulate depth to compute average depth
1495	mStat.accumDepth += data.mDepth;
1496
1497	#ifdef _DEBUG
1498	Debug << "BSP stats: "
1499	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1500	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1501	<< "Area: " << data.mArea << " (min: " << mTermMinArea << "), "
1502	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1503	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
1504	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1505	#endif
1506	}
1507
1508	int VspBspTree::CastRay(Ray &ray)
1509	{
1510	int hits = 0;
1511
1512	stack<BspRayTraversalData> tStack;
1513
1514	float maxt, mint;
1515
1516	if (!mBox.GetRaySegment(ray, mint, maxt))
1517	return 0;
1518
1519	Intersectable::NewMail();
1520
1521	Vector3 entp = ray.Extrap(mint);
1522	Vector3 extp = ray.Extrap(maxt);
1523
1524	BspNode *node = mRoot;
1525	BspNode *farChild = NULL;
1526
1527	while (1)
1528	{
1529	if (!node->IsLeaf())
1530	{
1531	BspInterior in = dynamic_cast<BspInterior >(node);
1532
1533	Plane3 splitPlane = in->GetPlane();
1534	const int entSide = splitPlane.Side(entp);
1535	const int extSide = splitPlane.Side(extp);
1536
1537	if (entSide < 0)
1538	{
1539	node = in->GetBack();
1540
1541	if(extSide <= 0) // plane does not split ray => no far child
1542	continue;
1543
1544	farChild = in->GetFront(); // plane splits ray
1545
1546	} else if (entSide > 0)
1547	{
1548	node = in->GetFront();
1549
1550	if (extSide >= 0) // plane does not split ray => no far child
1551	continue;
1552
1553	farChild = in->GetBack(); // plane splits ray
1554	}
1555	else // ray and plane are coincident
1556	{
1557	// WHAT TO DO IN THIS CASE ?
1558	//break;
1559	node = in->GetFront();
1560	continue;
1561	}
1562
1563	// push data for far child
1564	tStack.push(BspRayTraversalData(farChild, extp, maxt));
1565
1566	// find intersection of ray segment with plane
1567	float t;
1568	extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
1569	maxt *= t;
1570
1571	} else // reached leaf => intersection with view cell
1572	{
1573	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
1574
1575	if (!leaf->GetViewCell()->Mailed())
1576	{
1577	//ray.bspIntersections.push_back(Ray::VspBspIntersection(maxt, leaf));
1578	leaf->GetViewCell()->Mail();
1579	++ hits;
1580	}
1581
1582	//-- fetch the next far child from the stack
1583	if (tStack.empty())
1584	break;
1585
1586	entp = extp;
1587	mint = maxt; // NOTE: need this?
1588
1589	if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
1590	break;
1591
1592	BspRayTraversalData &s = tStack.top();
1593
1594	node = s.mNode;
1595	extp = s.mExitPoint;
1596	maxt = s.mMaxT;
1597
1598	tStack.pop();
1599	}
1600	}
1601
1602	return hits;
1603	}
1604
1605
1606	void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
1607	{
1608	ViewCell::NewMail();
1609
1610	CollectViewCells(mRoot, onlyValid, viewCells, true);
1611	}
1612
1613
1614	void VspBspTree::ValidateTree()
1615	{
1616	stack<BspNode *> nodeStack;
1617
1618	if (!mRoot)
1619	return;
1620
1621	nodeStack.push(mRoot);
1622
1623	const bool addToUnbounded = false;
1624
1625	while (!nodeStack.empty())
1626	{
1627	BspNode *node = nodeStack.top();
1628	nodeStack.pop();
1629
1630	if (node->IsLeaf())
1631	{
1632	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
1633
1634	if (!addToUnbounded && node->TreeValid())
1635	{
1636	BspViewCell viewCell = dynamic_cast<BspLeaf >(node)->GetViewCell();
1637
1638	if (!mViewCellsManager->CheckValid(viewCell))
1639	{
1640	vector<BspLeaf *>::const_iterator it, it_end = viewCell->mLeaves.end();
1641	for (it = viewCell->mLeaves.begin();it != it_end; ++ it)
1642	{
1643	BspLeaf l = it;
1644
1645	l->SetTreeValid(false);
1646	PropagateUpValidity(l);
1647
1648	if (addToUnbounded)
1649	l->SetViewCell(GetOrCreateOutOfBoundsCell());
1650
1651	++ mStat.invalidLeaves;
1652	}
1653
1654	// add to unbounded view cell or set to invalid
1655	if (addToUnbounded)
1656	{
1657	GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
1658	DEL_PTR(viewCell);
1659	}
1660	else
1661	{
1662	viewCell->SetValid(false);
1663	}
1664	}
1665	}
1666	}
1667	else
1668	{
1669	BspInterior interior = dynamic_cast<BspInterior >(node);
1670
1671	nodeStack.push(interior->GetFront());
1672	nodeStack.push(interior->GetBack());
1673	}
1674	}
1675	}
1676
1677
1678	void VspBspTree::CollectViewCells(BspNode *root,
1679	bool onlyValid,
1680	ViewCellContainer &viewCells,
1681	bool onlyUnmailed) const
1682	{
1683	stack<BspNode *> nodeStack;
1684
1685	if (!root)
1686	return;
1687
1688	nodeStack.push(root);
1689
1690	while (!nodeStack.empty())
1691	{
1692	BspNode *node = nodeStack.top();
1693	nodeStack.pop();
1694
1695	if (node->IsLeaf())
1696	{
1697	if (!onlyValid \|\|node->TreeValid())
1698	{
1699	ViewCell viewCell = dynamic_cast<BspLeaf >(node)->GetViewCell();
1700
1701	if (!onlyUnmailed \|\| !viewCell->Mailed())
1702	{
1703	viewCell->Mail();
1704	viewCells.push_back(viewCell);
1705	}
1706	}
1707	}
1708	else
1709	{
1710	BspInterior interior = dynamic_cast<BspInterior >(node);
1711
1712	nodeStack.push(interior->GetFront());
1713	nodeStack.push(interior->GetBack());
1714	}
1715	}
1716	}
1717
1718
1719	float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
1720	{
1721	float len = 0;
1722
1723	RayInfoContainer::const_iterator it, it_end = rays.end();
1724
1725	for (it = rays.begin(); it != it_end; ++ it)
1726	len += (*it).SegmentLength();
1727
1728	return len;
1729	}
1730
1731
1732	int VspBspTree::SplitRays(const Plane3 &plane,
1733	RayInfoContainer &rays,
1734	RayInfoContainer &frontRays,
1735	RayInfoContainer &backRays)
1736	{
1737	int splits = 0;
1738
1739	while (!rays.empty())
1740	{
1741	RayInfo bRay = rays.back();
1742	rays.pop_back();
1743
1744	VssRay *ray = bRay.mRay;
1745	float t;
1746
1747	// get classification and receive new t
1748	const int cf = bRay.ComputeRayIntersection(plane, t);
1749
1750	switch (cf)
1751	{
1752	case -1:
1753	backRays.push_back(bRay);
1754	break;
1755	case 1:
1756	frontRays.push_back(bRay);
1757	break;
1758	case 0:
1759	{
1760	//-- split ray
1761	//-- test if start point behind or in front of plane
1762	const int side = plane.Side(bRay.ExtrapOrigin());
1763
1764	if (side <= 0)
1765	{
1766	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1767	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1768	}
1769	else
1770	{
1771	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1772	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1773	}
1774	}
1775	break;
1776	default:
1777	Debug << "Should not come here" << endl;
1778	break;
1779	}
1780	}
1781
1782	return splits;
1783	}
1784
1785
1786	void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
1787	{
1788	BspNode *lastNode;
1789
1790	do
1791	{
1792	lastNode = n;
1793
1794	// want to get planes defining geometry of this node => don't take
1795	// split plane of node itself
1796	n = n->GetParent();
1797
1798	if (n)
1799	{
1800	BspInterior interior = dynamic_cast<BspInterior >(n);
1801	Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
1802
1803	if (interior->GetFront() != lastNode)
1804	halfSpace.ReverseOrientation();
1805
1806	halfSpaces.push_back(halfSpace);
1807	}
1808	}
1809	while (n);
1810	}
1811
1812
1813	void VspBspTree::ConstructGeometry(BspNode *n,
1814	BspNodeGeometry &geom) const
1815	{
1816	vector<Plane3> halfSpaces;
1817	ExtractHalfSpaces(n, halfSpaces);
1818
1819	PolygonContainer candidatePolys;
1820
1821	// bounded planes are added to the polygons (reverse polygons
1822	// as they have to be outfacing
1823	for (int i = 0; i < (int)halfSpaces.size(); ++ i)
1824	{
1825	Polygon3 *p = GetBoundingBox().CrossSection(halfSpaces[i]);
1826
1827	if (p->Valid(mEpsilon))
1828	{
1829	candidatePolys.push_back(p->CreateReversePolygon());
1830	DEL_PTR(p);
1831	}
1832	}
1833
1834	// add faces of bounding box (also could be faces of the cell)
1835	for (int i = 0; i < 6; ++ i)
1836	{
1837	VertexContainer vertices;
1838
1839	for (int j = 0; j < 4; ++ j)
1840	vertices.push_back(mBox.GetFace(i).mVertices[j]);
1841
1842	candidatePolys.push_back(new Polygon3(vertices));
1843	}
1844
1845	for (int i = 0; i < (int)candidatePolys.size(); ++ i)
1846	{
1847	// polygon is split by all other planes
1848	for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
1849	{
1850	if (i == j) // polygon and plane are coincident
1851	continue;
1852
1853	VertexContainer splitPts;
1854	Polygon3 frontPoly, backPoly;
1855
1856	const int cf =
1857	candidatePolys[i]->ClassifyPlane(halfSpaces[j],
1858	mEpsilon);
1859
1860	switch (cf)
1861	{
1862	case Polygon3::SPLIT:
1863	frontPoly = new Polygon3();
1864	backPoly = new Polygon3();
1865
1866	candidatePolys[i]->Split(halfSpaces[j],
1867	*frontPoly,
1868	*backPoly,
1869	mEpsilon);
1870
1871	DEL_PTR(candidatePolys[i]);
1872
1873	if (frontPoly->Valid(mEpsilon))
1874	candidatePolys[i] = frontPoly;
1875	else
1876	DEL_PTR(frontPoly);
1877
1878	DEL_PTR(backPoly);
1879	break;
1880	case Polygon3::BACK_SIDE:
1881	DEL_PTR(candidatePolys[i]);
1882	break;
1883	// just take polygon as it is
1884	case Polygon3::FRONT_SIDE:
1885	case Polygon3::COINCIDENT:
1886	default:
1887	break;
1888	}
1889	}
1890
1891	if (candidatePolys[i])
1892	geom.mPolys.push_back(candidatePolys[i]);
1893	}
1894	}
1895
1896
1897	void VspBspTree::ConstructGeometry(BspViewCell *vc,
1898	BspNodeGeometry &vcGeom) const
1899	{
1900	vector<BspLeaf *> leaves = vc->mLeaves;
1901	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
1902
1903	for (it = leaves.begin(); it != it_end; ++ it)
1904	ConstructGeometry(*it, vcGeom);
1905	}
1906
1907
1908	typedef pair<BspNode , BspNodeGeometry > bspNodePair;
1909
1910	int VspBspTree::FindNeighbors(BspNode n, vector<BspLeaf > &neighbors,
1911	const bool onlyUnmailed) const
1912	{
1913	stack<bspNodePair> nodeStack;
1914
1915	BspNodeGeometry nodeGeom;
1916	ConstructGeometry(n, nodeGeom);
1917
1918	// split planes from the root to this node
1919	// needed to verify that we found neighbor leaf
1920	vector<Plane3> halfSpaces;
1921	ExtractHalfSpaces(n, halfSpaces);
1922
1923
1924	BspNodeGeometry *rgeom = new BspNodeGeometry();
1925	ConstructGeometry(mRoot, *rgeom);
1926
1927	nodeStack.push(bspNodePair(mRoot, rgeom));
1928
1929
1930	while (!nodeStack.empty())
1931	{
1932	BspNode *node = nodeStack.top().first;
1933	BspNodeGeometry *geom = nodeStack.top().second;
1934
1935	nodeStack.pop();
1936
1937	bool isAdjacent = true;
1938
1939
1940	#if 1
1941	// test all planes of current node if still adjacent
1942	for (int i = 0; (i < halfSpaces.size()) && isAdjacent && (node != n); ++ i)
1943	{
1944	const int cf =
1945	Polygon3::ClassifyPlane(geom->mPolys,
1946	halfSpaces[i],
1947	mEpsilon);
1948
1949	if (cf == Polygon3::BACK_SIDE)
1950	{
1951	isAdjacent = false;
1952	}
1953	}
1954	#else
1955	// test all planes of current node if still adjacent
1956	for (int i = 0; i < nodeGeom.size()) && isAdjacent && (node != n); ++ i)
1957	{
1958	Polygon3 *poly = nodeGeom->mPolys[i];
1959
1960	const int cf =
1961	Polygon3::ClassifyPlane(geom->mPolys,
1962	poly->GetSupportingPlane(),
1963	mEpsilon);
1964
1965	if (cf == Polygon3::BACK_SIDE)
1966	{
1967	isAdjacent = false;
1968	}
1969	}
1970	#endif
1971	if (isAdjacent)
1972	{
1973
1974	if (node->IsLeaf())
1975	{
1976	// test if this leaf is in valid view space
1977	if (node->TreeValid() &&
1978	node != n &&
1979	(!onlyUnmailed \|\| !node->Mailed()))
1980	{
1981	// neighbor was found
1982	neighbors.push_back(dynamic_cast<BspLeaf *>(node));
1983	}
1984	}
1985	else
1986	{
1987	BspInterior interior = dynamic_cast<BspInterior >(node);
1988
1989	const int cf = Polygon3::ClassifyPlane(nodeGeom.mPolys,
1990	interior->GetPlane(),
1991	mEpsilon);
1992
1993	BspNode *front = interior->GetFront();
1994	BspNode *back = interior->GetBack();
1995
1996	BspNodeGeometry *fGeom = new BspNodeGeometry();
1997	BspNodeGeometry *bGeom = new BspNodeGeometry();
1998
1999	geom->SplitGeometry(*fGeom,
2000	*bGeom,
2001	interior->GetPlane(),
2002	mBox,
2003	mEpsilon);
2004
2005	if (cf == Polygon3::FRONT_SIDE)
2006	{
2007	nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
2008	DEL_PTR(bGeom);
2009	}
2010	else
2011	{
2012	if (cf == Polygon3::BACK_SIDE)
2013	{
2014	nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
2015	DEL_PTR(fGeom);
2016	}
2017	else
2018	{ // random decision
2019	nodeStack.push(bspNodePair(front, fGeom));
2020	nodeStack.push(bspNodePair(back, bGeom));
2021	}
2022	}
2023	}
2024	}
2025
2026	DEL_PTR(geom);
2027	}
2028
2029	return (int)neighbors.size();
2030	}
2031
2032
2033	BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace)
2034	{
2035	stack<BspNode *> nodeStack;
2036	nodeStack.push(mRoot);
2037
2038	int mask = rand();
2039
2040	while (!nodeStack.empty())
2041	{
2042	BspNode *node = nodeStack.top();
2043	nodeStack.pop();
2044
2045	if (node->IsLeaf())
2046	{
2047	return dynamic_cast<BspLeaf *>(node);
2048	}
2049	else
2050	{
2051	BspInterior interior = dynamic_cast<BspInterior >(node);
2052	BspNode *next;
2053	BspNodeGeometry geom;
2054
2055	// todo: not very efficient: constructs full cell everytime
2056	ConstructGeometry(interior, geom);
2057
2058	const int cf =
2059	Polygon3::ClassifyPlane(geom.mPolys, halfspace, mEpsilon);
2060
2061	if (cf == Polygon3::BACK_SIDE)
2062	next = interior->GetFront();
2063	else
2064	if (cf == Polygon3::FRONT_SIDE)
2065	next = interior->GetFront();
2066	else
2067	{
2068	// random decision
2069	if (mask & 1)
2070	next = interior->GetBack();
2071	else
2072	next = interior->GetFront();
2073	mask = mask >> 1;
2074	}
2075
2076	nodeStack.push(next);
2077	}
2078	}
2079
2080	return NULL;
2081	}
2082
2083	BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed)
2084	{
2085	stack<BspNode *> nodeStack;
2086
2087	nodeStack.push(mRoot);
2088
2089	int mask = rand();
2090
2091	while (!nodeStack.empty())
2092	{
2093	BspNode *node = nodeStack.top();
2094	nodeStack.pop();
2095
2096	if (node->IsLeaf())
2097	{
2098	if ( (!onlyUnmailed \|\| !node->Mailed()) )
2099	return dynamic_cast<BspLeaf *>(node);
2100	}
2101	else
2102	{
2103	BspInterior interior = dynamic_cast<BspInterior >(node);
2104
2105	// random decision
2106	if (mask & 1)
2107	nodeStack.push(interior->GetBack());
2108	else
2109	nodeStack.push(interior->GetFront());
2110
2111	mask = mask >> 1;
2112	}
2113	}
2114
2115	return NULL;
2116	}
2117
2118	int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const
2119	{
2120	int pvsSize = 0;
2121
2122	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2123
2124	Intersectable::NewMail();
2125
2126	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2127	{
2128	VssRay ray = (rit).mRay;
2129
2130	if (ray->mOriginObject)
2131	{
2132	if (!ray->mOriginObject->Mailed())
2133	{
2134	ray->mOriginObject->Mail();
2135	++ pvsSize;
2136	}
2137	}
2138	if (ray->mTerminationObject)
2139	{
2140	if (!ray->mTerminationObject->Mailed())
2141	{
2142	ray->mTerminationObject->Mail();
2143	++ pvsSize;
2144	}
2145	}
2146	}
2147
2148	return pvsSize;
2149	}
2150
2151	float VspBspTree::GetEpsilon() const
2152	{
2153	return mEpsilon;
2154	}
2155
2156
2157	int VspBspTree::SplitPolygons(const Plane3 &plane,
2158	PolygonContainer &polys,
2159	PolygonContainer &frontPolys,
2160	PolygonContainer &backPolys,
2161	PolygonContainer &coincident) const
2162	{
2163	int splits = 0;
2164
2165	while (!polys.empty())
2166	{
2167	Polygon3 *poly = polys.back();
2168	polys.pop_back();
2169
2170	// classify polygon
2171	const int cf = poly->ClassifyPlane(plane, mEpsilon);
2172
2173	switch (cf)
2174	{
2175	case Polygon3::COINCIDENT:
2176	coincident.push_back(poly);
2177	break;
2178	case Polygon3::FRONT_SIDE:
2179	frontPolys.push_back(poly);
2180	break;
2181	case Polygon3::BACK_SIDE:
2182	backPolys.push_back(poly);
2183	break;
2184	case Polygon3::SPLIT:
2185	backPolys.push_back(poly);
2186	frontPolys.push_back(poly);
2187	++ splits;
2188	break;
2189	default:
2190	Debug << "SHOULD NEVER COME HERE\n";
2191	break;
2192	}
2193	}
2194
2195	return splits;
2196	}
2197
2198
2199	int VspBspTree::CastLineSegment(const Vector3 &origin,
2200	const Vector3 &termination,
2201	vector<ViewCell *> &viewcells)
2202	{
2203	int hits = 0;
2204	stack<BspRayTraversalData> tStack;
2205
2206	float mint = 0.0f, maxt = 1.0f;
2207
2208	Intersectable::NewMail();
2209
2210	Vector3 entp = origin;
2211	Vector3 extp = termination;
2212
2213	BspNode *node = mRoot;
2214	BspNode *farChild = NULL;
2215
2216	float t;
2217	while (1)
2218	{
2219	if (!node->IsLeaf())
2220	{
2221	BspInterior in = dynamic_cast<BspInterior >(node);
2222
2223	Plane3 splitPlane = in->GetPlane();
2224
2225	const int entSide = splitPlane.Side(entp);
2226	const int extSide = splitPlane.Side(extp);
2227
2228	if (entSide < 0)
2229	{
2230	node = in->GetBack();
2231	// plane does not split ray => no far child
2232	if (extSide <= 0)
2233	continue;
2234
2235	farChild = in->GetFront(); // plane splits ray
2236	}
2237	else if (entSide > 0)
2238	{
2239	node = in->GetFront();
2240
2241	if (extSide >= 0) // plane does not split ray => no far child
2242	continue;
2243
2244	farChild = in->GetBack(); // plane splits ray
2245	}
2246	else // ray end point on plane
2247	{ // NOTE: what to do if ray is coincident with plane?
2248	if (extSide < 0)
2249	node = in->GetBack();
2250	else
2251	node = in->GetFront();
2252
2253	continue; // no far child
2254	}
2255
2256	// push data for far child
2257	tStack.push(BspRayTraversalData(farChild, extp));
2258
2259	// find intersection of ray segment with plane
2260	extp = splitPlane.FindIntersection(origin, extp, &t);
2261	}
2262	else
2263	{
2264	// reached leaf => intersection with view cell
2265	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2266
2267	if (!leaf->GetViewCell()->Mailed())
2268	{
2269	viewcells.push_back(leaf->GetViewCell());
2270	leaf->GetViewCell()->Mail();
2271	++ hits;
2272	}
2273
2274	//-- fetch the next far child from the stack
2275	if (tStack.empty())
2276	break;
2277
2278	entp = extp;
2279
2280	BspRayTraversalData &s = tStack.top();
2281
2282	node = s.mNode;
2283	extp = s.mExitPoint;
2284
2285	tStack.pop();
2286	}
2287	}
2288
2289	return hits;
2290	}
2291
2292	int VspBspTree::TreeDistance(BspNode n1, BspNode n2) const
2293	{
2294	std::deque<BspNode *> path1;
2295	BspNode *p1 = n1;
2296
2297	// create path from node 1 to root
2298	while (p1)
2299	{
2300	if (p1 == n2) // second node on path
2301	return (int)path1.size();
2302
2303	path1.push_front(p1);
2304	p1 = p1->GetParent();
2305	}
2306
2307	int depth = n2->GetDepth();
2308	int d = depth;
2309
2310	BspNode *p2 = n2;
2311
2312	// compare with same depth
2313	while (1)
2314	{
2315	if ((d < (int)path1.size()) && (p2 == path1[d]))
2316	return (depth - d) + ((int)path1.size() - 1 - d);
2317
2318	-- d;
2319	p2 = p2->GetParent();
2320	}
2321
2322	return 0; // never come here
2323	}
2324
2325	BspNode VspBspTree::CollapseTree(BspNode node, int &collapsed)
2326	{
2327	if (node->IsLeaf())
2328	return node;
2329
2330	BspInterior interior = dynamic_cast<BspInterior >(node);
2331
2332	BspNode *front = CollapseTree(interior->GetFront(), collapsed);
2333	BspNode *back = CollapseTree(interior->GetBack(), collapsed);
2334
2335	if (front->IsLeaf() && back->IsLeaf())
2336	{
2337	BspLeaf frontLeaf = dynamic_cast<BspLeaf >(front);
2338	BspLeaf backLeaf = dynamic_cast<BspLeaf >(back);
2339
2340	//-- collapse tree
2341	if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
2342	{
2343	BspViewCell *vc = frontLeaf->GetViewCell();
2344
2345	BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
2346	leaf->SetTreeValid(frontLeaf->TreeValid());
2347
2348	// replace a link from node's parent
2349	if (leaf->GetParent())
2350	leaf->GetParent()->ReplaceChildLink(node, leaf);
2351	else
2352	mRoot = leaf;
2353
2354	++ collapsed;
2355	delete interior;
2356
2357	return leaf;
2358	}
2359	}
2360
2361	return node;
2362	}
2363
2364
2365	int VspBspTree::CollapseTree()
2366	{
2367	int collapsed = 0;
2368
2369	(void)CollapseTree(mRoot, collapsed);
2370
2371	// revalidate leaves
2372	RepairViewCellsLeafLists();
2373
2374	return collapsed;
2375	}
2376
2377
2378	void VspBspTree::RepairViewCellsLeafLists()
2379	{
2380	// list not valid anymore => clear
2381	stack<BspNode *> nodeStack;
2382	nodeStack.push(mRoot);
2383
2384	ViewCell::NewMail();
2385
2386	while (!nodeStack.empty())
2387	{
2388	BspNode *node = nodeStack.top();
2389	nodeStack.pop();
2390
2391	if (node->IsLeaf())
2392	{
2393	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2394
2395	BspViewCell *viewCell = leaf->GetViewCell();
2396
2397	if (!viewCell->Mailed())
2398	{
2399	viewCell->mLeaves.clear();
2400	viewCell->Mail();
2401	}
2402
2403	viewCell->mLeaves.push_back(leaf);
2404	}
2405	else
2406	{
2407	BspInterior interior = dynamic_cast<BspInterior >(node);
2408
2409	nodeStack.push(interior->GetFront());
2410	nodeStack.push(interior->GetBack());
2411	}
2412	}
2413	}
2414
2415
2416	typedef pair<BspNode , BspNodeGeometry > bspNodePair;
2417
2418
2419	int VspBspTree::CastBeam(Beam &beam)
2420	{
2421	stack<bspNodePair> nodeStack;
2422	BspNodeGeometry *rgeom = new BspNodeGeometry();
2423	ConstructGeometry(mRoot, *rgeom);
2424
2425	nodeStack.push(bspNodePair(mRoot, rgeom));
2426
2427	ViewCell::NewMail();
2428
2429	while (!nodeStack.empty())
2430	{
2431	BspNode *node = nodeStack.top().first;
2432	BspNodeGeometry *geom = nodeStack.top().second;
2433	nodeStack.pop();
2434
2435	AxisAlignedBox3 box;
2436	box.Initialize();
2437	geom->IncludeInBox(box);
2438
2439	const int side = beam.ComputeIntersection(box);
2440
2441	switch (side)
2442	{
2443	case -1:
2444	CollectViewCells(node, true, beam.mViewCells, true);
2445	break;
2446	case 0:
2447
2448	if (node->IsLeaf())
2449	{
2450	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2451
2452	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
2453	{
2454	leaf->GetViewCell()->Mail();
2455	beam.mViewCells.push_back(leaf->GetViewCell());
2456	}
2457	}
2458	else
2459	{
2460	BspInterior interior = dynamic_cast<BspInterior >(node);
2461
2462	BspNode *first = interior->GetFront();
2463	BspNode *second = interior->GetBack();
2464
2465	BspNodeGeometry *firstGeom = new BspNodeGeometry();
2466	BspNodeGeometry *secondGeom = new BspNodeGeometry();
2467
2468	geom->SplitGeometry(*firstGeom,
2469	*secondGeom,
2470	interior->GetPlane(),
2471	mBox,
2472	mEpsilon);
2473
2474	// decide on the order of the nodes
2475	if (DotProd(beam.mPlanes[0].mNormal,
2476	interior->GetPlane().mNormal) > 0)
2477	{
2478	swap(first, second);
2479	swap(firstGeom, secondGeom);
2480	}
2481
2482	nodeStack.push(bspNodePair(first, firstGeom));
2483	nodeStack.push(bspNodePair(second, secondGeom));
2484	}
2485
2486	break;
2487	default:
2488	// default: cull
2489	break;
2490	}
2491
2492	DEL_PTR(geom);
2493
2494	}
2495
2496	return (int)beam.mViewCells.size();
2497	}
2498
2499
2500	bool VspBspTree::MergeViewCells(BspLeaf l1, BspLeaf l2) const
2501	{
2502	//-- change pointer to view cells of all leaves associated
2503	//-- with the previous view cells
2504	BspViewCell *fVc = l1->GetViewCell();
2505	BspViewCell *bVc = l2->GetViewCell();
2506
2507	BspViewCell vc = dynamic_cast<BspViewCell >(
2508	mViewCellsManager->MergeViewCells(fVc, bVc));
2509
2510	// if merge was unsuccessful
2511	if (!vc) return false;
2512
2513	// set new size of view cell
2514	if (mUseAreaForPvs)
2515	vc->SetArea(fVc->GetArea() + bVc->GetArea());
2516	else
2517	vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
2518
2519	vector<BspLeaf *> fLeaves = fVc->mLeaves;
2520	vector<BspLeaf *> bLeaves = bVc->mLeaves;
2521
2522	vector<BspLeaf *>::const_iterator it;
2523
2524	//-- change view cells of all the other leaves the view cell belongs to
2525	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
2526	{
2527	(*it)->SetViewCell(vc);
2528	vc->mLeaves.push_back(*it);
2529	}
2530
2531	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
2532	{
2533	(*it)->SetViewCell(vc);
2534	vc->mLeaves.push_back(*it);
2535	}
2536
2537	vc->Mail();
2538
2539	// clean up old view cells
2540	DEL_PTR(fVc);
2541	DEL_PTR(bVc);
2542
2543	return true;
2544	}
2545
2546
2547	void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
2548	{
2549	mViewCellsManager = vcm;
2550	}
2551
2552
2553	int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves)
2554	{
2555	BspLeaf::NewMail();
2556
2557	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2558
2559	int candidates = 0;
2560
2561	// find merge candidates and push them into queue
2562	for (it = leaves.begin(); it != it_end; ++ it)
2563	{
2564	BspLeaf leaf = it;
2565
2566	/// create leaf pvs (needed for post processing
2567	leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
2568
2569	BspMergeCandidate::sOverallCost +=
2570	leaf->mProbability * leaf->mPvs->GetSize();
2571
2572	// the same leaves must not be part of two merge candidates
2573	leaf->Mail();
2574	vector<BspLeaf *> neighbors;
2575	FindNeighbors(leaf, neighbors, true);
2576
2577	vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
2578
2579	// TODO: test if at least one ray goes from one leaf to the other
2580	for (nit = neighbors.begin(); nit != nit_end; ++ nit)
2581	{
2582	if ((*nit)->GetViewCell() != leaf->GetViewCell())
2583	{
2584	mMergeQueue.push(BspMergeCandidate(leaf, *nit));
2585	++ candidates;
2586	}
2587	}
2588	}
2589
2590	Debug << "found " << candidates << " new merge candidates" << endl;
2591
2592	return (int)leaves.size();
2593	}
2594
2595
2596	int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays)
2597	{
2598	vector<BspRay *> bspRays;
2599
2600	ViewCell::NewMail();
2601	long startTime = GetTime();
2602	ConstructBspRays(bspRays, rays);
2603	Debug << (int)bspRays.size() << " bsp rays constructed in "
2604	<< TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
2605
2606	map<BspLeaf , vector<BspLeaf> > neighborMap;
2607	vector<BspIntersection>::const_iterator iit;
2608
2609	int numLeaves = 0;
2610
2611	BspLeaf::NewMail();
2612
2613	for (int i = 0; i < (int)bspRays.size(); ++ i)
2614	{
2615	BspRay *ray = bspRays[i];
2616
2617	// traverse leaves stored in the rays and compare and
2618	// merge consecutive leaves (i.e., the neighbors in the tree)
2619	if (ray->intersections.size() < 2)
2620	continue;
2621
2622	iit = ray->intersections.begin();
2623	BspLeaf leaf = ((iit ++)).mLeaf;
2624
2625	// create leaf pvs (needed for post processing)
2626	if (!leaf->mPvs)
2627	{
2628	leaf->mPvs =
2629	new ObjectPvs(leaf->GetViewCell()->GetPvs());
2630
2631	BspMergeCandidate::sOverallCost +=
2632	leaf->mProbability * leaf->mPvs->GetSize();
2633
2634	++ numLeaves;
2635	}
2636
2637	// traverse intersections
2638	// consecutive leaves are neighbors => add them to queue
2639	for (; iit != ray->intersections.end(); ++ iit)
2640	{
2641	// next pair
2642	BspLeaf *prevLeaf = leaf;
2643	leaf = (*iit).mLeaf;
2644
2645	// view space not valid or same view cell
2646	if (!leaf->TreeValid() \|\| !prevLeaf->TreeValid() \|\|
2647	(leaf->GetViewCell() == prevLeaf->GetViewCell()))
2648	continue;
2649
2650	// create leaf pvs (needed for post processing)
2651	if (!leaf->mPvs)
2652	{
2653	leaf->mPvs =
2654	new ObjectPvs(leaf->GetViewCell()->GetPvs());
2655
2656	BspMergeCandidate::sOverallCost +=
2657	leaf->mProbability * leaf->mPvs->GetSize();
2658
2659	++ numLeaves;
2660	}
2661
2662	vector<BspLeaf *> &neighbors = neighborMap[leaf];
2663
2664	bool found = false;
2665
2666	// both leaves inserted in queue already =>
2667	// look if double pair already exists
2668	if (leaf->Mailed() && prevLeaf->Mailed())
2669	{
2670	vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
2671
2672	for (it = neighbors.begin(); !found && (it != it_end); ++ it)
2673	if (*it == prevLeaf)
2674	found = true; // already in queue
2675	}
2676
2677	if (!found)
2678	{
2679	// this pair is not in map already
2680	// => insert into the neighbor map and the queue
2681	neighbors.push_back(prevLeaf);
2682	neighborMap[prevLeaf].push_back(leaf);
2683
2684	leaf->Mail();
2685	prevLeaf->Mail();
2686
2687	mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf));
2688	}
2689	}
2690	}
2691	Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
2692	Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
2693	Debug << "leaves in queue: " << numLeaves << endl;
2694	Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
2695
2696	CLEAR_CONTAINER(bspRays);
2697
2698	//-- collect the leaves which haven't been found by ray casting
2699	if (0)
2700	{
2701	cout << "finding additional merge candidates using geometry" << endl;
2702	vector<BspLeaf *> leaves;
2703	CollectLeaves(leaves, true);
2704	Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
2705	CollectMergeCandidates(leaves);
2706	}
2707
2708	return numLeaves;
2709	}
2710
2711
2712	void VspBspTree::ConstructBspRays(vector<BspRay *> &bspRays,
2713	const VssRayContainer &rays)
2714	{
2715	VssRayContainer::const_iterator it, it_end = rays.end();
2716
2717	for (it = rays.begin(); it != rays.end(); ++ it)
2718	{
2719	VssRay vssRay = it;
2720	BspRay *ray = new BspRay(vssRay);
2721
2722	ViewCellContainer viewCells;
2723
2724	Ray hray(*vssRay);
2725	float tmin = 0, tmax = 1.0;
2726	// matt TODO: remove this!!
2727	//hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
2728	if (!mBox.GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
2729	continue;
2730
2731	Vector3 origin = hray.Extrap(tmin);
2732	Vector3 termination = hray.Extrap(tmax);
2733
2734	// cast line segment to get intersections with bsp leaves
2735	CastLineSegment(origin, termination, viewCells);
2736
2737	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2738	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2739	{
2740	BspViewCell vc = dynamic_cast<BspViewCell >(*vit);
2741	vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
2742	//NOTE: not sorted!
2743	for (it = vc->mLeaves.begin(); it != it_end; ++ it)
2744	{
2745	ray->intersections.push_back(BspIntersection(0, *it));
2746	}
2747	}
2748
2749	bspRays.push_back(ray);
2750	}
2751	}
2752
2753
2754	int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
2755	{
2756	BspMergeCandidate::sMaxPvsSize = mViewCellsManager->GetMaxPvsSize();
2757	BspMergeCandidate::sUseArea = mUseAreaForPvs;
2758
2759	MergeStatistics mergeStats;
2760	mergeStats.Start();
2761	// TODO: REMOVE LATER for performance!
2762	const bool showMergeStats = false;
2763	//BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs;
2764	long startTime = GetTime();
2765
2766	if (mUseRaysForMerge)
2767	{
2768	cout << "collecting merge candidates (rays) ... ";
2769	mergeStats.nodes = CollectMergeCandidates(rays);
2770	cout << "fininshed collecting candidates" << endl;
2771	}
2772	else
2773	{
2774	vector<BspLeaf *> leaves;
2775	CollectLeaves(leaves);
2776	mergeStats.nodes = CollectMergeCandidates(leaves);
2777	}
2778
2779
2780	mergeStats.collectTime = TimeDiff(startTime, GetTime());
2781	mergeStats.candidates = (int)mMergeQueue.size();
2782	startTime = GetTime();
2783
2784	int nViewCells = mStat.Leaves() - mStat.invalidLeaves;
2785	int pass = 0;
2786	const int nextPass = 200;
2787
2788	cout << "starting merge ... ";
2789
2790	//-- use priority queue to merge leaf pairs
2791	while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) &&
2792	(mMergeQueue.top().GetMergeCost() <
2793	mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
2794	{
2795	/*Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
2796	<< mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost
2797	<< " max ratio: " << mMergeMaxCostRatio << endl;*/
2798	BspMergeCandidate mc = mMergeQueue.top();
2799	mMergeQueue.pop();
2800
2801	// both view cells equal!
2802	if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
2803	continue;
2804
2805	if (mc.Valid())
2806	{
2807	ViewCell::NewMail();
2808	const float mergeCost = mc.GetMergeCost();
2809
2810	MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
2811
2812
2813	// increase absolute merge cost
2814	BspMergeCandidate::sOverallCost += mc.GetMergeCost();
2815
2816
2817	if (showMergeStats)
2818	{
2819	if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
2820	++ mergeStats.siblings;
2821
2822	const int dist =
2823	TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
2824	if (dist > mergeStats.maxTreeDist)
2825	mergeStats.maxTreeDist = dist;
2826	mergeStats.accTreeDist += dist;
2827
2828
2829	if (((mergeStats.merged % nextPass) == 0) \|\| (nViewCells == mMergeMinViewCells))
2830	{
2831	mStats
2832	<< "#Pass\n" << pass ++ << endl
2833	<< "#Merged\n" << mergeStats.merged << endl
2834	<< "#Viewcells\n" << nViewCells << endl
2835	<< "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl
2836	<< "#CurrentCost\n" << mergeCost << endl
2837	<< "#RelCost\n" << mc.GetMergeCost() / BspMergeCandidate::sOverallCost << endl
2838	<< "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl;
2839
2840	cout << "exporting view cells ... ";
2841	ViewCellContainer viewCells;
2842	CollectViewCells(mRoot, false, viewCells);
2843
2844
2845	char s[64];
2846	sprintf(s, "merged_viewcells%07d.x3d", nViewCells);
2847	Exporter *exporter = Exporter::GetExporter(s);
2848
2849	if (exporter)
2850	{
2851	exporter->ExportGeometry(objects);
2852	Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
2853	ViewCellContainer::const_iterator it, it_end = viewCells.end();
2854
2855	for (it = viewCells.begin(); it != it_end; ++ it)
2856	{
2857	mViewCellsManager->ExportVcGeometry(exporter, *it);
2858	}
2859
2860	delete exporter;
2861	}
2862	cout << "finished " << endl;
2863	}
2864	}
2865
2866	-- nViewCells;
2867	++ mergeStats.merged;
2868	}
2869	// merge candidate not valid, because one of the leaves was already
2870	// merged with another one => validate and reinsert into queue
2871	else
2872	{
2873	mc.SetValid();
2874	mMergeQueue.push(mc);
2875	}
2876	}
2877	cout << "finished merge" << endl;
2878	mergeStats.mergeTime = TimeDiff(startTime, GetTime());
2879	mergeStats.Stop();
2880
2881	if (showMergeStats)
2882	Debug << mergeStats << endl << endl;
2883
2884
2885	//TODO: should return sample contributions?
2886	return mergeStats.merged;
2887	}
2888
2889
2890	ViewCell *VspBspTree::GetViewCell(const Vector3 &point)
2891	{
2892	if (mRoot == NULL)
2893	return NULL;
2894
2895	stack<BspNode *> nodeStack;
2896	nodeStack.push(mRoot);
2897
2898	ViewCell *viewcell = NULL;
2899
2900	while (!nodeStack.empty()) {
2901	BspNode *node = nodeStack.top();
2902	nodeStack.pop();
2903
2904	if (node->IsLeaf()) {
2905	viewcell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
2906	break;
2907	} else {
2908
2909	BspInterior interior = dynamic_cast<BspInterior >(node);
2910
2911	// random decision
2912	if (interior->GetPlane().Side(point) < 0)
2913	nodeStack.push(interior->GetBack());
2914	else
2915	nodeStack.push(interior->GetFront());
2916	}
2917	}
2918
2919	return viewcell;
2920	}
2921
2922
2923	int VspBspTree::RefineViewCells(const VssRayContainer &rays)
2924	{
2925	int shuffled = 0;
2926
2927	Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
2928	BspLeaf::NewMail();
2929
2930	// Use priority queue of remaining leaf pairs
2931	// These candidates either share the same view cells or
2932	// are border leaves which share a boundary.
2933	// We test if they can be shuffled, i.e.,
2934	// either one leaf is made part of one view cell or the other
2935	// leaf is made part of the other view cell. It is tested if the
2936	// remaining view cells are "better" than the old ones.
2937	while (!mMergeQueue.empty())
2938	{
2939	BspMergeCandidate mc = mMergeQueue.top();
2940	mMergeQueue.pop();
2941
2942	// both view cells equal or already shuffled
2943	if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) \|\|
2944	(mc.GetLeaf1()->Mailed()) \|\| (mc.GetLeaf2()->Mailed()))
2945	continue;
2946
2947	// candidate for shuffling
2948	const bool wasShuffled =
2949	ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
2950
2951	//-- stats
2952	if (wasShuffled)
2953	++ shuffled;
2954	}
2955
2956	return shuffled;
2957	}
2958
2959
2960	inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
2961	{
2962	return pvs1.AddPvs(pvs2);
2963	}
2964
2965	/inline int SubtractedPvsSize(BspViewCell vc, BspLeaf *l, const ObjectPvs &pvs2)
2966	{
2967	ObjectPvs pvs;
2968	vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
2969	for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
2970	if (*it != l)
2971	pvs.AddPvs((it)->mPvs);
2972	return pvs.GetSize();
2973	}*/
2974
2975	inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
2976	{
2977	return pvs1.SubtractPvs(pvs2);
2978	}
2979
2980
2981	float VspBspTree::GetShuffledVcCost(BspLeaf leaf, BspViewCell vc1, BspViewCell *vc2) const
2982	{
2983	//const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
2984	const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
2985	const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
2986
2987	if (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize())
2988	return 1e15f;
2989
2990	float p1, p2;
2991
2992	if (mUseAreaForPvs)
2993	{
2994	p1 = vc1->GetArea() - leaf->mProbability;
2995	p2 = vc2->GetArea() + leaf->mProbability;
2996	}
2997	else
2998	{
2999	p1 = vc1->GetVolume() - leaf->mProbability;
3000	p2 = vc2->GetVolume() + leaf->mProbability;
3001	}
3002
3003	const float cost1 = pvs1 * p1;
3004	const float cost2 = pvs2 * p2;
3005
3006	return cost1 + cost2;
3007	}
3008
3009
3010	void VspBspTree::ShuffleLeaf(BspLeaf *leaf,
3011	BspViewCell *vc1,
3012	BspViewCell *vc2) const
3013	{
3014	// compute new pvs and area
3015	vc1->GetPvs().SubtractPvs(*leaf->mPvs);
3016	vc2->GetPvs().AddPvs(*leaf->mPvs);
3017
3018	if (mUseAreaForPvs)
3019	{
3020	vc1->SetArea(vc1->GetArea() - leaf->mProbability);
3021	vc2->SetArea(vc2->GetArea() + leaf->mProbability);
3022	}
3023	else
3024	{
3025	vc1->SetVolume(vc1->GetVolume() - leaf->mProbability);
3026	vc2->SetVolume(vc2->GetVolume() + leaf->mProbability);
3027	}
3028
3029	/// add to second view cell
3030	vc2->mLeaves.push_back(leaf);
3031
3032	// erase leaf from old view cell
3033	vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
3034
3035	for (; *it != leaf; ++ it);
3036	vc1->mLeaves.erase(it);
3037
3038	/*vc1->GetPvs().mEntries.clear();
3039	for (; it != vc1->mLeaves.end(); ++ it)
3040	{
3041	if (*it == leaf)
3042	vc1->mLeaves.erase(it);
3043	else
3044	vc1->GetPvs().AddPvs((it)->mPvs);
3045	}*/
3046
3047	leaf->SetViewCell(vc2); // finally change view cell
3048	}
3049
3050
3051	bool VspBspTree::ShuffleLeaves(BspLeaf leaf1, BspLeaf leaf2) const
3052	{
3053	BspViewCell *vc1 = leaf1->GetViewCell();
3054	BspViewCell *vc2 = leaf2->GetViewCell();
3055
3056	float cost1;
3057	float cost2;
3058
3059	if (mUseAreaForPvs)
3060	{
3061	cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
3062	cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
3063	}
3064	else
3065	{
3066	cost1 = vc1->GetPvs().GetSize() * vc1->GetVolume();
3067	cost2 = vc2->GetPvs().GetSize() * vc2->GetVolume();
3068	}
3069
3070	const float oldCost = cost1 + cost2;
3071
3072	float shuffledCost1 = Limits::Infinity;
3073	float shuffledCost2 = Limits::Infinity;
3074
3075	// the view cell should not be empty after the shuffle
3076	if (vc1->mLeaves.size() > 1)
3077	shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
3078	if (vc2->mLeaves.size() > 1)
3079	shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
3080
3081	// shuffling unsuccessful
3082	if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
3083	return false;
3084
3085	if (shuffledCost1 < shuffledCost2)
3086	{
3087	ShuffleLeaf(leaf1, vc1, vc2);
3088	leaf1->Mail();
3089	}
3090	else
3091	{
3092	ShuffleLeaf(leaf2, vc2, vc1);
3093	leaf2->Mail();
3094	}
3095
3096	return true;
3097	}
3098
3099
3100	bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
3101	{
3102	BspNode *node = mRoot;
3103
3104	while (1)
3105	{
3106	// early exit
3107	if (node->TreeValid())
3108	return true;
3109
3110	if (node->IsLeaf())
3111	return false;
3112
3113	BspInterior in = dynamic_cast<BspInterior >(node);
3114
3115	if (in->GetPlane().Side(viewPoint) <= 0)
3116	{
3117	node = in->GetBack();
3118	}
3119	else
3120	{
3121	node = in->GetFront();
3122	}
3123	}
3124
3125	// should never come here
3126	return false;
3127	}
3128
3129
3130	void VspBspTree::PropagateUpValidity(BspNode *node)
3131	{
3132	while (!node->IsRoot() && node->GetParent()->TreeValid())
3133	{
3134	node = node->GetParent();
3135	node->SetTreeValid(false);
3136	}
3137	}
3138
3139
3140	bool VspBspTree::Export(ofstream &stream)
3141	{
3142	ExportNode(mRoot, stream);
3143
3144	return true;
3145	}
3146
3147
3148	void VspBspTree::ExportNode(BspNode *node, ofstream &stream)
3149	{
3150	if (node->IsLeaf())
3151	{
3152	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
3153
3154	int id = -1;
3155	if (leaf->GetViewCell() != mOutOfBoundsCell)
3156	id = leaf->GetViewCell()->GetId();
3157
3158	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
3159	}
3160	else
3161	{
3162	BspInterior interior = dynamic_cast<BspInterior >(node);
3163
3164	Plane3 plane = interior->GetPlane();
3165	stream << "<Interior plane=\"" << plane.mNormal.x << " "
3166	<< plane.mNormal.y << " " << plane.mNormal.z << " "
3167	<< plane.mD << "\">" << endl;
3168
3169	ExportNode(interior->GetBack(), stream);
3170	ExportNode(interior->GetFront(), stream);
3171
3172	stream << "</Interior>" << endl;
3173	}
3174	}
3175
3176	/************************************************************************/
3177	/* BspMergeCandidate implementation */
3178	/************************************************************************/
3179
3180
3181	BspMergeCandidate::BspMergeCandidate(BspLeaf l1, BspLeaf l2):
3182	mMergeCost(0),
3183	mLeaf1(l1),
3184	mLeaf2(l2),
3185	mLeaf1Id(l1->GetViewCell()->mMailbox),
3186	mLeaf2Id(l2->GetViewCell()->mMailbox)
3187	{
3188	EvalMergeCost();
3189	}
3190
3191
3192	float BspMergeCandidate::GetCost(ViewCell *vc) const
3193	{
3194	if (sUseArea)
3195	return vc->GetPvs().GetSize() * vc->GetArea();
3196
3197	return vc->GetPvs().GetSize() * vc->GetVolume();
3198	}
3199
3200
3201	float BspMergeCandidate::GetLeaf1Cost() const
3202	{
3203	BspViewCell *vc = mLeaf1->GetViewCell();
3204	return GetCost(vc);
3205	}
3206
3207
3208	float BspMergeCandidate::GetLeaf2Cost() const
3209	{
3210	BspViewCell *vc = mLeaf2->GetViewCell();
3211	return GetCost(vc);
3212	}
3213
3214
3215	void BspMergeCandidate::EvalMergeCost()
3216	{
3217	//-- compute pvs difference
3218	BspViewCell *vc1 = mLeaf1->GetViewCell();
3219	BspViewCell *vc2 = mLeaf2->GetViewCell();
3220
3221	const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
3222	const int newPvs = diff1 + vc1->GetPvs().GetSize();
3223
3224	//-- compute ratio of old cost
3225	// (i.e., added size of left and right view cell times pvs size)
3226	// to new rendering cost (i.e, size of merged view cell times pvs size)
3227	const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
3228
3229	const float newCost = sUseArea ?
3230	(float)newPvs * (vc1->GetArea() + vc2->GetArea()) :
3231	(float)newPvs * (vc1->GetVolume() + vc2->GetVolume());
3232
3233
3234	if (newPvs > sMaxPvsSize) // strong penalty if pvs size too large
3235	{
3236	mMergeCost = 1e15f;
3237	}
3238	else
3239	{
3240	mMergeCost = newCost - oldCost;
3241	}
3242	}
3243
3244
3245	void BspMergeCandidate::SetLeaf1(BspLeaf *l)
3246	{
3247	mLeaf1 = l;
3248	}
3249
3250
3251	void BspMergeCandidate::SetLeaf2(BspLeaf *l)
3252	{
3253	mLeaf2 = l;
3254	}
3255
3256
3257	BspLeaf *BspMergeCandidate::GetLeaf1()
3258	{
3259	return mLeaf1;
3260	}
3261
3262
3263	BspLeaf *BspMergeCandidate::GetLeaf2()
3264	{
3265	return mLeaf2;
3266	}
3267
3268
3269	bool BspMergeCandidate::Valid() const
3270	{
3271	return
3272	(mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
3273	(mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
3274	}
3275
3276
3277	float BspMergeCandidate::GetMergeCost() const
3278	{
3279	return mMergeCost;
3280	}
3281
3282
3283	void BspMergeCandidate::SetValid()
3284	{
3285	mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
3286	mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
3287
3288	EvalMergeCost();
3289	}
3290
3291
3292	/************************************************************************/
3293	/* MergeStatistics implementation */
3294	/************************************************************************/
3295
3296
3297	void MergeStatistics::Print(ostream &app) const
3298	{
3299	app << "===== Merge statistics ===============\n";
3300
3301	app << setprecision(4);
3302
3303	app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
3304
3305	app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
3306
3307	app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
3308
3309	app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
3310
3311	app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
3312
3313	app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
3314	app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
3315
3316	app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
3317
3318	app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
3319
3320	app << "===== END OF BspTree statistics ==========\n";
3321	}

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

Download in other formats: