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

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

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

Отсечка

Най-често се налага изобразяването на отсечки върху растера2. Ще разгледаме алгоритъма на Брезенхам (на английски Bresenham). Като за начало да видим какво точно ще правим:
bresenham1
Ако си представим отсечката като безкрайно тънка линия, която минава през 2 точки от екрана, то трябва да 'светнем' квадратчетата (пикселите), през които тази отсечка минава. За удобство ще приемем, че отсечката върви от югозапад (долу-ляво) до североизток (горе-дясно) и ъгълът, който тя сключва със $\overrightarrow{Ox}$, e по-малък от 45 градуса (т.е отсечката е по-"легнала"). Всички останали случаи са еквивалентни на този с подходяща ротация на координатната система. :)

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

bresenham_next

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

bresenham_err
бре
Имаме дадени 2та края на отсечката - нека това са $(x_1, y_1), (x_2, y_2)$. Тогава $\Delta x = x2 - x1, \Delta y = y2 - y1$. Нека за улеснение приемем, че $\Delta x \ge \Delta y$, т.е линията има по-малък наклон от $\frac{\pi}{4}$. Ако си отбележим наклона с $\alpha$, то $\tg \alpha = \frac{\Delta y}{\Delta x} = m$. Това е първата много важна характеристика на линията (за единица дължина по $x$, колко пиксела нагоре (по $y$) се изкачва линията).

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

  • Във всеки момент се знае кой е текущият пиксел, в който се намираме - $x_c, y_c$ както и стойността на текущата грешка - $e$, т.е колко далече минава истинската линия от квадратчето. Ще приемем, че координатите на квадратчето са координатите на долния му десен ъгъл и ще се интересуваме повече от самото ъгълче, отколкото от целия квадрат.
  • От всеки пиксел можем да се движим или надясно (т.е увеличаваме $x$) или по диагонал (т.е увеличаваме $x$ и $y$). Това зависи от грешката - тя се изчислява като към старата грешка прибавим $m$. Т.е $e_{new} = e_{old} + m$. Тъй като грешката е разстоянието от долния десен ъгъл на пиксела до пресечната точка на истинската отсечка с вертикалната права, минаваща над този долен десен ъгъл (на картинката отбелязано със синьо), то за да получим следващата грешка прибавяме точно разстоянието, което отсечката ще "изкачи" за един пиксел. Тъй като искаме точката (долния десен ъгъл) да бъде най-близо до пресечната точка на отсечката с вертикалната права, то ако грешката е повече от $\frac{1}{2}$, избираме горната точка, иначе - долната.
моментни стойности $x_c, y_c, e$
пресмятаме новата грешка $e \mbox{ += } m$
движим се нагоре, ако грешката е повече от $\frac{1}{2}$ $\mbox{if (}} e > \frac{1}{2} \mbox{) \{} \mbox{++}y_c\mbox{; } e \mbox{ -= } 1\mbox{;} \mbox{\}}$
движим се напред (винаги) $\mbox{++}x_c$

Окръжност

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

  • центъра и е в $(0, 0)$ (в общия случай трябва да транслираме)
  • има целочислен радиус
  • изчертаваме само частта, която е разположена в първи квадрант (останалите са симетрични)
bresenham_circ_simple

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

bresenham_circ_cases2.bmp

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

(1)
\begin{equation} k(x, y) = x ^ 2 + y ^ 2 - R ^ 2 \end{equation}
$k(x, y) > 0$ точката е извън окръжността
$k(x, y) = 0$ точката е върху окръжността
$k(x, y) < 0$ точката е вътрешна за окръжността

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

(2)
\begin{align} \Delta = k(x+1, y-1) = (x+1)^2 + (y-1)^2 - R^2 \end{align}

Очевидно:

$\Delta < 0$ точката по диагонала е вътрешна за окръжността намираме се в случай 1 или случай 2
$\Delta = 0$ точката по диагонала е върху окръжността новата точка е по диагонал - няма нужда от разглеждане на случаи
$\Delta > 0$ точката по диагонала е извън окръжността намираме се в случай 3 или случай 4

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

(3)
\begin{align} |k(x+1, y-1)| \lesseqqgtr |k(x+1, y)| \iff \delta = |k(x+1, y)| - |k(x+1, y-1)| \lesseqqgtr 0 \end{align}

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

(4)
\begin{eqnarray} \delta &=& |\underbrace{k(x+1, y)}_{> 0}| - |\underbrace{k(x+1, y-1)}_{< 0}| \\ &=& k(x+1, y) - (- k(x+1, y-1)) \\ &=& (x+1) ^ 2 + y ^ 2 - R^2 + (x+1)^2 + (y-1) ^ 2 - R^2 \\ &=& (x+1)^2 + y^2 \underbrace{- 2y + 1} - R^2 + (x+1)^2 + (y-1) ^ 2 - R^2 \underbrace{+ 2y - 1}\\ &=& 2\Big[ (x+1)^2 + (y-1) ^ 2 - R^2 \Big] + 2y - 1 \\ &=& 2\Delta + 2y - 1 \\ &=& 2(\Delta + y) - 1 \end{eqnarray}

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

$\delta > 0$ разстоянието до окръжността на горната точка е по-голямо избираме диагоналната $(x+1, y-1)$
$\delta \le 0$ разстоянието до окръжността на долната точка е по-голямо (или са равни) избираме хоризонталната (т.е дясната) $(x+1, y)$

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

(5)
\begin{eqnarray} k(x+1, y) &\le& 0 \\ &\iff& \\ (x+1) ^ 2 + y^2 - R^2 &\le& 0 \\ (x+1) ^2 + y^2 -2y + 1 - R^2 + 2y - 1 &\le& 0 \\ (x+1)^2 + (y-1) ^ 2 - R^2 + 2y - 1 &\le& 0 \\ \Delta + 2y - 1 &\le& 0 \\ 2(\Delta + y) - 1 &\le& \Delta < 0 \\ \delta < 0 \\ \end{eqnarray}

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

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

$\Delta < 0$
$\delta = 2(\Delta + y) - 1$
$\delta > 0$ $(x+1, y-1)$ $\Delta' = \Delta + 2(x- y) + 1$
$\delta \le 0$ $(x+1, y)$ $\Delta' = \Delta -2y + 1$
$\Delta > 0$
$\delta = 2(\Delta - x) - 1$
$\delta \le 0$ $(x+1, y-1)$ $\Delta' = \Delta + 2(x- y) + 1$
$\delta > 0$ $(x, y-1)$ $\Delta' = \Delta +2x + 1$
$\Delta = 0$
$\delta \le 0$ $(x+1, y-1)$ $\Delta' = \Delta + 2(x- y) + 1$

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

Елипса

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

  • елипсата има център $(0, 0)$ и осите и са успоредни на координатните (т.е така би изглеждала след канонизация)
  • дължините на диаметрите й са реални числа
  • ще начертаем само частта и в първи квадрант
(6)
\begin{align} \frac{x^2}{a^2} + \frac{y^2}{b^2} = 1 \quad a, b > 0 \end{align}

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

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

Ако в момента се намираме в $(x, y)$, то следващата точка е или $(x, y+1)$ (нагоре) или $(x-1, y+1)$ (по диагонал). За да решим коя от 2те ще изберем, ще проверим положението на средната точка $(x - \frac{1}{2}, y+1)$ спрямо елипсата. Просто ще заместим в уравнението на елипсата:

(7)
\begin{align} \frac{x^2}{a^2} + \frac{y^2}{b^2} = 1 \iff f(x, y) = b^2x^2 + a^2y^2 - a^2b^2 = 0 \end{align}
(8)
\begin{align} f(x-\frac{1}{2}, y+1) \lesseqqgtr 0 \end{align}
$f(x-\frac{1}{2}, y+1) \le 0$ средната точка е вътре или по контура движим се към $(x, y+1)$
$f(x-\frac{1}{2}, y+1) > 0$ средната точка е вън движим се към $(x-1, y+1)$

След като тангенсът на допирателната стане по-малък от -1 (в началото е $-\infty$ при ъгъл $\frac{\pi}{2}$ (защото е вертикална), накрая е $0$ при ъгъл $\pi$ (защото е хоризонтална)), трябва да разгледаме новата средна точка $(x-1, y+\frac{1}{2})$:

van_aken_elipse_case2
$f(x-1, y+\frac{1}{2}) \le 0$ средната точка е вътре или по контура движим се към $(x-1, y+1)$
$f(x-1, y+\frac{1}{2}) > 0$ средната точка е вън движим се към $(x-1, y)$

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

(9)
\begin{align} \frac{dy}{dx} = -\frac{b^2x}{a^2y} \lessgtr -1 \end{align}

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

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