6 typedef struct Seg Seg;
21 static void zsort(Seg **seg, Seg **ep);
22 static int ycompare(const void*, const void*);
23 static int xcompare(const void*, const void*);
24 static int zcompare(const void*, const void*);
25 static void xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int, int, int, int);
26 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);
43 fillline(Memimage *dst, int left, int right, int y, Memimage *src, Point p, int op)
53 memdraw(dst, r, src, p, memopaque, p, op);
57 fillpoint(Memimage *dst, int x, int y, Memimage *src, Point p, int op)
67 memdraw(dst, r, src, p, memopaque, p, op);
71 memfillpoly(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int op)
73 _memfillpolysc(dst, vert, nvert, w, src, sp, 0, 0, 0, op);
77 _memfillpolysc(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
86 seg = malloc((nvert+2)*sizeof(Seg*));
89 segtab = malloc((nvert+1)*sizeof(Seg));
95 sp.x = (sp.x - vert[0].x) >> fixshift;
96 sp.y = (sp.y - vert[0].y) >> fixshift;
102 for(i = 0; i < nvert; i++) {
115 xscan(dst, seg, segtab, nvert, w, src, sp, detail, fixshift, clipped, op);
117 yscan(dst, seg, segtab, nvert, w, src, sp, fixshift, op);
129 if((long)(((u32int)z)^((u32int)y)) > 0 || z == 0)
137 if((long)(((u32int)x)^((u32int)y)) >= 0 || x == 0)
140 return (x+((y>>30)|1))/y-1;
144 smuldivmod(long x, long y, long z, long *mod)
148 if(x == 0 || y == 0){
156 *mod += z; /* z is always >0 */
157 if((vx < 0) == (z < 0))
163 xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
165 long y, maxy, x, x2, xerr, xden, onehalf;
166 Seg **ep, **next, **p, **q, *s;
167 long n, i, iy, cnt, ix, ix2, minx, maxx;
169 void (*fill)(Memimage*, int, int, int, Memimage*, Point, int);
173 * This can only work on 8-bit destinations, since fillcolor is
174 * just using memset on sp.x.
176 * I'd rather not even enable it then, since then if the general
177 * code is too slow, someone will come up with a better improvement
178 * than this sleazy hack. -rsc
180 if(clipped && (src->flags&Frepl) && src->depth==8 && Dx(src->r)==1 && Dy(src->r)==1) {
182 sp.x = membyteval(src);
189 for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
191 if(s->p0.y == s->p1.y)
193 if(s->p0.y > s->p1.y) {
199 s->num = s->p1.x - s->p0.x;
200 s->den = s->p1.y - s->p0.y;
201 s->dz = sdiv(s->num, s->den) << fixshift;
202 s->dzrem = mod(s->num, s->den) << fixshift;
203 s->dz += sdiv(s->dzrem, s->den);
204 s->dzrem = mod(s->dzrem, s->den);
211 qsort(seg, p-seg , sizeof(Seg*), ycompare);
215 onehalf = 1 << (fixshift-1);
217 minx = dst->clipr.min.x;
218 maxx = dst->clipr.max.x;
221 if(y < (dst->clipr.min.y << fixshift))
222 y = dst->clipr.min.y << fixshift;
223 iy = (y + onehalf) >> fixshift;
224 y = (iy << fixshift) + onehalf;
225 maxy = dst->clipr.max.y << fixshift;
230 for(q = p = seg; p < ep; p++) {
236 if(s->zerr >= s->den) {
239 if(s->zerr < 0 || s->zerr >= s->den)
240 print("bad ratzerr1: %ld den %ld dzrem %ld\n", s->zerr, s->den, s->dzrem);
245 for(p = next; *p; p++) {
252 s->z += smuldivmod(y - s->p0.y, s->num, s->den, &s->zerr);
253 if(s->zerr < 0 || s->zerr >= s->den)
254 print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
263 iy = (next[0]->p0.y + onehalf) >> fixshift;
264 y = (iy << fixshift) + onehalf;
270 for(p = seg; p < ep; p++) {
275 ix = (x + onehalf) >> fixshift;
284 print("xscan: fill to infinity");
293 ix2 = (x2 + onehalf) >> fixshift;
298 if(ix == ix2 && detail) {
299 if(xerr*p[0]->den + p[0]->zerr*xden > p[0]->den*xden)
301 ix = (x + x2) >> (fixshift+1);
304 (*fill)(dst, ix, ix2, iy, src, sp, op);
312 yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int fixshift, int op)
314 long x, maxx, y, y2, yerr, yden, onehalf;
315 Seg **ep, **next, **p, **q, *s;
316 int n, i, ix, cnt, iy, iy2, miny, maxy;
319 for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
321 if(s->p0.x == s->p1.x)
323 if(s->p0.x > s->p1.x) {
329 s->num = s->p1.y - s->p0.y;
330 s->den = s->p1.x - s->p0.x;
331 s->dz = sdiv(s->num, s->den) << fixshift;
332 s->dzrem = mod(s->num, s->den) << fixshift;
333 s->dz += sdiv(s->dzrem, s->den);
334 s->dzrem = mod(s->dzrem, s->den);
341 qsort(seg, n , sizeof(Seg*), xcompare);
345 onehalf = 1 << (fixshift-1);
347 miny = dst->clipr.min.y;
348 maxy = dst->clipr.max.y;
351 if(x < (dst->clipr.min.x << fixshift))
352 x = dst->clipr.min.x << fixshift;
353 ix = (x + onehalf) >> fixshift;
354 x = (ix << fixshift) + onehalf;
355 maxx = dst->clipr.max.x << fixshift;
360 for(q = p = seg; p < ep; p++) {
366 if(s->zerr >= s->den) {
369 if(s->zerr < 0 || s->zerr >= s->den)
370 print("bad ratzerr1: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
375 for(p = next; *p; p++) {
382 s->z += smuldivmod(x - s->p0.x, s->num, s->den, &s->zerr);
383 if(s->zerr < 0 || s->zerr >= s->den)
384 print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
393 ix = (next[0]->p0.x + onehalf) >> fixshift;
394 x = (ix << fixshift) + onehalf;
400 for(p = seg; p < ep; p++) {
405 iy = (y + onehalf) >> fixshift;
414 print("yscan: fill to infinity");
423 iy2 = (y2 + onehalf) >> fixshift;
429 if(yerr*p[0]->den + p[0]->zerr*yden > p[0]->den*yden)
431 iy = (y + y2) >> (fixshift+1);
432 fillpoint(dst, ix, iy, src, sp, op);
441 zsort(Seg **seg, Seg **ep)
447 /* bubble sort by z - they should be almost sorted already */
452 for(p = seg; p < q; p++) {
453 if(p[0]->z > p[1]->z) {
463 for(p = seg; p < q; p++) {
464 if(p[0]->z > p[1]->z) {
465 qsort(seg, ep-seg, sizeof(Seg*), zcompare);
473 ycompare(const void *a, const void *b)
491 xcompare(const void *a, const void *b)
509 zcompare(const void *a, const void *b)