1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 \chapter{Kingdom Spatial Audio}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 \section{概要}
|
|
2
|
3 本章ではリアルタイムで音響を再計算,再生するシステムとして制作したKingdom Spatial Audio(以降,KSA)の構成について説明する.
|
|
|
4 KSAでは聴覚的な影響が大きい反射と,音が壁を回り込んでくる回折現象を主に再現するシステムとなっている.
|
|
|
5 それぞれの音響効果をシミュレートするにあたって,KSAではレイキャストと経路探索を用いてシステムを構築している.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6
|
|
2
|
7 レイキャストを用いることで周囲の遮蔽物の状態を取得する事が可能となり,音の反響時間や反射による音の増幅の計算をすることが可能になる.
|
|
|
8 経路探索では音が回り込むために生成される回折経路を近似し,音が聞こえる方向を変化させる効果と音の高周波成分が減衰する現象を再現する.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9
|
|
2
|
10 また,経路探索は計算に時間を要するため,メインスレッドで処理を行うと同じくメインスレッドで動作しているUnityの動作が停止し画面が固まってしまうなどの悪影響が発生する.
|
|
|
11 そのため,経路探索はサブスレッドで処理を行う様にし,複数の経路探索が同時に行われても問題なく実行できるように構築している.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 \section{システムの流れ}
|
|
2
|
14 図\ref{fig:ksa_flow}にシステムの大まかなフローチャートを示す.
|
|
|
15 まずゲーム開始時に初期化処理としてワールドのオブジェクト情報を読み込む.次に,そのオブジェクト情報から8分木を構築する.
|
|
|
16 初期化処理の完了後は,毎フレーム実行されるゲームループでリスナーの位置を更新し,計算した回折経路を元にオーディオプレイヤーの位置を変更する.
|
|
|
17 レイキャストを用いた反響の計算を行い,必要に応じて8分木とグラフの更新を非同期で実行する.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
19 \begin{figure}[htbp]
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20 \begin{center}
|
|
2
|
21 \includegraphics[width=80mm]{./figures/flow.pdf}
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
22 \caption[KSAのフローチャート]{KSAのフローチャート}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
23 \label{fig:ksa_flow}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 \end{center}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
25 \end{figure}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
26
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27 \section{反射の再現}
|
|
2
|
28 音は障害物に衝突すると,一部は吸収され残りは反射されて空間に放出される.それが繰り返された結果,その場にいる人間には音が反響して聴こえる様になる.
|
|
|
29 これはコンピュータ上ではリバーブエフェクトとして再現される.そこで,KSAではリバーブエフェクトに渡すパラメータを計算することで音の反射を再現する.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30
|
|
2
|
31 リバーブのパラメーターには反射音の遅延時間や反響音の持続時間などを渡す必要がある.
|
|
|
32 反射音の遅延時間は音が音源から発生し壁に反射した後リスナーに届くまでの時間で計算できる.反響音の持続時間は以下に示されるSabineの式\cite{sabin}を利用して求める事が可能である.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34 \begin{math}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35 T=\frac{0.161V}{S*A}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 T:残響時間
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
39 S:空間の表面積
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
40
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41 A:吸音率
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 \end{math}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
44
|
|
2
|
45 どちらのパラメータを求めるにも音源の周囲の環境を測定する必要があり,本システムではレイキャストを用いてこれらの計算を行う.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46
|
|
2
|
47 空間分割を行わずにレイキャストなどの衝突判定を行うことは計算量が多くなってしまうため最適ではない.そこで,レイキャストを行う前に8分木を用いた空間分割を実行する.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48
|
|
2
|
49 図\ref{fig:quad_div}は4分木の分割の様子を示している.可視化のしやすさのために4分木を用いているが,基本的な考え方は8分木も同様である.
|
|
|
50 まず空間が空白ブロックと遮蔽ブロックで構成されているとする.分割レベル0では一つの空間に灰色の遮蔽ブロックと空白ブロックが混ざっている.そこでさらに分割数を増やす.分割レベル1では空間1と空間3が同じブロックのみで構成されているためこれ以上分割する必要はない.
|
|
|
51 分割レベル2では空間0と空間2の分割数をさらに増やし,一種類のブロックのみで空間が構成される様にする.
|
|
|
52 この様な分割を行うことで,空間1と3関してはその中に含まれる4つのブロックに対して個別に衝突判定を行う必要がなくなり,空間そのものと衝突判定を行えば良くなる.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
53
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
54 \begin{figure}[htbp]
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
55 \begin{center}
|
|
2
|
56 \includegraphics[width=120mm]{./figures/quad_div.pdf}
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
57 \caption[4分木の分割の様子]{4分木の分割の様子}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
58 \label{fig:quad_div}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
59 \end{center}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 \end{figure}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61
|
|
2
|
62 次に,4分木を用いたレイキャストの方法について説明する.
|
|
|
63 図\ref{raycast1}に示すように,4分木の分割の際と同じ環境を用いて,赤色の直線がオブジェクトに遮られていないかを判定する.
|
|
|
64 ここでは遮られているかどうかの判定に直線が通っている空間の中に遮蔽ブロックが存在しないことを条件として用いる.
|
|
|
65 図\ref{raycast2}では,分割レベル1の4つの空間の中から遮蔽オブジェクトが含まれている可能性のある空間0,2,3の空間と交差判定を行っている.実際に交差している空間0にはさらに分割された子空間が存在するため,その子空間に対しても交差判定を行う.
|
|
|
66 子空間0'~3'の中から遮蔽ブロックが含まれる空間1'と交差判定を行う.直線は空間1'と交差していないため直線が交差している全ての空間の中に遮蔽オブジェクトが含まれていないことが確認できる.よって直線は遮蔽オブジェクトに遮られていないと判定できる.
|
|
|
67 上記のようなレイキャストの実装を行うことで,通常は遮蔽物の数だけ行う必要があった交差判定が,空間0,2,3,1'の計4回で済むようになり高速化が見込める.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
69 \begin{figure}[htbp]
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70 \begin{minipage}{0.3\hsize}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
71 \centering
|
|
2
|
72 \includegraphics[width=40mm]{./figures/raycast_first.pdf}
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
73 \label{raycast1}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74 \caption{レイキャストの環境}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 \end{minipage}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76 \begin{minipage}{0.3\hsize}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77 \centering
|
|
2
|
78 \includegraphics[width=40mm]{./figures/raycast_second.pdf}
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
79 \caption{空間0,2,3との交差判定}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
80 \label{raycast2}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 \end{minipage}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82 \begin{minipage}{0.3\hsize}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83 \centering
|
|
2
|
84 \includegraphics[width=40mm]{./figures/raycast_third.pdf}
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85 \caption{空間1'との交差判定}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
86 \label{raycast3}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87 \end{minipage}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
88 \end{figure}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
89
|
|
2
|
90 これを3次元に拡張し8分木に適応したプログラムをKSAに実装した.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
91 \begin{figure}[htbp]
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
92 \begin{center}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
93 \includegraphics[width=70mm]{./figures/raycast.png}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
94 \caption[レイキャスト]{レイキャスト}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
95 \label{fig:raycast}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
96 \end{center}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
97 \end{figure}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
98
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
99 \section{回折の再現}
|
|
2
|
100 音は障害物の端から回り込んで伝播する性質を持っている.高周波の音ほど回折は起こりにくいため,壁を挟んで音源の反対側にいる人物には音が篭って聞こえる.また音の方向も音源自体ではなく回り込んでくる壁の端から聞こえるようになる.
|
|
|
101 本システムでは経路探索を用いて音の回折経路と回折してきた音の方向を計算する.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
102
|
|
2
|
103 回折経路を算出する際,通常のグラフ探索アルゴリズムでは計算された経路がグラフの離散化された位置に依存してしまうため,図\ref{astar_path}のようにギザギザの経路が算出されてしまい,期待する結果よりも経路長が長くなってしまう.
|
|
|
104 そこでKSAではAny-angle path planningアルゴリズムとedge-corner graphを用いた最短経路探索を行う.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
105
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
106
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
107 \subsection{Any-angle path planning}
|
|
2
|
108 Any-angle path planningアルゴリズムの一つであるTheta*\cite{ThetaStar}はA*アルゴリズムをベースに,間に障害物がないノード同士を接続することで図\ref{thetastar_path}のような直線的で自然な経路を生成している.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
109
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
110 \begin{figure}[htbp]
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
111 \begin{minipage}{0.44\hsize}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
112 \centering
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
113 \includegraphics[width=40mm]{./figures/astarpath.pdf}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
114 \label{astar_path}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
115 \caption{A*による経路生成}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
116 \end{minipage}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
117 \begin{minipage}{0.44\hsize}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
118 \centering
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
119 \includegraphics[width=40mm]{./figures/thetastarpath.pdf}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
120 \caption{Theta*による経路生成}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
121 \label{thetastar_path}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
122 \end{minipage}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
123 \end{figure}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
124
|
|
2
|
125
|
|
|
126 \section{8分木によるグラフの構築}
|
|
|
127 8分木は一つの空間に含まれる情報を少なくするために,一つの3次元空間を8つの空間に分割しこれを再帰的に繰り返して木構造を構築するアルゴリズムである.
|
|
|
128 本システムで構築した8分木は,空間に含まれるオブジェクトの種類が複数存在する場合に分割を行い,一つの空間に含まれるオブジェクトの種類が一つになるまで空間を小さくしていく方法を用いている.
|
|
|
129
|
|
|
130 構築した8分木空間の頂点にノードを生成し,遮蔽物で遮られていない隣接するノード同士を接続していきグラフを構築する.
|
|
|
131 この様なグラフをedge-corner graphと呼び,何もない場所が多いような疎な空間において生成されるノードの密度が低くなり,グラフの探索効率が上昇する.
|
|
|
132
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
133 \section{経路探索のサブスレッド化}
|
|
2
|
134 経路探索は本システムの計算処理の中でもかなり計算量が多いアルゴリズムとなっている.
|
|
|
135 グラフのサイズが128の場合,経路探索に27msかかっている.一般的なゲームが最低60fps(1フレーム16.6ms)で動作することを鑑みると,この計算時間はフレーム落ちやフレームレートの不安定化の原因になるため避けたい現象である.
|
|
|
136 そこで経路探索をサブスレッドで行うようにし,メインスレッド動作しているUnityの処理を停止させないようにする.
|
1
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
137 \begin{table}[H]
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
138 \caption{経路探索の計算時間}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
139 \label{pathfinding_time}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
140 \centering
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
141 \begin{tabular}{|r|r|r|r|}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
142 \hline
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
143 グラフの一辺のサイズ(m) & 計算時間(ms) & 経路長(m)\\
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
144 \hline
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
145 128&27.8668&341\\
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
146 \hline
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
147 64&5.7981&170\\
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
148 \hline
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
149 32&4.5226&88\\
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
150 \hline
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
151 16&1.5909&44\\
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
152 \hline
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
153 \end{tabular}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
154 \end{table}
|
Masato Tawata <e185761@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
155
|
|
2
|
156 メインスレッドで行っていた処理をサブスレッドに移行するにあたって,複数のサブスレッドから同時にアクセスされる可能性を考慮する必要がある.
|
|
|
157 複数のスレッドから同時に書き込みが発生すると,最後に書き込まれた情報以外は消失してしまうことになるためデータの整合性が取れなくなったり,プログラム上で意図しないエラーが発生する.
|
|
|
158 これを解決するために,ソースコード\ref{write_node}の45行目で行なっているグラフにスタートノードとゴールノードを書き込んでいた処理を削除し,
|
|
|
159 ソースコード\ref{unwrite_node}の42行目のように別の変数に保持しておき,探索時に適切なタイミングで前述の二つのノードを読み込む様に変更した.
|
|
|
160 \begin{lstlisting}[caption=グラフに直接ノードを書き込む場合,label=write_node]
|
|
|
161 VertexNode* ThetaStar::CreateEndNode(Utility::Vector3 endPos, VertexGraph* graph, Octree* octree)
|
|
|
162 {
|
|
|
163 VertexNode* endNode = new VertexNode();
|
|
|
164 endNode->id = -2;
|
|
|
165 endNode->nodePosition = endPos;
|
|
|
166 endNode->h = 0;
|
|
|
167
|
|
|
168 Utility::Vector3Index index = Utility::Vector3Index{ (int)floorf(endPos.x), (int)floorf(endPos.y),(int)floorf(endPos.z) };
|
|
|
169 int morton = OctreeUtility::Index2Morton(index);
|
|
|
170
|
|
|
171 int maxlevel = octree->getMaxOctreeLevel();
|
|
|
172
|
|
|
173 OctreeNode* targetNode = octree->getOctreeRoot();
|
|
|
174 for (int i = 1; i <= maxlevel; i++)
|
|
|
175 {
|
|
|
176 if (targetNode->attribute == OctreeNodeAttribute::Branch)
|
|
|
177 {
|
|
|
178 int childSpatialIndex = (morton & (7 << ((maxlevel - i) * 3))) >> ((maxlevel - i) * 3);
|
|
|
179 targetNode = &targetNode->childNodes[childSpatialIndex];
|
|
|
180 }
|
|
|
181 }
|
|
|
182 int lowestMorton = (int)pow(8, maxlevel - targetNode->nodeLevel) * targetNode->mortonNumber;
|
|
|
183 Utility::Vector3Index lowestIndex;
|
|
|
184 OctreeUtility::Morton2Index(lowestMorton, maxlevel, &lowestIndex);
|
|
|
185
|
|
|
186 int nodeScale = (int)pow(2, maxlevel - targetNode->nodeLevel);
|
|
|
187
|
|
|
188 for (int x = 0; x <= 1; x++)
|
|
|
189 {
|
|
|
190 for (int y = 0; y <= 1; y++)
|
|
|
191 {
|
|
|
192 for (int z = 0; z <= 1; z++)
|
|
|
193 {
|
|
|
194 int edgeIndex = x + (2 * y) + (4 * z);
|
|
|
195
|
|
|
196 int graphIndex_x = lowestIndex.x + (x * nodeScale);
|
|
|
197 int graphIndex_y = lowestIndex.y + (y * nodeScale);
|
|
|
198 int graphIndex_z = lowestIndex.z + (z * nodeScale);
|
|
|
199
|
|
|
200 int index = Utility::Vec3IndexToLinerIndex(graph->getGraphSize(), graphIndex_x, graphIndex_y, graphIndex_z);
|
|
|
201
|
|
|
202 graph->vertexGraph[index].neighbors.resize(7);
|
|
|
203 graph->vertexGraph[index].neightborDistance.resize(7);
|
|
|
204
|
|
|
205 graph->vertexGraph[index].neighbors[6] = endNode;
|
|
|
206 graph->vertexGraph[index].neightborDistance[6] = Utility::Distance(endPos, Utility::Vector3{ (float)graphIndex_x, (float)graphIndex_y, (float)graphIndex_z });
|
|
|
207 }
|
|
|
208 }
|
|
|
209 }
|
|
|
210
|
|
|
211 return endNode;
|
|
|
212 \end{lstlisting}
|
|
|
213
|
|
|
214 \begin{lstlisting}[caption=グラフにノードを書き込まない場合,label=unwrite_node]
|
|
|
215 VertexNode* ThetaStar::CreateEndNode(Utility::Vector3 endPos, VertexNode* graph, unordered_map<int, float>* nodeAdjacentGoal, Octree* octree)
|
|
|
216 {
|
|
|
217 VertexNode* endNode = new VertexNode();
|
|
|
218 endNode->id = -2;
|
|
|
219 endNode->nodePosition = endPos;
|
|
|
220 endNode->h = 0;
|
|
|
221
|
|
|
222 Utility::Vector3Index index = Utility::Vector3Index{ (int)floorf(endPos.x), (int)floorf(endPos.y),(int)floorf(endPos.z) };
|
|
|
223 int morton = OctreeUtility::Index2Morton(index);
|
|
|
224
|
|
|
225 int maxlevel = octree->getMaxOctreeLevel();
|
|
|
226
|
|
|
227 OctreeNode* targetNode = octree->getOctreeRoot();
|
|
|
228 for (int i = 1; i <= maxlevel; i++)
|
|
|
229 {
|
|
|
230 if (targetNode->attribute == OctreeNodeAttribute::Branch)
|
|
|
231 {
|
|
|
232 int childSpatialIndex = (morton & (7 << ((maxlevel - i) * 3))) >> ((maxlevel - i) * 3);
|
|
|
233 targetNode = &targetNode->childNodes[childSpatialIndex];
|
|
|
234 }
|
|
|
235 }
|
|
|
236 int lowestMorton = (int)pow(8, maxlevel - targetNode->nodeLevel) * targetNode->mortonNumber;
|
|
|
237 Utility::Vector3Index lowestIndex;
|
|
|
238 OctreeUtility::Morton2Index(lowestMorton, maxlevel, &lowestIndex);
|
|
|
239
|
|
|
240 int nodeScale = (int)pow(2, maxlevel - targetNode->nodeLevel);
|
|
|
241
|
|
|
242 for (int x = 0; x <= 1; x++)
|
|
|
243 {
|
|
|
244 for (int y = 0; y <= 1; y++)
|
|
|
245 {
|
|
|
246 for (int z = 0; z <= 1; z++)
|
|
|
247 {
|
|
|
248 int edgeIndex = x + (2 * y) + (4 * z);
|
|
|
249
|
|
|
250 int graphIndex_x = lowestIndex.x + (x * nodeScale);
|
|
|
251 int graphIndex_y = lowestIndex.y + (y * nodeScale);
|
|
|
252 int graphIndex_z = lowestIndex.z + (z * nodeScale);
|
|
|
253
|
|
|
254 int index = Utility::Vec3IndexToLinerIndex(vertexGraph->getGraphSize(), graphIndex_x, graphIndex_y, graphIndex_z);
|
|
|
255
|
|
|
256 nodeAdjacentGoal->insert(make_pair(graph[index].id, Utility::Distance(endPos, Utility::Vector3{ (float)graphIndex_x, (float)graphIndex_y, (float)graphIndex_z })));
|
|
|
257 }
|
|
|
258 }
|
|
|
259 }
|
|
|
260
|
|
|
261 return endNode;
|
|
|
262 }
|
|
|
263 \end{lstlisting}
|
|
|
264
|
|
|
265 \section{レイキャストの実行結果}
|
|
|
266 以下にUnityでTheta*による経路探索を行なった結果を示す.
|
|
|
267 \begin{figure}[htbp]
|
|
|
268 \centering
|
|
|
269 \includegraphics[width=80mm]{./figures/theta_unity.png}
|
|
|
270 \label{theta_path1}
|
|
|
271 \caption{Theta*による経路の生成}
|
|
|
272
|
|
|
273 \centering
|
|
|
274 \includegraphics[width=80mm]{./figures/theta2_unity.png}
|
|
|
275 \caption{複雑な経路の生成}
|
|
|
276 \label{theta_path2}
|
|
|
277 \end{figure}
|
|
|
278
|
|
|
279 図\ref{theta_path1}では音源である赤いブロックと,リスナーを表す青いブロックの間に遮蔽物が存在しており,計算された経路は遮蔽物を横から回り込むようなパスになっている.
|
|
|
280 図\ref{theta_path2}は音源とリスナーとの間に遮蔽物が2枚あるより複雑な環境を示しており,それぞれの壁で一度づつ経路が曲がって到達している事がわかる.
|
