home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 2 / 2213 / poly.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-12-28  |  4.5 KB  |  253 lines
  1.  
  2. /*
  3.  * poly.c - This module conatins all of the code that relates to polygons.
  4.  * 
  5.  * Copyright (C) 1990, Kory Hamzeh
  6.  */
  7.  
  8. #include <stdio.h>
  9. #include <malloc.h>
  10. #include <math.h>
  11.  
  12. #include "rt.h"
  13. #include "externs.h"
  14.  
  15.  
  16. int             Poly_intersect(), Poly_normal();
  17. extern int      line;
  18.  
  19. /*
  20.  * Build_poly()
  21.  * 
  22.  * Given some info on a polygon, build the entire object structure.
  23.  */
  24.  
  25. Build_poly(p)
  26. POLYGON        *p;
  27. {
  28.     OBJECT         *o;
  29.     VECTOR          pt1, pt2;
  30.     int             i;
  31.  
  32.     if (nobjects == MAX_PRIMS)
  33.     {
  34.         fprintf(stderr, "%s: too many objects specified\n", my_name);
  35.         exit(1);
  36.     }
  37.  
  38.     if ((o = (OBJECT *) malloc(sizeof(OBJECT))) == NULL)
  39.     {
  40.         fprintf(stderr, "%s: malloc failed\n", my_name);
  41.         exit(1);
  42.     }
  43.  
  44.     o->type = T_POLYGON;
  45.     o->obj = p;
  46.     o->surf = cur_surface;
  47.     o->inter = Poly_intersect;
  48.     o->normal = Poly_normal;
  49.  
  50.     objects[nobjects++] = o;
  51.  
  52.     /*
  53.      * Calculate the normals and the D coefficient by various cross
  54.      * products.
  55.      */
  56.  
  57.     VecSub(p->points[1], p->points[0], pt1);
  58.     VecSub(p->points[2], p->points[0], pt2);
  59.     VecCross(pt1, pt2, p->normal);
  60.     VecNormalize(&p->normal);
  61.  
  62.     p->d = -VecDot(p->normal, p->points[0]);
  63.  
  64.     for (i = 0; i < p->npoints; i++)
  65.     {
  66.         if (fabs(VecDot(p->points[i], p->normal) + p->d) > MIN_T)
  67.         {
  68. #ifdef CHECK_COORD_ORDER
  69.             fprintf(stderr, "%s: coordinate given in wrong order on line %d\n",
  70.                 my_name, line - p->npoints);
  71. #endif
  72.         }
  73.     }
  74.  
  75.     /*
  76.      * Figure out the most dominant normal.
  77.      */
  78.  
  79.     if (fabs(p->normal.x) > fabs(p->normal.y) &&
  80.         fabs(p->normal.x) > fabs(p->normal.z))
  81.     {
  82.         p->p1 = 1;
  83.         p->p2 = 2;
  84.     }
  85.     else if (fabs(p->normal.y) > fabs(p->normal.x) &&
  86.          fabs(p->normal.y) > fabs(p->normal.z))
  87.     {
  88.         p->p1 = 0;
  89.         p->p2 = 2;
  90.     }
  91.     else
  92.     {
  93.         p->p1 = 0;
  94.         p->p2 = 1;
  95.     }
  96.  
  97.     /*
  98.      * Setup the min and the max values for the bouding box.
  99.      */
  100.  
  101.     o->b_min.x = o->b_min.y = o->b_min.z = HUGE;
  102.     o->b_max.x = o->b_max.y = o->b_max.z = -HUGE;
  103.  
  104.     for (i = 0; i < p->npoints; i++)
  105.     {
  106.         o->b_min.x = MIN(p->points[i].x, o->b_min.x);
  107.         o->b_min.y = MIN(p->points[i].y, o->b_min.y);
  108.         o->b_min.z = MIN(p->points[i].z, o->b_min.z);
  109.  
  110.         o->b_max.x = MAX(p->points[i].x, o->b_max.x);
  111.         o->b_max.y = MAX(p->points[i].y, o->b_max.y);
  112.         o->b_max.z = MAX(p->points[i].z, o->b_max.z);
  113.     }
  114. }
  115.  
  116.  
  117.  
  118. /*
  119.  * Poly_intersect()
  120.  * 
  121.  * Check given ploy for intersection with given ray. Return TRUE if an
  122.  * intersection takes place.
  123.  */
  124.  
  125. Poly_intersect(obj, ray, inter)
  126. OBJECT         *obj;
  127. RAY            *ray;
  128. INTERSECT      *inter;
  129. {
  130.     POLYGON        *p;
  131.     VECTOR          ipoint;
  132.     double          vo, vd;
  133.     double          t, b, m;
  134.     double          pi[3], pj[3], ip[3];
  135.     int             qi, qj, ri, rj, i, j;
  136.     int             n1, n2, l;
  137.  
  138.  
  139.     p = obj->obj;
  140.  
  141.     /*
  142.      * First check to see if this ray hit the plane which this polygon
  143.      * resides on.
  144.      */
  145.  
  146.     vd = VecDot(ray->dir, p->normal);
  147.  
  148.     if (fabs(vd) < MIN_T)
  149.         return (0);
  150.  
  151.     vo = VecDot(ray->pos, p->normal) + p->d;
  152.  
  153.     t = -vo / vd;
  154.     if (t < MIN_T)
  155.         return (0);
  156.  
  157.     /*
  158.      * OK. We now know that this ray hit the plane in which this polygon
  159.      * resides on. Now we need to check to see if it hits the polygon. We
  160.      * use the Jordon Curve Theorem to do this.
  161.      */
  162.  
  163.     /* get the point of intersection on the plane */
  164.     VecAddS(t, ray->dir, ray->pos, ipoint);
  165.     ip[0] = ipoint.x;
  166.     ip[1] = ipoint.y;
  167.     ip[2] = ipoint.z;
  168.  
  169.     /* get the dominant normals */
  170.     n1 = p->p1;
  171.     n2 = p->p2;
  172.  
  173.     /* ok, do it */
  174.  
  175.     l = 0;
  176.     for (i = 0; i < p->npoints; i++)
  177.     {
  178.         j = (i + 1) % p->npoints;
  179.         qi = qj = ri = rj = 0;
  180.  
  181.         pi[0] = p->points[i].x;
  182.         pi[1] = p->points[i].y;
  183.         pi[2] = p->points[i].z;
  184.  
  185.         pj[0] = p->points[j].x;
  186.         pj[1] = p->points[j].y;
  187.         pj[2] = p->points[j].z;
  188.  
  189.         /* check for horizontal line and ignore them */
  190.         if (pi[n2] == pj[n2])
  191.             continue;
  192.  
  193.         if (pi[n2] < ip[n2])
  194.             qi = 1;
  195.         if (pj[n2] < ip[n2])
  196.             qj = 1;
  197.         if (qi == qj)
  198.             continue;
  199.  
  200.         if (pi[n1] < ip[n1])
  201.             ri = 1;
  202.         if (pj[n1] < ip[n1])
  203.             rj = 1;
  204.  
  205.         if (ri & rj)
  206.         {
  207.             ++l;    /* crossed an edge         */
  208.             continue;
  209.         }
  210.  
  211.         if (!(rj | ri))
  212.             continue;
  213.  
  214.         m = (pj[n2] - pi[n2]) / (pj[n1] - pi[n1]);
  215.         b = (pj[n2] - ip[n2]) - (m * (pj[n1] - ip[n1]));
  216.  
  217.         if ((-b / m) < MIN_T)
  218.             ++l;
  219.     }
  220.  
  221.     if ((l % 2) == 0)
  222.         return (0);
  223.  
  224.     /*
  225.      * We have crossed an odd number of edges, that means that we have a
  226.      * hit!!!
  227.      */
  228.  
  229.     inter->t = t;
  230.     inter->obj = obj;
  231.     inter->inside = 0;
  232.  
  233.     return (1);
  234. }
  235.  
  236.  
  237. /*
  238.  * Poly_normal()
  239.  * 
  240.  * Return the normal to a polygon at a given point along the surface.
  241.  */
  242.  
  243. Poly_normal(poly, ray, ip, normal)
  244. POLYGON        *poly;
  245. RAY            *ray;
  246. VECTOR         *ip;
  247. VECTOR         *normal;
  248. {
  249.     VecCopy(poly->normal, *normal);
  250.     if (VecDot(ray->dir, *normal) >= 0)
  251.         VecNegate(*normal);
  252. }
  253.