Context Navigation

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

Revision 509, 68.6 KB checked in by mattausch, 19 years ago (diff)

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

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

Download in other formats: