Context Navigation

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

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

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

Download in other formats: