home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Professional / OS2PRO194.ISO / os2 / graphic / qrt / intersec.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-26  |  13.3 KB  |  500 lines
  1.  
  2. /**********************************************************
  3.  
  4.   Line/Object intersection routines.  Routine returns
  5.   TRUE if object is hit, along with the nearest of the
  6.   possibly multiple intersections.  First parameter is
  7.   line, second is object, and third is pointer to parameter
  8.   on line for intersection (filled by routine).  Functions
  9.   are pointed at by entries in ObjData structure.
  10.  
  11.  **********************************************************/
  12.  
  13. #include "qrt.h"
  14.  
  15. /* #define INTERSECTDEBUG */
  16.  
  17. /**********************************************************
  18.  
  19.           Line/bounding box intersection test.
  20.  
  21.    Looks bad, but its pretty fast.  Many times we don't
  22.    even have to go through the whole routine if a miss
  23.    can be detected early.
  24.  
  25.  **********************************************************/
  26.  
  27. int LineBbox(line, bbox, t)
  28.   OBJ_PTR line, bbox;
  29.   float *t;
  30. {
  31.   register float tminx, tmaxx, tminy, tmaxy,
  32.                  tminz, tmaxz, tmin, tmax, t1,t2;
  33.  
  34.   /* this number is not really important, since nothing
  35.      cares about the exact location of the intersection */
  36.  
  37.   *t=10;
  38.  
  39. # ifdef ROBUST
  40.     if (line->type!=LINE) Error(INTERNAL_ERROR,301);
  41.     if (bbox->type!=BBOX) Error(INTERNAL_ERROR,302);
  42. # endif
  43.  
  44.   if (fabs(line->vect1.x) < SMALL) {
  45.     if ((bbox->lower.x < line->loc.x) &&
  46.         (bbox->upper.x > line->loc.x)) {
  47.           tminx = -BIG; tmaxx=BIG;
  48.         } else return(FALSE);
  49.  
  50.   } else {
  51.  
  52.     t1 = (bbox->lower.x-line->loc.x)/line->vect1.x;
  53.     t2 = (bbox->upper.x-line->loc.x)/line->vect1.x;
  54.     tminx = MIN(t1,t2);
  55.     tmaxx = MAX(t1,t2);
  56.     if (tmaxx<0) return(FALSE);
  57.   }
  58.  
  59.   if (fabs(line->vect1.y) < SMALL) {
  60.     if ((bbox->lower.y < line->loc.y) &&
  61.         (bbox->upper.y > line->loc.y)) {
  62.           tminy = -BIG; tmaxy=BIG;
  63.         } else return(FALSE);
  64.  
  65.   } else {
  66.  
  67.     t1 = (bbox->lower.y-line->loc.y)/line->vect1.y;
  68.     t2 = (bbox->upper.y-line->loc.y)/line->vect1.y;
  69.     tminy = MIN(t1,t2);
  70.     tmaxy = MAX(t1,t2);
  71.     if (tmaxy<0) return(FALSE);
  72.   }
  73.  
  74.   if (fabs(line->vect1.z) < SMALL) {
  75.     if ((bbox->lower.z < line->loc.z) &&
  76.         (bbox->upper.z > line->loc.z)) {
  77.           tminz = -BIG; tmaxz=BIG;
  78.         } else return(FALSE);
  79.  
  80.   } else {
  81.  
  82.     t1 = (bbox->lower.z-line->loc.z)/line->vect1.z;
  83.     t2 = (bbox->upper.z-line->loc.z)/line->vect1.z;
  84.     tminz = MIN(t1,t2);
  85.     tmaxz = MAX(t1,t2);
  86.     if (tmaxz<0) return(FALSE);
  87.   }
  88.  
  89.   tmin = MAX(MAX(tminx,tminy),tminz);
  90.   tmax = MIN(MIN(tmaxx,tmaxy),tmaxz);
  91.  
  92. # ifdef INTERSECTDEBUG
  93.     printf("LINEBBOX: dir = %f %f %f\n",line->vect1.x,
  94.                                         line->vect1.y,
  95.                                         line->vect1.z);
  96.  
  97.     printf("  tminx=%7.2f, tmaxx=%7.2f, tminy=%7.2f, tmaxy=%7.2f\n",
  98.             tminx, tmaxx, tminy, tmaxy);
  99.     printf("  tminz=%7.2f, tmaxz=%7.2f, tmin=%7.2f,  tmax=%f\n",
  100.             tminz, tmaxz, tmin, tmax);
  101. # endif
  102.  
  103.   if (tmax<0) return(FALSE);
  104.  
  105.   if (tmax<tmin) return(FALSE);
  106.  
  107. # ifdef INTERSECTDEBUG
  108.     printf("  HIT:\n");
  109. # endif
  110.  
  111.   return(TRUE);
  112. }
  113.  
  114. /**********************************************************
  115.  
  116.                Line/ring intersection test
  117.  
  118.      Similar to, but slower than parallelogram test
  119.  
  120.      Changed 11 Mar 89 to fix bug with planar position
  121.      computation.  Now uses Plane_Pos(), which is a
  122.      little slower than before.
  123.  
  124.  **********************************************************/
  125.  
  126. int LineRing(line, ring, t)
  127.   OBJ_PTR line, ring;
  128.   float *t;
  129. {
  130.   VECTOR         loc;
  131.   register float dot, rad;
  132.   float          pos1, pos2;
  133.  
  134. # ifdef ROBUST
  135.     if (line->type!=LINE) Error(INTERNAL_ERROR,303);
  136.     if (ring->type!=RING) Error(INTERNAL_ERROR,304);
  137. # endif
  138.  
  139.   dot  = DotProd((ring->precomp.norm),line->vect1);
  140.  
  141.   if (fabs(dot)<SMALL) return(FALSE);
  142.  
  143.   pos1 = ring->precomp.n1;
  144.   pos2 = DotProd((ring->precomp.norm),line->loc);
  145.  
  146.   *t=(pos1-pos2)/dot;
  147.  
  148. # ifdef INTERSECTDEBUG
  149.     printf("LINERING: t=%f\n", *t);
  150. # endif
  151.  
  152.   FindPos(&loc,line,*t);
  153.   Plane_Pos(ring,&loc,&pos1,&pos2,TRUE);
  154.  
  155.   rad = sqrt(sqr(pos1)+sqr(pos2));
  156.  
  157. # ifdef INTERSECTDEBUG
  158.     printf("LINERING  pos1,2 = %f %f\n",pos1,pos2);
  159.     printf("          radius = %f\n",rad);
  160.     printf("          R1,2   = %f %f\n",ring->vect3.x,ring->vect3.y);
  161. # endif
  162.  
  163.   if (rad<(ring->vect3.x) || rad>(ring->vect3.y))
  164.      return(FALSE);
  165.  
  166. # ifdef INTERSECTDEBUG
  167.     printf("  HIT:\n");
  168. # endif
  169.  
  170.   return(TRUE);
  171. }
  172.  
  173.  
  174. /**********************************************************
  175.  
  176.         Line/Parallelogram intersection test
  177.         Returns Parameter T for intersection
  178.  
  179.         Changed 11 Mar 89 to fix bug with planar position
  180.         computation.  Now uses Plane_Pos(), which is a
  181.         little slower than before.
  182.  
  183.  **********************************************************/
  184.  
  185. int LineParallelogram(line, para, t)
  186.   OBJ_PTR line, para;
  187.   float *t;
  188. {
  189.   VECTOR  loc;
  190.   float   dot, in1, in2;
  191.  
  192. # ifdef ROBUST
  193.     if (line->type!=LINE)          Error(INTERNAL_ERROR,305);
  194.     if (para->type!=PARALLELOGRAM) Error(INTERNAL_ERROR,306);
  195. # endif
  196.  
  197.   dot = DotProd((para->precomp.norm),line->vect1);
  198.  
  199.   if (fabs(dot)<SMALL) return(FALSE);
  200.  
  201.   in1 = para->precomp.n1;
  202.   in2 = DotProd((para->precomp.norm),line->loc);
  203.  
  204.   *t=(in1-in2)/dot;
  205.  
  206. # ifdef INTERSECTDEBUG
  207.     printf("LINEPARALL: t=%f\n", *t);
  208. # endif
  209.  
  210.   FindPos(&loc,line,*t);
  211.   Plane_Pos(para,&loc,&in1,&in2,TRUE);
  212.  
  213. # ifdef INTERSECTDEBUG
  214.     printf("LINEPARALL: in1,2 = %f %f\n",in1,in2);
  215. # endif
  216.  
  217.   if (!((in1>=0) && (in2>=0) && (in1<=1) && (in2<=1)))
  218.     return(FALSE);
  219.  
  220. # ifdef INTERSECTDEBUG
  221.     printf("  HIT:\n");
  222. # endif
  223.  
  224.   return(TRUE);
  225. }
  226.  
  227.  
  228. /**********************************************************
  229.  
  230.         Line/Triangle intersection test
  231.         Returns Parameter T for intersection
  232.  
  233.         Changed 11 Mar 89 to fix bug with planar position
  234.         computation. Now uses Plane_Pos(), which is a
  235.         little slower than before.
  236.  
  237.  **********************************************************/
  238.  
  239. int LineTriangle(line, obj, t)
  240.   OBJ_PTR line, obj;
  241.   float *t;
  242. {
  243.   VECTOR         loc;
  244.   register float dot;
  245.   float          in1, in2;
  246.  
  247. # ifdef ROBUST
  248.     if (line->type != LINE)      Error(INTERNAL_ERROR,307);
  249.     if (obj->type  != TRIANGLE)  Error(INTERNAL_ERROR,308);
  250. # endif
  251.  
  252.   dot = DotProd((obj->precomp.norm),line->vect1);
  253.  
  254.   if (fabs(dot)<SMALL) return(FALSE);
  255.  
  256.   in1 = obj->precomp.n1;
  257.   in2 = DotProd((obj->precomp.norm),line->loc);
  258.  
  259.   *t=(in1-in2)/dot;
  260.  
  261. # ifdef INTERSECTDEBUG
  262.     printf("LINETRIANGLE: t=%f\n", *t);
  263. # endif
  264.  
  265.   FindPos(&loc,line,*t);
  266.   Plane_Pos(obj,&loc,&in1,&in2,TRUE);
  267.  
  268. # ifdef INTERSECTDEBUG
  269.     printf("LINETRIANGLE: in1,2 = %f %f\n",in1,in2);
  270. # endif
  271.  
  272.   if (!((in1>=0) && (in2>=0) && (in1+in2<=1)))
  273.     return(FALSE);
  274.  
  275. # ifdef INTERSECTDEBUG
  276.     printf("  HIT:\n");
  277. # endif
  278.  
  279.   return(TRUE);
  280. }
  281.  
  282.  
  283. /**********************************************************
  284.  
  285.            Line/sphere intersection test
  286.         Returns parameter T for intersection
  287.  
  288.  **********************************************************/
  289.  
  290. int LineSphere(line, sph, t)
  291.   OBJ_PTR line, sph;
  292.   float *t;
  293. {
  294.   register float a,b,c,d,t1, tmpx,tmpy,tmpz;
  295.  
  296. # ifdef ROBUST
  297.     if (line->type!=LINE) Error(INTERNAL_ERROR,309);
  298.     if (!(sph->type==SPHERE || sph->type==LAMP))
  299.       Error(INTERNAL_ERROR,310);
  300. # endif
  301.  
  302.   tmpx = sph->loc.x-line->loc.x;
  303.   tmpy = sph->loc.y-line->loc.y;
  304.   tmpz = sph->loc.z-line->loc.z;
  305.  
  306.   c = sqr(tmpx)+ sqr(tmpy)+ sqr(tmpz) - (sph->precomp.n1);
  307.  
  308.   b = -2*(line->vect1.x*tmpx+                      /* find b */
  309.           line->vect1.y*tmpy+
  310.           line->vect1.z*tmpz);
  311.  
  312.   a = sqr(line->vect1.x)+                          /* find a */
  313.       sqr(line->vect1.y)+
  314.       sqr(line->vect1.z);
  315.  
  316.   d = sqr(b)-4.0*a*c;
  317.  
  318. # ifdef INTERSECTDEBUG
  319.     printf("LINESPHERE: a=%f, b=%f, c=%f, d=%f\n",a,b,c,d);
  320. # endif
  321.  
  322.   if (d<=0) return(FALSE);                          /* does sphere hit? */
  323.  
  324.   d=sqrt(d); *t=(-b+d)/(a+a);
  325.              t1=(-b-d)/(a+a);
  326.  
  327.   if (t1<*t && t1>SMALL) *t=t1;                     /* find 1st collision */
  328.  
  329.   if (*t > SMALL) {
  330.  
  331. #   ifdef INTERSECTDEBUG
  332.       printf("LINESPHERE: collision @ t=%f\n",*t);
  333. #   endif
  334.  
  335.     return(TRUE);
  336.   }
  337.  
  338.   return(FALSE);
  339. }
  340.  
  341.  
  342. /**********************************************************
  343.  
  344.         Line/quadratic intersection test
  345.         Returns parameter T for intersection
  346.  
  347.   newline is the input line translated and rotated so that
  348.   the quadratic is @ 0,0,0 and pointed up.
  349.  
  350.  **********************************************************/
  351.  
  352. int LineQuadratic(line, quad, t)
  353.   OBJ_PTR line, quad;
  354.   float *t;
  355. {
  356.   register   float a,b,c,d, t1;
  357.   VECTOR     loc, loc1, tempdir;
  358.   OBJ_STRUCT newline;
  359.  
  360. # ifdef ROBUST
  361.     if (line->type!=LINE)      Error(INTERNAL_ERROR,311);
  362.     if (quad->type!=QUADRATIC) Error(INTERNAL_ERROR,312);
  363. # endif
  364.  
  365.   newline.type=LINE;
  366.  
  367.   /*** translation transformation to newpos for line ***/
  368.  
  369.   VecSubtract(&(newline.loc),&(line->loc),&(quad->loc));
  370.  
  371.   if ((quad->vect1.x == 0) &&                  /* no rotation  */
  372.       (quad->vect1.y == 1) &&                  /* if aligned   */
  373.       (quad->vect1.z == 0))   {
  374.  
  375.       VectEQ(&(newline.vect1),&(line->vect1));
  376.  
  377.   } else {                                     /* here we must rot */
  378.  
  379. #   ifdef INTERSECTDEBUG
  380.  
  381.       printf("LINEQUADRATIC 0\n");
  382.       printf("  inline.loc  = %f %f %f\n",    line->loc.x,
  383.                                               line->loc.y,
  384.                                               line->loc.z);
  385.  
  386.       printf("  inline.dir  = %f %f %f\n",    line->vect1.x,
  387.                                               line->vect1.y,
  388.                                               line->vect1.z);
  389.  
  390.       printf("  newline.loc = %f %f %f\n",    newline.loc.x,
  391.                                               newline.loc.y,
  392.                                               newline.loc.z);
  393. #   endif
  394.  
  395.     Rot12( &(line->vect1),&(newline.vect1),    /* rot view direction */
  396.            quad->precomp.cos1,
  397.            quad->precomp.sin1,
  398.            quad->precomp.cos2,
  399.            quad->precomp.sin2 );
  400.  
  401.     Rot12( &(newline.loc),&(newline.loc),      /* rotate view location */
  402.            quad->precomp.cos1,
  403.            quad->precomp.sin1,
  404.            quad->precomp.cos2,
  405.            quad->precomp.sin2 );
  406.  
  407. #   ifdef INTERSECTDEBUG
  408.  
  409.       printf("LINEQUADRATIC 1\n");
  410.       printf("  inline.loc  = %f %f %f\n",    line->loc.x,
  411.                                               line->loc.y,
  412.                                               line->loc.z);
  413.  
  414.       printf("  inline.dir  = %f %f %f\n",    line->vect1.x,
  415.                                               line->vect1.y,
  416.                                               line->vect1.z);
  417.  
  418.       printf("  newline.loc = %f %f %f\n",    newline.loc.x,
  419.                                               newline.loc.y,
  420.                                               newline.loc.z);
  421.  
  422.       printf("  newline.dir = %f %f %f\n",    newline.vect1.x,
  423.                                               newline.vect1.y,
  424.                                               newline.vect1.z);
  425. #   endif
  426.  
  427.   }
  428.  
  429.   c = -(quad->cterm) + quad->vect2.x * sqr(newline.loc.x) +
  430.                        quad->vect2.y * sqr(newline.loc.y) +
  431.                        quad->vect2.z * sqr(newline.loc.z);
  432.  
  433.   b = 2*( quad->vect2.x * newline.loc.x * newline.vect1.x +
  434.           quad->vect2.y * newline.loc.y * newline.vect1.y +
  435.           quad->vect2.z * newline.loc.z * newline.vect1.z);
  436.  
  437.   a = quad->vect2.x * sqr(newline.vect1.x) +
  438.       quad->vect2.y * sqr(newline.vect1.y) +
  439.       quad->vect2.z * sqr(newline.vect1.z);
  440.  
  441.   d = sqr(b)-4.0*a*c;
  442.  
  443. # ifdef INTERSECTDEBUG
  444.     printf("LINEQUADRATIC 2: a=%f, b=%f, c=%f, d=%f\n",a,b,c,d);
  445.  
  446.     printf("               newpos = %f %f %f\n",newline.loc.x,
  447.                                                 newline.loc.y,
  448.                                                 newline.loc.z);
  449.  
  450.     printf("               newdir = %f %f %f\n",newline.vect1.x,
  451.                                                 newline.vect1.y,
  452.                                                 newline.vect1.z);
  453. # endif
  454.  
  455.   if (d<0) return(FALSE);                           /* we missed it */
  456.  
  457.  
  458.   d=sqrt(d); *t=(-b+d)/(a+a);
  459.              t1=(-b-d)/(a+a);
  460.  
  461.   FindPos(&loc,&newline,*t);                        /* find locations */
  462.   FindPos(&loc1,&newline,t1);
  463.  
  464.  
  465.   if ((loc.x < quad->lower.x) ||                    /* 1st in range ? */
  466.       (loc.x > quad->upper.x) ||
  467.       (loc.y < quad->lower.y) ||
  468.       (loc.y > quad->upper.y) ||
  469.       (loc.z < quad->lower.z) ||
  470.       (loc.z > quad->upper.z))    *t = -1;
  471.  
  472.   if ((loc1.x < quad->lower.x) ||                   /* 2nd in range ? */
  473.       (loc1.x > quad->upper.x) ||
  474.       (loc1.y < quad->lower.y) ||
  475.       (loc1.y > quad->upper.y) ||
  476.       (loc1.z < quad->lower.z) ||
  477.       (loc1.z > quad->upper.z))   t1 = -1;
  478.  
  479. # ifdef INTERSECTDEBUG
  480.     printf("    t,t1 = %f %f\n",*t,t1);
  481. # endif
  482.  
  483.   if (*t<=SMALL && t1 <=SMALL) return(FALSE);
  484.  
  485.   if (*t<=SMALL && t1>SMALL) *t=t1;
  486.   if (t1<*t && t1>SMALL)     *t=t1;   /* find 1st collision */
  487.  
  488.   if (*t>SMALL) {
  489.  
  490. #   ifdef INTERSECTDEBUG
  491.       printf("LINEQUADRATIC: collision @ t=%f\n",*t);
  492. #   endif
  493.  
  494.     return(TRUE);
  495.   }
  496.  
  497.   return(FALSE);
  498. }
  499.  
  500.