\documentclass[twocolumn,twoside,9.5pt]{jarticle}
% \usepackage[dvips]{graphicx}
\usepackage[dvipdfm]{graphicx}
\usepackage{fancyhdr,picins}
\usepackage{comment}
\pagestyle{fancy}
\lhead{\parpic{
\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.pdf}}
琉球大学主催 工学部情報工学科 卒業研究発表会}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\begin{document}
\title{マルチコア CPU における\\ SceneGraph を用いたゲームの作成}
\author{065746J 仲宗根広樹　指導教員 : 河野真治}
\date{\today}
\maketitle
\thispagestyle{fancy}

\section{概要}
近年のゲームマシンは高度な並列性を持つようになっており、
ゲームプログラムでの様々なレベルでの並列処理が必須となっている。
プログラムの一部を並列処理するのではなく、定常的な並列度を提供する
必要がある。しかし、
データが処理される順番を把握することができないので出力結果などが特定しづらく、
逐次型に比べて難易度が高い
データ転送やタスクの生成、管理等の技術が多く存在する。\\
　現在、学生実験にて PlayStation 3(PS3) で動作するゲーム開発を行っている。
短期間の学生実験では新しい技術を習得することに時間を割かれ、ゲームの完成度を上げることが難しくなる。\\
　そこで本研究では、
SceneGraph と言うゲーム中の１つの場面(Scene) を構成するオブジェクトやその振る舞い、ゲームのルールの集合を導入する。
SceneGraph の処理を並列に行なうことにより、完成度の高いゲームの作成を可能とする。

\section{SceneGraph を使ったゲーム作成}
SceneGraph のノードは親子関係を持つ tree で構成される(図\ref{fig:SceneGraph})。

SceneGraph を使用すると、ゲーム内のオブジェクトは個別に SceneGraph ノードに分けられているので、ノードを別個に処理すると自然と並列度がでてくる。

SceneGraph ノード は以下のようなデータと動作を持つ。
\\\\
{\small
\begin{tabular}{|l|l|}
  \hline
  データ & 説明 \\ \hline
  Vertex & ポリゴンオブジェクトの頂点座標 \\ \hline
  Texture & ポリゴンオブジェクトのテクスチャ座標　\\ \hline
  TextureImage & テクスチャイメージ \\ \hline
  TransMatrix & ポリゴンオブジェクトの変換行列 \\ \hline
  Coordinates & オブジェクトの座標 \\ \hline
  Angle & オブジェクトの角度 \\\hline
  Property & オブジェクトの内部状態 \\
  \hline
\end{tabular}
\\\\\\
\begin{tabular}{|l|l|}
  \hline
  動作 & 説明 \\ \hline
  Move & 自律的なオブジェクトの動く \\ \hline
  Collision & 他のノードとの衝突判定をする \\ \hline
\end{tabular}
}
\\\\
\begin{comment}
\begin{itemize}
  \item データ
    \begin{enumerate}
      \item Vertex ：ポリゴンオブジェクトの頂点座標
      \item Texture：ポリゴンオブジェクトのテクスチャ座標
      \item TextureImage：テクスチャイメージ
      \item TransMatrix ：ポリゴンオブジェクトの変換行列
      \item Coordinates ：オブジェクトの座標
      \item Angle：オブジェクトの角度
      \item Property：オブジェクトのゲームに係わる内部状態
    \end{enumerate}
  \item 動作
    \begin{enumerate}
      \item Move：自律的なオブジェクトの動き
      \item Collision：他のノードとの衝突判定をする
    \end{enumerate}
\end{itemize}
\end{comment}

SceneGraph の親子関係に沿って TransMatrix を計算し、Move, Collision を実行することで SceneGraph 内のオブジェクトが変化する。Collision によって Move が変更され、Move によって Coordinates や Angle が変更される。これらをどのように変更させるかがゲームのルールになる。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.4]{image/SceneGraph.pdf}
    \caption{tree 構造の SceneGraph}
    \label{fig:SceneGraph}
  \end{center}
\end{figure}


\section{Cell Broadband Engine} \label{sec:cell}
Cell\cite{cell} は１基の PowerPC Processor Element (PPE) と８基の Synergistic Processor Element (SPE) で構成されるヘテロジニアスマルチコアプロセッサである。各プロセッサは高速バスで接続されている。本研究では６基の SPE が使用可能となっている。

\section{Cerium}
Cerium とは当研究室で開発した Cell 上で動作するゲームフレームワークである。
Cerium は SceneGraph、OSMesa に代表される Rendering Engine、そしてそれらの実行単位を Task とし、動的に全てのコアが動作する様な割り振りを行うカーネル TaskManager で構成されている。

現在、Cerium では SceneGraph の Move, Collision を PPE でシーケンシャルに処理しているので、この部分の処理を SPE を用いて並列に処理するように変更する。

\section{SceneGraph の並列処理}
\subsection{Property}
オブジェクトの動作(move, collision) に必要になるのは Coordinates や Angle であり、Polygon や Texture のデータは不要になる。そこで、ゲームに必要なオブジェクトの内部状態を持った配列 Property を用いる。Property には Coordinates, Angle の他に、tree を再生成する時に必要な親子関係、オブジェクト生成消滅のパラメータなどが含まれる。\\
　Move, Collsion の処理をする際は Property を SPE に送り、変更されて返された Updated Property を元に PPE 側で SceneGraphTree を構成する。 (図\ref{fig:sgtask})\\
\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.7]{image/SceneGraphTask.pdf}
    \caption{SceneGraphTree の生成}
    \label{fig:sgtask}
  \end{center}
\end{figure}
\subsection{chain}
SceneGraph の処理の例題として、学生実験で作成された鎖のシミュレーション chain を使用する。
この例題では、動作は Move の処理のみ行い、処理に使用する SPE は1基となっている。
\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.3]{image/chain.png}
    \caption{chain の画面}
    \label{fig:chain}
  \end{center}
\end{figure}

[Move] chain のオブジェクトの値は一つ前のオブジェクトの値から算出されるので、複数 SPE に分割して並列処理することができない。
\\
　Move の処理を SPE で行った場合と PPE で行った場合の FPS の比較を以下に示す。
\begin{center}
\begin{tabular}{|l|l|}
  \hline
  　 & FPS(Frame Per Scecond) \\ \hline
  PPE & 2.708696 \\ \hline
  SPE & 2.893348 \\
  \hline
\end{tabular}
\end{center}
PPE より、 SPE で処理した方の FPS が若干向上した。
\if 0
\subsection{vacuum}
SceneGraph の処理の例題として、学生実験で作成されたゲーム vacuum を使用する。
vacuum には自機と吸収ブロック、敵ブロックの３種類のオブジェクトがあり、自機を上下左右に移動させ、ボタンを押している間は自機の周りのブロックを引き寄せ、うまく吸収ブロックだけを自機と衝突させるゲームである。このゲームのMoveとCollisionは以下のようになる。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.7]{image/vacuum.png}
    \caption{vacuum のゲーム画面}
    \label{fig:vacuum}
  \end{center}
\end{figure}

[Move] vacuum のオブジェクトは全て独立して動くので、使用する SPE に均等に Property を割り振る。
SPE でオブジェクトの種類毎の Move 処理を行い、Property を更新して PPE に返す。

\if0
\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.43]{image/Move.pdf}
    \caption{vacuum の Move}
    \label{fig:Move}
  \end{center}
\end{figure}
\fi

[Collision]
vaccum の Collision は自機と吸収ブロック(Collision A)、自機と敵ブロック(Collision B)の二つがある。
Collision の種類毎に SPE で動作する Collision Task を作成する。どちらの Collision も自機とブロックの衝突判定しか行わないので SPE には自機とブロックの Property を送り、SPE で2者間の衝突判定を行い、Property を更新して PPE に返す。(図\ref{fig:Collision})\\

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.43]{image/Collision.pdf}
    \caption{Collision に使う Property を各 SPE に渡す}
    \label{fig:Collision}
  \end{center}
\end{figure}

Move, Collision を SPE で処理する際に、SPE には SceneGraph ノードは送らない。代わりに vacuum の Move, Collision に必要な情報をまとめた Property を送る。
Property は SceneGraph ノードと1対1で対応しており、Coordinates, Angle, 親子関係の情報, ノードの生成消滅の情報を持つ。
PPE 側では返されてきた Property を元に SceneGraph を作成し Tree を再構成して Rendering に渡す。
\fi

\section{まとめと今後の課題}
PPE で行っていた Move の処理を SPE で行うことで速度の向上が見られた。複数 SPE を用いることでさらに速度の向上が期待できる。
\begin{itemize}
\item SPE 1基で SceneGraph を処理する例題はできたので、複数 SPE に均等に処理を割り振る例題の作成および、SPE での演算の SIMD 化。
\item Property から SceneGraph を生成し tree を構築する部分において、SceneGraph の新規生成と削除を考慮した設計を行う。
\end{itemize}

\thispagestyle{fancy}
\begin{thebibliography}{9}

\bibitem{cell}Sony Corporation.

Cell BroadbandEngine \texttrademark アーキテクチャ, 2006

\bibitem{spursengine}TOSHIBA: SpursEngine

\verb|http://www.semicon.toshiba.co.jp|\\
\verb|/product/assp/selection/spursengine/index.html|

\bibitem{cerium} SourceForge.JP: Cerium Rendering Engine

\verb|https//sourceforge.jp/projects/cerium/|

\bibitem{opencl} OpenCL

\verb|http://www.khronos.org/opencl/|

\bibitem{wataru} Wataru MIYAGUNI.

Cell 用の Fine-Grain Task Manager の実装, 2009

\end{thebibliography}
\end{document}