Mercurial > hg > Papers > 2009 > gongo-master
view paper/cerium.tex @ 10:cd28a12aa36a
add Texture Hash and Scaling effect
| author | gongo@gendarme.cr.ie.u-ryukyu.ac.jp |
|---|---|
| date | Fri, 13 Feb 2009 18:29:33 +0900 |
| parents | df0056a7b95d |
| children | 11d9fd29571b |
line wrap: on
line source
\chapter{Cerium} \label{chapter:cerium} Cerium \cite{gongo2} \cite{cerium} は、我々が提案したゲーム開発フレームワークで、 独自に Rendering Engine (\ref{sec:cerium_rendering}節) を持つ。 ゲーム中のオブジェクトの振る舞いや ルールは SceneGraph (\ref{sec:cerium_scene_graph}節) で管理し、 それらの動きやレンダリングの処理を動的に SPE に割り振るカーネルとして Task Manager が用いられる。 Cerium は主に以下の３つのタスクを持つ (\figref{cerium_task})。 \begin{itemize} \item SceneGraph が持つ Polygon の座標から、実際に画面に表示する座標の 計算を行い、PolygonPack (\ref{sec:cerium_rendering_data}節) を生成する SceneGraph2PolygonPack タスク (\ref{sec:cerium_rendering_s2p} 節) \item PolygonPack から、同じ Y 座標を持つ線分の集合 SpanPack (\ref{sec:cerium_rendering_data}節) を生成する PolygonPack2SpanPack タスク (\ref{sec:cerium_rendering_p2s} 節) \item SpanPack を、Texture を読み込みながら Z Buffer を用いて描画する DrawSpan タスク (\ref{sec:cerium_rendering_draw_span} 節) \end{itemize} \begin{figure}[htb] \begin{center} \includegraphics[scale=0.5]{images/cerium_task.pdf} \caption{Cerium の要素} \label{fig:cerium_task} \end{center} \end{figure} Cerium は SceneGraph、PolygonPack、SpanPack に対してデータ並列実行を行う。 さらに、この3つのタスクは表示画面毎にパイプライン的に実行される。 そのため、Cerium では並列度を維持することが出来る。 Cerium は C++ で実装されており、画像の読み込みや入力デバイスは SDL を用いて行っている。 %プログラム行数は 6919 行である。 \section{SceneGraph} \label{sec:cerium_scene_graph} 本研究では、ゲーム中の一つの場面(Scene)を構成するオブジェクトや その振る舞い、ゲームのルールの集合を SceneGraph とする \cite{chiaki}。 SceneGraph のノードは親子関係を持つ tree で構成される (\figref{cerium_sg_tree})。 親子関係とは、親オブジェクトの回転や平行移動等の行列計算による 頂点座標の変更が、子オブジェクトにも反映する関係のことである。 これは子に対してスタックに積まれた親の変換行列を掛けることで実現できる。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.8]{images/cerium_sg_tree.pdf} \caption{SceneGraph} \label{fig:cerium_sg_tree} \end{center} \end{figure} SceneGraph のノードは以下のようなデータと動作を持つ。 \begin{itemize} \item データ \begin{enumerate} \item Vervatim: ポリゴンオブジェクトの頂点座標 \item Texture: ポリゴンオブジェクトのテクスチャ座標 \item TextureImage: テクスチャイメージ \item TransMatrix: ポリゴンオブジェクトの変換行列 \item Corrdinates: オブジェクトの座標 \item Angle: オブジェクトの角度 \end{enumerate} \item 動作 \item Move: 自律的なオブジェクトの動き \item Collision: 他のノードと衝突したときの動き \end{itemize} \subsection{Scene ポリゴンの生成} \label{sec:cerium_sg_xml} ゲーム中に登場するオブジェクトは、オープンソースの 3Dモデリングツールである Blender \cite{blender} を用いる。 Blender で記述したポリゴンオブジェクトを、座標やテクスチャイメージを 埋め込んだ xml ファイルとして出力する。 Blender にはPython インタプリタがあり、杉山 \cite{chiaki} が独自形式の xml ファイルを生成する Python スクリプトを作成している。 xmlファイルは以下のような構造を持っている。 {\small \begin{verbatim} <?xml version="1.0"?> <OBJECT-3D> <surface name="BACK" size="6" prim="Triangle" parent="NULL"> <coordinate> -227.432511 293.664585 -192.702660 235.318160 294.080875 -192.770592 ・・・・ </coordinate> <normal> 0.000900 -1.000000 0.000000 ・・・・ </normal> <model> -0.016892 -30.731319 -35.638344 </model> <texture> -0.002805 0.996740 ・・・・ </texture> <image name="EARTH.png"> (base64 エンコードデコードされたテクスチャイメージ) </image> </surface> <surface name="ENEMY" size="48" prim="Triangle" parent="BACK"> ・・・・ </surface> </OBJECT-3D> \end{verbatim} } xml には、オブジェクトの名前や親に該当するオブジェクトの名前、 coordinate(ポリゴン情報)、texture(ポリゴンに対応するテクスチャ座標)、 テクスチャイメージがある。 xml ファイル形式を採用している理由は、 Cerium が MacOSX や Linux、PS3 など複数の環境で動作することを目的としており、 環境に依存しないテキスト形式でのデータ構造を構築できるからである。 また、Cerium が将来的にネットワークを使用することを考えており、 その際に有効なフォーマットであると考えたからである。 \subsection{SceneGraph オブジェクトの生成} \label{sec:cerium_sg_create} Cerium は 生成された xml ファイルから、そのパラメータを持つ SceneGraph オブジェクトを生成する (Original Scene Graph)。 ここで作られたオブジェクトはユーザには見せず、 ユーザが該当する SceneGraph を生成したい場合は Orignal を参照し、 そのコピー (Copy Scene Graph) を渡す (\figref{cerium_sg_create}) 。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.8]{images/cerium_sg_create.pdf} \caption{SceneGraph の生成} \label{fig:cerium_sg_create} \end{center} \end{figure} \figref{cerium_sg_create} の Original SceneGraph Database は Cerium が配列として持っており、 xml ファイルを読み込んで生成された SceneGraph を、SceneGraph ID の位置に 格納する。SceneGraph ID は SceneGraph に割り振られるグローバルIDである。 Blender の時点では、SceneGraph の名前は付けられるが、ID(番号) をユーザが 決定、管理するのは難しい。そこで、xml ファイルから自動的に ID を決定する スクリプトを作成した (\figref{cerium_sg_createlist}) 。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.6]{images/cerium_sg_createlist.pdf} \caption{SceneGraph ID の決定} \label{fig:cerium_sg_createlist} \end{center} \end{figure} ゲームに使用する xml ファイルを指定して、SGList.h と SGList.cpp を生成する。 SGList.h には各 SceneGraph の名前に対応する ID が割り振られている。 SGList.cpp のsglist とは、Cerium が xml ファイルを読み込んで、 SceneGraph の名前が分かったとき、 その名前がどの ID を持つかを求めるための配列である。 \subsection{SceneGraph の操作} Cerium では、\ref{sec:cerium_sg_create} 節で述べたような、 xml ファイルのロード、SceneGraph の生成など、SceneGraph を管理するクラスとして SceneGraphRoot クラスを実装している。 SceneGraphRoot では、ユーザが生成した SceneGraph を持ち、 カメラ、ジョイスティックなどの入力デバイスの管理を行う。 以下は SceneGraphRoot の構造である。 \begin{verbatim} typedef SceneGraphRoot *SceneGraphRootPtr; class SceneGraphRoot { // xml から読み込んだ、オリジナルの SceneGraph SceneGraphPtr *sg_src; // move, collision 用の SceneGraph SceneGraphPtr sg_exec_tree; // 描画用の SceneGraph List SceneGraphPtr sg_draw_tree; // コントローラーオブジェクト (Keyboard, Joystick, ..) Pad *controller; // カメラオブジェクト Camera *camera; }; \end{verbatim} SceneGraphRoot と SceneGraph の API をそれぞれ \tabref{cerium_sg_rootapi}、\tabref{cerium_sg_api}に示す。 \begin{table}[htb] \begin{center} \caption{SceneGraphRoot API} \label{tab:cerium_sg_rootapi} \hbox to\hsize{\hfil \begin{tabular}{l|l} \hline \hline createFromXMLfile(char *xmlname) & xml ファイルから \\ & Original SceneGraph を生成する \\ \hline createSceneGraph(int id) & ID に対応する SceneGraph を生成する \\ \hline setSceneData(SceneGraoh* top) & セットした SceneGraph を辿って \\ & Cerium が処理を行う \\ \hline \end{tabular}\hfil} \end{center} \end{table} \begin{table}[htb] \begin{center} \caption{SceneGraph API} \label{tab:cerium_sg_api} \hbox to\hsize{\hfil \begin{tabular}{l|l} \hline \hline addChild(SceneGraph*) & 自身に子を追加する \\ \hline addBrother(SceneGraph*) & 自身に兄弟を追加する \\ \hline remove(void) & 自身を削除する \\ \hline set\_move(move\_func move) & 自身の move を設定する\\ \hline set\_collision(coll\_func collision) & 自身の collision を設定する\\ \hline translate\{X, Y, Z\}(float) & 自身の、各軸に平行な移動 \\ \hline rotate\{X, Y, Z\}(float) & 自身の、各軸に対する回転 \\ \hline \end{tabular}\hfil} \end{center} \end{table} %SceneGraphRoot は \verb+sg_exec_tree+ と \verb+sg_draw_tree+ の二つを持つ。 %\verb+sg_exec_tree+ で各 SceneGraph の move と collison を行った後、 %処理後のノードをコピーして保存しておく。その後 \verb+sg_exec_tree+ が %\verb+sg_draw_tree+ へ遷移し、保存してある SceneGraph を新たな %\verb+sg_exec_tree+ として使用する。SceneGraph のコピーを行うのは、 %SceneGraph の処理を SPE で行わせることが目的だからである。 %SceneGraph の全てを SPE 上に置けない場合、コピーをせず %木の操作をするのは困難である。 \subsection{例題} 以下のコードは、地球と月のオブジェクトがそれぞれ 回転しながら移動するという SceneGraph を記述したものである。 \begin{verbatim} void create_sg(void) { SceneGraphRoot *sgroot = new SceneGraphRoot; // xml ファイルを読み込み、Original Scene Graph を生成 sgroot->createFromXMLfile("universe.xml"); // ID を指定して SceneGraph を生成(Original からのコピー) SceneGraph *earth = sgroot->createSceneGraph(EARTH); // 地球 SceneGraph *moon = sgroot->createSceneGraph(MOON); // 月 earth->set_move(earth_move); moon->set_move(moon_move); // 親子関係の設定 earth->addChild(moon); // SceneGraph をセット sgroot->setSceneData(earth); } /** * @param node 自身 (この場合は moon) */ void moon_move(SceneGraph *node) { // y軸 で 3度回転 node->rotateY(3.0f); } /** * @param node 自身 (この場合は earth) */ void earth_move(SceneGraph *node) { // y軸 で 1度回転 node->rotateY(1.0f); // x,y 軸方向にそれぞれ平行移動 node->translateX(3.0f); node->translateY(3.0f); } \end{verbatim} 実行結果を \figref{cerium_sg_example} に示す。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.5]{images/cerium_sg_example.pdf} \caption{SceneGraph 例題} \label{fig:cerium_sg_example} \end{center} \end{figure} この SceneGraph では、地球が自転と平行移動、月が自転を行うもので、 地球の平行移動、回転に合わせて月が付いてきており、 親子関係が正常に動作していることが確認できた。 地球と月は Blender で、球体にそれぞれのテクスチャを貼付けて作成した。 \section{Rendering Engine} \label{sec:cerium_rendering} Rendering Engine では、SceneGraph から、 実際に表示するポリゴンの抽出 (\ref{sec:cerium_rendering_s2p}節)、 ポリゴンから Span の生成 (\ref{sec:cerium_rendering_p2s}節)、 Span に RGB をマッピングし描画する部分 (\ref{sec:cerium_rendering_draw_span}節) と３つに分けることが出来る。 ここでいう Span とは、ポリゴンに対するある特定の Y 座標に関するデータを 抜き出したものである (\figref{cerium_rendering_span})。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.8]{images/cerium_rendering_span.pdf} \caption{Span} \label{fig:cerium_rendering_span} \end{center} \end{figure} \subsection{Rendering で使うデータの構造} \label{sec:cerium_rendering_data} レンダリング処理は SPE で行うことを前提とし、 それに合わせたデータ構造を採用している。 \subsubsection{PolygonPack} PolygonPack は、SceneGraph から抽出されたポリゴンの集合である。 以下に構造を示す。 \begin{verbatim} // ポリゴンを構成する辺の情報 typedef struct VertexPack { // 座標 (x, y, z) float x; float y; float z; // テクスチャの座標 float tex_x; float tex_y; } VertexPack, *VertexPackPtr; // テクスチャ情報 typedef struct TriTexInfo { uint32 *addr; // テクスチャイメージのアドレス int width; // 幅 int height; // 高さ int scale_max; // 縮小率 } TriangleTexInfo, *TriangleTexInfoPtr; typedef struct PolygonPack { struct PORIGON_info { int size; int light_pos[3]; // 光源の位置 int light_rgb[3]; // 光源の色 }info; TrianglePack tri[MAX_SIZE_TRIANGLE]; PolygonPack* next; }PolygonPack, *PolygonPackPtr; \end{verbatim} PolygonPack は光源やテクスチャ、頂点の情報から構成される。 テクスチャの縮小率に関しては \ref{sec:cerium_rendering_texture_scale} 節で後述する。 \subsubsection{SpanPack} SpanPack は、ポリゴンから抽出された Span の集合である。 以下に構造を示す。 \begin{verbatim} class Span { public: // テクスチャ情報 uint32 *tex_addr; int tex_width; int tex_height; int y; // y 座標 int x; // span の開始 x 座標 int length_x; // span の長さ // span のz 座標(開始、終了) float start_z, end_z; // span に対応するテクスチャの座標 float tex_x1, tex_x2, tex_y1, tex_y2; } class SpanPack { public: /* fields */ struct SpanInfo { int start; int size; int y_top; int light_pos[3]; int light_rgb[3]; } info; Span span[MAX_SIZE_SPAN]; SpanPack *next; }; \end{verbatim} Span は、その座標と、対応するテクスチャの座標を持つ (\figref{cerium_rendering_span_tex})。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.8]{images/cerium_rendering_span_tex.pdf} \caption{Span構造} \label{fig:cerium_rendering_span_tex} \end{center} \end{figure} レンダリングには、この SpanPack を用いる。 ここからは、レンダリングの役割を果たす３つのタスクを説明する。 \subsection{SceneGraph2PolygonPack} \label{sec:cerium_rendering_s2p} SceneGraph の move や collision を行い、 各オブジェクトの変換行列が生成されたら、SceneGraph が持つ ポリゴンの座標に変換行列をかけ、得られた座標を PolygonPack に格納していく。 以下がそのコードである。 \begin{verbatim} SceneGraph *sg = sg_draw_list; float xyz[4]; // ポリゴンの 1辺 xyz[0] = sg->coord[i*3]; xyz[1] = sg->coord[i*3+1]; xyz[2] = sg->coord[i*3+2]*-1; xyz[3] = 1; // matrix = SceneGraph の変換行列 ApplyMatrix(xyz, sg->matrix); // 格納する PolygonPack と PolygonPackPtr pp = new PolygonPack; TrianglePack *triangle = &pp->tri[pp->info.size++]; triangle->ver1.x = xyz[0]; triangle->ver1.y = xyz[1]; triangle->ver1.z = xyz[2]; triangle->ver1.tex_x = sg->tex_pos[i*3]; triangle->ver1.tex_y = sg->tex_pos[i*3+1]; \end{verbatim} この処理を全ての SceneGraph に行い、PolygonPack を生成していく。 \subsection{PolygonPack2SpanPack} \label{sec:cerium_rendering_p2s} 生成された PolygonPack に格納されているポリゴンから、Span を抽出していく。 Span は x 軸に平行な線分を表しているため、始めにポリゴンを水平に分割して 二つの三角形にして、それぞれに対して Span を求める \cite{akira} (\figref{cerium_rendering_half})。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.8]{images/cerium_rendering_half.pdf} \caption{Span生成時のポリゴン分割} \label{fig:cerium_rendering_half} \end{center} \end{figure} 得られた Span を SpanPack に格納する場合、 その SpanPack が持つ全ての Span の y 座標が一定範囲内に入る様にする。 レンダリングする場合、画面を複数の領域に分割しそれぞれを 一つのタスク (\ref{sec:cerium_rendering_draw_span}節) で担当する。 Cerium では レンダリング時に Z Buffer を用いているため、 同じタスクに違う領域の Span があると正常に描画できない。 そこで、一つの SpanPack には決まった y 座標を持った span だけを入れることにより、レンダリング時には独立して行うことができる。 今回は、y の範囲を 8 とした (\figref{cerium_rendering_spack})。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.8]{images/cerium_rendering_spack.pdf} \caption{SpanPack の割り当て} \label{fig:cerium_rendering_spack} \end{center} \end{figure} \subsection{Rendering するための準備} SpanPack が出来れば、あとは Span を見ていき、対応する RGB 値を テクスチャイメージから取り出して フレームバッファに書き込むだけである。しかし、ここで問題がある。 SPE のメモリ領域は 256KB しかないため、Span が参照している テクスチャイメージ全てを送ると動かなくなる可能性がある。 そこで我々は、テクスチャイメージに対していくつかの操作を行った。 ここからは、その詳細について説明する。 \subsection{Texture の分割} \label{sec:cerium_rendering_texture_split} テクスチャは、SDL\_image \cite{sdl_image} の API である IMG\_Load を使用して 読み込む。その後画像は1ピクセル32ビット(RGB$\alpha$)のデータに変換される。 SPE のメモリ領域は 256KB しかないため、テクスチャ全て送ると 動かなくなる可能性がある。 そこで、テクスチャを分割し、そのブロック毎で送ることにした。 そのブロックを Tile と呼び、分割単位は 8x8 とする (\figref{cerium_rendering_tile})。 Tile は \figref{cerium_rendering_tile} のような順番で配列に変換する。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.8]{images/cerium_rendering_tile.pdf} \caption{Texture の分割 (Tile)} \label{fig:cerium_rendering_tile} \end{center} \end{figure} span が持つテクスチャのアドレスはこの配列を指しており、 描画する span 中の 1 pixel の座標から、どの Tile かを計算する。 その Tile をメインメモリから DMA で持って来て RGB 値を取り出す。コードは以下の様になる。 \begin{verbatim} #define TEXTURE_SPLIT_PIXEL 8 #define TEXTURE_BLOCK_SIZE 8*8 /** * テクスチャの座標から、 * テクスチャのどのブロックかを求める * * @param tx X coordinates of texture * @param tx Y coordinates of texture * @param twidth Width of texture * @return block ID */ int getTexBlock(int tx, int ty, int twidth) { int blockX, blockY; blockX = tx / TEXTURE_SPLIT_PIXEL; blockY = ty / TEXTURE_SPLIT_PIXEL; return blockX + (twidth/TEXTURE_SPLIT_PIXEL)*blockY; } /** * block ID と、テクスチャの TOP address から * (tx,ty) で使われるテクスチャの Tile addres を求める * * @param tx X coordinates of texture * @param tx Y coordinates of texture * @param tw Width of texture * @param tex_addr_top (tx,ty) で使うテクスチャの先頭address * @return block ID */ uint32* getTile(int tx, int ty, int tw, uint32 *tex_addr_top) { int block = getTexBlock(tx, ty, tw); return tex_addr_top + block*TEXTURE_BLOCK_SIZE; } /** * texture の座標から、Tile が持つ RGB 値を返す * * @param tx X coordinates of texture * @param tx Y coordinates of texture * @param addr Tile address (return getTile()) */ uint32 get_rgb(int tx, int ty, uint32 *tile) { uint32 pixel[TEXTURE_BLOCK_SIZE]; smanager->dma_load(pixel, tile, sizeof(uint32)*TEXTURE_BLOCK_SIZE, tag); smanager->dma_wait(tag); return pixel[(TEXTURE_SPLIT_PIXEL)*ty+tx]; } \end{verbatim} \subsection{SPE 上での Tile の管理} \label{sec:cerium_rendering_texture_hash} \ref{sec:cerium_rendering_texture_split} 節で求めた Tile を毎回 DMA で転送するのは効率が悪い。 そこで、SPE 上にいくつか Tile を置ける領域を予め作っておき、 DMA 転送してきた Tile を保存しておく。 描画する span が、すでに SPE 上にある Tile を参照する場合、そのままそれを使い、 それ以外の Tile を参照し且つ領域が満杯の場合、 一番最初に保存した Tile を削除して、 新しくきた Tile を保存するという FIFO で Tile を管理する。 Tile の検索はハッシュを用いる。ハッシュ値は Tile のアドレスを使用している。 コードは以下の様になる。 \begin{verbatim} #define TEXTURE_BLOCK_SIZE 8*8 // SPE 上での Tile の構造 typedef struct { uint32 pixel[TEXTURE_BLOCK_SIZE] // Tile の実データ; uint32 *texture_addr // Tile のメインメモリのアドレス; } Tile, *TilePtr; // Tile リスト class TileList { public: int curIndex; Tile tile[MAX_TILE]; /** * 次に扱う tile を取得する * * @return tile * * tile[] をリングバスとして * FIFO を実現する */ TilePtr nextTile(void) { TilePtr t = &tile[curIndex]; curIndex = (curIndex + 1) % MAX_TILE; return t; } }; TileListPtr tileList; /** * 新しい Tile を登録する * 一番古い Tile は順次削除していく * * @param addr Tile のアドレス(メインメモリ空間) */ void set_rgb(uint32 *addr) { TilePtr tile; // 新しい Tile の登録 tile = tileList->nextTile(); hash->remove(tile->texture_addr); tile->texture_addr = addr; // hash に登録 hash->put(tile->texture_addr, tile); // DMA 転送 (PPE->SPE) smanager->dma_load(tile->pixel, (uint32)addr, sizeof(uint32)*TEXTURE_BLOCK_SIZE, tag); } /** * Tile のアドレスから、テクスチャイメージデータを返す * * @param tx X coordinates of texture * @param tx Y coordinates of texture * @param addr tile address * @return Image data * uint32 get_rgb(int tx, int ty, uint32 *addr) { TilePtr tile; tile = hash->get(addr); return tile->pixel[(TEXTURE_SPLIT_PIXEL)*ty+tx]; } \end{verbatim} \ref{sec:cerium_rendering_texture_split}節で説明した get\_rgb() も ハッシュを導入したことにより変更されている。 現在、SPE 上で保存する Tile は 128 個としている。 領域は \verb+global_alloc()+ (\ref{sec:tm_sm_global} 節)で確保する。 ここで、SPE 上で保存する Tile の数を変化させることによって レンダリングの実行速度がどのように変化するかを実験した。 使用する画像は \figref{cerium_hash_test} を用いる。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.5]{images/cerium_scale_test1.pdf} \caption{Texture 例題 (512x384)} \label{fig:cerium_hash_test} \end{center} \end{figure} \begin{table}[htb] \begin{center} \caption{SPE 上での Tile 管理数による実行速度比較} \label{tab:cerium_hash_test} \hbox to\hsize{\hfil \begin{tabular}{c|l} \hline \hline Tile 保存数 & 実行速度 (FPS) \\ \hline \hline 1 & 11.051374 \\ \hline 128 & 29.411765 \\ \hline \end{tabular}\hfil} \end{center} \end{table} \tabref{cerium_hash_test} より、 SPE 上で保存する Tile の数を増やすことにより テクスチャのヒット率が上昇し、DMA 転送回数が減ることで 実行速度が向上することがわかる。 \subsection{Texture の縮小} \label{sec:cerium_rendering_texture_scale} 遠くにいるオブジェクトに対して、原寸のテクスチャを貼る必要はなく、 経験的に荒いテクスチャを貼っても問題ないと考えられる。 そこで、オリジナルのテクスチャに対して縮小したものを用意し、 オブジェクトがどれだけ離れているかによって、縮小率を変えたテクスチャを 使うことにする。 まず、オリジナルのテクスチャの最大縮小率を求める。 テクスチャは縦横ともに 1/2、1/4、1/8 と、2分の1ずつ縮小させる。 また、後に Tile に分割しなければならないため、縦、横ともに 8の倍数を保つようにする。 テクスチャの width、height から、最大縮小率を求めるコードが以下になる。 \begin{verbatim} // tex_w 原寸幅 // tex_h 原寸高さ // TEXTURE_SPLIT_PIXEL 8 while (tex_w % TEXTURE_SPLIT_PIXEL == 0 && tex_h % TEXTURE_SPLIT_PIXEL == 0) { all_pixel_num += tex_w*tex_h; tex_w /= 2; tex_h /= 2; scale *= 2; } scale /= 2; \end{verbatim} これで 最大縮小率 (scale = テクスチャを 1/(scale*2) する) が求められる。 次に、scale を使ってテクスチャを縮小する。 縮小したテクスチャ毎に Tile で分割し、全ての縮小率で求めた Tile を繋げて Tile Array とする (\figref{cerium_rendering_tex_tapestry})。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.8]{images/cerium_rendering_tex_tapestry.pdf} \caption{Texture の縮小 (Tapestry の生成)} \label{fig:cerium_rendering_tex_tapestry} \end{center} \end{figure} ここでは、縮小された画像を Tapestry と呼ぶ。 SceneGraph や PolygonPack の時点ではテクスチャイメージとして、 \figref{cerium_rendering_tex_tapestry} における、TileArray の先頭 (Tapestry 1) のアドレスを持つ。 そして、PolygonPack2SpanPack (\ref{sec:cerium_rendering_p2s}節)の中で、 span の長さと使用するテクスチャの長さの比率を調べ、それに適した Tapestry を Span のテクスチャイメージとする。 以下が、Span で使用するテクスチャの scale を求め、その scale にあった Tapestry を決定するコードである。 {\small \begin{verbatim} /** * span の width,height と texture の width,height を比べて * span を描画する際に使う texture の比率を求める * * @param[in] width Width of span * @param[in] height Height of span * @param[in] tex_width Width of 1/1 texture that span use * @param[in] tex_height Height of 1/1 texture that span use * @param[in] scale_max この Span で使う texture の最大縮小率 * 計算結果が scale_max 以上になるのを防ぐ * @return 描画に使う texture の比率 * width と height は 1/scale の画像を使う * */ static int getScale(int width, int height, int tex_width, int tex_height, int scale_max) { int base, tex_base; int scale = 1; /** * width と height で、長い方を基準に、 * texture の scale を決める */ if (width > height) { base = width; tex_base = tex_width; } else { base = height; tex_base = tex_height; } if (tex_base > base) { int t_scale = tex_base/base; while (t_scale >>= 1) { scale <<= 1; } } return (scale > scale_max) ? scale_max : scale; } /* * scale の値から、各 Tapestry の先頭アドレスを返す * * @param[in] tw Width of texture * @param[in] th Height of texture * @param[in] scale テクスチャの縮小率 (= 2^n) * @param[in] addr_top TileArrayの先頭(Tapestry1) * @return scale に対応する Tapestry のアドレス */ static uint32* getTapestry(int tw, int th, int scale, uint32 *addr_top) { int index = 0; for (int s = 1; s < scale; s <<= 1) { index += tw*th; tw /= 2; th /= 2; } return addr_top + index; } \end{verbatim} } \figref{cerium_rendering_tex_tapestry} を見てわかるように 縮小すれば Tile の数は減るので、Span に必要な Tile の数も抑えられる。 そのことにより、SPE 上での Tile の入れ替えも少なくなり、 Tile のヒット率も上昇する。 \figref{cerium_scale_test} が、実際にテクスチャの縮小を行った結果である。 画像は \figref{cerium_hash_test} と同じ物を使う。 この画像の scale\_max は 16 となる。 左が通常(1/1)のテクスチャを用いた図、右が scale\_max (1/16) のテクスチャを 用いた図である。 \figref{cerium_scale_test} を実際にレンダリングし、その実行速度を \tabref{cerium_scale_test} に示す。 \begin{figure}[htb] \begin{center} \begin{tabular}{cc} \begin{minipage}[t]{.45\hsize} \includegraphics[scale=0.40]{images/cerium_scale_test1.pdf} \end{minipage} \begin{minipage}[t]{.45\hsize} \includegraphics[scale=0.40]{images/cerium_scale_test2.pdf} \end{minipage} \end{tabular} \caption{Texture Scaling の結果 左：1/1、右：1/16} \label{fig:cerium_scale_test} \end{center} \end{figure} \begin{table}[htb] \begin{center} \caption{Texture Scaling による実行速度比較} \label{tab:cerium_scale_test} \hbox to\hsize{\hfil \begin{tabular}{c|l} \hline \hline Scale & 実行速度 (FPS) \\ \hline \hline 1 (\figref{cerium_scale_test} 左) & 29.411765 FPS \\ \hline 16 (\figref{cerium_scale_test} 右) & 64.643800 FPS \\ \hline \end{tabular}\hfil} \end{center} \end{table} \tabref{cerium_scale_test} より、 Texture の Scaling によって、 実行速度を向上させる効果があることがわかる。 \subsection{Rendering (DrawSpan)} \label{sec:cerium_rendering_draw_span} 現在、PlayStation 3 の GPU にアクセスする API は公開されていないため、 Cerium ではフレームバッファに描画する。 フレームバッファのアドレスは mmap() で取得できるため、 タスクの出力としてフレームバッファを指定するか、 タスク内で DMA 転送を行えば (\ref{sec:tm_dma}節)、直接描画することができる。 通常の Linux で動作する場合も同様にフレームバッファに描画する。 MacOSX の場合は SDL 経由で描画する。 レンダリングは DrawSpan というタスクで行う。 受け取った SpanPack から Span を取り出す。 Span の端から 1 pixel ずつ見ていき、その pixel の z 座標と Z Buffer を見比べ、 描画するものとをわかれば、対応する RGB 値を書き込む。 また、DrawSpan は分割された画面領域の一部を担当するので、 span がその領域を超えている場合は描画しない。 現在、一つの DrawSpan が描画する領域は 256x8 としている (\figref{cerium_rendering_draw_span})。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.7]{images/cerium_rendering_draw_span.pdf} \caption{DrawSpan の担当領域} \label{fig:cerium_rendering_draw_span} \end{center} \end{figure} {\small \begin{verbatim} /** * Span から RGB 値を求め、FrameBuffer 用のバッファ (linebuf) に書き込む * * @param span Span * @param startx DrawSpan が担当する領域開始の x 座標 * @param endx DrawSpan が担当する領域終了の x 座標 */ void DrawSpan::drawLine(SpanPtr span, int startx, int endx) { int x = span->x; int rangex = endx - startx + 1; int x_len = span->length_x; int js = (x < startx) ? startx - x : 0; int je = (x + x_len > endx) ? endx - x : x_len; /* span->x に対応する Texture の座標 (tex_xpos, tex_ypos) */ int tex_xpos, tex_ypos; // span の始点に対応する座標 (tex1, tey1) float tex1 = span->tex_x1; float tey1 = span->tex_y1; // span の終点に対応する座標 (tex2, tey2) float tex2 = span->tex_x2; float tey2 = span->tex_y2; // span の始点、終点に対応する z 座標 float zpos1 = span->start_z; float zpos2 = span->end_z; // Tile 内での座標 int localx, localy = getLocalY(span->y-1); for (int j = js; j <= je; j++) { float tex_x, tex_y, tex_z; localx = getLocalX(x-1+j); tex_z = zpos1*(x_len-1-j)/(x_len-1) + zpos2*j/(x_len-1); // z 座標が小さいほど、画面に近い if (tex_z < zRow[localx + (rangex*localy)]) { uint32 *tex_addr; int tex_localx; int tex_localy; tex_x = tex1*(x_len-1-j)/(x_len-1) + tex2*j/(x_len-1); tex_y = tey1*(x_len-1-j)/(x_len-1) + tey2*j/(x_len-1); if (tex_x > 1) tex_x = 1; if (tex_x < 0) tex_x = 0; if (tex_y > 1) tex_y = 1; if (tex_y < 0) tex_y = 0; tex_xpos = (int)((span->tex_width-1) * tex_x); tex_ypos = (int)((span->tex_height-1) * tex_y); tex_addr = getTile(tex_xpos, tex_ypos, span->tex_width, span->tex_addr); tex_localx = tex_xpos % TEXTURE_SPLIT_PIXEL; tex_localy = tex_ypos % TEXTURE_SPLIT_PIXEL; // SPE 上に 使用する Tile がない if (!isAvailableTile(tex_addr)) { set_rgb(tex_addr); smanager->dma_wait(tag); } int rgb = get_rgb(tex_x, tex_y, tex_addr); // Z Buffer の更新 zRow[x + (rangex*y)] = zpos; // RGB 値の更新 linebuf[x + (rangex*y)] = rgb; } } } \end{verbatim} } タスク終了後、linebuf をフレームバッファに DMA 転送することで、描画が完了する。 \section{Cerium を用いた学生によるゲーム開発} \label{sec:cerium_student} \figref{cerium_game_1} は、学生が Cerium を実際に 使用して作った作成した 3D シューティングゲームである。 学生は、始めに MacOSX で開発を進め、移動や衝突判定のアルゴリズムを 確認し、そのままの形で PS3 で動作することも確認できた。 開発期間は１ヶ月である。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.2]{images/cerium_game_1.pdf} \caption{SuperDandy3D (仮)} \label{fig:cerium_game_1} \end{center} \end{figure} このゲームの SceneGraph は \figref{cerium_game_sg} のようになる。 \begin{figure}[htb] \begin{center} \includegraphics[scale=0.8]{images/cerium_game_sg.pdf} \caption{SuperDandy3D (仮) の SceneGraph} \label{fig:cerium_game_sg} \end{center} \end{figure} Player はキーボードやジョイスティックの十字キーで移動ができ、 対応するボタンを押すと弾を発射する。以下がそのコードである。 {\small \begin{verbatim} player_move_all(SceneGraphPtr node, int screen_w, int screen_h) { Pad *pad = sgroot->getController(); // 移動中は機体の傾きが変わるため // move_right, move_left, move_up, move_down 内で // 傾きの計算をしている if (pad->right.isHold() || pad->left.isHold() || pad->up.isHold() || pad->down.isHold()) { if (pad->right.isHold()) { player_move_right(node, screen_w, screen_h); } else if (pad->left.isHold()) { player_move_left(node, screen_w, screen_h); } if (pad->down.isHold()) { player_move_up(node, screen_w, screen_h); } else if(pad->up.isHold()) { player_move_down(node, screen_w, screen_h); } } else { player_move_idle(node); } // 弾を発射 if (pad->circle.isPush()) { // 弾の SceneGraph を生成し、初期化したあと // node (player) の兄弟として SceneGraph に登録する SceneGraphPtr bullet = sgroot->createSceneGraph(BULEBULLET); bullet->set_move_collision(bluebullet_move, bullet_collision); bullet_init(bullet, node); node->addBrother(bullet); } } \end{verbatim} } 発射された弾は Enemy と衝突判定を行う。 弾と Enemy が衝突していれば、両者とも SceneGraph から削除する。 また、弾が画面外から消えたら弾自身を削除する。 以下がそのコードとなる。 {\small \begin{verbatim} void bullet_collision(SceneGraphPtr node, int w, int h, SceneGraphPtr tree) { SceneGraphIteratorPtr it = sgroot->getIterator(tree); static int damage = 0; // tree に E_PLANE が入れば全て判定する for (; it->hasNext(E_PLANE);) { // Iterator を E_PLANE まで進める it->next(E_PLANE); // Iterator が現在参照している SceneGraph を返す SceneGraphPtr enemy = it->get(); int judge = square_judge(node, enemy); if (judge == HIT) { enemy->remove(); node->remove(); } } // 画面外に消えたら削除 if (node->xyz[1] > 100) { node->remove(); } } \end{verbatim} } SceneGraphIterator とは、SceneGraph を走査するオブジェクトである。 上記コードの様に、tree の中から特定の SceneGraph を検索する場合に用いる。 SceneGraph を指定しなければ順に SceneGraph を辿っていく。 Back は \figref{cerium_game_1} の画面中央にある背景画像である。 本来は Back は画面全体に表示されるべきだが、 Cerium にはまだ背景用の SceneGraph が実装されていない。 このゲームを、MacOSX、Linux、PS3上でそれぞれ動作させ、 それらの実行速度を比較してみた。\tabref{cerium_game_tab} が結果となる。 \begin{table}[htb] \begin{center} \caption{SuperDandy3D(仮) の各動作環境での実行速度} \label{tab:cerium_game_tab} \hbox to\hsize{\hfil \begin{tabular}{l|r} \hline \hline MacOSX 10.5 & 5.7 FPS \\ \hline Linux (Fedora 10) & 7.8 FPS \\ \hline PS3 SPE 1個 & 8.1 FPS \\ \hline PS3 SPE 6個 & {\bf 29.3 FPS} \\ \hline \end{tabular}\hfil} \end{center} \end{table} Linux は FrameBuffer に直接描画しているため 一旦 SDL\_Surface を経由して描画する MacOSX より速い。 PS3 では、SPE の数を 1 から 6 に変えると、およそ 3.6 倍となった。 性能は上がっているものの、台数効果が出ていないと言える。 この原因として以下の点が挙げられる。 \begin{itemize} \item SceneGraph の演算を SPE で行っていない \item SPE での処理に SIMD 演算を組み込んでいない \end{itemize} 各 SceneGraph の move、collision は、現在メインスレッドの関数として 実行している。これらをタスクとして生成し、SPE 上で実行することにより、 並列度が確保でき、実行速度が向上すると考えている。 また、SIMD 演算を積極的に用いることにより、SPE の処理能力を最大限に 使うことができるため、今後の課題として挙がる。