\documentclass[twocolumn,twoside,9.5pt]{jarticle}
% \usepackage[dvips]{graphicx}
\usepackage[dvipdfm]{graphicx}
\usepackage{fancyhdr,picins}
\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{SceneGraph を用いた\\マルチコア CPU 向けゲームの処理}
\author{065746J 仲宗根広樹　指導教員 : 河野真治}
\date{\today}
\maketitle
\thispagestyle{fancy}

\section{概要}
近年のゲームマシンは高度な並列性を持つようになっており、
ゲームプログラムでの様々なレベルでの並列処理が必須となっている。
プログラムの一部を並列処理するのではなく、定常的な並列度を提供する
必要がある。しかし、
データが処理される順番を把握することができないので出力結果などが特定しづらく、
逐次型に比べて難易度が高い
データ転送やタスクの生成、管理等の技術が多く存在する。
短期間の学生実験では新しい技術を習得することに時間を割かれ、ゲームの完成度を上げることが難しくなる。

そこで本研究では、
SceneGraph と言うゲーム中の１つの場面(Scene) を構成するオブジェクトやその振る舞い、ゲームのルールの集合を導入する。
SceneGraph の処理を自動的に並列に行なうことにより、並列処理と、習得の早い
ゲームプログラミングの両立を可能にする。

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

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

SceneGraph ノード は以下のようなデータと動作を持つ。
\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}

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}
オブジェクトの動作や衝突判定に必要になるのは Coordinates や Angle であり、Polygon や Texture のデータは不要になる。そこでゲームに必要なオブジェクトの内部状態を持った Property を用いる。Property には Coordinates, Angle の他に、tree を再生成する時に必要な親子関係なども含める。一方の tree を Rendering で使用し、もう一方を Move, Collision で使用し、両方の処理が終わったら、相互にバッファを切り替える。切替える時に二つのタスクは同期する必要がある。

\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}

%SceneGraph ノードにはポリゴンを形成するための点やテクスチャの座標等が含まれている。これらの情報を全て SPE に送ると Local Store に入りきらない。そのため Move、Collision に必要な Coordinates, Angle, 親子関係の情報、生成消滅の情報を持つ Property の配列を作成する。
%SceneGraph の tree と Property のバッファは二つ用意する。

% \subsection{Move}
[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

% \subsection{Collision}
[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 に渡す。

\section{まとめと今後の課題}
\begin{itemize}
\item 現在は SPE 1基で SceneGraph を処理する例題の作成途中なので、複数 SPE に均等に処理を割り振る例題の作成。
\item Property から SceneGraph を生成し tree を構築する部分において、SceneGraph の新規生成と削除を考慮した設計を行う。
\item xml から作成された SceneGraph はオリジナルとして配列に順次格納されている。現在は SceneGraph を create する場合はオリジナルの配列をリニアサーチしてきた物をコピーしている。このオリジナルの配列を Texture を管理している hash テーブルを用いてまとめて管理できるようにする。
\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}