1 #include <u.h>
2 #include <libc.h>
3 #include <draw.h>
4 
5 #define	PINC	32		/* realloc granularity */
6 
7 typedef struct Plist Plist;
8 struct Plist
9 {
10 	Point *p;
11 	int np;			/* -1 if malloc/realloc failed */
12 };
13 
14 static void
15 appendpt(Plist *l, Point p)
16 {
17 	if(l->np == -1)
18 		return;
19 	if(l->np == 0)
20 		l->p = malloc(PINC*sizeof(Point));
21 	else if(l->np%PINC == 0)
22 		l->p = realloc(l->p, (l->np+PINC)*sizeof(Point));
23 	if(l->p == 0){
24 		l->np = -1;
25 		return;
26 	}
27 	l->p[l->np++] = p;
28 }
29 
30 static int
31 normsq(Point p)
32 {
33 	return p.x*p.x+p.y*p.y;
34 }
35 
36 static int
37 psdist(Point p, Point a, Point b)
38 {
39 	int num, den;
40 
41 	p = subpt(p, a);
42 	b = subpt(b, a);
43 	num = p.x*b.x + p.y*b.y;
44 	if(num <= 0)
45 		return normsq(p);
46 	den = normsq(b);
47 	if(num >= den)
48 		return normsq(subpt(b, p));
49 	return normsq(subpt(divpt(mulpt(b, num), den), p));
50 }
51 
52 /*
53  * Convert cubic Bezier curve control points to polyline
54  * vertices.  Leaves the last vertex off, so you can continue
55  * with another curve.
56  */
57 static void
58 bpts1(Plist *l, Point p0, Point p1, Point p2, Point p3, int scale)
59 {
60 	Point p01, p12, p23, p012, p123, p0123;
61 	Point tp0, tp1, tp2, tp3;
62 	tp0=divpt(p0, scale);
63 	tp1=divpt(p1, scale);
64 	tp2=divpt(p2, scale);
65 	tp3=divpt(p3, scale);
66 	if(psdist(tp1, tp0, tp3)<=1 && psdist(tp2, tp0, tp3)<=1){
67 		appendpt(l, tp0);
68 		appendpt(l, tp1);
69 		appendpt(l, tp2);
70 	}
71 	else{
72 		/*
73 		 * if scale factor is getting too big for comfort,
74 		 * rescale now & concede the rounding error
75 		 */
76 		if(scale>(1<<12)){
77 			p0=tp0;
78 			p1=tp1;
79 			p2=tp2;
80 			p3=tp3;
81 			scale=1;
82 		}
83 		p01=addpt(p0, p1);
84 		p12=addpt(p1, p2);
85 		p23=addpt(p2, p3);
86 		p012=addpt(p01, p12);
87 		p123=addpt(p12, p23);
88 		p0123=addpt(p012, p123);
89 		bpts1(l, mulpt(p0, 8), mulpt(p01, 4), mulpt(p012, 2), p0123, scale*8);
90 		bpts1(l, p0123, mulpt(p123, 2), mulpt(p23, 4), mulpt(p3, 8), scale*8);
91 	}
92 }
93 
94 static void
95 bpts(Plist *l, Point p0, Point p1, Point p2, Point p3)
96 {
97 	bpts1(l, p0, p1, p2, p3, 1);
98 }
99 
100 static void
101 bezierpts(Plist *l, Point p0, Point p1, Point p2, Point p3)
102 {
103 	bpts(l, p0, p1, p2, p3);
104 	appendpt(l, p3);
105 }
106 
107 static void
108 _bezsplinepts(Plist *l, Point *pt, int npt)
109 {
110 	Point *p, *ep;
111 	Point a, b, c, d;
112 	int periodic;
113 
114 	if(npt<3)
115 		return;
116 	ep = &pt[npt-3];
117 	periodic = eqpt(pt[0], ep[2]);
118 	if(periodic){
119 		a = divpt(addpt(ep[1], pt[0]), 2);
120 		b = divpt(addpt(ep[1], mulpt(pt[0], 5)), 6);
121 		c = divpt(addpt(mulpt(pt[0], 5), pt[1]), 6);
122 		d = divpt(addpt(pt[0], pt[1]), 2);
123 		bpts(l, a, b, c, d);
124 	}
125 	for(p=pt; p<=ep; p++){
126 		if(p==pt && !periodic){
127 			a = p[0];
128 			b = divpt(addpt(p[0], mulpt(p[1], 2)), 3);
129 		}
130 		else{
131 			a = divpt(addpt(p[0], p[1]), 2);
132 			b = divpt(addpt(p[0], mulpt(p[1], 5)), 6);
133 		}
134 		if(p==ep && !periodic){
135 			c = divpt(addpt(mulpt(p[1], 2), p[2]), 3);
136 			d = p[2];
137 		}
138 		else{
139 			c = divpt(addpt(mulpt(p[1], 5), p[2]), 6);
140 			d = divpt(addpt(p[1], p[2]), 2);
141 		}
142 		bpts(l, a, b, c, d);
143 	}
144 	appendpt(l, d);
145 }
146 
147 int
148 bezsplinepts(Point *pt, int npt, Point **pp)
149 {
150 	Plist l;
151 	l.np = 0;
152 	l.p = nil;
153 	_bezsplinepts(&l, pt, npt);
154 	*pp  = l.p;
155 	return l.np;
156 }
157 
158 int
159 bezier(Image *dst, Point p0, Point p1, Point p2, Point p3, int end0, int end1, int radius, Image *src, Point sp)
160 {
161 	return bezierop(dst, p0, p1, p2, p3, end0, end1, radius, src, sp, SoverD);
162 }
163 
164 int
165 bezierop(Image *dst, Point p0, Point p1, Point p2, Point p3, int end0, int end1, int radius, Image *src, Point sp, Drawop op)
166 {
167 	Plist l;
168 
169 	l.np = 0;
170 	bezierpts(&l, p0, p1, p2, p3);
171 	if(l.np == -1)
172 		return 0;
173 	if(l.np != 0){
174 		polyop(dst, l.p, l.np, end0, end1, radius, src, addpt(subpt(sp, p0), l.p[0]), op);
175 		free(l.p);
176 	}
177 	return 1;
178 }
179 
180 int
181 bezspline(Image *dst, Point *pt, int npt, int end0, int end1, int radius, Image *src, Point sp)
182 {
183 	return bezsplineop(dst, pt, npt, end0, end1, radius, src, sp, SoverD);
184 }
185 
186 int
187 bezsplineop(Image *dst, Point *pt, int npt, int end0, int end1, int radius, Image *src, Point sp, Drawop op)
188 {
189 	Plist l;
190 
191 	l.np = 0;
192 	_bezsplinepts(&l, pt, npt);
193 	if(l.np==-1)
194 		return 0;
195 	if(l.np != 0){
196 		polyop(dst, l.p, l.np, end0, end1, radius, src, addpt(subpt(sp, pt[0]), l.p[0]), op);
197 		free(l.p);
198 	}
199 	return 1;
200 }
201 
202 int
203 fillbezier(Image *dst, Point p0, Point p1, Point p2, Point p3, int w, Image *src, Point sp)
204 {
205 	return fillbezierop(dst, p0, p1, p2, p3, w, src, sp, SoverD);
206 }
207 
208 int
209 fillbezierop(Image *dst, Point p0, Point p1, Point p2, Point p3, int w, Image *src, Point sp, Drawop op)
210 {
211 	Plist l;
212 
213 	l.np = 0;
214 	bezierpts(&l, p0, p1, p2, p3);
215 	if(l.np == -1)
216 		return 0;
217 	if(l.np != 0){
218 		fillpolyop(dst, l.p, l.np, w, src, addpt(subpt(sp, p0), l.p[0]), op);
219 		free(l.p);
220 	}
221 	return 1;
222 }
223 
224 int
225 fillbezspline(Image *dst, Point *pt, int npt, int w, Image *src, Point sp)
226 {
227 	return fillbezsplineop(dst, pt, npt, w, src, sp, SoverD);
228 }
229 
230 int
231 fillbezsplineop(Image *dst, Point *pt, int npt, int w, Image *src, Point sp, Drawop op)
232 {
233 	Plist l;
234 
235 	l.np = 0;
236 	_bezsplinepts(&l, pt, npt);
237 	if(l.np == -1)
238 		return 0;
239 	if(l.np > 0){
240 		fillpolyop(dst, l.p, l.np, w, src, addpt(subpt(sp, pt[0]), l.p[0]), op);
241 		free(l.p);
242 	}
243 	return 1;
244 }