Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11631
Последний выпуск: 19.06.2015

Геометрическое сглаживание В-сплайнами

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

рис. 14.1

Рассмотрим построение кубического сплайна. Пусть нам даны две соседние точки, через которые проведем кубический полином, но у полинома — 4 коэффициента, следовательно нужно еще два дополнительных условия или точки. Для этого прихватим еще две соседние точки. Чем более плавной мы хотим видеть линию, тем сложнее пройти точно через точки. Если в формуле x = q3, то достаточно плавности 3.

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

Рассмотрим рис. 14.2. Пусть t — параметр, по которому пробегаем от точки Pi к точке Pi+1. При t = 0 мы находимся в точке Pi, при t = 1 — в точке Pi+1. Если 0 < t < 1, то мы находимся между Pi и Pi+1.

рис. 14.2

Эта линия в каждой точке имеет систему:


x(t) = ((a3t + a2)t + a1)t + a0, для 0 <= t <= 1

y(t) = ((b3t + b2)t + b1)t + b0, для 0 <= t <= 1 a3 = (-xi-1 + 3xi - 3xi+1 + xi+2)/6

a2 = (xi-1 - 2xi + xi+1)/2

a1 = (-xi-1 + xi+1)/2

a0 = (xi-1 + 4xi+ xi+1)/6

Точки b3 - b0 расписывают так же, но вместо x подставляют у. Между Pi и Pi+1 точки а и b не меняются. Если после последней точки указать первую точку, то система замкнет контур.

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

Следствия

  1. Кривые отходят от точек, точки усредняют свое влияние:
    xi: x(0) = a0 = (xi-1 + 4xi + xi+1)/6
    xi+1: x(1) = a3 + a2 + a1 + a0 = (xi + 4xi+1 + xi+2)/6

    рис. 14.3
  2. Изменение одной вершины ведет к изменению только четырех соседних отрезков (рис. 14.4).

    рис. 14.4
  3. Геометрическая интерпретация В-сплайна: так как сумма коэффициентов равна единице, а коэффициенты положительны, то мы получаем средневзвешенную точку для четырех соседей, то есть первоначальный отрезок будет находиться внутри выпуклой сплайновой оболочки. Формула расчета: 1/6хi-1 + 2/3xi + 1/6xi+1 = 2/3xi + 1/3 * [1/2(xi-1 + xi+1)]

    рис. 14.5
  4. Кратность вершины усиливает ее притяжение. В острые углы линия не успевает забегать. В этом случае увеличивают кратность вершины. Порядок сплайна влияет на конфигурацию — увеличение порядка ведет к большему спрямлению (см. рис. 14.6).

Сглаживание B-сплайнами

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

  • поверхность покрывается двумя воображаемыми группами линий; первая идет в продольном направлении, вторая — трансверсальна к первой. Эта сетка линий определяет множество ячеек, каждая из которых (в случае гладкой поверхности), будет ограничена четырьмя гладкими кривыми;
  • координаты узлов этой воображаемой сетки измеряются на модели или на наборе чертежей поперечных сечений поверхности;
  • с помощью интерполяции (усреднения) математически описываются эти две группы линий, образующие сетку.

Можно строить достаточно гладкие кривые и поверхности с использованием полиномов. Допустим, что мы хотим построить поверхность в виде графика функции z = z(x, y). Линия y = const на этой поверхности будет представлена линией z = z(x), она будет проходить через последовательность точек (x0, z0), ..., (xi, zi), ..., (xn, zn) с x0 < ... < xi < ... < xn. Наша цель — провести через эти точки составную кривую f(x), имеющую следующие свойства:

  • на каждом подынтервале xi-1 <= x <= xi, i = 1, 2, ..., n функция f(x) является кубическим полиномом;
  • ее первые и вторые производные непрерывны в узлах.

Полученная гладкая кривая называется кубическим сплайном. Термин «сплайн» возник по аналогии: это название чертежного инструмента — тонкой металлической линейки, которая может изгибаться так, чтобы проходить через заданные точки. Физически такая кривая минимизирует энергию внутренних напряжений. Математически — имеет минимальную среднеквадратичную кривизну, то есть она наиболее гладкая. Сплайны имеют много приложений в конструировании криволинейных форм. Однако они имеют и некоторые ограничения:

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

Первое ограничение можно устранить с помощью B-сплайна. Общая форма полученной в этом случае кривой показана на рис. 20.1.

рис. 20.1

На этом рисунке сплайн продолжен от его конечных точек xi-4, xi прямыми линиями, идущими вдоль оси x. В результате получается кубический сплайн на любом числе отрезков, но он не равен нулю только на четырех из них. Такая функция называется B-сплайном (или фундаментальным сплайном) четвертого порядка (или третьей степени). Про него говорят, что он имеет минимальный носитель (носитель — это число отрезков, на которых сплайн отличен от нуля).

Заметим, что кубический B-сплайн полностью определяется множеством узлов, на которых он определен, и только одной заданной величиной z. В более общем виде B-сплайн Mmi(x) порядка m (или степени m - 1) на данном множестве узлов везде равен нулю, кроме m последовательных отрезков xi-m < x < xi. Опять-таки Mmi(x) определяется множеством узлов и одной величиной z. Принято исключать последнюю степень свободы и фиксировать амплитуду B-сплайна некоторым стандартным образом.

Часто удобно для вычислений использовать нормализованный B-сплайн Nmi(x), связанный с Mmi(x) соотношением Nmi(x) = (xi - xi-m)Mmi(x).

Любой сплайн порядка m на множестве узлов x0, x1, ..., xn может быть выражен в виде линейной комбинации B-сплайнов, определенных на том же множестве узлов, расширенном (m - 1) дополнительными узлами на каждом из концов интервала, которые можно выбрать произвольно: x-m+1, x-m+2, ..., x-1 и xn+1, ..., xn+m-1. Можно построить m + n - 1 последовательных B-сплайнов на расширенном множестве узлов, каждый из которых отличен от нуля на m последовательных отрезках. Поэтому можно записать:
j(x) = Sci * Mmi(x),
где j(x) — любой сплайн степени (m - 1) на первоначальном множестве узлов и Mmi(x) есть B-сплайн на расширенном множестве узлов, отличный от нуля при xi-m < x < xi; ci  суть числовые коэффициенты; суммирование ведется по i = 1, ..., m + n - 1.

Если имеется множество векторов r0, r1, ..., rn, то можно использовать их: r(u) = Sri * N4, i+1(u) (суммирование ведется по i = 0, ..., n). Так как имеется (n + 1) векторных коэффициентов, то необходим набор из (n + 1) B-сплайнов. Последняя формула для 0 <= u <= n - 2 является уравнением кривой, образованной кубическими B-сплайнами.

Свойства

Некоторые простейшие свойства следуют из тождества SN4, i+1 = 1, 0 <= u <= n - 2, i = 0..n. При u = 0 следует: r(0) = N42(0)(r1 - r0). Из этого следует, что если r0, r1, .., rn — вершины некоторой замкнутой ломанной, то кривая, построенная на основе B-сплайна, начинается в r0 и ее касательная в этой точке имеет направление (r1 - r0). Аналогичное утверждение верно и для другого конца. Главное преимущество этого сплайна заключается в том, что изменение одной из вершин влечет за собой изменение только четырех отрезков кривой. Далее, мы также можем построить кривую, аппроксимирующую ломанную с любым желаемым числом сторон. Отрезок сплайна всегда лежит в выпуклой оболочке:

рис. 20.2

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

Имеется еще 2 полезных факта:

  • кривая проходит вблизи средней точки каждой стороны, за исключением 1-ой и последней точками;
  • при k = 2, ..., n - 2 кривая проходит через точки: 1/6rk-1 + 2/3rk + 1/6rk+1 = 2/3rk + 1/3(1/2(rk-1 + rk+1))

Эти точки, как показано на рис. 20.3, лежат на 1/3 расстояния от rk на прямой, соединяющей rk с серединой отрезка между rk-1 и rk+1.

рис. 20.3

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

1.
91K
24 июня 2013 года
Владимир Федосов
0 / / 24.06.2013
Мне нравитсяМне не нравится
24 июня 2013, 10:21:43
на рис 14.1 третья кривая синусоида. с каких пор у нее вторая производная разрывна? или там чтото другое - но не очевидно
2.
38K
13 апреля 2008 года
kup-ol
0 / / 13.04.2008
+0 / -8
Мне нравитсяМне не нравится
13 апреля 2008, 20:13:16
МНЕ НУЖНА ПРОГА О ПОСТРОЕНИИ В-СПЛАЙНОВ И &#946;-СПЛАЙНОВ НА N-ТОЧКАХ НА C++BUILDER.ПОМОГИТЕ ЧЕМ СМОЖЕТЕ, ЗАШИВАЮСЬ, ДЛЯ КУРСОВИКА(СДАВАТЬ ВО ВТОРНИК)!!!!!!!!!!!
3.
22K
21 ноября 2006 года
Arseniy
2 / / 21.11.2006
Мне нравитсяМне не нравится
5 мая 2007, 19:34:04
Кто знает как избегать деления на ноль в нормированных сплайнах n-го порядка?
4.
Аноним
+1 / -12
Мне нравитсяМне не нравится
6 ноября 2005, 16:55:32
Если кому не трудно,то скиньте, плз, исходник на Си-шке или Паскале на мыло: q_shock@freemail.ru,
а то самому разбираться и писать - впадло.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог