\documentclass[autoref,subf,href,facsimile,colorlinks=true
%,fixint=false
%,times
%,classified
]{disser}

\usepackage[a4paper,nohead,includefoot,mag=1000,
            margin=2cm,footskip=1cm]{geometry}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{tabularx}
\ifpdf\usepackage{epstopdf}\fi

% Поддержка нескольких списков литературы в одном документе
\usepackage{multibib}
% Создание команд для цитирования собственных работ диссертанта
% в отдельном разделе. В данном случае ссылка будет иметь вид \citemy{...}.
\newcites{my}{Список публикаций}

% Путь к файлам с иллюстрациями
\graphicspath{{fig/}}

\begin{document}
% Включение файла с общим текстом диссертации и автореферата
% (текст титульного листа и характеристика работы).
\input{common}

% номер копии для грифа секретности
%\copynum{1}
% класс доступа
%\classlabel{Для служебного пользования}

\title{АВТОРЕФЕРАТ\\
диссертации на соискание ученой степени\\
кандидата физико-математических наук}

\maketitle

% Внутренняя сторона обложки
\noindent
\begin{center}
Работа выполнена в \emph{Институте Прикладной Математики имени М.В. Келдыша Российской Академии Наук}.
\end{center}
\vskip1ex
\begin{tabularx}{\linewidth}{lp{1cm}X}
Научный руководитель:  & & \emph{д.ф.м.н.}, \\
                       & & \emph{профессор}, \\
                       & & \emph{Галактионов Владимир Александрович}
\\
Официальные оппоненты: & & \emph{ученая степень}, \\
                       & & \emph{ученое звание}, \\
                       & & \emph{фамилия имя отчество}\\
                       & & \emph{ученая степень}, \\
                       & & \emph{ученое звание}, \\
                       & & \emph{фамилия имя отчество}
\\
Ведущая организация:   & & \emph{название организации}\\
\end{tabularx}

\vskip2ex\noindent
Защита состоится \datefield{} в \rule[0pt]{1cm}{0.5pt} часов
на заседании диссертационного совета \emph{шифр совета} при \emph{название
организации, при которой создан совет}, расположенном по адресу:
\emph{адрес}

\vskip1ex\noindent
С диссертацией можно ознакомиться в библиотеке
\emph{название организации}.

\vskip1ex\noindent
Автореферат разослан \datefield{}

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

\vfill\noindent
Ученый секретарь\\
диссертационного совета,\\
\emph{ученая степень}, \emph{ученое звание}%
\hfill
\makeatletter
% вставка файла, содержащего факсимиле ученого секретаря
\ifDis@facsimile
  \raisebox{-4pt}{\includegraphics[width=3cm]{sec-facsimile}}\hfill
\fi%
\makeatother%
\emph{фамилия и. о.}

\clearpage

\nsection{Общая характеристика работы}

% Актуальность работы
\actualitysection
\actualitytext

% Цель диссертационной работы
\objectivesection
\objectivetext

% Научная новизна
\noveltysection
\noveltytext

% Практическая значимость
\valuesection
\valuetext

% Результаты и положения, выносимые на защиту
\resultssection
\resultstext

% Апробация работы
\approbationsection
\approbationtext

% Публикации
\pubsection
\pubtext

% Личный вклад автора
\contribsection
\contribtext

% Структура и объем диссертации
\structsection
\structtext

\nsection{Содержание работы}

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

\textbf{В первой главе} дается введение в предметную область и анализ основных литературных источников, посвященных проблеме глобальной освещенности. Даются определения основных терминов и понятий, вводятся основные математические модели и рассматриваются базовые алгоритмы вычисления глобальной освещенности.

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

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

В \underline{разделе 3.1} рассматривается предложенный метод построения изображения на графических процессорах в целом. Обсуждаются его преимущества и недостатки по сравнению с существующими решениями.

\noindent Стандартная реализация трассировки путей, применяемая в таких системах как IRay, Octane, Arion, VRayRT имеет определенные недостатки. 

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

\noindent Второй недостаток стандартной трассировки путей при реализации на GPU заключается в том, что несмотря на то, что каждый луч может быть обработан независимо, общая вычислительная нагрузка и обращения к памяти сильно нерегулярны. Это ухудшает производительность при реализации трассировки лучей на массивно-параллельном процессоре. Предложенный подход позволяет в значительной мере амортизировать проблемму дивергентных потоков и нерегулярного доступа к памяти за счет группировки лучей в пространственно-близкие группы в 2 местах: 

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

В \underline{разделе 3.2} рассматривается алгоритм адаптивной трассировки путей.

\noindent Одна из серьезных проблем при реализации метода Монте-Карло для вычисления глобальной освещенности на множестве пикселей изображения заключается в неравномерном объеме вычислений, необходимом для каждого пиксела. Стандартная реализация трассировки лучей на GPU, при которой одному пикселу всегда соответствует 1 поток в этом случае не эффективна, поскольку все потоки вынуждены делать такое же число Монте-Карло выборок, какое требуется для самого сложного в расчетном плане пиксела. Для решения этой проблемы предложен специализированный алгоритм распределения работы. 
 
\noindent В начале расчета изображения экран изображения разбивается на блоки 8x8 или 16x16 пикселей. Внутри каждого блока пикселы нумеруются согласно Кривой Мортона. Это позволяет в значительной степени сохранить пространственную близость лучей с последовательно-идущими номерами потоков что, в свою очередь положительно сказывается на скорости трассировки лучей вследствие уменьшения числа дивергентных групп потоков warp. Далее все блоки добавляются в список активных блоков. Из списка всех активных блоков, графический процессор извлекает ровно M блоков, которые он может обработать параллельно. При этом число M определяется заранее выделенным для программы объемом памяти (т.е. это позволяет ограничить объем потребляемой памяти с ростом разрешения изображения). Если число активных блоков в списке меньше M, в список добавляются дубликаты каждого блока за счет удваивания числа лучей, трассируемых на 1 пиксел. Такой подход позволяет создать достаточно работы для GPU при любом числе активных блоков и при этом всегда занимать фиксированный объем памяти.
 

В \underline{разделе 3.3} рассматривается реализация параллельного кэша освещенности на графических процессорах и механизм интеграции такого кэша в программу расчета освещения. 

\noindent Изначально последовательный алгоритм кэшировани освещенности работает по схеме ленивых вычислений. Новые записи в кэш вставляются тогда, когда в них появляется необходимость. Параллельная вставка записей в кэш освещенности на GPU порождает 3 основные проблемы:

\begin{enumerate}

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

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

\item \underline{Вычисление радиусов валдиности записей}. Радиусом валидности записи кэша освещенности называют радиус, в пределах которого запись может быть использована для интерполяции. Для вычисления этого радиуса однопоточная реализация использует ряд эвристических методов, основывающихся на последовательной вставке точек в кэш. При одновременной вставке в кэш больших групп записей, эти методы приводят к чрезмерному перекрытию записей и последующей медленной интерполяции (выборкам из кэша). Для решения этой проблеммы был предложен алгоритм уменьшения радиусов валидности основанный на контроле степени перекрытия записей.


\end{enumerate}

В \underline{разделе 3.4} предлагается метод построения окто-дерева со множественными ссылками на графических процессорах для ускорения сбора освещенности в алгоритме фотонных карт. 

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

\noindent Разработанный метод применен для ускорения операции сбора освещенности в алгоритме фотонных карт и позволяет ускорить сбор освещенности от 2 до 5 раз.


\textbf{В четвертой главе} описывается разработанная система расчета освещенности. Проводится сравнение с существующими аналогами.

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

\nsection{Основные Результаты Работы}

\begin{enumerate}
\item Разработаны эффективные параллельные алгоритмы вычисления глобальной освещенности на графических процессорах на основе алгоритмов со смещенной оценкой решения.

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

\item Создана система расчета освещенности на графических процессорах, значительно превосходящая по скорости существующие аналоги. Разработанная система интегрирована в среду трехмерного моделирования 3d Studio Max 2012 и 2013

\end{enumerate}

Список основных публикаций  - \cite{Frolov_2011, Frolov_2013, Frolov_2013_GC, Frolov_2009, Frolov_2010_NIT, Gruzdev_2012, Gruzdev_2013, mortikov2012parallelnye1250402}.

% ----------------------------------------------------------------
\renewcommand\bibsection{\nsection{Список публикаций}}

\bibliographystylemy{gost705}
\bibliographymy{thesis}

\renewcommand\bibsection{\nsection{Публикации по теме диссертации}}


\bibliographystyle{gost705}
\bibliography{thesis}
% ----------------------------------------------------------------

\end{document}
