Context Navigation

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

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

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

Download in other formats: