\documentclass[a4paper, 11pt, notitlepage]{article}

\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english,russian]{babel}
\usepackage[dvips]{graphicx}
\usepackage[top=20mm,bottom=20mm]{geometry}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{listings}
\usepackage{color}
\usepackage{caption}
\hypersetup{
    pdftitle={Лабораторная работа по схемотехнике},
    pdfauthor={Широков Олег},
    bookmarksopenlevel=1,
    bookmarksopen=true,
    bookmarksnumbered=true
}

\fancyhf{}

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.4,0.4,0.4}

\lstdefinestyle{MyCPP}{
    language=C++,
    basicstyle=\small,
    captionpos=b,
    backgroundcolor=\color{white},
    keywordstyle=\color{mygreen},
    identifierstyle=\color{blue},
    stringstyle=\color{red},
    breaklines=true
}

\graphicspath{{./images/eps/}}
\pagestyle{fancy}
\rfoot{\thepage}

\setcounter{tocdepth}{3}

\begin{document}
\tableofcontents
\newpage

\section{Введение}
\subsection{Цели}
Знакомство с физическими движками и написание приложения, демонстрирующего взаимодействие твердых тел.
\subsection{Использованные технологии}
В процессе разработки приложения были использованы следующие технологии: программный интерфейс OpenGL\cite{OpenGL} и физический движок Bullet\cite{Bullet}. Разработка велась на языке C++. Выбор OpenGL обусловлен плаформо-независимостью и наличием обширной документации. В качестве аналогов можно привести  DirectX API\cite{Bullet}, но его использование не позволяет написать платформо-независимый код. 

При выборе физического движка рассматривались следующие критерии:
\begin{itemize}
    \item Открытость 
    \item Наличие документации
    \item Доступность для различных платформ
\end{itemize}

В качестве альтернатив рассматривались Newton\cite{Newton} и Tokamak\cite{Tokamak}. Newton был отброшен из-за отсутствия документации, а Tokamak из-за отсутствия поддержки платформы разработки (Mac OS X). 
Кроме того Bullet поддерживает SIMD расширения, многопоточность, и кроме симуляции поведения твердых тел (rigid bodies) позволяет также симулировать поведение деформируемых тел (soft bodies).


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


    В OpenGL зачастую используются следующие:
\begin{itemize}
 \item Модельная матрица (Model Matrix) эта матрица, используемая для задания положения объекта в пространстве. 
 \item Проекционная матрица (Projection Matrix) матрица, которая используется для задания параметров проекции
 \item Видовая матрица (View Matrix) матрица, определяющая положение и направление камеры.
\end{itemize}
 Результатом перемножения всех этих матриц на вектор координаты точки станет вектор определяющий положение точки на экране.

 \subsection{Физические движки}
 Физическим движком называют специализированное ПО предназначенное для моделирования физических процессов таких как: симуляция столкновения твердых тел(rigid bodies), симуляция поведения деформируемых тел (soft bodies), динамика жидкостей, газов.

 \subsection{Симуляция столкновения твердых тел\\ (Rigid body simulation)}
 Под твердым телом понимается такое тело, в котором дистанция между любыми двумя точками всегда остается прежней, другими словами, деформация такого тела невозможна. Твердое тело описывается множеством параметров, включая: положение центра масс, импульс, угловой момент, масса, кинетическая энергия, и т.п.  

 Симуляция столкновения делится на две составляющие: Обнаружение столкновений (Collision Detection) и Реакция на столкновение (Collision Reaction). Первая стадия будет подробнее описана ниже.  Во время второй стадии вычисляются новые параметры тел в соответствии с физическими законами. 

 \subsection{Обнаружение столкновений}

 \begin{figure}[h]
     \begin{center}
         \includegraphics[width=0.8\linewidth]{BS_and_AABB}
         \caption{Ограничивающий цилиндр (AABB) и ограничивающая сфера (BS)}
         \label{AABB_BS}
    \end{center}
\end{figure}

 Под обнаружением столкновений обычно понимают задачу о нахождении пересечения физических объектов во время физической симуляции. Это одна из самых сложных и затратных частей симуляции. Зачастую обнаружение столкновений разбивается на две фазы:
 \begin{itemize}
     \item Широкая фаза (Broad phase) определяет объекты, которые потенциально могут пересекаться, для уменьшения количества обрабатываемых объектов в узкой фазе. Для определения потенциально пересекающихся объектов объекты «ограничиваются» более простыми геометрическими фигурами (Bounding volume) как, например, AABB(Axis-Aligned Bounding Box) или BS (Bounding Sphere), пример на рис. ~\ref{AABB_BS} \\
        Часто используют один из следующих алгоритмов:
        \begin{itemize}
            \item Метод грубой силы(Brute force) проверка пересечения ограничивающих фигур для каждого объекта с каждым другим. Сложность этого алгоритма получается равной
            \item Spatial Hashing. В этом алгоритме все пространство разбивается на ячейки содержащие объекты и на столкновение проверяются только объекты из соседних ячеек. 
            \item Spatial Hashing. В этом алгоритме все пространство разбивается на ячейки содержащие объекты и на столкновение проверяются только объекты из соседних ячеек. Sort And Sweep. Суть этого объекта состоит в сортировке координат ограничивающих элементов вдоль какой-либо оси, и объекты помечаются для обработки в следующей фазе, если их координаты пересекаются. 
        \end{itemize}

    \item Узкая фаза (Narrow phase) стадия в которой определяются столкновения объектов, найденных в предыдущей Широкой фазе, в данной фазе используются такие алгоритмы как V-Clip и GJK-EPA\cite{GJK}

        \section{Реализация}
        \subsection{Структура программы}
        Программа симуляции написана с использованием прадигмы ООП. Программа содержит следующие классы:
        \begin{itemize}
            \item Box — класс, который описывает поведение и состояние объектов симуляции
            \item Camera — класс, хранит состояние камеры
            \item Scene — класс, содержащий информацию о объектах участвующих в симуляции
        \end{itemize}

        И файлы:
        \begin{itemize}
            \item inputUtils.cpp — в нем определены функции ввода с клавиатуры и мыши
            \item MyShadersCompile.cpp — в этом файле определяются функции для компиляции шейдеров (OpenGL )Shaders)\cite{GLSL}
        \end{itemize}

        \subsection{Использование OpenGL и Bullet}
        Для хранения ссылок на буферы и уменьшения количества обращений к API используются VAO (Vertex Array Object). Инициализация буферов и VAO происходит в конструкторе класса Box. 
        Создание OpenGL контекста и обработка ввода осуществляется с помощью библиотеки  GLFW\cite{GLFW}\\

        Также в конструкторе класса Box создаются объекты типа btRigidBody, используемые физическим движком для расчетов, и их добавление в симуляцию.\\ 

        После расчета следующего шага симуляции, можно получить из объекта btRigidBody соответствующую его положению матрицу преобразований, и передать ее во вершинный шейдер (Vertex Shader) (Листинг ~\ref{ModelToShader})

        Видовая и проекционная матрицы хранятся и вычисляются в классе Camera.

        \begin{lstlisting}[style=MyCPP,caption={Передача Model Matrix в вершинный шейдер.}, label=ModelToShader]
        void Box::draw()
        {
            GLint uniform_location; 

            setModel();

            glUseProgram(program);

            uniform_location = glGetUniformLocation(program, "ModelMatrix");

            if(uniform_location == -1)
            {
                fprintf(stderr, "Could not bind to uniform\n");
                return;
            }

            glUniformMatrix4fv(uniform_location, 1, GL_FALSE, glm::value_ptr(Model));

            glBindVertexArray(vao);
            glDrawElements(GL_TRIANGLES, NumOfPrimitives, GL_UNSIGNED_INT, 0);
            glBindVertexArray(0);
        }

        void Box::setModel()
        {
            btTransform trans;
            btScalar    m[16];
            body -> getMotionState() -> getWorldTransform(trans); 

            trans.getOpenGLMatrix(m);

            Model = glm::make_mat4((float *)m);
        }
        \end{lstlisting}
\end{itemize}


\section{Результат}
В результате была разработана программа симулирующая поведение твердых тел управление камерой осуществляется с помощью мыши и кнопок 'w','a','s','d'. Кнопка 'f' запускает симуляцию, а кнопка 'r' переводит все объекты в начальное состояние. На  рисунке ~\ref{resultImage}  приведены снимки экрана во время работы программы.
\begin{figure}[h]
    \begin{minipage}[h]{0.59\linewidth}
        \center{ \includegraphics[width=0.6\linewidth]{Simulation2nd} \\ a) }
    \end{minipage}
    \begin{minipage}[h]{0.59\linewidth}
        \center{ \includegraphics[width=0.6\linewidth]{Simulation} \\ b) }
    \end{minipage}
    \caption{Снимки экрана во время работы программы}
    \label{resultImage}
\end{figure}

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

\newpage
\begin{thebibliography}{9}
        \bibitem{OpenGL}
        The OpenGL Graphics System: A Specification (Version 4.1(Core Profile)) - 2010 - c.518

        \bibitem{Bullet}
        Real-Time Physics Simulation http://bulletphysics.org/wordpress/

        \bibitem{DirectX}
        Microsoft Windows http://windows.microsoft.com/ru-ru/windows7/products/features/directx-11
        
        \bibitem{Newton}
        Newton Game Dynamics http://newtondynamics.com/forum/newton.php

        \bibitem{Tokamak}
        Tokamak Open Source Physics Engine http://www.tokamakphysics.com/

        \bibitem{GJK}
        Davor Jovanoski, The Gilbert-Johnson-Keerthi(GJK) Algorithm, 2008

        \bibitem{GLSL}
        John Kessenich, Dave Baldwin,  Randi Rost The OpenGL Shading Language - 2010 - c.161

        \bibitem{GLFW}
        GLFW - An OpenGL library http://www.glfw.org/
\end{thebibliography}
\end{document}
