Context Navigation

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

Revision 1006, 24.7 KB checked in by mattausch, 18 years ago (diff)
started viewspace-objectspace subdivision removed memory leaks

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 cost 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	// cost of applying 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	#endif
186	#if 0
187	return (float) (-mDepth); // for kd tree
188	#endif
189	}
190
191	friend bool operator<(const VspBspSplitCandidate &a, const VspBspSplitCandidate &b)
192	{
193	return a.GetCost() < b.GetCost();
194	}
195	};
196
197	typedef std::priority_queue<VspBspSplitCandidate> VspBspSplitQueue;
198
199	/** Default constructor creating an empty tree.
200	*/
201	VspBspTree();
202
203	/** Default destructor.
204	*/
205	~VspBspTree();
206
207	/** Returns BSP Tree statistics.
208	*/
209	const BspTreeStatistics &GetStatistics() const;
210
211
212	/** Constructs the tree from a given set of rays.
213	@param sampleRays the set of sample rays the construction is based on
214	@param viewCells if not NULL, new view cells are
215	created in the leafs and stored in the container
216	*/
217	void Construct(const VssRayContainer &sampleRays,
218	AxisAlignedBox3 *forcedBoundingBox);
219
220	/** Returns list of BSP leaves with pvs smaller than
221	a certain threshold.
222	@param onlyUnmailed if only the unmailed leaves should be considered
223	@param maxPvs the maximal pvs (-1 means unlimited)
224	*/
225	void CollectLeaves(vector<BspLeaf *> &leaves,
226	const bool onlyUnmailed = false,
227	const int maxPvs = -1) const;
228
229	/** Returns box which bounds the whole tree.
230	*/
231	AxisAlignedBox3 GetBoundingBox()const;
232
233	/** Returns root of BSP tree.
234	*/
235	BspNode *GetRoot() const;
236
237	/** Collects the leaf view cells of the tree
238	@param viewCells returns the view cells
239	*/
240	void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
241
242	/** A ray is cast possible intersecting the tree.
243	@param the ray that is cast.
244	@returns the number of intersections with objects stored in the tree.
245	*/
246	int CastRay(Ray &ray);
247
248	/// bsp tree construction types
249	enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};
250
251	/** finds neighbouring leaves of this tree node.
252	*/
253	int FindNeighbors(BspNode *n,
254	vector<BspLeaf *> &neighbors,
255	const bool onlyUnmailed) const;
256
257	/** Constructs geometry associated with the half space intersections
258	leading to this node.
259	*/
260	void ConstructGeometry(BspNode *n, BspNodeGeometry &geom) const;
261
262	/** Construct geometry of view cell.
263	*/
264	void ConstructGeometry(ViewCell *vc, BspNodeGeometry &geom) const;
265
266	/** Returns random leaf of BSP tree.
267	@param halfspace defines the halfspace from which the leaf is taken.
268	*/
269	BspLeaf *GetRandomLeaf(const Plane3 &halfspace);
270
271	/** Returns random leaf of BSP tree.
272	@param onlyUnmailed if only unmailed leaves should be returned.
273	*/
274	BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
275
276	/** Returns epsilon of this tree.
277	*/
278	float GetEpsilon() const;
279
280	/** Casts line segment into the tree.
281	@param origin the origin of the line segment
282	@param termination the end point of the line segment
283	@returns view cells intersecting the line segment.
284	*/
285	int CastLineSegment(const Vector3 &origin,
286	const Vector3 &termination,
287	ViewCellContainer &viewcells);
288
289
290	/** Sets pointer to view cells manager.
291	*/
292	void SetViewCellsManager(ViewCellsManager *vcm);
293
294	/** Returns distance from node 1 to node 2.
295	*/
296	int TreeDistance(BspNode n1, BspNode n2) const;
297
298	/** Collapses the tree with respect to the view cell partition.
299	@returns number of collapsed nodes
300	*/
301	int CollapseTree();
302
303	/** Returns view cell the current point is located in.
304	@param point the current view point
305	@param active if currently active view cells should be returned or
306	elementary view cell
307	*/
308	ViewCell *GetViewCell(const Vector3 &point, const bool active = false);
309
310
311	/** Returns true if this view point is in a valid view space,
312	false otherwise.
313	*/
314	bool ViewPointValid(const Vector3 &viewPoint) const;
315
316	/** Returns view cell corresponding to
317	the invalid view space.
318	*/
319	BspViewCell *GetOutOfBoundsCell();
320
321	/** Writes tree to output stream
322	*/
323	#if ZIPPED_VIEWCELLS
324	bool Export(ogzstream &stream);
325	#else
326	bool Export(ofstream &stream);
327	#endif
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 data the traversal data holding the polygons and rays which the split decision is based
470	@param frontData the front node traversal data (which may be updated to avoid repcomputations
471	@param backData the front node traversal data (which may be updated to avoid repcomputations
472	@param splitAxis 0 - 2 if axis aligned split, 3 if polygon-aligned split
473
474	@note the polygons can be reordered in the process
475
476	@returns true if the cost of the split is under maxCostRatio
477
478	*/
479	bool SelectPlane(Plane3 &plane,
480	BspLeaf *leaf,
481	VspBspTraversalData &data,
482	VspBspTraversalData &frontData,
483	VspBspTraversalData &backData,
484	int &splitAxis);
485
486	/** Strategies where the effect of the split plane is tested
487	on all input rays.
488
489	@returns the cost of the candidate split plane
490	*/
491	float EvalSplitPlaneCost(const Plane3 &candidatePlane,
492	const VspBspTraversalData &data,
493	BspNodeGeometry &geomFront,
494	BspNodeGeometry &geomBack,
495	float &pFront,
496	float &pBack) const;
497
498	/** Subdivides leaf.
499	@param leaf the leaf to be subdivided
500
501	@param polys the polygons to be split
502	@param frontPolys returns the polygons in front of the split plane
503	@param backPolys returns the polygons in the back of the split plane
504
505	@param rays the polygons to be filtered
506	@param frontRays returns the polygons in front of the split plane
507	@param backRays returns the polygons in the back of the split plane
508
509	@returns the root of the subdivision
510	*/
511
512	BspInterior *SubdivideNode(const Plane3 &splitPlane,
513	VspBspTraversalData &tData,
514	VspBspTraversalData &frontData,
515	VspBspTraversalData &backData,
516	PolygonContainer &coincident);
517
518	/** Extracts the meshes of the objects and adds them to polygons.
519	Adds object aabb to the aabb of the tree.
520	@param maxPolys the maximal number of objects to be stored as polygons
521	@returns the number of polygons
522	*/
523	int AddToPolygonSoup(const ObjectContainer &objects,
524	PolygonContainer &polys,
525	int maxObjects = 0);
526
527	/** Extracts the meshes of the view cells and and adds them to polygons.
528	Adds view cell aabb to the aabb of the tree.
529	@param maxPolys the maximal number of objects to be stored as polygons
530	@returns the number of polygons
531	*/
532	int AddToPolygonSoup(const ViewCellContainer &viewCells,
533	PolygonContainer &polys,
534	int maxObjects = 0);
535
536	/** Extract polygons of this mesh and add to polygon container.
537	@param mesh the mesh that drives the polygon construction
538	@param parent the parent intersectable this polygon is constructed from
539	@returns number of polygons
540	*/
541	int AddMeshToPolygons(Mesh mesh, PolygonContainer &polys, MeshInstance parent);
542
543	/** Selects an axis aligned for the next split.
544	@returns cost for this split
545	*/
546	float SelectAxisAlignedPlane(Plane3 &plane,
547	const VspBspTraversalData &tData,
548	int &axis,
549	BspNodeGeometry **frontGeom,
550	BspNodeGeometry **backGeom,
551	float &pFront,
552	float &pBack,
553	const bool useKdSplit);
554
555	/** Sorts split candidates for surface area heuristics for axis aligned splits.
556	@param polys the input for choosing split candidates
557	@param axis the current split axis
558	@param splitCandidates returns sorted list of split candidates
559	*/
560	void SortSplitCandidates(const RayInfoContainer &rays,
561	const int axis,
562	float minBand,
563	float maxBand);
564
565	/** Computes best cost for axis aligned planes.
566	*/
567	float BestCostRatioHeuristics(const RayInfoContainer &rays,
568	const AxisAlignedBox3 &box,
569	const int pvsSize,
570	const int axis,
571	float &position);
572
573	/** Subdivides the rays into front and back rays according to the split plane.
574
575	@param plane the split plane
576	@param rays contains the rays to be split. The rays are
577	distributed into front and back rays.
578	@param frontRays returns rays on the front side of the plane
579	@param backRays returns rays on the back side of the plane
580
581	@returns the number of splits
582	*/
583	int SplitRays(const Plane3 &plane,
584	RayInfoContainer &rays,
585	RayInfoContainer &frontRays,
586	RayInfoContainer &backRays) const;
587
588
589	/** Extracts the split planes representing the space bounded by node n.
590	*/
591	void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const;
592
593	/** Adds the object to the pvs of the front and back leaf with a given classification.
594
595	@param obj the object to be added
596	@param cf the ray classification regarding the split plane
597	@param frontPvs returns the PVS of the front partition
598	@param backPvs returns the PVS of the back partition
599
600	*/
601	void AddObjToPvs(Intersectable *obj,
602	const int cf,
603	float &frontPvs,
604	float &backPvs,
605	float &totalPvs) const;
606
607	/** Computes PVS size induced by the rays.
608	*/
609	int ComputePvsSize(const RayInfoContainer &rays) const;
610
611	/** Returns true if tree can be terminated.
612	*/
613	inline bool LocalTerminationCriteriaMet(const VspBspTraversalData &data) const;
614
615	/** Returns true if global tree can be terminated.
616	*/
617	inline bool GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const;
618
619	/** Computes accumulated ray lenght of this rays.
620	*/
621	float AccumulatedRayLength(const RayInfoContainer &rays) const;
622
623	/** Splits polygons with respect to the split plane.
624
625	@param plane the split plane
626	@param polys the polygons to be split. the polygons are consumed and
627	distributed to the containers frontPolys, backPolys, coincident.
628	@param frontPolys returns the polygons in the front of the split plane
629	@param backPolys returns the polygons in the back of the split plane
630	@param coincident returns the polygons coincident to the split plane
631
632	@returns the number of splits
633	*/
634	int SplitPolygons(const Plane3 &plane,
635	PolygonContainer &polys,
636	PolygonContainer &frontPolys,
637	PolygonContainer &backPolys,
638	PolygonContainer &coincident) const;
639
640	/** Adds ray sample contributions to the PVS.
641	@param sampleContributions the number contributions of the samples
642	@param contributingSampels the number of contributing rays
643
644	*/
645	void AddToPvs(BspLeaf *leaf,
646	const RayInfoContainer &rays,
647	float &sampleContributions,
648	int &contributingSamples);
649
650
651	/** Take 3 ray endpoints, where two are minimum and one a maximum
652	point or the other way round.
653	*/
654	Plane3 ChooseCandidatePlane(const RayInfoContainer &rays) const;
655
656	/** Take plane normal as plane normal and the midpoint of the ray.
657	PROBLEM: does not resemble any point where visibility is
658	likely to change
659	*/
660	Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const;
661
662	/** Fit the plane between the two lines so that the plane
663	has equal shortest distance to both lines.
664	*/
665	Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
666
667	/** Collects candidates for merging.
668	@param leaves the leaves to be merged
669	@returns number of leaves in queue
670	*/
671	int CollectMergeCandidates(const vector<BspLeaf *> leaves, vector<MergeCandidate> &candidates);
672
673	/** Collects candidates for the merge in the merge queue.
674	@returns number of leaves in queue
675	*/
676	int CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
677
678	/** Preprocesses polygons and throws out all polygons which are coincident to
679	the view space box faces (they can be problematic).
680	*/
681	void PreprocessPolygons(PolygonContainer &polys);
682
683	/** Propagates valid flag up the tree.
684	*/
685	void PropagateUpValidity(BspNode *node);
686
687	/** Writes the node to disk
688	@note: should be implemented as visitor.
689	*/
690	#if ZIPPED_VIEWCELLS
691	void ExportNode(BspNode *node, ogzstream &stream);
692	#else
693	void ExportNode(BspNode *node, ofstream &stream);
694	#endif
695
696	/** Returns estimated memory usage of tree.
697	*/
698	float GetMemUsage() const;
699	//float GetMemUsage(const VspBspTraversalQueue &tstack) const;
700
701
702
703	///////////////////////////////////////////////////////////
704	protected:
705
706	/// Pointer to the root of the tree
707	BspNode *mRoot;
708
709	/// the pointer to the view cells manager
710	ViewCellsManager *mViewCellsManager;
711
712	/// View cell corresponding to the space outside the valid view space
713	BspViewCell *mOutOfBoundsCell;
714
715	/// the bsp tree statistics
716	BspTreeStatistics mBspStats;
717
718	/// sorted split candidates used for sweep-heuristics
719	vector<SortableEntry> *mSplitCandidates;
720
721	/// box around the whole view domain
722	AxisAlignedBox3 mBox;
723
724
725	//-- termination critera
726
727	/// minimal number of rays before subdivision termination
728	int mTermMinRays;
729	/// maximal possible depth
730	int mTermMaxDepth;
731	/// mininum probability
732	float mTermMinProbability;
733	/// mininum PVS
734	int mTermMinPvs;
735	/// maximal contribution per ray
736	float mTermMaxRayContribution;
737	/// minimal accumulated ray length
738	float mTermMinAccRayLength;
739	/// maximal acceptable cost ratio
740	float mTermMaxCostRatio;
741	/// tolerance value indicating how often the max cost ratio can be failed
742	int mTermMissTolerance;
743
744
745	//-- termination criteria for
746	//-- hybrid stategy where only axis aligned split are used until
747	//-- a certain point and then also polygon aligned split are taken
748
749	/// minimal number of rays where axis aligned split is taken
750	int mTermMinRaysForAxisAligned;
751	/// max ray contribution
752	float mTermMaxRayContriForAxisAligned;
753	/// weight for heuristics evaluation
754	float mAxisAlignedCtDivCi;
755	/// spezifies the split border of the axis aligned split
756	float mAxisAlignedSplitBorder;
757
758
759	//-- global terminatino criteria
760
761	float mTermMinGlobalCostRatio;
762	int mTermGlobalCostMissTolerance;
763	int mGlobalCostMisses;
764
765	/// maximal number of view cells
766	int mMaxViewCells;
767	/// maximal tree memory
768	float mMaxMemory;
769	/// the tree is out of memory
770	bool mOutOfMemory;
771
772
773	/// number of candidates evaluated for the next split plane
774	int mMaxPolyCandidates;
775	/// number of candidates for split planes evaluated using the rays
776	int mMaxRayCandidates;
777
778
779
780	//-- axis aligned split criteria
781
782	/// if only driving axis should be used for choosing the axis-aligned split
783	bool mOnlyDrivingAxis;
784	/// if heuristics should be used to place the split plane of an axis-aligned split
785	bool mUseCostHeuristics;
786	/// if driving axis should taken if max cost is exceeded for
787	/// all evaluated axis aligned split plane candidates
788	bool mUseDrivingAxisIfMaxCostViolated;
789	/// minimal relative position where the split axis can be placed
790	float mMinBand;
791	/// maximal relative position where the split axis can be placed
792	float mMaxBand;
793	/// balancing factor for PVS criterium
794	float mCtDivCi;
795	/// if random split axis should be used
796	bool mUseRandomAxis;
797	/// if vsp bsp tree should simulate octree
798	bool mCirculatingAxis;
799
800
801
802	/// priority queue strategy
803	enum {BREATH_FIRST, DEPTH_FIRST, COST_BASED};
804	/// if we should use breath first priority for the splits
805	int mNodePriorityQueueType;
806	/// if split cost queue should be used to compute next best split
807	bool mUseSplitCostQueue;
808
809
810
811	/// Strategies for choosing next split plane.
812	enum {NO_STRATEGY = 0,
813	RANDOM_POLYGON = 1,
814	AXIS_ALIGNED = 2,
815	LEAST_RAY_SPLITS = 256,
816	BALANCED_RAYS = 512,
817	PVS = 1024
818	};
819
820	/// strategy to get the best split plane
821	int mSplitPlaneStrategy;
822
823	//-- factors guiding the split plane heuristics
824
825	float mLeastRaySplitsFactor;
826	float mBalancedRaysFactor;
827	float mPvsFactor;
828
829
830	/// if area or volume should be used for PVS heuristics
831	bool mUseAreaForPvs;
832	/// tolerance for polygon split
833	float mEpsilon;
834	/// maximal number of test rays used to evaluate candidate split plane
835	int mMaxTests;
836	/// normalizes different bsp split plane criteria
837	float mCostNormalizer;
838	// if rays should be stored in leaves
839	bool mStoreRays;
840	/// render cost weight between expected value and variance
841	float mRenderCostWeight;
842
843
844	//-- subdivision statistics
845
846	/// subdivision stats output file
847	ofstream mSubdivisionStats;
848	float mTotalCost;
849	int mTotalPvsSize;
850
851
852	/// use polygon split whenever there are polys left
853	bool mUsePolygonSplitIfAvailable;
854	/// current time stamp (used for keeping split history)
855	int mTimeStamp;
856	/// number of currenly generated view cells
857	int mCreatedViewCells;
858
859
860	private:
861
862	/// Generates unique ids for PVS criterium
863	static void GenerateUniqueIdsForPvs();
864
865	//-- unique ids for PVS criterium
866	static int sFrontId;
867	static int sBackId;
868	static int sFrontAndBackId;
869	};
870
871	}
872
873
874	#endif

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

Download in other formats: