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.

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

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

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

Javascript Editor

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

The current codebase has now 1285 lines ps20240722.js

My Journey to PostScript