(57)【要約】【課題】任意のアスペクト比の矩形領域について、フラグメント数を考慮した好適なタイリングを行う。【解決手段】情報処理装置は、３次元シーンを所定の視点について描画する矩形画像の各画素と視点とで規定される直線上に存在するフラグメント数を取得し、矩形画像に対応するスクリーン座標系における２次元領域を、所定の演算を行う処理単位である複数の領域に分割する。情報処理装置は、分割後の各領域に含まれるフラグメント数の総和の差が最小となるような１以上の直線で、２次元領域を異なる領域に分割する。【選択図】図３
2015210672.tif 000002
【特許請求の範囲】
【請求項１】
３次元シーンを所定の視点について描画した矩形画像を生成する情報処理装置であって、
前記視点と前記矩形画像の各画素に描画される前記３次元シーン内の所定の点とで規定される直線上に存在するフラグメント数を取得する取得手段と、
前記矩形画像に対応するスクリーン座標系における２次元領域を複数の領域に分割する分割手段と、
前記複数の領域の夫々を演算の一単位として、所定の演算を行う演算手段と、を有し、
前記分割手段は、分割後の各領域に含まれる前記フラグメント数の総和の差が最小となるような１以上の分割線で前記２次元領域を前記複数の領域に分割する情報処理装置。
【請求項２】
３次元シーンを所定の視点について描画した矩形画像を生成する情報処理装置であって、
前記視点と前記矩形画像の各画素に描画される前記３次元シーン内の所定の点とで規定される直線上に存在するフラグメント数を取得する取得手段と、
前記矩形画像に対応するスクリーン座標系における２次元領域を複数の領域に分割する分割手段と、
前記複数の領域の夫々を演算の一単位として、所定の演算を行う演算手段と、を有し、
前記分割手段は、分割後の各領域に含まれる前記フラグメント数の総和の差が所定の値以下となるような１以上の分割線で前記２次元領域を前記複数の領域に分割する情報処理装置。
【請求項３】
前記分割手段は、水平軸及び垂直軸の少なくともいずれかの軸に直交する直線を前記分割線として、前記２次元領域を前記複数の領域に分割する請求項１または２に記載の情報処理装置。
【請求項４】
前記分割手段は、各領域に含まれる前記フラグメント数の総和が、予め定められたフラグメント数以下となるまで前記２次元領域を分割する請求項１乃至３のいずれか１項に記載の情報処理装置。
【請求項５】
前記予め定められたフラグメント数は、前記所定の演算に使用する記憶領域の容量に応じて定められる請求項４に記載の情報処理装置。
【請求項６】
前記分割線は直線であり、
前記分割手段は、１つの領域を分割する前記分割線の方向を、分割後の複数の領域のいずれかの領域の形状が正方形に近くなる方向に決定する請求項１乃至５のいずれか１項に記載の情報処理装置。
【請求項７】
前記取得手段は、前記矩形画像の対応する画素について取得した前記フラグメント数を各画素が有する２次元画像に基づいて範囲総和テーブルを生成する生成手段を有し、
前記分割手段は、前記生成手段により生成された前記範囲総和テーブルに基づいて前記分割後の各領域に含まれる前記フラグメント数の総和を算出する請求項１乃至６のいずれか１項に記載の情報処理装置。
【請求項８】
前記生成手段は、前記２次元画像の分解能を低下させて得られた画像に基づいて前記範囲総和テーブルを生成する請求項７に記載の情報処理装置。
【請求項９】
前記生成手段は、前記所定の演算において並行して処理される画素数に基づいて前記２次元画像の分解能を低下させる請求項８に記載の情報処理装置。
【請求項１０】
前記分割手段により分割された前記複数の領域のそれぞれを選択して前記矩形画像の対応する領域を描画する描画手段をさらに有する請求項１乃至９のいずれか１項に記載の情報処理装置。
【請求項１１】
３次元シーンを所定の視点について描画した矩形画像を生成する情報処理装置の制御方法であって、
前記視点と前記矩形画像の各画素に描画される前記３次元シーン内の所定の点とで規定される直線上に存在するフラグメント数を取得する取得工程と、
前記矩形画像に対応するスクリーン座標系における２次元領域を複数の領域に分割する分割工程と、
前記複数の領域の夫々を演算の一単位として、所定の演算を行う演算工程と、を有し、
前記分割工程において、分割後の各領域に含まれる前記フラグメント数の総和の差が最小となるような１以上の分割線で前記２次元領域が前記複数の領域に分割される情報処理装置の制御方法。
【請求項１２】
３次元シーンを所定の視点について描画した矩形画像を生成する情報処理装置の制御方法であって、
前記視点と前記矩形画像の各画素に描画される前記３次元シーン内の所定の点とで規定される直線上に存在するフラグメント数を取得する取得工程と、
前記矩形画像に対応するスクリーン座標系における２次元領域を複数の領域に分割する分割工程と、
前記複数の領域の夫々を演算の一単位として、所定の演算を行う演算工程と、を有し、
前記分割工程において、分割後の各領域に含まれる前記フラグメント数の総和の差が所定の値以下となるような１以上の分割線で前記２次元領域が前記複数の領域に分割される情報処理装置の制御方法。
【請求項１３】
１以上のコンピュータを、請求項１乃至１０のいずれか１項に記載の情報処理装置の各手段として機能させるためのプログラム。
【請求項１４】
請求項１３に記載のプログラムを記録したコンピュータが読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、制御方法、プログラム及び記録媒体に関し、特に３Ｄシーンの描画技術に関する。
【背景技術】
【０００２】
３Ｄグラフィックスは、ゲームや映画に限らず、様々な分野において視覚化表現方法として用いられている。このような３Ｄグラフィックスの分野では、近年、より写実的な描写、あるいは上質な描画表現に近づけるために様々な手法が提案されている。
【０００３】
３Ｄグラフィックスの写実性を向上させるための手法の１つに、間接照明等、光源から放出された光が複数回反射や散乱を考慮した照明を反映させる大域照明（Global Illumination）手法がある。該手法では、１つの描画オブジェクトについて、定義された照明（光源）によって直接生じた陰影を描画するだけでなく、該光源が他の描画オブジェクトで反射することで現れる間接照明も考慮して陰影を描画することで、よりリアリティ味のある描画表現を提供することができる。
【０００４】
大域照明に係る影響を解析する手法には様々なものがあるが、近年では並行演算能力に優れたＧＰＵを用いて解析を行う手法が提案されている。レイバンドルトレーシング手法では、解析対象の３Ｄシーンに対してサンプリング方向を選択して平行な光線（レイ）の集合（光線束）を定義し、各光線上の深度方向に並んだ描画オブジェクト間の反射を解析し、入射放射輝度を求める。このとき、光線上には複数の描画オブジェクトが存在することもあるため、１つの光線について複数のフラグメントが存在し、連続するフラグメントで規定される複数の区間における相互反射を解析することもある。非特許文献１には、このような１つの光線上に存在するフラグメントで規定される区間を考慮するために、リンクトリストを用いて光線上の各区間を関連付けている。
【０００５】
ところで、非特許文献１のようなリンクトリストは、ＯＩＴ（Order-Independent Transparency）にも用いることができる。ＯＩＴとは、半透明表示を描画順序に依らずに、即ち半透明表示で描画される最奥のオブジェクトから視点方向に順番に描画を行わずとも半透明表示を実現できる３Ｄグラフィックスの描画手法である。この場合、視点について描画する２次元画像の各画素について、視点から各画素の方向に延びる直線上に存在するフラグメントをリンクトリストとして構成することができる。
【０００６】
しかしながら、このようにリンクトリストを用いる場合、描画される画像や解析対象のマップの１つの画素には複数のフラグメントが含まれることになるため、総画素数以上の情報を有することになる。即ち、フラグメント数の総和が大きい場合、処理に使用する有限のメモリ領域内に処理対象の情報の全体を収めることができない（メモリ溢れ）可能性がある。これに対し非特許文献２には、描画する２次元画像の領域を均一なサイズを有する格子状のタイルに分割し、分割したタイルごとに描画処理を行う手法（タイリング）が開示されている。また非特許文献３には、領域内のフラグメント数を予測し、メモリ溢れが生じないようにタイルサイズを適応的に変更してタイリングを行う手法が開示されている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】徳吉雄介、外２名著、「光線束を用いた高速大域照明ベイキング（Fast Global Illumination Baking via Ray-Bundles）」、シーグラフ・アジア２０１１  テクニカル・スケッチ（SIGGRAPH Asia 2011 Technical Sketches）、2011年
【非特許文献２】ニコラス・ティビローズ（Nicolas Thibieroz）著、「画素毎のリンクトリストを用いるＯＩＴ（Order-Independent Transparency using Per-Pixel Linked Lists）」、GPU Pro 2、エー・ケー・ピーターズ（A K Peters）、2011年3月11日、第７章の２、p.409−431
【非特許文献３】徳吉雄介、外３名著、「メモリ使用予測を伴う適応的レイバンドルトレーシング：広大なシーンの効率的なグローバルイルミネーション（Adaptive Ray-bundle Tracing with Memory Usage Prediction: Efficient Global Illumination in Large Scenes）」、コンピュータグラフィックスフォーラム２０１３（Computer Graphichs Forum 2013）、2013年
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、非特許文献３に記載されるタイリングの手法では、ＧＰＵとの親和性や解析処理における参照用としての利便性を考慮して、タイリングの対象となるマップは、四分木（Quadtree）ベースでタイル分割を行うか否かの判断が行われていた。即ち、あるサイズのタイルについて分割すると判断した場合、該タイルは水平方向に２分割、垂直方向に２分割した４つのタイルに分割される構成となっているため、各方向に２のべき乗数の画素を有する正方形の画像に制約されるものであった。つまり、任意のアスペクト比の矩形領域を処理することを想定した手法ではなかった。
【０００９】
本発明の少なくとも１つの実施形態は、上述の問題点に鑑みてなされたものであり、任意のアスペクト比の矩形領域について、フラグメント数を考慮した好適なタイリングを行う情報処理装置、制御方法、プログラム及び記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１０】
前述の目的を達成するために、本発明の少なくとも１つの実施形態に係る情報処理装置は、３次元シーンを所定の視点について描画した矩形画像を生成する情報処理装置であって、視点と矩形画像の各画素に描画される３次元シーン内の所定の点とで規定される直線上に存在するフラグメント数を取得する取得手段と、矩形画像に対応するスクリーン座標系における２次元領域を複数の領域に分割する分割手段と、複数の領域の夫々を演算の一単位として、所定の演算を行う演算手段と、を有し、分割手段は、分割後の各領域に含まれるフラグメント数の総和の差が最小となるような１以上の分割線で２次元領域を複数の領域に分割する。
【００１１】
また前述の目的を達成するために、本発明の少なくとも１つの実施形態に係る情報処理装置は、３次元シーンを所定の視点について描画した矩形画像を生成する情報処理装置であって、視点と矩形画像の各画素に描画される３次元シーン内の所定の点とで規定される直線上に存在するフラグメント数を取得する取得手段と、矩形画像に対応するスクリーン座標系における２次元領域を複数の領域に分割する分割手段と、複数の領域の夫々を演算の一単位として、所定の演算を行う演算手段と、を有し、分割手段は、分割後の各領域に含まれるフラグメント数の総和の差が所定の値以下となるような１以上の分割線で２次元領域を複数の領域に分割する。
【発明の効果】
【００１２】
このような構成により本発明の少なくとも１つの実施形態によれば、任意のアスペクト比の矩形領域について、フラグメント数を考慮した好適なタイリングを行うことが可能となる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施形態に係るＰＣ１００の機能構成を示したブロック図
【図２】本発明の実施形態で用いるｋｄ木によるタイル分割を説明するための図
【図３】本発明の実施形態１に係るＰＣ１００で実行される描画処理を例示したフローチャート
【図４】本発明の実施形態の描画処理で構築する範囲総和テーブルを説明するための図
【図５】本発明の実施形態に係るＰＣ１００で実行されるタイリング処理を例示したフローチャート
【図６】本発明の実施形態２に係るＰＣ１００で実行される描画処理を例示したフローチャート
【発明を実施するための形態】
【００１４】
［実施形態１］
以下、本発明の例示的な実施形態について、図面を参照して詳細に説明する。なお、以下に説明する一実施形態は、情報処理装置の一例としての、対象シーンを所定の視点について描画した矩形画像を生成可能なＰＣに、本発明を適用した例を説明する。しかし、本発明は、対象シーンを所定の視点について描画した矩形画像を生成することが可能な任意の機器に適用可能である。
【００１５】
《ＰＣ１００の構成》
図１は、本発明の実施形態に係るＰＣ１００の機能構成を示すブロック図である。
【００１６】
制御部１０１は、例えばＣＰＵ等のＰＣ１００が有する各ブロックの動作を制御する。具体的には制御部１０１は、記憶媒体１０２に記憶された各ブロックの動作プログラムを読み出し、メモリ１０３に展開して実行することにより各ブロックの動作を制御する。
【００１７】
記憶媒体１０２は、不揮発性メモリやＨＤＤ等の記憶装置である。記憶媒体１０２は、ＰＣ１００が有する各ブロックの動作プログラムだけでなく、各ブロックの動作において必要となるパラメータ等を記憶する。また記憶媒体１０２は、後述の描画処理での生成対象となる３次元シーン（対象シーン）に配置される描画オブジェクトの各種データを記憶する。またメモリ１０３は、ＲＡＭ等の揮発性メモリである。メモリ１０３は、各ブロックの動作プログラムの展開領域としてだけでなく、各ブロックの動作において出力された中間データ等を記憶する。
【００１８】
描画部１０４は、例えばＧＰＵ等の描画装置である。描画部１０４は、例えば描画用メモリ１０５に展開された描画オブジェクトのデータを、所定のパラメータに基づいて並進や回転等の処理を行い、設定された視点の情報（位置、方向、画角、上方向等）に従って対象シーンを描画し、画像を生成する。生成される画像は、設定されたアスペクト比、あるいは設定された画素数を有する矩形状であり、画素数は２のべき乗に制約される必要はない。
【００１９】
《ｋｄ木によるタイル分割》
次に、このような構成を有する本実施形態のＰＣ１００において行われる、設定された視点について描画される対象シーンのスクリーン座標系における２次元領域をタイリングする処理の原理について説明する。
【００２０】
本実施形態のタイリング処理では、従来用いられていた四分木ではなく、ｋｄ木を用いて分割用の直線を定義する位置を決定しながら探索を行う。四分木が図２（ａ）に示されるように１つの要素を４つの要素に均等分割しながら探索を行っていくものであるのに対し、ｋｄ木は図２（ｂ）に示されるように１つの要素を２つの要素に分割しながら探索を行っていく。このとき、ｋｄ木は分割後の各要素の大きさを等しく分割する必要はなく、いずれかの軸に垂直な分割面（直線）で分割しながら探索を行っていく。
【００２１】
本実施形態のタイル分割では、対象シーンのスクリーン座標系における２次元領域を分割する直線を、該直線により分割された２つの領域（タイル）に含まれるフラグメント数の差が最小となるように条件設定し、順次定義していくものとする。即ち、分割対象のタイルについて、予め定めた軸に垂直な直線で分割した際に、分割後の２つのタイルに含まれるフラグメント数がなるべく均等になるように直線を定義しながらタイル分割を行っていく。
【００２２】
タイル分割は、全てのタイルが、描画用メモリ１０５の描画処理用の記憶領域に格納できるフラグメント数以下となるまで行われる。即ち、タイル内の各画素と視点とで定義される直線上に存在するフラグメント数の総和が全タイルで理想的には略均一数となり、かつ各タイルに係るデータ量が描画用メモリ１０５に格納可能な量に収まるまでタイル分割が行われることになる。
【００２３】
《描画処理》
以下、ｋｄ木による二分探索を利用したタイリング処理を含む本実施形態のＰＣ１００で実行される描画処理について、図３のフローチャートを用いて具体的な処理を説明する。該フローチャートに対応する処理は、制御部１０１が、例えば記憶媒体１０２に記憶されている対応する処理プログラムを読み出し、メモリ１０３に展開して実行することにより実現することができる。なお、本描画処理は、例えば対象シーンを描画する視点情報が決定され、矩形画像の生成命令がなされた際に開始されるものとして説明する。また以下の説明では、対象シーン及びシーン配置された描画オブジェクトの少なくともいずれかを、ＯＩＴによる半透明処理を伴って矩形画像を生成するものとして説明する。
【００２４】
Ｓ３０１で、制御部１０１は、決定された視点情報に基づいて、対応する投影に係るフラグメント数マップを描画部１０４に生成させる。フラグメント数マップは、本描画処理により生成される矩形画像の各画素に描画される対象シーン内の所定の点と視点とで規定される直線上に存在するフラグメント数をカウントすることにより得られる、矩形画像と同一の画素数を有する２次元マップである。フラグメント数マップの各画素は、視点からの投影に対応する範囲の対象シーンの情報が構築された後に、例えばＧＰＵのＡｔｏｍｉｃ命令を使用して生成すればよい。
【００２５】
Ｓ３０２で、描画部１０４は、生成したフラグメント数マップから範囲総和テーブル（ＳＡＴ：Summed Area Table）を構築し、例えばメモリ１０３に格納する。
【００２６】
〈範囲総和テーブル（ＳＡＴ）〉
ここで範囲総和テーブルについて、その生成方法及び本実施形態の描画処理における利用態様について説明する。
【００２７】
範囲総和テーブルは、Hensleyらの「Fast Summed-Area Table Generation and its Applications」（EUROGRAPHICS 2005）等に開示される、２次元画像の任意の矩形内の画素値の総和を効率的に算出するための２次元情報である。例えば図４（ａ）に示されるようなフラグメント数マップについての範囲総和テーブルの生成は次のように行われる。まず、フラグメント数マップの各画素の画素値を、該画素の画素値と該画素よりも水平座標の小さい画素の画素値とを総和した値に変換した図４（ｂ）のようなマップを生成する。そして該マップの各画素の画素値を、該画素の画素値と該画素よりも垂直座標の小さい画素の画素値とを総和した値にさらに変換することで、図４（ｃ）のような範囲総和テーブルを生成することができる。即ち、範囲総和テーブルの座標（ｘ，ｙ）に格納される画素値Ｉ（ｘ，ｙ）は、変換元であるフラグメント数マップの該座標の画素値ｉ（ｘ，ｙ）を用いて
2015210672.tif 000003
として算出することができる。
【００２８】
このようにして生成された範囲総和テーブルを使用することで、図４（ａ）において範囲４０１に含まれるフラグメント数の総和値Ｓ401を求めることができる。具体的には総和値は、図４（ｃ）に示される範囲総和テーブルの座標４０２、４０３、４０４、及び４０５に対応する位置の値を使用して
2015210672.tif 000004
として算出することができる。つまり、図４の例では範囲４０１内のフラグメント数の総和値は、
Ｓ401＝28＋2＋0＋17＋9＋2＋14＋21＋43＋21＋11＋0＋18＋13＋19＋5
＝16−82−69＋358
＝223
として得ることができる。
【００２９】
本実施形態では、フラグメント数マップについて範囲総和テーブルを生成しておくことで、タイリングを行う際に分割後に各タイルに含まれるフラグメント数を４つの値の参照及びそれらの加減算により算出することができるため、演算量を低減することができる。
【００３０】
なお、本実施形態では演算量の低減を目的として範囲総和テーブルを用いてタイル分割を行うものとして説明するが、本発明の実施はこれに限られるものではない。即ち、分割後のタイルに含まれるフラグメント数の算出方法は、範囲総和テーブルを用いずにフラグメント数マップを参照して直接算出するものであってもよいし、その他の手法が用いられてもよいことは容易に理解されよう。
【００３１】
Ｓ３０３で、制御部１０１は、範囲総和テーブルを参照してタイリング処理を行う。なお、本実施形態ではタイリング処理は制御部１０１が行うものとして説明するが、描画部１０４が行ってもよい。
【００３２】
〈タイリング処理〉
以下、本ステップのタイリング処理について、図５のフローチャートを用いて詳細を説明する。本タイリング処理は、生成する矩形画像に対応するスクリーン座標系における２次元領域全体を未処理の初期タイルとして設定し、該タイルの情報を未確定タイルリストに追加した上で開始されるものとして説明する。
【００３３】
Ｓ５０１で、制御部１０１は、未確定タイルリストに未処理のタイルが存在するか否かを判断する。制御部１０１は、未確定タイルリストに未処理のタイルが存在すると判断した場合は処理をＳ５０２に移し、存在しないと判断した場合は本タイリング処理を完了する。
【００３４】
Ｓ５０２で、制御部１０１は、未確定タイルリストに含まれる未処理のタイル（選択タイル）の１つを選択する。本ステップで選択される未処理のタイルは、処理の開始時は初期タイルが選択される。また、制御部１０１は選択タイルの情報を未確定タイルリストから削除する。
【００３５】
Ｓ５０３で、制御部１０１は、選択タイルに含まれるフラグメント数が描画用メモリ１０５の予め定められた領域に格納可能なフラグメント数（限界フラグメント数）を上回るか否かを判断する。制御部１０１は、範囲総和テーブルを使用して、選択タイルに含まれるフラグメント数の総和を算出する。なお、選択タイルが水平座標及び垂直座標のいずれかが０である画素を含む場合は、範囲総和テーブルに含まれない範囲外の値を０として計算することで総和数は得ることができる。制御部１０１は、選択タイルに含まれるフラグメント数が限界フラグメント数を上回ると判断した場合は処理をＳ５０５に移す。また制御部１０１は、選択タイルに含まれるフラグメント数が限界フラグメント数を上回らないと判断した場合、Ｓ５０４で該タイルの情報を確定タイルリストに追加して処理をＳ５０１に戻す。
【００３６】
Ｓ５０５で、制御部１０１は、選択タイルのアスペクト比に基づいて選択タイルを分割する方向（分割方向）を決定し、該方向に直交する方向に選択タイルを２つのタイルに分割する直線（分割線）を定義する位置を決定する。分割方向の決定は、選択タイルの長手方向に決定される。即ち、分割後のタイルが正方形状に近くなるように分割方向は決定されるものであり、制御部１０１は選択タイルの水平方向及び垂直方向の画素数を比較して分割方向の決定を行う。例えば選択タイルが水平画素数７２０、垂直画素数５４０である場合、制御部１０１は水平方向に分割方向を決定する。なお、選択タイルが正方形状であった場合は分割方向はいずれの方向としてもよい。
【００３７】
また分割線を定義する位置（選択タイルの分割方向の座標）は、例えば選択タイルの長手方向の最小座標と最大座標とを初期値として二分法により決定すればよい。この場合、制御部１０１は最小座標と最大座標の中点に分割線を仮定義し、該分割線でタイルが分割された場合に分割後のタイルの各々に含まれるフラグメント数を範囲総和テーブルにより算出する。そしてフラグメント数の大小関係に応じて最小座標及び最大座標のいずれかを更新しながら、分割後のタイル間のフラグメント数の差が最小となる座標を特定し、該座標を分割線を定義する位置として決定する。即ち、本ステップの処理により、選択タイルに対して、分割後の各タイルに含まれるフラグメント数の差が最小となるような分割線の位置を決定できる。
【００３８】
Ｓ５０６で、制御部１０１は、決定された位置に分割線を定義し、該直線で選択タイルを異なる２つのタイルに分割する。そして得られた２つのタイルを未処理タイルとして未確定タイルリストに追加し処理をＳ５０１に戻す。
【００３９】
このように全てのタイルに含まれるフラグメント数が限界フラグメント数以下となるまでタイリング処理の各ステップを再帰的に行うことで、制御部１０１は、生成する矩形画像に対応するスクリーン座標系における２次元領域に、描画する処理単位のタイルを設定することができる。
【００４０】
Ｓ３０４で、描画部１０４は制御部１０１の制御の下、描画処理を行って矩形画像を生成する。描画処理は、タイリング処理により確定タイルリストに定義されたタイルを順に選択し、該タイルについてのリンクトリストを生成してピクセルごとにソート処理を行った後、シェーディング処理を行い、矩形画像の対応する画素を描画して出力することにより行われる。
【００４１】
このようにすることで、本実施形態のＰＣ１００では、所定の視点について対象シーンを矩形画像に描画する場合であっても、フラグメント数に基づいて好適にタイリングすることができる。
【００４２】
なお、本実施形態ではタイリング処理における分割線を決定するための処理を、分割後の各領域に含まれるフラグメント数の差が最小となるように行うものとして説明したが、本発明の実施はこれに限られるものではない。即ち、タイルの長手方向の画素数が大きい場合には、二分法の収束解が得られるまでに処理に時間を要する可能性があるため、例えば分割後の各領域に含まれるフラグメント数の差が所定の値以下となる分割線で分割するものとしてもよい。
【００４３】
また本実施形態では処理の効率性を考慮し、ｋｄ木を用いて水平軸あるいは垂直軸に直交する分割線を定義するものとして説明したが、本発明の実施はこれに限られるものではない。演算量は多くなるが、例えばＢＳＰ木を用いることで水平方向及び垂直方向に限らず分割線を定義してもよい。
【００４４】
また本実施形態ではｋｄ木を用いるため、再帰的にタイルを二分割することによりタイリング処理を行うものとして説明したが、本発明の実施はこれに限られるものではない。ｋｄ木では、分割後に定義されるタイルは２つに限られるが、例えばタイルに含まれるフラグメント数が限定フラグメント数の３倍に近いとみなされる数であれば、分割線を２本定義して３つのタイルに分割する等、１つのタイルは２以上のタイルに分割されるように構成してもよい。
【００４５】
また本実施形態では、対象タイルの２つの異なる辺上の点を通過する直線を分割線として１回のタイル分割を行うものとして説明したが、本発明の実施はこれに限られるものではない。分割線は直線に限らず、例えば途中で所定の角度に屈折するような折れ曲がり直線で規定されるものであってもよいし、曲線として規定されるものであってもよい。
【００４６】
以上説明したように、本実施形態の情報処理装置によれば、任意のアスペクト比の矩形領域について、フラグメント数を考慮した好適なタイリングを行うことができる。本実施形態の情報処理装置は、３次元シーンを所定の視点について描画する矩形画像の各画素と視点とで規定される直線上に存在するフラグメント数を取得し、矩形画像に対応するスクリーン座標系における２次元領域を、所定の演算を行う処理単位である複数の領域に分割する。情報処理装置は、分割後の各領域に含まれるフラグメント数の総和の差が最小となるような１以上の直線で、２次元領域を異なる領域に分割する。
【００４７】
［実施形態２］
上述した実施形態１では、タイリング処理により定義される各タイルの画素数は分割線を定義する位置に応じて決定されるため、様々な画素数を有するタイルが定義される可能性があった。一方で、描画処理において行われるソート処理は、予め定められた数の画素（例えば１６×１６）について並行して実行することが可能であるため、タイル内の画素数は該予め定められた数の倍数となっていることが好ましい。即ち、任意に決定された画素数のタイルでは、同時並行処理数未満の画素を対象としてソート処理を行う可能性がある。本実施形態では、描画処理における描画部１０４の並行処理能力を考慮して、描画処理が効率化される画素数となるようにタイリング処理を行う方法について説明する。
【００４８】
《描画処理》
以下、本実施形態のＰＣ１００において実行される描画処理について、図６のフローチャートを参照して詳細を説明する。なお、本実施形態のＰＣ１００の構成は実施形態１と同様であるものとする。また本実施形態の描画処理において実施形態１の描画処理と同様の処理を行うステップについては、同一の参照番号を付して説明を省略する。
【００４９】
Ｓ３０１において生成する矩形画像と同画素数のフラグメント数マップを生成した後、描画部１０４はＳ６０１で、フラグメント数マップを低解像度化する。該低解像度化は、例えば上述したように描画処理におけるソート処理の同時並行処理数を考慮して行われる。例えばソート処理を１６×１６画素について並行して実行可能に描画部１０４が構成される場合、７６８０×４３２０画素のフラグメント数マップは１６×１６画素の画素値の総和を変換後の画素値とするように処理され、４８０×２７０画素の低解像度フラグメント数マップに変換される。即ち、低解像度フラグメント数マップの１画素が矩形画像の１６×１６画素に対応しているため、低解像度フラグメント数マップを基準に分割を行えばタイルごとのソート処理を効率的に実行することができる。
【００５０】
Ｓ６０２で、描画部１０４は、生成した低解像度フラグメント数マップに基づいて範囲総和テーブルを構築してメモリ１０３に格納する。そしてＳ６０３で、制御部１０１は、低解像度フラグメント数マップについて構築された範囲総和テーブルを参照してタイリング処理を行う。
【００５１】
Ｓ６０４で、制御部１０１は、低解像度フラグメント数マップについて定義されたタイルに基づいて、矩形画像の対応画素を特定し、矩形画像の解像度でのタイルを定義する。
【００５２】
このようにすることで、描画処理が効率的に実行できるようにタイリング処理を行うことができる。またフラグメント数マップを低解像度化することにより、範囲総和テーブルの生成に係る演算量を低減することができる。
【００５３】
なお、本実施形態ではフラグメント数マップを生成した後に低解像度フラグメント数マップに変換する２パスの処理について説明したが、フラグメント数マップの生成を最初から低解像度となるように行ってもよい。即ち、矩形画像の各画素と視点とで規定される直線上のフラグメント数はカウントするが、低解像度フラグメント数マップの生成において対応する画素群のフラグメント数の総和を画素値とするように１パスで処理を行ってもよい。
【００５４】
［その他の実施形態］
本発明は上記実施の形態に制限されるものではなく、本発明の精神及び範囲から離脱することなく、様々な変更及び変形が可能である。また本発明に係る情報処理装置は、１以上のコンピュータを情報処理装置として機能させるプログラムによっても実現可能である。該プログラムは、コンピュータが読み取り可能な記録媒体に記録されることにより、あるいは電気通信回線を通じて、提供／配布することができる。
【符号の説明】
【００５５】
１００：ＰＣ
１０１：制御部
１０２：記憶媒体
１０３：メモリ
１０４：描画部
１０５：描画用メモリ
【図１】
2015210672.tif 000005
【図２】
2015210672.tif 000006
【図３】
2015210672.tif 000007
【図４】
2015210672.tif 000008
【図５】
2015210672.tif 000009
【図６】
2015210672.tif 000010