Российская академия наук

Институт прикладной математики им. М.В. Келдыша

На правах рукописи

Волобой Алексей Геннадьевич

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

Специальность 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.

Автореферат

диссертации на соискание ученой степени

кандидата физико-математических наук

Москва – 2005

Работа выполнена в Институте прикладной математики

им. М.В. Келдыша РАН.

Научный руководитель – кандидат физико-математических наук, старший научный сотрудник Галактионов Владимир Александрович

Официальные оппоненты:

– доктор физико-математических наук, профессор

Платонов Александр Константинович,

– кандидат физико-математических наук

Крылов Андрей Серджевич.

Ведущая организация:

Институт вычислительной математики и математической геофизики Сибирского отделения РАН

Защита состоится « 07 » июня 2005 г. в 11 часов на заседании Диссертационного совета Д 002.024.01 в Институте прикладной математики им. М.В. Келдыша РАН по адресу: 125047, Москва, Миусская пл., 4.

С диссертацией можно ознакомиться в библиотеке Института прикладной математики им. М.В. Келдыша РАН.

Автореферат разослан «____» апреля 2005 г.

Ученый секретарь диссертационного совета

доктор физико-математических наук Т.А. Полилова

Общая характеристика работы

Актуальность проблемы

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

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

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

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

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

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

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

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

Цель работы

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

Научная новизна работы

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

Практическая значимость

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

На базе концепций и технологий, предложенных в диссертации, были реализованы индустриальные программные продукты Visualizer (контекстная визуализация пространственных данных), Lkernel (Интернет приложение моделирования освещенности) и Fly (интерактивная система реалистичной визуализации).

Апробация работы и публикации

Основные результаты диссертации были доложены на международных конференциях [3, 4, 7, 8, 12], опубликованы в рецензируемых журналах [2, 5, 6, 10, 13], сборнике статей [1] и препринтах ИПМ им. М.В. Келдыша РАН [9, 11]. Основные результаты диссертационной работы были внедрены и использованы в

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

- индустриальных программных комплексах фирмы Integra Inc, Япония.

Структура и объем работы

Диссертация состоит из введения, пяти глав, заключения и списка литературы. Содержание работы изложено на 137 страницах. Список литературы включает 111 наименований. В работе содержится 45 рисунков и 7 таблиц.

Содержание работы

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

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

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

В главе подробно описан алгоритм компактного хранения октарного дерева. Исторически задача создания компактной модели хранения октарного дерева возникла в ходе работы над двумя проектами – создание системы синтеза реалистичных изображений Ray3D на машинах класса IBM PC (в то время это были Intel 286 и 386) и экспериментов с распараллеливанием алгоритма трассировки лучей на транспьютерах. Система синтеза реалистичных изображений Ray3D была полностью разработана автором.

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

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

Рис. 1. Ссылки на порожденные узлы октарного дерева.

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

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

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

· Для IBM PC и транспьютера Т800 на VME–плате PARSYTEC первоначальная модель хранения октарного дерева была неприемлема. Использование компактной модели хранения позволило реализовать систему реалистической визуализации для этих вычислительных машин. В частности, система Ray3D, реализованная на IBM РС, была интегрирована в биологический программный комплекс GeneBee.

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

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

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

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

Рис. 2. Равномерное разбиение пространства сцены с равномерным делением подобластей. Трассируемый луч показан красным цветом.

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

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

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

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

Автор рассматривает понятие «правдоподобности» цветового изображения и предлагает контролировать его с помощью двух критериев:

Критерий L2:

L2 = SUM {dr²+dg²+db²},

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

Критерий L0:

L0 = MAX {max (dr, dg, db)},

где функция MAX – выбор максимума по всем точкам рисунка. Этот критерий даёт возможность контролировать смещение какого-либо цвета в соседний цвет спектра.

Идея метода состоит в следующем. Цветовой куб разбивается на подпространства плоскостями перпендикулярными осям координат, таким образом, чтобы плотность разбиения была выше там, где более плотно расположены точки. Каждой итоговой клетке разбиения выделяется один цвет. Это позволяет иметь большее число изображаемых цветов для основных (доминирующих в этой картинке) цветовых областей, представленных большим количеством точек. Более детальное изображение основных областей позволит "сгладить" картинку, так как незначительное изменение цвета хорошо заметно на больших поверхностях и почти не видно на линиях или для различных точек. Улучшение цветного изображения картинки таким методом численно должно выразиться в уменьшении значений критерия L2, но пока никак не учитывает критерий L0, что может привести к значительному, видимому для глаза, смещению цветов, представленных небольшим количеством точек. Проблема значительного смещения цветов была решена введением начального, равномерного разбиения, которое гарантирует несмешиваемость основных цветов.

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

Естественным развитием изучения цветового восприятия человека и разработки методов преобразования физических величин яркости в цветовые координаты дисплея является в наши дни алгоритмы сжатия физических величин с большим диапазоном значений. Для отображения изображений с большим динамическим диапазоном яркостей на стандартных устройствах отображения, таких как графические дисплеи, этот диапазон должен быть сжат до уровня, который может быть воспроизведен на этих устройствах. Глаз и нервная система человека по-разному обрабатывает большой и малый диапазоны яркости видимого изображения. Механизм обработки сигналов, который успешно работает при большом диапазоне яркостей (например, при соотношении яркостей сотни тысяч к одному), просто не включается при обработке изображения с экрана, где диапазон мал (сотни к одному). Следовательно, для создания реалистичного изображения необходимо смоделировать процесс обработки больших яркостей глазом. В литературе такой оператор сжатия называется tone mapping или tone reproduction. Качество работы таких операторов оценивается главным образом по уровню сохранения деталей изображения, локального контраста и отсутствию артефактов (некорректных изображений). Существенным фактором являются также скорость работы алгоритма и объем требуемой памяти, поскольку в настоящее время все более актуальным становится обеспечение работы в режиме реального времени.

Для создания эффективного оператора сжатия за основу был взят оператор, называемый улучшенным оператором Тумблина-Рушмеера, в основе которого лежит вычисление адаптационной яркости изображения , определяемой как среднее логарифмическое всех яркостей изображения. Оператор сжатия использует модель сохранения яркости, основанную на математической модели человеческого зрения Стивенса. Целью этой модели является обеспечение постоянного отношения яркости изображения, воспринимаемого с экрана монитора, к яркости соответствующей части реальной сцены при любых условиях освещения. Улучшенный оператор Тумблина-Рушмеера уменьшает контраст изображения на мониторе для очень темных изображений, что предотвращает избыточность контраста.

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

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

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

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

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

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

Схема реализации контекстной визуализации пространственных данных изображена на рис. 3.

Рис. 3. Схема реализации контекстной визуализации пространственных данных.

Как уже упоминалось, система контекстной визуализации работает с произвольными пространственными данными. Набор данных с определенным для него способом визуализации называется презентационным набором данных. Подготовка презентационных наборов данных реализована как отдельный компонент – адаптер пространственных данных (VDA – Volumetric Data Adapter), который предоставляет интерактивный интерфейс для загрузки исходных массивов и выбора компонентов для презентационных наборов.

Выделенные презентационные наборы данных передаются затем в генератор презентационной геометрии (PGG – Presentation Geometry Generator). PGG генерирует презентационную геометрию в форме плоскостей с изолиниями или с тоновой заливкой, стрелок и т.д., в зависимости от формы представления, выбранной пользователем. Сформированная презентационная геометрия добавляется к геометрии текущей сцены и отображается средствами графической библиотеки (GL – Graphics Library) графической системы. Таким образом, сама сцена, которая часто состоит из большого количества объектов, требующих специальной предварительной обработки для эффективной визуализации, не видоизменяется. Добавленная презентационная геометрия содержит относительно небольшое число объектов, и она практически не влияет на общую эффективность визуализации. Это позволят включать и выключать визуализацию пространственных данных в интерактивном режиме.

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

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

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

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

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

Рис. 4. Организация Интернет-приложения для интерактивного физически аккуратного моделирования освещенности; взаимодействие компонентов пользовательского интерфейса с серверным компонентом

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

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

Рис. 5. Схема работы пользователя.

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

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

В таблице 1 приведены результаты измерений, демонстрирующих ускорение вычислений, достигнутое за счет использования квазислучайных выборок вместо псевдослучайных последовательностей при расчете глобальной освещенности методом Монте-Карло. Измерения проводились для сцен Office и Montage, предоставленных фирмой-производителем осветительных приборов Zumtobel, Австрия, с различными значениями итоговой точности. Время вычислений указано в секундах.

Сцена	Точность (%)	T_MC	T_QMC	Ускорение (раз)
Office	97	332.164	224.057	1.48
Office	98	757.918	486.441	1.56
Montage	97	54.202	32.624	1.66
Montage	98	135.731	70.717	1.92
Montage	99	972.882	243.072	4.00

Таблица 1. Сравнение времени вычислений при использовании псевдослучайных последовательностей (T_MC) и квазислучайных выборок (T_QMC) в расчетах глобальной освещенности методом Монте-Карло.

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

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

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

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

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

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

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

В системе было принято решение реализовать несколько режимов генерации изображения:

1) простой режим, где изображение генерируется с помощью закраски по Фонгу, аппаратно поддерживаемой через OpenGL;

2) режим вывода глобальной освещенности, где в качестве цветов вершин используются преобразованные физические значения глобальной освещенности, рассчитанные предварительно с помощью модуля физически аккуратного моделирования;

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

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

Рис. 6. Архитектура системы генерации реалистичных изображений в реальном времени.

В реализованном программном комплексе Fly имеется два ядра для генерации изображений: генерация изображений методом обратной трассировки лучей (BRT – Backward Ray Tracing) и визуализация сцены через OpenGL. Каждый из этих ядер предъявляет свои требования к представлению сцены в памяти. Например, пространственное разбиение сцены необходимо для ускорения трассировки лучей, в то время как геометрические объекты могут быть заданы как полигональными сетками, так и замкнутыми объектами (сферами, цилиндрами и т.д.). Для визуализации сцены через OpenGL геометрия сцены должна быть представлена набором треугольников, а пространственное разбиение сцены не требуется. Поэтому описание сцены подготавливаются специальным образом для каждого ядра визуализации. Такая схема с единым начальным представлением сцены и отдельными подготовленными представлениями для каждого ядра позволяет легко расширять методы визуализации, использующиеся в системе.

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

· генерация источников света, соответствующих солнцу и небесному освещению;

· генерация заднего плана, изображающего небо и солнце;

· генерация теней от солнца и текстур освещения, которые используются для визуализации теней.

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

Реализованный программный комплекс Fly обеспечивает визуализацию оптически сложных материалов, заданных через двунаправленную функцию отражения (ДФО). ДФО может быть задана в наиболее общем, табличном виде. Была использована оригинальная технология поточечного вычисления освещения поверхности с оптически сложным материалом, зависящая от ДФО. Технология основывается на вычислении специальной текстуры, которая накладывается на объект с помощью аппаратных средств. Текстуры строятся для каждого источника света, а потом складываются и наносятся на объект с помощью аппаратных средств через OpenGL (reflection mapping).

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

Рис. 7. Изображения оптически сложной автомобильной краски, освещенной пятью источниками света. Левый рисунок получен трассировкой лучей. Правый рисунок получен в реальном времени.

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

Рис. 8. Примеры визуализации вторичной освещенности. Левый рисунок получен трассировкой лучей. Правый рисунок получен в реальном времени.

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

Тесты показали, что программный комплекс способен строить вполне реалистичные изображения с естественным освещением, визуализацией двунаправленных функций отражения, вторичной освещенностью в реальном времени. Результаты тестов, оценивающих производительность комплекса на сценах различной сложности, показаны в таблице 2. Тесты выполнены на обычном персональном компьютере (процессор Pentium4 2,8 ГГц, 1 Гб оперативной памяти, графическая карта Radeon 9700 Pro). Значения приведены в количестве кадров в секунду.

Сцена	Количество треугольников	Вывод карт освещенности	Простой режим	Естественное освещение
Mercedes	137551	35 к/с	33 к/с	12 к/с
Jaguar	107222	38 к/с	33 к/с	14 к/с
House	312923	26 к/с	24 к/с	7 к/с

Таблица 2. Скорость генерации изображений (к/c - число кадров в секунду).

Разработанный программный комплекс показал себя мощным интерактивным средством реалистичной визуализации, исследования и модификации трехмерных сцен (3D browser), содержащих оптически сложные материалы.

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

Основные результаты работы состоят в следующем:

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

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

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

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

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

Публикации по теме диссертации

[1] Волобой А.Г., Динамический подбор палитры в системах реалистической визуализации. Библиотека информационной технологии: Сборник статей. Выпуск 3. Под ред. Г.Р. Громова. Москва, 1991, стр. 214-221.

[2] Волобой А.Г., Метод компактного хранения октарного дерева в задаче трассировки лучей. «Программирование», № 1, 1992, стр. 21-27.

[3] Волобой А.Г., Задача компактного хранения октарного дерева в методе трассировки лучей. Труды 2-ой Международной конференции «Компьютерная графика в науке и искусстве» – ГрафиКон-92, Москва, 1992, стр. 3-6.

[4] Волобой А.Г., Система реалистической визуализации Ray3D. Тезисы Международной конференции-выставки по свободному системному и прикладному программному обеспечению в среде ОС UNIX. Москва, 1993, стр. 84-90.

[5] Voloboj A.G., The method of dynamic palette construction in realistic visualization systems. Computer Graphics Forum, Vol. 12, № 5, December 1993, pp. 289-296.

[6] Барладян Б.Х., Волобой А.Г., Галактионов В.А., Копылов Э.А., Эффективный оператор сжатия динамического диапазона яркостей. «Программирование», № 5, 2004, стр. 35-42.

[7] Ignatenko A., Barladian B., Dmitriev K., Ershov S., Galaktionov V., Valiev I., Voloboy A.,A Real-Time 3D Rendering System with BRDF Materials and Natural Lighting. The 14-th International Conference on Computer Graphics and Vision GraphiCon-2004, Conference Proceedings, Moscow, 2004, pp. 159-162.

[8] Vassiliev V., Voloboy A., Vyukova N., Context-Aided Visualization of Volumetric Data. Proceeding of GraphiCon’2004 - The 14-th International conference of Computer Graphics and Vision, Moscow, 2004, pp. 151-154.

[9] Васильев В.Р., Волобой А.Г., Вьюкова Н.И., Галактионов В.А., Контекстная визуализация пространственных данных. Препринт Института Прикладной Математики им. М.В. Келдыша РАН № 56, 2004.

[10] Васильев В.Р., Волобой А.Г., Вьюкова Н.И., Галактионов В.А., Контекстная визуализация пространственных данных. «Информационные технологии и вычислительные системы», № 4, 2004, стр. 25-34.

[11] Барладян Б.Х., Волобой А.Г., Вьюкова Н.И., Галактионов В.А., Дерябин Н.Б., Моделирование освещенности и синтез фотореалистичных изображений с использованием Интернет технологий. Препринт ИПМ им. М.В. Келдыша РАН № 57, 2004.

[12] Барладян Б.Х., Волобой А.Г., Вьюкова Н.И., Галактионов В.А., Дерябин Н.Б., Интернет сервис для моделирования освещенности и синтеза фотореалистичных изображений. 15-ая Международная конференция по компьютерной графике и машинному зрению – Графикон-2005, Новосибирск, 2005.

[13] Барладян Б.Х., Волобой А.Г., Вьюкова Н.И., Галактионов В.А., Дерябин Н.Б., Моделирование освещенности и синтез фотореалистичных изображений с использованием Интернет технологий. "Программирование", 2005, в печати.