Context Navigation

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

Revision 411, 62.5 KB checked in by mattausch, 19 years ago (diff)
worked on view space partition kd tree

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

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

Download in other formats: