Context Navigation

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

Revision 492, 68.1 KB checked in by bittner, 19 years ago (diff)
Large merge - viewcells seem not functional now

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

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

Download in other formats: