Home

Fast cubic Bézier curve offsetting.

Curve offsetting is a process of finding parallel curves. It is one of the most fundamental operations in vector graphics. Stroking, shrinking or enlarging Bézier paths are just a few use cases.

This is a picture of a curve going from point P1 to P4 with control points P2 and P3. The red curve is a parallel curve.

The problem is that there is no perfect solution for it. Curve offsetting is simply finding a set of curves that appear to be parallel to the original curve within accepted error. However, it turns out, finding this approximation is not an easy task, especially when considering performance, accuracy and limiting the amount of output segments. This is an overview of my attempt to come up with a fast, accurate offsetter which tries to produce as few output segments as practically possible.

Demo & implementation.

A web-based demo is here. In the demo, two offsets are shown. Blue indicates positive offset and red indicates negative offset. Offsetter handles both positive and negative offsets.

C++ and JavaScript implementations are here. Note that the JavaScript version is a direct translation from C++ implementation.

Implementation overview.

The method I present here is using a combination of two approaches to curve offsetting.

The first approach is to find a single parallel curve using one of the established curve offsetting algorithms. Let’s call this simple offsetting. If a candidate fails an error test, the second approach is attempted.

The second approach tries to approximate the original curve with a circular arc first, then the circular arc is scaled before it is converted back to cubic curve representation. I will call this circular arc offsetting throughout the rest of this document.

If both of these methods fail, the curve is split in the middle and the process is continued recursively for both curves.

Simple offsetting.

There are quite a few methods developed for finding a parallel curve of a cubic Bézier. I’ll mention two of them.

Probably the most famous method is Tiller-Hanson described in the paper Offsets of Two-Dimensional Profiles. It works by shifting edges of a polygon enclosing curve points along polygon edge normals. It is intuitive and quite easy to visualize.

Another approach was introduced by Shi-Nine Yang and Ming-Liang Huang in the paper A New Shape Control and Classification for Cubic Bézier Curves.

Using exactly the same method for error testing with the same error tolerance, it quickly becomes clear that the latter method performs much better. The final number of parallel curves calculated for a single input curve using the Tiller-Hanson method is much higher. In the meantime, it takes roughly the same amount of time to find a candidate parallel curve using either of these methods.

This implementation is using the method developed by Yang and Huang with a control point at the middle (t=0.5) of the curve.

Determining if the offset curve is good enough.

Once an attempt is made to find a candidate parallel curve, it is time to test if it is good enough. For this, a few points are selected on the original curve. For each of these points a normal vector is calculated and a ray is cast from the curve point to the direction of the normal vector. Intersection between this ray and shifted curve is found and distance to the intersection is compared with offset amount. If the difference between distance and offset is within maximum allowed error, the curve is accepted as good. In the picture below, points A, B and C are points on the original curve and the arrows are pointing to the direction of normal vectors at these points.

Ray-curve intersections are marked with crosses. Distance from point to intersection must be roughly equal to offset amount or the candidate curve is discarded.

This is not exactly the cheapest way. Finding each intersection involves a search for cubic roots. But this method generates less false negatives than simply using distance between points on both curves at the same t value and does not require any special handling for situations where shifted version of the curve gets flipped.

Circular arc offsetting.

First, what is a circular arc? It is simply a partial circle. Like a circle, it has a center. But unlike a circle, it does not go around its center 360°. There is a start and end. All cubic curves except completely flat ones can be approximated with a set of circular arcs.

I found that for round curve segments, first approximating them with circular arcs and scaling them instead works quite well. Unlike cubic curves, circular arcs can be offset without error. So if we manage to find a circular arc which approximates input curve close enough, it can be used to calculate offset.

Finding a circular arc which approximates a cubic curve.

This is an overview of the process of finding parameters of circular arcs approximating a single cubic curve.

The first step is to find the intersection between the start and end tangents of the curve. Let’s call this intersection V.

Now we have a triangle defined by P1, V and P4 points. The next step is to find the incenter point of this triangle. We will call it G. Point G is the splitting point between two circular arcs approximating a cubic curve. This pair of arcs is called biarc.

Then we will find the center points of these arcs. For the first arc, cast a ray from the first point of the start tangent of the curve to the direction of tangent’s normal vector. Cast another ray from the middle of the line segment (P1 → G) to the direction of this line’s normal. Intersection of these rays will be the center point of the first arc. Do the same with the second arc.

If centers of both arcs are in the same place, we can merge both of them into one circular arc which further reduces output segment count and error testing cost.

An interactive demo is available to see how it all works. You can see that the closer point G gets to the curve, the better approximation becomes.

Testing if arc approximates input curve close enough.

Testing for error is also much cheaper for circular arcs. Instead of trying to intersect a ray being cast from a point on a circle with a curve to see if it is within error margin, we can do the opposite. Select the point on the curve and intersect with the candidate arc. This is way cheaper and more robust.

In this example, a point on the original curve is selected. Then, a line segment (A → B in the image above) is constructed which has the same direction as the normal vector of the curve at that point. Line segment extends to both sides by half of maximum allowed error. If this segment intersects with the candidate arc, it is accepted as good. Much cheaper than finding a ray-curve intersection.

Circular arcs work very well in some practical situations.

Perhaps the most important benefit of using circular arcs is that it detects curves which were intended to approximate circular geometries. This includes circles, rounded corners, round ends of strokes and more. For these situations offsetting becomes very fast and accurate.

Another situation where circular arcs work well is where the offset curve becomes extremely small. If the curve has symmetric or close to symmetric start and end tangents, and intersection of rays cast from P1 and P4 points to the direction of tangents is at distance from P1 and P4 similar to offset amount, candidate curve can become too small to reliably test if it is accepted as good.

Since circular arc approximation is performed for the original curve, not offset candidate, the potential for error is smaller. Even if the scaled version of the circular arc also becomes tiny, this situation has a better chance of being detected simply by testing if the radius of the scaled arc became too tiny to be included in the output.

Converting circular arcs back to curves.

An Improved Algorithm for the Approximation of a Cubic Bézier Curve and its Application for Approximating Quadratic Bézier Curve is an excellent paper by Aleksas Riškus and Giedrius Liutkus about approximating circular arcs with cubic curves. This implementation is using the method described in this paper.

Finding good starting cut positions.

To minimize the amount of output curves, a good starting set of potential cut points should be found. These points are inflection points and maximum curvature points.

All of them are determined for the input curve once at the beginning.

Once the input curve is divided at inflection points, all curves that are created by this division will have their control points on the same side of the line connecting start and end points. Knowing this fact makes further processing simpler.

Dealing with cusps.

Cubic Bézier curves may have an unpleasant feature called cusp. Cusp is a sharp edge somewhere on a curve. Length of the derivative vector at the cusp becomes zero.

Cusps usually need special handling when processing curves. Offsetting is not an exception.

How to correctly handle cusp while offsetting a curve? My solution is to find two points on a curve, on different sides of a cusp which have derivatives of length large enough and draw a circular arc between them, with the arc center being the position of a cusp. These points are found by performing a limited number of search iterations until points closest to the cusp are found.

Dealing with small hooks at the beginning and the end.

Sometimes the curve looks smooth and nice, but when stroked, it suddenly becomes weird in one or both ends. Then, if you take a closer look, the curve has one or both control points placed very close to end points. Even worse, control points may point in the opposite direction from the rest of the curve making a sharp turn very close to the end.

These tiny turns do not usually appear because someone decided to draw a curve like that. Instead it is usually a result of some path processing feature like boolean operation.

It is not an entirely bad idea to get rid of these tiny turns. But how to determine if a curve contains these undesired properties? The cheap solution is to divide the length of (P1 → P2) by the perimeter of the curve polygon. Then compare the ratio with a predefined small number to see if the ratio is smaller. If it is, make P2 equal to P1. Do the same with (P3 → P4).

Choosing the right acceptable error value.

When deciding if an attempt to approximate a parallel curve is good enough, there is some acceptable error value. When offsetting a curve which barely fits into the screen, even high error can be hard to notice, but if the entire input curve fits into one pixel, error should be smaller. It is easy to conclude that this value should not be absolute. It should depend on the size of an input curve.

What is a good way to decide what is the size of the input curve? The simple and cheap solution is to combine lengths of (P1 → P2), (P2 → P3) and (P3 → P4) and use this number for deciding what is the final maximum allowed error.

Process overview.

The first step is to fix hooks at both ends of the input curve.

Make an attempt to use circular arc offsetting on the entire curve in case it approximates circular geometry already.

If that fails, the next step is to find positions of inflection points and maximum curvature points of a curve. Split input curve into smaller curves at these points.

For each resulting curve do the following -

  1. Try offsetting using a simple cubic offsetting method. Test if the result is acceptable. If acceptable, add to the result set and go to the next curve. If not, continue to the next step.
  2. Calculate circular arc parameters of this curve and test if it is good enough. If it is, offset the circular arc and add the result to the result set. If the error is too large, split in half and continue from step 1.

Conclusion.

Risking being not modest I’ll say that considering performance, accuracy and the number of output segments, this implementation of cubic Bézier offsetter is not completely useless. On Apple M1 Max it takes from 0.5 to 3.0 microseconds on average to process one curve with maximum error of 0.01, depending on curve complexity and offset amount. If the curve is already an approximation of circular geometry, processing time is reduced to less than 0.1 microseconds per curve. These numbers are for C++ implementation, compiled using clang compiler and -O3 flag.

The C++ version of the offsetter should also be good enough to be used as-is, without major modifications.

References.

Blog of Aurimas Gasiulis
Twitter Mastodon GitHub E-Mail
Home