Context Navigation

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

Revision 578, 87.5 KB checked in by mattausch, 18 years ago (diff)
added upper and lower boundary for pvs penalty in heuristics

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

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

Download in other formats: