Stuffing curves into boxes: calculating the bounds

Now that we’ve drawn beziers and arcs there’s only one piece missing in the vector API. We need to calculate the bounds of the curve: the minimum/maximum points where it will draw. This is required both to setup the drawing canvas and to dynamically size paths to fit inside elements.

See also The smooth sexy curves of a bezier spline and Rendering an SVG elliptical arc as bezier curves in this series.

Why?

I should first answer why we need the bounds of the curve. There are two primary reasons: one relating to the backend drawing, and the other to layout sizing.

The backend vector engines expect us to tell it how big the drawing canvas is. There’s no option to draw to an infinite canvas and find the bounds of it. If we were to simply create a canvas the same size as the UI element, we’d often have curves that clip on the edges. Generally it is far more desirable to have curves that go over the bounds than to be clipped. (Clipping is of course, also available as an option.)

For layout, we want to treat paths like images. They have a natural size, but can be resized to fit within an element. A variety of stretching modes are provided for this, all of which require knowing the “natural size” of the path.

Structure of a curve

We’re interested in measuring the bounds of an entire curve. In the Fuse vector API these are represented with a series of segments. Each segment represents one of four things:

• move the cursor
• draw a straight line
• draw a bezier curve
• draw an elliptic arc

Measuring the bounds of the entire curve involves iterating over all these segments, calculating the bounds of each one, and combining the results.

The “move” segment has no bounds, and the line segment is trivial. There are a few lines of code involved, so the unit tests should still cover them. Never skip the testing of trivial things!

Bezier curve

From the previous articles it should be clear that drawing curves involves derivatives. Measuring curves is no different. Finding the min/max of an equation requires calculating where the derivative equals zero. This isn’t technically the min/max of the equation, it’s where the equation has a flat slope. On a bezier curve, since it’s cubic, it will have two such points. We’re finding those two locations.

Calculating the derivative of the bezier equation isn’t difficult, but you can also look it up online. It’s been done a million times already. It is:

1

F'(t) = 3(-(p0-3p1-p3+3p2)*t^2  + 2(p0-2p1+p2)t - p0 + p1)

Where p0 and p3 are the end points, and p1 and p2 are the control points. We are only interested in the roots (where F'(t) == 0) so we can drop the 3 multiplier. We’ll then also rewrite this as F'(t) = a*t^2 + b*t + c where the parts are:

1
2
3

var b = 2 * p0 - 4 * p1 + 2 * p2;
var a = -p0 + 3 * p1 - 3 * p2 + p3;
var c = p1 - p0;

The zero points are thus at t = (-b ± sqrt( b^2 - 4ac)) / 2a.

If a is zero we don’t have a solution. The argument to sqrt might also be negative. Not all curves actually have a zero slope at some point. There is also a case where the min/max are inside the end point bounds, -c/b I think. In any case, since we really want the segment bounds, not the actual min/max, we can just use the endpoints.

If we have a proper solution for t we check if they are in the range of 0..1. Those are the only parts of this bezier we are actually drawing. In practice, and I’ll show the code at the end, we simply clamp the values to this range. This correctly indicates t=0 or t=1 is the min/max value for our curve segment.

We pass these values of t to our bezier equation and get the segment bounds.

Elliptic arc

This process is basically the same as for the bezier curve: calculate the derivative, find the min/max, check if within range. First we must convert the endpoint notation to center point notation. From that article as well you’ll see we already have the derivative of the arc, as it was needed to convert to beziers.

1
2
3
4
5
6

static public float2 EllipticArcDerivative( float2 c, float2 r, float xAngle, float t ) 
{
    return float2(
        -r.X * Math.Cos(xAngle) * Math.Sin(t) - r.Y * Math.Sin(xAngle) * Math.Cos(t),
        -r.X * Math.Sin(xAngle) * Math.Sin(t) + r.Y * Math.Cos(xAngle) * Math.Cos(t) );
}

Unlike the bezier curve, the value for X is slightly different from Y this time. We need a different calculation for each value. It’s good to remember the trigonometric identity tan(t) = sin(t)/cos(t) here. When I put the equation in Maxima, it didn’t want to use that identity, and thus couldn’t find a solution. I had to resort to doing math by hand! gasp

In any case, the simplified X solution is tan(t) = - r.Y * sin(xAngle) / (r.X * cos(xAngle)) and for Y is tan(t) = r.Y * cos(xAngle) / (r.X * sin(xAngle)). t is just an arctan calculation away now. Since we have a division, we call the atan2 function. This correctly handles the case where the denominator nears, or reaches, 0.

An ellipse has 4 min/max values however, not just 2. tan is a cyclic function, it produces the same results at multiples of π offsets. arctan returns only one of those, but we can simply add π to each to get the other two values.

If you aren’t convinved of this, and I wouldn’t be, you can calculate those other results without just adding π. atan2 actually gives a very specific result depending on the sign of the two values. It’s designed to give a result corresponding to the cartesian quadrant of the input values. If you instead pass in the negative radius, selecting a different quadrant, you will get the π offset outputs.

We’re drawing partial arcs, so we need to check if these t values are in the range we are drawing. If you have a suitable AngleInRange function this is easy enough. For each t value in range we add the ellipse point to the bounds.

It’s possible that only one, or none, of the boundary points on the full ellipse are in our segment. The form of the ellipse then dictates the actual endpoints of our segment are the extents. I just always add both endpoints to the extents for simplicity.

I didn’t really prove this last bit, instead using several diagrams and intuition. If somebody has an actual proof that would be nice. And certainly if I’m wrong I definitely want to know.

Stroke width

The above only gives us the point boundaries of the curve. It doesn’t take into account the thickness, or shape, of a stroke used to draw them. I mentioned before the backend vector engines expect us to tell them how much space is required, so we must include the space for the stroke.

It’s quite problematic to calculate the precise drawing bounds of the stroke. It depends on the angles and stlye of each joint and end cap. Instead I’ve used an upper bounds value, the maximum of a square end cap and a miter joint.

The square cap extends the width in the direction of the line, as well as the perpendicular. In worse case this means sqrt( 2 * width ^ 2 ) or sqrt(2) * width in all directions. This is slightly more than a round joint/cap which simply extends width in all directions.

An unlimited miter joint can actually extend off to infinity, but nobody ever wants that. There’s a limit at which point a bevel is used instead. We simply use this as the limit.

This isn’t quite right however, as the angle of the joint can still push parts of the stroke beyond this, especially if the miter limit is less than the stroke width. This is probably covered by the square cap calculation, since we take the maximum, but I will have to revisit this at some point and solve it with a bit more precision.

Testing

There are a lot of equations here. That means plenty of potential to make mistakes during derivation, or while coverting to code. Testing is an absolute necessity. Unfortunately I couldn’t find any readily available sources of inputs and expected values. I resorted to two other approaches to verify.

The first is a brute force calculation. We can also find the bounds of a curve by calculating the location at every point on that curve. For each bezier I used a delta of 1/10000 to step through the segment. I could do the same for ellipses, but it was quicker to use the conversion to bezier code and just reuse the bezier stepping. I then compared these results against the formulas above. If they were close enough I’d assume the calculation was correct. This was done for a variety of curve types, including some with known oddities, to get good coverage.

By close enough I mean within a few bits of floating point precision. The ellipses were a bit more off simply because I didn’t step through a true ellipse, but through the bezier approximation.

The second approach was visual confirmation. The extents are both used to fit a path to an element, and to ensure the strokes aren’t clipped. By animating through a variety of curves we can have visual confirmation of correctness.

These two approaches combined give me confidence the calculations are good.

Moving on

This concludes the set of articles about creating the vector API for Fuse. I’ve covered how beziers work, how to draw arcs, and how to measure the curves. There are several other components involved, but these were the three most interesting aspects.

This isn’t the end of the story of curves however. Eventually I’ll come back and cover how to move at a constant speed along a curve, useful for animation, and how to split a bezier into parts, also useful for animation. But that’ll have to wait until later.

Appendix: Code Samples

This are just some high-level functions of interest, to help show how the logic works. They call several functions which I won’t show here.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

static float2 BezierMinMax(float p0, float p1, float p2, float p3 )
{
    //the derivative of he bezier curve is:
    //F'(t) = 3(-(p0-3p1-p3+3p2)*t^2  + 2(p0-2p1+p2)t - p0 + p1)
    //we only care about the zeros, so drop the 3, and replace with simple bits
    //F'(t) = a*t^2 + b*t + c
    var b = 2 * p0 - 4 * p1 + 2 * p2;
    var a = -p0 + 3 * p1 - 3 * p2 + p3;
    var c = p1 - p0;
    //zero points are
    // t = (-b ± sqrt( b^2 - 4ac)) / 2a

    //float precision stuff
    if (Math.Abs(a) < float.ZeroTolerance)
    {
        //technically if -c/b is within 0<t
        //the bounding box of the endpoints so we don't need to identify that
        return float2(0,1);
    }

    var sqr = b *b - 4 * a * c;
    if (sqr < 0)
        return float2(0,1);

    var rt = Math.Sqrt(sqr);

    var t1 = (-b + rt) / (2 * a);
    var t2 = (-b - rt) / (2 * a);
    return float2(
        Math.Clamp(t1, 0, 1),
        Math.Clamp(t2, 0, 1) );
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

void EllipticBounds(float2 from, LineSegment seg)
{
    if (SurfaceUtil.EllipticArcOutOfRange(from,seg))
    {
        AddPoint(from);
        AddPoint(seg.To);
        return;
    }

    float2 c, angles;
    var radius = seg.A;
    var xAngle = seg.B.X;
    SurfaceUtil.EndpointToCenterArcParams( from, seg.To, ref radius, xAngle,
        seg.Flags.HasFlag(LineSegmentFlags.EllipticArcLarge), 
        seg.Flags.HasFlag(LineSegmentFlags.EllipticArcSweep),
        out c, out angles );

    var ts = float4(0);
    // solve the derivative of E(t).X == 0
    // tan(t) = - r.Y * sin(xAngle) / (r.X * cos(xAngle))
    ts[0] = Math.Atan2( -radius.Y * Math.Sin(xAngle), radius.X * Math.Cos(xAngle));
    ts[1] = ts[0] + Math.PIf;

    // for E(t).Y = 0
    // tan(t) = r.Y * cos(xAngle) / (r.X * sin(xAngle))
    ts[2] = Math.Atan2( radius.Y * Math.Cos(xAngle), radius.X * Math.Sin(xAngle) );
    ts[3] = ts[2] + Math.PIf;

    //add any of those extents if they are in the angle range
    for (int i=0; i < 4; ++i)
    {
        var t = ts[i];//i * Math.PIf/2;
        if (SurfaceUtil.AngleInRange(t, angles[0], angles[0] + angles[1]))
            AddPoint( SurfaceUtil.EllipticArcPoint( c, radius, xAngle, t ));
    }

    //add both angle end points
    AddPoint( SurfaceUtil.EllipticArcPoint( c, radius, xAngle, angles[0] ) );
    AddPoint( SurfaceUtil.EllipticArcPoint( c, radius, xAngle, angles[0] + angles[1] ) );
}