Context Navigation

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

Revision 391, 61.6 KB checked in by mattausch, 19 years ago (diff)

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

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

Download in other formats: