JPH0740308B2 - 線分境界画定領域のクリツプ後の余分な辺の除去方法 - Google Patents

Description

【発明の詳細な説明】 以下の順序で本発明を説明する。

Ａ 産業上の利用分野 Ｂ 従来技術 Ｃ 発明が解決しようとする問題点 Ｄ 問題点を解決するための手段 Ｅ 実施例 E1 本発明が使用するシステム（第２、３図） E2 クリッピングの例（第４、５図） E3 本発明のクリッピング（第１、6A、6B図） E4 クリップ後の余分な辺の削除方法（第7A、7B、8A、
8B、9A、9B図） E5 Ｚ軸の場合のクリップ（第10A、10B、10C図） E6 ２つの実施例（第11A−11C、第12A−12D図） Ｆ 発明の効果 A.産業上の利用分野 本発明は一般にコンピユータ図形表示システムに関し、
具体的には線分の境界で画定された領域を制限平面によ
つてクリップする方法、及びこれに関連するクリップ後
の余分な辺の削除方法に関する。これ等の方法は共に、
図形の形象が線分境界画定領域に対応するデータの辺に
よつて表わされる、表示システムで使用される。

B.従来技術 以下、次の用語は次の意味で使用される。

（１）線分境界画定領域：頂点及び接続用直線の線分に
ついて画定された閉じた境界を有する任意の幾何学的形
状、例、凸、凹多角形、自己交差多角形 （２）辺（多角形の辺）：少なくとも２つの頂点と接続
線分の集合（即ち、少なくとも１本のベクトルより成る
集合）３線分境界画定領域は少なくとも１つの辺で画定
される。

（３）連続／不連続：連続とは、線分が時計方向もしく
は反時計方向のどちらかで、相次いで読取られもしくは
発生されることを意味する。不連続とは、線分が非順次
的に読取られ、発生されること、方向に一貫性がなく、
即ち線分が時計方法及び反時計方向に読取られ、発生さ
れることを意味する。

代表的な場合、コンピユータの図形システムにおいて表
示されるべき形象もしくはオブジェクトは、線、字もし
くは多角形のような線分境界画定領域のような基本要素
を使用して画定されている。このシステムによつて遂行
される幾何学的操作のうちで、クリッピングは主も重要
なものの一つである。クリッピングによつて、図形表示
システムはオペレータが画定した窓即ち領域内に存在す
る基本要素の部分だけを表示できる。従つて、線分境界
画定領域即ち多角形のクリッピングはある窓の縁を越え
て進出している閉じた表面を、２次元のものであれ３次
元のものであれ、上記縁を越えて進出されない表面に限
定する過程である。要するに、この過程は視野を画定す
る領域の外部にある閉じた表面の部分を削除して、実際
に発生されるイメージから、形象のオフ・スクリーン部
分即ち不可視部分を除去することを含む。

おそらく、最も普通の閉表面クリッピング方法は、スー
ザーランド・ホジマン（Sutherland Hodgman）アルゴ
リズムである。スーザーランド・ホジマンのクリッピン
グ・アルゴリズムは、一連の簡単な同じ問題を解き、こ
れ等を組合して問題全体を解決する分割一克服技法を使
用する。この方法は米国特許第3816726号に説明されて
いる。スーザーランド・ホジマン・アルゴリズムの教科
書的説明は、1982年刊のJ.D.フオーレィ及びA.バン・ダ
ム著「対話型コンピユータ図形処理の基礎」の第451−4
55頁（J.D.Foley and A.Van Dam,“Fundamentals i
n Interactive Computer Graphics,pp451−455（198
2））になされている。

簡単に説明すると、スーザーランド・ホジマン・アルゴ
リズムは入力として、多角形を表わす一連の頂点を受取
つて、この多角形を視野の境界でクリップし、クリップ
された多角形を画定する他の一連の頂点を出力する。こ
のアルゴリズムは任意の開始／終了頂点から出発して多
角形のまわりを連続的に進み、各段階で相継ぐ頂点と視
野の境界、具体的には視野の境界の１つの平面間との関
係を調べる。

スーザーランド・ホジマン・アルゴリズムの重要な要件
は、多角形の頂点を連続的に多角形のすべての頂点が考
慮される迄、このアルゴリズムに与えなければならない
ことである。この連続性の要件は多くのアプリケーショ
ンを使用する図形表示システムには大きな制約となる。
工業及び機械的設計の応用で、たとえばある種の物理的
部品を設計する場合には、ユーザが画定された領域の境
界を指定する順序はランダムであることが多い。このよ
うなことは、設計されつつある部品が１つもしくは複数
の軸のまわりに対称であり、ユーザは最後に表示される
イメージの半分もしくは1/4を画定して、残りをコンピ
ユータで発生させる場合に、しばしば生ずる。

このことと、スーザーランド・ホジマン・アルゴリズム
が頂点のデータの連続入力を必要とするということか
ら、次の３つの選択が考えられる。

（１）このアプリケーション・プログラムにより、ユー
ザは連続的な線分の境界画定領域だけを画定することに
制約される。（２）不連続的に提示されるデータを連続
したデータに再配列するために、上位コンピユータもし
くは図形表示システムに中間処理を挿入する。（３）不
連続的に提示されるデータを処理できる別の閉表面クリ
ッピング・アルゴリズムを使用する。第１のオプション
は明らかに、ユーザに制約を課すシステムを生じ、第１
及び第２のオプションは共にシステムのパホーマンスが
良くない。従つて第３のオプションを追求しなくてはな
らない。好ましいと考えられるが、線分境界画定領域を
定義する、不連続的に提示されるデータを処理できる代
替クリッピング・アルゴリズムは代表的な場合、クリッ
プされた点を記憶して、その後の点間の線分の分類と発
生に使用するのに大容量のメモリを必要とする。たとえ
ばIBM 5080はこのような図形表示システムであるが、
そのクリッピング・アルゴリズムの具体化には、1Kのメ
モリを必要とする。従つて、連続的もしくは不連続的に
提示されるデータに操作でき、このようなデータを操作
する現在のクリッピング方法を具体化するのより少ない
ハードウエアもしくはソフトウエアを必要とする非制約
的閉表面クリッピング方法は明らかに有用であると考え
られる。

多くの線分境界画定領域クリッピング・アルゴリズムの
他の欠点は、クリッピング処理によつて２つの離ればな
れになつた多角形が生じた場合に発生する、クリップ後
の境界を誤つて表示（接続）する余分な線の削除に関す
るものである。この問題は、スーザーランド・ホジマン
方法を含む、多くの一般に知られたクリッピング・アル
ゴリズム中で生ずるものと考えられ、このクリッピング
・アルゴリズムの後に、さらに処理段階を設けて余分の
辺を除去するか、上出のフオーレイ及びバン・ダムの教
科書の第455頁に説明されているフイラー−アセルトン
（Weiler−Atherton）アルゴリズムのようなより複雑な
クリッピング・アルゴリズムを使用して、最初からクリ
ップ後の余分な辺の発生を避けることによつて解決され
ている。しかしながら、この両方の方法は明らかにパホ
ーマンスを劣化する。従つて動作がより効率的であり、
線分境界画定領域クリッピング方法と協働して、クリッ
プされた閉表面をより効率的に発生し、後述のような新
らしいクリップ後の余分な辺の削除方法が望ましいこと
は明らかである。

C.発明が解決しようとする問題点 本発明の主目的は、連続的もしくは不連続的に提示され
る辺を処理することができる境界画定領域のクリッピン
グ方法を与えることにある。

本発明の他の目的は、具体的により少ないハードウエア
及びソフトウエアを必要とするだけで、従来のクリッピ
ング・アルゴリズムよりもシステムのパホーマンスが改
良された境界画定領域のクリッピング方法を与えること
にある。

本発明の他の目的は、境界画定領域クリッピング・アル
ゴリズムと組合されて使用される、従来の削除技法より
も効率的に、クリップ後に境界を誤つて表わす線を消去
する、余分な辺の削除方法を与えることにある。

D.問題点を解決するための手段 以下さらに説明するように、本発明はその主な態様とし
て、形象が線分境界画定領域を定義する順序付けられた
もしくはランダムな辺の組によつて表わされるコンピユ
ータ図形表示システム中で使用される、線分境界画定領
域を制限平面によつてクリップする方法より成る。この
方法は、第１の線分がクリップ用平面と交差する点を決
定する；第２の線分がクリップ用平面と交差する点を決
定する；第１及び第２の交点を対にする；境界画定領域
のすべての辺が処理される迄上述の段階を繰返す；そし
て複数の交点対が決定された時に、上記交点対を処理し
て、上記交点対の各々に含まれる点間に線が描かれた時
に形成される余分な辺を除去する段階を有する。ここで
上記交点対の処理は、上記平面がＸ軸平面もしくはＹ軸
平面より成る時には（Ｚ軸平面でない時には）、図形表
示システムの領域充填処理中に生ずる。

本発明の他の態様では、本発明は線分境界画定領域をＸ
軸もしくはＹ軸平面によつてクリップした結果形成され
る任意の線を削除する方法を与える。この余分な線の除
去方法は、クリップされた境界画定領域の各線を決定
し、クリップされたＸ軸の辺もしくはクリップされたＹ
軸の辺を同時に除去する段階を有する。

E.実施例 E1.本発明が使用するシステム 本発明の一つの態様の方法は、形象即ちオブジエクトが
閉じた表面の基本要素によつて表わされるコンピュータ
図形表示システムのための線分境界画定領域クリッピン
グ方法である。この方法は入力として、線分境界画定領
域を定義するランダムなもしくは順序付けられた辺の組
を受取つて、クリップされた境界画定領域を表わすクリ
ップ後の辺の組を出力する。

第２図を参照すると、図形表示システム10と上位コンピ
ユータ13間の関係が表示されている。上位コンピユータ
13はアプリケーション・プログラム12及びアプリケーシ
ョン・データ構造14を含む。アプリケーション・プログ
ラム12はアプリケーション・データ構造14中にデータを
記憶し、これからデータを取出して、図形表示コマンド
を図形表示システム10に送る。データ構造14は、以下説
明する図形表示モニタ上に表示さるべき実際の（元の）
もしくは描出された形像即ちオブジェクトの記述を保持
する。データ構造14内に記憶されたオブジェクトの記述
は、オブジェクトの各部の形状を決定する幾何学的座標
データ、オブジェクトの属性、つながりの関係及びどの
ようにオブジェクトの各部が互に接続されるかを示す位
置決めデータを含んでいる。たとえば、上述のように、
オブジェクトは通常多角形のような閉表面の幾何学的基
本要素によつて形成される。多角形は、代表的な場合、
辺を形成する頂点と接続線分の組によつて表わされる。

図形表示システム10は詳細に第３図に示されている。シ
ステム10は上位通信インターフェイス20、システム制御
プロセッサ22、システム・メモリ24、表示プロセッサ2
6、ベクトル・ゼネレータ28、領域充填プロセッサ29、
充填制御平面／境界平面（ビット平面）31、ビデオ・ピ
クセル・メモリ30、及び形像即ちオブジェクトを表示す
るためのモニタ32を含んでいる。これ等の部品の各々
は、IBM 5080のような市販のコンピユータ図形表示シ
ステムの部品によつて具体化できる。上位通信インター
フェイス20は図形表示システム10から上位コンピユータ
13（第２図）への直列インターフェイスを与える。シス
テム制御プロセッサ22は図形表示システム10の主制御装
置を存する汎用プロセッサを有する。プロセッサ22はす
べての関連入／出力装置にサービスし、表示プロセッサ
26に関連した処理を調整し、インターフェイス20を介し
て上位プロセッサ26とインターフェイスする。表示プロ
セッサ26はシステム・メモリ24中に常駐する表示メモリ
・プログラム中の図形表示オーダを実行し、主に表示モ
ニタ32上のイメージの発生に関係する。表示プロセッサ
26は次の機能を実行する。（１）図形表示オーダを解読
し、且たとえばブツクキーピング及び制御のような非図
形表示オーダを実行する。（２）線分境界画定領域に変
換及びクリッピングを行う。（３）データを前処理し、
ベクトル・ゼネレータ28、領域充填プロセッサ29及びビ
デオ・ピクセル・メモリ30に送ることによつて、線、文
字、マーカ、充填多角形のような幾何学的オブジエクト
を表示のために準備する。ベクトル・ゼネレータ28及び
領域充填プロセッサ29は入力として線分の端点を受取
り、表示のための出力としてビデオ・ピクセル・メモリ
30中にピクセルを発生する。ビデオ・ピクセル・メモリ
30はカラー牽引テーブルによつて256色のカラーを同時
に与えることができる８枚の1K×1Kビツト平面より成
る。ビデオ・ピクセル・メモリ30中に記憶されたイメー
ジがモニタ32中に表示され、オペレータがこれを眺め
る。

E2.クリッピングの例 第4A図に示した特定の線分境界画定領域のクリッピング
の例は、不規則な形状の閉表面40に関するものである。
閉表面の一部は表示窓42内に存在するものとして示され
ている。表面40は８個の頂点P1、P2、P3、P4、P5、P6、
P7及びP8を含む。窓42はユーザによつて画定され、２次
元の領域を表わし、その内部では図形の形象を眺めるこ
とができ、即ち形象が表示され、その外部では形象を眺
めることができない、即ちクリップされる。窓40は４つ
のクリッピング平面X_min、X_max、Y_min及びY_maxによつて
画定されている。

ここで説明しているクリッピング方法は、要するに領域
を画定している辺の各頂点を一時に一つずつ処理し、窓
の平面を一時に一つずつ考慮することによつて境界画定
領域、たとえば、表面40を窓によつてクリップする。辺
の最初の頂点を除き、各頂点は現在の入力の頂点値（こ
こではP2で示されている）と、１つ前の入力の頂点値
（ここではP1で示されている）によつて決定される辺の
終点と考える。このクリッピング方法によつて、現在の
頂点P2と前の頂点P1間の関係に基づきクリップ後の境界
画定領域を決定する出力の頂点が発生される。それはこ
れ等の点が考慮中の制限平面に関連しているからであ
る。

本発明の動作を詳細に説明する前に、従来のクリッピン
グ動作を第5A乃至第5D図を参照して簡単に説明する。こ
れ等の図には、閉表面の辺とクリッピング平面間の４つ
の可能な関係が示されている。即ち、辺は完全に制限平
面の見える側にあるか（第5A図）、制限平面の見えない
側の方に向つているか（第5B図）、完全に制限平面の見
えない側にあるか（第5C図）、もしくは制限平面の見え
る側に向つている（第5D図）。

第5A乃至第5D図は、２次元もしくは３次元の表示窓の一
つの境界をなす制限平面50を示している。平面50の見え
る側、即ち左側に存在する境界画定領域の部分は表示の
ために保存されてなくてはならず、見えない側、即ち右
側の部分はクリップされてなくてはならない。図示され
た４つの場合の各々について、境界画定領域の辺52a、5
2b、52c及び52dは現在の頂点P2と１つ前の頂点P1によつ
て決定されている。ここでは頂点は連続的に提示されて
クリップされるものと仮定する。

先ず、第5A図を参照すると、頂点P1及びP2によつて定義
される辺52aは完全に制限平面50の見える側にあり、従
つてこれについてはクリッピング動作は行われない。こ
の場合の頂点P1及びP2は残されて、クリップ後の多角形
の辺となり、最終的に表示される。頂点P2は次の線分評
価のための新らしい頂点P1（第5B図）となり、出力とし
て与えられる。

第5B図は視野の内部から外部へと延びる、頂点P1及びP2
によつて定義される辺52bを示している。平面50の左側
にある、線分の部分は保存しなければならず、右側の部
分はクリップしなければならない。従つて、線分52bと
平面50との交点Ｉがクリップ後の多角形の頂点として出
力される。前の場合と同様に、頂点P2が次の評価のため
の一つ前の頂点P1（第5C図）となる。

第5C図は、完全に視野の外側、即ち平面50の右側にある
辺52cを示している。頂点P1は前のテストでなくなつて
いて（第5B図）、ここで頂点P2が脱落するので、両点と
も表示のためには保存されない。前の場合と同様に、頂
点P2は次の評価での一つ前の頂点P1となる（第5D図）。

最後に、第5D図は平面50の見えない側から見える側に向
う辺52dを示している。従つて、交点Ｉと現在の頂点２
の２つの出力が与えられる。即ち交点Ｉと頂点P2間のク
リップされた辺を決定するためには、両点を出力として
与えられなくてはならない。

上述のことから、第4A図に示されたような閉表面の頂点
を、各クリッピング平面によつて連続的に処理すること
によつて、頂点P1、P2、P3′、P4′、P5、P6、P7′及び
P8′を有する第4B図に示された新らしい表面が発生され
ることか明らかであろう。この新らしい表面が表示され
るべき、原境界画定領域の部分を画定する。

E3.本発明のクリッピング 上述のように、本発明のクリッピング方法の基本的な特
徴は領域の頂点と接続線分を決定する辺が不連続にもし
くはランダムに入力されても、表面40のような線分境界
画定領域を操作できる点にある。たとえば、ユーザは２
つの不連続な辺:P1P2P3P4P5P6及びP1P8P7P6として閉表
面40を定義できる。

本発明のクリッピング方法の基本的原理は、境界画定領
域の辺画定線分が制限平面の見える側から見えない方
に、もしくはこの逆の方に横切る時は、反対方向に向う
他の線分が必ず存在するという認識に基づいている。そ
れは境界画定領域が定義により閉じた幾何学構造だから
である。１つの平面の突当つて２つの交点即ちクリップ
点が発生されると、これ等の点は新らしい、クリップ後
の本境界画定領域の辺を形成するように接続される。交
点を接続する順序は本発明では問題でなく、従つて本発
明の方法は、連続的に提示されるデータの場合と同程度
に容易に、不連続的に提示されるデータを処理できる。
もし交点を接続する線の一部が重なる時は、これ等の線
が処理されて余分な辺が除去されるか、好ましくは以下
説明するように、本発明の他の態様に従つて、Ｘ軸もし
くはＹ軸クリッピング平面中に存在する余分な辺は、ク
リップされた辺を描く時に同時に除去される。

本発明のクリッピング方法を具体化するには、主に第１
の交点即ちクリップ点を記憶する唯一つのレジスタ、お
よび現在のクリップ点の状態を示す、即ちこれが対にさ
れる２つの点のうち第１の点であるか第２の点であるか
を示すフラグ・レジスタがあればよい。

次に、本発明に従つてデータを処理するための１方法及
び関連段階を示す第１図、第6A及び第6B図を参照して線
分境界画定領域のクリッピングについて詳細に説明す
る。２次元のクリッピングには、第6A図及び第6B図の基
本的クリッピング・アルゴリズムを通して、データを４
回通過させる必要がある。たとえば、第１回及び第２回
の通過は左及び右のＸ軸クリッピング平面（即ち第4A図
のX_min及びX_max）に対して行われ、第３及び第４回の通
過は下及び上のＹ軸クリッピング平面（第4A図のY_min及
びY_max）に対して行われる。３次元のクリッピングで
は、従つて６回のアルゴリズムの通過を必要とする。た
とえば、第１図を参照すると、60で主クリッピング・ル
ーチンに導入した後、表示プロセッサ26（第３図）は、
境界画定領域をクリップする平面を表示窓の平面X_minに
セツトする（61）ように指示され、その後第6A及び第6B
図の多角形クリップ・サブルーチン62を呼び出す。平面
X_minによつて境界画定領域を処理した後、プロセッサ26
は主クリッピング・ルーチンに戻つて、クリップ平面を
X_maxに等しくセツトし（63）、境界画定領域をX_maxに対
して評価する（64）。この手順は表示窓のすべての平
面、即ちY_min65及び66、Y_max67及び68、Z_min69及び70、
並びにZ_max71及び72が考慮されて、クリッピング・コマ
ンドの終り73に遭遇する迄続けられる。主クリッピング
・ルーチン中で処理されるために、平面がセツトされる
順序は任意である。さらに直交軸Ｘ、Ｙ及びＺに代つて
任意の定義された平面が使用できる。

第6A図を参照すると、表示プロセッサ26は80でクリッピ
ング・サブルーチンに入り、先ずクリップ状態フラグを
オフにセツト即ちクリヤして、現在まだ対にされるため
に保持されているクリップ交点はないことが示される
（“Ｃフラグ←オフ"82）。命令82を実行した後、プロ
セッサはサブルーチンの主ループに入り、ここで評価の
ために次のデータ部分が得られ、これが現在点レジスタ
P2中に記憶される（“次のP2の読取り"84）。この時点
で、レジスタP2中に記憶されているデータは２つの図形
表示オーダ（コマンド）の一方即ち評価中の辺の頂点を
示す。可能な２つの図形表示コマンドは“境界画定終了
コマンド”及び“辺開始コマンド”である。境界画定終
了コマンドは境界画定領域を表わす入力データの終了を
示すオーダであり、辺開始コマンドは境界画定領域の全
体もしくは一部を表わす新らしい辺の開始を示すオーダ
である。これ等の図形表示オーダは、クリッピング・ア
ルゴリズムのための指示を与える外に、クリップ後の境
界画定領域を描く際にベクトル・ゼネレータ28に指示を
与える。たとえば、辺開始コマンドはゼネレータに命令
して特定の点で作図を停止させ、新らしい代表的には連
続していない頂点に移動して、作図動作を続けさせる。
境界画定終了コマンドはゼネレータに指示して、境界画
定フエイズを中断して以下説明するように、ピクセル発
生段階の充填フエイズを開始させる。命令84の次は質問
“終了コマンド?"に進み、これによつてプロセッサは現
在レジスタP2中に記憶されたデータが境界画定終了コマ
ンドであるかどうかを判断する。もし終了コマンドなら
ば（YESならば）、流れは出口88を介して主クリッピン
グ・ルーチン（第１図）に戻る。もしN0ならば、流れは
質問“辺開始コマンド?"90に進み、現在点レジスタP2中
に記憶されているデータが“辺開始コマンド”であるか
どうかが判断される。もしYESならば、辺開始コマンド
が表示プロセッサの出力“辺開始コマンド出力"92に書
込まれ、フラグがセツトされて次のデータ部分が、辺の
第１の（最初の）頂点であることが示される。（“第１
のフラグ←オン"94）。プロセッサはアルゴリズムの開
始、即ち命令84に戻つて、次のデータ部分を受取る。

質問90に戻つて、もし返答がNOで、現在点レジスタP2中
のデータが評価中の閉表面の辺を決定する１つの線分の
頂点であることが示されると、流れは質問“第１のフラ
グはオン?"に進む。もしレジスタP2中に記憶されている
データが辺の第１の頂点を表わして、第１のフラグがオ
ンならば、プロセッサは指示によつて、第１のフラグを
クリヤし（オフにセツトし）（“第１のフラグ←オフ"9
8）、質問“P2は見られるか?"100に進む。もしレジスタ
P2中の現在の頂点がクリッピング平面の見える側にある
と、現在の点P2が出力“P2出力”に書込まれる（10
2）。どの平面が現在定義されたクリッピング平面であ
るかに依存し、２次元クリッピングを仮定して、簡単な
不等式、即ちX_min≦P2（ｘ）、P2（ｘ）≦X_max、Y_min≦
P2（ｙ）もしくはP2（ｙ）≦Y_maxを満足すると、現在点
P2は平面の見える側にある。現在点P2は次に前の点レジ
スタP1にコピーされ（“P1←P2"104）、アルゴリズムの
ループの最初、即ち命令84に戻り、次のデータ部分が受
取られる。

質問96に戻って、第１のフラグがオフで、現在点レジス
タP2中のデータが辺開始コマンド後の最初の頂点でない
ことがわかると、流れは質問“P1P2クリップ?"106に進
み、前の点P1と現在点P2によつて決定される線分が定義
されたクリッピング平面と交差するかどうかが判断され
る。もし線分P1P2がクリップされない場合には、流れは
質問“P2は見られるか?"100に進み、現在点P2がクリッ
ピング平面の見える側にあるかどうか、従つて命令102
で出力“P2出力”に書込まれるかどうかが判断される。
再び、現在点P2が前の点レジスタP1にコピーされ（“P1
←P2"104）、アルゴリズムのループの最初に戻って、次
のデータ部分が求められる。

もし質問106で評価されつつある線分P1P2が定義された
クリッピング平面と交差する時は、プロセッサは指示さ
れて交点Ｉを計算する（“交点Ｉの計算"108）。クリッ
ピング平面の交点は任意の方法で決定できる。たとえ
ば、特に効率的な方法は上出のフオーレイ及びバン・ダ
ムの教科書の第146−147頁に説明されている。交点Ｉの
計算は任意の標準の線クリッピング・アルゴリズム、た
とえば上出のフオーレイ及びバン・ダムの教科書の第14
5−151頁に示されたいくつかのアルゴリズムによつて達
成される。

第6B図に示すように、交点Ｉの決定後、結合線109を介
して、プロセッサはクリップ状態フラグの状態を評価す
る（“Ｃフラツグ１＝オン?"110）。もし交点Ｉが対に
なるべき２つの点の最初の点である時は、流れは質問
“P2は見られるか?"112に進み、現在点P2が定義された
クリッピング平面の見える側にあるかどうかが判断され
る。もしYESならば、交点Ｉは出力“Ｉ出力"114に書込
まれ、現在点P2は“P2出力',116に書込まれる。それは
線分P1P2が視野の外側から視野の内側に入るからであ
る。もし現在点P2がクリッピング平面の見えない側にあ
る時は、交点Ｉだけが出力“Ｉ出力"118に書込まれる。
現在点P2がクリッピング平面の見える側にあるか、見え
ない側にあるかにかかわらず、交点Ｉは使用のためにレ
ジスタCP1中に記憶され（“CP1←I"120）、クリップ状
態フラグがオンにセツトされて、１つの交点が対にされ
るために現在保持されていることが示される。クリップ
状態フラツグをセツトした後、現在点は前の点レジスタ
P1にコピーされ（“P1←P2"124）、線125によつてアル
ゴリズムのループの最初に戻り、次のデータ部分が求め
られる。

質問110に戻って、もしクリップ状態フラグがオンなら
ば、交点はすでにレジスタCP1中に記憶されていて、現
在の交点Ｉと対にされるようになつている。従つて、流
れは最初質問“P2は見られるか?"126に進み、現在点P2
がクリッピング平面の見える側にあるか見えない側にあ
るかが判断される。もし見える側にあると、辺開始コマ
ンドが出力され（“辺開始コマンド出力"128）、続いて
レジスタCP1中に記憶された前のクリップ点（“CP1出
力"130）、現在の交点Ｉ（出力“Ｉ出力"132）、および
現在点P2（出力“P2出力"134）が出力される。辺CP1、
Ｉ、P2が出力された後、プロセッサは指示されて、クリ
ップ状態フラグをオフ状態にセツトする（“Ｃフラグ←
オフ"136）。

もし質問126で、評価中の線分P1 P2の終点P2がクリッ
ピング平面の見えない側にあると判断されると、現在の
交点Ｉが先ず“Ｉ出力"138に出力され、次に辺開始コマ
ンドが“辺開始コマンド出力"140に、記憶されているク
リップ点が“CP1出力"142に、また現在の交点が“Ｉ出
力"144に、出力される。１対の交点が出力された後、同
じくクリップ状態フラツグが“オフ状態にセツトされる
（“Ｃフラグ←オフ"136）。命令136の後に、現在点P2
が前の点レジスタP1にコピーされ（“P1←P2"124）、線
125を介してアルゴリズムのループの最初の命令84に戻
り、次のデータ部分が求められる。

出力のため、レジスタCP1中に記憶した前の交点と現在
の交点Ｉを対にするための命令128及び140で辺開始コマ
ンドを発生し、出力する機能は境界辺を任意の順序で処
理するための上述のクリッピング・アルゴリズムの能力
の中心部分である。

E4.クリップ後の余分な辺の削除方法 最初に説明した通り、本発明の他の態様はクリップされ
た辺の改良削除方法を与えることにある。第4B図を参照
して明らかなように、閉表面40を制限平面X_minに対して
クリップすると、余分な辺51とともに、クリッピング平
面の見える側に２つの接近する多角形50及び52が形成さ
れる。辺51は頂点がP1P2P3P4P5P6P7P8P9P1のように連続
的に提示されるか、たとえば辺P1P2P3P4P5P6とP1P8P7P6
のように不連続的に提示されるかにかかわらず形成され
る。余分な辺51が消去された所望の結果を第4C図に示
す。

Ｘ軸、Ｙ軸及びＺ軸でクリップされた時に生じる余分の
辺は異なる処理方法で除去される。具体的には、Ｘ軸及
びＹ軸の余分な辺はシステムの境界画定段階の領域充填
中に除去することが好ましく、他方Ｚ軸の余分な辺はシ
ステムのクリッピング段階と領域充填段階間に挿入され
る処理によつて除去される。Ｘ軸及びＹ軸の余分な辺の
削除について、以下先ず説明する。

最適実施例では、第6A図及び第6B図のアルゴリズムによ
つて出力されたクリップ後の辺は、システムの作図段階
の境界画定段階中に２つの“作業”ビツト平面中に記憶
される情報を発生するのに使用される。この記憶情報は
領域充填フエイズ中に領域充填プロセッサによつて使用
され、ピクセル・メモリ30の表示ビツト平面中に充填領
域及び辺が発生される。このメモリ30から表示がリフレ
ツシユされる、以下説明されるように、境界画定フェイ
ズは、クリッピング・アルゴリズムの出力から領域充填
プロセッサ29によつてＸ軸及びＹ軸辺が受取られる時に
同時に情報を発生して、これを２つの作業ビツト平面
（第３図）中に記憶する。以下説明するように、Ｚ軸辺
は上記Ｘ軸及びＹ軸辺の処理後に処理される。ピクセル
発生段階の充填フエイズは、上述の境界画定終了コマン
ドに遭遇した後に開始する。

境界画定フエイズの開始時に、２つの作業ビツト平面の
ピクセルはある既知の状態、たとえば０にクリヤされ
る。２つの作業ビツト平面のうちの第１の平面、充填制
御平面（以下説明される）は、「辺フラグ・アルゴリズ
ム−ラスタ走査表示のための充填方法」と題するアツク
ランド及びウエスチによる論文（Ackland and Weste
“The Edge Flag AlgorithIm−Ａ Fill Method f
or Raster Scan Displays"）及び「境界画定領域充
填の実際的実施における実験」と題するアドリアン・ゲ
イによる論文（Adrian Gay“Experience in Practic
al Implementation of Boundary−Defined Area F
ill"）中に説明されているのと類似の充填方法によつて
充填さるべきクリップ後の領域の境界を画定する“辺フ
ラグ”即ち書込み信号を記憶するのに使用される。他の
一般に知られている充填アルゴリズムも使用できるが、
辺フラグ・アルゴリズムが好適と考えられる。それはこ
れがハードウエア中でより容易に具体化できるからであ
る。２つの作業ビツト平面のうち第２の平面、境界平面
（以下説明する）はクリッピング・アルゴリズムからの
実際の（元の）辺及び任意のＺ軸辺（以下説明された余
分な線の除去のために予め処理された）を記憶するのに
使用される。これ等の辺は標準のブレセンハム（Bresen
ham）線発生アルゴリズムによつて発生される。

VLSIゲート・アレイ並びに、充填制御平面（FCP）及び
境界平面（BP）と呼ばれる２つの専用作業ビツト平面よ
り成る領域充填のためのハードウエアがクリップ後の線
分境界画定領域の作図に使用されることが好ましい。ゲ
ート・アレイが実際及びクリップ後の線分境界画定領域
の作図及び該領域の内部を充填するために、データをビ
ツト平面に書込み、これから読出すのを制御する。具体
的には、領域充填ハードウエアは次の２つのモード動作
を遂行する。（１）境界プロツト・モード（２）走査モ
ード。境界プロツト・モードでは、領域の閉じた境界が
描かれ、走査モードでは、領域の内部が充填される。代
表的には、線分境界画定領域の境界及び内部には、夫々
境界色と異なつた内部色が関連している。実際の（即ち
クリップされていない）辺は境界色で描かれ、クリップ
後に発生した辺は充填段階中に内部色で描かれている。

作業ビツト平面の内容が読出されて、充填データがスク
リーン・リフレツシユ（再生）メモリ（SRM）に送られ
る。論理的には、ビツト平面及びスクリーン・リフレツ
シユ・メモリは1:1に対応している。境界平面はクリッ
プ後の境界画定領域のすべての実際の辺及びすべてのＺ
軸の辺を含んでいる。充填制御平面は、１ベクトル、１
走査線につき１つのピクセルを含んでいて、従つて所与
の線分境界領域について１本の水平走査線当り一対のピ
クセル（即ち辺フラグ）が存在する。

本発明の境界プロツト・モードでは、領域充填動作は、
次の第１表乃至第４表のアルゴリズムに従つて、クリッ
プ後の境界画定領域の辺をビツト平面及びスクリーン・
リフレツシユ・メモリ（SRM）中に描く。クリップされ
た時の余分な辺の削除及びいくつかの例の説明に進む前
に、ある仮定を設定する。具体的には、この説明は領域
充填段階中に水平走査を仮定している。もし領域充填走
査が水平方向でなく垂直方向に行われるわらば、Ｘ軸及
びＹ軸の余分な辺の削除方法は逆にすることができる。
水平走査を仮定すると、充填制御平面への書込みはＹ軸
の移動の関数である。

又、次の用語は右側に説明された意味を有する。

X_pos及びY_pos−夫々Ｘ軸及びＹ軸の方向の相対移動 ０は非移動を示す。

１は移動を示す。

X_sgn及びY_sgn−夫々Ｘ軸及びＹ軸方向の移動方向 ０は正方向移動を示す。

１は負方向移動を示す。

W_pix −個々のピクセルの書込みイネーブル ０は非書込みを示す。

１は書込みを示す。

さらに、提示される表及び例は、特にことわらないかぎ
り、単位としてデータの４ピクセルが受取られて描かれ
ること、クリップされた辺はその成分ベクトルによつて
調べられるものとする。しかしながら、この概念は同じ
くデータのベクトル当り任意の数のピクセルに適用可能
である。

最初に、第１表に示したように、辺のタイプでビット平
面（FCP、BP）もしくはSRMあるいはこの両方に書込み可
能であるかどうかを判断する。

“YES"はビツト平面もしくはスクリーン・リフレツシユ
・メモリが作図即ち書込み信号を受取れること、“NO"
はそうでないことを示す。FCP、BPもしくはSRMに実際に
書込まれるかどうかは以下に説明する特定の充填アルゴ
リズムに依存する。

第１表に決められたように、クリップ後のＸ軸及びクリ
ップ後のＹ軸の辺は境界平面もしくはスクリーン・リフ
レツシユ・メモリのどちらにも書込まれないことに注意
されたい。それは各辺が真に垂直及び水平であり、従つ
て本発明の新らしい態様に従つて、クリップ後の境界画
定領域が充填される時に陰伏的に描かれるからである。
さらに、クリップ後のY_maxとY_min辺とはFCP中では異な
る態様で処理される。それは充填制御平面の作図アルゴ
リズムがクリップ後の領域の一番上のピクセルは描かな
いが、一番下のピクセルは描くからである。具体的に説
明すると、正方向のＹ移動ベクトルの場合、最後のピク
セルは描かれないが、負方向のＹ移動ベクトルの場合は
最初のピクセルが描かれない。もし望まれる場合には、
この書込みアルゴリズムは逆にすることができるが、第
１表のFCP中のクリップされたY_min及びクリップされたY
_minのための書込みコマンドは逆にしなければならな
い。

境界平面及びスクリーン・リフレッシュ・メモリへの作
図は次のようにW_pixの関数である。

第２表 ビット（０）のBP/SRM書込み W_pix（０） ビット（１）のBP/SRM書込み W_pix（１） ビット（２）のBP/SRM書込み W_pix（２） ビット（３）のBP/SRM書込み W_pix（３） 現在の説明では、すべての実際の辺及びクリップ後のＺ
軸の辺のためのW_pix信号は“1"書込み信号より成るもの
と仮定している。

上述のように、FCPのため書込み信号はＹ軸移動と方
向、即ちY_posとY_sgnの関数である。

特定のFCPアルゴリズムを第３表中に示す。

ここで、 Y_pos（０）＝ビツト（０）のＹ軸方向の相対移動 Y_pos（１）＝ビツト（１）のＹ軸方向の相対移動 Y_pos（２）＝ビツト（２）のＹ軸方向の相対移動 Y_pos（３）＝ビツト（３）のＹ軸方向の相対移動 C_in＝キヤリ・イン・ビット キヤリ・イン・ビツトは前のベクトルの関数であり、方
向の変化、即ち０から１もしくは１から０へのY_sgnの変
化を示す機能を有する。現在のクリップ後の余分な辺の
削除の説明には関係ないが、このビツトは次のようにし
て計算される。

クリップ後の境界画定領域の最初のベクトルの場合、C
_in＝０、 その後は ここで、 ★は論理AND ＋は論理OR ｉ＝現在のベクトル Y_sgn（ｉ−１）＝前のベクトルのY_sgn C_in（ｉ−１）＝前のベクトルのキヤリ・イン・ビツト Y_pos（ｉ−１）（０）＝ビツト（０）における前のベク
トルのY_pos 最後に、適切なビツト平面もしくはスクリーン・リフレ
ツシユ・メモリに書込み信号を与える前に、本発明の境
界プロツト・モードは次のような２サイクルの読取り−
変更−書込み動作を行う。

（１）データを両ビツト平面から読取つてラツチする
（サイクル１） （２）データを次の第４表に従つて変更する。

（３）新らしいデータを両ビツト平面に書戻す（サイク
ル２） 上記表に示したように、境界平面のデータはOR演算によ
つて変更される。即ち境界平面から読取られたデータ
（即ち前のベクトルのピクセル）はその新らしいデータ
（新らしいベクトルのピクセル）と論理的にORされてBP
に書込まれる。充填制御平面は、データをFCPから読取
つて、これを新らしいデータとXOR（排他的OR）するこ
とによつてそのデータが変更される。この動作の意図
は、オンであつたビツトを新らしいデータもオンの時に
オフにすることにある。従つてベクトルを描く時には、
最初のベクトルが充填の制御平面に書込まれ、第２のベ
クトルが最初のベクトルと一部重なるように描かれる時
は、最初のベクトルと重なる第２のベクトルの線分はFC
Pから消去される。さらに第３のベクトルが描かれて、
前に消去された線分と重なる時は、この線分は再び描か
れる。スクリーン・リフレツシユ・メモリは、境界平面
から読取られたデータが０で、新らしいデータが１の時
にだけ更新される。上述の領域充填アルゴリズムに関連
するＸ軸及びＹ軸のクリップ後の余分な辺の削除方法は
第7A、第7B、第8A、第8B、第9A及び第9B図の例を参照す
ればより良く理解されよう。

［Ｘ軸のクリップ後の余分な辺］ 先ず、第7A図及び第7B図を参照すると、軸の余分な辺の
削除方法が示されている。境界画定領域150はクリッピ
ング窓152のX_min制限平面に対してクリップされて、影
線で示した２つの離散領域151が眺められるように残さ
れる。第4A−第4C図に関して説明した通り、余分な辺P
2′P3′が存在し、削除しなければならない。クリップ
後の辺は成分ベクトルに分割され次の情報が得られる。

P1P2′＝実際のベクトル P2′P3′＝クリップ後のＸ軸ベクトル P3′P4＝実際のベクトル P4P5＝実際のベクトル P5P6′＝実際のベクトル P6′P7′＝クリップ後のＸ軸ベクトル P7′P8＝実際のベクトル P8P1＝実際のベクトル 説明の目的のために、ベクトルを順番に調べるものと
し、夫々の平面及びメモリに書込まれる情報は第7B図の
通りであるものとする。ここで“×”は移動だけを表わ
し、“○”は対応するFCPもしくはBP及びSRM（BP/SRM）
に書込まれるデータを表わすものとする。

P1P2′はFCP、BPもしくはSRM（第１表）に書込まれるこ
とのできる実際の辺である。P1P2′は水平移動より成る
ので、充填制御平面は書込み信号を受取らない（第３
表）。BP及びSRMは各々ベクトルP1P2′に対応するピク
セルに書込まれる。即ち“1111"信号が上記平面及びメ
モリによつて受取られる（第２表及び第４表）。上述の
ように、境界平面の読取り−変更−書込み動作は論理OR
によつて行われ、新らしいベクトルのピクセル、もしく
は読取つたベクトルが“1"であると、結果も“1"であ
り、他方スクリーン・リフレツシユ・メモリは境界平面
から読取られたデータが“0"であり、新らしいデータは
“1"である時に更新される。

ベクトルP2′P3′はクリップ後のＸ軸辺であり、従つて
データはBPもしくはSRMに送られない（第１表）。ベク
トルP2′P3′は正のＹ軸方向に向いているので夫々ビツ
ト（０）（１）（２）及び（３）のための書込み信号は
“1110"である（第３表）。この信号はP2′のビツト
（０）からP3′のビツト（３）に通過するのに必要な３
つの正方向移動から導かれる。即ちY_pos（０）（１）
（２）及び（３）＝"1110"である。Y_pos（０）は“1"で
あり、上述のキヤリ・イン・ビツトから決定されるC_in
は“0"であるから、ビツト（０）には書込み信号が存在
する。

P3′P4は実際のベクトルであり、“1111"のような書込
み信号がBP/SRMに送られる。このP3′P4はＹ軸方向の移
動を伴なわず、水平方向を向いているので、“x"移動信
号だけがFCPに送られる（第１表乃至第３表）。

P4P5は実際のベクトルであり、このことはBP/SRMの各々
が“1111"書込み信号を受取ることを意味し、“1110"の
Y_posのＹ軸移動より成り、これによつて“1110"の書込
信号がFCPに与えられる（第３表）。この場合もC_in移動
は“0"である。

P5P6′も実際のベクトルであり、“1111"データ信号がB
P及びSRMに書込まれる。Ｙ軸の移動はないので、データ
は充填制御平面には書込まれない。

P6′P7′は重要なベクトルである。それはそのマツピン
グによつて、充填制御平面内のP2′P3′間の余分な辺が
削除されるからである。P6′P7′はＸ軸の辺より成り、
従つて情報はBPにもSRMにも書込まれない。ベクトルP
6′P7′はＹ軸の負方向を向いているので、Y_sgnは“1"
である。この書込み信号については第３表を参照された
い。ベクトルP6′P7′は10個のピクセルを合み、従つて
第３表を外挿することによつて、ビツト（４）乃至
（９）のための書込み信号は夫々Y_pos（３）乃至（８）
によつて決定される。再び、C_inは“0"であり、Y
_pos（０）乃至（８）は各々“1"であるから、書込み信
号は“011111111"となる。この信号と、同じピクセルに
ついてFCPから読出した対応する信号“0000111000"に対
してXOR論理演算を適用すると、ビツト（５）乃至
（７）に対応するデータが削除され、P2′及びP3′間の
余分な辺が除去される。P7′P8及びP8P1は各実際のベク
トルであり、ベクトルP1P2′とP4P5に関して説明したの
と同じ理由で、FCP、BP及びSRMに書込まれる上述のデー
タが生ずる。

最後に、クリップ後の領域のすべての実際の辺は境界平
面とスクリーン・リフレツシュ・メモリ中に存在し、適
切なＸ軸のクリップ後の辺は、エツジ・フラグもしくは
充填制御平面中の書込み信号からの領域充填中に生ずる
ことに注意されたい。

〔Y_maxの余分な辺〕

第8A図で、線分境界画定領域150′は表示窓152′のY_max
と交差して、次のベクトルのタイプを発生する。

P1 P2′＝実際のベクトル P2′P3′＝クリップ後のY_maxベクトル P3′P4＝実際のベクトル P4P5＝実際のベクトル P5P6′＝実際のベクトル P6′P7′＝クリップ後のベクトル P7′P8＝実際のベクトル P8P1＝実際のベクトル 再び各ベクトルを個々に調べて、充填制御平面、境界平
面及びスクリーン・リフレツシュ・メモリがどのように
書込まれるかについて、第8B図を参照して説明する。

ベクトルP1P2′は実際のベクトルであり、情報はFCP及
びBP/SRMに書込むことができる（第１表）。再び実際の
辺のW_pixは常に書込み信号、即ち“1"であり、従つて
“1111"書込信号がBP及びSRMに送られる。ベクトルP1P
2′についてのY_posは、Y_sgn“0"であるから“1110"であ
り、書込み信号“1110"を生ずる（C_in＝“0"、第３
表）。

ベクトルP2′P3′はクリップ後のY_max辺であり、これは
第１表から明らかなように、PBもしくはSRMに送られる
書込み信号を予じめ空にする。さらに第１表はクリップ
後のY_max辺の最初と最後のピクセルだけをFCPに書込む
ように指示する。XORによる読取り−変更−書込み動作
の遂行によつて（第４表）P2′P3′の最初と最後のピク
セルが形成される。

ベクトルP3′P4は負のＹ軸方向に向う実際のベクトルで
あり、ビツト平面及びスクリーン・リフレツシユ・メモ
リ中の適切なピクセルは“1111"書込み信号を受取り
（第２表）、充填制御平面は“0111"信号を受取り、こ
れは対応するピクセルから読取られた信号と一度XORさ
れ（第４表）、４つのピクセルのＹ方向移動について、
Y_pos（０）乃至（３）は“1110"に等しくなり、上述のC
_inの式から導かれてC_in＝“0"となる（第３表）。

ベクトルP4P5は実際のベクトルであり、“1111"書込み
信号がBP/SRMに送られる。ここでも、BPに送られる信号
は読取り−変更−書込みサイクル中にOR演算を受ける
（第４表）。Ｙ移動は存在しないので、充填制御平面は
P4P5に対応するピクセルの書込みシステムを受取らな
い。

ベクトルP5P6′は実際のベクトルであり、BP/SRMへの
“1111"書込信号を生じ、Ｙ軸の正方向に向うので、“1
110"のY_posを生じる。従つて、第３表からC_in＝“0"に
より、FCPへの書込み信号は“1110"になる。

ベクトルP6′P7′はクリップ後の辺であり、従つて移動
信号だけがBP/SRMに送られ、FCP中のベクトルの最初及
び最後のピクセルだけが書込み信号を受取る（第１
表）。読取り−変更−書込みサイクルは依然行われるが
（第４表）、前にP2′及びP3′で遭遇したピクセルが０
の書込み信号とXORされるので、これ等は“オン”に留
まる。

ベクトルP7′P8′は実際のベクトルであり、従つて“11
11"書込み信号がBP/SRMに送られ、Ｙ軸の負の方向に向
いているのでY_pos（０）乃至（３）は“1110"になる。Y
_sgnが“1"で、C_in＝“0',であるから、“0111"書込み信
号がFCPに送られる（第３表）。

ベクトルP8P1は実際のベクトルであり、"1111"の書込み
信号がBP/SRMに送られ、Ｘ軸方向にあるので充填制御平
面には情報は書込まれない。

再び、すべての実際の辺はBP/SRM中にあり、正しいY_max
の辺はFCP中の書込信号からの領域充填走査中に発生さ
れることに注意されたい。

〔Y_minの余分な辺］ 第9A図で、境界画定領域150″は表示窓152″のY_minによ
つてクリップされている。領域150″は前に説明した領
域150及び150′と同じであり、一度制限平面でクリップ
されると、余分な辺P2′P3′が発生する。所望の結果15
1″は影線で示した２つの別個の領域より成る。再び領
域150″を画定するベクトルを順番に調べる。点P1から
始まつて、次のベクトルを描かなければならない。

P1P2′＝実際のベクトル P2′P3′＝クリップ後のY_minベクトル P3′P4＝実際のベクトル P4P5＝実際のベクトル P5P6′＝実際のベクトル P6′P7′＝クリップ後のY_minベクトル P7′P8＝実際のベクトル P8P1＝実際のベクトル 最初に、クリップ後の辺がY_minベクトルである時は、書
込み信号はビツト平面にもスクリーン・リフレツシユ・
メモリにも送られないことに注意されたい。上述のよう
に、クリップ後のY_min辺は、概路が説明された充填アル
ゴリズムの実行の結果、本来完成するものである。

ベクトルP1P2′は実際のベクトルであり、"1111"書込み
信号がBP/SRMに送られ、Ｙ軸の負の方向に向うので、FC
Pへの書込み信号は“0111"である（C_in＝“0"）（第３
表）P2′P3′はクリップ後のY_min辺であるから、FCPもB
P/SRMも書込み信号を受取らない。

ベクトルP3′P4は実際の辺であり、“1111"書込み信号
がBP/SRMに送られ、Ｙ軸の正の方向に向うので、“111
1"書込み信号がFCPに送られる。

ベクトルP4P5は実際の水平辺であり、移動信号だけがFC
Pに送られ、BP/SRMは“1111"書込み信号を受取る。

ベクトルP5P6′は再び実際の辺であり、BP/SRMは“111
1"書込み信号を受取り、Ｙ軸の負の方向に向うので、FC
Pは“0111"信号を受取る（第３表）。

ベクトルP6′P7′はY_min上のクリップ後の辺であるか
ら、書込み信号はFCPにもBP/SRMにも送られない（第１
表）。

ベクトルP7′P8はＹ軸の正の方向に向う実際の辺である
から、FCPは“1110"信号を受取り、BP/SRMは“1111"信
号を受取る。

最後に、ベクトルP8P1は水平の実際の辺であるから、書
込み信号はFCPに送られず、1111"信号がBP/SRMに送られ
る。

E5.Z軸の場合のクリップ 上述のように、第２のモード、即ち走査モードは線分境
界画定領域の実際の充填を行う。境界平面及び充填制御
平面からのデータは、領域の下左端から始まつて下右端
へ水平方向に読出される。

次にデータは１走査線インクレメントされて、右端から
左端に読出される。この過程はすべてのデータがビツト
平面から走査して出される迄、即ち境界画定領域の一番
上に達する迄繰り返される。

充填制御平面で、水平行上の各ビツト対は充填動作のイ
ネーブル／ディスェーブリングを制御する。充填動作は
第１（最初）のビットから始まつて第２のビツトまで続
く。クリップ後のＸ軸及びクリップ後のＹ軸辺はこのよ
うにして描かれる。それはこれ等の辺が境界平面もしく
はスクリーン・リフレツシユ・メモリへ書込まれていな
いからである。充填がイネーブルされる時、これは境界
平面のデータとチェツクされる。対応する境界平面ビツ
トが“オン”（実際のもしくはクリップ後のＺ軸辺を表
わす）ならば、これ等のビツトは充填の一部として書込
まれない。

簡単に上述したように、余分な辺の除去は３次元クリッ
ピングの場合、特に線分境界画定領域をＺ軸平面（即ち
Z_minもしくはZ_max）によつてクリップする場合は若干複
雑となる。クリップ後のＺ辺は表示モニタ上で、任意の
回転角度で表示できる。本発明の排他的OR方法は偶数本
重なり合った辺を除去するが、この方法は重なりあう辺
が互に同じピクセルを含むという前提に依存している。
このことはＸ軸及びＹ軸のクリップ後の辺については常
に成立つ。それは、第4A図を参照して明らかなように、
Ｘ軸によるクリップ後の辺は常に水平線分であり、Ｙ軸
によるクリップ後の辺は常に垂直線分であるからであ
る。このようなクリップ後の辺について、ピクセルが発
生される時は、夫々Ｘ軸辺もしくはＹ軸辺には夫々Ｙ方
向もしくはＸ方向の移動成分は含まれない。従つてＸ軸
もしくはＹ軸上に発生される任意の点は互に重なること
が保証される。

Ｚ軸のクリップ後の辺では、クリップ後のＺ軸辺の端点
を発生する時に図形表示システムによつて使用された論
理によつて、偶数本重なりあう線分を完全に除去するこ
とはできない。線分境界画定領域160を水平から僅かに
傾いたＺ軸制御平面162によつてクリッピングする例が
第10A図に示されている。領域160は辺P1P2P3P4P5P6P7P8
P1によつて画定されている。領域160をＺ軸平面162によ
つてクリップすると、新らしいクリップ後の辺P3′P4′
及びP7′P8′を生ずる。これ等の辺は重畳し、従って削
除しなければならない線分P3′P4′を有する。しかしな
がら、線P3′及びP4′は、スクリーンの整数の座標点上
にないので、これ等は一番近い座標点にまるめなければ
ならない。第10B図は、点が直線によつて接続される時
にこの整数へのまるめによつて発生する誤差を示してい
る。クリップ後の辺P3′P4′及びP7′P8′をラスタで描
いた結果を第10C図に示す。この図からわかるように、
排他的OR演算をクリップ後の辺に対して行つても、余分
な辺P3′P4′の一部が残されるので、このやり方は不完
全である。領域充填辺フラグ・アルゴリズムは、これ等
の辺を完全に除去しなければならない。さもないと、あ
いまいな結果を生ずる。従つて、Ｚ軸の余分な辺はクリ
ッピング後、ただし領域充填段階の前に別途に処理され
て、望ましくない線分を除去しなくてはならない。この
除去は、以下説明するようにして達成される。

Ｚ軸のクリップ後の線分は、この辺が前側のＺ平面もし
くは後側のＺ平面、即ち夫々Z_minもしくはZ_maxのどちら
でクリップされたかに依存して、２つの積層面（heap）
中に記憶される。線分境界画定領域をクリッピング段階
を通して完全に通過した後、クリップ後のＺ軸の線分は
一連の点として夫々の積層面中に記憶される。分類アル
ゴリズムは重要ではない。代表的な場合、境界画定領域
は少数の（たとえば、３以下の）クリップ後のＺ軸の辺
を有する。多数のベクトルの点を分類するのには十分で
はないが、挿入アルゴリズムのオーバーヘツドの低いこ
とが多くの場合に効率を最大化する。

分類の順序は主な変更の軸によつて決定される。８分円
１、４、５及び８内に存在する辺は、点の内Ｘ軸の座標
に基づいて分類され、８分円２、３、６及び７内に存在
する辺はＹ軸座標に基づいて分類される。分類された点
は次に対にされ、互に重畳する新らしいクリップ後の線
分が形成される。第10B図に示された例では、分類後ベ
クトルP8′P3′及びP4′P7′が発生され、これによつて
余分な辺P3′P4′が除去される。新らしいクリップ後の
線分はベクトル・ゼネレータに送られ、すべての実際の
辺並びにクリップ後のＸ軸及びクリップ後のＹ軸辺のそ
の後の処理について上述されたように、領域充填処理か
行われる。これによつて、Ｚ軸書込み信号がBPに境界色
でなく、内部色で書込み可能になる。

E6。２つの実施例〔実施例１〕 第11A図を先ず参照すると、線分境界画定領域170は４つ
のクリッピング平面X_min、X_max、Y_min、Y_maxによつて画
定されている表示窓172内に部分的に存在するものとし
て示されている。図示されたように、基本要素170は、Y
_minクリッピング平面だけと交差している。しかしなが
ら，領域170内に存在する開孔171によつて、クリッピン
グを複雑にしている。入力データ・ストリームはユーザ
によつて次のように決定される。

辺 P3P4P5P3 辺 P6P7P8P6 第6A図及び第6Bに示したアルゴリズムを適用して、辺開
始コマンドを受取つてデータ入力の処理が開始される。
辺開始コマンドが先ず命令92において出力に書込まれ、
クリップ後の辺の開始が示される。第１のフラグ・レジ
スタが“オン”にされて、アルゴリズムの最初に戻っ
て、ここでデータの次の部分が現在点レジスタP2に読込
まれる。レジスタP2はここで最初の入力辺の最初の点、
即ちP3を含んでいる。頂点P3は表示窓172内にあるの
で、この点は命令102で出力に書込まれる。次に現在点P
2は前の点レジスタP1に読込まれ、次の頂点P4が現在点
レジスタP2を読取られる。線分P1P2、即ちこの実施例の
P3P4はクリッピング平面（Y_min）と交差しているので、
交点Ｉ即ちP4′が命令108で計算される。次に交点P4′
か命令118で出力される。それはこの点が対にさるべき
２つの交点の最初のものであつて、現在点P2がクリッピ
ング平面Y_minの見えない側にあるからである。交点P4′
も又レジスタCP1中に記憶され、クリップ状態フラグが
“オン”にセツトされる。現在点P2は命令124で前の点
レジスタP1にコピーされ、次の頂点P5が現在点レジスタ
P2に受取られる。線分P4P5はクリッピング平面Y_minの見
えない側にあるので、出力は与えられない。現在点P2、
即ち今の現在実施例でP5は、命令104で前の点レジスタP
1に書込まれ、辺の次の頂点P3が現在点レジスタP1に書
込まれる。線分P5P3はクリッピング平面Y_minと点P5′で
交差するので、アルゴリズムの命令108で計算され、次
にプロセッサはクリップ状態フラグがセツトされている
かどうかを判断するように指示される。点P5′は対にさ
るべき２つの点の第２の点であり、P4′はすでに記憶さ
れていて、現在点P2はクリッピング平面の見える側にあ
るので、プロセッサは最初命令128で辺開始コマンドを
出力に書込み、続いてCP1レジスタに記憶したクリップ
点P4′、現在のクリップ点P5′及びレジスタP2に保持さ
れた現在点か出力される。対にされた交点、即ちP4′及
びP5′が出力された後、クリップ状態フラグがオフにセ
ツトされ、アルゴリズムの最初に戻る。第１の辺の入力
から得られるクリップ後の出力データ・ストリームは次
の通りである。

辺 P3P4′ 辺 P4′P5′P3 開孔171を画定する辺P6P7P8P6が次に同じようにして処
理されて、次の出力データ・ストリームが発生される。

辺 P6P7′ 辺 P7′P8′P6 出力された辺を描くと、第11B図に示されたクリップ後
の境界画定領域が発生される。図示のとおり、表示窓17
2の境界の余分な辺174は出力された辺の線分を接続して
一度は発生される。本発明の上述の余分な辺削除方法を
使用して、辺の接続線が描かれる時に、クリップ点P7′
とP8′間の接続線174が削除される。具体的に説明する
と、線分174はクリップ後のＸ軸辺であるから、ベクト
ルP4′P5′及びP7′P8′を領域充填段階の境界画定フエ
イズで排他的OR演算を適用すると、出力辺P7′P8′P6を
描くのと同時にFCP中の辺174が除去される。

［実施例２］ 境界画定領域を２つの制限平面でクリップする方法を第
12A図乃至12D図に関して説明する。第12A図に示すとお
り、境界画定領域180は表示窓182に見える部分内に２つ
の部分を有する。再び、表示窓182は４つの制限平面X
_min、X_max、Y_min、Y_maxによつて画定される。領域180は
X_min及びY_minと交差している。ユーザが決定する入力デ
ータ・ストリームは次のように与えられる。

