Context Navigation

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

Revision 372, 21.9 KB checked in by bittner, 19 years ago (diff)
preparation for vss preprocessor. converted all .cpp and .h to dos new line format

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
25
26	#define DEBUG_DIR_SPLIT 0
27
28
29
30	// Static variables
31	int
32	VssTreeLeaf::mailID = 0;
33
34
35	// Constructor
36	VssTree::VssTree()
37	{
38	environment->GetIntValue("VssTree.maxDepth", termMaxDepth);
39
40	environment->GetIntValue("VssTree.minCost", termMinCost);
41
42	environment->GetFloatValue("VssTree.minSize", termMinSize);
43	termMinSize = sqr(termMinSize);
44
45	environment->GetFloatValue("VssTree.refDirBoxMaxSize", refDirBoxMaxSize);
46	refDirBoxMaxSize = sqr(refDirBoxMaxSize);
47
48	environment->GetFloatValue("VssTree.epsilon", epsilon);
49	environment->GetFloatValue("VssTree.ct_div_ci", ct_div_ci);
50
51	environment->GetFloatValue("VssTree.maxTotalMemory", maxTotalMemory);
52	environment->GetFloatValue("VssTree.maxStaticMemory", maxStaticMemory);
53
54	environment->GetFloatValue("VssTree.maxCostRatio", maxCostRatio);
55
56
57
58	float refDirAngle;
59	environment->GetFloatValue("VssTree.refDirAngle", refDirAngle);
60
61	environment->GetIntValue("VssTree.accessTimeThreshold", accessTimeThreshold);
62	//= 1000;
63	environment->GetIntValue("VssTree.minCollapseDepth", minCollapseDepth);
64	// int minCollapseDepth = 4;
65
66	// pRefDirThresh = cos(0.5M_PI - M_PIrefDirAngle/180.0);
67	// cosRefDir = cos(M_PI*refDirAngle/180.0);
68	// sinRefDir = sin(M_PI*refDirAngle/180.0);
69
70
71	// split type
72	char sname[128];
73	environment->GetStringValue("VssTree.splitType", sname);
74	string name(sname);
75
76	if (name.compare("regular") == 0)
77	splitType = ESplitRegular;
78	else
79	if (name.compare("volume") == 0)
80	splitType = ESplitVolume;
81	else
82	if (name.compare("queries") == 0)
83	splitType = ESplitQueries;
84	else {
85	cerr<<"Invalid VssTree split type "<<name<<endl;
86	exit(1);
87	}
88
89	environment->GetBoolValue("VssTree.randomize", randomize);
90
91	root = NULL;
92
93	splitCandidates = new vector<SSortableEntry>;
94	}
95
96
97	VssTree::~VssTree()
98	{
99	if (root)
100	delete root;
101	}
102
103
104
105
106	void
107	VssStatistics::Print(ostream &app) const
108	{
109	app << "===== VssTree statistics ===============\n";
110
111	app << "#N_RAYS Number of rays )\n"
112	<< rays <<endl;
113	app << "#N_DOMAINS ( Number of query domains )\n"
114	<< queryDomains <<endl;
115
116	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
117
118	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
119
120	app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n";
121	for (int i=0; i<7; i++)
122	app << splits[i] <<" ";
123	app <<endl;
124
125	app << "#N_RAYREFS ( Number of rayRefs )\n" <<
126	rayRefs << "\n";
127
128	app << "#N_RAYRAYREFS ( Number of rayRefs / ray )\n" <<
129	rayRefs/(double)rays << "\n";
130
131	app << "#N_LEAFRAYREFS ( Number of rayRefs / leaf )\n" <<
132	rayRefs/(double)Leaves() << "\n";
133
134	app << "#N_MAXRAYREFS ( Max number of rayRefs / leaf )\n" <<
135	maxRayRefs << "\n";
136
137	app << "#N_NONEMPTYRAYREFS ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" <<
138	rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";
139
140	app << "#N_LEAFDOMAINREFS ( Number of query domain Refs / leaf )\n" <<
141	queryDomainRefs/(double)Leaves() << "\n";
142
143	// app << setprecision(4);
144
145	app << "#N_PEMPTYLEAVES ( Percentage of leaves with zero query domains )\n"<<
146	zeroQueryNodes*100/(double)Leaves()<<endl;
147
148	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
149	maxDepthNodes*100/(double)Leaves()<<endl;
150
151	app << "#N_PMINCOSTLEAVES ( Percentage of leaves with minCost )\n"<<
152	minCostNodes*100/(double)Leaves()<<endl;
153
154	app << "#N_ADDED_RAYREFS (Number of dynamically added ray references )\n"<<
155	addedRayRefs<<endl;
156
157	app << "#N_REMOVED_RAYREFS (Number of dynamically removed ray references )\n"<<
158	removedRayRefs<<endl;
159
160	// app << setprecision(4);
161
162	app << "#N_CTIME ( Construction time [s] )\n"
163	<< Time() << " \n";
164
165	app << "===== END OF VssTree statistics ==========\n";
166
167	}
168
169
170
171
172	void
173	VssTree::Construct(
174	VssRayContainer &rays,
175	const bool onlyStaticPart
176	)
177	{
178	stat.Start();
179
180	if (onlyStaticPart)
181	maxMemory = maxStaticMemory;
182	else
183	maxMemory = maxTotalMemory;
184
185
186	if (root)
187	delete root;
188
189	root = new VssTreeLeaf(NULL, rays.size());
190	// first construct a leaf that will get subdivide
191	VssTreeLeaf leaf = (VssTreeLeaf ) root;
192
193	stat.nodes = 1;
194
195	bbox.Initialize();
196
197	dirBBox.Initialize();
198
199	for(VssRayContainer::const_iterator ri = rays.begin();
200	ri != rays.end();
201	ri++) {
202	leaf->AddRay(VssTreeNode::RayInfo(*ri));
203	bbox.Include((*ri)->GetOrigin());
204	bbox.Include((*ri)->GetTermination());
205
206	dirBBox.Include( (*ri)->GetNormalizedDir() );
207	}
208
209
210	stat.rays = leaf->rays.size();
211
212	// Subdivide();
213	root = Subdivide(TraversalData(leaf, bbox, 0));
214
215	if (splitCandidates) {
216	// force realease of this vector
217	delete splitCandidates;
218	splitCandidates = new vector<SSortableEntry>;
219	}
220
221	stat.Stop();
222
223	cout<<"##################################"<<endl;
224
225	}
226
227
228	VssTreeNode *
229	VssTree::Subdivide(const TraversalData &tdata)
230	{
231	VssTreeNode *result = NULL;
232
233	priority_queue<TraversalData> tStack;
234	// stack<TraversalData> tStack;
235
236	tStack.push(tdata);
237
238	AxisAlignedBox3 backBox;
239	AxisAlignedBox3 frontBox;
240
241
242	while (!tStack.empty()) {
243
244	if ( GetMemUsage() > maxMemory ) {
245	// count statistics on unprocessed leafs
246	while (!tStack.empty()) {
247	EvaluateLeafStats(tStack.top());
248	tStack.pop();
249	}
250	break;
251	}
252
253	TraversalData data = tStack.top();
254	tStack.pop();
255
256	VssTreeNode node = SubdivideNode((VssTreeLeaf ) data.node,
257	data.bbox,
258	backBox,
259	frontBox
260	);
261	if (result == NULL)
262	result = node;
263
264	if (!node->IsLeaf()) {
265
266	VssTreeInterior interior = (VssTreeInterior ) node;
267	// push the children on the stack
268	tStack.push(TraversalData(interior->back, backBox, data.depth+1));
269	tStack.push(TraversalData(interior->front, frontBox, data.depth+1));
270
271	} else {
272	EvaluateLeafStats(data);
273	}
274	}
275
276	return result;
277	}
278
279
280	// returns selected plane for subdivision
281	int
282	VssTree::SelectPlane(
283	VssTreeLeaf *leaf,
284	const AxisAlignedBox3 &box,
285	float &position
286	)
287	{
288
289	int minDirDepth = 6;
290
291	Vector3 size = box.Size();
292
293	float pDirSubdivision = 0.0f;
294	if (leaf->depth >= minDirDepth && RandomValue(0, 1) < pDirSubdivision) {
295	AxisAlignedBox3 dirbox = GetDirBBox(leaf);
296	Vector3 size = dirbox.Size();
297	int axis = size.DrivingAxis();
298	position = (dirbox.Min()[axis] + dirbox.Max()[axis])*0.5f;
299	return axis + 3;
300	}
301
302	int axis = size.DrivingAxis();
303
304
305	if (splitType == ESplitRegular) {
306	position = (box.Min()[axis] + box.Max()[axis])*0.5f;
307	}
308
309	return axis;
310	}
311
312
313	void
314	VssTree::EvaluateLeafStats(const TraversalData &data)
315	{
316
317	// the node became a leaf -> evaluate stats for leafs
318	VssTreeLeaf leaf = (VssTreeLeaf )data.node;
319
320	if (data.depth > termMaxDepth)
321	stat.maxDepthNodes++;
322
323	if ( (int)(leaf->rays.size()) < termMinCost)
324	stat.minCostNodes++;
325
326
327	if ( (int)(leaf->rays.size()) > stat.maxRayRefs)
328	stat.maxRayRefs = leaf->rays.size();
329
330	}
331
332
333
334	VssTreeNode *
335	VssTree::SubdivideNode(
336	VssTreeLeaf *leaf,
337	const AxisAlignedBox3 &box,
338	AxisAlignedBox3 &backBBox,
339	AxisAlignedBox3 &frontBBox
340	)
341	{
342
343	if ( ((int)leaf->rays.size() < termMinCost) \|\|
344	(leaf->depth >= termMaxDepth) ) {
345	return leaf;
346	}
347
348	float position;
349
350	// select subdivision axis
351	int axis = SelectPlane( leaf, box, position);
352
353	if (axis == -1) {
354	return leaf;
355	}
356
357	stat.nodes+=2;
358	stat.splits[axis]++;
359
360	// add the new nodes to the tree
361	VssTreeInterior *node = new VssTreeInterior(leaf->parent);
362
363	node->axis = axis;
364	node->position = position;
365	node->bbox = box;
366
367	node->dirBBox = GetDirBBox(leaf);
368
369	backBBox = box;
370	frontBBox = box;
371
372	// first count ray sides
373	int raysBack = 0;
374	int raysFront = 0;
375
376	if (axis <= VssTreeNode::SPLIT_Z) {
377	backBBox.SetMax(axis, position);
378	frontBBox.SetMin(axis, position);
379
380	// this is the main ray classification loop!
381	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
382	ri != leaf->rays.end();
383	ri++)
384	if ((*ri).mRay->IsActive()) {
385
386	// determine the side of this ray with respect to the plane
387	int side = node->ComputeRayIntersection(ri, (ri).mRay->mT);
388
389	(*ri).mRay->mSide = side;
390
391	if (side <= 0)
392	raysBack++;
393
394	if (side >= 0)
395	raysFront++;
396
397	#if 0
398	cout<<"-------------------"<<endl;
399	cout<<"axis = "<<(int)node->axis<<"\t position="<<node->position<<endl;
400	cout<<"origin="<<(ri).ray->GetOrigin()<<"\t term="<<(ri).ray->GetTermination()<<endl;
401	cout<<"side = "<<side<<"\t t="<<t<<endl;
402	cout<<"-------------------"<<endl;
403	#endif
404	}
405	} else {
406	// directional split
407	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
408	ri != leaf->rays.end();
409	ri++)
410	if ((*ri).mRay->IsActive()) {
411
412	// determine the side of this ray with respect to the plane
413	int side;
414	if ((*ri).mRay->GetNormalizedDir(axis - 3) > position)
415	side = 1;
416	else
417	side = -1;
418
419
420	(*ri).mRay->mSide = side;
421
422	if (side <= 0)
423	raysBack++;
424
425	if (side >= 0)
426	raysFront++;
427	}
428	}
429
430	VssTreeLeaf *back = new VssTreeLeaf(node, raysBack);
431	VssTreeLeaf *front = new VssTreeLeaf(node, raysFront);
432
433	// replace a link from node's parent
434	if ( leaf->parent )
435	leaf->parent->ReplaceChildLink(leaf, node);
436	// and setup child links
437	node->SetupChildLinks(back, front);
438
439
440	if (axis <= VssTreeNode::SPLIT_Z) {
441	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
442	ri != leaf->rays.end();
443	ri++) {
444	if ((*ri).mRay->IsActive()) {
445
446	// first unref ray from the former leaf
447	(*ri).mRay->Unref();
448
449	if ((*ri).mRay->mSide == 0) {
450	if ((*ri).mRay->HasPosDir(axis)) {
451	back->AddRay(VssTreeNode::RayInfo((*ri).mRay,
452	(*ri).mMinT,
453	(*ri).mRay->mT)
454	);
455	front->AddRay(VssTreeNode::RayInfo((*ri).mRay,
456	(*ri).mRay->mT,
457	(*ri).mMaxT));
458	} else {
459	back->AddRay(VssTreeNode::RayInfo((*ri).mRay,
460	(*ri).mRay->mT,
461	(*ri).mMaxT));
462	front->AddRay(VssTreeNode::RayInfo((*ri).mRay,
463	(*ri).mMinT,
464	(*ri).mRay->mT));
465	}
466	} else
467	if ((*ri).mRay->mSide == 1)
468	front->AddRay(*ri);
469	else
470	back->AddRay(*ri);
471	} else
472	(*ri).mRay->Unref();
473	}
474	} else {
475	// rays front/back
476
477	#if DEBUG_DIR_SPLIT
478	cout<<"dir split, depth="<<(int)leaf->depth<<" front= "<<raysFront<<" back="<<raysBack<<endl;
479	#endif
480
481	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
482	ri != leaf->rays.end();
483	ri++) {
484	if ((*ri).mRay->IsActive()) {
485	// first unref ray from the former leaf
486	(*ri).mRay->Unref();
487
488	if ((*ri).mRay->mSide == 1)
489	front->AddRay(*ri);
490	else
491	back->AddRay(*ri);
492
493	} else
494	(*ri).mRay->Unref();
495	}
496	}
497
498	// update stats
499	stat.rayRefs -= leaf->rays.size();
500	stat.rayRefs += raysBack + raysFront;
501
502
503	delete leaf;
504	return node;
505	}
506
507
508
509
510
511
512	int
513	VssTree::ReleaseMemory(const int time)
514	{
515	stack<VssTreeNode *> tstack;
516
517	// find a node in the tree which subtree will be collapsed
518	int maxAccessTime = time - accessTimeThreshold;
519	int released;
520
521	tstack.push(root);
522
523	while (!tstack.empty()) {
524	VssTreeNode *node = tstack.top();
525	tstack.pop();
526
527
528	if (!node->IsLeaf()) {
529	VssTreeInterior in = (VssTreeInterior )node;
530	// cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
531	if (in->depth >= minCollapseDepth &&
532	in->lastAccessTime <= maxAccessTime) {
533	released = CollapseSubtree(node, time);
534	break;
535	}
536
537	if (in->back->GetAccessTime() <
538	in->front->GetAccessTime()) {
539	tstack.push(in->front);
540	tstack.push(in->back);
541	} else {
542	tstack.push(in->back);
543	tstack.push(in->front);
544	}
545	}
546	}
547
548	while (tstack.empty()) {
549	// could find node to collaps...
550	// cout<<"Could not find a node to release "<<endl;
551	break;
552	}
553
554	return released;
555	}
556
557
558
559
560	VssTreeNode *
561	VssTree::SubdivideLeaf(
562	VssTreeLeaf *leaf,
563	const float sizeThreshold
564	)
565	{
566	VssTreeNode *node = leaf;
567
568	AxisAlignedBox3 leafBBox = GetBBox(leaf);
569
570	static int pass = 0;
571	pass ++;
572
573	// check if we should perform a dynamic subdivision of the leaf
574	if (
575	leaf->rays.size() > (unsigned)termMinCost &&
576	SqrMagnitude(leafBBox.Size()) > sizeThreshold) {
577
578	// memory check and realese...
579	if (GetMemUsage() > maxTotalMemory) {
580	ReleaseMemory( pass );
581	}
582
583	AxisAlignedBox3 backBBox, frontBBox;
584
585	// subdivide the node
586	node =
587	SubdivideNode(leaf,
588	leafBBox,
589	backBBox,
590	frontBBox
591	);
592	}
593	return node;
594	}
595
596
597
598	void
599	VssTree::UpdateRays(VssRayContainer &remove,
600	VssRayContainer &add
601	)
602	{
603	VssTreeLeaf::NewMail();
604
605	// schedule rays for removal
606	for(VssRayContainer::const_iterator ri = remove.begin();
607	ri != remove.end();
608	ri++) {
609	(*ri)->ScheduleForRemoval();
610	}
611
612	int inactive=0;
613
614	for(VssRayContainer::const_iterator ri = remove.begin();
615	ri != remove.end();
616	ri++) {
617	if ((*ri)->ScheduledForRemoval())
618	// RemoveRay(*ri, NULL, false);
619	// !!! BUG - with true it does not work correctly - aggreated delete
620	RemoveRay(*ri, NULL, true);
621	else
622	inactive++;
623	}
624
625
626	// cout<<"all/inactive"<<remove.size()<<"/"<<inactive<<endl;
627
628	for(VssRayContainer::const_iterator ri = add.begin();
629	ri != add.end();
630	ri++) {
631	AddRay(*ri);
632	}
633
634
635	}
636
637
638	void
639	VssTree::RemoveRay(VssRay *ray,
640	vector<VssTreeLeaf > affectedLeaves,
641	const bool removeAllScheduledRays
642	)
643	{
644
645	stack<RayTraversalData> tstack;
646
647	tstack.push(RayTraversalData(root, VssTreeNode::RayInfo(ray)));
648
649	RayTraversalData data;
650
651	// cout<<"Number of ray refs = "<<ray->RefCount()<<endl;
652
653	while (!tstack.empty()) {
654	data = tstack.top();
655	tstack.pop();
656
657	if (!data.node->IsLeaf()) {
658	// split the set of rays in two groups intersecting the
659	// two subtrees
660
661	TraverseInternalNode(data, tstack);
662
663	} else {
664	// remove the ray from the leaf
665	// find the ray in the leaf and swap it with the last ray...
666	VssTreeLeaf leaf = (VssTreeLeaf )data.node;
667
668	if (!leaf->Mailed()) {
669	leaf->Mail();
670	if (affectedLeaves)
671	affectedLeaves->push_back(leaf);
672
673	if (removeAllScheduledRays) {
674	int tail = leaf->rays.size()-1;
675
676	for (int i=0; i < (int)(leaf->rays.size()); i++) {
677	if (leaf->rays[i].mRay->ScheduledForRemoval()) {
678	// find a ray to replace it with
679	while (tail >= i && leaf->rays[tail].mRay->ScheduledForRemoval()) {
680	stat.removedRayRefs++;
681	leaf->rays[tail].mRay->Unref();
682	leaf->rays.pop_back();
683	tail--;
684	}
685
686	if (tail < i)
687	break;
688
689	stat.removedRayRefs++;
690	leaf->rays[i].mRay->Unref();
691	leaf->rays[i] = leaf->rays[tail];
692	leaf->rays.pop_back();
693	tail--;
694	}
695	}
696	}
697	}
698
699	if (!removeAllScheduledRays)
700	for (int i=0; i < (int)leaf->rays.size(); i++) {
701	if (leaf->rays[i].mRay == ray) {
702	stat.removedRayRefs++;
703	ray->Unref();
704	leaf->rays[i] = leaf->rays[leaf->rays.size()-1];
705	leaf->rays.pop_back();
706	// check this ray again
707	break;
708	}
709	}
710
711	}
712	}
713
714	if (ray->RefCount() != 0) {
715	cerr<<"Error: Number of remaining refs = "<<ray->RefCount()<<endl;
716	exit(1);
717	}
718
719	}
720
721
722	void
723	VssTree::AddRay(VssRay *ray)
724	{
725
726	stack<RayTraversalData> tstack;
727
728	tstack.push(RayTraversalData(root, VssTreeNode::RayInfo(ray)));
729
730	RayTraversalData data;
731
732	while (!tstack.empty()) {
733	data = tstack.top();
734	tstack.pop();
735
736	if (!data.node->IsLeaf()) {
737
738	TraverseInternalNode(data, tstack);
739
740	} else {
741	// remove the ray from the leaf
742	// find the ray in the leaf and swap it with the last ray...
743	VssTreeLeaf leaf = (VssTreeLeaf )data.node;
744	leaf->AddRay(data.rayData);
745	stat.addedRayRefs++;
746	}
747	}
748	}
749
750	void
751	VssTree::TraverseInternalNode(
752	RayTraversalData &data,
753	stack<RayTraversalData> &tstack)
754	{
755	VssTreeInterior in = (VssTreeInterior ) data.node;
756
757	if (in->axis <= VssTreeNode::SPLIT_Z) {
758
759	// determine the side of this ray with respect to the plane
760	int side = in->ComputeRayIntersection(data.rayData,
761	data.rayData.mRay->mT);
762
763
764	if (side == 0) {
765	if (data.rayData.mRay->HasPosDir(in->axis)) {
766	tstack.push(RayTraversalData(in->back,
767	VssTreeNode::RayInfo(data.rayData.mRay,
768	data.rayData.mMinT,
769	data.rayData.mRay->mT))
770	);
771
772	tstack.push(RayTraversalData(in->front,
773	VssTreeNode::RayInfo(data.rayData.mRay,
774	data.rayData.mRay->mT,
775	data.rayData.mMaxT
776	))
777	);
778
779	} else {
780	tstack.push(RayTraversalData(in->back,
781	VssTreeNode::RayInfo(data.rayData.mRay,
782	data.rayData.mRay->mT,
783	data.rayData.mMaxT
784	))
785	);
786
787	tstack.push(RayTraversalData(in->front,
788	VssTreeNode::RayInfo(data.rayData.mRay,
789	data.rayData.mMinT,
790	data.rayData.mRay->mT))
791	);
792
793
794	}
795	} else
796	if (side == 1)
797	tstack.push(RayTraversalData(in->front, data.rayData));
798	else
799	tstack.push(RayTraversalData(in->back, data.rayData));
800	}
801	else {
802	// directional split
803	// if (DotProd(data.rayData.mRay->GetNormalizedDir(), in->refDir) > sinRefDir )
804	// tstack.push(RayTraversalData(in->front, data.rayData));
805	// else
806	// tstack.push(RayTraversalData(in->back, data.rayData));
807	}
808
809	}
810
811
812	int
813	VssTree::CollapseSubtree(VssTreeNode *sroot, const int time)
814	{
815	// first count all rays in the subtree
816	// use mail 1 for this purpose
817	stack<VssTreeNode *> tstack;
818	int rayCount = 0;
819	int totalRayCount = 0;
820	int collapsedNodes = 0;
821
822	#if DEBUG_COLLAPSE
823	cout<<"Collapsing subtree"<<endl;
824	cout<<"acessTime="<<sroot->GetAccessTime()<<endl;
825	cout<<"depth="<<(int)sroot->depth<<endl;
826	#endif
827
828	// tstat.collapsedSubtrees++;
829	// tstat.collapseDepths += (int)sroot->depth;
830	// tstat.collapseAccessTimes += time - sroot->GetAccessTime();
831
832	tstack.push(sroot);
833	VssRay::NewMail();
834
835	while (!tstack.empty()) {
836	collapsedNodes++;
837	VssTreeNode *node = tstack.top();
838	tstack.pop();
839
840	if (node->IsLeaf()) {
841	VssTreeLeaf leaf = (VssTreeLeaf ) node;
842	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
843	ri != leaf->rays.end();
844	ri++) {
845
846	totalRayCount++;
847	if ((ri).mRay->IsActive() && !(ri).mRay->Mailed()) {
848	(*ri).mRay->Mail();
849	rayCount++;
850	}
851	}
852	} else {
853	tstack.push(((VssTreeInterior *)node)->back);
854	tstack.push(((VssTreeInterior *)node)->front);
855	}
856	}
857
858	VssRay::NewMail();
859
860	// create a new node that will hold the rays
861	VssTreeLeaf *newLeaf = new VssTreeLeaf( sroot->parent, rayCount );
862	if ( newLeaf->parent )
863	newLeaf->parent->ReplaceChildLink(sroot, newLeaf);
864
865
866	tstack.push( sroot );
867
868	while (!tstack.empty()) {
869
870	VssTreeNode *node = tstack.top();
871	tstack.pop();
872
873	if (node->IsLeaf()) {
874	VssTreeLeaf leaf = (VssTreeLeaf ) node;
875
876	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
877	ri != leaf->rays.end();
878	ri++) {
879
880	// unref this ray from the old node
881
882	if ((*ri).mRay->IsActive()) {
883	(*ri).mRay->Unref();
884	if (!(*ri).mRay->Mailed()) {
885	(*ri).mRay->Mail();
886	newLeaf->AddRay(*ri);
887	}
888	} else
889	(*ri).mRay->Unref();
890
891	}
892	} else {
893	tstack.push(((VssTreeInterior *)node)->back);
894	tstack.push(((VssTreeInterior *)node)->front);
895	}
896	}
897
898	// delete the node and all its children
899	delete sroot;
900
901	// for(VssTreeNode::SRayContainer::iterator ri = newLeaf->rays.begin();
902	// ri != newLeaf->rays.end();
903	// ri++)
904	// (*ri).ray->UnMail(2);
905
906
907	#if DEBUG_COLLAPSE
908	cout<<"Total memory before="<<GetMemUsage()<<endl;
909	#endif
910
911	stat.nodes -= collapsedNodes - 1;
912	stat.rayRefs -= totalRayCount - rayCount;
913
914	#if DEBUG_COLLAPSE
915	cout<<"collapsed nodes"<<collapsedNodes<<endl;
916	cout<<"collapsed rays"<<totalRayCount - rayCount<<endl;
917	cout<<"Total memory after="<<GetMemUsage()<<endl;
918	cout<<"================================"<<endl;
919	#endif
920
921	// tstat.collapsedNodes += collapsedNodes;
922	// tstat.collapsedRays += totalRayCount - rayCount;
923
924	return totalRayCount - rayCount;
925	}

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

Download in other formats: