Почему сплайны?

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

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

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

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

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

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

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

Попробуем перевести рассматриваемую проблему на геометрический язык.

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

Тем самым решение задачи создания искривленной поверхности разбивается на несколько этапов:

1) задание подходящего набора опорных точек,

2) выработка универсального и сравнительно несложного способа построения элементарных фрагментов поверхности,

3) отыскание эффективного механизма плавной состыковки элементарных фрагментов,

4) анализ полученных результатов.

Ясно, что решение такой задачи далеко не однозначно, так как приблизить массив точек плавноизменяющейся кривой (или

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

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

Немаловажную роль играет и проблема единственности решения задачи приближения.

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

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

1. Выбираемый класс должен описываться достаточно просто.

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

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

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

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

Именно эти кривые и поверхности принято называть сплайнами.

Таким образом, неизбежность появления сплайнов висела в воздухе уже очень давно. По-видимому, в наиболее доходчивой и вместе с тем поэтичной форме это всеобщее ощущение сумел выразить великий Гоголь в "Женитьбе": "Если бы губы Никанора Ивановича да приставить к носу Ивана Кузьмича, да взять сколько-нибудь развязности, какая у Балтазара Балтазарыча, да, пожалуй, прибавить к этому еще дородности Ивана Павловича - я бы тогда тотчас же решилась" (курсив наш. - А. П., Е. Ш.).