fill.c (4097B)
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 }