home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume15 / ggems / part03 / LineEdge.c < prev    next >
C/C++ Source or Header  |  1990-10-14  |  4KB  |  121 lines
  1. /* 
  2. Fast Line-Edge Intersections on a Uniform Grid 
  3. by Andrew Shapira
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7. #include "GraphicsGems.h"
  8.  
  9. #define OCTANT(f1, f2, f3, f4, f5, i1, s1, r1, r2) \
  10.     for (f1, f2, f3, nr = 0; f4; f5) { \
  11.         if (nr < liconst) { \
  12.             if (i1) \
  13.                 r1(&C); \
  14.             else \
  15.                 vertex(&C); \
  16.         } \
  17.         else { \
  18.             s1; \
  19.             if (nr -= liconst) { \
  20.                 r2(&C); \
  21.                 r1(&C); \
  22.             } \
  23.             else \
  24.                 vertex(&C); \
  25.         } \
  26.     }
  27.  
  28. find_intersections(Pptr, Qptr)
  29. IntPoint2   *Pptr, *Qptr;       /* P and Q as described in gem text */
  30. {
  31.     IntPoint2   P, Q;           /* P and Q, dereferenced for speed */
  32.     IntPoint2   C;              /* current grid point */
  33.     int         nr;             /* remainder */
  34.     int         deltax, deltay; /* Q.x - P.x, Q.y - P.y */
  35.     int         liconst;          /* loop-invariant constant */
  36.  
  37.     P.x = Pptr->x;
  38.     P.y = Pptr->y;
  39.     Q.x = Qptr->x;
  40.     Q.y = Qptr->y;
  41.     deltax = Q.x - P.x;
  42.     deltay = Q.y - P.y;
  43.  
  44.  
  45.     /* for reference purposes, let theta be the angle from P to Q */
  46.  
  47.     if ((deltax >= 0) && (deltay >= 0) && (deltay < deltax)) 
  48.                         /* 0 <= theta < 45 */
  49.         OCTANT(C.x = P.x + 1, C.y = P.y, liconst = deltax - deltay, 
  50.             C.x < Q.x, C.x++, nr += deltay, C.y++, up, left)
  51.     else if ((deltax > 0) && (deltay >= 0) && (deltay >= deltax)) 
  52.                        /* 45 <= theta < 90 */
  53.         OCTANT(C.y = P.y + 1, C.x = P.x, liconst = deltay - deltax,
  54.              C.y < Q.y, C.y++, nr += deltax, C.x++, right, down)
  55.     else if ((deltax <= 0) && (deltay >= 0) && (deltay > -deltax))
  56.                        /* 90 <= theta < 135 */
  57.         OCTANT(C.y = P.y + 1, C.x = P.x, liconst = deltay + deltax,
  58.              C.y < Q.y, C.y++, nr -= deltax, C.x--, left, down)
  59.     else if ((deltax <= 0) && (deltay > 0) && (deltay <= -deltax)) 
  60.                        /* 135 <= theta < 180 */
  61.         OCTANT(C.x = P.x - 1, C.y = P.y, liconst = -deltax - deltay,
  62.              C.x > Q.x, C.x--, nr += deltay, C.y++, up, right)
  63.     else if ((deltax <= 0) && (deltay <= 0) && (deltay > deltax))
  64.                       /* 180 <= theta < 225 */
  65.         OCTANT(C.x = P.x - 1, C.y = P.y, liconst = -deltax + deltay, 
  66.             C.x > Q.x, C.x--, nr -= deltay, C.y--, down, right)
  67.     else if ((deltax < 0) && (deltay <= 0) && (deltay <= deltax))
  68.                       /* 225 <= theta < 270 */
  69.         OCTANT(C.y = P.y - 1, C.x = P.x, liconst = -deltay + deltax,
  70.             C.y > Q.y, C.y--, nr -= deltax, C.x--, left, up)
  71.     else if ((deltax >= 0) && (deltay <= 0) && (-deltay > deltax))
  72.                      /* 270 <= theta < 315 */
  73.         OCTANT(C.y = P.y - 1, C.x = P.x, liconst = -deltay - deltax, 
  74.             C.y > Q.y, C.y--, nr += deltax, C.x++, right, up)
  75.     else if ((deltax >= 0) && (deltay < 0) && (-deltay <= deltax))
  76.                      /* 315 <= theta < 360 */
  77.         OCTANT(C.x = P.x + 1, C.y = P.y, liconst = deltax + deltay,
  78.              C.x < Q.x, C.x++, nr -= deltay, C.y--, down, left)
  79.     else {}                    /* P = Q */
  80. }
  81.  
  82. vertex(I)
  83. IntPoint2   *I;
  84. {
  85.     /* Note: replace printf with code to process vertex, if desired */
  86.     (void) printf("vertex at %d %d\n", I->x, I->y);
  87. }
  88.  
  89. left(I)
  90. IntPoint2   *I;
  91. {
  92.  
  93.     /* Note: replace printf with code to process leftward */     
  94.     /* intersection, if desired */
  95.     (void) printf("left from %d %d\n", I->x, I->y);
  96. }
  97.  
  98. up(I)
  99. IntPoint2   *I;
  100. {
  101.     /* Note: replace printf with code to process upward */
  102.     /* intersection, if desired */
  103.     (void) printf("up from %d %d\n", I->x, I->y);
  104. }
  105.  
  106. right(I)
  107. IntPoint2   *I;
  108. {
  109.     /* Note: replace printf with code to process rightward */
  110.     /* intersection, if desired */
  111.     (void) printf("right from %d %d\n", I->x, I->y);
  112. }
  113.  
  114. down(I)
  115. IntPoint2   *I;
  116. {
  117.     /* Note: replace printf with code to process downward */
  118.     /* intersection, if desired */
  119.     (void) printf("down from %d %d\n", I->x, I->y);
  120. }
  121.