Федеральное агентство по образованию РФ
Государственное учреждение высшего профессионального образования
Уральский государственный университет
им. А.М.Горького
математико-механический факультет
кафедра информатики и процессов управления
ИССЛЕДОВАНИЕ И РАЗРАБОТКА НЕКОТОРЫХ ГРАФИЧЕСКИХ АЛГОРИТМОВ
Допустить к защите:
зав. кафедрой
___________________
"__"____________2008 г.
|
|
Магистерская диссертация:
студента гр. МГМТ-2
Шайдурова А. Г.
___________________
Научный руководитель:
доцент КИПУ,
к.ф.-м.н. Вахрушев В. А.
___________________
|
Екатеринбург
2008
Реферат:
Шайдуров А.Г. Исследование и разработка некоторых графических алгоритмов. Квалификационная работа на степень магистра наук по направлению «Математика. Прикладная математика»: 137 стр., 62 ил, библ.: 35 назв., 1 приложение.
Ключевые слова: ДЕТАЛИЗАЦИЯ ПОВЕРХНОСТЕЙ, ЛОКАЛЬНАЯ ТРАССИРОВКА ЛУЧЕЙ, ПОСТРОЕНИЕ ОТРАЖЕНИЙ, КУБИЧЕСКИЕ ТЕКСТУРЫ, АЛИАСИНГ, PARALLAX MAPPING, GPU ALGORITHMS.
Представлен алгоритм визуализации мелких деталей, основанный на трассировке в карте высот, который отличается от других подобных алгоритмов наличием отражений и использованием нового метода вычисления градиентов текстурных координат. В созданном алгоритме локальной трассировки комбинируется классическая трассировка лучей и метод построения отражений при помощи кубических текстур. Также разработаны модификации алгоритмов построения теней, метод рисования символов и другие. Большинство этих методов допускает эффективную реализацию на графическом оборудовании.
Содержание
Введение
Компьютерная графика – обширная и быстро развивающаяся дисциплина. Особое место в ней занимают методы, использующие специализированные аппаратные средства, поскольку графическое оборудование позволяет отображать сложные сцены с высокой скоростью. В настоящее время графические процессоры быстро развиваются, увеличивается гибкость их программирования, что позволяет реализовывать на них все более сложные методы. Это подталкивает к активным исследованиям, направленным на разработку новых методов.
В главе 1 приводится краткий обзор существующих методов рушения рассматриваемых в работе задач. Глава 2 посвящена описанию разработанных алгоритмов. В главе 3 подводятся итоги и рассматриваются направления дальнейших исследований. В Приложении 1 находятся фрагменты исходного кода.
Постановка задачи
Предлагается выполнить следующую работу:
Исследовать некоторые из существующих методов и алгоритмов компьютерной графики.
Предложить новые методы или модификации существующих.
Реализовать предложенные методы, по возможности на графическом оборудовании.
1. Существующие алгоритмы
1.1. Методы улучшения детализации поверхностей
Мелкие детали сильно влияют на внешний вид объектов, но моделирование всех деталей с помощью геометрии приводит к чрезмерному усложнению модели. Существует несколько методов улучшения детализации объектов без усложнения геометрической модели: normal mapping, parallax mapping, displacement mapping и другие [7, 9, 10, 12, 13, 33, 35].
1.1.1. Bump mapping
Один из наиболее простых методов основан на модификации нормали к поверхности. Его предложил Jim Blinn в 1978 году. Поверхность задается с помощью геометрической модели сравнительно низкой детализации и дополнительной информации для увеличения детализации – карты высот или карты нормалей (рис. 1). В каждом элементе карты высот содержится смещение H соответствующей точки вдоль нормали к геометрической поверхности. Если для каждой точки геометрической поверхности добавить это смещение, то получится более детализированная поверхность. Для того, чтобы получить изображение детализированной поверхности с небольшими вычислительными затратами, для рисования поверхности используется геометрическая модель с низкой детализацией. Информация в карте высот используется для вычисления нормали Ns к детализированной поверхности. Для этого при обработке каждого пикселя выполняется численное дифференцирование карты высот на остове нескольких соседних выборок. Вместо карты высот можно использовать карту нормалей, в которой хранятся нормали к детализированной поверхности в касательном пространстве исходной (геометрической) поверхности. В этом случае требуется только одна выборка из карты нормалей. Кроме того, выполняется меньше математических расчетов, так как не выполняется численное дифференцирование. Недостатки по сравнению с картой высот – отсутствие информации о смещении поверхности вдоль нормали (которая может понадобиться для других методов), а также невозможность использования дополнительных текстур детализации. При расчете освещения точки P вместо геометрической нормали Ng используется полученная нормаль, в результате чего достигается увеличение детализации.
рис. 1
1.1.2. Parallax mapping
Parallax mapping – развитие предыдущих методов. Кроме модификации нормали в этом методе подвергаются изменениям текстурные координаты. Для этого требуется карта высот, карты нормалей здесь недостаточно. При рисовании поверхности точка S пересечения вектора наблюдения с поверхностью, заданной в карте высот, аппроксимируется точкой S` (рис. 2). Для того, чтобы обрабатываемый пиксель имел цвет точки S` (а не G), исходные текстурные координаты TG, взятые из геометрической модели, заменяются на TS. Такая аппроксимация дает удовлетворительные результаты только в том случае, если высота меняется не очень быстро. Кроме того, данный метод не учитывает возможность перекрытия пикселя другим участком поверхности (рис. 3).
рис. 2
рис. 3
1.1.3. Методы, основанные на трассировке в карте высот
Методы, использующие трассировку в карте высот (parallax occlusion mapping, steep parallax mapping, relief mapping), работают следующим образом. Сначала выполняется перевод вектора наблюдения (направленного из камеры к обрабатываемому пикселю) в касательное пространство. Затем ищется точка пересечения S этого вектора с поверхностью, заданной в карте высот. После этого вычисляется цвет точки S, который возвращается в качестве результата. Дополнительно можно определить, находится ли точка S в тени. Для этого ищется пересечение вектора, направленного из точки S к источнику света, с поверхностью (подобно тому, как находилось пересечения вектора наблюдения с поверхностью на предыдущем этапе). Если пересечение существует, точка находится в тени; иначе – освещена. Эта информация используется в процессе расчета освещения.
Ключевая операция в таких алгоритмах – вычисление пересечения луча с поверхностью. Наиболее простой способ – линейный поиск.
Методы нахождения пересечения луча с поверхностью
Линейный поиск
В процессе линейного поиска осуществляется смещение вдоль вектора наблюдения на небольшую фиксированную величину до тех пор, пока текущая точка Si не окажется ниже поверхности (рис. 4). Для того, чтобы проверить положение текущей точки относительно поверхности, осуществляется выборка из карты высот по координатам x и y точки Si (поиск проводится в касательном пространстве, поэтому в качестве текстурных координат используются координаты точки Si). Если координата z точки Si меньше (или больше – в зависимости от направления оси z касательного пространства) значения из карты высот, то Si находится ниже поверхности, иначе – выше.
рис. 4
У линейного поиска есть недостаток – для точного поиска пересечения величина смещения вдоль вектора наблюдения должна быть небольшой. Это приводит к большому числу итераций и низкой скорости работы. Увеличение величины смещения приводит к двум проблемам:
Снижение точности поиска. Абсолютная погрешность в касательном пространстве равна длине вектора смещения.
Пропуск мелких деталей (выступов и т.п.) (рис. 5). Это общая проблема всех дискретных методов.
рис. 5
Вторая проблема особенно неприятна, так как мелкие детали могут внезапно появляться и исчезать при движении объекта или камеры. Это один из основных недостатков методов, использующих трассировку в карте высот, по сравнению с геометрическими методами (displacement mapping). У геометрических методов тоже есть проблемы дискретизации, но формируемая поверхность получается непрерывной. Кроме того, у таких методов нет зависимости от вектора наблюдения, поэтому при движении объекта или камеры поверхность не меняется и не происходит внезапного появления и исчезновения мелких деталей.
Для ускорения поиска пересечения без снижения точности существует несколько методов.
Бинарный поиск
Это рекурсивный алгоритм. На каждой итерации текущий отрезок делится пополам и выбирается та половина, концы которой находятся по разные стороны от поверхности (рис. 6).
Скорость сходимости бинарного поиска гораздо выше, чем у линейного, но для корректной работы требуется, чтобы для вектора, подаваемого на вход алгоритма, существовало единственное пересечение с поверхностью. В противном случае алгоритм может найти не первое пересечение (рис. 7). Можно достичь хороших результатов, если комбинировать линейный поиск с бинарным. В этом случае сначала выполняется линейный поиск с достаточно большим шагом (чтобы ускорить поиск) для локализации пересечения. Затем следует бинарный поиск для уточнения пересечения. При этом в качестве начального отрезка для бинарного поиска используется отрезок, сформированный последней и предпоследней точками, полученными в процессе линейного поиска. Линейный поиск останавливается, как только текущая точка оказывается под поверхностью, поэтому последняя точка находится под поверхностью, а предпоследняя – над поверхностью (иначе поиск завершился бы на предыдущем шаге). В случае выбора большого шага для линейного поиска возможно существование более одного пересечения получившегося отрезка с поверхностью (что может привести к некорректной работе бинарного поиска), но на практике это маловероятно. К сожалению, пропуск мелких деталей по-прежнему возможен, т.к. локализация точки пересечения осуществляется линейным поиском с достаточно большим шагом. Таким образом, рассмотренный комбинированный подход решает первую из названных выше проблем, но не вторую.
рис. 6
рис. 7
Методы, использующие предварительно рассчитанные данные
В алгоритме per-pixel displacement mapping with distance functions [33] расстояние от каждой точки до поверхности сохраняется в трехмерной текстуре. Для поиска пересечения выполняется трассировка сфер, при осуществлении которой используется сохраненная информация.
Алгоритм cone step mapping [35] для каждого элемента карты высот на этапе предрасчета данных (который выполняется один раз) рассчитывает конус и сохраняет его угол в двумерной текстуре. Конус рассчитывается таким образом, чтобы он не пересекал поверхность, заданную в карте высот, и его угол был максимальным (т.е. конус касается поверхности). Для нахождения пересечения вектора наблюдения с поверхностью на каждом шаге вычисляется пересечение этого вектора с сохраненным конусом. Для получения конуса из рассчитанной на подготовительном этапе текстуры используются текстурные координаты текущей точки. Вычисленное пересечение с конусом считается новой текущей точкой. Так как конус касается поверхности, но не пересекает ее, последовательность точек только приближается к поверхности, но не может перескочить через нее. Благодаря этому решается вторая проблема линейного поиска. Но в большинстве случаев последовательность точек так и не достигает поверхности, и на практике это привадит к заметным искажениям. То есть первая проблема остается нерешенной.
Quad-directional cone step [35] – развитие предыдущего метода. Отличие заключается в том, что вместо одного угла конуса сохраняется четыре для каждого направления. Это позволяет немного увеличить точность поиска, но не решает полностью проблемы предыдущего алгоритма.
Алгоритм relaxed cone stepping [35] во многом похож на комбинацию линейного и бинарного поисков. Только вместо линейного поиска используется модификация метода cone step mapping: конус рассчитывается таким образом, чтобы любой отрезок внутри него пересекал поверхность не более одного раза. Это менее жесткое ограничение. В результате радиусы конусов оказываются значительно больше, что приводит к ускорению сходимости. Кроме того, так как любой отрезок внутри конуса пересекает поверхность не более одного раза, можно еще уточнить пересечение при помощи бинарного поиска, имеющего высокую скорость сходимости.
1.2. Метод наложения окружающей среды с использованием кубических текстур
Существует эффективный метод построения отражений на зеркальных объектах, который легко реализовать на графическом оборудовании. Для этого точка наблюдения помещается в центр зеркального объекта, угол обзора для перспективной матрицы проекции [3, 6] устанавливается равным 90 градусам, и окружающая среда рисуется в 6 направлениях (справа, слева, сверху, снизу, спереди и сзади объекта). 6 полученных изображений формируют кубическую текстуру. При рисовании зеркального объекта на основе направления вектора наблюдения и нормали вычисляется вектор отражения. Он используется в качестве текстурных координат для кубической текстуры (по трехмерному вектору направления определяется грань куба и двумерные текстурные координаты соответствующей двумерной текстуры, это обычно осуществляется аппаратно). Полученное из кубической текстуры значение и есть цвет отражения в обрабатываемом пикселе.
Один из основных недостатков данного метода – отсутствие самоотражений, поскольку сам объект при построении кубической текстуры не рисуется. Это может привести к некорректным отражениям на невыпуклых объектах: там, где должен отражаться объект, отражается окружающая среда.
Другой недостаток заключается в том, что при выборке значения из кубической текстуры предполагается, что вектор отражения направлен из центра объекта. Таким образом, отражения получаются корректными только в предельных случаях для бесконечно малого объекта или бесконечно удаленной окружающей среды. На практике в большинстве случаев такие искажения не сильно влияют на восприятие полученных отражений.
Более подробно о методе наложения окружающей среды с использованием кубических текстурных карт можно прочитать, например, в [1, 14].
1.3. Алгоритмы теневых буферов
Алгоритм теневых буферов – один из наиболее распространенных методов построения теней. Его предложил Lance Williams в 1978 году. Алгоритм достаточно простой. На первом этапе требуется нарисовать с позиции источника света в буфер глубины все объекты, которые могут отбрасывать тень. На втором этапе рисуется сцена с позиции наблюдателя. Для того, чтобы определить, находится ли пиксель в тени, он переводится в систему координат источника света. Если его глубина больше сохраненного на первом этапе значения, то он находится в тени, иначе – освещен.
К преимуществам алгоритма по сравнению с другими относится небольшая зависимость от геометрической сложности объектов, универсальность (работает с любой геометрией, а также с прозрачными текстурами), простота реализации. В то же время алгоритм работает в пространстве изображения, что приводит к алиасингу и проблемам передискретизации. Кроме того, буфер глубины имеет ограниченную точность, к тому же для него требуется дополнительная память.
Существуют многочисленные модификации этого алгоритма [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 30, 31, 32, 34]. В этих модификациях предпринимаются попытки улучшить базовый алгоритм, например, уменьшить алиасинг или размыть границы теней.
2. Предлагаемые алгоритмы
В работе предлагается метод улучшения детализации поверхностей без увеличения геометрической сложности, основанный на трассировке в карте высот. Кроме самозатенений, присутствующих в других методах, использующих трассировку в карте высот, в данном методе реализованы отражения, а также комбинированный метод вычисления градиентов текстурных координат.
Использованные идеи лежат в основе метода локальной трассировки, в котором комбинируется классическая трассировка лучей и кубические текстуры для получения отражений.
Оба предлагаемых алгоритма допускают эффективную реализацию на существующем графическом оборудовании.
Реализации всех алгоритмов можно найти в Приложении 1. Программы для демонстрации предложенных методов были написаны на языке программирования C++. Для программирования графического процессора использовался язык HLSL. Взаимодействие с графическим оборудованием осуществлялось через интерфейс Direct3D 9.0c. В качестве начальной точки для реализации методов, использующих графическое оборудование, использовался проект SimpleSample из DirectX SDK (за исключением методов построения теней, для которых за основу был взят проект ShadowMap). Многие текстуры были взяты из NVIDIA SDK. Использовались следующие инструменты: Visual C++ 6.0, Visual Studio 2003, Visual Studio 2008, DirectX SDK April 2007, DirectX SDK August 2007, DirectX SDK March 2008, NVIDIA SDK 9.5, NVIDIA NVPerfHUD 4.1.
2.1. Развитие методов parallax occlusion mapping
Прежде всего, были реализованы несколько методов улучшения детализации поверхностей: normal mapping, две разновидности parallax mapping, parallax occlusion mapping. Две реализации parallax mapping отличаются друг от друга тем, что в одной для вычисления текстурных координат TS` используется пересечение плоскости, проходящей через точку G параллельно касательной плоскости, с вектором наблюдения V (как на рис. 2), а во второй – пересечение сферы с центром в обрабатываемом пикселе и радиусом, равным значению высоты точки G. В первом случае требуется одно деление, одно умножение и одно сложение, а во втором – нормирование вектора V, одно умножение и одно сложение (см. Приложение 1). Но вектор V в любом случае требуется нормировать для вычисления освещения, поэтому второй метод несколько более производительный. Кроме того, в случаях, когда вектор V почти параллелен касательной плоскости, использование первого метода приводит к сильным искажениям из-за слишком большого смещения текстурных координат.
На рис. 8 показан результат отображения плоскости (два треугольника) без применения каких-либо методов улучшения детализации поверхности. Далее показаны методы normal mapping (рис. 9) и parallax mapping (рис. 10). На рис. 11 показаны искажения, вносимые методом parallax mapping при достаточно больших локальных изменениях высоты.
рис. 8
рис. 9
рис. 10
рис. 11
В предлагаемой реализации parallax occlusion mapping, в отличие от других подобных методов, например, relief mapping [35], возможны два направления линейного поиска: вверх и вниз. Для нахождения пересечения вектора V с поверхностью используется направление вниз. Далее, если источник света находится над поверхностью, пересечение вектора, направленного на источник света, с поверхностью (с целью определить, находится ли точка в тени) определяется с помощью линейного поиска вверх. Это можно было реализовать с помощью поиска вниз в направлении от источника света к исследуемой точке, как это сделано в методе relief mapping. Но трассировка вверх понадобится для построения отражений (если вектор отражения направлен вверх). Результат можно посмотреть на рис. 12.
рис. 12
2.1.1. Вычисление градиентов
рис. 13
Для корректной фильтрации текстур и выбора уровня детализации требуются градиенты текстурных координат. На рис. 13 изображен пиксель в пространстве текстурных координат. ddx – вектор производных текстурных координат вдоль оси x пространства изображения, а ddy – вдоль y. Эти векторы позволяют определить, какие элементы текстуры вносят вклад в обрабатываемый пиксель и выполнить фильтрацию. В стандартных функциях выборки текстур градиенты вычисляются автоматически с помощью метода конечных разностей (берутся значения текстурных координат в соседних пикселях). Обычно такой метод дает достаточно точное приближение градиентов. Но на границах объектов происходит разрыв текстурных координат, в соседних пикселях значения текстурных координат сильно различаются. Это приводит к неправильному вычислению градиентов и некорректной фильтрации текстур, что проявляется в виде отдельных точек на силуэтах объектов (рис. 14).
рис. 14
В некоторых реализациях [33] градиенты вычисляются на основе немодифицированных текстурных координат (т.е. из базовой плоскости). Это позволяет избежать разрывов текстурных координат и точек на силуэтах (рис. 15), но внутри объектов градиенты оказываются неправильными. В результате из-за неправильного выбора уровня детализации и фильтрации на одних участках может возникнуть алиасинг (если используется более высокий уровень детализации, чем требуется), на других – потеря четкости (в противоположном случае).
рис. 15
В разработанном алгоритме предлагается комбинированный метод вычисления градиентов. В случае, если градиенты, вычисленные на основе смещенных текстурных координат, больше некоторого порогового значения, используются градиенты на основе немодифицированных координат. В противном случае используются градиенты на основе смещенных координат. Данный метод объединяет достоинства рассмотренных выше двух методов. При правильном выборе порогового значения на силуэтах точки не появляются, а текстуры во внутренних участках корректно фильтруются. Тем не менее, в некоторых случаях для устранения разрывов на границах пороговое значение приходится устанавливать небольшим, и фильтрация внутренних участков по сравнению со вторым методом улучшается не так сильно.
Следующие иллюстрации показывают преимущества предлагаемого метода: на рис. 16 показан результат использования стандартного метода вычисления градиентов (есть точки на границах объектов); на рис. 17 используется метод вычисления градиентов на основе немодифицированных текстурных координат (точек нет, но задняя стенка оказалась размытой); рис. 18 иллюстрирует применение предложенного метода (точек нет, задняя стенка не размыта).
рис. 16
рис. 17
рис. 18
2.1.2. Построение отражений
Отражения в предлагаемом алгоритме реализуются следующим образом. После того, как было найдено пересечение S вектора V с поверхностью и определено, находится ли точка S в тени, вычисляется вектор отражения R и выполняется трассировка в карте высот в направлении от точки S вдоль вектора R.
Если пересечение SR с поверхностью найдено, в точке S отражается сама поверхность (точка SR). В этом случае вычисляется цвет точки SR. Для этого берется значение из диффузной текстуры по смещенным координатам (соответствующим точке SR), вычисляется нормаль. Затем выполняется трассировка в направлении источника света для определения самозатенения и вычисляется освещение точки SR.
Если пересечение при трассировке вдоль вектора V не было найдено, в точке S отражается окружающая среда, а не поверхность. Чтобы получить отражение окружающей среды, используется значение из кубической текстуры. Эта идея используется в методе локальной трассировки лучей.
На рис. 19 показан результат с отключенными отражениями. Далее добавляются отражения с коэффициентом отражения 50% (рис. 20) и 100% (рис. 21).
рис. 19
рис. 20
рис. 21
2.1.3. Вычисление нормалей
Во многих алгоритмах улучшения детализации поверхностей, основанных на трассировке в карте высот, при расчете освещения пикселя нормаль берется из карты нормалей. Но в предлагаемом алгоритме нормаль используется еще и для вычисления вектора отражения R, поэтому требования к точности нормалей усиливаются. В данной реализации использовались текстуры, у которых в первых трех (или двух) компонентах хранились нормали, а в четвертой – высота. Но эти текстуры задавались в неизвестном касательном пространстве, связь между нормалями и высотой (коэффициент масштабирования, который использовался при построении карты нормалей) тоже неизвестна. Предпринимались попытки подобрать коэффициент масштабирования нормалей вдоль оси z касательного пространства, но соответствие с картой высот так и не было достигнуто (кроме того, этот коэффициент может быть разным для разных текстур). Это приводит к неправильному вычислению вектора отражения, что в свою очередь является причиной некорректных отражений. Ниже приведен соответствующий пример (рис. 22). Отражения от горизонтальной плоскости рассчитываются верно (там координаты x и y нормали равны нулю, и коэффициент масштабирования вдоль оси z не влияет на направление нормали), но на боковых стенках отчетливо видны искажения.
рис. 22
Для решения этой проблемы нормали брались не из карты нормалей, а вычислялись методом дифференцирования карты высот. Сначала был реализован метод дифференцирования по трем выборкам из карты высот: центральный элемент текстуры (C), справа от него (R) и сверху (U) (рис. 23). Частная производная функции высоты по координате x аппроксимировалась разницей между значениями высоты в элементах R и C, а по координате y – разницей между U и C. Но такой способ получения нормалей принес другие проблемы (рис. 24). Для сравнения на рис. 25 приведен результат при использовании карты нормалей.
рис. 23
рис. 24
рис. 25
После этого был реализован метод дифференцирования по четырем выборкам: справа (R), слева (L), сверху (U) и снизу (D) от центрального элемента (C) (рис. 26). Частные производные по x и y аппроксимировались разностями между элементами R, L и U, D соответственно. Результат показан на рис. 27.
рис. 26
рис. 27
Также был попробован метод дифференцирования на основе восьми выборок [4]. К четырем выборкам из предыдущего метода добавилось еще четыре выборки, расположенные на диагоналях. На рис. 28 показаны весовые коэффициенты для дифференцирования по x, а на рис. 29 – по y. Но это по-прежнему не решало проблему (рис. 30).
рис. 28
рис. 29
рис. 30
Позже было выяснено, что проблема была вызвана недостаточно качественной картой высот: значения в карте высот менялись слишком дискретно, были области с одинаковым значением высоты, которое резко менялось на другое. В таких областях с одинаковым значением методы дифференцирования высоты давали нормаль, направленную вдоль оси z, там, где она должна быть направлена по-другому (рис. 31), что и приводило к дефектам в виде отдельных точек.
рис. 31
Проблему удалось решить, увеличив шаг дифференцирования. При увеличении шага дифференцирования соседние выборки оказываются в областях с разным значением высоты, в результате чего вычисляется нормаль, направленная не вдоль оси z (рис. 32), и удается избежать дефектов.
рис. 32
Результаты для шага дифференцирования, равного 5, показаны на рис. 33 (3 выборки), рис. 34 (4 выборки) и рис. 35 (8 выборок).
рис. 33
рис. 34
рис. 35
Использование слишком большого шага дифференцирования приводит к другим искажениям. Примеры таких искажений демонстрируются для шага дифференцирования, равного 32, на рис. 36 (3 выборки), рис. 37 (4 выборки) и рис. 38 (8 выборок).
рис. 36
рис. 37
рис. 38
2.1.4. Определение числа итераций
Число итераций, выполняемых в процессе линейного и бинарного поисков, определяет качество получаемого изображения. Но оно также сильно влияет на производительность. В разных ситуациях требования к числу итераций разные. Требования меняются, в частности, в зависимости от наличия мелких деталей и направления вектора, вдоль которого осуществляется трассировка. Например, для вектора, почти параллельного касательной плоскости, требуется большее число итераций, так как в таких ситуациях увеличивается вероятность пропуска мелких деталей.
Первое время для определения числа итераций использовался подход, применяемый в других реализациях трассировки в карте высот: задается минимальное и максимальное число итераций, после чего осуществляется интерполяция между ними. В качестве параметра интерполяции используется координата z нормированного вектора, вдоль которого выполняется трассировка. Таким образом, для вектора, перпендикулярного касательной плоскости, выполняется минимальное число итераций, а для почти параллельного – почти максимальное, что соответствует требованиям. Сначала такой подход использовался и для линейного поиска, и для бинарного. На рис. 39 показана визуализация общего числа итераций (включая итерации для построения теней и отражений). Чем ярче пиксель, тем больше для него выполнялось итераций.
рис. 39
В дальнейшем описанный подход стал применяться только к линейному поиску. Для бинарного поиска стало использоваться фиксированное число итераций. Это было сделано потому, что пропуск мелких деталей определяется точностью только линейного поиска. А бинарный поиск определяет точность нахождения пересечений, которая не зависит от вектора, вдоль которого выполняется поиск.
Несмотря на то, что рассмотренный подход подбирает число итераций в зависимости от направления вектора трассировки, у него есть недостатки. Например, для вектора, перпендикулярного касательной плоскости, можно выполнить только одну итерацию, переместившись на максимальную глубину, так как для такого вектора существует только одно пересечение с поверхностью, и его можно найти с помощью гораздо более быстрого бинарного поиска. А для вектора, почти параллельного касательной плоскости, шаг линейного поиска должен быть гораздо меньше (соответственно число итераций должно быть гораздо больше). Но если указать максимальное число итераций очень большим, то для промежуточных углов наклона вектора число итераций будет быстро увеличиваться, даже если минимальное число итераций установить равным 1. Таким образом, данный подход обеспечивает не очень оптимальное распределение числа итераций в зависимости от угла наклона вектора трассировки. Поэтому был придуман новый метод. В отличие от предыдущего, он вычисляет не число итераций, а связанную с ним величину шага поиска. Для этого сначала задается число элементов карты высот, которое хотелось бы проходить за одну итерацию. Величина шага затем вычисляется таким образом, чтобы проекция шага на касательную плоскость по каждому направлению (x и y) не превосходила указанного числа. Также обеспечивается, чтобы проекция шага на ось z не превосходила максимальной высоты (это возможно для почти перпендикулярных к касательной плоскости векторов). На следующих рисунках показана визуализация числа итераций для разных углов наклона вектора трассировки. Видно, что для почти перпендикулярного вектора (рис. 40) число итераций значительно меньше, чем для вектора, близкого к параллельному (рис. 41).
рис. 40
рис. 41
2.1.5. Проблема ошибочных самозатенений
Используемому методу построения теней присуща проблема ошибочных самозатенений, которая характерна также для алгоритмов shadow mapping. Эта проблема проявляется в виде затенения некоторых точек, которые не должны находиться в тени. Это происходит из-за того, что в некоторых случаях алгоритм нахождения пересечения вектора наблюдения V с поверхностью возвращает точку S`, расположенную немного под поверхностью. Затем, в ходе трассировки от точки S` вдоль вектора L, направленного на источник света, находится пересечение SL с поверхностью (рис. 42), в результате чего алгоритм ошибочно считает, что точка S находится в тени. Помимо ошибочного затенения это приводит еще и к тому, что в точке S (аппроксимированной S`) будет отражаться точка SR, полученная при трассировке от S` вдоль вектора отражения R (рис. 42).
рис. 42
Напрашивается очевидное решение проблемы – сместить точку S` вдоль вектора V на небольшую величину перед тем, как осуществлять трассировки вдоль векторов L и R (рис. 43). В приведенном примере при трассировке от смещенной точки S`` вдоль векторов L и R пересечений с поверхностью найдено не будет, в результате чего обрабатываемая точка не будет затенена, и в ней будет отражаться окружающая среда, а не сама поверхность.
рис. 43
Несмотря на кажущуюся простоту такого способа, существует одна сложность – определение величины смещения. Если она слишком маленькая – точка S`` останется под поверхностью и проблемы останутся, если слишком большая – появятся другие проблемы (отставание теней от отбрасывающих их объектов, некорректные отражения).
В первой реализации использовалось фиксированное смещение. Как оказалось, такой способ иногда может только добавить проблем. На рис. 44 показан пример такой ситуации. В процессе линейного поиска мелкий выступ был пропущен, а после бинарного поиска последняя аппроксимация S` оказалась над поверхностью. Если не делать никакого смещения, то в данном случае все будет нормально (точка не будет считаться затененной, а отражаться в ней будет окружающая среда). Но если выполнить смещение на неудачную для данной ситуации величину, то возникнут упоминаемые выше проблемы.
рис. 44
Далее иллюстрируется пример практического возникновения описанной выше ситуации. На рис. 45 не выполняется никакого смещения, и в то же время не возникает ошибочного самозатенения. При добавлении небольшого смещения начинают появляться дефекты (слева). На рис. 46 приведен результат для коэффициента смещения, равного 0.002. При дальнейшем увеличении величины смещения дефекты исчезают. На рис. 47 используется коэффициент, равный 0.01. Таким образом, для данной ситуации подходят первый и третий варианты величины смещения. Но для других углов зрения и направлений источника света такие варианты могут привести к неудовлетворительным результатам. Для первого варианта (отсутствие смещения) вероятно возникновение ошибочных самозатенений. В третьем варианте используется достаточно большое смещение, что может привести к заметному отставанию теней от отбрасывающих их объектов.
рис. 45
рис. 46
рис. 47
Позже был реализован другой способ выбора величины смещения. Длина вектора смещения выбиралась кратной длине шага линейного поиска. При этом смещение выполнялось относительно точки, полученной в результате выполнения линейного поиска (без уточнения бинарным поиском). В случае не очень большого смещения и достаточного числа итераций линейного поиска гарантируется, что смещенная точка совпадет с точкой, полученной на одной из итераций линейного поиска (за исключением последней). А это в свою очередь гарантирует, что смещенная точка окажется над поверхностью (в противном случае линейный поиск закончился бы раньше – в смещенной точке), благодаря чему удается избежать ошибочных самозатенений.
Описанный выше способ хорошо работает, если шаг линейного поиска не очень большой (т.е. выполняется достаточно много итераций). В противном случае смещение будет слишком большим. Особенно сильно эта проблема проявляется в последней реализации линейного поиска, в которой для увеличения производительности шаг выбирается достаточно большим в тех ситуациях, когда это не приводит к сильному ухудшению качества получаемого изображения. Для векторов трассировки, близких к перпендикулярному к касательной плоскости, выполняется всего одна итерация линейного поиска.
Для решения проблемы некоторое время использовалась модификация приведенного выше метода. Длина вектора смещения выбиралась кратной длине последнего шага бинарного поиска, а не линейного. Кроме того, смещение выполнялось относительно уточненной бинарным поиском точки. При большом числе итераций бинарного поиска смещение оказывается слишком маленьким (точка оказывается слишком близко к поверхности, а также начинает проявляться конечность точности вычислений). Если для смещения использовать большой множитель для устранения названной проблемы, точка может не совпадать ни с одной из точек, полученных в процессе линейного поиска, и возможно возникновение ситуации, проиллюстрированной на рис. 44.
В конечном варианте использовался следующий подход. Сначала в качестве смещенной точки выбирается точка из предпоследней итерации линейного поиска. Если бинарный поиск не выполняется (когда точка, из которой начинался линейный поиск, лежит на поверхности; в этом случае применение бинарного поиска приводит к некорректным результатам), то смещение не меняется. В противном случае при осуществлении бинарного поиска на каждой итерации выполняется следующие действия. Если текущая точка находится выше поверхности и расстояние до поверхности больше некоторого значения (g_max_raytrace_bias), то текущая точка запоминается в качестве смещенной. Сравнение расстояния до поверхности с величиной g_max_raytrace_bias выполняется для того, чтобы точка не оказалась слишком близко к поверхности (одна из проблем предыдущего метода). Стоит отметить, что в итоге расстояние от смещенной точки до поверхности может оказаться как меньше, чем g_max_raytrace_bias (только в том случае, когда расстояние уже от первой смещенной точки (из предпоследней итерации линейного поиска) меньше, чем g_max_raytrace_bias), так и больше (в остальных случаях). Ниже приведен окончательный на данный момент вариант процедуры бинарного поиска.
void BinarySearch(inout float3 dir, inout float3 delta, inout float3 offset, out float3 offset_back, in float2 uv, in float2 dx, in float2 dy, in int binary_search_steps, inout int steps)
{
offset_back = offset - delta;
if (start_diff != 0)
{
float delta_len = length(delta);
for (int cur_step = 0; cur_step < binary_search_steps; cur_step++)
{
delta *= 0.5;
if ((tex2Dgrad(NormalHeightTextureSampler, uv + offset, dx, dy).w * g_max_height - offset.z) * start_diff > 0)
{
// outside
if (delta_len > g_max_raytrace_bias)
offset_back = offset;
offset += delta;
}
else
// inside
offset -= delta;
delta_len *= 0.5;
}
steps += binary_search_steps;
}
}
2.2. Метод локальной трассировки лучей
Сначала выполняется стандартная аппаратная растеризация треугольника с удалением невидимых точек при помощи буфера глубины. Для каждого пикселя ищется пересечение с другими треугольниками в пределах одного объекта (а не всей сцены, как в классической трассировке) в направлении источника света. Если пересечение найдено, пиксель находится в тени. Затем ищется пересечение вдоль отраженного луча. Если оно существует, то выбирается значение цвета из текстуры (текстурные координаты вычисляются на основе барицентрических координат, которые вычисляются в процессе поиска пересечения луча) и снова выполняется трассировка в направлении источника света для определения затенения отраженной точки. Если пересечения вдоль отраженного луча не существует, берется значение из кубической карты. Этот алгоритм устраняет один из основных недостатков построения отражений с помощью кубических текстур – отсутствие самоотражений, которые возможны на невыпуклых объектах. Благодаря тому, что трассировка выполняется для одного объекта, а не для всей сцены, этот алгоритм работает существенно быстрее классической трассировки лучей, и его можно эффективно реализовать на графических процессорах.
Ниже показывается сравнение стандартного метода построения отражений, основанного на применении кубических текстур, с предлагаемым алгоритмом. На рис. 48 для построения отражений используется только кубическая текстура. Из-за этого в местах, где должен отражаться сам объект, отражается окружающая среда. На рис. 49 к кубическим текстурам добавляется локальная трассировка лучей, благодаря чему корректно воспроизводятся самоотражения. К сожалению, для этого примера пришлось отключить тени в отражении, поскольку в противном случае получались некорректные результаты. Скорее всего, это происходит из-за ошибки компилятора HLSL или рекомпилятора шейдеров в драйвере. В режиме программной эмуляции (при использовании устройства D3DDEVTYPE_REF) проблем не возникало, и тени в отражении правильно отображались.
рис. 48
рис. 49
2.2.1. Пространство, в котором вычисляется освещение
Результаты расчета освещения зависят от того, в каком пространстве (системе координат) оно вычисляется. Если системы координат связаны не ортогональными преобразованиями, углы между одними и теми же векторами в разных системах координат будут разными. Из-за этого разными будут и результаты расчета освещения (поскольку они зависят от углов между направлением наблюдения, нормалью, направлением света). Обычно правильными считаются результаты, полученные в пространстве наблюдателя (т.е. после применения к объекту мировых и видовых преобразований, но до проецирования) [5, 28]. На практике освещение рассчитывается в том пространстве, в котором это удобнее или эффективнее реализовать. Если преобразования из используемого пространства в пространство наблюдателя ортогональное, то результаты будут правильными.
В предлагаемых реализациях (это относится не только к локальной трассировки лучей, но и к методам из предыдущей главы) освещение рассчитывается в мировой системе координат. Поскольку система координат наблюдателя получается из мировой применением поворотов и переносов (т.е. ортогональных преобразований), освещение рассчитывается корректно.
2.2.2. Вычисление вектора отражения
Вектор отражения тоже зависит от того, в каком пространстве его вычислять. Также как и освещение, он рассчитывался в мировом пространстве.
Ниже приведен пример, который показывает, что при вычислении в разных пространствах могут получиться разные результаты. На рис. 50 показана ситуация в системе координат S1.
рис. 50
Рассмотрим систему координат S2, переход в которую осуществляется линейным преобразованием сдвига (или скоса) [7]:
|
