Context Navigation

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

Revision 501, 68.2 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: