Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp @ 433

Revision 433, 63.1 KB checked in by mattausch, 19 years ago (diff)
changed tabs

Line
1	#include "Plane3.h"
2	#include "ViewCellBsp.h"
3	#include "Mesh.h"
4	#include "common.h"
5	#include "ViewCell.h"
6	#include "Environment.h"
7	#include "Polygon3.h"
8	#include "Ray.h"
9	#include "AxisAlignedBox3.h"
10	#include <stack>
11	#include <time.h>
12	#include <iomanip>
13	#include "Exporter.h"
14	#include "Plane3.h"
15
16	//-- static members
17
18	int BspNode::sMailId = 1;
19
20	/** Evaluates split plane classification with respect to the plane's
21	contribution for a minimum number splits in the tree.
22	*/
23	const float BspTree::sLeastPolySplitsTable[] = {0, 0, 1, 0};
24	/** Evaluates split plane classification with respect to the plane's
25	contribution for a balanced tree.
26	*/
27	const float BspTree::sBalancedPolysTable[] = {1, -1, 0, 0};
28
29	/** Evaluates split plane classification with respect to the plane's
30	contribution for a minimum number of ray splits.
31	*/
32	const float BspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
33	/** Evaluates split plane classification with respect to the plane's
34	contribution for balanced rays.
35	*/
36	const float BspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
37
38	int BspTree::sConstructionMethod = FROM_INPUT_VIEW_CELLS;
39
40	int BspTree::sFrontId = 0;
41	int BspTree::sBackId = 0;
42	int BspTree::sFrontAndBackId = 0;
43
44	/****************************************************************/
45	/* class BspNode implementation */
46	/****************************************************************/
47
48	BspNode::BspNode():
49	mParent(NULL)
50	{}
51
52	BspNode::BspNode(BspInterior *parent):
53	mParent(parent)
54	{}
55
56
57	bool BspNode::IsRoot() const
58	{
59	return mParent == NULL;
60	}
61
62	BspInterior *BspNode::GetParent()
63	{
64	return mParent;
65	}
66
67	void BspNode::SetParent(BspInterior *parent)
68	{
69	mParent = parent;
70	}
71
72	/****************************************************************/
73	/* class BspInterior implementation */
74	/****************************************************************/
75
76
77	BspInterior::BspInterior(const Plane3 &plane):
78	mPlane(plane), mFront(NULL), mBack(NULL)
79	{}
80
81	BspInterior::~BspInterior()
82	{
83	DEL_PTR(mFront);
84	DEL_PTR(mBack);
85	}
86
87	bool BspInterior::IsLeaf() const
88	{
89	return false;
90	}
91
92	BspNode *BspInterior::GetBack()
93	{
94	return mBack;
95	}
96
97	BspNode *BspInterior::GetFront()
98	{
99	return mFront;
100	}
101
102	Plane3 *BspInterior::GetPlane()
103	{
104	return &mPlane;
105	}
106
107	void BspInterior::ReplaceChildLink(BspNode oldChild, BspNode newChild)
108	{
109	if (mBack == oldChild)
110	mBack = newChild;
111	else
112	mFront = newChild;
113	}
114
115	void BspInterior::SetupChildLinks(BspNode b, BspNode f)
116	{
117	mBack = b;
118	mFront = f;
119	}
120
121	int BspInterior::SplitPolygons(PolygonContainer &polys,
122	PolygonContainer &frontPolys,
123	PolygonContainer &backPolys,
124	PolygonContainer &coincident)
125	{
126	Polygon3 *splitPoly = NULL;
127
128	int splits = 0;
129
130	#ifdef _Debug
131	Debug << "splitting polygons of node " << this << " with plane " << mPlane << endl;
132	#endif
133	while (!polys.empty())
134	{
135	Polygon3 *poly = polys.back();
136	polys.pop_back();
137
138	//Debug << "New polygon with plane: " << poly->GetSupportingPlane() << "\n";
139
140	// classify polygon
141	const int cf = poly->ClassifyPlane(mPlane);
142
143	Polygon3 *front_piece = NULL;
144	Polygon3 *back_piece = NULL;
145
146	VertexContainer splitVertices;
147
148	switch (cf)
149	{
150	case Polygon3::COINCIDENT:
151	coincident.push_back(poly);
152	break;
153	case Polygon3::FRONT_SIDE:
154	frontPolys.push_back(poly);
155	break;
156	case Polygon3::BACK_SIDE:
157	backPolys.push_back(poly);
158	break;
159	case Polygon3::SPLIT:
160	front_piece = new Polygon3(poly->mParent);
161	back_piece = new Polygon3(poly->mParent);
162
163	//-- split polygon into front and back part
164	poly->Split(mPlane,
165	*front_piece,
166	*back_piece,
167	splitVertices);
168
169	++ splits; // increase number of splits
170
171	//-- inherit rays from parent polygon for blocked ray criterium
172	poly->InheritRays(front_piece, back_piece);
173	//Debug << "p: " << poly->mPiercingRays.size() << " f: " << front_piece->mPiercingRays.size() << " b: " << back_piece->mPiercingRays.size() << endl;
174
175	// check if polygons still valid
176	if (front_piece->Valid())
177	frontPolys.push_back(front_piece);
178	else
179	DEL_PTR(front_piece);
180
181	if (back_piece->Valid())
182	backPolys.push_back(back_piece);
183	else
184	DEL_PTR(back_piece);
185
186	#ifdef _DEBUG
187	Debug << "split " << poly << endl << front_piece << endl << *back_piece << endl;
188	#endif
189	DEL_PTR(poly);
190	break;
191	default:
192	Debug << "SHOULD NEVER COME HERE\n";
193	break;
194	}
195	}
196
197	return splits;
198	}
199
200	/****************************************************************/
201	/* class BspLeaf implementation */
202	/****************************************************************/
203	BspLeaf::BspLeaf(): mViewCell(NULL)
204	{
205	}
206
207	BspLeaf::BspLeaf(BspViewCell *viewCell):
208	mViewCell(viewCell)
209	{
210	}
211
212	BspLeaf::BspLeaf(BspInterior *parent):
213	BspNode(parent), mViewCell(NULL)
214	{}
215
216	BspLeaf::BspLeaf(BspInterior parent, BspViewCell viewCell):
217	BspNode(parent), mViewCell(viewCell)
218	{
219	}
220
221	BspViewCell *BspLeaf::GetViewCell() const
222	{
223	return mViewCell;
224	}
225
226	void BspLeaf::SetViewCell(BspViewCell *viewCell)
227	{
228	mViewCell = viewCell;
229	}
230
231	bool BspLeaf::IsLeaf() const
232	{
233	return true;
234	}
235
236	void BspLeaf::AddToPvs(const BoundedRayContainer &rays,
237	int &sampleContributions,
238	int &contributingSamples,
239	bool storeLeavesWithRays)
240	{
241	sampleContributions = 0;
242	contributingSamples = 0;
243
244	BoundedRayContainer::const_iterator it, it_end = rays.end();
245
246	// add contributions from samples to the PVS
247	for (it = rays.begin(); it != it_end; ++ it)
248	{
249	int contribution = 0;
250	Ray ray = (it)->mRay;
251
252	if (!ray->intersections.empty())
253	contribution += mViewCell->GetPvs().AddSample(ray->intersections[0].mObject);
254
255	if (ray->sourceObject.mObject)
256	contribution += mViewCell->GetPvs().AddSample(ray->sourceObject.mObject);
257
258	if (contribution > 0)
259	{
260	sampleContributions += contribution;
261	++ contributingSamples;
262	}
263
264	if (storeLeavesWithRays)
265	// warning: intersections not ordered
266	ray->bspIntersections.push_back(Ray::BspIntersection((*it)->mMinT, this));
267	}
268	}
269
270
271	/****************************************************************/
272	/* class BspTree implementation */
273	/****************************************************************/
274
275	BspTree::BspTree(BspViewCell *viewCell):
276	mRootCell(viewCell),
277	mRoot(NULL),
278	mGenerateViewCells(false),
279	mStoreLeavesWithRays(false),
280	mPvsUseArea(true)
281	{
282	Randomize(); // initialise random generator for heuristics
283
284	//-- termination criteria for autopartition
285	environment->GetIntValue("BspTree.Termination.maxDepth", mTermMaxDepth);
286	environment->GetIntValue("BspTree.Termination.minPvs", mTermMinPvs);
287	environment->GetIntValue("BspTree.Termination.minPolygons", mTermMinPolys);
288	environment->GetIntValue("BspTree.Termination.minRays", mTermMinRays);
289	environment->GetFloatValue("BspTree.Termination.minArea", mTermMinArea);
290	environment->GetFloatValue("BspTree.Termination.maxRayContribution", mTermMaxRayContribution);
291	environment->GetFloatValue("BspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
292
293	//-- factors for bsp tree split plane heuristics
294	environment->GetFloatValue("BspTree.Factor.verticalSplits", mVerticalSplitsFactor);
295	environment->GetFloatValue("BspTree.Factor.largestPolyArea", mLargestPolyAreaFactor);
296	environment->GetFloatValue("BspTree.Factor.blockedRays", mBlockedRaysFactor);
297	environment->GetFloatValue("BspTree.Factor.leastRaySplits", mLeastRaySplitsFactor);
298	environment->GetFloatValue("BspTree.Factor.balancedRays", mBalancedRaysFactor);
299	environment->GetFloatValue("BspTree.Factor.pvsFactor", mPvsFactor);
300	environment->GetFloatValue("BspTree.Factor.leastSplits" , mLeastSplitsFactor);
301	environment->GetFloatValue("BspTree.Factor.balancedPolys", mBalancedPolysFactor);
302	environment->GetFloatValue("BspTree.Factor.balancedViewCells", mBalancedViewCellsFactor);
303	environment->GetFloatValue("BspTree.Termination.ct_div_ci", mCtDivCi);
304
305	//-- termination criteria for axis aligned split
306	environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", mAaCtDivCi);
307	environment->GetFloatValue("BspTree.Termination.AxisAligned.maxCostRatio", mMaxCostRatio);
308	environment->GetIntValue("BspTree.Termination.AxisAligned.minPolys",
309	mTermMinPolysForAxisAligned);
310	environment->GetIntValue("BspTree.Termination.AxisAligned.minRays",
311	mTermMinRaysForAxisAligned);
312	environment->GetIntValue("BspTree.Termination.AxisAligned.minObjects",
313	mTermMinObjectsForAxisAligned);
314	//-- partition criteria
315	environment->GetIntValue("BspTree.maxPolyCandidates", mMaxPolyCandidates);
316	environment->GetIntValue("BspTree.maxRayCandidates", mMaxRayCandidates);
317	environment->GetIntValue("BspTree.splitPlaneStrategy", mSplitPlaneStrategy);
318	environment->GetFloatValue("BspTree.AxisAligned.splitBorder", mSplitBorder);
319
320	environment->GetFloatValue("BspTree.Construction.sideTolerance", Vector3::sDistTolerance);
321	Vector3::sDistToleranceSqrt = Vector3::sDistTolerance * Vector3::sDistTolerance;
322
323	// post processing stuff
324	environment->GetIntValue("ViewCells.PostProcessing.minPvsDif", mMinPvsDif);
325	environment->GetIntValue("ViewCells.PostProcessing.minPvs", mMinPvs);
326	environment->GetIntValue("ViewCells.PostProcessing.maxPvs", mMaxPvs);
327
328	Debug << "BSP max depth: " << mTermMaxDepth << endl;
329	Debug << "BSP min PVS: " << mTermMinPvs << endl;
330	Debug << "BSP min area: " << mTermMinArea << endl;
331	Debug << "BSP max polys: " << mTermMinPolys << endl;
332	Debug << "BSP max rays: " << mTermMinRays << endl;
333	Debug << "BSP max polygon candidates: " << mMaxPolyCandidates << endl;
334	Debug << "BSP max plane candidates: " << mMaxRayCandidates << endl;
335
336	Debug << "Split plane strategy: ";
337	if (mSplitPlaneStrategy & RANDOM_POLYGON)
338	Debug << "random polygon ";
339	if (mSplitPlaneStrategy & AXIS_ALIGNED)
340	Debug << "axis aligned ";
341	if (mSplitPlaneStrategy & LEAST_SPLITS)
342	Debug << "least splits ";
343	if (mSplitPlaneStrategy & BALANCED_POLYS)
344	Debug << "balanced polygons ";
345	if (mSplitPlaneStrategy & BALANCED_VIEW_CELLS)
346	Debug << "balanced view cells ";
347	if (mSplitPlaneStrategy & LARGEST_POLY_AREA)
348	Debug << "largest polygon area ";
349	if (mSplitPlaneStrategy & VERTICAL_AXIS)
350	Debug << "vertical axis ";
351	if (mSplitPlaneStrategy & BLOCKED_RAYS)
352	Debug << "blocked rays ";
353	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
354	Debug << "least ray splits ";
355	if (mSplitPlaneStrategy & BALANCED_RAYS)
356	Debug << "balanced rays ";
357	if (mSplitPlaneStrategy & PVS)
358	Debug << "pvs";
359
360	Debug << endl;
361	}
362
363	void BspTree::ParseEnvironment()
364	{
365	//-- parse bsp cell tree construction method
366	char constructionMethodStr[60];
367
368	environment->GetStringValue("BspTree.Construction.input", constructionMethodStr);
369
370	sConstructionMethod = FROM_INPUT_VIEW_CELLS;
371
372	if (strcmp(constructionMethodStr, "fromViewCells") == 0)
373	sConstructionMethod = FROM_INPUT_VIEW_CELLS;
374	else if (strcmp(constructionMethodStr, "fromSceneGeometry") == 0)
375	sConstructionMethod = FROM_SCENE_GEOMETRY;
376	else if (strcmp(constructionMethodStr, "fromSamples") == 0)
377	sConstructionMethod = FROM_SAMPLES;
378	else
379	{
380	cerr << "Wrong construction method " << constructionMethodStr << endl;
381	exit(1);
382	}
383
384	Debug << "Construction method: " << constructionMethodStr << endl;
385	}
386
387	const BspTreeStatistics &BspTree::GetStatistics() const
388	{
389	return mStat;
390	}
391
392	void BspTreeStatistics::Print(ostream &app) const
393	{
394	app << "===== BspTree statistics ===============\n";
395
396	app << setprecision(4);
397
398	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
399
400	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
401
402	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
403
404	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
405
406	app << "#N_SPLITS ( Number of splits )\n" << splits << "\n";
407
408	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
409	<< maxDepthNodes * 100 / (double)Leaves() << endl;
410
411	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
412	<< maxDepthNodes * 100 / (double)Leaves() << endl;
413
414	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
415	<< minPvsNodes * 100 / (double)Leaves() << endl;
416
417	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n"
418	<< minRaysNodes * 100 / (double)Leaves() << endl;
419
420	app << "#N_PMINAREALEAVES ( Percentage of leaves with mininum area )\n"
421	<< minAreaNodes * 100 / (double)Leaves() << endl;
422
423	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"
424	<< maxRayContribNodes * 100 / (double)Leaves() << endl;
425
426	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
427
428	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
429
430	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
431
432	app << "#N_INPUT_POLYGONS (number of input polygons )\n" << polys << endl;
433
434	//app << "#N_PVS: " << pvs << endl;
435
436	app << "#N_ROUTPUT_INPUT_POLYGONS ( ratio polygons after subdivision / input polygons )\n" <<
437	(polys + splits) / (double)polys << endl;
438
439	app << "===== END OF BspTree statistics ==========\n";
440	}
441
442
443	BspTree::~BspTree()
444	{
445	DEL_PTR(mRoot);
446	}
447
448	void BspTree::InsertViewCell(ViewCell *viewCell)
449	{
450	PolygonContainer *polys = new PolygonContainer();
451
452	// extract polygons that guide the split process
453	mStat.polys += AddMeshToPolygons(viewCell->GetMesh(), *polys, viewCell);
454	mBox.Include(viewCell->GetBox()); // add to BSP aabb
455
456	InsertPolygons(polys);
457	}
458
459	void BspTree::InsertPolygons(PolygonContainer *polys)
460	{
461	std::stack<BspTraversalData> tStack;
462
463	// traverse existing tree or create new tree
464	if (!mRoot)
465	mRoot = new BspLeaf();
466
467	tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer(), 0,
468	mBox.SurfaceArea(), new BspNodeGeometry()));
469
470	while (!tStack.empty())
471	{
472	// filter polygons donw the tree
473	BspTraversalData tData = tStack.top();
474	tStack.pop();
475
476	if (!tData.mNode->IsLeaf())
477	{
478	BspInterior interior = dynamic_cast<BspInterior >(tData.mNode);
479
480	//-- filter view cell polygons down the tree until a leaf is reached
481	if (!tData.mPolygons->empty())
482	{
483	PolygonContainer *frontPolys = new PolygonContainer();
484	PolygonContainer *backPolys = new PolygonContainer();
485	PolygonContainer coincident;
486
487	int splits = 0;
488
489	// split viewcell polygons with respect to split plane
490	splits += interior->SplitPolygons(*tData.mPolygons,
491	*frontPolys,
492	*backPolys,
493	coincident);
494
495	// extract view cells associated with the split polygons
496	ViewCell *frontViewCell = mRootCell;
497	ViewCell *backViewCell = mRootCell;
498
499	BspTraversalData frontData(interior->GetFront(),
500	frontPolys,
501	tData.mDepth + 1,
502	mRootCell,
503	tData.mRays,
504	tData.mPvs,
505	mBox.SurfaceArea(),
506	new BspNodeGeometry());
507
508	BspTraversalData backData(interior->GetBack(),
509	backPolys,
510	tData.mDepth + 1,
511	mRootCell,
512	tData.mRays,
513	tData.mPvs,
514	mBox.SurfaceArea(),
515	new BspNodeGeometry());
516
517	if (!mGenerateViewCells)
518	{
519	ExtractViewCells(frontData,
520	backData,
521	coincident,
522	interior->mPlane);
523	}
524
525	// don't need coincident polygons anymore
526	CLEAR_CONTAINER(coincident);
527
528	mStat.splits += splits;
529
530	// push the children on the stack
531	tStack.push(frontData);
532	tStack.push(backData);
533	}
534
535	// cleanup
536	DEL_PTR(tData.mPolygons);
537	}
538	else
539	{
540	// reached leaf => subdivide current viewcell
541	BspNode *subRoot = Subdivide(tStack, tData);
542	}
543	}
544	}
545
546	int BspTree::AddMeshToPolygons(Mesh mesh, PolygonContainer &polys, MeshInstance parent)
547	{
548	FaceContainer::const_iterator fi;
549
550	// copy the face data to polygons
551	for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
552	{
553	Polygon3 poly = new Polygon3((fi), mesh);
554
555	if (poly->Valid())
556	{
557	poly->mParent = parent; // set parent intersectable
558	polys.push_back(poly);
559	}
560	else
561	DEL_PTR(poly);
562	}
563	return (int)mesh->mFaces.size();
564	}
565
566	int BspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
567	PolygonContainer &polys,
568	int maxObjects)
569	{
570	int limit = (maxObjects > 0) ?
571	Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
572
573	int polysSize = 0;
574
575	for (int i = 0; i < limit; ++ i)
576	{
577	if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
578	{
579	mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
580	polysSize += AddMeshToPolygons(viewCells[i]->GetMesh(), polys, viewCells[i]);
581	}
582	}
583
584	return polysSize;
585	}
586
587	int BspTree::AddToPolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
588	{
589	int limit = (maxObjects > 0) ? Min((int)objects.size(), maxObjects) : (int)objects.size();
590
591	for (int i = 0; i < limit; ++i)
592	{
593	Intersectable object = objects[i];//it;
594	Mesh *mesh = NULL;
595
596	switch (object->Type()) // extract the meshes
597	{
598	case Intersectable::MESH_INSTANCE:
599	mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
600	break;
601	case Intersectable::VIEW_CELL:
602	mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
603	break;
604	// TODO: handle transformed mesh instances
605	default:
606	Debug << "intersectable type not supported" << endl;
607	break;
608	}
609
610	if (mesh) // copy the mesh data to polygons
611	{
612	mBox.Include(object->GetBox()); // add to BSP tree aabb
613	AddMeshToPolygons(mesh, polys, mRootCell);
614	}
615	}
616
617	return (int)polys.size();
618	}
619
620	void BspTree::Construct(const ViewCellContainer &viewCells)
621	{
622	mStat.nodes = 1;
623	mBox.Initialize(); // initialise bsp tree bounding box
624
625	// copy view cell meshes into one big polygon soup
626	PolygonContainer *polys = new PolygonContainer();
627	mStat.polys = AddToPolygonSoup(viewCells, *polys);
628
629	// construct tree from the view cell polygons
630	Construct(polys, new BoundedRayContainer());
631	}
632
633
634	void BspTree::Construct(const ObjectContainer &objects)
635	{
636	mStat.nodes = 1;
637	mBox.Initialize(); // initialise bsp tree bounding box
638
639	PolygonContainer *polys = new PolygonContainer();
640
641	// copy mesh instance polygons into one big polygon soup
642	mStat.polys = AddToPolygonSoup(objects, *polys);
643
644	// construct tree from polygon soup
645	Construct(polys, new BoundedRayContainer());
646	}
647
648	void BspTree::Construct(const RayContainer &sampleRays)
649	{
650	mStat.nodes = 1;
651	mBox.Initialize(); // initialise BSP tree bounding box
652
653	PolygonContainer *polys = new PolygonContainer();
654	BoundedRayContainer *rays = new BoundedRayContainer();
655
656	RayContainer::const_iterator rit, rit_end = sampleRays.end();
657
658	long startTime = GetTime();
659
660	Debug << "** Extracting polygons from rays **\n";
661
662	std::map<Face , Polygon3 > facePolyMap;
663
664	//-- extract polygons intersected by the rays
665	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
666	{
667	Ray ray = rit;
668
669	// get ray-face intersection. Store polygon representing the rays together
670	// with rays intersecting the face.
671	if (!ray->intersections.empty())
672	{
673	MeshInstance obj = dynamic_cast<MeshInstance >(ray->intersections[0].mObject);
674	Face *face = obj->GetMesh()->mFaces[ray->intersections[0].mFace];
675
676	std::map<Face , Polygon3 >::iterator it = facePolyMap.find(face);
677
678	if (it != facePolyMap.end())
679	{
680	//store rays if needed for heuristics
681	if (mSplitPlaneStrategy & BLOCKED_RAYS)
682	(*it).second->mPiercingRays.push_back(ray);
683	}
684	else
685	{ //store rays if needed for heuristics
686	Polygon3 *poly = new Polygon3(face, obj->GetMesh());
687	poly->mParent = obj;
688	polys->push_back(poly);
689
690	if (mSplitPlaneStrategy & BLOCKED_RAYS)
691	poly->mPiercingRays.push_back(ray);
692
693	facePolyMap[face] = poly;
694	}
695	}
696	}
697
698	facePolyMap.clear();
699
700	// compue bounding box
701	Polygon3::IncludeInBox(*polys, mBox);
702
703	//-- store rays
704	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
705	{
706	Ray ray = rit;
707	ray->SetId(-1); // reset id
708
709	float minT, maxT;
710	if (BoundRay(*ray, minT, maxT))
711	rays->push_back(new BoundedRay(ray, minT, maxT));
712	}
713
714	mStat.polys = (int)polys->size();
715
716	Debug << "** Finished polygon extraction **" << endl;
717	Debug << (int)polys->size() << " polys extracted from " << (int)sampleRays.size() << " rays" << endl;
718	Debug << "extraction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
719
720	Construct(polys, rays);
721	}
722
723	void BspTree::Construct(PolygonContainer polys, BoundedRayContainer rays)
724	{
725	std::stack<BspTraversalData> tStack;
726
727	mRoot = new BspLeaf();
728
729	BspNodeGeometry *cell = new BspNodeGeometry();
730	ConstructGeometry(mRoot, *cell);
731
732	BspTraversalData tData(mRoot, polys, 0, mRootCell, rays,
733	ComputePvsSize(*rays), cell->GetArea(), cell);
734
735	tStack.push(tData);
736
737	mStat.Start();
738	cout << "** Contructing bsp tree **\n";
739
740	while (!tStack.empty())
741	{
742	tData = tStack.top();
743	tStack.pop();
744
745	// subdivide leaf node
746	BspNode *subRoot = Subdivide(tStack, tData);
747	}
748
749	mStat.Stop();
750	}
751
752	bool BspTree::TerminationCriteriaMet(const BspTraversalData &data) const
753	{
754	return
755	(((int)data.mPolygons->size() <= mTermMinPolys) \|\|
756	((int)data.mRays->size() <= mTermMinRays) \|\|
757	(data.mPvs <= mTermMinPvs) \|\|
758	(data.mArea <= mTermMinArea) \|\|
759	(data.mDepth >= mTermMaxDepth) \|\|
760	(data.GetAvgRayContribution() < mTermMaxRayContribution));
761	}
762
763	BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData)
764	{
765	//-- terminate traversal
766	if (TerminationCriteriaMet(tData))
767	{
768	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
769
770	BspViewCell *viewCell;
771
772	// generate new view cell for each leaf
773	if (mGenerateViewCells)
774	{
775	viewCell = dynamic_cast<BspViewCell *>(ViewCell::Generate());
776	}
777	else
778	{
779	// add view cell to leaf
780	viewCell = dynamic_cast<BspViewCell *>(tData.mViewCell);
781	}
782
783	leaf->SetViewCell(viewCell);
784	viewCell->mBspLeaves.push_back(leaf);
785
786	//-- add pvs
787	if (viewCell != mRootCell)
788	{
789	int conSamp = 0, sampCon = 0;
790	leaf->AddToPvs(*tData.mRays, conSamp, sampCon);
791
792	mStat.contributingSamples += conSamp;
793	mStat.sampleContributions += sampCon;
794	}
795
796	EvaluateLeafStats(tData);
797
798	//-- clean up
799
800	// discard polygons
801	CLEAR_CONTAINER(*tData.mPolygons);
802	// discard rays
803	CLEAR_CONTAINER(*tData.mRays);
804
805	DEL_PTR(tData.mPolygons);
806	DEL_PTR(tData.mRays);
807	DEL_PTR(tData.mGeometry);
808
809	return leaf;
810	}
811
812	//-- continue subdivision
813	PolygonContainer coincident;
814
815	PolygonContainer *frontPolys = new PolygonContainer();
816	PolygonContainer *backPolys = new PolygonContainer();
817
818	BoundedRayContainer *frontRays = new BoundedRayContainer();
819	BoundedRayContainer *backRays = new BoundedRayContainer();
820
821	BspTraversalData tFrontData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell,
822	new BoundedRayContainer(), 0, 0, new BspNodeGeometry());
823	BspTraversalData tBackData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell,
824	new BoundedRayContainer(), 0, 0, new BspNodeGeometry());
825
826	// create new interior node and two leaf nodes
827	BspInterior *interior = SubdivideNode(tData,
828	tFrontData,
829	tBackData,
830	coincident);
831
832	#ifdef _DEBUG
833	if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2))
834	{ for (PolygonContainer::iterator it = coincident.begin(); it != coincident.end(); ++it)
835	Debug << (it) << " " << (it)->GetArea() << " " << (*it)->mParent << endl ;
836	Debug << endl;}
837	#endif
838
839	// extract view cells from coincident polygons according to plane normal
840	// only if front or back polygons are empty
841	if (!mGenerateViewCells)
842	{
843	ExtractViewCells(tFrontData,
844	tBackData,
845	coincident,
846	interior->mPlane);
847	}
848
849	// don't need coincident polygons anymory
850	CLEAR_CONTAINER(coincident);
851
852	// push the children on the stack
853	tStack.push(tFrontData);
854	tStack.push(tBackData);
855
856	// cleanup
857	DEL_PTR(tData.mNode);
858	DEL_PTR(tData.mPolygons);
859	DEL_PTR(tData.mRays);
860	DEL_PTR(tData.mGeometry);
861
862	return interior;
863	}
864
865	void BspTree::ExtractViewCells(BspTraversalData &frontData,
866	BspTraversalData &backData,
867	const PolygonContainer &coincident,
868	const Plane3 splitPlane) const
869	{
870	// if not empty, tree is further subdivided => don't have to find view cell
871	bool foundFront = !frontData.mPolygons->empty();
872	bool foundBack = !frontData.mPolygons->empty();
873
874	PolygonContainer::const_iterator it =
875	coincident.begin(), it_end = coincident.end();
876
877	//-- find first view cells in front and back leafs
878	for (; !(foundFront && foundBack) && (it != it_end); ++ it)
879	{
880	if (DotProd((*it)->GetNormal(), splitPlane.mNormal) > 0)
881	{
882	backData.mViewCell = dynamic_cast<ViewCell >((it)->mParent);
883	foundBack = true;
884	}
885	else
886	{
887	frontData.mViewCell = dynamic_cast<ViewCell >((it)->mParent);
888	foundFront = true;
889	}
890	}
891	}
892
893	BspInterior *BspTree::SubdivideNode(BspTraversalData &tData,
894	BspTraversalData &frontData,
895	BspTraversalData &backData,
896	PolygonContainer &coincident)
897	{
898	mStat.nodes += 2;
899
900	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
901	// select subdivision plane
902	BspInterior *interior =
903	new BspInterior(SelectPlane(leaf, tData));
904
905	#ifdef _DEBUG
906	Debug << interior << endl;
907	#endif
908
909	// subdivide rays into front and back rays
910	SplitRays(interior->mPlane, tData.mRays, frontData.mRays, *backData.mRays);
911
912	// subdivide polygons with plane
913	mStat.splits += interior->SplitPolygons(*tData.mPolygons,
914	*frontData.mPolygons,
915	*backData.mPolygons,
916	coincident);
917
918	// compute pvs
919	frontData.mPvs = ComputePvsSize(*frontData.mRays);
920	backData.mPvs = ComputePvsSize(*backData.mRays);
921
922	// split geometry and compute area
923	if (1)
924	{
925	tData.mGeometry->SplitGeometry(*frontData.mGeometry,
926	*backData.mGeometry,
927	*this,
928	interior->mPlane);
929
930
931	frontData.mArea = frontData.mGeometry->GetArea();
932	backData.mArea = backData.mGeometry->GetArea();
933	}
934
935	// compute accumulated ray length
936	//frontData.mAccRayLength = AccumulatedRayLength(*frontData.mRays);
937	//backData.mAccRayLength = AccumulatedRayLength(*backData.mRays);
938
939	//-- create front and back leaf
940
941	BspInterior *parent = leaf->GetParent();
942
943	// replace a link from node's parent
944	if (!leaf->IsRoot())
945	{
946	parent->ReplaceChildLink(leaf, interior);
947	interior->SetParent(parent);
948	}
949	else // new root
950	{
951	mRoot = interior;
952	}
953
954	// and setup child links
955	interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
956
957	frontData.mNode = interior->mFront;
958	backData.mNode = interior->mBack;
959
960	//DEL_PTR(leaf);
961	return interior;
962	}
963
964	void BspTree::SortSplitCandidates(const PolygonContainer &polys,
965	const int axis,
966	vector<SortableEntry> &splitCandidates) const
967	{
968	splitCandidates.clear();
969
970	int requestedSize = 2 * (int)polys.size();
971	// creates a sorted split candidates array
972	splitCandidates.reserve(requestedSize);
973
974	PolygonContainer::const_iterator it, it_end = polys.end();
975
976	AxisAlignedBox3 box;
977
978	// insert all queries
979	for(it = polys.begin(); it != it_end; ++ it)
980	{
981	box.Initialize();
982	box.Include((it));
983
984	splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it));
985	splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it));
986	}
987
988	stable_sort(splitCandidates.begin(), splitCandidates.end());
989	}
990
991
992	float BspTree::BestCostRatio(const PolygonContainer &polys,
993	const AxisAlignedBox3 &box,
994	const int axis,
995	float &position,
996	int &objectsBack,
997	int &objectsFront) const
998	{
999	vector<SortableEntry> splitCandidates;
1000
1001	SortSplitCandidates(polys, axis, splitCandidates);
1002
1003	// go through the lists, count the number of objects left and right
1004	// and evaluate the following cost funcion:
1005	// C = ct_div_ci + (ol + or)/queries
1006
1007	int objectsLeft = 0, objectsRight = (int)polys.size();
1008
1009	float minBox = box.Min(axis);
1010	float maxBox = box.Max(axis);
1011	float boxArea = box.SurfaceArea();
1012
1013	float minBand = minBox + mSplitBorder * (maxBox - minBox);
1014	float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
1015
1016	float minSum = 1e20f;
1017	vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end();
1018
1019	for(ci = splitCandidates.begin(); ci != ci_end; ++ ci)
1020	{
1021	switch ((*ci).type)
1022	{
1023	case SortableEntry::POLY_MIN:
1024	++ objectsLeft;
1025	break;
1026	case SortableEntry::POLY_MAX:
1027	-- objectsRight;
1028	break;
1029	default:
1030	break;
1031	}
1032
1033	if ((ci).value > minBand && (ci).value < maxBand)
1034	{
1035	AxisAlignedBox3 lbox = box;
1036	AxisAlignedBox3 rbox = box;
1037	lbox.SetMax(axis, (*ci).value);
1038	rbox.SetMin(axis, (*ci).value);
1039
1040	float sum = objectsLeft * lbox.SurfaceArea() +
1041	objectsRight * rbox.SurfaceArea();
1042
1043	if (sum < minSum)
1044	{
1045	minSum = sum;
1046	position = (*ci).value;
1047
1048	objectsBack = objectsLeft;
1049	objectsFront = objectsRight;
1050	}
1051	}
1052	}
1053
1054	float oldCost = (float)polys.size();
1055	float newCost = mAaCtDivCi + minSum / boxArea;
1056	float ratio = newCost / oldCost;
1057
1058
1059	#if 0
1060	Debug << "====================" << endl;
1061	Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox)
1062	<< "\t o=(" << objectsBack << "," << objectsFront << ")" << endl;
1063	#endif
1064	return ratio;
1065	}
1066
1067	bool BspTree::SelectAxisAlignedPlane(Plane3 &plane,
1068	const PolygonContainer &polys) const
1069	{
1070	AxisAlignedBox3 box;
1071	box.Initialize();
1072
1073	// create bounding box of region
1074	Polygon3::IncludeInBox(polys, box);
1075
1076	int objectsBack = 0, objectsFront = 0;
1077	int axis = 0;
1078	float costRatio = MAX_FLOAT;
1079	Vector3 position;
1080
1081	//-- area subdivision
1082	for (int i = 0; i < 3; ++ i)
1083	{
1084	float p = 0;
1085	float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
1086
1087	if (r < costRatio)
1088	{
1089	costRatio = r;
1090	axis = i;
1091	position = p;
1092	}
1093	}
1094
1095	if (costRatio >= mMaxCostRatio)
1096	return false;
1097
1098	Vector3 norm(0,0,0); norm[axis] = 1.0f;
1099	plane = Plane3(norm, position);
1100
1101	return true;
1102	}
1103
1104	Plane3 BspTree::SelectPlane(BspLeaf *leaf, BspTraversalData &data)
1105	{
1106	if (data.mPolygons->empty() && data.mRays->empty())
1107	{
1108	Debug << "Warning: No autopartition polygon candidate available\n";
1109
1110	// return axis aligned split
1111	AxisAlignedBox3 box;
1112	box.Initialize();
1113
1114	// create bounding box of region
1115	Polygon3::IncludeInBox(*data.mPolygons, box);
1116
1117	const int axis = box.Size().DrivingAxis();
1118	const Vector3 position = (box.Min()[axis] + box.Max()[axis])*0.5f;
1119
1120	Vector3 norm(0,0,0); norm[axis] = 1.0f;
1121	return Plane3(norm, position);
1122	}
1123
1124	if ((mSplitPlaneStrategy & AXIS_ALIGNED) &&
1125	((int)data.mPolygons->size() > mTermMinPolysForAxisAligned) &&
1126	((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
1127	((mTermMinObjectsForAxisAligned < 0) \|\|
1128	(Polygon3::ParentObjectsSize(*data.mPolygons) > mTermMinObjectsForAxisAligned)))
1129	{
1130	Plane3 plane;
1131	if (SelectAxisAlignedPlane(plane, *data.mPolygons))
1132	return plane;
1133	}
1134
1135	// simplest strategy: just take next polygon
1136	if (mSplitPlaneStrategy & RANDOM_POLYGON)
1137	{
1138	if (!data.mPolygons->empty())
1139	{
1140	Polygon3 nextPoly = (data.mPolygons)[Random((int)data.mPolygons->size())];
1141	return nextPoly->GetSupportingPlane();
1142	}
1143	else
1144	{
1145	const int candidateIdx = Random((int)data.mRays->size());
1146	BoundedRay bRay = (data.mRays)[candidateIdx];
1147
1148	Ray *ray = bRay->mRay;
1149
1150	const Vector3 minPt = ray->Extrap(bRay->mMinT);
1151	const Vector3 maxPt = ray->Extrap(bRay->mMaxT);
1152
1153	const Vector3 pt = (maxPt + minPt) * 0.5;
1154
1155	const Vector3 normal = ray->GetDir();
1156
1157	return Plane3(normal, pt);
1158	}
1159
1160	return Plane3();
1161	}
1162
1163	// use heuristics to find appropriate plane
1164	return SelectPlaneHeuristics(leaf, data);
1165	}
1166
1167	Plane3 BspTree::SelectPlaneHeuristics(BspLeaf *leaf, BspTraversalData &data)
1168	{
1169	float lowestCost = MAX_FLOAT;
1170	Plane3 bestPlane;
1171	Plane3 plane;
1172
1173	int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
1174
1175	int candidateIdx = limit;
1176
1177	for (int i = 0; i < limit; ++ i)
1178	{
1179	candidateIdx = GetNextCandidateIdx(candidateIdx, *data.mPolygons);
1180
1181	Polygon3 poly = (data.mPolygons)[candidateIdx];
1182	// evaluate current candidate
1183	const float candidateCost =
1184	SplitPlaneCost(poly->GetSupportingPlane(), data);
1185
1186	if (candidateCost < lowestCost)
1187	{
1188	bestPlane = poly->GetSupportingPlane();
1189	lowestCost = candidateCost;
1190	}
1191	}
1192
1193	//Debug << "lowest: " << lowestCost << endl;
1194
1195	//-- choose candidate planes extracted from rays
1196	// we currently use two methods
1197	// 1) take 3 ray endpoints, where two are minimum and one a maximum
1198	// point or the other way round
1199	// 2) take plane normal as plane normal and the midpoint of the ray.
1200	// PROBLEM: does not resemble any point where visibility is likely to change
1201	const BoundedRayContainer *rays = data.mRays;
1202
1203	for (int i = 0; i < mMaxRayCandidates / 2; ++ i)
1204	{
1205	candidateIdx = Random((int)rays->size());
1206	BoundedRay bRay = (rays)[candidateIdx];
1207
1208	Ray *ray = bRay->mRay;
1209
1210	const Vector3 minPt = ray->Extrap(bRay->mMinT);
1211	const Vector3 maxPt = ray->Extrap(bRay->mMaxT);
1212
1213	const Vector3 pt = (maxPt + minPt) * 0.5;
1214
1215	const Vector3 normal = ray->GetDir();
1216
1217	plane = Plane3(normal, pt);
1218
1219	const float candidateCost = SplitPlaneCost(plane, data);
1220
1221	if (candidateCost < lowestCost)
1222	{
1223	bestPlane = plane;
1224
1225	lowestCost = candidateCost;
1226	}
1227	}
1228
1229	//Debug << "lowest: " << lowestCost << endl;
1230	for (int i = 0; i < mMaxRayCandidates / 2; ++ i)
1231	{
1232	Vector3 pt[3];
1233	int idx[3];
1234	int cmaxT = 0;
1235	int cminT = 0;
1236	bool chooseMin = false;
1237
1238	for (int j = 0; j < 3; j ++)
1239	{
1240	idx[j] = Random((int)rays->size() * 2);
1241
1242	if (idx[j] >= (int)rays->size())
1243	{
1244	idx[j] -= (int)rays->size();
1245
1246	chooseMin = (cminT < 2);
1247	}
1248	else
1249	chooseMin = (cmaxT < 2);
1250
1251	BoundedRay bRay = (rays)[idx[j]];
1252	pt[j] = chooseMin ? bRay->mRay->Extrap(bRay->mMinT) : bRay->mRay->Extrap(bRay->mMaxT);
1253	}
1254
1255	plane = Plane3(pt[0], pt[1], pt[2]);
1256
1257	const float candidateCost = SplitPlaneCost(plane, data);
1258
1259	if (candidateCost < lowestCost)
1260	{
1261	//Debug << "choose ray plane 2: " << candidateCost << endl;
1262	bestPlane = plane;
1263
1264	lowestCost = candidateCost;
1265	}
1266	}
1267
1268	#ifdef _DEBUG
1269	Debug << "plane lowest cost: " << lowestCost << endl;
1270	#endif
1271	return bestPlane;
1272	}
1273
1274	int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)
1275	{
1276	const int candidateIdx = Random(currentIdx --);
1277
1278	// swap candidates to avoid testing same plane 2 times
1279	std::swap(polys[currentIdx], polys[candidateIdx]);
1280
1281	return currentIdx;
1282	//return Random((int)polys.size());
1283	}
1284
1285	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1286	const PolygonContainer &polys) const
1287	{
1288	float val = 0;
1289
1290	float sumBalancedPolys = 0;
1291	float sumSplits = 0;
1292	float sumPolyArea = 0;
1293	float sumBalancedViewCells = 0;
1294	float sumBlockedRays = 0;
1295	float totalBlockedRays = 0;
1296	//float totalArea = 0;
1297	int totalViewCells = 0;
1298
1299	// need three unique ids for each type of view cell
1300	// for balanced view cells criterium
1301	ViewCell::NewMail();
1302	const int backId = ViewCell::sMailId;
1303	ViewCell::NewMail();
1304	const int frontId = ViewCell::sMailId;
1305	ViewCell::NewMail();
1306	const int frontAndBackId = ViewCell::sMailId;
1307
1308	PolygonContainer::const_iterator it, it_end = polys.end();
1309
1310	for (it = polys.begin(); it != it_end; ++ it)
1311	{
1312	const int classification = (*it)->ClassifyPlane(candidatePlane);
1313
1314	if (mSplitPlaneStrategy & BALANCED_POLYS)
1315	sumBalancedPolys += sBalancedPolysTable[classification];
1316
1317	if (mSplitPlaneStrategy & LEAST_SPLITS)
1318	sumSplits += sLeastPolySplitsTable[classification];
1319
1320	if (mSplitPlaneStrategy & LARGEST_POLY_AREA)
1321	{
1322	if (classification == Polygon3::COINCIDENT)
1323	sumPolyArea += (*it)->GetArea();
1324	//totalArea += area;
1325	}
1326
1327	if (mSplitPlaneStrategy & BLOCKED_RAYS)
1328	{
1329	const float blockedRays = (float)(*it)->mPiercingRays.size();
1330
1331	if (classification == Polygon3::COINCIDENT)
1332	sumBlockedRays += blockedRays;
1333
1334	totalBlockedRays += blockedRays;
1335	}
1336
1337	// assign view cells to back or front according to classificaion
1338	if (mSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1339	{
1340	MeshInstance viewCell = (it)->mParent;
1341
1342	// assure that we only count a view cell
1343	// once for the front and once for the back side of the plane
1344	if (classification == Polygon3::FRONT_SIDE)
1345	{
1346	if ((viewCell->mMailbox != frontId) &&
1347	(viewCell->mMailbox != frontAndBackId))
1348	{
1349	sumBalancedViewCells += 1.0;
1350
1351	if (viewCell->mMailbox != backId)
1352	viewCell->mMailbox = frontId;
1353	else
1354	viewCell->mMailbox = frontAndBackId;
1355
1356	++ totalViewCells;
1357	}
1358	}
1359	else if (classification == Polygon3::BACK_SIDE)
1360	{
1361	if ((viewCell->mMailbox != backId) &&
1362	(viewCell->mMailbox != frontAndBackId))
1363	{
1364	sumBalancedViewCells -= 1.0;
1365
1366	if (viewCell->mMailbox != frontId)
1367	viewCell->mMailbox = backId;
1368	else
1369	viewCell->mMailbox = frontAndBackId;
1370
1371	++ totalViewCells;
1372	}
1373	}
1374	}
1375	}
1376
1377	const float polysSize = (float)polys.size() + Limits::Small;
1378
1379	// all values should be approx. between 0 and 1 so they can be combined
1380	// and scaled with the factors according to their importance
1381	if (mSplitPlaneStrategy & BALANCED_POLYS)
1382	val += mBalancedPolysFactor * fabs(sumBalancedPolys) / polysSize;
1383
1384	if (mSplitPlaneStrategy & LEAST_SPLITS)
1385	val += mLeastSplitsFactor * sumSplits / polysSize;
1386
1387	if (mSplitPlaneStrategy & LARGEST_POLY_AREA)
1388	// HACK: polys.size should be total area so scaling is between 0 and 1
1389	val += mLargestPolyAreaFactor * (float)polys.size() / sumPolyArea;
1390
1391	if (mSplitPlaneStrategy & BLOCKED_RAYS)
1392	if (totalBlockedRays != 0)
1393	val += mBlockedRaysFactor * (totalBlockedRays - sumBlockedRays) / totalBlockedRays;
1394
1395	if (mSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1396	val += mBalancedViewCellsFactor * fabs(sumBalancedViewCells) /
1397	((float)totalViewCells + Limits::Small);
1398
1399	return val;
1400	}
1401
1402	bool BspTree::BoundRay(const Ray &ray, float &minT, float &maxT) const
1403	{
1404	maxT = 1e6;
1405	minT = 0;
1406
1407	// test with tree bounding box
1408	if (!mBox.GetMinMaxT(ray, &minT, &maxT))
1409	return false;
1410
1411	if (minT < 0) // start ray from origin
1412	minT = 0;
1413
1414	// bound ray or line segment
1415	if ((ray.GetType() == Ray::LOCAL_RAY) &&
1416	!ray.intersections.empty() &&
1417	(ray.intersections[0].mT <= maxT))
1418	{
1419	maxT = ray.intersections[0].mT;
1420	}
1421
1422	return true;
1423	}
1424
1425	inline void BspTree::GenerateUniqueIdsForPvs()
1426	{
1427	Intersectable::NewMail(); sBackId = ViewCell::sMailId;
1428	Intersectable::NewMail(); sFrontId = ViewCell::sMailId;
1429	Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;
1430	}
1431
1432	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1433	const BoundedRayContainer &rays,
1434	const int pvs,
1435	const float area,
1436	const BspNodeGeometry &cell) const
1437	{
1438	float val = 0;
1439
1440	float sumBalancedRays = 0;
1441	float sumRaySplits = 0;
1442
1443	int backId = 0;
1444	int frontId = 0;
1445	int frontAndBackId = 0;
1446
1447	int frontPvs = 0;
1448	int backPvs = 0;
1449
1450	// probability that view point lies in child
1451	float pOverall = 0;
1452	float pFront = 0;
1453	float pBack = 0;
1454	Debug << "here" << endl;
1455	if (mSplitPlaneStrategy & PVS)
1456	{
1457	// create unique ids for pvs heuristics
1458	GenerateUniqueIdsForPvs();
1459
1460	if (mPvsUseArea) // use front and back cell areas to approximate volume
1461	{
1462	// construct child geometry with regard to the candidate split plane
1463	BspNodeGeometry frontCell;
1464	BspNodeGeometry backCell;
1465
1466	cell.SplitGeometry(frontCell, backCell, *this, candidatePlane);
1467
1468	pFront = frontCell.GetArea();
1469	pBack = backCell.GetArea();
1470
1471	pOverall = area;
1472	}
1473	}
1474
1475	BoundedRayContainer::const_iterator rit, rit_end = rays.end();
1476
1477	for (rit = rays.begin(); rit != rays.end(); ++ rit)
1478	{
1479	Ray ray = (rit)->mRay;
1480	const float minT = (*rit)->mMinT;
1481	const float maxT = (*rit)->mMaxT;
1482
1483	Vector3 entP, extP;
1484
1485	const int cf =
1486	ray->ClassifyPlane(candidatePlane, minT, maxT, entP, extP);
1487
1488	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1489	{
1490	sumBalancedRays += sBalancedRaysTable[cf];
1491	}
1492
1493	if (mSplitPlaneStrategy & BALANCED_RAYS)
1494	{
1495	sumRaySplits += sLeastRaySplitsTable[cf];
1496	}
1497
1498	if (mSplitPlaneStrategy & PVS)
1499	{
1500	// in case the ray intersects an object
1501	// assure that we only count the object
1502	// once for the front and once for the back side of the plane
1503
1504	// add the termination object
1505	AddObjToPvs(ray->intersections[0].mObject, cf, frontPvs, backPvs);
1506
1507	// add the source object
1508	AddObjToPvs(ray->sourceObject.mObject, cf, frontPvs, backPvs);
1509
1510	if (!mPvsUseArea) // use front and back cell areas to approximate volume
1511	{
1512	float len = Distance(entP, extP);
1513	pOverall += len;
1514
1515	// use length of rays to approximate volume
1516	switch (cf)
1517	{
1518	case Ray::COINCIDENT:
1519	pBack += len;
1520	pFront += len;
1521	break;
1522	case Ray::BACK:
1523	pBack += len;
1524	break;
1525	case Ray::FRONT:
1526	pFront += len;
1527	break;
1528	case Ray::FRONT_BACK:
1529	{
1530	// find intersection of ray segment with plane
1531	const Vector3 extp = ray->Extrap(maxT);
1532	const float t = candidatePlane.FindT(ray->GetLoc(), extp);
1533
1534	const float newT = t * maxT;
1535	float newLen = Distance(ray->Extrap(newT), extp);
1536
1537	pFront += len - newLen;
1538	pBack += newLen;
1539	}
1540	break;
1541	case Ray::BACK_FRONT:
1542	{
1543	// find intersection of ray segment with plane
1544	const Vector3 extp = ray->Extrap(maxT);
1545	const float t = candidatePlane.FindT(ray->GetLoc(), extp);
1546
1547	const float newT = t * maxT;
1548	float newLen = Distance(ray->Extrap(newT), extp);
1549
1550	pFront += len;
1551	pBack += len - newLen;
1552	}
1553	break;
1554	default:
1555	Debug << "Should not come here 2" << endl;
1556	break;
1557	}
1558	}
1559	}
1560	}
1561
1562	const float raysSize = (float)rays.size() + Limits::Small;
1563	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1564	val += mLeastRaySplitsFactor * sumRaySplits / raysSize;
1565
1566	if (mSplitPlaneStrategy & BALANCED_RAYS)
1567	val += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
1568
1569	float denom = pOverall * (float)pvs * 2.0f + Limits::Small;
1570	if ((mSplitPlaneStrategy & PVS) && area && pvs)
1571	{
1572	val += mPvsFactor * (frontPvs * pFront + (backPvs * pBack)) / denom;
1573
1574	// give penalty to unbalanced split
1575	if (0)
1576	if (((pFront * 0.2 + Limits::Small) > pBack) \|\| (pFront < (pBack * 0.2 + Limits::Small)))
1577	val += 0.5;
1578	}
1579
1580	#ifdef _DEBUG
1581	Debug << "totalpvs: " << pvs << " ptotal: " << pOverall
1582	<< " frontpvs: " << frontPvs << " pFront: " << pFront
1583	<< " backpvs: " << backPvs << " pBack: " << pBack << endl << endl;
1584	#endif
1585	Debug << "here2" << endl;
1586	return val;
1587	}
1588
1589	void BspTree::AddObjToPvs(Intersectable *obj,
1590	const int cf,
1591	int &frontPvs,
1592	int &backPvs) const
1593	{
1594	if (!obj)
1595	return;
1596	// TODO: does this really belong to no pvs?
1597	//if (cf == Ray::COINCIDENT) return;
1598
1599	// object belongs to both PVS
1600	const bool bothSides = (cf == Ray::FRONT_BACK) \|\|
1601	(cf == Ray::BACK_FRONT) \|\|
1602	(cf == Ray::COINCIDENT);
1603
1604	if ((cf == Ray::FRONT) \|\| bothSides)
1605	{
1606	if ((obj->mMailbox != sFrontId) &&
1607	(obj->mMailbox != sFrontAndBackId))
1608	{
1609	++ frontPvs;
1610
1611	if (obj->mMailbox == sBackId)
1612	obj->mMailbox = sFrontAndBackId;
1613	else
1614	obj->mMailbox = sFrontId;
1615	}
1616	}
1617
1618	if ((cf == Ray::BACK) \|\| bothSides)
1619	{
1620	if ((obj->mMailbox != sBackId) &&
1621	(obj->mMailbox != sFrontAndBackId))
1622	{
1623	++ backPvs;
1624
1625	if (obj->mMailbox == sFrontId)
1626	obj->mMailbox = sFrontAndBackId;
1627	else
1628	obj->mMailbox = sBackId;
1629	}
1630	}
1631	}
1632
1633	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1634	BspTraversalData &data) const
1635	{
1636	float val = 0;
1637
1638	if (mSplitPlaneStrategy & VERTICAL_AXIS)
1639	{
1640	Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
1641	// we put a penalty on the dot product between the "tiny" vertical axis
1642	// and the split plane axis
1643	val += mVerticalSplitsFactor *
1644	fabs(DotProd(candidatePlane.mNormal, tinyAxis));
1645	}
1646
1647	// the following criteria loop over all polygons to find the cost value
1648	if ((mSplitPlaneStrategy & BALANCED_POLYS) \|\|
1649	(mSplitPlaneStrategy & LEAST_SPLITS) \|\|
1650	(mSplitPlaneStrategy & LARGEST_POLY_AREA) \|\|
1651	(mSplitPlaneStrategy & BALANCED_VIEW_CELLS) \|\|
1652	(mSplitPlaneStrategy & BLOCKED_RAYS))
1653	{
1654	val += SplitPlaneCost(candidatePlane, *data.mPolygons);
1655	}
1656
1657	// the following criteria loop over all rays to find the cost value
1658	if ((mSplitPlaneStrategy & BALANCED_RAYS) \|\|
1659	(mSplitPlaneStrategy & LEAST_RAY_SPLITS) \|\|
1660	(mSplitPlaneStrategy & PVS))
1661	{
1662	val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs,
1663	data.mArea, *data.mGeometry);
1664	}
1665
1666	// return linear combination of the sums
1667	return val;
1668	}
1669
1670	void BspTree::CollectLeaves(vector<BspLeaf *> &leaves) const
1671	{
1672	stack<BspNode *> nodeStack;
1673	nodeStack.push(mRoot);
1674
1675	while (!nodeStack.empty())
1676	{
1677	BspNode *node = nodeStack.top();
1678
1679	nodeStack.pop();
1680
1681	if (node->IsLeaf())
1682	{
1683	BspLeaf leaf = (BspLeaf )node;
1684	leaves.push_back(leaf);
1685	}
1686	else
1687	{
1688	BspInterior interior = dynamic_cast<BspInterior >(node);
1689
1690	nodeStack.push(interior->GetBack());
1691	nodeStack.push(interior->GetFront());
1692	}
1693	}
1694	}
1695
1696	AxisAlignedBox3 BspTree::GetBoundingBox() const
1697	{
1698	return mBox;
1699	}
1700
1701	BspNode *BspTree::GetRoot() const
1702	{
1703	return mRoot;
1704	}
1705
1706	void BspTree::EvaluateLeafStats(const BspTraversalData &data)
1707	{
1708	// the node became a leaf -> evaluate stats for leafs
1709	BspLeaf leaf = dynamic_cast<BspLeaf >(data.mNode);
1710
1711	// store maximal and minimal depth
1712	if (data.mDepth > mStat.maxDepth)
1713	mStat.maxDepth = data.mDepth;
1714
1715	if (data.mDepth < mStat.minDepth)
1716	mStat.minDepth = data.mDepth;
1717
1718	// accumulate depth to compute average depth
1719	mStat.accumDepth += data.mDepth;
1720
1721
1722	if (data.mDepth >= mTermMaxDepth)
1723	++ mStat.maxDepthNodes;
1724
1725	if (data.mPvs < mTermMinPvs)
1726	++ mStat.minPvsNodes;
1727
1728	if ((int)data.mRays->size() < mTermMinRays)
1729	++ mStat.minRaysNodes;
1730
1731	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1732	++ mStat.maxRayContribNodes;
1733
1734	if (data.mGeometry->GetArea() <= mTermMinArea)
1735	++ mStat.minAreaNodes;
1736
1737	#ifdef _DEBUG
1738	Debug << "BSP stats: "
1739	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1740	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1741	<< "Area: " << data.mArea << " (min: " << mTermMinArea << "), "
1742	<< "#polygons: " << (int)data.mPolygons->size() << " (max: " << mTermMinPolys << "), "
1743	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1744	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
1745	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1746	#endif
1747	}
1748
1749	int BspTree::CastRay(Ray &ray)
1750	{
1751	int hits = 0;
1752
1753	stack<BspRayTraversalData> tStack;
1754
1755	float maxt, mint;
1756
1757	if (!BoundRay(ray, mint, maxt))
1758	return 0;
1759
1760	Intersectable::NewMail();
1761
1762	Vector3 entp = ray.Extrap(mint);
1763	Vector3 extp = ray.Extrap(maxt);
1764
1765	BspNode *node = mRoot;
1766	BspNode *farChild = NULL;
1767
1768	while (1)
1769	{
1770	if (!node->IsLeaf())
1771	{
1772	BspInterior in = (BspInterior ) node;
1773
1774	Plane3 *splitPlane = in->GetPlane();
1775
1776	int entSide = splitPlane->Side(entp);
1777	int extSide = splitPlane->Side(extp);
1778
1779	Vector3 intersection;
1780
1781	if (entSide < 0)
1782	{
1783	node = in->GetBack();
1784
1785	if(extSide <= 0) // plane does not split ray => no far child
1786	continue;
1787
1788	farChild = in->GetFront(); // plane splits ray
1789
1790	} else if (entSide > 0)
1791	{
1792	node = in->GetFront();
1793
1794	if (extSide >= 0) // plane does not split ray => no far child
1795	continue;
1796
1797	farChild = in->GetBack(); // plane splits ray
1798	}
1799	else // ray and plane are coincident
1800	{
1801	// WHAT TO DO IN THIS CASE ?
1802	//break;
1803	node = in->GetFront();
1804	continue;
1805	}
1806
1807	// push data for far child
1808	tStack.push(BspRayTraversalData(farChild, extp, maxt));
1809
1810	// find intersection of ray segment with plane
1811	float t;
1812	extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &t);
1813	maxt *= t;
1814
1815	} else // reached leaf => intersection with view cell
1816	{
1817	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
1818
1819	if (!leaf->mViewCell->Mailed())
1820	{
1821	ray.bspIntersections.push_back(Ray::BspIntersection(maxt, leaf));
1822	leaf->mViewCell->Mail();
1823	++ hits;
1824	}
1825
1826	//-- fetch the next far child from the stack
1827	if (tStack.empty())
1828	break;
1829
1830	entp = extp;
1831	mint = maxt; // NOTE: need this?
1832
1833	if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
1834	break;
1835
1836	BspRayTraversalData &s = tStack.top();
1837
1838	node = s.mNode;
1839	extp = s.mExitPoint;
1840	maxt = s.mMaxT;
1841
1842	tStack.pop();
1843	}
1844	}
1845
1846	return hits;
1847	}
1848
1849	bool BspTree::Export(const string filename)
1850	{
1851	Exporter *exporter = Exporter::GetExporter(filename);
1852
1853	if (exporter)
1854	{
1855	exporter->ExportBspTree(*this);
1856	return true;
1857	}
1858
1859	return false;
1860	}
1861
1862	void BspTree::CollectViewCells(ViewCellContainer &viewCells) const
1863	{
1864	stack<BspNode *> nodeStack;
1865	nodeStack.push(mRoot);
1866
1867	ViewCell::NewMail();
1868
1869	while (!nodeStack.empty())
1870	{
1871	BspNode *node = nodeStack.top();
1872	nodeStack.pop();
1873
1874	if (node->IsLeaf())
1875	{
1876	ViewCell viewCell = dynamic_cast<BspLeaf >(node)->mViewCell;
1877
1878	if (!viewCell->Mailed())
1879	{
1880	viewCell->Mail();
1881	viewCells.push_back(viewCell);
1882	}
1883	}
1884	else
1885	{
1886	BspInterior interior = dynamic_cast<BspInterior >(node);
1887
1888	nodeStack.push(interior->mFront);
1889	nodeStack.push(interior->mBack);
1890	}
1891	}
1892	}
1893
1894	void BspTree::EvaluateViewCellsStats(BspViewCellsStatistics &stat) const
1895	{
1896	stat.Reset();
1897
1898	stack<BspNode *> nodeStack;
1899	nodeStack.push(mRoot);
1900
1901	ViewCell::NewMail();
1902
1903	// exclude root cell
1904	mRootCell->Mail();
1905
1906	while (!nodeStack.empty())
1907	{
1908	BspNode *node = nodeStack.top();
1909	nodeStack.pop();
1910
1911	if (node->IsLeaf())
1912	{
1913	++ stat.bspLeaves;
1914
1915	BspViewCell viewCell = dynamic_cast<BspLeaf >(node)->mViewCell;
1916
1917	if (!viewCell->Mailed())
1918	{
1919	viewCell->Mail();
1920
1921	++ stat.viewCells;
1922	const int pvsSize = viewCell->GetPvs().GetSize();
1923
1924	stat.pvs += pvsSize;
1925
1926	if (pvsSize < 1)
1927	++ stat.emptyPvs;
1928
1929	if (pvsSize > stat.maxPvs)
1930	stat.maxPvs = pvsSize;
1931
1932	if (pvsSize < stat.minPvs)
1933	stat.minPvs = pvsSize;
1934
1935	if ((int)viewCell->mBspLeaves.size() > stat.maxBspLeaves)
1936	stat.maxBspLeaves = (int)viewCell->mBspLeaves.size();
1937	}
1938	}
1939	else
1940	{
1941	BspInterior interior = dynamic_cast<BspInterior >(node);
1942
1943	nodeStack.push(interior->mFront);
1944	nodeStack.push(interior->mBack);
1945	}
1946	}
1947	}
1948
1949	bool BspTree::MergeViewCells(BspLeaf front, BspLeaf back) const
1950	{
1951	BspViewCell *viewCell =
1952	dynamic_cast<BspViewCell >(ViewCell::Merge(front->mViewCell, *back->mViewCell));
1953
1954	if (!viewCell)
1955	return false;
1956
1957	// change view cells of all leaves associated with the
1958	// previous view cells
1959
1960	BspViewCell *fVc = front->mViewCell;
1961	BspViewCell *bVc = back->mViewCell;
1962
1963	vector<BspLeaf *> fLeaves = fVc->mBspLeaves;
1964	vector<BspLeaf *> bLeaves = bVc->mBspLeaves;
1965
1966	vector<BspLeaf *>::const_iterator it;
1967
1968	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
1969	{
1970	(*it)->SetViewCell(viewCell);
1971	viewCell->mBspLeaves.push_back(*it);
1972	}
1973	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
1974	{
1975	(*it)->SetViewCell(viewCell);
1976	viewCell->mBspLeaves.push_back(*it);
1977	}
1978
1979	DEL_PTR(fVc);
1980	DEL_PTR(bVc);
1981
1982	return true;
1983	}
1984
1985	bool BspTree::ShouldMerge(BspLeaf front, BspLeaf back) const
1986	{
1987	ViewCell *fvc = front->mViewCell;
1988	ViewCell *bvc = back->mViewCell;
1989
1990	if ((fvc == mRootCell) \|\| (bvc == mRootCell) \|\| (fvc == bvc))
1991	return false;
1992
1993	int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());
1994
1995	if (fvc->GetPvs().GetSize() + fdiff < mMaxPvs)
1996	{
1997	if ((fvc->GetPvs().GetSize() < mMinPvs) \|\|
1998	(bvc->GetPvs().GetSize() < mMinPvs) \|\|
1999	((fdiff < mMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif)))
2000	{
2001	return true;
2002	}
2003	}
2004
2005	return false;
2006	}
2007
2008	void BspTree::SetGenerateViewCells(int generateViewCells)
2009	{
2010	mGenerateViewCells = generateViewCells;
2011	}
2012
2013	BspTreeStatistics &BspTree::GetStat()
2014	{
2015	return mStat;
2016	}
2017
2018	float BspTree::AccumulatedRayLength(BoundedRayContainer &rays) const
2019	{
2020	float len = 0;
2021
2022	BoundedRayContainer::const_iterator it, it_end = rays.end();
2023
2024	for (it = rays.begin(); it != it_end; ++ it)
2025	{
2026	len += SqrDistance((it)->mRay->Extrap((it)->mMinT),
2027	(it)->mRay->Extrap((it)->mMaxT));
2028	}
2029
2030	return len;
2031	}
2032
2033	int BspTree::SplitRays(const Plane3 &plane,
2034	BoundedRayContainer &rays,
2035	BoundedRayContainer &frontRays,
2036	BoundedRayContainer &backRays)
2037	{
2038	int splits = 0;
2039
2040	while (!rays.empty())
2041	{
2042	BoundedRay *bRay = rays.back();
2043	Ray *ray = bRay->mRay;
2044	float minT = bRay->mMinT;
2045	float maxT = bRay->mMaxT;
2046
2047	rays.pop_back();
2048
2049	Vector3 entP, extP;
2050
2051	const int cf =
2052	ray->ClassifyPlane(plane, minT, maxT, entP, extP);
2053
2054	// set id to ray classification
2055	ray->SetId(cf);
2056
2057	switch (cf)
2058	{
2059	case Ray::COINCIDENT: // TODO: should really discard ray?
2060	frontRays.push_back(bRay);
2061	//DEL_PTR(bRay);
2062	break;
2063	case Ray::BACK:
2064	backRays.push_back(bRay);
2065	break;
2066	case Ray::FRONT:
2067	frontRays.push_back(bRay);
2068	break;
2069	case Ray::FRONT_BACK:
2070	{
2071	// find intersection of ray segment with plane
2072	const float t = plane.FindT(ray->GetLoc(), extP);
2073
2074	const float newT = t * maxT;
2075
2076	frontRays.push_back(new BoundedRay(ray, minT, newT));
2077	backRays.push_back(new BoundedRay(ray, newT, maxT));
2078
2079	DEL_PTR(bRay);
2080	}
2081	break;
2082	case Ray::BACK_FRONT:
2083	{
2084	// find intersection of ray segment with plane
2085	const float t = plane.FindT(ray->GetLoc(), extP);
2086	const float newT = t * bRay->mMaxT;
2087
2088	backRays.push_back(new BoundedRay(ray, bRay->mMinT, newT));
2089	frontRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT));
2090	DEL_PTR(bRay);
2091
2092	++ splits;
2093	}
2094	break;
2095	default:
2096	Debug << "Should not come here 4" << endl;
2097	break;
2098	}
2099	}
2100
2101	return splits;
2102	}
2103
2104	void BspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
2105	{
2106	BspNode *lastNode;
2107	do
2108	{
2109	lastNode = n;
2110
2111	// want to get planes defining geometry of this node => don't take
2112	// split plane of node itself
2113	n = n->GetParent();
2114
2115	if (n)
2116	{
2117	BspInterior interior = dynamic_cast<BspInterior >(n);
2118	Plane3 halfSpace = dynamic_cast<BspInterior >(interior)->GetPlane();
2119
2120	if (interior->mFront != lastNode)
2121	halfSpace.ReverseOrientation();
2122
2123	halfSpaces.push_back(halfSpace);
2124	}
2125	}
2126	while (n);
2127	}
2128
2129	void BspTree::ConstructGeometry(BspNode *n, BspNodeGeometry &cell) const
2130	{
2131	PolygonContainer polys;
2132	ConstructGeometry(n, polys);
2133	cell.mPolys = polys;
2134	}
2135
2136	void BspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &cell) const
2137	{
2138	vector<BspLeaf *> leaves = vc->mBspLeaves;
2139
2140	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2141
2142	for (it = leaves.begin(); it != it_end; ++ it)
2143	ConstructGeometry(*it, cell);
2144	}
2145
2146
2147	void BspTree::ConstructGeometry(BspNode *n, PolygonContainer &cell) const
2148	{
2149	vector<Plane3> halfSpaces;
2150	ExtractHalfSpaces(n, halfSpaces);
2151
2152	PolygonContainer candidatePolys;
2153
2154	// bounded planes are added to the polygons (reverse polygons
2155	// as they have to be outfacing
2156	for (int i = 0; i < (int)halfSpaces.size(); ++ i)
2157	{
2158	Polygon3 *p = GetBoundingBox().CrossSection(halfSpaces[i]);
2159
2160	if (p->Valid())
2161	{
2162	candidatePolys.push_back(p->CreateReversePolygon());
2163	DEL_PTR(p);
2164	}
2165	}
2166
2167	// add faces of bounding box (also could be faces of the cell)
2168	for (int i = 0; i < 6; ++ i)
2169	{
2170	VertexContainer vertices;
2171
2172	for (int j = 0; j < 4; ++ j)
2173	vertices.push_back(mBox.GetFace(i).mVertices[j]);
2174
2175	candidatePolys.push_back(new Polygon3(vertices));
2176	}
2177
2178	for (int i = 0; i < (int)candidatePolys.size(); ++ i)
2179	{
2180	// polygon is split by all other planes
2181	for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
2182	{
2183	if (i == j) // polygon and plane are coincident
2184	continue;
2185
2186	VertexContainer splitPts;
2187	Polygon3 frontPoly, backPoly;
2188
2189	const int cf = candidatePolys[i]->ClassifyPlane(halfSpaces[j]);
2190
2191	switch (cf)
2192	{
2193	case Polygon3::SPLIT:
2194	frontPoly = new Polygon3();
2195	backPoly = new Polygon3();
2196
2197	candidatePolys[i]->Split(halfSpaces[j], *frontPoly,
2198	*backPoly, splitPts);
2199
2200	DEL_PTR(candidatePolys[i]);
2201
2202	if (frontPoly->Valid())
2203	candidatePolys[i] = frontPoly;
2204	else
2205	DEL_PTR(frontPoly);
2206
2207	DEL_PTR(backPoly);
2208	break;
2209	case Polygon3::BACK_SIDE:
2210	DEL_PTR(candidatePolys[i]);
2211	break;
2212	// just take polygon as it is
2213	case Polygon3::FRONT_SIDE:
2214	case Polygon3::COINCIDENT:
2215	default:
2216	break;
2217	}
2218	}
2219
2220	if (candidatePolys[i])
2221	cell.push_back(candidatePolys[i]);
2222	}
2223	}
2224
2225
2226	int BspTree::FindNeighbors(BspNode n, vector<BspLeaf > &neighbors,
2227	const bool onlyUnmailed) const
2228	{
2229	PolygonContainer cell;
2230
2231	ConstructGeometry(n, cell);
2232
2233	stack<BspNode *> nodeStack;
2234	nodeStack.push(mRoot);
2235
2236	// planes needed to verify that we found neighbor leaf.
2237	vector<Plane3> halfSpaces;
2238	ExtractHalfSpaces(n, halfSpaces);
2239
2240	while (!nodeStack.empty())
2241	{
2242	BspNode *node = nodeStack.top();
2243	nodeStack.pop();
2244
2245	if (node->IsLeaf())
2246	{
2247	if (node != n && (!onlyUnmailed \|\| !node->Mailed()))
2248	{
2249	// test all planes of current node if candidate really
2250	// is neighbour
2251	PolygonContainer neighborCandidate;
2252	ConstructGeometry(node, neighborCandidate);
2253
2254	bool isAdjacent = true;
2255	for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
2256	{
2257	const int cf =
2258	Polygon3::ClassifyPlane(neighborCandidate, halfSpaces[i]);
2259
2260	if (cf == Polygon3::BACK_SIDE)
2261	isAdjacent = false;
2262	}
2263
2264	if (isAdjacent)
2265	neighbors.push_back(dynamic_cast<BspLeaf *>(node));
2266
2267	CLEAR_CONTAINER(neighborCandidate);
2268	}
2269	}
2270	else
2271	{
2272	BspInterior interior = dynamic_cast<BspInterior >(node);
2273
2274	const int cf = Polygon3::ClassifyPlane(cell, interior->mPlane);
2275
2276	if (cf == Polygon3::FRONT_SIDE)
2277	nodeStack.push(interior->mFront);
2278	else
2279	if (cf == Polygon3::BACK_SIDE)
2280	nodeStack.push(interior->mBack);
2281	else
2282	{
2283	// random decision
2284	nodeStack.push(interior->mBack);
2285	nodeStack.push(interior->mFront);
2286	}
2287	}
2288	}
2289
2290	CLEAR_CONTAINER(cell);
2291	return (int)neighbors.size();
2292	}
2293
2294	BspLeaf *BspTree::GetRandomLeaf(const Plane3 &halfspace)
2295	{
2296	stack<BspNode *> nodeStack;
2297	nodeStack.push(mRoot);
2298
2299	int mask = rand();
2300
2301	while (!nodeStack.empty())
2302	{
2303	BspNode *node = nodeStack.top();
2304	nodeStack.pop();
2305
2306	if (node->IsLeaf())
2307	{
2308	return dynamic_cast<BspLeaf *>(node);
2309	}
2310	else
2311	{
2312	BspInterior interior = dynamic_cast<BspInterior >(node);
2313
2314	BspNode *next;
2315
2316	PolygonContainer cell;
2317
2318	// todo: not very efficient: constructs full cell everytime
2319	ConstructGeometry(interior, cell);
2320
2321	const int cf = Polygon3::ClassifyPlane(cell, halfspace);
2322
2323	if (cf == Polygon3::BACK_SIDE)
2324	next = interior->mFront;
2325	else
2326	if (cf == Polygon3::FRONT_SIDE)
2327	next = interior->mFront;
2328	else
2329	{
2330	// random decision
2331	if (mask & 1)
2332	next = interior->mBack;
2333	else
2334	next = interior->mFront;
2335	mask = mask >> 1;
2336	}
2337
2338	nodeStack.push(next);
2339	}
2340	}
2341
2342	return NULL;
2343	}
2344
2345	BspLeaf *BspTree::GetRandomLeaf(const bool onlyUnmailed)
2346	{
2347	stack<BspNode *> nodeStack;
2348
2349	nodeStack.push(mRoot);
2350
2351	int mask = rand();
2352
2353	while (!nodeStack.empty())
2354	{
2355	BspNode *node = nodeStack.top();
2356	nodeStack.pop();
2357
2358	if (node->IsLeaf())
2359	{
2360	if ( (!onlyUnmailed \|\| !node->Mailed()) )
2361	return dynamic_cast<BspLeaf *>(node);
2362	}
2363	else
2364	{
2365	BspInterior interior = dynamic_cast<BspInterior >(node);
2366
2367	// random decision
2368	if (mask & 1)
2369	nodeStack.push(interior->mBack);
2370	else
2371	nodeStack.push(interior->mFront);
2372
2373	mask = mask >> 1;
2374	}
2375	}
2376
2377	return NULL;
2378	}
2379
2380	int BspTree::ComputePvsSize(const BoundedRayContainer &rays) const
2381	{
2382	int pvsSize = 0;
2383
2384	BoundedRayContainer::const_iterator rit, rit_end = rays.end();
2385
2386	Intersectable::NewMail();
2387
2388	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2389	{
2390	Ray ray = (rit)->mRay;
2391
2392	if (!ray->intersections.empty())
2393	{
2394	if (!ray->intersections[0].mObject->Mailed())
2395	{
2396	ray->intersections[0].mObject->Mail();
2397	++ pvsSize;
2398	}
2399	}
2400	if (ray->sourceObject.mObject)
2401	{
2402	if (!ray->sourceObject.mObject->Mailed())
2403	{
2404	ray->sourceObject.mObject->Mail();
2405	++ pvsSize;
2406	}
2407	}
2408	}
2409
2410	return pvsSize;
2411	}
2412
2413	/*************************************************************
2414	* BspNodeGeometry Implementation *
2415	*************************************************************/
2416
2417	BspNodeGeometry::~BspNodeGeometry()
2418	{
2419	CLEAR_CONTAINER(mPolys);
2420	}
2421
2422	float BspNodeGeometry::GetArea() const
2423	{
2424	return Polygon3::GetArea(mPolys);
2425	}
2426
2427	void BspNodeGeometry::SplitGeometry(BspNodeGeometry &front,
2428	BspNodeGeometry &back,
2429	const BspTree &tree,
2430	const Plane3 &splitPlane) const
2431	{
2432	// get cross section of new polygon
2433	Polygon3 *planePoly = tree.GetBoundingBox().CrossSection(splitPlane);
2434
2435	planePoly = SplitPolygon(planePoly, tree);
2436
2437	//-- plane poly splits all other cell polygons
2438	for (int i = 0; i < (int)mPolys.size(); ++ i)
2439	{
2440	const int cf = mPolys[i]->ClassifyPlane(splitPlane, 0.00001f);
2441
2442	// split new polygon with all previous planes
2443	switch (cf)
2444	{
2445	case Polygon3::SPLIT:
2446	{
2447	Polygon3 *poly = new Polygon3(mPolys[i]->mVertices);
2448
2449	Polygon3 *frontPoly = new Polygon3();
2450	Polygon3 *backPoly = new Polygon3();
2451
2452	VertexContainer splitPts;
2453
2454	poly->Split(splitPlane, frontPoly, backPoly, splitPts);
2455
2456	DEL_PTR(poly);
2457
2458	if (frontPoly->Valid())
2459	front.mPolys.push_back(frontPoly);
2460	if (backPoly->Valid())
2461	back.mPolys.push_back(backPoly);
2462	}
2463
2464	break;
2465	case Polygon3::BACK_SIDE:
2466	back.mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
2467	break;
2468	case Polygon3::FRONT_SIDE:
2469	front.mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
2470	break;
2471	case Polygon3::COINCIDENT:
2472	//front.mPolys.push_back(CreateReversePolygon(mPolys[i]));
2473	back.mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
2474	break;
2475	default:
2476	break;
2477	}
2478	}
2479
2480	//-- finally add the new polygon to the child cells
2481	if (planePoly)
2482	{
2483	// add polygon with normal pointing into positive half space to back cell
2484	back.mPolys.push_back(planePoly);
2485	// add polygon with reverse orientation to front cell
2486	front.mPolys.push_back(planePoly->CreateReversePolygon());
2487	}
2488
2489	//Debug << "returning new geometry " << mPolys.size() << " f: " << front.mPolys.size() << " b: " << back.mPolys.size() << endl;
2490	//Debug << "old area " << GetArea() << " f: " << front.GetArea() << " b: " << back.GetArea() << endl;
2491	}
2492
2493	Polygon3 BspNodeGeometry::SplitPolygon(Polygon3 planePoly,
2494	const BspTree &tree) const
2495	{
2496	// polygon is split by all other planes
2497	for (int i = 0; (i < (int)mPolys.size()) && planePoly; ++ i)
2498	{
2499	Plane3 plane = mPolys[i]->GetSupportingPlane();
2500
2501	const int cf =
2502	planePoly->ClassifyPlane(plane, 0.00001f);
2503
2504	// split new polygon with all previous planes
2505	switch (cf)
2506	{
2507	case Polygon3::SPLIT:
2508	{
2509	VertexContainer splitPts;
2510
2511	Polygon3 *frontPoly = new Polygon3();
2512	Polygon3 *backPoly = new Polygon3();
2513
2514	planePoly->Split(plane, frontPoly, backPoly, splitPts);
2515	DEL_PTR(planePoly);
2516
2517	if (backPoly->Valid())
2518	planePoly = backPoly;
2519	else
2520	DEL_PTR(backPoly);
2521	}
2522	break;
2523	case Polygon3::FRONT_SIDE:
2524	DEL_PTR(planePoly);
2525	break;
2526	// polygon is taken as it is
2527	case Polygon3::BACK_SIDE:
2528	case Polygon3::COINCIDENT:
2529	default:
2530	break;
2531	}
2532	}
2533
2534	return planePoly;
2535	}
2536
2537	void BspViewCellsStatistics::Print(ostream &app) const
2538	{
2539	app << "===== BspViewCells statistics ===============\n";
2540
2541	app << setprecision(4);
2542
2543	//app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
2544
2545	app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl;
2546
2547	app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
2548
2549	app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
2550
2551	app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
2552
2553	app << "#N_PEMPTYPVS ( view cells with PVS smaller 2 )\n" << emptyPvs << endl;
2554
2555	app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
2556
2557	app << "#N_AVGBSPLEAVES (average number of BSP leaves per view cell )\n" << AvgBspLeaves() << endl;
2558
2559	app << "#N_MAXBSPLEAVES ( maximal number of BSP leaves per view cell )\n" << maxBspLeaves << endl;
2560
2561	app << "===== END OF BspViewCells statistics ==========\n";
2562	}

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

Download in other formats: