3.13. Треугольные сплайновые поверхности

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

Рассмотрим аналогию между В-сплайнами и симплексными сплайнами. Каждый В-сплайн строится на последовательности узлов. Узлами последовательности можно разделить область определения В-сплайна на полуоткрытые подобласти. При этом каждое значение параметра В-сплайна может принадлежать только одной подобласти. Область определения симплексного сплайна можно разбить на несколько подобластей. Каждая точка области определения может принадлежать только одной подобласти. Нужно условиться, какой из двух подобластей принадлежат точки разделяющей их линии. Для этого вводится понятие полуоткрытой выпуклой области.

Полуоткрытая выпуклая область.

Через [V] обозначим выпуклую область, которую покрывает некоторый выпуклый многоугольник V, а через обозначим полуоткрытую выпуклую область многоугольника V. Не все граничные точки выпуклой области [V] принадлежат полуоткрытой выпуклой области [V). Точка принадлежит полуоткрытой выпуклой области [V), если существуют такие при которых точки принадлежат [V].

Рис. 3.13.1. Полуоткрытая выпуклая область

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

Симплексный сплайн.

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

Пусть задана последовательность двухмерных точек хотя бы три из которых не совпадают друг с другом и не лежат на одной прямой. Для такой последовательности можно построить выпуклый многоугольник с вершинами в точках последовательности, так чтобы все точки заданной последовательности принадлежали [V]. В общем случае часть точек заданной последовательности будет лежать в вершинах многоугольника V, часть — на его сторонах и остальная часть — внутри многоугольника V. Некоторые точки последовательности могут совпадать.

Точки последовательности называют узлами. На базе узлов можно построить симплексный сплайн порядка, где . Полуоткрытую выпуклую область [V) многоугольника V называют носителем симплексного сплайна или его областью определения. Все узлы симплексного сплайна равноправны. Симплексный сплайн является функцией точки . Введем еще одно обозначение: через обозначим симплексный сплайн порядка, построенный на последовательности узлов, полученной из заданной последовательности путем исключения из нее вершины

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

(3.13.1)

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

(3.13.2)

где Симплексный сплайн нулевого порядка является разрывной константной функцией положения точки . Симплексный сплайн первого порядка является непрерывной функцией с разрывными первыми производными.

Симплексный сплайн всегда неотрицателен. Он отличен от нуля внутри своей полуоткрытой выпуклой области [V) и равен нулю вне ее.

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

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

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

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

Производная симплексного сплайна (3.13.1) в направлении вектора t вычисляется по формуле

(3.13.3)

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

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

Рис. 3.13.2. Симплексный сплайн первого порядка

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

Рис. 3.13.3. Симплексный сплайн третьего порядка

Рис. 3.13.4. Симплексный сплайн пятого порядка с кратными узлами

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

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

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

Некоторые узлы симплексного сплайна могут лежать на границе его выпуклого многоугольника.

Рис. 3.13.5. Симплексный сплайн третьего порядка с тремя кратными узлами в центре

Рис. 3.13.6. Симплексный сплайн второго порядка

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

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

Рис. 3.13.7. Симплексный сплайн седьмого порядка

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

Трехиндексные функции Бернштейна (3.12.4) являются частными случаями симплексных сплайнов. Функция Бернштейна

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

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

где — удвоенная площадь треугольника Т. Симплексный сплайн построен на последовательности узлов: — кратности , — кратности — кратности .

DMS поверхности.

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

Дамен (Dahmen), Микели (Micchelli) и Зайдель (Seidel) предложили один из способов построения поверхностей на базе симплексных сплайнов. Этот способ имеет много общего со способом построения треугольных поверхностей Безье.

Рис. 3.13.8. Триангуляция в качестве области определения DMS поверхности

Поверхности, построенные этим способом, называют DMS сплайнами или поверхностями. Рассмотрим построение DMS поверхности на базе симплексных сплайнов порядка п.

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

Пусть вершины триангуляции описываются двухмерными радиус-векторами . С каждой вершиной некоторым образом свяжем узлов: . За узел примем вершину остальные узлы могут не совпадать с вершиной. Совокупность узлов называют узловым облаком. Узловые облака нам понадобятся в качестве узлов симплексных сплайнов.

Рассмотрим некоторый треугольник из области определения DMS поверхности О (рис. 3.13.9). Пусть его вершинами являются точки

Рис. 3.13.9. Узловые облака вершин треугольника для

Совокупность всех узлов в вершинах рассматриваемого треугольника называют сеткой узлов. Для треугольника мы можем получить различных последовательностей узлов , где . С каждым треугольником свяжем характеристических пространственных точек где Количество точек равно количеству возможных последовательностей узлов для рассматриваемого треугольника. На характеристические точки никаких ограничений не накладывается. Их положение в пространстве определяет форму DMS поверхности. Пусть треугольники, образованные узлами являются невырожденными, и при обходе их вершин мы будем двигаться против часовой стрелки.

На каждой последовательности узлов найдем выпуклую область симплексный сплайн Вычислим нормированный симплексный сплайн

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

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

(3.13.6)

Внешнее суммирование выполняется по всем треугольникам области определения поверхности О. Внутреннее суммирование в формуле (3.13.6) выполняется по всем возможным последовательностям узлов треугольника Таких последовательностей , где — порядок симплексных сплайнов.

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

В работе [39] показано, что сумма всех отличных от нуля в заданной точке нормированных симплексных сплайнов (3.13.5) равна единице. То есть для правильной триангуляции выполняется равенство

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

(3.13.8)

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