Context Navigation

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

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

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

Download in other formats: