2
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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\| } $$

$\endgroup$
  • $\begingroup$ Thanks for the answer bubba. Regarding my second image, I used the same colors as the first to try to show what is going on. Clearly that did not work :) So, the black dots are three points in the curve which the normal to the tangents (arrows purple) differ too much. You can see that the tangent of one is equal to the normal of the tangent of the other. I need way more points to generate an smooth transition in that scenario. Otherwise I end up with sharp edges as shown in the figure. $\endgroup$ – Cezar Signori Mar 22 '16 at 13:30
  • $\begingroup$ I need more than one comment to reply you bubba :) So, regarding the number of points, I don't use the same number for all curves. I compute the length of the two lines (as described), sum those and that is my N. So if the sum is 30, then I create 30 points between those 3 original points. The idea is that there is one point per pixel on the curve and not more. And that is already too much. Only those very curves with very sharp edges need way more points than the number of pixels in the curve to result in a smooth curve due to the way the data is tessellated. $\endgroup$ – Cezar Signori Mar 22 '16 at 13:37
  • $\begingroup$ If I understand you correctly, a curve that is "very sharp" will have a large value for $\max \|C''\|$, so my formula will give you a large $n$. $\endgroup$ – bubba Mar 22 '16 at 13:45
  • $\begingroup$ So your suggestion is to compute the N in such a way where each curve will use as many points as required for it to look smooth, even though some very sharp ones will require much more points than the actual number of pixels that need to be painted to represent it? I am trying to avoid that because an approach like that would generate a lot of overdraw (and processing time that doesn't result in any improvement as the same region is being painted over and over again). $\endgroup$ – Cezar Signori Mar 22 '16 at 14:27
  • $\begingroup$ If the scenario I described doesn't happen often enough on actual use cases (rather than me trying to reproduce it) and the amount of points is not absurd when it does, it might work for MVP. Said that I would like to try out your approach. Would you mind to explain how one would estimate max{∥C″(t)∥:t∈I}? I assume you mean to compute the second derivative for a point in the actual curve for a given t and then compute the length of that. But since t is based on N (t = 1/N), I can't go that route. What do you suggest? Thanks again. $\endgroup$ – Cezar Signori Mar 22 '16 at 14:44
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.