Циркулярные кривые 2-го порядка

Как известно ^[1], кривыми Безье нельзя построить дугу окружности или эллипса. В этой статье рассматриваются кривые, лишённые такого недостатка.

Кривые Безье

Логика построения кривых Безье хорошо понятна из следующей анимации:

Чтобы получить формулу непосредственно из графического представления, достаточно определить вспомогательную функцию для линейной интерполяции между двумя точками, в которая при изменении параметра t от 0 до 1 возвращает промежуточные значения от a до b:

С её помощью можно последовательно найти необходимые точки — сначала найти

и

а затем уже через них найти

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

Увеличение порядка кривых достигается тривиально — исходные точки задаются не константно, а как результат интерполяции между n+1 других контрольных точек:

Циркулярные кривые

Дуга окружности

Чтобы похожим образом построить дугу окружности, необходимо определить соответствующую логику построения — по аналогии с черчением окружности циркулем.

Изначально нам неизвестен центр окружности d — он находится через пересечение перпендикуляров к касательным в точках a и b (далее узловых); сами же касательные задаются с помощью точки c (далее направляющей). Для построения произвольной дуги окружности (меньшей 180°) достаточно, чтобы расстояния от направляющей точки до узловых были одинаковыми.

Дуга эллипса

Построить дугу эллипса уже посложнее — потребуется два вектора, вращающихся в разные стороны (подробнее здесь ^[2])

Используя озвученный выше способ нахождения точки d, мы уже не можем построить произвольную дугу эллипса — только лишь от 0° до 90° (в том числе и повёрнутую на некоторый угол).

Дуга гипотрохоиды

Задав условие, что в начале и конце черчения векторы должны лежать на одной прямой, мы получим дугу гипотрохоиды ^[3] во всех остальных случаях. Это условие не случайно и (помимо однозначного определения кривой) гарантирует совпадение касательных в узловых точках. Как следствие, угловые пути, которые проходят оба вектора, станут разными, но в сумме по-прежнему будут давать 180°.

Как изменяется форма кривой в зависимости от положения направляющей точки, можно посмотреть на следующей анимации:

Алгоритм

Поскольку здесь мы имеем вращения на двумерной плоскости, математику построения этих кривых удобно описывать через комплексные числа.

1) находим точку пересечения нормалей касательных, проведённых от направляющей точки к узловым:

(здесь звёздочка означает комплексное сопряжение).

2) зная d, находим длины нормалей

и их сумму и разность

3) находим единичный вектор, от которого начинается построение

4) находим угловые пути, которые должны пройти каждый из векторов

5) последовательно изменяя t от 0 до 1 с некоторым шагом, находим принадлежащую кривой точку по формуле

Циркулярные сплайны

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

Справа для сравнения использован тот же подход с кривыми Безье 2-го порядка.

Замечания и нюансы

В отличие от кривых Безье, здесь кривая не всегда лежит внутри фигуры из линий, соединяющих контрольные точки, например

Кроме того, существует вырожденный случай, который необходимо обрабатывать отдельно — когда направляющая точка лежит на одной прямой с узловыми точками. При этом кривая вырождается в прямую, а при попытке вычислить точку d возникает деление на ноль.

У этих кривых также имеется ограничения на кривизну линии, поскольку в соответствии с алгоритмом выбирается наименьший путь следования и кривая не может обогнуть больше, чем 180°. Это приводит к тому, что при кусочно-непрерывной интерполяции могут возникать острые углы при определённом положении направляющих точек (справа — те же точки для Безье):

Заключение

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

Рассмотренный метод построения кривых также не является единственным, частным случаем которого являются дуги окружности и эллипса — как минимум, эллипс можно построить через пересечение прямых в параллелограмме ^[4] (правда, в этом варианте автор потерпел неудачу). Возможно, что существуют и другие решения, в том числе и варианты описанного в статье — пишите в комментариях, если вам что-то известно на эту тему.

Исходный код статьи можно скачать на GitHub ^[5].

Автор: Refridgerator

Источник ^[6]