1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n  J

Тъй като светлинният импулс на луминофора намалява много бързо с времето, образът се нуждае от непрекъснато прерисуване, дори когато е статичен. За да се постигне илюзията на постоянен образ, честотата на опресняване трябва да е най-малко 60 Hz.

В зависимост от начина на регенерация на образа дисплеите се делят на два вида – векторни и растерни. Ние ще разглеждаме цветни растерни дисплеи. При тях във всеки един момент изображението представлява една правоъгълна матрица от пиксели. С всеки пиксел се свързват (обикновено) 24 бита – по

3 бита за всяка от основните цветови компоненти на пиксела.

По този начин се осигуряват над 16000000 цветове. Основни характеристики на тези дисплеи са броят на пикселите (размерите на матрицата, например 800/600, 1024/768) и гъстотата на пикселите (броят на пикселите, които се събират в един инч, варира от 72 до 130).

Така при растерните дисплеи възниква необходимостта от създаването на ефективни алгоритми за растеризация на отсечки и криви линии, т.е. за преобразуване на криви и отсечки в растерен формат. Когато е дадена една отсечка (например, чрез двата си края) или крива (например, чрез уравнението си), за да се изчертае тя, трябва да се определи кои пиксели на дисплея да се оцветят, така че да се да се получи достатъчно близка апроксимация на отсечката или кривата.

Обикновено на всеки пиксел се съпоставя двойка координати – номера на стълба x и номера на реда y на пиксела. За начало на координатната система се счита горният ляв ъгъл, така че като се придвижваме надясно x нараства, а като се придвижваме надолу y нараства.
При всички алгоритми за растеризиране на отсечка, считаме, че отсечката е зададена с двата си края (X1, Y1) и (X2, Y2), където координатите са с цели числа. Целта на тези алгоритми е да се оцветят подходящи пиксели, така че да се създаде илюзията, че на екрана е начертана отсечката с начало в пиксела с координати X1 и Y1 и край в пиксела с координати X2 и Y2.
Първо разглеждаме алгоритъма на Брезенхем за растеризиране на отсечка. Първо изчисляваме наклонът на отсечката.
Той е m = dY/dX, където dY = Y2 – Y1, dX = X2 – X1 и уравнението на правата, определена от отсечката е y = m.x + b, където

b = Y2 – m.X2. Ще считаме, че за наклона m е изпълнено -1  m  1. Ако това не е така, извършваме симетрия относно правата y = x и след това при изчертаване просто променяме ролите на двете координати.

Също така, ще считаме, че dX > 0. Ако това не е така, просто разменяме краищата на отсечката (при тази размяна наклонът m не се променя). Ще отбележим, че dX  0 – това е осигурено от първото съображение.

Така след тези две предварителни съображения, (X1, Y1) е левият край и (X2, Y2) е десният край на отсечката. Също, тъй като

|m|  1, във всеки стълб между X1 и X2 (за всяка фиксирана първа координата между X1 и X2) трябва да се оцвети точно един пиксел. Първият оцветен пиксел е (x₀, y₀) = (X1, Y1).

Нека (x_i, y_i) е i-тият оцветен пиксел. Отсечката пресича стълба

x_i + 1 при y = m.(x_i + 1) + b. При това, i-тият оцветен пиксел ще е така избран, че y_i  m.(x_i + 1) + b  y_i + 1, ако dY е неотрицателно и

y_i – 1  m.(x_i + 1) + b  y_i, ако dY е отрицателно. Сега трябва да изберем (i+1)-ият пиксел за оцветяване. Ако dY е неотрицателно, той ще е един от двата пиксела (x_i + 1, y_i) и (x₁ + 1, y_i + 1). Ако dY е отрицателно, той ще е един от двата пиксела (x_i + 1, y_i) и

(x_i + 1, y_i – 1). И в двата случая, кой точно пиксел да се избере се определя от това кой е по-близо до пресечната точка на отсечката със стълба x_i + 1.

При dY  0, разстоянието от (x_i + 1, y_i) до (x_i + 1, m.(x_i + 1) + b) е

t = m.(x_i + 1) + b – y_i, а разстоянието от (x_i + 1, y_i +1) до

(x_i + 1, m.(x_i + 1) + b) е s = 1 – t = y_i + 1 – m.(x_i + 1) – b.

Така t – s = m.(x_i + 1) + b – y_i – (y_i + 1 – m.(x_i + 1) – b) =

= 2.m.(x_i + 1) + 2.b – 2.y_i – 1. Умножаваме полученото равенство

с dX и получаваме dX.(t – s) = 2.dY.(x_i + 1) + 2.dX.b – 2.dX.y_i – dX.

Така знакът на t – s съвпада със знака на числото

d_i = 2.dY.(x_i + 1) + 2.dX.b – 2.dX.y_i – dX.

Ако d_i > 0, тогава избираме (x_i+1, y_i+1) = (x_i + 1, y_i + 1).

Ако d_i  0, тогава избираме (x_i+1, y_i+1) = (x_i + 1, y_i).

При dY < 0, разсъжденията са аналогични: тогава

d_i = - 2.dY.(x_i + 1) – 2.dX.b + 2.dX.y_i – dX и

ако d_i > 0, избираме (x_i+1, y_i+1) = (x_i+1, y_i+1) = (x_i + 1, y_i – 1),

ако d_i  0, тогава избираме (x_i+1, y_i+1) = (x_i + 1, y_i).

За по-лесно изчисляване да съобразим следното:

d₀ = 2.dY.(X1 + 1) + 2.dX.b – 2.dX.Y1 – dX = 2.dY – dX, ако dY  0,

d₀ = - 2.dY – dX, ако dY < 0. Двата случая можем да обединим така:

d₀ = 2.abs (dY) – dX.

След това, при dY  0, d_i+1 = 2.dY.(x_i+1 + 1) + 2.dX.b – 2.dX.y_i+1 – dX 

 d_i+1 – d_i = 2.dY.(x_i+1 – x_i) – 2.dX.(y_i+1 – y_i).

При dY < 0, d_i+1 = - 2.dY.(x_i+1 + 1) – 2.dX.b + 2.dX.y_i+1 – dX 

 d_i+1 – d_i = - 2.dY.(x_i+1 – x_i) + 2.dX.(y_i+1 – y_i).

Двата случая можем да обединим така:

ако d_i > 0, d_i+1 = d_i + 2.abs (dY) – 2.dX,

ако d_i  0, d_i+1 = d_i + 2.abs (dY).

Вход: (X1, Y1), (X2, Y2).

1. Ако abs (X2 – X1) < abs (Y2 – Y1), тогава

разменяме X1, Y1 и X2, Y2 и rev = 1, иначе rev = 0; към 2.

2. Ако X2 < X1, тогава разменяме X1, X2 и Y1, Y2; към 3.

3. dY = Y2 – Y1, dX = X2 – X1; към 4.

4. d₀ = 2.abs (dY) – dX, x₀ = X1, y₀ = Y1, i = 0; към 5.

5. Ако dY  0, incY = 1, иначе incY = -1; към 6.

6. Ако rev = 0, чертаем (x_i, y_i), иначе чертаем (y_i, x_i); към 7.

7. Ако x_i < X2, към 8., иначе към 10.

8. Ако d_i > 0, тогава d_i+1 = d_i + 2.abs (dY) – 2.dX, x_i+1 = x_i + 1,

y_i+1 = y_i + incY, иначе d_i+1 = d_i + 2.abs (dY), x_i+1 = x_i +1, y_i+1 = y_i; към 9.

9. i = i+1; към 6.

10. Край.

Така можем да считаме, че за наклона m имаме – 1  m  1 и освен това, че dX > 0. Правата, която е определена от точките (X1, Y1) и (X2, Y2) има уравнение F (x, y) = dY.x – dX.y + C = 0, където

C = dX.Y1 – dY.X1. Тази права определя две полуравнини: за всички точки (x, y) над правата е изпълнено F (x, y) < 0 и за всички точки (x, y) под правата е изпълнено F (x, y) > 0.
Първият оцветен пиксел е (x₀, y₀) = (X1, Y1).

Нека (x_i, y_i) е i-тият оцветен пиксел. Трябва да изберем (i+1)-ият пиксел за оцветяване. Както при Брезенхем, ако dY е неотрицателно, той ще е един от двата пиксела (x_i + 1, y_i) и

(x₁ + 1, y_i + 1). Ако dY е отрицателно, той ще е един от двата пиксела (x_i + 1, y_i) и (x_i + 1, y_i – 1). Тук обаче, изборът кой точно пиксел да се избере се определя по друг начин.

Ако dY  0, нека M_i е средата на отсечката (x_i + 1, y_i) (x_i + 1, y_i + 1),

ако dY < 0, нека M_i е средата на отсечката (x_i + 1, y_i) (x_i + 1, y_i – 1).

Изчисляваме d_i = F (M_i) и определяме в коя полуравнина се намира точката M_i относно правата и по този начин определяме кой от двата пиксела да изберем (естествено, този който лежи в противоположната полуравнина).

При dY  0, d_i = F (M_i) = dY.(x_i + 1) – dX.(y_i + ) + C. Ако d_i > 0, избираме (x_i+1, y_i+1) = (x_i + 1, y_i + 1), ако d_i  0 избираме

(x_i+1, y_i+1) = (x_i + 1, y_i).

При dY < 0, d_i = F (M_i) = dY.(x_i + 1) – dX.(y_i - ) + C. Ако d_i  0, избираме (x_i+1, y_i+1) = (x_i + 1, y_i), ако d_i < 0 избираме

(x_i+1, y_i+1) = (x_i + 1, y_i – 1).

Отново можем да съобразим някои неща за да изчисляваме

по-лесно.

Ако dY  0, d₀ = F (M₀) = dY.(X1 + 1) – dX.(Y1 + ) + C = dY - ,

d_i+1 = F (M_i+1) = dY.(x_i+1 + 1) – dX.(y_i+1 + ) + C =

= d_i + dY.(x_i+1 – x_i) – dX.(y_i+1 – y_i)  при d_i > 0, d_i+1 = d_i + dY – dX,

при d_i  0, d_i+1 = d_i + dY.

Ако dY < 0, d₀ = F (M₀) = dY.(X1 + 1) – dX.(Y1 - ) + C = dY + ,

d_i+1 = F (M_i+1) = dY.(x_i+1 + 1) – dX.(y_i+1 - ) + C =

= d_i + dY.(x_i+1 – x_i) – dX.(y_i+1 – y_i)  при d_i  0, d_i+1 = d_i + dY,

при d_i < 0, d_i+1 = d_i + dY + dX.

Тук привидно имаме недостатък – резултатът от делението на 2 може да не е целочислено, но ние лесно можем да го поправим като разглеждаме уравнението 2.F (x, y) = 2.dY.x – 2.dX.y + 2.C = 0 за правата.

Така достигаме до следния алгоритъм:

Вход: (X1, Y1), (X2, Y2).

1. Ако abs (X2 – X1) < abs (Y2 – Y1), тогава

разменяме X1, Y1 и X2, Y2 и rev = 1, иначе rev = 0; към 2.

2. Ако X2 < X1, тогава разменяме X1, X2 и Y1, Y2; към 3.

3. dY = 2.(Y2 – Y1), dX = 2.(X2 – X1); към 4.

4. Ако dY  0, d₀ = dY – dX/2, иначе d₀ = dY + dX/2; към 5.

5. x₀ = X1, y₀ = Y1, i = 0; към 6.

6. Ако rev = 0, чертаем (x_i, y_i), иначе чертаем (y_i, x_i); към 7.

7. Ако x_i < X2, към 8., иначе към 12.

8. Ако dY  0, към 9., иначе към 10.

9. Ако d_i > 0, тогава d_i+1 = d_i + dY – dX, x_i+1 = x_i + 1,

y_i+1 = y_i + 1, иначе d_i+1 = d_i + dY, x_i+1 = x_i + 1, y_i+1 = y_i; към 11.

10. Ако d_i  0, тогава d_i+1 = d_i + dY, x_i+1 = x_i + 1, y_i+1 = y_i, иначе

d_i+1 = d_i + dY + dX, x_i+1 = x_i + 1, y_i+1 = y_i – 1; към 11.

11. i = i+1; към 6.

12. Край.

V = Y2. Тогава m = . Във всеки фиксиран ред (при фиксирана втора координата) при растеризиране на отсечката трябва да се изчертава известна порция последователни пиксели. При направените предположения, първата порция трябва да е в

(-1, при V < 0) започва точно с един стълб по надясно от последния стълб в първата порция и т.н. Порциите се определят по следния начин: в реда y порцията е от всички x, такива че

y -  .x  y + . Оттук нататък предполагаме, че V > 0 – случаят V = 0 ще се разглежда отделно в алгоритъма, а случаят

V < 0 лесно може да се сведе към V > 0, тъй като порциите и в двата случая са едни и същи.

Умножаваме последното неравенство с и получаваме:

.y -  x  .y + .

Сега нека = c₀ + , където c₀, r₀   и 0  r₀ < 2.V и

Тогава, (c₁ + ).y – c₀ -  x  (c₁ + ).y + c₀ + 

c₁.y – c₀ +  x  c₁.y + c₀ + .y + . Така първата порция при y = 0 е 0, 1, …, c₀, тъй като < 1. Да положим mod₀ = r₀.

Очевидно е, че 0 = - . Втората порция при y = 1 започва точно с един стълб по-надясно от края на първата порция, т.е. в c₀ + 1 и продължава до c₀ + c₁ + . При това,

mod₁ = mod₀ + r₁, ако mod₀ + r₁ < 2.V (т.е. = 0) или

mod₁ = mod₀ + r₁ – 2.V, ако mod₀ + r₁  2.V (т.е. = 1).

Тогава е ясно, че = = - .

По-общо, нека порцията в реда y завършва в c. Имаме

c = c₁.y + c₀ + = c₁.y + c₀ + - .

Тогава порцията в реда y+1 започва в c+1 и завършва в = =

.

Първото събираемо е равно или на 0 или на 1, тъй като

mod_y + r₁ < 4.V. Ако mod_y + r₁ < 2.V, тогава порцията в реда y + 1 завършва в c + c₁ и тогава полагаме mod_y+1 = mod_y + r₁.

Ако mod_y + r₁  2.V, тогава порцията в реда y+1 завършва в

1 + c + c₁ и тогава полагаме mod_y+1 = mod_y + r₁ – 2.V.

Естествено, полагането е такова, че

= + - 

Този процес продължава естествено до момента, в който края на някоя от порциите достигне (или надмине) H.

Така достигаме до следния алгоритъм:

Вход: (X1, Y1), (X2, Y2).

1. Ако abs (X2 – X1) < abs (Y2 – Y1), тогава

разменяме X1, Y1 и X2, Y2 и rev = 1, иначе rev = 0; към 2.

2. Ако X2 < X1, тогава разменяме X1, X2 и Y1, Y2; към 3.

3. H = X2 – X1, V = abs (Y2 – Y1); към 4.

4. Ако Y2 > Y1, incY = 1, иначе incY = -1; към 5.

5. y = 0, x = 0, ако V = 0 към 6., иначе към 7.

6. c = H; към 8.

7. r₁ = (H + H) % (V + V), c₁ = (H + H) / (V + V), mod₀ = H % (V + V),

c = H / (V + V); към 8.

8. Ако c < H, към 9., иначе към 10.

9. Ако rev = 1 изчертаване на пикселите (Y1 + y, X1 + x),

(Y1 + y, X1 + x +1), …, (Y1 + y, X1 + c), иначе изчертаване на пикселите (X1 + x, Y1 + y), (X1 + x + 1, Y1 + y), …, (X1 + c, Y1 + y); към 11.

10. Ако rev = 1 изчертаване на пикселите (Y1 + y, X1 + x),

(Y1 + y, X1 + x +1), …, (Y1 + y, X1 + H), иначе изчертаване на пикселите (X1 + x, Y1 + y), (X1 + x + 1, Y1 + y), …, (X1 + H, Y1 + y); към 14.

11. x = c + 1; към 12.

12. Ако mod_y + r₁  V + V, mod_y+1 = (mod_y + r₁) – (V + V), c = c + c₁ + 1,

иначе mod_y+1 = mod_y + r₁, c = c + c₁; към 13.

13. y = y + incY; към 8.

14. Край.
По-нататък ще разгледаме алгоритми за растеризиране на окръжност. Навсякъде ще предполагаме, че окръжността има център (0, 0) и радиус цяло неотрицателно число R. Естествено, чрез подходяща транслация могат да се растеризират окръжности с произволен център. Целта на алгоритмите е да се оцветят по такъв начин пикселите, че да се създаде илюзията, че на екрана окръжността с център в пиксела (0, 0) и радиус R.

Естествено, при тези предположения, окръжността има уравнение F (x, y) = x² + y² – R² = 0. Тя разделя равнината на три части – вътрешността на кръга (тези с F (x, y) < 0), самата окръжност (контура на кръга, тези с F (x, y) = 0) и точките, извън кръга

(тези с F (x, y) > 0).
Първо разглеждаме алгоритъмът на Брезенхем за растеризиране на окръжност. При алгоритъма се растеризира само дъгата от окръжността, която се намира в първи квадрант и се използва, че окръжността е симетрична спрямо координатните оси и спрямо центъра. Първият пиксел, който оцветяваме е (x₀, y₀) = (0, R).

Нека е изчертан i-тият пиксел (x_i, y_i).

Да означим H_i = (x_i + 1, y_i), D_i = (x_i + 1, y_i – 1), V_i = (x_i, y_i – 1).

Следващият пиксел за чертане ще е един от H_i, D_i, V_i. За да определим точно кой изчисляваме

d_i = F (D_i) = F (x_i + 1, y_i – 1) = (x_i + 1)² + (y_i – 1)² – R².

Ако d_i  0 окръжността минава под D_i, но не и под V_i и затова ще избираме един от двата пиксела D_i и V_i. За целта изчисляваме

_i = F (D_i) + F (V_i). Тъй като F (D_i)  0, то F (D_i) е най-близкото разстояние от D_i до окръжността. Тъй като F (V_i)  0, то F (V_i) е

най-близкото разстояние от V_i до окръжността, но взето с обратен знак. Така, ако _i  0, трябва да изберем V_i, а когато _i < 0 трябва да изберем D_i. Имаме _i = F (D_i) + F (V_i) = d_i + x_i² + (y_i – 1)² – R² =

= 2.d_i + x_i² – (x_i + 1)² = 2.d_i – 2.x_i – 1. Така _i  0  2.d_i – 2.x_i – 1  0  d_i  x_i +  d_i > x_i, тъй като x_i и d_i са цели числа. Също,

_i < 0  d_i < x_i +  d_i  x_i, тъй като x_i и d_i са цели числа.

Така в случая 0  d_i  x_i избираме D_i, а в случая d_i > x_i избираме V_i.

Вторият случай е d_i < 0 и тогава окръжността минава над D_i, но не и над H_i и затова ще избираме един от двата пиксела D_i и H_i. За целта изчисляваме _i = F (D_i) + F (H_i). Тъй като F (D_i) < 0, то F (D_i) е най-близкото разстояние от D_i до окръжността, взето с обратен знак. Тъй като F (H_i)  0, то F (H_i) е най-близкото разстояние от H_i до окръжността. Така, ако _i  0, трябва да изберем D_i, а когато

_i < 0 трябва да изберем H_i. Имаме _i = F (D_i) + F (H_i) =

= d_i + (x_i + 1)² + y_i² – R² = 2.d_i + y_i² – (y_i – 1)² = 2.d_i + 2.y_i – 1.

Така _i  0  2.d_i + 2.y_i – 1  0  d_i  - y_i +  d_i > - y_i, тъй като

y_i и d_i са цели числа. Също, _i < 0  d_i < - y_i +  d_i  - y_i, тъй като y_i и d_i са цели числа. Така в случая - y_i < d_i < 0 избираме D_i, а в случая d_i  - y_i избираме H_i.

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

ако d_i  - y_i избираме (x_i+1, y_i+1) = H_i, ако – y_i < d_i  x_i избираме

(x_i+1, y_i+1) = D_i, ако x_i < d_i избираме (x_i+1, y_i+1) = V_i.
За по-ефективно изчисление да съобразим, че

d₀ = F (d₀) = F (x₀ + 1, y₀ – 1) = F (1, R – 1) = 1² + (R – 1)² – R² =

= 2 – 2.R.

Освен това, d_i+1 = F (D_i+1) = F (x_i+1 + 1, y_i+1 – 1) =

= (x_i+1 + 1)² + (y_i+1 – 1)² – R² = d_i – (x_i + 1)² – (y_i – 1)² + (x_i+1 + 1)² +

+ (y_i+1 – 1)² = d_i + (x_i+1 – x_i).(x_i+1 + x_i + 2) + (y_i+1 – y_i).(y_i+1 + y_i – 2).

Така, при (x_i+1, y_i+1) = H_i = (x_i + 1, y_i) имаме

d_i+1 = d_i + 2.x_i + 3, при (x_i+1, y_i+1) = D_i = (x_i + 1, y_i – 1) имаме

d_i+1 = d_i + 2.x_i + 3 – (y_i – 1 + y_i – 2) = d_i + 2.x_i – 2.y_i + 6,

при (x_i+1, y_i+1) = V_i = (x_i, y_i – 1) имаме

d_i+1 = d_i – (y_i – 1 + y_i – 2) = d_i – 2.y_i + 3.
Така достигаме до следния алгоритъм:

Вход: R.

2. Изчертаване на пиксела (x_i, y_i) и трите му симетрични точки относно координатните оси и относно центъра; към 3.

3. Ако y_i = 0 към 7., иначе към 4.

4. Ако d_i > - y_i, d_i+1 = d_i - 2.y_i + 3, y_i+1 = y_i – 1, иначе y_i+1 = y_i, d_i+1 = d_i; към 5.

5. Ако d_i  x_i, d_i+1 = d_i+1 + 2.x_i + 3, x_i+1 = x_i + 1, иначе x_i+1 = x_i; към 6.

6. i = i + 1, към 2.

7. Край.
Сега ще разгледаме алгоритъма на Михенер за растеризиране на окръжност. При този алгоритъм се растеризира само горния октант в първи квадрант и се използва, че окръжността е симетрична относно координатните оси, центъра и ъглополовящите на квадрантите.

Първият пиксел, който оцветяваме е (x₀, y₀) = (0, R).

Нека сме оцветили i-тият пиксел (x_i, y_i).

Отново да означим H_i = (x_i + 1, y_i), D_i = (x_i + 1, y_i – 1).

Тогава (i+1)-ият пиксел ще е един от H_i, D_i. С други думи, в означенията от алгоритъма на Брезенхем, при изчертаване на въпросния октант никога няма да се прави избор на V_i.

За да определим кой от двата пиксела да оцветим, изчисляваме

d_i = F (H_i) + F (D_i). Тъй като се намираме във въпросния октант,

винаги имаме F (H_i)  0 и F (D_i)  0. Така F (H_i) е най-близкото разстояние от H_i до окръжността и F (D_i) е най-близкото разстояние от D_i до окръжността, но взето с обратен знак.

И следователно при d_i  0 трябва да вземем (x_i+1, y_i+1) = D_i, а при

d_i < 0 трябва да вземем (x_i+1, y_i+1) = H_i.

За по-ефективно изчисление да съобразим, че

d₀ = F (H₀) + F (D₀) = F (1, R) + F (1, R – 1) = 1² + R² – R² + 1² +

+ (R – 1)² – R² = 3 – 2.R.

Освен това, d_i+1 = F (H_i+1) + F (D_i+1) = (x_i+1 + 1)² + y_i+1² – R² +

+ (x_i+1 + 1)² + (y_i+1 – 1)² – R² = d_i + (x_i+1 + 1)² + y_i+1² – (x_i + 1)² – y_i² +

+ (x_i+1 + 1)² + (y_i+1 – 1)² – (x_i + 1)² – (y_i – 1)² = d_i +

+ 2.(x_i+1 – x_i).(x_i+1 + x_i + 2) + (y_i+1 – y_i).(y_i+1 + y_i) + (y_i+1 – y_i).(y_i+1 + y_i – 2) =

= d_i + 2.(x_i+1 – x_i).(x_i+1 + x_i + 2) + 2.(y_i+1 – y_i).(y_i+1 + y_i – 1).

Така, при (x_i+1, y_i+1) = H_i = (x_i + 1, y_i), d_i+1 = d_i + 4.x_i + 6, а

при (x_i+1, y_i+1) = D_i = (x_i + 1, y_i – 1), d_i+1 = d_i + 4.x_i + 6 – 2.(2.y_i – 2) =

= d_i + 4.x_i – 4.y_i + 10.
Така достигаме следния алгоритъм:

Вход: R.

2. Изчертаване на пикселите (x_i, y_i) и (y_i, x_i) и шестте им симетрични точки относно двете координатни оси и центъра на координатната система; към 3.

3. Ако x_i  y_i към 6., иначе към 4.

4. Ако d_i  0, d_i+1 = d_i + 4.x_i – 4.y_i + 10, y_i+1 = y_i – 1, иначе

d_i+1 = d_i + 4.x_i + 6, y_i+1 = y_i; към 5.

5. x_i+1 = x_i + 1, i = i + 1, към 2.

6. Край.
Следващият алгоритъм за растеризиране на окръжност е алгоритъма на средната точка. При този алгоритъм също се растеризира само горния октант в първи квадрант.

Първият пиксел, който оцветяваме е (x₀, y₀) = (0, R).

Нека сме оцветили i-тият пиксел (x_i, y_i).

Отново да означим H_i = (x_i + 1, y_i), D_i = (x_i + 1, y_i – 1).

Както при алгоритъма на Михенер, тъй като изчертаваме въпросният октант, (i+1)-ият пиксел ще е един от H_i, D_i (няма да се прави избор на V_i). За да определим кой от двата пиксела ще се оцвети, въвеждаме M_i = (x_i + 1, y_i - ) – средата на H_iD_i и изчисляваме d_i = F (M_i) = F (x_i + 1, y_i - ) = (x_i + 1)² – (y_i - )² – R².

Ако d_i  0, т.е. окръжността минава под M_i, тогава е ясно, че трябва да изберем D_i, ако d_i < 0, т.е. окръжността минава над M_i, то е ясно, че трябва да изберем H_i.

d_i+1 = F (M_i+1) = (x_i+1 + 1)² + (y_i+1 - )² – R² = d_i + (x_i+1 + 1)² – (x_i + 1)² +

+ (y_i+1 - )² – (y_i - )² = d_i + (x_i+1 – x_i).(x_i+1 + x_i + 2) +

+ (y_i+1 – y_i).(y_i+1 + y_i – 1). Така, ако (x_i+1, y_i+1) = D_i = (x_i + 1, y_i – 1),

d_i+1 = d_i + 2.x_i + 3 – (2.y_i – 2) = d_i + 2.x_i – 2.y_i + 5, а ако

(x_i+1, y_i+1) = H_i = (x_i + 1, y_i), d_i+1 = d_i + 2.x_i + 3. Освен това,

d₀ = F (M₀) = F (1, R - ) = 1² + (R - )² – R² = - R.

Тук достигаме до недостатък, тъй като не е цяло число.

Това, обаче, лесно може да се преодолее по следния начин:

полагаме e_i = d_i - за всяко i. Естествено, горните зависимости между d_i+1 и d_i автоматично се пренасят и за e_i+1 и e_i, също

e₀ = 1 – R. Оттук се вижда, че за всяко i, e_i е цяло число 

e_i  0  d_i  0, e_i < 0  d_i < 0. Така при определянето на това кой пиксел да се избере можем да използваме знака на e_i вместо знака на d_i.

Вход : R.

1. x₀ = 0, y₀ = R, e₀ = 1 – R, i = 0; към 2.

2. Изчертаване на пикселите (x_i, y_i) и (y_i, x_i) и симетрични им точки относно двете координатни оси и центъра на координатната система; към 3.

3. Ако x_i  y_i към 6., иначе към 4.

4. Ако e_i  0, e_i+1 = e_i + 2.x_i – 2.y_i + 5, y_i+1 = y_i – 1, иначе

e_i+1 = e_i + 2.x_i + 3, y_i+1 = y_i; към 5.

5. x_i+1 = x_i + 1, i = i + 1, към 2.

6. Край.
Последният алгоритъм за растеризиране на окръжност, който ще разгледаме е алгоритъма на вторите крайни разлики. Отново окръжността растеризираме само в горния октант на първи квадрант и използваме нейната богата симетрия.

Първият оцветен пиксел е (x₀, y₀) = (0, R). Нека сме оцветили i-тият пиксел (x_i, y_i). Тогава, както в алгоритъма на средната точка, за (i+1)-ви пиксел избираме D_i или H_i, в зависимост от знака на

d_i = F (M_i) = (x_i + 1)² + (y_i - )² – R². Хитрото тук е начинът на изчисляване на d_i. Дефинираме d_i^H като изменението на d_i, ако на i-тата стъпка е избран пиксела H_i, т.е. d_i^H = d_i+1 – d_i, ако

(x_i+1, y_i+1) = H_i. Дефинираме d_i^D като изменението на d_i, ако на i-тата стъпка е избран пиксела D_i, т.е. d_i^D = d_i+1 – d_i, ако (x_i+1, y_i+1) = D_i.

Ако на i-тата стъпка сме избрали H_i, то от по-горе

d_i+1 = d_i + 2.x_i + 3  d_i^H = 2.x_i + 3. Ако на i-тата стъпка сме избрали D_i, то от по-горе d_i+1 = d_i + 2.x_i – 2.y_i + 5  d_i^D = 2.x_i – 2.y_i + 5.

Нека на i-тата стъпка е избрана H_i, т.е. (x_i+1, y_i+1) = H_i.

Тогава d_i+1^H = d_i+2 – d_i+1, ако на (i+1)-та стъпка е избрана H_i+1.

