16+
ComputerPrice
НА ГЛАВНУЮ СТАТЬИ НОВОСТИ О НАС




Яндекс цитирования


Версия для печати

Модуль поиска не установлен.

Фотореализм в реальном времени

13.10.2004

Алексей Калютов

Как известно, всё или почти всё в этом мире несовершенно. Возможно, в первую очередь это справедливо для искусственных творений. Срок жизни, или эффективности, аппаратного обеспечения составляет порядка трёх лет, то же можно сказать относительно программного обеспечения. Можно ли в таких условиях написать действительно хороший 3D-движок, который хотя бы не устареет к моменту своего релиза? Это зависит от того, что понимать под словом "хороший".

Для качественного рендеринга существует давно известный и активно используемый алгоритм фотореалистической визуализации - обратная трассировка лучей (Ray Tracing), который наряду с методом учёта рассеянного света (Radiosity) представляет собой своеобразную граничную черту, преступать которую не имеет смысла - улучшить качество конечного результата практически невозможно. До недавнего времени подобные алгоритмы считались не только самыми совершенными, но и самыми медленными. Почти 20-летние усилия программистов и специалистов по компьютерной графике изменили подобное положение - уже существующие или разрабатываемые в настоящее время программы рендеринга, представляющие собой удивительную смесь изобретательности, математического мастерства и глубоких идей в области аналитической геометрии и физической оптики, сочетают в себе свойства, которые считались несовместимыми в 3D-графике, - высочайшее качество и быстроту. По-видимому, идея создания алгоритма фотореалистического рендеринга в реальном времени исчерпает себя только после появления программ, способных визуализировать компьютерный мир на обычных PC (а не на многопроцессорных системах) с нормальной скоростью 30 fps. В этой статье подробно рассматривается алгоритм рендеринга, который (вероятно) лежит в основе большинства современных рендеров, и если не является окончательным, то находится недалеко от такового.

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

Каждый луч, пересекающийся с каким-либо объектом, разделяется на два луча - отражённый и преломленный, при этом каждому из них приписывается определённый вес, обусловленный свойствами поверхности предмета. Например, в случае обыкновенного стекла первый луч будет давать вклад в конечную интенсивность луча около 4%, а преломлённый - 96%. Далее этот процесс повторяется для каждого из лучей, и в конце концов возникает дерево, узлам которого соответствуют процессы отражения/преломления света, а соединяющим их линиям (ветвям дерева) - движение луча света от одной точки пересечения с каким-нибудь объектом сцены до другой. Может оказаться, что луч не пересекается ни с одним объектом, в таком случае для данной ветви дальнейшая трассировка заканчивается, а вершине ветви (как и каждому узлу дерева) приписывается определённое значение освещённости в точке последнего пересечения. Процесс трассировки заканчивается также в том случае, когда вклад ветви становится очень маленьким (скажем, меньше 0,01%). Для получения значения освещенности в направлении исходного луча, пущенного в сцену, нужно сложить все освещённости дерева с вычисленными в процессе построения дерева весами. Практически достаточно прослеживать лучи не глубже 10-го уровня, т.е. после 9-10 процессов отражений/преломлений. Если сцена не содержит прозрачных объектов, эта глубина может быть ещё меньше.

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

По-настоящему эффективный и оригинальный алгоритм вычисления рассеянного света и непрямого освещения - метод фотонных карт - появился много лет спустя, в 1994-96 гг. Он заключается в трассировке от каждого источника света некоторого числа лучей - фотонов. Каждая точка пересечения фотона с объектом вместе с текущим значением энергии фотона (которое, собственно, и будет в дальнейшем определять интенсивность света в различных точках пространства), сохраняется в памяти, и совокупность всех этих точек образует так называемую фотонную карту (photon map) сцены, или карту глобальной освещённости. После каждого отражения или преломления на границах объектов фотон изменяет свои характеристики в соответствии со свойствами материала предмета, поэтому фотон как бы переносит цвет (точнее, световую энергию, величина которой принимает различные значения для разных участков спектра). Как следствие, итоговое изображение богато оттенками и мягкими полутонами (эффект colour blending). Для вычисления значения рассеянного освещения в произвольной точке сцены используются несколько ближайших фотонов из фотонной карты. Для того чтобы ускорить поиск соседних фотонов можно, например, разбить всё пространство сцены на отдельные клетки и вести поиск соседей только среди фотонов той клетки, в которую попадает эта точка. Кроме того, существуют более изощренные методы поиска таких соседей - построение из фотонов специальных структур - KD-деревьев и др.

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

Для трассировки лучей ситуация долгое время обстояла по-иному. Здесь основной трудностью была проблема определения пересечения трассируемого луча с объектами, состоящими из полигонов (для объектов типа шара, конуса таких сложностей вообще не существует, поэтому в сцене их может быть сколько угодно, и это не будет особенно сильно сказываться на скорости рендеринга). В типичных 3D-сценах очень много полигонов, так как на каждый объект средней сложности приходится порядка 3000 треугольников. В соответствии с алгоритмом трассировки среди десятков тысяч полигонов нужно найти один - с которым пересекается луч. Эту операцию придётся выполнять для каждого луча, пущенного из точки наблюдения в сцену, а также для отражённых лучей 1-го, 2-го... 10-го уровней. Тогда число треугольников, которые нужно будет проверить на предмет пересечения, будет достигать невообразимой величины. Первые программы рендеринга в самом деле работали очень медленно, и не только вследствие скромной вычислительной мощности машин. Но оставим прошлое историкам и обратимся к современности.

Идеальное решение этой проблемы состоит в том, чтобы сразу найти искомый полигон, без необходимости выполнения какой-либо проверки для всех остальных треугольников. Наиболее плодотворная идея на этот счёт была выдвинута в 1987 г., и после многочисленных изменений, дополнений и других мутаций в 1995-1997 гг. она превратилась в концепцию иерархичных сетей (Hierarchiсal Grids) - структур для сверхбыстрого поиска "того самого" единственного полигона. Первоначальная идея была очень простая и заключалась в том, чтобы всё пространство сцены разделить на множество ячеек и с каждой ячейкой связать попадающие в неё полигоны. Таким образом, проверять на пересечение нужно только те полигоны, которые попадают в пересекаемые лучом ячейки. Для небольших сцен с полигонами примерно одного и того же размера этот метод, который получил название 3DDDA, действительно на два-три порядка ускоряет вычисления, правда, если только правильно подобрать размер ячеек. Дальнейшее развитие этой идеи состоит в том, чтобы разбивать на ячейки не всё пространство, а только прямоугольные области, заключающие в себе, как в ящике, объекты сцены. В англоязычных источниках они так и называются - ограничивающие параллелепипеды (bounding box). Сам процесс разбивки на ячейки выполняется путём рекурсивного деления первоначальной области на две части (поочередно вдоль каждого из трёх направлений) до тех пор, пока в каждой части не останется небольшое число попадающих в неё полигонов. При использовании подобных структур алгоритм поиска треугольника, с которым пересекается луч, сводится к последовательности операций:

- определить объекты, попадающие в видимую область (обычно это 1/8 часть пространства сцены, если считать точку, из которой исходит трассируемый луч, началом координат);

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

- отсортировать все найденные на предыдущем шаге области по удалённости;

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

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

На современном компьютере средней конфигурации в реальном времени можно выполнять фотореалистический рендеринг пока относительно несложных сцен, с заранее заданной геометрией. Для "искусства реального времени" - демо-сцены - попытки визуализировать сцены с использованием алгоритмов обратной трассировки лучей возобновлялись с завидным постоянством на протяжении многих лет (очень небольшая часть всех демонстраций по этой поистине неисчерпаемой тематике находится на http://www.acm.org/tog/resources/RTNews/demos/overview.htm). Алгоритмы фотореалистического рендеринга настолько сложны, что их полная аппаратная реализация - нереальная задача, но ускорение отдельных 3D-операций возможно. Одна из наиболее известных 3D-библиотек - Open GL - использует разновидность традиционного алгоритма обратной трассировки лучей, поэтому аппаратная поддержка некоторых функций OpenGL в современных графических процессорах позволит ещё примерно на порядок увеличить скорость реалистического рендеринга. Учитывая, что большая часть процессорного времени (около 60%) в такого рода алгоритмах тратится на чисто вычислительные операции (работа с векторами - сложение, скалярное и векторное умножение, масштабирование и т.д.), от графического ускорителя требуется быстрое выполнение именно этих операций.

Ещё один путь оптимизации по уменьшению времени рендеринга - использование небольшого числа лучей для определения цвета в отдельных точках изображения с последующей интерполяцией всех остальных пикселей. В тех направлениях, где освещенность меняется медленно или все лучи пересекаются с одним и тем же объектом, можно посылать меньшее их число (в литературе этот алгоритм называется subsampling). В некоторых случаях удаётся получить отличное изображение, послав в сцену всего 10% от общего числа всех лучей, т.е. на каждый пиксель в среднем приходится 0,1 лучей. Такого рода оптимизация очень часто используется как в демонстрациях, так и в программах высококачественного рендеринга, и скорее всего будет применяться в будущих играх на RayTracing-движках, т.к. аппаратная интерполяция значений пикселей поддерживается графическими ускорителями чуть ли не с первых моделей и может выполняться очень быстро. Современные платы используют для этого более совершенные методы - интерполяцию с помощью сплайнов (благодаря чему стало возможным имитировать криволинейные поверхности) и др.

Для разработчиков ПО большой интерес представляют проекты с открытым кодом. Среди последних по рассматриваемой теме особого внимания заслуживает RenderPark (http://www.renderpark.be), распространяющийся под GNU GPL для *nix-систем. Программный код RenderPark на тестовых сценах показывает сравнительно высокую производительность и может служить как основой для серьёзных проектов, так и для использования в качестве обычной программы для рендеринга сцен в формате MGF (внутренний формат) и XRML (расширение VRML)). Основная задача, которую ставили перед собой разработчики данного проекта, заключалась в достижении наилучшей корреляции результата рендеринга реальности, поэтому качество получаемых картинок, которые уже лучше называть фотографиями, - на высшем уровне. В целом этот проект следует рассматривать как коллекцию отлаженных и вполне работоспособных алгоритмов рендеринга, требующих лишь оптимизации по скорости и дополнительного кода для того, чтобы задействовать разнообразные возможности современных графических плат. В пакете реализованы разнообразные модификации метода обратной трассировки лучей и различные алгоритмы вычисления непрямого освещения, которые были разработаны в 90-х гг., включая метод фотонных карт.

Другой открытый проект - это достаточно известный набор инструментов для высококачественного рендеринга Persistence of Vision (POV-Ray, http://www.pov-ray.org/), версии которого (в форме бинарного кода и в виде исходных текстов) существуют почти под все известные платформы. Он включает один из наиболее продвинутых рендеров, адаптированный под современное железо. Этот проект включает достаточно подробную документацию по исходникам и по работе с самими программами.

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

Первая иллюстрация получена с помощью моего собственного рендера, написанного на основе описанных в этой статье алгоритмов и технологий. Время рендеринга, указанное в подписи, не включает время, затраченное на расчёт фотонной карты (около 1,5 с). Для оценки вычислительной сложности алгоритма все 3D-функции эмулировались программно. Последнее изображение - результат работы рендера из пакета RenderPark, скомпилированного из исходных текстов. Ориентировочная конфигурация системы: Athlon 1GHz, 256 MB, OS Red Hat Linux 9.0.



статьи
статьи
 / 
новости
новости
 / 
контакты
контакты