For one of the preprocessing steps of a GPU renderer for Scalable Vector Graphics, I am dealing with SVG curves (of the four types: lines, quadratic and cubic Bézier curves, and ellipse arcs). One of the steps is curve subdivision on intersections, as a prestep algorithm to populate a doubly-connected edge list.
Previously, I went to store each type of curve in a separate struct (Line, QuadraticBezier, CubicBezier and EllipticArc), which means that, to operate on them, I needed to write the same (similar) code to each of those combinations (leading to a whopping 10-ication of the code). Now, I want to try something different. I have two options: using an interface ICurve, or use a struct Curve that has a Type and reunite all the operations.
The code that operates on the curve looks (bar the duplication) like this:
// Reunite all the shapes
var curves = new List<ICurve>(path.PathCommands.Length);
foreach (var cmd in path.PathCommands)
/* generate the curves by evaluating the path commands */;
// Reunite all intersections to subdivide the curves
var curveRootSets = new SortedSet<float>[curves.Count];
for (int i = 0; i < curveRootSets.Length; i++)
curveRootSets[i] = new SortedSet<float>(new[] { 1f }, Half.Comparer);
// Get all intersections
for (int i = 0; i < curves.Count; i++)
for (int j = i+1; i < curves.Count; j++)
foreach (var pair in CurveIntersectionPairs(curves[i], curves[j]))
{
curveRootSets[i].Add(pair.A);
curveRootSets[j].Add(pair.B);
}
// Account for possibly-duplicate curves
foreach (var set in curveRootSets) set.Remove(0f);
// Subdivide the curves
var curvesSubdiv = curves.Zip(curveRootSets, delegate (ICurve curve, SortedSet<float> set)
{
float v = 0f;
var list = new List<ICurve>();
foreach (var l in set)
{
list.Add(curve.Subcurve(v, l));
v = l;
}
return list;
}).Aggregate(Enumerable.Empty<ICurve>(), Enumerable.Concat);
The first approach I have come to is to define an interface ICurve with the necessary contract to allow it to work both on the subdivision phase and on the DCEL phase. The interface looks like this:
public interface ICurve
{
// Evaluates the curve at parameter "t"
Vector2 At(float t);
// The derivative of the curve (aka the "velocity curve")
ICurve Derivative { get; }
// Gets the curve that maps [0,1] to [l,r] on this curve
ICurve Subcurve(float l, float r);
// The bounding box of the curve
FRectangle BoundingBox { get; }
// The measure of how much counterclockwise the curve is
// (aka double the area swept by it and the segments that
// connect the endpoints to the origin)
float Winding { get; }
// Does the curve degenerate to a single point?
bool IsDegenerate { get; }
}
And then I would have each struct to implement the interface:
public struct Line : ICurve { /* ... */ }
public struct QuadraticBezier : ICurve { /* ... */ }
public struct CubicBezier : ICurve { /* ... */ }
public struct EllipticArc : ICurve { /* ... */ }
This works wonders, and each of the classes correctly implements the contract methods, and thus I can work with ICurves abstractly, and even implement more curves as the SVG specification asks for them. But I have read some horror stories about boxing/unboxing of interfaces (since they are reference types) and the structs allocated on the heap, which would be scattered on the memory. I guess I could get better (on cache coherency, indirection and other means) by setting up a struct Curve with a public readonly CurveType Type and all the necessary fields for it:
public enum CurveType { Line, QuadraticBezier, CubicBezier, EllipticArc }
public partial struct Curve
{
// four Vector2's are sufficient for now
readonly Vector2 A, B, C, D;
public readonly CurveType Type;
// Evaluates the curve at parameter "t"
public Vector2 At(float t)
{
// "Dispatch" the function based on the type
switch (Type)
{
case CurveType.Line: return LineAt(t);
case CurveType.QuadraticBezier: return QuadraticBezierAt(t);
case CurveType.CubicBezier: return CubicBezierAt(t);
case CurveType.EllipticArc: return EllipticArcAt(t);
default: return new Vector2(float.NaN, float.NaN);
}
}
// Other contract methods implemented similarly ...
}
Since structs are value types, I can allocate them locally using List<Curve> (which uses an array internally) and benefit (at least a little) from cache locality. However, I would lose the ability of "open inheritance" (I think that is a non-issue, because there is only a handful of curves in use on today's SVG).
But maybe I am overengineering it? I am a newcomer to C# (been to C++ for some years), and I do not know the intricacies an interface would bring to value types, and maybe a dynamic dispatch provided by an interface would be faster than a "manual dispatch". Because of this, I would like to ask for your knowledge on those specific approaches. Maybe there is another, better alternative I am not aware?
Bear in mind I am preparing this to work on real-world SVG files, which means potentially tens or hundreds of curves per path, and having to subdivide them afterwards. I could reuse those constructions when I come to generate the primitives encompassing each curve, assign fills and other nuances of the SVG.
