Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp @ 344

Revision 344, 18.7 KB checked in by mattausch, 19 years ago (diff)

Line
1	#include "SceneGraph.h"
2	#include "KdTree.h"
3	#include "SamplingPreprocessor.h"
4	#include "X3dExporter.h"
5	#include "Environment.h"
6	#include "MutualVisibility.h"
7	#include "Polygon3.h"
8	#include "ViewCell.h"
9
10	SamplingPreprocessor::SamplingPreprocessor(): mPass(0), mSampleRays(NULL)
11	{
12	// this should increase coherence of the samples
13	environment->GetIntValue("Sampling.samplesPerPass", mSamplesPerPass);
14	environment->GetIntValue("Sampling.totalSamples", mTotalSamples);
15	environment->GetIntValue("BspTree.Construction.samples", mBspConstructionSamples);
16
17	mKdPvsDepth = 100;
18	mStats.open("stats.log");
19
20	}
21
22	SamplingPreprocessor::~SamplingPreprocessor()
23	{
24	CLEAR_CONTAINER(mSampleRays);
25	}
26
27	void
28	SamplingPreprocessor::SetupRay(Ray &ray,
29	const Vector3 &point,
30	const Vector3 &direction,
31	const int type)
32	{
33	ray.intersections.clear();
34	ray.leaves.clear();
35	ray.meshes.clear();
36	ray.viewCells.clear();
37
38	// cout<<point<<" "<<direction<<endl;
39	ray.Init(point, direction, type);
40	}
41
42	KdNode *
43	SamplingPreprocessor::GetNodeForPvs(KdLeaf *leaf)
44	{
45	KdNode *node = leaf;
46	while (node->mParent && node->mDepth > mKdPvsDepth)
47	node = node->mParent;
48	return node;
49	}
50
51	bool
52	SamplingPreprocessor::BuildBspTree()
53	{
54	// delete old tree
55	DEL_PTR(mBspTree);
56	mBspTree = new BspTree(&mUnbounded);
57
58	ObjectContainer objects;
59	int prunedCells = 0;
60	switch (BspTree::sConstructionMethod)
61	{
62	case BspTree::FROM_INPUT_VIEW_CELLS:
63	mBspTree->SetGenerateViewCells(false);
64	mBspTree->Construct(mViewCells);
65	break;
66	case BspTree::FROM_SCENE_GEOMETRY:
67	DeleteViewCells(); // we generate new view cells
68	mBspTree->SetGenerateViewCells(true);
69	mSceneGraph->CollectObjects(&objects);
70	mBspTree->Construct(objects);
71
72	mBspTree->CollectViewCells(mViewCells);
73	break;
74	case BspTree::FROM_RAYS:
75	DeleteViewCells(); // we generate new view cells
76	mBspTree->SetGenerateViewCells(true);
77	mBspTree->Construct(mSampleRays);
78	// prunedCells = mBspTree->MergeViewCells();
79
80	mBspTree->CollectViewCells(mViewCells);
81
82	// Debug << "Collected " << (int)mViewCells.size() << " cells (" << prunedCells << " pruned)" << endl;
83	break;
84	default:
85	Debug << "Error: Method not available\n";
86	break;
87	}
88
89
90	return true;
91	}
92
93	int
94	SamplingPreprocessor::AddNodeSamples(Intersectable *object,
95	const Ray &ray
96	)
97	{
98	int contributingSamples = 0;
99	int j;
100	for (j=0; j < ray.leaves.size(); j++) {
101	KdNode *node = GetNodeForPvs( ray.leaves[j] );
102	contributingSamples += object->mKdPvs.AddSample(node);
103	}
104
105	if (mPass > 10)
106	for (j=1; j < ((int)ray.leaves.size() - 1); j++) {
107	ray.leaves[j]->AddPassingRay(ray, contributingSamples ? 1 : 0);
108	}
109
110	return contributingSamples;
111	}
112
113
114	int SamplingPreprocessor::AddObjectSamples(Intersectable *obj, const Ray &ray)
115	{
116	int contributingSamples = 0;
117	int j;
118
119	// object can be seen from the view cell => add to view cell pvs
120	for (j=0; j < ray.viewCells.size(); ++ j)
121	{ // if ray not in unbounded space
122	if (ray.viewCells[j] != &mUnbounded)
123	contributingSamples += ray.viewCells[j]->GetPvs().AddSample(obj);
124	}
125
126	// rays passing through this viewcell
127	if (mPass > 1)
128	for (j=1; j < ((int)ray.viewCells.size() - 1); ++ j)
129	{
130	if (ray.viewCells[j] != &mUnbounded)
131	ray.viewCells[j]->AddPassingRay(ray, contributingSamples ? 1 : 0);
132	}
133
134	return contributingSamples;
135	}
136
137
138	void
139	SamplingPreprocessor::HoleSamplingPass()
140	{
141	vector<KdLeaf *> leaves;
142	mKdTree->CollectLeaves(leaves);
143
144	// go through all the leaves and evaluate their passing contribution
145	for (int i=0 ; i < leaves.size(); i++) {
146	KdLeaf *leaf = leaves[i];
147	cout<<leaf->mPassingRays<<endl;
148	}
149	}
150
151
152	int
153	SamplingPreprocessor::CastRay(Intersectable *object,
154	Ray &ray)
155	{
156	int sampleContributions = 0;
157
158	long t1 = GetRealTime();
159	// cast ray to KD tree to find intersection with other objects
160	mKdTree->CastRay(ray);
161	long t2 = GetRealTime();
162
163	if (0 && object->GetId() > 2197) {
164	object->Describe(cout)<<endl;
165	cout<<ray<<endl;
166	}
167
168	// cout<<object->GetId()<<" "<<TimeDiff(t1, t2)<<endl;
169
170	if (mViewCellsType == BSP_VIEW_CELLS)
171	{
172	// cast ray to BSP tree to get intersection with view cells
173	if (mBspTree)
174	{
175	mBspTree->CastRay(ray);
176
177	sampleContributions += AddObjectSamples(object, ray);
178
179	if (!ray.intersections.empty()) // second intersection found
180	{
181	sampleContributions +=
182	AddObjectSamples(ray.intersections[0].mObject, ray);
183	}
184	}
185	}
186	else
187	{
188	if (ray.leaves.size()) {
189	sampleContributions += AddNodeSamples(object, ray);
190
191	if (ray.intersections.size()) {
192	sampleContributions += AddNodeSamples(ray.intersections[0].mObject, ray);
193	}
194	}
195	}
196
197	return sampleContributions;
198	}
199
200	// void
201	// SamplingPreprocessor::AvsGenerateRandomRay(Ray &ray)
202	// {
203	// int objId = RandomValue(0, mObjects.size());
204	// Intersectable *object = objects[objId];
205	// object->GetRandomSurfacePoint(point, normal);
206	// direction = UniformRandomVector(normal);
207	// SetupRay(ray, point, direction);
208	// }
209
210	// void
211	// SamplingPreprocessor::AvsHandleRay(Ray &ray)
212	// {
213	// int sampleContributions = 0;
214
215	// mKdTree->CastRay(ray);
216
217	// if (ray.leaves.size()) {
218	// sampleContributions += AddNodeSamples(object, ray, pass);
219
220	// if (ray.intersections.size()) {
221	// sampleContributions += AddNodeSamples(ray.intersections[0].mObject, ray, pass);
222	// }
223	// }
224	// }
225
226	// void
227	// SamplingPreprocessor::AvsBorderSampling(Ray &ray)
228	// {
229
230
231	// }
232
233	// void
234	// SamplingPreprocessor::AvsPass()
235	// {
236	// Ray ray;
237	// while (1) {
238	// AvsGenerateRay(ray);
239	// HandleRay(ray);
240	// while ( !mRayQueue.empty() ) {
241	// Ray ray = mRayQueue.pop();
242	// mRayQueue.pop();
243	// AdaptiveBorderSampling(ray);
244	// }
245	// }
246
247
248
249	// }
250
251
252	int
253	SamplingPreprocessor::CastEdgeSamples(
254	Intersectable *object,
255	const Vector3 &point,
256	MeshInstance *mi,
257	const int samples
258	)
259	{
260	Ray ray;
261	int maxTries = samples*10;
262	int i;
263	int rays = 0;
264	int edgeSamplesContributions = 0;
265	for (i=0; i < maxTries && rays < samples; i++) {
266	// pickup a random face of each mesh
267	Mesh *mesh = mi->GetMesh();
268	int face = RandomValue(0, mesh->mFaces.size()-1);
269
270	Polygon3 poly(mesh->mFaces[face], mesh);
271	poly.Scale(1.001);
272	// now extend a random edge of the face
273	int edge = RandomValue(0, poly.mVertices.size()-1);
274	float t = RandomValue(0.0f,1.0f);
275	Vector3 target = tpoly.mVertices[edge] + (1.0f-t)poly.mVertices[(edge + 1)%
276	poly.mVertices.size()];
277	SetupRay(ray, point, target - point, Ray::LOCAL_RAY);
278	if (!mesh->CastRay(ray, mi)) {
279	// the rays which intersect the mesh have been discarded since they are not tangent
280	// to the mesh
281	rays++;
282	edgeSamplesContributions += CastRay(object, ray);
283	}
284	}
285	return edgeSamplesContributions;
286	}
287
288	bool
289	SamplingPreprocessor::ComputeVisibility()
290	{
291
292	// pickup an object
293	ObjectContainer objects;
294
295	mSceneGraph->CollectObjects(&objects);
296
297	Vector3 point, normal, direction;
298	Ray ray;
299
300	long startTime = GetTime();
301
302	int i;
303	int totalSamples = 0;
304
305	int pvsOut = Min((int)objects.size(), 10);
306
307	vector<Ray> rays[10];
308
309	vector<Ray> vcRays[5];
310	ViewCellContainer pvsViewCells;
311	vector<Ray> viewCellRays; // used for BSP tree construction
312
313	while (totalSamples < mTotalSamples) {
314	int passContributingSamples = 0;
315	int passSampleContributions = 0;
316	int passSamples = 0;
317	int index = 0;
318	Real maxTime = 0;
319	int maxTimeIdx = 0;
320
321	cout << "totalSamples: " << totalSamples << endl;
322
323	for (i = 0; i < objects.size(); i++) {
324
325	KdNode *nodeToSample = NULL;
326	Intersectable *object = objects[i];
327
328	int pvsSize = 0;
329	if (mViewCellsType == KD_VIEW_CELLS)
330	pvsSize = object->mKdPvs.GetSize();
331
332	if (0 && pvsSize) {
333	// mail all nodes from the pvs
334	Intersectable::NewMail();
335	KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
336
337	for (; i != object->mKdPvs.mEntries.end(); i++) {
338	KdNode node = (i).first;
339	node->Mail();
340	}
341
342	int maxTries = 2*pvsSize;
343	Debug << "Finding random neighbour" << endl;
344	for (int tries = 0; tries < 10; tries++) {
345	index = RandomValue(0, pvsSize - 1);
346	KdPvsData data;
347	KdNode *node;
348	object->mKdPvs.GetData(index, node, data);
349	nodeToSample = mKdTree->FindRandomNeighbor(node, true);
350	if (nodeToSample)
351	break;
352	}
353	}
354
355	if (0 && pvsSize && mPass == 1000 ) {
356	// mail all nodes from the pvs
357	Intersectable::NewMail();
358	KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
359	for (; i != object->mKdPvs.mEntries.end(); i++) {
360	KdNode node = (i).first;
361	node->Mail();
362	}
363	Debug << "Get all neighbours from PVS" << endl;
364	vector<KdNode *> invisibleNeighbors;
365	// get all neighbors of all PVS nodes
366	i = object->mKdPvs.mEntries.begin();
367	for (; i != object->mKdPvs.mEntries.end(); i++) {
368	KdNode node = (i).first;
369	mKdTree->FindNeighbors(node, invisibleNeighbors, true);
370	AxisAlignedBox3 box = object->GetBox();
371	for (int j=0; j < invisibleNeighbors.size(); j++) {
372	int visibility = ComputeBoxVisibility(mSceneGraph,
373	mKdTree,
374	box,
375	mKdTree->GetBox(invisibleNeighbors[j]),
376	1e-6f);
377	// exit(0);
378	}
379	// now rank all the neighbors according to probability that a new
380	// sample creates some contribution
381	}
382	}
383
384	object->GetRandomSurfacePoint(point, normal);
385
386	long samplesPerObjStart = GetTime();
387
388	bool viewcellSample = true;
389	int sampleContributions;
390	bool debug = false; //(object->GetId() >= 2199);
391	if (viewcellSample) {
392	nodeToSample = mKdTree->GetRandomLeaf(Plane3(normal, point));
393
394	for (int k=0; k < mSamplesPerPass; k++) {
395	if (nodeToSample) {
396	int maxTries = 5;
397
398	for (int tries = 0; tries < maxTries; tries++) {
399	direction = mKdTree->GetBox(nodeToSample).GetRandomPoint() - point;
400
401	if (DotProd(direction, normal) > Limits::Small)
402	break;
403	}
404	if (tries == maxTries)
405	direction = UniformRandomVector(normal);
406
407	if (debug) {
408	cout<<
409	"normal "<<normal<<endl<<
410	"tries "<<tries<<endl<<
411	"dir="<<direction<<endl;
412	}
413
414	}
415	else {
416	direction = UniformRandomVector(normal);
417	}
418
419	// construct a ray
420	SetupRay(ray, point, direction, Ray::LOCAL_RAY);
421
422	sampleContributions = CastRay(object, ray);
423
424	//-- CORR matt: put block inside loop
425	if (sampleContributions) {
426	passContributingSamples++;
427	passSampleContributions += sampleContributions;
428	}
429
430	if ( i < pvsOut )
431	rays[i].push_back(ray);
432
433	if (!ray.intersections.empty()) {
434	// check whether we can add this to the rays
435	for (int j = 0; j < pvsOut; j++) {
436	if (objects[j] == ray.intersections[0].mObject) {
437	rays[j].push_back(ray);
438	}
439	}
440	}
441	//-------------------
442
443	if (mViewCellsType == BSP_VIEW_CELLS)
444	{
445	// save rays for bsp tree construction
446	if ((BspTree::sConstructionMethod = BspTree::FROM_RAYS) &&
447	(totalSamples < mBspConstructionSamples))
448	{
449	mSampleRays.push_back(new Ray(ray));
450	}
451	else
452	{
453	// construct BSP tree using the samples
454	if (!mBspTree)
455	{
456	BuildBspTree();
457
458	cout << "generated " << (int)mViewCells.size() << " view cells" << endl;
459	passContributingSamples += mBspTree->GetStat().contributingSamples;
460	passSampleContributions += mBspTree->GetStat().pvs;
461
462	BspTreeStatistics(Debug);
463	Export("vc_bsptree.x3d", false, false, true);
464	}
465
466	// some random view cells for output
467	if (pvsViewCells.empty())
468	{
469	int vcPvsOut = Min((int)mViewCells.size(), 5);
470
471	for (int j = 0; j < vcPvsOut; ++ j)
472	{
473	int idx = Random((int)mViewCells.size());
474	Debug << "output view cell=" << idx << endl;
475	pvsViewCells.push_back(mViewCells[Random((int)mViewCells.size())]);
476	}
477	}
478	else
479	{
480	// check whether we can add the current ray to the rays
481	for (int k = 0; k < (int)ray.viewCells.size(); ++ k)
482	for (int j = 0; j < (int)pvsViewCells.size(); ++ j)
483	if (pvsViewCells[j] == ray.viewCells[k])
484	vcRays[j].push_back(ray);
485	}
486	}
487	}
488
489	}
490	} else {
491	// edge samples
492	// get random visible mesh
493	// object->GetRandomVisibleMesh(Plane3(normal, point));
494	}
495
496	// measure maximal time for samples per object
497	Real t = TimeDiff(samplesPerObjStart, GetTime());
498
499	if (t > maxTime)
500	{
501	maxTime = t;
502	maxTimeIdx = i;
503	}
504
505	// CORR matt: must add all samples
506	passSamples += mSamplesPerPass;
507	}
508
509	totalSamples += passSamples;
510
511	// if (pass>10)
512	// HoleSamplingPass();
513
514	mPass++;
515
516	int pvsSize = 0;
517
518	if (mViewCellsType == BSP_VIEW_CELLS) {
519	for (i=0; i < mViewCells.size(); i++) {
520	ViewCell *vc = mViewCells[i];
521	pvsSize += vc->GetPvs().GetSize();
522	}
523	} else {
524	for (i=0; i < objects.size(); i++) {
525	Intersectable *object = objects[i];
526	pvsSize += object->mKdPvs.GetSize();
527	}
528	}
529
530	Debug << "maximal time needed for pass: " << maxTime << " (object " << maxTimeIdx << ")" << endl;
531
532	float avgRayContrib = (passContributingSamples > 0) ?
533	passSampleContributions/(float)passContributingSamples : 0;
534
535	cout << "#Pass " << mPass << " : t = " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
536	cout << "#TotalSamples=" << totalSamples/1000
537	<< "k #SampleContributions=" << passSampleContributions << " ("
538	<< 100*passContributingSamples/(float)passSamples<<"%)" << " avgPVS="
539	<< pvsSize/(float)objects.size() << endl
540	<< "avg ray contrib=" << avgRayContrib << endl;
541
542	mStats <<
543	"#Pass\n" <<mPass<<endl<<
544	"#Time\n" << TimeDiff(startTime, GetTime())*1e-3 << endl<<
545	"#TotalSamples\n" << totalSamples<< endl<<
546	"#SampleContributions\n" << passSampleContributions << endl <<
547	"#PContributingSamples\n"<<100*passContributingSamples/(float)passSamples<<endl <<
548	"#AvgPVS\n"<< pvsSize/(float)objects.size() << endl <<
549	"#AvgRayContrib\n" << avgRayContrib << endl;
550	}
551
552	if (mViewCellsType == KD_VIEW_CELLS)
553	cout << "#totalPvsSize=" << mKdTree->CollectLeafPvs() << endl;
554
555	// HoleSamplingPass();
556	if (0) {
557	Exporter *exporter = Exporter::GetExporter("ray-density.x3d");
558	exporter->SetExportRayDensity(true);
559	exporter->ExportKdTree(*mKdTree);
560
561	if (mViewCellsType == BSP_VIEW_CELLS)
562	exporter->ExportBspTree(*mBspTree);
563
564	delete exporter;
565	}
566
567	bool exportRays = false;
568	if (exportRays) {
569	Exporter *exporter = NULL;
570	exporter = Exporter::GetExporter("sample-rays.x3d");
571	exporter->SetWireframe();
572	exporter->ExportKdTree(*mKdTree);
573	exporter->ExportBspTree(*mBspTree);
574
575	for (i=0; i < pvsOut; i++)
576	exporter->ExportRays(rays[i], 1000, RgbColor(1, 0, 0));
577	exporter->SetFilled();
578
579	delete exporter;
580	}
581	//-- several visualizations and statistics
582	if (1) {
583	if (mViewCellsType == BSP_VIEW_CELLS)
584	{
585	bool exportSplits = false;
586	environment->GetBoolValue("BspTree.exportSplits", exportSplits);
587
588	// export the bsp splits
589	if (exportSplits)
590	{
591	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
592
593	if (exporter)
594	{
595	Material m;
596	m.mDiffuseColor = RgbColor(1, 0, 0);
597	exporter->SetForcedMaterial(m);
598	exporter->SetWireframe();
599	exporter->ExportBspSplits(*mBspTree);
600
601	// take forced material, else big scenes cannot be viewed
602	m.mDiffuseColor = RgbColor(0, 1, 0);
603	exporter->SetForcedMaterial(m);
604	exporter->SetFilled();
605
606	exporter->ResetForcedMaterial();
607
608	// export scene geometry
609	if (0)
610	{
611	Material m;//= RandomMaterial();
612	m.mDiffuseColor = RgbColor(0, 0, 1);
613	exporter->SetForcedMaterial(m);
614
615	for (int j = 0; j < objects.size(); ++ j)
616	exporter->ExportIntersectable(objects[j]);
617
618	delete exporter;
619	}
620	}
621	}
622
623	for (int j = 0; j < pvsViewCells.size(); ++ j)
624	{
625	ViewCell *vc = pvsViewCells[j];
626
627	Intersectable::NewMail();
628	char s[64]; sprintf(s, "bsp-pvs%04d.x3d", j);
629
630	Exporter *exporter = Exporter::GetExporter(s);
631	exporter->SetFilled();
632
633	ViewCellPvsMap::iterator it = vc->GetPvs().mEntries.begin();
634
635	Material m;//= RandomMaterial();
636	m.mDiffuseColor = RgbColor(0, 1, 0);
637	exporter->SetForcedMaterial(m);
638
639	exporter->ExportViewCell(vc);
640
641	Debug << j << ": pvs size=" << (int)vc->GetPvs().GetSize()
642	<< ", piercing rays=" << (int)vcRays[j].size() << endl;
643
644	exporter->SetWireframe();
645
646	// export view cells
647	m.mDiffuseColor = RgbColor(1, 0, 1);
648	exporter->SetForcedMaterial(m);
649	exporter->ExportViewCells(mViewCells);
650
651	// export rays piercing this view cell
652	exporter->ExportRays(vcRays[j], 1000, RgbColor(0, 1, 0));
653
654	m.mDiffuseColor = RgbColor(1, 0, 0);
655	exporter->SetForcedMaterial(m);
656
657	// output PVS of view cell
658	for (; it != vc->GetPvs().mEntries.end(); ++ it)
659	{
660	Intersectable intersect = (it).first;
661	if (!intersect->Mailed())
662	{
663	exporter->ExportIntersectable(intersect);
664	intersect->Mail();
665	}
666	}
667
668	// output rest of the sobjects
669	if (0)
670	{
671	Material m;//= RandomMaterial();
672	m.mDiffuseColor = RgbColor(0, 0, 1);
673	exporter->SetForcedMaterial(m);
674
675	for (int j = 0; j < objects.size(); ++ j)
676	if (!objects[j]->Mailed())
677	{
678	//if (j == 2198)m.mDiffuseColor = RgbColor(1, 0, 1);
679	//else m.mDiffuseColor = RgbColor(1, 1, 0);
680	exporter->SetForcedMaterial(m);
681	exporter->ExportIntersectable(objects[j]);
682	objects[j]->Mail();
683	}
684	}
685	DEL_PTR(exporter);
686	}
687	}
688
689	for (int k=0; k < pvsOut; k++) {
690	Intersectable *object = objects[k];
691	char s[64];
692	sprintf(s, "sample-pvs%04d.x3d", k);
693	Exporter *exporter = Exporter::GetExporter(s);
694	exporter->SetWireframe();
695
696
697	KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
698	Intersectable::NewMail();
699
700	// avoid adding the object to the list
701	object->Mail();
702	ObjectContainer visibleObjects;
703
704	for (; i != object->mKdPvs.mEntries.end(); i++)
705	{
706	KdNode node = (i).first;
707	exporter->ExportBox(mKdTree->GetBox(node));
708	mKdTree->CollectObjects(node, visibleObjects);
709	}
710
711	exporter->ExportRays(rays[k], 1000, RgbColor(0, 1, 0));
712	exporter->SetFilled();
713
714	for (int j = 0; j < visibleObjects.size(); j++)
715	exporter->ExportIntersectable(visibleObjects[j]);
716
717
718	Material m;
719	m.mDiffuseColor = RgbColor(1, 0, 0);
720	exporter->SetForcedMaterial(m);
721	exporter->ExportIntersectable(object);
722
723	delete exporter;
724	}
725	}
726
727	return true;
728	}

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

Download in other formats: