Context Navigation

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

Revision 609, 72.6 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: