If you already have working code for basic NURBS operations or you are a NURBS expert, I would recommend using some NURBS library. Typically, a set of operations related to your problem: point evaluation, insertion of a node, separation, and possibly an increase in degree.
For generality, I will describe three possible solutions.
Divide into nodes
Suppose your NURBS input curves are irrational (without weights = unit weights) and their degree cannot exceed the maximum allowable degree of the resulting Bézier curves. Then each spline span is a polynomial curve, so it can be extracted as a Bezier curve.
Depending on the library used, the description of the algorithm may be different. Here are the options:
- If there is a function to split a NURBS curve into Bezier curves, just name it.
- Suppose that there is a function for splitting a curve into two sub-curves in a given parameter. Then divide your curve into any internal node (i.e. Not equal to min / max nodes). Do the same for each of the pods until there are no internal nodes, which means all Bezier curves.
- Any NURBS library must have a node insert function. For each node Ki with a multiplicity less than D (degree), call the insert node with param = Ki. You can insert different nodes in any order. The library may also contain a "multiple insertion of nodes", which allows you to combine all the inserts into one call. In the end, the minimum / maximum nodes must have a multiplicity of D + 1, all internal nodes must have a multiplicity of D. At this point, the control points completely describe the Bezier curves that you need: the control points [0..D] define the 0th Bezier, [D..2D] determine the 1st Bezier, ..., [q D .. (q + 1) D] control points determine the qth Bezier.
If the degree of your input NURBS curve is lower than the required Bezier curve, you can also cause a degree increase for either the original NURBS curve or the resulting Bezier curves. Speaking of ID2D1GeometrySink, it accepts all Bezier curves with degree <= 3 (a linear Bezier curve is just a line segment), so this is not necessary.
If your NURBS curve can be unacceptably high or rational, then you should approximate the curve either with a cubic spline (harder and faster) or with a polyline (simpler but slower).
Guaranteed polyline approximation
Here is a fairly simple recursive algorithm that builds a polyline approximation of a NURBS curve with a guaranteed error <= MaxErr.
- Draw a line segment from the first to the last control points of the curve.
- Check if all control points are within the distance of MaxErr from the segment.
- If they are, add a line segment to the output.
- Otherwise, divide the curve in the middle into two cigarettes and approximate them recursively.
To implement it, you need a NURBS curve splitting operation (which can be implemented by inserting a node).
Heuristic approximation of a polyline
If there is no NURBS library on hand, embedding a node insert can cause great pain. That is why I am describing another solution that uses only a point estimate of NURBS curves. You can implement point estimation either using the de Bohr algorithm or by definition (see basic functions and NURBS curve )
The algorithm is recursive, it takes a parametric interval on the original curve as an input.
- Estimate the start and end points of the parametric interval.
- Draw a line segment along them.
- Estimate a certain number of points on the curve inside the parametric interval.
- Make sure that these internal points are at a distance of MaxErr from the line segment.
- If they are, add a line segment to the output.
- Otherwise, we divide the parametric interval into two halves and call the approximation on them recursively.
This algorithm is adaptive, and in practice it can give a poor approximation in some rare cases. Control points can be selected evenly within a parametric interval. For greater reliability, it is also better to evaluate the curve at all nodes of the input curve that fall in the parametric interval.
Third party library
If you are not going to work a lot with NURBS, I suggest taking the tinyspline library. It is very small in design, has no dependencies and has a MIT license. In addition, it seems to be actively developing, so you can communicate with the author in case of any problems.
It seems that the first solution is enough for the theme starter, so here is the code for splitting NURBS into Bezier curves with a tin plan:
#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 the minimum and maximum nodes have a multiplicity of D + 1. Sometimes NURBS curves are also used. If you match one, you may also need to pinch it using the library function matching function. The toBeziers method from the tinsiplane, which is used directly above the NURBS clamps automatically, you do not need to clamp it manually.