home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume18 / mtvraytrace / part02 / poly.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-26  |  5.3 KB  |  247 lines
  1. /***********************************************************************
  2.  * $Author: markv $
  3.  * $Revision: 1.2 $
  4.  * $Date: 88/10/04 14:32:25 $
  5.  * $Log:    poly.c,v $
  6.  * Revision 1.2  88/10/04  14:32:25  markv
  7.  * Renamed p1 and p2 to be poly_u and poly_v, which are better names.
  8.  * Also may have solved problems having to do with floating point roundoff
  9.  * when planes are parallel to bounding slabs.
  10.  * 
  11.  * Revision 1.1  88/09/11  11:00:42  markv
  12.  * Initial revision
  13.  * 
  14.  ***********************************************************************/
  15.  
  16. #include <stdio.h>
  17. #include <math.h>
  18. #include "defs.h"
  19. #include "extern.h"
  20.  
  21. typedef struct t_polydata {
  22.     int     poly_npoints ;
  23.     Vec    * poly_point ;
  24.     Vec    poly_normal ;
  25.     Flt     poly_d ;
  26.     Flt    poly_u, poly_v ;
  27. } PolyData ;
  28.  
  29. int PolyPrint ();
  30. int PolyIntersect ();
  31. int PolyNormal ();
  32.  
  33. ObjectProcs PolyProcs = {
  34.     PolyPrint,
  35.     PolyIntersect,
  36.     PolyNormal,
  37. } ;
  38.  
  39. int 
  40. PolyPrint(obj)
  41.  Object * obj ;
  42. {
  43.     int i ;
  44.     PolyData * pd ;
  45.  
  46.     pd = (PolyData *) obj -> o_data ;
  47.     printf("p %d\n", pd -> poly_npoints) ;
  48.     for (i = 0 ; i < pd -> poly_npoints ; i++) {
  49.         printf("%g %g %g\n", pd -> poly_point[i][0],
  50.                     pd -> poly_point[i][1],
  51.                     pd -> poly_point[i][2]) ;
  52.     }
  53. }
  54.  
  55. /***********************************************************************
  56.  * PolyIntersect(obj, ray, hit)
  57.  * 
  58.  * returns 1 if we hit the polygon, with the hit information in hit.
  59.  * Uses a version of Jordan's theorem to determine whether the point 
  60.  * is inside the polygon.
  61.  * The variable "crosses" will count the number of times that we
  62.  * cross the boundary of the curve.  If it is odd, we are inside.
  63.  *
  64.  ***********************************************************************/
  65.  
  66. PolyIntersect(obj, ray, hit)
  67.  Object * obj ;
  68.  Ray * ray ;
  69.  Isect * hit ;
  70. {
  71.     Flt n,d,t,m,b ;
  72.     Point V ;
  73.     int i, j, crosses = 0 ;
  74.     int qi, qj ;
  75.     int ri, rj ;
  76.     int u, v ;
  77.     PolyData * pd ;
  78.  
  79.     pd = (PolyData *) obj -> o_data ;
  80.     n = VecDot(ray -> P, pd -> poly_normal) + pd -> poly_d ;
  81.     d = VecDot(ray -> D, pd -> poly_normal) ;
  82.  
  83.     if ((Flt) fabs(d) < rayeps) {
  84.         return (0) ;
  85.     }
  86.  
  87.     t = - n / d ;
  88.     if (t < rayeps)
  89.         return 0 ;
  90.  
  91.     RayPoint(ray,t,V);
  92.  
  93.     u = pd -> poly_u ;
  94.     v = pd -> poly_v ;
  95.  
  96.     for (i = 0 ; i < pd -> poly_npoints ; i++) {
  97.  
  98.         j = (i + 1) % pd -> poly_npoints ;
  99.  
  100.         qi = 0 ; qj = 0 ;
  101.         ri = 0 ; rj = 0 ;
  102.  
  103.         if (pd -> poly_point[i][v] == pd -> poly_point[j][v])
  104.             continue ;        /*ignore horizontal lines */
  105.  
  106.         /*
  107.          * If we are both above, or both below the intersection point,
  108.          * go onto the next one.
  109.          */
  110.  
  111.         if (pd -> poly_point[i][v] < V[v])
  112.             qi = 1 ;
  113.         if (pd -> poly_point[j][v] < V[v])
  114.             qj = 1 ;
  115.         if (qi == qj)
  116.             continue ;
  117.  
  118.         /*
  119.          * We know one end point was above, and one was below.
  120.          * If theyare both to the left, then we crossed the line 
  121.          * to negative infinity, and we continue.
  122.          */
  123.         if (pd -> poly_point[i][u] < V[u])
  124.             ri = 1 ;
  125.          if (pd -> poly_point[j][u] < V[u])
  126.             rj = 1 ;
  127.  
  128.         if (ri & rj) {
  129.             crosses ++ ;
  130.             continue ;
  131.         }
  132.  
  133.         /*
  134.          * Otherwise, if we are both to the right, 
  135.          * we can continue without a cross.
  136.          */
  137.  
  138.         if ((ri|rj) == 0)
  139.             continue ;
  140.  
  141.  
  142.         /* 
  143.          * more difficult acceptance...
  144.          * We have a line segment which occurs with endpoints
  145.          * in diagonally opposite quadrants.  We must solve
  146.          * for the intersection, ie, where v = 0.
  147.          */
  148.  
  149.         m = (pd -> poly_point[j][v] - pd -> poly_point[i][v]) /
  150.             (pd -> poly_point[j][u] - pd -> poly_point[i][u]) ;
  151.         
  152.         b = (pd -> poly_point[j][v] - V[v]) - 
  153.             m * (pd -> poly_point[j][u] - V[u]);
  154.  
  155.         if ((-b/m) < rayeps)
  156.             crosses ++ ;
  157.     }
  158.  
  159.     if (crosses & 1) {
  160.         hit -> isect_t = t ;
  161.         hit -> isect_surf = obj -> o_surf ;
  162.         hit -> isect_prim = obj ;
  163.         hit -> isect_enter = 0 ;
  164.         return(1);
  165.     } else {
  166.         return(0);
  167.     }
  168. }
  169.  
  170. PolyNormal(obj, hit, P, N)
  171.  Object * obj ;
  172.  Isect * hit ;
  173.  Point P, N ;
  174. {
  175.  
  176.     PolyData * pd ;
  177.     pd = (PolyData *) obj -> o_data ;
  178.     VecCopy(pd -> poly_normal, N);
  179. }
  180.  
  181. Object *
  182. MakePoly(npoints, points)
  183.  int npoints ;
  184.  Vec * points ;
  185. {
  186.     Object * obj ;
  187.     PolyData * pd ;
  188.     Vec P1, P2 ;
  189.     Flt d, dmax, dmin ;
  190.     int i, j ;
  191.  
  192.     obj = (Object *) malloc (sizeof(Object)) ;
  193.     obj -> o_type = T_POLY ;
  194.     obj -> o_procs = & PolyProcs ;
  195.     obj -> o_surf = CurrentSurface ;
  196.  
  197.     pd = (PolyData *) malloc (sizeof(PolyData)) ;
  198.     pd -> poly_npoints = npoints ;
  199.     pd -> poly_point = points ;
  200.  
  201.     /*
  202.      * calculate the normal by giving various cross products...
  203.      */
  204.     
  205.     VecSub(pd -> poly_point[0], pd -> poly_point[1], P1) ;
  206.     VecSub(pd -> poly_point[2], pd -> poly_point[1], P2) ;
  207.  
  208.     VecCross(P1, P2, pd -> poly_normal) ;
  209.     VecNormalize(pd -> poly_normal) ;
  210.  
  211.     if (fabs(pd -> poly_normal[0]) > fabs(pd -> poly_normal[1])
  212.         && fabs(pd -> poly_normal[0]) > fabs(pd -> poly_normal[2])) {
  213.         pd -> poly_u = 1 ;
  214.         pd -> poly_v = 2 ;
  215.     } else if (fabs(pd -> poly_normal[1]) > fabs(pd -> poly_normal[0]) 
  216.         && fabs(pd -> poly_normal[1]) > fabs(pd -> poly_normal[2])) {
  217.         pd -> poly_u = 0 ;
  218.         pd -> poly_v = 2 ;
  219.     } else {
  220.         pd -> poly_u = 0 ;
  221.         pd -> poly_v = 1 ;
  222.     }
  223.  
  224.     pd -> poly_d = - VecDot(pd -> poly_normal, pd -> poly_point[0]) ;
  225.  
  226.     obj -> o_data = (void *) pd ;
  227.  
  228.     /*
  229.      * now, calculate the values of 
  230.      * the dmin and dmax 'es for the globally defined slabs...
  231.      */
  232.     
  233.     for (i = 0 ; i < NSLABS ; i ++) {
  234.         dmin = HUGE ;
  235.         dmax = - HUGE ;
  236.  
  237.         for (j = 0 ; j < pd -> poly_npoints ; j ++) {
  238.             d = VecDot(Slab[i], pd -> poly_point[j]) ;
  239.             if (d < dmin) dmin = d ;
  240.             if (d > dmax) dmax = d ;
  241.         }
  242.         obj -> o_dmin[i] = dmin - rayeps ;
  243.         obj -> o_dmax[i] = dmax + rayeps ;
  244.     }
  245.     return(obj) ;
  246. }
  247.