Optimal step for drawing Bezier curve

Question

Bezier curves are parametric in the sense that for each dimension their polynomials share common parameter $t$ [1]. To draw a Bezier curve on screen one could increment $t$ by tiny step and calculate the pixels along the curve. The problem is that if $t$ is too tiny the computed position along the curve may "fall" on just one pixel several times.

My question is, how to find such step that no pixel will be drawn more than once? I am interested in finding it in O(1) (I could use De Casteljau's algorithm [2] to recursively subdivide the curve but I would like to find the step faster). It is ok if the step produces pixels sparsely at some part of the curve - I don't mind the "gaps" between pixels as long as no pixel will be drawn over again.

More formally, how to find the smallest uniform step which increases Cartesian distance from previous point at least by 1 pixel?

[1] https://en.wikipedia.org/wiki/B%C3%A9zier_curve#Specific_cases
[2] https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm

Answer 1

Let's call the original curve $\mathbf{F}(t)$. Compute the derivative curve $\mathbf{G}(t) = \mathbf{F}'(t)$, where the prime denotes differentiation with respect to $t$. It is well known that $\mathbf{G}(t)$ will be another Bezier curve whose degree is one less than the degree of your original curve $\mathbf{F}(t)$. So, if $\mathbf{F}(t)$ is a cubic curve (the most common case), then $\mathbf{G}(t)$ will be quadratic.

Using the convex hull property of $\mathbf{G}(t)$ (or otherwise), find a number $r$ such that $\| \mathbf{G}(t)\| \ge r$ for all $t \in [0,1]$.

Let $\delta s$ be the smallest step you want to take along the curve, which in your case will be the width (or the diagonal) of a pixel. Then choose $\delta t \ge \delta s / r$, and step along your curve using parameter increments of $\delta t$.

The problem with this is that $r$ might be zero, though it's highly unlikely that this will happen in practice. If you're worried about this, then you'll need to add some special logic to deal with it. For example, you could split the curve into two at the point where $\| \mathbf{G}(t)\| = 0$, and handle this nasty point as a special case. There can only be one such place on a cubic Bezier curve, fortunately.

Another problem is that the curve might loop back and intersect itself, in which case it's very difficult to avoid drawing the same pixel twice, of course.

Answer 2

We ought to be developing the points of the desired curve, not serially (by bumping the value of the parameter by a fixed amount), but recursively (wherein each new value of the parameter would be the median of the parameter values of the last two points that were created). During this recursive process, the distance from each new point to both of the two previous points would be compared to a certain minimally acceptable arbitrary distance. When both of the distances fall below the arbitrary minimal distance, that particular branch of the recursion would be shut down. The starting values of the parameter for this recursion would, of course, be 0 and 1.