Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/VssTree.cpp @ 430

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

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

Download in other formats: