JPH0640349B2 - ディジタル図形処理方法 - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、ディジタル図形処理方法に関し、更に詳しく
は、画像メモリ等にあって、２組の与えられた２点を通
る直線の交点に対応するドットを簡単な構成で精度良く
抽出することのできるディジタル図形処理方法に関する
ものである。

（従来の技術） 例えばファクシミリ装置等のディジタル図形読み取り／
再生装置では、強調表示の対象とする、または図形塗り
潰し処理の境界点とする等の種々の応用において、ビッ
ト・マップ・メモリ、また画像メモリ等に格納された２
つの直線の交点に対応するドットが必要となる場合がし
ばしばある。

２つの直線Ｌ_１，Ｌ_２の交点に対応するドットを抽出す
る従来の方法の例は第２図に示される。

即ち、直線Ｌ_１が通る２つのドットがＰ_１１（ｘ_１１，
ｙ_１１），Ｐ_１２（ｘ_１２，ｙ_１２）で与えられ、直線
Ｌ_２が通る２つのドットがＰ_２１（ｘ_２１，ｙ_２１），
Ｐ_２２（ｘ_２２，ｙ_２２）で与えられる場合、 ｘ＝（ｂ_２ｃ_１−ｂ_１ｃ_２）× １／（ａ_１ｂ_２−ａ_２ｂ_１）， ｙ＝（ａ_１ｃ_２−ａ_２ｃ_１）× １／（ａ_１ｂ_２−ａ_２ｂ_１）…（１） 但し、 ａ_１＝ｘ_１２−ｘ_１１，ａ_２＝ｘ_２２−ｘ_２１， ｂ_１＝ｙ_１１−ｙ_１２，ｂ_２＝ｙ_２１−ｙ_２２， ｃ＝ａ_１ｘ_１１＋ｂ_１ｙ_１１， ｃ_２＝ａ_２ｘ_２２＋ｂ_２ｙ_２２…（２） を計算する。

尚、数値ｘ_１１，ｙ_１１，ｘ_１２，ｙ_１２，ｘ_２１，ｙ
_２１，ｘ_２２，ｙ_２２は全て整数値である。

そして、上記の（１）式で算出された座標値（ｘ，ｙ）
は整数値でない場合があり、座標値が整数値でないと最
終的なドット位置が確定できないため、（ｘ，ｙ）に四
捨五入、切上げ、切下げ等を施して真値（（１）式で求
まった座標値）に最も近い点（整数座標で表されるドッ
ト）を算出し、このドットを２つの直線Ｌ_１，Ｌ_２の交
点にきわめて近いドット、またはこの交点に対応するド
ットＲ（ｘ_ｃ，ｙ_ｃ）として抽出していた。

（発明が解決しようとする問題点） 以上のような従来の方法によれば、２つの直線Ｌ_１，Ｌ
_２の交点に対応するドットＲを求めるためには、（１）
式、（２）式に表されるような剰除算を実行する機能が
必要となり、その分ハードウェア構成が複雑となり、装
置全体も複雑かつ高価なものになるという不具合が発生
していた。

本発明は、このような点に鑑みてなされたものであっ
て、その目的は、２組の与えられた２つのドットを通る
直線の交点に対応するドットを、簡単な構成でかつ精度
良く抽出することのできるディジタル図形処理方法を実
現することにある。

（問題点を解決するための手段） 前記した問題点を解決する本発明は、システムバスを経
由して上位装置からのコマンドを入力解読し初期値設定
を制御する入力制御部と、該入力制御部から与えられた
各種定数を基にして数値演算を行うレジスタ演算部と、
該レジスタ演算部の演算結果より得られた各種ステイタ
スを受けて全体を制御するマイクロプログラム制御部と
を備えて、ドットによって図形処理を行う方法であって
ドットＰ_１１（ｘ_１１，ｙ_１１）及びドットＰ_１２（ｘ
_１２，ｙ_１２）を通る直線Ｌ_１とドットＰ
_２１（ｘ_２１，ｙ_２１）及びドットＰ_２２（ｘ_２２，ｙ
_２２）を通る直線Ｌ_２ （但し、ｘ_１１，ｙ_１１，ｘ_１２，ｙ_１２，ｘ_２１，ｙ
_２１，ｘ_２２，ｙ_２２は整数値）との交点に対応するド
ットＲ（ｘ_ｃ，ｙ_ｃ）を抽出するディジタル図形処理方
法において、 (a)直線Ｌ_１，Ｌ_２を関数 Ｌ_１：ｆ_１（ｘ，ｙ）＝ａ_１ｘ＋ｂ_１ｙ−ｃ_１， Ｌ_２：ｆ_２（ｘ，ｙ）＝ａ_２ｘ＋ｂ_２ｙ−ｃ_２ （但し、ａ_１＝ｘ_１２−ｘ_１１，ｂ_１＝ｙ_１１−
ｙ_１２， ａ_２＝ｘ_２２−ｘ_２１，ｂ_２＝ｙ_２１−ｙ_２２， ｃ_１，ｃ_２は任意、 ｆ_１（ｘ_１１，ｙ_１１）＝ｆ_１（ｘ_１２，ｙ_１２）＝
０， ｆ_２（ｘ_２１，ｙ_２１）＝ｆ_２（ｘ_２２，ｙ_２２）＝
０） として定義し、ａ_１＝ａ_２＝０またはｂ_１＝ｂ_２＝０の
ときはエラーとするエラー発生工程、 (b)前記直線Ｌ_１を含む平面_１ ：ｚ＝ｆ_１（ｘ，ｙ）＝ａ_１ｘ＋ｂ_１ｙ−ｃ_１ を定義し、 ｘ_２１−ｘ_１１→ｘｄ_１，ｙ_２１−ｙ_１１→ｙｄ_１， ｘ_１１→ｘ，０→ｆ_１（ｘ） を前記レジスタ演算部内のレジスタに格納し、 ｘｄ_１≧０の場合、ｘをｘ_１１からｘ_２１まで順次１イ
ンクリメントしｆ_１（ｘ）にａ_１を加算し、ｘｄ_１＜０
の場合、ｘをｘ_１１からｘ_２１まで順次１デクリメント
しｆ_１（ｘ）＝０からａ_１を減算し、ｆ_１（ｘ）＝ｆ_１
（ｘ_２１）を求めてｆ_１（ｘ_２１）＝ｆ_１（ｙ）として
前記レジスタ演算部内のレジスタに格納し、ｙｄ_１≧０
の場合、ｙをｙ_１１からｙ_２１になるまで順次１インク
リメントしｆ_１（ｙ）にｂ_１を加算し、ｙｄ_１＜０の場
合、ｙをｙ_１１からｙ_２１まで順次１デクリメントしｆ
_１（ｙ）からｂ_１を減算し、ｆ_１（ｙ）＝ｆ
_１（ｙ_２１）の値を前記ドットＰ_２１から前記平面_１
までの変位ｆ_１１とし、続いて、 ｘ_２２−ｘ_１１→ｘｄ_２，ｙ_２２−ｙ_１１→ｙｄ_２ ｘ_１１→ｘ，０→ｆ_１（ｘ） を前記レジスタ演算部内のレジスタに格納し、 ｘｄ_２≧０の場合、ｘをｘ_１１からｘ_２２まで順次１イ
ンクリメントしｆ_１（ｘ）にａ_１を加算し、ｘｄ_２＜０
の場合、ｘをｘ_１１からｘ_２２まで順次１デクリメント
しｆ_１（ｘ）＝０からａ_１を減算してｆ_１（ｘ）＝ｆ_１
（ｘ_２２）を求めてｆ_１（ｘ_２１）＝ｆ_１（ｙ）として
前記レジスタ演算部内のレジスタに格納し、ｙｄ_２≧０
の場合、ｙをｙ_１１からｙ_２２になるまで順次１インク
リメントしｆ_１（ｙ）にｂ_１を加算し、ｙｄ_２＜０の場
合、ｙをｙ_１１からｙ_２２まで順次１デクリメントしｆ
_１（ｙ）からｂ_１を減算してｆ_１（ｙ）＝ｆ
_１（ｙ_２２）の値を前記ドットＰ_２２から前記平面_１
までの変位ｆ_１２とし、｜ｆ_１１｜≦｜ｆ_１２｜の場合
には前記ドットＰ_２１を始点とし｜ｆ_１１｜＞｜ｆ_１２
｜の場合には前記ドットＰ_２２を始点として選択する始
点選択工程、 (c)前記工程(b)で得られた始点Ｐ_２１またはＰ_２２から
変位比較法を用いて前記直線Ｌ_２をドットで描画するよ
うに最適ドットを選択し、この最適ドットの前記平面
_１からの変位の絶対値が｜ｆ_１１｜または｜ｆ_１２｜に
比較して小さくなる方向に向かって順次最適ドットを発
生させていくドット発生工程と、 (d)前記工程(c)と並行して行われる工程であって、前記
工程(c)にて逐次発生した最適ドットにつき前記平面_１ ：ｚ＝ｆ_１（ｘ，ｙ）＝ａ_１ｘ＋ｂ_１ｙ−ｃ_１へ向
かってｘｙ平面に垂直となる垂線の長さを距離Ｆ
_１（ｘ，ｙ）と定義し、 Ｆ_１（ｘ，ｙ）＝ｆ_１（ｘ＋Δｘ，ｙ＋Δｙ）＝ｆ
_１（ｘ，ｙ）＋ａ_１Δｘ＋ｂ_１Δｙ （但し、ｆ_１（ｘ，ｙ）の初期値は ｆ_１（ｘ_２１，ｙ_２１）＝ｆ_１１または ｆ_１（ｘ_２２，ｙ_２２）＝ｆ_１２であり、 Δｘ，Δｙ＝−１，０，＋１） を、前記工程(c)にて最適ドットが選択される毎に、そ
の時に選択されたΔｘ，Δｙの値を用いて距離Ｆ
_１（ｘ，ｙ）を算出する距離算出工程、 (e)前記工程(d)と並行して行われる工程であって、前記
距離Ｆ_１（ｘ，ｙ）の符号を逐次監視し、前記符号の反
転を検出した場合、前記符号が反転する直前の距離Ｆ_１
（ｘ，ｙ）の絶対値と前記符号が反転した直後の距離Ｆ
_１（ｘ，ｙ）の絶対値とを比較し、小さい方の距離Ｆ_１
（ｘ，ｙ）に対応するドット（ｘ，ｙ）を前記直線Ｌ_１
と前記直線Ｌ_２との交点に対応するドットＲ（ｘ_ｃ，ｙ
_ｃ）として抽出する交点抽出工程 よりなることを特徴とするディジタル図形処理方法であ
る。

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

第１図は、本発明の方法を実現するためのハードウェア
構成例を示す構成ブロック図である。

図に示す装置は、マイクロプログラム制御方式を採用
し、入力制御部１０，レジスタ演算部２０及びマイクロ
プログラム制御部３０の３つの主要部分より構成されて
いる。入力制御部１０とレジスタ演算部２０は、内部バ
スＵＢによって相互に連結されている。

１０は、システムバスＳＢを経由して上位の計算機等か
ら直線の交点に対応するドット抽出コマンドを入力・解
読し、初期値設定を制御する入力制御部で、入力レジス
タ１１及びバス制御部１２とから構成されている。

２０は、数値演算を行うレジスタ演算部で、レジスタ・
アンド・アリスメティック・ロジカル・ユニット（以下
「ＲＡＬＵ」と略す）２１を中心に構成されている。

ＲＡＬＵ２１は、複数個の内部レジスタより構成される
レジスタ群２２を有し、これらの内部レジスタ間で、例
えば加減算、論理積、論理和等の論理算術演算を行う。
更に、ＲＡＬＵ２１での演算結果における各種ステイタ
スは、マイクロプログラム制御部３０内のマルチプレク
サ３１への入力となっている。

３０は全体の制御及び交点に対応するドット算出の工程
を実行するマイクロプログラム制御部で、マルチプレク
サ３１，アドレスシーケンサ３２，マイクロプログラム
メモリ３３及びパイプラインレジスタ３４とから構成さ
れている。

パイプラインレジスタ３４は、マイクロプログラムメモ
リ３３からの出力を保持し、前述の入力制御部１０及び
レジスタ演算部２０の各部分へマイクロ命令を供給す
る。

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

本発明は、このように構成された回路を用いて実現され
る方法であり、その詳しい動作は以下の通りである。

本発明にあっては、第２図に示すように、２つのドット
Ｐ_１１（ｘ_１１，ｙ_１１），Ｐ_１２（ｘ_１２，ｙ_１２）
を通る直線Ｌ_１と、２つのドットＰ_２１（ｘ_２１，ｙ
_２１）Ｐ_２２（ｘ_２２，ｙ_２２）を通る直線Ｌ_２との交
点にきわめて近く、その交点に対応するドットとしてＲ
（ｘ_ｃ，ｙ_ｃ）を抽出する場合を例として動作説明をす
る。

尚、本発明の方法では、ドットＲ（ｘ_ｃ，ｙ_ｃ）を抽出
する過程で従来より提案されている変位比較法を使用し
ている。この変位比較法とは、線分の発生法の一つであ
り、直線、２次曲線図形等を発生させるときに用いられ
るものである。

このような変位比較法は、例えば、 ・「図形のドット表示」信学論vol.56-A, No.7,p.401（July1973） ・“An improved algorithm for the generation of no
nparametric curves”： B.W.Jordan.Jr.,W.J.Lennon, B.D.Holm：ＩＥＥＥTrans.C-22 No.12,p.1052（Dec.1973） 等に記載されている。

その概略は次の通りである。

発生すべき直線Ｌの方程式を Ｌ：ｆ（ｘ，ｙ）＝ａｘ−ｂｙ＋ｃ＝０…（３） としたとき、始点を含む既に選択したドットの次に選択
すべきドットを ＩＦ ＭＩＮ｜ｆ（Ｐ_ｉ）｜＝｜ｆ（Ｐ_ｊ）｜ ＴＨＥＮ ＴＡＫＥ Ｐ_ｊ （但し、ｉ，ｊ∈Ｉ，Ｉ＝１，２，…，８）…（４） なるアルゴリズムに基づいて生成する方法である。

ここで、ａ，ｂ，ｃは定数である。

第３図は、このような変位比較法にあって、候補となる
ドットを選択するときの説明図である。

Ｐ_０，Ｐ_１，…，Ｐ_８は、ｘｙ平面内のドット位置を表
し、Ｐ_０は前回選択したドットを、Ｐ_１，…，Ｐ_８は今
回選択すべき候補ドットをそれぞれ表している。候補ド
ットＰ_１，…，Ｐ_８のうちＰ_１，…，Ｐ_４は４画素連結
表示時の候補ドット、Ｐ_１，…，Ｐ_８は８画素連結表示
時の候補ドットである。

また、（４）式内のＩはドットＰ_１，…，Ｐ_８の添字番
号を示し、ｆ（Ｐ_ｉ）は特定平面からドットＰ_ｉの位
置までの変位（詳細は後述）を表すものである。

即ち、（３）式で表される直線Ｌは次式 ：ｚ＝ｆ（ｘ，ｙ）＝ａｘ−ｂｙ＋ｃ…（５） で表される平面とｘｙ平面（ｚ＝０の面）との交線と
考えることができ、これを第４図及び第５図に表す。

第４図は、特定平面とｘｙｚ３次元空間内のｘｙ平面
との交わりを示す図、第５図は特定平面の断面図であ
る。

第４図及び第５図において、特定平面とｘｙ平面との
交線はＬで表される。そして、ｘｙ平面上のドットＰ_０
（第３図に示したように、既に選択された前回のドット
Ｐ_０）からの垂線が特定平面と交わる点をＡ_０とする
と、ドットＰ_０（ｘ_０，ｙ_０）から交点Ａ_０までの距離
を｜ｆ（Ｐ_０）｜または｜ｚ_０｜で表わし、ｆ（Ｐ_０）
を特定平面からのドットＰ_０に対する変位と定義す
る。

即ち、 ｆ（Ｐ_０）＝ｚ_０＝ａｘ_０−ｂｙ_０＋ｃ…（51） で表される。

このように、変位比較法とは、前回選択したドットＰ_０
から今回選択すべきドットを決定するにあたり、第３図
に示したような候補ドットＰ_１，…，Ｐ_８のうちからそ
の変位ｆ（Ｐ_ｉ）（ｉ＝１，…，８）が最小となるドッ
トを選択して線分を発生し、この操作を順次繰り返して
線分を発生していく方法である。

即ち、（４）式で各々の候補ドットＰ_１に対応する変位
ｆ（Ｐ_ｉ）の絶対値を比較し、最小の変位を有する候補
ドットＰ_ｉを次に選択すべきドットとするものである。

なおここで、変位比較法を用いて単純な加減算機能のみ
で直線、曲線を発生するためには、発生すべき線図形の
始点Ｐ_ｓが当該線図形上に存在すること、即ち、始点Ｐ
_ｓにおける変位ｆ（Ｐ_Ｓ）が“０”であることが前提で
ある。

このように、変位比較法によって最適ドットを選択して
いく場合、変位ｆ（Ｐ_ｉ）（ｉ＝１，２，…，８）の算
出は、（５）式，（51）式を前提とすると、 ｆ（Ｐ_ｉ）＝ｆ（ｘ_０＋Δｘ，ｙ_０＋Δｙ） ＝ｆ（ｘ_０，ｙ_０）＋ａΔｘ−ｂΔｙ ＝ｆ（Ｐ_０）＋ａΔｘ−ｂΔｙ により表される。

但し、今回選択すべき候補ドットをドットＰ_ｉ（ｘ_０＋
Δｘ，ｙ_０＋Δｙ）とし、前回選択されたドットをドッ
トＰ_０（ｘ_０，ｙ_０）とする。また、Δｘ，Δｙは表示
ドットの座標を対象としているため、ｉの値により０，
＋１，−１のいずれかの値をとる。

更に、発生すべき線図形の始点Ｐ_ｓが当該線Ｌ上に存在
し、変位ｆ（Ｐ_Ｓ）が“０”であるのでｆ（Ｐ_０）の初
期値は“０”である。

以上のように、変位比較法によれば、乗除算機能を設置
しなくとも、加減算機能のみを有すれば線分発生を実現
できるものである。

以上が従来よりある変位比較法の概要説明であり、本発
明方法にあっては、この変位比較法をその手順の中に用
いてある。

次に本発明方法にかかる工程を第８図、第９図、第１０
図、第１１図のフローチャートを用いて説明する。

はじめに、第８図のフローチャートより説明を開始す
る。

上位の計算機等よりシステムバスＳＢを経由して、直線
Ｌ_１が通る２つのドットＰ_１１，Ｐ_１２、直線Ｌ_２が通
る２つのドットＰ_２１，Ｐ_２２のそれぞれのｘ座標，ｙ
座標（ｘ_１１，ｙ_１１，ｘ_１２，ｙ_１２，ｘ_２１，ｙ
_２１，ｘ_２２，ｙ_２２）を入力制御部１０内の入力レジ
スタ１１にセットした後、上位計算機等から入力制御部
に対してスタート起動（ＳＴＡＲＴ）がかかる。

スタート起動（ＳＴＡＲＴ）がかかると、マイクロプロ
グラム制御部３０は、パラメータｘ_１１，ｙ_１１，ｘ
_１２，ｙ_１２，ｘ_２１，ｙ_２１，ｘ_２２，ｙ_２２を内部
バスＵＢを経由してレジスタ演算部２０内のレジスタ群
２２に格納する。これにより、レジスタ群２２には上の
レジスタから順に、第１図に示すように、ｘ_１１，ｘ
_１２，ｘ_２１，ｘ_２２，…のデータが格納される。

続いてレジスタ演算部２０は、これらのデータを基に、 ｘ_１２−ｘ_１１，ｙ_１１−ｙ_１２， ｘ_２２−ｘ_２１，ｙ_２１−ｘ_２２， を演算し、 ｘ_１２−ｘ_１１→ａ_１，ｙ_１１−ｙ_１２→ｂ_１， ｘ_２２−ｘ_２１→ａ_２，ｙ_２１−ｙ_２２→ｂ_２ として、ａ_１，ａ_２，ｂ_１，ｂ_２をそれぞれのレジスタ
２２に格納する。

この時点で、ａ_１＝ａ_２＝０またはｂ_１＝ｂ_２＝０の場
合（ＹＥＳ）には、直線Ｌ_１と直線Ｌ_２は、それぞれ異
なる２つのドットにおけるｘ座標またはｙ座標が等しい
ので、ｘ軸またはｙ軸に平行となり、第２図を参照する
と明らかなように、直線Ｌ_１と直線Ｌ_２とは平行であ
り、その交点は存在しない。従って、この場合はエラー
（ＥＲＲＯＲ）とし、レジスタ演算部２０は処理を停止
する。

一方、ａ_１とａ_２の少なくとも一方が“０”でない場
合、または、ｂ_１とｂ_２の少なくとも一方が“０”でな
い場合（ＮＯ）には、直線Ｌ_１と直線Ｌ_２とは平行でな
く、交点に対応するドットが存在するので処理を続行す
る。

なおここで、直線Ｌ_１を表す関数を Ｌ_１：ｆ_１（ｘ，ｙ）＝ａ_１ｘ＋ｂ_１ｙ−ｃ_１ （但し、ｆ_１（ｘ_１１，ｙ_１１）＝ｆ_１（ｘ_１２，ｙ
_１２）と定義する。値ｃ_１については、後述の算出式に
は用いられないので特に求めなくてもよく、任意定数と
する。

そして、この直線Ｌ_１を含む、３次元空間における平面_１ ：ｚ＝ｆ_１（ｘ，ｙ）＝ａ_１ｘ＋ｂ_１ｙ−ｃ_１と直
線Ｌ_２上のドットＰ_２１との変位ｆ_１１と、この平面
_１と直線Ｌ_２上のドットＰ_２２との変位ｆ_１２を求める
処理を開始する。

この変位ｆ_１１と変位ｆ_１２を求める処理は、後に詳述
するが、変位比較法によって直線Ｌ_２を発生するときの
始点となるべき点を選択するためのものである。

尚、変位ｆ_１１と変位ｆ_１２を求める処理は、単純に
は、_１ ：ｚ＝ｆ_１（ｘ，ｙ）＝ａ_１ｘ＋ｂ_１ｙ−ｃ_１の式
にドットＰ_２１（ｘ_２１，ｙ_２１）またはドットＰ_２２
（ｘ_２２，ｙ_２２）を代入すれば求まるが、この演算を
行うにはハードウェア資源として乗算器を設定しないと
処理不可である。本発明は、乗除算機能を設定しないと
いう前提により、次に説明するような処理によって乗算
を含まない演算処理により変位ｆ_１１と変位ｆ_１２を求
めるものである。

これらの変位ｆ_１１，ｆ_１２を求める概念を第６図に表
し、この図を参照しながら変位ｆ_１１，ｆ_１２を求める
工程を次に説明する。

さて、第８図のフローチャートに戻り、まず、変位ｆ
_１１を求める手順を説明する。

最初に、ドットＰ_２１（ｘ_２１，ｙ_２１）とドットＰ
_１１（ｘ_１１，ｙ_１１）のｘ座標，ｙ座標の差をそれぞ
れ求め、 ｘ_２１−ｘ_１１→ｘｄ_１， ｙ_２１−ｙ_１１→ｙｄ_１…（８） をレジスタ群２２内のレジスタに格納する。

次に、第９図のフローチャートに遷移する。

なおここで、 ｆ_１（ｘ_１１＋Δｘ，ｙ_１１） ＝ｆ_１（ｘ_１１，ｙ_１１）＋ａ_１Δｘ…（９） と表すことができ（但し、ｘ座標の増減分Δｘについて
は、ｘｙ平面上における表示ドットを対象としているた
め、Δｘ＝−１，０，＋１）、ｆ_１（ｘ_１１，ｙ_１１）
＝０である（（ｘ_１１，ｙ_１１）は直線Ｌ_１上の点）か
ら、（９）式は、 ｆ_１（ｘ，ｙ_１１）＝ｆ_１（ｘ） （但し、ｆ_１（ｘ_１１）＝０）…（10） と表わすことができる。

そして、ｙ＝ｙ_１１を固定とし、ｘ_１１→ｘ，０→ｆ_１
（ｘ）をレジスタ群２２内のレジスタに格納する。

続いて、ｘｄ_１≧０の場合には、ｘ＝ｘ_１１からｘの値
を順次＋１インクリメントし、同時に、ｘをインクリメ
ントする毎にｆ_１（ｘ）＝０にａ_１を加算していき、こ
の動作をｘ＝ｘ_２１になるまで繰り返す。

一方、ｘｄ_１＜０の場合には、ｘ＝ｘ_１１からｘの値を
順次１デクリメントし、同時に、ｘをデクリメントする
毎にｆ_１（ｘ）＝０からａ_１を減算し、この動作をｘ＝
ｘ_２１になるまで繰り返す。

これにより、ｘ＝ｘ_２１に達したときのｆ_１（ｘ）の値
はｆ_１（ｘ_２１）で表される。

次に、ｘ＝ｘ_２１を固定とする。

このときは、 ｆ_１（ｘ_２１，ｙ_１１＋Δｙ） ＝ｆ_１（ｘ_２１，ｙ_１１）＋ｂ_１Δｙ…（11） と表すことができ（但し、ｙ座標の増減分Δｙについて
は、ｘｙ平面上における表示ドットを対象としているた
め、Δｙ＝−１，０，＋１）、（10）式より、ｆ_１（ｘ
_２１，ｙ_１１）＝ｆ_１（ｘ_２１）となる。

従って、（11）式は、 ｆ_１（ｘ_２１，ｙ）＝ｆ_１（ｙ） （但し、ｆ_１（ｙ_１１）＝ｆ_１（ｘ_２１））…（12） と表わすことができる。

そして、ｙ_１１→ｙ，ｆ_１（ｘ_２１）→ｆ_１（ｙ）をレ
ジスタ群２２内のレジスタに格納する。

ここで、ｙｄ_１≧０の場合には、ｙ＝ｙ_１１からｙの値
を順次＋１インクリメントし、同時に、ｙをインクリメ
ントする毎にｆ_１（ｙ）＝ｆ_１（ｘ_２１）にｂ_１を加算
していき、この動作をｙ＝ｙ_２１になるまで繰り返す。

一方、ｙｄ_１＜０の場合には、ｙ＝ｙ_１１からｙの値を
順次１デクリメントし、同時に、ｙをデクリメントする
毎にｆ_１（ｙ）＝ｆ_１（ｘ_２１）からｂ_１を減算し、こ
の動作をｙ＝ｙ_２１になるまで繰り返す。

以上のｆ_１（ｙ）＝０にｂ_１を加算または減算していく
動作をｙ＝ｙ_２１に達するまで繰り返す。

そして、ｙ＝ｙ_２１に達したときのｆ_１（ｙ_２１）の値
を変位ｆ_１１とする。この変位ｆ_１１はドットＰ_２１に
おける平面_１との変位に対応する。

次に、変位ｆ_１２を求める。

ドットＰ_２２（ｘ_２２，ｙ_２２）とドットＰ_１１（ｘ
_１１，ｙ_１１）のｘ座標，ｙ座標の差をそれぞれ求め、 ｘ_２２−ｘ_１１→ｘｄ_２， ｙ_２２−ｙ_１１→ｙｄ_２…（13） をレジスタ群２２内のレジスタに格納する。

以下、第１０図のフローチャートに示すように、第９図
のフローチャートと同様の工程に従ってｆ_１（ｙ_２２）
を算出し、この値をドットＰ_２２（ｘ_２２，ｙ_２２）と
平面_１との変位ｆ_１２とする。

次に、変位ｆ_１１，変位ｆ_１２のそれぞれの絶対値｜ｆ
_１１｜，｜ｆ_１２｜を算出して、その大小関係を｜ｆ
_１１｜≦｜ｆ_１２｜として調べる。

｜ｆ_１１｜≦｜ｆ_１２｜が成立する場合（ＹＥＳ）は第
１１図のＭ_１からの工程を起動して、点Ｐ
_２１（ｘ_２１，ｙ_２１）を始点とする。

一方、｜ｆ_１１｜≦｜ｆ_１２｜が成立しない場合（Ｎ
Ｏ）は第１１図のＭ_２からの工程を起動して、ドットＰ
_２２（ｘ_２２，ｙ_２２）を始点とする。

なおここで、直線Ｌ_２を表す関数を Ｌ_２：ｆ_２（ｘ，ｙ）＝ａ_２ｘ＋ｂ_２ｙ−ｃ_２＝０（但
し、ｆ_２（ｘ_２１，ｙ_２１）＝ｆ_２（ｘ_２２，ｙ_２２） ＝０）…（14） と定義する。値ｃ_２については、後述の算出式には用い
られないので求めなくてもよく、任意でよい。

そして、決定した始点Ｐ_２１またはＰ_２２から、上述し
た変位比較法を用いて、今度は、直線Ｌ_１に近づく方向
に、直線Ｌ_２を描画するべく、順次、最適ドットを発生
させていく。

即ち、始点Ｐ_２１またはＰ_２２より、変位比較法 ｆ_２（ｘ＋Δｘ，ｙ＋Δｙ） ＝ｆ_２（ｘ，ｙ）＋ａ_２Δｘ＋ｂ_２Δｙ により、直線Ｌ_２： ｆ_２（ｘ，ｙ）＝ａ_２ｘ＋ｂ_２ｙ−ｃ_２＝０ のドット表示を、直線Ｌ_１： ｆ_１（ｘ，ｙ）＝ａ_１ｘ＋ｂ_１ｙ−ｃ_１＝０ （但し、ｆ_１（ｘ_１１，ｙ_１１）＝ｆ_１（ｘ_１２，ｙ
_１２）＝０） の存在する方向に向かって、順次実行する。

このとき、併せて、逐次発生した直線Ｌ_２上の最適ドッ
トにつき、直線Ｌ_１を含む平面_１ ：ｚ＝ｆ_１（ｘ，ｙ）＝ａ_１ｘ＋ｂ_１ｙ−ｃ_１へ向
かって、ｘｙ平面に垂直となる垂線を下ろし、その垂線
の長さを距離Ｆ_１（ｘ，ｙ）と定義してこの値を算出す
る。

尚、直線Ｌ_２上の最適ドットと平面_１までの距離Ｆ_１
（ｘ，ｙ）（但し、ｘｙ平面に垂直な距離）は、単純に
は、_１ ：ｚ＝ｆ_１（ｘ，ｙ）＝ａ_１ｘ＋ｂ_１ｙ−ｃ_１の式
に、選択された最適ドットの座標値（ｘ，ｙ）を逐次代
入すれば求まるが、この演算を行うにはハードウェア資
源として乗算器を設定しないと処理不可である。本発明
は、乗算機能を設定しないという前提により、次に説明
するような処理によって乗算を含まない演算処理によっ
て距離Ｆ_１（ｘ，ｙ）を求めるものである。

詳しくは、最適ドットの選択は、変位比較法により、 ｆ_２（ｘ＋Δｘ，ｙ＋Δｙ） ＝ｆ_２（ｘ，ｙ）＋ａ_２Δｘ＋ｂ_２Δｙ に従って行われるが、同時に、距離を算出するため、距
離Ｆ_１（ｘ，ｙ）を Ｆ_１（ｘ，ｙ）＝ｆ_１（ｘ＋Δｘ，ｙ＋Δｙ） ＝ｆ_１（ｘ，ｙ）＋ａ_１Δｘ＋ｂ_１Δｙ （但し、ｆ_１（ｘ，ｙ）の初期値は ｆ_１（ｘ_２１，ｙ_２１）＝ｆ_１１または ｆ_１（ｘ_２２，ｙ_２２）＝ｆ_１２であり、 Δｘ，Δｙは０，＋１，−１のいずれかの値である） により求める。

即ち、距離Ｆ_１（ｘ，ｙ）の初期値ｆ（ｘ，ｙ）とし
て、始点としてドットＰ_２１を選択したときはｆ_１１の
値を採用し、始点としてドットＰ_２２を選択したときは
ｆ_１２の値を採用する。そして、直線Ｌ_２を描画するド
ットが選択される毎に、その時に選択されたΔｘ，Δｙ
の値（−１，０，＋１）を用いて距離Ｆ_１（ｘ，ｙ）を
算出する。

ここで、前回のドット選択時の距離Ｆ_０をｆ_１（ｘ，
ｙ）とし、今回のドット選択時の距離Ｆ_１をｆ_１（ｘ＋
Δｘ，ｙ＋Δｙ）とする。

尚、直線Ｌ_１に近づく方向に最適ドットを発生させるた
めには、始点Ｐ_２１またはＰ_２２の次に選択すべき最適
ドットの平面_１からの変位の絶対値が始点とのそれ
（平面_１からの変位）に比較して小さくなる方向に直
線Ｌ_２の描画方向を選べばよい。

そして、距離Ｆ_１（ｘ，ｙ）の符号が反転した時点、即
ち、平面_１がｘｙ平面を切る時点で、距離Ｆ_１（ｘ，
ｙ）の符号が反転する直前の直線Ｌ_２の最適ドットの平
面_１からの距離Ｆ_０と、反転した直後の直線Ｌ_２の最
適ドットの平面_１からの距離Ｆ_１の絶対値を比較す
る。

｜Ｆ_０｜≦｜Ｆ_１｜の場合には、符号反転直前の最適ド
ットを直線Ｌ_１と直線Ｌ_２の交点にきわめて近いドット
とし、このドットを交点に対応するドットとして抽出す
る。

また、｜Ｆ_０｜＞｜Ｆ_１｜の場合には、符号反転直後の
最適ドットを直線Ｌ_１と直線Ｌ_２の交点にきわめて近い
ドットとし、このドットを交点に対応するドットとして
抽出する。

この交点にた対応する点、即ちドットＲ（ｘ_ｃ，ｙ_ｃ）
を第７図に示す。

このように、本発明によれば、直線Ｌ_１とＬ_２の交点に
対応するドットＲを乗除算機能を用いることなく、加減
算を主とするので、簡単なハードウェア構成で精度良く
求めることができるものである。

尚、（４）式で表される値ａ_１，ｂ_１，ａ_２，ｂ_２のい
ずれの１つも０でなく、ａ_１ｂ_２＝ａ_２ｂ_１の場合、即
ち、直線Ｌ_１とＬ_２が平行な場合には前述の距離Ｆ
_１（ｘ，ｙ）の符号がいつまでたっても反転しない。こ
のような不都合を発生させないようにするためには、ソ
フトウェアまたはハードウェアによる時間監視タイマー
を設け、一定時間経過しても動作が終了しないときには
エラーとし、動作を打ち切るようにしておく。

（発明の効果） 以上詳細に説明したように、本発明は次のように作用す
る。

まず、２つのドットＰ_１１（ｘ_１１，ｙ_１１）とＰ_１２
（ｘ_１２，ｙ_１２）を通る直線Ｌ_１と、２つのドットＰ
_２１（ｘ_２１，ｙ_２１）とＰ_２２（ｘ_２２，ｙ_２２）を
通る直線Ｌ_２のそれぞれに対して、関数 ｆ_１（ｘ，ｙ）＝ａ_１ｘ＋ｂ_１ｙ−ｃ_１， ｆ_２（ｘ，ｙ）＝ａ_２ｘ＋ｂ_２ｙ−ｃ_２ 但し、 ａ_１＝ｘ_１２−ｘ_１１，ｂ_１＝ｙ_１１−ｙ_１２， ａ_２＝ｘ_２２−ｘ_２１，ｂ_２＝ｙ_２１−ｙ_２２， ｃ_１，ｃ_２は任意、 ｆ_１（ｘ_１１，ｙ_１１）＝ｆ_１（ｘ_１２，ｙ_１２） ＝ｆ_２（ｘ_２１，ｙ_２１）＝ｆ_２（ｘ_２２，ｙ_２２）＝
０を定義する。

そして、乗除算を用いずに直線Ｌ_２上のドットＰ_２１ま
たはドットＰ_２２のいずれかを始点として選択し、この
始点から変位比較法を用いて最適ドット選択により直線
Ｌ_２を発生させながら、併せて、選択した最適ドットの
直線Ｌ_１を含む平面_１ ：ｚ＝ｆ_１（ｘ，ｙ） からの距離Ｆ_１（ｘ，ｙ）を逐次計算し、この距離Ｆ_１
（ｘ，ｙ）の符号がいつ反転するかを判定する。

距離Ｆ_１（ｘ，ｙ）の符号の反転を検出すると、符号反
転前後の最適ドットの平面_１からのそれぞれの距離Ｆ
_１（ｘ，ｙ）の絶対値を比較し、小さい方の最適ドット
を直線Ｌ_１と直線Ｌ_２の交点に対応するドットとして抽
出する。

従って、本発明によれば、２つの直線の交点に対応する
ドットを単純な加減算機能のみで精度良く求めることが
できる。

また、本発明によれば、直線Ｌ_２を発生する際に、 平面_１：ｚ＝ｆ_１（ｘ，ｙ）からドットＰ_２１までの
距離ｆ_１１と、 平面_１：ｚ＝ｆ_１（ｘ，ｙ）からドットＰ_２２までの
距離ｆ_１２とを計算し、 ｜ｆ_１１｜≦｜ｆ_１２｜の場合には、ドットＰ_２１を始
点とし、｜ｆ_１１｜＞｜ｆ_１２｜の場合には、ドットＰ
_２２を始点として選択するので、直線Ｌ_２の描画開始時
に始点をドットＰ_２１またはドットＰ_２２のいずれか一
方を固定する方法に比較すると、より高速に２つの直線
の交点に対応するドットを求めることができる。

【図面の簡単な説明】

第１図は本発明の方法を実現するための一実施例を示す
構成ブロック図、第２図は直線の交点に対応するドット
を表す図、第３図は候補ドットの方向を示す図、第４
図，第５図は変位比較法を説明するための図、第６図は
変位ｆ_１１と変位ｆ_１２の算出を説明するための図、第
７図は直線の交点に対応するドットを算出するための説
明図、第８図〜第１１図は本発明の処理工程を示すフロ
ーチャートである。 １０……入力制御部、１１……入力レジスタ １２……バス制御部、２０……レジスタ演算部 ２１……ＲＡＬＵ、２２……レジスタ群 ３０……マイクロプログラム制御部 ３１……マルチプレクサ ３２……アドレスシーケンサ ３３……マイクロプログラムメモリ ３４……パイプラインレジスタ ＳＢ……システムバス、ＵＢ……内部バス

Claims (1)

【特許請求の範囲】
1. 【請求項１】システムバスを経由して上位装置からのコ
   マンドを入力解読し初期値設定を制御する入力制御部
   と、該入力制御部から与えられた各種定数を基にして数
   値演算を行うレジスタ演算部と、該レジスタ演算部の演
   算結果より得られた各種ステイタスを受けて全体を制御
   するマイクロプログラム制御部とを備えて、ドットによ
   って図形処理を行う方法であってドットＰ
   _１１（ｘ_１１，ｙ_１１）及びドットＰ_１２（ｘ_１２，ｙ
   _１２）を通る直線Ｌ_１とドットＰ_２１（ｘ_２１，
   ｙ_２１）及びドットＰ_２２（ｘ_２２，ｙ_２２）を通る直
   線Ｌ_２（但し、ｘ_１１，ｙ_１１，ｘ_１２，ｙ_１２，ｘ
   _２１，ｙ_２１，ｘ_２２，ｙ_２２は整数値）との交点に対
   応するドットＲ（ｘ_ｃ，ｙ_ｃ）を抽出するディジタル図
   形処理方法において、 (a)直線Ｌ_１，Ｌ_２を関数 Ｌ_１：ｆ_１（ｘ，ｙ）＝ａ_１ｘ＋ｂ_１ｙ−ｃ_１， Ｌ_２：ｆ_２（ｘ，ｙ）＝ａ_２ｘ＋ｂ_２ｙ−ｃ_２ （但し、ａ_１＝ｘ_１２−ｘ_１１，ｂ_１＝ｙ_１１−
   ｙ_１２， ａ_２＝ｘ_２２−ｘ_２１，ｂ_２＝ｙ_２１−ｙ_２２， ｃ_１，ｃ_２は任意、 ｆ_１（ｘ_１１，ｙ_１１）＝ｆ_１（ｘ_１２，ｙ_１２）＝
   ０， ｆ_２（ｘ_２１，ｙ_２１）＝ｆ_２（ｘ_２２，ｙ_２２）＝
   ０） として定義し、ａ_１＝ａ_２＝０またはｂ_１＝ｂ_２＝０の
   ときはエラーとするエラー発生工程、 (b)前記直線Ｌ_１を含む平面_１ ：ｚ＝ｆ_１（ｘ，ｙ）＝ａ_１ｘ＋ｂ_１ｙ−ｃ_１ を定義し、 ｘ_２１−ｘ_１１→ｘｄ_１，ｙ_２１−ｙ_１１→ｙｄ_１， ｘ_１１→ｘ，０→ｆ_１（ｘ） を前記レジスタ演算部内のレジスタに格納し、 ｘｄ_１≧０の場合、ｘをｘ_１１からｘ_２１まで順次１イ
   ンクリメントしｆ_１（ｘ）にａ_１を加算し、ｘｄ_１＜０
   の場合、ｘをｘ_１１からｘ_２１まで順次１デクリメント
   しｆ_１（ｘ）＝０からａ_１を減算し、ｆ_１（ｘ）＝ｆ_１
   （ｘ_２１）を求めてｆ_１（ｘ_２１）＝ｆ_１（ｙ）として
   前記レジスタ演算部内のレジスタに格納し、ｙｄ_１≧０
   の場合、ｙをｙ_１１からｙ_２１になるまで順次１インク
   リメントしｆ_１（ｙ）にｂ_１を加算し、ｙｄ_１＜０の場
   合、ｙをｙ_１１からｙ_２１まで順次１デクリメントしｆ
   _１（ｙ）からｂ_１を減算し、ｆ_１（ｙ）＝ｆ
   _１（ｙ_２１）の値を前記ドットＰ_２１から前記平面_１
   までの変位ｆ_１１とし、続いて、 ｘ_２２−ｘ_１１→ｘｄ_２，ｙ_２２−ｙ_１１→ｙｄ_２ ｘ_１１→ｘ，０→ｆ_１（ｘ） を前記レジスタ演算部内のレジスタに格納し、 ｘｄ_２≧０の場合、ｘをｘ_１１からｘ_２２まで順次１イ
   ンクリメントしｆ_１（ｘ）にａ_１を加算し、ｘｄ_２＜０
   の場合、ｘをｘ_１１からｘ_２２まで順次１デクリメント
   しｆ_１（ｘ）＝０からａ_１を減算してｆ_１（ｘ）＝ｆ_１
   （ｘ_２２）を求めてｆ_１（ｘ_２１）＝ｆ_１（ｙ）として
   前記レジスタ演算部内のレジスタに格納し、ｙｄ_２≧０
   の場合、ｙをｙ_１１からｙ_２２になるまで順次１インク
   リメントしｆ_１（ｙ）にｂ_１を加算し、ｙｄ_２＜０の場
   合、ｙをｙ_１１からｙ_２２まで順次１デクリメントしｆ
   _１（ｙ）からｂ_１を減算してｆ_１（ｙ）＝ｆ
   _１（ｙ_２２）の値を前記ドットＰ_２２から前記平面_１
   までの変位ｆ_１２とし、｜ｆ_１１｜≦｜ｆ_１２｜の場合
   には前記ドットＰ_２１を始点とし｜ｆ_１１｜＞｜ｆ_１２
   ｜の場合には前記ドットＰ_２２を始点として選択する始
   点選択工程、 (c)前記工程(b)で得られた始点Ｐ_２１またはＰ_２２から
   変位比較法を用いて前記直線Ｌ_２をドットで描画するよ
   うに最適ドットを選択し、この最適ドットの前記平面
   _１からの変位の絶対値が｜ｆ_１１｜または｜ｆ_１２｜に
   比較して小さくなる方向に向かって順次最適ドットを発
   生させていくドット発生工程と、 (d)前記工程(c)と並行して行われる工程であって、前記
   工程(c)にて逐次発生した最適ドットにつき前記平面_１ ：ｚ＝ｆ_１（ｘ，ｙ）＝ａ_１ｘ＋ｂ_１ｙ−ｃ_１へ向
   かってｘｙ平面に垂直となる垂線の長さを距離Ｆ
   _１（ｘ，ｙ）と定義し、 Ｆ_１（ｘ，ｙ）＝ｆ_１（ｘ＋Δｘ，ｙ＋Δｙ） ＝ｆ_１（ｘ，ｙ）＋ａ_１Δｘ＋ｂ_１Δｙ （但し、ｆ_１（ｘ，ｙ）の初期値は ｆ_１（ｘ_２１，ｙ_２１）＝ｆ_１１または ｆ_１（ｘ_２２，ｙ_２２）＝ｆ_１２であり、 Δｘ，Δｙ＝−１，０，＋１） を、前記工程（ｃ）にて最適ドットが選択される毎に、
   その時に選択されたΔｘ，Δｙの値を用いて距離Ｆ
   _１（ｘ，ｙ）の算出する距離算出工程、 (e)前記工程(d)と並行して行われる工程であって、前記
   距離Ｆ_１（ｘ，ｙ）の符号を逐次監視し、前記符号の反
   転を検出した場合、前記符号が反転する直前の距離Ｆ_１
   （ｘ，ｙ）の絶対値と前記符号が反転した直後の距離Ｆ
   _１（ｘ，ｙ）の絶対値とを比較し、小さい方の距離Ｆ_１
   （ｘ，ｙ）に対応するドット（ｘ，ｙ）を前記直線Ｌ_１
   と前記直線Ｌ_２との交点に対応するドットＲ（ｘ_ｃ，ｙ
   _ｃ）として抽出する交点抽出工程 よりなることを特徴とするディジタル図形処理方法。