JPH0281179A - ピッキング回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概要〕 例えばＣＡＤなどのような図形処理システムにより図形
を作成する操作過程で対話的に画面上の図形を選択し、
移動、拡大、縮小等の図形編集を行う場合のピッキング
回路に関し、 中点分割法を改善し、中点分割を交点が得られるまで繰
返さなくても途中の中点と、その中点に対応する始点と
終点の位置関係で、ピック領域と交差するか否かを判定
することによりピッキング処理を高速化し、ＣＡＤ等の
図形処理における図形選択を効率化することを目的とし
、 始点、中点及び終点のそれぞれの位置する領域の位置関
係により、線分が前記範囲内を通るか否かを判定し、こ
れにより判定できない線分に関しては中点分割を行い、
分割された線分の始点、中点及び終点のそれぞれの位置
する領域の位置関係により、線分が前記範囲内を通るか
否かを判定する位置判定回路を備えるように構成する。

〔産業上の利用分野〕

本発明は、例えばＣＡＤなどのような図形処理システム
により図形を作成する操作過程で対話的に画面上の図形
を選択し、移動、拡大、縮小等の図形編集を行う場合の
ピッキング（図形選択）回路に関する。

図形処理システムは、−船釣に、第７図に示すように、
メモリ３０．デイスプレィ３１．キーボード３２．入力
ペン３３．タブレット３４．プロセッサ３５等から成り
、オペレータはＣＲＴ画面上の図形をボインティング・
デイバイス（例えばマウス、タブレット等）で画面上を
指定することにより、その座標を中心とするピンク領域
（中心から矩形領域のＸ軸及びＹ軸方向の大きさは予め
設定される）と交わる図形が選択される。即ち、上記の
ピンク領域と画面上の図形が交わるか否かを高速に判定
する回路が必要で、図形選択の速度は、特にオペレータ
の生産性に関係があり、利用分野からも一層の高速化が
要求される。

〔従来の技術〕

従来のピッキング回路は、大別すると、３通りになる。

その第１は、線分を表示する場合に使用されるＤＤＡ回
路を拡張したものである。ＤＤＡ回路は指定された２点
を結ぶ線上の点を発生させる回路で、ＣＲＴ上に線分を
表示する際に使用される。

ピッキングの場合は、この回路の出力をフレームバッフ
ァに書込む代りに、出力された点がピンク範囲内に含ま
れるか否かを判定する回路に導く。

この回路によると、線分上のすべての点についてピンク
範囲に含まれるか否かを判定しなければならない。また
表示する場合と同程度の処理時間を必要とする。

その第２は、ＤＤＡ回路の線分発生とは独立にクリップ
回路を採用するもので、最終的には線分とピック範囲が
交差するか否かを判定するためのピック範囲の境界線と
線分との交点を計算する。

この回路は、線分の始点及び終点のピック範囲に対する
位置を判定することにより、線分上の点を発生しなくて
もピンク判定できるようにしたものである。ピック判定
は、下記の順序で行われる。

（１）ピック範囲の範囲内外を第８図に示す９個の領域
に分割し、それぞれに４ビツトのコードを与える。

（２）入力された線分の始点及び終点が分割した９領域
のどこにあるか調べ、以下の処理を行う。

（イ）始点及び終点のコードの論理積をとり、結果が０
０００でなければ、線分はピック範囲外であるためピッ
クされない。

（［Ｉ）始点又は終点のコードが００００であればコー
ドがｏｏｏｏＯ点はピック範囲内にあるので、ピックさ
れる。

（ハ）上記２例以外の場合はピンク範囲と交差している
可能性があるため、線分とピンク範囲の境界線との交点
を求め、交点が存在すれば、ピックされる。

この方法は、ピック範囲と線分との交点を計算するため
に除算器を必要とする。

その第３は、その交点計算に中点分割法を使用するもの
で、上記第２の回路で（ハ）の部分を実現するには除算
器を必要とするが、これを除算器なしでも実現できるよ
うに中点分割法を利用した回路である。

中点分割法は、第９図に示すように、まず始点及び終点
の間を２等分してＣＩを求め、次にその点Ｃ１と始点と
の中点Ｃ３を求める・・・という中点分割を繰返すこと
により、ピック範囲の境界との交点を求めるもので、例
えば第９図では、Ｃ５が境界と交差していることが得ら
°れる。第２の回路で（イ）もしくは（ロ）以外の場合
、ピック範囲と交差している可能性があるため、線分を
中点で２本に分割し、それぞれの線分について（イ）〜
（ハ）の方法を行う。

この中点分割法では、交点がもとまるまで中点分割を繰
返さなければならない。

〔発明が解決しようとする課題〕

上記各回路には、それぞれ難点がある。

第１の回路では、線分上のすべての点についてビック範
囲に含まれるか否かを判定しなければならない。また表
示する場合と同程度の処理時間を必要とする。

第２の回路は、ビック範囲と線分の交点を計算するため
に除算器を必要とする。

第３の中点分割法は、交点が得られるまで中点分割を繰
返さなければならない。

本発明は、このような課題に鑑みて創案されたもので、
中点分割法を改善し、中点分割を交点が得られるまで繰
返さなくても途中の中点と、その中点に対応する始点と
終点の位置関係で、ビック領域と交差するか否かを判定
することによりピッキング処理を高速化し、ＣＡＤなど
の図形処理における図形選択を効率化したピッキング回
路を提供することを目的としている。

〔課題を解決するための手段〕

本発明における上記課題を解決するための手段は、所定
の範囲の周辺を複数の領域に区分し、線分の始点、終点
及び中点の位置する領域を算出するコード計算回路と、
始点と終点が位置する領域の位置関係により、線分が前
記範囲内を通るか否かを判定するコード判定回路とを備
え、図形を前記範囲内で選択するピッキング回路におい
て、始点、中点及び終点のそれぞれの位置する領域の位
置関係により、線分が前記範囲内を通るか否かを判定し
、これにより判定できない線分に関しては中点分割を行
い、分割された線分の始点、中点及び終点のそれぞれの
位置する領域の位置関係により、線分が前記範囲内を通
るか否かを判定する位置判定回路を備えたピッキング回
路とするものである。

〔作用〕

本発明は、中点分割を利用したピッキング処理に際し、
始点と中点と終点のそれぞれの位置関係の判定を追加す
ることにより、不必要な中点分割を省略するものである
。

第１図は、本発明の原理を示す説明図である。

同図に示すように、指定された始点と終点を結ぶ線分が
ビック範囲と交差するか否かは、例えば、ピック範囲の
左端、右端、下端、上端の各辺の延長線により９個に分
割した領域に対する始点、中点、終点の位置関係で判定
可、能である。例えば■〜■のような位置関係にあれば
交差しないことがわかる。これに対して、■の位置関係
にある線分は交差することが明らかである。また■、■
のような位置関係にある線分は始点、中点、終点の位置
の情報だけでは交差するかしないかの判定はできないの
で、中点分割をする必要がある。

位置判定回路は、例えば分割した領域の位置コードを第
１図の（）内のようにしたとすると、上記判定を下記の
如く行う。

■）中点のコードを求める（始点、終点のコードは予め
求めである）。

■）中点のコードが００００ならば、その中点はピック
範囲に含まれるのでビックされる（■の場合）。

■）始点と中点のコードの論理積が００００でない場合
、終点及び中点のコードの論理積により下記のいずれか
になる。

終点と中点のコードの論理積も００００でなければ、線
分はビック範囲と交差する可能性がないのでビックされ
ない（■〜■の場合）。

終点と中点のコードの論理積がｏｏｏｏの場合、始点と
中点が同じ座標ならばピンクされず、同じ座標でなけれ
ば中点を新始点として新始点と終点の中点を求め、■）
から繰返す（■の場合）。

■）始点と中点のコードの論理積が００００である場合
、終点と中点が同じ座標であればピンクされず、同じ座
標でなければ中点を新路点として始点と新路点の中点を
求め、■）から繰返す（■の場合）。

このように、第１図の■〜■の線分のように、明らかに
ビック範囲内を通らない線分でも、従来では、例えば分
割ができなくなるまで中点分割を繰り返さなければ判定
できなかったのに対し、本発明では、始点、中点、終点
の位置関係により、より速くビック範囲内を通らない線
分が判定されるため、図形選択を効率化できる。

〔実施例〕

以下、図面を参照して、本発明の実施例を詳細に説明す
る。

第２図は、本発明を実施したデイスプレィ装置の一例を
示す概略ブロック図である。同図に示すように、通信制
御回路１１はホストコンピュータ１０から送られてきた
データをデイスプレィプロセッサ１２に与え、デイスプ
レィプロセッサ１２はホストコンピュータ１０から与え
られたデータをデータＲＡＭ１５に格納すると共に、座
標変換回路１６に出力する。座標変換回路１６は、前記
デイスプレィプロセッサ１２から出力された表示データ
（ｘ、ｙ、２）に対して拡大や縮小や回転や平行移動を
行う。この座標変換回路１６から出力されたデータはク
リップ回路１７に与えられ、クリップ回路１７は表示領
域からはみだした線分のクリップを行い、クリップした
結果を直線発生（ＤＤＡ）回路１９に与える。直線発生
回路１９はクリップ回路１７から出力された始点と終点
とを結ぶ線分上の点を発生してフレームメモリ２０に書
き込む。フレームメモリ２０に記憶された各ドツトデー
タはモニタインタフェース２１に与えられ、モニタイン
タフェース２１はフレームメモリ２０上のドツトデータ
を読み出して、同期信号と共にＣＲＴ２２に与える。従
って、ＣＲＴ２２には図形が表示される。

次に、本発明の制御の流れについて説明する。

マウス３１又はタブレット３２を操作すると座標値がデ
イスプレィプロセッサ１２に通知される。

デイスプレィプロセッサ１２は通知された座標値に対応
するＣＲＴ上の位置に第２図に示すようなカーソル２３
を表示する。オペレータは１．マウス３１又はタブレッ
ト３２を操作して、選択したい図形の上にカーソル２３
を移動し、マウス３１もしくはタブレット３２のボタン
が押下されたことがデイスプレィプロセッサ１２に通知
されると、デイスプレィプロセッサ１２はピ・ツク処理
を開始する。まず、状態をピックモードに遷移し、次に
データＲＡＭ１５に格納されている図形データを順に座
標変換回路１６に出力する。座標変換回路１６は図形デ
ータを座標変換する。ビックモードの場合には、座標変
換したデータをクリップ回路１７でなく、本発明のピッ
ク回路１８に出力し、ビック回路１８はその図形データ
がピック範囲と交差するか否かを判定して、結果をデイ
スプレィプロセッサ１２に通知する。デイスプレィプロ
セッサ１２は、判定結果が“ピックされた”場合はその
図形データ情報をホストコンピュータ１０に通知する。

判定結果が“ビックされた“でない場合は次の図形デー
タについてピンクされるか否かの判定を行う。

第３図は、第２図に示した前記ビック回路１８の具体的
な構成図である。同図において、ビ・ツク回路１８は、
コード判定回路２４２位置判定回路２５、コード計算回
路２６．及び始点座標、始点コード、終点座標、終点コ
ード、中点座標、中点コード、ピック範囲の値を登録す
る各レジスタで構成されている。

ピック回路１８に対して、ピンク対象の線分の始点及び
終点の座標を通知すると、まず、コード計算回路２６に
より始点及び終点のコードが演算される。第４図は、コ
ード計算回路２６の処理を示すフローチャートである。

コードとは、図形が定義される空間を第８図に示す如く
、指定されたピック範囲の左端、右端。

上端、下端で９つの領域に分割した場合に、指定された
点が９つの領域のどこに位置するかを示したものである
。各領域は４ビツトの符号を持ち、その４ビツトは、各
ビットが１の時、次のような意味を持つ。

第１ビツト二頂点はピック領域の左端より左方にある。

第２ビツト二頂点はピック領域の右端より右方にある。

第３ビット：頂点はビック領域の下端より下方にある。

第４ビツト二頂点はビック領域の上端より上方にある。

次に、コード計算回路２６で得たコードを使用して、指
定された線分がピックされるかをコード判定回路２４で
判定する。第５図は、この処理を示すフローチャートで
ある。

■始点と終点のコードの論理積をとり、その結果がｏｏ
ｏｏでなければ、線分はピンク範囲外であるため、ピッ
クされない。

■始点又は終点のコードがｏｏｏｏであるとき、コード
がｏｏｏｏである点はピック範囲内にあるので、その線
分はピックされる。

■上記■及び■の判定でピンクされるか否か決定できな
かった場合は、本発明の位置判定回路２５によってピン
ク判定を行う。第６図は、その処理を示すフローチャー
トである。

ｌ）中点の座標を計算し、コード計算回路によりコード
を求める。

中点の座標（ｘ、ｙ）は ｘ−（始点のＸ十終点のＸ）÷２ ｙ＝（始点のｙ十終点のｙ）÷２ である。

■）中点のコードがｏｏｏｏならば中点はピック範囲に
含まれるのでピックされる。

■）始点及び中点のコードの論理積が００００でない場
合は３通りに分けられる。終点及び中点のコードの論理
積もｏｏｏｏでない場合は、線分はピック範囲と交差す
る可能性がないので、ピンクされない。コードの論理積
が００００の場合は、始点と中点が同じ座標ならピ・ツ
クされない。同じ座標でない場合は、中点を新しい始点
とし、始点と終点の中点を求め、１）から処理を繰返す
。

■）始点及び中点のコードの論理積が００００である場
合は２通りに分けられる。終点と中点とが同じ座標なら
ばピックされない。同じ座標でない場合は中点を新しい
終点とし、始点と終点の中点を求め、Ｉ）から処理を繰
返す。

このようにして、コード判定回路２４でピックされるか
否かを判定し、結果を通知する。上記の如く、本実施例
では、明らかにピンクされるもの及び明らかにピンクさ
れないものを検討の途中で判定して行くので、従来より
も処理時間が大幅に短縮されている。

〔発明の効果〕

以上、説明したとおり、本発明によれば、中点分割法を
改善し、中点分割を交点が得られるまで繰返さなくても
途中の中点と、その中点に対応する始点と終点の位置関
係でピック領域と交差するか否かを判定することにより
ピッキング処理を高速化し、ＣＡＤ等の図形処理におけ
る図形選択を効率化したピッキング回路を提供すること
ができる。

２６；コード計算回路。

【図面の簡単な説明】

第１図は本発明の詳細な説明図、 第２〜第３図は本発明の一実施例の構成図、第４〜第６
図は実施例のフローチャート、第７図は一般的な図形処
理システムの構成図、第８図は一般的な判定処理の説明
図、 第９図は従来の中点分割法の説明図である。 １８；ピック回路、 ２４；コード判定回路、 ２５；位置判定回路、 本発明の一実施例の構成図 第２図 本発明の一冥施伊ｊの構成図 第３図 第４図 コード判定舛理のフロー 第５図

Claims (1)

1. 【特許請求の範囲】 所定の範囲の周辺を複数の領域に区分し、線分の始点、
   終点及び中点の位置する領域を算出するコード計算回路
   （２６）と、 始点と終点が位置する領域の位置関係により、線分が前
   記範囲内を通るか否かを判定するコード判定回路（２４
   ）とを備え、 図形を前記範囲内で選択するピッキング回路（１８）に
   おいて、 始点、中点及び終点のそれぞれの位置する領域の位置関
   係により、線分が前記範囲内を通るか否かを判定し、こ
   れにより判定できない線分に関しては中点分割を行い、
   分割された線分の始点、中点及び終点のそれぞれの位置
   する領域の位置関係により、線分が前記範囲内を通るか
   否かを判定する位置判定回路（２５）を備えたことを特
   徴とするピッキング回路。