source: projectionDesigner/tag/ProjectionDesigner_1.1.5/projdesigner/include/gmtl/Intersection.h @ 2

Last change on this file since 2 was 2, checked in by Torben Dannhauer, 10 years ago
File size: 27.3 KB
Line 
1/************************************************************** ggt-head beg
2 *
3 * GGT: Generic Graphics Toolkit
4 *
5 * Original Authors:
6 *   Allen Bierbaum
7 *
8 * -----------------------------------------------------------------
9 * File:          Intersection.h,v
10 * Date modified: 2006/06/08 21:11:59
11 * Version:       1.25
12 * -----------------------------------------------------------------
13 *
14 *********************************************************** ggt-head end */
15/*************************************************************** ggt-cpr beg
16*
17* GGT: The Generic Graphics Toolkit
18* Copyright (C) 2001,2002 Allen Bierbaum
19*
20* This library is free software; you can redistribute it and/or
21* modify it under the terms of the GNU Lesser General Public
22* License as published by the Free Software Foundation; either
23* version 2.1 of the License, or (at your option) any later version.
24*
25* This library is distributed in the hope that it will be useful,
26* but WITHOUT ANY WARRANTY; without even the implied warranty of
27* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
28* Lesser General Public License for more details.
29*
30* You should have received a copy of the GNU Lesser General Public
31* License along with this library; if not, write to the Free Software
32* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
33*
34 ************************************************************ ggt-cpr end */
35#ifndef _GMTL_INTERSECTION_H_
36#define _GMTL_INTERSECTION_H_
37
38#include <algorithm>
39#include <limits>
40#include <gmtl/AABox.h>
41#include <gmtl/Point.h>
42#include <gmtl/Sphere.h>
43#include <gmtl/Vec.h>
44#include <gmtl/Plane.h>
45#include <gmtl/VecOps.h>
46#include <gmtl/Math.h>
47#include <gmtl/Ray.h>
48#include <gmtl/LineSeg.h>
49#include <gmtl/Tri.h>
50#include <gmtl/PlaneOps.h>
51
52namespace gmtl
53{
54   /**
55    * Tests if the given AABoxes intersect with each other. Sharing an edge IS
56    * considered intersection by this algorithm.
57    *
58    * @param box1    the first AA box to test
59    * @param box2    the second AA box to test
60    *
61    * @return  true if the boxes intersect; false otherwise
62    */
63   template<class DATA_TYPE>
64   bool intersect(const AABox<DATA_TYPE>& box1, const AABox<DATA_TYPE>& box2)
65   {
66      // Look for a separating axis on each box for each axis
67      if (box1.getMin()[0] > box2.getMax()[0])  return false;
68      if (box1.getMin()[1] > box2.getMax()[1])  return false;
69      if (box1.getMin()[2] > box2.getMax()[2])  return false;
70
71      if (box2.getMin()[0] > box1.getMax()[0])  return false;
72      if (box2.getMin()[1] > box1.getMax()[1])  return false;
73      if (box2.getMin()[2] > box1.getMax()[2])  return false;
74
75      // No separating axis ... they must intersect
76      return true;
77   }
78
79   /**
80    * Tests if the given AABox and point intersect with each other. On an edge IS
81    * considered intersection by this algorithm.
82    *
83    * @param box    the box to test
84    * @param point  the point to test
85    *
86    * @return  true if the point is within the box's bounds; false otherwise
87    */
88   template<class DATA_TYPE>
89   bool intersect( const AABox<DATA_TYPE>& box, const Point<DATA_TYPE, 3>& point )
90   {
91      // Look for a separating axis on each box for each axis
92      if (box.getMin()[0] > point[0])  return false;
93      if (box.getMin()[1] > point[1])  return false;
94      if (box.getMin()[2] > point[2])  return false;
95
96      if (point[0] > box.getMax()[0])  return false;
97      if (point[1] > box.getMax()[1])  return false;
98      if (point[2] > box.getMax()[2])  return false;
99
100      // they must intersect
101      return true;
102   }
103
104   /**
105    * Tests if the given AABoxes intersect if moved along the given paths. Using
106    * the AABox sweep test, the normalized time of the first and last points of
107    * contact are found.
108    *
109    * @param box1          the first box to test
110    * @param path1         the path the first box should travel along
111    * @param box2          the second box to test
112    * @param path2         the path the second box should travel along
113    * @param firstContact  set to the normalized time of the first point of contact
114    * @param secondContact set to the normalized time of the second point of contact
115    *
116    * @return  true if the boxes intersect at any time; false otherwise
117    */
118   template<class DATA_TYPE>
119   bool intersect( const AABox<DATA_TYPE>& box1, const Vec<DATA_TYPE, 3>& path1,
120                   const AABox<DATA_TYPE>& box2, const Vec<DATA_TYPE, 3>& path2,
121                   DATA_TYPE& firstContact, DATA_TYPE& secondContact )
122   {
123      // Algorithm taken from Gamasutra's article, "Simple Intersection Test for
124      // Games" - http://www.gamasutra.com/features/19991018/Gomez_3.htm
125      //
126      // This algorithm is solved from the frame of reference of box1
127
128      // Get the relative path (in normalized time)
129      Vec<DATA_TYPE, 3> path = path2 - path1;
130
131      // The first time of overlap along each axis
132      Vec<DATA_TYPE, 3> overlap1(DATA_TYPE(0), DATA_TYPE(0), DATA_TYPE(0));
133
134      // The second time of overlap along each axis
135      Vec<DATA_TYPE, 3> overlap2(DATA_TYPE(1), DATA_TYPE(1), DATA_TYPE(1));
136
137      // Check if the boxes already overlap
138      if (gmtl::intersect(box1, box2))
139      {
140         firstContact = secondContact = DATA_TYPE(0);
141         return true;
142      }
143
144      // Find the possible first and last times of overlap along each axis
145      for (int i=0; i<3; ++i)
146      {
147         if ((box1.getMax()[i] < box2.getMin()[i]) && (path[i] < DATA_TYPE(0)))
148         {
149            overlap1[i] = (box1.getMax()[i] - box2.getMin()[i]) / path[i];
150         }
151         else if ((box2.getMax()[i] < box1.getMin()[i]) && (path[i] > DATA_TYPE(0)))
152         {
153            overlap1[i] = (box1.getMin()[i] - box2.getMax()[i]) / path[i];
154         }
155
156         if ((box2.getMax()[i] > box1.getMin()[i]) && (path[i] < DATA_TYPE(0)))
157         {
158            overlap2[i] = (box1.getMin()[i] - box2.getMax()[i]) / path[i];
159         }
160         else if ((box1.getMax()[i] > box2.getMin()[i]) && (path[i] > DATA_TYPE(0)))
161         {
162            overlap2[i] = (box1.getMax()[i] - box2.getMin()[i]) / path[i];
163         }
164      }
165
166      // Calculate the first time of overlap
167      firstContact = Math::Max(overlap1[0], overlap1[1], overlap1[2]);
168
169      // Calculate the second time of overlap
170      secondContact = Math::Min(overlap2[0], overlap2[1], overlap2[2]);
171
172      // There could only have been a collision if the first overlap time
173      // occurred before the second overlap time
174      return firstContact <= secondContact;
175   }
176
177   /**
178    * Given an axis-aligned bounding box and a ray (or subclass thereof),
179    * returns whether the ray intersects the box, and if so, \p tIn and
180    * \p tOut are set to the parametric terms on the ray where the segment
181    * enters and exits the box respectively.
182    *
183    * The implementation of this function comes from the book
184    * <i>Geometric Tools for Computer Graphics</i>, pages 626-630.
185    *
186    * @note Internal function for performing an intersection test between an
187    *       axis-aligned bounding box and a ray. User code should not call this
188    *       function directly. It is used to capture the common code between
189    *       the gmtl::Ray<T> and gmtl::LineSeg<T> overloads of
190    *       gmtl::intersect() when intersecting with a gmtl::AABox<T>.
191    */
192   template<class DATA_TYPE>
193   bool intersectAABoxRay(const AABox<DATA_TYPE>& box,
194                          const Ray<DATA_TYPE>& ray, DATA_TYPE& tIn,
195                          DATA_TYPE& tOut)
196   {
197      tIn  = -std::numeric_limits<DATA_TYPE>::max();
198      tOut = std::numeric_limits<DATA_TYPE>::max();
199      DATA_TYPE t0, t1;
200      const DATA_TYPE epsilon(0.0000001);
201
202      // YZ plane.
203      if ( gmtl::Math::abs(ray.mDir[0]) < epsilon )
204      {
205         // Ray parallel to plane.
206         if ( ray.mOrigin[0] < box.mMin[0] || ray.mOrigin[0] > box.mMax[0] )
207         {
208            return false;
209         }
210      }
211
212      // XZ plane.
213      if ( gmtl::Math::abs(ray.mDir[1]) < epsilon )
214      {
215         // Ray parallel to plane.
216         if ( ray.mOrigin[1] < box.mMin[1] || ray.mOrigin[1] > box.mMax[1] )
217         {
218            return false;
219         }
220      }
221
222      // XY plane.
223      if ( gmtl::Math::abs(ray.mDir[2]) < epsilon )
224      {
225         // Ray parallel to plane.
226         if ( ray.mOrigin[2] < box.mMin[2] || ray.mOrigin[2] > box.mMax[2] )
227         {
228            return false;
229         }
230      }
231
232      // YZ plane.
233      t0 = (box.mMin[0] - ray.mOrigin[0]) / ray.mDir[0];
234      t1 = (box.mMax[0] - ray.mOrigin[0]) / ray.mDir[0];
235
236      if ( t0 > t1 )
237      {
238         std::swap(t0, t1);
239      }
240
241      if ( t0 > tIn )
242      {
243         tIn = t0;
244      }
245      if ( t1 < tOut )
246      {
247         tOut = t1;
248      }
249
250      if ( tIn > tOut || tOut < DATA_TYPE(0) )
251      {
252         return false;
253      }
254
255      // XZ plane.
256      t0 = (box.mMin[1] - ray.mOrigin[1]) / ray.mDir[1];
257      t1 = (box.mMax[1] - ray.mOrigin[1]) / ray.mDir[1];
258
259      if ( t0 > t1 )
260      {
261         std::swap(t0, t1);
262      }
263
264      if ( t0 > tIn )
265      {
266         tIn = t0;
267      }
268      if ( t1 < tOut )
269      {
270         tOut = t1;
271      }
272
273      if ( tIn > tOut || tOut < DATA_TYPE(0) )
274      {
275         return false;
276      }
277
278      // XY plane.
279      t0 = (box.mMin[2] - ray.mOrigin[2]) / ray.mDir[2];
280      t1 = (box.mMax[2] - ray.mOrigin[2]) / ray.mDir[2];
281
282      if ( t0 > t1 )
283      {
284         std::swap(t0, t1);
285      }
286
287      if ( t0 > tIn )
288      {
289         tIn = t0;
290      }
291      if ( t1 < tOut )
292      {
293         tOut = t1;
294      }
295
296      if ( tIn > tOut || tOut < DATA_TYPE(0) )
297      {
298         return false;
299      }
300
301      return true;
302   }
303
304   /**
305    * Given a line segment and an axis-aligned bounding box, returns whether
306    * the line intersects the box, and if so, \p tIn and \p tOut are set to
307    * the parametric terms on the line segment where the segment enters and
308    * exits the box respectively.
309    *
310    * @since 0.4.11
311    */
312   template<class DATA_TYPE>
313   bool intersect(const AABox<DATA_TYPE>& box, const LineSeg<DATA_TYPE>& seg,
314                  unsigned int& numHits, DATA_TYPE& tIn, DATA_TYPE& tOut)
315   {
316      numHits = 0;
317      bool result = intersectAABoxRay(box, seg, tIn, tOut);
318
319      if ( result )
320      {
321         // If tIn is less than 0, then the origin of the line segment is
322         // inside the bounding box (not on an edge)but the endpoint is
323         // outside.
324         if ( tIn < DATA_TYPE(0) )
325         {
326            numHits = 1;
327            tIn = tOut;
328         }
329         // If tIn is less than 0, then the origin of the line segment is
330         // outside the bounding box but the endpoint is inside (not on an
331         // edge).
332         else if ( tOut > DATA_TYPE(1) )
333         {
334            numHits = 1;
335            tOut = tIn;
336         }
337         // Otherwise, the line segement intersects the bounding box in two
338         // places. tIn and tOut reflect those points of intersection.
339         else
340         {
341            numHits = 2;
342         }
343      }
344
345      return result;
346   }
347
348   /**
349    * Given a line segment and an axis-aligned bounding box, returns whether
350    * the line intersects the box, and if so, \p tIn and \p tOut are set to
351    * the parametric terms on the line segment where the segment enters and
352    * exits the box respectively.
353    *
354    * @since 0.4.11
355    */
356   template<class DATA_TYPE>
357   bool intersect(const LineSeg<DATA_TYPE>& seg, const AABox<DATA_TYPE>& box,
358                  unsigned int& numHits, DATA_TYPE& tIn, DATA_TYPE& tOut)
359   {
360      return intersect(box, seg, numHits, tIn, tOut);
361   }
362
363   /**
364    * Given a ray and an axis-aligned bounding box, returns whether the ray
365    * intersects the box, and if so, \p tIn and \p tOut are set to the
366    * parametric terms on the ray where it enters and exits the box
367    * respectively.
368    *
369    * @since 0.4.11
370    */
371   template<class DATA_TYPE>
372   bool intersect(const AABox<DATA_TYPE>& box, const Ray<DATA_TYPE>& ray,
373                  unsigned int& numHits, DATA_TYPE& tIn, DATA_TYPE& tOut)
374   {
375      numHits = 0;
376
377      bool result = intersectAABoxRay(box, ray, tIn, tOut);
378
379      if ( result )
380      {
381         // Ray is inside the box.
382         if ( tIn < DATA_TYPE(0) )
383         {
384            tIn = tOut;
385            numHits = 1;
386         }
387         else
388         {
389            numHits = 2;
390         }
391      }
392
393      return result;
394   }
395
396   /**
397    * Given a ray and an axis-aligned bounding box, returns whether the ray
398    * intersects the box, and if so, \p tIn and \p tOut are set to the
399    * parametric terms on the ray where it enters and exits the box
400    * respectively.
401    *
402    * @since 0.4.11
403    */
404   template<class DATA_TYPE>
405   bool intersect(const Ray<DATA_TYPE>& ray, const AABox<DATA_TYPE>& box,
406                  unsigned int& numHits, DATA_TYPE& tIn, DATA_TYPE& tOut)
407   {
408      return intersect(box, ray, numHits, tIn, tOut);
409   }
410
411   /**
412    * Tests if the given Spheres intersect if moved along the given paths. Using
413    * the Sphere sweep test, the normalized time of the first and last points of
414    * contact are found.
415    *
416    * @param sph1          the first sphere to test
417    * @param path1         the path the first sphere should travel along
418    * @param sph2          the second sphere to test
419    * @param path2         the path the second sphere should travel along
420    * @param firstContact  set to the normalized time of the first point of contact
421    * @param secondContact set to the normalized time of the second point of contact
422    *
423    * @return  true if the spheres intersect; false otherwise
424    */
425   template<class DATA_TYPE>
426   bool intersect(const Sphere<DATA_TYPE>& sph1, const Vec<DATA_TYPE, 3>& path1,
427                  const Sphere<DATA_TYPE>& sph2, const Vec<DATA_TYPE, 3>& path2,
428                  DATA_TYPE& firstContact, DATA_TYPE& secondContact)
429   {
430      // Algorithm taken from Gamasutra's article, "Simple Intersection Test for
431      // Games" - http://www.gamasutra.com/features/19991018/Gomez_2.htm
432      //
433      // This algorithm is solved from the frame of reference of sph1
434
435      // Get the relative path (in normalized time)
436      const Vec<DATA_TYPE, 3> path = path2 - path1;
437
438      // Get the vector from sph1's starting point to sph2's starting point
439      const Vec<DATA_TYPE, 3> start_offset = sph2.getCenter() - sph1.getCenter();
440
441      // Compute the sum of the radii
442      const DATA_TYPE radius_sum = sph1.getRadius() + sph2.getRadius();
443
444      // u*u coefficient
445      const DATA_TYPE a = dot(path, path);
446
447      // u coefficient
448      const DATA_TYPE b = DATA_TYPE(2) * dot(path, start_offset);
449
450      // constant term
451      const DATA_TYPE c = dot(start_offset, start_offset) - radius_sum * radius_sum;
452
453      // Check if they're already overlapping
454      if (dot(start_offset, start_offset) <= radius_sum * radius_sum)
455      {
456         firstContact = secondContact = DATA_TYPE(0);
457         return true;
458      }
459
460      // Find the first and last points of intersection
461      if (Math::quadraticFormula(firstContact, secondContact, a, b, c))
462      {
463         // Swap first and second contacts if necessary
464         if (firstContact > secondContact)
465         {
466            std::swap(firstContact, secondContact);
467            return true;
468         }
469      }
470
471      return false;
472   }
473
474   /**
475    * Tests if the given AABox and Sphere intersect with each other. On an edge
476    * IS considered intersection by this algorithm.
477    *
478    * @param box  the box to test
479    * @param sph  the sphere to test
480    *
481    * @return  true if the items intersect; false otherwise
482    */
483   template<class DATA_TYPE>
484   bool intersect(const AABox<DATA_TYPE>& box, const Sphere<DATA_TYPE>& sph)
485   {
486      DATA_TYPE dist_sqr = DATA_TYPE(0);
487
488      // Compute the square of the distance from the sphere to the box
489      for (int i=0; i<3; ++i)
490      {
491         if (sph.getCenter()[i] < box.getMin()[i])
492         {
493            DATA_TYPE s = sph.getCenter()[i] - box.getMin()[i];
494            dist_sqr += s*s;
495         }
496         else if (sph.getCenter()[i] > box.getMax()[i])
497         {
498            DATA_TYPE s = sph.getCenter()[i] - box.getMax()[i];
499            dist_sqr += s*s;
500         }
501      }
502
503      return dist_sqr <= (sph.getRadius()*sph.getRadius());
504   }
505
506   /**
507    * Tests if the given AABox and Sphere intersect with each other. On an edge
508    * IS considered intersection by this algorithm.
509    *
510    * @param sph  the sphere to test
511    * @param box  the box to test
512    *
513    * @return  true if the items intersect; false otherwise
514    */
515   template<class DATA_TYPE>
516   bool intersect(const Sphere<DATA_TYPE>& sph, const AABox<DATA_TYPE>& box)
517   {
518      return gmtl::intersect(box, sph);
519   }
520
521   /**
522    * intersect point/sphere.
523    * @param point   the point to test
524    * @param sphere  the sphere to test
525    * @return true if point is in or on sphere
526    */
527   template<class DATA_TYPE>
528   bool intersect( const Sphere<DATA_TYPE>& sphere, const Point<DATA_TYPE, 3>& point )
529   {
530      gmtl::Vec<DATA_TYPE, 3> offset = point - sphere.getCenter();
531      DATA_TYPE dist = lengthSquared( offset ) - sphere.getRadius() * sphere.getRadius();
532
533      // point is inside the sphere when true
534      return  dist <= 0;
535   }
536
537   /**
538    * intersect ray/sphere-shell (not volume).
539    * only register hits with the surface of the sphere.
540    * note: after calling this, you can find the intersection point with: ray.getOrigin() + ray.getDir() * t
541    *
542    * @param ray     the ray to test
543    * @param sphere  the sphere to test
544    * @return returns intersection point in t, and the number of hits
545    * @return numhits, t0, t1 are undefined if return value is false
546    */
547   template<typename T>
548   inline bool intersect( const Sphere<T>& sphere, const Ray<T>& ray, int& numhits, float& t0, float& t1 )
549   {
550      numhits = -1;
551
552      // set up quadratic Q(t) = a*t^2 + 2*b*t + c
553      const Vec<T, 3> offset = ray.getOrigin() - sphere.getCenter();
554      const T a = lengthSquared( ray.getDir() );
555      const T b = dot( offset, ray.getDir() );
556      const T c = lengthSquared( offset ) - sphere.getRadius() * sphere.getRadius();
557
558
559
560      // no intersection if Q(t) has no real roots
561      const T discriminant = b * b - a * c;
562      if (discriminant < 0.0f)
563      {
564         numhits = 0;
565         return false;
566      }
567      else if (discriminant > 0.0f)
568      {
569         T root = Math::sqrt( discriminant );
570         T invA = T(1) / a;
571         t0 = (-b - root) * invA;
572         t1 = (-b + root) * invA;
573
574         // assert: t0 < t1 since A > 0
575
576         if (t0 >= T(0))
577         {
578            numhits = 2;
579            return true;
580         }
581         else if (t1 >= T(0))
582         {
583            numhits = 1;
584            t0 = t1;
585            return true;
586         }
587         else
588         {
589            numhits = 0;
590            return false;
591         }
592      }
593      else
594      {
595         t0 = -b / a;
596         if (t0 >= T(0))
597         {
598            numhits = 1;
599            return true;
600         }
601         else
602         {
603            numhits = 0;
604            return false;
605         }
606      }
607   }
608
609   /** intersect LineSeg/Sphere-shell (not volume).
610    * does intersection on sphere surface, point inside sphere doesn't count as an intersection
611    * returns intersection point(s) in t
612    * find intersection point(s) with: ray.getOrigin() + ray.getDir() * t
613    * numhits, t0, t1 are undefined if return value is false
614    */
615   template<typename T>
616   inline bool intersect( const Sphere<T>& sphere, const LineSeg<T>& lineseg, int& numhits, float& t0, float& t1 )
617   {
618      if (intersect( sphere, Ray<T>( lineseg ), numhits, t0, t1 ))
619      {
620         // throw out hits that are past 1 in segspace (off the end of the lineseg)
621         while (0 < numhits && 1.0f < t0)
622         {
623            --numhits;
624            t0 = t1;
625         }
626         if (2 == numhits && 1.0f < t1)
627         {
628            --numhits;
629         }
630         return 0 < numhits;
631      }
632      else
633      {
634         return false;
635      }
636   }
637
638   /**
639    * intersect lineseg/sphere-volume.
640    * register hits with both the surface and when end points land on the interior of the sphere.
641    * note: after calling this, you can find the intersection point with: ray.getOrigin() + ray.getDir() * t
642    *
643    * @param ray     the lineseg to test
644    * @param sphere  the sphere to test
645    * @return returns intersection point in t, and the number of hits
646    * @return numhits, t0, t1 are undefined if return value is false
647    */
648   template<typename T>
649   inline bool intersectVolume( const Sphere<T>& sphere, const LineSeg<T>& ray, int& numhits, float& t0, float& t1 )
650   {
651      bool result = intersect( sphere, ray, numhits, t0, t1 );
652      if (result && numhits == 2)
653      {
654         return true;
655      }
656      // todo: make this faster (find an early out) since 1 or 0 hits is the common case.
657      // volume test has some additional checks before we can throw it out because
658      // one of both points may be inside the volume, so we want to return hits for those as well...
659      else // 1 or 0 hits.
660      {
661         const T rsq = sphere.getRadius() * sphere.getRadius();
662         const Vec<T, 3> dist = ray.getOrigin() - sphere.getCenter();
663         const T a = lengthSquared( dist ) - rsq;
664         const T b = lengthSquared( gmtl::Vec<T,3>(dist + ray.getDir()) ) - rsq;
665
666         bool inside1 = a <= T( 0 );
667         bool inside2 = b <= T( 0 );
668
669         // one point is inside
670         if (numhits == 1 && inside1 && !inside2)
671         {
672            t1 = t0;
673            t0 = T(0);
674            numhits = 2;
675            return true;
676         }
677         else if (numhits == 1 && !inside1 && inside2)
678         {
679            t1 = T(1);
680            numhits = 2;
681            return true;
682         }
683         // maybe both points are inside?
684         else if (inside1 && inside2) // 0 hits.
685         {
686            t0 = T(0);
687            t1 = T(1);
688            numhits = 2;
689            return true;
690         }
691      }
692      return result;
693   }
694
695   /**
696    * intersect ray/sphere-volume.
697    * register hits with both the surface and when the origin lands in the interior of the sphere.
698    * note: after calling this, you can find the intersection point with: ray.getOrigin() + ray.getDir() * t
699    *
700    * @param ray     the ray to test
701    * @param sphere  the sphere to test
702    * @return returns intersection point in t, and the number of hits
703    * @return numhits, t0, t1 are undefined if return value is false
704    */
705   template<typename T>
706   inline bool intersectVolume( const Sphere<T>& sphere, const Ray<T>& ray, int& numhits, float& t0, float& t1 )
707   {
708      bool result = intersect( sphere, ray, numhits, t0, t1 );
709      if (result && numhits == 2)
710      {
711         return true;
712      }
713      else
714      {
715         const T rsq = sphere.getRadius() * sphere.getRadius();
716         const Vec<T, 3> dist = ray.getOrigin() - sphere.getCenter();
717         const T a = lengthSquared( dist ) - rsq;
718
719         bool inside = a <= T( 0 );
720
721         // start point is inside
722         if (inside)
723         {
724            t1 = t0;
725            t0 = T(0);
726            numhits = 2;
727            return true;
728         }
729      }
730      return result;
731   }
732
733   /**
734    * Tests if the given plane and ray intersect with each other.
735    *
736    *  @param ray - the Ray
737    *  @param plane - the Plane
738    *  @param t - t gives you the intersection point:
739    *         isect_point = ray.origin + ray.dir * t
740    *
741    *  @return true if the ray intersects the plane.
742    *  @note If ray is parallel to plane: t=0, ret:true -> on plane, ret:false -> No hit
743    */
744   template<class DATA_TYPE>
745   bool intersect( const Plane<DATA_TYPE>& plane, const Ray<DATA_TYPE>& ray, DATA_TYPE& t )
746   {
747      const float eps(0.00001f);
748
749      // t = -(n·P + d)
750      Vec<DATA_TYPE, 3> N( plane.getNormal() );
751      float denom( dot(N,ray.getDir()) );
752      if(gmtl::Math::abs(denom) < eps)    // Ray parallel to plane
753      {
754         t = 0;
755         if(distance(plane, ray.mOrigin) < eps)     // Test for ray on plane
756         { return true; }
757         else
758         { return false; }
759      }
760      t = dot( N, Vec<DATA_TYPE,3>(N * plane.getOffset() - ray.getOrigin()) ) / denom;
761
762      return (DATA_TYPE)0 <= t;
763   }
764
765   /**
766    * Tests if the given plane and lineseg intersect with each other.
767    *
768    *  @param ray - the lineseg
769    *  @param plane - the Plane
770    *  @param t - t gives you the intersection point:
771    *         isect_point = lineseg.origin + lineseg.dir * t
772    *
773    *  @return true if the lineseg intersects the plane.
774    */
775   template<class DATA_TYPE>
776   bool intersect( const Plane<DATA_TYPE>& plane, const LineSeg<DATA_TYPE>& seg, DATA_TYPE& t )
777   {
778      bool res(intersect(plane, static_cast<Ray<DATA_TYPE> >(seg), t));
779      return res && t <= (DATA_TYPE)1.0;
780   }
781
782   /**
783    * Tests if the given triangle and ray intersect with each other.
784    *
785    *  @param tri - the triangle (ccw ordering)
786    *  @param ray - the ray
787    *  @param u,v - tangent space u/v coordinates of the intersection
788    *  @param t - an indicator of the intersection location
789    *  @post t gives you the intersection point:
790    *         isect = ray.dir * t + ray.origin
791    *  @return true if the ray intersects the triangle.
792    *  @see from http://www.acm.org/jgt/papers/MollerTrumbore97/code.html
793    */
794   template<class DATA_TYPE>
795   bool intersect( const Tri<DATA_TYPE>& tri, const Ray<DATA_TYPE>& ray,
796                        float& u, float& v, float& t )
797   {
798      const float EPSILON = (DATA_TYPE)0.00001f;
799      Vec<DATA_TYPE, 3> edge1, edge2, tvec, pvec, qvec;
800      float det,inv_det;
801
802      /* find vectors for two edges sharing vert0 */
803      edge1 = tri[1] - tri[0];
804      edge2 = tri[2] - tri[0];
805
806      /* begin calculating determinant - also used to calculate U parameter */
807      gmtl::cross( pvec, ray.getDir(), edge2 );
808
809      /* if determinant is near zero, ray lies in plane of triangle */
810      det = gmtl::dot( edge1, pvec );
811
812      if (det < EPSILON)
813         return false;
814
815      /* calculate distance from vert0 to ray origin */
816      tvec = ray.getOrigin() - tri[0];
817
818      /* calculate U parameter and test bounds */
819      u = gmtl::dot( tvec, pvec );
820      if (u < 0.0 || u > det)
821         return false;
822
823      /* prepare to test V parameter */
824      gmtl::cross( qvec, tvec, edge1 );
825
826      /* calculate V parameter and test bounds */
827      v = gmtl::dot( ray.getDir(), qvec );
828      if (v < 0.0 || u + v > det)
829         return false;
830
831      /* calculate t, scale parameters, ray intersects triangle */
832      t = gmtl::dot( edge2, qvec );
833      inv_det = ((DATA_TYPE)1.0) / det;
834      t *= inv_det;
835      u *= inv_det;
836      v *= inv_det;
837
838      // test if t is within the ray boundary (when t >= 0)
839      return t >= (DATA_TYPE)0;
840   }
841
842   /**
843    * Tests if the given triangle and line segment intersect with each other.
844    *
845    *  @param tri - the triangle (ccw ordering)
846    *  @param lineseg - the line segment
847    *  @param u,v - tangent space u/v coordinates of the intersection
848    *  @param t - an indicator of the intersection point
849    *  @post t gives you the intersection point:
850    *         isect = lineseg.getDir() * t + lineseg.getOrigin()
851    *
852    *  @return true if the line segment intersects the triangle.
853    */
854   template<class DATA_TYPE>
855   bool intersect( const Tri<DATA_TYPE>& tri, const LineSeg<DATA_TYPE>& lineseg,
856                        float& u, float& v, float& t )
857   {
858      const DATA_TYPE eps = (DATA_TYPE)0.0001010101;
859      DATA_TYPE l = length( lineseg.getDir() );
860      if (eps < l)
861      {
862         Ray<DATA_TYPE> temp( lineseg.getOrigin(), lineseg.getDir() );
863         bool result = intersect( tri, temp, u, v, t );
864         return result && t <= (DATA_TYPE)1.0;
865      }
866      else
867      {  return false; }
868   }
869}
870
871
872
873#endif
Note: See TracBrowser for help on using the repository browser.