(57)【特許請求の範囲】
【請求項１】
線分の始点及び終点を指定するベクトルデータと、線分の太さを指定する太さデータとに基づいて、前記線分を前記指定された太さの太線として形成する際の前記太線のコーナ座標を算出する太線コーナ座標算出方式において、
前記ベクトルデータから求められる前記線分の傾きに基づいて前記線分の始点及び終点の少なくとも一方から前記指定された太さに相当する距離までＤＤＡ処理を実行して前記太線のコーナ座標を算出し、
前記ＤＤＡ処理は、第１軸方向の各座標値に対する第２軸方向の座標値を順次求めると共に、前記第１軸方向の座標値を更新する度に前記第１軸方向及び前記第２軸方向の累積値であって初期値をそれぞれ０とする累積値を２倍して１加算した値を次の累積値とする処理を実行し、前記第１軸方向の累積値と前記第２軸方向の累積値との加算値が前記太さに相当する距離の２乗の値を超えたときに終了する
ことを特徴とする太線コーナ座標算出方式。
【請求項２】
前記ＤＤＡ処理は、前記線分に沿った方向に実行し、
前記太線のコーナ座標は、前記ＤＤＡ処理で求められた座標値を座標変換して求める
ことを特徴とする請求項１記載の太線コーナ座標算出方式。
【請求項３】
線分の始点及び終点を指定するベクトルデータと、線分の太さを指定する太さデータとに基づいて、前記線分を前記指定された太さの太線として形成するための太線形成方式において、
前記ベクトルデータから求められる前記線分の傾きに基づいて前記線分の始点及び終点の少なくとも一方から前記指定された太さに相当する距離までＤＤＡ処理を実行して前記太線の端線を表すドット列を求める端線ＤＤＡ処理手段と、
この端線ＤＤＡ処理手段で求められた前記各端線の両端から前記線分に平行な線を形成して得られた輪郭線の内部を塗り潰すことにより太線を形成する手段と
を備え、
前記端線ＤＤＡ処理手段は、第１軸方向の各座標値に対する第２軸方向の座標値を順次求めると共に、前記第１軸方向の座標値を更新する度に前記第１軸方向及び前記第２軸方向の累積値であって初期値をそれぞれ０とする累積値を２倍して１加算した値を次の累積値とする処理を実行し、前記第１軸方向の累積値と前記第２軸方向の累積値との加算値が前記太さに相当する距離の２乗の値を超えたときに処理を終了するものである
ことを特徴とする太線形成方式。
【請求項４】
前記ＤＤＡ処理手段は、前記線分に沿った方向に前記指定された太さの１／２の距離のドット列を算出し、求められたドット列を前記太線の始点及び終点を中心として９０°回転させることにより、前記各端線を表すドット列を形成するものである
ことを特徴とする請求項３記載の太線形成方式。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、ラスタプロッタやプリンタ等で太線を形成する際の太線コーナ座標算出方式及び太線形成方式に関する。
【０００２】
【従来の技術】
ラスタプロッタで、例えば図６（ａ）に示すような太線を出力する場合、ラスタプロッタには、同図（ｂ）に示すように、線分の始終点座標（ｘS，ｙS），（ｘE，ｙE）と線分の太さＷの情報とが与えられるので、ラスタプロッタの内部では、これらのデータに基づいて、同図（ｃ）に示すように、太線のコーナ座標（ｘ1，ｙ1），（ｘ2，ｙ2），（ｘ3，ｙ3），（ｘ4，ｙ4）を算出し、これらのコーナ間を結ぶドット列をＤＤＡ（Digital Differential Analyzer）処理により形成したのち、内部を塗り潰すことにより太線を形成する処理が実行される。
【０００３】
コーナ座標（ｘ1，ｙ1），（ｘ2，ｙ2），（ｘ3，ｙ3），（ｘ4，ｙ4）を求めるには、図７（ａ）に示すように、まず始点（ｘS，ｙS）から線分ベクトルに沿って太さＷの１／２だけ離れた点Ｒの座標（ｘR，ｙR）を下記数１のように求める。
【０００４】
【数１】
0003913831.tif 000002
【０００５】
図７（ｃ）に示すコーナ座標（ｘ1，ｙ1），（ｘ2，ｙ2），（ｘ3，ｙ3），（ｘ4，ｙ4）は、同図（ｂ）に示すように、点Ｒの９０°回転と座標の平行移動とによって下記数２のように求められる。
【０００６】
【数２】
0003913831.tif 000003
【０００７】
【発明が解決しようとする課題】
しかし、上述した従来の方式では、ｘR，ｙRを求めるために、数１のように平方根演算及び除算が必要であり、処理時間がかかりすぎるという問題があった。
【０００８】
この発明は、このような問題点に鑑みなされたもので、高速処理が可能な太線コーナ座標算出方式及び太線形成方式を提供することを目的とする。
【０００９】
【課題を解決するための手段】
この発明に係る太線コーナ座標算出方式は、線分の始点及び終点を指定するベクトルデータと、線分の太さを指定する太さデータとに基づいて、前記線分を前記指定された太さの太線として形成する際の前記太線のコーナ座標を算出する太線コーナ座標算出方式において、前記ベクトルデータから求められる前記線分の傾きに基づいて前記線分の始点及び終点の少なくとも一方から前記指定された太さに相当する距離までＤＤＡ処理を実行して前記太線のコーナ座標を算出し、前記ＤＤＡ処理は、第１軸方向の各座標値に対する第２軸方向の座標値を順次求めると共に、前記第１軸方向の座標値を更新する度に前記第１軸方向及び前記第２軸方向の累積値であって初期値をそれぞれ０とする累積値を２倍して１加算した値を次の累積値とする処理を実行し、前記第１軸方向の累積値と前記第２軸方向の累積値との加算値が前記太さに相当する距離の２乗の値を超えたときに終了することを特徴とする。
【００１０】
この発明に係る太線形成処理方式は、線分の始点及び終点を指定するベクトルデータと、線分の太さを指定する太さデータとに基づいて、前記線分を前記指定された太さの太線として形成するための太線形成方式において、前記ベクトルデータから求められる前記線分の傾きに基づいて前記線分の始点及び終点の少なくとも一方から前記指定された太さに相当する距離までＤＤＡ処理を実行して前記太線の端線を表すドット列を求める端線ＤＤＡ処理手段と、この端線ＤＤＡ処理手段で求められた前記各端線の両端から前記線分に平行な線を形成して得られた輪郭線の内部を塗り潰すことにより太線を形成する手段とを備え、前記端線ＤＤＡ処理手段は、第１軸方向の各座標値に対する第２軸方向の座標値を順次求めると共に、前記第１軸方向の座標値を更新する度に前記第１軸方向及び前記第２軸方向の累積値であって初期値をそれぞれ０とする累積値を２倍して１加算した値を次の累積値とする処理を実行し、前記第１軸方向の累積値と前記第２軸方向の累積値との加算値が前記太さに相当する距離の２乗の値を超えたときに処理を終了するものであることを特徴とする。
【００１１】
この発明に係る太線コーナ座標算出方式によれば、指定されたベクトルデータから求められる線分の傾きに基づいて線分の始点及び終点の少なくとも一方から指定された太さに相当する距離までＤＤＡ処理を実行して太線のコーナ座標を算出するようにしているので、平方根演算や除算を含まず、高速処理が可能であると共に、ハードウェアの構成も簡素化することができる。
【００１２】
また、この発明に係る太線形成方式によれば、上述したＤＤＡ処理を実行してコーナ座標を算出するときに、太線の輪郭の一部をなす端線も同時にドット列として求めてしまうため、その分の処理時間も短縮されて、太線形成時間を従来よりも大幅に短縮することができる。
【００１３】
なお、上述した太線のコーナ座標や端線を求めるためにＤＤＡ処理を行う場合、終点座標が定まっていないため、太線の太さに相当する距離だけＤＤＡ処理が実行されたかどうかをＤＤＡ処理の終了条件とする必要がある。
この場合、距離計算には平方根演算が必要になるが、２乗距離を判定することで、平方根演算を省略することができる。また、ＤＤＡ処理が、第１軸方向の各座標値に対する第２軸方向の座標値を順次求めると共に、第１軸方向の座標値を更新する度に第１軸方向及び第２軸方向の累積値であって初期値をそれぞれ０とする累積値を２倍して１加算した値を次の累積値とする処理を実行し、第１軸方向の累積値と第２軸方向の累積値との加算値が太さに相当する距離の２乗の値を超えたときに終了するようにすれば、ＤＤＡ処理の各ステップでＤＤＡ実行の２乗距離を単純な累積加算だけで求められるので、更に処理速度を向上させることができる。
【００１４】
また、ＤＤＡ処理は、例えば線分に沿った方向に実行し、太線のコーナ座標や端線を示すドット列は、例えば始終点を中心として９０°回転処理させる座標変換によって求めることができる。
このため、ＤＤＡ処理は、始点及び終点の少なくとも一方から線分ベクトルに沿って実行すればよい。
【００１５】
【発明の実施の形態】
以下、図面を参照して、この発明の好ましい実施の形態を説明する。
一般に、ＤＤＡ演算をベクタ／ラスタ変換に適用する場合には、始点と終点とが与えられ、長軸の長さだけ演算を繰り返してドット列を求めていく。一方、太線のコーナ座標を算出する場合には、図７（ａ）のように、線分ベクトル方向にＤＤＡ処理を実行していくが、終点が与えられていないため、演算回数を予め決定しておくことはできない。そこで、ＤＤＡの終了条件は、始点（ｘS，ｙS）からの距離Ｄが所定値を超えたときとする。この所定値は、図６（ａ）から明らかなように、太さＷの１／２である。ＤＤＡ演算の途中における現在座標を（Ｘ，Ｙ）とすると、距離Ｄは、
【００１６】
【数３】
0003913831.tif 000004
【００１７】
となるので、平方根演算が必要になる。
ところで、距離指定によるＤＤＡでは終了条件が指定距離を超えたかどうかであるから、その比較演算は距離の２乗で行っても結果は同じである。そこで、現在座標（Ｘ，Ｙ）の始点（ｘS，ｙS）からの距離Ｄの２乗（２乗距離Ｓと呼ぶ）を用いれば、平方根演算を行う必要が無くなる。本発明では、この２乗距離ＳをＤＤＡ演算の各ステップ毎に計算して終了条件を判定するようにしてもよいが、この実施例では、更に処理を簡単化するため、この２乗距離Ｓを累積加算により求めるようにしている。
【００１８】
即ち、数３をＸ，Ｙでそれぞれ偏微分すると２Ｘ，２Ｙになるので、Ｘが増加すると２乗距離はそのときのＸ−ｘSの２倍増加することになる。Ｙについても同様である。このため、２乗距離ＳはＸ又はＹの増加に伴って各時点でのＸ又はＹ座標（始点からの相対値）の２倍を累積していくことにより求めることができる。また、ＤＤＡ演算は、ディジタル処理であるから、実際には微分ではなく、差分による解が必要になる。ｘ又はｙが１増加したときの２乗距離Ｓの増分を求めると次のようになる。
【００１９】
【数４】
0003913831.tif 000005
【００２０】
即ち、ＤＤＡ演算により座標値が１つだけ増加した場合は、そのときの座標値の２倍＋１を累積すれば、始点からの距離の２乗を求めることができる。この方法は、ＤＤＡ演算のように演算処理を１ステップずつ行う場合には、２倍演算と加算処理しか必要としないため、極めて有効な方法である。このようにして求めた２乗距離Ｓが（Ｗ／２）2を超えた時点で処理を終了すれば、Ｒ点の座標値が求められる。
【００２１】
いま、図１に示すように、始点座標が（０，０）、終点座標が（３７，２１）、太さが１５と指定された太線のコーナ座標を求めるため、線分ベクトルに沿ってＤＤＡ処理を実行しＲ点を求める。太さＷ＝１５であるから、判定の基準となる太さに相当する距離は、Ｗ／２＝７．５であるが、ディジタル処理であるから、距離＝７とし、２乗距離＝４９とする。
【００２２】
この例では、長軸がＸ軸であるから、Ｘ軸座標を１つずつ増加して、Ｙ軸方向の増分を決定していく。始点〜終点間のＸＹ軸距離をそれぞれΔＸ，ΔＹとすると、ブレゼンハムのＤＤＡアルゴリズムでは、誤差の初期値を−ΔＸとし、この誤差に２・ΔＹを累算して、０を超えたときにＹ軸座標を１つ増やすと同時に誤差から２・ΔＸを減算する。減算した誤差を修正誤差と呼ぶ。上記の例についてＤＤＡ演算を行うと次のようになる。
【００２３】
【表１】
0003913831.tif 000006
【００２４】
２乗距離Ｓが４９を超えるのは、（Ｘ，Ｙ）＝（７，４）のときであるから、Ｒ点の座標（ｘR，ｙR）＝（７，４）となる。ちなみに、数１に、Ｗ＝１５，（ｘS，ｙS）＝（０，０），（ｘE，ｙE）＝（３７，２１）を代入すると、（ｘR，ｙR）＝（６．５２，３．７０）となり、上記のＤＤＡ演算結果が正しいことが確認できる。この求められたＲ点の座標（ｘR，ｙR）＝（７，４）を数２に代入して座標変換を行えば、各コーナ座標（ｘ1，ｙ1）〜（ｘ4，ｙ4）が求められる。
【００２５】
図２は、以上の処理を実現するＤＤＡ処理回路の構成を示すブロック図である。  始点座標ｘS，ｙSは、現在Ｘレジスタ１及び現在Ｙレジスタ２にそれぞれ格納される。終点座標の始点座標からの相対値ΔＸ，ΔＹは、レジスタ３，４にそれぞれ格納される。また、太さＷから求められた（Ｗ／２）2の値は、レジスタ５に格納される。レジスタ３に格納されたΔＸから符号部と絶対値とが求められ、それぞれレジスタ６，７に格納される。また、レジスタ４に格納されたΔＹから符号部と絶対値とが求められ、それぞれレジスタ８，９に格納される。レジスタ７，９にそれぞれ格納されたΔＸ，ΔＹの絶対値は、ＤＤＡ演算部１０に与えられ、ここで、長軸、短軸、誤差、修正誤差等が求められ、ＤＤＡ演算が実行される。
【００２６】
ＤＤＡ演算の過程で、ＤＤＡ演算部１０からはＸ，Ｙをそれぞれ増分させるための増分パルス＋Ｘ，＋Ｙが出力される。増分パルス＋Ｘは、レジスタ６に格納された符号に基づき、ゲート回路１１，１２のいずれか一方を通過し、現在値Ｘを１つ増加させるパルス＋１又は１つ減少させるパルス−１として現在Ｘレジスタ１に与えられる。増分パルス＋Ｙも同様に、レジスタ８に格納された符号に基づき、ゲート回路１３，１４のいずれか一方を通過し、現在値Ｙを１つ増加させるパルス＋１又は１つ減少させるパルス−１として現在Ｙレジスタ２に与えられる。
【００２７】
また、増分パルス＋Ｘは、加算器１５を駆動し、加算器１５の出力は累積値を保持するレジスタ１６に供給され、レジスタ１６の出力は２倍＋１を演算する演算器１７に供給される。そして、レジスタ１６と演算器１７の出力が加算器１５の入力にそれぞれフィードバックして累積加算が行われるようになっている。増分パルス＋Ｙも同様に、加算器１８を駆動し、加算器１８の出力は累積値を保持するレジスタ１９に供給され、レジスタ１９の出力は２倍＋１を演算する演算器２０に供給される。そして、レジスタ１９と演算器２０の出力が加算器１８の入力にそれぞれフィードバックして累積加算が行われる。レジスタ１６，１９に保持されるＸ，Ｙの累積値は、加算器２１で加算され、現在までの２乗距離Ｓが求められる。この２乗距離Ｓとレジスタ５に格納された（Ｗ／２）2の値とが比較器２２で比較され、２乗距離Ｓがレジスタ５の値を超えた時点で比較出力ＣＰＭがアクティブになる。この比較出力ＣＭＰでＤ−フリップフロップ（ＦＦ）２３をリセットする。Ｄ−ＦＦ２３の出力はＤＤＡ演算部１０の演算開始及び指示するコントロール信号となる。
【００２８】
図３は、このＤＤＡ処理回路を使用した太線形成処理のフローチャートである。
図示しない、ＣＰＵは、まず始点座標を現在Ｘ，Ｙレジスタ１，２にロードする（Ｓ１）。次に、ΔＸ，ΔＹをレジスタ３，４にロードし（Ｓ２）、それぞれの符号と絶対値とを計算してレジスタ６〜９にセットする（Ｓ３）。次に、（Ｗ／２）2の値をレジスタ５にロードし（Ｓ４）、端線ＤＤＡ処理を開始する（Ｓ５）。即ち、図４に示すように、スタート信号ＳＴの立ち下がりで累積値を格納するレジスタ１６，１９がリセットされ、スタート信号ＳＴの立ち上がりでＤ−ＦＦ２３の出力Ｑが立ち上がり、ＤＤＡ演算部１０がＤＤＡ処理を開始する。比較出力ＣＭＰが立ち上がると、Ｄ−ＦＦ２３のＱ出力が立ち下がるので、ＤＤＡ処理が終了する。
【００２９】
現在Ｘ，Ｙレジスタ１，２には、ＤＤＡ処理の過程で得られた座標値（Ｘ，Ｙ）のデータ列が保持されており、これらデータ列に対して数２に示す座標変換処理を実行して各コーナの座標値（ｘ1，ｙ1）〜（ｘ4，ｙ4）を算出する（Ｓ６）。なお、このときデータ列に対して座標変換を行うので、図５（ａ）に示すように、太線の端線部分のデータ列は全て求まっていることになる。そして、（ｘ1，ｙ1）〜（ｘ3，ｙ3）間及び（ｘ2，ｙ2）〜（ｘ4，ｙ4）間をＤＤＡ処理することにより（Ｓ７，Ｓ８）、図５（ｂ）に示すように、太線の輪郭線が全て求まる。最後に図５（ｃ）のように、輪郭線の内部を塗り潰すことにより、太線が形成されることになる（Ｓ９）。
【００３０】
【発明の効果】
以上述べたように、この発明によれば、指定されたベクトルデータから求められる線分の傾きに基づいて線分の始点及び終点の少なくとも一方から指定された太さに相当する距離までＤＤＡ処理を実行して太線のコーナ座標を算出するようにしているので、平方根演算や除算を含まず、高速処理が可能であると共に、ハードウェアの構成も簡素化することができるという効果を奏する。
【図面の簡単な説明】
【図１】  この発明の一実施例に係る太線コーナ座標算出方式を説明するための図である。
【図２】  同方式に使用されるＤＤＡ処理回路のブロック図である。
【図３】  同回路を使用した太線形成処理の手順を示すフローチャートである。
【図４】  同回路のタイミングチャートである。
【図５】  同太線形成処理を説明するための図である。
【図６】  従来の太線コーナ座標の算出処理を説明するための図である。
【図７】  従来の太線コーナ座標の算出処理を説明するための図である。
【符号の説明】
１〜９，１６，１９…レジスタ、１０…ＤＤＡ演算部、１１〜１４…ゲート回路、１５，１８，２１…加算器、１７，２０…演算器、２２…比較器、２３…Ｄ−フリップフロップ。
【図１】
0003913831.tif 000007
【図２】
0003913831.tif 000008
【図３】
0003913831.tif 000009
【図４】
0003913831.tif 000010
【図５】
0003913831.tif 000011
【図６】
0003913831.tif 000012
【図７】
0003913831.tif 000013