Context Navigation

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

Revision 487, 64.4 KB checked in by mattausch, 19 years ago (diff)
fixed bug in raycasting added valid view point regions, get view point only from valid regions

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

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

Download in other formats: