Context Navigation

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

Revision 517, 68.7 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
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	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	else
2087	mRoot = leaf;
2088
2089	++ collapsed;
2090	delete interior;
2091
2092	return leaf;
2093	}
2094	}
2095
2096	return node;
2097	}
2098
2099
2100	int VspBspTree::CollapseTree()
2101	{
2102	int collapsed = 0;
2103
2104	(void)CollapseTree(mRoot, collapsed);
2105
2106	// revalidate leaves
2107	RepairViewCellsLeafLists();
2108
2109	return collapsed;
2110	}
2111
2112
2113	void VspBspTree::RepairViewCellsLeafLists()
2114	{
2115	// list not valid anymore => clear
2116	stack<BspNode *> nodeStack;
2117	nodeStack.push(mRoot);
2118
2119	ViewCell::NewMail();
2120
2121	while (!nodeStack.empty())
2122	{
2123	BspNode *node = nodeStack.top();
2124	nodeStack.pop();
2125
2126	if (node->IsLeaf())
2127	{
2128	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2129
2130	BspViewCell *viewCell = leaf->GetViewCell();
2131
2132	if (!viewCell->Mailed())
2133	{
2134	viewCell->mLeaves.clear();
2135	viewCell->Mail();
2136	}
2137
2138	viewCell->mLeaves.push_back(leaf);
2139	}
2140	else
2141	{
2142	BspInterior interior = dynamic_cast<BspInterior >(node);
2143
2144	nodeStack.push(interior->GetFront());
2145	nodeStack.push(interior->GetBack());
2146	}
2147	}
2148	}
2149
2150
2151	bool VspBspTree::MergeViewCells(BspLeaf l1, BspLeaf l2) const
2152	{
2153	//-- change pointer to view cells of all leaves associated
2154	//-- with the previous view cells
2155	BspViewCell *fVc = l1->GetViewCell();
2156	BspViewCell *bVc = l2->GetViewCell();
2157
2158	BspViewCell vc = dynamic_cast<BspViewCell >(
2159	mViewCellsManager->MergeViewCells(fVc, bVc));
2160
2161	// if merge was unsuccessful
2162	if (!vc) return false;
2163
2164	// set new size of view cell
2165	vc->SetArea(fVc->GetArea() + bVc->GetArea());
2166
2167	vector<BspLeaf *> fLeaves = fVc->mLeaves;
2168	vector<BspLeaf *> bLeaves = bVc->mLeaves;
2169
2170	vector<BspLeaf *>::const_iterator it;
2171
2172	//-- change view cells of all the other leaves the view cell belongs to
2173	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
2174	{
2175	(*it)->SetViewCell(vc);
2176	vc->mLeaves.push_back(*it);
2177	}
2178
2179	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
2180	{
2181	(*it)->SetViewCell(vc);
2182	vc->mLeaves.push_back(*it);
2183	}
2184
2185	vc->Mail();
2186
2187	// clean up old view cells
2188	DEL_PTR(fVc);
2189	DEL_PTR(bVc);
2190
2191	return true;
2192	}
2193
2194
2195	void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
2196	{
2197	mViewCellsManager = vcm;
2198	}
2199
2200
2201	int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves)
2202	{
2203	BspLeaf::NewMail();
2204
2205	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2206
2207	int candidates = 0;
2208
2209	// find merge candidates and push them into queue
2210	for (it = leaves.begin(); it != it_end; ++ it)
2211	{
2212	BspLeaf leaf = it;
2213
2214	/// create leaf pvs (needed for post processing
2215	leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
2216
2217	BspMergeCandidate::sOverallCost +=
2218	leaf->mArea * leaf->mPvs->GetSize();
2219
2220	// the same leaves must not be part of two merge candidates
2221	leaf->Mail();
2222	vector<BspLeaf *> neighbors;
2223	FindNeighbors(leaf, neighbors, true);
2224
2225	vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
2226
2227	// TODO: test if at least one ray goes from one leaf to the other
2228	for (nit = neighbors.begin(); nit != nit_end; ++ nit)
2229	{
2230	if ((*nit)->GetViewCell() != leaf->GetViewCell())
2231	{
2232	mMergeQueue.push(BspMergeCandidate(leaf, *nit));
2233	++ candidates;
2234	}
2235	}
2236	}
2237
2238	Debug << "found " << candidates << " new merge candidates" << endl;
2239
2240	return (int)leaves.size();
2241	}
2242
2243
2244	int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays)
2245	{
2246	vector<BspRay *> bspRays;
2247
2248	long startTime = GetTime();
2249	ConstructBspRays(bspRays, rays);
2250	Debug << (int)bspRays.size() << " bsp rays constructed in "
2251	<< TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
2252
2253	map<BspLeaf , vector<BspLeaf> > neighborMap;
2254	vector<BspIntersection>::const_iterator iit;
2255
2256	int numLeaves = 0;
2257
2258	BspLeaf::NewMail();
2259
2260	for (int i = 0; i < (int)bspRays.size(); ++ i)
2261	{
2262	BspRay *ray = bspRays[i];
2263
2264	// traverse leaves stored in the rays and compare and
2265	// merge consecutive leaves (i.e., the neighbors in the tree)
2266	if (ray->intersections.size() < 2)
2267	continue;
2268
2269	iit = ray->intersections.begin();
2270	BspLeaf leaf = ((iit ++)).mLeaf;
2271
2272	// create leaf pvs (needed for post processing)
2273	if (!leaf->mPvs)
2274	{
2275	leaf->mPvs =
2276	new ObjectPvs(leaf->GetViewCell()->GetPvs());
2277
2278	BspMergeCandidate::sOverallCost +=
2279	leaf->mArea * leaf->mPvs->GetSize();
2280
2281	++ numLeaves;
2282	}
2283
2284	// traverse intersections
2285	// consecutive leaves are neighbors => add them to queue
2286	for (; iit != ray->intersections.end(); ++ iit)
2287	{
2288	// next pair
2289	BspLeaf *prevLeaf = leaf;
2290	leaf = (*iit).mLeaf;
2291
2292	// view space not valid or same view cell
2293	if (!leaf->TreeValid() \|\| !prevLeaf->TreeValid() \|\|
2294	(leaf->GetViewCell() == prevLeaf->GetViewCell()))
2295	continue;
2296
2297	// create leaf pvs (needed for post processing)
2298	if (!leaf->mPvs)
2299	{
2300	leaf->mPvs =
2301	new ObjectPvs(leaf->GetViewCell()->GetPvs());
2302
2303	BspMergeCandidate::sOverallCost +=
2304	leaf->mArea * leaf->mPvs->GetSize();
2305
2306	++ numLeaves;
2307	}
2308
2309	vector<BspLeaf *> &neighbors = neighborMap[leaf];
2310
2311	bool found = false;
2312
2313	// both leaves inserted in queue already =>
2314	// look if double pair already exists
2315	if (leaf->Mailed() && prevLeaf->Mailed())
2316	{
2317	vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
2318
2319	for (it = neighbors.begin(); !found && (it != it_end); ++ it)
2320	if (*it == prevLeaf)
2321	found = true; // already in queue
2322	}
2323
2324	if (!found)
2325	{
2326	// this pair is not in map already
2327	// => insert into the neighbor map and the queue
2328	neighbors.push_back(prevLeaf);
2329	neighborMap[prevLeaf].push_back(leaf);
2330
2331	leaf->Mail();
2332	prevLeaf->Mail();
2333
2334	mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf));
2335	}
2336	}
2337	}
2338	Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
2339	Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
2340	Debug << "leaves in queue: " << numLeaves << endl;
2341	Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
2342
2343	CLEAR_CONTAINER(bspRays);
2344
2345	//-- collect the leaves which haven't been found by ray casting
2346	vector<BspLeaf *> leaves;
2347	CollectLeaves(leaves, true, mMaxPvs);
2348	Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
2349	// TODO
2350	CollectMergeCandidates(leaves);
2351
2352	return numLeaves;
2353	}
2354
2355
2356	void VspBspTree::ConstructBspRays(vector<BspRay *> &bspRays,
2357	const VssRayContainer &rays)
2358	{
2359	VssRayContainer::const_iterator it, it_end = rays.end();
2360
2361	for (it = rays.begin(); it != rays.end(); ++ it)
2362	{
2363	VssRay vssRay = it;
2364	BspRay *ray = new BspRay(vssRay);
2365
2366	ViewCellContainer viewCells;
2367
2368	Ray hray(*vssRay);
2369	float tmin = 0, tmax = 1.0;
2370	// matt TODO: remove this!!
2371	//hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
2372	if (!mBox.GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
2373	continue;
2374
2375	Vector3 origin = hray.Extrap(tmin);
2376	Vector3 termination = hray.Extrap(tmax);
2377
2378	// cast line segment to get intersections with bsp leaves
2379	CastLineSegment(origin, termination, viewCells);
2380
2381	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2382	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2383	{
2384	BspViewCell vc = dynamic_cast<BspViewCell >(*vit);
2385	vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
2386	//NOTE: not sorted!
2387	for (it = vc->mLeaves.begin(); it != it_end; ++ it)
2388	ray->intersections.push_back(BspIntersection(0, *it));
2389	}
2390
2391	bspRays.push_back(ray);
2392	}
2393	}
2394
2395
2396	int VspBspTree::MergeViewCells(const VssRayContainer &rays)
2397	{
2398	MergeStatistics mergeStats;
2399	mergeStats.Start();
2400	// TODO: REMOVE LATER for performance!
2401	const bool showMergeStats = true;
2402	//BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs;
2403	long startTime = GetTime();
2404
2405	if (mUseRaysForMerge)
2406	mergeStats.nodes = CollectMergeCandidates(rays);
2407	else
2408	{
2409	vector<BspLeaf *> leaves;
2410	CollectLeaves(leaves);
2411	mergeStats.nodes = CollectMergeCandidates(leaves);
2412	}
2413
2414	mergeStats.collectTime = TimeDiff(startTime, GetTime());
2415	mergeStats.candidates = (int)mMergeQueue.size();
2416	startTime = GetTime();
2417
2418	int nViewCells = /mergeStats.nodes/ mStat.Leaves() - mStat.invalidLeaves;
2419
2420	//-- use priority queue to merge leaf pairs
2421	while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) &&
2422	(mMergeQueue.top().GetMergeCost() <
2423	mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
2424	{
2425	//Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
2426	// << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost
2427	// << " max ratio: " << mMergeMaxCostRatio << endl;
2428	BspMergeCandidate mc = mMergeQueue.top();
2429	mMergeQueue.pop();
2430
2431	// both view cells equal!
2432	if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
2433	continue;
2434
2435	if (mc.Valid())
2436	{
2437	ViewCell::NewMail();
2438	MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
2439	-- nViewCells;
2440
2441	++ mergeStats.merged;
2442
2443	// increase absolute merge cost
2444	BspMergeCandidate::sOverallCost += mc.GetMergeCost();
2445
2446	if (showMergeStats)
2447	{
2448	if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
2449	++ mergeStats.siblings;
2450
2451	const int dist =
2452	TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
2453	if (dist > mergeStats.maxTreeDist)
2454	mergeStats.maxTreeDist = dist;
2455	mergeStats.accTreeDist += dist;
2456	}
2457	}
2458	// merge candidate not valid, because one of the leaves was already
2459	// merged with another one => validate and reinsert into queue
2460	else
2461	{
2462	mc.SetValid();
2463	mMergeQueue.push(mc);
2464	}
2465	}
2466
2467	mergeStats.mergeTime = TimeDiff(startTime, GetTime());
2468	mergeStats.Stop();
2469
2470	if (showMergeStats)
2471	Debug << mergeStats << endl << endl;
2472
2473	//TODO: should return sample contributions?
2474	return mergeStats.merged;
2475	}
2476
2477
2478	ViewCell *VspBspTree::GetViewCell(const Vector3 &point)
2479	{
2480	if (mRoot == NULL)
2481	return NULL;
2482
2483	stack<BspNode *> nodeStack;
2484	nodeStack.push(mRoot);
2485
2486	ViewCell *viewcell = NULL;
2487
2488	while (!nodeStack.empty()) {
2489	BspNode *node = nodeStack.top();
2490	nodeStack.pop();
2491
2492	if (node->IsLeaf()) {
2493	viewcell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
2494	break;
2495	} else {
2496
2497	BspInterior interior = dynamic_cast<BspInterior >(node);
2498
2499	// random decision
2500	if (interior->GetPlane().Side(point) < 0)
2501	nodeStack.push(interior->GetBack());
2502	else
2503	nodeStack.push(interior->GetFront());
2504	}
2505	}
2506
2507	return viewcell;
2508	}
2509
2510
2511	int VspBspTree::RefineViewCells(const VssRayContainer &rays)
2512	{
2513	int shuffled = 0;
2514
2515	Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
2516	BspLeaf::NewMail();
2517
2518	// Use priority queue of remaining leaf pairs
2519	// These candidates either share the same view cells or
2520	// are border leaves which share a boundary.
2521	// We test if they can be shuffled, i.e.,
2522	// either one leaf is made part of one view cell or the other
2523	// leaf is made part of the other view cell. It is tested if the
2524	// remaining view cells are "better" than the old ones.
2525	while (!mMergeQueue.empty())
2526	{
2527	BspMergeCandidate mc = mMergeQueue.top();
2528	mMergeQueue.pop();
2529
2530	// both view cells equal or already shuffled
2531	if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) \|\|
2532	(mc.GetLeaf1()->Mailed()) \|\| (mc.GetLeaf2()->Mailed()))
2533	continue;
2534
2535	// candidate for shuffling
2536	const bool wasShuffled =
2537	ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
2538
2539	//-- stats
2540	if (wasShuffled)
2541	++ shuffled;
2542	}
2543
2544	return shuffled;
2545	}
2546
2547
2548	inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
2549	{
2550	return pvs1.AddPvs(pvs2);
2551	}
2552
2553	/inline int SubtractedPvsSize(BspViewCell vc, BspLeaf *l, const ObjectPvs &pvs2)
2554	{
2555	ObjectPvs pvs;
2556	vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
2557	for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
2558	if (*it != l)
2559	pvs.AddPvs((it)->mPvs);
2560	return pvs.GetSize();
2561	}*/
2562
2563	inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
2564	{
2565	return pvs1.SubtractPvs(pvs2);
2566	}
2567
2568
2569	float GetShuffledVcCost(BspLeaf leaf, BspViewCell vc1, BspViewCell *vc2)
2570	{
2571	//const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
2572	const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
2573	const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
2574
2575	const float area1 = vc1->GetArea() - leaf->mArea;
2576	const float area2 = vc2->GetArea() + leaf->mArea;
2577
2578	const float cost1 = pvs1 * area1;
2579	const float cost2 = pvs2 * area2;
2580
2581	return cost1 + cost2;
2582	}
2583
2584
2585	void VspBspTree::ShuffleLeaf(BspLeaf *leaf,
2586	BspViewCell *vc1,
2587	BspViewCell *vc2) const
2588	{
2589	// compute new pvs and area
2590	vc1->GetPvs().SubtractPvs(*leaf->mPvs);
2591	vc2->GetPvs().AddPvs(*leaf->mPvs);
2592
2593	vc1->SetArea(vc1->GetArea() - leaf->mArea);
2594	vc2->SetArea(vc2->GetArea() + leaf->mArea);
2595
2596	/// add to second view cell
2597	vc2->mLeaves.push_back(leaf);
2598
2599	// erase leaf from old view cell
2600	vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
2601
2602	for (; *it != leaf; ++ it);
2603	vc1->mLeaves.erase(it);
2604
2605	/*vc1->GetPvs().mEntries.clear();
2606	for (; it != vc1->mLeaves.end(); ++ it)
2607	{
2608	if (*it == leaf)
2609	vc1->mLeaves.erase(it);
2610	else
2611	vc1->GetPvs().AddPvs((it)->mPvs);
2612	}*/
2613
2614	leaf->SetViewCell(vc2); // finally change view cell
2615
2616	//Debug << "new pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize()
2617	// << " (" << vc1->GetPvs().GetSize() << ", " << vc2->GetPvs().GetSize() << ")" << endl;
2618
2619	}
2620
2621
2622	bool VspBspTree::ShuffleLeaves(BspLeaf leaf1, BspLeaf leaf2) const
2623	{
2624	BspViewCell *vc1 = leaf1->GetViewCell();
2625	BspViewCell *vc2 = leaf2->GetViewCell();
2626
2627	const float cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
2628	const float cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
2629
2630	const float oldCost = cost1 + cost2;
2631
2632	float shuffledCost1 = Limits::Infinity;
2633	float shuffledCost2 = Limits::Infinity;
2634
2635	// the view cell should not be empty after the shuffle
2636	if (vc1->mLeaves.size() > 1)
2637	shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
2638	if (vc2->mLeaves.size() > 1)
2639	shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
2640
2641	// shuffling unsuccessful
2642	if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
2643	return false;
2644
2645	if (shuffledCost1 < shuffledCost2)
2646	{
2647	//Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost1 << endl;
2648	ShuffleLeaf(leaf1, vc1, vc2);
2649	leaf1->Mail();
2650	}
2651	else
2652	{
2653	//Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost2 << endl;
2654	ShuffleLeaf(leaf2, vc2, vc1);
2655	leaf2->Mail();
2656	}
2657
2658	return true;
2659	}
2660
2661	bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
2662	{
2663	BspNode *node = mRoot;
2664
2665	while (1)
2666	{
2667	// early exit
2668	if (node->TreeValid())
2669	return true;
2670
2671	if (node->IsLeaf())
2672	return false;
2673
2674	BspInterior in = dynamic_cast<BspInterior >(node);
2675
2676	if (in->GetPlane().Side(viewPoint) <= 0)
2677	{
2678	node = in->GetBack();
2679	}
2680	else
2681	{
2682	node = in->GetFront();
2683	}
2684	}
2685
2686	// should never come here
2687	return false;
2688	}
2689
2690
2691	bool VspBspTree::CheckValid(const VspBspTraversalData &data) const
2692	{
2693	return data.mPvs <= mMaxPvs;
2694	}
2695
2696
2697	void VspBspTree::PropagateUpValidity(BspNode *node)
2698	{
2699	while (!node->IsRoot() && node->GetParent()->TreeValid())
2700	{
2701	node = node->GetParent();
2702	node->SetTreeValid(false);
2703	}
2704	}
2705
2706
2707	bool VspBspTree::Export(ofstream &stream)
2708	{
2709	ExportNode(mRoot, stream);
2710
2711	return true;
2712	}
2713
2714
2715	void VspBspTree::ExportNode(BspNode *node, ofstream &stream)
2716	{
2717	if (node->IsLeaf())
2718	{
2719	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2720
2721	int id = -1;
2722	if (leaf->GetViewCell() != mOutOfBoundsCell)
2723	id = leaf->GetViewCell()->GetId();
2724
2725	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
2726	}
2727	else
2728	{
2729	BspInterior interior = dynamic_cast<BspInterior >(node);
2730
2731	Plane3 plane = interior->GetPlane();
2732	stream << "<Interior plane=\"" << plane.mNormal.x << " "
2733	<< plane.mNormal.y << " " << plane.mNormal.z << " "
2734	<< plane.mD << "\">" << endl;
2735
2736	ExportNode(interior->GetBack(), stream);
2737	ExportNode(interior->GetFront(), stream);
2738
2739	stream << "</Interior>" << endl;
2740	}
2741	}
2742
2743	/************************************************************************/
2744	/* BspMergeCandidate implementation */
2745	/************************************************************************/
2746
2747
2748	BspMergeCandidate::BspMergeCandidate(BspLeaf l1, BspLeaf l2):
2749	mMergeCost(0),
2750	mLeaf1(l1),
2751	mLeaf2(l2),
2752	mLeaf1Id(l1->GetViewCell()->mMailbox),
2753	mLeaf2Id(l2->GetViewCell()->mMailbox)
2754	{
2755	EvalMergeCost();
2756	}
2757
2758	float BspMergeCandidate::GetCost(ViewCell *vc) const
2759	{
2760	return vc->GetPvs().GetSize() * vc->GetArea();
2761	}
2762
2763	float BspMergeCandidate::GetLeaf1Cost() const
2764	{
2765	BspViewCell *vc = mLeaf1->GetViewCell();
2766	return GetCost(vc);
2767	}
2768
2769	float BspMergeCandidate::GetLeaf2Cost() const
2770	{
2771	BspViewCell *vc = mLeaf2->GetViewCell();
2772	return GetCost(vc);
2773	}
2774
2775	void BspMergeCandidate::EvalMergeCost()
2776	{
2777	//-- compute pvs difference
2778	BspViewCell *vc1 = mLeaf1->GetViewCell();
2779	BspViewCell *vc2 = mLeaf2->GetViewCell();
2780
2781	const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
2782	const int newPvs = diff1 + vc1->GetPvs().GetSize();
2783
2784	//-- compute ratio of old cost
2785	//-- (added size of left and right view cell times pvs size)
2786	//-- to new rendering cost (size of merged view cell times pvs size)
2787	const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
2788
2789	const float newCost =
2790	(float)newPvs * (vc1->GetArea() + vc2->GetArea());
2791
2792	mMergeCost = newCost - oldCost;
2793	// if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
2794	// mMergeCost += 1.0;
2795	}
2796
2797	void BspMergeCandidate::SetLeaf1(BspLeaf *l)
2798	{
2799	mLeaf1 = l;
2800	}
2801
2802	void BspMergeCandidate::SetLeaf2(BspLeaf *l)
2803	{
2804	mLeaf2 = l;
2805	}
2806
2807	BspLeaf *BspMergeCandidate::GetLeaf1()
2808	{
2809	return mLeaf1;
2810	}
2811
2812	BspLeaf *BspMergeCandidate::GetLeaf2()
2813	{
2814	return mLeaf2;
2815	}
2816
2817	bool BspMergeCandidate::Valid() const
2818	{
2819	return
2820	(mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
2821	(mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
2822	}
2823
2824	float BspMergeCandidate::GetMergeCost() const
2825	{
2826	return mMergeCost;
2827	}
2828
2829	void BspMergeCandidate::SetValid()
2830	{
2831	mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
2832	mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
2833
2834	EvalMergeCost();
2835	}
2836
2837
2838	/************************************************************************/
2839	/* MergeStatistics implementation */
2840	/************************************************************************/
2841
2842
2843	void MergeStatistics::Print(ostream &app) const
2844	{
2845	app << "===== Merge statistics ===============\n";
2846
2847	app << setprecision(4);
2848
2849	app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
2850
2851	app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
2852
2853	app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
2854
2855	app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
2856
2857	app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
2858
2859	app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
2860	app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
2861
2862	app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
2863
2864	app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
2865
2866	app << "===== END OF BspTree statistics ==========\n";
2867	}

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

Download in other formats: