Лекциите на ФМИ

За да изглеждаме умни пред другите

Начало

Начална страница

Членове на
сайта

Присъедини
се

За автори

Препоръки за писане на
статии

Формат на статиите

Форум

Новини от
форума

Последни
промени

Списък със
задачи

Първи курс

Анализ

ЕАИ

Геометрия

ООП

Втори курс

Структури от Данни

Компютърни Архитектури

КАрх - Практикум

Основи на компютърната
графика

Функционално програмиране

ФП - Практикум

Трети курс

Логическо програмиранеУпражнения

Числени методиУпражнения

Системно
програмиранеУпражнения

Мрежово
програмиранеУпражнения

За
администратори

Create account or Sign in

Начало

Начална страница

Членове на сайта

Присъедини се

За автори

Препоръки за писане на
статии

Формат на статиите

Последни
промени

Панел за
администратори

Лекции

Първи Курс

Анализ

ЕАИ

Геометрия

ООП

Втори курс

Структури от Данни

Компютърни Архитектури

КАрх - Практикум

Основи на компютърната
графика

Функционално програмиране

ФП - Практикум

Трети курс

Логическо програмиранеУпражнения

Числени методиУпражнения

Системно
програмиранеУпражнения

Мрежово
програмиранеУпражнения

Избираеми дисциплини

Математическа Логика

Дискретна Оптимизация

Теория на Множествата

Теория на Графите

Избрани Глави от
Анализа

ФМИ за начинаещи
» Основи на компютърната графика » Okg6

Дискретно изчертаване на основни примитиви – отсечка, окръжност,
елипса

foldunfold

Table of Contents

Растеризация

Отсечка

Окръжност

Елипса

Растеризация

Често се налага да се изчертават на екрана основни геометрични обекти като
отсечки, части от окръжност/елипса. Както знаете обаче мониторът е правоъгълна
таблица от пиксели, като всеки пиксел свети в определен цвят. Естествено
възниква проблемът за изчертаване на отсечка/окръжност със зададени
координати1 върху тази правоъгълна таблица. Т.е трябва да
определим кои точно пиксели трябва да светят и евентуално колко силно. Проблемът
не е сложен за решаване, но бързодействието е от изключително голяма важност. В
тази глава ще разгледаме основните алгоритми за растеризация на отсечка,
окръжност и елипса.

Отсечка

Най-често се налага изобразяването на отсечки върху растера2. Ще разгледаме алгоритъма на Брезенхам (на
английски Bresenham). Като за начало да видим какво точно ще правим:

Ако
си представим отсечката като безкрайно тънка линия, която минава през 2 точки от
екрана, то трябва да 'светнем' квадратчетата (пикселите) през които тази отсечка
минава. За удобство ще приемем, че отсечката върви от югозапад (долу-ляво) до
североизток (горе-дясно) и ъгъла който тя сключва със
e по-малък от 45 градуса (т.е отсечката е по-"легнала"). Всички останали случай
са еквивалентни на този с подходящо ротиране на координатната система. :)

С тези ограничения задачата ни става наистина много лесна - ако си
представим, че в момента сме в даден пиксел и се чудим в кой следващ пиксел да
отидем имаме само 2 възможности - надясно или по диагонал нагоре и
надясно:

На всяка стъпка от алгоритъма, трябва да знаем текущото квадратче,
което сме светнали както и грешката, която показва колко далеч е минала
линията от квадратчето. За център на квадратчето ще приемем долния му ляв ъгъл.
Ще разглеждаме също пресечните точки на линията (отсечката) с вертикалните линии
на решетката. Спрямо тези точно пресечни точки (отбелязани с червено на
фигурата) избираме най-близката точка от решетката по тази вертикална линия (т.е
най близкия долен ляв ъгъл на квадрат със същия )
- на фигурата е отбелязано с лилаво мерниче. След като изберем долните леви ъгли
просто светваме съответните им квадратчета (т.е квадратчето, което стои горе
вдясно спрямо точката).

бре
Имаме
дадени 2та края на отсечката - нека това са .
Тогава .
Нека за улеснение приемем, че ,
т.е линията има по-малък наклон от .
Ако си отбележим наклона с ,
то .
Това е първата много важна характеристика на линията (за единица дължина по ,
колко пиксела нагоре (по )
се изкачва линията).

