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 fillcolor(Memimage *dst, int left, int right, int y, Memimage *src, Point p)
38 memset(byteaddr(dst, p), srcval, right-left);
42 fillline(Memimage *dst, int left, int right, int y, Memimage *src, Point p, int op)
52 memdraw(dst, r, src, p, memopaque, p, op);
56 fillpoint(Memimage *dst, int x, int y, Memimage *src, Point p, int op)
66 memdraw(dst, r, src, p, memopaque, p, op);
70 memfillpoly(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int op)
72 _memfillpolysc(dst, vert, nvert, w, src, sp, 0, 0, 0, op);
76 _memfillpolysc(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
85 seg = malloc((nvert+2)*sizeof(Seg*));
88 segtab = malloc((nvert+1)*sizeof(Seg));
94 sp.x = (sp.x - vert[0].x) >> fixshift;
95 sp.y = (sp.y - vert[0].y) >> fixshift;
101 for(i = 0; i < nvert; i++) {
114 xscan(dst, seg, segtab, nvert, w, src, sp, detail, fixshift, clipped, op);
116 yscan(dst, seg, segtab, nvert, w, src, sp, fixshift, op);
128 if((long)(((ulong)z)^((ulong)y)) > 0 || z == 0)
136 if((long)(((ulong)x)^((ulong)y)) >= 0 || x == 0)
139 return (x+((y>>30)|1))/y-1;
143 smuldivmod(long x, long y, long z, long *mod)
147 if(x == 0 || y == 0){
155 *mod += z; /* z is always >0 */
156 if((vx < 0) == (z < 0))
162 xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
164 long y, maxy, x, x2, xerr, xden, onehalf;
165 Seg **ep, **next, **p, **q, *s;
166 long n, i, iy, cnt, ix, ix2, minx, maxx;
168 void (*fill)(Memimage*, int, int, int, Memimage*, Point, int);
172 * This can only work on 8-bit destinations, since fillcolor is
173 * just using memset on sp.x.
175 * I'd rather not even enable it then, since then if the general
176 * code is too slow, someone will come up with a better improvement
177 * than this sleazy hack. -rsc
179 if(clipped && (src->flags&Frepl) && src->depth==8 && Dx(src->r)==1 && Dy(src->r)==1) {
181 sp.x = membyteval(src);
188 for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
190 if(s->p0.y == s->p1.y)
192 if(s->p0.y > s->p1.y) {
198 s->num = s->p1.x - s->p0.x;
199 s->den = s->p1.y - s->p0.y;
200 s->dz = sdiv(s->num, s->den) << fixshift;
201 s->dzrem = mod(s->num, s->den) << fixshift;
202 s->dz += sdiv(s->dzrem, s->den);
203 s->dzrem = mod(s->dzrem, s->den);
210 qsort(seg, p-seg , sizeof(Seg*), ycompare);
214 onehalf = 1 << (fixshift-1);
216 minx = dst->clipr.min.x;
217 maxx = dst->clipr.max.x;
220 if(y < (dst->clipr.min.y << fixshift))
221 y = dst->clipr.min.y << fixshift;
222 iy = (y + onehalf) >> fixshift;
223 y = (iy << fixshift) + onehalf;
224 maxy = dst->clipr.max.y << fixshift;
229 for(q = p = seg; p < ep; p++) {
235 if(s->zerr >= s->den) {
238 if(s->zerr < 0 || s->zerr >= s->den)
239 print("bad ratzerr1: %ld den %ld dzrem %ld\n", s->zerr, s->den, s->dzrem);
244 for(p = next; *p; p++) {
251 s->z += smuldivmod(y - s->p0.y, s->num, s->den, &s->zerr);
252 if(s->zerr < 0 || s->zerr >= s->den)
253 print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
262 iy = (next[0]->p0.y + onehalf) >> fixshift;
263 y = (iy << fixshift) + onehalf;
269 for(p = seg; p < ep; p++) {
274 ix = (x + onehalf) >> fixshift;
283 print("xscan: fill to infinity");
292 ix2 = (x2 + onehalf) >> fixshift;
297 if(ix == ix2 && detail) {
298 if(xerr*p[0]->den + p[0]->zerr*xden > p[0]->den*xden)
300 ix = (x + x2) >> (fixshift+1);
303 (*fill)(dst, ix, ix2, iy, src, sp, op);
311 yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int fixshift, int op)
313 long x, maxx, y, y2, yerr, yden, onehalf;
314 Seg **ep, **next, **p, **q, *s;
315 int n, i, ix, cnt, iy, iy2, miny, maxy;
318 for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
320 if(s->p0.x == s->p1.x)
322 if(s->p0.x > s->p1.x) {
328 s->num = s->p1.y - s->p0.y;
329 s->den = s->p1.x - s->p0.x;
330 s->dz = sdiv(s->num, s->den) << fixshift;
331 s->dzrem = mod(s->num, s->den) << fixshift;
332 s->dz += sdiv(s->dzrem, s->den);
333 s->dzrem = mod(s->dzrem, s->den);
340 qsort(seg, n , sizeof(Seg*), xcompare);
344 onehalf = 1 << (fixshift-1);
346 miny = dst->clipr.min.y;
347 maxy = dst->clipr.max.y;
350 if(x < (dst->clipr.min.x << fixshift))
351 x = dst->clipr.min.x << fixshift;
352 ix = (x + onehalf) >> fixshift;
353 x = (ix << fixshift) + onehalf;
354 maxx = dst->clipr.max.x << fixshift;
359 for(q = p = seg; p < ep; p++) {
365 if(s->zerr >= s->den) {
368 if(s->zerr < 0 || s->zerr >= s->den)
369 print("bad ratzerr1: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
374 for(p = next; *p; p++) {
381 s->z += smuldivmod(x - s->p0.x, s->num, s->den, &s->zerr);
382 if(s->zerr < 0 || s->zerr >= s->den)
383 print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
392 ix = (next[0]->p0.x + onehalf) >> fixshift;
393 x = (ix << fixshift) + onehalf;
399 for(p = seg; p < ep; p++) {
404 iy = (y + onehalf) >> fixshift;
413 print("yscan: fill to infinity");
422 iy2 = (y2 + onehalf) >> fixshift;
428 if(yerr*p[0]->den + p[0]->zerr*yden > p[0]->den*yden)
430 iy = (y + y2) >> (fixshift+1);
431 fillpoint(dst, ix, iy, src, sp, op);
440 zsort(Seg **seg, Seg **ep)
446 /* bubble sort by z - they should be almost sorted already */
451 for(p = seg; p < q; p++) {
452 if(p[0]->z > p[1]->z) {
462 for(p = seg; p < q; p++) {
463 if(p[0]->z > p[1]->z) {
464 qsort(seg, ep-seg, sizeof(Seg*), zcompare);
472 ycompare(void *a, void *b)
490 xcompare(void *a, void *b)
508 zcompare(void *a, void *b)