xref: /inferno-os/appl/math/polyfill.b (revision 37da2899f40661e3e9631e497da8dc59b971cbd0) 
1implement Polyfill;
2
3include "sys.m";
4	sys: Sys;
5include "draw.m";
6	draw: Draw;
7	Point, Rect, Image, Endsquare: import draw;
8include "math/polyfill.m";
9
10∞: con 16r7fffffff;
11
12init()
13{
14	sys = load Sys Sys->PATH;
15	draw = load Draw Draw->PATH;
16}
17
18initzbuf(r: Rect): ref Zstate
19{
20	if(sys == nil)
21		init();
22	s := ref Zstate;
23	s.r = r;
24	s.xlen = r.dx();
25	s.ylen = r.dy();
26	s.xylen = s.xlen*s.ylen;
27	s.zbuf0 = array[s.xylen] of int;
28	s.zbuf1 = array[s.xylen] of int;
29	return s;
30}
31
32clearzbuf(s: ref Zstate)
33{
34	b0 := s.zbuf0;
35	b1 := s.zbuf1;
36	n := s.xylen;
37	for(i := 0; i < n; i++)
38		b0[i] = b1[i] = ∞;
39}
40
41setzbuf(s: ref Zstate, zd: int)
42{
43	b0 := s.zbuf0;
44	b1 := s.zbuf1;
45	n := s.xylen;
46	for(i := 0; i < n; i++)
47		b0[i] = b1[i] = zd;
48}
49
50Seg: adt
51{
52	p0: Point;
53	p1: Point;
54	num: int;
55	den: int;
56	dz: int;
57	dzrem: int;
58	z: int;
59	zerr: int;
60	d: int;
61};
62
63fillline(dst: ref Image, left: int, right: int, y: int, src: ref Image, p: Point)
64{
65	p.x += left;
66	p.y += y;
67	dst.line((left, y), (right, y), Endsquare, Endsquare, 0, src, p);
68}
69
70filllinez(dst: ref Image, left: int, right: int, y: int, z: int, e: int, dx: int, k: int, zbuf0: array of int, zbuf1: array of int, src: ref Image, p: Point)
71{
72	prevx := ∞;
73	for(x := left; x <= right; x++){
74		if(z+e < zbuf0[k] || (z-e <= zbuf1[k] && x != right && prevx != ∞)){
75			zbuf0[k] = z-e;
76			zbuf1[k] = z+e;
77			if(prevx == ∞)
78				prevx = x;
79		}
80		else if(prevx != ∞){
81			fillline(dst, prevx, x-1, y, src, p);
82			prevx = ∞;
83		}
84		z += dx;
85		k++;
86	}
87	if(prevx != ∞)
88		fillline(dst, prevx, right, y, src, p);
89}
90
91fillpoly(dst: ref Image, vert: array of Point, w: int, src: ref Image, sp: Point, zstate: ref Zstate, dc: int, dx: int, dy: int)
92{
93	p0: Point;
94	i: int;
95
96	nvert := len vert;
97	if(nvert == 0)
98		return;
99	fixshift := 0;
100	seg := array[nvert+2] of ref Seg;
101	if(seg == nil)
102		return;
103	segtab := array[nvert+1] of ref Seg;
104	if(segtab == nil)
105		return;
106
107	sp.x = (sp.x - vert[0].x) >> fixshift;
108	sp.y = (sp.y - vert[0].y) >> fixshift;
109	p0 = vert[nvert-1];
110	if(!fixshift) {
111		p0.x <<= 1;
112		p0.y <<= 1;
113	}
114	for(i = 0; i < nvert; i++) {
115		segtab[i] = ref Seg;
116		segtab[i].p0 = p0;
117		p0 = vert[i];
118		if(!fixshift) {
119			p0.x <<= 1;
120			p0.y <<= 1;
121		}
122		segtab[i].p1 = p0;
123		segtab[i].d = 1;
124	}
125	if(!fixshift)
126		fixshift = 1;
127
128	xscan(dst, seg, segtab, nvert, w, src, sp, zstate, dc, dx, dy, fixshift);
129}
130
131mod(x: int, y: int): int
132{
133	z: int;
134
135	z = x%y;
136	if((z^y) > 0 || z == 0)
137		return z;
138	return z + y;
139}
140
141sdiv(x: int, y: int): int
142{
143	if((x^y) >= 0 || x == 0)
144		return x/y;
145	return (x+((y>>30)|1))/y-1;
146}
147
148smuldivmod(x: int, y: int, z: int): (int, int)
149{
150	mod: int;
151	vx: int;
152
153	if(x == 0 || y == 0)
154		return (0, 0);
155	vx = x;
156	vx *= y;
157	mod = vx % z;
158	if(mod < 0)
159		mod += z;
160	if((vx < 0) == (z < 0))
161		return (vx/z, mod);
162	return (-((-vx)/z), mod);
163}
164
165xscan(dst: ref Image, seg: array of ref Seg, segtab: array of ref Seg, nseg: int, wind: int, src: ref Image, spt: Point, zstate: ref Zstate, dc: int, dx: int, dy: int, fixshift: int)
166{
167	y, maxy, x, x2, onehalf: int;
168	ep, next, p, q, s: int;
169	n, i, iy, cnt, ix, ix2, minx, maxx, zinc, k, zv: int;
170	pt: Point;
171	sp: ref Seg;
172
173	er := (abs(dx)+abs(dy)+1)/2;
174	zr := zstate.r;
175	xlen := zstate.xlen;
176	zbuf0 := zstate.zbuf0;
177	zbuf1 := zstate.zbuf1;
178	s = 0;
179	p = 0;
180	for(i=0; i<nseg; i++) {
181		sp = seg[p] = segtab[s];
182		if(sp.p0.y == sp.p1.y){
183			s++;
184			continue;
185		}
186		if(sp.p0.y > sp.p1.y) {
187			pt = sp.p0;
188			sp.p0 = sp.p1;
189			sp.p1 = pt;
190			sp.d = -sp.d;
191		}
192		sp.num = sp.p1.x - sp.p0.x;
193		sp.den = sp.p1.y - sp.p0.y;
194		sp.dz = sdiv(sp.num, sp.den) << fixshift;
195		sp.dzrem = mod(sp.num, sp.den) << fixshift;
196		sp.dz += sdiv(sp.dzrem, sp.den);
197		sp.dzrem = mod(sp.dzrem, sp.den);
198		p++;
199		s++;
200	}
201	n = p;
202	if(n == 0)
203		return;
204	seg[p] = nil;
205	qsortycompare(seg, p);
206
207	onehalf = 0;
208	if(fixshift)
209		onehalf = 1 << (fixshift-1);
210
211	minx = dst.clipr.min.x;
212	maxx = dst.clipr.max.x;
213
214	y = seg[0].p0.y;
215	if(y < (dst.clipr.min.y << fixshift))
216		y = dst.clipr.min.y << fixshift;
217	iy = (y + onehalf) >> fixshift;
218	y = (iy << fixshift) + onehalf;
219	maxy = dst.clipr.max.y << fixshift;
220	k = (iy-zr.min.y)*xlen;
221	zv = dc+iy*dy;
222
223	ep = next = 0;
224
225	while(y<maxy) {
226		for(q = p = 0; p < ep; p++) {
227			sp = seg[p];
228			if(sp.p1.y < y)
229				continue;
230			sp.z += sp.dz;
231			sp.zerr += sp.dzrem;
232			if(sp.zerr >= sp.den) {
233				sp.z++;
234				sp.zerr -= sp.den;
235				if(sp.zerr < 0 || sp.zerr >= sp.den)
236					sys->print("bad ratzerr1: %d den %d dzrem %d\n", sp.zerr, sp.den, sp.dzrem);
237			}
238			seg[q] = sp;
239			q++;
240		}
241
242		for(p = next; seg[p] != nil; p++) {
243			sp = seg[p];
244			if(sp.p0.y >= y)
245				break;
246			if(sp.p1.y < y)
247				continue;
248			sp.z = sp.p0.x;
249			(zinc, sp.zerr) = smuldivmod(y - sp.p0.y, sp.num, sp.den);
250			sp.z += zinc;
251			if(sp.zerr < 0 || sp.zerr >= sp.den)
252				sys->print("bad ratzerr2: %d den %d ratdzrem %d\n", sp.zerr, sp.den, sp.dzrem);
253			seg[q] = sp;
254			q++;
255		}
256		ep = q;
257		next = p;
258
259		if(ep == 0) {
260			if(seg[next] == nil)
261				break;
262			iy = (seg[next].p0.y + onehalf) >> fixshift;
263			y = (iy << fixshift) + onehalf;
264			k = (iy-zr.min.y)*xlen;
265			zv = dc+iy*dy;
266			continue;
267		}
268
269		zsort(seg, ep);
270
271		for(p = 0; p < ep; p++) {
272			sp = seg[p];
273			cnt = 0;
274			x = sp.z;
275			ix = (x + onehalf) >> fixshift;
276			if(ix >= maxx)
277				break;
278			if(ix < minx)
279				ix = minx;
280			cnt += sp.d;
281			p++;
282			sp = seg[p];
283			for(;;) {
284				if(p == ep) {
285					sys->print("xscan: fill to infinity");
286					return;
287				}
288				cnt += sp.d;
289				if((cnt&wind) == 0)
290					break;
291				p++;
292				sp = seg[p];
293			}
294			x2 = sp.z;
295			ix2 = (x2 + onehalf) >> fixshift;
296			if(ix2 <= minx)
297				continue;
298			if(ix2 > maxx)
299				ix2 = maxx;
300			filllinez(dst, ix, ix2, iy, zv+ix*dx, er, dx, k+ix-zr.min.x, zbuf0, zbuf1, src, spt);
301		}
302		y += (1<<fixshift);
303		iy++;
304		k += xlen;
305		zv += dy;
306	}
307}
308
309zsort(seg: array of ref Seg, ep: int)
310{
311	done: int;
312	s: ref Seg;
313	q, p: int;
314
315	if(ep < 20) {
316		# bubble sort by z - they should be almost sorted already
317		q = ep;
318		do {
319			done = 1;
320			q--;
321			for(p = 0; p < q; p++) {
322				if(seg[p].z > seg[p+1].z) {
323					s = seg[p];
324					seg[p] = seg[p+1];
325					seg[p+1] = s;
326					done = 0;
327				}
328			}
329		} while(!done);
330	} else {
331		q = ep-1;
332		for(p = 0; p < q; p++) {
333			if(seg[p].z > seg[p+1].z) {
334				qsortzcompare(seg, ep);
335				break;
336			}
337		}
338	}
339}
340
341ycompare(s0: ref Seg, s1: ref Seg): int
342{
343	y0, y1: int;
344
345	y0 = s0.p0.y;
346	y1 = s1.p0.y;
347
348	if(y0 < y1)
349		return -1;
350	if(y0 == y1)
351		return 0;
352	return 1;
353}
354
355zcompare(s0: ref Seg, s1: ref Seg): int
356{
357	z0, z1: int;
358
359	z0 = s0.z;
360	z1 = s1.z;
361
362	if(z0 < z1)
363		return -1;
364	if(z0 == z1)
365		return 0;
366	return 1;
367}
368
369qsortycompare(a : array of ref Seg, n : int)
370{
371	i, j : int;
372	t : ref Seg;
373
374	while(n > 1) {
375		i = n>>1;
376		t = a[0]; a[0] = a[i]; a[i] = t;
377		i = 0;
378		j = n;
379		for(;;) {
380			do
381				i++;
382			while(i < n && ycompare(a[i], a[0]) < 0);
383			do
384				j--;
385			while(j > 0 && ycompare(a[j], a[0]) > 0);
386			if(j < i)
387				break;
388			t = a[i]; a[i] = a[j]; a[j] = t;
389		}
390		t = a[0]; a[0] = a[j]; a[j] = t;
391		n = n-j-1;
392		if(j >= n) {
393			qsortycompare(a, j);
394			a = a[j+1:];
395		} else {
396			qsortycompare(a[j+1:], n);
397			n = j;
398		}
399	}
400}
401
402qsortzcompare(a : array of ref Seg, n : int)
403{
404	i, j : int;
405	t : ref Seg;
406
407	while(n > 1) {
408		i = n>>1;
409		t = a[0]; a[0] = a[i]; a[i] = t;
410		i = 0;
411		j = n;
412		for(;;) {
413			do
414				i++;
415			while(i < n && zcompare(a[i], a[0]) < 0);
416			do
417				j--;
418			while(j > 0 && zcompare(a[j], a[0]) > 0);
419			if(j < i)
420				break;
421			t = a[i]; a[i] = a[j]; a[j] = t;
422		}
423		t = a[0]; a[0] = a[j]; a[j] = t;
424		n = n-j-1;
425		if(j >= n) {
426			qsortzcompare(a, j);
427			a = a[j+1:];
428		} else {
429			qsortzcompare(a[j+1:], n);
430			n = j;
431		}
432	}
433}
434
435abs(n: int): int
436{
437	if(n < 0)
438		return -n;
439	return n;
440}
441