Алгоритъм на Брезенхам:

Във всеки момент се знае кой е текущият пиксел, в който се намираме -
както и стойността на текущата грешка - ,
т.е колко далече минава истинската линия от квадратчето. Ще приемем, че
координатите на квадратчето са координатите на долния му
десен ъгъл и ще се интересуваме повече от самото ъгълче, отколкото от
целия квадрат.

От всеки пиксел можем да се движим или надясно (т.е увеличаваме )
или по диагонал (т.е увеличаваме
и ).
Това зависи от грешката - тя се изчислява като към старата грешка прибавим
.
Т.е .
Тъй като грешката е разстоянието от долния десен ъгъл на пиксела до пресечната
точка на истинската отсечка с вертикалната права, минаваща над този долен
десен ъгъл (на картинката отбелязано със синьо), то за да получим следващата
грешка прибавяме точно разстоянието, което отсечката ще "изкачи" за един
пиксел. Тъй като искаме точката (долния десен ъгъл) да бъде най-близо до
пресечната точка на отсечката с вертикалната права, то ако грешката е повече
от ,
избираме горната точка, иначе - долната.

моментни стойности

пресмятаме новата грешка

движим се нагоре, ако грешката е повече от

движим се напред (винаги)

Окръжност

Сега ще разгледаме подробно алгоритъма за растеризиране на окръжност. За
удобство ще приемем за изчертаваната окръжност:

центъра и е в
(в общия случай трябва да транслираме)

има целочислен радиус

изчертаваме само частта, която е разположена в първи квадрант (останалите
са симетрични)

Както при алгоритъма за отсечка, ще приемем, че пиксела се отъждествява с
долния си ляв ъгъл. Също така по текущ пиксел в който се
намираме ,
ще видим как да стигнем до следващия. В случая на окръжност, ако изчертаваме
само първи квадрант имаме следните 3 случая: надясно (по хоризонтала), надолу и
надясно (по диагонал), на долу (по вертикала):

Ще разгледаме случай 1 и 2, останалите два са им симетрични. Основното, което
ще използваме, е разстояние от точка до окръжност, което се свежда до разстояние
между 2 точки (самата точка и центъра на окръжността). Нека с функцията
означим това разстояние. Тогава:
(1)

точката е извън окръжността

точката е върху окръжността

точката е вътрешна за окръжността

Първо трябва да разберем дали сме в първите два случая (1 и 2) или във
вторите два случая (3 и 4). За тази цел просто ще определим разположението на
точката по диагонала (с координати )
спрямо окръжността - т.е дали тя е външна или вътрешна. Да положим на
разстоянието от диагоналната точка до центъра на окръжността:
(2)

Очевидно:

точката по диагонала е вътрешна за окръжността

намираме се в случай 1 или случай 2

точката по диагонала е върху окръжността

новата точка е по диагонал - няма нужда от разглеждане на случаи

точката по диагонала е извън окръжността

намираме се в случай 3 или случай 4

Да разгледаме подробно случай 1 (окръжността минава между
точките с координати
и
(т.е между дясната и диагоналната спрямо текущата). За да разберем коя от
2те точки трябва да светнем, трябва да проверим до коя точка модула
от разстоянието до окръжността е минимално - т.е да изберем по-близката до
окръжността точка. С други думи трябва да сравним:
(3)

Понеже сме в първи случай, знаем че точката
е извън окръжността, а точката
е в окръжността, следователно знаем знаците на изразите в модулите. Да махнем
модула и да разпишем:
(4)

Сега да видим какво става според знака на :

разстоянието до окръжността на горната точка е по-голямо

избираме диагоналната

разстоянието до окръжността на долната точка е по-голямо (или са
равни)

избираме хоризонталната (т.е дясната)

С това случай 1 е завършен.
Да разгледаме случай 2:
По
принцип може да направим абсолютно същите разсъждения като в предния случай -
това обаче не е необходимо. В случай 2 и диагоналната и дясната точка са в
окръжността и очевидно дясната е по-близо, т.е в този случай избираме дясната.
Сега ще проверим следното: когато сме в случай 2, ,
т.е стойността, която сметнахме за случай 1 ще важи и тук (т.е няма нужда даже
да проверяваме дали сме в този случай - просто разписваме
все едно сме в случай 1 и използваме резултата).
Във втори случай сме когато
дясната точка е в окръжността:
(5)

Т.е получихме, че когато сме във 2ри случай, то сметнатото
от първи случай е винаги отрицателно. Но това означава че ако просто бяхме
забравили за 2ри случай и приемем че има само първи, ако
получим
пак ще вземем хоризонталната дясна точка - т.е ще направим правилен избор. Ето
защо 1ви и 2ри случай се изчерпват с разглеждането
на таблицата, показана в 1ви случай.

Както казахме 3ти и 4ти случай са напълно аналогични на
разгледаните до сега. Ще запишем в таблица всички случай за улеснение:

е просто новата стойност на .
Така си спестявате малко умножения :)

Елипса

Остана да разлгедаме и алгоритъма на Бреззенхам за растеризация на елипса. Ще
приемем че:

елипсата има център
и осите и са успоредни на координатните (т.е така би изглеждала след
канонизация)

дължините на диаметрите й са реални числа

ще начертаем само частта и в първи квадрант

(6)

Сега да погледнем какво трябва да се получи:

Ще чертаем само в първи квадрант отдолу нагоре. При тези условия ако в даден
момент се намираме в клетка
имаме 3 възможни случая - нагоре, наляво и по диагонал (горе-ляво). В началото
елипсата ще се движи по-скоро нагоре (т.е следващият пиксел ще е или над текущия
или по диагонал), а след един точно определен момент (този, в който
допирателната към елипсата сключва ъгъл 135 (= 180 - 45) градуса с )
- наляво. Преди и след този специален момент, алгоритъмът върви по подобен
начин. Първо ще разгледаме ъгъл на допирателната по-малък от 135 градуса:

Ако в момента се намираме в ,
то следващата точка е или
(нагоре) или
(по диагонал). За да решим коя от 2те ще изберем, ще проверим
положението на средната точка
спрямо елипсата. Просто ще заместим в уравнението на елипсата:
(7)

(8)

средната точка е вътре или по контура

движим се към

средната точка е вън

движим се към

След като тангенсът на допирателната стане по-малък от -1 (в началото е
при ъгъл
(защото е вертикална), накрая е
при ъгъл
(защото е хоризонтална)), трябва да разгледаме новата средна точка :

средната точка е вътре или по контура

движим се към

средната точка е вън

движим се към

Единствено остава да изясним преминаването от случай 1 към случай 2.
Производната спрямо
на функцията
е точно:
(9)

Заместваме със
и получаваме производната. После естествено я сравняваме с
Забележка:
Как да получите формулата за производната? П просто разписвате спрямо
или пък правите пълен диференциал на функцията. Как точно? Има статии по анализ
:)

Footnotes

1. за отсечка това са координатите на 2та и
края, за окръжност - центъра и радиуса; разбира се, има и други варианти

2. растер се нарича правоъгълната матрица от
пиксели

page_revision: 33, last_edited: 1229115067|%e %b %Y, %H:%M %Z (%O ago)

EditRate
(+1)Tagsdiscuss (0) History Files Print
Site tools+ Options

Edit sections Append Edit meta Watchers Backlinks Page source Parent Lock
page Rename Delete

Help | Terms
of Service | Privacy | Report a bug | Flag as objectionable
Powered by Wikidot.com

Unless otherwise stated, the content of
this page is licensed under Creative
Commons Attribution-NonCommercial-ShareAlike 3.0 License

Click here to edit contents of this page.

Click here to toggle editing of individual
sections of the page (if possible). Watch headings for an "edit" link when
available.

Append content without editing the whole
page source.

Check out how this page has evolved in the past.

If you want to discuss contents of this page -
this is the easiest way to do it.

View and manage file attachments for this page.

A few useful tools to manage this Site.

See pages that link to and include this page.

Change the name (also URL address, possibly
the category) of the page.

View wiki source for this page without
editing.

View/set parent page (used for creating
breadcrumbs and structured layout).

Notify administrators if there is
objectionable content in this page.

Something does not work as expected? Find out
what you can do.

General Wikidot.com documentation and help
section.

Wikidot.com Terms of Service - what you can,
what you should not etc.

Wikidot.com Privacy Policy.