Context Navigation

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

Revision 420, 38.1 KB checked in by mattausch, 19 years ago (diff)

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

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

Download in other formats: