exam05 - MiAneko24/bmstu-cg GitHub Wiki
05. Алгоритмы Брезенхема разложения отрезков в растр. Простой алгоритм Брезенхема. Целочисленный алгоритм Брезенхема. Общий алгоритм Брезенхема.
В алгоритме Брезенхема используется понятие ошибки.
Ошибка - расстояние между действительным положением отрезка и ближайшими координатами сетки.
Проверяют только знак ошибки (это работает быстре). Поэтому, настоящее значение ошибки уменьшают на 0.5. Таким образом, e = m - 0.5, где (m - тангенс угла наклона) для второго пикселя (первый пиксель высвечивается по координатам, соответствующим началу отрезка).
В алгоритме, одна из координат х или у изменяется на 1 (выбирается путем приращения сравнения приращений по модулю, здесь выбирается большее из приращений, см. ниже), а другая на 0 или 1, взависимости от ошибки.
Простой алгоритм Брезенхема
Предназначен для построения отрезков только в октанте. х - единичное приращение, у - меняется на 0 или 1, взависимости от ошибки.
Общий алгоритм Брезенхема
Подходит для любого октанта, благодаря определению разности начальной и конечной точки отрезка.
Δx = sign(хк - хн)
Δy = sign(ук - ун)
Значение другой координаты идеального отрезка определяют как:
Y идеальное (i+1) = Y идеальное (i) + m.
Ошибка вычисляется как e = e + m.
Если e < 0, y(i+1) = yi
иначе, y(i+1) = y(i+1) + 1
Так как ошибку вычисляем заранее, то при e >= 0 делаем e = e - 1, т.к. y(i + 1) = y(i) + 1, что не было учтено при подсчёте ошибки.
Псевдокод простого алгоритма
1. Ввод исходных данных (Xн, Yн), (Xк, Yк)
2. X = Xн ; Y = Yн
3. dx = Xк - Xн; dx = Xк - Xн
4. m = dy / dx; e = m - 0.5
5. Цикл определения отрезка (по i от 1 до dx + 1)
5.1. Высвечивание (x, y)
5.2. Если e >= 0, то
1) y = y + 1
2) e = e - 1
5.3. e = e + m
5.4. Конец цикла
6. Конец
Хоть алгоритм и работает с действительными числами, путем математических преобразований, мы можем получить тот же самый алгоритм, но в целых числах.
e = dy / dx - 0.5 =====> e = 2dy - dx
Псевдокод общего алгоритма
1. Ввод исходных данных (Xн, Yн), (Xк, Yк)
2. X = Xн ; Y = Yн
3. dx = Xк - Xн; dx = Xк - Xн
4. Sх = sign(dx); Sy = sign(dy)
5. dx = |dx|; dy = |dy|
6. Если dx > dy, то обмен = 0, иначе обмен = 1; t = dx; dx = dy; dy = t
7. m = dy / dx; e = m - 0.5 (для челочисленного e = 2dy - dx)
8. Цикл определения отрезка (по i от 1 до dx + 1)
8.1. Высвечивание T(x, y)
8.2. Если e >= 0, то
1) если обмен = 0, то y = y + sy, иначе x = x + sx
2) e = e - 1 (для целочисленного e = e - 2dx)
8.3. Если обмен = 0, то x = x + sx, иначе y = y + sy
8.4. e = e + m (для целочисленного e = e + 2dy)
8.5. Конец цикла
9. Конец
По Курову стр. 7-8
Следующий вопрос: 06. Основные расчетные соотношения и алгоритм Брезенхема для генерации окружности.