Бидејќи LCD екранот може да се гледа како матрица од дискретни елементи (пиксели), од кои секој може да биде осветлен, не е можно директно да се повлече линија од една до друга точка. Процес на откривање пиксели најдобриот начинприближувањето на даден сегмент се нарекува растерско разложување. Кога се комбинира со процесот на рендерирање линија по линија на слика, тоа е познато како конверзија на растерско скенирање. За хоризонтални, вертикални и наклонети под агол од 45°. сегменти, очигледен е изборот на растерски елементи. Со која било друга ориентација, потешко е да се изберат потребните пиксели, како што е прикажано на слика 1.
Сл.1. Растерско разложување на отсечки на линии.
Општите барања за алгоритми за цртање отсечки се следни: Сегментите мора да изгледаат право, да започнуваат и завршуваат во дадените точки, осветленоста по должината на сегментот мора да биде константна и независна од должината и наклонот и мора брзо да се нацртаат.
Постојана осветленост по целиот сегмент се постигнува само кога се цртаат хоризонтални, вертикални и наклонети линии под агол од 45°. За сите други ориентации, растеризацијата ќе резултира со нерамномерност на осветленоста, како што е прикажано на сл. 1.
Повеќето алгоритми за цртање линии користат алгоритам чекор-по-чекор. Еве еден пример за таков алгоритам:
Едноставен алгоритам чекор-по-чекор
позиција = почеток
чекор = прираст
1. акопозиција - крај< точность тогаш 4
акопозиција > крај тогаш 2
акопозиција< конец тогаш 3
2. позиција = позиција - чекор
3. позиција = позиција + чекор
4. заврши
Алгоритам на Брезенхем.
Иако алгоритмот на Брезенхем првично беше развиен за дигитални плотери, тоа е подеднаквоПогоден за LCD монитор. Алгоритмот избира оптимални растерски координати за претставување на сегментот. За време на работата, една од координатите е или x или y (во зависност од наклон) - се менува за еден. Промената на друга координата (на 0 или 1) зависи од растојанието помеѓу вистинската позиција на сегментот и најблиските координати на мрежата. Ова растојание ќе го наречеме грешка.
Алгоритмот е конструиран на таков начин што треба да се провери само знакот на оваа грешка. На сл. 2 ова е илустрирано за сегментот во првиот октант, т.е. за отсечка со наклон кој се движи од 0 до 1. Од сликата можете да видите дека ако наклонот на отсечката од точката (0,0) е поголем од 1/2, тогаш пресекот со правата x = 1 ќе да се наоѓа поблиску до правата y = 1 отколку до правата y = 0. Следствено, растерската точка (1,1) подобро го приближува текот на отсечката отколку точката (1,0). Ако наклонот е помал од 1/2, тогаш е точно спротивното. за наклон од 1/2 нема претпочитан избор. ВО во овој случајалгоритмот ја избира точката (1,1).
Ориз. 2. Главната идеја на алгоритмот Брезенхам.
Не сите сегменти минуваат низ растерски точки. Слична ситуацијаилустрирано на Сл. 3, каде што сегмент со наклон од 3/8 прво поминува низ растерската точка (0,0) и секвенцијално пресекува три пиксели. Пресметката на грешката при претставување на сегмент со дискретни пиксели е исто така илустрирана.
Сл.3. График на грешка во алгоритамот на Брезенхем.
Бидејќи е пожелно да се провери само знакот на грешката, тој првично е поставен на -1/2. Така, ако аголниот коефициент на сегментот е поголем или еднаков на 1/2, тогаш вредноста на грешката во следната растерска точка со координати (1,0) може да се пресмета како
д= д + м
Каде м- аголен коефициент. Во нашиот случај, кога почетна вредностгрешки -1/2
д = 1/2 + 3/8 = -1/8
Бидејќи днегативно, сегментот ќе помине под средината на пикселот. Затоа, пиксел на исто хоризонтално ниво подобро ја приближува положбата на сегментот, така што нане се зголемува. Грешката ја пресметуваме на ист начин
д= -1/8 + 3/8 = 1/4
на следната растерска точка (2,0). Сега дпозитивен, што значи дека сегментот ќе помине повисоко средна точка. Растерски елемент (2,1) со следната најголема координата наподобро ја приближува положбата на сегментот. Оттука насе зголемува за 1. Пред да се разгледа следниот пиксел, потребно е да се поправи грешката со одземање 1 од него
д = 1/4 - 1 = -3/4
Имајте на ум дека пресекот на вертикална линија x= 2 с даден сегментлежи 1/4 под права линија на= 1. Ако ја поместиме отсечката за 1/2 надолу, ја добиваме точно вредноста -3/4. Продолжувањето на пресметките за следниот пиксел дава
д = -3/4 + 3/8 = -3/8
Бидејќи де негативен, тогаш y не се зголемува. Од сето она што е кажано, произлегува дека грешката е отсечениот интервал по оската наразгледуван сегмент во секој растерски елемент (во однос на -1/2).
Да го претставиме алгоритамот на Брезенхам за првиот октант, т.е. за случајот 0 =< y =< x.
Алгоритам на Брезенхам за разложување на сегмент во растер за првиот октант
Цел број- функција за конверзија во цел број
x, y, x, y - цели броеви
е - реално
иницијализација на променливи
Поправена иницијализација со половина пиксели
почеток на главниот циклус
додека (e => 0)
Блок-дијаграмот на алгоритмот е прикажан на Сл. 4.
Сл.4. Блок дијаграм на алгоритам на Брезенхем.
Пример за алгоритам на Брезенхем.
Размислете за отсечка нацртана од точката (0,0) до точката (5,5). Разложувањето на сегмент во растер користејќи го алгоритмот Брезенхам води до следниов резултат:
почетни поставки
e = 1 - 1/2 = 1/2
Резултатот е прикажан на слика 5 и се совпаѓа со очекуваното. Забележете дека растерската точка со координати (5,5) не е активирана. Оваа точка може да се активира со менување на јамката за следно на 0 до x. Активирањето на точката (0,0) може да се елиминира со поставување на изјава Plot непосредно пред следната i линија.
Ориз. 5. Резултат на алгоритмот Брезенхам во првиот октант.
Општ алгоритамБрезенхем.
За да биде целосна имплементацијата на алгоритмот Брезенхам, потребно е да се обработат сегменти во сите октанти. Модификацијата е лесно да се направи, земајќи го предвид во алгоритмот бројот на квадрантот во кој лежи сегментот и неговиот аголен коефициент. Кога абсолутна вредностнаклонот е поголем од 1, напостојано се менува за еден, а критериумот за грешка Брезенхам се користи за да се одлучи дали да се промени вредноста x. Изборот на постојано променлива (за +1 или -1) координата зависи од квадрантот (сл. 6.). Општиот алгоритам може да се формулира на следниов начин:
Генерализиран целоброен алгоритам за квадрант на Брезенхам
се претпоставува дека краевите на отсечката (x1,y1) и (x2,y2) не се совпаѓаат
сите променливи се сметаат за цели броеви
Потпишете- функција која враќа -1, 0, 1 за негативен, нула и позитивен аргумент, соодветно
иницијализација на променливи
x = апс (x2 - x1)
y = abs(y2 - y1)
s1 = Потпишете(x2 - x1)
s2 = Потпишете(y2 - y1)
размена на x и y вредности во зависност од наклонот на сегментот
ако y< x тогаш
крај ако
иницијализација дприспособена за половина пиксел
главната јамка
зајас = 1 до x
Заплет(x,y)
додека(д =>0)
акоРазмена = 1 тогаш
заврши додека
акоРазмена = 1 тогаш
Сл.6. Анализа на случаи за генерализираниот алгоритам Брезенхам.
Пример. Генерализиран алгоритам Брезенхам.
За илустрација, земете ја отсечката од точката (0,0) до точката (-8, -4).
почетни поставки
резултатите од циклусот чекор-по-чекор
Сл.7. Резултатот од генерализираниот алгоритам Брезенхам во третиот квадрант.
На сл. 7 го покажува резултатот. Споредба со Сл. 5 покажува дека резултатите од двата алгоритма се различни.
Следниот дел го разгледува алгоритмот на Брезенхам за генерирање на круг.
Алгоритам на Брезенхам за генерирање на круг.
Неопходно е да се распадне во растер не само линеарно, туку и друго, повеќе сложени функции. Распаѓање конусни пресеци, т.е., кругови, елипси, параболи, хиперболи, беа посветени значителен број дела. Најмногу внимание, се разбира, се дава на кругот. Еден од најефикасните и најлесни за разбирање алгоритми за генерирање кругови се должи на Брезенхам. Прво, забележете дека треба да генерирате само една осмина од кругот. Неговите преостанати делови може да се добијат со последователни рефлексии, како што е прикажано на сл. 8. Ако се генерира првиот октант (од 0 до 45° спротивно од стрелките на часовникот), тогаш вториот октант може да се добие со рефлексија на огледалото во однос на правата линија y = x, што заедно го дава првиот квадрант. Првиот квадрант се рефлектира во однос на правата x = 0 за да се добие соодветниот дел од кругот во вториот квадрант. Горниот полукруг се рефлектира во однос на правата линија y = 0 за да се заврши конструкцијата. На сл. Слика 8 покажува дводимензионални матрици на соодветните трансформации.
Ориз. 8. Генерација полн кругод лакот во првиот октант.
За да го изведете алгоритмот, земете ја првата четвртина од кругот со неговиот центар на почетокот. Забележете дека ако алгоритмот започне во точката x = 0, y = R,тогаш кога се генерира круг во насока на стрелките на часовникот во првиот квадрант нае монотоно опаѓачка функција на аргументите (сл. 9). Исто така, ако Почетна точкае y = 0, X = Р,тогаш кога се генерира круг спротивно од стрелките на часовникот Xќе биде монотоно опаѓачка функција на аргументот u.Во нашиот случај, се избира генерацијата во насока на стрелките на часовникот, почнувајќи од точката X = 0, y = Р.Се претпоставува дека центарот на кругот и почетната точка се токму на растерските точки.
За било кој дадена точкана круг, кога се генерира во насока на стрелките на часовникот, постојат само три можности да се избере следниот пиксел што најдобро се приближува на кругот: хоризонтално надесно, дијагонално надолу и надесно, вертикално надолу. На сл. 10 овие насоки се означени како m H, m D, m V соодветно . Алгоритмот избира пиксел за кој квадратот на растојанието помеѓу еден од овие пиксели и кругот е минимален, т.е.
m H = |(x i + 1) 2 + (y i) 2 -R 2 |
m D = | |
m V = |(x i) 2 + (y i -1) 2 -R 2 |
Пресметките може да се поедностават ако забележиме дека во близина на точката (xi,yi,) можни се само пет типа на пресеци на кругот и растерската мрежа, прикажани на сл. единаесет.
Ориз. 11. Пресек на круг и растерска мрежа.
Разликата помеѓу квадратните растојанија од центарот на кругот до дијагоналниот пиксел (x i, + 1, y i - 1) и од центарот до точка на кругот R 2 е еднаков на
d i = (x i + 1) 2 + (y i -1) 2 -R 2
Како и во алгоритмот Брезенхам за сегмент, препорачливо е да се користи само знакот на грешката, а не нејзината големина, за да се избере соодветниот пиксел.
Кога г< 0 диагональная точка (x i , + 1, у i - 1) се наоѓа во реален круг, односно тоа се случаите 1 или 2 на сл. 11. Јасно е дека во оваа ситуација треба да изберете кој било пиксел (x i, + 1, наз) , т.е. m H, или пиксел (x i, + 1, најас - 1), т.е. m D. За да го направите ова, прво разгледајте го случајот 1 и проверете ја разликата во квадратните растојанија од кругот до пикселите во хоризонтална и дијагонална насока:
d = |(x i + 1) 2 + (y i) 2 -R 2 | - |(x i + 1) 2 + (y i -1) 2 -R 2 |
На г< 0 расстояние от окружности до диагонального пикселя больше, чем до горизонтального. Напротив, ако г > 0, растојанието до хоризонталниот пиксел е поголемо. Така,
на г<= 0 выбираем m H в (x i , + 1, у i - 1)
за d > 0, изберете m D во (x i, + 1, y i - 1)
На e = 0, кога растојанието од кругот до двата пиксели е исто, го избираме хоризонталниот чекор.
Бројот на пресметки потребни за да се процени вредноста на e може да се намали со забележување дека во случајот 1
(x i + 1) 2 + (y i) 2 -R 2 >= 0
(x i + 1) 2 + (y i -1) 2 -R 2< 0
бидејќи дијагонален пиксел (x i, + 1, најас - 1) секогаш лежи внатре во кругот и хоризонтално (x i, + 1, наз) - надвор од неа. Така, e може да се пресмета со помош на формулата
г = (x i + 1) 2 + (y i) 2 -R 2 + (x i + 1) 2 + (y i -1) 2 -R 2
Дополнување на полн квадратчлен (y i) 2 користејќи собирање и одземање - 2y i + 1 дава
d = 2[(x i + 1) 2 + (y i -1) 2 -R 2 ] + 2y i - 1
ВО квадратни заградистои по дефиниција e i и неговата замена
г = 2 (e i + y i) - 1
во голема мера го поедноставува изразувањето.
Размислете за случајот 2 на сл. 11 и забележете дека овде мора да се избере хоризонталниот пиксел (x i, + 1, y i), бидејќи y е монотоно опаѓачка функција. Проверката на компонентите e покажува дека
(x i + 1) 2 + (y i) 2 -R 2< 0
(x i + 1) 2 + (y i -1) 2 -R 2< 0
бидејќи во случајот 2 хоризонталните (x i, + 1, y i) и дијагоналните (x i, + 1, y i -1) пиксели лежат во кругот. Затоа г< 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел (x i , + 1, у i).
Ако e i > 0, тогаш дијагоналната точка (x i, + 1, y i -1) е надвор од кругот, т.е. тоа се случаите 3 и 4 на сл. 11. Во оваа ситуација, јасно е дека или пикселот (x i, + 1, y i -1) или (x i, y i -1) мора да се избере . Слично на анализата на претходниот случај, критериумот за избор може да се добие со прво разгледување на случајот 3 и проверка на разликата помеѓу квадратните растојанија од кругот до дијагоналата m D и вертикалните m V пиксели,
т.е " = |(x i + 1) 2 + (y i -1) 2 -R 2 | - |(x i) 2 + (y i -1) 2 -R 2 |
На г " < 0 растојанието од кругот до вертикалниот пиксел (x i, y i -1) е поголемо и треба да изберете дијагонален чекор до пикселот (x i, + 1, y i -1). Напротив, во случајот г " > 0, растојанието од кругот до дијагоналниот пиксел е поголемо и треба да изберете вертикално движење до пикселот (x i, y i -1). Така,
на г " <= 0 изберете m D во (x i +1, y i -1)
на г " > 0 изберете m V во (x i, y i -1)
Овде во случајот г " = 0, т.е. кога растојанијата се еднакви, се избира дијагоналниот чекор.
Проверка на компоненти д " покажува дека
(x i) 2 + (y i -1) 2 -R 2 >= 0
(x i + 1) 2 + (y i -1) 2 -R 2< 0
бидејќи за случајот 3, дијагоналниот пиксел (x i +1, y i -1) е надвор од кругот, додека вертикалниот пиксел (x i, y i -1) е внатре во него. Ова ни овозможува да напишеме е " како
г " = (x i +1) 2 + (y i -1) 2 -R 2 + (x i) 2 + (y i -1) 2 -R 2
Со комплетирање на совршениот квадрат на членот (x i) 2 со собирање и одземање 2x i + 1 се добива
г " = 2[(x i +1) 2 + (y i -1) 2 -R 2 ] - 2x i - 1
Користејќи ја дефиницијата d i го доведува изразот до формата
г " = 2 (т.е - x i )- 1
Сега, со оглед на случајот 4, повторно забележуваме дека треба да го избереме вертикалниот пиксел (x i, y i -1), бидејќи y е монотоно опаѓачка функција како што се зголемува X.
Проверка на компонентите г " за случајот 4 покажува дека
(x i +1) 2 + (y i -1) 2 -R 2 > 0
(x i) 2 + (y i -1) 2 -R 2 > 0
бидејќи и двата пиксели се надвор од кругот. Затоа, д " > 0 и при користење на критериумот развиен за случајот 3 се случува правилен избор на m V .
Останува да се провери само случајот 5 на сл. 11, што се јавува кога дијагоналниот пиксел (x i, y i -1) лежи на кругот, т.е. d i = 0. Проверката на компонентите e покажува дека
(x i +1) 2 + (y i) 2 -R 2 > 0
Затоа, се избира d > 0 и дијагоналниот пиксел (x i +1, y i -1). Слично, ги проценуваме компонентите г " :
(x i +1) 2 + (y i -1) 2 -R 2 = 0
(x i +1) 2 + (y i -1) 2 -R 2< 0
и г " < 0, что является условием выбора правильного диагонального шага к (x i +1 , у i -1) . Таким образом, случай d i = 0 подчиняется тому же критерию, что и случай d i < 0 или d i >0. Да ги сумираме добиените резултати:
г<= 0 выбираем пиксел (x i +1 , у i) - m H
г > 0 изберете пиксел (x i +1, y i -1) - м Д
г " <= 0 выбираем пиксел (x i +1 , у i -1) - m D
г " > 0 изберете пиксел (x i, y i -1) - m V
d i = 0 изберете пиксел (x i +1, y i -1) - m D
Лесно е да се развијат едноставни релации за повторување за да се имплементира алгоритам во чекор. Прво земете го хоризонталниот чекор m H до пикселот (x i + 1, y i) . Да ја означиме оваа нова позиција на пиксели како (i + 1). Тогаш координатите на новиот пиксел и вредноста e i се еднакви
d i +1 = (x i +1 +1) 2 + (y i +1 -1) 2 -R 2 dd i + 2x i +1 + 1
Слично на тоа, координатите на новиот пиксел и вредноста d i за чекорот m D до пикселот (x i + 1, y i -1) се како што следува:
d i+1 = d i + 2x i+1 - 2y i+1 +2
Истото за чекорот m V до (x i, y i -1)
d i+1 = d i - 2y i+1 +1
Подолу е дадена имплементација на алгоритмот на Брезенхам во псевдокод за круг.
Чекор-по-чекор алгоритам на Брезенхам за генерирање круг во првиот квадрант
сите променливи се цели броеви
иницијализација на променливи
Ограничување = 0
1 Заплет(x i, y i )
ако y јас<= Пределпотоа 4
Избор на случај 1 или 2, 4 или 5 или 3
ако Д и< 0тогаш 2
ако Д > 0тогаш 3
ако D i = 0 тогаш 20
дефиниција на случај 1 или 2
2 d = 2d i + 2у i - 1
ако г<= 0тогаш 10
ако d > 0 тогаш 20
дефиниција на случај 4 или 5
3 d = 2D i + 2x i - 1
аког <= 0тогаш 20
аког > 0 тогаш 30
изведување чекори
10 x i = x i + 1
D i = D i + 2x i + 1
еОдо 1
20 x i = x i + 1
D i = D i + 2х i - 2у i + 2
оди на 1
4 завршница
Граничната променлива е поставена на нула за да го прекине алгоритмот на хоризонталната оска, што резултира со генерирање на круг во првиот квадрант. Ако е потребен само еден од октантите, тогаш вториот октант може да се добие со помош на поставката Limit = Цел број(R/sqrt(2)), а првиот - користејќи го одразот на вториот октант во однос на правата линија y = x (слика 8). Блок-дијаграмот на алгоритмот е прикажан на сл. 12.
Ориз. 12. Блок дијаграм на алгоритам на Брезенхам за генерирање круг во првиот квадрант.
Безиевата крива и нејзиниот геометриски алгоритам.
Безиерските облини беа развиени независно во 60-тите години на 20 век од Пјер Безиер од автомобилската компанија Рено и Пол де Кастељау од компанијата Цитроен, каде што беа користени за дизајнирање на каросерии на автомобили.
И покрај фактот дека откритието на Де Кастелие беше направено нешто порано од Безие (1959), неговото истражување не беше објавено и беше скриено од компанијата како деловна тајна до крајот на 1960-тите.
Кривите првпат беа претставени на пошироката јавност во 1962 година од францускиот инженер Пјер Безје, кој, откако ги разви независно од де Кастелие, ги користеше за компјутерски потпомогнато дизајнирање на автомобилски тела. Кривите биле именувани по Безје, а рекурзивниот метод што тој го развил за одредување криви (алгоритам на де Кастелие) го добил името по де Кастелиер.
Последователно, ова откритие стана едно од најважните алатки во системите за дизајн со помош на компјутер и програмите за компјутерска графика.
Безиерска крива – параметарска крива дадена со изразот
, 0 < t <1
каде е функцијата на компонентите на векторите на потпорните темиња, и – основни функцииБезиерските облини, исто така наречени Бернштајн полиноми.
каде n е степенот на полиномот, i е редниот број на референтното теме.
Видови безиерски криви
Линеарни кривини
Кога n = 1, кривата е права линија, референтните точки P0 и P1 го дефинираат нејзиниот почеток и крај.
Кривата е дадена со равенката:
,
Квадратни кривини
(n = 2) е специфицирано со 3 референтни точки: P0, P1 и P2.
Квадратни Bezier криви како дел од сплајни се користат за опишување на обликот на знаците во фонтовите TrueType и SWF-датотеките.
Кубни кривини
(n = 3) се опишува со следнава равенка:
Четири референтни точки P0, P1, P2 и P3, дефинирани во 2- или 3-димензионален простор, го одредуваат обликот на кривата.
Линијата започнува од точката P0 која се движи кон P1 и завршува во точката P3 приближувајќи и се од P2. Тоа е, кривата не поминува низ точките P1 и P2, тие се користат за да се покаже нејзината насока. Должината на сегментот помеѓу P0 и P1 одредува колку брзо кривата ќе се сврти кон P3.
Во форма на матрица, кубната Безиеова крива е напишана на следниов начин:
,
каде се вика основна матрицаБезиер:
Современите графички системи како што се PostScript, Metafont и GIMP користат Bezier шипки составени од кубни криви за да претставуваат заоблени форми.
Примена во компјутерска графика
Поради леснотијата на дефиниција и манипулација, Bezier кривите се широко користени во компјутерската графика за моделирање на мазни линии. Кривата целосно лежи во конвексниот труп на неговите референтни точки. Ова својство на Безиерските криви, од една страна, во голема мера ја поедноставува задачата за пронаоѓање на пресечните точки на кривите (ако конвексните трупови не се сечат, тогаш самите кривини не се сечат), а од друга страна, ви овозможува да се визуелизира кривата користејќи ги нејзините референтни точки. Дополнително, трансформациите на афините криви (превод, скалирање, ротација) исто така може да се имплементираат со примена на соодветни трансформации на контролните точки.
Најважни се безиерските кривини од вториот и третиот степен (квадратни и кубни). Кривите со повисоки степени бараат повеќе пресметки кога се обработуваат и се користат поретко за практични цели. За да се конструираат линии со сложени форми, поединечните Безиерови криви може последователно да се поврзат една со друга за да формираат Безиерски сплин. За да се обезбеди мазна линија на спојот на две кривини, соседните контролни точки на двете кривини мора да лежат на иста линија. Во програмите за векторска графика како Adobe Illustrator или Inkscape, овие фрагменти се познати како „патеки“.
Геометриски алгоритам за Безиеова крива
Овој алгоритам ви овозможува да ги пресметате координатите (x, y) на точка на Безиеова крива врз основа на вредноста на параметарот т.
1. Секоја страна од контурата на многуаголникот што минува низ ориентирните точки е поделена пропорционално на вредноста т.
2. Точките на делење се поврзани со прави отсечки и формираат нов многуаголник. Бројот на јазли на новото коло е за еден помал од бројот на јазли од претходното коло.
3. Страните на новата контура повторно се поделени пропорционално на вредноста т. И така натаму. Ова продолжува додека не се добие единствена точка на делење. Оваа точка ќе биде точка на безиерската крива.
Еве снимка од геометрискиот алгоритам во C++:
за (i = 0;јас< = m;јас + +)
R[i] =P[i]; // креирајте помошна низаР
за (j = m; i > 0; i – –)
за (i = 0; i< j; i + +)
R[i] =R[i] +т*(R[јас + 1] -R[i]);
Резултатот од алгоритмот - координатите на една точка од Безиевата крива се запишуваат во Р.
Модели за опишување на површини. Аналитички модел.
Аналитички модел е опис на површина со помош на математички формули:
z = f(x,y) – опис со помош на функција,
F(x,y,z) = 0 – опис со помош на имплицитна равенка.
Често се користи параметарска форма на опис на површината:
каде што s и t се параметри кои се менуваат во одреден опсег, а функциите Fx, Fy и Fz го одредуваат обликот на површината.
Предност параметарската форма лежи во леснотијата на опишување на површини кои одговараат на двосмислени функции и затворени површини.
Параметриски опис може да се постави на таков начин што формулата нема значително да се промени (да стане посложена) кога површината се ротира или се намалува.
Како пример, разгледајте го аналитичкиот опис на површината на топката.
е експлицитна функција од два аргументи,
- имплицитна равенка,
x = R sin s cos t, y = R sin s sin t, z = R cos s – во параметарска форма.
Аналитичкиот модел е најсоодветен за многу операции за анализа на површината.
Предности модели (од гледна точка на CG):
- леснотија на пресметување на координатите на секоја површинска точка и нормала;
- мала количина на податоци за да се опишат прилично сложените форми.
Недостатоци:
- сложеноста на формулите за опис со користење на функции кои полека се пресметуваат на компјутер ја намалува брзината на операциите на приказот;
- Во повеќето случаи, невозможно е да се примени оваа форма на опис директно на сликата на површината - површината се прикажува како полиедар, чии координати на темињата и лицата се пресметуваат за време на процесот на прикажување, што ја намалува брзината во споредба со полигонален опис модел.
Површински модел "униформа мрежа".
Овој модел ги опишува координатите на поединечните површински точки на следниот начин. На секој мрежен јазол со индекси (i, j) му е доделена висинска вредност zij. Индексите (i, j) одговараат на одредени координатни вредности (x, y). Растојанието помеѓу јазлите е исто - dx по x-оската, dy по y-оската. Всушност, таков модел е дводимензионална низа, растер, матрица, од кои секој елемент складира вредност на висина.
Не секоја површина може да биде претставена со овој модел. Ако на секој јазол е забележана само една вредност на висината (i, j), тоа значи дека површината е опишана со една вредносна функција z = f (x, y). Со други зборови, ова е површина што секоја вертикала ја пресекува само еднаш. Не може да се моделираат ниту вертикалните лица. Треба да се забележи дека решетката може да се специфицира не само во Декартови координати. На пример, за да ја опишете површината на топката со единствена функција, можете да користите поларни координати. Користејќи униформа мрежа, често се опишува релјефот на површината на земјата.
Позитивни карактеристики на униформа мрежа:
- леснотија на опис на површини;
- способност брзо да се дознае висината на која било точка на површината со едноставна интерполација.
Недостатоци на униформа мрежа:
- површините што одговараат на двосмислена висинска функција во точките на мрежата не можат да се моделираат;
- За да се опишат сложените површини, потребен е голем број јазли, што може да биде ограничено со количината на компјутерска меморија.
Модел на површина со „нерамна мрежа“.
Нерамна мрежа е модел за опишување површина во форма на збир на поединечни точки ((x0, y0, z0), (x1, y1, z1), ..., (xn – 1, yn – 1, zn – 1)) кои припаѓаат на површината. Овие точки може да се добијат, на пример, како резултат на мерење на површината на објект со помош на одредена опрема. Овој модел може да се смета за генерализација за некои од моделите дискутирани погоре. На пример, модел на векторски полигон и униформа мрежа може да се сметаат за варијации на неуниформната мрежа.
Ајде да разгледаме површински модел во форма на збир на вредности на точки кои логично не се поврзани едни со други. Нерамномерноста на дефинирањето на референтните точки го отежнува одредувањето на координатите за други површински точки кои не се совпаѓаат со референтните точки. Потребни се посебни техники на просторна интерполација.
Нека задачата е да се пресмета вредноста на z координатата користејќи познати координати (x, y). За да го направите ова, треба да пронајдете неколку од најблиските точки, а потоа да ја пресметате саканата z вредност врз основа на релативната положба на овие точки во проекцијата (x, y). За униформа мрежа, овој проблем е решен прилично едноставно - практично нема пребарување, веднаш се пресметуваат индексите на најблиските референтни точки.
Втората задача е да се прикаже (визуелизира) површината. Овој проблем може да се реши на неколку начини. Еден од најчестите е триангулацијата.
Процесот на триангулација може да се претстави на следниов начин:
- ги наоѓаме првите три точки најблиску еден до друг - добиваме едно рамно триаголно лице;
- ја наоѓаме точката најблиску до ова лице и формираме соседно лице, и така натаму, додека не остане ниту една точка.
Алгоритмот Брезенхам беше предложен од Џек Е. Брезенхам во 1962 година и е наменет за цртање форми со точки на рамнина. Овој алгоритам е широко користен во компјутерската графика за цртање линии на екранот. Алгоритмот одредува кои точки на дводимензионален растер треба да се насликаат.
Графичка интерпретација на алгоритмот на Брезенхам е претставена на сликата.
За да нацртаме прави отсечки на рамнина користејќи го алгоритмот Брезенхам, ја пишуваме равенката на права линија во општа форма
f(x,y)=Ax+By+C=0
каде се коефициентите АИ Бизразени преку коефициенти кИ бравенки на права линија. Ако права минува низ две точки со координати ( x1;y1) И ( x2;y2), тогаш со формулите се одредуваат коефициентите на равенката на права линија
A=y2-y1
Б=х1-х2
C=y1∙x2-y2∙x1
За која било растерска точка со координати ( xi;ји) функција на вредност
- f (xi, yi)=0 ако точката лежи на права
- f (xi, yi)>0 ако точката лежи под линијата
- f (xi, yi)Каде јас– број на прикажаната точка.
Така, еден метод за одлучување која точка Пили П(види слика) ќе се прикаже во следниот чекор, е споредбата на средината на сегментот |P-Q|со вредност на функцијата f(x,y). Доколку вредноста f(x,y)лежи под средната точка на сегментот |P-Q|, тогаш следната точка што ќе се прикаже ќе биде точката П, инаку - точка П
.
Да го запишеме инкрементот на функцијата
∆f=A∆x+B∆y
Откако ќе се прикаже точка со координати (xi, yi)се донесува одлука за следната точка што треба да се прикаже. За да го направите ова, зголемувањата се споредуваат ΔxИ Δy, карактеризирајќи го присуството или отсуството на движење по соодветната координата. Овие зголемувања може да ги земат вредностите 0 или 1. Затоа, кога се движиме од точка надесно,
кога се движиме од точка надесно и надолу, тогаш
∆f=A+B,
кога се движиме од точка надолу, тогаш
Ги знаеме координатите на почетокот на отсечката, односно точка која очигледно лежи на саканата линија. Таму ја ставаме првата точка и прифаќаме ѓ= 0. Може да направите два чекора од моменталната точка - или вертикално (хоризонтално) или дијагонално по еден пиксел.
Насоката на движење вертикално или хоризонтално се одредува со коефициентот на аголот на навалување. Ако аголот на наклон е помал од 45º, и
|А|<|B|
Со секој чекор, движењето се случува хоризонтално или дијагонално.
Ако аголот на наклон е поголем од 45º, при секој чекор движењето е вертикално или дијагонално.
Така, алгоритмот за цртање наклонет сегмент е како што следува:
Имплементација во C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#вклучи
користејќи именски простор std;
празнина Брезенхем (char **z, int x0, int y0, int x1, int y1)
{
int A, B, знак;
A = y1 - y0;
B = x0 - x1;
ако (abs(A) > abs(B)) знак = 1;
друг знак = -1;
int signa, signb;
ако< 0) signa = -1;
друго знак = 1;
ако (Б< 0) signb = -1;
друго знакb = 1;
int f = 0;
z = "*" ;
int x = x0, y = y0;
ако (знак == -1)
{
направи (
f += A * знак;
ако (f > 0)
{
f -= B*знак;
y += знак;
}
x -= знакб;
z[y][x] = "*" ;
}
друго
{
направи (
f += B*знак;
ако (f > 0) (
f -= А*сигна;
x -= знакб;
}
y += знак;
z[y][x] = "*" ;
) додека (x != x1 || y != y1);
}
}
int main()
{
const int SIZE = 25; // големина на поле
int x1, x2, y1, y2;
шар**з;
z = нов знак *;
за (int i = 0; i< SIZE; i++)
{
z[i] = нов знак ;
за (int j = 0; j< SIZE; j++)
z[i][j] = "-" ;
}
коут<<
"x1 = "
; cin >> x1;
коут<<
"y1 = "
; cin >> y1;
коут<<
"x2 = "
; cin >>x2;
коут<<
"y2 = "
; cin >> y2;
Брезенхем(z, x1, y1, x2, y2);
за (int i = 0; i< SIZE; i++)
{
за (int j = 0; j< SIZE; j++)
коут<<
z[i][j];
коут<<
endl;
}
cin.get(); cin.get();
врати 0;
}
Резултат од извршувањето
Алгоритмот на Брезенхам може да се користи и во контролни проблеми, како што се контрола на моќ или брзина. Во овој случај, хоризонталната оска е временската оска, а одредената вредност го поставува коефициентот на аголот на наклон на правата линија.
Алгоритамот на Брезенхам е алгоритам кој одредува кои точки на дводимензионален растер треба да бидат засенчени за да се добие блиска апроксимација на права линија помеѓу две дадени точки.
Отсечката е нацртана помеѓу две точки - (x0,y0) и (x1,y1), каде што во овие парови се означени колоната и редот, соодветно, чии броеви се зголемуваат надесно и надолу. Прво ќе претпоставиме дека нашата линија оди надолу и надесно, а хоризонталното растојание x1 − x0 го надминува вертикалното растојание y1 − y0, т.е. наклонот на линијата од хоризонталата е помал од 45°. Нашата цел е за секоја колона x помеѓу x0 и x1, да одредиме кој ред од y е најблиску до правата и да нацртаме точка (x,y).
Општата формула за права помеѓу две точки е:
Бидејќи ја знаеме колоната x, редот y се добива со заокружување на цел број следната вредност:
Сепак, нема потреба да се пресметува точната вредност на овој израз. Доволно е да се забележи дека y се зголемува од y0 и за секој чекор додаваме по еден на x и ја додаваме вредноста на наклонот на y
што може да се пресмета однапред. Покрај тоа, на секој чекор правиме една од двете работи: или го задржуваме истото y, или го зголемуваме за 1.
Кое од овие две да се избере може да се одлучи со следење на вредноста на грешката, што значи вертикално растојание помеѓу тековната вредност y и точната вредност y за тековната x. Секогаш кога го зголемуваме x, ја зголемуваме вредноста на грешката за количината на наклон s дадена погоре. Ако грешката е поголема од 0,5, правата е поблиску до следната y, така што го зголемуваме y за еден додека ја намалуваме вредноста на грешката за 1. При имплементацијата на алгоритмот подолу, заплетот(x,y) црта точка и abs ја враќа апсолутната вредност на бројот:
функцијалинија (x0, x1, y0, y1)
интделтакс:= abs (x1 - x0)
интделтај:= abs (y1 - y0)
вистинскигрешка: = 0
вистински deltaerr:= deltay / deltax
инт y:=y0
за x од x0 до x1
грешка:= грешка + deltaerr
акогрешка >= 0,5
грешка:= грешка - 1.0
Нека почетокот на отсечката има координати (X 1,Y 1), а крајот (X 1,X 2). Да означиме
Dx=(X 2 -X 1),dy=(Y 2 -Y 1) . Без губење на општоста, ќе претпоставиме дека почетокот на сегментот се совпаѓа со потеклото на координатите, а правата линија има форма
Каде. Претпоставуваме дека почетната точка е лево. Нека на (i-1)-тиот чекор моменталната точка на отсечката е P i -1 =(r,q) . Изборот на следната точка S i или T i зависи од знакот на разликата (s-t). Ако (s-t)<0 , то P i =T i =(r+1,q) и тогда
X i +1 =i+1;Y i +1 =Y i, ако (s-t)≥0, тогаш P i =T i =(r+1,q+1) и потоа X i +1 =i+ 1 ; Y i +1 =Y i +1 ;
dx=(s-t)=2(rdy-qdx)+2dy –dx
Бидејќи знакот dx=(s-t) се совпаѓа со знакот на разликата, ќе го провериме знакот на изразот d i =dx(s-t). . Бидејќи r=X i -1 и q=Y i -1, тогаш
d i +1 = d i +2dy -2dx(y i -y i -1) .
Нека на претходниот чекор d i<0 , тогда(y i -y i -1)=0 и d i +1 = d i +2dy . Если же на предыдущем шаге d i ≥0 , тогда(y i -y i -1)=1 и d i +1 = d i +2dx(y i -y i -1)
Останува да дознаеме како да се пресмета d i. Бидејќи за i=1
Постапка Bresenham(x1,y1,x2,y2,Боја: цел број);
dx,dy,incr1,incr2,d,x,y,xend: цел број;
dx:= ABS (x2-x1);
dy:= Abs(y2-y1);
d:=2*dy-dx; (почетна вредност за г)
incr1:=2*dy; (прираст за г<0}
incr2:=2*(dy-dx); (прираст за d>=0)
ако x1>x2 тогаш (почнете од точката со помалата вредност x)
PutPixel (x, y, Боја); (прва точка од сегментот)
Додека х d:=d+incr1 (изберете ја долната точка) d:=d+incr2; (изберете ја горната точка, y се зголемува) PutPixel (x, y, Боја); 26. Општ алгоритам Брезенхам.
Алгоритмот избира оптимални растерски координати за претставување на сегментот. Поголемиот од зголемувањата, или Δx или Δy, се избира како растерска единица. За време на работата, една од координатите - или x или y (во зависност од наклонот) - се менува за една. Промената на друга координата (на 0 или 1) зависи од растојанието помеѓу вистинската позиција на сегментот и најблиските координати на мрежата. Ова растојание е грешка. Алгоритмот е конструиран на таков начин што треба само да го знаете знакот на оваа грешка. Следствено, растерската точка (1, 1) подобро го приближува текот на сегментот отколку точката (1, 0). Ако наклонот е помал од ½, тогаш е точно спротивното. За наклон од ½, нема претпочитан избор. Во овој случај, алгоритмот ја избира точката (1, 1). Бидејќи е пожелно да се провери само знакот на грешката, тој првично е поставен на -½. Така, ако наклонот на сегментот е поголем или еднаков на ½, тогаш вредноста на грешката во следната растерска точка може да се пресмета како e = -½ + Δy/Δx. За да биде целосна имплементацијата на алгоритмот Брезенхам, потребно е да се обработат сегменти во сите октанти. Ова е лесно да се направи, земајќи го предвид во алгоритмот бројот на квадрантот во кој лежи сегментот и неговиот аголен коефициент. Кога апсолутната вредност на наклонот е поголема од 1, y постојано се менува за еден, а критериумот за грешка Брезенхам се користи за да се одлучи дали да се промени вредноста на x. Изборот на постојано променлива (+1 или -1) координата зависи од квадрантот
var x,y,sy,sx,dx,dy,e,z,i: Цел број; 27. Брезенхам алгоритам за генерирање на круг
Растерот треба да се прошири како линеарни и други, посложени функции. Распределбата на терминалните исечоци, како што се кили, елипси, параболи, хиперболи, беше доделена на бројот на роботи. Со најголема почит, разбирливо е додаден влог. Еден од најефикасните и најлесните за разбирање алгоритми за генерирање кругови е оној на Брезенхам. За кочанот, важно е да се генерира само една осмина од влогот. Овие делови може да се отстранат со последователни удари. Откако ќе се генерира првиот октант (од 0 до 45 ° од стрелката против годината), тогаш другиот октант може да се изрази како огледална слика на правата линија y = x, што заедно го дава првиот квадрант. Првиот квадрант се чука право x = 0 за да се отстрани потпорниот дел од колецот од другиот квадрант. Горниот е соборен директно на = 0 за да се заврши задачата. За да го прикажеме алгоритмот, ајде да погледнеме четвртина од влогот центриран на кочанот од координати. Ве молиме имајте предвид дека бидејќи алгоритмот започнува во точката x = 0, y = R, тогаш кога се генерира круг зад стрелката на годината на првиот квадрат, y е монотоно опаѓачка функција на аргументите. Слично, ако излезната точка е y = 0, x == R, тогаш кога се генерира круг спроти стрелката x ќе биде монотоно опаѓачка функција на аргументот y. Во нашиот случај, се избира генерацијата зад стрелката на годината со кочан во точката x = 0, y = R Се пренесува дека центарот на влогот и точката на кочанот се токму на растерските точки. За која било дадена точка на кругот кога се генерира зад стрелката на годината, постојат само три можности да се избере следниот пиксел, најблискиот круг: хоризонтално надесно, дијагонално надолу и надесно, вертикално надолу. Алгоритмот избира пиксел за кој минималниот квадрат е помеѓу еден од тие пиксели и кругот. 28. Концептот на фрактал. Историја на фрактална графика
Во секојдневниот живот, често можете да набљудувате слики (шеми) кои, се чини, не можат да се опишат математички. Пример: прозорците замрзнуваат во зима, може да завршите со набљудување на сликата. Таквите множества се нарекуваат фрактал. Фракталите не се слични на добро познатите фигури од геометријата и се градат според одредени алгоритми кои можат да се имплементираат на компјутер. Едноставно кажано, фрактал е слика што произлегува од некаква трансформација која постојано се применува на оригиналната форма. Фрактал е геометриска фигура која се состои од делови и која може да се подели на делови, од кои секоја ќе претставува помала копија од целината. Главното својство на фракталите е самосличноста, т.е. кој било фрагмент од фрактал на еден или друг начин ја репродуцира неговата глобална структура. Фракталите се поделени на геометриски, алгебарски, стохастички и системи на повторувачки функции. 29. Концептот на димензија и нејзино пресметување
Во секојдневниот живот постојано се среќаваме со димензии. Ја проценуваме должината на патот, ја дознаваме површината на станот итн. Овој концепт е доста интуитивен и, се чини, не бара појаснување. Правата има димензија 1. Тоа значи дека со избирање на референтна точка, можеме да дефинираме која било точка на оваа права користејќи 1 број - позитивен или негативен. Покрај тоа, ова се однесува на сите линии - круг, квадрат, парабола итн. Димензијата 2 значи дека можеме уникатно да дефинираме која било точка со два броја. Немојте да мислите дека дводимензионалното значи рамно. Површината на сферата е исто така дводимензионална (може да се дефинира со користење на две вредности - агли како ширина и должина). Ако го погледнеме од математичка гледна точка, тогаш димензијата се одредува на следниов начин: за еднодимензионални објекти, удвојувањето на нивната линеарна големина доведува до зголемување на големината (во овој случај, должина) за фактор два (2 ^ 1). За дводимензионални објекти, удвојувањето на линеарните димензии резултира со зголемување на големината (на пример, површината на правоаголник) за четири пати (2^2). За 3-димензионални објекти, удвојувањето на линеарните димензии доведува до осумкратно зголемување на волуменот (2^3) и така натаму. Геометриски фрактали Токму со овие фрактали започна историјата на развојот на фракталите воопшто. Овој тип на фрактал се добива преку едноставни геометриски конструкции. Обично, кога се конструираат геометриски фрактали, се користи следниов алгоритам: Примери на геометриски фрактали: крива Пеано, снегулка Кох, лист од папрат, триаголник Сиерпински, Алгебарски фрактали Фрактал- сложена геометриска фигура која има својство на самосличност, односно составена од неколку делови, од кои секој е сличен на целата фигура Алгебарските фрактали го добиле своето име затоа што се изградени врз основа на алгебарски функции. Алгебарските фрактали вклучуваат: множество Манделброт, множество Јулија, Њутнови басени, биоморфи. -Комплет Манделброт:Комплетот Манделброт првпат беше опишан во 1905 година од Пјер Фату. Фату ги проучувал рекурзивните процеси на формата Почнувајќи со точка на сложената рамнина, можете да добиете нови поени со последователна примена на оваа формула на нив. Таквата низа точки се нарекува орбита под трансформација Фату откри дека орбитата под оваа трансформација покажува доста сложено и интересно однесување. Има бесконечен број такви трансформации - по една за секоја вредност. (наречен Манделброт затоа што тој беше првиот што го изврши потребниот број на пресметки користејќи компјутер). -Сет Јулија: Јулија збир на рационално мапирање -Њутн базени:Регионите со фрактални граници се појавуваат кога корените на нелинеарната равенка се приближно пронајдени со Њутновиот алгоритам на сложена рамнина (за функција на реална променлива, Њутновиот метод често се нарекува тангентен метод, што, во овој случај, се генерализира на сложената рамнина). Да го примениме Њутновиот метод за да ја најдеме нулата на функција од сложена променлива користејќи ја постапката: Изборот на првично приближување е од особен интерес. Бидејќи функцијата може да има повеќе нули, а во различни случаи методот може да конвергира до различни вредности. -биоморфи:скратена форма на множеството Јулија, пресметана со формулата z=z 3 +c. Името го добила поради сличноста со едноклеточните организми. Стохастички фрактали Типичен претставник на овој тип на фрактал е таканаречената плазма. За да го конструирате, земете правоаголник и одредете боја за секој негов агол. Следно, пронајдете ја централната точка на правоаголникот и насликајте ја со боја еднаква на аритметичката средина на боите на аглите на правоаголникот + некој случаен број. Колку е поголем овој случаен број, толку повеќе ќе биде искинат цртежот. Природните предмети често имаат фрактална форма. За нивно моделирање може да се користат стохастички (случајни) фрактали. Примери на стохастички фрактали: траекторија на Брауново движење на рамнината и во вселената; граница на траекторијата на Брауновото движење на рамнина. Во 2001 година, Лолер, Шрам и Вернер ја докажаа хипотезата на Манделброт дека нејзината димензија е 4/3. Еволуциите на Schramm-Löwner се конформално непроменливи фрактални криви што се појавуваат во критичните дводимензионални модели на статистичката механика, на пример, Ising моделот и перколацијата. разни видови рандомизирани фрактали, односно фрактали добиени со рекурзивна процедура во која се воведува случаен параметар на секој чекор. Плазмата е пример за употреба на таков фрактал во компјутерската графика. Фрактален монотип, или стохатипија, е тренд во ликовната уметност што вклучува добивање слика на случаен фрактал. Поврзани информации. Што гледаш сега? Освен ако не сте од паралелен универзум каде што сите седат зад векторски монитори, тогаш ова е растерска слика. Погледнете ја оваа лента: /. Ако се приближите до мониторот, можете да видите пикселирани чекори кои се обидуваат да се преправаат дека се векторска линија. Има цел куп различни алгоритми за растеризација за оваа намена, но јас би сакал да зборувам за алгоритмот Брезенхам и алгоритмот Y, кои наоѓаат приближување на векторски сегмент во растерски координати. Наидов на проблемот на растеризација додека работев на процедурален генератор на градежни планови. Требаше да ги претставам ѕидовите на собата како ќелии од дводимензионална низа. Слични проблеми може да се сретнат при пресметките на физиката, алгоритмите за пронаоѓање патеки или пресметките на осветлувањето ако се користи поделба на просторот. Кој би помислил дека запознавањето со алгоритмите за растеризација еден ден би можело да ни се најде? Ова беше суштината на алгоритмот, во реалноста сè изгледа вака. Прво, се пресметува наклонот (y1 - y0)/(x1 - x0). Вредност на грешка на почетната точка на сегментот (0,0)
се зема еднакво на нула и се пополнува првата ќелија. На следниот чекор, наклонот се додава на грешката и неговата вредност се анализира доколку грешката е помала 0.5
, тогаш ќелијата е пополнета (x0+1, y0), ако повеќе, тогаш ќелијата е пополнета (x0+1, y0+1)а еден се одзема од вредноста на грешката. На сликата подолу, линијата пред растеризација е прикажана со жолта боја, а растојанието до најблиските ќелии е прикажано со зелена и црвена боја. Наклонот е еднаков на една шестина, на првиот чекор грешката станува еднаква на наклонот, што е помало 0.5
, што значи дека ординатата останува иста. Кон средината на линијата, грешката ја преминува линијата, се одзема една од неа, а новиот пиксел се крева повисоко. И така натаму до крајот на сегментот. Уште една нијанса. Ако проекцијата на сегмент на оската xпомала проекција на оската yили почетокот и крајот на сегментот се заменети, тогаш алгоритмот нема да работи. За да се спречи тоа да се случи, треба да ја проверите насоката на векторот и неговиот наклон, а потоа, доколку е потребно, да ги замените координатите на сегментот, да ги ротирате оските и, на крајот, да намалите сè на еден или барем два случаи. Главната работа не е да заборавите да ги вратите оските на нивното место додека цртате. За да ги оптимизирате пресметките, користете го трикот за множење на сите фракциони променливи со dx = (x1 - x0). Потоа на секој чекор грешката ќе се промени во dy = (y1 - y0)наместо наклонот и од страна dxнаместо еден. Можете исто така да ја промените логиката малку, да ја „поместите“ грешката така што границата е на нула и можете да го проверите знакот на грешката. Кодот за цртање растерска линија со помош на алгоритмот Брезенхам може да изгледа отприлика вака. Псевдокод од Википедија претворен во C#. void BresenhamLine(int x0, int y0, int x1, int y1) ( var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); // Проверете го растот на сегментот долж оската x и по должината на y-оската / / Одразете ја линијата дијагонално ако аголот на наклон е преголем ако (стрмен) ( Swap(ref x0, ref y0); // Мешањето на координатите е вклучено во посебна функција за убавина Swap(ref x1, ref y1 ) // Ако линијата не расте од лево кон десно, тогаш ги заменуваме почетокот и крајот на сегментот ако (x0 > x1) ( Swap(ref x0, ref x1); Swap(ref y0, ref y1 ) int dx = x1 - x0 int dy = Math.Abs (y1 - y0 int error = dx / 2) Ова користи оптимизација со множење со dx; y0< y1) ? 1: -1; // Выбираем направление роста координаты y
int y = y0;
for (int x = x0; x <= x1; x++)
{
DrawPoint(steep ? y: x, steep ? x: y); // Не забываем вернуть координаты на место
error -= dy;
if (error < 0)
{
y += ystep;
error += dx;
}
}
}
Пример код за цртање круг во C#. void BresenhamCircle (int x0, int y0, int радиус) ( int x = радиус; int y = 0; int радиус Грешка = 1 - x; додека (x >= y) ( DrawPoint (x + x0, y + y0); DrawPoint (y + x0, x + y0, DrawPoint (-x + x0, y + y0); y + x0, -x + y0 (x + x0, -y + y0) (y + x0, -x + y0);< 0)
{
radiusError += 2 * y + 1;
}
else
{
x--;
radiusError += 2 * (y - x + 1);
}
}
} На сликата погоре, црвените и зелените бои ги покажуваат растојанијата до два соседни пиксели. За да ја пресметате грешката, можете да користите променлива со подвижна запирка и да ја земете вредноста на грешката од фракциониот дел. Примерок код за мазната линија на Ву Ксиаолин во C#. приватна празнина WuLine (int x0, int y0, int x1, int y1) ( var стрмни = Math.Abs (y1 - y0) > Math.Abs (x1 - x0); ако (стрмни) ( Swap(ref x0, ref y0 Swap (ref x1, ref y1) if (x0 > x1) (Swap (ref x0, ref x1); Swap(ref y0, ref y1); / Оваа функција автоматски ги заменува координатите во зависност од променливата стрмна DrawPoint (стрмна, x1, y1, 1) // Последниот аргумент е интензитетот во фракции од еден float dx = x1 - x0; = dy / dx плови y = y0 + градиент за (var x = x0 + 1;<= x1 - 1; x++)
{
DrawPoint(steep, x, (int)y, 1 - (y - (int)y));
DrawPoint(steep, x, (int)y + 1, y - (int)y);
y += gradient;
}
}
Денес е тешко да се најде човек кој не наишол на компјутерска графика во една или друга форма. Ако некое лице почне да се интересира за алгоритмите што се во основата на него, тогаш алгоритмите на Брезенхем ќе бидат еден од првите. Единствената неволја е што сè уште не наидов на едноставен и разбирлив опис на овие алгоритми, а уште помалку имплементација. Во оваа статија, ќе се обидам да зборувам што е можно поедноставно за семејството на алгоритми Брезенхам, а исто така ќе дадам готов за употреба код во JavaScript, кој практично не се разликува од кодот во C/C++. Кодот може да се земе и да се искористи со тоа што прво ќе се напише писмо за благодарност до авторот. Значи, целта на алгоритмите на Брезенхам е да нацртаат линија на растерски уред, обично монитор. Како што можете да видите на слика 1, не сите пиксели вклучени во сликата на линијата лежат на оваа линија, односно задачата на алгоритмот е да ги пронајде најблиските пиксели. Главната предност на алгоритмот на Брезенхем е тоа што не користи скапа операција за множење во јамка. Алгоритмот е погоден за прави линии или криви од втор ред*. Постојат модификации на алгоритмот за четири поврзани (т.е. точките што се разликуваат за 1 во една координата се сметаат за соседни) и осум поврзани (т.е. точките се сметаат за соседни ако двете координати се разликуваат за не повеќе од 1) линии. Еве ја втората опција - посложена, но и давајќи подобар резултат. Главната идеја на алгоритмот е дека линијата што треба да се повлече ја дели рамнината на два дела. Равенката на кривата е напишана како Z = f (x,y) . Во сите точки на кривата Z = 0, во точките што лежат над кривата Z > 0 и во точките под кривата Z< 0 . Нам известны координаты начала отрезка, то есть точки,
заведомо лежащей на искомой кривой. Ставим туда первый пиксель и принимаем
Z = 0 . От текущего пикселя можно сделать два шага — либо
по вертикали (по горизонтали), либо по диагонали на один пиксель. Конкретные
направления шагов выбираются в зависимости от типа линии, которую надо нарисовать.
Делая шаг, мы мы вычисляем, как изменятся значение Z: ΔZ = Z" x Δx + Z" y Δy На еден од можните чекори Z се зголемува, на другиот се намалува. Секој чекор е избран така што вредноста Z за новиот пиксел е што е можно поблиску до 0 Така, ќе се движиме по линијата, создавајќи ја неговата слика. Веднаш да се согласиме дека алгоритмот за права линија не црта хоризонтални и вертикални линии. Тоа е затоа што цртањето такви линии може да се имплементира на многу поедноставен начин, често на ниво на BIOS-от или возачот. Останатите сегменти се поделени во две групи: хоризонтална и вертикална. Ако ја претставиме равенката на права линија во форма y = kx, тогаш отсечките за кои |k| ≤ 1, и вертикални - за кои |k| > 1. Со доделување отсечка на една од групите, можеме да ги замениме координатите на краевите така што хоризонталните отсечки секогаш се цртаат од лево кон десно, а вертикалните отсечки секогаш се цртаат од врвот до дното. За хоризонталните сегменти, секој нов пиксел ќе биде 1 десно од претходниот, а може да биде и повисок (понизок), т.е. можни се два чекори - десно и десно дијагонално. За вертикалните сегменти, можните чекори се надолу и надолу дијагонално. Ако координатите на краевите на отсечката се (x 1 ,y 1) и (x 2 ,y 2), соодветно, тогаш со секој чекор долж оската x Z се менува за 1, а долж оската y - за (x 2 -x 1)/(y 2 -y 1) . За да не се занимаваме со делење и да останеме во границите на аритметиката на цели броеви, ќе ја промениме променливата Z во y2-y1 и x2-x1, соодветно. Тоа е целата математика, другото може да се разбере од кодот. Алгоритмот за цртање лак ќе остане надвор од опсегот на статијата, но алгоритмот за цртање круг се покажа како многу поедноставен отколку за права линија. Ова се должи на многу причини. Прво, цртаме само една осмина од кругот - од π/2 до π/4, а во спротивна насока, односно во насока на стрелките на часовникот. Остатокот од кругот се добива со рефлексија на овој дел во однос на центарот на кругот, хоризонталната и вертикалната оска, како и правите линии y = x + b и y = -x + b кои минуваат низ центарот на кругот . Второ, поради симетријата, отстапувањата на права од круг не се толку забележливи како отстапувањата од права линија, така што Z може да се спореди со нула без да се пресмета максимално дозволеното отстапување. Валидните чекори се правилни и десно-дијагонални, а промената на Z зависи од вредностите на x и y, но врската е линеарна, така што не е потребна операција за множење. Тоа е се, всушност. Подолу ќе најдете скрипта што ја демонстрира работата на опишаните алгоритми, а за да разберете како функционира, само погледнете го изворниот текст на страницата. Со среќа! Ако сакате да видите демонстрација на алгоритмите во прозорецот на вашиот прелистувач, ве молиме овозможете JavaScript!
промена: булова;
започне
x:=x1; y:=y1;
dx:=abs(x2-x1); dy:=abs(y2-y1);
sx:=знак (x2-x1); sy:=знак (y2-y1);
e:= 2*dy-dx;
ако ди
друго започне
z:=dx;
dx:=dy; dy:=z;
промена:=точно
крај;
за i:=1 до dx+dy почнуваат
ако ди< dx then begin
ако се промени тогаш y:=y+sy
друго x:=x+sx;
e:=e+2*dy;
крај на друго место
ако се промени тогаш x:=x+sx
друго y:=y+sy;
e:=e-2*dx
крај;
Form1.Canvas.Pixels:=clblack; // излез точка, на пример
крај;
Првите идеи за фракталната геометрија се појавија во 19 век. Кантор, користејќи едноставна рекурзивна процедура, ја претвори линијата во збирка од неповрзани точки, кои подоцна беа наречени „Кантор прашина“. Тој ќе земе линија и ќе ја отстрани централната третина, а потоа ќе го повтори истото со останатите делови. Пеано повлече посебен вид линија. За да го нацрта, Пеано го користел следниов алгоритам:
Тој зеде права линија и ја замени со сегменти три пати пократки од првобитната линија. Потоа го повтори истото дејство со секој од сегментите. Неговата уникатност е во тоа што ја исполнува целата рамнина, т.е. за секоја точка лоцирана на рамнината, можете да најдете точка што припаѓа на линијата Пеано.
Се смета за основач на фракталната геометрија Беноа Манделброт. Манделброт го воведе концептот на „фрактал“.
Ориз. Снегулка Кох
Ориз. Лист
Ориз. Сиерпински триаголник
- збир на точки, динамиката во чија близина е, во одредена смисла, нестабилна во однос на малите пертурбации на почетната положба. Ако ѓ- полином, сметаме и пополнето множество Јулија - збир на точки што не тежат кон бесконечност. Вообичаениот сет на Јулија е нејзината граница.
Принципот на работа на алгоритмот на Брезенхем е многу едноставен. Земете отсечка и нејзината почетна координата x. На x во циклусот додаваме еден по еден кон крајот на сегментот. На секој чекор се пресметува грешката - растојанието помеѓу реалната координата yна оваа локација и најблиската мрежна ќелија. Ако грешката не надминува половина од висината на ќелијата, тогаш таа е пополнета. Тоа е целиот алгоритам.
Алгоритмот на Брезенхем има модификација за цртање кругови. Таму сè работи на сличен принцип, на некој начин и поедноставно. Пресметката е направена за еден октант, а сите останати делови од кругот се нацртани според симетрија.
Сега за алгоритмот на Ву Ксијаолин за цртање мазни линии. Се разликува по тоа што на секој чекор се врши пресметка за двата пиксели најблиску до линијата и тие се обоени со различен интензитет, во зависност од растојанието. Точно преминувањето на средината на пиксел дава 100% интензитет, ако пикселот е оддалечен 0,9 пиксели, тогаш интензитетот ќе биде 10%. Со други зборови, сто проценти од интензитетот е поделен помеѓу пикселите што ја ограничуваат векторската линија на двете страни. 
Ако некогаш се најдете дека работите со мрежи во иднина, размислете за момент, можеби повторно го измислувате тркалото и всушност работите со пиксели, иако не го знаете тоа. Модификациите на овие алгоритми може да се користат во игрите за пребарување на ќелии пред единица на картата, пресметување на површината на ударот на снимката или убаво уредување на предметите. Или едноставно можете да нацртате линии, како во програмата од линковите подолу. Би сакал да ги изразам моите длабоки и искрени чувства кон развивачите на www стандардите и оние кои ги спроведуваат. Варијанта на JavaScript код што работи во сите достапни прелистувачи, т.е. IE 6.0, NN 7.0 и Opera 6.0x не се одликуваат со нивната убавина и софистицираност. Сепак, „ова нема никаква врска со науката што јас моментално ја застапувам“.
Цртање отсечка
Цртање круг
x1: y1:
x2: y2:
x0: y0:
Р: