Context Navigation

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

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

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

Download in other formats: