Задала прикладных пакетов генерации изображений, как правило, состоит в автоматической генерации изображения сцены по заданным исходным данным. Этот процесс схематически изображен на Рис. 1. Сцена представляет собой цифровую модель виртуальной системы объектов, включаюгцую все необходимые данные для генерации изображения на ЭВМ. Она содержит описание объектов и их свойств, так или иначе влияющих на распространение световой энергии в пространстве, а именно: геометрии объектов, их расположения в пространстве и оптических свойств, расположения и характеристик источников света, оптических свойств полупрозрачных сред и т. д. Иногда сцена может включать также данные для генерации анимационной или интерактивной последовательности изображений. В том случае, если применяемые при генерации изображения методы основаны на физических законах взаимодействия света с объектами, получаемые изображения называются физически аккуратными.
Вычисления.
Сцена исходные данные) О.
Изображение у V.
Рис. 1: Схема генерации изображений.
Актуальность задачи.
Задача разработки программных средств автоматической генерации изобра,-жений по заданным исходным данным является весьма актуальной в настоящее время. Человеко-машинные интерфейсы систем автоматического проектирования, баз да, нных и знаний, игровых приложений и т. д., часто реализуются посредством визуализации некоторых объектов (природа, которых зависит от конкретного приложения). Хотя еще совсем недавно мощности ЭВМ хватало лишь для схематичной визуализации объектов, бурное развитие компьютерной техники сделало возможным генерацию высокореалистичных изображений. Это не только позволило улучшить существующие приложения, но и открыло ряд новых применений ЭВМ.
Для реалистичной визуализации необходимо моделировать взаимодействие света, с объектами, что является вычислительно сложной задачей. Даже мощности современных ЭВМ часто не достаточно для решения ее с приемлемой скоростью. Поэтому иногда для повышения эффективности прибегают к различным эвристическим подходам, не претендующим на физическую аккуратность. Хотя это позволяет значительно повысить скорость, для достижения реалистичности обычно необходима трудоемкая настройка параметров алгоритма для конкретной сцены или коррекция полученного изображения вручную.
Более перспективным направлением представляется повышение эффективности за счет использования более совершенных методик построения физически аккуратных изображений. Это направление является одним из приоритетных в мировой индустрии компьютерной графики. Программные модули физически аккуратного моделирования включены в последние версии таких известных программ визуализации как 3D Studio МАХ, 3D Studio VIZ, RenderMan.
Одним из перспективных способов повышения скорости генерации изображений является использование метода квази-Монте-Карло вместо традиционно используемого Монте-Карло. Теоретическое преимущество метода квази-Монте-Карло давно обосновано исследователями в обла, сти мат. моделирования [б, 7, 8, 56]. Тем не менее, остается ряд теоретических и практических трудностей применения этого метода, в программных средствам визуализации и виртуальной реальности.
Локальное и глобальное освещение.
Для расчета физически аккуратных изображений необходимо моделировать процесс распространения света от источников света к глазу наблюдателя. При этом влияние фотонов света, прошедших разными путями, удобно рассматривать раздельно. При дальнейшем изложении будем, следуя [29], классифицировать фотонные траектории в соответствии с событиями, которые произошли с фотонами на пути от источника к глазу наблюдателя. Используем следующие обозначения из работы [29]:
• Е — глаз наблюдателя;
• L — источник света;
• S — идеальное преломление или отражение;
• D — не идеальное преломление или отражение луча;
• * - символ итерации, т. е. например S* означает некоторое количество идеальных преломлений или отражений;
• [ ] - символ, обозначающий возможное событие;
• | - символ разделяет два альтернативных события;
Любой путь, представляющий интерес для задали генерации изображений, начинается символом Ь и заканчивается Е. Поэтому все возможные пути света принадлежат классу Ь[Б|8]*Е.
Широкое распространение методы генерации физически аккуратных изображений получили только в последнее десятилетие, когда производительность вычислительных машин стала, достаточной для решения подобных задач. В настоящее время на рынке доступны мощные графические ускорители, позволяющие визуализировать чрезвычайно сложные модели в реальном времени. Тем не менее, точность расчета освещения, предоставляемая большинством прикладных пакетов очень невысока,. При расчете изображений они учитывают только световые пути, не требующие больших вычислительных затрат. Например, упомянутые графические ускорители рассчитывают только пути 1ЛЗЕ, т. е. прямое освещение объектов, создаваемое светом, приходящим напрямую от источников света без отражений и/или преломлений поверхностями и/или рассеивающими средами сцены.
Между тем, непрямое освещение часто оказывает огромное влияние на изображение. Например, на Рис. 2 представлено изображение простой сцены, состоящей из параллелепипеда, с находящимися внутри него сферой, многогранником и кольцом. Многогранник и кольцо выполнены из металла, сфера, состоит из стекла. В сцене присутствует один конический источник света. При расчете Рис. 2 а) учтено влияние только наиболее простых для расчета фотонных путей ЪБ[8]*Е. Большая часть изображения черная, так как соответствующие части поверхности освещены непрямым светом. Рис. 2 Ь) демонстрирует изображение той же сцены, рассчитанное с учетом всех возможных фотонных путей Ь[Б|3]*Е. Яркие пятна на стенах параллелепипеда создаются светом, отраженным от граней многогранника. Яркая дуга — свет, отраженный от металлического кольца. Стеклянная сфера фокусирует падающий на нее свет в яркий круг на полу под ней. Эти зрелищные эффекты называются каустиками и образуются фотонными путями Ь[Б|8]*80Е. Мягкое непрямое освещение на стенках и потолке образуется фотонными путями.
Рис. 2: Изображение сцены, рассчитанное с учетом а) фотонных путей ЬВ[8]*Е и Ь) всех возможных фотонных путей Ь[Б|3]*Е .
Методы расчета, позволяющие учесть более широкий класс фотонных путей, чем ЬО[8]*Е, носят название методов вычисления глобального освещения. Методы моделирования глобального освещения можно условно разделить на две группы: методы конечных элементов и методы Монте-Карло.
Ьр|8]*БОЕ. а).
Ъ).
Вычисления непрямого освещения: методы конечных элементов.
Методы конечных элементов для переноса световой энергии были изначально адаптированы из литературы по моделированию переноса тепла. Основополагающе, я идея заключается в разбиении геометрии сцены на достаточно малые конечные элементы и расчет распределения освещенности в результате решения системы алгебраических уравнений (обычно линейных), описывающей перенос энергии между этими конечными элементами. Впервые в компьютерной графике подобные методы предложили использовать Горал [24], Кохен [13] и Нишита [44] и именно тогда эти методы получили свое название: «методы излучательности». С тех пор было реализовано много усовершенствований к этим методам. Например: инкрементальное повышение качества решения [14], использование иерархических базисных функций [27], адаптация объема вычислений в каждом регионе сцены в соответствии с его значимостью [55], разбиение по границам теней [40], применение вейвлетов для уменьшения ошибки дискретизации [25], кластеризация [54] и геометрическая декомпозиция [17]. Были реализованы разновидности метода, позволяющие корректно моделировать преломление и поглощение света в полупрозрачных средах [47], пере отражение света от глянцевых и зеркальных поверхностей [32] и от поверхностей с произвольными Двулучевыми Функциями Рассеивающей Способности (ДФРС) [53].
Недостатком методов излучательности является то, что они допускают эффективную реализацию лишь для небольшого подкласса задач. А именно, их успешно применяют для диффузных сцен, содержащих источники света с простыми функциями яркости. Обобщение метода конечных элементов на другие виды сцен хотя и возможно, но требует слишком больших объемов памяти. Поэтому традиционно в таких задачах применяются методы Монте-Карло.
Методы Монте-Карло.
Методы Монте-Карло начали использоваться для проблем переноса нейтронов с 50-х годов [9], и с тех пор всесторонне изучены для этих задал [57]. В компьютерной графике методы Монте-Карло начали использовать независимо, начинал с работы [10], где изображения вычислялись с использованием трассировки случайных фотонов. В [67] было предложено использовать рекурсивную трассировку лучей, а также была обсуждена идея о внесении случайных искажений в направление луча для устранения лестничного эффекта в изображении, связанного с конечным размером пикселей экрана ЭВМ. В [15] эта идея была не только реализована, но и дополнена. С помощью случайного выбора точки на источнике света, точки на линзе виртуальной камеры, момента, времени и направления отражения луча от глянцевой поверхности предлагалось моделировать эффекты физически аккуратных мягких теней, расфокусированных изображений, размытости быстро движущихся объектов и нечетких отражений соответственно.
Эти работы стали предпосылкой к появлению первого алгоритма Монте-Карло с несмещенной оценкой для вычисления физически аккуратных изображений, который был предложен в [35]. В [35] было показано, что задача вычисления глобального освещения может быть сформулирована в виде интегрального уравнения Фредгольма, второго рода и может быть решена методом трассировки путей. Затем последовало много усовершенствований этого первого алгоритма. Основные из них: [11, 58, 59]. Кроме этих основополагающих работ, было предложено много алгоритмов со смещенной оценкой, которые как правило более эффективны. Например, в [65] был предложен алгоритм кэширования освещенности, использующий информацию об особенностях геометрии для вычисления освещенности лишь в некоторых точках пространства и использующий интерполяцию для получения полного решения. В [51] был предложен эффективный алгоритм реконструкции освещенности по оценке плотности фотонов в сценах с полигональной геометрией, а в [34] - метод фотонных карт, позволяющий проводить расчеты для сцен с любым типом геометрии.
Кроме этого, были предложены алгоритмы, сочетающие особенности методов Монте Карло и конечных элементов. Обычно это многопроходные алгоритмы, которые чередуют проходы методами излучательности и трассировкой фотонов Монте-Карло с целью обработки более широкого класса сцен [64]. Еще один подход — излучательносгь Монте-Карло, где решение представляется в виде базисных функций на, сетке конечных элементов, как в методе излучательности. но коэффициенты базисных функций вычисляются с помощью трассировки случайных лучей [50].
Алгоритмы, основанные на методе Монте-Карло обычно более универсальны. Возможна реализация, напрямую генерирующая изображения без хранения каких-либо промежуточных данных, что позволяет обрабатывать сцены практически любой сложности. При этом существуют эффективные методы оценки погрешности результатов, основалные на теории вероятностей.
Основным недостатком алгоритмов Монте-Карло является их медленная скорость сходимости к точному решению. Хотя первые результаты могут быть получены уже через несколько секунд после начала счета, шум, являющийся признаком недостаточной точности, исчезает из изображений чрезвычайно медленно.
Другим недостатком существующих алгоритмов Монте-Карло является их неспособность использовать когерентность глобального освещения во времени при генерации анимационных или интерактивных последовательностей. Перемещение даже больших объектов сцены обычно вызывает очень локальное, сконцентрированное в одном месте, изменение освещения. Большинство существующих алгоритмов не используют это свойство и вычисляют каждый кадр последовательности заново.
Методы квази-Монте-Карло.
В основе метода Монте-Карло лежит использование последовательностей псевдослучайных чисел для интегрирования сложных, обычно многомерных, функций. Как альтернативу можно рассматривать использование заведомо неслучайных, но более равномерных последовательностей точек с низким отклонением или квазислучайных последовательностей точек.
Первые работы по применению таких последовательностей для интегрирования появились в других областях знаний задолго до начала применения метода Монте-Карло. Например, теорема Коксмы об оценке 1-мерных интегралов с помощью последовательности равномерно распределенных чисел [38] относится к 1943 году.
В компьютерной графике квазислучайньте последовательности точек стали применяться совсем недавно. Одна из первых работ с использованием квазислучайных точек в компьютерной графике относится к 1996 году [36], где метод был применен для оценки форм-факторов в алгоритме излучательности. Приблизительно к этому же времени относится применение метода квази-Монте-Карло в алгоритме трассировки фотонов [37].
В работе [30] было показано, что алгоритмы квази-МонтеКарло сходятся к точному решению быстрее, чем алгоритмы Монте-Карло. Тем не менее, использование метода в индустриальных приложениях затруднено по следующим причинам.
1) Реализация эффективных генераторов квазислучайных точек довольно трудоемка и должна проводится с учетом особенности конкретного алгоритма. Например, многие существующие реализации генерируют все координаты заданной точки сразу. В алгоритмах же трассировки фотонов не требуется генерировать квазислучайные точки целиком — генерируются только координаты, необходимые для трассировки текущего фотона.
2) При моделировании источников света со сложным распределением интенсивности, или поверхностей со сложными рассеивающими свойствами, необходимо моделировать нетривиальные распределения вероятности. Традиционно в алгоритмах Монте-Карло для этого используется метод отказов. В случае использования квазислучайных точек, это ведет к ухудшению производительности (см. раздел 2.2.2), поэтому необходимо искать другие способы моделирования таких объектов.
3) На сегодняшний день не существует надежного способа оценки погрешности алгоритмов квази-Монте-Карло трассировки фотонов. В научных публикациях по применению метода погрешность определяется на основе сравнения с известным точным решением. При решении практических задач этот способ неприменим, так как точное решение обычно не доступно.
Цель работы.
Обоснование целесообразности применения метода квази-Монте-Карло в алгоритмах генерации изображений. Оптимизация алгоритмов генерации ква,-зислучайных точек с учетом требований данной прикладной области. Реализация алгоритма квази-Монте-Карло генерации физически аккуратных изображений. Разработка метода оценки погрешности реализованного алгоритма. Изучение возможности модификации реализованного алгоритма для эффективной генерации интерактивных последовательностей изображений.
Научная новизна работы.
Предложены новые способы рекуррентной генерации последовательностей Холтона, и ЛПТ, оптимизированные для алгоритмов трассировки фотонов. Предложены и обоснованы ряд новых рекомендаций по использованию квазислучайных последовательностей точек в алгоритмах генерации изображений. Разработана новая методика оценки погрешности алгоритмов квази-Монте-Карло и дано ее экспериментальное обоснование. Предложена, новая методика использования свойств последовательности Холтона для нахождения фотонов с близкими траекториями, что дает возможность концентрировать вычисления в нужном районе сцены.
Практическая значимость.
Разработана и реализована модификация базового алгоритма, Монте-Карло, описанного в [61]. Реализованная модификация использует квазислучайные последовательности точек вместо псевдослучайных чисел, что позволяет достичь лучшей производительности. При реализации алгоритма были решены ряд проблем, мешающих применению квазислучайных последовательностей точек в прикладных пакетах визуализации и генерации физически аккуратных изображений.
Кроме этого, разработан и реализован новый алгоритм генерации интерактивных последовательностей изображений. Реализованный алгоритм имеет широкое практическое применение, так как позволяет достичь интерактивной скорости генерации изображений сложных сцен даже на стандартном персональном компьютере.
Апробация работы и публикации.
Основные результаты диссертации представлены в публикациях [2, 3, 18, 19, 20, 22]. Предложенные алгоритмы для генерации статических физически аккуратных изображений были внедрены в прикладной пакет генерации изображений. Алгоритм для генерации интерактивных последовательностей изображений был представлен на конференции «Eurographics Workshop on Rendering'2002, Pisa, Italy».
Структура диссертации.
Изложение последующих глав организовано следующим образом. В первой главе описана модель исходных данных, используемая при дальнейшем изложении, и дан краткий теоретический обзор методов Монте-Карло и квази-Монте-Карло. Обоснована целесообразность применения методов квази-Монте-Карло и сформулированы проблемы, решаемые в диссертационной работе.
Во второй главе обоснованы рекомендации по реализации алгоритма квази-МонтеКарло трассировки фотонов. В частности: предложены эффективные алгоритмы генерации квазислучайных последовательности Холтона и ЛПГописана модификация базового алгоритма DEPT [61] для использования ква,-зислучайных последовательностей чиселпредложен алгоритм моделирования источников света и рассеивающих свойств поверхностей любой сложности без применения метода отказов.
В третьей главе рассмотрен вопрос оценки погрешности разработанного комплексного алгоритма квази-Монте-Карло. Показана неприменимость оценки погрешности способом, используемым в базовом алгоритме и предложена ее корректная модификация. Описаны численные эксперименты, подтверждающие точность предложенной оценки погрешности в различных ситуациях. Представлены результаты численных экспериментов по определению расчетной эффективности предложенного комплексного алгоритма квази-Монте-Карло.
В четвертой главе представлена, модификация базового алгоритма, использующая свойства квазислучайной последовательности Холтона для генерации интерактивных последовательностей изображений.
В заключении формулируются основные результаты работы.
Приложения содержат список использованных обозначений и предментый указатель.
Благодарности.
Автор выражает благодарность научному руководителю Ю. М. Банковскому и научному консультанту В. А. Галактионову за содействие и помощь в работе, компании Integra Inc. (http://ww.integra.jp) за предоставление исходных кодов базовой системы генерации физически аккуратных изображений.
Основные результаты работы состоят в следующем:
1. Существующие алгоритмы генерации точек квазислучайных последовательностей Холтона и ЛПт усовершенствованы с учетом требований задач визуализации. Численные эксперименты показали, что применение усовершенствованных генераторов существенно сократило общее время вычисления изображений по сравнению с использованием других генераторов этих последовательностей. Реализованные генераторы требуют при трассировке фотонов даже меньше вычислительных ресурсов, чем стандартный генератор псевдослучайных чисел. Обоснованы преимущества ЛПг-последовательности для генерации статических изображений.
2. Разработан комплексный алгоритм, использующий квазислучайные последовательности точек для вычисления непрямого освещения. В рамках его разработки:
— решена задача моделирования источников света со сложными распределениями интенсивности и ДФРС поверхностей со сложными функциями рассеивания без использования метода отказов;
— предложен способ понижения конструктивной размерности интегрирования.
Проведены численные эксперименты и представлены их результаты, показывающие значительно возросшую скорость сходимости к точному решению по сравнению с исходным алгоритмом.
3. Предложена методика оценки погрешности разработанного комплексного алгоритма квази-Монте-Карло. Для этого обоснован способ получения двух квазислучайных последовательностей, А и В из одной исходной. Разность между решениями Е^ {х) и Е^(х), полученными с помощью этих последовательностей, использована для оценки погрешности. Предложенная методика позволяет оценивать погрешность результатов вычислений в любой момент времени без значительных вычислительных затрат и с высокой точностью.
4. Разработан алгоритм генерации интерактивных последовательностей изображений. Реализованный алгоритм использует свойство периодичности квазислучайной последовательности Холтона для интерактивного обновления изображения при изменении сцены. Эффективная реализация алгоритма позволяет использовать его для достаточно сложных сцен на стандартных ЭВМ.
5. Продемонстрированы преимущества использования методов квази-Монте-Карло для задач генерации физически аккуратных изображений. Разработанные алгоритмы позволяют применять этот метод в индустриальных приложениях, так как снимают многие существовавшие ранее проблемы.
Заключение
.
Рассмотрена задача разработки программных средств визуализации путем генерации физически аккуратных изображений и их последовательностей. Известно, что это требует вычисления значений, в общем случае, бесконечномерных интегралов, чем объясняется широкое применение методов Монте-Карло в данной области. В настоящее время одним из основных инструментов для генерации физически аккуратных изображений являются методы Монте-Карло, реализуемые на ЭВМ с помощью псевдослучайных чисел. На основе проведенного анализа обоснована целесообразность перехода к методам квази-Монте-Карло, использующим более равномерно распределенные квазислучайные точки для повышения точности и скорости визуализации.
Поставлены и решены ряд проблем, связанных с переводом существующих алгоритмов Монте-Карло генерации изображений на использование квазислучайных точек. Изучены возможности методов квази-Монте-Карло для генерации интерактивных последовательностей изображений.
