Context Navigation

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

Revision 557, 80.7 KB checked in by mattausch, 18 years ago (diff)
started implementing merge visualization !not working!!

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

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

Download in other formats: