JPH0417081A - 線分近似座標発生方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、ラスクスキャン型ディスプレイ装置における
線分近似座標発生方法に関する。

［従来の技術］ 従来から図形を画面表示する装置が知られている。ラス
クスキャン型ディスプレイ装置はそのうち代表的なもの
である。

第３図には、ラスクスキャン型ディスプレイ装置の一例
の概略構成か示されている。

この図においては、グラフィックプロセシングユニット
（ＧＰＵ）１０．ディジタル微分解析器（ＤＤＡ）１２
、フレームバッファ（ＦＢ）１．４及びＣＲＴ１６がカ
スケード接続されている。

すなわち、ＧＰＵＩＯにホストコンピュータの指令によ
り図形データが供給されると、ＧＰＵＩＯはユーザの作
成したソフトウェアに従い動作する。ＤＤＡ１２は、Ｇ
ＰＵＩＯの制御のもとに各種図形に係る座標値を発生さ
せ、図形情報を発生させる。この図形情報は、ＦＢ１４
に格納され、ＣＲＴ１６の画面上に当該図形が表示され
ることになる。

この図に示されるＤＤＡ１２には、短軸座標カウンタＳ
ｄ、長軸座標カウンタＬｄ、長軸カウンタＮＬ及び誤差
レジスタＥＲがソフト的又はハト的に設けられている。

これらは、線分の近似座標発生のためのものである。一
般に、図形表示において最も基本的な図形は線分である
。このため、ＤＤＡ１２における線分座標の発生方法が
各種開発されている。また、Ｆ　Ｂ　１．４が離散的デ
ータのみを取り扱うことから、線分座標は本質的に近似
座標である。

（１）　Ｂｒｅｓｅｎｈａｍアルゴリズムの原理ここで
まず、Ｂｒｅｓｅｎｈａ１１アルゴリズムの原理につい
て説明する。

Ｂｒｅｓｅｎｈａｍアルゴリズムは、線分の近似座標を
発生する方法としてよく用いられる方法である。

Ｂｒｅｓｅｎｈａｍアルゴリズムでは、ます線分のＸ座
標の変位ｄｘ及びＹ座標の変位ｄｙが求められる。次に
、変位ｄｘとｄｙが比較される。比較の結果、大きい方
の座標（Ｘ又はＹ）が長軸、小さい方（Ｙ又はＸ）が短
軸とされる。これらの軸に沿った増分のうち、長軸に係
る増分は常に１とし、他方の短軸に係る増分は実際の線
分の座標に一番近い整数座標との誤差Ｅを調べて決定さ
れる。

このことを詳細に説明すると、以下のようになる。

まず、線分の始点がＰｓ　（Ｘｓ、　Ｙｓ）　、終点か
Ｐｃ（Ｘｅ、　Ｙｅ）であるとする。また、Ｘｅ＞Ｘｓ
　　Ｙｅ＞Ｙｓ。

Ｘｅ−Ｘ５＝２ｎ、　Ｙｅ−Ｙｓ＝２ｍ＋１　　（ｒｉ
、　　ｍ　：自然数）と仮定する。

このとき、 Ｘｅｓ　＝Ｘｅ−Ｘｓ Ｙｅｓ　＝Ｙｅ−Ｙｓ　　　　　　　　　　−（１）ｄ
ｘ＝　　Ｘｅ５ ｄｙ＝　　Ｙｅｓ　　ｌ　　　　　　　　　　・・・（
２）のように変位ｄｘ及びｄｙを求める。さらに、変位
ｄｘ及びｄｙの大小関係を両者の比較により求める。

比較の結果、 ｄｘ　＞　ｄｙ となった場合、ＢｒｅｓｅｎｈａｍアルゴリズムではＸ
座標か長軸、Ｘ座標が短軸に設定される。

今、近似される線分の真の座標値のうちＸ座標をＸ（ｉ
）、本アルゴリズムにより得られる近似Ｘ座標をＹ（ｉ
）、近似Ｘ座標Ｙ（ｉ）と真のＹ座標との誤差をＥ（ｉ
）と表すことにする。ただし、ｉは自然数で長軸（この
場合Ｘ座標）に沿った位置を表している。この仮定の下
では、長軸に係る増分を常に１にとることは、 Ｘ（１）　＝　Ｘ（＋−１）　＋１ と表される。

ここで、ＦＢ１４は離散的データしか取り扱えないため
、近似Ｘ座標Ｙ（ｊ）は整数である必要がある。すなわ
ち、真のＹ座標Ｙ（ｉ）は本来実数値であるが、これを
Ｆ　Ｂ　］−４で取り扱うためには最も近い整数に近似
する必要かある。

この様な要請から、近似Ｘ座標Ｙ（ｊ）を求める際、誤
差Ｅ（ｊ）なる指標を用いる。誤差Ｅ（ｉ）は、Ｅ（ｉ
）＝Ｅ（ｉ−１）＋ｄｘ／ｄｙ　　　　　＝・（３）と
表される。すなわち、長軸に沿ってまたけ増加させてい
った場合のＹ座標の増過分（すなわち線分の勾配）　ｄ
ｘ／ｄｙを加算していくことにより求められる数値であ
る。

本アルゴリズムでは、誤差ＩＥ（Ｊ）の値に応じて近似
Ｘ座標Ｙ（ｉ）を次のように増加させる。

Ｙ（１）−Ｙ（ｉ−１）　＋１　　　（Ｅ（ｉ）≧１／
２）Ｙ（ｉ）＝　Ｙ（ｉ−１）　　　　　（Ｅ（４）　
＜　１　／　２　）・・・（４） ここでＹが増加された場合、 Ｅ（ｉ）＝Ｅ（ｉ）　−１・・・（５）を行う必要があ
る。すなわち、次回以降の近似Ｘ座標Ｙ（ｔ）のインク
リメント可否の判断を式（４）の分岐条件で行うため、
かかる処理を行う。

なお、Ｅ（ｊ）　＝　１　／　２の場合、近似Ｘ座標Ｙ
（ｉ）は増加させずともよい。すなわち式（４）の分岐
条件の等号はいずれの条件式の不等号に付加されてもよ
い。

この式（４）及び（５）に従い近似Ｘ座標Ｙ（ｉ）を発
生させていこうとすると、増加可否の判定式か式（４）
の括弧内に示されるように１／２を境界とする式になる
。

そこで、増加可否の判定を簡単にするために、誤差Ｅ（
ｊ）に−１／２の値を有する初期値Ｅｏを加えて判定す
る方法か採られている。

この方法を採用する場合、式（４）は次のように変形さ
れる。

Ｙ（ｉ）−Ｙ（ｊ−１）＋　１　　　（Ｅ（ｉ）十Ｅｏ
≧０）Ｙ（ｉ）＝Ｙ（ｉ−］）　　　　　　（Ｅ（ｔ）
＋Ｅｏ＜　０）従って、括弧内が符号判定式となり、増
加可否の判定が簡単になる。

（２）　１３ｒｅｓｅｎｈａｍアルゴリズムの初期動作
次に、実際にＩ）ＤＡ１２によりＢｒｅｓｅｎｈａｍア
ルゴリズムを稼働させる場合の流れについて説明する。

第４図には、Ｂｒｅｓｅｎｈａｍアルゴリズムの初期動
作の流れが示されている。

動作開始］−〇〇直後には、まず始点Ｐｓと終点Ｐｅ０
間の変位ｄｘ及びｄｙを求める演算が行われる（１０２
．１０４）。この演算は、前述の式（１）及び（２）に
より行われる。

このようにして求められた変位ｄｘ及びｄｙは、次にそ
の大小か比較される（１０６）。この結果、前者が大の
場合にはステップ１０８−・、小の場合にはステップ１
１０へ移行する。

ステップ１０８へ移行した場合、Ｘ座標が長軸、Ｙ座標
が短軸に設定される。すなわち、このステップ１０８及
び引き続くステップ１１２．１１４により、以下の演算
か行われる。

５ｓ＝Ｙｓ、　５ｅ＝Ｙｅ Ｌｓ＝ＸｓＳＬｅ＝Ｘｅ　　　　　　　　−’−（７）
Ｓｅｓ　＝Ｙｅｓ　、、　Ｌｅｓ、＝Ｘｅｓ　　　　−
（８）ｄＳ＝ｄｙ、　ｄＬ−ｄｘ　　　　　　　　・・
・（９）ここで、Ｓｓ及びＳｅは短軸の始点及び終点座
標、Ｌｓ及びＬｅは長軸の始点及び終点座標、Ｓｅｓ及
びＬｅＳは短軸及び長軸に沿った座標差、ｄｓ及びｄＬ
は短軸及び長軸に沿った変位である。

