Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/VssTree.h @ 427

Revision 427, 18.7 KB checked in by bittner, 19 years ago (diff)
vss updates

Line
1	// ================================================================
2	// $Id$
3	// ****************************************************************
4	//
5	// Initial coding by
6	/**
7	@author Jiri Bittner
8	*/
9
10	#ifndef __VSSTREE_H__
11	#define __VSSTREE_H__
12
13	// Standard headers
14	#include <iomanip>
15	#include <vector>
16	#include <functional>
17	#include <stack>
18
19
20	// User headers
21	#include "VssRay.h"
22	#include "AxisAlignedBox3.h"
23
24
25	#define USE_KDNODE_VECTORS 1
26	#define _RSS_STATISTICS
27	#define _RSS_TRAVERSAL_STATISTICS
28
29
30	#include "Statistics.h"
31	#include "Ray.h"
32
33	// --------------------------------------------------------------
34	// Static statistics for kd-tree search
35	// --------------------------------------------------------------
36	class VssStatistics :
37	public StatisticsBase
38	{
39	public:
40	// total number of nodes
41	int nodes;
42	// number of splits along each of the axes
43	int splits[7];
44	// totals number of rays
45	int rays;
46	// initial size of the pvs
47	int initialPvsSize;
48	// total number of query domains
49	int queryDomains;
50	// total number of ray references
51	int rayRefs;
52
53	// max depth nodes
54	int maxDepthNodes;
55	// max depth nodes
56	int minPvsNodes;
57	int minRaysNodes;
58	// max ray contribution nodes
59	int maxRayContribNodes;
60	// max depth nodes
61	int minSizeNodes;
62	int maxCostRatioNodes;
63
64	// max number of rays per node
65	int maxRayRefs;
66	// number of dynamically added ray refs
67	int addedRayRefs;
68	// number of dynamically removed ray refs
69	int removedRayRefs;
70
71	// Constructor
72	VssStatistics() {
73	Reset();
74	}
75
76	int Nodes() const {return nodes;}
77	int Interior() const { return nodes/2; }
78	int Leaves() const { return (nodes/2) + 1; }
79
80	void Reset() {
81	nodes = 0;
82	for (int i=0; i<7; i++)
83	splits[i] = 0;
84	rays = queryDomains = 0;
85	rayRefs = 0;
86	maxDepthNodes = 0;
87	minPvsNodes = 0;
88	minRaysNodes = 0;
89	maxRayRefs = 0;
90	addedRayRefs = removedRayRefs = 0;
91	initialPvsSize = 0;
92	maxRayContribNodes = 0;
93	minSizeNodes = 0;
94	maxCostRatioNodes = 0;
95	}
96
97
98	void
99	Print(ostream &app) const;
100
101	friend ostream &operator<<(ostream &s, const VssStatistics &stat) {
102	stat.Print(s);
103	return s;
104	}
105
106	};
107
108
109	// --------------------------------------------------------------
110	// For sorting rays
111	// --------------------------------------------------------------
112	struct SortableEntry
113	{
114	enum EType {
115	ERayMin,
116	ERayMax
117	};
118
119	int type;
120	float value;
121	void *data;
122
123	SortableEntry() {}
124	SortableEntry(const int t, const float v, void *d):type(t),
125	value(v),
126	data(d) {}
127
128	friend bool operator<(const SortableEntry &a, const SortableEntry &b) {
129	return a.value < b.value;
130	}
131	};
132
133
134	class VssTreeInterior;
135
136
137	// --------------------------------------------------------------
138	// KD-tree node - abstract class
139	// --------------------------------------------------------------
140	class VssTreeNode
141	{
142	public:
143
144	#define USE_FIXEDPOINT_T 0
145
146	struct RayInfo
147	{
148	// pointer to the actual ray
149	VssRay *mRay;
150
151	// endpoints - do we need them?
152	#if USE_FIXEDPOINT_T
153	short mMinT, mMaxT;
154	#else
155	float mMinT, mMaxT;
156	#endif
157
158	RayInfo():mRay(NULL) {}
159
160	RayInfo(VssRay *r):mRay(r), mMinT(0),
161	#if USE_FIXEDPOINT_T
162	#define FIXEDPOINT_ONE 0x7FFE
163	// mMaxT(0xFFFF)
164	mMaxT(FIXEDPOINT_ONE)
165	#else
166	mMaxT(1.0f)
167	#endif
168	{}
169
170	RayInfo(VssRay *r,
171	const float _min,
172	const float _max
173	):mRay(r) {
174	SetMinT(_min);
175	SetMaxT(_max);
176	}
177
178	RayInfo(VssRay *r,
179	const short _min,
180	const float _max
181	):mRay(r), mMinT(_min) {
182	SetMaxT(_max);
183	}
184
185	RayInfo(VssRay *r,
186	const float _min,
187	const short _max
188	):mRay(r), mMaxT(_max) {
189	SetMinT(_min);
190	}
191
192	enum {
193	SOURCE_RAY = 0,
194	TERMINATION_RAY,
195	PASSING_RAY,
196	CONTAINED_RAY
197	};
198
199	int GetRayClass() const {
200
201	bool startsBefore = GetMinT() > 0.0f;
202	bool terminatesAfter = GetMaxT() < 1.0f;
203
204	if (startsBefore && terminatesAfter)
205	return PASSING_RAY;
206
207	if (!startsBefore && !terminatesAfter)
208	return CONTAINED_RAY;
209
210	if (!startsBefore)
211	return SOURCE_RAY;
212
213	return TERMINATION_RAY;
214	}
215
216	friend bool operator<(const RayInfo &a, const RayInfo &b) {
217	return a.mRay < b.mRay;
218	}
219
220
221	float ExtrapOrigin(const int axis) const {
222	return mRay->GetOrigin(axis) + GetMinT()*mRay->GetDir(axis);
223	}
224
225	float ExtrapTermination(const int axis) const {
226	return mRay->GetOrigin(axis) + GetMaxT()*mRay->GetDir(axis);
227	}
228
229	#if USE_FIXEDPOINT_T
230	float GetMinT () const { return mMinT/(float)(FIXEDPOINT_ONE); }
231	float GetMaxT () const { return mMaxT/(float)(FIXEDPOINT_ONE); }
232
233	void SetMinT (const float t) {
234	mMinT = (short) (t*(float)(FIXEDPOINT_ONE));
235	}
236
237	void SetMaxT (const float t) {
238	mMaxT = (short) (t*(float)(FIXEDPOINT_ONE));
239	mMaxT++;
240	// if (mMaxT!=0xFFFF)
241	// mMaxT++;
242	}
243	#else
244	float GetMinT () const { return mMinT; }
245	float GetMaxT () const { return mMaxT; }
246
247	void SetMinT (const float t) { mMinT = t; }
248	void SetMaxT (const float t) { mMaxT = t; }
249	#endif
250
251
252	int ComputeRayIntersection(const int axis,
253	const float position,
254	float &t
255	) const {
256
257	// intersect the ray with the plane
258	float denom = mRay->GetDir(axis);
259
260	if (fabs(denom) < 1e-20)
261	//if (denom == 0.0f)
262	return (mRay->GetOrigin(axis) > position) ? 1 : -1;
263
264	t = (position - mRay->GetOrigin(axis))/denom;
265
266	if (t < GetMinT())
267	return (denom > 0) ? 1 : -1;
268
269	if (t > GetMaxT())
270	return (denom > 0) ? -1 : 1;
271
272	return 0;
273	}
274
275
276	};
277
278
279	typedef vector<RayInfo> RayInfoContainer;
280
281	enum { EInterior, ELeaf };
282
283	/////////////////////////////////
284	// The actual data goes here
285
286	// link to the parent
287	VssTreeInterior *parent;
288
289	enum {SPLIT_X=0, SPLIT_Y, SPLIT_Z, SPLIT_DIRX, SPLIT_DIRY, SPLIT_DIRZ};
290
291	// splitting axis
292	char axis;
293
294	// depth
295	unsigned char depth;
296
297	// short depth;
298	//
299	/////////////////////////////////
300
301	inline VssTreeNode(VssTreeInterior *p);
302
303
304	virtual ~VssTreeNode() {};
305	virtual int Type() const = 0;
306
307
308	bool IsLeaf() const { return axis == -1; }
309
310	virtual void Print(ostream &s) const = 0;
311
312	virtual int GetAccessTime() {
313	return 0x7FFFFFF;
314	}
315
316
317
318	};
319
320	// --------------------------------------------------------------
321	// KD-tree node - interior node
322	// --------------------------------------------------------------
323	class VssTreeInterior :
324	public VssTreeNode
325	{
326	public:
327	// plane in local modelling coordinates
328	float position;
329
330	// pointers to children
331	VssTreeNode back, front;
332
333	// the bbox of the node
334	AxisAlignedBox3 bbox;
335
336	// the bbox of the node
337	AxisAlignedBox3 dirBBox;
338
339	// data for caching
340	long accesses;
341	long lastAccessTime;
342
343	VssTreeInterior(VssTreeInterior *p):VssTreeNode(p),
344	back(NULL),
345	front(NULL),
346	accesses(0),
347	lastAccessTime(-1)
348	{ }
349
350	virtual int GetAccessTime() {
351	return lastAccessTime;
352	}
353
354	void SetupChildLinks(VssTreeNode b, VssTreeNode f) {
355	back = b;
356	front = f;
357	b->parent = f->parent = this;
358	}
359
360	void ReplaceChildLink(VssTreeNode oldChild, VssTreeNode newChild) {
361	if (back == oldChild)
362	back = newChild;
363	else
364	front = newChild;
365	}
366
367	virtual int Type() const { return EInterior; }
368
369	virtual ~VssTreeInterior() {
370	if (back)
371	delete back;
372	if (front)
373	delete front;
374	}
375
376	virtual void Print(ostream &s) const {
377	if (axis == 0)
378	s<<"x ";
379	else
380	if (axis == 1)
381	s<<"y ";
382	else
383	s<<"z ";
384	s<<position<<" ";
385	back->Print(s);
386	front->Print(s);
387	}
388
389
390
391	int ComputeRayIntersection(const RayInfo &rayData,
392	float &t
393	) {
394	return rayData.ComputeRayIntersection(axis, position, t);
395	}
396
397	};
398
399
400	// --------------------------------------------------------------
401	// KD-tree node - leaf node
402	// --------------------------------------------------------------
403	class VssTreeLeaf :
404	public VssTreeNode
405	{
406	private:
407	int mPvsSize;
408	public:
409	static int mailID;
410	int mailbox;
411
412	RayInfoContainer rays;
413	bool mValidPvs;
414
415	VssTreeLeaf(VssTreeInterior *p,
416	const int nRays
417	):VssTreeNode(p), rays(), mPvsSize(0), mValidPvs(false) {
418	rays.reserve(nRays);
419	}
420
421	virtual ~VssTreeLeaf() { }
422
423	virtual int Type() const { return ELeaf; }
424
425	virtual void Print(ostream &s) const {
426	s<<endl<<"L: r="<<rays.size()<<endl;
427	};
428
429	void AddRay(const RayInfo &data) {
430	mValidPvs = false;
431	rays.push_back(data);
432	data.mRay->Ref();
433	}
434
435	int GetPvsSize() const {
436	return mPvsSize;
437	}
438	void SetPvsSize(const int s) {
439	mPvsSize = s;
440	}
441
442	void
443	UpdatePvsSize();
444
445	void Mail() { mailbox = mailID; }
446	static void NewMail() { mailID++; }
447	bool Mailed() const { return mailbox == mailID; }
448
449	bool Mailed(const int mail) {
450	return mailbox >= mailID + mail;
451	}
452
453	float GetAvgRayContribution() const {
454	return GetPvsSize()/((float)rays.size() + Limits::Small);
455	}
456
457	float GetSqrRayContribution() const {
458	return sqr(GetPvsSize()/((float)rays.size() + Limits::Small));
459	}
460
461	// comparator for the
462	struct less_contribution : public
463	binary_function<const VssTreeLeaf , const VssTreeLeaf , bool> {
464
465	bool operator()(const VssTreeLeaf * a, const VssTreeLeaf *b) {
466	return a->GetAvgRayContribution() < b->GetAvgRayContribution();
467	}
468	};
469
470	struct greater_contribution : public
471	binary_function<const VssTreeLeaf , const VssTreeLeaf , bool> {
472
473	bool operator()(const VssTreeLeaf * a, const VssTreeLeaf *b) {
474	return a->GetAvgRayContribution() > b->GetAvgRayContribution();
475	}
476	};
477
478	friend bool GreaterContribution(const VssTreeLeaf * a, const VssTreeLeaf *b) {
479	return a->GetAvgRayContribution() > b->GetAvgRayContribution();
480	}
481
482	};
483
484	// Inline functions
485	inline
486	VssTreeNode::VssTreeNode(VssTreeInterior *p):
487	parent(p), axis(-1), depth(p ? p->depth + 1 : 0) {}
488
489
490
491	// ---------------------------------------------------------------
492	// Main LSDS search class
493	// ---------------------------------------------------------------
494	class VssTree
495	{
496	struct TraversalData
497	{
498	VssTreeNode *node;
499	AxisAlignedBox3 bbox;
500	int depth;
501	float priority;
502
503	TraversalData() {}
504
505	TraversalData(VssTreeNode *n, const float p):
506	node(n), priority(p)
507	{}
508
509	TraversalData(VssTreeNode *n,
510	const AxisAlignedBox3 &b,
511	const int d):
512	node(n), bbox(b), depth(d) {}
513
514
515	// comparator for the
516	struct less_priority : public
517	binary_function<const TraversalData, const TraversalData, bool> {
518
519	bool operator()(const TraversalData a, const TraversalData b) {
520	return a.priority < b.priority;
521	}
522
523	};
524
525	// ~TraversalData() {}
526	// TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {}
527
528	friend bool operator<(const TraversalData &a,
529	const TraversalData &b) {
530	// return a.node->queries.size() < b.node->queries.size();
531	VssTreeLeaf leafa = (VssTreeLeaf ) a.node;
532	VssTreeLeaf leafb = (VssTreeLeaf ) b.node;
533	#if 0
534	return
535	leafa->rays.size()*a.bbox.GetVolume()
536	<
537	leafb->rays.size()*b.bbox.GetVolume();
538	#endif
539	#if 1
540	return
541	leafa->GetPvsSize()*a.bbox.GetVolume()
542	<
543	leafb->GetPvsSize()*b.bbox.GetVolume();
544	#endif
545	#if 0
546	return
547	leafa->GetPvsSize()
548	<
549	leafb->GetPvsSize();
550	#endif
551	#if 0
552	return
553	leafa->GetPvsSize()/(leafa->rays.size()+1)
554	>
555	leafb->GetPvsSize()/(leafb->rays.size()+1);
556	#endif
557	#if 0
558	return
559	leafa->GetPvsSize()*leafa->rays.size()
560	<
561	leafb->GetPvsSize()*leafb->rays.size();
562	#endif
563	}
564	};
565
566	// simplified data for ray traversal only...
567
568	struct RayTraversalData {
569
570	VssTreeNode::RayInfo rayData;
571	VssTreeNode *node;
572
573	RayTraversalData() {}
574	RayTraversalData(VssTreeNode *n,
575	const VssTreeNode::RayInfo &data):
576	rayData(data), node(n) {}
577	};
578
579	public:
580	/////////////////////////////
581	// The core pointer
582	VssTreeNode *root;
583
584	/////////////////////////////
585	// Basic properties
586
587	// total number of nodes of the tree
588	int nodes;
589	// axis aligned bounding box of the scene
590	AxisAlignedBox3 bbox;
591
592	// axis aligned bounding box of directions
593	AxisAlignedBox3 dirBBox;
594
595	/////////////////////////////
596	// Construction parameters
597
598	// epsilon used for the construction
599	float epsilon;
600
601	// ratio between traversal and intersection costs
602	float ct_div_ci;
603	// max depth of the tree
604	int termMaxDepth;
605	// minimal ratio of the volume of the cell and the query volume
606	float termMinSize;
607
608	// minimal pvs per node to still get subdivided
609	int termMinPvs;
610
611	// minimal ray number per node to still get subdivided
612	int termMinRays;
613
614	// maximal cost ration to subdivide a node
615	float termMaxCostRatio;
616
617	// maximal contribution per ray to subdivide the node
618	float termMaxRayContribution;
619
620
621	// randomized construction
622	bool randomize;
623
624	// type of the splitting to use fo rthe tree construction
625	enum {ESplitRegular, ESplitHeuristic };
626	int splitType;
627
628	// maximal size of the box on which the refdir splitting can be performed
629	// (relative to the scene bbox
630	float refDirBoxMaxSize;
631
632	// maximum alovable memory in MB
633	float maxTotalMemory;
634
635	// maximum alovable memory for static kd tree in MB
636	float maxStaticMemory;
637
638	// this is used during the construction depending
639	// on the type of the tree and queries...
640	float maxMemory;
641
642
643	// minimal acess time for collapse
644	int accessTimeThreshold;
645
646	// minimal depth at which to perform collapse
647	int minCollapseDepth;
648
649
650	// reusable array of split candidates
651	vector<SortableEntry> *splitCandidates;
652	/////////////////////////////
653
654	VssStatistics stat;
655
656
657	VssTree();
658	virtual ~VssTree();
659
660	virtual void
661	Construct(
662	VssRayContainer &rays,
663	AxisAlignedBox3 *forcedBoundingBox = NULL
664	);
665
666	// incemental construction
667	virtual void UpdateRays(VssRayContainer &remove,
668	VssRayContainer &add
669	);
670
671	virtual void AddRays(
672	VssRayContainer &add
673	)
674	{
675	VssRayContainer remove;
676	UpdateRays(remove, add);
677	}
678
679
680
681	VssTreeNode *
682	Locate(const Vector3 &v);
683
684	VssTreeNode *
685	SubdivideNode(VssTreeLeaf *leaf,
686	const AxisAlignedBox3 &box,
687	AxisAlignedBox3 &backBox,
688	AxisAlignedBox3 &frontBox
689	);
690
691	VssTreeNode *
692	Subdivide(const TraversalData &tdata);
693
694	int
695	SelectPlane(VssTreeLeaf *leaf,
696	const AxisAlignedBox3 &box,
697	float &position,
698	int &raysBack,
699	int &raysFront,
700	int &pvsBack,
701	int &pvsFront
702	);
703
704	void
705	SortSplitCandidates(
706	VssTreeLeaf *node,
707	const int axis
708	);
709
710
711	// return memory usage in MB
712	float GetMemUsage() const {
713	return
714	(sizeof(VssTree) +
715	stat.Leaves()*sizeof(VssTreeLeaf) +
716	stat.Interior()*sizeof(VssTreeInterior) +
717	stat.rayRefssizeof(VssTreeNode::RayInfo))/(1024.0f1024.0f);
718	}
719
720	float GetRayMemUsage() const {
721	return
722	stat.rays(sizeof(VssRay))/(1024.0f1024.0f);
723	}
724
725	float
726	BestCostRatioHeuristic(
727	VssTreeLeaf *node,
728	int &axis,
729	float &position,
730	int &raysBack,
731	int &raysFront,
732	int &pvsBack,
733	int &pvsFront
734	);
735
736	float
737	BestCostRatioRegular(
738	VssTreeLeaf *node,
739	int &axis,
740	float &position,
741	int &raysBack,
742	int &raysFront,
743	int &pvsBack,
744	int &pvsFront
745
746	);
747
748	float
749	EvalCostRatio(
750	VssTreeLeaf *node,
751	const int axis,
752	const float position,
753	int &raysBack,
754	int &raysFront,
755	int &pvsBack,
756	int &pvsFront
757	);
758
759	AxisAlignedBox3 GetBBox(const VssTreeNode *node) {
760	if (node->parent == NULL)
761	return bbox;
762
763	if (!node->IsLeaf())
764	return ((VssTreeInterior *)node)->bbox;
765
766	if (node->parent->axis >= 3)
767	return node->parent->bbox;
768
769	AxisAlignedBox3 box(node->parent->bbox);
770	if (node->parent->front == node)
771	box.SetMin(node->parent->axis, node->parent->position);
772	else
773	box.SetMax(node->parent->axis, node->parent->position);
774	return box;
775	}
776
777	AxisAlignedBox3 GetDirBBox(const VssTreeNode *node) {
778
779	if (node->parent == NULL)
780	return dirBBox;
781
782	if (!node->IsLeaf() )
783	return ((VssTreeInterior *)node)->dirBBox;
784
785	if (node->parent->axis < 3)
786	return node->parent->dirBBox;
787
788	AxisAlignedBox3 dBBox(node->parent->dirBBox);
789
790	if (node->parent->front == node)
791	dBBox.SetMin(node->parent->axis - 3, node->parent->position);
792	else
793	dBBox.SetMax(node->parent->axis - 3, node->parent->position);
794	return dBBox;
795	}
796
797	int
798	ReleaseMemory(const int time);
799
800	int
801	CollapseSubtree(VssTreeNode *node, const int time);
802
803	void
804	CountAccess(VssTreeInterior *node, const long time) {
805	node->accesses++;
806	node->lastAccessTime = time;
807	}
808
809	VssTreeNode *
810	SubdivideLeaf(
811	VssTreeLeaf *leaf
812	);
813
814	void
815	RemoveRay(VssRay *ray,
816	vector<VssTreeLeaf > affectedLeaves,
817	const bool removeAllScheduledRays
818	);
819
820	// void
821	// AddRay(VssRay *ray);
822	void
823	AddRay(VssTreeNode::RayInfo &info);
824
825	void
826	TraverseInternalNode(
827	RayTraversalData &data,
828	stack<RayTraversalData> &tstack);
829
830	void
831	EvaluateLeafStats(const TraversalData &data);
832
833
834	int
835	GetRootPvsSize() const {
836	return GetPvsSize(root, bbox);
837	}
838
839	int
840	GetPvsSize(VssTreeNode *node, const AxisAlignedBox3 &box) const;
841
842	void
843	GetRayContributionStatistics(
844	float &minRayContribution,
845	float &maxRayContribution,
846	float &avgRayContribution
847	);
848
849	int
850	GenerateRays(const float ratioPerLeaf,
851	SimpleRayContainer &rays);
852
853	int
854	GenerateRays(const int numberOfRays,
855	const int numberOfLeaves,
856	SimpleRayContainer &rays);
857
858	float
859	GetAvgPvsSize();
860
861	int
862	UpdateSubdivision();
863
864	bool
865	TerminationCriteriaSatisfied(VssTreeLeaf *leaf);
866
867	void
868	CollectLeaves(vector<VssTreeLeaf *> &leaves);
869
870	bool
871	ClipRay(
872	VssTreeNode::RayInfo &rayInfo,
873	const AxisAlignedBox3 &box
874	);
875
876
877	};
878
879
880	#endif // __LSDS_KDTREE_H__
881

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

Download in other formats: