Bezier curves

Until now, we can draw straight lines for our polygons, but not curves. However, curves are everywhere, also in the typography. So we need a way to represent any type of curves mathematically in a way that the specification is both simple and performant.

Bevor the Bezier curves, costume designers and architects had this instrument called french curve or pistolet in french. It is a plastic template to draw curves of any radius. My architect parents had in their atelier.

After the World War II, the automobile industry and the fast growing economy asked for the fast development of new models. Pierre Bezier worked in the 1960s as engineer for Renault and developed Unisurf Cad, one of the earliest CAD softwares. The Peugeot 204 was the first car developed with this software using Bezier curves.

However, Bezier was not alone. The engineer Paul de Castelijau worked for Citroën and had the same idea. He invented cubic Bezier curves already in 1959.

It happens sometimes that multiple clever people have the same idea at the same time, because the idea is ready. If you want split the credits, Castelijau developed the astonishing simple algorithm we will use, while Bezier takes credits for that curve handles you see in each layout program.

So what is a cubic Bezier curve? The curve is defined by four points P0, P1, P2 and P3. Only P0 and P3 are on the curve. The other points P2 and P3 act like gravity points and form the vectors V0 and V3 with their counterpart points P0 and P3. The longer the vectors are and the more they point fare away from the opposite point, the more likely the curve will stay at the starting point.

100 100 moveto 100 150 200 150 200 100 curveto stroke
100 100 moveto 100 150 lineto 95 145 lineto 100 150 moveto 105 145 lineto stroke
200 100 moveto 200 150 lineto 195 145 lineto 200 150 moveto 205 145 lineto stroke
90 90 moveto (P0) show
190 90 moveto (P3) show
90 155 moveto (P1) show
190 155 moveto (P2) show

300 100 moveto 300 125 450 200 400 100 curveto stroke
300 100 moveto 300 125 lineto 295 120 lineto 300 125 moveto 305 120 lineto stroke
400 100 moveto 450 200 lineto 445 195 lineto 450 200 moveto 455 195 lineto stroke
290 90 moveto (P0) show
390 90 moveto (P3) show
290 130 moveto (P1) show
450 205 moveto (P2) show

showpage

De Caseljau showed that with a simple linear interpolation, a cubic Bezier curve could be split into two Bezier curves. If you do that recursively, you finish either with a straight line at least for the resolution we are drawing. So the algorithms converts the curve in a sequence of lines we can handle.

If the original points are P0, P1, P2, P3 then you calculate P4 as center of [P0 P1], P5 as center of [P1 P2], P6 as center of [P2 P3]. Then you calculate P7 as center of [P4 P5], P8 as center of [P5 P6]. Finally you calculate P9 as center of [P7 P8]. (The triple linear interpolation represents the cubic character of this curve.)

The you have to new curves:

P0 P4 P7 P9
P9 P8 P6 P3

P1 and P2 are out of the game

200 100 moveto 200 200 450 280 400 100 curveto stroke
200 100 moveto 200 200 lineto 195 195 lineto 200 200 moveto 205 195 lineto stroke
400 100 moveto 450 280 lineto 442 278 lineto 450 280 moveto 453 273 lineto stroke
190 90 moveto (P0) show
390 90 moveto (P3) show
190 210 moveto (P1) show
450 285 moveto (P2) show

0.7 setgray
200 200 moveto 450 280 lineto stroke
200 150 moveto 325 240 lineto stroke
325 240 moveto 425 190 lineto stroke
262.50 195 moveto 375 215 lineto stroke

0 setgray
180 150 moveto (P4) show
314 245 moveto (P5) show
430 185 moveto (P6) show
245 195 moveto (P7) show
380 215 moveto (P8) show
315 210 moveto (P9) show

showpage

We create a bezier function which takes a curve path element and returns an array of lines.

Javascript

bezier = function (curve, depth = -1) {
    const [ type, x0, y0, x1, y1, x2, y2, x3, y3 ] = curve;
    // distance of points to line
    var d1 = 0;
    var d2 = 0;
    if (x0 == x3) {
        d1 = Math.abs(x1 - x0);
        d2 = Math.abs(x2 - x0);
    } else {
        const m = (y3 - y0) / (x3 - x0);
        const p = y0 - m * x0;
        d1 = Math.abs(y1 - m * x1 - p) /  Math.sqrt(1 + m*m)
        d2 = Math.abs(y2 - m * x2 - p) /  Math.sqrt(1 + m*m)
    }
    if (d1 < 1 && d2 < 1) {
        return [ [ "L", x0, y0, x3, y3 ] ];
    }
    if (!depth) return [ [ "L", x0, y0, x3, y3 ] ];
 
    const x4 =  (x0 + x1) / 2;
    const y4 =  (y0 + y1) / 2;
    const x5 =  (x1 + x2) / 2;
    const y5 =  (y1 + y2) / 2;
    const x6 =  (x2 + x3) / 2;
    const y6 =  (y2 + y3) / 2;
    const x7 =  (x4 + x5) / 2;
    const y7 =  (y4 + y5) / 2;
    const x8 =  (x5 + x6) / 2;
    const y8 =  (y5 + y6) / 2;
    const x9 =  (x7 + x8) / 2;
    const y9 =  (y7 + y8) / 2;

return bezier(["C", x0, y0, x4, y4, x7, y7, x9, y9], depth - 1).concat(bezier(["C", x9, y9, x8, y8, x6, y6, x3, y3], depth - 1)); 
}

We also rewrite scanfill as independent function.

Javascript

scanfill = function (path, width, height, color, data) {
   const crossings = [];

for (var line of path) {
      var [type, x0, y0, x1, y1] = line;
      const dx = x1 - x0;
      const dy = y1 - y0;
      if (dy) {
          if (y1 < y0) { 
              [y0, y1] = [y1, y0];
              [x0, x1] = [x1, x0];
          }
          const ex = dx / dy;
          const y0c = Math.ceil(y0);
          var x = x0 + ex * (y0c - y0);
          for(var y = y0c; y < y1; y++) {
              if (y >= 0 && y < height) {
                 if (! crossings[y] ) crossings[y] = [];
                 crossings[y].push(x);
              }
              x += ex;
          }
       }
    }

for (var y in crossings) {
       const arr = crossings[y];
       arr.sort(function (a, b) { return a - b }); 
       for (var i = 0; i < arr.length - 1; i += 2) {
          var xstart = Math.round(arr[i]);
          var xend = Math.round(arr[i + 1]);
          var offset = ((height - 1 - y) * width + xstart) * 4;
          for (var j = xstart; j < xend; j++) {                 
              for (var c = 0; c < 4; c++) {
                    data[offset + c] = color[c];
              }
              offset += 4;
          }
       } 
    }

return data;

};

Rewrite the fill operator and add the curveto and rcurveto operator.

Javascript

operators.fill = function(context) {

// flatten the path
   const flatpath = [];
   for (var subpath of context.graphics.path) {
       for (var line of subpath) {
           if (line[0] == "C") {
               const lines = bezier(line,-1);
               for (var elem of lines) {
                   flatpath.push(elem)
               }
           } else {
               flatpath.push(line);
           }
       }
   }         
   context.data = scanfill(flatpath, context.width, context.height, context.graphics.color, context.data)
 
    context.graphics.path = [];
    context.graphics.current = [];

return context; 
};   
unitTest("fill","");

