Context Navigation

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

Revision 427, 41.1 KB checked in by bittner, 19 years ago (diff)
vss updates

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	// determine the side of this ray with respect to the plane
989	int side = node->ComputeRayIntersection(ri, (ri).mRay->mT);
990
991	if (side == 0) {
992	if ((*ri).mRay->HasPosDir(axis)) {
993	back->AddRay(VssTreeNode::RayInfo((*ri).mRay,
994	(*ri).mMinT,
995	(*ri).mRay->mT)
996	);
997	front->AddRay(VssTreeNode::RayInfo((*ri).mRay,
998	(*ri).mRay->mT,
999	(*ri).mMaxT));
1000	} else {
1001	back->AddRay(VssTreeNode::RayInfo((*ri).mRay,
1002	(*ri).mRay->mT,
1003	(*ri).mMaxT));
1004	front->AddRay(VssTreeNode::RayInfo((*ri).mRay,
1005	(*ri).mMinT,
1006	(*ri).mRay->mT));
1007	}
1008	} else
1009	if (side == 1)
1010	front->AddRay(*ri);
1011	else
1012	back->AddRay(*ri);
1013	} else
1014	(*ri).mRay->Unref();
1015	}
1016	} else {
1017	// rays front/back
1018
1019
1020	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
1021	ri != leaf->rays.end();
1022	ri++) {
1023	if ((*ri).mRay->IsActive()) {
1024	// first unref ray from the former leaf
1025	(*ri).mRay->Unref();
1026
1027	int side;
1028	if ((*ri).mRay->GetDirParametrization(axis - 3) > position)
1029	side = 1;
1030	else
1031	side = -1;
1032
1033	if (side == 1)
1034	front->AddRay(*ri);
1035	else
1036	back->AddRay(*ri);
1037
1038	} else
1039	(*ri).mRay->Unref();
1040	}
1041	}
1042
1043	// update stats
1044	stat.rayRefs -= leaf->rays.size();
1045	stat.rayRefs += raysBack + raysFront;
1046
1047
1048	delete leaf;
1049	return node;
1050	}
1051
1052
1053
1054
1055
1056
1057	int
1058	VssTree::ReleaseMemory(const int time)
1059	{
1060	stack<VssTreeNode *> tstack;
1061
1062	// find a node in the tree which subtree will be collapsed
1063	int maxAccessTime = time - accessTimeThreshold;
1064	int released;
1065
1066	tstack.push(root);
1067
1068	while (!tstack.empty()) {
1069	VssTreeNode *node = tstack.top();
1070	tstack.pop();
1071
1072
1073	if (!node->IsLeaf()) {
1074	VssTreeInterior in = (VssTreeInterior )node;
1075	// cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
1076	if (in->depth >= minCollapseDepth &&
1077	in->lastAccessTime <= maxAccessTime) {
1078	released = CollapseSubtree(node, time);
1079	break;
1080	}
1081
1082	if (in->back->GetAccessTime() <
1083	in->front->GetAccessTime()) {
1084	tstack.push(in->front);
1085	tstack.push(in->back);
1086	} else {
1087	tstack.push(in->back);
1088	tstack.push(in->front);
1089	}
1090	}
1091	}
1092
1093	while (tstack.empty()) {
1094	// could find node to collaps...
1095	// cout<<"Could not find a node to release "<<endl;
1096	break;
1097	}
1098
1099	return released;
1100	}
1101
1102
1103
1104
1105	VssTreeNode *
1106	VssTree::SubdivideLeaf(
1107	VssTreeLeaf *leaf
1108	)
1109	{
1110	VssTreeNode *node = leaf;
1111
1112	AxisAlignedBox3 leafBBox = GetBBox(leaf);
1113
1114	static int pass = 0;
1115	pass ++;
1116
1117	// check if we should perform a dynamic subdivision of the leaf
1118	if (!TerminationCriteriaSatisfied(leaf)) {
1119
1120	// memory check and realese...
1121	if (GetMemUsage() > maxTotalMemory) {
1122	ReleaseMemory( pass );
1123	}
1124
1125	AxisAlignedBox3 backBBox, frontBBox;
1126
1127	// subdivide the node
1128	node =
1129	SubdivideNode(leaf,
1130	leafBBox,
1131	backBBox,
1132	frontBBox
1133	);
1134	}
1135
1136	return node;
1137	}
1138
1139
1140
1141	void
1142	VssTree::UpdateRays(VssRayContainer &remove,
1143	VssRayContainer &add
1144	)
1145	{
1146	VssTreeLeaf::NewMail();
1147
1148	// schedule rays for removal
1149	for(VssRayContainer::const_iterator ri = remove.begin();
1150	ri != remove.end();
1151	ri++) {
1152	(*ri)->ScheduleForRemoval();
1153	}
1154
1155	int inactive=0;
1156
1157	for(VssRayContainer::const_iterator ri = remove.begin();
1158	ri != remove.end();
1159	ri++) {
1160	if ((*ri)->ScheduledForRemoval())
1161	// RemoveRay(*ri, NULL, false);
1162	// !!! BUG - with true it does not work correctly - aggreated delete
1163	RemoveRay(*ri, NULL, true);
1164	else
1165	inactive++;
1166	}
1167
1168
1169	// cout<<"all/inactive"<<remove.size()<<"/"<<inactive<<endl;
1170
1171	for(VssRayContainer::const_iterator ri = add.begin();
1172	ri != add.end();
1173	ri++) {
1174	VssTreeNode::RayInfo info(*ri);
1175	if (ClipRay(info, bbox))
1176	AddRay(info);
1177	}
1178	}
1179
1180
1181	void
1182	VssTree::RemoveRay(VssRay *ray,
1183	vector<VssTreeLeaf > affectedLeaves,
1184	const bool removeAllScheduledRays
1185	)
1186	{
1187
1188	stack<RayTraversalData> tstack;
1189
1190	tstack.push(RayTraversalData(root, VssTreeNode::RayInfo(ray)));
1191
1192	RayTraversalData data;
1193
1194	// cout<<"Number of ray refs = "<<ray->RefCount()<<endl;
1195
1196	while (!tstack.empty()) {
1197	data = tstack.top();
1198	tstack.pop();
1199
1200	if (!data.node->IsLeaf()) {
1201	// split the set of rays in two groups intersecting the
1202	// two subtrees
1203
1204	TraverseInternalNode(data, tstack);
1205
1206	} else {
1207	// remove the ray from the leaf
1208	// find the ray in the leaf and swap it with the last ray...
1209	VssTreeLeaf leaf = (VssTreeLeaf )data.node;
1210
1211	if (!leaf->Mailed()) {
1212	leaf->Mail();
1213	if (affectedLeaves)
1214	affectedLeaves->push_back(leaf);
1215
1216	if (removeAllScheduledRays) {
1217	int tail = leaf->rays.size()-1;
1218
1219	for (int i=0; i < (int)(leaf->rays.size()); i++) {
1220	if (leaf->rays[i].mRay->ScheduledForRemoval()) {
1221	// find a ray to replace it with
1222	while (tail >= i && leaf->rays[tail].mRay->ScheduledForRemoval()) {
1223	stat.removedRayRefs++;
1224	leaf->rays[tail].mRay->Unref();
1225	leaf->rays.pop_back();
1226	tail--;
1227	}
1228
1229	if (tail < i)
1230	break;
1231
1232	stat.removedRayRefs++;
1233	leaf->rays[i].mRay->Unref();
1234	leaf->rays[i] = leaf->rays[tail];
1235	leaf->rays.pop_back();
1236	tail--;
1237	}
1238	}
1239	}
1240	}
1241
1242	if (!removeAllScheduledRays)
1243	for (int i=0; i < (int)leaf->rays.size(); i++) {
1244	if (leaf->rays[i].mRay == ray) {
1245	stat.removedRayRefs++;
1246	ray->Unref();
1247	leaf->rays[i] = leaf->rays[leaf->rays.size()-1];
1248	leaf->rays.pop_back();
1249	// check this ray again
1250	break;
1251	}
1252	}
1253
1254	}
1255	}
1256
1257	if (ray->RefCount() != 0) {
1258	cerr<<"Error: Number of remaining refs = "<<ray->RefCount()<<endl;
1259	exit(1);
1260	}
1261
1262	}
1263
1264
1265	void
1266	VssTree::AddRay(VssTreeNode::RayInfo &info)
1267	{
1268
1269	stack<RayTraversalData> tstack;
1270
1271	tstack.push(RayTraversalData(root, info));
1272
1273	RayTraversalData data;
1274
1275	while (!tstack.empty()) {
1276	data = tstack.top();
1277	tstack.pop();
1278
1279	if (!data.node->IsLeaf()) {
1280	TraverseInternalNode(data, tstack);
1281	} else {
1282	// remove the ray from the leaf
1283	// find the ray in the leaf and swap it with the last ray...
1284	VssTreeLeaf leaf = (VssTreeLeaf )data.node;
1285	leaf->AddRay(data.rayData);
1286	stat.addedRayRefs++;
1287	}
1288	}
1289	}
1290
1291	void
1292	VssTree::TraverseInternalNode(
1293	RayTraversalData &data,
1294	stack<RayTraversalData> &tstack)
1295	{
1296	VssTreeInterior in = (VssTreeInterior ) data.node;
1297
1298	if (in->axis <= VssTreeNode::SPLIT_Z) {
1299
1300	// determine the side of this ray with respect to the plane
1301	int side = in->ComputeRayIntersection(data.rayData,
1302	data.rayData.mRay->mT);
1303
1304
1305	if (side == 0) {
1306	if (data.rayData.mRay->HasPosDir(in->axis)) {
1307	tstack.push(RayTraversalData(in->back,
1308	VssTreeNode::RayInfo(data.rayData.mRay,
1309	data.rayData.mMinT,
1310	data.rayData.mRay->mT))
1311	);
1312
1313	tstack.push(RayTraversalData(in->front,
1314	VssTreeNode::RayInfo(data.rayData.mRay,
1315	data.rayData.mRay->mT,
1316	data.rayData.mMaxT
1317	))
1318	);
1319
1320	} else {
1321	tstack.push(RayTraversalData(in->back,
1322	VssTreeNode::RayInfo(data.rayData.mRay,
1323	data.rayData.mRay->mT,
1324	data.rayData.mMaxT
1325	))
1326	);
1327
1328	tstack.push(RayTraversalData(in->front,
1329	VssTreeNode::RayInfo(data.rayData.mRay,
1330	data.rayData.mMinT,
1331	data.rayData.mRay->mT))
1332	);
1333
1334
1335	}
1336	} else
1337	if (side == 1)
1338	tstack.push(RayTraversalData(in->front, data.rayData));
1339	else
1340	tstack.push(RayTraversalData(in->back, data.rayData));
1341	}
1342	else {
1343	// directional split
1344	if (data.rayData.mRay->GetDirParametrization(in->axis - 3) > in->position)
1345	tstack.push(RayTraversalData(in->front, data.rayData));
1346	else
1347	tstack.push(RayTraversalData(in->back, data.rayData));
1348	}
1349	}
1350
1351
1352	int
1353	VssTree::CollapseSubtree(VssTreeNode *sroot, const int time)
1354	{
1355	// first count all rays in the subtree
1356	// use mail 1 for this purpose
1357	stack<VssTreeNode *> tstack;
1358	int rayCount = 0;
1359	int totalRayCount = 0;
1360	int collapsedNodes = 0;
1361
1362	#if DEBUG_COLLAPSE
1363	cout<<"Collapsing subtree"<<endl;
1364	cout<<"acessTime="<<sroot->GetAccessTime()<<endl;
1365	cout<<"depth="<<(int)sroot->depth<<endl;
1366	#endif
1367
1368	// tstat.collapsedSubtrees++;
1369	// tstat.collapseDepths += (int)sroot->depth;
1370	// tstat.collapseAccessTimes += time - sroot->GetAccessTime();
1371
1372	tstack.push(sroot);
1373	VssRay::NewMail();
1374
1375	while (!tstack.empty()) {
1376	collapsedNodes++;
1377	VssTreeNode *node = tstack.top();
1378	tstack.pop();
1379
1380	if (node->IsLeaf()) {
1381	VssTreeLeaf leaf = (VssTreeLeaf ) node;
1382	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
1383	ri != leaf->rays.end();
1384	ri++) {
1385
1386	totalRayCount++;
1387	if ((ri).mRay->IsActive() && !(ri).mRay->Mailed()) {
1388	(*ri).mRay->Mail();
1389	rayCount++;
1390	}
1391	}
1392	} else {
1393	tstack.push(((VssTreeInterior *)node)->back);
1394	tstack.push(((VssTreeInterior *)node)->front);
1395	}
1396	}
1397
1398	VssRay::NewMail();
1399
1400	// create a new node that will hold the rays
1401	VssTreeLeaf *newLeaf = new VssTreeLeaf( sroot->parent, rayCount );
1402	if ( newLeaf->parent )
1403	newLeaf->parent->ReplaceChildLink(sroot, newLeaf);
1404
1405
1406	tstack.push( sroot );
1407
1408	while (!tstack.empty()) {
1409
1410	VssTreeNode *node = tstack.top();
1411	tstack.pop();
1412
1413	if (node->IsLeaf()) {
1414	VssTreeLeaf leaf = (VssTreeLeaf ) node;
1415
1416	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
1417	ri != leaf->rays.end();
1418	ri++) {
1419
1420	// unref this ray from the old node
1421
1422	if ((*ri).mRay->IsActive()) {
1423	(*ri).mRay->Unref();
1424	if (!(*ri).mRay->Mailed()) {
1425	(*ri).mRay->Mail();
1426	newLeaf->AddRay(*ri);
1427	}
1428	} else
1429	(*ri).mRay->Unref();
1430
1431	}
1432	} else {
1433	tstack.push(((VssTreeInterior *)node)->back);
1434	tstack.push(((VssTreeInterior *)node)->front);
1435	}
1436	}
1437
1438	// delete the node and all its children
1439	delete sroot;
1440
1441	// for(VssTreeNode::SRayContainer::iterator ri = newLeaf->rays.begin();
1442	// ri != newLeaf->rays.end();
1443	// ri++)
1444	// (*ri).ray->UnMail(2);
1445
1446
1447	#if DEBUG_COLLAPSE
1448	cout<<"Total memory before="<<GetMemUsage()<<endl;
1449	#endif
1450
1451	stat.nodes -= collapsedNodes - 1;
1452	stat.rayRefs -= totalRayCount - rayCount;
1453
1454	#if DEBUG_COLLAPSE
1455	cout<<"collapsed nodes"<<collapsedNodes<<endl;
1456	cout<<"collapsed rays"<<totalRayCount - rayCount<<endl;
1457	cout<<"Total memory after="<<GetMemUsage()<<endl;
1458	cout<<"================================"<<endl;
1459	#endif
1460
1461	// tstat.collapsedNodes += collapsedNodes;
1462	// tstat.collapsedRays += totalRayCount - rayCount;
1463
1464	return totalRayCount - rayCount;
1465	}
1466
1467
1468	int
1469	VssTree::GetPvsSize(VssTreeNode *node, const AxisAlignedBox3 &box) const
1470	{
1471	stack<VssTreeNode *> tstack;
1472	tstack.push(root);
1473
1474	Intersectable::NewMail();
1475	int pvsSize = 0;
1476
1477	while (!tstack.empty()) {
1478	VssTreeNode *node = tstack.top();
1479	tstack.pop();
1480
1481
1482	if (node->IsLeaf()) {
1483	VssTreeLeaf leaf = (VssTreeLeaf )node;
1484	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
1485	ri != leaf->rays.end();
1486	ri++)
1487	if ((*ri).mRay->IsActive()) {
1488	Intersectable *object;
1489	#if BIDIRECTIONAL_RAY
1490	object = (*ri).mRay->mOriginObject;
1491	if (object && !object->Mailed()) {
1492	pvsSize++;
1493	object->Mail();
1494	}
1495	#endif
1496	object = (*ri).mRay->mTerminationObject;
1497	if (object && !object->Mailed()) {
1498	pvsSize++;
1499	object->Mail();
1500	}
1501	}
1502	} else {
1503	VssTreeInterior in = (VssTreeInterior )node;
1504	if (in->axis < 3) {
1505	if (box.Max(in->axis) >= in->position )
1506	tstack.push(in->front);
1507
1508	if (box.Min(in->axis) <= in->position )
1509	tstack.push(in->back);
1510	} else {
1511	// both nodes for directional splits
1512	tstack.push(in->front);
1513	tstack.push(in->back);
1514	}
1515	}
1516	}
1517	return pvsSize;
1518	}
1519
1520	void
1521	VssTree::GetRayContributionStatistics(
1522	float &minRayContribution,
1523	float &maxRayContribution,
1524	float &avgRayContribution
1525	)
1526	{
1527	stack<VssTreeNode *> tstack;
1528	tstack.push(root);
1529
1530	minRayContribution = 1.0f;
1531	maxRayContribution = 0.0f;
1532	float sumRayContribution = 0.0f;
1533	int leaves = 0;
1534
1535	while (!tstack.empty()) {
1536	VssTreeNode *node = tstack.top();
1537	tstack.pop();
1538
1539	if (node->IsLeaf()) {
1540	leaves++;
1541	VssTreeLeaf leaf = (VssTreeLeaf )node;
1542	float c = leaf->GetAvgRayContribution();
1543	if (c > maxRayContribution)
1544	maxRayContribution = c;
1545	if (c < minRayContribution)
1546	minRayContribution = c;
1547	sumRayContribution += c;
1548
1549	} else {
1550	VssTreeInterior in = (VssTreeInterior )node;
1551	// both nodes for directional splits
1552	tstack.push(in->front);
1553	tstack.push(in->back);
1554	}
1555	}
1556
1557	cout<<"sum="<<sumRayContribution<<endl;
1558	cout<<"leaves="<<leaves<<endl;
1559	avgRayContribution = sumRayContribution/(float)leaves;
1560	}
1561
1562
1563	int
1564	VssTree::GenerateRays(const float ratioPerLeaf,
1565	SimpleRayContainer &rays)
1566	{
1567	stack<VssTreeNode *> tstack;
1568	tstack.push(root);
1569
1570	while (!tstack.empty()) {
1571	VssTreeNode *node = tstack.top();
1572	tstack.pop();
1573
1574	if (node->IsLeaf()) {
1575	VssTreeLeaf leaf = (VssTreeLeaf )node;
1576	float c = leaf->GetAvgRayContribution();
1577	int num = (c*ratioPerLeaf + 0.5);
1578	// cout<<num<<" ";
1579
1580	for (int i=0; i < num; i++) {
1581	Vector3 origin = GetBBox(leaf).GetRandomPoint();
1582	Vector3 dirVector = GetDirBBox(leaf).GetRandomPoint();
1583	Vector3 direction = Vector3(sin(dirVector.x), sin(dirVector.y), cos(dirVector.x));
1584	//cout<<"dir vector.x="<<dirVector.x<<"direction'.x="<<atan2(direction.x, direction.y)<<endl;
1585	rays.push_back(SimpleRay(origin, direction));
1586	}
1587
1588	} else {
1589	VssTreeInterior in = (VssTreeInterior )node;
1590	// both nodes for directional splits
1591	tstack.push(in->front);
1592	tstack.push(in->back);
1593	}
1594	}
1595
1596	return rays.size();
1597	}
1598
1599	void
1600	VssTree::CollectLeaves(vector<VssTreeLeaf *> &leaves)
1601	{
1602	stack<VssTreeNode *> tstack;
1603	tstack.push(root);
1604
1605	while (!tstack.empty()) {
1606	VssTreeNode *node = tstack.top();
1607	tstack.pop();
1608
1609	if (node->IsLeaf()) {
1610	VssTreeLeaf leaf = (VssTreeLeaf )node;
1611	leaves.push_back(leaf);
1612	} else {
1613	VssTreeInterior in = (VssTreeInterior )node;
1614	// both nodes for directional splits
1615	tstack.push(in->front);
1616	tstack.push(in->back);
1617	}
1618	}
1619	}
1620
1621	int
1622	VssTree::GenerateRays(const int numberOfRays,
1623	const int numberOfLeaves,
1624	SimpleRayContainer &rays)
1625	{
1626
1627	vector<VssTreeLeaf *> leaves;
1628
1629	CollectLeaves(leaves);
1630
1631	sort(leaves.begin(),
1632	leaves.end(),
1633	GreaterContribution);
1634
1635
1636	float sumContrib = 0.0;
1637	int i;
1638	for (i=0; i < numberOfLeaves; i++) {
1639	float c = leaves[i]->GetAvgRayContribution();
1640	sumContrib += c;
1641	// cout<<"ray contrib "<<i<<" : "<<c<<endl;
1642	}
1643
1644	float avgContrib = sumContrib/numberOfLeaves;
1645	float ratioPerLeaf = numberOfRays/(avgContrib*numberOfLeaves);
1646
1647	for (i=0; i < numberOfLeaves; i++) {
1648	VssTreeLeaf *leaf = leaves[i];
1649	float c = leaf->GetAvgRayContribution();
1650	int num = (c*ratioPerLeaf + 0.5);
1651	// cout<<num<<" ";
1652
1653	for (int i=0; i < num; i++) {
1654	Vector3 origin = GetBBox(leaf).GetRandomPoint();
1655	Vector3 dirVector = GetDirBBox(leaf).GetRandomPoint();
1656	Vector3 direction = Vector3(sin(dirVector.x), sin(dirVector.y), cos(dirVector.x));
1657	//cout<<"dir vector.x="<<dirVector.x<<"direction'.x="<<atan2(direction.x, direction.y)<<endl;
1658	rays.push_back(SimpleRay(origin, direction));
1659	}
1660	}
1661	return rays.size();
1662	}
1663
1664
1665	float
1666	VssTree::GetAvgPvsSize()
1667	{
1668	stack<VssTreeNode *> tstack;
1669	tstack.push(root);
1670
1671	int sumPvs = 0;
1672	int leaves = 0;
1673	while (!tstack.empty()) {
1674	VssTreeNode *node = tstack.top();
1675	tstack.pop();
1676
1677	if (node->IsLeaf()) {
1678	VssTreeLeaf leaf = (VssTreeLeaf )node;
1679	// update pvs size
1680	leaf->UpdatePvsSize();
1681	sumPvs += leaf->GetPvsSize();
1682	leaves++;
1683	} else {
1684	VssTreeInterior in = (VssTreeInterior )node;
1685	// both nodes for directional splits
1686	tstack.push(in->front);
1687	tstack.push(in->back);
1688	}
1689	}
1690
1691
1692	return sumPvs/(float)leaves;
1693	}
1694
1695

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

Download in other formats: