Context Navigation

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

Revision 556, 79.0 KB checked in by bittner, 18 years ago (diff)
debug version looking for glrenderer bug...

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

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

Download in other formats: