|
RUSH
#02
30 ноября 1999 |
|
Творчество - Алгоритмы и код: Клипирование линии и Кривые Безье.
Рад видеть тебя здесь Читатель!
Если ты сюда залез, то одно из двух: или
ты действительно зашел сюда за знаниями
или просто посмотреть, нет ли здесь
картинок... Но в любом случае рад тебя тут
видеть.
Начну с того, что все же представлюсь. Я
являюсь не кем иным, как главным и
единственным кодером группы Energy Minds в
которой меня прозвали Priest'ом. Надеюсь
ты о нас слышал.
Ну а теперь, что же я все-таки предлагаю
сегодня на ваше рассмотрение:
1. Клипирование линии.
2. Кривые Безье.
------------------------------------------
Клипирование линии
------------------------------------------
Наверное еще кто-то не догадался, что
такое клипирование и поэтому я сразу же
это объясню. Слово клипирование произошло
от английского "to clip", что в переводе
на наш означает, отсекать (резать,
обрезать). Таким образом клипирование
линии это отсечение выходящих за край
экрана концов заданного отрезка. При этом
от отрезка остается только видимая его
часть.
Итак, зачем же отсекать... Как уже
писалось во многих изданиях, пришло время,
когда очень часто приходится пользоваться
векторной графикой. Да и при написании
программ на Бейсике часто возникает
необходимость нарисовать какой-либо объект
нередко уходящий за пределы экрана,
вызывая тем самым ошибку и,
соответственно, останов программы. А
писать для Бейсика подпрограмму нет
смысла, она только замедлит и без того его
медленные расчеты. И тут остается один
выход: ассемблер.
Приведенный ниже алгоритм и его
реализация на ассемблере, являются просто
примерами и критике подвергать не стоит.
Итак в основу всего был положен алгоритм
Сазерленда-Кохена.
В первую очередь нам требуется узнать,
где находятся каждый из концов отрезка.
Для этого используем битовое представление
положения конца отрезка относительно
видимого прямоугольника (у нас этим
прямоугольником выступает экран), т.е.:
бит 0 - точка лежит левее прямоуг.
бит 1 - -----//---- выше прямоуг.
бит 2 - -----//---- правее прямоуг.
бит 3 - -----//---- ниже прямоуг.
Допустим, что х1,у1 координаты первого
конца отрезка, а х2,у2 , соответственно,
координаты второго конца отрезка. Теперь
надо получить два 4х битных кода для обеих
концов. Только сначала условимся, что
начало координат будет в верхнем левом
углу, как на всех других платформах и
почти в 99% спектрумовских программах
написанных на ассемблере. Итак для
спектрумовского экрана это выглядит так:
X1=0 ; левый край видимой области
X2=255 ; правый край видимой области
Y1=0 ; верхний край видимой области
Y2=192 ; нижний край видимой области
code=0 ; переменная для 4х битного кода
if x<X1 then code=code+1
if y<Y1 then code=code+2
if x>X2 then code=code+4
if y>y2 then code=code+8
С помощью такого алгоритма получаем два
кода для двух концов.
А теперь произведем само клипирование по
уже известным положениям концов отрезка.
if bit_0=1; клипим, что левее области
then y1=y1+(y2-y1)*(X1-x1)/(x2-x1)
x1=X1
if bit_1=1; клипим, то что выше области
then x1=x1+(x2-x1)*(Y1-y1)/(y2-y1)
y1=Y1
if bit_2=1; клипим, что правее области
then y1=y1+(y2-y1)*(X2-x1)/(x2-x1)
x1=X2
if bit_3=1; клипим, то что ниже области
then x1=x1+(x2-x1)*(Y2-y1)/(y2-y1)
y1=Y2
После данной процедурки проверяется,
остался ли конец отрезка за экраном, если
не остался, то обрабатываем второй конец,
в другом случае повторяем процедуру
(такого повторения на практике я не
встречал, все должно проходить с первого
раза).
Кстати как вы могли заметить, процедура
клипит только конец отрезка х1,у1. Для
того чтобы отклипить второй конец,
достаточно поменять местами координаты
концов отрезка, а не переписывать
процедуру конкретно для второго конца.
В заключении этой части скажу, что в
приложении лежит исходник "CLIPPING" в
котором реализовано все выше сказанное. Он
записан как текстовый файл, но с
синктасисом ассемблера STORM. Исходник
проверен и работает без глюков (я его уже
применял в своих прогах :).
И еще... В исходнике применена сверх
медленная процедура деления и умножения, а
посему они нуждаются в хорошей замене
:)...
------------------------------------------
Кривые Безье
------------------------------------------
Боюсь, что вы прочитав первые несколько
строк предыдущей части и узнав, что
какое-то клипирование просто отсечение
отрезка, сразу кинулись читать эту часть,
с еще более непонятным названием. Но может
быть это и к лучшему. Так что приступим...
Кривые Безье служат для построения
гладких кривых (глупо звучит, не так ли?)
по какому-либо заданному количеству точек.
Причем кривая является касательной к
отрезкам образованным из данных точек.
Звучит мутно, но сейчас попробую объяснить
по-человечески.
Допустим вы загорелись желанием создать
свой масштабируемый шрифт. Т.е. при
увеличении символа он сохраняет прежний
вид, а не когда увеличенные пиксели
становятся размером с футбольное поле (к
таким шрифтам относятся шрифты .chr с
PCшки). Так вот, обычно такие шрифты
задаются набором вершин, которые
впоследствии соединяются отрезками. Такой
способ приемлем для 80% символьного
набора. Почему? А как вы зададите букву
"О"? Кто-то скажет подумав, можно
расстояние между вершинами уменьшить
настолько, что несколько таких отрезков
сойдут за гладкую кривую.
Да, скажу я, согласен. Но так будет до
тех пор, пока нам не потребуется увеличить
символ, скажем, эдак раз в 10... И что
получится? Расстояния между вершинами тоже
увеличатся раз в 10 и это уже будет отнюдь
не гладкая кривая, а ломанная и далеко не
гладкая. Вот тут и могут прийти на помощь
эти самые кривые. Одно из достоинств этих
кривых, что они всегда плавные, начинаются
всегда в первой заданной точке и
заканчиваются точно в последней заданной
точке. К еще одному из достоинств можно
отнести то, что кривая может пересекать
сама себя и причем не один раз (а в
приведенном ниже примере только один раз,
т.к. у нас будет только 4 точки задающие
кривую). Кстати довольно примечательно,
что если поменять местами любые 2 (или
более) точки, то меняется весь вид кривой
(логичней некуда :).
Вернемся к символу "О". Например нам
потребовалось задать правую(левую)
половину символа. Промучавшись полчаса мы
наконец добились получения плавной
псевдо-кривой из отрезков и на это у нас
ушло, по скромным подсчетам, не менее 10
вершин (все еще зависит от величины
исходного символа, т.к. чем он больше, тем
больше точек требуется для представления
кривой). А для наших кривых будет
достаточно и 4х вершин.
Итак, кривая описывается векторным
уравнением:
m
_____
\ | i i m-i
r(t)= \ C * t * (1-t) * V
/ m i
/____|
i=0
i m!
где C =--------- и 0<t<1
m i!*(m-i)!
Вижу как кто-то дико матерясь орет:
"Дальше вы ребята без меня читайте этот
бред!".
Да, велика формула, но не так страшен
черт как его малюют. Всю эту прелесть мы
доведем до такого состояния, что не то что
на Бейсике, а и на ассемблере енто можно
будет замутить.
Давайте поднапрягем мозги и разберемся,
что здесь почем, только приготовьтесь
вспомнить кое-чего из векторной алгебры
:)...
t - это величина зависящая от того
сколько всего точек будет иметь
кривая, т.е. каким количеством
точек мы нарисуем саму кривую.
Начальное t получается из 1/m,
где m - количество точек. Переби-
рая все t в диапазоне от 0 до 1
мы сможем нарисовать все точки...
При этом t_next=t_previous+1/m
r(t) - функция зависимости r от t.
Т.е. изменяя t от 0 до 1 мы по-
лучим все значения r. Где r яв-
ляется вектор-столбцом. Таким
образом координаты вектора пол-
ностью зависят от параметра t.
Для тех кто не понял:
| x |
r(t) это столбец вида | |,а
| y |
x и y являются коорд. одной из
точек на кривой.
знак суммы - это сумма всех значений,
получаемых из выражения стояще-
го после знака суммы, в котором
изменяется параметр i. Параметр
"m" показывает сколькими направ-
ляющими точками задается наша
кривая.
i
C - коофициенты в разложении бинома
m Ньютона (число сочетаний из m
элементов по i). Принимайте это
так как оно есть, ибо это долгая
история (формула ведь приведена!
И тем более не я ее придумал).
i m-i
t и (1-t) - это из области астроно-
номии :-)
V - это направляющие вершины нашей
i кривой. Т.е. это опять вектор-
столбцы:
(x0;y0),(x1;y1)......(x?;y?)
Говоря нормальным языком это
координаты направляющих точек,
благодоря которым задается вид
кривой.
На данном этапе по-моему еще ничего не
прояснилось, но это еще и не конец.
Давайте построим кривую, определяемую 4мя
точками. При этом следует заметить, что
m=3. Теперь при подстановке i=0...3 должна
получиться формула (попробуйте подставить
все значения и у вас должно получиться
тоже самое):
r(t)=(((1-t)*V0+3*t*V1)*(1-t)+3*t^2*V2)*
*(1-t)+t^3*V3
Т.к. мы уже взрослые и знаем, что: r(t)
это (x,y), а V0...V3 это (x0,y0)...
...(x3,y3). И перебрав все значения t мы
получим все координаты точек на кривой
(при каждом изменении t формула должна
пересчитываться). Кто-то может потрениро-
ваться и записать это уравнение заменяя
r(t) и V на столбцы. А мы тем временем
пойдем дальше.
Воспользуемся свойством столбцов:
|x| |a*x|
a * | |= | |
|y| |a*y|
Глядя на формулу сразу должно бросить-
ся в глаза, что нам только это и нужно
было: это позволяет записать выражение с
x отдельно и с y отдельно. Теперь полу-
чается:
for t=0 to 1 step .01; .01 это 100 точек в
кривой.
x=(((1-t)*x0+3*t*x1)*(1-t)+3*t^1*x2)*
*(1-t)+t^3*x3
y=(((1-t)*y0+3*t*y1)*(1-t)+3*t^1*y2)*
*(1-t)+t^3*y3
plot x,y
next t
Если возьмете шаг не .01, а .001 (1000
точек), то получите не разрывную кривую,
только считать будет соответственно...
Вот и все!
Я думаю, что кто-то возмущенно заорет:
"Ты шо, гад, не мог сразу дать этот
примерчик? Надо было мозгу нам полоскать?"
Отвечу кратко: обьяснение должно было
закончиться на описании формулы,а я просто
еще привел пример как можно пользоваться
формулой если кол-во точек заданно как
const, что, несомненно дает выигрыш не
только в размере, но и в скорости. Ну а
если вам нужно было, чтобы кол-во точек
постоянно изменялось, то дальше формулы
вам читать не нужно было, там все
полностью требует пересчета (кстати
единственный и большой недостаток этих
кривых :-(...
Кто-то все же не угомонится и будет
орать: "Чо ты нам про басик втираешь? На
дворе третье тысячелетие! Что нам на асме
делать с твоими t и его .01 и .001?"
Мда... Вот и подобрались мы к проблемам.
Но начну немного из далека... Сидел я
как-то у знакомого за PCшкой и в AutoCAD'e
14 рисовал курсовик (довольно обьемный). A
пень у него вроде не хилый на 233MHz... И
вот заметил я в этом самом CAD'e опцию
"сплайны" (для тех кто не понял кривые
Безье это и есть сплайны).Тогда я уже был
посвящен в вышеприведенную формулу и меня
это заинтересовало. Вобщем когда я начал
рисовать эти сплайны и задал где-то
порядка 10 направляющих точек, я заметил
что сплайны рисуются далеко не шустро, а
еще через пару секунд понял, что более 15
направляющих точек в этой программе мне не
получить (надеюсь вы представляете какой
обьем вычислений там был при 15 точках?)
Плюс к этому программа является
профессиональной и зараннее количество
направляющих точек не известно, а посему
та "маленькая" формула пересчитывалась
полностью... Так что куда там нам на
3.5MHz иметь такую роскошь, как
произвольное количество направляющих
точек... Итак мы подошли к самому
главному. Теперь попытаемся сделать
нереальное - реальным :). Что нам для
этого нужно?
Во-первых: зная сколько направляющих
точек и точек лежащих на кривой нам нужно,
мы избавляем себя (программу) от 80%
промежуточных вычислений. Т.е. сказав
с6ебе: "Моей кривой достаточно 8
направляющих точек и 256 точек самой
кривой" вы облегчили себе жизнь на 80% :)
Во-вторых:если просчитать все оставшиеся
величины в таблицы то ваша программа уже
может потягаться по скорости с AutoCAD'ом
на том же пне. (прим. После того как я
написал статью я проверил это на практике
и понял, что немного преувеличил в
последней фразе :)
Перед тем как обьяснить все до конца,
хочу предупредить, что нам все же
прийдется работать с дробными числами
(точнее с их образами). Для этого все
дробные числа, в результате подготовки
таблицы (а затем и ее использования),
представим в однобайтной форме. Т.е. все
дроби умножим на 255. К примеру чтобы
получить образ числа 0.01, умножим 0.01 на
255. Полученное число 2.55 округляем до
3х. Число 3, понятное дело, не 0.01, но
зато обладает его свойствами. Как? Очень
просто... Допустим нам надо умножить 117
на 0.01, поэтому берем 117 и умножаем его
на образ 0.01, т.е на 3. получили мы число
351. Это число лучше записать в hex #015f
чтобы было более наглядно. Итак, что это
нам дало? Возьмите калькулятор и умножьте
117 на 0.01. Получили число 1.17. Надеюсь
вы заметили, что целая часть искомого
числа и старшего байта числа полученного
нами совпадает. Вот именно это нам и
требуется. С одной стороны мы пользуемся
дробями, а с другой оперируем целыми
числами, что нам на руку.
Ну "вернемся к нашим баранам". Итак о
каких же велечинах идет речь? Выражение
типа:
i i m-i
C * t * (1-t)
m
можно представить ввиде таблицы. Итак в
чем же тут суть... Значит пусть у нас
будет 8 направляющих точек, а точек в
кривой 256. Теперь попробую привести
пример на басике для создания таблицы:
adress=30000
fact7=5040; 7!
for t=0 to 1 step 1/256; 256 точек
for i=0 to 7; 8 направляющих точек
gosub BINOM
a=c*t^i*(1-t)^(7-i)
poke adress,int (a*255)
adress=adress+1
next i
next t
BINOM:
if i=0 then fact_1=1: goto PROD
fact_i=1
for f=1 to i
fact_i=fact_i*f
next f
PROD:
if (7-i)=0 then fract_mi=1 goto PROD1
fact_mi=1
for f=1 to (7-i)
fact_mi=fact_mi*f
next f
PROD1:
c=fact7/(fact_i*fact_mi)
return
Обратите внимание на то, что следуя
формуле требовалось все умножать на
координаты направляющих точек, а затем
состовлять сумму. Но мы это будем делать в
асме, чтобы не потерять возможности
изменять координаты направляющих точек и
соответственно вид кривой... Длина такой
таблицы составит: 8(напр.)*256(крив.)=2048
байт.
С басиком вроде все... Теперь попробуем
в асме... Это конечно не шедевр кодерского
исскуства... но для примера годится...
SPLINE DI
LD IX,UPRAVL;управляющие точки
LD IY,SPLdata;просчитанные конст.
PUSH IY
LD B,0; 256 точек в кривой
N_DOT PUSH BC,IY
CALL COORDS; считаем x
POP IY
PUSH AF
INC IX
CALL COORDS; считаем y
DEC IX
LD D,A; Y
POP AF
LD E,A; X
CALL PLOT; рисуем точку D=y E=x
POP BC
DJNZ N_DOT; итак 256 точек
POP IY
RET
COORDS PUSH IX
LD B,8; кол-во направл. точек
LAPS LD D,(IY); берем просчитанную
;величину для текущей точки
LD E,(IX); берем одну из коорди-
;нат x или y (устанавливается вызывающей
;процедурой)
INC IX,IX,IY
CALL MULT; D*E=HL
PUSH HL; сохраняем рез-тат
DJNZ LAPS
LD HL,0; сумма =0
.8 POP DE:ADD HL,DE;сумма+сохр. знач.
LD A,H
RL L; судя по старшему биту-
ADC A,0;округляем в болш. или
;меньшую сторону
POP IX
RET
;HL=D*E
MULT LD H,D,D,0,L,D
.8 ADD HL,HL:JR NC,$+3:ADD HL,DE
RET
;координаты управляющих точек
UPRAVL DB #75,#02
DB #9F,#03
DB #C2,#A7
DB #D6,#4E
DB #51,#9A
DB #C8,#B8
DB #02,#33
DB #2F,#05
;константы для каждой точки кривой
SPLdata INCB "SPLdata"
Процедура рисования точки у каждого своя
посему я ее не писал. Асмовый текст
грабанут прямо из моей рабочей проги,
которая лежит в приложении...
Вот наконец-то и все... Кто не понял я не
виноват :)... Шутка... Тут я так подробно
все обьяснил, что я переплюнул авторов
книги из которой я все это почерпнул. Там
все это изложенно на 1.5-2 страницы, и
такими математическими словцами и
обозначениями все преукрашено... Жуть...
Причем 90% из того что я тута разжевал,
там вообще не разьясняется - принимается
как за общеизвестное :)
И еще пару слов... В Спековском варианте
журнала можно будет найти следующие файлы:
Bezie.B - Пример на басике
Spline.B - считалка таблицы
SPLdata.C - уже просчитанная таблица
SPLINE.C - текстовый файл для конвертинга
в STORM навороченной процедуры сплайнов.
Кстати не стоит плеваться увидев
результат работы программы, т.к. точность
вычислений очень низкая 1/256. Более
лучших результатов можно добиться
используя точность 1/65535. Т.е. все
дробные числа (при составлении таблицы)
умножать на 65535, а в асме оперировать
двух и более байтовыми величинами, что
несомненно повлечет за собой потерю
производительности... Решение за вами
господа...
Если будете использовать енто в своих
прогах, то хоть привет передайте, что-ли
:). Копирайт тут явно не мой, а г-на
Безье... :)
__________________________________________
В следующих номерах скорее всего будет
алгоритм быстрой заливки любых замкнутых
областей, вычисление освещенности
полигонов и прочая лабуда. Так что
ждите... До встречи, господа кодеры!
Bye!
Priest/EM/XPJ
__________________________________________
DI:HALT
Другие статьи номера:
Похожие статьи:
В этот день... 21 ноября