How to smooth a very narrow quadratic bezier curve with a very low number of points?

Question

I am a software engineer working on a whiteboard application for iOS. One of the features we have is a drawing tool. This tool gathers x,y coordinates and other information like the applied pressure, velocity, azimuth and altitude from a user's gestures and performs several operations to make the drawing look natural.

From the data we capture - besides the coordinate - we compute an scalar called thickness which represents how thick the stroke is at a given point.

The curve and the thickness transition needs to be smooth to look natural. To smooth those we use a quadratic bezier. As part of the smoothing process we compute the normal to tangent of each point in the curve and normalize it.

Then for each point we multiply the thickness by the normal and add or subtract that from the point in the curve and then triangulate the result as shown in the figure below:

Drawing explained

To decide on the amount of points required in the curve to make the drawing stroke smooth enough, we estimate the length of the curve by summing the distance between the first point to the control point and from the control point to the second point.

That works pretty well. However there are instances where the curve is too narrow and the distance between the points is very small but the normal to the tangents vary significantly. Such characteristic results in sharp edges, as shown below:

Problem explained

In order to generate a smooth curve on those scenarios, much more points are required, way more than the length of the curve. On my tests, I observed that while 3-100 points are required to obtain a smooth curve on the majority of the curves, these required about 1000 to start looking smooth/rounded.

Such number of points is just too much for us to tessellate for a single curve in a single stroke, as the application allows for an infinite number of drawing strokes to exist at the same time.

This is my fourth day working on the matter. I've tried many different approaches. The one I am working on now regards identifying the normal varied too much between two points and instead of just adding that point to the data model, compute an ellipses that has a similar curvature and generate points that represent that ellipses instead of trying to further smooth the gap between those two points using bezier, in hopes the curve looks similar enough using way less points.

I am looking for solutions which are not computationally expensive and still provide good results.

Any ideas?

Thanks!

Answer 1

I don't understand your second picture at all.

But, anyway, the number of points you need to get a smooth-looking curve can't be the same for all curves. Also, it can't be computed from arclength: a straight line will only require two points no matter how long it is.

A polyline is a spline of degree 1, and spline theory tells us how to approximate curves by splines. Specifically, suppose we sample a curve $X(t)$ at parameter values $t_0, \ldots, t_n$, and let $\Delta t = \max\{t_i - t_{i-1}: i = 1,2,\dots,n\}$. Let $L(t)$ be the polyline constructed from the points $L(t_0), \ldots, L(t_n)$. Then the error when approximating $X$ by $L$ on the interval $I = [t_0,t_n]$ is given by $$ \max\{\|X(t) - L(t)\| : t \in I\} \le \frac18(\Delta t)^2 \max\{\|X''(t)\| : t \in I\} $$ More info on this in these notes.

So, if you want the approximation error to be less than some given number $\varepsilon$, then you have to choose $\Delta t$ such that $$ \frac18(\Delta t)^2 \max\{\|C''(t)\| : t \in I\} < \varepsilon $$ If the $n$ sample points are equally spaced, then $\Delta t = \frac1n$, so we need to choose $n$ such that $$ \frac{1}{8n^2} \max\{\|X''(t)\| : t \in I\} < \varepsilon $$ which means $$ n > \sqrt{ \frac{1}{8\varepsilon} \max\{\|X''(t)\| : t \in I\} } $$ For a quadratic Bezier curve, it's easy to estimate $\max\{\|X''(t)\| : t \in I\}$. Specifically, if the curve has control points $A$, $B$, $C$, then $$ X(t) = A(1-t)^2 + 2Bt(1-t) + Ct^2 = A + (2B-2A)t + (A-2B+C)t^2 $$ and so $$ X''(t) = 2\big\{A - 2B +C\big\} = 2\big\{(C-B) - (B - A)\big\} $$ If coordinates are expressed in pixels, then something like $\varepsilon = \tfrac12$ is reasonable, so the final formula becomes: $$ n = \sqrt{ \frac{1}{2} \, \big\| (C-B) - (B - A) \big\| } $$

Answer 2

So here is the best answer our team found:

We compute the angle between the lines formed by each point in the bezier curve and their control points. If that angle is below a threshold (15 degrees in our case), the control point is annotated and not smoothing is applied. The annotated curve is tessellated as a semi-arc instead of a bezier curve.

If the angle is bigger than the specified threshold, bezier runs as normal. Only, while smoothing the curve, we compute the angle between the normal to the tangents at the last point and current points. If that angle is bigger than another threshold (1.14 degrees), that part of the curve (from the previous point to the current) is further smoothed.

The logic behind the nested bezier, is that if the normal to the tangents vary too much, the curve needs more points to be properly represented.

But if the angle was too narrow, then we would end up with the original problem again (too many points representing that curve) - only reduced since now we know where the curve needs more points and where it does not -. That is where the first threshold comes in. It prevents us from properly presenting the curve and we solve the problem somewhere else.

I say "solve the problem" because in our application these narrow curves should look like rounded joints. They don't need to precisely represent the actual curve.

The thresholds were defined through experimentation and pragmatic reasoning (considering how precise we want to be and how far we want to go as far as trade offs go).