JPS61117596A - ディジタル線分発生器 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明はディジタル線分発生器に関し、更に詳しくは始
点が直線上にないディジタル線分を高速に発生させるこ
とができるディジタル線分発生器に関する。

（従来の技術） グラフィックディスプレイ装置や数値制御工作機械（Ｎ
Ｏマシン）等の分野では、ディジタル線分やディジタル
円弧等の線図形を高速、高精度で発生する必要がある。

このため、これまで各種の図形発生アルゴリズムが開発
され、このアルゴリズムをハードウェア化した線図形発
生器が考案されている。

ディジタル線分の発生法の一つとして、直線を含む高精
度の２次曲線図形が統一的に発生できる変位比較法が用
いられている。変位比較法は、発生すべき直線の方程式
を ｆ　（ｘ、ｙ）＝ａｘ−ｂｙ＋ｃ−０　　　（１）とし
た時、始点を含む既に選択したドツトの次に選択すべき
ドツトを ＩＦ　　ＭＩＮｌｆ（Ｐｉ）Ｉ−Ｉｆ（Ｐｊ）１ＴＨＥ
Ｎ　　　ＴＡＫＥ　　　Ｐｊ　　　　　　　　　　　（
２）（但しｉ、　ｊｅｒ、Ｉ−１＋　２・・・８）なる
アルゴリズムに基づいて生成する方法である。

ここで、（１）式のａ、ｂ、ｃは定数である。

第８図は前述した候補ドツトの方向選択を説明するため
の図である。Ｐｏ乃至Ｐｓは、ｘｙ平面内のドツト位−
を示す。Ｐｏは前回選択したドツトを、Ｐ１〜Ｐｓは今
回選択すべき候補ドツトをそれぞれ示している。候補ド
ツトＰ１〜Ｐｇのうち、Ｐ　１〜Ｐ４は４画素連結表示
時の候補ドツト、Ｐ１〜Ｐａは８画素連結表示時の候補
ドツトである。第（２）式の■はドツトＰ１〜Ｐ６の番
号を示し、ｆ　（Ｐｉ　）は特定平面φからドツトＰｉ
における変位（詳細後述）を表わしている。

第（１）式は、次式 φ：Ｚ−＝ｆ　（ｘ、ｙ）−ａｘ−ｂｙ＋ｃ　　（３）
で表わされる平面φとｘｙ平面（ｚ−００面）との交線
と考えることができる。第９図は、特定平面φとｘｙｚ
３次元空間内のｘｙ平面との交わりを示す図、第１０図
は特定平面φの断面図である。

第９図のＬが平面φとｘｙ平面との交線である。

ｘｙ平面上の点Ｐｏ　（第８図のＰＯに同じ）から垂直
に伸ばした垂線が特定平面φと交わる場合、Ｐａから交
点Ａｏまでの距離をＩｆ（’Ｐｏ）ｌ又は１Ｚｏｌで表
わし、ｆ　（Ｐｏ　）を平面φからドツトＰａにおける
変位と定義する。

変位比較法は前回選択したＰｏ点の次のドツトを選択す
るのに、第８図Ｐ１〜Ｐｓ′に示す候補点のうちからそ
の変位ｆ　（Ｐｉ　）　　（ｉ　−１〜８）が最小にな
る点を選ぶもめである。即ち、（２）式で変位の絶対値
を比較し、最小の変位を有する候補ドツトを次の選択ド
ツトとして選択するものである。

（発明が解決しようとする同題点）　　゛前述した変位
比較法を用いて、単純な加減算機能のみでディジタル線
分を発生するためには、始点Ｐｓ　　（Ｘｓ　、　Ｖｓ
　）が（１）式で表わされる一線上に存在すること、即
ち、始点における１位２６が０、つまり Ｚｓ　＝ｆ　（Ｐｓ　）−ａＸｓ　−ｂｕｓ　＋ｃ４０
であることが前提になっている。しかしながら、発生す
べき直線の方程式（１）式に対して、Ｘ座標又はｙ座標
の何れか一方の座標をパラメータとして ×６　≦Ｘ≦ｘｅ　　　　　　　　　　　　　（５）又
は　Ｖｓ≦ｙ≦’／ｅ　　　　　　　　　　（６）を満
足する範囲でディジタル線分を発生させる場合には、始
点Ｐｓ　（Ｘｓ　、　Ｖｓ　）の座標及び始点Ｐｓにお
ける変位Ｚｓを求める必要がある。従来方法によれば、
始点Ｐｓ　（Ｘｓ　、　’ｉ／ｓ　）の座標及びＰｓに
おける変位Ｚｓを求めるのに乗除算機能が必要となる。

即ち、ｘｓが与えられる時にはｙ−（ａＸ６　＋０）／
ｂより最も真値に近いディジタル値をｙｓ。

一方ｙ＄が与えられる時にはＸ−（ｂＶｓ−０）／ａよ
り最も真値に近いディジタル値をＸｓとして求め、算出
したＸ９ヌは’Ｉｓの値を用いて、始点Ｐｓ　（ｘ台’
、Ｖｓ　）における変位Ｚｓ　−ａＸｓ”ｂｙｓ４−ｃ
を計算しなければならなかった。

本発明はこのような点に鑑みてなされたものであって、
その目的は、方程式ｆ　（ｘ、ｙ）−ａｘ−ｂｙ＋ｃ−
Ｑで記述され、ｘ６≦Ｘ≦Ｘｅ又はＶｓ≦ｙ≦Ｖｅを満
足するディジタル線分を、変位比較法を用いて単純な加
減算機能のみで高速かつ高精度で発生できる簡単な構成
のディジタル線分発生器を実現することにある。

（問題点を解決するための手段） 前記した問題点を、解決する本発明は、ｘ、ｙを変数、
ａ、ｂ、ｃを既知の定数とする方程式％式％ で記述され、ｘｓ≦Ｘ≦ｘｅ又はｙｓ≦ｙ≦Ｖｅの範囲
を満足するディシル線分を発生する場合に、パラメータ
Ｘ６＋Ｘｅが与えられる場合には、ｙ、ｕを変数、−す
を係数、Ｃを定数とする方程式 ％式％ を、パラメータＶ　ｓ　＊　Ｖ　ｔｓが与えられる場合
には、Ｘ、Ｖを変数、ａを係数、Ｃを定数とする方程式
％式％ をそれぞれ定義し、 これら方程式より、ｆｓ　　（Ｖ、ｕ＞−ｏの近傍点で
ｕ−Ｑを満足するｙ軸上の最も真値に近いディジタル値
’ｊｅ１、又はｆｚ　（ｘ、ｖ）−０の近傍点でｖ−０
を満足するＸ軸上の最も真値に近いディジタル値ｘｅｚ
を、 方程式ｆｔ　　（Ｖ、ｕ）−０の場合にはｆｔ　　（Ｖ
。

ｕ）−〇を満足する点Ｑｓ　ｔ　　（０，ｃ）を、方程
式ｆｚ　　（Ｘ、ｖ＞−ｏの場合にはｆｚ　　（ｘ、ｖ
）−〇を満足する点Ｑｓ　２　　（０，Ｃ）をそれぞれ
始点として与え、変位比較法を適用することにより単純
に加減算機能のみで算出し、 次に、方程式ｆ　（Ｘ、Ｖ）＝Ｏにおいて、Ｐｓｔ　　
（０，”／ｅｔ　）又はＰ８２　　（Ｘｅｚ、Ｏ）を始
点、これらＶｅｌ又はｘｅｚを算出する時に得られた既
知のｆｔ　　（ｙｅ　ｔ　、　Ｏ）又はｆｚ（Ｘｅｚ。

０）をそれぞれの場合の始点の初期変位として与え、こ
れらの値を基にして再度変位比較法を用いることにより
、Ｘｓ≦Ｘ≦Ｘｅ又はｙｓ≦ｙ≦ｙｅの範囲のディジタ
ル線分を、単純に加減算機能のみで発生させるようにし
たことを特徴とするものである。

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

第１図は、本発明の一実施例を示す構成ブロック図であ
る。図に示す装置は、マイクロプログラム制御方式を採
用し、入力制御部１０．出力部２０、レジスタ演算部３
０．及びマイクロプログラム制御部４０の４つの主要部
分より構成されている。

入力制御部１０とレジスタ演算部３０は、内部バスＵＢ
によって相互に連結されている。１０は、システムバス
Ｓ８を経由して上位の計算機等からコマンドを入力・解
読し、初期値設定を制御する入力制御部で、入力レジス
タ１１及びバス制御部１２とから構成されている。２０
は画像メモリ等の外部表示装置（図示せず）にｘ、ｙ座
標値を出力する出力部で、内部バスＵＢを介して送られ
てくる座標データを取込むＸレジスタ２１及びｙレジス
タ２２とから構成されている。これらレジスタ２１．２
２には内部バスＵＢを経由し、てそれぞれの値がセット
される。

３０は数値演算を行うレジスタ演算部で、レジスタアン
ドアリスメチイック・ロジカルユニット（以下ＲＡＬＵ
と略す）３１を中心に構成されている。ＲＡＬＵ３１は
複数個の内部レジスタより構成されるレジスタ群３２を
有し、内部レジスタ間で、例えば加減算、論理積、論理
和演算等の算術演算を行うことができるようになってい
る。更に、ＲＡＬＵ３１での演算結果における各種ステ
ィタスは、マイクロプログラム制御部４０内のマルチプ
レクサへの入力となっている。４０幡全体の制御及び線
分発生のアルゴリズムを実行するマイクロプログラム制
御部で、マルチプレクサ４１゜アドレスシーケンサ４２
．マイクロプログラムメモリ４３及びバイブラインレジ
スタ４４とから構成されている。パイプラインレジスタ
４４は、マイクロプログラムメモリ４３からの出力を保
持し、前述の入力制御部１０．出り部２０及びレジスタ
演算部３０の各部分へのマイクロ命令を供給する。

マイクロプログラムでの条件付分岐は、マルチプレクサ
４１において、レジスタ演算部３０からの各種スティタ
スを含む入力の内、一つを選択しアドレスシーケンサ４
２で判定することによって行われるようになっている。

このように構成された回路の動作を説明すれば以下のと
おりである。

ここでは、ａ、ｂ、ｃを既知の定数として、方程式 ％式％ で記述され、×＄≦Ｘ≦ｘｅ又はＶｓ≦ｙ≦ｙｃ、を満
足するディジタル線分として、第２図に示すように線分
が×ｙ平面の第１象限に存在する場合を例にとって説明
する。第２図において、（イ）はＸｓ≦Ｘ≦ｘｅの場合
を、（ロ）はＶｓ≦ｙ≦’／ｅの場合をそれぞれ示して
いてる。（イ）のＰｓｒ　　（０，”ｉ／ｅｔ　）、　
　（ロ）のＰｓ２　（Ｘ＠ｚ＋０）はそれぞれ直線の発
生始点を、Ｌは線分を示す。

上位の計算機等よりシステムバスＳＢを経由して、線分
のパラメータａ、ｂ、ｃ及びＸの可変パラメータＸＳ＋
Ｘｅ又はｙの可変パラメータｙＳ。

’Ｊｅを入力制御部１０内の入力レジスタ１１にセット
し、上位計算機等から入力制御部１０に対してスタート
起動をかける。スタート起動がかかると、マイクロプロ
グラム制御部４０では、可変パラメータがＸの場合には
入力レジスタ１１内のパラメータ、ａｘ　ｂ　＊　Ｃ＊
　ｘ　６　＋　ｘ　＠を、可変パラメータがｙの場合に
はパラメータａ、ｂ、ｃ、ｙｓ＋Ｖｅを内部バスＵＢを
経由してレジスタ演算部３０内のレジスタ群３２に格納
する。

可変パラメータがｘ、ｙ何れの場合も以下、同様な手順
となるので、ここでは可変パラメータがＸ、即ちＸがｘ
６≦Ｘ≦Ｘｓを満足する範囲でディジタル線分を発生す
る手順について説明する。

この場合は、第１図に示すようにレジスタ演算部３０内
のレジスタ群３２に、上のレジスタから順にパラメータ
ａ＊　ｂ＊　Ｃ＋　×６　＋　×＠が格納される。

先ず、第２図（イ）に示すように、ｙ軸上の点で直線Ｌ
　（Ｌ　：　ａｘ−ｂｙ＋ｃ＝０）に最も近接するドツ
トＰｓ重　（０，Ｖｅ　ｔ　）及びＰｓｔの変位Ｚｓ　
ｔ　＝ｆ　（０，ｙｅ　ｔ　）を求める。そのためにｙ
、ｕを変数、−ｂを係数、Ｃを定数とす□る方程式 ％式％（７） を新たに定義する。そして、ｆｓ　　＜Ｖ、ｕ）”Ｑを
満足する点Ｑｓｔ（０，’ｃ）を始点として、変位比較
法により始点Ｑｓ１より順次１ドツトずつ、最適ドツト
をｕ＝Ｑとなるまで線分Ｌｔ（Ｌｔ’ニーｂｙ＋ｃ−ｕ
＝０）を発生させる。　　　　　・第３図（イ）は、線
分Ｌ１の発生を示す図である。横軸はｙを、縦軸はＵを
それぞれ示しいる。

Ｌｌは（７）式で定義される線分、Ｑｓｌは始点であり
、Ｑｓｔから順次変位比較法によりドツトを発生させ、
線分Ｌ１を発生させている。ｕ−０となった時点で線分
Ｌｌの発生を停止し、その時のｙ座標をｙｅｌ、終点Ｑ
ｅｔ（Ｖｅｔ、Ｏ）の変位Ｚ＠ｔ　−ｆｔ　　（ｙｅ　
ｔ　＊　Ｏ）を再びレジスタ群３２に格納する。

第３図（イ）について説明した操作によＶ）ｙｅ１が求
めると、第２図（イ）に示す始点Ｐｓｓ（０，Ｖｅｔ）
及びＰｓｔの変位Ｚｓ　ｔ　−ｆ　（０゜Ｖｅｘ）が求
まる。そこで、Ｖｅｔ＋変位Ｚ’ｅｔより始点をＰｓｓ
　　（０，”／ａｓ　）、始点Ｐｓ’ｔの変位Ｚｓ　ｔ
　−ｆ　（０，Ｖｅ　ｔ　）＝Ｚｅ　ｔとし、ここで再
度、変位比較法を用いて始点Ｐｓ１より１ドツトずつ最
適ドツトをｘｘｘ６となるまで発生させる。

ｘ−Ｘｓとなった時点より、続けて最適ドツトを発生ぎ
せると同時に、最適ドツトのｘ、ｙ座標値を内部バスＵ
Ｂを介して出力部２０のｘ、ｙレジスタ２１．２２にセ
ットする。この結果、ディジタル線分りが例えばＣＲＴ
上に表示される。上述の動作は線分（−（６ｘ座標上限
値（最終到達点）×ｅ□になるまで繰處される。第４図
は、上述の動作を示すフローチャートである。

このように、本発明によれば、方程式 ％式％ で記述され、ｘ６≦Ｘ≦Ｘｅ’Ｓ−満足するディジタル
線分を単純な加減算機能のみで高速かつ高精度に発生さ
せることができる。以上、可変パラメータが×の場合を
例にとって説明したが、この間の事情は可変パラメータ
がｙの場合についても全（同様である。

即ち、第２図（ロ）に示すように、Ｘ軸上の点で直線Ｌ
　（Ｌ　：　ａｘ−ｂｙ＋ｃ−０）　ニｌｌＩモ近接す
るドツトＰＳ２　　（Ｘｅ２．Ｏ）及びＰＳ２の変位Ｚ
ｓｚ−ｆ（Ｘｅｚ、Ｏ）を求める。そのために、Ｘ、Ｖ
を変数、ａを係数、Ｃを定数とする方程式 ％式％（８） を新たに定義する。そして、ｆ２　（Ｘ、Ｖ）＝０を満
足する点Ｑｓ　２　　（０，ｃ）を始点として、変位比
較法により始点ＱＳ２より順次１ドツトずつ、最適ドツ
トをｖ＝Ｑとなるまで線分Ｌ２　　（Ｌ２　：ａｘ＋ｃ
−ｖ＝ｏ）を発生させる。

第３図（ロ）は、線分Ｌ２の発生を示す図である。横軸
はｙを、縦軸は■をそれぞれ示している。

Ｌ２は（８）式で定義される線分、ＱＳ２は始点であり
、ＱＳ２から順次変位比較法によりドツトを発生させ、
線分Ｌ２を発生させている。以下の動作についてはＸが
可変パラメータの場合と同様であるので説明は省略する
。

第６図は、ａ−２，ｂ＝３．Ｃ−５，Ｘｓ　−３゜Ｘｅ
　−９の場合におけるディジタル線分発生例を示す図で
ある。（イ）はＱｓｓ及びその変位Ｚｅ１算出時の線分
発生を示しており、〈口）は目的とする実際の線分の発
生例を示している。（イ）。

（ロ）何れの図形も、（）内の数値はその点における変
位を示している。

上述の説明においては、ディジタル線分が×ｙ平面の第
１象限に存在する場合について説明した。

しかしながら、本発明は、第１象限に限るものではなく
、第７図（イ）に示すように線分が第２゜３．４象限に
存在する場合にも、同様の手順によりディジタル線分を
発生させることができる。但し、Ｘｓ　、Ｘｅ　＜Ｑ又
は’／　ｓ　＊　Ｖ　ｅ　＜Ｏの場合には、第４図、第
５図のフローチャートにおいて、×＄とｘｅ　＋　’１
／　ｓと’／ｅの関係を入れ替え、Ｘ−Ｘｅからｘ＝ｘ
６の方向へ、又はＶ＝ｙｅがらｙ＝Ｖｓの方向へ線分を
発生させる。

又、線分が第７図（ロ）に示すように２つ以上の象限に
またがって存在する場合には、ｘ−０又はｙ−０を中心
に左右又は上下方向へ、即ちＸ＝０からｘａ−ｘｓの方
向と、ｘ−ＱからＸ−Ｘ、の方向へ、ｙ−ｏからＶ＝ｙ
ｓの方向と、ｙ＝ｏからＶ＝Ｖｅの方向へそれぞれ２つ
に介けて線分を発生させればよい。尚、第７図に線分の
発生方向を矢印で示す。

（発明の効果）　　　゛ 以上詳細に説明したように、本発明によればｆ　（ｘ、
ｙ）−ａｘ−ｂｙ＋ｃ−０ で表わされ、ｘ６≦Ｘ≦Ｘｓ又はＶｓ≦ｙ≦ｙｅなる範
囲を満足するディジタル線分を発生させる場合にそれぞ
れ ｆ　１　　（Ｖ　、　ｕ　）　−−ｂ　ｙ＋ｃ　−ｕ　
＝　Ｑ又はｆ２　（ｘ、ｖ）−ａｘ＋ｃ−ｖ−０ で定義される方程式より始点のｙ座標ｙｅｔ又は×座標
Ｘｅ２を算出して始点を求めた後、変位比較法で線分を
発生させるようにすることにより、単純加算機能のみで
ディジタル線分を高速かつ高精痩に発生させることがで
きる。

【図面の簡単な説明】

第１図は本発明の一実施例を示す構成ブロック図、第２
図はディジタル線分の発生例を示す図、第３　ｍ　′＊
　ｙ・・又は８・・の算出の説明図・第４図、第５図は
本発明の動作を示すフローチャート、第６図はディジタ
ル線分の具体的な発生例を示す図、第７図はディジタル
線分発生例を示す図、第８図は候補ドツトの方向を示す
図、第９図、第１０図は変位比較法の説明図である。 １０・・・入力制御部　　　１１・・・入力レジスタ１
２・・・バス制御部　　　２０・・・出力部２１・・・
Ｘレジスタ　　　２２・・・ｙレジスタ３０・・・レジ
スタ演算部　３１・・・ＲＡＬＬＩ３２・・・レジスタ
群 ４０・・・マイクロプログラム制御部 ４１・・・マルチプレクサ ４２・・・アドレスシーケンサ ４３・・・マイクロプログラムメモリ ４４・・・バイブラインレジスタ ８Ｂ・・・システムバス　　ＵＢ・・・内部バス納２ （イ） 曝 第３ （イ） 図 （ｅＩ） １声

Claims (1)

1. 【特許請求の範囲】 ｘ、ｙを変数、ａ、ｂ、ｃを既知の定数とする方程式 ｆ（ｘ、ｙ）＝ａｘ−ｂｙ＋ｃ＝０ で記述され、ｘ＿ｓ≦ｘ≦ｘ＿ｅ又はｙ＿ｓ≦ｙ≦ｙ＿
   ｅの範囲を満足するディジル線分を発生する場合に、パ
   ラメータｘ＿ｓ、ｘ＿ｅが与えられる場合には、ｙ、ｕ
   を変数、−ｂを係数、ｃを定数とする方程式 ｆ＿１（ｙ、ｕ）＝−ｂｙ＋ｃ−ｕ＝０ を、パラメータｙ＿ｓ、ｙ＿ｅが与えられる場合には、
   ｘ、ｖを変数、ａを係数、ｃを定数とする方程式ｆ＿２
   （ｘ、ｖ）＝ａｘ＋ｃ−ｖ＝０ をそれぞれ定義し、 これら方程式より、ｆ＿１（ｙ、ｕ）＝０の近傍点でｕ
   ＝０を満足するｙ軸上の最も真値に近いディジタル値ｙ
   ＿ｅ＿１、又はｆ＿２（ｘ、ｖ）＝０の近傍点でｖ＝０
   を満足するｘ軸上の最も真値に近いディジタル値ｘ＿ｅ
   ＿２を、 方程式ｆ＿１（ｙ、ｕ）＝０の場合にはｆ＿１（ｙ、ｕ
   ）＝０を満足する点Ｑ＿ｓ＿１（Ｏ、ｃ）を、方程式ｆ
   ＿２（ｘ、ｖ）＝０の場合にはｆ＿２（ｘ、ｖ）＝０を
   満足する点Ｑ＿ｓ＿２（Ｏ、Ｃ）をそれぞれ始点として
   与え、変位比較法を適用することにより単純に加減算機
   能のみで算出し、 次に、方程式ｆ（ｘ、ｙ）＝０において、Ｐ＿ｓ＿１（
   Ｏ、ｙ＿ｅ＿１）又はＰ＿ｓ＿２（ｘ＿ｅ＿２、Ｏ）を
   始点、これらｙ＿ｅ＿１又はＸ＿ｅ＿２を算出する時に
   得られた既知のｆ＿１（ｙ＿ｅ１、Ｏ）又はｆ＿２（ｘ
   ＿ｅ＿２、Ｏ）をそれぞれの場合の始点の初期変位とし
   て与え、これらの値を基にして再度変位比較法を用いる
   ことにより、ｘ＿ｓ≦ｘ≦ｘ＿ｅ又はｙ＿ｓ≦ｙ≦ｙ＿
   ｅの範囲のディジタル線分を、単純に加減算機能のみで
   発生させるようにしたことを特徴とするディジタル線分
   発生器。