JPH0760465B2 - 凹ポリゴン描出方法及びプロセツサ - Google Patents

Description

【発明の詳細な説明】 A.産業上の利用分野 本発明は総括的にコンピュータ・グラフィックス表示シ
ステムに関し、詳細にいえば、表示モニタに表示すべき
複数のラインの各々に対する個々のピクセルを記憶する
ためのフレーム・バッファを含むグラフィックス表示手
段に対して、凹（concave）ポリゴン、セルフ・インタ
ーセクティング・ポリゴン及び多角形孔を有するポリゴ
ンの１つを描くための改善された方法及びプロセッサに
関する。

B.従来の技術及びその課題 周知のように、コンピュータ・グラフィックス表示シス
テムは、ラスタ操作ディスプレイ装置上にグラフィック
・イメージを生成し、表示するコンピュータ・システム
である。このようなグラフィック・イメージはシステム
のメモリに記憶されているディジタル・データから導か
れる。データは通常、２次元または３次元座標系の点の
形で記憶されており、点は三角形などのポリゴンの頂点
に対応している。ポリゴンは最終的な表示オブジェクト
である大きなオブジェクトの「建築ブロック」を形成す
る。頂点データにはパラメータ値、すなわち輝度、ある
いは表面色、表面反射率、透明度、光源、法線ベクトル
などの輝度の計算を可能とするその他の値も記憶されて
いる。

所与のオブジェクトについて、このデータは「ディスプ
レイ・リスト」と呼ばれる命令のリストの形で記憶され
る。このようなディスプレイ・リストを、ラスタ走査デ
ィスプレイ装置上の実際のイメージに変換するために、
メモリからリストを読み取り、データを処理し、次いで
生のピクセル・データをフレーム・バッファに書き込む
ディスプレイ・プロセッサを設ける。ラスタ操作時に、
リアル・タイムで、フレーム・バッファが読み取られ、
結果として得られるデータ・ストリームはアナログ・ビ
デオ信号に変換され、このビデオ信号はディスプレイ装
置に送られる。

本発明はこのようなコンピュータ・グラフィックス・シ
ステムのディスプレイ・プロセッサ部に設けられる機能
に関する。詳細にいえば、本発明は表示された三角形の
すべてのピクセル値に対する第３のパラメータ値に対応
するデータを、ピクセルの位置、及び第３のパラメータ
に関連した他のデータに基づいて生成することに関す
る。たとえば、いわゆるシェーディング問題において
は、所与の三角形のシェーディング情報が、三角形の頂
点の光度の形でディスプレイ・プロセッサに与えられ
る。あるいは、ディスプレイ・プロセッサに、オブジェ
クト表面、表面の向き、及び指定の光モデルのパラメー
タを与えることもできる。ディスプレイ・プロセッサは
この場合、三角形に関連する各ピクセルについて、与え
られた値に基づいて光度の値を計算しなければならな
い。

シェードの付けられるポリゴンが凹ポリゴン、セルフ・
インターセクティング・ポリゴンまたは多角形孔を有す
るポリゴン（以下、「凹ポリゴン」と総称する）を包含
している、シェーディング問題の特別な場合が存在す
る。凹ポリゴンのシェーディングの問題は２つの主要な
方法、すなわち（１）ポリゴンの凸形部分への分解、及
び（２）走査線アルゴリズムの使用で処理されていた。

第１の手法において、分解されたポリゴンを定義する各
凸形部分には、独立してシェードが付けられる。この手
法は「Triangulating a Simple Polygon」、M.R.Carey
et al.Information Processing letters、（June 197
8）、pp.175−179に記載されている。他の例が「Surfac
e Triangulation for Picture Production」、by B.Wor
denweber、IEEE CG＆Ａ（November,1983）、pp.45−51
に記載されている。この手法の主な欠点は、特に分解プ
ロシージャにおいて、付加的な頂点が導入されない場合
に、処理時間の増加によってシステム・パフォーマンス
が低下することである。付加的な頂点の生成を認めた場
合、頂点の数に対する線形時間挙動が得られる。しかし
ながら、処理はこれでも時間のかかるものである。この
別の手法の例は、「A Linear−Time Algorithm for Tri
angulating Simple Polygons」、by R.E.Tarjan and C.
J.Van Wyk,PROC Eighteenth Annual ACM Symnposium on
Theory of Computing（1986）pp.380−388で検討され
ている。また、オリジナルのポリゴンのエッジが２つま
たは３つの部分に分割される場合には、付加的な頂点の
導入は避けなければならない。丸めの誤差によって、部
分の線方程式は、オリジナルのエッジの方程式とは異な
ってくる。このことはアプリケーションがこれを描くこ
とを選択した場合に、オリジナルのポリゴンのエッジと
合致する線の可視性に問題を引き起こす。

走査線アルゴリズムを使用する、凹ポリゴンにシェード
を付ける第２の手法は、「Fundamentals of Interactiv
e Computer Graphics」、by J.D.Foley and A.Van Da
m、at pp.456−460（1985）で説明されている。この手
法の主な欠点は、エッジ・リストの分類、及びシェード
の付けられるポリゴンの各スパンに対する勾配（dZ/dX
/、dR/dX、dG/dX、dB/dX）の計算に付加的な時間が必要
なことである。

本発明は従来の凹ポリゴン処理手法に付随する上述のパ
フォーマンスの問題を解決するようになされており、凸
ポリゴンを処理するためにすでに標準となっている多く
のハードウェアを有利に使用する、凹ポリゴンの描出
（すなわち、塗りつぶしやシェーディング）手法を提供
する。

C.課題を解決するための手段 簡単にいえば、ディスプレイ・モニタに表示すべき複数
の線の各々に対する個々のピクセルを記憶するためにフ
レーム・バッファを含む、ディスプレイ・プロセッサ及
びディスプレイ装置を有するコンピュータ・グラフィッ
クス・ディスプレイ・システムにおいて、本発明は広い
意味で、フレーム・バッファ内の凹ポリゴンを描出する
方法を提供する。フレーム・バッファは通常、複数個の
アドレス可能なＭ×Ｎの構成（constituent）ピクセル
・ブロックに編成され、本方法は複数個のアドレス可能
なＭ×Ｎの構成ピクセルで構成されたマーク・バッファ
を使用する。本方法はポリゴンの境界に対応するマーク
・バッファ内のピクセルをマップし、ポリゴンの境界に
対応するフレーム・バッファ内のピクセルに記入するス
テップと、ポリゴンの内部に対応するマーク・バッファ
内のピクセルをマークするとともに、ポリゴンの境界に
対応するマークされたピクセルをマーク・バッファ内に
保存するステップと、ポリゴンの内部に対応するフレー
ム・バッファ内のピクセルを、マーク・バッファ内のマ
ークされたポリゴン内部のピクセルを参照して描くステ
ップからなる。

特定な実施例において、ディスプレイ・プロセッサは個
々のピクセルのＺ値を記憶するためのデプス・バッファ
を含んでおり、このバッファは複数個のアドレス可能な
Ｍ×Ｎの構成ピクセル・ブロックで構成されている。本
方法はさらに、ポリゴンの境界に対応するピクセルにお
ける該当するＺ値を、デプス・バッファに記憶するステ
ップと、前記ポリゴンの内部に対応するピクセルにおけ
るデプス・バッファ内のＺ値を、マーク・バッファ内の
マークされたポリゴンの内部のピスセルを参照して記憶
するステップを含んでいる。

さらに、本方法はポリゴンを一連の三角形に分割（tess
ellate）し、分解されたポリゴンを定義する三角形の各
々の向きを判定し、各三角形の内部に対応するマーク・
バッファ内のピクセルを処理して、同じ向きの隣接した
三角形の内部ピクセルをマークするとともに、異なる向
きの隣接した三角形の内部ピクセルを三角形の重畳領域
内でマークしないようにすることを含むことが好まし
い。概要を述べたマスキング、描出、及び記憶の各ステ
ップを実現する詳細なアルゴリズムが提供される。

他の実施例において、本発明は上述の方法を実現するデ
ィスプレイ・プロセッサからなる。プロセッサはコント
ローラ、コントローラから信号を受け取るように接続さ
れたエッジ／トライアングル生成手段、生成手段から信
号を受け取るように接続された第１組合せ論理手段、複
数個のＭ×Ｎの構成ピクセルで構成されたマーク・バッ
ファ、第１組合せ論理手段からのピクセル値及び生成手
段からのアドレス信号を受け取るように接続され、プロ
セッサによって使用されて、マーク・バッファ内にポリ
ゴンの境界及びポリゴンの内部のマークを形成するマー
ク・バッファ、ならびに生成手段からのアドレス信号及
びマーク・バッファからのピクセル値を受け取るように
接続された第２組合せ論理手段とを含んでいる。信号及
びピクセル値の入力に応じて、第２組合せ論理手段は処
理される各Ｘ、Ｙアドレスに対し、エッジ信号及び塗り
つぶし信号の一方を発生する。エッジ信号はポリゴンの
境界ピクセルに対応しており、塗りつぶし信号はポリゴ
ンの内部ピクセルに対応している。信号はフレーム・バ
ッファに送られる。

D.実施例 簡単に上述したように、本発明はポリゴンの座標、及び
その頂点にこれらの対応する輝度（すなわち、主に、た
とえば赤緑青（RGB）系を使用した、カラー）を与えた
ポリゴンを描出する（すなわち、塗りつぶしまたはシェ
ーディングを行なう）改善された方法及びプロセッサを
提供する。本発明は特に、凹ポリゴンの処理を目的とす
る。特に断らない限り、本明細書で使用する「凹ポリゴ
ン」とは、セルフ・インターセクティング・ポリゴン及
び多角形孔を有するポリゴンを含むものである。本発明
のすべての実施例において、ポリゴンの境界及び内部の
カラーは異なることができる。さらに、拡張された実施
例においては、ポリゴンの境界を記述する線は、たとえ
ば、点線、破線などの形式とすることができる。

まず、第１図には、総括的に10で示されているラスタ・
グラフィック・ディスプレイ・システムのいくつかの主
要構成部品が示されている。システム10はホスト・イン
ターフェース12、システム・メモリ14、システム制御プ
ロセッサ16、ディスプレイ・プロセッサ18、I/Oデバイ
ス20、２つのフレーム・バッファ22a及び22b、ならびに
モニタ24を含んでいる。これらの構成部品の各々は、IB
M5080などの市販コンピュータ・グラフィックス・ディ
スプレイ・システムの要素によって実現できる。簡単に
いうと、メモリ14、プロセッサ16及び18、ならびにI/O
デバイス20はシステム・バス13を介して互いに通信を行
ない、またシリアル・ホスト・インターフェース12を介
してホスト・コンピュータ（図示せず）と通信を行な
う。システム制御プロセッサ16は、グラフィックス・シ
ステム10のマスタ・コントローラを有している汎用プロ
セッサである。プロセッサ16は接続されたすべてのグラ
フィックスI/Oデバイス20にサービスを行ない、関連す
る処理をディスプレイ・プロセッサ18と整合させ、かつ
インターフェース12を介してホスト・コンピュータとイ
ンターフェースする。ディスプレイ・プロセッサ18はシ
ステム・メモリ14に常駐するディスプレイ・プログラム
のグラフィックス命令を実行するものであり、主として
ディスプレイ・モニタ24に現れるイメージの生成にかか
わっている。ディスプレイ・プロセッサ18は部分的に、
モニタ24に表示されるオブジェクトを表すポリゴンやポ
リラインなどの幾何学的プリミティブを作成する機能を
果たす。ディスプレイ・プロセッサはシステム・バス13
を介して、メモリ14から基本プリミティブを読み取り、
フレーム・バッファ・バス15によって、フレーム・バッ
ファ−Ａ 22a及びフレーム・バッファ−B22b内に希望
する画素を生成する。フレーム・バッファは通常２重に
なっており、これによって一方に描面プロセッサによっ
て書き込みを行ないながら、他方をモニタによって表示
することが可能となる。本発明を構成する方法及びシス
テムは主として、システム10のディスプレイ・プロセッ
サ18内で実現される。

標準的なハードワイヤード・トライアングル・ジェネレ
ータを使用してポリゴンを塗りつぶすように構成された
本発明の第１の基本実施例を、第２図に示す。（本実施
例に関連して使用する場合、「凹ポリゴン」という用語
の定義は、多角形孔を有するポリゴンを除くものとみな
される。）本実施例の利点は、ポリゴンのシェーディン
グ（後述）に使用されるものと同じトライアングル・ジ
ェネレータを使用することであり、したがって、シェー
ディング及び塗りつぶし両方の機能を、同一のハードウ
ェアに統合することができる。図示のように、プロセッ
サ18はコントローラ30、エッジ／トライアングル・ジェ
ネレータ82、第１組合せ論理回路34、第２組合せ論理回
路36、及びマーク・バッファ38を含んでいる。コントロ
ーラ30はμプロセッサであって、システム・メモリに記
憶されている命令リストの読取り解釈を行ない、幾何学
的変換を計算し、かつクリッピング、ライティング及び
デプス・キューイングなどの他の操作を行なう。エッジ
／トライアングル・ジェネレータ32はコントローラ30に
よって設定された操作モードに応じて、エッジ・ジェネ
レータまたはトライアングル・ジェネレータのいずれか
として機能する。３つの操作信号、すなわち現在の信号
がポリゴンの有効なピクセルからなっていることを示す
「VALID」（エッジまたはトライアングル生成モードの
いずれか）、ポリゴンを部分的に定義する三角形（以下
の説明参照）の向きの信号を出す「ORIENT」、及びジェ
ネレータ32がエッジ生成モードにあるときに活動状態と
なる「EDGE」が、ジェネレータ32から出力される。エッ
ジ生成モードにおいて、ジェネレータ32はポリゴンの２
つの頂点を接続するベクトルの点のアドレスのシーケン
スを生成する。このモードにおいて、信号VALIDはアド
レス線31がエッジ・ピクセルの実際のアドレスを含んで
いることを示す。また、エッジ生成モードにおいて、信
号EDGEは活動状態であり、信号ORIENTは非活動状態であ
る。

トライアングル生成モードにおいて、ジェネレータ32は
三角形の頂点のＸ及びＹ座標を受け取り、三角形を定義
するピクセルのアドレスのシーケンスを生成する。（４
つ以上の辺を有するポリゴンの頂点を処理する場合、周
知技術においては、頂点は一般に系統的な順序で、一度
に３つの頂点を組合せて処理されるので、システムは複
雑なポリゴンではなく、単純な三角形を処理することに
なる。）トライアングル生成モードにおいて、信号VALI
Dはアドレス線31が、三角形のピクセルの実際のアドレ
スを含むことを示す。信号EDGEはトライアングル生成モ
ードになったときに非活動状態となり、信号ORIENTは現
在の三角形の向きを示す。ORIENT信号は次のように定義
される。

ViVj×ViVk≧０の場合、ORIENT＝‘＋’ （１） ViVj×ViVk＜０の場合、ORIENT＝‘−’ （２） ViVjは頂点Viから頂点Vjへのベクトルであり、ViVkは頂
点ViからVkへのベクトルであり、×はクロス乗積演算で
ある。ORIENTは所与の三角形に対する定数である。

上述のように、コントローラ30はシステム・メモリに記
憶されている命令リスト内のポリゴン塗りつぶしコマン
ドを解釈し、トライアングル・ジェネレータ32に、ポリ
ゴンの頂点のＸおよびＹの座標を供給する。P1、P2、・
・・、PNをＮ辺のポリゴンの頂点とした場合、コントロ
ーラ30はエッジ・モードになったとき、ポリゴンの辺
（P1−P2、P2−P3、・・Ｐ（Ｎ−１）−PN）を描くよう
命令する。トライアングル・モードになったときに、コ
ントローラ30は次のように、ポリゴンを一連の三角形に
分割する。第１の三角形はP1、P2及びP3によって与えら
れ、第２の三角形はPl、P3及びP4によって与えられ、最
後の三角形はP1、PN−１及びPNによって与えられる。コ
ントローラ30はジェネレータ32に、三角形ごとに該当す
る頂点のデータをロードする。

マーク・バッファ38はそれぞれが２ビットの深さのＭ×
Ｎの位置で構成されたバッファ・メモリからなる。Ｍ×
Ｎの位置はＭ×Ｎの典型的なモニタ・サイズに対応する
ように選択される。２ビット平面によって、各Ｘ、Ｙ位
置は４つの信号の１つを記憶することができる。信号は
この説明において、「＋」、「−」、「ｅ」、及び
「０」というラベルが付けられる。バッファ38は組合せ
論理回路34によって更新され、各Ｘ、Ｙアドレスはジェ
ネレータ32から線31を介して受け取られる。

組合せ論理回路36はシステム・フレーム・バッファ22a
及び22bに対して、信号「EDGE_PX」及び「FILL_PX」を
出力する。活動EDGE_PX信号は現在の点がエッジ・ポイ
ントであることを示す。このエッジ・ポイントに対応し
ているＸ、Ｙアドレス（線31を介した）は、エッジのカ
ラーとともにフレーム・バッファに書き込まれる。活動
信号FILL_PXは線31上のＸ、Ｙアドレスによって与えら
れる対応する位置を、フレーム・バッファ内で、内部カ
ラーで塗りつぶさなければならないことを示す。フレー
ム・バッファへのアドレス線上の信号は、マーク・バッ
ファへのアクセス時間を考慮して遅延することが好まし
い。これは当技術分野において、ラッチ回路33を使用す
ることによって容易に達成される。

塗りつぶすべき各ポリゴンに対し、本方法はＸ、Ｙ座標
を通る３本のパス及びポリゴンを表す輝度を必要とす
る。ただし、マーク・バッファ38はまずクリアされる。
すなわち、バッファの各ピクセルは最初のポリゴンの処
理に進む前に、値「０」にセットされる。最初のパスに
おいて、トライアングル・ジェネレータ32はエッジ生成
モードで作動し、（１）各ポリゴン・エッジの点のアド
レス・シーケンスを生成し、（２）VALIDエッジ・アド
レスに対応する位置に値「ｅ」を書き込むことによっ
て、マーク・バッファ38内のポリゴンのエッジをマーク
する。第２のパスにおいて、分割されたポリゴンの各三
角形について、ジェネレータ82は（１）三角形のアドレ
ス・シーケンスを生成し、（２）各有効アドレスにある
マーク・バッファ38に第１表による新しいバッファ値を
ロードすることによって、ポリゴンの内部に対応するバ
ッファ38内のピクセルをマークする。

真理値表１は第１の組合せ論理回路84に常駐するもの
で、当分野の技術者によって簡単に実現できる。

データ構造を通過する第３のパスにおいて、ポリゴンを
表す各三角形について、トライアングル・ジェネレータ
は（１）三角形の点のアドレス・シーケンスを生成し、
（２）アドレスＸ、Ｙが有効であり、この位置における
マーク・バッファ38の内容が‘e'であれば、信号EDGE_P
Xを発生し、（３）アドレスＸ、Ｙが有効であり、この
位置におけるマーク・バッファ38の内容が‘＋’または
‘−’であれば、FILL_PXを活動化し、（４）アドレス
Ｘ、ＹがVALIDであれば、マーク・バッファ38を再初期
設定する。EDGE_PX及びFILL_PX信号を発生する論理は回
路36で実現される。マーク・バッファ38の再初期設定
は、組合せ論理回路34によって行なわれる。

第３図は凹ポリゴン40の例を示すが、この図において、
ポリゴン40は頂点P1、P2、P3、P4、P5によって定義され
る。ポリゴン40の分割によって形成される結果として生
じる三角形を第4A図一第4C図、ならびにORIENTのそれぞ
れに対応する値で示す。第5A図一第5C図は、ジェネレー
タ32が上述の処理の第２のパスにおいて各三角形P1P2P3
P、P1P3P4及びP1P4P5を処理した後の、マーク・バッフ
ァ38の内容を示す。

本発明の他の拡張された実施例を、第６図及び第７図に
示す。この実施例において、ディスプレイ・プロセッサ
18′は座標及びその頂点における輝度を与えられたポリ
ゴンにシェードを付けるように作動する。また、ポリゴ
ンの境界をたとえば、点線や破線などのスタイルにする
ことができる。この実施例は補間関数が面で表される場
合に、最良の作動を行なう。また処理対象の幾何学的プ
リミティブを、単一のポリゴン・コマンドによっていく
つかのサブポリゴンまたはサブエリアで構成することも
できる。単一のコマンドによってグループ化されたすべ
てのサブエリアは、本発明にしたがって三角形ごとにま
とめて処理される。

第６図において、ディスプレイ・プロセッサ18′はシス
テム・バス13を介して、ディスプレイ・システムと通信
を行なう。プロセッサ18′はコントローラ50、Ｘ−Ｙジ
ェネレータ52インタポレータ54、ライン・スタイル・ジ
ェネレータ56、マーク及びデプス・バッファならびにこ
れらに関連した組合せ論理回路58、ならびにディレイ回
路60を含んでいる。マーク・バッファ及びユニット58内
のこれをサポートする論理回路を除き、これらの構成要
素の各々はコンピュータ・グラフィックス・システムの
市販の要素で構成することができる。第２図に示した実
施例のコントローラ30と同様に、コントローラ50はシス
テム・メモリに記憶された命令リストを読み取り、解釈
し、必要な幾何学的変換、及びクリッピング、ライティ
ング、デプス・キューイングなどの他の操作を計算す
る。命令リストの一部として、各頂点に関連した境界フ
ラグが通常与えられる。たとえば、第１のフラグはポリ
ゴン境界の実エッジまたはスタイル・エッジからなる
「リアル・エッジ」を定義し、第２のフラグは境界エッ
ジ（以下「レギュラー・エッジ」と呼ぶ）が内部カラー
を受け取るものであることの信号を出し、第３のフラグ
はフロントまたはバックＺ軸クリッピング面のそれぞれ
に対するポリゴンのクリッピングによって生成された、
フェイクＺフロント・エッジまたはフェイクＺバック・
エッジを定義することができる。（フェイクＸ及びＹエ
ッジはクリッピング処理において、「レギュラー・エッ
ジ」と識別される。）これらのフラグを以下で詳述する
処理のいくつかの態様で使用すると有利である。

コントローラ50はＸ−Ｙジェネレータ52、インターポレ
ータ54、ライン・スタイル・ジェネレータ56、ならびに
マーク・バッファ及びデプス・バッファ・ユニット58の
論理回路で構成されたレンダリング・パイプラインと通
信する。各ポリゴン・プリミティブ及びその各頂点に対
して、位置（X,Y,Z）、内部カラー（たとえば、Ｒ、
Ｇ、Ｂ）及びエッジ・カラー（Ｒ、Ｇ、Ｂ）を、レンダ
リング・パイプラインに利用できる。

ジェネレータ52は取りうる２つの操作モード、すなわち
（１）ベクトル生成モード及び（２）トライアングル生
成モードに対応するＸ及びＹ座標のシーケンを生成す
る。ベクトル生成モードにおいて、ジェネレータ52はベ
クトルの２つの端点の座標を与えられて、周知のブレゼ
ンナムのアルゴリズムなどのベクトル生成アルゴリズム
を実現する。このアルゴリズムはスクリーン・スペース
内にＸ、Ｙ座標のシーケンスをもたらすが、これは幾何
学的直線を最もよく近似するものである。最初及び最後
に生成された点、すなわち端点は常に幾何学的直線上に
ある。しかしながら、中間点は２つの端点が定義する特
定の線によっては、幾何学的直線上にあることも、ない
こともある。以下で詳述するように、本発明で好ましく
実現されるベクトル・ジェネレータは、正確に幾何学的
直線上にあるのは、生成されたシーケンスのどの点かを
検出し、これによってコントローラ50の命令による２つ
の「サブモード」、すなわち（１）正規生成モード、及
び（２）オン・ジオメトリック・ライン生成モードが可
能となる。後者のモードは正確に幾何学的直線上にある
点のみを生成する。

トライアングル生成モードにおいて、Ｘ−Ｙジェネレー
タ52を、たとえば、当分野の技術者が構成し、３つの所
与の頂点によって定義される三角形の内部または正確に
エッジ上にあるすべての点を生成することができる（そ
れゆえ、以下で説明する処理で、オン・ジオメトリカル
・ライン・ベクトル生成サブモードが必要となる）。あ
るいは、このプロセスをベクトル生成モードにおいて、
三角形のエッジに対応する点を生成できる限り、より典
型的な、精度の低いトライアングル生成手法で実現する
こともできる（以下で、詳述する）。

トライアングル生成モードにおいて、ジェネレータ52は
２進変数ORIENTを計算するが、これはこの場合も、三角
形の向きを示し、方程式（１）及び（２）によって定義
される。ORIENTの値を、たとえば、Ｘ−Ｙジェネレータ
52内の適当な状況レジスタによって、コントローラ50が
利用できる。Ｘ−Ｙジェネレータ52は制御信号をインタ
ーポレータ54へ、また検証信号（VALID）をライン・ス
タイル・ジェネレータ56へもたらす。ジェネレータ52か
ら出力され、コントローラ50によって制御される信号OP
ERは制御信号を、ライン・スタイル選択活動化、デプス
・バッファの制御などのレンタリング・パイプラインの
論理のさまざまな部分に配布する。

インターポレータ54も２つの作動モード、すなわちベク
トル・モードとトライアングル・モードを有している。
インターポレータ54は周知の態様で、端点における対応
する値から、ベクトルの点に対するＺならびにＲ、Ｇ及
び（原色）の補間された値を生成するか（ベクトル生成
モードの場合）、頂点の対応する値から三角形の点の補
間された値を生成するかする（トライアングル生成モー
ドの場合）。ベクトル・モードにおいて、インターポレ
ータ54は「Incremental Linear Interpolation」、D.Fi
eld、ACM Transactions on Craphics、Volume4,No.1、
（January 1985）という記事に記載されている方法を実
現することができる。トライアングル・モードにおいて
は、米国特許明細書第4805116号に開示されているよう
な方法が適当である。両方のモードにおいて、インター
ポレータ54はＸ−Ｙジェネレータ52の制御のもとで、ジ
ェネレータと同期して作動し、補間された各点のＸ、
Ｙ、Ｚ、Ｒ、Ｇ、及びＢの値がフレーム・バッファで同
時に利用できるようになる。これは部分的に、Ｒ、Ｇ、
Ｂディレイ回路60によって達成される。

ライン・スタイル・ジェネレータ56は、Ｘ−Ｙジェネレ
ータ52がベクトル生成モードのときに作動する。ジェネ
レータ56は信号「GAP」を発生し、現在のピクセルが線
の活動セグメントに属しているか、またはセグメント間
のギャップに属しているかを示す。すなわち、スタイル
化された線が存在していると想定する。ライン・スタイ
ル・ジェネレータ56の適当な実施形態は、周知の文献か
ら入手できる。

マーク・バッファ及びデプス・バッファ・ユニット58
は、マーク・バッファと組み合わされたデプス・バッフ
ァで周知のＺバッファ・アルゴリズムを実施して、凹ポ
リゴンのシェーディングを可能とする。この組合せはＺ
バッファ作動を拡張するものであって、本発明の中心を
なすものである。デプス・バッファはＭ×Ｎのメモリで
あり、通常はビット深さが16ないし32ビットであって、
この内部にＺ（X,Y）値がＺバッファ・アルゴリズムと
同様な態様で記録される。ＭとＮは通常、画面の寸法で
ある。マーク・バッファもデプス・バッファと同じサイ
ズのメモリであるが、ビット深さはたとえば２ビットに
過ぎないものである。バッファは両方ともＸ−Ｙジェネ
レータ52からのＸ及びＹ座標出力によってアドレスされ
る。

第７図はマーク・バッファ及びデプス・バッファ回路58
を、より詳細に示すものである。Ｘ、Ｙ座標はデプス・
バッファ62及びマーク・バッファ64の両方に供給され、
処理中のピクセル位置を識別する。位置X,YにおけるＺ
の値はインターポレータ54から、比較器68に供給され、
この比較器は新しい値を、位置X,Yにおけるデプス・バ
ッファ62の内容と比較し、たとえば、右側の座標系につ
いて、Ｚ（X,Y）≧Z_OLDであるかどうかを判定する。ト
ランスペアレント・ラッチ66をタイミングを取るために
使用して、Z_OLDを遅延させる。比較器68からの出力ZCO
MP_OUT、ならびに信号GAP、VALID及びマーク・バッファ
64の対応する位置X,Yの内容（MB_OLD）を使用して、第
１組合せ論理回路70を介して信号PIXEL_VALID及びZ_UPD
ATEを生成する。PIXEL_VALIDを使用して、フレーム・バ
ッファ（第１図）に、現在のピクセルが有効であるか
ら、受け入れるべきであるとの信号を出す。Z_UPDATEは
新しいＺの値Ｚ（X,Y）を、この位置におけるデプス・
バッファの古い内容と置き換えるべきであることを示
す。この信号をマルチプレクサ72に供給し、Ｚ（X,Y）
とZ_OLDの間のこの選択を指示する。

同様な態様で、位置X,Yにおけるマーク・バッファ64の
内容（MB_OLD）（トランスペアレント・ラッチ65を介し
た）、ならびに信号VALID、GAP及びZCOMP_OUTを第２組
合せ論理回路74で使用して、位置X,Yにおけるマーク・
バッファ64の内容と置き換えることを目的としたマーク
・バッファ値を生成する。マーク・バッファ64の性質に
ついては、以下で詳述する。信号OPERは組合せ論理回路
70及び74に対する制御信号であって、シェーディング・
アルゴリズムの演算を可能とし、かつそのさまざまなス
テップを識別する（後述） 本発明のこの実施例によれば、２ビット・プレーン・マ
ーク・バッファ64は、各位置における４種類の値のうち
の１つを記憶することを可能とする。これらのマーク値
には、次のようなラベルが付けられる。

‘O':初期状態。クリアされたピクセル ‘i':内部ピクセル ‘g':エッジ・ギャップ・ピクセル ‘e':エッジ・セグメント・ピクセル 組合せ論理回路74は２つの入力値、すなわちマーク・バ
ッファの内容（すなわち、MB_OLD）とアルゴリズムによ
って指定される何らかの他の値の間の論理演算（以下の
アルゴリズムの説明においては、‘■’と記号化する）
を実施する。真理値表２は、MB_OLDと置き換えるために
マーク・バッファ64に記憶される値を明らかにするもの
である。

第２表を調べれば、‘■’演算が相互的なものであり、
また信号が入力のいずれかに現れた場合に、値‘e'が出
力に現れることから、これが高い優先順位を有している
ことがわかろう。値‘g'はこの点で同様なものである
が、この信号が‘e'よりも低い優先順位を有しているこ
とが異なっている（すなわち、‘e'、‘■’、‘g'＝
‘e'である）。これが意味するところは、エッジ・セグ
メント・ピクセルにはエッジ・ギャップ信号よりも高い
優先順位が与えられるということだけである。‘■’演
算は本質的に値‘0'及び‘i'に関する排他的論理和演算
である。以下の説明から明らかなように、マーク・バッ
ファ64における‘■’演算はあらゆる内部ピクセルに対
するポリゴン境界ピクセルを、またエッジ・ギャップ・
ピクセルに対するエッジ・セグメント・ピクセルを保存
するようになされている。偶数回書き込まれた内部ピク
セルは‘0'のマークされた値をもたらし、これは最終的
なピクチュアの凹面または孔を排除するのに有利なもの
である。本発明の実施例の１つの実施アルゴリズムを、
以下で検討する。

この場合も、該当する処理ステップがジェネレータ52か
らのOPER信号によって識別される。アルゴリズムは暫定
条件として、マーク・バッファの各ピクセルが値「０」
に初期設定され、かつデプス・バッファの各ピクセルが
最も遠いＺ値に対応した値に初期設定されるものと想定
する。各ステップはレンダリング・パイプラインを通る
別々なパスを含んでいる。

ステップ１ このステップの目的はマーク・バッファ内のポリゴンの
境界をまずマークして、これが以降の処理で保存される
ようにすることである。この場合も、エッジをスタイル
化することができる。「リアル・エッジ」、「レギュラ
ー・エッジ」、及び「Ｚフェイク・エッジ（偽エッ
ジ）」のフラグがまず、処理される境界エッジのタイプ
を識別する。「セグメント」ピクセルが、エッジ・カラ
ーによって描かれる。「リアル・エッジ」のエッジ「ギ
ャップ」ピクセルはフレーム・バッファ内に描かれず、
後で内部カラーが割り当てられる。「レギュラー・エッ
ジ」ピクセルは同様にして処理される。Ｘ−Ｙジェネレ
ータ52及びインターポレータ54はベクトル・モードにセ
ットされ、ポリゴンのエッジを生成する。ポリゴンのエ
ッジの各ピクセルに対し、マーク・バッファ、デプス・
バッファ、及びフレーム・バッファの操作は、次のよう
にライン・スタイル・ジェネレータ56の出力によって決
定される。

ライン・スタイル・ギャップ・ピクセル： マーク・バッファ： If ZCOMP_OUT＝“真”（たとえば、Ｚ（X,Y）≧ZB_OL
D） デプス・バッファ： If（ZCOMP_OUT＝“真”及びMB_OLD‘e'） Then DB＜＝Ｚ（X,Y） フレーム・バッファ： 変更なし。

ライン・スタイル・セグメント・ピクセル マーク・バッファ： If（ZCOMP_OUT＝，“真”またはMB_OLD＝‘g'） Then MB＜＝‘e' デプス・バッファ： If（ZCOMP_OUT＝“真”またはMB_OLD＝‘g'） Then DB＜＝Ｚ（X,Y） フレーム・バッファ： If（ZCOMP_OUT＝“真”またはMB_OLD＝‘g'） Then FB＜＝R,G,B この場合も、■演算は第２表で定義されている。上記の
アルゴリズムは標準のブーリアン演算であって、当分野
の技術者が実行できるものである。デプス・バッファ及
びフレーム・バッファの処理は組合せ論理回路70で実施
され、マーク・バッファの処理は組合せ論理回路74に常
駐している。上記のアルゴリズムから、処理対象の点が
エッジ・ギャップ・ピクセルからなっており、Ｚの値
が、たとえば、X,Yに記憶されているデプス・バッファ
の値以上であれば、マーク・バッファが以前の点の処理
からの値‘e'をすでに保持していない限り、マーク・バ
ッファには値‘g'が割り当てられることがわかる。ま
た、エッジ・セグメント・ピクセルとエッジ・ギャップ
・ピクセルがマーク・バッファに描かれ、可視のＺ（X,
Y）値がデプス・バッファに割り当てられ、Ｚ（X,Y）が
可視のエッジ・セグメント・ピクセルである（すなわ
ち、ZCOMP_OUT＝‘真’）と、デプス・バッファが示し
ている場合には、この点におけるカラーＲ、Ｇ、Ｂがフ
レーム・バッファに割り当てられることに留意された
い。

ステップ２ このステップの目的はマーク・バッファ内のポリゴンの
内部をマークすることである。これを達成するため、Ｘ
−Ｙジェネレータとインターポレータを、トライアング
ル生成モードにセットする。P1、P2、・・・PNがポリゴ
ンの頂点であり、Q1、Q2、・・・QMがポリゴ内の孔の頂
点であれば（すなわち、存在している場合）、コントロ
ーラはＸ−Ｙジェネレータとインターポレータに、三角
形P1P2P3、P1P3P4、・・・P1（PN−１）PNを生成するよ
う命令する。同様に、処理されるポリゴンが孔を含んで
いるのであれば、三角形Q1Q2Q3、Q1Q3Q4、・・・Q1（QM
−１）QMが生成される。上述のように、第３図及び第4A
図−第4C図は、３つの三角形に分割された凹ポリゴンの
例を示している。三角形１、２、３がまず生成され、次
いで、三角形１、３、４が生成され、最後に、三角形
１、４、５が生成される。第１と第２の三角形が生成さ
れた後、マーク・バッファは凸ポリゴン１、２、３、４
に対応するマークを含む（第5B図）。最後の三角形が生
成されると、向きが反対の隣接する三角形の重畳領域
１、４、５が、■演算で暗黙の排他的論理和関数によっ
て、この凸ポリゴンから差し引かれる（第5C図）。ステ
ップ１で使用される値‘e'及び‘g'が優先権を有してい
るので、エッジ１、５及び５、４は差し引かれない（第
２表参照） この実施例において、隣接する三角形に共通の点に、特
に注意を払わなければならない。たとえば、第３図の内
部線１、３に沿った共通の点を、■演算によるこれらの
ピクセルの最初の排他的論理和除去とかかわりなく、保
存しなければならない。あるいは、線１、４に共通なこ
れらのピクセルは凹ポリゴンの外部のものであるから、
これらのピクセルを保存してはならない。この問題の解
は、隣接する２つの三角形の向き（すなわち、ORIENTの
値）が同じ場合に、共通点を再度生成することである。
これは線１、３の場合であって、線１、４の場合ではな
い。上述のように、トライアングル生成モードで作動す
るＸ−Ｙジェネレータが、幾何学的三角形の内部または
正確に境界上にある点のみを作成するのが好ましいの
で、共通の点が整数のＸ及びＹ座標を有する幾何学的
（真の直線）のものでなければならないということにな
る。これを達成するために、コントローラはＸ−Ｙジェ
ネレータに、同じ向きの隣接する三角形に対して、ベク
トル・モードのオン・ジオメトリカル・ライン・サブモ
ード（後述）で共通の点を生成するよう命令する。

このステップの両方の場合、すなわちトライアングル生
成モード及びベクトル生成モードにおいて、マーク・バ
ッファ、デプス・バッファ及びフレーム・バッファの作
動は次のようになる。

マーク・バッファ： MB＜＝‘i'■ MB_OLD デプス・バッファ 変更なし。

フレーム・バッファ 変更なし。

デプス・バッファ及びフレーム・バッファに書き込みが
行なわれないのであるから、Ｚ、Ｒ、Ｇ、及びＢの値が
このステップでは必要なく、このステップがマーク・バ
ッファ内にポリゴンの適正なアウトラインを生成するだ
けであることに留意されたい。

オン・ジオメトリック・ライン・サブモードのための回
路の実施形態の１つを、第８図に示し、かつ第３表で定
義する。従来、ベクトル・ジェネレータは画面の座標
（X,Y）のシーケンスを生成し、これは２つの所与の端
点をつなぐ幾何学的直線を最もよく近似するものであ
る。ブレゼンハム・アルゴリズムにおいて、幾何学的直
線に関して生成された各ピクセルの位置誤差は0.5ユニ
ット以下である。誤差は生成されたベクトルの端点にお
いて、またおそらく若干の中間点においてゼロである。
しかしながら、本発明で使用するマーク生成手法では、
必要なものは、誤差がゼロのこれらの点だけである。第
８図はこのようなゼロ誤差デテクタを実現する新規の論
理回路からなっている。破線80内の論理回路は、周知の
ブレゼンハムのベクトル・ジェネレータに存在している
ものである。

下記の設定手順は外部のマイクロプロセッサまたはハー
ドウェア論理回路によって実現され、点P1（X1,Y1）か
らP2（X2,Y2）へのベクトルを描く。

第1: DX及びDYは次のように計算される。

DX＝ABS（X2−X1） DY＝ABS（Y2−Y1） ただし、ABS＝絶対値 第2: 操作のOCTANTは下記の論理式によって決定される。

DX≧DY X2≧X1 Y2≧Y1 ３ビットの信号OCTANTはこれら３つの式の結果によって
発生される。

第3: レジスタINCP、INCN、及びD1（第８図）には、OCTANT信
号を導くために第１及び第２ステップで数値を求めた論
理式の関数として、第３表によって与えられる値がロー
ドされる。

第4: レジスタD2（第８図）をクリアする。

第5: Ｘカウンタ及びＹカウンタに、X1及びY1をそれぞれロー
ドする。

第6: 信号MODEを次のように操作のモードにしたがって発生す
る。

MODE＝０＝「オン・ジオメトリック・ライン」点を生成
する。

MODE＝1:ベクトルのすべての点を生成する。

上記の手順の各々が４番目及び６番目の操作を除き、通
常のブレゼンハム・アルゴリズムに必要なことに留意さ
れたい。

第８図において、作動時に、レジスタD1≦０であれば
（すなわち、レジスタD1の符号ビット、信号SIGN_D1＝
１または負）、値INCN 83が加算器ADD−１ 82及びADD
−２ 84のそれぞれによって、レジスタD1 77及びD2
79に加えられる。それ以外の場合には、値INCP 81がレ
ジスタD1 77及びD2 79に加えられる。組合せ論理回路
86はD1の符号ビット（すなわち、信号SIGN_D1）及び第
３表に示す信号OCTANT（XINC及びYINC欄）の関数として
Ｘカウンタ88及びＹカウンタ90を増分または減分する。
増分または減分がSIGN_D1＝０（すなわち、D1≧０）の
場合にのみ生じることを、表の項目のアスタリスクが意
味していることに留意されたい。回路86は発生されたピ
クセルが有効な場合に、VALID信号を断定する。

D2＝０の状態はNOR回路92によって検出され、MODEがゼ
ロであれば、VALIDはOR回路94によりAND回路96を通過し
て、ピクセルの有効化をもたらす（信号PIXEL_VALI
D）。D2 79の内容が０でない場合、ピクセルはこれが
生成されていることにかかわりなく、有効とはされな
い。MODEが１の場合（正規モード）、PIXEL_VALIDは有
効となる。

上記のオン・ジオメトリック・ライン・サブモード処理
の他の手法は、第２図に関連して本明細書で説明したよ
うな手法を実現することである。たとえば、３ビットの
平面をマーク・バッファとして使用した場合、信号‘i'
を上述の‘＋’及び‘−’の内部信号に分割することが
できる。第１表の論理を実施することによって、内部線
を再生成する必要がなくなる。しかしながら、このよう
な手法の欠点は、付加的なビット平面に関連して、余分
なコストがかかることである。

本実施例のポリゴン処理ステップに戻ると、マーク・バ
ッファ内でポリゴンの内部をマークした後、コントロー
ラはステップ３に進む。

ステップ３ このステップの目的はマーク・バッファを参照して、あ
るいはマーク・バッファの制御のもとでポリゴンの内部
の点を描くことである。たとえば第３図の三角形１、
４、５に対応する点が生成されるが、これらをマーク・
バッファによってフレーム・バッファに書き込むことは
認められない。フレーム・バッファに書き込まれた内部
の点に関するマーク・バッファは、同時にクリアされ
る。Ｘ−Ｙジェネレータ及びインターポレータはトライ
アングル・モードにセットされ、ポリゴンの内部の点の
Ｚ値と輝度を生成して、ステップ２に関連して上述した
ものと同様な態度で、デプス・バッファに記憶し、フレ
ーム・バッファへの描出を行なう。このステップにおけ
るバッファの作動は、次のように説明できる。

マーク・バッファ： If（MB OLD）＝‘i'） Then MB＜＝‘0' デプス・バッファ： If（Ｚ COMP_OUT＝“真”及びMB_OLD＝‘i'） Then DB＜＝Ｚ（X,Y） フレーム・バッファ： If（ZCOMP_OUT＝“真”及びMB_OLD＝‘i'） Then FB＜＝Ｚ（X,Y）においてR,G,B ステップ４ このステップの機能は、この場合もマーク・バッファの
制御のもとで、スタイル化されたポリゴンの境界のギャ
ップ点（すなわち、値‘g'を有する点）を、この場合
も、マーク・バッファの制御のもとで描くことである。
Ｘ−Ｙジェネレータ及びインターポレータはベクトル・
モードにセットされ、ポリゴン・エッジ・ポイントを生
成する。バッファの作動は、次のように表される。

マーク・バッファ： 変更なし デプス・バッファ： 変更なし フレーム・バッファ： If（ZCOMP_OUT＝“真”及びMB_OLD＝‘g'） Then FB＜＝（X,Y）においてR,G,B ステップ５ このステップの目的はポリゴンの処理に引き続き、マー
ク・バッファをクリアすることである。Ｘ−Ｙジェネレ
ータはベクトル・モードにセットされ、ステップ３でマ
ーク・バッファからクリアされたポリゴン境界、内部点
を生成する。このステップにおけるバッファの作動は次
のとおりである。

マーク・バッファ： MB＜＝‘0' デプス・バッファ及びフレーム・バッファ 変更なし 処理対象の凹ポリゴンが「リアル・エッジ」 みを有しており、エッジ・ギャップがない場合、上記の
アルゴリズムは次のように表すことができる。

ステップ１ ポリゴンの境界はマークされ、マーク・バッファ、デプ
ス・バッファ及びフレーム・バッファの作動は次のよう
になる。

マーク・バッファ： If（ZCOMP_OUT）＝“真”） Then MB＜＝‘e'■ MB_OLD デプス・バッファ If（ZCOMP_OUT） Then DB Ｚ フレーム・バッファ If（ZCOMP_OUT）＝‘真’） Then FB＜＝（X,Y）においてR,G,B ステップ２ このステップの目的はマーク・バッファ内部のポリゴン
の内側をマークすることである。マーク・バッファ、デ
プス・バッファ及びフレーム・バッファの作動は次のと
おりである。

マーク・バッファ MB＜＝‘i'■ MB_OLD デプス・バッファ及びフレームバッファ： 変更なし ステップ３ このステップの目的は、マーク・バッファを参照して、
あるいはマーク・バッファの制御のもとでポリゴンの内
部の点を描くことである。バッファの作動は次のとおり
である。

マーク・バッファ： If（MB_OLD＝‘i'） Then MB＜＝‘0' デプス・バッファ： If（ZCOMP_OUT＝“真”及びMB_OLD＝‘i'） Then DB＜＝Ｚ（X,Y） フレーム・バッファ If（ZCOMP_OUT＝“真”及びMB_OLD＝‘i'） Then FB＜＝（X,Y）においてR,G,B ステップ４ 定義により、このステップの機能は適用されない。

ステップ５ 最後のステップはポリゴンの処理に引き続きマーク・バ
ッファをクリアすることである。バッファの作動は次の
とおりである。

マーク・バッファ： MB＜＝‘0' デプス・バッファ及びフレーム・バッファ： 変更なし この実施例において、論理濱算‘■’は第４表に記載す
るように定義される。

本発明の方法及びプロセッサを実施する際に、フロント
またはバックのＺ軸クリッピング面に対してクリップさ
れたポリゴンを描くには、特に注意を払わなければなら
ない。たとえば、第９図は２つのサブエリア、すなわち
１、２、３、４及び11、12、13、14を有するボリゴン・
プリミティブを示す。後者のサブエリアは前者のサブエ
リアにある孔を定義する。上述のアルゴリズムは第１の
サブエリア（エッジ及び内部の点）、ならびに第２のサ
ブエリア（エッジ及び内部の点）を生成する。この処理
に固有なEX−OR関数は、第２のサブエリアの内部の点を
除去し、孔をもたらす。しかしながら、EX−OR演算が境
界点に適用されないので、第２のサブエリアのエッジの
点（すなわち、孔の境界）は除去されない。

クリッピング・ボックスのフロント及びバックのＺ軸面
に対してポリゴン・ブリミティブをクリップすると、第
10図に示すような構造を得ることができる。図示のよう
に、２つの新しいサブエリア、すなわちサブエリア１、
２′、３′、４、及び11、12′、13′、14が生成され
る。エッジ２′、３′及び12′、13′をＺフェイク・エ
ッジ、つまり偽のエッジと呼ぶ。上述のようにポリゴン
のマークを生成した場合、これらのＺのフェイク・エッ
ジに問題が生じる。詳細にいえば、セグメント12′、1
3′は孔に対応しているのであるから、エッジが現れる
筈はなく、ポリゴンの境界としてマークしてはならな
い。しかしながら、画面座標の量子化により（すなわ
ち、Ｘ及びＹが整数であるため）、エッジ２′、３′が
エッジ12′、13′に正確に重ならないことがある。結果
として、この処理に固有なEX−OR演算は、いくつかの点
においてうまくいかないことがある。この問題はＸフェ
イクまたはＹフェイク・エッジ（すなわち、Ｘ軸または
Ｙ軸のクリッピング面に対するクリッピングによって生
じたエッジ）には存在しないが、これはこれらのセグメ
ントがそれぞれ垂直または水平であり、かつEX−OR演算
が失敗することがないからである。

この問題に鑑み、上記の方法と共同するソフトウェアで
実現された解決策が考案されており、この組合せの詳細
を第13図−第17図を参照して以下に詳述する。ただし、
この付加的な処理手法の概要をまず説明する。

マーク生成プロセスのステップ１において、Ｚフェイク
・エッジ（クリッピング・ステージにおいて識別され
た）は生成されるのではなく、リストに保管されている
（すなわち、フェイク・エッジを定義する２つの端点に
よって）。バックのＺ軸クリッピング面に対するポリゴ
ンのクリッピングによって作成されたフェイク・エッジ
のもの、及びフロントのＺ軸クリッピング面に対するポ
リゴンのクリッピングによって生じるＺフェイク・エッ
ジのものという、２つのこのようなリストが維持され
る。Ｚフェイク・エッジの勾配の向きが垂直よりも、水
平に近い場合には、各空でないリストはＸによって分類
される。それ以外の場合には、Ｙによって分類される。
当分野の技術者には、Ｚ軸クリッピング面とのポリンゴ
ン面の交点の勾配を、たとえばポリゴン法線のＸ及びＹ
成分を検査することによって、容易に得ることができる
ことが認識されよう。第５表は分類（ソート）の前後に
おける、第10図に示したＺフェイク・エッジの頂点リス
トを示す。

マーク生成プロセスのステップ１を完了するために、分
離された第１の点から第２の点へのセグメント、次いで
第３の点から第４の点へのセグメントなどを生成するこ
とによって、Ｚフェイク・エッジをマークする。これが
達成されたら、マーク・バッファはクリップされたポリ
ゴンの真の境界を含む（すなわち、第10図の線12′、1
3′などのセグメントは除かれる）。

マーク生成プロセスのステップ２において、内部の点が
生成される。ただし、各サブエリアの定義は変更され、
考察の対象の特定のＺフェイク頂点の間にある他のサブ
エリアのあらゆる頂点を含むようになっている。たとえ
ば、新しいサブエリア１が１、２′、12′、13′、
３′、４として再定義される。頂点12′及び13′がポリ
ゴンの頂点のリストに人為的に追加されたことがわか
る。第２のサブエリアは依然として11、12′、13′、14
である。この処理の結果として、変更された第１サブエ
リアのエッジ12′、13′は第２のサブエリアの同じエッ
ジと一致し、したがって、上記の処理に固有なEX−OR演
算はマークから第２のサブエリア・エッジを消去する。

しかしながら、場合によっては、完全なキャンセルが行
なわれないこともある。このような特別な場合には、マ
ークを分類されたリストの２番目から３番目の点へ向か
うベクトル、４番目から５番目へ向うベクトルなどにつ
いて、クリアすることが必要となる。例においては、セ
グメント12′、13′が生成され、対応するマーク・バッ
ファ位置がクリアされる。この活動の必要性を、以下で
説明する。

第11図は第10図のクリップされたポリゴンを示すもので
あり、Ｘ及びＹの量子化によるフェイク・エッジによる
位置誤差が、検討のために誇張されている。また、クリ
ッピング・ステージが次の順序で、サブエリアの頂点を
もたらすと想定している。

サブエリア1:2′、１、４、３′ サブエリア2:11、12′、13′、14 第２のサブエリアの順序は、この説明には無関係であ
る。マーク生成プロセスの第１のステップにおいて、エ
ッジ２′、１、１、４及び４、３′はポリゴンの境界エ
ッジとしてマークされる。次いで、エッジ11、12′;1
3′、14及び14、11が生成される。Ｚフェイク頂点リス
トが分類され、セグメント２、12′及び13、３′が生成
される。ステップ２において、三角形２′、１、４（第
12図（ａ））;2′、４、３′（第12図（ｂ））及び
２′、３′、13′（第12図（ｃ））が生成される。点P
a、Pb及びPcがこの時点でマークされることに留意され
たい。

次に、三角形２′、13′、12′が生成され、EX−OR関数
がこの三角形をクリアする。三角形２′、12′、13′と
ポリゴンの残余部分との間のセグメント12′、13′上の
共通点（すなわち、点Pa、Pb、及びPc）が、EX−OP演算
の結果としてクリアされる（第12（ｄ）図）。ポリゴン
11、12′、13′、14が生成され、これは上記の説明に従
い、マークからの孔11、12′、13′、14をキャンセルす
る。しかしながら、点Pa、Pb、及びPc（クリアされた）
はこのプロセスによって間違ってマークされる（第12図
（ｅ））。それゆえ、セグメント12′、13′に対応した
マーク・バッファの点を特にクリアしなければならな
い。

略述したＺフェイク・エッジ処理と組み合わせた上述の
処理ステップ１−５の詳細な実施形態の１つを、第13図
−第17図の流れ図に示す。

第13図はステップ１の流れ図を示しており、このステッ
プの主たる目的はマーク・バッファ内のポリゴン・プリ
ミティブの境界をマークし、これを以降の処理のために
保存することである。この場合も、ポリゴン・プリミテ
ィブはいくつかの個別のサブエリアからなっていてもか
まわない。「開始」100に入った後、コントローラはポ
リゴンの最後のサブエリアがステップ１によって処理さ
れたかどうか、「最後のサブエリアが処理されたか」を
照会する。処理が終わっていない場合、コントローラは
命令104「最初の頂点データを得る」に進み、その後、
照会106「サブエリアの最後の頂点か」に進む。処理が
開始したばかりなので、答えは「ノー」であり、流れは
108「次の頂点データを得る」になる。処理対象のサブ
エリアの最後の頂点が存在していれば、コントローラに
は照会106から、照会102に戻るように命令か与えられ
る。

命令108により、コントローラは命令104で得られた最初
の頂点データと、命令108で得られた次の頂点データと
の間のベクトルが、サブエリアな「レギュラー・エッ
ジ」であるかどうかを判断する。上述のように、境界フ
ラグがデータ・リストの一部として与えられ、各頂点を
「リアル・エッジ」、「レギュラー・エッジ」または
「フェイクＺフロント・エッジまたはフェイクＺバック
・エッジ」にあるものとして定義する。「レギュラー・
エッジ」はポリゴン・プリミティブのすべての内部点ま
たはギャップ・ピクセルに対応する。「イエス」の場
合、コントローラはコマンド112「ベクトルを生成す
る」に進み、信号‘g'をレギュラー・エッジに沿ってマ
ーク・バッファに対してマークする。この場合も、カラ
ーは‘g'に対するステップ１におけるフレーム・バッフ
ァには送られない。

その後、コマンド112の流れは照会106に戻る。

照会110に対する答えが「ノー」である場合には、コン
トローラは照会114「エッジはリアル・エッジか」に進
み、ベクトルがポリゴン・プリミティブのリアル・エッ
ジを定義しているかどうか（すなわち、実線か飾り線
か）を判定する。「イエス」の場合には、コントローラ
はコマンド116「ベクトルを生成する」においてベクト
ルを生成し、上出のアルゴリズム及びカラーＲ、Ｇ、Ｂ
にしたがって、すなわち、エッジ・セグメントの場合に
は、フレーム・バッファにしたがって、マーク・バッフ
ァ内の該当する信号‘e'または‘g'をマークする。照会
114に対する答えが「ノー」である場合には、コントロ
ーラは照会118「エッジはＺフェイクか」に進む。この
場合も、「ノー」であれば、コントローラは照会106へ
戻る。

エッジがフェイクＺエッジからなっている場合には、照
会118によって、コントローラは照会120「フロントＺフ
ェイクか」に進み、フェイクＺエッジがフロントＺ軸ク
リッピング境界またはバックＺ軸クリッピング境界に沿
っているかどうかを判断する。エッジがバッグＺ軸クリ
ッピング境界に対応している場合には、流れは命令122
「エッジ頂点を、Ｚフェイク頂点リスト（バック）に保
管する」に進む。逆に、Ｚフェイク・エッジがフロント
・エッジからなっている場合には、コントローラはＺフ
ェイク・エッジ頂点を別のリスト124に記憶する。「エ
ッジ頂点を、Ｚフェイク頂点リスト（フロント）に保管
する」。命令122または124を処理した後、コントローラ
は照会106に戻る。

照会102に対する答えが「イエス」である場合には、コ
ントローラは照会126「Ｚフェイク・バック・エッジ
か」に進む。この命令はコントローラに、頂点が命令12
2で作成されたＺフェイク頂点リスト（バック）に記憶
されているかどうかを判断するよう命令する。「イエ
ス」の場合には、コントローラはＺフェイク・バック頂
点のリストを分類し、128「Ｚフェイク頂点リスト（バ
ック）を分類する」、分類されたリストからベクトルP1
−P2、P3−P4、・・・を生成する、130「ベクトルP1−P
2、P3−P4、・・・を生成する」。フェイクＺエッジに
内部カラーが割り当てられているので、マーク・バッフ
ァは生成されたベクトルに対する‘g'信号を受け取る
が、フレーム・バッファには何も書き込まれない。命令
130の後、あるいは照会126に対する答えが「ノー」であ
る場合、コントローラは照会132「Ｚフェイク・フロン
ト・エッジか」に送られる。「ノー」の場合、コントロ
ーラは本描出処理のステップ２に進む。

「イエス」の場合には、流れ命令184「Ｚフェイク頂点
リスト（フロント）」へ進み、その後命令136「ベクト
ルP1−P2、P3−P4、・・・を生成する」に進む。命令13
4及び136は、これらがコントローラにフロントＺ軸クリ
ッピング面に沿った非重畳フェイクＺエッジを分類生成
し、これらのエッジをマーク・バッファ内の信号‘g'に
よってマークするよう命令する点で、命令128及び130の
それぞれに対応している。この場合も、フレーム・バッ
ファへの描出は遅延する。命令136が完了すると、コン
トローラは処理対象のボリゴン・プリミティブに対する
ステップ１を完了し、ステップ２へ進む。

ステップ２の目的は、マーク・バッファ内のポリゴンの
内部をマークすることである。まず、コントローラに
は、最後のサブエリアが処理されたかどうか、138「最
後のサブエリアが処理されたか」を判断するよう命令が
与えられる。ステップ２の処理が始まったばかりなの
で、答えは「ノー」であり、コントローラはサブエリア
の最初の頂点データを獲得し、140「サブエリアの最初
の頂点データを得る」、その後サブエリアの最後の頂点
が処理されたかどうかを照会する、42「最後の頂点が処
理されたか」。「ノー」の場合、コントローラは獲得し
た頂点データがフェイクＺエッジの頂点に対応している
かどうかを照会する、「エッジはＺフェイクか」。「ノ
ー」の場合、コントローラはサブルーチンALPH1に入
る、146「ALPH1を呼び出す」。

第14B図に略示したALPH1はコントローラに、Ｚフェイク
・エッジのない三角形を生成するよう命令する。サブル
ーチンには170で入り、コントローラはまず、検討対象
の頂点が処理対象のサブエリアの第２の頂点からなって
いるかどうかを判定する、172「処理対象のサブエリア
の２番目の頂点か」。「ノー」の場合、コントローラは
２番目の頂点を獲得し、174「２番目の頂点データを得
る」、次いで照会142で、第14A図に示した処理に戻る、
186。サブエリアの２番目の頂点が獲得されている場
合、照会172によって、コントローラは３番目の頂点を
獲得し、176「次の頂点データを得る」、その後３つの
頂点を使用して三角形を生成する、178「三角形を生成
する」。三角形を生成した後、コントローラは生成され
た三角形が処理対象のサブエリアの最初の三角形である
かどうかを判定し、「イエス」の場合には、第14A図の
メインステップ２の処理に戻る、186。反対に、コマン
ド178で作成された三角形がサブエリアの最初のもので
ない場合には、コントローラは以前の三角形の向きが、
現在の三角形の向きと同じであうかどうかを判定する、
182「以前の三角形と同じ向きか」。「ノー」の場合、
流れはステップ２のメイン・プロセスに戻る、186。
「イエス」の場合には、コントローラは現在の三角形及
び以前の三角形のすべての共通の点を修正するが、以前
の三角形は第８図に関連して詳述した処理アルゴリズム
に固有な排他的論理和関数によって消去されたものであ
る。命令184の後、照会142においてステップ２のメイン
処理への復帰が行なわれる、186。

照会144に戻ると、答えが「イエス」の場合、コントロ
ーラは頂点がＺフェイク・フロント・エッジまたはＺフ
ェイク・バック・エッジに対応しているかどうか判定す
る、148「Ｚフェイク・エッジのタイプは」。エッジが
Ｚフェイク・バック・エッジである場合には、サブレー
チンALPH2Bが呼び出される、150「ALPH2Bを呼び出
す」。あるいは、エッジがＺフェイク・フロント・エッ
ジである場合にはサブルーチンALPH2Fが呼び出される、
152「ALPH2Fを呼び出す」。サブルーチンALPH2B及びALP
H2Fは、これらがステップ１のコマンド122及び124でコ
ンパイルされた異なるリストにアクセスすることを除け
ば、同じものである。ALPH2BはＺフェイク頂点リスト
（バック）に保管されているエッジ頂点にアクセスし、
ALPH2FはＺフェイク頂点リスト（フロント）に保管され
ているエッジ頂点にアクセスする。ALPH2B/ALPH2Fサブ
ルーチンの概要を、14C図に示す。

188でサブルーチンに入ってから、コントローラは重畳
Ｚフェイク・エッジが存在しているかどうかを確認す
る、190「重畳Ｚフェイク・エッジか」。「ノー」の場
合、コントローラはサブエリアの最後のエッジが処理さ
れたかどうかを照会する、192「サブエリアの最後のエ
ッジか」。再度「ノー」の場合には、サブルーチンALPH
1が入力される、194「ALPH1を呼び出す」。ALPH1サブル
ーチンの処理後、照会142において、ステップ２のメイ
ン処理フローへの復帰が行なわれる、196。プロセッサ
には同様に、照会192に対する答えが「イエス」の場合
に、照会142に戻るよう命令が与えられる、196。

重畳Ｚフェイク・エッジが存在している場合には、コン
トローラは重畳Ｚフェイク・エッジが処理すべき最後の
エッジであるかどうかを判断する、198「サブエリアの
最後のエッジか」。「ノー」の場合、次の頂点データが
獲得され、200「次の頂点データを得る」、その後コン
トローラは命令202へ進む。命令202において、コントロ
ーラは上述のＺフェイク処理を実施する。詳細にいえ
ば、他の対応するＺフェイク・エッジのＮ個の頂点が、
現在のエッジ頂点の間に挿入され、結果として生じるＮ
＋１個の三角形が生成され、Ｚフェイク・エッジに沿っ
たあらゆる共通点に対して修正が行なわれる、202「他
のＺフェイク・エッジの頂点（Ｎ個）を、現在のエッジ
頂点の間に挿入し、Ｎ＋１個の三角形を生成し、共通点
の修正を行なう」。重畳Ｚフェイク・エッジがサブエリ
アの最後のエッジに沿って整合している場合には、照会
198によって、コントローラは次の頂点データを獲得
し、206「次の頂点データを得る」、その後命令208「他
のＺフェイク・エッジの頂点（Ｎ個）を、現在のエッジ
頂点の間に挿入し、Ｎ個の三角形を生成し、共通点の修
正を行なう」。命令208は命令202と同様であるが、Ｚフ
ェイク重畳エッジが、処理すべきサブエリアの最後のエ
ッジでない場合に、Ｎ個の三角形のみが生成される点が
異なっている。命令202または208の後、コントローラは
ステップ２のメイン処理ループへ戻る、196。

最後の頂点が処理されると、コントローラは照会142か
ら照会154「エッジはＺフェイクか」に進む。最後の頂
点がフェイクＺエッジに沿っていない場合には、コント
ローラは照会138に戻る。照会154に対する答えが「イエ
ス」の場合には、コントローラは処理対象のＺフェイク
・エッジのタイプを判断する、156「Ｚフェイク・エッ
ジのタイプは」。Ｚフェイク・エッジがバックＺ軸クリ
ッピング面に沿っている場合には、コントローラはサブ
ルーチンALPH2Bを呼び出す、158「ALPH2Bを呼び出
す」。それ以外の場合には、コントローラはサブルーチ
ンALPH2Fを呼び出す、160「ALPH2Fを呼び出す」。命令1
58または命令160の処理後、コトローラは照会138に戻
る。

照会138に戻ると、答えが「イエス」の場合、コントロ
ーラはサブエリアが、バックＺ軸クリッピング面に沿っ
たフェイクＺエッジを含んでいるかどうかを判断する、
162「Ｚフェイク・バック・エッジか」。答えが「イエ
ス」の場合、コントローラはベクトルを生成し、Ｚフェ
イク・バック・エッジに沿ったマークをクリアする、16
4「ベクトルP1−P2、P3−P4、・・．を生成する」命令1
64の後、コントローラは進行し、何らかのＺフェイク・
フロント・エッジが存在しているかどうかを判断する、
166「Ｚフェイク・フロント・エッジか」。照会162に対
する答えが「ノー」の場合、流れは照会166に進む。フ
ロントＺフェイク・エッジが存在するものと想定する
と、コントラーラはベクトルを生成し、フロントＺフェ
イク・エッジのマークをクリアする、168「ベクトルP1
−P2、P3−P4、・・・を生成する」。命令168の後、あ
るいは照会166に対する答えが「ノー」の場合には、コ
ントローラは処理アルゴリズムのステップ３に送られ
る。

メイン・ステップ３の処理の１実施例を、第15A図に示
す。このステップの目的は、ポリゴンの内部をフレーム
・バッファに描くことである。ステップ２から、コント
ローラはまず、最後のサブエリアが処理されたかどうか
を判断する、210「最後のサブエリアが処理された
か」。イエスであれば、コントローラはステップ４に送
られる。反対に、照会210に対する答えが「ノー」の場
合、コントローラはサブエリアの最初の頂点データを獲
得し、212「サブエリアの最初の頂点データを得る」、
サブエリアの最後の頂点が処理されているかどうかを照
会する、216「最後の頂点が処理されたか」。「ノー」
の場合、獲得された頂点データにＺフェイク・エッジと
フラグが付けられたかどうか照会される、218「エッジ
はＺフェイクか」。「ノー」の場合、コントローラはサ
ブルーチンBETA1に入る、220「BETA1を呼び出す」。

第15B図に示すようにBETA1はコントローラに、Ｚフェイ
ク・エッジのない三角形を生成するよう命令する。236
で、サブルーチンに入り、コントローラはまず、検討対
象の頂点が処理対象のサブエリアの２番目の頂点を含ん
でいるかどうかを判断する、238「処理対象のサブエリ
アの２番目の頂点か」。「ノー」の場合、コントローラ
は２番目の頂点を獲得し、240「２番目の頂点データを
得る」、照会216で第15A図の処理ルーチンに戻る、24
6。

サブエリアの２番目の頂点が獲得されている場合には、
照会238により、コントローラは３番目の頂点データを
獲得し、242「次の頂点データを得る」、３つの頂点を
使用して、三角形を生成する、244「三角形を生成す
る」。三角形の生成後、照会216で、第15A図のメイン・
ルーチン処理に戻る、246。

照会218に戻ると、答えが「イエス」の場合、コントロ
ーラは頂点が、Ｚフェイク・フロント・エッジまたはＺ
フェイク・バック・エッジに対応しているかどうかを判
断する、222「Ｚフェイク・エッジのタイプは」。エッ
ジがＺフェイク・バック・エッジの場合には、コントロ
ーラはサブルーチンBETA2Bを呼び出す、224「BETA2Bを
呼び出す」。反対に、エッジがＺフェイク・フロント・
エッジを含んでいる場合には、サブルーチンBETA2Fが呼
び出される、226「BETA2Fを呼び出す」。サブルーチンB
ETA2B及びBETA2Fはこれらがステップ１のコマンド122及
び124でコンパイルされた異なる２つのリストをアクセ
スすることを除けば、同一のものである。BETA2BはＺフ
ェイク頂点リスト（バック）で保管されているエッジ頂
点にアクセスし、BETA2FはＺフェイク頂点リスト（フロ
ント）で保管されているエッジ頂点にアクセスする。BE
TA2B/BETA2Fサブルーチンの概要を第15C図に示す。

248でサブルーチンに入った後、コントローラは重畳Ｚ
フェイク・エッジが存在しているかどうかを確認する、
250「重畳したＺフェイク・エッジか」。「ノー」の場
合、コントローラはサブエリアの最後のエッジが処理さ
れているかどうかを照会し、252「サブエリアの最後の
エッジか」、再度「ノー」であれば、サブルーチンBETA
1に入る、254「BETA1を呼び出す」。BETA1サブルーチン
の処理の後、コントローラは照会216で、ステップ３の
メイン処理フローに戻る、256。照会252に対する答えが
「イエス」の場合には、プロセッサは同様に照会216に
戻る、256。

重畳Ｚフェイク・エッジが存在している場合には、コン
トローラはＺフェイク・エッジが、処理すべき最後のエ
ッジであるかどうかを判断する、258「サブエリアの最
後のエッジか」。「ノー」の場合、次の頂点データが獲
得され、260「次の頂点データを得る」、コントローラ
は命令262「他のＺフェイク・エッジの頂点（Ｎ個）
を、現在のエッジ頂点の間に挿入し、Ｎ＋１個の三角形
を生成する」へ進む。重畳Ｚフェイク・エッジがサブエ
リアの最後のエッジと整合している場合には、照会258
により、コントローラは次の頂点データを獲得し、264
「次の頂点データを得る」、その後命令266「他のＺフ
ェイク・エッジの頂点（Ｎ個）を、現在のエッジ頂点の
間に挿入し、Ｎ個の三角形を生成する」へ進む。命令26
2及び266は共通点を修正する必要がないことを除けば、
命令202及び208のそれぞれと同一である。命令262また
は266の後、コントローラはステップ３のメイン処理ル
ープへ戻る、256。

照会216に対する答えが「イエス」の場合には、コント
ローラは頂点が、Ｚフェイク・エッジに対応しているか
どうかを判断し、228「エッジはＺフェイクか」、再度
「イエス」の場合、Ｚフェイク・エッジのタイプを識別
する、23「Ｚフェイク・エッジのタイプは」。Ｚフェイ
ク・エッジがＺ軸クリッピング面に沿っている場合に
は、サブルーチンBETA2Bが呼び出される、232「BETA2B
を呼び出す」。それ以外の場合には、サブルーチンBETA
2Fが呼び出される、234「BETA2Fを呼び出す」。サブル
ーチンBETA2BまたはBETA2Fの処理の後、コントローラは
照会210に戻る。また、頂点がＺフェイク・エッジに沿
っていない場合には、コントローラは照会228から照会2
10へ直接戻る。

ステップ３から、コントローラはステップ４でスタイル
化されたポリゴン境界のギャップ・ポイントを描くよう
に命令される。ステップ４の処理の１実施例を第16図に
示す。図示のように、コントローラはまず、最後のサブ
エリアが処理されているかどうかを判断する、270「最
後のサブエリアを処理したか」。「ノー」の場合、最初
の頂点が獲得され、272「最初の頂点データを得る」、
その後獲得された頂点データがサブエリアの最後で頂点
に対応しているのかどうかの照会が行なわれる、274
「サブエリアの最後の頂点か」。「イエス」の場合、コ
ントローラは照会270へ戻る。反対に、サブエリアの最
後の頂点が処理されていない場合には、コントローラは
次の頂点を獲得し、275「次の頂点データを得る」、２
つの頂点によって定義されたエッジが「レギュラー・エ
ッジ」なのかどうかを照会する、276「エッジはレギュ
ラー・エッジか」。「イエス」の場合、上述のアルゴリ
ズムにしたがって、エッジのすべてのピクセルに内部カ
ラーが割り当てられる、278「ベクトルを生成する」。
照会276に対する答えが「ノー」の場合、コントローラ
はエッジが「リアル・エッジ」であるかどうかを判断
し、280「エッジは「リアル・エッジ」か」、「イエ
ス」の場合には、エッジがスタイル化されているかどう
かを判断する、282「エッジはスタイル化された線
か」。「イエス」の場合には、ベクトルが生成され、27
8「ベクトルを生成する」、アルゴリズムにしたがって
ギャップ・ピクセルが描かれる。エッジがスタイル化さ
れた線でない場合には、エッジがすでにステップ１で描
かれているので、ベクトルは生成されない。

会280または282に対する答えが「ノー」の場合、コント
ローラは照会274に戻り、さらに処理される。同様に、
ベクトル生成コマンド278によって、プロセッサは274に
戻る。

最後のサブエリアが処理されると、照会270によって、
コントローラはＺフェイク・バック・エッジがあるかど
うかを判断する、284「Ｚフェイク・バック・エッジ
か」。「イエス」の場合、ベクトルP1−P2、P3−P4、・
・・が生成されるので、内部カラーをこれに割り当てる
ことができる、286「ベクトルP1−P2、P3−P4、・・．
を生成する」。命令286の後、あるいは照会284に対する
答えが「ノー」の場合、コントローラは進行し、何らか
のＺフェイク・フロント・エッジがあるかどうかを判断
する、288「Ｚフェイク・エッジか」。「イエス」の場
合、対応するベクトルP1−P2、P3−P4、・・・が生成さ
れる、290「ベクトルP1−P2、P3−P4、・・・を生成す
る」。命令290の後、コントローラはステップ５へ送ら
れる。同様に、ポリゴン・プリミティブに対してＺフェ
イク・フロント・エッジが存在しない場合には、コント
ローラはステップ５へ送られる。

ステップ５の目的は最後のサブエリアの処理に引き続
き、マーク・バッファに残っているあらゆるエッジを消
去することである。ステップ５の概要を第17図に示す。
図示のように、コントローラはまず、最後のサブエリア
が処理されているかどうかを判断する、292「最後のサ
ブエリアが処理されたか」。「ノー」の場合、最初の頂
点が獲得される、294「最初の頂点を得る」。次いで、
コントローラはサブエリアの最後の頂点が処理されてい
るかどうかを判断し、296「サブエリアの最後の頂点
か」、「イエス」の場合には、照会292に戻る。最後の
頂点が処理されていない場合には、コントローラは次の
頂点データを獲得し、298「次の頂点データを得る」、
２つの頂点によって定義されたエッジがレギュラー・エ
ッジであるかどうかを判断する、300「エッジはレギュ
ラー・エッジか」。「イエス」の場合には、ベクトルが
生成され、エッジを消去する、302「ベクトルを生成す
る」。エッジがレギュラー・エッジでない場合には、コ
ントローラはエッジが「リアル・エッジ」であるかどう
かを判断し、804「エッジは「リアル・エッジ」か」、
再度「イエス」の場合には、ベクトルを生成して、エッ
ジを消去する、302「ベクトルを生成する」。命令302の
後、コントローラは照会296に戻る。照会304に対する答
えが「ノー」の場合には、コントローラは直接296に戻
る。

最後のサブエリアが処理された後、コントローラはＺフ
ェイク・バック・エッジがあるかどうかを判断し、306
「Ｚフェイク・バック・エッジか」、「イエス」の場合
には、ベクトルを生成して、エッジを消去する、308
「ベクトルP1−P2、P3−P4、・・・を生成する」。命令
308から、あるいは答えが「ノー」の場合には、直接命
令306から、コントローラはＺフェイク・フロント・エ
ッジがあるかどうかを判断し、306「Ｚフェイク・フロ
ント・エッジか」、「イエス」の場合には、ベクトルを
生成し、エッジを消去する、312「ベクトルP1−P2、P3
−P4、・・・を生成する」。バック及びフロントＺフェ
イク・エッジを消去した後、ステップ５の処理は終了す
る、314。

上記したところから、本発明が本明細書に記載した目的
を完全に満たしていることがわかろう。セルフ・インタ
ーセクティング・ポリゴン及び多角形孔を有するポリゴ
ンを含む凹ポリゴンを効率的に処理する、コンピュータ
・グラフィックス・ディスプレイ・システム用の方法及
びプロセッサが提供される。また、上述の方法及びプロ
セッサは、典型的なコンピュータ・グラフィックス・デ
ィスプレイ・システムのさまざまな既存のハードウェア
構成要素を使用して実現される。

E.発明の効果 本発明により、周知の手法に比較して、凹ポリゴン処理
時間が大幅に短縮される。さらに、実施例の説明から明
らかなように、本発明は既存のディスプレイ・システム
・ハードウェアの多くの要素、たとえば、凸ポリゴンを
処理するのに必要な要素を使用して実現される。

【図面の簡単な説明】

第１図は、本発明を組み込んだコンピュータ・グラフィ
ックス・システムの全体ブロック図である。 第２図は、本発明のディスプレイ・プロセッサの１実施
例のプロック図である。 第３図は、本発明にしたがって処理される凹ポリゴンの
図である。 第4A図ないし第4C図は、３つの三角形に分割された第３
図の凹ポリゴンと、三角形のそれぞれの向きを示す図で
ある。 第5A図ないし第5C図は、隣接する三角形を処理するため
の本発明の総和方法の図である。 第６図は、本発明のディスプレイ・プロセッサの他の実
施例のブロック図である。 第７図は、第６図に示したマーク及びデプス・バッファ
のブロック図である。 第８図は、第６図に示したＸ−Ｙジェネレータのオン・
ジオメトリック・ライン・サブモード処理を実現する論
理回路のブロック図である。 第９図は、本発明にしたがって処理される多角形孔を有
するポリゴンの図である。 第10図は、第９図の多角形孔を有するポリゴンをＺ軸ク
リッピングしたことによって生じる新しいポリゴンの図
である。 第11図は、説明のために誇張した、Ｚフェイク・エッジ
の位置誤差のある第10図のクリップされたポリゴンの図
である。 第12A図ないし第12E図は、本発明のＺフェイク・エッジ
処理手法による各種の段階における、第11図の誇張され
たクリップされたポリゴンの図である。 第13図は、本発明の第１の処理ステップの流れ図であ
る。 第14A図ないし第14C図は、本発明の第３の処理ステップ
の流れ図である。 第15A図ないし15C図は、本発明の第３の処理ステップの
流れ図である。 第16図は、本発明の第４のステップの流れ図である。 第17図は、本発明の第５の処理ステップの流れ図であ
る。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ウイリアム・ルイス・ルーケン、ジユニア アメリカ合衆国ニユーヨーク州アルスタ ー・パーク、オチヤード・ヒル・ロード２ 番地

Claims (20)

【特許請求の範囲】
1. 【請求項１】ディスプレイ・プロセッサと、ディスプレ
   イモニタに表示される複数の線の各々についての個々の
   ピクセルを記憶するためのフレーム・バッフアを含むデ
   ィスプレイ手段とを有しており、該フレーム・バッファ
   が複数個のアドレス可能なＭ×Ｎの構成ピクセル・ブロ
   ックに編成されているコンピュータ・グラフィックス・
   ディスプレイ・システムにおける、複数個のアドレス可
   能なＭ×Ｎの構成ピクセルに編成されたマーク・バッフ
   ァを使用して、前記フレーム・バッファに凹ポリゴンを
   描く方法であって、 （ａ）前記ポリゴンの境界に対応する前記マーク・バッ
   ファ内のピクセルをマークし、前記ポリゴンの境界に対
   応するピクセルを前記フレーム・バッファに描くステッ
   プと、 （ｂ）前記ポリゴン境界に対応するマークされたピクセ
   ルが前記マーク・バッファに保存されている間に、前記
   ポリゴンの内側に対応する前記マーク・バツファ内のピ
   クセルをマークするステップと、 （ｃ）前記マーク・バッファ内のマークされたポリゴン
   内部ピクセルを参照して、前記ポリゴンの内側に対応す
   る前記フレーム・バッファ内のピクセルに記入するステ
   ップと、 からなる凹ポリゴンを描く方法。
2. 【請求項２】前記ポリゴンが複数の多角形サブェリアに
   よって定義され、前記ステップ（ａ）−（ｃ）の各々が
   前記サブェリアのすべてを処理する、請求項１記載の方
   法。
3. 【請求項３】ディスプレイ・プロセッサと、ディスプレ
   イ・モニタに表示される複数の線の各々についての個々
   のピクセルを記憶するためのフレーム・バッファ及び個
   々のピクセルについてのＺ値を記憶するためのデプス・
   バッファを含むディスプレイ手段とを有しており、該フ
   レーム・バッファ及び該デプス・バッファの各々が複数
   個のアドレス可能なＭ×Ｎの構成ピクセル・ブロックで
   構成されているコンピュータ・グラフィックス・ディス
   プレイ・システムにおける、複数個のアドレス可能なＭ
   ×Ｎの構成ピクセルで構成されたマーク・バッファを使
   用して、エッジ・ギャップ及びエッジ・セグメントによ
   って定義されるスタイル化された境界のある、あるいは
   該境界のない凹ポリゴンを描く方法であって、 （ａ）前記ポリゴンの境界を定義するエッジ・ギャップ
   及びエッジ・セグメントに対応する前記マーク・バッフ
   ァ内のピクセルをマークするステップと、 （ｂ）前記マーク・バッファの内容を参照して、ポリゴ
   ンの境界を定義するエッジ・ギャップ及びエッジ・セグ
   メントに対応する前記デプス・バッファ内のピクセルに
   Ｚ値を記憶するステップと、 （ｃ）前記マーク・バッファの内容を参照して、前記ポ
   リゴンの境界のエッジ・セグメントに対応するものにつ
   いて前記フレーム・バッファ内のピクセルに記入するス
   テップと、 （ｄ）前記ポリゴンの境界のエッジ・ギャップ及びエッ
   ジ・セグメントに対応する前記マーク・バッファにマー
   クされたピクセルが保存されている間に、前記ポリゴン
   の内側に対応する前記マーク・バッファ内のピクセルを
   マークするステップと、 （ｅ）前記マーク・バッファの内容を参照して、前記ポ
   リゴンの内側の点に対応するピクセルについて前記デプ
   ス・バッファにＺ値を記憶し、これと同時に前記フレー
   ム・バッファのピクセルに記入するステップと、 （ｆ）前記マーク・バッファの内容を参照して、前記ポ
   リゴンの境界のエッジ・ギャップに対応するものについ
   て前記フレーム・バッファのピクセルに記入するステッ
   プと、 からなり、前記ステップ（ａ）−（ｃ）が実質的に同時
   に行なわれる凹ポリゴンを描く方法
4. 【請求項４】各々が３辺のエッジによって内側が囲まれ
   た三角形であって、隣接する三角形が共通の重複するエ
   ッジを有する三角形のセットに前記ポリゴンを分割する
   ステップであって、前記各三角形は共通の第１頂点、個
   々の第２頂点及び第３頂点を有し、該第１及び第２頂点
   を結ぶ第１ベクトルと該第１及び第３頂点を結ぶ第２ベ
   クトルとの積の符号によって決まる正の向きまたは負の
   向きを有する如き三角形に分割するステップと、 前記ポリゴンの内側に対応するピクセルをマークするス
   テップが、 前記三角形の各々の向きを判断し、 同一の向きの隣接する三角形の内部ピクセルはマークさ
   れるが、異なる向きの隣接する三角形の内部ピクセルは
   三角形の重畳領域内でマークされないように三角形の各
   々の内側に対応する前記マーク・バッファ内のピクセル
   を処理することを含んでいる、 請求項１または３記載の方法。
5. 【請求項５】前記フレーム・バッファに前記凹ポリゴン
   を描いた後、前記マーク・バッファをクリアするステッ
   プをさらに包含している、請求項１または３記載の方
   法。
6. 【請求項６】ディスプレイ・モニタに表示される複数の
   線の各々に対する個々のピクセルを記憶するためのフレ
   ーム・バッファを含むディスプレィ手段とを有してお
   り、該フレーム・バッファが複数個のアドレス可能なＭ
   ×Ｎの構成ピクセル・ブロックで構成されている、コン
   ピュータ・グラフィックス・ディスプレイ・システム用
   のディスプレイ・プロセッサであって、前記フレーム・
   バッファに凹ポリゴンを描くことのできるディスプレイ
   ・プロセッサにおいて、 コントローラと、 該コントローラから信号を受け取るように接続されたエ
   ッジ／トライアングル生成手段と、 該生成手段から信号を受け取るように接続された第１組
   合せ論理手段と、 複数個のＭ×Ｎの構成ピクセルで構成されたマーク・バ
   ッファであって、該マーク・バッファが前記第１組合せ
   論理手段からのピクセル値及び前記生成手段からのアド
   レス信号を受け取るように接続されており、前記第１組
   合せ論理手段からの前記ピクセル値及び前記生成手段か
   らの前記アドレス信号が、第１パスの間に前記ポリゴン
   の境界をマークするために使用され、その後の１または
   複数パスの間に前記ポリゴンの前記境界のマークが前記
   マーク・バッファに保存されている間に前記マーク・バ
   ッファ内の前記ポリゴンの内側をマースするために使用
   されるマーク・バッファと、 前記生成手段からのアドレス信号及び前記マーク・バッ
   ファからのピクセル値を受け取るように接続された第２
   組合せ論理手段であって、該第２組合せ論理手段が前記
   フレーム・バッファに対して、処理される各Ｘ、Ｙアド
   レスに対するエッジ信号及び塗りつぶし信号の一方を出
   力し、前記エッジ信号が前記ポリゴンの境界ピクセルに
   対応しており、前記塗りつぶし信号が前記ポリゴンの内
   部ピクセルに対応している如き第２組合わせ論理手段
   と、 から成るディスプレイ・プロセッサ。
7. 【請求項７】前記生成手段が、 各々が３辺のエッジによって内側が囲まれた三角形であ
   って、隣接する三角形が共通の重複するエッジを有する
   三角形のセットに前記ポリゴンを分割する手段であっ
   て、前記各三角形は共通の第１頂点、個々の第２頂点及
   び第３頂点を有し、該第１及び第２頂点を結ぶ第１ベク
   トルと該第１及び第３頂点を結ぶ第２ベクトルとの積の
   符号によって決まる正の向きまたは負の向きを有する如
   き手段と、 前記三角形の各々の向きを判断する手段と、 を含み、 前記第１組合わせ論理手段が、 同一の向きの隣接する三角形の内部ピクセルはマークさ
   れるが、異なる向きの隣接する三角形の内部ピクセルは
   三角形の重畳領域内でマークされないように三角形の各
   々の内側に対応する前記マーク・バッファ内のピクセル
   を処理する手段を含んでいる、 請求項６記載のディスプレイ・プロセッサ。
8. 【請求項８】前記三角形の内側に対応する前記マーク・
   バッファ内のピクセルを処理するための手段が、下記の
   表を実現する、請求項７記載のディスプレイ・プロセッ
   サ。 0RIENT MB_O LD MB_NEW ‘＋’ ‘＋’ ‘＋’ ‘＋’ ‘−’ ‘0' ‘＋’ ‘0' ‘＋’ ‘＋’ ‘e' ‘e' ‘−’ ‘＋’ ‘0' ‘−’ ‘−’ ‘−’ ‘−’ ‘0' ‘−’ ‘−’ ‘e' ‘e' ただし、 ‘＋’＝反時計方向の三角形の向きの塗りつぶしピクセ
   ル ‘−’＝時計方向の三角形の塗りつぶしピクセル ‘0'＝クリアされたピクセル ‘e'＝エッジ・ピクセル MB_0LD＝Ｘ、Ｙアドレスにおける古いマーク・バッファ
   値 MB_NEW＝Ｘ、Ｙアドレスにおける新しいマーク・バッフ
   ァ値
9. 【請求項９】前記第２組合せ論理手段が、有効なＸ、Ｙ
   アドレス信号を前記生成手段から受け取り、かつ該Ｘ、
   Ｙアドレスにおける前記マーク・バッファの内容が，
   ＋’または‘−’である場合に、前記塗りつぶし信号を
   発生し、また有効なＸ、Ｙアドレス信号を前記生成手段
   から受け取り、かつ該Ｘ、Ｙアドレスにおける前記マー
   ク・バッファの内容が‘e'である場合に、前記エッジ信
   号を発生する、請求項８記載のディスプレイ・プロセッ
   サ。
10. 【請求項１０】前記エッジ／トライアングル生成手段が
    ポリゴンのエッジ上のすべての点のアドレス・シーケン
    スを生成する手段を含んでおり、前記第１組合せ論理手
    段が有効なＸ、Ｙエッジ・アドレスに対応するマーク・
    バッファ内の位置に、エッジ‘e'を書き込み、該アドレ
    スを前記生成手段から受け取る、請求項６記載のディス
    プレイ・プロセッサ。
11. 【請求項１１】ディスプレイ・モニタに表示される複数
    の線の各々に対する個々のピクセルを記憶するためのフ
    レーム・バッファを含むディスプレイ手段を有してお
    り、該フレーム・バッファが複数個のアドレス可能なＭ
    ×Ｎの構成ピクセル・ブロックで構成されている、コン
    ピュータ・グラフィックス・ディスプレイ・システム用
    のディスプレイ・プロセッサであって、前記フレーム・
    バッファに凹ポリゴンを描くことのできるディスプレイ
    ・プロセッサにおいて、 コントローラと、 Ｘ−Ｙジェネレータと、 前記コントローラ及び前記Ｘ−Ｙジェネレータから信号
    を受け取り、各Ｘ、Ｙアドレスに対するＺの補間された
    値及び輝度を出力するように構成された補間手段と、 各々のピクセルの深さが２ビットである複数個のアドレ
    ス可能なＭ×Ｎのピクセルを有するマーク・バッファ、
    ならびに複数個のアドレス可能なＭ×Ｎの構成ピクセル
    ・プロックで構成されたデプス・バッファを含むマーク
    ・バッファ及びデプス・バッファ手段からなり、該バッ
    ファ手段が前記ポリゴンの境界及び内側に対応する各
    Ｘ、Ｙアドレスに対するＺの補間された値を、フレーム
    ・バッファに出力し、 前記マーク・バッファ及びデプス・バッファ手段が前記
    マーク・バッファ内の前記ポリゴンの正確なマークを生
    成するための組合せ論理手段を含んでおり、前記マーク
    が、前記フレーム・バッファへの前記輝度値の描出、な
    らびに各Ｘ、Ｙアドレスに対するＺの補間された値の前
    記デプス・バッファ内への記憶を制御するために使用さ
    れる、 ディスプレイ・プロセッサ。
12. 【請求項１２】前記Ｘ−Ｙジェネレータと前記マーク・
    バッファ及びデプス・バッファ手段の間に配置されたラ
    イン・スタイル・ジェネレータをさらに含んでおり、該
    ライン・スタイル・ジェネレータが前記マーク・バッフ
    ァ及びデプス・バッファ手段に対して、スタイル化され
    たポリゴン境界を表すエッジ・ギャップ・ピクセル及び
    エッジ・セグメント・ピクセルを定義する、請求項11記
    載のディスプレイ・プロセッサ。
13. 【請求項１３】ディスプレイ・プロセッサと、ディスプ
    レイモニタに表示される複数の線の各々についての個々
    のピクセルを記憶するためのフレーム・バッフアを含む
    ディスプレイ手段とを有しており、該フレーム・バッフ
    ァが複数個のアドレス可能なＭ×Ｎの構成ピクセル・ブ
    ロックに編成されているコンピュータ・グラフィックス
    ・ディスプレイ・システムにおける、複数個のアドレス
    可能なＭ×Ｎの構成ピクセルに編成されたマーク・バッ
    ファを使用して前記フレーム・バッファに凹ポリゴンを
    描く方法であって、 （ａ）前記ポリゴンの境界に対応する前記マーク・バッ
    ファ内のピクセルをマークし、前記ポリゴンの境界に対
    応するピクセルを前記フレーム・バッファに描くステッ
    プと、 （ｂ）前記ポリゴンを三角形のセットに分割するステッ
    プと、 （ｃ）前記ポリゴン境界に対応するマークされたピクセ
    ルが前記マーク・バッファに保存されている間に、前記
    ポリゴンの内側に対応する前記マークバツファ内のピク
    セルをマークするステップと、 （ｄ）前記マーク・バッファ内のマークされた内部ピク
    セルを参照して、前記各三角形の内側に対応する前記フ
    レーム・バッファのピクセルに記入するステップと、 を含む凹ポリゴンを描く方法
14. 【請求項１４】前記凹ポリゴンが多角形の孔を有するポ
    リゴンからなっており、 前記方法が、各々が同一のボリゴンの頂点から始まる頂
    点のセットによって多角形孔定義三角形の各々が表され
    る一連の三角形に多角形孔を分割することをさらに含ん
    でおり、 前記内部ビクセルをマークするステップ（ｃ）が、 ポリゴン三角形及び多角形孔定義三角形の重畳するピク
    セルがマークされないように前記凹ポリゴン定義三角形
    及び前記多角形孔定義三角形の各々の内側に対応する前
    記マーク・バッファ中のピクセルを処理することを含ん
    でいる、 請求項13記載の方法。
15. 【請求項１５】前記三角形の各々が三角形のエッジによ
    って内側が囲まれ、かつ順番の頂点のセットによって表
    される三角形であって、隣接する三角形が共通のエッジ
    に沿った重複領域を有し、前記各三角形は共通の第１頂
    点、個々の第２頂点及び第３頂点を有し、該第１及び第
    ２頂点を結ぶ第１ベクトルと該第１及び第３頂点を結ぶ
    第２ベクトルとの積の符号によって決まる正の向きまた
    は負の向きを有し、 前記内部ピクセルをマークするステップ（ｃ）が、 前記三角形の各々の向きを判断し、 同一の向きの隣接する三角形の内部ピクセルはマークさ
    れるが、異なる向きの隣接する三角形の内部ピクセルは
    三角形の重畳領域内でマークされないように三角形の各
    々の内側に対応する前記マーク・バッファ内のピクセル
    を処理することを含んでいる、 請求項13記載の方法。
16. 【請求項１６】ディスプレイ・プロセッサと、ディスプ
    レイモニタに表示される複数の線の各々についての個々
    のピクセルを記憶するためのフレーム・バッフアを含む
    ディスプレイ手段とを有しており、該フレーム・バッフ
    ァが複数個のアドレス可能なＭ×Ｎの構成ピクセル・ブ
    ロックに編成されているコンピュータ・グラフィックス
    ・ディスプレイ・システムにおける、複数個のアドレス
    可能なＭ×Ｎの構成ピクセルに編成されたマーク・バッ
    ファを使用して前記フレーム・バッファに凹ポリゴンを
    描く方法であって、 （ａ）前記ポリゴンの境界に対応する前記マーク・バッ
    ファ内のピクセルをマークし、前記ポリゴンの境界に対
    応する前記デプス・バッファ中のピクセルのＺ値を記憶
    させ、前記ポリゴンの境界に対応するピクセルを前記フ
    レーム・バッファに描くステップと、 （ｂ）前記ポリゴン境界に対応するマークされたピクセ
    ルが前記マーク・バッファに保存されている間に、前記
    ポリゴンの内側に対応する前記マークバッファ内のピク
    セルをマークするステップと、 （ｃ）前記マーク・バッファ内のマークされたポリゴン
    内部ピクセルを参照して、前記ポリゴンの内側に対応す
    る前記フレーム・バッファのピクセルに記入するステッ
    プと、 からなる凹ポリゴンを描く方法。
17. 【請求項１７】前記三角形の各々が三角形のエッジによ
    って内側が囲まれ、かつ順番の頂点のセットによって表
    される三角形であって、隣接する三角形が共通のエッジ
    に沿った重複領域を有し、前記各三角形は共通の第１頂
    点、個々の第２頂点及び第３頂点を有し、該第１及び第
    ２頂点を結ぶ第１ベクトルと該第１及び第３頂点を結ぶ
    第２ベクトルとの積の符号によって決まる正の向きまた
    は負の向きを有し、 前記内部ピクセルをマークするステップ（ｃ）が、 前記三角形の各々の向きを判断し、 同一の向きの隣接する三角形の内部ピクセルはマークさ
    れるが、異なる向きの隣接する三角形の内部ピクセルは
    三角形の重畳領域内でマークされないように三角形の各
    々の内側に対応する前記マーク・バッファ内のピクセル
    を処理することを含んでいる、 請求項16記載の方法。
18. 【請求項１８】フレーム・バッファにおける内部ビクセ
    ル描出及びデプス・バッファにおける前記Ｚ値記憶がほ
    ぼ同時に行なわれる、請求項16記載の方法。
19. 【請求項１９】ディスプレイ・プロセッサと、ディスプ
    レイモニタに表示される複数の線の各々についての個々
    のピクセルを記憶するためのフレーム・バッフアを含む
    ディスプレイ手段とを有しており、該フレーム・バッフ
    ァが複数個のアドレス可能なＭ×Ｎの構成ピクセル・ブ
    ロックに編成されているコンピュータ・グラフィックス
    ・ディスプレイ・システムにおいて前記フレーム・バッ
    ファに凹ポリゴンを描く方法であって、 前記ポリゴがフロントまたはバックＺ軸クリップ面に対
    してポリゴンをクリップすることにより生じるＺフェイ
    ク・バック・エッジまたはＺフェイク・フロント・エッ
    ジ内の少なくとも１つのサブエリアを有するクリップさ
    れたボリゴンからなっており、 （ａ）前記ポリゴンの境界に対応する前記マーク・バッ
    ファ内のピクセルをマークし、前記ポリゴンの境界に対
    応するピクセルを前記フレーム・バッファに描くステッ
    プであって、 （ｉ）第１のリストがＺフェイク・バック・エッジの頂
    点を含んでおり、第２のリストがＺフェイク・フロント
    ・エッジの頂点を含んでいる２つのリストの一方に、ポ
    リゴンの各Ｚフェイク・エッジを定義する頂点を保管
    し、 （ii）前記Ｚフェイク・エッジの勾配が垂直勾配よりも
    水平勾配に近い場合には、Ｘ軸の頂点値に基づいて、ま
    た前記Ｚフェイク・エッジの勾配が水平勾配よりも垂直
    勾配に近い場合には、Ｙ軸の頂点値に基づいて、各空で
    ない第１及び第２のリストを分類し、 （iii）各空でないリストに対し、順次に対の分類され
    た頂点間にエッジ・セグメントを生成することによっ
    て、前記マーク・バッファ内のＺフェイク・エッジを前
    記境界としてマークする、 ことを含むステップと、 （ｂ）前記ポリゴン境界に対応するマークされたピクセ
    ルが前記マーク・バッファに保存されている間に、前記
    ポリゴンの内側に対応する前記マークバツファ内のピク
    セルをマークするステップと、 （ｃ）前記マーク・バッファ内のマークされたポリゴン
    内部ピクセルを参照して、前記ポリゴンの内側に対応す
    る前記フレーム・バッファのピクセルに記入するステッ
    プと、 からなる凹ポリゴンを描く方法。
20. 【請求項２０】ディスプレイ・プロセッサと、ディスプ
    レイモニタに表示される複数の線の各々についての個々
    のピクセルを記憶するためのフレーム・バッフアを含む
    ディスプレイ手段とを有しており、該フレーム・バッフ
    ァが複数個のアドレス可能なＭ×Ｎの構成ピクセル・ブ
    ロックに編成されているコンピュータ・グラフィックス
    ・ディスプレイ・システムにおける、複数個のアドレス
    可能なＭ×Ｎの構成ピクセルに編成されたマーク・バッ
    ファを使用して前記フレーム・バッファに凹ポリゴンを
    描く方法であって、 各々が３辺のエッジによって内側が囲まれ且つ順番の頂
    点のセットにより表される三角形であって、隣接する三
    角形が共通の重複するエッジを有する三角形のセットに
    前記ポリゴンを分割するステップであって、前記各三角
    形は共通の第１頂点、個々の第２頂点及び第３頂点を有
    し、該第１及び第２頂点を結ぶ第１ベクトルと該第１及
    び第３頂点を結ぶ第２ベクトルとの積の符号によって決
    まる正の向きまたは負の向きを有する如き三角形に分割
    するステップと、 三角形の前記セットを用いて前記ポリゴンの内部に対応
    する前記マーク・バッファのピクセルをマークするステ
    ップと、 前記内部ピクセルをマークするステップが、 前記三角形の各々の向きを判断し、 同一の向きの隣接する三角形の内部ピクセルはマークさ
    れるが、異なる向きの隣接する三角形の内部ピクセルは
    三角形の重畳領域内でマークされないように三角形の各
    々の内側に対応する前記マーク・バッファ内のピクセル
    を処理することを含み、 前記マーク・バッファ内のマークされた内部ピクセルを
    参照して、前記各三角形の内部に対応する前記フレーム
    ・バッファのピクセルに記入するステップと、 からなる凹ポリゴンを描く方法。