Context Navigation

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

Revision 473, 66.2 KB checked in by mattausch, 19 years ago (diff)
worked on new features, removed Random Bug (took only 32000 values), removed bug when choosing new candidates (totally wrong) introduced new candidate plane method implemented priority queue for vsp bsp

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

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

Download in other formats: