Rendering an SVG elliptical arc as bezier curves

I needed to draw ellipses and arcs. A vector API just wouldn’t be complete without them. Though opinions seem to differ as Apple’s Core Graphics lacks anything but an axis aligned circular arc. Android allows for an ellipse, but seems also to restrict it to axis aligned. That means I needed to convert an ellipse to a series of bezier curves for these backing APIs.

See also The smooth sexy curves of a bezier spline and Stuffing curves into boxes: calculating the bounds in this series.

SVG arc notation

SVG’s arc command allows for any type of arc one might want to draw. Since Fuse’s old Path control already allowed SVG path data it seemed logical to use this definition of an arc.

SVG specifies arcs by their end points: where it starts and ends. This is combined with the radius and a rotation of the ellipse. With just these parameters there are four potential arcs that could be drawn. Two at-first-odd-looking flags are included to select which one.

1

a radius-x radius-y x-axis-rotation large-arc-flag sweep-flag x y

This is a great way to specify an arc from the drawing perspective. You know what two points to connect, and you know which sweep angle you want. The problem is that it’s not a good way to actually draw an arc. It needs to be converted to give us a center point and the range of angles to be drawn.

Endpoint to center point conversion

The SVG appendix “Elliptical arc implementation notes” has a “conversion from endpoint to center parametrization” algorithm. This is helpful since the arc notation is a bit uncommon and it’s hard to find this algorithm elsewhere.

It’s got a a few problems however. The example arcs in the standard itself actually fail! Some patching is required.

Square Root

The first problem is the square root in F6.5.2:

Square root fails — produces an imaginary number, which becomes NaN — when given a negative value. This happens whenever the input radius is not large enough to connect the two end points with an ellipse. Even if the source numbers are consistent, floating point precision errors can result in this number being slightly negative. sqrt is unforgiving: sqrt(0) is 0, but sqrt(-0.000001) is NaN.

I patched it as follows. From the spec we separate out \(\sqrt{pq}\) where:

The problem case is when \(pq < 0\). This happens when \(cr > 1\) given the ratio \(cr\) below:

Given this ratio it’s quite easy to scale up the radius. We multiply the radius by the \(\sqrt{cr}\). This reduces the \(cr\) value to exactly \(1\) (floating point precision notwithstanding), resulting in \(pq == 0\).

The full function is at the end of this article. I still do a sqrt(max(0,pq)); due to precision the pq value could still be negative after scaling up r (it actually was in practice, slight negatives appeared).

Arc cosine

The algorithm also involves calculating the angle between two vectors. Though we already have functions to calculate this I decided to use their equation to ensure the ± part worked as intended.

Normally we’d have to worry about the division here, but our prefiltering in this algorithm ensures we have non-zero lengths.

What it doesn’t guarantee is that the operand to arccos will be valid. Due to floating point precision (again) the value might be slightly greater than 1, or slightly less than -1. arccos is of course unforgiving and just returns a NaN in those cases (the correct result would be an imaginary number). In my code I added a clamp to prevent this.

The clamp here is valid since theoretically the equation can’t be producing a value outside the range of -1..1. It’s an angle being measured, which has a fixed range of values. The out-of-range values I was getting were only ever-so-slightly out of range.

From arcs to beziers

We can use this center point notation to convert the arc into a series of bezier curves. This involves many things: a parametric form of the ellipse equation, it’s derivative, and some complex formula that I didn’t derive.

Thankfully L.Maisonobe did all the work in his paper Drawing an elliptical arc using polylines, quadratic or cubic Bézier curves. All I had to do was read it and translate into code.

Parametrics

The first bit is getting parametric equations for an ellipse. The classic definition for the points of an ellipse looks like this:

This tells us if a given x,y point resides on the edge of the ellipse. It’s not very useful for drawing that ellipse. Instead we want to get a parametric form. The below is a function that takes a value t, which respresents a pseudo-angle on the ellipse, and returns the x,y coordinate. This includes a rotation of the ellipse away from the X-axis (required for SVG arcs).

1
2
3
4
5
6

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

The purpose of this equation form is that we can iterate between the starting and ending angles of our arc definition to find the points on the ellipse. There is a second function called EllipticArcDerivative that provides the derivative. These two functions let us calculate a bezier curve that approximates any section of arc. The following table from Maisonobe’s paper is all we need.

Where \(\mathit{E}\) is the EllipticArcPoint function, \(\mathit{E}’\) the EllipticArcDerivative function, \(\eta_1\) and \(\eta_2\) are the start and end angle of the arc we’re approximating.

All I had to do was subdivide the angle range into small sections to get a good approximation. I didn’t quite understand the paper’s error calculations, but I found another paper by Joe Cridge indicating divisions of \(\pi/2\) provides a potential one pixel error on a fairly high resolution device. So I chose \(\pi/4\) to ensure smooth animation, even for partial arcs on high density mobile devices.

An Ellipse

Putting this all together we’re able to render the examples from SVG. This builds on the vector API I started with my previous article on The smooth sexy curves of a bezier spline. My working backend is Apple’s Core Graphics, but this code will also run with Android Canvas, and Windows System.Drawing. By calculating the bezier curves ourselves we don’t need to limit ourselves to the backend arc drawing abilities.

There is one more article in this series to come. We still need to calculate the bounds of these shapes. Another adventure in derivatives.

Appendix: Endpoint to center arc conversion

This is the Uno code (as of article publishing time) used to convert from SVG arcs to center point notation.

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

/**
    Perform the endpoint to center arc parameter conversion as detailed in the SVG 1.1 spec.
    F.6.5 Conversion from endpoint to center parameterization

    @param r must be a ref in case it needs to be scaled up, as per the SVG spec
*/
internal static void EndpointToCenterArcParams( float2 p1, float2 p2, ref float2 r_, float xAngle, 
    bool flagA, bool flagS, out float2 c, out float2 angles )
{
    double rX = Math.Abs(r_.X);
    double rY = Math.Abs(r_.Y);

    //(F.6.5.1)
    double dx2 = (p1.X - p2.X) / 2.0;
    double dy2 = (p1.Y - p2.Y) / 2.0;
    double x1p = Math.Cos(xAngle)*dx2 + Math.Sin(xAngle)*dy2;
    double y1p = -Math.Sin(xAngle)*dx2 + Math.Cos(xAngle)*dy2;

    //(F.6.5.2)
    double rxs = rX * rX;
    double rys = rY * rY;
    double x1ps = x1p * x1p;
    double y1ps = y1p * y1p;
    // check if the radius is too small `pq < 0`, when `dq > rxs * rys` (see below)
    // cr is the ratio (dq : rxs * rys) 
    double cr = x1ps/rxs + y1ps/rys;
    if (cr > 1) {
        //scale up rX,rY equally so cr == 1
        var s = Math.Sqrt(cr);
        rX = s * rX;
        rY = s * rY;
        rxs = rX * rX;
        rys = rY * rY;
    }
    double dq = (rxs * y1ps + rys * x1ps);
    double pq = (rxs*rys - dq) / dq;
    double q = Math.Sqrt( Math.Max(0,pq) ); //use Max to account for float precision
    if (flagA == flagS)
        q = -q;
    double cxp = q * rX * y1p / rY;
    double cyp = - q * rY * x1p / rX;

    //(F.6.5.3)
    double cx = Math.Cos(xAngle)*cxp - Math.Sin(xAngle)*cyp + (p1.X + p2.X)/2;
    double cy = Math.Sin(xAngle)*cxp + Math.Cos(xAngle)*cyp + (p1.Y + p2.Y)/2;

    //(F.6.5.5)
    double theta = svgAngle( 1,0, (x1p-cxp) / rX, (y1p - cyp)/rY );
    //(F.6.5.6)
    double delta = svgAngle(
        (x1p - cxp)/rX, (y1p - cyp)/rY,
        (-x1p - cxp)/rX, (-y1p-cyp)/rY);
    delta = Math.Mod(delta, Math.PIf * 2 );
    if (!flagS)
        delta -= 2 * Math.PIf;

    r_ = float2((float)rX,(float)rY);
    c = float2((float)cx,(float)cy);
    angles = float2((float)theta, (float)delta);
}

static float svgAngle( double ux, double uy, double vx, double vy )
{
    var u = float2((float)ux, (float)uy);
    var v = float2((float)vx, (float)vy);
    //(F.6.5.4)
    var dot = Vector.Dot(u,v);
    var len = Vector.Length(u) * Vector.Length(v);
    var ang = Math.Acos( Math.Clamp(dot / len,-1,1) ); //floating point precision, slightly over values appear
    if ( (u.X*v.Y - u.Y*v.X) < 0)
        ang = -ang;
    return ang;
}