Custom Bezier Curve Tool for HTML Canvas, pt. 2

Last time we rendered the curve by connecting the pixels with a series of lines, creating a polyline that estimates the bezier curve. That method may work sometimes, but it often produces artifacts when used for pixel art. This time we’re going to try plotting each pixel one after another. However, this is not a simple matter because a bezier curve is a parametric function where the x and y values depend on time (t). Plotting the curve using t results in points that are equally far apart in terms of time, but not in space.

There are two methods I’m going to use to estimate the next pixel. First, I’m going to choose a default deltaT, then correct that deltaT by dividing it by the actual distance between the coordinates at the current t value and the next t value as estimated by the default deltaT. That constrains deltaT so that the difference in space between coordinates is not more than 1 pixel difference.

The second method I’m going to use will allow us to skip over duplicated pixels and also pixels that are estimated to have too little of the curve passing through them to deserve being plotted. NOTE: The method uses the tangent circle to the curve to estimate which pixel the next point should lie in, and it works great until the curve becomes too sharp of a turn. When the radius of the circle is too small, the circle no longer becomes a good estimate for the bezier curve, and can return the wrong pixel. This is mitigated somewhat by running the algorithm to plot the pixels from both directions, going from t=0 to t=0.5, then going from t=1 to t=0.5. The end result is that curves that are too sharp end up with gaps near it’s zenith.

The formula I’m using to calculate coordinates for a given t hasn’t changed, but I normalized the control points to be a the center of the pixels that they’re on.

function pt(p1, p2, p3, t) {
//center control points on their pixels
p1 += 0.5;
p2 += 0.5;
p3 += 0.5;
return p3 + Math.pow((1 - t), 2) * (p1 - p3) + Math.pow(t, 2) * (p2 - p3);
}

While t<1, I get the coordinates at t, and get the estimate for the next coordinates using a default deltaT. Then divide that deltaT by the distance in space between the points (multiplied by 2 for insurance), and increment t by that amount.

let truext = pt(x1, x2, controlX, t);
let trueyt = pt(y1, y2, controlY, t);
let nextxt = pt(x1, x2, controlX, t + 0.01);
let nextyt = pt(y1, y2, controlY, t + 0.01);
let dist = Math.sqrt(Math.pow(nextxt - truext, 2) + Math.pow(nextyt - trueyt, 2)) * 2;
t += 0.01 / dist;

The method I’m using to estimate the next pixel on the curve first finds the circle tangent to the curve, then checks each of the three pixels in the quadrant that matches the direction of time to see which point is closest to matching the radius of that circle using the distance to the origin of the circle.

//derivatives
let dxt = dpt(x1, x2, controlX, t);
let dyt = dpt(y1, y2, controlY, t);
let ddxt = ddpt(x1, x2, controlX);
let ddyt = ddpt(y1, y2, controlY);
let sign = Math.sign(denom(dxt, dyt, ddxt, ddyt));
let rad = radius(dxt, dyt, ddxt, ddyt);
let s = speed(dxt, dyt);
let circlex = truext - sign * (dyt / s) * rad;
let circley = trueyt - sign * (-dxt / s) * rad;

The functions those are calling:

//derivative for slope
function dpt(p1, p2, p3, t) {
   return -2 * (1 - t) * (p1 - p3) + 2 * t * (p2 - p3);
}
//second derivative for curvature
function ddpt(p1, p2, p3) {
   return 2 * (p1 - p3) + 2 * (p2 - p3);
}
//radius of curvature for parametric functions
function denom(dx, dy, ddx, ddy) {
   return dx * ddy - dy * ddx;
}
function radius(dx, dy, ddx, ddy) {
   let numerator = Math.pow(Math.pow(dx, 2) + Math.pow(dy, 2), 1.5);
   let denominator = denom(dx, dy, ddx, ddy);
   return Math.abs(numerator / denominator);
}
function speed(dx, dy) {
   return Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
}

The closest distance to matching the radius for all 8 possible candidates for the next pixel. Closer to 0 is closer to the radius.

let m1 = Math.abs(Math.sqrt(Math.pow(xt + 1.5 - circlex, 2) + Math.pow(yt + 0.5 - circley, 2)) - rad);
let m2 = Math.abs(Math.sqrt(Math.pow(xt + 1.5 - circlex, 2) + Math.pow(yt + 1.5 - circley, 2)) - rad);
let m3 = Math.abs(Math.sqrt(Math.pow(xt + 0.5 - circlex, 2) + Math.pow(yt + 1.5 - circley, 2)) - rad);
let m4 = Math.abs(Math.sqrt(Math.pow(xt - 0.5 - circlex, 2) + Math.pow(yt + 1.5 - circley, 2)) - rad);
let m5 = Math.abs(Math.sqrt(Math.pow(xt - 0.5 - circlex, 2) + Math.pow(yt + 0.5 - circley, 2)) - rad);
let m6 = Math.abs(Math.sqrt(Math.pow(xt - 0.5 - circlex, 2) + Math.pow(yt - 0.5 - circley, 2)) - rad);
let m7 = Math.abs(Math.sqrt(Math.pow(xt + 0.5 - circlex, 2) + Math.pow(yt - 0.5 - circley, 2)) - rad);
let m8 = Math.abs(Math.sqrt(Math.pow(xt + 1.5 - circlex, 2) + Math.pow(yt - 0.5 - circley, 2)) - rad);

Then set the predicted next pixel to check against in the next iteration of the loop. This part is a lot, so I’ll just show the case for Quadrant I:

let direction = [];
switch (true) {
   case (Math.sign(dxt) === 1 && Math.sign(dyt) === 1):
      //Q1
   direction.push(m1, m2, m3);
   direction.sort();
   switch (direction[0]) {
      case m1:
          xNext = xt + 1;
          yNext = yt;
      break;
      case m2:
          xNext = xt + 1;
          yNext = yt + 1;
      break;
      case m3:
          xNext = xt;
          yNext = yt + 1;
      break;
      default:
          //
   }
   break;
...
}

Finally, plot the integer version of the coordinates to the pixelgrid before iterating again:

ctx.fillRect(xt, yt, scale, scale)

Next time I hope to have implemented an entirely different method that’s much more stable. While this method isn’t recommended, I think it’s good to document the struggle. A promising avenue I’ve found is using Bresenham’s algorithm, but the curve needs to be subdivided into smaller parts to handle gradient changes, which I haven’t figured out how to do yet.