Context Navigation

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

Revision 579, 95.4 KB checked in by mattausch, 18 years ago (diff)
started to include variance into the measures

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

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

Download in other formats: