(57)【要約】予め決められた親頂点に子頂点をプッシュして、ポリゴンのアレイ（５００）からディテールを取り除くシステムおよび方法が記述される。一実施形態では、グラフィックスエンジンは、ポリゴンのアレイ（５００）を低ＬＯＤ領域と高ＬＯＤ領域に分割するＬＯＤ境界（５５３）を特定する。グラフィックスエンジンは、ＬＯＤ境界（５５３）の低ＬＯＤ側に存在する各子頂点を特定するとともに、その子頂点の親頂点を特定する。ポイントプッシング技術の規則を使用して、グラフィックスエンジンは、もしあれば、特定された子頂点のうち親頂点に移行する子頂点を決定する。グラフィックスエンジンは、各移行する子頂点を移動する先となる予め決められた親頂点を特定する。グラフィックスエンジンは、各移行する子頂点をそれぞれの予め決められた親頂点にプッシュする。グラフィックスエンジンはこのプロセスを逆に実行して、ポリゴンのアレイにディテールを追加する。【選択図】図６
2005506612.tif 000002
【特許請求の範囲】
【請求項１】
ソフトウェアを実行するように構成されたプロセッサと、前記ソフトウェアを格納するメモリとを備える、ポリゴンのアレイからディテールを取り除くシステムであって、
前記ソフトウェアが、
前記ポリゴンのアレイの低レベルオブディテール領域に存在する、２つの親頂点を有する子頂点を特定し、
前記２つの親頂点のうちの一方に前記子頂点が移行するか否かを決定し、
前記子頂点が移行する場合、該子頂点を前記２つの親頂点のうちの一方にプッシュするように構成されていることを特徴とするシステム。
【請求項２】
前記ソフトウェアが、前記ポリゴンのアレイを低レベルオブディテール領域と高レベルオブディテール領域とに分割するレベルオブディテール境界を特定するようにさらに構成されていることを特徴とする請求項１に記載のシステム。
【請求項３】
前記ソフトウェアが、子頂点が移行するか否かを決定する前に、該子頂点の２つの親頂点を特定するようにさらに構成されていることを特徴とする請求項１に記載のシステム。
【請求項４】
前記ソフトウェアが、
前記２つの親頂点のうちのひとつを予め決められた親頂点として特定し、
前記子頂点を前記予め決められた親頂点にプッシュすることによって、前記子頂点をプッシュするように構成されていることを特徴とする請求項１に記載のシステム。
【請求項５】
前記ソフトウェアが、ポイントプッシング技術の規則を使用して前記子頂点が移行するか否かを決定するようにさらに構成されていることを特徴とする請求項１に記載のシステム。
【請求項６】
前記ポイントプッシング技術の規則が、２つの親頂点が低レベルオブディテール領域に存在する場合、前記子頂点が移行し、２つの親頂点のうちの一方が低レベルオブディテール領域に存在しない場合、前記子頂点が移行しないことを述べていることを特徴とする請求項５に記載のシステム。
【請求項７】
ソフトウェアを実行するように構成されたプロセッサと、前記ソフトウェアを格納するメモリとを備える、ポリゴンのアレイにディテールを追加するシステムであって、
前記ソフトウェアが、
前記ポリゴンのアレイの高レベルオブディテール領域にある予め決められた親頂点を特定し、
前記予め決められた親頂点と同じ位置にある子頂点であって、該予め決められた親頂点が前記子頂点の２つの親頂点のうちの一方である、子頂点を特定し、
前記子頂点を予め決められた位置に移行するか否かを決定し、
前記子頂点が移行する場合、該子頂点を前記予め決められた位置にプッシュするように構成されていることを特徴とするシステム。
【請求項８】
前記ソフトウェアが、前記ポリゴンのアレイを高レベルオブディテール領域と低レベルオブディテール領域とに分割するレベルオブディテール境界を特定するようにさらに構成されていることを特徴とする請求項７に記載のシステム。
【請求項９】
前記ソフトウェアが、子頂点が移行するか否かを決定する前に、該子頂点のもう一方の親頂点を特定するようにさらに構成されていることを特徴とする請求項７に記載のシステム。
【請求項１０】
前記ソフトウェアが、ポイントプッシング技術の規則を使用して前記子頂点が移行するか否かを決定するようにさらに構成されていることを特徴とする請求項７に記載のシステム。
【請求項１１】
前記ポイントプッシング技術の規則が、２つの親頂点が高レベルオブディテール領域に存在する場合、前記子頂点が移行し、２つの親頂点のうちの一方が高レベルオブディテール領域に存在しない場合、前記子頂点が移行しないことを述べていることを特徴とする請求項１０に記載のシステム。
【請求項１２】
ポリゴンのアレイからディテールを取り除くポイントプッシング方法であって、
前記ポリゴンのアレイの低レベルオブディテール領域に存在する、２つの親頂点を有する子頂点を特定するステップと、
前記２つの親頂点のうちの一方に前記子頂点が移行するか否かを決定するステップと、
前記子頂点が移行する場合、該子頂点を前記２つの親頂点のうちの一方にプッシュするステップと、
を含むことを特徴とする方法。
【請求項１３】
前記ポリゴンのアレイを低レベルオブディテール領域と高レベルオブディテール領域とに分割するレベルオブディテール境界を特定するステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記子頂点が移行するか否かを決定する前に、該子頂点の２つの親頂点を特定するステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１５】
前記子頂点をプッシュするステップが、
前記２つの親頂点のうちのひとつを予め決められた親頂点として特定するステップと、
前記子頂点を前記予め決められた親頂点にプッシュするステップと、
を含むことを特徴とする請求項１２に記載の方法。
【請求項１６】
前記子頂点が移行するか否かを決定するステップがポイントプッシング技術の規則を使用することを含むことを特徴とする請求項１２に記載の方法。
【請求項１７】
前記ポイントプッシング技術の規則が、２つの親頂点が低レベルオブディテール領域に存在する場合、前記子頂点が移行し、２つの親頂点のうちの一方が低レベルオブディテール領域に存在しない場合、前記子頂点が移行しないことを述べていることを特徴とする請求項１６に記載の方法。
【請求項１８】
ポリゴンのアレイにディテールを追加するポイントプッシング方法であって、
ポリゴンのアレイの高レベルオブディテール領域にある予め決められた親頂点を特定するステップと、
前記予め決められた親頂点と同じ位置にある子頂点であって、該予め決められた親頂点が前記子頂点の２つの親頂点のうちの一方である、子頂点を特定するステップと、
前記子頂点が予め決められた位置に移行するか否かを決定するステップと、
前記子頂点が移行する場合、該子頂点を前記予め決められた位置にプッシュするステップと、
を含むことを特徴とする方法。
【請求項１９】
前記ポリゴンのアレイを高レベルオブディテール領域と低レベルオブディテール領域とに分割するレベルオブディテール境界を特定するステップをさらに含むことを特徴とする請求項１８に記載の方法。
【請求項２０】
前記子頂点が移行するか否かを決定する前に、該子頂点のもう一方の親頂点を特定するステップをさらに含むことを特徴とする請求項１８に記載の方法。
【請求項２１】
前記子頂点が移行するか否かを決定するステップがポイントプッシング技術の規則を使用することを含むことを特徴とする請求項１８に記載の方法。
【請求項２２】
前記ポイントプッシング技術の規則が、２つの親頂点が高レベルオブディテール領域に存在する場合、前記子頂点が移行し、２つの親頂点のうちの一方が高レベルオブディテール領域に存在しない場合、前記子頂点が移行しないことを述べていることを特徴とする請求項２１に記載の方法。
【請求項２３】
ポリゴンのアレイからディテールを取り除くシステムであって、
前記ポリゴンのアレイの低レベルオブディテール領域に存在する、２つの親頂点を有する子頂点を特定する手段と、
前記２つの親頂点のうち一方に前記子頂点が移行するか否かを決定する手段と、
前記子頂点が移行する場合、該子頂点を前記２つの親頂点のうちの一方にプッシュする手段と、
を含むことを特徴とするシステム。
【請求項２４】
前記ポリゴンのアレイを低レベルオブディテール領域と高レベルオブディテール領域とに分割するレベルオブディテール境界を特定する手段をさらに含むことを特徴とする請求項２３に記載のシステム。
【請求項２５】
前記子頂点が移行するか否かを決定する前に、該子頂点の２つの親頂点を特定する手段をさらに含むことを特徴とする請求項２３に記載のシステム。
【請求項２６】
前記子頂点をプッシュする手段が、
前記２つの親頂点のうちのひとつを予め決められた親頂点として特定する手段と、
前記子頂点を前記予め決められた親頂点にプッシュする手段と、
を含むことを特徴とする請求項２３に記載のシステム。
【請求項２７】
前記子頂点が移行するか否かを決定する手段がポイントプッシング技術の規則を使用することを含むことを特徴とする請求項２３に記載のシステム。
【請求項２８】
前記ポイントプッシング技術の規則が、２つの親頂点が低レベルオブディテール領域に存在する場合、前記子頂点が移行し、２つの親頂点のうちの一方が低レベルオブディテール領域に存在しない場合、前記子頂点が移行しないことを述べていることを特徴とする請求項２７に記載のシステム。
【請求項２９】
ポリゴンのアレイにディテールを追加するシステムであって、
前記ポリゴンのアレイの高レベルオブディテール領域にある予め決められた親頂点を特定する手段と、
前記予め決められた親頂点と同じ位置にある子頂点であって、該予め決められた親頂点が前記子頂点の２つの親頂点のうちの一方である、子頂点を特定する手段と、
前記子頂点を予め決められた位置に移行するか否かを決定する手段と、
前記子頂点が移行する場合、該子頂点を前記予め決められた位置にプッシュする手段と、
を含むことを特徴とするシステム。
【請求項３０】
前記ポリゴンのアレイを高レベルオブディテール領域と低レベルオブディテール領域とに分割するレベルオブディテール境界を特定する手段をさらに含むことを特徴とする請求項２９に記載のシステム。
【請求項３１】
前記子頂点が移行するか否かを決定する前に、該子頂点のもう一方の親頂点を特定する手段をさらに含むことを特徴とする請求項２９に記載のシステム。
【請求項３２】
前記前記子頂点が移行するか否かを決定する手段がポイントプッシング技術の規則を使用することを含むことを特徴とする請求項２９に記載のシステム。
【請求項３３】
前記ポイントプッシング技術の規則が、２つの親頂点が高レベルオブディテール領域に存在する場合、前記子頂点が移行し、２つの親頂点のうちの一方が高レベルオブディテール領域に存在しない場合、前記子頂点が移行しないことを述べていることを特徴とする請求項３２に記載のシステム。
【請求項３４】
ポリゴンのアレイの低レベルオブディテール領域に存在する、２つの親頂点を有する子頂点を特定するステップと、
前記２つの親頂点のうちの一方に前記子頂点が移行するか否かを決定するステップと、
前記子頂点が移行する場合、該子頂点を前記２つの親頂点のうちの一方にプッシュするステップと、
を実行することによって、コンピュータにポリゴンのアレイからディテールを取り除かせる命令を格納するコンピュータ可読媒体。
【請求項３５】
前記ポリゴンのアレイを低レベルオブディテール領域と高レベルオブディテール領域とに分割するレベルオブディテール境界を特定するステップをさらに含むことを特徴とする請求項３４に記載のコンピュータ可読媒体。
【請求項３６】
前記子頂点が移行するか否かを決定する前に、該子頂点の２つの親頂点を特定するステップをさらに含むことを特徴とする請求項３４に記載のコンピュータ可読媒体。
【請求項３７】
前記子頂点をプッシュするステップが、
前記２つの親頂点のうちのひとつを予め決められた親頂点として特定するステップと、
前記子頂点を前記予め決められた親頂点にプッシュするステップと、
を含むことを特徴とする請求項３４に記載のコンピュータ可読媒体。
【請求項３８】
前記子頂点が移行するか否かを決定するステップがポイントプッシング技術の規則を使用することを含むことを特徴とする請求項３４に記載のコンピュータ可読媒体。
【請求項３９】
前記ポイントプッシング技術の規則が、２つの親頂点が低レベルオブディテール領域に存在する場合、前記子頂点が移行し、２つの親頂点のうちの一方が低レベルオブディテール領域に存在しない場合、前記子頂点が移行しないことを述べていることを特徴とする請求項３８に記載のコンピュータ可読媒体。
【請求項４０】
ポリゴンのアレイの高レベルオブディテール領域にある予め決められた親頂点を特定するステップと、
前記予め決められた親頂点と同じ位置にある子頂点であって、該予め決められた親頂点が前記子頂点の２つの親頂点のうちの一方である、子頂点を特定するステップと、
前記子頂点が予め決められた位置に移行するか否かを決定するステップと、
前記子頂点が移行する場合、該子頂点を前記予め決められた位置にプッシュするステップと、
を実行することによって、コンピュータにポリゴンのアレイにディテールを追加させる命令を格納するコンピュータ可読媒体。
【請求項４１】
前記ポリゴンのアレイを高レベルオブディテール領域と低レベルオブディテール領域とに分割するレベルオブディテール境界を特定するステップをさらに含むことを特徴とする請求項４０に記載のコンピュータ可読媒体。
【請求項４２】
前記子頂点が移行するか否かを決定する前に、該子頂点のもう一方の親頂点を特定するステップをさらに含むことを特徴とする請求項４０に記載のコンピュータ可読媒体。
【請求項４３】
前記子頂点が移行するか否かを決定するステップがポイントプッシング技術の規則を使用することを含むことを特徴とする請求項４０に記載のコンピュータ可読媒体。
【請求項４４】
前記ポイントプッシング技術の規則が、２つの親頂点が高レベルオブディテール領域に存在する場合、前記子頂点が移行し、２つの親頂点のうちの一方が高レベルオブディテール領域に存在しない場合、前記子頂点が移行しないことを述べていることを特徴とする請求項４３に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００１年１０月１０日に出願された「解像度を計算するためのポイントプッシング方法（Point Pushing Method for Calculating Resolution）」と題する米国仮特許出願第６０／３２８，４５３号の利益を主張する。関連する出願の主要な事項は、参照により本明細書に援用される。関連する出願は本発明の譲受人に譲渡されている。
【０００２】
本発明は、一般にコンピュータグラフィックスに関し、より詳細には、レベルオブディテールが変化する環境でポリゴンを描画するポイントプッシング技術（point pushing technique）を使用するシステムおよび方法に関する。
【背景技術】
【０００３】
描画オブジェクトの解像度は、一般にそのオブジェクトを生成するために使用したポリゴン数に関係する。所与の領域に対して多数のポリゴンを含む描画オブジェクトは、通常、同じ領域に対して少数のポリゴンを含むオブジェクトよりも高い解像度を有する。
【０００４】
グラフィックスエンジンまたはグラフィックスソフトウェアは、通常、オブジェクトの描画時に、「ストリッピング（stripping）」として知られる技術を実施する。ストリッピングはポリゴン生成方法のひとつであり、これにより、普通は中央処理ユニットおよびグラフィックス処理ユニットであるプロセッサが、比較的少ない処理能力を使用して多数のポリゴンを生成することが可能になる。したがって、ストリッピングによってグラフィックスエンジンまたはグラフィックスソフトウェアは、より高速にかつコストをかけずに、より解像度の高いオブジェクトを描画することができる。このため、ストリッピング・アルゴリズムを利用するビデオゲームや他のコンピュータプログラムおよび他のコンピュータアプリケーション向けに高解像度のグラフィックスを作成するほうが、ストリッピング・アルゴリズムを利用しないゲーム、プログラムおよびアプリケーション向けに高解像度のグラフィックスを作成するよりも簡単であり、かつコストもかからない。
【０００５】
一般に、ストリッピングは、ストリップ内のポリゴンのリンク付けが必要であり、グラフィックスエンジンまたはグラフィックスソフトウェアは、新しい頂点をストリップの一端から作り出し、それらの新しい頂点を、ストリップの一端上の最後のポリゴンの頂点と接続することで、追加のポリゴンを生成することができる。追加のポリゴンとストリップ内の最後にあったポリゴンとは、グラフィックスエンジンまたはグラフィックスソフトウェアが新しい頂点を接続した先の頂点を共有する。三角形は、ストリッピング・アルゴリズムにおいてもっとも普通に使用されるポリゴンである。これは、グラフィックスエンジンまたはグラフィックスソフトウェアが、ただひとつの新しい頂点を作成し、その頂点をストリップ内の最後の三角形の２つの頂点のそれぞれと接続することによって、ストリップに追加の三角形を描画することができるからである。
【０００６】
オブジェクトを描画するとき、グラフィックスエンジンまたはグラフィックスソフトウェアは、通常、画像スクリーンを種々のポリゴンのアレイ（これを「メッシュ」と呼ぶこともある）に分割する。任意の所与の時間において、ある特定のメッシュは、ひとつまたは複数の解像度レベルすなわちレベルオブディテール（levels of details、以下、「ＬＯＤ」という）を有する。このＬＯＤは、メッシュ内に表された描画オブジェクトの解像度レベルが異なる部分に対応する。メッシュの高ＬＯＤ領域は、メッシュの低ＬＯＤ領域が含むよりも、より小さなポリゴンとより多数のポリゴンの両方を含む。メッシュの高ＬＯＤ領域とメッシュの低ＬＯＤ領域の間の境界を、「ＬＯＤ境界」と呼ぶ。
【０００７】
ＬＯＤ境界がメッシュ内のポリゴンのうちのひとつと交差するとき、グラフィックスエンジンまたはグラフィックスソフトウェアは、ＬＯＤ境界の高ＬＯＤ側に追加のポリゴンを生成し、メッシュのその部分にディテールを追加する。ＬＯＤ領域と追加されたポリゴンの一辺との間の交差領域は、「Ｔ接点（T-junction）」と呼ばれる。この結果、元のポリゴンのうち一部（これを「低解像度パッチ」と呼ぶ）のみがＴ接点の低ＬＯＤ側に存在し、いくつかのより小さなポリゴン（これを「高解像度パッチ」と呼ぶ）がＴ接点の高ＬＯＤ側に存在することになる。低解像度パッチと高解像度パッチとは正確に整列しないことが多く、これによって、スクリーン画像中に「クラック（crack）」が生ずる。クラックとは、描画オブジェクトの高解像度部分の中に背景画像の一部が現れる場所である。グラフィックスエンジンまたはグラフィックスソフトウェアがＬＯＤ境界の低ＬＯＤ側に位置するメッシュの一部からディテールを除いたときにも、これと同じ現象が生じる。
【０００８】
上述したＴ接点問題に対処するスキームがいくつか存在する。しかしながら、これらの従来技術は、グラフィックスエンジンまたはグラフィックスソフトウェアのストリッピング実行能力を損なう傾向がある。その結果、Ｔ接点問題に対処するように設計されたシステムがストリッピングの効率を失って低解像度のグラフィックスを生成するようになり、また、ストリッピングを保持するシステムが、クラックを生じるグラフィックスを作成することが多くなる。
【発明の開示】
【０００９】
予め決められた親頂点に子頂点をプッシュしてポリゴンのアレイからディテールを取り除くシステムおよび方法の一実施形態は、前記ポリゴンのアレイを低ＬＯＤ領域と高ＬＯＤ領域とに分割するＬＯＤ境界を特定するグラフィックスエンジンから始まる。続いて、グラフィックスエンジンは、ＬＯＤ境界の低ＬＯＤ側に存在する、ポリゴンのアレイ内の各子頂点を特定する。グラフィックスエンジンは、このような子頂点それぞれの親頂点も特定する。次に、グラフィックスエンジンは、もしあるならば、ＬＯＤ境界の低ＬＯＤ側に存在する子頂点のうち、親頂点に移行（migrate）する子頂点を決定する。グラフィックスエンジンは、ポイントプッシング技術の規則（point pushing technique rule）を使用して、この決定を行う。この規則の一実施例によれば、親頂点の両方がＬＯＤ境界の低ＬＯＤ側に存在する場合、子頂点は親頂点のうちの一方に移行する。しかしながら、親頂点のいずれかがＬＯＤ境界の高ＬＯＤ側に存在する場合、子頂点は移行しない。移行する各子頂点に対して、グラフィックスエンジンは、その子頂点を移動する先である親頂点を特定する。これら親頂点はそれぞれ、「予め決められた（predetermined）親頂点」と呼ばれる。最後に、グラフィックスエンジンは、各移行する子頂点をそれぞれの予め決められた親頂点にプッシュ（push）する。子頂点がその移行を完了すると、ポリゴンのアレイの低ＬＯＤ領域は高ＬＯＤ領域よりも低いディテールを有する。
【００１０】
システムおよび方法の別の実施形態によれば、グラフィックスエンジンは、上述のプロセスを本質的に逆に実行することによって、ポリゴンのアレイにディテールを追加する。初めに、グラフィックスエンジンは、ポリゴンのアレイを高ＬＯＤ領域と低ＬＯＤ領域とに分割するＬＯＤ境界を特定する。続いて、グラフィックスエンジンは、ＬＯＤ境界の高ＬＯＤ側にあるすべての予め決められた親頂点を特定する。加えて、グラフィックスエンジンは、特定された予め決められた親頂点の任意のものと同じ位置を有する各子頂点を特定するとともに、そのような各子頂点のもう一方の親頂点も特定する。次に、グラフィックスエンジンは、もしあれば、それらの子頂点のうち移行する子頂点を決定する。グラフィックスエンジンは、再びポイントプッシング技術の規則を使用して、この決定を行う。一実施形態では、ポイントプッシング技術の規則は、ＬＯＤ境界の高ＬＯＤ側に親頂点の両方が存在する場合、その子頂点が移行することを記述する。しかしながら、親頂点のいずれかがＬＯＤ境界の低ＬＯＤ側に存在する場合には、子頂点は移行しない。最後に、グラフィックスエンジンは、各移行する子頂点を予め決められた位置にプッシュする。子頂点がそれぞれの移行を完了すると、ポリゴンのアレイの高ＬＯＤ領域は低ＬＯＤ領域よりも高いディテールを有する。
【００１１】
上述のシステムおよび方法の実施形態の利点のひとつは、グラフィックスエンジンがポリゴンのアレイの低ＬＯＤ領域からディテールを取り除くかまたは高ＬＯＤ領域にディテールを追加したとき、アレイ内のポリゴンのストリップがその整合性（integrity）を保持することである。別の利点は、ポリゴンのアレイの低ＬＯＤ領域と高ＬＯＤ領域の間にクラックを出現させることなく、グラフィックスエンジンがディテールを取り除いたり追加したりできることである。
【発明を実施するための最良の形態】
【００１２】
図１は、本発明による電子エンタテインメントシステム１００の一実施形態のブロック図である。システム１００は、メインメモリ１１０と、中央処理装置（ＣＰＵ）１１２と、ベクトル処理ユニットＶＵ０  １１１およびＶＵ１  １１３と、グラフィックス処理ユニット（ＧＰＵ）１１４と、入出力プロセッサ（ＩＯＰ）１１６と、ＩＯＰメモリ１１８と、コントローラインターフェイス１２０と、メモリカード１２２と、ユニバーサルシリアルバス（ＵＳＢ）インターフェイス１２４と、ＩＥＥＥ１３９４インターフェイス１２６とを含むが、これらに限定されない。システム１００はまた、オペレーティングシステム・リードオンリメモリ（ＯＳ  ＲＯＭ）１２８と、サウンド処理ユニット（ＳＰＵ）１３２と、光ディスク制御ユニット１３４と、ハードディスクドライブ（ＨＤＤ）１３６とを含み、これらはバス１４６を介してＩＯＰ１１６に接続される。システム１００は、好ましくは、電子ゲームコンソールである。しかしながら、システム１００は、汎用コンピュータ、セットトップボックス、または携帯型ゲーム装置の任意のタイプとして実施することもできる。
【００１３】
ＣＰＵ１１２、ＶＵ０  １１１、ＶＵ１  １１３、ＧＰＵ１１４、およびＩＯＰ１１６は、システムバス１４４を介して通信する。ＣＰＵ１１２は、専用バス１４２を介してメインメモリ１１０と通信する。ＶＵ１  １１３およびＧＰＵ１１４も、専用バス１４０を介して通信することができる。ＣＰＵ１１２は、ＯＳ  ＲＯＭ１２８およびメインメモリ１１０に格納されたプログラムを実行する。メインメモリ１１０は、予め記憶されたプログラムを含むことができ、また、光ディスク制御ユニット１３４を使用して、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭまたは他の光ディスク（図示せず）からＩＯＰ１１６を介して転送されたプログラムを含むこともできる。ＩＯＰ１１６は、ＣＰＵ１１２、ＶＵ０  １１１、ＶＵ１  １１３、ＧＰＵ１１４およびシステム１００の他の装置、例えばコントローラインターフェイス１２０の間のデータ交換を制御する。
【００１４】
ＧＰＵ１１４は、ＣＰＵ１１２およびＶＵ０  １１１からの描画命令を実行し、ディスプレイ装置（図示せず）上に表示する画像を作成する。ＶＵ１  １１３は、オブジェクトを三次元座標から二次元座標に変換し、その二次元座標をＧＰＵ１１４に送る。ＳＰＵ１３２は、命令を実行して、オーディオ装置（図示せず）に出力する音声信号を作成する。本発明の一実施形態では、ＧＰＵ１１４、ＣＰＵ１１２およびメインメモリ１１０内の特定のグラフィックスソフトウェアは、協働して「グラフィックスエンジン」として動作する。
【００１５】
システム１００のユーザは、コントローラインターフェイス１２０を介してＣＰＵ１１２に命令を与える。例えばユーザは、ＣＰＵ１１２に対してメモリカード１２２上に特定のゲーム情報を記憶するように命令することができるし、あるいは、ゲーム中のキャラクタにある指定された動作を実行するように命令することができる。ＵＳＢインターフェイス１２４およびＩＥＥＥ１３９４インターフェイス１２６を介して、他の装置がシステム１００に接続されていてもよい。
【００１６】
図２は、本発明の一実施形態にしたがった、描画ポリゴン２１０の親頂点と子頂点の間の関係を説明する図である。図示するように、ポリゴン２１０は三角形であるが、他の実施形態では、ポリゴン２１０は任意のタイプのポリゴンであってよい。ポリゴン２１０は３つの親頂点２１２、２１４および２１６を有しており、各親頂点はポリゴン２１０の頂点でもある。加えて、ポリゴン２１０は３つの子頂点２１８、２２０および２２２を有している。各子頂点はポリゴン２１０の一辺上に位置する点であり、２つの親頂点からなるセットがそれぞれ、ひとつの子頂点を有するようになっている。例えば、子頂点２１８は親頂点２１２と親頂点２１６の子であり、子頂点２２０は親頂点２１２と親頂点２１４の子であり、子頂点２２２は親頂点２１４と親頂点２１６の子である。図２に示す矢印は、子頂点２１８、２２０および２２２のそれぞれの親頂点を指している。本発明の一実施形態では、子頂点は、その２つの親頂点の間の中間点である。
【００１７】
一般的に述べると、グラフィックスエンジンは、親頂点および子頂点を使用して、描画オブジェクト（または、描画オブジェクトの一部）にディテールを追加するか、または描画オブジェクトからディテールを除くことができる。例えば、ディテールを追加するとき、グラフィックスエンジンは初めに、描画オブジェクト内の各ポリゴンの親頂点のセットのそれぞれについて、子頂点を生成する。次に、グラフィックスエンジンは、描画オブジェクトの予想される（anticipated）輪郭内の予め決められた位置に、各子頂点をプッシュ、すなわち移動する（このような子頂点の運動を「移行（migrate）」と呼ぶ）。グラフィックスエンジンはまた、親頂点と同様に子頂点を互いに接続することによって、描画オブジェクトの輪郭内に追加のポリゴンを生成する。グラフィックスエンジンは、ストリッピング・アルゴリズムまたは他の方法を使用して、追加のポリゴンを生成することができる。各子頂点は、ひとつまたは複数の追加ポリゴンの頂点となり、したがって、このような各追加ポリゴンの親頂点となる。この結果、その描画オブジェクトを元々構成していたポリゴンよりも小さなポリゴンおよび多数のポリゴンの両方から描画オブジェクトが構成されることになり、これにより、その描画オブジェクトが元々有していたよりも高いレベルオブディテールを当該描画オブジェクトに与える。
【００１８】
描画オブジェクトにさらにディテールを追加するとき、グラフィックスエンジンは上述のプロセスを繰り返す。唯一の違いは、今度の描画オブジェクトがより多数のポリゴンを含むことである。グラフィックスエンジンは、最初に、描画オブジェクト内の各ポリゴンの親頂点のセットそれぞれについて、子頂点を生成する。次に、グラフィックスエンジンは、描画オブジェクトの予想される輪郭内の予め決められた位置に、各子頂点を移動させる。再び、グラフィックスエンジンは、親頂点と同様に子頂点を互いに接続することによって、描画オブジェクトの輪郭内に追加のポリゴンを生成する。やはり、各子頂点は、ひとつまたは複数の追加ポリゴンの親頂点となる。この結果、最初のレベルオブディテールの追加後にその描画オブジェクトを構成していたよりも小さいポリゴンおよび多数のポリゴンの両方から当該描画オブジェクトが構成されることになり、これによって、最初のレベルオブディテールの追加後にその描画オブジェクトが有していたよりも高いレベルオブディテールを、当該描画オブジェクトに与える。
【００１９】
図３Ａおよび図３Ｂは、図２とともに述べた、グラフィックスエンジンが親頂点と子頂点を使用して描画オブジェクト３１０にディテールを追加する方法を説明する図である。より具体的には、図３Ａは、描画オブジェクト３１０が画像スクリーンの低ＬＯＤ領域から中間ＬＯＤ領域に移動するときの、グラフィックスエンジンによるディテールの追加を示している。図示するように、描画オブジェクト３１０は、低ＬＯＤ領域内では正方形で表されている。説明を簡単にするため、描画オブジェクト３１０を、４つの親頂点３１２、３１４、３１６、３１８を有する単一のポリゴンとしてモデリングできると仮定する。
【００２０】
描画オブジェクト３１０が画像スクリーン内を低ＬＯＤ領域から中間ＬＯＤ領域に移動するとき、グラフィックスエンジンは描画オブジェクト３１０にディテールを追加する。図２とともに述べたように、必要なディテールを追加するため、最初にグラフィックスエンジンは、描画オブジェクト３１０の親頂点のセットがそれぞれひとつの子頂点を有するように、子頂点３２０、３２２、３２４、３２６を生成する。例えば、子頂点３２０は親頂点３１２と親頂点３１４の子であり、子頂点３２２は親頂点３１４と親頂点３１６の子であり、子頂点３２４は親頂点３１６と親頂点３１８の子であり、子頂点３２６は親頂点３１２と親頂点３１８の子である。
【００２１】
次に、グラフィックスエンジンは、描画オブジェクト３２８の予想される輪郭内の予め決められた位置に各子頂点を移動する。移行経路３３０、３３２、３３４、３３６は、それぞれ、グラフィックスエンジンが子頂点３２０、３２２、３２４、３２６を移動する経路を示す。
【００２２】
グラフィックスエンジンはまた、描画オブジェクト３１０の輪郭内に追加ポリゴンを生成し、必要な量の追加のディテールを持った描画オブジェクト３１０を作成する。説明を簡単にするため、図３Ａは、子頂点３２０、３２２、３２４、３２６と、親頂点３１２、３１４、３１６、３１８との間の接続を構成する追加のポリゴンの辺のみを示す。この結果、描画オブジェクト３２８である八角形が、描画オブジェクト３１０である正方形よりも高いディテールを有する。
【００２３】
図３Ｂは、描画オブジェクト３２８が画像スクリーンの中間ＬＯＤ領域から高ＬＯＤ領域に移動するときの、グラフィックスエンジンによるディテールの追加を示している。図示するように、描画オブジェクト３２８は、中間ＬＯＤ領域では八角形で表されている。やはり、説明を簡単にするため、描画オブジェクト３２８を、８つの親頂点３１２、３１４、３１６、３１８、３２０、３２２、３２４、３２６を有する単一のポリゴンとしてモデリングできるものと仮定する。
【００２４】
描画オブジェクト３２８が画像スクリーン内を中間ＬＯＤ領域から高ＬＯＤ領域に移動するとき、グラフィックスエンジンは描画オブジェクト３２８にディテールを追加する。必要なディテールを追加するため、最初にグラフィックスエンジンは、描画オブジェクト３２８の親頂点のセットがそれぞれひとつの子頂点を有するように、子頂点３３８、３４０、３４２、３４４、３４６、３４８、３５０、３５２を生成する。例えば、子頂点３３８は親頂点３１２と親頂点３２０の子であり、子頂点３４０は親頂点３１４と親頂点３２０の子であり、子頂点３４２は親頂点３１４と親頂点３２２の子であり、子頂点３４４は親頂点３１６と親頂点３２２の子であり、子頂点３４６は親頂点３１６と親頂点３２４の子であり、子頂点３４８は親頂点３１８と親頂点３２４の子であり、子頂点３５０は親頂点３１８と親頂点３２６の子であり、子頂点３５２は親頂点３１２と親頂点３２６の子である。
【００２５】
次に、グラフィックスエンジンは、描画オブジェクト３５４の予想される輪郭内の予め決められた位置に各子頂点を移動する。移行経路３５６、３５８、３６０、３６２、３６４、３６６、３６８、３７０は、それぞれ、グラフィックスエンジンが子頂点３３８、３４０、３４２、３４４、３４６、３４８、３５０、３５２を移動する経路を示す。
【００２６】
グラフィックスエンジンはまた、描画オブジェクト３２８の輪郭内に追加ポリゴンを生成し、必要な量の追加ディテールを持った描画オブジェクト３２８を作成する。説明を簡単にするため、図３Ｂは、子頂点３３８、３４０、３４２、３４４、３４６、３４８、３５０、３５２と、親頂点３１２、３１４、３１６、３１８、３２０、３２２、３２４、３２６との間の接続を構成する追加のポリゴンの辺のみを示す。この結果、描画オブジェクト３５４である十六角形のポリゴンは、描画オブジェクト３２８である八角形よりも高いディテールを有する。
【００２７】
グラフィックスエンジンは、上述のステップを単に逆に実行することで、描画オブジェクト３５４または描画オブジェクト３２８のいずれかからディテールを取り除くことができる。例えば、描画オブジェクト３５４が画像スクリーンの高ＬＯＤ領域から中間ＬＯＤ領域に移動する場合、グラフィックスエンジンは、図３Ｂとともに上述したステップを逆に実行して、描画オブジェクト３５４からディテールを取り除き、描画オブジェクト３５４を描画オブジェクト３２８に変換することができる。同様に、描画オブジェクト３２８が画像スクリーンの中間ＬＯＤ領域から低ＬＯＤ領域に移動する場合、グラフィックスエンジンは、図３Ａとともに上述したステップを逆に実行して、描画オブジェクト３２８からディテールを取り除き、描画オブジェクト３２８を描画オブジェクト３１０に変換することができる。
【００２８】
図３Ａおよび図３Ｂとともに述べた例は、円形の物体（例えば、車のタイヤ）が画像スクリーン内の描画オブジェクトであり、車のタイヤが画像スクリーン内の異なるＬＯＤ領域間を移動する状況に対応している。車のタイヤが全体画像の背景内にあるとき、車のタイヤは画像スクリーン内の低ＬＯＤ領域内にある。画像システムは、車のタイヤを正方形として示す。これは、車のタイヤが画像の残りの部分と比べて大変小さく、画像システムのユーザは、正方形と円とを区別することができないからである。したがって、正方形の車のタイヤは、ユーザには円のように見える。
【００２９】
車のタイヤがさらに移動して全体画像の前面に出てくると、車のタイヤは画像スクリーン内の中間ＬＯＤ領域に来る。今度は、画像システムは、車のタイヤをより詳細に表す必要がある。なぜなら、車のタイヤは画像の残りの部分と比べて比較的大きく、画像システムのユーザは車のタイヤをよりはっきりと視認することができるからである。このため、画像システムは、車のタイヤの正方形バージョンよりも詳細なディテールを持つ八角形として車のタイヤを表す。
【００３０】
車のタイヤがさらに移動を続け全体画像の前面に出てくると、車のタイヤは画像スクリーン内の高ＬＯＤ領域に来る。今度は、画像システムは、車のタイヤの八角形バージョンよりもさらに詳細な車のタイヤを表す必要がある。なぜなら、画像システムのユーザによって、車のタイヤは八角形バージョンよりも大きくかつはっきりと視認されるからである。したがって、画像システムは、八角形バージョンの車のタイヤよりも詳細度の高い十六角形のポリゴンとして車のタイヤを表現する。車のタイヤが画像システムのユーザに接近すればするほど、グラフィックスエンジンは、辺の数が増えディテール量が増加したポリゴンで車のタイヤを表現する。極限的には、車のタイヤの形状は実際の円の形状に近づく。
【００３１】
図４は、本発明の一実施形態によるポイントプッシング技術の規則を説明する図である。図示するように、３つのポリゴン４１０、４３０および４５０が画像スクリーン４００内に表示されている。ポリゴン４１０は、３つの親頂点４１８、４２０、４２２と、３つの子頂点４１２、４１４、４１６とを有する。ポリゴン４３０は、３つの親頂点４３８、４４０、４４２と、３つの子頂点４３２、４３４、４３６とを有する。ポリゴン４５０は、３つの親頂点４５８、４６０、４６２と、３つの子頂点４５２、４５４、４５６とを有する。ＬＯＤ境界４０５は、画像スクリーン４００を低ＬＯＤ領域と高ＬＯＤ領域とに分割する。
【００３２】
本発明の一実施形態によるポイントプッシング技術の規則は、以下の通りである。子頂点の両方の親頂点がＬＯＤ境界の低ＬＯＤ側に存在するとき、グラフィックスエンジンは、子頂点をその親頂点のうちのひとつにプッシュ、すなわち移動させる。この規則を実施するシステムは、グラフィックスエンジンが子頂点をプッシュする先の親頂点を予め決定しておく（これを、「予め決められた親頂点」と呼ぶ）。しかしながら、子頂点の親頂点のうちいずれかがＬＯＤ境界の高ＬＯＤ側に存在するとき、グラフィックスエンジンは子頂点をプッシュすなわち移動しない。代わりに、子頂点をその元の位置に留まらせる。
【００３３】
ポイントプッシング技術の規則は、ポリゴン４１０に対して以下のように適用される。子頂点４１２の親である親頂点４１８と親頂点４２２は、両方ともＬＯＤ境界４０５の低ＬＯＤ側に存在する。上記規則にしたがって、グラフィックスエンジンは、図４に矢印で示すように、子頂点４１２を予め決められた親頂点４１８にプッシュする。子頂点４１４の親である親頂点４１８と親頂点４２０は、両方ともＬＯＤ境界４０５の低ＬＯＤ側に存在する。上記規則にしたがって、グラフィックスエンジンは、図４に矢印で示すように、子頂点４１４を予め決められた親頂点４１８にプッシュする。子頂点４１６の親である親頂点４２０と親頂点４２２は、両方ともＬＯＤ境界４０５の低ＬＯＤ側に存在する。再び上記規則にしたがって、グラフィックスエンジンは、図４に矢印で示すように、子頂点４１６を予め決められた親頂点４２０にプッシュする。
【００３４】
ポイントプッシング技術の規則は、ポリゴン４３０に対して以下のように適用される。子頂点４３４の親である親頂点４３８と親頂点４４０は、両方ともＬＯＤ境界４０５の低ＬＯＤ側に存在する。上記規則にしたがって、グラフィックスエンジンは、図４に矢印で示すように、子頂点４３４を予め決められた親頂点４４０にプッシュする。子頂点４３６の親である親頂点４４０と親頂点４４２は、ＬＯＤ境界４０５の反対の側にある。上記規則にしたがって、子頂点４３６は移動せず、その元の位置に留まる。同様に、子頂点４３２の親である親頂点４３８と親頂点４４２は、ＬＯＤ境界４０５の反対の側にある。上記規則にしたがって、子頂点４３２は移動せず、その元の位置に留まる。
【００３５】
ポイントプッシング技術の規則は、ポリゴン４５０に対して以下のように適用される。子頂点４５２の親である親頂点４５８と親頂点４６２は、両方ともＬＯＤ境界４０５の高ＬＯＤ側に存在する。上記規則にしたがって、子頂点４５２は移動せず、その元の位置に留まる。子頂点４５４の親である親頂点４５８と親頂点４６０は、両方ともＬＯＤ境界４０５の高ＬＯＤ側に存在する。上記規則にしたがって、子頂点４５４は移動せず、その元の位置に留まる。同様に、子頂点４５６の親である親頂点４６０と親頂点４６２は、両方ともＬＯＤ境界４０５の高ＬＯＤ側にある。再び上記規則にしたがって、子頂点４５６は移動せず、その元の位置に留まる。
【００３６】
図３Ａおよび図３Ｂとともに述べたように、描画オブジェクトが画像スクリーンの高ＬＯＤ側から低ＬＯＤ側に移動するとき、グラフィックスエンジンは描画オブジェクトからディテールを取り除く。グラフィックスエンジンは、低ＬＯＤに相応するディテール量を描画オブジェクトが有するようになるまで、描画オブジェクトからポリゴンを除去することによってこの目的を達成する。
【００３７】
上記に関連して、描画オブジェクトが画像スクリーン内を移動するとき、ＬＯＤ境界の異なるタイプが、グラフィックスエンジンによって画像スクリーンが分割された結果であるポリゴンのアレイすなわちメッシュと交差する。画像スクリーンの高ＬＯＤ領域内に特定のメッシュが最初から存在し、描画オブジェクトが移動することによって、ＬＯＤ境界が当該メッシュを低ＬＯＤ領域と高ＬＯＤ領域に分割するような状況では、グラフィックスエンジンは、メッシュの低ＬＯＤ領域からディテールを取り除かなければならない。描画オブジェクトからディテールを取り除くのと同様に、グラフィックスエンジンは、メッシュのその部分が低ＬＯＤ領域に相応するディテール量を有するようになるまで、その領域内のポリゴンを除去することによってメッシュの低ＬＯＤ領域からディテールを取り除く。
【００３８】
図５Ａ、図５Ｂ、図６および図７とともに後述する議論は、本発明のポイントプッシング方法を使用して、グラフィックスエンジンがポリゴンのアレイの任意の領域からディテールを取り除くとともに、（ｉ）従来技術とともに述べたＴ接点問題を回避し、（ｉｉ）ストリッピング中にポリゴンを生成するグラフィックスエンジンの能力を保持する方法を開示する。
【００３９】
図５Ａは、本発明にしたがった、画像スクリーンの低ＬＯＤ領域に位置するメッシュ５００の一実施形態を示す図である。メッシュ５００は、水平ストリップおよび垂直ストリップ内に配置されたポリゴンのアレイの一実施例である。図示するように、メッシュ５００は、３つのポリゴンの水平ストリップ５０２、５０４、５０６と、４つのポリゴンの垂直ストリップ５０８、５１０、５１２、５１４とを含む。いくつかのポリゴンの親頂点も示されている。例えば、親頂点５１６、５１８、５２２は、あるポリゴンの頂点であり、親頂点５１８、５２０、５２２は、あるポリゴンの頂点であり、親頂点５２４、５２６、５３０は、あるポリゴンの頂点であり、親頂点５２６、５２８、５３０は、あるポリゴンの頂点であり、親頂点５３２、５３４、５３８は、あるポリゴンの頂点であり、親頂点５３４、５３６、５３８はさらに別のポリゴンの頂点である。
【００４０】
図５Ｂは、図５Ａのメッシュ５００が画像スクリーンの高ＬＯＤ領域に位置する場合を示すとともに、本発明の一実施形態にしたがって、グラフィックエンジンがポイントプッシング技術の規則を適用してメッシュ５００の低ＬＯＤ領域からディテールを取り除く様子を示す図である。図示するように、メッシュ５００が画像スクリーンの高ＬＯＤ領域に位置するとき、メッシュ５００は、６つのポリゴンの水平ストリップ５３９、５４０、５４１、５４２、５４３、５４４と、８つのポリゴンの垂直ストリップ５４５、５４６、５４７、５４８、５４９、５５０、５５１、５５２とを含む。図５Ａと図５Ｂとを比較すればわかるように、メッシュ５００は、画像スクリーンの低ＬＯＤ領域に位置するときと比べて、高ＬＯＤ領域に位置するとき、より小さなポリゴンおよびより多数のポリゴンの両方を含む。このため、メッシュ５００は、画像スクリーンの低ＬＯＤ領域に位置するときよりも、画像スクリーンの高ＬＯＤ領域に位置するときにより詳細なディテールを示す。
【００４１】
より具体的には、図５Ｂは、画像スクリーンの高ＬＯＤ領域に位置するとき、低ＬＯＤ領域に位置するときの４倍多くのポリゴンを含むことを示している。グラフィックスエンジンは、高ＬＯＤ領域において、メッシュ５００が、図５Ａに描いたポリゴン（それぞれを、「元のポリゴン」と呼ぶ）のそれぞれについて４つのポリゴンを効率的に含むように、ポリゴンを生成する。例えば、グラフィックスエンジンは、図５Ａに示す頂点５１６、５１８、５２２により定義される元のポリゴンを、頂点５１６、５５４、５６２によって定義されるポリゴンと、頂点５５４、５１８、５６０によって定義されるポリゴンと、頂点５５４、５６０、５６２によって定義されるポリゴンと、頂点５６２、５６０、５２２によって定義されるポリゴンと、で効率的に置換している。同様に、グラフィックスエンジンは、図５Ａに示す頂点５２６、５２８、５３０により定義される元のポリゴンを、頂点５２６、５６６、５７０によって定義されるポリゴンと、頂点５７０、５６６、５６８によって定義されるポリゴンと、頂点５７０、５６８、５３０によって定義されるポリゴンと、頂点５６６、５２８、５６８によって定義されるポリゴンと、で効率的に置換している。
【００４２】
図５Ｂは、元のポリゴンそれぞれの各親頂点セットの子頂点も示している。例えば、子頂点５５４は親頂点５１６と親頂点５１８の子であり、子頂点５５６は親頂点５１８と親頂点５２０の子であり、子頂点５５８は親頂点５２０と親頂点５２２の子であり、子頂点５６０は親頂点５１８と親頂点５２２の子であり、子頂点５６２は親頂点５１６と親頂点５２２の子である。同様に、子頂点５６４は親頂点５２４と親頂点５２６の子であり、子頂点５６６は親頂点５２６と親頂点５２８の子であり、子頂点５７８は親頂点５３６と親頂点５３８の子であり、子頂点５８０は親頂点５３４と親頂点５３８の子であり、子頂点５８２は親頂点５３２と親頂点５３８の子である。
【００４３】
図５ＢにはＬＯＤ境界５５３も示されており、このＬＯＤ境界５５３はメッシュ５００と交差して、ＬＯＤ境界５５３の一方の側に低ＬＯＤ領域を、ＬＯＤ境界５５３のもう一方側に高ＬＯＤ領域を作成する。図６および図７とともに詳細に説明するように、グラフィックスエンジンは、本発明のポイントプッシング方法を使用してメッシュ５００の低ＬＯＤ領域からディテールを取り除く。図５Ｂに描かれた矢印は予め決められた頂点を示しており、グラフィックスエンジンは、この予め決められた頂点に対して、ポイントプッシング技術の規則の一実施形態にしたがって各子頂点をプッシュする。例えば、上記規則にしたがって、親頂点５１６と親頂点５１８の両方がＬＯＤ境界５５３の低ＬＯＤ領域に存在するので、グラフィックスエンジンは子頂点５５４を予め決められた親頂点５１８にプッシュする。同様に、上記規則にしたがって、親頂点５３２と親頂点５３４の両方がＬＯＤ境界５５３の低ＬＯＤ側に存在するので、グラフィックスエンジンは子頂点５７４を予め決められた親頂点５３４にプッシュする。対照的に、上記規則にしたがって、親頂点５２６がＬＯＤ境界５５３の低ＬＯＤ側にあり、親頂点５３０がＬＯＤ境界５５３の高ＬＯＤ側にあるので、子頂点５７０は、その元の位置に留まる。同様に、上記規則にしたがって、親頂点５３６と親頂点５３８の両方がＬＯＤ境界５５３の高ＬＯＤ側に存在するので、子頂点５７８はその元の位置に留まる。
【００４４】
図６は、図５Ｂの子頂点が図５Ｂの予め決められた親頂点に移行する様子を示す図である。図示するように、グラフィックスエンジンは、図５Ｂに示したメッシュ５００に適用されたポイントプッシング技術の規則によって説明したとおりに、メッシュ５００の低ＬＯＤ領域に位置する特定の子頂点を、それぞれの予め決められた親頂点に向けてプッシュしている。例えば、図５Ｂと図６に示すように、グラフィックスエンジンは子頂点５６２を予め決められた親頂点５１６に向けてプッシュし、子頂点５５４、５５６、５６０を予め決められた親頂点５１８に向けてプッシュし、子頂点５５８を予め決められた親頂点５２０に向けてプッシュし、子頂点５６４を予め決められた親頂点５２６に向けてプッシュし、子頂点５７４を予め決められた親頂点５３４に向けてプッシュする。同じく図５Ｂと図６に示すように、子頂点５６６、５６８、５７０、５７２は、子頂点５７６、５７８、５８０、５８２と同様に、それぞれの元の位置に留まる。これは、それら各子頂点の親頂点のいずれか一方（または両方）が、ＬＯＤ境界５５３の高ＬＯＤ側に存在するからである。
【００４５】
図６に示すように、メッシュ５００の低ＬＯＤ領域にある特定の子頂点が、それぞれの予め決められた親頂点に向けて移行するとき、これらのストリップ内のポリゴンの多くが崩壊し始めるにつれて、ストリップ５３９、５４１、５４６、５４８、５５０、５５２の一部分が狭くなる。対照的に、ストリップ５４０、５４２、５４５、５４７、５４９、５５１の一部分が同時に広くなる。この結果、ストリップ５４０とストリップ５４５の交差部分、ストリップ５４２と５４５の交差部分、ストリップ５４０と５４７の交差部分、ストリップ５４２とストリップ５４７の交差部分、ストリップ５４０とストリップ５４９の交差部分、ストリップ５４２とストリップ５４９の交差部分、ストリップ５４０とストリップ５５１の交差部分に位置するポリゴンのサイズが増加して、崩壊するポリゴンによって開放される空間をこれらのポリゴンが埋める。この現象の結果、より大きくかつより少数のポリゴンがメッシュ５００の低ＬＯＤ領域を支配し始めるが、これはメッシュ５００のその領域におけるディテールの量を減少させる。
【００４６】
重要なことは、図６が、いくつかの子頂点がそれぞれの予め決められた親頂点に向かって移行するときに、グラフィックスエンジンがメッシュ５００内の各ストリップの整合性を保持していることを示している点である。ストリップ内のいくつかのポリゴンは、直角三角形であった元の形状を保ってはいないが、それにもかかわらず、各ストリップは、メッシュ５００の一端から他端に至るまでその形状を維持している。
【００４７】
さらに、本発明のポイントプッシング方法により、グラフィックスエンジンが、ＬＯＤ境界にＴ接点を作成したり使用したりすることなく、メッシュ５００の低ＬＯＤ領域内のポリゴンを崩壊させることが可能となる。図６は、ポイントプッシングにより、ＬＯＤ境界５５３に沿っていくつかの遷移ポリゴンが形成している様子を示す。ポリゴン６１０、６１２、６１４、６１６、６１８、６２０、６２２、６２４、６２６、６２８、６３０、６３２は、遷移ポリゴンの例である。これらの遷移ポリゴンは、ＬＯＤ境界５５３にまたがって、メッシュ５００の低ＬＯＤ領域内のポリゴンと高ＬＯＤ領域内のポリゴンとの間に、小さくかつ効率的な遷移領域を形成する。遷移ポリゴンが遷移領域を完全に埋めるために、画像スクリーンにはクラックが現れない。これによって、頂点を共有している高解像度パッチと低解像度パッチとの間の境界からＴ接点を排除している。ポイントプッシング技術を使用することによって、グラフィックスエンジンは、その不整列がしばしばクラックの発生原因となる、高解像度パッチと低解像度パッチとの位置あわせをする必要がなくなる。
【００４８】
図７は、図５Ｂの子頂点を図５Ｂの予め決められた親頂点にさらに移行した様子を示す図である。図示するように、グラフィックスエンジンは、ポイントプッシング技術の規則によって述べたように、メッシュ５００の低ＬＯＤ領域に位置する特定の子頂点を、それぞれの予め決められた親頂点のさらに近くにプッシュする。例えば、図７に示すように、グラフィックスエンジンは、子頂点５６２を予め決められた親頂点５１６のさらに近くにプッシュし、子頂点５５４、５５６、５６０を予め決められた親頂点５１８のさらに近くにプッシュし、子頂点５５８を予め決められた親頂点５２０のさらに近くにプッシュし、子頂点５６４を予め決められた親頂点５２６のさらに近くにプッシュし、子頂点５７４を予め決められた親頂点５３４のさらに近くにプッシュする。再び、図６に示すように、子頂点５６６、５６８、５７０、５７２は、子頂点５７６、５７８、５８０、５８２と同様に、それぞれの元の位置に留まり続けるが、これは、これら子頂点のそれぞれの親頂点のいずれか一方（または両方）が、ＬＯＤ境界５５３の高ＬＯＤ側に存在するからである。
【００４９】
図７に示すように、メッシュ５００の低ＬＯＤ領域における特定の子頂点が、それぞれの予め決められた親頂点に向かってさらに移行すると、ストリップ５３９、５４１、５４６、５４８、５５０、５５２は、それらのストリップ内のポリゴンの多くがさらに崩壊するにつれて狭くなる。対照的に、ストリップ５４０、５４２、５４５、５４７、５４９、５５１は、同時にさらに広くなる。ストリップ５４０と５４５の交差部分、ストリップ５４２とストリップ５４５の交差部分、ストリップ５４０とストリップ５４７の交差部分、ストリップ５４２とストリップ５４７の交差部分、ストリップ５４０とストリップ５４９の交差部分、ストリップ５４２とストリップ５４９の交差部分、ストリップ５４０とストリップ５５１の交差部分に位置するポリゴンのサイズが増加して、崩壊するポリゴンによって開放される空間をこれらのポリゴンが埋める。この現象の結果、少数の大きなポリゴンがメッシュ５００の低ＬＯＤ領域を支配するが、これはメッシュ５００のその領域におけるディテールの量をさらに減少させる。
【００５０】
図７から、それぞれの予め決められた親頂点への子頂点の以降が継続するとき、グラフィックスエンジンは、各ストリップの整合性を保持し続けるということがわかる。また、いくつかの子頂点がその移行を完了すると、ストリップ５３９、５４１、５４６、５４８、５５０、５５２における多くのポリゴンが完全に崩壊し消滅することもわかる。その結果、メッシュ５００の低ＬＯＤ領域が、（メッシュ５００のすべてが画像スクリーンの低ＬＯＤ領域に位置するとき）図５Ａに描いたメッシュ５００とほぼ同様になる。さらに、メッシュ５００の高ＬＯＤ領域が、（メッシュ５００のすべてが画像スクリーンの高ＬＯＤ領域に位置するとき）図５Ｂに描いたメッシュ５００とほぼ同様になる。最後に、図６とともに上述したように、一旦子頂点がその移行を完了すると、メッシュ５００の低ＬＯＤ領域内のポリゴンと高ＬＯＤ領域内のポリゴンの間に遷移ポリゴンが存在し、クラックのない連続遷移領域を形成する。その結果、パッチ間で頂点を共有する高解像度パッチと低解像度パッチの間の領域にＴ接点が存在しなくなる。
【００５１】
図８は、本発明の一実施形態にしたがって、子頂点を予め決められた親頂点にプッシュして、ポリゴンのアレイの低ＬＯＤ領域からディテールを取り除く方法ステップのフローチャートである。この方法ステップは、図１に示したシステム１００のサブシステムであるグラフィックスエンジンの文脈で説明するが、この方法ステップを実行するように構成された任意のタイプのシステム、エンジン、プロセッサ、プロセッサの組合せまたはソフトウェアも本発明の範囲内である。
【００５２】
図８に示すように、ステップ８１０において、グラフィックスエンジンは、ポリゴンのアレイを低ＬＯＤ領域と高ＬＯＤ領域とに分割するＬＯＤ境界を特定する。図２から図５Ｂとともに上述したように、これらの異なるレベルオブディテールは相対的に比較される。ステップ８１２において、グラフィックスエンジンは、ＬＯＤ領域の低ＬＯＤ側に存在するポリゴンのアレイ内のあらゆる子頂点を特定する。ステップ８１４において、グラフィックスエンジンは、そのような子頂点のそれぞれの親頂点を特定する。
【００５３】
次に、ステップ８１６において、グラフィックスエンジンは、もしあれば、ＬＯＤ境界の低ＬＯＤ側に存在する子頂点のうち、親頂点に移行する子頂点を決定する。グラフィックスエンジンは、ポイントプッシング技術の規則を使用してこの決定を行う。上記規則の一実施形態にしたがって、親頂点の両方がＬＯＤ領域の低ＬＯＤ側に存在する場合、子頂点はその親頂点のうちのひとつに移行する。しかしながら、親頂点のいずれかがＬＯＤ境界の高ＬＯＤ側に存在する場合、子頂点は移行しない。
【００５４】
ステップ８１８において、移行する各子頂点について、グラフィックスエンジンがその子頂点を移動すると特定した親頂点を特定する。図４とともに上述したように、これら親頂点のいずれかが「予め決められた親頂点」と呼ばれる。最後に、ステップ８２０において、グラフィックスエンジンは、各移行する子頂点をそれぞれの予め決められた親頂点に対してプッシュ、すなわち移動する。
【００５５】
図６および図７とともに上述したように、子頂点がそれぞれの親頂点への移行を完了すると、ポリゴンのアレイの低ＬＯＤ領域は高ＬＯＤ領域よりもディテールが小さくなる。さらに、ポリゴンのアレイ内のポリゴンのストリップはその整合性を保持し、ポリゴンのアレイの低ＬＯＤ領域と高ＬＯＤ領域の間にクラックは表れない。
【００５６】
本発明の別の実施形態にしたがって、画像スクリーンの低ＬＯＤ領域内に位置するポリゴンのアレイにディテールを加えるために、グラフィックスエンジンは、図５Ａから図８とともに上述したプロセスを本質的に逆に実行する。グラフィックスエンジンは、最初に、ポリゴンのアレイを高ＬＯＤ領域と低ＬＯＤ領域に分割するＬＯＤ領域を特定する。続いて、グラフィックスエンジンは、ＬＯＤ領域の高ＬＯＤ側にあるあらゆる予め決められた親頂点を特定する。グラフィックスエンジンはまた、任意の特定された親頂点と同じ位置を有する各子頂点と、そのような子頂点それぞれのもう一方の親頂点とを特定する（予め決められた親頂点は、同時に、子頂点の一方の親でもあることに注意されたい）。
【００５７】
次に、グラフィックスエンジンは、もしあれば、これらの子頂点のうち移行するものを決定する。グラフィックスエンジンは、再び、ポイントプッシング技術の規則を使用してこの決定を行う。一実施形態では、ポイントプッシング技術の規則は、その親頂点の両方がＬＯＤ境界の高ＬＯＤ側に存在する場合、子頂点が移行することを述べている。しかしながら、親頂点のいずれか一方が、ＬＯＤ境界の低ＬＯＤ側に存在する場合、子頂点は移行しない。
【００５８】
最後に、グラフィックスエンジンは、移行する各子頂点を予め決められた位置にプッシュする。これらの子頂点がそれぞれの予め決められた位置への移行を完了すると、ポリゴンのアレイの高ＬＯＤ領域に最初に存在した大きなポリゴンのサイズが減少する。さらに、グラフィックスエンジンは、移行する子頂点を相互に接続し、また高ＬＯＤ領域内に存在する親頂点に接続することによって、ポリゴンのアレイの高ＬＯＤ領域内に追加のポリゴンを生成する。その結果、ポリゴンのアレイの高ＬＯＤ領域が、低ＬＯＤ領域よりも小さくかつ多数のポリゴンの両方を有するようになり、高ＬＯＤ領域におけるディテールの量を増加する。
【００５９】
ポリゴンのアレイからディテールを除くときと同様に、グラフィックスエンジンは、アレイの高ＬＯＤ領域にディテールを加えるときに、ポリゴンのアレイ内のポリゴンのストリップの整合性を保存する。さらに、グラフィックスエンジンは、ＬＯＤ領域のいずれか一方の側に遷移ポリゴンを生成するが、これは、ポリゴンのアレイの低ＬＯＤ領域と高ＬＯＤ領域との間にクラックが出現することを防止する。
【００６０】
本発明を、いくつかの実施形態を参照して説明した。しかしながら、当業者は、添付の特許請求の範囲に述べた本発明のより広範な精神および範囲から逸脱することなく、種々の修正および変更をなしえることを理解するであろう。例えば、説明を簡単にすべく、上述の議論および例で参照した本発明の一実施形態は、簡単な形状（例えば、三角形）の少数のポリゴンを含むポリゴンのアレイについて記載した。しかし、本発明の別の実施形態は、任意のタイプの形状（簡単なものと複雑なものの両方）の任意の数のポリゴンを含むポリゴンのアレイを扱うことができる。したがって、上述の説明および図面は、限定的な意味よりもむしろ例示とみなされるべきである。
【図面の簡単な説明】
【００６１】
【図１】本発明による電子エンタテインメントシステムの一実施形態のブロック図である。
【図２】本発明の一実施形態にしたがった、描画ポリゴンの親頂点と子頂点の間の関係を説明する図である。
【図３Ａ】図２とともに説明した、グラフィックスエンジンが親頂点と子頂点を使用して描画オブジェクトにディテールを追加する方法を説明する図である。
【図３Ｂ】図２とともに説明した、グラフィックスエンジンが親頂点と子頂点を使用して描画オブジェクトにディテールを追加する方法を説明する図である。
【図４】本発明の一実施形態によるポイントプッシング技術の規則を説明する図である。
【図５Ａ】本発明にしたがった、画像スクリーンの低ＬＯＤ領域に位置するメッシュの一実施形態を説明する図である。
【図５Ｂ】画像スクリーンの高ＬＯＤ領域に位置する図５Ａのメッシュを示すとともに、本発明の一実施形態にしたがって、グラフィックエンジンがポイントプッシング技術の規則を適用してメッシュの低ＬＯＤ領域からディテールを取り除く様子を示す図である。
【図６】図５Ｂの子頂点が図５Ｂの予め決められた親頂点に移行する様子を示す図である。
【図７】図５Ｂの子頂点を図５Ｂの予め決められた親頂点にさらに移行した様子を示す図である。
【図８】本発明の一実施形態にしたがって、子頂点を予め決められた親頂点にプッシュして、ポリゴンのアレイからディテールを取り除く方法ステップのフローチャートである。
【図１】
2005506612.tif 000003
【図２】
2005506612.tif 000004
【図３Ａ】
2005506612.tif 000005
【図３Ｂ】
2005506612.tif 000006
【図４】
2005506612.tif 000007
【図５Ａ】
2005506612.tif 000008
【図５Ｂ】
2005506612.tif 000009
【図６】
2005506612.tif 000010
【図７】
2005506612.tif 000011
【図８】
2005506612.tif 000012
【国際公開パンフレット】
2005506612.tif 000013
2005506612.tif 000014
2005506612.tif 000015
2005506612.tif 000016
2005506612.tif 000017
2005506612.tif 000018
2005506612.tif 000019
2005506612.tif 000020
2005506612.tif 000021
2005506612.tif 000022
2005506612.tif 000023
2005506612.tif 000024
2005506612.tif 000025
2005506612.tif 000026
2005506612.tif 000027
2005506612.tif 000028
2005506612.tif 000029
2005506612.tif 000030
2005506612.tif 000031
2005506612.tif 000032
2005506612.tif 000033
2005506612.tif 000034
2005506612.tif 000035
2005506612.tif 000036
2005506612.tif 000037
2005506612.tif 000038
2005506612.tif 000039
2005506612.tif 000040
2005506612.tif 000041
2005506612.tif 000042
2005506612.tif 000043
2005506612.tif 000044
2005506612.tif 000045
2005506612.tif 000046
2005506612.tif 000047
2005506612.tif 000048
2005506612.tif 000049
2005506612.tif 000050
2005506612.tif 000051
2005506612.tif 000052
2005506612.tif 000053
2005506612.tif 000054
【国際調査報告】
2005506612.tif 000055
2005506612.tif 000056