home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1994 March / Source_Code_CD-ROM_Walnut_Creek_March_1994.iso / netsrcs / lng_bars.txt < prev    next >
Internet Message Format  |  1987-03-23  |  8KB
  1. From sbw@naucse.UUCP Mon Mar 23 13:30:21 1987
  2. Path: seismo!rutgers!sri-unix!hplabs!hao!noao!arizona!naucse!sbw
  3. From: sbw@naucse.UUCP (Steve Wampler)
  4. Newsgroups: net.sources
  5. Subject: Liang-Barsky Polygon Clipping (2 C versions)
  6. Message-ID: <270@naucse.UUCP>
  7. Date: 23 Mar 87 18:30:21 GMT
  8. Organization: Northern Arizona University, Flagstaff, Arizona
  9. Lines: 294
  10.  
  11. The following C functions are two versions of the Liang-Barsky
  12. polygon clipping algorithm.  The first is directly from their
  13. paper in CACM (and the corrigenda that followed).  The second
  14. is slightly modified and seems to run about 6% quicker (assuming
  15. floating point hardware).
  16.  
  17. #___________cut mark
  18.  
  19. /* Liang-Barsky Polygon Clipping [CACM, Vol 26 (Nov, 1983)]
  20.  *    (with corrections from [CACM (April, 1984)])
  21.  */
  22.  
  23. /*   Note that this assumes the last point == the first in the
  24.  *    polygon representation the code in the article adds the
  25.  *    last point in at the start of the algorithm (probably
  26.  *    a better approach).
  27.  */
  28.  
  29.     /* The following include brings in some macro definitions
  30.      * for accessing information about a polygon:
  31.      *
  32.      *   NPNTS()  is the number of vertices in the polygon
  33.      *            (counting first point twice)
  34.          *
  35.          *   GETPNT() accesses the specified point out of the
  36.      *              polygon.
  37.      *
  38.      *   XCOORD/YCOORD() access the x(y)-coordinate in a point
  39.      *
  40.      * Macros were used because this code must ultimately tie
  41.      *  into my wife's animation package, and I don't know
  42.      *  how she is going to represent polygons yet.
  43.      */
  44.  
  45. # include "pln.h"
  46.  
  47. # define INFINITY    (1.0e+30)
  48.  
  49.     /* add a new vertex into the output polygon */
  50.  
  51. # define add(x,y) {\
  52.                    XCOORD(GETPNT(npoly,npnt)) = x;\
  53.                    YCOORD(GETPNT(npoly,npnt)) = y;\
  54.                    ++npnt;\
  55.                   }
  56.  
  57.     /* window bounds (xleft,ybottom), (xright,ytop) */
  58. extern float wx1,wy1,  wx2,wy2;
  59.  
  60.     /* The Liang-Barsky Polygon Clipping Algorithm */
  61. fclip(opoly,npoly)
  62.    PLN *opoly, *npoly;
  63.  
  64.    {
  65.    register int i, npnt;
  66.    float deltax, deltay, xin,xout,  yin,yout;
  67.    float tinx,tiny,  toutx,touty,  tin1, tin2,  tout1,tout2;
  68.    float x1,y1, x2,y2;
  69.    
  70.    npnt = 0;
  71.  
  72.    for (i = 0; i < NPNTS(opoly)-1; ++i) {
  73.  
  74.       x1 = XCOORD(GETPNT(opoly,i));
  75.       y1 = YCOORD(GETPNT(opoly,i));
  76.       x2 = XCOORD(GETPNT(opoly,i+1));
  77.       y2 = YCOORD(GETPNT(opoly,i+1));
  78.  
  79.       deltax = x2-x1;
  80.       deltay = y2-y1;
  81.  
  82.       if (deltax > 0 || (deltax == 0 && x1>wx2)) { /*  points to right */
  83.          xin = wx1;
  84.          xout = wx2;
  85.          }
  86.       else {
  87.          xin = wx2;
  88.          xout = wx1;
  89.          }
  90.       if (deltay > 0 || (deltay == 0 && y1>wy2)) { /*  points up */
  91.          yin = wy1;
  92.          yout = wy2;
  93.          }
  94.       else {
  95.          yin = wy2;
  96.          yout = wy1;
  97.          }
  98.  
  99.       tinx = (deltax != 0) ? ((xin - x1)/deltax) : -INFINITY ;
  100.       tiny = (deltay != 0) ? ((yin - y1)/deltay) : -INFINITY ;
  101.    
  102.       if (tinx < tiny) {    /* hits x first */
  103.          tin1 = tinx;
  104.          tin2 = tiny;
  105.          }
  106.       else            /* hits y first */
  107.          {
  108.          tin1 = tiny;
  109.          tin2 = tinx;
  110.          }
  111.  
  112.       if (1 >= tin1) {
  113.          if (0 < tin1) {
  114.             add(xin,yin);
  115.             }
  116.          if (1 >= tin2) {
  117.         if (deltax != 0) toutx = (xout-x1)/deltax;
  118.         else {
  119.                if (wx1 <= x1 && x1 <= wx2) toutx = INFINITY;
  120.                else                        toutx = -INFINITY;
  121.            }
  122.         if (deltay != 0) touty = (yout-y1)/deltay;
  123.         else {
  124.                if (wy1 <= y1 && y1 <= wy2) touty = INFINITY;
  125.                else                        touty = -INFINITY;
  126.            }
  127.  
  128.         tout1 = (toutx < touty) ? toutx : touty ;
  129.    
  130.             if (0 < tin2 || 0 < tout1) {
  131.                if (tin2 <= tout1) {
  132.                   if (0 < tin2) {
  133.                      if (tinx > tiny) {
  134.                         add (xin, y1+tinx*deltay);
  135.                         }
  136.                      else {
  137.                         add (x1 + tiny*deltax, yin);
  138.                         }
  139.                      }
  140.                   if (1 > tout1) {
  141.                      if (toutx < touty) {
  142.                         add (xout, y1+toutx*deltay);
  143.                         }
  144.                      else {
  145.                         add (x1 + touty*deltax, yout);
  146.                         }
  147.                      }
  148.                   else {
  149.                      add (x2,y2);
  150.                      }
  151.                   }
  152.                else {
  153.                   if (tinx > tiny) {
  154.                      add (xin, yout);
  155.                      }
  156.                   else {
  157.                      add (xout, yin);
  158.                      }
  159.                   }
  160.                }
  161.             }
  162.          }
  163.       }
  164.  
  165.    if (npnt) {
  166.       add(XCOORD(GETPNT(npoly,0)),YCOORD(GETPNT(npoly,0)));
  167.       }
  168.    NPNTS(npoly) = npnt;
  169.    }
  170.  
  171. #___________ cut mark
  172.  
  173. /* Modified Liang-Barsky Polygon Clipping [CACM, Vol 26 (Nov, 1983)] */
  174.  
  175. /* see the comments at the start of the unmodified version for more
  176.  * details.
  177.  */
  178.  
  179. # include "pln.h"
  180.  
  181. # define INFINITY    (1.0e+30)
  182. # define NEARZERO    (1.0e-30)    /* 1/INFINITY */
  183.  
  184. # define add(x,y) {\
  185.                    XCOORD(GETPNT(npoly,npnt)) = x;\
  186.                    YCOORD(GETPNT(npoly,npnt)) = y;\
  187.                    ++npnt;\
  188.                   }
  189.  
  190. extern float wx1,wy1,  wx2,wy2;    /* window boundaries */
  191.  
  192. fclip(opoly,npoly)
  193.    PLN *opoly, *npoly;
  194.  
  195.    {
  196.    register int i, npnt;
  197.    float deltax, deltay, xin,xout,  yin,yout;
  198.    float tinx,tiny,  toutx,touty,  tin1, tin2,  tout1,tout2;
  199.    float x1,y1, x2,y2;
  200.    
  201.    npnt = 0;
  202.  
  203.    for (i = 0; i < NPNTS(opoly)-1; ++i) {
  204.  
  205.       x1 = XCOORD(GETPNT(opoly,i));
  206.       y1 = YCOORD(GETPNT(opoly,i));
  207.       x2 = XCOORD(GETPNT(opoly,i+1));
  208.       y2 = YCOORD(GETPNT(opoly,i+1));
  209.  
  210.       deltax = x2-x1;
  211.       if (deltax == 0) { /* bump off of the vertical */
  212.          deltax = (x1 > wx1) ? -NEARZERO : NEARZERO ;
  213.          }
  214.       deltay = y2-y1;
  215.       if (deltay == 0) { /* bump off of the horizontal */
  216.          deltay = (y1 > wy1) ? -NEARZERO : NEARZERO ;
  217.          }
  218.  
  219.       if (deltax > 0) {        /*  points to right */
  220.          xin = wx1;
  221.          xout = wx2;
  222.          }
  223.       else {
  224.          xin = wx2;
  225.          xout = wx1;
  226.          }
  227.       if (deltay > 0) {        /*  points up */
  228.          yin = wy1;
  229.          yout = wy2;
  230.          }
  231.       else {
  232.          yin = wy2;
  233.          yout = wy1;
  234.          }
  235.  
  236.       tinx = (xin - x1)/deltax;
  237.       tiny = (yin - y1)/deltay;
  238.    
  239.       if (tinx < tiny) {    /* hits x first */
  240.          tin1 = tinx;
  241.          tin2 = tiny;
  242.          }
  243.       else            /* hits y first */
  244.          {
  245.          tin1 = tiny;
  246.          tin2 = tinx;
  247.          }
  248.  
  249.       if (1 >= tin1) {
  250.          if (0 < tin1) {
  251.             add(xin,yin);
  252.             }
  253.          if (1 >= tin2) {
  254.             toutx = (xout - x1)/deltax;
  255.             touty = (yout - y1)/deltay;
  256.  
  257.             tout1 = (toutx < touty) ? toutx : touty ;
  258.    
  259.             if (0 < tin2 || 0 < tout1) {
  260.                if (tin2 <= tout1) {
  261.                   if (0 < tin2) {
  262.                      if (tinx > tiny) {
  263.                         add (xin, y1+tinx*deltay);
  264.                         }
  265.                      else {
  266.                         add (x1 + tiny*deltax, yin);
  267.                         }
  268.                      }
  269.                   if (1 > tout1) {
  270.                      if (toutx < touty) {
  271.                         add (xout, y1+toutx*deltay);
  272.                         }
  273.                      else {
  274.                         add (x1 + touty*deltax, yout);
  275.                         }
  276.                      }
  277.                   else {
  278.                      add (x2,y2);
  279.                      }
  280.                   }
  281.                else {
  282.                   if (tinx > tiny) {
  283.                      add (xin, yout);
  284.                      }
  285.                   else {
  286.                      add (xout, yin);
  287.                      }
  288.                   }
  289.                }
  290.             }
  291.          }
  292.       }
  293.  
  294.    if (npnt) {
  295.       add(XCOORD(GETPNT(npoly,0)),YCOORD(GETPNT(npoly,0)));
  296.       }
  297.    NPNTS(npoly) = npnt;
  298.    }
  299.  
  300. #_________ cut mark
  301.  
  302.  
  303. -Steve Wampler
  304. {...}!arizona!naucse!sbw
  305.  
  306.  
  307.