АлгоритмБрезенхема для прямой

АЛГОРИТМ БРЕЗЕНХЕМА

Современная информация на дисплеях – растровая. Она представляет собой двумерный массив (матрицу), ячейки которой заполнены информацией о цвете.

Когда мы получаем в распоряжение матрицу из пикселей, у нас возникает задача: как вывести объект, чтобы его изображение получилось достоверным?

Самый простой объект – точка. С ней все легко и зависит от аппаратуры, с которой вы работаете.Рассмотрим более сложный объект – прямая линия. В частном случае ее вывод также не составит труда, когда прямая линия горизонтальная, вертикальная или под углом 45 градусов. Нужно лишь вывести точки в цикле, вовремя инкрементируя значения координаты. Но в общем случае это не годится, и для вывода используются определенные алгоритмы.

В качестве грубого варианта можно использовать параметрическое уравнение прямой:

Далее возьмем достаточно малое t и закрасим все точки, которые удовлетворяют системе. Но в таком случае у нас появится неприятный эффект: точки в некоторых местах будут сгущаться (рис. 1.1). Дискретность экрана не учитывается, и из-за маленького шага алгоритм будет ходить лестницей по экрану. В компьютерной графике существует правило, по которому при точном воспроизведении линейных объектов на экране в зоне 2х2 существует не более двух точек.

рис. 1.1Эффект сгущающихся точек (слева); корректно построенная прямая линия (справа)

Рассмотрим прямую, лежащую в первой «октанте»– под углом к оси OX от 0 до 45 градусов. Идея состоит в следующем: двигаясь слева на право, мы в цикле закрашиваем точку (X, Y), при этом либо увеличиваем координату Y на единицу (закрашиваем пиксель А), либо оставляем ее без изменений (закрашиваем пиксель B). Координату X, соответственно, постоянно увеличиваем на единицу(рис. 1.2). Т.е. наша задача: вовремя увеличить координату Y на единицу.

рис. 1.2Прохождение прямой по растровой сетке

АлгоритмDDA-линии (Digitaldifferentialanalyzer)

int x;

float y;

float slope = (y2 – y1) / (x2 – x1)

x = x1;

y = y + 0.5;

while (x <= x2)

{

setPixel(x, (int)y);

y = y + slope;

x = x + 1;

}

Алгоритм очень простой и используется повсеместно. Мы просто рассчитываем каждый раз Y и округляем его до целых. Прибавление ½ к координате Y обеспечивает округление числа по законам математики.

В чем недостаток этого подхода?

В общей своей части этот алгоритм оптимален – он не делает ничего лишнего. Нам нужно поставить N точек и наш цикл проходит N раз. Быстрее не сделаешь. Но исторически сложилось, что работа с числами вещественной арифметики (float, double и т.д.) идет намного дольше, чем с целыми. Прогресс не стоит на месте, и вычислительная мощность наших компьютеров ощутимо выше, чем пол века назад, но во многих случаях (тем более в компьютерной графике) скорость все еще важна, а значит, необходимо избавляться от вещественной арифметики.

АлгоритмБрезенхема для прямой

Возьмем за основу уравнение прямой проходящей через две точки

Умножаем обе части уравнения на знаменатели:

Левую часть полученного уравнения обозначим за

, когда точка  лежит на прямой

Несложно проверить, что

, когда точка  «ниже» прямой

, когда точка  «выше» прямой

Как этим можно воспользоваться? Изобразим пиксели в виде точек (рис. 1.3):

рис. 1.3Возможные пути линии по экрану

Красным цветом выделены возможные пути линии по экрану. M­– средняя точка на следующем разрезе между пикселями. Если линия идет над этой точкой, то мы окрашиваем верхний пиксель, если ниже – то нижний. Будем считать, что точка P уже нарисована.

Таким образом:

если – выбираем точку NE

если  – выбираем точку E

Получившийся алгоритм:

intx, y;

x = x1; y = y1;

setPixel (x,y)

count = dx;

while (count > 0)

{

count = count – 1;

if (f(x + 1, y + 0.5) > 0

     y = y + 1;

x = x + 1

setPixel(x,y)

}

Однако проблема вещественных чисел никуда не ушла. К тому же мы в каждом цикле пересчитываем функцию . Следующий шаг – использовать приращение функции вместо постоянного ее расчета. Т.е. мы смотрим, как изменяется функция в своем значении, в зависимости от того, куда мы перемещаемся на Eили NE (рис. 1.4).

рис. 1.4 Расчет приращения функции

Если мы в процессе алгоритма уходим вправо, то точка M перемещается в точку M_E, если вправо и вверх – в M_NE.

Рассчитаем значение функции в этих трех точках:

Выходит разница между текущим значением и следующим равна в одном случае и  в другом

Осталось узнать, чему равно  – значение функции в первом случае, после выхода из начальной точки  (рис. 1.5)

рис. 1.5 Расчет первого значения функции

Общий алгоритм теперь выглядит так:

int x, y, dx, dy;

float f;

dx = x2 – x1;

dy = y2 – y1;

f = dy – dx/2; //e = 2*dy - dx

x = x1; y = y1;

setPixel (x,y)

count = dx;

while (count > 0)

{

count = count – 1;

if (f > 0) //if(e > 0)

{

     y = y + 1;

     f = f + dy – dx; //e = e + 2*dy – 2*dx

}

else

     f = f + dy; //e = e + 2*dy

x = x + 1;

setPixel(x,y)

}

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

Задание на лабораторную работу:

Минимальный функционал, который должен дать нам видеодрайвер – рисование точки. Его возьмем готовой функцией. Мы не будем работать с нижним уровнем, т.к. наша цель – понять принцип работы алгоритмов.

В качестве языка программирования возьмемJavaScript(выполнять лабораторные работы можно на любом удобном вам языке). Краткую информацию по языку можно найти в приложении.

1. В новой папке, в которой будем хранить наш проект, создаем два новых файла: index.htmlи main.js

2. В файл index.html вписываем следующий код:

В рамках нашего курса у нас не стоит задачи разбираться в html разметке, однако немного поясним, что мы сделали:

· index.html это файл, который и представляет нашу страницу – его можно запустить в любом браузере. Сейчас он выдаст лишь пустую страницу с заголовком "Компьютерная графика" (его мы указали в теге <title>

· стр. 8: В теге <canvas> мы объявили область (размер 800x800), в которой будем рисовать

· стр. 9 – 14: После выполняем еще один небольшой скрипт, который зеркально отражает наш canvas по вертикали. По умолчанию начало системы координат в canvas находится в верхнем левом углу и ось ординат направлена вниз. Мы же переместили начало координат в левый нижний угол и направили ось ординат вверх – что немного привычней

· стр. 15: Далее выполняем наш скрипт из файла main.js

3. В файлеmain.jsобъявляем функцию set_pixel:

Эта функция рисует пиксель (прямоугольник 1x1) в области canvas заданным цветом. Можно легко проверить ее работу, вызвав ниже эту функцию. Например, так:

4. Добавляем в main.jsфункциюset_line принимающую аргументы x1, y1, x2, y2, color. Функция должна использовать алгоритм Брезенхема и строить прямую линию цвета color от точки (x1, y1) до (x2, y2).

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

5. Проверяем работу функции вызвав ее со следующими параметрами:

В итоге мы должны получитьвосемь линий в форме звезды (рис. 1.6)

рис. 1.6Результат лабораторной работы

ПРОВОЛОЧНЫЙ РЕНДЕР

В качестве модели используем файл Triss.obj.

OBJ — это формат файлов описания геометрии, разработанный в Wavefront Technologies. Формат файла является открытым и был принят другими разработчиками приложений 3D графики и может быть экспортирован или импортирован в Maya, Blender, 3D Studio Max, Cinema 4D и т.д.

Просмотреть файл OBJможно в любом текстовом редакторе. Он содержит несколько видов определений, например:

· Список вершин с координатами XYZ

v 0.1088586 0.05728579 0.1080199

vXXX

· Список граней

f -42/-42/-42-41/-41/-41-43/-43/-43

f X/X/XX/X/X X/X/X

В гранях нас интересуют первые числа в кортежах X/X/X

Это индексы вершин в массиве, котором мы прочитали ранее. В нашем случае индексация отрицательная. Отрицательный индекс указывает позицию относительно последнего элемента (индекс -1 указывает на последний элемент). Т.е. точки -42 -41 и -43 образуют треугольник).

Задание на лабораторную работу:

1. В папке проекта создаем новую папку Model

2. Помещаем в папку Modelфайлы модели (Triss.obj)

3. В файле index.htmlдобавляем ссылку на скрипт jQuery перед ссылкой на скрипт main.js. Он необходим нам для работы с файлом модели.

4. Добавляем в файл main.jsфункцию-конструкторvector, для обозначения вершин и векторов. Функция принимает значения координат xyz, которые мы возьмем с файла OBJ

5. Пишем ajaxзапрос на чтение файла модели. Данная часть кода считывает файл OBJпо указанному адресу и, в случае успеха, передает в переменную onjtextмассив строк из этого файла.

6. Заполняем два массива: в listVertexхранятся объекты типа vector – вершины модели. А listFaceпредставляет из себя массив массивов или массив треугольников (граней, полигонов).

7. Проходим циклом по всем треугольникам модели, а в каждом треугольнике по всем трем сторонам. В переменные v1 и v2 передаем координаты точек (начальная и конечная границы отрезка) и вызываем функцию set_lineс этими координатами.

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

8. В итоге мы получаем отображение каркасной модели (рис. 2.1)

рис. 2.1 Каркасная модель

ЗАКРАСКА ПОЛИГОНА

Изображение треугольника на экране – набор горизонтальных отрезков. И достаточно пройтись по всем строкам экрана, с которыми пересекается треугольник, и нарисовать соответствующие горизонтальные отрезки.

Т.е. первым делом сортируем вершины треугольника по координате y. Далее проходим по всем линиям от до .

В качестве примера возьмем линиюS и треугольник ABC, в котором
, а  (рис. 3.1).

рис. 3.1 Линия пересечения треугольника

Если S.y<B.y, то она пересекает стороны AC и BC,если S.y>B.y, то она пересекает стороны AC и AB. Алгоритм будет проще реализовывать в два цикла, закрашивая сначала одну половину треугольника, затем другую.

Для рисования отрезка нам нужно лишь узнать координаты точек пересечения Sсо сторонами треугольника. Вспомним, что точка на координатной плоскости задается радиус-вектором (рис. 3.2).

рис. 3.2 Нахождение точки пересечения

В нашем примере вектор OK равен сумме векторов OC и CK.

Как узнать вектор CK? Он равен вектору CB, умноженному на некоторый коэффициент .Коэффициент  можно вычислить из подобия треугольников:

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

Задание на лабораторную работу:

1. Для начала немного изменим структуру нашего проекта в эстетических целях. Добавим три новых файла geometry.js, model.js, graphic.js

2. Прописываем новые сценарии в файл index.html

3. В файл geometry.jsперемещаем наш конструктор vector

4. Вфайлgraphic.js – функцииset_pixel, set_line

5. В файл model.jsпереносим парсер для модели в виде функции-конструктора model, принимающую на входемассив objtext

6. В файле main.jsу нас остаются объявление переменнойajaxзапрос (без изменений) и цикл хождения по модели. Перед циклом создаем новый объект типа modelи далее обращаемся к массивам вершин и граней только через объект

7. Приступим к рисованию треугольника. Добавлям в файл graphic.js функцию triangle принимающую аргументы (v1, v2, v3, color). Функция должна уметь рисовать треугольник цвета color с вершинами v1, v2, v3. Лучше будет использовать вызов функций set_pixel, чем set_line. Также для функции, возможно, необходимо будет добавить в файл geometry.jsновые функции работы с векторами

8. Проверяем работу функции, нарисовав несколько произвольных треугольников

9. Применяем закраску треугольников для нашей модели. Для этого следует внести изменения в цикл файла main.js

10. Проверяем результат (рис. 3.3)

рис. 3.3 Модель с закрашенными полигонами

ПЛОСКАЯ МОДЕЛЬ ЗАТЕНЕНИЯ

Полученное изображение все еще не воспринимается как объемная модель. Для решения этой проблемы используют затенение. (рис. 4.1) В компьютерной графике это означает изменение цвета полигонов в зависимости от их положения к источнику света.

рис. 4.1Заливка модели цветом (слева), добавление видимых граней (центр), затенение модели (справа)

Идея алгоритма довольно проста. Каждый полигон целиком закрашивается в цвет, который рассчитывается на основании угла между нормалью полигона Nи направлением вектора светаLight.

На рисунке 4.2 видно, что свет перпендикулярный полигону, освещает его максимально ярко. А при изменении угла падения света, яркость освещения уменьшается.

Яркость можем задать коэффициентомintensity из промежутка [0, 1], который равен косинусу угла между нормалью к поверхности к вектору света .

Под вектором света в данном случае понимаем направление от изображения к наблюдателю (рис. 4.3)

рис. 4.3 При стремлении угла к 0^°,  стремится к 1 (слева), при стремлении угла к 90^°,  стремится к 0 (справа)

Вектор света  можно задать как вектор обратный направлению оси Z.

Нормаль к треугольнику может быть рассчитана как векторное произведение двух векторов, полученных из двух его сторон (рис. 4.4).

рис. 4.4 Нормаль к треугольнику