Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp @ 495

Revision 495, 58.4 KB checked in by mattausch, 19 years ago (diff)
fixed bug in tree collapse

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 "VspKdTree.h"
21
22	#include "Environment.h"
23	#include "VssRay.h"
24	#include "Intersectable.h"
25	#include "Ray.h"
26	#include "RayInfo.h"
27	#include "ViewCellsManager.h"
28	#include "ViewCellBsp.h"
29
30	// Static variables
31	int VspKdLeaf::sMailId = 0;
32	int MergeCandidate::sMaxPvsSize = 150;
33	float MergeCandidate::sOverallCost = Limits::Small;
34	#define USE_FIXEDPOINT_T 0
35
36	/// Adds object to the pvs of the front and back node
37	inline void AddObject2Pvs(Intersectable *object,
38	const int side,
39	int &pvsBack,
40	int &pvsFront)
41	{
42	if (!object)
43	return;
44
45	if (side <= 0)
46	{
47	if (!object->Mailed() && !object->Mailed(2))
48	{
49	++ pvsBack;
50
51	if (object->Mailed(1))
52	object->Mail(2);
53	else
54	object->Mail();
55	}
56	}
57
58	if (side >= 0)
59	{
60	if (!object->Mailed(1) && !object->Mailed(2))
61	{
62	++ pvsFront;
63
64	if (object->Mailed())
65	object->Mail(2);
66	else
67	object->Mail(1);
68	}
69	}
70	}
71
72	/**************************************************************/
73	/* class VspKdNode implementation */
74	/**************************************************************/
75
76	// Inline constructor
77	VspKdNode::VspKdNode(VspKdInterior *p):
78	mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0)
79	{}
80
81	VspKdNode::~VspKdNode()
82	{
83	};
84
85	inline VspKdInterior *VspKdNode::GetParent() const
86	{
87	return mParent;
88	}
89
90	inline void VspKdNode::SetParent(VspKdInterior *p)
91	{
92	mParent = p;
93	}
94
95	bool VspKdNode::IsLeaf() const
96	{
97	return mAxis == -1;
98	}
99
100	int VspKdNode::GetAccessTime()
101	{
102	return 0x7FFFFFF;
103	}
104
105	/**************************************************************/
106	/* VspKdInterior implementation */
107	/**************************************************************/
108
109	VspKdInterior::VspKdInterior(VspKdInterior *p):
110	VspKdNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)
111	{
112	}
113
114	int VspKdInterior::GetAccessTime()
115	{
116	return mLastAccessTime;
117	}
118
119	void VspKdInterior::SetupChildLinks(VspKdNode b, VspKdNode f)
120	{
121	mBack = b;
122	mFront = f;
123	b->SetParent(this);
124	f->SetParent(this);
125	}
126
127	void VspKdInterior::ReplaceChildLink(VspKdNode *oldChild,
128	VspKdNode *newChild)
129	{
130	if (mBack == oldChild)
131	mBack = newChild;
132	else
133	mFront = newChild;
134	}
135
136	int VspKdInterior::Type() const
137	{
138	return EInterior;
139	}
140
141	VspKdInterior::~VspKdInterior()
142	{
143	DEL_PTR(mBack);
144	DEL_PTR(mFront);
145	}
146
147	void VspKdInterior::Print(ostream &s) const
148	{
149	switch (mAxis)
150	{
151	case 0:
152	s << "x "; break;
153	case 1:
154	s << "y "; break;
155	case 2:
156	s << "z "; break;
157	}
158
159	s << mPosition << " ";
160
161	mBack->Print(s);
162	mFront->Print(s);
163	}
164
165	int VspKdInterior::ComputeRayIntersection(const RayInfo &rayData, float &t)
166	{
167	return rayData.ComputeRayIntersection(mAxis, mPosition, t);
168	}
169
170	VspKdNode *VspKdInterior::GetBack() const
171	{
172	return mBack;
173	}
174
175	VspKdNode *VspKdInterior::GetFront() const
176	{
177	return mFront;
178	}
179
180
181	/*******************************************************************/
182	/* class VspKdLeaf implementation */
183	/*******************************************************************/
184
185
186	VspKdLeaf::VspKdLeaf(VspKdInterior *p,
187	const int nRays,
188	const int maxCostMisses):
189	VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL),
190	mMaxCostMisses(maxCostMisses), mPvs(NULL), mVolume(0)
191	{
192	mRays.reserve(nRays);
193	}
194
195	VspKdLeaf::~VspKdLeaf()
196	{
197	DEL_PTR(mPvs);
198	}
199
200
201	int VspKdLeaf::GetMaxCostMisses()
202	{
203	return mMaxCostMisses;
204	}
205
206
207	int VspKdLeaf::Type() const
208	{
209	return ELeaf;
210	}
211
212	void VspKdLeaf::Print(ostream &s) const
213	{
214	s << endl << "L: r = " << (int)mRays.size() << endl;
215	};
216
217	void VspKdLeaf::AddRay(const RayInfo &data)
218	{
219	mValidPvs = false;
220	mRays.push_back(data);
221	data.mRay->Ref();
222	}
223
224	int VspKdLeaf::GetPvsSize() const
225	{
226	return mPvsSize;
227	}
228
229	void VspKdLeaf::SetPvsSize(const int s)
230	{
231	mPvsSize = s;
232	}
233
234	void VspKdLeaf::Mail()
235	{
236	mMailbox = sMailId;
237	}
238
239	void VspKdLeaf::NewMail()
240	{
241	++ sMailId;
242	}
243
244	bool VspKdLeaf::Mailed() const
245	{
246	return mMailbox == sMailId;
247	}
248
249	bool VspKdLeaf::Mailed(const int mail) const
250	{
251	return mMailbox == mail;
252	}
253
254	int VspKdLeaf::GetMailbox() const
255	{
256	return mMailbox;
257	}
258
259	float VspKdLeaf::GetAvgRayContribution() const
260	{
261	return GetPvsSize() / ((float)mRays.size() + Limits::Small);
262	}
263
264	float VspKdLeaf::GetSqrRayContribution() const
265	{
266	return sqr(GetAvgRayContribution());
267	}
268
269	RayInfoContainer &VspKdLeaf::GetRays()
270	{
271	return mRays;
272	}
273
274	void VspKdLeaf::ExtractPvs(ObjectContainer &objects) const
275	{
276	RayInfoContainer::const_iterator it, it_end = mRays.end();
277
278	for (it = mRays.begin(); it != it_end; ++ it)
279	{
280	if ((*it).mRay->mTerminationObject)
281	objects.push_back((*it).mRay->mTerminationObject);
282	if ((*it).mRay->mOriginObject)
283	objects.push_back((*it).mRay->mOriginObject);
284	}
285	}
286
287	void VspKdLeaf::GetRays(VssRayContainer &rays)
288	{
289	RayInfoContainer::const_iterator it, it_end = mRays.end();
290
291	for (it = mRays.begin(); it != mRays.end(); ++ it)
292	rays.push_back((*it).mRay);
293	}
294
295	VspKdViewCell *VspKdLeaf::GetViewCell()
296	{
297	return mViewCell;
298	}
299
300	void VspKdLeaf::SetViewCell(VspKdViewCell *viewCell)
301	{
302	mViewCell = viewCell;
303	}
304
305
306	void VspKdLeaf::UpdatePvsSize()
307	{
308	if (!mValidPvs)
309	{
310	Intersectable::NewMail();
311	int pvsSize = 0;
312	for(RayInfoContainer::iterator ri = mRays.begin();
313	ri != mRays.end(); ++ ri)
314	{
315	if ((*ri).mRay->IsActive())
316	{
317	Intersectable *object;
318	#if BIDIRECTIONAL_RAY
319	object = (*ri).mRay->mOriginObject;
320
321	if (object && !object->Mailed())
322	{
323	++ pvsSize;
324	object->Mail();
325	}
326	#endif
327	object = (*ri).mRay->mTerminationObject;
328	if (object && !object->Mailed())
329	{
330	++ pvsSize;
331	object->Mail();
332	}
333	}
334	}
335
336	mPvsSize = pvsSize;
337	mValidPvs = true;
338	}
339	}
340
341	/*********************************************************/
342	/* class VspKdTree implementation */
343	/*********************************************************/
344
345
346	VspKdTree::VspKdTree(): mOnlyDrivingAxis(false)
347	{
348	environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth);
349	environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs);
350	environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays);
351	environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution);
352	environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio);
353	environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize);
354
355	environment->GetIntValue("VspKdTree.Termination.missTolerance", mTermMissTolerance);
356
357	mTermMinSize = sqr(mTermMinSize);
358
359	environment->GetFloatValue("VspKdTree.epsilon", mEpsilon);
360	environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi);
361
362	environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory);
363	environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory);
364
365	environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold);
366	environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth);
367
368	//environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells);
369
370	environment->GetIntValue("VspKdTree.PostProcess.minViewCells", mMergeMinViewCells);
371	environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
372	environment->GetIntValue("VspKdTree.PostProcess.maxPvsSize",
373	MergeCandidate::sMaxPvsSize);
374
375	environment->GetBoolValue("VspKdTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
376
377	//-- output
378	Debug << "======= vsp kd tree options ========" << endl;
379	Debug << "max depth: "<< mTermMaxDepth << endl;
380	Debug << "min pvs: "<< mTermMinPvs << endl;
381	Debug << "min rays: "<< mTermMinRays << endl;
382	Debug << "max ray contribution: "<< mTermMaxRayContribution << endl;
383	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
384	Debug << "min size: " << mTermMinSize << endl;
385
386	Debug << "split type: ";
387
388	//-- split type
389	char sname[128];
390	environment->GetStringValue("VspKdTree.splitType", sname);
391	string name(sname);
392
393	if (name.compare("regular") == 0)
394	{
395	Debug << "regular split" << endl;
396	splitType = ESplitRegular;
397	}
398	else
399	{
400	if (name.compare("heuristic") == 0)
401	{
402	Debug << "heuristic split" << endl;
403	splitType = ESplitHeuristic;
404	}
405	else
406	{
407	cerr << "Invalid VspKdTree split type " << name << endl;
408	exit(1);
409	}
410	}
411
412	mRoot = NULL;
413	mSplitCandidates = new vector<SortableEntry>;
414	}
415
416
417	VspKdTree::~VspKdTree()
418	{
419	DEL_PTR(mRoot);
420	DEL_PTR(mSplitCandidates);
421	}
422
423	void VspKdStatistics::Print(ostream &app) const
424	{
425	app << "===== VspKdTree statistics ===============\n";
426
427	app << "#N_RAYS ( Number of rays )\n"
428	<< rays << endl;
429
430	app << "#N_INITPVS ( Initial PVS size )\n"
431	<< initialPvsSize << endl;
432
433	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
434
435	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
436
437	app << "#N_SPLITS ( Number of splits in axes x y z\n";
438
439	for (int i = 0; i < 3; ++ i)
440	app << splits[i] << " ";
441	app << endl;
442
443	app << "#N_RAYREFS ( Number of rayRefs )\n" <<
444	rayRefs << "\n";
445
446	app << "#N_RAYRAYREFS ( Number of rayRefs / ray )\n" <<
447	rayRefs / (double)rays << "\n";
448
449	app << "#N_LEAFRAYREFS ( Number of rayRefs / leaf )\n" <<
450	rayRefs / (double)Leaves() << "\n";
451
452	app << "#N_MAXRAYREFS ( Max number of rayRefs / leaf )\n" <<
453	maxRayRefs << "\n";
454
455	// app << setprecision(4);
456
457	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n" <<
458	maxDepthNodes * 100 / (double)Leaves() << endl;
459
460	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n" <<
461	minPvsNodes * 100 / (double)Leaves() << endl;
462
463	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n" <<
464	minRaysNodes * 100 / (double)Leaves() << endl;
465
466	app << "#N_PMINSIZELEAVES ( Percentage of leaves with minSize )\n"<<
467	minSizeNodes * 100 / (double)Leaves() << endl;
468
469	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n" <<
470	maxRayContribNodes * 100 / (double)Leaves() << endl;
471
472	app << "#N_PMAXRCOSTLEAVES ( Percentage of leaves with maximal cost ratio )\n" <<
473	maxCostNodes * 100 / (double)Leaves() << endl;
474
475	app << "#N_ADDED_RAYREFS ( Number of dynamically added ray references )\n"<<
476	addedRayRefs << endl;
477
478	app << "#N_REMOVED_RAYREFS ( Number of dynamically removed ray references )\n"<<
479	removedRayRefs << endl;
480
481	// app << setprecision(4);
482
483	app << "#N_( Maximal PVS size / leaf)\n"
484	<< maxPvsSize << endl;
485
486	app << "#N_( Average PVS size / leaf)\n"
487	<< (double) accPvsSize / (double)Leaves() << endl;
488
489	app << "#N_CTIME ( Construction time [s] )\n"
490	<< Time() << " \n";
491
492	app << "===== END OF VspKdTree statistics ==========\n";
493	}
494
495
496	void VspKdTree::CollectViewCells(ViewCellContainer &viewCells) const
497	{
498	stack<VspKdNode *> nodeStack;
499	nodeStack.push(mRoot);
500
501	ViewCell::NewMail();
502
503	while (!nodeStack.empty())
504	{
505	VspKdNode *node = nodeStack.top();
506	nodeStack.pop();
507
508	if (node->IsLeaf())
509	{
510	ViewCell viewCell = dynamic_cast<VspKdLeaf >(node)->mViewCell;
511
512	if (!viewCell->Mailed())
513	{
514	viewCell->Mail();
515	viewCells.push_back(viewCell);
516	}
517	}
518	else
519	{
520	VspKdInterior interior = dynamic_cast<VspKdInterior >(node);
521
522	nodeStack.push(interior->GetFront());
523	nodeStack.push(interior->GetBack());
524	}
525	}
526	}
527
528	void VspKdTree::Construct(const VssRayContainer &rays,
529	AxisAlignedBox3 *forcedBoundingBox)
530	{
531	mStat.Start();
532
533	mMaxMemory = mMaxStaticMemory;
534	DEL_PTR(mRoot);
535
536	mRoot = new VspKdLeaf(NULL, (int)rays.size());
537
538	// first construct a leaf that will get subdivided
539	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(mRoot);
540
541	mStat.nodes = 1;
542	mBox.Initialize();
543
544	//-- compute bounding box
545	if (forcedBoundingBox)
546	mBox = *forcedBoundingBox;
547	else
548	for (VssRayContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
549	{
550	if ((*ri)->mOriginObject)
551	mBox.Include((*ri)->GetOrigin());
552	if ((*ri)->mTerminationObject)
553	mBox.Include((*ri)->GetTermination());
554	}
555
556	Debug << "bbox = " << mBox << endl;
557
558	for (VssRayContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
559	{
560	//leaf->AddRay(RayInfo(*ri));
561	VssRay ray = ri;
562	float minT, maxT;
563
564	// TODO: not very efficient to implictly cast between rays types!
565	if (mBox.GetRaySegment(*ray, minT, maxT))
566	{
567	float len = ray->Length();
568
569	if (!len)
570	len = Limits::Small;
571
572	leaf->AddRay(RayInfo(ray, minT / len, maxT / len));
573	}
574	}
575
576	mStat.rays = (int)leaf->mRays.size();
577	leaf->UpdatePvsSize();
578
579	mStat.initialPvsSize = leaf->GetPvsSize();
580
581	// Subdivide();
582	mRoot = Subdivide(TraversalData(leaf, mBox, 0));
583
584	if (mSplitCandidates)
585	{
586	// force release of this vector
587	delete mSplitCandidates;
588	mSplitCandidates = new vector<SortableEntry>;
589	}
590
591	mStat.Stop();
592
593	mStat.Print(cout);
594	Debug << "#Total memory=" << GetMemUsage() << endl;
595	}
596
597
598
599	VspKdNode *VspKdTree::Subdivide(const TraversalData &tdata)
600	{
601	VspKdNode *result = NULL;
602
603	priority_queue<TraversalData> tStack;
604	//stack<TraversalData> tStack;
605
606	tStack.push(tdata);
607
608	AxisAlignedBox3 backBox;
609	AxisAlignedBox3 frontBox;
610
611	int lastMem = 0;
612
613	while (!tStack.empty())
614	{
615	float mem = GetMemUsage();
616
617	if (lastMem / 10 != ((int)mem) / 10)
618	{
619	Debug << mem << " MB" << endl;
620	}
621	lastMem = (int)mem;
622
623	if (1 && mem > mMaxMemory)
624	{
625	Debug << "memory limit reached: " << mem << endl;
626	// count statistics on unprocessed leafs
627	while (!tStack.empty())
628	{
629	EvaluateLeafStats(tStack.top());
630	tStack.pop();
631	}
632	break;
633	}
634
635	TraversalData data = tStack.top();
636	tStack.pop();
637
638	VspKdNode node = SubdivideNode(dynamic_cast<VspKdLeaf >(data.mNode),
639	data.mBox, backBox, frontBox);
640	if (result == NULL)
641	result = node;
642
643	if (!node->IsLeaf())
644	{
645	VspKdInterior interior = dynamic_cast<VspKdInterior >(node);
646
647	// push the children on the stack
648	tStack.push(TraversalData(interior->GetBack(), backBox, data.mDepth + 1));
649	tStack.push(TraversalData(interior->GetFront(), frontBox, data.mDepth + 1));
650	}
651	else
652	{
653	EvaluateLeafStats(data);
654	}
655	}
656
657	return result;
658	}
659
660
661	// returns selected plane for subdivision
662	int VspKdTree::SelectPlane(VspKdLeaf *leaf,
663	const AxisAlignedBox3 &box,
664	float &position,
665	int &raysBack,
666	int &raysFront,
667	int &pvsBack,
668	int &pvsFront)
669	{
670	int axis = 0;
671	float costRatio = 0;
672
673	if (splitType == ESplitRegular)
674	{
675	costRatio = BestCostRatioRegular(leaf,
676	box,
677	axis,
678	position,
679	raysBack,
680	raysFront,
681	pvsBack,
682	pvsFront);
683	}
684	else if (splitType == ESplitHeuristic)
685	{
686	costRatio = BestCostRatioHeuristic(leaf,
687	box,
688	axis,
689	position,
690	raysBack,
691	raysFront,
692	pvsBack,
693	pvsFront);
694	}
695	else
696	{
697	cerr << "VspKdTree: Unknown split heuristics\n";
698	exit(1);
699	}
700
701	if (costRatio > mTermMaxCostRatio)
702	{
703	//Debug << "Too big cost ratio " << costRatio << endl;
704	++ leaf->mMaxCostMisses;
705	if (leaf->mMaxCostMisses > mTermMissTolerance)
706	{
707	++ mStat.maxCostNodes;
708	return -1;
709	}
710	}
711
712	if (0)
713	Debug << "pvs=" << leaf->mPvsSize
714	<< " rays=" << (int)leaf->mRays.size()
715	<< " rc=" << leaf->GetAvgRayContribution()
716	<< " axis=" << axis << endl;
717
718	return axis;
719	}
720
721
722
723	float VspKdTree::EvalCostRatio(VspKdLeaf *leaf,
724	const AxisAlignedBox3 &box,
725	const int axis,
726	const float position,
727	int &raysBack,
728	int &raysFront,
729	int &pvsBack,
730	int &pvsFront)
731	{
732	raysBack = 0;
733	raysFront = 0;
734	pvsFront = 0;
735	pvsBack = 0;
736
737	Intersectable::NewMail(3);
738
739	// eval pvs size
740	const int pvsSize = leaf->GetPvsSize();
741
742	// this is the main ray classification loop!
743	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
744	ri != leaf->mRays.end(); ++ ri)
745	{
746	if (!(*ri).mRay->IsActive())
747	continue;
748
749	// determine the side of this ray with respect to the plane
750	float t;
751	int side = (*ri).ComputeRayIntersection(axis, position, t);
752
753	if (side <= 0)
754	++ raysBack;
755
756	if (side >= 0)
757	++ raysFront;
758
759	AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
760	}
761
762	//-- only one of these options should be one
763
764	if (0) //-- only pvs
765	{
766	const float sum = float(pvsBack + pvsFront);
767	const float oldCost = (float)pvsSize;
768
769	return sum / oldCost;
770	}
771
772	//-- pvs + probability heuristics
773	float pBack, pFront, pOverall;
774
775	if (0)
776	{
777	// box length substitute for probability
778	const float minBox = box.Min(axis);
779	const float maxBox = box.Max(axis);
780
781	pBack = position - minBox;
782	pFront = maxBox - position;
783	pOverall = maxBox - minBox;
784	}
785
786	if (1) //-- area substitute for probability
787	{
788	pOverall = box.SurfaceArea();
789
790	const bool useMidSplit = true;
791	//const bool useMidSplit = false;
792
793	if (!useMidSplit)
794	{
795	Vector3 pos = box.Max(); pos[axis] = position;
796	pBack = AxisAlignedBox3(box.Min(), pos).SurfaceArea();
797
798	pos = box.Min(); pos[axis] = position;
799	pFront = AxisAlignedBox3(pos, box.Max()).SurfaceArea();
800	}
801	else
802	{
803	//-- simplified computation for mid split
804	const int axis2 = (axis + 1) % 3;
805	const int axis3 = (axis + 2) % 3;
806
807	const float faceArea =
808	(box.Max(axis2) - box.Min(axis2)) *
809	(box.Max(axis3) - box.Min(axis3));
810
811	pBack = pFront = pOverall * 0.5f + faceArea;
812	}
813	}
814
815	//-- ray density substitute for probability
816	if (0)
817	{
818	pBack = (float)raysBack;
819	pFront = (float)raysFront;
820	pOverall = (float)leaf->mRays.size();
821	}
822
823	//Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
824	//Debug << pFront << " " << pBack << " " << pOverall << endl;
825
826	// float sum = raysBack(position - minBox) + raysFront(maxBox - position);
827	const float newCost = pvsBack * pBack + pvsFront * pFront;
828	// float oldCost = leaf->mRays.size();
829	const float oldCost = (float)pvsSize * pOverall;
830
831	return (mCtDivCi + newCost) / oldCost;
832	}
833
834
835	float VspKdTree::BestCostRatioRegular(VspKdLeaf *leaf,
836	const AxisAlignedBox3 &box,
837	int &axis,
838	float &position,
839	int &raysBack,
840	int &raysFront,
841	int &pvsBack,
842	int &pvsFront)
843	{
844	int nRaysBack[3], nRaysFront[3];
845	int nPvsBack[3], nPvsFront[3];
846
847	float nPosition[3];
848	float nCostRatio[3];
849	int bestAxis = -1;
850
851	//AxisAlignedBox3 sBox = GetBBox(leaf);
852	const int sAxis = box.Size().DrivingAxis();
853
854	for (axis = 0; axis < 3; ++ axis)
855	{
856	if (!mOnlyDrivingAxis \|\| axis == sAxis)
857	{
858
859	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
860
861	nCostRatio[axis] = EvalCostRatio(leaf,
862	box,
863	axis,
864	nPosition[axis],
865	nRaysBack[axis],
866	nRaysFront[axis],
867	nPvsBack[axis],
868	nPvsFront[axis]);
869	if (bestAxis == -1)
870	{
871	bestAxis = axis;
872	}
873	else if (nCostRatio[axis] < nCostRatio[bestAxis])
874	{
875	/*Debug << "pvs front " << nPvsBack[axis]
876	<< " pvs back " << nPvsFront[axis]
877	<< " overall pvs " << leaf->GetPvsSize() << endl;*/
878	bestAxis = axis;
879	}
880
881	}
882	}
883
884	//-- assign best axis
885	axis = bestAxis;
886	position = nPosition[bestAxis];
887
888	raysBack = nRaysBack[bestAxis];
889	raysFront = nRaysFront[bestAxis];
890
891	pvsBack = nPvsBack[bestAxis];
892	pvsFront = nPvsFront[bestAxis];
893
894	if (bestAxis == 1)
895	Debug << "y axis!" << endl;
896	return nCostRatio[bestAxis];
897	}
898
899	float VspKdTree::BestCostRatioHeuristic(VspKdLeaf *leaf,
900	const AxisAlignedBox3 &box,
901	int &axis,
902	float &position,
903	int &raysBack,
904	int &raysFront,
905	int &pvsBack,
906	int &pvsFront)
907	{
908	//AxisAlignedBox3 box = GetBBox(leaf);
909	// AxisAlignedBox3 dirBox = GetDirBBox(node);
910
911	axis = box.Size().DrivingAxis();
912
913	SortSplitCandidates(leaf, axis);
914
915	// go through the lists, count the number of objects left and right
916	// and evaluate the following cost funcion:
917	// C = ct_div_ci + (qlrl + qrrr)/queries
918
919	int rl = 0, rr = (int)leaf->mRays.size();
920	int pl = 0, pr = leaf->GetPvsSize();
921
922	float minBox = box.Min(axis);
923	float maxBox = box.Max(axis);
924	float sizeBox = maxBox - minBox;
925
926	float minBand = minBox + 0.1f*(maxBox - minBox);
927	float maxBand = minBox + 0.9f*(maxBox - minBox);
928
929	float sum = rr*sizeBox;
930	float minSum = 1e20f;
931
932	Intersectable::NewMail();
933
934	// set all object as belonging to the fron pvs
935	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
936	ri != leaf->mRays.end(); ++ ri)
937	{
938	if ((*ri).mRay->IsActive())
939	{
940	Intersectable object = (ri).mRay->mTerminationObject;
941
942	if (object)
943	if (!object->Mailed())
944	{
945	object->Mail();
946	object->mCounter = 1;
947	}
948	else
949	++ object->mCounter;
950	}
951	}
952
953	Intersectable::NewMail();
954
955	for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin();
956	ci < mSplitCandidates->end(); ++ ci)
957	{
958	VssRay *ray;
959
960	switch ((*ci).type)
961	{
962	case SortableEntry::ERayMin:
963	{
964	++ rl;
965	ray = (*ci).ray;
966	Intersectable *object = ray->mTerminationObject;
967	if (object && !object->Mailed())
968	{
969	object->Mail();
970	++ pl;
971	}
972	break;
973	}
974	case SortableEntry::ERayMax:
975	{
976	-- rr;
977
978	ray = (*ci).ray;
979	Intersectable *object = ray->mTerminationObject;
980
981	if (object)
982	{
983	if (-- object->mCounter == 0)
984	-- pr;
985	}
986
987	break;
988	}
989	}
990
991	if ((ci).value > minBand && (ci).value < maxBand)
992	{
993	sum = pl((ci).value - minBox) + pr(maxBox - (ci).value);
994
995	// cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
996	// cout<<"cost= "<<sum<<endl;
997
998	if (sum < minSum)
999	{
1000	minSum = sum;
1001	position = (*ci).value;
1002
1003	raysBack = rl;
1004	raysFront = rr;
1005
1006	pvsBack = pl;
1007	pvsFront = pr;
1008
1009	}
1010	}
1011	}
1012
1013	float oldCost = (float)leaf->GetPvsSize();
1014	float newCost = mCtDivCi + minSum / sizeBox;
1015	float ratio = newCost / oldCost;
1016
1017	//Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
1018	// <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
1019
1020	return ratio;
1021	}
1022
1023	void VspKdTree::SortSplitCandidates(VspKdLeaf *node,
1024	const int axis)
1025	{
1026	mSplitCandidates->clear();
1027
1028	int requestedSize = 2 * (int)(node->mRays.size());
1029	// creates a sorted split candidates array
1030	if (mSplitCandidates->capacity() > 500000 &&
1031	requestedSize < (int)(mSplitCandidates->capacity()/10) )
1032	{
1033	DEL_PTR(mSplitCandidates);
1034	mSplitCandidates = new vector<SortableEntry>;
1035	}
1036
1037	mSplitCandidates->reserve(requestedSize);
1038
1039	// insert all queries
1040	for(RayInfoContainer::const_iterator ri = node->mRays.begin();
1041	ri < node->mRays.end(); ++ ri)
1042	{
1043	bool positive = (*ri).mRay->HasPosDir(axis);
1044	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
1045	(ri).ExtrapOrigin(axis), (ri).mRay));
1046
1047	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
1048	(ri).ExtrapTermination(axis), (ri).mRay));
1049	}
1050
1051	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
1052	}
1053
1054
1055	void VspKdTree::EvaluateLeafStats(const TraversalData &data)
1056	{
1057	// the node became a leaf -> evaluate stats for leafs
1058	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(data.mNode);
1059
1060	if (leaf->GetPvsSize() > mStat.maxPvsSize)
1061	mStat.maxPvsSize = leaf->GetPvsSize();
1062
1063	if ((int)(leaf->mRays.size()) > mStat.maxRayRefs)
1064	mStat.maxRayRefs = (int)leaf->mRays.size();
1065
1066	mStat.rays += (int)leaf->mRays.size();
1067
1068	if (data.mDepth >= mTermMaxDepth)
1069	++ mStat.maxDepthNodes;
1070
1071	if (leaf->GetPvsSize() < mTermMinPvs)
1072	++ mStat.minPvsNodes;
1073
1074	mStat.accPvsSize += leaf->GetPvsSize();
1075
1076	if ((int)leaf->GetRays().size() < mTermMinRays)
1077	++ mStat.minRaysNodes;
1078
1079	if (leaf->GetAvgRayContribution() > mTermMaxRayContribution)
1080	++ mStat.maxRayContribNodes;
1081
1082	if (SqrMagnitude(data.mBox.Size()) <= mTermMinSize)
1083	++ mStat.minSizeNodes;
1084	}
1085
1086
1087	inline bool VspKdTree::TerminationCriteriaMet(const VspKdLeaf *leaf,
1088	const AxisAlignedBox3 &box) const
1089	{
1090	return ((leaf->GetPvsSize() < mTermMinPvs) \|\|
1091	(leaf->mRays.size() < mTermMinRays) \|\|
1092	(leaf->GetAvgRayContribution() > mTermMaxRayContribution ) \|\|
1093	(leaf->mDepth >= mTermMaxDepth) \|\|
1094	(SqrMagnitude(box.Size()) <= mTermMinSize));
1095	}
1096
1097
1098	VspKdNode VspKdTree::SubdivideNode(VspKdLeaf leaf,
1099	const AxisAlignedBox3 &box,
1100	AxisAlignedBox3 &backBBox,
1101	AxisAlignedBox3 &frontBBox)
1102	{
1103	if (TerminationCriteriaMet(leaf, box))
1104	{
1105	if (1 && leaf->mDepth >= mTermMaxDepth)
1106	{
1107	Debug << "Warning: max depth reached depth=" << (int)leaf->mDepth<<" rays=" << (int)leaf->mRays.size() << endl;
1108	Debug << "Bbox: " << GetBBox(leaf) << endl;
1109	}
1110	//Debug << "depth: " << (int)leaf->mDepth << " pvs: " << leaf->GetPvsSize() << " rays: " << leaf->mRays.size() << endl;
1111
1112	return leaf;
1113	}
1114
1115	float position;
1116	// first count ray sides
1117	int raysBack;
1118	int raysFront;
1119	int pvsBack;
1120	int pvsFront;
1121
1122	// select subdivision axis
1123	const int axis = SelectPlane(leaf, box, position, raysBack, raysFront, pvsBack, pvsFront);
1124	//Debug << "rays back=" << raysBack << " rays front=" << raysFront << " pvs back=" << pvsBack << " pvs front=" << pvsFront << endl;
1125
1126	if (axis == -1)
1127	return leaf;
1128
1129	mStat.nodes += 2;
1130	++ mStat.splits[axis];
1131
1132	// add the new nodes to the tree
1133	VspKdInterior *node = new VspKdInterior(leaf->mParent);
1134
1135	node->mAxis = axis;
1136	node->mPosition = position;
1137	node->mBox = box;
1138
1139	backBBox = box;
1140	frontBBox = box;
1141
1142	VspKdLeaf *back = new VspKdLeaf(node, raysBack, leaf->GetMaxCostMisses());
1143	back->SetPvsSize(pvsBack);
1144	VspKdLeaf *front = new VspKdLeaf(node, raysFront, leaf->GetMaxCostMisses());
1145	front->SetPvsSize(pvsFront);
1146
1147	// replace a link from node's parent
1148	if (leaf->mParent)
1149	leaf->mParent->ReplaceChildLink(leaf, node);
1150	// and setup child links
1151	node->SetupChildLinks(back, front);
1152
1153	if (axis <= VspKdNode::SPLIT_Z)
1154	{
1155	backBBox.SetMax(axis, position);
1156	frontBBox.SetMin(axis, position);
1157
1158	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
1159	ri != leaf->mRays.end(); ++ ri)
1160	{
1161	if ((*ri).mRay->IsActive())
1162	{
1163	// first unref ray from the former leaf
1164	(*ri).mRay->Unref();
1165	float t;
1166	// determine the side of this ray with respect to the plane
1167	int side = node->ComputeRayIntersection(*ri, t);
1168
1169	if (side == 0)
1170	{
1171	if ((*ri).mRay->HasPosDir(axis))
1172	{
1173	back->AddRay(RayInfo((*ri).mRay,
1174	(*ri).mMinT,
1175	t));
1176	front->AddRay(RayInfo((*ri).mRay,
1177	t,
1178	(*ri).mMaxT));
1179	}
1180	else
1181	{
1182	back->AddRay(RayInfo((*ri).mRay,
1183	t,
1184	(*ri).mMaxT));
1185	front->AddRay(RayInfo((*ri).mRay,
1186	(*ri).mMinT,
1187	t));
1188	}
1189	}
1190	else
1191	if (side == 1)
1192	front->AddRay(*ri);
1193	else
1194	back->AddRay(*ri);
1195	} else
1196	(*ri).mRay->Unref();
1197	}
1198	}
1199	else
1200	{
1201	// rays front/back
1202
1203	for (RayInfoContainer::iterator ri = leaf->mRays.begin();
1204	ri != leaf->mRays.end(); ++ ri)
1205	{
1206	if ((*ri).mRay->IsActive())
1207	{
1208	// first unref ray from the former leaf
1209	(*ri).mRay->Unref();
1210
1211	int side;
1212	if ((*ri).mRay->GetDirParametrization(axis - 3) > position)
1213	side = 1;
1214	else
1215	side = -1;
1216
1217	if (side == 1)
1218	front->AddRay(*ri);
1219	else
1220	back->AddRay(*ri);
1221	}
1222	else
1223	(*ri).mRay->Unref();
1224	}
1225	}
1226
1227	// update stats
1228	mStat.rayRefs -= (int)leaf->mRays.size();
1229	mStat.rayRefs += raysBack + raysFront;
1230
1231	DEL_PTR(leaf);
1232
1233	return node;
1234	}
1235
1236	int VspKdTree::ReleaseMemory(const int time)
1237	{
1238	stack<VspKdNode *> tstack;
1239
1240	// find a node in the tree which subtree will be collapsed
1241	int maxAccessTime = time - mAccessTimeThreshold;
1242	int released = 0;
1243
1244	tstack.push(mRoot);
1245
1246	while (!tstack.empty())
1247	{
1248	VspKdNode *node = tstack.top();
1249	tstack.pop();
1250
1251	if (!node->IsLeaf())
1252	{
1253	VspKdInterior in = dynamic_cast<VspKdInterior >(node);
1254	// cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
1255	if (in->mDepth >= mMinCollapseDepth && in->mLastAccessTime <= maxAccessTime)
1256	{
1257	released = CollapseSubtree(node, time);
1258	break;
1259	}
1260	if (in->GetBack()->GetAccessTime() < in->GetFront()->GetAccessTime())
1261	{
1262	tstack.push(in->GetFront());
1263	tstack.push(in->GetBack());
1264	}
1265	else
1266	{
1267	tstack.push(in->GetBack());
1268	tstack.push(in->GetFront());
1269	}
1270	}
1271	}
1272
1273	while (tstack.empty())
1274	{
1275	// could find node to collaps...
1276	// cout<<"Could not find a node to release "<<endl;
1277	break;
1278	}
1279
1280	return released;
1281	}
1282
1283
1284	VspKdNode VspKdTree::SubdivideLeaf(VspKdLeaf leaf,
1285	const float sizeThreshold)
1286	{
1287	VspKdNode *node = leaf;
1288
1289	AxisAlignedBox3 leafBBox = GetBBox(leaf);
1290
1291	static int pass = 0;
1292	++ pass;
1293
1294	// check if we should perform a dynamic subdivision of the leaf
1295	if (// leaf->mRays.size() > (unsigned)termMinCost &&
1296	(leaf->GetPvsSize() >= mTermMinPvs) &&
1297	(SqrMagnitude(leafBBox.Size()) > sizeThreshold) )
1298	{
1299	// memory check and release
1300	if (GetMemUsage() > mMaxTotalMemory)
1301	ReleaseMemory(pass);
1302
1303	AxisAlignedBox3 backBBox, frontBBox;
1304
1305	// subdivide the node
1306	node = SubdivideNode(leaf, leafBBox, backBBox, frontBBox);
1307	}
1308	return node;
1309	}
1310
1311
1312
1313	void VspKdTree::UpdateRays(VssRayContainer &remove,
1314	VssRayContainer &add)
1315	{
1316	VspKdLeaf::NewMail();
1317
1318	// schedule rays for removal
1319	for(VssRayContainer::const_iterator ri = remove.begin();
1320	ri != remove.end(); ++ ri)
1321	{
1322	(*ri)->ScheduleForRemoval();
1323	}
1324
1325	int inactive = 0;
1326
1327	for (VssRayContainer::const_iterator ri = remove.begin(); ri != remove.end(); ++ ri)
1328	{
1329	if ((*ri)->ScheduledForRemoval())
1330	// RemoveRay(*ri, NULL, false);
1331	// !!! BUG - with true it does not work correctly - aggreated delete
1332	RemoveRay(*ri, NULL, true);
1333	else
1334	++ inactive;
1335	}
1336
1337	// cout<<"all/inactive"<<remove.size()<<"/"<<inactive<<endl;
1338	for (VssRayContainer::const_iterator ri = add.begin(); ri != add.end(); ++ ri)
1339	{
1340	AddRay(*ri);
1341	}
1342	}
1343
1344
1345	void VspKdTree::RemoveRay(VssRay *ray,
1346	vector<VspKdLeaf > affectedLeaves,
1347	const bool removeAllScheduledRays)
1348	{
1349	stack<RayTraversalData> tstack;
1350
1351	tstack.push(RayTraversalData(mRoot, RayInfo(ray)));
1352
1353	RayTraversalData data;
1354
1355	// cout<<"Number of ray refs = "<<ray->RefCount()<<endl;
1356	while (!tstack.empty())
1357	{
1358	data = tstack.top();
1359	tstack.pop();
1360
1361	if (!data.mNode->IsLeaf())
1362	{
1363	// split the set of rays in two groups intersecting the
1364	// two subtrees
1365	TraverseInternalNode(data, tstack);
1366	}
1367	else
1368	{
1369	// remove the ray from the leaf
1370	// find the ray in the leaf and swap it with the last ray...
1371	VspKdLeaf leaf = (VspKdLeaf )data.mNode;
1372
1373	if (!leaf->Mailed())
1374	{
1375	leaf->Mail();
1376
1377	if (affectedLeaves)
1378	affectedLeaves->push_back(leaf);
1379
1380	if (removeAllScheduledRays)
1381	{
1382	int tail = (int)leaf->mRays.size() - 1;
1383
1384	for (int i=0; i < (int)(leaf->mRays.size()); ++ i)
1385	{
1386	if (leaf->mRays[i].mRay->ScheduledForRemoval())
1387	{
1388	// find a ray to replace it with
1389	while (tail >= i && leaf->mRays[tail].mRay->ScheduledForRemoval())
1390	{
1391	++ mStat.removedRayRefs;
1392	leaf->mRays[tail].mRay->Unref();
1393	leaf->mRays.pop_back();
1394
1395	-- tail;
1396	}
1397
1398	if (tail < i)
1399	break;
1400
1401	++ mStat.removedRayRefs;
1402
1403	leaf->mRays[i].mRay->Unref();
1404	leaf->mRays[i] = leaf->mRays[tail];
1405	leaf->mRays.pop_back();
1406	-- tail;
1407	}
1408	}
1409	}
1410	}
1411
1412	if (!removeAllScheduledRays)
1413	for (int i=0; i < (int)leaf->mRays.size(); i++)
1414	{
1415	if (leaf->mRays[i].mRay == ray)
1416	{
1417	++ mStat.removedRayRefs;
1418	ray->Unref();
1419	leaf->mRays[i] = leaf->mRays[leaf->mRays.size() - 1];
1420	leaf->mRays.pop_back();
1421	// check this ray again
1422	break;
1423	}
1424	}
1425	}
1426	}
1427
1428	if (ray->RefCount() != 0)
1429	{
1430	cerr << "Error: Number of remaining refs = " << ray->RefCount() << endl;
1431	exit(1);
1432	}
1433
1434	}
1435
1436	void VspKdTree::AddRay(VssRay *ray)
1437	{
1438	stack<RayTraversalData> tstack;
1439
1440	tstack.push(RayTraversalData(mRoot, RayInfo(ray)));
1441
1442	RayTraversalData data;
1443
1444	while (!tstack.empty())
1445	{
1446	data = tstack.top();
1447	tstack.pop();
1448
1449	if (!data.mNode->IsLeaf())
1450	{
1451	TraverseInternalNode(data, tstack);
1452	}
1453	else
1454	{
1455	// remove the ray from the leaf
1456	// find the ray in the leaf and swap it with the last ray
1457	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(data.mNode);
1458
1459	leaf->AddRay(data.mRayData);
1460	++ mStat.addedRayRefs;
1461	}
1462	}
1463	}
1464
1465	void VspKdTree::TraverseInternalNode(RayTraversalData &data,
1466	stack<RayTraversalData> &tstack)
1467	{
1468	VspKdInterior in = dynamic_cast<VspKdInterior >(data.mNode);
1469
1470	if (in->mAxis <= VspKdNode::SPLIT_Z)
1471	{
1472	// determine the side of this ray with respect to the plane
1473	float t;
1474	const int side = in->ComputeRayIntersection(data.mRayData, t);
1475
1476	if (side == 0)
1477	{
1478	if (data.mRayData.mRay->HasPosDir(in->mAxis))
1479	{
1480	tstack.push(RayTraversalData(in->GetBack(),
1481	RayInfo(data.mRayData.mRay, data.mRayData.mMinT, t)));
1482
1483	tstack.push(RayTraversalData(in->GetFront(),
1484	RayInfo(data.mRayData.mRay, t, data.mRayData.mMaxT)));
1485
1486	}
1487	else
1488	{
1489	tstack.push(RayTraversalData(in->GetBack(),
1490	RayInfo(data.mRayData.mRay,
1491	t,
1492	data.mRayData.mMaxT)));
1493	tstack.push(RayTraversalData(in->GetFront(),
1494	RayInfo(data.mRayData.mRay,
1495	data.mRayData.mMinT,
1496	t)));
1497	}
1498	}
1499	else
1500	if (side == 1)
1501	tstack.push(RayTraversalData(in->GetFront(), data.mRayData));
1502	else
1503	tstack.push(RayTraversalData(in->GetBack(), data.mRayData));
1504	}
1505	else
1506	{
1507	// directional split
1508	if (data.mRayData.mRay->GetDirParametrization(in->mAxis - 3) > in->mPosition)
1509	tstack.push(RayTraversalData(in->GetFront(), data.mRayData));
1510	else
1511	tstack.push(RayTraversalData(in->GetBack(), data.mRayData));
1512	}
1513	}
1514
1515
1516	int VspKdTree::CollapseSubtree(VspKdNode *sroot, const int time)
1517	{
1518	// first count all rays in the subtree
1519	// use mail 1 for this purpose
1520	stack<VspKdNode *> tstack;
1521
1522	int rayCount = 0;
1523	int totalRayCount = 0;
1524	int collapsedNodes = 0;
1525
1526	#if DEBUG_COLLAPSE
1527	cout << "Collapsing subtree" << endl;
1528	cout << "accessTime=" << sroot->GetAccessTime() << endl;
1529	cout << "depth=" << (int)sroot->depth << endl;
1530	#endif
1531
1532	// tstat.collapsedSubtrees++;
1533	// tstat.collapseDepths += (int)sroot->depth;
1534	// tstat.collapseAccessTimes += time - sroot->GetAccessTime();
1535	tstack.push(sroot);
1536	VssRay::NewMail();
1537
1538	while (!tstack.empty())
1539	{
1540	++ collapsedNodes;
1541
1542	VspKdNode *node = tstack.top();
1543	tstack.pop();
1544	if (node->IsLeaf())
1545	{
1546	VspKdLeaf leaf = (VspKdLeaf ) node;
1547
1548	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
1549	ri != leaf->mRays.end(); ++ ri)
1550	{
1551	++ totalRayCount;
1552
1553	if ((ri).mRay->IsActive() && !(ri).mRay->Mailed())
1554	{
1555	(*ri).mRay->Mail();
1556	++ rayCount;
1557	}
1558	}
1559	}
1560	else
1561	{
1562	tstack.push(dynamic_cast<VspKdInterior *>(node)->GetFront());
1563	tstack.push(dynamic_cast<VspKdInterior *>(node)->GetBack());
1564	}
1565	}
1566
1567	VssRay::NewMail();
1568
1569	// create a new node that will hold the rays
1570	VspKdLeaf *newLeaf = new VspKdLeaf(sroot->mParent, rayCount);
1571
1572	if (newLeaf->mParent)
1573	{
1574	newLeaf->mParent->ReplaceChildLink(sroot, newLeaf);
1575	}
1576	tstack.push(sroot);
1577
1578	while (!tstack.empty())
1579	{
1580	VspKdNode *node = tstack.top();
1581	tstack.pop();
1582
1583	if (node->IsLeaf())
1584	{
1585	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(node);
1586
1587	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
1588	ri != leaf->mRays.end(); ++ ri)
1589	{
1590	// unref this ray from the old node
1591	if ((*ri).mRay->IsActive())
1592	{
1593	(*ri).mRay->Unref();
1594	if (!(*ri).mRay->Mailed())
1595	{
1596	(*ri).mRay->Mail();
1597	newLeaf->AddRay(*ri);
1598	}
1599	}
1600	else
1601	(*ri).mRay->Unref();
1602	}
1603	}
1604	else
1605	{
1606	VspKdInterior *interior =
1607	dynamic_cast<VspKdInterior *>(node);
1608	tstack.push(interior->GetBack());
1609	tstack.push(interior->GetFront());
1610	}
1611	}
1612
1613	// delete the node and all its children
1614	DEL_PTR(sroot);
1615
1616	// for(VspKdNode::SRayContainer::iterator ri = newleaf->mRays.begin();
1617	// ri != newleaf->mRays.end(); ++ ri)
1618	// (*ri).ray->UnMail(2);
1619
1620	#if DEBUG_COLLAPSE
1621	cout << "Total memory before=" << GetMemUsage() << endl;
1622	#endif
1623
1624	mStat.nodes -= collapsedNodes - 1;
1625	mStat.rayRefs -= totalRayCount - rayCount;
1626
1627	#if DEBUG_COLLAPSE
1628	cout << "collapsed nodes" << collapsedNodes << endl;
1629	cout << "collapsed rays" << totalRayCount - rayCount << endl;
1630	cout << "Total memory after=" << GetMemUsage() << endl;
1631	cout << "================================" << endl;
1632	#endif
1633
1634	// tstat.collapsedNodes += collapsedNodes;
1635	// tstat.collapsedRays += totalRayCount - rayCount;
1636	return totalRayCount - rayCount;
1637	}
1638
1639
1640	int VspKdTree::GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const
1641	{
1642	stack<VspKdNode *> tstack;
1643	tstack.push(mRoot);
1644
1645	Intersectable::NewMail();
1646	int pvsSize = 0;
1647
1648	while (!tstack.empty())
1649	{
1650	VspKdNode *node = tstack.top();
1651	tstack.pop();
1652
1653	if (node->IsLeaf())
1654	{
1655	VspKdLeaf leaf = (VspKdLeaf )node;
1656	for (RayInfoContainer::iterator ri = leaf->mRays.begin();
1657	ri != leaf->mRays.end(); ++ ri)
1658	{
1659	if ((*ri).mRay->IsActive())
1660	{
1661	Intersectable *object;
1662	#if BIDIRECTIONAL_RAY
1663	object = (*ri).mRay->mOriginObject;
1664
1665	if (object && !object->Mailed())
1666	{
1667	++ pvsSize;
1668	object->Mail();
1669	}
1670	#endif
1671	object = (*ri).mRay->mTerminationObject;
1672	if (object && !object->Mailed())
1673	{
1674	++ pvsSize;
1675	object->Mail();
1676	}
1677	}
1678	}
1679	}
1680	else
1681	{
1682	VspKdInterior in = dynamic_cast<VspKdInterior >(node);
1683
1684	if (in->mAxis < 3)
1685	{
1686	if (box.Max(in->mAxis) >= in->mPosition)
1687	tstack.push(in->GetFront());
1688
1689	if (box.Min(in->mAxis) <= in->mPosition)
1690	tstack.push(in->GetBack());
1691	}
1692	else
1693	{
1694	// both nodes for directional splits
1695	tstack.push(in->GetFront());
1696	tstack.push(in->GetBack());
1697	}
1698	}
1699	}
1700
1701	return pvsSize;
1702	}
1703
1704	void VspKdTree::GetRayContributionStatistics(float &minRayContribution,
1705	float &maxRayContribution,
1706	float &avgRayContribution)
1707	{
1708	stack<VspKdNode *> tstack;
1709	tstack.push(mRoot);
1710
1711	minRayContribution = 1.0f;
1712	maxRayContribution = 0.0f;
1713
1714	float sumRayContribution = 0.0f;
1715	int leaves = 0;
1716
1717	while (!tstack.empty())
1718	{
1719	VspKdNode *node = tstack.top();
1720	tstack.pop();
1721	if (node->IsLeaf())
1722	{
1723	leaves++;
1724	VspKdLeaf leaf = (VspKdLeaf )node;
1725	float c = leaf->GetAvgRayContribution();
1726
1727	if (c > maxRayContribution)
1728	maxRayContribution = c;
1729	if (c < minRayContribution)
1730	minRayContribution = c;
1731	sumRayContribution += c;
1732
1733	}
1734	else
1735	{
1736	VspKdInterior in = (VspKdInterior )node;
1737
1738	tstack.push(in->GetFront());
1739	tstack.push(in->GetBack());
1740	}
1741	}
1742
1743	Debug << "sum=" << sumRayContribution << endl;
1744	Debug << "leaves=" << leaves << endl;
1745	avgRayContribution = sumRayContribution / (float)leaves;
1746	}
1747
1748
1749	int VspKdTree::GenerateRays(const float ratioPerLeaf,
1750	SimpleRayContainer &rays)
1751	{
1752	stack<VspKdNode *> tstack;
1753	tstack.push(mRoot);
1754
1755	while (!tstack.empty())
1756	{
1757	VspKdNode *node = tstack.top();
1758	tstack.pop();
1759
1760	if (node->IsLeaf())
1761	{
1762	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(node);
1763
1764	float c = leaf->GetAvgRayContribution();
1765	int num = (int)(c*ratioPerLeaf + 0.5);
1766	// cout<<num<<" ";
1767
1768	for (int i=0; i < num; i++)
1769	{
1770	Vector3 origin = GetBBox(leaf).GetRandomPoint();
1771	/*Vector3 dirVector = GetDirBBox(leaf).GetRandomPoint();
1772	Vector3 direction = Vector3(sin(dirVector.x), sin(dirVector.y), cos(dirVector.x));
1773	//cout<<"dir vector.x="<<dirVector.x<<"direction'.x="<<atan2(direction.x, direction.y)<<endl;
1774	rays.push_back(SimpleRay(origin, direction));*/
1775	}
1776
1777	}
1778	else
1779	{
1780	VspKdInterior *in =
1781	dynamic_cast<VspKdInterior *>(node);
1782
1783	tstack.push(in->GetFront());
1784	tstack.push(in->GetBack());
1785	}
1786	}
1787
1788	return (int)rays.size();
1789	}
1790
1791
1792	float VspKdTree::GetAvgPvsSize()
1793	{
1794	stack<VspKdNode *> tstack;
1795	tstack.push(mRoot);
1796
1797	int sumPvs = 0;
1798	int leaves = 0;
1799
1800	while (!tstack.empty())
1801	{
1802	VspKdNode *node = tstack.top();
1803	tstack.pop();
1804
1805	if (node->IsLeaf())
1806	{
1807	VspKdLeaf leaf = (VspKdLeaf )node;
1808	// update pvs size
1809	leaf->UpdatePvsSize();
1810	sumPvs += leaf->GetPvsSize();
1811	leaves++;
1812	}
1813	else
1814	{
1815	VspKdInterior in = (VspKdInterior )node;
1816
1817	tstack.push(in->GetFront());
1818	tstack.push(in->GetBack());
1819	}
1820	}
1821
1822	return sumPvs / (float)leaves;
1823	}
1824
1825	VspKdNode *VspKdTree::GetRoot() const
1826	{
1827	return mRoot;
1828	}
1829
1830	AxisAlignedBox3 VspKdTree::GetBBox(VspKdNode *node) const
1831	{
1832	if (node->mParent == NULL)
1833	return mBox;
1834
1835	if (!node->IsLeaf())
1836	return (dynamic_cast<VspKdInterior *>(node))->mBox;
1837
1838	if (node->mParent->mAxis >= 3)
1839	return node->mParent->mBox;
1840
1841	AxisAlignedBox3 box(node->mParent->mBox);
1842	if (node->mParent->GetFront() == node)
1843	box.SetMin(node->mParent->mAxis, node->mParent->mPosition);
1844	else
1845	box.SetMax(node->mParent->mAxis, node->mParent->mPosition);
1846
1847	return box;
1848	}
1849
1850	int VspKdTree::GetRootPvsSize() const
1851	{
1852	return GetPvsSize(mRoot, mBox);
1853	}
1854
1855	const VspKdStatistics &VspKdTree::GetStatistics() const
1856	{
1857	return mStat;
1858	}
1859
1860	void VspKdTree::AddRays(VssRayContainer &add)
1861	{
1862	VssRayContainer remove;
1863	UpdateRays(remove, add);
1864	}
1865
1866	// return memory usage in MB
1867	float VspKdTree::GetMemUsage() const
1868	{
1869	return
1870	(sizeof(VspKdTree) +
1871	mStat.Leaves() * sizeof(VspKdLeaf) +
1872	mStat.Interior() * sizeof(VspKdInterior) +
1873	mStat.rayRefs * sizeof(RayInfo)) / (1024.0f * 1024.0f);
1874	}
1875
1876	float VspKdTree::GetRayMemUsage() const
1877	{
1878	return mStat.rays * (sizeof(VssRay))/(1024.0f * 1024.0f);
1879	}
1880
1881
1882	int VspKdTree::ComputePvsSize(VspKdNode *node,
1883	const RayInfoContainer &globalRays) const
1884	{
1885	int pvsSize = 0;
1886
1887	const AxisAlignedBox3 box = GetBBox(node);
1888
1889	RayInfoContainer::const_iterator it, it_end = globalRays.end();
1890
1891	Intersectable::NewMail();
1892
1893	// warning: implicit conversion from VssRay to Ray
1894	for (it = globalRays.begin(); it != globalRays.end(); ++ it)
1895	{
1896	VssRay ray = (it).mRay;
1897
1898	// ray intersects node bounding box
1899	if (box.GetMinMaxT(*ray, NULL, NULL))
1900	{
1901	if (ray->mTerminationObject && !ray->mTerminationObject->Mailed())
1902	{
1903	ray->mTerminationObject->Mail();
1904	++ pvsSize;
1905	}
1906	}
1907	}
1908	return pvsSize;
1909	}
1910
1911
1912	void VspKdTree::CollectLeaves(vector<VspKdLeaf *> &leaves) const
1913	{
1914	stack<VspKdNode *> nodeStack;
1915	nodeStack.push(mRoot);
1916
1917	while (!nodeStack.empty())
1918	{
1919	VspKdNode *node = nodeStack.top();
1920
1921	nodeStack.pop();
1922
1923	if (node->IsLeaf())
1924	{
1925	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(node);
1926	leaves.push_back(leaf);
1927	}
1928	else
1929	{
1930	VspKdInterior interior = dynamic_cast<VspKdInterior >(node);
1931
1932	nodeStack.push(interior->GetBack());
1933	nodeStack.push(interior->GetFront());
1934	}
1935	}
1936	}
1937
1938	int VspKdTree::FindNeighbors(VspKdLeaf *n,
1939	vector<VspKdLeaf *> &neighbors,
1940	bool onlyUnmailed)
1941	{
1942	stack<VspKdNode *> nodeStack;
1943
1944	nodeStack.push(mRoot);
1945
1946	AxisAlignedBox3 box = GetBBox(n);
1947
1948	while (!nodeStack.empty())
1949	{
1950	VspKdNode *node = nodeStack.top();
1951	nodeStack.pop();
1952
1953	if (node->IsLeaf())
1954	{
1955	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(node);
1956
1957	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
1958	neighbors.push_back(leaf);
1959	}
1960	else
1961	{
1962	VspKdInterior interior = dynamic_cast<VspKdInterior >(node);
1963
1964	if (interior->mPosition > box.Max(interior->mAxis))
1965	nodeStack.push(interior->mBack);
1966	else
1967	{
1968	if (interior->mPosition < box.Min(interior->mAxis))
1969	nodeStack.push(interior->mFront);
1970	else
1971	{
1972	// random decision
1973	nodeStack.push(interior->mBack);
1974	nodeStack.push(interior->mFront);
1975	}
1976	}
1977	}
1978	}
1979
1980	return (int)neighbors.size();
1981	}
1982
1983
1984	void VspKdTree::SetViewCellsManager(ViewCellsManager *vcm)
1985	{
1986	mViewCellsManager = vcm;
1987	}
1988
1989
1990	int VspKdTree::CastLineSegment(const Vector3 &origin,
1991	const Vector3 &termination,
1992	vector<ViewCell *> &viewcells)
1993	{
1994	int hits = 0;
1995
1996	float mint = 0.0f, maxt = 1.0f;
1997	const Vector3 dir = termination - origin;
1998
1999	stack<LineTraversalData> tStack;
2000
2001	Intersectable::NewMail();
2002
2003	Vector3 entp = origin;
2004	Vector3 extp = termination;
2005
2006	VspKdNode *node = mRoot;
2007	VspKdNode *farChild;
2008
2009	float position;
2010	int axis;
2011
2012	while (1)
2013	{
2014	if (!node->IsLeaf())
2015	{
2016	VspKdInterior in = dynamic_cast<VspKdInterior >(node);
2017	position = in->mPosition;
2018	axis = in->mAxis;
2019
2020	if (entp[axis] <= position)
2021	{
2022	if (extp[axis] <= position)
2023	{
2024	node = in->mBack;
2025	// cases N1,N2,N3,P5,Z2,Z3
2026	continue;
2027	} else
2028	{
2029	// case N4
2030	node = in->mBack;
2031	farChild = in->mFront;
2032	}
2033	}
2034	else
2035	{
2036	if (position <= extp[axis])
2037	{
2038	node = in->mFront;
2039	// cases P1,P2,P3,N5,Z1
2040	continue;
2041	}
2042	else
2043	{
2044	node = in->mFront;
2045	farChild = in->mBack;
2046	// case P4
2047	}
2048	}
2049
2050	// $$ modification 3.5.2004 - hints from Kamil Ghais
2051	// case N4 or P4
2052	float tdist = (position - origin[axis]) / dir[axis];
2053	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2054	extp = origin + dir * tdist;
2055	maxt = tdist;
2056	}
2057	else
2058	{
2059	// compute intersection with all objects in this leaf
2060	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(node);
2061	ViewCell *vc = leaf->GetViewCell();
2062
2063	if (!vc->Mailed())
2064	{
2065	vc->Mail();
2066	viewcells.push_back(vc);
2067	++ hits;
2068	}
2069
2070	if (0) //matt TODO: REMOVE LATER
2071	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
2072
2073	// get the next node from the stack
2074	if (tStack.empty())
2075	break;
2076
2077	entp = extp;
2078	mint = maxt;
2079
2080	LineTraversalData &s = tStack.top();
2081	node = s.mNode;
2082	extp = s.mExitPoint;
2083	maxt = s.mMaxT;
2084	tStack.pop();
2085	}
2086	}
2087
2088	return hits;
2089	}
2090
2091
2092	void VspKdTree::GenerateViewCell(VspKdLeaf *leaf)
2093	{
2094	RayInfoContainer::const_iterator it, it_end = leaf->GetRays().end();
2095
2096	VspKdViewCell vc = dynamic_cast<VspKdViewCell >(mViewCellsManager->GenerateViewCell());
2097	leaf->SetViewCell(vc);
2098
2099	vc->SetVolume(GetBBox(leaf).GetVolume());
2100	vc->SetArea(GetBBox(leaf).SurfaceArea());
2101
2102	vc->mLeaves.push_back(leaf);
2103
2104	for (it = leaf->GetRays().begin(); it != it_end; ++ it)
2105	{
2106	VssRay ray = (it).mRay;
2107
2108	if (ray->mTerminationObject)
2109	vc->GetPvs().AddSample(ray->mTerminationObject);
2110
2111	if (ray->mOriginObject)
2112	vc->GetPvs().AddSample(ray->mOriginObject);
2113	}
2114	}
2115
2116
2117	bool VspKdTree::MergeViewCells(VspKdLeaf l1, VspKdLeaf l2)
2118	{
2119	//-- change pointer to view cells of all leaves associated
2120	//-- with the previous view cells
2121	VspKdViewCell *fVc = l1->GetViewCell();
2122	VspKdViewCell *bVc = l2->GetViewCell();
2123
2124	VspKdViewCell vc = dynamic_cast<VspKdViewCell >(
2125	mViewCellsManager->MergeViewCells(fVc, bVc));
2126
2127	// if merge was unsuccessful
2128	if (!vc) return false;
2129
2130	// set new size of view cell
2131	vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
2132	// new area
2133	vc->SetArea(fVc->GetArea() + bVc->GetArea());
2134
2135	vector<VspKdLeaf *> fLeaves = fVc->mLeaves;
2136	vector<VspKdLeaf *> bLeaves = bVc->mLeaves;
2137
2138	vector<VspKdLeaf *>::const_iterator it;
2139
2140	//-- change view cells of all the other leaves the view cell belongs to
2141	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
2142	{
2143	(*it)->SetViewCell(vc);
2144	vc->mLeaves.push_back(*it);
2145	}
2146
2147	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
2148	{
2149	(*it)->SetViewCell(vc);
2150	vc->mLeaves.push_back(*it);
2151	}
2152
2153	vc->Mail();
2154
2155	// clean up old view cells
2156	DEL_PTR(fVc);
2157	DEL_PTR(bVc);
2158
2159	return true;
2160	}
2161
2162	void VspKdTree::CollectMergeCandidates()
2163	{
2164	MergeCandidate::sOverallCost = 0;
2165	vector<VspKdLeaf *> leaves;
2166
2167	// collect the leaves, e.g., the "voxels" that will build the view cells
2168	CollectLeaves(leaves);
2169
2170	VspKdLeaf::NewMail();
2171
2172	vector<VspKdLeaf *>::const_iterator it, it_end = leaves.end();
2173
2174	// generate view cells
2175	for (it = leaves.begin(); it != it_end; ++ it)
2176	GenerateViewCell(*it);
2177
2178	// find merge candidates and push them into queue
2179	for (it = leaves.begin(); it != it_end; ++ it)
2180	{
2181	VspKdLeaf leaf = it;
2182	ViewCell *vc = leaf->GetViewCell();
2183	// no leaf is part of two merge candidates
2184	leaf->Mail();
2185	MergeCandidate::sOverallCost +=
2186	vc->GetVolume() * vc->GetPvs().GetSize();
2187	vector<VspKdLeaf *> neighbors;
2188	FindNeighbors(leaf, neighbors, true);
2189
2190	vector<VspKdLeaf *>::const_iterator nit,
2191	nit_end = neighbors.end();
2192
2193	for (nit = neighbors.begin(); nit != nit_end; ++ nit)
2194	{
2195	mMergeQueue.push(MergeCandidate(leaf, *nit));
2196	}
2197	}
2198	}
2199	#if 0
2200	void VspKdTree::CollectMergeCandidates(const vector<VspKdRay *> &rays)
2201	{
2202	MergeCandidate::sOverallCost = 0;
2203
2204	vector<VspKdIntersection>::const_iterator iit;
2205	map<BspLeaf , vector<BspLeaf> candidateMap;
2206
2207	for (int i = 0; i < (int)rays.size(); ++ i)
2208	{
2209	//VspKdLeaf::NewMail();
2210	VspKdRay *ray = rays[i];
2211
2212	// traverse leaves stored in the rays and compare and merge consecutive
2213	// leaves (i.e., the neighbors in the tree)
2214	if (ray->intersections.size() < 2)
2215	continue;
2216
2217	iit = ray->intersections.begin();
2218
2219	BspLeaf previousLeaf = (iit).mLeaf;
2220
2221	++ iit;
2222
2223	for (; iit != ray->intersections.end(); ++ iit)
2224	{
2225	BspLeaf leaf = (iit).mLeaf;
2226	leaf->Mail
2227	// TODO: how to sort out doubles?
2228	MergeCandidate mc = MergeCandidate(leaf, previousLeaf);
2229	mMergeQueue.push(mc);
2230
2231	MergeCandidate::sOverallCost += mc.GetLeaf1Cost();
2232	MergeCandidate::sOverallCost += mc.GetLeaf2Cost();
2233
2234	previousLeaf = leaf;
2235	}
2236	}
2237	}
2238	#endif
2239
2240	int VspKdTree::MergeViewCells(const VssRayContainer &rays)
2241	{
2242	CollectMergeCandidates();
2243
2244	int merged = 0;
2245
2246	int vcSize = mStat.Leaves();
2247	// use priority queue to merge leaves
2248	while (!mMergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
2249	(mMergeQueue.top().GetMergeCost() <
2250	mMergeMaxCostRatio * MergeCandidate::sOverallCost))
2251	{
2252	//Debug << "mergecost: " << mergeQueue.top().GetMergeCost() /
2253	//MergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
2254	MergeCandidate mc = mMergeQueue.top();
2255	mMergeQueue.pop();
2256
2257	// both view cells equal!
2258	if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
2259	continue;
2260
2261	if (mc.Valid())
2262	{
2263	ViewCell::NewMail();
2264	MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
2265
2266	++ merged;
2267	-- vcSize;
2268	// increase absolute merge cost
2269	MergeCandidate::sOverallCost += mc.GetMergeCost();
2270	}
2271	// merge candidate not valid, because one of the leaves was already
2272	// merged with another one
2273	else
2274	{
2275	// validate and reinsert into queue
2276	mc.SetValid();
2277	mMergeQueue.push(mc);
2278	//Debug << "validate " << mc.GetMergeCost() << endl;
2279	}
2280	}
2281
2282	Debug << "merged " << merged << " of " << mStat.Leaves() << " leaves" << endl;
2283
2284	//TODO: should return sample contributions
2285	return merged;
2286	}
2287
2288
2289	void VspKdTree::RepairVcLeafLists()
2290	{
2291	// list not valid anymore => clear
2292	stack<VspKdNode *> nodeStack;
2293	nodeStack.push(mRoot);
2294
2295	ViewCell::NewMail();
2296
2297	while (!nodeStack.empty())
2298	{
2299	VspKdNode *node = nodeStack.top();
2300	nodeStack.pop();
2301
2302	if (node->IsLeaf())
2303	{
2304	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(node);
2305
2306	VspKdViewCell *viewCell = leaf->GetViewCell();
2307
2308	if (!viewCell->Mailed())
2309	{
2310	viewCell->mLeaves.clear();
2311	viewCell->Mail();
2312	}
2313
2314	viewCell->mLeaves.push_back(leaf);
2315	}
2316	else
2317	{
2318	VspKdInterior interior = dynamic_cast<VspKdInterior >(node);
2319
2320	nodeStack.push(interior->GetFront());
2321	nodeStack.push(interior->GetBack());
2322	}
2323	}
2324	}
2325
2326
2327	VspKdNode VspKdTree::CollapseTree(VspKdNode node)
2328	{
2329	if (node->IsLeaf())
2330	return node;
2331
2332	VspKdInterior interior = dynamic_cast<VspKdInterior >(node);
2333
2334	VspKdNode *front = CollapseTree(interior->GetFront());
2335	VspKdNode *back = CollapseTree(interior->GetBack());
2336
2337	if (front->IsLeaf() && back->IsLeaf())
2338	{
2339	VspKdLeaf frontLeaf = dynamic_cast<VspKdLeaf >(front);
2340	VspKdLeaf backLeaf = dynamic_cast<VspKdLeaf >(back);
2341
2342	//-- collapse tree
2343	if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
2344	{
2345	VspKdViewCell *vc = frontLeaf->GetViewCell();
2346
2347	VspKdLeaf *leaf = new VspKdLeaf(interior->GetParent(), 0);
2348	leaf->SetViewCell(vc);
2349
2350	// replace a link from node's parent
2351	if (leaf->mParent)
2352	leaf->mParent->ReplaceChildLink(node, leaf);
2353
2354	delete interior;
2355
2356	return leaf;
2357	}
2358	}
2359
2360	return node;
2361	}
2362
2363
2364	void VspKdTree::CollapseTree()
2365	{
2366	CollapseTree(mRoot);
2367	// revalidate leaves
2368	RepairVcLeafLists();
2369	}
2370
2371	int VspKdTree::RefineViewCells(const VssRayContainer &rays)
2372	{
2373	int shuffled = 0;
2374
2375	Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
2376	BspLeaf::NewMail();
2377
2378	// Use priority queue of remaining leaf pairs
2379	// These candidates either share the same view cells or
2380	// are border leaves which share a boundary.
2381	// We test if they can be shuffled, i.e.,
2382	// either one leaf is made part of one view cell or the other
2383	// leaf is made part of the other view cell. It is tested if the
2384	// remaining view cells are "better" than the old ones.
2385	while (!mMergeQueue.empty())
2386	{
2387	MergeCandidate mc = mMergeQueue.top();
2388	mMergeQueue.pop();
2389
2390	// both view cells equal or already shuffled
2391	if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) \|\|
2392	(mc.GetLeaf1()->Mailed()) \|\| (mc.GetLeaf2()->Mailed()))
2393	continue;
2394
2395	// candidate for shuffling
2396	const bool wasShuffled = false;
2397	//ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
2398	// matt: restore
2399	//-- stats
2400	if (wasShuffled)
2401	++ shuffled;
2402	}
2403
2404	return shuffled;
2405	}
2406
2407
2408	inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
2409	{
2410	return pvs1.AddPvs(pvs2);
2411	}
2412
2413
2414	inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
2415	{
2416	return pvs1.SubtractPvs(pvs2);
2417	}
2418
2419
2420	float GetShuffledVcCost(VspKdLeaf leaf, VspKdViewCell vc1, VspKdViewCell *vc2)
2421	{
2422	const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
2423	const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
2424
2425	const float vol1 = vc1->GetVolume() - leaf->mVolume;
2426	const float vol2 = vc2->GetVolume() + leaf->mVolume;
2427
2428	const float cost1 = pvs1 * vol1;
2429	const float cost2 = pvs2 * vol2;
2430
2431	return cost1 + cost2;
2432	}
2433
2434
2435	void VspKdTree::ShuffleLeaf(VspKdLeaf *leaf,
2436	VspKdViewCell *vc1,
2437	VspKdViewCell *vc2) const
2438	{
2439	// compute new pvs and area
2440	vc1->GetPvs().SubtractPvs(*leaf->mPvs);
2441	vc2->GetPvs().AddPvs(*leaf->mPvs);
2442
2443	vc1->SetArea(vc1->GetVolume() - leaf->mVolume);
2444	vc2->SetArea(vc2->GetVolume() + leaf->mVolume);
2445
2446	/// add to second view cell
2447	vc2->mLeaves.push_back(leaf);
2448
2449	// erase leaf from old view cell
2450	vector<VspKdLeaf *>::iterator it = vc1->mLeaves.begin();
2451
2452	for (; *it != leaf; ++ it);
2453	vc1->mLeaves.erase(it);
2454
2455	leaf->SetViewCell(vc2); // finally change view cell
2456	}
2457
2458
2459	bool VspKdTree::ShuffleLeaves(VspKdLeaf leaf1, VspKdLeaf leaf2) const
2460	{
2461	VspKdViewCell *vc1 = leaf1->GetViewCell();
2462	VspKdViewCell *vc2 = leaf2->GetViewCell();
2463
2464	const float cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
2465	const float cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
2466
2467	const float oldCost = cost1 + cost2;
2468
2469	float shuffledCost1 = Limits::Infinity;
2470	float shuffledCost2 = Limits::Infinity;
2471
2472	// the view cell should not be empty after the shuffle
2473	if (vc1->mLeaves.size() > 1)
2474	shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
2475	if (vc2->mLeaves.size() > 1)
2476	shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
2477
2478	// shuffling unsuccessful
2479	if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
2480	return false;
2481
2482	if (shuffledCost1 < shuffledCost2)
2483	{
2484	ShuffleLeaf(leaf1, vc1, vc2);
2485	leaf1->Mail();
2486	}
2487	else
2488	{
2489	ShuffleLeaf(leaf2, vc2, vc1);
2490	leaf2->Mail();
2491	}
2492
2493	return true;
2494	}
2495
2496
2497
2498
2499	/*********************************************************************/
2500	/* MergeCandidate implementation */
2501	/*********************************************************************/
2502
2503
2504	MergeCandidate::MergeCandidate(VspKdLeaf l1, VspKdLeaf l2):
2505	mMergeCost(0),
2506	mLeaf1(l1),
2507	mLeaf2(l2),
2508	mLeaf1Id(l1->GetViewCell()->mMailbox),
2509	mLeaf2Id(l2->GetViewCell()->mMailbox)
2510	{
2511	EvalMergeCost();
2512	}
2513
2514	float MergeCandidate::GetLeaf1Cost() const
2515	{
2516	VspKdViewCell *vc = mLeaf1->GetViewCell();
2517	return vc->GetPvs().GetSize() * vc->GetVolume();
2518	}
2519
2520	float MergeCandidate::GetLeaf2Cost() const
2521	{
2522	VspKdViewCell *vc = mLeaf2->GetViewCell();
2523	return vc->GetPvs().GetSize() * vc->GetVolume();
2524	}
2525
2526	void MergeCandidate::EvalMergeCost()
2527	{
2528	//-- compute pvs difference
2529	VspKdViewCell *vc1 = mLeaf1->GetViewCell();
2530	VspKdViewCell *vc2 = mLeaf2->GetViewCell();
2531
2532	const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
2533	const int vcPvs = diff1 + vc1->GetPvs().GetSize();
2534
2535	//-- compute ratio of old cost
2536	//-- (added size of left and right view cell times pvs size)
2537	//-- to new rendering cost (size of merged view cell times pvs size)
2538	const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
2539
2540	const float newCost =
2541	(float)vcPvs * (vc1->GetVolume() + vc2->GetVolume());
2542
2543	mMergeCost = newCost - oldCost;
2544
2545	// if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
2546	// mMergeCost += 1.0;
2547	}
2548
2549	void MergeCandidate::SetLeaf1(VspKdLeaf *l)
2550	{
2551	mLeaf1 = l;
2552	}
2553
2554	void MergeCandidate::SetLeaf2(VspKdLeaf *l)
2555	{
2556	mLeaf2 = l;
2557	}
2558
2559
2560	VspKdLeaf *MergeCandidate::GetLeaf1()
2561	{
2562	return mLeaf1;
2563	}
2564
2565
2566	VspKdLeaf *MergeCandidate::GetLeaf2()
2567	{
2568	return mLeaf2;
2569	}
2570
2571
2572	bool MergeCandidate::Valid() const
2573	{
2574	return
2575	(mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
2576	(mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
2577	}
2578
2579
2580	float MergeCandidate::GetMergeCost() const
2581	{
2582	return mMergeCost;
2583	}
2584
2585
2586	void MergeCandidate::SetValid()
2587	{
2588	mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
2589	mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
2590
2591	EvalMergeCost();
2592	}

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

Download in other formats: