Context Navigation

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

Revision 426, 39.5 KB checked in by mattausch, 19 years ago (diff)
fixed ray bug in vspkdtree added visualizations

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

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

Download in other formats: