JPH03242768A - オブジエクトの選択を検出する方法及び装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 Ａ、産業上の利用野 本発明は、広義にはコンピュータ・グラフィックス・デ
ィスプレイ・システムに関し、より詳しくはオペレータ
が選択したデイスプレィ・スクリーンのエリアと交差す
る表示オブジェクトを識別するための処理方法及び装置
に関する。さらに詳しくは、本発明は表示図形の詳細描
出前におけるオペレータのオブジェクト選択の検出に関
する。

Ｂ８　　従来の技術及びその課題 ＣＡＤ／ＣＡＭワークステーションのような対話型ラス
タ・グラフィックス・システムは、機械、電気機器、電
気機械、及びエレクトロニクス装置のコンポーネントや
システムの設計に広範に利用されている。このようなグ
ラフィックス・システムにおいては、設計中のコンポー
ネントやシステムを変更しまたは試験するために、オペ
レータによるそれらのコンポーネント、またはシステム
のコンピュータ・ベース・モデルとの対話に重点が置か
れることが度々ある。コンピュータ・ベース・モデルは
、オペレータが処置を加えることが出来るよう個々に処
理され、表示される多数のオブジェクトよりなる。表示
オブジェクトの選択は、ライトペン、ロケータ（位置入
力装置）（例えば、スタイラスを有するデータ・タブレ
ット）、及びアルファ二二一メリツク・機能キーボード
のような多種多様なオペレータ操作型対話装置のうち、
適宜の装置を用いて行われる。多くの対話シーケンスの
うち重要な役割を有する部分の一つは、オペレータによ
り処置されるべく選択される表示オブジェクトのコンピ
ュータによる識別であり、このプロセスはピッキング（
ｐｉｃｋｉｎｇ）として知られている。

一般に、グラフィックス・システムの処理技術にあって
は、さらに処理を加えるために選択あるいはピックされ
る特定オブジェクトを識別するのに、デイスプレィ・ス
クリーン全体の再処理が必要である。より詳しく言うと
、現行の処理方法は、ワールド座標空間における表示オ
ブジェクトを定義する各幾何学的基本表示要素（ｐｒｉ
−Ｉｔｉｖｅ）の変換、変換された各基本表示要素のワ
ールド座標空間における定義済みクリッピング境界に対
するクリッピング、クリッピングされた各基本表示要素
のオペレータ定義ビューポート及びスクリーン座標空間
へのマツピング、マツピングされた全データのラスク化
、さらには生成されたピクセル（画素）がスクリーン座
標空間内のウィンドウ中のオペレータ定義の選択エリア
と交差するか否かの判断を含めて、デイスプレィ・プロ
グラムの再実行を必要とする。上記の交差に関する判断
の結果がイエスであれば、ピッキングが行われる。

上記の方法は効果的ではあるが、選択されなかい幾何学
的オブジェクトをもマツピングし、ラスク化する結果、
不必要な処理が行われると言う明らかな欠点を有する。

例えば、オペレータが選択したスクリーン・エリア外に
おけるべた塗り（ｆｌｌｌｅｄ）ポリゴン（多角形）の
描画やラスク化は不要でありまた時間の無駄でもある。

この問題を扱った一つの解決案が、１９８９年１月２３
日付けの「オペレータが選択した表示オブジェクトを識
別するための対話型コンピュータ・グラフィックス・デ
ィスプレイ・システムによる処理方法（Ｉｎｔｅｒａｃ
ｔｌｖｅ　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ　Ｓｙ
ｓｔｅｍ　Ｐｒｏｃｅｓｓｌｎｇ　Ｍｅｔｈｏｄ　ｆｏ
ｒ　ｌｄｅｎｔｌｆｙｌｎｇ　ａｎ　０ｐｅｒａｔｏｒ
Ｓｅｌｅｃｔｅｄ　Ｄｌｓｐｌａｙｅｄ　０ｂｊｅｃｔ
）Ｊと言う名称の米国特許出願第２９９，９０１号にお
いて論じられている。

この特許出願では、ピック・ウィンドウのワールド座標
空間への逆マツピングを形成する装置及び方法について
考察がなされている。これに開示された技術によれば、
三次元ワールド座標空間から二次元スクリーンへのウィ
ンドウ−ビューポート・マツピングの前にワールド座標
空間内でピツキングを実行させることが可能である。こ
の技術は、パイプライン・サイクル内で早期にピッキン
グする方法、従ってオブジェクトの無用なラスタ化を回
避する方法を提供してくれるものの、他方ではいくつか
の欠点を伴う。最も大きな欠点は二次元のピック・ウィ
ンドウを三次元ワールド座標空間へ逆マツピングしよう
とする際にいくつか不都合が生じると言うことである。

透視画やその他の選択可能な特徴的機能、機構の使用な
ど、三次元から二次元へのマツピングには高度化した技
術が用いられることにより、ピック・ウィンドウの正確
な逆マツピングは困難になっている。

そのため、ピック・ウィンドウの逆マツピングの諸制約
をなくしたラスタ化前にピック検出を行うための改良さ
れた装置及び方法が求められている。

Ｃ０課題を解決するための手段 本発明はパイプライン式グラフィックス・ディスプレイ
・システムにおいて効率的に動作するビック検出システ
ムを提供するものである。本発明のピック検出システム
によれば、グラフィックス・プロセッサにおいてラスタ
化ステップ前にオペレータによるグラフィックス・オブ
ジェクト（適宜単に「オブジェクト」とする）の選択を
効率的に検出するための手段及び方法が得られる。

従って、本発明の目的は、各基本表示要素の全ラスタ化
または全描画を必要としないピック検出ロジックを提供
することにある。

本発明のもう一つの目的は、スクリーン空間よりオブジ
ェクトを正確にピックすることのできる簡単なピック検
出装置及び方法を提供することにある。

上記及びそれ以外の本発明の目的については、以下の実
施例の説明の中においてさらに詳細に述べられている。

Ｄ、実施例 本発明は、グラフィックス・オブジェクトのオペレータ
による選択をそのオブジェクトのラスタ化及びピクセル
生成の前に検出する方法及び装置を提供するものである
。本発明の方法においては、スクリーンを幾つかの領域
に分割し、相続くエンドポイント（端点）及びベクトル
をそれらの領域に基づき分析してトリビアル・ピック（
ピック自明）　（ｔｒｉｖｌａｌ　ｐｉｃｋ）かトリビ
アル・ノー・ピック（ノー・ピック自明）　（ｔｒｌｖ
ｌａｌ　ｎｏ　ｐｌｃｋ）かを判断する。ノントリビア
ル（非自明）　（ｎｏｎ−ｔｒｌｖｌａｌ）条件につい
ては、ピック・ウィンドウの頂点を通って引いたサンプ
ル線の吟味を通じて直線の傾きを求めることにより分析
が行われる。本発明のピック検出を行うための装置は、
ビック検出をグラフィックス・パイプライン処理の一部
として実行する。本発明の装置においてはトリビアル・
ピックまたはトリビアル・ノー・ピックの場合、パイプ
ライン動作は遅くならないが、ノントリビアルの場合は
、余分−の処理サイクルが必要である。

本発明は、グラフィックス処理システム用のピック検出
機構を提供するものである。このピック検出機構はパイ
プライン式プロセッサを用いたグラフィックス・ディス
プレイ・システム用として特に好適であり、本願におい
てはパイプライン式グラフィックス・システムと共に使
用する場合を実施例として説明する。しかしながら、本
発明のピック検出機構ないしは検出方法は、そのような
パイプライン処理システムにおける利用にのミ限定され
るものではない。

本発明のもう一つの特徴はピック相関として知られてい
る機能にある。グラフィックス・パイプラインにおいて
は、描画プロセッサによる実際の描画が障害となること
がよくある。デイスプレィ・プログラムは、描画をしよ
うとしている場合でなければ、より迅速にトラバース（
ｔｒａｖｅｒｓｅ）できることがしばしばある。本発明
によるピック検出ハードウェアはパイプライン式要素で
あるから、データを全く次のパイプライン式要素へ通過
させないモードに設定することができる。ピック相関モ
ードとして知られているこのモードにおいては、グラフ
ィックス・プロセッサは、オブジェクトを描画する必要
なく、ピック検出のためのデイスプレィ・プログラム・
チェックを実行することができる。

本発明の一実施例のグラフィックス・ディスプレイ・シ
ステムの全体的構成を第１図に示す。システム制御プロ
セッサ１００は通信回線１０２を介して行われるこのグ
ラフィックス・デイスプレィ◆システムとホスト・プロ
セッサとの対話を制御する。内部１１０プロセツサ１０
４は、キーボード、タブレットとスタイラス、プログラ
ム機能キー　及びその他所要のオペレータ操作機器等の
オペレータ制御装置に接続されている。システム制御プ
ロセッサ＋００はグラフィックス制御プロセッサ１０８
によるグラフィックス命令の実行を管理する。システム
制御プロセッサ＋００とグラフィックス制プロセッサｌ
０Ｅｉは共用システム・メモリ１０８を介してデータ交
換し、システム制御プロセッサ＋００はホスト・システ
ムより表示命令を受は取り、グラフィックス制御プロセ
ッサｌＯ［ｉに実行させるべく記憶する。グラフィック
ス制御プロセッサＩｏ６はグラフィックス描画命令を解
読し、変換、クリッピング、マツピング、及びピッキン
グのためにパイプライン・プロセッサ１１０に供給する
。ピック検出ロジック１１２はグラフィック処理パイプ
ラインの一部をなしている。さらに、ピクセル描画プロ
セッサ１１４もこのパイプラインの一部をなしており、
このプロセッサ＋１４は関連ピクセルをビデオ・ピクセ
ル・メモリ１１Ｂに書き込むことにより最終画像を描出
する役割を有する。ビデオ・ピクセル・メモ１ＪｌｌＢ
は、ビデオ・デイスプレィ・モニタ、ハードコピー・プ
リンタ、あるいはこれらと類似の装置であるデイスプレ
ィ・デバイス（表示装置）　１１８上に画像を生成する
のに必要な回路群によってアクセスされる。

本発明によれば、ピッキング・プロセスはピック検出ロ
ジック！１２により行われる。１１０プロセツサ１０４
はスタイラスとタブレットのようなオペレータが選択動
作を行うオペレータ選択装置の位置を監視する。この実
施例においては、システム制御プロセッサ１００は周期
的にＩ１０プロセッサ１０４をサンプリングして、オペ
レータ選択装置の位置が変化したかどうかを判断する。

位置が変化していれば、システム制御プロセッサ１００
はグラフィックス制御プロセッサＩＯＧに割込みをかけ
、そのオペレータ選択装置の新しいＸ及びＹ座標（スク
リーン座標空間の）を転送する。グラフィックス制御プ
ロセッサ１０Ｂはピック・ウィンドウ境界を座標値Ｘ５
ｌｎ＋Ｘｍｍｘ＋Ｙｓｌｎ＋Ｙ＊ｓｘ＋として決定し、
これらの値を制御ライン１０７を通じてピック検出ロジ
ック１１２中のレジスタにロードする。ピック・ウィン
ドウは、通常、オペレータ選択装置のＸ、Ｙ座標位置を
取り囲む例えば２４Ｘ２４のピクセルの正方形よりなる
。ピック・ウィンドウの範囲はＸ、Ｙ座標から計算され
る。

グラフィックス制御プロセッサＩＯＢはグラフィックス
命令を解読し、変換、ピック検出及びピクセル描画のた
めにパイプライン・プロセッサ１１０　。

１１２および＋１４へ転送する役割を有する。パイプラ
イン・プロセッサは多辺形（ｐｏｌｙｌｌｎｅｓ）　、
ポリゴン、及びその他の幾何学形状のような基本表示要
素の指定された頂点に対して処理を行う。直線の両端点
を定める２つの頂点座標を、ビデオ・ピクセル・メモリ
ｌｌ［ｉへの記憶及びデイスプレィ・デバイス１１８で
の表示のためにピクセルに変換するのは、ピクセル描画
プロセッサ１１４におけるピクセル描画ステップのみで
ある。パイプラインはこれらの頂点を変換し、マツピン
グするよう動作する。例えば、ポリライン・コマンドは
沢山の指定点の間に線分を引くことを要求することがあ
る。

このような場合、パイプライン・プロセッサは先ずワー
ルド座標空間（三次元空間）において平行移動（ｔｒａ
ｎｓｌａｔｌｏｎ）、スケーリング（拡大縮小）あるい
は回転コマンドを適用することにより指定された各頂点
を変換する。続いて、パイプライン・プロセッサは生成
された像を定義済みウィンドウに従い三次元空間におい
てクリッピングする。

その後、パイプラインはウィンドウ内の三次元データを
二次元のビューボートにマツピングする。

この時点で、各頂点は二次元スクリーン座標において指
定された状態となる。

本発明におけるピック検出ロジック１１２は二次元スク
リーン座標内で指定された頂点情報に対して処理を行う
。ピック検出ロジック１１２は合致が起こった時、即ち
２つの頂点を結ぶ直線が定義済みピック・ウィンドウを
通る時、確実にこれを検出するよう動作する。グラフィ
ックス制御プロセッサ１０［ｉは、アプリケージ日ン・
パラメータに基づいてその合致が実際に起こったかどう
かを判断する役割を有する。例えば、この実施例のシス
テムにおいては、グラフィックス制御プロセッサは、ピ
ック・ウィンドウを介して描かれる最初のオブジェクト
、ピック・ウィンドウを介して描かれる最後のオブジェ
クト、あるいはピック・ウィンドウを介して描かれる全
てのオブジェクトのピックを信号で知らせるよう設定す
ることができる。ピック検出ロジック１１２は、合致を
検出すると必す、ビック割込み処理のためにグラフィッ
クス制御プロセッサ１０６に割込みをかける。グラフィ
ックス制御プロセッサｌ０Ｅｉはアプリケージ５ン指定
動作を実行し、次いでピック検出ロジック＋１２の割込
みをリセットし、これによってパイプライン・プロセッ
サを再始動させ、処理を再開する。

本発明のこの実施例のピック検出ロジックはコーエン・
サザーランド（Ｃｏｈｅｎ−Ｓｕｔｈｅｒｌａｎｄ）の
クツピング・アルゴリズムに基づく形態のピック検出を
行うものである。コーエン・サザーランドのクリッピン
グ・アルゴリズムについては、フォリー（Ｆｏｌｅｙ）
及びファン・ダム（Ｖａｎ　Ｄａｍ）著の「対話型コン
ピュータ・グラフィックスの基１！（Ｆｕｎｄａｍｅｎ
ｔａｌｓ　ｏｆ　Ｉｎｔｅｒａｃｔｉｖｅ　Ｃｏｌ１ｐ
ｕｔｅｒ　（ｉｒａｐｂｌｃｓ）　Ｊ、＋４１ｉ乃至１
４９頁により詳細に記載されている。コーエン・サザー
ランドのアルゴリズムにおいては、スクリーン空間を９
つの領域に分割することによりクリッピングを実行する
。これと同じように、本発明のピック検出ロジックはス
クリーンを９つの領域に分割してピック検出を行う。オ
ペレータが指定するピック・ウィンドウは、４つの点、
即ちＬｌｎ　＋Ｌａ＋＋　ＩＹＩＩＩｌｌ及びＹ＊ａｘ
によって指定することができる。第２図はスクリーン座
標空間におけるピック・ウィンドウ１２０の位置を示す
。ピック・ウィンドウ＋２０は通常は正方形のスクリー
ン・エリアの形で実施される。９つの各領域はアラトコ
−）’　（ｏｕｔｃｏｄｅ）で識別される。アウトコー
ドは４ビットからなり、それらの各ビットは各領域とウ
ィンドウ１２０を定義する４つの点の中の１点との関係
を示す。即ち、本発明のこの実施例で用いられているア
ウトコードは、その領域がＣ１ｎの左側かどうかを示す
１ビット、Ｘ□８の右側かどうかを示す１ビット、Ｙｌ
ｌ、ｘの上側かどうかを示す１ビット、及びＹｍｌｎの
下側かどうかを示す１ビットの合計４ビットで構成され
ている。従って１２２．！ニラベルされた領域は１０１
０と言うアウトコードを有し、この領域がＸｓ　ｌ　ｎ
の左側でＹ□８の上側にあり、Ｘ。

、８の右側あるいはＹｓｌｎの下側にはないということ
を示している。ピック・ウィンドウ！２０を定義する領
域のアウトコードはｏｏｏｏである。

コーエンーサザーランドのアルゴリズムは、２つの頂点
により定まる線分について、その全体がピック・ウィン
ドウの外部にあるか否か、限定的にピック・ウィンドウ
内にあるか否か、あるいは更に分析が必要か否か、を迅
速に判断する手段を与えるものである。最初の２つの条
件はそれぞれ「自明に内側（ｔｒｌｖｌａｌｌｙ　Ｉｎ
）Ｊ及び「自明に外側（ｔｒｌｖｌａｌｌｙ　ｏｕｔ）
Ｊと呼ばれる。本発明によれば、コーエン・サザーラン
ドのアルゴリズムでは扱うことのできない非自明（ｎｏ
ｎ−ｔｒｌｖｌａｌ）ピック条件を処理するための新規
な手段を実施することが可能である。

以下、本発明によるピッキング・プロセスを第３図を参
照しつつ説明する。図中、線分（直線）１３０は領域■
の点ＰＩと領域■の点Ｐ２を結んでいる。

領域■内の一点と領域■内の一点を結ぶ直線は決してピ
ック・ウィンドウと交わらないと言うことを証明するこ
とができる。従って、直線１３Ｇは自明にピック・ウィ
ンドウの外側であると断定することができる。同様にし
て、領域■の点Ｐ３と領域■の点Ｐ４とを結ぶ直線＋３
２は常にピック・ウィンドウと交わるので、自明にピッ
ク・ウィンドウの内側であると認定される。点Ｐ５とＰ
Ｂ、Ｐ７及びＰＢをそれぞれ結ぶ直線１３４、＋３１１
ｉ及び＋３８は、単にこれらの直線の始点の領域と終点
の領域のみに基づいて各直線が自明に内側ではないとか
、自明に外側ではないとかを判定することはできないと
言う情況を示している。点Ｐ５とＰ６を結ぶ直線１３４
は明らかにピック・ウィンドウを通らないが、点Ｐ５と
Ｐ７を結ぶ直線１３［ｉはピック・ウィンドウを通る。

従って、領域■と■との間を結ぶ全ての線について概括
することは不可能である。これらの領域を結ぶ直線につ
いては更に詳細に分析しなければならない。

直線がピック・ウィンドウを通るか否かを判断するため
には、組合せ論理を用いて直線の端点のアウトコードが
結合され、これに基づいて判断がなされる。ベクトルは
、下記の条件（判断基準）が満たされる場合、自明に内
側である。

ａ、第１の点ＰＩまたは第２の点ＰＩＩのアウトコード
が’ｏｏｏｏ　’であるか、またはす、　　ＰＩ及びＰ
ＩＩのアウトコードが、Ｘを任意の値として、共に’ｏ
ｏｘｘ’であるか、またはｃ、　　ＰＩ及びＰＩＩのア
ウトコードが、Ｘを任意の値として、共に“ｘｘｏｏ　
’である。

第１の点ＰＩと第２の点ＰＩのアウトコードの論理積Ａ
ＮＤが’ｏｏｏｏ’でなければ、ベクトルは自明に外側
である。ベクトルがこれらの何れの基準をも満たさない
場合には、自明に内側であると認定するか、自明に外側
であるとして拒絶するかを判断するために更に分析を行
う必要がある。このようにして、直線１３０は、アウト
コードの論理積ＡＮＤが”ｏｏｏｏ’に等しくないから
、自明に外側と判断される。直線１３２は、点ＰＩとＰ
Ｉのアウトコードが共に”ｘｘｏｏ　’であるから、自
明に内側である。直線１３４．１３６及び１３Ｂは上記
のどの基準をも満たしていない。

上記のような非自明の場合は、端点によって定まる直線
の実際の経路について検討しなければならない。第１の
点ＰＩを（ＸＩ　、Ｙｌ）とし、第２の点Ｐｎを（Ｘ２
．Ｙ２）とするならば、ビック検出ロジック＋１２は下
記の直線の方程式を評価しなければならない。

（ｙ　　−Ｙｌ）−Ｍ（ｘ　　−ＸＩ）＝０阿は２つの
点ＰＩ、　　ＰＩＩを結ぶベクトルの傾きであり、ｘ、
ｙは直線上の点を表す変数である。上式において、傾き
Ｍに直線の両端点の座標値を代入すると下記の方程式を
得ることができる。

（７−Ｙｌ）（Ｘ２−　ＩＩ）　−（Ｙ２−　Ｙｌ）（
ｘ　−ＸＩ）＝　０この直線と、ピック・ウィンドウの
２つの頂点との相対的関係を調べることにより、この直
線がピック・ウィンウドの内側にあるか否かを判断する
ことができる。この判断方法には様々なやり方が考えら
れる。例えば次のようなやり方がある。

上記の通り、上式のＸ＋　７は直線上の任意の点を表す
変数である。もちろん、Ｘ及びｙに任意の値を入れても
、点（ｘ、ｙ）が必ずこの直線上に乗る訳ではなく、直
線上に乗らない場合は方程式の値はＯとはならずに、点
（ｘ、ｙ）が上記両端点を結ぶベクトルのどちら側にあ
るかによっである正の値または負の値となる。従って、
（ＸＩ、Ｙｌ）と（１２，Ｙ２）を結ぶ直線がピック・
ウィンドウと交わるか否かの判断に関しては、ピック・
ウィンドウの２つの頂点の座標値を指定された方程式に
代入し、その結果を分析することにより吟味することが
できる。

例えば、第４図において、点１４０と点１４２の値、即
ち（Ｘ−＋□Ｙ、、、）と（Ｘ、、、、Ｙ−＋ｎ）を代
入することにより、この直線がピック・ウィンドウの内
側にあるか否かを判断することができる。−例として第
４図の点ＰＩとＰ２”を結ぶ直線１４４について上記直
線の方程式の吟味を行うと、ピック・ウィンドウの２つ
の頂点のうち一方は符号が正となり、他方は負となる。

２つの頂点の座標値を代入した結果の符号が互いに逆に
なると言うことはその直線がピック・ウィンドウを通っ
ていると言うことを示す。直線１４６または１４８につ
いて上記の評価を行うと、２つの符号が共に正かまたは
共に負となり、これによってそれらの直線はピック・ウ
ィンドウを通らないから拒絶すべきであるという指示が
得られる。

この他にも、次のような調べ方がある。すなわち、直線
ＰＩＰＩＩの一方の端点、例えばＰＩからピック・ウィ
ンドウの２つの頂点のそれぞれに向かう２つの直線を考
えて、これらの直線の傾きＭｌ及び恥と、直線ＰＩＰｎ
の傾き閾とを比較することである。Ｌ＜潤〈Ｍ２（叉は
恥＜　Ｍ＜　ｘ＋　）であれば、直線ＰＩＰｎはピッ・
り・ウィンドウの内側にあり、そうでなければ（例えば
、Ｍ＜Ｊ＜Ｍｓ）直線ＰＩＰＩＩはピック◆ウィンドウ
の内側にはないと判断する。

また次のような調べ方もある。直線ＰＩＰＩ［と、ピッ
ク・ウィンドウの２つの頂点を結ぶ直線とが交わるかど
うかを調べることにより、これらの直線が交わっていれ
ば、直線ＰＩＰＩ［がピック・ウィンドウの内側にある
ものと判断する方法である。

いずれの調べ方にせよ、これらの方法の本質は吟味すべ
き直線と、ピック・ウィンドウの２つの頂点との相対的
関係を調べることにより、この直線がピック・ウィンド
ウの内側にあるか否かを判断することである。

従って、第４図において直線１４８叉は直線１４８のよ
うに、ピック・ウィンドウの２つの頂点＋４０及び１４
２がいずれもこれらの直線の下側叉は上側にあれば、ピ
ックなしと判断され、直線１４４のように、ピック・ウ
ィンドウの２つの頂点がちょうどその直線に対して上側
と下側にそれぞれ存在する場合には、ピックありと判断
される。

直線の方程式の吟味に用いる２つの点（ピック・ウィン
ドウの頂点）は各直線の始点たる第１の点が存在する領
域によって決まる。即ち、頂点の選択は下表に従って行
われる。

１−二嘆　　　　　　　　　　　　　の　　　　　　に
　　　　　　れる■　　　　（Ｘｍａｘ、Ｙｍａｘ）と
（Ｘｍｌｎ、Ｙｍｌｎ）■　　　　　　　　　（Ｘｍａ
ｘ、Ｙｍａｘ）　　と　（Ｘｉ＋Ｉｎ　、Ｙｍａｘ）■
　　　　　　　　（Ｘｍｌｎ、Ｙｓａｘ）　　と　（Ｘ
ｍａｘ、Ｙｓｉｎ）■　　　　　　　　（Ｘｍｌｎ、Ｙ
ｍａｘ）　　と　（Ｘｍｌｎ、Ｙｍｌｎ）■　　　　（
Ｘｍａｘ　、Ｙｍａｘ）と（Ｘｍａｘ、Ｙｍｌｎ）■　
　　　（Ｘｍｌｎ　、Ｙｍａｘ）と（Ｘｍａｘ、Ｙｍｌ
ｎ）■　　　　（Ｘｍａｘ、Ｙｍｌｎ）と（Ｘｍｌｎ、
Ｙｍｌｎ）■　　　　（Ｘｍａｘ、Ｙｍａｘ）と（Ｘｍ
ｌｎ、Ｙｍｌｎ）非自明ビック処理において解決しなけ
ればならない最後の問題として、ピック・ウィンドウが
例えばポリゴンによって完全に取り囲まれている場合に
そのことをどのようにして識別するかと言う問題がある
。即ち、第５図に示すように、ピック・ウィンドウ１５
０の周囲がポリゴン１５２によって完全に取り囲まれて
いるような場合である。上に述べたような直線方程式の
吟味では、ポリゴン１５２のどの辺もピック・ウィンド
ウ１５０を通らないので、ポリゴン１５２の合致あるい
はピックは検出されない、この場合、合致あるいはピッ
クの有無は、ピック・ウィンドウの１つの頂点から任意
の方向に向けて無限に延びる直線を吟味することによっ
て判断される。第５図においては、ピック・ウィンドウ
＋５０の頂点（Ｘ、、、、Ｙ、、、）から右方へ直線１
５４が引かれている。そして、この直線１５４がリボン
１５２と交わる回数（交差回数）を計数することにより
、合致が起こっているか否かの判断がなされる。この実
施例においては、ビック検出ロジック１１２により処理
された各ポリゴン・ベクトル毎に、上記の直線の交差（
ピック・ウィンドウとの交わり）が吟味される。ポリゴ
ン開始（ｂｅｇｉｎｐｏｌｙｇｏ’ｎ）命令が出される
と、まずこの吟味モードがセットされる。アウトコード
が吟味され、ポリゴン交差ビットが合致の有無によって
“ｏｌまたは′１′にトグルされる（　ｔｏｇｇｌｅｄ
）。ポリゴン終了（ｅｎｄ　ｐｏｌｙｇｏｎ）命令が入
力された時、合致が起こっていなければ、上記の最後に
述べた直線のポリゴン交差が吟味される。この例の場合
（第５図）、直線１５４はポリゴン１５２の辺と１回だ
け交わり、ピック・ウィンドウ１５０が完全にポリゴン
１５２の内側にあると言うことを示している。一般に、
交差回数が奇数の場合、合致またはピックが起こってい
ると言うことを示し、偶数は合致またはピックが起こっ
ていないと言うことを示す。

第６図は、本発明によるシステムの全体的論理処理の流
れを示ナフローチャートである。図示のシステムは、先
ず次回のアウトコードを演算する（ステップ１６０）。

　（この論理システムは一回（１サイクル）に１つの頂
点の処理を行い、最初のアウトコードについては吟味を
実行することができない。吟味処理は全て今回と前回の
頂点を対象に行われる。）今回と前回のアウトコードが
吟味され、自明に内側（ビック自明）または自明に外側
（ノー・ピック自明）の条件の有無が判断される（ステ
ップ１６２）。これらの自明か否かの吟味の結果が何れ
も真でない場合、制御はステップ１６４へ移り、非自明
な直線方程式の吟味が実行される。

ステップ１６２で自明条件が存在すれば、制御はステッ
プ１［ｉへ移り、自明に内側と自明に外側のどちらの条
件が生じているのかの判断が行われる。

自明に外側であれば、制御はアウトコードの演算（ステ
ップ１６０）へ戻る。自明に内側であれば、制御はステ
ップＩＧ８へ進み、パイプラインを停止させると共に、
グラフィックス制御プロセッサに割込みをかけてピック
を処理させる。同様にして、非自明な直線方程式の吟味
（ステップｌ６４）の結果はステップ＋７０へ送られ、
非自明ピックが起こっているか否かが判断される。非自
明ピックが起こっていなければ、制御はステップＩＥｉ
Ｏへ戻り、非自明ピックが検出された場合、制御はやは
りステップ１８Ｂへ進む。グラフィックス制御プｏ−ｔ
＝ツサが割込みを処理し終えると、ピック検出ロジック
における割込みをクリアさせ、パイプラインを再スター
トさせるコマンドが送出される（ステップ１７２）。

本発明による上記のビック検出ロジックを実行させるた
めのハードウェア・システムの一実施例の構成を第７図
に詳細に示す。ビック検出ロジックの入力はピック・ウ
ィンドウ境界値ＬＩＩｌｓ　Ｘｌｌ＠。、Ｙｓｌ＋＋ｓ
　Ｙｍ＊ｘ、ベクトルの第１の点の前回のＸ及び前回の
ｙの値、及びベクトルの第２の点を表す今回のＸの値及
びｙの値である。ピック・ウィンドウ境界値はピック検
出レジスタに記憶され、前回のＸ及びｙの値はパイプラ
イン・レジスタに記憶される。

アウトコードは、図の左側に示す回路群により演算され
る。減算装置１８Ｇは（ｘ−Ｘｓ　ｌ　ｎ　）または（
ｙ−ｙ、＋。）を計算し、その結果の符号を次段へ送る
。

同様に、減算装置１８４は（Ｌｓｘ−ｘ）または（Ｙ、
、。

−ｙ）を計算する。マルチプレクサ！８２及び１８ｆｉ
は上記の減算プロセスのための適切なウィンドウ座標を
選択する。Ｘ及びｙの値はパイプライン・レジスタによ
って交互にビック検出ロジック１１２へ送られるので、
１つの点（ｘ、ｙ）を演算するためには２処理サイクル
が必要である。減算装置＋８０により実行される減算の
結果は、今回のＸの場合は「左」レジスタ１８８に入れ
られ、今回のｙについては「下」レジスタ１９０に入れ
られる。同様に、減算装置１８４による演算結果は「右
」レジスタ１９２及び「上」レジスタ１９４に入れられ
る。これら４つのレジスタの内容がアウトコードを表す
。アウトコード分析ロジック１９６は上記の論理規則を
適用して自明に内側または自明に外側の条件の有無を判
断する。アウトコード分析ロジック１９６は、ピック・
ウィンドウがポリゴンによって取り囲まれているかどう
かを判断するためのポリゴン分析をも実行する。アウト
コード分析ロジック１９Ｇは、トグル式のポリゴン参照
ビット１９Ｂ、　自明／非自明信号２００及び自明ピッ
ク／拒絶信号２０２を出力する。

非自明条件が存在する場合は、非自明ピックを検出する
ために図示の論理システムの右側の部分を用いて直線の
傾きが演算される。減算袋＠　２０４はマルチプレクサ
２０Ｂ及び２０８の選択するところにより（今回のＸ−
前回のＸ）、または（今回のｙ−前回のｙ）の減算を行
う。減算装置２１０はマルチプレクサ２１２及び２１４
によって選択される適切なピック・ウィンドウ座標値か
ら適切な前回のＸ値または前回のｙ値を減算する。これ
らの減算結果は乗算器２１６によって乗算され、その結
果はレジスタ２１８，２２０．２２２、または２２４の
中の適切なレジスタに記憶される。この処理ロジックは
、非自明ピックが起こっているか否かを判断するのに必
要な４つのレジスタにデータを入れるのに４サイクルが
必要とする。最初の２つの処理サイクルはアウトコード
分析ロジック１９ＢによるＸ及びｙ値の処理と同時に行
われる。アウトコード処理ロジック１９Ｂによって非自
明条件の存在が知らされると、パイプラインは停止され
、ビック検出ロジックはさらに２サイクル動作して、他
の２つの演算を完結する。４つのレジスタ２１Ｂ乃至２
２４に全てデータが入れられる−と、減算装置２２６及
び２２８がこれらのレジスタの内容をそれぞれ減算し、
それらの減算結果がＸＯＲ回路２３０により排他的論理
和処理されて、非自明ピックまたは拒絶信号が導出され
る。マルチプレクサ２３２は適切な値の信号を選択して
、割込み発生ロジック及びパイプライン制御ロジックへ
供給する。

本発明において上記と異なる回路を用いた実施例が可能
なことは明らかであろう。例えば、乗算器を減算回路と
共に別途に付加して、非自明条件に関する演算を２サイ
クルで行うようにすることも可能である。同様に、この
演算を１サイクルで実行するような論理システムを用い
ることも可能である。

上記実施例においては、ピック自明の認定または拒絶の
演算は通常２サイクルで行われ、パイプラインの流れに
割り込みをしない。処理の大半は、ピック条件なしで行
われるため、乗算器を付加した場合の演算のためにパイ
プラインが停止される頻度は極めて低い。

Ｅ０発明の詳細 な説明したように本発明によれば、各基本表示要素の全
ラスク化または全描画を必要とせすにピック検出を行う
ことができる。

【図面の簡単な説明】

第１図は本発明の一実施例のグラフィックス・ディスプ
レイ・システムのブロック図、第２図は本発明で使用す
るビック・ウィンドウの説明図、 第３図は本発明を説明するためのグラフィックス・デイ
スプレィ・スクリーンの説明図、第４図は、本発明の一
つの特徴を説明するためのビック・ウィンドウの説明図
、 第５図は本発明を説明するためのビック・ウィンドウが
ポリゴンにより囲まれた状態を例示する説明図、 第６図は本発明の一実施例のシステムにおける論理処理
の流れを示すフローチャート、第７図は本発明の一実施
例の装置のブロック図である。 ００ ０Ｅｉ １０ １２ １４ システム制御プロセッサ、 システム制御プロセッサ、 パイプライン・プロセッサ、 ピック検出ロジック、 ピクセル描画プロセッサ、 １６ １８ １２０゜ ５２ １８２゜ １８８゜ ９Ｂ ２０４゜ ２０６゜ １６ ２１８゜ ２２６゜ ３０ ３２ ・・・　ビデオ・ピクセル・メモリ、 ・・・表示装置（デイスプレィ・デバイス）、１５０・
・・　ビック・ウィンドウ、 ・・・　ポリゴ、　　　　　１８０，１８４・・・・減
算装置、１８Ｂ・・・　マルチプレクサ、 １９０、１９２．　１９４・・・　レジスタ、・・・　
アウトコード分析ロジック、 ２１０・・・減算装置、 ２０８、２１２，２１４・・・　マルチプレクサ、・・
・乗算器、 ２２０、２２２．２２４・・・　レジスタ、２２８・・
・減算装置、 ・・・　ＸＯＲ回路、 ・・・　マルチプレクサ

Claims (6)

【特許請求の範囲】
1. （１）グラフィックス・ディスプレイ・システムによっ
   て表示装置上の画像中に表示されるオブジェクトのオペ
   レータによる選択を検出する検出方法であって、 上記オペレータによる選択のためのオペレータ選択エリ
   アを画定するピック境界を記憶するステップと、 上記ピック境界に対する第１のオブジェクト頂点の関係
   を表す第１のコード化表示を得るステップと、 上記ピック境界に対する第２のオブジェクト頂点の関係
   を表す第２のコード化表示を得るステップと、 上記の第１のコード化表示と第２のコード化表示を論理
   結合するステップと、 上記の論理結合されたコード化表示を吟味して上記の２
   つの頂点を結ぶ直線が上記オペレータ選択エリアに対し
   自明に内側であるかまたは自明に外側であるかを判断す
   るステップと、 上記直線が上記オペレータ選択エリアの自明に内側の場
   合に合致事象の発生を知らせる信号を出すステップと、 上記の自明に内側か外側かの判断が不可能な場合に、続
   いて上記オペレータ選択エリアの２つの頂点を選択する
   ステップと、 上記第１のオブジェクト頂点と上記第２のオブジェクト
   頂点とを結ぶ直線と、上記オペレータ選択エリアの上記
   ２つの頂点とが所定の関係にある場合に、これをを知ら
   せる信号を出し、そうでない場合は処理を継続するステ
   ップと、 を有し、上記各ステップを上記画像中の全てのオブジェ
   クトの各頂点について繰り返すことを特徴とする検出方
   法。
2. （２）上記第１及び第２のコード化表示が、各ピットが
   上記ピック境界との関係を表す４ビットの２進コードよ
   りなることを特徴とする請求項（１）記載の検出方法。
3. （３）上記の論理結合されたコード化表示を吟味するス
   テップが、 その論理結合されたコード化表示を吟味するステップと
   、 この吟味の結果、 上記の論理結合されたコード化表示の全てのビットが０
   である以外の場合に、自明に外側の条件の存在を知らせ
   る信号を出すステップと、 全てのビットが０である場合に、上記第１及び第２のコ
   ード化表示を吟味するステップと、この吟味の結果、 そのどちらかのコード化表示の全てのビットが０である
   場合に、自明に内側の条件の存在を在を知らせる信号を
   出し、そうでない場合に非 上記の両方のコード化表示の前の方の２ビットが共に０
   であるか、または後の方の２ビットが共に０である場合
   に、自明に内側の条件の存在を知らせる信号を出し、そ
   うでない場合に非自明条件の存在を知らせる信号を出す
   ステップと、 よりなることを特徴とする請求項（２）記載の検出方法
   。
4. （４）上記第１及び第２のコード化表示を評価して、上
   記の第１のオブジェクト頂点と第２のオブジェクト頂点
   との間のベクトルが上記オペレータ選択エリアの頂点の
   一つから無限に延びる直線と交わるか否かを判断するス
   テップと、 上記ベクトルが上記直線と交わる場合には、カウンタを
   インクリメントし、ポリゴン終了コマンド処理時に上記
   カウンタをチェックするステップと、 合致事象を示す信号が出されていない場合、上記カウン
   タのチェックにおいてカウンタ内容が奇数であれば合致
   事象を示す信号を出すステップと、を具備したことを特
   徴とする請求項（１）記載の検出方法。
5. （５）複数のグラフィックス命令により表示装置上に生
   成される画像中に表示されるオブジェクトのオペレータ
   による選択を検出するための検出装置であって、 オペレータが上記画像内にオペレータ位置を指定するた
   めの第１オペレータ位置指示手段と、第１次元及び第２
   次元におけるピック上限及びピック下限を記憶するため
   の第１メモリ手段であって、上記ピック上下限が上記オ
   ペレータ位置からのオフセットを表すと共に、オペレー
   タが選択するオペレータ選択ウィンドウの頂点をなすよ
   う組み合わされる第１メモリ手段と、 上記グラフィックス命令を記憶するための第２メモリ手
   段と、 上記グラフィックス命令をデコードしてオブジェクト頂
   点情報を転送する第１処理手段と、上記第１処理により
   転送されたオブジェクト頂点情報に対して図形変換を実
   行する第２処理手段と、 上記の図形変換されたオブジェクト頂点の上記上下限に
   対する関係を示すコード化表示を生成する第１論理手段
   と、 第１のオブジェクト頂点及び第２のオブジェクト頂点よ
   り得られる第１コード化表示と第２コード化表示とを論
   理結合する第２論理手段と、上記第２論理手段により論
   理結合されたコ ード化表示が自明ピックを示している場合は合致信号を
   発生し、上記論理結合されたコード化表示を自明に評価
   することができない場合は非自明信号を発生する第３論
   理手段と、 上記の第１のオブジェクト頂点と第２のオブジェクト頂
   点とを結ぶ直線を上記オペレータ選択ウィンドウの頂点
   を通る直線に関して評価する第４論理手段と、 上記第４論理手段による評価を吟味して、上記第１のオ
   ブジェクト頂点と第２のオブジェクト頂点とを結ぶ直線
   が上記オペレータ選択ウィンドウと交わる場合ピック信
   号を発生する第５論理手段と、 を具備したことを特徴とする検出装置。
6. （６）上記頂点情報をピクセル値に変換する第３処理手
   段と、 上記ピクセル値を上記表示装置上に表示するために記憶
   する第３メモリ手段と、 を具備し、 上記第２処理手段が、上記の図形変換された頂点情報が
   上記第３処理手段へ転送される第１モードと上記第３処
   理手段へ何も転送されない第２モードで動作可能である
   ことを特徴とする請求項（５）記載の検出装置。