Така d_i+1^H = F (M_i+2) – F (M_i+1) = (x_i + 3)² + (y_i - )² – R² – (x_i + 2)² –

(y_i - )² + R² = 2.x_i + 5 = d_i^H + 2.

Също, d_i+1^D = d_i+2 – d_i+1, ако на (i+1)-та стъпка е избрана D_i+1.

Така d_i+1^D = F (M_i+2) – F (M_i+1) = (x_i + 3)² + (y_i - )² – R² – (x_i + 2)² –

(y_i - )² + R² = 2.x_i + 5 – (2.y_i – 2) = 2.x_i – 2.y_i + 7 = d_i^D + 2.

Нека на i-тата стъпка е избрана D_i, т.е. (x_i+1, y₊₁) = D_i.

Тогава d_i+1^H = d_i+2 – d_i+1, ако на (i+1)-та стъпка е избрана H_i+1.

Така d_i+1^H = F (M_i+2) – F (M_i+1) = (x_i + 3)² + (y_i - )² – R² – (x_i + 2)² –

(y_i - )² + R² = 2.x_i + 5 = d_i^H + 2.

Също, d_i+1^D = d_i+2 – d_i+1, ако на (i+1)-та стъпка е избрана D_i+1.

Така d_i+1^D = F (M_i+2) – F (M_i+1) = (x_i + 3)² + (y_i - )² – R² – (x_i + 2)² –

(y_i - )² + R² = 2.x_i + 5 – (2.y_i – 4) = 2.x_i – 2.y_i + 9 = d_i^D + 4.

Освен това, d₀^H = d₁ – d₀, ако на 0-та стъпка е избранo H_i, т.е.

d₀^H = F (M₁) – F (M₀) = 2² + (R – )² – R² – 1² – (R – )² + R² = 3.

Също, d₀^D = d₁ – d₀, ако на 0-та стъпка е избрано D_i, т.е.

d₀^D = F (M₁) – F (M₀) = 2² + (R – )² – R² – 1² – (R – )² + R² =

= 3 – (2.R – 2) = 5 – 2.R.

Имаме d₀ = - R и затова отново въвеждаме e_i = d_i - за всяко i.

Тогава e₀ = 1 – R и освен това в процеса на изчисление e_i се изменят по същия начин, както d_i – ако заменим навсякъде

по-горе d_i с e_i ще получим коректни резултати. Но e_i са цели 

e_i  0  d_i  0, e_i < 0  d_i < 0 и следователно можем да използваме знакът на e_i за да определяме кой пиксел да изберем на i-тата стъпка. Сега е ясно следното: ако на i-тата стъпка сме избрали

H_i, т.е. (x_i+1, y_i+1) = H_i  e_i+1 = e_i + d_i^H, а ако на i-тата стъпка сме избрали D_i, т.е. (x_i+1, y_i+1) = D_i  e_i+1 = e_i + d_i^D. Така като знаем e₀ и

d_i^H, d_i^D за всяко i ние можем да изчисляваме e_i за всяко i.
Така стигаме до следния алгоритъм:

Вход: R.

2. Изчертаване на пикселите (x_i, y_i) и (y_i, x_i) и шестте им симетрични точки относно двете координатни оси и центъра на координатната система; към 3.

3. Ако x_i  y_i към 6., иначе към 4.

4. Ако e_i  0, e_i+1 = e_i + d_i^D, d_i+1^H = d_i^H + 2, d_i+1^D = d_i^D + 4, y_i+1 = y_i – 1, иначе e_i+1 = e_i + d_i^H, d_i+1^H = d_i^H + 2, d_i+1^D = d_i^D + 2, y_i+1 = y_i; към 5.

5. x_i+1 = x_i + 1, i = i + 1, към 2.

6. Край.
Всички разгледани алгоритми могат да се използват за растеризиране на дъга от окръжност по следната схема:

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

F (x, y) = x² + y² – R² = 0, от ъгъл  до ъгъл  (спрямо абсцисата).

Тогава трябва да действаме по следната схема: първо изчисляваме

StartX = R.cos, StartY = R.sin, EndX = R.cos , EndY = R.sin

и след това чертаем цялата окръжност по някой от алгоритмите, като оцветяваме само тези пиксели, чийто номер на стълб е между StartX и EndX и чийто номер на ред е между StartY и EndY.

Естествено, тук прибягваме до изчисляване на тригонометричните функции, но няма как.

Нека сме оцветили i-тият пиксел (x_i, y_i). Тогава (i+1)-ят пиксел се избира между пикселите H_i = (x_i + 1, y_i), D_i = (x_i + 1, y_i – 1) и

V_i = (x_i, y_i – 1). При това растеризацията се разделя на два етапа:

през първия етап градиента на елипсата в изчертаваната точка сключва ъгъл по-голям от 45 градуса с абсцисната ос, а през втория етап градиента на елипсата в изчертаваната точка сключва ъгъл по-малък от 45 градуса с абсцисната ос. Ясно е, че през първия етап няма да има избор на V_i, а през втория етап няма да има избор на H_i. Границата между двата етапа е първият момента, в който ъгълът между градиента на елипсата в изчертаваната точка и абсцисната ос стане по-малък или равен на 45 градуса (в началото, естествено, този ъгъл е 90 градуса).

