(57)【特許請求の範囲】
【請求項１】
テッセレートされた画像データを表し、且つ、各々が複数の辺（４２２）を含んでいる複数のポリゴン（４２０）に関するハイブリッド隠線処理を、ＰＤＭデータ処理システム（１００）によって実施するための方法において、
前記テッセレートされた画像データのシルエットの後向きの側に複数のポリゴン（４２０）を含んでいる後向きプレートと、前記テッセレートされた画像データの前記シルエットの前向きの側に複数のポリゴンを含んでいる前向きプレートとを、シルエット生成器（４０２）によって識別するステップ（５０４）と、
識別された前記前向きプレート及び前記後向きプレートのポリゴン（４０２）を、メモリ（３０４）の中に前向きプレート及び後向きプレートとして分類しておくステップ（５０６）と、
Ｚデプスポリゴン（４０２）スキャンコンバージョンを実行し（５０８）、前記ポリゴン（４２０）の外辺及びシルエット辺を識別し、変換及び識別されたデータをＺバッファ（４２６）に記憶するステップと、
前記Ｚバッファ（４２６）における、外辺の一部であるピクセルをマークするステップ（５１０）と、
前記辺をトレースするステップ（５１４）と、
トレースした辺間の交差を設置することによって、前記トレースした辺の各サブセットにおける、少なくとも一つの可視性変化ピクセルを識別するステップ（５２０）と、
各可視性変化ピクセルに対して、前記トレースした辺が、前記可視性変化ピクセルに対応するポリゴンと同一のプレートに由来しているか否かを決定するステップ（５２２）と、
前記可視性変化ピクセルに対応するポリゴンと同一のプレートに由来することが確認された（５２４）、各トレースした辺について、該トレースした辺を表示するステップ（５３２）と、
を備えていることを特徴とする、方法。
【請求項２】
前記辺の少なくとも一つのサブセットはそれぞれ外辺及び内辺の一方を含み、
前記方法は更に、
前記可視性変化ピクセルに対応するポリゴンとは異なるプレートに由来することが確認された（５２４）、前記トレースした辺の各サブセットについて、前記可視性変化ピクセルに対応する外辺を識別するステップと、
識別された各外辺について、可視性変化点を識別するために、前記トレースした辺と前記外辺を交差させるステップ（５２６）と、
を備えている、請求項１に記載の方法。
【請求項３】
前記トレースした辺と前記外辺を交差させるステップ（５２６）は、第１の線セグメントと第２の線セグメントを交差させるステップを含む、請求項２に記載の方法。
【請求項４】
前記トレースした辺と前記外辺を交差させるステップ（５２６）は、第１の曲線と第２の曲線を交差させるステップを含む、請求項２に記載の方法。
【請求項５】
前記ポリゴンは三角形を含み、該三角形の各頂点についてシルエット関数を実行し、
前記シルエット関数は、前記三角形の三つの頂点の各々における、法線ベクトルと視線ベクトルのドット積である、請求項１乃至４のいずれか一項に記載の方法。
【請求項６】
前記シルエット関数が三つの三角形頂点の各々について負である場合には、前記ポリゴン（４０２）を後向きポリゴンとして識別し、該ポリゴンに関してシルエットは存在しないことを確認し、
前記シルエット関数が三つの三角形頂点の各々について正である場合には、前記ポリゴンを前向きポリゴンとして識別し、該ポリゴンに関してシルエットは存在しないことを確認し、
前記ポリゴンに関する少なくとも一つのシルエット関数が負であり、且つ、前記ポリゴンに関する少なくとも一つのシルエット関数が正である場合には、前記ポリゴンをシルエットポリゴンとして識別し、二つのシルエット点を識別するために前記シルエットポリゴン（４０２）の辺に沿って線形補間を実施し、前記二つのシルエット点を結ぶことによってシルエットセグメントを形成する、請求項５に記載の方法。
【請求項７】
前記線形補間の実施は、前記シルエットポリゴンの第１の辺及び前記シルエットポリゴンの第２の辺に沿った線形補間を含み、
前記シルエットポリゴンの第３の辺は、前記シルエット関数が同一の符号を有している二つの頂点を結んだものである、請求項６に記載の方法。
【請求項８】
前記シルエットの生成は更に、前記シルエットポリゴンの各々に関する前記シルエットセグメントを一つに結合させて、シルエット辺を生成することを含む、請求項６に記載の方法。
【請求項９】
前記シルエットの生成は更に、
（ｉ）既知のタイプの面に関して、前記シルエット辺に曲線をフィットさせること、
（ｉｉ）未知のタイプの面に関して、各シルエットセグメントの前記シルエット点を通るように３次Ｂスプラインをフィットさせること、
の内の少なくとも一方によって、前記シルエット辺の精度を高めることを含む、請求項８に記載の方法。
【請求項１０】
データ処理システムであって、
メモリと、該メモリに接続されているハイブリッド隠線プロセッサと、該ハイブリッド隠線プロセッサに接続されているディスプレイとを備えており、
前記メモリは、テッセレートされた画像データを表す複数のポリゴンと、該複数のポリゴンの外辺と、前記テッセレートされた画像データのシルエットの前向きの側に複数のポリゴンを含んでいる前向きプレートとを記憶し、
前記ハイブリッド隠線プロセッサは、前記ポリゴンに関する頂点法線に基づきシルエットを生成し、且つ、前記外辺及び前記シルエットに対するプレート保護を提供することによって、前記テッセレートされた画像データに基づき表示データを生成し、
前記ディスプレイは、前記表示データに基づき、処理された画像を表示する、
データ処理システムにおいて、
前記プロセッサは、
前記前向きプレートを生成し、且つ、前記シルエットの後向きの側に複数のポリゴンを含んでいる後向きプレートを生成する、プレート生成器と、
前記辺をトレースし、該トレースした辺の各サブセットにおいて、トレースした辺間の交差を設置することによって、少なくとも一つの可視性変化ピクセルを識別する、可視性トレーサと、
プレートプロテクタとを備えており、
前記プレートプロテクタは、各可視性変化ピクセルに関して、前記トレースした辺が、前記可視性変化ピクセルに対応するポリゴンと同一のプレートに由来するものであるか否かを確認し、前記可視性変化ピクセルに対応するポリゴンと同一のプレートに由来するものであることが確認された各トレースした辺に関して、該トレースした辺を表示させることによって、プレート保護を提供する、
ことを特徴とする、データ処理システム。
【請求項１１】
前記プロセッサは更に、
（ｉ）前記可視性変化ピクセルに対応するポリゴンとは異なるプレートに由来するものであることが確認された、前記トレースした辺の各サブセットに関して、前記可視性変化ピクセルに対応する外辺を識別し、
（ｉｉ）識別された各外辺に関して、可視性変化点を識別するために、前記トレースした辺と前記外辺を交差させる、
辺インターセクタを備えている、請求項１０に記載のデータ処理システム。
【請求項１２】
前記ポリゴンは三角形を含み、
前記プロセッサは更に、各ポリゴンに関して、前記シルエットを生成するシルエット生成器を備えており、
前記シルエットの生成を以下のように実行する、即ち、
前記ポリゴンの各頂点についてシルエット関数を実行し、
前記シルエット関数が三つの三角形頂点の各々について負である場合には、前記ポリゴンを後向きポリゴンとして識別し、該ポリゴンに関してシルエットは存在しないことを確認し、
前記シルエット関数が三つの三角形頂点の各々について正である場合には、前記ポリゴンを前向きポリゴンとして識別し、該ポリゴンに関してシルエットは存在しないことを確認し、
前記ポリゴンに関する少なくとも一つのシルエット関数が負であり、且つ、前記ポリゴンに関する少なくとも一つのシルエット関数が正である場合には、前記ポリゴンをシルエットポリゴンとして識別し、二つのシルエット点を識別するために前記シルエットポリゴンの辺に沿って線形補間を実施し、前記二つのシルエット点を結ぶことによってシルエットセグメントを形成する、
ことによって実行する、請求項１０に記載のデータ処理システム。
【請求項１３】
前記シルエット生成器は更に、前記シルエット関数が同一の符号を有している二つの頂点を結んだものである、前記シルエットポリゴンの第１の辺を識別し、且つ、前記シルエットポリゴンの第２の辺及び前記シルエットポリゴンの第３の辺に沿った線形補間を実施する、請求項１２に記載のデータ処理システム。
【請求項１４】
実行可能な命令がコーディングされている、非一時的なコンピュータ読み出し可能媒体において、
前記命令が実行されると、一つ又は複数のデータ処理システムに、
シルエットの後向きの側において、各々が複数の辺を含んでいる複数のポリゴンを含んでいる後向きプレートと、前記シルエットの前向きの側において、各々が複数の辺を含んでいる複数のポリゴンを含んでいる前向きプレートとを生成させ、
前記辺をトレースさせ、
トレースした辺間の交差を設置することによって、前記トレースした辺の各サブセットにおける、少なくとも一つの可視性変化ピクセルを識別させ、
各可視性変化ピクセルに関して、前記トレースした辺は、前記可視性変化ピクセルに対応するポリゴンと同一のプレートに由来するものであるか否かを確認させ、前記可視性変化ピクセルに対応するポリゴンと同一のプレートに由来するものであることが確認された各トレースした辺に関して、該トレースした辺を表示させる、
ことを特徴とする、非一時的なコンピュータ読み出し可能媒体。
【請求項１５】
前記辺の少なくとも一つのサブセットはそれぞれ外辺及び内辺の一方を含み、且つ、前記コンピュータ読み出し可能媒体には更に、実行時に、一つ又は複数のデータ処理システムに、
前記可視性変化ピクセルに対応するポリゴンとは異なるプレートに由来することが確認された、前記トレースした辺の各サブセットについて、前記可視性変化ピクセルに対応する外辺を識別させ、
識別された各外辺について、可視性変化点を識別するために、前記トレースした辺と前記外辺を交差させる、
実行可能な命令がコーディングされている、請求項１４に記載のコンピュータ読み出し可能媒体。
【請求項１６】
前記ポリゴンは三角形を含み、且つ、前記コンピュータ読み出し可能媒体には更に、実行時に、一つ又は複数のデータ処理システムに、
各ポリゴンに関して、
前記ポリゴンの各頂点についてシルエット関数を実行させ、
前記シルエット関数が三つの三角形頂点の各々について負である場合には、前記ポリゴンを後向きポリゴンとして識別させ、該ポリゴンに関してシルエットは存在しないことを確認させ、
前記シルエット関数が三つの三角形頂点の各々について正である場合には、前記ポリゴンを前向きポリゴンとして識別させ、該ポリゴンに関してシルエットは存在しないことを確認させ、
前記ポリゴンに関する少なくとも一つのシルエット関数が負であり、且つ、前記ポリゴンに関する少なくとも一つのシルエット関数が正である場合には、前記ポリゴンをシルエットポリゴンとして識別させ、二つのシルエット点を識別するために前記シルエットポリゴンの辺に沿って線形補間を実施させ、前記二つのシルエット点を結ぶことによってシルエットセグメントを形成させ、
シルエット辺を生成するために、前記シルエットポリゴンの各々に関する前記シルエットセグメントを一つに結合させる、
実行可能な命令がコーディングされている、請求項１４に記載のコンピュータ読み出し可能媒体。
【請求項１７】
前記ポリゴンは三角形を含み、且つ、前記コンピュータ読み出し可能媒体には更に、実行時に、一つ又は複数のデータ処理システムに、
（ｉ）既知のタイプの面に関して、前記シルエット辺に曲線をフィットさせること、
（ｉｉ）未知のタイプの面に関して、各シルエットセグメントの前記シルエット点を通るように３次Ｂスプラインをフィットさせること、
の内の少なくとも一方によって、前記シルエット辺の精度を高めさせる、
実行可能な命令がコーディングされている、請求項１６に記載のコンピュータ読み出し可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、独立請求項に記載されている、複数のポリゴンに関するハイブリッド隠線処理を提供するための、方法、製品情報管理（ＰＤＭ：Product Data Management）データ処理システム及びコンピュータ読み出し可能媒体に関する。
【背景技術】
【０００２】
本発明は全体的に、製品及び他の商品のためのデータを管理する、コンピュータ支援設計（「ＣＡＤ」）、視覚化、製造システム、製品ライフサイクル管理（「ＰＬＭ」）及び同様のシステムに関する（それらのシステムを集合的に「製品情報管理」システム又ＰＤＭシステムと称する）。従来のコンピュータグラフィックス表示システムは、三次元物体の二次元画像を生成するために種々の処理を使用する。
【０００３】
発明の概要
本明細書に開示されている種々の実施の形態には、システム、方法及びコンピュータ読み出し可能媒体が含まれる。テッセレートされた画像データを表し、且つ、各々が複数の辺（エッジ）を含んでいる複数のポリゴンに関するハイブリッド隠線処理を実施するための方法が開示されている。この方法は、テッセレートされた画像データのシルエットの後向きの側に複数のポリゴンを含んでいる後向きプレートと、テッセレートされた画像データのシルエットの前向きの側に複数のポリゴンを含んでいる前向きプレートとを生成するステップを備えている。この方法は、複数の辺をトレースするステップと、トレースしたそれらの辺の各サブセットにおいて、少なくとも一つの可視性変化ピクセルを識別するステップとを備えている。この方法は、各可視性変化ピクセルに対して、トレースした辺が、可視性変化ピクセルに対応するポリゴンと同一のプレートに由来しているか否かを決定するステップを備えている。この方法は、可視性変化ピクセルに対応するポリゴンと同一のプレートに由来することが確認された、各トレースした辺について、そのトレースした辺を表示するステップを備えている。
【０００４】
上記においては、当業者が以下の詳細な説明をより良く理解できるように、本発明の特徴及び技術的な利点をかなり大まかに述べている。本発明の更なる特徴及び利点を下記において説明するが、これは特許請求の範囲の対象をなしている。当業者であれば、本開示の同一の目的を達成するための他のシステムを修正又は設計するための基礎として記載した、コンセプト及び特定の実施の形態を容易に使用できることが分かる。当業者であれば、そのような等価の構造は、最も広義の形態での本発明の思想及び範囲から逸脱しないように実現することができる。
【０００５】
以下の発明を実施するための形態の項に先立って、本明細書全体にわたり使用されている幾つかの用語又は語句の定義を明確にしておくことは有利である：「含む」及び「備えている」、またそれらから派生した語は限定的でない包含を意味しており、「又は」という語は包含的な語であり、即ち、及び／又は、を意味しており、「関連した」及び「それと関連した」並びにそれらから派生した語は、含む、その中に含まれる、相互に接続されている、〜に、又は、〜と結合する、〜と通じている、〜と協働する、交互配置する、並置する、〜と近接している、〜と又は〜に結び付けられている、〜を有する、〜の性質を有する等を意味しており、また「コントローラ」という語は、ハードウェア、ファームウェア又はソフトウェアで実施されているか、又はそれらの内の少なくとも二つのいずれかの組合せで実施されている、少なくとも一つの動作を制御する任意のデバイス、システム又はそれらの一部を意味している。任意の特定のコントローラに関連する機能は中央に集中していても良いし、局所的であれ遠隔的であれ分散していても良いことを言及しておく。本明細書全体にわたり幾つかの用語及び語句の定義が示されているが、当業者であれば、そのような定義は、殆どではないにしろ、その多くがそのように定義された用語及び語句の以前の用法及び将来の用法にも当てはまることを理解するであろう。幾つかの語は多様な実施の形態を含んでいるが、添付の特許請求の範囲にはそれらの語を特定の実施形態に明示的に限定している。
【０００６】
本発明及び本発明の利点をより完全に理解するために、以下では、添付の図面を参照しながら本発明を説明する。図面において、同一の参照番号は同一の対象を表している。
【図面の簡単な説明】
【０００７】
【図１】本発明によりハイブリッド隠線プロセッサを実施することができる、データ処理システムのブロック図を示す。
【図２Ａ】本発明による図１のデータ処理システムでもって処理することができる、画像の一例を示す。
【図２Ｂ】本発明による図１のデータ処理システムでもって処理することができる、画像の一例を示す。
【図２Ｃ】本発明による図１のデータ処理システムでもって処理することができる、画像の一例を示す。
【図２Ｄ】本発明による図１のデータ処理システムでもって処理することができる、画像の一例を示す。
【図２Ｅ】本発明による図１のデータ処理システムでもって処理することができる、画像の一例を示す。
【図２Ｆ】本発明による図１のデータ処理システムでもって処理することができる、画像の一例を示す。
【図２Ｇ】本発明による図１のデータ処理システムでもって処理することができる、画像の一例を示す。
【図３】本発明による図１のデータ処理システムの一部を示す。
【図４】本発明による図３のハイブリッド隠線プロセッサ及びメモリの詳細を示す。
【図５】本発明によるハイブリッド隠線処理を実施するための方法のフローチャートを示す。
【発明を実施するための形態】
【０００８】
下記において説明する図１から図５、また本明細書における本開示の原理を表すために用いられる種々の実施の形態は単に説明を目的としたものに過ぎず、本発明の範囲を限定するものと解するべきではない。当業者であれば、本開示の原理は適切に構成された任意の装置において実現できることが分かるであろう。以下では、限定を意図したものではない複数の実施例を参照しながら、本発明の多数の革新的な教示について説明する。
【０００９】
三次元物体の二次元画像を生成する際の共通の問題は、隠線（即ち、視野角に起因して隠されて現われるべき線であることから、及び／又は、所定のシーンにおける他の物体によって覆われる線であることから、ユーザが表示したくない線）の識別及び除去に関する。一般的に、隠線を識別する方法は画像空間アルゴリズムか、又は物体空間アルゴリズムのいずれかである。しかしながら、それらの技術はいずれも欠点を有している。
【００１０】
画像空間処理では、デプスバッファ又はＺバッファが使用される。このバッファはスクリーンをピクセルに分割し、それらのピクセルに基づき可視性処理を実行する。一つのピクセル位置に二つ以上の物体が存在する場合には、観察者に最も近い物体の部分に関連するデータが表示画面の生成に使用されるべきであり、従って、そのピクセルにおいて観察者から更に離れた位置にある画像のあらゆる部分は隠される。画像空間処理を使用することにより、比較的高速に画像が生成される。しかしながら、この処理に関する精度は、多くの用途において所望される精度よりも低い。
【００１１】
画像データのファセット表現又は厳密な数学表現を使用するような物体空間処理は、画像空間処理に比べてより高い精度を提供する。しかしながら、比較的大きいアセンブリ（例えば、自動車、船等の全体）を製図するユーザにとって、物体空間技術は画像の表示に非常に長い時間を必要とし、更には過度に大きいメモリフットプリントも必要とする。一般的に、特別な技術によって提供される精度はより高くなるが、その技術に関連して、画像生成はより緩慢になり、またメモリフットプリントは一層大きくなる。
【００１２】
従って、例えば、Ｚバッファは視点（ビュー）にわたり固定の解像度を規定することができる（例えばＸ方向及びＹ方向においてそれぞれ１０００ピクセル）。表示すべき画像をテッセレートすることができ、そのような画像は、物体を表す複数のポリゴン又は複数のファセットが接続されてメッシュを生成することによって、物体のあらゆる曲面の平面近似を提供する。それらのポリゴン及び辺がＺバッファにスキャンされる。スキャン後の各ピクセルの「勝者」は隠線画像に対応する。このＺバッファアルゴリズムは、モデルのサイズの増大に比例して線形性能を有している（即ち、オーダーｎシステム）。そのオーダーに起因して、これは一般的に最も高速なタイプの隠線プロセッサである。更に、ポリゴンに関する必要メモリは、ポリゴンの数が増加しても一定であり、また辺に関する必要メモリは、辺の数の増加に比例して線形である。
【００１３】
しかしながら、Ｚバッファ技術の精度は、視点にわたり配置されているピクセルの数によって制限される（例えば、大きいアセンブリの全域での１０００個のピクセルは比較的少ない）。これは、結果として得られる画像におけるオーバーシュート及びアンダーシュートによって顕著に現われる。また、Ｚバッファピクセルにマッピングするために、全ての座標が整数に丸められる。この丸めはＺバッファ座標における退化及び関連する可視性の欠陥を生じさせる可能性がある。更には、Ｚバッファから辺を抽出することは困難であり、また多角形又は曲線の出力が作図及び注釈のために必要とされる。
【００１４】
物体空間技術を使用するファセット隠線プロセッサは、一般的に、全てのファセット辺セグメントがモデル内の他の全てのファセット辺セグメントと交差することを要求する。これによって一連の辺ピースが生成され、それらの辺ピースは各々一つの可視性を有している。各辺ピースの可視性は、トポロジ、レイキャスティング又は他の幾何学テストによって求められる。物体空間アルゴリズムは、交差候補の数及びレイファイア（Ray Fire）候補の数を考えられる最小数に限定することを試みる。
【００１５】
精密隠線プロセッサを上回る物体空間ファセット隠線プロセッサの利点は、精密曲線を交差させる代わりに、ファセット辺セグメントを交差させるだけで良いことである。ラインセグメントは二つの線であり、従ってそれらの交差は比較的安定している。また、可視性変化点の精度はテッセレーション許容誤差（例えば、１．０Ｅ−０３又は１．０Ｅ−０４モデル単位）によって限定されており、これによってＺバッファから得られる精度よりも遙かに高い精度の画像が得られる。最後に、図面にのせるために辺を容易に利用することができる（即ち、それらの辺は隠線プロセッサの直接的な出力である）。
【００１６】
しかしながら、いずれの物体空間アルゴリズムのオーダーもｎ2である。従って、ファセットアルゴリズムの各交差の質は比較的低いものでありながら、そのアルゴリズムのオーダーは最終的には優位になる。但し、そのようなオーダーによってこの技術はＺバッファアルゴリズムよりも遙かに緩慢になる。その上、あらゆる技術が交差候補の数を限定することを試みているにもかかわらず、その技術のオーダーｎはｎ2のままである。更に、辺が図面にのせられることから、それらの辺はファセット状に現われる。またポリゴンに関する必要メモリは、ポリゴンの数の増加に比例して線形であり、辺に関する必要メモリは辺の数の増加に比例して線形である。
【００１７】
物体空間技術も使用する精密隠線プロセッサは、一般的に、全ての精密辺がモデル内の他の全ての精密辺と交差することを要求する。これによって一連の辺ピースが生成され、それらの辺ピースは各々一つの可視性を有している。各辺ピースの可視性は、トポロジ、レイキャスティング又は他の何らかの幾何学テストによって求められる。精密物体空間アルゴリズムは、交差候補の数及びレイファイア候補の数を考えられる最小数に限定することを試みる。
【００１８】
精密物体空間隠線プロセッサの利点は、モデリング許容誤差（例えば、１．０Ｅ−０５又は１．０Ｅ−０６モデル単位）分に限定されている、可視性変化点に関する精度を提供することであり、これにより、Ｚバッファ又は物体空間ファセット技術のいずれかから得られる精度よりも遙かに高い精度の画像が得られる。更には、図面にのせるために辺及びその精密曲線を容易に利用することができる（即ち、それらは隠線プロセッサの直接的な出力である）。最終的に、精密曲線は製図に使用されるので、それらの辺は現実と同様に平滑且つ正確に現われる。
【００１９】
しかしながら、二つの精密辺間の交差は、二つの一般的な曲線間の交差であり、これは二つの線間の交差に比べて比較的緩慢である。更に、精密物体空間アルゴリズムのオーダーはｎ2である。従って、各交差が比較的時間を消費し、また、最終的には優位になるアルゴリズムのオーダーはｎ2であるので、精密アルゴリズムはＺバッファアルゴリズム又はファセットアルゴリズムよりも遙かに緩慢である。その上、全ての技術が交差候補の数を限定することを試みているにもかかわらず、その技術のオーダーｎはｎ2のままである。更に、サーフェス（surface）に関する必要メモリはサーフェスの数に関して線形であるが、しかしながら各サーフェスは必要メモリに関して比較的費用がかかると考えられる。最後に、辺に関する必要メモリは辺の数の増加に比例して線形である。
【００２０】
従来の隠線処理アルゴリズムを用いる際の限界を克服するために、ファセットアルゴリズムのようにラインセグメント辺を交差させるが、交差する全ての辺ではなく、交差する特定の辺のみを用いる隠線プロセッサが近年開発された。交差すべき辺はＺバッファの使用により識別される。従って、ファセットアルゴリズムのレベルに近いレベルの精度が提供され、その一方で、Ｚバッファアルゴリズムの速度に近いレベルの速度が提供される。高速隠線プロセッサと称されるこの技術はファセットモデルを基礎としている。しかしながら、ソフトウェアＺバッファはポリゴンを記憶するために使用される。この技術は線形性能（即ち、オーダーｎ）を提供する。
【００２１】
高速隠線処理に関して、ポリゴンスキャンコンバージョン（Polygon Scan Conversion）は、ポリゴンの辺が外辺（external edge）の一部である場合には、ピクセルの付注を含む。取得された辺及びポリゴンの情報はＺバッファに記憶される。辺の可視性はソフトウェアＺバッファによってトレースされる。このプロセスは線形性能を有する（即ち、オーダーｎ）。Ｚバッファトレースは、目下の辺が隠されるピクセルを調べることによって、トレースされている辺を隠す可能性があるあらゆる外辺を識別する。これによって高速隠線プロセッサは、従来の物体空間ファセット隠線プロセッサによって要求されるようなｎ2の性能の代わりに、線形性能を用いて全ての辺交差を識別することができる。一つのピクセルの可視性が確認された後に、一つのピクセルにおいて取得された辺は、可視性変化点を、テッセレートされた精密なもの（例えば辺セグメント、辺セグメント交差）へと更に精度を高めるために使用される。
【００２２】
高速隠線プロセッサの利点は、交差すべき辺の線形時間での識別である（即ち、時間は辺の数に基づき一定である）。このことは、全ての交差（即ち各辺と他の全ての辺との交差）を識別するためにｎ2の性能を必要とする大多数の物体空間隠線プロセッサとは対照的である。更にこの技術は、そのオーダーに基づき、またコアプロセッサとしてのソフトウェアＺバッファの使用に基づき、比較的高速な処理技術である。ポリゴンに関する必要メモリは、ポリゴンの数が増加しても一定であり、また形成される交差はファセット辺セグメントの間にあり、それらは二つの線間の交差である。更に、可視性変化点の位置はＺバッファによって検出される。またその位置は単に可視性が変化する交差である。最後に、可視性変化点の精度はテッセレーション許容誤差（例えば、１．０Ｅ−０３又は１．０Ｅ−０４モデル単位）分に限定されており、Ｚバッファから得られる結果と比べて遙かに高く、また図面にのせるために辺を容易に利用することができる（即ち、それらの辺は隠線プロセッサの直接的な出力である）。
【００２３】
しかしながら、高速隠線プロセッサを用いる交差のクリーンアップは辺及びシルエットに関する制限を有している。不正確なＺデプスポリゴンスキャンコンバージョン、並びに、ポリゴンの外辺を取り込むポリゴンの内部に起因して、複数の辺は、それらが本来取得すべきピクセルを取得できないこともしばしば起こる。更に、この技術を用いて生成されるシルエットは一般的に不正確である。何故ならば、それらのシルエットは標準的なファセット処理技術に応じてポリゴンの境界に従うからである。
【００２４】
図１には、本発明によりハイブリッド隠線プロセッサを実施することができる、データ処理システム１００のブロック図が示されている。幾つかの実施の形態では、このデータ処理システム１００を、特にソフトウェアによって構成されているか、又は、本明細書に記載されているプロセスを実行するように構成されている、ＰＤＭシステムとして実施することができる。特定の実施の形態では、データ処理システム１００を、本明細書に記載されているように、複数のシステムを相互に接続して通信を行うものとして実施することもできる。図１に示されているデータ処理システム１００は、レベル２キャッシュ／ブリッジ１０４に接続されているプロセッサ１０２を有しており、またレベル２キャッシュ／ブリッジ１０４はローカルシステムバス１０６に接続されている。ローカルシステムバス１０６は、例えば周辺機器コンポーネントインターコネクト（ＰＣＩ：peripheral component interconnect）で良い。また、図示されている実施例では、メインメモリ１０８及びグラフィックスアダプタ１１０もローカルシステムバスに接続されている。グラフィックスアダプタ１１０をディスプレイ１１１に接続することもできる。
【００２５】
ローカルエリアネットワーク（ＬＡＮ）／ワイドエリアネットワーク（ＷＡＮ）／ワイヤレス（例えばＷｉＦｉ）アダプタ１１２のような他の周辺機器もローカルシステムバス１０６に接続することができる。拡張バスインタフェース１１４は、ローカルシステムバス１０６を入力／出力（Ｉ／Ｏ）バス１１６に接続することができる。Ｉ／Ｏバス１１６にはキーボード／マウスアダプタ１１８、ディスクコントローラ１２０及びＩ／Ｏアダプタ１２２を接続することができる。ディスクコントローラ１２０をストレージ１２６に接続することができる。ストレージ１２６として、（ｉ）読み出し専用メモリ（ＲＯＭ）又は電気的にプログラム可能な消去できる読み出し専用メモリ（ＥＥＰＲＯＭ）のような不揮発性のハードコーディングされたタイプの媒体、（ｉｉ）磁気テープストレージ、（ｉｉｉ）フロッピーディスク、ハードディスクドライブ及びコンパクトディスク読出し専用メモリ（ＣＤ−ＲＯＭ）又はディジタル多目的ディスク（ＤＶＤ）のようなユーザ記録可能なタイプの媒体、並びに、（ｉｖ）他の公知の光学的、電気的又は磁気的なストレージデバイスを含むが、これらに限定されるものではない、任意の適切な機械により使用可能な記憶媒体又は機械読み出し可能な記憶媒体が考えられる。
【００２６】
図示されている実施例において、Ｉ／Ｏバス１１６をオーディオアダプタ１２４にも接続することができ、このオーディオアダプタ１２４を、音再生用のスピーカ（図１には図示せず）に接続することもできる。キーボード／マウスアダプタ１１８を、マウス、トラックボール、トラックポインタ等のようなポインティングデバイス（図１には図示せず）に接続することができる。
【００２７】
当業者であれば、図１に示したハードウェアを特定の実施の形態のために変更できることが分かる。例えば、他の周辺機器、例えば光学ディスクドライブ等も付加的に使用することができるか、又は、図示したハードウェアの代わりに使用することができる。図示の実施例は説明を目的としているに過ぎず、本開示に関するアーキテクチャ上の制限を意図しているものではない。
【００２８】
データ処理システム１００は、グラフィカルユーザインタフェースを使用するオペレーティングシステムを含んでいる。このオペレーティングシステムは、グラフィカルユーザインタフェースに同時に複数のウィンドウを表示することができ、表示されている各ウィンドウは異なるアプリケーション又は同一アプリケーションの異なるインスタンスへのインタフェースを提供する。ユーザはポインティングデバイスを介してグラフィカルユーザインタフェースにおけるカーソルを操作することができる。
【００２９】
商用の種々のオペレーティングシステムの内の一つ、例えばMicrosoft Windows(TM)のヴァージョン（Redmond, Washに位置するMicrosoft社の製品）を、適切に変更されている場合には使用することができる。オペレーティングシステムを、本明細書において説明する本開示に従い修正又は作成することができる。
【００３０】
ＬＡＮ／ＷＡＮ／ワイヤレスアダプタ１１２を（データ処理システム１００の一部ではない）ネットワーク１３０に接続することができ、このネットワーク１３０として、パブリック又はプライベートのあらゆるデータ処理システムネットワーク、又は、それらネットワークの組み合わせが考えられ、例えばインターネットが含まれる。データ処理システム１００はネットワーク１３０を介して（そのデータ処理システム１００の一部ではない）サーバシステム１４０と通信することができる。幾つかの実施の形態では、サーバシステム１４０を別個のデータ処理システムとして実施することもできる。
【００３１】
本発明の一つの実施の形態によれば、データ処理システム１００は、ディスプレイ１１１に送信されるべき画像を生成するためのハイブリッド隠線処理を提供することができる。以下において図３から５と関連させて詳細に説明するように、Ｚバッファ技術に基づき、（ファセット技術において行われる交差のように）交差されるべき比較的小数の辺を識別することによって、画像を処理することができる。従って、Ｚバッファアルゴリズムの速度と同等の速度が、ファセットアルゴリズムの精度と同等の精度と共に提供される。更に、幾つかの実施の形態では、ファセット辺の代わりに精密辺を交差させることができ、それにより、Ｚバッファアルゴリズムの速度と同等の速度と共に、精密アルゴリズムと同等の精度が得られる。
【００３２】
下記において説明するハイブリッド隠線処理によって、正確なポリゴンスキャンコンバージョン、並びに、ポリゴンの内部を取り込むポリゴンの外辺に起因して、複数の辺はそれらが本来取得すべきピクセルを取得する。更に、シルエットはポリゴン辺に基づき生成されるのではなく、頂点法線から生成される。従って、ポリゴンの中心を通ってシルエットを交差させることができ、またシルエットはポリゴンの境界に追従するものよりも精度が高い。
【００３３】
図２Ａから図２Ｇには、本発明によるデータ処理システム１００によって処理することができる種々の画像の例が示されている。これらの例は単に、本開示において使用される種々の項を示しているに過ぎない。図２Ａには、図１のディスプレイ１１１のような二次元ディスプレイ上に三次元画像を表示するプロセスが示されている。二次元ディスプレイは、ｘ軸及びｙ軸によって規定される平面に対応すると考えられる。図示されている例には円錐２０２及びブロック２０４が含まれている。実線は表示することができる線を表しており、その一方で破線は、円錐２０２及びブロック２０４の二次元表示において現わされるべきではない隠線を表している。従って図示されているように、ｘ軸及びｙ軸によって規定される平面を真っ直ぐ見ている観察者の視野では、円錐２０２の手前にブロック２０４が存在している場所では、そのブロック２０４によって円錐２０２の一部が覆い隠されている。一つの可視線及び一つの隠線には、それらのタイプの線の例として参照番号２０８及び２１０がそれぞれ付されている。
【００３４】
例えば、円錐２０２の三次元画像が二次元スクリーン上での表示のために処理されると、図２Ｂに示されているように、円錐２０２がテッセレートされ、テッセレートされた円錐２２０が生成される。従って、表示用の画像処理を開始するために、円錐２０２の曲面を複数のポリゴンのメッシュ又は複数のファセットによって近似させることができる。図２Ｂに示されている、テッセレートされた円錐２２０では、見易くするために、円錐２２０の背面側における隠線は含まれていない。しかしながら、図２Ａのブロック２０４によって隠れる線は、テッセレートされた円錐２２０に表されている。同様に見易くするために、テッセレートされた形態のブロック２０４も示されていない。
【００３５】
この例では、円錐２２０の複数のシルエットの内の一つに参照番号２２２が付されている。このシルエット２２２は、前向きポリゴン及び後向きポリゴンが共有する一つの辺に相当する。従って、シルエット２２２は物体（即ち円錐２０２）の本当の辺ではない。しかしながら、シルエット２２２はｘｙプレートの円錐２０２の観察者にとっての可視線として現われる。下記において更に詳細に説明するように、多くの画像に関する本当の精密シルエットは、前向きポリゴンと後向きポリゴンとの間の辺に正確に沿って置かれる代わりに、シルエットポリゴンとして既知であるポリゴンを通過することになると理解される。
【００３６】
また図２Ｂに示されている実施例において、外辺の内の一つにも参照番号２２４が付されている。実線によって示唆されているので、この辺２２４は可視辺である。隠れシルエットセグメント２２６及び隠れ外辺２２８はそれぞれ破線として示されている。また一つの内辺にも参照番号２３０が付されている。実線として示されているが、内辺は表示される必要はないと解される。何故ならば、それらの内辺は、テッセレートされた物体を構成する複数のポリゴンの辺に相当し、従って、物体の実際の辺又は可視の辺には対応しないからである。
【００３７】
図２Ｃには、テッセレートされた円錐２２０の一部が、その円錐２２０の一部を覆い隠しているテッセレートされたブロック２４０の一部と共に示されている。見易くするために、この図において内辺は省略されている。下記において更に詳細に説明するように、ポリゴンスキャンコンバージョンの間に、外辺が識別される。例えば、ブロック２４０の外辺２４２が識別される。ポリゴンスキャンコンバージョンの終了後に、各外辺がＺバッファを介してトレースされ、それにより可視性変化ピクセルが求められる。従って図示されている例では、可視性変化ピクセル２４６において円錐２２０の辺２４４が隠されるまでその辺２４４をトレースすることができる。ハイブリッド隠線プロセッサは、先行して識別された外辺２４２を可視性変化ピクセル２４６に存在するものとしてリコールすることができる。ハイブリッド隠線プロセッサは続いて、可視性変化点２４８を識別するために、トレースした辺２４４と外辺２４２を交差させる。従って、図２Ｃに示されているように、また下記において更に詳細に説明するように、可視性変化ピクセル２４６は、辺を隠せるピクセルを含んでおり（プレート保護により実際には隠されていない辺が得られる）、また可視性変化点２４８は、その位置において辺が隠される点である。可視性変化ピクセル２４６は可視性変化点２４８よりも精密ではない。しかしながら、図示されている実施の形態では、ピクセル２４６の解像度と点２４８の解像度との差異が強調されていることを示していると理解される。
【００３８】
図２Ｄには三次元円錐２５０が示されている。現行の隠線処理技術を用いた際に考えられる問題を説明するために、円錐２５０の一部と交差している平面２５２が示されている。平面２５２と円錐２５０が交差することにより、円錐２５０の円形の断面２５４が生じる。シルエットの前面側における面の複数のピースに対応する前向きプレート２５６と、シルエットの後面側における面の複数のピースに対応する後向きプレート２５８とを、以下において説明するように、プレート保護を提供するために使用することができる。図２Ｅには、多角形テッセレーションによって近似されている図２Ｄの円形の断面２５４を表す、テッセレートされた断面２６０が示されている。
【００３９】
ハイブリッド隠線プロセッサにおけるＺバッファトレースの精度を改善するための技術が図２Ｅに示されている。この例において、一つのポリゴンの外辺上の一つの点２６８が、隣接するポリゴンの内辺上の一点２７０と同一のｘＺバッファ座標及びｙＺバッファ座標を有している。従って、点２７０は点２６８よりも大きいｚ値を有しているので、標準的な処理を使用して、点２６８と比較して点２７０はピクセルを取得することになる。しかしながら、点２６８は外辺上にあるので、その点２６８がピクセルを取得すべきである。従って、以下において詳細に説明するように、ハイブリッド隠線プロセッサは、外辺点２６８が内辺点２７０の上に表示されることを保証するために、プレート保護を提供する。
【００４０】
図２Ｆ及び図２Ｇには、付加的なプレート保護をどのようにサーフェス２７８及び２８０のような複曲面に提供できるかが示されている。図示されている例では、サーフェス２７８は外辺２８２を有しており、また二つのサーフェス２７８及び２８０はシルエット２８４及びプレートブレーク線２８６を有している。複曲面に関して、シルエット２８４は、前向きプレートと後向きプレートとの間の境界を完全に規定することはできない。従って、それらのサーフェス２７８及び２８０について、シルエット先天２８８を識別することができ、また、プレート間の境界を更に規定する付加的なプレートブレーク線２８６を生成するためにシルエット先天２８８を使用することができる。
【００４１】
図３には、本発明によるデータ処理システム１００の一部３００が示されている。データ処理システム１００は、図３に示したコンポーネントを実現できるタイプのシステムの一例であり、またそれらのコンポーネントは、本開示の範囲から逸脱することなく、適切に設計された他の任意の画像生成システムにおいても実現できると理解される。
【００４２】
図示されている実施の形態では、上述の部分３００は、テッセレータ３０２、メモリ３０４、ハイブリッド隠線プロセッサ３０６及びディスプレイ３０８を含んでいる。幾つかの実施の形態では、汎用プロセッサ、例えば図１のプロセッサ１０２を使用して、テッセレータ３０２及び／又はハイブリッド隠線プロセッサ３０６を実現することができる。メモリ３０４に接続することができるテッセレータ３０２は、表示される三次元物体を表す画像データを受信することができる。幾つかの実施の形態では、テッセレータ３０２は、パス３１０を介してメモリ３０４から画像データを検索することができる。別の実施の形態では、テッセレータ３０２は、データ処理システム１００の（図３には図示していない）別のコンポーネントから画像データを受信することができる。
【００４３】
テッセレータ３０２は精密画像データをテッセレートし、テッセレートされた画像データを生成することができる。テッセレートされた画像データは、表示されるべき物体のテッセレートされたヴァージョンを構成する複数のファセット又はポリゴンを識別することができるデータを含んでいる。例えば、幾つかの実施の形態では、テッセレートされた画像データは、テッセレートされた画像を形成する、複数の三角形又は別の多角形の各頂点の座標を含むことができる。
【００４４】
幾つかの実施の形態では、テッセレータ３０２はテッセレートされた画像データを、パス３１２を介してハイブリッド隠線プロセッサ３０６に供給することができる。しかしながら、別の実施の形態では、テッセレータ３０２はテッセレートされた画像データを、パス３１０を介してメモリ３０４に記憶し、パス３１２を介してハイブリッド隠線プロセッサ３０６にレディ信号を供給し、メモリ３０４にテッセレートされた画像データが存在することを通知することができる。
【００４５】
テッセレータ３０２及びメモリ３０４に接続することができるハイブリッド隠線プロセッサ３０６は、テッセレートされた画像データ又はレディ信号をテッセレータ３０２から受信することができる。テッセレートされた画像データがメモリ３０４に記憶されている実施の形態では、ハイブリッド隠線プロセッサ３０６は、レディ信号に基づき、メモリ３０４からテッセレートされた画像データを検索することができる。しかしながら、本明細書において記載されているように、テッセレートされた画像データを「受信する」とは、データを受動的に受信することも、データを能動的に検索することも含んでいる。
【００４６】
テッセレートされた画像データを受信した後に、ハイブリッド隠線プロセッサ３０６は、テッセレートされた画像データによって表されるポリゴンの辺を識別し、且つ、Ｚバッファアルゴリズムに基づき、交差を行うための辺のサブセットを選択することができる。図４及び図５と関連させて以下においてより詳細に説明するように、ハイブリッド隠線プロセッサ３０６は、ポリゴンの辺に沿って可視性変化ピクセルを識別し、それらの辺を、同様にそれらの可視性変化ピクセルにあるいずれかの外辺と交差させ、その外辺における可視性変化点を求めることができる。またハイブリッド隠線プロセッサ３０６は、頂点法線に基づき正確なシルエットを生成し、Ｚバッファに関して正確なＺデプスポリゴンスキャンコンバージョンを実施し、また、外辺及びシルエットに関してプレート保護を提供することができる。この隠線処理の実施に際し、ハイブリッド隠線プロセッサ３０６は、テッセレートされた画像データに基づき、比較的高速且つ比較的正確に表示データを生成することができる。
【００４７】
ハイブリッド隠線プロセッサ３０６に接続されているディスプレイ３０８は、パス３１６を介してハイブリッド隠線プロセッサ３０６から表示データを受信し、その表示データに基づき、処理された画像をデータ処理システム１００のユーザに表示することができる。別の実施の形態においては、ハイブリッド隠線プロセッサは画像データをプロッタに送信し、ハードコピー紙図面を作成することができる。
【００４８】
図４には、本発明によるハイブリッド隠線プロセッサ３０６及びメモリ３０４が詳細に示されている。幾つかの実施の形態では、汎用プロセッサ、例えば図１のプロセッサ１０２を使用して、ハイブリッド隠線プロセッサ３０６を実現することができる。図示されている実施の形態では、ハイブリッド隠線プロセッサ３０６はシルエット生成器４０２、プレート生成器４０４、ポリゴンスキャンコンバータ４０６、Ｚバッファディバイダ４０８、可視性トレーサ４１０、プレートプロテクタ４１２、辺インターセクタ４１４並びにオプションとしての精密辺トラッカ４１６を含んでいる。また、メモリ３０４はポリゴン４２０、辺４２２、プレート４２４、Ｚバッファ４２６並びにオプションとしての精密辺４２８を含んでいる。
【００４９】
分かり易くするために、それらのコンポーネントは別個のものとして図示されており、またそのようなものとして説明するが、本開示の範囲から逸脱することなく、ハイブリッド隠線プロセッサ３０６のそれらのコンポーネント４０２，４０４，４０６，４０８，４１０，４１２，４１４及び４１６の内の二つ以上のいずれかのコンポーネントを、単一のコンポーネントとして実施することができる。また、コンポーネント４０２，４０４，４０６，４０８，４１０，４１２，４１４及び４１６の内のいずれか一つを、幾つかの実施の形態においては二つ以上のコンポーネントとして実現することもできる。更に、以下の説明においては、テッセレートされた画像データにおいて表されるポリゴンは三角形であるとする。しかしながら、本発明の範囲から逸脱することなく、テッセレートされた画像データは他のタイプの多角形を表すことができると理解される。
【００５０】
シルエット生成器４０２は、テッセレートされた画像データによって表されるポリゴン４２０の頂点の頂点法線に基づき、シルエットを正確に生成することができる。シルエット点は、ポリゴン法線ベクトルと視線ベクトルのドット積が０である場所に生じる。ある一点が後向きポリゴン上にある場合にはドット積は負であり、それに対して、ある一点が前向きポリゴン上にある場合にはドット積は正である。従ってシルエット生成器４０２は、シルエットを生成するために、各ポリゴン４２０に関してポリゴンの三つの頂点の各々において、シルエット関数を実行する。つまり、法線ベクトルと視線ベクトルのドット積が形成される。
【００５１】
シルエット関数に基づき、シルエット生成器４０２は、ポリゴンが前向きポリゴンであるか、又は後向きポリゴンであるかを決定することができる。シルエット生成器４０２が、三つの三角形頂点の各々に関するシルエット関数は負であることを求めると、シルエット生成器４０２はそのポリゴンが後向きポリゴンであることを識別する。従って、そのポリゴンに関してシルエットは存在しない。シルエット生成器４０２は、メモリ３０４のポリゴン４２０部において、そのポリゴンを後向きポリゴンとして分類することができる。
【００５２】
同様に、シルエット生成器４０２が、三つの三角形頂点の各々に関するシルエット関数は正であることを求めると、シルエット生成器４０２はそのポリゴンが前向きポリゴンであることを識別する。従って、そのポリゴンに関してシルエットは存在しない。シルエット生成器４０２は、メモリ３０４のポリゴン４２０部において、そのポリゴンを前向きポリゴンとして分類することができる。
【００５３】
しかしながら、シルエット生成器４０２が、一つの三角形についてのシルエット関数は複合的なものであることを求めると、即ち、三つの三角形頂点の内の一つに関する少なくとも一つのシルエット関数は負であり、且つ、三つの三角形頂点の内の一つに関する少なくとも一つのシルエット関数は正であることを求めると、シルエット生成器４０２はそのポリゴンがシルエットポリゴンであることを識別する。その場合、シルエット生成器４０２は、本当のシルエット点を識別するために、各ポリゴン辺に沿って線形補間を実施することができる。しかしながら、頂点の内の二つに関するシルエット関数は同一の符号を有することになるので、それら二つの頂点を結ぶ辺上にはシルエット点は存在しない。従って、シルエット生成器４０２は、三角形の他の二つの辺に沿って線形補間を実施することができる。このプロセスでは、三角形における二つのシルエット点が識別される。続いて、シルエット生成器４０２は、二つのシルエット点を結ぶことによって、シルエットセグメントを形成することができる。シルエット生成器４０２がシルエットセグメントの形成を終了すると、シルエット生成器４０２は、異なる三角形から形成された複数のシルエットセグメントを結合させ、一つのシルエット辺を生成し、また、メモリ３０４の辺４２２部にシルエット辺を記憶することができる。
【００５４】
幾つかの実施の形態では、シルエット生成器４０２は、精密シルエット辺を生成することができる。例えば、特定のタイプの面に関しては、シルエットの精密タイプが既知である（例えば、球の輪郭は円形である）。それらのタイプの面に関しては、シルエット生成器４０２は、正確なタイプの精密曲線をテッセレートされたシルエットにフィットさせることができる。別のタイプのサーフェスに関しては、シルエット生成器４０２は、テッセレートされた複数のシルエット点を通るように３次Ｂスプライン（cubic B-spline）をフィットさせ、精密シルエット曲線を生成することができる。
【００５５】
図２Ｆ及び図２Ｇのサーフェス２７８及び２８０のような複曲面に関して、シルエット生成器４０２は、それらのサーフェスに関するあらゆるシルエット先点を識別し、そのシルエット先点に基づきプレートブレーク線を生成することもできる。
【００５６】
プレート生成器４０４は、図２Ｄに示されているような、前向きプレート２５６及び後向きプレート２５８のような、前向きプレート及び後向きプレートを生成することができる。幾つかの実施の形態では、プレート生成器４０４は、シルエット生成器４０２によるメモリ３０４のポリゴン４２０部における前向きポリゴンの識別に基づき前向きプレートを生成し、また、シルエット生成器４０２によるメモリ３０４のポリゴン４２０部における後向きポリゴンの識別に基づき後向きプレートを生成することができる。従って、幾つかの実施の形態では、プレート生成器４０４は、メモリ３０４のプレート４２４部に記憶されている前向きプレートに各前向きポリゴンを付加することによって前向きプレートを生成し、また、メモリ３０４のプレート４２４部に記憶されている後向きプレートに各後向きポリゴンを付加することによって後向きプレートを生成することができる。別の実施の形態では、プレート生成器４０４は、メモリ３０４のプレート４２４部に記憶されている所定のプレートに各前向きポリゴンを付加することによって前向きプレートを生成し、また、プレート４２４部に記憶されている前述のプレートに各後向きポリゴンを付加しないことによって後向きプレートを生成することができる。従って、それらの実施の形態では、メモリ３０４のプレート４２４部にポリゴンが存在しないことは、ポリゴンが後向きプレートに由来することを示唆している。図２Ｆ及び図２Ｇのサーフェス２７８及び２８０のような複曲面に関して、プレート生成器４０４は、シルエット生成器４０２によって生成されたプレートブレーク線に基づきプレートを生成することもできる。
【００５７】
ポリゴンスキャンコンバータ４０６は、テッセレートされた画像データによって表されるポリゴン、又はポリゴン４２０をＺバッファ４２６にスキャンコンバージョンすることができる。幾つかの実施の形態では、ポリゴンスキャンコンバータ４０６は、Ｚバッファ可視性マップ（visibility map）における連続関数を形成するために、重心スキャンコンバージョン（barycentric scan conversion）を提供することができる。スキャンコンバージョン中に、ポリゴンスキャンコンバータ４０６はスキャンコンバートされているポリゴン４２０の外辺を識別することができる。幾つかの実施の形態では、ポリゴンスキャンコンバータ４０６は外辺又はシルエット辺の一部であるピクセルを外辺に属するものとしてマークすることによって、外辺識別をＺバッファ４２６に記憶することができる。
【００５８】
Ｚバッファディバイダ４０８は、ポリゴン４２０のプレート４２４への分割をＺバッファ４２６に記憶することができる。従って、Ｚバッファディバイダ４０８は、プレート生成器４０４によって生成されたプレート４２４に基づき、Ｚバッファ４２６を複数の別個の領域、又は、シルエットの同一側にある面の一部に対応するプレートに分割することができる。
【００５９】
可視性トレーサ４１０は、Ｚバッファ４２６を介して各辺をトレースし、トレースした辺が隠されて表されるならば、図２Ｃに示されている可視性変化ピクセル２４６のような可視性変化ピクセルを識別することができる。幾つかの実施の形態では、可視性トレーサ４１０は、Ｚバッファ４２６を介する辺のステッピングによって、トレースした辺はどこで隠されて表されるかを求めることができる。ステッピング処理の間に、可視性トレーサ４１０は、トレースした辺が隠されて表される可視性変化ピクセルとしてのピクセルを識別する。
【００６０】
プレートプロテクタ４１２はプレート保護を実施することができる。幾つかの実施の形態では、プレートプロテクタ４１２は、トレースした辺は同一のプレートに由来するピクセルの後方にあるか否かを確認することによってプレート保護を実施することができる。プレートプロテクタ４１２が、トレースした辺は同一のプレートに由来するピクセルの後方にあることを確認すると、そのトレースした辺は隠れていない。従って、所定の辺と所定のポリゴンが同一のプレートに由来する場合、ポリゴンはＺ値に係わらず辺を隠さない。
【００６１】
辺が実際に隠されている場合には、即ち、プレートプロテクタ４１２が辺はプレート保護に基づき可視であるべきことを確認しない場合には、辺インターセクタ４１４はメモリ３０４のＺバッファ４２６部を検査し、可視性変化ピクセルはポリゴンスキャンコンバージョン中に先行してマークされている外辺を含んでいるか否かを求めることができる。可視性変化ピクセルが外辺を含んでいる場合には、辺インターセクタ４１４はメモリ４２２の辺部から外辺を抽出し、可視性トレーサ４１０によってトレースされている辺と、可視性変化ピクセルに対応するものとして識別された外辺との辺交差を実施することができる。幾つかの実施の形態では、辺交差４１４は、精密辺を交差させることができる。例えば、辺インターセクタ４１４は、単純に一つの線セグメントと一つの線セグメントとを交差させる代わりに、一つの非一様有理Ｂスプライン（ＮＵＲＢＳ：non-uniform rational basis spline）曲線と、一つのＮＵＲＢＳ曲線とを交差させることができる。
【００６２】
ハイブリッド隠線プロセッサ３０６が精密辺トラッカ４１６を含んでいる実施の形態では、この精密辺トラッカ４１６は、メモリ３０４の精密辺４２８部に記憶されている精密辺情報を、ファセット辺情報の代わりに使用することができる。従って、精密辺トラッカ４１６は、より正確な表示データを提供するために、各ポリゴンの各ファセット辺の代わりに、精密辺を使用することができる。ハイブリッド隠線プロセッサ３０６は、上述の処理に基づき、ディスプレイ３０８のための表示データを生成することができる。
【００６３】
幾つかの実施の形態では、単にファセット辺の代わりに精密辺４２８を使用するのではなく、ファセット画像から精密画像への変換をより直接的に実施することができる。それらの実施の形態では、精密辺トラッカ４１６は、ファセットシルエットの精密サーフェスへの投影に基づき、ファセットシルエットを精密シルエットに変換することができる。これを達成するために、ファセットシルエットをそれに関連付けられた精密辺４２８上に投影することができる。ファセットシルエットの内部点を、基礎精密サーフェス上に投影することができる。
【００６４】
更に、精密辺トラッカ４１６は、基礎サーフェスのタイプに応じて、投影された点に精密曲線をフィットさせることができる。例えば、複数の平面に関して、シルエットは存在しない。円筒及び円錐に関して、シルエットに沿って内部点は使用されない。その代わりに、精密辺上に投影されたシルエットの二つの終端点が使用され、それらの二つの終端点の間に線が生成される。球に関しては、投影された、テッセレートされたシルエット点を通るように円弧が生成される。他のタイプのサーフェスに関しては、投影された、テッセレートされたシルエット点を通るように３次スプライン曲線を生成することができる。各タイプの曲線をフィットさせている間、曲線の終端点は、それらの終端点が付されている精密辺上に維持される。
【００６５】
またそれらの実施の形態では、可視性変化点をファセット状のものから精密なものに変換することができる。それらの実施の形態の内の幾つかの実施の形態では、その変換はニュートン・ラフソン（Newton Raphson）階段アルゴリズムを使用して、二つの精密曲線上の可視性変化点の位置を発見する。第１の可視性変化点に関して、この第１の可視性変化点は精密辺の開始位置に明示的に移動される。各内部可視性変化点に関して、現在の可視性変化点が現在の辺上に投影され、初期洗練値が取得される。一方の可視性変化点は、ｔ値を取得するために、投影座標空間において、一方の辺上に投影される。ニュートン・ラフソン階段関数は、２Ｄの可視性変化点を洗練させるために実行される。この洗練された可視性変化点は可視性変化点として使用される。複数の可視性変化点のリストは辺に沿ってバッファされる。
【００６６】
図５には、本明細書に記載されているような一つ又は複数のＰＤＭデータ処理システムによって実行される、本発明によるハイブリッド隠線処理を提供するための方法５００のフローチャートが示されている。この方法５００は、ハイブリッド隠線プロセッサ３０６がテッセレートされた画像データを受信する（ステップ５０２）ことから始まる。幾つかの実施の形態では、ハイブリッド隠線プロセッサは、テッセレートされた画像データをテッセレータ３０２から受信する。別の実施の形態では、ハイブリッド隠線プロセッサ３０６は、テッセレートされた画像データをメモリ３０４から検索する。例えば、ハイブリッド隠線プロセッサ３０６は、テッセレートされた画像データをメモリ３０４のポリゴン４２０部から検索する。以下の記述において、ポリゴン４２０は三角形であるとする。しかしながら、本開示の範囲から逸脱することなく、テッセレートされた画像データは他のタイプの多角形を表すことができると理解される。
【００６７】
シルエット生成器４０２は、複数のポリゴン４２０を分類し、それらのポリゴン４２０の複数の頂点の頂点法線に基づきシルエットを生成する（ステップ５０４）。例えば、シルエット生成器４０２は、各ポリゴン４２０に関してポリゴンの三つの頂点の各々において、シルエット関数を実行することができる。つまり、法線ベクトルと視線ベクトルのドット積を形成することができる。シルエット関数が三つの三角形頂点の各々について負である場合には、シルエット生成器４０２はポリゴンを後向きポリゴンとして識別し、また、そのポリゴンをメモリ３０４のポリゴン４２０部においてそのようなポリゴンとして分類する。シルエット関数が三つの三角形頂点の各々について正である場合には、シルエット生成器４０２はポリゴンを前向きポリゴンとして識別し、また、そのポリゴンをメモリ３０４のポリゴン４２０部においてそのようなポリゴンとして分類する。後向きポリゴン及び前向きポリゴンの両ポリゴンに関して、シルエットは存在しない。
【００６８】
しかしながら、シルエット生成器４０２が、一つの三角形に関するシルエット関数は複合的なものであることを求めると、シルエット生成器４０２は各ポリゴン辺に沿って線形補間を実施し、二つの本当のシルエット点を識別し、また、それら二つのシルエット点を結ぶことによってシルエットセグメントを形成する。複数の頂点の内の二つに関するシルエット関数は同一の符号を有することになるので、それら二つの頂点を結ぶ辺上にはシルエット点は存在しない。従って、シルエット生成器４０２は、残りの二つの辺に沿って線形補間を実施し、本当のシルエット点を識別することができる。シルエット生成器４０２は続いて、複数のシルエットセグメントを結合させてシルエット辺を生成し、そのシルエット辺をメモリ３０４の辺４２２部に記憶する。
【００６９】
幾つかの実施の形態では、シルエット生成器４０２は、既知のタイプの面に関しては、テッセレートされたシルエットに適切なタイプの精密曲線をフィットさせることによって、また、未知のタイプの面に関しては、テッセレートされたシルエット点を通るように３次Ｂスプラインをフィットさせることによって、精密シルエット辺を生成することができる。図２Ｆ及び図２Ｇのサーフェス２７８及び２８０のような複曲面に関して、シルエット生成器４０２は、それらのサーフェスに関するあらゆるシルエット先点を識別し、そのシルエット先点に基づきプレートブレーク線を生成することができる。
【００７０】
プレート生成器４０４は、シルエットの同一側にある面の一部を含むプレートを生成する（ステップ５０６）。幾つかの実施の形態では、プレート生成器４０４は、シルエット生成器４０２によって分類された各前向きポリゴン４２０を前向きプレートに付加することによって前向きプレートを生成し、また、シルエット生成器４０２によって分類された各後向きポリゴン４２０を後向きプレートに付加することによって後向きプレートを生成することができる。図２Ｆ及び図２Ｇのサーフェス２７８及び２８０のような複曲面に関して、プレート生成器４０４は、シルエット生成器４０２によって生成されたプレートブレーク線に基づきプレートを生成することができる。
【００７１】
ポリゴンスキャンコンバータ４０６は、テッセレートされた画像データによって表されるポリゴン、又はポリゴン４２０をＺバッファ４２６にスキャンコンバージョンする（ステップ５０８）。幾つかの実施の形態では、ポリゴンスキャンコンバータ４０６は、Ｚバッファ可視性マップにおける連続関数を形成するために、重心スキャンコンバージョンを実行する。スキャンコンバージョン中に、ポリゴンスキャンコンバータ４０６はポリゴン４２０のシルエット辺及び外辺を識別し、またそれらの辺の一部であるピクセルを、メモリ３０４のＺバッファ４２６部において外辺に属するものとしてマークする（ステップ５１０）。
【００７２】
Ｚバッファディバイダ４０８は、プレート生成器４０４によって生成されたプレート４２４に基づき、Ｚバッファ４２６を複数の別個の領域に分割する（ステップ５１２）。可視性トレーサ４１０は、Ｚバッファ４２６を介して一つの辺の可視性のトレースを開始する（ステップ５１４）。可視性トレーサ４１０は、トレースした辺が隠されて表されることなく、辺のトレースを完了すると（ステップ５１６）、可視性トレーサ４１０はトレースされるべき次の辺を選択し（ステップ５１８）、新たな可視性トレースを開始する（ステップ５１４）。
【００７３】
しかしながら、可視性トレーサ４１０が、トレースした辺は隠されて表されなければならないことを確認すると（ステップ５１６）、可視性トレーサ４１０は可視性変化ピクセルを識別する、即ち、トレースした辺が隠されて表される位置にあるピクセルを識別する（ステップ５２０）。プレートプロテクタ４１２は、トレースした辺が実際に隠されているか否かを検査することによって、ポリゴンよりもシルエット及び辺の方が優先されることを保証するためにプレート保護を実施する。プレートプロテクタ４１２はこの検査を、トレースした辺が同一のプレートに由来するピクセルの後方にあるか否かを確認する（即ち、トレースした辺及び可視性変化ピクセルは、いずれも前向きプレートに由来するか、又はいずれも後向きプレートに由来するかを確認する）ことによって行う（ステップ５２２）。
【００７４】
プレートプロテクタ４１２が、トレースした辺は同一のプレートに由来するピクセルの後方にあることを確認すると（ステップ５２２）、プレートプロテクタ４１２はトレースした辺が実際のところは隠されておらず、表示されるべきことを確認する。従って、辺及びポリゴンが同一のプレートに由来している場合には、ポリゴンはその辺を隠さない。可視性トレーサ４１０は続いて、先行して識別された可視性変化ピクセルの後方にある辺を隠すことなく辺のトレースを継続する（ステップ５１４）。しかしながら、プレートプロテクタ４１２が、トレースした辺は異なるプレートに由来するピクセルの後方にあることを確認すると（ステップ５２２）、辺インターセクタ４１４は、可視性変化ピクセルは外辺の一部であるか否かを確認する（ステップ５２４）。辺インターセクタ４１４が、可視性変化ピクセルは、ステップ５１０においてポリゴンスキャンコンバータ４０６によってマークされたような外辺の一部ではないことを確認すると（ステップ５２４）、可視性トレーサ４１０は単にその辺をピクセル位置において隠される辺としてマークし、続いてその辺のトレースを継続する（ステップ５１４）。
【００７５】
しかしながら、辺インターセクタ４１４が、可視性変化ピクセルは、ステップ５１０においてポリゴンスキャンコンバータ４０６によってマークされたような外辺の一部であることを確認すると（ステップ５２４）、辺インターセクタ４１４はトレースした辺と、可視性変化ピクセルが一部をなしている外辺とを交差させ、可視性変化点を識別する（ステップ５２６）。幾つかの実施の形態では、辺インターセクタ４１４はファセット辺、即ち線セグメントを交差させることができる。他の実施の形態では、辺インターセクタ４１４は、精密辺、例えばＮＵＲＢＳ曲線を交差させることができる。
【００７６】
ハイブリッド隠線プロセッサ３０６が精密辺トラッカ４１６を含んでいる実施の形態では、精密辺トラッカ４１６は必要に応じて、メモリ３０４の精密辺４２８部に記憶されている精密辺情報をファセット辺情報の代わりに使用することができる（オプションステップ５２８）。
【００７７】
トレースされるべき付加的な辺が残存している場合（ステップ５３０）、次の辺が選択され（ステップ５１８）、可視性トレーサ４１０は次の辺のトレースを開始する（ステップ５１４）。しかしながら、トレースすべき辺が残存していない場合（ステップ５３０）、ハイブリッド隠線プロセッサ３０６は、上述の処理技術に基づきディスプレイ３０８用の表示データを生成し、またディスプレイ３０８はその表示データに基づき、処理された画像データを表示する（ステップ５３２）。表示データを生成するために全ての辺がトレースされるまで待機するのではなく、それらの辺をトレースしながら、ハイブリッド隠線プロセッサ３０６はディスプレイ３０８用の表示データを生成することができると理解される。
【００７８】
このようにして、より正確且つ高速な隠線処理技術が提供される。例えば、プレート保護の実施は、シルエット辺を含む辺はポリゴンの内部によって隠されないことを保証する。隠されない辺を、二次的なエラー除去を実施するために使用することができる。正確なシルエットは頂点法線から生成され、また、ポリゴン辺を基礎とする不正確なシルエットとは異なり、ポリゴンの中心に正確に交差させることができる。更に、Ｚバッファステッピングとは異なり、重心スキャンコンバージョンが実施される場合には、より正確なポリゴンスキャンコンバージョンが提供される。最後に、精密に洗練されたものを提供する実施の形態では、精密シルエットを、ファセットシルエット及び既知の精密サーフェスタイプから生成することができ、また、線セグメント交差を精密辺交差に置換し、より正確な結果を提供することができる。
【００７９】
当業者であれば、一連の動作によって特別に指示または要求されない限り、上述の処理における特定のステップを省略できるか、又は、組み合わせることができるか、又は、同時に若しくは連続的に実行できるか、又は、異なる順序で実行できることが分かる。上述の種々の実施例の種々の処理並びに構成要素を本開示の範囲内で組み合わせることができる。
【００８０】
当業者であれば、簡単且つ明瞭にするために、本開示の使用に適しているあらゆるデータ処理システムの完全な構造及び動作は本明細書において記述又は説明していないことが分かる。その代わりに、本開示に固有のデータ処理システム又は本開示の理解のために必要なデータ処理システムのみを図示及び説明している。データ処理システム１００のその他の部分の構造及び動作は、当業者には公知である現行の種々の実施の形態並びに実践に従うもので良い。
【００８１】
本開示には完全に機能的なシステムの文脈での記述が含まれているが、当業者であれば、本発明のメカニズムの少なくとも一部は種々の任意の形態の機械使用可能、コンピュータ使用可能又はコンピュータ読み取り可読な媒体に記録された命令の形態で配布できること、また本発明はその配布を実際に実行するために使用される特定のタイプの命令又は信号が記録されている媒体又は記憶媒体に関係なく同様に適用されることを理解するであろうということを言及することは重要である。機械使用可能／機械読み出し可能又はコンピュータ使用可能／コンピュータ読み出し可能な媒体の例には、不揮発のハードコーディングタイプの媒体、例えば読み出し専用メモリ（ＲＯＭ）又は電気的に消去及びプログラミング可能な読み出し専用メモリ（ＥＥＰＲＯＭ）及びユーザ記録可能なタイプの媒体、例えばフロッピーディスク、ハードディスクドライブ及びコンパクトディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）又はディジタル多目的ディスク（ＤＶＤ）が含まれる。
【符号の説明】
【００８２】
１００  データ処理システム
１０２  プロセッサ
１０４  キャッシュ／ブリッジ
１０６  ローカルシステムバス
１０８  メインメモリ
１１０  グラフィックスアダプタ
１１１  ディスプレイ
１１２  ローカルエリアネットワーク／ワイドエリアネットワーク／ワイヤレスアダプタ
１１４  拡張バスインタフェース
１１６  入力／出力バス
１１８  キーボード／マウスアダプタ
１２０  ディスクコントローラ
１２２  Ｉ／Ｏアダプタ
１２４  オーディオアダプタ
１３０  ネットワーク
１４０  サーバシステム
２０２  円錐
２０４  ブロック
２０８  可視線
２１０  隠線
２２０  テッセレートされた円錐
２２２  シルエット
２２４  可視の外辺
２２６  隠れシルエットセグメント
２２８  隠れ外辺
２３０  内辺
２４０  テッセレートされたブロック
２４２  外辺
２４４  辺、トレースした辺
２４６  可視性変化ピクセル
２４８  可視性変化点
２５０  三次元円錐
２５２  平面
２５４  円形の断面
２５６  前向きプレート
２５８  後向きプレート
２６０  テッセレートされた断面
２６８  点、外辺点
２７０  点、内辺点
２７８  サーフェス
２８０  サーフェス
２８２  外辺
２８４  シルエット
２８６  プレートブレーク線
２８８  シルエット先点
３００  データ処理システム１００の一部
３０２  テッセレータ
３０４  メモリ
３０６  隠線プロセッサ、ハイブリッド隠線プロセッサ
３０８  ディスプレイ
３１０  パス
３１２  パス
３１４  パス
３１６  パス
４０２  シルエット生成器
４０４  プレート生成器
４０６  ポリゴンスキャンコンバータ
４０８  Ｚバッファディバイダ
４１０  可視性トレーサ
４１２  プレートプロテクタ
４１４  辺インターセクタ
４１６  精密辺トラッカ
４２０  ポリゴン部
４２２  辺部
４２４  プレート部
４２６  Ｚバッファ
４２２  精密辺部
５００  方法
５０２  テッセレートされた画像データを受信するステップ
５０４  ポリゴンを分類し、シルエットを生成するステップ
５０６  プレートを生成するステップ
５０８  ポリゴンスキャンコンバージョンを実行するステップ
５１０  外辺におけるピクセルをマークするステップ
５１２  プレートに基づきＺバッファを分割するステップ
５１４  辺の可視性をトレースするステップ
５１６  トレースした辺は隠されて表されるかを確認するステップ
５１８  次の辺を選択するステップ
５２０  可視性変化ピクセルを識別するステップ
５２２  可視性変化ピクセルはトレースした辺と同一のプレートに由来するか否かを確認するステップ
５２４  可視性変化ピクセルは外辺の一部であるかを確認するステップ
５２６  可視性変化点を識別するために、トレースした辺と外辺を交差させるステップ
５２８  精密辺を使用して精密モデルに変換するステップ
５３０  付加的な辺が残存するかを確認するステップ
５３２  処理された画像を表示するステップ
ＡＳＩＣ  特定用途向け集積回路
ＣＡＤ  コンピュータ支援設計
Ｉ／Ｏ  入力／出力
ＬＡＮ  ローカルエリアネットワーク
ＰＣＩ  周辺機器コンポーネントインターコネクト
ＰＤＭ  製品情報管理
ＰＬＭ  製品ライフサイクル管理
ＷＡＮ  ワイドエリアネットワーク
【図１】
0006038158.tif 000002
【図２Ａ】
0006038158.tif 000003
【図２Ｂ】
0006038158.tif 000004
【図２Ｃ】
0006038158.tif 000005
【図２Ｄ】
0006038158.tif 000006
【図２Ｅ】
0006038158.tif 000007
【図２Ｆ】
0006038158.tif 000008
【図２Ｇ】
0006038158.tif 000009
【図３】
0006038158.tif 000010
【図４】
0006038158.tif 000011
【図５】
0006038158.tif 000012