Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp @ 2539

Revision 2539, 93.1 KB checked in by mattausch, 17 years ago (diff)
fixed obj loading error

Line
1	#include <stack>
2	#include <time.h>
3	#include <iomanip>
4
5	#include "ViewCell.h"
6	#include "Plane3.h"
7	#include "VspTree.h"
8	#include "Mesh.h"
9	#include "common.h"
10	#include "Environment.h"
11	#include "Polygon3.h"
12	#include "Ray.h"
13	#include "AxisAlignedBox3.h"
14	#include "Exporter.h"
15	#include "Plane3.h"
16	#include "ViewCellsManager.h"
17	#include "Beam.h"
18	#include "KdTree.h"
19	#include "IntersectableWrapper.h"
20	#include "HierarchyManager.h"
21	#include "BvHierarchy.h"
22	#include "OspTree.h"
23
24
25
26	namespace GtpVisibilityPreprocessor {
27
28
29	#define VISUALIZE_SPLIT 0
30	#define USE_FIXEDPOINT_T 0
31	#define HACK_PERFORMANCE 1
32
33
34	#define TYPE_INTERIOR -2
35	#define TYPE_LEAF -3
36
37
38	/////////////
39	//-- static members
40
41	VspTree *VspTree::VspSubdivisionCandidate::sVspTree = NULL;
42	int VspNode::sMailId = 1;
43
44	// variable for debugging volume contribution for heuristics
45	static float debugVol;
46
47
48	// pvs penalty can be different from pvs size
49	inline static float EvalPvsPenalty(const float pvs,
50	const float lower,
51	const float upper)
52	{
53	// clamp to minmax values
54	if (pvs < lower)
55	{
56	return (float)lower;
57	}
58	else if (pvs > upper)
59	{
60	return (float)upper;
61	}
62	return (float)pvs;
63	}
64
65
66	void VspTreeStatistics::Print(ostream &app) const
67	{
68	app << "=========== VspTree statistics ===============\n";
69
70	app << setprecision(4);
71
72	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
73
74	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
75
76	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
77
78	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
79
80	app << "#N_SPLITS ( Number of splits in axes x y z)\n";
81
82	for (int i = 0; i < 3; ++ i)
83	app << splits[i] << " ";
84
85	app << endl;
86
87	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
88	<< maxDepthNodes * 100 / (double)Leaves() << endl;
89
90	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
91	<< minPvsNodes * 100 / (double)Leaves() << endl;
92
93	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n"
94	<< minRaysNodes * 100 / (double)Leaves() << endl;
95
96	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
97	<< maxCostNodes * 100 / (double)Leaves() << endl;
98
99	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
100	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
101
102	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"
103	<< maxRayContribNodes * 100 / (double)Leaves() << endl;
104
105	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
106
107	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
108
109	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
110
111	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
112
113	app << "#AVGRAYS (number of rays / leaf)\n" << AvgRays() << endl;
114
115	app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
116
117	app << "========== END OF VspTree statistics ==========\n";
118	}
119
120
121
122	VspTree::VspTraversalData::VspTraversalData():
123	mNode(NULL),
124	mDepth(0),
125	mRays(NULL),
126	mPvs(0),
127	mProbability(0.0),
128	mMaxCostMisses(0),
129	mPriority(0),
130	mCorrectedPvs(0)
131	{}
132
133
134	VspTree::VspTraversalData::VspTraversalData(VspLeaf *node,
135	const int depth,
136	RayInfoContainer *rays,
137	const float pvs,
138	const float p,
139	const AxisAlignedBox3 &box):
140	mNode(node),
141	mDepth(depth),
142	mRays(rays),
143	mProbability(p),
144	mBoundingBox(box),
145	mMaxCostMisses(0),
146	mPriority(0),
147	mCorrectedPvs(0),
148	mPvs(pvs),
149	mRenderCost(0),
150	mCorrectedRenderCost(0)
151	{}
152
153
154	float VspTree::VspTraversalData::GetAvgRayContribution() const
155	{
156	return (float)mPvs / ((float)mRays->size() + Limits::Small);
157	}
158
159
160	float VspTree::VspTraversalData::GetAvgRaysPerObject() const
161	{
162	return (float)mRays->size() / ((float)mPvs + Limits::Small);
163	}
164
165
166	float VspTree::VspTraversalData::GetCost() const
167	{
168	return mPriority;
169	}
170
171
172	void VspTree::VspTraversalData::Clear()
173	{
174	DEL_PTR(mRays);
175
176	if (mNode)
177	{ // delete old view cell
178	delete mNode->GetViewCell();
179	delete mNode;
180	mNode = NULL;
181	}
182	}
183
184
185	/******************************************************************/
186	/* class VspNode implementation */
187	/******************************************************************/
188
189
190	VspNode::VspNode():
191	mParent(NULL),
192	mTreeValid(true),
193	mTimeStamp(0)
194	{}
195
196
197	VspNode::VspNode(VspInterior *parent):
198	mParent(parent),
199	mTreeValid(true),
200	mTimeStamp(0)
201	{}
202
203
204	bool VspNode::IsRoot() const
205	{
206	return mParent == NULL;
207	}
208
209
210	VspInterior *VspNode::GetParent()
211	{
212	return mParent;
213	}
214
215
216	void VspNode::SetParent(VspInterior *parent)
217	{
218	mParent = parent;
219	}
220
221
222	bool VspNode::IsSibling(VspNode *n) const
223	{
224	return ((this != n) && mParent &&
225	(mParent->GetFront() == n) \|\| (mParent->GetBack() == n));
226	}
227
228
229	int VspNode::GetDepth() const
230	{
231	int depth = 0;
232	VspNode *p = mParent;
233
234	while (p)
235	{
236	p = p->mParent;
237	++ depth;
238	}
239
240	return depth;
241	}
242
243
244	bool VspNode::TreeValid() const
245	{
246	return mTreeValid;
247	}
248
249
250	void VspNode::SetTreeValid(const bool v)
251	{
252	mTreeValid = v;
253	}
254
255
256
257	/****************************************************************/
258	/* class VspInterior implementation */
259	/****************************************************************/
260
261
262	VspInterior::VspInterior(const AxisAlignedPlane &plane):
263	mPlane(plane), mFront(NULL), mBack(NULL)
264	{}
265
266
267	VspInterior::~VspInterior()
268	{
269	DEL_PTR(mFront);
270	DEL_PTR(mBack);
271	}
272
273
274
275
276
277
278	void VspInterior::ReplaceChildLink(VspNode oldChild, VspNode newChild)
279	{
280	if (mBack == oldChild)
281	mBack = newChild;
282	else
283	mFront = newChild;
284	}
285
286
287	void VspInterior::SetupChildLinks(VspNode front, VspNode back)
288	{
289	mBack = back;
290	mFront = front;
291	}
292
293
294	AxisAlignedBox3 VspInterior::GetBoundingBox() const
295	{
296	return mBoundingBox;
297	}
298
299
300	void VspInterior::SetBoundingBox(const AxisAlignedBox3 &box)
301	{
302	mBoundingBox = box;
303	}
304
305
306	int VspInterior::Type() const
307	{
308	return Interior;
309	}
310
311
312
313	/****************************************************************/
314	/* class VspLeaf implementation */
315	/****************************************************************/
316
317
318	VspLeaf::VspLeaf():
319	mViewCell(NULL), mSubdivisionCandidate(NULL)
320	{
321	}
322
323
324	VspLeaf::~VspLeaf()
325	{
326	VssRayContainer::const_iterator vit, vit_end = mVssRays.end();
327
328	for (vit = mVssRays.begin(); vit != vit_end; ++ vit)
329	{
330	VssRay ray = vit;
331	ray->Unref();
332
333	if (!ray->IsActive())
334	delete ray;
335	}
336	}
337
338
339	int VspLeaf::Type() const
340	{
341	return Leaf;
342	}
343
344
345	VspLeaf::VspLeaf(ViewCellLeaf *viewCell):
346	mViewCell(viewCell)
347	{
348	}
349
350
351	VspLeaf::VspLeaf(VspInterior *parent):
352	VspNode(parent), mViewCell(NULL)
353	{}
354
355
356	VspLeaf::VspLeaf(VspInterior parent, ViewCellLeaf viewCell):
357	VspNode(parent), mViewCell(viewCell)
358	{
359	}
360
361
362
363
364	void VspLeaf::SetViewCell(ViewCellLeaf *viewCell)
365	{
366	mViewCell = viewCell;
367	}
368
369
370
371
372
373	/*************************************************************************/
374	/* class VspTree implementation */
375	/*************************************************************************/
376
377
378	VspTree::VspTree():
379	mRoot(NULL),
380	mOutOfBoundsCell(NULL),
381	mStoreRays(false),
382	//mStoreRays(true),
383	mTimeStamp(1),
384	mHierarchyManager(NULL)
385	{
386	mLocalSubdivisionCandidates = new vector<SortableEntry>;
387
388	bool randomize = false;
389	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
390	if (randomize)
391	Randomize(); // initialise random generator for heuristics
392
393	char subdivisionStatsLog[100];
394	Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
395	mSubdivisionStats.open(subdivisionStatsLog);
396
397	/////////////
398	//-- termination criteria for autopartition
399
400	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
401	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
402	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
403	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
404	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
405
406	Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
407	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
408	// max cost ratio for early tree termination
409	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
410
411	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
412	Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
413
414	Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
415
416
417	//////////////
418	//-- factors for bsp tree split plane heuristics
419
420	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
421	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
422	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
423	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
424	Environment::GetSingleton()->GetIntValue("VspTree.maxTests", mMaxTests);
425
426	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
427
428	// if only the driving axis is used for axis aligned split
429	Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
430	Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
431	Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
432
433	//mMemoryConst = (float)(sizeof(VspLeaf) + sizeof(VspViewCell));
434	//mMemoryConst = 50;//(float)(sizeof(VspViewCell));
435	//mMemoryConst = (float)(sizeof(VspLeaf) + sizeof(ObjectPvs));
436
437	mMemoryConst = 16;//(float)sizeof(ObjectPvs);
438
439
440	//////////////
441	//-- debug output
442
443	Debug << "***** VSP options ******" << endl;
444
445	Debug << "max depth: " << mTermMaxDepth << endl;
446	Debug << "min PVS: " << mTermMinPvs << endl;
447	Debug << "min probabiliy: " << mTermMinProbability << endl;
448	Debug << "min rays: " << mTermMinRays << endl;
449	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
450	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
451	Debug << "miss tolerance: " << mTermMissTolerance << endl;
452	Debug << "max view cells: " << mMaxViewCells << endl;
453	Debug << "randomize: " << randomize << endl;
454
455	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
456	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
457	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
458	Debug << "max memory: " << mMaxMemory << endl;
459	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
460	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
461	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
462
463	Debug << "circulating axis: " << mCirculatingAxis << endl;
464	Debug << "minband: " << mMinBand << endl;
465	Debug << "maxband: " << mMaxBand << endl;
466
467	Debug << "vsp mem const: " << mMemoryConst << endl;
468
469	Debug << endl;
470	}
471
472
473	VspViewCell *VspTree::GetOutOfBoundsCell()
474	{
475	return mOutOfBoundsCell;
476	}
477
478
479	VspViewCell *VspTree::GetOrCreateOutOfBoundsCell()
480	{
481	if (!mOutOfBoundsCell)
482	{
483	mOutOfBoundsCell = new VspViewCell();
484	mOutOfBoundsCell->SetId(-1);
485	mOutOfBoundsCell->SetValid(false);
486	}
487
488	return mOutOfBoundsCell;
489	}
490
491
492	const VspTreeStatistics &VspTree::GetStatistics() const
493	{
494	return mVspStats;
495	}
496
497
498	VspTree::~VspTree()
499	{
500	DEL_PTR(mRoot);
501	DEL_PTR(mLocalSubdivisionCandidates);
502	}
503
504
505	void VspTree::ComputeBoundingBox(const VssRayContainer &rays,
506	AxisAlignedBox3 *forcedBoundingBox)
507	{
508	if (forcedBoundingBox)
509	{
510	mBoundingBox = *forcedBoundingBox;
511	return;
512	}
513
514	//////////////////////////////////////////////
515	// bounding box of view space includes all visibility events
516
517	mBoundingBox.Initialize();
518	VssRayContainer::const_iterator rit, rit_end = rays.end();
519
520	for (rit = rays.begin(); rit != rit_end; ++ rit)
521	{
522	VssRay ray = rit;
523
524	mBoundingBox.Include(ray->GetTermination());
525	mBoundingBox.Include(ray->GetOrigin());
526	}
527	}
528
529
530	void VspTree::AddSubdivisionStats(const int viewCells,
531	const float renderCostDecr,
532	const float totalRenderCost,
533	const float avgRenderCost)
534	{
535	mSubdivisionStats
536	<< "#ViewCells\n" << viewCells << endl
537	<< "#RenderCostDecrease\n" << renderCostDecr << endl
538	<< "#TotalRenderCost\n" << totalRenderCost << endl
539	<< "#AvgRenderCost\n" << avgRenderCost << endl;
540	}
541
542
543	// $$matt temporary: number of rayrefs + pvs should be in there, but
544	// commented out for testing
545	float VspTree::GetMemUsage() const
546	{
547	return (float)
548	(sizeof(VspTree)
549	+ mVspStats.Leaves() * sizeof(VspLeaf)
550	+ mVspStats.Leaves() * sizeof(VspViewCell)
551	+ mVspStats.Interior() * sizeof(VspInterior)
552	//+ mVspStats.pvs * sizeof(PvsData)
553	//+ mVspStats.rayRefs * sizeof(RayInfo)
554	) / (1024.0f * 1024.0f);
555	}
556
557
558	inline bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
559	{
560	const bool localTerminationCriteriaMet = (0
561	\|\| ((int)data.mRays->size() <= mTermMinRays)
562	\|\| (data.mPvs <= mTermMinPvs)
563	\|\| (data.mProbability <= mTermMinProbability)
564	\|\| (data.mDepth >= mTermMaxDepth)
565	);
566
567	#if GTP_DEBUG
568	if (localTerminationCriteriaMet)
569	{
570	Debug << "local termination criteria met:" << endl;
571	Debug << "rays: " << (int)data.mRays->size() << " " << mTermMinRays << endl;
572	Debug << "pvs: " << data.mPvs << " " << mTermMinPvs << endl;
573	Debug << "p: " << data.mProbability << " " << mTermMinProbability << endl;
574	Debug << "avg contri: " << data.GetAvgRayContribution() << " " << mTermMaxRayContribution << endl;
575	Debug << "depth " << data.mDepth << " " << mTermMaxDepth << endl;
576	}
577	#endif
578	return localTerminationCriteriaMet;
579	}
580
581
582	inline bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
583	{
584	// note: to track for global cost misses does not really
585	// make sense because termination on cost or memory is done
586	// in the hierarchy mananger
587	const bool terminationCriteriaMet = (0
588	// \|\| mOutOfMemory
589	\|\| (mVspStats.Leaves() >= mMaxViewCells)
590	// \|\| (mVspStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
591	);
592
593	#if GTP_DEBUG
594	if (terminationCriteriaMet)
595	{
596	Debug << "vsp global termination criteria met:" << endl;
597	Debug << "cost misses: " << mVspStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
598	Debug << "leaves: " << mVspStats.Leaves() << " " << mMaxViewCells << endl;
599	}
600	#endif
601
602	return terminationCriteriaMet;
603	}
604
605
606	void VspTree::CreateViewCell(VspTraversalData &tData,
607	const bool updatePvs,
608	const float renderCost,
609	const int pvs)
610	{
611	///////////////
612	//-- create new view cell
613
614	VspLeaf *leaf = tData.mNode;
615
616	VspViewCell *viewCell = new VspViewCell();
617	leaf->SetViewCell(viewCell);
618
619	int conSamp = 0;
620	float sampCon = 0.0f;
621
622	if (updatePvs)
623	{
624	// store pvs of view cell
625	AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
626
627	// update scalar pvs size value
628	ObjectPvs &pvs = viewCell->GetPvs();
629	mViewCellsManager->UpdateScalarPvsSize(viewCell,
630	pvs.EvalPvsCost(),
631	pvs.GetSize());
632
633	mVspStats.contributingSamples += conSamp;
634	mVspStats.sampleContributions += (int)sampCon;
635	}
636	else
637	{
638	viewCell->SetTrianglesInPvs(renderCost);
639	viewCell->SetEntriesInPvs(pvs);
640
641	//cout << "create view cell with tri=" << (int)renderCost << " pvs=" << pvs << endl;
642	}
643
644	if (mStoreRays)
645	{
646	///////////
647	//-- store sampling rays
648
649	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
650
651	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
652	{
653	VssRay ray = new VssRay((*rit).mRay);
654	ray->Ref();
655
656	// note: should rather store rays with view cell
657	leaf->mVssRays.push_back(ray);
658	}
659	}
660
661	// set view cell values
662	viewCell->mLeaves.push_back(leaf);
663
664	viewCell->SetVolume(tData.mProbability);
665	leaf->mProbability = tData.mProbability;
666	}
667
668
669	void VspTree::EvalSubdivisionStats(const SubdivisionCandidate &sc)
670	{
671	const float costDecr = sc.GetRenderCostDecrease();
672
673	AddSubdivisionStats(mVspStats.Leaves(),
674	costDecr,
675	mTotalCost,
676	(float)mTotalPvsSize / (float)mVspStats.Leaves());
677	}
678
679
680	VspNode *VspTree::Subdivide(SplitQueue &tQueue,
681	SubdivisionCandidate *splitCandidate,
682	const bool globalCriteriaMet)
683	{
684	mSubdivTimer.Entry();
685
686	// todo remove dynamic cast
687	VspSubdivisionCandidate *sc =
688	static_cast<VspSubdivisionCandidate *>(splitCandidate);
689
690	VspTraversalData &tData = sc->mParentData;
691	VspNode *newNode = tData.mNode;
692
693	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
694	{
695	///////////
696	//-- continue subdivision
697
698	VspTraversalData tFrontData;
699	VspTraversalData tBackData;
700
701	// create new interior node and two leaf node
702	const int maxCostMisses = sc->GetMaxCostMisses();
703
704	newNode = SubdivideNode(*sc, tFrontData, tBackData);
705
706	// how often was max cost ratio missed in this branch?
707	tFrontData.mMaxCostMisses = maxCostMisses;
708	tBackData.mMaxCostMisses = maxCostMisses;
709
710	mTotalCost -= sc->GetRenderCostDecrease();
711	//mTotalPvsSize += (int)(tFrontData.mPvs + tBackData.mPvs - tData.mPvs);
712	mPvsEntries += sc->GetPvsEntriesIncr();
713
714	// subdivision statistics
715	if (1) EvalSubdivisionStats(*sc);
716
717	/////////////
718	//-- evaluate new split candidates for global greedy cost heuristics
719
720	VspSubdivisionCandidate *frontCandidate = new VspSubdivisionCandidate(tFrontData);
721	VspSubdivisionCandidate *backCandidate = new VspSubdivisionCandidate(tBackData);
722
723	EvalSubdivisionCandidate(*frontCandidate);
724	EvalSubdivisionCandidate(*backCandidate);
725
726	// cross reference
727	tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
728	tBackData.mNode->SetSubdivisionCandidate(backCandidate);
729
730	tQueue.Push(frontCandidate);
731	tQueue.Push(backCandidate);
732
733	// note: leaf is not destroyed because it is needed to collect
734	// dirty candidates in hierarchy manager
735	}
736
737	if (newNode->IsLeaf()) // subdivision terminated
738	{
739	VspLeaf leaf = static_cast<VspLeaf >(newNode);
740
741	if (0 && mStoreRays)
742	{
743	//////////
744	//-- store rays piercing this view cell
745
746	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
747	for (it = tData.mRays->begin(); it != it_end; ++ it)
748	{
749	(*it).mRay->Ref();
750	leaf->mVssRays.push_back((*it).mRay);
751	}
752	}
753
754	// finally evaluate statistics for this leaf
755	EvaluateLeafStats(tData);
756	// detach subdivision candidate: this leaf is no candidate for
757	// splitting anymore
758	tData.mNode->SetSubdivisionCandidate(NULL);
759	// detach node so it won't get deleted
760	tData.mNode = NULL;
761	}
762
763	mSubdivTimer.Exit();
764
765	return newNode;
766	}
767
768
769	void VspTree::EvalSubdivisionCandidate(VspSubdivisionCandidate &splitCandidate,
770	bool computeSplitPlane)
771	{
772	mPlaneTimer.Entry();
773
774	if (computeSplitPlane)
775	{
776	float frontProb;
777	float backProb;
778
779	// compute locally best split plane
780	const float ratio = SelectSplitPlane(splitCandidate.mParentData,
781	splitCandidate.mSplitPlane,
782	frontProb,
783	backProb);
784
785	const bool maxCostRatioViolated = mTermMaxCostRatio < ratio;
786
787	const int maxCostMisses = splitCandidate.mParentData.mMaxCostMisses;
788	// max cost threshold violated?
789	splitCandidate.SetMaxCostMisses(maxCostRatioViolated ?
790	maxCostMisses + 1: maxCostMisses);
791	}
792
793	mPlaneTimer.Exit();
794
795	mEvalTimer.Entry();
796
797	VspLeaf leaf = static_cast<VspLeaf >(splitCandidate.mParentData.mNode);
798
799	//////////////
800	//-- compute global decrease in render cost
801
802	const AxisAlignedPlane candidatePlane = splitCandidate.mSplitPlane;
803
804	RayInfoContainer::const_iterator rit, rit_end = splitCandidate.mParentData.mRays->end();
805
806	SplitData sData;
807
808	Intersectable::NewMail(3);
809	KdLeaf::NewMail(3);
810
811	for (rit = splitCandidate.mParentData.mRays->begin(); rit != rit_end; ++ rit)
812	{
813	RayInfo rayInf = *rit;
814
815	float t;
816
817	// classify ray
818	const int cf = rayInf.ComputeRayIntersection(candidatePlane.mAxis,
819	candidatePlane.mPosition,
820	t);
821
822	VssRay *ray = rayInf.mRay;
823
824	#if HACK_PERFORMANCE
825	Intersectable obj = (ray).mTerminationObject;
826
827	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
828
829	// evaluate contribution of ray endpoint to front
830	// and back pvs with respect to the classification
831	UpdateContributionsToPvs(leaf, cf, sData);
832
833	#if COUNT_ORIGIN_OBJECTS
834
835	obj = (*ray).mOriginObject;
836
837	if (obj)
838	{
839	leaf = mBvHierarchy->GetLeaf(obj);
840
841	UpdateContributionsToPvs(leaf, cf, sData);
842	}
843	#endif
844
845	#else
846	cerr << "TODO classify" << endl;
847	#endif
848	}
849
850	sData.mTotalRenderCost = mViewCellsManager->ComputeRenderCost(sData.mTotalTriangles, sData.mTotalObjects);
851	sData.mBackRenderCost = mViewCellsManager->ComputeRenderCost(sData.mBackTriangles, sData.mBackObjects);
852	sData.mFrontRenderCost = mViewCellsManager->ComputeRenderCost(sData.mFrontTriangles, sData.mFrontObjects);
853
854
855	/////////////
856	// avg ray contri
857
858	const float avgRayContri = (float)sData.mTotalObjects /
859	((float)splitCandidate.mParentData.mRays->size() + Limits::Small);
860
861	const float avgRaysPerObject = (float)splitCandidate.mParentData.mRays->size() /
862	((float)sData.mTotalObjects + Limits::Small);
863
864	//cout << "avg rays per obj: " << avgRaysPerObject << endl;
865
866	splitCandidate.SetAvgRayContribution(avgRayContri);
867	splitCandidate.SetAvgRaysPerObject(avgRaysPerObject);
868
869	// todo: compute old render cost in the function
870	// using michi's render cost evaluation
871	float oldRenderCost;
872	const float renderCostDecr = EvalRenderCostDecrease(splitCandidate, oldRenderCost, sData);
873	splitCandidate.SetRenderCostDecrease(renderCostDecr);
874
875	// the increase in pvs entries num induced by this split
876	const int pvsEntriesIncr = EvalPvsEntriesIncr(splitCandidate, sData);
877	splitCandidate.SetPvsEntriesIncr(pvsEntriesIncr);
878
879	splitCandidate.mFrontTriangles = (float)sData.mFrontTriangles;
880	splitCandidate.mBackTriangles = (float)sData.mBackTriangles;
881
882	// take render cost of node into account
883	// otherwise danger of being stuck in a local minimum!
884	float priority = mRenderCostDecreaseWeight * renderCostDecr + (1.0f - mRenderCostDecreaseWeight) * oldRenderCost;
885
886	if (mHierarchyManager->mConsiderMemory)
887	{
888	priority /= ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst);
889	}
890
891	splitCandidate.SetPriority(priority);
892
893	//cout << "vsp render cost decrease=" << renderCostDecr << endl;
894	mEvalTimer.Exit();
895	}
896
897
898	int VspTree::EvalPvsEntriesIncr(VspSubdivisionCandidate &splitCandidate,
899	const SplitData &sData) const
900	{
901	const float oldPvsRatio = (splitCandidate.mParentData.mPvs > 0) ?
902	sData.mTotalObjects / splitCandidate.mParentData.mPvs : 1;
903	const float correctedOldPvs = splitCandidate.mParentData.mCorrectedPvs * oldPvsRatio;
904
905	splitCandidate.mCorrectedFrontPvs =
906	mHierarchyManager->EvalCorrectedPvs((float)sData.mFrontObjects,
907	(float)correctedOldPvs,
908	splitCandidate.GetAvgRaysPerObject());
909	splitCandidate.mCorrectedBackPvs =
910	mHierarchyManager->EvalCorrectedPvs((float)sData.mBackObjects,
911	(float)correctedOldPvs,
912	splitCandidate.GetAvgRaysPerObject());
913
914	splitCandidate.mFrontPvs = (float)sData.mFrontObjects;
915	splitCandidate.mBackPvs = (float)sData.mBackObjects;
916
917	return (int)(splitCandidate.mCorrectedFrontPvs + splitCandidate.mCorrectedBackPvs - correctedOldPvs);
918	}
919
920
921	VspInterior *VspTree::SubdivideNode(const VspSubdivisionCandidate &sc,
922	VspTraversalData &frontData,
923	VspTraversalData &backData)
924	{
925	mNodeTimer.Entry();
926
927	VspLeaf leaf = static_cast<VspLeaf >(sc.mParentData.mNode);
928
929	const VspTraversalData &tData = sc.mParentData;
930	const AxisAlignedPlane &splitPlane = sc.mSplitPlane;
931
932	///////////////
933	//-- new traversal values
934
935	frontData.mDepth = tData.mDepth + 1;
936	backData.mDepth = tData.mDepth + 1;
937
938	frontData.mRays = new RayInfoContainer();
939	backData.mRays = new RayInfoContainer();
940
941	//-- subdivide rays
942	SplitRays(splitPlane, tData.mRays, frontData.mRays, *backData.mRays);
943
944	//-- compute pvs
945	frontData.mPvs = sc.mFrontPvs;
946	backData.mPvs = sc.mBackPvs;
947
948	//-- compute pvs correction for coping with undersampling
949	frontData.mCorrectedPvs = sc.mCorrectedFrontPvs;
950	backData.mCorrectedPvs = sc.mCorrectedBackPvs;
951
952	//-- split front and back node geometry and compute area
953	tData.mBoundingBox.Split(splitPlane.mAxis,
954	splitPlane.mPosition,
955	frontData.mBoundingBox,
956	backData.mBoundingBox);
957
958	frontData.mProbability = frontData.mBoundingBox.GetVolume();
959	backData.mProbability = tData.mProbability - frontData.mProbability;
960
961	//-- compute render cost
962	frontData.mRenderCost = sc.mFrontRenderCost;
963	backData.mRenderCost = sc.mBackRenderCost;
964
965	frontData.mCorrectedRenderCost = sc.mCorrectedFrontRenderCost;
966	backData.mCorrectedRenderCost = sc.mCorrectedBackRenderCost;
967
968	////////
969	//-- update some stats
970
971	if (tData.mDepth > mVspStats.maxDepth)
972	{
973	mVspStats.maxDepth = tData.mDepth;
974	}
975
976	// two more leaves per split
977	mVspStats.nodes += 2;
978	// and a new split
979	++ mVspStats.splits[splitPlane.mAxis];
980
981
982	////////////////
983	//-- create front and back and subdivide further
984
985	VspInterior *interior = new VspInterior(splitPlane);
986	VspInterior *parent = leaf->GetParent();
987
988	// replace a link from node's parent
989	if (parent)
990	{
991	parent->ReplaceChildLink(leaf, interior);
992	interior->SetParent(parent);
993	}
994	else // new root
995	{
996	mRoot = interior;
997	}
998
999	VspLeaf *frontLeaf = new VspLeaf(interior);
1000	VspLeaf *backLeaf = new VspLeaf(interior);
1001
1002	// and setup child links
1003	interior->SetupChildLinks(frontLeaf, backLeaf);
1004
1005	// add bounding box
1006	interior->SetBoundingBox(tData.mBoundingBox);
1007
1008	// set front and back leaf
1009	frontData.mNode = frontLeaf;
1010	backData.mNode = backLeaf;
1011
1012	// create front and back view cell for the new leaves
1013	CreateViewCell(frontData, false, sc.mFrontTriangles, (int)sc.mFrontPvs);
1014	CreateViewCell(backData, false, sc.mBackTriangles, (int)sc.mBackPvs);
1015
1016	// set the time stamp so the order of traversal can be reconstructed
1017	interior->mTimeStamp = mHierarchyManager->mTimeStamp ++;
1018
1019	mNodeTimer.Exit();
1020
1021	return interior;
1022	}
1023
1024
1025	void VspTree::AddSamplesToPvs(VspLeaf *leaf,
1026	const RayInfoContainer &rays,
1027	float &sampleContributions,
1028	int &contributingSamples)
1029	{
1030	sampleContributions = 0;
1031	contributingSamples = 0;
1032
1033	RayInfoContainer::const_iterator it, it_end = rays.end();
1034
1035	ViewCellLeaf *vc = leaf->GetViewCell();
1036
1037	// add contributions from samples to the pvs
1038	for (it = rays.begin(); it != it_end; ++ it)
1039	{
1040	float sc = 0.0f;
1041	VssRay ray = (it).mRay;
1042
1043	bool madeContrib = false;
1044	float contribution = 1;
1045
1046	Intersectable *entry =
1047	mHierarchyManager->GetIntersectable(ray->mTerminationObject, true);
1048
1049	if (entry)
1050	{
1051	madeContrib =
1052	vc->GetPvs().AddSample(entry, ray->mPdf);
1053
1054	sc += contribution;
1055	}
1056	#if COUNT_ORIGIN_OBJECTS
1057	entry = mHierarchyManager->GetIntersectable(ray->mOriginObject, true);
1058
1059	if (entry)
1060	{
1061	madeContrib =
1062	vc->GetPvs().AddSample(entry, ray->mPdf);
1063
1064	sc += contribution;
1065	}
1066	#endif
1067	if (madeContrib)
1068	{
1069	++ contributingSamples;
1070	}
1071	}
1072	}
1073
1074
1075	void VspTree::SortSubdivisionCandidates(const RayInfoContainer &rays,
1076	const int axis,
1077	float minBand,
1078	float maxBand)
1079	{
1080	mSortTimer.Entry();
1081
1082	mLocalSubdivisionCandidates->clear();
1083
1084	const int requestedSize = 2 * (int)(rays.size());
1085
1086	// creates a sorted split candidates array
1087	if (mLocalSubdivisionCandidates->capacity() > 500000 &&
1088	requestedSize < (int)(mLocalSubdivisionCandidates->capacity() / 10) )
1089	{
1090	delete mLocalSubdivisionCandidates;
1091	mLocalSubdivisionCandidates = new vector<SortableEntry>;
1092	}
1093
1094	mLocalSubdivisionCandidates->reserve(requestedSize);
1095
1096	float pos;
1097	RayInfoContainer::const_iterator rit, rit_end = rays.end();
1098
1099	const bool delayMinEvent = false;
1100
1101	////////////
1102	//-- insert all queries
1103	for (rit = rays.begin(); rit != rit_end; ++ rit)
1104	{
1105	const bool positive = (*rit).mRay->HasPosDir(axis);
1106
1107	// origin point
1108	pos = (*rit).ExtrapOrigin(axis);
1109	const int oType = positive ? SortableEntry::ERayMin : SortableEntry::ERayMax;
1110
1111	if (delayMinEvent && oType == SortableEntry::ERayMin)
1112	pos += mEpsilon; // could be useful feature for walls
1113
1114	mLocalSubdivisionCandidates->push_back(SortableEntry(oType, pos, (*rit).mRay));
1115
1116	// termination point
1117	pos = (*rit).ExtrapTermination(axis);
1118	const int tType = positive ? SortableEntry::ERayMax : SortableEntry::ERayMin;
1119
1120	if (delayMinEvent && tType == SortableEntry::ERayMin)
1121	pos += mEpsilon; // could be useful feature for walls
1122
1123	mLocalSubdivisionCandidates->push_back(SortableEntry(tType, pos, (*rit).mRay));
1124	}
1125
1126	if (1)
1127	stable_sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
1128	else
1129	sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
1130
1131	mSortTimer.Exit();
1132	}
1133
1134
1135	float VspTree::PrepareHeuristics(KdLeaf *leaf)
1136	{
1137	float pvsSize = 0;
1138
1139	if (!leaf->Mailed())
1140	{
1141	leaf->Mail();
1142	leaf->mCounter = 1;
1143	// add objects without the objects which are in several kd leaves
1144	pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1145	}
1146	else
1147	{
1148	++ leaf->mCounter;
1149	}
1150
1151	//-- the objects belonging to several leaves must be handled seperately
1152	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1153
1154	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1155	{
1156	Intersectable object = oit;
1157
1158	if (!object->Mailed())
1159	{
1160	object->Mail();
1161	object->mCounter = 1;
1162
1163	++ pvsSize;
1164	}
1165	else
1166	{
1167	++ object->mCounter;
1168	}
1169	}
1170
1171	return pvsSize;
1172	}
1173
1174
1175	float VspTree::PrepareHeuristics(const RayInfoContainer &rays)
1176	{
1177	Intersectable::NewMail();
1178	KdNode::NewMail();
1179
1180	float pvsSize = 0;
1181
1182	RayInfoContainer::const_iterator ri, ri_end = rays.end();
1183
1184	// set all kd nodes / objects as belonging to the front pvs
1185	for (ri = rays.begin(); ri != ri_end; ++ ri)
1186	{
1187	VssRay ray = (ri).mRay;
1188
1189	pvsSize += PrepareHeuristics(*ray, true);
1190	#if COUNT_ORIGIN_OBJECTS
1191	pvsSize += PrepareHeuristics(*ray, false);
1192	#endif
1193	}
1194
1195	return pvsSize;
1196	}
1197
1198
1199	float VspTree::EvalMaxEventContribution(KdLeaf *leaf) const
1200	{
1201	float pvs = 0;
1202
1203	// leaf falls out of right pvs
1204	if (-- leaf->mCounter == 0)
1205	{
1206	pvs -= ((float)leaf->mObjects.size() - (float)leaf->mMultipleObjects.size());
1207	}
1208
1209	//////
1210	//-- separately handle objects which are in several kd leaves
1211
1212	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1213
1214	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1215	{
1216	Intersectable object = oit;
1217
1218	if (-- object->mCounter == 0)
1219	{
1220	++ pvs;
1221	}
1222	}
1223
1224	return pvs;
1225	}
1226
1227
1228	float VspTree::EvalMinEventContribution(KdLeaf *leaf) const
1229	{
1230	if (leaf->Mailed())
1231	return 0;
1232
1233	leaf->Mail();
1234
1235	// add objects without those which are part of several kd leaves
1236	float pvs = ((float)leaf->mObjects.size() - (float)leaf->mMultipleObjects.size());
1237
1238	// separately handle objects which are part of several kd leaves
1239	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1240
1241	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1242	{
1243	Intersectable object = oit;
1244
1245	// object not previously in pvs
1246	if (!object->Mailed())
1247	{
1248	object->Mail();
1249	++ pvs;
1250	}
1251	}
1252
1253	return pvs;
1254	}
1255
1256
1257	void VspTree::EvalHeuristics(const SortableEntry &ci,
1258	float &pvsLeft,
1259	float &pvsRight) const
1260	{
1261	VssRay *ray = ci.ray;
1262
1263	// eval changes in pvs causes by min event
1264	if (ci.type == SortableEntry::ERayMin)
1265	{
1266	pvsLeft += EvalMinEventContribution(*ray, true);
1267	#if COUNT_ORIGIN_OBJECTS
1268	pvsLeft += EvalMinEventContribution(*ray, false);
1269	#endif
1270	}
1271	else // eval changes in pvs causes by max event
1272	{
1273	pvsRight -= EvalMaxEventContribution(*ray, true);
1274	#if COUNT_ORIGIN_OBJECTS
1275	pvsRight -= EvalMaxEventContribution(*ray, false);
1276	#endif
1277	}
1278	}
1279
1280
1281	float VspTree::EvalLocalCostHeuristics(const VspTraversalData &tData,
1282	const AxisAlignedBox3 &box,
1283	const int axis,
1284	float &position,
1285	const RayInfoContainer &usedRays)
1286	{
1287	const float minBox = box.Min(axis);
1288	const float maxBox = box.Max(axis);
1289
1290	const float sizeBox = maxBox - minBox;
1291
1292	const float minBand = minBox + mMinBand * sizeBox;
1293	const float maxBand = minBox + mMaxBand * sizeBox;
1294
1295	// sort by the current dimension
1296	SortSubdivisionCandidates(usedRays, axis, minBand, maxBand);
1297
1298	// prepare the sweep
1299	// note: returns pvs size => no need t give pvs size as function parameter
1300	const float pvsCost = PrepareHeuristics(usedRays);
1301
1302	// go through the lists, count the number of objects left and right
1303	// and evaluate the following cost funcion:
1304	// C = ct_div_ci + (qlrl + qrrr)/queries
1305
1306	float pvsl = 0;
1307	float pvsr = pvsCost;
1308
1309	float pvsBack = pvsl;
1310	float pvsFront = pvsr;
1311
1312	float sum = pvsCost * sizeBox;
1313	float minSum = 1e20f;
1314
1315	// if no good split can be found, take mid split
1316	position = minBox + 0.5f * sizeBox;
1317
1318	// the relative cost ratio
1319	float ratio = 99999999.0f;
1320	bool splitPlaneFound = false;
1321
1322	Intersectable::NewMail();
1323	KdLeaf::NewMail();
1324
1325	const float volRatio =
1326	tData.mBoundingBox.GetVolume() / (sizeBox * mBoundingBox.GetVolume());
1327
1328	////////
1329	//-- iterate through visibility events
1330
1331	vector<SortableEntry>::const_iterator ci,
1332	ci_end = mLocalSubdivisionCandidates->end();
1333
1334	#ifdef GTP_DEBUG
1335	const int leaves = mVspStats.Leaves();
1336	const bool printStats = ((axis == 0) && (leaves > 0) && (leaves < 90));
1337
1338	ofstream sumStats;
1339	ofstream pvslStats;
1340	ofstream pvsrStats;
1341
1342	if (printStats)
1343	{
1344	char str[64];
1345
1346	sprintf(str, "tmp/vsp_heur_sum-%04d.log", leaves);
1347	sumStats.open(str);
1348	sprintf(str, "tmp/vsp_heur_pvsl-%04d.log", leaves);
1349	pvslStats.open(str);
1350	sprintf(str, "tmp/vsp_heur_pvsr-%04d.log", leaves);
1351	pvsrStats.open(str);
1352	}
1353
1354	#endif
1355
1356
1357	for (ci = mLocalSubdivisionCandidates->begin(); ci != ci_end; ++ ci)
1358	{
1359	// compute changes to front and back pvs
1360	EvalHeuristics(*ci, pvsl, pvsr);
1361
1362	// Note: sufficient to compare size of bounding boxes of front and back side?
1363	if (((ci).value >= minBand) && ((ci).value <= maxBand))
1364	{
1365	float currentPos;
1366
1367	// HACK: current positition is BETWEEN visibility events
1368	if (0 && ((ci + 1) != ci_end))
1369	currentPos = ((ci).value + ((ci + 1)).value) * 0.5f;
1370	else
1371	currentPos = (*ci).value;
1372
1373	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
1374
1375	#ifdef GTP_DEBUG
1376	if (printStats)
1377	{
1378	sumStats
1379	<< "#Position\n" << currentPos << endl
1380	<< "#Sum\n" << sum * volRatio << endl
1381	<< "#Pvs\n" << pvsl + pvsr << endl;
1382
1383	pvslStats
1384	<< "#Position\n" << currentPos << endl
1385	<< "#Pvsl\n" << pvsl << endl;
1386
1387	pvsrStats
1388	<< "#Position\n" << currentPos << endl
1389	<< "#Pvsr\n" << pvsr << endl;
1390	}
1391	#endif
1392
1393	if (sum < minSum)
1394	{
1395	splitPlaneFound = true;
1396
1397	minSum = sum;
1398	position = currentPos;
1399
1400	pvsBack = pvsl;
1401	pvsFront = pvsr;
1402	}
1403	}
1404	}
1405
1406	/////////
1407	//-- compute cost
1408
1409	const float pOverall = sizeBox;
1410	const float pBack = position - minBox;
1411	const float pFront = maxBox - position;
1412
1413	const float penaltyOld = pvsCost;
1414	const float penaltyFront = pvsFront;
1415	const float penaltyBack = pvsBack;
1416
1417	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
1418	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1419
1420	#if VISUALIZE_SPLIT
1421
1422	const int leaves = mVspStats.Leaves();
1423	const bool showViz = (leaves >= 3000) && (leaves % 497 == 0);
1424
1425	if (showViz)
1426	{
1427	//cout << "========================== exporting split ===================" << endl;
1428
1429	Exporter *exporter;
1430
1431	char str[64]; sprintf(str, "vc-%04d_%d.wrl", leaves, axis);
1432
1433	exporter = Exporter::GetExporter(str);
1434
1435	Material m;
1436	m.mDiffuseColor.r = 1.0f;
1437	m.mDiffuseColor.g = 0.0f;
1438	m.mDiffuseColor.b = 0.0f;
1439
1440	exporter->SetForcedMaterial(m);
1441	exporter->SetWireframe();
1442
1443	exporter->ExportBox(tData.mBoundingBox);
1444
1445	exporter->ResetForcedMaterial();
1446
1447	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
1448
1449	exporter->SetFilled();
1450
1451	m.mDiffuseColor.r = 0.0f;
1452	m.mDiffuseColor.g = 1.0f;
1453	m.mDiffuseColor.b = 0.0f;
1454
1455	exporter->SetForcedMaterial(m);
1456
1457	// create unique ids for pvs heuristics
1458	Intersectable::NewMail(3);
1459
1460	float a = 0, b = 0, c = 0;
1461
1462	// this is the main ray classification loop!
1463	for(rit = tData.mRays->begin(); rit != rit_end; ++ rit)
1464	{
1465	VssRay ray = (rit).mRay;
1466
1467	// determine the side of this ray with respect to the plane
1468	float t;
1469	const int side = (*rit).ComputeRayIntersection(axis, position, t);
1470
1471	UpdateContributionsToPvs(*ray, true, side, a, b, c);
1472	UpdateContributionsToPvs(*ray, false, side, a, b, c);
1473	}
1474
1475
1476	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
1477	{
1478	RayInfo rayInf = *rit;
1479
1480	// export objects
1481	VssRay *ray = rayInf.mRay;
1482	BvhLeaf *leaf = mBvHierarchy->GetLeaf(ray->mTerminationObject);
1483
1484	//left and right
1485	if (leaf->Mailed(2))
1486	{
1487	m.mDiffuseColor.r = 0.0f;
1488	m.mDiffuseColor.g = 1.0f;
1489	m.mDiffuseColor.b = 1.0f;
1490	}
1491	else if (leaf->Mailed(1)) // only right
1492	{
1493	m.mDiffuseColor.r = 0.0f;
1494	m.mDiffuseColor.g = 1.0f;
1495	m.mDiffuseColor.b = 0.0f;
1496	}
1497	else // left
1498	{
1499	m.mDiffuseColor.r = 0.0f;
1500	m.mDiffuseColor.g = 0.0f;
1501	m.mDiffuseColor.b = 1.0f;
1502	}
1503
1504	exporter->SetForcedMaterial(m);
1505	exporter->ExportIntersectable(leaf);
1506
1507	}
1508
1509	m.mDiffuseColor.r = 1.0f;
1510	m.mDiffuseColor.g = 0.0f;
1511	m.mDiffuseColor.b = 1.0f;
1512
1513	exporter->SetForcedMaterial(m);
1514	AxisAlignedBox3 vizPlaneBox;
1515	vizPlaneBox = tData.mBoundingBox;
1516
1517	vizPlaneBox.SetMin(axis, position - 0.01);
1518	vizPlaneBox.SetMax(axis, position + 0.01);
1519
1520	exporter->ExportBox(vizPlaneBox);
1521
1522	delete exporter;
1523	}
1524
1525	#endif
1526
1527	if (splitPlaneFound)
1528	{
1529	ratio = newRenderCost / oldRenderCost;
1530	}
1531
1532
1533	#ifdef GTP_DEBUG
1534	Debug << "\n((((( eval local vsp cost )))))" << endl
1535	<< "back pvs: " << penaltyBack << " front pvs: " << penaltyFront << " total pvs: " << penaltyOld << endl
1536	<< "back p: " << pBack * volRatio << " front p " << pFront * volRatio << " p: " << pOverall * volRatio << endl
1537	<< "old rc: " << oldRenderCost * volRatio << " new rc: " << newRenderCost * volRatio << endl
1538	<< "render cost decrease: " << oldRenderCost * volRatio - newRenderCost * volRatio << endl;
1539	#endif
1540
1541	return ratio;
1542	}
1543
1544
1545	float VspTree::SelectSplitPlane(const VspTraversalData &tData,
1546	AxisAlignedPlane &plane,
1547	float &pFront,
1548	float &pBack)
1549	{
1550	mSplitTimer.Entry();
1551
1552	float nPosition[3];
1553	float nCostRatio[3];
1554	float nProbFront[3];
1555	float nProbBack[3];
1556
1557	// create bounding box of node geometry
1558	AxisAlignedBox3 box = tData.mBoundingBox;
1559
1560	int sAxis = 0;
1561	int bestAxis = -1;
1562
1563	// do we use some kind of specialised "fixed" axis?
1564	const bool useSpecialAxis =
1565	mOnlyDrivingAxis \|\| mCirculatingAxis;
1566
1567	// get subset of rays
1568	RayInfoContainer randomRays;
1569	randomRays.reserve(min(mMaxTests, (int)tData.mRays->size()));
1570
1571	RayInfoContainer *usedRays;
1572
1573	if (mMaxTests < (int)tData.mRays->size())
1574	{
1575	GetRayInfoSets(*tData.mRays, mMaxTests, randomRays);
1576	usedRays = &randomRays;
1577	}
1578	else
1579	{
1580	usedRays = tData.mRays;
1581	}
1582
1583	if (mCirculatingAxis)
1584	{
1585	int parentAxis = 0;
1586	VspNode *parent = tData.mNode->GetParent();
1587
1588	if (parent)
1589	{
1590	parentAxis = static_cast<VspInterior *>(parent)->GetAxis();
1591	}
1592
1593	sAxis = (parentAxis + 1) % 3;
1594	}
1595	else if (mOnlyDrivingAxis)
1596	{
1597	sAxis = box.Size().DrivingAxis();
1598	}
1599
1600	for (int axis = 0; axis < 3; ++ axis)
1601	{
1602	if (!useSpecialAxis \|\| (axis == sAxis))
1603	{
1604	if (mUseCostHeuristics)
1605	{
1606	//-- place split plane using heuristics
1607	nCostRatio[axis] =
1608	EvalLocalCostHeuristics(tData,
1609	box,
1610	axis,
1611	nPosition[axis],
1612	*usedRays);
1613	}
1614	else
1615	{
1616	//-- split plane position is spatial median
1617	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1618	nCostRatio[axis] = EvalLocalSplitCost(tData,
1619	box,
1620	axis,
1621	nPosition[axis],
1622	nProbFront[axis],
1623	nProbBack[axis]);
1624	}
1625
1626	if (bestAxis == -1)
1627	{
1628	bestAxis = axis;
1629	}
1630	else if (nCostRatio[axis] < nCostRatio[bestAxis])
1631	{
1632	bestAxis = axis;
1633	}
1634	}
1635	}
1636
1637	/////////////////////////
1638	//-- assign values of best split
1639
1640	plane.mAxis = bestAxis;
1641	// best split plane position
1642	plane.mPosition = nPosition[bestAxis];
1643
1644	pFront = nProbFront[bestAxis];
1645	pBack = nProbBack[bestAxis];
1646
1647	mSplitTimer.Exit();
1648
1649	return nCostRatio[bestAxis];
1650	}
1651
1652
1653	float VspTree::EvalRenderCostDecrease(VspSubdivisionCandidate &sc,
1654	float &normalizedOldRenderCost,
1655	const SplitData &sData) const
1656	{
1657	const float viewSpaceVol = mBoundingBox.GetVolume();
1658	const VspTraversalData &tData = sc.mParentData;
1659
1660	const AxisAlignedPlane &candidatePlane = sc.mSplitPlane;
1661	const float avgRaysPerObject = sc.GetAvgRaysPerObject();
1662
1663
1664	AxisAlignedBox3 frontBox;
1665	AxisAlignedBox3 backBox;
1666
1667	tData.mBoundingBox.Split(candidatePlane.mAxis,
1668	candidatePlane.mPosition,
1669	frontBox,
1670	backBox);
1671
1672	// probability that view point lies in back / front node
1673	float pOverall = tData.mProbability;
1674	float pFront = frontBox.GetVolume();
1675	float pBack = pOverall - pFront;
1676
1677
1678	///////////////////
1679	//-- evaluate render cost heuristics
1680
1681	// ratio of how render cost changed since last evaluation
1682	const float oldRenderCostRatio = (tData.mRenderCost > 0)? (sData.mTotalRenderCost / tData.mRenderCost) : 1;
1683	const float penaltyOld = tData.mCorrectedRenderCost * oldRenderCostRatio;
1684
1685	sc.mCorrectedFrontRenderCost = mHierarchyManager->EvalCorrectedPvs(sData.mFrontRenderCost, penaltyOld, avgRaysPerObject);
1686	sc.mCorrectedBackRenderCost = mHierarchyManager->EvalCorrectedPvs(sData.mBackRenderCost, penaltyOld, avgRaysPerObject);
1687
1688	sc.mFrontRenderCost = sData.mFrontRenderCost;
1689	sc.mBackRenderCost = sData.mBackRenderCost;
1690
1691	const float oldRenderCost = penaltyOld * pOverall;
1692	const float newRenderCost = sc.mCorrectedFrontRenderCost * pFront + sc.mCorrectedBackRenderCost * pBack;
1693
1694
1695	// the normalized old render cost is needed for the priority
1696	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
1697
1698	// the render cost decrase for this split
1699	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
1700
1701	#if GTP_DEBUG
1702	Debug << "old: " << normalizedOldRenderCost << " new: " << newRenderCost / viewSpaceVol
1703	<< " corr: " << tData.mCorrectedRenderCost << " ratio: " << oldRenderCostRatio << endl;
1704	#endif
1705
1706	return renderCostDecrease;
1707	}
1708
1709
1710	float VspTree::EvalLocalSplitCost(const VspTraversalData &tData,
1711	const AxisAlignedBox3 &box,
1712	const int axis,
1713	const float &position,
1714	float &pFront,
1715	float &pBack) const
1716	{
1717	float pvsTotal = 0;
1718	float pvsFront = 0;
1719	float pvsBack = 0;
1720
1721	// create unique ids for pvs heuristics
1722	Intersectable::NewMail(3);
1723	KdLeaf::NewMail(3);
1724
1725	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
1726
1727	// this is the main ray classification loop!
1728	for(rit = tData.mRays->begin(); rit != rit_end; ++ rit)
1729	{
1730	VssRay ray = (rit).mRay;
1731
1732	// determine the side of this ray with respect to the plane
1733	float t;
1734	const int side = (*rit).ComputeRayIntersection(axis, position, t);
1735
1736	UpdateContributionsToPvs(*ray, true, side, pvsFront, pvsBack, pvsTotal);
1737	UpdateContributionsToPvs(*ray, false, side, pvsFront, pvsBack, pvsTotal);
1738	}
1739
1740	//////////////
1741	//-- evaluate cost heuristics
1742
1743	float pOverall = tData.mProbability;
1744
1745	// we use spatial mid split => simplified computation
1746	pBack = pFront = pOverall * 0.5f;
1747
1748	const float newCost = pvsBack * pBack + pvsFront * pFront;
1749	const float oldCost = (float)pvsTotal * pOverall + Limits::Small;
1750
1751	#ifdef GTPGTP_DEBUG
1752	Debug << "axis: " << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1753	Debug << "p: " << pFront << " " << pBack << " " << pOverall << endl;
1754	#endif
1755
1756	return (mCtDivCi + newCost) / oldCost;
1757	}
1758
1759
1760	void VspTree::UpdateContributionsToPvs(Intersectable *obj,
1761	const int cf,
1762	float &frontPvs,
1763	float &backPvs,
1764	float &totalPvs) const
1765	{
1766	if (!obj) return;
1767
1768	// object in none of the pvss => new object
1769	if (!obj->Mailed() && !obj->Mailed(1) && !obj->Mailed(2))
1770	{
1771	totalPvs += 1.0f;
1772	}
1773
1774	// QUESTION matt: is it safe to assume that
1775	// the object belongs to no pvs in this case?
1776	//if (cf == Ray::COINCIDENT) return;
1777	if (cf >= 0) // front pvs
1778	{
1779	if (!obj->Mailed() && !obj->Mailed(2))
1780	{
1781	frontPvs += 1.0f;
1782
1783	// already in back pvs => in both pvss
1784	if (obj->Mailed(1))
1785	obj->Mail(2);
1786	else
1787	obj->Mail();
1788	}
1789	}
1790
1791	if (cf <= 0) // back pvs
1792	{
1793	if (!obj->Mailed(1) && !obj->Mailed(2))
1794	{
1795	backPvs += 1.0f;
1796
1797	// already in front pvs => in both pvss
1798	if (obj->Mailed())
1799	obj->Mail(2);
1800	else
1801	obj->Mail(1);
1802	}
1803	}
1804	}
1805
1806
1807	void VspTree::UpdateContributionsToPvs(BvhLeaf *leaf,
1808	const int cf,
1809	float &frontPvs,
1810	float &backPvs,
1811	float &totalPvs,
1812	const bool countEntries) const
1813	{
1814	if (!leaf) return;
1815
1816	const float renderCost = countEntries ? 1 :
1817	(float)leaf->mObjects.size();
1818
1819	// leaf in no pvs => new
1820	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1821	{
1822	totalPvs += renderCost;
1823	}
1824
1825	if (cf >= 0) // front pvs
1826	{
1827	if (!leaf->Mailed() && !leaf->Mailed(2))
1828	{
1829	frontPvs += renderCost;
1830
1831	// already in back pvs => in both pvss
1832	if (leaf->Mailed(1))
1833	leaf->Mail(2);
1834	else
1835	leaf->Mail();
1836	}
1837	}
1838
1839	if (cf <= 0) // back pvs
1840	{
1841	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1842	{
1843	backPvs += renderCost;
1844
1845	// already in front pvs => in both pvss
1846	if (leaf->Mailed())
1847	leaf->Mail(2);
1848	else
1849	leaf->Mail(1);
1850	}
1851	}
1852	}
1853
1854
1855	void VspTree::UpdateContributionsToPvs(BvhLeaf *leaf,
1856	const int cf,
1857	SplitData &sData) const
1858	{
1859	const int triSize = (int)leaf->mObjects.size();
1860
1861	// object in no pvs => count as new
1862	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1863	{
1864	sData.mTotalTriangles += (int)triSize;
1865	++ sData.mTotalObjects;
1866	}
1867
1868	if (cf >= 0) // front pvs
1869	{
1870	if (!leaf->Mailed() && !leaf->Mailed(2))
1871	{
1872	sData.mFrontTriangles += triSize;
1873	++ sData.mFrontObjects;
1874
1875	// already in back pvs => in both pvss
1876	if (leaf->Mailed(1))
1877	leaf->Mail(2);
1878	else
1879	leaf->Mail();
1880	}
1881	}
1882
1883	if (cf <= 0) // back pvs
1884	{
1885	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1886	{
1887	sData.mBackTriangles += triSize;
1888	++ sData.mBackObjects;
1889
1890	// already in front pvs => in both pvss
1891	if (leaf->Mailed())
1892	leaf->Mail(2);
1893	else
1894	leaf->Mail(1);
1895	}
1896	}
1897	}
1898
1899
1900	void VspTree::UpdateContributionsToPvs(KdLeaf *leaf,
1901	const int cf,
1902	float &frontPvs,
1903	float &backPvs,
1904	float &totalPvs) const
1905	{
1906	if (!leaf) return;
1907
1908	// the objects which are referenced in this and only this leaf
1909	const int contri = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1910
1911	// newly found leaf
1912	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1913	{
1914	totalPvs += contri;
1915	}
1916
1917	// recursivly update contributions of yet unclassified objects
1918	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1919
1920	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1921	{
1922	UpdateContributionsToPvs(*oit, cf, frontPvs, backPvs, totalPvs);
1923	}
1924
1925	if (cf >= 0) // front pvs
1926	{
1927	if (!leaf->Mailed() && !leaf->Mailed(2))
1928	{
1929	frontPvs += contri;
1930
1931	// already in back pvs => in both pvss
1932	if (leaf->Mailed(1))
1933	leaf->Mail(2);
1934	else
1935	leaf->Mail();
1936	}
1937	}
1938
1939	if (cf <= 0) // back pvs
1940	{
1941	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1942	{
1943	backPvs += contri;
1944
1945	// already in front pvs => in both pvss
1946	if (leaf->Mailed())
1947	leaf->Mail(2);
1948	else
1949	leaf->Mail(1);
1950	}
1951	}
1952	}
1953
1954
1955	void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
1956	const bool onlyUnmailed,
1957	const int maxPvsSize) const
1958	{
1959	stack<VspNode *> nodeStack;
1960	nodeStack.push(mRoot);
1961
1962	while (!nodeStack.empty())
1963	{
1964	VspNode *node = nodeStack.top();
1965	nodeStack.pop();
1966
1967	if (node->IsLeaf())
1968	{
1969	// test if this leaf is in valid view space
1970	VspLeaf leaf = static_cast<VspLeaf >(node);
1971
1972	if (leaf->TreeValid() &&
1973	(!onlyUnmailed \|\| !leaf->Mailed()) &&
1974	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().EvalPvsCost() <= maxPvsSize)))
1975	{
1976	leaves.push_back(leaf);
1977	}
1978	}
1979	else
1980	{
1981	VspInterior interior = static_cast<VspInterior >(node);
1982
1983	nodeStack.push(interior->GetBack());
1984	nodeStack.push(interior->GetFront());
1985	}
1986	}
1987	}
1988
1989
1990	AxisAlignedBox3 VspTree::GetBoundingBox() const
1991	{
1992	return mBoundingBox;
1993	}
1994
1995
1996	VspNode *VspTree::GetRoot() const
1997	{
1998	return mRoot;
1999	}
2000
2001
2002	void VspTree::EvaluateLeafStats(const VspTraversalData &data)
2003	{
2004	// the node became a leaf -> evaluate stats for leafs
2005	VspLeaf leaf = static_cast<VspLeaf >(data.mNode);
2006
2007	if (data.mPvs > mVspStats.maxPvs)
2008	{
2009	mVspStats.maxPvs = (int)data.mPvs;
2010	}
2011
2012	mVspStats.pvs += (int)data.mPvs;
2013
2014	if (data.mDepth < mVspStats.minDepth)
2015	{
2016	mVspStats.minDepth = data.mDepth;
2017	}
2018
2019	if (data.mDepth >= mTermMaxDepth)
2020	{
2021	++ mVspStats.maxDepthNodes;
2022	}
2023
2024	// accumulate rays to compute rays / leaf
2025	mVspStats.rayRefs += (int)data.mRays->size();
2026
2027	if (data.mPvs < mTermMinPvs)
2028	++ mVspStats.minPvsNodes;
2029
2030	if ((int)data.mRays->size() < mTermMinRays)
2031	++ mVspStats.minRaysNodes;
2032
2033	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
2034	++ mVspStats.maxRayContribNodes;
2035
2036	if (data.mProbability <= mTermMinProbability)
2037	++ mVspStats.minProbabilityNodes;
2038
2039	// accumulate depth to compute average depth
2040	mVspStats.accumDepth += data.mDepth;
2041
2042	++ mCreatedViewCells;
2043
2044	#ifdef GTP_DEBUG
2045	Debug << "BSP stats: "
2046	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
2047	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
2048	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
2049	<< "#pvs: " << leaf->GetViewCell()->GetPvs().EvalPvsCost() << "), "
2050	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
2051	#endif
2052	}
2053
2054
2055	void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
2056	{
2057	ViewCell::NewMail();
2058	CollectViewCells(mRoot, onlyValid, viewCells, true);
2059	}
2060
2061
2062	void VspTree::CollectRays(VssRayContainer &rays)
2063	{
2064	vector<VspLeaf *> leaves;
2065	CollectLeaves(leaves);
2066
2067	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
2068
2069	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2070	{
2071	VspLeaf leaf = lit;
2072	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
2073
2074	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
2075	rays.push_back(*rit);
2076	}
2077	}
2078
2079
2080	void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
2081	{
2082	mViewCellsManager = vcm;
2083	}
2084
2085
2086	void VspTree::ValidateTree()
2087	{
2088	if (!mRoot)
2089	return;
2090
2091	mVspStats.invalidLeaves = 0;
2092	stack<VspNode *> nodeStack;
2093
2094	nodeStack.push(mRoot);
2095
2096	while (!nodeStack.empty())
2097	{
2098	VspNode *node = nodeStack.top();
2099	nodeStack.pop();
2100
2101	if (node->IsLeaf())
2102	{
2103	VspLeaf leaf = static_cast<VspLeaf >(node);
2104
2105	if (!leaf->GetViewCell()->GetValid())
2106	++ mVspStats.invalidLeaves;
2107
2108	// validity flags don't match => repair
2109	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
2110	{
2111	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
2112	PropagateUpValidity(leaf);
2113	}
2114	}
2115	else
2116	{
2117	VspInterior interior = static_cast<VspInterior >(node);
2118
2119	nodeStack.push(interior->GetFront());
2120	nodeStack.push(interior->GetBack());
2121	}
2122	}
2123
2124	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
2125	}
2126
2127
2128
2129	void VspTree::CollectViewCells(VspNode *root,
2130	bool onlyValid,
2131	ViewCellContainer &viewCells,
2132	bool onlyUnmailed) const
2133	{
2134	if (!root)
2135	return;
2136
2137	stack<VspNode *> nodeStack;
2138	nodeStack.push(root);
2139
2140	while (!nodeStack.empty())
2141	{
2142	VspNode *node = nodeStack.top();
2143	nodeStack.pop();
2144
2145	if (node->IsLeaf())
2146	{
2147	if (!onlyValid \|\| node->TreeValid())
2148	{
2149	ViewCellLeaf leafVc = static_cast<VspLeaf >(node)->GetViewCell();
2150
2151	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
2152
2153	if (!onlyUnmailed \|\| !viewCell->Mailed())
2154	{
2155	viewCell->Mail();
2156	viewCells.push_back(viewCell);
2157	}
2158	}
2159	}
2160	else
2161	{
2162	VspInterior interior = static_cast<VspInterior >(node);
2163
2164	nodeStack.push(interior->GetFront());
2165	nodeStack.push(interior->GetBack());
2166	}
2167	}
2168	}
2169
2170
2171	int VspTree::FindNeighbors(VspLeaf *n,
2172	vector<VspLeaf *> &neighbors,
2173	const bool onlyUnmailed) const
2174	{
2175	stack<VspNode *> nodeStack;
2176	nodeStack.push(mRoot);
2177
2178	const AxisAlignedBox3 box = GetBoundingBox(n);
2179
2180	while (!nodeStack.empty())
2181	{
2182	VspNode *node = nodeStack.top();
2183	nodeStack.pop();
2184
2185	if (node->IsLeaf())
2186	{
2187	VspLeaf leaf = static_cast<VspLeaf >(node);
2188
2189	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
2190	neighbors.push_back(leaf);
2191	}
2192	else
2193	{
2194	VspInterior interior = static_cast<VspInterior >(node);
2195
2196	if (interior->GetPosition() > box.Max(interior->GetAxis()))
2197	nodeStack.push(interior->GetBack());
2198	else
2199	{
2200	if (interior->GetPosition() < box.Min(interior->GetAxis()))
2201	nodeStack.push(interior->GetFront());
2202	else
2203	{
2204	// random decision
2205	nodeStack.push(interior->GetBack());
2206	nodeStack.push(interior->GetFront());
2207	}
2208	}
2209	}
2210	}
2211
2212	return (int)neighbors.size();
2213	}
2214
2215
2216	// Find random neighbor which was not mailed
2217	VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
2218	{
2219	stack<VspNode *> nodeStack;
2220	nodeStack.push(mRoot);
2221
2222	int mask = rand();
2223
2224	while (!nodeStack.empty())
2225	{
2226	VspNode *node = nodeStack.top();
2227
2228	nodeStack.pop();
2229
2230	if (node->IsLeaf())
2231	{
2232	return static_cast<VspLeaf *>(node);
2233	}
2234	else
2235	{
2236	VspInterior interior = static_cast<VspInterior >(node);
2237	VspNode *next;
2238
2239	if (GetBoundingBox(interior->GetBack()).Side(plane) < 0)
2240	{
2241	next = interior->GetFront();
2242	}
2243	else
2244	{
2245	if (GetBoundingBox(interior->GetFront()).Side(plane) < 0)
2246	{
2247	next = interior->GetBack();
2248	}
2249	else
2250	{
2251	// random decision
2252	if (mask & 1)
2253	next = interior->GetBack();
2254	else
2255	next = interior->GetFront();
2256	mask = mask >> 1;
2257	}
2258	}
2259
2260	nodeStack.push(next);
2261	}
2262	}
2263
2264	return NULL;
2265	}
2266
2267
2268	VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
2269	{
2270	stack<VspNode *> nodeStack;
2271
2272	nodeStack.push(mRoot);
2273
2274	int mask = rand();
2275
2276	while (!nodeStack.empty())
2277	{
2278	VspNode *node = nodeStack.top();
2279	nodeStack.pop();
2280
2281	if (node->IsLeaf())
2282	{
2283	if ( (!onlyUnmailed \|\| !node->Mailed()) )
2284	return static_cast<VspLeaf *>(node);
2285	}
2286	else
2287	{
2288	VspInterior interior = static_cast<VspInterior >(node);
2289
2290	// random decision
2291	if (mask & 1)
2292	nodeStack.push(interior->GetBack());
2293	else
2294	nodeStack.push(interior->GetFront());
2295
2296	mask = mask >> 1;
2297	}
2298	}
2299
2300	return NULL;
2301	}
2302
2303
2304	float VspTree::EvalPvsCost(const RayInfoContainer &rays) const
2305	{
2306	float pvsCost = 0;
2307
2308	Intersectable::NewMail();
2309	KdNode::NewMail();
2310
2311	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2312
2313	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2314	{
2315	VssRay ray = (rit).mRay;
2316
2317	pvsCost += EvalContributionToPvs(*ray, true);
2318
2319	#if COUNT_ORIGIN_OBJECTS
2320	pvsCost += EvalContributionToPvs(*ray, false);
2321	#endif
2322	}
2323
2324	return pvsCost;
2325	}
2326
2327
2328	int VspTree::EvalPvsEntriesContribution(const VssRay &ray,
2329	const bool isTermination) const
2330
2331	{
2332
2333	#if HACK_PERFORMANCE
2334	Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject;
2335
2336	if (!obj) return 0;
2337	BvhLeaf *bvhleaf = mBvHierarchy->GetLeaf(obj);
2338
2339	if (!bvhleaf->Mailed())
2340	{
2341	bvhleaf->Mail();
2342	return 1;
2343	}
2344
2345	#else
2346
2347	Intersectable *obj;
2348	static Vector3 pt;
2349	KdNode *node;
2350
2351	ray.GetSampleData(isTermination, pt, &obj, &node);
2352
2353	if (!obj) return 0;
2354
2355	switch(mHierarchyManager->GetObjectSpaceSubdivisionType())
2356	{
2357	case HierarchyManager::NO_OBJ_SUBDIV:
2358	{
2359	if (!obj->Mailed())
2360	{
2361	obj->Mail();
2362	return 1;
2363	}
2364
2365	return 0;
2366	}
2367
2368	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2369	{
2370	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2371	if (!leaf->Mailed())
2372	{
2373	leaf->Mail();
2374	return 1;
2375	}
2376
2377	return 0;
2378	}
2379	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2380	{
2381	BvhLeaf *bvhleaf = mBvHierarchy->GetLeaf(obj);
2382
2383	if (!bvhleaf->Mailed())
2384	{
2385	bvhleaf->Mail();
2386	return 1;
2387	}
2388
2389	return 0;
2390	}
2391	default:
2392	break;
2393	}
2394	#endif
2395	return 0;
2396	}
2397
2398
2399	int VspTree::EvalPvsEntriesSize(const RayInfoContainer &rays) const
2400	{
2401	int pvsSize = 0;
2402
2403	Intersectable::NewMail();
2404	KdNode::NewMail();
2405
2406	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2407
2408	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2409	{
2410	VssRay ray = (rit).mRay;
2411
2412	pvsSize += EvalPvsEntriesContribution(*ray, true);
2413
2414	#if COUNT_ORIGIN_OBJECTS
2415	pvsSize += EvalPvsEntriesContribution(*ray, false);
2416	#endif
2417	}
2418
2419	return pvsSize;
2420	}
2421
2422
2423	float VspTree::GetEpsilon() const
2424	{
2425	return mEpsilon;
2426	}
2427
2428
2429	int VspTree::CastLineSegment(const Vector3 &origin,
2430	const Vector3 &termination,
2431	ViewCellContainer &viewcells,
2432	const bool useMailboxing)
2433	{
2434	int hits = 0;
2435
2436	float mint = 0.0f, maxt = 1.0f;
2437	const Vector3 dir = termination - origin;
2438
2439	stack<LineTraversalData> tStack;
2440
2441	Vector3 entp = origin;
2442	Vector3 extp = termination;
2443
2444	VspNode *node = mRoot;
2445	VspNode *farChild;
2446
2447	float position;
2448	int axis;
2449
2450	while (1)
2451	{
2452	if (!node->IsLeaf())
2453	{
2454	VspInterior in = static_cast<VspInterior >(node);
2455	position = in->GetPosition();
2456	axis = in->GetAxis();
2457
2458	if (entp[axis] <= position)
2459	{
2460	if (extp[axis] <= position)
2461	{
2462	node = in->GetBack();
2463	// cases N1,N2,N3,P5,Z2,Z3
2464	continue;
2465	}
2466	else
2467	{
2468	// case N4
2469	node = in->GetBack();
2470	farChild = in->GetFront();
2471	}
2472	}
2473	else
2474	{
2475	if (position <= extp[axis])
2476	{
2477	node = in->GetFront();
2478	// cases P1,P2,P3,N5,Z1
2479	continue;
2480	}
2481	else
2482	{
2483	node = in->GetFront();
2484	farChild = in->GetBack();
2485	// case P4
2486	}
2487	}
2488
2489	// $$ modification 3.5.2004 - hints from Kamil Ghais
2490	// case N4 or P4
2491	const float tdist = (position - origin[axis]) / dir[axis];
2492	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2493
2494	// new exit point for near child
2495	extp = origin + dir * tdist;
2496	maxt = tdist;
2497	}
2498	else
2499	{
2500	// compute intersection with all objects in this leaf
2501	VspLeaf leaf = static_cast<VspLeaf >(node);
2502	ViewCell *viewCell;
2503
2504	if (0)
2505	viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2506	else
2507	viewCell = leaf->GetViewCell();
2508
2509	// don't have to mail if each view cell belongs to exactly one leaf
2510	if (!useMailboxing \|\| !viewCell->Mailed())
2511	{
2512	if (useMailboxing)
2513	viewCell->Mail();
2514
2515	viewcells.push_back(viewCell);
2516	++ hits;
2517	}
2518
2519	// get the next node from the stack
2520	if (tStack.empty())
2521	break;
2522
2523	// set new entry point for far child
2524	entp = extp;
2525	mint = maxt;
2526
2527	LineTraversalData &s = tStack.top();
2528	node = s.mNode;
2529	extp = s.mExitPoint;
2530	maxt = s.mMaxT;
2531
2532	tStack.pop();
2533	}
2534	}
2535
2536	return hits;
2537	}
2538
2539
2540	int VspTree::TraverseRayPacket(RayPacket &rp, const bool useMailboxing)
2541	{
2542	#ifdef USE_SSE
2543	int hits = 0;
2544
2545	// reciprocal of ray directions
2546	float one = 1.0f;
2547	float zero = 0.0f;
2548
2549	__m128 one4 = _mm_load1_ps(&one);
2550	__m128 zero4 = _mm_load1_ps(&zero);
2551
2552	union { __m128 mask4; float mask[4];};
2553	union { __m128 mask4_2; float mask_2[4];};
2554
2555	mask4 = one4;
2556
2557	__declspec(align(16)) __m128 entp4[] = {rp.mOriginX4, rp.mOriginY4, rp.mOriginZ4};
2558	__declspec(align(16)) __m128 extp4[] = {rp.mTerminationX4, rp.mTerminationY4, rp.mTerminationZ4};
2559
2560	__m128 *origin = &rp.mOriginX4;
2561	__m128 *termination = &rp.mTerminationX4;
2562
2563	// ray directions
2564	__m128 dirX4 = _mm_sub_ps(rp.mTerminationX4, rp.mOriginX4);
2565	__m128 dirY4 = _mm_sub_ps(rp.mTerminationY4, rp.mOriginY4);;
2566	__m128 dirZ4 = _mm_sub_ps(rp.mTerminationZ4, rp.mOriginZ4);;
2567
2568	__m128 rdx4 = _mm_div_ps(one4, dirX4);
2569	__m128 rdy4 = _mm_div_ps(one4, dirY4);
2570	__m128 rdz4 = _mm_div_ps(one4, dirZ4);
2571
2572	__m128 maxT4 = one4;
2573	__m128 minT4 = zero4;
2574
2575	PacketTraversalStack tStack(1000);
2576
2577	VspNode *node = mRoot;
2578	VspNode *farChild;
2579
2580	float position;
2581	int axis;
2582
2583	__m128 position4;
2584
2585	while (1)
2586	{
2587	if (!node->IsLeaf())
2588	{
2589	VspInterior in = static_cast<VspInterior >(node);
2590
2591	position = in->GetPosition();
2592	axis = in->GetAxis();
2593
2594	position4 = _mm_load1_ps(&position);
2595
2596	// are the entry points all in near leaf?
2597	if (_mm_movemask_ps(_mm_and_ps(_mm_cmple_ps(entp4[axis], position4), mask4)))
2598	{
2599	// are the exit points all in near leaf?
2600	if (_mm_movemask_ps(_mm_and_ps(_mm_cmple_ps(extp4[axis], position4), mask4)))
2601	{
2602	node = in->GetBack();
2603	// cases N1,N2,N3,P5,Z2,Z3
2604	continue;
2605	}
2606	else // traverse both children
2607	{
2608	// case N4
2609	node = in->GetBack();
2610	farChild = in->GetFront();
2611	}
2612	}
2613	else
2614	{
2615	if (_mm_movemask_ps(_mm_and_ps(_mm_cmple_ps(position4, entp4[axis]), mask4)) &&
2616	_mm_movemask_ps(_mm_and_ps(_mm_cmple_ps(position4, extp4[axis]), mask4)))
2617	{
2618	node = in->GetFront();
2619	// cases P1,P2,P3,N5,Z1
2620	continue;
2621	}
2622	else // traverse both children
2623	{
2624	node = in->GetFront();
2625	farChild = in->GetBack();
2626	// case P4
2627	}
2628	}
2629
2630	// $$ modification 3.5.2004 - hints from Kamil Ghais
2631	// case N4 or P4
2632	const __m128 tDist4 = _mm_mul_ps(_mm_sub_ps(position4, origin[axis]), termination[axis]);
2633
2634	mask4 = _mm_and_ps(_mm_cmplt_ps(tDist4, minT4), mask4);
2635	mask4_2 = _mm_and_ps(_mm_cmpgt_ps(tDist4, minT4), mask4);
2636
2637	// push far child for further processing
2638	tStack.Push(PacketTraversalData(farChild, extp4[0], extp4[1], extp4[2], maxT4, mask4_2));
2639
2640	// compute new exit point
2641	extp4[0] = _mm_add_ps(_mm_mul_ps(dirX4, tDist4), rp.mOriginX4);
2642	extp4[1] = _mm_add_ps(_mm_mul_ps(dirY4, tDist4), rp.mOriginY4);
2643	extp4[2] = _mm_add_ps(_mm_mul_ps(dirZ4, tDist4), rp.mOriginZ4);
2644
2645	maxT4 = tDist4;
2646	}
2647	else
2648	{
2649	// compute intersection with all objects in this leaf
2650	VspLeaf leaf = static_cast<VspLeaf >(node);
2651	ViewCell *viewCell;
2652
2653	viewCell = leaf->GetViewCell();
2654
2655	// note: don't have to mail if each view
2656	// cell belongs to exactly one leaf
2657	if (!useMailboxing \|\| !viewCell->Mailed())
2658	{
2659	if (useMailboxing)
2660	viewCell->Mail();
2661
2662	for (int i = 0; i < 4; ++i)
2663	{
2664	// push view cells for all valid rays
2665	if (mask[i])
2666	rp.mViewCells[i].push_back(viewCell);
2667	}
2668
2669	++ hits;
2670	}
2671
2672	// get the next node from the stack
2673	if (tStack.Empty())
2674	break;
2675
2676	// use memcopy?
2677	entp4[0] = extp4[0];
2678	entp4[1] = extp4[1];
2679	entp4[2] = extp4[2];
2680
2681	minT4 = maxT4;
2682
2683	const PacketTraversalData &s = tStack.Top();
2684	node = s.mNode;
2685
2686	extp4[0] = s.mExitPointX4;
2687	extp4[1] = s.mExitPointY4;
2688	extp4[2] = s.mExitPointZ4;
2689
2690	maxT4 = s.mMaxT4;
2691	mask4 = s.mMask4;
2692
2693	tStack.Pop();
2694	}
2695	}
2696
2697	return hits;
2698
2699	#else
2700
2701	return 0;
2702	#endif
2703	}
2704
2705
2706	int VspTree::CastRay(Ray &ray)
2707	{
2708	int hits = 0;
2709
2710	stack<LineTraversalData> tStack;
2711	const Vector3 dir = ray.GetDir();
2712
2713	float maxt, mint;
2714
2715	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
2716	return 0;
2717
2718	Intersectable::NewMail();
2719	ViewCell::NewMail();
2720
2721	Vector3 entp = ray.Extrap(mint);
2722	Vector3 extp = ray.Extrap(maxt);
2723
2724	const Vector3 origin = entp;
2725
2726	VspNode *node = mRoot;
2727	VspNode *farChild = NULL;
2728
2729	float position;
2730	int axis;
2731
2732	while (1)
2733	{
2734	if (!node->IsLeaf())
2735	{
2736	VspInterior in = static_cast<VspInterior >(node);
2737	position = in->GetPosition();
2738	axis = in->GetAxis();
2739
2740	if (entp[axis] <= position)
2741	{
2742	if (extp[axis] <= position)
2743	{
2744	node = in->GetBack();
2745	// cases N1,N2,N3,P5,Z2,Z3
2746	continue;
2747	}
2748	else
2749	{
2750	// case N4
2751	node = in->GetBack();
2752	farChild = in->GetFront();
2753	}
2754	}
2755	else
2756	{
2757	if (position <= extp[axis])
2758	{
2759	node = in->GetFront();
2760	// cases P1,P2,P3,N5,Z1
2761	continue;
2762	}
2763	else
2764	{
2765	node = in->GetFront();
2766	farChild = in->GetBack();
2767	// case P4
2768	}
2769	}
2770
2771	// $$ modification 3.5.2004 - hints from Kamil Ghais
2772	// case N4 or P4
2773	const float tdist = (position - origin[axis]) / dir[axis];
2774	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2775	extp = origin + dir * tdist;
2776	maxt = tdist;
2777	}
2778	else
2779	{
2780	// compute intersection with all objects in this leaf
2781	VspLeaf leaf = static_cast<VspLeaf >(node);
2782	ViewCell *vc = leaf->GetViewCell();
2783
2784	if (!vc->Mailed())
2785	{
2786	vc->Mail();
2787	// todo: add view cells to ray
2788	++ hits;
2789	}
2790
2791	// get the next node from the stack
2792	if (tStack.empty())
2793	break;
2794
2795	entp = extp;
2796	mint = maxt;
2797
2798	LineTraversalData &s = tStack.top();
2799	node = s.mNode;
2800	extp = s.mExitPoint;
2801	maxt = s.mMaxT;
2802	tStack.pop();
2803	}
2804	}
2805
2806	return hits;
2807	}
2808
2809
2810	ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
2811	{
2812	if (!mRoot)
2813	return NULL;
2814
2815	stack<VspNode *> nodeStack;
2816	nodeStack.push(mRoot);
2817
2818	ViewCellLeaf *viewcell = NULL;
2819
2820	while (!nodeStack.empty())
2821	{
2822	VspNode *node = nodeStack.top();
2823	nodeStack.pop();
2824
2825	if (node->IsLeaf())
2826	{
2827	/const AxisAlignedBox3 box = GetBoundingBox(static_cast<VspLeaf >(node));
2828	if (!box.IsInside(point))
2829	cerr << "error, point " << point << " should be in view cell " << box << endl;
2830	*/
2831	viewcell = static_cast<VspLeaf *>(node)->GetViewCell();
2832	break;
2833	}
2834	else
2835	{
2836	VspInterior interior = static_cast<VspInterior >(node);
2837
2838	// random decision
2839	if (interior->GetPosition() - point[interior->GetAxis()] < 0)
2840	{
2841	nodeStack.push(interior->GetFront());
2842	}
2843	else
2844	{
2845	nodeStack.push(interior->GetBack());
2846	}
2847	}
2848	}
2849
2850	// return active or leaf view cell
2851	if (active)
2852	{
2853	return mViewCellsTree->GetActiveViewCell(viewcell);
2854	}
2855	else
2856	{
2857	return viewcell;
2858	}
2859	}
2860
2861
2862	bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
2863	{
2864	VspNode *node = mRoot;
2865
2866	while (1)
2867	{
2868	// early exit
2869	if (node->TreeValid())
2870	return true;
2871
2872	if (node->IsLeaf())
2873	return false;
2874
2875	VspInterior in = static_cast<VspInterior >(node);
2876
2877	if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
2878	{
2879	node = in->GetBack();
2880	}
2881	else
2882	{
2883	node = in->GetFront();
2884	}
2885	}
2886
2887	// should never come here
2888	return false;
2889	}
2890
2891
2892	void VspTree::PropagateUpValidity(VspNode *node)
2893	{
2894	const bool isValid = node->TreeValid();
2895
2896	// propagative up invalid flag until only invalid nodes exist over this node
2897	if (!isValid)
2898	{
2899	while (!node->IsRoot() && node->GetParent()->TreeValid())
2900	{
2901	node = node->GetParent();
2902	node->SetTreeValid(false);
2903	}
2904	}
2905	else
2906	{
2907	// propagative up valid flag until one of the subtrees is invalid
2908	while (!node->IsRoot() && !node->TreeValid())
2909	{
2910	node = node->GetParent();
2911	VspInterior interior = static_cast<VspInterior >(node);
2912
2913	// the parent is valid iff both leaves are valid
2914	node->SetTreeValid(interior->GetBack()->TreeValid() &&
2915	interior->GetFront()->TreeValid());
2916	}
2917	}
2918	}
2919
2920
2921	bool VspTree::Export(OUT_STREAM &stream)
2922	{
2923	ExportNode(mRoot, stream);
2924
2925	return true;
2926	}
2927
2928
2929	void VspTree::ExportNode(VspNode *node, OUT_STREAM &stream)
2930	{
2931	if (node->IsLeaf())
2932	{
2933	VspLeaf leaf = static_cast<VspLeaf >(node);
2934	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2935
2936	int id = -1;
2937	if (viewCell != mOutOfBoundsCell)
2938	id = viewCell->GetId();
2939
2940	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
2941	}
2942	else
2943	{
2944	VspInterior interior = static_cast<VspInterior >(node);
2945
2946	AxisAlignedPlane plane = interior->GetPlane();
2947	stream << "<Interior plane=\"" << plane.mPosition << " "
2948	<< plane.mAxis << "\">" << endl;
2949
2950	ExportNode(interior->GetBack(), stream);
2951	ExportNode(interior->GetFront(), stream);
2952
2953	stream << "</Interior>" << endl;
2954	}
2955	}
2956
2957
2958	int VspTree::SplitRays(const AxisAlignedPlane &plane,
2959	RayInfoContainer &rays,
2960	RayInfoContainer &frontRays,
2961	RayInfoContainer &backRays) const
2962	{
2963	int splits = 0;
2964
2965	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2966
2967	for (rit = rays.begin(); rit != rit_end; ++ rit)
2968	{
2969	RayInfo bRay = *rit;
2970
2971	VssRay *ray = bRay.mRay;
2972	float t;
2973
2974	// get classification and receive new t
2975	// test if start point behind or in front of plane
2976	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
2977
2978	if (side == 0)
2979	{
2980	++ splits;
2981
2982	if (ray->HasPosDir(plane.mAxis))
2983	{
2984	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2985	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2986	}
2987	else
2988	{
2989	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2990	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2991	}
2992	}
2993	else if (side == 1)
2994	{
2995	frontRays.push_back(bRay);
2996	}
2997	else
2998	{
2999	backRays.push_back(bRay);
3000	}
3001	}
3002
3003	return splits;
3004	}
3005
3006
3007	AxisAlignedBox3 VspTree::GetBoundingBox(VspNode *node) const
3008	{
3009	if (!node->GetParent())
3010	return mBoundingBox;
3011
3012	if (!node->IsLeaf())
3013	{
3014	return (static_cast<VspInterior *>(node))->GetBoundingBox();
3015	}
3016
3017	VspInterior parent = static_cast<VspInterior >(node->GetParent());
3018
3019	AxisAlignedBox3 box(parent->GetBoundingBox());
3020
3021	if (parent->GetFront() == node)
3022	box.SetMin(parent->GetAxis(), parent->GetPosition());
3023	else
3024	box.SetMax(parent->GetAxis(), parent->GetPosition());
3025
3026	return box;
3027	}
3028
3029
3030	int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
3031	ViewCellContainer &viewCells) const
3032	{
3033	stack<VspNode *> nodeStack;
3034
3035	ViewCell::NewMail();
3036
3037	nodeStack.push(mRoot);
3038
3039	while (!nodeStack.empty())
3040	{
3041	VspNode *node = nodeStack.top();
3042	nodeStack.pop();
3043
3044	const AxisAlignedBox3 bbox = GetBoundingBox(node);
3045
3046	if (Overlap(bbox, box))
3047	{
3048	if (node->IsLeaf())
3049	{
3050	VspLeaf leaf = static_cast<VspLeaf >(node);
3051
3052	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
3053	{
3054	leaf->GetViewCell()->Mail();
3055	viewCells.push_back(leaf->GetViewCell());
3056	}
3057	}
3058	else
3059	{
3060	VspInterior interior = static_cast<VspInterior >(node);
3061
3062	VspNode *first = interior->GetFront();
3063	VspNode *second = interior->GetBack();
3064
3065	nodeStack.push(first);
3066	nodeStack.push(second);
3067	}
3068	}
3069	// default: cull
3070	}
3071
3072	return (int)viewCells.size();
3073	}
3074
3075
3076	void VspTree::PreprocessRays(const VssRayContainer &sampleRays,
3077	RayInfoContainer &rays)
3078	{
3079	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
3080
3081	long startTime = GetTime();
3082
3083	cout << "storing rays ... ";
3084
3085	Intersectable::NewMail();
3086
3087	////////////////
3088	//-- store rays and objects
3089
3090	VssRay *lastVssRay = NULL;
3091
3092	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
3093	{
3094	VssRay ray = rit;
3095
3096	// filter out double rays (last ray the same as this ray
3097	if (
3098	!lastVssRay \|\|
3099	!(ray->mOrigin == lastVssRay->mTermination) \|\|
3100	!(ray->mTermination == lastVssRay->mOrigin))
3101	{
3102	lastVssRay = ray;
3103
3104	float minT, maxT;
3105	static Ray hray;
3106
3107	hray.Init(*ray);
3108
3109	// TODO: not very efficient to implictly cast between rays types
3110	if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
3111	{
3112	const float len = ray->Length();
3113
3114	if (len) // ray not degenerate
3115	{ //len = Limits::Small;
3116	rays.push_back(RayInfo(ray, minT / len, maxT / len));
3117	}
3118	}
3119	}
3120	else
3121	{
3122	//cout << "r";
3123	// store object only for one ray
3124	//lastVssRay->mOriginObject = ray->mTerminationObject;
3125	}
3126	}
3127
3128	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
3129	}
3130
3131
3132	void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells)
3133	{
3134	mViewCellsTimer.Entry();
3135
3136	static Ray hray;
3137	hray.Init(ray);
3138
3139	float tmin = 0, tmax = 1.0;
3140
3141	if (!mBoundingBox.GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
3142	return;
3143
3144	const Vector3 origin = hray.Extrap(tmin);
3145	const Vector3 termination = hray.Extrap(tmax);
3146
3147	// view cells were not precomputed and are extracted on the fly
3148	// don't mail because the same view cells can be found for different rays
3149	CastLineSegment(origin, termination, viewCells, false);
3150
3151	mViewCellsTimer.Exit();
3152	}
3153
3154
3155	void VspTree::Initialise(const VssRayContainer &rays,
3156	AxisAlignedBox3 *forcedBoundingBox,
3157	const ObjectContainer &objects)
3158	{
3159	ComputeBoundingBox(rays, forcedBoundingBox);
3160
3161	VspLeaf *leaf = new VspLeaf();
3162	mRoot = leaf;
3163
3164	VspViewCell *viewCell = new VspViewCell();
3165	leaf->SetViewCell(viewCell);
3166
3167	viewCell->SetTrianglesInPvs((float)objects.size());
3168	viewCell->SetEntriesInPvs(1);
3169
3170	// set view cell values
3171	viewCell->mLeaves.push_back(leaf);
3172	viewCell->SetVolume(mBoundingBox.GetVolume());
3173
3174	leaf->mProbability = mBoundingBox.GetVolume();
3175	}
3176
3177
3178	void VspTree::PrepareConstruction(SplitQueue &tQueue,
3179	const VssRayContainer &sampleRays,
3180	RayInfoContainer &rays)
3181	{
3182	mVspStats.Reset();
3183	mVspStats.Start();
3184	mVspStats.nodes = 1;
3185
3186	// store pointer to this tree
3187	VspSubdivisionCandidate::sVspTree = this;
3188
3189	mBvHierarchy = mHierarchyManager->mBvHierarchy;
3190
3191	// initialise termination criteria
3192	mTermMinProbability *= mBoundingBox.GetVolume();
3193
3194	// get clipped rays
3195	PreprocessRays(sampleRays, rays);
3196
3197	/// collect pvs from rays
3198	const float pvsCost = EvalPvsCost(rays);
3199
3200	// root and bounding box were already constructed
3201	VspLeaf leaf = static_cast<VspLeaf >(mRoot);
3202
3203	//////////
3204	//-- prepare view space partition
3205
3206	const float prop = mBoundingBox.GetVolume();
3207
3208	// first vsp traversal data
3209	VspTraversalData vData(leaf, 0, &rays, pvsCost, prop, mBoundingBox);
3210
3211	mTotalCost = vData.mCorrectedRenderCost = vData.mRenderCost = pvsCost;
3212	mPvsEntries = EvalPvsEntriesSize(rays);
3213	vData.mCorrectedPvs = vData.mPvs = (float)mPvsEntries;
3214
3215	//////////////
3216	//-- create the first split candidate
3217
3218	VspSubdivisionCandidate *splitCandidate = new VspSubdivisionCandidate(vData);
3219	EvalSubdivisionCandidate(*splitCandidate);
3220	leaf->SetSubdivisionCandidate(splitCandidate);
3221
3222	EvalSubdivisionStats(*splitCandidate);
3223
3224	tQueue.Push(splitCandidate);
3225	}
3226
3227
3228	void VspTree::AddCandidateToDirtyList(const VssRay &ray,
3229	const bool isTermination,
3230	vector<SubdivisionCandidate *> &dirtyList,
3231	const bool onlyUnmailed) const
3232
3233	{
3234	#if HACK_PERFORMANCE
3235
3236	Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject;
3237
3238	if (!obj) return;
3239
3240	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3241	SubdivisionCandidate *candidate;
3242
3243	if (!leaf->Mailed())
3244	{
3245	leaf->Mail();
3246	candidate = leaf->GetSubdivisionCandidate();
3247	}
3248	else
3249	{
3250	candidate = NULL;
3251	}
3252	#else
3253
3254	SubdivisionCandidate *candidate = NULL;
3255
3256	Intersectable *obj;
3257	Vector3 pt;
3258	KdNode *node;
3259
3260	ray.GetSampleData(isTermination, pt, &obj, &node);
3261
3262	if (!obj) return;
3263
3264	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3265	{
3266	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3267	{
3268	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3269
3270	if (!leaf->Mailed())
3271	{
3272	leaf->Mail();
3273	candidate = leaf->mSubdivisionCandidate;
3274	}
3275	break;
3276	}
3277	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3278	{
3279	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3280
3281	if (!leaf->Mailed())
3282	{
3283	leaf->Mail();
3284	candidate = leaf->GetSubdivisionCandidate();
3285	}
3286	break;
3287	}
3288	default:
3289	cerr << "collectdirtycandidates not implemented yet" << endl;
3290	candidate = NULL;
3291	break;
3292	}
3293	#endif
3294
3295	// is this leaf still a split candidate?
3296	if (candidate && (!onlyUnmailed \|\| !candidate->Mailed()))
3297	{
3298	candidate->Mail();
3299	candidate->SetDirty(true);
3300	dirtyList.push_back(candidate);
3301	}
3302	}
3303
3304
3305	void VspTree::CollectDirtyCandidates(VspSubdivisionCandidate *sc,
3306	vector<SubdivisionCandidate *> &dirtyList,
3307	const bool onlyUnmailed)
3308	{
3309	VspTraversalData &tData = sc->mParentData;
3310	VspLeaf *node = tData.mNode;
3311
3312	KdLeaf::NewMail();
3313	Intersectable::NewMail();
3314
3315	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
3316
3317	// add all nodes seen by the rays
3318	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
3319	{
3320	VssRay ray = (rit).mRay;
3321
3322	AddCandidateToDirtyList(*ray, true, dirtyList, onlyUnmailed);
3323
3324	#if COUNT_ORIGIN_OBJECTS
3325	AddCandidateToDirtyList(*ray, false, dirtyList, onlyUnmailed);
3326	#endif
3327	}
3328	}
3329
3330
3331	float VspTree::EvalMaxEventContribution(const VssRay &ray,
3332	const bool isTermination) const
3333	{
3334	#if HACK_PERFORMANCE
3335
3336	Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject;
3337
3338	if (!obj) return 0.0f;
3339
3340	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3341
3342	// simple render cost evaluation
3343	if (-- leaf->mCounter == 0)
3344	return (float)leaf->mObjects.size();
3345	else
3346	return 0.0f;
3347	#else
3348
3349	Intersectable *obj;
3350	Vector3 pt;
3351	KdNode *node;
3352
3353	ray.GetSampleData(isTermination, pt, &obj, &node);
3354
3355	if (!obj) return 0.0f;
3356
3357	float pvs = 0.0f;
3358
3359	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3360	{
3361	case HierarchyManager::NO_OBJ_SUBDIV:
3362	{
3363	if (-- obj->mCounter == 0)
3364	++ pvs;
3365	break;
3366	}
3367	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3368	{
3369	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3370
3371	// add contributions of the kd nodes
3372	pvs += EvalMaxEventContribution(leaf);
3373	break;
3374	}
3375	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3376	{
3377	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3378
3379	// simple render cost evaluation
3380	if (-- leaf->mCounter == 0)
3381	//pvs += (int)leaf->mObjects.size();
3382	pvs += BvHierarchy::EvalAbsCost(leaf->mObjects);
3383	break;
3384	}
3385	default:
3386	break;
3387	}
3388	return pvs;
3389
3390	#endif
3391	}
3392
3393
3394	float VspTree::PrepareHeuristics(const VssRay &ray, const bool isTermination)
3395	{
3396
3397	#if HACK_PERFORMANCE
3398
3399	Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject;
3400
3401	if (!obj) return 0.0f;
3402
3403	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3404
3405	if (!leaf->Mailed())
3406	{
3407	leaf->Mail();
3408	leaf->mCounter = 1;
3409	return (float)leaf->mObjects.size();
3410	}
3411	else
3412	{
3413	++ leaf->mCounter;
3414	return 0.0f;
3415	}
3416
3417	#else
3418
3419	float pvsSize = 0;
3420
3421	Intersectable *obj;
3422	Vector3 pt;
3423	KdNode *node;
3424
3425	ray.GetSampleData(isTermination, pt, &obj, &node);
3426
3427	if (!obj) return 0.0f;
3428
3429	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3430	{
3431	case HierarchyManager::NO_OBJ_SUBDIV:
3432	{
3433	if (!obj->Mailed())
3434	{
3435	obj->Mail();
3436	obj->mCounter = 0;
3437	++ pvsSize;
3438	}
3439
3440	++ obj->mCounter;
3441	break;
3442	}
3443	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3444	{
3445	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3446	pvsSize += PrepareHeuristics(leaf);
3447	break;
3448	}
3449	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3450	{
3451	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3452
3453	if (!leaf->Mailed())
3454	{
3455	leaf->Mail();
3456	leaf->mCounter = 0;
3457	pvsSize += BvHierarchy::EvalAbsCost(leaf->mObjects);
3458	}
3459
3460	++ leaf->mCounter;
3461	break;
3462	}
3463	default:
3464	break;
3465	}
3466	return pvsSize;
3467	#endif
3468
3469	}
3470
3471
3472	float VspTree::EvalMinEventContribution(const VssRay &ray,
3473	const bool isTermination) const
3474	{
3475	#if HACK_PERFORMANCE
3476
3477	Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject;
3478
3479	if (!obj) return 0.0f;
3480
3481	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3482
3483	if (!leaf->Mailed())
3484	{
3485	leaf->Mail();
3486	return (float)leaf->mObjects.size();
3487	}
3488	else
3489	{
3490	return 0.0f;
3491	}
3492	#else
3493
3494	Intersectable *obj;
3495	static Vector3 pt;
3496	KdNode *node;
3497
3498	ray.GetSampleData(isTermination, pt, &obj, &node);
3499
3500	if (!obj) return 0;
3501
3502	float pvs = 0.0f;
3503
3504	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3505	{
3506	case HierarchyManager::NO_OBJ_SUBDIV:
3507	{
3508	if (!obj->Mailed())
3509	{
3510	obj->Mail();
3511	++ pvs;
3512	}
3513	break;
3514	}
3515	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3516	{
3517	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3518	// add contributions of the kd nodes
3519	pvs += EvalMinEventContribution(leaf);
3520	break;
3521	}
3522	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3523	{
3524	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3525	if (!leaf->Mailed())
3526	{
3527	leaf->Mail();
3528	pvs += BvHierarchy->EvalAbsCost(leaf->mObjects);
3529	}
3530	break;
3531	}
3532	default:
3533	break;
3534	}
3535	return pvs;
3536
3537	#endif
3538	}
3539
3540
3541	void VspTree::UpdateContributionsToPvs(const VssRay &ray,
3542	const bool isTermination,
3543	const int cf,
3544	float &frontPvs,
3545	float &backPvs,
3546	float &totalPvs) const
3547	{
3548	#if HACK_PERFORMANCE
3549
3550	BvhLeaf *leaf = mBvHierarchy->GetLeaf(ray.mTerminationObject);
3551	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs, false);
3552
3553	#else
3554
3555	Intersectable *obj;
3556	static Vector3 pt;
3557	KdNode *node;
3558
3559	ray.GetSampleData(isTermination, pt, &obj, &node);
3560
3561	if (!obj) return;
3562
3563	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3564	{
3565	case HierarchyManager::NO_OBJ_SUBDIV:
3566	{
3567	// find front and back pvs for origing and termination object
3568	UpdateContributionsToPvs(obj, cf, frontPvs, backPvs, totalPvs);
3569	break;
3570	}
3571	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3572	{
3573	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3574	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs);
3575	break;
3576	}
3577	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3578	{
3579	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3580	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs, false);
3581	break;
3582	}
3583	}
3584	#endif
3585	}
3586
3587
3588	void VspTree::UpdatePvsEntriesContribution(const VssRay &ray,
3589	const bool isTermination,
3590	const int cf,
3591	float &pvsFront,
3592	float &pvsBack,
3593	float &totalPvs) const
3594	{
3595	#if HACK_PERFORMANCE
3596
3597	BvhLeaf *leaf = mBvHierarchy->GetLeaf(ray.mTerminationObject);
3598	UpdateContributionsToPvs(leaf, cf, pvsFront, pvsBack, totalPvs, true);
3599
3600	#else
3601
3602	Intersectable *obj;
3603	static Vector3 pt;
3604	KdNode *node;
3605
3606	ray.GetSampleData(isTermination, pt, &obj, &node);
3607	if (!obj) return;
3608
3609	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3610	{
3611	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3612	// TODO
3613	break;
3614	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3615	{
3616	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3617	UpdateContributionsToPvs(leaf, cf, pvsFront, pvsBack, totalPvs, true);
3618	break;
3619	}
3620	default:
3621	{
3622	UpdateContributionsToPvs(obj, cf, pvsFront, pvsBack, totalPvs);
3623	break;
3624	}
3625	}
3626	#endif
3627	}
3628
3629
3630	float VspTree::EvalContributionToPvs(const VssRay &ray, const bool isTermination) const
3631	{
3632
3633	#if HACK_PERFORMANCE
3634
3635	Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject;
3636
3637	if (!obj) return 0;
3638
3639	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3640
3641	if (!leaf->Mailed())
3642	{
3643	leaf->Mail();
3644	return (float)leaf->mObjects.size();
3645	}
3646	else
3647	{
3648	return 0.0f;
3649	}
3650
3651	#else
3652
3653	Intersectable *obj;
3654	static Vector3 pt;
3655	KdNode *node;
3656
3657	ray.GetSampleData(isTermination, pt, &obj, &node);
3658
3659	if (!obj) return 0;
3660
3661	float pvs = 0.0f;
3662
3663	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3664	{
3665	case HierarchyManager::NO_OBJ_SUBDIV:
3666	{
3667	if (!obj->Mailed())
3668	{
3669	obj->Mail();
3670	++ pvs;
3671	}
3672	break;
3673	}
3674	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3675	{
3676	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3677	pvs += EvalContributionToPvs(leaf);
3678	break;
3679	}
3680	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3681	{
3682	BvhLeaf *bvhleaf = mBvHierarchy->GetLeaf(obj);
3683
3684	if (!bvhleaf->Mailed())
3685	{
3686	bvhleaf->Mail();
3687	pvs += BvHierarchy::EvalAbsCost(bvhleaf->mObjects);
3688	}
3689	break;
3690	}
3691	default:
3692	break;
3693	}
3694	return pvs;
3695
3696	#endif
3697	}
3698
3699
3700	float VspTree::EvalContributionToPvs(KdLeaf *leaf) const
3701	{
3702	if (leaf->Mailed()) // leaf already mailed
3703	return 0;
3704
3705	leaf->Mail();
3706
3707	// this is the pvs which is uniquely part of this kd leaf
3708	float pvs = (float)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
3709
3710	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
3711
3712	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
3713	{
3714	Intersectable obj = oit;
3715	if (!obj->Mailed())
3716	{
3717	obj->Mail();
3718	++ pvs;
3719	}
3720	}
3721
3722	return pvs;
3723	}
3724
3725
3726	int VspTree::CompressObjects(VspLeaf *leaf)
3727	{
3728	bool compressed = true;
3729
3730	while (compressed)
3731	{
3732	BvhNode::NewMail(2);
3733
3734	ObjectPvsIterator oit = leaf->GetViewCell()->GetPvs().GetIterator();
3735	vector<BvhNode *> parents;
3736	ObjectPvs newPvs;
3737
3738	compressed = false;
3739
3740	while (oit.HasMoreEntries())
3741	{
3742	BvhNode obj = static_cast<BvhNode >(oit.Next());
3743
3744	if (!obj->IsRoot())
3745	{
3746	BvhNode *parent = obj->GetParent();
3747
3748	if (!parent->Mailed())
3749	{
3750	if (parent->Mailed(1))
3751	cout << "error!!" << endl;
3752	parent->Mail();
3753	}
3754	else
3755	{
3756	// sibling was already found =>
3757	// this entry can be exchanged by the parent
3758	parents.push_back(parent);
3759	parent->Mail(1);
3760
3761	compressed = true;
3762	}
3763	}
3764	}
3765
3766	PvsData pvsData;
3767	oit = leaf->GetViewCell()->GetPvs().GetIterator();
3768
3769	while (oit.HasMoreEntries())
3770	{
3771	BvhNode obj = static_cast<BvhNode >(oit.Next(pvsData));
3772
3773	if (!obj->IsRoot())
3774	{
3775	BvhNode *parent = obj->GetParent();
3776
3777	// add only entries that cannot be exchanged with the parent
3778	if (!parent->Mailed(1))
3779	{
3780	newPvs.AddSampleDirty(obj, pvsData.mSumPdf);
3781	}
3782	}
3783	}
3784
3785	// add parents
3786	vector<BvhNode *>::const_iterator bit, bit_end = parents.end();
3787
3788	for (bit = parents.begin(); bit != bit_end; ++ bit)
3789	{
3790	newPvs.AddSampleDirty(*bit, 1);
3791	}
3792
3793	//cout << "size " << newPvs.GetSize() << endl;
3794	leaf->GetViewCell()->SetPvs(newPvs);
3795	}
3796
3797	return leaf->GetViewCell()->GetPvs().GetSize();
3798	}
3799
3800
3801	int VspTree::CompressObjects()
3802	{
3803	vector<VspLeaf *> leaves;
3804	CollectLeaves(leaves);
3805
3806	int numEntries = 0;
3807
3808	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
3809
3810	for (lit = leaves.begin(); lit != lit_end; ++ lit)
3811	{
3812	numEntries += CompressObjects(*lit);
3813	}
3814
3815	return numEntries;
3816	}
3817
3818
3819	void VspTree::EvalMinMaxDepth(int &minDepth, int &maxDepth)
3820	{
3821	stack<pair<VspNode *, int> > nodeStack;
3822	nodeStack.push(pair<VspNode *, int>(mRoot, 0));
3823
3824	minDepth = 999999;
3825	maxDepth = 0;
3826
3827	while (!nodeStack.empty())
3828	{
3829	VspNode *node = nodeStack.top().first;
3830	const int depth = nodeStack.top().second;
3831
3832	nodeStack.pop();
3833
3834	if (node->IsLeaf())
3835	{
3836	// test if this leaf is in valid view space
3837	VspLeaf leaf = static_cast<VspLeaf >(node);
3838
3839	if (depth < minDepth)
3840	minDepth = depth;
3841
3842	if (depth > maxDepth)
3843	maxDepth = depth;
3844	}
3845	else
3846	{
3847	VspInterior interior = static_cast<VspInterior >(node);
3848
3849	nodeStack.push(pair<VspNode *, int>(interior->GetBack(), depth + 1));
3850	nodeStack.push(pair<VspNode *, int>(interior->GetFront(), depth + 1));
3851	}
3852	}
3853	}
3854
3855
3856	//////////
3857	// Binary export
3858
3859	void VspTree::ExportBinInterior(OUT_STREAM &stream, VspInterior *interior)
3860	{
3861	int interiorid = TYPE_INTERIOR;
3862	stream.write(reinterpret_cast<char *>(&interiorid), sizeof(int));
3863
3864	int axis = interior->GetAxis();
3865	float pos = interior->GetPosition();
3866
3867	stream.write(reinterpret_cast<char *>(&axis), sizeof(int));
3868	stream.write(reinterpret_cast<char *>(&pos), sizeof(float));
3869	}
3870
3871
3872	void VspTree::ExportBinLeaf(OUT_STREAM &stream, VspLeaf *leaf)
3873	{
3874	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
3875
3876	int type = TYPE_LEAF;
3877
3878	int id = -1;
3879	if (viewCell != mOutOfBoundsCell)
3880	id = viewCell->GetId();
3881
3882	stream.write(reinterpret_cast<char *>(&type), sizeof(int));
3883	stream.write(reinterpret_cast<char *>(&id), sizeof(int));
3884
3885	int pvsSize = viewCell->GetPvs().GetSize();
3886	stream.write(reinterpret_cast<char *>(&pvsSize), sizeof(int));
3887
3888	ObjectPvsIterator pit = viewCell->GetPvs().GetIterator();
3889
3890	// write PVS of view cell
3891	while (pit.HasMoreEntries())
3892	{
3893	Intersectable *intersect = pit.Next();
3894	id = intersect->GetId();
3895	stream.write(reinterpret_cast<char *>(&id), sizeof(int));
3896	}
3897	}
3898
3899
3900	bool VspTree::ExportBinary(OUT_STREAM &stream)
3901	{
3902	// export binary version of mesh
3903	queue<VspNode *> tStack;
3904	tStack.push(mRoot);
3905
3906	while(!tStack.empty())
3907	{
3908	VspNode *node = tStack.front();
3909	tStack.pop();
3910
3911	if (node->IsLeaf())
3912	{
3913	ExportBinLeaf(stream, static_cast<VspLeaf *>(node));
3914	}
3915	else
3916	{
3917	VspInterior interior = static_cast<VspInterior >(node);
3918
3919	ExportBinInterior(stream, interior);
3920
3921	tStack.push(interior->GetFront());
3922	tStack.push(interior->GetBack());
3923	}
3924	}
3925
3926	return true;
3927	}
3928
3929
3930	//////////////////
3931	// import binary
3932
3933	VspInterior VspTree::ImportBinInterior(IN_STREAM &stream, VspInterior parent)
3934	{
3935	AxisAlignedPlane plane;
3936
3937	stream.read(reinterpret_cast<char *>(&plane.mAxis), sizeof(int));
3938	stream.read(reinterpret_cast<char *>(&plane.mPosition), sizeof(float));
3939
3940	VspInterior *interior = new VspInterior(plane);
3941
3942	return interior;
3943	}
3944
3945
3946	VspLeaf *VspTree::ImportBinLeaf(IN_STREAM &stream,
3947	VspInterior *parent,
3948	const ObjectContainer &pvsObjects)
3949	{
3950	#if TODO
3951	int leafId = TYPE_LEAF;
3952	int objId = leafId;
3953	int size;
3954
3955	stream.read(reinterpret_cast<char *>(&size), sizeof(int));
3956	KdLeaf *leaf = new KdLeaf(parent, size);
3957
3958	MeshInstance dummyInst(NULL);
3959
3960	// read object ids
3961	// note: could also do this geometrically
3962	for (int i = 0; i < size; ++ i)
3963	{
3964	stream.read(reinterpret_cast<char *>(&objId), sizeof(int));
3965	dummyInst.SetId(objId);
3966
3967	ObjectContainer::const_iterator oit =
3968	lower_bound(objects.begin(), objects.end(), (Intersectable *)&dummyInst, ilt);
3969
3970	if ((oit != objects.end()) && ((*oit)->GetId() == objId))
3971	leaf->mObjects.push_back(*oit);
3972	else
3973	Debug << "error: object with id " << objId << " does not exist" << endl;
3974	}
3975	return leaf;
3976	#endif
3977	return NULL;
3978	}
3979
3980
3981	VspNode *VspTree::ImportNextNode(IN_STREAM &stream,
3982	VspInterior *parent,
3983	const ObjectContainer &objects)
3984	{
3985	int nodeType;
3986	stream.read(reinterpret_cast<char *>(&nodeType), sizeof(int));
3987
3988	if (nodeType == TYPE_LEAF)
3989	return ImportBinLeaf(stream, static_cast<VspInterior *>(parent), objects);
3990
3991	if (nodeType == TYPE_INTERIOR)
3992	return ImportBinInterior(stream, static_cast<VspInterior *>(parent));
3993
3994	Debug << "error! loading failed!" << endl;
3995	return NULL;
3996	}
3997
3998
3999	/** Data used for tree traversal
4000	*/
4001	struct MyTraversalData
4002	{
4003	public:
4004
4005	MyTraversalData(VspNode *node, const int depth, const AxisAlignedBox3 &box):
4006	mNode(node), mDepth(depth), mBox(box)
4007	{}
4008
4009
4010	//////////////////////
4011
4012	/// the current node
4013	VspNode *mNode;
4014	/// current depth
4015	int mDepth;
4016	/// the bounding box
4017	AxisAlignedBox3 mBox;
4018	};
4019
4020
4021	bool VspTree::ImportBinary(IN_STREAM &stream, ObjectContainer &pvsObjects)
4022	{
4023	// export binary version of mesh
4024	queue<MyTraversalData> tStack;
4025
4026	// sort objects by their id
4027	//sort(objects.begin(), objects.end(), ilt);
4028
4029	// hack: we make a new root
4030	DEL_PTR(mRoot);
4031
4032	mRoot = ImportNextNode(stream, NULL, pvsObjects);
4033
4034	tStack.push(MyTraversalData(mRoot, 0, mBoundingBox));
4035	mVspStats.Reset();
4036	mVspStats.nodes = 1;
4037
4038	while(!tStack.empty())
4039	{
4040	MyTraversalData tData = tStack.front();
4041	tStack.pop();
4042
4043	VspNode *node = tData.mNode;
4044
4045	if (!node->IsLeaf())
4046	{
4047	mVspStats.nodes += 2;
4048
4049	//Debug << "i" ;
4050	VspInterior interior = static_cast<VspInterior >(node);
4051	interior->SetBoundingBox(tData.mBox);
4052
4053	VspNode *front = ImportNextNode(stream, interior, pvsObjects);
4054	VspNode *back = ImportNextNode(stream, interior, pvsObjects);
4055
4056	interior->SetupChildLinks(back, front);
4057
4058	++ mVspStats.splits[interior->GetAxis()];
4059
4060	// compute new bounding box
4061	AxisAlignedBox3 frontBox, backBox;
4062
4063	tData.mBox.Split(interior->GetAxis(),
4064	interior->GetPosition(),
4065	frontBox,
4066	backBox);
4067
4068	tStack.push(MyTraversalData(front, tData.mDepth + 1, frontBox));
4069	tStack.push(MyTraversalData(back, tData.mDepth + 1, backBox));
4070	}
4071	else
4072	{
4073	//EvaluateLeafStats(tData);
4074	//cout << "l";
4075	}
4076	}
4077	return true;
4078	}
4079
4080
4081	}

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

Download in other formats: