Федеральная Служба Опасности (malaya_zemlya) wrote,
Федеральная Служба Опасности
malaya_zemlya

Category:

Кривы и Поврхности

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

Тут на помощь приходит господин Эд Кэтмулл (Edwin Catmull), лауреат всевозможных премий, президент небезызвестной компании Pixar. В 1974ом(!) году он защитил диссертацию, где описал рисование кривых и поверхностей Безье методом деления пополам. Как это делается? Сначала напомню вкратце, основные свойства кривых Безье (все, что я скажу легко переносится на поверхности и 3-х мерные тела):

Кривая Безье - это кривая 3-го порядка, которая задается посредством 4-х контрольных точек: p1,p2,p3,p4. Она проходит через точки p1 и p4 и изгибается в сторону точек p2 и p3 (но обычно не проходит через них). Кривая задается следующех формулой:
x[t]=p1*B1[t]+p2*B2[t]+p3*B3[t]+p4*B4[t]    (1)

где B1,B2,B3,B4 - так называемые "полиномы Бернштейна"

B1[t]=(1-t)^3
B2[t]=3*t*(1-t)^2
B3[t]=3*t^2*(1-t)
B4[t]=t^3

Примечание: Эти полиномы получаются естественным образом, как члены разложения:
1=1^3=((1-t)+t)^3=(1-t)^3+3*t*(1-t)^2+3*t^2*(1-t)+t^3=B1[t]+B2[t]+B3[t]+B4[t]


Что сделал господин Кэтмулл? Он разделил кривую Безье пополам (то есть рассмотрел отдельно интервалы t=0...1/2 и t=1/2...1), получив две кривые поменьше. Оказалось что они тоже описываются формулой Безье, но, естественно, с другими контрольными точками. Метод для их вычисления оказался черезвычайно простым:

Рассмотрим т.н. средние точки:
p12=1/2 (p1+p2)
p23=1/2 (p2+p3)
p34=1/2 (p3+p4)
p123=1/2(p12+p23)
p234=1/2(p23+p34)
p1234=1/2(p123+p234)

(Сходство с треугольником Паскаля неслучайно!)

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

p1,p12,p123,p1234

А для рисования второй половину нам нужны точки

p1234,p234,p34,p4

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

Вот примерный алгоритм:

DrawBezier( Point p1,p2,p3,p4)
{
if ( abs(p1.x-p2.x)< epsilon &&
abs(p1.y-p2.y)< epsilon &&
abs(p2.x-p3.x)< epsilon &&
abs(p2.y-p3.y)< epsilon &&
abs(p3.x-p4.x)< epsilon &&
abs(p3.y-p4.y)< epsilon )
{
// if epsilon is small enough, you can simply use Plot((p1+p4)/2)
DrawLine(p1,p2);
DrawLine(p2,p3);
DrawLine(p3,p4);
return;
}
Point p12 = (p1+p2)/2;
Point p23 = (p2+p3)/2;
Point p34 = (p3+p4)/2;
Point p123 = (p12+p23)/2;
Point p234 = (p23+p34)/2;
Point p1234 = (p123+p234)/2;
DrawBezier(p1,p12,p123,p1234);
DrawBezier(p1234,p234,p34,p4);
}

С поверхностями поступают практически так же, только для их задания требуется уже 16 контрольных точек и деление уже производится не на 2, а на 4 куска. Кода приводить не буду, по причине муторности его набития, надеюсь, что и так понятно, что делать. Но если кому будет нужно, то так уж и быть, постну. Для справки, формула поверхности Безье следующая:

x(u,v)=P11*B1(u)*B1(v)+P12*B1(u)*B2(v)+...+P44*B4(u)*B4(v)

Вот так.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments