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