\documentclass[12pt,subf,href,colorlinks=true]{article}



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

\title{Задание 2: Излучательность}
\author{
        Фролов Владимир, Алексей Игнатенко \\
}
\date{\today}

\usepackage{graphicx}
\graphicspath{{img/}}
\renewcommand{\baselinestretch}{1.25}

% listings

\usepackage{color} %% это для отображения цвета в коде
\usepackage{listings} %% собственно, это и есть пакет listings
\usepackage{caption}
\DeclareCaptionFont{white}{\color{white}} %% это сделает текст заголовка белым
%% код ниже нарисует серую рамочку вокруг заголовка кода.
\DeclareCaptionFormat{listing}{\colorbox{gray}{\parbox{\textwidth}{#1#2#3}}}
\captionsetup[lstlisting]{format=listing,labelfont=white,textfont=white}


\lstset{ %
language=C,                % выбор языка для подсветки (здесь это С)
stepnumber=1,              % размер шага между двумя номерами строк
tabsize=2,                 % размер табуляции по умолчанию равен 2 пробелам
}


\begin{document}
\maketitle

\begin{abstract}
Основная цель данного задания - изучение основ метода излучательности, расчёта глобальной освещенности и базовой визуализации. Задание предполагает реализацию метода излучательности \underline{целиком}, но для простой трехмерной сцены. При его выполнении придётся столкнуться с трассировкой лучей, либо с проективными преобразованиями. Для выполнения данного задания необходимы базовые знания линейной алгебры и аналитической геометрии, и умениие программировать на любом языке. Желателено иметь опыт любой трехмерной визуализации. Объем расчётной части задания (без учёта визуализации, создания окна и.т.д) - около 500 строк кода.

\end{abstract}

\section{Введение}
Алгоритм излучательности - один из самых старых методов расчёта глобальной освещенности. Однако, это не означает, что сегодня он потерял свою актуальность. Позже мы рассмотрим применение излучательности в движке <<Frostbyte 2>> (на котором сделана игра <<Battlefield 3>>) компании <<DICE>>. Но сначала остановимся на описании метода и непосредственно самом задании.

\section{Базовые принципы работы излучательности}

Излучательность (Radiosity) по определению - это энергия, покидающая поверхность на единицу площади и в единицу времени. Алгоритм расчёта освещения, называемый также словом -<<излучательность>> исходит в своей основе из закона сохранения энергии и предположения <<энергетического равновесия>>. 

Давайте рассмотрим простой пример (комнату из 4 стен в 2D, рисунок \ref{fig:room1} ) и попробуем разобраться, что это означает. Предположим, что одна из стен излучила некоторое количество энергии (световой) в некотором очень коротком промежутке времени (и тут же потухла). Закон сохранения энергии говорит, что вся энергия которая была излучёна этой стеной останется внутри комнаты. Для излученного света это означает, что он весь придет на остальные 3 стены. 

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

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

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

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.75\linewidth]{room1}           
  \caption{\label{fig:room1}
          Простая 2D комната со светящимся потолком.}
\end{figure}

Таким образом, термин <<энергетическое равновесие в системе>> для нас на самом деле всего лишь означает, что \underline{уровень освещенности в сцене не меняется со временем}. То есть мы можем игнорировать время и рассматривать <<мгновенное>> решение. 
  
\section{Алгоритм излучательности в общем}


Алгоритм излучательности работает в терминах энергии, переносимой между небольшими площадками (patch).

\begin{enumerate}

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

\item Источники света также представляются площадками, излучающими энергию.

\item Для каждой пары площадок расчитывается так называемый форм-фактор $F_{ij}$. Форм фактор $F_{ij}$ представляет собой часть энергии, переносимой с патча $i$ на патч $j$. таким образом получаем матрицу. Из закона сохранения энергии следует, что вся излучённая энергия их патча i энергия должна прийти на какие-то другие патчи. То есть сумма форм-факторов в строке должна быть равна 1.

\item После того как форм-факторы известны, начинается процесс решения линейного уравнения излучательности. Идет расчёт того, какая часть фактической энергии на какие площадки переходит. Здесь возможны как минимум 2 способа - прямой расчёт и решение СЛАУ. Мы опишем прямой расчёт, т.к. он проще в понимании и практичней в реализации (переход к СЛАУ делает площадки равнозначными друг относительно друга, а это не позволит сделать иерархическую излучательность).

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

\end{enumerate}

\section{Сцена}\label{scene}

В качестве основного геометрического элемента предлагается использовать выровненные по осям координат прямоугольники (Axis Aligned Quad). Этот примитив определяет прямоугольник, находящейся в 1 из 3 плоскостей - XoY, XoZ или YoZ. Его можно задать в виде позиции $P$ и размера в 2 направлениях, перпендикулярных вектору нормали $n$ (рисунок \ref{fig:planes}). Нормаль $n$ у прямоугольника XoY может быть либо (0,0,1), либо (0,0,-1).


\begin{figure}[htb]
  \centering
  \includegraphics[width=0.75\linewidth]{planes}           
  \caption{\label{fig:planes}
           Выровненные по осям координат прямоугольники и прямоугольный параллелипипед.}
\end{figure}

С таким примитивом достаточно легко искать пересечение луча. Пусть у вас есть луч с началом в точке $O$ и направлением $D$. И есть плоскость YoZ. Тогда параметрическая координата $t$ точки пересечения луча и плоскости будет равна $t_{hit} = (P.x - O.x)/D.x$. Для того чтобы понять, пересекает ли луч ваш прямоугольник, Вам останется проверить, лежит ли найденная точка (выражаемая из уравнения прямой как $P_{hit} = O + D*t_{hit}$) в пределах границ прямоугольника.  

Вы можете составить из таких прямоугольников стены комнаты, паралеллипипеды и более сложные сцены (рисунок \ref{fig:mine}). Вы также можете испольховать любое другое представление поверхностей сцены.


\begin{figure}[htb]
  \centering
  \includegraphics[width=0.75\linewidth]{mine}           
  \caption{\label{fig:mine}
           Скриншот из игры minecraft.}
\end{figure}

\section{Расчёт форм-факторов}\label{factors}


Дифференциальный Форм-Фактор для двух площадок $i$ и $j$ (рисунок \ref{fig:07_patches}) записывается следующим образом:

$$ FdA_idA_j = \frac{\cos{\theta_i}\cos{\theta_j}}{\pi r^2}  $$

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.35\linewidth]{07_patches}
  \caption{\label{fig:07_patches}
           Взаимное расположение патчей. }
\end{figure}

Полный форм-фактор для заданного патча будет равен интегралу от дифференциального форм-фактора по площади рассматриваемого патча. Формально, полный Форм-Фактор для двух площадок $i$ и $j$ определяется следующим образом: 

$$ F_{ij} = \frac{1}{A_i} \int\limits_{x \in p_j} \int\limits_{y \in i_j} \frac{\cos{\theta_i}\cos{\theta_j}}{\pi r^2} V(x, y) dy dx $$

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

Мы приведем здесь простой (и долгий) алгоритм расчёта форм-факторов при помощи трассировки лучей и метода Монте-Карло. Монте-карло интегрирование позволяет посчитать интеграл как сумму большого числа случайных выборок (для форм-факторов нужно примерно от 200 до 1000 выборок). В случае форм-факторов нужно N раз сгенерировать по 2 случайные точки на площадках, посчитать для каждой пары точек дифференциальные форм-факторы и усреднить результат. Полученный результат необходимо умножить на площади обоих площадок (рисунок \ref{fig:mc_formfactor}).

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.5\linewidth]{mc_formfactor}           
  \caption{\label{fig:mc_formfactor}
           Интегрирование форм-факторов при помощи Монте-Карло метода и трассироки лучей.}
\end{figure}


\subsection{Свойства форм-фактора}

Перечислим основные свойства форм-фактора:
\begin{itemize}

\item \textbf{Зависимость от геометрии сцены.}
\textit{Форм-Фактор зависит исключительно от геометрии сцены, не зависит от положения источников освещения и их интенсивности и от положения камеры}.

\item \textbf{Обратимость.} 
Зная соотношение площадей патчей, можно перейти от одного Форм-Фактора к другому: $F_{ij}A_i = F_{ji}A_j$

\item \textbf{Аддитивность.} 
Зная Форм-Фактор для пары патчей i и j и Форм-Фактор для пары патчей i и k, объединив патчи j и k, можно вычислить Форм-Фактор для пары патчей i и патча, являющегося объединением патчей j и k. Это свойство будет полезно при реализации иерархической излучательности, когда группу далёких площадок можно рассматривать как 1 большую площадку.

\item \textbf{Сумма всех возможных Форм-Факторов для каждого патча сцены равна единице.} 
Вся энергия, покидающая патч, должна прийти на некоторый другой патч.

\end{itemize}


\section{Прямой расчёт излучательности}\label{radiosity_alg}

Алгоритм прямого расчёта достаточно прост. На каждой итерации для каждой площадки собирается вся входящая энергия. В конце итерации она умножается на коэфифциент отражения и превращается в исходящую энергию для следующей итерации.

\begin{lstlisting}

struct PatchRadiosity // separate radiosity params from geometry
{
  float3 emmision;
  float3 reflectance;
  float3 incident;
  float3 excident;
  float3 deposit; // this is summ of all passes
};

// std::vector<PatchRadiosity> patchesR(N_PATCHES);

// init phase
for (PatchRadiosity& p : patchesR)
{
  p.excident = p.emmision;
  p.emmision = float3(0, 0, 0);
  p.deposit += p.excident;
}

// do radiosity
for (int pass = 0; pass < a_numPasses; pass++)
{
  // each patch collects light from the scene
  for (int i = 0; i < patchesR.size(); j++)
  {
    patchesR[i].incident = float3(0, 0, 0); 
    for (int j = 0; j < patchesR.size(); j++)
      patchesR[i].incident += patchesR[j].excident*a_formFactors[i][j];
  }
  
  // deposit emitted energy for current bounce
  for (PatchRadiosity& patch : patchesR)
  {
    patch.excident = patch.incident*patch.reflectance;
    patch.deposit += patch.excident;
  }
}

\end{lstlisting}


\section{Требования} \label{conclusions}

\paragraph{Обязательная часть задания}. Необходимо сделать следующее:

\begin{enumerate}

\item Реализовать метод излучательности целиком, для простой трехмерной сцены, состоящей как минимум из \underline{1 комнаты} с 6 стенами и минимум \underline{1 прямоугольного паралеллипипеда}, находящегося внутри комнаты.

\item Визуализировать полученное освещение любым удобным способом. 

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

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

\item При изменении начальной излучательности патчей-источников, освещение должно пересчитываться. Время расчёта не должно превышать 0.5 секунды на средне-статистическом ноутбуке (в тестовой реализации для 2000 патчей расчёт освещения занимал 2 мс).

\item Время расчёта всех форм-факторов сцене не должно превышать 10 минут на средне-статческом ноутбуке. Хотя бы для одной сцены.

\item Сцена должна быть замкнута, но стены, смотрящие нормалью от наблюдателя не должны рисоваться. Иначе не получится увидеть содержимое комнаты.

\end{enumerate}

На рисунке \ref{fig:applications2} изображен пример выполненного задания.

\setlength\tabcolsep{1pt}   
\begin{figure*}[h]    
\begin{tabular}{c c}
  
  \hline  
  \includegraphics[width=0.45\linewidth]{radiosity1} & \includegraphics[width=0.45\linewidth]{radiosity2} \\

\end{tabular}
\caption{ Пример выполненного задания (на базу). }  
\label{fig:applications2}
\end{figure*}

\paragraph{Что можно делать}.

\begin{enumerate}

\item Вы можете кэшировать файл с форм-факторами на диск. Однако, программа должна предоставлять возможноть пересчитать форм-факторы заново. В readme.txt необходимо описать, как это делается.

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

\item Вы можете обмениваться файлами сцен и форм-факторов с товарищами в любом формате, если вы показываете несколько сцен (как минимум одна должна быть лично ваша!). Вы должны указать в readme.txt чьи сцены вы используете. Хотя бы на одной сцене (а именно вашей) программа должна уметь вычислять форм-факторы заного.

\item Можно писать задание на любом языке программирования.

\item Если вы находите решение через СЛАУ, допускается использование любой сторонней библиотеки решения СЛАУ.

\item Можно использовать любые существующие frame-wrok-и для визуализации и GUI.

\item Допускается использование сторонней реализации разбиения сцены на патчи в случае использования сложных сцен. К прямоугольникам и кубам это не относится.

\end{enumerate}

\paragraph{Чего нельзя делать}.

\begin{enumerate}

\item Нельзя использовать чужой исходный код в том что касается непосредственно задания за исключением оговоренного выше.

\item Нельзя использовать \underline{только чужие сцены} с уже расчитанными форм-факторами. Баллы за базу могут быть снижены в половину. Баллы за дополнительные фичи по сцене не засчитываются. 

\end{enumerate}


\paragraph{Подсказки}.


\begin{enumerate}

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

\item Если вы используете Монте-Карло интегрирование и трассировку лучей для расчёта форм-фактором (лучами), не забудьте умножить полученное значение <<частичной суммы/число\_выборок>> на площади обоих патчей перед тем как поделить результат на площадь i-ого патча.

\item Не забудьте в финале (при визуализации патчей) про гамма-коррекцию. Иначе, вторичное освещение будет выглядеть слабым.

\end{enumerate}


\section{Оценки}

\begin{enumerate}

\item База - 12 баллов.

\item Иерархическая излучательность для большой сцены (число патчей должно быть порядка 100 000, минимум 10 <<комнат>>) - 6 баллов.

\item Сцена, содержащая треугольные меши - 6 баллов. 

\item Реализация интересной сцены из квадов и кубиков (2-3 <<комнаты>> или коридор с 2-3 объектами внутри) - от 2 до 4 баллов.

\item Расчёт освещенности на GPU - 4 балла.

\item Многопоточный расчёт форм-факторов и освещенности +2 балла.

\item Рассчёт форм-факторов на GPU при помощи метода полукуба - 6 баллов.

\item Использование аналогии нуссетьта( или тот же метод полукуба) на CPU для расчета форм-факторов - 3 балла.

\item Возможность рисовать мышкой освещение на стенах - 1 балл

\item Возможность покрутить сцену - 1 балл.

\item Возможность путешествовать по комнате или коридору - 1 балл.


\end{enumerate}

Оценки:

\begin{enumerate}

\item 8 баллов - 3

\item 12 баллов - 4

\item 16 и выше баллов - 5

\end{enumerate}


\section{Применение излучательности в современном мире} \label{cool_demo}

Безусловно, изображения на рисунке \ref{fig:applications2} не выглядят очень реалистично. Отчасти это из-за отсутствия интерполяции при финальной визуализации. В действительности метод излучательности не плох при приближённом расчёте <<дальнего вторичного освещения>> может конкурировать с такими современными аналогами как LPV и Cone Tracing (рисунок \ref{fig:compos}). 

То есть на практике не нужно пытаться считать при помощи излучательности всю сцену в точности, и тем более не стоит вычислять при помощи неё первичное освещение. В движке <<Frost Byte 2>> методу излучательности подается на вход упрощенная геометрия (рисунок \ref{fig:approx}. Излучательность вычисляет только грубую апроксимацию вторичного освещения и затем полученное решение эксраполируется на детальную геометрию. Локальная детализация вторичного освещения уточняется при помощи <<Ambient Occlusion>> в пространстве экрана (SSAO), а первичное освещение вычисляетс отдельно.

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.95\linewidth]{approx}
  \caption{\label{fig:approx}
           Детальная геометрия и грубое приближение. }
\end{figure}  

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.95\linewidth]{compos}
  \caption{\label{fig:compos}
           Использование грубого приближения поверхностей в вижке <<Frost Byte 2>> и финальное изображение, где вторичное освещение наложено <<поверх>> детальных поверхностей. }
\end{figure}


При достаточно небольшом числе площадок финальный расчёт вычислительно прост даже для CPU, чего нельзя сказать о таких методах как LPV и Cone Tracing. Причём, для вторичного диффузного освещения небольшого числа площадок, как правило, достаточно (рисунок \ref{fig:compos}.

\end{document}
