Рисование сплайнов с помощью Direct2D

Если у вас уже нет рабочего кода для основных операций NURBS или вы не являетесь экспертом NURBS, я бы посоветовал использовать библиотеку NURBS. Как правило, набор операций, связанных с вашей проблемой: балльная оценка, вставка узла, расщепление, и, возможно повышение степени.

Для общности опишу три возможных решения.

Разделить на узлы

Предположим, что ваши входные NURBS-кривые являются нерациональными (без весов = удельные веса), и их степень не может превышать максимально допустимую степень результирующих кривых Безье. Тогда каждый промежуток сплайна является полиномиальной кривой, поэтому его можно извлечь как кривую Безье.

В зависимости от используемой вами библиотеки описание алгоритма может быть различным. Вот возможные варианты:

1. Если есть функция для разбиения кривой NURBS на кривые Безье, просто вызовите ее.
2. Предположим, что существует функция для разбиения кривой на две подкатушки при заданном параметре. Затем разбейте свою кривую на любой внутренний узел (т. Е. Не равный минимальным / максимальным узлам). Сделайте то же самое для каждой из подкаталогов, пока не будет внутренних узлов, что означает, что все кривые Безье.
3. Любая библиотека NURBS должна иметь функцию вставки узла. Для каждого узла Ki с кратностью, меньшей D (градуса), вызовите вставку узла с параметром = Ki. Вы можете вставить разные узлы в любом порядке. Библиотека также может содержать «вставку нескольких узлов», что позволяет объединить все вставки в один вызов. В конце, узлы min / max должны иметь кратность D + 1, все внутренние узлы должны иметь кратность D. В этот момент контрольные точки полностью описывают необходимые вам кривые Безье: контрольные точки [0..D] определяют 0- th Безье, [D..2D] определяют 1-й Безье, …, [q D .. (q + 1) D] контрольные точки определяют q-й Безье.

Если степень входной кривой NURBS ниже требуемой степени кривых Безье, вы также можете вызвать повышение степени либо для исходной кривой NURBS, либо для результирующих кривых Безье. Говоря о ID2D1GeometrySink, он принимает все кривые Безье со степенью <= 3 (линейная кривая Безье — это просто отрезок), поэтому в этом нет необходимости.

Если ваша кривая NURBS может иметь неприемлемо высокую степень или может быть рациональной, то вы должны аппроксимировать кривую либо кубическим сплайном (сложнее и быстрее), либо ломаной (проще, но медленнее).

Гарантированное приближение полилинии

Вот довольно простой рекурсивный алгоритм, который строит полилинейную аппроксимацию кривой NURBS с гарантированной ошибкой <= MaxErr.

1. Нарисуйте отрезок линии от первой до последней контрольной точки кривой.
2. Проверьте, все ли контрольные точки находятся на расстоянии MaxErr от сегмента.
3. Если они есть, то добавьте отрезок к выводу.
4. В противном случае разбейте кривую посередине на две подкатушки и рекурсивно аппроксимируйте их.

Для его реализации вам понадобится операция расщепления кривой NURBS (которая может быть реализована с помощью вставки узла).

Эвристическая полилиния

Если под рукой нет библиотеки NURBS, реализация вставки узла может причинить много боли. Вот почему я описываю еще одно решение, которое использует только точечную оценку кривых NURBS. Вы можете реализовать оценку точек либо по алгоритму де Бур, либо по определению (см. базисные функции а также Кривая NURBS определения)

Алгоритм является рекурсивным, он принимает параметрический интервал на исходной кривой в качестве входных данных.

1. Оцените начальную и конечную точки параметрического интервала.
2. Нарисуйте отрезок линии через них.
3. Оцените некоторое количество точек на кривой внутри параметрического интервала.
4. Убедитесь, что эти внутренние точки находятся на расстоянии MaxErr от отрезка.
5. Если они есть, то добавьте отрезок к выводу.
6. В противном случае разбейте параметрический интервал на две половины и вызовите аппроксимацию по ним рекурсивно.

Этот алгоритм является адаптивным, и в некоторых редких случаях он может привести к плохому приближению на практике. Контрольные точки могут быть выбраны равномерно в параметрическом интервале. Для большей надежности лучше также оценить кривую на всех узлах входной кривой, которые попадают в параметрический интервал.

Сторонняя библиотека

Если вы не собираетесь много работать с NURBS, я предлагаю взять tinyspline библиотека. Он очень маленький по дизайну, не имеет никаких зависимостей и имеет лицензию MIT. Также он, похоже, активно развивается, поэтому вы можете общаться с автором в случае каких-либо проблем.

Кажется, что первого решения достаточно для инициатора темы, поэтому вот код для разбиения NURBS на кривые Безье с помощью 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;
}

Конечная нота

Большая часть текста выше предполагает, что ваши кривые NURBS зажимают, это означает, что минимальные и максимальные узлы имеют кратность D + 1. Незакрепленные кривые NURBS также иногда используются. Если вы встретите один из них, вам также может понадобиться закрепить его, используя подходящую функцию библиотеки. Метод toBeziers от tinyspline, используемый чуть выше зажимов NURBS автоматически, вам не нужно зажимать его вручную.