Context Navigation

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

Revision 604, 71.7 KB checked in by mattausch, 18 years ago (diff)
fixed statistics

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

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

Download in other formats: