lib/gfxpoly/stroke.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <math.h>
   4 #include "../gfxdevice.h"
   5 #include "../gfxtools.h"
   6 #include "poly.h"
   7 #include "wind.h"
   8 #include "convert.h"
   9
  10 /* notice: left/right for a coordinate system where y goes up, not down */
  11 typedef enum {LEFT=0, RIGHT=1} leftright_t;
  12
  13 /* factor that determines into how many line fragments a spline is converted */
  14 #define SUBFRACTION (2.4)
  15
  16 // spline equation:
  17 // s(t) = t*t*x2 + 2*t*(1-t)*cx + (1-t)*(1-t)*x1
  18 //
  19 // s(0.5) = 0.25*x2 + 0.5*cx + 0.25*x1
  20 // ds(t)/dt = 2*t*x2 + (2-2t)*cx + (2t-2)*x1
  21 // ds(0) = 2*(cx-x1)
  22
  23 static void draw_arc(gfxdrawer_t*draw, double x, double y, double a1, double a2, double r)
  24 {
  25     if(a2<a1) a2+=M_PI*2;
  26
  27     double d = (a2-a1);
  28     int steps = ceil(8*d/(M_PI*2)); // we use 8 splines for a full circle
  29     if(!steps) return;
  30
  31     int t;
  32     double step = (a2-a1)/steps;
  33     double lastx = x+cos(a1)*r;
  34     double lasty = y+sin(a1)*r;
  35
  36     /* we could probably build a table for this- there are only 8
  37        possible values for step */
  38     double r2 = r*(2-sqrt(0.5+0.5*cos(step)));
  39
  40     for(t=1;t<=steps;t++) {
  41         double a = a1 + t*step;
  42         double c = cos(a)*r;
  43         double s = sin(a)*r;
  44         double xx = c + x;
  45         double yy = s + y;
  46         //double dx = (s*step/2 + lastx);
  47         //double dy = (-c*step/2 + lasty);
  48         double dx = x + cos(a-step/2)*r2;
  49         double dy = y + sin(a-step/2)*r2;
  50         //draw->lineTo(draw, xx, yy);
  51         draw->splineTo(draw, dx, dy, xx, yy);
  52         lastx = xx;
  53         lasty = yy;
  54     }
  55 }
  56
  57 static void draw_single_stroke(gfxpoint_t*p, int num, gfxdrawer_t*draw, double width, gfx_capType cap, gfx_joinType join, double limit)
  58 {
  59     char do_draw=0;
  60     leftright_t lastdir = LEFT;
  61
  62     width/=2;
  63     if(width<=0)
  64         width = 0.05;
  65
  66     /* remove duplicate points */
  67     int s=1,t;
  68     for(t=1;t<num;t++) {
  69         p[s] = p[t];
  70         if(p[t].x != p[t-1].x || p[t].y != p[t-1].y) {
  71             s++;
  72         } else {
  73             num--;
  74         }
  75     }
  76
  77     int start = 0;
  78     int end = num-1;
  79     int incr = 1;
  80     int pos = 0;
  81
  82     double alimit = atan(limit / width);
  83
  84     /* iterate through the points two times: first forward, then backward,
  85        adding a stroke outline to the right side and line caps after each
  86        pass */
  87     int pass;
  88     double lastw=0;
  89     for(pass=0;pass<2;pass++) {
  90         int pos;
  91         for(pos=start;pos!=end;pos+=incr) {
  92             //printf("%d) %.2f %.2f\n", pos, p[pos].x, p[pos].y);
  93             double dx = p[pos+incr].x - p[pos].x;
  94             double dy = p[pos+incr].y - p[pos].y;
  95             double l = sqrt(dx*dx+dy*dy);
  96             double w = atan2(dy,dx);
  97             if(w<0) w+=M_PI*2;
  98
  99             if(pos!=start) {
 100                 double d = w-lastw;
 101                 leftright_t turn;
 102                 if(d>=0 && d<M_PI) turn=LEFT;
 103                 else if(d<0 && d>-M_PI) turn=RIGHT;
 104                 else if(d>=M_PI) {turn=RIGHT;}
 105                 else if(d<=-M_PI) {turn=LEFT;d+=M_PI*2;}
 106                 else {assert(0);}
 107                 if(turn!=LEFT || join==gfx_joinBevel) {
 108                     /* TODO: does a bevel join extend beyond the segment (i.e.,
 109                        is it like a square cap or like a butt cap? */
 110                 } else if(join==gfx_joinRound) {
 111                     draw_arc(draw, p[pos].x, p[pos].y, lastw-M_PI/2, w-M_PI/2, width);
 112                 } else if(join==gfx_joinMiter) {
 113                     if(d/2<alimit) {
 114                         double r2 = width*(1-sin(d/2)+tan(d/2));
 115                         double addx = cos(lastw-M_PI/2+d/2)*r2;
 116                         double addy = sin(lastw-M_PI/2+d/2)*r2;
 117                         draw->lineTo(draw, p[pos].x+addx, p[pos].y+addy);
 118                     } else {
 119                         /* convert to bevel join, which always looks the same (is
 120                            independent of miterLimit TODO: verify this */
 121                     }
 122                 }
 123             }
 124
 125             double addx = cos(w-M_PI/2)*width;
 126             double addy = sin(w-M_PI/2)*width;
 127             draw->lineTo(draw, p[pos].x+addx, p[pos].y+addy);
 128             //printf("-- %.2f %.2f (angle:%d)\n", px1, py1, (int)(180*w/M_PI));
 129             double px2 = p[pos+incr].x + addx;
 130             double py2 = p[pos+incr].y + addy;
 131             //printf("-- %.2f %.2f (angle:%d)\n", px2, py2, (int)(180*w/M_PI));
 132             draw->lineTo(draw, p[pos+incr].x+addx, p[pos+incr].y+addy);
 133
 134             lastw = w;
 135         }
 136         /* draw stroke ends. We draw duplicates of some points here. The drawer
 137            implementationshould be smart enough to remove them. */
 138         double c = cos(lastw-M_PI/2)*width;
 139         double s = sin(lastw-M_PI/2)*width;
 140         if(cap == gfx_capButt) {
 141             draw->lineTo(draw, p[pos].x+c, p[pos].y+s);
 142             draw->lineTo(draw, p[pos].x-c, p[pos].y-s);
 143         } else if(cap == gfx_capRound) {
 144             draw->lineTo(draw, p[pos].x+c, p[pos].y+s);
 145             draw_arc(draw, p[pos].x, p[pos].y, lastw-M_PI/2, lastw+M_PI/2, width);
 146         } else if(cap == gfx_capSquare) {
 147             double c = cos(lastw-M_PI/2)*width;
 148             double s = sin(lastw-M_PI/2)*width;
 149             draw->lineTo(draw, p[pos].x+c, p[pos].y+s);
 150             draw->lineTo(draw, p[pos].x+c-s, p[pos].y+s+c);
 151             draw->lineTo(draw, p[pos].x-c-s, p[pos].y-s+c);
 152             draw->lineTo(draw, p[pos].x-c, p[pos].y-s);
 153         }
 154         start=num-1;
 155         end=0;
 156         incr=-1;
 157         lastw += M_PI; // for dots
 158     }
 159 }
 160
 161 static void draw_stroke(gfxline_t*start, gfxdrawer_t*draw, double width, gfx_capType cap, gfx_joinType join, double miterLimit)
 162 {
 163     if(!start)
 164         return;
 165     assert(start->type == gfx_moveTo);
 166     gfxline_t*line = start;
 167     // measure array size
 168     int size = 0;
 169     int pos = 0;
 170     double lastx,lasty;
 171     while(line) {
 172         if(line->type == gfx_moveTo) {
 173             if(pos>size) size = pos;
 174             pos++;
 175         } else if(line->type == gfx_lineTo) {
 176             pos++;
 177         } else if(line->type == gfx_splineTo) {
 178             int parts = (int)(sqrt(fabs(line->x-2*line->sx+lastx) + fabs(line->y-2*line->sy+lasty))*SUBFRACTION);
 179             if(!parts) parts = 1;
 180             pos+=parts+1;
 181         }
 182         lastx = line->x;
 183         lasty = line->y;
 184         line = line->next;
 185     }
 186     if(pos>size) size = pos;
 187     if(!size) return;
 188
 189     gfxpoint_t* points = malloc(sizeof(gfxpoint_t)*size);
 190     line = start;
 191     pos = 0;
 192     while(line) {
 193         if(line->type == gfx_moveTo) {
 194             if(pos) draw_single_stroke(points, pos, draw, width, cap, join, miterLimit);
 195             pos = 0;
 196         } else if(line->type == gfx_splineTo) {
 197             int parts = (int)(sqrt(fabs(line->x-2*line->sx+lastx) + fabs(line->y-2*line->sy+lasty))*SUBFRACTION);
 198             if(!parts) parts = 1;
 199             double stepsize = 1.0/parts;
 200             int i;
 201             for(i=0;i<parts;i++) {
 202                 double t = (double)i*stepsize;
 203                 points[pos].x = (line->x*t*t + 2*line->sx*t*(1-t) + lastx*(1-t)*(1-t));
 204                 points[pos].y = (line->y*t*t + 2*line->sy*t*(1-t) + lasty*(1-t)*(1-t));
 205                 pos++;
 206             }
 207         }
 208         lastx = points[pos].x = line->x;
 209         lasty = points[pos].y = line->y;
 210         pos++;
 211         line = line->next;
 212     }
 213     if(pos) draw_single_stroke(points, pos, draw, width, cap, join, miterLimit);
 214     free(points);
 215 }
 216
 217 static windcontext_t onepolygon = {1};
 218 gfxpoly_t* gfxpoly_from_stroke(gfxline_t*line, gfxcoord_t width, gfx_capType cap_style, gfx_joinType joint_style, gfxcoord_t miterLimit, double gridsize)
 219 {
 220     gfxdrawer_t d;
 221     gfxdrawer_target_poly(&d, gridsize);
 222     draw_stroke(line, &d, width, cap_style, joint_style, miterLimit);
 223     gfxpoly_t*poly = (gfxpoly_t*)d.result(&d);
 224     assert(gfxpoly_check(poly));
 225     gfxpoly_t*poly2 = gfxpoly_process(poly, 0, &windrule_circular, &onepolygon);
 226     gfxpoly_destroy(poly);
 227     return poly2;
 228 }
 229