«В.М. Гасов, А.М. Цыганенко ТРЕХМЕРНАЯ ГРАФИКА В МЕДИАИНДУСТРИИ Учебник Допущено УМО по образованию в области полиграфии и книжного дела для студентов высших учебных заведений, обучающихся по специальностям: 230102.65 – ...»

В противном случае определить z для списка пересечений.

Вычислить преобразование, обратное комбинированному преобразованию.

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

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

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

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

Вводятся сферические оболочки для групп или кластеров связанных объектов, например для вазы и всех плодов в ней, для блюда и всех конфет в нем, а также для стола и всех предметов на нем. Сферические оболочки, охватывающие более чем один объект, называются сферическими кластерами. Если это необходимо, то можно ввести и прямоугольные кластеры. Вводится, кроме того, наибольший сферический кластер, именуемый сферой сцены, которая охватывает все объекты в этой сцене. Затем сферические оболочки обрабатываются в иерархическом порядке. Если луч не пересекает сферу сцены, то он не может пересечь и ни одного из ее объектов. Следовательно, пиксел, соответствующий этому лучу, будет изображен с фоновым значением интенсивности. Если же луч пересекает сферу сцены, то на пересечении с лучом проверяются сферические кластеры и сферические оболочки объектов, не содержащихся ни в одном из сферических кластеров, принадлежащих кластеру сцены. Если луч не пересекает сферический кластер, то сам этот кластер и все объекты или кластеры, содержащиеся в нем, исключаются из дальнейшего рассмотрения. Если же луч пересекает кластер, то эта процедура рекурсивно повторяется до тех пор, пока не будут рассмотрены все объекты. Если луч пересекает сферическую оболочку некоего объекта в какой-нибудь точке, то этот объект заносится в список активных объектов. Эта процедура значительно сокращает количество вычислений точек пересечения луча со сферическими оболочками и тем самым повышает эффективность всего алгоритма.

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

Пересечения луча с объектами из списка пересеченных объектов определяются в порядке их приоритетов. К сожалению, точка пересечения луча с первым из объектов в упорядоченном по приоритетам списке пересеченных объектов необязательно будет видимой. Необходимо определить точки пересечения луча со всеми потенциально видимыми объектами из множества {Q} и занести их в список пересечений. Затем модифицированный алгоритм упорядочивает этот список пересечений так, как это делалось и в простом алгоритме. К счастью, множество {Q} потенциально видимых объектов обычно значительно меньше числа объектов в списке пересеченных лучом. Следовательно, эффективность алгоритма возрастет. Обе эти модификации применимы также и к общему алгоритму трассировки лучей, учитывающему отражение, преломление и прозрачность.

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

Д. Рот указал, что алгоритм трассировки лучей можно использовать также и для создания каркасных чертежей сплошных тел.

При этом предполагается, что лучи порождаются в том порядке, в каком происходит сканирование экрана, т. е. сверху вниз и слева направо. Получающаяся процедура такова: если видимая поверхность для пиксел (x, y) соответствует фону или отличается от видимой поверхности для пиксел (x – 1, y) или для пиксел (x, y – 1), то изобразить этот пиксел. В противном случае пиксел не изображать.

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

Это можно проделать, породив множество параллельных лучей, расположенных на определенных расстояниях друг от друга.

Точки пересечения каждого луча с заданным объемом вычисляются и упорядочиваются вдоль направления этого луча. Если подвергнуть луч переносу, совмещающему его с осью z, как это было описано выше, то объем каждого прямоугольного параллелепипеда будет равен где lx и ly – расстояние между лучами по горизонтали и вертикали соответственно. Каждое слагаемое (zi-1 + zi) представляет собой участок луча, лежащий внутри заданного тела. Объем тела, следовательно, равен сумме объемов всех таких прямоугольных параллелепипедов. Точность результатов зависит от числа использованных лучей. Точность можно повысить, умеренно увеличив объем вычислений и рекурсивно уменьшив размер «пиксела», в том случае, если объемы смежных прямоугольных параллелепипедов различаются более чем на заранее заданную величину. При таком подходе точнее определяются объемы тех элементов тела, где имеют место быстрые изменения, например, в окрестностях ребер тел, ограниченных криволинейными поверхностями.

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

Алгоритм предложен Эдом Кэтмулом и представляет собой обобщение буфера кадра. Обычный буфер кадра хранит коды цвета для каждого пиксела в пространстве изображения. Идея алгоритма состоит в том, чтобы для каждого пиксела дополнительно хранить еще и координату Z или глубину. При занесении очередного пиксела в буфер кадра значение его Z-координаты сравнивается с Z-координатой пиксела, который уже находится в буфере.

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

Алгоритм работает в параллельной проекции. Пусть размеры окна вывода или экрана составляют X точек в ширину и Y точек в высоту. В качестве z-буфера заведем двухмерный прямоугольный массив чисел, по размерности совпадающий с окном вывода или экрана, т. е. XY. В z-буфере будут храниться текущие значения Z-координат каждого пиксела.

В начале работы алгоритма в z-буфер заносятся значения, соответствующие бесконечности. Каждая грань трехмерного объекта, представленная в виде многоугольника, преобразуется в растровую форму. При разложении в растр для каждой точки многоугольника вычисляется значение ее Z-координаты. Если Z-координата оказалась меньше чем текущее значение в z-буфере, то в z-буфер заносится Z-координата точки, и на экране рисуется точка цветом текущего многоугольника. После разложения в растр всех многоугольников, изображение трехмерной сцены построено.

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

Выразим Z-координату точки:

z0 = f (x0, y0). Найдем z-координату для соседней точки Пусть Для соседнего пиксела на экране Dx = 1, тогда AC x = Const, отсюда следует, что z1 = z0 - Const. Таким образом, вычисление Z-координаты соседнего пиксела сводится к одной операции вычитания.

Общая схема алгоритма с z-буфером:

• Инициализировать кадровый и z-буфера. Кадровый буфер закрашивается фоном. z-буфер закрашивается минимальным значением Z.

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

• Выполнить, если это было предусмотрено, усреднение изображения с понижением разрешения.

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

Алгоритм производит обход восьмеричного дерева, начиная с вершины, и для каждого узла определяет, попадает ли он в пирамиду видимости. Если да, то определяет, видны ли грани куба, соответствующего этому узлу, и если видны, то производит аналогичную обработку для дочерних узлов, вплоть до того, пока не будут достигнуты листья дерева. Тогда ассоциированная с ними геометрия выводится на экран.

Алгоритм построения восьмеричного дерева 1. Вся сцена помещается в куб с гранями, параллельными координатным плоскостям.

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

3. Каждый из получившихся восьми кубов рекурсивно делится еще на восемь кубов и т. д.

4. В каждой ветке деление прекращается, либо когда достигается заранее определенная глубина дерева, либо когда в очередном кубе количество примитивов становится меньше заранее определенного порога.

5. Примитивы сцены ассоциируются с кубами, соответствующими листьям получившегося дерева.

6. При обработке примитивов, которые разбиваются секущими плоскостями можно:

• ассоциировать разбиваемый примитив с родительским кубом;

• разбивать примитив и каждую его часть ассоциировать с соответствующим листом;

• не разбивая примитив, ассоциировать его со всеми листьями, в которые он попадает.

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

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

Z-пирамида – это иерархия карт глубины. Каждый следующий уровень иерархии имеет разрешение в два раза меньше предыдущего уровня и строится на его основе. В качестве самого нижнего уровня выступает z-буфер. Из каждой четверки соседних значений с нижнего уровня выбирается самое большое значение, то есть соответствующее самой далекой точке, и помещается в элемент следующего уровня. На рис. 6.15 это проиллюстрировано для z-буфера размером 44 пикселей.

Определение видимости грани куба осуществляется следующим образом:

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

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

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

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

Алгоритм имеет логарифмическую сложность и основывается на возможности быстро выяснить, будет ли точка видима, если ее визуализировать.

Зачастую, когда просчитывается проекция сложной модели на двухмерную плоскость с использованием восьмеричного дерева, только малая часть кубических подпространств из состава дерева остается видимой. Если начать просчитывать следующий кадр анимации, то можно с большой вероятностью утверждать, что большинство кубов, видимых в предыдущем кадре, будет видимо и в следующем. Некоторые из видимых кубов станут невидимыми, а некоторые наоборот, но когерентность между соседними кадрами в большинстве анимации достаточно велика и только небольшое количество кубов изменит свой статус при переходе между соседними кадрами (если конечно не произошла полная смена всей сцены). С помощью иерархического алгоритма реализуется и эта зависимость. Создав первый кадр, создается и сохраняется перечень видимых кубов из него в виде списка. Перейдя к формированию следующего, перед тем как с самого начала запустить иерархический алгоритм для нового кадра, проводится рендеризация геометрии, содержащейся в подпространствах из созданного списка. Кубы, геометрия которых уже просчитана, помечаются как «rendered». На базе получившегося в результате этой операции z-буфера создается начальная z-пирамида. Тогда при достаточной когерентности между кадрами затрачивается значительно меньше времени на работу алгоритма, т. к. большая часть геометрии уже будет рендеризована.

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

Данный метод является простым усовершенствованием метода z-буфера. Различие состоит в том, что в буфере вместо значения глубины хранится величина, обратная величине глубины.

Благодаря этому количество расчетов сокращается.

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

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

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

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

Для этого необходимо, чтобы более дальние грани выводились раньше, чем более близкие.

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

Основные алгоритмы упорядочения рассматриваются ниже.

Метод двоичного разбиения пространства Рассмотрим некоторую плоскость в объектном пространстве.

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

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

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

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

В результате получаем дерево разбиения пространства (Binary Space Partitioning), узлами которого являются грани.

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

В этом процессе присутствует определенный произвол в выборе очередной грани. Существует два основных критерия для выбора:

• получение как можно более сбалансированного дерева;

• минимизация количества разбиений.

К сожалению, эти критерии, как правило, являются взаимоисключающими, поэтому выбирается некоторый компромиссный вариант.

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

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

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

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

1) если две оболочки не пересекаются, тогда не пересекаются и многоугольники;

2) оболочки пересекаются. Здесь многоугольники могут пересекаться и требуются дополнительные исследования.

На первом этапе работы алгоритма все грани сортируются по глубине расположения самых дальних вершин каждой грани.

Если грани не перекрываются, то эта сортировка устанавливает верный порядок следования граней (рис. 6.16).

Далее следует специальная сортировка, которая проверяет, действительно ли список составлен в нужном порядке. Если это не так, то список соответствующим образом приводится в порядок.

Проверяется последняя грань P в списке. Если ближайшая вершина P расположена дальше по глубине, чем самая отдаленная, то грань P не может загораживать Q и какую-либо другую грань списка. Грань P может быть записана в буферную память регенерации кадра. Если это условие не выполняется, то проводится проверка из пяти тестов:

1. X-оболочки граней не пересекаются.

2. Y-оболочки граней не пересекаются.

3. P целиком лежит с той стороны Q, которая дальше от точки зрения.

4. P целиком находится с той стороны от Q, которая ближе 5. Проекции многоугольников на экране не пересекаются.

Если во всех пяти тестах получен отрицательный ответ, то P закрывает Q, поэтому P и Q меняются местами в списке, а на грани Q ставится метка (рис. 6.17).

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

На рис. 6.18 показан способ разрешения подобного конфликта. Грань Q разделена плоскостью P на две грани Q а и Qb. Эти грани помещаются в список граней и затем рассматривается последовательность Qа Р, Qb.

Оперирует в картинной плоскости и основывается на использовании растра сканирующих прямых, накладываемых на изображение. Изображение представляет собой ортогональные проекции плоских граней трехмерных объектов. Сканирующие прямые горизонтальны. На первом шаге производится сортировка негоризонтальных ребер и граней. Сортировка осуществляется на основе меньшей Y-координаты ребра. На втором шаге производится сортировка по X-координате. Для каждой линии развертки исследуется рассортированная по y структура с целью обнаружения новых ребер, которые заходят за данную линию развертки.

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

Все это можно разбить на 4 шага:

• сортировка по у;

• сортировка по x;

• выбор отрезков;

• определение глубины по оси.

Алгоритмы отсечения невидимых граней Алгоритм удаления нелицевых граней Сначала формируется приоритетный список тел в сцене, т. е.

проводится сортировка по z.

Для каждого тела в сцене:

1. Формируются многоугольники граней и ребра, исходя из списка вершин тела.

2. Вычисляется уравнение плоскости для каждой полигональной грани тела.

3. Проверяется знак уравнения плоскости.

3.1. Берется любая точка внутри тела, например, после усреднения координаты его вершин.

3.2. Вычисляется скалярное произведение уравнения плоскости и точки внутри тела.

3.3. Если это скалярное произведение больше 0, формируется 3.4. Умножают ее слева на матрицу, обратную матрице видового преобразования, включающего перспективу.

4. Вычисляются и запоминаются габариты прямоугольной объемлющей оболочки преобразованного объема: x min, x max, y min, y max.

5. Определяются нелицевые плоскости:

5.1. Вычисляется скалярное произведение пробной точки, лежащей в бесконечности, на преобразованную матрицу 5.2. Если это скалярное произведение меньше 0, удаляется весь многоугольник, лежащий в этой плоскости. Это избавляет от необходимости отдельно рассматривать невидимые линии, образуемые пересечением пар невидимых 6. Удаляются из каждого тела те ребра, которые экранируются всеми остальными телами в сцене.

Рассмотрим работу этого алгоритма на примере, который изображен на рис. 6.19.

Рис. 6.19. Пересечения прямой AB с плоскостями граней призмы Пусть наблюдатель находится в точке A. Выберем точку B, которая заведомо является внутренней для выпуклой фигуры, в данном случае призмы. Выберем некоторую грань, про которую мы хотим узнать видима она из точки A, или не видима. Построим плоскость, в которой лежит выбранная грань. Найдем точку пересечения плоскости и прямой, которая образована отрезком AB. Если точка пересечения прямой и плоскости лежит внутри отрезка AB, то делаем вывод, что данная грань видима. Если точка пересечения находится вне отрезка AB, то грань не видима. В случае, когда прямая и плоскость параллельны, считаем что грань не видима.

В алгоритме Ходжмана весь многоугольник последовательно отсекается каждой границей окна, как это показано на рис. 6.20.

изображение Рис. 6.20. Последовательное отсечение многоугольника сторонами окна При отсечении ребра, соединяющего очередную пару вершин K и, возможны 4 случая взаимного расположения (рис. 6.21):

• ребро на внутренней стороне границы;

• ребро выходит из окна наружу;

• ребро на внешней стороне границы;

• ребро входит снаружи в окно.

Рис. 6.21. Относительные расположения ребра и границы окна В случае а в результат добавляется вершина L; в случае б в результат заносится S-точка пересечения ребра с границей; в случае в нет вывода, а в случае г выдаются точка пересечения S и конечная точка ребра L.

Для определения взаимного расположения и направленности используется векторное произведение вектора P1P2, проведенного из начальной в конечную точку текущего ребра окна, на вектор b > P1S из начальной точки текущего ребра окна в очередную вершину S многоугольника (рис. 6.22).

Рис. 6.22. Определение взаимного расположения окна и вершины Если P1P2 P1S < 0, то поворот от P1P2 к P1S по часовой стрелке, т. е. точка S внутри окна. Если P1P2 P1S > 0, то поворот от P1P2 к P1S против часовой стрелки, т. е. точка S вне окна.

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

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

В случае пересечения границ отсекаемого многоугольника и окна возникают точки двух типов:

• входные точки, когда ориентированное ребро отсекаемого многоугольника входит в окно;

• выходные точки, когда ребро отсекаемого многоугольника идет с внутренней на внешнюю стороны окна.

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

1. Строятся списки вершин отсекаемого многоугольника и окна.

2. Отыскиваются все точки пересечения. При этом расчете касания не считаются пересечением, т. е. когда вершина или ребро отсекаемого многоугольника инцидентна или совпадает со стороной окна (рис. 6.23 и 6.24).

3. Списки координат вершин отсекаемого многоугольника и окна дополняются новыми вершинами – координатами точек пересечения. Причем, если точка пересечения Pk находится на ребре, соединяющем вершины Vi, Vj, то последовательность точек Vi, Vj превращается в последовательность Vi, Pk, Vj. При этом устанавливаются двухсторонние связи между одноименными точками пересечения в списках вершин отсекаемого многоугольника и окна. Входные и выходные точки пересечения образуют отдельные подсписки входных и выходных точек в списках вершин.

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

• Если не исчерпан список входных точек пересечения, то выбирается очередная входная точка.

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

5. Используя двухстороннюю связь точек пересечения, переключаются на список вершин обрабатываемого многоугольника.

6. Эти действия повторяются, пока не будет достигнута исходная вершина – очередная часть отсекаемого многоугольника, попавшая в окно, замкнулась.

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

Рис. 6.23. Случаи, не считающиеся пересечением Модификация этого алгоритма для определения части отсекаемого многоугольника, находящейся вне окна, заключается в следующем:

• исходная точка пересечения берется из списка выходных точек;

• движение по списку вершин окна выполняется в обратном порядке, т. е. так, чтобы внутренняя часть отсекателя была слева.

На рис. 6.25 иллюстрируется отсечение многоугольника ABCDEFGHI окном PQRS по алгоритму Азертона.

Рис. 6.25. Отсечение невидимых граней по алгоритму Азертона

МЕТОДЫ СОЗДАНИЯ

РЕАЛИСТИЧНЫХ ИЗОБРАЖЕНИЙ

На сегодняшний день использование трехмерной графики вышло уже далеко за пределы сферы только информационных технологий. Кинематограф, компьютерные игры и тренажеры, архитектура и строительство, машиностроение, медицина и биология — это далеко не полный перечень областей, в которые глубоко проникла 3D-медиаиндустрия. Некоторые отрасли человеческой деятельности (как, например, дизайн, мультипликация, компьютерные игры) уже просто невозможно представить без реалистичных 3D-изображений или анимации. Математические зависимости, описывающие формирование цифровой модели реальных объектов, а также алгоритмы для просчета освещения трехмерных сцен (областей виртуального пространства, содержащих трехмерные объекты и источники света), разработаны еще в 60-х годах прошлого века.

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

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

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

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

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

Начнем с источников света. Они бывают:

• Точечные источники света (omni), которые излучают свет по всем направлениям. Отсюда они и получили свое название. При их задании необходимо определять их положение в пространстве.

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

• Направленный свет (directional). Он представляет собой свет, идущий из одного определенного направления, обычно задаваемого либо в векторной форме, либо при помощи координат двух точек, лежащих на одном из его параллельных лучей.

Подобная модель напоминает фактически параллельные друг другу при освещении объектов на Земле солнечные лучи. Угол между этими лучами и нормалью к поверхности играет ту же роль, что и в остальных моделях освещения.

• Существует фоновое освещение, или (background) – это окружающее объект освещение от удаленных источников, чье положение и характеристики не известны.

Затенение – техника интерполяции для снижения количества вычислений при расчете освещенности. Параметры, которые интерполируются при затенении, обычно называются интерполянтами. Интерполянтами могут быть как скаляры (например, R,G,B компоненты цвета), так и векторы (например, нормали).

Локальная модель освещенности. Фоновая освещенность, диффузное и зеркальное отражение.

Рис. 7.1. Освещение сцены Рис. 7.2. Освещение сцены с одним источником света с одним источником света без учета отраженного света с учетом отражения света К настоящему моменту разработано несколько моделей освещенности. Самая первая, и самая простая – локальная модель освещенности. Эта модель не рассматривает процессы светового взаимодействия объектов сцены между собой, а только помогает произвести расчет освещенности самих объектов.

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

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

В самом общем случае, с учетом требования фотореалистичности, эта модель должна также учитывать и неявное освещение.

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

Интенсивность такого освещения постоянна и равномерно распределена во всем пространстве, расчет его отражения поверхностью выполняется по формуле где Iamb – интенсивность отраженного света; ka – коэффициент, характеризующий отражающие свойства поверхности в пределах от 0 до 1; Ia – исходная интенсивность фонового света, падающего на поверхность.

Часть света от прямых источников зеркально отражается поверхностью, а остальной свет диффузно рассеивается (diffuse reflection) во всех направлениях. Представителем таких моделей является, например модель Ламберта.

Кроме чисто зеркального отражения, которое имеют идеально отполированные поверхности, различают так называемое распределенное зеркальное отражение (glossiness) – отражение в некотором створе углов, а не на один единственный угол. Такое рассеяние света обусловлено микрорельефом («шероховатостью») поверхности, то есть поверхность реальных объектов не является идеально гладкой, а состоит из большого количества микровыступов и впадин, которые зеркально отражают падающий свет под разными углами. Результатом glossy-отражения является яркий световой блик (specular highlight), имеющий размер в зависимости от степени шероховатости поверхности.

Свет отражается равномерно под всеми углами Рис. 7.4. Зеркальное отражение под одним идеальным углом и glossy-отражение в створе углов, обусловленное шероховатостью поверхности Интенсивность рассеянного света зависит от угла падающего на поверхность света по закону Ламберта (Lambert):

где Id – интенсивность падающего на поверхность света; kdiff – коэффициент, характеризующий рассеивающие свойства поверхности (его значение изменяется в пределах от 0 до 1), cos() – угол между направлением на источник света и нормалью поверхности.

Рис. 7.5. Угол между направлением на источник света Другими словами, поверхность будет освещена больше, если свет падает на нее перпендикулярно ( = 0), и меньше, если свет падает под любым другим углом, поскольку в этом случае увеличивается освещаемая площадь.

Диффузно рассеянный свет является главным источником визуальной информации о геометрии трехмерных объектов.

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

где Ispec – интенсивность зеркально отраженного света; Is – интенсивность источника света; ks – коэффициент, характеризующий свойства зеркального отражения поверхности; – угол между направлением идеального отражения и направлением на наблюдателя, степень n определяет размер пятна светового блика – чем больше n, тем меньше световой блик, и тем ближе отражающие свойства поверхности к свойствам идеального зеркала.

Рис. 7.6. Угол между направлением идеального отражения Таким образом, локальная модель освещенности предполагает расчет отраженной фоновой освещенности, диффузного и зеркального отражения от прямых источников:

= ka # Ia + 1/(a + br + cr 2) (Id # kdiff # cos ) + Is # ks # cos n ().

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

Описанные выше модели хороши тем, что они просты в реализации даже на графических акселераторах. Но они не годятся для достижения достаточной реалистичности в сложных сценах.

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

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

Если бы было возможным применять модель освещенности для расчетов в каждой точке поверхности, необходимость в создании моделей затенения попросту не возникла. Однако такой расчет очень расточителен в отношении вычислительных ресурсов компьютерной системы, а, следовательно, неприемлем. На практике расчет освещенности выполняется не для всех точек поверхности, а лишь для некоторых из них. Задача моделей затенения (shading) состоит в том, чтобы «правильно» определить эти точки и аппроксимировать результат «честных» вычислений модели освещения в этих точках на всю поверхность с соблюдением принципа фотореалистичности.

7.2.1. Модель затенения Flat-shading Самая первая и самая быстрая модель затенения, разработанная в компьютерной графике – Flat shading, в настоящее время мало используется и имеет скорее историческое значение.

Суть Flat-затенения состоит в том, что освещенность рассчитывается только для одной точки полигона, и затем рассчитанное значение просто присваивается всему полигону (всем точкам полигона). Более точно для поверхности каждого полигона рассчитывается нормаль, с помощью которой и вычисляется общая для одного полигона освещенность. Таким образом, цвет в пределах одного полигона неизменен и резко меняется на границах между разными полигонами, в результате чего трехмерная поверхность приобретает типичный «граненый» вид.

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

Модель была разработана в 1971 году. Автором модели является Henry Gauroud, отсюда и название модели. В этой модели освещенность рассчитывается для каждой вершины полигона, а полученный цвет интерполируется сначала вдоль границ полигона и затем – для внутренних точек. Затенение Гуро является наиболее общим методом для аппаратной реализации. Затенение Гуро не учитывает перспективу, поэтому для большей реалистичности требуется перспективная коррекция. Синоним затенения Гуро – вершинное освещение, так как освещенность рассчитывается только для вершин. Для расчета освещенности вершины используется нормаль, получаемая усреднением нормалей всех полигонов, для которых данная вершина является общей.

Расчет достаточно прост и дает сглаженные цветовые переходы на всей поверхности и позволяет вычислять зеркальные подсветки.

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

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

Последнее обстоятельство обусловило широкое применение этой модели в приложениях реального времени, например – эта модель принята по умолчанию в OpenGL. Видовые окна 3ds max, Maya и других программ 3D-моделирования также отображают объекты с применением затенения Гуро.

Затенение Гуро имеет существенный недостаток – ему свойственен артефакт под названием «stars» (звезды). Если вглядеться в изображение шара (рис. 7.7), затененного по Гуро, то белый блик, который в идеале должен иметь форму эллипса, имеет форму звезды. Кроме этого, подсветки иногда могут исчезать, если попадают на внутреннюю точку полигона. Еще одним существенным недостатком является зависимость результата интерполяции от поворотов. Причина тому – в интерполяции цвета вдоль сканирующей линии, при повороте полигона относительно которой расчет цвета одного и того же пиксела осуществляется с использованием разных границ полигона. Кроме того, в модели затенения по Гуро также могут проявляться проблемы с перспективой.

Эта модель была разработана в 1975 году. Автором является Phong Biu-Thuong, отсюда и название модели. Модель затенения по Фонгу вычисляет с помощью локальной модели освещенности интенсивность для каждого пиксела поверхности. Для этого, как и в модели Гуро, находятся нормали всех вершин полигона, затем эти нормали интерполируются вдоль границ полигона и для внутренних точек полигона – вдоль сканирующей линии, подобно тому, как интерполировалась интенсивность освещения в модели Гуро. И уже затем для каждого пиксела полигона рассчитывается освещенность.

Интерполяция нормалей вместо интенсивностей решает вопрос с подсветками – поскольку теперь известна нормаль в каждой точке поверхности, интенсивность можно рассчитать точно. Рассчитанные при помощи модели затенения Фонга нормали высокополигонной модели можно сохранить как специальную растровую карту (карту нормалей) и затем накладывать ее на низкополигонную модель – присваивать каждому пикселу низкополигонной модели нормаль, рассчитанную на высокополигонной модели. В результате, рендер (rendering – визуализация) низкополигонной модели будет почти таким же качественным, как и рендер высокополигонной модели.

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

7.2.5. Модель затенения Cook-Torrance Модель является логичным развитием модели Blinn, делая подсветку зависящей еще и от длины волны. Эта модель позволяет получать дополнительные цветовые переходы на краях подсветки для шероховатых металлических и пластиковых материалов.

7.2.6. Модель затенения Ward (anisotropic shading) Эта модель позволяет определять преимущественное направление шероховатостей поверхности и позволяет изменять форму подсветки в зависимости от этого направления.

Обеспечивает сглаженность цветовых переходов при высокой скорости вычислений. Последнее обстоятельство обусловило широкое применение этой модели в приложениях реального времени, например – эта модель принята по умолчанию в OpenGL. Видовые окна 3Ds max, Maya и других программ 3D-моделирования также отображают объекты с применением затенения Гуро. Но эта модель имеет и ряд серьезных недостатков, главным среди которых является неверное отображение подсветок, особенно если поверхность низкополигонная. Во-первых, подсветки имеют «звездообразную» форму и часто визуально проявляют полигональную структуру поверхности. Во-вторых, подсветки просто-напросто могут внезапно исчезать, если попадают на внутреннюю точку полигона и т. д. Понаблюдать за этими явлениями можно в видовом окне 3Ds max, вращая низкополигонную сферу. Второй существенный недостаток – зависимость результата интерполяции от поворотов.

Причина тому – в интерполяции цвета вдоль сканирующей линии.

Что касается теней, то поскольку локальная модель освещенности не рассматривает взаимодействие объектов между собой, тени просчитываются при помощи некоторых искусственных процедур. Например, рендер генерирует растровое изображение (теневую карту, shadow map) объекта и затем проектирует ее по направлению от источника к объекту. Такие тени не могут учитывать цвет, прозрачность и другие сложные свойства объектов.

7.2.7. Классический ray tracing, или метод трассировки лучей Предложен Артуром Аппелем (Arthur Appel) еще в 1968 году и дополнен алгоритмом общей рекурсии, разработанным Whitted в 1980 году. Понадобилось почти 12 лет эволюции вычислительных систем, прежде чем этот алгоритм стал доступен для широкого применения в практических приложениях. Суть метода заключается в отслеживании траекторий лучей и расчета взаимодействий с лежащими на траекториях объектами, от момента испускания лучей источником света до момента попадания в камеру. Под взаимодействием луча с объектами понимаются процессы диффузного (в смысле модели локальной освещенности), многократного зеркального отражения от их поверхности и прохождение лучей сквозь прозрачные объекты. Таким образом, ray tracing – первый метод расчета глобального освещения, рассматривающий освещение, затенение (расчет тени), многократные отражения и преломления. Различают два основных вида метода трассировки лучей: прямой – forward ray tracing, и обратный – backward ray tracing. Расчет освещенности выполняется во всех точках пересечения лучей и объектов.

В forward ray tracing траектории лучей строятся от источника ко всем точкам всех объектов сцены (первичные лучи). Затем проверяется ориентация каждой точки относительно источника, и, если она лежит на стороне объекта, обращенной в противоположную от источника сторону, точка из расчетов освещенности исключается.

Для всех остальных точек вычисляется освещенность с помощью локальной модели освещения. Если объект не является отражающим или прозрачным, то есть поверхность объекта только диффузно рассеивает свет, траектория луча на этой точке обрывается (заканчивается). Если же поверхность объекта обладает свойством отражения (reflection) и/или преломления (refraction), из точки строятся новые лучи, направления которых совершенно точно определяются законами отражения и преломления.

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

Эта главная, хотя и далеко не единственная, причина того, что метод прямой трассировки лучей считается неэффективным и на практике не используется.

Второй метод – обратная трассировка лучей, или backward ray tracing. Этот метод расчетов основывается на построении лучей от наблюдателя через плоскость экрана вглубь сцены, а не от источника, то есть – наоборот.

Рис. 7.11. В точке пересечения луча с объектом строится три вторичных луча – один в направлении отражения (1), третий в направлении преломления прозрачной поверхностью (3) Лучи теперь строятся иначе. А именно, по двум точкам: первая точка, общая для всех лучей – положение камеры (наблюдателя), вторая точка определяется положением пикселя на плоскости видового окна. Каждый луч вдоль заданного направления продляется от наблюдателя вглубь трехмерной сцены, и для каждой траектории выполняется проверка на пересечение со всеми объектами сцены и с отсекающими плоскостями. Если пересечений с объектами нет, а есть пересечение только с плоскостью отсечения, значит луч выходит за пределы видимой части сцены, и соответствующему пикселю видового окна присваивается цвет фона. Если луч пересекается с объектами сцены, то среди всех объектов выбирается тот, который ближе всего к наблюдателю. В точке пересечения с таким объектом строится три новых, так называемых вторичных луча. Один луч строится в направлении источника света. Если источников несколько, строится несколько таких лучей, по одному на каждый источник. Основное назначение этого луча – определить ориентацию точки (обращена точка к источнику или от него), наличие объектов, закрывающих точку от источника света, и расстояние до источника света. Если точка обращена в противоположную сторону от источника света или закрыта другим непрозрачным объектом, освещенность от такого источника не рассчитывается, точка находится в тени. В случае затеняющего прозрачного объекта интенсивность освещения уменьшается в соответствии со степенью прозрачности. Если точка закрыта от освещения всеми источниками сцены, ей присваивается фоновый ambient цвет. В противном случае точка освещена, интенсивность и цвет освещения рассчитываются при помощи локальной модели освещенности (diffuse + specular) как сумма освещенностей от всех источников, для которых эта точка не закрыта другими объектами.

Этот тип луча получил название shadow ray (иногда его еще называют illumination ray) – теневой луч. Если поверхность объекта не является отражающей и непрозрачна, теневой луч – единственный тип лучей, который строится, траектория первичного луча обрывается (заканчивается), и дальнейшие расчеты не выполняются. Рассчитанный цвет (освещенности или тени) присваивается тому пикселю видового окна, через который проходит соответствующий первичный луч.

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

Направление отраженного луча определяется по закону:

где (N $ I ) – скалярное произведение векторов Для отраженного луча проверяется возможность пересечения с другими объектами сцены. Если пересечений нет, то интенсивность и цвет отраженного луча равна интенсивности и цвету фона. Если пересечение есть, то в новой точке снова строится три типа лучей – теневые, отражения и преломления.

Третий луч строится, если поверхность объекта прозрачна, и носит название transparency ray, т. е. луч прозрачности. Направление для преломленного луча определяется следующим образом (рис. 7.13).

n1 и n2 – коэффициенты рефракции для первой среды (в которой распространяется первичный луч) и второй среды прозрачного объекта.

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

Рис. 7.14. Древовидная структура преобразования лучей Если древовидная структура для данного луча построена, то расчет освещенности можно выполнить в следующем порядке.

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

Затем вычисленная освещенность передается вверх по ветви к следующему ближайшему узлу. Освещенность в этом узле будет вычисляться по формуле In = Iiocal + kreflection # Ireflection + kreflection # Ireflection, где In – полная освещенность в узле n;

Ilocal – локальная освещенность в узле n, вычисленная от источников освещения с помощью локальной модели освещенности;

kreflection – коэффициент, определяющий отражающие свойства Ireflection – освещенность предыдущего узла, переданная вдоль ветки отражения;

kreflection – коэффициент, определяющий преломляющие свойства поверхности;

Ireflection – освещенность предыдущего узла, переданная вдоль ветки преломления.

Изображение можно считать построенным, когда цвета всех пикселов видового окна (все соответствующие деревья для каждого первичного луча) вычислены. Естественным завершением трассировки лучей является выход всех испущенных вторичных лучей за пределы видимой области и их рассеяние на чисто диффузных объектах. Результат вычислений будет наиболее точным. Но, если сцена достаточно сложна, такой расчет будет очень медленным, а в некоторых случаях и невозможным по причине ограниченности аппаратных ресурсов. Поэтому часто трассировку лучей прекращают, когда вклад от следующего узла ветви становится меньше заданной величины. Это также достаточно точный метод расчетов, который может быть использован для получения качественных результатов при определенных условиях. Алгоритм обратной трассировки лучей стал основным способом расчетов освещенности методом трассировки лучей. Метод трассировки лучей – первый метод расчета глобальной освещенности, учитывающий взаимное влияние объектов сцены друг на друга.

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

Основные недостатки: неучет вторичного освещения от диффузно отраженного объектами света; низкая скорость и высокая вычислительная стоимость расчетов – в классическом рейтресинге необходимо проверять на пересечение каждый луч со всеми объектами сцены, в результате от 70 до 95 процентов всего времени расчетов тратится на вычисление пересечений; резкие границы цветовых переходов тени/подсветок/прозрачности; aliasing – «зазубренность» линий и т. д.; дискретность определяющих цвет пиксела первичных лучей – одного первичного луча недостаточно для корректного определения цвета пиксела, формирующего изображение.

7.2.9. Алгоритм Distributed Ray Tracing (DRT) Дальнейшая эволюция алгоритмов ray tracing протекала в направлении преодоления недостатков классического метода обратной рекурсивной трассировки лучей (далее – просто трассировки лучей). Так, для подавления эффекта aliasing и различных его проявлений, например – «зазубренных» линий, были разработаны различные методы сглаживания – supersampling, adaptive supersampling, stochastic и statistical sampling. Существует точная математическая теория сэмплинга, как операции представления непрерывных функций набором дискретных значений. Эта теория использует так называемый Фурье-анализ. В рамках этой теории получено совершенно строгое правило, определяющее способ сэмплирования. Это правило – теорема Найквиста (Nyquist), и оно гласит, что для того, чтобы набор дискретных значений (сэмплов) корректно описывал непрерывную функцию, частота сэмплирования должна быть как минимум в два раза больше максимальной частоты функции. Пример приведен на рис. 7.15.

Результат неверного сэмплирования – алиасинг. Пример пространственного алиасинга – ступеньки на границах объектов, временного алиасинга – вращение колес мчащегося на экране поезда в обратную сторону или «дерганое» воспроизведение видео и анимации. Теорема Найквиста определяет нижнюю границу сэмплинга – чем выше частота сэмплирования, тем точнее и качественнее представление непрерывной функции.

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

Идея адаптивного суперсэмплинга (adaptive supersampling) использует идею о том, что не для всех пикселов изображения столь качественное сглаживание необходимо (на самом деле – только для граничных) первоначально через пиксел пропускается небольшое количество лучей. Вычисленные значения сравниваются между собой. Если разница не превышает заданную величину, количество лучей не увеличивается, а интенсивность усредняется. Если какой-либо из лучей существенно отличается от других, соответствующий субпиксел «простреливается» еще тремя лучами, и все повторяется. Адаптивный суперсэмплинг использует нужное количество лучей в зависимости от того, является ли пиксел «пограничным».

Также интересен и тот факт, что фоторецепторы глаза распределены на сетчатке нерегулярно, а некоторым случайным образом – на разном расстоянии. Главное – существует минимальная дистанция, ближе которой рецепторы не располагаются. Именно такое строение фоторецепторов послужило идеей еще одного вида суперсэмплинга – стохастический сэмплинг. Этот метод разбивает пиксел на заданное количество субпикселей, скажем 4 4 = 16. Вычисляются координаты центров субпикселей, и затем к ним применяется небольшой шум – случайные отклонения по координатам x и y. Так что новые центры смещаются случайным образом в пределах. Затем через них пропускают первичные лучи, которые теперь распространяются под случайными углами. Основная идея distribute ray tracing была предложена Cook, Porter и Carpenter в 1984 году. В самом общем смысле ее суть состоит в том, что три типа вторичных лучей классического рейтресинга – теневой, зеркальный и прозрачности, должны «расщепляться» (рис. 7.17) на несколько дополнительных лучей, распространяющихся в направлении «родительского» луча.

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

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

Тем не менее, удивительно, но факт – такое простое усовершенствование позволяет DRT просчитывать такие эффекты, как:

• gloss (или scattered reflectance – размытые отражения translucency (размытая прозрачность);

• penumbra (мягкая тень с размытыми краями) depth of field (размывание объектов в зависимости от их положения относительно фокуса камеры) motion blur (истинное размытие в движении).

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

Вычислить интегралы в большинстве случаев невозможно.

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

Правильно подобранный множитель p(xi) также может сильно уменьшить ошибку (его математический смысл – вероятность используемого значения xi). Углы в направлении идеального (зеркального) отражения и идеального преломления берутся за основу. Применим к ним генератор случайных чисел для получения небольших случайных вариаций углов числом N и эти значения подставим в сумму. Интеграл в одной точке найден. Нужно сказать, что выбор наиболее вероятных значений углов в направлении идеального направления отражения и преломления не единственен. Для определения наиболее вероятных углов еще довольно часто используются: лепестковый створ углов cos(n, r) угла между нормалью и некоторым направлением (cosine sampling); BRDF-поверхности, которой принадлежит рассчитываемая точка. Он хорошо срабатывает на сильно отражающих поверхностях (BRDF sampling); функцию, описывающую распределение приходящего из соседних узлов освещения (Incident radiance field sampling).

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

Поскольку BRDF известна заранее, трейсеры обычно предварительно просчитывают таблицы сэмплирования (lookup table) для каждой поверхности трехмерной сцены и сохраняют их для использования в нужный момент времени.

Правильный выбор направлений сэмплирования и весовых коэффициентов является «камнем преткновения» для современных рендеров, поскольку их оптимальное сочетание разом влияет и на качество рендера, и на скорость. Математически строгого решения пока нет, ведутся интенсивные исследования этого вопроса.

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

Сэмплирование (выбор направления лучей) в наиболее вероятном направлении получил название importance sampling, а distribute ray tracing еще называют stochastic ray tracing из-за оценки значений интегралов случайными числами (случайными сэмплами). Вычисление интегралов освещенности точек методом МонтеКарло приводит к появлению новых сэмплирующих лучей вместо вторичных лучей классического рекурсивного рейтресинга. Количество лучей растет лавинообразно. Для ускорения расчетов, а также во избежание зацикливания трейсера на вычислении бесконечных траекторий (что вполне возможно) применяется Русская рулетка – математический метод отсечения ветвей рейтресинга, если их вклад становится меньше некоторой заданной величины.

Итак, стандартные возможности distributed (stochastic) ray tracing:

• сэмплирование отражений (reflection) размывает отражения;

• сэмплирование преломлений (transmission) размывает прозрачность;

• сэмплирование источников света дает мягкие тени с размытыми краями (penumbras);

• сэмплирование длин волн света (wavelength) позволяет рассчитывать дисперсию.

DRT очень качественный и очень «дорогой» метод расчетов, способный «перегрузить» современный компьютер. Поэтому в настоящее время большинство рендеров общего назначения используют сочетание: скан-лайн плюс рейтресинг только там, где это необходимо. Такой подход позволяет получать высокое качество за приемлемое время.

7.2.10. Метод расчетов освещенности Radiosity Скан-лайн рендер и рейтресинг рассчитывают диффузную освещенность трехмерных поверхностей только от прямых источников света в соответствии с законом Ламберта. Учитывая, что диффузная освещенность несет основную визуальную информацию о геометрии и цвете объектов, совершенно очевидно, что только закона Ламберта для достижения фотореалистичных результатов расчета освещенности недостаточно. В частности, при расчете диффузного освещения данной поверхности необходимо учесть не только ее освещение прямыми источниками света, но и так называемое вторичное (или отраженное) диффузное освещение – диффузное рассеяние света окружающими объектами. Метод расчетов, позволяющих учесть вторичное диффузное освещение, получил название radiosity, или метод излучения.

На сегодняшний день этот алгоритм считается наиболее мощным и универсальным методом создания реалистичных изображений. Ключевая задача метода трассировки лучей – определение освещённости произвольной точки объекта сцены и той части световой энергии, которая от него уходит в заданном направлении. Допустим, что, во-первых, рассчитываемая сцена содержит тела, различным образом отражающие и преломляющие свет. Однако сцена невидима до тех пор, пока не заданы положение и параметры источников света, которые будут освещать объекты сцены, давать тени и т. д.

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

Прямая трассировка лучей. Рассчитываются пути лучей света, идущие от источников до объектов сцены. Если такой первичный луч попадает в прозрачный объект, то преломляясь и теряя интенсивность, он идёт дальше и, возможно, попадает на другой объект, в свою очередь отражаясь от него. Так, многократно отражаясь и преломляясь, какая-то часть лучей приходит в точку наблюдения – т. е. эти лучи определяют цвет некоторых пикселей экранной плоскости. Если ограничиться некоторыми первичными лучами, выходящими из источников и попадающими только на объекты сцены или в камеру, а затем точно так же поступить со вторичными лучами, то время вычисления сцены уже будет конечным, а результат достаточно реалистичным. Например, тени и полутени от объектов сцены будут сформированы сразу же. Тем не менее даже небольшое изменение точки наблюдения приведёт к пересчёту всей сцены. Недостаток данного метода – огромное количество «лишних» вычислительных операций.

Обратная трассировка лучей. Данный метод позволяет значительно сократить перебор световых лучей. Метод разработан в 80-х годах, основополагающими считаются работы Уиттеда и Кея.

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

На рис. 7.19 представлена сцена, рассчитываемая по методу обратной трассировки лучей. Из точки наблюдения через пиксель картинной (экранной) плоскости P* восстанавливается луч зрения v, упираясь в точку P на видимой грани объекта трёхмерной сцены. Эта точка освещается с помощью первичных лучей, идущих от нескольких источников света. На рисунке показан один из источников, направление на который даёт вектор r. Кроме того, если в этой точке грань является отражающей, то восстановив вектор отражения r, симметричный v относительно нормали к грани n, отследим пересечение этого вектора с другими объектами сцены и проведём расчёт освещённости для точки P2. Если в точке P указано свойство прозрачности, то необходимо также отследить преломлённый луч t для луча зрения v, по которому также может быть получена информация об освещённости других объектов сцены (точка P3).

Точка Таким образом, расчёт цвета пикселя P* в общем случае определяется освещённостью всех поверхностей сцены, видимых по лучу зрения с учётом многократного отражения, преломления и поглощения. Для убыстрения вычислений необходимо ограничиться небольшим числом отражённых или преломлённых лучей, либо вести оценку порога минимальной интенсивности света, приходящего по лучу зрения. Интенсивность в точке P некоторой поверхности сцены может быть рассчитана по следующей формуле:

Первое слагаемое – вклад фонового освещения; ka – коэффициент «участия» поверхности в фоновой засветке.

Второе слагаемое – учитывает прямое диффузное освещение поверхности источниками света, близкими к точечным; kd – коэффициент диффузного освещения.

Третье слагаемое – производит учёт зеркального отражения источников света от поверхности по лучу зрения в соответствии со свойствами поверхности; ks – коэффициент зеркальности.

Четвёртое слагаемое – производит учёт интенсивности света, приходящего по отражённому лучу зрения, с условием поглощения в среде, где проходит луч. Ir – интенсивность отражённого луча, рассчитываемая в свою очередь по предыдущей формуле для точки P2.

Пятое слагаемое – учитывает интенсивность света, приходящего по преломлённому лучу зрения, с условием поглощения в среде;

kt – коэффициент прозрачности; It – интенсивность преломлённого луча, рассчитываемая по предыдущей формуле для точки P3.

Часто вместо коэффициентов Френеля для упрощения вычисp лений используют аппроксимацию вида R = K $ (r $ l ) – модель Уиттеда. К – константа; p – экспериментально подбираемая степень «реалистичного» отражения света.

Таким образом, алгоритм обратной трассировки лучей включает в себя:

• расчёт освещённости сцены с учётом положения источников света с параметрами яркости, цвета, направленности и положения объектов для расчёта теневых масок;

• расчёт видимости граней объектов из точки наблюдения с учётом положения точки наблюдения и вида проецирования;

• расчёт цветовых компонент по освещённости и цвету граней с учётом оптических свойств поверхности и среды для каждого пикселя картинной плоскости.

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

Пусть объекты некой сцены имеют идеально диффузно рассеивающие поверхности (после отражения луч пропадает). Разобъём сцену на n фрагментов (например, связанных с гранями объектов), для каждого из которых напишем уравнение баланса Здесь Bi – полная энергия i-го фрагмента сцены; Ei – собственная энергия (излучательность) i-го фрагмента сцены; ri – коэффициент отражения; Fij – форм-фактор – доля энергии j фрагмента, форм-фактор определяет часть энергии, исходящей от одной поверхности и достигающей другой. Расчёт заключается в формировании итерационного процесса и решением системы из n линейных алгебраических уравнений с начальными условиями и очередным приближением:

Здесь k – номер текущей итерации. Процесс продолжается до достижения заданной точности расчёта сцены.

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

Наиболее трудоемкая часть метода излучательности – вычисление форм-факторов.

Для двух неперекрытых элементарных площадок (рис. 7.20) i и j форм-фактор имеет вид:

Общее выражение для форм-фактора двух граней с условием частичного перекрытия (т. е. когда часть поверхности Ai закрыта от Aj) можно представить как Здесь Hij – функция перекрытия, принимающая значения от 0 до 1. Чтобы не вычислять такие интегралы, используется ряд эффективных приближённых методов, работающих при определённых ограничениях, налагаемых на сцену.

7.2.12. Затенение по Гуро (Gourad Shading) Затенение по Гуро – это метод линейной интерполяции освещенности в пределах одного полигона. Это эффективный метод придания ощущения изогнутости для ровного полигона. Этот метод также часто используется для сокращения глубины прорисовываемой сцены, путем имитации исчезновения удаленных объектов в тумане.

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

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

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

Рассмотрим подробнее фазу интерполяции освещения по полигону. Визуализация полигона и интерполяция освещенности будет проведена путем преобразования сканирования строк вдоль координаты Х (рис. 7.22).

Будем предполагать, что освещенность в вершинах уже вычислена и допустив, что вдоль кромок полигона она изменяется линейно, вычислить ее значение в точках A и В на каждое изменение координаты Y будет несложно.

Рис. 7.22. Интерполяция освещения по полигону Небольшой полигон для простоты изображен с равномерным заполнением. Просчитаем линию АВ. Т. к. мы имеем дело с пикселизованным экраном, поэтому сможем вывести на экран только линию, состоящую из трех пикселей СD. Центр первого пикселя С не совпадает с центром точки А, а центр пикселя D – не совпадает с точкой B.

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

Определим градиент изменения освещенности по всей длине линии:

где: As и Bs – оттенок в точках А и В;

Bx и Ax – значения X в точках А и В соответственно градиент показывает относительную величину изменения освещенности в пересчете на единицу изменения координаты X.

Определим точное значение в точке С.

величина frac(Ax) определяет смещение (см. рис. 7.21).

Процесс визуализации одной горизонтальной полосы из состава полигона Гуро включает в себя просчет оттенка каждого пикселя в линии и выводе его на устройство визуализации. Это достаточно простой процесс, так как величина изменения оттенка (градиент) линейна на всей протяженности выводимой линии.

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

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

Аппроксимации Фонга или затенение по Фонгу (Phong shading) носят название от имени своего изобретателя – Ву Тонг Фонга (Wu Tong Phong). Этот метод дает более точные результаты при затенении полигонов по сравнению с затенением Гуро, рассмотренным выше. Суть этих аппроксимаций заключается в определении нормали к поверхности в каждой вершине полигона и дальнейшей интерполяции вектора по всему полигону поверхности.

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

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

Поэтому большинство компьютерных программ, сообщающих об использовании затенение по Фонгу в реальном времени, на самом деле используют такой вариант, который позволяет достичь приемлемых результатов и при этом он значительно быстрее.) Затенение по Фонгу считается популярным методом для реализации затенения, особенно в программах, работающих вне режима реального времени, например 3D Studio и др. Однако несмотря на то, что этот метод значительно точнее затенения Гуро, он не является физически более точным.

Затенение по Фонгу основывается на том, что количество света, отраженного от поверхности прямо пропорционально косинусу угла между нормалью к поверхности и направлением света. При этом не имеет значения, под каким углом вы смотрите на поверхность.

В реальности очень немногие поверхности обладают такими идеальными свойствами. Наиболее подходящими являются поверхности, имеющие микроскопические шероховатости, например, хорошо отшлифованное дерево. Большинство поверхностей также обладают некоторой степенью спектрального отражения.

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

Итак, имеется полигон. В каждой вершине полигона мы имеем вектор нормали к поверхности, частью которой полигон является (v1, v2, v3). Эти векторы интерполированы по всей площади полигона, подобно тому, как это делалось для затенения Гуро. В затенении Гуро мы имели дело только с одним значением shade (это скалярная величина). Здесь же мы оперируем вектором с тремя значениями Vx, Vy и Vz.

Возьмем пиксель на этом полигоне, красная точка (рис. 7.23).

Вектор нормали, соответствующий этому пикселю на поверхности – n. Свет падает на полигон вдоль вектора l. Количество света, отраженного от данного пикселя является функцией называемой dot product.

Dot product – это скалярное произведение векторов, дающее в результате число, определяющее длину (величину) результирующего вектора. Скалярное произведение вектора n (x, y, z) и вектора l(x, y, z) может производиться по любой из двух формул:

где q (тетта) – угол между векторами.

Более удобный второй вариант, т. к он оперирует с длинами (величинами) векторов и углом между ними. Величина нормали к поверхности равна 1. А величина вектора, падающего света приводится к 1 и будет иметь значения от 0 до 1. Cамый яркий свет – 1.

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

Понятия отрицательного света не существует, поэтому значения меньше 0 следует понимать как 0. Если затем умножить данное значение на величину яркости света (brightness), то получится значение яркости нашего пикселя.

Быстрое затенение по Фонгу (Fast Phong shading). Базовый алгоритм затенения по Фонгу требует больших вычислительных ресурсов и поэтому очень медленный. Однако эффект от применения этого затенения очень привлекателен, поэтому сам алгоритм неоднократно подвергался различным оптимизациям.

Один из вариантов упрощения – это способ, заключающийся в интерполяции угла между нормалью и направлением света, вместо базовой интерполяции самого вектора нормали по всему полигону. По существу это воспроизводство затенения Гуро (т. к.

интерполируется скалярная величина). Было предложено интерполировать не один лишь угол, а сразу два. Во избежании проделывания целого ряда тяжелейших вычислений с двумя углами можно рассмотреть эти углы как соответствие координатам на заранее просчитанной карте (текстуре) затенения. Это значительно упростит задачу просчета в реальном времени. Затенение по Фонгу теперь становиться обычным, линейным текстурированием.

Карта для затенения по Фонгу представляет собой заранее просчитанный набор яркостей для всех возможных нормалей.

Удобно использовать текстуру размерностью 256256 пикселей.

Рис. 7.24. Полигон, подготовленный к визуализации Для каждой из вершин подготовленного к визуализации полигона необходимо просчитать координаты соответствующей позиции на карте затенения. Для этого полигона определим два вектора, находящихся под прямым углом друг к другу и к нормали полигона. Назовем их V и H. Эти два вектора будут определять координаты u, v карты затенения (текстуры).

Рис. 7.25. Изменение положения полигона Теперь расположим полигон в пространстве таким образом, что нам можно представить вектор света к нашей вершине. Это будет вектор L.

Цель – получить координаты u и v исходя из значений V, H, L.

Алгоритм. Если карта затенения будет размерностью пикселей с точным центром то:

Просчитав это для каждой вершины, а затем «натянув» карту затенения на полигон – мы получим плавно затененный полигон в соответствии с внешним освещением.

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

Для получения уравнений radiosity делается несколько основных допущений. Первое – поверхности всех объектов трехмерной сцены разбиваются на плоские небольшие участки – патчи (patch). В некотором смысле они напоминают полигоны, с помощью которых описываются поверхности, хотя на самом деле таковыми не являются. То есть, они могут быть больше или меньше размера реальных полигонов и по сути являются модельным инструментом radiosity, а не средством точного описания поверхности. Размер каждого патча должен быть настолько мал, что плотность распределения интенсивности световой энергии в его пределах можно считать постоянной величиной (константой). И наконец, считают, что диффузное рассеяние света не зависит от угла, то есть свет рассеивается равномерно по всем направлениям. Такой подход для получения и решения уравнений освещенности radiosity получил название finite element method – метод ограниченных элементов. Основные идеи radiosity заимствованы из физики теплового переноса. Сама величина radiosity определяется как плотность потока энергии, испускаемой патчем (покидающей патч).

Таким образом, radiosity – это поток энергии, исходящей от единицы площади поверхности в единицу времени. Поток энергии каждого из окружающих патчей вычисляется как произведение площади такого патча на плотность испускаемого им потока энергии (т. е. radiosity этого патча), поскольку патч настолько мал, что плотность потока в его пределах можно считать постоянной величиной. Необходимо учесть взаимную ориентацию и расстояние патчей. Для этого вводится так называемый форм-фактор. Форм-фактор просто определяет, какая часть всего потока излучаемой энергии (radiosity) данного патча достигает другого патча. Вследствие всего этого, основные уравнения расчета radiosity имеют следующий вид:

где: Bj – radiosity i-го патча;

Ei – диффузное отражение света от прямого источника;

i – коэффициент, характеризующий свойства диффузного отражения поверхности, которой принадлежит патч;

Bj – radiosity j-го патча;

Аij – форм-фактор, определяющий, какая часть радиосити j-го патча достигает i-го патча;

n – количество всех патчей трехмерной сцены.

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

Это означает, что прямое математическое решение уравнений методом исключения Гаусса неприемлемо как с точки зрения времени вычислений, так и количества памяти для хранения переменных (радиосити патчей и форм-факторов). Поэтому, хотя основные уравнения радиосити имеют универсальное значение, для их решения используются различные подходы, что и привело к появлению разновидностей алгоритмов расчета радиосити.

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

Поскольку для реалистичных поверхностей коэффициент диффузного отражения меньше единицы, и любой из форм-факторов также всегда меньше единицы (описывает часть от целого значения), добавка к промежуточному значению радиосити с каждым шагом вычислений будет все меньше и меньше. Хотя этот метод решает часть проблем вычисления значений радиосити, он все еще недостаточно быстр и требует такого количества памяти для хранения переменных, что его использование для решения практических задач почти невозможно. Второй, и наиболее распространенный, метод решения уравнений радиосити носит название метода прогрессивного уточнения оценок (progressive refinement method). Основные уравнения radiosity путем математических преобразований можно привести к такому виду, что они будут описывать вклад данного патча в радиосити всех остальных патчей, то есть наоборот – не собираем свет, а излучаем свет из данного патча в направлении окружающих поверхностей.

Такой подход имеет то преимущество, что при вычислении вкладов требуется только n форм-факторы того патча, вклады которого вычисляются.

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

1. На первом шаге итерации считается, что отраженного света пока нет, поэтому радиосити всех патчей определяются освещенностью прямыми источниками света в соответствии с законом Ламберта + собственное излучение, если патч принадлежит самосветящейся поверхности. По найденным значениям радиосити производится упорядочивание патчей в порядке убывания. Это делается для того, чтобы в последующих итерациях вычисления начинались с патчей, которые будут наиболее сильно освещенными.

2. Выбирается первый «патч» последовательности (наиболее освещенный), и в соответствии с формулой рисунка выше вычисляются вклады первого патча в радиосити всех остальных патчей.

Вычисленные вклады суммируются с радиосити соответствующих патчей и сохраняются с накоплением в так называемой переменной неизлученной радиосити (unshoot radiosity) соответствующего патча для следующей итерации (то есть, вклад первого патча в радиосити второго патча прибавляется к радиосити второго патча и суммируется со значением переменной неизлученной освещенности радиосити второго патча). Unshot radiosity первого патча обнуляется после вычисления всех вкладов первого патча – вся «неизлученная» освещенность теперь «излучена». Таким образом, каждый патч характеризуется текущим значением радиосити и переменной «неизлученной» радиосити, представляющей собой сумму вкладов от других патчей, вычисленных в текущей итерации.

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

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

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

Выигрыш в скорости расчетов и экономия необходимой для вычислений памяти в progressive refinement method оказались настолько велики, что этот метод впервые позволил реализовать расчет radiosity в практических приложениях и даже успешно применяется в приложениях реального времени.

Третий метод решения уравнений носит название wavelet radiosity.

Wavelet метод использует динамическое представление поверхностей патчами в зависимости от расстояния поверхностей друг от друга.

Matrix radiosity, wavelet radiosity и progressive refinement являются основными разработанными методами вычислений. В практических приложениях в основном используется усовершенствованный progressive refinement method with substructuring (адаптивно разбивает патчи на более мелкие по площади в областях с тоновым градиентом – например, на границах теней), wavelet radiosity – очень редко.

Сравнения этих методов показывают, что progressive refinement дает лучшие результаты в простых сценах, wavelet radiosity – в больших сложных сценах с множеством объектов. Однако wavelet radiosity использует гораздо большее количество памяти в вычислениях. В конце 90-х годов, был разработан еще один способ решения основных уравнений радиосити, получивший название Stochastic Relaxation Radiosity, или SRR. Именно этот алгоритм расчетов применяется в 3ds max, начиная с шестой версии, он основывается на применении метода Монте-Карло (М-К) как для решения матричных уравнений радиосити, так и уравнений progressive refinement method. В данном случае метод М-К используется для оценки величины суммы вкладов радиосити всех патчей в данный (или вкладов данного патча во все остальные патчи) по величине вкладов части из них. Другими словами, этот метод позволяет вычислять не все вклады, а только часть из них, выбранных по некоторому случайному закону. Кроме того, он же позволяет при вычислениях вкладов избежать вычислений форм-факторов. Общий алгоритм таков: берем первый патч и на его поверхности некоторым случайным образом выбираем N точек. Из каждой точки под некоторым случайным углом испускается луч. Луч трассируется до пересечения с ближайшим патчем. Вероятность того, что луч пересечет именно этот патч, а не другой, определяется величиной форм-фактора двух соответствующих патчей. Именно это обстоятельство позволяет исключить вычисление форм-фактора из вычислений вкладов. Вклад i-го патча, с которым пересекся луч (или вклад в i-й патч) вычисляется по формуле После расчета вкладов от N случайных патчей переходим к следующему патчу. После перебора всех патчей данная итерация закончена, переходим к следующей, пока величина вкладов не станет меньше заданной величины.

Stochastic Relaxation Radiosity обеспечивает гораздо более быстрый расчет радиосити и требует меньше памяти для вычислений, чем все другие рассмотренные методы.