Context Navigation

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

Revision 475, 66.1 KB checked in by mattausch, 19 years ago (diff)
bsp merging possible again

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 = (data.mPolygons)[(int)RandomValue(0, (int)data.mPolygons->size() - 1)];
1151	return nextPoly->GetSupportingPlane();
1152	}
1153	else
1154	{
1155	const int candidateIdx = (int)RandomValue(0, (Real)((int)data.mRays->size() - 1));
1156	BoundedRay bRay = (data.mRays)[candidateIdx];
1157
1158	Ray *ray = bRay->mRay;
1159
1160	const Vector3 minPt = ray->Extrap(bRay->mMinT);
1161	const Vector3 maxPt = ray->Extrap(bRay->mMaxT);
1162
1163	const Vector3 pt = (maxPt + minPt) * 0.5;
1164
1165	const Vector3 normal = ray->GetDir();
1166
1167	return Plane3(normal, pt);
1168	}
1169
1170	return Plane3();
1171	}
1172
1173	// use heuristics to find appropriate plane
1174	return SelectPlaneHeuristics(leaf, data);
1175	}
1176
1177	Plane3 BspTree::SelectPlaneHeuristics(BspLeaf *leaf, BspTraversalData &data)
1178	{
1179	float lowestCost = MAX_FLOAT;
1180	Plane3 bestPlane;
1181	Plane3 plane;
1182
1183	int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
1184
1185	int candidateIdx = limit - 1;
1186
1187	for (int i = 0; i < limit; ++ i)
1188	{
1189	candidateIdx = GetNextCandidateIdx(candidateIdx, *data.mPolygons);
1190
1191	Polygon3 poly = (data.mPolygons)[candidateIdx];
1192	// evaluate current candidate
1193	const float candidateCost =
1194	SplitPlaneCost(poly->GetSupportingPlane(), data);
1195
1196	if (candidateCost < lowestCost)
1197	{
1198	bestPlane = poly->GetSupportingPlane();
1199	lowestCost = candidateCost;
1200	}
1201	}
1202
1203	//Debug << "lowest: " << lowestCost << endl;
1204
1205	//-- choose candidate planes extracted from rays
1206	// we currently use two methods
1207	// 1) take 3 ray endpoints, where two are minimum and one a maximum
1208	// point or the other way round
1209	// 2) take plane normal as plane normal and the midpoint of the ray.
1210	// PROBLEM: does not resemble any point where visibility is likely to change
1211	const BoundedRayContainer *rays = data.mRays;
1212
1213	for (int i = 0; i < mMaxRayCandidates / 2; ++ i)
1214	{
1215	candidateIdx = (int)RandomValue(0, (int)rays->size() - 1);
1216	BoundedRay bRay = (rays)[candidateIdx];
1217
1218	Ray *ray = bRay->mRay;
1219
1220	const Vector3 minPt = ray->Extrap(bRay->mMinT);
1221	const Vector3 maxPt = ray->Extrap(bRay->mMaxT);
1222
1223	const Vector3 pt = (maxPt + minPt) * 0.5;
1224
1225	const Vector3 normal = ray->GetDir();
1226
1227	plane = Plane3(normal, pt);
1228
1229	const float candidateCost = SplitPlaneCost(plane, data);
1230
1231	if (candidateCost < lowestCost)
1232	{
1233	bestPlane = plane;
1234
1235	lowestCost = candidateCost;
1236	}
1237	}
1238
1239	//Debug << "lowest: " << lowestCost << endl;
1240	for (int i = 0; i < mMaxRayCandidates / 2; ++ i)
1241	{
1242	Vector3 pt[3];
1243	int idx[3];
1244	int cmaxT = 0;
1245	int cminT = 0;
1246	bool chooseMin = false;
1247
1248	for (int j = 0; j < 3; j ++)
1249	{
1250	idx[j] = (int)RandomValue(0, (int)rays->size() * 2 - 1);
1251
1252	if (idx[j] >= (int)rays->size())
1253	{
1254	idx[j] -= (int)rays->size();
1255
1256	chooseMin = (cminT < 2);
1257	}
1258	else
1259	chooseMin = (cmaxT < 2);
1260
1261	BoundedRay bRay = (rays)[idx[j]];
1262	pt[j] = chooseMin ? bRay->mRay->Extrap(bRay->mMinT) :
1263	bRay->mRay->Extrap(bRay->mMaxT);
1264	}
1265
1266	plane = Plane3(pt[0], pt[1], pt[2]);
1267
1268	const float candidateCost = SplitPlaneCost(plane, data);
1269
1270	if (candidateCost < lowestCost)
1271	{
1272	//Debug << "choose ray plane 2: " << candidateCost << endl;
1273	bestPlane = plane;
1274
1275	lowestCost = candidateCost;
1276	}
1277	}
1278
1279	#ifdef _DEBUG
1280	Debug << "plane lowest cost: " << lowestCost << endl;
1281	#endif
1282	return bestPlane;
1283	}
1284
1285	int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)
1286	{
1287	const int candidateIdx = (int)RandomValue(0, currentIdx --);
1288
1289	// swap candidates to avoid testing same plane 2 times
1290	std::swap(polys[currentIdx], polys[candidateIdx]);
1291
1292	return currentIdx;
1293	//return (int)RandomValue(0, (int)polys.size() - 1);
1294	}
1295
1296	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1297	const PolygonContainer &polys) const
1298	{
1299	float val = 0;
1300
1301	float sumBalancedPolys = 0;
1302	float sumSplits = 0;
1303	float sumPolyArea = 0;
1304	float sumBalancedViewCells = 0;
1305	float sumBlockedRays = 0;
1306	float totalBlockedRays = 0;
1307	//float totalArea = 0;
1308	int totalViewCells = 0;
1309
1310	// need three unique ids for each type of view cell
1311	// for balanced view cells criterium
1312	ViewCell::NewMail();
1313	const int backId = ViewCell::sMailId;
1314	ViewCell::NewMail();
1315	const int frontId = ViewCell::sMailId;
1316	ViewCell::NewMail();
1317	const int frontAndBackId = ViewCell::sMailId;
1318
1319	bool useRand;;
1320	int limit;
1321
1322	// choose test polyongs randomly if over threshold
1323	if ((int)polys.size() > mMaxTests)
1324	{
1325	useRand = true;
1326	limit = mMaxTests;
1327	}
1328	else
1329	{
1330	useRand = false;
1331	limit = (int)polys.size();
1332	}
1333
1334
1335	for (int i = 0; i < limit; ++ i)
1336	{
1337	const int testIdx = useRand ? (int)RandomValue(0, limit - 1) : i;
1338
1339	Polygon3 *poly = polys[testIdx];
1340
1341	const int classification =
1342	poly->ClassifyPlane(candidatePlane, mEpsilon);
1343
1344	if (mSplitPlaneStrategy & BALANCED_POLYS)
1345	sumBalancedPolys += sBalancedPolysTable[classification];
1346
1347	if (mSplitPlaneStrategy & LEAST_SPLITS)
1348	sumSplits += sLeastPolySplitsTable[classification];
1349
1350	if (mSplitPlaneStrategy & LARGEST_POLY_AREA)
1351	{
1352	if (classification == Polygon3::COINCIDENT)
1353	sumPolyArea += poly->GetArea();
1354	//totalArea += area;
1355	}
1356
1357	if (mSplitPlaneStrategy & BLOCKED_RAYS)
1358	{
1359	const float blockedRays = (float)poly->mPiercingRays.size();
1360
1361	if (classification == Polygon3::COINCIDENT)
1362	sumBlockedRays += blockedRays;
1363
1364	totalBlockedRays += blockedRays;
1365	}
1366
1367	// assign view cells to back or front according to classificaion
1368	if (mSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1369	{
1370	MeshInstance *viewCell = poly->mParent;
1371
1372	// assure that we only count a view cell
1373	// once for the front and once for the back side of the plane
1374	if (classification == Polygon3::FRONT_SIDE)
1375	{
1376	if ((viewCell->mMailbox != frontId) &&
1377	(viewCell->mMailbox != frontAndBackId))
1378	{
1379	sumBalancedViewCells += 1.0;
1380
1381	if (viewCell->mMailbox != backId)
1382	viewCell->mMailbox = frontId;
1383	else
1384	viewCell->mMailbox = frontAndBackId;
1385
1386	++ totalViewCells;
1387	}
1388	}
1389	else if (classification == Polygon3::BACK_SIDE)
1390	{
1391	if ((viewCell->mMailbox != backId) &&
1392	(viewCell->mMailbox != frontAndBackId))
1393	{
1394	sumBalancedViewCells -= 1.0;
1395
1396	if (viewCell->mMailbox != frontId)
1397	viewCell->mMailbox = backId;
1398	else
1399	viewCell->mMailbox = frontAndBackId;
1400
1401	++ totalViewCells;
1402	}
1403	}
1404	}
1405	}
1406
1407	const float polysSize = (float)polys.size() + Limits::Small;
1408
1409	// all values should be approx. between 0 and 1 so they can be combined
1410	// and scaled with the factors according to their importance
1411	if (mSplitPlaneStrategy & BALANCED_POLYS)
1412	val += mBalancedPolysFactor * fabs(sumBalancedPolys) / polysSize;
1413
1414	if (mSplitPlaneStrategy & LEAST_SPLITS)
1415	val += mLeastSplitsFactor * sumSplits / polysSize;
1416
1417	if (mSplitPlaneStrategy & LARGEST_POLY_AREA)
1418	// HACK: polys.size should be total area so scaling is between 0 and 1
1419	val += mLargestPolyAreaFactor * (float)polys.size() / sumPolyArea;
1420
1421	if (mSplitPlaneStrategy & BLOCKED_RAYS)
1422	if (totalBlockedRays != 0)
1423	val += mBlockedRaysFactor * (totalBlockedRays - sumBlockedRays) / totalBlockedRays;
1424
1425	if (mSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1426	val += mBalancedViewCellsFactor * fabs(sumBalancedViewCells) /
1427	((float)totalViewCells + Limits::Small);
1428
1429	return val;
1430	}
1431
1432
1433	inline void BspTree::GenerateUniqueIdsForPvs()
1434	{
1435	Intersectable::NewMail(); sBackId = ViewCell::sMailId;
1436	Intersectable::NewMail(); sFrontId = ViewCell::sMailId;
1437	Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;
1438	}
1439
1440	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1441	const BoundedRayContainer &rays,
1442	const int pvs,
1443	const float area,
1444	const BspNodeGeometry &cell) const
1445	{
1446	float val = 0;
1447
1448	float sumBalancedRays = 0;
1449	float sumRaySplits = 0;
1450
1451	int frontPvs = 0;
1452	int backPvs = 0;
1453
1454	// probability that view point lies in child
1455	float pOverall = 0;
1456	float pFront = 0;
1457	float pBack = 0;
1458
1459	const bool pvsUseLen = false;
1460
1461	if (mSplitPlaneStrategy & PVS)
1462	{
1463	// create unique ids for pvs heuristics
1464	GenerateUniqueIdsForPvs();
1465
1466	if (mPvsUseArea) // use front and back cell areas to approximate volume
1467	{
1468	// construct child geometry with regard to the candidate split plane
1469	BspNodeGeometry frontCell;
1470	BspNodeGeometry backCell;
1471
1472	cell.SplitGeometry(frontCell,
1473	backCell,
1474	candidatePlane,
1475	mBox,
1476	mEpsilon);
1477
1478	pFront = frontCell.GetArea();
1479	pBack = backCell.GetArea();
1480
1481	pOverall = area;
1482	}
1483	}
1484
1485	bool useRand;;
1486	int limit;
1487
1488	// choose test polyongs randomly if over threshold
1489	if ((int)rays.size() > mMaxTests)
1490	{
1491	useRand = true;
1492	limit = mMaxTests;
1493	}
1494	else
1495	{
1496	useRand = false;
1497	limit = (int)rays.size();
1498	}
1499
1500	for (int i = 0; i < limit; ++ i)
1501	{
1502	const int testIdx = useRand ? (int)RandomValue(0, (Real)(limit - 1)) : i;
1503
1504	BoundedRay *bRay = rays[testIdx];
1505
1506	Ray *ray = bRay->mRay;
1507	const float minT = bRay->mMinT;
1508	const float maxT = bRay->mMaxT;
1509
1510	Vector3 entP, extP;
1511
1512	const int cf =
1513	ray->ClassifyPlane(candidatePlane, minT, maxT, entP, extP);
1514
1515	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1516	{
1517	sumBalancedRays += sBalancedRaysTable[cf];
1518	}
1519
1520	if (mSplitPlaneStrategy & BALANCED_RAYS)
1521	{
1522	sumRaySplits += sLeastRaySplitsTable[cf];
1523	}
1524
1525	if (mSplitPlaneStrategy & PVS)
1526	{
1527	// in case the ray intersects an object
1528	// assure that we only count the object
1529	// once for the front and once for the back side of the plane
1530
1531	// add the termination object
1532	if (!ray->intersections.empty())
1533	AddObjToPvs(ray->intersections[0].mObject, cf, frontPvs, backPvs);
1534
1535	// add the source object
1536	AddObjToPvs(ray->sourceObject.mObject, cf, frontPvs, backPvs);
1537
1538	if (mPvsUseArea)
1539	{
1540	float len = 1;
1541
1542	if (pvsUseLen)
1543	len = SqrDistance(entP, extP);
1544
1545	// use length of rays to approximate volume
1546	if (Ray::BACK && Ray::COINCIDENT)
1547	pBack += len;
1548	if (Ray::FRONT && Ray::COINCIDENT)
1549	pFront += len;
1550	if (Ray::FRONT_BACK \|\| Ray::BACK_FRONT)
1551	{
1552	if (pvsUseLen)
1553	{
1554	const Vector3 extp = ray->Extrap(maxT);
1555	const float t = candidatePlane.FindT(ray->GetLoc(), extp);
1556
1557	const float newT = t * maxT;
1558	const float newLen = SqrDistance(ray->Extrap(newT), extp);
1559
1560	if (Ray::FRONT_BACK)
1561	{
1562	pFront += len - newLen;
1563	pBack += newLen;
1564	}
1565	else
1566	{
1567	pBack += len - newLen;
1568	pFront += newLen;
1569	}
1570	}
1571	else
1572	{
1573	++ pFront;
1574	++ pBack;
1575	}
1576	}
1577	}
1578	}
1579	}
1580
1581	const float raysSize = (float)rays.size() + Limits::Small;
1582
1583	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1584	val += mLeastRaySplitsFactor * sumRaySplits / raysSize;
1585
1586	if (mSplitPlaneStrategy & BALANCED_RAYS)
1587	val += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
1588
1589	const float denom = pOverall * (float)pvs * 2.0f + Limits::Small;
1590
1591	if (mSplitPlaneStrategy & PVS)
1592	{
1593	val += mPvsFactor * (frontPvs * pFront + (backPvs * pBack)) / denom;
1594
1595	// give penalty to unbalanced split
1596	if (0)
1597	if (((pFront * 0.2 + Limits::Small) > pBack) \|\|
1598	(pFront < (pBack * 0.2 + Limits::Small)))
1599	val += 0.5;
1600	}
1601
1602
1603	#ifdef _DEBUG
1604	Debug << "totalpvs: " << pvs << " ptotal: " << pOverall
1605	<< " frontpvs: " << frontPvs << " pFront: " << pFront
1606	<< " backpvs: " << backPvs << " pBack: " << pBack << endl << endl;
1607	#endif
1608
1609	return val;
1610	}
1611
1612	void BspTree::AddObjToPvs(Intersectable *obj,
1613	const int cf,
1614	int &frontPvs,
1615	int &backPvs) const
1616	{
1617	if (!obj)
1618	return;
1619	// TODO: does this really belong to no pvs?
1620	//if (cf == Ray::COINCIDENT) return;
1621
1622	// object belongs to both PVS
1623	const bool bothSides = (cf == Ray::FRONT_BACK) \|\|
1624	(cf == Ray::BACK_FRONT) \|\|
1625	(cf == Ray::COINCIDENT);
1626
1627	if ((cf == Ray::FRONT) \|\| bothSides)
1628	{
1629	if ((obj->mMailbox != sFrontId) &&
1630	(obj->mMailbox != sFrontAndBackId))
1631	{
1632	++ frontPvs;
1633
1634	if (obj->mMailbox == sBackId)
1635	obj->mMailbox = sFrontAndBackId;
1636	else
1637	obj->mMailbox = sFrontId;
1638	}
1639	}
1640
1641	if ((cf == Ray::BACK) \|\| bothSides)
1642	{
1643	if ((obj->mMailbox != sBackId) &&
1644	(obj->mMailbox != sFrontAndBackId))
1645	{
1646	++ backPvs;
1647
1648	if (obj->mMailbox == sFrontId)
1649	obj->mMailbox = sFrontAndBackId;
1650	else
1651	obj->mMailbox = sBackId;
1652	}
1653	}
1654	}
1655
1656	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1657	BspTraversalData &data) const
1658	{
1659	float val = 0;
1660
1661	if (mSplitPlaneStrategy & VERTICAL_AXIS)
1662	{
1663	Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
1664	// we put a penalty on the dot product between the "tiny" vertical axis
1665	// and the split plane axis
1666	val += mVerticalSplitsFactor *
1667	fabs(DotProd(candidatePlane.mNormal, tinyAxis));
1668	}
1669
1670	// the following criteria loop over all polygons to find the cost value
1671	if ((mSplitPlaneStrategy & BALANCED_POLYS) \|\|
1672	(mSplitPlaneStrategy & LEAST_SPLITS) \|\|
1673	(mSplitPlaneStrategy & LARGEST_POLY_AREA) \|\|
1674	(mSplitPlaneStrategy & BALANCED_VIEW_CELLS) \|\|
1675	(mSplitPlaneStrategy & BLOCKED_RAYS))
1676	{
1677	val += SplitPlaneCost(candidatePlane, *data.mPolygons);
1678	}
1679
1680	// the following criteria loop over all rays to find the cost value
1681	if ((mSplitPlaneStrategy & BALANCED_RAYS) \|\|
1682	(mSplitPlaneStrategy & LEAST_RAY_SPLITS) \|\|
1683	(mSplitPlaneStrategy & PVS))
1684	{
1685	val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs,
1686	data.mArea, *data.mGeometry);
1687	}
1688
1689	// return linear combination of the sums
1690	return val;
1691	}
1692
1693	void BspTree::CollectLeaves(vector<BspLeaf *> &leaves) const
1694	{
1695	stack<BspNode *> nodeStack;
1696	nodeStack.push(mRoot);
1697
1698	while (!nodeStack.empty())
1699	{
1700	BspNode *node = nodeStack.top();
1701
1702	nodeStack.pop();
1703
1704	if (node->IsLeaf())
1705	{
1706	BspLeaf leaf = (BspLeaf )node;
1707	leaves.push_back(leaf);
1708	}
1709	else
1710	{
1711	BspInterior interior = dynamic_cast<BspInterior >(node);
1712
1713	nodeStack.push(interior->GetBack());
1714	nodeStack.push(interior->GetFront());
1715	}
1716	}
1717	}
1718
1719	AxisAlignedBox3 BspTree::GetBoundingBox() const
1720	{
1721	return mBox;
1722	}
1723
1724	BspNode *BspTree::GetRoot() const
1725	{
1726	return mRoot;
1727	}
1728
1729	void BspTree::EvaluateLeafStats(const BspTraversalData &data)
1730	{
1731	// the node became a leaf -> evaluate stats for leafs
1732	BspLeaf leaf = dynamic_cast<BspLeaf >(data.mNode);
1733
1734	// store maximal and minimal depth
1735	if (data.mDepth > mStat.maxDepth)
1736	mStat.maxDepth = data.mDepth;
1737
1738	if (data.mDepth < mStat.minDepth)
1739	mStat.minDepth = data.mDepth;
1740
1741	// accumulate depth to compute average depth
1742	mStat.accumDepth += data.mDepth;
1743
1744
1745	if (data.mDepth >= mTermMaxDepth)
1746	++ mStat.maxDepthNodes;
1747
1748	if (data.mPvs < mTermMinPvs)
1749	++ mStat.minPvsNodes;
1750
1751	if ((int)data.mRays->size() < mTermMinRays)
1752	++ mStat.minRaysNodes;
1753
1754	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1755	++ mStat.maxRayContribNodes;
1756
1757	if (data.mGeometry->GetArea() <= mTermMinArea)
1758	++ mStat.minAreaNodes;
1759
1760	#ifdef _DEBUG
1761	Debug << "BSP stats: "
1762	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1763	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1764	<< "Area: " << data.mArea << " (min: " << mTermMinArea << "), "
1765	<< "#polygons: " << (int)data.mPolygons->size() << " (max: " << mTermMinPolys << "), "
1766	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1767	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
1768	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1769	#endif
1770	}
1771
1772	int
1773	BspTree::_CastRay(Ray &ray)
1774	{
1775	int hits = 0;
1776
1777	stack<BspRayTraversalData> tStack;
1778
1779	float maxt, mint;
1780
1781	if (!mBox.GetRaySegment(ray, mint, maxt))
1782	return 0;
1783
1784	Intersectable::NewMail();
1785
1786	Vector3 entp = ray.Extrap(mint);
1787	Vector3 extp = ray.Extrap(maxt);
1788
1789	BspNode *node = mRoot;
1790	BspNode *farChild = NULL;
1791
1792	while (1)
1793	{
1794	if (!node->IsLeaf())
1795	{
1796	BspInterior in = dynamic_cast<BspInterior >(node);
1797
1798	Plane3 splitPlane = in->GetPlane();
1799	const int entSide = splitPlane.Side(entp);
1800	const int extSide = splitPlane.Side(extp);
1801
1802	if (entSide < 0)
1803	{
1804	node = in->GetBack();
1805
1806	if(extSide <= 0) // plane does not split ray => no far child
1807	continue;
1808
1809	farChild = in->GetFront(); // plane splits ray
1810
1811	} else if (entSide > 0)
1812	{
1813	node = in->GetFront();
1814
1815	if (extSide >= 0) // plane does not split ray => no far child
1816	continue;
1817
1818	farChild = in->GetBack(); // plane splits ray
1819	}
1820	else // ray and plane are coincident
1821	{
1822	// WHAT TO DO IN THIS CASE ?
1823	//break;
1824	node = in->GetFront();
1825	continue;
1826	}
1827
1828	// push data for far child
1829	tStack.push(BspRayTraversalData(farChild, extp, maxt));
1830
1831	// find intersection of ray segment with plane
1832	float t;
1833	extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
1834	maxt *= t;
1835
1836	} else // reached leaf => intersection with view cell
1837	{
1838	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
1839
1840	if (!leaf->mViewCell->Mailed())
1841	{
1842	// ray.bspIntersections.push_back(Ray::BspIntersection(maxt, leaf));
1843	leaf->mViewCell->Mail();
1844	++ hits;
1845	}
1846
1847	//-- fetch the next far child from the stack
1848	if (tStack.empty())
1849	break;
1850
1851	entp = extp;
1852	mint = maxt; // NOTE: need this?
1853
1854	if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
1855	break;
1856
1857	BspRayTraversalData &s = tStack.top();
1858
1859	node = s.mNode;
1860	extp = s.mExitPoint;
1861	maxt = s.mMaxT;
1862
1863	tStack.pop();
1864	}
1865	}
1866
1867	return hits;
1868	}
1869
1870
1871	int BspTree::CastLineSegment(const Vector3 &origin,
1872	const Vector3 &termination,
1873	vector<ViewCell *> &viewcells)
1874	{
1875	int hits = 0;
1876	stack<BspRayTraversalData> tStack;
1877
1878	float mint = 0.0f, maxt = 1.0f;
1879
1880	Intersectable::NewMail();
1881
1882	Vector3 entp = origin;
1883	Vector3 extp = termination;
1884
1885	BspNode *node = mRoot;
1886	BspNode *farChild = NULL;
1887
1888	while (1) {
1889	if (!node->IsLeaf()) {
1890	BspInterior in = dynamic_cast<BspInterior >(node);
1891
1892	Plane3 splitPlane = in->GetPlane();
1893	const int entSide = splitPlane.Side(entp);
1894	const int extSide = splitPlane.Side(extp);
1895
1896	if (entSide < 0) {
1897	node = in->GetBack();
1898
1899	if(extSide <= 0) // plane does not split ray => no far child
1900	continue;
1901
1902	farChild = in->GetFront(); // plane splits ray
1903
1904	} else
1905	if (entSide > 0) {
1906	node = in->GetFront();
1907
1908	if (extSide >= 0) // plane does not split ray => no far child
1909	continue;
1910
1911	farChild = in->GetBack(); // plane splits ray
1912	}
1913	else // ray and plane are coincident
1914	{
1915	// WHAT TO DO IN THIS CASE ?
1916	//break;
1917	node = in->GetFront();
1918	continue;
1919	}
1920
1921	// push data for far child
1922	tStack.push(BspRayTraversalData(farChild, extp, maxt));
1923
1924	// find intersection of ray segment with plane
1925	float t;
1926	extp = splitPlane.FindIntersection(origin, extp, &t);
1927	maxt *= t;
1928
1929	} else {
1930	// reached leaf => intersection with view cell
1931	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
1932
1933	if (!leaf->mViewCell->Mailed()) {
1934	viewcells.push_back(leaf->mViewCell);
1935	leaf->mViewCell->Mail();
1936	hits++;
1937	}
1938
1939	//-- fetch the next far child from the stack
1940	if (tStack.empty())
1941	break;
1942
1943	entp = extp;
1944	mint = maxt; // NOTE: need this?
1945
1946	BspRayTraversalData &s = tStack.top();
1947
1948	node = s.mNode;
1949	extp = s.mExitPoint;
1950	maxt = s.mMaxT;
1951
1952	tStack.pop();
1953	}
1954	}
1955	return hits;
1956	}
1957
1958	bool BspTree::Export(const string filename)
1959	{
1960	Exporter *exporter = Exporter::GetExporter(filename);
1961
1962	if (exporter)
1963	{
1964	exporter->ExportBspTree(*this);
1965	return true;
1966	}
1967
1968	return false;
1969	}
1970
1971	void BspTree::CollectViewCells(ViewCellContainer &viewCells) const
1972	{
1973	stack<BspNode *> nodeStack;
1974	nodeStack.push(mRoot);
1975
1976	ViewCell::NewMail();
1977
1978	while (!nodeStack.empty())
1979	{
1980	BspNode *node = nodeStack.top();
1981	nodeStack.pop();
1982
1983	if (node->IsLeaf())
1984	{
1985	ViewCell viewCell = dynamic_cast<BspLeaf >(node)->mViewCell;
1986
1987	if (!viewCell->Mailed())
1988	{
1989	viewCell->Mail();
1990	viewCells.push_back(viewCell);
1991	}
1992	}
1993	else
1994	{
1995	BspInterior interior = dynamic_cast<BspInterior >(node);
1996
1997	nodeStack.push(interior->GetFront());
1998	nodeStack.push(interior->GetBack());
1999	}
2000	}
2001	}
2002
2003	void BspTree::EvaluateViewCellsStats(ViewCellsStatistics &vcStat) const
2004	{
2005	vcStat.Reset();
2006
2007	stack<BspNode *> nodeStack;
2008	nodeStack.push(mRoot);
2009
2010	ViewCell::NewMail();
2011
2012	// exclude root cell
2013	mRootCell->Mail();
2014
2015	while (!nodeStack.empty())
2016	{
2017	BspNode *node = nodeStack.top();
2018	nodeStack.pop();
2019
2020	if (node->IsLeaf())
2021	{
2022	++ vcStat.leaves;
2023
2024	BspViewCell viewCell = dynamic_cast<BspLeaf >(node)->mViewCell;
2025
2026	if (!viewCell->Mailed())
2027	{
2028	viewCell->Mail();
2029
2030	++ vcStat.viewCells;
2031	const int pvsSize = viewCell->GetPvs().GetSize();
2032
2033	vcStat.pvs += pvsSize;
2034
2035	if (pvsSize < 1)
2036	++ vcStat.emptyPvs;
2037
2038	if (pvsSize > vcStat.maxPvs)
2039	vcStat.maxPvs = pvsSize;
2040
2041	if (pvsSize < vcStat.minPvs)
2042	vcStat.minPvs = pvsSize;
2043
2044	if ((int)viewCell->mLeaves.size() > vcStat.maxLeaves)
2045	vcStat.maxLeaves = (int)viewCell->mLeaves.size();
2046	}
2047	}
2048	else
2049	{
2050	BspInterior interior = dynamic_cast<BspInterior >(node);
2051
2052	nodeStack.push(interior->GetFront());
2053	nodeStack.push(interior->GetBack());
2054	}
2055	}
2056	}
2057
2058	BspTreeStatistics &BspTree::GetStat()
2059	{
2060	return mStat;
2061	}
2062
2063	float BspTree::AccumulatedRayLength(BoundedRayContainer &rays) const
2064	{
2065	float len = 0;
2066
2067	BoundedRayContainer::const_iterator it, it_end = rays.end();
2068
2069	for (it = rays.begin(); it != it_end; ++ it)
2070	{
2071	len += SqrDistance((it)->mRay->Extrap((it)->mMinT),
2072	(it)->mRay->Extrap((it)->mMaxT));
2073	}
2074
2075	return len;
2076	}
2077
2078	int BspTree::SplitRays(const Plane3 &plane,
2079	BoundedRayContainer &rays,
2080	BoundedRayContainer &frontRays,
2081	BoundedRayContainer &backRays)
2082	{
2083	int splits = 0;
2084
2085	while (!rays.empty())
2086	{
2087	BoundedRay *bRay = rays.back();
2088	Ray *ray = bRay->mRay;
2089	float minT = bRay->mMinT;
2090	float maxT = bRay->mMaxT;
2091
2092	rays.pop_back();
2093
2094	Vector3 entP, extP;
2095
2096	const int cf =
2097	ray->ClassifyPlane(plane, minT, maxT, entP, extP);
2098
2099	// set id to ray classification
2100	ray->SetId(cf);
2101
2102	switch (cf)
2103	{
2104	case Ray::COINCIDENT: // TODO: should really discard ray?
2105	frontRays.push_back(bRay);
2106	//DEL_PTR(bRay);
2107	break;
2108	case Ray::BACK:
2109	backRays.push_back(bRay);
2110	break;
2111	case Ray::FRONT:
2112	frontRays.push_back(bRay);
2113	break;
2114	case Ray::FRONT_BACK:
2115	{
2116	// find intersection of ray segment with plane
2117	const float t = plane.FindT(ray->GetLoc(), extP);
2118
2119	const float newT = t * maxT;
2120
2121	frontRays.push_back(new BoundedRay(ray, minT, newT));
2122	backRays.push_back(new BoundedRay(ray, newT, maxT));
2123
2124	DEL_PTR(bRay);
2125	}
2126	break;
2127	case Ray::BACK_FRONT:
2128	{
2129	// find intersection of ray segment with plane
2130	const float t = plane.FindT(ray->GetLoc(), extP);
2131	const float newT = t * bRay->mMaxT;
2132
2133	backRays.push_back(new BoundedRay(ray, minT, newT));
2134	frontRays.push_back(new BoundedRay(ray, newT, maxT));
2135
2136	DEL_PTR(bRay);
2137
2138	++ splits;
2139	}
2140	break;
2141	default:
2142	Debug << "Should not come here 4" << endl;
2143	break;
2144	}
2145	}
2146
2147	return splits;
2148	}
2149
2150	void BspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
2151	{
2152	BspNode *lastNode;
2153	do
2154	{
2155	lastNode = n;
2156
2157	// want to get planes defining geometry of this node => don't take
2158	// split plane of node itself
2159	n = n->GetParent();
2160
2161	if (n)
2162	{
2163	BspInterior interior = dynamic_cast<BspInterior >(n);
2164	Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
2165
2166	if (interior->GetFront() != lastNode)
2167	halfSpace.ReverseOrientation();
2168
2169	halfSpaces.push_back(halfSpace);
2170	}
2171	}
2172	while (n);
2173	}
2174
2175	void BspTree::ConstructGeometry(BspNode *n, BspNodeGeometry &cell) const
2176	{
2177	PolygonContainer polys;
2178	ConstructGeometry(n, polys);
2179	cell.mPolys = polys;
2180	}
2181
2182	void BspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &cell) const
2183	{
2184	vector<BspLeaf *> leaves = vc->mLeaves;
2185
2186	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2187
2188	for (it = leaves.begin(); it != it_end; ++ it)
2189	ConstructGeometry(*it, cell);
2190	}
2191
2192
2193	void BspTree::ConstructGeometry(BspNode *n, PolygonContainer &cell) const
2194	{
2195	vector<Plane3> halfSpaces;
2196	ExtractHalfSpaces(n, halfSpaces);
2197
2198	PolygonContainer candidates;
2199
2200	// bounded planes are added to the polygons (reverse polygons
2201	// as they have to be outfacing
2202	for (int i = 0; i < (int)halfSpaces.size(); ++ i)
2203	{
2204	Polygon3 *p = GetBoundingBox().CrossSection(halfSpaces[i]);
2205
2206	if (p->Valid(mEpsilon))
2207	{
2208	candidates.push_back(p->CreateReversePolygon());
2209	DEL_PTR(p);
2210	}
2211	}
2212
2213	// add faces of bounding box (also could be faces of the cell)
2214	for (int i = 0; i < 6; ++ i)
2215	{
2216	VertexContainer vertices;
2217
2218	for (int j = 0; j < 4; ++ j)
2219	vertices.push_back(mBox.GetFace(i).mVertices[j]);
2220
2221	candidates.push_back(new Polygon3(vertices));
2222	}
2223
2224	for (int i = 0; i < (int)candidates.size(); ++ i)
2225	{
2226	// polygon is split by all other planes
2227	for (int j = 0; (j < (int)halfSpaces.size()) && candidates[i]; ++ j)
2228	{
2229	if (i == j) // polygon and plane are coincident
2230	continue;
2231
2232	VertexContainer splitPts;
2233	Polygon3 frontPoly, backPoly;
2234
2235	const int cf = candidates[i]->
2236	ClassifyPlane(halfSpaces[j], mEpsilon);
2237
2238	switch (cf)
2239	{
2240	case Polygon3::SPLIT:
2241	frontPoly = new Polygon3();
2242	backPoly = new Polygon3();
2243
2244	candidates[i]->Split(halfSpaces[j],
2245	*frontPoly,
2246	*backPoly,
2247	mEpsilon);
2248
2249	DEL_PTR(candidates[i]);
2250
2251	if (frontPoly->Valid(mEpsilon))
2252	candidates[i] = frontPoly;
2253	else
2254	DEL_PTR(frontPoly);
2255
2256	DEL_PTR(backPoly);
2257	break;
2258	case Polygon3::BACK_SIDE:
2259	DEL_PTR(candidates[i]);
2260	break;
2261	// just take polygon as it is
2262	case Polygon3::FRONT_SIDE:
2263	case Polygon3::COINCIDENT:
2264	default:
2265	break;
2266	}
2267	}
2268
2269	if (candidates[i])
2270	cell.push_back(candidates[i]);
2271	}
2272	}
2273
2274
2275	int BspTree::FindNeighbors(BspNode n, vector<BspLeaf > &neighbors,
2276	const bool onlyUnmailed) const
2277	{
2278	PolygonContainer cell;
2279
2280	ConstructGeometry(n, cell);
2281
2282	stack<BspNode *> nodeStack;
2283	nodeStack.push(mRoot);
2284
2285	// planes needed to verify that we found neighbor leaf.
2286	vector<Plane3> halfSpaces;
2287	ExtractHalfSpaces(n, halfSpaces);
2288
2289	while (!nodeStack.empty())
2290	{
2291	BspNode *node = nodeStack.top();
2292	nodeStack.pop();
2293
2294	if (node->IsLeaf())
2295	{
2296	if (node != n && (!onlyUnmailed \|\| !node->Mailed()))
2297	{
2298	// test all planes of current node if candidate really
2299	// is neighbour
2300	PolygonContainer neighborCandidate;
2301	ConstructGeometry(node, neighborCandidate);
2302
2303	bool isAdjacent = true;
2304	for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
2305	{
2306	const int cf =
2307	Polygon3::ClassifyPlane(neighborCandidate,
2308	halfSpaces[i],
2309	mEpsilon);
2310
2311	if (cf == Polygon3::BACK_SIDE)
2312	isAdjacent = false;
2313	}
2314
2315	if (isAdjacent)
2316	neighbors.push_back(dynamic_cast<BspLeaf *>(node));
2317
2318	CLEAR_CONTAINER(neighborCandidate);
2319	}
2320	}
2321	else
2322	{
2323	BspInterior interior = dynamic_cast<BspInterior >(node);
2324
2325	const int cf = Polygon3::ClassifyPlane(cell,
2326	interior->mPlane,
2327	mEpsilon);
2328
2329	if (cf == Polygon3::FRONT_SIDE)
2330	nodeStack.push(interior->GetFront());
2331	else
2332	if (cf == Polygon3::BACK_SIDE)
2333	nodeStack.push(interior->GetBack());
2334	else
2335	{
2336	// random decision
2337	nodeStack.push(interior->GetBack());
2338	nodeStack.push(interior->GetFront());
2339	}
2340	}
2341	}
2342
2343	CLEAR_CONTAINER(cell);
2344	return (int)neighbors.size();
2345	}
2346
2347	BspLeaf *BspTree::GetRandomLeaf(const Plane3 &halfspace)
2348	{
2349	stack<BspNode *> nodeStack;
2350	nodeStack.push(mRoot);
2351
2352	int mask = rand();
2353
2354	while (!nodeStack.empty())
2355	{
2356	BspNode *node = nodeStack.top();
2357	nodeStack.pop();
2358
2359	if (node->IsLeaf())
2360	{
2361	return dynamic_cast<BspLeaf *>(node);
2362	}
2363	else
2364	{
2365	BspInterior interior = dynamic_cast<BspInterior >(node);
2366
2367	BspNode *next;
2368
2369	PolygonContainer cell;
2370
2371	// todo: not very efficient: constructs full cell everytime
2372	ConstructGeometry(interior, cell);
2373
2374	const int cf = Polygon3::ClassifyPlane(cell,
2375	halfspace,
2376	mEpsilon);
2377
2378	if (cf == Polygon3::BACK_SIDE)
2379	next = interior->GetFront();
2380	else
2381	if (cf == Polygon3::FRONT_SIDE)
2382	next = interior->GetFront();
2383	else
2384	{
2385	// random decision
2386	if (mask & 1)
2387	next = interior->GetBack();
2388	else
2389	next = interior->GetFront();
2390	mask = mask >> 1;
2391	}
2392
2393	nodeStack.push(next);
2394	}
2395	}
2396
2397	return NULL;
2398	}
2399
2400	BspLeaf *BspTree::GetRandomLeaf(const bool onlyUnmailed)
2401	{
2402	stack<BspNode *> nodeStack;
2403
2404	nodeStack.push(mRoot);
2405
2406	int mask = rand();
2407
2408	while (!nodeStack.empty())
2409	{
2410	BspNode *node = nodeStack.top();
2411	nodeStack.pop();
2412
2413	if (node->IsLeaf())
2414	{
2415	if ( (!onlyUnmailed \|\| !node->Mailed()) )
2416	return dynamic_cast<BspLeaf *>(node);
2417	}
2418	else
2419	{
2420	BspInterior interior = dynamic_cast<BspInterior >(node);
2421
2422	// random decision
2423	if (mask & 1)
2424	nodeStack.push(interior->GetBack());
2425	else
2426	nodeStack.push(interior->GetFront());
2427
2428	mask = mask >> 1;
2429	}
2430	}
2431
2432	return NULL;
2433	}
2434
2435	void BspTree::AddToPvs(BspLeaf *leaf,
2436	const BoundedRayContainer &rays,
2437	int &sampleContributions,
2438	int &contributingSamples)
2439	{
2440	sampleContributions = 0;
2441	contributingSamples = 0;
2442
2443	BoundedRayContainer::const_iterator it, it_end = rays.end();
2444
2445	ViewCell *vc = leaf->GetViewCell();
2446
2447	// add contributions from samples to the PVS
2448	for (it = rays.begin(); it != it_end; ++ it)
2449	{
2450	int contribution = 0;
2451	Ray ray = (it)->mRay;
2452	float relContribution;
2453	if (!ray->intersections.empty())
2454	contribution += vc->GetPvs().AddSample(ray->intersections[0].mObject, relContribution);
2455
2456	if (ray->sourceObject.mObject)
2457	contribution += vc->GetPvs().AddSample(ray->sourceObject.mObject, relContribution);
2458
2459	if (contribution)
2460	{
2461	sampleContributions += contribution;
2462	++ contributingSamples;
2463	}
2464
2465	//if (ray->mFlags & Ray::STORE_BSP_INTERSECTIONS)
2466	// ray->bspIntersections.push_back(Ray::BspIntersection((*it)->mMinT, this));
2467	}
2468	}
2469
2470	int BspTree::ComputePvsSize(const BoundedRayContainer &rays) const
2471	{
2472	int pvsSize = 0;
2473
2474	BoundedRayContainer::const_iterator rit, rit_end = rays.end();
2475
2476	Intersectable::NewMail();
2477
2478	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2479	{
2480	Ray ray = (rit)->mRay;
2481
2482	if (!ray->intersections.empty())
2483	{
2484	if (!ray->intersections[0].mObject->Mailed())
2485	{
2486	ray->intersections[0].mObject->Mail();
2487	++ pvsSize;
2488	}
2489	}
2490	if (ray->sourceObject.mObject)
2491	{
2492	if (!ray->sourceObject.mObject->Mailed())
2493	{
2494	ray->sourceObject.mObject->Mail();
2495	++ pvsSize;
2496	}
2497	}
2498	}
2499
2500	return pvsSize;
2501	}
2502
2503	float BspTree::GetEpsilon() const
2504	{
2505	return mEpsilon;
2506	}
2507
2508
2509	/*************************************************************/
2510	/* BspNodeGeometry Implementation */
2511	/*************************************************************/
2512
2513	BspNodeGeometry::~BspNodeGeometry()
2514	{
2515	CLEAR_CONTAINER(mPolys);
2516	}
2517
2518	float BspNodeGeometry::GetArea() const
2519	{
2520	return Polygon3::GetArea(mPolys);
2521	}
2522
2523	void BspNodeGeometry::SplitGeometry(BspNodeGeometry &front,
2524	BspNodeGeometry &back,
2525	const Plane3 &splitPlane,
2526	const AxisAlignedBox3 &box,
2527	const float epsilon) const
2528	{
2529	// get cross section of new polygon
2530	Polygon3 *planePoly = box.CrossSection(splitPlane);
2531
2532	// split polygon with all other polygons
2533	planePoly = SplitPolygon(planePoly, epsilon);
2534
2535	//-- new polygon splits all other polygons
2536	for (int i = 0; i < (int)mPolys.size(); ++ i)
2537	{
2538	/// don't use epsilon here to get exact split planes
2539	const int cf =
2540	mPolys[i]->ClassifyPlane(splitPlane, Limits::Small);
2541
2542	switch (cf)
2543	{
2544	case Polygon3::SPLIT:
2545	{
2546	Polygon3 *poly = new Polygon3(mPolys[i]->mVertices);
2547
2548	Polygon3 *frontPoly = new Polygon3();
2549	Polygon3 *backPoly = new Polygon3();
2550
2551	poly->Split(splitPlane,
2552	*frontPoly,
2553	*backPoly,
2554	epsilon);
2555
2556	DEL_PTR(poly);
2557
2558	if (frontPoly->Valid(epsilon))
2559	front.mPolys.push_back(frontPoly);
2560	else
2561	DEL_PTR(frontPoly);
2562
2563	if (backPoly->Valid(epsilon))
2564	back.mPolys.push_back(backPoly);
2565	else
2566	DEL_PTR(backPoly);
2567	}
2568
2569	break;
2570	case Polygon3::BACK_SIDE:
2571	back.mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
2572	break;
2573	case Polygon3::FRONT_SIDE:
2574	front.mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
2575	break;
2576	case Polygon3::COINCIDENT:
2577	//front.mPolys.push_back(CreateReversePolygon(mPolys[i]));
2578	back.mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
2579	break;
2580	default:
2581	break;
2582	}
2583	}
2584
2585	//-- finally add the new polygon to the child node geometries
2586	if (planePoly)
2587	{
2588	// add polygon with normal pointing into positive half space to back cell
2589	back.mPolys.push_back(planePoly);
2590	// add polygon with reverse orientation to front cell
2591	front.mPolys.push_back(planePoly->CreateReversePolygon());
2592	}
2593
2594	//Debug << "returning new geometry " << mPolys.size() << " f: " << front.mPolys.size() << " b: " << back.mPolys.size() << endl;
2595	//Debug << "old area " << GetArea() << " f: " << front.GetArea() << " b: " << back.GetArea() << endl;
2596	}
2597
2598	Polygon3 BspNodeGeometry::SplitPolygon(Polygon3 planePoly,
2599	const float epsilon) const
2600	{
2601	if (!planePoly->Valid(epsilon))
2602	DEL_PTR(planePoly);
2603
2604	// polygon is split by all other planes
2605	for (int i = 0; (i < (int)mPolys.size()) && planePoly; ++ i)
2606	{
2607	Plane3 plane = mPolys[i]->GetSupportingPlane();
2608
2609	/// don't use epsilon here to get exact split planes
2610	const int cf =
2611	planePoly->ClassifyPlane(plane, Limits::Small);
2612
2613	// split new polygon with all previous planes
2614	switch (cf)
2615	{
2616	case Polygon3::SPLIT:
2617	{
2618	Polygon3 *frontPoly = new Polygon3();
2619	Polygon3 *backPoly = new Polygon3();
2620
2621	planePoly->Split(plane,
2622	*frontPoly,
2623	*backPoly,
2624	epsilon);
2625
2626	// don't need anymore
2627	DEL_PTR(planePoly);
2628	DEL_PTR(frontPoly);
2629
2630	// back polygon is belonging to geometry
2631	if (backPoly->Valid(epsilon))
2632	planePoly = backPoly;
2633	else
2634	DEL_PTR(backPoly);
2635	}
2636	break;
2637	case Polygon3::FRONT_SIDE:
2638	DEL_PTR(planePoly);
2639	break;
2640	// polygon is taken as it is
2641	case Polygon3::BACK_SIDE:
2642	case Polygon3::COINCIDENT:
2643	default:
2644	break;
2645	}
2646	}
2647
2648	return planePoly;
2649	}

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

Download in other formats: