Context Navigation

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

Revision 386, 31.1 KB checked in by bittner, 19 years ago (diff)
VssPreprocessor? updates - directional rays, x3dexporter updates - removed duplicated code for ray exports

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
26
27	#define DEBUG_DIR_SPLIT 0
28
29
30
31	// Static variables
32	int
33	VssTreeLeaf::mailID = 0;
34
35	inline void
36	AddObject2Pvs(Intersectable *object,
37	const int side,
38	int &pvsBack,
39	int &pvsFront)
40	{
41
42	if (!object)
43	return;
44
45	if (side <= 0) {
46	if (!object->Mailed() && !object->Mailed(2)) {
47	pvsBack++;
48	if (object->Mailed(1))
49	object->Mail(2);
50	else
51	object->Mail();
52	}
53	}
54
55	if (side >= 0) {
56	if (!object->Mailed(1) && !object->Mailed(2)) {
57	pvsFront++;
58	if (object->Mailed())
59	object->Mail(2);
60	else
61	object->Mail(1);
62	}
63	}
64	}
65
66
67	// Constructor
68	VssTree::VssTree()
69	{
70	environment->GetIntValue("VssTree.maxDepth", termMaxDepth);
71	environment->GetIntValue("VssTree.minPvs", termMinPvs);
72	environment->GetFloatValue("VssTree.maxRayContribution", termMaxRayContribution);
73	environment->GetFloatValue("VssTree.maxCostRatio", termMaxCostRatio);
74
75	environment->GetFloatValue("VssTree.minSize", termMinSize);
76	termMinSize = sqr(termMinSize);
77
78	environment->GetFloatValue("VssTree.refDirBoxMaxSize", refDirBoxMaxSize);
79	refDirBoxMaxSize = sqr(refDirBoxMaxSize);
80
81	environment->GetFloatValue("VssTree.epsilon", epsilon);
82	environment->GetFloatValue("VssTree.ct_div_ci", ct_div_ci);
83
84	environment->GetFloatValue("VssTree.maxTotalMemory", maxTotalMemory);
85	environment->GetFloatValue("VssTree.maxStaticMemory", maxStaticMemory);
86
87
88
89
90	float refDirAngle;
91	environment->GetFloatValue("VssTree.refDirAngle", refDirAngle);
92
93	environment->GetIntValue("VssTree.accessTimeThreshold", accessTimeThreshold);
94	//= 1000;
95	environment->GetIntValue("VssTree.minCollapseDepth", minCollapseDepth);
96	// int minCollapseDepth = 4;
97
98	// pRefDirThresh = cos(0.5M_PI - M_PIrefDirAngle/180.0);
99	// cosRefDir = cos(M_PI*refDirAngle/180.0);
100	// sinRefDir = sin(M_PI*refDirAngle/180.0);
101
102
103	// split type
104	char sname[128];
105	environment->GetStringValue("VssTree.splitType", sname);
106	string name(sname);
107
108	if (name.compare("regular") == 0)
109	splitType = ESplitRegular;
110	else
111	if (name.compare("heuristic") == 0)
112	splitType = ESplitHeuristic;
113	else {
114	cerr<<"Invalid VssTree split type "<<name<<endl;
115	exit(1);
116	}
117
118	environment->GetBoolValue("VssTree.randomize", randomize);
119
120	root = NULL;
121
122	splitCandidates = new vector<SortableEntry>;
123	}
124
125
126	VssTree::~VssTree()
127	{
128	if (root)
129	delete root;
130	}
131
132
133
134
135	void
136	VssStatistics::Print(ostream &app) const
137	{
138	app << "===== VssTree statistics ===============\n";
139
140	app << "#N_RAYS ( Number of rays )\n"
141	<< rays <<endl;
142
143	app << "#N_INITPVS ( Initial PVS size )\n"
144	<< initialPvsSize <<endl;
145
146	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
147
148	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
149
150	app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n";
151	for (int i=0; i<7; i++)
152	app << splits[i] <<" ";
153	app <<endl;
154
155	app << "#N_RAYREFS ( Number of rayRefs )\n" <<
156	rayRefs << "\n";
157
158	app << "#N_RAYRAYREFS ( Number of rayRefs / ray )\n" <<
159	rayRefs/(double)rays << "\n";
160
161	app << "#N_LEAFRAYREFS ( Number of rayRefs / leaf )\n" <<
162	rayRefs/(double)Leaves() << "\n";
163
164	app << "#N_MAXRAYREFS ( Max number of rayRefs / leaf )\n" <<
165	maxRayRefs << "\n";
166
167
168	// app << setprecision(4);
169
170	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
171	maxDepthNodes*100/(double)Leaves()<<endl;
172
173	app << "#N_PMINCOSTLEAVES ( Percentage of leaves with minCost )\n"<<
174	minCostNodes*100/(double)Leaves()<<endl;
175
176	app << "#N_PMINSIZELEAVES ( Percentage of leaves with minSize )\n"<<
177	minSizeNodes*100/(double)Leaves()<<endl;
178
179	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"<<
180	maxRayContribNodes*100/(double)Leaves()<<endl;
181
182	app << "#N_ADDED_RAYREFS (Number of dynamically added ray references )\n"<<
183	addedRayRefs<<endl;
184
185	app << "#N_REMOVED_RAYREFS (Number of dynamically removed ray references )\n"<<
186	removedRayRefs<<endl;
187
188	// app << setprecision(4);
189
190	app << "#N_CTIME ( Construction time [s] )\n"
191	<< Time() << " \n";
192
193	app << "===== END OF VssTree statistics ==========\n";
194
195	}
196
197
198
199
200	void
201	VssTree::Construct(
202	VssRayContainer &rays,
203	AxisAlignedBox3 *forcedBoundingBox
204	)
205	{
206	stat.Start();
207
208	maxMemory = maxStaticMemory;
209
210	if (root)
211	delete root;
212
213	root = new VssTreeLeaf(NULL, rays.size());
214	// first construct a leaf that will get subdivide
215	VssTreeLeaf leaf = (VssTreeLeaf ) root;
216
217	stat.nodes = 1;
218
219	bbox.Initialize();
220	dirBBox.Initialize();
221
222	for(VssRayContainer::const_iterator ri = rays.begin();
223	ri != rays.end();
224	ri++) {
225	leaf->AddRay(VssTreeNode::RayInfo(*ri));
226
227	bbox.Include((*ri)->GetOrigin());
228	bbox.Include((*ri)->GetTermination());
229
230
231	dirBBox.Include(Vector3(
232	(*ri)->GetDirParametrization(0),
233	(*ri)->GetDirParametrization(1),
234	0
235	)
236	);
237	}
238
239
240	if (forcedBoundingBox)
241	bbox = *forcedBoundingBox;
242
243	cout<<"Bbox = "<<bbox<<endl;
244	cout<<"Dirr Bbox = "<<dirBBox<<endl;
245
246	stat.rays = leaf->rays.size();
247	EvalLeafPvs(leaf);
248	stat.initialPvsSize = leaf->mPvsSize;
249	// Subdivide();
250	root = Subdivide(TraversalData(leaf, bbox, 0));
251
252	if (splitCandidates) {
253	// force realease of this vector
254	delete splitCandidates;
255	splitCandidates = new vector<SortableEntry>;
256	}
257
258	stat.Stop();
259
260	stat.Print(cout);
261	cout<<"#Total memory="<<GetMemUsage()<<endl;
262
263	}
264
265	void
266	VssTree::EvalLeafPvs(VssTreeLeaf *leaf)
267	{
268	Intersectable::NewMail();
269	int pvsSize = 0;
270	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
271	ri != leaf->rays.end();
272	ri++)
273	if ((*ri).mRay->IsActive()) {
274	Intersectable object = (ri).mRay->mOriginObject;
275	if (object && !object->Mailed()) {
276	pvsSize++;
277	object->Mail();
278	}
279	object = (*ri).mRay->mTerminationObject;
280	if (object && !object->Mailed()) {
281	pvsSize++;
282	object->Mail();
283	}
284	}
285	leaf->mPvsSize = pvsSize;
286	}
287
288
289	VssTreeNode *
290	VssTree::Subdivide(const TraversalData &tdata)
291	{
292	VssTreeNode *result = NULL;
293
294	priority_queue<TraversalData> tStack;
295	// stack<TraversalData> tStack;
296
297	tStack.push(tdata);
298
299	AxisAlignedBox3 backBox;
300	AxisAlignedBox3 frontBox;
301
302
303	int lastMem = 0;
304	while (!tStack.empty()) {
305
306	float mem = GetMemUsage();
307
308	if ( lastMem/10 != ((int)mem)/10) {
309	cout<<mem<<" MB"<<endl;
310	}
311	lastMem = (int)mem;
312
313	if ( mem > maxMemory ) {
314	// count statistics on unprocessed leafs
315	while (!tStack.empty()) {
316	EvaluateLeafStats(tStack.top());
317	tStack.pop();
318	}
319	break;
320	}
321
322	TraversalData data = tStack.top();
323	tStack.pop();
324
325	VssTreeNode node = SubdivideNode((VssTreeLeaf ) data.node,
326	data.bbox,
327	backBox,
328	frontBox
329	);
330	if (result == NULL)
331	result = node;
332
333	if (!node->IsLeaf()) {
334
335	VssTreeInterior interior = (VssTreeInterior ) node;
336	// push the children on the stack
337	tStack.push(TraversalData(interior->back, backBox, data.depth+1));
338	tStack.push(TraversalData(interior->front, frontBox, data.depth+1));
339
340	} else {
341	EvaluateLeafStats(data);
342	}
343	}
344
345	return result;
346	}
347
348
349	// returns selected plane for subdivision
350	int
351	VssTree::SelectPlane(
352	VssTreeLeaf *leaf,
353	const AxisAlignedBox3 &box,
354	float &position,
355	int &raysBack,
356	int &raysFront,
357	int &pvsBack,
358	int &pvsFront
359	)
360	{
361
362	int minDirDepth = 6;
363	int axis;
364	float costRatio;
365
366	if (splitType == ESplitRegular) {
367	int sRaysBack, sRaysFront;
368	int dRaysBack, dRaysFront;
369	int sPvsBack, sPvsFront;
370	int dPvsBack, dPvsFront;
371
372
373	int sAxis = box.Size().DrivingAxis();
374	float sPosition = (box.Min()[sAxis] + box.Max()[sAxis])*0.5f;
375	float sCostRatio = EvalCostRatio(leaf,
376	sAxis,
377	sPosition,
378	sRaysBack,
379	sRaysFront,
380	sPvsBack,
381	sPvsFront
382	);
383	// cout<<"srays back="<<sRaysBack<<" rays front="<<sRaysFront<<" pvs back="<<sPvsBack<<
384	// " pvs front="<<sPvsFront<<endl;
385
386	AxisAlignedBox3 dirBox = GetDirBBox(leaf);
387	int dAxis = dirBox.Size().DrivingAxis();
388	float dPosition = (dirBox.Min()[dAxis] + dirBox.Max()[dAxis])*0.5f;
389	float dCostRatio = EvalCostRatio(leaf,
390	dAxis+3,
391	dPosition,
392	dRaysBack,
393	dRaysFront,
394	dPvsBack,
395	dPvsFront
396	);
397
398	// cout<<"drays back="<<dRaysBack<<" rays front="<<dRaysFront<<" pvs back="<<dPvsBack<<
399	// " pvs front="<<dPvsFront<<endl;
400
401	if (sCostRatio < dCostRatio) {
402	costRatio = sCostRatio;
403	axis = sAxis;
404	position = sPosition;
405	raysBack = sRaysBack;
406	raysFront = sRaysFront;
407	pvsBack = sPvsBack;
408	pvsFront = sPvsFront;
409
410	} else {
411	costRatio = dCostRatio;
412	axis = dAxis+3;
413	position = dPosition;
414	raysBack = dRaysBack;
415	raysFront = dRaysFront;
416	pvsBack = dPvsBack;
417	pvsFront = dPvsFront;
418	}
419
420	} else {
421	if (splitType == ESplitHeuristic)
422	costRatio = BestCostRatioHeuristic(leaf,
423	axis,
424	position,
425	raysBack,
426	raysFront,
427	pvsBack,
428	pvsFront
429	);
430	else {
431	cerr<<"VssTree: Unknown split heuristics\n";
432	exit(1);
433	}
434	}
435
436	if (costRatio > termMaxCostRatio) {
437	// cout<<"Too big cost ratio "<<costRatio<<endl;
438	return -1;
439	}
440
441	#if 0
442	cout<<
443	"pvs="<<leaf->mPvsSize<<
444	" rays="<<leaf->rays.size()<<
445	" rc="<<leaf->GetAvgRayContribution()<<
446	" axis="<<axis<<endl;
447	#endif
448
449	return axis;
450	}
451
452
453
454
455	float
456	VssTree::EvalCostRatio(
457	VssTreeLeaf *leaf,
458	const int axis,
459	const float position,
460	int &raysBack,
461	int &raysFront,
462	int &pvsBack,
463	int &pvsFront
464	)
465	{
466	raysBack = 0;
467	raysFront = 0;
468	pvsFront = 0;
469	pvsBack = 0;
470
471	float newCost;
472
473	Intersectable::NewMail(3);
474
475	// eval pvs size
476	int pvsSize = leaf->mPvsSize;
477
478	Intersectable::NewMail(3);
479
480	if (axis <= VssTreeNode::SPLIT_Z) {
481	// this is the main ray classification loop!
482	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
483	ri != leaf->rays.end();
484	ri++)
485	if ((*ri).mRay->IsActive()) {
486
487	// determine the side of this ray with respect to the plane
488	int side = (ri).ComputeRayIntersection(axis, position, (ri).mRay->mT);
489
490	// (*ri).mRay->mSide = side;
491
492	if (side <= 0)
493	raysBack++;
494
495	if (side >= 0)
496	raysFront++;
497
498	#if BIDIRECTIONAL_RAY
499	AddObject2Pvs((*ri).mRay->mOriginObject, side, pvsBack, pvsFront);
500	#endif
501	AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
502
503	}
504
505	AxisAlignedBox3 box = GetBBox(leaf);
506
507	float minBox = box.Min(axis);
508	float maxBox = box.Max(axis);
509	float sizeBox = maxBox - minBox;
510
511	// float sum = raysBack(position - minBox) + raysFront(maxBox - position);
512	float sum = pvsBack(position - minBox) + pvsFront(maxBox - position);
513
514	newCost = ct_div_ci + sum/sizeBox;
515
516	} else {
517
518	// directional split
519	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
520	ri != leaf->rays.end();
521	ri++)
522	if ((*ri).mRay->IsActive()) {
523
524	// determine the side of this ray with respect to the plane
525	int side;
526	if ((*ri).mRay->GetDirParametrization(axis - 3) > position)
527	side = 1;
528	else
529	side = -1;
530
531	if (side <= 0)
532	raysBack++;
533
534	if (side >= 0)
535	raysFront++;
536
537	// (*ri).mRay->mSide = side;
538
539	#if BIDIRECTIONAL_RAY
540	AddObject2Pvs((*ri).mRay->mOriginObject, side, pvsBack, pvsFront);
541	#endif
542	AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
543
544	}
545
546	AxisAlignedBox3 box = GetDirBBox(leaf);
547
548	float minBox = box.Min(axis-3);
549	float maxBox = box.Max(axis-3);
550	float sizeBox = maxBox - minBox;
551
552	// float sum = raysBack(position - minBox) + raysFront(maxBox - position);
553	float sum = pvsBack(position - minBox) + pvsFront(maxBox - position);
554	// float sum = pvsBack + pvsFront;
555	newCost = ct_div_ci + sum/sizeBox;
556	}
557
558	// cout<<axis<<" "<<pvsSize<<" "<<pvsBack<<" "<<pvsFront<<endl;
559	// float oldCost = leaf->rays.size();
560	float oldCost = pvsSize;
561	float ratio = newCost/oldCost;
562	// cout<<"ratio="<<ratio<<endl;
563	return ratio;
564	}
565
566	float
567	VssTree::BestCostRatioRegular(
568	VssTreeLeaf *node,
569	int &axis,
570	float &position,
571	int &raysBack,
572	int &raysFront,
573	int &pvsBack,
574	int &pvsFront
575
576	)
577	{
578
579	return 0;
580	}
581
582	float
583	VssTree::BestCostRatioHeuristic(
584	VssTreeLeaf *node,
585	int &axis,
586	float &position,
587	int &raysBack,
588	int &raysFront,
589	int &pvsBack,
590	int &pvsFront
591	)
592	{
593	AxisAlignedBox3 box = GetBBox(node);
594	AxisAlignedBox3 dirBox = GetDirBBox(node);
595
596	axis = box.Size().DrivingAxis();
597
598	SortSplitCandidates(node, axis);
599
600	// go through the lists, count the number of objects left and right
601	// and evaluate the following cost funcion:
602	// C = ct_div_ci + (qlrl + qrrr)/queries
603
604	int rl=0, rr=node->rays.size();
605
606	float minBox = box.Min(axis);
607	float maxBox = box.Max(axis);
608	float sizeBox = maxBox - minBox;
609
610	float minBand = minBox + 0.1*(maxBox - minBox);
611	float maxBand = minBox + 0.9*(maxBox - minBox);
612
613	float sum = rr*sizeBox;
614	float minSum = 1e20;
615
616	for(vector<SortableEntry>::const_iterator ci = splitCandidates->begin();
617	ci < splitCandidates->end();
618	ci++) {
619
620	switch ((*ci).type) {
621	case SortableEntry::ERayMin:
622	rl++;
623	break;
624	case SortableEntry::ERayMax:
625	rr--;
626	break;
627	}
628
629	if ((ci).value > minBand && (ci).value < maxBand) {
630
631	sum = rl((ci).value - minBox) + rr(maxBox - (ci).value);
632
633	// cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
634	// cout<<"cost= "<<sum<<endl;
635
636	if (sum < minSum) {
637	minSum = sum;
638	position = (*ci).value;
639
640	raysBack = rl;
641	raysFront = rr;
642
643	}
644	}
645	}
646
647	float oldCost = node->rays.size();
648	float newCost = ct_div_ci + minSum/sizeBox;
649	float ratio = newCost/oldCost;
650
651	// cout<<"===================="<<endl;
652	// cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
653	// <<"\t q=("<<queriesBack<<","<<queriesFront<<")\t r=("<<raysBack<<","<<raysFront<<")"<<endl;
654
655	return ratio;
656	}
657
658	void
659	VssTree::SortSplitCandidates(
660	VssTreeLeaf *node,
661	const int axis
662	)
663	{
664
665	splitCandidates->clear();
666
667	int requestedSize = 2*(node->rays.size());
668	// creates a sorted split candidates array
669	if (splitCandidates->capacity() > 500000 &&
670	requestedSize < (int)(splitCandidates->capacity()/10) ) {
671
672	delete splitCandidates;
673	splitCandidates = new vector<SortableEntry>;
674	}
675
676	splitCandidates->reserve(requestedSize);
677
678	// insert all queries
679	for(VssTreeNode::RayInfoContainer::const_iterator ri = node->rays.begin();
680	ri < node->rays.end();
681	ri++) {
682	bool positive = (*ri).mRay->HasPosDir(axis);
683	splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin :
684	SortableEntry::ERayMax,
685	(*ri).ExtrapOrigin(axis),
686	(void )&ri)
687	);
688
689	splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax :
690	SortableEntry::ERayMin,
691	(*ri).ExtrapTermination(axis),
692	(void )&ri)
693	);
694	}
695
696	stable_sort(splitCandidates->begin(), splitCandidates->end());
697	}
698
699
700	void
701	VssTree::EvaluateLeafStats(const TraversalData &data)
702	{
703
704	// the node became a leaf -> evaluate stats for leafs
705	VssTreeLeaf leaf = (VssTreeLeaf )data.node;
706
707	if (data.depth >= termMaxDepth)
708	stat.maxDepthNodes++;
709
710	// if ( (int)(leaf->rays.size()) < termMinCost)
711	// stat.minCostNodes++;
712	if ( leaf->mPvsSize < termMinPvs)
713	stat.minCostNodes++;
714
715	if (leaf->GetAvgRayContribution() > termMaxRayContribution )
716	stat.maxRayContribNodes++;
717
718	if (SqrMagnitude(data.bbox.Size()) <= termMinSize) {
719	stat.minSizeNodes++;
720	}
721
722	if ( (int)(leaf->rays.size()) > stat.maxRayRefs)
723	stat.maxRayRefs = leaf->rays.size();
724
725	}
726
727
728
729	VssTreeNode *
730	VssTree::SubdivideNode(
731	VssTreeLeaf *leaf,
732	const AxisAlignedBox3 &box,
733	AxisAlignedBox3 &backBBox,
734	AxisAlignedBox3 &frontBBox
735	)
736	{
737
738	if ( (leaf->mPvsSize < termMinPvs) \|\|
739	(leaf->GetAvgRayContribution() > termMaxRayContribution ) \|\|
740	(leaf->depth >= termMaxDepth) \|\|
741	SqrMagnitude(box.Size()) <= termMinSize ) {
742
743	#if 0
744	if (leaf->depth >= termMaxDepth) {
745	cout<<"Warning: max depth reached depth="<<(int)leaf->depth<<" rays="<<leaf->rays.size()<<endl;
746	cout<<"Bbox: "<<GetBBox(leaf)<<" dirbbox:"<<GetDirBBox(leaf)<<endl;
747	}
748	#endif
749
750	return leaf;
751	}
752
753	float position;
754
755	// first count ray sides
756	int raysBack;
757	int raysFront;
758	int pvsBack;
759	int pvsFront;
760
761	// select subdivision axis
762	int axis = SelectPlane( leaf, box, position, raysBack, raysFront, pvsBack, pvsFront);
763
764	// cout<<"rays back="<<raysBack<<" rays front="<<raysFront<<" pvs back="<<pvsBack<<" pvs front="<<
765	// pvsFront<<endl;
766
767	if (axis == -1) {
768	return leaf;
769	}
770
771	stat.nodes+=2;
772	stat.splits[axis]++;
773
774	// add the new nodes to the tree
775	VssTreeInterior *node = new VssTreeInterior(leaf->parent);
776
777	node->axis = axis;
778	node->position = position;
779	node->bbox = box;
780	node->dirBBox = GetDirBBox(leaf);
781
782	backBBox = box;
783	frontBBox = box;
784
785	VssTreeLeaf *back = new VssTreeLeaf(node, raysBack);
786	back->mPvsSize = pvsBack;
787	VssTreeLeaf *front = new VssTreeLeaf(node, raysFront);
788	front->mPvsSize = pvsFront;
789
790	// replace a link from node's parent
791	if ( leaf->parent )
792	leaf->parent->ReplaceChildLink(leaf, node);
793	// and setup child links
794	node->SetupChildLinks(back, front);
795
796	if (axis <= VssTreeNode::SPLIT_Z) {
797	backBBox.SetMax(axis, position);
798	frontBBox.SetMin(axis, position);
799
800	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
801	ri != leaf->rays.end();
802	ri++) {
803	if ((*ri).mRay->IsActive()) {
804
805	// first unref ray from the former leaf
806	(*ri).mRay->Unref();
807
808	// determine the side of this ray with respect to the plane
809	int side = node->ComputeRayIntersection(ri, (ri).mRay->mT);
810
811	if (side == 0) {
812	if ((*ri).mRay->HasPosDir(axis)) {
813	back->AddRay(VssTreeNode::RayInfo((*ri).mRay,
814	(*ri).mMinT,
815	(*ri).mRay->mT)
816	);
817	front->AddRay(VssTreeNode::RayInfo((*ri).mRay,
818	(*ri).mRay->mT,
819	(*ri).mMaxT));
820	} else {
821	back->AddRay(VssTreeNode::RayInfo((*ri).mRay,
822	(*ri).mRay->mT,
823	(*ri).mMaxT));
824	front->AddRay(VssTreeNode::RayInfo((*ri).mRay,
825	(*ri).mMinT,
826	(*ri).mRay->mT));
827	}
828	} else
829	if (side == 1)
830	front->AddRay(*ri);
831	else
832	back->AddRay(*ri);
833	} else
834	(*ri).mRay->Unref();
835	}
836	} else {
837	// rays front/back
838
839
840	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
841	ri != leaf->rays.end();
842	ri++) {
843	if ((*ri).mRay->IsActive()) {
844	// first unref ray from the former leaf
845	(*ri).mRay->Unref();
846
847	int side;
848	if ((*ri).mRay->GetDirParametrization(axis - 3) > position)
849	side = 1;
850	else
851	side = -1;
852
853	if (side == 1)
854	front->AddRay(*ri);
855	else
856	back->AddRay(*ri);
857
858	} else
859	(*ri).mRay->Unref();
860	}
861	}
862
863	// update stats
864	stat.rayRefs -= leaf->rays.size();
865	stat.rayRefs += raysBack + raysFront;
866
867
868	delete leaf;
869	return node;
870	}
871
872
873
874
875
876
877	int
878	VssTree::ReleaseMemory(const int time)
879	{
880	stack<VssTreeNode *> tstack;
881
882	// find a node in the tree which subtree will be collapsed
883	int maxAccessTime = time - accessTimeThreshold;
884	int released;
885
886	tstack.push(root);
887
888	while (!tstack.empty()) {
889	VssTreeNode *node = tstack.top();
890	tstack.pop();
891
892
893	if (!node->IsLeaf()) {
894	VssTreeInterior in = (VssTreeInterior )node;
895	// cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
896	if (in->depth >= minCollapseDepth &&
897	in->lastAccessTime <= maxAccessTime) {
898	released = CollapseSubtree(node, time);
899	break;
900	}
901
902	if (in->back->GetAccessTime() <
903	in->front->GetAccessTime()) {
904	tstack.push(in->front);
905	tstack.push(in->back);
906	} else {
907	tstack.push(in->back);
908	tstack.push(in->front);
909	}
910	}
911	}
912
913	while (tstack.empty()) {
914	// could find node to collaps...
915	// cout<<"Could not find a node to release "<<endl;
916	break;
917	}
918
919	return released;
920	}
921
922
923
924
925	VssTreeNode *
926	VssTree::SubdivideLeaf(
927	VssTreeLeaf *leaf,
928	const float sizeThreshold
929	)
930	{
931	VssTreeNode *node = leaf;
932
933	AxisAlignedBox3 leafBBox = GetBBox(leaf);
934
935	static int pass = 0;
936	pass ++;
937
938	// check if we should perform a dynamic subdivision of the leaf
939	if (
940	// leaf->rays.size() > (unsigned)termMinCost &&
941	(leaf->mPvsSize >= termMinPvs) &&
942	SqrMagnitude(leafBBox.Size()) > sizeThreshold) {
943
944	// memory check and realese...
945	if (GetMemUsage() > maxTotalMemory) {
946	ReleaseMemory( pass );
947	}
948
949	AxisAlignedBox3 backBBox, frontBBox;
950
951	// subdivide the node
952	node =
953	SubdivideNode(leaf,
954	leafBBox,
955	backBBox,
956	frontBBox
957	);
958	}
959	return node;
960	}
961
962
963
964	void
965	VssTree::UpdateRays(VssRayContainer &remove,
966	VssRayContainer &add
967	)
968	{
969	VssTreeLeaf::NewMail();
970
971	// schedule rays for removal
972	for(VssRayContainer::const_iterator ri = remove.begin();
973	ri != remove.end();
974	ri++) {
975	(*ri)->ScheduleForRemoval();
976	}
977
978	int inactive=0;
979
980	for(VssRayContainer::const_iterator ri = remove.begin();
981	ri != remove.end();
982	ri++) {
983	if ((*ri)->ScheduledForRemoval())
984	// RemoveRay(*ri, NULL, false);
985	// !!! BUG - with true it does not work correctly - aggreated delete
986	RemoveRay(*ri, NULL, true);
987	else
988	inactive++;
989	}
990
991
992	// cout<<"all/inactive"<<remove.size()<<"/"<<inactive<<endl;
993
994	for(VssRayContainer::const_iterator ri = add.begin();
995	ri != add.end();
996	ri++) {
997	AddRay(*ri);
998	}
999
1000
1001	}
1002
1003
1004	void
1005	VssTree::RemoveRay(VssRay *ray,
1006	vector<VssTreeLeaf > affectedLeaves,
1007	const bool removeAllScheduledRays
1008	)
1009	{
1010
1011	stack<RayTraversalData> tstack;
1012
1013	tstack.push(RayTraversalData(root, VssTreeNode::RayInfo(ray)));
1014
1015	RayTraversalData data;
1016
1017	// cout<<"Number of ray refs = "<<ray->RefCount()<<endl;
1018
1019	while (!tstack.empty()) {
1020	data = tstack.top();
1021	tstack.pop();
1022
1023	if (!data.node->IsLeaf()) {
1024	// split the set of rays in two groups intersecting the
1025	// two subtrees
1026
1027	TraverseInternalNode(data, tstack);
1028
1029	} else {
1030	// remove the ray from the leaf
1031	// find the ray in the leaf and swap it with the last ray...
1032	VssTreeLeaf leaf = (VssTreeLeaf )data.node;
1033
1034	if (!leaf->Mailed()) {
1035	leaf->Mail();
1036	if (affectedLeaves)
1037	affectedLeaves->push_back(leaf);
1038
1039	if (removeAllScheduledRays) {
1040	int tail = leaf->rays.size()-1;
1041
1042	for (int i=0; i < (int)(leaf->rays.size()); i++) {
1043	if (leaf->rays[i].mRay->ScheduledForRemoval()) {
1044	// find a ray to replace it with
1045	while (tail >= i && leaf->rays[tail].mRay->ScheduledForRemoval()) {
1046	stat.removedRayRefs++;
1047	leaf->rays[tail].mRay->Unref();
1048	leaf->rays.pop_back();
1049	tail--;
1050	}
1051
1052	if (tail < i)
1053	break;
1054
1055	stat.removedRayRefs++;
1056	leaf->rays[i].mRay->Unref();
1057	leaf->rays[i] = leaf->rays[tail];
1058	leaf->rays.pop_back();
1059	tail--;
1060	}
1061	}
1062	}
1063	}
1064
1065	if (!removeAllScheduledRays)
1066	for (int i=0; i < (int)leaf->rays.size(); i++) {
1067	if (leaf->rays[i].mRay == ray) {
1068	stat.removedRayRefs++;
1069	ray->Unref();
1070	leaf->rays[i] = leaf->rays[leaf->rays.size()-1];
1071	leaf->rays.pop_back();
1072	// check this ray again
1073	break;
1074	}
1075	}
1076
1077	}
1078	}
1079
1080	if (ray->RefCount() != 0) {
1081	cerr<<"Error: Number of remaining refs = "<<ray->RefCount()<<endl;
1082	exit(1);
1083	}
1084
1085	}
1086
1087
1088	void
1089	VssTree::AddRay(VssRay *ray)
1090	{
1091
1092	stack<RayTraversalData> tstack;
1093
1094	tstack.push(RayTraversalData(root, VssTreeNode::RayInfo(ray)));
1095
1096	RayTraversalData data;
1097
1098	while (!tstack.empty()) {
1099	data = tstack.top();
1100	tstack.pop();
1101
1102	if (!data.node->IsLeaf()) {
1103
1104	TraverseInternalNode(data, tstack);
1105
1106	} else {
1107	// remove the ray from the leaf
1108	// find the ray in the leaf and swap it with the last ray...
1109	VssTreeLeaf leaf = (VssTreeLeaf )data.node;
1110	leaf->AddRay(data.rayData);
1111	stat.addedRayRefs++;
1112	}
1113	}
1114	}
1115
1116	void
1117	VssTree::TraverseInternalNode(
1118	RayTraversalData &data,
1119	stack<RayTraversalData> &tstack)
1120	{
1121	VssTreeInterior in = (VssTreeInterior ) data.node;
1122
1123	if (in->axis <= VssTreeNode::SPLIT_Z) {
1124
1125	// determine the side of this ray with respect to the plane
1126	int side = in->ComputeRayIntersection(data.rayData,
1127	data.rayData.mRay->mT);
1128
1129
1130	if (side == 0) {
1131	if (data.rayData.mRay->HasPosDir(in->axis)) {
1132	tstack.push(RayTraversalData(in->back,
1133	VssTreeNode::RayInfo(data.rayData.mRay,
1134	data.rayData.mMinT,
1135	data.rayData.mRay->mT))
1136	);
1137
1138	tstack.push(RayTraversalData(in->front,
1139	VssTreeNode::RayInfo(data.rayData.mRay,
1140	data.rayData.mRay->mT,
1141	data.rayData.mMaxT
1142	))
1143	);
1144
1145	} else {
1146	tstack.push(RayTraversalData(in->back,
1147	VssTreeNode::RayInfo(data.rayData.mRay,
1148	data.rayData.mRay->mT,
1149	data.rayData.mMaxT
1150	))
1151	);
1152
1153	tstack.push(RayTraversalData(in->front,
1154	VssTreeNode::RayInfo(data.rayData.mRay,
1155	data.rayData.mMinT,
1156	data.rayData.mRay->mT))
1157	);
1158
1159
1160	}
1161	} else
1162	if (side == 1)
1163	tstack.push(RayTraversalData(in->front, data.rayData));
1164	else
1165	tstack.push(RayTraversalData(in->back, data.rayData));
1166	}
1167	else {
1168	// directional split
1169	// if (DotProd(data.rayData.mRay->GetNormalizedDir(), in->refDir) > sinRefDir )
1170	// tstack.push(RayTraversalData(in->front, data.rayData));
1171	// else
1172	// tstack.push(RayTraversalData(in->back, data.rayData));
1173	}
1174
1175	}
1176
1177
1178	int
1179	VssTree::CollapseSubtree(VssTreeNode *sroot, const int time)
1180	{
1181	// first count all rays in the subtree
1182	// use mail 1 for this purpose
1183	stack<VssTreeNode *> tstack;
1184	int rayCount = 0;
1185	int totalRayCount = 0;
1186	int collapsedNodes = 0;
1187
1188	#if DEBUG_COLLAPSE
1189	cout<<"Collapsing subtree"<<endl;
1190	cout<<"acessTime="<<sroot->GetAccessTime()<<endl;
1191	cout<<"depth="<<(int)sroot->depth<<endl;
1192	#endif
1193
1194	// tstat.collapsedSubtrees++;
1195	// tstat.collapseDepths += (int)sroot->depth;
1196	// tstat.collapseAccessTimes += time - sroot->GetAccessTime();
1197
1198	tstack.push(sroot);
1199	VssRay::NewMail();
1200
1201	while (!tstack.empty()) {
1202	collapsedNodes++;
1203	VssTreeNode *node = tstack.top();
1204	tstack.pop();
1205
1206	if (node->IsLeaf()) {
1207	VssTreeLeaf leaf = (VssTreeLeaf ) node;
1208	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
1209	ri != leaf->rays.end();
1210	ri++) {
1211
1212	totalRayCount++;
1213	if ((ri).mRay->IsActive() && !(ri).mRay->Mailed()) {
1214	(*ri).mRay->Mail();
1215	rayCount++;
1216	}
1217	}
1218	} else {
1219	tstack.push(((VssTreeInterior *)node)->back);
1220	tstack.push(((VssTreeInterior *)node)->front);
1221	}
1222	}
1223
1224	VssRay::NewMail();
1225
1226	// create a new node that will hold the rays
1227	VssTreeLeaf *newLeaf = new VssTreeLeaf( sroot->parent, rayCount );
1228	if ( newLeaf->parent )
1229	newLeaf->parent->ReplaceChildLink(sroot, newLeaf);
1230
1231
1232	tstack.push( sroot );
1233
1234	while (!tstack.empty()) {
1235
1236	VssTreeNode *node = tstack.top();
1237	tstack.pop();
1238
1239	if (node->IsLeaf()) {
1240	VssTreeLeaf leaf = (VssTreeLeaf ) node;
1241
1242	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
1243	ri != leaf->rays.end();
1244	ri++) {
1245
1246	// unref this ray from the old node
1247
1248	if ((*ri).mRay->IsActive()) {
1249	(*ri).mRay->Unref();
1250	if (!(*ri).mRay->Mailed()) {
1251	(*ri).mRay->Mail();
1252	newLeaf->AddRay(*ri);
1253	}
1254	} else
1255	(*ri).mRay->Unref();
1256
1257	}
1258	} else {
1259	tstack.push(((VssTreeInterior *)node)->back);
1260	tstack.push(((VssTreeInterior *)node)->front);
1261	}
1262	}
1263
1264	// delete the node and all its children
1265	delete sroot;
1266
1267	// for(VssTreeNode::SRayContainer::iterator ri = newLeaf->rays.begin();
1268	// ri != newLeaf->rays.end();
1269	// ri++)
1270	// (*ri).ray->UnMail(2);
1271
1272
1273	#if DEBUG_COLLAPSE
1274	cout<<"Total memory before="<<GetMemUsage()<<endl;
1275	#endif
1276
1277	stat.nodes -= collapsedNodes - 1;
1278	stat.rayRefs -= totalRayCount - rayCount;
1279
1280	#if DEBUG_COLLAPSE
1281	cout<<"collapsed nodes"<<collapsedNodes<<endl;
1282	cout<<"collapsed rays"<<totalRayCount - rayCount<<endl;
1283	cout<<"Total memory after="<<GetMemUsage()<<endl;
1284	cout<<"================================"<<endl;
1285	#endif
1286
1287	// tstat.collapsedNodes += collapsedNodes;
1288	// tstat.collapsedRays += totalRayCount - rayCount;
1289
1290	return totalRayCount - rayCount;
1291	}

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

Download in other formats: