(57)【特許請求の範囲】
【請求項１】
プリミティブを画面空間のピクセル位置に変換するように構成される階層的タイラーを備える装置であって、それぞれのピクセル位置は、画面空間のx座標およびy座標によって規定され、それぞれのプリミティブは、複数の頂点を有し、それぞれの頂点は、画面空間のx座標およびy座標によって規定され、上記階層的タイラーは、上記画面空間を複数の領域に細分し、それぞれの領域は、上記画面空間の複数のピクセル位置に対応し、上記階層的タイラーは、上記複数の領域のうちの特定の１つが、完全に上記プリミティブの外にあるか、完全に上記プリミティブの中にあるか、または部分的に上記プリミティブの中にあるか判断し、上記階層的タイラーが、特定の領域または領域をさらに細分した特定のサブ領域は完全に上記プリミティブの中にあると判断する場合、上記階層的タイラーは、当該特定の領域または特定のサブ領域を画面空間のピクセル位置に変換し、上記階層的タイラーにおいて生成されたピクセル情報の２次元領域をフレームバッファに送り、上記階層的タイラーが、プリミティブに対応する画面空間のピクセル位置を求めるように上記２次元領域の走査変換を実行する装置。
【請求項２】
走査変換を実施する方法であって、
それぞれの頂点が、画面空間のx座標およびy座標によって規定される複数の頂点を持つ、走査変換されるプリミティブを獲得するステップと、
画面空間を、それぞれの領域が画面空間の複数のピクセル位置に対応する複数の領域に細分するステップと、
上記複数の領域のうち特定の１つが、完全に上記プリミティブの外にあるか、完全に上記プリミティブの中にあるか、または部分的に上記プリミティブの中にあるかを判断するステップと、
特定の領域または領域をさらに細分した特定のサブ領域が完全に上記プリミティブの中にあると判断される場合、特定の領域または特定のサブ領域を画面空間のピクセル位置に変換するステップであって、画面空間は、表示モニタ上のピクセル位置のxおよびy座標に対応し、上記変換は特定の２次元領域上にピクセルを生成するステップと、を含む方法。
【請求項３】
上記階層的タイラーは、特定の領域が部分的に上記プリミティブの中にあると判断した場合に、特定の領域を、それぞれが画面空間の複数のピクセル位置からなるサブ領域に細分し、上記階層的タイラーは、サブ領域の特定の１つが完全に上記プリミティブの外にあるか、完全に上記プリミティブの中にあるか、または部分的に上記プリミティブの中にあるか判断し、部分的に上記プリミティブの中にあるサブ領域が存在する限り、ピクセルレベルに至るまでさらに細分する、請求項１に記載の装置。
【請求項４】
特定の領域が部分的に上記プリミティブの中にあると判断した場合に、特定の領域を、それぞれが画面空間の複数のピクセル位置からなるサブ領域に細分するステップと、
サブ領域の特定の１つが完全に上記プリミティブの外にあるか、完全に上記プリミティブの中にあるか、または部分的に上記プリミティブの中にあるか判断するステップと、
部分的に上記プリミティブの中にあるサブ領域が存在する限り、ピクセルレベルに至るまでさらに細分するステップと、をさらに含む請求項２に記載の方法。
【請求項５】
上記階層的タイラーは、特定の領域が部分的に上記プリミティブの中にあると判断した場合に、特定の領域を、それぞれが画面空間の複数のピクセル位置からなるサブ領域に細分する請求項１に記載の装置。
【請求項６】
特定の領域が部分的に上記プリミティブの中にあると判断した場合に、特定の領域を、それぞれが画面空間の複数のピクセル位置からなるサブ領域に細分するステップをさらに含む請求項２に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、コンピュータグラフィクス表示システムに関連し、特に、コンピュータグラフィクス表示システムで走査変換を実施するための方法および装置に関する。
【０００２】
【従来の技術】
３次元(3-D)のコンピュータグラフィクス表示システムで、プリミティブ(基本立体)は、コンピュータグラフィックス表示システムの表示装置上にレンダリングされ、ビジュアル画像を表示装置上に生成する。それぞれのプリミティブは、プリミティブのX,YおよびZ値、プリミティブの頂点の法線、並びに頂点の色によって規定される。Zピラミッド記憶素子すなわちZバッファを利用してプリミティブのオクルージョン(occlusion:隠れた部分)を検査するコンピュータグラフィックス表示システムが提案されている。例えば、そのようなシステムは、Greene他による「Hierarchical Z-Buffer Visibility」(SIGGRAPH 93,Anaheim,California,1-6 August 1993)という表題の論文の中に提案されており、そのシステムは、Zピラミッド記憶素子すなわちZバッファを使用してプリミティブのオクルージョンについて検査する。
【０００３】
Greene他によって提案されたシステムで、Zバッファは、Z値のピラミッドとして構成されるデータ構造の中の現在のピクセル・フレームに関するZ値を記憶する。ピラミッド内のこれらのZ値は、新しいZ値を検査するために階層的タイラー(tiler：タイル化する手段)内で利用され、新しいZ値に関連する各プリミティブが隠れている(occluded)かどうか判断する。プリミティブが隠れていると判明する場合、隠れているプリミティブは、表示装置上に表示されるべきではないので、プリミティブをピクセルに走査変換する必要はない。なぜなら、隠れているプリミティブが表示されると、隠れているプリミティブは、表示装置上にレンダリングされる画像の中で、隠れているプリミティブの前にあると思われる別のプリミティブを覆ってしまうからである。
【０００４】
Greene他による論文は、元のZバッファからZピラミッドを組み立て、そのZピラミッドを使用して、オクルージョンつみ取り(occlusion culling)のために複数のプリミティブからなる立方体を検査する。この方法は、その面すべてが隠れた多角形に対応する場合、立方体はZバッファに関して隠れているという考えを利用する。
【０００５】
この比較を実施する前に、Zピラミッドは、ピラミッドの底面としてピクセルレベルのZ値から開始し、隣接するZ値のサブグループを比較し、それぞれのサブグループについて最大Z値を求めることによって構築される。そのサブグループの最大Z値は、ピラミッド内の次に高いレベルについてZバッファに記憶される。例えば、比較が始まるとき、64個のZ値がZバッファに含まれている場合、ピラミッド内の次に高いレベルは、16個のZ値を含む。それら16個のZ値はそれぞれ、その下位のレベルの中の対応するサブグループ内で比較された４個のピクセルの最大Z値に対応する。
【０００６】
この次に高いレベルの中で、４つの隣接するZ値のそれぞれのサブグループのZ値を比較してそれぞれのサブグループの最大Z値を求め、この最大Z値は、ピラミッド内の次に高いレベルのためにZバッファに記憶される。従って、ピラミッド内の次に高いレベルについて、Zバッファは４つのZ値を含む。これら４つのZ値を比較して最大Z値を求め、それは、ピラミッド内の次に高いレベルのためにZバッファに記憶される。この最後の最大Z値は、ピラミッドの頂上に対応する。
【０００７】
Greene他によって提案されたコンピュータグラフィックス表示システムで、Zピラミッドが構築されると、立方体の面を形成するプリミティブのZ値は、ピラミッドの特定のレベルから始まってピラミッドの底面に向かって下りながら比較される。それぞれのプリミティブについて、プリミティブの最小Z値は、ピラミッドのレベルに対して上から下へと順に検査される。プリミティブの最小Z値がピラミッドZ値より大きい場合、プリミティブは完全に隠れている。立方体の面を形成するプリミティブすべてが隠れている場合、その立方体は隠れており、捨てることができる。そうでない場合、立方体が完全に隠れるまで、または、プリミティブが少なくとも部分的に見えると判明するZピラミッド内のレベルに達するまで、プロセスは、ピラミッドのそれぞれのレベルで続行する。立方体の１つの面に対応するプリミティブが、少なくとも部分的に見えると判明する場合、立方体全体は、典型的な走査変換プロセスを使用してピクセルに走査変換される。
【０００８】
走査変換は、プリミティブに対応する表示装置の画面上の正確なピクセル位置を求めるプロセスである。走査変換は通常、辺ステッパ・エンジンによって実施される。この辺ステッパ・エンジンは、プリミティブが走査線と交差するところのプリミティブの辺上の点に達するまで、プリミティブの辺に沿ってステップダウンし、走査線に対応するスパンを横切ってステップする。このようにして、走査線がプリミティブと交差するプリミティブの反対側の点を求める。
【０００９】
【発明が解決しようとする課題】
走査変換を実施する典型的な方法の１つの不利益は、典型的な方法がピクセルレベルで開始ピクセル位置で始まるということである。この開始ピクセル位置は、それぞれのスパンについて、ホスト中央処理装置(CPU)またはコンピュータグラフィックス表示システムの幾何学アクセラレータによって求めなければならない。それぞれのスパンについて開始ピクセル位置およびその開始ピクセル位置に関連するパラメータを求めることは、数学上、集約的なプロセスである。特定のスパンについて開始ピクセル位置およびそれに関連するパラメータが求められると、辺ステッパは、上述した方法でプリミティブを横断してステップする。
【００１０】
走査変換の典型的な方法の別の不利益は、次のピクセルスパンが次の走査線について取得される前に、ピクセルのスパン全体がx方向(すなわち水平)の走査線について得られる方法により、それがピクセルの１次元の所在(locality)を生じることである。これは、ピクセルの１次元グループすなわち画面空間のx次元に関するグループを生成し、フレーム・バッファ・メモリ内のピクセルの構成と記憶を容易にしない。ピクセルがフレーム・バッファ・メモリから読み出されて表示モニタに送り出される速度を最大限にするために、フレーム・バッファ・メモリ内のピクセルを、２次元の所在をもつグループに分ける、すなわち画面空間のxおよびy次元に関してグループ化することが望ましい。
【００１１】
それぞれのスパンの開始ピクセル位置を判断する必要性を排除して走査変換プロセスを単純化する走査変換プロセスを利用することが有利である。Zピラミッドの階層を活用するために、走査変換プロセスを、階層的タイラーの中で実施されるオクルージョン検査プロセスに結びつけることも有利である。これは、オクルージョン検査プロセスと走査変換プロセスが階層的タイラーの中で同時に実施されることを可能にし、従ってコンピュータグラフィクス表示システムの包括的な処理能力を大幅に高めることができる。また、プリミティブを、画面空間のxおよびy次元に関してグループ化されるピクセルに走査変換する走査変換プロセスを利用することも有利である。
【００１２】
従って、走査変換を実施するための改善された方法および装置が必要とされている。さらに、オクルージョン検査と同時に階層的タイラーの中で実施される走査変換プロセスも必要とされている。
【００１３】
【課題を解決するための手段】
この発明は、コンピュータ画像表示システムの中で、走査変換中のプリミティブに対応する画面空間内のピクセル位置を求めるように走査変換を実施する方法および装置を提供する。画面空間は、コンピュータグラフィックス表示システムの表示モニタ上のピクセル位置のxおよびy座標に対応する。この発明の装置は、プリミティブを画面空間のピクセル位置に変換するよう構成される論理を含み、その中で、それぞれのピクセル位置は、画面空間のx座標およびy座標によって規定される。それぞれのプリミティブは、複数の頂点をもち、それぞれの頂点は、画面空間のx座標およびy座標によって規定される。
【００１４】
階層的タイラーとして以下で言及される論理は、画面空間を、それぞれが画面空間の複数のピクセル位置を含む複数の領域に細分する。階層的タイラーは、領域のうちの特定の１つが完全にプリミティブの外にあるか、完全にプリミティブの中にあるか、または部分的にプリミティブの中にあるか判断する。階層的タイラーは、特定の領域が完全にプリミティブの中にあると判断する場合、特定の領域を画面空間のピクセル位置に変換する。階層的タイラーは、特定の領域が部分的にプリミティブの中にあると判断する場合、その特定の領域を複数の部分領域（サブ領域）に細分する。それぞれの部分領域は、画面空間の複数のピクセル位置からなる。階層的タイラーは、複数の部分領域のうちの特定の１つが完全にプリミティブの外にあるか、完全にプリミティブの中にあるか、または部分的にプリミティブの中にあるかを判断する。階層的タイラーは、特定の部分領域が完全にプリミティブの中にあると判断する場合、その特定の部分領域を画面空間のピクセル位置に変換する。
【００１５】
階層的タイラーは、特定の領域または部分領域が完全にプリミティブの外にあるわけではないと判断した後にのみ、特定の領域または部分領域が完全にプリミティブの中にあるかどうか判断することが好ましい。階層的タイラーは、特定の領域または部分領域が完全にプリミティブの中にあるわけではないと判断した後にのみ、特定の領域または部分領域が部分的にプリミティブの中にあるかどうか判断することが好ましい。
【００１６】
この発明の好ましい実施例に従って、階層的タイラーは、オクルージョン検査に関連して走査変換を実施する。この発明の代替実施例に従って、この発明の走査変換プロセスは、オクルージョン検査から独立して実施される完全に単独のプロセスである。この発明の好ましい実施例に従って、階層的タイラーは、特定の領域が完全に特定のプリミティブの中にあると判断するとき、特定の領域をピクセル位置に変換する前に、特定のプリミティブが隠れているかどうかどうか判断する。階層的タイラーが特定のプリミティブは隠れていないと判断する場合のみ、特定の領域は、画面空間内のピクセル位置に変換される。
【００１７】
階層的タイラーは、特定の領域が部分的に特定のプリミティブの中にあると判断するとき、特定のプリミティブが隠れているかどうか判断する。特定のプリミティブは隠れていないと階層的タイラーが判断する場合、階層的タイラーは、部分的に特定のプリミティブの中にあると判明した特定の領域を、複数の部分領域に細分する。それぞれの部分領域は、画面空間の複数のピクセル位置からなる。階層的タイラーは、部分領域のうちの特定の１つが完全に特定のプリミティブの外にあるか、完全に特定のプリミティブの中にあるか、または部分的に特定のプリミティブの中にあるか、を判断する。
【００１８】
階層的タイラーは、特定の部分領域が完全に特定のプリミティブの中にあると判断する場合、特定のプリミティブが隠れているかどうか判断する。階層的タイラーは、特定のプリミティブが隠れていないと判断すると、特定のプリミティブの中にあると判断された特定の部分領域を画面空間のピクセル位置に変換する。ピクセルは、コンピュータグラフィックス表示システムのグラフィックスパイプラインの中の更なる処理のために下流に送り出される。階層的タイラーは、特定の部分領域が部分的に特定のプリミティブの中にあると判断する場合、特定のプリミティブが隠れているかどうか判断する。
【００１９】
特定のプリミティブは隠れていないと階層的タイラーが判断する場合、階層的タイラーは、特定の部分領域を、複数のより小さい部分領域に細分する。より小さい部分領域はそれぞれ、画面空間の複数のピクセル位置からなる。階層的タイラーは、これらのより小さい部分領域のうちの特定の１つが、完全に特定のプリミティブの外にあるか、完全にその特定のプリミティブの中にあるか、または部分的に特定のプリミティブの中にあるか、判断する。プロセスは、領域または部分領域がプリミティブの中に完全にまたは部分的に含まれると判明し、ピクセルに変換されるまで、あるいは、ピクセルレベルに達するまでこのように続行する。
【００２０】
この発明の上述および他の利点および特徴は、以下の説明および図面から明らかになるであろう。
【００２１】
【発明の実施の形態】
上述したように、この発明の好ましい実施例に従って、この発明の走査変換プロセスは、プリミティブが階層的タイラー内でオクルージョンについて検査されるとき、コンピュータグラフィクス表示システムの階層的タイラー内で実施される。この発明の好ましい実施例に従って、プリミティブをオクルージョンについて検査するために使用されるZピラミッド型データ構造は、プリミティブがコンピュータグラフィクス表示システムのグラフィックスパイプラインを通って処理されているとき、「進行中」に更新される。従って、まずこの発明の階層的タイラー、それを使用してオクルージョン検査を実施する方法、およびZピラミッドデータ構造が進行中に更新される方法について詳しく説明する。
【００２２】
この発明のオクルージョン検査方法を詳しく説明した後、この発明の走査変換プロセス、およびオクルージョン検査に関連して階層的タイラー内でこの発明の走査変換プロセスが実施される方法について詳述する。しかし、当業者であれば、この発明の走査変換プロセスは、オクルージョン検査に関連して実施されなくてもよいことが分かるであろう。
【００２３】
図1は、好ましい実施例に従うこの発明のグラフィックスシステム20を含むコンピュータグラフィクス表示システム10のブロック図である。コンピュータグラフィクス表示システム10は、ホストCPU12、ホスト記憶装置14、ローカルバス18、入力/出力(I/O)制御装置25、I/Oバス16、グラフィックスシステム20、およびグラフィックスシステム20から出力されるグラフィクス情報を表示するためのモニタ21を含む。
【００２４】
ホストCPU12は、コンピュータグラフィクス表示システム10のコンソール(図示せず)から受け取った入力を処理し、ローカルバス18を通してI/Oインタフェース・コントローラ25にコマンドおよびデータを出力する。I/Oインタフェース・コントローラ25は、I/Oバス16のプロトコルを利用して、コマンドおよびデータをフォーマットする。I/Oバス16を通して受信された情報は、グラフィックスシステム20に入る。グラフィックスシステム20は、この情報を処理してモニタ21上にグラフィクス画像を表示させる。
【００２５】
図2は、好ましい実施例に従うこの発明のグラフィックスシステム20のブロック図である。ホストインタフェース・ユニット(HIU)32は、I/Oバス16を通してホスト・メモリ14から、コマンド・データパケットおよびテクスチャ・マップをフェッチする。ホストインタフェース・ユニット32は、グラフィクス2D情報を2Dマクロ機能ユニット(MFU)34に、3D情報を3Dマクロ機能ユニット(MFU)36に提供する。2Dマクロ機能ユニット34は、2Dベクトル、テキスト、および矩形スパンを生成する。3Dマクロ機能ユニット36は、図3に関して以下で詳述するように、三角形セットアップ、3Dラスター化、およびテクスチャ・マッピングを実施する。さらに3D MFU36は、図3ないし図8に関して以下で詳述するように、この発明に従ってオクルージョン検査を実施することが好ましい。さらに、3D MFU36は、図9および図10に関して後述するように、この発明の方法に従って走査変換を実施することが好ましい。
【００２６】
2Dマクロ機能ユニット34および3Dマクロ機能ユニット36からの出力は、オブジェクト機能ユニット(OFU)38によって受け取られる。オブジェクト機能ユニット38は、矩形クリッピング、パターニング、フレームバッファからフレームバッファへのブロック転送、および矩形スパン充てんを実施する。オブジェクト機能ユニット38の出力は、フレームバッファ・コントローラ(FBC)40によって受け取られる。フレームバッファ・コントローラ40は、要求をメモリ・コントローラ(MC)41にディスパッチし、メモリ・コントローラ41が、ピクセルカラーおよびZ座標をRAM45に書き込みまたはそこから読み取るようにする。さらに、フレームバッファ・コントローラ40は、ディスプレイ・コントローラ43に送り出される表示情報をフェッチする。ディスプレイ・コントローラ43は、表示情報を受け取り、それを赤、緑および青(RGB)のアナログデータに変換し、表示モニタ21に送り出す。
【００２７】
この発明の好ましい実施例に従うオクルージョン検査
図3は、図2に示す3Dマクロ機能ユニット36のブロック図である。3Dマクロ機能ユニット36のセットアップ・ユニット55は、多角形の頂点のX,Y値を使用することによって、多角形の平面方程式を準備する。これを実現する方法は図11に関して以下に詳述する。図4Aないし図8に関して以下に詳述するが、頂点のZ値がセットアップ・ユニット55によって使用され、それぞれの多角形の最小および最大Z値を判断する。それぞれの多角形の最小および最大Z値は、階層的タイラー57に出力される。階層的タイラー57は、進行中に、すなわち多角形がグラフィックスパイプラインを通して処理されているとき、Zピラミッドを組み立てる。階層的タイラー57は、セットアップ・ユニット55から受け取った多角形の最小および最大Z値を使用してオクルージョン検査を実施することが好ましい。また、階層的タイラー57は、図4Aないし図8に関して以下で詳述するように、この発明に従ってカバレージ・マスクを生成し維持してZピラミッドを更新する。
【００２８】
階層的タイラー57は、それぞれの可視プリミティブについてXおよびY値を生成し、そのXおよびY値をパラメータ補間器58に提供する。パラメータ補間器58は、受け取ったそれぞれのXおよびY値について、ピクセルレベルの正確なZ値を計算する。
【００２９】
正確なZ値は、ピクセルZ比較成分61に与えられる。ピクセルZ比較成分61は、フレームバッファ・コントローラ40のメモリコントローラ41によって、どの値がRAM45内のZバッファメモリに書き込まれる必要があるかをピクセルレベルで判断する。このピクセルレベルのZ比較検査を実施するために、3Dマクロ機能ユニット36は、RAM45に含まれるZバッファメモリから得られるZ値を記憶するピクセルレベルのZバッファメモリ66を含むことが好ましい。ピクセルZ比較成分61は、これらのZ値を使用してピクセルレベルのZ比較検査を実施する。
【００３０】
概して、ピクセルレベルのZ比較検査は、パラメータ補間器58によって生成されたZ値とフレーム・バッファ・メモリに記憶された一群のZ値を比較し、パラメータ補間器58によって生成されたZ値がZバッファメモリに記憶される必要があるか、すなわち、Z値に対応するピクセルが隠れているかどうか判断する。RAM45内のZバッファメモリに記憶されるピクセルレベルのZ値は、オブジェクト機能ユニット38に出力される。オブジェクト機能ユニット38は、矩形クリッピング、パターニング、フレームバッファからフレームバッファへのブロック転送、矩形スパン充てん等のタスクを実施する。
【００３１】
図4Aないし図4Dは、Zピラミッド記憶素子63に記憶され、この発明のオクルージョン検査方法に従ってオクルージョン検査に使用されるZピラミッド・データ構造の多様なレベルを示す。図4Aは、Zピラミッドの底面レベルを表し、図4Bないし図4Dは、ピラミッドのそれに続く高いレベルを表し、図4Dは、ピラミッドの最上レベルを表す。図示および説明を分かり易くするため、Zピラミッドの底面レベルは、図4Aの中で64個のZ値73を含むように表されており、それらは、隣接するZ値の16個の部分領域にグループ化され、それぞれ部分領域は４つのZ値をもつ。それぞれの部分領域76のそれぞれの４つの隣接するZ値を比較して、それぞれの部分領域の最大Z値を判断する。
【００３２】
それぞれの部分領域の最大Z値は、図4Bの中で数字81によって表されている。ピラミッド79のこのレベルには、４つの部分領域が存在する。このレベルのそれぞれの部分領域83は、４つのZ値を含む。レベル79で、４つの部分領域83の各々について４つのZ値が比較され、それぞれの部分領域83の最大Z値は保存される。図4Cは、図4Bに示す部分領域83のZ値の比較から生じる４つの最大Z値を表す。図4Cに示すレベル85の４つのZ値87が比較され、最大Z値は、図4Dに示すピラミッド93の最上レベルに対応する。
【００３３】
この発明のオクルージョン検査方法に従って、カバレージ・マスクは、領域および/または部分領域が多角形に覆われているかどうかを示すために使用される。これらのカバレージマスクは、Zピラミッドを更新する必要があるか、もし必要ならば、ピラミッドのどのZ値を更新する必要があるか判断するために使用される。図5Aないし図5Cは、それぞれ、図4Aないし図4Cに表すピラミッドの異なるレベルに関連するカバレージ・マスクを示す。これらのカバレージ・マスクは、多角形がグラフィックスシステム20のパイプラインを通して処理されているとき、進行中に、Zピラミッドが更新されることを可能にする。ピラミッドの各レベルのカバレージ・マスクは、ピラミッドの対応するレベルの中のそれぞれのZ値につき１ビットを含むことが好ましい。これらの個々のZ値は、特定のマスクに関連するピラミッドのレベル内の部分領域に対応する。例えば、図4Aに示すピラミッドのレベル71は、それぞれが４個の部分領域を含む16個の領域を含む。それゆえに、図5Aに示す対応するカバレージ・マスクは、64のエントリ、すなわち部分領域につき１ビットを含む。
【００３４】
ピラミッドの各レベルで、それぞれの領域のZ MAX.PYR.値が記憶され、これは、その領域の最大Z値に対応する。この値は、領域ごとのオクルージョン検査に使用される。さらに、それぞれの部分領域のZ値が記憶される。この値は、オクルージョン検査の結果として多角形が完全に隠れているわけではなく、その領域を完全に覆うわけではないと先行して判断された場合のみ、オクルージョン検査に使用される。しかし、個々の部分領域の値は、図7に関して以下で詳述するようにZピラミッドを更新するために使用される。
【００３５】
多角形の最小Z値Z MIN.POLY.が部分領域のZ値より小さく、多角形が領域を完全に覆う場合、部分領域のZ値は、多角形の最大Z値のZ MAX.POLY.によって更新される。しかし、部分領域のZ値は、Z MAX.POLY.値が部分領域の現在のZ値Z MAX.PYR.より小さい場合のみ更新される。部分領域の対応するビットが、ピラミッドの当該レベルに対応するカバレージ・マスク内に設定される。部分領域のビットすべてが設定されると、対応する領域ビットが、Zピラミッドの次に高いレベルに関連するカバレージ・マスク内に設定される。例えば、図4Aに示すピラミッド・レベル71に関して、部分領域73およびそれに隣接する３つの部分領域がすべて多角形に覆われている場合、図5Aに示すカバレージ・マスク100内の位置101、102、103および104に対応するビットが設定される。従って、図5Bに示すピラミッド内の次に高いレベルのカバレージ・マスク113内にも対応するビット115が設定される。
【００３６】
図5Aに示すカバレージ・マスク100内の位置107、108、109および110に示すように、１つの領域のすべてではなくいくつかのビットが設定されるとき、図5Bのカバレージ・マスク113内に示すように、ピラミッド内の次に高いレベルのカバレージ・マスク内の対応するビットは設定されない。図5Bに示すカバレージ・マスク113内のビットのうち１つしか設定されていないので、図5Cに示すカバレージ・マスク120内のビットはどれも設定されない。
【００３７】
ある領域に関連するカバレージ・マスク内のビットがすべて設定されるとき、その領域のすべての部分領域のZ値を比較して最大値を求める。この最大Z値は、その領域のZ MAX.PYR値となり、オクルージョン検査を実施するのに使用される。
【００３８】
ここで、図4Aないし図4Dに表すZピラミッドを使用してオクルージョン検査を実施する方法を、図6ないし図8のフローチャートに関して説明する。この発明の好ましい実施例に従って、それぞれの多角形の最小Z値をピラミッドの現在レベルの各領域の最大Z値と比較することによって、多角形を領域毎にオクルージョン検査する。領域が多角形によって完全に隠れていない場合、および領域が多角形に完全に覆われていない場合のみ、部分領域毎の比較が実施されることが好ましい。
【００３９】
Zピラミッドは既に構築されていると仮定すると、オクルージョン検査プロセスの第１ステップは、ブロック122に示すように、オクルージョン検査されている多角形の最小Z値であるZ MIN.POLY.を取得することである。Z MIN.POLY.値は、ブロック124に示すように、多角形と交差するピラミッドの現在レベルの領域のZ MAX.PYR値と比較される。ピラミッドの最上レベルから始まり、ブロック125に示すように、Z MIN.POLY.値がZ MAX.PYR.より小さいかどうか判断が行われる。もしそうであれば、多角形は少なくとも部分的に可視であり、プロセスは、以下で詳述するように、部分領域ごとのオクルージョン検査のためにブロック127に示すように図7のブロック140に進む。
【００４０】
ブロック125で、Z MIN.POLY.値がZ MAX.PYR.値より小さくないと判断される場合、プロセスはブロック129に進み、ブロック129に示されるように、ピラミッドの現在レベルに検査される他の領域があるかどうか判断される。
【００４１】
ブロック125で、Z MIN.POLY値がその領域のZ MAX.PYR.より小さいと判断されるとき、検査されている多角形が少なくとも部分的に可視であることを意味し、プロセスは、図7のブロック140に進む。それぞれの部分領域のZ値をZ MIN.POLY.値と比較して、多角形が部分領域によって隠れているかどうか判断する。ブロック141で、Z MIN.POLY.値が部分領域のZ値以下でないと判断される場合、ブロック142で、その領域内に比較される他の部分領域があるかどうか判断がなされる。もしなければ、プロセスは図6のブロック129に戻る。ブロック142で、該領域内に比較される他の部分領域があると判断される場合、プロセスは、ブロック143に示すように、その領域内の次の部分領域に進む。ブロック140に示すように、次の部分領域のZ値をZ MIN.POLY.値と比較する。
【００４２】
ブロック141で、Z MIN.POLY.値が比較されている部分領域のZ値より小さいかまたは等しいと判断される場合、プロセスはブロック144に進み、そこで、部分領域が多角形に完全に覆われているかどうか判断される。もしそうであれば、ブロック145に示すように、検査されている多角形の最大Z値Z MAX.POLY.が部分領域のZ MAX.PYR.値より小さいかどうか判断がなされる。もしそうであれば、ブロック146に示すように、部分領域のZ MAX.PYR.値に多角形の最大Z値Z MAX.POLYを代入する。ブロック147に示すように、部分領域の対応するビットが、領域カバレージ・マスク内に設定される。プロセスは、以下に詳述するように図8のブロック150に進み、Zピラミッドが、更新されたZバッファ値によって再構築される必要があるかどうか判断がなされる。
【００４３】
ブロック144で、多角形は部分領域を完全には覆っていないと判断される場合、プロセスは、ブロック149に示すように、ピラミッド内の次に低いレベルに進む。そしてブロック140に戻り、多角形は、ピラミッドのこのレベル内の部分領域に対して検査される。
【００４４】
プロセスが図8のブロック150に進むとき、現在領域のすべての部分領域のビットがカバレージ・マスク内に設定されているかどうか判断がなされる。もしそうであれば、プロセスは図７のブロック142に戻り、多角形に対して検査される他の部分領域があるかどうか判断される。
【００４５】
ブロック150で、その領域に対応するすべてのビットがカバレージ・マスク内に設定されおり、プロセスがピラミッドの最上レベルでないと判断される場合、ブロック153に示すように、その領域の最大Z値Z MAX.PYRに、すべての部分領域の最大Z値に等しい値を代入する。図6のブロック125で、この新しい値を使用して、領域毎の多角形のオクルージョン検査を実施する。ブロック155に示すように、その領域に対応するカバレージ・マスク内のビットが、ピラミッド内の次に高いレベルのカバレージ・マスク内に設定される。プロセスは、図7のブロック142に戻る。さらに、ブロック150で、現在領域のすべてのビットが設定されているわけではない、あるいは、プロセスがピラミッドの最上レベルに達したと判断されるとき、プロセスはブロック142に戻る。
【００４６】
Zピラミッドの特定レベルに関連するカバレージ・マスクが更新されるときはいつも、ピラミッド内のそれより高いレベルに関連するカバレージ・マスクを更新しなければならないかどうか判断しなければならない。例えば、ある領域に関連するすべての部分領域のビットが、カバレージ・マスク内に設定されているとき、ピラミッド内の次に高いレベルに関連するカバレージ・マスクが設定される必要がある。プロセスはピラミッド内の次に高いレベルに進み、ピラミッド内のその上位のレベルに関連するカバレージ・マスクを設定する必要があるかどうか判断する。このプロセスは、ピラミッドの最上レベルに達するまで、あるいは、カバレージマスク内の対応するビットが設定される必要がないと判断されるまで続行する。ある領域に関連する部分領域のすべてのビットより少ないビットがカバレージ・マスク内に設定されたとき、ピラミッド内の次に高いレベルに関連するカバレージマスクが設定される必要はない。このようにカバレージ・マスクを更新することによって、多角形がグラフィックスシステム20を通して処理されているとき、Zピラミッドは進行中に更新される。
【００４７】
Zピラミッドは、多角形の最小および最大Z値を使用して進行中に更新されるので、Zピラミッドは、ピクセルレベルのZバッファ記憶素子66からZピラミッド記憶素子63に供給されるピクセルレベルのZ値を使用して定期的に組み立て直されることが好ましい。これは、オクルージョン検査に使用されるZ値およびMFU36からOFU38に出力されるピクセルレベルのZ値の正確さを保証する。
【００４８】
この発明に従う走査変換
図9は、第１の実施例に従ってこの発明の走査変換プロセスを機能的に示すフローチャートである。この実施例によれば、走査変換は、グラフィックスシステム20の中の任意の適当な場所で実現することができる独立したプロセスである。図10は、好ましい実施例に従うこの発明の走査変換プロセスを機能的に示すフローチャートである。好ましい実施例に従って、走査変換プロセスは、階層的タイラー57の中で実現され、図3ないし図8に関して上述したオクルージョン検査プロセスと同時に実施される。
【００４９】
図9に示すように、表示モニタ21に対応する画面空間は、まず、ブロック179に示すように複数のN×N領域に細分される。ここで、Nは整数に対応する。ブロック180に示すように、既にセットアップ・ユニット55内で計算された、走査変換されようとする第１プリミティブの辺に対応する平面方程式を使用して、それぞれのN×N領域の角(コーナー)に関連する座標がプリミティブの外にあるかどうか判断する。ブロック180で、領域のすべての角がプリミティブの外にあると判断される場合、画面空間の当該領域の中で行わなければならない他の作業はない。ブロック181に示すように、プロセスは次の領域に進む。それから、画面空間の当該レベルの次の領域のすべての角がプリミティブの外にあるかどうか判断される。
【００５０】
ブロック180で領域のすべての角がプリミティブの外にあるわけではないと判断されるまで、プロセスのブロック180および181に示す部分が続行する。ブロック180で、領域のすべての角がプリミティブの外にあるわけではないと判断されると、ブロック182に示すように、領域のすべての角がプリミティブの中にあるかどうか判断がなされる。もしそうであれば、ブロック183に示すように、その領域はピクセルに変換され、それらのピクセルは、更なる処理のために下流に送り出される。
【００５１】
当業者であれば、ピクセルレベルに到達したら、領域をピクセルに変換するに適当な複数の方法があることが分かるであろう。これらの方法の１つによれば、領域は、領域の最小y座標をもつ走査線から始まって領域の最小x座標から領域の最大x座標に向かう方向の走査線上のピクセルを識別することによって、ピクセルに変換される。これは、領域の最大y値に達するまで、それぞれの走査線について行われる。
【００５２】
当業者であれば、領域をピクセルに変換する他の方法を使用して、ピクセルを２次元領域にグループ化し、フレームバッファRAM45内のピクセルの編成および記憶を容易にできることが分かるであろう。例えば、階層的タイラー57の中で論理を構築し、xおよびy画面空間座標についてネストされた(入れ子になった)ループを実現し、領域のピクセルを２次元所在をもつグループに分類することができる。これが実現される方法は、当業者であれば理解できるであろう。従って、このタスクを実施するためのコードを設計することは、当業者にとって決まりきったことなので、簡潔さのため、ここではこのアルゴリズムを説明しない。
【００５３】
ブロック182で、領域が完全にプリミティブの中に含まれるわけではないと判断される場合、ブロック185に示すように、その領域を検査して、それが少なくとも部分的にプリミティブの中にあるかどうか判断する。ブロック180で、領域が完全にプリミティブの外にあるわけではないと判断されても、その領域は、実際にはプリミティブの外にあることがある。それゆえ、領域が部分的にプリミティブに覆われているかどうか判断しなければならない。この判断を行う方法は、図11を参照して以下で詳述する。ブロック185で、領域がプリミティブに部分的に覆われていないと判断される場合、ブロック186に示すように、プロセスは、検査される次の領域に進む。
【００５４】
ブロック185で、領域が部分的にプリミティブに覆われていると判断される場合、ブロック187に示すように、部分的にプリミティブに覆われている領域は、さらに複数の領域に細分される。これらの領域をそれぞれ検査して、領域の角がプリミティブの中にあるかどうか判断する。それゆえ、ブロック188に示すようにピクセルレベルに達していない場合、ブロック190に示すように、プロセスはブロック180に戻る。ピクセルレベルに達するまで、画面空間は細分され続ける。すなわち、それぞれの領域が単一のピクセルに対応する点に達するまで、画面空間は細かく細分される。ピクセルレベルに達すると、プリミティブに対応する正確なピクセル位置が分かり、ブロック189に示すように、プリミティブに対応するピクセルを更なる処理のために下流に送り出すことができる。
【００５５】
図10は、走査変換およびオクルージョン検査が同時に実施される好ましい実施例に従うこの発明の走査変換方法を表すフローチャートである。図10に示すように、表示モニタ21に対応する画面空間は、まずブロック191に示すように複数のN×N領域に細分される。ここで、Nは整数に対応する。ブロック192に示すように、走査変換される第１プリミティブの辺に対応する平面方程式を使用して、それぞれのN×N領域の角に関連する座標がプリミティブの外にあるかどうか判断する。ブロック192で、領域のすべての角がプリミティブの外にあると判断される場合、画面空間のその領域内で行わなければならない他の作業はないので、プロセスは、ブロック193に示すように次の領域に進む。ブロック192に示すステップで、画面空間の当該レベルの次の領域のすべての角がプリミティブの外にあるかどうか判断がなされる。
【００５６】
ブロック192で、ブロック192および193によって表されるプロセスの一部は、領域のすべての角がプリミティブの外にあるわけではないと判断されるまで続行する。ブロック192で、領域のすべての角がプリミティブの外にあるわけではないと判断されると、ブロック196に示すように、領域のすべての角がプリミティブの中にあるかどうか判断がなされる。もしそうであれば、ブロック198に示すように、プリミティブが隠れているかどうか判断される。プリミティブが隠れていない場合、プリミティブの中に含まれると判明した領域は、ブロック199に示すようにピクセルに変換される。プリミティブが隠れているかどうかを判断する好ましい方法は、図6ないし図8を参照して上述した方法である。しかし、当業者であれば、この目的のためにここで述べたオクルージョン検査方法と異なるオクルージョン検査方法を使用することができることが分かるであろう。
【００５７】
ブロック196で、領域が完全にプリミティブの中に含まれるわけではないと判断される場合、ブロック200に示すように、領域が少なくとも部分的にプリミティブに覆われているどうか判断しなければならない。領域が少なくとも部分的にプリミティブに覆われていない場合、プロセスは、ブロック201に示すようにブロック193に戻り、次の領域を検査することができる。ブロック200で、領域が少なくとも部分的にプリミティブに覆われていると判断される場合、ブロック202で、プリミティブが隠れているかどうか判断される。もしそうであれば、プロセスは、ブロック201に示すようにブロック193に戻る。もしそうでなければ、ブロック203に示すように、部分的に覆われている領域は、複数の領域にさらに細分されなければならない。これらの領域をそれぞれ検査して、これらの領域の角がプリミティブの中にあるかどうか判断する。それゆえ、プロセスが、ブロック204に示すようにピクセルレベルに達していない場合、プロセスは、ブロック205に示すようにブロック192で表したステップに戻る。
【００５８】
領域が完全にプリミティブの中にあるわけではなく、また、完全に外にあるわけでもないとプロセスが判断し続ける限り、画面空間は、ピクセルレベルに達するまで細分され続ける、すなわち、それぞれの部分領域が単一のピクセルに対応する点に達するまで、画面空間は細かく細分される。ピクセルレベルに達すると、プリミティブに対応する正確なピクセル位置が分かる。ピクセルは、ブロック206に示すようにオクルージョン検査される。ピクセルが隠れていない場合、ピクセルは、ブロック207に示すように更なる処理のために下流に送り出される。ピクセルが隠れている場合、ブロック208に示すように、それらは捨てられる。
【００５９】
ここで、図11を参照して、領域の角がプリミティブの中にあるかどうかを平面方程式を使用して判断する方法を説明する。図11は、走査変換されるプリミティブ212を示す。プリミティブの頂点のxおよびy座標を図11に示す。これらの頂点の座標を使用して、辺0,1,2について平面方程式を計算する。座標(x0,y0)から始めて反時計回りに計算することが好ましい。平面方程式は、次のように与えられる:
Ax+By+C=0                                  方程式(1)
ここで、A、BおよびCは、定数である。辺0について平面方程式を計算するため、A、BおよびCは、次のように計算される:
A=y1-y0                                    方程式(2)
B=x0-x1                                    方程式(3)
C=-Ax0-By0                                 方程式(4)
辺１について平面方程式を計算するため、A、BおよびCは、次のように計算される:
A=y2-y1                                    方程式(5)
B=x2-x1                                    方程式(6)
C=Ax1-By1                                  方程式(7)
辺2について平面方程式を計算するため、A、BおよびCは、次のように計算される:
A=y0-y2                                    方程式(8)
B=x0-x2                                    方程式(9)
C=Ax2-By2                                  方程式(10)
【００６０】
それぞれの辺について値A、BおよびCが計算されると、それぞれの辺に関する平面方程式がそれぞれのA、BおよびC値によって準備される。平面方程式を図9および図10に関して上述したプロセスの中で使用して、領域の角に対応するxおよびy画面座標がすべてプリミティブの中にあるか、または、すべてプリミティブの外にあるか、または、領域が完全にプリミティブの外にあるわけでなく、完全にプリミティブの中にあるわけでもないのか、を判断する。
【００６１】
領域のそれぞれの角に対応するxおよびy座標が、それぞれの辺の方程式(1)の中のxおよびy値として使用されるとき、平面方程式のすべての結果が正であれば、領域は、完全にプリミティブの中にあり、すなわち完全にプリミティブに覆われている。領域のそれぞれの角に対応するxおよびy座標が、それぞれの辺の方程式(1)の中のxおよびy値として使用されるとき、平面方程式のどれか１つの結果が領域の４つの角すべてについて負であるとき、領域は、完全にプリミティブの外にある。
【００６２】
上記の検査を使用して領域が完全にプリミティブの中にあるとも、完全に外にあるとも言えない場合、領域が部分的にプリミティブに覆われているかどうか判断しなければならない。これは、まずプリミティブのまわりに矩形の境界ボックスを生成することによって実現される。図11に、x軸215、y軸216、破線217および破線218からなる境界ボックスが示されている。境界ボックスの左下角は、プリミティブ212の頂点の座標(x0,y0)に対応する。境界ボックスの左上角は、破線217とy軸の交点に対応し、座標(x0,y2)に対応する。境界ボックスの右上角は、破線217と218の交点に対応し、座標(x1,y2)に対応する。境界ボックスの右下角は、破線218とx軸の交点に対応し、座標(x1,y0)に対応する。
【００６３】
境界ボックスが構築されると、以下のように、領域が完全にプリミティブの外にあるか、ゆえに部分的にプリミティブに覆われていないかを容易に判断することができる。境界ボックスの最大x値(図11のx1)が領域の最小x値より小さい場合、領域は、完全にプリミティブの外にある。同様に、境界ボックスの最小x値(図11のx0)が領域の最大x値より大きい場合、領域は完全にプリミティブの外にある。同様に、境界ボックスの最大y値(図11のy2)が領域の最小y値より小さい場合、領域は完全にプリミティブの外にある。同様に、境界ボックスの最小y値(図11のy0)が領域の最大y値より大きい場合、領域は完全にプリミティブの外にある。
【００６４】
さらに、領域がプリミティブに部分的に覆われているかどうかを判断するためのプロセスの代替実施例も次のように境界ボックスを使用する。境界ボックスのそれぞれの辺についての平面方程式は、境界ボックスの座標を使用して計算され、辺の方程式のA、BおよびC値を得る。領域の角のxおよびy値が平面方程式の中でxおよびy値として使用されるとき、領域の４つの角すべてが負の結果をもたらす平面方程式がないかどうか判断される。領域の４つの角すべてが負の結果をもたらす平面方程式がない場合、領域は部分的にプリミティブに覆われている。言い換えると、領域の４つの角すべてのxおよびy値が平面方程式の中で使用されるとき、負の結果をもたらす平面方程式がある場合、領域は、完全にプリミティブの外にある。
【００６５】
当業者であれば分かるであろうが、平面方程式は、反時計回りの方法とは対照的に、時計回りに計算することができることに注意すべきである。この発明は、平面方程式が計算される方法に限定されない。さらに、画面空間の領域がプリミティブによって全体的にまたは部分的に覆われているかどうか判断するための他の適当な方法がありうる。当業者であれば、図9および図10に関して上述した方法と共に、ここで明示的に説明したもの以外のこのタスクを実施するための方法を使用することができることが分かるであろう。
【００６６】
この発明は、この発明の好ましい実施例に関して記述されており、これらの実施例に限定されないことに注意すべきである。また、当業者であれば、階層的タイラー57は、ハードウェア、ソフトウェア、またはハードウェアとソフトウェアの組み合わせの中で実現できることが分かるであろう。離散的な電気的成分のような他のハードウェア具体例が、階層的タイラー57に適当でありうるが、階層的タイラー57は、集積回路内の状態機械として実現されることが好ましい。当業者であれば、この発明の精神および理念から逸脱することなく、上述した実施例に変更を加えることができることが分かるであろう。
【００６７】
本発明は例として次の実施態様を含む。
【００６８】
(１)コンピュータグラフィックス表示システム(10)において、走査変換中のプリミティブに対応する画面空間のピクセル位置を求めるよう走査変換を実施する装置(20)であって、上記画面空間は、表示モニタ(21)上のピクセル位置のxおよびy座標に対応し、上記装置(20)は、
プリミティブを画面空間のピクセル位置に変換するように構成される論理(36)を備え、それぞれのピクセル位置は、画面空間のx座標およびy座標によって規定され、それぞれのプリミティブは、複数の頂点を有し、それぞれの頂点は、画面空間のx座標およびy座標によって規定され、上記論理(36)は、上記画面空間を複数の領域に細分し(179)、それぞれの領域は、上記画面空間の複数のピクセル位置に対応し、上記論理(36)は、上記複数の領域のうちの特定の１つが、完全に上記プリミティブの外にあるか(180)、完全に上記プリミティブの中にあるか(182)、または部分的に上記プリミティブの中にあるか(185)判断し、上記論理(36)が、特定の領域は完全に上記プリミティブの中にあると判断する場合、上記論理(36)は、特定の領域を画面空間のピクセル位置に変換する(183)、装置。
【００６９】
（２）特定の領域は部分的に上記プリミティブの中にあると上記論理(36)が判断する場合(185)、上記論理(36)は、特定の領域を複数の部分領域に細分し(187)、それぞれの部分領域は、画面空間の複数のピクセル位置からなり、上記論理(36)は、上記複数の部分領域のうちの特定の１つが、完全に上記プリミティブの外にあるか(180)、完全に上記プリミティブの中にあるか(182)、または部分的に上記プリミティブの中にあるか(185)を判断し、上記論理(36)が、特定の部分領域は完全に上記プリミティブの中にあると判断する場合、上記論理(36)は、上記プリミティブの中にあると判断された特定の部分領域を、画面空間のピクセル位置に変換する(183)、上記(1)に記載の装置(20)。
【００７０】
（３）特定の領域または部分領域は完全にプリミティブの外にあるわけではないと上記論理(36)が判断した後にのみ、上記論理(36)は、特定の領域または部分領域が完全にプリミティブの中にあるか判断し、特定の領域または部分領域は完全にプリミティブの中にあるわけではないと上記論理(36)が判断した後にのみ、上記論理(36)は、特定の領域または部分領域が部分的にプリミティブの中にあるか判断する、上記(2)に記載の装置(20)。
【００７１】
（４）上記論理(36)が、特定の領域は完全に特定のプリミティブの中にあると判断するとき(196)、上記論理(36)は、特定の領域をピクセル位置に変換する前に、特定のプリミティブが隠れているかどうか判断し(198)、上記論理(36)が特定のプリミティブは隠れないと判断した場合のみ、特定の領域は画面空間のピクセル位置に変換される(199)、上記(3)に記載の装置(20)。
【００７２】
（５）上記論理(36)が特定の領域は完全に特定のプリミティブの中にあるわけではないと判断した後にのみ、上記論理(36)は、特定の領域が部分的に特定のプリミティブの中にあるかどうか判断し(200)、上記論理(36)が特定の領域は部分的に特定のプリミティブの中にあると判断するとき(200)、上記論理(36)は、特定のプリミティブが隠れているか判断し(202)、上記論理(36)が特定のプリミティブは隠れていないと判断する場合、上記論理(36)は、部分的に特定のプリミティブの中にあると判明した特定の領域を複数の部分領域に細分し(203)、それぞれの部分領域は、画面空間の複数のピクセル位置からなる、上記(4)に記載の装置(20)。
【００７３】
（６）上記論理(36)は、上記複数の部分領域のうち特定の１つが完全に特定のプリミティブの外にあるか(192)、完全に特定のプリミティブの中にあるか(196)、または部分的に特定のプリミティブの中にあるか(200)を判断し、上記論理(36)が特定の部分領域は完全に特定のプリミティブの中にあると判断する場合(196)、上記論理(36)は、特定のプリミティブが隠れているかどうか判断し(198)、上記論理(36)が特定のプリミティブは隠れていないと判断する場合、上記論理(36)は、特定のプリミティブの中にあると判断された特定の部分領域を、画面空間のピクセル位置に変換し(199)、上記論理(36)が特定の部分領域は完全に特定のプリミティブの外にあるわけではないと判断した後にのみ、上記論理(36)は、特定の部分領域が完全に特定のプリミティブの中にあるかどうか判断し、上記論理(36)が特定の部分領域は完全に特定のプリミティブの中にあるわけではないと判断した後にのみ、上記論理(36)は、特定の部分領域が部分的に特定のプリミティブの中にあるかどうか判断し、上記論理(36)が、特定の部分領域は部分的に特定のプリミティブの中にあると判断する場合(200)、上記論理(36)は、特定のプリミティブが隠れているかどうか判断し(202)、上記論理(36)が特定のプリミティブは隠れていないと判断する場合、上記論理は、特定の部分領域を複数のより小さい部分領域に細分し(203)、上記より小さい部分領域はそれぞれ、画面空間の複数のピクセル位置からなる、上記(5)に記載の装置(20)。
【００７４】
（７）コンピュータグラフィックス表示システム(10)において、走査変換中のプリミティブに対応する画面空間のピクセル位置を求めるよう走査変換を実施する方法であって、上記画面空間は、表示モニタ(21)上のピクセル位置のxおよびy座標に対応し、それぞれのピクセル位置は、画面空間のx座標およびy座標によって規定され、それぞれのプリミティブは、複数の頂点をもち、それぞれの頂点は、画面空間のx座標およびy座標によって規定され、上記方法は、
画面空間を複数の領域に細分し、それぞれの領域は画面空間の複数のピクセル位置に対応するステップ(179)と、
上記複数の領域のうち特定の１つが、完全に上記プリミティブの外にあるか(180)、完全に上記プリミティブの中にあるか(182)、または部分的に上記プリミティブの中にあるか(185)を判断するステップと、
特定の領域が完全に上記プリミティブの中にあると判断される場合(182)、特定の領域は画面空間のピクセル位置に変換されるステップ(183)と、
を含む上記方法。
【００７５】
（８）さらに、特定の領域が部分的にプリミティブの中にあると判断される場合(185)、特定の領域を複数の部分領域に細分し、それぞれの部分領域は画面空間の複数のピクセル位置からなるステップ(187)と、
上記複数の部分領域のうち特定の１つが、完全に上記プリミティブの外にあるか(180)、完全に上記プリミティブの中にあるか(182)、または部分的に上記プリミティブの中にあるか(185)を判断するステップと、
特定の部分領域が完全に上記プリミティブの中にあると判断される場合(182)、上記プリミティブの中にあると判断された特定の部分領域を画面空間のピクセル位置に変換するステップ(183)と、
を含む上記(7)に記載の方法。
【００７６】
（９）特定の領域または部分領域が完全にプリミティブ外にあるわけではないと判断された後(180)にのみ、特定の領域または部分領域が完全にプリミティブの中にあるかどうか判断するステップ(182)と、特定の領域または部分領域が完全にプリミティブの中にあるわけではないと判断された後(182)にのみ、特定の領域または部分領域が部分的にプリミティブの中にあるかどうか判断するステップ(185)と、を含む上記(8)に記載の方法。
【００７７】
（１０）特定の領域は完全に特定のプリミティブの中にあると判断される場合(196)、特定の領域が画面空間のピクセル位置に変換される(199)前に、特定のプリミティブが隠れているかどうか判断され(198)、特定のプリミティブは隠れていないと判断される場合のみ(198)、特定の領域は画面空間のピクセル位置に変換され、特定の領域は完全に特定のプリミティブの中にあるわけではないと判断された後にのみ(196)、特定の領域が部分的に特定のプリミティブの中にあるかどうか判断され(200)、特定の領域は部分的に特定のプリミティブの中にあると判断されるとき(200)、特定のプリミティブが隠れているかどうか判断され(202)、特定のプリミティブは隠れていないと判断される場合、部分的に特定のプリミティブの中にあると判明した特定の領域は複数の部分領域に細分され(203)、それぞれの部分領域は、画面空間の複数のピクセル位置からなる、上記(9)に記載の方法。
【００７８】
【発明の効果】
本発明によれば、グラフィックス表示システムでプリミティブの処理およびピクセル表示を改善することができる。
【図面の簡単な説明】
【図１】この発明のグラフィックスシステムを取り入れたコンピュータグラフィクス表示システムのブロック図。
【図２】図1に示すコンピュータグラフィクス表示システムのグラフィックスシステムのブロック図。
【図３】この発明の好ましい実施例に従う図2に示すグラフィックスシステムのマクロ機能ユニットのブロック図。
【図４】図4の(A)ないし(D)は、図3に示すマクロ機能ユニットによってオクルージョン検査に使用されるZピラミッドの異なるレベルを示す図。
【図５】図5の(A)ないし(C)は、図4の(A)ないし(C)に示したZピラミッド・レベルを更新するために使用されるカバレージ・マスクに対応する図。
【図６】図７および図８と共に、オクルージョン検査を実施し、進行中にZピラミッドを更新するこの発明の方法を示すフローチャート。
【図７】図６および図８と共に、オクルージョン検査を実施し、進行中にZピラミッドを更新するこの発明の方法を示すフローチャート。
【図８】図６および図８と共に、オクルージョン検査を実施し、進行中にZピラミッドを更新するこの発明の方法を示すフローチャート。
【図９】走査変換を実施するこの発明の方法を機能的に示すフローチャート。
【図１０】走査変換およびオクルージョン検査が同時に実施される、好ましい実施例に従うこの発明の走査変換を実施する方法を機能的に示すフローチャート。
【図１１】この発明に従って走査変換されるプリミティブを示す図。
【符号の説明】
２０    グラフィックスシステム
３６    ３次元マクロ機能ユニット
５７    階層的タイラー
【図１】
0003840014.tif 000002
【図２】
0003840014.tif 000003
【図３】
0003840014.tif 000004
【図４】
0003840014.tif 000005
【図５】
0003840014.tif 000006
【図６】
0003840014.tif 000007
【図７】
0003840014.tif 000008
【図８】
0003840014.tif 000009
【図９】
0003840014.tif 000010
【図１０】
0003840014.tif 000011
【図１１】
0003840014.tif 000012