source: GTP/trunk/Lib/Vis/Preprocessing/src/RayCaster.cpp @ 2635

Revision 2635, 11.1 KB checked in by bittner, 17 years ago (diff)

GetPvsCost? changed, APplyFilter2 collects small kdnodes

RevLine 
[1520]1#include "RayCaster.h"
2#include "VssRay.h"
3#include "Ray.h"
4#include "Preprocessor.h"
[1942]5#include "ViewCellsManager.h"
[1520]6
[2629]7#include <cassert>
[1520]8
9namespace GtpVisibilityPreprocessor {
10
11
[2635]12#define DEBUG_PROCESS_RAY 0
13
[1520]14#define DEBUG_RAYCAST 0
15
[1942]16#define EXACT_BOX_CLIPPING 0
[1520]17
18RayCaster::RayCaster(const Preprocessor &preprocessor):
[2583]19  mVssRayPool(), mPreprocessor(preprocessor)
[1520]20{
21}
22
23
[1521]24RayCaster::~RayCaster()
25{
26}
27
28
[1545]29VssRay *RayCaster::CastRay(const SimpleRay &simpleRay,
[1990]30                                                   const AxisAlignedBox3 &box,
[1996]31                                                   const bool castDoubleRay)
[1521]32{
[1932]33        VssRayContainer rays;
[1996]34        CastRay(simpleRay, rays, box, castDoubleRay, true);
[1932]35   
36        if (!rays.empty())
37                return rays.back();
38        else
39                return NULL;
[1521]40}
41
[1990]42
[1942]43bool
44RayCaster::ClipToViewSpaceBox(const Vector3 &origin,
45                                                          const Vector3 &termination,
46                                                          Vector3 &clippedOrigin,
47                                                          Vector3 &clippedTermination)
48{
[1952]49 
[1942]50  Ray ray(origin, termination - origin, Ray::LINE_SEGMENT);     
51  ray.Precompute();
52 
53  float tmin, tmax;
54  if ((!mPreprocessor.mViewCellsManager->
55           GetViewSpaceBox().ComputeMinMaxT(ray, &tmin, &tmax)) ||
56          tmin>=tmax
57          )
58        return false;
[1521]59
[2070]60  if (tmin >= 1.0f || tmax <= 0.0f)
[1942]61        return false;
62 
63  if (tmin > 0.0f)
64        clippedOrigin = ray.Extrap(tmin);
65  else
66        clippedOrigin = origin;
67 
68  if (tmax < 1.0f)
69        clippedTermination = ray.Extrap(tmax);
70  else
71        clippedTermination = termination;
72 
73  return true;
74}
75
[2070]76/** Checks if ray is valid
77        (e.g., not in empty view space or outside the view space)
[1528]78*/
[1867]79bool
80RayCaster::ValidateRay(const Vector3 &origin,
81                                           const Vector3 &direction,
82                                           const AxisAlignedBox3 &box,
83                                           Intersection &hit)
[1528]84{
[1932]85        if (!hit.mObject) 
86        {
87                // compute intersection with the scene bounding box
[1584]88#if EXACT_BOX_CLIPPING
[1932]89                static Ray ray;
90                mPreprocessor.SetupRay(ray, origin, direction);
91
92                float tmin, tmax;
93                if (box.ComputeMinMaxT(ray, &tmin, &tmax) && (tmin < tmax))
94                {
95                        hit.mPoint = ray.Extrap(tmax);
96                }
97                else
98                {
99                        // cout<<" invalid hp "<<tmin<<" "<<tmax<<endl;
100                        // cout<<" box "<<box<<endl;
101                        // cout<<" origin "<<origin<<endl;
102                        // cout<<" direction "<<direction<<endl;
103                        // cout<< "inv dir"<<ray.GetInvDir()<<endl;
104                        return false;
105                }
[1584]106#else
[1932]107                hit.mPoint = origin + direction * Magnitude(box.Diagonal());
[1584]108#endif
109        }
[1932]110        else
111        {
[2035]112          if (mPreprocessor.mDetectEmptyViewSpace)  {
113                if (DotProd(hit.mNormal, direction) >= -Limits::Small)  {       
114                  hit.mObject = NULL;
115                  return false;
[1932]116                }
[2035]117          }
[1932]118        }
[2035]119       
[1932]120        return true;
[1528]121}
122
[1974]123void
124RayCaster::SortRays(SimpleRayContainer &rays)
125{
[1984]126  AxisAlignedBox3 box =
127        mPreprocessor.mViewCellsManager->GetViewSpaceBox();
[2105]128 
[1984]129  float b[12]={
130        box.Min().x,
131        box.Min().y,
132        box.Min().z,
133        -1,
134        -1,
135        -1,
136        box.Max().x,
137        box.Max().y,
138        box.Max().z,
139        1,
140        1,
141        1
142  };
143
[2105]144#if 0
145  static vector<SimpleRay *> pointerArray;
146
147  if (pointerArray.size()!=rays.size()) {
148        // realloc the pointerarray
149        pointerArray.resize(rays.size());
150  }
151
152  // init pointer array
153  SimpleRay *p = &pointerArray[0];
154  for (i=0; i < rays.size(); i++, p++)
155        pointerArray[i] = p;
156#endif
157 
[1984]158  _SortRays(rays,
159                        0,
[1990]160                        (int)rays.size()-1,
[1984]161                        0,
162                        b
163                        );
[1974]164}
165                                       
166void
167RayCaster::_SortRays(SimpleRayContainer &rays,
168                                         const int l,
169                                         const int r,
[1984]170                                         const int depth,
171                                         float box[12])
[1974]172{
173  // pick-up a pivot
[1984]174  int axis;
175 
176  float maxDiff = -1.0f;
177  // get the largest axis
178  int offset = 0;
[1990]179  int i;
[1984]180
[2105]181  //const int batchsize = 16384;
[2008]182  const int batchsize = 8192;
[2105]183  //const int batchsize = 128;
[2008]184
[2105]185  //if (r - l < 16*batchsize)
186  //    offset = 3;
[2008]187       
[2105]188  //  if (depth%2==0)
[2008]189  //    offset = 3;
[1984]190 
[2002]191  for (i=offset; i < offset + 3; i++) {
192        float diff = box[i + 6] - box[i];
[1984]193        if (diff > maxDiff) {
194          maxDiff = diff;
195          axis = i;
196        }
197  }
198
[2008]199  //  cout<<depth<<" "<<axis<<" "<<l<<" "<<r<<endl;
[1984]200 
[1990]201  i=l;
202  int j=r;
203
[1984]204  float x = (box[axis] + box[axis+6])*0.5f;
205  //  float x = rays[(l+r)/2].GetParam(axis);
[1974]206  do {
[2008]207        while(i<j && rays[i].GetParam(axis) < x)
[1974]208          i++;
[2008]209        while(i<j && x < rays[j].GetParam(axis))
[1974]210          j--;
211       
212        if (i <= j) {
213          swap(rays[i], rays[j]);
214          i++;
215          j--;
216        }
217  } while (i<=j);
[2008]218
[1974]219 
[2008]220  if (l + batchsize < j ) {
[1984]221        // set new max
222        float save = box[axis+6];
223        box[axis+6] = x;
224        _SortRays(rays, l, j, depth+1, box);
225        box[axis+6] = save;
[2008]226  } else {
227        //      for (int k=0; k < 6; k++)
228        //        cout<<k<<" "<<box[k]<<" - "<<box[k+6]<<endl;
[1984]229  }
[1974]230 
[2008]231  if (i + batchsize < r) {
[1984]232        // set new min
233        box[axis] = x;
234    _SortRays(rays, i, r, depth+1, box);
[2008]235  } else {
236        //      for (int k=0; k < 6; k++)
237        //        cout<<k<<" "<<box[k]<<" - "<<box[k+6]<<endl;
[1984]238  }
[2008]239       
[1974]240}
241 
[2629]242
243void
244RayCaster::SortRays2(SimpleRayContainer &rays)
245{
246  AxisAlignedBox3 box =
247        mPreprocessor.mViewCellsManager->GetViewSpaceBox();
248
249  const float sizeBox = Magnitude(box.Diagonal());
250  // This is some size of the
251  const float sizeDir = 0.2f * sizeBox;
252 
253  float b[12]={
254    box.Min().x,
255    box.Min().y,
256    box.Min().z,
257    -sizeDir,
258    -sizeDir,
259    -sizeDir,
260    box.Max().x,
261    box.Max().y,
262    box.Max().z,
263    sizeDir,
264    sizeDir,
265    sizeDir
266  };
267
268#if 0
269  static vector<SimpleRay *> pointerArray;
270
271  if (pointerArray.size()!=rays.size()) {
272        // realloc the pointerarray
273        pointerArray.resize(rays.size());
274  }
275
276  // init pointer array
277  SimpleRay *p = &pointerArray[0];
278  for (i=0; i < rays.size(); i++, p++)
279        pointerArray[i] = p;
280#endif
281 
282  _SortRays2(rays, 0, (int)rays.size()-1, 0, b);
283
284  return;
285}
[1974]286                                       
[2629]287void
288RayCaster::_SortRays2(SimpleRayContainer &rays,
289                      const int l,
290                      const int r,
291                      const int depth,
292                      float box[12])
293{
294  // pick-up a pivot
295  int axis;
296 
297  float maxDiff = -1.0f;
298  // get the largest axis
299  int offset = 0;
300  int i;
301
302  //const int batchsize = 16384;
303  //const int batchsize = 8192;
304  const int batchsize = 128;
305
306  //if (r - l < 16*batchsize)
307  //    offset = 3;
308       
309  //  if (depth%2==0)
310  //    offset = 3;
311 
312  for (i=offset; i < offset + 6; i++) {
313    float diff = box[i + 6] - box[i];
314    assert(diff >= 0.f);
315    if (diff > maxDiff) {
316      // Find the maximum
317      maxDiff = diff;
318      axis = i;
319    }
320  }
321
322  //  cout<<depth<<" "<<axis<<" "<<l<<" "<<r<<endl;
323 
324  i=l;
325  int j=r;
326
327  float x = (box[axis] + box[axis+6])*0.5f;
328  //  float x = rays[(l+r)/2].GetParam(axis);
329  do {
330        while(i<j && rays[i].GetParam(axis) < x)
331          i++;
332        while(i<j && x < rays[j].GetParam(axis))
333          j--;
334       
335        if (i <= j) {
336          swap(rays[i], rays[j]);
337          i++;
338          j--;
339        }
340  } while (i<=j);
341
342 
343  if (l + batchsize < j ) {
344        // set new max
345        float save = box[axis+6];
346        box[axis+6] = x;
347        _SortRays2(rays, l, j, depth+1, box);
348        box[axis+6] = save;
349  } else {
350        //      for (int k=0; k < 6; k++)
351        //        cout<<k<<" "<<box[k]<<" - "<<box[k+6]<<endl;
352  }
353 
354  if (i + batchsize < r) {
355    // set new min
356    box[axis] = x;
357    _SortRays2(rays, i, r, depth+1, box);
358  } else {
359        //      for (int k=0; k < 6; k++)
360        //        cout<<k<<" "<<box[k]<<" - "<<box[k+6]<<endl;
361  }
362       
363}
364 
365 
[2187]366VssRay *RayCaster::RequestRay(const Vector3 &origin,
367                                                          const Vector3 &termination,
368                                                          Intersectable *originObject,
369                                                          Intersectable *terminationObject,
370                                                          const int pass,
371                                                          const float pdf)
372{
373 #if DEBUG_RAYCAST
374        Debug<<"PR2a"<<flush;
375#endif
376       
377        // old method: always allocate
[2198]378        if (0) return new VssRay(origin, termination, originObject, terminationObject, pass, pdf);
[1528]379
[2187]380        VssRay *vssRay = mVssRayPool.Alloc();
381
382#if DEBUG_RAYCAST
383        Debug<<"PR2b"<<flush;
384#endif
385       
386        *vssRay = VssRay(origin, termination, originObject, terminationObject, pass, pdf);
387
388#if DEBUG_RAYCAST
389        Debug<<"PR2c"<<flush;
390#endif
391
392        return vssRay;
393}
394
395
[1867]396int
397RayCaster::ProcessRay(const SimpleRay &simpleRay,
[2583]398                                          Intersection &hitA,
399                                          Intersection &hitB,
400                                          VssRayContainer &vssRays,
401                                          const AxisAlignedBox3 &box,
402                                          const bool castDoubleRay,
403                                          const bool pruneInvalidRays)
[1520]404{
[1984]405  int hits = 0;
[1528]406
[2014]407
[1520]408#if DEBUG_RAYCAST
[2013]409  static int id=0;
410  Debug<<"PRA "<<id++<<endl<<flush;
[1520]411#endif
[1528]412       
[1932]413        if (pruneInvalidRays)
414        {
[1952]415          if (!hitA.mObject && !hitB.mObject) {
[2635]416#if DEBUG_PROCESS_RAY
417                cout<<"I1 ";
418#endif
[1952]419                return 0;
420          }
[1520]421        }
[1584]422       
[2070]423        // regardless of the pruneInvalidRays setting reject
424        // rays whic degenerate to a point
[1966]425        if (EpsilonEqualV3(hitA.mPoint, hitB.mPoint, Limits::Small)) {
[2635]426#if DEBUG_PROCESS_RAY
427                cout<<"I2 ";
428#endif
[2035]429          return 0;
[1966]430        }
431       
[1952]432        const bool validA = ValidateRay(simpleRay.mOrigin, simpleRay.mDirection, box, hitA);
[1932]433        const bool validB = //castDoubleRay &&
[1952]434          ValidateRay(simpleRay.mOrigin, -simpleRay.mDirection, box, hitB);
[1867]435       
[1952]436       
[1757]437#if DEBUG_RAYCAST
438        Debug<<"PR1"<<flush;
439#endif
[1584]440       
[1867]441        // reset both contributions
[1952]442        if (!validA || !validB) {
[2070]443          if (0 || pruneInvalidRays)
[1952]444                return 0;
[2635]445
446#if DEBUG_PROCESS_RAY
447                cout<<"I2 ";
448#endif
449
[1952]450          // reset both contributions of this ray
451          hitA.mObject = NULL;
452          hitB.mObject = NULL;
453        }
454       
[1867]455        // 8.11. 2007 JB
456        // degenerate rays checked by geometrical constraint...
457        //      !pruneInvalidRays || (hitA.mObject != hitB.mObject);
[1942]458
[1584]459       
[1757]460#if DEBUG_RAYCAST
461        Debug<<"PR2"<<flush;
462#endif
[2575]463
464        // VH - I do not know what this is for, commented out temporarily
465        // !!!!!!!!!!!!!! !!!!!!!!!!!! !!!!!!!!!!
466#if 1
[1942]467        const bool validSample = true;
468        if (validSample) {
469          Vector3 clipA, clipB;
470          if (!ClipToViewSpaceBox(hitA.mPoint,
471                                                          hitB.mPoint,
472                                                          clipA,
[2635]473                                                          clipB)) {
474#if DEBUG_PROCESS_RAY
475                cout<<"I3 ";
476#endif
477
[1942]478                return 0;
[2635]479          }
[1952]480
[1942]481          if (!pruneInvalidRays || hitA.mObject) {
[2014]482
[2187]483                  VssRay *vssRay =
484                          RequestRay(!castDoubleRay ? simpleRay.mOrigin : clipB,
[2012]485                                                 hitA.mPoint,
486                                                 hitB.mObject,
487                                                 hitA.mObject,
488                                                 mPreprocessor.mPass,
[2105]489                                                 1.0f //simpleRay.mPdf
[2012]490                                                 );
[2187]491
[1867]492                if (validA)
[2021]493                  vssRay->mFlags |= VssRay::Valid;
494               
[1883]495                vssRay->mDistribution = simpleRay.mDistribution;
[1989]496                vssRay->mGeneratorId = simpleRay.mGeneratorId;
497
[1867]498                vssRays.push_back(vssRay);
499                ++ hits;
500                //cout << "vssray 1: " << *vssRay << " " << vssRay->mTermination - vssRay->mOrigin << endl;
[1932]501        }
502
[1867]503#if DEBUG_RAYCAST
[1932]504        Debug<<"PR3"<<flush;
[1867]505#endif
506
[2070]507        if (castDoubleRay && (!pruneInvalidRays || hitB.mObject))
508        {
[2187]509                VssRay *vssRay = RequestRay(
[2575]510                                            clipA,
511                                            hitB.mPoint,
512                                            hitA.mObject,
513                                            hitB.mObject,
514                                            mPreprocessor.mPass,
515                                            1.0f //simpleRay.mPdf
516                                            );
[2070]517
518                if (validB)
[1771]519                        vssRay->mFlags |= VssRay::Valid;
[1932]520
521                vssRay->mDistribution = simpleRay.mDistribution;
[1989]522                vssRay->mGeneratorId = simpleRay.mGeneratorId;
[1932]523                vssRays.push_back(vssRay);
524                ++ hits;
525                //cout << "vssray 2: " << *vssRay << endl;
[2070]526        }
[1942]527#if DEBUG_RAYCAST
528          Debug<<"PR4"<<flush;
529#endif
[2575]530        } // validSample
531#else
532        // Just pass if intersected or not
533        hits = (hitA.mObject != 0) ? 1 : 0;
534        intersect = hitA;
535#endif 
[1867]536       
[1520]537        return hits;
538}
539
[2076]540
541void
542RayCaster::CastRays(
[2575]543                    SimpleRayContainer &rays,
544                    VssRayContainer &vssRays,
545                    const AxisAlignedBox3 &sbox,
546                    const bool castDoubleRay,
547                    const bool pruneInvalidRays )
[2076]548{
[2575]549  SimpleRayContainer::const_iterator rit, rit_end = rays.end();
550 
551  for (rit = rays.begin(); rit != rit_end; ++ rit) {
552   
553    CastRay(
554            *rit,                               
555            vssRays,
556            sbox,
557            castDoubleRay,
558            pruneInvalidRays);
[2187]559        }
[1583]560}
[2575]561 
[2076]562
563}
Note: See TracBrowser for help on using the repository browser.