他方、ステップ１１０に移行した場合には、Ｙ座標が長
袖、Ｘ座標が短軸に設定される。この場合のステップ１
１０及び引き続くステップ１１６．１１８の演算は、式
（７）〜（９）のＸ、Ｙを入れ替えた演算となる。

ステップ１１４又は１１８の終了後、すなわち短軸・長
軸の設定後には、ステップ１２０〜１２６による初期設
定が行われる。このうち、ステップ１２０では座標差Ｓ
ｅｓ及びｌ、ｅｓの符号に応じて長軸及び短軸座標カウ
ンタＳｃｌ及びＬｄのｕｐ、　ｄ。

ｗｎが設定される。ステップ１２２では誤差Ｅ（ｉ）の
初期値Ｅｏか一１／２に設定され、ステップ１２４では
誤差Ｅ（ｔ）の補正値Ｅｃが−１に設定され、ステップ
１２６ては誤差Ｅ（１）の増過分Ｅｄがｄｓ／ｄＬに設
定される。

これにより、Ｂｒｅｓｅｎｈａｍアルゴリズムの初期動
作が終了する（１２８）。

（３）　Ｂｒｃｓｅｎｈａｍアルゴリズムの近似座標発
生処理 第５図には、Ｂｒｅｓｅｎｈａｍアルゴリズムにおける
近似座標発生処理の流れが示されている。

近似座標発生処理の開始直後（２００）には、短軸及び
長軸の始点座標Ｓｓ及びＬｓが短軸及び長軸座標カウン
タＳｄ及びＬｄにセラ）・される（２０２）。さらに、
長軸カウンタＮＬに長軸に沿った変位ｄＬ、すなわち後
述する演算ループの繰り返し回数が設定される（　２０
４．）。さらに、誤差レジスタＥＲに初期値Ｅｏがセッ
トされる（２０６）。

こののち、線分近似のためのループ動作に移行する。こ
のループにおいては、まずＦＢｌ−４に対する短軸及び
長軸座標カウンタＳｄ及びＬｄの内容の出力が行われる
（２０８）。Ｆ　Ｂ　：１．４に係る出力が書き込まれ
ると、ＣＲＴ１６の画面上に線分が表示される。

次に、長軸カウンタＮＬかデクリメントされ（２１０）
、その内容が０となるか否かが判定される（２１２）。

この結果、Ｏとならない場合には線分近似座標の発生が
終了していないため判定２１４に移り、０となる場合は
ループを抜は出し処理を終了する（２１６）。

判定２］４においては、誤差レジスタＥＲの内容が０以
上であるか否かか判定される。これは、式（６）の括弧
内の判定式に対応する動作である。

０以上とされた場合には、短軸の座標値、すなわち短軸
座標カウンタＳｄをインクリメントするステップ２１８
に移る。さらに、ステップ２２０に移行し、誤差レジス
タＥＲの内容に補正値Ｅｃを加算する。すなわち、式（
５）を実行する。

判定２１４において０より小と判定された場合及びステ
ップ２２０の終了後には、ステップ２２２に移行する。

ステップ２２２では、誤差レジスタＥＲにさらに増過分
Ｅｄが加算される。すなわち、式（３）が実行される。

こののち、長軸の座標値、すなわち長軸座標カウンタＬ
ｄがインクリメントされる。

このようにして、ＢｒｅｓｅｎｈａＴ１１アルゴリズム
が実行され線分の近似座標か発生する。

［発明が解決しようとする課題］ （１）従来の問題点 前述のＢｒｅｓｅｎｈａｍアルゴリズムでは、長軸の変
位が偶数、短軸の変位が奇数の場合、始点Ｐｓと終点Ｐ
ｅを入れ換えて近似座標を求めると、中点の近似座標が
一致しないという問題がある。

以下この問題を詳細に説明する。

状況として、Ｐｓ　（Ｘｓ、　Ｙｓ）及びＰｅ（Ｘｅ、
　Ｙｅ）を両端とし、Ｘｅ＞Ｘｓ、　Ｙｅ＞Ｙｓの線分
を考える。また、ｄｘ＝Ｘｅ−Ｘｓ＝　２ｎ　、　ｄｙ
＝Ｙｅ−Ｙｓ＝　２＋＋＋　＋　１　（ｎｍ　、自然数
）とすれば、ｎ　＞ｍのときＸ座標が長軸、ｎ＝川のと
きＹ座標が長軸となる。

この線分の中点近似座標Ｐｎ（Ｘｎ　、　Ｙｎ）を、始
点と終点を入れ換えた２つの場合について求めてみる。

■始点をＰｓ、終点をＰｅとした場合 この場合、Ｙ座標を長軸として中点近似Ｘ座標Ｘｎを前
述のアルゴリズムで求めると、次の式のようになる。す
なわち Ｘｎ＝Ｘ５＋ｎ となる。この値は整数なので、そのまま中点近似Ｘ座標
Ｘｎとなる。

また、Ｘ座標が長軸となるときには中点近似Ｙ座標Ｙｎ
は Ｙｎ＝Ｙｓ＋ｎ（２ｍ　＋１　）　／　２ｎ＝Ｙｓ＋ｍ
　＋１／２ ＝Ｙｓ＋（ｍ＋１）　　−１／２　　　−（１０）とな
る。ただし、このＹｎは実数であるため整数近似した値
が中点近似Ｙ座標Ｙｎかとされる。式（１０）かられか
るように、整数近似するとすればＹｓ＋■又はＹｓ＋（
ｍ＋１）のいずれかである。前掲の式（６）に従うとす
ると、中点近似Ｙ座標はＹｓ＋（ｍ＋１）とされる。

まとめると、近似座標は次のようになる。

Ｘｎ＝Ｘ５＋ｎ Ｙｎ＝Ｙｓ＋　（ｍ＋　１　）　　　　　　　　−（１
］　）■始点をＰｃ、終点をＰｓとした場合 この場合も同様の演算を行うと、 Ｘｎ＝Ｘｅ−ｎ Ｙｎ＝Ｙｅ＋（２Ｅ　＋　１）　／　２ｎ　＊　（−ｎ
　）＝Ｙｅ　−（ｍ　＋　１　／　２） ＝Ｙｅ−■−１／２ となり、式（６）の判定式に基つきまとめるとＸｎ＝Ｘ
ｅ−ｎ Ｙｎ＝Ｙｅ　−（ｍ　＋１）　　　　　　−（］　２）
となる。

■両者の比較 次に、始点をＰｅ、終点をＰｓとした場合の式（１２）
の変形を行い、始点をＰｓ、終点をＰｅとした場合の式
（１１）と比較する。

まず、式（１２）のうち Ｘｎ＝Ｘｅ−ｎ に仮定Ｘｅ−Ｘ５＝２ｎを代入してＸｅを消去するとＸ
ｎ＝　（２ｎ　＋Ｘｓ）　−ｎ ＝Ｘｓ＋ｎ となる。これは式（１１）と一致するため、変位が偶数
のＸ座標が短軸、変位が奇数のＹ座標が長軸となる場合
には点Ｐｅ及びＰｓのうちいずれを始点にしても同じ中
点近似座標か得られることになる。

一方、式（１２）のうち Ｙｎ＝Ｙｅ　−（ｍ　＋　１） に仮定’Ｖｅ−Ｙｓ＝　２ｍ　＋　１を代入してＹｅを
消去すると Ｙｎ＝　（２ｍ　＋１　＋Ｙｓ）　−（＋ｎ　＋１）＝
Ｙｓ＋ｍ となり、これは式（１１）と一致しない。

これは、短軸の変位か奇数で長軸の変位が偶数の場合に
いずれの点を始点とするかで中点近似座標が異なること
を示している。

（２）問題発生の具体例 以上述べた中点近似座標不一致の問題は、具体的にはこ
の近似座標発生方法による直線の表示、その組み合わせ
である図形の描画等の場合に顕在化する。

■第６図（ａ）の例 図形Ａ、Ｂか１つの線分Ｐ３−Ｐ４を共用するとき、こ
の線分Ｐ３−Ｐ４は２つの図形Ａ、Ｂの描画の際にそれ
ぞれ描画される。このとき、図において矢印３．００−
１及び３００−２で示される方向で図形Ａ及びＢに係る
描画が行われると、それぞれの描画について異なる２個
の中点座標が生じることがある。この場合、線分Ｐ：３
−Ｐ４が部分的に２重化する。

