コンピュータ生成画像をレンダリングするための方法及び装置
ステンシルバッファを使用してコンピュータ生成画像をレンダリングするための方法及び装置について説明する。この方法は、任意閉多角形輪郭線を、任意閉多角形輪郭線内の連続する頂点に対応する第１のレベルのプリミティブと、直前のプリミティブレベルの連続するプリミティブの終端頂点に対応する上位レベルのプリミティブとに分割する。この方法は、ステンシルバッファを使用して任意多角形輪郭線をレンダリングする場合の過剰描画のレベルを、他の画像空間法に比べて低減する。輪郭線の最後の第１のレベルのプリミティブの前に作成された第２の及びより上位レベルのプリミティブと交互になった順序でプリミティブを生成する方法について説明し、この方法により、プリミティブが生成されるにつれて、これらの間でより多くの頂点を再使用することによりキャッシュヒット率を改善する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、少なくとも１つの閉多角形輪郭線を含むコンピュータ生成画像をレンダリングするための方法及び装置に関する。具体的には、本発明は、画像空間計算及び標準グラフィックスハードウェアを使用した、凹部、自己交差、さらには複数の「輪郭線」の存在をも許容する「任意」形状の多角形を含む画像のレンダリングに関する。
【背景技術】
【０００２】
通常、コンピュータ生成画像内には数多くの個別の多角形が存在する。多くの場合、グラフィックスレンダリングハードウェア、特に３Ｄグラフィックスハードウェアは、三角形プリミティブ、或いは、時にその他の凸多角形、すなわち全ての内角が１８０°よりも小さな多角形をレンダリングする能力しか有していない。このような多角形は、比較的容易にレンダリングされる。このような仕様は、任意多角形のいずれの部分を内部と見なし、いずれの部分を外部と見なすべきかを決定する「塗りつぶしルール」を含む。ＳＶＧは、「偶数−奇数」及び「非ゼロ」という２つのこのようなルールを定義する。本明細書では、説明を簡単にするために、通常は「偶数−奇数」ルールの使用を前提とするが、当業者には、提示する技術がその他の明確な塗りつぶしルールにも当てはまることが明らかであろう。
【０００３】
図１ａに、（凹多角形、自己交差を含む多角形、及び複数輪郭線で構成された多角形を含む）「任意」多角形のいくつかの例を示す。図１ａ及び図１ｅは、それぞれ凹多角形、すなわち内角の少なくとも１つが１８０°よりも大きな多角形の例を示している。図１ｂは、自己交差を含む多角形、すなわち２つの頂点間の各線分の全ての部分が多角形の境界内又は境界上に留まるとは限らない多角形の例を示している。図１ｃは、複数の輪郭線を含む多角形、すなわち、全体的形状を定義するために外部輪郭線と内部輪郭線が必要な穴を含む多角形の例を示している。図１ｄは、全てのこれらの特徴を含む多角形の例を示している。
【０００４】
このような任意多角形をレンダリングする傍ら凸多角形にも対応する能力は、例えばＳＶＧ（スケーラブルベクトルグラフィックス）及びＯｐｅｎＶＧ（オープンベクトルグラフィックス）などのベクトルグラフィックス規格をサポートするためなどの多くの理由により有用である。ＳＶＧは、２次元グラフィックス及びグラフィックアプリケーションをＸＭＬ（拡張マークアップ言語）で記述するための言語である。ＯｐｅｎＶＧは、ハードウェア加速型２次元ベクトルグラフィックス向けに設計された、著作権使用料が無料のアプリケーションプログラミングインターフェイス（ＡＰＩ）である。当然ながら、任意多角形をレンダリングできる方法は、いずれも凸多角形を処理できなければならない。
【０００５】
このようなハードウェア上で任意多角形をレンダリングできる方法には２つの系列がある。第１の系列は、モデル空間内で計算を行うものであり、一般に三角形分割アルゴリズムと呼ばれる。これらのアルゴリズムは、多角形の外形を取得して、元の多角形の塗りつぶし領域を正確に補う重なり合わない三角形の組を作成する。本明細書では、他の「三角形分割」の使用と混同しないように、このようなアルゴリズムを「真の三角形分割」と呼ぶ。このような処理を図１ａの多角形に適用した考えられる結果の例を図２に示す。このように、原形を三角形｛［ｖ２，ｖ３，ｖ５］、［ｖ３，ｖ４，ｖ５］、［ｖ５，ｖ６，ｖ２］、［ｖ６，ｖ２，ｖ７］、［ｖ７，ｖ２，ｖ１］｝で構築することができる。Ｎ個の辺を有する単純多角形を想定し、これ以上頂点を追加しないと想定すると（アルゴリズムによっては追加の頂点を導入できるものもある）、Ｎ−２個の三角形が得られる。これらの三角形は、一度作成したら、いずれかの市販のグラフィックスハードウェア上で容易にレンダリングすることができる。
【０００６】
「真の三角形分割」処理のためのアルゴリズムは数多く公開されてきた。Ｌａｍｏｔ及びＺａｌｉｋが、「単純多角形のための三角形分割アルゴリズムの概要（Ａｎ ｏｖｅｒｖｉｅｗ ｏｆ ｔｒｉａｎｇｕｌａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｓｉｍｐｌｅ ｐｏｌｙｇｏｎｓ）」（Ｉｎｆｏｒｍａｔｉｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ、１９９９年、１５３〜１５８ページ）において方法の概論を示している。これらの文献の方法は、図１（ａ）及び図１（ｅ）などの単純多角形に限定したものがほとんどであり、すなわちこれらの方法は、（繰り返し頂点を含む）自己交差も、複数の輪郭線も含むことができない。とは言うものの、Ｍｅｉｓｔｅｒの「イヤーカッティング（ｅａｒ ｃｕｔｔｉｎｇ）」（又はイヤークリッピング（ｅａｒ ｃｌｉｐｐｉｎｇ））アルゴリズム、及びＳｅｉｄｅｌの方法は本考察にとって興味深い。
【０００７】
Ｍｅｉｓｔｅｒの方法は、（単純）多角形から頂点を１つずつ除去して、切り詰めた多角形を単純な状態で残すものである。この方法は、３つの連続する頂点により形成される「耳」を多角形から繰り返し「切り取る」ものである。このアルゴリズムはＯ（ｎ3）時間で実行され、後でＯ（ｎ2）に改善されたが、比較的頂点の少ない多角形を除き、特に魅力的なものではない。
【０００８】
一方、Ｓｅｉｄｅｌの方法は、単純多角形ではｌｏｇ*（ｎ）を次式のように定義するＯ（ｎｌｏｇ*ｎ）時間で実行される。
【０００９】
従って、ｎがいずれかの適正値の場合、Ｏ（ｎｌｏｇ*ｎ）を実際にはＯ（ｎ）と見なすことができる。上述したように、任意多角形を処理する「真の三角形分割」アルゴリズムはほとんど公開されていない。Ｈｅｌｄの方法（「多角形の高速強力三角形分割（ＦＩＳＴ：Ｆａｓｔ Ｉｎｄｕｓｔｒｉａｌ−Ｓｔｒｅｎｇｔｈ Ｔｒｉａｎｇｕｌａｔｉｏｎ ｏｆ Ｐｏｌｙｇｏｎｓ）」、Ａｌｇｏｒｉｔｈｍｉｃａ第３０巻、第４号、５６３〜５９６ページ）は、これらの数少ない例外の１つである。イヤークリッピングに基づくものであるが、単純多角形では追加構造を使用してより良好な時間計算量を達成するものの、本発明者には、自己交差などが存在する場合にこの方法がどのような挙動を示すかは明らかでない。
【００１０】
本出願の発明者は、任意多角形を完全にサポートするように強化したバージョンのＳｅｉｄｅｌのアルゴリズムを実践した。このアルゴリズムは、（自己交差によって形成される潜在的頂点が「ｎ」に含まれると仮定して）依然として事実上線形の性能を実現する。しかしながら、〜２ＧＨｚのＣＰＵ上では、この処理は、多角形の頂点当たり依然として平均１〜２μｓを要する。数多くのフレームにわたって複数回描画される多角形では、三角形分割の結果をキャッシュに記憶することができるので、事前処理コストがレンダリング処理により償却される。しかしながら、多角形が数回しか描画されず、又はフレーム単位で劇的に変化して再三角形分割が強いられるような状況では、真の三角形分割処理は極めて不利益となる恐れがある。（なお、モデルに線形変換を適用すると再三角形分割は不要となる。）
【００１１】
任意多角形をレンダリングできる方法の第２の系列は、画像空間計算を使用するものである。この場合、レンダリング／サンプリング処理自体が、いずれの画素が任意多角形の内部に含まれ、いずれが外部に存在するかを判定するように構成される。この方法は、走査線レンダリングアルゴリズムを使用して行うことができるが、本発明者らは主に、任意多角形をより小さな多角形（通常は三角形）に分割し、これらの小さな多角形に関してハードウェアがレンダリングを直接サポートしてこれらをレンダリングし、ハードウェアのステンシルバッファを利用して、レンダリングした画素のいずれが元の任意多角形の内部に存在するかを判定する方法に関心がある。当業では、ステンシルバッファを使用することにより任意多角形を描画できることが周知である（Ｓｈｒｅｉｎｅｒ他著「ＯｐｅｎＧＬプログラミングガイド：ＯｐｅｎＧＬバージョン１．４公式習得ガイド（ＯｐｅｎＧＬ ｐｒｏｇｒａｍｍｉｎｇ ｇｕｉｄｅ： ｔｈｅ ｏｆｆｉｃｉａｌ ｇｕｉｄｅ ｔｏ ｌｅａｒｎｉｎｇ ＯｐｅｎＧＬ， ｖｅｒｓｉｏｎ １．４）」、ＩＳＢＮ０３２１１７３４８１）。例えば、ステンシルにＸＯＲ演算を適用することにより、奇数−偶数ルールを実践することができる。同様に、三角形の屈曲順序を考慮に入れた場合、ステンシルの増分及び減分を使用して非ゼロルールを実践することができる。
【００１２】
いずれの塗りつぶしルールの場合にも、まずソース多角形から三角形の組を作成しなければならない。Ｓｈｒｅｉｎｅｒ他の第１３章、「ステンシルバッファを使用した塗りつぶし凹多角形の描画（Ｄｒａｗｉｎｇ Ｆｉｌｌｅｄ， Ｃｏｎｃａｖｅ Ｐｏｌｙｇｏｎｓ Ｕｓｉｎｇ ｔｈｅ Ｓｔｅｎｃｉｌ Ｂｕｆｆｅｒ）」の節（ｈｔｔｐ：／／ｆｌｙ．ｃｃ．ｆｅｒ．ｈｒ／〜ｕｎｒｅａｌ／ｔｈｅｒｅｄｂｏｏｋ／ｃｈａｐｔｅｒ１３．ｈｔｍｌ又はｈｔｔｐ：／／ｗｗｗ．ｓｃｒｉｂｄ．ｃｏｍ／ｄｏｃ／７６０５３９５／Ｒｅｄｂｏｏｋで閲覧可能）に明白な方法が記載されている。この場合、頂点を単純に［ｖ１，ｖ２，ｖ３，．．．ｖＮ］の順番で提示することにより三角形の扇（Ｓｈｒｅｉｎｅｒ他の第２章、又はｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｔｒｉａｎｇｌｅ ｆａｎを参照）が作成され、これにより頂点を｛［ｖ1，ｖ2，ｖ3］，［ｖ1，ｖ3，ｖ4］，［ｖ1，ｖ4，ｖ5］，．．．［ｖ1，ｖN-1，ｖN］｝とするＮ−２個の三角形の組が暗黙的に作成される。
【００１３】
Ｓｈｒｅｉｎｅｒ他による例（図１（ａ））を借りて、この処理の一部を図３に示す。７本の辺を有する図を、５つの三角形の扇としてレンダリングする。奇数−偶数塗りつぶしルールを仮定すれば、奇数個の三角形で覆われた網目部分の画素は内部と見なされ、偶数個で覆われたものは外部となる。例えば、ｖ１、ｖ３、及び場所２０で境界された領域は、三角形［ｖ1，ｖ2，ｖ3］及び［ｖ1，Ｖ3，ｖ4］によって覆われている。ステンシルバッファがゼロに初期化され、ＸＯＲ演算が使用されると仮定すると、三角形［ｖ1，ｖ2，ｖ3］を描画することで、まず領域［ｖ1，ｖ3，「２０」］の全ての画素のステンシル値が設定されるが、その後これらは三角形［ｖ1，ｖ3，ｖ4］によって再び消去される。この結果、この領域は、多角形に対して外部にあると正しく判断される。この処理の単純さは極めて魅力的であり、この処理は三角形の扇を使用するので、Ｎ個の頂点をグラフィックスハードウェアへ送信すればよい。
【００１４】
いずれの画素が多角形の内部に存在するかを示すようにステンシルを設定したら、ここを適当な色又は模様で塗りつぶさなければならない。これを行うための方法には、多角形の全ての頂点の２Ｄ境界矩形を計算し、その後（ステンシルテストを使用して）単一の矩形のみを描画する方法、又は作成された三角形を単純に再送する方法がある。図１（ａ）に適用して図１５（ａ）に示す前者は、ハードウェアにほぼ最少量の幾何学データしか送信しないという利点を有するが、最小境界と最大境界を事前計算する必要がある。この方法はまた、領域４１５によって示すように、塗りつぶすべき多角形に矩形が密に接しない場合には、無駄な画素処理という面でコストがかかる恐れもある。
【００１５】
図１５（ｂ）に示す別の方法（この例では本発明の方法（図７を参照）を使用して作成された三角形の組を使用する）は、境界ボックス法よりも多くの幾何学形状を送信するが、一般に画素塗りつぶしの重複が少なくなる。この例では、形状の大半が単一の画素の「層／パス」４５０で塗りつぶされるが、画素が複数回塗りつぶされる領域４６０も存在する。通常、凹部の数又は総凹領域が多い多角形では、この重複が多くなる。
【００１６】
この方法は、自己交差多角形及び複数輪郭線多角形でも変わらずに機能し、Ｓｈｒｅｉｎｅｒ他は、複数輪郭線多角形の例も示している。実際には、彼らは、全ての輪郭線の全ての頂点を連結し、この結果を大きな三角形の扇として処理しているだけである。
【００１７】
この扇法は、当業で示されるように単純明快であるにも関わらず、本発明者は、この方法に２つの根本的な問題があることを察した。１つめは、作成される三角形の形状に関するものである。元の多角形から三角形の扇を作成すると、細く長い三角形が作成される傾向にある。このような三角形は、画面領域は等しいが「より等辺的」な形状の別の三角形よりもグラフィックスハードウェアでのレンダリングに時間がかかる。「シルエットクリッピング（Ｓｉｌｈｏｕｅｔｔｅ ｃｌｉｐｐｉｎｇ）」（Ｓａｎｄｅｒ他、ＳＩＧＧＲＡＰＨ２０００、３２７〜３３４ページ）という１つの出版物にこの問題が記載され、部分的解決策が示されている。Ｓａｎｄｅｒ他によれば、輪郭の縁の組を塗りつぶすことも必要となる。実際にはこれらは多角形であり、凹部を有する可能性が高い。彼らは以下のように述べている。
「これまでに説明されている基本アルゴリズムは、多くの長く細い三角形を描画する傾向にある。（ＮＶＩＤＩＡ社のＴＮＴ２などの）多くのラスタ化チップ上では、このような偏心した三角形をレンダリングすることに大きな不利点がある。ｓｅｔＳｔｅｎｃｉｌアルゴリズムが、ｑの画面−空間投影が輪郭線の頂点の中央にｙ座標を有する場合に最適に挙動することは容易に示される。ｑを輪郭線の頂点の３Ｄ重心として選択すると、高速近似として機能する。」
さらに以下のように続く。
「各縁部の輪郭線は、輪郭線の頂点の３Ｄ重心となるように選択した任意の中心点を中心とする三角形の扇として描画される。」
【００１８】
通常はこれにより確かに三角形の形状は改善されるが、残念ながらデータを２回読み出す必要があるという余分な点が導入される。また、扇内に追加の三角形も作成される。図１（ａ）に適用したこの処理の結果の例を図４に示す。（なお、この図では、「重心」位置であるＶｃｅｎｔｒｏｉｄは近似である。）
【００１９】
Ｓａｎｄｅｒ他は、さらなる改善を提案している。
「扇の三角形の偏心度をさらに下げるために、個々の大きな輪郭線を小さなループの組に分割する。より詳細には、輪郭線上の２つの頂点を選択し、これらの頂点間の２つの反対方向を向く縁部をデータ構造に追加し、このようにして形成した小さなループに対して上述の処理を続ける。」
【００２０】
残念ながら、これは非常に曖昧である。まず、彼らはどのように「２つの頂点を選択する」かについて述べていない。次に、この書類の文脈では、「小さなループに対して上述の処理を続ける」は、各ループの「重心」を計算して各々を扇に変えるという処理を意味するように思える。この処理では２つの子ループしか生成されないので、これは正しいとは思えない。
【００２１】
よりふさわしい解釈は、子「ループ」ごとに頂点の数に関する目標Ｍを有し、この目標数を満たす十分な等しい断片にソース多角形を分割することである。従って、Ｎ個の頂点のソース多角形では、
とするＰ個の子多角形が必要となる。彼らの方法では、このようにソース多角形をＰ個の区分に分割した場合、（各々がそれぞれの「ループ」の重心に位置する）Ｐ個の追加の頂点が導入される。なお、個々の子ループは扇で描画されるので、過度に小さなＭの値を選択しない現実的な理由が存在し、これについては次の段落で説明する。
【００２２】
現代のレンダリングハードウェアにいくつかのモデルを提供したときに、これらのレンダリングハードウェアが三角形データ及びバス帯域幅を削減できるようになる方法も本発明に関連する。最も単純な方法は、各三角形を３つのＶバイトの頂点として提供して、Ｔ個の三角形を有するモデルの場合にハードウェアに３*Ｔ*Ｖバイトのデータが伝達されるようにすることであるが、より効率的な選択肢が存在する。通常、３Ｄハードウェアが三角形の扇の概念をサポートすることにより、Ｔ個の三角形の扇は（Ｔ＋２）*Ｖバイトのデータを提供すればよいことは既に知られている。３Ｄモデルでは、通常は三角形ストリップと呼ばれる関連概念（ここでもＳｈｒｅｉｎｅｒ又はｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｔｒｉａｎｇｌｅ ｓｔｒｉｐを参照）がより有用である。三角形の扇と同様に、三角形ストリップも、Ｔ個の三角形のストリップでは（Ｔ＋２）*Ｖバイトのデータしか必要としない。両方の場合、ストリップ又は扇の長さが増えるにつれ、頂点数に対する三角形の比率は、漸近的に１：１に向かって伸びる。従って、長いストリップ及び扇の方が効率的である。
【００２３】
過去１０年にわたり、帯域幅及びストレージコストをさらに減少させる手段としてインデックス付き三角形フォーマットが高い人気を得てきた。この場合、個々の三角形が、頂点アレイから頂点を選択する、例えば各々が１６又は３２ビットの３つの整数インデックスとして定義される。３Ｄモデルでは、このフォーマットは、ストリップ及び扇の１：１の障壁を超える機会を提供するが、２Ｄ形状ではこの可能性は低い。このようなフォーマットを効率的にサポートするために、今ではグラフィックスハードウェアが、Ｈｏｐｐｅによって説明されている（「透明な頂点キャッシングのためのメッシュ局所性の最適化（Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｍｅｓｈ ｌｏｃａｌｉｔｙ ｆｏｒ ｔｒａｎｓｐａｒｅｎｔ ｖｅｒｔｅｘ ｃａｃｈｉｎｇ）」、Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ（ＳＩＧＧＲＡＰＨ’９９議事録）、２６９〜２７６ページ）ような頂点キャッシング技術を頻繁に使用する。簡単に言えば、ハードウェアが、過去の三角形で使用した最後のＫ個の頂点のキャッシュを保持する。より単純であるだけでなく、何より一般に３Ｄモデルのキャッシュヒット率が高くなるという理由で、例えば最長未使用時間（ＬＲＵ）方式ではなく、一般にＦＩＦＯ置換ポリシーが使用される。
【００２４】
ここで第２の、恐らくはるかに重要な、従来技術の扇アルゴリズムが過度の「画素塗りつぶし」を必要とし得るという問題に戻る。例えば、図３から、「真の三角形分割」法により生み出される図２の理想的な状況と比較して、複数の三角形に覆われた比較的大きな領域が存在することが分かる。複数の三角形に覆われた領域を「過剰描画」と呼ぶ。この過剰描画は、レンダリング段階では望ましくない負荷であり、できれば減少させることが有利である。
【００２５】
概して、それほど明確でない三角形ストリップの順序を単純に使用して、すなわちｖ1，ｖ2，ｖN，ｖ3，ｖN-1，ｖ4．．．の順序で頂点を出力して三角形｛［ｖ1，ｖ2，ｖN］、［ｖ2，ｖN，ｖ3］、［ｖN，ｖ3，ｖN-1］…｝を作成すると、多くの場合、扇の順序と比較して三角形の形状がより良好になるとともに過剰描画が減少する（皮肉にも特定の事例である図１（ａ）ではそうならないが）が、残念ながらそれ程大きな改善ではない。図４から、Ｓａｎｄｅｒ他の方法も、追加の頂点及び三角形の導入を犠牲にして過剰描画を減少させるように思われるが、これが全ての場合に機能するわけではないことは確かである。彼らの方法を、「Ｕ」の中心に重心が位置するであろう図１（ｅ）に適用すると、図５に示すように大きな過剰描画領域が生じる。
【００２６】
本発明者は、ステンシルバッファ法によるレンダリングのための、任意多角形からより単純な多角形（常にとは限らないが、通常は三角形）の組を作成する方法が必要とされていることを理解しており、この方法は以下の特徴を有する。
・多角形データの事前処理を避ける（事前処理にコストがかかる場合には、真の三角形分割アルゴリズムを使用した方がよい）。
・追加頂点を導入しない。
・平均して、扇（又はストリップ）法よりも過剰描画率が低い。
・平均して、扇／ストリップ法よりも三角形の形状が「より等辺的」になる。
・ソフトウェア及びハードウェアの両方において簡単に実施でき、使用する演算が比較的少ない。当然ながら、この方法はＯ（ｎ）でなければならない。
【先行技術文献】
【非特許文献】
【００２７】
【非特許文献１】Ｌａｍｏｔ及びＺａｌｉｋ著、「単純多角形のための三角形分割アルゴリズムの概要（Ａｎ ｏｖｅｒｖｉｅｗ ｏｆ ｔｒｉａｎｇｕｌａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｓｉｍｐｌｅ ｐｏｌｙｇｏｎｓ）」（Ｉｎｆｏｒｍａｔｉｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ、１９９９年、１５３〜１５８ページ）
【非特許文献２】Ｈｅｌｄ著、（「多角形の高速強力三角形分割（ＦＩＳＴ：Ｆａｓｔ Ｉｎｄｕｓｔｒｉａｌ−Ｓｔｒｅｎｇｔｈ Ｔｒｉａｎｇｕｌａｔｉｏｎ ｏｆ Ｐｏｌｙｇｏｎｓ）」、Ａｌｇｏｒｉｔｈｍｉｃａ第３０巻、第４号、５６３〜５９６ページ
【非特許文献３】Ｓｈｒｅｉｎｅｒ他著、「ＯｐｅｎＧＬプログラミングガイド：ＯｐｅｎＧＬバージョン１．４公式習得ガイド（ＯｐｅｎＧＬ ｐｒｏｇｒａｍｍｉｎｇ ｇｕｉｄｅ： ｔｈｅ ｏｆｆｉｃｉａｌ ｇｕｉｄｅ ｔｏ ｌｅａｒｎｉｎｇ ＯｐｅｎＧＬ， ｖｅｒｓｉｏｎ １．４）」、ＩＳＢＮ０３２１１７３４８１
【非特許文献４】Ｓｈｒｅｉｎｅｒ他、第１３章、「ステンシルバッファを使用した塗りつぶし凹多角形の描画（Ｄｒａｗｉｎｇ Ｆｉｌｌｅｄ， Ｃｏｎｃａｖｅ Ｐｏｌｙｇｏｎｓ Ｕｓｉｎｇ ｔｈｅ Ｓｔｅｎｃｉｌ Ｂｕｆｆｅｒ）」、［ｏｎｌｉｎｅ］、インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｆｌｙ．ｃｃ．ｆｅｒ．ｈｒ／〜ｕｎｒｅａｌ／ｔｈｅｒｅｄｂｏｏｋ／ｃｈａｐｔｅｒ１３．ｈｔｍｌ又はｈｔｔｐ：／／ｗｗｗ．ｓｃｒｉｂｄ．ｃｏｍ／ｄｏｃ／７６０５３９５／Ｒｅｄｂｏｏｋ＞
【非特許文献５】Ｓｈｒｅｉｎｅｒ他、第２章、［ｏｎｌｉｎｅ］、又はインターネット＜ＵＲＬ：ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｔｒｉａｎｇｌｅ ｆａｎ＞
【非特許文献６】Ｓａｎｄｅｒ他著「シルエットクリッピング（Ｓｉｌｈｏｕｅｔｔｅ ｃｌｉｐｐｉｎｇ）」、ＳＩＧＧＲＡＰＨ２０００、３２７〜３３４ページ
【非特許文献７】インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｔｒｉａｎｇｌｅ ｓｔｒｉｐ＞
【非特許文献８】Ｈｏｐｐｅ著、「透明な頂点キャッシングのためのメッシュ局所性の最適化（Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｍｅｓｈ ｌｏｃａｌｉｔｙ ｆｏｒ ｔｒａｎｓｐａｒｅｎｔ ｖｅｒｔｅｘ ｃａｃｈｉｎｇ）」、Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ（ＳＩＧＧＲＡＰＨ’９９議事録）、２６９〜２７６ページ
【発明の概要】
【発明が解決しようとする課題】
【００２８】
本発明の目的は、上記の目標を達成する何らかの助けになる方法及びシステムを提供することである。
【００２９】
また、あらゆる方法及びシステムにおいて、必ずしも必須ではないが以下の特徴が望ましい。
・扇／ストリップ法とほぼ同等の幾何学形状データ転送コスト。
・好ましくは、三角形などの提供されるプリミティブを、「時系列的に近い」プリミティブが画面空間内でも近くに存在することにより、（フレームバッファキャッシングなどの）キャッシングをより効果的にすることができるような順序で配列すべきである。
・方法は、扇法よりも実質的に複雑であってはならない。
【課題を解決するための手段】
【００３０】
本発明は、ここで参照すべき添付の特許請求の範囲において定義される。従属請求項では、有利な特徴を定義する。
【００３１】
公知の方法で特定される問題点に対処するために、本発明者は以下のことを理解した。
・通常、多角形上の頂点は凹角よりもむしろ凸角を多く形成する。
・レンダリングハードウェアにおいてインデックス付き三角形をサポートすることにより、別の三角形順序を効率的にサポートすることができる。
・数値的に局所的な指標を有する頂点は、空間的にも局所的な傾向にある。通常、この傾向は、図６ａ、図６ｂ、及び図６ｃに示すような頂点の数が多い多角形でより顕著である。
・グラフィックスレンダリングハードウェアは、多角形が時計回りであるか、又は反時計回りであるかの特定をほぼ必ず「無償」でサポートし、このグラフィックスレンダリングハードウェアに、特定の屈曲順序を有する多角形を除外するように指示することができる。
【００３２】
真の三角形分割のための「イヤークリッピングアルゴリズム」（例えば、Ｍｅｉｓｔｅｒ又はＨｅｌｄ）では、「安全な」頂点を識別し、その後この頂点を除去して、Ｎ個の辺形状をＮ−１個の形状に切り詰める。この結果、切り取られた頂点が、その元の２つの隣接する頂点とともに三角形を形成する。残念ながら、「安全な」頂点、すなわち作成される三角形が元の多角形の完全に内部に存在するようになる頂点の識別にはコストがかかる。
【００３３】
本発明者は、画像空間法を用いステンシルバッファを使用してレンダリングする場合には、選択した頂点が「安全」であるかどうかは全く重要ではないことを理解した。図３を例をとると、実際には、扇法は、多角形が三角形｛Ｖ1，Ｖ6，Ｖ7｝に切り詰められるまで、頂点Ｖ2，Ｖ3，．．．Ｖ5により形成される耳を次第に切り取ることであると考えることができる。
【００３４】
本発明者は、三角形プリミティブでは、Ｎ個の辺の多角形の元の（単一の）輪郭線の１つ置きの頂点に単純なイヤークリッピングアルゴリズムを適用した場合、通常、このようにして形成される。
個の三角形は、扇法又はストリップ法によって作成される三角形よりも等辺的な形状になることを認識した。さらに、これらの三角形の最終的に塗りつぶされる形状の外部に位置する領域、又は他の三角形と重なり合う領域のいずれかが、通常扇法又はストリップ法により生成される領域よりも大きくなる可能性は低い。この処理後には、
（すなわち、上限（Ｎ／２））個の頂点を有する「残りの」多角形が残る。その後、同じ処理を再び適用して、頂点数がさらに少ない別の三角形の組及び別の残りの多角形を作成することができる。このようにして、残りの多角形が「空」になるまで、すなわち残りの多角形が出力するのに望ましいサイズのプリミティブになるまで、又は残りの多角形の面積が自明にゼロになるまでこの処理を繰り返す。このような処理を図１（ａ）に適用した結果を図７に示す。この例では、過剰描画が少なくなるという望ましい結果が得られた。
【００３５】
前段落では、レンダリングシステムが三角形プリミティブをサポートすることを前提とした。レンダリングシステムによっては、（凸状又は任意のいずれの）四角形、さらには例えばＭ≦１６とするＭ個の辺の「任意」多角形のレンダリングをサポートするものもある。以下で詳述する好ましい実施形態は、本発明を三角形プリミティブに関して実証するものであるが、本発明は、三角形プリミティブの出力に限定されるものではなく、より柔軟なレンダリングシステムで使用した場合には、Ｍ個の辺のプリミティブユニット、又は三角形と四角形などの複数の種類のプリミティブユニットを出力することができる。現時点で好ましい実施形態では、三角形などの１つの種類のプリミティブを出力して輪郭線の大部分を補う。
【００３６】
また、ステンシルを設定した時点で生じる色又は模様の塗りつぶし処理をできるだけ適度に効率化することも非常に望ましい。この目的のために、本発明者は、自己交差のない単一輪郭線の任意多角形が全体的屈曲順序を有し、さらにこの屈曲順序が、通常アプリケーションにより描画される全てのオブジェクトで一貫していることが有益であることも認識した。（これは、例えば、ＯｐｅｎＧＬ規格、ＤｉｒｅｃｔＸ規格、又はＯｐｅｎＶＧ規格によって要約される、隣接するオブジェクト間に見られる「隙間」などのアーチファクトを回避するための、グラフィックスハードウェアの「三角形塗りつぶし」又は「タイブレーキングルール」に起因する。）実際のシステムでは、複数輪郭線の任意多角形も、このように一貫した全体的屈曲順序を他の断片に使用する。（一貫したものであることにより、「穴」を表す輪郭線の屈曲順序は逆になり、各輪郭線自体は自己交差しない。）
【００３７】
本発明者は、ステンシルバッファを設定したら、全体的屈曲順序Ｗを有するこのような任意多角形では、オブジェクトを塗りつぶす際に、ステンシルを作成するために使用したやはり屈曲順序Ｗの三角形しか必要でなくなることに注目した。描画される画素は、奇数−偶数ルールにより生成されるものの上位集合であるため、非ゼロ塗りつぶしルールの挙動を考慮することにより、このことを立証することができる。
【００３８】
全体的屈曲順序Ｗが画素のステンシル値の増分に対応すると仮定すると、正の値のステンシルを有する画素を塗りつぶすだけでよい。逆の屈曲順序の三角形は、ステンシルの値から減算を行うだけであり、一貫した屈曲順序を仮定しているので、これらを排除することができる。通常、レンダリングパイプラインは、ユーザ選択可能な屈曲順序の多角形の排除を無料でサポートするので、元の三角形分割を再使用することができる。（なお、自己交差する「蝶ネクタイ形」などの多角形、すなわち「［０，０］，［１，０］，［０，１］，［１，１］」は、全体的屈曲順序を有していないため、この追加の最適化を使用することができない。）
【００３９】
図７に示すような図１（ａ）の三角形分割に適用したこの処理を図１６に示しており、これを図１５（ｂ）に示す結果と比較することができる。三角形５２０を塗りつぶし処理から排除でき、この場合、単一の塗りつぶし層５１０の領域のみが残されることが分かる。依然として重複した塗りつぶしが若干存在するが、４６０と比較すると大幅に減少している。
【００４０】
ここで、添付図面を参照しながら本発明の例示的な実施形態について詳細に説明する。
【図面の簡単な説明】
【００４１】
【図１ａ】「任意」多角形の例を示す図である。
【図１ｂ】「任意」多角形の例を示す図である。
【図１ｃ】「任意」多角形の例を示す図である。
【図１ｄ】「任意」多角形の例を示す図である。
【図１ｅ】「任意」多角形の例を示す図である。
【図２】図１ａの多角形に「真の三角形分割」を適用した考えられる結果を示す図である。
【図３】最も良く知られている従来技術のレンダリング処理をステンシルバッファと併せて図１ａの多角形に適用することにより生成される三角形を示す図である。
【図４】Ｓａｎｄｅｒ他の方法を使用して図１ａの多角形に適用した場合に生成される追加の点及び三角形を示す図である。
【図５】Ｓａｎｄｅｒ他の方法を図１ｅの多角形に適用した図である。
【図６ａ】より多くの頂点を有する「任意」多角形の例を示す図である。
【図６ｂ】より多くの頂点を有する「任意」多角形の例を示す図である。
【図６ｃ】より多くの頂点を有する「任意」多角形の例を示す図である。
【図６ｄ】より多くの頂点を有する「任意」多角形の例を示す図である。
【図６ｅ】より多くの頂点を有する「任意」多角形の例を示す図である。
【図７】本発明の１つの実施形態を図１ａの多角形に適用することにより生成される三角形を示す図である。
【図８】多輪郭線の任意多角形をその輪郭線に論理的に分割する本発明の実施形態の処理の最初のステップを示す図である。
【図９ａ】本発明の実施形態を図６ａの多角形に適用することにより生成される、ある階層的「サイズ」の三角形に対応する三角形のサブセットを示す図である。
【図９ｂ】本発明の実施形態を図６ａの多角形に適用することにより生成される、ある階層的「サイズ」の三角形に対応する三角形のサブセットを示す図である。
【図９ｃ】本発明の実施形態を図６ａの多角形に適用することにより生成される、ある階層的「サイズ」の三角形に対応する三角形のサブセットを示す図である。
【図９ｄ】本発明の実施形態を図６ａの多角形に適用することにより生成される、ある階層的「サイズ」の三角形に対応する三角形のサブセットを示す図である。
【図９ｅ】本発明の実施形態を図６ａの多角形に適用することにより生成される、ある階層的「サイズ」の三角形に対応する三角形のサブセットを示す図である。
【図９ｆ】本発明の実施形態を図６ａの多角形に適用することにより生成される、ある階層的「サイズ」の三角形に対応する三角形のサブセットを示す図である。
【図１０】図６ａの多角形に適用した修正した扇法の出力のサブセット（１０個目ごとの三角形）を示す図である。
【図１１ａ】本発明の実施形態を図６ａの多角形に適用することにより生成される三角形に生じる過剰描画の領域を示す図である。
【図１１ｂ】修正した扇アルゴリズムによって生じる過剰描画の領域を示す図である。
【図１２】本発明の装置の例示的な実施形態の概要を示す図である。
【図１３ａ】本発明の実施形態にとって異常な多角形の事例を示す図である。
【図１３ｂ】本発明の実施形態にとって異常な多角形の事例を示す図である。
【図１４ａ】図１３ａ及び図１３ｂの事例の異常でない別の構成を示す図である。
【図１４ｂ】図１３ａ及び図１３ｂの事例の異常でない別の構成を示す図である。
【図１５（ａ）】多角形の先端から求めた矩形の境界ボックスを使用して、ステンシルバッファ値を決定した後に多角形の画素を塗りつぶす方法を示す図である。
【図１５（ｂ）】ステンシルを作成するために使用した三角形分割を再送して、ステンシルバッファ値を決定した後に多角形の画素を塗りつぶす方法を示す図である。
【図１６】頂点の屈曲順序が一貫した多角形ステンシルバッファを決定した後に、ステンシルを作成するために生成された三角形分割を使用するが、頂点の屈曲順序が逆の三角形を排除した多角形の画素を塗りつぶした結果を示す図である。
【発明を実施するための形態】
【００４２】
第１の好ましい実施形態は、基本的に前述したものであり、以下のステップによって表される。
１．まず任意多角形を、その成分である閉輪郭線又は部分経路に論理的に分離する。図８は、この単純な処理を図１（ｄ）の多角形の例に適用したものを示している。明らかに、図１の（ａ）、（ｂ）、及び（ｅ）のような単一輪郭線の多角形では、このステップを無視することができる。
なお、このステップは、輪郭線を全て連結し、単一の扇として処理するＳｈｒｅｉｎｅｒ他の方法とは異なる。Ｓｈｒｅｉｎｅｒ他の方法は、単純ではあるものの、通常は大幅な過剰描画を招く。
２．以下で説明する方法を使用して、輪郭線をプリミティブ、この場合は三角形の組に変換し、結果として得られるプリミティブ、例えば三角形を、いずれかの先行する多角形の輪郭によって生成された組と連結する。
３．ステンシルバッファを使用して、この組み合わせたプリミティブ、例えば三角形の組をレンダリングする。
【００４３】
Ｎ0≧３とする輪郭線
のプリミティブの組への変換は、Ｐ−２個（まで）の頂点の第１の組を輪郭線から繰り返し除去することにより、閉多角形輪郭を、Ｐ≧３とする最大サイズがＰのより小さな多角形ユニットに分割して、Ｐ個の頂点
を有する多角形及びＮ0−（Ｐ−２）個の頂点を有する切り詰めたソース輪郭線を生成するステップと、（可能であれば）前回の組の最後の頂点から開始してＰ−２個（まで）の頂点の第２の組を除去するステップと、これらのステップをソース輪郭線の終端まで続けるステップとで構成される。より詳細には、この変換により最初の小さな多角形の組
及び残りの輪郭線
が生成され、この残りの輪郭線は、表現の都合上、
とする
として番号を付け直すことができる。
【００４４】
この処理を、個々の後続して切り詰められる輪郭線Ｃjに対し、頂点がＰ個又はそれよりも少なくなるか、又は線分（従って自明のゼロ面積）に切り詰められるかのいずれかまで繰り返す。その後、ステンシルバッファを使用して、生成されたプリミティブをレンダリングし、コンピュータ生成画像を作成する。
【００４５】
次に、本発明の第１の実施形態による、例えばステップ２を単一の輪郭線に適用して三角形（すなわちＰ＝３）を生成する処理について説明する。輪郭線が、Ｎ個の辺、及びＢａｓｅ〜Ｂａｓｅ＋Ｎ−１の番号を付けた頂点を有すると仮定する。
StepSize := 1;
WHILE( StepSize < N )
{
// generate all the triangles with this step size
J := 0;
WHILE (J < (N - StepSize))
{
// Get the other two points that will make
// up this triangle
PtB := MIN(J+ StepSize, N-1);
PtC := MIN(J + 2*StepSize, N-1);
//if this is a non degenerate triangle...
IF(PtB != PtC)
{
//output triangle {J, PtB, PtC} relative
//to “base”
OutputTriangle(J + Base,
PtB + Base,
PtC + Base);
}
// Move to the next triangle in this set
J := J + 2*StepSize;
}
// Double the step size
StepSize := StepSize * 2;
}
【００４６】
当業者であれば、ＶＨＤＬ又はＶｅｒｉｌｏｇなどの言語を使用してこの単純なアルゴリズムをハードウェア内で実現することができ、加算器、レジスタ、及び比較器を含むわずかな構成要素しか必要でないことを理解すべきである。
【００４７】
図６に、より多くの頂点を有する任意多角形の５つの例を示す。図６ａのオーストラリアの地図は、約１５００個の頂点及び２６個の輪郭線を含む。図６ｂに示す「ヒルベルト曲線」は、１０００個の頂点を含む。図６ｃの「Ｔｈ」というテキストは８０７個の頂点を有し、図６ｄに示すランダムウォーク及び図６ｅに示す星は、両方とも１００個のソース頂点を有する。これらの任意多角形は、いずれも本発明を使用してレンダリングすることができる。例えば、図９に、この方法を図６ａの多角形に適用した際に出力される三角形のいくつかのサブセットを示しており、これらの６つの画像は、ＳｔｅｐＳｉｚｅがそれぞれ１、４、１６、６４、２５６、及び５１２のときに出力した三角形を取り込んでレンダリングした結果を示している。比較のために、図１０に、修正された従来技術の扇アルゴリズムによって生成される１０個目ごとの三角形を示す（この修正は、Ｓｈｒｅｉｎｅｒ他が提案するような低効率での併合ではなく、各輪郭線を別個に処理するものである）。図９と図１０を比較すると、このソースモデルでは、本発明によってこのように生成される三角形の方が、扇アルゴリズムによって生成されるものよりも著しく良好に成形されることが分かる。
【００４８】
さらに重要なことは、本発明によって生じる過剰描画の量である。図１１（Ａ）は、複数の三角形によって覆われた画素を示している。説明を簡単にするために、この図では、２つの三角形によって覆われた領域と、３又はそれ以上の三角形によって覆われた領域とを区別していないが、明らかに後者の方がコストがかかる。にも関わらず、過剰描画領域に接する画素数を、最終的な意図した結果の画素に対して単純に計算した場合、過剰描画の面積は、意図した最終結果の面積の約１５％であることが分かる。
【００４９】
対照的に、図１１（Ｂ）には、修正された扇アルゴリズムを用いた過剰描画領域を示している。この状況では、驚いたことに、過剰描画される画素の面積は最終結果の約３９％となる。なお、無修正のＳｈｒｅｉｎｅｒの扇アルゴリズムではさらに悪化する。
【００５０】
上述したこの本発明の第１の実施形態は、概して２つの最も重要な問題、すなわち三角形形状の改善の問題及び過剰描画の削減の問題に確実に対処する。それほど重要ではないが、第１の実施形態では、Ｎ−２個の三角形を必要とするＮ個の辺の輪郭線をＮ個の頂点だけで伝達できるようになる扇及びストリップの三角形データ効率が達成されない。第１の実施形態の方法の別の潜在的欠点は、最終的なＳｔｅｐＳｉｚｅ値が大きくなる可能性を除き、多くの場合、生成された「時系列的に」局所的な三角形が、単一の共有頂点の近傍においてのみ空間的に局所的となることである。
【００５１】
上述した実施形態によって作成される頂点の順序を調べた場合（さらに頂点が「１」から始まると仮定する場合）、三角形が、｛［ｖ1，ｖ2，ｖ3］，［ｖ3，ｖ4，ｖ5］，［ｖ5，ｖ6，ｖ7］．．．｛ｖ1，Ｖ3，ｖ5｝，［ｖ5，ｖ7，ｖ9］．．．｝の順序で作成されることが分かる。このデータが、Ｋ個の頂点のキャッシュ（通常、ＫはＮよりもかなり小さい）を有するハードウェアにインデックス付きフォーマットで供給されると仮定した場合、隣接する三角形間では、通常１つの頂点しか再使用されないので、３３％程度のキャッシュヒット率しか達成されない。一方、扇又はストリップでは２つの頂点が共有されるので、約６６％が達成される。
【００５２】
次に、これらのさらなる問題に対処する第２の好ましい実施形態を提供する。この第２の実施形態は、非常に小さなスタックという追加の特徴を組み入れる。輪郭線において遭遇するであろう頂点の最大数をＮＭａｘとすると、このスタックは、最大でも［ｌｏｇ2（ＮMax）］＋１（すなわち上限（ｌｏｇ2（Ｎmax））＋１）個のエントリしか必要としない。例えば、所与のシステムにおいて、輪郭線が最大２16個の頂点を有することができる場合、このスタックは、たった１７個のエントリしか有さない。
【００５３】
この実施形態では、プリミティブレベルを交互にして頂点の時間局所性を最大化し、全ての第１のレベルのプリミティブが生成される前に少なくとも１つの第２のレベルのプリミティブを生成する。元の任意閉多角形輪郭線の頂点に対してプリミティブ多角形の頂点を分離する際に、プリミティブ多角形レベルが反映される。第１のレベルのプリミティブは、元の閉多角形輪郭線内の連続する頂点である頂点を有する。上位レベルのプリミティブは、元の閉多角形輪郭線内で互いにオフセットされた頂点を有する。オフセット量は、プリミティブレベル及びプリミティブ内の頂点数に関連する。連続するｉ番目のレベルのプリミティブの端点では、（ｉ＋１）番目のレベル（ｉ≧１）のプリミティブが形成される。ｉ番目のレベルのプリミティブの組及び関連する頂点を考慮すると、各頂点は、端点という特別な場合を除き、この組の正確に１つの要素に属し、端点は、最大でも１つの他のｉ番目のレベルのプリミティブと共有される。
【００５４】
輪郭線が、全てのプリミティブレベルにわたる単一サイズのプリミティブに分割される場合、プリミティブレベルをｉ、及び多角形プリミティブサイズをＱとすると、ｉ番目のレベルのプリミティブにおける頂点は、元の任意閉多角形輪郭線内で互いに（Ｑ−１）＾（ｉ−１）だけオフセットされた頂点に対応する。例えば、三角形プリミティブのみを使用して輪郭線を分割する場合、第１のレベルのプリミティブが頂点［ｖ１，ｖ２，ｖ３］、［ｖ３，ｖ４，ｖ５］．．．を有すると仮定すると、第２のレベルのプリミティブは、元の閉多角形輪郭線の頂点に対するオフセットが（３−１）＾（２−１）＝２の頂点［ｖ１，ｖ３，ｖ５］，［ｖ５，ｖ７，ｖ９］．．．を有することになり、第３のレベルのプリミティブは、元の閉多角形輪郭線の頂点に対するオフセット４の頂点［ｖ１，ｖ５，ｖ９］，［ｖ９，ｖ１３，ｖ１７］．．．を有することになり、以下同様である。
【００５５】
第２の実施形態は、第１の変形と同じステップ１及び３を使用するが、ステップ２、すなわち単一の輪郭線の三角形分割を、以下の擬似コードで表す方法に置き換える。前回と同様に、輪郭線は頂点番号「ｂａｓｅ」から開始し、Ｎ個の頂点を有すると仮定する。
int Vstack[MAX_VERTEX_STACK_SIZE]; //vertex stack
int StackDepth;
int CurrentVertexID;
// put the first vertex, 0, on the stack.
StackDepth := 1;
Vstack[0] := 0;
CurrentVertexID := 1; //next vertex to process*/
// while we have at least 2 more vertices
WHILE(CurrentVertexID <= N-2)
{
// put the next two vertices on the stack
Vstack[StackDepth] := CurrentVertexID;
Vstack[StackDepth+1] := CurrentVertexID+1;
CurrentVertexID+=2;
StackDepth +=2;
// form a triangle from the top 3 vertices
OutputTriangle(Vstack[StackDepth-3] + Base,
Vstack[StackDepth-2] + Base,
Vstack[StackDepth-1] + Base);
// remove the ‘second from top’ stack element
Vstack[StackDepth-2] := Vstack[StackDepth-1];
StackDepth--;
// do all the higher triangle levels we can..
WHILE((StackDepth >= 3) &&
((Vstack[StackDepth-1] - Vstack[StackDepth-2]) ==
(Vstack[StackDepth-2] - Vstack[StackDepth-3])) )
{
// form a triangle from the top 3 vertices
OutputTriangle(Vstack[StackDepth-3] + Base,
Vstack[StackDepth-2] + Base,
Vstack[StackDepth-1] + Base);
// remove the second from top stack element
Vstack[StackDepth-2] := Vstack[StackDepth-1];
StackDepth--;
}//end while doing upper levels
}//end while at least 2 vertices left
// process remaining whole triangles on the stack
WHILE(StackDepth >= 3)
{
// form a triangle from the top 3 vertices
OutputTriangle(Vstack[StackDepth-3] + Base,
Vstack[StackDepth-2] + Base,
Vstack[StackDepth-1] + Base);
// remove the second from top stack element
Vstack[StackDepth-2] := Vstack[StackDepth-1];
StackDepth--;
}//end while
// if there is just one vertex left to do,
// add it to the stack and form the final triangle
IF(CurrentVertexID <= N-1)
{
Vstack[StackDepth] := CurrentVertexID;
StackDepth++;
// form a triangle from the top 3 vertices
OutputTriangle(Vstack[StackDepth-3] + Base,
Vstack[StackDepth-2] + Base,
Vstack[StackDepth-1] + Base);
}// end if one leftover vertex
【００５６】
この実施形態では、三角形が、はるかに「頂点キャッシュに適した」順序で作成される。具体的には、作成される三角形は、
｛［ｖ1，ｖ2，ｖ3］，［ｖ3，ｖ4，ｖ5］，［ｖ1，ｖ3，ｖ5］，［ｖ5，ｖ6，ｖ7］，［ｖ7，ｖ8，ｖ9］，［ｖ5，ｖ7，ｖ9］，［ｖ1，ｖ5，ｖ9］，．．．｝となる。
【００５７】
基本的に、第１の実施形態の「ＳｔｅｐＳｉｚｅ」の様々な値に対応する三角形が交互配置される。Ｎが十分に大きいと仮定すると、三角形は、少なくとも最初は以下のパターンのレベルに対応して作成される。
ＳｔｅｐＳｉｚｅ＝［１，１，２，１，１，２，４，１，１，２，１，１，２，４，８，１，．．．］
【００５８】
第２の実施形態によって作成される順序付けを使用して、ＦＩＦＯ置換ポリシーを有する１６個のエントリの頂点キャッシュが存在すると仮定した場合、例えば１２０個の頂点の輪郭線におけるヒット率は評価に値する６２％であり、これは第１の実施形態のほぼ２倍であり、扇又はストリップと同等である。
【００５９】
本発明を実施する装置の例を図１２に示す。入力バッファ２１０に、輪郭線のパラメータが供給される２００。これらのパラメータは状態マシーン２２０によって読み出され、この状態マシーンは、上記の擬似コードで記述したステップを実施する。
【００６０】
状態マシーンは、頂点スタックにアクセスすることができる。頂点スタックは、Ｐ個のスタックエントリを含む第１の部分２３０と、第２の部分２４０という２つの部分に分割されることが好ましい。状態マシーン２２０は、頂点スタック２３０の第１の部分の上位Ｐ個のエントリ（三角形分割の場合にはＰ＝３）に直接アクセスすることができる。これらの３つのエントリへの読み出しアクセス及び書き込みアクセスを並行して行えることが望ましいので、これらの部分は、独立したレジスタとして実現されることが好ましい。頂点スタック２４０の第２の部分は、残りのスタックエントリを保持し、単一の読み出し／書き込みポートしか必要とせず、従ってスタック上で４番目に高い要素のインデックスを有する安価なレジスタファイルで実現することができる。
【００６１】
スタックデータの押し出し及び抜き取りを可能にするために、この場合、上位３つのエントリを含む頂点スタックの第１の部分２３０と、スタック空間の残りの部分である第２の部分２４０との間に読み出し／書き込み経路２５０が存在する。
【００６２】
ユニット２３０は、上記の擬似コードで記述したような中心的要素（Ｐ＝３の場合、輪郭線が処理されるにつれて除外又はクリップされる要素に対応する上位から２番目のスタック要素）を削除又は上書きする能力もサポートする。状態マシーンの誘導の下、スタック演算が行われる。状態マシーンにより、プリミティブ出力ユニット、ここでは三角形出力ユニット２６０に、上位３つのスタック要素２３０を選択して対応する三角形を出力するように指示することができる。
【００６３】
いくつかの説明した三角形生成技術を使用して図６の任意多角形のステンシルを塗りつぶすための「サイクル」数を、レンダリングシミュレータを使用して互いに比較する。また、目標ベンチマークとして、真の三角形分割アルゴリズムの結果の（事前処理コストを含まない）レンダリングサイクルを提供する。解釈を容易にするために、（修正された）扇アルゴリズムがスコア１．０となるようにスコアを正規化する。数字が小さい方が良い。「Ｓａｎｄｅｒ」アルゴリズムは、本発明者がＳａｎｄｅｒ他の文献を解釈したものである。
【００６４】
明らかなように、本発明は、ステンシルを利用する他の方法と比較して一般的に好ましい。
【００６５】
第２の好ましい実施形態を、三角形インデックスを生成し始める前に、特定の輪郭線内に何個の頂点が存在するかを前もって把握する必要がないようにさらに構成することができる。このような実施形態は、「オンザフライ」で生成される頂点をストリーミングする用途において有用となる。また、この実施形態を、やはり頂点座標をより広いスタックに記憶することにより、レンダリングハードウェア内でインデックス付き三角形をサポートする必要がないように修正することもできる。
【００６６】
レンダリングシステムによっては、四角形（凸又は任意のいずれでも）、さらには、例えばＭ≦１６とするＭ個の辺の「任意」多角形のレンダリングをサポートするものもある。提示した好ましい実施形態は、いずれも本発明の範囲から逸脱することなく、三角形以外のプリミティブユニットを出力して、これらをより柔軟なレンダリングシステムに適合させるように容易に構成することができる。
【００６７】
このように提示する発明では、概して、従来技術と比較して過剰描画が減少し、三角形形状が改善され、及び／又は必要なデータが減少するが、異常な状況に遭遇する恐れがある。非常に単純な事例を図１３（Ａ）に示す。この例では、最初の３つの頂点｛ｖ１，ｖ２，ｖ３｝が、図１３（Ｂ）に灰色で示す他の全ての「ＳｔｅｐＳｉｚｅ＝１」の三角形３００がそうであるように、形状内に凹部を形成する。これらの三角形を処理した後、この方法は、なおも大きな五角形領域３１０を効果的に塗りつぶす必要がある。図から分かるように、これらの三角形は全て、かなりの量の過剰描画領域を形成する。
【００６８】
図１３における最初の頂点の場所は「不運」であった。そうではなく、この実施形態が、図１４（Ａ）に示す幾何学的に均等な図を受け取った場合、図１４（Ｂ）の別の「ＳｔｅｐＳｉｚｅ＝１」の三角形が代わりに作成される。これにより、残りの「ＳｔｅｐＳｉｚｅ」の三角形によって覆うべき領域３７０のみが残され、過剰描画は全く生じない。
【００６９】
従って、別の実施形態では、これらの異常な事例の頻度を低減させようと試みる。Ｓｅｉｄｅｌの「真の三角形分割」からの思いつきで、別の実施形態ではランダム化技術を使用する。この実施形態では、輪郭線ごとにランダム又は擬似ランダムなオフセット値を供給又は計算することができる。その後、このオフセットを、Ｎを法として輪郭線内の全ての頂点インデックスに加算して、最悪の事例が再発する可能性を低減させる。
【００７０】
多角形データによっては、頂点自体を任意のインデックスのアレイとして頂点アレイ内に供給できるものもある。当業者には、本明細書に示す実施形態を、このような間接的方法をサポートするように拡張できることが明らかであろう。
【００７１】
Ａｄｏｂｅフラッシュフォーマットでは、任意多角形の縁部が、明らかにランダムな分断された順序で供給される。当業者であれば、本明細書に記載した発明を適用する前に、ハッシュ処理システムを使用して、これらを連結されたチェーンに並べ替えできることを認識するであろう。
【００７２】
上記の方法で三角形分割を描画することによってステンシルを構成したら、上述したような当業で公知の方法のいずれかにより、すなわち境界ボックスを使用して又は三角形分割を再使用して、これらの三角形に塗りつぶし／陰影付け／模様付けを行うことができる。さらに、親多角形の頂点の屈曲順序が一貫したものである場合、本発明で提示した追加の機能強化を使用することにより、三角形分割をレンダリングシステムに再送できるが、頂点の屈曲順序が逆の三角形を除外するように指示することができる。
【符号の説明】
【００７３】
Ｖ１〜Ｖ７ 頂点
【技術分野】
【０００１】
本発明は、少なくとも１つの閉多角形輪郭線を含むコンピュータ生成画像をレンダリングするための方法及び装置に関する。具体的には、本発明は、画像空間計算及び標準グラフィックスハードウェアを使用した、凹部、自己交差、さらには複数の「輪郭線」の存在をも許容する「任意」形状の多角形を含む画像のレンダリングに関する。
【背景技術】
【０００２】
通常、コンピュータ生成画像内には数多くの個別の多角形が存在する。多くの場合、グラフィックスレンダリングハードウェア、特に３Ｄグラフィックスハードウェアは、三角形プリミティブ、或いは、時にその他の凸多角形、すなわち全ての内角が１８０°よりも小さな多角形をレンダリングする能力しか有していない。このような多角形は、比較的容易にレンダリングされる。このような仕様は、任意多角形のいずれの部分を内部と見なし、いずれの部分を外部と見なすべきかを決定する「塗りつぶしルール」を含む。ＳＶＧは、「偶数−奇数」及び「非ゼロ」という２つのこのようなルールを定義する。本明細書では、説明を簡単にするために、通常は「偶数−奇数」ルールの使用を前提とするが、当業者には、提示する技術がその他の明確な塗りつぶしルールにも当てはまることが明らかであろう。
【０００３】
図１ａに、（凹多角形、自己交差を含む多角形、及び複数輪郭線で構成された多角形を含む）「任意」多角形のいくつかの例を示す。図１ａ及び図１ｅは、それぞれ凹多角形、すなわち内角の少なくとも１つが１８０°よりも大きな多角形の例を示している。図１ｂは、自己交差を含む多角形、すなわち２つの頂点間の各線分の全ての部分が多角形の境界内又は境界上に留まるとは限らない多角形の例を示している。図１ｃは、複数の輪郭線を含む多角形、すなわち、全体的形状を定義するために外部輪郭線と内部輪郭線が必要な穴を含む多角形の例を示している。図１ｄは、全てのこれらの特徴を含む多角形の例を示している。
【０００４】
このような任意多角形をレンダリングする傍ら凸多角形にも対応する能力は、例えばＳＶＧ（スケーラブルベクトルグラフィックス）及びＯｐｅｎＶＧ（オープンベクトルグラフィックス）などのベクトルグラフィックス規格をサポートするためなどの多くの理由により有用である。ＳＶＧは、２次元グラフィックス及びグラフィックアプリケーションをＸＭＬ（拡張マークアップ言語）で記述するための言語である。ＯｐｅｎＶＧは、ハードウェア加速型２次元ベクトルグラフィックス向けに設計された、著作権使用料が無料のアプリケーションプログラミングインターフェイス（ＡＰＩ）である。当然ながら、任意多角形をレンダリングできる方法は、いずれも凸多角形を処理できなければならない。
【０００５】
このようなハードウェア上で任意多角形をレンダリングできる方法には２つの系列がある。第１の系列は、モデル空間内で計算を行うものであり、一般に三角形分割アルゴリズムと呼ばれる。これらのアルゴリズムは、多角形の外形を取得して、元の多角形の塗りつぶし領域を正確に補う重なり合わない三角形の組を作成する。本明細書では、他の「三角形分割」の使用と混同しないように、このようなアルゴリズムを「真の三角形分割」と呼ぶ。このような処理を図１ａの多角形に適用した考えられる結果の例を図２に示す。このように、原形を三角形｛［ｖ２，ｖ３，ｖ５］、［ｖ３，ｖ４，ｖ５］、［ｖ５，ｖ６，ｖ２］、［ｖ６，ｖ２，ｖ７］、［ｖ７，ｖ２，ｖ１］｝で構築することができる。Ｎ個の辺を有する単純多角形を想定し、これ以上頂点を追加しないと想定すると（アルゴリズムによっては追加の頂点を導入できるものもある）、Ｎ−２個の三角形が得られる。これらの三角形は、一度作成したら、いずれかの市販のグラフィックスハードウェア上で容易にレンダリングすることができる。
【０００６】
「真の三角形分割」処理のためのアルゴリズムは数多く公開されてきた。Ｌａｍｏｔ及びＺａｌｉｋが、「単純多角形のための三角形分割アルゴリズムの概要（Ａｎ ｏｖｅｒｖｉｅｗ ｏｆ ｔｒｉａｎｇｕｌａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｓｉｍｐｌｅ ｐｏｌｙｇｏｎｓ）」（Ｉｎｆｏｒｍａｔｉｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ、１９９９年、１５３〜１５８ページ）において方法の概論を示している。これらの文献の方法は、図１（ａ）及び図１（ｅ）などの単純多角形に限定したものがほとんどであり、すなわちこれらの方法は、（繰り返し頂点を含む）自己交差も、複数の輪郭線も含むことができない。とは言うものの、Ｍｅｉｓｔｅｒの「イヤーカッティング（ｅａｒ ｃｕｔｔｉｎｇ）」（又はイヤークリッピング（ｅａｒ ｃｌｉｐｐｉｎｇ））アルゴリズム、及びＳｅｉｄｅｌの方法は本考察にとって興味深い。
【０００７】
Ｍｅｉｓｔｅｒの方法は、（単純）多角形から頂点を１つずつ除去して、切り詰めた多角形を単純な状態で残すものである。この方法は、３つの連続する頂点により形成される「耳」を多角形から繰り返し「切り取る」ものである。このアルゴリズムはＯ（ｎ3）時間で実行され、後でＯ（ｎ2）に改善されたが、比較的頂点の少ない多角形を除き、特に魅力的なものではない。
【０００８】
一方、Ｓｅｉｄｅｌの方法は、単純多角形ではｌｏｇ*（ｎ）を次式のように定義するＯ（ｎｌｏｇ*ｎ）時間で実行される。
【０００９】
従って、ｎがいずれかの適正値の場合、Ｏ（ｎｌｏｇ*ｎ）を実際にはＯ（ｎ）と見なすことができる。上述したように、任意多角形を処理する「真の三角形分割」アルゴリズムはほとんど公開されていない。Ｈｅｌｄの方法（「多角形の高速強力三角形分割（ＦＩＳＴ：Ｆａｓｔ Ｉｎｄｕｓｔｒｉａｌ−Ｓｔｒｅｎｇｔｈ Ｔｒｉａｎｇｕｌａｔｉｏｎ ｏｆ Ｐｏｌｙｇｏｎｓ）」、Ａｌｇｏｒｉｔｈｍｉｃａ第３０巻、第４号、５６３〜５９６ページ）は、これらの数少ない例外の１つである。イヤークリッピングに基づくものであるが、単純多角形では追加構造を使用してより良好な時間計算量を達成するものの、本発明者には、自己交差などが存在する場合にこの方法がどのような挙動を示すかは明らかでない。
【００１０】
本出願の発明者は、任意多角形を完全にサポートするように強化したバージョンのＳｅｉｄｅｌのアルゴリズムを実践した。このアルゴリズムは、（自己交差によって形成される潜在的頂点が「ｎ」に含まれると仮定して）依然として事実上線形の性能を実現する。しかしながら、〜２ＧＨｚのＣＰＵ上では、この処理は、多角形の頂点当たり依然として平均１〜２μｓを要する。数多くのフレームにわたって複数回描画される多角形では、三角形分割の結果をキャッシュに記憶することができるので、事前処理コストがレンダリング処理により償却される。しかしながら、多角形が数回しか描画されず、又はフレーム単位で劇的に変化して再三角形分割が強いられるような状況では、真の三角形分割処理は極めて不利益となる恐れがある。（なお、モデルに線形変換を適用すると再三角形分割は不要となる。）
【００１１】
任意多角形をレンダリングできる方法の第２の系列は、画像空間計算を使用するものである。この場合、レンダリング／サンプリング処理自体が、いずれの画素が任意多角形の内部に含まれ、いずれが外部に存在するかを判定するように構成される。この方法は、走査線レンダリングアルゴリズムを使用して行うことができるが、本発明者らは主に、任意多角形をより小さな多角形（通常は三角形）に分割し、これらの小さな多角形に関してハードウェアがレンダリングを直接サポートしてこれらをレンダリングし、ハードウェアのステンシルバッファを利用して、レンダリングした画素のいずれが元の任意多角形の内部に存在するかを判定する方法に関心がある。当業では、ステンシルバッファを使用することにより任意多角形を描画できることが周知である（Ｓｈｒｅｉｎｅｒ他著「ＯｐｅｎＧＬプログラミングガイド：ＯｐｅｎＧＬバージョン１．４公式習得ガイド（ＯｐｅｎＧＬ ｐｒｏｇｒａｍｍｉｎｇ ｇｕｉｄｅ： ｔｈｅ ｏｆｆｉｃｉａｌ ｇｕｉｄｅ ｔｏ ｌｅａｒｎｉｎｇ ＯｐｅｎＧＬ， ｖｅｒｓｉｏｎ １．４）」、ＩＳＢＮ０３２１１７３４８１）。例えば、ステンシルにＸＯＲ演算を適用することにより、奇数−偶数ルールを実践することができる。同様に、三角形の屈曲順序を考慮に入れた場合、ステンシルの増分及び減分を使用して非ゼロルールを実践することができる。
【００１２】
いずれの塗りつぶしルールの場合にも、まずソース多角形から三角形の組を作成しなければならない。Ｓｈｒｅｉｎｅｒ他の第１３章、「ステンシルバッファを使用した塗りつぶし凹多角形の描画（Ｄｒａｗｉｎｇ Ｆｉｌｌｅｄ， Ｃｏｎｃａｖｅ Ｐｏｌｙｇｏｎｓ Ｕｓｉｎｇ ｔｈｅ Ｓｔｅｎｃｉｌ Ｂｕｆｆｅｒ）」の節（ｈｔｔｐ：／／ｆｌｙ．ｃｃ．ｆｅｒ．ｈｒ／〜ｕｎｒｅａｌ／ｔｈｅｒｅｄｂｏｏｋ／ｃｈａｐｔｅｒ１３．ｈｔｍｌ又はｈｔｔｐ：／／ｗｗｗ．ｓｃｒｉｂｄ．ｃｏｍ／ｄｏｃ／７６０５３９５／Ｒｅｄｂｏｏｋで閲覧可能）に明白な方法が記載されている。この場合、頂点を単純に［ｖ１，ｖ２，ｖ３，．．．ｖＮ］の順番で提示することにより三角形の扇（Ｓｈｒｅｉｎｅｒ他の第２章、又はｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｔｒｉａｎｇｌｅ ｆａｎを参照）が作成され、これにより頂点を｛［ｖ1，ｖ2，ｖ3］，［ｖ1，ｖ3，ｖ4］，［ｖ1，ｖ4，ｖ5］，．．．［ｖ1，ｖN-1，ｖN］｝とするＮ−２個の三角形の組が暗黙的に作成される。
【００１３】
Ｓｈｒｅｉｎｅｒ他による例（図１（ａ））を借りて、この処理の一部を図３に示す。７本の辺を有する図を、５つの三角形の扇としてレンダリングする。奇数−偶数塗りつぶしルールを仮定すれば、奇数個の三角形で覆われた網目部分の画素は内部と見なされ、偶数個で覆われたものは外部となる。例えば、ｖ１、ｖ３、及び場所２０で境界された領域は、三角形［ｖ1，ｖ2，ｖ3］及び［ｖ1，Ｖ3，ｖ4］によって覆われている。ステンシルバッファがゼロに初期化され、ＸＯＲ演算が使用されると仮定すると、三角形［ｖ1，ｖ2，ｖ3］を描画することで、まず領域［ｖ1，ｖ3，「２０」］の全ての画素のステンシル値が設定されるが、その後これらは三角形［ｖ1，ｖ3，ｖ4］によって再び消去される。この結果、この領域は、多角形に対して外部にあると正しく判断される。この処理の単純さは極めて魅力的であり、この処理は三角形の扇を使用するので、Ｎ個の頂点をグラフィックスハードウェアへ送信すればよい。
【００１４】
いずれの画素が多角形の内部に存在するかを示すようにステンシルを設定したら、ここを適当な色又は模様で塗りつぶさなければならない。これを行うための方法には、多角形の全ての頂点の２Ｄ境界矩形を計算し、その後（ステンシルテストを使用して）単一の矩形のみを描画する方法、又は作成された三角形を単純に再送する方法がある。図１（ａ）に適用して図１５（ａ）に示す前者は、ハードウェアにほぼ最少量の幾何学データしか送信しないという利点を有するが、最小境界と最大境界を事前計算する必要がある。この方法はまた、領域４１５によって示すように、塗りつぶすべき多角形に矩形が密に接しない場合には、無駄な画素処理という面でコストがかかる恐れもある。
【００１５】
図１５（ｂ）に示す別の方法（この例では本発明の方法（図７を参照）を使用して作成された三角形の組を使用する）は、境界ボックス法よりも多くの幾何学形状を送信するが、一般に画素塗りつぶしの重複が少なくなる。この例では、形状の大半が単一の画素の「層／パス」４５０で塗りつぶされるが、画素が複数回塗りつぶされる領域４６０も存在する。通常、凹部の数又は総凹領域が多い多角形では、この重複が多くなる。
【００１６】
この方法は、自己交差多角形及び複数輪郭線多角形でも変わらずに機能し、Ｓｈｒｅｉｎｅｒ他は、複数輪郭線多角形の例も示している。実際には、彼らは、全ての輪郭線の全ての頂点を連結し、この結果を大きな三角形の扇として処理しているだけである。
【００１７】
この扇法は、当業で示されるように単純明快であるにも関わらず、本発明者は、この方法に２つの根本的な問題があることを察した。１つめは、作成される三角形の形状に関するものである。元の多角形から三角形の扇を作成すると、細く長い三角形が作成される傾向にある。このような三角形は、画面領域は等しいが「より等辺的」な形状の別の三角形よりもグラフィックスハードウェアでのレンダリングに時間がかかる。「シルエットクリッピング（Ｓｉｌｈｏｕｅｔｔｅ ｃｌｉｐｐｉｎｇ）」（Ｓａｎｄｅｒ他、ＳＩＧＧＲＡＰＨ２０００、３２７〜３３４ページ）という１つの出版物にこの問題が記載され、部分的解決策が示されている。Ｓａｎｄｅｒ他によれば、輪郭の縁の組を塗りつぶすことも必要となる。実際にはこれらは多角形であり、凹部を有する可能性が高い。彼らは以下のように述べている。
「これまでに説明されている基本アルゴリズムは、多くの長く細い三角形を描画する傾向にある。（ＮＶＩＤＩＡ社のＴＮＴ２などの）多くのラスタ化チップ上では、このような偏心した三角形をレンダリングすることに大きな不利点がある。ｓｅｔＳｔｅｎｃｉｌアルゴリズムが、ｑの画面−空間投影が輪郭線の頂点の中央にｙ座標を有する場合に最適に挙動することは容易に示される。ｑを輪郭線の頂点の３Ｄ重心として選択すると、高速近似として機能する。」
さらに以下のように続く。
「各縁部の輪郭線は、輪郭線の頂点の３Ｄ重心となるように選択した任意の中心点を中心とする三角形の扇として描画される。」
【００１８】
通常はこれにより確かに三角形の形状は改善されるが、残念ながらデータを２回読み出す必要があるという余分な点が導入される。また、扇内に追加の三角形も作成される。図１（ａ）に適用したこの処理の結果の例を図４に示す。（なお、この図では、「重心」位置であるＶｃｅｎｔｒｏｉｄは近似である。）
【００１９】
Ｓａｎｄｅｒ他は、さらなる改善を提案している。
「扇の三角形の偏心度をさらに下げるために、個々の大きな輪郭線を小さなループの組に分割する。より詳細には、輪郭線上の２つの頂点を選択し、これらの頂点間の２つの反対方向を向く縁部をデータ構造に追加し、このようにして形成した小さなループに対して上述の処理を続ける。」
【００２０】
残念ながら、これは非常に曖昧である。まず、彼らはどのように「２つの頂点を選択する」かについて述べていない。次に、この書類の文脈では、「小さなループに対して上述の処理を続ける」は、各ループの「重心」を計算して各々を扇に変えるという処理を意味するように思える。この処理では２つの子ループしか生成されないので、これは正しいとは思えない。
【００２１】
よりふさわしい解釈は、子「ループ」ごとに頂点の数に関する目標Ｍを有し、この目標数を満たす十分な等しい断片にソース多角形を分割することである。従って、Ｎ個の頂点のソース多角形では、
とするＰ個の子多角形が必要となる。彼らの方法では、このようにソース多角形をＰ個の区分に分割した場合、（各々がそれぞれの「ループ」の重心に位置する）Ｐ個の追加の頂点が導入される。なお、個々の子ループは扇で描画されるので、過度に小さなＭの値を選択しない現実的な理由が存在し、これについては次の段落で説明する。
【００２２】
現代のレンダリングハードウェアにいくつかのモデルを提供したときに、これらのレンダリングハードウェアが三角形データ及びバス帯域幅を削減できるようになる方法も本発明に関連する。最も単純な方法は、各三角形を３つのＶバイトの頂点として提供して、Ｔ個の三角形を有するモデルの場合にハードウェアに３*Ｔ*Ｖバイトのデータが伝達されるようにすることであるが、より効率的な選択肢が存在する。通常、３Ｄハードウェアが三角形の扇の概念をサポートすることにより、Ｔ個の三角形の扇は（Ｔ＋２）*Ｖバイトのデータを提供すればよいことは既に知られている。３Ｄモデルでは、通常は三角形ストリップと呼ばれる関連概念（ここでもＳｈｒｅｉｎｅｒ又はｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｔｒｉａｎｇｌｅ ｓｔｒｉｐを参照）がより有用である。三角形の扇と同様に、三角形ストリップも、Ｔ個の三角形のストリップでは（Ｔ＋２）*Ｖバイトのデータしか必要としない。両方の場合、ストリップ又は扇の長さが増えるにつれ、頂点数に対する三角形の比率は、漸近的に１：１に向かって伸びる。従って、長いストリップ及び扇の方が効率的である。
【００２３】
過去１０年にわたり、帯域幅及びストレージコストをさらに減少させる手段としてインデックス付き三角形フォーマットが高い人気を得てきた。この場合、個々の三角形が、頂点アレイから頂点を選択する、例えば各々が１６又は３２ビットの３つの整数インデックスとして定義される。３Ｄモデルでは、このフォーマットは、ストリップ及び扇の１：１の障壁を超える機会を提供するが、２Ｄ形状ではこの可能性は低い。このようなフォーマットを効率的にサポートするために、今ではグラフィックスハードウェアが、Ｈｏｐｐｅによって説明されている（「透明な頂点キャッシングのためのメッシュ局所性の最適化（Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｍｅｓｈ ｌｏｃａｌｉｔｙ ｆｏｒ ｔｒａｎｓｐａｒｅｎｔ ｖｅｒｔｅｘ ｃａｃｈｉｎｇ）」、Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ（ＳＩＧＧＲＡＰＨ’９９議事録）、２６９〜２７６ページ）ような頂点キャッシング技術を頻繁に使用する。簡単に言えば、ハードウェアが、過去の三角形で使用した最後のＫ個の頂点のキャッシュを保持する。より単純であるだけでなく、何より一般に３Ｄモデルのキャッシュヒット率が高くなるという理由で、例えば最長未使用時間（ＬＲＵ）方式ではなく、一般にＦＩＦＯ置換ポリシーが使用される。
【００２４】
ここで第２の、恐らくはるかに重要な、従来技術の扇アルゴリズムが過度の「画素塗りつぶし」を必要とし得るという問題に戻る。例えば、図３から、「真の三角形分割」法により生み出される図２の理想的な状況と比較して、複数の三角形に覆われた比較的大きな領域が存在することが分かる。複数の三角形に覆われた領域を「過剰描画」と呼ぶ。この過剰描画は、レンダリング段階では望ましくない負荷であり、できれば減少させることが有利である。
【００２５】
概して、それほど明確でない三角形ストリップの順序を単純に使用して、すなわちｖ1，ｖ2，ｖN，ｖ3，ｖN-1，ｖ4．．．の順序で頂点を出力して三角形｛［ｖ1，ｖ2，ｖN］、［ｖ2，ｖN，ｖ3］、［ｖN，ｖ3，ｖN-1］…｝を作成すると、多くの場合、扇の順序と比較して三角形の形状がより良好になるとともに過剰描画が減少する（皮肉にも特定の事例である図１（ａ）ではそうならないが）が、残念ながらそれ程大きな改善ではない。図４から、Ｓａｎｄｅｒ他の方法も、追加の頂点及び三角形の導入を犠牲にして過剰描画を減少させるように思われるが、これが全ての場合に機能するわけではないことは確かである。彼らの方法を、「Ｕ」の中心に重心が位置するであろう図１（ｅ）に適用すると、図５に示すように大きな過剰描画領域が生じる。
【００２６】
本発明者は、ステンシルバッファ法によるレンダリングのための、任意多角形からより単純な多角形（常にとは限らないが、通常は三角形）の組を作成する方法が必要とされていることを理解しており、この方法は以下の特徴を有する。
・多角形データの事前処理を避ける（事前処理にコストがかかる場合には、真の三角形分割アルゴリズムを使用した方がよい）。
・追加頂点を導入しない。
・平均して、扇（又はストリップ）法よりも過剰描画率が低い。
・平均して、扇／ストリップ法よりも三角形の形状が「より等辺的」になる。
・ソフトウェア及びハードウェアの両方において簡単に実施でき、使用する演算が比較的少ない。当然ながら、この方法はＯ（ｎ）でなければならない。
【先行技術文献】
【非特許文献】
【００２７】
【非特許文献１】Ｌａｍｏｔ及びＺａｌｉｋ著、「単純多角形のための三角形分割アルゴリズムの概要（Ａｎ ｏｖｅｒｖｉｅｗ ｏｆ ｔｒｉａｎｇｕｌａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｓｉｍｐｌｅ ｐｏｌｙｇｏｎｓ）」（Ｉｎｆｏｒｍａｔｉｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ、１９９９年、１５３〜１５８ページ）
【非特許文献２】Ｈｅｌｄ著、（「多角形の高速強力三角形分割（ＦＩＳＴ：Ｆａｓｔ Ｉｎｄｕｓｔｒｉａｌ−Ｓｔｒｅｎｇｔｈ Ｔｒｉａｎｇｕｌａｔｉｏｎ ｏｆ Ｐｏｌｙｇｏｎｓ）」、Ａｌｇｏｒｉｔｈｍｉｃａ第３０巻、第４号、５６３〜５９６ページ
【非特許文献３】Ｓｈｒｅｉｎｅｒ他著、「ＯｐｅｎＧＬプログラミングガイド：ＯｐｅｎＧＬバージョン１．４公式習得ガイド（ＯｐｅｎＧＬ ｐｒｏｇｒａｍｍｉｎｇ ｇｕｉｄｅ： ｔｈｅ ｏｆｆｉｃｉａｌ ｇｕｉｄｅ ｔｏ ｌｅａｒｎｉｎｇ ＯｐｅｎＧＬ， ｖｅｒｓｉｏｎ １．４）」、ＩＳＢＮ０３２１１７３４８１
【非特許文献４】Ｓｈｒｅｉｎｅｒ他、第１３章、「ステンシルバッファを使用した塗りつぶし凹多角形の描画（Ｄｒａｗｉｎｇ Ｆｉｌｌｅｄ， Ｃｏｎｃａｖｅ Ｐｏｌｙｇｏｎｓ Ｕｓｉｎｇ ｔｈｅ Ｓｔｅｎｃｉｌ Ｂｕｆｆｅｒ）」、［ｏｎｌｉｎｅ］、インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｆｌｙ．ｃｃ．ｆｅｒ．ｈｒ／〜ｕｎｒｅａｌ／ｔｈｅｒｅｄｂｏｏｋ／ｃｈａｐｔｅｒ１３．ｈｔｍｌ又はｈｔｔｐ：／／ｗｗｗ．ｓｃｒｉｂｄ．ｃｏｍ／ｄｏｃ／７６０５３９５／Ｒｅｄｂｏｏｋ＞
【非特許文献５】Ｓｈｒｅｉｎｅｒ他、第２章、［ｏｎｌｉｎｅ］、又はインターネット＜ＵＲＬ：ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｔｒｉａｎｇｌｅ ｆａｎ＞
【非特許文献６】Ｓａｎｄｅｒ他著「シルエットクリッピング（Ｓｉｌｈｏｕｅｔｔｅ ｃｌｉｐｐｉｎｇ）」、ＳＩＧＧＲＡＰＨ２０００、３２７〜３３４ページ
【非特許文献７】インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｔｒｉａｎｇｌｅ ｓｔｒｉｐ＞
【非特許文献８】Ｈｏｐｐｅ著、「透明な頂点キャッシングのためのメッシュ局所性の最適化（Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｍｅｓｈ ｌｏｃａｌｉｔｙ ｆｏｒ ｔｒａｎｓｐａｒｅｎｔ ｖｅｒｔｅｘ ｃａｃｈｉｎｇ）」、Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ（ＳＩＧＧＲＡＰＨ’９９議事録）、２６９〜２７６ページ
【発明の概要】
【発明が解決しようとする課題】
【００２８】
本発明の目的は、上記の目標を達成する何らかの助けになる方法及びシステムを提供することである。
【００２９】
また、あらゆる方法及びシステムにおいて、必ずしも必須ではないが以下の特徴が望ましい。
・扇／ストリップ法とほぼ同等の幾何学形状データ転送コスト。
・好ましくは、三角形などの提供されるプリミティブを、「時系列的に近い」プリミティブが画面空間内でも近くに存在することにより、（フレームバッファキャッシングなどの）キャッシングをより効果的にすることができるような順序で配列すべきである。
・方法は、扇法よりも実質的に複雑であってはならない。
【課題を解決するための手段】
【００３０】
本発明は、ここで参照すべき添付の特許請求の範囲において定義される。従属請求項では、有利な特徴を定義する。
【００３１】
公知の方法で特定される問題点に対処するために、本発明者は以下のことを理解した。
・通常、多角形上の頂点は凹角よりもむしろ凸角を多く形成する。
・レンダリングハードウェアにおいてインデックス付き三角形をサポートすることにより、別の三角形順序を効率的にサポートすることができる。
・数値的に局所的な指標を有する頂点は、空間的にも局所的な傾向にある。通常、この傾向は、図６ａ、図６ｂ、及び図６ｃに示すような頂点の数が多い多角形でより顕著である。
・グラフィックスレンダリングハードウェアは、多角形が時計回りであるか、又は反時計回りであるかの特定をほぼ必ず「無償」でサポートし、このグラフィックスレンダリングハードウェアに、特定の屈曲順序を有する多角形を除外するように指示することができる。
【００３２】
真の三角形分割のための「イヤークリッピングアルゴリズム」（例えば、Ｍｅｉｓｔｅｒ又はＨｅｌｄ）では、「安全な」頂点を識別し、その後この頂点を除去して、Ｎ個の辺形状をＮ−１個の形状に切り詰める。この結果、切り取られた頂点が、その元の２つの隣接する頂点とともに三角形を形成する。残念ながら、「安全な」頂点、すなわち作成される三角形が元の多角形の完全に内部に存在するようになる頂点の識別にはコストがかかる。
【００３３】
本発明者は、画像空間法を用いステンシルバッファを使用してレンダリングする場合には、選択した頂点が「安全」であるかどうかは全く重要ではないことを理解した。図３を例をとると、実際には、扇法は、多角形が三角形｛Ｖ1，Ｖ6，Ｖ7｝に切り詰められるまで、頂点Ｖ2，Ｖ3，．．．Ｖ5により形成される耳を次第に切り取ることであると考えることができる。
【００３４】
本発明者は、三角形プリミティブでは、Ｎ個の辺の多角形の元の（単一の）輪郭線の１つ置きの頂点に単純なイヤークリッピングアルゴリズムを適用した場合、通常、このようにして形成される。
個の三角形は、扇法又はストリップ法によって作成される三角形よりも等辺的な形状になることを認識した。さらに、これらの三角形の最終的に塗りつぶされる形状の外部に位置する領域、又は他の三角形と重なり合う領域のいずれかが、通常扇法又はストリップ法により生成される領域よりも大きくなる可能性は低い。この処理後には、
（すなわち、上限（Ｎ／２））個の頂点を有する「残りの」多角形が残る。その後、同じ処理を再び適用して、頂点数がさらに少ない別の三角形の組及び別の残りの多角形を作成することができる。このようにして、残りの多角形が「空」になるまで、すなわち残りの多角形が出力するのに望ましいサイズのプリミティブになるまで、又は残りの多角形の面積が自明にゼロになるまでこの処理を繰り返す。このような処理を図１（ａ）に適用した結果を図７に示す。この例では、過剰描画が少なくなるという望ましい結果が得られた。
【００３５】
前段落では、レンダリングシステムが三角形プリミティブをサポートすることを前提とした。レンダリングシステムによっては、（凸状又は任意のいずれの）四角形、さらには例えばＭ≦１６とするＭ個の辺の「任意」多角形のレンダリングをサポートするものもある。以下で詳述する好ましい実施形態は、本発明を三角形プリミティブに関して実証するものであるが、本発明は、三角形プリミティブの出力に限定されるものではなく、より柔軟なレンダリングシステムで使用した場合には、Ｍ個の辺のプリミティブユニット、又は三角形と四角形などの複数の種類のプリミティブユニットを出力することができる。現時点で好ましい実施形態では、三角形などの１つの種類のプリミティブを出力して輪郭線の大部分を補う。
【００３６】
また、ステンシルを設定した時点で生じる色又は模様の塗りつぶし処理をできるだけ適度に効率化することも非常に望ましい。この目的のために、本発明者は、自己交差のない単一輪郭線の任意多角形が全体的屈曲順序を有し、さらにこの屈曲順序が、通常アプリケーションにより描画される全てのオブジェクトで一貫していることが有益であることも認識した。（これは、例えば、ＯｐｅｎＧＬ規格、ＤｉｒｅｃｔＸ規格、又はＯｐｅｎＶＧ規格によって要約される、隣接するオブジェクト間に見られる「隙間」などのアーチファクトを回避するための、グラフィックスハードウェアの「三角形塗りつぶし」又は「タイブレーキングルール」に起因する。）実際のシステムでは、複数輪郭線の任意多角形も、このように一貫した全体的屈曲順序を他の断片に使用する。（一貫したものであることにより、「穴」を表す輪郭線の屈曲順序は逆になり、各輪郭線自体は自己交差しない。）
【００３７】
本発明者は、ステンシルバッファを設定したら、全体的屈曲順序Ｗを有するこのような任意多角形では、オブジェクトを塗りつぶす際に、ステンシルを作成するために使用したやはり屈曲順序Ｗの三角形しか必要でなくなることに注目した。描画される画素は、奇数−偶数ルールにより生成されるものの上位集合であるため、非ゼロ塗りつぶしルールの挙動を考慮することにより、このことを立証することができる。
【００３８】
全体的屈曲順序Ｗが画素のステンシル値の増分に対応すると仮定すると、正の値のステンシルを有する画素を塗りつぶすだけでよい。逆の屈曲順序の三角形は、ステンシルの値から減算を行うだけであり、一貫した屈曲順序を仮定しているので、これらを排除することができる。通常、レンダリングパイプラインは、ユーザ選択可能な屈曲順序の多角形の排除を無料でサポートするので、元の三角形分割を再使用することができる。（なお、自己交差する「蝶ネクタイ形」などの多角形、すなわち「［０，０］，［１，０］，［０，１］，［１，１］」は、全体的屈曲順序を有していないため、この追加の最適化を使用することができない。）
【００３９】
図７に示すような図１（ａ）の三角形分割に適用したこの処理を図１６に示しており、これを図１５（ｂ）に示す結果と比較することができる。三角形５２０を塗りつぶし処理から排除でき、この場合、単一の塗りつぶし層５１０の領域のみが残されることが分かる。依然として重複した塗りつぶしが若干存在するが、４６０と比較すると大幅に減少している。
【００４０】
ここで、添付図面を参照しながら本発明の例示的な実施形態について詳細に説明する。
【図面の簡単な説明】
【００４１】
【図１ａ】「任意」多角形の例を示す図である。
【図１ｂ】「任意」多角形の例を示す図である。
【図１ｃ】「任意」多角形の例を示す図である。
【図１ｄ】「任意」多角形の例を示す図である。
【図１ｅ】「任意」多角形の例を示す図である。
【図２】図１ａの多角形に「真の三角形分割」を適用した考えられる結果を示す図である。
【図３】最も良く知られている従来技術のレンダリング処理をステンシルバッファと併せて図１ａの多角形に適用することにより生成される三角形を示す図である。
【図４】Ｓａｎｄｅｒ他の方法を使用して図１ａの多角形に適用した場合に生成される追加の点及び三角形を示す図である。
【図５】Ｓａｎｄｅｒ他の方法を図１ｅの多角形に適用した図である。
【図６ａ】より多くの頂点を有する「任意」多角形の例を示す図である。
【図６ｂ】より多くの頂点を有する「任意」多角形の例を示す図である。
【図６ｃ】より多くの頂点を有する「任意」多角形の例を示す図である。
【図６ｄ】より多くの頂点を有する「任意」多角形の例を示す図である。
【図６ｅ】より多くの頂点を有する「任意」多角形の例を示す図である。
【図７】本発明の１つの実施形態を図１ａの多角形に適用することにより生成される三角形を示す図である。
【図８】多輪郭線の任意多角形をその輪郭線に論理的に分割する本発明の実施形態の処理の最初のステップを示す図である。
【図９ａ】本発明の実施形態を図６ａの多角形に適用することにより生成される、ある階層的「サイズ」の三角形に対応する三角形のサブセットを示す図である。
【図９ｂ】本発明の実施形態を図６ａの多角形に適用することにより生成される、ある階層的「サイズ」の三角形に対応する三角形のサブセットを示す図である。
【図９ｃ】本発明の実施形態を図６ａの多角形に適用することにより生成される、ある階層的「サイズ」の三角形に対応する三角形のサブセットを示す図である。
【図９ｄ】本発明の実施形態を図６ａの多角形に適用することにより生成される、ある階層的「サイズ」の三角形に対応する三角形のサブセットを示す図である。
【図９ｅ】本発明の実施形態を図６ａの多角形に適用することにより生成される、ある階層的「サイズ」の三角形に対応する三角形のサブセットを示す図である。
【図９ｆ】本発明の実施形態を図６ａの多角形に適用することにより生成される、ある階層的「サイズ」の三角形に対応する三角形のサブセットを示す図である。
【図１０】図６ａの多角形に適用した修正した扇法の出力のサブセット（１０個目ごとの三角形）を示す図である。
【図１１ａ】本発明の実施形態を図６ａの多角形に適用することにより生成される三角形に生じる過剰描画の領域を示す図である。
【図１１ｂ】修正した扇アルゴリズムによって生じる過剰描画の領域を示す図である。
【図１２】本発明の装置の例示的な実施形態の概要を示す図である。
【図１３ａ】本発明の実施形態にとって異常な多角形の事例を示す図である。
【図１３ｂ】本発明の実施形態にとって異常な多角形の事例を示す図である。
【図１４ａ】図１３ａ及び図１３ｂの事例の異常でない別の構成を示す図である。
【図１４ｂ】図１３ａ及び図１３ｂの事例の異常でない別の構成を示す図である。
【図１５（ａ）】多角形の先端から求めた矩形の境界ボックスを使用して、ステンシルバッファ値を決定した後に多角形の画素を塗りつぶす方法を示す図である。
【図１５（ｂ）】ステンシルを作成するために使用した三角形分割を再送して、ステンシルバッファ値を決定した後に多角形の画素を塗りつぶす方法を示す図である。
【図１６】頂点の屈曲順序が一貫した多角形ステンシルバッファを決定した後に、ステンシルを作成するために生成された三角形分割を使用するが、頂点の屈曲順序が逆の三角形を排除した多角形の画素を塗りつぶした結果を示す図である。
【発明を実施するための形態】
【００４２】
第１の好ましい実施形態は、基本的に前述したものであり、以下のステップによって表される。
１．まず任意多角形を、その成分である閉輪郭線又は部分経路に論理的に分離する。図８は、この単純な処理を図１（ｄ）の多角形の例に適用したものを示している。明らかに、図１の（ａ）、（ｂ）、及び（ｅ）のような単一輪郭線の多角形では、このステップを無視することができる。
なお、このステップは、輪郭線を全て連結し、単一の扇として処理するＳｈｒｅｉｎｅｒ他の方法とは異なる。Ｓｈｒｅｉｎｅｒ他の方法は、単純ではあるものの、通常は大幅な過剰描画を招く。
２．以下で説明する方法を使用して、輪郭線をプリミティブ、この場合は三角形の組に変換し、結果として得られるプリミティブ、例えば三角形を、いずれかの先行する多角形の輪郭によって生成された組と連結する。
３．ステンシルバッファを使用して、この組み合わせたプリミティブ、例えば三角形の組をレンダリングする。
【００４３】
Ｎ0≧３とする輪郭線
のプリミティブの組への変換は、Ｐ−２個（まで）の頂点の第１の組を輪郭線から繰り返し除去することにより、閉多角形輪郭を、Ｐ≧３とする最大サイズがＰのより小さな多角形ユニットに分割して、Ｐ個の頂点
を有する多角形及びＮ0−（Ｐ−２）個の頂点を有する切り詰めたソース輪郭線を生成するステップと、（可能であれば）前回の組の最後の頂点から開始してＰ−２個（まで）の頂点の第２の組を除去するステップと、これらのステップをソース輪郭線の終端まで続けるステップとで構成される。より詳細には、この変換により最初の小さな多角形の組
及び残りの輪郭線
が生成され、この残りの輪郭線は、表現の都合上、
とする
として番号を付け直すことができる。
【００４４】
この処理を、個々の後続して切り詰められる輪郭線Ｃjに対し、頂点がＰ個又はそれよりも少なくなるか、又は線分（従って自明のゼロ面積）に切り詰められるかのいずれかまで繰り返す。その後、ステンシルバッファを使用して、生成されたプリミティブをレンダリングし、コンピュータ生成画像を作成する。
【００４５】
次に、本発明の第１の実施形態による、例えばステップ２を単一の輪郭線に適用して三角形（すなわちＰ＝３）を生成する処理について説明する。輪郭線が、Ｎ個の辺、及びＢａｓｅ〜Ｂａｓｅ＋Ｎ−１の番号を付けた頂点を有すると仮定する。
StepSize := 1;
WHILE( StepSize < N )
{
// generate all the triangles with this step size
J := 0;
WHILE (J < (N - StepSize))
{
// Get the other two points that will make
// up this triangle
PtB := MIN(J+ StepSize, N-1);
PtC := MIN(J + 2*StepSize, N-1);
//if this is a non degenerate triangle...
IF(PtB != PtC)
{
//output triangle {J, PtB, PtC} relative
//to “base”
OutputTriangle(J + Base,
PtB + Base,
PtC + Base);
}
// Move to the next triangle in this set
J := J + 2*StepSize;
}
// Double the step size
StepSize := StepSize * 2;
}
【００４６】
当業者であれば、ＶＨＤＬ又はＶｅｒｉｌｏｇなどの言語を使用してこの単純なアルゴリズムをハードウェア内で実現することができ、加算器、レジスタ、及び比較器を含むわずかな構成要素しか必要でないことを理解すべきである。
【００４７】
図６に、より多くの頂点を有する任意多角形の５つの例を示す。図６ａのオーストラリアの地図は、約１５００個の頂点及び２６個の輪郭線を含む。図６ｂに示す「ヒルベルト曲線」は、１０００個の頂点を含む。図６ｃの「Ｔｈ」というテキストは８０７個の頂点を有し、図６ｄに示すランダムウォーク及び図６ｅに示す星は、両方とも１００個のソース頂点を有する。これらの任意多角形は、いずれも本発明を使用してレンダリングすることができる。例えば、図９に、この方法を図６ａの多角形に適用した際に出力される三角形のいくつかのサブセットを示しており、これらの６つの画像は、ＳｔｅｐＳｉｚｅがそれぞれ１、４、１６、６４、２５６、及び５１２のときに出力した三角形を取り込んでレンダリングした結果を示している。比較のために、図１０に、修正された従来技術の扇アルゴリズムによって生成される１０個目ごとの三角形を示す（この修正は、Ｓｈｒｅｉｎｅｒ他が提案するような低効率での併合ではなく、各輪郭線を別個に処理するものである）。図９と図１０を比較すると、このソースモデルでは、本発明によってこのように生成される三角形の方が、扇アルゴリズムによって生成されるものよりも著しく良好に成形されることが分かる。
【００４８】
さらに重要なことは、本発明によって生じる過剰描画の量である。図１１（Ａ）は、複数の三角形によって覆われた画素を示している。説明を簡単にするために、この図では、２つの三角形によって覆われた領域と、３又はそれ以上の三角形によって覆われた領域とを区別していないが、明らかに後者の方がコストがかかる。にも関わらず、過剰描画領域に接する画素数を、最終的な意図した結果の画素に対して単純に計算した場合、過剰描画の面積は、意図した最終結果の面積の約１５％であることが分かる。
【００４９】
対照的に、図１１（Ｂ）には、修正された扇アルゴリズムを用いた過剰描画領域を示している。この状況では、驚いたことに、過剰描画される画素の面積は最終結果の約３９％となる。なお、無修正のＳｈｒｅｉｎｅｒの扇アルゴリズムではさらに悪化する。
【００５０】
上述したこの本発明の第１の実施形態は、概して２つの最も重要な問題、すなわち三角形形状の改善の問題及び過剰描画の削減の問題に確実に対処する。それほど重要ではないが、第１の実施形態では、Ｎ−２個の三角形を必要とするＮ個の辺の輪郭線をＮ個の頂点だけで伝達できるようになる扇及びストリップの三角形データ効率が達成されない。第１の実施形態の方法の別の潜在的欠点は、最終的なＳｔｅｐＳｉｚｅ値が大きくなる可能性を除き、多くの場合、生成された「時系列的に」局所的な三角形が、単一の共有頂点の近傍においてのみ空間的に局所的となることである。
【００５１】
上述した実施形態によって作成される頂点の順序を調べた場合（さらに頂点が「１」から始まると仮定する場合）、三角形が、｛［ｖ1，ｖ2，ｖ3］，［ｖ3，ｖ4，ｖ5］，［ｖ5，ｖ6，ｖ7］．．．｛ｖ1，Ｖ3，ｖ5｝，［ｖ5，ｖ7，ｖ9］．．．｝の順序で作成されることが分かる。このデータが、Ｋ個の頂点のキャッシュ（通常、ＫはＮよりもかなり小さい）を有するハードウェアにインデックス付きフォーマットで供給されると仮定した場合、隣接する三角形間では、通常１つの頂点しか再使用されないので、３３％程度のキャッシュヒット率しか達成されない。一方、扇又はストリップでは２つの頂点が共有されるので、約６６％が達成される。
【００５２】
次に、これらのさらなる問題に対処する第２の好ましい実施形態を提供する。この第２の実施形態は、非常に小さなスタックという追加の特徴を組み入れる。輪郭線において遭遇するであろう頂点の最大数をＮＭａｘとすると、このスタックは、最大でも［ｌｏｇ2（ＮMax）］＋１（すなわち上限（ｌｏｇ2（Ｎmax））＋１）個のエントリしか必要としない。例えば、所与のシステムにおいて、輪郭線が最大２16個の頂点を有することができる場合、このスタックは、たった１７個のエントリしか有さない。
【００５３】
この実施形態では、プリミティブレベルを交互にして頂点の時間局所性を最大化し、全ての第１のレベルのプリミティブが生成される前に少なくとも１つの第２のレベルのプリミティブを生成する。元の任意閉多角形輪郭線の頂点に対してプリミティブ多角形の頂点を分離する際に、プリミティブ多角形レベルが反映される。第１のレベルのプリミティブは、元の閉多角形輪郭線内の連続する頂点である頂点を有する。上位レベルのプリミティブは、元の閉多角形輪郭線内で互いにオフセットされた頂点を有する。オフセット量は、プリミティブレベル及びプリミティブ内の頂点数に関連する。連続するｉ番目のレベルのプリミティブの端点では、（ｉ＋１）番目のレベル（ｉ≧１）のプリミティブが形成される。ｉ番目のレベルのプリミティブの組及び関連する頂点を考慮すると、各頂点は、端点という特別な場合を除き、この組の正確に１つの要素に属し、端点は、最大でも１つの他のｉ番目のレベルのプリミティブと共有される。
【００５４】
輪郭線が、全てのプリミティブレベルにわたる単一サイズのプリミティブに分割される場合、プリミティブレベルをｉ、及び多角形プリミティブサイズをＱとすると、ｉ番目のレベルのプリミティブにおける頂点は、元の任意閉多角形輪郭線内で互いに（Ｑ−１）＾（ｉ−１）だけオフセットされた頂点に対応する。例えば、三角形プリミティブのみを使用して輪郭線を分割する場合、第１のレベルのプリミティブが頂点［ｖ１，ｖ２，ｖ３］、［ｖ３，ｖ４，ｖ５］．．．を有すると仮定すると、第２のレベルのプリミティブは、元の閉多角形輪郭線の頂点に対するオフセットが（３−１）＾（２−１）＝２の頂点［ｖ１，ｖ３，ｖ５］，［ｖ５，ｖ７，ｖ９］．．．を有することになり、第３のレベルのプリミティブは、元の閉多角形輪郭線の頂点に対するオフセット４の頂点［ｖ１，ｖ５，ｖ９］，［ｖ９，ｖ１３，ｖ１７］．．．を有することになり、以下同様である。
【００５５】
第２の実施形態は、第１の変形と同じステップ１及び３を使用するが、ステップ２、すなわち単一の輪郭線の三角形分割を、以下の擬似コードで表す方法に置き換える。前回と同様に、輪郭線は頂点番号「ｂａｓｅ」から開始し、Ｎ個の頂点を有すると仮定する。
int Vstack[MAX_VERTEX_STACK_SIZE]; //vertex stack
int StackDepth;
int CurrentVertexID;
// put the first vertex, 0, on the stack.
StackDepth := 1;
Vstack[0] := 0;
CurrentVertexID := 1; //next vertex to process*/
// while we have at least 2 more vertices
WHILE(CurrentVertexID <= N-2)
{
// put the next two vertices on the stack
Vstack[StackDepth] := CurrentVertexID;
Vstack[StackDepth+1] := CurrentVertexID+1;
CurrentVertexID+=2;
StackDepth +=2;
// form a triangle from the top 3 vertices
OutputTriangle(Vstack[StackDepth-3] + Base,
Vstack[StackDepth-2] + Base,
Vstack[StackDepth-1] + Base);
// remove the ‘second from top’ stack element
Vstack[StackDepth-2] := Vstack[StackDepth-1];
StackDepth--;
// do all the higher triangle levels we can..
WHILE((StackDepth >= 3) &&
((Vstack[StackDepth-1] - Vstack[StackDepth-2]) ==
(Vstack[StackDepth-2] - Vstack[StackDepth-3])) )
{
// form a triangle from the top 3 vertices
OutputTriangle(Vstack[StackDepth-3] + Base,
Vstack[StackDepth-2] + Base,
Vstack[StackDepth-1] + Base);
// remove the second from top stack element
Vstack[StackDepth-2] := Vstack[StackDepth-1];
StackDepth--;
}//end while doing upper levels
}//end while at least 2 vertices left
// process remaining whole triangles on the stack
WHILE(StackDepth >= 3)
{
// form a triangle from the top 3 vertices
OutputTriangle(Vstack[StackDepth-3] + Base,
Vstack[StackDepth-2] + Base,
Vstack[StackDepth-1] + Base);
// remove the second from top stack element
Vstack[StackDepth-2] := Vstack[StackDepth-1];
StackDepth--;
}//end while
// if there is just one vertex left to do,
// add it to the stack and form the final triangle
IF(CurrentVertexID <= N-1)
{
Vstack[StackDepth] := CurrentVertexID;
StackDepth++;
// form a triangle from the top 3 vertices
OutputTriangle(Vstack[StackDepth-3] + Base,
Vstack[StackDepth-2] + Base,
Vstack[StackDepth-1] + Base);
}// end if one leftover vertex
【００５６】
この実施形態では、三角形が、はるかに「頂点キャッシュに適した」順序で作成される。具体的には、作成される三角形は、
｛［ｖ1，ｖ2，ｖ3］，［ｖ3，ｖ4，ｖ5］，［ｖ1，ｖ3，ｖ5］，［ｖ5，ｖ6，ｖ7］，［ｖ7，ｖ8，ｖ9］，［ｖ5，ｖ7，ｖ9］，［ｖ1，ｖ5，ｖ9］，．．．｝となる。
【００５７】
基本的に、第１の実施形態の「ＳｔｅｐＳｉｚｅ」の様々な値に対応する三角形が交互配置される。Ｎが十分に大きいと仮定すると、三角形は、少なくとも最初は以下のパターンのレベルに対応して作成される。
ＳｔｅｐＳｉｚｅ＝［１，１，２，１，１，２，４，１，１，２，１，１，２，４，８，１，．．．］
【００５８】
第２の実施形態によって作成される順序付けを使用して、ＦＩＦＯ置換ポリシーを有する１６個のエントリの頂点キャッシュが存在すると仮定した場合、例えば１２０個の頂点の輪郭線におけるヒット率は評価に値する６２％であり、これは第１の実施形態のほぼ２倍であり、扇又はストリップと同等である。
【００５９】
本発明を実施する装置の例を図１２に示す。入力バッファ２１０に、輪郭線のパラメータが供給される２００。これらのパラメータは状態マシーン２２０によって読み出され、この状態マシーンは、上記の擬似コードで記述したステップを実施する。
【００６０】
状態マシーンは、頂点スタックにアクセスすることができる。頂点スタックは、Ｐ個のスタックエントリを含む第１の部分２３０と、第２の部分２４０という２つの部分に分割されることが好ましい。状態マシーン２２０は、頂点スタック２３０の第１の部分の上位Ｐ個のエントリ（三角形分割の場合にはＰ＝３）に直接アクセスすることができる。これらの３つのエントリへの読み出しアクセス及び書き込みアクセスを並行して行えることが望ましいので、これらの部分は、独立したレジスタとして実現されることが好ましい。頂点スタック２４０の第２の部分は、残りのスタックエントリを保持し、単一の読み出し／書き込みポートしか必要とせず、従ってスタック上で４番目に高い要素のインデックスを有する安価なレジスタファイルで実現することができる。
【００６１】
スタックデータの押し出し及び抜き取りを可能にするために、この場合、上位３つのエントリを含む頂点スタックの第１の部分２３０と、スタック空間の残りの部分である第２の部分２４０との間に読み出し／書き込み経路２５０が存在する。
【００６２】
ユニット２３０は、上記の擬似コードで記述したような中心的要素（Ｐ＝３の場合、輪郭線が処理されるにつれて除外又はクリップされる要素に対応する上位から２番目のスタック要素）を削除又は上書きする能力もサポートする。状態マシーンの誘導の下、スタック演算が行われる。状態マシーンにより、プリミティブ出力ユニット、ここでは三角形出力ユニット２６０に、上位３つのスタック要素２３０を選択して対応する三角形を出力するように指示することができる。
【００６３】
いくつかの説明した三角形生成技術を使用して図６の任意多角形のステンシルを塗りつぶすための「サイクル」数を、レンダリングシミュレータを使用して互いに比較する。また、目標ベンチマークとして、真の三角形分割アルゴリズムの結果の（事前処理コストを含まない）レンダリングサイクルを提供する。解釈を容易にするために、（修正された）扇アルゴリズムがスコア１．０となるようにスコアを正規化する。数字が小さい方が良い。「Ｓａｎｄｅｒ」アルゴリズムは、本発明者がＳａｎｄｅｒ他の文献を解釈したものである。
【００６４】
明らかなように、本発明は、ステンシルを利用する他の方法と比較して一般的に好ましい。
【００６５】
第２の好ましい実施形態を、三角形インデックスを生成し始める前に、特定の輪郭線内に何個の頂点が存在するかを前もって把握する必要がないようにさらに構成することができる。このような実施形態は、「オンザフライ」で生成される頂点をストリーミングする用途において有用となる。また、この実施形態を、やはり頂点座標をより広いスタックに記憶することにより、レンダリングハードウェア内でインデックス付き三角形をサポートする必要がないように修正することもできる。
【００６６】
レンダリングシステムによっては、四角形（凸又は任意のいずれでも）、さらには、例えばＭ≦１６とするＭ個の辺の「任意」多角形のレンダリングをサポートするものもある。提示した好ましい実施形態は、いずれも本発明の範囲から逸脱することなく、三角形以外のプリミティブユニットを出力して、これらをより柔軟なレンダリングシステムに適合させるように容易に構成することができる。
【００６７】
このように提示する発明では、概して、従来技術と比較して過剰描画が減少し、三角形形状が改善され、及び／又は必要なデータが減少するが、異常な状況に遭遇する恐れがある。非常に単純な事例を図１３（Ａ）に示す。この例では、最初の３つの頂点｛ｖ１，ｖ２，ｖ３｝が、図１３（Ｂ）に灰色で示す他の全ての「ＳｔｅｐＳｉｚｅ＝１」の三角形３００がそうであるように、形状内に凹部を形成する。これらの三角形を処理した後、この方法は、なおも大きな五角形領域３１０を効果的に塗りつぶす必要がある。図から分かるように、これらの三角形は全て、かなりの量の過剰描画領域を形成する。
【００６８】
図１３における最初の頂点の場所は「不運」であった。そうではなく、この実施形態が、図１４（Ａ）に示す幾何学的に均等な図を受け取った場合、図１４（Ｂ）の別の「ＳｔｅｐＳｉｚｅ＝１」の三角形が代わりに作成される。これにより、残りの「ＳｔｅｐＳｉｚｅ」の三角形によって覆うべき領域３７０のみが残され、過剰描画は全く生じない。
【００６９】
従って、別の実施形態では、これらの異常な事例の頻度を低減させようと試みる。Ｓｅｉｄｅｌの「真の三角形分割」からの思いつきで、別の実施形態ではランダム化技術を使用する。この実施形態では、輪郭線ごとにランダム又は擬似ランダムなオフセット値を供給又は計算することができる。その後、このオフセットを、Ｎを法として輪郭線内の全ての頂点インデックスに加算して、最悪の事例が再発する可能性を低減させる。
【００７０】
多角形データによっては、頂点自体を任意のインデックスのアレイとして頂点アレイ内に供給できるものもある。当業者には、本明細書に示す実施形態を、このような間接的方法をサポートするように拡張できることが明らかであろう。
【００７１】
Ａｄｏｂｅフラッシュフォーマットでは、任意多角形の縁部が、明らかにランダムな分断された順序で供給される。当業者であれば、本明細書に記載した発明を適用する前に、ハッシュ処理システムを使用して、これらを連結されたチェーンに並べ替えできることを認識するであろう。
【００７２】
上記の方法で三角形分割を描画することによってステンシルを構成したら、上述したような当業で公知の方法のいずれかにより、すなわち境界ボックスを使用して又は三角形分割を再使用して、これらの三角形に塗りつぶし／陰影付け／模様付けを行うことができる。さらに、親多角形の頂点の屈曲順序が一貫したものである場合、本発明で提示した追加の機能強化を使用することにより、三角形分割をレンダリングシステムに再送できるが、頂点の屈曲順序が逆の三角形を除外するように指示することができる。
【符号の説明】
【００７３】
Ｖ１〜Ｖ７ 頂点
【特許請求の範囲】
【請求項１】
ステンシルバッファを使用してコンピュータ生成画像をレンダリングする方法であって、
Ｎ個の頂点を有する任意閉多角形輪郭線を受信するステップと、
前記任意閉多角形輪郭線を、２＜Ｐ＜Ｎとする少なくとも３つの及び最大でＰ個の頂点を各々が有する多角形であるプリミティブに分割するステップと、
ステンシルバッファを使用して前記プリミティブをレンダリングし、コンピュータ生成画像を生成するステップと、
を含み、前記分割ステップが、
ｉ）前記任意閉多角形輪郭線の１つの頂点を第１の指標頂点として選択し、前記任意閉多角形輪郭線としてのソース輪郭線を設定するステップと、
ｉｉ）前記指標頂点と、前記ソース輪郭線の（Ｑ−１）個の連続する頂点とを使用して、Ｑ個の頂点で構成されるプリミティブを出力するステップと、
ｉｉｉ）前記出力したプリミティブの前記指標頂点と終端頂点との間の（Ｑ−２）個の頂点を前記ソース輪郭線から削除することにより切り詰めたソース輪郭線を形成するステップと、
ｉｖ）前記出力したプリミティブの前記終端頂点を、前記指標頂点として設定するステップと、
ｖ）前記ソース輪郭線の全ての頂点が前記生成プリミティブの少なくとも１つに含まれるまで、ステップ（ｉｉ）からステップ（ｉｖ）を繰り返すステップと、
ｖｉ）前記切り詰めたソース輪郭線の頂点を指標頂点として選択し、前記切り詰めたソース輪郭線としての前記ソース輪郭線を設定するステップと、
ｖｉｉ）前記切り詰めたソース輪郭線がプリミティブとして出力されるまで、又は前記切り詰めたソース輪郭線が自明なゼロ面積を有するまで、ステップ（ｉｉ）からステップ（ｖ）を繰り返すステップと、
を含むことを特徴とする方法。
【請求項２】
ステンシルバッファを使用してコンピュータ生成画像をレンダリングする方法であって、
Ｎ個の頂点を有する任意閉多角形輪郭線を受信するステップと、
前記任意閉多角形輪郭線を、２＜Ｐ＜Ｎとする少なくとも３つの及び最大でＰ個の頂点を各々が有する多角形であるプリミティブに分割するステップと、
ステンシルバッファを使用して前記プリミティブをレンダリングし、コンピュータ生成画像を生成するステップと、
を含み、前記分割ステップが、
（ｉ）前記閉多角形輪郭線からの部分的輪郭線を表すデータを記憶するステップと、
（ｉｉ）前記記憶したデータを使用して、前記閉多角形輪郭線の連続する頂点に対応する第１のレベルのプリミティブを出力するステップと、
（ｉｉｉ）前記記憶したデータを更新するステップと、
（ｉｖ）前記記憶したデータが上位レベルのプリミティブを表している間に、前記記憶したデータを使用して上位レベルのプリミティブを出力し、上位（ｉ＋１）番目のレベルのプリミティブが、連続するｉ番目のレベルのプリミティブの終端頂点に対応し、前記記憶したデータを更新するステップと、
（ｖ）前記記憶したデータがさらなる第１のレベルのプリミティブを表している間に、前記さらなる第１のレベルのプリミティブを出力し、前記記憶したデータを更新するステップと、
（ｖｉ）前記閉多角形輪郭線がプリミティブに分割されるまで、又は残りの部分的輪郭線が実質的なゼロ面積を有するまで、ステップ（ｉ）からステップ（ｖ）を繰り返すステップと、
を含むことを特徴とする方法。
【請求項３】
前記ステップ（ｉ）が、出力すべき前記第１のレベルのプリミティブの頂点数をＱとする、前記閉多角形輪郭線の少なくともＱ個の連続する頂点を表すデータを記憶するステップを含む、
ことを特徴とする請求項２に記載の方法。
【請求項４】
前記ステップ（ｉｉｉ）における記憶したデータを更新するステップが、前記第１のレベルのプリミティブの（Ｑ−２）個の中心の頂点を表すデータを上書きするステップを含む、
ことを特徴とする請求項２又は請求項３に記載の方法。
【請求項５】
前記ステップ（ｉｖ）における記憶したデータを更新するステップが、前記上位レベルのプリミティブの（Ｑ−２）個の中心の頂点を表すデータを上書きするステップを含む、
ことを特徴とする請求項２から請求項４のいずれかに記載の方法。
【請求項６】
前記輪郭線をプリミティブに分割する前に、前記任意閉多角形輪郭線内の全ての頂点インデックスにＮを法としてオフセットが加算される、
ことを特徴とする請求項１から請求項５のいずれかに記載の方法。
【請求項７】
前記ステンシルバッファを使用して前記プリミティブをレンダリングするステップが、各プリミティブの屈曲順序を、前記任意閉多角形輪郭線の全体的屈曲順序と比較するステップと、前記全体的屈曲順序と同じ屈曲順序のプリミティブのみを、色及び／又は模様の塗りつぶし処理で使用するステップとをさらに含む、
ことを特徴とする請求項１から請求項６のいずれかに記載の方法。
【請求項８】
複数の閉多角形輪郭線を含む複雑な任意多角形が受信され、前記方法が、前記複雑な任意多角形をその成分である閉多角形輪郭線に分離するステップをさらに含み、その後、個々の成分である閉多角形輪郭線にプリミティブへの分割が行われ、個々の成分である閉多角形輪郭線で構成される結果としてのプリミティブが、前記ステンシルバッファを用いたレンダリングの前に連結される、
ことを特徴とする請求項１から請求項７のいずれかに記載の方法。
【請求項９】
実質的に全てのプリミティブが三角形である、
ことを特徴とする請求項１から請求項８のいずれかに記載の方法。
【請求項１０】
コンピュータ生成画像をレンダリングするための装置であって、
任意閉多角形輪郭線を受信するための入力部と、
前記任意のＮ個の頂点の閉多角形輪郭線を、２＜Ｐ＜Ｎとする少なくとも３つの及び最大でＰ個の頂点を各々が有する多角形であるプリミティブに分割して該プリミティブを出力するための手段と、
前記プリミティブをレンダリングしてコンピュータ生成画像を生成するためのステンシルバッファと、
を備え、前記任意閉多角形輪郭線をプリミティブに分割するための手段が、請求項１から請求項９のいずれかに記載の方法を実施するように構成される、
ことを特徴とする装置。
【請求項１１】
前記任意閉多角形輪郭線をプリミティブに分割するための前記手段が、
Ｐ個のスタックエントリを含む第１の部分と、第２の部分とを含み、前記第１の部分と前記第２の部分の間でスタックデータの押し出し及び抜き取りを可能にするように構成された頂点スタック手段と、
前記頂点スタック手段の前記第１の部分及び状態マシーン手段に結合された、前記頂点スタック手段の前記第１の部分に存在する前記データからプリミティブを出力するためのプリミティブ出力手段と、
前記頂点スタック手段に結合された、前記頂点スタック手段の前記第１及び第２の部分に存在する前記データを管理して、前記プリミティブ出力手段の前記出力におけるプリミティブレベルを交互にするように構成された前記状態マシーン手段と、
を備えることを特徴とする請求項１０に記載の装置。
【請求項１２】
コンピュータ生成画像をレンダリングするための装置であって、
任意閉多角形輪郭線を受信するための入力部と、
前記任意閉多角形輪郭線を、少なくとも３つの及び最大でＰ個の頂点を各々が有する多角形であるプリミティブに分割して該プリミティブを出力するための手段と、
前記任意閉多角形輪郭線を分割するための手段に結合された、前記プリミティブをレンダリングしてコンピュータ生成画像を生成するためのステンシルバッファと、
を備え、前記任意閉多角形輪郭線をプリミティブに分割するための前記手段が、
Ｐ個のスタックエントリを含む第１の部分と、第２の部分とを含み、前記第１の部分と前記第２の部分の間でスタックデータの押し出し及び抜き取りを可能にするように構成された頂点スタック手段と、
前記頂点スタック手段の前記第１の部分及び状態マシーン手段に結合された、前記頂点スタック手段の前記第１の部分に存在する前記データからプリミティブを出力するためのプリミティブ出力手段と、
前記頂点スタック手段に結合された、前記頂点スタック手段の前記第１及び第２の部分に存在する前記データを管理して、前記プリミティブ出力手段の前記出力におけるプリミティブレベルを交互にするように構成された前記状態マシーン手段と、
を備えることを特徴とする装置。
【請求項１】
ステンシルバッファを使用してコンピュータ生成画像をレンダリングする方法であって、
Ｎ個の頂点を有する任意閉多角形輪郭線を受信するステップと、
前記任意閉多角形輪郭線を、２＜Ｐ＜Ｎとする少なくとも３つの及び最大でＰ個の頂点を各々が有する多角形であるプリミティブに分割するステップと、
ステンシルバッファを使用して前記プリミティブをレンダリングし、コンピュータ生成画像を生成するステップと、
を含み、前記分割ステップが、
ｉ）前記任意閉多角形輪郭線の１つの頂点を第１の指標頂点として選択し、前記任意閉多角形輪郭線としてのソース輪郭線を設定するステップと、
ｉｉ）前記指標頂点と、前記ソース輪郭線の（Ｑ−１）個の連続する頂点とを使用して、Ｑ個の頂点で構成されるプリミティブを出力するステップと、
ｉｉｉ）前記出力したプリミティブの前記指標頂点と終端頂点との間の（Ｑ−２）個の頂点を前記ソース輪郭線から削除することにより切り詰めたソース輪郭線を形成するステップと、
ｉｖ）前記出力したプリミティブの前記終端頂点を、前記指標頂点として設定するステップと、
ｖ）前記ソース輪郭線の全ての頂点が前記生成プリミティブの少なくとも１つに含まれるまで、ステップ（ｉｉ）からステップ（ｉｖ）を繰り返すステップと、
ｖｉ）前記切り詰めたソース輪郭線の頂点を指標頂点として選択し、前記切り詰めたソース輪郭線としての前記ソース輪郭線を設定するステップと、
ｖｉｉ）前記切り詰めたソース輪郭線がプリミティブとして出力されるまで、又は前記切り詰めたソース輪郭線が自明なゼロ面積を有するまで、ステップ（ｉｉ）からステップ（ｖ）を繰り返すステップと、
を含むことを特徴とする方法。
【請求項２】
ステンシルバッファを使用してコンピュータ生成画像をレンダリングする方法であって、
Ｎ個の頂点を有する任意閉多角形輪郭線を受信するステップと、
前記任意閉多角形輪郭線を、２＜Ｐ＜Ｎとする少なくとも３つの及び最大でＰ個の頂点を各々が有する多角形であるプリミティブに分割するステップと、
ステンシルバッファを使用して前記プリミティブをレンダリングし、コンピュータ生成画像を生成するステップと、
を含み、前記分割ステップが、
（ｉ）前記閉多角形輪郭線からの部分的輪郭線を表すデータを記憶するステップと、
（ｉｉ）前記記憶したデータを使用して、前記閉多角形輪郭線の連続する頂点に対応する第１のレベルのプリミティブを出力するステップと、
（ｉｉｉ）前記記憶したデータを更新するステップと、
（ｉｖ）前記記憶したデータが上位レベルのプリミティブを表している間に、前記記憶したデータを使用して上位レベルのプリミティブを出力し、上位（ｉ＋１）番目のレベルのプリミティブが、連続するｉ番目のレベルのプリミティブの終端頂点に対応し、前記記憶したデータを更新するステップと、
（ｖ）前記記憶したデータがさらなる第１のレベルのプリミティブを表している間に、前記さらなる第１のレベルのプリミティブを出力し、前記記憶したデータを更新するステップと、
（ｖｉ）前記閉多角形輪郭線がプリミティブに分割されるまで、又は残りの部分的輪郭線が実質的なゼロ面積を有するまで、ステップ（ｉ）からステップ（ｖ）を繰り返すステップと、
を含むことを特徴とする方法。
【請求項３】
前記ステップ（ｉ）が、出力すべき前記第１のレベルのプリミティブの頂点数をＱとする、前記閉多角形輪郭線の少なくともＱ個の連続する頂点を表すデータを記憶するステップを含む、
ことを特徴とする請求項２に記載の方法。
【請求項４】
前記ステップ（ｉｉｉ）における記憶したデータを更新するステップが、前記第１のレベルのプリミティブの（Ｑ−２）個の中心の頂点を表すデータを上書きするステップを含む、
ことを特徴とする請求項２又は請求項３に記載の方法。
【請求項５】
前記ステップ（ｉｖ）における記憶したデータを更新するステップが、前記上位レベルのプリミティブの（Ｑ−２）個の中心の頂点を表すデータを上書きするステップを含む、
ことを特徴とする請求項２から請求項４のいずれかに記載の方法。
【請求項６】
前記輪郭線をプリミティブに分割する前に、前記任意閉多角形輪郭線内の全ての頂点インデックスにＮを法としてオフセットが加算される、
ことを特徴とする請求項１から請求項５のいずれかに記載の方法。
【請求項７】
前記ステンシルバッファを使用して前記プリミティブをレンダリングするステップが、各プリミティブの屈曲順序を、前記任意閉多角形輪郭線の全体的屈曲順序と比較するステップと、前記全体的屈曲順序と同じ屈曲順序のプリミティブのみを、色及び／又は模様の塗りつぶし処理で使用するステップとをさらに含む、
ことを特徴とする請求項１から請求項６のいずれかに記載の方法。
【請求項８】
複数の閉多角形輪郭線を含む複雑な任意多角形が受信され、前記方法が、前記複雑な任意多角形をその成分である閉多角形輪郭線に分離するステップをさらに含み、その後、個々の成分である閉多角形輪郭線にプリミティブへの分割が行われ、個々の成分である閉多角形輪郭線で構成される結果としてのプリミティブが、前記ステンシルバッファを用いたレンダリングの前に連結される、
ことを特徴とする請求項１から請求項７のいずれかに記載の方法。
【請求項９】
実質的に全てのプリミティブが三角形である、
ことを特徴とする請求項１から請求項８のいずれかに記載の方法。
【請求項１０】
コンピュータ生成画像をレンダリングするための装置であって、
任意閉多角形輪郭線を受信するための入力部と、
前記任意のＮ個の頂点の閉多角形輪郭線を、２＜Ｐ＜Ｎとする少なくとも３つの及び最大でＰ個の頂点を各々が有する多角形であるプリミティブに分割して該プリミティブを出力するための手段と、
前記プリミティブをレンダリングしてコンピュータ生成画像を生成するためのステンシルバッファと、
を備え、前記任意閉多角形輪郭線をプリミティブに分割するための手段が、請求項１から請求項９のいずれかに記載の方法を実施するように構成される、
ことを特徴とする装置。
【請求項１１】
前記任意閉多角形輪郭線をプリミティブに分割するための前記手段が、
Ｐ個のスタックエントリを含む第１の部分と、第２の部分とを含み、前記第１の部分と前記第２の部分の間でスタックデータの押し出し及び抜き取りを可能にするように構成された頂点スタック手段と、
前記頂点スタック手段の前記第１の部分及び状態マシーン手段に結合された、前記頂点スタック手段の前記第１の部分に存在する前記データからプリミティブを出力するためのプリミティブ出力手段と、
前記頂点スタック手段に結合された、前記頂点スタック手段の前記第１及び第２の部分に存在する前記データを管理して、前記プリミティブ出力手段の前記出力におけるプリミティブレベルを交互にするように構成された前記状態マシーン手段と、
を備えることを特徴とする請求項１０に記載の装置。
【請求項１２】
コンピュータ生成画像をレンダリングするための装置であって、
任意閉多角形輪郭線を受信するための入力部と、
前記任意閉多角形輪郭線を、少なくとも３つの及び最大でＰ個の頂点を各々が有する多角形であるプリミティブに分割して該プリミティブを出力するための手段と、
前記任意閉多角形輪郭線を分割するための手段に結合された、前記プリミティブをレンダリングしてコンピュータ生成画像を生成するためのステンシルバッファと、
を備え、前記任意閉多角形輪郭線をプリミティブに分割するための前記手段が、
Ｐ個のスタックエントリを含む第１の部分と、第２の部分とを含み、前記第１の部分と前記第２の部分の間でスタックデータの押し出し及び抜き取りを可能にするように構成された頂点スタック手段と、
前記頂点スタック手段の前記第１の部分及び状態マシーン手段に結合された、前記頂点スタック手段の前記第１の部分に存在する前記データからプリミティブを出力するためのプリミティブ出力手段と、
前記頂点スタック手段に結合された、前記頂点スタック手段の前記第１及び第２の部分に存在する前記データを管理して、前記プリミティブ出力手段の前記出力におけるプリミティブレベルを交互にするように構成された前記状態マシーン手段と、
を備えることを特徴とする装置。
【図１ａ】
【図１ｂ】
【図１ｃ】
【図１ｄ】
【図１ｅ】
【図２】
【図３】
【図４】
【図５】
【図６ａ】
【図６ｂ】
【図６ｃ】
【図６ｄ】
【図６ｅ】
【図７】
【図８】
【図９ａ−９ｆ】
【図１０】
【図１１ａ】
【図１１ｂ】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１ｂ】
【図１ｃ】
【図１ｄ】
【図１ｅ】
【図２】
【図３】
【図４】
【図５】
【図６ａ】
【図６ｂ】
【図６ｃ】
【図６ｄ】
【図６ｅ】
【図７】
【図８】
【図９ａ−９ｆ】
【図１０】
【図１１ａ】
【図１１ｂ】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公表番号】特表２０１２−５２７６７６（Ｐ２０１２−５２７６７６Ａ）
【公表日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願番号】特願２０１２−５１１３３５（Ｐ２０１２−５１１３３５）
【出願日】平成２２年５月１７日（２０１０．５．１７）
【国際出願番号】ＰＣＴ／ＧＢ２０１０／０００９９５
【国際公開番号】ＷＯ２０１０／１３３８３３
【国際公開日】平成２２年１１月２５日（２０１０．１１．２５）
【出願人】（５０１１７６０３７）イマジネイション テクノロジーズ リミテッド (59)
【Ｆターム（参考）】
【公表日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願日】平成２２年５月１７日（２０１０．５．１７）
【国際出願番号】ＰＣＴ／ＧＢ２０１０／０００９９５
【国際公開番号】ＷＯ２０１０／１３３８３３
【国際公開日】平成２２年１１月２５日（２０１０．１１．２５）
【出願人】（５０１１７６０３７）イマジネイション テクノロジーズ リミテッド (59)
【Ｆターム（参考）】
[ Back to top ]