Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h @ 352

Revision 352, 19.2 KB checked in by mattausch, 19 years ago (diff)

Line
1	#ifndef _ViewCellBsp_H__
2	#define _ViewCellBsp_H__
3
4	#include "Mesh.h"
5	#include "Containers.h"
6	#include <stack>
7
8	class ViewCell;
9	class Plane3;
10	class BspTree;
11	class BspInterior;
12	class Polygon3;
13	class AxisAlignedBox3;
14	class Ray;
15
16	struct BspRayTraversalData
17	{
18	BspNode *mNode;
19	Vector3 mExitPoint;
20	float mMaxT;
21
22	BspRayTraversalData() {}
23
24	BspRayTraversalData(BspNode *n, const Vector3 &extp, const float maxt):
25	mNode(n), mExitPoint(extp), mMaxT(maxt)
26	{}
27	};
28
29	class BspTreeStatistics
30	{
31	public:
32	// total number of nodes
33	int nodes;
34	// number of splits
35	int splits;
36	// totals number of rays
37	int rays;
38	// maximal reached depth
39	int maxDepth;
40	// minimal depth
41	int minDepth;
42	// max depth nodes
43	int maxDepthNodes;
44	// max number of rays per node
45	int maxObjectRefs;
46	// accumulated depth (used to compute average)
47	int accumDepth;
48	// number of initial polygons
49	int polys;
50	/// number of view cells different to the view cell representing unbounded space.
51	int viewCells;
52	/// size of the VPS
53	int pvs;
54	/// samples contributing to pvs
55	int contributingSamples;
56	/// sample contributions to pvs
57	int sampleContributions;
58
59	// Constructor
60	BspTreeStatistics()
61	{
62	Reset();
63	}
64
65	int Nodes() const {return nodes;}
66	int Interior() const { return nodes / 2; }
67	int Leaves() const { return (nodes / 2) + 1; }
68	double AvgDepth() const { return accumDepth / (double)Leaves();}; // TODO: computation wrong
69
70	void Reset()
71	{
72	nodes = 0;
73	splits = 0;
74	maxDepthNodes = 0;
75	maxDepth = 0;
76	minDepth = 99999;
77	polys = 0;
78	accumDepth = 0;
79	viewCells = 0;
80	pvs = 0;
81	contributingSamples = 0;
82	sampleContributions = 0;
83	}
84
85	void
86	Print(ostream &app) const;
87
88	friend ostream &operator<<(ostream &s, const BspTreeStatistics &stat) {
89	stat.Print(s);
90	return s;
91	}
92
93	};
94
95	/**
96	BspNode abstract class serving for interior and leaf node implementation
97	*/
98	class BspNode
99	{
100	friend BspTree;
101
102	public:
103	BspNode();
104	virtual ~BspNode();
105	BspNode(BspInterior *parent);
106
107	/** Determines whether this node is a leaf or not
108	@return true if leaf
109	*/
110	virtual bool IsLeaf() const = 0;
111
112	/** Determines whether this node is a root
113	@return true if root
114	*/
115	virtual bool IsRoot() const;
116
117	/** Returns parent node.
118	*/
119	BspInterior *GetParent();
120	/** Sets parent node.
121	*/
122	void SetParent(BspInterior *parent);
123
124	/** Returns pointer to polygons.
125	*/
126	PolygonContainer *GetPolygons();
127	/** Stores polygons in node or discards them according to storePolys.
128	*/
129	void ProcessPolygons(PolygonContainer *polys, const bool storePolys);
130
131	//int mViewCellIdx;
132	protected:
133
134	/// parent of this node
135	BspInterior *mParent;
136
137	/// store polygons created during BSP splits
138	PolygonContainer *mPolygons;
139	};
140
141	/** BSP interior node implementation
142	*/
143	class BspInterior : public BspNode
144	{
145	friend BspTree;
146	public:
147	/** Standard contructor taking split plane as argument.
148	*/
149	BspInterior(const Plane3 &plane);
150	/** @return false since it is an interior node
151	*/
152	bool IsLeaf() const;
153
154	BspNode *GetBack();
155	BspNode *GetFront();
156
157	Plane3 *GetPlane();
158
159	void ReplaceChildLink(BspNode oldChild, BspNode newChild);
160	void SetupChildLinks(BspNode b, BspNode f);
161
162	/** Splits polygons with respect to the split plane.
163	@param polys the polygons to be split. the polygons are consumed and
164	distributed to the containers frontPolys, backPolys, coincident.
165	@param frontPolys returns the polygons in the front of the split plane
166	@param backPolys returns the polygons in the back of the split plane
167	@param coincident returns the polygons coincident to the split plane
168	@param storePolys if the polygons should be stored in the node
169	@returns the number of splits
170	*/
171	int SplitPolygons(PolygonContainer &polys,
172	PolygonContainer &frontPolys,
173	PolygonContainer &backPolys,
174	PolygonContainer &coincident,
175	const bool storePolys = false);
176
177	/** Stores polygon in node or discards them according to storePolys.
178	@param polys the polygons
179	@param storePolys if the polygons should be stored or discarded
180	*/
181	void ProcessPolygon(Polygon3 **poly, const bool storePolys);
182
183	friend ostream &operator<<(ostream &s, const BspInterior &A)
184	{
185	return s << A.mPlane;
186	}
187
188	protected:
189
190	/// Splitting plane corresponding to this node
191	Plane3 mPlane;
192	/// back node
193	BspNode *mBack;
194	/// front node
195	BspNode *mFront;
196	};
197
198	/** BSP leaf node implementation.
199	*/
200	class BspLeaf : public BspNode
201	{
202	friend BspTree;
203
204	public:
205	BspLeaf();
206	BspLeaf(ViewCell *viewCell);
207	BspLeaf(BspInterior *parent);
208	BspLeaf(BspInterior parent, ViewCell viewCell);
209
210	/** @return true since it is an interior node
211	*/
212	bool IsLeaf() const;
213	/** Returns pointer from view cell.
214	*/
215	ViewCell *GetViewCell();
216	/** Sets pointer to view cell.
217	*/
218	void SetViewCell(ViewCell *viewCell);
219
220	/** Generates new view cell and adds rays to the PVS.
221	@param sampleContributions the number contributions of the sampels
222	@param contributingSampels the number of contributing rays
223	@param storeRays if ray set should be stored in view cell
224	*/
225	void BspLeaf::GenerateViewCell(const RayContainer &rays,
226	int &sampleContributions,
227	int &contributingSamples,
228	const bool storeRays = false);
229
230	protected:
231
232	/// if NULL this does not correspond to feasible viewcell
233	ViewCell *mViewCell;
234	};
235
236	/** Implementation of the view cell BSP tree.
237	*/
238	class BspTree
239	{
240	public:
241
242	/** Additional data which is passed down the BSP tree during traversal.
243	*/
244	struct BspTraversalData
245	{
246	/// the current node
247	BspNode *mNode;
248	/// polygonal data for splitting
249	PolygonContainer *mPolygons;
250	/// current depth
251	int mDepth;
252	/// the view cell associated with this subdivsion
253	ViewCell *mViewCell;
254	/// rays piercing this node
255	RayContainer *mRays;
256
257	BspTraversalData():
258	mNode(NULL),
259	mPolygons(NULL),
260	mDepth(0),
261	mViewCell(NULL),
262	mRays(NULL)
263	{}
264
265	BspTraversalData(BspNode *node,
266	PolygonContainer *polys,
267	const int depth,
268	ViewCell *viewCell,
269	RayContainer *rays):
270	mNode(node),
271	mPolygons(polys),
272	mDepth(depth),
273	mViewCell(viewCell),
274	mRays(rays)
275	{}
276	};
277
278	typedef std::stack<BspTraversalData> BspTraversalStack;
279
280	/** Default constructor creating an empty tree.
281	@param viewCell view cell corresponding to unbounded space
282	*/
283	BspTree(ViewCell *viewCell);
284
285	~BspTree();
286
287	const BspTreeStatistics &GetStatistics() const;
288
289	/** Constructs tree using the given list of view cells.
290	For this type of construction we filter all view cells down the
291	tree. If there is no polygon left, the last split plane
292	decides inside or outside of the viewcell. A pointer to the
293	appropriate view cell is stored within each leaf.
294	Many leafs can point to the same viewcell.
295	*/
296	void Construct(const ViewCellContainer &viewCells);
297
298	/** Constructs tree using the given list of objects.
299	@note the objects are not taken as view cells, but the view cells are
300	constructed from the subdivision: Each leaf is taken as one viewcell.
301	@param objects list of objects
302	*/
303	void Construct(const ObjectContainer &objects);
304
305	/** Constructs the tree from a given set of rays.
306	@param sampleRays the set of sample rays the construction is based on
307	@param viewCells if not NULL, new view cells are
308	created in the leafs and stored in the conatainer
309	*/
310	void Construct(const RayContainer &sampleRays);
311
312	/** Returns list of BSP leaves.
313	*/
314	void CollectLeaves(vector<BspLeaf *> &leaves);
315
316	/** Returns box which bounds the whole tree.
317	*/
318	AxisAlignedBox3 GetBoundingBox()const;
319
320	/** Returns root of BSP tree.
321	*/
322	BspNode *GetRoot() const;
323
324	/** Exports Bsp tree to file.
325	*/
326	bool Export(const string filename);
327
328	/** Collects the leaf view cells of the tree
329	@param viewCells returns the view cells
330	*/
331	void CollectViewCells(ViewCellContainer &viewCells) const;
332
333	/** A ray is cast possible intersecting the tree.
334	@param the ray that is cast.
335	@returns the number of intersections with objects stored in the tree.
336	*/
337	int CastRay(Ray &ray);
338
339	/** Merges view cells based on some criteria
340	E.g., empty view cells can pe purged, view cells which have
341	a very similar PVS can be merged to one larger view cell farther up
342	in the BSP tree.
343	@returns the number of merged view cells
344	*/
345	int MergeViewCells();
346
347	/** Set to true if new view cells shall be generated in each leaf.
348	*/
349	void SetGenerateViewCells(int generateViewCells);
350
351	/// bsp tree construction types
352	enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_RAYS};
353
354	/** Returns statistics.
355	*/
356	BspTreeStatistics &GetStat();
357
358	protected:
359
360	// --------------------------------------------------------------
361	// For sorting objects
362	// --------------------------------------------------------------
363	struct SortableEntry
364	{
365	enum {POLY_MIN, POLY_MAX};
366
367	int type;
368	float value;
369	Polygon3 *poly;
370	SortableEntry() {}
371	SortableEntry(const int t, const float v, Polygon3 *poly):
372	type(t), value(v), poly(poly) {}
373
374	bool operator<(const SortableEntry &b) const
375	{
376	return value < b.value;
377	}
378	};
379
380	/** Merges view cells of leafs.
381	*/
382	void MergeLeafs(BspLeaf front, BspLeaf back) const;
383
384	/** Evaluates tree stats in the BSP tree leafs.
385	*/
386	void EvaluateLeafStats(const BspTraversalData &data);
387
388	/** Subdivides node with respect to the traversal data.
389	@param tStack current traversal stack
390	@param tData traversal data also holding node to be subdivided
391	@returns new root of the subtree
392	*/
393	BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData);
394
395	/** Constructs the tree from the given list of polygons and rays.
396	@param polys stores set of polygons on which subdivision may be based
397	@param rays storesset of rays on which subdivision may be based
398	*/
399	void Construct(PolygonContainer polys, RayContainer rays);
400
401	/** Selects the best possible splitting plane.
402	@param leaf the leaf to be split
403	@param polys the polygon list on which the split decition is based
404	@param rays ray container on which selection may be based
405	@note the polygons can be reordered in the process
406	@returns the split plane
407	*/
408	Plane3 SelectPlane(BspLeaf *leaf,
409	PolygonContainer &polys,
410	const RayContainer &ray);
411
412	/** Evaluates the contribution of the candidate split plane.
413
414	@param canditatePlane the candidate split plane
415	@param polys the polygons the split can be based on
416	@param rays the rays the split can be based on
417	@returns the cost of the candidate split plane
418	*/
419	float SplitPlaneCost(const Plane3 &candidatePlane,
420	const PolygonContainer &polys,
421	const RayContainer &rays) const;
422
423	/** Strategies where the effect of the split plane is tested
424	on all input rays.
425	@returns the cost of the candidate split plane
426	*/
427	float SplitPlaneCost(const Plane3 &candidatePlane,
428	const PolygonContainer &polys) const;
429
430	/** Strategies where the effect of the split plane is tested
431	on all input polygons.
432	@returns the cost of the candidate split plane
433	*/
434	float SplitPlaneCost(const Plane3 &candidatePlane,
435	const RayContainer &polys) const;
436
437	/** Filters next view cell down the tree and inserts it into the appropriate leaves
438	(i.e., possibly more than one leaf).
439	*/
440	void InsertViewCell(ViewCell *viewCell);
441	/** Inserts polygons down the tree. The polygons are filtered until a leaf is reached,
442	then further subdivided.
443	*/
444	void InsertPolygons(PolygonContainer *polys);
445
446	/** Subdivide leaf.
447	@param leaf the leaf to be subdivided
448
449	@param polys the polygons to be split
450	@param frontPolys returns the polygons in front of the split plane
451	@param backPolys returns the polygons in the back of the split plane
452
453	@param rays the polygons to be filtered
454	@param frontRays returns the polygons in front of the split plane
455	@param backRays returns the polygons in the back of the split plane
456
457	@returns the root of the subdivision
458	*/
459	BspInterior SubdivideNode(BspLeaf leaf,
460	PolygonContainer &polys,
461	PolygonContainer &frontPolys,
462	PolygonContainer &backPolys,
463	PolygonContainer &coincident,
464	RayContainer &rays,
465	RayContainer &frontRays,
466	RayContainer &backRays);
467
468	/** Filters polygons down the tree.
469	@param node the current BSP node
470	@param polys the polygons to be filtered
471	@param frontPolys returns the polygons in front of the split plane
472	@param backPolys returns the polygons in the back of the split plane
473	*/
474	void FilterPolygons(BspInterior *node,
475	PolygonContainer *polys,
476	PolygonContainer *frontPolys,
477	PolygonContainer *backPolys);
478
479	/** Selects the split plane in order to construct a tree with
480	certain characteristics (e.g., balanced tree, least splits,
481	2.5d aligned)
482	@param polygons container of polygons
483	@param rays bundle of rays on which the split can be based
484	@param maxTests the maximal number of candidate tests
485	*/
486	Plane3 SelectPlaneHeuristics(PolygonContainer &polys,
487	const RayContainer &rays,
488	const int maxTests);
489
490	/** Extracts the meshes of the objects and adds them to polygons.
491	Adds object aabb to the aabb of the tree.
492	@param maxPolys the maximal number of objects to be stored as polygons
493	@returns the number of polygons
494	*/
495	int AddToPolygonSoup(const ObjectContainer &objects,
496	PolygonContainer &polys,
497	int maxObjects = 0);
498
499	/** Extracts the meshes of the view cells and and adds them to polygons.
500	Adds view cell aabb to the aabb of the tree.
501	@param maxPolys the maximal number of objects to be stored as polygons
502	@returns the number of polygons
503	*/
504	int AddToPolygonSoup(const ViewCellContainer &viewCells,
505	PolygonContainer &polys,
506	int maxObjects = 0);
507
508	/** Extract polygons of this mesh and add to polygon container.
509	@param mesh the mesh that drives the polygon construction
510	@param parent the parent intersectable this polygon is constructed from
511	@returns number of polygons
512	*/
513	int AddMeshToPolygons(Mesh mesh, PolygonContainer &polys, MeshInstance parent);
514
515	/** returns next candidate index and reorders polygons so no candidate is chosen two times
516	@param the current candidate index
517	@param max the range of candidates
518	*/
519	int GetNextCandidateIdx(int currentIdx, PolygonContainer &polys);
520
521	/** Helper function which extracts a view cell on the front and the back
522	of the split plane.
523	@param backViewCell returns view cell on the back of the split plane
524	@param frontViewCell returns a view cell on the front of the split plane
525	@param coincident container of polygons coincident to the split plane
526	@param splitPlane the split plane which decides about back and front
527	@param extractBack if a back view cell is extracted
528	@param extractFront if a front view cell is extracted
529	*/
530	void ExtractViewCells(ViewCell **backViewCell,
531	ViewCell **frontViewCell,
532	const PolygonContainer &coincident,
533	const Plane3 splitPlane,
534	const bool extractBack,
535	const bool extractFront) const;
536
537	/** Computes best cost ratio for the suface area heuristics for axis aligned
538	splits. This heuristics minimizes the cost for ray traversal.
539	@param polys the polygons guiding the ratio computation
540	@param box the bounding box of the leaf
541	@param axis the current split axis
542	@param position returns the split position
543	@param objectsBack the number of objects in the back of the split plane
544	@param objectsFront the number of objects in the front of the split plane
545	*/
546	float BestCostRatio(const PolygonContainer &polys,
547	const AxisAlignedBox3 &box,
548	const int axis,
549	float &position,
550	int &objectsBack,
551	int &objectsFront) const;
552
553	/** Sorts split candidates for surface area heuristics for axis aligned splits.
554	@param polys the input for choosing split candidates
555	@param axis the current split axis
556	@param splitCandidates returns sorted list of split candidates
557	*/
558	void SortSplitCandidates(const PolygonContainer &polys,
559	const int axis,
560	vector<SortableEntry> &splitCandidates) const;
561
562	/** Selects an axis aligned split plane.
563	Returns true if split is valied
564	*/
565	bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;
566
567	/** Bounds ray and returns minT and maxT.
568	@returns true if ray hits BSP tree bounding box
569	*/
570	bool BoundRay(const Ray &ray, float &minT, float &maxT) const;
571
572	/** Subdivides the rays into front and back rays according to the split plane.
573
574	@param plane the split plane
575	@param rays contains the rays to be split. The rays are
576	distributed into front and back rays.
577	@param frontRays returns rays on the front side of the plane
578	@param backRays returns rays on the back side of the plane
579
580	@returns the number of splits
581	*/
582	int SplitRays(const Plane3 &plane,
583	RayContainer &rays,
584	RayContainer &frontRays,
585	RayContainer &backRays);
586
587	/// Pointer to the root of the tree
588	BspNode *mRoot;
589
590	/// Pointer to the root cell of the viewspace
591	// ViewCell *mRootCell;
592
593	BspTreeStatistics mStat;
594
595	/// Strategies for choosing next split plane.
596	enum {NO_STRATEGY = 0,
597	RANDOM_POLYGON = 1,
598	AXIS_ALIGNED = 2,
599	LEAST_SPLITS = 4,
600	BALANCED_POLYS = 8,
601	BALANCED_VIEW_CELLS = 16,
602	LARGEST_POLY_AREA = 32,
603	VERTICAL_AXIS = 64,
604	BLOCKED_RAYS = 128,
605	LEAST_RAY_SPLITS = 256,
606	BALANCED_RAYS = 512
607	};
608
609	/// box around the whole view domain
610	AxisAlignedBox3 mBox;
611
612	/// view cell corresponding to unbounded space
613	ViewCell *mRootCell;
614
615	/// should view cells be stored or generated in the leaves?
616	bool mGenerateViewCells;
617
618	/// if rays should be stored that are piercing this view cell
619	bool mStorePiercingRays;
620
621	public:
622	/// Parses the environment and stores the global BSP tree parameters
623	static void ParseEnvironment();
624
625	/// maximal number of polygons before subdivision termination
626	static int sTermMaxPolygons;
627	/// maximal number of rays before subdivision termination
628	static int sTermMaxRays;
629	/// maximal possible depth
630	static int sTermMaxDepth;
631	/// strategy to get the best split plane
632	static int sSplitPlaneStrategy;
633	/// number of candidates evaluated for the next split plane
634	static int sMaxCandidates;
635	/// BSP tree construction method
636	static int sConstructionMethod;
637	/// maximal number of polygons where we do axis aligned splits
638	static int sTermMaxPolysForAxisAligned;
639
640	/// axis aligned split criteria
641	static float sCt_div_ci;
642	static float sSplitBorder;
643	static float sMaxCostRatio;
644
645	// factors guiding the split plane heuristics
646	static float sLeastSplitsFactor;
647	static float sBalancedPolysFactor;
648	static float sBalancedViewCellsFactor;
649	static float sVerticalSplitsFactor;
650	static float sLargestPolyAreaFactor;
651	static float sBlockedRaysFactor;
652	static float sLeastRaySplitsFactor;
653	static float sBalancedRaysFactor;
654
655	/// if polygons should be stored in the tree
656	static bool sStoreSplitPolys;
657
658	private:
659	/** Evaluates split plane classification with respect to the plane's
660	contribution for a balanced tree.
661	*/
662	static float sLeastPolySplitsTable[4];
663	/** Evaluates split plane classification with respect to the plane's
664	contribution for a minimum number splits in the tree.
665	*/
666	static float sBalancedPolysTable[4];
667	/** Evaluates split plane classification with respect to the plane's
668	contribution for a minimum number of ray splits.
669	*/
670	static float sLeastRaySplitsTable[5];
671	/** Evaluates split plane classification with respect to the plane's
672	contribution for balanced rays.
673	*/
674	static float sBalancedRaysTable[5];
675
676	};
677
678	//}; // GtpVisibilityPreprocessor
679
680	#endif

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

Download in other formats: