bezier.c (4948B)
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 }