Draw splines by using Direct2D

Question

I have the data of a spline curve

• Degree
• Knots
• Control points
• Fit points

And I need to draw this curve by using Direct2D. At the moment I am using the ID2D1GeometrySink interface to draw geometries but it seems it does not implements a possible AddSpline method.

Is there a way to draw spline by means of Direct2D? Even a DirectX implementation that can be used in a Direct2D application will be fine.

Manizales

You need to convert the spline to Beziers so you can use ID2D1GeometrySink::AddBezier(). You do that with the Bohm algorithm. Lots and lots of Google hits, it isn't very clear what you need. At least make up your mind whether you use C or C++. – Erek

@HansPassant It doesn't matter whether it is C or C++, once I have a working algorithm I will be able to adapt it to my project. Actually, I didn't find all these hints about a clear implementation of this algorithm for any of the two languages. Please show me where you found this code. – Manizales

Indeed, you have to convert NURBS to bezier or lines. Can degree be greater than cubic (3)? Can you use free libraries or you want pure C/C++ code? Do you expect conversion to be performance-critical? Is sufficiently precise approximate conversion ok or you need exactly the same curve? – Kindliness

@Kindliness Degree cannot be greater than 3. I can use free libraries. Performance is not a critical factor. The curve can be approximated, but not too much. – Manizales

One more important question: can input NURBS curve be rational? I.e. can it have weights (non-unit)? If yes, then approximation seems inevitable... – Kindliness

@Kindliness Even if approximated I can only judge this approximation only after I will be able to performe this conversion. – Manizales

Answer 1

Unless you already have working code for basic NURBS operations or you are a NURBS expert, I would advise to use some NURBS library. Generally, the set of operations related to your problem are: point evaluation, knot insertion, splitting, and perhaps degree elevation.

For generality, I'll describe three possible solutions.

Split by knots

Suppose that your input NURBS curves are nonrational (no weights = unit weights), and their degree cannot exceed maximal allowed degree of resulting Bezier curves. Then each span of the spline is a polynomial curve, so it can be extracted as Bezier curve.

Depending on the library you use, the description of the algorithm can be different. Here are possible variants:

1. If there is a function to split a NURBS curve into Bezier curves, simply call it.
2. Suppose that there is a function for splitting a curve into two subcurves at given parameter. Then split your curve in any internal knot (i.e. not equal to min/max knots). Do the same for each of the subcurves until there are no internal knots, which means all the curves are Bezier.
3. Any NURBS library must have knot insertion function. For each knot Ki with multiplicity less than D (degree), call knot insertion with param = Ki. You can insert different knots in any order. The library can also contain "multiple knot insertion", which allows to combine all the insertions into one call. At the end, min/max knots must have multiplicity D+1, all the internal knots must have multiplicity D. At this moment the control points fully describe the Bezier curves you need: control points [0..D] define the 0-th Bezier, [D..2D] define the 1-th Bezier, ..., [q D .. (q+1) D] control points define the q-th Bezier.

If the degree of your input NURBS curve is lower that the required degree of Bezier curves, you can also call degree elevation either for the original NURBS curve, or for the resulting Bezier curves. Speaking of ID2D1GeometrySink, it accepts all Bezier curves with degree <= 3 (linear Bezier curve is simply a line segment), so it is not necessary.

If your NURBS curve may have unacceptably high degree, or may be rational, then you have to approximate the curve with either cubic spline (harder and faster) or with polyline (simpler but slower).

Guaranteed polyline approximation

Here is a rather simple recursive algorithm that builds polyline approximation of a NURBS curve with guaranteed error <= MaxErr.

1. Draw a line segment from the first to the last control points of the curve.
2. Check if all the control points are within MaxErr distance from the segment.
3. If they are, then add the line segment to the output.
4. Otherwise, split the curve at the middle into two subcurves, and approximate them recursively.

To implement it, you need NURBS curve splitting operation (which can be implemented via knot insertion).

Heuristic polyline approximation

If there is no NURBS library at hand, implementing knot insertion may cause a lot of pain. That's why I describe one more solution which uses only point evaluation of NURBS curves. You can implement point evaluation either via de Boor algorithm, or by definition (see basis functions and NURBS curve definitions)

The algorithm is recursive, it accepts a parametric interval on the original curve as input.

1. Evaluate the start and the end points of the parametric interval.
2. Draw a line segment through them.
3. Evaluate some number of points on the curve inside the parametric interval.
4. Check that these internal points are within MaxErr distance of the line segment.
5. If they are, then add the line segment to the output.
6. Otherwise, split the parametric interval into two halves, and call approximation on them recursively.

This algorithm is adaptive, and it can produce bad approximation in practice in some rare cases. The check points can be chosen uniformly within the parametric interval. For more reliability, it's better to also evaluate the curve at all the knots of the input curve which fall within the parametric interval.

Third-party library

If you are not going to work with NURBS a lot, I suggest taking the tinyspline library. It is very small by design, has no dependencies, and has MIT license. Also, it seems to be actively developed, so you can communicate to the author in case of any issues.

It seems that the first solution is enough for the topic starter, so here is the code for splitting NURBS into Bezier curves with tinyspline:

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <math.h>
#include "tinysplinecpp.h"
#include "debugging.h"

int main() {
    //create B-spline curve and set its data
    TsBSpline nurbs(3, 2, 10, TS_NONE);
    float knotsData[] = {0.0f, 0.0f, 0.0f, 0.0f, 0.3f, 0.3f, 0.5f, 0.7f, 0.7f, 0.7f, 1.0f, 1.0f, 1.0f, 1.0f};
    for (int i = 0; i < nurbs.nKnots(); i++)
        nurbs.knots()[i] = knotsData[i];
    for (int i = 0; i < nurbs.nCtrlp(); i++) {
        nurbs.ctrlp()[2*i+0] = 0.0f + i;
        float x = 1.0f - i / float(nurbs.nCtrlp());
        nurbs.ctrlp()[2*i+1] = x * x * x;
    }
    ts_bspline_print(nurbs.data());

    //insert knots into B-spline so that it becomes a sequence of bezier curves
    TsBSpline beziers = nurbs;
    beziers.toBeziers();
    ts_bspline_print(beziers.data());

    //check that the library does not fail us
    for (int i = 0; i < 10000; i++) {
        float t = float(rand()) / RAND_MAX;
        float *pRes1 = nurbs(t).result();
        float *pRes2 = beziers(t).result();
        float diff = hypotf(pRes1[0] - pRes2[0], pRes1[1] - pRes2[1]);
        if (diff >= 1e-6f)
            printf("Bad eval at %f: err = %f  (%f;%f) vs (%f;%f)\n", t, diff, pRes1[0], pRes1[1], pRes2[0], pRes2[1]);
    }

    //extract bezier curves
    assert(beziers.nCtrlp() % nurbs.order() == 0);
    int n = beziers.nCtrlp() / nurbs.order();
    int sz = nurbs.order() * 2; //floats per bezier
    for (int i = 0; i < n; i++) {
        float *begin = beziers.ctrlp() + sz * i;
        float *end = beziers.ctrlp() + sz * (i + 1);
        //[begin..end) contains control points of i-th bezier curve
    }

    return 0;
}

Final note

Most of the text above assumes that your NURBS curves are clamped, which means that min and max knots have multiplicity D+1. Unclamped NURBS curves are also used sometimes. If you meet one, you may also need to clamp it by using approproate function of the library. Method toBeziers from tinyspline used just above clamps NURBS automatically, you don't need to clamp it manually.

Kindliness

The library work but it seems that I have a problem with the approximation. Please see theese images original and outcome. Is there a way to decrease the level of approximation? – Manizales

Moreover sometimes happens that nurbs->nCtrlp() % nurbs->order() != 0, or that I get a TS_MULTIPLICITY exception, how should I handle these cases? – Manizales

@Nick, I think we should better speak about the issues in chat. – Kindliness

Answer 2

Direct2D, more clear ID2D1GeometrySink, doesn't support splines, but cubic bezier curves which can be put together to a spline. In the opposite, you can gain b-curves out of your spline data and just add them to your geometry.

The algorithm is simply explained by this picture: .

An article for short and well explanation can be found here. You can split your spline until control points overlap and the degree can be lowered, even until all curves are flat enough to be lines. Last thing isn't a bad idea because your hardware doesn't know curves, so your passed curves get converted to lines later anyway. When you do this conversion, you can determine the tolerance for flatness and avoid ugly edges.

Margueritamarguerite

Please, can you explain the algorithm shown in the picture? – Manizales

Let's say you want to split the curve in halves, then t=0.5. Now you interpolate between the curve points [1,2,3,4] by t to get points on vectors between them [12,23,34]. You repeat this until just one point [1234] remains. The first curve you get by taking every first point in every pass, so [1,12,123,1234], the second curve by taking the last point in every pass in reverse order [1234,234,34,4]. This can be done with curves of any degree. – Margueritamarguerite

This curve splitting can be repeated until all curves are flat and be converted to lines by just using their first & last point. A curve is flat, when the angle between vectors of all points is below a tolerance value, like f.e. 2°. A curve with all control points very near the line between first and last point is flat enough to be called a line. – Margueritamarguerite

@Manizales be sure to check out the wonderful animations that someone put up on Wikipedia: en.wikipedia.org/wiki/… – Brogle

Answer 3

I used this sample code for transforming a cardinal spline to a list of cubic bezier patches: http://www.codeproject.com/Articles/31859/Draw-a-Smooth-Curve-through-a-Set-of-D-Points-wit

It's written for WPF, but since WPF and Direct2D differ only in their programming model (declarative vs. imperative), it translates very easily to Direct2D.

Brogle