sys/src/libdraw/bezier.c

   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 }