sys/src/cmd/plot/libplot/fill.c

   1 /*
   2  * fill -- polygon tiler
   3  * Updating the edgelist from scanline to scanline could be quicker if no
   4  * edges cross:  we can just merge the incoming edges.  If the scan-line
   5  * filling routine were a parameter, we could do textured
   6  * polygons, polyblt, and other such stuff.
   7  */
   8 #include "mplot.h"
   9 typedef enum{
  10         Odd=1,
  11         Nonzero=~0
  12 }Windrule;
  13 typedef struct edge Edge;
  14 struct edge{
  15         Point p;        /* point of crossing current scan-line */
  16         int maxy;       /* scan line at which to discard edge */
  17         int dx;         /* x increment if x fraction<1 */
  18         int dx1;        /* x increment if x fraction>=1 */
  19         int x;          /* x fraction, scaled by den */
  20         int num;        /* x fraction increment for unit y change, scaled by den */
  21         int den;        /* x fraction increment for unit x change, scaled by num */
  22         int dwind;      /* increment of winding number on passing this edge */
  23         Edge *next;     /* next edge on current scanline */
  24         Edge *prev;     /* previous edge on current scanline */
  25 };
  26 static void insert(Edge *ep, Edge **yp){
  27         while(*yp && (*yp)->p.x<ep->p.x) yp=&(*yp)->next;
  28         ep->next=*yp;
  29         *yp=ep;
  30         if(ep->next){
  31                 ep->prev=ep->next->prev;
  32                 ep->next->prev=ep;
  33                 if(ep->prev)
  34                         ep->prev->next=ep;
  35         }
  36         else
  37                 ep->prev=0;
  38 }
  39 static void polygon(int cnt[], double *pts[], Windrule w, int v){
  40         Edge *edges, *ep, *nextep, **ylist, **eylist, **yp;
  41         Point p, q, p0, p1, p10;
  42         int i, dy, nbig, y, left, right, wind, nwind, nvert;
  43         int *cntp;
  44         double **ptsp, *xp;
  45         nvert=0;
  46         for(cntp=cnt;*cntp;cntp++) nvert+=*cntp;
  47         edges=(Edge *)malloc(nvert*sizeof(Edge));
  48         if(edges==0){
  49         NoSpace:
  50                 sysfatal("polygon: no space");
  51         }
  52         ylist=(Edge **)malloc(Dy(screen->r)*sizeof(Edge *));
  53         if(ylist==0) goto NoSpace;
  54         eylist=ylist+Dy(screen->r);
  55         for(yp=ylist;yp!=eylist;yp++) *yp=0;
  56         ep=edges;
  57         for(cntp=cnt,ptsp=pts;*cntp;cntp++,ptsp++){
  58                 p.x=SCX((*ptsp)[*cntp*2-2]);
  59                 p.y=SCY((*ptsp)[*cntp*2-1]);
  60                 nvert=*cntp;
  61                 for(xp=*ptsp,i=0;i!=nvert;xp+=2,i++){
  62                         q=p;
  63                         p.x=SCX(xp[0]);
  64                         p.y=SCY(xp[1]);
  65                         if(p.y==q.y) continue;
  66                         if(p.y<q.y){
  67                                 p0=p;
  68                                 p1=q;
  69                                 ep->dwind=1;
  70                         }
  71                         else{
  72                                 p0=q;
  73                                 p1=p;
  74                                 ep->dwind=-1;
  75                         }
  76                         if(p1.y<=screen->r.min.y) continue;
  77                         if(p0.y>=screen->r.max.y) continue;
  78                         ep->p=p0;
  79                         if(p1.y>screen->r.max.y)
  80                                 ep->maxy=screen->r.max.y;
  81                         else
  82                                 ep->maxy=p1.y;
  83                         p10=subpt(p1, p0);
  84                         if(p10.x>=0){
  85                                 ep->dx=p10.x/p10.y;
  86                                 ep->dx1=ep->dx+1;
  87                         }
  88                         else{
  89                                 p10.x=-p10.x;
  90                                 ep->dx=-(p10.x/p10.y); /* this nonsense rounds toward zero */
  91                                 ep->dx1=ep->dx-1;
  92                         }
  93                         ep->x=0;
  94                         ep->num=p10.x%p10.y;
  95                         ep->den=p10.y;
  96                         if(ep->p.y<screen->r.min.y){
  97                                 dy=screen->r.min.y-ep->p.y;
  98                                 ep->x+=dy*ep->num;
  99                                 nbig=ep->x/ep->den;
 100                                 ep->p.x+=ep->dx1*nbig+ep->dx*(dy-nbig);
 101                                 ep->x%=ep->den;
 102                                 ep->p.y=screen->r.min.y;
 103                         }
 104                         insert(ep, ylist+(ep->p.y-screen->r.min.y));
 105                         ep++;
 106                 }
 107         }
 108         left = 0;
 109         for(yp=ylist,y=screen->r.min.y;yp!=eylist;yp++,y++){
 110                 wind=0;
 111                 for(ep=*yp;ep;ep=nextep){
 112                         nwind=wind+ep->dwind;
 113                         if(nwind&w){    /* inside */
 114                                 if(!(wind&w)){
 115                                         left=ep->p.x;
 116                                         if(left<screen->r.min.x) left=screen->r.min.x;
 117                                 }
 118                         }
 119                         else if(wind&w){
 120                                 right=ep->p.x;
 121                                 if(right>=screen->r.max.x) right=screen->r.max.x;
 122 #define BART_BUG_FIXED  /* what goes on here?? -rob */
 123 #ifdef BART_BUG_FIXED
 124                                 if(right>left)
 125                                         line(screen, Pt(left, y), Pt(right, y), Endsquare, Endsquare, 0, getcolor(v), ZP);
 126 #else
 127                                 if(right>left){
 128                                         switch(v){
 129                                         default:
 130                                                 segment(&screen, Pt(left, y), Pt(right, y),
 131                                                         ~0, D&~S);
 132                                                 segment(&screen, Pt(left, y), Pt(right, y),
 133                                                         v, f);
 134                                                 break;
 135                                         case 0:
 136                                                 segment(&screen, Pt(left, y), Pt(right, y),
 137                                                         ~0, D&~S);
 138                                                 break;
 139                                         case 3:
 140                                                 segment(&screen, Pt(left, y), Pt(right, y),
 141                                                         v, f);
 142                                                 break;
 143                                         }
 144                                 }
 145 #endif
 146                         }
 147                         wind=nwind;
 148                         nextep=ep->next;
 149                         if(++ep->p.y!=ep->maxy){
 150                                 ep->x+=ep->num;
 151                                 if(ep->x>=ep->den){
 152                                         ep->x-=ep->den;
 153                                         ep->p.x+=ep->dx1;
 154                                 }
 155                                 else
 156                                         ep->p.x+=ep->dx;
 157                                 insert(ep, yp+1);
 158                         }
 159                 }
 160         }
 161         free((char *)edges);
 162         free((char *)ylist);
 163 }
 164 void fill(int num[], double *ff[]){
 165         polygon(num, ff, Odd, e1->foregr);
 166 }