Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »
реклама
http://zagustitelvolos.com/

Почтовая рассылка

Подписчиков: 11878
Последний выпуск: 19.06.2015

Классификация алгоритмов компьютерной графики

Алгоритмы машинной графики можно разделить на два уровня : нижний и верхний. Группа алгоритмов нижнего уровня предназначена для реализации графических примитивов (линий, окружностей, заполнений и т.п.). Эти алгоритмы или подобные им воспроизведены в графических библиотеках языков высокого уровня (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). Используются некоторые регистры и переменные, назначение которых комментируется.

Начало алгоритма.  
СX=1, DX=1 - начальные  инкременты по X и по  Y 
{ вычисление вертикальной  дистанции }  
DI=y2-y1 > 0 ? Если  да, то на шаг 4, иначе  - на след.  
DX=-1, DI=-DI (дистанция по  Y должна быть > 0)  
DIAG_Y=DX - приращение по  Y для диагональных эл-тов 
{ вычисление горизонтальной  дистанции }  
SI=x2-x1 > 0 ? Если  да, то на шаг 7, иначе  - на след.  
СX=-1, SI=-SI (дистанция по  X должна быть > 0)  
DIAG_X=СX - приращение по  X для диагональных эл-тов 
{ вертикальны или горизонтальны  прямые сегменты }  
SI >= DI ? Если  да, то на шаг 9, иначе  шаг 10.  
DX=0 - для прямых сегментов  Y не меняется (т.е. они  горизонтальны).
      Переход на шаг  11.  
СX=0 - прямые сегменты  вертикальны. 
SI <-> DI - обмен  SWAP, чтобы больший отрезок  был в SI. 
{ вычисление выравнивающего  фактора }  
SHORT=DI - более короткий  отрезок 
STR_X=СX, STR_Y=DX - инкременты  для прямых сегментов (один  из них = 0) 
STR_СOUNT = 2*SHORT 
DIAG_COUNT= 2*SHORT - 2*SI 
BX=2*SHORT-SI - начальное  значение переключателя 
{ подготовка к выводу  линии } 

CX=x1, DX=y1 - начальные  координаты 
SI=SI+1 - прибавить один  пиксел для конца отрезка 
{ вывод линии }  
SI=SI-1  
SI = 0 ? Если да,  то конец алгоритма - шаг  19.  
Вывод точки с координатами  CX, DX через BIOS или  ПДП.  
BX < 0 ? Если  да, то шаг 17, иначе  18. 
{ следующий сегмент прямой  - подготовка координат для  вывода }  
CX=CX+STR_X 
DX=DX+STR_Y 
BX=BX+STR_COUNT 
переход на шаг 13 
{ след. сегмент диагональный  }  
CX=CX+DIAG_X 
DX=DX+DIAG_Y 
BX=BX+DIAG_COUNT 
переход на шаг 13  
Конец алгоритма. 

Для примера рассмотрим проведение линии по алгоритму в декартовых координатах из точки (0, 0) в точку (10, 6). Наклон прямой < 1, значит все сегменты либо горизонтальны (STR_X=1, STR_Y=0), либо диагональны (DIAG_X=1, DIAG_Y=1). Больше расстояние по X: SI = 10 (цикл по нему). Выравнивающий фактор: STR_COUNT = 12, DIAG_COUNT = -8. Начальное значение BX=2, следовательно первый сегмент будет диагональный.

Таблица значений по шагам :

   BX CX DX       BX CX  DX 
1)  2  1  1   6)   2  6   4 
2) -6  2  1   7)  -6  7   4 
3)  6  3  2   8)   6  8   5  
4) -2  4  2   9)  -2  9   5 
5) 10  5  3   10) 10 10  6  

Первая точка будет иметь координаты (0, 0), остальные - как указано в таблице (CX, DX). Нарисуйте получившуюся линию на клетчатой бумаге.

Алгоритм Брезенхема (2 вида), окружности и заполнения Вы реализуете в лабораторных работах (labs_96.mgr).

ЗАПОЛНЕНИЕ СПЛОШНЫХ ОБЛАСТЕЙ

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

Метод сканирования строк решает задачи определенного порядка сканирования, принадлежности точки внутренней области многоугольника или контура. При затравочном заполнении предполагается наличие некоторой точки, принадлежащей внутренней области (затравочная точка), для которой определяют ее соседние точки и включают ее в список других затравочных точек. Список этих точек анализируется с точки зрения необходимости их закрашивания.

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

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

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

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

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, выражающийся в лестничном эффекте и пропадании точек) используется распределенная трассировка, добавляющая высокочастотный шум по методу Монте-Карло. Вообще более сложные задачи - неточечные источники света, нечеткие отражения, глубина резкости тесно связаны с методами оптимизации.

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

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

1.
23K
29 ноября 2006 года
Alexuy
1 / / 29.11.2006
+1 / -0
Мне нравитсяМне не нравится
7 марта 2010, 08:27:54
Отличная статья
2.
54K
10 октября 2009 года
Senieur
0 / / 10.10.2009
+0 / -1
Мне нравитсяМне не нравится
10 октября 2009, 10:22:55
Спасибо за статью!
3.
28K
28 марта 2007 года
Виктор_set
0 / / 28.03.2007
Мне нравитсяМне не нравится
28 марта 2007, 21:27:48
хорошая статья она мне очень помогла,,,, спасибо....огромное
4.
Аноним
Мне нравитсяМне не нравится
28 сентября 2005, 21:01:23
Чётко и коротко. 5 , садись.
5.
Аноним
Мне нравитсяМне не нравится
29 июня 2005, 12:44:12
очень полезная статья. все сразу слепил. спасибо
6.
Аноним
Мне нравитсяМне не нравится
7 июня 2005, 16:23:43
Абалденная статья. Респект.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог