JPS6227872A - 交点検出回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の技術分野］ この発明は、線分と指定枠の指定辺との交点の座標を検
出する交点検出回路に関する。

［発明の技術的背景とその問題点］ 近年、電子計算機システムの中で図形処理の要求が増加
している。この処理の基本となるのは、予め定義された
幾何空間の中で、両端の座標値が与えられる線分の表示
である。そして最近では、指定された線分のうち、別に
指定される枠の中に含まれる部分だけを表示する要求が
ある。この指定枠に含まれる部分の切出しは、指定線分
と指定枠との交点の座標を検出することにより行なわれ
る。

従来、上記の交点座標検出は、マイクロプロセッサ等で
行なわれており、多大な処理時間を要していた。そこで
、この種の交点座標検出が高速で行なえるハードウェア
回路の実現が要望されていた。

［発明の目的］ この発明は上記事情に鑑みてなされたものでその目的は
、指定線分と指定枠との交点の座標が、マイクロプロセ
ッサ等から独立して蟲速に検出できる交点検出回路を提
供することにある。

［発明の概要］ この発明では、指定された線分の始点と終点の第１の方
向の座標の差の１　／　２　Ｉｌｌ！である第１差分値
がその小数部を含めて初期設定される第１シフトレジス
タと、第２シフトレジスタとが設けられる。この第２シ
フトレジスタには、上記線分の始点と終点の上記第１の
方向と直交する第２の方向の座標の差の１／２）ｉ１で
ある第２差分値がその小数部を含めて初期設定される。

第１．第２シフトレジスタは、第１クロツク信号に応じ
て右に１ビット算術シフト動作を行なう。これにより、
シフト後の第１．第２シフトレジスタの内容は、シフト
前のそれの１／２の値を示す。

また、この発明では、上記線分の始点の第１゜第２の方
向の座標値が初期設定される第１．第２レジスタが設け
られる。第１レジスタの出力は、第１加算器によって第
１シフトレジスタの出力と加算される。第２レジスタの
出力は、第２加算器によって第２シフトレジスタの出力
と加算される。

第１加算器の加算結果は、比較器によって、上記線分と
の交点検出が要求される指定枠の第２の方向の指定辺の
第１の方向の座標値と比較される。

この結果、比較器からは、大小比較結果を示す第１比較
信号および一致検出結果を示す第２比較信号が出力され
る。

比較器から出力される第１比較信号は、論理回路により
、上記第１差分値の符号に応じてレベル反転される。こ
の論理回路の出力信号は、第１レジスタの出力および第
１加算器の加算結果のいずれか一方を選択する第１選択
器と、第２レジスタの出力および第２加惇器の加算結東
のいずれか一方を選択する第２）３択器に対する選択制
御信号として用いられる。第１．第２選択器の出力は、
ロード手段により、クロック信号に応じて第１．第２レ
ジスタにロードされる。そして、比較器から一致を示す
第２比較信号が出力された際に第１゜第２レジスタにロ
ードされたデータにより、上記線分と指定枠の第２の方
向の指定辺との交点の第１、第２の方向の座標値が示さ
れる。

［発明の実施例］ 以下、この発明の一実施例を第１図乃至第４図を参照し
て説明する。

第１図は交点検出回路のブロック構成を示す。

第１図の交点検出回路は、第２図に示す指定線分ＰＡＰ
日と指定枠Ｗの右辺との交点ＰＲを求めるのに用いられ
る。

ここで、第１図の交点検出回路に適用される交点検出動
作の原理を第３図を参照して説明する。

第３図において、ＰＡ、ＰＢは指定線分ＰＡ　Ｐａの始
点、終点である。始点ＰＡの座標を（Ｘ　Ａ＊ｙＡ）、
終点ＰＢの座標を（Ｘｅ、Ｖ日）とする。

ＰＲは求めようとする線分ＰＡ　Ｐａと枠Ｗの右辺との
交点であり、その座標を（ＸＲ，ＶＲ）とする。交点Ｐ
ＲのＸ座標（ＸＲ）は予め与えられ、Ｘ座標（ｙＲ）を
第１図の交点検出回路により中点分割アルゴリズムを用
いて求める。

ここでは、線分ＰＡ　Ｐａの中点ＰＴｏを求めるために
、線分ＰＡ　ＰＢの終点Ｐａと始点ＰＡのＸ座標の差の
１／２）ｉ！であるΔｘ八と、同じくＸ座標の差の１　
／２）！［であるΔｙＡとが予め与えられる。

ここで、ΔＸＡ　−（ＸＢ　−ＸＡ　）／２．ΔｙＡ＝
＋＝（Ｖｓ−Ｖ＾）／２である。線分ＰＡ　ＰＢの中点
ＰＴｏのＸ座標は始点ＰＡのＸ座標とΔＸＡとにより求
められ、同じくＸ座標は始点ＰＡのＸ座標とΔｙＡとに
より求められる。もし、始点ＰＡおよび中点Ｐ　Ｔ　Ｏ
が第３図に示すように枠Ｗの右辺（Ｘ−ＸＲ）に対して
同じ側にあるときは、交点ＰＲはＰＴ、とＰａとの間に
あることから、今度はＰＴ。

とＰａとの中点ＰＴ＋が求められる。これに対して始点
ＰＡおよび中点ＰＴｏが枠Ｗの右辺（Ｘ−ＸＲ＞に対し
て互いに反対側にあるときは、交点ＰＲはＰＡとＰＴｏ
との間にあることから、今度はＰＡとＰＴｏどの中点Ｐ
Ｔ！が求められる。以上の動作を繰返すことにより、新
たに求められる中点ＰＴｉが求める交点ＰＲに近付いて
いく。ヤがてＸ座標がＸＲに一致する中点ＰＴｎが求め
られると、その中点ＰＴｎが求めようとする枠Ｗ（の右
辺）との交点ＰＲとなる。

第１図の交点検出回路において、Ｉｔ、　１２はΔＸ　
Ａ　＋Δｙ＾が初期設定されシフト用のクロック信号Ｃ
ＬＫＧにより右に１ビツト算術シフトするシフトレジス
タである。ΔＸＡ、ΔｙＡは、１ビツトのサイン・ビッ
トを含む４１ビツトの整数゛である。負数は２の補数で
表わされる。シフトレジスタ１１．１２のピッ］・長は
、整数部４１ビットおよび小数部７ピツトの４８ビツト
である。シフトレジスタ１１．１２のＭＳＢ側直列入力
端には、ΔｘＡ、ΔｙＡのサイン・ビット（Ｓ）を保持
するフリップフロップ１３．１４の出力が接続されてい
る。

１５は第２図に示す枠Ｗの右辺のｘＪｉｌ標×Ｒを保持
するレジスタである。ＸＲは、１ビットのサイン・ビッ
トを含む４０ビツトの整数である。１６゜１７はＸＡ、
ｙＡが初期設定されるレジスタである。

ＸＡ、ＭＡは、１ビツトのサイン・ビットを含む４０ビ
ツトの整数である。レジスタ１６．１７のビット長は、
整数部４０ビットおよび小数部７ビツトの４７ビツトで
ある。

上記したように、シフトレジスタ１１．１２およびレジ
スタ１６．１７のビット長は、各パラメータの最大ビッ
ト長より良くなっている。これは、演算精度を保証する
ために、各パラメータの小数点以下の値を保持するよう
にしたことによる。整数部のビット長をｍ１小数部のビ
ット長をｎとすると、これらの間には２ｎ　＞ｍの関係
がある。なお小数部（ここでは７ビツト）には、後述す
るように“ＯＩｔが初期設定される。

さて、上記のＸＡ、ｙＡ、ΔｘＡ、Δ’１／Ａ。

ＸＲは図示せぬマイクロプロセッサにより用意される。

即ちマイクロプロセッサは、第１図の交点検出回路の動
作に先立って、Ｘ　Ａ＊　Ｖ　ｘをレジスタ１６．１７
に、ΔｘＡ、ΔｙＡをシフトレジスタ１１゜１２に、そ
してｘＲをレジスタ１５に、それぞれ供給する。その後
マイクロプロセッサは、交点検出回路起動用のスタート
信号ＳＴＲを第４図に示すように１サイクルＯＮする。

マイクロプロセッサからのスタート信号ＳＴＲは、タイ
ミング制御回路１８に供給される。タイミング制御回路
１８には、基本のクロック信号ＣＬＫが常時供給されて
いる。タイミング制御回路１８は、スタート信号ＳＴＲ
がＯＮされると、クロック信号ＣＬＫに同期したクロッ
ク信号ＣＬＫＬを１サイクルだ・け出力し、次のサイク
ルよりクロック信号ＣＬＫに同期したクロック信号ＣＬ
ＫＣを繰返し出力するように構成されている。タイミン
グ制御回路１８からのクロック信号ＣＬＫＬはシフトレ
ジスタ１１．１２およびレジスタ１５〜１７に供給され
、同じくクロック信号ＣＬＫＣはシフトレジスタ１１゜
１２およびレジスタ１６．１７に供給される。

タイミングＩＩＪ　１ｕ１１回路１８からのクロック信
号ＣＬ　Ｋ　Ｌがシフトレジスタ１１．１２およびレジ
スタ１５〜１７に供給されると、ΔｘＡ、ΔｙＡがシフ
トレジスタ１１．１２の整数部に、ＸＲがレジスタ１５
に、そしてＸＡＩＶＡがレジスタ１６．１７の整数部に
、それぞれロードされる。このときシフトレジスタ１１
、１２およびレジスタ１６．１７の小数部には０”がロ
ードされる。

レジスタ１６．１７の出力は加算器１９．２０の六入力
に接続され、シフトレジスタ１１．１２の出力は加算器
１９．２０の８入力に接続される。ここでレジスタ１６
、１７の出力〈４７ビツト）をＸ＋　、Ｖ＋　、シフト
レジスタｉｔ、　１２の出力をΔｘｌ、Δｙ１とする。

ｉは対応データが何回目のロードデータであるかを示す
もので、りＯツク信号ＣＬＫＬによりｘＡ。

Ｖｈ、ΔｘＡ、ΔｙＡがロードされた初期状態では０で
ある。

加算器１９はレジスタ１６からの×１とシフトレジスタ
１１からのΔｘ１との加算×１＋Δｘ１を行ない、中点
ＰＴ１のＸ座Ｉ　ＸＴ、を出力する。また加算器２０は
レジスタ１７からのｙｌとシフトレジスタ１２からのΔ
ｙ１との加ｌｙｔ＋Δｙ１を行ない、中点Ｐ　のｙ座標
ｙＴ、を出力する。加算器１９．２０の最初の加算結果
ＸＴｏ　、ＶＴｏは、ＸＱ＋ΔＸｏ　　（＝ＸＡ＋ΔＸ
Ａ）、”Ｉ１０＋Δ’Ｔ’Ｏ（＝ｙＡ＋ΔｙＡ）となり
、線分ＰＡ　Ｐａの中点ＰＴｏのｘ、ｙ座標ｘ　　、ｙ
　　を示す。加算器１９．２０の出力（ＸＴ　ｏ＊Ｔ６
　　　　　Ｔ。

ＶＴｏ　）は、１ビットのサイン・ビットを含む４０ピ
ツトの整数部と、７ピツトの小数部から成る。

加算器１９の出力ＸＴｏの整数部は比較器２）の六入力
に接続される。比較器２）０Ｂ入力にはレジスタ１５の
出力ｘＲが接続される。比較器２）は、Ａ、Ｂ入力を比
較、即ち中点ＰＴｉのＸ座標ＸＴｉの整数部（ここでは
点ＰＴｏのＸ座標ＸＱ＋ΔＸｏ　）と枠Ｗの右辺のＸ座
ｔｌｌＸＲを比較し、大小比較結果を示す第１比較信号
Ｆ（Ａ≦Ｂで’１”）と一致検出結果を示す第２比較信
号（Ａ−８で“”１”）とを出力する。この第２比較信
号は“１″で交点検出の終了を示すことから、終了検出
信号ＥＮＤと呼ぶ。

比較器２）からの比較信号Ｆは排他的論理和ゲート（Ｘ
ＯＲ）２２の一方の入力に接続される。排他的論理和ゲ
ート２２の他方の入力には、フリップフロップ１３の出
力、即ちΔＸＡ（ΔＸ＋）のサイン・ビットが接続され
る。排他的論理和ゲート２２は、信号Ｆと７リツプ７０
ツブ１３からのサイン・ビットとの排他的論理和をとる
。排他的論理和ゲート２２の出力は、レジスタ１６．１
７の出力Ｘ＋　、Ｖ＋の示す点くここではＰＡ）と中点
Ｐ７１とが、枠Ｗの右辺（Ｘ＝Ｘｙｚ　）に対して同じ
側にあるか否かを示す。排他的論理和ゲート２２の出力
は２人力１出力の選択器２３．２４の選択指定入力に接
続される。

選択器２３．２４の六入力にはレジスタ１６．１７の出
力ｘｉ　、　’ｉ／ｌが接続され、選択器２３．２４の
８入力には加算器１９．２０の出力ｘ’ｒｔ、ｙ’ｒｔ
が接続される。

選択器２３．２４は、Ａ、８両入力のいずれか一方を排
他的論理和ゲート２２の出力に応じて選択する。

例えば排他的論理和ゲート２２の出力が１′の場合、即
ちレジスタ１６．１７の出力ＸＩ　、Ｖ＋の示す点（こ
こではＰＡ）と中点Ｐア、とが、枠Ｗの右辺（Ｘ−ＸＲ
）に対して同じ側にある場合、選択器２３、２４は加算
器１９．２０の出力ＸＴＨ、ｙＴｔ　（即ち中点ＰＴｉ
の座標）を選択する。これに対して排他的論理和ゲート
２２の出力がＯ″の場合、即ちレジスタ１６．１７の出
力Ｘｉ　、　ｙｌの示す点（ここではＰＡ）と中点ＰＴ
ｉとが、枠Ｗの右辺（Ｘ＝ＸＲ）に対して互いに反対側
にある場合、選択器２３．２４はレジスタ１６．１７の
出力ＸＩ　、　ｙｌを選択する。

第３図の例では、ＰＡとＰＴ、とが枠Ｗの右辺に対して
同じ側にある。したがって最初のサイクル（第０サイク
ル）ではＰＴ、が選択される。

選択器２３．２４の出力はレジスタ１６．１７の入力に
接続される。レジスタ１６．１７には前記したようにタ
イミング制御回路１８からのクロック信号ＣＬＫＣが供
給される。しかして、選択器２３．２４の出力は、クロ
ック信号ＣＬＫＣに応じてレジスタ１Ｇ。

１７にロードされる。ここでは、第０サイクルにおいて
レジスタ１６．１７にロードされる選択器２３．２４の
出力（座標値）は、上記したようにＰＴｏのＸ座標ＸＴ
（＋１　’／座標ｙ１ｏである。もし、ＰＡとＰＴｏと
が枠Ｗの右辺に対して互いに反対側にあれば、第０サイ
クルにおいては、レジスタ１６．１７には点ＰＡの座標
が再ロードされることになる。

タイミング制御回路１８からのクロック信号ＣＬＫＣは
、前記したようにシフトレジスタ１１．１２にも供給さ
れる。これによりシフトレジスタ１１．１２では、（選
択器２３．２４の出力がレジスタＩＧ、　１７にロード
されるタイミングで）右に１ピツト算術シフトが行なわ
れる。この結果、前のサイクルにおけるシフトレジスタ
１１．１２の内容の１／２の値が新たなΔｘｌ、ΔＶ＋
（ｉ−ｉ＋１）としてシフトレジスタ１１．１２内に求
められる。なお、上記のシフト時には、シフトレジスタ
１１．１２のＭＳＢ（Ｊｌ上位ビット）位置に７リツプ
フロツブ１３．１４からのサイン・ビットが入力される
。

次のサイクルでは、シフトレジスタ１１．１２に求めら
れた新たなΔｘｌ、Δｙ＋　　（ここではΔＸｌ。

Δｙ１の１／２値であるΔｘ２．ΔＶ２　）と、レジス
タ１６．１７にロードされた新たなＸＩ　、Ｖ＋（ここ
では点ＰＴ０の座標）を用いて、上記の場合と同様の演
算が行なわれる。即ち、加算器１９．２０により、前の
サイクルでの中点ＰＴＯと終点Ｐａを結ぶ線分の新たな
中点ＰＴ１の座標Ｘ　Ｔ　１　＊　Ｖ　Ｔ　Ｉが求めら
れる。次に比較器２）および排他的論理和ゲート２２に
より、レジスタ１６．１７の示す点（ここでは前の中点
ＰＴｏ）と加算器１９．２０により求められた新たな中
点ＰＴｌとが、枠Ｗの右辺（Ｘ＝ＸＲ）に対して同じ側
にあるか否かが検出される。続いて、この検出結果によ
り、次の中点を求める際の始点となる座標がレジスタ１
６．１７に求められる。そして、以上の動作を繰返すこ
とにより各サイクル毎に新たに求められる中点は、求め
る交点ＰＲに近付く。

やがて、第ｎサイクルにおいて、加算器１９の出力ＸＴ
＋ｖ（−ＸｒＬ＋ΔＸｎ＞がＸＲに一致すると、第４図
に示すように比較器２）から論理“１”の終了検出信号
ＥＮＤが出力される。この終了検出信号ＥＮＤはタイミ
ング制御回路１８に供給される。

このときレジスタ１６．１７の出力Ｘｎ、Ｖｎ　（これ
らはＰＲの座標を示す）は、タイミング制御回路１８か
らのクロック信＠ＣＬＫＣにより、同レジスタ１６．１
７に再ロードされる。タイミング制御回路１８は、比較
器２）から論理１１１　ＩＩの終了検出信号ＥＮＤを受
取ると、第４図に示すように、終了信号５ＴＯＰを出力
し、且つクロック信号ＣＬＫＣの出力を停止する。終了
信号５ＴＯＰは、線分ＰＡＰａと枠Ｗ〈ここでは枠Ｗの
右辺）との交点ＰＲの検出終了を示す。したがって、論
理“１”の終了検出信号ＥＮＤ出力時におけるレジスタ
１６．１７の再ロード内容（これをｘ　１ａｓｔ、　Ｖ
　１ａｓｔと呼ぶ）の整数部が、求める交点ＰＲのＸ座
標ＸＲ，Ｖ座標ｙＲとなる。

さて、この実施例では、第１図の交点検出回路を第１交
点検出回路とすると、第１交点検出回路の他に第１交点
検出回路と同様の回路構成を有する第２乃至第４交点検
出回路が用意される。第２交点検出回路は線分ＰＡＰ日
と枠Ｗの左辺との交点検出に用いられる。この第２交点
検出回路は、第１図に示すレジスタ１５に枠Ｗの左辺の
Ｘ座標値が初期設定きれる点を除いて、第１交点検出回
路と同じである。また第３交点検出回路は線分ＰＡＰａ
と枠Ｗの上辺との交点検出に、第４交点検出回路は線分
ＰＡ　ＰＨと枠Ｗの下辺との交点を求めるのに用いられ
る。第３．第４交点検出回路は、第１図の交点検出回路
においてｘ、ｙを相互に入替えたものとなる。第１閏の
交点検出回路を第３゜第４交点検出回路に用いる場合、
レジスタ１５には指定枠Ｗの上辺、下辺のｙ座標が初期
設定される。

このような第１乃至第４交点検出回路を同時に起動する
ことにより、指定線分ＰＡ　ＰＢと指定枠Ｗとの交点が
全て求められる。なお、第３図の例では、線分ＰＡ　Ｐ
ａと枠Ｗの交点は、枠Ｗの左辺、上辺および下辺には存
在しない。この場合、マイクロプロセッサは第１交点検
出回路のみ起動する。

第１乃至第４交点検出回路には、直線線発生器が接続さ
れるようになっている。したがって直線線発生器は、マ
イクロプロセッサにより起動された全ての交点検出回路
から終了信号５ＴＯＰ信号が出力されると、対応する交
点検出回路で検出された交点の座標に基づいて直線（第
３図の例であれば、線分ＰＡ　ＰＲ）を発生することが
できる。

なお、第１乃至第４交点検出回路で求められた交点が枠
Ｗ外に存在することがある。しかし、この種の交点は、
枠Ｗの左右辺のＸ座標または上下辺のｙ座標との比較に
より、Ｐ！Ｉｗｉにリジェクトできる。

ところで線分ＰＮＰ日と枠Ｗの交点が、枠Ｗの左辺、右
辺、上辺および下辺のいずれに存在するかは、マイクロ
プロセッサにより予め検出することが可能である。例え
ば線分ＰＡ　ＰＢと枠Ｗの左右辺との交点の有無は、Ｐ
Ａ、ＰＢのＸ座標と左右辺のＸ座標との比較により検出
可能である。また線分ＰＡ　Ｐａと枠Ｗの上下辺との交
点の有無は、ＰＡ、ＰＢのｙ座標と上下辺のｙ座標との
比較により検出可能である。

［発明の効果］ 以上詳述したようにこの発明によれば、指定線分と指定
枠との交点の座標検出に必要な浮動小数点演算を含む処
理が、ハードウェア回路により高速に行なえる。しかも
マイクロプロセッサ等は、本回路による演算と並行して
次の演算の準備を行なえることから、処理の一層の轟速
化が図れる。

【図面の簡単な説明】

第１図はこの発明の一実施例に係る交点検出回路のブロ
ック構成図、第２図は指定線分と指定枠との交点を説明
する図、第３図はこの発明の詳細な説明するための図、
第４図は動作を説明するためのタイミングチャートであ
る。 １１、１２・・・シフトレジスタ、１５〜１７・・・レ
ジスタ、１８・・・タイミング制御回路、１９．２０・
・・加算器、２）・・・比較器、２２・・・排他的論理
和ゲート（ＸＯＲ）、２３゜２４・・・選択器。

Claims (2)

【特許請求の範囲】
1. （１）指定された線分の始点と終点の第１の方向の座標
   の差の１／２値である第１差分値がその小数部を含めて
   初期設定され、クロック信号に応じて右に１ビット算術
   シフトする第１シフトレジスタと、 上記線分の始点と終点の上記第１の方向と直交する第２
   の方向の座標の差の１／２値である第２差分値がその小
   数部を含めて初期設定され、上記クロック信号に応じて
   右に１ビット算術シフトする第２シフトレジスタと、 上記線分の始点の第１の方向の座標値が初期設定される
   第１レジスタと、 上記線分の始点の第２の方向の座標値が初期設定される
   第２レジスタと、 上記第１レジスタおよび上記第１シフトレジスタの各出
   力間の加算を行なう第１加算器と、上記第２レジスタお
   よび上記第２シフトレジスタの各出力間の加算を行なう
   第２加算器と、上記線分との交点検出が要求される指定
   枠の第２の方向の指定辺の第１の方向の座標値と上記第
   １加算器の加算結果とを比較し、大小比較結果を示す第
   １比較信号および一致検出結果を示す第２比較信号を出
   力する比較器と、 この比較器から出力される上記第１比較信号を上記第１
   差分値の符号に応じてレベル反転する論理回路と、 この論理回路の出力に応じて上記第１レジスタの出力お
   よび上記第１加算器の加算結果のいずれか一方を選択す
   る第１選択器と、 上記論理回路の出力に応じて上記第２レジスタの出力お
   よび上記第２加算器の加算結果のいずれか一方を選択す
   る第２選択器と、 上記クロック信号に応じ、上記第１選択器の出力を上記
   第１レジスタに、上記第２選択器の出力を上記第２レジ
   スタに、それぞれロードするロード手段と、 を具備し、 上記比較器から一致を示す上記第２比較信号が出力され
   た際に上記第１、第２レジスタにロードされたデータが
   上記線分と指定枠の第２の方向の指定辺との交点の第１
   、第２の方向の座標値を示すことを特徴とする交点検出
   回路。
2. （２）上記論理回路が排他的論理和ゲートであることを
   特徴とする特許請求の範囲第１項記載の交点検出回路。