home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 8 / CDASC08.ISO / NEWS / RADIANCE / SRC / OT / O_CONE.C < prev    next >
C/C++ Source or Header  |  1993-10-07  |  3KB  |  117 lines
  1. /* Copyright (c) 1986 Regents of the University of California */
  2.  
  3. #ifndef lint
  4. static char SCCSid[] = "@(#)o_cone.c 2.1 11/12/91 LBL";
  5. #endif
  6.  
  7. /*
  8.  *  o_cone.c - routines for intersecting cubes with cones.
  9.  *
  10.  *     2/3/86
  11.  */
  12.  
  13. #include  "standard.h"
  14.  
  15. #include  "octree.h"
  16.  
  17. #include  "object.h"
  18.  
  19. #include  "cone.h"
  20.  
  21. #define  ROOT3        1.732050808
  22.  
  23. /*
  24.  *     The algorithm used to detect cube intersection with cones is
  25.  *  recursive.  First, we approximate the cube to be a sphere.  Then
  26.  *  we test for cone intersection with the sphere by testing the
  27.  *  segment of the cone which is nearest the sphere's center.
  28.  *     If the cone has points within the cube's bounding sphere,
  29.  *  we must check for intersection with the cube.  This is done with
  30.  *  the 3D line clipper.  The same cone segment is used in this test.
  31.  *  If the clip fails, we still cannot be sure there is no intersection,
  32.  *  so we subdivide the cube and recurse.
  33.  *     If none of the sub-cubes intersect, then our cube does not intersect.
  34.  */
  35.  
  36. extern double  mincusize;        /* minimum cube size */
  37.  
  38.  
  39. o_cone(o, cu)            /* determine if cone intersects cube */
  40. OBJREC  *o;
  41. register CUBE  *cu;
  42. {
  43.     double  dist2lseg(), findcseg();
  44.     CONE  *co;
  45.     FVECT  ep0, ep1;
  46.     FVECT  cumin, cumax;
  47.     CUBE  cukid;
  48.     double  r;
  49.     FVECT  p;
  50.     register int  i, j;
  51.                     /* get cone arguments */
  52.     co = getcone(o, 0);
  53.                     /* get cube center */
  54.     r = cu->cusize * 0.5;
  55.     for (i = 0; i < 3; i++)
  56.         p[i] = cu->cuorg[i] + r;
  57.     r *= ROOT3;            /* bounding radius for cube */
  58.  
  59.     if (findcseg(ep0, ep1, co, p) > 0.0) {
  60.                     /* check min. distance to cone */
  61.         if (dist2lseg(p, ep0, ep1) > (r+FTINY)*(r+FTINY))
  62.             return(O_MISS);
  63. #ifdef  STRICT
  64.                     /* get cube boundaries */
  65.         for (i = 0; i < 3; i++)
  66.             cumax[i] = (cumin[i] = cu->cuorg[i]) + cu->cusize;
  67.                     /* closest segment intersects? */
  68.         if (clip(ep0, ep1, cumin, cumax))
  69.             return(O_HIT);
  70.     }
  71.                     /* check sub-cubes */
  72.     cukid.cusize = cu->cusize * 0.5;
  73.     if (cukid.cusize < mincusize)
  74.         return(O_HIT);        /* cube too small */
  75.     cukid.cutree = EMPTY;
  76.  
  77.     for (j = 0; j < 8; j++) {
  78.         for (i = 0; i < 3; i++) {
  79.             cukid.cuorg[i] = cu->cuorg[i];
  80.             if (1<<i & j)
  81.                 cukid.cuorg[i] += cukid.cusize;
  82.         }
  83.         if (o_cone(o, &cukid))
  84.             return(O_HIT);    /* sub-cube intersects */
  85.     }
  86.     return(O_MISS);            /* no intersection */
  87. #else
  88.     }
  89.     return(O_HIT);            /* assume intersection */
  90. #endif
  91. }
  92.  
  93.  
  94. double
  95. findcseg(ep0, ep1, co, p)    /* find line segment from cone closest to p */
  96. FVECT  ep0, ep1;
  97. register CONE  *co;
  98. FVECT  p;
  99. {
  100.     double  d;
  101.     FVECT  v;
  102.     register int  i;
  103.                     /* find direction from axis to point */
  104.     for (i = 0; i < 3; i++)
  105.         v[i] = p[i] - CO_P0(co)[i];
  106.     d = DOT(v, co->ad);
  107.     for (i = 0; i < 3; i++)
  108.         v[i] = v[i] - d*co->ad[i];
  109.     d = normalize(v);
  110.     if (d > 0.0)            /* find endpoints of segment */
  111.         for (i = 0; i < 3; i++) {
  112.             ep0[i] = CO_R0(co)*v[i] + CO_P0(co)[i];
  113.             ep1[i] = CO_R1(co)*v[i] + CO_P1(co)[i];
  114.         }
  115.     return(d);            /* return distance from axis */
  116. }
  117.