Context Navigation

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

Revision 547, 77.1 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: