Context Navigation

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

Revision 544, 75.0 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: