logo
CG

32. Алгоритм определения принадлежности точки внутренности треугольника

33. В-сплайн. Алгоритм реализации.

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

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

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

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

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

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

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

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

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