Context Navigation

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

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

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

Download in other formats: