Классификация алгоритмов компьютерной графики
Алгоритмы машинной графики можно разделить на два уровня : нижний и верхний. Группа алгоритмов нижнего уровня предназначена для реализации графических примитивов (линий, окружностей, заполнений и т.п.). Эти алгоритмы или подобные им воспроизведены в графических библиотеках языков высокого уровня (BGI в Турбо - Паскале) или реализованы аппаратно в графических процессорах рабочих станций (Silicon Graphics и др.).
Среди алгоритмов нижнего уровня можно выделить следующие группы :
Простейшие в смысле используемых математических методов и отличающиеся простотой реализации. Как правило, такие алгоритмы не являются наилучшими по объему выполняемых вычислений или требуемым ресурсам памяти.
Поэтому можно выделить вторую группу алгоритмов, использующих более сложные математические предпосылки (но часто и эвристические) и отличающихся большей эффективностью.
К третьей группе следует отнести алгоритмы, которые могут быть без больших затруднений реализованы аппаратно (допускающие распараллеливание, рекурсивные, реализуемые в простейших командах). В эту группу могут попасть и алгоритмы, представленные в первых двух группах.
Наконец, к четвертой группе можно отнести алгоритмы со специальным назначением (например, для устранения лестничного эффекта).
К алгоритмам верхнего уровня относятся в первую очередь алгоритмы удаления невидимых линий и поверхностей. Задача удаления невидимых линий и поверхностей продолжает оставаться центральной в машинной графике. От эффективности алгоритмов, позволяющих решить эту задачу, зависят качество и скорость построения трехмерного изображения.
К задаче удаления невидимых линий и поверхностей примыкает задача построения (закрашивания) полутоновых (реалистических) изображений, т.е. учета явлений, связанных с количеством и характером источников света, учета свойств поверхности тела (прозрачность, преломление, отражение света).
Однако при этом не следует забывать, что вывод объектов в алгоритмах верхнего уровня обеспечивается примитивами, реализующими алгоритмы нижнего уровня, поэтому нельзя игнорировать проблему выбора и разработки эффективных алгоритмов нижнего уровня.
Для разных областей применения машинной графики на первый план могут выдвигаться разные свойства алгоритмов. Для научной графики большое значение имеет универсальность алгоритма, быстродействие может отходить на второй план. Для систем моделирования, воспроизводящих движущиеся объекты, быстродействие становится главным критерием, поскольку требуется генерировать изображение практически в реальном масштабе времени.
Особенности растровой графики связаны с тем, что обычные изображения, с которыми сталкивается человек в своей деятельности (чертежи, графики, карты, художественные картины и т.п.), реализованы на плоскости, состоящей из бесконечного набора точек. Экран же растрового дисплея представляется матрицей дискретных элементов, имеющих конкретные физические размеры. При этом число их существенно ограничено. Поэтому нельзя провести точную линию из одной точки в другую, а можно выполнить только аппроксимацию этой линии с отображением ее на дискретной матрице (плоскости). Такую плоскость также называют целочисленной решеткой, растровой плоскостью или растром. Эта решетка представляется квадратной сеткой с шагом 1. Отображение любого объекта на целочисленную решетку называется разложением его в растр или просто растровым представлением.
Построение линий, окружностей, эллипсов
Проще всего начертить линию можно с помощью уравнения y=ax+b. При этом результаты надо округлять до целых, поэтому прямая будет неровная.
Если наоборот, нужно соединить 2 точки с заданными координатами (х1, y1), (x2, y2), то:
a = (y2-y1) / (x2-x1); b = y1 - a*x1;
Уравнение окружности выглядит следующим образом:
x = xc + r*cos(a); y = yc + r*sin(a),
где (xc, yc) - координаты центра окружности, r - радиус, a - угол для текущей точки (x, y).
Можно строить окружность прямо по этому уравнению, задав определенный шаг по углу (a = 0..360 с шагом DA). Однако, если шаг будет слишком мал, окружность за счет округления координат будет неровная и некоторые точки будут высвечиваться по несколько раз. Обычно шаг по углу выбирается равным 1/r радиан, (чаще всего шаг изменения угла должен быть переменным для того, чтобы избежать разрывов или отсутствия изменения координат).
Можно осуществить простой алгоритм аппроксимации отрезками.
Например, координаты 6 отрезков получаются с шагом 60 градусов, затем они соединяются прямыми линиями.
Для быстрого построения используется симметрия окружности (вычисляются координаты точек только 1/8 части окружности - для сегмента от 0 до 45 градусов). Кроме того, можно уйти от операций синуса/косинуса, если выразить координаты следующей точки окружности из предыдущей (рекуррентная формула) :
x2 = xc + (x1-xc) * CA + (y1-yc) * SA;
y2 = yc + (y1-yc) * CA - (x1-xc) * SA, где
SA = sin(DA), CA = cos(DA).
Начальная точка для рекуррентной формулы: x1 = xc, y1 = yc+r.
При построении окружностей следует учитывать, что размеры пикселов по вертикали и горизонтали не совпадают (кроме VGA 640x480) и окружности будут вытягиваться в эллипсы. Для того чтобы избежать этого, нужно вводить по выравнивающие коэффициенты (которые можно определить по GetAspectRatio). Сами же эллипсы описываются уранениями:
x = xc + rx * cos(a); y = yc + ry * sin(a),
где rx, ry - полурадиусы.
Общие принципы построения для них те же, что и для окружностей.
Алгоритм Брезенхема
Алгоритм Брезенхема (Bresenham) был разработан в 1965 году для цифровых графопостроителей, а затем стал использоваться для растровых дисплеев.
Идея алгоритма заключается в том, что одна координата изменяется на единицу, а другая - либо не изменяется, либо изменяется на единицу в зависимости от расположения соответствующей точки от ближайшего узла координатной сетки. Расстояние от точки отрезка до ближайшего узла по соответствующей ортогональной координате называется ошибкой. Алгоритм организован таким образом, что для вычисления второй координаты требуется только определять знак этой ошибки. Величину ошибки Delta можно определить в соответствии со следующим выражением:
Delta = Yуз - Yот ,
где Yуз - координата Y ближайшего узла при X = 1, Yот - координата Y отрезка при X = 1.
Если при X = 1 координата Y точки отрезка равна 1/2, то узлы координатной сетки (1,0) и (1,1) находятся на одинаковом расстоянии от отрезка и в качестве "ближайшего" выбирается узел (1,1). Таким образом, если Yот >= 1/2, то Delta >=0, в противном случае, при Yот < 1/2, Delta < 0. Для организации вычислений удобнее пользоваться не величиной Delta, а другой, определяемой как величина d = Delta - 1/2. При изменении координаты X на 1 величина d меняется на значение углового коэффициента: d = d + dY / dX. На каждом шаге алгоритма производится вычисление координаты Х, величины d и выполняется анализ знака d. При этом, если окажется, что d >= 0, то производится увеличение Y на 1, а значение d корректируется путем вычитания из нее 1.
С учетом изложенного алгоритм аппроксимации отрезка в первом октанте можно представить в следующем виде :
Х := Х1; Y : = Y1;
dX := X2 - X1;
dY := Y2 - Y1;
d : = - 1/2;
while X =< X2 do
PutPixel (X, Y);
X := X + 1;
d := d + dY / dX;
if d >= 0 then
begin
Y := Y + 1;
d := d - 1
end
end while.
Представленный алгоритм использует вещественные числа и операцию деления. Оба недостатка можно исключить заменой величины d на другую, равную D = 2 * dX * d. В соответствии с этим арифметические выражения, в которых участвует d, модифицируются путем умножения обеих частей на величину 2 * dХ.
Тогда алгоритм принимает вид :
X := X1; Y := Y1;
dX := X2 - X1;
dY := Y2 - Y1;
D := - dX;
while X =< X2 do
PutPixel (X, Y);
X := X + 1;
D := D + 2 * dY;
if D >= 0 then
begin
Y := Y + 1;
D := D - 2 * dX;
end
end while.
Последний вариант алгоритма можно еще улучшить, если операцию умножения на 2 заменить операцией сдвига влево на один разряд. Кроме того, если вычисление 2 * dX и 2 * dY выполнить перед циклом, то операцию сдвига потребуется выполнить только два раза.
Тогда алгоритм принимает окончательный вид :
X := X1; Y := Y1;
dX := X2 - X1;
dY := Y2 - Y1;
D := - dX;
Dx := dX shl 1;
Dy := dY shl 1;
while X =< X2 do
PutPixel (X, Y);
X := X + 1;
D := D + Dy;
if D >= 0 then
begin
Y := Y + 1;
D := D - Dx
end
end while.
Оценивая достоинства полученного алгоритма, можно отметить, что он выполняет оптимальную аппроксимацию отрезка, используя при этом целочисленную арифметику и минимальное количество операций сложения и вычитания. Кроме того, алгоритм позволяет использовать его и в остальных октантах плоскости.
В алгоритме Брезенхема для всех октантов линия рассматривается как набор сегментов двух типов: тех, которые расположены диагонально и тех, которые расположены горизонтально или вертикально. Для линий с наклоном больше 1 прямые сегменты вертикальны, <= 1 - горизонтальны. Первая задача алгоритма состоит в вычислении наклона. Затем вычисляется выравнивающий фактор, который следит, чтобы некоторое число прямых сегментов имело большую длину, чем остальные. В цикле по большему отрезку (по x или по y) BX поочередно принимает то положительные, то отрицательные значения, отмечая какой тип сегмента выводится - диагональный или прямой.
В алгоритме проводится линия от (x1, y1) к (x2, y2). Используются некоторые регистры и переменные, назначение которых комментируется.
procedure Linija(x0,y0,x1,y1:Integer);
var x,y,dx,dy,ix,iy,p,i:Integer;
begin
dx:=abs(x1-x0);
dy:=abs(y1-y0);
x:=x0;
y:=y0;
If (x1-x0)<0 Then ix:=-1 //proverka napravlenija
Else ix:=1; // ix,iy - shagi dlja x, y
if y1-y0<0 Then iy:=-1 //
else iy:=1; //
If dx>=dy Then //dlja naklona <= 45 gr.
begin
p:=2*dy-dx;
for i:=1 To dx do
begin
if p>0 Then
begin
x:=x+ix;
y:=y+iy;
p:=p+2*(dy-dx);
form1.Canvas.Pixels[x,y]:=$000000;
end
else
begin
x:=x+ix;
y:=y;
p:=p+2*dy;
form1.Canvas.Pixels[x,y]:=$000000;
end;
end;
end
Else //dlja naklona > 45 gr.
begin
//
p:=2*dx-dy; //
for i:=1 To dy do //
begin //
if p>0 Then //
begin //
y:=y+iy; //
x:=x+ix; //
p:=p+2*(dx-dy);
form1.Canvas.Pixels[x,y]:=$000000; //
end //
else //
begin //
y:=y+iy; //
x:=x; //
p:=p+2*dx;
form1.Canvas.Pixels[x,y]:=$000000; //
end; //
//
ЗАПОЛНЕНИЕ СПЛОШНЫХ ОБЛАСТЕЙ
Заполнение областей может быть выполнено двумя способами- сканированием строк и затравочным заполнением.
Метод сканирования строк решает задачи определенного порядка сканирования, принадлежности точки внутренней области многоугольника или контура. При затравочном заполнении предполагается наличие некоторой точки, принадлежащей внутренней области (затравочная точка), для которой определяют ее соседние точки и включают ее в список других затравочных точек. Список этих точек анализируется с точки зрения необходимости их закрашивания.
Области могут задаваться внутренне определенным и гранично - определенным способом. Внутренне определенная область состоит из точек только одного цвета или интенсивности. Пикселы, внешние по отношению к точкам внутренне определенной области, имеют отличную от них интенсивность или цвет.
Гранично - определенные области имеют контур, состоящий из пикселов с выделенным значением цвета или интенсивности. Внутренние пикселы области отличны от них по цвету или интенсивности, а внешние могут с ними совпадать.
Внутренне и гранично - определенные области могут быть четырех- и восмисвязными. В четырехсвязных областях любой пиксел достигается движением по четырем взаимно перпендикулярным направлениям, а восьмисвязные- по восьми: горизонтальным, вертикальным и диагональным.
Можно сформировать простейший алгоритм затравочного заполнения четырехсвязной гранично - определенной области в следующем виде.
var
X,Y: integer: { координаты затравочной точки}
oldcolor: word: { исходное значение цвета}
newcolor: word: { новое значение цвета}
framcolor: word: { цвет границы}
begin
помещаем пиксел в Stack;
while (Stack не пуст) do
begin
извлекаем пиксел из Stack;
PutPixel (X, Y, newcolor) ;
для точек (Xт, Yт), соседних с (Х, Y):
(X+1, Y); (X, Y+1); (X-1, Y); (X, Y-1),
проверяем условие:
if GetPixel (Xт, Yт) = newcolor and
GetPixel (Xт, Yт) = framcolor
then помещаем (Xт, Yт) в Stack;
end
end.
Аналогично строится алгоритм и для внутренне определенной области. В этом случае меняется только условный оператор, который должен проверять принадлежность соседних точек и наличие неизмененного цвета.
Предложенные алгоритмы легко обобщаются на случай восьмисвязных областей, для которых необходимо выполнять анализ восьми соседних точек.
Процедура затравочного заполнения областей, описанная выше, обладает двумя недостатками: стек заполняется большим количеством повторяющихся точек, что приводит к существенным временным затратам при их анализе и, как следствие, требуется стек большого объема. Однако эти проблемы легко разрешить изящным методом перестановки местами операций помещения точек в стек и их закраски.
Тогда процедура будет записана следующим образом :
begin
PutPixel (X, Y, newcolor) ;
помещаем пиксел в Stack;
while (Stack не пуст) do
begin
извлекаем пиксел (X, Y) из Stack;
для точек (Xт, Yт) , соседних с (X, Y) :
(X+ 1,Y); (X, Y+1); (X-1, Y); (X, Y-1),
проверяем условие:
if GetPixel (Xт, Yт) = newcolor and
GetPixel (Xт, Yт) = framcolor
then
begin
PutPixel (Xт, Yт, newcolor);
помещаем (Xт, Yт) в Stack
end
end
end.
Другой метод повышения эффективности затравочного заполнения областей заключается в организации построчного заполнения непрерывного интервала на сканирующей строке с одной затравочной точкой.
Удаление невидимых линий и поверхностей
Сложность задачи удаления невидимых линий и поверхностей привела к появлению большого числа различных способов ее решения, различных алгоритмов, но наилучшего решения поставленной задачи не существует. Главным недостатком всех алгоритмов является значительный объем вычислений, необходимых для определения удаляемых линий и поверхностей.
В начале реализации любого алгоритма удаления невидимых линий и поверхностей для повышения эффективности его работы обычно проводится сортировка координат объектов синтезируемой сцены. Основная идея сортировки заключается в том, что, чем дальше расположен объект от точки визирования, тем больше вероятность того, что он будет полностью или частично экранироваться одним из объектов, более близких к точке наблюдения.
Алгоритмы удаления невидимых линий и поверхностей классифицируются по способу выбора систем координат или пространства, в котором они работают.
Первый класс - это алгоритмы, работаюшие в объектном пространстве, имеющие дело с физической системой координат (мировые координаты), в которой они описаны.
Второй класс алгоритмов работает в пространстве изображения и имеет дело с системой координат того устройства, на котором эти объекты синтезируются.
* - существует большое число смешанных методов, объединяющих оба подхода
Алгоритмы первого класса используются в тех случаях, когда требуется высокая точность изображения объектов. Синтезируемые в этом случае изображения можно свободно увеличивать (уменьшать) во много раз, сдвигать или поворачивать. Точность вычислений алгоритмов второго класса ограничивается разрешающей способностью экрана. Результаты, полученные в пространстве изображения, а затем увеличенные (уменьшенные) во много раз, не будут соответствовать исходной сцене.
Наиболее часто используются алгоритмы Робертса, Аппеля, Варнока, Вейлера-Азертона, алгоритм, использующий список приоритетов (упорядочений), метод Z-буфера, метод построчного сканирования.
На практике, сравнительный анализ существующих алгоритмов удаления невидимых линий крайне затруднителен. В различных случаях при работе с различными моделями синтезируемого пространства эффективны различные алгоритмы. Даже при работе с одной и той же моделью оказывается, что в зависимости от точки наблюдения следует использовать различные алгоритмы.
Для реализации алгоритмов удаления невидимых линий часто используются алгоритмы нижнего уровня - отсечения отрезка (алгоритм Сазерленда - Кохена) и алгоритм принадлежности точки многоугольнику.
Отсечение нелицевых граней
Рассмотрим задачу удаления невилимых линий для многоугогранника. Несложно заметить, что если вектор нормали грани составляет с вектором, задающим направление навблюдения, тупой угол, то эта грань заведомо не может быть видна. Тупой угол или нет, определяется знаком скалярного произведения векторов. В случае, когда сцена представляет собой один выпуклый многогранник, удаление нелицевых граней полностью решает проблему удаления невидимых линий (в общем случае позволяет значительно сократить кол-во рассматриваемых граней).
Алгоритм Робертса
Самым первым алгоритмом, предназначенным для удаления невидимых линий был алгоритм Робертса. Сначала в нем отбрасываются все ребра, обе определяющие грани которых являются нелицевыми. Следующим шагом является проверка оставшихся ребер со всеми гранями многогранника на закрывание.
Возможны следующие случаи :
грань не закрывает ребро;
грань полностью закрывает ребро;
грань частично закрывает ребро (в этом случае ребро разбивается на несколько частей, из к-рых видимыми являются не более двух)
Алгоритм Аппеля
Этот алгоритм основан на понятии количественной невидимости точки, как кол-ва лицевых граней, ее закрывающих. Точка является видимой только в том случае, если ее количественная невидимость = 0.
Метод Z-буфера
Одним из самых простых алгоритмов удаления невидимых граней и поверхностей является метод Z-буфера (буфера глубины). В силу крайней простоты этого метода (OpenGL) часто встречаются его аппаратные реализации.
Сопоставим каждому пикселу (x, y) картинной плоскости его расстояние вдоль напрвления проектирования z(x, y) - его глубину. Изначально массив глубин инициализирутся бесконечностью. Для вывода на картинную плоскость произвольной грани она переводится в свое растровое представление и для каждого пиксела этой грани находится его глубина. В случае, если эта глубина меньше значения глубины, хранящегося в Z-буфере, то этот пиксел рисуется и его глубина заносится в Z-буфер.
Алгоритмы упорядочения
Подход заключается в таком упорядочении граней, чтобы при их выводе в этом порядке получалось корректное изображение. Для этого необходимо, чтобы дальние грани выводились раньше, чем более близкие (используются методы сортировки по глубине и двоичного разбиения пространства).
Метод построчного сканирования
x
Это еще один пример метода, работающего в простанстве картинной плоскости. Все изображение на картинной плоскости можно представить как ряд горизонтальных (вертикальных) линий пикселов. Рассмотрим сечение счены плоскостью, проходящей через такую линию пикселов и центр проектирования. Пересечением этой плоскости с объектами сцены будет множество непересекающихся (за исключением концов) отрезков, к-рые и небходимо спроектировать. Задача удаления невидимых линий для такого набора отрезков решается тривиально.
Т.о. исходная задача удаления невидимых граней разбивается на набор гораздо более простых задач. Подобные алгоритмы успешно применяются для создания компьютерных игр (Wolfenstein 3D).
Принципы построения полутоновых изображений
Световая энергия, падающая на пов-ть от источника света, может быть поглощена, отражена или пропущена. Количество энергии зависит от длины световой волны. При этом цвет пов-ти объекта определяется поглощенными длинами волн.
Разработано множество способов закрашивания : гранением, пропорциональное закрашивание, закрашивание по способу Гуро, закрашивание по способу Фонга, закрашивание способом трассировки лучей (лучей зондирования). Эти способы требуют различного количества процессорного времени и, следовательно, обеспечивают различное качество изображения.
Самый простой способ закрашивания назывется гранением (faceting). Он требует сравнительно небольших ресурсов компьютера, поскольку предполагает лишь заполнение каждого из многоугольников одним цветом или оттенком. Однако способ слишком примитивен; закрашенные этим способом объекты выглядят не плавными.
Линейное, или пропорциональное закрашивание, предполагает изменение освещенности в пределах каждого многоугольника и благодаря этому позволяет воспроизводить более реалистичные изображения. Здесь яркость и цветовая насыщенность элементов каждого многоугольника плавно меняются в интервале между значениями, вычисленными для его вершин. При этом поверхности воспроизводимых предметов преобретают идеальную сюрреалистическую гладкость, как будто мы видим их при непрямом освещении.
Более реалистические изображения получаются в случае, если яркость и цветовая насыщенность каждого многоугольника плавно меняется не только от угла к углу, но и вдоль его ребер.
Такое закрашивание носит название способа Гуро и осуществляется в четыре этапа:
*вычисление нормалей к поверхности;
*определение нормалей в вершинах путем усреднения нормалей по граням, которым принадлежит данная вершина;
вычисление интенсивности в вершинах;
*закрашивание многоугольника путем линейной интерполяции значений интенсивности вдоль ребер и между ребрами.
*Основной недостаток - эффект полосы Маха : на ребрах смежных многоугольников возникает полоса разрыва непрерывности.
Закрашивание по способу Фонга решает проблемы полосы Маха, поскольку предполагает плавное изменение яркости и насыщенности не только вдоль ребер каждого многоугольника, но и по самой поверхности (вдоль сканирующей строки интерполируется значение вектора нормали, который затем используется в модели освещения для вычисления интенсивности пиксела). При этом даже зеркальные блики на поверностях выглядят вполне правдоподобно (в 3D Studio 4.0 помимо методов Гуро и Фонга добавилось еще закрашивание Metal).
Однако наиболее реалистичные изображения в трехмерной машинной графике обеспечивает закрашивание способом трассировки лучей, которое позволяет учесть такие эффекты, как отражение и преломление, наложение текстур.
Выпустим из каждого источника света пучок лучей во все стороны и мысленно проследим (оттрассируем) дальнейшее распространение каждого из них до тех пор, пока лиюо он не попадет в глаз наблюдателя, либо не покинет сцену. При попадпнии луча на границу объекта выпускаем из точки попадания отраженный и преломленный лучи и отслеживаем их и все порожденные ими лучи. Описанный выше процесс называется прямой трассировкой лучей. В результате его выполнения можно получить изображение сцены, однако он требует огромных вычислительных затрат. Причем, в получаемое изображение вносит вклад лишь небольшая часть трассируемых лучей. Чтобы избежать этого, попытаемся отследить лишь те лучи, которые попадают в глаз наблюдателя. Проследим путь луча, выходящего из глаза наблюдателя и проходящего через соответсвующую точку экрана. Цвет соответствующей точки экрана будет определяться долей световой энергии, попадающей в эту точку и покидающей ее в направлении глаза. Для этого из нее выпускаются лучи в тех направлениях, из которых может прийти энергия. Это, в свою очередь, может привести к определению точек пересечения соответствующих лучей с объектами сцены, выпускания новых лучей и т.д.
Описанный процесс называется обратной трассировкой лучей или просто трассировкой лучей. Именно этот метод и применяется в компьютерной графике.
Для придания более естственного вида сцене желательно иметь возможность менять параметры поверхности (в простейшем случае - цвет).
Существуют разные способы моделирования текстуры :
*проективные текстуры
*процедурные (сплошные) текстуры.
В первом случае образец текстуры проецируется на пов-ть параллельным переносом (плоское проектирование), либо цилиндрическим или сферическим методом. Недостатки проективных текстур - большой объем памяти для хранения образцов текстур, небольшая гибкость и трудность текстурирования объектов сложной формы.
Второй путь не требует больших затрат памяти и работает с объектами любой формы. Но поскольку подобранная функция может зависеть от большого числа переменных, основным недостатком является ее сложность.
Для удаления погрешностей метода трассировки лучей (aliasing, выражающийся в лестничном эффекте и пропадании точек) используется распределенная трассировка, добавляющая высокочастотный шум по методу Монте-Карло. Вообще более сложные задачи - неточечные источники света, нечеткие отражения, глубина резкости тесно связаны с методами оптимизации.
Основным недостатком метода трассировки лучей является то, что с изменением положения наблюдателя необходимо пересчитывать всю сцену (кроме этого неэффективность работы при диффузном отражении). Метод излучательности основан на законе сохранения энергии в замкнутой системе и производит вычисление глобальной освещенности независимо от положения наблюдателя. Все объекты разбиваются на фрагменты и для этих фрагментов составляются уравнения баланса энергии.
источники http://www.codenet.ru/progr/alg/alg.php
личные ресурсы
Это не просто буквы, а осмысленный текст.
