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

Line 
1#include "RayCaster.h"
2#include "VssRay.h"
3#include "Ray.h"
4#include "Preprocessor.h"
5#include "ViewCellsManager.h"
6
7#include <cassert>
8
9namespace GtpVisibilityPreprocessor {
10
11
12#define DEBUG_PROCESS_RAY 0
13
14#define DEBUG_RAYCAST 0
15
16#define EXACT_BOX_CLIPPING 0
17
18RayCaster::RayCaster(const Preprocessor &preprocessor):
19  mVssRayPool(), mPreprocessor(preprocessor)
20{
21}
22
23
24RayCaster::~RayCaster()
25{
26}
27
28
29VssRay *RayCaster::CastRay(const SimpleRay &simpleRay,
30                                                   const AxisAlignedBox3 &box,
31                                                   const bool castDoubleRay)
32{
33        VssRayContainer rays;
34        CastRay(simpleRay, rays, box, castDoubleRay, true);
35   
36        if (!rays.empty())
37                return rays.back();
38        else
39                return NULL;
40}
41
42
43bool
44RayCaster::ClipToViewSpaceBox(const Vector3 &origin,
45                                                          const Vector3 &termination,
46                                                          Vector3 &clippedOrigin,
47                                                          Vector3 &clippedTermination)
48{
49 
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;
59
60  if (tmin >= 1.0f || tmax <= 0.0f)
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
76/** Checks if ray is valid
77        (e.g., not in empty view space or outside the view space)
78*/
79bool
80RayCaster::ValidateRay(const Vector3 &origin,
81                                           const Vector3 &direction,
82                                           const AxisAlignedBox3 &box,
83                                           Intersection &hit)
84{
85        if (!hit.mObject) 
86        {
87                // compute intersection with the scene bounding box
88#if EXACT_BOX_CLIPPING
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                }
106#else
107                hit.mPoint = origin + direction * Magnitude(box.Diagonal());
108#endif
109        }
110        else
111        {
112          if (mPreprocessor.mDetectEmptyViewSpace)  {
113                if (DotProd(hit.mNormal, direction) >= -Limits::Small)  {       
114                  hit.mObject = NULL;
115                  return false;
116                }
117          }
118        }
119       
120        return true;
121}
122
123void
124RayCaster::SortRays(SimpleRayContainer &rays)
125{
126  AxisAlignedBox3 box =
127        mPreprocessor.mViewCellsManager->GetViewSpaceBox();
128 
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
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 
158  _SortRays(rays,
159                        0,
160                        (int)rays.size()-1,
161                        0,
162                        b
163                        );
164}
165                                       
166void
167RayCaster::_SortRays(SimpleRayContainer &rays,
168                                         const int l,
169                                         const int r,
170                                         const int depth,
171                                         float box[12])
172{
173  // pick-up a pivot
174  int axis;
175 
176  float maxDiff = -1.0f;
177  // get the largest axis
178  int offset = 0;
179  int i;
180
181  //const int batchsize = 16384;
182  const int batchsize = 8192;
183  //const int batchsize = 128;
184
185  //if (r - l < 16*batchsize)
186  //    offset = 3;
187       
188  //  if (depth%2==0)
189  //    offset = 3;
190 
191  for (i=offset; i < offset + 3; i++) {
192        float diff = box[i + 6] - box[i];
193        if (diff > maxDiff) {
194          maxDiff = diff;
195          axis = i;
196        }
197  }
198
199  //  cout<<depth<<" "<<axis<<" "<<l<<" "<<r<<endl;
200 
201  i=l;
202  int j=r;
203
204  float x = (box[axis] + box[axis+6])*0.5f;
205  //  float x = rays[(l+r)/2].GetParam(axis);
206  do {
207        while(i<j && rays[i].GetParam(axis) < x)
208          i++;
209        while(i<j && x < rays[j].GetParam(axis))
210          j--;
211       
212        if (i <= j) {
213          swap(rays[i], rays[j]);
214          i++;
215          j--;
216        }
217  } while (i<=j);
218
219 
220  if (l + batchsize < j ) {
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;
226  } else {
227        //      for (int k=0; k < 6; k++)
228        //        cout<<k<<" "<<box[k]<<" - "<<box[k+6]<<endl;
229  }
230 
231  if (i + batchsize < r) {
232        // set new min
233        box[axis] = x;
234    _SortRays(rays, i, r, depth+1, box);
235  } else {
236        //      for (int k=0; k < 6; k++)
237        //        cout<<k<<" "<<box[k]<<" - "<<box[k+6]<<endl;
238  }
239       
240}
241 
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}
286                                       
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 
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
378        if (0) return new VssRay(origin, termination, originObject, terminationObject, pass, pdf);
379
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
396int
397RayCaster::ProcessRay(const SimpleRay &simpleRay,
398                                          Intersection &hitA,
399                                          Intersection &hitB,
400                                          VssRayContainer &vssRays,
401                                          const AxisAlignedBox3 &box,
402                                          const bool castDoubleRay,
403                                          const bool pruneInvalidRays)
404{
405  int hits = 0;
406
407
408#if DEBUG_RAYCAST
409  static int id=0;
410  Debug<<"PRA "<<id++<<endl<<flush;
411#endif
412       
413        if (pruneInvalidRays)
414        {
415          if (!hitA.mObject && !hitB.mObject) {
416#if DEBUG_PROCESS_RAY
417                cout<<"I1 ";
418#endif
419                return 0;
420          }
421        }
422       
423        // regardless of the pruneInvalidRays setting reject
424        // rays whic degenerate to a point
425        if (EpsilonEqualV3(hitA.mPoint, hitB.mPoint, Limits::Small)) {
426#if DEBUG_PROCESS_RAY
427                cout<<"I2 ";
428#endif
429          return 0;
430        }
431       
432        const bool validA = ValidateRay(simpleRay.mOrigin, simpleRay.mDirection, box, hitA);
433        const bool validB = //castDoubleRay &&
434          ValidateRay(simpleRay.mOrigin, -simpleRay.mDirection, box, hitB);
435       
436       
437#if DEBUG_RAYCAST
438        Debug<<"PR1"<<flush;
439#endif
440       
441        // reset both contributions
442        if (!validA || !validB) {
443          if (0 || pruneInvalidRays)
444                return 0;
445
446#if DEBUG_PROCESS_RAY
447                cout<<"I2 ";
448#endif
449
450          // reset both contributions of this ray
451          hitA.mObject = NULL;
452          hitB.mObject = NULL;
453        }
454       
455        // 8.11. 2007 JB
456        // degenerate rays checked by geometrical constraint...
457        //      !pruneInvalidRays || (hitA.mObject != hitB.mObject);
458
459       
460#if DEBUG_RAYCAST
461        Debug<<"PR2"<<flush;
462#endif
463
464        // VH - I do not know what this is for, commented out temporarily
465        // !!!!!!!!!!!!!! !!!!!!!!!!!! !!!!!!!!!!
466#if 1
467        const bool validSample = true;
468        if (validSample) {
469          Vector3 clipA, clipB;
470          if (!ClipToViewSpaceBox(hitA.mPoint,
471                                                          hitB.mPoint,
472                                                          clipA,
473                                                          clipB)) {
474#if DEBUG_PROCESS_RAY
475                cout<<"I3 ";
476#endif
477
478                return 0;
479          }
480
481          if (!pruneInvalidRays || hitA.mObject) {
482
483                  VssRay *vssRay =
484                          RequestRay(!castDoubleRay ? simpleRay.mOrigin : clipB,
485                                                 hitA.mPoint,
486                                                 hitB.mObject,
487                                                 hitA.mObject,
488                                                 mPreprocessor.mPass,
489                                                 1.0f //simpleRay.mPdf
490                                                 );
491
492                if (validA)
493                  vssRay->mFlags |= VssRay::Valid;
494               
495                vssRay->mDistribution = simpleRay.mDistribution;
496                vssRay->mGeneratorId = simpleRay.mGeneratorId;
497
498                vssRays.push_back(vssRay);
499                ++ hits;
500                //cout << "vssray 1: " << *vssRay << " " << vssRay->mTermination - vssRay->mOrigin << endl;
501        }
502
503#if DEBUG_RAYCAST
504        Debug<<"PR3"<<flush;
505#endif
506
507        if (castDoubleRay && (!pruneInvalidRays || hitB.mObject))
508        {
509                VssRay *vssRay = RequestRay(
510                                            clipA,
511                                            hitB.mPoint,
512                                            hitA.mObject,
513                                            hitB.mObject,
514                                            mPreprocessor.mPass,
515                                            1.0f //simpleRay.mPdf
516                                            );
517
518                if (validB)
519                        vssRay->mFlags |= VssRay::Valid;
520
521                vssRay->mDistribution = simpleRay.mDistribution;
522                vssRay->mGeneratorId = simpleRay.mGeneratorId;
523                vssRays.push_back(vssRay);
524                ++ hits;
525                //cout << "vssray 2: " << *vssRay << endl;
526        }
527#if DEBUG_RAYCAST
528          Debug<<"PR4"<<flush;
529#endif
530        } // validSample
531#else
532        // Just pass if intersected or not
533        hits = (hitA.mObject != 0) ? 1 : 0;
534        intersect = hitA;
535#endif 
536       
537        return hits;
538}
539
540
541void
542RayCaster::CastRays(
543                    SimpleRayContainer &rays,
544                    VssRayContainer &vssRays,
545                    const AxisAlignedBox3 &sbox,
546                    const bool castDoubleRay,
547                    const bool pruneInvalidRays )
548{
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);
559        }
560}
561 
562
563}
Note: See TracBrowser for help on using the repository browser.