Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h @ 1016

Revision 1016, 24.7 KB checked in by mattausch, 18 years ago (diff)
worked on view space / object space partition

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

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

Download in other formats: