Разработка и модернизация методов генерации физически аккуратных изображений на ЭВМ тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Дмитриев, Кирилл Александрович

• Дмитриев, Кирилл Александрович
• кандидат физико-математических наук
• 2002

Оглавление диссертации кандидат физико-математических наук Дмитриев, Кирилл Александрович

Введение

1 Задача генерации физически аккуратных изображений

1.1 Исходные данные.

1.1.1 Геометрия сцены.

1.1.2 Источники света.

1.1.3 ДФРС поверхностей сцены.

1.1.4 Функции параметров наблюдения

1.2 Уравнение рендеринга.

1.3 Методы решения Монте-Карло.

1.4 Методы решения квази-Монте-Карло.

1.5 Проблемы применения метода квази-Монте-Карло для задач генерации изображений.

1.6 Постановка задачи.

2 Реализация метода квази-Монте-Карло в современных индустриальных приложениях

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

2.1.1 Генерация последовательности Холтона.

2.1.2 Генерация ЛПт-последовательности.

2.1.3 Оценка эффективности разработанных алгоритмов

2.2 Трассировка фотонов с использованием квазислучайных последовательностей точек

2.2.1 Общая структура алгоритма.

2.2.2 Уменьшение дисперсии: метод существенной выборки

2.2.3 Оценка эффективности предложенных методов.

2.3 Анализ результатов

3 Оценка погрешности алгоритмов квази-Монте-Карло

3.1 Оценка погрешности в алгоритме БЕРТ.

3.2 Предлагаемый метод оценки погрешности.

3.3 Экспериментальное подтверждение

3.3.1 Сравнение с аналитическим решением.

3.3.2 Сравнение с эталонным решением.

3.4 Анализ результатов

4 Генерация интерактивных последовательностей изображений

4.1 Периодичность последовательности Холтона,.

4.2 Обновление непрямого освещения.

4.2.1 Фотонные группы

4.2.2 Поиск и перетрассировка динамических фотонов.

4.3 Детали реализации.

4.3.1 Структуры трассировки фотонов.

4.3.2 Вычисление прямого освещения

4.3.3 Распараллеливание вычислений

4.4 Оценка эффективности предложенного метода.

4.5 Анализ результатов, развитие задачи.

Введение диссертации (часть автореферата) на тему «Разработка и модернизация методов генерации физически аккуратных изображений на ЭВМ»

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

Заключение

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Дмитриев, Кирилл Александрович, 2002 год

1. Антонов В.М., Салеев И.А. Экономичный способ вычисления ЛЦ--последовательностей // Ж. вычиел. математики и матем. физ. — 1979. — Т. 19, № 1. С. 252-256.

2. Дмитриев К.А. От Монте-Карло к квази-Монте-Карло // Труды конференции ГрафиКон '2002. 2002. - С. 53-59.

3. Дмитриев К.А. Анализ методов оптимизации вычисления глобальной освещенности в компьютерной графике. // Технический отчет, Проект РФТР № 85/2001. 2001 53 С.

4. Михайлов Г.А. К вопросу о построении экономичных алгоритмов моделирования случайных величин. // Ж. вычисл. математики и матем. физ.- 1966. Т. 6, № 6. - С. 1134-1136.

5. Переберин A.B. Многомасштабные методы синтеза и анализа изображений: Дис. .канд. физ.-мат. наук: 05.13.11 — Москва, 2002.

6. Соболь И. М. Многомерные квадратурные формулы и функции Хаара.1. М.: Наука, 1969.

7. Соболь И. М. Численные методы Монте-Карло. — М.: Наука, 1973.

8. Соболь И. М. Вероятностная оценка погрешности интегрирования для

9. ЛП^-сеток // Ж. вычисл. математики и матем. физ. — 1973. — Т. 13, № 4.- С. 1034-1036.

10. Albert G.E. A general theory of stochastic estimates of the neumann series for solution of certain fredholm integral equations and related series. // Symposium on Monte Carlo Methods. — 1956. — P. 37-46.

11. Appel A. Some techniques for shading machine renderings of solids // AFIPS Spring Joint Computer Conference. — 1968. — P. 37-45.

12. Arvo J. and Kirk D. Particle transport and image synthesis // Computer Graphics. 1990. - Vol. 24, No. 4.

13. Bekaert P. Renderpark, a test-bed system for global illumination, (http:// www.cs.kuleuven.ac.be/cwis/research/graphics/RENDERPARK)

14. Cohen M. F. and Greenberg D. P. The hemi-cube: A radiosity for complex environments. // Computer Graphics. — July 1985. — Vol. 19, No. 3. — P. 3140.

15. Cohen M., Chen S., Wallace J. and Greenberg D. A progressive refinement approach to fast radiosity image generation // SIGGRAPH '88 Proceedings.- August 1988. P. 75-84.

16. Cook R., Porter T. and Carpenter L. Distributed ray tracing // SIGGRAPH '84 Proceedings. July 1984. - P. 137-45.

17. Crow F.C. Shadow algorithms for computer graphics // SIGGRAPH 577 Proceedings. July 1977. - P. 242-248.

18. Develov V., Sevastyanov I. One method to Reduce Complexity of Matrix

19. Radiosity Algorithm // Труды конференции ГрафиКон '2000. — 2000. — С. 110-116.1.. Dmitriev К. Efficiency issues on ray tracing machine // Труды конференции ГрафиКон '2000. 2000. - С. 99-103.

20. Dmitriev К. and Kulikova A. Fuzzy reflections rendering // Труды конференции ГрафиКон '2001. 2001. - С. 88-91.

21. Dmitriev К., Brabec S., Myszkowski К. and Seidel H.-P. Interactive global illumination using selective photon tracing // Rendering Techniques '2002. — 2002. P. 100-113.

22. Drettakis G. and Siliion F. Interactive update of global illumination using A line-space hierarchy // SIGGRAPH '97 Proceedings. — August 1997. — P. 57-64.

23. Kopylov E. and Dmitriev K. Light propagation visualization as a tool for 3d scene analysis in lighting design // Computers & Graphics. — 2000. — Vol. 24, No. 1. P. 31-39.

24. Fox В., Bratley P. and Niederreiter H. Implementation and test of low discrepancy sequences // ACM Transactions on Modeling and Computer Simulation. 1992. - Vol. 2, No. 3. - P. 195-213.

25. Goral C, Torrance K, Greenberg D. and Battaile B. Modeling the interaction of light between diffuse surfaces // Computer Graphics. — July 1991. — Vol. 25, No. 4. P. 41-50.

26. Gortler S., Schroeder P., Cohen M. and Hanrahan P. Wavelet radiosity // SIGGRAPH '93 Proceedings. 1993. - P. 221-230.

27. Halton J. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals // Numerische Mathematik. — 1960. Vol 2. - P. 84-90.

28. Hanrahan P., Salzman D. and Aupperle L. A rapid hierarchical radiosity algorithm // SIGGRAPH '91 Proceedings. July 1991. - P. 197-206.

29. Havran V. Heuristic Ray Shooting Algorithms: PhD thesis / Czech Technical University — Prague, Nov. 2000.

30. Heckbert P. Simulating Global Illumination Using Adaptive Meshing: PhD thesis / U.C. Berkeley — June. 1991.

31. Heinrich S. and Keller A. Quasi-Monte Carlo Methods in Computer Graphics Part II: The Radiance Equation // Technical Report 243/94, University of Kaiserslautern, 1994. (http://www. uni-kl. de/AG-Heinrich/Alex.html)

32. Hlawka E. Discrepancy and Riemann Integration, Studies in Pure Mathematics. — New York: Academic Press, 1971 — P. 121-129.

33. Immel D., Cohen M and Greenberg D. Radiosity method for non-diffuse environments // Computer Graphics. — August 1986. — Vol. 20, No. 4. — P. 133-142.

34. Integra Inc Turbo Beam Tracing (TBT) simulation package (http://www. integra.jp)

35. Jensen H. Realistic Image Synthesis Using Photon Mapping. — AK Peters: ISBN: 1568811470, 2001.

36. Kajiya J. The rendering equation // SIGGRAPH '86 Proceedings. — August 1986. P. 143-150.

37. Keller A. The fast calculation of form factors using low discrepancy sequances // Proceedings of the 12. Spring Conference on Computer Graphics. — 1996. P. 195-204.

38. Keller A. Quasi-monte carlo radiosity J J Rendering Techniques '96. 1996.

39. Koksma J.F. Een algemeene stelling uit de theorie der gelijkmatige verdeeling modulo 1 // Tijdschrift voor studeerenden voor de acten wiskunde M.O. en voor studeerenden aan universiteiten. Afdeeling B. — 1943. — Vol 11. — P. 711.

40. Laszlo S.-K. Monte-carlo methods in global illumination // script, Institute of Computer Graphics, Vienna University of Technology, 1999. (http : //www. fsz. bme. hu/~szirmay/puba. html)

41. Lischinski D., Tampieri F. and Greenberg D. Discontinuity meshing for accurate radiosity // IEEE Computer Graphics and Applications. — November 1992. Vol. 12, No. 6. - P. 25-39.

42. Morohosi H. and Fushimi M. A practical approach to the error estimation of quasi-Monte Carlo integrations // Technical Report, University of Tokyo. 1998. (http://citeseer.nj .nec.com/morohosi98practical.litml)

43. Niederreiter H. Low-discrepancy and low-dispersion sequences //J. Number Theory. 1988. - Vol 30. - P. 51-70.

44. Niederreiter H. Random Number Generation and Quasi-Monte Carlo Methods. — Pennsylvania: SIAM, 1992.

45. Nishita T. and Nakarnae E. Continuous tone representation of 3-D objectstaking account of shadows and interrefiection // SIGGRAPH '85 Proceedings.- July 1985. P. 23-30.

46. Owen A. Monte Carlo variance of scrambled net quadrature // SIAM Journal on Numerical Analysis. 1997. - Vol. 34, No. 5. - P. 1884-1910.

47. Press W., Flannery B., Teukolsky S. and Vetterling W. Numerical Recipes: The Art of Scientific Computing, 2nd edition. — Cambridge (UK) and New York: Cambridge University Press, 1992.

48. Rushmeier H. and Torrance K. The zonal method for calculating light intensities in the presence of a participating medium // SIGGRAPH '87 Proceedings. July 1987. - P. 293-302.

49. Ryer A. Light measurement handbook. — Newburyport, MA: International Light Inc., 1997. ISBN 0-9658356-9-3

50. Schoeffel F. and Pomi A. Reducing memory requirements for interactive radiosity using movement prediction // Rendering Techniques '99. — 1999.- P. 225-234.

51. Shirley P. A ray tracing method for illumination calculation in diffuse-specular scenes // Proceedings of Graphics Interface '90. — May 1990. — P. 205-212.

52. Shirley P., Wade B., Hubbard P., Zareski D., Walter B. and Greenberg D. Global Illumination via Density Estimation // Rendering Techniques '95. — 1995. P. 219-230.

53. Shirley P., Wang C. and Zimmerman K. Monte Carlo techniques for directlighting calculations // ACM Transactions on Graphics. — January 1996. — Vol. 15, No. 1. P. 1-36.

54. Siüion F., Arvo J., Westin S., Greenberg D. A global illumination solution for general reflectance distributions // SIGGRAPH '91 Proceedings. — July 1991. P. 187-196.

55. Smits B., Arvo J. and Greenberg D. A clustering algorithm for radiosity in complex environments // SIGGRAPH '94 Proceedings. — July 1994. — P. 435442.

56. Smits B., Arvo J. and Salesin D. An importance-driven radiosity algorithm // Computer Graphics. July 1992. - Vol. 26, No. 2. - P. 273-282.

57. Sobol' I.M., Turchaninov V.l., Levitan Yu.L. and Shukhman B.V. Quasirandom sequence generators. — Moscow: Keldysh Inst. Appl. Maths RAS Acad. Sei., 1992.

58. Spanier J. and Gelbard E. Monte Carlo Principles and Neutron Transport Problems. — Addison-Wesley Publishing Co.: , 1969.

59. Veach E. and Guibas L. Bidirectional Estimators for Light Transport. // Rendering techniques '94. 1994. - P. 147-162.

60. Veach E. and Guibas L. Metropolis light transport // SIGGRAPH '97 Proceedings. — August 1997. — P. 65-76.

61. Volevich V., Myszkowski K., Khodulev A. and Kopylov E. Perceptually-Informed Progressive Global Illumination Solution // Technical Report TR-99-1-002, Department of Computer Science, Aizu University, February 1999.

62. Volevich V., Myszkowski K., Khodulev A., and Kopylov E. Using the visual differences predictor to improve performance of progressive global illumination computations // ACM Transactions on Graphics. — 2000. — Vol. 19, No. 2. P. 122-161.

63. Voorhies D. and Foran J. Reflection vector shading hardware // SIGGRAPH '94 Proceedings. 1994. - P. 163-166.

64. Wald I., Benthin C., Wagner M. and Slusallek P. Interactive rendering with coherent ray tracing // Proceedings of EUROGRAPHICS 2001. 2001. -P. 153-164.

65. Wallace J., Cohen M., and Greenberg D. A two-pass solution to the render-ing equation: A synthesis of ray tracing and radiosity methods // SIGGRAPH '87 Proceedings. July 1987. - P. 311-320.

66. Ward G. The RADIANCE lighting simulation and rendering system // SIGGRAPH '94 Proceedings. July 1994. - P. 459-472.

67. Wernecke J. The Inventor Mentor, Open Inventor Architecture Group. — Addison-Wesley Publishing Co.: , 1994.

68. Whitted T. An improved illumination model for shaded display // Communications of the ACM. June 1980. - Vol. 23, No. 6. - P. 343-349.

69. Williams L. Casting curved shadows on curved surfaces // SIGGRAPH '78 Proceedings. August 1978. - P. 270-274.