home *** CD-ROM | disk | FTP | other *** search
/ Monster Disc 2: The Best of 1992 / MONSTER2.ISO / prog / djgpp / cbgrx102.a01 / CONTRIB / LIBGRX / SRC / SCANPOLY.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-12  |  6.0 KB  |  209 lines
  1. /**
  2.  ** SCANPOLY.C
  3.  **
  4.  **  Copyright (C) 1992, Csaba Biegl
  5.  **    820 Stirrup Dr, Nashville, TN, 37221
  6.  **    csaba@vuse.vanderbilt.edu
  7.  **
  8.  **  This file is distributed under the terms listed in the document
  9.  **  "copying.cb", available from the author at the address above.
  10.  **  A copy of "copying.cb" should accompany this file; if not, a copy
  11.  **  should be available from where this file was obtained.  This file
  12.  **  may not be distributed without a verbatim copy of "copying.cb".
  13.  **  You should also have received a copy of the GNU General Public
  14.  **  License along with this program (it is in the file "copying");
  15.  **  if not, write to the Free Software Foundation, Inc., 675 Mass Ave,
  16.  **  Cambridge, MA 02139, USA.
  17.  **
  18.  **  This program is distributed in the hope that it will be useful,
  19.  **  but WITHOUT ANY WARRANTY; without even the implied warranty of
  20.  **  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21.  **  GNU General Public License for more details.
  22.  **/
  23.  
  24. #include "grx.h"
  25. #include "libgrx.h"
  26. #include "clipping.h"
  27. #include "scale.h"
  28. #include "gmalloc.h"
  29.  
  30. typedef enum {
  31.     inactive,
  32.     active,
  33.     passed
  34. } edgestatus;
  35.  
  36. typedef struct _scansegment_ {
  37.     struct _scansegment_ *next;
  38.     int X1,X2;
  39. } scansegment;
  40.  
  41. typedef struct {
  42.     scansegment seg;
  43.     edgestatus  status;
  44.     int x1,x2,y1,y2;
  45.     int slope,error;
  46.     int dx,dy;
  47. } polyedge;
  48.  
  49.  
  50. void _GrScanPolygon(int n,int pt[][2],_GrScanLineProc lnproc,void *lnarg)
  51. {
  52.     polyedge    *edgetable,*ep;
  53.     scansegment *firstpt,*firstseg,*pp,*sp,*prev;
  54.     int prevx,prevy;
  55.     int minx,maxx,miny,maxy;
  56.     int realedges;
  57.     int X1,X2,Y;
  58.     MOUSE_FLAG;
  59.  
  60. #define add_scanpoint(seg,x) do {                        \
  61.     X1 = (x);                                \
  62.     prev = NULL;                                \
  63.     for(pp = firstpt; pp != NULL; prev = pp,pp = pp->next)            \
  64.         if(pp->X1 >= X1) break;                        \
  65.     (seg)->next = pp;                            \
  66.     (seg)->X1 = X1;                                \
  67.     *(prev ? &prev->next : &firstpt) = (seg);                \
  68. } while(0)
  69.  
  70. #define add_scansegment(seg,x1,x2) do {                        \
  71.     char overlap = FALSE;                            \
  72.     X1 = (x1);                                \
  73.     X2 = (x2);                                \
  74.     prev = NULL;                                \
  75.     for(sp = firstseg; sp != NULL; prev = sp,sp = sp->next) {        \
  76.         if((sp->X1 <= X2) && (X1 <= sp->X2)) {                \
  77.         overlap = TRUE;                            \
  78.         if(X1 < sp->X1) sp->X1 = X1;                    \
  79.         if(X2 > sp->X2) {                        \
  80.             prev = sp;                            \
  81.             while((sp = sp->next) != NULL) {                \
  82.             if(sp->X1 > X2) break;                    \
  83.             if(sp->X2 > X2) X2 = sp->X2;                \
  84.             }                                \
  85.             prev->X2 = X2;                        \
  86.             prev->next = sp;                        \
  87.         }                                \
  88.         break;                                \
  89.         }                                    \
  90.         if(sp->X1 > X2) break;                        \
  91.     }                                    \
  92.     if(!overlap) {                                \
  93.         (seg)->next = sp;                            \
  94.         (seg)->X1 = X1;                            \
  95.         (seg)->X2 = X2;                            \
  96.         *(prev ? &prev->next : &firstseg) = (seg);                \
  97.     }                                    \
  98. } while(0)
  99.  
  100.     edgetable = (polyedge *)_GrGetTempBuffer(sizeof(polyedge) * (n + 2));
  101.     if(edgetable == NULL) return;
  102.     /*
  103.      * Build the edge table. Store only those edges which are in the valid
  104.      * Y region. Clip them in Y if ncessary. Store them with the endpoints
  105.      * ordered by Y in the edge table.
  106.      */
  107.     prevx = pt[0][0];
  108.     prevy = pt[0][1];
  109.     minx = miny = 32000;
  110.     maxx = maxy = (-32000);
  111.     realedges = 0;
  112.     ep = edgetable;
  113.     while(--n >= 0) {
  114.         if(pt[n][1] >= prevy) {
  115.         ep->x1 = prevx;
  116.         ep->y1 = prevy;
  117.         ep->x2 = prevx = pt[n][0];
  118.         ep->y2 = prevy = pt[n][1];
  119.         }
  120.         else {
  121.         ep->x2 = prevx;
  122.         ep->y2 = prevy;
  123.         ep->x1 = prevx = pt[n][0];
  124.         ep->y1 = prevy = pt[n][1];
  125.         }
  126.         if(ep->y1 > _GrHiY) continue;
  127.         if(ep->y2 < _GrLoY) continue;
  128.         if(ep->y1 < _GrLoY) {
  129.         SCALE(X1,(ep->x1 - ep->x2),(ep->y2 - _GrLoY),(ep->y2 - ep->y1));
  130.         ep->x1 = ep->x2 + X1;
  131.         ep->y1 = _GrLoY;
  132.         }
  133.         if(ep->y2 > _GrHiY) {
  134.         SCALE(X2,(ep->x2 - ep->x1),(_GrHiY - ep->y1),(ep->y2 - ep->y1));
  135.         ep->x2 = ep->x1 + X2;
  136.         ep->y2 = _GrHiY;
  137.         }
  138.         if(ep->y1 < miny) miny = ep->y1;
  139.         if(ep->y2 > maxy) maxy = ep->y2;
  140.         if(ep->x2 > ep->x1) {
  141.         if(ep->x1 < minx) minx = ep->x1;
  142.         if(ep->x2 > maxx) maxx = ep->x2;
  143.         }
  144.         else {
  145.         if(ep->x1 > maxx) maxx = ep->x1;
  146.         if(ep->x2 < minx) minx = ep->x2;
  147.         }
  148.         ep->status = inactive;
  149.         realedges++;
  150.         ep++;
  151.     }
  152.     if(realedges == 0) return;
  153.     if(minx > _GrHiX) return;
  154.     if(maxx < _GrLoX) return;
  155.     MOUSE_BLOCK(CURC,minx,miny,maxx,maxy);
  156.     /*
  157.      * Scan for every row between ymin and ymax.
  158.      * Build a linked list of disjoint segments to fill. Rules:
  159.      *   (1) a horizontal edge in the row contributes a segment
  160.      *   (2) any other edge crossing the row contributes a point
  161.      *   (3) every segment between even and odd points is filled
  162.      */
  163.     for(Y = miny; Y <= maxy; Y++) {
  164.         firstpt  = NULL;
  165.         firstseg = NULL;
  166.         for(n = realedges,ep = edgetable; --n >= 0; ep++) {
  167.         switch(ep->status) {
  168.           case inactive:
  169.             if(ep->y1 != Y) break;
  170.             ep->dx = ep->x2 - ep->x1;
  171.             ep->dy = ep->y2 - ep->y1;
  172.             if(ep->dy == 0) {
  173.             add_scansegment(&ep->seg,
  174.                 ((ep->dx > 0) ? ep->x1 : ep->x2),
  175.                 ((ep->dx > 0) ? ep->x2 : ep->x1)
  176.             );
  177.             ep->status = passed;
  178.             break;
  179.             }
  180.             ep->slope = ep->dx / ep->dy;
  181.             if((ep->dx %= ep->dy) < 0) { ep->slope--; ep->dx += ep->dy; }
  182.             ep->error = ep->dy >> 1;
  183.             ep->status = active;
  184.           case active:
  185.             if((ep->y2 == Y) && (Y != maxy)) { ep->status = passed; break; }
  186.             add_scanpoint(&ep->seg,ep->x1);
  187.             if((ep->error -= ep->dx) < 0) { ep->x1++; ep->error += ep->dy; }
  188.             ep->x1 += ep->slope;
  189.             break;
  190.           default:
  191.             break;
  192.         }
  193.         }
  194.         while((pp = firstpt) != NULL) {
  195.         firstpt = pp->next->next;
  196.         add_scansegment(pp,pp->X1,pp->next->X1);
  197.         }
  198.         for(sp = firstseg; sp != NULL; sp = sp->next) {
  199.         if((X1 = sp->X1) > _GrHiX) continue;
  200.         if((X2 = sp->X2) < _GrLoX) continue;
  201.         if(X1 < _GrLoX) X1 = _GrLoX;
  202.         if(X2 > _GrHiX) X2 = _GrHiX;
  203.         (*lnproc)(X1,X2,Y,lnarg);
  204.         }
  205.     }
  206.     MOUSE_UNBLOCK();
  207. }
  208.  
  209.