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
appendpt(Plist * l,Point p)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
normsq(Point p)31 normsq(Point p)
32 {
33 return p.x*p.x+p.y*p.y;
34 }
35
36 static int
psdist(Point p,Point a,Point b)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
bpts1(Plist * l,Point p0,Point p1,Point p2,Point p3,int scale)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
bpts(Plist * l,Point p0,Point p1,Point p2,Point p3)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
bezierpts(Plist * l,Point p0,Point p1,Point p2,Point p3)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
_bezsplinepts(Plist * l,Point * pt,int npt)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
bezsplinepts(Point * pt,int npt,Point ** pp)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
bezier(Image * dst,Point p0,Point p1,Point p2,Point p3,int end0,int end1,int radius,Image * src,Point sp)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
bezierop(Image * dst,Point p0,Point p1,Point p2,Point p3,int end0,int end1,int radius,Image * src,Point sp,Drawop op)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
bezspline(Image * dst,Point * pt,int npt,int end0,int end1,int radius,Image * src,Point sp)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
bezsplineop(Image * dst,Point * pt,int npt,int end0,int end1,int radius,Image * src,Point sp,Drawop op)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
fillbezier(Image * dst,Point p0,Point p1,Point p2,Point p3,int w,Image * src,Point sp)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
fillbezierop(Image * dst,Point p0,Point p1,Point p2,Point p3,int w,Image * src,Point sp,Drawop op)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
fillbezspline(Image * dst,Point * pt,int npt,int w,Image * src,Point sp)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
fillbezsplineop(Image * dst,Point * pt,int npt,int w,Image * src,Point sp,Drawop op)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 }
245