Context Navigation

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

Revision 440, 62.9 KB checked in by mattausch, 19 years ago (diff)

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

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

Download in other formats: