JPH0453318B2 - - Google Patents

Description

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

（従来の技術） グラフイツクデイスプレイ装置や数値制御工作
機械（NCマシン）等の分野では、デイジタル線
分やデイジタル円弧等の線図形を高速、高精度で
発生する必要がある。このため、これまで各種の
図形発生アルゴリズムが開発され、このアルゴリ
ズムをハードウエア化した線図形発生器が考案さ
れている。

デイジタル線分の発生法の一つとして、直線を
含む高精度の２次曲線図形が統一的に発生できる
変位比較法が用いられている。変位比較法は、発
生すべき直線の方程式を ｆ（ｘ，ｙ）＝ax−by＋ｃ＝０ (1) とした時、始点を含む既に選択したドツトの次に
選択すべきドツトを IF MIN｜ｆ（Pi）｜＝｜ｆ（Pj）｜ THEN TAKE Pj (2) （但しｉ，ｊ〓Ｉ，Ｉ＝１，２……８） なるアルゴリズムに基づいて生成する方法であ
る。ここで、(1)式のａ，ｂ，ｃは定数である。

第８図は前述した候補ドツトの方向選択を説明
するための図である。P₀乃至P₈は、xy平面内の
ドツト位置を示す。P₀は前回選択したドツトを、
P₁〜P₈は今回選択すべき候補ドツトをそれぞれ
示している。候補ドツトP₀〜P₈のうち、P₁〜P₄
は４画素連結表示時の候補ドツト、P₁〜P₈は８
画素連結表示時の候補ドツトである。第(2)式のＩ
はドツトP₁〜P₈の番号を示し、ｆ（Pi）は特定平
面φからドツトPiにおける変位（詳細後述）を表
わしている。

第(1)式は、次式 φ：Ｚ＝ｆ（ｘ，ｙ）＝ax−by＋ｃ (3) で表わされる平面φとxy平面（ｚ＝０の面）と
の交線と考えることができる。第９図は、特定平
面φとxyz3次元空間内のxy平面との交わりを示
す図、第１０図は特定平面φの断面図である。第
９図のＬが平面φとxy平面との交線である。xy
平面上の点P₀（第８図のP₀に同じ）から垂直に伸
ばした垂線が特定平面φと交わる場合、P₀から
交点A₀までの距離を｜ｆ（P₀）｜又は｜Z₀｜で表
わし、ｆ（P₀）を平面φからドツトP₀における変
位と定義する。

変位比較法は前回選択したP₀点の次のドツト
を選択するのに、第８図P₁〜P₈に示す候補点の
うちからその変位ｆ（Pi）（ｉ＝１〜８）が最小に
なる点を選ぶものである。即ち、(2)式で変位の絶
対値を比較し、最小の変位を有する候補ドツトを
次の選択ドツトとして選択するものである。

（発明が解決しようとする問題点） 前述した変位比較法を用いて、単純な加減算機
能のみでデイジタル線分を発生するためには、始
点P_s（x_s，y_s）が(1)式で表わされる直線上に存在
すること、即ち、始点における変位Z_sが０、つま
り Z_s＝ｆ（P_s）＝ax_s−by_s＋ｃ＝０ (4) であることが前提になつている。しかしながら、
発生すべき直線の方程式(1)式に対して、ｘ座標又
はｙ座標の何れか一方の座標をパラメータとして x_s≦ｘ≦x_e (5) 又は、 y_s≦ｙ≦y_e (6) を満足する範囲でデイジタル線分を発生させる場
合には、始点P_s（x_s，y_s）の座標及び始点P_sにお
ける変位Z_sを求める必要がある。従来方法によれ
ば、始点P_s（x_s，y_s）の座標及びP_sにおける変位
Z_sを求めるのに乗除算機能が必要となる。

即ち、x_sが与えられる時にはｙ＝（ax_s＋ｃ）／
ｂより最も真値に近いデイジタル値をy_s，一方y_s
が与えられる時にはｘ＝（by_s−ｃ）／ａより最も
真値に近いデイジタル値をx_sとして求め、算出し
たx_s又はy_sの値を用いて、始点P_s（x_s，y_s）にお
ける変位Z_s＝ax_s−by_s＋ｃを計算しなければなら
なかつた。

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

（問題点を解決するための手段） 前記した問題点を解決する本発明は、ｘ，ｙを
変数、ａ，ｂ，ｃを既知の定数とする方程式 ｆ（ｘ，ｙ）＝ax−by＋ｃ＝０ で記述され、x_s≦ｘ≦x_e又はy_s≦ｙ≦y_eの範囲を
満足するデイジル線分を発生する場合に、 パラメータx_s，x_eが与えられる場合には、ｙ，
ｕを変数、−ｂを係数、ｃを定数とする方程式 f₁（ｙ，ｕ）＝−by＋ｃ−ｕ＝０ を、パラメータy_s，y_eが与えられる場合には、
ｘ，ｖを変数、ａを係数、ｃを定数とする方程式 f₂（ｘ，ｖ）＝ax＋ｃ−ｖ＝０ をそれぞれ定義し、 これら方程式より、f₁（ｙ，ｕ）＝０の近傍点で
ｕ＝０を満足するｙ軸上の最も真値に近いデイジ
タル値y_e1、又はf₂（ｘ，ｖ）＝０の近傍点でｖ＝
０を満足するｘ軸上の最も真値に近いデイジタル
値x_e2を、 方程式f₁（ｙ，ｕ）＝０の場合にはf₁（ｙ，ｕ）＝
０を満足する点Q_s1（０，ｃ）を、方程式f₂（ｘ，
ｖ）＝０の場合にはf₂（ｘ，ｖ）＝０を満足する点
Q_s2（０，Ｃ）をそれぞれ始点として与え、変位比
較法を適用することにより単純に加減算機能のみ
で算出し、 次に、方程式ｆ（ｘ，ｙ）＝０において、P_s1
（０，y_e1）又はP_s2（x_e2，０）を始点、これらy_e1
又はx_e2を算出する時に得られた既知のf₁（y_e1，
０）またはf₂（x_e2，０）をそれぞれの場合の始点
の初期変位として与え、これらの値を基にして再
度変位比較法を用いることにより、x_s≦ｘ≦x_e又
はy_s≦ｙ≦y_eの範囲のデイジタル線分を、単純に
加減算機能のみで発生させるようにしたことを特
徴とするものである。

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

第１図は、本発明の一実施例を示す構成ブロツ
ク図である。図に示す装置は、マイクロプログラ
ム制御方式を採用し、入力制御部１０、出力部２
０、レジスタ演算部３０及びマイクロプログラム
制御部４０の４つの主要部分より構成されてい
る。入力制御部１０とレジスタ演算部３０は、内
部バスUBによつて相互に連結されている。１０
は、システムバスSBを経由して上位の計算機等
からコマンドを入力・解読し、初期値設定を制御
する入力制御部で、入力レジスタ１１及びバス制
御部１２とから構成されている。２０は画像メモ
リ等の外部表示装置（図示せず）にｘ，ｙ座標値
を出力する出力部で、内部バスUBを介して送ら
れてくる座標データを取込むｘレジスタ２１及び
ｙレジスタ２２とから構成されている。これらレ
ジスタ２１，２２には内部バスUBを経由してそ
れぞれの値がセツトされる。

３０は数値演算を行うレジスタ演算部で、レジ
スタアンドアリスメテイツク・ロジカルユニツト
（以下RALUと略す）３１を中心に構成されてい
る。RALU３１は複数個の内部レジスタより構
成されるレジスタ群３２を有し、内部レジスタ間
で、例えば加減算、論理積、論理和演算等の算術
演算を行うことができるようになつている。更
に、RALU３１での演算結果における各種ステ
イタスは、マイクロプログラム制御部４０内のマ
ルチプレクサへの入力となつている。４０は全体
の制御及び線分発生のアルゴリズムを実行するマ
イクロプログラム制御部で、マルチプレクサ４
１、アドレスシーケンサ４２、マイクロプログラ
ムメモリ４３及びパイプラインレジスタ４４とか
ら構成されている。パイプラインレジスタ４４
は、マイクロプログラムメモリ４３からの出力を
保持し、前述の入力制御部１０、出力部２０及び
レジスタ演算部３０の各部分へのマイクロ命令を
供給する。マイクロプログラムでの条件付分岐
は、マルチプレクサ４１において、レジスタ演算
部３０からの各種ステイタスを含む入力の内、一
つを選択しアドレスシーケンサ４２で判定するこ
とによつて行われるようになつている。このよう
に構成された回路の動作を説明すれば以下のとお
りである。

ここでは、ａ，ｂ，ｃを既知の定数として、方
程式 ｆ（ｘ，ｙ）＝ax−by＋ｃ＝０ で記述され、x_s≦ｘ≦x_e又はy_s≦ｙ≦y_eの範囲を
満足するデイジタル線分として、第２図に示すよ
うに線分がxy平面の第１象限に存在する場合を
例にとつて説明する。第２図において、イはx_s≦
ｘ≦x_eの場合を、ロはy_s≦ｙ≦y_eの場合をそれぞ
れ示していてる。イのP_s1（０，y_e1）、ロのP_s2
（x_e2，０）はそれぞれ直線の発生始点を、Ｌは線
分を示す。

上位の計算機等よりシステムバスSBを経由し
て、線分のパラメータａ，ｂ，ｃ及びｘの可変パ
ラメータx_s，x_e又はｙの可変パラメータy_s，y_eを
入力制御部１０内の入力レジスタ１１にセツト
し、上位計算機等から入力制御部１０に対してス
タート起動をかける。スタート起動がかかると、
マイクロプログラム制御部４０では、可変パラメ
ータがｘの場合には入力レジスタ１１内のパラメ
ータ、ａ，ｂ，ｃ，x_s，x_eを、可変パラメータが
ｙの場合にはパラメータａ，ｂ，ｃ，y_s，y_eを内
部バスUBを経由してレジスタ演算部３０内のレ
ジスタ群３２に格納する。

可変パラメータがｘ，ｙ何れの場合も以下、同
様な手順となるので、ここでは可変パラメータが
ｘ、即ちｘがx_s≦ｘ≦x_eを満足する範囲でデイジ
タル線分を発生する手順について説明する。この
場合は、第１図に示すようにレジスタ演算部３０
内のレジスタ群３２に、上のレジスタから順にパ
ラメータａ，ｂ，ｃ，x_s，x_eが格納される。

先ず、第２図イに示すように、ｙ軸上の点で直
線Ｌ（Ｌ：ax−by＋ｃ＝０）に最も近接するドツ
トP_s1（０，y_e1）及びP_s1の変位Z_s1＝ｆ（０，y_e1）
を求める。そのためにｙ，ｕを変数、−ｂを係数、
ｃを定数とする方程式 f₁（ｙ，ｕ）＝−by＋ｃ−ｕ＝０ (7) を新たに定義する。そして、f₁（ｙ，ｕ）＝０を満
足する点Q_s1（０，ｃ）を始点として、変位比較法
により始点Q_s1より順次１ドツトずつ、最適ドツ
トをｕ＝０となるまで線分L₁（L₁：−by＋ｃ−ｕ
＝０）を発生させる。

第３図イは、線分L₁の発生を示す図である。
横軸はｙを、縦軸はｕをそれぞれ示しいる。L₁
は(7)式で定義される線分、Q_s1は始点であり、Q_s1
から順次変位比較法によりドツトを発生させ、線
分L₁を発生させている。ｕ＝０となつた時点で
線分L₁の発生を停止し、その時のｙ座標をy_e1、
終点Q_e1（y_e1，０）の変位Z_e1＝f₁（y_e1，０）を再
びレジスタ群３２に格納する。

第３図イについて説明した操作によりy_e1が求
めると、第２図イに示す始点P_s1（０，y_e1）及び
P_s1の変位Z_s1＝ｆ（０，y_e1）が求まる。そこで、
y_e1、変位Z_e1より始点をP_s1（０，y_e1）、始点P_s1の
変位Z_s1＝ｆ（０，y_e1）＝Z_e1とし、ここで再度、
変位比較法を用いて始点P_s1より１ドツトずつ最
適ドツトをｘ＝x_sとなるまで発生させる。

ｘ＝x_sとなつた時点より、続けて最適ドツトを
発生させると同時に、最適ドツトのｘ，ｙ座標値
を内部バスUBを介して出力部２０のｘ，ｙレジ
スタ２１，２２にセツトする。この結果、デイジ
タル線分Ｌが例えばCRT上に表示される。上述
の動作は線分Ｌのｘ座標上限値（最終到達点）x_e
になるまで繰返される。第４図は、上述の動作を
示すフローチヤートである。

このように、本発明によれば、方程式 ｆ（ｘ，ｙ）＝ax−by＋ｃ＝０ で記述され、x_s≦ｘ≦x_eを満足するデイジタル線
分を単純な加減算機能のみで高速かつ高精度に発
生させることができる。以上、可変パラメータが
ｘの場合を例にとつて説明したが、この間の事情
は可変パラメータがｙの場合についても全く同様
である。

即ち、第２図ロに示すように、ｘ軸上の点で直
線Ｌ（Ｌ：ax−by＋ｃ＝０）に最も近接するドツ
トP_s2（x_e2，０）及びP_s2の変位Z_s2＝ｆ（x_e2，０）
を求める。そのために、ｘ，ｖを変数、ａを係
数、ｃを定数とする方程式 f₂（ｘ，ｖ）＝ax＋ｃ−ｖ＝０ (8) を新たに定義する。そして、f₂（ｘ，ｖ）＝０を満
足する点Q_s2（０，ｃ）を始点として、変位比較法
により始点Q_s2より順次１ドツトずつ、最適ドツ
トをｖ＝０となるまで線分L₂（L₂：ax＋ｃ−ｖ＝
０）を発生させる。

第３図ロは、線分L₂の発生を示す図である。
横軸はｙを、縦軸はｖをそれぞれ示している。
L₂は（８）式で定義される線分、Q_s2は始点であ
り、Q_s2から順次変位比較法によりドツトを発生
させ、線分L₂を発生させている。以下の動作に
ついてはｘが可変パラメータの場合と同様である
ので説明は省略する。

第６図は、ａ＝２，ｂ＝３，ｃ＝５，x_s＝３，
x_e＝９の場合におけるデイジタル線分発生例を示
す図である。イはQ_s1及びその変位Z_e1算出時の線
分発生を示しており、ロは目的とする実際の線分
の発生例を示している。イ，ロ何れの図形も、
（ ）内の数値はその点における変位を示してい
る。

上述の説明においては、デイジタル線分がxy
平面の第１象限に存在する場合について説明し
た。しかしながら、本発明は、第１象限に限るも
のではなく、第７図イに示すように線分が第２，
３，４象限に存在する場合にも、同様の手順によ
りデイジタル線分を発生させることができる。但
し、x_s，x_e＜０又はy_s，y_e＜０の場合には、第４
図、第５図のフローチヤートにおいて、x_sとx_e、
y_sとy_eの関係を入れ替え、ｘ＝x_eからｘ＝x_sの方
向へ、又はｙ＝y_eからｙ＝y_sの方向へ線分を発生
させる。

又、線分が第７図ロに示すように２つ以上の象
限にまたがつて存在する場合には、ｘ＝０又はｙ
＝０を中心に左右又は上下方向へ、即ちｘ＝０か
らｘ＝x_sの方向と、ｘ＝０からｘ＝x_eの方向へ、
ｙ＝０からｙ＝y_sの方向と、ｙ＝０からｙ＝y_eの
方向へそれぞれ２つに分けて線分を発生させれば
よい。尚、第７図に線分の発生方向を矢印で示
す。

（発明の効果） 以上詳細に説明したように、本発明によれば ｆ（ｘ，ｙ）＝ax−by＋ｃ＝０ で表わされ、x_s≦ｘ≦x_e又はy_s≦ｙ≦y_eなる範囲
を満足するデイジタル線分を発生させる場合にそ
れぞれ f₁（ｙ，ｕ）＝−by＋ｃ−ｕ＝０又は f₂（ｘ，ｖ）＝ax＋ｃ−ｖ＝０ で定義される方程式より始点のｙ座標y_e1又はｘ
座標x_e2を算出して始点を求めた後、変位比較法
で線分を発生させるようにすることにより、単純
加算機能のみでデイジタル線分を高速かつ高精度
に発生させることができる。

【図面の簡単な説明】

第１図は本発明の一実施例を示す構成ブロツク
図、第２図はデイジタル線分の発生例を示す図、
第３図はy_e1又はx_e2の算出の説明図、第４図、第
５図は本発明の動作を示すフローチヤート、第６
図はデイジタル線分の具体的な発生例を示す図、
第７図はデイジタル線分発生例を示す図、第８図
は候補ドツトの方向を示す図、第９図、第１０図
は変位比較法の説明図である。 １０……入力制御部、１１……入力レジスタ、
１２……バス制御部、２０……出力部、２１……
ｘレジスタ、２２……ｙレジスタ、３０……レジ
スタ演算部、３１……RALU、３２……レジス
タ群、４０……マイクロプログラム制御部、４１
……マルチプレクサ、４２……アドレスシーケン
サ、４３……マイクロプログラムメモリ、４４…
…パイプラインレジスタ、SB……システムバス、
UB……内部バス。

Claims (1)

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