Context Navigation

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

Revision 573, 85.8 KB checked in by mattausch, 18 years ago (diff)
implemented functtion for view cell construction

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

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

Download in other formats: