JPH0855239A

JPH0855239A - グラフィカル・オブジェクトの可視性を判定するための方法および装置

Info

Publication number: JPH0855239A
Application number: JP7168688A
Authority: JP
Inventors: Chandrasekhar Narayanaswami; チャンドラセカール・ナラヤナスワミ
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1994-07-21
Filing date: 1995-07-04
Publication date: 1996-02-27
Also published as: US5734806A

Abstract

(57)【要約】（修正有）【目的】グラフィカル・オブジェクトの可視性を判定
する方法と装置の提供。【構成】各グラフィカル・オブジェクトを複数の画素
にスキャン変換する装置と、各画素の深さとオブジェク
ト識別子とをメモリに記憶する装置と、メモリに記憶さ
れたオブジェクト識別子を有するグラフィカル・オブジ
ェクトをレンダリングする装置とを含む。各グラフィカ
ル・オブジェクトを、深さを有しそれぞれに該オブジェ
クトのオブジェクト識別子が与えられる複数の画素にス
キャン変換するステップ５２０と、所与の画素位置につ
いて前に記憶された深さより視点に近い画素深さを有す
る各画素の深さとオブジェクト識別子とをメモリに記憶
するステップ５３０と、メモリに記憶されたオブジェク
ト識別子を有するグラフィカル・オブジェクトをレンダ
リングするステップとを含み、ディスプレイ上に可視の
グラフィカル・オブジェクトをレンダリングする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、全般的にはコンピュー
タ・グラフィックス・システムに関し、具体的には、グ
ラフィカル・オブジェクトの可視性を判定する方法およ
び装置に関する。

【０００２】

【従来の技術】コンピュータ・グラフィックス・システ
ムでは、３次元グラフィックの絵を２次元ディスプレイ
に提示することが望ましい。通常、このような絵は、３
次元オブジェクトの組としてメモリに記憶される構造ま
たは画像である。たとえば、オブジェクトは、通常は頂
点Ｐ（０），Ｐ（１），…，Ｐ（ｎ−２），Ｐ（ｎ−
１）の組として指定され、このｎは、オブジェクトの頂
点の個数である。各頂点Ｐ（ｉ）は、適当な座標空間内
の位置Ｖ（ｉ）と、少なくとも１つの関数、たとえばカ
ラー係数ｆ（Ｖ（ｉ））などによって指定される。カラ
ー係数は、後程カラー（グレイスケールを含む）の変動
として表示できる、各頂点で評価される関数である（光
の強度、温度特性、湿度係数など）。カラー係数は、色
に変換することができ、モデリングに有用である（単純
な照明モデリングやより複雑な気象モデリングなど）。

【０００３】オブジェクトをレンダリングしている時
に、位置または画素アドレス（通常はＸＹ空間）と、色
などのその画素のさまざまな関数を含むオブジェクトの
画素表現を計算し、補間する。その結果、ディスプレイ
上の絵を生成するために、通常は計算集中型の処理を使
用してオブジェクトをレンダリングする。その結果、複
数の技法を使用して、レンダリングするオブジェクトま
たは画素の個数を減らすことができる。

【０００４】たとえば、表現しなければならない絵の一
部が、ディスプレイ上のウィンドウまたはディスプレイ
自体によってもたらされる視野から外れる場合がある。
そのような場合には、絵を生成する際にその絵とその絵
を構成するオブジェクトをクリッピングし、これによっ
て必要な計算量を減らし、レンダリング速度を高めるこ
とが望ましい。

【０００５】もう１つの例では、いくつかのオブジェク
トが視野の中にあるが、その前にあるオブジェクトによ
って隠されている場合がある。どのオブジェクトが可視
であるかを判定し、その結果、可視のオブジェクトまた
はオブジェクトの一部だけをレンダリングするための技
法が複数存在する。これらの可視性判定技法の多くが、
フォレイ（Foley）、バン−ダム（Van Dam）、ファイナ
（Feiner）およびヒューズ（Hughes）著、"Computer Gr
aphics Principles and Practice", second edition、
１９９０年の６４９ページから７２０ページに記載され
ている。

【０００６】

【発明が解決しようとする課題】たとえば、レンダリン
グしようとするグラフィカル・オブジェクトのすべて
を、その深さに従って順序付けた後に、後方のオブジェ
クトから前方のオブジェクトへとレンダリングして、す
べてのオブジェクトのすべての画素がレンダリングされ
るようにすることができる。その結果、不可視のオブジ
ェクトの画素値は、レンダリングされた後に、その前に
あるオブジェクトがレンダリングされる時に置換され
る。しかし、この処理では、すべてのオブジェクトのす
べての画素をレンダリングする必要があり、オブジェク
トが交差している場合は処理されない。すなわち、この
処理は、第１のオブジェクトの第１の部分が第２のオブ
ジェクトに隠され、第１のオブジェクトの第２の部分が
第２のオブジェクトの前にある場合を取り扱えない。

【０００７】

【課題を解決するための手段】本発明には、各グラフィ
カル・オブジェクトを、深さを有しそれぞれに該オブジ
ェクトのオブジェクト識別子が与えられる複数の画素に
スキャン変換する装置と、所与の画素位置について前に
記憶された深さより視点に近い画素深さを有する各画素
の深さとオブジェクト識別子とをメモリに記憶する装置
と、メモリに記憶されたオブジェクト識別子を有するグ
ラフィカル・オブジェクトをレンダリングする装置とを
含む、ディスプレイ上に可視のグラフィカル・オブジェ
クトをレンダリングするための装置が含まれる。さら
に、本発明には、各グラフィカル・オブジェクトを、深
さを有しそれぞれに該オブジェクトのオブジェクト識別
子が与えられる複数の画素にスキャン変換するステップ
と、所与の画素位置について前に記憶された深さより視
点に近い画素深さを有する各画素の深さとオブジェクト
識別子とをメモリに記憶するステップと、メモリに記憶
されたオブジェクト識別子を有するグラフィカル・オブ
ジェクトをレンダリングするステップとを含む、ディス
プレイ上に可視のグラフィカル・オブジェクトをレンダ
リングするための方法が含まれる。

【０００８】本発明の性質および長所のさらなる理解
は、本明細書の残りの部分および図面を参照することに
よって得られる。

【０００９】

【実施例】この開示では、グラフィカル・オブジェクト
の可視性を判定するための改良された方法および装置を
説明する。好ましい実施例では、各オブジェクトに識別
子を与え、Ｘ、ＹおよびＺ値だけを決定された画素にス
キャン変換する。その後、可視性バッファを使用して、
各オブジェクトの可視の画素を記憶する。これが完了し
たならば、カラー、照明および他の補間計算の実行を含
めて、可視のオブジェクトまたはオブジェクトの可視部
分だけをレンダリングする。この処理では、必要なレン
ダリング計算の量が少なくなり、したがって、レンダリ
ング処理の速度が向上する。

【００１０】図１は、本発明の好ましい実施例によって
使用される典型的なディジタル・コンピュータ１００の
ブロック図である。このコンピュータには、入力装置１
３０および出力装置１４０を接続されたコンピュータ・
ボックス１０５内の、主記憶１２０およびハード・ディ
スク１２５に結合された主プロセッサ１１０が含まれ
る。主プロセッサ１１０には、単一のプロセッサまたは
複数のプロセッサを含めることができる。入力装置１３
０には、キーボード、マウス、タブレットまたは他のタ
イプの入力装置を含めることができる。出力装置１４０
には、テキスト・モニタ、プロッタまたは他のタイプの
出力装置を含めることができる。磁気ディスケットやコ
ンパクト・ディスクなどのコンピュータ可読の取外し可
能媒体１９０を、ディスク駆動装置やＣＤ−ＲＯＭ（コ
ンパクト・ディスク読取専用メモリ）駆動装置などの入
出力装置１８０に挿入することができる。データは、入
出力装置コントローラ１７０の制御の下で、入出力装置
によって取外し可能媒体から読み取られ、書き込まれ
る。入出力装置コントローラは、バス１６０を介して主
プロセッサと通信する。主記憶１２０、ハード・ディス
ク１２５および取外し可能媒体１９０のすべてを、主プ
ロセッサ１１０による処理のためのデータの記憶に関し
てメモリと称する。

【００１１】主プロセッサは、グラフィックス・アダプ
タ２００を介して、グラフィックス・ディスプレイなど
のグラフィックス出力装置１５０に結合することもでき
る。グラフィックス・アダプタ２００は、バス１６０を
介して主プロセッサ１１０からグラフィックスに関する
命令を受け取る。その後、グラフィックス・アダプタ
は、グラフィックス・アダプタ・メモリ２３０に結合さ
れたグラフィックス・アダプタ・プロセッサ２２０を用
いてこれらの命令を実行する。グラフィックス・アダプ
タ内のグラフィックス・プロセッサは、これらの命令を
実行し、これらの命令に基づいてフレーム・バッファ２
４０を更新する。グラフィックス・アダプタ・プロセッ
サ２２０は、直列のプロセッサのパイプライン、１組の
並列プロセッサ、またはその組合せとすることができ、
この各プロセッサは、完了すべきタスクの一部を処理す
ることができる。グラフィックス・アダプタ・プロセッ
サ２２０には、特定のタイプのプリミティブのレンダリ
ング専用のレンダリング・ハードウェアを含めることも
できる。グラフィックス・アダプタ・メモリ２３０は、
グラフィックス・プロセッサによって、受け取ったオブ
ジェクト・データ、中間計算データ（ステンシル・バッ
ファや部分的にレンダリングされたオブジェクトのデー
タなど）およびフレーム・バッファ２４０にロードされ
る完了したデータなど、処理される情報の記憶に使用さ
れる。フレーム・バッファ２４０には、グラフィックス
出力装置に表示されるすべての画素のデータが含まれ
る。ＲＡＭＤＡＣ（ランダム・アクセス・メモリ・ディ
ジタル・アナログ変換器）２５０は、フレーム・バッフ
ァに記憶されたディジタル・データをＲＧＢ信号に変換
してグラフィックス出力装置１５０に供給し、これによ
って、主プロセッサから所望されたグラフィックス出力
をレンダリングする。

【００１２】図２は、通常はグラフィックス機能を実行
するためホスト・コンピュータおよびグラフィックス・
アダプタによって利用されるコードの層を示すブロック
図である。ＵＮＩＸなどのオペレーティング・システム
３００が、ホスト・コンピュータの基本制御を提供す
る。オペレーティング・システムに結合されているの
が、オペレーティング・システムにハードウェア集中型
タスクを提供するオペレーティング・システム・カーネ
ル３１０である。オペレーティング・システム・カーネ
ルは、ホスト・コンピュータ・マイクロコード３２０と
直接に通信する。ホスト・コンピュータ・マイクロコー
ドは、ホスト・コンピュータ・プロセッサによって実行
される基本命令セットである。オペレーティング・シス
テム３００に結合されているのが、グラフィックス・ア
プリケーション３３０および３３２である。このグラフ
ィックス・アプリケーション・ソフトウェアには、シリ
コン・グラフィック（Silicon Graphic）社のＧＬ、Ｉ
ＢＭ社のｇｒａＰＨＩＧＳ、ＭＩＴ（マサチューセッツ
工科大学）のＰＥＸなどのソフトウェア・パッケージを
含めることができる。このソフトウェアは、２次元グラ
フィックスまたは３次元グラフィックスの主要な機能を
提供する。グラフィックス・アプリケーション３３０は
グラフィックス・アプリケーションのＡＰＩ（アプリケ
ーション・プログラム・インターフェース）３４０に、
グラフィックス・アプリケーション３３２はＡＰＩ３４
２に結合される。ＡＰＩは、グラフィックス・アプリケ
ーションに計算集中型タスクの多くを提供し、グラフィ
ックス・アダプタ用のデバイス／ドライバなど、グラフ
ィックス・ハードウェアに近いソフトウェアとアプリケ
ーション・ソフトウェアの間のインターフェースを提供
する。たとえば、ＡＰＩ３４０はＧＡＩ（グラフィック
ス・アプリケーション・インターフェース）３５０と、
ＡＰＩ３４２はＧＡＩ３５２と、通信することができ
る。ＧＡＩは、アプリケーションＡＰＩとグラフィック
ス・アダプタのデバイス・ドライバ３７０の間のインタ
ーフェースを提供する。一部のグラフィックス・システ
ムでは、ＡＰＩがＧＡＩの機能も実行する。

【００１３】グラフィックス・アプリケーション、ＡＰ
ＩおよびＧＡＩは、オペレーティング・システムとデバ
イス・ドライバによって、単一のプロセスであるとみな
される。すなわち、オペレーティング・システム３００
とデバイス・ドライバ３７０からは、グラフィックス・
アプリケーション３３０、ＡＰＩ３４０およびＧＡＩ３
５０がプロセス３６０とみなされ、グラフィックス・ア
プリケーション３３２、ＡＰＩ３４２およびＧＡＩ３５
２がプロセス３６２とみなされる。プロセスは、オペレ
ーティング・システムとデバイス・ドライバからは、オ
ペレーティング・システム・カーネルによってそのプロ
セスに割り当てられるプロセス識別子（ＰＩＤ）によっ
て識別される。プロセス３６０および３６２は、２つの
別々のウィンドウ内での１プログラムの２つの実行な
ど、２回同時に実行される同一のコードを使用すること
ができる。ＰＩＤは、同一のコードの別々の実行を区別
するのに使用される。

【００１４】このデバイス・ドライバは、オペレーティ
ング・システム・カーネル３１０の拡張であるグラフィ
ックス・カーネルである。グラフィックス・カーネル
は、グラフィックス・アダプタ・マイクロコード３８０
と直接に通信する。多くのグラフィックス・システムで
は、ＧＡＩまたは、ＧＡＩ層を使用しない場合にはＡＰ
Ｉが、デバイス・ドライバに初期要求命令を送ることに
よって、ＧＡＩまたはＡＰＩからアダプタ・マイクロコ
ードへの直接アクセスを要求することができる。さら
に、多くのグラフィックス・システムでは、アダプタ・
マイクロコードが、デバイス・ドライバに初期要求命令
を送ることによって、アダプタ・マイクロコードからＧ
ＡＩまたはＧＡＩを使用しない場合にはＡＰＩへの直接
アクセスを要求することもできる。以下、この両方の処
理を、直接メモリ・アクセス（ＤＭＡ）と称する。ＤＭ
Ａ、通常は、データの大きなブロックを転送する時に使
用される。ＤＭＡは、ＤＭＡをセットアップするための
デバイス・ドライバに対する初期要求以外にディスプレ
イ・ドライバを通る必要をなくすことによって、ホスト
・コンピュータとアダプタの間のより高速のデータ伝送
をもたらす。場合によっては、アダプタ・マイクロコー
ドがコンテキスト切換えを利用する。これによって、ア
ダプタ・マイクロコードは、アダプタ・マイクロコード
によって利用される現在の属性を置換できるようにな
る。コンテキスト切換えが使用されるのは、アダプタ・
マイクロコードが、そのアダプタ・マイクロコードが現
在使用しているものと異なる属性を使用するグラフィッ
クス・アプリケーションから命令を受け取ろうとしてい
る時である。コンテキスト切換えは、通常は、属性変化
を認識するデバイス・ドライバによって開始される。

【００１５】ブロック３００ないしブロック３４０は、
通常は、使用されるグラフィックス・アダプタのタイプ
から独立したソフトウェア・コード層である。ブロック
３５０ないしブロック３８０は、通常は、使用されるグ
ラフィックス・アダプタのタイプに依存するソフトウェ
ア・コード層である。たとえば、グラフィックス・アプ
リケーション・ソフトウェアが異なるグラフィックス・
アダプタを使用しなければならない場合、新しいＧＡＩ
とグラフィックス・カーネルとアダプタ・マイクロコー
ドが必要になるはずである。さらに、ブロック３００な
いしブロック３７０は、通常はホスト・コンピュータに
常駐し、ホスト・コンピュータによって実行される。し
かし、グラフィックス・アダプタ・マイクロコード３８
０は、通常は、グラフィックス・アダプタに常駐し、グ
ラフィックス・アダプタによって実行される。しかし、
一部の場合では、アダプタ・マイクロコードが、グラフ
ィックス・アダプタの初期設定中にホスト・コンピュー
タによってグラフィックス・アダプタにロードされる。

【００１６】通常のグラフィックス・システムでは、ユ
ーザが、グラフィックス・アプリケーションに、２次元
モデルまたは３次元モデルから画像を構築するように指
令する。ユーザはまず、光源の位置とタイプを選択す
る。次に、ユーザは、定義済みのオブジェクトやユーザ
定義オブジェクトの組から所望のモデルを作るようにア
プリケーション・ソフトウェアに指令する。各オブジェ
クトには、そのオブジェクトを記述する１つまたは複数
の同平面描画プリミティブを含めることができる。たと
えば、多数の三角形などの描画プリミティブの組を使用
して、オブジェクトの表面を定義することができる。そ
の後、ユーザは、モデルを眺めるためのウィンドウ内の
パースを提供し、これによって所望の画像を定義する。
その後、アプリケーション・ソフトウェアが、ＡＰＩ、
ＧＡＩ、およびＤＭＡを使用しない場合にはデバイス・
ドライバを介して、アダプタ・マイクロコードにオブジ
ェクトを記述した描画プリミティブを送ることによっ
て、モデルからの画像のレンダリングを開始する。その
後、アダプタ・マイクロコードは、ウィンドウ内で可視
でない描画プリミティブをクリッピングし（すなわち使
用しない）、残りの描画プリミティブのそれぞれをユー
ザによって与えられたパースから可視の画素に分解する
ことによって、グラフィックス・ディスプレイ上の画像
をレンダリングする。その後、これらの画素をフレーム
・バッファにロードするが、３次元モデルの場合にはデ
プス・バッファを併用することがしばしばである。この
ステップは、関連する描画プリミティブ、変数および画
素の数が原因で、非常に計算集中型である。フレーム・
バッファに格納され、グラフィックス・ディスプレイに
表示される結果の画像は、通常は、画素がどの描画プリ
ミティブまたはオブジェクトから導出されたかなどのオ
リジナルの情報を含まない。その結果、ウィンドウ、ユ
ーザのパース、モデル、照明などが変更された場合に
は、画像の一部または全体をレンダリングし直す必要が
生じる可能性がある。

【００１７】本発明の技法は、アダプタ・フレーム・バ
ッファに近いアダプタ・マイクロコードなど、多くの位
置で利用できるはずである。また、この手法は、比較的
高速であり、実施がかなり簡単である。さらに、本発明
は、像をレンダリングする前またはその後のいずれか
に、グラフィックス・アダプタがデータをグラフィック
ス・アプリケーション・ソフトウェアまで返すことによ
って、レンダリングされた画像がシステム・メモリにも
記憶されるグラフィックス・アプリケーション・ソフト
ウェアで適用することもできる。この手法は、おそらく
はより低速であるが、これによって、既存のグラフィッ
クス・アダプタにこの技法を使用できるようになるはず
である。本発明は、グラフィックス・アダプタ・プロセ
ッサ内のハードウェアで実施することもできる。この手
法は、非常に高速であるが、特殊なハードウェアを必要
とする可能性がある。当業者には明白なとおり、本発明
は、ホスト・コンピュータ内またはグラフィックス・ア
ダプタ内の多くの他の位置で適用できる。

【００１８】ほとんどのグラフィック・オブジェクト
は、一連の頂点を有する多角形として記述できる。図３
は、ウィンドウ４００に表示された大きな立方体４１
０、三角錐４２０および小さな立方体４３０を示す図で
ある。大きい立方体の３つの面と三角錐の１つの面だけ
が可視であり、小さな立方体はどの面も不可視である。
説明のため、これらの隠面の不可視の輪郭を、破線で図
示する。しかし、通常は、陰面やその不可視の輪郭は、
通常の３次元グラフィカル・システムでは表示されな
い。

【００１９】図４は、本発明の好ましい実施例でグラフ
ィックス・アダプタ・メモリ２３０内で使用されるデー
タ構造を示すブロック図である。

【００２０】オブジェクト可視性バッファ２３１を使用
して、画素位置のそれぞれについて、オブジェクトの識
別子とその相対深さを記憶する。すなわち、オブジェク
ト可視性バッファ２３１は、ＸＹ座標によって示される
ように、フレーム・バッファ（代替実施例ではその一
部）の各画素位置に対応する項目を有する。各項目に
は、オブジェクト識別子２３２とＺ値２３３が含まれ
る。各項目は、識別されるオブジェクトが、その画素位
置で、記憶されたＺ値または深さ値を有することを示
し、識別されたオブジェクトがその画素位置で可視であ
ることを示す。

【００２１】オブジェクト可視性リスト２３５は、オブ
ジェクト識別子バッファ内に少なくとも１つの項目を有
し、これによって、識別されたオブジェクトの少なくと
も１つの画素が可視であることが示されるオブジェクト
識別子のすべてのリストである。

【００２２】下記の流れ図で、オブジェクト可視性バッ
ファとオブジェクト・リストを生成する方法と、その後
これらを使用して、すばやく可視オブジェクトをレンダ
リングする方法を説明する。

【００２３】図５は、本発明の好ましい実施例による、
陰面と隠れオブジェクトを効率的に取り除く方法を示す
流れ図である。

【００２４】最初のステップ５００で、深さ値のそれぞ
れを最大深さにセットすることによって、オブジェクト
可視性バッファを初期設定する。さらに、オブジェクト
識別子のすべてを、０か、オブジェクト識別子として使
用されない値にセットすることができる。

【００２５】ステップ５０５で、プリミティブと称する
こともあるグラフィカル・オブジェクトを受け取り、元
の座標系からウィンドウ座標系に変換する。これは通
常、オブジェクト内のすべての頂点に対して行われる。

【００２６】ステップ５１０で、オブジェクトまたはプ
リミティブを複数のサブオブジェクトに分割することが
できる。サブオブジェクトのそれぞれを、下では別々の
オブジェクトとして記述する。たとえば、図３の立方体
４１０は、立方体の各側面を１つのオブジェクトとし
て、６つのオブジェクトに分割できる。その結果、ある
側面が不可視の場合、その側面がレンダリングされなく
なる。さらに、使用可能な識別子の所与の個数に対して
オブジェクトが多すぎる場合には、複数のオブジェクト
を単一のオブジェクトにグループ化して、その状況に対
処することができる。さらに、ハッシュ法を利用して、
複数のオブジェクトを同一の識別子にハッシュ化するこ
とができる。視野ボリュームを複数の均一または不均一
な部分空間に分割し、部分空間のそれぞれに識別子を割
り当てるという組合せの方法もある。さらに、非常に大
量のオブジェクトを扱う時などには、多重解（multires
olution）技法を使用することができる。オブジェクト
を上記のようにグループ化することができ、その後に、
これらのグループについて可視性を判定する。終了した
ならば、可視グループの各オブジェクトに、個別の識別
子を割り当て、可視性検出処理を繰り返す。これらの代
替案のそれぞれについて、このステップは任意選択であ
るが、本発明の最適化に有用である可能性がある。

【００２７】ステップ５１５で、各オブジェクトに識別
子を割り当てる。この識別子は、下で説明するように、
どのオブジェクトが可視であるかを追跡するのに使用さ
れる。

【００２８】ステップ５２０で、オブジェクトを画素に
スキャン変換する。すなわち、各オブジェクトを、Ｘ、
ＹおよびＺ値が決定された画素に変換する。本発明の性
質のゆえに、オブジェクトが可視であると判定されるま
では、カラー、照明などの実行と補間を行う必要はな
い。

【００２９】ステップ５２５で、オブジェクトの画素が
可視であるかどうかを判定する。これは、画素のＸＹ値
を使用してオブジェクト可視性バッファをアドレッシン
グすることによって達成される。その後、オブジェクト
画素のＺ値を、オブジェクト可視性バッファに記憶され
たＺ値と比較して、オブジェクト画素が可視すなわち視
点により近いかどうかを判定する。オブジェクト画素の
Ｚ値がオブジェクト可視性バッファ内のＺ値より小さい
場合、ステップ５３０で、オブジェクト画素のＺ値とオ
ブジェクト識別子の両方を、オブジェクト可視性バッフ
ァに記憶し、これによって、バッファに前に記憶された
値（初期設定された値である可能性もある）を置換す
る。もちろん、代替実施例では、より大きなＺ値が視点
に近いとみなすことができ、その結果、このテストは、
オブジェクト画素のＺ値がオブジェクト可視性バッファ
のＺ値より大きいかどうかによって変更されることにな
る。

【００３０】その後、ステップ５４０に進んで、これが
そのオブジェクトの最後の画素であるかどうかを判定す
る。そうでない場合、ステップ５２０に戻って、そのオ
ブジェクトの次の画素のＸ、ＹおよびＺ値を取得する。
そうである場合、ステップ５４５に進んで、（上で述べ
たようにステップ５１０を使用した場合に）これが所与
のオブジェクトの最後のサブオブジェクトであるかどう
かを判定する。そうである場合、ステップ５１５に戻っ
て、次のサブオブジェクトを処理する。そうでない場
合、ステップ５５０に進んで、これが処理すべき最後の
オブジェクトであるかどうかを判定する。そうでない場
合、ステップ５０５に戻って、次のオブジェクトを処理
する。

【００３１】ステップ５５０の回答が否定の場合、すべ
てのオブジェクトを処理し終えているので、好ましい実
施例のこの部分を終了する。この時点で、オブジェクト
可視性バッファには、可視のすべてのオブジェクトの識
別子と、これらのオブジェクトの可視の画素が含まれ
る。処理は、下の図６で説明する処理ステップに進む。

【００３２】図６は、本発明の好ましい実施例による、
可視のオブジェクトを判定するためのオブジェクト可視
性バッファの処理を示す流れ図である。最初のステップ
５６０で、オブジェクト可視性バッファの１項目を読み
取って、その項目に記憶されたオブジェクト識別子を得
る。ステップ５６５で、そのオブジェクト識別子が既に
オブジェクト可視性リストに含まれるかどうかを判定す
る。そうでない場合、ステップ５７０で、オブジェクト
識別子をリストに追加する。そうである場合、またはス
テップ５７０を処理した後に、処理はステップ５７５に
進む。ステップ５７５で、オブジェクト可視性バッファ
内のすべての項目を処理したかどうかを判定する。そう
でない場合、ステップ５６０に戻る。そうである場合、
オブジェクト可視性リストの処理が完了している。その
後、処理は下の図７で説明する処理ステップに進む。

【００３３】上の図３を参照すると、オブジェクト可視
性リストには、立方体４１０と三角錐４２０の識別子が
含まれていなければならない。しかし、立方体４３０は
不可視であるから、このオブジェクトの識別子がオブジ
ェクト可視性リストに含まれていてはならない。各オブ
ジェクトを複数のサブオブジェクトに分割する（すなわ
ち各オブジェクトの各面が１つのサブオブジェクトにな
る）場合、可視のサブオブジェクトだけが、オブジェク
ト可視性リストに含まれるはずである（すなわち、立方
体４１０の３つの面と三角錐４２０の１つの面）。その
結果、オブジェクトをレンダリングするためのレンダリ
ング計算の回数が少なくなっている。

【００３４】代替実施例では、オブジェクト可視性リス
トの各項目が、オブジェクトが可視である位置とそこで
の深さを示す、オブジェクト可視性バッファ内の各項目
を差すポインタを有する。

【００３５】図７は、本発明の好ましい実施例による、
可視オブジェクトの可視画素のレンダリングを示す流れ
図である。

【００３６】ステップ６００で、メモリからオブジェク
トを取得または検索する。ステップ６０５で、そのオブ
ジェクトがオブジェクト可視性リストに存在するかどう
かを判定する。そうでない場合、そのオブジェクトはレ
ンダリングされず、処理はステップ６５０に進んで、こ
れが最後のオブジェクトであるかどうかを判定する。ス
テップ６０５で存在する場合、処理は任意選択のステッ
プ６１０に進む（ステップ６１０を利用しない場合には
ステップ６１５に進む）。

【００３７】任意指定のステップ６１０では、そのオブ
ジェクトのどの部分が可視であるかを判定する。これ
は、オブジェクト可視性バッファの項目を検討して、ど
の画素が可視であるかを判定することによって達成でき
る。このステップは、図３の立方体４１０や三角錐４２
０の背面など、オブジェクトのうちの可視でない面を取
り除くのに有用である。このステップは、三角錐４２０
の前面のうちで立方体４１０の陰に隠れた部分など、あ
る面のうちの可視でない部分を取り除くのにも有用であ
る。どちらの場合でも、可視の頂点と画素だけを処理す
ることができ、オブジェクトの可視部分を反映するよう
に追加の頂点を追加することができる。

【００３８】ステップ６１５で、オブジェクトをレンダ
リングするために、オブジェクトの各頂点のカラー、照
明、テクスチャ、透明度などを計算する。おわかりによ
うに、これは、このような計算集中型の計算が実行され
る上で述べた処理の最初のステップである。

【００３９】ステップ６２０で、オブジェクトの各画素
のカラー、照明などの値を補間する。ステップ６２５
で、オブジェクト可視性バッファを検査することによっ
て、その画素が可視であるかどうかを判定する。そうで
ある場合、この画素値をフレーム・バッファに記憶す
る。ステップ６２５の回答が否定の場合またはステップ
６３０の後に、処理はステップ６４０に進む。ステップ
６２０をステップ６２５と共に実行すれば、補間計算の
回数を減らせることに留意されたい。

【００４０】ステップ６４０で、このオブジェクトの最
後の画素を処理したかどうかを判定する。そうでない場
合、ステップ６２０に戻る。そうである場合、ステップ
６５０に進む。ステップ６５０では、最後のオブジェク
ト（またはサブオブジェクト）を処理したかどうかを判
定する。そうでない場合、ステップ６００に戻る。そう
である場合、すべてのオブジェクトの処理が完了してい
る。

【００４１】代替実施例では、一時にオブジェクトの総
数のうちの一部だけを処理する多重パス手法を使用でき
る。オブジェクトのその部分は、上で説明したようにレ
ンダリングすることができ、その後、オブジェクトの別
の部分に対して上で説明した処理を繰り返す。これは、
オブジェクトの総数が識別子の数を超える場合に特に有
用であり、オブジェクト可視性バッファやオブジェクト
可視性リストを小さくすることができる。この手法は、
各プロセッサが他のプロセッサから独立にオブジェクト
の総数のうちの一部を処理する多重プロセッサ・システ
ムでも有用である。

【００４２】まとめとして、本発明の構成に関して以下
の事項を開示する。

【００４３】（１）それぞれにグラフィカル・オブジェ
クトのオブジェクト識別子が与えられる、深さを有する
複数の画素に、前記オブジェクトのそれぞれをスキャン
変換する手段と、所与の画素位置に関して前に記憶され
た深さより視点に近い画素深さを有する画素のそれぞれ
の深さとオブジェクト識別子とをメモリに記憶する手段
と、前記メモリに記憶されたオブジェクト識別子を有す
るグラフィカル・オブジェクトをレンダリングする手段
とを含む、ディスプレイ上に可視のグラフィカル・オブ
ジェクトをレンダリングする装置。（２）グラフィカル・オブジェクトのそれぞれに識別子
を割り当てる手段をさらに含む、上記（１）の装置。（３）前記割当手段が、複数のグラフィカル・プリミテ
ィブを単一のグラフィカル・オブジェクトにグループ化
する手段を含むことを特徴とする、上記（２）の装置。（４）前記割当手段が、グラフィカル・プリミティブを
複数のグラフィカル・オブジェクトに分割する手段を含
み、各グラフィカル・オブジェクトに異なるオブジェク
ト識別子が割り当てられることを特徴とする、上記
（２）の装置。（５）前記分割手段が、前記グラフィカル・プリミティ
ブを面によって分割する手段を含むことを特徴とする、
上記（４）の装置。（６）それぞれにグラフィカル・オブジェクトのオブジ
ェクト識別子が与えられる、深さを有する複数の画素
に、前記オブジェクトのそれぞれをスキャン変換するス
テップと、所与の画素位置に関して前に記憶された深さ
より視点に近い画素深さを有する画素のそれぞれの深さ
とオブジェクト識別子とをメモリに記憶するステップ
と、前記メモリに記憶されたオブジェクト識別子を有す
るグラフィカル・オブジェクトをレンダリングするステ
ップとを含む、ディスプレイ上に可視のグラフィカル・
オブジェクトをレンダリングする方法。（７）グラフィカル・オブジェクトのそれぞれに識別子
を割り当てるステップをさらに含む、上記（６）の方
法。（８）前記割当ステップが、複数のグラフィカル・プリ
ミティブを単一のグラフィカル・オブジェクトにグルー
プ化するステップを含むことを特徴とする、上記（７）
の方法。（９）前記割当ステップが、グラフィカル・プリミティ
ブを複数のグラフィカル・オブジェクトに分割するステ
ップを含み、各グラフィカル・オブジェクトに異なるオ
ブジェクト識別子が割り当てられることを特徴とする、
上記（７）の方法。（１０）前記分割ステップが、前記グラフィカル・プリ
ミティブを面によって分割するステップを含むことを特
徴とする、上記（９）の方法。（１１）処理すべきデータを記憶するためのメモリと、
メモリに記憶されたデータを処理するためのプロセッサ
と、ディスプレイ上に可視のグラフィカル・オブジェク
トをレンダリングするためのグラフィックス処理装置で
あって、それぞれにグラフィカル・オブジェクトのオブ
ジェクト識別子が与えられる、深さを有する複数の画素
に、前記オブジェクトのそれぞれをスキャン変換する手
段と、所与の画素位置に関して前に記憶された深さより
視点に近い画素深さを有する画素のそれぞれの深さとオ
ブジェクト識別子とをメモリに記憶する手段と、前記メ
モリに記憶されたオブジェクト識別子を有するグラフィ
カル・オブジェクトをレンダリングする手段とを含む前
記グラフィックス処理装置とを含むデータ処理システ
ム。（１２）グラフィックス処理システムが、グラフィカル
・オブジェクトのそれぞれに識別子を割り当てる手段を
さらに含む、上記（１１）のデータ処理システム。（１３）前記割当手段が、複数のグラフィカル・プリミ
ティブを単一のグラフィカル・オブジェクトにグループ
化する手段を含むことを特徴とする、上記（１２）のデ
ータ処理システム。（１４）前記割当手段が、グラフィカル・プリミティブ
を複数のグラフィカル・オブジェクトに分割する手段を
含み、各グラフィカル・オブジェクトに異なるオブジェ
クト識別子が割り当てられることを特徴とする、上記
（１２）のデータ処理システム。（１５）前記分割手段が、前記グラフィカル・プリミテ
ィブを面によって分割する手段を含むことを特徴とす
る、上記（１４）のデータ処理システム。

【００４４】

【発明の効果】本発明には、多数の長所がある。たとえ
ば、照明、カラー、テクスチャなどのレンダリング計算
は、オブジェクトが可視であると判定されない限り、実
行する必要がない。さらに、オブジェクトは、どのよう
な順序でも処理することができ、このため、以前の可視
性判定技法の制約の一部が克服される。さらに、本発明
は、オブジェクトの分割、オブジェクトのグループ化、
多重解処理および他の技法を含む、上で述べた多数の最
適化技法を扱える柔軟性を有する。

【００４５】上では具体的な実施例を参照して本発明を
完全に説明してきたが、他の代替実施例も、当業者には
明白であろう。したがって、上の説明は、本発明の範囲
を制限するものとして解釈してはならず、本発明の範囲
は、請求の範囲によって定義される。

【図面の簡単な説明】

【図１】本発明の好ましい実施例によって使用される典
型的なディジタル・コンピュータを示す図である。

【図２】通常はグラフィックス機能を実行するためホス
ト・コンピュータおよびグラフィックス・アダプタによ
って利用されるコードの層を示すブロック図である。

【図３】ウィンドウ４００に表示された大きな立方体４
１０、三角錐４２０および小さな立方体４３０を示す図
である。

【図４】本発明の好ましい実施例でグラフィックス・ア
ダプタ・メモリ内で使用されるデータ構造を示すブロッ
ク図である。

【図５】本発明の好ましい実施例による、陰面と隠れオ
ブジェクトを効率的に取り除く方法を示す流れ図であ
る。

【図６】本発明の好ましい実施例による、可視のオブジ
ェクトを判定するためのオブジェクト可視性バッファの
処理を示す流れ図である。

【図７】本発明の好ましい実施例による、可視オブジェ
クトの可視画素のレンダリングを示す流れ図である。

【符号の説明】

１００ディジタル・コンピュータ１０５コンピュータ・ボックス１１０主プロセッサ１２０主記憶１２５ハード・ディスク１３０入力装置１４０出力装置１５０グラフィックス出力装置１６０バス１７０入出力装置コントローラ１８０入出力装置１９０取外し可能媒体２００グラフィックス・アダプタ２２０グラフィックス・アダプタ・プロセッサ２３０グラフィックス・アダプタ・メモリ２３１オブジェクト可視性バッファ２３２オブジェクト識別子２３３Ｚ値２３５オブジェクト可視性リスト２４０フレーム・バッファ２５０ＲＡＭＤＡＣ（ランダム・アクセス・メモリ・
ディジタル・アナログ変換器）３００オペレーティング・システム３１０オペレーティング・システム・カーネル３２０ホスト・コンピュータ・マイクロコード３３０グラフィックス・アプリケーション３３２グラフィックス・アプリケーション３４０ＡＰＩ３４２ＡＰＩ３５０ＧＡＩ３５２ＧＡＩ３６０プロセス３６２プロセス３７０デバイス・ドライバ３８０グラフィックス・アダプタ・マイクロコード４００ウィンドウ４１０立方体４２０三角錐４３０立方体

Claims

【特許請求の範囲】

【請求項１】それぞれにグラフィカル・オブジェクトの
オブジェクト識別子が与えられる、深さを有する複数の
画素に、前記オブジェクトのそれぞれをスキャン変換す
る手段と、所与の画素位置に関して前に記憶された深さより視点に
近い画素深さを有する画素のそれぞれの深さとオブジェ
クト識別子とをメモリに記憶する手段と、前記メモリに記憶されたオブジェクト識別子を有するグ
ラフィカル・オブジェクトをレンダリングする手段とを
含む、ディスプレイ上に可視のグラフィカル・オブジェ
クトをレンダリングする装置。
【請求項２】グラフィカル・オブジェクトのそれぞれに
識別子を割り当てる手段をさらに含む、請求項１の装
置。
【請求項３】前記割当手段が、複数のグラフィカル・プ
リミティブを単一のグラフィカル・オブジェクトにグル
ープ化する手段を含むことを特徴とする、請求項２の装
置。
【請求項４】前記割当手段が、グラフィカル・プリミテ
ィブを複数のグラフィカル・オブジェクトに分割する手
段を含み、各グラフィカル・オブジェクトに異なるオブ
ジェクト識別子が割り当てられることを特徴とする、請
求項２の装置。
【請求項５】前記分割手段が、前記グラフィカル・プリ
ミティブを面によって分割する手段を含むことを特徴と
する、請求項４の装置。
【請求項６】それぞれにグラフィカル・オブジェクトの
オブジェクト識別子が与えられる、深さを有する複数の
画素に、前記オブジェクトのそれぞれをスキャン変換す
るステップと、所与の画素位置に関して前に記憶された深さより視点に
近い画素深さを有する画素のそれぞれの深さとオブジェ
クト識別子とをメモリに記憶するステップと、前記メモリに記憶されたオブジェクト識別子を有するグ
ラフィカル・オブジェクトをレンダリングするステップ
とを含む、ディスプレイ上に可視のグラフィカル・オブ
ジェクトをレンダリングする方法。
【請求項７】グラフィカル・オブジェクトのそれぞれに
識別子を割り当てるステップをさらに含む、請求項６の
方法。
【請求項８】前記割当ステップが、複数のグラフィカル
・プリミティブを単一のグラフィカル・オブジェクトに
グループ化するステップを含むことを特徴とする、請求
項７の方法。
【請求項９】前記割当ステップが、グラフィカル・プリ
ミティブを複数のグラフィカル・オブジェクトに分割す
るステップを含み、各グラフィカル・オブジェクトに異
なるオブジェクト識別子が割り当てられることを特徴と
する、請求項７の方法。
【請求項１０】前記分割ステップが、前記グラフィカル
・プリミティブを面によって分割するステップを含むこ
とを特徴とする、請求項９の方法。
【請求項１１】処理すべきデータを記憶するためのメモ
リと、メモリに記憶されたデータを処理するためのプロセッサ
と、ディスプレイ上に可視のグラフィカル・オブジェクトを
レンダリングするためのグラフィックス処理装置であっ
て、それぞれにグラフィカル・オブジェクトのオブジェクト
識別子が与えられる、深さを有する複数の画素に、前記
オブジェクトのそれぞれをスキャン変換する手段と、所与の画素位置に関して前に記憶された深さより視点に
近い画素深さを有する画素のそれぞれの深さとオブジェ
クト識別子とをメモリに記憶する手段と、前記メモリに記憶されたオブジェクト識別子を有するグ
ラフィカル・オブジェクトをレンダリングする手段とを
含む前記グラフィックス処理装置とを含むデータ処理シ
ステム。
【請求項１２】グラフィックス処理システムが、グラフ
ィカル・オブジェクトのそれぞれに識別子を割り当てる
手段をさらに含む、請求項１１のデータ処理システム。
【請求項１３】前記割当手段が、複数のグラフィカル・
プリミティブを単一のグラフィカル・オブジェクトにグ
ループ化する手段を含むことを特徴とする、請求項１２
のデータ処理システム。
【請求項１４】前記割当手段が、グラフィカル・プリミ
ティブを複数のグラフィカル・オブジェクトに分割する
手段を含み、各グラフィカル・オブジェクトに異なるオ
ブジェクト識別子が割り当てられることを特徴とする、
請求項１２のデータ処理システム。
【請求項１５】前記分割手段が、前記グラフィカル・プ
リミティブを面によって分割する手段を含むことを特徴
とする、請求項１４のデータ処理システム。