辺 P1P2 辺 P3P4P5P6 辺 P7P8P1 辺 P7P6 最初に、制限平面は主クリッピング・ルーチンによつて
X_minに決定される。平面がこのように決定されて、入力
データが第6A図及び6B図のクリッピング・アルゴリズム
を通過すると、第12B図に示したようなクリップ後の画
定領域が得られる。簡単に説明すると、線分P1P2はX_min
と交差して、第１のクリップ点を生じ、その値が計算さ
れて出力され、レジスタCP1中に記憶される。従つて、
最初に出力される辺はP1P2′より成る。第２のクリップ
点は第２の入力辺の入力辺の線分P4P5がX_minの外挿部分
と交差する時に得られる。クリップ点P2′及びP4′は対
にされて、点P5とともに辺開始コマンドによつて出力さ
れる。図示されたように点P5はX_minの見える側にある。
アルゴリズムの次の通過によつて、出力される辺にP6が
加えられる。アルゴリズムの最初に戻って受取られる次
の入力辺P7P8P1はP8′及びP8″で２回制限平面と交差す
る。最初に、クリップ後の辺P7P8′が出力され、P8′は
対にさるべき２つのクリップ点の最初の点であるから、
レジスタCP1に記憶される。もう一回アルゴリズムを通
過することによつて、２のクリップ点P8″が得られ、前
のクリップ点P8′と対にされる。この時点でレジスタP2
中に記憶されている現在の頂点、今の例ではP1は平面の
見える側にあるので、多角形開始コマンドが出力に書込
まれ、続いて頂点P8′、P8″及びP1が書込まれる。クリ
ップ後の境界画定領域180′を決定するために出力され
た最後の辺は、辺P7P6が処理される時に得られる。それ
は両頂点が制限平面の見える側にあるからである。

要約すると、単一平面によつてクリップされた境界画定
領域180′を表わすものとしてクリッピング・アルゴリ
ズムから出力される情報は次のようになる。

辺 P1P2′ 辺 P2′P4′P5P6 辺 P7P8′ 辺 P8′P8″P1 辺 P7P6 交点P8″とP8′間のＸ軸の余分な辺184は上述の排他的O
R機能を使用して、システム10のピクセル発生段階の境
界画定領域中に、FCPから自動的に消去される（第４
表）。それは頂点P2′とP4′間、P8″とP8′間に描かれ
る線分がP8″からP8′の間で重畳しているからである。

クリッピング動作を続けると、制限平面がY_minとして定
義し直されている主クリッピング・ルーチンに戻りがな
され、第6A図及び第6B図のクリッピング・アルゴリズム
が今度は単一の平面でクリップされた後の境界画定領域
180′を処理する。最初辺P1P2′はクリッピング動作を
不変のまま通過する。線分P2′P4′は制限平面Y_minとP
4″で交わり、この点は対にさるべき２つの交点の最初
のものとして識別され、レジスタCP1に記憶される。頂
点P4′、P5及びP6は制限平面Y_minの見えない側にあるの
で削除される。次の入力辺P7P8′はそのまま残される。
次の辺P8′P8″P1も同じである。辺P7P6がP6′で平面Y
_minと交差する時に、第２の交点が計算される。現時点
で評価中の現在点P2、即ち頂点P6は平面Y_minの見えない
側にあるので、クリップ点P6′が出力に書込まれる。こ
れに続いて辺開始コマンド、レジスタCP1中に記憶され
ている前のクリップ点P4″及び現在の交点P6′か出力さ
れる。このようにして２つの平面でクリップされた境界
画定領域180″は次のように表わされる（第12C図）。

辺 P1P2′ 辺 P2′P4″ 辺 P7P8′ 辺 P8′P8″P1 辺 P7P6′ 辺 P4″P6′ この場合も、交点P8″と、P8′間のX_min上の余分な辺18
4′は、上述のようにピクセル発生段階の境界画定フエ
イズ中にFCPから除去される。即ち、頂点P2′とP4′間
の線分の発生によつて頂点P8′と頂点P8′も結ばれる
が、辺８′P8″P1のための接続線の発生する際に線18
4′は２回描かれるので、画定フエイズの排他的OR機能
で線184′が消去される（第12D図）。

上述のことから、本発明は上述の目的を完全に満足する
ことが明らかである。本発明の線分境界画定領域のクリ
ッピング方法は、クリップさるべき境界画定領域に対応
する、データの連続的もしくは不連続的な辺を処理でき
る。さらに本発明の方法は、不連続的に提示されるデー
タを処理できる従来のクリッピング方法に比してより少
ないハードウエアしか必要としない。さらに、本発明の
余分な辺削除方法は、システムのパホーマンスを劣化す
ることなく、望ましくない線分を消去する。

上述のパイプライン実施例の外に、本発明のクリッピン
グ方法は非エントラント型の多角形クリッピング方法と
しても使用でき、又異なる余分な辺削除方法とともに使
用できる。同じく、本発明の余分な辺削除方法は異なる
境界画定領域クリッピング・アルゴリズムと使用でき
る。

F.発明の効果 本発明に従えば、連続的もしくは不連続的に提示される
辺を処理することができる境界画定領域のクリッピング
方法が与えられる。

【図面の簡単な説明】

第１図は、本発明に従う３次元パイプライン・クリッピ
ング方法の主ルーチンの流れ図である。 第２図は上位コンピユータと本発明が取人れられた図形
表示システム間の相互関係を示すブロック図である。 第３図は、第２図の図形表示システムの詳細なブロック
図である。 第4A−4C図は、蘭表面の基本要素を表示窓によつてクリ
ッピングする段階を図形的に示した図である。 第5A−5D図は、クリッピング・アルゴリズムによつて遂
行される、４つの基本的なクリッピング動作を図形的に
示した図である。 第6A−6B図は、本発明のクリッピング方法の流れ図であ
る。 第7A−7B図は、本発明に従うＸ軸でクリップ後の余分な
辺の削除方法を図形的に示した図である。 第8A−8B図は、本発明に従うYI_max軸でクリップ後の余
分な辺の削除方法を図形的に示した図である。 第9A−9B図は、本発明に従うY_min軸でクリップ後の余分
な辺の削除方法を図形的に示した図である。 第10A−10C図は、線分境界画定領域をＺ軸平面によつて
クリップした後に発生される余分な線の独特な特徴を図
形的に示した図である。 第11A−11C図は、本発明に従う単一平面による線分境界
画定領域クリッピング方法の実施例を図形的に示した図
である。 第12A−12D図は、本発明に従う２平面による線分境界画
定領域クリッピング方法の実施例を図形的に示した図で
ある。 10……図形表示システム、12……アプリケーション・プ
ログラム、13……上位コンピユータ、14……アプリケー
ション・データ構造、20……上位通信インターフェイ
ス、22……システム制御プロセッサ、24……システム・
メモリ、26……表示プロセッサ、28……ベクトル・ゼネ
レータ、29……領域充填プロセッサ、30……ビデオ・ピ
クセル・メモリ、31……充填制御平面及び境界平面、32
……表示モニク

───────────────────────────────────────────────────── フロントページの続き (72)発明者 リチヤード・アンソニイ・マリノ アメリカ合衆国ニユーヨーク州キングスト ン、ロビンズ・レーン30番地 (72)発明者 テレンス・ウエレース・リンドグレン アメリカ合衆国マサチユーセツツ州リツト ルトーン、スパーテン・アロー12番地

Claims (1)

【特許請求の範囲】
1. 【請求項１】図形が境界画定領域によつて定義され、直
   交するＸ軸、Ｙ軸の表示窓上に表示されるコンピユータ
   図形表示システムにおいて、上記境界画定領域を定義す
   る辺の組をクリッピングおよび領域充填プロセスを通し
   て処理し、上記領域の見える側と見えない側とを仕切る
   制限平面に対して上記境界画定領域をクリップし、クリ
   ップされた線分の内余分な線分を除去する方法であっ
   て、 （ａ）上記境界画定領域の１辺が上記制限平面と交差す
   る点を決定し、 （ｂ）上記交差する点に対応するデータを記憶し、 （ｃ）上記交差する点の決定を示すフラグをセットし、 （ｄ）上記境界画定領域の次の辺が上記制限平面と交差
   する点を決定し、 （ｅ）上記フラグを調べて該フラグがセットされている
   ならば上記（ａ）で決定された点および上記（ｂ）で決
   定された点を対となし、 （ｆ）上記フラグをリセットし、 （ｇ）上記境界画定領域の辺のすべてが上記制限平面と
   の交差に関して調べられるまで上記（ａ）ないし（ｆ）
   の処理を繰り返し、 （ｈ）上記各対の点を結ぶ線分を決定し、該線分が同じ
   場所で偶数回重なる部分を有するとき該部分を除去す
   る、 処理段階から成る方法。