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                 fprintf(stderr, "polygon: no space\n");
  51                 exits("malloc failed");
  52         }
  53         ylist=(Edge **)malloc(Dy(screen->r)*sizeof(Edge *));
  54         if(ylist==0) goto NoSpace;
  55         eylist=ylist+Dy(screen->r);
  56         for(yp=ylist;yp!=eylist;yp++) *yp=0;
  57         ep=edges;
  58         for(cntp=cnt,ptsp=pts;*cntp;cntp++,ptsp++){
  59                 p.x=SCX((*ptsp)[*cntp*2-2]);
  60                 p.y=SCY((*ptsp)[*cntp*2-1]);
  61                 nvert=*cntp;
  62                 for(xp=*ptsp,i=0;i!=nvert;xp+=2,i++){
  63                         q=p;
  64                         p.x=SCX(xp[0]);
  65                         p.y=SCY(xp[1]);
  66                         if(p.y==q.y) continue;
  67                         if(p.y<q.y){
  68                                 p0=p;
  69                                 p1=q;
  70                                 ep->dwind=1;
  71                         }
  72                         else{
  73                                 p0=q;
  74                                 p1=p;
  75                                 ep->dwind=-1;
  76                         }
  77                         if(p1.y<=screen->r.min.y) continue;
  78                         if(p0.y>=screen->r.max.y) continue;
  79                         ep->p=p0;
  80                         if(p1.y>screen->r.max.y)
  81                                 ep->maxy=screen->r.max.y;
  82                         else
  83                                 ep->maxy=p1.y;
  84                         p10=subpt(p1, p0);
  85                         if(p10.x>=0){
  86                                 ep->dx=p10.x/p10.y;
  87                                 ep->dx1=ep->dx+1;
  88                         }
  89                         else{
  90                                 p10.x=-p10.x;
  91                                 ep->dx=-(p10.x/p10.y); /* this nonsense rounds toward zero */
  92                                 ep->dx1=ep->dx-1;
  93                         }
  94                         ep->x=0;
  95                         ep->num=p10.x%p10.y;
  96                         ep->den=p10.y;
  97                         if(ep->p.y<screen->r.min.y){
  98                                 dy=screen->r.min.y-ep->p.y;
  99                                 ep->x+=dy*ep->num;
 100                                 nbig=ep->x/ep->den;
 101                                 ep->p.x+=ep->dx1*nbig+ep->dx*(dy-nbig);
 102                                 ep->x%=ep->den;
 103                                 ep->p.y=screen->r.min.y;
 104                         }
 105                         insert(ep, ylist+(ep->p.y-screen->r.min.y));
 106                         ep++;
 107                 }
 108         }
 109         left = 0;
 110         for(yp=ylist,y=screen->r.min.y;yp!=eylist;yp++,y++){
 111                 wind=0;
 112                 for(ep=*yp;ep;ep=nextep){
 113                         nwind=wind+ep->dwind;
 114                         if(nwind&w){    /* inside */
 115                                 if(!(wind&w)){
 116                                         left=ep->p.x;
 117                                         if(left<screen->r.min.x) left=screen->r.min.x;
 118                                 }
 119                         }
 120                         else if(wind&w){
 121                                 right=ep->p.x;
 122                                 if(right>=screen->r.max.x) right=screen->r.max.x;
 123 #define BART_BUG_FIXED  /* what goes on here?? -rob */
 124 #ifdef BART_BUG_FIXED
 125                                 if(right>left)
 126                                         line(screen, Pt(left, y), Pt(right, y), Endsquare, Endsquare, 0, getcolor(v), ZP);
 127 #else
 128                                 if(right>left){
 129                                         switch(v){
 130                                         default:
 131                                                 segment(&screen, Pt(left, y), Pt(right, y),
 132                                                         ~0, D&~S);
 133                                                 segment(&screen, Pt(left, y), Pt(right, y),
 134                                                         v, f);
 135                                                 break;
 136                                         case 0:
 137                                                 segment(&screen, Pt(left, y), Pt(right, y),
 138                                                         ~0, D&~S);
 139                                                 break;
 140                                         case 3:
 141                                                 segment(&screen, Pt(left, y), Pt(right, y),
 142                                                         v, f);
 143                                                 break;
 144                                         }
 145                                 }
 146 #endif
 147                         }
 148                         wind=nwind;
 149                         nextep=ep->next;
 150                         if(++ep->p.y!=ep->maxy){
 151                                 ep->x+=ep->num;
 152                                 if(ep->x>=ep->den){
 153                                         ep->x-=ep->den;
 154                                         ep->p.x+=ep->dx1;
 155                                 }
 156                                 else
 157                                         ep->p.x+=ep->dx;
 158                                 insert(ep, yp+1);
 159                         }
 160                 }
 161         }
 162         free((char *)edges);
 163         free((char *)ylist);
 164 }
 165 void fill(int num[], double *ff[]){
 166         polygon(num, ff, Odd, e1->foregr);
 167 }