Context Navigation

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

Revision 511, 68.6 KB checked in by mattausch, 19 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
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->GetIntValue("ViewCells.pvsInvalid", 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
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	const bool onlyAxisAligned =
942	(mSplitPlaneStrategy & AXIS_ALIGNED) &&
943	((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
944	((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
945
946	// split polygons if no axis aligned splits
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	void VspBspTree::CollectViewCells(ViewCellContainer &viewCells) const
1467	{
1468	stack<BspNode *> nodeStack;
1469
1470	if (!mRoot)
1471	return;
1472
1473	nodeStack.push(mRoot);
1474
1475	ViewCell::NewMail();
1476
1477	while (!nodeStack.empty())
1478	{
1479	BspNode *node = nodeStack.top();
1480	nodeStack.pop();
1481
1482	if (node->IsLeaf())
1483	{
1484	if (!mShowInvalidSpace && node->TreeValid())
1485	{
1486	ViewCell viewCell = dynamic_cast<BspLeaf >(node)->GetViewCell();
1487
1488	if (!viewCell->Mailed())
1489	{
1490	viewCell->Mail();
1491	viewCells.push_back(viewCell);
1492	}
1493	}
1494	}
1495	else
1496	{
1497	BspInterior interior = dynamic_cast<BspInterior >(node);
1498
1499	nodeStack.push(interior->GetFront());
1500	nodeStack.push(interior->GetBack());
1501	}
1502	}
1503	}
1504
1505
1506	float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
1507	{
1508	float len = 0;
1509
1510	RayInfoContainer::const_iterator it, it_end = rays.end();
1511
1512	for (it = rays.begin(); it != it_end; ++ it)
1513	len += (*it).SegmentLength();
1514
1515	return len;
1516	}
1517
1518
1519	int VspBspTree::SplitRays(const Plane3 &plane,
1520	RayInfoContainer &rays,
1521	RayInfoContainer &frontRays,
1522	RayInfoContainer &backRays)
1523	{
1524	int splits = 0;
1525
1526	while (!rays.empty())
1527	{
1528	RayInfo bRay = rays.back();
1529	rays.pop_back();
1530
1531	VssRay *ray = bRay.mRay;
1532	float t;
1533
1534	// get classification and receive new t
1535	const int cf = bRay.ComputeRayIntersection(plane, t);
1536
1537	switch (cf)
1538	{
1539	case -1:
1540	backRays.push_back(bRay);
1541	break;
1542	case 1:
1543	frontRays.push_back(bRay);
1544	break;
1545	case 0:
1546	{
1547	//-- split ray
1548	//-- test if start point behind or in front of plane
1549	const int side = plane.Side(bRay.ExtrapOrigin());
1550
1551	if (side <= 0)
1552	{
1553	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1554	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1555	}
1556	else
1557	{
1558	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1559	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1560	}
1561	}
1562	break;
1563	default:
1564	Debug << "Should not come here" << endl;
1565	break;
1566	}
1567	}
1568
1569	return splits;
1570	}
1571
1572
1573	void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
1574	{
1575	BspNode *lastNode;
1576
1577	do
1578	{
1579	lastNode = n;
1580
1581	// want to get planes defining geometry of this node => don't take
1582	// split plane of node itself
1583	n = n->GetParent();
1584
1585	if (n)
1586	{
1587	BspInterior interior = dynamic_cast<BspInterior >(n);
1588	Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
1589
1590	if (interior->GetFront() != lastNode)
1591	halfSpace.ReverseOrientation();
1592
1593	halfSpaces.push_back(halfSpace);
1594	}
1595	}
1596	while (n);
1597	}
1598
1599
1600	void VspBspTree::ConstructGeometry(BspNode *n,
1601	BspNodeGeometry &geom) const
1602	{
1603	vector<Plane3> halfSpaces;
1604	ExtractHalfSpaces(n, halfSpaces);
1605
1606	PolygonContainer candidatePolys;
1607
1608	// bounded planes are added to the polygons (reverse polygons
1609	// as they have to be outfacing
1610	for (int i = 0; i < (int)halfSpaces.size(); ++ i)
1611	{
1612	Polygon3 *p = GetBoundingBox().CrossSection(halfSpaces[i]);
1613
1614	if (p->Valid(mEpsilon))
1615	{
1616	candidatePolys.push_back(p->CreateReversePolygon());
1617	DEL_PTR(p);
1618	}
1619	}
1620
1621	// add faces of bounding box (also could be faces of the cell)
1622	for (int i = 0; i < 6; ++ i)
1623	{
1624	VertexContainer vertices;
1625
1626	for (int j = 0; j < 4; ++ j)
1627	vertices.push_back(mBox.GetFace(i).mVertices[j]);
1628
1629	candidatePolys.push_back(new Polygon3(vertices));
1630	}
1631
1632	for (int i = 0; i < (int)candidatePolys.size(); ++ i)
1633	{
1634	// polygon is split by all other planes
1635	for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
1636	{
1637	if (i == j) // polygon and plane are coincident
1638	continue;
1639
1640	VertexContainer splitPts;
1641	Polygon3 frontPoly, backPoly;
1642
1643	const int cf =
1644	candidatePolys[i]->ClassifyPlane(halfSpaces[j],
1645	mEpsilon);
1646
1647	switch (cf)
1648	{
1649	case Polygon3::SPLIT:
1650	frontPoly = new Polygon3();
1651	backPoly = new Polygon3();
1652
1653	candidatePolys[i]->Split(halfSpaces[j],
1654	*frontPoly,
1655	*backPoly,
1656	mEpsilon);
1657
1658	DEL_PTR(candidatePolys[i]);
1659
1660	if (frontPoly->Valid(mEpsilon))
1661	candidatePolys[i] = frontPoly;
1662	else
1663	DEL_PTR(frontPoly);
1664
1665	DEL_PTR(backPoly);
1666	break;
1667	case Polygon3::BACK_SIDE:
1668	DEL_PTR(candidatePolys[i]);
1669	break;
1670	// just take polygon as it is
1671	case Polygon3::FRONT_SIDE:
1672	case Polygon3::COINCIDENT:
1673	default:
1674	break;
1675	}
1676	}
1677
1678	if (candidatePolys[i])
1679	geom.mPolys.push_back(candidatePolys[i]);
1680	}
1681	}
1682
1683
1684	void VspBspTree::ConstructGeometry(BspViewCell *vc,
1685	BspNodeGeometry &vcGeom) const
1686	{
1687	vector<BspLeaf *> leaves = vc->mLeaves;
1688	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
1689
1690	for (it = leaves.begin(); it != it_end; ++ it)
1691	ConstructGeometry(*it, vcGeom);
1692	}
1693
1694
1695	int VspBspTree::FindNeighbors(BspNode n, vector<BspLeaf > &neighbors,
1696	const bool onlyUnmailed) const
1697	{
1698	BspNodeGeometry geom;
1699	ConstructGeometry(n, geom);
1700
1701	stack<BspNode *> nodeStack;
1702	nodeStack.push(mRoot);
1703
1704	// split planes from the root to this node
1705	// needed to verify that we found neighbor leaf
1706	vector<Plane3> halfSpaces;
1707	ExtractHalfSpaces(n, halfSpaces);
1708
1709	while (!nodeStack.empty())
1710	{
1711	BspNode *node = nodeStack.top();
1712	nodeStack.pop();
1713
1714	if (node->IsLeaf())
1715
1716	{ // test if this leaf is in valid view space
1717	if (node->TreeValid() &&
1718	node != n &&
1719	(!onlyUnmailed \|\| !node->Mailed()))
1720	{
1721	// test all planes of current node if candidate really
1722	// is neighbour
1723	BspNodeGeometry neighborCandidate;
1724	ConstructGeometry(node, neighborCandidate);
1725
1726	bool isAdjacent = true;
1727	for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
1728	{
1729	const int cf =
1730	Polygon3::ClassifyPlane(neighborCandidate.mPolys,
1731	halfSpaces[i],
1732	mEpsilon);
1733
1734	if (cf == Polygon3::BACK_SIDE)
1735	isAdjacent = false;
1736	}
1737	// neighbor was found
1738	if (isAdjacent)
1739	neighbors.push_back(dynamic_cast<BspLeaf *>(node));
1740	}
1741	}
1742	else
1743	{
1744	BspInterior interior = dynamic_cast<BspInterior >(node);
1745
1746	const int cf = Polygon3::ClassifyPlane(geom.mPolys,
1747	interior->GetPlane(),
1748	mEpsilon);
1749
1750	if (cf == Polygon3::FRONT_SIDE)
1751	nodeStack.push(interior->GetFront());
1752	else
1753	if (cf == Polygon3::BACK_SIDE)
1754	nodeStack.push(interior->GetBack());
1755	else
1756	{
1757	// random decision
1758	nodeStack.push(interior->GetBack());
1759	nodeStack.push(interior->GetFront());
1760	}
1761	}
1762	}
1763
1764	return (int)neighbors.size();
1765	}
1766
1767
1768	BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace)
1769	{
1770	stack<BspNode *> nodeStack;
1771	nodeStack.push(mRoot);
1772
1773	int mask = rand();
1774
1775	while (!nodeStack.empty())
1776	{
1777	BspNode *node = nodeStack.top();
1778	nodeStack.pop();
1779
1780	if (node->IsLeaf())
1781	{
1782	return dynamic_cast<BspLeaf *>(node);
1783	}
1784	else
1785	{
1786	BspInterior interior = dynamic_cast<BspInterior >(node);
1787	BspNode *next;
1788	BspNodeGeometry geom;
1789
1790	// todo: not very efficient: constructs full cell everytime
1791	ConstructGeometry(interior, geom);
1792
1793	const int cf =
1794	Polygon3::ClassifyPlane(geom.mPolys, halfspace, mEpsilon);
1795
1796	if (cf == Polygon3::BACK_SIDE)
1797	next = interior->GetFront();
1798	else
1799	if (cf == Polygon3::FRONT_SIDE)
1800	next = interior->GetFront();
1801	else
1802	{
1803	// random decision
1804	if (mask & 1)
1805	next = interior->GetBack();
1806	else
1807	next = interior->GetFront();
1808	mask = mask >> 1;
1809	}
1810
1811	nodeStack.push(next);
1812	}
1813	}
1814
1815	return NULL;
1816	}
1817
1818	BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed)
1819	{
1820	stack<BspNode *> nodeStack;
1821
1822	nodeStack.push(mRoot);
1823
1824	int mask = rand();
1825
1826	while (!nodeStack.empty())
1827	{
1828	BspNode *node = nodeStack.top();
1829	nodeStack.pop();
1830
1831	if (node->IsLeaf())
1832	{
1833	if ( (!onlyUnmailed \|\| !node->Mailed()) )
1834	return dynamic_cast<BspLeaf *>(node);
1835	}
1836	else
1837	{
1838	BspInterior interior = dynamic_cast<BspInterior >(node);
1839
1840	// random decision
1841	if (mask & 1)
1842	nodeStack.push(interior->GetBack());
1843	else
1844	nodeStack.push(interior->GetFront());
1845
1846	mask = mask >> 1;
1847	}
1848	}
1849
1850	return NULL;
1851	}
1852
1853	int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const
1854	{
1855	int pvsSize = 0;
1856
1857	RayInfoContainer::const_iterator rit, rit_end = rays.end();
1858
1859	Intersectable::NewMail();
1860
1861	for (rit = rays.begin(); rit != rays.end(); ++ rit)
1862	{
1863	VssRay ray = (rit).mRay;
1864
1865	if (ray->mOriginObject)
1866	{
1867	if (!ray->mOriginObject->Mailed())
1868	{
1869	ray->mOriginObject->Mail();
1870	++ pvsSize;
1871	}
1872	}
1873	if (ray->mTerminationObject)
1874	{
1875	if (!ray->mTerminationObject->Mailed())
1876	{
1877	ray->mTerminationObject->Mail();
1878	++ pvsSize;
1879	}
1880	}
1881	}
1882
1883	return pvsSize;
1884	}
1885
1886	float VspBspTree::GetEpsilon() const
1887	{
1888	return mEpsilon;
1889	}
1890
1891
1892	int VspBspTree::SplitPolygons(const Plane3 &plane,
1893	PolygonContainer &polys,
1894	PolygonContainer &frontPolys,
1895	PolygonContainer &backPolys,
1896	PolygonContainer &coincident) const
1897	{
1898	int splits = 0;
1899
1900	while (!polys.empty())
1901	{
1902	Polygon3 *poly = polys.back();
1903	polys.pop_back();
1904
1905	// classify polygon
1906	const int cf = poly->ClassifyPlane(plane, mEpsilon);
1907
1908	switch (cf)
1909	{
1910	case Polygon3::COINCIDENT:
1911	coincident.push_back(poly);
1912	break;
1913	case Polygon3::FRONT_SIDE:
1914	frontPolys.push_back(poly);
1915	break;
1916	case Polygon3::BACK_SIDE:
1917	backPolys.push_back(poly);
1918	break;
1919	case Polygon3::SPLIT:
1920	backPolys.push_back(poly);
1921	frontPolys.push_back(poly);
1922	++ splits;
1923	break;
1924	default:
1925	Debug << "SHOULD NEVER COME HERE\n";
1926	break;
1927	}
1928	}
1929
1930	return splits;
1931	}
1932
1933
1934	int VspBspTree::CastLineSegment(const Vector3 &origin,
1935	const Vector3 &termination,
1936	vector<ViewCell *> &viewcells)
1937	{
1938	int hits = 0;
1939	stack<BspRayTraversalData> tStack;
1940
1941	float mint = 0.0f, maxt = 1.0f;
1942
1943	Intersectable::NewMail();
1944
1945	Vector3 entp = origin;
1946	Vector3 extp = termination;
1947
1948	BspNode *node = mRoot;
1949	BspNode *farChild = NULL;
1950
1951	float t;
1952	while (1)
1953	{
1954	if (!node->IsLeaf())
1955	{
1956	BspInterior in = dynamic_cast<BspInterior >(node);
1957
1958	Plane3 splitPlane = in->GetPlane();
1959
1960	const int entSide = splitPlane.Side(entp);
1961	const int extSide = splitPlane.Side(extp);
1962
1963	if (entSide < 0)
1964	{
1965	node = in->GetBack();
1966	// plane does not split ray => no far child
1967	if (extSide <= 0)
1968	continue;
1969
1970	farChild = in->GetFront(); // plane splits ray
1971	}
1972	else if (entSide > 0)
1973	{
1974	node = in->GetFront();
1975
1976	if (extSide >= 0) // plane does not split ray => no far child
1977	continue;
1978
1979	farChild = in->GetBack(); // plane splits ray
1980	}
1981	else // ray end point on plane
1982	{ // NOTE: what to do if ray is coincident with plane?
1983	if (extSide < 0)
1984	node = in->GetBack();
1985	else
1986	node = in->GetFront();
1987
1988	continue; // no far child
1989	}
1990
1991	// push data for far child
1992	tStack.push(BspRayTraversalData(farChild, extp));
1993
1994	// find intersection of ray segment with plane
1995	extp = splitPlane.FindIntersection(origin, extp, &t);
1996	}
1997	else
1998	{
1999	// reached leaf => intersection with view cell
2000	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2001
2002	if (!leaf->GetViewCell()->Mailed())
2003	{
2004	viewcells.push_back(leaf->GetViewCell());
2005	leaf->GetViewCell()->Mail();
2006	++ hits;
2007	}
2008
2009	//-- fetch the next far child from the stack
2010	if (tStack.empty())
2011	break;
2012
2013	entp = extp;
2014
2015	BspRayTraversalData &s = tStack.top();
2016
2017	node = s.mNode;
2018	extp = s.mExitPoint;
2019
2020	tStack.pop();
2021	}
2022	}
2023
2024	return hits;
2025	}
2026
2027	int VspBspTree::TreeDistance(BspNode n1, BspNode n2) const
2028	{
2029	std::deque<BspNode *> path1;
2030	BspNode *p1 = n1;
2031
2032	// create path from node 1 to root
2033	while (p1)
2034	{
2035	if (p1 == n2) // second node on path
2036	return (int)path1.size();
2037
2038	path1.push_front(p1);
2039	p1 = p1->GetParent();
2040	}
2041
2042	int depth = n2->GetDepth();
2043	int d = depth;
2044
2045	BspNode *p2 = n2;
2046
2047	// compare with same depth
2048	while (1)
2049	{
2050	if ((d < (int)path1.size()) && (p2 == path1[d]))
2051	return (depth - d) + ((int)path1.size() - 1 - d);
2052
2053	-- d;
2054	p2 = p2->GetParent();
2055	}
2056
2057	return 0; // never come here
2058	}
2059
2060	BspNode VspBspTree::CollapseTree(BspNode node, int &collapsed)
2061	{
2062	if (node->IsLeaf())
2063	return node;
2064
2065	BspInterior interior = dynamic_cast<BspInterior >(node);
2066
2067	BspNode *front = CollapseTree(interior->GetFront(), collapsed);
2068	BspNode *back = CollapseTree(interior->GetBack(), collapsed);
2069
2070	if (front->IsLeaf() && back->IsLeaf())
2071	{
2072	BspLeaf frontLeaf = dynamic_cast<BspLeaf >(front);
2073	BspLeaf backLeaf = dynamic_cast<BspLeaf >(back);
2074
2075	//-- collapse tree
2076	if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
2077	{
2078	BspViewCell *vc = frontLeaf->GetViewCell();
2079
2080	BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
2081	leaf->SetTreeValid(frontLeaf->TreeValid());
2082
2083	// replace a link from node's parent
2084	if (leaf->GetParent())
2085	leaf->GetParent()->ReplaceChildLink(node, leaf);
2086
2087	++ collapsed;
2088	delete interior;
2089
2090	return leaf;
2091	}
2092	}
2093
2094	return node;
2095	}
2096
2097
2098	int VspBspTree::CollapseTree()
2099	{
2100	int collapsed = 0;
2101	(void)CollapseTree(mRoot, collapsed);
2102	// revalidate leaves
2103	RepairVcLeafLists();
2104
2105	return collapsed;
2106	}
2107
2108
2109	void VspBspTree::RepairVcLeafLists()
2110	{
2111	// list not valid anymore => clear
2112	stack<BspNode *> nodeStack;
2113	nodeStack.push(mRoot);
2114
2115	ViewCell::NewMail();
2116
2117	while (!nodeStack.empty())
2118	{
2119	BspNode *node = nodeStack.top();
2120	nodeStack.pop();
2121
2122	if (node->IsLeaf())
2123	{
2124	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2125
2126	BspViewCell *viewCell = leaf->GetViewCell();
2127
2128	if (!viewCell->Mailed())
2129	{
2130	viewCell->mLeaves.clear();
2131	viewCell->Mail();
2132	}
2133
2134	viewCell->mLeaves.push_back(leaf);
2135	}
2136	else
2137	{
2138	BspInterior interior = dynamic_cast<BspInterior >(node);
2139
2140	nodeStack.push(interior->GetFront());
2141	nodeStack.push(interior->GetBack());
2142	}
2143	}
2144	}
2145
2146
2147	bool VspBspTree::MergeViewCells(BspLeaf l1, BspLeaf l2) const
2148	{
2149	//-- change pointer to view cells of all leaves associated
2150	//-- with the previous view cells
2151	BspViewCell *fVc = l1->GetViewCell();
2152	BspViewCell *bVc = l2->GetViewCell();
2153
2154	BspViewCell vc = dynamic_cast<BspViewCell >(
2155	mViewCellsManager->MergeViewCells(fVc, bVc));
2156
2157	// if merge was unsuccessful
2158	if (!vc) return false;
2159
2160	// set new size of view cell
2161	vc->SetArea(fVc->GetArea() + bVc->GetArea());
2162
2163	vector<BspLeaf *> fLeaves = fVc->mLeaves;
2164	vector<BspLeaf *> bLeaves = bVc->mLeaves;
2165
2166	vector<BspLeaf *>::const_iterator it;
2167
2168	//-- change view cells of all the other leaves the view cell belongs to
2169	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
2170	{
2171	(*it)->SetViewCell(vc);
2172	vc->mLeaves.push_back(*it);
2173	}
2174
2175	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
2176	{
2177	(*it)->SetViewCell(vc);
2178	vc->mLeaves.push_back(*it);
2179	}
2180
2181	vc->Mail();
2182
2183	// clean up old view cells
2184	DEL_PTR(fVc);
2185	DEL_PTR(bVc);
2186
2187	return true;
2188	}
2189
2190
2191	void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
2192	{
2193	mViewCellsManager = vcm;
2194	}
2195
2196
2197	int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves)
2198	{
2199	BspLeaf::NewMail();
2200
2201	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2202
2203	int candidates = 0;
2204
2205	// find merge candidates and push them into queue
2206	for (it = leaves.begin(); it != it_end; ++ it)
2207	{
2208	BspLeaf leaf = it;
2209
2210	/// create leaf pvs (needed for post processing
2211	leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
2212
2213	BspMergeCandidate::sOverallCost +=
2214	leaf->mArea * leaf->mPvs->GetSize();
2215
2216	// the same leaves must not be part of two merge candidates
2217	leaf->Mail();
2218	vector<BspLeaf *> neighbors;
2219	FindNeighbors(leaf, neighbors, true);
2220
2221	vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
2222
2223	// TODO: test if at least one ray goes from one leaf to the other
2224	for (nit = neighbors.begin(); nit != nit_end; ++ nit)
2225	{
2226	if ((*nit)->GetViewCell() != leaf->GetViewCell())
2227	{
2228	mMergeQueue.push(BspMergeCandidate(leaf, *nit));
2229	++ candidates;
2230	}
2231	}
2232	}
2233
2234	Debug << "found " << candidates << " new merge candidates" << endl;
2235
2236	return (int)leaves.size();
2237	}
2238
2239
2240	int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays)
2241	{
2242	vector<BspRay *> bspRays;
2243
2244	long startTime = GetTime();
2245	ConstructBspRays(bspRays, rays);
2246	Debug << (int)bspRays.size() << " bsp rays constructed in "
2247	<< TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
2248
2249	map<BspLeaf , vector<BspLeaf> > neighborMap;
2250	vector<BspIntersection>::const_iterator iit;
2251
2252	int numLeaves = 0;
2253
2254	BspLeaf::NewMail();
2255
2256	for (int i = 0; i < (int)bspRays.size(); ++ i)
2257	{
2258	BspRay *ray = bspRays[i];
2259
2260	// traverse leaves stored in the rays and compare and
2261	// merge consecutive leaves (i.e., the neighbors in the tree)
2262	if (ray->intersections.size() < 2)
2263	continue;
2264
2265	iit = ray->intersections.begin();
2266	BspLeaf leaf = ((iit ++)).mLeaf;
2267
2268	// create leaf pvs (needed for post processing)
2269	if (!leaf->mPvs)
2270	{
2271	leaf->mPvs =
2272	new ObjectPvs(leaf->GetViewCell()->GetPvs());
2273
2274	BspMergeCandidate::sOverallCost +=
2275	leaf->mArea * leaf->mPvs->GetSize();
2276
2277	++ numLeaves;
2278	}
2279
2280	// traverse intersections
2281	// consecutive leaves are neighbors => add them to queue
2282	for (; iit != ray->intersections.end(); ++ iit)
2283	{
2284	// next pair
2285	BspLeaf *prevLeaf = leaf;
2286	leaf = (*iit).mLeaf;
2287
2288	// view space not valid or same view cell
2289	if (!leaf->TreeValid() \|\| !prevLeaf->TreeValid() \|\|
2290	(leaf->GetViewCell() == prevLeaf->GetViewCell()))
2291	continue;
2292
2293	// create leaf pvs (needed for post processing)
2294	if (!leaf->mPvs)
2295	{
2296	leaf->mPvs =
2297	new ObjectPvs(leaf->GetViewCell()->GetPvs());
2298
2299	BspMergeCandidate::sOverallCost +=
2300	leaf->mArea * leaf->mPvs->GetSize();
2301
2302	++ numLeaves;
2303	}
2304
2305	vector<BspLeaf *> &neighbors = neighborMap[leaf];
2306
2307	bool found = false;
2308
2309	// both leaves inserted in queue already =>
2310	// look if double pair already exists
2311	if (leaf->Mailed() && prevLeaf->Mailed())
2312	{
2313	vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
2314
2315	for (it = neighbors.begin(); !found && (it != it_end); ++ it)
2316	if (*it == prevLeaf)
2317	found = true; // already in queue
2318	}
2319
2320	if (!found)
2321	{
2322	// this pair is not in map already
2323	// => insert into the neighbor map and the queue
2324	neighbors.push_back(prevLeaf);
2325	neighborMap[prevLeaf].push_back(leaf);
2326
2327	leaf->Mail();
2328	prevLeaf->Mail();
2329
2330	mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf));
2331	}
2332	}
2333	}
2334	Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
2335	Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
2336	Debug << "leaves in queue: " << numLeaves << endl;
2337	Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
2338
2339	CLEAR_CONTAINER(bspRays);
2340
2341	//-- collect the leaves which haven't been found by ray casting
2342	vector<BspLeaf *> leaves;
2343	CollectLeaves(leaves, true, mMaxPvs);
2344	Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
2345	// TODO
2346	CollectMergeCandidates(leaves);
2347
2348	return numLeaves;
2349	}
2350
2351
2352	void VspBspTree::ConstructBspRays(vector<BspRay *> &bspRays,
2353	const VssRayContainer &rays)
2354	{
2355	VssRayContainer::const_iterator it, it_end = rays.end();
2356
2357	for (it = rays.begin(); it != rays.end(); ++ it)
2358	{
2359	VssRay vssRay = it;
2360	BspRay *ray = new BspRay(vssRay);
2361
2362	ViewCellContainer viewCells;
2363
2364	Ray hray(*vssRay);
2365	float tmin = 0, tmax = 1.0;
2366	// matt TODO: remove this!!
2367	//hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
2368	if (!mBox.GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
2369	continue;
2370
2371	Vector3 origin = hray.Extrap(tmin);
2372	Vector3 termination = hray.Extrap(tmax);
2373
2374	// cast line segment to get intersections with bsp leaves
2375	CastLineSegment(origin, termination, viewCells);
2376
2377	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2378	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2379	{
2380	BspViewCell vc = dynamic_cast<BspViewCell >(*vit);
2381	vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
2382	//NOTE: not sorted!
2383	for (it = vc->mLeaves.begin(); it != it_end; ++ it)
2384	ray->intersections.push_back(BspIntersection(0, *it));
2385	}
2386
2387	bspRays.push_back(ray);
2388	}
2389	}
2390
2391
2392	int VspBspTree::MergeViewCells(const VssRayContainer &rays)
2393	{
2394	MergeStatistics mergeStats;
2395	mergeStats.Start();
2396	// TODO: REMOVE LATER for performance!
2397	const bool showMergeStats = true;
2398	//BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs;
2399	long startTime = GetTime();
2400
2401	if (mUseRaysForMerge)
2402	mergeStats.nodes = CollectMergeCandidates(rays);
2403	else
2404	{
2405	vector<BspLeaf *> leaves;
2406	CollectLeaves(leaves);
2407	mergeStats.nodes = CollectMergeCandidates(leaves);
2408	}
2409
2410	mergeStats.collectTime = TimeDiff(startTime, GetTime());
2411	mergeStats.candidates = (int)mMergeQueue.size();
2412	startTime = GetTime();
2413
2414	int nViewCells = /mergeStats.nodes/ mStat.Leaves() - mStat.invalidLeaves;
2415
2416	//-- use priority queue to merge leaf pairs
2417	while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) &&
2418	(mMergeQueue.top().GetMergeCost() <
2419	mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
2420	{
2421	//Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
2422	// << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost
2423	// << " max ratio: " << mMergeMaxCostRatio << endl;
2424	BspMergeCandidate mc = mMergeQueue.top();
2425	mMergeQueue.pop();
2426
2427	// both view cells equal!
2428	if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
2429	continue;
2430
2431	if (mc.Valid())
2432	{
2433	ViewCell::NewMail();
2434	MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
2435	-- nViewCells;
2436
2437	++ mergeStats.merged;
2438
2439	// increase absolute merge cost
2440	BspMergeCandidate::sOverallCost += mc.GetMergeCost();
2441
2442	if (showMergeStats)
2443	{
2444	if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
2445	++ mergeStats.siblings;
2446
2447	const int dist =
2448	TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
2449	if (dist > mergeStats.maxTreeDist)
2450	mergeStats.maxTreeDist = dist;
2451	mergeStats.accTreeDist += dist;
2452	}
2453	}
2454	// merge candidate not valid, because one of the leaves was already
2455	// merged with another one => validate and reinsert into queue
2456	else
2457	{
2458	mc.SetValid();
2459	mMergeQueue.push(mc);
2460	}
2461	}
2462
2463	mergeStats.mergeTime = TimeDiff(startTime, GetTime());
2464	mergeStats.Stop();
2465
2466	if (showMergeStats)
2467	Debug << mergeStats << endl << endl;
2468
2469	//TODO: should return sample contributions?
2470	return mergeStats.merged;
2471	}
2472
2473
2474	ViewCell *VspBspTree::GetViewCell(const Vector3 &point)
2475	{
2476	if (mRoot == NULL)
2477	return NULL;
2478
2479	stack<BspNode *> nodeStack;
2480	nodeStack.push(mRoot);
2481
2482	ViewCell *viewcell = NULL;
2483
2484	while (!nodeStack.empty()) {
2485	BspNode *node = nodeStack.top();
2486	nodeStack.pop();
2487
2488	if (node->IsLeaf()) {
2489	viewcell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
2490	break;
2491	} else {
2492
2493	BspInterior interior = dynamic_cast<BspInterior >(node);
2494
2495	// random decision
2496	if (interior->GetPlane().Side(point) < 0)
2497	nodeStack.push(interior->GetBack());
2498	else
2499	nodeStack.push(interior->GetFront());
2500	}
2501	}
2502
2503	return viewcell;
2504	}
2505
2506
2507	int VspBspTree::RefineViewCells(const VssRayContainer &rays)
2508	{
2509	int shuffled = 0;
2510
2511	Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
2512	BspLeaf::NewMail();
2513
2514	// Use priority queue of remaining leaf pairs
2515	// These candidates either share the same view cells or
2516	// are border leaves which share a boundary.
2517	// We test if they can be shuffled, i.e.,
2518	// either one leaf is made part of one view cell or the other
2519	// leaf is made part of the other view cell. It is tested if the
2520	// remaining view cells are "better" than the old ones.
2521	while (!mMergeQueue.empty())
2522	{
2523	BspMergeCandidate mc = mMergeQueue.top();
2524	mMergeQueue.pop();
2525
2526	// both view cells equal or already shuffled
2527	if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) \|\|
2528	(mc.GetLeaf1()->Mailed()) \|\| (mc.GetLeaf2()->Mailed()))
2529	continue;
2530
2531	// candidate for shuffling
2532	const bool wasShuffled =
2533	ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
2534
2535	//-- stats
2536	if (wasShuffled)
2537	++ shuffled;
2538	}
2539
2540	return shuffled;
2541	}
2542
2543
2544	inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
2545	{
2546	return pvs1.AddPvs(pvs2);
2547	}
2548
2549	/inline int SubtractedPvsSize(BspViewCell vc, BspLeaf *l, const ObjectPvs &pvs2)
2550	{
2551	ObjectPvs pvs;
2552	vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
2553	for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
2554	if (*it != l)
2555	pvs.AddPvs((it)->mPvs);
2556	return pvs.GetSize();
2557	}*/
2558
2559	inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
2560	{
2561	return pvs1.SubtractPvs(pvs2);
2562	}
2563
2564
2565	float GetShuffledVcCost(BspLeaf leaf, BspViewCell vc1, BspViewCell *vc2)
2566	{
2567	//const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
2568	const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
2569	const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
2570
2571	const float area1 = vc1->GetArea() - leaf->mArea;
2572	const float area2 = vc2->GetArea() + leaf->mArea;
2573
2574	const float cost1 = pvs1 * area1;
2575	const float cost2 = pvs2 * area2;
2576
2577	return cost1 + cost2;
2578	}
2579
2580
2581	void VspBspTree::ShuffleLeaf(BspLeaf *leaf,
2582	BspViewCell *vc1,
2583	BspViewCell *vc2) const
2584	{
2585	// compute new pvs and area
2586	vc1->GetPvs().SubtractPvs(*leaf->mPvs);
2587	vc2->GetPvs().AddPvs(*leaf->mPvs);
2588
2589	vc1->SetArea(vc1->GetArea() - leaf->mArea);
2590	vc2->SetArea(vc2->GetArea() + leaf->mArea);
2591
2592	/// add to second view cell
2593	vc2->mLeaves.push_back(leaf);
2594
2595	// erase leaf from old view cell
2596	vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
2597
2598	for (; *it != leaf; ++ it);
2599	vc1->mLeaves.erase(it);
2600
2601	/*vc1->GetPvs().mEntries.clear();
2602	for (; it != vc1->mLeaves.end(); ++ it)
2603	{
2604	if (*it == leaf)
2605	vc1->mLeaves.erase(it);
2606	else
2607	vc1->GetPvs().AddPvs((it)->mPvs);
2608	}*/
2609
2610	leaf->SetViewCell(vc2); // finally change view cell
2611
2612	//Debug << "new pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize()
2613	// << " (" << vc1->GetPvs().GetSize() << ", " << vc2->GetPvs().GetSize() << ")" << endl;
2614
2615	}
2616
2617
2618	bool VspBspTree::ShuffleLeaves(BspLeaf leaf1, BspLeaf leaf2) const
2619	{
2620	BspViewCell *vc1 = leaf1->GetViewCell();
2621	BspViewCell *vc2 = leaf2->GetViewCell();
2622
2623	const float cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
2624	const float cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
2625
2626	const float oldCost = cost1 + cost2;
2627
2628	float shuffledCost1 = Limits::Infinity;
2629	float shuffledCost2 = Limits::Infinity;
2630
2631	// the view cell should not be empty after the shuffle
2632	if (vc1->mLeaves.size() > 1)
2633	shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
2634	if (vc2->mLeaves.size() > 1)
2635	shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
2636
2637	// shuffling unsuccessful
2638	if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
2639	return false;
2640
2641	if (shuffledCost1 < shuffledCost2)
2642	{
2643	//Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost1 << endl;
2644	ShuffleLeaf(leaf1, vc1, vc2);
2645	leaf1->Mail();
2646	}
2647	else
2648	{
2649	//Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost2 << endl;
2650	ShuffleLeaf(leaf2, vc2, vc1);
2651	leaf2->Mail();
2652	}
2653
2654	return true;
2655	}
2656
2657	bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
2658	{
2659	BspNode *node = mRoot;
2660
2661	while (1)
2662	{
2663	// early exit
2664	if (node->TreeValid())
2665	return true;
2666
2667	if (node->IsLeaf())
2668	return false;
2669
2670	BspInterior in = dynamic_cast<BspInterior >(node);
2671
2672	if (in->GetPlane().Side(viewPoint) <= 0)
2673	{
2674	node = in->GetBack();
2675	}
2676	else
2677	{
2678	node = in->GetFront();
2679	}
2680	}
2681
2682	// should never come here
2683	return false;
2684	}
2685
2686
2687	bool VspBspTree::CheckValid(const VspBspTraversalData &data) const
2688	{
2689	return data.mPvs <= mMaxPvs;
2690	}
2691
2692
2693	void VspBspTree::PropagateUpValidity(BspNode *node)
2694	{
2695	while (!node->IsRoot() && node->GetParent()->TreeValid())
2696	{
2697	node = node->GetParent();
2698	node->SetTreeValid(false);
2699	}
2700	}
2701
2702
2703	bool VspBspTree::Export(ofstream &stream)
2704	{
2705	ExportNode(mRoot, stream);
2706
2707	return true;
2708	}
2709
2710
2711	void VspBspTree::ExportNode(BspNode *node, ofstream &stream)
2712	{
2713	if (node->IsLeaf())
2714	{
2715	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2716
2717	int id = -1;
2718	if (leaf->GetViewCell() != mOutOfBoundsCell)
2719	id = leaf->GetViewCell()->GetId();
2720
2721	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
2722	}
2723	else
2724	{
2725	BspInterior interior = dynamic_cast<BspInterior >(node);
2726
2727	Plane3 plane = interior->GetPlane();
2728	stream << "<Interior plane=\"" << plane.mNormal.x << " "
2729	<< plane.mNormal.y << " " << plane.mNormal.z << " "
2730	<< plane.mD << "\">" << endl;
2731
2732	ExportNode(interior->GetBack(), stream);
2733	ExportNode(interior->GetFront(), stream);
2734
2735	stream << "</Interior>" << endl;
2736	}
2737	}
2738
2739	/************************************************************************/
2740	/* BspMergeCandidate implementation */
2741	/************************************************************************/
2742
2743
2744	BspMergeCandidate::BspMergeCandidate(BspLeaf l1, BspLeaf l2):
2745	mMergeCost(0),
2746	mLeaf1(l1),
2747	mLeaf2(l2),
2748	mLeaf1Id(l1->GetViewCell()->mMailbox),
2749	mLeaf2Id(l2->GetViewCell()->mMailbox)
2750	{
2751	EvalMergeCost();
2752	}
2753
2754	float BspMergeCandidate::GetCost(ViewCell *vc) const
2755	{
2756	return vc->GetPvs().GetSize() * vc->GetArea();
2757	}
2758
2759	float BspMergeCandidate::GetLeaf1Cost() const
2760	{
2761	BspViewCell *vc = mLeaf1->GetViewCell();
2762	return GetCost(vc);
2763	}
2764
2765	float BspMergeCandidate::GetLeaf2Cost() const
2766	{
2767	BspViewCell *vc = mLeaf2->GetViewCell();
2768	return GetCost(vc);
2769	}
2770
2771	void BspMergeCandidate::EvalMergeCost()
2772	{
2773	//-- compute pvs difference
2774	BspViewCell *vc1 = mLeaf1->GetViewCell();
2775	BspViewCell *vc2 = mLeaf2->GetViewCell();
2776
2777	const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
2778	const int newPvs = diff1 + vc1->GetPvs().GetSize();
2779
2780	//-- compute ratio of old cost
2781	//-- (added size of left and right view cell times pvs size)
2782	//-- to new rendering cost (size of merged view cell times pvs size)
2783	const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
2784
2785	const float newCost =
2786	(float)newPvs * (vc1->GetArea() + vc2->GetArea());
2787
2788	mMergeCost = newCost - oldCost;
2789	// if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
2790	// mMergeCost += 1.0;
2791	}
2792
2793	void BspMergeCandidate::SetLeaf1(BspLeaf *l)
2794	{
2795	mLeaf1 = l;
2796	}
2797
2798	void BspMergeCandidate::SetLeaf2(BspLeaf *l)
2799	{
2800	mLeaf2 = l;
2801	}
2802
2803	BspLeaf *BspMergeCandidate::GetLeaf1()
2804	{
2805	return mLeaf1;
2806	}
2807
2808	BspLeaf *BspMergeCandidate::GetLeaf2()
2809	{
2810	return mLeaf2;
2811	}
2812
2813	bool BspMergeCandidate::Valid() const
2814	{
2815	return
2816	(mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
2817	(mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
2818	}
2819
2820	float BspMergeCandidate::GetMergeCost() const
2821	{
2822	return mMergeCost;
2823	}
2824
2825	void BspMergeCandidate::SetValid()
2826	{
2827	mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
2828	mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
2829
2830	EvalMergeCost();
2831	}
2832
2833
2834	/************************************************************************/
2835	/* MergeStatistics implementation */
2836	/************************************************************************/
2837
2838
2839	void MergeStatistics::Print(ostream &app) const
2840	{
2841	app << "===== Merge statistics ===============\n";
2842
2843	app << setprecision(4);
2844
2845	app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
2846
2847	app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
2848
2849	app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
2850
2851	app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
2852
2853	app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
2854
2855	app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
2856	app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
2857
2858	app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
2859
2860	app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
2861
2862	app << "===== END OF BspTree statistics ==========\n";
2863	}

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

Download in other formats: