Pixel Art Algorithm: Drawing Smooth Bezier Curves

Jan 12, 2019

This post is a demo of the vector tool in my pixel art editor tool Xprite.

Press b for pencil. Pressv for vector. F5 to clear canvas.

this is from quickhoney(not made by me)

The algorithm

Store cursor positions as a polyline(a vector of coordinates).
Simplify polyline. Connect two points with a line and check if the distance between next point and line exceeds some predefined threshold.
Interpolate. Convert the simplified polyline into a vector of cubic bezier curves. I used an implementation from d3.
Segment each bezier curve to monotonic subcurves. The pixel sorting algorithm(from previous post) only works with monotonically increasing or decreasing curves whose first and second derivatives don’t change sign. This is done by solving quadratic and cubic bezier equation for t to find extrema.
Rasterize by sampling. I use indexset to store continuous lines. Dedupe takes O(1) time.
Optimize pixel selection cost. Each pixel in the rasterized line is scored by distance from center to the smooth curve. The goal is to minimize total cost. However, this step is not used since this problem in NP and I’m not sure how to speed up(or if it’s even possible).
Pixel perfect. As an alternative to step 6, removing intermediate pixels actually works pretty well.
Finally. Sort monotonic segments by slope. See my previous post on this.