■第６図（ｂ）の例 図形（この図では“Ａ”文字）を回転させると、同し文
字であっても描画方向が変わってしまう。

この場合、中点座標が１−ドツトすれてしまい同し形の
図形にならない。

■線分消去時の不具合 本アルゴリズムで描画された線分を消去する場合、一般
に、描画時と同じ始点、終点の線分で“０”書き込みを
行う。かかる書き込みにより、描画時に“１”となって
いたドツトが“０″゛となり、線分が消去されることに
なる。しかし、消去時に始点と終点か入れ換わってしま
った場合、“０′′書き込みによっても中点近似座標不
一致により消し残しが発生してしまう。

■従来においては、これらの間融を解決するために線分
の描画方向をいずれかに固定して処理していた。従って
、描画したい線分の描画方向か決められた方向と違う場
合には始点と終点を入れ換えなければならず、このため
処理速度か遅くなる、回路部品点数が増えるといった不
具合か生じていた。

（３）発明の目的 本発明は、この様な問題点を解決することを課題として
なされたものであり、描画方向により近似座標の値が変
イっることがなく、従って処理速度が速（ＤＤＡが簡易
な回路構成でよい線分近似座標発生方法を提供すること
を目的とする。

［課題を解決するための手段］ このような目的を達成するために、本発明は、誤差Ｅ（
１）の値か所定値に等しいときに、短軸の増加方向が正
の場合には短軸近似座標に前記加算を施し、負の場合に
はそのまま維持することを特徴とする。

［作用］ 本発明の線分近似座標発生方法においては、解決するも
のであり、誤差ＩＥ（ｉ）の値か所定値、例えば１／２
に等しいときに、短軸の増加方向に応じて短軸近似座標
の加算可否が決定される。すなわち、短軸の増加方向が
正の場合には加算され、負の場合には加算されない。従
って、始点と終点の入れ替えによる座標値の変化が発生
せず、同一の近似座標か簡易な手段で得られることにな
る。

［実施例］ 以下、本発明の好適な実施例について図面に基づき説明
する。なお、第３図乃至第６図に示される従来例と同様
の構成には同一の符号を伺し説明を省略する。

第１図及び第２図は、本発明の一実施例に係る線分近似
座標発生方法の流れが示されている。このうち、第１図
は初期演算、第２図は近似座標発生処理を示している。

本実施例に係る方法を実現するための装置としては、例
えば第３図に示されるような構成かあげられる。このた
め、以下の説明では本発明の動作についてのみ説明する
。

（１）実施例の初期演算 第１図に示される初期演算において、ステップ１００〜
１２０は第４図の従来例と同様の処理である。

ステップ１２０の終了後、ずなわぢ長軸及び短軸座標カ
ウンタＬｄ及びＳｄのｕｐ、ｄｏｗｎ設定の後、本発明
の特徴に係る動作１３０〜１３８に移行する。

まず、判定１３０において短軸に沿った座標差Ｓｅｓが
０より大であるか否かが判定される。これは、短軸に沿
った座標増加方向が正方向であるか否かの判定に相当す
る。

次に、判定１３０の結果に応してステップ１３２又は１
３４に分岐する。すなわち、Ｓｅｓ＞Ｏの場合にはステ
ップ］３２、Ｓｅｓ≦Ｏの場合にはステップ１３４に移
る。

この実施例においては、演算の簡略化のために従来例に
おいて示されている数式のうち、Ｅｏ−−１／２ Ｅ（ｊ）　＝　Ｅ（ｔ−１）　十ｄＳ／ｄＬＥ（ｉ）　
＝　Ｅ（ｉ）−１ Ｅ（ｉ）＋ＩＥｏ≧０ を以下のように変形している。

Ｅｏ＝−ｄＬ Ｅ（＋）　＝　Ｅ（＋）−１−２ｄＳ Ｅ（ｔ）＝Ｅ（ｉ）　−２ｄＬ Ｅ（ｉ）＋Ｅｏ≧０ すなわち、従来式の両辺に２ｄＬを乗じ、２ｄｌ、Ｅ（
ｉ）を新たにＥ（ｉ）とおく。これにより、以後の演算
における除算の削除、演算数値の整数化を実現している
。

ステップ１３２又は１３４以降は、この様な変形式に従
い実行される。

まず、ステップ１３２では誤差Ｅ（ｆ）の初期値Ｅ。

