% Общие поля титульного листа диссертации и автореферата
\institution{Институт Прикладной Математики имени М.В. Келдыша Российской Академии Наук }

\topic{ Методы решения проблемы глобальной освещенности на графических процессорах }

\author{Фролов Владимир Александрович}

\specnum{05.13.11}
\spec{ Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей }
%\specsndnum{ 05.13.11 }
%\specsnd{Компьютерная графика и вычислительная оптика}

\sa{Галактионов Владимир Александрович}
\sastatus{д.~ф.-м.~н., проф.}

%\scon{ФИО консультанта}
%\sconstatus{д.~ф.-м.~н., проф.}
%\sconsnd{ФИО второго консультанта}
%\sconsndstatus{д.~ф.-м.~н., проф.}

\city{Москва}
\date{\number\year}

% Общие разделы автореферата и диссертации
\mkcommonsect{actuality}{Актуальность работы}{% 
Проблема глобальной освещенности - одна из основных проблем расчета освещения. Освещенность принято разделять на локальную и глобальную. 
Локальной освещенностью точки поверхности называют освещенность, вызванную прямым попаданием света от его источника.
Глобальной освещенностью точки поверхности называют освещенность, вызванную как прямым так и непрямым попаданием света в данную точку (т.е. в результате одного или более переотражений).
В настоящее время расчет глобальной освещенности на электронно-вычислительных машинах (ЭВМ) находит широкое применение. Выделим три основных группы сфер применения алгоритмов расчета глобальной освещенности.

\noindent Первую группу сфер применения алгоритмов вычисляющих глобальное освещение составляет синтез реалистичных изображений:

\begin{enumerate}
\item Оценка внешнего вида любых промышленных изделий, находящихся в проекте. Прежде всего это моделирование внешнего вида переносных электронных устройств (телефоны, ноутбуки, планшеты), персональных транспортных средств (автомобилей, мотоциклов и других транспортных средств, для которых важен внешний вид).  
\item Архитектурный дизайн - моделирование экстерьеров, интерьеров помещений, салонов транспортных средств в целях оценки уровня освещенности и эстетичности соответствующего интерьера или экстерьера. 
Для архитектурных проектов особенно важно уметь демонстрировать как будет выглядеть спроектированное здание или интерьер дома в различных условиях освещения.
\item Создание рекламных и демонстрационных презентаций. В данной сфере применение можно условно разделить на демонстрацию решения, находящегося в проекте и дополненную реальность - встраивание виртуального 3D объектва в видео-последовательность или изображения, снятые с реального мира.
\item Киноиндустрия, мультипликация и индустрия компьютерных игр. В последнем случае реалистичный расчет освещенности применяется особенно часто для создания карт освещенности.  
\end{enumerate}

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

\noindent Вторая группа сфер применения расчета глобальной освещенности связана с моделированием оптических эффектов для определенного ряда задач:
\begin{enumerate}
\item Расчет уровня освещенности приборов в кабине самолета, поезда или другого транспортного средства, а также офисных помещений в целях соблюдения государственных стандартов.   
\item Моделирование осветительных приборов, панелей ЖК-дисплеев.
\item Расчет нежелательных слепящих или ухудшающих видимость эффектов, вызванных отражениями света от зеркальных поверхностей. 
Среди примеров таких эффектов можно отметить отражения светящихся элементов приборной панели в лобовом стекле автомобиля, отражения ярких источников света на экране монитора, 
отражения солнечного света от ярких поверхностей автобилей и архитектурныъх сооружений.  
\end{enumerate}

\noindent Cферы применения из данной группы требуют высокоточного расчета освещения в виртуальной сцене и, как следствие, вычисления глобальной освещенности.

\noindent Третья группа сфер применения алгоритмов вычисления глобальной освещенности связана с расчетом переноса не-светового излучения. Особенно важна задача расчета переноса нейтронов в ядерных реакторах.
Алгоритмы глобальной освещенности могут быть использованы для расчета переноса не-светового излучения, если поведение такого излучение для заданной модели в достаточной мере описывается законами геометрической оптики.


\setlength\tabcolsep{1pt}   
\begin{table}[h]    
\begin{tabular}{| c | c |}
  \hline  
   
  \includegraphics[width=0.5\linewidth]{alpha_romeo_MC} & \includegraphics[width=0.5\linewidth]{exterior2} \\
   
  \includegraphics[width=0.5\linewidth]{bedroom_MC} & \includegraphics[width=0.5\linewidth]{cabin_MC2} \\
  \hline   

\end{tabular}
\caption{ Примеры применения разработанной системы. }  
\label{table:applications1}
\end{table}


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


Такие алгоритмы как кэш освещенности и фотонные карты дают смещенную оценку (то есть не обладают точностью в пределе), но позволяют получить приемлемое изображение за гораздо меньшее время, поскольку они в значительной мере переиспользуют результаты вычислений.
Однако их реализация на графических процессорах затруднена по ряду причин:
\begin{enumerate}
\item Переиспользование результатов вычислений уменьшает общий объем вычислений, однако, приводит к необходимости явной синхронизации и необходимости построения ускоряющих структур на графических процессорах.
\item Методы реалистичной визуализации со смещенной оценкой решения требуют особые способы контроля точности. Существующие подходы на основе смещенных методов или не Монте-Карло (не основанных на Монте-Карло трассировке лучей) алгоритмов на графических процессорах не удовлетворяют необходимым критериям точности и направлены на интерактивный синтез изображений для компьютерных игр.
\end{enumerate}

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

}

\mkcommonsect{objective}{Цель диссертационной работы}{%
состоит в разработке эффективных методов решения проблемы глобальной освещенности на графических процессорах на основе алгоритмов, дающих смещенную оценку решения и разработке системы расчета освещенности, реализующей эти методы.
Под эффективностью метода понимается следующие два требования: 

\begin{enumerate}

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

\end{enumerate}

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

\noindent Для достижения поставленной цели необходимо решить следующие \textbf{задачи}:

\begin{enumerate}

\item Исследовать существующие алгоритмы и методы вычисления глобальной освещенности и синтеза реалистичных изображений на центральных и графических процессорах.
\item Выявить основные проблемы, возникающие при адаптации наиболее эффективных алгоритмов вычисления глобальной освещенности со смещенной оценкой решения к архитектуре графических процессоров и предложить методы их решения. 
  
  \begin{enumerate}
  \item Разработать алгоритм распределения работы для метода Монте-Карло на графических процессорах в применении к задаче вычисления глобальной освещенности на множестве пикселей изображения.
  \item Разработать параллельную реализацию алгоритма кэширования освещенности на графических процессорах, позволяющую значительно снизить время построения изображения при сравнимом с эталонным методом Монте-Карло качестве.
  \item Разработать метод построения ускоряющей структуры на графических процессорах, позволяющий эффективно реализовать алгоритм фотонных карт.
  \end{enumerate}

\item Создать систему расчета освещенности на графических процессорах с использованием технологии CUDA. 
\item Интегрировать разработанную систему в среду трехмерного моделирования 3d Studio Max.
  
\end{enumerate}


}

\mkcommonsect{novelty}{Научная новизна}{%

\noindent Получены следующие новые результаты в области расчета глобальной освещенности на графических процессорах.


\begin{enumerate}

\item Предложен алгоритм распределения работы для эффективной реализации метода Монте-Карло на графических процессорах в применении к задаче вычисления глобальной освещенности и фото-реалистичного синтеза изображений.
      Алгоритм позволяет эффективно распределить вычислительные ресурсы графического процессора на множестве пикселей изображения с неравномерной сложностью расчета.
      В отличие от появившихся позднее аналогов, алгоритм позволяет сохранять пространсвенную близость групп лучей, что повышает эффективность 
      использования ресурсов графического процессора за счет снижения числа расходящихся по разным веткам групп потоков. 
      
\item Предложена параллельная реализация алгоритма кэширования освещенности на графических процессорах, позволяющая снизить время построения изображения в 10 раз 
      по сравнению с традиционным методом Монте-Карло при сравнимом качестве получаемого изображения.
      В отличие от существующих параллельных реализаций кэша освещенности или реализаций, частично использующих графические процессоры, 
      в предложенном подходе впервые решена проблемма одновременной вставки в кэш большого числа не-дублирующих друг друга записей.
      За счет этого достигнута масштабируемость алгоритма и возможность легкой интеграции в существующие системы расчета освещения на графических процессорах. 
      
\item Разработан метод построения ускоряющей структуры на графических процессорах, позволяющий от 2 до 5 раз ускорить сбор освещенности в алгоритме фотонных карт по сравнению с существующими методами.
      Разработанный метод впервые позволил строить окто-деревья со множеcтвенными ссылками над множеством объектов ненулевого размера полностью параллельно на графических процессорах. 
      Метод прост в реализации и использует только 2 примитивных операции параллельного программирования - параллельное добавление элементов в буфер и параллельную сортировку.
      В отличие от других способов построения фотонной карты, предложенный метод строит ускоряющую структуру, позволяющую выполнить процесс сбора освещенности в заданной точке со всех фотонов
      в единственном цикле сбора, не содержащем ветвлений.
  
\end{enumerate}

}

\mkcommonsect{value}{Практическая значимость}{%

\noindent Разработанный программный комплекс может быть использован для расчета освещения и реалистичной визуализации при работе в среде моделирования 3D Studio Max.
Основные сферы применения: 

\begin{enumerate}
\item Оценка внешнего вида и реалистичная визуализация любых проектов промышленных изделий.
\item Архитектурный дизайн - моделирование экстерьеров, интерьеров помещений, салонов транспортных средств для оценки уровня освещенности и эстетичности соответствующего интерьера или экстерьера. 
\item Создание рекламных и демонстрационных презентаций. 
\item Расчет нежелательных оптических эффектов при проектировании архитектурных и инжереных сооружений.  
\end{enumerate}

}

\mkcommonsect{results}{%
На защиту выносятся следующие основные результаты и положения:}{%

\begin{enumerate}

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

\item Метод построения окто-дерева со множественными ссылками на графических процессорах, способный работать с объектами ненулевого размера и от 2 до 5 раз ускоряющий сбор освещенности в методе фотонных карт по сравнению с аналогами.

\item Система расчета освещенности на графических процессорах, значительно превосходящая по скорости существующие аналоги.

\end{enumerate}

}

\mkcommonsect{approbation}{Апробация работы}{%
Основные результаты диссертации докладывались на следующих конференциях:

\begin{enumerate}

\item Международная Конференции по Компьютерной Графике и Зрению GraphiCon'2009 (Москва, факультет ВМК МГУ).
\item Международная Конференции по Компьютерной Графике и Зрению GraphiCon'2010 (Санкт-Петербургский государственный университет информационных технологий, механики и оптики).
\item Международная Конференции по Компьютерной Графике и Зрению GraphiCon'2012 (Москва, факультет ВМК МГУ).
\item Международная Конференции по Компьютерной Графике и Зрению GraphiCon'2013 (Институт автоматики и процессов управления ДВО РАН, Дальневосточный Федеральный Университет). 
\item Семинар по компьютерной графике и машинному зрению Ю.М. Баяковского (Москва, факультет ВМК МГУ).
\item Семинар направления «Программирование» им. М. Р. Шура-Бура в ИПМ им. М. В. Келдыша.
\item Тринадцатый научно-практический семинар новые информационные технологии в автоматизированных системах. Московский государственный институт электроники и математики.

\end{enumerate}

}

\mkcommonsect{pub}{Публикации.}{%
Материалы диссертации опубликованы в $8$ печатных работах, из них $2$
статей в рецензируемых журналах \cite{Frolov_2011, Frolov_2013} $4$ статьи в
сборниках трудов конференций, $1$ в учебном пособии и $1$ тезис доклада.
}

\mkcommonsect{contrib}{Личный вклад автора}{%
Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы.
Подготовка к публикации полученных результатов проводилась совместно с соавторами, причем вклад диссертанта был определяющим. Все представленные в диссертации результаты получены лично автором.
}

\mkcommonsect{struct}{Структура и объем диссертации}{%
Диссертация состоит из введения, обзора литературы, $4$ глав, заключения и библиографии.
Общий объем диссертации $P$ страниц, из них $p_1$ страницы текста, включая $f$ рисунков.
Библиография включает $B$ наименований на $p_2$ страницах.
}
