Context Navigation

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

Revision 387, 32.8 KB checked in by bittner, 19 years ago (diff)
vss preprocessor 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
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;
275	#if BIDIRECTIONAL_RAY
276	object = (*ri).mRay->mOriginObject;
277	if (object && !object->Mailed()) {
278	pvsSize++;
279	object->Mail();
280	}
281	#endif
282	object = (*ri).mRay->mTerminationObject;
283	if (object && !object->Mailed()) {
284	pvsSize++;
285	object->Mail();
286	}
287	}
288	leaf->mPvsSize = pvsSize;
289	}
290
291
292	VssTreeNode *
293	VssTree::Subdivide(const TraversalData &tdata)
294	{
295	VssTreeNode *result = NULL;
296
297	priority_queue<TraversalData> tStack;
298	// stack<TraversalData> tStack;
299
300	tStack.push(tdata);
301
302	AxisAlignedBox3 backBox;
303	AxisAlignedBox3 frontBox;
304
305
306	int lastMem = 0;
307	while (!tStack.empty()) {
308
309	float mem = GetMemUsage();
310
311	if ( lastMem/10 != ((int)mem)/10) {
312	cout<<mem<<" MB"<<endl;
313	}
314	lastMem = (int)mem;
315
316	if ( mem > maxMemory ) {
317	// count statistics on unprocessed leafs
318	while (!tStack.empty()) {
319	EvaluateLeafStats(tStack.top());
320	tStack.pop();
321	}
322	break;
323	}
324
325	TraversalData data = tStack.top();
326	tStack.pop();
327
328	VssTreeNode node = SubdivideNode((VssTreeLeaf ) data.node,
329	data.bbox,
330	backBox,
331	frontBox
332	);
333	if (result == NULL)
334	result = node;
335
336	if (!node->IsLeaf()) {
337
338	VssTreeInterior interior = (VssTreeInterior ) node;
339	// push the children on the stack
340	tStack.push(TraversalData(interior->back, backBox, data.depth+1));
341	tStack.push(TraversalData(interior->front, frontBox, data.depth+1));
342
343	} else {
344	EvaluateLeafStats(data);
345	}
346	}
347
348	return result;
349	}
350
351
352	// returns selected plane for subdivision
353	int
354	VssTree::SelectPlane(
355	VssTreeLeaf *leaf,
356	const AxisAlignedBox3 &box,
357	float &position,
358	int &raysBack,
359	int &raysFront,
360	int &pvsBack,
361	int &pvsFront
362	)
363	{
364
365	int minDirDepth = 6;
366	int axis;
367	float costRatio;
368
369	if (splitType == ESplitRegular) {
370	costRatio = BestCostRatioRegular(leaf,
371	axis,
372	position,
373	raysBack,
374	raysFront,
375	pvsBack,
376	pvsFront
377	);
378
379	} else {
380	if (splitType == ESplitHeuristic)
381	costRatio = BestCostRatioHeuristic(leaf,
382	axis,
383	position,
384	raysBack,
385	raysFront,
386	pvsBack,
387	pvsFront
388	);
389	else {
390	cerr<<"VssTree: Unknown split heuristics\n";
391	exit(1);
392	}
393	}
394
395	if (costRatio > termMaxCostRatio) {
396	// cout<<"Too big cost ratio "<<costRatio<<endl;
397	return -1;
398	}
399
400	#if 0
401	cout<<
402	"pvs="<<leaf->mPvsSize<<
403	" rays="<<leaf->rays.size()<<
404	" rc="<<leaf->GetAvgRayContribution()<<
405	" axis="<<axis<<endl;
406	#endif
407
408	return axis;
409	}
410
411
412
413
414	float
415	VssTree::EvalCostRatio(
416	VssTreeLeaf *leaf,
417	const int axis,
418	const float position,
419	int &raysBack,
420	int &raysFront,
421	int &pvsBack,
422	int &pvsFront
423	)
424	{
425	raysBack = 0;
426	raysFront = 0;
427	pvsFront = 0;
428	pvsBack = 0;
429
430	float newCost;
431
432	Intersectable::NewMail(3);
433
434	// eval pvs size
435	int pvsSize = leaf->mPvsSize;
436
437	Intersectable::NewMail(3);
438
439	if (axis <= VssTreeNode::SPLIT_Z) {
440	// this is the main ray classification loop!
441	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
442	ri != leaf->rays.end();
443	ri++)
444	if ((*ri).mRay->IsActive()) {
445
446	// determine the side of this ray with respect to the plane
447	int side = (ri).ComputeRayIntersection(axis, position, (ri).mRay->mT);
448	// (*ri).mRay->mSide = side;
449
450	if (side <= 0)
451	raysBack++;
452
453	if (side >= 0)
454	raysFront++;
455
456	AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
457	}
458
459	AxisAlignedBox3 box = GetBBox(leaf);
460
461	float minBox = box.Min(axis);
462	float maxBox = box.Max(axis);
463	float sizeBox = maxBox - minBox;
464
465	// float sum = raysBack(position - minBox) + raysFront(maxBox - position);
466	float sum = pvsBack(position - minBox) + pvsFront(maxBox - position);
467
468	newCost = ct_div_ci + sum/sizeBox;
469
470	} else {
471
472	// directional split
473	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
474	ri != leaf->rays.end();
475	ri++)
476	if ((*ri).mRay->IsActive()) {
477
478	// determine the side of this ray with respect to the plane
479	int side;
480	if ((*ri).mRay->GetDirParametrization(axis - 3) > position)
481	side = 1;
482	else
483	side = -1;
484
485	if (side <= 0)
486	raysBack++;
487
488	if (side >= 0)
489	raysFront++;
490
491	// (*ri).mRay->mSide = side;
492	AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
493
494	}
495
496	AxisAlignedBox3 box = GetDirBBox(leaf);
497
498	float minBox = box.Min(axis-3);
499	float maxBox = box.Max(axis-3);
500	float sizeBox = maxBox - minBox;
501
502	// float sum = raysBack(position - minBox) + raysFront(maxBox - position);
503	float sum =
504	pvsBack*(position - minBox) +
505	pvsFront*(maxBox - position);
506	// float sum = pvsBack + pvsFront;
507	newCost = ct_div_ci + sum/sizeBox;
508	}
509
510	// cout<<axis<<" "<<pvsSize<<" "<<pvsBack<<" "<<pvsFront<<endl;
511	// float oldCost = leaf->rays.size();
512	float oldCost = pvsSize;
513	float ratio = newCost/oldCost;
514	// cout<<"ratio="<<ratio<<endl;
515	return ratio;
516	}
517
518	float
519	VssTree::BestCostRatioRegular(
520	VssTreeLeaf *leaf,
521	int &axis,
522	float &position,
523	int &raysBack,
524	int &raysFront,
525	int &pvsBack,
526	int &pvsFront
527	)
528	{
529	int nRaysBack[6], nRaysFront[6];
530	int nPvsBack[6], nPvsFront[6];
531	float nPosition[6];
532	float nCostRatio[6];
533	int bestAxis = -1;
534
535	AxisAlignedBox3 sBox = GetBBox(leaf);
536	AxisAlignedBox3 dBox = GetDirBBox(leaf);
537	// int sAxis = box.Size().DrivingAxis();
538	int sAxis = sBox.Size().DrivingAxis();
539	int dAxis = dBox.Size().DrivingAxis() + 3;
540
541	bool onlyDrivingAxis = true;
542
543	for (axis = 0; axis < 6; axis++) {
544	if (!onlyDrivingAxis \|\| axis == sAxis \|\| axis == dAxis) {
545	if (axis < 3)
546	nPosition[axis] = (sBox.Min()[axis] + sBox.Max()[axis])*0.5f;
547	else
548	nPosition[axis] = (dBox.Min()[axis-3] + dBox.Max()[axis-3])*0.5f;
549
550	nCostRatio[axis] = EvalCostRatio(leaf,
551	axis,
552	nPosition[axis],
553	nRaysBack[axis],
554	nRaysFront[axis],
555	nPvsBack[axis],
556	nPvsFront[axis]
557	);
558
559	if ( bestAxis == -1)
560	bestAxis = axis;
561	else
562	if ( nCostRatio[axis] < nCostRatio[bestAxis] )
563	bestAxis = axis;
564	}
565	}
566
567	axis = bestAxis;
568	position = nPosition[bestAxis];
569
570	raysBack = nRaysBack[bestAxis];
571	raysFront = nRaysFront[bestAxis];
572
573	pvsBack = nPvsBack[bestAxis];
574	pvsFront = nPvsFront[bestAxis];
575
576	return nCostRatio[bestAxis];
577	}
578
579	float
580	VssTree::BestCostRatioHeuristic(
581	VssTreeLeaf *leaf,
582	int &axis,
583	float &position,
584	int &raysBack,
585	int &raysFront,
586	int &pvsBack,
587	int &pvsFront
588	)
589	{
590	AxisAlignedBox3 box = GetBBox(leaf);
591	// AxisAlignedBox3 dirBox = GetDirBBox(node);
592
593	axis = box.Size().DrivingAxis();
594
595	SortSplitCandidates(leaf, axis);
596
597	// go through the lists, count the number of objects left and right
598	// and evaluate the following cost funcion:
599	// C = ct_div_ci + (qlrl + qrrr)/queries
600
601	int rl=0, rr = leaf->rays.size();
602	int pl=0, pr = leaf->mPvsSize;
603	float minBox = box.Min(axis);
604	float maxBox = box.Max(axis);
605	float sizeBox = maxBox - minBox;
606
607	float minBand = minBox + 0.1*(maxBox - minBox);
608	float maxBand = minBox + 0.9*(maxBox - minBox);
609
610	float sum = rr*sizeBox;
611	float minSum = 1e20;
612
613	Intersectable::NewMail();
614	// set all object as belonging to the fron pvs
615	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
616	ri != leaf->rays.end();
617	ri++)
618	if ((*ri).mRay->IsActive()) {
619	Intersectable object = (ri).mRay->mTerminationObject;
620	if (object)
621	if (!object->Mailed()) {
622	object->Mail();
623	object->mCounter = 1;
624	} else
625	object->mCounter++;
626	}
627
628	Intersectable::NewMail();
629
630	for(vector<SortableEntry>::const_iterator ci = splitCandidates->begin();
631	ci < splitCandidates->end();
632	ci++) {
633	VssRay *ray;
634	switch ((*ci).type) {
635	case SortableEntry::ERayMin: {
636	rl++;
637	ray = (VssRay ) (ci).data;
638	Intersectable *object = ray->mTerminationObject;
639	if (object && !object->Mailed()) {
640	object->Mail();
641	pl++;
642	}
643	break;
644	}
645	case SortableEntry::ERayMax: {
646	rr--;
647	ray = (VssRay ) (ci).data;
648	Intersectable *object = ray->mTerminationObject;
649	if (object) {
650	if (--object->mCounter == 0)
651	pr--;
652	}
653	break;
654	}
655	}
656	if ((ci).value > minBand && (ci).value < maxBand) {
657
658	sum = pl((ci).value - minBox) + pr(maxBox - (ci).value);
659
660	// cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
661	// cout<<"cost= "<<sum<<endl;
662
663	if (sum < minSum) {
664	minSum = sum;
665	position = (*ci).value;
666
667	raysBack = rl;
668	raysFront = rr;
669
670	pvsBack = pl;
671	pvsFront = pr;
672
673	}
674	}
675	}
676
677	float oldCost = leaf->mPvsSize;
678	float newCost = ct_div_ci + minSum/sizeBox;
679	float ratio = newCost/oldCost;
680
681	// cout<<"===================="<<endl;
682	// cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
683	// <<"\t q=("<<queriesBack<<","<<queriesFront<<")\t r=("<<raysBack<<","<<raysFront<<")"<<endl;
684	return ratio;
685	}
686
687	void
688	VssTree::SortSplitCandidates(
689	VssTreeLeaf *node,
690	const int axis
691	)
692	{
693
694	splitCandidates->clear();
695
696	int requestedSize = 2*(node->rays.size());
697	// creates a sorted split candidates array
698	if (splitCandidates->capacity() > 500000 &&
699	requestedSize < (int)(splitCandidates->capacity()/10) ) {
700
701	delete splitCandidates;
702	splitCandidates = new vector<SortableEntry>;
703	}
704
705	splitCandidates->reserve(requestedSize);
706
707	// insert all queries
708	for(VssTreeNode::RayInfoContainer::const_iterator ri = node->rays.begin();
709	ri < node->rays.end();
710	ri++) {
711	bool positive = (*ri).mRay->HasPosDir(axis);
712	splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin :
713	SortableEntry::ERayMax,
714	(*ri).ExtrapOrigin(axis),
715	(void )&ri)
716	);
717
718	splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax :
719	SortableEntry::ERayMin,
720	(*ri).ExtrapTermination(axis),
721	(void )&ri)
722	);
723	}
724
725	stable_sort(splitCandidates->begin(), splitCandidates->end());
726	}
727
728
729	void
730	VssTree::EvaluateLeafStats(const TraversalData &data)
731	{
732
733	// the node became a leaf -> evaluate stats for leafs
734	VssTreeLeaf leaf = (VssTreeLeaf )data.node;
735
736	if (data.depth >= termMaxDepth)
737	stat.maxDepthNodes++;
738
739	// if ( (int)(leaf->rays.size()) < termMinCost)
740	// stat.minCostNodes++;
741	if ( leaf->mPvsSize < termMinPvs)
742	stat.minCostNodes++;
743
744	if (leaf->GetAvgRayContribution() > termMaxRayContribution )
745	stat.maxRayContribNodes++;
746
747	if (SqrMagnitude(data.bbox.Size()) <= termMinSize) {
748	stat.minSizeNodes++;
749	}
750
751	if ( (int)(leaf->rays.size()) > stat.maxRayRefs)
752	stat.maxRayRefs = leaf->rays.size();
753
754	}
755
756
757
758	VssTreeNode *
759	VssTree::SubdivideNode(
760	VssTreeLeaf *leaf,
761	const AxisAlignedBox3 &box,
762	AxisAlignedBox3 &backBBox,
763	AxisAlignedBox3 &frontBBox
764	)
765	{
766
767	if ( (leaf->mPvsSize < termMinPvs) \|\|
768	(leaf->GetAvgRayContribution() > termMaxRayContribution ) \|\|
769	(leaf->depth >= termMaxDepth) \|\|
770	SqrMagnitude(box.Size()) <= termMinSize ) {
771
772	#if 0
773	if (leaf->depth >= termMaxDepth) {
774	cout<<"Warning: max depth reached depth="<<(int)leaf->depth<<" rays="<<leaf->rays.size()<<endl;
775	cout<<"Bbox: "<<GetBBox(leaf)<<" dirbbox:"<<GetDirBBox(leaf)<<endl;
776	}
777	#endif
778
779	return leaf;
780	}
781
782	float position;
783
784	// first count ray sides
785	int raysBack;
786	int raysFront;
787	int pvsBack;
788	int pvsFront;
789
790	// select subdivision axis
791	int axis = SelectPlane( leaf, box, position, raysBack, raysFront, pvsBack, pvsFront);
792
793	// cout<<"rays back="<<raysBack<<" rays front="<<raysFront<<" pvs back="<<pvsBack<<" pvs front="<<
794	// pvsFront<<endl;
795
796	if (axis == -1) {
797	return leaf;
798	}
799
800	stat.nodes+=2;
801	stat.splits[axis]++;
802
803	// add the new nodes to the tree
804	VssTreeInterior *node = new VssTreeInterior(leaf->parent);
805
806	node->axis = axis;
807	node->position = position;
808	node->bbox = box;
809	node->dirBBox = GetDirBBox(leaf);
810
811	backBBox = box;
812	frontBBox = box;
813
814	VssTreeLeaf *back = new VssTreeLeaf(node, raysBack);
815	back->mPvsSize = pvsBack;
816	VssTreeLeaf *front = new VssTreeLeaf(node, raysFront);
817	front->mPvsSize = pvsFront;
818
819	// replace a link from node's parent
820	if ( leaf->parent )
821	leaf->parent->ReplaceChildLink(leaf, node);
822	// and setup child links
823	node->SetupChildLinks(back, front);
824
825	if (axis <= VssTreeNode::SPLIT_Z) {
826	backBBox.SetMax(axis, position);
827	frontBBox.SetMin(axis, position);
828
829	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
830	ri != leaf->rays.end();
831	ri++) {
832	if ((*ri).mRay->IsActive()) {
833
834	// first unref ray from the former leaf
835	(*ri).mRay->Unref();
836
837	// determine the side of this ray with respect to the plane
838	int side = node->ComputeRayIntersection(ri, (ri).mRay->mT);
839
840	if (side == 0) {
841	if ((*ri).mRay->HasPosDir(axis)) {
842	back->AddRay(VssTreeNode::RayInfo((*ri).mRay,
843	(*ri).mMinT,
844	(*ri).mRay->mT)
845	);
846	front->AddRay(VssTreeNode::RayInfo((*ri).mRay,
847	(*ri).mRay->mT,
848	(*ri).mMaxT));
849	} else {
850	back->AddRay(VssTreeNode::RayInfo((*ri).mRay,
851	(*ri).mRay->mT,
852	(*ri).mMaxT));
853	front->AddRay(VssTreeNode::RayInfo((*ri).mRay,
854	(*ri).mMinT,
855	(*ri).mRay->mT));
856	}
857	} else
858	if (side == 1)
859	front->AddRay(*ri);
860	else
861	back->AddRay(*ri);
862	} else
863	(*ri).mRay->Unref();
864	}
865	} else {
866	// rays front/back
867
868
869	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
870	ri != leaf->rays.end();
871	ri++) {
872	if ((*ri).mRay->IsActive()) {
873	// first unref ray from the former leaf
874	(*ri).mRay->Unref();
875
876	int side;
877	if ((*ri).mRay->GetDirParametrization(axis - 3) > position)
878	side = 1;
879	else
880	side = -1;
881
882	if (side == 1)
883	front->AddRay(*ri);
884	else
885	back->AddRay(*ri);
886
887	} else
888	(*ri).mRay->Unref();
889	}
890	}
891
892	// update stats
893	stat.rayRefs -= leaf->rays.size();
894	stat.rayRefs += raysBack + raysFront;
895
896
897	delete leaf;
898	return node;
899	}
900
901
902
903
904
905
906	int
907	VssTree::ReleaseMemory(const int time)
908	{
909	stack<VssTreeNode *> tstack;
910
911	// find a node in the tree which subtree will be collapsed
912	int maxAccessTime = time - accessTimeThreshold;
913	int released;
914
915	tstack.push(root);
916
917	while (!tstack.empty()) {
918	VssTreeNode *node = tstack.top();
919	tstack.pop();
920
921
922	if (!node->IsLeaf()) {
923	VssTreeInterior in = (VssTreeInterior )node;
924	// cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
925	if (in->depth >= minCollapseDepth &&
926	in->lastAccessTime <= maxAccessTime) {
927	released = CollapseSubtree(node, time);
928	break;
929	}
930
931	if (in->back->GetAccessTime() <
932	in->front->GetAccessTime()) {
933	tstack.push(in->front);
934	tstack.push(in->back);
935	} else {
936	tstack.push(in->back);
937	tstack.push(in->front);
938	}
939	}
940	}
941
942	while (tstack.empty()) {
943	// could find node to collaps...
944	// cout<<"Could not find a node to release "<<endl;
945	break;
946	}
947
948	return released;
949	}
950
951
952
953
954	VssTreeNode *
955	VssTree::SubdivideLeaf(
956	VssTreeLeaf *leaf,
957	const float sizeThreshold
958	)
959	{
960	VssTreeNode *node = leaf;
961
962	AxisAlignedBox3 leafBBox = GetBBox(leaf);
963
964	static int pass = 0;
965	pass ++;
966
967	// check if we should perform a dynamic subdivision of the leaf
968	if (
969	// leaf->rays.size() > (unsigned)termMinCost &&
970	(leaf->mPvsSize >= termMinPvs) &&
971	SqrMagnitude(leafBBox.Size()) > sizeThreshold) {
972
973	// memory check and realese...
974	if (GetMemUsage() > maxTotalMemory) {
975	ReleaseMemory( pass );
976	}
977
978	AxisAlignedBox3 backBBox, frontBBox;
979
980	// subdivide the node
981	node =
982	SubdivideNode(leaf,
983	leafBBox,
984	backBBox,
985	frontBBox
986	);
987	}
988	return node;
989	}
990
991
992
993	void
994	VssTree::UpdateRays(VssRayContainer &remove,
995	VssRayContainer &add
996	)
997	{
998	VssTreeLeaf::NewMail();
999
1000	// schedule rays for removal
1001	for(VssRayContainer::const_iterator ri = remove.begin();
1002	ri != remove.end();
1003	ri++) {
1004	(*ri)->ScheduleForRemoval();
1005	}
1006
1007	int inactive=0;
1008
1009	for(VssRayContainer::const_iterator ri = remove.begin();
1010	ri != remove.end();
1011	ri++) {
1012	if ((*ri)->ScheduledForRemoval())
1013	// RemoveRay(*ri, NULL, false);
1014	// !!! BUG - with true it does not work correctly - aggreated delete
1015	RemoveRay(*ri, NULL, true);
1016	else
1017	inactive++;
1018	}
1019
1020
1021	// cout<<"all/inactive"<<remove.size()<<"/"<<inactive<<endl;
1022
1023	for(VssRayContainer::const_iterator ri = add.begin();
1024	ri != add.end();
1025	ri++) {
1026	AddRay(*ri);
1027	}
1028
1029
1030	}
1031
1032
1033	void
1034	VssTree::RemoveRay(VssRay *ray,
1035	vector<VssTreeLeaf > affectedLeaves,
1036	const bool removeAllScheduledRays
1037	)
1038	{
1039
1040	stack<RayTraversalData> tstack;
1041
1042	tstack.push(RayTraversalData(root, VssTreeNode::RayInfo(ray)));
1043
1044	RayTraversalData data;
1045
1046	// cout<<"Number of ray refs = "<<ray->RefCount()<<endl;
1047
1048	while (!tstack.empty()) {
1049	data = tstack.top();
1050	tstack.pop();
1051
1052	if (!data.node->IsLeaf()) {
1053	// split the set of rays in two groups intersecting the
1054	// two subtrees
1055
1056	TraverseInternalNode(data, tstack);
1057
1058	} else {
1059	// remove the ray from the leaf
1060	// find the ray in the leaf and swap it with the last ray...
1061	VssTreeLeaf leaf = (VssTreeLeaf )data.node;
1062
1063	if (!leaf->Mailed()) {
1064	leaf->Mail();
1065	if (affectedLeaves)
1066	affectedLeaves->push_back(leaf);
1067
1068	if (removeAllScheduledRays) {
1069	int tail = leaf->rays.size()-1;
1070
1071	for (int i=0; i < (int)(leaf->rays.size()); i++) {
1072	if (leaf->rays[i].mRay->ScheduledForRemoval()) {
1073	// find a ray to replace it with
1074	while (tail >= i && leaf->rays[tail].mRay->ScheduledForRemoval()) {
1075	stat.removedRayRefs++;
1076	leaf->rays[tail].mRay->Unref();
1077	leaf->rays.pop_back();
1078	tail--;
1079	}
1080
1081	if (tail < i)
1082	break;
1083
1084	stat.removedRayRefs++;
1085	leaf->rays[i].mRay->Unref();
1086	leaf->rays[i] = leaf->rays[tail];
1087	leaf->rays.pop_back();
1088	tail--;
1089	}
1090	}
1091	}
1092	}
1093
1094	if (!removeAllScheduledRays)
1095	for (int i=0; i < (int)leaf->rays.size(); i++) {
1096	if (leaf->rays[i].mRay == ray) {
1097	stat.removedRayRefs++;
1098	ray->Unref();
1099	leaf->rays[i] = leaf->rays[leaf->rays.size()-1];
1100	leaf->rays.pop_back();
1101	// check this ray again
1102	break;
1103	}
1104	}
1105
1106	}
1107	}
1108
1109	if (ray->RefCount() != 0) {
1110	cerr<<"Error: Number of remaining refs = "<<ray->RefCount()<<endl;
1111	exit(1);
1112	}
1113
1114	}
1115
1116
1117	void
1118	VssTree::AddRay(VssRay *ray)
1119	{
1120
1121	stack<RayTraversalData> tstack;
1122
1123	tstack.push(RayTraversalData(root, VssTreeNode::RayInfo(ray)));
1124
1125	RayTraversalData data;
1126
1127	while (!tstack.empty()) {
1128	data = tstack.top();
1129	tstack.pop();
1130
1131	if (!data.node->IsLeaf()) {
1132
1133	TraverseInternalNode(data, tstack);
1134
1135	} else {
1136	// remove the ray from the leaf
1137	// find the ray in the leaf and swap it with the last ray...
1138	VssTreeLeaf leaf = (VssTreeLeaf )data.node;
1139	leaf->AddRay(data.rayData);
1140	stat.addedRayRefs++;
1141	}
1142	}
1143	}
1144
1145	void
1146	VssTree::TraverseInternalNode(
1147	RayTraversalData &data,
1148	stack<RayTraversalData> &tstack)
1149	{
1150	VssTreeInterior in = (VssTreeInterior ) data.node;
1151
1152	if (in->axis <= VssTreeNode::SPLIT_Z) {
1153
1154	// determine the side of this ray with respect to the plane
1155	int side = in->ComputeRayIntersection(data.rayData,
1156	data.rayData.mRay->mT);
1157
1158
1159	if (side == 0) {
1160	if (data.rayData.mRay->HasPosDir(in->axis)) {
1161	tstack.push(RayTraversalData(in->back,
1162	VssTreeNode::RayInfo(data.rayData.mRay,
1163	data.rayData.mMinT,
1164	data.rayData.mRay->mT))
1165	);
1166
1167	tstack.push(RayTraversalData(in->front,
1168	VssTreeNode::RayInfo(data.rayData.mRay,
1169	data.rayData.mRay->mT,
1170	data.rayData.mMaxT
1171	))
1172	);
1173
1174	} else {
1175	tstack.push(RayTraversalData(in->back,
1176	VssTreeNode::RayInfo(data.rayData.mRay,
1177	data.rayData.mRay->mT,
1178	data.rayData.mMaxT
1179	))
1180	);
1181
1182	tstack.push(RayTraversalData(in->front,
1183	VssTreeNode::RayInfo(data.rayData.mRay,
1184	data.rayData.mMinT,
1185	data.rayData.mRay->mT))
1186	);
1187
1188
1189	}
1190	} else
1191	if (side == 1)
1192	tstack.push(RayTraversalData(in->front, data.rayData));
1193	else
1194	tstack.push(RayTraversalData(in->back, data.rayData));
1195	}
1196	else {
1197	// directional split
1198	// if (DotProd(data.rayData.mRay->GetNormalizedDir(), in->refDir) > sinRefDir )
1199	// tstack.push(RayTraversalData(in->front, data.rayData));
1200	// else
1201	// tstack.push(RayTraversalData(in->back, data.rayData));
1202	}
1203
1204	}
1205
1206
1207	int
1208	VssTree::CollapseSubtree(VssTreeNode *sroot, const int time)
1209	{
1210	// first count all rays in the subtree
1211	// use mail 1 for this purpose
1212	stack<VssTreeNode *> tstack;
1213	int rayCount = 0;
1214	int totalRayCount = 0;
1215	int collapsedNodes = 0;
1216
1217	#if DEBUG_COLLAPSE
1218	cout<<"Collapsing subtree"<<endl;
1219	cout<<"acessTime="<<sroot->GetAccessTime()<<endl;
1220	cout<<"depth="<<(int)sroot->depth<<endl;
1221	#endif
1222
1223	// tstat.collapsedSubtrees++;
1224	// tstat.collapseDepths += (int)sroot->depth;
1225	// tstat.collapseAccessTimes += time - sroot->GetAccessTime();
1226
1227	tstack.push(sroot);
1228	VssRay::NewMail();
1229
1230	while (!tstack.empty()) {
1231	collapsedNodes++;
1232	VssTreeNode *node = tstack.top();
1233	tstack.pop();
1234
1235	if (node->IsLeaf()) {
1236	VssTreeLeaf leaf = (VssTreeLeaf ) node;
1237	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
1238	ri != leaf->rays.end();
1239	ri++) {
1240
1241	totalRayCount++;
1242	if ((ri).mRay->IsActive() && !(ri).mRay->Mailed()) {
1243	(*ri).mRay->Mail();
1244	rayCount++;
1245	}
1246	}
1247	} else {
1248	tstack.push(((VssTreeInterior *)node)->back);
1249	tstack.push(((VssTreeInterior *)node)->front);
1250	}
1251	}
1252
1253	VssRay::NewMail();
1254
1255	// create a new node that will hold the rays
1256	VssTreeLeaf *newLeaf = new VssTreeLeaf( sroot->parent, rayCount );
1257	if ( newLeaf->parent )
1258	newLeaf->parent->ReplaceChildLink(sroot, newLeaf);
1259
1260
1261	tstack.push( sroot );
1262
1263	while (!tstack.empty()) {
1264
1265	VssTreeNode *node = tstack.top();
1266	tstack.pop();
1267
1268	if (node->IsLeaf()) {
1269	VssTreeLeaf leaf = (VssTreeLeaf ) node;
1270
1271	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
1272	ri != leaf->rays.end();
1273	ri++) {
1274
1275	// unref this ray from the old node
1276
1277	if ((*ri).mRay->IsActive()) {
1278	(*ri).mRay->Unref();
1279	if (!(*ri).mRay->Mailed()) {
1280	(*ri).mRay->Mail();
1281	newLeaf->AddRay(*ri);
1282	}
1283	} else
1284	(*ri).mRay->Unref();
1285
1286	}
1287	} else {
1288	tstack.push(((VssTreeInterior *)node)->back);
1289	tstack.push(((VssTreeInterior *)node)->front);
1290	}
1291	}
1292
1293	// delete the node and all its children
1294	delete sroot;
1295
1296	// for(VssTreeNode::SRayContainer::iterator ri = newLeaf->rays.begin();
1297	// ri != newLeaf->rays.end();
1298	// ri++)
1299	// (*ri).ray->UnMail(2);
1300
1301
1302	#if DEBUG_COLLAPSE
1303	cout<<"Total memory before="<<GetMemUsage()<<endl;
1304	#endif
1305
1306	stat.nodes -= collapsedNodes - 1;
1307	stat.rayRefs -= totalRayCount - rayCount;
1308
1309	#if DEBUG_COLLAPSE
1310	cout<<"collapsed nodes"<<collapsedNodes<<endl;
1311	cout<<"collapsed rays"<<totalRayCount - rayCount<<endl;
1312	cout<<"Total memory after="<<GetMemUsage()<<endl;
1313	cout<<"================================"<<endl;
1314	#endif
1315
1316	// tstat.collapsedNodes += collapsedNodes;
1317	// tstat.collapsedRays += totalRayCount - rayCount;
1318
1319	return totalRayCount - rayCount;
1320	}
1321
1322
1323	int
1324	VssTree::GetPvsSize(VssTreeNode *node, const AxisAlignedBox3 &box) const
1325	{
1326	stack<VssTreeNode *> tstack;
1327	tstack.push(root);
1328
1329	Intersectable::NewMail();
1330	int pvsSize = 0;
1331
1332	while (!tstack.empty()) {
1333	VssTreeNode *node = tstack.top();
1334	tstack.pop();
1335
1336
1337	if (node->IsLeaf()) {
1338	VssTreeLeaf leaf = (VssTreeLeaf )node;
1339	for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
1340	ri != leaf->rays.end();
1341	ri++)
1342	if ((*ri).mRay->IsActive()) {
1343	Intersectable *object;
1344	#if BIDIRECTIONAL_RAY
1345	object = (*ri).mRay->mOriginObject;
1346	if (object && !object->Mailed()) {
1347	pvsSize++;
1348	object->Mail();
1349	}
1350	#endif
1351	object = (*ri).mRay->mTerminationObject;
1352	if (object && !object->Mailed()) {
1353	pvsSize++;
1354	object->Mail();
1355	}
1356	}
1357	} else {
1358	VssTreeInterior in = (VssTreeInterior )node;
1359	if (in->axis < 3) {
1360	if (box.Max(in->axis) >= in->position )
1361	tstack.push(in->front);
1362
1363	if (box.Min(in->axis) <= in->position )
1364	tstack.push(in->back);
1365	} else {
1366	// both nodes for directional splits
1367	tstack.push(in->front);
1368	tstack.push(in->back);
1369	}
1370	}
1371	}
1372	return pvsSize;
1373	}

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

Download in other formats: