7 typedef struct Seg Seg;
22 static void zsort(Seg **seg, Seg **ep);
23 static int ycompare(void*, void*);
24 static int xcompare(void*, void*);
25 static int zcompare(void*, void*);
26 static void xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int, int, int, int);
27 static void yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int, int);
30 fillline(Memimage *dst, int left, int right, int y, Memimage *src, Point p, int op)
40 memdraw(dst, r, src, p, memopaque, p, op);
44 fillpoint(Memimage *dst, int x, int y, Memimage *src, Point p, int op)
54 memdraw(dst, r, src, p, memopaque, p, op);
58 memfillpoly(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int op)
60 _memfillpolysc(dst, vert, nvert, w, src, sp, 0, 0, 0, op);
64 _memfillpolysc(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
73 seg = malloc((nvert+2)*sizeof(Seg*));
76 segtab = malloc((nvert+1)*sizeof(Seg));
82 sp.x = (sp.x - vert[0].x) >> fixshift;
83 sp.y = (sp.y - vert[0].y) >> fixshift;
89 for(i = 0; i < nvert; i++) {
102 xscan(dst, seg, segtab, nvert, w, src, sp, detail, fixshift, clipped, op);
104 yscan(dst, seg, segtab, nvert, w, src, sp, fixshift, op);
116 if((long)(((ulong)z)^((ulong)y)) > 0 || z == 0)
124 if((long)(((ulong)x)^((ulong)y)) >= 0 || x == 0)
127 return (x+((y>>30)|1))/y-1;
131 smuldivmod(long x, long y, long z, long *mod)
135 if(x == 0 || y == 0){
143 *mod += z; /* z is always >0 */
144 if((vx < 0) == (z < 0))
150 xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
152 long y, maxy, x, x2, xerr, xden, onehalf;
153 Seg **ep, **next, **p, **q, *s;
154 long n, i, iy, cnt, ix, ix2, minx, maxx;
159 for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
161 if(s->p0.y == s->p1.y)
163 if(s->p0.y > s->p1.y) {
169 s->num = s->p1.x - s->p0.x;
170 s->den = s->p1.y - s->p0.y;
171 s->dz = sdiv(s->num, s->den) << fixshift;
172 s->dzrem = mod(s->num, s->den) << fixshift;
173 s->dz += sdiv(s->dzrem, s->den);
174 s->dzrem = mod(s->dzrem, s->den);
181 qsort(seg, p-seg , sizeof(Seg*), ycompare);
185 onehalf = 1 << (fixshift-1);
187 minx = dst->clipr.min.x;
188 maxx = dst->clipr.max.x;
191 if(y < (dst->clipr.min.y << fixshift))
192 y = dst->clipr.min.y << fixshift;
193 iy = (y + onehalf) >> fixshift;
194 y = (iy << fixshift) + onehalf;
195 maxy = dst->clipr.max.y << fixshift;
200 for(q = p = seg; p < ep; p++) {
206 if(s->zerr >= s->den) {
209 if(s->zerr < 0 || s->zerr >= s->den)
210 print("bad ratzerr1: %ld den %ld dzrem %ld\n", s->zerr, s->den, s->dzrem);
215 for(p = next; *p; p++) {
222 s->z += smuldivmod(y - s->p0.y, s->num, s->den, &s->zerr);
223 if(s->zerr < 0 || s->zerr >= s->den)
224 print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
233 iy = (next[0]->p0.y + onehalf) >> fixshift;
234 y = (iy << fixshift) + onehalf;
240 for(p = seg; p < ep; p++) {
245 ix = (x + onehalf) >> fixshift;
254 print("xscan: fill to infinity");
263 ix2 = (x2 + onehalf) >> fixshift;
268 if(ix == ix2 && detail) {
269 if(xerr*p[0]->den + p[0]->zerr*xden > p[0]->den*xden)
271 ix = (x + x2) >> (fixshift+1);
274 fillline(dst, ix, ix2, iy, src, sp, op);
282 yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int fixshift, int op)
284 long x, maxx, y, y2, yerr, yden, onehalf;
285 Seg **ep, **next, **p, **q, *s;
286 int n, i, ix, cnt, iy, iy2, miny, maxy;
289 for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
291 if(s->p0.x == s->p1.x)
293 if(s->p0.x > s->p1.x) {
299 s->num = s->p1.y - s->p0.y;
300 s->den = s->p1.x - s->p0.x;
301 s->dz = sdiv(s->num, s->den) << fixshift;
302 s->dzrem = mod(s->num, s->den) << fixshift;
303 s->dz += sdiv(s->dzrem, s->den);
304 s->dzrem = mod(s->dzrem, s->den);
311 qsort(seg, n , sizeof(Seg*), xcompare);
315 onehalf = 1 << (fixshift-1);
317 miny = dst->clipr.min.y;
318 maxy = dst->clipr.max.y;
321 if(x < (dst->clipr.min.x << fixshift))
322 x = dst->clipr.min.x << fixshift;
323 ix = (x + onehalf) >> fixshift;
324 x = (ix << fixshift) + onehalf;
325 maxx = dst->clipr.max.x << fixshift;
330 for(q = p = seg; p < ep; p++) {
336 if(s->zerr >= s->den) {
339 if(s->zerr < 0 || s->zerr >= s->den)
340 print("bad ratzerr1: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
345 for(p = next; *p; p++) {
352 s->z += smuldivmod(x - s->p0.x, s->num, s->den, &s->zerr);
353 if(s->zerr < 0 || s->zerr >= s->den)
354 print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
363 ix = (next[0]->p0.x + onehalf) >> fixshift;
364 x = (ix << fixshift) + onehalf;
370 for(p = seg; p < ep; p++) {
375 iy = (y + onehalf) >> fixshift;
384 print("yscan: fill to infinity");
393 iy2 = (y2 + onehalf) >> fixshift;
399 if(yerr*p[0]->den + p[0]->zerr*yden > p[0]->den*yden)
401 iy = (y + y2) >> (fixshift+1);
402 fillpoint(dst, ix, iy, src, sp, op);
411 zsort(Seg **seg, Seg **ep)
417 /* bubble sort by z - they should be almost sorted already */
422 for(p = seg; p < q; p++) {
423 if(p[0]->z > p[1]->z) {
433 for(p = seg; p < q; p++) {
434 if(p[0]->z > p[1]->z) {
435 qsort(seg, ep-seg, sizeof(Seg*), zcompare);
443 ycompare(void *a, void *b)
461 xcompare(void *a, void *b)
479 zcompare(void *a, void *b)