に−ｄＬを、他方ステップ１３４では−ｄＬ−１を設定
し、終了後は共にステップ１３６に移行する。

これらのステップ１３２及び１−３４により、異なる値
を初期値ＥＯに設定する点が、本発明の特徴に係る動作
である。

すなわち、Ｓｅｓ＞０であり短軸の増加方向が正方向の
場合には従来と同様の初期値Ｅｏの設定を行い、Ｓｅｓ
≦０であり短軸の増加方向か負方向の場合にはさらに１
を減算した値の設定を行う。

この設定は、短軸の増加方向が負方向かっＥ（ｉ）−〇
の場合にＥ（ｉ）＋Ｅｏ≧０が成立しないようにする役
割を果たす。

ステップ］３６では誤差Ｅ（ｉ）の補正値Ｅｃが一２ｄ
Ｌに、続き実行されるステップ１３８では誤差Ｅ（ｉ）
の増過分Ｅｄが２ｄＳに、それぞれ設定され、そののち
終了する（１２８）。

（２）実施例の近似座標発生処理 第２図には、本実施例の近似座標発生処理の流れが示さ
れているが、この動作は第５図に示される従来動作と同
様である。

（３）従来との比較 第２図及び第２図に示される流れに従い短軸の変位が奇
数で長袖の変位が偶数の線分をＪｊ’７ｉ画する場合を
考える。比較の便宜のため、線分の両端の点をＰｓ　（
Ｘｓ、　Ｙｓ）及びＰｃ（Ｘｃ、　Ｙｃ）と設定し、Ｘ
ｅ＞Ｘｓ、　Ｙｅ＞Ｙｓ、　ｄｘ＝Ｘｅ−Ｘｓ＝２ｎ　
、　ｄｙ＝Ｙｅ−Ｙｓ＝２ｍ　＋１　（ｎ、　ｍ　　：
自然数）の関係が成立しているとする。

この場合、始点かＰＳ％終点がＰｅならば、Ｙ座標及び
Ｘ座標をそれぞれ長軸とした場合の中点近似Ｘ座標Ｘｎ
及び中点近似Ｙ座標Ｙｎを実数で求めると、前述のよう
に Ｘｎ＝Ｘ５＋ｎ Ｙｎ＝Ｙｓ＋ｎ（２ｍ　　＋　］　）／　２ｎ＝Ｙｓ十
ｍ　＋１／２ ＝Ｙｓ＋（ｍ＋１）　　−１／２ となる。

このうち中点近似Ｘ座標Ｘｎは繁数であるため、そのま
ま中点近似Ｘ座標Ｘｎとして採用し得る。

他方、中点近似Ｙ座標Ｙｎは実数であるため、整数近似
した値を中点近似Ｘ座標Ｙｎとして採用する必要がある
。

中点近似Ｙ座標Ｙｎとして採用する値としては、前にも
述べたようにＹｓ＋ｍとＹｓ　＋（ｍ　＠−１，）の２
種類がある。従来例ではステップ１２２で設定される初
期値Ｅｏの値に基づき行われる判定２１４の結果、後者
、すなわちＹｓ十（ｒｎ＋１−　）が採用される。

本実施例ではステップ１３２で設定される初期値Ｅｏの
値に基づき行われる判定２］４の結果、やはりｙｓ十（
ｍ＋１　）が採用される。

従って、本実施例では中点近似座標は最終的にＸｎ＝Ｘ
５＋ｎ Ｙｎ−４ｓ＋　（ｍ＋　１．　）　　　　　　　−（１
，３）となる。

逆に、始点がＰｅ、終点がＰｓの場合、中点近似Ｘ座標
Ｘｎ及び中点近似Ｘ座標Ｙｎを実数で求めると、前述の
ように Ｘｎ−Ｘｅ−ｎ Ｙｎ＝Ｙｅ十（２ｍ　　＋　１）／２ｎ　　＊　　（−
ｎ　）＝Ｙｅ　−（ｍ　＋　１　／　２） ＝Ｙｅ−ｍ−１／２ となる。

この場合にも、中点近似Ｘ座標Ｘｎは整数となりそのま
ま採用し得るが、中点近似Ｘ座標Ｙｎは実数であるため
整数近似する必要がある。従来例では、結果としてＹｎ
＝Ｙｅ　−（１１１＋１）に近似されていたが、本実施
例ではステップ１３４が実行されるためＹｅ−ｍに近似
される。

すなわち本実施例ではこの場合の中点近似座標は Ｘｎ＝Ｘｅ−ｎ Ｙｎ＝Ｙｅ−ｍ　　　　　　　　　　　　　　・＝　　
（１，４）となる。

この様にして始点・終点を入れ替えた場合の中点近似座
標が求められたが、これらを比較すると次のように一致
することがわかる。

すなわち、式（１４）において変位ｄｙ−Ｙｅ−Ｙｓ−
２ｍ＋１を変形し代入すると、 Ｙｎ−（Ｙｓ＋　　２ｍ　　＋　１　　）　　−ｍ＝Ｙ
ｓ＋（ｍ＋１　） となり、式（１３）とまったく同じ値に近似されている
ことが明らかとなる。

従って、本実施例においては、前述の初期値設定により
従来と同様の近似座標発生処理で描画方向による近似座
標の差の発生を防止することができる。

［発明の効果］ 以上説明したように、本発明によれば、短軸増加方向に
応じて初期値設定を変更するようにしたため、１本の線
分を異なる短軸増加方向で近似する際の近似座標の差の
発生が防止できる。この結果、例えば１個の線分を共用
する図形の描画の際、共用される線分が２重化すること
がない。また、図形に回転等の処理を施した場合にも描
画方向による図形変化が生しない。さらに、線分消去に
おける消し残しが防止される。

従って、従来において採用されていた方法、例えば描画
方向の固定を廃止することができ、始点・終点の入れ替
えが不必要となる。この結果、簡易な改良で処理速度の
高速化、回路構成の肥大防止等の効果を得ることかでき
る。

【図面の簡単な説明】

第１図は、本発明の一実施例に係る線分近似座標発生方
法の初期演算のフローチャート図、第２図は、この実施
例における近似座標発生処理のフローチャート図、 第３図は、ラスクスキャン型ディスプレイ装置の一般的
な構成を示すブロック図、 第４図は、Ｂｒｅｓｅｎｈａｍアルゴリズムによる線分
近似座標発生方法の初期演算のフローチャート図、第５
図は、Ｂｒｅｓｅｎｈａ１１アルゴリズム方式による線
分近似座標発生方法の近似座標発生処理のフローチャー
ト図、 第６図（ａ）は、２個の図形が線分Ｐ　３−Ｐ４を共有
している場合の線分の描画方向を示す図、第６図（ｂ）
は、３本の線分で構成されている文字“Ａ”の回転前と
回転後の線分の描画方向を示す図である。 １２　　・・ １４　　・・・ １６　　・・・ Ｓｄ　　　・・ Ｌｄ　　　・・ ＮＬ　　　・・・ ＥＲ・・ Ｅ（ｉ）　　・・・ Ｅｏ　　・・・ Ｅｃ　　・・・ Ｅｄ　　　・・・ ｘ ａｙ　　・・ ｄｓ　　・・・ ｄＬ　　・・ ディジタル微分回折器 フレームバッファ ＲＴ 短軸座標カウンタ 長軸座標カウンタ 長軸カウンタ 誤差レジスタ 誤差 誤差の初期値 誤差の補正値 誤差の増過分 Ｘ座標の変位 Ｘ座標の変位 短軸座標の変位 長軸座標の変位

Claims (1)

【特許請求の範囲】
1. ディスプレイ装置の画面上に描画する線分の始点及び終
   点の座標値に基づき短軸及び長軸を設定し、長軸を所定
   値ずつ増加させた際の短軸方向の線分座標の増加分を演
   算したのち、長軸座標を始点の長軸座標値から所定量刻
   みで終点まで増加させながら、線分座標の増加分を累積
   加算し短軸近似座標の増加に伴い所定量を減算すること
   による短軸近似座標の加算の指標値たる誤差値の演算と
   、この誤差値が所定値以上のときには短軸近似座標に所
   定量を加算し、誤差値が所定値以下のときには短軸近似
   座標をそのまま維持する近似座標演算と、を行う線分近
   似座標発生方法において、誤差値が所定値に等しいとき
   に、短軸の増加方向が正の場合には短軸近似座標に前記
   加算を施し、負の場合にはそのまま維持することを特徴
   とする線分近似座標発生方法。