За градиента имаме grad F (x_i, y_i) = () =

= (2.b².x_i, 2.a².y_i). Тогава първият етап се определя от неравенството b².x_i < a².y_i. В първия момент, в който b².x_i  a².y_i трябва да започне вторият етап.

Нека сме в първия етап. За да определим кой пиксел ще се оцветява – H_i или D_i, полагаме M_i = (x_i + 1, y_i - ) и изчисляваме

d_i = F (M_i) = b².(x_i + 1)² + a².(y_i - )² – a².b². Ако d_i  0, т.е. M_i не попада във вътрешността на елипсата, то естествено трябва да изберем (x_i+1, y_i+1) = D_i, ако d_i < 0, т.е. M_i е във вътрешността на елипсата, трябва да изберем H_i. Ако сме избрали D_i, тогава

d_i+1 = F (M_i+1) = b².(x_i + 2)² + a².(y_i – ) – a².b² = d_i + b².(x_i + 2)² +

+ a².(y_i – ) – b².(x_i + 1)² – a².(y_i – ) = d_i + b².(2.x_i + 3) – a².(2.y_i – 2) =

= d_i + 2.b².x_i – 2.a².y_i + 3.b² + 2.a². Ако сме избрали H_i, тогава

d_i+1 = F (M_i+1) = b².(x_i + 2)² + a².(y_i – ) – a².b² = d_i + b².(x_i + 2)² +

+ a².(y_i – ) – b².(x_i + 1)² – a².(y_i – ) = d_i + b².(2.x_i + 3) =

= d_i + 2.b².x_i + 3.b².

Нека сме във втория етап. За да определим кой пиксел ще се оцветява – V_i или D_i, полагаме M_i = (x_i + , y_i - 1) и изчисляваме

d_i = F (M_i) = b².(x_i + )² + a².(y_i - 1)² – a².b². Ако d_i  0, т.е. M_i не попада във вътрешността на елипсата, то естествено трябва да изберем (x_i+1, y_i+1) = V_i, ако d_i < 0, т.е. M_i е във вътрешността на елипсата, трябва да изберем D_i. Ако сме избрали V_i, тогава

d_i+1 = F (M_i+1) = b².(x_i + )² + a².(y_i – 2) – a².b² = d_i + b².(x_i + )² +

+ a².(y_i – 2) – b².(x_i + )² – a².(y_i – 1) = d_i – a².(2.y_i – 3) =

= d_i – 2.a².y_i + 3.a². Ако сме избрали D_i, тогава

d_i+1 = F (M_i+1) = b².(x_i + )² + a².(y_i – 2) – a².b² = d_i + b².(x_i + )² +

+ a².(y_i – 2) – b².(x_i + )² – a².(y_i – 1) = d_i + b².(2.x_i + 2) – a².(2.y_i – 3) =

= d_i + 2.b².x_i – 2.a².y_i + 2.b² + 3.a².

Освен това, d₀ = F (M₀) = b².1² + a².(b - )² – a².b² = b² + a².b² – b.a² + .a² – a².b² = b² – b.a² + .a². Също, при прехода между етапите, естествено, трябва в началото да изчислим d_i директно.

Тук привидно има недостатък, тъй като не е цяло число. Това лесно може да се избегне, ако вместо уравнението F (x, y) = 0 за елипсата използваме еквивалентното уравнение 4.F (x, y) = 0.

Вход: a, b.

1. x₀ = 0, y₀ = b, d₀ = 4.b² – 4.b.a² + a², i = 0; към 2.

2. Изчертваваме пикселът (x_i, y_i) и трите му симетрични относно координатните оси и центъра на координатната система; към 3.

3. Ако a².y_i  b².x_i към 6., иначе към 4.

4. Ако d_i  0, d_i+1 = d_i + 8.b².x_i – 8.a².y_i + 12.b² + 8.a², y_i+1 = y_i – 1, иначе d_i+1 = d_i + 8.b².x_i + 12.b², y_i+1 = y_i; към 5.

5. x_i+1 = x_i + 1, i = i + 1; към 2.

6. d_i = b².(2.x_i + 1)² + a².(2.y_i - 2)² – 4.a².b²; към 7.

7. Ако d_i  0, d_i+1 = d_i – 8.a².y_i + 12.a², x_i+1 = x_i, иначе

d_i+1 = d_i + 8.b².x_i – 8.a².y_i + 8.b² + 12.a², x_i+1 = x_i + 1; към 8.

8. y_i+1 = y_i – 1, i = i + 1; към 9.

9. Изчертваваме пикселът (x_i, y_i) и трите му симетрични относно координатните оси и центъра на координатната система; към 10.

10. Ако y > 0 към 7., иначе към 11.

11. Край.

Съгласно принципа за модулност, програмата се разделя на подходящи взаимосвързани части, всяка от които се реализира чрез определени средства. Целта е промените в представянето на данните да не променят голям брой от модулите на програмата.