Context Navigation

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

Revision 445, 62.1 KB checked in by mattausch, 19 years ago (diff)
Added VspBspTree? functionality: This is a view space partitioning specialised BSPtree. There are no polygon splits, but we split the sample rays. The candidates for the next split plane are evaluated only by checking the sampled visibility information. The polygons are employed merely as candidates for the next split planes.

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

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

Download in other formats: