Context Navigation

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

Revision 882, 23.7 KB checked in by mattausch, 19 years ago (diff)
added new active view cell concept

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

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

Download in other formats: