\chapter{Kingdom Spatial Audio}
\section{概要}
本章ではリアルタイムで音響を再計算,再生するシステムとして制作したKingdom Spatial Audio(以降,KSA)の構成について説明する.
KSAでは聴覚的な影響が大きい反射と,音が壁を回り込んでくる回折現象を主に再現するシステムとなっている.
それぞれの音響効果をシミュレートするにあたって,KSAではレイキャストと経路探索を用いてシステムを構築している.

レイキャストを用いることで周囲の遮蔽物の状態を取得する事が可能となり,音の反響時間や反射による音の増幅の計算をすることが可能になる.
経路探索では音が回り込むために生成される回折経路を近似し,音が聞こえる方向を変化させる効果と音の高周波成分が減衰する現象を再現する.

また,経路探索は計算に時間を要するため,メインスレッドで処理を行うと同じくメインスレッドで動作しているUnityの動作が停止し画面が固まってしまうなどの悪影響が発生する.
そのため,経路探索はサブスレッドで処理を行う様にし,複数の経路探索が同時に行われても問題なく実行できるように構築している.

\section{システムの流れ}
図\ref{fig:ksa_flow}にシステムの大まかなフローチャートを示す.
まずゲーム開始時に初期化処理としてワールドのオブジェクト情報を読み込む.次に,そのオブジェクト情報から8分木を構築する.
初期化処理の完了後は,毎フレーム実行されるゲームループでリスナーの位置を更新し,計算した回折経路を元にオーディオプレイヤーの位置を変更する.
レイキャストを用いた反響の計算を行い,必要に応じて8分木とグラフの更新を非同期で実行する.

\begin{figure}[htbp]
  \begin{center}
   \includegraphics[width=80mm]{./figures/flow.pdf}
   \caption[KSAのフローチャート]{KSAのフローチャート}
   \label{fig:ksa_flow}
   \end{center}
\end{figure}

\section{反射の再現}
音は障害物に衝突すると,一部は吸収され残りは反射されて空間に放出される.それが繰り返された結果,その場にいる人間には音が反響して聴こえる様になる.
これはコンピュータ上ではリバーブエフェクトとして再現される.そこで,KSAではリバーブエフェクトに渡すパラメータを計算することで音の反射を再現する.

リバーブのパラメーターには反射音の遅延時間や反響音の持続時間などを渡す必要がある.
反射音の遅延時間は音が音源から発生し壁に反射した後リスナーに届くまでの時間で計算できる.反響音の持続時間は以下に示されるSabineの式\cite{sabin}を利用して求める事が可能である.

\begin{math}
T=\frac{0.161V}{S*A}

T:残響時間

S:空間の表面積

A:吸音率
\end{math}


どちらのパラメータを求めるにも音源の周囲の環境を測定する必要があり,本システムではレイキャストを用いてこれらの計算を行う.

空間分割を行わずにレイキャストなどの衝突判定を行うことは計算量が多くなってしまうため最適ではない.そこで,レイキャストを行う前に8分木を用いた空間分割を実行する.

図\ref{fig:quad_div}は4分木の分割の様子を示している.可視化のしやすさのために4分木を用いているが,基本的な考え方は8分木も同様である.
まず空間が空白ブロックと遮蔽ブロックで構成されているとする.分割レベル0では一つの空間に灰色の遮蔽ブロックと空白ブロックが混ざっている.そこでさらに分割数を増やす.分割レベル1では空間1と空間3が同じブロックのみで構成されているためこれ以上分割する必要はない.
分割レベル2では空間0と空間2の分割数をさらに増やし,一種類のブロックのみで空間が構成される様にする.
この様な分割を行うことで,空間1と3関してはその中に含まれる4つのブロックに対して個別に衝突判定を行う必要がなくなり,空間そのものと衝突判定を行えば良くなる.

\begin{figure}[htbp]
  \begin{center}
   \includegraphics[width=120mm]{./figures/quad_div.pdf}
   \caption[4分木の分割の様子]{4分木の分割の様子}
   \label{fig:quad_div}
   \end{center}
\end{figure}

次に,4分木を用いたレイキャストの方法について説明する.
図\ref{raycast1}に示すように,4分木の分割の際と同じ環境を用いて,赤色の直線がオブジェクトに遮られていないかを判定する.
ここでは遮られているかどうかの判定に直線が通っている空間の中に遮蔽ブロックが存在しないことを条件として用いる.
図\ref{raycast2}では,分割レベル1の4つの空間の中から遮蔽オブジェクトが含まれている可能性のある空間0,2,3の空間と交差判定を行っている.実際に交差している空間0にはさらに分割された子空間が存在するため,その子空間に対しても交差判定を行う.
子空間0'~3'の中から遮蔽ブロックが含まれる空間1'と交差判定を行う.直線は空間1'と交差していないため直線が交差している全ての空間の中に遮蔽オブジェクトが含まれていないことが確認できる.よって直線は遮蔽オブジェクトに遮られていないと判定できる.
上記のようなレイキャストの実装を行うことで,通常は遮蔽物の数だけ行う必要があった交差判定が,空間0,2,3,1'の計4回で済むようになり高速化が見込める.

\begin{figure}[htbp]
  \begin{minipage}{0.3\hsize}
  \centering
  \includegraphics[width=40mm]{./figures/raycast_first.pdf}
  \label{raycast1}
  \caption{レイキャストの環境}
\end{minipage}
\begin{minipage}{0.3\hsize}
  \centering
  \includegraphics[width=40mm]{./figures/raycast_second.pdf}
  \caption{空間0,2,3との交差判定}
  \label{raycast2}
\end{minipage}
\begin{minipage}{0.3\hsize}
  \centering
  \includegraphics[width=40mm]{./figures/raycast_third.pdf}
  \caption{空間1'との交差判定}
  \label{raycast3}
\end{minipage}
\end{figure}

これを3次元に拡張し8分木に適応したプログラムをKSAに実装した.
\begin{figure}[htbp]
  \begin{center}
   \includegraphics[width=70mm]{./figures/raycast.png}
   \caption[レイキャスト]{レイキャスト}
   \label{fig:raycast}
   \end{center}
\end{figure}

\section{回折の再現}
音は障害物の端から回り込んで伝播する性質を持っている.高周波の音ほど回折は起こりにくいため,壁を挟んで音源の反対側にいる人物には音が篭って聞こえる.また音の方向も音源自体ではなく回り込んでくる壁の端から聞こえるようになる.
本システムでは経路探索を用いて音の回折経路と回折してきた音の方向を計算する.

回折経路を算出する際,通常のグラフ探索アルゴリズムでは計算された経路がグラフの離散化された位置に依存してしまうため,図\ref{astar_path}のようにギザギザの経路が算出されてしまい,期待する結果よりも経路長が長くなってしまう.
そこでKSAではAny-angle path planningアルゴリズムとedge-corner graphを用いた最短経路探索を行う.


\subsection{Any-angle path planning}
Any-angle path planningアルゴリズムの一つであるTheta*\cite{ThetaStar}はA*アルゴリズムをベースに,間に障害物がないノード同士を接続することで図\ref{thetastar_path}のような直線的で自然な経路を生成している.

\begin{figure}[htbp]
  \begin{minipage}{0.44\hsize}
  \centering
  \includegraphics[width=40mm]{./figures/astarpath.pdf}
  \label{astar_path}
  \caption{A*による経路生成}
\end{minipage}
\begin{minipage}{0.44\hsize}
  \centering
  \includegraphics[width=40mm]{./figures/thetastarpath.pdf}
  \caption{Theta*による経路生成}
  \label{thetastar_path}
\end{minipage}
\end{figure}


\section{8分木によるグラフの構築}
8分木は一つの空間に含まれる情報を少なくするために,一つの3次元空間を8つの空間に分割しこれを再帰的に繰り返して木構造を構築するアルゴリズムである.
本システムで構築した8分木は,空間に含まれるオブジェクトの種類が複数存在する場合に分割を行い,一つの空間に含まれるオブジェクトの種類が一つになるまで空間を小さくしていく方法を用いている.

構築した8分木空間の頂点にノードを生成し,遮蔽物で遮られていない隣接するノード同士を接続していきグラフを構築する.
この様なグラフをedge-corner graphと呼び,何もない場所が多いような疎な空間において生成されるノードの密度が低くなり,グラフの探索効率が上昇する.

\section{経路探索のサブスレッド化}
経路探索は本システムの計算処理の中でもかなり計算量が多いアルゴリズムとなっている.
グラフのサイズが128の場合,経路探索に27msかかっている.一般的なゲームが最低60fps(1フレーム16.6ms)で動作することを鑑みると,この計算時間はフレーム落ちやフレームレートの不安定化の原因になるため避けたい現象である.
そこで経路探索をサブスレッドで行うようにし,メインスレッド動作しているUnityの処理を停止させないようにする.
\begin{table}[H]
\caption{経路探索の計算時間}
\label{pathfinding_time}
\centering
\begin{tabular}{|r|r|r|r|}
  \hline
  グラフの一辺のサイズ(m) & 計算時間(ms) &　経路長(m)\\
  \hline
  128&27.8668&341\\
  \hline
  64&5.7981&170\\
  \hline
  32&4.5226&88\\
  \hline
  16&1.5909&44\\
  \hline
\end{tabular}
\end{table}

メインスレッドで行っていた処理をサブスレッドに移行するにあたって,複数のサブスレッドから同時にアクセスされる可能性を考慮する必要がある.
複数のスレッドから同時に書き込みが発生すると,最後に書き込まれた情報以外は消失してしまうことになるためデータの整合性が取れなくなったり,プログラム上で意図しないエラーが発生する.
これを解決するために,ソースコード\ref{write_node}の45行目で行なっているグラフにスタートノードとゴールノードを書き込んでいた処理を削除し,
ソースコード\ref{unwrite_node}の42行目のように別の変数に保持しておき,探索時に適切なタイミングで前述の二つのノードを読み込む様に変更した.
\begin{lstlisting}[caption=グラフに直接ノードを書き込む場合,label=write_node]
VertexNode* ThetaStar::CreateEndNode(Utility::Vector3 endPos, VertexGraph* graph, Octree* octree)
{
    VertexNode* endNode = new VertexNode();
    endNode->id = -2;
    endNode->nodePosition = endPos;
    endNode->h = 0;

    Utility::Vector3Index index = Utility::Vector3Index{ (int)floorf(endPos.x), (int)floorf(endPos.y),(int)floorf(endPos.z) };
    int morton = OctreeUtility::Index2Morton(index);

    int maxlevel = octree->getMaxOctreeLevel();

    OctreeNode* targetNode = octree->getOctreeRoot();
    for (int i = 1; i <= maxlevel; i++)
    {
        if (targetNode->attribute == OctreeNodeAttribute::Branch)
        {
            int childSpatialIndex = (morton & (7 << ((maxlevel - i) * 3))) >> ((maxlevel - i) * 3);
            targetNode = &targetNode->childNodes[childSpatialIndex];
        }
    }
    int lowestMorton = (int)pow(8, maxlevel - targetNode->nodeLevel) * targetNode->mortonNumber;
    Utility::Vector3Index lowestIndex;
    OctreeUtility::Morton2Index(lowestMorton, maxlevel, &lowestIndex);

    int nodeScale = (int)pow(2, maxlevel - targetNode->nodeLevel);

    for (int x = 0; x <= 1; x++)
    {
        for (int y = 0; y <= 1; y++)
        {
            for (int z = 0; z <= 1; z++)
            {
                int edgeIndex = x + (2 * y) + (4 * z);

                int graphIndex_x = lowestIndex.x + (x * nodeScale);
                int graphIndex_y = lowestIndex.y + (y * nodeScale);
                int graphIndex_z = lowestIndex.z + (z * nodeScale);

                int index = Utility::Vec3IndexToLinerIndex(graph->getGraphSize(), graphIndex_x, graphIndex_y, graphIndex_z);

                graph->vertexGraph[index].neighbors.resize(7);
                graph->vertexGraph[index].neightborDistance.resize(7);

                graph->vertexGraph[index].neighbors[6] = endNode;
                graph->vertexGraph[index].neightborDistance[6] = Utility::Distance(endPos, Utility::Vector3{ (float)graphIndex_x, (float)graphIndex_y, (float)graphIndex_z });
            }
        }
    }

    return endNode;
\end{lstlisting}

\begin{lstlisting}[caption=グラフにノードを書き込まない場合,label=unwrite_node]
VertexNode* ThetaStar::CreateEndNode(Utility::Vector3 endPos, VertexNode* graph, unordered_map<int, float>* nodeAdjacentGoal, Octree* octree)
{
    VertexNode* endNode = new VertexNode();
    endNode->id = -2;
    endNode->nodePosition = endPos;
    endNode->h = 0;

    Utility::Vector3Index index = Utility::Vector3Index{ (int)floorf(endPos.x), (int)floorf(endPos.y),(int)floorf(endPos.z) };
    int morton = OctreeUtility::Index2Morton(index);

    int maxlevel = octree->getMaxOctreeLevel();

    OctreeNode* targetNode = octree->getOctreeRoot();
    for (int i = 1; i <= maxlevel; i++)
    {
        if (targetNode->attribute == OctreeNodeAttribute::Branch)
        {
            int childSpatialIndex = (morton & (7 << ((maxlevel - i) * 3))) >> ((maxlevel - i) * 3);
            targetNode = &targetNode->childNodes[childSpatialIndex];
        }
    }
    int lowestMorton = (int)pow(8, maxlevel - targetNode->nodeLevel) * targetNode->mortonNumber;
    Utility::Vector3Index lowestIndex;
    OctreeUtility::Morton2Index(lowestMorton, maxlevel, &lowestIndex);

    int nodeScale = (int)pow(2, maxlevel - targetNode->nodeLevel);

    for (int x = 0; x <= 1; x++)
    {
        for (int y = 0; y <= 1; y++)
        {
            for (int z = 0; z <= 1; z++)
            {
                int edgeIndex = x + (2 * y) + (4 * z);

                int graphIndex_x = lowestIndex.x + (x * nodeScale);
                int graphIndex_y = lowestIndex.y + (y * nodeScale);
                int graphIndex_z = lowestIndex.z + (z * nodeScale);

                int index = Utility::Vec3IndexToLinerIndex(vertexGraph->getGraphSize(), graphIndex_x, graphIndex_y, graphIndex_z);

                nodeAdjacentGoal->insert(make_pair(graph[index].id, Utility::Distance(endPos, Utility::Vector3{ (float)graphIndex_x, (float)graphIndex_y, (float)graphIndex_z })));
            }
        }
    }

    return endNode;
}
\end{lstlisting}

\section{レイキャストの実行結果}
以下にUnityでTheta*による経路探索を行なった結果を示す.
\begin{figure}[htbp]
  \centering
  \includegraphics[width=80mm]{./figures/theta_unity.png}
  \label{theta_path1}
  \caption{Theta*による経路の生成}

  \centering
  \includegraphics[width=80mm]{./figures/theta2_unity.png}
  \caption{複雑な経路の生成}
  \label{theta_path2}
\end{figure}

図\ref{theta_path1}では音源である赤いブロックと,リスナーを表す青いブロックの間に遮蔽物が存在しており,計算された経路は遮蔽物を横から回り込むようなパスになっている.
図\ref{theta_path2}は音源とリスナーとの間に遮蔽物が2枚あるより複雑な環境を示しており,それぞれの壁で一度づつ経路が曲がって到達している事がわかる.