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

Revision 2592, 8.5 KB checked in by bittner, 17 years ago (diff)

havran ray caster update

Line 
1#include "RayCaster.h"
2#include "VssRay.h"
3#include "Ray.h"
4#include "Preprocessor.h"
5#include "ViewCellsManager.h"
6
7
8namespace GtpVisibilityPreprocessor {
9
10
11#define DEBUG_RAYCAST 0
12
13#define EXACT_BOX_CLIPPING 0
14
15RayCaster::RayCaster(const Preprocessor &preprocessor):
16  mVssRayPool(), mPreprocessor(preprocessor)
17{
18}
19
20
21RayCaster::~RayCaster()
22{
23}
24
25
26VssRay *RayCaster::CastRay(const SimpleRay &simpleRay,
27                                                   const AxisAlignedBox3 &box,
28                                                   const bool castDoubleRay)
29{
30        VssRayContainer rays;
31        CastRay(simpleRay, rays, box, castDoubleRay, true);
32   
33        if (!rays.empty())
34                return rays.back();
35        else
36                return NULL;
37}
38
39
40bool
41RayCaster::ClipToViewSpaceBox(const Vector3 &origin,
42                                                          const Vector3 &termination,
43                                                          Vector3 &clippedOrigin,
44                                                          Vector3 &clippedTermination)
45{
46 
47  Ray ray(origin, termination - origin, Ray::LINE_SEGMENT);     
48  ray.Precompute();
49 
50  float tmin, tmax;
51  if ((!mPreprocessor.mViewCellsManager->
52           GetViewSpaceBox().ComputeMinMaxT(ray, &tmin, &tmax)) ||
53          tmin>=tmax
54          )
55        return false;
56
57  if (tmin >= 1.0f || tmax <= 0.0f)
58        return false;
59 
60  if (tmin > 0.0f)
61        clippedOrigin = ray.Extrap(tmin);
62  else
63        clippedOrigin = origin;
64 
65  if (tmax < 1.0f)
66        clippedTermination = ray.Extrap(tmax);
67  else
68        clippedTermination = termination;
69 
70  return true;
71}
72
73/** Checks if ray is valid
74        (e.g., not in empty view space or outside the view space)
75*/
76bool
77RayCaster::ValidateRay(const Vector3 &origin,
78                                           const Vector3 &direction,
79                                           const AxisAlignedBox3 &box,
80                                           Intersection &hit)
81{
82        if (!hit.mObject) 
83        {
84                // compute intersection with the scene bounding box
85#if EXACT_BOX_CLIPPING
86                static Ray ray;
87                mPreprocessor.SetupRay(ray, origin, direction);
88
89                float tmin, tmax;
90                if (box.ComputeMinMaxT(ray, &tmin, &tmax) && (tmin < tmax))
91                {
92                        hit.mPoint = ray.Extrap(tmax);
93                }
94                else
95                {
96                        // cout<<" invalid hp "<<tmin<<" "<<tmax<<endl;
97                        // cout<<" box "<<box<<endl;
98                        // cout<<" origin "<<origin<<endl;
99                        // cout<<" direction "<<direction<<endl;
100                        // cout<< "inv dir"<<ray.GetInvDir()<<endl;
101                        return false;
102                }
103#else
104                hit.mPoint = origin + direction * Magnitude(box.Diagonal());
105#endif
106        }
107        else
108        {
109          if (mPreprocessor.mDetectEmptyViewSpace)  {
110                if (DotProd(hit.mNormal, direction) >= -Limits::Small)  {       
111                  hit.mObject = NULL;
112                  return false;
113                }
114          }
115        }
116       
117        return true;
118}
119
120void
121RayCaster::SortRays(SimpleRayContainer &rays)
122{
123  AxisAlignedBox3 box =
124        mPreprocessor.mViewCellsManager->GetViewSpaceBox();
125 
126  float b[12]={
127        box.Min().x,
128        box.Min().y,
129        box.Min().z,
130        -1,
131        -1,
132        -1,
133        box.Max().x,
134        box.Max().y,
135        box.Max().z,
136        1,
137        1,
138        1
139  };
140
141#if 0
142  static vector<SimpleRay *> pointerArray;
143
144  if (pointerArray.size()!=rays.size()) {
145        // realloc the pointerarray
146        pointerArray.resize(rays.size());
147  }
148
149  // init pointer array
150  SimpleRay *p = &pointerArray[0];
151  for (i=0; i < rays.size(); i++, p++)
152        pointerArray[i] = p;
153#endif
154 
155  _SortRays(rays,
156                        0,
157                        (int)rays.size()-1,
158                        0,
159                        b
160                        );
161}
162                                       
163void
164RayCaster::_SortRays(SimpleRayContainer &rays,
165                                         const int l,
166                                         const int r,
167                                         const int depth,
168                                         float box[12])
169{
170  // pick-up a pivot
171  int axis;
172 
173  float maxDiff = -1.0f;
174  // get the largest axis
175  int offset = 0;
176  int i;
177
178  //const int batchsize = 16384;
179  const int batchsize = 8192;
180  // const int batchsize = 1024;
181  //const int batchsize = 128;
182
183  //if (r - l < 16*batchsize)
184  //    offset = 3;
185       
186  //  if (depth%2==0)
187  //    offset = 3;
188 
189  for (i=offset; i < offset + 3; i++) {
190        float diff = box[i + 6] - box[i];
191        if (diff > maxDiff) {
192          maxDiff = diff;
193          axis = i;
194        }
195  }
196
197  //  cout<<depth<<" "<<axis<<" "<<l<<" "<<r<<endl;
198 
199  i=l;
200  int j=r;
201
202  float x = (box[axis] + box[axis+6])*0.5f;
203  //  float x = rays[(l+r)/2].GetParam(axis);
204  do {
205        while(i<j && rays[i].GetParam(axis) < x)
206          i++;
207        while(i<j && x < rays[j].GetParam(axis))
208          j--;
209       
210        if (i <= j) {
211          swap(rays[i], rays[j]);
212          i++;
213          j--;
214        }
215  } while (i<=j);
216
217 
218  if (l + batchsize < j ) {
219        // set new max
220        float save = box[axis+6];
221        box[axis+6] = x;
222        _SortRays(rays, l, j, depth+1, box);
223        box[axis+6] = save;
224  } else {
225        //      for (int k=0; k < 6; k++)
226        //        cout<<k<<" "<<box[k]<<" - "<<box[k+6]<<endl;
227  }
228 
229  if (i + batchsize < r) {
230        // set new min
231        box[axis] = x;
232    _SortRays(rays, i, r, depth+1, box);
233  } else {
234        //      for (int k=0; k < 6; k++)
235        //        cout<<k<<" "<<box[k]<<" - "<<box[k+6]<<endl;
236  }
237       
238}
239 
240                                       
241VssRay *RayCaster::RequestRay(const Vector3 &origin,
242                                                          const Vector3 &termination,
243                                                          Intersectable *originObject,
244                                                          Intersectable *terminationObject,
245                                                          const int pass,
246                                                          const float pdf)
247{
248 #if DEBUG_RAYCAST
249        Debug<<"PR2a"<<flush;
250#endif
251       
252        // old method: always allocate
253        if (0) return new VssRay(origin, termination, originObject, terminationObject, pass, pdf);
254
255        VssRay *vssRay = mVssRayPool.Alloc();
256
257#if DEBUG_RAYCAST
258        Debug<<"PR2b"<<flush;
259#endif
260       
261        *vssRay = VssRay(origin, termination, originObject, terminationObject, pass, pdf);
262
263#if DEBUG_RAYCAST
264        Debug<<"PR2c"<<flush;
265#endif
266
267        return vssRay;
268}
269
270
271int
272RayCaster::ProcessRay(const SimpleRay &simpleRay,
273                                          Intersection &hitA,
274                                          Intersection &hitB,
275                                          VssRayContainer &vssRays,
276                                          const AxisAlignedBox3 &box,
277                                          const bool castDoubleRay,
278                                          const bool pruneInvalidRays)
279{
280  int hits = 0;
281
282
283#if DEBUG_RAYCAST
284  static int id=0;
285  Debug<<"PRA "<<id++<<endl<<flush;
286#endif
287       
288        if (pruneInvalidRays)
289        {
290          if (!hitA.mObject && !hitB.mObject) {
291                return 0;
292          }
293        }
294       
295        // regardless of the pruneInvalidRays setting reject
296        // rays whic degenerate to a point
297        if (EpsilonEqualV3(hitA.mPoint, hitB.mPoint, Limits::Small)) {
298          return 0;
299        }
300       
301        const bool validA = ValidateRay(simpleRay.mOrigin, simpleRay.mDirection, box, hitA);
302        const bool validB = //castDoubleRay &&
303          ValidateRay(simpleRay.mOrigin, -simpleRay.mDirection, box, hitB);
304       
305       
306#if DEBUG_RAYCAST
307        Debug<<"PR1"<<flush;
308#endif
309       
310        // reset both contributions
311        if (!validA || !validB) {
312          if (0 || pruneInvalidRays)
313                return 0;
314         
315          // reset both contributions of this ray
316          hitA.mObject = NULL;
317          hitB.mObject = NULL;
318        }
319       
320        // 8.11. 2007 JB
321        // degenerate rays checked by geometrical constraint...
322        //      !pruneInvalidRays || (hitA.mObject != hitB.mObject);
323
324       
325#if DEBUG_RAYCAST
326        Debug<<"PR2"<<flush;
327#endif
328
329        // VH - I do not know what this is for, commented out temporarily
330        // !!!!!!!!!!!!!! !!!!!!!!!!!! !!!!!!!!!!
331#if 1
332        const bool validSample = true;
333        if (validSample) {
334          Vector3 clipA, clipB;
335          if (!ClipToViewSpaceBox(hitA.mPoint,
336                                                          hitB.mPoint,
337                                                          clipA,
338                                                          clipB))
339                return 0;
340
341          if (!pruneInvalidRays || hitA.mObject) {
342
343                  VssRay *vssRay =
344                          RequestRay(!castDoubleRay ? simpleRay.mOrigin : clipB,
345                                                 hitA.mPoint,
346                                                 hitB.mObject,
347                                                 hitA.mObject,
348                                                 mPreprocessor.mPass,
349                                                 1.0f //simpleRay.mPdf
350                                                 );
351
352                if (validA)
353                  vssRay->mFlags |= VssRay::Valid;
354               
355                vssRay->mDistribution = simpleRay.mDistribution;
356                vssRay->mGeneratorId = simpleRay.mGeneratorId;
357
358                vssRays.push_back(vssRay);
359                ++ hits;
360                //cout << "vssray 1: " << *vssRay << " " << vssRay->mTermination - vssRay->mOrigin << endl;
361        }
362
363#if DEBUG_RAYCAST
364        Debug<<"PR3"<<flush;
365#endif
366
367        if (castDoubleRay && (!pruneInvalidRays || hitB.mObject))
368        {
369                VssRay *vssRay = RequestRay(
370                                            clipA,
371                                            hitB.mPoint,
372                                            hitA.mObject,
373                                            hitB.mObject,
374                                            mPreprocessor.mPass,
375                                            1.0f //simpleRay.mPdf
376                                            );
377
378                if (validB)
379                        vssRay->mFlags |= VssRay::Valid;
380
381                vssRay->mDistribution = simpleRay.mDistribution;
382                vssRay->mGeneratorId = simpleRay.mGeneratorId;
383                vssRays.push_back(vssRay);
384                ++ hits;
385                //cout << "vssray 2: " << *vssRay << endl;
386        }
387#if DEBUG_RAYCAST
388          Debug<<"PR4"<<flush;
389#endif
390        } // validSample
391#else
392        // Just pass if intersected or not
393        hits = (hitA.mObject != 0) ? 1 : 0;
394        intersect = hitA;
395#endif 
396       
397        return hits;
398}
399
400
401void
402RayCaster::CastRays(
403                    SimpleRayContainer &rays,
404                    VssRayContainer &vssRays,
405                    const AxisAlignedBox3 &sbox,
406                    const bool castDoubleRay,
407                    const bool pruneInvalidRays )
408{
409  SimpleRayContainer::const_iterator rit, rit_end = rays.end();
410 
411  for (rit = rays.begin(); rit != rit_end; ++ rit) {
412   
413    CastRay(
414            *rit,                               
415            vssRays,
416            sbox,
417            castDoubleRay,
418            pruneInvalidRays);
419        }
420}
421 
422
423}
Note: See TracBrowser for help on using the repository browser.