(57)【特許請求の範囲】
【請求項１】
図形を線で表す線分データをドットで表すドットデータにドット変換する方法において、
線分データをドット変換する際、線分の傾きを算出して処理を行うデジタルディファレンシャルアナライザの線分描画アルゴリズムによるＤＤＡ方式と、誤差項を算出して処理を行うブレゼンハムの線分描画アルゴリズムによるブレゼンハム方式との双方を設定し、前記線分データの特性に応じて、処理速度が前記誤差項を算出して処理を行うブレゼンハム方式よりも相対的に優位な前記線分の傾きを算出して処理を行うＤＤＡ方式と、変換精度が前記線分の傾きを算出して処理を行うＤＤＡ方式よりも相対的に優位な前記誤差項を算出して処理を行うブレゼンハム方式とを選択的に用いて、前記線分データを速く、高精度に前記ドットデータに変換することを特徴とする線分データ変換方法。
【請求項２】
図形を線で表す線分データをドットで表すドットデータにドット変換する方法において、
線分データをドット変換する際、線分の傾きを算出して処理を行うデジタルディファレンシャルアナライザの線分描画アルゴリズムによるＤＤＡ方式と、誤差項を算出して処理を行うブレゼンハムの線分描画アルゴリズムによるブレゼンハム方式との双方を設定し、前記線分データにおける線分の傾きが所定の範囲内にあるときは前記線分の傾きを算出して処理を行うＤＤＡ方式を用い、それ以外の線分データは前記誤差項を算出して処理を行うブレゼンハム方式を用いて、前記線分データを前記ドットデータに変換することを特徴とする線分データ変換方法。
【請求項３】
図形を線で表す線分データをドットで表すドットデータにドット変換する方法において、
線分データをドット変換する際、線分の傾きを算出して処理を行うデジタルディファレンシャルアナライザの線分描画アルゴリズムによるＤＤＡ方式と、誤差項を算出して処理を行うブレゼンハムの線分描画アルゴリズムによるブレゼンハム方式との双方を設定し、前記線分データにおける線分の長さが所定の範囲内にあるときは前記線分の傾きを算出して処理を行うＤＤＡ方式を用い、それ以外の線分データは前記誤差項を算出して処理を行うブレゼンハム方式を用いて、前記線分データを前記ドットデータに変換することを特徴とする線分データ変換方法。
【請求項４】
図形を線で表す線分データをドットで表すドットデータにドット変換する方法において、
線分データをドット変換する際、線分の傾きを算出して処理を行うデジタルディファレンシャルアナライザの線分描画アルゴリズムによるＤＤＡ方式と、誤差項を算出して処理を行うブレゼンハムの線分描画アルゴリズムによるブレゼンハム方式との双方を設定し、前記線分データにおける線分の傾き及び長さが所定の範囲内にあるときは前記線分の傾きを算出して処理を行うＤＤＡ方式を用い、それ以外の線分データは前記誤差項を算出して処理を行うブレゼンハム方式を用いて、前記線分データを前記ドットデータに変換することを特徴とする線分データ変換方法。
【請求項５】
図形を線で表す線分データをドットで表すドットデータにドット変換する装置において、
線分データをドット変換する方式として、線分の傾きを算出して処理を行うデジタルディファレンシャルアナライザの線分描画アルゴリズムによるＤＤＡ方式と、誤差項を算出して処理を行うブレゼンハムの線分描画アルゴリズムによるブレゼンハム方式との双方の方式を記憶するドット変換方式記憶手段と、
前記線分データの特性を取り込む線分特性取込み手段と、
前記線分データの特性が予め定められた条件に該当するか否かを判別する線分条件判別手段と、
前記線分条件判別手段による判別に基づいて、前記線分データをドット変換する方式として、処理速度が前記誤差項を算出して処理を行うブレゼンハム方式よりも相対的に優位な前記線分の傾きを算出して処理を行うＤＤＡ方式と、変換精度が前記線分の傾きを算出して処理を行うＤＤＡ方式よりも相対的に優位な前記誤差項を算出して処理を行うブレゼンハム方式とのいずれか一を設定するドット変換方式設定手段と、
そのドット変換方式設定手段で設定された前記線分の傾きを算出して処理を行うＤＤＡ方式又は誤差項を算出して処理を行うブレゼンハム方式により前記線分データをドットデータに変換する変換実行手段と、を含み、
前記線分データを速く、高精度に前記ドットデータに変換することを特徴とする線分データ変換装置。
【請求項６】
図形を線で表す線分データをドットで表すドットデータにドット変換する装置において、
線分データをドット変換する方式として、線分の傾きを算出して処理を行うデジタルディファレンシャルアナライザの線分描画アルゴリズムによるＤＤＡ方式と、誤差項を算出して処理を行うブレゼンハムの線分描画アルゴリズムによるブレゼンハム方式との双方の方式を記憶するドット変換方式記憶手段と、
前記線分データにおける線分の長さ及び傾きの少なくとも一の特性を取り込む線分特性取込み手段と、
前記線分の長さが設定値より短いこと、及び前記線分の傾きが所定範囲内にあることの少なくとも一の条件に該当するかどうかを判別する線分条件判別手段と、
前記線分条件判別手段によって、前記線分データが前記少なくとも一の条件に該当すると判別された場合は、前記線分データをドット変換する方式として、前記線分の傾きを算出して処理を行うＤＤＡ方式を設定し、それ以外の場合は、前記誤差項を算出して処理を行うブレゼンハム方式を設定するドット変換方式設定手段と、
そのドット変換方式設定手段で設定された前記線分の傾きを算出して処理を行うＤＤＡ方式又は誤差項を算出して処理を行うブレゼンハム方式により前記線分データをドットデータに変換する変換実行手段と、
を含むことを特徴とする線分データ変換装置。
【請求項７】
前記線分特性取込み手段は、前記線分の長さ及び傾きを取り込み、
前記線分条件判別手段は、前記線分の長さが設定値より短いこと、及びその線分の傾きが所定範囲内にあることの２条件に該当するかどうかを判別し、
前記ドット変換方式設定手段は、前記線分条件判別手段によって、前記２条件を共に満たすと判別された場合は、前記線分の傾きを算出して処理を行うＤＤＡ方式を、そうでない場合は、前記誤差項を算出して処理を行うブレゼンハム方式を設定する請求項５又は６に記載の線分データ変換装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、図形を線分で表す線分データを、ドットで表すドットデータに変換ドット変換するための方法及び装置に関する。
【０００２】
【従来の技術】
図９のように線分ＡＢのデータをドット変換する際、一般には２つの方式がある。１つはデジタル・ディファレンシャルアナライザ（Digital Differential Analyser）の線分描画アルゴリズムによるＤＤＡ方式と、いわゆるブレゼンハム（Bresenham）の線分描画アリゴリズムによるブレゼンハム方式である。ＤＤＡ方式は、そのアルゴリズムの特性上、処理速度はブレゼンハム方式に比較して速い特長があるが、線分の種類によっては数値の精度が必ずしも高くないため、線分を正確に表現できなくなることがある。特に、基準線に対する傾きがごく小さい線分をドット変換するような場合は、その微小な傾きを再現できなかったり、長い線分の場合に誤差の累積で傾きが正確に表されない場合も生じる可能性がある。
【０００３】
一方、ブレゼンハム方式は、ＤＤＡ方式より処理は一般に遅いが、そのアルゴリズムの特長として、数値の精度がＤＤＡ方式より高く誤差が少ないため、わずかな傾きの線分や長い線分でもそれを正確に表現できる。なお、以上のようなＤＤＡ方式やブレゼンハム方式のアルゴリズムに関する参考文献として、例えば次のようなものがある。
「実践コンピュータグラフィックス−基礎手続きと応用−」（発行所：日刊工業新聞社、発行日：昭和６２年２月２８日）の第２章
「コンピュータ・グラフィックス」（発行所：日本コンピュータ協会、発行日：昭和５９年７月１５日）の第１１章
【０００４】
【発明が解決しようとする課題】
ところで、従来、線分データをドットデータに変換する方法や装置として、ＤＤＡ方式かブレゼンハム方式のいずれかが独立に設けられ、例えばある機種はＤＤＡ方式、また別のある機種はブレゼンハム方式でそれぞれドット変換するのが実情である。従ってＤＤＡ方式の機種は、処理は速いが変換精度が低いということになり、ブレゼンハム方式では変換の精度は高いが、処理速度は必ずしも速くないという結果を生じる。
【０００５】
本発明の課題は、線分データをドットデータに変換するドット変換の処理において、ＤＤＡ方式とブレゼンハム方式とのそれぞれの方式の長所が生かされるようにすることにある。
【０００６】
【課題を解決するための手段及び作用・効果】
この発明では、ドット変換に際し、線分データの傾きの程度や長さといった、線分データの特性に応じて、ＤＤＡ方式とブレゼンハム方式とを選択的に用いることにより、両方式のそれぞれの長所は生かし、短所はもう一方の方式でカバーすることで、全体として処理が速くかつ変換精度も高いものとなる。
【０００７】
すなわち、本発明の方法では線分データをドット変換する際、ＤＤＡ方式とブレゼンハム方式との双方を設定し、線分データの特性に応じてＤＤＡ方式とブレゼンハム方式とを選択的に用いて、線分データをドットデータに変換するものである。
【０００８】
上述の線分データの特性として、線分の長さ、線分の傾きを採用することができる。その場合、ＤＤＡ方式かブレゼンハム方式かを選択する基準として、ドットデータに変換すべき線分の長さが設定値より短いこと、及びその線分の傾きが所定範囲内にあることの少なくともいずれかの条件を満たす場合にＤＤＡ方式を、それ以外の場合にブレゼンハム方式を選択することができる。つまり、ＤＤＡ方式の短所として、微小な傾きを表現しにくいこと、及び長い線分で傾きの誤差が大きくなること等があるが、この場合はブレゼンハム方式を用い、その他の場合は処理が速いＤＤＡ方式を用いる。
【０００９】
上記のような方法を実施するに好適な装置としては、次の（１）〜（５）の要素を含むもの、すなわち（１）線分データをドット変換する方式としてＤＤＡ方式とブレゼンハム方式との双方の方式を記憶するドット変換方式記憶手段、（２）線分の長さ及び傾きの少なくとも一の特性を取り込む線分特性取込み手段、（３）上記線分の長さが設定より短いこと、及び線分の傾きが所定範囲にあることの少なくとも一の条件に該当するかどうかを判別する線分条件判別手段、（４）線分が上記少なくとも一の条件（線分の長さや傾き）に該当する場合は、線分データをドット変換する方式としてＤＤＡ方式を設定し、それ以外の場合はブレゼンハム方式を設定するドット変換方式設定手段、（５）そのドット変換方式設定手段で設定された方式により線分データをドットデータに変換する変換実行手段、を含むものとすることができる。
【００１０】
ここで、ＤＤＡ方式を採用する場合に、線分の傾きが所定範囲内にあること、かつ線分の長さが設定値より短いことの２条件のいずれにも該当する場合にＤＤＡ方式を、そうでない場合にブレゼンハム方式を設定することができる。
【００１１】
以上のようなＤＤＡ方式とブレゼンハム方式との、いわば選択的な切替え方式により、ＤＤＡ方式の長所である処理の速さと、ブレゼンハム方式の長所である変換精度の高さとの双方のメリットを享受し、線分データの種類特性に拘らず、線分データを速く、かつ高精度にドットデータに変換することができる。
【００１２】
【発明の実施の形態】
以下、図面に示す実施例に基づき、発明の実施の形態を説明する。図１（ａ）は、本発明の一例を、コンピュータ１を主体として構成した例を示すものである。ここでは、全体の制御を行うＣＰＵ２、その制御プログラム等を格納したＲＯＭ３、各種メモリ領域を有するＲＡＭ４、マウス・キーボード等の描画用入力装置５や、モニタ等の表示装置６と接続するための入出力インターフェース７、プリンタ８との通信を行うプリンタインターフェース９、並びにそれらを相互に接続するバス１０を有する。
【００１３】
なお、このシステムは、ホストコンピュータ１０で線分データをドットデータに変換するドット変換処理を行い、そのドットデータをプリンタ８に供給する例であるが、コンピュータ１０をプリンタに内蔵されたもの（プリンタコントローラ）として、全体をプリンタのシステムにすることもできる。その場合は、プリンタ８がプリンタエンジンに、プリンタインターフェース９がプリンタエンジンインターフェースとなり、入出力インターフェース７には外部装置としてホストコンピュータ等が接続され、ホストコンピュータからプリンタに送られた線分データを、プリンタでドットデータに変換することとなる。
【００１４】
いずれにしても、上述のＲＯＭ３は、全体のシステムを制御するシステムプログラム、フォント等の生成のためのフォントデータ、ＤＤＡ（デジタル・ディファレンシャル・アナライザ）方式のアルゴリズムにより線分データをドットデータに変換するためのＤＤＡ方式アルゴリズムプログラム、ブレゼンハム方式のアルゴリズムにより線分データをドットデータに変換するためのブレゼンハムアルゴリズムプログラム等、必要なデータ内容を格納したそれぞれのメモリ領域３ａ〜３ｄを有している。一方、ＲＡＭ４は、ＤＤＡ方式によるドット変換のフラグをたてるＤＤＡ方式フラグメモリ４ａ、線分データを両端の座標で記憶する線分データメモリ４ｂ、線分データをドット変換したドットデータを記憶するページメモリ４ｃ、処理の途中経過等を一時的に記憶するワークメモリ４ｄ等、必要なメモリ領域を持っている。なお、線分データメモリ４ｂ等、ＲＡＭ４の一部をハードディスク（ＨＤＤ）で構成することができる。
【００１５】
図２に線分データをドットデータにドット変換する処理の一例を示す。ステップＳ１（以下、単にＳ１という）で線分データを取り込む。これは図１（ｃ）の線分データメモリ４ｂに格納されている線分データ（一般にその線分の両端の座標で規定される）を取り込む。Ｓ２でその線分の長さを算出する。
【００１６】
ここで、一般に線分の長さを求めるのは、例えば（ｘ1，ｙ1）→（ｘ2，ｙ2）の線分の場合ならば（例えば図４参照）、数学的には｛（ｘ2−ｘ1）2＋（ｙ2−ｙ1）2｝の平方根を求めるが、そうすると処理時間が長くなるので、処理を簡略化する意味で、例えばｄｘ＝｜ｘ2−ｘ1｜，ｄｙ＝｜ｙ2−ｙ1｜を算出してこれを線分の長さとし、さらに線分が短いかどうかの基準として、ｄｘ＜しきい値、かつｄｙ＜しきい値かを判断し、この条件を満たす場合に当該線分の長さは短いものとみなし得る。Ｓ２及び後述のＳ５の処理はこのように簡略化できる。なお、図３の右上に示すように、線分は必ずｙ方向に増加するもの（ｙ1≦ｙ2）とした場合、ｙ2＜ｙ1ならば、線分（ｘ1，ｙ1）と（ｘ2，ｙ2）が交換される。この処理が図２のＳ３，Ｓ４に対応する。
【００１７】
そしてＳ５で、例えば上述のようにｄｘ＜しきい値、かつｄｙ＜しきい値かどうかを判断することにより、線分の長さは長さしきい値（設定値）より短いかどうかを判断する。長さしきい値より短ければ、Ｓ６で線分データの傾き（ｄｘ／ｄｙ）が線分両端の座標に基づいて算出される。さらにＳ７で、その線分の傾きが最小傾きしきい値と最大傾きしきい値の間にあるかどうかが判定される。また、ここでは、最大傾きしきい値は、最小傾きしきい値の逆数と設定している（図３の右上欄参照：縦線ハッチによる網部がＤＤＡ方式，網部以外がブレゼンハム方式）。
【００１８】
そしてＳ５で、線分の長さが長さしきい値より短く、かつＳ７で線分の傾きが最小及び最大傾きしきい値の範囲内にあると判断された場合に、Ｓ８においてＤＤＡ方式による線分データのドット変換、つまり線分データをドットデータに変換する処理が行われ、ページメモリに書き込まれる。また、Ｓ５で線分の長さが長さしきい値より長いと判断された場合、Ｓ７で線分の傾きは上記最小・最大傾きしきい値の範囲外にあると判断された場合は、Ｓ９によりブレゼンハム方式による線分データのドット変換が行われ、ページメモリに書き込まれる。
【００１９】
そして、Ｓ１０ですべての線分データの変換が終了したと判断されるまで、Ｓ１〜Ｓ９の処理が繰り返され、Ｓ１０の判断がＹｅｓとなれば、ページメモリに格納されたドットデータが、Ｓ１１でプリンタ８や表示装置に出力される。
【００２０】
Ｓ８のＤＤＡ方式によるドット変換は、公知のアルゴリズムによるものであるが、その処理について図３及び図４（線分Ｐ1Ｐ2）を参照して簡単に説明する。ここで、図３の右上部に示すように、線分の傾きを例えば（１）〜（４）の４種類に分けて処理することができる。分岐の基準は例えば、ｘ軸、ｙ軸、左右の４５°の直線であり、各領域の該当条件は次のように定義できる。
ｄｘ≧０，  ｄｘ  ＞ｄｙ──── （１）
ｄｘ＜０，｜ｄｘ｜＞ｄｙ──── （４）
ｄｘ≧０，  ｄｘ  ＜ｄｙ──── （２）
ｄｘ＜０，｜ｄｘ｜＜ｄｙ──── （３）
これら（１）〜（４）の種類に分けた処理において、基本的にはアルゴリズムは同じであるが、各傾きの線分の特徴に応じたプログラムが用意されていて、変数の扱い、正負の扱いなどが、（１）〜（４）でそれぞれ異なってくる。そこで、まず（１）の傾きの線分の処理について詳しく説明し、（２），（３），（４）の傾きの線分の処理については、違いに簡単に言及することとする。
【００２１】
Ｓa１で線分データのｘ成分dx、ｙ成分dyが、線分データの両端の座標（ｘ1，ｙ1）及び（ｘ2，ｙ2）から求められる。Ｓa２，Ｓa３，Ｓa４を経て（１）の傾きに属する線分の処理を行う。Ｓa５ではｄｄｘ（インクリメント値）＝１とし、Ｓa６で傾き△（delta）が求められ、Ｓa７でｉｎｔ（ｘ），ｉｎｔ（ｙ）をプロット（ページメモリに書き込み）する。ｉｎｔは整数の意味である。さらにＳa８を経てＳa９で、ｘ、ｙがそれぞれインクリメントされて、Ｓa７〜Ｓa９が繰り返し実行され、線分データの終端に至って、Ｓa８でこの変換処理が終了する（ｘ＝ｘ2）。
【００２２】
なお、（４）の傾きの線分については、Ｓa１０でｄｄｘ＝−１とされ、（２），（３）の傾きの線分については、Ｓa３からＳa１１で傾きを求めて、Ｓa１２〜Ｓa１４へ移行し、ｙ＝ｙ2になれば処理終了となる。
【００２３】
なお、このようなＤＤＡ方式によるドット変換は、いわゆる固定小数点方式を用いたアルゴリズムであるため、処理が比較的速い長所があるが、図７に示すように、線分Ｐ1Ｐ2の傾き△が相当小さい場合は、固定小数点方式によるために演算結果が傾きを持たないようになる場合がある。例えば、小数点以下８ビットをもつ固定小数点方式を用いた場合、いま図７においてｄｘ＝１０００、ｄｙ＝３（いずれもドット数）とすれば、これは非常になだらかな線分であるが、「△＝ｄｙ／ｄｘ＝３／１０００＝０．００３→０．０」
△＝０．０となってしまい、実際の線分における傾きがドットデータでは傾きを持たなくなる。これは、１／２５６（＝１／２８）以下の値を表現できないためである。
【００２４】
また、図８に示すように、線分Ｐ1Ｐ2が長い線分である場合、例えば図８において、「ｄｘ＝５０００、ｄｙ＝４９０２（いずれもドット数）」とし、「△＝４９０２／５０００＝０．９８０４０００→０．９７６５６２５」となり、固定小数点方式によるための誤差が、０．００３８３７５生じる。この０．００３８３７５の誤差がｄｘ回繰り返されることにより、「０．００３８３７５×５０００」で、約１９ドットの誤差が生じる。
【００２５】
従って、図２のＤＤＡ方式によるドット変換は、線分の長さが比較的短く、かつ線分の傾きが所定範囲内にある場合に適し、このような場合にＤＤＡ方式を用いることにより、高速にドット変換ができる。
【００２６】
一方、図５及び図６（線分Ｐ1Ｐ2）に、ブレゼンハム方式のアルゴリズムによるドット変換の一例を簡単に示す。この処理においても、線分の傾きは（１）、（２）、（３）、（４）の４種類に分けられ、各傾きの特徴に応じた変更がなされるが、基本的なアルゴリズムは同じであるので、主に（１）の傾きの線分について説明し、その後に（２）〜（４）の傾きの線分について補足する。
【００２７】
Ｓｂ１〜Ｓｂ４は図３のＳａ１〜Ｓａ４と同じで、要するに、処理すべき線分が（１）〜（４）のいずれの傾きのものかをみる。Ｓｂ５〜Ｓｂ１２が（１）の傾きのものに対応し、Ｓｂ６で誤差項ｅを算出する。Ｓｂ７で（ｘ，ｙ）をプロット（ページメモリに書き込み）し、Ｓｂ８を経てＳｂ９でｘをインクリメントし、Ｓｂ９において、上述の誤差項ｅが正であるか否かにより、Ｓｂ１１又はＳｂ１２の処理を行う。このような処理を線分の始端から終端まで行い、Ｓｂ７で終端に達すれば、これで変換処理は終了する。
【００２８】
（４）の傾きの線分については、Ｓｂ１３を経てＳｂ６へ流れ、またＳｂ１４のＹｅｓの判断で（２）の傾きの線分を処理し、Ｎｏの判断で（３）の傾きの線分を処理する。Ｓｂ１５〜Ｓｂ２２が（２）の処理であるが、（３）の処理においてはＳｂ２３からＳｂ１６へ流れる。
【００２９】
このブレゼンハム方式の場合は、公知のように基本的には固定小数点方式ではなく、整数方式が用いられるため、誤差が少なく線分データをドットデータに変換する際の正確性が高い。ただ処理時間はＤＤＡ方式の方が速いため、線分データがあまり長くないときや、傾きが所定範囲内にあるときは、図３のＤＤＡ方式により変換の高速性を確保する。
【００３０】
また、以上の実施例において、図１のＲＯＭ３がドット変換方式記憶手段に、図２のＳ２、Ｓ６等のステップとこれを実行するＣＰＵが線分特性取込み手段に、図２のＳ５、Ｓ７等のステップとこれを実行するＣＰＵがドット変換方式設定手段及び変換実行手段にそれぞれ相当するものと言うことができる。
【図面の簡単な説明】
【図１】本発明の変換方法を実施するのに好適な装置構成の一例を示すブロック図。
【図２】本発明による線分データのドット変換の一例を示すフローチャート。
【図３】図２におけるＳ８のＤＤＡ方式の処理をさらに詳しく示すフローチャート。
【図４】ＤＤＡ方式によるドット変換の概念図。
【図５】図２におけるＳ９のブレゼンハム方式の処理をさらに詳しく示すフローチャート。
【図６】ブレゼンハム方式によるドット変換の概念図。
【図７】ＤＤＡ方式によりなだらかな線分をドット変換する場合の欠点を説明する図。
【図８】ＤＤＡ方式により長い線分をドット変換する場合の欠点を説明する図。
【図９】一般に線分データをドットデータに変換する概念を示す図。
【符号の説明】
１ コンピュータ
２ ＣＰＵ
３ ＲＯＭ
４ ＲＡＭ
【図１】
0003610997.tif 000002
【図２】
0003610997.tif 000003
【図３】
0003610997.tif 000004
【図４】
0003610997.tif 000005
【図５】
0003610997.tif 000006
【図６】
0003610997.tif 000007
【図７】
0003610997.tif 000008
【図８】
0003610997.tif 000009
【図９】
0003610997.tif 000010