JPH0785290A

JPH0785290A - グラフィック多角形をクリップ領域にクリップする方法および装置

Info

Publication number: JPH0785290A
Application number: JP6165257A
Authority: JP
Inventors: Chandrasekhar Narayanaswami; チャンドラセクハール・ナラヤナスワミ
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1993-09-02
Filing date: 1994-07-18
Publication date: 1995-03-31
Anticipated expiration: 2015-04-10
Also published as: EP0642103A3; US5613052A; EP0642103A2; JP3030206B2

Abstract

(57)【要約】【目的】複数の頂点と接続辺とによって定義されたグ
ラフィック多角形をクリップ領域にクリップするための
方法において、交差に関する不必要な計算を避ける。【構成】表示すべき多角形のどの頂点を放棄できるか
を計算し、放棄されなかった頂点に対してのみ少なくと
も一つのカラー・ファクタを計算するステップと、クリ
ップ領域境界と交差するすべての辺の上の境界頂点を計
算し、それらに対する少なくとも一つのカラー・ファク
タを計算するステップと、上記計算されたカラー・ファ
クタに従って上記頂点を表示するステップとを含む。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、コンピュータ・グラフ
ィックス・システムに関し、特に多角形をより効率良く
クリップするための方法および装置に関するものであ
る。

【０００２】

【従来の技術】コンピュータ・グラフィックス・システ
ムでは、２次元および３次元のグラフィック画像を２次
元のディスプレイ上に表示することが望まれる。典型的
には、このような画像は、多角形の集合としてメモリに
格納される構成体あるいはイメージである。そしてディ
スプレイ上に画像を生成するため、上記多角形は、典型
的には計算量の多い処理によって描画される。しかし、
表示すべき画像の一部が、ディスプレイ上のウインドウ
またはディスプレイ自身によって与えられる視野の外に
出る場合がある。このようなときには、描画の際、画像
および画像を構成する多角形をクリップすることが望ま
しく、それによって計算量を低減し、描画速度を増すこ
とができる。

【０００３】多角形クリッピングとは、クリップ領域と
呼ばれる領域の外にある多角形の部分を除去する処理の
ことである。一つの多角形は一般に頂点Ｐ（０），Ｐ
（１），・・・，Ｐ（ｎ−２），Ｐ（ｎ−１）の集合と
して特定される。ここでｎは多角形の頂点の数である。
多角形の頂点は、多角形の内部が、連続する頂点によっ
て形成される辺の左側にあるということで特定される。
各頂点Ｐ（ｉ）は、適当な座標空間におけるその位置Ｖ
（ｉ）と、ここでカラー・ファクタと呼ぶ関数ｆ（Ｖ
（ｉ））とによって表される。カラー・ファクタは各頂
点において評価される関数であり、後に色（灰色を含
む）変数（光の強さ、熱特性、湿度ファクタなど）とし
て表示される。カラー・ファクタは色に変換することが
できるものであり、モデリングに有用である（例えば、
簡単な明るさのモデリングやより複雑な気象モデリン
グ）。上記関数、すなわちカラー・ファクタｆ（Ｖ
（ｉ））は、その評価に必要な計算資源のため、一般に
クリッピング技術の開始時には評価されず、必要な場合
にのみ評価されるのが一般的である。

【０００４】関数、すなわちカラー・ファクタの補間
は、位置Ｖ（ｋ）において新たに生成された頂点Ｐ
（ｋ）での関数、すなわちカラー・ファクタの値を計算
するという処理である。関数、すなわちカラー・ファク
タの補間は、一般に多角形とクリップ領域の境界との交
点においてクリップするときに実行される。典型的に
は、関数、すなわちカラー・ファクタの補間は、ｆ（Ｖ
（ｋ））に関して、Ｖ（ｉ），ｆ（Ｖ（ｉ）），Ｖ
（ｊ），ｆ（Ｖ（ｊ）），ならびにＶ（ｋ）が既知のと
き可能である。

【０００５】

【発明が解決しようとする課題】従来のグラフィックス
・パイプラインでは、多角形の全頂点の明るさの計算
（関数補間の一例）はクリッピングに先だって行われ
る。その結果、多角形がクリップ領域の内部にない場合
にも明るさの計算は実行され、計算資源の無駄が生じ
る。

【０００６】

【課題を解決するための手段】本発明は、複数の頂点と
接続辺とによって定義されたグラフィック多角形をクリ
ップ領域にクリップする方法において、表示すべき多角
形のどの頂点を放棄できるかを計算し、放棄されなかっ
た頂点に対してのみ少なくとも一つのカラー・ファクタ
を計算するステップと、クリップ領域境界と交差するす
べての辺の上の境界頂点を計算し、それらに対する少な
くとも一つのカラー・ファクタを計算するステップと、
上記計算されたカラー・ファクタに従って上記頂点を表
示するステップとを含んでいる。さらに、本発明は、複
数の頂点と接続辺とによって定義されたグラフィック多
角形をクリップ領域にクリップする装置において、表示
すべき多角形のどの頂点を放棄できるかを計算し、放棄
されなかった頂点に対してのみ少なくとも一つのカラー
・ファクタを計算する手段と、クリップ領域境界と交差
するすべての辺の上の境界頂点を計算し、それらに対す
る少なくとも一つのカラー・ファクタを計算する手段
と、上記計算されたカラー・ファクタに従って上記頂点
を表示する手段とを備えている。

【０００７】

【実施例】この開示は改良したクリップ技術を記述した
ものである。望ましい実施例において、このクリップ技
術では、以下に述べるように、単純受容あるいは単純排
除したケースに関しては必ずしも交点を計算する必要が
ない。単純排除あるいは単純受容しなかったケースに関
しては、この技術では、必ずしも全頂点に対する関数、
すなわちカラー・ファクタを計算する必要がない。

【０００８】図１は、本発明の望ましい実施例で用いる
典型的なディジタル・コンピュータ１００のブロック図
である。このコンピュータは、入力装置（一つまたは複
数）１３０および出力装置（一つまたは複数）１４０を
接続したコンピュータ・ボックス１０５内に、メモリ１
２０およびハード・ディスク１２５に接続したメイン・
プロセッサ（一つまたは複数）１１０を含んでいる。メ
イン・プロセッサ１１０は単一のプロセッサであって
も、あるいは複数のプロセッサであってもよい。入力装
置１３０は例えばキーボード、マウス、タブレット、あ
るいはその他の入力装置である。出力装置１４０は、例
えばテキスト・モニタ、プロッタ、あるいはその他の出
力装置である。磁気ディスケットやコンパクト・ディス
クなどの、コンピュータが読むことができ、取り外し可
能なメディア１９０は、ディスク・ドライブあるいはＣ
Ｄ−ＲＯＭ（コンパクト・ディスク−読み出し専用メモ
リ）などの入力／出力（Ｉ／Ｏ）装置１８０に挿入する
ことができる。データは、取り外し可能メディアに対し
て、Ｉ／Ｏ装置により、Ｉ／Ｏ装置コントローラ１７０
の制御のもとで読み書きされる。Ｉ／Ｏ装置コントロー
ラは、バス１６０を通じてメイン・プロセッサと通信す
る。メイン・メモリ１２０、ハード・ディスク１２５、
ならびに取り外し可能メディア１９０はすべて、メイン
・プロセッサ１１０による処理のためのデータを格納す
るためのメモリと呼ぶ。

【０００９】メイン・プロセッサはまた、グラフィック
ス・ディスプレイなどのグラフィックス出力装置（一つ
または複数）１５０にグラフィックス・アダプタ２００
を通じて接続することができる。グラフィックス・アダ
プタ２００はメイン・プロセッサ１１０からのグラフィ
ックスに応じた命令をバス１６０より受け取る。そして
グラフィックス・アダプタはこれらの命令を、グラフィ
ックス・アダプタ・メモリ２３０に接続されたグラフィ
ックス・アダプタ・プロセッサ（一つまたは複数）２２
０により実行する。グラフィックス・アダプタのグラフ
ィックス・プロセッサは上記命令を実行し、そして上記
命令にもとづいてフレーム・バッファ（一つまたは複
数）２４０を更新する。グラフィックス・プロセッサ２
２０は、特定の基本的なグラフィックスのタイプを描画
するための特別のハードウェアを含んでいてもよい。フ
レーム・バッファ２４０は、グラフィックス出力装置に
表示するための、すべてのピクセルのデータを含んでい
る。ＲＡＭＤＡＣ（ランダム・アクセス・メモリＤ／Ａ
変換器）２５０は、フレーム・バッファに格納されたデ
ィジタル・データを、グラフィックス・ディスプレイ１
５０に与えるためのＲＧＢ信号に変換し、メイン・プロ
セッサが出力する所望のグラフィックスを描画する。

【００１０】図２は、ホスト・コンピュータおよびグラ
フィックス・アダプタがグラフィックス機能を実施する
ために典型的に使用するコードの層を示すブロック図で
ある。ＵＮＩＸなどのオペレーティング・システム３０
０によってホスト・コンピュータの基本的な制御が行わ
れる。オペレーティング・システム３００にはオペレー
ティング・システム・カーネル３１０が結合されてお
り、それによってハードウェアに強く依存するタスクが
オペレーティング・システムのために行われる。オペレ
ーティング・システム・カーネルはホスト・コンピュー
タのマイクロコード３２０と直接コミュニケーションす
る。ホスト・コンピュータ・マイクロコードは、ホスト
・コンピュータ・プロセッサによって実行される主要な
命令の集合である。オペレーティング・システム３００
にはグラフィックス・アプリケーション３３０，３３２
が結合されている。このグラフィックス・アプリケーシ
ョン・ソフトウェアとしては、例えばシリコン・グラフ
ィックのＧＬや、ＩＢＭのｇｒａＰＨＩＧＳ、ＭＩＴの
ＰＥＸなどを用いることができる。このソフトウェア
は、２次元あるいは３次元のグラフィックスの基本的な
機能を与えるものである。グラフィックス・アプリケー
ション３３０，３３２はグラフィックス・アプリケーシ
ョンＡＰＩ（アプリケーション・プロセッサ・インタフ
ェース）３４０，３４２にそれぞれ結合されている。Ａ
ＰＩは計算量の多いタスクの多くをグラフィックス・ア
プリケーションのために行い、また、グラフィックス・
アダプタのためのデバイス・ドライバなどのグラフィッ
クス・ハードウェアに近いソフトウェアと、アプリケー
ション・ソフトウェアとの間のインターフェースとして
機能する。例えば、ＡＰＩ３４０，３４２はＧＡＩ（グ
ラフィックス・アプリケーション・インターフェース）
３５０，３５２とそれぞれコミュニケーションすること
ができる。ＧＡＩは、アプリケーションＡＰＩとグラフ
ィックス・アダプタ・デバイス・ドライバー３７０との
インターフェースとして機能する。いくつかのグラフィ
ックス・システムでは、ＡＰＩはＧＡＩの機能も果た
す。

【００１１】グラフィックス・アプリケーション、ＡＰ
Ｉ、ならびにＧＡＩは、オペレーティング・システムお
よびデバイス・ドライバによって一つの処理と見なされ
る。すなわち、グラフィックス・アプリケーション３３
０，３３２、ＡＰＩ３４０，３４２、ならびにＧＡＩ３
５０，３５２は、オペレーティング・システム３００お
よびデバイス・ドライバ３７０によってそれぞれ処理３
６０，３６２と見なされる。これらの処理は、オペレー
ティング・システム・カーネルが処理に割り当てた処理
識別子（ＰＩＤ）にもとづき、オペレーティング・シス
テムおよびデバイス・ドライバによって識別される。処
理３６０，３６２には、例えば２つの別のウインドウに
おいて一つのプログラムを２回実行するような場合に
は、同一のコードを用い、それを同時に２回実行しても
よい。ＰＩＤは同一のコードの個別の実行を区別するた
めに用いられる。

【００１２】デバイス・ドライバはグラフィックス・カ
ーネルであり、それはオペレーティング・システム・カ
ーネル３１０を拡張したものである。グラフィックス・
カーネルは、グラフィックス・アダプタ３８０のマイク
ロコードと直接コミュニケーションを行う。多くのグラ
フィックス・システムにおいては、ＧＡＩあるいはＧＡ
Ｉ層が使用されない場合のＡＰＩは、デバイス・ドライ
バに初期リクエスト命令を送ることによって、アダプタ
・マイクロコードへの直接アクセスをリクエストするこ
とができる。さらに、多くのグラフィックス・システム
では、アダプタ・マイクロコードも、デバイス・ドライ
バに初期リクエスト命令を送ることによって、ＧＡＩあ
るいはＧＡＩが使用されない場合のＡＰＩに直接アクセ
スをリクエストすることが可能である。これらの処理は
以下では共に直接メモリ・アクセス（ＤＭＡ）と呼ぶ。
ＤＭＡは典型的には、大きいデータ・ブロックを伝達す
る場合に用いられる。ＤＭＡでは、ＤＭＡをセットアッ
プするためのデバイス・ドライバーに対する初期リクエ
ストを別にして、ディスプレイ・ドライバーを通る必要
がなくなるので、ホスト・コンピュータとアダプタとの
間のデータ伝送を速く行うことができる。いくつかのケ
ースでは、アダプタ・マイクロコードはコンテクスト・
スイッチングを用い、それによってアダプタ・マイクロ
コードはそれが使用しているカレント・アトリビュート
を置き換えることができる。コンテクスト・スイッチン
グは、アダプタ・マイクロコードが、それが現在用いて
いるものと異なるアトリビュートを使用するグラフィッ
クス・アプリケーションから命令を受けなければならな
い場合に用いられる。コンテクスト・スイッチは、典型
的には、アトリビュートの変化を認識するデバイス・ド
ライバによって起動される。

【００１３】ブロック３００〜３４０はソフトウェア・
コードの層であり、それらは典型的には、使用されてい
るグラフィックス・アダプタの種類には依存しない。ブ
ロック３５０〜３８０は典型的には、使用されているグ
ラフィックス・アダプタの種類に依存するソフトウェア
・コードの層である。例えば、グラフィックス・アプリ
ケーション・ソフトウェアによって異なるグラフィック
ス・アダプタが用いられるような場合、新たなＧＡＩ、
グラフィックス・カーネル、ならびにアダプタ・マイク
ロコードが必要となる。また、ブロック３００〜３７０
は典型的にはホスト・コンピュータ上にあり、ホスト・
コンピュータによって実行される。しかし、アダプタ・
マイクロコード３８０は典型的にはグラフィックス・ア
ダプタ上にあり、それによって実行される。しかし、い
くつかのケースでは、アダプタ・マイクロコードは、グ
ラフィックス・アダプタの初期化の際に、ホスト・コン
ピュータによってグラフィックス・アダプタにロードさ
れる。

【００１４】典型的なグラフィックス・システムでは、
ユーザがグラフィックス・アプリケーションに対して、
２次元あるいは３次元のモデルよりイメージを構成する
よう命令する。ユーザは最初、光源の位置および種類を
選択する。次にユーザはアプリケーション・ソフトウェ
アに命令して、予め定義された、あるいはユーザが定義
したオブジェクトの集合より所望のモデルを構築させ
る。各オブジェクトは、オブジェクトを表現する、一つ
または複数の同平面描画基本要素を含むことができる。
例えば、多数の三角形などの描画基本要素の集合を、オ
ブジェクトの表面を定義するために用いることができ
る。ユーザは次にモデルを見るために、ウインドウ内で
パースペクティブを与え、それによって所望のイメージ
を定義する。その後、アプリケーション・ソフトウェア
は、オブジェクトを表現する描画基本要素をアダプタ・
マイクロコードに対し、ＡＰＩ、ＧＡＩ、ならびにデバ
イス・ドライバ（ＤＭＡを使用しない場合）を通じて送
り、上記モデルからのイメージの描画を開始する。アダ
プタ・マイクロコードは次に、ウインドウ内で見えない
描画基本要素をクリップし（すなわち非使用とし）、そ
して残った描画基本要素を、ユーザにより与えられたパ
ースペクティブからの可視ピクセルとし、グラフィック
ス・ディスプレイ上にイメージを描画する。ピクセルは
その後、３次元モデルの場合にはしばしばデプス（深
さ）・バッファを用いて、フレーム・バッファにロード
される。このステップは、含まれる描画基本要素、変
数、ならびにピクセルの数が多いため、計算量の多いも
のとなっている。フレーム・バッファに格納され、また
グラフィックス・ディスプレイに表示された結果として
のイメージは、ピクセルがどの描画基本要素あるいはオ
ブジェクトから得たものかなどの情報を一般には含んで
いない。従って、ウインドウ、ユーザのパースペクティ
ブ、モデル、明るさなどが変更された場合には、イメー
ジは一部または全体が再描画されなければならない。

【００１５】望ましい実施例では、アダプタ・フレーム
・バッファに近いアダプタ・マイクロコードなどの多く
の位置において、クリッピング技術を用いることができ
よう。このアプローチはまた、比較的高速であり、そし
て実施が非常に容易であろう。また、このクリッピング
技術は、描画イメージが、描画される前または後に、グ
ラフィックス・アダプタ（データ・バックアップをグラ
フィックス・アプリケーション・ソフトウェアに渡す）
によってシステム・メモリにも格納されるグラフィック
ス・アプリケーション・ソフトウェアにおいて適用でき
よう。このアプローチでは、低速となるが、既存のグラ
フィックス・アダプタにおいて本技術を用いることが可
能であろう。このクリッピング技術はグラフィックス・
アダプタ・プロセッサのハードウェアにおいても実施で
きよう。この場合には、極めて高速となるが、特別のハ
ードウェアが必要となる。このアプローチでは、グラフ
ィックス・アダプタによって表示されるべき基本要素の
クリッピングを高速に行えることになる。当業者にとっ
て明らかなように、本技術は、ホスト・コンピュータあ
るいはグラフィックス・アダプタ内の他の多数の位置に
おいて用いることができよう。

【００１６】簡単のため、２次元の場合のクリッピング
技術についてまず説明する。２次元の技術における基本
概念は、以下に示すように３次元にも適用できる。標準
のクリップ領域は望ましくは正規化したクリップ領域で
あり、領域｛−１．０≦ｘ≦１．０｝および｛−１．０
≦ｙ≦１．０｝（および３次元の場合には｛−１．０≦
ｚ≦１．０｝）によって定義される。この領域は、ある
固定されたサイズのクリップ領域に対する設計を行う場
合、クリッピング・ハードウェアを最適化できるので、
広く用いられている。他のクリップ領域に対するクリッ
ピングが必要なときは、クリップ領域および多角形を標
準クリッピング空間に変換し、その後、クリッピングの
結果を変換し直して所望の結果を得ればよい。しかし、
非標準クリップ領域や長方形クリップ領域であっても、
ここに示す技術に関して概念上の問題は一切生じない。

【００１７】図３は、多角形の単純受容および単純排除
のケースを示すフローチャートである。すなわち望まし
い実施例では、最初にすべての多角形が調べられ、それ
らが単純受容できるか、あるいは単純排除できるかが判
定される。その結果、計算資源の使用の低減が可能とな
る。もし多角形が単純受容あるいは単純排除されなかっ
た場合には、その多角形は、本発明のより計算量の多い
技術の対象となる。ただし、本発明は、多角形をすべて
単純排除あるいは単純受容することを要求するものでは
ない。

【００１８】第１のステップ４００では、多角形の頂点
のそれぞれに４ビットの領域コードが割り当てられる。
全２次元空間は、図４に示すようにクリップ領域の境界
によって９つの非重複領域に分割される。これらの領域
のそれぞれには、図に示すような、それぞれ異なる４ビ
ットの領域コード（Ｃ３Ｃ２Ｃ１Ｃ０）が与えら
れる。以下では、２つの１を含む４つの領域はコーナー
領域と呼ぶ。また、１を１つだけ含む４つの領域は中間
領域、１つだけの１を含まない領域は中心領域と呼ぶ。
クリップ領域の境界線の交点はコーナー頂点と呼ぶ。多
角形の頂点のコードは、それが位置する領域のコードと
同じである。望ましい実施例では、頂点の領域コード
は、ｘ，ｙ座標を用いて以下に示す簡単なテストによっ
て素早く判定することができる。

【００１９】ｘ＜−１．０なら、Ｃ３＝１そうでない
なら、Ｃ３＝０ｘ＞−１．０なら、Ｃ２＝１そうでないなら、Ｃ２＝
０ｙ＜−１．０なら、Ｃ１＝１そうでないなら、Ｃ１＝
０ｙ＞−１．０なら、Ｃ０＝１そうでないなら、Ｃ０＝
０多角形を２次元の標準クリップ領域にクリップする場
合、いくつかのケースが生じる。それらは、単純受容、
単純排除、ならびにその他のケースである。このような
分類は本発明の説明を簡単なものとするためのものであ
る。本発明では、必要に応じてケースを切り換えること
によって、すべてのケースを扱う。以下に、各ケースに
ついて詳しく説明する。

【００２０】図５に示すように、多角形全体がクリップ
領域内にある場合には、その多角形は全体が単純受容さ
れる。この状態は、多角形のすべての頂点に関して領域
コードが０かどうかを判定することによって検出するこ
とができる。図６に、全体が中心領域の外側の中間領域
あるいはコーナー領域にある多角形を示す。これらの多
角形はすべて単純排除でき、交点を計算する必要がな
く、また関数、すなわちカラー・ファクタの評価も不要
である。この状態は、すべての頂点が同一の領域コード
であり、それらがゼロでないということの判定によって
検出できる。

【００２１】ステップ４１０では、多角形の連続する頂
点のすべての各対に関して領域コードの排他的論理和が
とられ、辺が領域の境界と交わるかどうかが判定され
る。ステップ４２０では、その結果がゼロ（辺が領域の
境界と交わらないことを示す）か否かが判定される。ス
テップ４２０の結果がイエスの場合、ステップ４３０に
おいて、多角形のすべての頂点の領域コードが選択され
る。すなわち、任意数の頂点の領域コードの論理和がと
られ、選択される。ステップ４４０では、選択処理の結
果がゼロ（多角形は、全体がクリップ領域内にあること
を示す）に等しいか否（多角形全体がクリップ領域以外
の領域内にあることを示す）かが判定さる。ステップ４
４０の結果がイエスの場合には、ステップ４５０におい
て、多角形はクリップ・ウインドウ内にあるとして単純
受容される。単純受容の場合には、頂点および辺はすべ
て完全にクリップ領域内にあるので、交点の計算は不要
である。従って、すべての頂点の関数、すなわちカラー
・ファクタ（必要なら、明るさの計算を含む）が、次の
多角形に移るまえに評価される。ステップ４４０の結果
がノーの場合には、ステップ４６０において、多角形は
まったくクリップ領域内にはないとして単純排除され
る。その場合には、交点の計算は不要であり、また頂点
における関数、すなわちカラー・ファクタ（明るさ、熱
特性など）の評価も不要である。その後、処理はクリッ
プすべき次の多角形に移る。

【００２２】図７に、単純排除される他のいくつかのケ
ースを示す。これらの多角形は、クリップ境界の一つの
側部にあり、そしてクリップ領域の外にある。ステップ
４２０の結果がノーの場合、ステップ４７０において、
すべての頂点に関する領域コードの論理積がとられる。
ステップ４８０では、論理積をとった領域コードの中に
１が一つだけあるかどうかが判定される。判定結果がイ
エスの場合には、多角形はステップ４９０において、多
角形はクリップ領域にはまったく入っていないとして、
単純排除することができる。その結果、交点は計算する
必要がなく、また頂点における、明るさなどの関数の評
価も不要である。その後、処理はクリップすべき次の多
角形に移る。しかし、ステップ４８０で、論理積をとっ
た領域コードの中に単一の１がないと判定された場合に
は、他のケースを扱うため、処理は図１５〜図１８に移
る。

【００２３】頂点の数が４を大きく上回る場合には、多
角形の制限ボックスを最初にクリップすることが有用で
あろう。多くの場合、多角形の制限ボックスは、すでに
行われた処理の結果として、グラフィックス・パイプラ
インを通じて得られている。その制限ボックスが単純受
容される場合には、多角形も単純受容されることにな
る。従って、その場合にはクリップ処理は完全にディス
エーブルされる。多角形の制限ボックスが単純排除され
た場合には、多角形も単純排除されることになる。従っ
て、その場合には多角形は全体が放棄することができ
る。Ｂ（０），Ｂ（１），Ｂ（２），Ｂ（３）を長方形
の制限ボックスとする。ｉ＝０，１，２，３のとき、い
かなるｉに対しても、［領域コードＢ（ｉ）ＸＯＲ領域
コードＢ（ｉ＋１）］ＯＲ［領域コードＢ（ｉ＋１）Ｘ
ＯＲ領域コードＢ（ｉ＋２）］の中に２つまたはそれ以
上の１が存在するなら、上記ボックスはクリップ領域の
コーナー頂点を含んでいる。多角形の境界がクリップ領
域のコーナー頂点を含んでいない場合には、制限ボック
スのいかなる部分もクリップ領域の内部には有りえな
い。従って、この場合には、多角形全体を放棄すること
ができる。

【００２４】図８に、本発明の望ましい実施例にもとづ
いて、単純受容あるいは単純排除されない多角形の他の
いくつかのケースを示す。ケース（ａ）は、多角形の一
部がクリップ領域の内部にあり、また一部が外部にある
場合の簡単なケースを示している。多角形のクリップし
た部分は、単一に接続された多角形である。ケース
（ｂ）はケース（ａ）と同様であるが、多角形のクリッ
プした部分が複数接続となっている。ケース（ｃ）は、
多角形の頂点はひとつもクリップ領域内にはなく、そし
て多角形がクリップ領域を被っている場合を示してい
る。ケース（ｄ）は、多角形の頂点はひとつもクリップ
領域内にはなく、そして多角形のどの部分もクリップ領
域内にない場合を示している。

【００２５】これらのケースでは、コーナー頂点を付加
する必要があるので、処理は難しいものとなる。あるコ
ーナー頂点が多角形の内部にある場合、そのコーナー頂
点は付加されなければならない。この判定は、コーナー
頂点から無限遠への垂直線あるいは水平線が多角形を奇
数回横断するかどうかを調べることによって行うことが
できる。図９に、クリップ領域のコーナー頂点のいくつ
かを取り囲む多角形を示す。垂直および水平境界Ｅ１〜
Ｅ４が、クリップ領域から多角形を通して延在して示さ
れている。上記線の多角形との交差にもとづけば、コー
ナーＳＥ，ＳＷは出力多角形に含まれなければならず、
一方、コーナーＮＥ，ＮＷは含まれるべきでない。この
判定も、入力多角形の頂点に関する領域コードを用いて
行うことができる。しかし、この方法では出力多角形の
コーナー頂点の正確な位置は簡単には判定できないの
で、この検出だけでは不十分であろう。重要なことは、
多角形の辺が、交差してコーナーを形成する境界の両方
と奇数回、交差すると判定されたとき、出力多角形に頂
点を挿入する必要があるということである。例えば、図
８のケース（ｃ）の場合、右下のコーナーは、Ｐ
（０），Ｐ（１），Ｐ（２）と進んだ後でのみ付加され
ることになる。さらに、この技術では既に付加されたコ
ーナー頂点を、後で除去する必要がある。例えば、図８
のケース（ｄ）の場合、Ｐ（０），Ｐ（１），Ｐ（２）
と進んだ後で、右上のコーナーが付加され、Ｐ（８），
Ｐ（９），Ｐ（０）と進んだとき、そのコーナーは除去
される。

【００２６】この問題は組み合せのアプローチによって
解決する。多角形の任意の２つの頂点を考える。頂点の
それぞれは９つの領域のいずれかに入っており、従っ
て、８１の異なる種類の辺がある（すなわち、辺を定義
する２つの頂点に対して、領域コードの８１の組み合せ
がある）。これらの８１の異なる種類の辺のうち、一つ
は単純受容され、８つは単純排除される。このようなケ
ースは、辺が完全に一つの領域内にあり、クリップ領域
の境界辺と交差しない場合である。この場合、望ましい
実施例では、コーナー検出論理はまったくディスエーブ
ルされる。

【００２７】残りの７２のケースは、辺がクリップ境界
と交差する場合である。これらのケースすべてに対して
コーナー検出論理はイネーブルされなければならない。
これらのケースの内の８つは、図１０に示すように分離
しており、水平辺および垂直辺が完全に共通となってい
る電気的ＣＡＤのアプリケーションでは、大幅なスピー
ドアップが可能となる。なお、このケースにおいて分離
されている辺はすべてが完全に水平あるいは垂直である
わけではない。

【００２８】残りの６４のケースは、辺がクリップ領域
の境界Ｅ１〜Ｅ４（図１１参照）と交差する際のその数
および種類にもとづいて分類される。この分類は、コー
ナー頂点検出処理を手助けするために行われる。頂点の
一つがクリップ領域内にある場合を除いて、辺の長さは
この分類においては無関係である。辺が境界のクリップ
領域側に入る場合、交差は境界に関するｉ（外→内）に
分類され、辺が境界の無限遠側に入る場合、交差は境界
に関するｏ（内→外）に分類される。一つを上回る数の
ｉ（外→内）交差がある場合、辺の開始頂点から最も遠
いものが保持される。一つを上回る数のｏ（内→外）交
差がある場合、辺の開始頂点から最も近いものが保持さ
れる。

【００２９】６４のケースのうち、１６のケースは図１
２に示す辺によってカバーされ、８つのケースは図１３
の辺によってカバーされる。そして、３２のケースは図
１４に示す辺によってカバーされる（図には２０のケー
スが示されているが、他の１２のケースは上記２０のケ
ースのいくつかのものの言い替えである）。

【００３０】図１１のケースでは、どの場合にも境界と
の単一の交差のみがある。図１２，図１３のケースで
は、どの場合にも正確に２つの交差があり、それらは共
にｉ（外→内）交差あるいはｏ（内→外）交差である。
図１４のケースでは、２つまたはそれを上回る数の交差
があり、それらのうちの少なくとも一つは、ｉ（外→
内）交差であり、少なくとも一つはｏ（内→外）交差で
ある。

【００３１】図１５〜図１９は、上述したケースを用い
た、多角形に関する頂点のクリッピングおよび頂点関
数、すなわちカラー・ファクタの評価のフローチャート
である。この技術は、上述した図３のもとですでに単純
受容あるいは単純排除されていない多角形に対して適用
することが望ましい。最初のステップ５００では、多角
形の現在の頂点Ｖに対して領域コードが割り当てられ
る。ステップ５１０では、頂点Ｖがクリップ領域の内部
にあるか否か（すなわち、頂点の領域コードが００００
に等しいかどうか）が判定される。頂点Ｖがクリップ領
域の内部にある場合には、ステップ５２０において、頂
点Ｖに対する頂点関数、すなわちカラー・ファクタが評
価される。例えば、頂点Ｖにおける明るさの計算を行う
ことになる。次にステップ５３０において、以前の頂点
Ｐがクリップ領域の内部にあるいか否かが判定される
（すなわち、頂点の領域コードが００００に等しいかど
うか）。この試験によって、多角形の最後の辺がクリッ
プ境界のいずれかと交差したかどうかが判定される。こ
れが処理される最初の頂点である場合には、答えはノー
となり、処理はステップ５４０に進む。また、多角形の
最後の辺が完全にクリップ領域内にある場合にはステッ
プ５３０の結果はイエスとなる。しかし、ステップ５３
０において、以前の頂点Ｐがクリップ領域の外にあった
場合には、処理は図１６に進む（この条件は、最後の辺
がクリップ領域の外側から内側に延びているとき成立す
る）。ステップ５４０では、頂点Ｖが多角形の最後の頂
点であるかどうかが判定される。判定結果がイエスの場
合には、多角形の処理は図１９に進み、現在の多角形に
対する処理は終了する。ノーの場合には、ステップ５５
０において、現在の頂点が出力される（すなわち、メモ
リなどに格納される）。ステップ５６０では、現在の頂
点Ｖが以前の頂点Ｐとして格納され、そして新しい現在
の頂点Ｖが処理の対象とされる。そして処理はステップ
５００に戻る。

【００３２】ステップ５１０において、頂点Ｖがクリッ
プ領域の内側にないと判定された場合には（すなわち、
頂点Ｖの領域コードが００００に等しくない）、処理は
ステップ５７０に進む。ステップ５７０では、以前の頂
点Ｐが現在の頂点Ｖと同じ領域内にあるかどうかが判定
される。判定結果がイエスの場合には、最後の辺は、ク
リップ領域以外のある領域内に完全に入っていることに
なり、単純排除されることになる。その場合、処理はス
テップ５７５に進む。ステップ５７５では、頂点Ｖが最
後の頂点かどうかが判定される。結果がイエスの場合に
は、処理は図１９に進み、イエスでない場合には処理は
上述したステップ５６０に進む。ステップ５７０におい
て現在の頂点Ｖおよび以前の頂点Ｐが異なる領域にある
と判定された場合には、処理はステップ５８０に進む。
ステップ５８０では、将来のステップのために、どのク
リップ境界が最後の辺と交差したかが判定される。クリ
ップ境界は、図９に示したように、両方の無限遠に延び
る２本の垂直および水平な線であり、クリップ領域を定
義するために用いられる。次に、ステップ５９０におい
て、以前の頂点がクリップ領域の内部にあるかどうかが
判定される。結果がイエスの場合、最後の辺はクリップ
領域の内側から外側に延びていることになる。ノーの場
合には、最後の辺はクリップ領域の外側から内側に延び
ていることになる。処理はその後、図１７，図１８にそ
れぞれ進む。

【００３３】図１６の処理は、クリップ領域の外側から
内側に延びる辺を扱うためのものであり、上述したステ
ップ５３０において起動される。最後の辺がクリップ領
域内に延びるため、最後の辺とクリップ領域の交差部に
おける交差頂点Ｉを決める必要がある。ステップ６００
において、関数（一つまたは複数；明るさなど）が以前
の頂点Ｐに対して評価される必要がある。ステップ６１
０では、以前の頂点Ｐと現在の頂点Ｖの位置およびそれ
らに対する関数に関する結果とにもとづいて、交差頂点
Ｉが生成され、辺の補間によって頂点に対する関数が評
価される。ステップ６２０では、辺が一つのクリップ境
界だけを横断するかどうかが判定される。結果がイエス
の場合には、コーナー頂点は生成する必要はない。その
結果、ステップ６３０において、上で計算された交差頂
点Ｉが出力され、処理は上述したステップ５７５に進
む。しかし、ステップ６２０において１を上回る数の境
界が横断されていた場合には、処理はステップ６４０に
進む。ステップ６４０では、最後の辺によってどのクリ
ップ境界が横断されたかが判定される。ステップ６５０
では、最後の辺によって横断されたクリップ境界より、
コーナー頂点Ｃの生成が必要がどうかが判定される。望
ましい実施例では、コーナー頂点は、多角形が垂直クリ
ップ境界および水平クリップ境界の両方を横断する場合
に生成される。コーナーが必要でない場合には、処理は
上述したステップ６３０に進む。コーナーが必要な場合
には、ステップ６６０において、コーナー頂点Ｃが生成
され、頂点に対する関数、すなわちカラー・ファクタが
三角補間によって評価され、そして頂点が出力される。
コーナー頂点Ｃの三角補間は、現在の頂点Ｖおよび二つ
の以前の頂点（三角形を与える）に対する関数、すなわ
ちカラー・ファクタを評価し、次に三角形よりコーナー
頂点Ｃに対して補間することにより行う。コーナーが生
成される場合にはいつも、それによって、以前に同一の
位置に生成されたコーナーは置き換えられるか、あるい
は消去されることになる。次に処理は上述したステップ
６３０に進む。

【００３４】図１７は、クリップ領域の内側から外側に
延びている辺を扱うための処理であり、上記ステップ５
９０において起動される。最後の辺はクリップ領域の外
側に進展しているので、最後の辺とクリップ領域との交
差部の交差頂点Ｉを決める必要がある。ステップ７００
において、関数、すなわちカラー・ファクタ（明るさ、
熱特性、湿度など）を現在の頂点Ｖに関して評価する必
要がある。ステップ７１０では、以前の頂点Ｐおよび現
在の頂点Ｖに対する、位置および関数に関する結果にも
とづいて、交差頂点Ｉが生成され、またその頂点に対す
る関数が辺補間によって評価される。ステップ７２０で
は、辺がクリップ境界を一度だけ横断するかどうかが判
定される。判定結果がイエスの場合には、コーナー頂点
を生成する必要はない。その結果、ステップ７３０にお
いて、上で計算した交差頂点Ｉが出力され、処理は上述
したステップ５７５に進む。一方、ステップ７２０にお
いて１を上回る数の境界が交差されていた場合には、処
理はステップ７４０に進む。ステップ７４０において、
どのクリップ境界が最後の辺によって横断されたが判断
される。ステップ７５０では、コーナー頂点Ｃを生成す
る必要があるかどうかが、最後の辺によって横断された
クリップ境界より判定される。望ましい実施例では、多
角形が垂直クリップ境界および水平クリップ境界の両方
を横断する場合に、コーナー頂点が生成される。コーナ
ーが必要ない場合には、処理は上述したステップ７３０
に進む。コーナーが必要な場合には、ステップ７６０に
おいて、コーナー頂点Ｃが生成され、その頂点に対する
関数が三角補間によって評価され、そして頂点が出力さ
れる。コーナー頂点Ｃの三角補間は、現在の頂点Ｖおよ
び２つの以前の頂点（三角形を与える）に対する関数、
すなわちカラー・ファクタを評価し、次に三角形よりコ
ーナー頂点Ｃに対して補間することにより行う。コーナ
ーが発生される場合にはいつも、それによって、以前に
同一の位置に発生されたコーナーは置き換えられるか、
あるいは消去されることになる。処理は次に、上述した
ステップ７３０に進む。

【００３５】図１８は、クリップ領域の外側の一つの領
域からクリップ領域の外側の他の領域に延びる辺を扱う
ための処理であり、上述したステップ５９０において起
動される。ステップ８００では、辺がクリップ境界を一
つだけ横断するかどうかが判定される。結果がイエスの
場合には、ステップ８１０において、コーナー頂点Ｃを
生成する必要があるかどうかが、最後の辺が横断したク
リップ境界より判定される。望ましい実施例では、多角
形が垂直クリップ境界および水平クリップ境界の両方を
横断する場合に、コーナー頂点が生成される。コーナー
が必要な場合には、ステップ８２０において、コーナー
頂点Ｃが生成され、その頂点に対する関数が三角補間に
よって評価され、そして頂点が出力される。コーナー頂
点Ｃの三角補間は、現在の頂点Ｖおよび２つの以前の頂
点（三角形を与える）に対する関数、すなわちカラー・
ファクタを評価し、次に三角形よりコーナー頂点Ｃに対
して補間することにより行う。コーナーが生成される場
合にはいつも、それによって、以前に同一の位置に発生
されたコーナーは置き換えられるか、あるいは消去され
ることになる。ステップ８２０においてコーナー頂点が
出力されると、あるいはステップ８１０においてコーナ
ーが必要ないと判定された場合には、処理は上述したス
テップ５７５に戻る。しかし、ステップ８００におい
て、１を上回る数の境界が横断されていた場合には、処
理はステップ８３０に進む。このステップにおいて、最
後の辺が水平境界だけ、あるいは垂直境界だけを横断す
るかどうかが判定される。結果がイエスの場合、ステッ
プ８４０において、コーナー頂点Ｃが必要かどうかが判
定される。コーナー頂点Ｃが必要な場合には、処理は上
述したステップ８２０に進み、一方、不要な場合には処
理は上述したステップ５７５に進む。ステップ８３０に
おいて最後の辺が水平境界および垂直境界の両方を横断
すると判定された場合には、処理はステップ８５０に進
み、最後の辺がクリップ領域を横断する可能性を扱う。
ステップ８５０において、最後の辺が水平境界および垂
直境界を横断する所で、交差頂点Ｉが生成される。ステ
ップ８６０において、これら２つの交差頂点がクリップ
領域内かどうかが判定される。判定結果がイエスの場合
には、ステップ８８０において、交差頂点Ｉの関数（明
るさなど）が辺補間を用いて評価され、２つの交差頂点
Ｉが出力され、そして処理は上述したステップ５７５に
進む。判定結果がノーの場合には、ステップ８７０にお
いて、コーナー頂点Ｃが必要かどうかが判定される。結
果がイエスの場合には処理は上述したステップ８２０に
進み、ノーの場合には処理は上記ステップ５７５に進
む。

【００３６】望ましい実施例では、交差は以下の三つの
ケースにおいて計算されることが明らかである。第１
は、以前の頂点がクリップ領域の中にあり、現在の頂点
がクリップ領域の外にある場合。第２は、以前の頂点が
クリップ領域の外にあり、現在の頂点がクリップ領域の
中にある場合。第３は、以前の頂点および現在の頂点が
共にクリップ領域の外にあり、辺の一部がクリップ領域
を通過する可能性がある場合。多角形の辺が図９の境界
Ｅ１〜Ｅ４の一つと交差する可能性がある場合には必ず
コーナー頂点の検出が行われる。

【００３７】３次元（３Ｄ）の場合でも基本概念は変ら
ない。主な差異は、３次元では、３次元空間が９ではな
く２７に分割され、コードワードが４ビットではなく６
ビットとなり、そして、コーナー頂点に加えて、多角形
の面と、クリップ領域の２つの境界面の交差線との交差
部における頂点を追加する必要があるということであ
る。

【００３８】当業者にとって明らかなように、本発明
は、並列処理システムを含むマルチプロセッサ・システ
ム、パイプライン処理システム、ならびにそれらの組み
合せに対して容易に応用できよう。例えば、複数のプロ
セッサによって、図１５〜図１９に示したフローチャー
トの各部を別々に扱うことができよう。

【００３９】本発明は、モザイク状にした多角形や、あ
るいは複数の頂点の間に複数の接続を有する多角形に対
しても適用することもできる。しかしその場合には、図
１５〜１９を参照して説明したように、頂点を順番に見
て各辺を扱うのではなく、他のアプローチを用いること
ができよう。例えば、各辺を個々にレビューして、辺に
対するクリップおよび関数に関する評価を行うことがで
きよう。さらに、各頂点をレビューして、その頂点ある
いはその頂点に結合された頂点がクリップ体の内部にあ
るかどうかを判定し、そしてクリップ領域を横断する辺
を評価することができよう。これらのアプローチもマル
チプロセッサ・システムによって容易に扱うことができ
る。

【００４０】以上、本発明について特定の実施例をもと
に詳しく説明したが、当業者にとって他の実施例も明か
であろう。例えば、コーナー頂点は、頂点がクリップ領
域に入る場合にのみ生成し、評価することができよう。

【００４１】まとめとして、本発明の構成に関して以下
の事項を開示する。（１）複数の頂点と接続辺とによって定義されたグラフ
ィック多角形をクリップ領域にクリップする方法におい
て、表示すべき多角形のどの頂点を放棄できるかを計算
し、放棄されなかった頂点に対してのみ少なくとも一つ
のカラー・ファクタを計算するステップと、クリップ領
域境界と交差するすべての辺の上の境界頂点を計算し、
それらに対する少なくとも一つのカラー・ファクタを計
算するステップと、前記計算されたカラー・ファクタに
従って前記頂点を表示するステップと、を含むことを特
徴とする方法。（２）どの頂点が放棄できるかを計算する前記ステップ
は、前記クリップ領域と交差する辺に接続された頂点に
対する少なくとも一つのカラー・ファクタの計算を含
む、上記（１）に記載の方法。（３）クリップ領域境界と交差するすべての辺の上の境
界頂点を計算する前記ステップは、前記境界頂点に対す
る少なくとも一つのカラー・ファクタを、前記辺に接続
された頂点に対してすでに計算されたカラー・ファクタ
による補間によって計算することを含む、上記（２）に
記載の方法。（４）前記クリップ領域内の辺の各点に対する少なくと
も一つのカラー・ファクタを、前記辺に接続された頂点
に対してすでに計算されたカラー・ファクタによる補間
によって計算するステップをさらに含む、上記（３）記
載の方法。（５）複数の頂点と接続辺とによって定義されたグラフ
ィック多角形をクリップ領域にクリップする装置におい
て、表示すべき多角形のどの頂点を放棄できるかを計算
し、放棄されなかった頂点に対してのみ少なくとも一つ
のカラー・ファクタを計算する手段と、クリップ領域境
界と交差するすべての辺の上の境界頂点を計算し、それ
らに対する少なくとも一つのカラー・ファクタを計算す
る手段と、前記計算されたカラー・ファクタに従って前
記頂点を表示する手段と、を備えることを特徴とする装
置。（６）どの頂点が放棄できるかを計算する前記手段は、
前記クリップ領域と交差する辺に接続された頂点に対す
る少なくとも一つのカラー・ファクタを計算する手段を
有する、上記（５）に記載の装置。（７）クリップ領域境界と交差するすべての辺の上の境
界頂点を計算する前記手段は、前記境界頂点に対する少
なくとも一つのカラー・ファクタを、前記辺に接続され
た頂点に対してすでに計算されたカラー・ファクタによ
る補間によって計算する手段を有する、上記（６）に記
載の装置。（８）前記クリップ領域内の辺の各点に対する少なくと
も一つのカラー・ファクタを、前記辺に接続された頂点
に対してすでに計算されたカラー・ファクタによる補間
によって計算する手段をさらに備える、上記（７）に記
載の装置。（９）複数の頂点と接続辺とによって定義されたグラフ
ィック多角形をクリップ領域にクリップするデータ処理
システムにおいて、データを処理する処理手段と、処理
すべきデータを格納する格納手段と、グラフィック・デ
ータを処理する前記処理手段に接続されたグラフィック
ス処理手段とを備え、前記グラフィックス処理手段は、ｉ）表示すべき多角形のどの頂点を放棄できるかを計算
し、放棄されなかった頂点に対してのみ少なくとも一つ
のカラー・ファクタを計算する手段と、 ii）クリップ領域境界と交差するすべての辺の上の境界
頂点を計算し、それらに対する少なくとも一つのカラー
・ファクタを計算する手段と、 iii ）前記計算されたカラー・ファクタに従って前記頂
点を表示する手段とを有する、ことを特徴とするデータ
処理システム。（１０）どの頂点が放棄できるかを計算する前記手段
は、前記クリップ領域と交差する辺に接続された頂点に
対する少なくとも一つのカラー・ファクタを計算する手
段を有する、上記（９）に記載のデータ処理システム。（１１）クリップ領域境界と交差するすべての辺の上の
境界頂点を計算する前記手段は、前記境界頂点に対する
少なくとも一つのカラー・ファクタを、前記辺に接続さ
れた頂点に対してすでに計算されたカラー・ファクタに
よる補間によって計算する手段を有する、上記（１０）
に記載のデータ処理システム。（１２）前記クリップ領域内の辺の各点に対する少なく
とも一つのカラー・ファクタを、前記辺に接続された頂
点に対してすでに計算されたカラー・ファクタによる補
間によって計算する手段をさらに備えた、上記（１１）
に記載のデータ処理システム。（１３）メモリに格納され、データ処理システムによっ
て実行でき、複数の頂点と接続辺とによって定義された
グラフィック多角形をクリップ領域にクリップするコン
ピュータ・プログラムの製品において、表示すべき多角
形のどの頂点を放棄できるかを計算し、放棄されなかっ
た頂点に対してのみ少なくとも一つのカラー・ファクタ
を計算する手段と、クリップ領域境界と交差するすべて
の辺の上の境界頂点を計算し、それらに対する少なくと
も一つのカラー・ファクタを計算する手段と、前記計算
されたカラー・ファクタに従って前記頂点を表示する手
段と、を備えることを特徴とするコンピュータ・プログ
ラム製品。（１４）どの頂点が放棄できるかを計算する前記手段
は、前記クリップ領域と交差する辺に接続された頂点に
対する少なくとも一つのカラー・ファクタを計算する手
段を有する、上記（１３）に記載のコンピュータ・プロ
グラム製品。（１５）クリップ領域境界と交差するすべての辺の上の
境界頂点を計算する前記手段は、前記境界頂点に対する
少なくとも一つのカラー・ファクタを、前記辺に接続さ
れた頂点に対してすでに計算されたカラー・ファクタに
よる補間によって計算する手段を有する、上記（１４）
に記載のコンピュータ・プログラム製品。（１６）前記クリップ領域内の辺の各点に対する少なく
とも一つのカラー・ファクタを、前記辺に接続された頂
点に対してすでに計算されたカラー・ファクタによる補
間によって計算する手段をさらに備える、上記（１５）
に記載のコンピュータ・プログラム製品。

【００４２】

【発明の効果】本発明の一つの長所は、その複雑さが、
現在の技術より、実際のフラックス（標準クリップ領域
の境界を横断する辺の数）に、より直接的に依存すると
いうことである。その結果、交差に関する不必要な計算
を避けることができる。

【図面の簡単な説明】

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

【図２】グラフィックス機能を実施するため、ホスト・
コンピュータおよびグラフィックス・アダプタが典型的
に使用するコードの層を示すブロック図である。

【図３】多角形の単純受容ケースおよび単純排除ケース
の決定を示すフローチャートである。

【図４】２次元空間におけるクリップ領域の、９つの非
重複境界を示す図である。

【図５】全体がクリップ領域内にある、単純受容される
多角形を示す図である。

【図６】全体が、クリップ領域の外側にある中間領域あ
るいは角領域内にある、単純排除される多角形を示す図
である。

【図７】単純排除され得る、他のいくつかの多角形を示
す図である。

【図８】本発明の望ましい実施例にもとづき、単純排除
あるいは単純受容されない、残りのいくつかの多角形の
ケースを示す図である。

【図９】クリップ領域のコーナー頂点のいくつかを取り
囲む多角形を示す図である。

【図１０】辺がクリップ領域と交わらない、２８の非単
純なケースを示す図である。

【図１１】辺がクリップ領域と交わらない、２８の非単
純なケースを示す図である。

【図１２】辺がクリップ境界を横断する、４８のケース
を示す図である。

【図１３】辺がクリップ境界を横断する、４８のケース
を示す図である。

【図１４】辺がクリップ境界を横断する、４８のケース
を示す図である。

【図１５】一つの多角形に対する、頂点のクリップおよ
び頂点関数の評価を示すフローチャートである。

【図１６】一つの多角形に対する、頂点のクリップおよ
び頂点関数の評価を示すフローチャートである。

【図１７】一つの多角形に対する、頂点のクリップおよ
び頂点関数の評価を示すフローチャートである。

【図１８】一つの多角形に対する、頂点のクリップおよ
び頂点関数の評価を示すフローチャートである。

【図１９】一つの多角形に対する、頂点のクリップおよ
び頂点関数の評価を示すフローチャートである。

【符号の説明】

１００ディジタル・コンピュータ１１０メイン・プロセッサ１２０メモリ１２５ハード・ディスク１３０入力装置１４０出力装置１５０グラフィックス・ディスプレイ１６０バス１７０Ｉ／Ｏコントローラ１８０Ｉ／Ｏ装置１９０取り外し可能なメディア２００グラフィックス・アダプタ２２０グラフィックス・アダプタ・プロセッサ２４０フレーム・バッファ２５０ランダム・アクセス・メモリＤ／Ａ変換器

Claims

【特許請求の範囲】

【請求項１】複数の頂点と接続辺とによって定義された
グラフィック多角形をクリップ領域にクリップする方法
において、表示すべき多角形のどの頂点を放棄できるかを計算し、
放棄されなかった頂点に対してのみ少なくとも一つのカ
ラー・ファクタを計算するステップと、クリップ領域境界と交差するすべての辺の上の境界頂点
を計算し、それらに対する少なくとも一つのカラー・フ
ァクタを計算するステップと、前記計算されたカラー・ファクタに従って前記頂点を表
示するステップと、を含むことを特徴とする方法。
【請求項２】どの頂点が放棄できるかを計算する前記ス
テップは、前記クリップ領域と交差する辺に接続された
頂点に対する少なくとも一つのカラー・ファクタの計算
を含むことを特徴とする請求項１記載の方法。
【請求項３】クリップ領域境界と交差するすべての辺の
上の境界頂点を計算する前記ステップは、前記境界頂点
に対する少なくとも一つのカラー・ファクタを、前記辺
に接続された頂点に対してすでに計算されたカラー・フ
ァクタによる補間によって計算することを含むことを特
徴とする請求項２記載の方法。
【請求項４】前記クリップ領域内の辺の各点に対する少
なくとも一つのカラー・ファクタを、前記辺に接続され
た頂点に対してすでに計算されたカラー・ファクタによ
る補間によって計算するステップをさらに含むことを特
徴とする請求項３記載の方法。
【請求項５】複数の頂点と接続辺とによって定義された
グラフィック多角形をクリップ領域にクリップする装置
において、表示すべき多角形のどの頂点を放棄できるかを計算し、
放棄されなかった頂点に対してのみ少なくとも一つのカ
ラー・ファクタを計算する手段と、クリップ領域境界と交差するすべての辺の上の境界頂点
を計算し、それらに対する少なくとも一つのカラー・フ
ァクタを計算する手段と、前記計算されたカラー・ファクタに従って前記頂点を表
示する手段と、を備えることを特徴とする装置。
【請求項６】どの頂点が放棄できるかを計算する前記手
段は、前記クリップ領域と交差する辺に接続された頂点
に対する少なくとも一つのカラー・ファクタを計算する
手段を有することを特徴とする請求項５記載の装置。
【請求項７】クリップ領域境界と交差するすべての辺の
上の境界頂点を計算する前記手段は、前記境界頂点に対
する少なくとも一つのカラー・ファクタを、前記辺に接
続された頂点に対してすでに計算されたカラー・ファク
タによる補間によって計算する手段を有することを特徴
とする請求項６記載の装置。
【請求項８】前記クリップ領域内の辺の各点に対する少
なくとも一つのカラー・ファクタを、前記辺に接続され
た頂点に対してすでに計算されたカラー・ファクタによ
る補間によって計算する手段をさらに備えることを特徴
とする請求項７記載の装置。
【請求項９】複数の頂点と接続辺とによって定義された
グラフィック多角形をクリップ領域にクリップするデー
タ処理システムにおいて、データを処理する処理手段と、処理すべきデータを格納する格納手段と、グラフィック・データを処理する前記処理手段に接続さ
れたグラフィックス処理手段とを備え、前記グラフィックス処理手段は、ｉ）表示すべき多角形のどの頂点を放棄できるかを計算
し、放棄されなかった頂点に対してのみ少なくとも一つ
のカラー・ファクタを計算する手段と、 ii）クリップ領域境界と交差するすべての辺の上の境界
頂点を計算し、それらに対する少なくとも一つのカラー
・ファクタを計算する手段と、 iii ）前記計算されたカラー・ファクタに従って前記頂
点を表示する手段とを有する、ことを特徴とするデータ処理システム。
【請求項１０】どの頂点が放棄できるかを計算する前記
手段は、前記クリップ領域と交差する辺に接続された頂
点に対する少なくとも一つのカラー・ファクタを計算す
る手段を有することを特徴とする請求項９記載のデータ
処理システム。
【請求項１１】クリップ領域境界と交差するすべての辺
の上の境界頂点を計算する前記手段は、前記境界頂点に
対する少なくとも一つのカラー・ファクタを、前記辺に
接続された頂点に対してすでに計算されたカラー・ファ
クタによる補間によって計算する手段を有することを特
徴とする請求項１０記載のデータ処理システム。
【請求項１２】前記クリップ領域内の辺の各点に対する
少なくとも一つのカラー・ファクタを、前記辺に接続さ
れた頂点に対してすでに計算されたカラー・ファクタに
よる補間によって計算する手段をさらに備えたことを特
徴とする請求項１１記載のデータ処理システム。
【請求項１３】メモリに格納され、データ処理システム
によって実行でき、複数の頂点と接続辺とによって定義
されたグラフィック多角形をクリップ領域にクリップす
るコンピュータ・プログラムの製品において、表示すべき多角形のどの頂点を放棄できるかを計算し、
放棄されなかった頂点に対してのみ少なくとも一つのカ
ラー・ファクタを計算する手段と、クリップ領域境界と交差するすべての辺の上の境界頂点
を計算し、それらに対する少なくとも一つのカラー・フ
ァクタを計算する手段と、前記計算されたカラー・ファクタに従って前記頂点を表
示する手段と、を備えることを特徴とするコンピュータ
・プログラム製品。
【請求項１４】どの頂点が放棄できるかを計算する前記
手段は、前記クリップ領域と交差する辺に接続された頂
点に対する少なくとも一つのカラー・ファクタを計算す
る手段を有することを特徴とする請求項１３に記載のコ
ンピュータ・プログラム製品。
【請求項１５】クリップ領域境界と交差するすべての辺
の上の境界頂点を計算する前記手段は、前記境界頂点に
対する少なくとも一つのカラー・ファクタを、前記辺に
接続された頂点に対してすでに計算されたカラー・ファ
クタによる補間によって計算する手段を有することを特
徴とする請求項１４記載のコンピュータ・プログラム製
品。
【請求項１６】前記クリップ領域内の辺の各点に対する
少なくとも一つのカラー・ファクタを、前記辺に接続さ
れた頂点に対してすでに計算されたカラー・ファクタに
よる補間によって計算する手段をさらに備えることを特
徴とする請求項１５記載のコンピュータ・プログラム製
品。