3. Алгоритм Брезенхема отрисовки отрезка. Слайд 12.

Недостатки алгоритма ДДА устранены в алгоритме Брезенхема. В алгоритме используют только целые числа и операции сложения, вычитания и сдвига.

Суть алгоритма: выбор наилучшей растровой координаты для представления отрезка. Одна из координат x или y (в зависимости от величины углового коэффициента k) на каждом шаге увеличивается на единицу (1). Изменение другой координаты равно либо 0, либо 1 и зависит от расстояния между действительным положением точки отрезка и ближайшими координатами сетки. Это расстояние называют ошибкой. Выбор пиксела определяется по знаку разности ошибок.

Будем считать: 0 ≤ k = = ≤ 1, т. е. наклон отрезка к оси x ≤ 45°. Отрезок задан начальной точкой x1, y1 и конечной x2, y2.

Преобразуем параллельным переносом положение отрезка так, чтобы начало отрезка совпало с началом координат, слайд 13.

Тогда начальной точкой отрезка стала точка (0, 0), а конечной (dx, dy), где dx = x₂ – x₁ и dy = y₂ – y₁; уравнение прямой принимает вид y = kx = · x.

Обозначим координаты точки P_i-1 после переноса отрезка в начало координат через (r, q), т. е. x_i-1 = r, y_i-1 = q; тогда Si = (r+1, q), а T = (r+1, q+1), Слайд 13. Из подобия треугольников найдём .

Выразим S: S = (r+1) – q.

Так как приращение по “y” может быть либо 0, либо 1, то

Σ (T+S) = 1 и T = 1-S = 1 - (r+1) – q.

Разность S -T = 2 (r+1) – 2q – 1.

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

dx(S - T) = 2(rdy - qdx) + 2dy – dx.

Приращение dx всегда больше нуля, поэтому dx(S - T) можно применять для определения ближайшего к отрезку пиксела, который будет закрашен. Если dx(S-T) < 0, то выбирается точка S_i, в противном случае Т_i. Введём обозначение: d_i = dx(S - t), тогда d_i = 2(rdy - qdx) + 2dy – dx.

Так как r = x_i-1, а q = y_i-1, то

d_i = 2x_i-1dy – 2y_i-1dx + 2dy – dx (A)

Прибавим единицу ко всем индексам, получим

d_i+1 = 2x₁dy -2y₁dx + 2dx – dx,

а разность

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

Тогда, так как x_i – x_i-1 = 1, то

d_i+1 = d_i +2dy – 2dx(y_i – y_i-1) (B)

Это есть рекуррентная формула управления выбором ближайшего пиксела к отрезку прямой под закраску.

Если d_i ≥ 0, то выбирается T_i:

y_i = y_i-1 + 1; d_i+1 = d_i +2(dy - dx).

Если d_i < 1, то выбирается S_i:

y_i = y_i-1; d_i+1 = d_i + 2dy.

Осталось найти начальные значения d_i: (x₀, y₀) = (0, 0).

Внесем значения координат (x₀, y₀) в формулу (А), тогда

d₁ = 2dy – dx.

Если dy > dx, то пошагово увеличивают y и вычисляют х.

4. Отрисовка окружности

Окружность нетрудно построить по её математическому представлению R² = x² + y², y = ± , 0 ≤ x ≤ R.

Задавая значения x будем получать значение y и ставить точку. Но быстро обнаружатся артефакты в отрисовке – неравномерное распределение пикселов по окружности. Другой недостаток – сложные вычисления – извлечение квадратного корня. Первый недостаток можно устранить, если представить окружность в полярных координатах

x = R cosθ, y = R sinθ.

Подбирая подходящий шаг θ изменения угла θ в заданном интервале его значений, например 0 ≤ θ ≤ , будем определять требуемые координаты пиксела и записывать их. А что плохо? Вычисление sinθ и cosθ.