JPH0581438A

JPH0581438A - 三次元ソリツド対象物を表現する表示可能情報を発生する装置と方法

Info

Publication number: JPH0581438A
Application number: JP4002910A
Authority: JP
Inventors: David A Epstein; デービツド・アレキサンダー・エプスタイン; Jaroslaw R Rossignac; ジヤロスロウ・ロマン・ロシグナツク; Jeffrey W Wu; ジエフレイ・ウエンフオン・ウー
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1991-03-12
Filing date: 1992-01-10
Publication date: 1993-04-02
Anticipated expiration: 2010-12-25
Also published as: JPH07122908B2; EP0503251A3; US5402532A; EP0503251A2

Abstract

(57)【要約】【目的】三次元のソリッド対象物を表現する表示可能
情報を発生する装置と方法とを提供する。【構成】１つ以上のプリミティブ対象物からなるよう
に対象物をＣＧＳ表示法で表現するプロセッサ１２、１
６と、１つ以上のプリミティブ対象物を繰り返し評価し
てその表示可能面を決定するプロセッサ１８、２０とが
設けられる。深度間隔バッファ２０が、スキャン変換プ
ロセッサ１８の動作に応答して表示可能面の決定におい
て何ら変化をもたらすことなく、かつ評価プロセッサの
動作を終了させることなく所定数の繰返し評価の発生す
るときを検出する。ダングリング面やエッジを除去し、
一致した面を適正に扱うように公差を付した深度試験が
用いられる。深度試験の精度を向上させ、かつ製品から
の上に投影するピクセルを識別するためにピクセル中心
付けが採用される。補助シャドウバッファＺＳを用いる
２パススキャン変換技術を用いてシャドウイングを達成
する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、一般的にはコンピュー
タディスプレイ装置と方法とに関し、特にコンストラク
ティブ・ソリッド・ジオメトリ（ＣＧＳ）式を提供する
装置と方法とに関する。

【０００２】

【従来の技術】例えばパートあるいはツールを表示する
ソリッドモデルは例えば合併、交差およびセットの差の
ようなセットされた論理的ブール演算を介してサブソリ
ッドあるいはプリミティブボリュームを組み合わせるこ
とにより特定化しうる。ソリッドは、バイナリツリー表
示、即ちより正確にはバイナリ指向のルーテッド・アシ
クリック・グラフ（ｒｏｏｔｅｄａｃｙｃｌｉｃｇ
ｒａｐｈ）の形でコンピュータメモリ内に効率的に記憶
しうるセットされた論理的ブール式により表示される。

【０００３】図１は２個のサブソリッド２および３の合
併からなるソリッド１のバイナリツリー表示を示す。サ
ブソリッド３はブロックプリミティブ４と円筒形プリミ
ティブ５との差から構成されている。そのようなツリー
の形態はブール式（２）＋（（４）−（５））を分解す
ることにより直接得られる。ツリー（ソリッド１）のル
ートは、ブール式によって定義されたソリッドと関連し
ている。ツリーの内部ノードは、ブール演算に対応し、
かつサブソリッドと関連している。ツリーのリーフは、
プリミティブボリュームと関連しており、プリミティブ
ボリュームは比較的単純な代数的半空間の交差、即ち、
３つの空間座標の単純な多項式関数が非正の値を有して
いる空間領域であることが多い。例えば、原点に中心付
けされた半径Ｒの球は、ｘ² ＋ｙ² ＋ｚ²−ｒ² ≦０
の関数で定義される半空間である。任意に位置し、かつ
方向づけたプリミティブボリュームは、リジッドモーシ
ョン変換、回転と移行との組合せ、および都合のよい局
部座標系で定義された合同のプリミティブボリュームに
よって記述しうる。単純なプリミティブボリュームは、
例えば球、円筒体あるいは円錐体のようなそれらのタイ
プと、例えば半径、長さ、項角のような比較的少ない真
性パラメータによって表わすことができる。そのような
ツリーが、コンストラクティブ・ソリッド・ジオメトリ
表示として知られ、以下ＣＳＧと略記する。

【０００４】プリミティブボリュームの位置および寸
法、即ち真性パラメータは、ＣＳＧツリーによって表示
されるソリッドの全体ファミリにおける特定のメンバを
特徴化する若干の主要パラメータによって表現しうる。
従って、その結果のパラメータ化したＣＳＧ表示を都合
よく用いて、例えばその寸法が許容限度内で変動するパ
ーツの組立体をモデル化することができる。

【０００５】ＣＳＧの対象物は、その面が重なるプリミ
ティブから構成される。しかしながら、境界が重なった
ソリッドに対するブール演算により非規則化（ｎｏｎ−
ｒｅｇｕｌａｒｉｚｅｄ）セットを作り出しうる。した
がって、ＣＳＧ演算を常に規則化（ｒｅｇｕｌａｒｉｚ
ｅｄ）されたソリッドを作るように都合よく修正してき
た。しかしながら、これらの修正は付加的な処理を必要
とする。

【０００６】境界評価を介してＣＳＧソリッドをシェー
ディングすることは一般的に高価なデータ処理手順であ
る。光線投影によりＣＳＧモデルにシェーディングする
効率的で直接的な方法が、フアセット（ｆａｃｅｔ）し
たモデルや、二次の半空間のブール組合せに対して使用
しうる。しかしながら光線投影は、多数の光線−表面交
差を計算することを含み、高次の代数あるいはパラメト
リックな表面が含まれる場合は特に非効率である。

【０００７】面評価が光線−表面公差より速いという点
において、適応性のあるモザイクを用いるスキャン変換
技術が境界モデルのシェーディングに度々使用される。
モデルの可視面を自動的に選択するためにハードウェア
深度バッファ（ｚバッファ）が用いられる。ＣＳＧソリ
ッドの面は直接は利用できないので、ソリッド上に位置
するプリミティブ面の部分を選択するトリミング処理と
深度バッファ可視性試験を組み合せる必要がある。

【０００８】この選択のソフトウエア実行は本発明の発
明者の一人によりハードウェア深度試験と組み合わされ
ており、Ｊ．Ｒ．ＲｏｓｓｉｇｎａｃおよびＡ．Ａ．
Ｇ．Ｒｅｑｕｉｃｈａによる１９８６年９月のＩＥＥＥ
のＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓａｎｄＡｐｐ
ｌｉｃａｔｉｏｎｓのｖｏｌ．６，Ｎｏ．９の２９〜３
９頁に記載の「Ｄｅｐｔｈｂｕｆｆｅｒｉｎｇｄｉ
ｓｐｌａｙｔｅｃｈｎｉｑｕｅｓｆｏｒｃｏｎｓ
ｔｒｕｃｔｉｖｅｓｏｌｉｄｑｅｏｍｅｔｒｙ」と
いう名称の論文に説明されている。この技術は、一般的
にプリミティブＡの正面を向いた面上の点Ｐを対応する
ピクセルのｚバッファに記憶された深度と比較すること
を含む。もしＰがｚバッファに記憶されているものの前
方にあるとすれば、それは「分類される」、即ちＣＳＧ
グラフに対して試験される。ソリッドの境界上の点はｚ
バッファに提供される。ソリッドの境界の内側あるいは
外側の点は棄てられる。ソリッドの内側の点はｚバッフ
ァ可視性試験により自動的に不合格とされる。従って、
ＰをＡのＩゾーンに対して分類することによりグラフに
おけるあるプリミティブに対するＰの試験を回避するこ
とにより性能が向上する。ＩゾーンはオリジナルのＣＳ
Ｇグラフのノートのサブセットの交差である。もしＰが
ＡのＩゾーンの内側に位置しているとすれば、それは最
終のソリッド上が、最終ソリッドの内側に位置する。

【０００９】スキャン変換法は、観察方向に沿って個々
のスクリーンピクセル上に投影される表面の点を発生さ
せる周知の技術である。観察者から離れる方向に観察方
向に沿って計算された三次元の点の深度は、対応するピ
クセルと関連したｚバッファメモリに記憶しうる。その
深度があるピクセルのｚバッファに記憶されている三次
元の点は、プリミティブの境界をスキャン変換し、かつ
試験されている点の後ろにあるプリミティブの表面の層
の数のパリティを計算することにより、プリミティブに
対して分類される。このことは、試験した点として同じ
ピクセル上に投影される表面の点の深度値をｚバッファ
に記憶された値に対して比較することにより達成され
る。スキャンされた点の深度が、記憶された点より大き
い度毎にそのピクセルと関連したバイナリ・パリテイ・
フラッグが反転される。

【００１０】ＣＳＧ式に対してある点を分類するには、
その点を全てのプリミティブに対して分類するだけでは
十分ではない。点とプリミティブとの分類結果をさらに
ブール式に従って組み合わせる必要がある。例えば交差
のようなある単純なブール式に対しては、その結果をブ
ールの結果の論理積として公式化しうるので記憶は必要
でない。分離アルゴリズムはプリミティブをいずれの順
序で処理してもよく、結果の１つが「偽」であれば直ち
に停止する。このことは、例えば点がブール交差におけ
るプリミティブから外れていた場合にいえる。もし全て
のプリミティブが処理され、しかも「偽」という結果が
判明しないとすれば、点はブール式により定義されたソ
リッドの内側にある。

【００１１】しかしながら、より複雑なＣＳＧ式を評価
することにより、中間のバイナリ結果に対して大量の一
時的な記憶が必要とされうるという点で問題を提起す
る。通常一時的な記憶に対してスタック機構が使用され
る。必要なスタックの深さはＣＳＧグラフの深さに到達
しうる。

【００１２】ピクセル当りのシステムメモリの量が制限
されているという点で、各ピクセルにおいて任意の深さ
のスタックを提供することは実用的でない。しかも、必
要なプリミティブスキャン変換の数を最小とするために
全てのピクセルに対して並列に分類演算を実行すること
が望ましい。

【００１３】Ｊ．Ｇｏｌｄｆｅａｔｈｅｒ他による、１
９８９年５月刊ＩＥＥＥＣＧ＆Ａ，ｖｏｌ．９，Ｎｏ．
３，２０〜２８頁の「ＮｅａｒＲｅａｌ−ＴｉｍｅＣ
ＳＧＲｅｎｄｅｒｉｎｇｕｓｉｎｇＴｒｅｅＮ
ｏｒｍａｌｉｚａｔｉｏｎａｎｄＧｅｏｍｅｔｒｉ
ｃＰｒｕｎｉｎｇ」という名称の技術は、ＣＳＧ式
を、プリミティブインスタンス（ｉｎｓｔａｎｃｅ）を
何回も重複しうることによって数個の積で現われる著し
く大きい積和形式へ変換することにより、メモリの限界
を回避している。冗長（空の）積を排除する技術も論じ
られている。この技術においては、プリミティブ面
は、プリミティブスキャン変換を繰返し用いることによ
り適当な積に対してまずトリムされる。その結果のトリ
ムされた面は、次いで最終深度バッファを用いて併合さ
れ全ての積の間で最前方の面を選択する。可視表面選択
とソリッドに対して内側の面を棄てることの双方に対し
てｚバッファが用いられる。

【００１４】しかしながら、積は干渉し、従って積の前
面がソリッド上に位置しない可能性のあることが注目さ
れる。

【００１５】その結果、ＣＳＧ処理に対する投影方法に
関して積の可視前面を決定するための効率的かつ正確な
方法に対する必要性がある。深度バッファ比較がｚバッ
ファの限定された分解能の範囲内で行われるという点に
おいて、数個のプリミティブの面が重なるか、あるいは
ピクセルの光線がそれらの共通のエッジに極めて近接し
て２つの隣接面を交差するといった状況を正確に対処す
る別の必要性がある。これらの場合の双方に対して、ス
キャン変換の丸めの誤差により、計算された深度値は正
確でないかもしれない。しかしながら、これらの固有の
不正確さにもかかわらず、ＣＳＧ式の規則化したバージ
ョンに対応する表示可能のイメージを発生させる必要性
は残る。ソリッドは、それが三次元のユークリッド空間
に関するその内側の位相閉包に等しい場合規則化される
ものと考えられる。従って、規則化したソリッドは、定
義により何らダングリング（ｄａｎｇｌｉｎｇ）エッジ
あるいは面を有さない。このように、数個のプリミティ
ブ上に位置するが、最終結果においていずれの三次元ボ
リュームも境界付けしない面あるいはエッジは表示すべ
きでない。

【００１６】以下の米国特許はイメージの表示またはＣ
ＳＧあるいはこれらの双方の提供の種々局面を教示して
いる。Ｔ．Ｙ．Ｓｈｅｎへの米国特許第４，６０９，９
１７号（１９８６年９月２日付）は、ｚバッファを用い
た一般に使用されるグラフイックアーキテクチャの変形
を開示している。Ａ．Ｐ．Ｒｏｃｋｗｏｏｄへの米国特
許第４，６２５，２８９号（１９８６年１１月２５日
付）は、表面上の点が該表面を記述する関数をサンプリ
ングすることによって発生する面表示の方法を開示して
いる。サンプリングによってカバーされた各ピクセルに
対して観察者に最も近いサンプリングした点を見つける
ためにｚバッファが採用されている。１９８８年４月５
日Ｃｈｒｉｓｔｅｎｓｅｎ他に発行された米国特許第
４，７３６，３０６号においては境界からＣＳＧへの変
換技術を開示している。１９８８年４月１２日発行のＧ
ｏｌｄｗａｓｓｅｒ他への米国特許第４，７３７，９２
１号においては、ピクセルデータを表示するためのマル
チプロセッサシステムを開示している。詳しくは、数台
のプロセッサによって並列に計算されるイメージ（強度
と深度）を併合するハードウエアアーキテクチャが提案
され、リアルタイムで個々のイメージを移動させる可能
性があり、またこのシステムにおいてシャドウイングプ
ロセッサも設けられている。１９８９年４月１１日Ｔ．
Ｗ．Ｓｅｄｅｒｂｅｒｇに発行された米国特許第４，８
２１，２１４号においては三変量ベクトル有理多項式を
用いることによりモデルの自由形式変形を得る技術を開
示している。この方法はＣＳＧソリッドモデリングシス
テムに適用可能といわれている。１９８９年４月２５日
Ｄ．Ｍ．Ｍｅｒｚに発行された米国特許第４，８２５，
３９１号において深度メモリの代りにスパン比較が用い
られている可視表面アーキテクチヤを開示している。１
９８９年８月８日Ｊ．Ｌｏｐｅｚ他に発行された米国特
許第４，８５５，３９８号は多角形の可視線を表示する
方法を開示している。ｚバッファは、多角形の稜に対す
る特殊なｚ値で初期化される。多角形は、ｚバッファへ
ラスタ化され、依然として特殊なｚ値を有するピクセル
のみが適当に色付けされる。１９９０年３月６日Ｃ．Ｐ
ｒｉｅｍに発行された米国特許第４，９０７，１７４号
は、どのグラフイック表示ウインドウにｚバッファが専
用とされているかを識別するためにｚバッファの一部に
おいてある範囲のｚ深度を使用することを開示してい
る。

【００１７】最後に、１９８９年８月１５日Ｐ．Ｑｕａ
ｒｅｎｄｏｎに発行された米国特許第４，８５８，１４
９号は、ＣＳＧ対象物を提供するソリッドモデリングを
開示している。立方体がいずれのプリミティブの境界と
も交差しなくなるまで、あるいは立方体が現在の分解能
より小さくなるまで領域（ユニバース）が帰納的に段々
と小さい立方体に分解される。この特許は本発明により
解決された問題の解に関するものの、その方法は効率的
でなく、ハードウエア深度バッファを採用していない。

【００１８】研究者は、プリミティブの面を、ある積に
おける全てのプリミティブの全ての前面と後面と比較す
ることによりプリミティブ面をトリミングするためハー
ドウエアアルゴリズムを実行した。各ピクセルにおいて
独立して比較が行われ、深度試験、マスク、計数および
各ピクセルで実行された論理ビット演算を含む。この技
術は単に２つの追加のバッファを用いるのみである。ア
ルゴリズムは、各ピクセルにおいてローカルメモリを備
えた１つのプロセッサを有するピクセル−パワーグラフ
ィックシステムにおいて実行されてきた。この方法は、
Ｊ．Ｇｏｌｄｆｅａｔｈｅｒ他による、１９８９年５月
のＩＥＥＥＣＧ＆Ａ，ｖｏｌ．９，Ｎｏ．３、２０〜
２８頁に既に述べた論文「ＮｅａｒＲｅａｌ−Ｔｉｍ
ｅＣＳＧＲｅｎｄｅｒｉｎｇｕｓｉｎｇＴｒｅ
ｅＮｏｒｍａｌｉｚａｔｉｏｎａｎｄＧｅｏｍｅｔ
ｒｉｃＰｒｕｎｉｎｇ」に記載されている。

【００１９】本発明者の中のある者を含むその他の研究
者は、積を処理するためのさらに効率的な技術を開発し
た。この技術は、「トリックル（ｔｒｉｃｋｌｅ）」ア
ルゴリズムと称され、一般的に、Ｇｏｌｄｆｅａｔｈｅ
ｒ他の技術より少ないプリミティブスキャン変換および
バッファ併合演算を必要とする。その結果この技術は、
出現するグラフイックワークステーションで実行するの
により適したものと考えられている。トリックルアルゴ
リズムは、Ｄ．Ａ．Ｅｐｓｔｅｉｎ，Ｆ．Ｗ．Ｊａｎｓ
ｅｎおよびＪ．Ｒ．Ｒｏｓｓｉｇｎａｃによる１９８９
年１１月のＩＢＭＲｅｓｅａｒｃｈＤｉｖｉｓｉｏ
ｎのＲＣ１５１８２（＃６７６２９）の研究報告「Ｚ
−ｂｕｆｆｅｒＲｅｎｄｅｒｉｎｇｆｒｏｍＣＳ
Ｇ：ｔｈｅＴｒｉｃｋｌｅＡｌｇｏｒｉｔｈｍ」に
記載されている。

【００２０】Ｇｏｌｄｆｅａｔｈｅｒ他により記述され
た技術と、Ｅｐｓｔｅｉｎ他により記述された技術の双
方共、プリミティブの隠面の一連の層を発生させ、かつ
トリミングすることにより非凸状のプリミティブを処理
する。

【００２１】トリックルアルゴリズムの重要な特徴は、
（観察者からは離れる方向で）前から後ろへの順序で各
ピクセルにおいて独立して製品のプリミティブ面を処理
することである。この順序により本技術では可視点即ち
バックグラウンドが製品の投影によりカバーされる各ピ
クセルに到来するやいなや所与の製品の処理を停止する
ことができるようにする。さらに、一方のプリミティブ
面層から別の層へ（観察者から離れる方向に）「より深
く」動いている間にトリックルアルゴリズムは、製品に
おける少なくとも１つのプリミティブから外れているの
で、製品上に位置できないことが明らかなプリミティブ
−面層を有利にスキップする。

【００２２】トリックルアルゴリズムは３つの、深度お
よび強度バッファを用いている。これらは、可視表面選
択に使用される標準的な深度および強度バッファと、２
つの深度バッファと２つの強度バッファとに複合した１
つの付加的な深度−強度バッファとである。トリックル
アルゴリズムは、スクリーンの各象限に対して１度、４
つのパスを通るように構成しうることを注目すべきであ
る。スクリーンを４象限に分割することによって、グラ
フィックワークステーションで通常使用しうる１つの深
度バッファと２つの強度バッファという標準的な構成に
対してさえも、トリックルアルゴリズムに対して十分な
バッファを提供する。

【００２３】

【発明が解決しようとする課題】従って本発明の目的
は、ＣＳＧ表示ソリッドの処理をさらに改良するために
トリックルアルゴリズムをさらに改良、向上させること
にある。

【００２４】本発明の別の目的は、ソリッド対象物をＣ
ＳＧ表示するための効率的で正確なシャドウイング技術
を提供することである。

【００２５】本発明の別の目的は、製品の可視前面を決
定し、数個のプリミティブ面が重なっているか、あるい
はピクセルの光線が共通のエッジに近い点において２つ
の隣接する面と交差する状態に正確に対処する効率的な
方法であって、小さい交差値を採用してスキャン変換中
丸めの誤差の影響を除去する方法を提供することであ
る。

【００２６】本発明の別の目的は、それ以上のスキャン
変換が不要であることが決定されると一時製品のプリミ
ティブのスキャン変換を停止させる方法を提供すること
である。

【００２７】本発明のさらに別の目的は面を提供する
（即ちスキャン変換）ことの精度を上げる方法であっ
て、その上に表面の頂点サブセットが突出するピクセル
の中心における表面の正確な深度値を決定することを採
用している方法を提供することである。

【００２８】

【課題を解決するための手段】まず積和の形に分解され
るＣＳＧ式を提供する装置と方法とにより前述およびそ
の他の問題は克服され、本発明の目的が実現される。各
プリミティブの面は前方に向いているか、後方に向いて
いるかで分類され、複数の深度バッファ（ｚバッファ）
にスキャンされる。本方法を繰り返す毎に、前方に向い
ている面が検討され、もし製品上に無いとその背後に位
置している他の前方に向いている面と置換する。

【００２９】本方法は、各ピクセルの可視面が得られる
と各製品の処理を終了する。次いで各製品の可視前面は
従来の隠面除去技術を用いて最終のｚバッファに併合さ
れる。

【００３０】各ピクセルの製品のプリミティブ面を独立
して処理することにより、本方法は、従来技術では必要
とされた境界評価を排除し、比較的単純な試験を使用し
て各ピクセルに対して、ある製品の境界に位置している
プリミティブ面の一部を決定する。ピクセルのための正
しい面は、前面の背後にあり、かつ製品の交互の正のプ
リミティブに対する後面の前にあり、さらに各負のプリ
ミティブに対して対向関係を保っている前面と考えられ
る。

【００３１】本方法の別の利点は、製品の他のプリミテ
ィブの外側に位置するあるプリミティブ面をスキップし
うるという点において製品の最も遠い前面から移動する
ことにより得られる。処理は、その上に製品が突出する
ピクセルのいずれにおいても何ら変化がないとすれば最
終パスにおいて終了する。

【００３２】さらに、本方法は、深度試験中およびまた
最終のｚバッファへのビット併合演算中スキャンされた
面の深度から交差値を差し引く。その結果、一致した面
が正確に扱われ、かつソリッドはダングリングエツジヤ
クラックを除去することにより規則化される。本方法は
また、各ピクセルにおいてｚ深度を正確に決定するため
にサブピクセル修正を用い、かつ面が所与のピクセルに
突出しているか否か決定するためにピクセル中心試験を
採用している。

【００３３】本発明の一実施例によれば、三次元のソリ
ッド対象物を表現する表示可能情報を発生させる装置と
方法が開示されている。本装置は、１つ以上のプリミテ
ィブ対象物から構成されるように前記対象物をコンスト
ラクティブ・ソリッド・ジオメトリ表示により表示する
プロセッサを含む。本装置はさらに、１つ以上のプリミ
ティブ対象物を繰返し評価してその表示可能面を決定す
るプロセッサを含む。深度間隔バッファが、スキャン変
換プロセッサの演算に応答して、表示可能面の決定にお
いて何ら変化を発生させることなく所定回数の繰返し評
価が行われたときを決定する。深度間隔バッファは評価
プロセッサの演算を終了させる信号を発生する。

【００３４】本発明の装置と方法とは、ダングリング面
やエッジを除去し、一致した面を適正に扱うように公差
を付けた深度試験を採用している。深度試験の精度を向
上させ、製品がその上に投影するピクセルを識別するた
めに、ピクセル中心付けを採用している。

【００３５】また、本発明の装置には、プリミティブ対
象物の面上の一点から光源の平面への投影の、対象物を
照射する光源の平面を基準にした深度を記憶するための
補助シャドウ深度バッファを設けることができる。補助
シャドウバッファと関連して２パスのスキヤン変換技術
を用いてシャドウイングが達成される。

【００３６】本発明の前述並びにその他の特徴は、添付
図面と関連して以下の本発明の詳細説明を読めばより明
らかとなる。

【００３７】

【実施例】図２を参照すれば、ＣＳＧ提供ならびに表示
パイプラインシステム１０の実施例がブロック線図の形
態で示されている。例えば、ＣＡＤシステムのようなア
プリケーションプロセッサ１２がＣＳＧデータをＣＳＧ
記憶装置即ちデータベース１４に提供する。このＣＳＧ
データは、モデル化されている三次元のソリッドを表わ
す。また、アプリケーションプロセッサ１２は、ＣＳＧ
プリミティブをＣＳＧ記憶装置１４から受け取り、そこ
からプリミティブの面を生成する製品抽出プロセッサ１
６に指令を提供する。カウンタ２４ａと比較器２４ｂと
が設けられ、ＴＥＲＭＩＮＡＴＥ（終了）信号をアプリ
ケーションプロセッサ１６に対して発生する。ＴＥＲＭ
ＩＮＡＥ信号を発生するカウンタ２４ａと比較器２４ｂ
との動作は以下詳細に説明する。面をスキャン変換する
スキャン変換プロセッサ１８にプリミティブ面が提供さ
れる。本発明の一局面によれば、スキャン変換プロセッ
サ１８はスキャン変換演算中以下に記述するようにピク
セル中心法を採用している。スキャン変化プロセッサ１
８の出力は、プリミティブ面がその上に投影される各ス
クリーンピクセルに対するｘ，ｙ，ｚの位置情報であ
る。また、スキャン変換プロセッサ１８から、赤
（Ｒ）、緑（Ｇ）および青（Ｂ）のにような表現された
ピクセル色情報が出力される。スキャン変換プロセッサ
１８の出力は深度間隔バッファプロセッサ（ＤＩＢ）２
０に提供される。

【００３８】ＤＩＢ２０は、アプリケーション１２から
指令を受け取り、以下詳述する疑似コード表示に従って
ＤＩＢ２０内でのデータの流れや処理を制御するコント
ロールブロック２２を含む。ＤＩＢ２０は、複数のｚバ
ッファ（Ｚ３、Ｚ２）と、関連の強度バッファ（Ｉ３、
Ｉ２）とを含む。ＤＩＢ２０により達成される深度比較
は、本発明の別の局面に従って、スキャン変換プロセッ
サ１８内で発生する計算の丸めの誤差を補償するように
交差がついている。またＤＩＢ２０には後述のように変
更フラッグ（ｃｆ）２３と前方に向いたフラッグ（ｆ
ｆ）２５とが設けられている。

【００３９】ＤＩＢ２０の出力は、製品の可視即ち表示
可能の前面を表現したデータであって、このデータは第
３の深度バッファ（Ｚ１）と第３の強度バッファ（Ｉ
１）とに提供される。Ｉ１はピクセル平面メモリを形成
し、その中味はディスプレイ・スクリーン２６上で表示
される。例えば、Ｚ１は各スクリーンピクセルに対する
深度情報を表現するための多数の２４ビットメモリロケ
ーションからなる。Ｉ１は多数の２４ビットメモリロケ
ーションからなり、その各々は３色（Ｒ，Ｇ，Ｂ）の強
度を表示するために３つのバイトに仕切られる。このよ
うに、各スクリーンピクセルに対して、対応する２４ビ
ットＺ１メモリロケーションと、対応する２４ビットＩ
１メモリロケーションとがある。バッファＺ３，Ｚ２，
Ｉ３及びＩ２も同様に構成されている。

【００４０】アプリケーション１２からＤＩＢ２０に送
られた指令は、バッファを初期化し、スキャン変換のた
めの動作をセットアップし、かつバッファ間の動作を実
行する指令を含む。例えば、ＩＮＩＴＢＵＦＦＥＲ
（１，ＭＡＸＤＥＰＴＨ，ＢＬＡＣＫ）のような指令
は、バッファ１を、Ｚ１に対する最大の深度値と、Ｉ１
に対するバックグランドの色とで初期化する。典型的な
バッファ演算指令はフォーマットＣＯＰＹＢＵＦＦＥＲ
（３，２，ＴＲＵＥ，′ＮＥ′，０）を有し、これは、
（ｆｆ）２５が真で、Ｚ２がＺ３＋ｅｐｓ（以下説明す
る交差値）に等しくないときはいつでもバッファ３をバ
ッファ２にコピイする。この指令は、後記の疑似コード
表示の表−１の２６〜３０行に対応する。スキャン変換
演算をセットアップする指令は、交差値を特定の値や、
後記の疑似コード表示の表−１の２３〜３４行における
スキャンした値の受領したものとしてバッファ３をセッ
トするＳＣＡＮＩＮＴＯ（３）のような指令とを含
む。終了条件は、疑似コード表示の表−１の１２行にお
けるように（ｃｆ）フラッグ２３をリセットするために
指令ＳＥＴＣＨＡＮＧＥＦＬＡＧ（ＦＡＬＳＥ）を
用いることにより試験しうる。各プリミティブスキャン
変換の後、ＩＦＧＥＴＣＨＡＮＧＥＦＬＡＧ（）
ＴＨＥＮｋ＝０のような指令は、疑似コード表示の
表−１の３１行におけるようにカウンタ２４ａをリセッ
トする作用を有する。

【００４１】製品抽出ブロック１６に向けられた指令の
例は、ＣＳＧツリーにおける製品の合計数をカウントす
る指令Ｎ＝ＣＯＵＮＴＰＲＯＤＵＣＴＳ（ＣＳＧＴＲ
ＥＥ）と、製品ｋがその表がバッファ２において構成さ
れるまでそのプリミティブをバッファ３へ繰り返しスキ
ャン変換することにより処理されるようにする指令ＲＥ
ＮＤＥＲＰＲＯＤＵＣＴ（ｋ）とを含む。これらの種
々の指令の演算は以下の説明において明らかとなる。

【００４２】高レベルにおいてはトリックルアルゴリズ
ムの演算は以下の疑似コードセグメントのように表現し
うる。

【００４３】バッファ１を初期化させ、各製品Ｐに対し
て、バッファ２におけるＰの前方を計算し、その結果
を、可視面を選択してバッファ１に併合する。

【００４４】バッファ１（Ｚ１とＩ１）は製品のユニオ
ンの可視面を選択するために使用される。各製品の可視
前面は、別の疑似コードセグメントにおいて以下要約す
るようにバッファ２、ＤＩＢ２０を用いて相前後して計
算される。

【００４５】Ｚ２をバッファグランドに対して初期化
し、初期化の未だの間にＰのプリミティブＱを循環し、
かつＺ２の後ろに位置するＱの次の面をＺ３へ計算し、
Ｑの次の面が前方に向いているピクセルにおいてＺ３を
Ｚ２へコピイする。

【００４６】トリックルアルゴリズムは、Ｚ２における
点が深度においてプリミティブＱのの前面をすぐ先行す
る場合、前記点はＱの外側、従って製品の外側に位置す
るという点において特に効果的である。さらに、試験し
た点と、Ｑ上の対応する前方点との間の間隔もＱの外
側、従って製品の外側にある。

【００４７】図３から判るように、観察点から離れる方
向にＺ軸に沿って前進するとき、点ｐは、現在の製品の
プリミティブＱに位置することが判り、その深度はＺ２
に記憶される。プリミティブＱはスキャン変換され、Ｑ
上のｑの深度はＺ３に記憶される。それは、Ｑ上の点ｑ
がｐによって隠れる（深度に関して）Ｑ上の最初の点で
あるためである。点ｑはＱに対する前方点である。従っ
てセグメント（ｐ，ｑ）はＱの外側にあり、従って製品
の外側にある。次にトリックルアルゴリズムはｐの深度
と強度とをＺ２とＩ２とに記憶する。製品における別の
プリミティブ上の点ｒは、それがｐとｑとの間に位置
し、従って製品上にないのでスキップされる。

【００４８】システム１０を構成する各種プロセッサの
動作を記述する疑似コード表示を以下説明する。前述の
トリックルアルゴリズムに対する著しい改良が、シルエ
ットエッジの投影の近傍における一致したプリミティブ
面とピクセルとを含み、「オン−オン」ケースとも称さ
れる全ての単一ケースに対して正しい処理を提供する公
差付きの深度試験によって達成される。トリックルアル
ゴリズムに対するその他の著しい改良はシステム１０の
動作についての以下の説明の間に明らかとなる。

【００４９】以下現れる全ての行番号参照符号は、以下
直ちに提供される改良トリックルアルゴリズムの疑似コ
ード表示を言及する。

【００５０】前述の改良トリックルアルゴリズムの疑似コード表示に
対して、深度バッファＺ１と強度バッファＩ１の各ピク
セルに対する初期化により、これら２つの要素をそれぞ
れ最大深度と、選定したバッファグランドの色とに設定
する（表−１の１〜３行）。次に、各製品に対して、Ｚ
２が最小深度まで初期化され、Ｉ２がバックグラウンド
の色に対して初期化される。次に、製品の可視前面が計
算され、かつ深度バッファＺ２と強度バッファＩ２に記
憶される（表−１の９〜３１行）。最終的に、結果が、
現在の製品の前面が先に処理された製品の前方に位置し
ているときは常にＺ１に併合される。（表−１の３３〜
３５行）。

【００５１】詳細には、製品の可視前面を計算するため
に本方法は以下の通り進行する。図２のカウンタ２４ａ
に対応するカウンタｋがまず−１に初期化される（表−
１の９行）。本発明によれば、カウンタ２４ａは、Ｚ２
に影響を与えることなく処理される現在の製品のプリミ
ティブの数をカウントするために採用されている。カウ
ンタ２４ａの値が製品のプリミティブの数と等しくなる
ように増分されるとき、現在の前面を表示するピクセル
に何ら変化の起らなかったことが示される。カウンタ２
４ａの出力は、カウンタの出力が製品のプリミティブの
数と比較される比較器２４ｂに提供される。カウンタ２
４ａの中味がプリミティブの数と等しいとき、ＴＥＲＭ
ＩＮＡＴＥ信号がアプリケーション１２に対して発生
し、スキャン変換（表−１の１０〜３１行のＵＮＴＩＬ
ループ）を停止させ、これにより製品に含まれる全ての
プリミティブの後続の全数スキャン変換を終了させる。
もし製品に唯一のプリミティブがあるとすれば単一のプ
リミティブは規則化効果を適正に発生させるため２回の
みスキャンされる。

【００５２】最悪の場合、本方法は、その製品の全ての
プリミティブにおいて「層」がある限り概ね何回でも製
品の各プリミティブをスキャン変換する。各層が、Ｚ２
に対して一時的な点を発生しうるという点において、Ｚ
２の点が製品の外側にあることを示すために製品の１つ
のプリミティブを除いて全てをスキャンする必要があ
る。本明細書で採用している層の概念は、プリミティブ
のボリュームに対する、ｚ軸に平行の光源を交差させる
ことにより得られる分解したセグメントに対応する。

【００５３】しかしながら、典型的なテースに対して、
本方法の動作は早期段階でのループ処理を停止させる。
ｋは−１（表−１の行９）に初期化され、単一のプリミ
ティブを有する製品の適正な処理を保証することが注目
される。

【００５４】ループ内において、変更フラッグ（ｃｆ）
２３が表−１の１２行において初期化され、表−１の３
０行において更新され、Ｚ２が前進したか、かつカウン
タ２４ａが零にリセットされたか否かを決定する（表−
１の３行）。もし変更が示されるとすれば、カウンタ２
４ａはリセットされ、その結果、ループを通るその特定
のパス対するＴＥＲＭＩＮＡＴＥ信号を発生させない。

【００５５】内側ループ（表−１の１３〜３１行）は製
品のプリミティブ（Ｑ）に対して実行され、プリミティ
ブのリストは一貫した円形の態様で処理される（表−１
の１３行）。まずＺ３、Ｉ３および前方に面したフラッ
グ（ｆｆ）２５が初期化される（表−１の１４〜１７
行）。そのピクセルの前方に面したフラッグを保持する
ために各ピクセルと関連した１ビットの記憶がある。も
し現在のプリミティブが正、即ち境界が付けられたとす
れば前方に面したフラッグ（ｆｆ）２５は１にセットさ
れる。この点について、各プリミティブは境界付けされ
た境界を有するものと想定する。内部が境界の付いたプ
リミティブは正と称され、他は負と称される。またこの
点に関して、もし元のＣＳＧグラフの複数のリーフが、
境界付けされたボリュームであるとすれば、負のプリミ
ティブは、奇数回差し引かれたこれらのリーフに対応す
る。前方に面したフラッグ（ｆｆ）２５は、各ピクセル
において、本方法がＺ２を前進させるべきか否かを決定
する（表−１の２７行）ために使用される。

【００５６】次に、本発明の方法と装置とは、現在のプ
リミティブＱの面をスキャン変換する（表−１の１８〜
２５行）。Ｑの投影によりカバーされる各ピクセルに対
して、Ｚ３とＩ３とは、適当なところで、スキャンされ
た面の点の深度と強度とにより更新される（表−１の２
２〜２４行）。更新は、スキャンされたｚの値がＺ２に
記憶された深度とＺ３内に記憶されたものの間に位置す
るときのみ発生する（表−１の２２行）。

【００５７】本発明の一局面によれば、比較的小さい公
差値（ｅｐｓ）（処理されているモデルの寸法と比較し
て小さい）は、深度試験の前に差し引かれ、一致した面
の正しい処理を保証する。またこの点に関して、Ｉ３
は、スキャンされた表面が前方に向いているときのみ更
新される。このことは、もし後方に向いた面が、シルエ
ットエッジ近傍の前方に向いた面と重ならないとすれ
ば、後方に向いた面の強度がＩ３内に記憶されないよう
に保証する。本発明のこの局面を以下詳述する。前方に
向いたフラッグ（ｆｆ）２５は、Ｚ２の後ろを通るＱの
各面に対してトグルされる（表−１の２５行）。更びｅ
ｐｓ値が、スキャン変換精度と丸めの誤差とが不正確な
結果をもたらさないように保証するために使用される。

【００５８】本発明において使用するように、前方を向
いたフラッグ（ｆｆ）２５は、プリミティブＱ内あるい
はその外側のいずれかに位置する点のパリティを示す作
用をする。例えば、図４のＣを参照すれば、ｚ方向に観
察平面から離れる方向に移動するとき、第１の点（Ｐ
１）は、その点の後ろに位置するＱの３つの面を有して
いることが判る。このように、点Ｐ１は、奇数のパリテ
ィを有するものと考えられ、定義によりプリミティブＱ
内に位置するものと考えられる。点Ｐ２とＰ３とは、そ
れぞれｚ方向に沿って位置したＱの２つの面を有し、従
って偶数のパリティを有するものと考えられる。定義に
より、偶数のパリティを有する点は、プリミティブＱの
外側に位置するものと考えられる。試験は、点をｚバッ
ファに記憶させ、かつプリミティブをスキャン変換し、
さらに点の後ろに位置することが決定された各面に対し
て前方に向いたフラッグ（ｆｆ）２５をトグルすること
により、達成される。スキャン変換の完了時、前方に向
いたフラッグ（ｆｆ）２５の状態は、点のパリティ、従
って点がプリミティブ内に含まれるか否かを指示する。

【００５９】前述のトリックルアルゴリズムにおいて、
面のトリミング即ち製品のプリミティブＱに対する面の
点を試験することは、試験された点の後ろで出会ったＱ
の第１の面が前方に向いているか、あるいは後方に向い
ているかを試験することにより達成される。しかしなが
ら、Ｑのエッジの近傍において、あるいはもしｚバッフ
ァの分解能内でＱが平担に見えるのであれば、前方に向
いた面と後方に向いた面とは同じ深さを有することがあ
りうる。この問題を克服するために、本発明による方法
は、前述のＪ．Ｇｏｌｄｆｅａｔｈｅｒ他による、ＩＥ
ＥＥＣＧ＆Ａ、ｖｏｌ．９，Ｎｏ．３２０〜２８頁、
１９８９年５月の「ＮｅａｒＲｅａｌ−ＴｉｍｅＣＳ
ＧＲｅｎｄｅｒｉｎｇｕｓｉｎｇＴｒｅｅＮｏ
ｒｍａｌｉｚａｔｉｏｎａｎｄＧｅｏｍｅｔｒｉｃ
Ｐｒｕｎｉｎｇ」という名称の論文に記述されている
ように試験した点の後ろの面の数のパリティ（表−１の
２５行）を採用している。ある点の後にあるＱの偶数の
面は点が、Ｑ（例えば正のＱ）の外側にあることを意味
する。

【００６０】最後に、全体のプリミティブＱがスキャン
変更された後に、Ｚ３は、前方に向いたフラッグ（ｆ
ｆ）２５がセットされているとき（表−１の２７〜３１
行）はいつでも、即ちＺ２に記憶された点がＱの外側に
あるときはいつでもＺ２にコピイされる。このように、
Ｚ２におけるこれらの点は、Ｚ３に記憶されずみのＱ
（もしあるとすれば）上の前方を向いた点により置換さ
れる。

【００６１】Ｚ２とＺ３とに記憶された深度が相違する
ことを要する追加の条件、Ｚ２〔ｘ〕！＝Ｚ３〔ｘ〕
（表−１の２７行）は、正のプリミティブの投影の外側
の点の適正な処理を保証するために設けられている。し
かし、これらの点ｆｆ＝１に対して、Ｚ２とＺ３の双方
は共に最大深度に等しい。

【００６２】前述の単一の状態（オン−オンのケース）
は、異なる２つの面が同じピクセルをカバーし、そのピ
クセルに投影する点において同じ深さあるいは概ね同じ
深さを有する場合に発生する。単一の状態（ＳＣ）は、
それぞれソリッドＡとＢとに対して図４のＡとＢとに示
されている。そのような状態は、数個の面が重なる場合
数学的（正確な）モデルにおいて発生する。さらに、そ
れらはまた、図４のＢに示すように前面および後面を接
続するエッジ近く、あるいは図４のＡに示すようにｚバ
ッファの深度分解能より小さい深さを有する薄い壁ある
いは内部のクラックのようなくびれ部における打切られ
たグラフイックモデルにおいて発生する。これらの単一
のケースの全てに対して正確なイメージを計算するため
の方法は、スキャン変換の固有の丸めの誤差による深度
誤差をも補償するように十分確固としたものであらねば
ならない。

【００６３】このように、もしプリミティブ層の深さが
ｚバッファの深度分解能より小さいとすれば、それがあ
たかも平担（深度零）の如く処理されるように補償方法
が必要とされる。

【００６４】さらに、比較的大きいプリミティブ層に対
してさえも、プリミティブが局部的に平担に見える状態
が存在しうる。例えば図４のＢに示すようにシルエット
のエッジに近づくとき、同じプリミティブの当接してい
る２個の面（１個の前方に面したものと、１個の後方に
面したもの）は深度において相互に任意に近接してい
る。シルエットエッジにおいて、前面と後面とは同じ深
度を有する。ディスプレイ２６上のエッジ投影に近く位
置したピクセルをスキャン変換する間、スクリーンは双
方の面に対して同じ整数に丸めた深度値を有することが
判る。このように、その特定のピクセルに対して、プリ
ミティブは、平担で（深度零）縮退したソリッドとして
現われる。本方法が全てのピクセルに対して独立して進
行するという点において、本方法は、そのような縮退し
たプリミティブを正確に扱う必要があり、さもなけれ
ば、表示されたソリッドは不正確にクラックやダングリ
ングエッジを表わしうる。

【００６５】本発明の一局面によれば、カウンタ２４ａ
を−１の値に初期化する（表−１の９行）ことにより、
単一のプリミティブを備えた製品が２回スキャン変換さ
れることを保証する。このため、本発明による方法が最
初のスキャン変換中にＺ２で一時的な点を発生させ、次
いで、もし適当であるとすればその一時的な点を２回目
のスキャン変換中にプリミティブの外側にあるものと分
類する。

【００６６】さらに、単一性即ち「オン／オン」のケー
スの処理は、１９８５年１月号のＩＥＥＥの会報ｖｏ
ｌ．７３，Ｎｏ．１のＡ．Ａ．Ｇ．Ｒｅｑｕｉｃｈａと
Ｈ．Ｂ．Ｖｏｅｌｃｋｅｒとによる「Ｂｏｏｌｅａｎ
ＯｐｅｒａｔｉｏｎｓｉｎＳｏｌｉｄＭｏｄｅｌｉ
ｎｇ：ＢｏｕｎｄａｒｙＥｖａｌｕａｔｉｏｎａｎ
ｄＭｅｒｇｉｎｇＡｌｇｏｒｉｔｈｍｓ」において
報告されているように近隣評価を含むことが知られてい
る。本発明の方法は前方から後方への要領でプリミティ
ブの複数の面を試験するという点において、面の後ろの
近隣のみが関係している。この点に関して、近隣は、面
の後ろに製品に関して材料があるか否かを示す。もし面
の前方に材料があるとすれば、本方法は、ピクセルに対
して早期に終了し、当該面には到達しない。従って、も
し製品の材料が面の後ろに存在するとすれば、面の点は
製品上にあり、対応するピクセルを介して見える最前方
の点である。

【００６７】その結果、１９８６年９月号ＩＥＥＥＣ
ｏｍｐｕｔｅｒＧｒａｐｈｉｃｓａｎｄＡｐｐｌｉ
ｃａｔｉｏｎｓのｖｏｌ．６，Ｎｏ．９，２９〜３９頁
のＪ．Ｒ．ＲｏｓｓｉｇｎａｃおよびＡ．Ａ．Ｇ．Ｒｅ
ｑｕｉｃｈａによる「Ｄｅｐｔｈｂｕｆｆｅｒｉｎｇ
ｄｉｓｐｌａｙｔｅｃｈｎｉｑｕｅｓｆｏｒｃｏｎ
ｓｔｒｕｃｔｉｖｅｓｏｌｉｄｇｅｏｍｅｔｒｙ」
という名称の前述の論文で提供された技術を採用して、
スキャン変換した点をＺ２に記憶した深度と比較する
（表−１の２２行）前にそのスキャン変換した点の後ろ
に位置する点を試験することが好ましい。

【００６８】ある計算に採用した前述の公差値（ｅｐ
ｓ）の使用を以下詳細に説明する。

【００６９】まず、プリミティブを位置づけるために従
来から使用している回転は、それらの境界平面あるいは
項点の係数内で丸めの誤差を導入することが注目され
る。その結果、もしプリミティブが、面のあるものを整
合させるために回転するとすれば、重なるべき面を含む
表面は典型的には一致しない。さらに、スキャン変換丸
めの誤差は、いずれかのピクセルにおいていずれかの理
論的に一致する２つの面を予測不可能に深度で順序付け
うる。その結果、専ら深度に基く面の順序付けは、双方
の面の全体の重なり領域にわたって一貫した結果を提供
しない。

【００７０】従って、一致した面の問題を指向する全て
の動作において、本発明の装置と方法とは、比較的小さ
い公差（ｅｐｓ）を採用している。公差値を用いること
により、等しくあるべき２つの深度値が等しいものと確
実に見做されるようにする。勿論、大きすぎるｅｐｓの
値の選択は、等しくあるべきでない２つの値を等しいも
のとして扱うようになる可能性がある。そのような場
合、本方法は、ソリッドの規則化「モジュロ（ｍｏｄｕ
ｌｏ）ｅｐｓ」に対応するイメージを発生させる。即
ち、本方法は、浅いｚ深度を有するモデルの部分を除去
し、一方いずれかの場所で正しい面を表示するよう作用
する。

【００７１】このように、（ｅｐｓ）に対する値は、限
定されたｚバッファ分解能と表面スキャン変換中の深度
計算中に導入される丸めの誤差との組合せ効果を上廻る
ように選択される。もし大きすぎるｅｐｓ値が使用され
るとすれば、浅い特徴のようなある細部が、前方に面す
る面と後方に面する面とが一致したものと見做されると
いう点において消えることがありうる。

【００７２】前述した一致した面の「オン／オン」のケ
ースを正確に処理している間に、ｅｐｓに対して比較的
小さい値を採用するには、各々スキャンラインに沿った
最初の深度を正確に決定する必要がある。この深度を正
確に検出する方法を以下詳細に説明する。

【００７３】まず、ｚバッファＺ１の整数表示能力のた
め、ある面によってカバーされた全てのピクセルの表面
の点を計算する従来のスキャン変換手順は、大体の、即
ち切り捨てた深度値を発生させることが注目される。そ
の結果、２つの共通平面の重なり部分に位置した点の深
度は、点を発生するためにどの面をスキャン変換したか
によって異なりうる。

【００７４】この欠点を克服するために、かつ所期の一
致性が正確にかつ確実に扱われるようにするために、本
方法は、同じピクセルに投影された２個の点が、もしｚ
軸に沿ったそれぞれの深さがｅｐｓ以下の分だけ異なる
とすれば、同一であると見做す。ｅｐｓの値は、シーン
（光景）のサイズから、ｚバッファの解像力によって決
定される。

【００７５】図５を参照すれば、もしプリミティブの面
がｚ軸に対して鋭角にあるとすれば、サンプリングされ
た深度値はピクセル（Ｐ）の幅にわたって広く変動しう
る。その結果、例えば面ＡとＢのように一致した面を正
確に処理するには、各面をピクセル内の正確に同じ点で
サンプリングすることが重要である。本方法によって採
用されているように、この点はピクセルが全体的に平担
な正方形の表面領域であると考えられるピクセルの幾何
学的中心であるように選択される。もし２つの面が一致
したとすれば、双方の面によってカバーされたピクセル
に対する深度値のサンプリングにより各々カバーされた
ピクセルにおける双方の面に対して同じ深度を生ずる。

【００７６】本方法は、ある従来のスキャニングアルゴ
リズムに対して行われたようにピクセルの先導縁に沿っ
たｚ増分を単に用いるのでなく、開始ピクセルの中心に
投影される表面の点を決定することにより、各水平スパ
ンの上記開始ピクセルの深度を決定するように作用す
る。その結果、ｚ増分の計算の数値上の精度内で、スキ
ャンラインに沿った後続の点の深度を決定するためにス
キャンラインに沿ってｚ増分を用いることにより、全て
のカバーされたピクセルに対する深度は、スキャンされ
た表面に対して正確で、このようにその表面に位置する
全ての面に対して同じである。

【００７７】本発明のこの局面は、第１の点の投影から
ピクセルの中心までの正確な水平方向のオフセット距離
を得るために浮動小数点計算を採用することにより達成
でき、このオフセット距離は、面のスキャンラインに沿
った他の点のｚ深度を決定する際以下適用する。代替的
に、ピクセル領域は、多数の領域に仕切られ、各領域
は、ピクセル中心に対するオフセット値が割り当てられ
ている。次いでオフセット値はルックアップテーブル内
に記憶され、ピクセル領域内で第１の点が投影する場所
の関数として正確なオフセット値を引き出す。

【００７８】本発明の別の局面は、２つのプリミティブ
面間の境界で一貫したスキャン変換を提供することに関
連する。図６を参照すれば、その上に投影されたプリミ
ティブの２つの面（ＡとＢ）を有する複数のピクセルが
図示されている。２つの面の間の境界即ちエッジをＥで
示す。前述のトリックルアルゴリズムは、プリミティブ
の投影によりカバーされた各ピクセルが、そのプリミテ
ィブの後面の数と等しくする数の前面によってカバーさ
れることを要する。この要件は、プリミティブの境界
を、内部の面あるいはダングリング面を何ら有さない有
効２サイクルであることを要することを示している。こ
の状態は、ＣＳＧの推定であるソリッドの規則化を意味
している。しかしながら、同じプリミティブの２つの面
を処理するスキャン変換手順は、そのようなバリティを
自動的に保証するものではない。例えば、従来のブレセ
ンハム（Ｂｒｅｓｅｎｈａｍ）あるいはアンチエイリア
シングアルゴリズムは保証しない。

【００７９】スパンにわたる深度値、あるいは面の投影
によりカバーされる水平列のピクセルを単純補間するこ
とにより、もしスパンの終りが単に部分的に関連のピク
セルをカバーしないとすれば、スパンの終りで深度を間
違って計算することになりうる。このことは、たとえピ
クセルの中心が面によってカバーされていないとして
も、面を含む平面の傾斜を用いて、深度は外挿されるか
らである。

【００８０】例えば、まず、その長方形領域が前面と後
面との間のエッジ投影が横切られるが、その中心がこれ
らの面によってカバーされていないピクセル（Ｐ１）が
考えられる。もしスキャン変換アルゴリズムが、これら
２つの面に対してＰ１を訪ねる（ｖｉｓｉｔ）とすれ
ば、ピクセルの中心に対して深度値を計算する。しかし
ながらｚバッファの深度分解の大きさあるいは（ｅｐ
ｓ）公差値の大きさにもかかわらず、２つの面に対する
傾斜は、ピクセルＰ１の中心において、前面に対して計
算した深度が後面の計算深度を越えるように選択するこ
とができる。この「オーバシュート」の状態は、プリミ
ティブのシルエットエッジ近傍で不正確な表示を生ぜし
める。

【００８１】本発明のこの局面によれば、この問題に対
する解決は、スキャン変換の間、特定の面によってその
中心がカバーされるピクセルのみを処理することを含
む。図６の例の場合、面Ａに関連したクロスハッチング
したピクセルのみが、面Ａの投影がピクセルの中心をカ
バーするのはこれらのピクセルのみであるという点にお
いて面Ａに対してスキャン変換される。同じ状態が、そ
の中心が面Ｂによってカバーされるクロスハッチングし
たピクセルについても存在する。そのように、スキャン
変換プロセッサ１８は、ピクセルＰ１を考慮せず、前述
のオーバシュートの問題が克服される。

【００８２】さて図７のＡとＢのフローチャートとを参
照すれば、表示されたソリッドのシャドウイングに関す
る本発明の別の局面が示されている。本発明によれば、
シャドウイングは、光源（ＬＳ）から可視の表面部分を
選択する補助的な「シャドウ」ｚバッファ（ＺＳ）を使
用することにより達成される。ＺＳは、まず目をＬＳに
位置させる座標系において、強度情報を何ら計算するこ
となく前述のトリックルアルゴリズムを実行することに
より構成される。次に、トリックルアルゴリズムは、可
視点により反射された強度を計算している間に、ＬＳに
対する距離がＺＳに記憶されている距離と比較されるこ
とを除いて、通常の目の方向（ＥＯ）から再度実行され
る。このため、ＬＳから見ることのできるこれらの表面
点を設定する。そのことは、もし可視表面点が照射され
るか、あるいはＬＳに一層近いその他の面のシャドウに
あることが前提である。

【００８３】この技術は、ＺＳが計算された後の最終の
スキャン変換中に、表面点の座標が、双方の座標系、詳
しくはＥＯと整合した座標系と、ＬＳと整合した座標系
とにおいて表示されることを要する。スキャン変換した
表面によってカバーされる全てのピクセルが、正確に処
理されることを保証するためには、スキャン変換は、Ｅ
Ｏ座標系における増分を利用する。これらの増分は、一
定のマトリックスを介してＬＳ座標系の増分へマッピン
グされ、スキャン変換処理の速度を増大することがで
る。

【００８４】ＺＳにおいて発生するエイリアシング作用
は、もしシャドウイングが投影される表面がＥＯ観察方
向に直交し、かつ概ねＬＳに平行であるとすれば著しく
強調しうる。しかしながら、そのような好ましくない可
視アーチフアクトは、例えば、１９９０年フインランド
のＨｅｌｓｉｎｋｉＵｎｉｖｅｒｓｉｔｙｏｆＴｅ
ｃｈｎｏｌｏｇｙのＭａｔｈｅｍａｔｉｃｓａｎｄ
ＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅＳｅｒｉｅｓ，Ｎ
ｏ．５６におけるＣ．Ｗｏｏｄｗａｒｄによる「Ｍｅｔ
ｈｏｄｓｆｏｒＣｏｍｐｕｔｅｒ−ａｉｄｅｄｄ
ｅｓｉｇｎｏｆｆｒｅｅ−ｆｏｒｍＯｂｊｅｃｔ
ｓ」と題する論文において論じられているような従来の
技術を用いて減衰させることができる。

【００８５】システム１０の動作の数例を以下説明す
る。これらの例は、製品の和（即ち和集合）が、従来の
ｚバッファリングの隠面除去法により実行しうる点にお
いて単純な製品の可視前面の計算のみに集中している。

【００８６】２つの凸状プリミティブＡおよびＢを示す
図８を最初に参照する。製品はＡとＢの交差である。プ
リミティブＡは、前面Ｆ１と後面Ｆ４とを有する。プリ
ミティブＢは、前面Ｆ２と後面Ｆ３とを有する。ＡとＢ
との外側の面は、この例において対象のピクセルには投
影されず、従って考慮されていない。観察点は左側にあ
り、従って、ｚ方向は水平方向で左方から右方である。
観察点を通して水平方向の線により符号表示される特定
のピクセルを検討する。ピクセルを通して見える製品の
面はＢの前面Ｆ２である。

【００８７】システム１０の動作は以下のように進行す
る。スキャン変換が始まる前に、ピクセルバッファメモ
リが初期化される。Ｚ２は、単純にするために、ワール
ドがＺ＝Ｏ平面の正の側に位置するものと想定して、零
に初期化する（表−１の６行）。Ｉ２もバックグラウン
ドの色に初期化される（表−１の７行）。冗長スキャン
変換パスの計数ｋ（カウンタ２４ａ）は、−１に初期化
される。

【００８８】プリミティブＡは、まず製品のプリミティ
ブの循環（ｃｉｒｃｕｌａｒ）リストに現われ、そのた
めまずスキャン変換される。Ａが正であって、境界付け
がされているので、各ピクセルに対するパリティビット
フラッグ「（ｆｆ）２５」は１に初期化される。その結
果、Ａの投影によってカバーされていないピクセルにお
いて記憶さた点はＡの外側にあるものとして適正に扱わ
れる。Ｚ３は「無限」に、即ちｚバッファの最大深度を
表わす値に初期化され、Ｉ３はバッファグラウンドの色
にセットされる（表−１の１５〜１７行）。

【００８９】Ａの面のスキャン変換の間、少なくともピ
クセルに対して以下の関係があるものと想定しているこ
とが判る。即ち、Ｚ２＜Ｆ１＜Ｆ４＜Ｚ３。表−１の２
２行における試験は、ｅｐｓの適当に小さい値に対して
は成功しＦ１の深度がＺ３に記憶され、Ｆ１の色がＩ３
に記憶される。即ちＡの前面はＺ３に記憶される。Ｆ１
とＦ４の双方はＺ２の後ろにあり、パリティフラッグｆ
ｆがＡのスキャン変換の間２回トグルされ、従ってＡの
スキャン変換が終了するとき１の値を有する。Ｚ２にお
ける試験した点はＡの外側にあり、さらに後の点と置換
すべきである。また、スキャン変換の間、詳細に前述し
たようにピクセル中心の検討と、公差付き（ｅｐｓ）深
度試験の使用とを含む、向上したトリックルアルゴリズ
ム特性が採用されていることが注目される。

【００９０】更新ステップ（表−１の２６〜３０行）の
間、今や面Ｆ１に対応するＺ３およびＩ３の中味が、Ｚ
２とＩ２とにコピイされる。冗長パスの計数ｋは、若干
のピクセルが更新ずみなので０にリセットされる。Ａの
投影の外側にあるピクセルは、今やＺ２においてバック
グラウンド深度と色とを含んでいることが注目される。

【００９１】次に、プリミティブＢがスキャン変換され
る。プリミティブＢは面Ｆ２とＦ３とを有する。ｋの値
（カウンタ２４ａ）が、１まで増加され、前方を向いた
フラッグ（ｆｆ）２５は１にセットされ、Ｚ３が「無
限」に初期化される。Ｚ２＜Ｆ２＜Ｆ３＜Ｚ３がＦ２の
深度と強度とをＺ３とＩ３とにコピイさせることが判
る。再度Ｚ２はＦ２およびＦ３より小さく、このためパ
リティフラッグを２回トグルさせる。このことは、Ｚ２
における試験した点がＢの外側にあるために発生す。Ｚ
２とＩ２の中味は面Ｆ２からのデータで重ね書きされ、
カウンタ２４ａは、変更フラッグ（ｃｆ）２３の作用に
より再度零にリセットされる。

【００９２】次のプリミティブを検討する必要がある。
まず、ｋが１に増加され、（ｆｆ）２５が各ピクセルに
おいて１にセットされる。プリミティブリストが循環性
であるため、プリミティブＡは再度スキャン変換され、
Ｆ１＜Ｚ２＜Ｆ４＜Ｚ３であることが判明する。このよ
うに、面Ｆ１はＺ２の後ろにないので考慮されない。Ｆ
４の深度はＺ３に記憶されるが、Ｆ４が後方を向いてい
るので、Ｆ４の色はＩ３にコピイされない。Ａの一つの
面Ｆ４のみがＺ２の後ろにあるので、パリティフラッグ
は一回のみトグルされ、このように零の値を有する。そ
の結果、Ｚ２は変更されず、カウンタ２４ａはリセット
されず１の値を保持する。

【００９３】プリミティブＢは再度スキャン変換され
る。ｋの値は２に増分され、パリティフラッグは１にセ
ットされる。Ｚ２はすでにＦ２の深度を含んでおり、Ｂ
のスキャン変換の後Ｚ２＜Ｆ３＜Ｚ３が判明する。従っ
て、Ｆ３の深度がＺ３へコピイされるが、Ｆ３が後方を
向いているので色はＩ３にコピイされない。Ｆ３のみが
Ｚ２の後ろにあり、そのためパリティフラッグはＦ３の
投影によりカバーされている各ピクセルにおいて零にト
グルされる。従って、Ｚ２は変化せず、（ｃｆ）２３は
カウンタ２４ａをリセットさせず、カウンタ２４ａが保
持する計数は２のままである。Ｚ２はＢの前面Ｆ２を保
持する。

【００９４】ｋの値（カウンタ２４ａ）が製品のプリミ
ティブの数と等しいので、ＴＥＲＭＩＮＡＴＥ信号が比
較器２４ｂにより発生し、製品の可視前面（Ｆ２）をＺ
２に位置させて変換ループが終了する（表−１の１０
行）。Ｚ２とＩ２の中味が、Ｚ２がＺ１より小さければ
いつでも表示バッファＺ１およびＩ１にコピイされ、こ
の製品を論理和形態の他の製品と併合する。

【００９５】図９を参照すれば、非凸状プリミティブＡ
を凸状プリミティブＢと交差させるためのシステム１０
の動作の別の例が示されている。プリミティブＡは面Ｆ
１、Ｆ３、Ｆ４およびＦ５を、Ｂは面Ｆ２およびＦ６と
を有している。前面Ｆ１とＦ２とは一致している。

【００９６】前述と同様、プリミティブＡをスキャン変
換する前にＺ２が初期化される。前例と同様に、Ａが正
であるのでパリティフラッグがセットされる。Ｚ２＜Ｆ
１＜Ｆ３＜Ｆ４＜Ｆ５であるので、面Ｆ１はＺ３に記憶
されている。Ｚ２の後ろにプリミティブＡの４つの面が
あるので、ｆｆは１にセットされ、Ｆ１はＺ２とＩ２と
にコピイされる（表−１の２６〜３０行）。

【００９７】Ｂのスキャン変換の間、面Ｆ２はＦ１と一
致しており、Ｆ２＜Ｚ２＋ｅｐｓ＜Ｆ６であることが判
明する。プリミティブＢの一つの面のみがＺ２の後ろに
あるので、パリティフラッグは零にトグルされ、Ｚ２は
変らないままである。カウンタ２４ａは１に増分され
る。

【００９８】プリミティブＡは再度スキャンされ、Ｚ２
＜Ｆ３＜Ｆ４＜Ｆ５であることが判明する。Ｆ３の深度
はＺ３に記憶されるが、Ｆ３が後方を向いているのでＩ
３は変らない。Ｚ２の後ろのプリミティブＡの面の数は
奇数なので、パリティフラッグは零にトグルされ、Ｚ２
は変らないままである。カウンタ２４ａは製品における
プリミティブの数に等しい値である。２に増分され、Ｔ
ＥＲＭＩＮＡＴＥ信号を発生してスキャン変換ループ処
理を停止する。Ｚ２は製品の前方にあるＦ１を含む。Ｚ
２は後でＺ１に併合される。

【００９９】単純なプリミティブＡおよびＢの減算に対
する別の例を図１０に示す。製品Ａ−Ｂにおいて、Ａの
前面Ｆ１はＢの前面Ｆ２と一致する。Ｂが製品において
負なので、Ｆ２は、ＡがＢの相補部と交差するため後面
として扱われることが注目される。製品の可視面は非相
補プリミティブＢの元の後面であるＦ３である。

【０１００】前例と同様に初期化が行われ、プリミティ
ブＡはＺ２に記憶されているＦ１とスキャン変換され
る。

【０１０１】次に、プリミティブＢがスキャン変換され
る。Ｂが負であるので、パリティフラッグｆｆは零に初
期化される。Ｆ２＜Ｚ２＋ｅｐｓ＜Ｆ３＜Ｚ３であるこ
とが判明する。従って、プリミティブＢが負であるため
Ｆ３は前向きであるので、Ｆ３は、Ｉ３の強度を含みＺ
３に記憶される。Ｂの一つの面がＺ２の後ろにあるの
で、ｆｆはスキャン変換により出合う（ｖｉｓｉｔｅ
ｄ）ピクセルにおいて１にトグルされる。Ｆ２はＢの外
側にありＺ３はＺ２にコピイされる。

【０１０２】プリミティブＡは再度スキャン変換され、
パリティフラッグは１にセットされる。Ｆ４のみがＺ２
の後ろにあり、従って（ｆｆ）２５は一旦トグルされ零
にセットされる。その結果、Ｚ２は変らないままであ
る。同じことが、プリミティブＢの２回目のスキャンの
間に発生する。カウンタ２４ａに含まれた値がプリミテ
ィブの数、この場合２に、リセットされずに達すると、
ＴＥＲＭＩＮＡＴＥ信号が発生しスキャン変換ループを
出ていく。Ｆ３を含むＺ２が次いでＺ１に併合される。

【０１０３】図１１を参照すれば、内部クラックを含む
プリミティブに対する前後の例が提供されている。プリ
ミティブＡは面Ｆ１、Ｆ４、Ｆ５およびＦ７を有し、一
方プリミティブＢは面Ｆ２、Ｆ３、Ｆ６およびＦ８を有
している。対象のピクセルに投影されるＡ−Ｂの非規則
化した差が、空のセットである。この例は、内部クラッ
クを有する非凸状プリミティブＢを、これも内部クラッ
クを有する別の非凸状プリミティブＡから減算すること
を含む。さらに、プリミティブＢの内部クラックはプリ
ミティブＡの内部クラックと一致している。そのような
クラックは、モデル内あるいは限定された深度分解能の
ため同じプリミティブの２つの面が一致したとき発生す
る。これらの特異性（ｓｉｎｇｕｌａｒｉｔｙ）はまた
前述のようにシルエットエッジ近傍で現われうる。

【０１０４】前例のように、プリミティブＡを初期化
し、かつスキャン変換した後、Ｆ１はＺ２に記憶され
る。

【０１０５】プリミティブＢはスキャン変換され、かつ
パリティフラッグはＢが負のため零にセットされる。Ｆ
２はＦ１と一致するので、Ｆ２＜Ｚ２＋ｅｐｓ＜Ｆ３＝
Ｆ６＜Ｆ８＜Ｚ３となる。Ｆ３またはＦ６のいずれかの
深度が、プリミティブＢの面がスキャン変換される順序
に応じてＺ３にコピイされる。しかしながら、Ｆ６は後
方に向いているので、Ｆ３の強度はＩ３に保存される。
Ｚ２の後ろにＢの面が３つあるので、（ｆｆ）２５は１
にトグルされ、Ｚ３はＺ２にコピイされる。

【０１０６】プリミティブＡは再度スキャン変換され、
パリティフラッグがセットされる。Ｆ４はＦ５並びにＺ
２と一致し、以下の状態が存在することが判る。即ち、
Ｆ１＜Ｆ４＝Ｆ５＜Ｚ２＋ｅｐｓ＜Ｆ７＜Ｚ３である。
Ｆ７はＺ３に書き込まれる。Ｆ７のみがＺ２の後ろにあ
るので、（ｆｆ）２５は零にリセットされ、Ｚ２は変わ
らないままで、従って依然としてＦ３を含んでいる。

【０１０７】プリミティブＢは再びスキャン変換され、
Ｆ６とＦ３とはＺ２と一致していることが判明し、Ｆ２
＜Ｆ３＝Ｆ６＜Ｆ２＋ｅｐｓ＜Ｆ８＜Ｚ３が得られる。
Ｆ８はＺ３に書き込まれる。プリミティブＢの１つの面
Ｆ８のみがＺ２の後ろにあるので、パリティフラッグは
一旦１にトグルされ、Ｆ８はＺ２にコピイされる。

【０１０８】プリミティブＡは再度スキャン変換され、
Ａの最も後ろの面Ｆ７がＦ８と一致し、Ｆ１＜Ｆ４＝Ｆ
５＜Ｆ７＜Ｚ２＋ｅｐｓ＜Ｚ３を提供することが判る。
従って、Ｚ３には何もコピイされず、パリティフラッグ
はセットされたままである。このように、Ｚ３がそれら
で初期化されたそれらのバックグラウンドの色と最大深
度（無限）とがＺ２にコピイされる。

【０１０９】プリミティブＢの別のスキャン変換パスは
何ら変化をもたらさず、プロセスは、カウンタ２４ａが
プリミティブの数に対応する２の計数に達したとき終了
する。

【０１１０】要約すれば、多重深度バッファ技術を用い
て規則化されたＣＳＧソリッドを適正に表示するため
に、２つの面が、あるピクセルにおいて同じ深度を有す
るという単一のケースを適正に考慮する必要のあること
が示された。そのような面が一致する状態は、ＣＳＧプ
リミティブがそれらの境界に沿って二次元の接触を有し
て位置決めされるときのみならず発生する。くびれ部、
あるいはシルエットエッジ近傍の鋭い隅部における表面
の点が、同じピクセルに投影され、かつ相互に十分近い
深度値を有し、それがスキャン変換処理によって同じ整
数の深度値に丸められたときも偶然に発生する。

【０１１１】この問題は、交差値（ｅｐｓ）を用いてス
キャン変換中の丸めの誤差による投影を除去することに
よって克服される。このように、一致すべき面は、たと
え実際の深度が同じピクセルにおいて異なることがあり
うるとしても一致する。また、ＣＳＧ式の規則化した解
釈に関して正しい表示イメージを発生させるには交差を
付した深度試験が用いられ、さもなければ現れるダング
リング面やエッジを除去する。

【０１１２】さらに、小さい特徴の損失を回避するため
モデルのサイズに対してｅｐｓの小さい値を保つため
に、改良されたスキャン変換技術が提供される。この改
良された技術は、ピクセルの中心に投影して全ての出合
ったピクセルに対して実際の表面深度を生成する。この
ように、もし空間で重なる２つの面が独立してスキャン
変換されるとすれば、双方の面によってカバーされた全
てのピクセルに対して発生した対の値が、深度増分累積
の間に発生しうる極めて小さい丸めの誤差を除いて等し
い。

【０１１３】また、プリミティブの点の分類に対してス
キャン変換法が正しく使用できるようにするには、スキ
ャン変換技術が、ある面によってその中心がカバーされ
るピクセルのみがその面のスキャン走査の間に出合うよ
うに保証すべく修正される。さらに、本発明によれば、
シャドウウイングは補助シャドウバッフア（ＺＳ）を用
いた単純な２回パススキャン変換技術により達成され
る。

【０１１４】本発明を特定実施例に関して説明してきた
が、本発明の範囲と精神とから逸脱することなく修正を
施しうることを認識すべきである。

【０１１５】例えば、強度バッファＩ２およびＩ３が設
けられていないところでは修正されたＤＩＢ２０ア
ーキテクチャを用いることができる。本発明の方法は、
強度の計算並びに更新が実施されないことを除いて、プ
リミティブ対象物を繰り返し評価するため前述の通り進
行する。その結果は、強度情報は無いが、全てのＣＳＧ
式に対してＺ１を計算することである。次いで、全ての
プリミティブの前方に面した面の一回のみのスキャン変
換を実行する強度決定パスが実行される。強度決定パス
は、Ｚ１に記憶された深度が現在処理されている点にお
ける表面深度と等しいピクセルに対してピクセルメモリ
Ｉ１において対応する強度値を記憶する。本発明のこの
変更はピクセルメモリを著しく節約するが、像の質を僅
かに低下させうる。

【図面の簡単な説明】

【図１】３個のプリミティブからなるソリッドに対する
従来技術によるＣＳＧバイナリツリーを示す斜視図。

【図２】本発明により構成され、かつ動作するイメージ
表示処理システムの実施例を示すブロック線図。

【図３】プリミティブＱを処理する上での図２に示す深
度インターバルバッファの動作を示す図。

【図４】Ａは、縮退した零厚さの壁としてくびれ部が現
われ、かつクラックとして狭い空洞が現われる、限定さ
れた深度分解能の作用を示す図であり、Ｂは、シルエッ
トの後面と前面とが一致するように見える個所近傍での
限定された深度分解能の作用を示す図であり、Ｃは、ソ
リッドに対する別の関係に位置する点の分類を決定する
ことを示す図。

【図５】ある表面に対して正確なｚ値を発生させるため
にスキャンラインの初期深度を調整することを採用す
る、正確なスキャン変換を達成する技術を示す図。

【図６】複数のピクセル上に投影する２つの面を有する
プリミティブの調整されたスキャン変換を達成する技術
を示す図。

【図７】Ａは、２パスのシャドウイング技術に採用され
た補助シャドウバッファを示す図であり、Ｂは、Ａに示
す補助シャドウバッファの動作を示すフローチャート。

【図８】本システムの動作の複数例による２個のプリミ
ティブの処理を示す図のうちの、２個の凸状のプリミテ
ィブの交差を示す図。

【図９】本システムの動作の複数例による２個のプリミ
ティブの処理を示す図のうちの、双方のプリミティブが
共通の前面を共用している、非凸状のプリミティブと凸
状のプリミティブとの交差を示す図。

【図１０】本システムの動作の複数例による２個のプリ
ミティブの処理を示す図のうちの、２個の凸状のプリミ
ティブの間の差を示す図。

【図１１】本システムの動作の複数例による２個のプリ
ミティブの処理を示す図のうちの、非凸状のプリミティ
ブの各々が内部クラックを有している、一方の非凸状の
プリミティブから別の非凸プリミティブを減算する図。

フロントページの続き (72)発明者デービツド・アレキサンダー・エプスタインアメリカ合衆国10562、ニユーヨーク州オシニング、イースターン・アベニユー 53番地 (72)発明者ジヤロスロウ・ロマン・ロシグナツクアメリカ合衆国10562、ニユーヨーク州オシニング、リンカーン・プレイス 1956 番地 (72)発明者ジエフレイ・ウエンフオン・ウーアメリカ合衆国10011、ニユーヨーク州ニユーヨーク、ウエスト・トウエンテイーサード・ストリート 208番地、アパートメント 1003

Claims

【特許請求の範囲】

【請求項１】三次元ソリッド対象物を表現する表示可
能情報を発生する装置において、１つ以上のプリミティブ対象物からなるように対象物を
コンストラクティブ・ソリッド・ジオメトリ（ＣＧＳ）
表示法で表現する手段と、前記１つ以上のプリミティブ対象物を繰り返し評価して
その表示可能面を決定する評価手段と、前記評価手段の動作に応答して、表示可能面の決定にお
いて変化を生じさせることなく所定数の繰返し評価の行
われる状態を決定する決定手段であって、評価を計数
し、かつ前記所定数の評価が行われたとき前記評価手段
の動作を終了させるための信号を発生する手段を含む決
定手段と、を備える表示可能情報を発生する装置。
【請求項２】前記所定数が前記対象物を構成するプリ
ミティブ対象物の数に等しい請求項１に記載の装置。
【請求項３】前記評価手段は、複数の深度バッファ手
段を含み、さらに、評価されつつあるプリミティブ対象
物の面上のある点の、基準平面に対する深度を、第１の
深度バッファ手段（Ｚ３）内に記憶された第１の点の深
度と、および第２の深度バッファ手段（Ｚ２）内に記憶
された第２の点とに比較する比較手段を含み、前記第１
の点および第２の点の深度は同じ、あるいは別のプリミ
ティブ対象物の先行評価中に決定される請求項１に記載
の装置。
【請求項４】前記評価手段は、前記比較手段の動作に
応答して、Ｚ２＜Ｚ＜Ｚ３のとき、Ｚ３内に記憶された
深度を現在の点の深度（Ｚ）と置換する手段を含む請求
項３に記載の装置。
【請求項５】前記評価手段は、前記比較手段の動作に
応答して、Ｚ２＜Ｚ＜Ｚ３のとき、Ｚ３内に記憶された
深度を現在の点（Ｚ）の深度と置換する置換手段を含
み、さらに、前記置換手段の動作に応答して、計数手段
をプリミティブ対象物の数より小さい値にリセットする
手段をさらに含む請求項３に記載の装置。
【請求項６】前記評価手段は、前記比較手段の動作に
応答して、Ｚ２＋ｅｐｓ＜Ｚ＜Ｚ３＋ｅｐｓでｅｐｓは
公差値であるとき、Ｚ３内に記憶された深度を現在の点
の深度（Ｚ）と置換する手段を含む請求項３に記載の装
置。
【請求項７】前記評価手段は、前記比較手段の動作に
応答して、Ｚ２＜Ｚ＜Ｚ３のとき、Ｚ３に記憶された深
度を現在の点の深度（Ｚ）と置換する手段を含み、さら
に、現在の点を通して基準平面から投影されたラインに
対して、該ラインが交差する、評価中のプリミティブ対
象物の複数の面を記録する手段を含む請求項３に記載の
装置。
【請求項８】指示手段が、評価されているプリミティ
ブ対象物上にあるいはその内部に現在の点が位置してい
ることを示すときのみ、Ｚ２内に記憶された深度をＺ３
内に記憶されている深度と置換する第２の置換手段をさ
らに含む請求項７に記載の装置。
【請求項９】Ｚ３が関連の強度バッファＩ３を有し、
Ｚ２が関連の強度バッファＩ２を有し、前記第２の置換
手段がまた、Ｉ２内に記憶された強度を、現在の点が前
記プリミティブ対象物の前面上に位置しているときの
み、Ｉ３内に記憶された強度と置換する請求項８に記載
の装置。
【請求項１０】前記評価手段は、前記プリミティブ対
象物の面上の点から前記基準平面へ投影する手段を含
み、前記基準平面が複数のピクセルに仕切られ、前記評
価手段はさらに、前記投影手段の動作に応答して、前記
面の投影によりカバーされるピクセルの位置を決定し、
かつ中心点が前記プリミティブ対象物の面の点からの投
影内に位置する中心を有するピクセルのみを選択する手
段を含む請求項３に記載の装置。
【請求項１１】前記基準平面が複数のピクセルに仕切
られ、前記評価手段は、前記プリミティブ対象物の面上
の点から前記基準平面に投影し、かつピクセルからの点
の深度を検出する手段を含み、該深度がピクセルの中心
を基準としている請求項３に記載の装置。
【請求項１２】第３の深度バッファ手段（Ｚ１）をさ
らに含み、前記装置はまた、信号の発生に応答して、Ｚ
２＜Ｚ１のときのみ、Ｚ１内に記憶された深度をＺ２内
に記憶された深度と置換する第３の手段を含む請求項８
に記載の装置。
【請求項１３】ソリッド対象物を照射する光源の平面
を基準とした、前記プリミティブ対象物の面上の点から
前記光源の平面への投影の深度を記憶するシャドウ深度
バッファ手段（ＺＳ）をさらに含む請求項３に記載の装
置。
【請求項１４】前記基準平面を基準とした、点の深度
を、ＺＳ内に記憶された深度と比較して、もしその点が
前記光源から見うるかどうか決定する手段をさらに含む
請求項１３に記載の装置。
【請求項１５】三次元ソリッド対象物を表現する表示
可能情報を発生する装置において、１つ以上のプリミティブ対象物からなるように対象物を
コンストラクティブ・ソリッド・ジオメトリ（ＣＧＳ）
表示法で表現する手段と、前記１つ以上のプリミティブ対象物を繰り返し評価して
表示可能面を決定する評価手段とを備え、前記評価手段は、前記プリミティブ対象物の面上の点か
ら前記基準平面に投影する投影手段を含み、前記基準平
面が複数のピクセルに仕切られ、前記評価手段は、前記
投影手段の動作に応答して、面の投影によってカバーさ
れるピクセルの位置を決定し、かつ前記プリミティブ対
象物の面上の点からの投影内に位置した中心を有するピ
クセルのみを選択する手段をさらに含む表示可能情報を
発生する装置。
【請求項１６】三次元ソリッド対象物を表現する表示
可能情報を発生する装置において、１つ以上のプリミティブ対象物からなるように対象物を
コンストラクティブ・ソリッド・ジオメトリ（ＣＧＳ）
表示法により表現する手段と、前記１つ以上のプリミティブ対象物を評価して表示可能
の面を決定する評価手段とを備え、前記評価手段は、評価されているプリミティブ対象物の
面上の点の、基準平面に対する深度を決定する手段を含
み、前記基準平面が複数のピクセルに仕切られ、深度が
前記点が投影されるピクセルの中心を基準とする、表示
可能情報を発生する装置。
【請求項１７】三次元のソリッド対象物を表現する表
示可能情報を発生する装置において、１つ以上のプリミティブ対象物からなるように対象物を
コンストラクティブ・ソリッド・ジオメトリ（ＣＧＳ）
表示法により表現する手段と、前記１つ以上のプリミティブ対象物を評価して表示可能
面を決定する手段とを備え、前記評価手段は、評価されているプリミティブ対象物の
面上の点の、基準面に対する深度を、第１の深度バッフ
ァ手段内に記憶された第１の点の深度と、および第２の
深度バッファ手段内に記憶された第２の点の深度とに比
較する比較手段を含み、前記比較手段は、所定の公差内
で深度比較を行い、前記所定の公差が、計算によりもた
らされた丸めの誤差および前記第１および第２の深度バ
ッファ手段の最小分解能とを補償するように選択された
値を有する、表示可能情報を発生する装置。
【請求項１８】三次元のソリッド対象物を表現する表
示可能情報を発生する装置において、１つ以上のプリミティブ対象物からなるように対象物を
コンストラクティブ・ソリッド・ジオメトリ（ＣＧＳ）
表示法で表現する手段と、前記１つ以上のプリミティブ対象物を評価して表示可能
面を決定する評価手段とを備え、前記評価手段は、評価されているプリミティブ対象物の
面上に位置する点の深度を、先に決定された深度と繰り
返し比較し、かつ深度バッファ手段（Ｚ１）内で、前記
プリミティブ対象物の表示可能面上に位置することが決
定された各点の深度を記憶する第１の比較手段を含み、
前記深度が基準平面に対する深度であり、前記評価手段は、前記第１の比較手段の動作の終了に応
答して、前記プリミティブ対象物の前方に向いた面上の
複数の点を比較し、かつ強度バッファ手段（Ｉ１）内
に、Ｚ１内に記憶されている対応の深度と等しいことが
決定された深度を有する前方を向いた面上の点の強度を
記憶する第２の比較手段を含み、前記第１および第２の比較手段はそれぞれ、所定公差内
で深度比較を行い、該所定の公差が、少なくとも計算に
よりもたらされた丸めの誤差を補償するように選択され
た値を有する、表示可能情報を発生する装置。
【請求項１９】三次元のソリッド対象物を表現する表
示可能情報を発生する方法において、１つ以上のプリミティブ対象物からなるように対象物を
コンストラクティブ・ソリッド・ジオメトリ（ＣＧＳ）
表示法で表現し、前記１つ以上のプリミティブ対象物の表示可能面を決定
するため、前記１つ以上のプリミティブ対象物を繰り返
し評価し、各々の繰返し評価に対して計数を増分し、該計数が、表示可能面の決定において変化を生じさせる
ことなく発生した繰返し評価の所定回数を指示する状態
を検出し、前記所定回数の評価が発生するとき評価手段の動作を終
了させる信号を発生するステップを備える表示可能情報
を発生する方法。
【請求項２０】前記所定回数が、対象物を構成するプ
リミティブ対象物の数と等しい請求項１９に記載の方
法。
【請求項２１】前記評価するステップは、評価されて
いるプリミティブ対象物の面上の点の、基準平面に対す
る深度を、第１の深度バッファ手段（Ｚ２）内に記憶さ
れた深度と、および第２の深度バッファ手段（Ｚ２）内
に記憶された第２の点の深度とに比較するステップを含
み、前記第１の点および第２の点の深度が同じ、あるい
は別のプリミティブ対象物の先行評価の間に決定される
請求項１９に記載の方法。
【請求項２２】前記評価するステップは、Ｚ２＜Ｚ＜
Ｚ３のとき、Ｚ３内に記憶された深度を現在の点の深度
（Ｚ）と置換するステップを含む請求項２１に記載の方
法。
【請求項２３】前記評価するステップは、Ｚ２＜Ｚ＜
Ｚ３のとき、Ｚ３内に記憶された深度を現在の点の深度
（Ｚ）と置換するステップを含み、さらに計数手段をプ
リミティブ対象物の数より小さい値にリセットするステ
ップを含む請求項２１に記載の方法。
【請求項２４】前記評価するステップは、Ｚ２＋ｅｐ
ｓ＜Ｚ＜Ｚ３＋ｅｐｓでｅｐｓは公差値であるとき、Ｚ
３内に記憶された深度を現在の点の深度（Ｚ）と置換す
るステップを含む請求項２１に記載の方法。
【請求項２５】前記評価するステップは、Ｚ２＜Ｚ＜Ｚ３のとき、Ｚ３内に記憶された深度を現在
の点の深度（Ｚ）と置換し、現在の点を介して前記基準平面から投影されたラインに
対して、該ラインが公差する、評価中のプリミティブ対
象物の面の数を記録するステップを含む請求項２１に記
載の方法。
【請求項２６】面の記録された数は、現在の点が評価
されているプリミティブ対象物上にあるいはその内部に
位置することを指示するときのみ、Ｚ２内に記憶された
深度をＺ３内に記憶された深度と置換するステップをさ
らに含む請求項２５に記載の方法。
【請求項２７】Ｚ３が関連の強度バッファＩ３を有
し、Ｚ２が関連の強度バッファＩ２を有し、さらに、現
在の点が前記プリミティブ対象物の前面に位置するとき
のみ、Ｉ２内に記憶された強度をＩ３内に記憶された強
度と置換するステップを含む請求項２６に記載の方法。
【請求項２８】前記基準平面が複数のピクセルに仕切
られ、前記評価するステップが前記プリミティブ対象物
の面上の点から前記基準平面へ投影するステップを含
み、いずれのピクセルが面によってカバーされたか決定し、
ピクセルは、もしその中心が前記プリミティブ対象物の
面上の点からの投影内に位置するときのみ前記面によっ
てカバーされたことが決定される請求項２１に記載の方
法。
【請求項２９】前記基準平面が複数のピクセルに仕切
られ、前記評価のステップが前記プリミティブ対象物の
面上の点から前記基準平面に投影してピクセルからの前
記点の深度を決定し、該決定された深度がピクセルの中
心を基準としている請求項２１に記載の方法。
【請求項３０】前記信号を発生するステップは、Ｚ２
＜Ｚ１であるときのみ、第３のＺバッファ手段（Ｚ１）
内に記憶された深度をＺ２内に記憶された深度と置換す
るステップを含む請求項２６に記載の方法。
【請求項３１】前記プリミティブ対象物の面上の点か
ら光源の平面への投影の、前記ソリッド対象物を照射す
る前記光源の平面を基準にした深度を記憶するステップ
をさらに含み、前記深度がシャドウ深度バッファ手段
（ＺＳ）内に記憶される請求項２１に記載の方法。
【請求項３２】前記基準平面を基準とした点の深度
を、ＺＳ内に記憶された深度と比較して、前記点が前記
光源から見えるか否かを決定するステップをさらに含む
請求項３１に記載の方法。
【請求項３３】三次元のソリッド対象物を表現する表
示可能情報を発生する方法において、１つ以上のプリミティブ対象物からなるように対象物を
コンストラクティブ・ソリッド・ジオメトリ（ＣＧＳ）
表示法で表現し、１つ以上のプリミティブ対象物の表示可能面を決定する
ため、該１つ以上のプリミティブ対象物を評価するステ
ップを備え、前記評価するステップは、前記プリミティブ対象物の面
上の点から、複数のピクセルに仕切られた基準平面に投
影して、いずれのピクセルが前記面によってカバーされ
ているか決定するステップを含み、前記の投影するステ
ップが、もしピクセルの中心が前記プリミティブ対象物
の面上の点からの投影内に位置するときのみ所与のピク
セルが前記面によってカバーされたことを決定するステ
ップを含む、表示可能情報を発生する方法。
【請求項３４】三次元ソリッド対象物を表現する表示
可能情報を発生する方法において、１つ以上のプリミティブ対象物からなるように対象物を
コンストラクティブ・ソリッド・ジオメトリ（ＣＧＳ）
表示法により表現し、前記１つ以上のプリミティブ対象物の表示可能面を決定
するため前記１つ以上のプリミティブ対象物を評価する
ステップを備え、前記評価するステップは、評価されているプリミティブ
対象物の面上の点の、基準平面に対する深度を決定する
ステップを含み、前記基準平面が複数のピクセルに仕切
られ、深度がその上に点が投影されるピクセルの中心を
基準としている、表示可能情報を発生する方法。
【請求項３５】三次元ソリッド対象物を表現する表示
可能情報を発生する方法において、１つ以上のプリミティブ対象物からなるように対象物を
コンストラクティブ・ソリッド・ジオメトリ（ＣＧＳ）
表示法で表現し、前記１つ以上のプリミティブ対象物の表示可能面を決定
するため前記１つ以上のプリミティブ対象物を評価する
ステップを備え、前記評価するステップは、評価されているプリミティブ
対象物の面上の点の、基準平面に対する深度を、第１の
深度バッファ手段内に記憶された第１の点の深度と、お
よび第２の深度バッファ手段内に記憶された第２の点の
深度とに比較するステップを含み、前記比較するステッ
プは、所定の公差内で深度を比較し、該所定の公差は少
なくとも計算によりもたらされた丸めの誤差を補償する
ように選択した値を有する、表示可能情報を発生する方
法。
【請求項３６】三次元のソリッド対象物を表現する表
示可能情報を発生する方法において、１つ以上のプリミティブ対象物からなるように対象物を
コンストラクティブ・ソリッド・ジオメトリ（ＣＧＳ）
表示法において表現し、前記１つ以上のプリミティブ対象物の表示可能面を決定
するため前記１つ以上のプリミティブ対象物を評価する
ステップを備え、前記評価するステップは、評価されているプリミティブ対象物の面の点の深度を、
先に決定された深度と繰返し比較し、プリミティブ対象物の表示可能面に位置すると決定され
た各点の、基準平面に対する深度を深度バッファ手段
（Ｚ１）内に記憶し、前記プリミティブ対象物の前方を向いている面上の点の
深度をＺ１内に記憶さた対応する深度と比較し、Ｚ１内に記憶された対応の深度と等しいと決定された深
度を有する前方に向いている表面上の点の強度を強度バ
ッファ手段（Ｉ１）内に記憶するステップを含む表示可
能情報を発生する方法。
【請求項３７】前記繰返し比較するステップは、所定
の公差を用いて深度を各々比較し、該所定の公差が少な
くとも計算によりもたらされた丸めの誤差を補償するよ
うに選択した値を有している請求項３６に記載の方法。