1 ed7c8e8d 2003-09-30 devnull #include <u.h>
2 ed7c8e8d 2003-09-30 devnull #include <libc.h>
3 ed7c8e8d 2003-09-30 devnull #include <draw.h>
5 ed7c8e8d 2003-09-30 devnull #define PINC 32 /* realloc granularity */
7 ed7c8e8d 2003-09-30 devnull typedef struct Plist Plist;
8 ed7c8e8d 2003-09-30 devnull struct Plist
10 ed7c8e8d 2003-09-30 devnull Point *p;
11 ed7c8e8d 2003-09-30 devnull int np; /* -1 if malloc/realloc failed */
14 ed7c8e8d 2003-09-30 devnull static void
15 ed7c8e8d 2003-09-30 devnull appendpt(Plist *l, Point p)
17 ed7c8e8d 2003-09-30 devnull if(l->np == -1)
19 ed7c8e8d 2003-09-30 devnull if(l->np == 0)
20 ed7c8e8d 2003-09-30 devnull l->p = malloc(PINC*sizeof(Point));
21 ed7c8e8d 2003-09-30 devnull else if(l->np%PINC == 0)
22 ed7c8e8d 2003-09-30 devnull l->p = realloc(l->p, (l->np+PINC)*sizeof(Point));
23 ed7c8e8d 2003-09-30 devnull if(l->p == 0){
24 ed7c8e8d 2003-09-30 devnull l->np = -1;
27 ed7c8e8d 2003-09-30 devnull l->p[l->np++] = p;
30 ed7c8e8d 2003-09-30 devnull static int
31 ed7c8e8d 2003-09-30 devnull normsq(Point p)
33 ed7c8e8d 2003-09-30 devnull return p.x*p.x+p.y*p.y;
36 ed7c8e8d 2003-09-30 devnull static int
37 ed7c8e8d 2003-09-30 devnull psdist(Point p, Point a, Point b)
39 ed7c8e8d 2003-09-30 devnull int num, den;
41 ed7c8e8d 2003-09-30 devnull p = subpt(p, a);
42 ed7c8e8d 2003-09-30 devnull b = subpt(b, a);
43 ed7c8e8d 2003-09-30 devnull num = p.x*b.x + p.y*b.y;
44 ed7c8e8d 2003-09-30 devnull if(num <= 0)
45 ed7c8e8d 2003-09-30 devnull return normsq(p);
46 ed7c8e8d 2003-09-30 devnull den = normsq(b);
47 ed7c8e8d 2003-09-30 devnull if(num >= den)
48 ed7c8e8d 2003-09-30 devnull return normsq(subpt(b, p));
49 ed7c8e8d 2003-09-30 devnull return normsq(subpt(divpt(mulpt(b, num), den), p));
53 ed7c8e8d 2003-09-30 devnull * Convert cubic Bezier curve control points to polyline
54 ed7c8e8d 2003-09-30 devnull * vertices. Leaves the last vertex off, so you can continue
55 ed7c8e8d 2003-09-30 devnull * with another curve.
57 ed7c8e8d 2003-09-30 devnull static void
58 ed7c8e8d 2003-09-30 devnull bpts1(Plist *l, Point p0, Point p1, Point p2, Point p3, int scale)
60 ed7c8e8d 2003-09-30 devnull Point p01, p12, p23, p012, p123, p0123;
61 ed7c8e8d 2003-09-30 devnull Point tp0, tp1, tp2, tp3;
62 ed7c8e8d 2003-09-30 devnull tp0=divpt(p0, scale);
63 ed7c8e8d 2003-09-30 devnull tp1=divpt(p1, scale);
64 ed7c8e8d 2003-09-30 devnull tp2=divpt(p2, scale);
65 ed7c8e8d 2003-09-30 devnull tp3=divpt(p3, scale);
66 ed7c8e8d 2003-09-30 devnull if(psdist(tp1, tp0, tp3)<=1 && psdist(tp2, tp0, tp3)<=1){
67 ed7c8e8d 2003-09-30 devnull appendpt(l, tp0);
68 ed7c8e8d 2003-09-30 devnull appendpt(l, tp1);
69 ed7c8e8d 2003-09-30 devnull appendpt(l, tp2);
73 ed7c8e8d 2003-09-30 devnull * if scale factor is getting too big for comfort,
74 ed7c8e8d 2003-09-30 devnull * rescale now & concede the rounding error
76 ed7c8e8d 2003-09-30 devnull if(scale>(1<<12)){
83 ed7c8e8d 2003-09-30 devnull p01=addpt(p0, p1);
84 ed7c8e8d 2003-09-30 devnull p12=addpt(p1, p2);
85 ed7c8e8d 2003-09-30 devnull p23=addpt(p2, p3);
86 ed7c8e8d 2003-09-30 devnull p012=addpt(p01, p12);
87 ed7c8e8d 2003-09-30 devnull p123=addpt(p12, p23);
88 ed7c8e8d 2003-09-30 devnull p0123=addpt(p012, p123);
89 ed7c8e8d 2003-09-30 devnull bpts1(l, mulpt(p0, 8), mulpt(p01, 4), mulpt(p012, 2), p0123, scale*8);
90 ed7c8e8d 2003-09-30 devnull bpts1(l, p0123, mulpt(p123, 2), mulpt(p23, 4), mulpt(p3, 8), scale*8);
94 ed7c8e8d 2003-09-30 devnull static void
95 ed7c8e8d 2003-09-30 devnull bpts(Plist *l, Point p0, Point p1, Point p2, Point p3)
97 ed7c8e8d 2003-09-30 devnull bpts1(l, p0, p1, p2, p3, 1);
100 ed7c8e8d 2003-09-30 devnull static void
101 ed7c8e8d 2003-09-30 devnull bezierpts(Plist *l, Point p0, Point p1, Point p2, Point p3)
103 ed7c8e8d 2003-09-30 devnull bpts(l, p0, p1, p2, p3);
104 ed7c8e8d 2003-09-30 devnull appendpt(l, p3);
107 ed7c8e8d 2003-09-30 devnull static void
108 ed7c8e8d 2003-09-30 devnull _bezsplinepts(Plist *l, Point *pt, int npt)
110 ed7c8e8d 2003-09-30 devnull Point *p, *ep;
111 ed7c8e8d 2003-09-30 devnull Point a, b, c, d;
112 ed7c8e8d 2003-09-30 devnull int periodic;
114 ed7c8e8d 2003-09-30 devnull if(npt<3)
116 ed7c8e8d 2003-09-30 devnull ep = &pt[npt-3];
117 ed7c8e8d 2003-09-30 devnull periodic = eqpt(pt[0], ep[2]);
118 ed7c8e8d 2003-09-30 devnull if(periodic){
119 ed7c8e8d 2003-09-30 devnull a = divpt(addpt(ep[1], pt[0]), 2);
120 ed7c8e8d 2003-09-30 devnull b = divpt(addpt(ep[1], mulpt(pt[0], 5)), 6);
121 ed7c8e8d 2003-09-30 devnull c = divpt(addpt(mulpt(pt[0], 5), pt[1]), 6);
122 ed7c8e8d 2003-09-30 devnull d = divpt(addpt(pt[0], pt[1]), 2);
123 ed7c8e8d 2003-09-30 devnull bpts(l, a, b, c, d);
125 ed7c8e8d 2003-09-30 devnull for(p=pt; p<=ep; p++){
126 ed7c8e8d 2003-09-30 devnull if(p==pt && !periodic){
127 ed7c8e8d 2003-09-30 devnull a = p[0];
128 ed7c8e8d 2003-09-30 devnull b = divpt(addpt(p[0], mulpt(p[1], 2)), 3);
131 ed7c8e8d 2003-09-30 devnull a = divpt(addpt(p[0], p[1]), 2);
132 ed7c8e8d 2003-09-30 devnull b = divpt(addpt(p[0], mulpt(p[1], 5)), 6);
134 ed7c8e8d 2003-09-30 devnull if(p==ep && !periodic){
135 ed7c8e8d 2003-09-30 devnull c = divpt(addpt(mulpt(p[1], 2), p[2]), 3);
136 ed7c8e8d 2003-09-30 devnull d = p[2];
139 ed7c8e8d 2003-09-30 devnull c = divpt(addpt(mulpt(p[1], 5), p[2]), 6);
140 ed7c8e8d 2003-09-30 devnull d = divpt(addpt(p[1], p[2]), 2);
142 ed7c8e8d 2003-09-30 devnull bpts(l, a, b, c, d);
144 ed7c8e8d 2003-09-30 devnull appendpt(l, d);
148 ed7c8e8d 2003-09-30 devnull bezsplinepts(Point *pt, int npt, Point **pp)
150 ed7c8e8d 2003-09-30 devnull Plist l;
151 ed7c8e8d 2003-09-30 devnull l.np = 0;
152 ed7c8e8d 2003-09-30 devnull l.p = nil;
153 ed7c8e8d 2003-09-30 devnull _bezsplinepts(&l, pt, npt);
154 ed7c8e8d 2003-09-30 devnull *pp = l.p;
155 ed7c8e8d 2003-09-30 devnull return l.np;
159 ed7c8e8d 2003-09-30 devnull bezier(Image *dst, Point p0, Point p1, Point p2, Point p3, int end0, int end1, int radius, Image *src, Point sp)
161 ed7c8e8d 2003-09-30 devnull return bezierop(dst, p0, p1, p2, p3, end0, end1, radius, src, sp, SoverD);
165 ed7c8e8d 2003-09-30 devnull bezierop(Image *dst, Point p0, Point p1, Point p2, Point p3, int end0, int end1, int radius, Image *src, Point sp, Drawop op)
167 ed7c8e8d 2003-09-30 devnull Plist l;
169 ed7c8e8d 2003-09-30 devnull l.np = 0;
170 ed7c8e8d 2003-09-30 devnull bezierpts(&l, p0, p1, p2, p3);
171 ed7c8e8d 2003-09-30 devnull if(l.np == -1)
172 ed7c8e8d 2003-09-30 devnull return 0;
173 ed7c8e8d 2003-09-30 devnull if(l.np != 0){
174 ed7c8e8d 2003-09-30 devnull polyop(dst, l.p, l.np, end0, end1, radius, src, addpt(subpt(sp, p0), l.p[0]), op);
175 ed7c8e8d 2003-09-30 devnull free(l.p);
177 ed7c8e8d 2003-09-30 devnull return 1;
181 ed7c8e8d 2003-09-30 devnull bezspline(Image *dst, Point *pt, int npt, int end0, int end1, int radius, Image *src, Point sp)
183 ed7c8e8d 2003-09-30 devnull return bezsplineop(dst, pt, npt, end0, end1, radius, src, sp, SoverD);
187 ed7c8e8d 2003-09-30 devnull bezsplineop(Image *dst, Point *pt, int npt, int end0, int end1, int radius, Image *src, Point sp, Drawop op)
189 ed7c8e8d 2003-09-30 devnull Plist l;
191 ed7c8e8d 2003-09-30 devnull l.np = 0;
192 ed7c8e8d 2003-09-30 devnull _bezsplinepts(&l, pt, npt);
193 ed7c8e8d 2003-09-30 devnull if(l.np==-1)
194 ed7c8e8d 2003-09-30 devnull return 0;
195 ed7c8e8d 2003-09-30 devnull if(l.np != 0){
196 ed7c8e8d 2003-09-30 devnull polyop(dst, l.p, l.np, end0, end1, radius, src, addpt(subpt(sp, pt[0]), l.p[0]), op);
197 ed7c8e8d 2003-09-30 devnull free(l.p);
199 ed7c8e8d 2003-09-30 devnull return 1;
203 ed7c8e8d 2003-09-30 devnull fillbezier(Image *dst, Point p0, Point p1, Point p2, Point p3, int w, Image *src, Point sp)
205 ed7c8e8d 2003-09-30 devnull return fillbezierop(dst, p0, p1, p2, p3, w, src, sp, SoverD);
209 ed7c8e8d 2003-09-30 devnull fillbezierop(Image *dst, Point p0, Point p1, Point p2, Point p3, int w, Image *src, Point sp, Drawop op)
211 ed7c8e8d 2003-09-30 devnull Plist l;
213 ed7c8e8d 2003-09-30 devnull l.np = 0;
214 ed7c8e8d 2003-09-30 devnull bezierpts(&l, p0, p1, p2, p3);
215 ed7c8e8d 2003-09-30 devnull if(l.np == -1)
216 ed7c8e8d 2003-09-30 devnull return 0;
217 ed7c8e8d 2003-09-30 devnull if(l.np != 0){
218 ed7c8e8d 2003-09-30 devnull fillpolyop(dst, l.p, l.np, w, src, addpt(subpt(sp, p0), l.p[0]), op);
219 ed7c8e8d 2003-09-30 devnull free(l.p);
221 ed7c8e8d 2003-09-30 devnull return 1;
225 ed7c8e8d 2003-09-30 devnull fillbezspline(Image *dst, Point *pt, int npt, int w, Image *src, Point sp)
227 ed7c8e8d 2003-09-30 devnull return fillbezsplineop(dst, pt, npt, w, src, sp, SoverD);
231 ed7c8e8d 2003-09-30 devnull fillbezsplineop(Image *dst, Point *pt, int npt, int w, Image *src, Point sp, Drawop op)
233 ed7c8e8d 2003-09-30 devnull Plist l;
235 ed7c8e8d 2003-09-30 devnull l.np = 0;
236 ed7c8e8d 2003-09-30 devnull _bezsplinepts(&l, pt, npt);
237 ed7c8e8d 2003-09-30 devnull if(l.np == -1)
238 ed7c8e8d 2003-09-30 devnull return 0;
239 ed7c8e8d 2003-09-30 devnull if(l.np > 0){
240 ed7c8e8d 2003-09-30 devnull fillpolyop(dst, l.p, l.np, w, src, addpt(subpt(sp, pt[0]), l.p[0]), op);
241 ed7c8e8d 2003-09-30 devnull free(l.p);
243 ed7c8e8d 2003-09-30 devnull return 1;