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 }