Context Navigation

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

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

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

Download in other formats: