(57)【要約】【課題】本発明は、タイル基盤３次元レンダリングにおいて、半平面エッジ関数を用いたタイルビニング方法およびシステムに関する。【解決手段】三角形をレンダリングするための画面を複数のタイルに分割し、前記タイルのタイルノードにおける半平面エッジ関数を用いた判別値に基づき、前記タイルのうち、前記三角形の全部または一部を含むタイルを判別する方法およびシステムに関する。【選択図】図８
2008027418.tif 000002
【特許請求の範囲】
【請求項１】
三角形に対してレンダリングを遂行するための画面を複数のタイルに分割する段階と、
前記タイルそれぞれのタイルノードの判別値を決定する段階と、
前記タイルそれぞれの前記タイルノードの前記判別値に基づき、前記タイルのうち、前記三角形の全部または一部を含んでいるタイルを判別する段階
と、
を含むことを特徴とするタイルビニング方法。
【請求項２】
前記判別値は、第１判別値、第２判別値および第３判別値を含み、
前記判別値を決定する前記段階は、
前記タイルノードにおいて、前記三角形の第１辺、第２辺および第３辺それぞれに対する半平面エッジ関数値の符号に基づいて第１判別値、第２判別値および第３判別値を決定すること、
を特徴とする請求項１に記載のタイルビニング方法。
【請求項３】
前記三角形の全部または一部を含んでいるタイルを判別する前記段階は、
前記タイルのうち、前記タイルに含まれるタイルノードの第１判別値が互いに同一であり、第２判別値が互いに同一であり、第３判別値が互いに同一であって、前記タイルノードのいずれか一つの第１判別値、第２判別値および第３判別値の少なくとも一つが負数であるタイルを除いた残りのタイルを前記三角形の全部または一部を含んでいるタイルとして判別すること、
を特徴とする請求項２に記載のタイルビニング方法。
【請求項４】
前記三角形の全部または一部を含んでいるタイルを判別する前記段階は、
前記タイルそれぞれに対して並列的に遂行されること、
を特徴とする請求項３に記載のタイルビニング方法。
【請求項５】
前記分割されたタイルのうち、前記三角形を含む最小の四角形の範囲に含まれるタイルを選別する段階、
をさらに含み、
前記判別値を決定する前記段階は、
前記選別されたタイルに対してのみ、それぞれのタイルノードの判別値を決定すること、
を特徴とする請求項３に記載のタイルビニング方法。
【請求項６】
前記タイルのうち、前記三角形を含む最小の四角形を含むタイルを選別する前記段階は、
前記三角形の頂点の座標に基づき、前記三角形を含む最小の四角形を求めること、
を特徴とする請求項５に記載のタイルビニング方法。
【請求項７】
前記判別値を決定する前記段階は、
第１タイルノードにおいて、前記三角形の第１辺に対する半平面エッジ関数値を計算する段階と、
前記関数値に基づき、前記第１タイルノードと所定の方向に隣接した第２タイルノードの半平面エッジ関数値を計算する段階と、
を含むことを特徴とする請求項２に記載のタイルビニング方法。
【請求項８】
前記第１タイルノードの半平面エッジ関数値の符号が前記第２タイルノードにおける半平面エッジ関数値の符号と異なる場合に、前記第２タイルノードから前記方向に存在するタイルノードの判別値を前記第２タイルノードの判別値として決定する段階、
をさらに含むことを特徴とする請求項７に記載のタイルビニング方法。
【請求項９】
前記第１タイルノードは、前記三角形の頂点のいずれか一つが含まれたタイルに含まれるタイルノードの一つであること、
を特徴とする請求項７に記載のタイルビニング方法。
【請求項１０】
前記タイルそれぞれの前記タイルノードの前記判別値に基づき、前記タイルのうち、前記三角形にすべて含まれるタイルを判別する段階、
をさらに含むことを特徴とする請求項１に記載のタイルビニング方法。
【請求項１１】
前記三角形に全部含まれるタイルを判別する前記段階は、
前記タイルのうち、前記タイルに含まれるタイルノードすべてに対して、前記第１判別値、前記第２判別値および前記第３判別値がすべて正数であるタイルを前記三角形にすべて含まれるタイルとして判別すること、
を特徴とする請求項１０に記載のタイルビニング方法。
【請求項１２】
前記タイルノードは前記タイルの頂点であることを特徴とする請求項１に記載のタイルビニング方法。
【請求項１３】
請求項１ないし１２のいずれか一項の方法を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１４】
三角形に対してレンダリングを遂行するための画面を複数のタイルに分割するタイル分割部と、
前記タイルそれぞれのタイルノードの判別値を決定する判別値決定部と、
前記タイルそれぞれの前記タイルノードの前記判別値に基づき、前記タイルのうち、前記三角形の全部または一部を含んでいるタイルを判別するタイル判別部と、
を含むことを特徴とするタイルビニングシステム。
【請求項１５】
前記判別値は、第１判別値、第２判別値および第３判別値を含み、
前記判別値決定部は、
前記タイルノードにおいて、前記三角形の第１辺、第２辺および第３辺それぞれに対する半平面エッジ関数値の符号に基づき、第１判別値、第２判別値および第３判別値を決定すること、
を特徴とする請求項１４に記載のタイルビニングシステム。
【請求項１６】
前記タイル判別部は、
前記タイルのうち、前記タイルに含まれるタイルノードの第１判別値が互いに同一であり、第２判別値が互いに同一であり、第３判別値が互いに同一であって、前記タイルノードのいずれか一つの第１判別値、第２判別値および第３判別値の少なくともいずれか一つが負数であるタイルを除いた残りのタイルを前記三角形の全部または一部を含んでいるタイルとして判別すること、
を特徴とする請求項１５に記載のタイルビニングシステム。
【請求項１７】
前記分割されたタイルのうち、前記三角形を含む最小の四角形の範囲に含まれるタイルを選別する範囲選別部、
をさらに含み、
前記判別値決定部は、
前記選別されたタイルに対してのみ、それぞれのタイルノードの判別値を決定すること、
を特徴とする請求項１４に記載のタイルビニングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、効率良くタイルビニングを行う技術を提供するタイルビニング方法及びタイルビニングシステムに関する。
【背景技術】
【０００２】
最近、個人用端末機の性能向上に伴い、３次元グラフィックを用いて情報を提供する場合が増加している。従来では、３次元グラフィックはコンピュータ端末機でのみ用いることができたが、最近では、携帯電話、ＰＤＡ、またはナビゲーションなどのような携帯端末機の性能向上に伴い、前記のような携帯端末機でも３次元グラフィックを用いることができるようになった。３次元グラフィックを用いると、２次元で表示されるディスプレイ装置でもよりリアルに３次元モデルを表現することができるという効果がある。
【０００３】
しかし、３次元グラフィックで３次元モデルを表現する場合でも、ユーザが確認することができるディスプレイ装置は２次元画面であるため、ユーザに表示するためには、３次元モデルをユーザの視点から見た２次元画面に変換する過程が必要となる。このように、３次元モデルを２次元画面に変換する過程のうち、２次元座標に変換されてベクトル形態で表示されている３次元モデルをピクセル基盤の２次元画面で生成する過程をラスタライゼーション（Rasterization）という。前記ラスタライゼーション過程では、３次元モデルの基本単位である三角形に基づいて２次元画面を生成する演算を遂行していた。
【０００４】
従来技術によると、ラスタライゼーション過程において処理しなければならないそれぞれの三角形を全体画面に対して処理していたため、スクリーン解像度と同一サイズのフレームバッファ（カラーバッファ＋Ｚバッファ）を必要とする。この場合、フレームバッファは、そのサイズによってチップ内部にエンベッドさせることが容易ではない。そのため、任意の外部フレームバッファを用いて、全体画面に対する処理を行っている。このとき、全体画面に対する処理を行うためには、外部フレームバッファに対して頻繁にアクセスする必要がある。このような外部メモリアクセスは、チップ内部のメモリアクセスに比べて約１０倍の電力を消耗するため、低電力を追求するモバイル環境においては、このような頻繁な外部メモリアクセスを減らすことが大きなポイントとなる。したがって、前記のような従来技術の問題点を解決するために開発されたものがタイル基盤３次元レンダリング方法である。
【０００５】
図１は、従来技術に係るタイル基盤３次元レンダリング方法を示した図である。
図面に示されたように、全体画面が複数のタイルに分割されている。この全体画面のタイルのうち、三角形１１０の全部または一部を含んでいるタイルは図面符号１２０で囲まれた部分であり、これ以外の部分は三角形を含んでいない。このとき、一つのタイルに対するレンダリングは、チップ内部にインベッドされた一つのタイル解像度サイズのフレームメモリを用いて遂行される。そして、１つのタイルに対するレンダリングが完了すると、そのレンダリング結果が一度にバーストモードを用いて外部フレームバッファのタイル位置に送信するようになる。言い換えれば、タイル基盤３次元レンダリング方法では、タイル毎に外部フレームバッファとのアクセスが行われる。このように、タイル基盤レンダリング方法によると、頻繁な外部フレームバッファメモリアクセスせず、タイル当り一回の効果的な外部バーストメモリアクセスのみを遂行することで、低電力駆動という側面において非常に有利となる。
【０００６】
このように、タイル基盤３次元レンダリング方法を遂行するためには、三角形１１０の全部または一部を含むタイルを判別する作業（これをタイルビニング（Tile Binning）と言う）が必要となる。しかし、タイル基盤３次元レンダリング方法において用いられるタイルビニング方法は、大きな負荷がかかる作業であり、また、正確に三角形１１０の全部または一部を含むタイルのみを判別することは非常に困難である。なお、タイル基盤３次元レンダリング方法ではない、別の既存のレンダリング方法においては、タイルビニングの作業は不要であり、そのことがタイル基盤３次元レンダリング方法に対して更に負荷を感じさせる要因となっている。したがって、短時間で正確に三角形の全部または一部を含むタイルを判別することができる方法が求められている。
【０００７】
図２（ａ）、（ｂ）は、従来技術に係る分割技法を用いたタイルビニング方法を示した図である。
分割技法を用いたタイルビニング方法は、短時間で三角形２１０の全部または一部を含むタイルを判別するために考案されたものである。図示されたように、この方法は、先ず、図２（ａ）のように三角形２１０を含む最小の四角形２２０を求める。四角形２２０のサイズが所定の臨界値より大きい場合には、図２（ｂ）のように三角形２１０の三つの辺の中点を連結して４つの三角形に分割し、分割されたそれぞれの三角形を含む最小の四角形を求める。このような過程をそれぞれの四角形のサイズが前記臨界値より小さくなるまで繰り返す。この結果、四角形のサイズが前記臨界値より小さくなると、前記四角形を含むタイルを前記三角形２１０の全部または一部を含むタイルとして判別する。この方法により、図２（ｂ）に示すように右上の角４つと、左下の角４つについては判別の対象から外れ、判別の処理が不要となる。そのため、全てのタイルについて判別処理を行う場合に比べて短時間で判別処理が終了する。
【０００８】
しかし、前記した方法によると、図面符号２３０（砂模様が付されたタイル）のように、前記三角形２１０の全部または一部を含むタイルとして判別されたものの、実際には前記三角形２１０の一部さえも含んでいないタイルが存在することが生じる。つまり、砂模様のタイル２３０は、それぞれ最小の四角形を含むが、三角形の一部又は全部は含まない。そのため、三角形の全部または一部を含むタイルを判別する作業が完全には正確に行われていない。また、一段階の分割ごとに三角形が４倍に増えるため、三角形のサイズが大きい場合、分割の段階が多くなる。このとき、処理しなければならない三角形の数が４ｎと幾何級数的に増加し、演算速度が非常に遅滞する恐れがあるという問題点が生じる。最後に、アルゴリズム自体の単純さとは別に、具現という側面においては、新たに生成される頂点を三角形の形態で再配列する過程が追加的なオーバーヘッドとして作用するようになる。
【０００９】
したがって、三角形の全部または一部を含むタイルのみを正確に探し出すことができ、三角形の形態やサイズとは関係なく、一定の性能を期待することができる方法があるとすると、タイルビニング方法をより効率的に遂行することができるであろう。
【特許文献１】韓国特許2003-005251号公報
【特許文献２】米国公開特許2004-0160450号明細書
【特許文献３】米国特許第6,900,800号明細書
【特許文献４】米国特許第6,957,318号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１０】
そこで、本発明は、効率良くタイルビニングを行う技術を提供するタイルビニング方法及びタイルビニングシステムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
前記目的を達成し、従来技術の問題点を解決するために、本発明１の一実施形態に係るタイルビニング方法は、三角形に対してレンダリングを遂行するための画面を複数のタイルに分割する段階と、前記タイルそれぞれのタイルノードの判別値を決定する段階と、前記選別されたタイルそれぞれの前記タイルノードの前記判別値に基づき、前記選別されたタイルのうち、前記三角形の全部または一部を含んでいるタイルを判別する段階と、を含む。
【００１２】
発明２は、発明１において、前記判別値は、第１判別値、第２判別値および第３判別値を含み、前記判別値を決定する前記段階は、前記タイルノードにおいて、前記三角形の第１辺、第２辺および第３辺それぞれに対する半平面エッジ関数値の符号に基づいて第１判別値、第２判別値および第３判別値を決定すること、を特徴とする。
発明３は、発明２において、前記三角形の全部または一部を含んでいるタイルを判別する前記段階は、前記タイルのうち、前記タイルに含まれるタイルノードの第１判別値が互いに同一であり、第２判別値が互いに同一であり、第３判別値が互いに同一であって、前記タイルノードのいずれか一つの第１判別値、第２判別値および第３判別値の少なくとも一つが負数であるタイルを除いた残りのタイルを前記三角形の全部または一部を含んでいるタイルとして判別することを特徴とする。
【００１３】
発明４は、発明３において、前記三角形の全部または一部を含んでいるタイルを判別する前記段階は、前記タイルそれぞれに対して並列的に遂行されることを特徴とする。
発明５は、発明３において、前記分割されたタイルのうち、前記三角形を含む最小の四角形の範囲に含まれるタイルを選別する段階、をさらに含み、前記判別値を決定する前記段階は、前記選別されたタイルに対してのみ、それぞれのタイルノードの判別値を決定することを特徴とする。
【００１４】
発明６は、発明５において、前記タイルのうち、前記三角形を含む最小の四角形を含むタイルを選別する前記段階は、前記三角形の頂点の座標に基づき、前記三角形を含む最小の四角形を求めることを特徴とする。
発明７は、発明２において、前記判別値を決定する前記段階は、第１タイルノードにおいて、前記三角形の第１辺に対する半平面エッジ関数値を計算する段階と、前記関数値に基づき、前記第１タイルノードと所定の方向に隣接した第２タイルノードの半平面エッジ関数値を計算する段階とを含むことを特徴とする。
【００１５】
発明８は、発明７において、前記第１タイルノードの半平面エッジ関数値の符号が前記第２タイルノードにおける半平面エッジ関数値の符号と異なる場合に、前記第２タイルノードから前記方向に存在するタイルノードの判別値を前記第２タイルノードの判別値として決定する段階、をさらに含むことを特徴とする。
発明９は、発明７において、前記第１タイルノードは、前記三角形の頂点のいずれか一つが含まれたタイルに含まれるタイルノードの一つであること、を特徴とする。
【００１６】
発明１０は、発明１において、前記タイルそれぞれの前記タイルノードの前記判別値に基づき、前記タイルのうち、前記三角形にすべて含まれるタイルを判別する段階、をさらに含むことを特徴とする。
発明１１は、発明１０において、前記三角形に全部含まれるタイルを判別する前記段階は、前記タイルのうち、前記タイルに含まれるタイルノードすべてに対して、前記第１判別値、前記第２判別値および前記第３判別値がすべて正数であるタイルを前記三角形にすべて含まれるタイルとして判別すること、を特徴とする。
【００１７】
発明１２は、発明１において、前記タイルノードは前記タイルの頂点であることを特徴とする。
発明１３は、発明１ないし１２のいずれか一項の方法を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体を提供する。
また、本１４発明の一実施形態に係るタイルビニングシステムは、三角形に対してレンダリングを遂行するための画面を複数のタイルに分割するタイル分割部と、前記タイルそれぞれのタイルノードの判別値を決定する判別値決定部と、前記タイルそれぞれの前記タイルノードの前記判別値に基づき、前記タイルのうち、前記三角形の全部または一部を含んでいるタイルを判別するタイル判別部と、を含む。
【００１８】
発明１５は、発明１４において、前記判別値は、第１判別値、第２判別値および第３判別値を含み、前記判別値決定部は、前記タイルノードにおいて、前記三角形の第１辺、第２辺および第３辺それぞれに対する半平面エッジ関数値の符号に基づき、第１判別値、第２判別値および第３判別値を決定すること、を特徴とする。
発明１６は、発明１５において、前記タイル判別部は、前記タイルのうち、前記タイルに含まれるタイルノードの第１判別値が互いに同一であり、第２判別値が互いに同一であり、第３判別値が互いに同一であって、前記タイルノードのいずれか一つの第１判別値、第２判別値および第３判別値の少なくともいずれか一つが負数であるタイルを除いた残りのタイルを前記三角形の全部または一部を含んでいるタイルとして判別すること、を特徴とする。
【００１９】
発明１７は、発明１４において、前記分割されたタイルのうち、前記三角形を含む最小の四角形の範囲に含まれるタイルを選別する範囲選別部、をさらに含み、前記判別値決定部は、前記選別されたタイルに対してのみ、それぞれのタイルノードの判別値を決定すること、を特徴とする。
【発明の効果】
【００２０】
本発明によれば、効率良くタイルビニングを行うことが可能なタイルビニング方法及びタイルビニングシステムを提供することができる。
【発明を実施するための最良の形態】
【００２１】
以下、添付の図面および添付の図面に記載された内容を参照して本発明の好ましい実施形態を詳細に説明するが、本発明が実施形態よって制限されたり限定されるものではない。各図面に提示された同一の参照符号は、同一部材を示している。
図３は、本発明の一実施形態に係るタイルビニング方法の流れを示したフローチャートである。
【００２２】
ここでは、本発明の一実施形態に係るタイルビニング方法の全般的な流れに関して説明しており、各段階に対しては図４ないし図７でより詳しく述べる。
段階３０１では、三角形に対してレンダリングを遂行するための画面を複数のタイルに分割する。タイルは、ユーザに表示される画面解像度を所定のサイズに分けたものであって、それぞれのタイルでレンダリング過程を遂行することで、全体画面に対するレンダリングを遂行することができる。例えば、６４０×４８０の解像度を有する画面を３２×３２の解像度を有するタイルに分割すると、２０×１５個のタイルがレンダリングのために用いられる。このように、全体画面を複数のタイルに分割すると、解像度が低いそれぞれのタイルに対してレンダリングを遂行するだけで全体画面のレンダリングを処理することができる。
【００２３】
段階３０２では、段階３０１で分割されたタイルのうち、三角形を含む最小の四角形の範囲に含まれるタイルを選別する。最小の四角形とは、図４に示すように頂点４１０、４２０、４３０の三角形を含む、頂点４１０、４４０、４５０、４６０の四角形である。段階３０１で分割されたタイルのうち、レンダリングを遂行しなければならないタイルは、三角形の全部または一部を含むタイルである。そこで、タイルから三角形の全部または一部を含むタイルを判別しなければならない。つまり、タイルの全体を三角形の一部が占める（図４のタイルＡ等）か、又はタイルの一部を三角形の一部が占める（図４のタイルＢ等）場合を抽出する。最小の四角形は三角形に比べてその範囲が明確であるため、その範囲を容易に判別することができる。したがって、三角形の全部または一部を含むタイルを判別する前に、まず三角形を含む最小の四角形を求める。次に、最小の四角形の範囲に含まれるタイルを選別することで、タイルビニング作業の対象となるタイルを大きく減らすことができる。最小の四角形を求める方法に対しては図４で詳述する。
【００２４】
段階３０３では、段階３０２で選別されたタイルそれぞれのタイルノードの判別値を決定する。タイルノードはタイルの頂点であり、判別値は、タイルノードが三角形を基準としてどのような位置に存在するのかを定義するものである。したがって、段階３０３で判別値を決定すると、タイルの４つの頂点それぞれが三角形を基準としてどのような位置に存在するかに対する情報を得ることができる。これを用いて、それぞれのタイルが三角形の全部または一部を含むかを確認することができる。
【００２５】
段階３０３で決定する判別値は、第１判別値、第２判別値および第３判別値を含む。第１判別値、第２判別値および第３判別値は、それぞれ三角形の第１辺、第２辺および第３辺それぞれに対するタイルノードにおける半平面エッジ関数値の符号に基づいて決定される。一例として、半平面エッジ関数値が正数であれば１、負数または０であれば０で決定されたり、正数、負数、０にそれぞれ異なる値を設定したりもする。なお、それぞれのタイルノードで三角形の３つの辺に対する半平面エッジ関数値の符号を確認することができる方法であれば、いかなる方法であっても判別値を記録することができる。
【００２６】
段階３０３で判別値を決定するために用いる半平面エッジ関数は直線および点の関係を示す関数であり、半平面エッジ関数値は下記式（１）によって計算される。
（数１）
Ｅ（ｘ、ｙ）＝（ｘ−ｘ０）×△ｙ−（ｙ−ｙ０）×△ｘ  ・・・（１）
ここで、△ｘ＝（ｘ１−ｘ０）
△ｙ＝（ｙ１−ｙ０）である。
【００２７】
ここで、（ｘ０、ｙ０）および（ｘ１、ｙ１）はそれぞれ直線の両端点を意味し、（ｘ、ｙ）は点の座標を意味する。また、Ｅ（ｘ、ｙ）値が半平面エッジ関数値となる。半平面エッジ関数値は、点が直線の左側にある場合には正数値を有し、直線の右側にある場合には負数値を有する性質がある。また、（ｘ０、ｙ０）および（ｘ１、ｙ１）は直線の方向を示すものである。つまり、（ｘ０、ｙ０）および（ｘ１、ｙ１）により直線の傾きが算出でき、これにより直線の方向が示される。本発明においては、三角形の周囲に沿って時計回りに回転する方向で三角形の各辺の方向を決定するようにする。方向は実施形態によって異なることがあるが、三角形の内部に存在するタイルノードの第１判別値、第２判別値および第３判別値が同一値を有するようにしようとすると、各辺は互いに同一の回転方向を有さなければならない。なお、このとき、後述のように各辺対してそれぞれ回転した場合に、三角形が各辺に対して下に位置するようにする。
【００２８】
また、半平面エッジ関数は下記式（２ａ）〜（２ｄ）のような性質を有する。
（数２）
Ｅ（ｘ＋１、ｙ）＝Ｅ（ｘ、ｙ）＋△ｙ  ・・・（２ａ）
Ｅ（ｘ−１、ｙ）＝Ｅ（ｘ、ｙ）−△ｙ  ・・・（２ｂ）
Ｅ（ｘ、ｙ＋１）＝Ｅ（ｘ、ｙ）−△ｘ  ・・・（２ｃ）
Ｅ（ｘ、ｙ−１）＝Ｅ（ｘ、ｙ）＋△ｘ  ・・・（２ｄ）
式（２ａ）〜（２ｄ）は式（１）から簡単に求めることができる。また、式（２ａ）〜（２ｄ）の性質を用いると、所定の直線に対して垂直または水平方向に移動する点に対して半平面エッジ関数値の演算過程を大きく減らすことができる。また、同一方向に垂直または水平移動をする場合には、半平面エッジ関数値が一定して増加したり減少したりする。よって、増加する方向において半平面エッジ関数値が負数から正数に変更されると、その後の点はすべて半平面エッジ関数値が正数を有するようになり、減少する方向において半平面エッジ関数値が負数に変更されると、その後の点はすべて半平面エッジ関数値が負数となる。式（２ａ）〜（２ｄ）の上記のような性質は、後述の具体例により明確となる。
【００２９】
段階３０４では、段階３０３で決定したタイルそれぞれのタイルノードの判別値に基づき、タイルから三角形の全部または一部を含むタイルを判別する。段階３０３で決定したタイルノードの判別値を用いると、三角形を基準としてタイルノードの位置に関する情報を確認することができるため、段階３０４では、タイルの各頂点であるタイルノードの三角形を基準とした位置に関する情報を用い、タイルが三角形の全部または一部を含むかを判別することができる。
【００３０】
例えば、段階３０３で、半平面エッジ関数値の符号に基づいてタイルノードの判別値を決定したとする。タイルの四つの頂点である４つのタイルノードについて第１判別値がすべて同一であると、タイルの四つの頂点が第１辺を基準としてすべて同一方向に存在するため、第１辺はタイルに含まれない。したがって、タイルのそれぞれのタイルノードの第１判別値が互いに同一であり、第２判別値が互いに同一であり、第３判別値が互いに同一であれば、タイルは三角形の第１辺、第２辺および第３辺のうちのいずれも含まない。したがって、このような場合には、タイルは三角形の内部に存在したり三角形の外部に存在したりする。ただし、三角形の各辺の方向を時計回りにして半平面エッジ関数値を計算した場合に、三角形の内部に存在するすべてのタイルノードの第１判別値、第２判別値および第３判別値はすべて正数でなければならない。
【００３１】
また、段階３０４で、タイルのそれぞれのタイルノードのうち、第１判別値、第２判別値および第３判別値のいずれか一つでも他の値のタイルノードが存在すると、いずれか一つの辺がタイルに含まれるため、タイルは三角形の一部を含むようになる。結局、タイルのうち、タイルに含まれるタイルノードの第１判別値が互いに同一であり、第２判別値が互いに同一であり、第３判別値が互いに同一であって、タイルノードのいずれか一つの第１判別値、第２判別値および第３判別値の少なくともいずれか一つが負数であるタイルを除いた残りのタイルを三角形の全部または一部を含んでいるものとして判別するようにすることができる。例えば、後述の図７のタイルＣの４つのタイルノードにおいて、第１判別値が全て同一であり、第２判別値が全て同一であり、第３判別値が全て同一であり、第１〜第３判別値の中に負数が含まれる。よって、タイルＣは、三角形の全部または一部を含まない。同様に、図７のタイルＤも三角形の全部または一部を含まない。よって、残りのタイルが三角形の全部または一部を含んでいると判別できる。それぞれのタイルのタイルノードの判別値が決定されていると、このような比較過程を並列的に遂行することができるため、演算時間を大きく減らすことができる。
【００３２】
また、段階３０４では、上記のように、タイルに含まれたすべてのタイルノードの第１判別値、第２判別値および第３判別値が全て正数である場合には、すべてのタイルノードが三角形の内部に含まれる。ここで、タイルノードはタイルの四つの頂点であるため、タイル全体が三角形の内部に含まれるものとして判別することができる。
図４は、本発明の一実施形態に係るタイルビニング方法であって、三角形を含む最小の四角形を求める方法の一例を示した図である。
【００３３】
図面に示されたように、図面符号４１０、図面符号４２０および図面符号４３０は三角形の三つの頂点である。三角形を含む最小の四角形を求めるためには、三角形の三つの頂点の座標を用いる。三つの頂点の座標の中からｘ座標の最小値および最大値を求め、ｙ座標の最小値および最大値を求めると、ｘ座標およびｙ座標の範囲に含まれる四角形は三角形を含む最小の四角形となる。例えば、図面符号４１０の座標が（３、２）、図面符号４２０の座標が（１９、１６）、図面符号４３０の座標が（１６、１９）である場合、三つの頂点のｘ座標のうち最小値は３であり最大値は１９となる。また、三つの頂点のｙ座標のうち最小値は２であり最大値は１９となる。したがって、このような場合には、図面符号４１０、４４０、４５０、４６０のそれぞれの座標（３、２）、（１９、２）、（３、１９）、（１９、１９）を頂点とする四角形が三角形を含む最小の四角形となる。これ以外でも三角形を含む最小の四角形を求めることができる方法であれば、いかなる方法であっても本発明に適用することができる。本発明は四角形を求める方法において制限がない。
【００３４】
図５（ａ）、（ｂ）、（ｃ）は、本発明の一実施形態に係るタイルビニング方法において、それぞれのタイルノードに対する半平面エッジ関数を計算する方法の一例を示した図である。
本発明の一実施形態に係るタイルビニング方法においては、三角形のそれぞれの辺に対して各タイルノードの判別値を決定する。図５（ａ）では、三角形の辺のうち、一つの辺５１０に対して各タイルノードにおける半平面エッジ関数を計算することで、各タイルノードにおける判別値を決定する方法を示している。同様に、図５（ｂ）は辺５１１に対する判別値の決定方法、図５（ｃ）は辺５１２に対する判別値の決定方法を示している。
【００３５】
図面に示されたように、辺５１０に対して図面符号５２０のタイルノードから判別値の演算を開始する場合、まず、式（１）を用いて図面符号５２０のタイルノードにおける半平面エッジ関数値を計算する。図面符号５２０のタイルノードにおける半平面エッジ関数値が求められると、その関数値および式（２）を用いて図面符号５２０のタイルノードと隣接したタイルノードの半平面エッジ関数値を求めることができる。図面では、辺５１０が右下に向かう方向を有しているため、図面符号５２０の半平面エッジ関数値は負数値を有するようになる。
【００３６】
しかし、図面符号５２０のタイルノードと隣接したタイルノードのうち、左側または下のタイルノードは半平面エッジ関数値が正数となる。したがって、図面符号５３０および図面符号５４０のように、図面符号５２０のタイルノードを基準として、左側およびの下のタイルノードの半平面エッジ関数値はすべて正数で決定され、右側およびの上のタイルノードの半平面エッジ関数値はすべて負数で決定される。
【００３７】
これにより、図面符号５３０および図面符号５４０に含まれるタイルノードの判別値はすべて決定される。つまり、図５（ａ）に示すように、辺５１０以上のタイルノードは全て負数（黒丸）となり、辺５１０より下のタイルノードは全て正数（白丸）となる。このように、一つのタイルノード５２０に対して式（１）を用いて半平面エッジ関数値を計算し、式（２）を用いてその隣接タイルノードの半平面エッジ関数値を計算することで、図面符号５３０および図面符号５４０に該当するすべてのタイルノードの判別値を決定することができる。上記した方法によって、判別値を決定するための演算過程を大きく減らすことができる。
【００３８】
具体的に、式（１）、（２）及び図５（ａ）〜（ｃ）を用いて、判別値を以下に算出する。
図５（ａ）において、辺５１０の両端点をまず求める。ここで、辺５１０に対して三角形が下に位置するようにする。また、各タイルノードの座標を決定するために、ｘ軸、ｙ軸に例えば図５（ａ）に示すように０〜６までの数値を割り振る。このとき、辺５１０の両端点は、例えば（ｘ０、ｙ０）＝（０、６）、（ｘ１、ｙ１）＝（６、１．５）である。よって、式（１）より次式の関係が求まる。
Ｅ（ｘ、ｙ）＝−４．５ｘ−６ｙ＋３６、Δｘ＝６、Δｙ＝−４．５
ここで、タイルノード５２０ａの座標は（３、４）であり、上記式に代入すると、Ｅ（３、４）＝−１．５となる。よって、座標は（３、４）のＥ（ｘ、ｙ）の値が負数であると算出できる。次に、式（２）より次式の関係が求まる。
タイルノード５２１ａ：Ｅ（ｘ＋１、ｙ）＝−１．５＋（−４．５）＝−６
タイルノード５２２ａ：Ｅ（ｘ−１、ｙ）＝−１．５−（−４．５）＝３
タイルノード５２３ａ：Ｅ（ｘ、ｙ＋１）＝−１．５−（−６）＝−７．５
タイルノード５２４ａ：Ｅ（ｘ、ｙ−１）＝−１．５＋（−６）＝４．５
よって、タイルノード５２１ａ及び５２３ａのＥ（ｘ、ｙ）の値は負数であり、タイルノード５２２ａ及び５２４ａのＥ（ｘ、ｙ）の値は正数であると算出できる。ここで、タイルノード５２０ａのＥ（ｘ、ｙ）値が正数であり、タイルノード５２４ａのＥ（ｘ、ｙ）値が負数であり、図面符号５３０内のタイルノードについて正数と負数との切替点が明確になっている。同様に、タイルノード５２０ａのＥ（ｘ、ｙ）値が負数であり、タイルノード５２２ａのＥ（ｘ、ｙ）値が正数であり、図面符号５４０内のタイルノードについて正数と負数との切替点が明確になっている。ここで、半平面エッジ関数値は、同一方向に垂直または水平移動をする場合には、半平面エッジ関数値が一定して増加したり減少したりする性質を有する。よって、図面符号５３０内のタイルノードについて、タイルノード５２４ａよりもｙの値が小さいタイルノードは全て正数となり、タイルノード５２０ａよりもｙの値が大きいタイルノードは全て負数となる。また、図面符号５４０内のタイルノードについて、タイルノード５２２ａよりもｘの値が小さいタイルノードは全て正数となり、タイルノード５２０ａよりもｘの値が大きいタイルノードは全て負数となる。このような演算により、すべてのタイルノードの判別値を即座に決定することができる。
【００３９】
次に、図５（ｂ）において、辺５１１に対して三角形が下に位置するように図面を回転する。そして、図５（ａ）と同様にして判別値を算出する。このとき、各タイルノードの座標を決定するために、ｘ軸、ｙ軸に例えば図５（ｂ）に示すように０〜６までの数値を割り振る。辺５１１の両端点は、例えば（ｘ０、ｙ０）＝（４、６）、（ｘ１、ｙ１）＝（６、４）である。よって、式（１）より次式の関係が求まる。
Ｅ（ｘ、ｙ）＝−２ｘ−２ｙ＋２０、Δｘ＝２、Δｙ＝−２
ここで、タイルノード５２０ｂの座標は（５、５）であり、上記式に代入すると、Ｅ（５、５）＝０となる。よって、座標は（５、５）のＥ（ｘ、ｙ）の値が負数であると算出できる。次に、式（２）より次式の関係が求まる。
タイルノード５２１ｂ：Ｅ（ｘ＋１、ｙ）＝０＋（−２）＝−２
タイルノード５２２ｂ：Ｅ（ｘ−１、ｙ）＝０−（−２）＝２
タイルノード５２３ｂ：Ｅ（ｘ、ｙ＋１）＝０−（２）＝−２
タイルノード５２４ｂ：Ｅ（ｘ、ｙ−１）＝０＋（２）＝２
よって、タイルノード５２０ｂ、５２１ｂ及び５２３ｂのＥ（ｘ、ｙ）の値は負数であり、タイルノード５２２ｂ及び５２４ｂのＥ（ｘ、ｙ）の値は正数であると算出できる。そして、前述と同様にしてタイルノード５２０ｂを含み、ｘ座標が共通のグループと、ｙ座標が共通のグループについても判別値を即座に算出することができる。
【００４０】
最後に、図５（ｃ）において、辺５１２に対して三角形が下に位置するように図面を回転する。そして、図５（ａ）、（ｂ）と同様にして判別値を算出する。このとき、各タイルノードの座標を決定するために、ｘ軸、ｙ軸に例えば図５（ｃ）に示すように０〜６までの数値を割り振る。辺５１２の両端点は、例えば（ｘ０、ｙ０）＝（１．２、６）、（ｘ１、ｙ１）＝（５．８、０）である。よって、式（１）より次式の関係が求まる。
Ｅ（ｘ、ｙ）＝−６ｘ−４．６ｙ＋３４．８、Δｘ＝４．６、Δｙ＝−６
ここで、タイルノード５２０ｃの座標は（３、４）であり、上記式に代入すると、Ｅ（３、４）＝−１．６となる。よって、座標は（３、４）のＥ（ｘ、ｙ）の値が負数であると算出できる。次に、式（２）より次式の関係が求まる。
タイルノード５２１ｃ：Ｅ（ｘ＋１、ｙ）＝−１．６＋（−６）＝−７．６
タイルノード５２２ｃ：Ｅ（ｘ−１、ｙ）＝−１．６−（−６）＝４．４
タイルノード５２３ｃ：Ｅ（ｘ、ｙ＋１）＝−１．６−（４．６）＝−６．２
タイルノード５２４ｃ：Ｅ（ｘ、ｙ−１）＝−１．６＋（４．６）＝３
よって、タイルノード５２０ｃ、５２１ｃ及び５２３ｃのＥ（ｘ、ｙ）の値は負数であり、タイルノード５２２ｃ及び５２４ｃのＥ（ｘ、ｙ）の値は正数であると算出できる。そして、前述と同様にしてタイルノード５２０ｃを含み、ｘ座標が共通のグループと、ｙ座標が共通のグループについても判別値を即座に算出することができる。
【００４１】
特に、判別値を決定する過程を開始するスタートタイルノードが直線と隣接して存在するほど演算を大きく減らすことができる。このために、三角形の三つの頂点が位置したタイルの各タイルノードから判別値を決定する過程が開始するようにすることができる。辺５１０以外の他の辺に対しても同一の方法で判別値を決定することができる。
図６は、三角形の内部および外部における半平面エッジ関数値の符号を示した図である。
【００４２】
図面に示されたように、三角形の三つの辺の方向を時計回りに回転する方向で各辺に対する半平面エッジ関数値を求めると、三角形の内部６１０はすべての辺に対して正数の値を有するようになり、三角形の外部６２０、６３０、６４０は少なくともいずれか一つの辺に対する半平面エッジ関数値が負数となる。本発明の一実施形態に係るタイルビニング方法においては、このような半平面エッジ関数の性質を用いて、三角形の全部または一部を含むタイルを判別することができる。
【００４３】
図７は、本発明の一実施形態に係るタイルビニング方法において、三角形の全部または一部を含むタイルを判別する方法の一例を示した図である。
図面では、本発明の一実施形態に係るタイルビニング方法を用いて３×３にタイルを分割し、分割されたタイルの中から三角形の全部または一部を含むタイルを判別する。図面において、各タイルノードに表示されている三つの丸は各タイルノードの第１判別値、第２判別値および第３判別値を意味しており、白円は半平面エッジ関数が正数あるタイルノードを、黒円は半平面エッジ関数が負数であるタイルノードを意味している。
【００４４】
図面に示されたように、図面符号７１０の領域に属する７個のタイル（タイルＣ及びＤ以外のタイル）は、それぞれのタイルに含まれたタイルノードの第１判別値、第２判別値および第３判別値がすべて同一でなく、いずれか一つのタイルノードも第１判別値、第２判別値および第３判別値がすべて正数でない。したがって、７個のタイルは三角形の辺のいずれか一つを含んでいるものであるため、三角形の一部を含むタイルとして判別される。しかし、図面符号７２０のタイル（タイルＣ及びＤ）は、タイルの四つの頂点であるタイルノードがすべて負数の第１判別値を有し、第２判別値および第３判別値が全て正数値を有しているため、三角形の一部さえも含んでいないタイルである。また、図面符号７３０のタイルは、タイルの四つの頂点のタイルノードがすべて正数の第１判別値および第３判別値を有し、第２判別値が全て負数値を有しているため、三角形の一部さえも含んでいないタイルである。
【００４５】
上記したように、各タイルノードの判別値を有していると、簡単な比較演算のみで各タイルが三角形の全部または一部を含むかを判別することができる。また、それぞれのタイルに対して順に判別する必要がないため、すべてのタイルに対して並列的に判別することが可能である。したがって、処理速度を大きく向上させることができるという効果がある。
【００４６】
図８は、本発明の一実施形態に係るタイルビニングシステムの内部構成を示した図である。
図面に示されたように、本発明の一実施形態に係るタイルビニングシステム８０１は、タイル分割部８１０、範囲選別部８２０、判別値決定部８３０およびタイル判別部８４０を含む。上記した構成要素は、ソフトウェア、ハードウェア、またはソフトウェアおよびハードウェアが結合した形態で具現されたり、互いに連結したりする。以下、構成要素別に詳述する。
【００４７】
タイル分割部８１０は、三角形に対してレンダリングを遂行するための画面を複数のタイルに分割する。タイルはユーザに表示される画面解像度を所定のサイズに分けたものであって、それぞれのタイルでレンダリング過程を遂行することで、全体画面に対するレンダリングを遂行することができる。例えば、６４０×４８０の解像度を有する画面を３２×３２の解像度を有するタイルに分割すると、２０×１５個のタイルがレンダリングのために用いられる。このように全体画面を複数のタイルに分割すると、解像度が低いそれぞれのタイルに対してレンダリングを遂行するだけで全体画面のレンダリングを処理することができる。
【００４８】
範囲選別部８２０は、タイル分割部８１０で分割されたタイルのうち、三角形を含む最小の四角形の範囲に含まれるタイルを選別する。タイル分割部８１０で分割されたタイルのうち、レンダリングを遂行しなければならないタイルは、三角形の全部または一部を含むタイルである。したがって、タイルから三角形の全部または一部を含むタイルを判別しなければならない。ここで、四角形は三角形に比べてその範囲が明確であるため、その範囲を容易に判別することができる。したがって、三角形の全部または一部を含むタイルを判別する前に三角形を含む最小の四角形をまず求め、次に最小の四角形の範囲に含まれるタイルを選別することで、タイルビニング作業の対象となるタイルを大きく減らすことができる。
【００４９】
判別値決定部８３０は、範囲選別部８２０で選別されたタイルそれぞれのタイルノードの判別値を決定する。タイルノードはタイルの頂点であり、判別値はタイルノードが三角形を基準としてどのような位置に存在するのかを確認することができるようにする。したがって、判別値決定部８３０で判別値を決定すると、タイルの四つの頂点それぞれが三角形を基準としてどのような位置に存在するかに対する情報を得ることができる。これを用いてそれぞれのタイルが三角形の全部または一部を含むかを確認することができる。
【００５０】
判別値決定部８３０で決定する判別値は、第１判別値、第２判別値および第３判別値を含み、第１判別値、第２判別値および第３判別値はそれぞれ三角形の第１辺、第２辺および第３辺それぞれに対するタイルノードにおける半平面エッジ関数値の符号に基づいて決定される。一例として、半平面エッジ関数値が正数であれば１、負数または０であれば０で決定されたり、正数、負数、０にそれぞれ異なる値を設定したりもする。なお、それぞれのタイルノードで三角形の三つの辺に対する半平面エッジ関数値の符号を確認することができる方法であれば、いかなる方法であっても判別値を記録することができる。半平面エッジ関数値は式（１）を用いて計算することができ、半平面エッジ関数は式（２）の特性を有する。
【００５１】
タイル判別部８４０は、判別値決定部８３０で決定したタイルそれぞれのタイルノードの判別値に基づき、タイルのうち、三角形の全部または一部を含むタイルを判別する。判別値決定部８３０で決定したタイルノードの判別値を用いると、三角形を基準としてタイルノードの位置に関する情報を確認することができるため、タイル判別部８４０では、タイルの各頂点であるタイルノードの三角形を基準とした位置に関する情報を用いて、タイルが三角形の全部または一部を含むかを判別することができる。
【００５２】
一例として、タイル判別部８４０は、結局、タイルのうち、タイルに含まれるタイルノードの第１判別値が互いに同一であり、第２判別値が互いに同一であり、第３判別値が互いに同一であって、タイルノードのいずれか一つの第１判別値、第２判別値および第３判別値の少なくともいずれか一つが負数であるタイルを除いた残りのタイルを三角形の全部または一部を含んでいるものとして判別するようにすることができる。それぞれのタイルのタイルノードの判別値が決定されていると、このような比較過程を並列的に遂行することができるため、演算時間を大きく減らすことができる。
【００５３】
また、タイル判別部８４０では、上記したように、タイルに含まれたすべてのタイルノードの第１判別値、第２判別値および第３判別値が正数である場合にはすべてのタイルノードが三角形の内部に含まれ、タイルノードはタイルの四つの頂点であるため、タイル全体が三角形の内部に含まれるものとして判別することができる。
図９は、本発明の一実施形態に係るタイルビニングシステムにおいて、それぞれのタイルに対して三角形の全部または一部を含むかを並列的に判断するための回路を示した図である。
【００５４】
図面において、図面符号９０１は各タイルに対してタイルビニングを遂行するために構成されたシステムであり、図面符号９１０は各タイルノードの判別値を保存している記録装置であり、図面符号９２０は記録装置９１０に記録された値を用いてタイルビニング方法を遂行する回路装置である。記録装置９１０は、記録装置９１０に対応するタイルノードにおける第１判別値、第２判別値および第３判別値を保存する。第１判別値、第２判別値および第３判別値はそれぞれ半平面エッジ関数値の符号を現わすため１ｂｉｔで表現可能である。したがって、記録装置９１０それぞれは３ｂｉｔの容量で十分である。
【００５５】
また、図面符号９０２は、図面符号９２０の回路装置を示したものである。回路装置は、回路装置で確認することができる四つのタイルノードの保存装置から判別値を受信する。判別値が正数である場合には１、負数である場合には０の値を有する。図面符号９３０では、四つのタイルノードのいずれか一つの第１判別値、第２判別値および第３判別値がすべて１である場合には０を、そうではない場合には１を出力する。また、図面符号９４０では、上から順にそれぞれ第１判別値、第２判別値および第３判別値を比較するが、それぞれの判別値がすべて同一である場合には１を出力し、そうではない場合には０を出力するようになるため、四つのタイルノードの判別値が互いに一致するかを判断することができる。したがって、回路装置は、回路装置が設置されたタイルのタイルノードの一つも判別値がすべて１でなく、それぞれの判別値に対してすべてのタイルノードが同一の判別値を有する場合にのみ１を出力するようになる。このように１が出力されたタイルを除去すると、残ったタイルが三角形の全部または一部を含むタイルとなる。
【００５６】
このように、それぞれのタイル別に一つずつの回路を構成するようになると、簡単な論理演算を並列的に遂行するようになり、短時間でタイルビニングを遂行することができるという効果がある。
以上のような本発明によれば、三角形の全部または一部が含まれるタイルを正確に判別することで、三角形に対するレンダリングが必要ではない部分で不要なレンダリング作業が遂行されないようにすることができる。
【００５７】
また、本発明によれば、半平面エッジ関数の値を用いて三角形の全部または一部が含まれるタイルを正確に判別することができるようにすることができる。
また、本発明によれば、三角形を含む最小の四角形が含まれるタイルに対してのみタイル判別作業を遂行することで、不要な判別作業を減らすようにすることができる。
また、本発明によれば、三角形の全部または一部を含むタイルを判別する作業をタイル別に並列的に遂行することができるようにすることで、判別を迅速に行えることができるようにすることができる。
【００５８】
また、本発明によれば、半平面エッジ関数の特性を用いてすべてのタイルノードに対して半平面エッジ関数を計算しなくても、タイルノードの判別値を決定することができるようにすることができる。
本発明の実施形態に係るタイルビニング方法は、コンピュータにより具現される多様な動作を実行するためのプログラム命令を含むコンピュータ読み取り可能な媒体を含む。媒体は、プログラム命令、データファイル、データ構造などを単独または組み合わせて含むこともできる。媒体およびプログラム命令は、本発明の目的のために特別に設計されて構成されたものでもよく、コンピュータソフトウェア分野の技術を有する当業者にとって公知であり使用可能なものであってもよい。コンピュータ読み取り可能な記録媒体の例としては、ハードディスク、フロッピーディスクおよび磁気テープのような磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤのような光記録媒体、フロプティカルディスクのような磁気−光媒体、およびＲＯＭ、ＲＡＭ、フラッシュメモリなどのようなプログラム命令を保存して実行するように特別に構成されたハードウェア装置が含まれる。媒体は、プログラム命令、データ構造などを保存する信号を送信する搬送波を含む光または金属線、導波管などの送信媒体でもある。プログラム命令の例としては、コンパイラによって生成されるもののような機械語コードだけでなく、インタプリタなどを用いてコンピュータによって実行される高級言語コードを含む。ハードウェアは、本発明の動作を実行するために一以上のソフトウェアモジュールとして作動するように構成され、その逆も同様である。
【００５９】
上述したように、本発明の好ましい実施形態を参照して説明したが、該当の技術分野において熟練した当業者にとっては、特許請求の範囲に記載された本発明の思想および領域から逸脱しない範囲内で、本発明を多様に修正および変更させることができることを理解することができるであろう。すなわち、本発明の技術的範囲は、特許請求の範囲に基づいて定められ、発明を実施するための最良の形態により制限されるものではない。
【図面の簡単な説明】
【００６０】
【図１】従来技術に係るタイル基盤３次元レンダリング方法を示した図である。
【図２ａ】従来技術に係る分割技法を用いたタイルビニング方法を示した図である（１）。
【図２ｂ】従来技術に係る分割技法を用いたタイルビニング方法を示した図である（２）。
【図３】本発明の一実施形態に係るタイルビニング方法の流れを示したフローチャートである。
【図４】本発明の一実施形態に係るタイルビニング方法において、三角形を含む最小の四角形を求める方法の一例を示した図である。
【図５ａ】本発明の一実施形態に係るタイルビニング方法において、それぞれのタイルノードに対する半平面エッジ関数を計算する方法の一例を示した図である（１）。
【図５ｂ】本発明の一実施形態に係るタイルビニング方法において、それぞれのタイルノードに対する半平面エッジ関数を計算する方法の一例を示した図である（２）。
【図５ｃ】本発明の一実施形態に係るタイルビニング方法において、それぞれのタイルノードに対する半平面エッジ関数を計算する方法の一例を示した図である（３）。
【図６】三角形の内部および外部における半平面エッジ関数値の符号を示した図である。
【図７】本発明の一実施形態に係るタイルビニング方法において、三角形の全部または一部を含むタイルを判別する方法の一例を示した図である。
【図８】本発明の一実施形態に係るタイルビニングシステムの内部構成を示した図である。
【図９】本発明の一実施形態に係るタイル基盤タイルビニングシステムにおいて、それぞれのタイルに対して三角形の全部または一部を含むかを並列的に判断するための回路を示した図である。
【符号の説明】
【００６１】
８０１：タイルビニングシステム
８１０：タイル分割部
８２０：範囲選別部
８３０：判別値決定部
８４０：タイル判別部
【図１】
2008027418.tif 000003
【図２ａ】
2008027418.tif 000004
【図２ｂ】
2008027418.tif 000005
【図３】
2008027418.tif 000006
【図４】
2008027418.tif 000007
【図５ａ】
2008027418.tif 000008
【図５ｂ】
2008027418.tif 000009
【図５ｃ】
2008027418.tif 000010
【図６】
2008027418.tif 000011
【図７】
2008027418.tif 000012
【図８】
2008027418.tif 000013
【図９】
2008027418.tif 000014