Context Navigation

OspTree.cpp @ 2542

Revision 2542, 60.6 KB checked in by mattausch, 17 years ago (diff)

Line
1	#include <stack>
2	#include <time.h>
3	#include <iomanip>
4
5	#include "ViewCell.h"
6	#include "Plane3.h"
7	#include "OspTree.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 "VspTree.h"
21
22	using namespace std;
23
24
25	namespace GtpVisibilityPreprocessor {
26
27
28	#define USE_FIXEDPOINT_T 0
29
30
31	int MailablePvsData::sMailId = 1;
32	int MailablePvsData::sReservedMailboxes = 1;
33
34
35	////////////
36	//-- static members
37
38	OspTree *OspTree::OspSubdivisionCandidate::sOspTree = NULL;
39
40	// variable for debugging volume contribution for heuristics
41	static float debugVol;
42
43	static bool ViewCellHasMultipleReferences(Intersectable *obj,
44	ViewCell *vc,
45	bool checkOnlyMailed)
46	{
47	// no view cell pvs!!
48	/* MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
49
50	if (vdata)
51	{
52	// more than one view cell sees this object inside different kd cells
53	if (!checkOnlyMailed \|\| !vdata->Mailed())
54	{
55	if (checkOnlyMailed)
56	vdata->Mail();
57	//Debug << "sumpdf: " << vdata->mSumPdf << endl;
58	if (vdata->mSumPdf > 1.5f)
59	return true;
60	}
61	}*/
62
63	return false;
64	}
65
66
67	void OspTreeStatistics::Print(ostream &app) const
68	{
69	app << "=========== OspTree statistics ===============\n";
70
71	app << setprecision(4);
72
73	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
74
75	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
76
77	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
78
79	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
80
81	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
82
83	app << "#N_SPLITS ( Number of splits in axes x y z)\n";
84
85	for (int i = 0; i < 3; ++ i)
86	app << splits[i] << " ";
87	app << endl;
88
89	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
90	<< maxDepthNodes * 100 / (double)Leaves() << endl;
91
92	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
93	<< minPvsNodes * 100 / (double)Leaves() << endl;
94
95	//app << "#N_PMINOBJECTREFLEAVES ( Percentage of leaves with minimal number of object ref)\n"
96	//<< minObjectNodes * 100 / (double)Leaves() << endl;
97
98	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
99	<< maxCostNodes * 100 / (double)Leaves() << endl;
100
101	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
102	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
103
104	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
105
106	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
107
108	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
109
110	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
111
112	app << "#N_MAXOBJECTREFS ( Max number of object refs / leaf )\n" <<
113	maxObjectRefs << "\n";
114
115	// app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
116	//app << "#N_PVS: " << pvs << endl;
117
118	app << "========== END OF VspTree statistics ==========\n";
119	}
120
121
122	/******************************************************************/
123	/* class VspNode implementation */
124	/******************************************************************/
125
126
127	/*******************************************************************/
128	/* class OspTree implementation */
129	/*******************************************************************/
130
131
132	OspTree::OspTree():
133	mRoot(NULL),
134	mTimeStamp(1),
135	mCopyFromKdTree(false)
136	{
137	ReadEnvironment();
138	mSubdivisionCandidates = new vector<SortableEntry>;
139	}
140
141
142	OspTree::OspTree(const KdTree &kdTree)
143	{
144	ReadEnvironment();
145
146	// copy values from kd tree
147	mCopyFromKdTree = true;
148	mBoundingBox = kdTree.GetBox();
149	mRoot = kdTree.GetRoot();
150
151	mSubdivisionCandidates = new vector<SortableEntry>;
152	}
153
154
155	OspTree::~OspTree()
156	{
157	// delete kd intersectables
158	KdIntersectableMap::iterator it, it_end = mKdIntersectables.end();
159
160	for (it = mKdIntersectables.begin(); it != mKdIntersectables.end(); ++ it)
161	{
162	DEL_PTR((*it).second);
163	}
164
165	// delete hierarchy only if not using the hierarchy from
166	// some other kd tree (otherwise the other kd tree has to do the job)
167	if (!mCopyFromKdTree)
168	DEL_PTR(mRoot);
169
170	DEL_PTR(mSubdivisionCandidates);
171	mSubdivisionStats.close();
172	}
173
174
175	void OspTree::ReadEnvironment()
176	{
177	bool randomize = false;
178	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
179	if (randomize)
180	Randomize(); // initialise random generator for heuristics
181
182	//-- termination criteria for autopartition
183	Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxDepth", mTermMaxDepth);
184	Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxLeaves", mTermMaxLeaves);
185	Environment::GetSingleton()->GetIntValue("OspTree.Termination.minObjects", mTermMinObjects);
186	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minProbability", mTermMinProbability);
187
188	Environment::GetSingleton()->GetIntValue("OspTree.Termination.missTolerance", mTermMissTolerance);
189
190	//-- max cost ratio for early tree termination
191	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.maxCostRatio", mTermMaxCostRatio);
192
193	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minGlobalCostRatio",
194	mTermMinGlobalCostRatio);
195
196
197	//-- factors for bsp tree split plane heuristics
198	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.ct_div_ci", mCtDivCi);
199
200	//-- partition criteria
201	Environment::GetSingleton()->GetFloatValue("OspTree.Construction.epsilon", mEpsilon);
202
203	// if only the driving axis is used for axis aligned split
204	Environment::GetSingleton()->GetBoolValue("OspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
205	Environment::GetSingleton()->GetFloatValue("OspTree.maxStaticMemory", mMaxMemory);
206	Environment::GetSingleton()->GetBoolValue("OspTree.useCostHeuristics", mUseCostHeuristics);
207
208
209	char subdivisionStatsLog[100];
210	Environment::GetSingleton()->GetStringValue("OspTree.subdivisionStats", subdivisionStatsLog);
211	mSubdivisionStats.open(subdivisionStatsLog);
212
213	Environment::GetSingleton()->GetFloatValue("OspTree.Construction.splitBorder", mSplitBorder);
214	Environment::GetSingleton()->GetFloatValue(
215	"OspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
216
217
218	//-- debug output
219
220	Debug << "***** OSP tree options ****** " << endl;
221
222	Debug << "max depth: " << mTermMaxDepth << endl;
223	Debug << "min probabiliy: " << mTermMinProbability << endl;
224	Debug << "min objects: " << mTermMinObjects << endl;
225	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
226	Debug << "miss tolerance: " << mTermMissTolerance << endl;
227	Debug << "max leaves: " << mTermMaxLeaves << endl;
228
229	Debug << "randomize: " << randomize << endl;
230
231	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
232	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
233	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
234	Debug << "max memory: " << mMaxMemory << endl;
235	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
236	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
237
238	Debug << "split borders: " << mSplitBorder << endl;
239	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
240	Debug << endl;
241	}
242
243
244	void OspTree::SplitObjects(KdLeaf *parent,
245	const AxisAlignedPlane& splitPlane,
246	const ObjectContainer &objects,
247	ObjectContainer &front,
248	ObjectContainer &back)
249	{
250	ObjectContainer::const_iterator oit, oit_end = objects.end();
251
252	for (oit = objects.begin(); oit != oit_end; ++ oit)
253	{
254	Intersectable object = oit;
255
256	// initialise leaf references of objects
257	if (parent->IsRoot())
258	{
259	// matt: no more parent ref
260	//object->mReferences = 1;
261	}
262
263	// remove parent ref
264	// matt: no more parent ref
265	//-- object->mReferences;
266
267	// determine the side of this ray with respect to the plane
268	const AxisAlignedBox3 box = object->GetBox();
269
270	if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition)
271	{
272	front.push_back(object);
273	// matt: no more ref
274	//++ object->mReferences;
275	}
276
277	if (box.Min(splitPlane.mAxis) < splitPlane.mPosition)
278	{
279	back.push_back(object);
280	// matt: no more ref
281	//++ object->mReferences;
282	}
283	}
284
285	mOspStats.objectRefs -= (int)objects.size();
286	mOspStats.objectRefs += (int)(back.size() + front.size());
287	}
288
289
290	KdInterior *OspTree::SubdivideNode(
291	const AxisAlignedPlane &splitPlane,
292	const OspTraversalData &tData,
293	OspTraversalData &frontData,
294	OspTraversalData &backData
295	)
296	{
297	KdLeaf *leaf = tData.mNode;
298
299	// two new leaves
300	mOspStats.nodes += 2;
301
302	// add the new nodes to the tree
303	KdInterior *node = new KdInterior(leaf->mParent);
304
305	const int axis = splitPlane.mAxis;
306	const float position = splitPlane.mPosition;
307
308	node->mAxis = axis;
309	node->mPosition = position;
310	node->mBox = tData.mBoundingBox;
311
312
313	//-- the front and back traversal data is filled with the new values
314
315	// bounding boxes: split front and back node geometry
316	tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition,
317	frontData.mBoundingBox, backData.mBoundingBox);
318
319	frontData.mDepth = backData.mDepth = tData.mDepth + 1;
320
321	//-- subdivide rays
322	frontData.mRays = new RayInfoContainer();
323	backData.mRays = new RayInfoContainer();
324
325	/* SplitRays(splitPlane,
326	*tData.mRays,
327	*frontData.mRays,
328	*backData.mRays);
329	*/
330
331	//-- classify objects
332
333	int objectsBack = 0;
334	int objectsFront = 0;
335
336	ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
337
338	for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi)
339	{
340	// determine the side of this ray with respect to the plane
341	const AxisAlignedBox3 box = (*mi)->GetBox();
342
343	if (box.Max(axis) >= position)
344	++ objectsFront;
345
346	if (box.Min(axis) < position)
347	++ objectsBack;
348	}
349
350
351	// TODO matt: compute pvs
352	//frontData.mPvs = objectsFront;
353	//backData.mPvs = objectsBack;
354
355	//CheckViewCellsPvs(leaf, *tData.mRays);
356	RemoveParentViewCellsPvs(leaf, *tData.mRays);
357
358
359	/////////////
360	//-- create front and back leaf
361
362	KdLeaf *back = new KdLeaf(node, objectsBack);
363	KdLeaf *front = new KdLeaf(node, objectsFront);
364
365	KdInterior *parent = leaf->mParent;
366
367	// replace a link from node's parent
368	if (parent)
369	{
370	parent->ReplaceChildLink(leaf, node);
371	node->mParent = parent;
372	}
373	else // new root
374	{
375	mRoot = node;
376	}
377
378	// and setup child links
379	node->SetupChildLinks(back, front);
380
381	SplitObjects(leaf, splitPlane, leaf->mObjects, front->mObjects, back->mObjects);
382
383	FilterRays(front, tData.mRays, frontData.mRays);
384	FilterRays(back, tData.mRays, backData.mRays);
385
386	++ mOspStats.splits[splitPlane.mAxis];
387
388	//-- eval view cells pvs
389
390	// remove parent pvs update pvs of left and right leaves
391	// Note: It is necessary to update first left and then right pvs.
392	// We need to store the view cells seen by each object,
393	// but also if the view cells are seen as part of two different
394	// kd leaves, which is stored in the pdf component of the pvs entry.
395	// Because if an object is part of a view cell more than once,
396	// it cannot be removed from the pvs by splitting a kd node where
397	// the view cell sees only the other child of the node.
398	// This is important during the subdivision
399
400	//MailablePvsData::NewMail();
401	UpdateViewCellsPvs(front, *frontData.mRays);
402	UpdateViewCellsPvs(back, *backData.mRays);
403
404	////////////////////////////////////
405
406
407	ProcessMultipleRefs(front);
408	ProcessMultipleRefs(back);
409
410	frontData.mNode = front;
411	backData.mNode = back;
412
413	// compute probability, i.e., volume of seen view cells
414	frontData.mProbability = EvalViewCellsVolume(front, *frontData.mRays);
415	backData.mProbability = EvalViewCellsVolume(back, *backData.mRays);
416
417	//delete leaf;
418	return node;
419	}
420
421
422	KdNode *OspTree::Subdivide(SplitQueue &tQueue,
423	SubdivisionCandidate *splitCandidate,
424	const bool globalCriteriaMet)
425	{
426	OspSubdivisionCandidate sc = static_cast<OspSubdivisionCandidate >(splitCandidate);
427	OspTraversalData &tData = sc->mParentData;
428
429	KdNode *newNode = tData.mNode;
430
431	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
432	{
433	OspTraversalData tFrontData;
434	OspTraversalData tBackData;
435
436	//-- continue subdivision
437
438	// create new interior node and two leaf node
439	const AxisAlignedPlane splitPlane = sc->mSplitPlane;
440
441	newNode = SubdivideNode(splitPlane,
442	tData,
443	tFrontData,
444	tBackData);
445
446	const int maxCostMisses = sc->GetMaxCostMisses();
447
448	// how often was max cost ratio missed in this branch?
449	tFrontData.mMaxCostMisses = maxCostMisses;
450	tBackData.mMaxCostMisses = maxCostMisses;
451
452	mTotalCost -= sc->GetRenderCostDecrease();
453
454	// subdivision statistics
455	if (1) EvalSubdivisionStats(*sc);
456
457	//-- push the new split candidates on the queue
458
459	OspSubdivisionCandidate *frontCandidate = new OspSubdivisionCandidate(tFrontData);
460	OspSubdivisionCandidate *backCandidate = new OspSubdivisionCandidate(tBackData);
461
462	EvalSubdivisionCandidate(*frontCandidate);
463	EvalSubdivisionCandidate(*backCandidate);
464
465	tQueue.Push(frontCandidate);
466	tQueue.Push(backCandidate);
467
468	// delete old leaf node
469	DEL_PTR(tData.mNode);
470	}
471
472
473	//-- terminate traversal
474	if (newNode->IsLeaf())
475	{
476	EvaluateLeafStats(tData);
477
478	const bool mStoreRays= true;
479
480	//-- store additional info
481	if (mStoreRays)
482	{
483	KdLeaf leaf = static_cast<KdLeaf >(newNode);
484
485	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
486
487	for (it = tData.mRays->begin(); it != it_end; ++ it)
488	{
489	(*it).mRay->Ref();
490	leaf->mVssRays.push_back((*it).mRay);
491	}
492	}
493	}
494
495	//-- cleanup
496	tData.Clear();
497
498	return newNode;
499	}
500
501
502	void OspTree::EvalSubdivisionCandidate(OspSubdivisionCandidate &splitCandidate)
503	{
504	// compute locally best split plane
505	const float ratio = SelectSplitPlane(splitCandidate.mParentData,
506	splitCandidate.mSplitPlane);
507
508	const bool success = ratio < mTermMaxCostRatio;
509	float oldRenderCost;
510
511	// compute global decrease in render cost
512	const float renderCostDecr = EvalRenderCostDecrease(splitCandidate.mSplitPlane,
513	splitCandidate.mParentData,
514	oldRenderCost);
515
516	splitCandidate.SetRenderCostDecrease(renderCostDecr);
517
518	const float pvsSizeIncr = 0; // todo
519	#if 0
520	const float priority = (float)-data.mDepth;
521	#else
522	// take render cost of node into account
523	// otherwise danger of being stuck in a local minimum!!
524	const float factor = mRenderCostDecreaseWeight;
525	const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
526
527	#endif
528
529	// compute global decrease in render cost
530	splitCandidate.SetPriority(priority);
531
532	splitCandidate.SetMaxCostMisses(success ?
533	splitCandidate.mParentData.mMaxCostMisses :
534	splitCandidate.mParentData.mMaxCostMisses + 1);
535	}
536
537
538	inline bool OspTree::LocalTerminationCriteriaMet(const OspTraversalData &data) const
539	{
540	// matt: TODO
541	return (
542	//(data.mNode->mObjects.size() < mTermMinObjects) \|\|
543	//(data.mProbability <= mTermMinProbability) \|\|
544	(data.mDepth >= mTermMaxDepth)
545	);
546	}
547
548
549	inline bool OspTree::GlobalTerminationCriteriaMet(const OspTraversalData &data) const
550	{
551	// matt: TODO
552	return (0
553	\|\| (mOspStats.Leaves() >= mTermMaxLeaves)
554	//\|\| mOutOfMemory
555	\|\| (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
556	);
557	}
558
559
560	void OspTree::EvaluateLeafStats(const OspTraversalData &data)
561	{
562	// the node became a leaf -> evaluate stats for leafs
563	KdLeaf *leaf = data.mNode;
564
565	++ mCreatedLeaves;
566
567	/*if (data.mPvs > mOspStats.maxPvs)
568	{
569	mOspStats.maxPvs = data.mPvs;
570	}
571
572	mOspStats.pvs += data.mPvs;
573
574	if (data.mDepth < mOspStats.minDepth)
575	{
576	mOspStats.minDepth = data.mDepth;
577	}*/
578
579	if (data.mDepth >= mTermMaxDepth)
580	{
581	++ mOspStats.maxDepthNodes;
582	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
583	}
584
585	if (data.mProbability <= mTermMinProbability)
586	++ mOspStats.minProbabilityNodes;
587
588	// accumulate depth to compute average depth
589	mOspStats.accumDepth += data.mDepth;
590
591	// if ((int)(leaf->mObjects.size()) < mTermMinCost)
592	// ++ mOspStats.minCostNodes;
593
594	if ((int)(leaf->mObjects.size()) > mOspStats.maxObjectRefs)
595	mOspStats.maxObjectRefs = (int)leaf->mObjects.size();
596
597	#ifdef GTP_DEBUG
598	Debug << "BSP stats: "
599	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
600	<< "Prob: " << data.mProbability << " (min: " << mTermMinProbability << ")\n";
601	#endif
602	}
603
604
605	float OspTree::EvalLocalCostHeuristics(const OspTraversalData &tData,
606	const AxisAlignedBox3 &box,
607	const int axis,
608	float &position,
609	int &objectsFront,
610	int &objectsBack)
611	{
612	RayInfoContainer usedRays;
613	int mMaxTests = 500000; // HACK
614
615	if (mMaxTests < (int)tData.mRays->size())
616	{
617	GetRayInfoSets(*tData.mRays, mMaxTests, usedRays);
618	}
619	else
620	{
621	usedRays = *tData.mRays;
622	}
623
624	// go through the lists, count the number of objects left and right
625	// and evaluate the following cost funcion:
626	// C = ct_div_ci + (ol + or)/queries
627
628	const float minBox = box.Min(axis);
629	const float maxBox = box.Max(axis);
630	Debug << "min: " << minBox << " max: " << maxBox << endl;
631
632	const float sizeBox = maxBox - minBox;
633
634	float minBand = minBox + mSplitBorder * (maxBox - minBox);
635	float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
636
637	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
638
639	//-- sort so we can use a sweep
640	SortSubdivisionCandidates(tData, axis, minBand, maxBand);
641
642	float totalVol = 0;
643	float voll = 0;
644	float volr = totalVol;
645
646	ViewCellContainer touchedViewCells;
647
648	const float totalRenderCost = PrepareHeuristics(tData, touchedViewCells);
649	float renderCost = totalRenderCost;
650
651	/// this is kind of a reverse pvs
652	const int totalPvs = (int)tData.mNode->mObjects.size();
653
654	int pvsl = 0;
655	int pvsr = totalPvs;
656
657	float sum = (float)totalVol * sizeBox;
658
659	Debug << "total render cost: " << renderCost / viewSpaceVol << endl;
660
661	/////////////////////////////////
662
663	// note: initialised to take mid split
664	// if no good split can be found,
665	position = minBox + 0.5f * sizeBox;
666
667	// the relative cost ratio
668	float ratio = 99999999.0f;
669	bool splitPlaneFound = false;
670
671	float volBack = voll;
672	float volFront = volr;
673
674	int pvsBack = pvsl;
675	int pvsFront = pvsr;
676
677	float minRenderCost = 1e20f;
678
679	debugVol = 0;
680
681
682
683	/////////////////////////////
684	// the sweep heuristics
685
686
687	//-- traverse through events and find best split plane
688
689	vector<SortableEntry>::const_iterator ci, ci_end = mSubdivisionCandidates->end();
690	//minRenderCost = RandomValue(0,viewSpaceVol);
691
692	for (ci = mSubdivisionCandidates->begin(); ci != ci_end; ++ ci)
693	{
694	Intersectable object = (ci).mObject;
695
696	EvalHeuristicsContribution(tData.mNode,
697	*ci,
698	renderCost,
699	touchedViewCells
700	);
701
702	// Note: sufficient to compare size of bounding boxes of front and back side?
703	if (((ci).mPos >= minBand) && ((ci).mPos <= maxBand))
704	{
705	float currentPos;
706	Debug << "current min: " << minRenderCost / viewSpaceVol << endl;
707
708	// HACK: current positition is BETWEEN visibility events
709	if (1 && /((ci).mType == SortableEntry::BOX_INTERSECT) &&*/ ((ci + 1) != ci_end))
710	currentPos = ((ci).mPos + ((ci + 1)).mPos) * 0.5f;
711	else
712	currentPos = (*ci).mPos;
713
714	if (renderCost < minRenderCost)
715	{
716	splitPlaneFound = true;
717	minRenderCost = renderCost;
718	position = currentPos;
719	Debug << "pos: " << position << endl;
720	}
721	}
722	}
723	//splitPlaneFound = true;
724	if (splitPlaneFound)
725	{
726	ratio = minRenderCost / totalRenderCost;
727	}
728	#if GTP_DEBUG
729	Debug << "\n§§§§ eval local cost §§§§" << endl
730	<< "old rc: " << totalRenderCost / viewSpaceVol << " new rc: " << minRenderCost / viewSpaceVol << endl
731	<< "render cost decrease: " << (totalRenderCost - minRenderCost) / viewSpaceVol << endl;
732	#endif
733	return ratio;
734	}
735
736
737	void OspTree::SortSubdivisionCandidates(const OspTraversalData &tData,
738	const int axis,
739	float minBand,
740	float maxBand)
741
742	{
743	mSubdivisionCandidates->clear();
744
745	RayInfoContainer *rays = tData.mRays;
746	KdLeaf *leaf = tData.mNode;
747
748	int requestedSize = 2 * (int)rays->size() + 2 * (int)leaf->mObjects.size();
749
750	// creates a sorted split candidates array
751	if (mSubdivisionCandidates->capacity() > 500000 &&
752	requestedSize < (int)(mSubdivisionCandidates->capacity() / 10) )
753	{
754	delete mSubdivisionCandidates;
755	mSubdivisionCandidates = new vector<SortableEntry>;
756	}
757
758	mSubdivisionCandidates->reserve(requestedSize);
759
760	float pos;
761
762	//-- insert ray queries
763	//-- we are intersested only in rays which intersect an object that
764	//-- is part of the kd node because they can induce a change in view cell
765	//-- volume on the left and the right part.
766	//-- Note that they cannot induce a change in pvs size!!
767
768	RayInfoContainer::const_iterator rit, rit_end = rays->end();
769
770	for (rit = rays->begin(); rit < rit_end; ++ rit)
771	{
772	VssRay ray = (rit).mRay;
773
774	const bool positive = ray->HasPosDir(axis);
775
776	if (EndPointInsideNode(leaf, *ray, true))
777	{
778	pos = ray->mTermination[axis];
779
780	mSubdivisionCandidates->push_back(
781	SortableEntry(SortableEntry::BOX_INTERSECT,
782	pos,
783	ray->mTerminationObject,
784	ray)
785	);
786	}
787
788	// if hitpoint with object is inside this node
789	if (EndPointInsideNode(leaf, *ray, false))
790	{
791	pos = ray->mOrigin[axis];
792
793	mSubdivisionCandidates->push_back(
794	SortableEntry(SortableEntry::BOX_INTERSECT,
795	pos,
796	ray->mOriginObject,
797	ray)
798	);
799	}
800	}
801
802
803	//-- insert object queries
804	//-- These queries can induce a change in pvs size.
805	//-- Note that they cannot induce a change in view cell volume, as
806	//-- there is no ray associated with these events!!
807
808	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
809
810	for (oit = leaf->mObjects.begin(); oit != leaf->mObjects.end(); ++ oit )
811	{
812	Intersectable object = oit;
813	const AxisAlignedBox3 box = object->GetBox();
814
815	mSubdivisionCandidates->push_back(
816	SortableEntry(SortableEntry::BOX_MIN,
817	box.Min(axis),
818	object,
819	NULL)
820	);
821
822
823	mSubdivisionCandidates->push_back(
824	SortableEntry(SortableEntry::BOX_MAX,
825	box.Max(axis),
826	object,
827	NULL)
828	);
829	}
830
831	stable_sort(mSubdivisionCandidates->begin(), mSubdivisionCandidates->end());
832	}
833
834
835	const OspTreeStatistics &OspTree::GetStatistics() const
836	{
837	return mOspStats;
838	}
839
840
841	void OspTree::PrepareHeuristics(const VssRay &ray,
842	ViewCellContainer &touchedViewCells)
843	{
844	// collect view cells and set mail + counter
845	ViewCellContainer viewCells;
846	mVspTree->GetViewCells(ray, viewCells);
847
848	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
849
850	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
851	{
852	ViewCell vc = (vit);
853
854	if (!vc->Mailed())
855	{
856	vc->Mail(); // set as belonging to front leaf
857	vc->mCounter = 0;
858	touchedViewCells.push_back(vc);
859	}
860
861	// view cell volume already added => just increase counter
862	++ vc->mCounter;
863	}
864	}
865
866
867	float OspTree::PrepareHeuristics(const OspTraversalData &tData,
868	ViewCellContainer &touchedViewCells)
869	{
870	float renderCost = 0;
871
872	Intersectable::NewMail(3);
873	ViewCell::NewMail(3);
874	MailablePvsData::NewMail();
875
876	KdLeaf *leaf = tData.mNode;
877
878	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
879
880	for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
881	{
882	VssRay ray = (rit).mRay;
883	PrepareHeuristics(*ray, touchedViewCells);
884	}
885
886	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
887
888	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
889	{
890	Intersectable obj = oit;
891	obj->Mail(); // set as belonging to front leaf
892
893	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
894
895	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
896	{
897	ViewCell vc = vit;
898	// no view cel pvs!!
899	/MailablePvsData vdata = obj->mViewCellPvs.Find(vc);
900
901	if (!vdata) // should never happen
902	continue;
903
904	if (!vdata->Mailed())
905	{
906	vdata->Mail();
907	renderCost += vc->GetVolume();
908	}*/
909	}
910	}
911
912	return renderCost;
913	}
914
915
916	void OspTree::AddObjectContribution(KdLeaf *leaf,
917	Intersectable *obj,
918	ViewCellContainer &touchedViewCells,
919	float &renderCost)
920	{
921	//Debug << "add contri to obj: " << obj->mMailbox - Intersectable::sMailId << endl;
922	obj->Mail(2); // set as belonging to both leafs
923
924	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
925
926	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
927	{
928	ViewCell vc = vit;
929
930	// if obj not previously associated with this view cell => increase render cost
931	if (vc->Mailed(1) && !ViewCellHasMultipleReferences(obj, vc, false))
932	{
933	//Debug << "add to rendercost: " << vc->GetVolume() / mVspTree->GetBoundingBox().GetVolume() << endl;
934	renderCost += vc->GetVolume();
935	}
936	}
937	}
938
939
940	void OspTree::SubtractObjectContribution(KdLeaf *leaf,
941	Intersectable * obj,
942	ViewCellContainer &touchedViewCells,
943	float &renderCost)
944	{
945	//Debug << "subtract contri from obj: " << obj->mMailbox - Intersectable::sMailId << endl;
946	obj->Mail(1); // set as belonging to back leaf
947	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
948
949	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
950	{
951	ViewCell vc = vit;
952
953	// if obj was previously associated with this view cell but is not now
954	// => decrease render cost
955	if (vc->Mailed() && !ViewCellHasMultipleReferences(obj, vc, false))
956	{
957	//Debug << "subtract from rendercost: " << vc->GetVolume() / mVspTree->GetBoundingBox().GetVolume() << endl;
958	renderCost -= vc->GetVolume();
959	}
960	}
961	}
962
963
964	void OspTree::EvalRayContribution(KdLeaf *leaf,
965	const VssRay &ray,
966	float &renderCost)
967	{
968	ViewCellContainer viewCells;
969
970	mVspTree->GetViewCells(ray, viewCells);
971
972	// classify view cells and compute volume contri accordingly
973	// possible view cell classifications:
974	// view cell mailed => view cell can be seen from left child node
975	// view cell counter > 0 view cell can be seen from right child node
976	// combined: view cell volume belongs to both nodes
977	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
978
979	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
980	{
981	EvalViewCellContribution(leaf, *vit, renderCost);
982	}
983	}
984
985
986	void OspTree::EvalViewCellContribution(KdLeaf *leaf,
987	ViewCell *viewCell,
988	float &renderCost)
989	{
990	//Debug << "**************" << endl;
991	//Debug << "vc contri: " << renderCost / mVspTree->GetBoundingBox().GetVolume() << " " << viewCell->mMailbox - ViewCell::sMailId << " counter: " << viewCell->mCounter << endl;
992
993	const float vol = viewCell->GetVolume();
994
995	if (viewCell->Mailed())
996	{
997	viewCell->Mail(2); // view cell can be seen from both nodes
998
999	// we now see view cell from both nodes => add contri
1000	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1001
1002	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1003	{
1004	Intersectable obj = oit;
1005
1006	// was render cost already added?
1007	if (!ViewCellHasMultipleReferences(obj, viewCell, false) &&
1008	obj->Mailed(1))
1009	{
1010	//Debug << "obj mail 1!! " << vol / mVspTree->GetBoundingBox().GetVolume() << endl;
1011	renderCost += vol;
1012	}
1013	}
1014	}
1015
1016	if (-- viewCell->mCounter == 0)
1017	{
1018	viewCell->Mail(1); // view cell can be seen from back node only
1019
1020	//MailablePvsData::NewMail();
1021	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1022
1023	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1024	{
1025	Intersectable obj = oit;
1026
1027	// can render cost be be reduced?
1028	if (!ViewCellHasMultipleReferences(obj, viewCell, false) && obj->Mailed())
1029	{
1030	renderCost -= vol;
1031	}
1032	}
1033	}
1034	//Debug << "new rc: " << renderCost / mVspTree->GetBoundingBox().GetVolume() << " counter2: " << viewCell->mCounter << endl;
1035	//Debug << "**************"<<endl;
1036	}
1037
1038
1039	void OspTree::EvalHeuristicsContribution(KdLeaf *leaf,
1040	const SortableEntry &ci,
1041	float &renderCost,
1042	ViewCellContainer &touchedViewCells)
1043	{
1044	Intersectable *obj = ci.mObject;
1045	VssRay *ray = ci.mRay;
1046
1047	// switch between different types of events
1048	switch (ci.mType)
1049	{
1050	case SortableEntry::BOX_MIN:
1051	cout << "<";
1052	AddObjectContribution(leaf, ci.mObject, touchedViewCells, renderCost);
1053	break;
1054
1055	case SortableEntry::BOX_MAX:
1056	cout << ">";
1057	SubtractObjectContribution(leaf, ci.mObject, touchedViewCells, renderCost);
1058	break;
1059
1060	// compute volume contribution from view cells
1061	case SortableEntry::BOX_INTERSECT:
1062	cout << "i";
1063	// process ray if the hit point with termination / origin object
1064	// is inside this kd leaf
1065	EvalRayContribution(leaf, *ray, renderCost);
1066	break;
1067
1068	default:
1069	cout << "should not come here" << endl;
1070	break;
1071	}
1072
1073	//cout << "vol left: " << volLeft << " vol right " << volRight << endl;
1074	}
1075
1076
1077	void OspTree::SetViewCellsManager(ViewCellsManager *vcm)
1078	{
1079	mViewCellsManager = vcm;
1080	}
1081
1082
1083	AxisAlignedBox3 OspTree::GetBoundingBox() const
1084	{
1085	return mBoundingBox;
1086	}
1087
1088
1089	float OspTree::SelectSplitPlane(const OspTraversalData &tData,
1090	AxisAlignedPlane &plane)
1091	{
1092	float nPosition[3];
1093	float nCostRatio[3];
1094
1095	// create bounding box of node geometry
1096	AxisAlignedBox3 box = tData.mBoundingBox;
1097
1098	int sAxis = 0;
1099	int bestAxis = -1;
1100
1101	if (mOnlyDrivingAxis)
1102	{
1103	sAxis = box.Size().DrivingAxis();
1104	}
1105
1106
1107	// -- evaluate split cost for all three axis
1108	for (int axis = 0; axis < 3; ++ axis)
1109	{
1110	if (!mOnlyDrivingAxis \|\| (axis == sAxis))
1111	{
1112	if (1 \|\| mUseCostHeuristics)
1113	{
1114	//-- place split plane using heuristics
1115	int objectsFront, objectsBack;
1116
1117	nCostRatio[axis] =
1118	EvalLocalCostHeuristics(tData,
1119	tData.mBoundingBox,
1120	axis,
1121	nPosition[axis],
1122	objectsFront,
1123	objectsBack);
1124	}
1125	/* else
1126	{
1127	//-- split plane position is spatial median
1128
1129	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1130
1131	nCostRatio[axis] = EvalLocalSplitCost(tData,
1132	box,
1133	axis,
1134	nPosition[axis],
1135	nProbFront[axis],
1136	nProbBack[axis]);
1137	}*/
1138
1139	if (bestAxis == -1)
1140	{
1141	bestAxis = axis;
1142	}
1143	else if (nCostRatio[axis] < nCostRatio[bestAxis])
1144	{
1145	bestAxis = axis;
1146	}
1147	}
1148	}
1149
1150	//-- assign values
1151
1152	plane.mAxis = bestAxis;
1153	// split plane position
1154	plane.mPosition = nPosition[bestAxis];
1155
1156	Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
1157	return nCostRatio[bestAxis];
1158	}
1159
1160
1161	bool OspTree::EndPointInsideNode(KdLeaf *leaf,
1162	VssRay &ray,
1163	bool isTermination) const
1164	{
1165	// test if the leaf where the hitpoint is located is the current leaf
1166	if (isTermination)
1167	{
1168	return ray.mTerminationObject && (GetLeaf(ray.mTermination, ray.mTerminationNode) == leaf);
1169	}
1170	else
1171	{
1172	return false; // no origin object!
1173	return ray.mOriginObject && (GetLeaf(ray.mOrigin, ray.mOriginNode) == leaf);
1174	}
1175	}
1176
1177
1178	void OspTree::EvalSubdivisionStats(const SubdivisionCandidate &sc)
1179	{
1180	const float costDecr = sc.GetRenderCostDecrease();
1181
1182	AddSubdivisionStats(mOspStats.Leaves(),
1183	costDecr,
1184	mTotalCost
1185	);
1186	}
1187
1188
1189	void OspTree::AddSubdivisionStats(const int leaves,
1190	const float renderCostDecr,
1191	const float totalRenderCost)
1192	{
1193	mSubdivisionStats
1194	<< "#Leaves\n" << leaves << endl
1195	<< "#RenderCostDecrease\n" << renderCostDecr << endl
1196	<< "#TotalRenderCost\n" << totalRenderCost << endl;
1197	//<< "#AvgRenderCost\n" << avgRenderCost << endl;
1198	}
1199
1200
1201	int OspTree::ClassifyRay(VssRay *ray,
1202	KdLeaf *leaf,
1203	const AxisAlignedPlane &plane) const
1204	{
1205	const bool originInside = EndPointInsideNode(leaf, *ray, false);
1206	const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
1207
1208	const bool originGt = (ray->mOrigin[plane.mAxis] >= plane.mPosition);
1209	const bool originLt = (ray->mOrigin[plane.mAxis] <= plane.mPosition);
1210
1211	const bool terminationGt = (ray->mTermination[plane.mAxis] >= plane.mPosition);
1212	const bool terminationLt = (ray->mTermination[plane.mAxis] <= plane.mPosition);
1213
1214	// add view cell volume to front volume
1215	const bool addToFront =
1216	((originInside && originGt) \|\| (terminationInside && terminationGt));
1217
1218	// add view cell volume to back volume
1219	const bool addToBack =
1220	((originInside && originLt/!originGt/) \|\| (terminationInside && terminationLt/terminationGt/));
1221
1222	// classify ray with respect to the child nodes the view cells contribute
1223	if (addToFront && addToBack)
1224	return 0;
1225	else if (addToBack)
1226	return -1;
1227	else if (addToFront)
1228	return 1;
1229
1230	return -2;
1231	}
1232
1233
1234	int OspTree::ClassifyRays(const RayInfoContainer &rays,
1235	KdLeaf *leaf,
1236	const AxisAlignedPlane &plane,
1237	RayInfoContainer &frontRays,
1238	RayInfoContainer &backRays) const
1239	{
1240	RayInfoContainer::const_iterator rit, rit_end = rays.end();
1241
1242	for (rit = rays.begin(); rit < rit_end; ++ rit)
1243	{
1244	VssRay ray = (rit).mRay;
1245
1246	bool originGt = false;
1247	bool terminationGt = false;
1248
1249	Intersectable *obj = ray->mOriginObject;
1250
1251	if (0 && obj)
1252	{
1253	originGt = ray->mOrigin[plane.mAxis] >= plane.mPosition;
1254	}
1255
1256	obj = ray->mTerminationObject;
1257
1258	if (obj)
1259	{
1260	terminationGt = ray->mTermination[plane.mAxis] >= plane.mPosition;
1261	}
1262
1263	// either begin or end point on front side
1264	const bool addToFront = originGt \|\| terminationGt;
1265
1266	// add view cell volume to back volume
1267	const bool addToBack = !originGt \|\| !terminationGt;
1268
1269	// classify ray with respect to the child nodes the view cells contribute
1270	if (addToFront)
1271	frontRays.push_back(*rit);
1272	if (addToBack)
1273	backRays.push_back(*rit);
1274	}
1275
1276	return 0;
1277	}
1278
1279
1280	float OspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
1281	const OspTraversalData &tData,
1282	float &normalizedOldRenderCost) const
1283	{
1284	float pvsFront = 0;
1285	float pvsBack = 0;
1286
1287	// probability that view point lies in back / front node
1288	float pOverall = 0;
1289	float pFront = 0;
1290	float pBack = 0;
1291	float pFrontAndBack = 0;
1292
1293	Intersectable::NewMail(3);
1294	KdLeaf *leaf = tData.mNode;
1295
1296	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
1297	const int totalPvs = (int)leaf->mObjects.size();
1298
1299	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1300
1301	// evaluate reverse pvs and view cell volume on left and right cell
1302	// note: should I take all leaf objects or rather the objects hit by rays?
1303	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1304	{
1305	int pvsContri = 0;
1306
1307	Intersectable obj = oit;
1308	const AxisAlignedBox3 box = obj->GetBox();
1309
1310	// test if box falls in left / right child node
1311	if (box.Max(candidatePlane.mAxis) >= candidatePlane.mPosition)
1312	{
1313	++ pvsFront;
1314	obj->Mail();
1315	}
1316
1317	if (box.Min(candidatePlane.mAxis) < candidatePlane.mPosition)
1318	{
1319	++ pvsBack;
1320
1321	if (obj->Mailed())
1322	obj->Mail(2);
1323	else
1324	obj->Mail(1);
1325	}
1326	}
1327
1328	ViewCellContainer touchedViewCells;
1329
1330	// sum up volume seen from the objects of left and right children
1331	// => the volume is the weight for the render cost equation
1332	ViewCell::NewMail(3);
1333
1334	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
1335	//map<Intersectable *, ViewCellContainer> objectsMap;
1336
1337	for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
1338	{
1339	VssRay ray = (rit).mRay;
1340
1341	// add volume to volumes of left and / or right children
1342	// if one of the ray end points is inside
1343	const int classification = ClassifyRay(ray, leaf, candidatePlane);
1344
1345	ViewCellContainer viewCells;
1346	mVspTree->GetViewCells(*ray, viewCells);
1347
1348	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1349
1350	// traverse through view cells and classify them according
1351	// to them being seen from to back / front / front and back node
1352	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1353	{
1354	ViewCell vc = vit;
1355
1356	// if not previously mailed
1357	if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
1358	{
1359	touchedViewCells.push_back(vc);
1360	}
1361
1362	// classify / mail the view cell
1363	MailViewCell(vc, classification);
1364	}
1365	}
1366
1367	// evaluate view cells volume contribution
1368	// with respect to the mail box classification
1369	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
1370
1371	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
1372	{
1373	AddViewCellVolumeContri(*vit, pFront, pBack, pFrontAndBack);
1374	}
1375
1376	//////////////////////////////////////////////
1377	//
1378	// evaluate contribution of objects which are part of other kd nodes
1379	// which are seen by the same view cell
1380	// These contributions cannot be reduced by splitting, because
1381	// the object would still be part of the pvs
1382
1383	float newRc = 0;
1384	float rc = 0;
1385
1386	MailablePvsData::NewMail();
1387	//ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1388
1389	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1390	{
1391	Intersectable obj = oit;
1392	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
1393
1394	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
1395	{
1396	ViewCell vc = vit;
1397	// no more view cell pvs!!
1398	/MailablePvsData vdata = obj->mViewCellPvs.Find(vc);
1399	if (!vdata)
1400	{
1401	Debug << "error! should not come here" << endl;
1402	continue;
1403	}
1404
1405	if (!vdata->Mailed())
1406	{
1407	vdata->Mail();
1408	rc += vc->GetVolume();
1409
1410	if ((vdata->mSumPdf > 1.5) \|\|
1411	vc->Mailed(2) \|\|
1412	obj->Mailed(2) \|\|
1413	(obj->Mailed() && vc->Mailed()) \|\|
1414	(obj->Mailed(1) && vc->Mailed(1))
1415	)
1416	{
1417	newRc += vc->GetVolume();
1418	}
1419	}*/
1420	}
1421	}
1422
1423
1424	/////////////////////////////
1425	//-- pvs rendering heuristics
1426
1427	const float oldRenderCost = rc;
1428
1429	// sum up the terms:
1430	// the view cells seeing
1431	// a) the left node are weighted by the #left node objects
1432	// b) the right node are weighted by the #right node objects
1433	// c) both nodes are weighted by the #parent node objects
1434	const float newRenderCost = newRc;
1435
1436
1437	// normalize volume with view space volume
1438	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
1439
1440	Debug << "\nrender cost decrease: " << endl
1441	<< "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
1442	<< "render cost decrease: " << renderCostDecrease << endl;
1443
1444	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
1445
1446
1447	return renderCostDecrease;
1448	}
1449
1450
1451	void OspTree::ComputeBoundingBox(const ObjectContainer &objects)
1452	{
1453	mBoundingBox.Initialize();
1454
1455	ObjectContainer::const_iterator oit, oit_end = objects.end();
1456
1457	//-- compute bounding box
1458	for (oit = objects.begin(); oit != oit_end; ++ oit)
1459	{
1460	Intersectable obj = oit;
1461
1462	// compute bounding box of view space
1463	mBoundingBox.Include(obj->GetBox());
1464	}
1465	}
1466
1467
1468	void OspTree::ProcessMultipleRefs(KdLeaf *leaf) const
1469	{
1470	// find objects from multiple kd-leaves
1471	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1472
1473	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1474	{
1475	Intersectable object = oit;
1476
1477	// matt: no more ref
1478	/*if (object->mReferences > 1)
1479	{
1480	leaf->mMultipleObjects.push_back(object);
1481	}*/
1482	}
1483	}
1484
1485
1486	void OspTree::CollectLeaves(vector<KdLeaf *> &leaves) const
1487	{
1488	stack<KdNode *> nodeStack;
1489	nodeStack.push(mRoot);
1490
1491	while (!nodeStack.empty())
1492	{
1493	KdNode *node = nodeStack.top();
1494	nodeStack.pop();
1495	if (node->IsLeaf())
1496	{
1497	KdLeaf leaf = (KdLeaf )node;
1498	leaves.push_back(leaf);
1499	}
1500	else
1501	{
1502	KdInterior interior = (KdInterior )node;
1503	nodeStack.push(interior->mBack);
1504	nodeStack.push(interior->mFront);
1505	}
1506	}
1507	}
1508
1509
1510	AxisAlignedBox3 OspTree::GetBoundingBox(KdNode *node) const
1511	{
1512	if (!node->mParent)
1513	return mBoundingBox;
1514
1515	if (!node->IsLeaf())
1516	{
1517	return (static_cast<KdInterior *>(node))->mBox;
1518	}
1519
1520	KdInterior parent = static_cast<KdInterior >(node->mParent);
1521
1522	AxisAlignedBox3 box(parent->mBox);
1523
1524	if (parent->mFront == node)
1525	box.SetMin(parent->mAxis, parent->mPosition);
1526	else
1527	box.SetMax(parent->mAxis, parent->mPosition);
1528
1529	return box;
1530	}
1531
1532
1533	void OspTree::CollectViewCells(KdLeaf *leaf, ViewCellContainer &viewCells)
1534	{
1535	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1536
1537	ViewCell::NewMail();
1538
1539	// loop through all object and collect view cell pvs of this node
1540	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1541	{
1542	Intersectable obj = oit;
1543	// no more view cell pvs!!
1544	/*ViewCellPvsMap::const_iterator vit, vit_end = obj->mViewCellPvs.mEntries.end();
1545
1546	for (vit = obj->mViewCellPvs.mEntries.begin(); vit != vit_end; ++ vit)
1547	{
1548	ViewCell vc = (vit).first;
1549
1550	if (!vc->Mailed())
1551	{
1552	vc->Mail();
1553	viewCells.push_back(vc);
1554	}
1555	}*/
1556	}
1557	}
1558
1559
1560	void OspTree::CollectDirtyCandidates(OspSubdivisionCandidate *sc,
1561	vector<SubdivisionCandidate *> &dirtyList,
1562	const bool onlyUnmailed)
1563	{
1564	OspTraversalData &tData = sc->mParentData;
1565	KdLeaf *node = tData.mNode;
1566
1567	ViewCell::NewMail();
1568	ViewCellContainer viewCells;
1569	ViewCellContainer tmpViewCells;
1570
1571	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
1572
1573	// find all view cells associated with the rays, add them to view cells
1574	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
1575	{
1576	VssRay ray = (rit).mRay;
1577	mVspTree->GetViewCells(*ray, tmpViewCells);
1578
1579	ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1580
1581	for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1582	{
1583	VspViewCell vc = static_cast<VspViewCell >(*vit);
1584
1585	if (!vc->Mailed())
1586	{
1587	vc->Mail();
1588	viewCells.push_back(vc);
1589	}
1590	}
1591	}
1592
1593	// candidates that contain this view cells are thrown into dirty list
1594	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1595
1596	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1597	{
1598	VspViewCell vc = static_cast<VspViewCell >(*vit);
1599
1600	VspLeaf *leaf = vc->mLeaves[0];
1601
1602	SubdivisionCandidate *dsc = leaf->GetSubdivisionCandidate();
1603	if (dsc && (!onlyUnmailed \|\| !dsc->Mailed()))
1604	{
1605	dsc->Mail();
1606	dirtyList.push_back(dsc);
1607	}
1608	}
1609	}
1610
1611
1612	KdNode *OspTree::GetRoot() const
1613	{
1614	return mRoot;
1615	}
1616
1617
1618	KdLeaf OspTree::GetLeaf(const Vector3 &pt, KdNode node) const
1619	{
1620	// start from root of tree
1621	if (node == NULL)
1622	{
1623	node = mRoot;
1624	}
1625
1626	stack<KdNode *> nodeStack;
1627	nodeStack.push(node);
1628
1629	KdLeaf *leaf = NULL;
1630
1631	while (!nodeStack.empty())
1632	{
1633	KdNode *node = nodeStack.top();
1634	nodeStack.pop();
1635
1636	if (node->IsLeaf())
1637	{
1638	leaf = static_cast<KdLeaf *>(node);
1639	}
1640	else
1641	{
1642	// find point
1643	KdInterior interior = static_cast<KdInterior >(node);
1644
1645	if (interior->mPosition > pt[interior->mAxis])
1646	{
1647	nodeStack.push(interior->mBack);
1648	}
1649	else
1650	{
1651	nodeStack.push(interior->mFront);
1652	}
1653	}
1654	}
1655
1656	return leaf;
1657	}
1658
1659
1660	void OspTree::PreprocessRays(KdLeaf *root,
1661	const VssRayContainer &sampleRays,
1662	RayInfoContainer &rays)
1663	{
1664	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
1665	RayInfoContainer clippedRays;
1666
1667	long startTime = GetTime();
1668
1669	cout << "storing rays ... ";
1670
1671	Intersectable::NewMail();
1672
1673	//-- store rays and objects
1674	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
1675	{
1676	VssRay ray = rit;
1677
1678	float minT, maxT;
1679	static Ray hray;
1680
1681	hray.Init(*ray);
1682
1683	// TODO: not very efficient to implictly cast between rays types
1684	if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
1685	{
1686	float len = ray->Length();
1687	if (!len)
1688	len = Limits::Small;
1689
1690	clippedRays.push_back(RayInfo(ray, minT / len, maxT / len));
1691
1692	// HACK: reset nodes for the case we have used object kd tree for
1693	// tree building.
1694	ray->mOriginNode = NULL;
1695	ray->mTerminationNode = NULL;
1696	}
1697	}
1698
1699	FilterRays(root, clippedRays, rays);
1700
1701	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1702	}
1703
1704
1705
1706	int OspTree::SplitRays(const AxisAlignedPlane &plane,
1707	RayInfoContainer &rays,
1708	RayInfoContainer &frontRays,
1709	RayInfoContainer &backRays) const
1710	{
1711	int splits = 0;
1712
1713	RayInfoContainer::const_iterator rit, rit_end = rays.end();
1714
1715	for (rit = rays.begin(); rit != rit_end; ++ rit)
1716	{
1717	RayInfo bRay = *rit;
1718
1719	VssRay *ray = bRay.mRay;
1720	float t;
1721
1722	// get classification and receive new t
1723	//-- test if start point behind or in front of plane
1724	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
1725
1726	if (side == 0)
1727	{
1728	++ splits;
1729
1730	if (ray->HasPosDir(plane.mAxis))
1731	{
1732	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1733	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1734	}
1735	else
1736	{
1737	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1738	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1739	}
1740	}
1741	else if (side == 1)
1742	{
1743	frontRays.push_back(bRay);
1744	}
1745	else
1746	{
1747	backRays.push_back(bRay);
1748	}
1749	}
1750
1751	return splits;
1752	}
1753
1754
1755	int OspTree::FilterRays(KdLeaf *leaf,
1756	const RayInfoContainer &rays,
1757	RayInfoContainer &filteredRays)
1758	{
1759	RayInfoContainer::const_iterator rit, rit_end = rays.end();
1760
1761	for (rit = rays.begin(); rit != rit_end; ++ rit)
1762	{
1763	VssRay ray = (rit).mRay;
1764
1765	// test if intersection point with one of the objects is inside this node
1766	const bool originInside = EndPointInsideNode(leaf, *ray, false);
1767	const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
1768
1769	if (originInside \|\| terminationInside)
1770	{
1771	filteredRays.push_back(ray);
1772	}
1773	}
1774
1775	return 0;
1776	}
1777
1778
1779	int OspTree::CheckViewCellsPvs(KdLeaf *leaf,
1780	const RayInfoContainer &rays) const
1781	{
1782	RayInfoContainer::const_iterator rit, rit_end = rays.end();
1783
1784	Intersectable::NewMail();
1785	ObjectContainer touchedObjects;
1786
1787
1788	for (rit = rays.begin(); rit < rit_end; ++ rit)
1789	{
1790	VssRay ray = (rit).mRay;
1791
1792	if (ray->mTerminationObject)
1793	{
1794	Intersectable *obj = ray->mTerminationObject;
1795
1796	if (!obj->Mailed())
1797	{
1798	obj->Mail();
1799	touchedObjects.push_back(obj);
1800	}
1801	}
1802
1803	if (ray->mOriginObject)
1804	{
1805	Intersectable *obj = ray->mOriginObject;
1806
1807	if (!obj->Mailed())
1808	{
1809	obj->Mail();
1810	touchedObjects.push_back(obj);
1811	}
1812	}
1813	}
1814	Debug << "touched view cells: " << (int)touchedObjects.size() << endl;
1815	ObjectContainer::const_iterator it, it_end = touchedObjects.end();
1816	for (it = touchedObjects.begin(); it != it_end; ++ it)
1817	{
1818	// no more view cell pvs!!
1819	/Debug << "\nobj: " << (it) << " vc pvs size: " << (*it)->mViewCellPvs.GetSize() << endl << endl;
1820	ViewCellPvsMap::const_iterator mit, mit_end = (*it)->mViewCellPvs.mEntries.end();
1821
1822	for (mit = (*it)->mViewCellPvs.mEntries.begin(); mit != mit_end; ++ mit)
1823	{
1824	Debug << "new sumpdf: " << (*mit).second.mSumPdf << endl;
1825	}*/
1826	}
1827
1828	return 0;
1829	}
1830
1831
1832	KdIntersectable OspTree::GetOrCreateKdIntersectable(KdNode node)
1833	{
1834	//if (!node) return NULL;
1835
1836	// search nodes
1837	std::map<KdNode , KdIntersectable >::const_iterator it = mKdIntersectables.find(node);
1838
1839	if (it != mKdIntersectables.end())
1840	{
1841	return (*it).second;
1842	}
1843
1844	// not in map => create new entry
1845	KdIntersectable *kdObj = new KdIntersectable(node, GetBoundingBox(node));
1846	mKdIntersectables[node] = kdObj;
1847
1848	return kdObj;
1849	}
1850
1851
1852	/*
1853	void OspTree::AddViewCellVolume(ViewCell *vc,
1854	const int cf,
1855	float &frontVol,
1856	float &backVol,
1857	float &totalVol) const
1858	{
1859	//const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
1860	const float vol = vc->GetVolume();
1861
1862	// view cell not found yet => new
1863	if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
1864	{
1865	totalVol += vol;
1866	}
1867
1868	if (cf >= 0) // front volume
1869	{
1870	if (!vc->Mailed() && !vc->Mailed(2))
1871	{
1872	frontVol += vol;
1873
1874	// already in back volume => in both volumes
1875	if (vc->Mailed(1))
1876	vc->Mail(2);
1877	else
1878	vc->Mail();
1879	}
1880	}
1881
1882	if (cf <= 0) // back volume
1883	{
1884	if (!vc->Mailed(1) && !vc->Mailed(2))
1885	{
1886	backVol += vol;
1887
1888	// already in front volume => in both volume
1889	if (vc->Mailed())
1890	vc->Mail(2);
1891	else
1892	vc->Mail(1);
1893	}
1894	}
1895	}
1896	*/
1897
1898
1899	void OspTree::MailViewCell(ViewCell *vc, const int cf) const
1900	{
1901	if (vc->Mailed(2)) // already classified
1902	return;
1903
1904	if (cf >= 0) // front volume
1905	{
1906	// already in back volume => in both volumes
1907	if (vc->Mailed(1))
1908	{
1909	vc->Mail(2);
1910	}
1911	else
1912	{
1913	vc->Mail();
1914	}
1915	}
1916
1917	if (cf <= 0) // back volume
1918	{
1919	// already in front volume => in both volume
1920	if (vc->Mailed())
1921	{
1922	vc->Mail(2);
1923	}
1924	else
1925	{
1926	vc->Mail(1);
1927	}
1928	}
1929	}
1930
1931
1932	void OspTree::AddViewCellVolumeContri(ViewCell *vc,
1933	float &frontVol,
1934	float &backVol,
1935	float &frontAndBackVol) const
1936	{
1937	if (vc->Mailed())
1938	{
1939	frontVol += vc->GetVolume();
1940	}
1941	else if (vc->Mailed(1))
1942	{
1943	backVol += vc->GetVolume();
1944	}
1945	else if (vc->Mailed(2))
1946	{
1947	frontAndBackVol += vc->GetVolume();
1948	}
1949	}
1950
1951
1952	float OspTree::EvalViewCellsVolume(KdLeaf *leaf,
1953	const RayInfoContainer &rays) const
1954	{
1955	float vol = 0;
1956	ViewCell::NewMail();
1957
1958	RayInfoContainer::const_iterator rit, rit_end = rays.end();
1959
1960	for (rit = rays.begin(); rit != rays.end(); ++ rit)
1961	{
1962	VssRay ray = (rit).mRay;
1963
1964	ViewCellContainer viewCells;
1965	mVspTree->GetViewCells(*ray, viewCells);
1966
1967	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1968
1969	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1970	{
1971	ViewCell vc = vit;
1972
1973	if (!vc->Mailed())
1974	{
1975	vc->Mail();
1976	vol += vc->GetVolume();
1977	}
1978	}
1979	}
1980
1981	return vol;
1982	}
1983
1984
1985	bool OspTree::AddViewCellToObjectPvs(Intersectable *obj,
1986	ViewCell *vc,
1987	float &contribution,
1988	bool onlyUnmailed) const
1989	{
1990	contribution = 0; // todo
1991
1992	// no more view cell pvs!!
1993	/MailablePvsData vdata = obj->mViewCellPvs.Find(vc);
1994	if (!vdata)
1995	{
1996	vdata = obj->mViewCellPvs.AddSample2(vc, 1);
1997	}
1998	else if (!onlyUnmailed \|\| !vdata->Mailed())
1999	{
2000	obj->mViewCellPvs.AddSample(vc, 1);
2001	}
2002
2003	vdata->Mail();
2004	*/
2005
2006	return true;
2007	}
2008
2009
2010	void OspTree::CollectTouchedViewCells(const RayInfoContainer &rays,
2011	ViewCellContainer &touchedViewCells) const
2012	{
2013	ViewCell::NewMail();
2014
2015	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2016
2017	for (rit = rays.begin(); rit != rit_end; ++ rit)
2018	{
2019	VssRay ray = (rit).mRay;
2020
2021	ViewCellContainer viewCells;
2022	mVspTree->GetViewCells(*ray, viewCells);
2023
2024	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2025
2026	// traverse through view cells and classify them according
2027	// to them being seen from to back / front / front and back node
2028	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2029	{
2030	ViewCell vc = vit;
2031	if (!vc->Mailed())
2032	{
2033	vc->Mail();
2034	touchedViewCells.push_back(vc);
2035	}
2036	}
2037	}
2038	}
2039
2040
2041	int OspTree::UpdateViewCellsPvs(KdLeaf *leaf,
2042	const RayInfoContainer &rays) const
2043
2044	{
2045	MailablePvsData::NewMail();
2046
2047	ViewCellContainer touchedViewCells;
2048	CollectTouchedViewCells(rays, touchedViewCells);
2049
2050	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2051
2052	for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
2053	{
2054	Intersectable obj = oit;
2055	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
2056
2057	// traverse through view cells and classify them according
2058	// to them being seen from to back / front / front and back node
2059	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2060	{
2061	ViewCell vc = vit;
2062	float contri;
2063	AddViewCellToObjectPvs(obj, vc, contri, true);
2064	}
2065	}
2066
2067	return 0;
2068	}
2069
2070
2071	int OspTree::RemoveParentViewCellsPvs(KdLeaf *leaf,
2072	const RayInfoContainer &rays
2073	) const
2074
2075	{
2076	MailablePvsData::NewMail();
2077
2078	ViewCellContainer touchedViewCells;
2079	CollectTouchedViewCells(rays, touchedViewCells);
2080
2081	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2082
2083	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
2084	{
2085	Intersectable obj = oit;
2086
2087	// traverse through view cells and classify them according
2088	// to them being seen from to back / front / front and back node
2089	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
2090
2091	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2092	{
2093	ViewCell vc = vit;
2094
2095	/MailablePvsData vdata = obj->mViewCellPvs.Find(vc);
2096
2097	if (vdata && !vdata->Mailed())
2098	{
2099	vdata->Mail();
2100	obj->mViewCellPvs.RemoveSample(vc, 1);
2101	}*/
2102	}
2103	}
2104
2105	return 0;
2106	}
2107
2108
2109	float OspTree::EvalRenderCost(const VssRayContainer &myrays)
2110	{
2111	float rc = 0;
2112	float prop = mVspTree->GetBoundingBox().GetVolume();
2113
2114	KdLeafContainer leaves;
2115	CollectLeaves(leaves);
2116
2117	ViewCellContainer vcleaves;
2118	mVspTree->CollectViewCells(vcleaves, false);
2119
2120
2121	ViewCellContainer::const_iterator vit, vit_end = vcleaves.end();
2122
2123	for (vit = vcleaves.begin(); vit != vit_end; ++ vit)
2124	{
2125	ViewCell vc = vit;
2126	vc->GetPvs().Clear();
2127	}
2128
2129	KdLeafContainer::const_iterator kit, kit_end = leaves.end();
2130
2131	MailablePvsData::NewMail();
2132
2133	for (kit = leaves.begin(); kit != kit_end; ++ kit)
2134	{
2135	KdLeaf leaf = kit;
2136	float newCost = 0;
2137	float vol = 0;
2138
2139	ViewCell::NewMail();
2140	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
2141	ViewCellContainer touchedViewCells;
2142
2143	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
2144	{
2145	VssRay ray = rit;
2146
2147	// test if intersection point with one of the objects is inside this node
2148	const bool originInside = EndPointInsideNode(leaf, *ray, false);
2149	const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
2150
2151	if (originInside \|\| terminationInside)
2152	{
2153	ViewCellContainer viewCells;
2154	mVspTree->GetViewCells(*ray, viewCells);
2155
2156	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2157
2158	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2159	{
2160	ViewCell vc = vit;
2161
2162	// if not previously mailed
2163	if (!vc->Mailed())
2164	{
2165	vc->Mail();
2166	touchedViewCells.push_back(vc);
2167	}
2168
2169	}
2170	}
2171	}
2172
2173	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2174
2175	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
2176	{
2177	Intersectable obj = oit;
2178	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
2179
2180	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2181	{
2182	ViewCell vc = vit;
2183	/PvsData vdata = vc->GetPvs().Find(obj);
2184
2185	if (!vdata)
2186	{
2187	vc->GetPvs().AddSample(obj, 1);
2188	newCost += vc->GetVolume();
2189	}
2190
2191	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
2192
2193	if (!vdata \|\| !vdata->Mailed())
2194	{
2195	newCost += vc->GetVolume();
2196	if (!vdata)
2197	vdata = obj->mViewCellPvs.AddSample2(vc, 1);
2198	vdata->Mail();
2199	}*/
2200	}
2201	}
2202
2203	rc += newCost;
2204	}
2205
2206	return rc / prop;
2207	}
2208
2209
2210	float OspTree::EvalLeafCost(const OspTraversalData &tData)
2211	{
2212	KdLeaf *leaf = tData.mNode;
2213
2214	float rc = 0;
2215	//float prop = mVspTree->GetBoundingBox().GetVolume();
2216	//float vol = 0;
2217	//ViewCell::NewMail();
2218
2219	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
2220	ViewCellContainer touchedViewCells;
2221
2222	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
2223	{
2224	VssRay ray = (rit).mRay;
2225
2226	// test if intersection point with one of the objects is inside this node
2227
2228	ViewCellContainer viewCells;
2229	mVspTree->GetViewCells(*ray, viewCells);
2230
2231	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2232
2233	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2234	{
2235	ViewCell vc = vit;
2236
2237	// if not previously mailed
2238	if (!vc->Mailed())
2239	{
2240	vc->Mail();
2241	touchedViewCells.push_back(vc);
2242	}
2243	}
2244	}
2245
2246	// clear pvs of involved view cells
2247	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
2248
2249	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2250	{
2251	ViewCell vc = vit;
2252	vc->GetPvs().Clear();
2253	}
2254
2255	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2256
2257	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
2258	{
2259	Intersectable obj = oit;
2260
2261	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2262	{
2263	ViewCell vc = vit;
2264	/PvsData vdata = vc->GetPvs().Find(obj);
2265
2266	if (!vdata)
2267	{
2268	vc->GetPvs().AddSample(obj, 1);
2269	rc += vc->GetVolume();
2270	}
2271	*/
2272	}
2273	}
2274
2275	return rc;
2276	}
2277
2278
2279	bool OspTree::Export(OUT_STREAM &stream)
2280	{
2281	ExportNode(mRoot, stream);
2282
2283	return true;
2284	}
2285
2286
2287	void OspTree::ExportNode(KdNode *node, OUT_STREAM &stream)
2288	{
2289	if (node->IsLeaf())
2290	{
2291	KdLeaf leaf = static_cast<KdLeaf >(node);
2292
2293	stream << "<Leaf ";
2294	stream << "objects=\"";
2295
2296	// export objects in kd leaves
2297	//if (mExportObjects) ExportObjects(leaf, stream);
2298
2299	stream << "\" />" << endl;
2300	}
2301	else
2302	{
2303	KdInterior interior = static_cast<KdInterior >(node);
2304
2305	stream << "<Interior plane=\"" << interior->mPosition << " "
2306	<< interior->mAxis << "\">" << endl;
2307
2308	ExportNode(interior->mBack, stream);
2309	ExportNode(interior->mFront, stream);
2310
2311	stream << "</Interior>" << endl;
2312	}
2313	}
2314
2315
2316	struct KdObjectsTraversalData
2317	{
2318	KdNode *node;
2319	ObjectContainer *objects;
2320	};
2321
2322
2323	void OspTree::InsertObjects(KdNode *node, const ObjectContainer &objects)
2324	{
2325	stack<KdObjectsTraversalData> tStack;
2326
2327	while (!tStack.empty())
2328	{
2329	KdObjectsTraversalData tData = tStack.top();
2330	tStack.pop();
2331
2332	KdNode *node = tData.node;
2333
2334	if (node->IsLeaf())
2335	{
2336	KdLeaf leaf = static_cast<KdLeaf >(node);
2337
2338	ObjectContainer::const_iterator oit, oit_end = tData.objects->end();
2339
2340	for (oit = tData.objects->begin(); oit != oit_end; ++ oit)
2341	{
2342	leaf->mObjects.push_back(*oit);
2343	}
2344	}
2345	else // interior
2346	{
2347	KdObjectsTraversalData frontData, backData;
2348	KdInterior interior = static_cast<KdInterior >(node);
2349
2350	frontData.objects = new ObjectContainer();
2351	backData.objects = new ObjectContainer();
2352
2353	ObjectContainer::const_iterator oit, oit_end = tData.objects->end();
2354
2355	for (oit = tData.objects->begin(); oit != oit_end; ++ oit)
2356	{
2357	Intersectable object = oit;
2358
2359	// determine the side of this ray with respect to the plane
2360	const AxisAlignedBox3 box = object->GetBox();
2361
2362	if (box.Max(interior->mAxis) >= interior->mPosition)
2363	{
2364	frontData.objects->push_back(object);
2365	}
2366
2367	if (box.Min(interior->mAxis) < interior->mPosition)
2368	{
2369	backData.objects->push_back(object);
2370	}
2371	}
2372
2373	tStack.push(backData);
2374	tStack.push(frontData);
2375	}
2376
2377	DEL_PTR(tData.objects);
2378	}
2379	}
2380
2381
2382	void OspTree::PrepareConstruction(SplitQueue &tQueue,
2383	const VssRayContainer &sampleRays,
2384	const ObjectContainer &objects,
2385	RayInfoContainer &rays)
2386	{
2387	// store pointer to this tree
2388	OspSubdivisionCandidate::sOspTree = this;
2389	mOspStats.nodes = 1;
2390
2391	// compute bounding box from objects
2392	ComputeBoundingBox(objects);
2393
2394	mTermMinProbability *= mBoundingBox.GetVolume();
2395	mGlobalCostMisses = 0;
2396
2397	//-- create new root
2398	KdLeaf *kdleaf = new KdLeaf(NULL, 0);
2399	kdleaf->mObjects = objects;
2400	mRoot = kdleaf;
2401
2402	// get clipped rays
2403	PreprocessRays(kdleaf, sampleRays, rays);
2404
2405	// probabilty is voume of all "seen" view cells
2406	#if 1
2407	const float prop = EvalViewCellsVolume(kdleaf, rays);
2408	#else
2409	const float prop = GetBoundingBox().GetVolume();
2410	#endif
2411
2412	//-- add first candidate for object space partition
2413
2414	// create osp traversal data
2415	OspTraversalData oData(kdleaf, 0, &rays, 0, prop, mBoundingBox);
2416
2417	//-- first split candidate
2418	OspSubdivisionCandidate *oSubdivisionCandidate =
2419	new OspSubdivisionCandidate(oData);
2420
2421	UpdateViewCellsPvs(kdleaf, rays);
2422
2423	EvalSubdivisionCandidate(*oSubdivisionCandidate);
2424
2425	mTotalCost = (float)objects.size() * prop /
2426	mVspTree->GetBoundingBox().GetVolume();
2427
2428	EvalSubdivisionStats(*oSubdivisionCandidate);
2429
2430	tQueue.Push(oSubdivisionCandidate);
2431	}
2432
2433
2434	bool OspTree::AddLeafToPvs(KdLeaf *leaf,
2435	ViewCell *vc,
2436	const float pdf,
2437	float &contribution)
2438	{
2439	// add kd intersecable to pvs
2440	KdIntersectable *kdObj = GetOrCreateKdIntersectable(leaf);
2441
2442	return vc->AddPvsSample(kdObj, pdf, contribution);
2443	}
2444
2445
2446	}

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

Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/OspTree.cpp @ 2542

Download in other formats: