Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp @ 421

Revision 421, 38.0 KB checked in by mattausch, 19 years ago (diff)
fixed controls for terrain demo fixed member names in vspkdtree

Line
1
2	// ================================================================
3	// $Id: lsds_kdtree.cpp,v 1.18 2005/04/16 09:34:21 bittner Exp $
4	// ****************************************************************
5	/**
6	The KD tree based LSDS
7	*/
8	// Initial coding by
9	/**
10	@author Jiri Bittner
11	*/
12
13	// Standard headers
14	#include <stack>
15	#include <queue>
16	#include <algorithm>
17	#include <fstream>
18	#include <string>
19
20	#include "VspKdTree.h"
21
22	#include "Environment.h"
23	#include "VssRay.h"
24	#include "Intersectable.h"
25	#include "Ray.h"
26	#include "RayInfo.h"
27
28	// Static variables
29	int VspKdTreeLeaf::mailID = 0;
30
31	/// Adds object to the pvs of the front and back node
32	inline void AddObject2Pvs(Intersectable *object,
33	const int side,
34	int &pvsBack,
35	int &pvsFront)
36	{
37	if (!object)
38	return;
39
40	if (side <= 0)
41	{
42	if (!object->Mailed() && !object->Mailed(2))
43	{
44	++ pvsBack;
45
46	if (object->Mailed(1))
47	object->Mail(2);
48	else
49	object->Mail();
50	}
51	}
52
53	if (side >= 0)
54	{
55	if (!object->Mailed(1) && !object->Mailed(2))
56	{
57	++ pvsFront;
58	if (object->Mailed())
59	object->Mail(2);
60	else
61	object->Mail(1);
62	}
63	}
64	}
65
66	/**************************************************************/
67	/* class VspKdTreeNode implementation */
68	/**************************************************************/
69
70	// Inline constructor
71	VspKdTreeNode::VspKdTreeNode(VspKdTreeInterior *p):
72	mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0)
73	{}
74
75	VspKdTreeNode::~VspKdTreeNode()
76	{};
77
78	inline VspKdTreeInterior *VspKdTreeNode::GetParent() const
79	{
80	return mParent;
81	}
82
83	inline void VspKdTreeNode::SetParent(VspKdTreeInterior *p)
84	{
85	mParent = p;
86	}
87
88	bool VspKdTreeNode::IsLeaf() const
89	{
90	return mAxis == -1;
91	}
92
93	int VspKdTreeNode::GetAccessTime()
94	{
95	return 0x7FFFFFF;
96	}
97
98	/**************************************************************/
99	/* VspKdTreeInterior implementation */
100	/**************************************************************/
101
102	VspKdTreeInterior::VspKdTreeInterior(VspKdTreeInterior *p):
103	VspKdTreeNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)
104	{
105	}
106
107	int VspKdTreeInterior::GetAccessTime()
108	{
109	return mLastAccessTime;
110	}
111
112	void VspKdTreeInterior::SetupChildLinks(VspKdTreeNode b, VspKdTreeNode f)
113	{
114	mBack = b;
115	mFront = f;
116	b->SetParent(this);
117	f->SetParent(this);
118	}
119
120	void VspKdTreeInterior::ReplaceChildLink(VspKdTreeNode oldChild, VspKdTreeNode newChild)
121	{
122	if (mBack == oldChild)
123	mBack = newChild;
124	else
125	mFront = newChild;
126	}
127
128	int VspKdTreeInterior::Type() const
129	{
130	return EInterior;
131	}
132
133	VspKdTreeInterior::~VspKdTreeInterior()
134	{
135	DEL_PTR(mBack);
136	DEL_PTR(mFront);
137	}
138
139	void VspKdTreeInterior::Print(ostream &s) const
140	{
141	if (mAxis == 0)
142	s << "x ";
143	else
144	if (mAxis == 1)
145	s << "y ";
146	else
147	s << "z ";
148	s << mPosition << " ";
149
150	mBack->Print(s);
151	mFront->Print(s);
152	}
153
154	int VspKdTreeInterior::ComputeRayIntersection(const RayInfo &rayData, float &t)
155	{
156	return rayData.ComputeRayIntersection(mAxis, mPosition, t);
157	}
158
159	VspKdTreeNode *VspKdTreeInterior::GetBack() const
160	{
161	return mBack;
162	}
163
164	VspKdTreeNode *VspKdTreeInterior::GetFront() const
165	{
166	return mFront;
167	}
168
169
170	/*********************************************************/
171	/* class VspKdTreeLeaf implementation */
172	/*********************************************************/
173	VspKdTreeLeaf::VspKdTreeLeaf(VspKdTreeInterior *p, const int nRays):
174	VspKdTreeNode(p), mRays(), mPvsSize(0), mValidPvs(false)
175	{
176	mRays.reserve(nRays);
177	}
178
179	VspKdTreeLeaf::~VspKdTreeLeaf()
180	{}
181
182	int VspKdTreeLeaf::Type() const
183	{
184	return ELeaf;
185	}
186
187	void VspKdTreeLeaf::Print(ostream &s) const
188	{
189	s << endl << "L: r = " << (int)mRays.size() << endl;
190	};
191
192	void VspKdTreeLeaf::AddRay(const RayInfo &data)
193	{
194	mValidPvs = false;
195	mRays.push_back(data);
196	data.mRay->Ref();
197	}
198
199	int VspKdTreeLeaf::GetPvsSize() const
200	{
201	return mPvsSize;
202	}
203
204	void VspKdTreeLeaf::SetPvsSize(const int s)
205	{
206	mPvsSize = s;
207	}
208
209	void VspKdTreeLeaf::Mail()
210	{
211	mMailbox = mailID;
212	}
213
214	void VspKdTreeLeaf::NewMail()
215	{
216	++ mailID;
217	}
218
219	bool VspKdTreeLeaf::Mailed() const
220	{
221	return mMailbox == mailID;
222	}
223
224	bool VspKdTreeLeaf::Mailed(const int mail)
225	{
226	return mMailbox >= mailID + mail;
227	}
228
229	float VspKdTreeLeaf::GetAvgRayContribution() const
230	{
231	return GetPvsSize() / ((float)mRays.size() + Limits::Small);
232	}
233
234	float VspKdTreeLeaf::GetSqrRayContribution() const
235	{
236	return sqr(GetAvgRayContribution());
237	}
238
239	/*********************************************************/
240	/* class VspKdTree implementation */
241	/*********************************************************/
242
243
244	// Constructor
245	VspKdTree::VspKdTree()
246	{
247	environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth);
248	environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs);
249	environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays);
250	environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution);
251	environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio);
252
253	environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize);
254	mTermMinSize = sqr(mTermMinSize);
255
256	environment->GetFloatValue("VspKdTree.epsilon", epsilon);
257	environment->GetFloatValue("VspKdTree.ct_div_ci", ct_div_ci);
258
259	environment->GetFloatValue("VspKdTree.maxTotalMemory", maxTotalMemory);
260	environment->GetFloatValue("VspKdTree.maxStaticMemory", maxStaticMemory);
261
262
263	environment->GetIntValue("VspKdTree.accessTimeThreshold", accessTimeThreshold);
264	//= 1000;
265	environment->GetIntValue("VspKdTree.minCollapseDepth", minCollapseDepth);
266
267
268	// split type
269	char sname[128];
270	environment->GetStringValue("VspKdTree.splitType", sname);
271	string name(sname);
272
273	if (name.compare("regular") == 0)
274	splitType = ESplitRegular;
275	else
276	{
277	if (name.compare("heuristic") == 0)
278	splitType = ESplitHeuristic;
279	else
280	{
281	cerr << "Invalid VspKdTree split type " << name << endl;
282	exit(1);
283	}
284	}
285
286	mRoot = NULL;
287
288	splitCandidates = new vector<SortableEntry>;
289	}
290
291
292	VspKdTree::~VspKdTree()
293	{
294	DEL_PTR(mRoot);
295	}
296
297	void VspKdStatistics::Print(ostream &app) const
298	{
299	app << "===== VspKdTree statistics ===============\n";
300
301	app << "#N_RAYS ( Number of rays )\n"
302	<< rays <<endl;
303
304	app << "#N_INITPVS ( Initial PVS size )\n"
305	<< initialPvsSize <<endl;
306
307	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
308
309	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
310
311	app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n";
312	for (int i=0; i<7; i++)
313	app << splits[i] <<" ";
314	app <<endl;
315
316	app << "#N_RAYREFS ( Number of rayRefs )\n" <<
317	rayRefs << "\n";
318
319	app << "#N_RAYRAYREFS ( Number of rayRefs / ray )\n" <<
320	rayRefs/(double)rays << "\n";
321
322	app << "#N_LEAFRAYREFS ( Number of rayRefs / leaf )\n" <<
323	rayRefs/(double)Leaves() << "\n";
324
325	app << "#N_MAXRAYREFS ( Max number of rayRefs / leaf )\n" <<
326	maxRayRefs << "\n";
327
328
329	// app << setprecision(4);
330
331	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
332	maxDepthNodes*100/(double)Leaves()<<endl;
333
334	app << "#N_PMINPVSLEAVES ( Percentage of leaves with minCost )\n"<<
335	minPvsNodes*100/(double)Leaves()<<endl;
336
337	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minCost )\n"<<
338	minRaysNodes*100/(double)Leaves()<<endl;
339
340	app << "#N_PMINSIZELEAVES ( Percentage of leaves with minSize )\n"<<
341	minSizeNodes*100/(double)Leaves()<<endl;
342
343	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"<<
344	maxRayContribNodes*100/(double)Leaves()<<endl;
345
346	app << "#N_ADDED_RAYREFS (Number of dynamically added ray references )\n"<<
347	addedRayRefs<<endl;
348
349	app << "#N_REMOVED_RAYREFS (Number of dynamically removed ray references )\n"<<
350	removedRayRefs<<endl;
351
352	// app << setprecision(4);
353
354	app << "#N_CTIME ( Construction time [s] )\n"
355	<< Time() << " \n";
356
357	app << "===== END OF VspKdTree statistics ==========\n";
358
359	}
360
361
362	void
363	VspKdTreeLeaf::UpdatePvsSize()
364	{
365	if (!mValidPvs)
366	{
367	Intersectable::NewMail();
368	int pvsSize = 0;
369	for(RayInfoContainer::iterator ri = mRays.begin();
370	ri != mRays.end(); ++ ri)
371	{
372	if ((*ri).mRay->IsActive())
373	{
374	Intersectable *object;
375	#if BIDIRECTIONAL_RAY
376	object = (*ri).mRay->mOriginObject;
377
378	if (object && !object->Mailed())
379	{
380	++ pvsSize;
381	object->Mail();
382	}
383	#endif
384	object = (*ri).mRay->mTerminationObject;
385	if (object && !object->Mailed())
386	{
387	++ pvsSize;
388	object->Mail();
389	}
390	}
391	}
392
393	mPvsSize = pvsSize;
394	mValidPvs = true;
395	}
396	}
397
398
399	void
400	VspKdTree::Construct(VssRayContainer &rays,
401	AxisAlignedBox3 *forcedBoundingBox)
402	{
403	mStat.Start();
404
405	maxMemory = maxStaticMemory;
406
407	DEL_PTR(mRoot);
408
409	mRoot = new VspKdTreeLeaf(NULL, (int)rays.size());
410
411	// first construct a leaf that will get subdivide
412	VspKdTreeLeaf leaf = dynamic_cast<VspKdTreeLeaf >(mRoot);
413
414
415	mStat.nodes = 1;
416
417	mBox.Initialize();
418
419	for (VssRayContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
420	{
421	leaf->AddRay(RayInfo(*ri));
422
423	mBox.Include((*ri)->GetOrigin());
424	mBox.Include((*ri)->GetTermination());
425	}
426
427	if (forcedBoundingBox)
428	mBox = *forcedBoundingBox;
429
430	cout << "Bbox = " << mBox << endl;
431
432	mStat.rays = (int)leaf->mRays.size();
433	leaf->UpdatePvsSize();
434
435	mStat.initialPvsSize = leaf->GetPvsSize();
436
437	// Subdivide();
438	mRoot = Subdivide(TraversalData(leaf, mBox, 0));
439
440	if (splitCandidates)
441	{
442	// force realease of this vector
443	delete splitCandidates;
444	splitCandidates = new vector<SortableEntry>;
445	}
446
447	mStat.Stop();
448
449	mStat.Print(cout);
450	cout<<"#Total memory=" << GetMemUsage() << endl;
451	}
452
453
454
455	VspKdTreeNode *VspKdTree::Subdivide(const TraversalData &tdata)
456	{
457	VspKdTreeNode *result = NULL;
458
459	priority_queue<TraversalData> tStack;
460	// stack<TraversalData> tStack;
461
462	tStack.push(tdata);
463
464	AxisAlignedBox3 backBox;
465	AxisAlignedBox3 frontBox;
466
467	int lastMem = 0;
468	while (!tStack.empty())
469	{
470	float mem = GetMemUsage();
471
472	if ( lastMem/10 != ((int)mem)/10)
473	{
474	cout << mem << " MB" << endl;
475	}
476	lastMem = (int)mem;
477
478	if ( mem > maxMemory )
479	{
480	// count statistics on unprocessed leafs
481	while (!tStack.empty())
482	{
483	EvaluateLeafStats(tStack.top());
484	tStack.pop();
485	}
486	break;
487	}
488
489	TraversalData data = tStack.top();
490	tStack.pop();
491
492
493	VspKdTreeNode node = SubdivideNode((VspKdTreeLeaf ) data.mNode,
494	data.mBox, backBox, frontBox);
495	if (result == NULL)
496	result = node;
497
498	if (!node->IsLeaf())
499	{
500	VspKdTreeInterior interior = (VspKdTreeInterior ) node;
501
502	// push the children on the stack
503	tStack.push(TraversalData(interior->GetBack(), backBox, data.mDepth + 1));
504	tStack.push(TraversalData(interior->GetFront(), frontBox, data.mDepth + 1));
505	}
506	else
507	{
508	EvaluateLeafStats(data);
509	}
510	}
511
512	return result;
513	}
514
515
516	// returns selected plane for subdivision
517	int
518	VspKdTree::SelectPlane(VspKdTreeLeaf *leaf,
519	const AxisAlignedBox3 &box,
520	float &position,
521	int &raysBack,
522	int &raysFront,
523	int &pvsBack,
524	int &pvsFront)
525	{
526	int minDirDepth = 6;
527	int axis;
528	float costRatio;
529
530	if (splitType == ESplitRegular) {
531	costRatio = BestCostRatioRegular(leaf,
532	axis,
533	position,
534	raysBack,
535	raysFront,
536	pvsBack,
537	pvsFront);
538
539	}
540	else
541	{
542	if (splitType == ESplitHeuristic)
543	costRatio = BestCostRatioHeuristic(leaf,
544	axis,
545	position,
546	raysBack,
547	raysFront,
548	pvsBack,
549	pvsFront);
550	else {
551	cerr << "VspKdTree: Unknown split heuristics\n";
552	exit(1);
553	}
554	}
555
556	if (costRatio > mTermMaxCostRatio)
557	{
558	// cout<<"Too big cost ratio "<<costRatio<<endl;
559	return -1;
560	}
561
562	#if 0
563	cout<<
564	"pvs="<<leaf->mPvsSize<<
565	" rays="<<leaf->mRays.size()<<
566	" rc="<<leaf->GetAvgRayContribution()<<
567	" axis="<<axis<<endl;
568	#endif
569
570	return axis;
571	}
572
573
574
575
576	float
577	VspKdTree::EvalCostRatio(VspKdTreeLeaf *leaf,
578	const int axis,
579	const float position,
580	int &raysBack,
581	int &raysFront,
582	int &pvsBack,
583	int &pvsFront)
584	{
585	raysBack = 0;
586	raysFront = 0;
587	pvsFront = 0;
588	pvsBack = 0;
589
590	float newCost;
591
592	Intersectable::NewMail(3);
593
594	// eval pvs size
595	int pvsSize = leaf->GetPvsSize();
596
597	Intersectable::NewMail(3);
598
599	// this is the main ray classification loop!
600	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
601	ri != leaf->mRays.end(); ri++)
602	{
603	if (!(*ri).mRay->IsActive())
604	continue;
605
606	// determine the side of this ray with respect to the plane
607	int side = (ri).ComputeRayIntersection(axis, position, (ri).mRay->mT);
608	// (*ri).mRay->mSide = side;
609
610	if (side <= 0)
611	++ raysBack;
612
613	if (side >= 0)
614	++ raysFront;
615
616	AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
617	}
618
619	AxisAlignedBox3 box = GetBBox(leaf);
620
621	float minBox = box.Min(axis);
622	float maxBox = box.Max(axis);
623	float sizeBox = maxBox - minBox;
624
625	// float sum = raysBack(position - minBox) + raysFront(maxBox - position);
626	float sum = pvsBack(position - minBox) + pvsFront(maxBox - position);
627
628	newCost = ct_div_ci + sum/sizeBox;
629
630	// cout<<axis<<" "<<pvsSize<<" "<<pvsBack<<" "<<pvsFront<<endl;
631	// float oldCost = leaf->mRays.size();
632	float oldCost = (float)pvsSize;
633
634	float ratio = newCost / oldCost;
635	// cout<<"ratio="<<ratio<<endl;
636	return ratio;
637	}
638
639	float
640	VspKdTree::BestCostRatioRegular(VspKdTreeLeaf *leaf,
641	int &axis,
642	float &position,
643	int &raysBack,
644	int &raysFront,
645	int &pvsBack,
646	int &pvsFront)
647	{
648	int nRaysBack[6], nRaysFront[6];
649	int nPvsBack[6], nPvsFront[6];
650	float nPosition[6];
651	float nCostRatio[6];
652	int bestAxis = -1;
653
654	AxisAlignedBox3 sBox = GetBBox(leaf);
655
656	// int sAxis = box.Size().DrivingAxis();
657	int sAxis = sBox.Size().DrivingAxis();
658
659	bool onlyDrivingAxis = true;
660
661	for (axis = 0; axis < 6; ++ axis)
662	{
663	if (!onlyDrivingAxis \|\| axis == sAxis)
664	{
665	nPosition[axis] = (sBox.Min()[axis] + sBox.Max()[axis])*0.5f;
666
667	nCostRatio[axis] = EvalCostRatio(leaf,
668	axis,
669	nPosition[axis],
670	nRaysBack[axis],
671	nRaysFront[axis],
672	nPvsBack[axis],
673	nPvsFront[axis]);
674
675	if (bestAxis == -1)
676	bestAxis = axis;
677	else
678	if (nCostRatio[axis] < nCostRatio[bestAxis])
679	bestAxis = axis;
680	}
681	}
682
683	axis = bestAxis;
684	position = nPosition[bestAxis];
685
686	raysBack = nRaysBack[bestAxis];
687	raysFront = nRaysFront[bestAxis];
688
689	pvsBack = nPvsBack[bestAxis];
690	pvsFront = nPvsFront[bestAxis];
691
692	return nCostRatio[bestAxis];
693	}
694
695	float VspKdTree::BestCostRatioHeuristic(VspKdTreeLeaf *leaf,
696	int &axis,
697	float &position,
698	int &raysBack,
699	int &raysFront,
700	int &pvsBack,
701	int &pvsFront)
702	{
703	AxisAlignedBox3 box = GetBBox(leaf);
704	// AxisAlignedBox3 dirBox = GetDirBBox(node);
705
706	axis = box.Size().DrivingAxis();
707
708	SortSplitCandidates(leaf, axis);
709
710	// go through the lists, count the number of objects left and right
711	// and evaluate the following cost funcion:
712	// C = ct_div_ci + (qlrl + qrrr)/queries
713
714	int rl = 0, rr = (int)leaf->mRays.size();
715	int pl = 0, pr = leaf->GetPvsSize();
716	float minBox = box.Min(axis);
717	float maxBox = box.Max(axis);
718	float sizeBox = maxBox - minBox;
719
720	float minBand = minBox + 0.1f*(maxBox - minBox);
721	float maxBand = minBox + 0.9f*(maxBox - minBox);
722
723	float sum = rr*sizeBox;
724	float minSum = 1e20f;
725
726	Intersectable::NewMail();
727	// set all object as belonging to the fron pvs
728	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
729	ri != leaf->mRays.end(); ++ ri)
730	{
731	if ((*ri).mRay->IsActive())
732	{
733	Intersectable object = (ri).mRay->mTerminationObject;
734
735	if (object)
736	if (!object->Mailed())
737	{
738	object->Mail();
739	object->mCounter = 1;
740	}
741	else
742	++ object->mCounter;
743	}
744	}
745
746	Intersectable::NewMail();
747
748	for (vector<SortableEntry>::const_iterator ci = splitCandidates->begin();
749	ci < splitCandidates->end(); ++ ci)
750	{
751	VssRay *ray;
752
753	switch ((*ci).type)
754	{
755	case SortableEntry::ERayMin:
756	{
757	++ rl;
758	ray = (VssRay ) (ci).data;
759	Intersectable *object = ray->mTerminationObject;
760	if (object && !object->Mailed())
761	{
762	object->Mail();
763	++ pl;
764	}
765	break;
766	}
767	case SortableEntry::ERayMax:
768	{
769	-- rr;
770
771	ray = (VssRay ) (ci).data;
772	Intersectable *object = ray->mTerminationObject;
773
774	if (object)
775	{
776	if (-- object->mCounter == 0)
777	-- pr;
778	}
779
780	break;
781	}
782	}
783
784	if ((ci).value > minBand && (ci).value < maxBand)
785	{
786	sum = pl((ci).value - minBox) + pr(maxBox - (ci).value);
787
788	// cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
789	// cout<<"cost= "<<sum<<endl;
790
791	if (sum < minSum)
792	{
793	minSum = sum;
794	position = (*ci).value;
795
796	raysBack = rl;
797	raysFront = rr;
798
799	pvsBack = pl;
800	pvsFront = pr;
801
802	}
803	}
804	}
805
806	float oldCost = (float)leaf->GetPvsSize();
807	float newCost = ct_div_ci + minSum / sizeBox;
808	float ratio = newCost / oldCost;
809
810	// cout<<"===================="<<endl;
811	// cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
812	// <<"\t q=("<<queriesBack<<","<<queriesFront<<")\t r=("<<raysBack<<","<<raysFront<<")"<<endl;
813
814	return ratio;
815	}
816
817	void VspKdTree::SortSplitCandidates(VspKdTreeLeaf *node,
818	const int axis)
819	{
820	splitCandidates->clear();
821
822	int requestedSize = 2 * (int)(node->mRays.size());
823	// creates a sorted split candidates array
824	if (splitCandidates->capacity() > 500000 &&
825	requestedSize < (int)(splitCandidates->capacity()/10) )
826	{
827	delete splitCandidates;
828	splitCandidates = new vector<SortableEntry>;
829	}
830
831	splitCandidates->reserve(requestedSize);
832
833	// insert all queries
834	for(RayInfoContainer::const_iterator ri = node->mRays.begin();
835	ri < node->mRays.end(); ++ ri)
836	{
837	bool positive = (*ri).mRay->HasPosDir(axis);
838	splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
839	(ri).ExtrapOrigin(axis), (void )&*ri));
840
841	splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
842	(ri).ExtrapTermination(axis), (void )&*ri));
843	}
844
845	stable_sort(splitCandidates->begin(), splitCandidates->end());
846	}
847
848
849	void VspKdTree::EvaluateLeafStats(const TraversalData &data)
850	{
851	// the node became a leaf -> evaluate stats for leafs
852	VspKdTreeLeaf leaf = dynamic_cast<VspKdTreeLeaf >(data.mNode);
853
854	if (data.mDepth >= mTermMaxDepth)
855	++ mStat.maxDepthNodes;
856
857	// if ( (int)(leaf->mRays.size()) < termMinCost)
858	// stat.minCostNodes++;
859	if (leaf->GetPvsSize() < mTermMinPvs)
860	++ mStat.minPvsNodes;
861
862	if (leaf->GetPvsSize() < mTermMinRays)
863	++ mStat.minRaysNodes;
864
865	if (0 && leaf->GetAvgRayContribution() > mTermMaxRayContribution)
866	++ mStat.maxRayContribNodes;
867
868	if (SqrMagnitude(data.mBox.Size()) <= mTermMinSize)
869	++ mStat.minSizeNodes;
870
871	// if ((int)(leaf->mRays.size()) > stat.maxRayRefs)
872	// mStat.maxRayRefs = (int)leaf->mRays.size();
873	}
874
875
876	inline bool VspKdTree::TerminationCriteriaMet(const VspKdTreeLeaf *leaf,
877	const AxisAlignedBox3 &box) const
878	{
879	return ((leaf->GetPvsSize() < mTermMinPvs) \|\| (leaf->mRays.size() < mTermMinRays) \|\|
880	// (leaf->GetAvgRayContribution() > termMaxRayContribution ) \|\|
881	(leaf->mDepth >= mTermMaxDepth) \|\| SqrMagnitude(box.Size()) <= mTermMinSize);
882	}
883
884
885	VspKdTreeNode VspKdTree::SubdivideNode(VspKdTreeLeaf leaf,
886	const AxisAlignedBox3 &box,
887	AxisAlignedBox3 &backBBox,
888	AxisAlignedBox3 &frontBBox)
889	{
890	if (TerminationCriteriaMet(leaf, box))
891	{
892
893	#if 0
894	if (leaf->mDepth >= termMaxDepth) {
895	cout<<"Warning: max depth reached depth="<<(int)leaf->mDepth<<" rays="<<leaf->mRays.size()<<endl;
896	cout<<"Bbox: "<<GetBBox(leaf)<<" dirbbox:"<<GetDirBBox(leaf)<<endl;
897	}
898	#endif
899
900	return leaf;
901	}
902
903	float position;
904	// first count ray sides
905	int raysBack;
906	int raysFront;
907	int pvsBack;
908	int pvsFront;
909
910	// select subdivision axis
911	int axis = SelectPlane( leaf, box, position, raysBack, raysFront, pvsBack, pvsFront);
912
913	// cout<<"rays back="<<raysBack<<" rays front="<<raysFront<<" pvs back="<<pvsBack<<" pvs front="<<
914	// pvsFront<<endl;
915
916	if (axis == -1)
917	{
918	return leaf;
919	}
920
921	mStat.nodes += 2;
922	//++ mStat.splits[axis];
923
924	// add the new nodes to the tree
925	VspKdTreeInterior *node = new VspKdTreeInterior(leaf->mParent);
926
927	node->mAxis = axis;
928	node->mPosition = position;
929	node->mBox = box;
930
931	backBBox = box;
932	frontBBox = box;
933
934	VspKdTreeLeaf *back = new VspKdTreeLeaf(node, raysBack);
935	back->SetPvsSize(pvsBack);
936	VspKdTreeLeaf *front = new VspKdTreeLeaf(node, raysFront);
937	front->SetPvsSize(pvsFront);
938
939	// replace a link from node's parent
940	if (leaf->mParent)
941	leaf->mParent->ReplaceChildLink(leaf, node);
942	// and setup child links
943	node->SetupChildLinks(back, front);
944
945	if (axis <= VspKdTreeNode::SPLIT_Z)
946	{
947	backBBox.SetMax(axis, position);
948	frontBBox.SetMin(axis, position);
949
950	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
951	ri != leaf->mRays.end(); ++ ri)
952	{
953	if ((*ri).mRay->IsActive())
954	{
955	// first unref ray from the former leaf
956	(*ri).mRay->Unref();
957
958	// determine the side of this ray with respect to the plane
959	int side = node->ComputeRayIntersection(ri, (ri).mRay->mT);
960
961	if (side == 0)
962	{
963	if ((*ri).mRay->HasPosDir(axis))
964	{
965	back->AddRay(RayInfo((*ri).mRay,
966	(*ri).mMinT,
967	(*ri).mRay->mT));
968	front->AddRay(RayInfo((*ri).mRay,
969	(*ri).mRay->mT,
970	(*ri).mMaxT));
971	}
972	else
973	{
974	back->AddRay(RayInfo((*ri).mRay,
975	(*ri).mRay->mT,
976	(*ri).mMaxT));
977	front->AddRay(RayInfo((*ri).mRay,
978	(*ri).mMinT,
979	(*ri).mRay->mT));
980	}
981	}
982	else
983	if (side == 1)
984	front->AddRay(*ri);
985	else
986	back->AddRay(*ri);
987	} else
988	(*ri).mRay->Unref();
989	}
990	}
991	else
992	{
993	// rays front/back
994
995	for (RayInfoContainer::iterator ri = leaf->mRays.begin();
996	ri != leaf->mRays.end(); ++ ri)
997	{
998	if ((*ri).mRay->IsActive())
999	{
1000	// first unref ray from the former leaf
1001	(*ri).mRay->Unref();
1002
1003	int side;
1004	if ((*ri).mRay->GetDirParametrization(axis - 3) > position)
1005	side = 1;
1006	else
1007	side = -1;
1008
1009	if (side == 1)
1010	front->AddRay(*ri);
1011	else
1012	back->AddRay(*ri);
1013	}
1014	else
1015	(*ri).mRay->Unref();
1016	}
1017	}
1018
1019	// update stats
1020	mStat.rayRefs -= (int)leaf->mRays.size();
1021	mStat.rayRefs += raysBack + raysFront;
1022
1023	DEL_PTR(leaf);
1024
1025	return node;
1026	}
1027
1028	int VspKdTree::ReleaseMemory(const int time)
1029	{
1030	stack<VspKdTreeNode *> tstack;
1031
1032	// find a node in the tree which subtree will be collapsed
1033	int maxAccessTime = time - accessTimeThreshold;
1034	int released = 0;
1035
1036	tstack.push(mRoot);
1037
1038	while (!tstack.empty())
1039	{
1040	VspKdTreeNode *node = tstack.top();
1041	tstack.pop();
1042
1043	if (!node->IsLeaf())
1044	{
1045	VspKdTreeInterior in = dynamic_cast<VspKdTreeInterior >(node);
1046	// cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
1047	if (in->mDepth >= minCollapseDepth && in->mLastAccessTime <= maxAccessTime)
1048	{
1049	released = CollapseSubtree(node, time);
1050	break;
1051	}
1052	if (in->GetBack()->GetAccessTime() < in->GetFront()->GetAccessTime())
1053	{
1054	tstack.push(in->GetFront());
1055	tstack.push(in->GetBack());
1056	}
1057	else
1058	{
1059	tstack.push(in->GetBack());
1060	tstack.push(in->GetFront());
1061	}
1062	}
1063	}
1064
1065	while (tstack.empty())
1066	{
1067	// could find node to collaps...
1068	// cout<<"Could not find a node to release "<<endl;
1069	break;
1070	}
1071
1072	return released;
1073	}
1074
1075
1076
1077
1078	VspKdTreeNode VspKdTree::SubdivideLeaf(VspKdTreeLeaf leaf,
1079	const float sizeThreshold)
1080	{
1081	VspKdTreeNode *node = leaf;
1082
1083	AxisAlignedBox3 leafBBox = GetBBox(leaf);
1084
1085	static int pass = 0;
1086	++ pass;
1087
1088	// check if we should perform a dynamic subdivision of the leaf
1089	if (// leaf->mRays.size() > (unsigned)termMinCost &&
1090	(leaf->GetPvsSize() >= mTermMinPvs) &&
1091	(SqrMagnitude(leafBBox.Size()) > sizeThreshold) )
1092	{
1093	// memory check and realese...
1094	if (GetMemUsage() > maxTotalMemory)
1095	ReleaseMemory(pass);
1096
1097	AxisAlignedBox3 backBBox, frontBBox;
1098
1099	// subdivide the node
1100	node = SubdivideNode(leaf, leafBBox, backBBox, frontBBox);
1101	}
1102	return node;
1103	}
1104
1105
1106
1107	void
1108	VspKdTree::UpdateRays(VssRayContainer &remove,
1109	VssRayContainer &add)
1110	{
1111	VspKdTreeLeaf::NewMail();
1112
1113	// schedule rays for removal
1114	for(VssRayContainer::const_iterator ri = remove.begin();
1115	ri != remove.end(); ++ ri)
1116	{
1117	(*ri)->ScheduleForRemoval();
1118	}
1119
1120	int inactive = 0;
1121
1122	for (VssRayContainer::const_iterator ri = remove.begin(); ri != remove.end(); ++ ri)
1123	{
1124	if ((*ri)->ScheduledForRemoval())
1125	// RemoveRay(*ri, NULL, false);
1126	// !!! BUG - with true it does not work correctly - aggreated delete
1127	RemoveRay(*ri, NULL, true);
1128	else
1129	++ inactive;
1130	}
1131
1132	// cout<<"all/inactive"<<remove.size()<<"/"<<inactive<<endl;
1133
1134	for(VssRayContainer::const_iterator ri = add.begin(); ri != add.end(); ++ ri)
1135	{
1136	AddRay(*ri);
1137	}
1138	}
1139
1140
1141	void VspKdTree::RemoveRay(VssRay *ray,
1142	vector<VspKdTreeLeaf > affectedLeaves,
1143	const bool removeAllScheduledRays)
1144	{
1145	stack<RayTraversalData> tstack;
1146
1147	tstack.push(RayTraversalData(mRoot, RayInfo(ray)));
1148
1149	RayTraversalData data;
1150
1151	// cout<<"Number of ray refs = "<<ray->RefCount()<<endl;
1152	while (!tstack.empty())
1153	{
1154	data = tstack.top();
1155	tstack.pop();
1156
1157	if (!data.mNode->IsLeaf())
1158	{
1159	// split the set of rays in two groups intersecting the
1160	// two subtrees
1161	TraverseInternalNode(data, tstack);
1162	}
1163	else
1164	{
1165	// remove the ray from the leaf
1166	// find the ray in the leaf and swap it with the last ray...
1167	VspKdTreeLeaf leaf = (VspKdTreeLeaf )data.mNode;
1168
1169	if (!leaf->Mailed())
1170	{
1171	leaf->Mail();
1172
1173	if (affectedLeaves)
1174	affectedLeaves->push_back(leaf);
1175
1176	if (removeAllScheduledRays)
1177	{
1178	int tail = (int)leaf->mRays.size() - 1;
1179
1180	for (int i=0; i < (int)(leaf->mRays.size()); ++ i)
1181	{
1182	if (leaf->mRays[i].mRay->ScheduledForRemoval())
1183	{
1184	// find a ray to replace it with
1185	while (tail >= i && leaf->mRays[tail].mRay->ScheduledForRemoval())
1186	{
1187	++ mStat.removedRayRefs;
1188	leaf->mRays[tail].mRay->Unref();
1189	leaf->mRays.pop_back();
1190
1191	-- tail;
1192	}
1193
1194	if (tail < i)
1195	break;
1196
1197	++ mStat.removedRayRefs;
1198
1199	leaf->mRays[i].mRay->Unref();
1200	leaf->mRays[i] = leaf->mRays[tail];
1201	leaf->mRays.pop_back();
1202	-- tail;
1203	}
1204	}
1205	}
1206	}
1207
1208	if (!removeAllScheduledRays)
1209	for (int i=0; i < (int)leaf->mRays.size(); i++)
1210	{
1211	if (leaf->mRays[i].mRay == ray)
1212	{
1213	++ mStat.removedRayRefs;
1214	ray->Unref();
1215	leaf->mRays[i] = leaf->mRays[leaf->mRays.size() - 1];
1216	leaf->mRays.pop_back();
1217	// check this ray again
1218	break;
1219	}
1220	}
1221	}
1222	}
1223
1224	if (ray->RefCount() != 0)
1225	{
1226	cerr << "Error: Number of remaining refs = " << ray->RefCount() << endl;
1227	exit(1);
1228	}
1229
1230	}
1231
1232	void VspKdTree::AddRay(VssRay *ray)
1233	{
1234	stack<RayTraversalData> tstack;
1235
1236	tstack.push(RayTraversalData(mRoot, RayInfo(ray)));
1237
1238	RayTraversalData data;
1239
1240	while (!tstack.empty())
1241	{
1242	data = tstack.top();
1243	tstack.pop();
1244
1245	if (!data.mNode->IsLeaf())
1246	{
1247	TraverseInternalNode(data, tstack);
1248	}
1249	else
1250	{
1251	// remove the ray from the leaf
1252	// find the ray in the leaf and swap it with the last ray
1253	VspKdTreeLeaf leaf = dynamic_cast<VspKdTreeLeaf >(data.mNode);
1254	leaf->AddRay(data.mRayData);
1255	++ mStat.addedRayRefs;
1256	}
1257	}
1258	}
1259
1260	void VspKdTree::TraverseInternalNode(RayTraversalData &data,
1261	stack<RayTraversalData> &tstack)
1262	{
1263	VspKdTreeInterior in = (VspKdTreeInterior ) data.mNode;
1264
1265	if (in->mAxis <= VspKdTreeNode::SPLIT_Z)
1266	{
1267	// determine the side of this ray with respect to the plane
1268	int side = in->ComputeRayIntersection(data.mRayData, data.mRayData.mRay->mT);
1269
1270	if (side == 0)
1271	{
1272	if (data.mRayData.mRay->HasPosDir(in->mAxis))
1273	{
1274	tstack.push(RayTraversalData(in->GetBack(),
1275	RayInfo(data.mRayData.mRay, data.mRayData.mMinT, data.mRayData.mRay->mT)));
1276
1277	tstack.push(RayTraversalData(in->GetFront(),
1278	RayInfo(data.mRayData.mRay, data.mRayData.mRay->mT, data.mRayData.mMaxT)));
1279
1280	}
1281	else
1282	{
1283	tstack.push(RayTraversalData(in->GetBack(),
1284	RayInfo(data.mRayData.mRay,
1285	data.mRayData.mRay->mT,
1286	data.mRayData.mMaxT)));
1287	tstack.push(RayTraversalData(in->GetFront(),
1288	RayInfo(data.mRayData.mRay,
1289	data.mRayData.mMinT,
1290	data.mRayData.mRay->mT)));
1291	}
1292	}
1293	else
1294	if (side == 1)
1295	tstack.push(RayTraversalData(in->GetFront(), data.mRayData));
1296	else
1297	tstack.push(RayTraversalData(in->GetBack(), data.mRayData));
1298	}
1299	else
1300	{
1301	// directional split
1302	if (data.mRayData.mRay->GetDirParametrization(in->mAxis - 3) > in->mPosition)
1303	tstack.push(RayTraversalData(in->GetFront(), data.mRayData));
1304	else
1305	tstack.push(RayTraversalData(in->GetBack(), data.mRayData));
1306	}
1307	}
1308
1309
1310	int VspKdTree::CollapseSubtree(VspKdTreeNode *sroot, const int time)
1311	{
1312	// first count all rays in the subtree
1313	// use mail 1 for this purpose
1314	stack<VspKdTreeNode *> tstack;
1315
1316	int rayCount = 0;
1317	int totalRayCount = 0;
1318	int collapsedNodes = 0;
1319
1320	#if DEBUG_COLLAPSE
1321	cout << "Collapsing subtree" << endl;
1322	cout << "acessTime=" << sroot->GetAccessTime() << endl;
1323	cout << "depth=" << (int)sroot->depth << endl;
1324	#endif
1325
1326	// tstat.collapsedSubtrees++;
1327	// tstat.collapseDepths += (int)sroot->depth;
1328	// tstat.collapseAccessTimes += time - sroot->GetAccessTime();
1329	tstack.push(sroot);
1330	VssRay::NewMail();
1331
1332	while (!tstack.empty())
1333	{
1334	++ collapsedNodes;
1335
1336	VspKdTreeNode *node = tstack.top();
1337	tstack.pop();
1338	if (node->IsLeaf())
1339	{
1340	VspKdTreeLeaf leaf = (VspKdTreeLeaf ) node;
1341
1342	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
1343	ri != leaf->mRays.end(); ++ ri)
1344	{
1345	++ totalRayCount;
1346
1347	if ((ri).mRay->IsActive() && !(ri).mRay->Mailed())
1348	{
1349	(*ri).mRay->Mail();
1350	++ rayCount;
1351	}
1352	}
1353	}
1354	else
1355	{
1356	tstack.push(((VspKdTreeInterior *)node)->GetFront());
1357	tstack.push(((VspKdTreeInterior *)node)->GetBack());
1358	}
1359	}
1360
1361	VssRay::NewMail();
1362
1363	// create a new node that will hold the rays
1364	VspKdTreeLeaf *newLeaf = new VspKdTreeLeaf(sroot->mParent, rayCount);
1365
1366	if (newLeaf->mParent)
1367	newLeaf->mParent->ReplaceChildLink(sroot, newLeaf);
1368
1369	tstack.push(sroot);
1370
1371	while (!tstack.empty())
1372	{
1373	VspKdTreeNode *node = tstack.top();
1374	tstack.pop();
1375
1376	if (node->IsLeaf())
1377	{
1378	VspKdTreeLeaf leaf = dynamic_cast<VspKdTreeLeaf >(node);
1379
1380	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
1381	ri != leaf->mRays.end(); ++ ri)
1382	{
1383	// unref this ray from the old node
1384	if ((*ri).mRay->IsActive())
1385	{
1386	(*ri).mRay->Unref();
1387	if (!(*ri).mRay->Mailed())
1388	{
1389	(*ri).mRay->Mail();
1390	newLeaf->AddRay(*ri);
1391	}
1392	}
1393	else
1394	(*ri).mRay->Unref();
1395	}
1396	}
1397	else
1398	{
1399	VspKdTreeInterior *interior =
1400	dynamic_cast<VspKdTreeInterior *>(node);
1401	tstack.push(interior->GetBack());
1402	tstack.push(interior->GetFront());
1403	}
1404	}
1405
1406	// delete the node and all its children
1407	DEL_PTR(sroot);
1408
1409	// for(VspKdTreeNode::SRayContainer::iterator ri = newleaf->mRays.begin();
1410	// ri != newleaf->mRays.end(); ++ ri)
1411	// (*ri).ray->UnMail(2);
1412
1413	#if DEBUG_COLLAPSE
1414	cout<<"Total memory before="<<GetMemUsage()<<endl;
1415	#endif
1416
1417	mStat.nodes -= collapsedNodes - 1;
1418	mStat.rayRefs -= totalRayCount - rayCount;
1419
1420	#if DEBUG_COLLAPSE
1421	cout << "collapsed nodes" << collapsedNodes << endl;
1422	cout << "collapsed rays" << totalRayCount - rayCount << endl;
1423	cout << "Total memory after=" << GetMemUsage() << endl;
1424	cout << "================================" << endl;
1425	#endif
1426
1427	// tstat.collapsedNodes += collapsedNodes;
1428	// tstat.collapsedRays += totalRayCount - rayCount;
1429	return totalRayCount - rayCount;
1430	}
1431
1432
1433	int VspKdTree::GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const
1434	{
1435	stack<VspKdTreeNode *> tstack;
1436	tstack.push(mRoot);
1437
1438	Intersectable::NewMail();
1439	int pvsSize = 0;
1440
1441	while (!tstack.empty())
1442	{
1443	VspKdTreeNode *node = tstack.top();
1444	tstack.pop();
1445
1446	if (node->IsLeaf())
1447	{
1448	VspKdTreeLeaf leaf = (VspKdTreeLeaf )node;
1449	for (RayInfoContainer::iterator ri = leaf->mRays.begin();
1450	ri != leaf->mRays.end(); ++ ri)
1451	{
1452	if ((*ri).mRay->IsActive())
1453	{
1454	Intersectable *object;
1455	#if BIDIRECTIONAL_RAY
1456	object = (*ri).mRay->mOriginObject;
1457
1458	if (object && !object->Mailed())
1459	{
1460	++ pvsSize;
1461	object->Mail();
1462	}
1463	#endif
1464	object = (*ri).mRay->mTerminationObject;
1465	if (object && !object->Mailed())
1466	{
1467	++ pvsSize;
1468	object->Mail();
1469	}
1470	}
1471	}
1472	}
1473	else
1474	{
1475	VspKdTreeInterior in = dynamic_cast<VspKdTreeInterior >(node);
1476
1477	if (in->mAxis < 3)
1478	{
1479	if (box.Max(in->mAxis) >= in->mPosition)
1480	tstack.push(in->GetFront());
1481
1482	if (box.Min(in->mAxis) <= in->mPosition)
1483	tstack.push(in->GetBack());
1484	}
1485	else
1486	{
1487	// both nodes for directional splits
1488	tstack.push(in->GetFront());
1489	tstack.push(in->GetBack());
1490	}
1491	}
1492	}
1493
1494	return pvsSize;
1495	}
1496
1497	void VspKdTree::GetRayContributionStatistics(float &minRayContribution,
1498	float &maxRayContribution,
1499	float &avgRayContribution)
1500	{
1501	stack<VspKdTreeNode *> tstack;
1502	tstack.push(mRoot);
1503
1504	minRayContribution = 1.0f;
1505	maxRayContribution = 0.0f;
1506
1507	float sumRayContribution = 0.0f;
1508	int leaves = 0;
1509
1510	while (!tstack.empty())
1511	{
1512	VspKdTreeNode *node = tstack.top();
1513	tstack.pop();
1514	if (node->IsLeaf())
1515	{
1516	leaves++;
1517	VspKdTreeLeaf leaf = (VspKdTreeLeaf )node;
1518	float c = leaf->GetAvgRayContribution();
1519
1520	if (c > maxRayContribution)
1521	maxRayContribution = c;
1522	if (c < minRayContribution)
1523	minRayContribution = c;
1524	sumRayContribution += c;
1525
1526	}
1527	else {
1528	VspKdTreeInterior in = (VspKdTreeInterior )node;
1529	// both nodes for directional splits
1530	tstack.push(in->GetFront());
1531	tstack.push(in->GetBack());
1532	}
1533	}
1534
1535	cout << "sum=" << sumRayContribution << endl;
1536	cout << "leaves=" << leaves << endl;
1537	avgRayContribution = sumRayContribution/(float)leaves;
1538	}
1539
1540
1541	int VspKdTree::GenerateRays(const float ratioPerLeaf,
1542	SimpleRayContainer &rays)
1543	{
1544	stack<VspKdTreeNode *> tstack;
1545	tstack.push(mRoot);
1546
1547	while (!tstack.empty())
1548	{
1549	VspKdTreeNode *node = tstack.top();
1550	tstack.pop();
1551
1552	if (node->IsLeaf())
1553	{
1554	VspKdTreeLeaf leaf = (VspKdTreeLeaf )node;
1555	float c = leaf->GetAvgRayContribution();
1556	int num = (int)(c*ratioPerLeaf + 0.5);
1557	// cout<<num<<" ";
1558
1559	for (int i=0; i < num; i++)
1560	{
1561	Vector3 origin = GetBBox(leaf).GetRandomPoint();
1562	/*Vector3 dirVector = GetDirBBox(leaf).GetRandomPoint();
1563	Vector3 direction = Vector3(sin(dirVector.x), sin(dirVector.y), cos(dirVector.x));
1564	//cout<<"dir vector.x="<<dirVector.x<<"direction'.x="<<atan2(direction.x, direction.y)<<endl;
1565	rays.push_back(SimpleRay(origin, direction));*/
1566	}
1567
1568	}
1569	else
1570	{
1571	VspKdTreeInterior *in =
1572	dynamic_cast<VspKdTreeInterior *>(node);
1573	// both nodes for directional splits
1574	tstack.push(in->GetFront());
1575	tstack.push(in->GetBack());
1576	}
1577	}
1578
1579	return (int)rays.size();
1580	}
1581
1582
1583	float VspKdTree::GetAvgPvsSize()
1584	{
1585	stack<VspKdTreeNode *> tstack;
1586	tstack.push(mRoot);
1587
1588	int sumPvs = 0;
1589	int leaves = 0;
1590
1591	while (!tstack.empty())
1592	{
1593	VspKdTreeNode *node = tstack.top();
1594	tstack.pop();
1595
1596	if (node->IsLeaf())
1597	{
1598	VspKdTreeLeaf leaf = (VspKdTreeLeaf )node;
1599	// update pvs size
1600	leaf->UpdatePvsSize();
1601	sumPvs += leaf->GetPvsSize();
1602	leaves++;
1603	}
1604	else
1605	{
1606	VspKdTreeInterior in = (VspKdTreeInterior )node;
1607	// both nodes for directional splits
1608	tstack.push(in->GetFront());
1609	tstack.push(in->GetBack());
1610	}
1611	}
1612
1613	return sumPvs / (float)leaves;
1614	}
1615
1616	VspKdTreeNode *VspKdTree::GetRoot() const
1617	{
1618	return mRoot;
1619	}
1620
1621	AxisAlignedBox3 VspKdTree::GetBBox(VspKdTreeNode *node) const
1622	{
1623	if (node->mParent == NULL)
1624	return mBox;
1625
1626	if (!node->IsLeaf())
1627	return (dynamic_cast<VspKdTreeInterior *>(node))->mBox;
1628
1629	if (node->mParent->mAxis >= 3)
1630	return node->mParent->mBox;
1631
1632	AxisAlignedBox3 box(node->mParent->mBox);
1633	if (node->mParent->mFront == node)
1634	box.SetMin(node->mParent->mAxis, node->mParent->mPosition);
1635	else
1636	box.SetMax(node->mParent->mAxis, node->mParent->mPosition);
1637
1638	return box;
1639	}
1640
1641	int VspKdTree::GetRootPvsSize() const
1642	{
1643	return GetPvsSize(mRoot, mBox);
1644	}
1645
1646	const VspKdStatistics &VspKdTree::GetStatistics() const
1647	{
1648	return mStat;
1649	}
1650
1651	void VspKdTree::AddRays(VssRayContainer &add)
1652	{
1653	VssRayContainer remove;
1654	UpdateRays(remove, add);
1655	}
1656
1657	// return memory usage in MB
1658	float VspKdTree::GetMemUsage() const
1659	{
1660	return
1661	(sizeof(VspKdTree) +
1662	mStat.Leaves() * sizeof(VspKdTreeLeaf) +
1663	mStat.Interior() * sizeof(VspKdTreeInterior) +
1664	mStat.rayRefs * sizeof(RayInfo)) / (1024.0f * 1024.0f);
1665	}
1666
1667	float VspKdTree::GetRayMemUsage() const
1668	{
1669	return mStat.rays * (sizeof(VssRay))/(1024.0f * 1024.0f);
1670	}

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

Download in other formats: