(57)【要約】【課題】  経路レンダリングを行う方法及びその装置を提供する。【解決手段】  レンダリングが行われる客体に含まれた頂点に係わる情報を含むデータを獲得する段階と、フレームに含まれたピクセルそれぞれの位置と、頂点が連結された少なくとも一つ以上の経路の進行方向との関係に基づいて、ピクセルそれぞれに対応する周回数を演算する段階と、周回数を利用して、ピクセルそれぞれにカラーを設定するか否かを決定する段階と、を含む経路レンダリングを行う方法である。【選択図】      図１
2015210816.tif 000002
【特許請求の範囲】
【請求項１】
レンダリングが行われる客体に含まれた頂点に係わる情報を含むデータを獲得する段階と、
フレームに含まれたピクセルそれぞれの位置と、前記頂点が連結された少なくとも一つ以上の経路の進行方向との関係に基づいて、前記ピクセルそれぞれに対応する周回数を演算する段階と、
前記周回数を利用して、前記ピクセルそれぞれにカラーを設定するか否かを決定する段階と、を含む経路レンダリングを行う方法。
【請求項２】
前記演算する段階は、前記ピクセルそれぞれの一つの側に位置する前記経路の進行方向を利用して、前記周回数を演算することを特徴とする請求項１に記載の方法。
【請求項３】
前記一つの側は、前記ピクセルそれぞれの位置を中心に、左側、右側、上側、下側のうちいずれか一つを含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記一つの側は、前記ピクセルそれぞれの位置と、前記少なくとも一つ以上の経路の位置とを考慮して決定されることを特徴とする請求項１乃至３のいずれか一項に記載の方法。
【請求項５】
前記演算する段階は、
前記ピクセルそれぞれの一つの側に、前記経路が位置するか否かを確認する段階と、
前記確認結果に基づいて、前記経路の進行方向が時計周り方向であるか、あるいは反時計周り方向であるかを決定する段階と、
前記決定された進行方向が時計周り方向である場合、既定値を増算し、前記決定された進行方向が反時計周り方向である場合、前記既定値を減算することにより、或いは、前記決定された進行方向が時計周り方向である場合、既定値を減算し、前記決定された進行方向が反時計周り方向である場合、前記既定値を増算することにより、前記周回数を演算する段階と、を含むことを特徴とする請求項１乃至４のいずれか一項に記載の方法。
【請求項６】
前記既定値は、１を含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記データに含まれた前記頂点それぞれの座標成分を利用して、前記フレームに境界ボックスを設定する段階と、をさらに含み、
前記演算する段階は、前記境界ボックスに含まれた前記ピクセルそれぞれに対応する周回数を演算することを特徴とする請求項１乃至６のいずれか一項に記載の方法。
【請求項８】
前記設定する段階は、
前記座標成分のうち、水平方向座標成分の最大値及び最小値、垂直方向座標成分の最大値及び最小値を利用して、前記フレームに、前記境界ボックスを設定することを特徴とする請求項９に記載の方法。
【請求項９】
前記境界ボックスは、前記水平方向座標成分の最大値、及び前記垂直方向座標成分の最大値によって形成された第１座標と、前記水平方向座標成分の最小値、及び前記垂直方向座標成分の最小値によって形成された第２座標と、を結ぶ線を対角線として含む四角形であることを特徴とする請求項８に記載の方法。
【請求項１０】
前記頂点は、前記少なくとも一つ以上の経路それぞれの開始位置に対応する頂点、及び終了位置に対応する頂点を含むことを特徴とする請求項１乃至９のいずれか一項に記載の方法。
【請求項１１】
前記決定する段階は、
既設定の規則に基づいて、前記カラーを設定するか否かを決定することを特徴とする請求項１乃至１０のいずれか一項に記載の方法。
【請求項１２】
前記既設定の規則は、前記周回数が０ではない値を有するピクセルに、カラー値を割り当てる第１規則、または前記周回数が奇数である値を有するピクセルに、カラー値を割り当てる第２規則を含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記決定結果に基づいて、前記ピクセルそれぞれにカラー値を設定する段階と、
前記ピクセルそれぞれのカラー値を保存する段階と、をさらに含むことを特徴とする請求項１乃至１２のいずれか一項に記載の方法。
【請求項１４】
請求項１乃至１３のいずれか一項に記載の方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能な記録媒体。
【請求項１５】
レンダリングが行われる客体に含まれた頂点に係わる情報を含むデータを獲得する獲得部と、
フレームに含まれたピクセルそれぞれの位置と、前記頂点が連結された少なくとも一つ以上の経路の進行方向との関係に基づいて、前記ピクセルそれぞれに対応する周回数を演算する演算部と、
前記周回数を利用して、前記ピクセルそれぞれにカラーを設定するか否かを決定する決定部と、を含む経路レンダリングを行う装置。
【請求項１６】
前記演算部は、前記ピクセルそれぞれの一つの側に位置する前記経路の進行方向を利用して、前記周回数を演算することを特徴とする請求項１５に記載の装置。
【請求項１７】
前記一つの側は、前記ピクセルそれぞれの位置を中心に、左側、右側、上側、下側のうちいずれか一つを含むことを特徴とする請求項１５又は１６に記載の装置。
【請求項１８】
前記演算部は、前記ピクセルそれぞれの位置と、前記少なくとも一つ以上の経路の位置とを考慮して、前記一つの側を決定することを特徴とする請求項１５乃至１７のいずれか一項に記載の方法。
【請求項１９】
前記演算部は、
前記ピクセルそれぞれの一つの側に、前記経路が位置するか否かを確認し、
前記確認結果に基づいて、前記経路の進行方向が時計周り方向であるか、あるいは反時計周り方向であるかを決定し、
前記決定された進行方向が時計周り方向である場合、既定値を増算し、前記決定された進行方向が反時計周り方向である場合、既定値を減算することにより、或いは、前記決定された進行方向が時計周り方向である場合、既定値を減算し、前記決定された進行方向が反時計周り方向である場合、前記既定値を増算することにより、前記周回数を演算することを特徴とする請求項１５乃至１８のいずれか一項に記載の装置。
【請求項２０】
前記既定値は、１を含むことを特徴とする請求項１９に記載の装置。
【請求項２１】
前記データに含まれた前記頂点それぞれの座標成分を利用して、前記フレームに境界ボックスを設定する設定部をさらに含み、
前記演算部は、前記境界ボックスに含まれた前記ピクセルそれぞれに対応する周回数を演算することを特徴とする請求項１５乃至２０のいずれか一項に記載の装置。
【請求項２２】
前記設定部は、
前記座標成分のうち、水平方向座標成分の最大値及び最小値、垂直方向座標成分の最大値及び最小値を利用して、前記フレームに、前記境界ボックスを設定することを特徴とする請求項２１に記載の装置。
【請求項２３】
前記境界ボックスは、前記水平方向座標成分の最大値、及び前記垂直方向座標成分の最大値によって形成された第１座標と、前記水平方向座標成分の最小値、及び前記垂直方向座標成分の最小値によって形成された第２座標と、を結ぶ線を対角線として含む四角形であることを特徴とする請求項２２に記載の装置。
【請求項２４】
前記頂点は、前記少なくとも一つ以上の経路それぞれの開始位置に対応する頂点、及び終了位置に対応する頂点を含むことを特徴とする請求項１５乃至２３のいずれか一項に記載の装置。
【請求項２５】
前記決定部は、
既設定の規則に基づいて、前記カラーを設定するか否かを決定することを特徴とする請求項１５乃至２４のいずれか一項に記載の装置。
【請求項２６】
前記既設定の規則は、前記周回数が０ではない値を有するピクセルに、前記カラー値を割り当てる第１規則、または前記周回数が奇数である値を有するピクセルに、前記カラー値を割り当てる第２規則を含むことを特徴とする請求項２５に記載の装置。
【請求項２７】
前記決定結果に基づいて、前記ピクセルそれぞれにカラー値を設定するピクセルシェーダと、
前記ピクセルそれぞれのカラー値を保存するフレームバッファと、をさらに含むことを特徴とする請求項１５乃至２６のいずれか一項に記載の装置。
【請求項２８】
経路レンダリングを行うグラフィック処理装置（ＧＰＵ）に連結され、フレームに含まれたピクセルそれぞれの周回数を生成する装置において、
前記グラフィック処理装置から、少なくとも一つ以上の経路に対応する頂点それぞれの座標に係わる情報、及び前記フレームに含まれたピクセルの座標に係わる情報を受信し、
前記受信された情報を利用して、前記ピクセルに対応する周回数を演算し、
前記演算された周回数を前記グラフィック処理装置に出力する装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路レンダリングを行う方法及びその装置に関する。
【背景技術】
【０００２】
最近、ベクトルグラフィックスまたは経路レンダリングを行う場合、グラフィック処理装置（ＧＰＵ：graphics  processing  unit）の加速性能を向上させるための方法が研究されている。ただし、三次元グラフィックを加速させるために、全ての入力データが三角形によって構成されるという仮定の下でＧＰＵのハードウェア構造が設計されるが、経路レンダリングの場合、入力データが三角形によって構成されず、コマンドと頂点との組み合わせによって構成されている。従って、経路レンダリングを行うとき、ＧＰＵの加速性能を向上させ難い。
【０００３】
例えば、ＧＰＵを利用して、１つの曲線を描くためには、まず、ＣＰＵが曲線の開始点を中心にして曲線を多数の三角形に分割し、OpenＧＬ  ＡＰＩを利用して、ＧＰＵに、分割された三角形を曲線に再構成するように指示する。従って、ＣＰＵが曲線を多数の三角形に分割するのに長時間かかり、多数のOpenＧＬ  ＡＰＩを呼び出すごとに、ＧＰＵとの通信が必要であり、ＧＰＵ上で多くの状態変化が発生する。
【０００４】
従って、ＧＰＵ内に存在するステンシルバッファを利用するステンシル基盤の経路レンダリング（stencil-based path  rendering）法が提案された。しかし、ステンシル基盤の経路レンダリング法は、レンダリング遂行中に、メモリ入出力が過度に発生し、ステンシルバッファは、並列処理が不可能であり、ＧＰＵの加速性能を向上させるのに限界が存在する。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明が解決しようとする課題は、経路レンダリングを行う方法及びその装置を提供するところにある。本発明が解決しようとする課題はまた、前記方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能な記録媒体を提供するところにある。
【０００６】
本実施例がなすべき技術的課題は、前述のような技術的課題に限定されるものではなく、以下の実施形態から他の技術的課題も類推される。
【課題を解決するための手段】
【０００７】
一つの側による経路レンダリングを行う方法は、レンダリングが行われる客体に含まれた頂点に係わる情報を含むデータを獲得する段階と、フレームに含まれたピクセルそれぞれの位置と、前記頂点が連結された少なくとも一つ以上の経路の進行方向との関係に基づいて、前記ピクセルそれぞれに対応する周回数（winding  number）を演算する段階と、前記周回数を利用して、前記ピクセルそれぞれにカラーを設定するか否かを決定する段階と、を含む。
【０００８】
他の側面による記録媒体は、前述の方法をコンピュータで実行させるためのプログラムを記録した記録媒体を含む。
【０００９】
さらに他の側面による経路レンダリングを行う装置は、レンダリングが行われる客体に含まれた頂点に係わる情報を含むデータを獲得する獲得部と、フレームに含まれたピクセルそれぞれの位置と、前記頂点が連結された少なくとも一つ以上の経路の進行方向との関係に基づいて、前記ピクセルそれぞれに対応する周回数を演算する演算部と、前記周回数を利用して、前記ピクセルそれぞれにカラーを設定するか否かを決定する決定部と、を含む。
【００１０】
さらに他の側面による経路レンダリングを行うグラフィック処理装置に連結され、フレームに含まれたピクセルそれぞれの周回数を生成する装置は、前記グラフィック処理装置から少なくとも一つ以上の経路に対応する頂点それぞれの座標に係わる情報、及び前記フレームに含まれたピクセルの座標に係わる情報を受信し、前記受信された情報を利用して、前記ピクセルに対応する周回数を演算し、前記演算された周回数を前記グラフィック処理装置に伝達する。
【発明の効果】
【００１１】
本発明によれば、ステンシルバッファの使用なしに、経路レンダリングが行われ、ステンシルバッファを使用することによってメモリ入出力が過度に発生するという問題と、重複されたメモリ入出力が発生するという問題とが解消される。
【００１２】
また、本発明によれば、フレームに含まれたピクセルそれぞれに対して、並列的に周回数を生成することにより、高速で経路レンダリングが行われ、短時間内に高解像度のレンダリングが行われる。
【図面の簡単な説明】
【００１３】
【図１】一実施形態による経路レンダリングを行う装置の一例を図示した構成図である。
【図２】一実施形態による周回数について説明するための図面である。
【図３Ａ】一実施形態による演算部が周回数を演算する一例について説明するための図面である。
【図３Ｂ】一実施形態による演算部が周回数を演算する一例について説明するための図面である。
【図４Ａ】一実施形態による演算部が、互いに異なる側面を選択してピクセルの周回数を演算する一例について説明するための図面である。
【図４Ｂ】一実施形態による演算部が、互いに異なる側面を選択してピクセルの周回数を演算する一例について説明するための図面である。
【図４Ｃ】一実施形態による演算部が、互いに異なる側面を選択してピクセルの周回数を演算する一例について説明するための図面である。
【図４Ｄ】一実施形態による演算部が、互いに異なる側面を選択してピクセルの周回数を演算する一例について説明するための図面である。
【図５】一実施形態による演算部が、ピクセルの周回数を演算するアルゴリズムの一例を記載した図面である。
【図６】一実施形態による決定部が、ピクセルそれぞれにカラーを設定するか否かを決定する一例について説明するための図面である。
【図７】一実施形態による経路レンダリングを行う装置の他の例を図示した構成図である。
【図８】一実施形態による設定部が境界ボックスを設定する一例について説明するための図面である。
【図９】一実施形態による周回数生成装置の一例について説明するための図面である。
【図１０】一実施形態による演算部及び周回数生成装置が動作する一例について説明するための図面である。
【図１１】一実施形態によるピクセルの周回数を演算する方法が、グラフィック処理装置で具現される一例について説明するための図面である。
【図１２】一実施形態によるバーテックスシェーダがピクセル・オーナーシップ・テストを行う一例について説明するためのフローチャートである。
【図１３】一実施形態による周回数生成装置が動作する一例について説明するためのフローチャートである。
【図１４】一実施形態による周回数生成装置が、ピクセルの一つの側に経路が位置するか否かを判断する一例について説明するためのフローチャートである。
【図１５】一実施形態による経路レンダリングを行う方法の一例について説明するためのフローチャートである。
【発明を実施するための形態】
【００１４】
以下、図面を参照し、本発明の実施形態について詳細に説明する。本発明の下記実施形態は、本発明を具体化するためのものであり、本発明の権利範囲を制限したり、あるいは限定したりするものではない。また、本発明の詳細な説明及び実施形態から、本発明が属する技術分野で当業者が容易に類推することができるものは、本発明の権利範囲に属するものであると解釈される。
【００１５】
図１は、一実施形態による経路レンダリングを行う装置１００の一例を図示した構成図である。図１を参照すれば、経路レンダリングを行う装置１００は、獲得部１１０、演算部１２０及び決定部１３０を含む。図１に図示された経路レンダリングを行う装置１００には、本実施形態に係わる構成要素だけが図示されている。従って、図１に図示された構成要素以外に、他の汎用的な構成要素がさらに含まれてもよい。
【００１６】
また、図１に図示された経路レンダリングを行う装置１００の獲得部１１０、演算部１２０及び決定部１３０は、一つまたは複数のプロセッサにも該当する。プロセッサは、多数の論理ゲートのアレイによって具現され、汎用的なマイクロプロセッサと、該マイクロプロセッサで実行されるプログラムが保存されたメモリとの組み合わせによって具現される。また、他の形態のハードウェアによっても具現されるということは、本実施形態が属する技術分野で当業者であるならば、理解することができるであろう。
【００１７】
獲得部１１０は、レンダリングが行われる客体に含まれた頂点に係わる情報を含むデータを獲得する。客体は、レンダリングが行われる少なくとも一つ以上の経路を含む。また、客体は、少なくとも一つ以上の経路が連結されて形成された閉多角形または閉経路を含んでもよい。ここで、経路は、一地点から他の地点まで続く直線または曲線を意味する。
【００１８】
獲得部１１０が獲得するデータには、頂点それぞれの座標に係わる情報、及び頂点を組み合わせて経路を構成するためのコマンドが含まれる。ここで、頂点は、経路の開始位置に対応する頂点、または経路の終了位置に対応する頂点を含む。
【００１９】
例えば、フレームに含まれたピクセルのうち、第１ピクセルから第２ピクセルまでの直線を経路であると仮定すれば、頂点は、フレームにおいて、第１ピクセル及び第２ピクセルのそれぞれに対応する地点を意味する。従って、獲得部１１０が獲得するデータは、第１ピクセルに対応する第１頂点の座標、第２ピクセルに対応する第２ピクセルの座標、及び第１頂点から第２頂点まで直線を構成せよとするコマンドを含む。従って、データを参照すれば、経路を構成する頂点それぞれの座標に係わる情報だけではなく、経路の方向に係わる情報も把握される。また、データには、それぞれのピクセルに設定されるカラー値に係わる情報も含まれる。
【００２０】
演算部１２０は、フレームに含まれたピクセルそれぞれの位置と、頂点を連結する少なくとも一つ以上の経路の進行方向との関係に基づいて、ピクセルそれぞれに対応する周回数を演算する。
【００２１】
ここで、周回数は、特定ピクセルの位置から一つの側を見るとき、経路が描かれる間、何周回転するかを示す既定値Ｎを意味する。あるいは、周回数は、特定ピクセルの位置を端点とする半直線を考えるとき、経路が描かれる間、この半直線を横切る又は通過する又は交差する回数に基づき算出される値を意味しても良い。
【００２２】
周回数は、経路が時計周り方向に回転する場合には、既定値Ｎを増算し、経路が反時計周り方向に回転する場合には、既定値Ｎを減算することによって演算されるが、それに限定されるものではない。言い換えれば、周回数は、経路が時計周り方向に回転する場合には、既定値Ｎを減算し、経路が反時計周り方向に回転する場合には、既定値Ｎを増算することによって演算されもする。
【００２３】
一例として、経路が時計周り方向に１周回転するならば、ピクセルの周回数は、＋１にもなる。このとき、経路が反時計周り方向に１周回転するならば、ピクセルの周回数は、−１にもなる。
【００２４】
他の例として、経路が時計周り方向に１周回転するならば、ピクセルの周回数は、−１になる。このとき、経路が反時計周り方向に１周回転するならば、ピクセルの周回数は、＋１にもなる。
【００２５】
また、既定値Ｎは整数にもなるが、それに限定されるものではない。言い換えれば、周回数は、特定ピクセルの位置から一つの側を見るとき、経路が描かれる間の回転数にマッピングされた数であるならば、制限なしに該当する。
【００２６】
一例として、経路が時計周り方向に１周回転するならば、ピクセルの周回数は、＋０．１にもなる。このとき、経路が反時計周り方向に１周回転するならば、ピクセルの周回数は、−０．１にもなる。
【００２７】
他の例として、経路が時計周り方向に１周回転するならば、ピクセルの周回数は、−０．５にもなる。このとき、経路が反時計周り方向に１周回転するならば、ピクセルの周回数は、＋０．５にもなる。
【００２８】
更に他の例では、周回数として任意の数値が割り当てられても良い。
【００２９】
以下、説明の便宜のために、経路が時計周り方向に１周回転する場合の周回数が＋１、経路が反時計周り方向に１周回転する場合の周回数が−１になると仮定して説明する。ここで、経路は、閉多角形または閉経路にもなることは、前述の通りである。以下、図２を参照し、周回数について詳細に説明する。
【００３０】
図２は、一実施形態による周回数について説明するための図面である。図２には、フレームに含まれたピクセルのうちいずれか１つのピクセル２１０に対応する周回数について説明するための一例が図示されている。図２を参照すれば、ピクセル２１０の周辺に沿って、経路２３０が図示されており、経路２３０は、閉経路であるように図示されている。図２には、ピクセル２１０の周回数が、ピクセル２１０の右側に位置した経路２３０を利用して演算されるように図示されているが、必ずしも右側に限定されるものではない。また、以下で、ピクセル２１０の右側位置は、ピクセル２１０から右側水平方向に引かれた仮想の半直線２２０に含まれた地点の位置を意味する。
【００３１】
ピクセル２１０から右側水平方向に仮想線２２０を図示すれば、仮想の半直線２２０と経路２３０は、総４個の頂点２３１，２３２，２３３，２３４で交差する。言い換えれば、経路２３０は、４個の頂点２３１，２３２，２３３，２３４を含むように描かれる。従って、ピクセル２１０の周回数は、４個の頂点２３１，２３２，２３３，２３４それぞれでの経路が描かれる方向に基づいて決定される。
【００３２】
具体的には、第１頂点２３１において、経路２３０が描かれる方向は、反時計周り方向に該当する。従って、一次的にピクセル２１０の周回数は、−１になる。そして、第２頂点２３２において、経路２３０が描かれる方向は、時計周り方向に該当する。従って、二次的にピクセル２１０の周回数は、−１＋１＝０と演算される。そして、第３頂点２３３において、経路２３０が描かれる方向は、反時計周り方向に該当する。従って、三次的にピクセル２１０の周回数は、−１＋１−１＝−１と演算される。そして、第４頂点２３４において、経路２３０が描かれる方向は、反時計周り方向に該当する。従って、最終的にピクセル２１０の周回数は、−１＋１−１−１＝−２と演算される。
【００３３】
再び図１を参照すれば、演算部１２０は、フレームに含まれたピクセルの一つの側に位置した経路に対して周回数を演算する。ここで、一つの側は、ピクセルの位置を中心に、左側、右側、上側及び下側のうちいずれか一つに該当する。また、演算部１２０は、経路の位置だけではなく、経路の進行方向を考慮して、周回数を演算する。このとき、演算部１２０は、ステンシルバッファを利用せずに、周回数を演算することができる。
【００３４】
一般的に、レンダリング装置（例えば、グラフィック処理装置（ＧＰＵ））は、ステンシルバッファを利用してレンダリングを行う。具体的には、レンダリング装置は、客体を構成する経路に含まれた頂点を分析し、三角形を構成する。言い換えれば、レンダリング装置は、連続した３個の頂点を連結することにより、経路に含まれた三角形を生成する。その後、レンダリング装置は、生成された三角形をステンシルバッファに順次に記録する。このとき、レンダリング装置は、三角形内部に含まれたピクセルそれぞれの周回数を決定し、周回数が決定される過程及び最終周回数は、ステンシルバッファに記録される。そして、レンダリング装置は、ステンシルバッファに記録された周回数を利用してピクセル処理を行う。
【００３５】
従って、レンダリング装置が、ステンシルバッファを利用して、客体のレンダリングを行う場合、ステンシルバッファのデータ入出力が多く発生する。具体的には、レンダリング装置が客体を含む三角形を描くたびに、ステンシルバッファのデータ入出力が発生するので、複雑な形態に形成された経路であればあるほど、レンダリング装置がレンダリングを行うときのステンシルバッファのデータ入出力は著しく増加する。また、ステンシルバッファには、同時に複数の三角形を描く並列処理が不可能である。従って、ステンシルバッファには、複数の三角形が順次に描かれなければならないので、三角形の数が多くなるほど、レンダリング装置がレンダリングを行うのにかかる時間が著しく延長される。
【００３６】
本発明の一実施形態による演算部１２０は、ステンシルバッファを利用せず、フレームに含まれたピクセルそれぞれの周回数を演算する。言い換えれば、演算部１２０は、客体を含む三角形をステンシルバッファに描かず、フレームに含まれたピクセルそれぞれの周回数を演算する。従って、ステンシルバッファに基づいたレンダリングで示されるデータ入出力が増加されるという問題、及びレンダリングにかかる時間が延長されるという問題を解消することができる。
【００３７】
また、本発明の一実施形態による演算部１２０は、複数のスレッドを利用して周回数を演算する。言い換えれば、演算部１２０は、単一スレッドを利用して、単一ピクセルの周回数を演算することができる。このとき、複数のスレッドは、並列的な処理が可能であるので、演算部１２０は、複数のスレッドを利用して、複数のピクセルそれぞれに対する周回数を同時に演算することができる。従って、経路レンダリングを行う装置１００は、高速で経路レンダリングを行うことができる。
【００３８】
以下では、説明の便宜のために、演算部１２０が、１つのスレッドを利用して、フレームに含まれたピクセルのうちいずれか１つの周回数を演算する方法について説明する。従って、以下で言及されていないとしても、演算部１２０が複数のスレッドを利用して、複数のピクセルそれぞれの周回数を同時に演算することができるということは、当技術分野で当業者であるならば、理解することができるであろう。
【００３９】
以下、図３Ａ及び図３Ｂを参照し、演算部１２０が周回数を演算する一例について詳細に説明する。
【００４０】
図３Ａ及び図３Ｂは、一実施形態による演算部１２０が周回数を演算する一例について説明するための図面である。
【００４１】
図３Ａには、頂点１、頂点２及び頂点３が含まれた客体３１０が図示されている。具体的には、図３Ａに図示された客体３１０は、頂点１から頂点２までの第１経路、頂点２から頂点３までの第２経路、及び頂点３から頂点１までの第３経路によって構成される。
【００４２】
獲得部１１０が獲得したデータには、客体３１０に含まれた頂点１、頂点２及び頂点３に係わる情報が含まれている。具体的には、データには、頂点１の座標、頂点２の座標及び頂点３の座標が含まれる。また、データには、客体を構成する経路の開始点を示す頂点と、終了点を示す頂点とが何であるかに係わる情報も含まれる。言い換えれば、客体３１０に含まれた第１経路の開始点は、頂点１であり、終了点は、頂点２であるという情報、第２経路の開始点は、頂点２であり、終了点は、頂点３であるとという情報、第３経路の開始点は、頂点３であり、終了点は、頂点１であるという情報が含まれる。従って、データに含まれた頂点に係わる情報に基づいて、経路の進行方向が把握される。
【００４３】
演算部１２０は、フレームに含まれたピクセルそれぞれの位置を中心に、一つの側に経路が位置するか否かを確認する。ここで、一つの側はピクセルの位置を中心に、左側、右側、上側及び下側のうちいずれか一つを意味する。以下では、説明の便宜のために、演算部１２０がピクセルＰ１の位置を中心に、右側に経路が位置するか否かを確認すると仮定して説明する。
【００４４】
演算部１２０は、確認結果に基づいて、経路の進行方向が時計周り方向であるか、あるいは反時計周り方向であるかを決定する。例えば、演算部１２０が、ピクセルＰ１の右側に経路が位置すると判断した場合には、演算部１２０は、経路の進行方向が時計周り方向であるか、あるいは反時計周り方向であるかを決定する。一方、演算部１２０が、ピクセルＰ１の右側に経路が位置しないと判断した場合には、演算部１２０は、ピクセルＰ１の周回数を０と決定する。
【００４５】
具体的には、演算部１２０は、客体３１０を構成する３個の経路のうち、ピクセルＰ１の右側に位置する第２経路の進行方向が時計周り方向であるか、あるいは反時計周り方向であるかを決定する。言い換えれば、第１経路と第３経路は、ピクセルＰ１の右側に位置しないので、演算部１２０は、第１経路と第３経路との進行方向を決定せず、第２経路の進行方向のみを決定する。ここで、第２経路は、頂点２から頂点３まで進むので、演算部１２０は、第２経路の進行方向が時計周り方向であると決定する。
【００４６】
その後、演算部１２０は、進行方向が時計周り方向である場合、周回数に既定値Ｎを増算し、進行方向が反時計周り方向である場合、周回数に既定値Ｎを減算することによって、ピクセルＰ１の周回数を決定する。ここで、既定値Ｎは、１にもなるが、それに限定されるものではないということは、図１を参照して説明した通りである。
【００４７】
もし既定値Ｎが１であると仮定すれば、演算部１２０は、第２経路の進行方向が時計周り方向であると決定したので、演算部１２０は、ピクセルＰ１の周回数を＋１と決定する。
【００４８】
前述の方法のように、演算部１２０がフレームに含まれたピクセルそれぞれに対して周回数を演算する場合、図３Ａに図示された客体３１０の内部に存在するピクセルの周回数は、いずれも＋１に決定され、客体３１０の外部に存在するピクセルの周回数は、いずれも０と決定される。
【００４９】
また、演算部１２０は、進行方向が時計周り方向である場合、周回数に既定値Ｎを減算し、進行方向が反時計周り方向である場合、周回数に既定値Ｎを増算することによって、ピクセルＰ１の周回数を決定することもできる。ここで、既定値Ｎは、１にもなるが、それに限定されるものではないということは、図１を参照して説明した通りである。
【００５０】
もし既定値Ｎが０．１であると仮定すれば、演算部１２０は、第２経路の進行方向が時計周り方向であると決定したので、演算部１２０は、ピクセルＰ１の周回数を−０．１と決定する。
【００５１】
前述の方法のように、演算部１２０がフレームに含まれたピクセルそれぞれに対して周回数を演算する場合、図３Ａに図示された客体３１０の内部に存在するピクセルの周回数は、いずれも−０．１に決定され、客体３１０の外部に存在するピクセルの周回数は、いずれも０と決定される。
【００５２】
以下では、説明の便宜のために、演算部１２０が、ピクセルの周回数を決定するとき、経路の進行方向が時計周り方向である場合、周回数に１を増算し、進行方向が反時計周り方向である場合、周回数に１を減算すると仮定して説明する。
【００５３】
図３Ｂには、頂点１、頂点２、頂点３及び頂点４で構成された第１客体３２０、並びに頂点５、頂点６、頂点７及び頂点８で構成された第２客体３３０が図示されている。具体的には、第１客体３２０は、頂点１から頂点２までの第１経路、頂点２から頂点３までの第２経路、頂点３から頂点４までの第３経路、及び頂点４から頂点１までの第４経路によって構成される。また、第２客体３３０は、頂点５から頂点６までの第５経路、頂点６から頂点７までの第６経路、頂点７から頂点８までの第７経路、及び頂点８から頂点５までの第８経路によって構成される。
【００５４】
獲得部１１０が獲得したデータには、第１客体３２０及び第２客体３３０を構成する経路それぞれの開始点を示す頂点と、終了点を示す頂点とに係わる情報が含まれているということは、前述の通りである。
【００５５】
以下では、説明の便宜のために、演算部１２０がピクセルＰ２またはＰ３の位置を中心に、右側に経路が位置するか否かを確認すると仮定して説明する。
【００５６】
一例として、演算部１２０がピクセルＰ２の周回数を演算する方法について説明する。
【００５７】
演算部１２０は、ピクセルＰ２の位置を中心に、右側に経路が存在するか否かを確認する。具体的には、演算部１２０は、ピクセルＰ２の右側には、第１客体３５０に含まれた第３経路が存在するということを確認する。
【００５８】
演算部１２０は、確認結果に基づいて、経路の進行方向が時計周り方向であるか、あるいは反時計周り方向であるかを決定する。具体的には、演算部１２０は、第３経路の進行方向が時計周り方向であると決定する。
【００５９】
演算部１２０は、第３経路の進行方向が時計周り方向であると決定したので、演算部１２０は、ピクセルＰ２の周回数を＋１と決定する。
【００６０】
他の例として、演算部１２０がピクセルＰ３の周回数を演算する方法について説明する。
【００６１】
演算部１２０は、ピクセルＰ３の右側には、第２客体３３０に含まれた第６経路と、第１客体３２０に含まれた第３経路とが存在するということを確認する。その後、演算部１２０は、第６経路の進行方向が反時計周り方向であり、第３経路の進行方向が時計周り方向であると決定する。演算部１２０は、第６経路の進行方向が反時計周り方向であると決定したので、演算部１２０は、一次的に、ピクセルＰ３の周回数を−１と決定する。そして、演算部１２０は、第３経路の進行方向が時計周り方向であると決定したので、演算部１２０は、最終的に、ピクセルＰ３の周回数を−１＋１＝０と演算する。
【００６２】
前述の方法のように、演算部１２０がフレームに含まれたピクセルそれぞれに対して周回数を演算する場合、図３Ｂに図示された第１客体３２０の内部であり、第２客体３３０の外部に存在するピクセルの周回数は、いずれも＋１に決定され、第２客体３３０の内部に存在するピクセルの周回数は、いずれも０と決定される。
【００６３】
一方、演算部１２０がピクセルの位置を中心に、左側、右側、上側及び下側のうちいずれの側面を選択して周回数を演算しても、その結果は、いずれも同一である。以下、図４Ａないし図４Ｄを参照し、演算部１２０が互いに異なる側面を選択してピクセルの周回数を演算する一例について説明する。
【００６４】
図４Ａないし図４Ｄは、一実施形態による演算部１２０が互いに異なる側面を選択し、ピクセルの周回数を演算する一例について説明するための図面である。
【００６５】
図４Ａないし図４Ｄには、頂点１ないし頂点５から構成された客体が図示されている。図４Ａないし図４Ｄに図示された客体は、星状閉多角形であって、いずれも同一である。
【００６６】
図４Ａを参照すれば、演算部１２０は、ピクセルＰの位置を中心に、右側に経路が位置するか否かを確認する。具体的には、演算部１２０は、ピクセルＰの右側（例えば、ピクセルＰの右側水平方向に引いた仮想の半直線上の位置）には、頂点２から頂点３までの経路と、頂点５から頂点１までの経路とが存在するということを確認する。頂点２から頂点３までの経路の進行方向と、頂点５から頂点１までの経路の進行方向は、いずれも時計周り方向であるので、演算部１２０は、ピクセルＰの周回数を＋２と演算する。
【００６７】
図４Ｂを参照すれば、演算部１２０は、ピクセルＰの位置を中心に、左側に経路が位置するか否かを確認する。具体的には、演算部１２０は、ピクセルＰの左側（例えば、ピクセルＰの左側水平方向に引いた仮想の半直線上の位置）には、頂点１から頂点２までの経路と、頂点３から頂点４までの経路とが存在するということを確認する。頂点１から頂点２までの経路の進行方向と、頂点３から頂点４までの経路の進行方向は、いずれも時計周り方向であるので、演算部１２０は、ピクセルＰの周回数を＋２と演算する。
【００６８】
図４Ｃを参照すれば、演算部１２０は、ピクセルＰの位置を中心に、上側に経路が位置するか否かを確認する。具体的には、演算部１２０は、ピクセルＰの上側（例えば、ピクセルＰの上側水平方向に引いた仮想の半直線上の位置）には、頂点２から頂点３までの経路と、頂点４から頂点５までの経路とが存在するということを確認する。頂点２から頂点３までの経路の進行方向と、頂点４から頂点５までの経路の進行方向は、いずれも時計周り方向であるので、演算部１２０は、ピクセルＰの周回数を＋２と演算する。
【００６９】
図４Ｄを参照すれば、演算部１２０は、ピクセルＰの位置を中心に、下側に経路が位置するか否かを確認する。具体的には、演算部１２０は、ピクセルＰの下側（例えば、ピクセルＰの下側水平方向に引いた仮想の半直線上の位置）には、頂点５から頂点１までの経路と、頂点３から頂点４までの経路とが存在するということを確認する。頂点５から頂点１までの経路の進行方向と、頂点３から頂点４までの経路の進行方向は、いずれも時計周り方向であるので、演算部１２０は、ピクセルＰの周回数を＋２と演算する。
【００７０】
前述のところのように、演算部１２０が、ピクセルＰの位置を中心に、いずれの側面を選択して周回数を演算しても、その結果は、いずれも同一である。また、図４Ａないし図４Ｄに図示されているように、経路によって区分された領域のうち、同一の領域内に存在するピクセルの周回数は、いずれも同一である。
【００７１】
演算部１２０は、ピクセルの位置及び経路の位置を考慮して、フレームに含まれたピクセルごとに、それぞれ周回数を演算する一つの側を決定することができる。言い換えれば、演算部１２０は、ピクセルＰの位置を中心に、いずれの側面を選択して周回数を演算するか否か、ピクセルＰの位置によって互いに異なるように決定することもできる。すなわち、ピクセルＰの位置を基準に、最も小さい数の経路が存在すると予想される方向に、周回数を演算する一つの側を決定することができる。
【００７２】
例えば、ピクセルＰがフレームの中心線を基準に、左側に存在すると仮定すれば、演算部１２０が周回数を演算する一つの側を、ピクセルＰの右側面よりは左側面を選択すると演算部１２０がさらに小さい数の経路を利用してピクセルＰの周回数を演算することができる。また、ピクセルＰがフレームの中心線を基準に、右側に存在すると仮定すれば、演算部１２０が周回数を演算する一つの側をピクセルＰの左側面よりは右側面を選択してこそ、演算部１２０がさらに小さい数の経路を利用して、ピクセルＰの周回数を演算することができる。
【００７３】
従って、演算部１２０は、フレームに含まれたピクセルごとに、それぞれ互いに異なる側面を決定して、周回数を演算することができる。このとき、演算部１２０は、フレーム内において客体を構成する経路が、いずれの位置に分布するかを判断し、演算部１２０は、周回数が演算されるピクセルの位置を中心に、最小の経路が存在する方向に、周回数の演算に利用される一つの側を選択する。
【００７４】
図５は、一実施形態によるピクセルの周回数を演算するアルゴリズムの一例を記載した図面である。
【００７５】
図５に図示されたアルゴリズムは、ピクセルの右側に経路が位置するか否かに基づいて、周回数を演算する方法に係わる。ただし、ピクセルの右側ではない他の側面に基づいて、周回数が演算されもするということは、前述の通りである。また、図５に記載したアルゴリズムと同一の結果が出力されるアルゴリズムであるならば、制限なしに適用される。
【００７６】
再び図１を参照すれば、決定部１３０は、演算部１２０によって演算された周回数を利用して、ピクセルそれぞれにカラーを設定するか否かを決定する。言い換えれば、決定部１３０は、演算部１２０によって演算されたピクセルそれぞれの周回数を利用して、ピクセルそれぞれにカラーを設定するか否かを決定する。例えば、決定部１３０は、既設定の規則に基づいて、ピクセルそれぞれにカラーを設定するか否かを決定することができる。ここで、既設定の規則は、周回数が０ではない値を有するピクセルにカラー値を割り当てる第１規則、または周回数が奇数である値を有するピクセルにカラー値を割り当てる第２規則のうちいずれか一つを意味する。以下、図６の６Ａないし６Ｃを参照し、決定部１３０が動作する一例について説明する。
【００７７】
図６の６Ａないし６Ｃは、一実施形態による決定部１３０が、ピクセルそれぞれにカラーを設定するか否かを決定する一例について説明するための図面である。
【００７８】
図６の６Ａは、演算部１２０がフレーム６１０に含まれたピクセルそれぞれに対して、周回数を演算した結果を図示した図面であり、図６の６Ｂは、第１規則によって、ピクセルそれぞれにカラー値が割り当てられた結果を図示した図面である。また、図６の６Ｃは、第２規則によって、ピクセルそれぞれにカラー値が割り当てられた結果を図示した図面である。
【００７９】
図６の６Ａを参照すれば、フレーム６１０に含まれたピクセルそれぞれに対して、周回数が演算されている。具体的には、領域６１１に含まれたピクセルは、それぞれ周回数が０と演算されており、領域６１２に含まれたピクセルは、それぞれ周回数が＋１と演算されており、領域６１３に含まれたピクセルは、それぞれ周回数が＋２と演算されている。
【００８０】
一例として、決定部１３０は、第１規則に基づいて、ピクセルそれぞれにカラーを設定するか否かを決定することができる。ここで、第１規則は、周回数が０ではない値を有するピクセルにカラー値を割り当てるということを意味する。図６の６Ｂを参照すれば、第１規則による場合、決定部１３０は、図６の６Ａに図示された領域６１２及び領域６１３に含まれたピクセルには、カラーを設定し、領域６１１に含まれたピクセルには、カラーを設定しないと決定する。
【００８１】
他の例として、決定部１３０は、第２規則に基づいて、ピクセルそれぞれにカラーを設定するか否かを決定することができる。ここで、第２規則は、周回数が奇数である値を有するピクセルにカラー値を割り当てるということを意味する。ここで、奇数は、ピクセルの周回数の絶対値が奇数である場合を意味する。例えば、周回数が＋３である場合も、奇数であると判断され、周回数が−３である場合も、奇数であると判断される。図６の６Ｃを参照すれば、第２規則による場合、決定部１３０は、図６の６Ａに図示された領域６１２に含まれたピクセルにはカラーを設定し、領域６１１及び領域６１３に含まれたピクセルには、カラーを設定しないと決定する。
【００８２】
決定部１３０は、カラーを設定すると決定したピクセルに係わる情報をピクセルシェーダで伝送し、ピクセルシェーダは、決定部１３０がカラーを設定すると決定したピクセルにカラー値を割り当てる。
【００８３】
前述のところによれば、経路レンダリングを行う装置１００は、ステンシルバッファの使用なしに、ピクセルそれぞれの周回数を演算することができるが、ステンシルバッファを使用することによって、メモリ入出力が過度に発生するという問題と、重複されたメモリ入出力が発生するという問題とが解消される。
【００８４】
また、経路レンダリングを行う装置１００は、フレームに含まれたピクセルそれぞれに対して、並列的に周回数を生成することにより、高速で経路レンダリングを行うことができ、短時間内に高解像度のレンダリングを行うことができる。
【００８５】
図７は、一実施形態による経路レンダリングを行う装置の他の例（１０１）を図示した構成図である。図７を参照すれば、経路レンダリングを行う装置１０１は、獲得部１１０、設定部１４０、演算部１２０及び決定部１３０を含む。図７に図示された経路レンダリングを行う装置１０１には、本実施形態に係わる構成要素だけが図示されている。従って、図７に図示された構成要素以外に、他の汎用的な構成要素がさらに含まれもする。
【００８６】
また、図７に図示された経路レンダリングを行う装置１０１の獲得部１１０、設定部１４０、演算部１２０及び決定部１３０は、一つまたは複数のプロセッサにも該当する。プロセッサは、多数の論理ゲートのアレイによって具現され、汎用的なマイクロプロセッサと、該マイクロプロセッサで実行されるプログラムが保存されたメモリとの組み合わせによって具現されもする。また、他の形態のハードウェアによって具現されもするということは、本実施形態が属する技術分野で当業者であるならば、理解することができるであろう。
【００８７】
また、図７に図示された経路レンダリングを行う装置１０１の獲得部１１０、演算部１２０及び決定部１３０の動作は、図１から図６の６Ａないし６Ｃを参照して説明した通りである。従って、以下では、獲得部１１０、演算部１２０及び決定部１３０の具体的な動作に係わる説明は省略する。
【００８８】
設定部１４０は、頂点それぞれの座標成分を利用して、フレームに境界ボックスを設定する。例えば、設定部１４０は、頂点の座標成分のうち、水平方向座標成分の最大値及び最小値、座標成分のうち、垂直方向座標成分の最大値及び最小値を利用して、フレームに境界ボックスを設定することができる。そして、演算部１２０は、設定部１４０によって設定された境界ボックスに含まれたピクセルそれぞれに対して、周回数を演算する。
【００８９】
以下、図８の８Ａ及び８Ｂを参照し、設定部１４０が動作する一例について詳細に説明する。
【００９０】
図８の８Ａ及び８Ｂは、一実施形態による設定部１４０が、境界ボックスを設定する一例について説明するための図面である。
【００９１】
図８の８Ａには、フレーム８１０内に含まれた三角形状の客体８４０が図示されている。演算部１２０は、フレーム８１０に含まれたピクセルそれぞれに対して、周回数を演算する。従って、フレーム８１０全体領域のうち、客体８４０が占める領域が狭い場合、演算部１２０がフレーム８１０に含まれた全てのピクセルに対して、周回数を演算しないとしても、経路レンダリングを行うことができる。言い換えれば、演算部１２０は、客体８４０から遠く離れた位置のピクセル８１１に対しては、周回数を演算せず、客体８４０と隣接した位置のピクセル８１２に対してだけ周回数を演算しても、同一の結果を算出することができる。従って、高速で経路レンダリングが行われる。
【００９２】
図８の８Ｂを参照すれば、設定部１４０は、フレーム８１０に境界ボックス８３０を設定する。そして、演算部１２０は、境界ボックス８３０内に位置するピクセル８３１に対してのみ周回数を演算する。このとき、設定部１４０は、客体８５０に含まれた頂点１の座標（ｘ１，ｙ１）、頂点２の座標（ｘ２，ｙ２）及び頂点３の座標（ｘ３，ｙ３）を利用して、境界ボックス８３０を設定する。
【００９３】
例えば、設定部１４０は、頂点１の座標（ｘ１，ｙ１）、頂点２の座標（ｘ２，ｙ２）及び頂点３の座標（ｘ３，ｙ３）のうち、水平方向座標成分の最大値及び最小値、垂直方向座標成分の最大値及び最小値を利用して、フレームに境界ボックスを設定することができる。まず、設定部１４０は、頂点のｘ座標成分（ｘ１，ｘ２，ｘ３）のうち、最大値ｘ３と最小値ｘ１とを選択する。その後、設定部１４０は、頂点のｙ座標成分（ｙ１，ｙ２，ｙ３）のうち、最大値ｙ２と、最小値ｙ１またはｙ３とを選択する。その後、設定部１４０は、ｘ座標成分の最大値と、ｙ座標成分の最大値とでもって、第１座標（ｘ３，ｙ２）を形成する。また、設定部１４０は、ｘ座標成分の最小値と、ｙ座標成分の最小値とでもって、第２座標（ｘ１，ｙ１）を設定する。その後、設定部１４０は、第１座標（ｘ３，ｙ２）と第２座標（ｘ１，ｙ１）とを結ぶ線を対角線とする四角形を境界ボックス８３０として設定する。
【００９４】
前述のところによれば、設定部１４０が経路レンダリングが行われるための最小のピクセルを含む境界ボックスを設定することにより、演算部１２０は、最小個数のピクセルに対してのみ周回数を演算することができる。従って、経路レンダリングを行う装置１００は、経路レンダリングをさらに迅速に遂行することができる。
【００９５】
図９は、一実施形態による周回数生成装置１５０の一例について説明するための図面である。図９に図示された経路レンダリングを行う装置１０２の獲得部１１０、設定部１４０及び決定部１３０の動作は、図１ないし図８の８Ａ及び８Ｂを参照して説明した通りである。従って、以下では、獲得部１１０、設定部１４０及び決定部１３０の具体的な動作に係わる説明は省略する。
【００９６】
また、図９には、経路レンダリングを行う装置１０２が境界ボックスを設定する設定部１４０を含むように図示されているが、それに限定されるものではない。言い換えれば、経路レンダリングを行う装置１０２が設定部１４０を含まないとしても動作することができるということは、図１を参照して説明した通りである。
【００９７】
また、図９に図示された周回数生成装置１５０は、一つまたは複数のプロセッサにも該当する。プロセッサは、多数の論理ゲートのアレイによって具現され、汎用的なマイクロプロセッサと、該マイクロプロセッサで実行されるプログラムが保存されたメモリとの組み合わせによって具現される。また、他の形態のハードウェアによって具現されもするということは、本実施形態が属する技術分野で当業者であるならば、理解することができるであろう。
【００９８】
図９に図示された周回数生成装置１５０は、経路レンダリングを行う装置１０２と連結される。そして、周回数生成装置１５０は、フレームに含まれたピクセルそれぞれの周回数を生成する。図９には、経路レンダリングを行う装置１０２の外部に、周回数生成装置１５０が位置するように図示されているが、それに限定されるものではない。言い換えれば、周回数生成装置１５０は、経路レンダリングを行う装置１０２の内部に位置することもできる。
【００９９】
図１から図８の８Ａ及び８Ｂを参照して説明したところによれば、ピクセルの周回数は、経路レンダリングを行う装置１００または１０１に含まれた演算部１２０によって演算される。しかし、図９及び図１０を参照して説明する一例によれば、ピクセルの周回数は、経路レンダリングを行う装置１０２と独立した周回数生成装置１５０によって演算され、経路レンダリングを行う装置１０２に伝送される。従って、演算部１２０は、経路データに含まれた頂点それぞれの座標に係わる情報、及びフレームに含まれたピクセルの座標を周回数生成装置１５０に伝送し、周回数生成装置１５０から周回数を受信する。
【０１００】
具体的には、周回数生成装置１５０は、経路レンダリングを行う装置１０２から少なくとも一つ以上の経路に対応する頂点それぞれの座標に係わる情報、及びフレームに含まれたピクセルの座標に係わる情報を受信する。そして、周回数生成装置１５０は、受信された情報を利用して、ピクセルに対応する周回数を演算する。そして、周回数生成装置１５０は、演算された周回数を経路レンダリングを行う装置１０２に戻す。
【０１０１】
以下、図１０を参照し、演算部１２０及び周回数生成装置１５０が動作する一例について詳細に説明する。
【０１０２】
図１０は、一実施形態による演算部１２０及び周回数生成装置１５０が動作する一例について説明するための図面である。図１０を参照すれば、演算部１２０は、経路データに含まれた頂点それぞれの座標と、周回数が演算されるピクセルの座標とを周回数生成装置１５０に伝送する。このとき、演算部１２０は、周回数が演算される複数のピクセルそれぞれの座標（または各座標に係わるインデックス）を周回数生成装置１５０に伝送することができる。
【０１０３】
周回数生成装置１５０は、演算部１２０から伝送された座標に係わる情報を利用して、フレームに含まれたピクセルそれぞれの周回数を演算する。このとき、周回数生成装置１５０が周回数を演算する方法は、図２ないし図４を参照し、演算部１２０が周回数を演算する方法と同一である。言い換えれば、演算部１２０は、経路レンダリングを行う装置１０２と独立して存在する周回数生成装置１５０に、周回数を演算するのに必要な情報を伝送し、周回数を演算する動作を一任する。
【０１０４】
周回数生成装置１５０は、演算された周回数を演算部１２０に伝送する。このとき、演算部１２０が、周回数が演算される複数のピクセルそれぞれの座標を、周回数生成装置１５０に伝送した場合には、周回数生成装置１５０は、複数のピクセルそれぞれに対応する周回数を演算部１２０に伝送する。
【０１０５】
図１１は、一実施形態によるピクセルの周回数を演算する方法が、グラフィック処理装置（ＧＰＵ）１１００でもって具現される一例について説明するための図面である。図１１を参照すれば、グラフィック処理装置１１００で実行されるピクセルの周回数を演算する方法は、図１、図７及び図９に図示された経路レンダリングを行う装置１００，１０１または１０２で時系列的に処理される段階によって構成される。従って、以下で省略された内容であるとしても、図１、図７及び図９に図示された経路レンダリングを行う装置１００，１０１または１０２について、以上で記述された内容は、図１１を参照して説明する内容にも適用されるということが分かる。
【０１０６】
図１１を参照すれば、グラフィック処理装置１１００は、バーテックスシェーダ１１２０、ピクセルシェーダ１１４０及びフレームバッファ１１５０を含んでもよい。ここで、バーテックスシェーダ１１２０は、周回数生成が可能なジオメトリシェーダまたはコンピュータシェーダのようなシェーダプログラムまたは装置でも代替可能である。以下では、説明の便宜のために、バーテックスシェーダ１１２０と記載しているが、それに限定されるものではない。また、グラフィック処理装置１１００とは別途に、周回数生成装置１１３０が具備されもする。このとき、周回数生成装置１１３０は、グラフィック処理装置１１００の内部に含まれもし、グラフィック処理装置１１００の外部に独立して位置することもできる。
【０１０７】
バーテックスシェーダ１１２０には、レンダリングが行われる客体に含まれた頂点に係わる情報を含むデータ１１１０が入力される。ここで、データ１１１０には、頂点それぞれの位置を示す座標に係わる情報；及び客体を構成する経路それぞれの開始点に対応する頂点と、経路の終了点に対応する頂点とが何であるかに係わる情報；が含まれる。
【０１０８】
バーテックスシェーダ１１２０は、必要により、境界ボックスを設定する（１１２１）。ここで、境界ボックスは、フレームに含まれたピクセルのうち、周回数が演算されなければならないピクセルを含む仮想のボックスを意味する。
【０１０９】
バーテックスシェーダ１１２０は、フレームに含まれたピクセルに対するピクセル・オーナーシップ・テストを行う（１１２２）。ここで、ピクセル・オーナーシップ・テストは、フレームに含まれたピクセルそれぞれの周回数を演算し、ピクセルそれぞれにカラーを設定するか否かを決定する手続きを意味する。もしバーテックスシェーダ１１２０が、境界ボックスを設定（１１２１）した場合には、境界ボックスに含まれたピクセルに対してのみピクセル・オーナーシップ・テストを行い（１１２２）、バーテックスシェーダ１１２０が境界ボックスを設定（１１２１）しない場合には、フレームに含まれたピクセル全体に対して、ピクセル・オーナーシップ・テストを行う（１１２２）。
【０１１０】
バーテックスシェーダ１１２０がピクセル・オーナーシップ・テストを行っている（１１２２）間、ピクセルそれぞれの周回数が演算される。このとき、バーテックスシェーダ１１２０は、ピクセルの周回数を自主的に演算することもでき、周回数生成装置１１３０に、ピクセルの周回数を問い合わせることもできる。図１２を参照し、バーテックスシェーダ１１２０がピクセル・オーナーシップ・テストを行う（１１２２）一例について詳細に説明する。
【０１１１】
図１２は、一実施形態によるバーテックスシェーダ１１２０がピクセル・オーナーシップ・テストを遂行する（１１２２）一例について説明するためのフローチャートである。
【０１１２】
図１２を参照すれば、バーテックスシェーダ１１２０がピクセル・オーナーシップ・テストを遂行する（１１２２）一例は、図１、図７及び図９に図示された演算部１２０及び決定部１３０で、時系列的に処理される段階によって構成される。従って、以下で省略された内容であるとしても、図１、図７及び図９に図示された演算部１２０及び決定部１３０について、以上で記述された内容は、図１２を参照して説明する内容にも適用されるということが分かる。
【０１１３】
１２１０段階で、バーテックスシェーダ１１２０は、ピクセル・オーナーシップ・テストが行われるピクセルが、境界ボックス内に位置したピクセルであるか否かを確認する。もしバーテックスシェーダ１１２０が境界ボックスを設定していない場合には、１２１０段階は省略される。
【０１１４】
１２２０段階で、バーテックスシェーダ１１２０は、ピクセルの周回数を演算する。もし周回数生成装置１１３０で、ピクセルの周回数を演算すれば、バーテックスシェーダ１１２０は、周回数生成装置１１３０にピクセルの周回数を問い合わせ、周回数生成装置１１３０から周回数を受信する。このとき、バーテックスシェーダ１１２０は、周回数生成装置１１３０に、頂点それぞれの座標に係わる情報、及び周回数が演算されるピクセルの座標に係わる情報を伝送し、周回数生成装置１１３０から周回数を受信する。周回数生成装置１１３０が動作する一例は、図１３及び図１４を参照して説明する。
【０１１５】
１２３０段階で、バーテックスシェーダ１１２０は、第１規則に基づいて、フレームに含まれたピクセルそれぞれに対して、カラーを設定するか否かを決定する。ここで、第１規則は、周回数が０ではない値を有するピクセルに、カラー値を割り当てる規則（non-zero  rule）を意味する。バーテックスシェーダ１１２０が、第１規則に基づいて、ピクセルにカラーを設定するか否かを決定する場合には、１２４０段階で進み、そうではない場合には、１２３５段階に進む。
【０１１６】
１２３５段階で、バーテックスシェーダ１１２０は、第２規則に基づいて、フレームに含まれたピクセルそれぞれに対してカラーを設定するか否かを決定する。ここで、第２規則は、周回数が奇数である値を有するピクセルに、カラー値を割り当てる規則（even-odd  rule）を意味する。バーテックスシェーダ１１２０、が第２規則に基づいて、ピクセルにカラーを設定するか否かを決定する場合には、１２３７段階に進み、そうではない場合には、１２６０段階に進む。
【０１１７】
１２３７段階で、バーテックスシェーダ１１２０は、フレームに含まれたピクセルそれぞれの周回数が奇数であるか否かを判断する。ここで、奇数は、ピクセルの周回数の絶対値が奇数である場合を意味する。例えば、周回数が＋３である場合も奇数と判断され、周回数が−３である場合も、奇数と判断される。バーテックスシェーダ１１２０は、周回数が奇数であるピクセルについては、１２５０段階に進み、周回数が偶数（０含む）であるピクセルについては、１２６０段階を進む。
【０１１８】
１２４０段階で、バーテックスシェーダ１１２０は、フレームに含まれたピクセルそれぞれの周回数が０ではないか否かを判断する。バーテックスシェーダ１１２０は、周回数が０であるピクセルについては、１２６０段階に進み、周回数が０ではないピクセルについては、１２５０段階に進む。
【０１１９】
１２５０段階で、バーテックスシェーダ１１２０は、カラーを設定すると決定したピクセルに係わる情報を、ピクセルシェーダ１１４０に伝送する。例えば、バーテックスシェーダ１１２０は、カラーを設定すると決定したピクセルに係わる座標情報を、ピクセルシェーダ１１４０に含まれたフラグメントシェーダに伝送することができる。
【０１２０】
１２６０段階で、バーテックスシェーダ１１２０は、１２１０段階ないし１２５０段階に基づいて、ピクセル・オーナーシップ・テストが遂行されたピクセルが、フレームに含まれた最後のピクセルであるか否かを判断する。もし最後のピクセルに対するピクセル・オーナーシップ・テストが遂行された場合であるならば、バーテックスシェーダ１１２０は、ピクセル・オーナーシップ・テストを終了し、そうではない場合には、他のピクセルに対して、１２１０段階ないし１２５０段階に基づいたピクセル・オーナーシップ・テストに進む。
【０１２１】
再び図１１を参照すれば、ピクセルシェーダ１１４０は、バーテックスシェーダ１１２０から伝送されたピクセルそれぞれに対して、ピクセル処理を遂行する。言い換えれば、ピクセルシェーダ１１４０は、バーテックスシェーダ１１２０から伝送されたピクセルそれぞれに、カラー値を設定する。
【０１２２】
まず、ピクセルシェーダ１１４０（または、ピクセルシェーダ１１４０に含まれたフラグメントシェーダ）は、ピクセルそれぞれにカラー値を設定する（１１４１）。このとき、フラグメントシェーダは、既保存のテクスチャ１１４２を利用して、ピクセルそれぞれにカラー値を設定することができる。
【０１２３】
その後、ピクセルシェーダ１１４０は、ピクセルそれぞれに、後処理作業を遂行する（１１４３）。ここで、後処理作業は、ブレンディング作業またはアンチエイリアシング作業を含む。
【０１２４】
ピクセルシェーダ１１４０は、ピクセル処理が行われた結果をフレームバッファ１１５０に伝送し、フレームバッファ１１５０は、ピクセルシェーダ１１４０から伝送された情報を保存する。
【０１２５】
図１３は、一実施形態による周回数生成装置１１３０が動作する一例について説明するためのフローチャートである。図１３を参照すれば、周回数生成装置１１３０が動作する一例は、図１及び図７に図示された演算部１２０、または図９に図示された周回数演算装置１５０において、時系列的に処理される段階によって構成される。従って、以下で省略された内容であるとしても、図１、図７及び図９に図示された演算部１２０または周回数演算装置１５０について、以上で記述された内容は、図１３を参照して説明する内容にも適用されるということが分かる。
【０１２６】
１３１０段階で、周回数生成装置１１３０は、バーテックスシェーダ１１２０から、頂点の座標及びピクセルＰの座標を受信する。
【０１２７】
１３２０段階で、周回数生成装置１１３０は、ピクセルＰの周回数Ｎを０に設定する。
【０１２８】
１３３０段階で、周回数生成装置１１３０は、ピクセルＰの一つの側に経路が位置するか否かを判断する。図１３では、周回数生成装置１１３０が、ピクセルＰの右側に経路が存在するか否かを判断すると説明するが、それに限定されるものではない。もしピクセルＰの右側に経路が存在する場合には、１３４０段階に進み、そうではない場合には、１３８０段階に進む。以下、図１４を参照し、周回数生成装置１１３０が、ピクセルＰの一つの側に経路が位置するか否かを判断する一例について説明する。
【０１２９】
図１４は、一実施形態による周回数生成装置１１３０が、ピクセルＰの一つの側に経路が位置するか否かを判断する一例について説明するためのフローチャートである。
【０１３０】
以下、ｘ座標は、フレームの水平方向に対応する座標を意味し、ｙ座標は、フレームの垂直方向に対応する座標を意味する。また、以下では、ピクセルＰの右側に経路が位置し、経路の終了点Ｖ２のｘ座標成分（Ｖ２．ｘ）が、開始点Ｖ１のｘ座標成分（Ｖ１．ｘ）より大きく、経路の終了点Ｖ２のｙ座標成分（Ｖ２．ｙ）が、開始点Ｖ１のｙ座標成分（Ｖ１．ｙ）より大きいと仮定して説明する。ただし、前述の仮定は、説明の便宜のために仮定したものであり、周回数生成装置１１３０が、ピクセルＰの一つの側に経路が位置するか否かを判断する方法は、前述の仮定に制限されるものではない。
【０１３１】
１４１０段階で、周回数生成装置１１３０は、周回数が演算されるピクセルＰの座標（Ｐ．ｘ，Ｐ．ｙ）、フレームに含まれた一経路の開始点Ｖ１の座標（Ｖ１．ｘ，Ｖ１．ｙ）、及び終了点Ｖ２の座標（Ｖ２．ｘ，Ｖ２．ｙ）を獲得する。
【０１３２】
１４２０段階及び１４３０段階で、周回数生成装置１１３０は、ピクセルＰの右側に経路が位置するか否かを判断する。例えば、周回数生成装置１１３０は、ピクセルＰから、右側水平方向に延長された仮想の半直線が経路と出合うか否かを確認する。もし仮想の半直線と経路が出合えば、周回数生成装置１１３０は、ピクセルＰの右側に経路が存在すると判断する。以下、周回数生成装置１１３０がピクセルＰから、右側水平方向に延長された仮想線が経路と出合うか否かを確認する方法について説明する。
【０１３３】
１４２０段階で、周回数生成装置１１３０は、ピクセルＰのｙ座標成分（Ｐ．ｙ）が、開始点Ｖ１のｙ座標成分（Ｖ１．ｙ）より大きく、終了点Ｖ２のｙ座標成分（Ｖ２．ｙ）より小さいか否かを判断する。もしピクセルＰのｙ座標成分（Ｐ．ｙ）が、開始点Ｖ１のｙ座標成分（Ｖ１．ｙ）より大きく、終了点Ｖ２のｙ座標成分（Ｖ２．ｙ）より小さい場合には、１４３０段階に進み、そうではない場合には、図１３の１３８０段階に進む。
【０１３４】
１４３０段階で、周回数生成装置１１３０は、開始点の終了点Ｖ２のｘ座標成分（Ｖ２．ｘ）と、開始点Ｖ１のｘ座標成分（Ｖ１．ｘ）との差（Ｖ２．ｘ−Ｖ１．ｘ）；及びピクセルＰのｙ座標成分（Ｐ．ｙ）と、開始点Ｖ１のｙ座標成分（Ｖ１．ｙ）との差（Ｐ．ｙ−Ｖ１．ｙ）；の積である第１値を演算する。そして、周回数生成装置１１３０は、ピクセルＰのｘ座標成分（Ｐ．ｘ）、と開始点Ｖ１のｘ座標成分（Ｖ１．ｘ）との差（Ｐ．ｘ−Ｖ１．ｘ）；及び終了点Ｖ２のｙ座標成分（Ｖ２．ｙ）と、開始点Ｖ１のｙ座標成分（Ｖ１．ｙ）との差（Ｖ２．ｙ−Ｖ１．ｙ）；の積である第２値を演算する。そして、周回数生成装置１１３０は、第１値が第２値より大きいか否かを判断する。
【０１３５】
もし第１値が第２値より大きい場合には、周回数生成装置１１３０は、ピクセルＰから右側水平方向に延長された仮想線が経路と出合うと判断し、図１３の１３４０段階に進む。もし第１値が第２値より小さいか、あるいは同じである場合には、周回数生成装置１１３０は、ピクセルＰから右側水平方向に延長された仮想線が経路と出合わないと判断し、図１３の１３８０段階に進む。
【０１３６】
再び図１３を参照すれば、１３４０段階で、周回数生成装置１１３０は、ピクセルＰの右側に存在する経路が、時計周り方向に回転するか否かを判断する。もし経路が時計周り方向に回転する場合には、１３５０段階に進み、そうではない場合には、１３６０段階に進む。
【０１３７】
１３５０段階で、周回数生成装置１１３０は、ピクセルＰの周回数Ｎに１を増算する。
【０１３８】
１３６０段階で、周回数生成装置１１３０は、ピクセルＰの右側に存在する経路が、反時計周り方向に回転するか否かを判断する。もし経路が反時計周り方向に回転する場合には、１３７０段階に進み、そうではない場合には、１３８０段階に進む。
【０１３９】
１３７０段階で、周回数生成装置１１３０は、ピクセルＰの周回数Ｎに１を減算する。
【０１４０】
１３８０段階で、周回数生成装置１１３０は、ピクセルＰの右側に、他の経路が存在するか否かを判断する。もしピクセルＰの右側に、他の経路が存在する場合には、１３３０段階に進み、そうではない場合には、１３９０段階に進む。
【０１４１】
１３９０段階で、周回数生成装置１１３０は、ピクセルＰの周回数を戻す。
【０１４２】
図１５は、一実施形態による経路レンダリングを行う方法の一例について説明するためのフローチャートである。図１５を参照すれば、経路レンダリングを行う方法は、図１、図７、図９及び図１１に図示された経路レンダリングを行う装置１００，１０１または１０２、あるいはグラフィック処理装置１１００において、時系列的に処理される段階によって構成される。従って、以下で省略された内容であるとしても、図１、図７、図９及び図１１に図示された経路レンダリングを行う装置１００，１０１または１０２、あるいはグラフィック処理装置１１００について、以上で記述された内容は、図１５の経路レンダリングを行う方法にも適用されるということが分かる。
【０１４３】
１５１０段階で、獲得部１１０は、少なくとも一つ以上の経路に対応する頂点に係わる情報を含む経路データを獲得する。
【０１４４】
１５２０段階で、演算部１２０は、フレームに含まれたピクセルそれぞれの位置を中心にする少なくとも一つ以上の経路の位置及び進行方向を利用して、ピクセルそれぞれに対応する周回数を演算する。
【０１４５】
１５３０段階で、決定部１３０は、周回数を利用して、ピクセルそれぞれにカラーを設定するか否かを決定する。
【０１４６】
なお、前述の方法は、コンピュータで実行されるプログラムによって作成可能であり、コンピュータで読取り可能な記録媒体を利用して、前記プログラムを動作させる汎用デジタルコンピュータで具現される。また、前述の方法で使用されたデータの構造は、コンピュータで読取り可能な記録媒体に、さまざまな手段を介して記録される。前記コンピュータで読取り可能な記録媒体は、マグネチック記録媒体（例えば、ＲＯＭ（read-only  memory）、ＲＡＭ（random-access  memory）、ＵＳＢ（universal  serial  bus）、フロッピー（登録商標）ディスク、ハードディスクなど）、光学的判読媒体（例えば、ＣＤ（compact  disc）−ＲＯＭ、ＤＶＤ（digital  versatile  disc）など）のような記録媒体を含む。
【０１４７】
本実施形態に係わる技術分野で当業者は、前述の記載の本質的な特性から外れない範囲で変形された形態で具現されるということを理解することができるであろう。従って、開示された方法は、限定的な観点ではなく、説明的な観点から考慮されなければならない。本発明の範囲は、前述の説明ではなく、特許請求の範囲に示されており、それと同等な範囲内にある全ての差異は、本発明に含まれたものであると解釈されなければならないのである。
【産業上の利用可能性】
【０１４８】
本発明の経路レンダリングを行う方法及びその装置は、例えば、グラフィック処理関連の技術分野に効果的に適用可能である。
【符号の説明】
【０１４９】
１００，１０１，１０２  経路レンダリング装置
１１０  獲得部
１２０  演算部
１３０  決定部
１４０  設定部
１５０，１１３０  周回数生成装置
２１０，８１１，８１２，８３１  ピクセル
２２０  仮想線
２３０  経路
２３１  第１頂点
２３２  第２頂点
２３３  第３頂点
２３４  第４頂点
３１０，８４０，８５０  客体
３２０  第１客体
３３０  第２客体
６１０，８１０，８２０  フレーム
８３０  境界ボックス
１１００  グラフィック処理装置
１１１０  データ
１１２０  バーテックスシェーダ
１１４０  ピクセルシェーダ
１１５０  フレームバッファ
【図１】
2015210816.tif 000003
【図２】
2015210816.tif 000004
【図３Ａ】
2015210816.tif 000005
【図３Ｂ】
2015210816.tif 000006
【図４Ａ】
2015210816.tif 000007
【図４Ｂ】
2015210816.tif 000008
【図４Ｃ】
2015210816.tif 000009
【図４Ｄ】
2015210816.tif 000010
【図５】
2015210816.tif 000011
【図６】
2015210816.tif 000012
【図７】
2015210816.tif 000013
【図８】
2015210816.tif 000014
【図９】
2015210816.tif 000015
【図１０】
2015210816.tif 000016
【図１１】
2015210816.tif 000017
【図１２】
2015210816.tif 000018
【図１３】
2015210816.tif 000019
【図１４】
2015210816.tif 000020
【図１５】
2015210816.tif 000021