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

Revision 332, 17.7 KB checked in by mattausch, 19 years ago (diff)

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