Context Navigation

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

Revision 479, 65.6 KB checked in by mattausch, 19 years ago (diff)

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

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

Download in other formats: