Context Navigation

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

Revision 538, 70.8 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: