Context Navigation

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

Revision 561, 81.4 KB checked in by mattausch, 18 years ago (diff)
added flexible checkvalitity function for view cells

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

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

Download in other formats: