Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h @ 611

Revision 611, 20.5 KB checked in by mattausch, 18 years ago (diff)

Line
1	#ifndef _VspBspTree_H__
2	#define _VspBspTree_H__
3
4	#include "Mesh.h"
5	#include "Containers.h"
6	#include "Polygon3.h"
7	#include <stack>
8	#include "Statistics.h"
9	#include "VssRay.h"
10	#include "RayInfo.h"
11	#include "ViewCellBsp.h"
12
13	class ViewCell;
14	//class BspViewCell;
15	class Plane3;
16	class VspBspTree;
17	class BspInterior;
18	class BspNode;
19	class AxisAlignedBox3;
20	class Ray;
21	class ViewCellsStatistics;
22	class ViewCellsManager;
23	class MergeCandidate;
24	class Beam;
25	class ViewCellsTree;
26
27
28	struct BspRay;
29
30	#define OCTREE_HACK 0
31	/**
32	This is a view space partitioning specialised BSPtree.
33	There are no polygon splits, but we split the sample rays.
34	The candidates for the next split plane are evaluated only
35	by checking the sampled visibility information.
36	The polygons are employed merely as candidates for the next split planes.
37	*/
38	class VspBspTree
39	{
40	friend class ViewCellsParseHandlers;
41	friend class VspBspViewCellsManager;
42	public:
43
44	/** Additional data which is passed down the BSP tree during traversal.
45	*/
46	struct VspBspTraversalData
47	{
48	/// the current node
49	BspNode *mNode;
50	/// polygonal data for splitting
51	PolygonContainer *mPolygons;
52	/// current depth
53	int mDepth;
54	/// rays piercing this node
55	RayInfoContainer *mRays;
56	/// the probability that this node contains view point
57	float mProbability;
58	/// geometry of node as induced by planes
59	BspNodeGeometry *mGeometry;
60	/// pvs size
61	int mPvs;
62	/// how often this branch has missed the max-cost ratio
63	int mMaxCostMisses;
64	/// if this node is a kd-node (i.e., boundaries are axis aligned
65	bool mIsKdNode;
66	#if OCTREE_HACK // OCTREE HACK
67	int mAxis;
68	#endif
69	/// bounding box of current view space.
70	///AxisAlignedBox3 mBbox;
71
72	/** Returns average ray contribution.
73	*/
74	float GetAvgRayContribution() const
75	{
76	return (float)mPvs / ((float)mRays->size() + Limits::Small);
77	}
78
79
80	VspBspTraversalData():
81	mNode(NULL),
82	mPolygons(NULL),
83	mDepth(0),
84	mRays(NULL),
85	mPvs(0),
86	mProbability(0.0),
87	mGeometry(NULL),
88	mMaxCostMisses(0),
89	mIsKdNode(false)
90	{}
91
92	VspBspTraversalData(BspNode *node,
93	PolygonContainer *polys,
94	const int depth,
95	RayInfoContainer *rays,
96	const int pvs,
97	const float p,
98	BspNodeGeometry *geom):
99	mNode(node),
100	mPolygons(polys),
101	mDepth(depth),
102	mRays(rays),
103	mPvs(pvs),
104	mProbability(p),
105	mGeometry(geom),
106	mMaxCostMisses(0),
107	mIsKdNode(false)
108	{}
109
110	VspBspTraversalData(PolygonContainer *polys,
111	const int depth,
112	RayInfoContainer *rays,
113	BspNodeGeometry *geom):
114	mNode(NULL),
115	mPolygons(polys),
116	mDepth(depth),
117	mRays(rays),
118	mPvs(0),
119	mProbability(0),
120	mGeometry(geom),
121	mMaxCostMisses(0),
122	mIsKdNode(false)
123	{}
124
125	/** Returns cost of the traversal data.
126	*/
127	float GetCost() const
128	{
129	#if 0
130	return mPvs * mProbability;
131	#endif
132	#if 1
133	return (float) (-mDepth); // for regular grid
134	#endif
135	#if 0
136	return (float)(mPvs * (int)mRays->size());
137	#endif
138	#if 0
139	return (float)mPvs;
140	#endif
141	#if 0
142	return mProbabiliy * (float)mRays->size();
143	#endif
144	}
145
146	// deletes contents and sets them to NULL
147	void Clear()
148	{
149	DEL_PTR(mPolygons);
150	DEL_PTR(mRays);
151	DEL_PTR(mGeometry);
152	}
153
154	friend bool operator<(const VspBspTraversalData &a, const VspBspTraversalData &b)
155	{
156	return a.GetCost() < b.GetCost();
157	}
158	};
159
160	typedef std::priority_queue<VspBspTraversalData> VspBspTraversalQueue;
161	//typedef std::stack<VspBspTraversalData> VspBspTraversalQueue;
162
163	/** Default constructor creating an empty tree.
164	*/
165	VspBspTree();
166
167	/** Default destructor.
168	*/
169	~VspBspTree();
170
171	/** Returns BSP Tree statistics.
172	*/
173	const BspTreeStatistics &GetStatistics() const;
174
175
176	/** Constructs the tree from a given set of rays.
177	@param sampleRays the set of sample rays the construction is based on
178	@param viewCells if not NULL, new view cells are
179	created in the leafs and stored in the container
180	*/
181	void Construct(const VssRayContainer &sampleRays,
182	AxisAlignedBox3 *forcedBoundingBox);
183
184	/** Returns list of BSP leaves with pvs smaller than
185	a certain threshold.
186	@param onlyUnmailed if only the unmailed leaves should be considered
187	@param maxPvs the maximal pvs (-1 means unlimited)
188	*/
189	void CollectLeaves(vector<BspLeaf *> &leaves,
190	const bool onlyUnmailed = false,
191	const int maxPvs = -1) const;
192
193	/** Returns box which bounds the whole tree.
194	*/
195	AxisAlignedBox3 GetBoundingBox()const;
196
197	/** Returns root of BSP tree.
198	*/
199	BspNode *GetRoot() const;
200
201	/** Collects the leaf view cells of the tree
202	@param viewCells returns the view cells
203	*/
204	void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
205
206	/** A ray is cast possible intersecting the tree.
207	@param the ray that is cast.
208	@returns the number of intersections with objects stored in the tree.
209	*/
210	int CastRay(Ray &ray);
211
212	/// bsp tree construction types
213	enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};
214
215	/** finds neighbouring leaves of this tree node.
216	*/
217	int FindNeighbors(BspNode *n,
218	vector<BspLeaf *> &neighbors,
219	const bool onlyUnmailed) const;
220
221	/** Constructs geometry associated with the half space intersections
222	leading to this node.
223	*/
224	void ConstructGeometry(BspNode *n, BspNodeGeometry &geom) const;
225
226	/** Construct geometry of view cell.
227	*/
228	void ConstructGeometry(ViewCell *vc, BspNodeGeometry &geom) const;
229
230	/** Returns random leaf of BSP tree.
231	@param halfspace defines the halfspace from which the leaf is taken.
232	*/
233	BspLeaf *GetRandomLeaf(const Plane3 &halfspace);
234
235	/** Returns random leaf of BSP tree.
236	@param onlyUnmailed if only unmailed leaves should be returned.
237	*/
238	BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
239
240	/** Returns epsilon of this tree.
241	*/
242	float GetEpsilon() const;
243
244	/** Casts line segment into the tree.
245	@param origin the origin of the line segment
246	@param termination the end point of the line segment
247	@returns view cells intersecting the line segment.
248	*/
249	int CastLineSegment(const Vector3 &origin,
250	const Vector3 &termination,
251	ViewCellContainer &viewcells);
252
253
254	/** Sets pointer to view cells manager.
255	*/
256	void SetViewCellsManager(ViewCellsManager *vcm);
257
258	/** Returns distance from node 1 to node 2.
259	*/
260	int TreeDistance(BspNode n1, BspNode n2) const;
261
262	/** Collapses the tree with respect to the view cell partition.
263	@returns number of collapsed nodes
264	*/
265	int CollapseTree();
266
267	/** Returns view cell the current point is located in.
268	*/
269	ViewCell *GetViewCell(const Vector3 &point);
270
271
272	/** Returns true if this view point is in a valid view space,
273	false otherwise.
274	*/
275	bool ViewPointValid(const Vector3 &viewPoint) const;
276
277	/** Returns view cell corresponding to
278	the invalid view space.
279	*/
280	BspViewCell *GetOutOfBoundsCell();
281
282	/** Writes tree to output stream
283	*/
284	bool Export(ofstream &stream);
285
286	/** Casts beam, i.e. a 5D frustum of rays, into tree.
287	Tests conservative using the bounding box of the nodes.
288	@returns number of view cells it intersected
289	*/
290	int CastBeam(Beam &beam);
291
292	void CollectViewCells(BspNode *root,
293	bool onlyValid,
294	ViewCellContainer &viewCells,
295	bool onlyUnmailed = false) const;
296
297
298	int FindApproximateNeighbors(BspNode *n,
299	vector<BspLeaf *> &neighbors,
300	const bool onlyUnmailed) const;
301
302	/** Checks if tree validity-flags are right
303	with respect to view cell valitiy.
304	If not, marks subtree as invalid.
305	*/
306	void ValidateTree();
307
308	/** Invalid view cells are added to the unbounded space
309	*/
310	void CollapseViewCells();
311
312	ViewCellsTree *mViewCellsTree;
313	protected:
314
315	// --------------------------------------------------------------
316	// For sorting objects
317	// --------------------------------------------------------------
318	struct SortableEntry
319	{
320	enum EType
321	{
322	ERayMin,
323	ERayMax
324	};
325
326	int type;
327	float value;
328	VssRay *ray;
329
330	SortableEntry() {}
331	SortableEntry(const int t, const float v, VssRay *r):type(t),
332	value(v), ray(r)
333	{
334	}
335
336	friend bool operator<(const SortableEntry &a, const SortableEntry &b)
337	{
338	return a.value < b.value;
339	}
340	};
341
342	/** faster evaluation of split plane cost for kd axis aligned cells.
343	*/
344	float EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
345	const AxisAlignedBox3 &box,
346	const int axis,
347	const float &position,
348	float &pFront,
349	float &pBack) const;
350
351	/** Returns view cell corresponding to
352	the invalid view space. If it does not exist, it is created.
353	*/
354	BspViewCell *GetOrCreateOutOfBoundsCell();
355
356	/** Collapses the tree with respect to the view cell partition,
357	i.e. leaves having the same view cell are collapsed.
358	@param node the root of the subtree to be collapsed
359	@param collapsed returns the number of collapsed nodes
360	@returns node of type leaf if the node could be collapsed,
361	this node otherwise
362	*/
363	BspNode CollapseTree(BspNode node, int &collapsed);
364
365	/** Helper function revalidating the view cell leaf list after merge.
366	*/
367	void RepairViewCellsLeafLists();
368
369	/** Evaluates tree stats in the BSP tree leafs.
370	*/
371	void EvaluateLeafStats(const VspBspTraversalData &data);
372
373	/** Subdivides node with respect to the traversal data.
374	@param tStack current traversal stack
375	@param tData traversal data also holding node to be subdivided
376	@returns new root of the subtree
377	*/
378	BspNode *Subdivide(VspBspTraversalQueue &tStack,
379	VspBspTraversalData &tData);
380
381	/** Constructs the tree from the given traversal data.
382	@param polys stores set of polygons on which subdivision may be based
383	@param rays storesset of rays on which subdivision may be based
384	*/
385	void Construct(const PolygonContainer &polys, RayInfoContainer *rays);
386
387	/** Selects the best possible splitting plane.
388	@param plane returns the split plane
389	@param leaf the leaf to be split
390	@param polys the polygon list on which the split decition is based
391	@param rays ray container on which selection may be based
392	@note the polygons can be reordered in the process
393	@returns true if the cost of the split is under maxCostRatio
394
395	*/
396	bool SelectPlane(Plane3 &plane,
397	BspLeaf *leaf,
398	VspBspTraversalData &data,
399	VspBspTraversalData &frontData,
400	VspBspTraversalData &backData);
401
402	/** Strategies where the effect of the split plane is tested
403	on all input rays.
404
405	@returns the cost of the candidate split plane
406	*/
407	float EvalSplitPlaneCost(const Plane3 &candidatePlane,
408	const VspBspTraversalData &data,
409	BspNodeGeometry &geomFront,
410	BspNodeGeometry &geomBack,
411	float &pFront,
412	float &pBack) const;
413
414	/** Subdivide leaf.
415	@param leaf the leaf to be subdivided
416
417	@param polys the polygons to be split
418	@param frontPolys returns the polygons in front of the split plane
419	@param backPolys returns the polygons in the back of the split plane
420
421	@param rays the polygons to be filtered
422	@param frontRays returns the polygons in front of the split plane
423	@param backRays returns the polygons in the back of the split plane
424
425	@returns the root of the subdivision
426	*/
427
428	BspNode *SubdivideNode(VspBspTraversalData &tData,
429	VspBspTraversalData &frontData,
430	VspBspTraversalData &backData,
431	PolygonContainer &coincident);
432
433	/** Extracts the meshes of the objects and adds them to polygons.
434	Adds object aabb to the aabb of the tree.
435	@param maxPolys the maximal number of objects to be stored as polygons
436	@returns the number of polygons
437	*/
438	int AddToPolygonSoup(const ObjectContainer &objects,
439	PolygonContainer &polys,
440	int maxObjects = 0);
441
442	/** Extracts the meshes of the view cells and and adds them to polygons.
443	Adds view cell aabb to the aabb of the tree.
444	@param maxPolys the maximal number of objects to be stored as polygons
445	@returns the number of polygons
446	*/
447	int AddToPolygonSoup(const ViewCellContainer &viewCells,
448	PolygonContainer &polys,
449	int maxObjects = 0);
450
451	/** Extract polygons of this mesh and add to polygon container.
452	@param mesh the mesh that drives the polygon construction
453	@param parent the parent intersectable this polygon is constructed from
454	@returns number of polygons
455	*/
456	int AddMeshToPolygons(Mesh mesh, PolygonContainer &polys, MeshInstance parent);
457
458	/** Selects an axis aligned for the next split.
459	@returns cost for this split
460	*/
461	float SelectAxisAlignedPlane(Plane3 &plane,
462	const VspBspTraversalData &tData,
463	int &axis,
464	BspNodeGeometry **frontGeom,
465	BspNodeGeometry **backGeom,
466	float &pFront,
467	float &pBack,
468	const bool useKdSplit);
469
470	/** Sorts split candidates for surface area heuristics for axis aligned splits.
471	@param polys the input for choosing split candidates
472	@param axis the current split axis
473	@param splitCandidates returns sorted list of split candidates
474	*/
475	void SortSplitCandidates(const RayInfoContainer &rays, const int axis);
476
477	/** Computes best cost for axis aligned planes.
478	*/
479	float BestCostRatioHeuristics(const RayInfoContainer &rays,
480	const AxisAlignedBox3 &box,
481	const int pvsSize,
482	const int &axis,
483	float &position);
484
485	/** Selects an axis aligned split plane.
486	@Returns true if split is valied
487	*/
488	bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;
489
490	/** Subdivides the rays into front and back rays according to the split plane.
491
492	@param plane the split plane
493	@param rays contains the rays to be split. The rays are
494	distributed into front and back rays.
495	@param frontRays returns rays on the front side of the plane
496	@param backRays returns rays on the back side of the plane
497
498	@returns the number of splits
499	*/
500	int SplitRays(const Plane3 &plane,
501	RayInfoContainer &rays,
502	RayInfoContainer &frontRays,
503	RayInfoContainer &backRays);
504
505
506	/** Extracts the split planes representing the space bounded by node n.
507	*/
508	void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const;
509
510	/** Adds the object to the pvs of the front and back leaf with a given classification.
511
512	@param obj the object to be added
513	@param cf the ray classification regarding the split plane
514	@param frontPvs returns the PVS of the front partition
515	@param backPvs returns the PVS of the back partition
516
517	*/
518	void AddObjToPvs(Intersectable *obj,
519	const int cf,
520	int &frontPvs,
521	int &backPvs,
522	int &totalPvs) const;
523
524	/** Computes PVS size induced by the rays.
525	*/
526	int ComputePvsSize(const RayInfoContainer &rays) const;
527
528	/** Returns true if tree can be terminated.
529	*/
530	inline bool TerminationCriteriaMet(const VspBspTraversalData &data) const;
531
532	/** Computes accumulated ray lenght of this rays.
533	*/
534	float AccumulatedRayLength(const RayInfoContainer &rays) const;
535
536	/** Splits polygons with respect to the split plane.
537
538	@param plane the split plane
539	@param polys the polygons to be split. the polygons are consumed and
540	distributed to the containers frontPolys, backPolys, coincident.
541	@param frontPolys returns the polygons in the front of the split plane
542	@param backPolys returns the polygons in the back of the split plane
543	@param coincident returns the polygons coincident to the split plane
544
545	@returns the number of splits
546	*/
547	int SplitPolygons(const Plane3 &plane,
548	PolygonContainer &polys,
549	PolygonContainer &frontPolys,
550	PolygonContainer &backPolys,
551	PolygonContainer &coincident) const;
552
553	/** Adds ray sample contributions to the PVS.
554	@param sampleContributions the number contributions of the samples
555	@param contributingSampels the number of contributing rays
556
557	*/
558	void AddToPvs(BspLeaf *leaf,
559	const RayInfoContainer &rays,
560	float &sampleContributions,
561	int &contributingSamples);
562
563
564
565
566
567
568	/** Take 3 ray endpoints, where two are minimum and one a maximum
569	point or the other way round.
570	*/
571	Plane3 ChooseCandidatePlane(const RayInfoContainer &rays) const;
572
573	/** Take plane normal as plane normal and the midpoint of the ray.
574	PROBLEM: does not resemble any point where visibility is
575	likely to change
576	*/
577	Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const;
578
579	/** Fit the plane between the two lines so that the plane
580	has equal shortest distance to both lines.
581	*/
582	Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
583
584	/** Collects candidates for merging.
585	@param leaves the leaves to be merged
586	@returns number of leaves in queue
587	*/
588	int CollectMergeCandidates(const vector<BspLeaf *> leaves, vector<MergeCandidate> &candidates);
589
590	/** Collects candidates for the merge in the merge queue.
591	@returns number of leaves in queue
592	*/
593	int CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
594
595
596
597	/** Propagates valid flag up the tree.
598	*/
599	void PropagateUpValidity(BspNode *node);
600
601	/** Writes the node to disk
602	@note: should be implemented as visitor
603	*/
604	void ExportNode(BspNode *node, ofstream &stream);
605
606	/** Returns estimated memory usage of tree.
607	*/
608	//float GetMemUsage(const VspBspTraversalQueue &tstack) const;
609	float GetMemUsage() const;
610
611
612
613	/// Pointer to the root of the tree
614	BspNode *mRoot;
615
616	BspTreeStatistics mBspStats;
617
618	/// Strategies for choosing next split plane.
619	enum {NO_STRATEGY = 0,
620	RANDOM_POLYGON = 1,
621	AXIS_ALIGNED = 2,
622	LEAST_RAY_SPLITS = 256,
623	BALANCED_RAYS = 512,
624	PVS = 1024
625	};
626
627	/// box around the whole view domain
628	AxisAlignedBox3 mBox;
629
630	/// minimal number of rays before subdivision termination
631	int mTermMinRays;
632	/// maximal possible depth
633	int mTermMaxDepth;
634	/// mininum probability
635	float mTermMinProbability;
636	/// mininum PVS
637	int mTermMinPvs;
638	/// maximal contribution per ray
639	float mTermMaxRayContribution;
640	/// minimal accumulated ray length
641	float mTermMinAccRayLength;
642
643	//HACK
644	int mTermMinPolygons;
645
646	//-- termination criteria for axis aligned split
647
648	/// minimal number of rays for axis aligned split
649	int mTermMinRaysForAxisAligned;
650	// max ray contribution
651	float mTermMaxRayContriForAxisAligned;
652
653	/// strategy to get the best split plane
654	int mSplitPlaneStrategy;
655	/// number of candidates evaluated for the next split plane
656	int mMaxPolyCandidates;
657	/// number of candidates for split planes evaluated using the rays
658	int mMaxRayCandidates;
659	/// balancing factor for PVS criterium
660	float mCtDivCi;
661
662	//-- axis aligned split criteria
663	float mAxisAlignedCtDivCi;
664	/// spezifies the split border of the axis aligned split
665	float mAxisAlignedSplitBorder;
666
667	/// maximal acceptable cost ratio
668	float mTermMaxCostRatio;
669	/// tolerance value indicating how often the max cost ratio can be failed
670	int mTermMissTolerance;
671
672	//-- factors guiding the split plane heuristics
673	float mLeastRaySplitsFactor;
674	float mBalancedRaysFactor;
675	float mPvsFactor;
676
677	/// if area or volume should be used for PVS heuristics
678	bool mUseAreaForPvs;
679	/// tolerance for polygon split
680	float mEpsilon;
681	/// maximal number of test rays used to evaluate candidate split plane
682	int mMaxTests;
683	/// normalizes different bsp split plane criteria
684	float mCostNormalizer;
685	/// maximal number of view cells
686	int mMaxViewCells;
687
688	ofstream mSubdivisionStats;
689
690	// if rays should be stored in leaves
691	bool mStoreRays;
692
693	/// if only driving axis should be used for split
694	bool mOnlyDrivingAxis;
695
696	ViewCellsManager *mViewCellsManager;
697
698	vector<SortableEntry> *mSplitCandidates;
699
700
701	float mRenderCostWeight;
702	/// View cell corresponding to the space outside the valid view space
703	BspViewCell *mOutOfBoundsCell;
704
705	/// maximal tree memory
706	float mMaxMemory;
707	/// the tree is out of memory
708	bool mOutOfMemory;
709
710	float mTotalCost;
711	int mTotalPvsSize;
712
713	//int mSplits;
714
715	ofstream mSubdivsionStats;
716
717	bool mUseRandomAxis;
718
719	bool mUsePolygonSplitIfAvailable;
720
721	int mTimeStamp;
722
723	private:
724
725
726	static const float sLeastRaySplitsTable[5];
727	/** Evaluates split plane classification with respect to the plane's
728	contribution for balanced rays.
729	*/
730	static const float sBalancedRaysTable[5];
731
732	/// Generates unique ids for PVS criterium
733	static void GenerateUniqueIdsForPvs();
734
735	//-- unique ids for PVS criterium
736	static int sFrontId;
737	static int sBackId;
738	static int sFrontAndBackId;
739	};
740
741
742
743
744	#endif

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

Download in other formats: