Глава 3. Сплайновые кривые

Общую задачу, рассматриваемую в этой главе, можно сформулировать так: по заданному множеству вершин

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

Рис. 3.1

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

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

где некоторые функциональные коэффициенты, подлежащие определению.

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

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

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

Для описания элементарных кривых и вычисления их геометрических характеристик (информация о которых необходима при состыковке) в качестве функциональных коэффициентов обычно используются многочлены невысоких степеней, 2-й или 3-й, в первую очередь потому, что они сравнительно просто вычисляются. Конечно, привлекая многочлены больших степеней, можно описывать весьма сложные кривые. Однако у таких многочленов много коэффициентов, физический и геометрический смысл которых трудно понять. Кроме того, использование многочленов высокой степени может вызвать нежелательные колебания результирующей кривой.

Наибольшее распространение получили методы конструирования составных кривых, в которых используются кубические многочлены (которые, кстати, активно применялись и в гл. 1). Выбор в качестве функциональных коэффициентов кубических многочленов позволяет учесть и дифференциальные и внешнегеометрические требования, накладываемые на искомую кривую.

Высказанные соображения определяют характер изложения разделов этой главы. Глава начинается с описания минимально необходимого набора сведений из дифференциальной геометрии кривых. Затем рассматриваются различные классы кривых, при помощи которых можно решить поставленную задачу приближения. Описание каждого из классов проводится практически по одной и той же схеме. Сначала

определяются элементарные кривые (фрагменты), а затем показывается, как путем состыковки этих элементарных кривых получить составную кривую с достаточно хорошими характеристиками. Значительное внимание уделено описанию основных свойств рассматриваемых кривых. Такой подход поможет пользователю в выборе наиболее подходящего для него класса кривых. Часть из свойств формулируется в виде ответов на стандартный набор вопросов, среди которых есть, например, такие:

• каков порядок гладкости построенной кривой?

• каковы особенности расположения кривой относительно

заданных вершин опорной ломаной?

• как сказываются на форме кривой изменения опорных вершин?

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

Ясно, что, построив кривую, можно подвергнуть ее любому (аффинному или проективному) преобразованию. Можно поступить и по-иному: сначала подвергнуть этому преобразованию заданный набор опорных вершин и только потом построить по нему кривую из рассматриваемого класса. Если результаты оказываются одинаковыми, то говорят, что кривая инвариантна относительно этого (аффинного или проективного) преобразования.

Напомним, что аффинные преобразования включают в себя вращение, растяжение и сжатие, параллельный перенос и их всевозможные комбинации, а к проективным преобразованиям, кроме того, относятся еще и преобразования перспективы.

Большинство из рассматриваемых классов кривых обладают свойством аффинной инвариантности. Есть среди них и проективно-инвариантные. Хотя окончательный результат и не зависит от последовательности выполнения этих двух операций - преобразования набора опорных точек и построения кривой, выбор порядка их исполнения может заметно снизить вычислительные затраты. Легко заметить, например, что поворот массива вершин вокруг оси на некоторый угол и последующее построение кривой требуют меньшего объема вычислений, чем поворот построенной кривой.

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

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

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

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