\chapter{基礎概念}
\section{OpenALについて}
OpenALとはクロスプラットフォームに対応し,ゲームやその他の多くのオーディオアプリケーションで利用できる3DオーディオAPIである.いくつかの実装が存在し,現在はOpenAL-Softが主流な実装となっている.
3次元空間上での音の表現に適しており,簡素な記述で立体的な音場を表現する事ができる.

OpenALの構造は以下の様になっている.
\begin{figure}[htbp]
  \begin{center}
   \includegraphics[width=70mm]{./figures/openal.pdf}
   \caption[OpenAL_Context]{OpenALの基本構造}
   \label{fig:opeal}
   \end{center}
\end{figure}

Deviceの下にコンテキストと,音源の実際の信号などを保持しているBufferが存在する.Contextは複数存在し,それぞれのContextに音を受け取る役割を持つListenerが1つある.
SourceはContext内に複数個設ける事ができ,Bufferからの情報を読み取り実際に音声を再生する役割を持つ.

\section{Unityについて}
UnityはUnity Tecnologiesが開発しているクロスプラットフォームに対応したゲームエンジンである.
C\#でのプログラミングが可能で,レンダリングの機能も充実しているためゲーム制作以外でも,研究用途やコンピュータグラフィックスの分野でも用いられる.
本研究ではC++を用いてOpenALによる3次元音響のシステムを構築するためC++によるコードをUnity上で利用できる様にする必要がある.
UnityにはUnity native pluginという機能があり,CやC++その他の言語で書かれたプログラムに対してCのインターフェースを介してアクセスする事ができる.

\section{レイキャストについて}
\label{section_raycast}
コンピューターにおいて,ある地点から特定の方向に障害物が存在するかを判定する際にレイキャストが用いられる.
走査したい方向に仮想的な光線を飛ばし,その光線と物体を構成するポリゴンと呼ばれる3角形が交差しているか否かで障害物の有無を判定する方法が代表的である.
この様な実装を工夫をせずに行うと全てのポリゴンに対して光線との交差判定をする必要があるため無駄な処理が多い.そのため通常は後述する空間分割などを用いて判定するポリゴンを減らす工夫がなされる.

\section{Any-angle path planning}
ゲーム上のある地点からある地点までの最短距離を求めたい場合,ダイクストラ法\cite{Dijkstra}を用いた経路探索アルゴリズムが用いられる.
ダイクストラ法ではノードとそれらを繋ぐエッジで構成されたグラフ構造を基に最短経路を求める.
3次元空間上ではノードが空間上の位置を表し,エッジはその空間同士が接続されているか(ノード間に障害物がない)を表現している.
ゲームではダイクストラ法の中でもA*アルゴリズムがよく利用されているが,欠点も存在する.
それは,A*は探索を始めるノードから隣接するノードを辿っていくことで経路を計算するため,ノード間の角度がグラフの構造に依存してしまうのである.例えばグラフ上のそれぞれのノードが隣接する上下左右の4方向のノードのみと接続されている場合,計算された経路は90度間隔でしか他のノードと接続できない.
これを解決するアルゴリズムがAny-angle path planningである.
Any-angle path planningはパスがグラフの構造に制限される事なく,任意の角度でノード同士を接続することができるアルゴリズムである.Any-angeでない経路探索アルゴリズムと比較してより適切なパスを計算できる.

\section{Theta*アルゴリズム}
Any-angle path planningの一つであるTheta*は親ノードを設定する際に,隣接しているノードの親ノードとの間に障害物があるかどうかを探索し障害物がなければ親ノードにその親ノードを設定する.

以下にTheta*の疑似コード\cite{ThetaStar}を示す.
Theta*で特徴的なのが,アルゴリズム\ref{alg1}の19行目の引数のノード間の障害物の有無を返すLineOfSight関数である.
自分の親ノードと隣接ノードのLineOfSightを判定し,障害物がない場合隣接ノードに自分の親ノードを直接設定する.そのため,Goalノードから親ノードを順にたどってパスを生成する際に余分なノードを経路に含めずに計算する事ができる.




\begin{algorithm}[H]
    \caption{Theta*}
    \label{alg1}
    \begin{algorithmic}[1]
    \Function{Main}{void}
      \State $g(start) := 0$
      \State $parent(start) := start$
      \State $open:= \emptyset$
      \State $closed:= \emptyset$
      \State $open.Insert(start, 0)$
      \While{$open \neq \emptyset$}
        \State $n=open.Pop()$
          \If{$n = n_{goal}$}
          \State \Return "Find path"
          \EndIf
        \State $close := close \cup n$
        \ForAll{$n' \in neighbors(n)$}
          \If{$n'\notin close$}
            \If{$n' \notin open$}
              \State $g(n')=\infty$
              \State $parent(n')=NULL$
            \EndIf
            \State UpdateVertex$(n,n')$
          \EndIf
        \EndFor
      \EndWhile
    \EndFunction
    \Function{UpdateVertex}{$n,n'$}
      \If{LineOfSight$(parent(n),n')$}
        \If{$g(n)+c(n,n')<g(s')$}
          \State $g(parent(n)):=g(n)+c(parebt(n),n')$
          \State $parent(n'):=parent(n)$
          \If{$n' \in open$}
            \State open.Remove(n')
          \EndIf
          \State open.Insert(n',g(n')+h(n'))
        \EndIf
      \Else
        \If{$g(n)+c(n,n')<g(n')$}
          \State $g(n'):=g(n)+c(n,n')$
          \State $parent(n'):=n$
          \If{$n' \in open$}
            \State $open.Remove(n')$
          \EndIf
          \State $open.Insert(n',g(n')+h(s'))$
        \EndIf
      \EndIf
    \EndFunction
    \end{algorithmic}
\end{algorithm}

\section{空間分割}
\label{spatialdiv}
\ref{section_raycast}の最後で述べたように空間を離散化せずにレイキャストなどの衝突判定を行うことは計算量の観点から見て非効率なため,同時に空間分割を用いた最適化がなされる場合が多い.
空間分割の方法には４分木やkd木,BSP木など分割の仕方が異なる方法が多数存在するが,基本的には空間を分割しそれぞれの空間に属するオブジェクトを登録し,分割した空間をさらに分割して子空間を生成,子空間に属するオブジェクトをその子空間に登録,という操作を繰り返してオブジェクトが所属する空間を小さくしていくというのが主な目的である.

以下に4分木での具体例を示す.
\begin{figure}[htbp]
  \begin{minipage}[b]{0.45\linewidth}
  \centering
  \includegraphics[width=40mm]{./figures/noSpatialPartitioning.pdf}
  \label{nsp}
  \caption{空間分割なし}
\end{minipage}
\begin{minipage}[b]{0.45\linewidth}
  \centering
  \includegraphics[width=40mm]{./figures/SpatialPartitioning.pdf}
  \caption{空間分割あり}
  \label{sp}
\end{minipage}
\end{figure}

図\ref{nsp}では,赤色のオブジェクトが他の物体と衝突しているかを判定するためには,青色のオブジェクト全てに対して計算を行わななければならないが,
図\ref{sp}では4分木アルゴリズムを使用し空間が4つに分割されており,他の空間に属している緑色のオブジェクトに関しては衝突していないことが保証されるため,同じ空間に属する青色のオブジェクト1つに対してのみ計算することで衝突する可能性のあるオブジェクトの判定を行う事ができる.
分割は任意の数だけ行う事ができ,分割した空間の一つをさらに4つに分解して粒度を細かくする事が可能である.オブジェクトの数が多い際は分割数を増やすことで衝突判定の計算量を減らせるが,メモリの使用量が増加するため空間の特性に応じた適切な分割数を用いる必要がある.

\section{8分木}
8分木は4分木を3次元空間上で利用できるようにしたアルゴリズムである.
一つの空間を8つの立方体に分割することを繰り返していくことで,それぞれのオブジェクトの所属空間を決定する.
\begin{figure}[htbp]
  \begin{minipage}{0.3\hsize}
  \centering
  \includegraphics[width=40mm]{./figures/octree_Level0.pdf}
  \label{octree0}
  \caption{分割数0}
\end{minipage}
\begin{minipage}{0.3\hsize}
  \centering
  \includegraphics[width=40mm]{./figures/octree_Level1.pdf}
  \caption{分割数1}
  \label{octree1}
\end{minipage}
\begin{minipage}{0.3\hsize}
  \centering
  \includegraphics[width=40mm]{./figures/octree_Level2.pdf}
  \caption{分割数2}
  \label{octree2}
\end{minipage}
\end{figure}