Алгоритм брезенхема для треугольника (4 видео)

Алгоритм Брезенхема для рисования наклонных отрезков

Алгоритм Брезенхема был предложен Джеком Е. Брезенхэмом (Jack E. Bresenham) в 1962 году и предназначен для рисования фигур точками на плоскости. Этот алгоритм находит широкое распространение в машинной графике для рисования линий на экране. Алгоритм определяет, какие точки двумерного растра необходимо закрасить.

Графическая интерпретация алгоритма Брезенхема представлена на рисунке.

Для рисования прямых отрезков на плоскости с использованием алгоритма Брезенхема запишем уравнение прямой в общем виде

y=kx+b

f(x,y)=Ax+By+C=0

где коэффициенты A и B выражаются через коэффициенты k и b уравнения прямой. Если прямая проходит через две точки с координатами (x1;y1) и (x2;y2) , то коэффициенты уравнения прямой определяются по формулам

A=y2-y1
B=x1-x2
C=y1∙x2-y2∙x1

Для любой растровой точки с координатами (xi;yi) значение функция

f(xi,yi)=0 если точка лежит на прямой
f(xi,yi)>0 если точка лежит ниже прямой
f(xi,yi) где i – номер отображаемой точки.

Таким образом, одним из методов решения того, какая из точек P или Q (см. рисунок) будет отображена на следующем шаге, является сравнение середины отрезка |P-Q| со значением функции f(x,y) . Если значение f(x,y) лежит ниже средней точки отрезка |P-Q| , то следующей отображаемой точкой будет точка P , иначе — точка Q .
Запишем приращение функции

∆f=A∆x+B∆y

После отображения точки с координатами (xi,yi) принимается решение о следующей отображаемой точке. Для этого сравниваются приращения Δx и Δy , характеризующие наличие или отсутствие перемещения по соответствующей координате. Эти приращения могут принимать значения 0 или 1. Следовательно, когда мы перемещаемся от точки вправо,

∆f=A,

когда мы перемещаемся от точки вправо и вниз, то

∆f=A+B,

когда мы перемещаемся от точки вниз, то

∆f=B

Нам известны координаты начала отрезка, то есть точки, заведомо лежащей на искомой прямой. Ставим туда первую точку и принимаем f = 0 . От текущей точки можно сделать два шага — либо по вертикали (по горизонтали), либо по диагонали на один пиксель.
Направление движения по вертикали или горизонтали определяется коэффициентом угла наклона. В случае если угол наклона меньше 45º, и

|A| Реализация на C++

Алгоритм Брезенхема также может применяться в задачах управления, например, для регулирования мощности или скорости вращения. При этом горизонтальной осью является ось времени, а заданное значение устанавливает коэффициент угла наклона прямой.

Содержание

Краткий курс компьютерной графики: пишем упрощённый OpenGL своими руками, статья 2 из 6
Улучшение кода
Official translation (with a bit of polishing) is available here.
Update:
Рисуем заполненный треугольник
Рисуем модель
Плоская тонировка
Алгоритм брезенхема для треугольника
Друзья
Алгоритм Брезенхэма
Распространение алгоритма на всю плоскость
Делений становится меньше
🎥 Видео

Видео:Графика с нуля | Точки и линии. Алгоритм БрезенхэмаСкачать

Краткий курс компьютерной графики: пишем упрощённый OpenGL своими руками, статья 2 из 6

Улучшение кода

Official translation (with a bit of polishing) is available here.

Update:

Внимание, статья 4в даёт новую, более простую версию растеризатора.

Давайте знакомиться, это я.

То есть, модель моей башки, отрендеренная в программе, которую мы сделаем за ближайшие час-два.

В прошлый раз мы нарисовали проволочную сетку трёхмерной модели, в этот раз мы зальём полигоны. Точнее, треугольники, так как OpenGL практически любой полигон триангулирует, поэтому ни к чему разбирать сложный случай. Напоминаю, что этот цикл статей создан для самостоятельного программирования. Время, которое я здесь привожу — это не время чтения моего кода. Это время написания вашего кода с нуля. Мой код здесь только для того, чтобы сравнить ваш (рабочий) код с моим. Я совсем не являюсь хорошим программистом, поэтому ваш код может быть существенно лучше моего. Любая критика приветствуется, любым вопросам рад.

Пожалуйста, если вы следуете этому туториалу и пишете свой код, выкладывайте его на github.com/code.google.com и им подобные и давайте ссылки в комментариях! Это может хорошо помочь как и вам (другие люди могут чего посоветовать), так и будущим читателям.

Видео:Алгоритм БрезенхэмаСкачать

Рисуем заполненный треугольник

Итак, тема на сегодня (примерно на два часа для плохо программирующих, но мотивированных студентов): отрисовка двумерных треугольников. В прошлый раз мы разобрали алгоритм Брезенхэма для растеризации отрезка, теперь задача нарисовать заполненный треугольник. Вы будете смеяться, но это нетривиальная задача. Я не знаю почему, но я знаю, что это так. Большинство моих студентов без подсказок проводят над этой задачей существенно больше пары часов. Давайте определимся с методом, а затем будем программировать.

В самом начале давайте рассмотрим вот такой псевдокод:

Я очень люблю этот метод. Он простой и рабочий. Найти описывающий прямоугольник крайне просто, проверить принадлежность точки двумерному треугольнику (да и любому выпуклому полигону) тоже просто.

Оффтоп: если мне нужно будет написать код, который будет крутиться на, скажем, самолёте, и этот код должен будет проверять принадлежность точки полигону, я никогда не сяду на этот самолёт. Это на удивление сложная проблема, если мы хотим её решить надёжно.

Почему я люблю этот код? Да потому, что, увидев такое, совсем новичок в программировании его воспримет с энтузиазмом, человек, немного знакомый с программированием, только самодовольно хмыкнет, мол, вот идиот писал. А эксперт в программировании компьютерной графики просто пожмёт плечами, мол, ну да, так оно и работает в реальной жизни. Массивно-параллельные вычисления в тысячах маленьких графических процессоров (я говорю про обычные потребительские компьютеры) творят чудеса. Но мы будем писать код под центральный процессор, поэтому этот метод использовать не будем. Да и какая разница, как оно там в кремнии, нашей абстракции вполне хватит для понимания принципа работы.

Окей, начальная заглушка будет выглядеть следующим образом:

Как обычно, на гитхабе доступен отпечаток кода. В этом коде всё просто: я даю три треугольника для начальной отладки вашего кода; если внутри функции triangle просто сделать вызов line(), то получим контур треугольника. Как нарисовать заполненный треугольник?

Хороший метод отрисовки треугольника должен обладать следующими свойствами:

Он должен быть (сюрприз) простым и быстрым
Он должен быть симметричным: картинка не должна зависеть от порядка вершин, переданных в функцию отрисовки
Если два треугольника имеют две общие вершины, между ними не должно быть дырок из-за округлений растеризации.

Требований можно добавлять гораздо больше, но мы довольствуемся этими тремя.

Традиционно используется line sweeping (заметание отрезком?):

Сортируем вершины треугольника по их y-координате
Растеризуем параллельно левую и правую границы треугольника
Отрисовываем горзонтальный отрезок между левой и правой точкой границы

Тут мои студенты начинают теряться, кто левый, кто правый, да и вообще, в треугольнике три отрезка…
В этот момент я оставляю своих студентов примерно на час, чтение моего кода куда как менее ценно, нежели сравнение своего (выстраданного!) кода с моим.

Как рисую я? Ещё раз, если у вас есть лучший метод, то я его с огромным удовольствием возьму на вооружение. Давайте предположим, что у нас есть три точки треугольника, t0,t1,t2, они отсортированы по возрастанию y-координаты.
Тогда граница А будет между t0 и t2, граница Б будет между t0 и t1, а затем между t1 и t2.

Здесь у нас граница А нарисована красным, а граница Б зелёным.

Граница Б, к сожалению, составная. Давайте отрисуем нижнюю половину треугольника, разрезав его по горизонтали в точке излома границы Б.

Заметьте, что в этот раз у меня получились разрывные отрезки. В отличие от прошлого раза (где мы рисовали прямые) я не заморочился поворотом изображения на 90°. Почему? Это оказывается не всем очевидным моментом. Просто если мы соединим горизонтальными линиями соответствующие пары точек, то пробелы пропадут:

Теперь осталось отрисовать вторую половину треугольника. Это можно сделать, добавив второй цикл:

На этом можно было бы успокоиться, но у меня случается несварение, когда я дважды вижу один и тот же код, да ещё так рядом. Поэтому сделаем его чуть менее читаемым, зато более простым для модификаций.

Отпечаток кода для отрисовки 2d треугольников.

Видео:Лекция 2 | Компьютерная графика | Виталий Галинский | ЛекториумСкачать

Рисуем модель

Мы умеем уже отрисовывать модель с пустыми треугольниками, давайте их зальём случайным цветом, это поможет нам проверить, насколько хорошо мы закодировали заполнение треугольников. Вот код.

Всё просто: как и раньше, пробегаем по всем треугольникам, превращаем мировые координаты в экранные и рисуем треугольники. Подробное описание разных систем координат в последущих статьях. Должно получиться нечто вроде этого:

Видео:Графика с нуля | Растеризация треугольника, интерполяцияСкачать

Плоская тонировка

Давайте теперь убирать эти клоунские цвета и освещать нашу модель.
Капитан Очевидность: «При одной и той же итенсивности света полигон освещён максимально ярко, если свет ему перпендикулярен».

Нулевую освещённость мы получим, если полигон параллелен вектору света.
Перефразируем: интенсивность освещённости равна скалярному произведению вектора света и нормали к данному треугольнику.
Нормаль к треугольнику может быть посчитана просто как векторное произведение двух его рёбер.

Но ведь скалярное произведение может быть отрицательным, что это означает? Это означает, что свет падает позади полигона. Если модель хорошая (обычно не наша забота, а 3д моделеров), то мы просто можем этот треугольник не рисовать. Это позволяет быстро убрать часть невидимых треугольников. В англоязычной литературе называется Back-face culling.

Модель моей головы выглядит детальнее? Ну так в ней четверть миллиона треугольников. Ничего, детали мы добавим позже, получив картинку, которую я дал для затравки в первой статье.

Обратите внимание, внутренняя полость рта нарисовалась поверх губ. Ну а что, такое быстрое отсечение невидимых треугольников убирает всё ненужное только для выпуклых моделей. Эти огрехи мы уберём в следующий раз, закодировав z-buffer.

Видео:Алгоритм Брезенхэма. Algorithms BresenhamСкачать

Алгоритм брезенхема для треугольника

Друзья

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

Прим. В зависимости от перевода, иногда его называют алгоритм Брезенхема.

Рассмотрим произвольный отрезок p ₁ ( x ₁ , y ₁ ) – p ₂ ( x ₂ , y ₂ ) :

Чтобы растеризовать его можно поступить следующим образом (небольшая модификация алгоритма DDA-линии):

посчитаем длины отрезка по осям координат lengthX = | x ₂ – x ₁ | и lengthY = | y ₂ – y ₁ | ;
выберем большую из них length = max ( lengthX , lengthY ) ;
случай length == 0 особый: закрашиваем пиксел ( x ₁ , y ₁ ) = ( x ₂ , y ₂ ) и завершаем работу алгоритма;
допустим большая длина оказалась lengthX . Установим начальную точку x = x₁, y = y₁ ;
сделаем length + 1 итераций:
закрашиваем пиксел с координатами ( x , roundf ( y )) ;
координата x увеличивается на единицу, координата y увеличивается на lengthY / length X .

Прим. roundf – округление до ближайшего целого.

Прим. Обратите внимание, что | x ₂ – x ₁ | и | y ₂ – y ₁ | это расстояния между центрами первого и последнего пикселей.

#define roundf(x) floor(x + 0.5f )

void line(HDC hdc, int x1, int y1, int x2, int y2)
<
int lengthX = abs(x2 — x1);
int lengthY = abs(y2 — y1);

int length = max(lengthX, lengthY);

if (length == 0)
<
SetPixel(hdc, x1, y1, 0);
>

if (lengthY
<
// Начальные значения
int x = x1;
float y = y1;

// Основной цикл
length++;
while (length—)
<
SetPixel(hdc, x, roundf(y), 0);
x++;
y += float (lengthY) / lengthX;
>
>
else
<
// Начальные значения
float x = x 1;
int y = y 1;

// Основной цикл
length ++;
while (length—)
<
SetPixel(hdc, roundf(x), y, 0);
x += float (lengthX) / lengthY;
y++;
>
>
>

При таком подходе x является целочисленной переменной, в то время как y – вещественная. Также заметим, что координата x всегда увеличивается на единицу, хотя x₂ может быть меньше x₁ . То же замечание относится к координате y .

Итак, приведенный выше алгоритм обладает двумя существенными недостатками:

Он работает только в первой четверти.
Используются вычисления с плавающей точкой.

Распространение алгоритма на всю плоскость

Делений становится меньше

Теперь избавимся от вычислений с плавающей точкой. Можно поступить по аналогии с оптимизацией к алгоритму DDA, используя вычисления с фиксированной точкой. Но в данном случае можно даже не использовать операцию деления.

Рассмотрим основной цикл. Сначала оптимизируем цикл для случая lengthY lengthX , для другого случая все делается аналогично. Заметим, что изначально y является целой величиной. В цикле y изменяется на дробь со знаменателем lengthX . Т.о. х также является дробью со знаменателем lengthX . Избавимся от знаменателя, домножив на него: // Начальные значения int x = x 1; int y = y 1 * lengthX ; // Основной цикл length++; while (length—) Увы, но при отрисовке пикселя мы снова должны прибегать к делению. Идея состоит в том, что величина y / lengthX за шаг меняется не более чем на единицу. Разобьем y на целую часть и приращение следующим образом:

y = z + c , где z это y , округленная до ближайшего целого, а с принадлежит отрезку [-0.5; 0.5] . То, что с принадлежит отрезку [-0.5; 0.5] гарантирует нам, что z — это действительно y, округленное до ближайшего целого. Нашей задачей будет поддержание величины c в этих границах. Рассмотрим исходный вариант реализации основного цикла: // Начальные значения int x = x 1; float y = y 1; // Основной цикл length ++; while (length—) Внесем необходимые изменения: // Начальные значения int x = x 1; int y = y1; float c = 0; // Основной цикл length++; while (length—) 0.5) if (c c++; y—; > > Чтобы не делать несколько сравнений можно величину с всегда увеличивать в положительную сторону. Тем самым сравнивать придется только с 0.5, но при этом у будет менятся на dy : // Начальные значения int x = x 1; int y = y1; float c = 0; // Основной цикл length++; while (length—) 0.5) > Начнем избавляться от дробей. Сперва заметим, что можно сделать замену d = 2 * c — 1 , при этом d сравнивается с нулем: // Начальные значения int x = x 1; int y = y1; float d = -1; // Основной цикл length++; while (length—) 0) >Прим. При линейных заменах ( u = a * v + b ) правила следующие:

Считаем, что замена имеет смысл, т.е. не рассматривются варианты a = 0. Тогда замена обратима:

v = (1 / a) – b / a

Присвоение переменной преобразуется по линейному закону:

v = 2 > u = a * 2 + b

При сравнении переменной, величина, с которой производится сравнение, преобразуется по линейному закону:

v >0.5 > u > a * 0.5 + b

Если v увеличивается на некоторую величину, то u увеличивается на ту же величину, помноженную на a :

v -= 4 > u -= 4 * a;

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

Вернемся к алгоритму. Последним штрихом будет применение оптимизации, рассмотренной в начале: // Начальные значения int x = x 1; int y = y1; int d = -lengthX; // Основной цикл length++; while (length—) 0) >