Context Navigation

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

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

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

Download in other formats: