home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / gems / gemsii / raycphdr.c < prev    next >
C/C++ Source or Header  |  1991-08-26  |  3KB  |  110 lines
  1. /* Ray-Convex Polyhedron Intersection Test by Eric Haines, erich@eye.com
  2.  *
  3.  * This test checks the ray against each face of a polyhedron, checking whether
  4.  * the set of intersection points found for each ray-plane intersection
  5.  * overlaps the previous intersection results.  If there is no overlap (i.e.
  6.  * no line segment along the ray that is inside the polyhedron), then the
  7.  * ray misses and returns 0; else 1 is returned if the ray is entering the
  8.  * polyhedron, -1 if the ray originates inside the polyhedron.  If there is
  9.  * an intersection, the distance and the normal of the face hit is returned.
  10.  */
  11.  
  12. #include <math.h>
  13. #include "GraphicsGems.h"
  14.  
  15. #ifndef    HUGE_VAL
  16. #define    HUGE_VAL    1.7976931348623157e+308
  17. #endif
  18.  
  19. typedef struct Point4Struct {    /* 4d point */
  20.     double x, y, z, w;
  21.     } Point4;
  22.  
  23. /* fast macro version of V3Dot, usable with Point4 */
  24. #define DOT3( a, b )    ( (a)->x*(b)->x + (a)->y*(b)->y + (a)->z*(b)->z )
  25.  
  26. /* return codes */
  27. #define    MISSED         0
  28. #define    FRONTFACE     1
  29. #define    BACKFACE    -1
  30.  
  31. int    RayCvxPolyhedronInt( org, dir, tmax, phdrn, ph_num, tresult, norm )
  32. Point3    *org, *dir ;    /* origin and direction of ray */
  33. double    tmax ;        /* maximum useful distance along ray */
  34. Point4    *phdrn ;    /* list of planes in convex polyhedron */
  35. int    ph_num ;    /* number of planes in convex polyhedron */
  36. double    *tresult ;    /* returned: distance of intersection along ray */
  37. Point3    *norm ;        /* returned: normal of face hit */
  38. {
  39. Point4    *pln ;            /* plane equation */
  40. double    tnear, tfar, t, vn, vd ;
  41. int    fnorm_num, bnorm_num ;    /* front/back face # hit */
  42.  
  43.     tnear = -HUGE_VAL ;
  44.     tfar = tmax ;
  45.  
  46.     /* Test each plane in polyhedron */
  47.     for ( pln = &phdrn[ph_num-1] ; ph_num-- ; pln-- ) {
  48.     /* Compute intersection point T and sidedness */
  49.     vd = DOT3( dir, pln ) ;
  50.     vn = DOT3( org, pln ) + pln->w ;
  51.     if ( vd == 0.0 ) {
  52.         /* ray is parallel to plane - check if ray origin is inside plane's
  53.            half-space */
  54.         if ( vn > 0.0 )
  55.         /* ray origin is outside half-space */
  56.         return ( MISSED ) ;
  57.     } else {
  58.         /* ray not parallel - get distance to plane */
  59.         t = -vn / vd ;
  60.         if ( vd < 0.0 ) {
  61.         /* front face - T is a near point */
  62.         if ( t > tfar ) return ( MISSED ) ;
  63.         if ( t > tnear ) {
  64.             /* hit near face, update normal */
  65.             fnorm_num = ph_num ;
  66.             tnear = t ;
  67.         }
  68.         } else {
  69.         /* back face - T is a far point */
  70.         if ( t < 0.0 ) return ( MISSED ) ;
  71.         if ( t < tfar ) {
  72.             /* hit near face, update normal */
  73.             bnorm_num = ph_num ;
  74.             tfar = t ;
  75.         }
  76.         }
  77.     }
  78.     }
  79.  
  80.     /* survived all tests */
  81.     /* Note: if ray originates on polyhedron, may want to change 0.0 to some
  82.      * epsilon to avoid intersecting the originating face.
  83.      */
  84.     if ( tnear >= 0.0 ) {
  85.     /* outside, hitting front face */
  86.     *norm = *(Point3 *)&phdrn[fnorm_num] ;
  87.     *tresult = tnear ;
  88.     return ( FRONTFACE ) ;
  89.     } else {
  90.     if ( tfar < tmax ) {
  91.         /* inside, hitting back face */
  92.         *norm = *(Point3 *)&phdrn[bnorm_num] ;
  93.         *tresult = tfar ;
  94.         return ( BACKFACE ) ;
  95.     } else {
  96.         /* inside, but back face beyond tmax */
  97.         return ( MISSED ) ;
  98.     }
  99.     }
  100. }
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.