(57)【特許請求の範囲】
【請求項１】
タイル基盤レンダリングのためのタイルビニングを行う方法において、
前記タイル基盤レンダリングの対象である客体を構成する経路に係わる情報を獲得する段階と、
前記経路の形状によって、前記経路それぞれを、第１グループまたは第２グループに分類する段階と、
前記第１グループに含まれた経路と、前記第２グループに含まれた経路と、を区分し、前記タイルビニングを行う段階と、を含み、
前記タイルビニングを行う段階は、
フレームに含まれたタイルのうち、前記第１グループに含まれた経路を含むタイルを選択する段階と、
前記選択されたタイル、及び前記選択されたタイルそれぞれの一側方向に並んだ少なくとも１つのタイルに、前記第１グループに含まれた経路の識別値を割り当てる段階と、を含む方法。
【請求項２】
タイル基盤レンダリングのためのタイルビニングを行う方法において、
前記タイル基盤レンダリングの対象である客体を構成する経路に係わる情報を獲得する段階と、
前記経路の形状によって、前記経路それぞれを、第１グループまたは第２グループに分類する段階と、
前記第１グループに含まれた経路と、前記第２グループに含まれた経路と、を区分し、前記タイルビニングを行う段階と、を含み、
前記タイルビニングを行う段階は、
フレームに含まれたタイルのうち、前記第２グループに含まれた経路に対応する外郭三角形を含むタイルを選択する段階と、
前記選択されたタイル、及び前記選択されたタイルそれぞれの一側方向に並んだ少なくとも１つのタイルに、前記第２グループに含まれた経路の識別値を割り当てる段階と、を含むことを特徴とする方法。
【請求項３】
前記選択されたタイルは、前記第１グループに含まれた経路の開始地点を含む第１タイル、及び前記第１グループに含まれた経路の終了地点を含む第２タイルを含むことを特徴とする請求項１または２に記載の方法。
【請求項４】
前記一側方向は、前記選択されたタイルそれぞれの位置を中心に、左側方向、右側方向、上側方向、下側方向のうちいずれか一つを含むことを特徴とする請求項１または２に記載の方法。
【請求項５】
前記第１グループに含まれた経路を構成する頂点それぞれに対応する座標を利用して、前記フレームに境界ボックスを設定する段階をさらに含み、
前記識別値を割り当てる段階は、前記境界ボックス内に含まれたタイルに、前記識別値を割り当てることを特徴とする請求項１または２に記載の方法。
【請求項６】
前記境界ボックスは、前記座標において、水平方向成分の最大値、及び垂直方向成分の最大値で形成された第１座標と、前記水平方向成分の最小値、及び前記垂直方向成分の最小値で形成された第２座標と、を結ぶ線を対角線にする四角形であることを特徴とする請求項５に記載の方法。
【請求項７】
前記第１グループに含まれた経路を含むタイル間の位置関係によって、前記識別値が割り当てられたタイルのうち、少なくとも１つのタイルに割り当てられた前記識別値を除去する段階をさらに含むことを特徴とする請求項１または２に記載の方法。
【請求項８】
前記除去する段階は、
前記フレームに含まれたタイルのうち、前記タイルそれぞれに対応する座標の垂直方向成分が同一であるタイルを選択し、
前記選択されたタイルのうち、前記第１グループに含まれた経路を含むタイルの水平方向成分を比較することにより、最小水平方向成分を獲得し、
前記選択されたタイルのうち、前記最小水平方向成分より小さい水平方向成分を有するタイルに割り当てられた前記識別値を除去することを特徴とする請求項７に記載の方法。
【請求項９】
前記除去する段階は、
前記フレームに含まれたタイルのうち、前記タイルそれぞれに対応する座標の水平方向成分が同一であるタイルを選択し、
前記選択されたタイルのうち、前記第１グループに含まれた経路を含むタイルの垂直方向成分を比較することにより、最小垂直方向成分及び最大垂直方向成分を獲得し、
前記選択されたタイルのうち、前記最小垂直方向成分より小さい垂直方向成分を有するタイルに割り当てられた識別値、及び前記最大垂直方向成分より大きい垂直方向成分を有するタイルに割り当てられた前記識別値を除去することを特徴とする請求項７に記載の方法。
【請求項１０】
前記第１グループに含まれた経路を含むタイルのうちから選択された第３タイルの一側方向に並んだ少なくとも１つのタイルの初期周回回数を演算する段階をさらに含み、
前記第３タイルは、前記第１グループに含まれた経路を含むタイルのうち、前記第１グループに含まれた経路の開始地点を含む第１タイル、及び前記第１グループに含まれた経路の終了地点を含む第２タイルが除かれたタイルを示すことを特徴とする請求項１または２に記載の方法。
【請求項１１】
前記初期周回回数を演算する段階は、前記第１グループに含まれた経路が、前記第３タイルを通過する形態に基づいて、前記初期周回回数を演算することを特徴とする請求項１０に記載の方法。
【請求項１２】
前記演算する段階は、
前記第１グループに含まれた経路が、前記第３タイルの対向する２本の境界線を時計回り方向に通過する場合、所定の値を加算し、前記第１グループに含まれた経路が、前記第３タイルの対向する２本の境界線を反時計回り方向に通過する場合、前記所定の値を減算することにより、前記初期周回回数を演算することを特徴とする請求項１１に記載の方法。
【請求項１３】
前記演算する段階は、
前記第１グループに含まれた経路が、前記第３タイルの対向する２本の境界線を時計回り方向に通過する場合、所定の値を減算し、前記第１グループに含まれた経路が、前記第３タイルの対向する２本の境界線を反時計回り方向に通過する場合、前記所定の値を加算することにより、前記初期周回回数を演算することを特徴とする請求項１１に記載の方法。
【請求項１４】
前記第１グループに含まれた経路は、前記客体を構成するエッジを含み、前記第２グループに含まれた経路は、前記客体を構成するカーブを含むことを特徴とする請求項１または２に記載の方法。
【請求項１５】
請求項１ないし１４のうちいずれか１項に記載の方法をコンピュータに実行させるコンピュータプログラム。
【請求項１６】
請求項１ないし１４のうちいずれか１項に記載の方法を実行するタイル基盤レンダリングのためのタイルビニングを行う装置。
【請求項１７】
タイル基盤レンダリングを行う方法において、
前記タイル基盤レンダリングの対象である客体を構成する少なくとも１つの経路に係わる情報を獲得する段階と、
前記経路の形状によって、前記経路それぞれを、第１グループまたは第２グループに分類する段階と、
前記第１グループに含まれた経路と、前記第２グループに含まれた経路と、を区分し、タイルビニングを行う段階と、
前記経路それぞれの位置及び進行方向に基づいて、フレームに含まれたタイルそれぞれの周回回数を演算し、前記演算された周回回数に基づいて、前記フレームに含まれたピクセルをシェーディングする段階と、を含む方法。
【請求項１８】
前記シェーディングする段階は、既設定の規則に基づいて、前記ピクセルをシェーディングし、
前記既設定の規則は、前記周回回数が０ではない値を有するピクセルにカラー値を割り当てる第１規則、または前記周回回数が奇数である値を有するピクセルにカラー値を割り当てる第２規則を含む請求項１７に記載の方法。
【請求項１９】
請求項１７または１８に記載の方法をコンピュータに実行させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路レンダリングのためのタイルビニングを行う方法及びその装置に関する。
【背景技術】
【０００２】
ベクトルグラフィックス（vector  graphics）または経路レンダリング（path  rendering）を行う場合、グラフィック処理装置（ＧＰＵ：graphics  processing  unit、以下ＧＰＵという）の加速性能を向上させるための方法が研究されている。経路レンダリングの場合、入力データが三角形によって構成されず、コマンド（command）と頂点（vertex）との組み合わせによって構成されている。従って、経路レンダリングを行うとき、ＧＰＵの加速性能を向上させ難い。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明が解決しようとする課題は、経路レンダリングのためのタイルビニングを行う方法及びその装置を提供するところにある。
【０００４】
本発明が解決しようとする課題はまた、前記方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体を提供するところにある。
【０００５】
本実施形態が解決しようとする技術的課題は、前述のような技術的課題に限定されるものではなく、以下の実施形態から、他の技術的課題が類推されるのである。
【課題を解決するための手段】
【０００６】
一側面によるタイル基盤レンダリング（tile-based  rendering）のためのタイルビニング（tile  binning）を行う方法は、前記レンダリングの対象である客体を構成する経路に係わる情報を獲得する段階と、前記経路の形状によって、前記経路それぞれを第１グループまたは第２グループに分類する段階と、前記第１グループに含まれた経路と、前記第２グループに含まれた経路と、を区分し、前記タイルビニングを行う段階と、を含む。
【０００７】
他の側面によるタイル基盤レンダリングのためのタイルビニングを行う装置は、前述の方法を実行する。
【０００８】
さらに他の側面によるタイル基盤レンダリングを行う方法は、前記レンダリングの対象である客体を構成する少なくとも１つの経路に係わる情報を獲得する段階と、前記経路の形状によって、前記経路それぞれを、第１グループまたは第２グループに分類する段階と、前記第１グループに含まれた経路と、前記第２グループに含まれた経路と、を区分し、前記タイルビニングを行う段階と、前記経路それぞれの位置及び進行方向に基づいて、前記フレームに含まれたタイルそれぞれの周回回数を演算し、前記演算された周回回数に基づいて、前記フレームに含まれたピクセルをシェーディングする段階と、を含む。
【０００９】
さらに他の側面によるコンピュータプログラムは、前述の方法をコンピュータに実行させる。
【発明の効果】
【００１０】
本発明によれば、レンダリング装置が経路それぞれに対して独立してタイルビニングを行うことができ、レンダリング装置の動作に要する時間及びコスト（例えば、電力）が低減される。また、該レンダリング装置は、フレームに含まれたタイルに対して不要に割り当てられた経路の識別コストを除去することにより、レンダリング装置の効率がさらに高くなる。
【００１１】
また、該レンダリング装置は、フレームに含まれたピクセルのうち、経路が通過するタイルに含まれたピクセルについてのみ周回回数を演算することにより、レンダリング装置の演算速度が向上する。また、該レンダリング装置は、ステンシルバッファの使用なしに、ピクセルそれぞれの周回回数を演算することができるが、ステンシルバッファを使用することにより、メモリ入出力が過度に発生するという問題と、重複したメモリ入出力が発生するという問題とが解消される。
【００１２】
また、該レンダリング装置は、フレームに含まれたピクセルそれぞれに対して、並列して周回回数を生成することにより、高速で経路レンダリングを行うことができ、短時間内に、高解像度のレンダリングを行うことができる。
【図面の簡単な説明】
【００１３】
【図１】一実施形態による、経路レンダリングを行う装置の一例を図示した構成図である。
【図２Ａ】一実施形態によるビニング遂行部の一例を図示した構成図である。
【図２Ｂ】一実施形態による獲得部が経路を分類する一例を示す図面である。
【図３】一実施形態によるビニング遂行部が遂行する動作の一例を示したフローチャートである。
【図４Ａ】一実施形態による割当て部が、フレームに含まれたタイルのうち、第１経路が通過するタイルを選択する一例について説明するための図面である。
【図４Ｂ】一実施形態による割当て部が、フレームに含まれたタイルのうち、第１経路が通過するタイルを選択する一例について説明するための図面である。
【図５Ａ】一実施形態による割当て部が、フレームに含まれたタイルのうち、経路が通過するタイルを選択する一例図面である。
【図５Ｂ】一実施形態による割当て部が、フレームに含まれたタイルのうち、経路が通過するタイルを選択する一例図面である。
【図５Ｃ】一実施形態による割当て部が、フレームに含まれたタイルのうち、経路が通過するタイルを選択する一例図面である。
【図５Ｄ】一実施形態による割当て部が、フレームに含まれたタイルのうち、経路が通過するタイルを選択する一例図面である。
【図５Ｅ】一実施形態による割当て部が、フレームに含まれたタイルのうち、経路が通過するタイルを選択する一例図面である。
【図６】一実施形態による割当て部が、タイルに経路の識別値を割り当てる一規則について説明するための図面である。
【図７】一実施形態による割当て部が、タイルに経路の識別値を割り当てた一例を示す図面である。
【図８】一実施形態による割当て部が、タイルに経路の識別値を割り当てる他の例を示したフローチャートである。
【図９】一実施形態による割当て部が、タイルにカーブの識別値を割り当てる一例について説明するための図面である。
【図１０】一実施形態によるビニング遂行部の他の例を図示した構成図である。
【図１１】一実施形態によるビニング遂行部が遂行する動作の他の例を示したフローチャートである。
【図１２Ａ】一実施形態による設定部が、境界ボックスを設定する一例について説明するための図面である。
【図１２Ｂ】一実施形態による設定部が、境界ボックスを設定する一例について説明するための図面である。
【図１３】一実施形態によるビニング遂行部のさらに他の例を図示した構成図である。
【図１４】一実施形態によるビニング遂行部が遂行する動作のさらに他の例を示したフローチャートである。
【図１５】一実施形態による、フレームに含まれたタイルに、経路の識別値が割り当てられた一例が図示された図面である。
【図１６】一実施形態による除去部が、タイルに割り当てられた識別値を除去する一例を示したフローチャートである。
【図１７】一実施形態による除去部が、最小水平方向成分を獲得する一例について説明するための図面である。
【図１８Ａ】一実施形態による除去部が、タイルに割り当てられた識別値を除去する一例について説明するための図面である。
【図１８Ｂ】一実施形態による除去部が、タイルに割り当てられた識別値を除去する一例について説明するための図面である。
【図１９】一実施形態による除去部が、タイルに割り当てられた識別値を除去する他の例を示したフローチャートである。
【図２０】一実施形態による除去部が、タイルに割り当てられた識別値を除去する他の例について説明するための図面である。
【図２１Ａ】一実施形態によるフレームに境界ボックスが設定された場合、除去部が動作する一例について説明するための図面である。
【図２１Ｂ】一実施形態によるフレームに境界ボックスが設定された場合、除去部が動作する一例について説明するための図面である。
【図２２】一実施形態によるビニング遂行部のさらに他の例を図示した構成図である。
【図２３】一実施形態によるビニング遂行部が遂行する動作のさらに他の例を示したフローチャートである。
【図２４Ａ】一実施形態による周回回数について説明するための図面である。
【図２４Ｂ】一実施形態による周回回数について説明するための図面である。
【図２５】一実施形態による演算部が、タイルの初期周回回数を演算する一例を示したフローチャートである。
【図２６】割当て部がタイルに経路の識別値を割り当て、演算部がタイルの初期周回回数を演算する一例について説明するための図面である。
【図２７Ａ】演算部が初期周回回数を付与する規則の一例を示す図面である。
【図２７Ｂ】演算部が初期周回回数を付与する規則の一例を示す図面である。
【図２７Ｃ】演算部が初期周回回数を付与する規則の一例を示す図面である。
【図２８Ａ】一実施形態による演算部が，フレームに含まれたタイルのうち、第２経路が通過するタイルの一側方向に並んだタイルの第２初期周回回数を演算する一例について説明するための図面である。
【図２８Ｂ】一実施形態による演算部が，フレームに含まれたタイルのうち、第２経路が通過するタイルの一側方向に並んだタイルの第２初期周回回数を演算する一例について説明するための図面である。
【図２９Ａ】一実施形態による演算部が、２個以上の経路の進行方向を考慮し、初期値を付与する規則の一例を示す図面である。
【図２９Ｂ】一実施形態による演算部が、２個以上の経路の進行方向を考慮し、初期値を付与する規則の一例を示す図面である。
【図２９Ｃ】一実施形態による演算部が、２個以上の経路の進行方向を考慮し、初期値を付与する規則の一例を示す図面である。
【図３０Ａ】一実施形態による演算部が、フレームに含まれたタイルのうち、第３経路が通過するタイルの一側方向に並んだタイルの第３初期回数を演算する一例について説明するための図面である。
【図３０Ｂ】一実施形態による演算部が、フレームに含まれたタイルのうち、第３経路が通過するタイルの一側方向に並んだタイルの第３初期回数を演算する一例について説明するための図面である。
【図３１Ａ】一実施形態による周回回数演算部が、ピクセルの周回回数を演算する一例について説明するための図面である。
【図３１Ｂ】一実施形態による周回回数演算部が、ピクセルの周回回数を演算する一例について説明するための図面である。
【図３１Ｃ】一実施形態による周回回数演算部が、ピクセルの周回回数を演算する一例について説明するための図面である。
【図３２Ａ】一実施形態による周回回数演算部が、ピクセルの周回回数を演算する一例について説明するための図面である。
【図３２Ｂ】一実施形態による周回回数演算部が、ピクセルの周回回数を演算する一例について説明するための図面である。
【図３３Ａ】一実施形態による周回回数演算部が、互いに異なる側面を選択してピクセルの周回回数を演算する一例について説明するための図面である。
【図３３Ｂ】一実施形態による周回回数演算部が、互いに異なる側面を選択してピクセルの周回回数を演算する一例について説明するための図面である。
【図３３Ｃ】一実施形態による周回回数演算部が、互いに異なる側面を選択してピクセルの周回回数を演算する一例について説明するための図面である。
【図３３Ｄ】一実施形態による周回回数演算部が、互いに異なる側面を選択してピクセルの周回回数を演算する一例について説明するための図面である。
【図３４Ａ】一実施形態による周回回数演算部が、経路が通過するタイルに含まれたピクセルの周回回数を演算した結果の例を示す図面である。
【図３４Ｂ】一実施形態による周回回数演算部が、経路が通過するタイルに含まれたピクセルの周回回数を演算した結果の例を示す図面である。
【図３５】一実施形態による周回回数演算部が、タイルの初期周回回数を演算する一例について説明するための図面である。
【図３６Ａ】一実施形態によるピクセルシェーダが、フレームに含まれたピクセルそれぞれに対応するカラーを決定する一例について説明するための図面である。
【図３６Ｂ】一実施形態によるピクセルシェーダが、フレームに含まれたピクセルそれぞれに対応するカラーを決定する一例について説明するための図面である。
【図３６Ｃ】一実施形態によるピクセルシェーダが、フレームに含まれたピクセルそれぞれに対応するカラーを決定する一例について説明するための図面である。
【発明を実施するための形態】
【００１４】
以下、図面を参照し、本発明の実施形態について詳細に説明する。本発明の下記実施形態は、本発明を具体化するためのものであるのみ、本発明の権利範囲を制限したり限定したりするものではない。また、本発明の詳細な説明及び実施形態から、本発明が属する技術分野で当業者が容易に類推することができるものは、本発明の権利範囲に属するものであると解釈される。
【００１５】
図１は、一実施形態によるレンダリング装置の一例を図示した構成図である。図１を参照すれば、レンダリング装置１００は、入力アセンブラ１１０、バーテックスシェーダ１２０、プリミティブアセンブラ１３０、ビニング遂行部１４０、周回回数演算部１５０、レンダ出力部１６０及びバッファ１７０を含む。図１に図示されたレンダリング装置１００には、本実施形態と係わる構成要素だけが図示されている。従って、図１に図示された構成要素以外に、他の汎用的な構成要素がさらに含まれてもよい。
【００１６】
また、図１に図示されたレンダリング装置１００は、一つまたは複数個のプロセッサに該当する。プロセッサは、多数の論理ゲートのアレイによっても具現され、汎用的なマイクロプロセッサと、該マイクロプロセッサで実行されるプログラムが保存されたメモリとの組み合わせによって具現されもする。また、他の形態のハードウェアによっても具現されるということは、本実施形態が属する技術分野で当業者であるならば、理解することができるであろう。例えば、レンダリング装置１００は、グラフィック処理装置（ＧＰＵ）を意味する。
【００１７】
レンダリング装置１００は、経路レンダリングを行う。ここで、経路は、レンダリングの対象を意味する客体を構成する要素であり、エッジ（edge）またはカーブ（curve）を含む。エッジは、互いに異なる２つの頂点（vertex）を連結する線分を意味し、カーブは、複数の頂点を連結する曲線を意味する。ここで、頂点は、経路の開始位置に対応する頂点、または経路の終了位置に対応する頂点を含む。
【００１８】
例えば、客体は、少なくとも１以上の経路が連結されて形成された閉多角形または閉経路を含んでもよい。
【００１９】
レンダリング装置１００は、少なくとも１つの経路を示すコマンドを受信し、コマンドを解釈することにより、フレームに含まれたピクセルそれぞれのカラーを決定する。ここで、レンダリング装置１００がピクセルのカラーを決定するということは、ピクセルにカラーを表示するか否かということを決定するだけではなく、カラーが表示されるピクセルにいかなるカラーを設定するかということを決定することを含むということは言うまでもない。従って、レンダリング装置１００が動作することにより、画面には、客体が出力される。
【００２０】
例えば、フレームに含まれたピクセルのうち、第１ピクセルから第２ピクセルまでのエッジを経路であると仮定すれば、頂点は、フレームにおいて、第１ピクセル及び第２ピクセルそれぞれに対応する地点を意味する。従って、コマンドは、第１ピクセルに対応する第１頂点の座標、第２ピクセルに対応する第２ピクセルの座標、及び第１頂点から第２頂点まで直線を構成せよという内容を含む。従って、コマンドを参照すれば、経路を構成する頂点それぞれの座標に係わる情報だけではなく、経路の方向に係わる情報も把握される。また、コマンドには、それぞれのピクセルに設定されるカラー値に係わる情報も含まれる。
【００２１】
例えば、レンダリング装置１００は、タイル基盤経路レンダリング（tile-based  path  rendering）を行うことができる。ここで、タイル基盤経路レンダリングは、フレームを仮想のタイルに分割し、タイルそれぞれに対して経路レンダリングを行うことを意味する。レンダリング装置１００がタイル基盤経路レンダリングを行うことにより、レンダリングに所要する時間及び電力消費が低減される。
【００２２】
入力アセンブラ１１０は、経路を構成する少なくとも１つの頂点に係わるデータをメモリから読み取り、読み取られたデータをバーテックスシェーダ１２０に伝送する。バーテックスシェーダ１２０は、頂点についてユーザが作成したバーテックスシェーディングコード（vertex  shading  code）を遂行する。ここで、バーテックスシェーディングコードは、前述のコマンドを意味する。言い換えれば、バーテックスシェーダ１２０は、経路を示すコマンドを解釈する。例えば、ＧＰＵのシェーディングコアがバーテックスシェーダ１２０の機能を遂行することができる。
【００２３】
プリミティブアセンブラ１３０は、バーテックスシェーダ１２０を通過した頂点を集めてプリミティブを構成する。ここで、プリミティブは、頂点から構成される経路であり、客体を構成する要素を意味する。一実施形態によるプリミティブは、エッジまたはカーブを含む。
【００２４】
ビニング遂行部１４０は、タイルビニングを行う。具体的には、ビニング遂行部１４０は、経路の形状によって、経路を、第１グループまたは第２グループに分類し、第１グループに含まれた経路と、第２グループに含まれた経路とを区分し、タイルビニングを行う。言い換えれば、ビニング遂行部１４０は、経路がエッジであるか、あるいはカーブであるかということによって区分し、タイルビニングを行う。例えば、ビニング遂行部１４０は、フレームに含まれたタイルに、経路の識別値を割り当てることができる。例えば、ビニング遂行部１４０は、タイルをレンダリングするときに処理しなければならないプリミティブ（エッジまたはカーブ）の名称を含んだリストを、それぞれのタイルごとに生成することができる。以下、エッジの名称を含んだリストを「Edge＿List」とし、カーブの名称を含んだリストを「Curve＿List」とする。
【００２５】
タイルは、フレームに含まれたピクセルのグループを意味する。例えば、フレームに１０２４＊７６８個のピクセルが含まれており、フレームが４個のタイルに分割されると仮定すれば、１つのタイルには、５１２＊３８４個のピクセルが含まれる。
【００２６】
経路の識別値は、経路を指すものであり、既定の名称に該当する。例えば、図４Ａにおいて、第１経路ｅ０に対応する経路の識別値は、「ｅ０」でもある。しかし、特定経路を意味するものであって、事前に約束された情報であるならば、制限なしに識別値に該当する。図２Ａないし図１９、及び図２９Ａないし図３０Ｂを参照し、ビニング遂行部１４０が、タイルに、経路の識別値を割り当てる例について追って説明する。
【００２７】
また、ビニング遂行部１４０は、経路の位置及び進行方向に基づいて、タイルそれぞれの初期周回回数（initial  winding  number）を演算することができる。図２０ないし図２８Ｂを参照し、ビニング遂行部１４０が、経路それぞれの初期周回回数を演算する例について追って説明する。ただし、ビニング遂行部１４０が初期周回回数を演算しないのであるならば、周回回数演算部１５０が初期周回回数を演算することもできる。
【００２８】
周回回数演算部１５０は、経路の位置及び進行方向に基づいて、タイルそれぞれに含まれたピクセルの周回回数を演算することができる。例えば、周回回数演算部１５０は、ハードウェア、またはシェーディングコアで動作するソフトウェアによって具現される。図３１Ａないし図３５を参照し、周回回数演算部１５０がピクセルの周回回数を演算する例について追って説明する。
【００２９】
一方、図１には、周回回数演算部１５０がレンダリング装置１００に含まれているように図示されているが、それに限定されるものではない。言い換えれば、周回回数演算部１５０は、レンダリング装置１００と独立した単一装置にもなる。例えば、独立した周回回数演算部（図示せず）は、レンダリング装置１００から、経路に含まれた頂点それぞれの座標に係わる情報、及びフレームに含まれたピクセルの座標に係わる情報を受信する。そして、独立した周回回数演算部（図示せず）は、受信された情報を利用して、ピクセルの周回回数を演算し、演算された周回回数をレンダリング装置１００に返す。
【００３０】
言い換えれば、ピクセルの周回回数が、レンダリング装置１００に含まれたシェーディングコアで演算されるように具現されもし、レンダリング装置１００と独立したハードウェアで演算されるように具現されもする。
【００３１】
レンダ出力部１６０は、ピクセルシェーダが動作することによって生成されたデータ（例えば、ピクセルのカラーに係わる情報）をバッファ１７０に記録する。言い換えれば、ピクセルシェーダは、フレームに含まれたピクセルそれぞれのカラーを決定し、レンダ出力部１６０は、ピクセルのカラーに係わる情報をマージしてバッファ１７０に記録する。
【００３２】
例えば、ピクセルシェーダは、フレームに含まれたピクセルに係わる情報を受信し、ピクセルそれぞれのカラーを決定することができる。言い換えれば、ピクセルシェーダは、ピクセルそれぞれの周回回数に基づいて、ピクセルのシェーディングを行う。ここで、シェーディングは、ピクセルそれぞれにカラーを設定する過程を意味するが、それに限定されるものではない。例えば、シェーディングは、ピクセルそれぞれに明暗を設定する過程にもなり、ピクセルそれぞれに質感を示す過程にもなる。また、ピクセルシェーダは、テクスチャに基づいて、ピクセルのシェーディングを行うことができる。例えば、ピクセルシェーダは、既設定の規則に基づいて、ピクセルのカラーを決定することができる。図３６Ａ，Ｂ及びＣを参照し、ピクセルシェーダがピクセルのカラーを決定する例についておって説明する。
【００３３】
レンダ出力部１６０は、ピクセルのカラーに係わる情報をバッファ１７０に記録する。
【００３４】
図２Ａは、一実施形態によるビニング遂行部の一例を図示した構成図である。図２Ａを参照すれば、ビニング遂行部１４０は、獲得部１４１及び割当て部１４２を含む。獲得部１４１または割当て部１４２は、一つまたは複数個のプロセッサに該当する。プロセッサは、多数の論理ゲートのアレイによって具現されもし、汎用的なマイクロプロセッサと、該マイクロプロセッサで実行されるプログラムが保存されたメモリとの組み合わせによって具現されもする。また、他の形態のハードウェアによっても具現されるということは、本実施形態が属する技術分野で当業者であるならば、理解することができるであろう。
【００３５】
獲得部１４１は、客体を構成する少なくとも１つの経路に係わる情報を獲得する。ここで、客体は、レンダリングが行われる対象を意味し、少なくとも１つのエッジまたはカーブで構成される。言い換えれば、獲得部１４１は、プリミティブアセンブラ１３０から、経路（エッジまたはカーブ）に係わる情報を獲得する。ここで、経路に係わる情報は、経路の開始地点に該当する頂点の座標、経路の終了地点に該当する頂点の座標、及び経路の進行方向（すなわち、経路が描かれる方向）を含む。
【００３６】
また、獲得部１４１は、経路の形状によって、経路を、第１グループまたは第２グループに分類する。ここで、第１グループは、エッジが含まれたグループを意味し、第２グループは、カーブが含まれたグループを意味する。例えば、獲得部１４１は、経路に係わる情報を利用して、経路それぞれが、第１グループに含まれるか、あるいは第２グループに含まれるということを決定することができる。経路に係わる情報には、経路に含まれた頂点の座標、及び経路の進行方向に係わる情報が含まれている。従って、獲得部１４１は、経路を、第１グループまたは第２グループに分類することができる。以下、図２Ｂを参照し、獲得部１４１が経路を分類する一例について説明する。
【００３７】
図２Ｂは、一実施形態による獲得部が経路を分類する一例を示す図面である。
【００３８】
ビニング遂行部１４０は、プリミティブアセンブラ１３０から経路に係わる情報を獲得する。客体が複数の経路によって構成されていると仮定すれば、ビニング遂行部１４０は、複数の経路に係わる情報を獲得することができる。図２Ｂを参照すれば、ビニング遂行部１４０が７個の経路ｅ０，ｅ１，ｅ２，ｅ３，ｃ０，ｃ１，ｃ２に係わる情報を獲得した一例が図示されている。
【００３９】
獲得部１４１は、それぞれの経路ｅ０，ｅ１，ｅ２，ｅ３，ｃ０，ｃ１，ｃ２を、第１グループ（リストＡ）または第２グループ（リストＢ）に分類する。例えば、獲得部１４１は、エッジ（ｅ０，ｅ１，ｅ２，ｅ３）に係わる情報を組み合わせて第１グループ（リストＡ）を構成し、カーブ（ｃ０，ｃ１，ｃ２）に係わる情報を組み合わせて第２グループ（リストＢ）を構成することができる。
【００４０】
獲得部１４１が経路を分類することにより、ビニング遂行部１４０は、経路の形態によって、タイルビニングを並列して行うことができる。言い換えれば、ビニング遂行部１４０は、エッジｅ０，ｅ１，ｅ２，ｅ３に対するタイルビニングと、カーブｃ０，ｃ１，ｃ２に対するタイルビニングと並列して行うことができる。
【００４１】
図２Ａ及び図２Ｂを参照して説明したところによれば、獲得部１４１が、経路をエッジまたはカーブに分類すると説明したが、それに限定されるものではない。すなわち、プリミティブアセンブラ１３０が、ビニング遂行部１４０に、エッジに係わる情報と、カーブに係わる情報とを区分して伝送することもできる。
【００４２】
再び図２Ａを参照すれば、割当て部１４２は、第１グループに含まれた経路と、第２グループに含まれた経路とを区分し、タイルビニングを行う。
【００４３】
一例として、経路が、第１グループに含まれた経路（エッジ）であると仮定すれば、割当て部１４２は、フレームに含まれたタイルのうち、経路を含むタイルを選択する。そして、割当て部１４２は、選択されたタイル、及び選択されたタイルそれぞれの一側方向に並んだ少なくとも１つのタイルに、経路の識別値を割り当てる。図３ないし図７を参照し、経路がエッジである場合、獲得部１４１及び割当て部１４２が動作する一例について説明する。
【００４４】
他の例として、経路が、第２グループに含まれた経路（カーブ）であると仮定すれば、割当て部１４２は、フレームに含まれたタイルのうち、経路に対応する外郭三角形を含むタイルを選択する。そして、割当て部１４２は、選択されたタイル、及び選択されたタイルそれぞれの一側方向に並んだ少なくとも１つのタイルに、経路の識別値を割り当てる。図８及び図９を参照し、経路がカーブである場合、獲得部１４１及び割当て部１４２が動作する一例について追って説明する。
【００４５】
図３は、一実施形態によるビニング遂行部が遂行する動作の一例を示したフローチャートである。
【００４６】
３１０段階において、獲得部１４１は、客体を構成する経路に係わる情報を獲得する。例えば、獲得部１４１は、プリミティブアセンブラ１３０から、エッジに係わる情報、またはカーブに係わる情報を獲得することができる。また、図３には図示されていないが、獲得部１４１は、経路がエッジであるか、あるいはカーブであるかということにより、経路を、第１グループまたは第２グループに分類することができる。
【００４７】
３２０段階において、割当て部１４２は、フレームに含まれたタイルのうち、経路を含むタイルを選択する。言い換えれば、割当て部１４２は、フレームに含まれたタイルのうち、経路が通過するタイルを選択する。ここで、割当て部１４２によって選択されたタイルには、経路の開始地点を含むタイル、及び経路の終了地点を含むタイルが含まれる。以下、図４Ａないし図５Ｅを参照し、割当て部１４２が、フレームに含まれたタイルのうち、経路を含むタイルを選択する一例について説明する。
【００４８】
図４Ａ及び図４Ｂは、一実施形態による割当て部が、フレームに含まれたタイルのうち、第１経路が通過するタイルを選択する一例について説明するための図面である。
【００４９】
図４Ａには、第１経路ｅ０が図示されている。ここで、第１経路ｅ０は、頂点Ｐ０から頂点Ｐ１まで連結された直線経路である。第１経路ｅ０の左側から、第１経路ｅ０を見ると仮定すれば、第１経路ｅ０は、反時計回り方向に回転する経路であるということが分かる。
【００５０】
図４Ｂには、フレーム４１０に含まれたタイルのうち、第１経路ｅ０が通過するタイル４２０が図示されている。割当て部１４２は、フレーム４１０に含まれたタイルのうち、第１経路ｅ０が通過するタイル４２０を選択する。割当て部１４２が、フレーム４１０に含まれたタイルのうち、第１経路ｅ０が通過するタイル４２０を選択する一例は、図５Ａないし図５Ｅを参照して説明する。
【００５１】
図５Ａないし図５Ｅは、一実施形態による割当て部が、フレームに含まれたタイルのうち、経路が通過するタイルを選択する一例図面である。
【００５２】
割当て部１４２は、フレームに含まれたタイルの一側面と出合う経路上の少なくとも１つの地点を決定する。ここで、タイルの一側面は、タイルの左側、右側、上側及び下側のうちいずれか一つを意味する。言い換えれば、割当て部１４２は、フレームに含まれたタイルの一側外郭線と経路とが出合う地点を決定する。
【００５３】
図５Ａを参照すれば、頂点Ｐ０から頂点Ｐ１まで連結された第１経路ｅ０が図示されている。割当て部１４２は、フレームに含まれたタイルの一側面と出合う経路上の地点を決定する。例えば、タイルの一側面を、右側外郭線５１０であると仮定すれば、割当て部１４２は、第１経路ｅ０が右側外郭線５１０と出合う（又は接触する又は交わる）地点５２１を決定する。
【００５４】
そして、割当て部１４２は、決定された地点５２１を基準に、経路を仮想で分割する。ここで、割当て部１４２が経路を仮想で分割するということは、経路を実際に分割するのではなく、割当て部１４２が、フレームに含まれたタイルのうち、経路が通過するタイルを正確に選択するために、経路の中間地点を計算する過程を意味する。
【００５５】
図５Ｂを参照すれば、割当て部１４２は、第１経路ｅ０を、第１経路ｅ０の開始頂点Ｐ０から、決定された地点５２１までの第１サブ経路ｅ０１と、決定された地点５２１から、第１経路ｅ０の終了頂点Ｐ１までの第２サブ経路ｅ０２とに仮想分割する。
【００５６】
そして、割当て部１４２は、分割された経路を含むタイルを選択する。例えば、割当て部１４２は、分割された経路を対角線にする四角形を構成し、構成された四角形を含むタイルを選択する。図５Ｂを参照すれば、割当て部１４２は、第１サブ経路ｅ０１を対角線にする四角形を構成する。そして、割当て部１４２は、構成された四角形を含むタイル５３１を選択する。
【００５７】
もしフレームに含まれたタイルの一側面と経路とが複数の地点で出合う場合、割当て部１４２は、図５Ａ及び図５Ｂを参照して説明した過程を反復する。
【００５８】
図５Ｃを参照すれば、割当て部１４２は、第１経路ｅ０が、右側外郭線５１０と出合う地点５２２を決定する。
【００５９】
そして、割当て部１４２は、決定された地点５２２を基準に、経路を仮想分割する。図５Ｄを参照すれば、割当て部１４２は、第２サブ経路ｅ０２を、第２サブ経路ｅ０２の開始頂点５２１から、決定された地点５２２までの第３サブ経路ｅ０３と、決定された地点５２２から、第２サブ経路ｅ０２の終了頂点Ｐ１までの第４サブ経路ｅ０４とに分割する。
【００６０】
そして、割当て部１４２は、分割された経路を対角線にする四角形を構成する。そして、割当て部１４２は、構成された四角形を含むタイルを選択する。図５Ｄを参照すれば、割当て部１４２は、第３サブ経路ｅ０３を対角線にする四角形を構成する。そして、割当て部１４２は、構成された四角形を含むタイル５３２を選択する。
【００６１】
フレームに含まれたタイルの一側面と経路とが出合う地点がそれ以上ない場合、割当て部１４２は、第１経路ｅ０が分割された残りのサブ経路を対角線にする四角形を構成し、四角形に含まれたタイルを選択する。図５Ｅを参照すれば、割当て部１４２は、第４サブ経路ｅ０４を対角線にする四角形を構成する。そして、割当て部１４２は、構成された四角形を含むタイル５３３を選択する。
【００６２】
最終的に、割当て部１４２は、選択したタイル５３１，５３２，５３３を組み合わせることにより、フレームに含まれたタイルのうち、第１経路ｅ０が通過するタイル５３１，５３２，５３３を決定することができる。
【００６３】
図５Ａないし図５Ｅを参照して説明したように、割当て部１４２は、経路を少なくとも１つのサブ経路に分割し、サブ経路を含むタイルを選択することにより、フレームに含まれたタイルのうち、第１経路ｅ０が通過するタイル５３１，５３２，５３３を正確に選択することができる。
【００６４】
再び図３を参照すれば、３３０段階において、割当て部１４２は、選択されたタイル、及び選択されたタイルそれぞれの一側方向に並んだ少なくとも１つのタイルに、経路の識別値を割り当てる。言い換えれば、割当て部１４２は、経路が通過するタイルに、経路の識別値を割り当て、経路が通過するタイルそれぞれの一側方向に並んだタイルにも、経路の識別値を割り当てる。ここで、一側方向は、選択されたタイル（すなわち、経路が通過するタイル）それぞれの位置を中心に、左側方向、右側方向、上側方向、下側方向のうちいずれか一つを意味する。
【００６５】
割当て部１４２が、タイルに経路の識別値を割り当てるということは、タイルのEdge＿ListまたはCurve＿Listを生成することを意味する。例えば、割当て部１４２は、図４に図示されたタイル４２０別に、タイルに第１経路ｅ０が通過するという情報をEdge＿Listとして生成し、それをビニング遂行部１４０に含まれたメモリ（図示せず）に保存する。例えば、Edge＿Listは、それぞれのタイル別に、ビットストリーム形態で保存される。また、割当て部１４２は、図４に図示されたタイル４２０の一側方向に並んだタイルに、第１経路ｅ０に係わる情報（例えば、タイル４２０を通過する第１経路ｅ０の名称）を含むEdge＿Listを生成し、それをメモリ（図示せず）に保存する。
【００６６】
図６は、一実施形態による割当て部が、タイルに経路の識別値を割り当てる一規則について説明するための図面である。図６を参照すれば、タイルＡは、経路６１０が通過するタイルを意味し、タイルＢは、経路６２０の開始頂点を含むタイルを意味する。また、タイルＣは、経路６３０の終了頂点を含むタイルを意味する。
【００６７】
割当て部１４２は、フレームに含まれたタイルのうち、タイルＡないしタイルＣに該当するタイルを選択する。そして、割当て部１４２は、タイルＡないしタイルＣに、経路６１０，６２０，６３０が通過するということを意味するEdge＿Listを生成する。また、割当て部１４２は、タイルＡないしタイルＣの一側方向に並んだタイルそれぞれに対して、Edge＿Listを生成する。
【００６８】
図７は、一実施形態による割当て部が、タイルに経路の識別値を割り当てた一例を示す図面である。図７には、フレーム７１０に含まれたタイルのうち、第１経路ｅ０を含むタイル７２０、及びタイル７２０それぞれの一側方向に並んだタイル７３０に、第１経路ｅ０の識別値が割り当てられた一例が図示されている。言い換えれば、図７には、タイル７２０，７３０それぞれに対して、Edge＿Listが生成された一例が図示されている。タイル７２０，７３０それぞれのEdge＿Listには、第１経路の名称であるｅ０が含まれる。
【００６９】
図７において、タイル７２０それぞれの一側方向は、タイル７２０それぞれの左側方向を意味するように図示されている。しかし、一側方向は、前述の左側方向だけではなく、右側方向、上側方向または下側方向にも該当するということは、前述の通りである。
【００７０】
一実施形態によるビニング遂行部１４０は、タイル７２１の一側方向に並んだタイル７３１、及びタイル７２２の一側方向に並んだタイル７３２に対して、Edge＿Listを生成する。従って、レンダリング装置１００が、経路それぞれを、独立して処理（すなわち、経路を並列して処理）することができるが、レンダリング装置１００の動作に所要する時間及びコスト（例えば、電力）が低減される。
【００７１】
一方、客体を構成する経路は、エッジだけでなくカーブも該当する。言い換えれば、獲得部１４１は、カーブに係わる情報を獲得し、割当て部１４２は、フレームに含まれたタイルのうち、一部タイルにカーブの識別値を割り当てることができる（すなわち、Curve＿Listを生成する）。以下、図８及び図９を参照し、割当て部１４２が、タイルにカーブの識別値を割り当てる一例について説明する。
【００７２】
図８は、一実施形態による割当て部が、タイルに経路の識別値を割り当てる他の例を示したフローチャートである。図８の２０２１段階は、図３の３１０段階が遂行された以後に遂行されることを前提する。
【００７３】
２０２１段階において、割当て部１４２は、フレームに含まれたタイルのうち、経路に対応する外郭三角形を含むタイルを選択する。ここで、経路は、カーブを意味し、外郭三角形の内部にカーブが含まれる。
【００７４】
外郭三角形は、３個のエッジに分割される。言い換えれば、外郭三角形は、頂点に対応する頂点を基準に、３個のエッジに分割される。従って、割当て部１４２は、フレームに含まれたタイルのうち、３個のエッジそれぞれを含むタイルを選択することができる。
【００７５】
２０３３段階において、割当て部１４２は、選択されたタイルそれぞれに、経路の識別値を割り当てる。また、２０３４段階において、割当て部１４２は、選択されたタイルそれぞれの一側方向に並んだタイルに、経路の識別値を割り当てる（Curve＿Listを生成する）。ここで、一側方向は、右側方向を意味するが、それに限定されるものではない。
【００７６】
図９は、一実施形態による割当て部が、タイルにカーブの識別値を割り当てる一例について説明するための図面である。図９を参照すれば、フレーム３０１０には、経路Ｃ０が図示されている。このとき、経路Ｃ０は、外郭三角形３０２０内に含まれる。具体的には、経路Ｃ０の開始頂点Ｐ０での勾配に対応するエッジｅ０と、経路Ｃ０の終了頂点Ｐ２での勾配に対応するエッジｅ１とが交差する頂点をＰ１とすれば、外郭三角形３０２０は、Ｐ０、Ｐ１及びＰ２を頂点とする三角形になる。また、外郭三角形３０２０は、エッジｅ０、エッジｅ１及びエッジｅ２から構成された三角形になる。
【００７７】
割当て部１４２は、フレーム３０１０に含まれたタイルのうち、外郭三角形３０２０を含むタイル３０３０を選択する。具体的には、割当て部１４２は、フレーム３０１０に含まれたタイルのうち、エッジｅ０を含むタイル、エッジｅ１を含むタイル、及びエッジｅ２を含むタイルを選択することができる。このとき、割当て部１４２がタイル３０３０を選択する具体的な方法は、図４Ａないし図５をＥ参照して説明した通りである。
【００７８】
割当て部１４２は、選択されたタイル３０３０それぞれに、経路の識別値を割り当てる。例えば、割当て部１４２は、選択されたタイル３０３０別に、Curve＿Listを生成することができる。また、割当て部１４２は、選択されたタイル３０３０の一側方向（例えば、右側方向）に並んだタイルそれぞれにも、経路の識別値を割り当てる。
【００７９】
従って、経路がカーブＣ０である場合、ビニング遂行部１４０は、カーブＣ０を取り囲んでいる外郭三角形３０２０を利用して、タイルビニングを行うことができる。
【００８０】
図２Ａないし図９を参照して説明したところによれば、ビニング遂行部１４０は、客体を構成する経路の種類によって、並列してタイルビニングを行うことができる。言い換えれば、ビニング遂行部１４０は、経路がエッジであるか、あるいはカーブであるかというにより、Edge＿ListとCurve＿Listとをそれぞれ生成することができる。そして、追って説明するように、ビニング遂行部１４０は、経路の種類（エッジまたはカーブ）によって、並列してタイルの初期周回回数を演算することができる。
【００８１】
従って、レンダリング装置１００がレンダリングを行うのに所要する時間が短縮されるだけではなく、レンダリング装置１００が消費する電力の量も減少する。
【００８２】
図１０は、一実施形態によるビニング遂行部の他の例を図示した構成図である。図１０を参照すれば、ビニング遂行部１４０は、獲得部１４１、割当て部１４２及び設定部１４３を含む。設定部１４３は、一つまたは複数個のプロセッサに該当する。プロセッサは、多数の論理ゲートのアレイによって具現されもし、汎用的なマイクロプロセッサと、該マイクロプロセッサで実行されるプログラムが保存されたメモリとの組み合わせによって具現されもする。また、他の形態のハードウェアによっても具現されるということは、本実施形態が属する技術分野で当業者であるならば、理解することができるであろう。
【００８３】
獲得部１４１及び割当て部１４２が動作する一例は、図２Ａないし図７を参照して説明した通りである。従って、以下では、獲得部１４１及び割当て部１４２に係わる具体的な説明を省略する。
【００８４】
設定部１４３は、経路に含まれた頂点それぞれに対応する座標を利用して、フレームに境界ボックスを設定する。ここで、境界ボックスは、客体の最外郭頂点を利用して設定されたボックスを意味する。言い換えれば、設定部１４３は、客体が完全に含まれるように境界ボックスを設定する。
【００８５】
割当て部１４２は、境界ボックス内に含まれたタイルに、経路の識別値を割り当てる。言い換えれば、割当て部１４２は、フレームに含まれたタイルのうち、境界ボックス内に含まれたタイルについてのみ経路の識別値を割り当てる。
【００８６】
以下、図１１ないし図１２Ｂを参照し、設定部１４３が境界ボックスを設定する一例について具体的に説明する。
【００８７】
図１１は、一実施形態によるビニング遂行部が遂行する動作の他の例を示したフローチャートである。図１１の９１０段階ないし９２０段階は、図３の３１０段階ないし３２０段階と同一である。従って、以下では、９１０段階ないし９２０段階についての具体的な説明は省略する。
【００８８】
９３０段階において、設定部１４３は、経路に含まれた頂点それぞれに対応する座標を利用して、フレームに境界ボックスを設定する。例えば、境界ボックスは、頂点の座標のうち、水平方向成分の最大値、及び垂直方向成分の最大値によって形成された第１座標と、水平方向成分の最小値、及び垂直方向成分の最小値によって形成された第２座標と結ぶ線を対角線にする四角形になる。
【００８９】
９４０段階において、割当て部１４２は、境界ボックス内に含まれたタイルに、経路の識別値を割り当てる。ここで、タイルに経路の識別値が割り当てられるということは、タイルに対して、Edge＿ListまたはCurve＿Listが生成されるということを意味する。言い換えれば、割当て部１４２は、図７に図示されたタイル７２０，７３０のうち、境界ボックス内に含まれたタイルについてのみ、Edge＿ListまたはCurve＿Listを生成する。
【００９０】
図１２Ａ及び図１２Ｂは、一実施形態による設定部が境界ボックスを設定し、割当て部が、経路の識別値を割り当てる一例について説明するための図面である。
【００９１】
図１２Ａには、フレーム１０１０内に含まれた三角形の客体１０２０が図示されている。客体１０２０は、第１経路ｅ０、第２経路ｅ１及び第３経路ｅ２によって構成されると仮定する。追って説明する周回回数演算部１５０は、フレーム１０１０に含まれたピクセルそれぞれに対して周回回数を演算する。従って、フレーム１０１０全体領域において、客体１０２０が占める領域が小さい場合、周回回数演算部１５０が、フレーム１０１０に含まれた全てのピクセルに対して周回回数を演算するものではないとしても、経路レンダリングを行うことができる。言い換えれば、周回回数演算部１５０は、客体１０２０から遠く離れた位置のピクセルに対しては、周回回数を演算せず、客体１０２０と隣接した位置のピクセルについてのみ周回回数を演算しても、同一結果を算出することができる。従って、フレーム１０１０に含まれた全てのピクセルに対して周回回数を演算する場合より、速い速度で経路レンダリングが行われる。
【００９２】
設定部１４３は、経路に含まれた頂点それぞれに対応する座標を利用して、フレーム１０１０に境界ボックス１０３０を設定する。例えば、設定部１４３は、客体１０２０に含まれた頂点Ｐ０の座標（ｘ１，ｙ１）、頂点Ｐ１の座標（ｘ２，ｙ２）、及び頂点Ｐ２の座標（ｘ３，ｙ３）を利用して、境界ボックス１０３０を設定することができる。
【００９３】
設定部１４３は、頂点Ｐ０の座標（ｘ１，ｙ１）、頂点Ｐ１の座標（ｘ２，ｙ２）、及び頂点Ｐ２の座標（ｘ３，ｙ３）のうち、水平方向座標成分の最大値及び最小値、垂直方向座標成分の最大値及び最小値を利用して、フレームに境界ボックスを設定することができる。まず、設定部１４３は、頂点のｘ座標成分（ｘ１，ｘ２，ｘ３）のうち、最大値（ｘ３）と最小値（ｘ１）とを選択する。その後、設定部１４３は、頂点のｙ座標成分（ｙ１，ｙ２，ｙ３）のうち、最大値（ｙ２）と最小値（ｙ１）とを選択する。その後、設定部１４３は、ｘ座標成分の最大値と、ｙ座標成分の最大値とによって、第１座標（ｘ３，ｙ２）を形成する。また、設定部１４３は、ｘ座標成分の最小値と、ｙ座標成分の最小値とによって、第２座標（ｘ１，ｙ１）を設定する。その後、設定部１４３は、第１座標（ｘ３，ｙ２）と第２座標（ｘ１，ｙ１）とと結ぶ線を対角線にする四角形を、境界ボックス１０３０として設定する。
【００９４】
図１２Ｂには、境界ボックス１０３０に含まれたタイルについてのみ第１経路ｅ０の識別値が割り当てられた例が図示されている。図１２Ｂには、図示されていないが、第２経路ｅ１及び第３経路ｅ２の識別値も、境界ボックス１０３０に含まれたタイルについてのみ割り当てられる。
【００９５】
図７と比較すれば、図１２Ｂには、第１経路ｅ０を含むタイル１０４０の左側方向に並んだタイルのうち、境界ボックス１０３０内に含まれないタイル１０５０には、Edge＿Listが生成されていない。言い換えれば、割当て部１４２は、境界ボックス１０３０に含まれたタイルについてのみEdge＿Listを生成する。
【００９６】
前述のところによれば、設定部１４３が、経路の識別値が割り当てられなければならない最小のタイルを含む境界ボックスを設定することにより、周回回数演算部１５０は、最小個数のピクセルについてのみ周回回数を演算することができる。従って、レンダリング装置１００は、経路レンダリングをさらに迅速に行うことができる。
【００９７】
図１３は、一実施形態によるビニング遂行部のさらに他の例を図示した構成図である。図１３を参照すれば、ビニング遂行部１４０は、獲得部１４１、割当て部１４２及び除去部１４４を含む。除去部１４４は、一つまたは複数個のプロセッサに該当する。プロセッサは、多数の論理ゲートのアレイによって具現されもし、汎用的なマイクロプロセッサと、該マイクロプロセッサで実行されるプログラムが保存されたメモリとの組み合わせによって具現されもする。また、他の形態のハードウェアによっても具現されるということは、本実施形態が属する技術分野で当業者であるならば、理解することができるであろう。
【００９８】
獲得部１４１及び割当て部１４２が動作する一例は、図２Ａないし図１２Ｂを参照して説明した通りである。従って、以下では、獲得部１４１及び割当て部１４２について具体的な説明を省略する。
【００９９】
除去部１４４は、少なくとも１つの経路を含むタイル間の位置関係によって、識別値が割り当てられたタイルのうち、少なくとも１つのタイルに割り当てられた識別値を除去する。言い換えれば、除去部１４４は、割当て部１４２によって、すでに識別値が割り当てられた一部タイルの識別値を除去する。
【０１００】
以下、図１４ないし図２０を参照し、除去部１４４がタイルに割り当てられた識別値を除去する一例について説明する。
【０１０１】
図１４は、一実施形態によるビニング遂行部が遂行する動作のさらに他の例を示したフローチャートである。図１４の１２１０段階ないし１２３０段階は、図３の３１０段階ないし３３０段階と同一である。従って、以下では、１２１０段階ないし１２３０段階についての具体的な説明は省略する。
【０１０２】
１２４０段階において、除去部１４４は、少なくとも１つの経路を含むタイル間の位置関係によって、識別値が割り当てられたタイルのうち、少なくとも１つのタイルに割り当てられた識別値を除去する。例えば、除去部１４４は、経路が通過するタイルの座標を利用して、識別値が除去されるタイルを決定することができる。
【０１０３】
図１５は、一実施形態による、フレームに含まれたタイルに経路の識別値が割り当てられた一例が図示された図面である。図１５を参照すれば、フレーム１３１０には、三角形の客体１３２０が図示されている。ここで、客体１３２０は、頂点Ｐ０から頂点Ｐ１までのエッジである第１経路ｅ０、頂点Ｐ１から頂点Ｐ２までのエッジである第２経路ｅ１、及び頂点Ｐ２から頂点Ｐ０までのエッジである第３経路ｅ２から構成されると仮定する。
【０１０４】
割当て部１４２は、第１経路ｅ０、第２経路ｅ１及び第３経路ｅ２を含むタイル１３３０、及びタイル１３３０の左側に並んだタイル１３４０，１３５０に、経路の識別値を割り当てる。言い換えれば、割当て部１４２は、タイル１３４０，１３５０それぞれに対してEdge＿Listを生成する。従って、フレーム１３１０に含まれた一部タイルには、１つの経路に係わる情報が含まれたEdge＿Listが生成され、他の一部タイルには、複数の経路に係わる情報が含まれたEdge＿Listが生成される。
【０１０５】
一方、Edge＿Listが生成されたタイル１３３０、１３４０，１３５０のうち一部タイル１３５０は、不要にEdge＿Listが生成されたタイルでもある。レンダリング装置１００によって経路レンダリングが行われれば、客体１３２０内のピクセルについてのみカラーが設定される。言い換えれば、タイル１３５０に含まれたピクセルについては、カラーが設定されない。従って、割当て部１４２が、タイル１３５０に対してEdge＿Listを生成したり、周回回数演算部１５０が、タイル１３５０に対して周回回数を演算したりすることは不要な作業に該当する。従って、除去部１４４が、タイル１３５０に対して生成されたEdge＿Listを除去すれば、レンダリング装置１００の効率がさらに高くなる。
【０１０６】
除去部１４４は、経路ｅ０，ｅ１，ｅ２を含むタイル１３３０の座標を利用して、タイル１３５０に割り当てられた識別値を除去することができる。以下、図１６ないし図２０を参照し、除去部１４４が、タイル１３５０に割り当てられた識別値を除去する例について説明する。
【０１０７】
図１６は、一実施形態による、除去部がタイルに割り当てられた識別値を除去する一例を示したフローチャートである。図１６に図示された１２４１段階ないし１２４３段階は、図１２の１２４０段階について具体的に説明するための段階である。従って、図１６の１２４１段階は、図１２の１２３０段階が遂行された後に遂行されることを前提とする。
【０１０８】
１２４１段階において、除去部１４４は、フレームに含まれたタイルのうち、タイルそれぞれに対応する座標の垂直方向成分が同一であるタイルを選択する。すなわち、除去部１４４によって選択されたタイルは、垂直方向成分が同一であり、水平方向成分だけ異なるタイルに該当する。例えば、除去部１４４は、フレームに含まれたタイルのうち、同一行に含まれたタイルを選択することができる。ただし、座標軸が設定される方向に沿って、同一列に含まれたタイルが選択されもする。
【０１０９】
一方、タイルの座標は、ビニング遂行部１４０によって事前に設定されもする。言い換えれば、フレームが、３６個のタイルに分割されると仮定すれば、ビニング遂行部１４０は、所定のタイルを基準に、３６個のタイルそれぞれに座標を設定することができる。
【０１１０】
１２４２段階において、除去部１４４は、選択されたタイルに含まれた少なくとも１つの経路を含むタイルの水平方向成分を比較することにより、最小水平方向成分を獲得する。１２４１段階において、除去部１４４が同一行に含まれたタイルを選択したと仮定すれば、除去部１４４は、同一行に含まれたタイルのうち、経路が含まれたタイルの水平方向成分を検出することができる。そして、除去部１４４は、検出された水平方向成分を比較することにより、最小水平方向成分を獲得することができる。
【０１１１】
以下、図１７を参照し、除去部１４４が最小水平方向成分を獲得する例について具体的に説明する。
【０１１２】
図１７は、一実施形態による、除去部が最小水平方向成分を獲得する一例について説明するための図面である。図１７には、フレーム１５１０に含まれた客体１５２０の一例が図示されている。ここで、客体１５２０は、頂点Ｐ０から頂点Ｐ１までのエッジである第１経路ｅ０、頂点Ｐ１から頂点Ｐ２までのエッジである第２経路ｅ１、頂点Ｐ２から頂点Ｐ３までのエッジである第３経路ｅ２、及び頂点Ｐ３から頂点Ｐ０までのエッジである第４経路ｅ３から構成されると仮定する。
【０１１３】
また、フレーム１５１０に含まれたタイルそれぞれには、水平方向座標成分及び垂直方向座標成分が事前に設定されていると仮定する。図１７に図示されているように、フレーム１５１０が、６＊６個のタイルから構成されており、ビニング遂行部１４０が、水平方向に０から５まで、垂直方向に０から５までの値を事前に設定したと仮定する。従って、フレーム１５１０に含まれたタイルには、（０，０）ないし（５，５）の座標が設定される。
【０１１４】
また、図１７に図示された水平方向と垂直方向は、互いに反対に設定されてもよい。言い換えれば、図１７の水平方向が垂直方向に、図１７の垂直方向が水平方向に設定されもする。従って、一実施形態による水平方向及び垂直方向は、いずれの方向を基準にするかということによって異なる。
【０１１５】
除去部１４４は、フレーム１５１０に含まれたタイルのうち、座標の垂直方向成分が同一であるタイルを選択する。まず、除去部１４４は、垂直方向成分が０であるタイル１５３０を選択することができる。言い換えれば、除去部１４４は、タイル（０，０）、タイル（１，０）、タイル（２，０）、タイル（３，０）及びタイル（４，０）を選択することができる。
【０１１６】
そして、除去部１４４は、選択されたタイル１５３０のうち、経路ｅ０，ｅ１，ｅ２，ｅ３を含むタイルの水平方向成分を比較する。そして、除去部１４４は、最小水平方向成分を獲得する。最初に、除去部１４４は、タイル１５３０のうち、第１経路ｅ０を含むタイル（４，０）を選択し、最小水平方向成分tile＿ｍｉｎ＿ｘを４に決定する。その後、除去部１４４は、タイル１５３０のうち、第２経路ｅ１を含むタイル（１，０）、タイル（２，０）、タイル（３，０）及びタイル（４，０）を利用して、最小水平方向成分ｘ０を更新する。例えば、第２経路ｅ１を含むタイルの水平方向成分において最小値が１であるので、除去部１４４は、最小水平方向成分ｘ０を、４から１に更新する。その後、除去部１４４は、タイル１５３０のうち、第３経路ｅ２を含むタイル（１，０）及びタイル（２，０）を利用して、最小水平方向成分ｘ０を更新する。例えば、第３経路ｅ２を含むタイルの水平方向成分において最小値が１であるので、除去部１４４は、最小水平方向成分ｘ０を１に維持する。最終的に、除去部１４４は、タイル１５３０の最小水平方向成分ｘ０を１に決定する。
【０１１７】
前述のところと同一方式で、除去部１４４は、座標の垂直方向成分が同一であるタイルそれぞれに対して、最小水平方向成分ｘ１，ｘ２，ｘ３，ｘ４，ｘ５を獲得する。図１５に図示されたところによれば、最小水平方向成分ｘ１は、２にで決まって、最小水平方向成分（ｘ２）は、３で決まって、最小水平方向成分（ｘ３）は、２で決定され、最小水平方向成分ｘ４は、１に決定され、最小水平方向成分ｘ５は、１に決定される。
【０１１８】
再び図１６を参照すれば、１２４３段階において、除去部１４４は、選択されたタイルのうち、最小水平方向成分より小さい水平方向成分を有するタイルに割り当てられた識別値を除去する。ここで、タイルに割り当てられた識別値が除去されるということは、タイルに対して生成されたEdge＿ListまたはCurve＿Listが削除されるということを意味する。
【０１１９】
以下、図１８Ａ及び図１８Ｂを参照し、除去部１４４が、タイルに割り当てられた識別値を除去する例について具体的に説明する。
【０１２０】
図１８Ａ及び図１８Ｂは、一実施形態による除去部が、タイルに割り当てられた識別値を除去する一例について説明するための図面である。
【０１２１】
図１８Ａには、フレーム１６１０に含まれた客体１６２０の一例が図示されている。ここで、客体１６２０は、頂点Ｐ０から頂点Ｐ１までのエッジである第１経路ｅ０、頂点Ｐ１から頂点Ｐ２までのエッジである第２経路ｅ１、及び頂点Ｐ２から頂点Ｐ３までのエッジである第３経路ｅ２から構成されると仮定する。また、図１８Ａには、経路ｅ０，ｅ１，ｅ２を含むタイル１６３０、及びタイル１６３０の左側方向に並んだタイル１６４０，１６５０に対してEdge＿Listが生成された例が図示されている。
【０１２２】
除去部１４４は、座標の垂直方向成分が同一であるタイルのうち、最小水平方向成分より小さい水平方向成分を有するタイルに割り当てられた識別値を除去（すなわち、Edge＿Listを除去）する。
【０１２３】
再び図１７を参照すれば、タイル１５３０の最小水平方向成分ｘ０が１であるので、除去部１４４は、１より小さい水平方向成分を有するタイル（０，０）に割り当てられた識別値を除去する。また、垂直方向成分が１であるタイルの最小水平方向成分ｘ１が２であるので、除去部１４４は、２より小さい水平方向成分を有するタイル（０，１）、タイル（１，１）に割り当てられた識別値を除去する。それと同一方式で、除去部１４４は、タイル（０，２）、タイル（１，２）、タイル（２，２）、タイル（０，３）、タイル（１，３）、タイル（０，４）及びタイル（０，５）に割り当てられた識別値を除去する。
【０１２４】
再び図１８Ａを参照すれば、除去部１４４は、図１５を参照して説明したところと同一方式で、タイル１６５０に対して生成されたEdge＿Listを除去する。具体的には、フレーム１６１０の最初の行に含まれたタイルの最小水平方向成分ｘ０が３であるので、除去部１４４は、タイル（０，０）、タイル（０，１）、タイル（０，２）に生成されたEdge＿Listを除去する。また、フレーム１６１０の２行目に含まれたタイルの最小水平方向成分ｘ１が２であるので、除去部１４４は、タイル（１，０）、タイル（１，１）に生成されたEdge＿Listを除去する。それと同一方式で、除去部１４４は、タイル（２，０）、タイル（２，１）、タイル（３，０）、タイル（３，１）、タイル（４，０）及びタイル（５，０）に生成されたEdge＿Listを除去する。
【０１２５】
図１８Ｂには、除去部１４４がタイルに割り当てられた経路の識別値を除去した結果が図示されている。除去部１４４が、客体１６２０のレンダリングに必要ではないタイルに割り当てられた識別値を除去することにより、客体１６２０のレンダリングに要求される時間及び電力の消耗が低減する。
【０１２６】
一方、除去部１４４が、タイルに割り当てられた識別値を除去する方法は、図１６ないし図１８Ｂを参照して説明した方法に限定されるものではない。客体１６２０の形状によって、除去部１４４が識別値を除去するタイルが異なる。従って、除去部１４４は、座標の水平方向成分が同一であるタイルの最小垂直方向成分を決定し、最小垂直方向成分に基づいて、識別値を除去するタイルを決定することができる。
【０１２７】
以下、図１９及び図２０を参照し、除去部１４４が、タイルに割り当てられた識別値を除去する他の例について説明する。
【０１２８】
図１９は、一実施形態による、除去部がタイルに割り当てられた識別値を除去する他の例を示したフローチャートである。図１９に図示された１２４４段階ないし１２４６段階は、図１４の１２４０段階について具体的に説明するための段階である。従って、図１４の１２３０段階が遂行された後、図１９の１２４４段階が遂行されることを前提とする。
【０１２９】
また、図１９では、図１６の１２４３段階が遂行された後、１２４４段階が遂行されるように図示されているが、それに限定されるものではない。言い換えれば、図１６に図示された段階が遂行されることなしに、図１４の１２３０段階が遂行された後、すぐに図１９に図示された１２４４段階ないし１２４６段階が遂行されもする。
【０１３０】
１２４４段階において、除去部１４４は、フレームに含まれたタイルのうち、タイルそれぞれに対応する座標の水平方向成分が同一であるタイルを選択する。すなわち、除去部１４４によって選択されたタイルは、水平方向成分が同一であり、垂直方向成分だけ異なるタイルに該当する。例えば、除去部１４４は、フレームに含まれたタイルのうち、同一列に含まれたタイルを選択することができる。ただし、座標軸が設定される方向に沿って、同一行に含まれたタイルが選択されもする。
【０１３１】
一方、タイルの座標は、ビニング遂行部１４０によって事前に設定されもする。言い換えれば、フレームが３６個のタイルに分割されると仮定すれば、ビニング遂行部１４０は、所定のタイルを基準に、３６個のタイルそれぞれに座標を設定することができる。
【０１３２】
１２４５段階において、除去部１４４は、選択されたタイルに含まれた少なくとも１つの経路を含むタイルの垂直方向成分を比較することにより、最小垂直方向成分及び最大垂直方向成分を獲得する。１２４４段階において、除去部１４４が、同一列に含まれたタイルを選択したと仮定すれば、除去部１４４は、同一列に含まれたタイルのうち、経路が含まれたタイルの垂直方向成分を検出することができる。そして、除去部１４４は、検出された垂直方向成分を比較することにより、最小垂直方向成分及び最大垂直方向成分を獲得することができる。
【０１３３】
１２４６段階において、除去部１４４は、選択されたタイルのうち、最小垂直方向成分より小さい垂直方向成分を有するタイルに割り当てられた識別値を除去する。また、除去部１４４は、選択されたタイルのうち、最大垂直方向成分より大きい垂直方向成分を有するタイルに割り当てられた識別値を除去する。ここで、タイルに割り当てられた識別値が除去されるということは、タイルに対して生成されたEdge＿ListまたはCurve＿Listが削除されるということを意味する。
【０１３４】
以下、図２０を参照し、除去部１４４がタイルに割り当てられた識別値を除去する具体的に説明する。
【０１３５】
図２０は、一実施形態による、除去部がタイルに割り当てられた識別値を除去する他の例について説明するための図面である。図２０には、フレーム１８１０に含まれた客体１８２０の一例が図示されている。ここで、客体１８２０は、頂点Ｐ０，Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５を順に結ぶエッジから構成されると仮定する。また、図２０には図示されていないが、フレーム１８１０に含まれたタイルそれぞれに対して経路の識別値が割り当てられている（すなわち、Edge＿Listが生成されている）と仮定する。
【０１３６】
また、フレーム１８１０に含まれたタイルそれぞれには、水平方向座標成分及び垂直方向座標成分が事前に設定されていると仮定する。図２０に図示されているように、フレーム１８１０が、６＊６個のタイルから構成されており、ビニング遂行部１４０が、水平方向に０から５まで、垂直方向に０から５までの値を事前に設定したと仮定する。従って、フレーム１８１０に含まれたタイルには、（０，０）ないし（５，５）の座標が設定される。
【０１３７】
また、図２０に図示された水平方向と垂直方向は、互いに反対に設定されてもよい。言い換えれば、図２０の水平方向が垂直方向に、図２０の垂直方向が水平方向に設定されもする。従って、一実施形態による水平方向及び垂直方向は、いずれの方向を基準にするかということによって異なる。
【０１３８】
図１６ないし図１８Ｂを参照して説明したところによれば、除去部１４４は、フレーム１８１０に含まれたタイルのうち一部タイル１８３０に割り当てられた識別値を除去することができる。言い換えれば、除去部１４４は、タイルの座標成分を利用して、最小水平方向成分tile＿ｍｉｎ＿ｘlistを獲得し、最小水平方向成分を利用して、タイル１８３０に割り当てられた識別値を除去することができる。
【０１３９】
除去部１４４は、フレーム１８１０に含まれたタイルのうち、座標の水平方向成分が同一であるタイルを選択する。除去部１４４は、水平方向成分が１であるタイル１８４０を選択することができる。言い換えれば、除去部１４４は、タイル（０，１）、タイル（１，１）、タイル（２，１）、タイル（３，１）及びタイル（４，１）を選択することができる。
【０１４０】
そして、除去部１４４は、選択されたタイル１８４０において、経路ｅ０，ｅ１，ｅ２，ｅ３を含むタイルの垂直方向成分を比較する。そして、除去部１４４は、最小垂直方向成分及び最大垂直方向成分を獲得する。例えば、除去部１４４は、タイル１８４０の最小垂直方向成分を０に、最大垂直方向成分を５に決定することができる。ここで、除去部１４４が、最小垂直方向成分及び最大垂直方向成分を獲得する方法は、図１７を参照して説明した方法が採用される。
【０１４１】
前述のところと同一方式で、除去部１４４は、座標の垂直方向成分が同一であるタイルそれぞれに対して、最小垂直方向成分及び最大垂直方向成分を獲得する。図２０に図示されたところによれば、３列目に対する最小垂直方向成分は、０に、最大垂直方向成分は、４に決定される。また、４列目に対する最小垂直方向成分は、１に、最大垂直方向成分は、４に決定され、５列目に対する最小垂直方向成分は、０に、最大垂直方向成分は、５に決定され、６列目に対する最小垂直方向成分は、４に、最大垂直方向成分は、５に決定される。
【０１４２】
除去部１４４は、座標の水平方向成分が同一であるタイルから、最小垂直方向成分より小さい垂直方向成分を有するタイルに割り当てられた識別値を除去（すなわち、Edge＿Listを除去）する。また、除去部１４４は、座標の水平方向成分が同一であるタイルから、最大垂直方向成分より大きい垂直方向成分を有するタイルに割り当てられた識別値を除去（すなわち、Edge＿Listを除去）する。例えば、タイル１８５０の最小垂直方向成分が１であるので、除去部１４４は、１より小さい垂直方向成分を有するタイル（０，３）に割り当てられた識別値を除去する。また、タイル１８５０の最大垂直方向成分が４であるので、除去部１４４は、４より大きい垂直方向成分を有するタイル（５，３）に割り当てられた識別値を除去する。
【０１４３】
前述の方式によれば、除去部１４４は、タイル（５，２）、タイル（０，３）及びタイル（５，３）に割り当てられた識別値を除去することができる。従って、レンダリング装置１００は、客体１８２０のレンダリングをさらに効率的に行うことができる。
【０１４４】
一方、設定部１４３が、フレームに境界ボックスを設定することができるということは、図１０ないし図１２Ｂを参照して説明した通りである。もしフレームに境界ボックスが設定されている場合、除去部１４４は、境界ボックス内に含まれたタイルについてのみ識別値を除去することもできる。
【０１４５】
図２１Ａ及び図２１Ｂは、一実施形態による、フレームに境界ボックスが設定された場合、除去部が動作する一例について説明するための図面である。
【０１４６】
図２１Ａを参照すれば、フレーム１９１０に客体１９２０が図示されており、客体１９２０の外郭には、境界ボックス１９３０が設定されている。設定部１４３は、客体１９２０に含まれた頂点Ｐ０，Ｐ１，Ｐ２に対応する座標を利用して、フレーム１９１０に境界ボックス１９３０を設定することができる。また、割当て部１４２は、フレーム１９１０に含まれたタイルのうち、境界ボックス１９３０内に含まれたタイルについてのみ経路の識別値を割り当てる。図２１Ａには、境界ボックス１９３０内に含まれたタイルに対してEdge＿Listが生成された例が図示されている。
【０１４７】
除去部１４４は、識別値が割り当てられたタイルのうち一部タイルに割り当てられた識別値を除去することができる。例えば、除去部１４４は、図１３ないし図２０を参照して説明した方法によって、最小水平方向成分tile＿ｍｉｎ＿ｘlistを獲得し、最小水平方向成分を利用して、不要に割り当てられた識別値を除去する。
【０１４８】
図２１Ｂを参照すれば、除去部１４４が、一部タイルに割り当てられた識別値を除去した結果が図示されている。図２１Ａ及び図２１Ｂを比較すれば、除去部１４４は、タイル１９４０に割り当てられた識別値を除去することができる。このとき、除去部１４４が、タイル１９４０に割り当てられた識別値を除去する具体的な方法は、図１３ないし図２０を参照して説明した通りである。従って、以下では、具体的な説明を省略する。
【０１４９】
図２２は、一実施形態による、ビニング遂行部のさらに他の例を図示した構成図である。図２２を参照すれば、ビニング遂行部１４０は、獲得部１４１、割当て部１４２及び演算部１４５を含む。演算部１４５は、一つまたは複数個のプロセッサに該当する。プロセッサは、多数の論理ゲートのアレイによって具現されもし、汎用的なマイクロプロセッサと、該マイクロプロセッサで実行されるプログラムが保存されたメモリとの組み合わせによって具現されもする。また、他の形態のハードウェアによっても具現されるということは、本実施形態が属する技術分野で当業者であるならば、理解することができるであろう。
【０１５０】
獲得部１４１及び割当て部１４２が動作する一例は、図２Ａないし図２１Ｂを参照して説明した通りである。従って、以下では、獲得部１４１及び割当て部１４２について具体的な説明を省略する。
【０１５１】
演算部１４５は、経路を含むタイルのうちから選択された第３タイルの一側方向に並んだ少なくとも１つのタイルの初期周回回数（initial  winding  number）を演算する。ここで、第３タイルは、経路を含むタイルのうち、経路の開始頂点を含む第１タイル、及び経路の終了頂点を含む第２タイルが除かれたタイルを意味する。
【０１５２】
タイルに係わる初期周回回数は、そのタイルに、経路の識別値が割り当てられて（タイルのEdge＿ListまたはCurve＿Listが生成されて）こそ演算される。しかし、一般的には、経路の開始頂点が含まれたタイル７２１（図７）の一側方向に並んだタイル７３１（図７）、及び経路の終了頂点が含まれたタイル７２２（図７）の一側方向に並んだタイル７３２（図７）については、識別値が割り当てられない。
【０１５３】
客体が、複数の経路が組み合わされた閉多角形であり、第１経路と第２経路とが連結されている場合、第１経路の終了頂点は、第２経路の開始頂点になる。すなわち、第１経路の終了頂点を含むタイルと、第２経路の開始頂点を含むタイルは、同一である。従って、一般的には、タイル７３２（図７）の初期周回回数は、第１経路だけではなく、第２経路に対する処理が終わった後には、演算が可能である。従って、経路それぞれが独立して処理されず、経路の処理において、従属性が生じるという問題が発生する。
【０１５４】
一実施形態による割当て部１４２は、タイル７２１（図７）の一側方向に並んだタイル７３１（図７）、及びタイル７２２（図７）の一側方向に並んだタイル７３２（図７）についても、経路の識別値を割り当てる。従って、演算部１４５は、経路それぞれに対して独立してタイルに係わる初期周回回数を演算することができる。すなわち、レンダリング装置１００が、経路それぞれを独立して処理（すなわち、経路を並列して処理）することができるが、レンダリング装置１００の動作に所要する時間及びコスト（例えば、電力）が低減する。
【０１５５】
以下、図２３ないし図３０Ｂを参照し、演算部１４５が、タイルの初期周回回数を演算する一例について説明する。
【０１５６】
図２３は、一実施形態による、ビニング遂行部が遂行する動作のさらに他の例を示したフローチャートである。図２３の２０１０段階ないし２０３０段階は、図３の３１０段階ないし３３０段階と同一である。従って、以下では、２０１０段階ないし２０３０段階についての具体的な説明は省略する。
【０１５７】
２０４０段階において、演算部１４５は、少なくとも１つの経路を含むタイルのうちから選択された第３タイルの一側方向に並んだタイルの初期周回回数を演算する。例えば、演算部１４５は、経路が第３タイルを通過する形態に基づいて、第３タイルの一側方向に並んだタイルの初期周回回数を演算することができる。具体的には、演算部１４５は、経路が第３タイルを通過する方向に基づいて、初期周回回数を演算することができる。
【０１５８】
ここで、初期周回回数は、周回回数演算部１５０がタイルの周回回数を演算するのに利用される初期値を意味する。以下、図２４Ａ及び図２４Ｂを参照し、周回回数について詳細に説明する。
【０１５９】
図２４Ａ及び図２４Ｂは、一実施形態による周回回数について説明するための図面である。
【０１６０】
図２４Ａ及び図２４Ｂには、フレーム２２１０に含まれたピクセルのうちいずれか１つのピクセルＰに対応する周回回数について説明するための一例が図示されている。図２４Ａでは、説明の便宜のために、ピクセルＰを、一側方向（例えば、右側方向）を見ている人の形状で図示した。
【０１６１】
図２４Ａを参照すれば、ピクセルＰの周辺に沿って、経路２２３０が図示されており、経路２２３０は、閉経路であるように図示されている。図２４Ａには、ピクセルＰの周回回数が、ピクセルＰの右側に存在する経路２２３０上の頂点２２３１，２２３２，２２３３，２２３４に基づいて演算されるように図示されているが、必ずしも右側に限定されるものではない。また、以下、ピクセルＰの右側は、ピクセルＰから右側水平方向に引かれた仮想の半直線２２２０上の頂点を意味する。
【０１６２】
ピクセルＰから右側水平方向に仮想の線２２２０を図示すれば、仮想の半直線２２２０と経路２２３０は、総４個の頂点２２３１，２２３２，２２３３，２２３４で交差する。言い換えれば、経路２２３０は、４個の頂点２２３１，２２３２，２２３３，２２３４を含むように描かれる。従って、ピクセルＰの周回回数は、４個の頂点２２３１，２２３２，２２３３，２２３４それぞれでの経路が描かれる方向に基づいて決定される。
【０１６３】
具体的には、第１頂点２２３１において経路２２３０が描かれる方向は、反時計回り方向（すなわち、経路２２３０が下から上に描かれる）に該当する。従って、一次的に、ピクセルＰの周回回数は、−１になる。そして、第２頂点２２３２において経路２２３０が描かれる方向は、時計回り方向（すなわち、経路２２３０が上から下に描かれる）に該当する。従って、二次的に、ピクセルＰの周回回数は、−１＋１＝０と演算される。そして、第３頂点２２３３において経路２２３０が描かれる方向は、反時計回り方向に該当する。従って、三次的にピクセルＰの周回回数は、−１＋１−１＝−１と演算される。そして、第４頂点２２３４において経路２２３０が描かれる方向は、反時計回り方向に該当する。従って、最終的に、ピクセルＰの周回回数は、−１＋１−１−１＝−２と演算される。
【０１６４】
図２４Ｂを参照すれば、ピクセルＰの周辺に沿って５個の経路が位置し、経路は、星状の客体２２４０を構成する。具体的には、頂点１から頂点２までのエッジｅ０、頂点２から頂点３までのエッジｅ１、頂点３から頂点４までのエッジｅ２、頂点４から頂点５までのエッジｅ３、及び頂点５から頂点１までのエッジｅ４が組み合わせされ、星状の客体２２４０が構成されている。
【０１６５】
図２４Ａを参照して説明したように、図２４Ｂに図示されたピクセルＰの周回回数は、ピクセルＰの右側水平方向に引いた仮想の線２２５０と経路とが交差する頂点２２６１，２２６２それぞれでの経路が描かれる方向に基づいて演算される。
【０１６６】
従って、経路によって区分された領域２２７１，２２７２，２２７３，２２７４，２２７５内のピクセルの周回回数は、＋１と、領域２２７６内のピクセルの周回回数は、＋２と演算される。また、フレーム２２１０に含まれたピクセルのうち、前述の領域２２７１ないし２２７６に含まれていないピクセル（すなわち、客体２２４０の内部に含まれていないピクセル）の周回回数は、０と演算される。
【０１６７】
図２４Ａ及び図２４Ｂを参照して説明したところによれば、ピクセルＰの周回回数は、ピクセルＰの右側に位置した経路を考慮して演算されるように記載されているが、それに限定されるものではない。言い換えれば、周回回数演算部１５０は、ピクセルＰの位置を中心に、左側、右側、上側及び下側のうちいずれか一つに位置した経路を考慮し、ピクセルＰの周回回数を演算することができる。このとき、周回回数演算部１５０は、ステンシルバッファを利用せずに、ピクセルＰの周回回数を演算することができる。
【０１６８】
また、一実施形態による周回回数演算部１５０は、複数のスレッドを利用して周回回数を演算する。単一スレッドは、単一ピクセルの周回回数が演算されるのに利用される。このとき、複数のスレッドは、並列して処理が行われるので、周回回数演算部１５０は、複数のスレッドを利用して、複数のピクセルそれぞれに対する周回回数を同時に演算することができる。従って、レンダリング装置１００は、高速で経路レンダリングを行うことができる。
【０１６９】
図２５は、一実施形態による、割当て部が、タイルに、経路の識別値を割り当て、演算部が、タイルの初期周回回数を演算する一例を示したフローチャートである。図２５に図示された２０３１段階ないし２０４２段階は、図２３の２０３０段階及び２０４０段階について具体的に説明するための段階である。従って、図２５の２０３１段階は、図２３の２０２０段階が遂行された後に遂行されることを前提とする。
【０１７０】
２０３１段階において、割当て部１４２は、選択されたタイルそれぞれに、経路の識別値を割り当てる。言い換えれば、割当て部１４２は、経路が通過するタイルそれぞれに、経路の識別値を割り当てる（すなわち、Edge＿ListまたはCurve＿Listを生成する）。
【０１７１】
２０３２段階において、割当て部１４２は、選択されたタイルそれぞれの左側方向に並んだタイルに、経路の識別値を割り当てる。言い換えれば、割当て部１４２は、経路が通過するタイルそれぞれの左側方向に並んだタイルに、経路の識別値を割り当てる。
【０１７２】
２０４１段階において、演算部１４５は、選択されたタイルのうち、経路の開始頂点が含まれたタイル、及び経路の終了頂点が含まれたタイルを除くことにより、第３タイルを選択する。例えば、経路が,タイルＸ、タイルＹ、タイルＺ及びタイルＷにわたって存在し、前記経路が、タイルＸに含まれた頂点Ｐ０から、タイルＷに含まれた頂点Ｐ１までのエッジであると仮定すれば、演算部１４５は、タイルＹ及びタイルＺを、第３タイルと決定する。
【０１７３】
２０４２段階において、演算部１４５は、第３タイルの左側方向に並んだタイルの初期周回回数を演算する。前述の例において、演算部１４５は、タイルＹの左側方向に並んだタイル、及びタイルＺの左側方向に並んだタイルの周回回数を演算する。一方、演算部１４５が、第３タイルの左側方向に並んだタイルの初期周回回数を演算すると説明したが、それに限定されるものではない。言い換えれば、演算部１４５が、フレームに含まれた全てのタイルに対して、同一方向に周回回数を演算するならば、その方向は、いかなる方向でもよい。
【０１７４】
演算部１４５は、経路が第３タイルを通過する方向に沿って、所定の値を加算または減算することにより、第３タイルの左側方向に並んだタイルの初期回数を演算することができる。また、第３タイルには、経路の開始頂点が含まれたタイル、及び経路の終了頂点の含まれたタイルが除かれる。従って、経路が通過するタイル（前述の例において、タイルＹ及びタイルＺ）の左側方向に並んだタイルには、Edge＿Listが生成されるだけではなく、初期周回回数も演算される。一方、経路の開始頂点が含まれたタイル（前述の例において、タイルＸ）の左側方向に並んだタイルには、Edge＿Listのみ生成される。また、経路の終了頂点が含まれたタイル（前述の例で、タイルＷ）の左側方向に並んだタイルにも、Edge＿Listのみ生成される。以下、図２６を参照し、前述の内容について具体的に説明する。
【０１７５】
図２６は、割当て部が、タイルに、経路の識別値を割り当て、演算部が、タイルの初期周回回数を演算する一例について説明するための図面である。
【０１７６】
演算部１４５は、経路の進行方向に対応する所定の規則により、タイルの初期周回回数を演算することができる。
【０１７７】
一例として、演算部１４５は、経路がタイルの対向する２本の境界線を時計回り方向に通過する場合、所定の値を加算することにより、初期周回回数を演算し、経路がタイルの対向する２本の境界線を反時計回り方向に通過する場合、所定の値を減算することにより、初期周回回数を演算することができる。
【０１７８】
他の例として、演算部１４５は、経路がタイルの対向する２本の境界線を時計回り方向に通過する場合、所定の値を減算することにより、初期周回回数を演算し、経路がタイルの対向する２本の境界線を反時計回り方向に通過する場合、所定の値を加算することにより、初期周回回数を演算することができる。ここで、所定の値は、１にもなるが、それに制限されるものではない。言い換えれば、所定の値は、経路の進行方向に沿って、既定の数であるならば、制限なしに該当する。
【０１７９】
図２６を参照すれば、経路２４１０は、タイルＡを上から下に通過する。言い換えれば、経路２４１０は、タイルＡを時計回り方向に通過する。演算部１４５は、経路２４１０がタイルＡを時計回り方向に通過すると認識し、タイルＡの左側に並んだタイルの初期周回回数を＋１と決定する。また、割当て部１４２は、タイルＡ、及びタイルＡの左側に並んだタイルに、経路２４１０の識別値を割り当てる（Edge＿Listを生成）。
【０１８０】
一方、経路２４２０は、タイルＢを下から上に通過する。言い換えれば、経路２４２０は、タイルＢを反時計回り方向に通過する。演算部１４５は、経路２４２０がタイルＢを反時計回り方向に通過すると認識し、タイルＢの左側に並んだタイルの初期周回回数を−１と決定する。また、割当て部１４２は、タイルＢ、及びタイルＢの左側に並んだタイルに、経路２４２０の識別値を割り当てる。
【０１８１】
一方、経路２４３０，２４４０は、タイルＣを通過しない。具体的には、経路２４３０は、タイルＣに含まれた頂点から始まる経路であり、経路２４４０は、タイルＣに含まれた頂点で終わる経路である。従って、演算部１４５は、タイルＣの左側に並んだタイルに係わる初期周回回数を演算しない。ただし、割当て部１４２は、タイルＣ、及びタイルＣの左側に並んだタイルに経路２４３０，２４４０の識別値を割り当てる。
【０１８２】
図２６には、タイルＡ、タイルＢ及びタイルＣに１つの経路だけ含まれていると仮定して説明した。もしタイルＡ、タイルＢ及びタイルＣに、複数の経路が含まれている場合、演算部１４５及び割当て部１４２は、それぞれの経路に対して、個別的に前述の方法を遂行する。例えば、タイルＡを時計回り方向に通過する２個の経路が存在するならば、演算部１４５は、タイルＡの左側に並んだタイルの初期周回回数を＋２と決定する。また、割当て部１４２も、タイルＡ、及びタイルＡの左側に並んだタイルに、２個の経路いずれの識別値も割り当てる。
【０１８３】
以下、図２７Ａないし図２７Ｃを参照し、演算部１４５が、タイルの初期周回回数を演算する例について具体的に説明する。
【０１８４】
図２７Ａないし図２７Ｃは、演算部が、初期周回回数を付与する規則の一例を示す図面である。
【０１８５】
図２７Ａは、経路２５１１が、タイル２５２１の対向する２本の境界線を、時計回り方向に（すなわち、上から下に）通過する場合を示し、図２７Ｂは、経路２５１２が、タイル２５２２）の対向する２本の境界線を、反時計回り方向に（すなわち、下から上に）通過する場合を示す。図２７Ｃは、経路２５１３がタイル２５２３の一境界線に入って出る場合を示す。
【０１８６】
図２７Ａないし図２７Ｃに図示されたタイル２５２１，２５２２，２５２３は、２以上のタイルが結合されたタイルにもなる。例えば、経路が通過するタイルが、水平方向に２以上連続する場合、図２７Ａないし図２７Ｃに図示された１つのタイル２５２１，２５２２，２５２３と見なされる。
【０１８７】
図２７Ａを参照すれば、経路２５１１が、タイル２５２１の対向する２本の境界線を時計回り方向に（すなわち、上から下に）通過する場合、演算部１４５は、タイル２５２１の左側に位置する少なくとも１つのタイル２５３１に＋１を、初期周回回数として付与する。すなわち、演算部１４５は、タイル２５２１の左側に位置する少なくとも１つのタイル２５３１の初期周回回数ＷＮｉｎｉｔにおいて１を増加させる。
【０１８８】
図２７Ｂを参照すれば、経路２５１２がタイル２５２２の対向する２本の境界線を反時計回り方向に（すなわち、下から上に）通過する場合、演算部１４５は、タイル２５２２の左側に位置する少なくとも１つのタイル２５３２に、−１を初期周回回数として付与する。すなわち、演算部１４５は、タイル２５２２の左側に位置する少なくとも１つのタイル２５３２の初期周回回数ＷＮｉｎｉｔにおいて１を減少させる。
【０１８９】
図２７Ｃを参照すれば、経路２５１３がタイル２５２３の一境界線に入って出て行く場合、演算部１４５は、タイル２５２３の左側に位置する少なくとも１つのタイル２５３３に０を初期周回回数として付与する。すなわち、演算部１４５は、タイル２５２３の左側に位置する少なくとも１つのタイル２５３３の初期周回回数ＷＮｉｎｉｔに何らの演算も行わない。
【０１９０】
図２７Ａないし図２７Ｃは、経路がタイルを時計回り方向に通過する場合、演算部１４５が＋１を初期周回回数として付与（初期周回回数に１を増加）し、反時計回り方向に通過する場合、演算部１４５が−１を初期周回回数として付与（初期周回回数に１を減少）すると説明したが、それに限定されるものではない。一例として、経路がタイルを時計回り方向に通過する場合、演算部１４５が−１を初期周回回数として付与し、反時計回り方向に通過する場合、演算部１４５が＋１を初期周回回数として付与することもできる。他の例として、経路がタイルを時計回り方向に通過する場合、演算部１４５が＋０．５を初期周回回数として付与（初期周回回数に０．５を増加）し、反時計回り方向に通過する場合、演算部１４５が−０．５を初期周回回数として付与（初期周回回数に０．５を減少）することもできる。
【０１９１】
一方、客体が複数の経路を含む場合、演算部１４５は、それぞれの経路に基づいて、タイルの初期周回回数を演算することができる。言い換えれば、演算部１４５は、複数の経路を順次に考慮し、タイルの初期周回回数を演算することができる。例えば、演算部１４５が、第１経路ｅ０の位置及び進行方向に基づいて、第１初期周回回数ＷＮｉｎｉｔ＿１を設定し、その後、演算部１４５は、第２経路ｅ１の位置及び進行方向に基づいて、第２初期値ＷＮｉｎｉｔ＿２を設定することができる。
【０１９２】
以下、図２８Ａないし図２９Ｃを参照し、複数の経路それぞれに対して、演算部１４５がタイルの初期周回回数を演算する一例について説明する。
【０１９３】
図２８Ａ及び図２８Ｂは、一実施形態による、演算部がフレームに含まれたタイルのうち、第２経路が通過するタイルの一側方向に並んだタイルの第２初期周回回数を演算する一例について説明するための図面である。
【０１９４】
図２８Ａには、第２経路ｅ１が図示されている。第２経路ｅ１は、フレーム２６１０に、第１経路ｅ０が描かれた以後に描かれる経路であると仮定する。このとき、第１経路ｅ０は、頂点Ｐ０から頂点Ｐ１まで連結されたエッジであると仮定する。また、第２経路ｅ１は、頂点Ｐ１から頂点Ｐ２まで連結されたエッジである。従って、第２経路ｅ１は、時計回り方向に進む経路であるということが分かる。
【０１９５】
割当て部１４２は、フレーム２６１０に含まれたタイルのうち、第２経路ｅ１が通過するタイル２６２０を選択する。そして、割当て部１４２は、選択されたタイル２６２０別にタイルに、第２経路ｅ１が通過するという情報をEdge＿Listとして生成し、それをメモリ（図示せず）に保存する。もしEdge＿Listがすでに生成されたタイルである場合には、割当て部１４２は、既生成のEdge＿Listに、第２経路ｅ１が通過するという情報を追加して保存する。図２８Ｂに図示されたタイル２６２０に表示された「ｅ０，ｅ１」または「ｅ１」は、タイル２６２０それぞれのEdge＿Listに含まれた情報を意味する。すなわち、「ｅ０，ｅ１」が表示されたタイルは、第１経路ｅ０が通過するタイルでありながら、第２経路ｅ１が通過するタイルを意味する。また、「ｅ１」が表示されたタイルは、第２経路ｅ１が通過するタイルを意味する。
【０１９６】
そして、演算部１４５は、選択されたタイル２６２０の一側面に位置するタイル２６３１それぞれに、第２初期周回回数ＷＮｉｎｉｔ＿２を付与する。例えば、演算部１４５は、選択されたタイル２６２０の左側方向のタイル２６３１それぞれに、第２初期周回回数ＷＮｉｎｉｔ＿２を付与することができる。すなわち、第２経路ｅ１が時計回り方向にタイル２６２０を通過するので、演算部１４５は、タイル２６３１それぞれに、＋１を第２初期周回回数ＷＮｉｎｉｔ＿２として付与する。そして、演算部１４５は、第２初期周回回数ＷＮｉｎｉｔ＿２を、それぞれのタイル別にメモリ（図示せず）に保存することができる。
【０１９７】
演算部１４５は、第２経路ｅ１の終了頂点Ｐ２を含むタイルの左側方向に位置したタイル２６３２については、第２初期周回回数ＷＮｉｎｉｔ＿２を付与しない。演算部１４５は、第２経路ｅ１及び第３経路ｅ２がタイルを通過する形態を考慮し、第２初期周回回数ＷＮｉｎｉｔ＿２が付与されていないタイル２６３２に対して、第３初期周回回数ＷＮｉｎｉｔ＿３を付与する。
【０１９８】
一方、第２経路ｅ１の開始頂点Ｐ１を含むタイルの左側方向に位置したタイル２６３３の場合、演算部１４５は、第１経路ｅ０及び第２経路ｅ１がタイルを通過する形態を考慮し、第２初期周回回数ＷＮｉｎｉｔ＿２を付与する。以下、図２９Ａないし図２９Ｃを参照し、演算部１４５が、タイル２６３３それぞれに、第２初期周回回数ＷＮｉｎｉｔ＿２を付与する一例について説明する。
【０１９９】
図２９Ａないし図２９Ｃは、一実施形態による、演算部が２個以上の経路の進行方向を考慮し、初期値を付与する規則の一例を示す図面である。
【０２００】
図２９Ａは、経路２７１１が、タイル２７２１の一境界線から入って出て行く場合を示し、図２９Ｂは、経路２７１２が、タイル２７２２の対向する２本の境界線を反時計回り方向に（すなわち、下から上に）通過する場合を示す。図２９Ｃは、経路２７１３が、タイル２７２３の対向する２本の境界線を時計回り方向に（すなわち、上から下に）通過する場合を示す。
【０２０１】
図２９Ａないし図２９Ｃに図示された経路２７１１，２７１２，２７１３は、２以上の経路が結合された経路にもなる。例えば、第１経路の終了頂点と、第２経路の開始頂点とが同一である頂点である場合、図２７Ａないし図２７Ｃに図示された経路２７１１，２７１２，２７１３は、第１経路と第２経路とが連結された１つの経路を意味する。
【０２０２】
また、図２９Ａないし図２９Ｃに図示されたタイル２７２１，２７２２，２７２３は、２以上のタイルが結合されたタイルにもなる。例えば、経路が通過するタイルが、水平方向に２以上連続する場合、図２９Ａないし図２９Ｃに図示された１つのタイル２７２１，２７２２，２７２３と見なされる。
【０２０３】
図２９Ａを参照すれば、経路２７１１が、タイル２７２１の一境界線から入っていて同じ方向に出て行く場合、演算部１４５は、タイル２７２１の左側に位置する少なくとも１つのタイル２７３１に、０を初期周回回数として付与する。
【０２０４】
図２９Ｂを参照すれば、経路２７１２が、タイル２７２２の対向する２本の境界線を反時計回り方向に（すなわち、下から上に）通過する場合、演算部１４５は、タイル２７２２の左側に位置する少なくとも１つのタイル２７３２に、−１を初期周回回数として付与する。
【０２０５】
図２９Ｃを参照すれば、経路２７１３が、タイル２７２３の対向する２本の境界線を時計回り方向に（すなわち、上から下に）通過する場合、演算部１４５は、タイル２７２３の左側に位置する少なくとも１つのタイル２７３３に、＋１を初期周回回数として付与する。
【０２０６】
図２９Ａないし図２９Ｃは、経路がタイルを時計回り方向に通過する場合、演算部１４５が＋１を初期周回回数として付与し、反時計回り方向に通過する場合、演算部１４５が−１を初期周回回数として付与すると説明したが、それに限定されるものではない。
【０２０７】
一例として、経路がタイルを時計回り方向に通過する場合、演算部１４５が−１を初期周回回数として付与し、反時計回り方向に通過する場合、演算部１４５が＋１を初期周回回数として付与することもできる。他の例として、経路がタイルを時計回り方向に通過する場合、演算部１４５が＋０．５を初期周回回数として付与し、反時計回り方向に通過する場合、演算部１４５が−０．５を初期周回回数として付与することもできる。
【０２０８】
再び図２８Ａを参照すれば、第１経路ｅ０と第２経路ｅ１とが連結された経路は、頂点Ｐ１を含むタイルの下側面から入り、下側面に出て行く。従って、演算部１４５は、タイル２６３３それぞれの第２初期周回回数ＷＮｉｎｉｔ＿２として０を付与する。
【０２０９】
図２８Ｂには、第１初期周回回数ＷＮｉｎｉｔ＿１及び第２初期周回回数ＷＮｉｎｉｔ＿２が合算された結果が図示されている。例えば、第１初期周回回数ＷＮｉｎｉｔ＿１または第２初期周回回数ＷＮｉｎｉｔ＿２は、メモリ（図示せず）に、それぞれのタイル別にビットストリーム形態で保存される。従って、第１初期周回回数ＷＮｉｎｉｔ＿１及び第２初期周回回数ＷＮｉｎｉｔ＿２がいずれも付与されたタイルに対して、演算部１４５は、第１初期周回回数ＷＮｉｎｉｔ＿１と第２初期周回回数ＷＮｉｎｉｔ＿２とを合算することができる。
【０２１０】
図２８Ａを参照して説明したところによれば、図２８Ｂに図示された一部タイル２６４１は、第１初期周回回数ＷＮｉｎｉｔ＿１（例えば、−１）のみ有する。また、図２８Ｂに図示された一部タイル２６４２は、第２初期周回回数ＷＮｉｎｉｔ＿２（例えば、０または＋１）のみ有する。また、図２８Ｂに図示された一部タイル２６４３は、第１初期周回回数ＷＮｉｎｉｔ＿１（例えば、−１）及び第２初期周回回数ＷＮｉｎｉｔ＿２（例えば、＋１）をいずれも有する。従って、演算部１４５は、図２８Ｂに図示された一部タイル２６４３それぞれに対して、第１初期周回回数ＷＮｉｎｉｔ＿１と第２初期周回回数ＷＮｉｎｉｔ＿２とを合算（例えば、−１＋１＝０）することができる。
【０２１１】
図２８Ｂに図示されたタイル２６４１，２６４２，２６４３ごとに表示された「０」、「−１」または「１」は、タイル２６４１，２６４２，２６４３それぞれの第１初期周回回数ＷＮｉｎｉｔ＿１、第２初期周回回数ＷＮｉｎｉｔ＿２、または第１初期周回回数ＷＮｉｎｉｔ＿１と第２初期周回回数ＷＮｉｎｉｔ＿２とが合算された結果を意味する。
【０２１２】
図２８Ａないし図２９Ｃを参照して説明したように、演算部１４５が、第２経路ｅ１の位置及び進行方向に基づいて、第２初期周回回数ＷＮｉｎｉｔ＿２を演算したので、その後、演算部１４５は、第３経路ｅ２の位置及び進行方向に基づいて、第３初期周回回数ＷＮｉｎｉｔ＿３を演算することができる。
【０２１３】
図３０Ａ及び図３０Ｂは、一実施形態による、演算部がフレームに含まれたタイルのうち、第３経路が通過するタイルの一側方向に並んだタイルの第３初期回数を演算する一例について説明するための図面である。
【０２１４】
図３０Ａには、第３経路ｅ２が図示されている。ここで、第３経路ｅ２は、頂点Ｐ２から頂点Ｐ０まで連結されたエッジである。従って、第３経路ｅ２は、時計回り方向に回転する経路であるということが分かる。
【０２１５】
割当て部１４２は、フレーム２８１０に含まれたタイルのうち、第２経路ｅ１が通過するタイル２８２０を選択する。そして、割当て部１４２は、選択されたタイル２８２０別にタイルに、第３経路ｅ２が通過するという情報を「Edge＿List」として生成し、それをメモリ（図示せず）に保存する。もしEdge＿Listがすでに生成されたタイルである場合には、割当て部１４２は、既生成のEdge＿Listに、第３経路ｅ２が通過するという情報を追加して保存する。図３０Ｂに図示されたタイル２８２０に表示された「ｅ０，ｅ２」、「ｅ１，ｅ２」または「ｅ２」は、タイル２８２０それぞれのEdge＿Listに含まれた情報を意味する。すなわち、「ｅ０，ｅ２」が表示されたタイルは、第１経路ｅ０が通過するタイルでありながら、第３経路ｅ２が通過するタイルを意味する。また、「ｅ１，ｅ２」が表示されたタイルは、第２経路ｅ１が通過するタイルでありながら、第３経路ｅ２が通過するタイルを意味する。また、「ｅ２」が表示されたタイルは、第３経路ｅ２が通過するタイルを意味する。
【０２１６】
そして、演算部１４５は、選択されたタイル２８２０の一側面に位置するタイル２８３１それぞれの第３初期周回回数ＷＮｉｎｉｔ＿３を演算する。例えば、演算部１４５は、選択されたタイル２８２０の左側方向のタイル２８３１それぞれの第３初期周回回数ＷＮｉｎｉｔ＿３を演算することができる。すなわち、第３経路ｅ２が時計回り方向にタイル２８２０を通過するので、演算部１４５は、タイル２８３１それぞれに、＋１を第３初期周回回数ＷＮｉｎｉｔ＿３として付与する。そして、演算部１４５は、第３初期周回回数ＷＮｉｎｉｔ＿３を、それぞれのタイル別にメモリ（図示せず）に保存することができる。
【０２１７】
一方、第３経路ｅ２の開始頂点Ｐ２を含むタイルの左側方向に位置したタイル２８３２の場合、演算部１４５は、第２経路ｅ１及び第３経路ｅ２がタイルを通過する形態を考慮し、第３初期周回回数ＷＮｉｎｉｔ＿３を付与する。このとき、演算部１４５が、タイル２８３２それぞれに、第３初期周回回数ＷＮｉｎｉｔ＿３を付与する方法は、図２９Ａないし図２９Ｃを参照して説明した通りである。すなわち、第２経路ｅ１と第３経路ｅ２が結合された単一経路が、タイル２８２１の対向する２本の境界線を時計回り方向に（すなわち、上から下に）通過するので、演算部１４５は、タイル２８３２それぞれに、＋１を第３初期周回回数ＷＮｉｎｉｔ＿３として付与する。そして、演算部１４５は、第３初期周回回数ＷＮｉｎｉｔ＿３をそれぞれのタイル別に、メモリ（図示せず）に保存することができる。
【０２１８】
また、第３経路ｅ２の終了頂点Ｐ０を含むタイルの左側方向に位置したタイル２８３３の場合、演算部１４５は、第３経路ｅ２及び第１経路ｅ０がタイルを通過する形態を考慮し、第３初期周回回数ＷＮｉｎｉｔ＿３を付与する。このとき、演算部１４５が、タイル２８３３に第３初期周回回数ＷＮｉｎｉｔ＿３を付与する方法は、図２９Ａないし図２９Ｃを参照して説明した通りである。すなわち、第３経路ｅ２と第１経路ｅ０とが結合された単一経路がタ、イル２８２２の単一面（すなわち、上側面）に入り、同じ方向に出て行くので、演算部１４５は、タイル２８３３に、０を第３初期周回回数ＷＮｉｎｉｔ＿３として付与する。そして、演算部１４５は、タイル２８３３の第３初期周回回数ＷＮｉｎｉｔ＿３をメモリ（図示せず）に保存することができる。
【０２１９】
図３０Ｂには、第１初期周回回数ＷＮｉｎｉｔ＿１、第２初期周回回数ＷＮｉｎｉｔ＿２及び第３初期周回回数ＷＮｉｎｉｔ＿３が合算された結果が図示されている。演算部１４５は、タイルの第１初期周回回数ＷＮｉｎｉｔ＿１、第２初期周回回数ＷＮｉｎｉｔ＿２または第３初期周回回数ＷＮｉｎｉｔ＿３をメモリ（図示せず）に保存することができる。例えば、第１初期周回回数ＷＮｉｎｉｔ＿１、第２初期周回回数ＷＮｉｎｉｔ＿２または第３初期周回回数ＷＮｉｎｉｔ＿３は、メモリ（図示せず）に、それぞれのタイル別にビットストリーム形態で保存される。従って、第１初期周回回数ＷＮｉｎｉｔ＿１、第２初期周回回数ＷＮｉｎｉｔ＿２または第３初期周回回数ＷＮｉｎｉｔ＿３のうち２以上がいずれも付与されたタイルに対して、演算部１４５は、付与された初期周回回数を合算することができる。
【０２２０】
図３０Ｂに図示された一部タイル２８４１は、第３初期周回回数ＷＮｉｎｉｔ＿３（例えば、０または＋１）のみを有する。また、図３０Ｂに図示された一部タイル２８４２は、第２初期周回回数ＷＮｉｎｉｔ＿２（例えば、０または＋１）のみを有する。また、図３０Ｂに図示された一部タイル２８４３は、第１初期周回回数ＷＮｉｎｉｔ＿１（例えば、−１）及び第３初期周回回数ＷＮｉｎｉｔ＿３（例えば、＋１）をいずれも有する。また、図３０Ｂに図示された一部タイル２８４４は、第１初期周回回数ＷＮｉｎｉｔ＿１（例えば、−１）及び第２初期周回回数ＷＮｉｎｉｔ＿２（例えば、＋１）をいずれも有する。
【０２２１】
従って、演算部１４５は、図３０Ｂに図示された一部タイル２８４３、２８４４それぞれに対して、初期周回回数を合算（例えば、−１＋１＝０）することができる。
【０２２２】
図３０Ｂに図示されたタイル２８４１，２８４２，２８４３，２８４４ごとに表示された「０」または「１」は、タイル２８４１，２８４２，２８４３，２８４４それぞれの第１初期周回回数ＷＮｉｎｉｔ＿１、第２初期周回回数ＷＮｉｎｉｔ＿２、第３初期周回回数ＷＮｉｎｉｔ＿３、または第１初期周回回数ＷＮｉｎｉｔ＿１ないし第３初期周回回数ＷＮｉｎｉｔ＿３が合算された値を意味する。
【０２２３】
演算部１４５は、第１初期周回回数ＷＮｉｎｉｔ＿１ないし第３初期周回回数ＷＮｉｎｉｔ＿３に基づいて、フレーム２８１０に含まれたタイルそれぞれに、最終初期周回回数ＷＮｉｎｉｔを設定する。例えば、第１初期周回回数ＷＮｉｎｉｔ＿１ないし第３初期周回回数ＷＮｉｎｉｔ＿３のうち一つが付与されたタイルの場合、演算部１４５は、付与された初期周回回数を、最終的な初期周回回数ＷＮｉｎｉｔに設定する。また、第１初期周回回数ＷＮｉｎｉｔ＿１ないし第３初期周回回数ＷＮｉｎｉｔ＿３のうち２以上が付与されたタイルの場合、演算部１４５は、付与された初期周回回数を合算することにより、最終的な初期周回回数ＷＮｉｎｉｔを設定する。また、第１初期周回回数ＷＮｉｎｉｔ＿１ないし第３初期周回回数ＷＮｉｎｉｔ＿３のうちいずれも付与されていないタイルの場合、演算部１４５は、最終的な初期周回回数ＷＮｉｎｉｔを「０」に設定する。
【０２２４】
再び図１を参照すれば、周回回数演算部１５０は、タイルビニングの結果を利用して、フレームに含まれたピクセルそれぞれの周回回数を演算する。例えば、周回回数演算部１５０は、それぞれのタイルごとに割り当てられた経路の識別値（例えば、Edge＿ListまたはCurve＿List）及び初期周回回数を利用して、ピクセルの周回回数を演算することができる。
【０２２５】
具体的には、周回回数演算部１５０は、タイルに対して生成されたEdge＿ListまたはCurve＿Listを参照することにより、周回回数の演算に必要な経路が何であるかということを確認することができる。そして、周回回数演算部１５０は、確認された経路の位置及び進行方向に基づいて、ピクセルの周回回数を演算することができる。
【０２２６】
一例として、ビニング遂行部１４０が、タイルの初期周回回数を演算した場合であるならば、周回回数演算部１５０は、初期周回回数に基づいて、ピクセルの周回回数を演算することができる。他の例として、ビニング遂行部１４０が、タイルの初期周回回数を演算していない場合であるならば、周回回数演算部１５０は、タイルの初期周回回数をまず演算し、その後、ピクセルの周回回数を演算することができる。
【０２２７】
以下、図３１Ａないし図３５を参照し、周回回数演算部１５０が、ピクセルの周回回数を演算する例について説明する。
【０２２８】
図３１Ａないし図３１Ｃは、一実施形態による周回回数演算部１５０が、ピクセルの周回回数を演算する一例について説明するための図面である。
【０２２９】
図３１Ａには、６＊６個のタイルから構成されたフレーム３１１０、及び三角形の客体３１２０が図示されている。図３１Ａないし図３１Ｃでは、割当て部１４２が、経路ｅ０，ｅ１，ｅ２が通過するタイル３１３０に対してEdge＿Listを生成し、演算部１４５が、フレーム３１１０に含まれたタイルそれぞれの初期周回回数ＷＮｉｎｉｔを演算したと仮定して説明する。
【０２３０】
１つのタイルには、複数個のピクセルが含まれている。従って、ピクセルの周回回数は、１つのタイルに含まれたピクセル間においても互いに異なる。以下、図３１Ｂ及び図３１Ｃを参照して具体的に説明する。
【０２３１】
図３１Ｂには、図３１Ａに図示された経路ｅ０，ｅ１，ｅ２が通過するタイル３１３０のうちいずれか１つのタイル３１３１が図示されている。タイル３１３１の内部領域は、第１経路ｅ０及び第２経路ｅ１によって２個の領域に区分される。以下では、第１経路ｅ０及び第２経路ｅ１によって取り囲まれた領域を第１領域３１４１とし、第１領域３１４１を除いた領域を第２領域３１４２とする。
【０２３２】
周回回数演算部１５０は、下記数式（１）によって、ピクセルの周回回数ＷＮを演算することができる。
【０２３３】
【数１】
0006785570.tif 000002
数式（１）で、ＷＮは、ピクセルの周回回数を意味し、ＷＮｉｎｉｔは、ピクセルを含むタイルの初期周回回数を意味する。そして、ＮＣＷは、ピクセルの一側面に位置し、時計回り方向に進む（すなわち、上から下に進む）経路に基づいて決定された値を意味する。そして、ＮＣＣＷは、ピクセルの一側面に位置し、反時計回り方向に進む（すなわち、下から上で進む）経路に基づいて決定された値を意味する。ここで、ピクセルの一側面は、ピクセルの位置を中心に、左側、右側、上側及び下側のうちいずれか一つを意味する。
【０２３４】
すなわち、周回回数演算部１５０は、ピクセルが含まれたタイルの初期周回回数ＷＮｉｎｉｔと、ピクセルの一側面に位置する経路の進行方向とを利用して、ピクセルの周回回数を演算することができる。以下、図３２Ａないし図３３Ｄを参照し、周回回数演算部１５０が、前記数式（１）のＮＣＷ及びＮＣＣＷを決定する一例について説明する。
【０２３５】
図３２Ａ及び図３２Ｂは、一実施形態による、周回回数演算部がピクセルの周回回数を演算する一例について説明するための図面である。
【０２３６】
図３２Ａには、頂点１、頂点２及び頂点３が含まれた客体３２４０が図示されている。具体的には、客体３２４０は、頂点１から頂点２までの第１経路、頂点２から頂点３までの第２経路、及び頂点３から頂点１までの第３経路によって構成される。
【０２３７】
周回回数演算部１５０は、フレームに含まれたピクセルそれぞれの位置を中心に、一側面に経路が位置するか否かということを確認する。ここで、一側面は、ピクセルの位置を中心に、左側、右側、上側及び下側のうちいずれか一つを意味する。以下では、説明の便宜のために、周回回数演算部１５０がピクセル３２１０の位置を中心に、右側に経路が位置するか否かということを確認すると仮定して説明する。
【０２３８】
周回回数演算部１５０は、ピクセル３２１０の右側に位置する経路の進行方向が、時計回り方向であるか、あるいは反時計回り方向であるかということを決定する。例えば、周回回数演算部１５０が、ピクセル３２１０の右側に経路が位置すると判断した場合には、周回回数演算部１５０は、経路の進行方向が、時計回り方向であるか、あるいは反時計回り方向であるかということを決定する。一方、周回回数演算部１５０が、ピクセル３２１０の右側に経路が位置しないと判断した場合には、周回回数演算部１５０は、数式（１）のＮＣＷ及びＮＣＣＷを０と決定する。
【０２３９】
図３２Ａを参照すれば、周回回数演算部１５０は、客体３２４０を構成する３個の経路のうち、ピクセル３２１０の右側に位置する第２経路の進行方向が、時計回り方向であるか、あるいは反時計回り方向であるかということを決定する。言い換えれば、第１経路と第３経路は、ピクセル３２１０の右側に位置しないので、周回回数演算部１５０は、第１経路と第３経路との進行方向を決定せず、第２経路の進行方向のみを決定する。ここで、第２経路は、頂点２から頂点３まで進むので、周回回数演算部１５０は、第２経路の進行方向が、時計回り方向であると決定する。
【０２４０】
その後、周回回数演算部１５０は、時計回り方向に進む経路の個数により、周回回数演算部１５０のＮＣＷに既定の値を加算し、反時計回り方向に進む経路の個数により、ＮＣＣＷに既定の値を加算する。ここで、既定の値は、１にもなるが、それに限定されるものではない。
【０２４１】
もし既定の値が１であると仮定すれば、周回回数演算部１５０は、第２経路の進行方向が時計回り方向であると決定したので、周回回数演算部１５０は、ピクセル３２１０のＮＣＷを＋１と決定する。
【０２４２】
前述の方法のように、周回回数演算部１５０が、フレームに含まれたピクセルそれぞれに対してＮＣＷを演算する場合、図３２Ａに図示された客体３２４０の内部に存在するピクセルのＮＣＷは、いずれも＋１に決定され、客体３２４０の外部に存在するピクセルのＮＣＷは、いずれも０に決定される。
【０２４３】
以下では、説明の便宜のために、周回回数演算部１５０が、ピクセルのＮＣＷ及びＮＣＣＷを決定するとき、経路の進行方向が時計回り方向である場合、ＮＣＷを＋１と決定し、経路の進行方向が反時計回り方向である場合、ＮＣＣＷを＋１と決定すると仮定して説明する。
【０２４４】
図３２Ｂには、頂点１、頂点２、頂点３及び頂点４で構成された第１客体３２５０、及び頂点５、頂点６、頂点７及び頂点８で構成された第２客体３２６０が図示されている。具体的には、第１客体３２５０は、頂点１から頂点２までの第１経路、頂点２から頂点３までの第２経路、頂点３から頂点４までの第３経路、及び頂点４から頂点１までの第４経路によって構成される。また、第２客体３２６０は、頂点５から頂点６までの第５経路、頂点６から頂点７までの第６経路、頂点７から頂点８までの第７経路、及び頂点８から頂点５までの第８経路によって構成される。
【０２４５】
以下では、周回回数演算部１５０が、ピクセル３２２０または３２３０の位置を中心に、右側に経路が位置するか否かということを確認すると仮定して説明する。
【０２４６】
一例として、周回回数演算部１５０が、ピクセル３２２０のＮＣＷ及びＮＣＣＷを決定する方法について説明する。
【０２４７】
周回回数演算部１５０は、ピクセル３２２０の位置を中心に、右側に経路が存在するか否かということを確認する。具体的には、周回回数演算部１５０は、ピクセル３２２０の右側には、第１客体３２５０に含まれた第３経路が存在すると確認する。
【０２４８】
周回回数演算部１５０は、確認結果に基づいて、第３経路の進行方向が時計回り方向であるか、あるいは反時計回り方向であるかということを決定する。周回回数演算部１５０は、第３経路の進行方向が時計回り方向であると決定する。従って、周回回数演算部１５０は、ピクセル３２２０のＮＣＷを＋１と決定する。
【０２４９】
他の例において、周回回数演算部１５０が、ピクセル３２３０のＮＣＷ及びＮＣＣＷを決定する方法について説明する。
【０２５０】
周回回数演算部１５０は、ピクセル３２３０の右側には、第２客体３２６０に含まれた第６経路と、第１客体３２５０に含まれた第３経路とが存在すると確認する。その後、周回回数演算部１５０は、第６経路の進行方向が反時計回り方向であり、第３経路の進行方向が時計回り方向であると決定する。周回回数演算部１５０は、第６経路の進行方向が反時計回り方向であると決定したので、周回回数演算部１５０は、ピクセル３２３０のＮＣＣＷを＋１と決定する。そして、周回回数演算部１５０は、第３経路の進行方向が時計回り方向であると決定したので、周回回数演算部１５０は、ピクセル３２３０のＮＣＷを＋１と決定する。
【０２５１】
前述の方法のように、周回回数演算部１５０がフレームに含まれたピクセルそれぞれに対して、ＮＣＷ及びＮＣＣＷを決定する場合、図３２Ｂに図示された第１客体３２５０の内部であり、第２客体３２６０の外部に存在するピクセルのＮＣＷは、いずれも＋１に決定され、第２客体３２６０の内部に存在するピクセルのＮＣＷ及びＮＣＣＷは、いずれも＋１に決定される。
【０２５２】
一方、周回回数演算部１５０が、ピクセルの位置を中心に、左側、右側、上側及び下側のうちいずれかの側面を選択して周回回数を演算しても、その結果は、いずれも同一である。以下、図３３Ａないし図３３Ｄを参照し、周回回数演算部１５０が互いに異なる側面を選択し、ピクセルのＮＣＷ及びＮＣＣＷを決定する一例について説明する。
【０２５３】
図３３Ａないし図３３Ｄは、一実施形態による、周回回数演算部が互いに異なる側面を選択し、ピクセルの周回回数を演算する一例について説明するための図面である。
【０２５４】
図３３Ａないし図３３Ｄには、頂点１ないし頂点５で構成された客体が図示されている。図３３Ａないし図３３Ｄに図示された客体は、星状の閉多角形であり、いずれも同一である。
【０２５５】
図３３Ａを参照すれば、周回回数演算部１５０は、ピクセルＰの位置を中心に、右側に経路が位置するか否かということを確認する。具体的には、周回回数演算部１５０は、ピクセルＰの右側（例えば、ピクセルＰの右側水平方向に引いた仮想の半直線上の位置）には、頂点２から頂点３までの経路と、頂点５から頂点１までの経路とが存在すると確認する。頂点２から頂点３までの経路の進行方向と、頂点５から頂点１までの経路の進行方向は、いずれも時計回り方向であるので、周回回数演算部１５０は、ピクセルＰのＮＣＷを＋２と決定する。
【０２５６】
図３３Ｂを参照すれば、周回回数演算部１５０は、ピクセルＰの位置を中心に、左側に経路が位置するか否かということを確認する。具体的には、周回回数演算部１５０は、ピクセルＰの左側（例えば、ピクセルＰの左側水平方向に引いた仮想の半直線上の位置）には、頂点１から頂点２までの経路と、頂点３から頂点４までの経路とが存在すると確認する。頂点１から頂点２までの経路の進行方向と、頂点３から頂点４までの経路の進行方向は、いずれも時計回り方向であるので、周回回数演算部１５０は、ピクセルＰのＮＣＷを＋２と決定する。
【０２５７】
図３３Ｃを参照すれば、周回回数演算部１５０は、ピクセルＰの位置を中心に、上側に経路が位置するか否かということを確認する。具体的には、周回回数演算部１５０は、ピクセルＰの上側（例えば、ピクセルＰの上側水平方向に引いた仮想の半直線上の位置）には、頂点２から頂点３までの経路と、頂点４から頂点５までの経路とが存在すると確認する。頂点２から頂点３までの経路の進行方向と、頂点４から頂点５までの経路の進行方向は、いずれも時計回り方向であるので、周回回数演算部１５０は、ピクセルＰのＮＣＷを＋２と決定する。
【０２５８】
図３３Ｄを参照すれば、周回回数演算部１５０は、ピクセルＰの位置を中心に、下側に経路が位置するか否かということを確認する。具体的には、周回回数演算部１５０は、ピクセルＰの下側（例えば、ピクセルＰの下側水平方向に引いた仮想の半直線上の位置）には、頂点５から頂点１までの経路と、頂点３から頂点４までの経路とが存在すると確認する。頂点５から頂点１までの経路の進行方向と、頂点３から頂点４までの経路の進行方向は、いずれも時計回り方向であるので、周回回数演算部１５０は、ピクセルＰのＮＣＷを＋２と決定する。
【０２５９】
前述のところのように、周回回数演算部１５０が、ピクセルＰの位置を中心に、いずれの側面を選択してＮＣＷ及びＮＣＣＷを決定するとしても、その結果は、いずれも同一である。また、図３３Ａないし図３３Ｄに図示されているように、経路によって区分された領域のうち同一である領域内に存在するピクセルのＮＣＷ及びＮＣＣＷは、いずれも同一である。
【０２６０】
周回回数演算部１５０は、ピクセルの位置、及び経路の位置を考慮し、フレームに含まれたピクセルごとにそれぞれ、ＮＣＷ及びＮＣＣＷを決定する一側面を選択することができる。言い換えれば、周回回数演算部１５０は、ピクセルＰの位置を中心に、いずれの側面を選択し、ＮＣＷ及びＮＣＣＷを決定するか、ピクセルＰの位置によって、互いに異なるように選択することもできる。すなわち、周回回数演算部１５０は、ピクセルＰの位置を基準に、最も少ない数の経路が存在すると予想される方向に、ＮＣＷ及びＮＣＣＷを決定する一側面を選択することができる。
【０２６１】
例えば、ピクセルＰが、フレームの中心線を基準に、左側に存在すると仮定すれば、周回回数演算部１５０がＮＣＷ及びＮＣＣＷを決定する一側面を、ピクセルＰの右側面よりは、左側面を選択してこそ、周回回数演算部１５０が、さらに少ない数の経路を利用して、ピクセルＰのＮＣＷ及びＮＣＣＷを決定することができる。また、ピクセルＰが、フレームの中心線を基準に、右側に存在すると仮定すれば、周回回数演算部１５０が、ＮＣＷ及びＮＣＣＷを演算する一側面を、ピクセルＰの左側面よりは右側面を選択してこそ、周回回数演算部１５０が、さらに少ない数の経路を利用して、ピクセルＰのＮＣＷ及びＮＣＣＷを決定することができる。
【０２６２】
従って、周回回数演算部１５０は、フレームに含まれたピクセルごとにそれぞれ互いに異なる側面を選択し、ＮＣＷ及びＮＣＣＷを決定することができる。このとき、周回回数演算部１５０は、フレーム内において、客体を構成する経路がどの位置に分布するかということを判断し、周回回数演算部１５０は、ＮＣＷ及びＮＣＣＷが決定されるピクセルの位置を中心に、最も少ない経路が存在する方向に、ＮＣＷ及びＮＣＣＷの決定に利用される一側面を選択する。
【０２６３】
再び図３１Ｂを参照すれば、周回回数演算部１５０は、第１領域３１４１に含まれたピクセル３１５１の周回回数ＷＮを＋１に演算することができる。具体的には、タイル３１３１の初期周回回数ＷＮｉｎｉｔは、０であり、ピクセル３１５１の右側面に位置した第２経路ｅ１が時計回り方向に進むので、ＮＣＷは、１である。また、ピクセル３１５１の右側面に反時計回り方向に進む経路がないので、ＮＣＣＷは、０である。従って、周回回数演算部１５０は、数式（１）によって、ピクセル３１５１の周回回数ＷＮを＋１に演算することができる。
【０２６４】
また、周回回数演算部１５０は、第２領域３１４２に含まれたピクセル３１５２の周回回数ＷＮを０に演算することができる。具体的には、タイル３１３１の初期周回回数ＷＮｉｎｉｔは、０であり、ピクセル３１５２の右側面に位置した第１経路ｅ０が反時計回り方向に進むので、ＮＣＣＷは、１である。また、ピクセル３１５２の右側面に位置した第２経路ｅ１が時計回り方向に進むので、ＮＣＷは１である。従って、周回回数演算部１５０は、数式（１）によって、ピクセル３１５２の周回回数ＷＮを０に演算することができる。
【０２６５】
また、周回回数演算部１５０は、第２領域３１４２に含まれたピクセル３１５３の周回回数ＷＮを０に演算することができる。具体的には、タイル３１３１の初期周回回数ＷＮｉｎｉｔは、０であり、ピクセル３１５３の右側面に位置した経路がないので、ＮＣＷ及びＮＣＣＷは、０である。従って、周回回数演算部１５０は、数式（１）によって、ピクセル３１５３の周回回数ＷＮを０に演算することができる。
【０２６６】
総合すれば、図３１Ｂに図示された第１領域３１４１に含まれたピクセルそれぞれの周回回数ＷＮは、いずれも１に演算され、第２領域３１４２に含まれたピクセルそれぞれの周回回数ＷＮは、いずれも０に演算される。すなわち、同一タイルに含まれたピクセルでも、経路によって区分された領域によって、ピクセルの周回回数ＷＮが互いに異なる。
【０２６７】
図３１Ｃには、図３１Ａに図示された経路ｅ０，ｅ１，ｅ２が通過するタイル３１３０のうちいずれか１つのタイル３１３２が図示されている。タイル３１３２の内部領域は、第１経路ｅ０によって、２個の領域に区分される。以下では、第１経路ｅ０及びタイル３１３２の境界線によって取り囲まれた領域を第３領域３１４３とし、第３領域３１４３を除いた領域を第４領域３１４４とする。
【０２６８】
周回回数演算部１５０は、第３領域３１４３に含まれたピクセル３１５４の周回回数ＷＮを＋１に演算することができる。具体的には、タイル３１３２の初期周回回数ＷＮｉｎｉｔは、１であり、ピクセル３１５４の右側面に位置した経路がないので、ＮＣＷ及びＮＣＣＷは、０である。従って、周回回数演算部１５０は、数式（１）によって、ピクセル３１５４の周回回数ＷＮを０に演算することができる。
【０２６９】
また、周回回数演算部１５０は、第４領域３１４４に含まれたピクセル３１５５の周回回数ＷＮを０に演算することができる。具体的には、タイル３１３２の初期周回回数ＷＮｉｎｉｔは、１であり、ピクセル３１５５の右側面に位置した第１経路ｅ０が反時計回り方向に進むので、ＮＣＣＷは、１である。また、ピクセル３１５１の右側面に時計回り方向に進む経路がないので、ＮＣＷは０である。従って、周回回数演算部１５０は、数式（１）によって、ピクセル３１５５の周回回数ＷＮを０に演算することができる。
【０２７０】
総合すれば、図３１Ｃに図示された第３領域３１４３に含まれたピクセルそれぞれの周回回数ＷＮは、いずれも１に演算され、第４領域３１４４に含まれたピクセルそれぞれの周回回数ＷＮは、いずれも０に演算される。
【０２７１】
図３４Ａ及び図３４Ｂは、一実施形態による、周回回数演算部が経路が通過するタイルに含まれたピクセルの周回回数を演算した結果の例を示す図面である。
【０２７２】
図３４Ａには、三角形の客体３４２０が図示されており、図３４Ｂには、星状の客体３４３０が図示されている。
【０２７３】
図３４Ａ及び図３４Ｂを参照すれば、客体３４２０を構成する経路が通過するタイル３４１１に含まれたピクセルの周回回数ＷＮが表示されている。周回回数演算部１５０が、フレーム３４１０に含まれた全てのピクセルの周回回数ＷＮを演算する場合、経路が通過しないタイル３４１２に含まれたピクセルの周回回数ＷＮは、タイル３４１２それぞれの初期周回回数ＷＮｉｎｉｔと同一になる。従って、周回回数演算部１５０は、タイル３４１１に含まれたピクセルの周回回数ＷＮのみを演算し、タイル３４１２に含まれたピクセルの周回回数ＷＮは、タイル３４１２それぞれの初期周回回数ＷＮｉｎｉｔと決定することができる。
【０２７４】
前述のところによれば、周回回数演算部１５０は、フレーム３４１０に含まれた全てのピクセルに対して、周回回数ＷＮを演算しなくてもよい。従って、レンダリング装置１００は、迅速な速度で、フレーム３４１０に含まれた全てのピクセルの周回回数ＷＮを演算することができる。
【０２７５】
一方、周回回数演算部１５０が、タイルの初期周回回数ＷＮｉｎｉｔを演算することもできる。具体的には、ビニング遂行部１４０の演算部１４５が、タイルの初期周回回数ＷＮｉｎｉｔを演算しない場合、周回回数演算部１５０が、タイルの初期周回回数ＷＮｉｎｉｔを演算することもできる。
【０２７６】
図３５は、一実施形態による、周回回数演算部がタイルの初期周回回数を演算する一例について説明するための図面である。図３５を参照すれば、タイル３５１０の右側に、経路３５２０が存在する。タイル３５１０が四角形であると仮定すれば、周回回数演算部１５０は、タイル３５１０の４側面のうち、経路３５２０と最も近い側面３５１１を選択する。そして、周回回数演算部３５１０は、側面３５１１に含まれた２つの頂点Ｔ１，Ｔ２の位置と、経路３５２０の位置とを比較する。例えば、２つの頂点Ｔ１，Ｔ２が、経路３５２０より左側に存在し、経路３５２０の進行方向が時計回り方向であると仮定すれば、周回回数演算部１５０は、タイル３５１０の初期周回回数ＷＮｉｎｉｔを１と決定する。一方、２つの頂点Ｔ１，Ｔ２が、経路３５２０より左側に存在し、経路３５２０の進行方向が反時計回り方向であると仮定すれば、周回回数演算部１５０は、タイル３５１０の初期周回回数ＷＮｉｎｉｔを−１と決定する。もし２つの頂点Ｔ１，Ｔ２のうちいずれか一つでも経路３５２０より右側に存在すれば、周回回数演算部１５０は、タイル３５１０の初期周回回数ＷＮｉｎｉｔを０と決定する。
【０２７７】
図３５を参照して説明したように、周回回数演算部１５０が、タイルの初期周回回数ＷＮｉｎｉｔを演算する場合、ビニング遂行部１４０において、タイルの初期周回回数ＷＮｉｎｉｔを演算し、それを保存するのに所要するコストが低減する。言い換えれば、タイルの初期周回回数ＷＮｉｎｉｔが保存または更新される過程において、ビニング遂行部１４０は、少なくとも１回以上、メモリ（図示せず）にデータを保存したり、メモリ（図示せず）からデータを読み取ったりする。従って、周回回数演算部１５０が、タイルの初期周回回数ＷＮｉｎｉｔを演算する場合、ハードウェアが動作するのに所要する時間またはコストが低減する。
【０２７８】
また、周回回数演算部１５０が、タイルの初期周回回数ＷＮｉｎｉｔを演算する場合、ビニング遂行部１４０において、周回回数演算部１５０にタイルの初期周回回数ＷＮｉｎｉｔを伝達するのに所要するコストが低減する。
【０２７９】
再び図１を参照すれば、ピクセルシェーダ１２０は、ピクセルの周回回数ＷＮに基づいて、ピクセルに対応するカラーを決定することができる。
【０２８０】
例えば、ピクセルシェーダは、既設定の規則に基づいて、ピクセルそれぞれに対応するカラーを決定することができる。ここで、既設定の規則は、周回回数が０ではない値を有するピクセルにカラー値を割り当てる第１規則、または周回回数が奇数である値を有するピクセルにカラー値を割り当てる第２規則のうちいずれか一つを意味する。以下、図３６Ａないし図３６Ｃを参照し、ピクセルシェーダ１２０がピクセルに対応するカラーを決定する一例について説明する。
【０２８１】
図３６Ａないし図３６Ｃは、一実施形態による、ピクセルシェーダ１２０がフレームに含まれたピクセルそれぞれに対応するカラーを決定する一例について説明するための図面である。
【０２８２】
図３６Ａは、フレーム３６１０に含まれたピクセルそれぞれの周回回数を図示した図面であり、図３６Ｂは、第１規則によって、ピクセルそれぞれにカラー値が割り当てられた結果を図示した図面である。また、図３６Ｃは、第２規則により、ピクセルそれぞれにカラー値が割り当てられた結果を図示した図面である。
【０２８３】
図３６Ａを参照すれば、領域３６１１に含まれたピクセルは、それぞれ周回回数が０と演算されており、領域３６１２に含まれたピクセルは、それぞれ周回回数が＋１と演算されており、領域３６１３に含まれたピクセルは、それぞれ周回回数が＋２と演算されている。
【０２８４】
一例として、ピクセルシェーダ１２０は、第１規則に基づいて、ピクセルそれぞれに対応するカラーを決定することができる。ここで、第１規則は、周回回数が０ではない値を有するピクセルにカラー値を割り当てることを意味する。図３６Ｂを参照すれば、ピクセルシェーダ１２０は、第１規則により、図３６Ａに図示された領域３６１２及び領域３６１３に含まれたピクセルには、カラーを設定し、領域３６１１に含まれたピクセルには、カラーを設定しないと決定する。
【０２８５】
他の例として、ピクセルシェーダ１２０は、第２規則に基づいて、ピクセルそれぞれに対応するカラーを決定することができる。ここで、第２規則は、周回回数が奇数である値を有するピクセルにカラー値を割り当てることを意味する。ここで、奇数は、ピクセルの周回回数の絶対値が奇数である場合を意味する。例えば、周回回数が＋３である場合も奇数と判断され、周回回数が−３である場合も奇数と判断される。また、周回回数が０である場合は、偶数と判断される。図３６Ｃを参照すれば、ピクセルシェーダ１２０は、第２規則により、図３６Ａに図示された領域３６１２に含まれたピクセルには、カラーを設定し、領域３６１１及び領域３６１３に含まれたピクセルにはカラーを設定しないと決定する。
【０２８６】
そして、ピクセルシェーダ１２０は、カラーが設定されると決定されたピクセルに、カラー値を割り当てる。
【０２８７】
前述のところによれば、レンダリング装置１００が、経路それぞれに対して独立してタイルビニングを行うことができるが、レンダリング装置１００が動作するのに所要する時間及びコスト（例えば、電力）が低減する。また、レンダリング装置１００は、フレームに含まれたタイルに対して不要に割り当てられた経路の識別値を除去することにより、レンダリング装置１００の効率がさらに高くなる。
【０２８８】
また、レンダリング装置１００は、フレームに含まれたピクセルのうち、経路が通過するタイルに含まれたピクセルについてのみ周回回数を演算することにより、レンダリング装置１００の演算速度が向上する。また、レンダリング装置１００は、ステンシルバッファの使用なしに、ピクセルそれぞれの周回回数を演算することができるが、ステンシルバッファを使用することにより、メモリ入出力が過度に発生する問題と、重複したメモリ入出力が発生する問題とが解消される。
【０２８９】
また、レンダリング装置１００は、フレームに含まれたピクセルそれぞれに対して並列して周回回数を生成することにより、高速で経路レンダリングを行うことができ、短時間内に高解像度のレンダリングを行うことができる。
【０２９０】
一方、前述の方法は、コンピュータで実行されるプログラムでもって作成可能であり、コンピュータで読み取り可能な記録媒体を利用して、前記プログラムを動作させる汎用デジタルコンピュータで具現される。また、前述の方法で使用されたデータの構造は、コンピュータで読み取り可能な記録媒体に、多くの手段を介して記録される。前記コンピュータで読み取り可能な記録媒体は、マグネチック記録媒体（例えば、ＲＯＭ（read  only  memory）、ＲＡＭ（random  access  memory）、ＵＳＢ（universal  serial  bus）、フロッピー（登録商標）ディスク、ハードディスクなど）、光学的判読媒体（例えば、ＣＤ（compact  disc）−ＲＯＭ、ＤＶＤ（digital  versatile  disc）など）のような記録媒体を含む。
【０２９１】
本実施形態と係わる技術分野で当業者であるならば、前述の記載の本質的な特性から外れない範囲で変形された形態に具現されるということを理解することができるであろう。従って、開示された方法は、限定的な観点ではなく、説明的な観点から考慮されなければならない。本発明の範囲は、前述の説明ではなく、特許請求の範囲に示されており、それと同等な範囲内にある全ての差異は、本発明に含まれたものであると解釈されなければならないのである。
【産業上の利用可能性】
【０２９２】
本発明の経路レンダリングのためのタイルビニングを行う方法及びその装置は、例えば、グラフィック処理関連の技術分野に効果的に適用可能である。
【符号の説明】
【０２９３】
１００  レンダリング装置
１１０  入力アセンブラ
１２０  バーテックスシェーダ
１３０  プリミティブアセンブラ
１４０  ビニング遂行部
１５０  周回回数演算部
１６０  レンダ出力部
１７０  バッファ
【図１】
0006785570.tif 000003
【図２Ａ】
0006785570.tif 000004
【図２Ｂ】
0006785570.tif 000005
【図３】
0006785570.tif 000006
【図４Ａ】
0006785570.tif 000007
【図４Ｂ】
0006785570.tif 000008
【図５Ａ】
0006785570.tif 000009
【図５Ｂ】
0006785570.tif 000010
【図５Ｃ】
0006785570.tif 000011
【図５Ｄ】
0006785570.tif 000012
【図５Ｅ】
0006785570.tif 000013
【図６】
0006785570.tif 000014
【図７】
0006785570.tif 000015
【図８】
0006785570.tif 000016
【図９】
0006785570.tif 000017
【図１０】
0006785570.tif 000018
【図１１】
0006785570.tif 000019
【図１２Ａ】
0006785570.tif 000020
【図１２Ｂ】
0006785570.tif 000021
【図１３】
0006785570.tif 000022
【図１４】
0006785570.tif 000023
【図１５】
0006785570.tif 000024
【図１６】
0006785570.tif 000025
【図１７】
0006785570.tif 000026
【図１８Ａ】
0006785570.tif 000027
【図１８Ｂ】
0006785570.tif 000028
【図１９】
0006785570.tif 000029
【図２０】
0006785570.tif 000030
【図２１Ａ】
0006785570.tif 000031
【図２１Ｂ】
0006785570.tif 000032
【図２２】
0006785570.tif 000033
【図２３】
0006785570.tif 000034
【図２４Ａ】
0006785570.tif 000035
【図２４Ｂ】
0006785570.tif 000036
【図２５】
0006785570.tif 000037
【図２６】
0006785570.tif 000038
【図２７Ａ】
0006785570.tif 000039
【図２７Ｂ】
0006785570.tif 000040
【図２７Ｃ】
0006785570.tif 000041
【図２８Ａ】
0006785570.tif 000042
【図２８Ｂ】
0006785570.tif 000043
【図２９Ａ】
0006785570.tif 000044
【図２９Ｂ】
0006785570.tif 000045
【図２９Ｃ】
0006785570.tif 000046
【図３０Ａ】
0006785570.tif 000047
【図３０Ｂ】
0006785570.tif 000048
【図３１Ａ】
0006785570.tif 000049
【図３１Ｂ】
0006785570.tif 000050
【図３１Ｃ】
0006785570.tif 000051
【図３２Ａ】
0006785570.tif 000052
【図３２Ｂ】
0006785570.tif 000053
【図３３Ａ】
0006785570.tif 000054
【図３３Ｂ】
0006785570.tif 000055
【図３３Ｃ】
0006785570.tif 000056
【図３３Ｄ】
0006785570.tif 000057
【図３４Ａ】
0006785570.tif 000058
【図３４Ｂ】
0006785570.tif 000059
【図３５】
0006785570.tif 000060
【図３６Ａ】
0006785570.tif 000061
【図３６Ｂ】
0006785570.tif 000062
【図３６Ｃ】
0006785570.tif 000063