operators.stroke = function(context) {
    // flatten the path
   const flatpath = [];
   for (var subpath of context.graphics.path) {
       for (var line of subpath) {
           if (line[0] == "C") {
               const lines = bezier(line,-1);
               for (var elem of lines) {
                   flatpath.push(elem)
               }
           } else {
               flatpath.push(line);
           }
       }
   }         
   for (var line of flatpath) {
      const [type, x0, y0, x1, y1] = line;
      const dx = x1 - x0;
      const dy = y1 - y0;
      const steps = Math.max(Math.abs(dx), Math.abs(dy));
      if (steps) {
          const ex = (x1 - x0) / steps;
          const ey = (y1 - y0) / steps;
          var x = x0;
          var y = y0;
          for (var i = 0; i < steps; i++) {
              offset = ((context.height - 1 - Math.round(y)) * context.width + Math.round(x) ) * 4;
              for (var c = 0; c < 4; c++) {
                  context.data[offset + c] = context.graphics.color[c];
              }
              x  += ex;
              y  += ey;
          }    
       }
    }
    
    context.graphics.path = [];
    context.graphics.current = [];

return context;
};

unitTest("stroke","");

operators.curveto = function(context) {
    const [y3, x3, y2, x2, y1, x1] = context.pop("number","number","number","number","number","number");
    if (!y3) return context;
    if (!context.graphics.current.length) {
       context.stack.push(new rpnError("nocurrentpoint"));
    } else if (!context.graphics.path.length) {
       context.stack.push(new rpnError("nocurrentpath"));
    } else {
      const subpath = context.graphics.path.pop();
      subpath.push([ "C", context.graphics.current[0], context.graphics.current[1], x1.value, y1.value, x2.value, y2.value, x3.value, y3.value ]);
      context.graphics.path.push(subpath); 
      context.graphics.current = [ x3.value, y3.value ];
    }
    return context;
};

unitTest("100 50 moveto 100 90 50 90 50 50 curveto",'');
unitTest("100 50 moveto 100 90 50 90 50 50 curveto currentpoint","50 50");
unitTest("100 90 50 90 50 50 curveto","!nocurrentpoint"); 
unitTest("(a) 100 90 50 90 50 curveto","!typeerror"); 
unitTest("100 90 50 90 50 curveto","100 90 50 90 50 !stackunderflow");

operators.rcurveto = function(context) {
    const [y3, x3, y2, x2, y1, x1] = context.pop("number","number","number","number","number","number");
    if (!y3) return context;
    if (!context.graphics.current.length) {
       context.stack.push(new rpnError("nocurrentpoint"));
    } else if (!context.graphics.path.length) {
       context.stack.push(new rpnError("nocurrentpath"));
    } else {
       const subpath = context.graphics.path.pop();
       subpath.push([ "C", context.graphics.current[0], context.graphics.current[1], context.graphics.current[0] + x1.value, context.graphics.current[1] + y1.value, context.graphics.current[0] + x2.value, context.graphics.current[1] + y2.value, context.graphics.current[0] + x3.value, context.graphics.current[1] + y3.value ]);
       context.graphics.path.push(subpath); 
       context.graphics.current = [ context.graphics.current[0] + x3.value, context.graphics.current[1] + y3.value ];       
    }
    return context;
};

unitTest("100 50 moveto 100 90 50 90 50 50 rcurveto",'');
unitTest("100 50 moveto 100 90 50 90 50 50 rcurveto currentpoint","150 100");
unitTest("100 90 50 90 50 50 rcurveto","!nocurrentpoint"); 
unitTest("(a) 100 90 50 90 50 rcurveto","!typeerror"); 
unitTest("100 90 50 90 50 rcurveto","100 90 50 90 50 !stackunderflow");

Some drawings with curves

Javascript Editor

PostScript

Some letters with and without curves. The "O" looks rough because we do not have any antialiasing at all here.

Javascript Editor

PostScript

Bezier cannot draw every curve exactly, but it can imitate it very well. With 4 points, it can imitate a circle with 99% precision. The formula for circle is with n segments distance to the control points, is (4/3)*tan(pi/(2n)).

On the left, a rough cercle with only 2 points and on the right a quite perfect circle with 4 points.

Javascript Editor

PostScript

The current codebase has now 1285 lines ps20240722.js

My Journey to PostScript