Context Navigation

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

Revision 489, 65.2 KB checked in by mattausch, 19 years ago (diff)
valid view point regions working now for bsp view cells (crit: maxpvs)

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

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

Download in other formats: