smoothing lines and polygons

01 Oct, 2023

My parents had an argument today and things got kinda outta control. So I left home and went over to my friend Souren's place, who was working on an amoeba eating game for a game jam.

At some point he wanted to smooth out the amoeba shape he made, I mentioned that he might want to look into Chaikin's algorithm -- I wanting to smooth out some lines for generative art I made in the past. I got to code it up and added it to the game.

The idea behind Chaikin's algorithm is for every point, we can chop off the tip (essentially flattening the top) and that will create a smoothing effect. For example say we have a teepee shape like the letter $A$, we can flatten the top (imagine the letter without the top and just the middle dash segment) -- in other words we can take the midpoint of the two edges and connect them.

Chaikin's algorithm is a slight modification on this idea. Create a new list where for every line segment (consecutive pair of points) with endpoints at $A$ and $B$, add new points $\frac{1}{4}\overrightarrow{AB}$ and $\frac{3}{4}\overrightarrow{AB}$.

I don't believe code is all that useful or interesting to read in a blog post, but it's in spoilers if you're interested.

module Vec2 = struct
  type t =
    { x : float
    ; y : float
    }
  [@@deriving sexp]

  let ( - ) t1 t2 = { x = t1.x -. t2.x; y = t1.y -. t2.y }
  let ( + ) t1 t2 = { x = t1.x +. t2.x; y = t1.y +. t2.y }
  let scale t factor = { x = t.x *. factor; y = t.y *. factor }
end

let chaikin ~points =
  if Array.length points <= 2
  then points
  else (
    let num_points = Array.length points in
    let new_points = ref [||] in
    let p = 0.25 in
    let q = 1. -. p in
    for i = 0 to num_points - 2 do
      let point1 = points.(i) in
      let point2 = points.(i + 1) in
      let delta = Vec2.( - ) point2 point1 in
      new_points
      := let open Vec2 in
         Array.append !new_points [| point1 + scale delta p; point1 + scale delta q |]
    done;
    !new_points)
;;

let rec smooth ~points ~iterations =
  if iterations <= 0
  then points
  else smooth ~points:(chaikin ~points) ~iterations:(iterations - 1)
;;