(57)【要約】【課題】  前進差分法を利用して曲線の太線を描画するにあたり、単純な演算によって微小線分の接続点に隙間が生じない太線を高速に描画できる図形描画装置を提供する。【解決手段】  曲線の情報を入力し、線幅を有する太線の曲線の描画開始位置に関する初期パラメータを算出する前処理部１と、曲線の情報に基づいて描画対象の曲線を特定し、初期パラメータによる描画開始位置から当該曲線を微小線分毎に分割して各微小線分の端点の座標を算出する曲線分割部２と、曲線分割部２が算出した各微小線分の端点に基づいて微小線分間の接続点における法線を決定し、当該法線上にあって曲線の太線の輪郭線に位置する点を順次算出する接続法線決定部３と、接続法線決定部３が算出した曲線の太線の輪郭線に位置する各点に基づいて、曲線の太線の描画データを生成する太線生成部４とを備える。【選択図】        図１
2006338541.tif 000002
【特許請求の範囲】
【請求項１】
曲線の描画開始点、曲線の関数及び線幅を含む曲線の情報を入力し、前記線幅を有する太線の曲線の描画開始位置に関する初期パラメータを算出する前処理部と、
前記曲線の情報に基づいて描画対象の曲線を特定し、前記初期パラメータによる描画開始位置から当該曲線を微小線分毎に分割して各微小線分の端点の座標を算出する曲線分割部と、
前記曲線分割部が算出した各微小線分の端点に基づいて前記微小線分間の接続点における法線を決定し、当該法線上にあって前記曲線の太線の輪郭線に位置する点を順次算出する接続法線決定部と、
前記接続法線決定部が算出した前記曲線の太線の輪郭線に位置する各点に基づいて、前記曲線の太線の描画データを生成する太線生成部とを備えた図形描画装置。
【請求項２】
接続法線決定部は、基準の法線に対する傾きに応じて分類した法線パターンデータを保持し、前記法線パターンデータに規定される法線で前記微小線分の接続点における法線を近似することを特徴とする請求項１記載の図形描画装置。
【請求項３】
接続法線決定部は、連続する点における法線の傾きの変化を前進差分法により算出した法線の傾きと定数との大小関係で規定した判定条件データを保持し、前記判定条件データに規定される法線の傾きと定数との大小関係に基づいて、連続する微小線分の接続点における法線の傾きの変化を判定することを特徴とする請求項１又は請求項２記載の図形描画装置。
【請求項４】
太線生成部は、接続法線決定部が求めた曲線の太線の輪郭線に位置する各点を用いて、前記輪郭線を含む太線の一部となる四角形を規定し、前記四角形を前記曲線に沿って順次描画して前記曲線の太線の描画データを生成することを特徴とする請求項１から請求項３のうちのいずれか１項記載の図形描画装置。
【請求項５】
曲線の描画開始点、曲線の関数及び線幅を含む曲線の情報を入力し、前記線幅を有する太線の曲線の描画開始位置に関する初期パラメータを算出する前処理部、前記曲線の情報に基づいて描画対象の曲線を特定し、前記初期パラメータによる描画開始位置から当該曲線を微小線分毎に分割して各微小線分の端点の座標を算出する曲線分割部、前記曲線分割部が算出した各微小線分の端点に基づいて前記微小線分間の接続点における法線を決定し、当該法線上にあって前記曲線の太線の輪郭線に位置する点を順次算出する接続法線決定部、前記接続法線決定部が算出した前記曲線の太線の輪郭線に位置する各点に基づいて、前記曲線の太線の描画データを生成する太線生成部としてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、曲線を描画する図形描画装置及びこの機能をコンピュータに実現させるプログラムに関するものである。
【背景技術】
【０００２】
例えば、３次ベジェ曲線は、ＸＹ平面において４つの制御点（ｘ0，ｙ0）、（ｘ1，ｙ1）、（ｘ2，ｙ2）、（ｘ3，ｙ3）と、パラメータｔ（０≦ｔ≦１）とを用いてパラメータｔの３次式である下記式（１）、（２）で定義される。なお、下記式（１）、（２）において、ｔ＝０のときが開始点（ｘ0，ｙ0）、ｔ＝１のときが終了点（ｘ3，ｙ3）に対応する。
ｘ（ｔ）＝
ｘ0（１−ｔ）3＋３ｘ1（１−ｔ）2ｔ＋３ｘ2（１−ｔ）ｔ2＋ｘ3ｔ3  ・・（１）
ｙ（ｔ）＝
ｙ0（１−ｔ）3＋３ｙ1（１−ｔ）2ｔ＋３ｙ2（１−ｔ）ｔ2＋ｙ3ｔ3  ・・（２）
【０００３】
上記式（１）、（２）でパラメータｔを（０≦ｔ≦１）の範囲で徐々に変化させながら開始点から終了点まで順に点を描画していけばベジェ曲線の軌跡が得られる。しかし、上記式（１）及び上記式（２）に従って毎回計算を行うのは多大な計算量を必要とする。このため、ベジェ曲線を微小線分に分割して描画するのが一般的であり、例としては前進差分法がある（非特許文献１参照）。
【０００４】
前進差分法は、点（ｘ（ｔ），ｙ（ｔ））の座標を用いて、微小量δ＝１／ｎ（ｎは分割数）だけ進んだ点（ｘ（ｔ＋δ），ｙ（ｔ＋δ））の座標を順に求める方法である。上記式（１）で下記式（３）のようにおくと、Ｘ座標についての前進差分は、下記式（４）〜（６）のように表すことができる。
ｘ（ｔ）＝ａｔ3＋ｂｔ2＋ｃｔ＋ｄ      ・・・（３）
Δｘ（ｔ）＝ｘ（ｔ＋δ）−ｘ（ｔ）
＝３ａｔ2δ＋（３ａδ2＋２ｂδ）ｔ＋ａδ3＋ｂδ2＋ｃδ      ・・・（４）
Δ2ｘ（ｔ）＝Δｘ（ｔ＋δ）−Δｘ（ｔ）
＝６ａδ2ｔ＋６ａδ3＋２ｂδ2      ・・・（５）
Δ3ｘ（ｔ）＝Δ2ｘ（ｔ＋δ）−Δ2ｘ（ｔ）＝６ａδ3      ・・・（６）
【０００５】
また、Ｙ座標についても同様に前進差分を定めることができる。上記式（４）〜（６）を変形することにより、点（ｘ（ｔ），ｙ（ｔ））から微小量δだけ進んだ点（ｘ（ｔ＋δ），ｙ（ｔ＋δ））のＸ座標は下記式（７）〜（９）により求められる。
ｘ（ｔ＋δ）＝ｘ（ｔ）＋Δｘ（ｔ）      ・・・（７）
Δｘ（ｔ＋δ）＝Δｘ（ｔ）＋Δ2ｘ（ｔ）      ・・・（８）
Δ2ｘ（ｔ＋δ）＝Δ2ｘ（ｔ）＋Δ3ｘ（ｔ）      ・・・（９）
【０００６】
各項の初期値は、上記式（４）〜（５）でｔ＝０とすることにより、下記式（１０）、（１１）で表すことができる。
Δｘ（０）＝ａδ3＋ｂδ2＋ｃδ      ・・・（１０）
Δ2ｘ（０）＝６ａδ3＋２ｂδ2      ・・・（１１）
【０００７】
なお、Δ3ｘ（ｔ）は刻み幅δによって定まる定数項であり、パラメータｔの値には依存しない。前進差分法の利点は曲線上の点のＸ座標またはＹ座標のいずれについても上記式（７）〜（９）で示したように各３回の加算のみで計算できる点にある。
【０００８】
また、ベジェ曲線の描画において、指定された線幅Ｗでベジェ曲線を太線化したい場合がある。これを実現する方法としては、曲線を微小線分で近似した後、各微小線分を太線化するものがある。しかし、単純に各微小線分を太線化しただけでは、微小線分同士の接続点において隙間やオーバーラップが生じてしまう。
【０００９】
この不具合を解決する従来の技術としては、例えば特許文献１に開示される描画装置がある。この描画装置では、各微小線分間に発生する隙間を埋めるための図形を生成し、これにより隙間を塗りつぶす。また、特許文献２には、第１のベジェ曲線との距離Ｗを保つ第２のベジェ曲線を生成し、２つの曲線の内部を塗りつぶすことにより線幅Ｗを有するベジェ曲線の太線を描画する曲線形成装置が示されている。
【００１０】
【特許文献１】特開平６−１６８３３９号公報
【特許文献２】特開平１１−０１５９８７号公報
【非特許文献１】James D.Forey, Andries van Dam, Steven K.Feiner, John F.Hughes共著「コンピュータグラフィックス理論と実践」、オーム社、２００１年３月、ｐ５０９−５１２
【発明の開示】
【発明が解決しようとする課題】
【００１１】
特許文献１に開示される曲線の太線を描画する処理では、ベジェ曲線を微小線分に分割して描画する際に微小線分の接続点において生じる隙間を埋めるための図形を生成する必要があり、描画処理の度に多大な計算を必要とするという課題がある。また、特許文献２に開示される技術においても、ベジェ曲線の太線を描画する度に新たに第２のベジェ曲線を生成するための計算が必要であり、計算量が増大するという課題がある。このように、従来のベジェ曲線の太線描画技術では、多大な計算量を要することなく高速な描画を実行することが困難であった。
【００１２】
この発明は、上記のような課題を解決するためになされたもので、前進差分法を利用して曲線の太線を描画するにあたり、単純な演算によって微小線分の接続点に隙間が生じない太線を高速に描画できる図形描画装置及びこの機能をコンピュータに実現させるプログラムを得ることを目的とする。
【課題を解決するための手段】
【００１３】
この発明に係る図形描画装置は、曲線の描画開始点、曲線の関数及び線幅を含む曲線の情報を入力し、線幅を有する太線の曲線の描画開始位置に関する初期パラメータを算出する前処理部と、曲線の情報に基づいて描画対象の曲線を特定し、初期パラメータによる描画開始位置から当該曲線を微小線分毎に分割して各微小線分の端点の座標を算出する曲線分割部と、曲線分割部が算出した各微小線分の端点に基づいて微小線分間の接続点における法線を決定し、当該法線上にあって曲線の太線の輪郭線に位置する点を順次算出する接続法線決定部と、接続法線決定部が算出した曲線の太線の輪郭線に位置する各点に基づいて、曲線の太線の描画データを生成する太線生成部とを備えるものである。
【発明の効果】
【００１４】
この発明によれば、単純な演算で曲線の太線を高速に描画することができるという効果がある。また、曲線を微小線分に分割して描画する際に、微小線分の接続点の形状を予め用意した法線パターンで近似するので、法線ベクトルの計算を必要とせず高速に描画することができる。さらに、一辺を共有する四角形を連続して描画することで曲線の太線を生成することから、微小線分の接続点において隙間やオーバーラップが生じることもない。
【発明を実施するための最良の形態】
【００１５】
実施の形態１．
図１は、この発明の実施の形態１による図形描画装置の構成を示すブロック図である。実施の形態１による図形描画装置６は、前処理部１、曲線分割部２、接続法線決定部３及び太線生成部４から構成され、フレームバッファ５に保持したピクセルデータが適宜読み出されて表示される。
【００１６】
前処理部１は、電子データとして入力された例えばベジェ曲線の情報を用いて微小線分の生成に必要な初期パラメータを算出する。曲線分割部２では、前処理部１が求めた初期パラメータの値に基づいて順次曲線を微小線分に分割し、各微小線分の端点の座標等を算出する。接続法線決定部３は、曲線分割部２が算出した各微小線分について接続点における法線を算出する。太線生成部４では、接続法線決定部３が算出した接続法線に基づいて太線描画処理を実行する。フレームバッファ５には、図形描画装置６が生成した曲線のピクセルデータを保持する。
【００１７】
また、図形描画装置６の構成要素である前処理部１、曲線分割部２、接続法線決定部３及び太線生成部４は、本発明の趣旨に従う図形描画プログラムをコンピュータに読み込ませてその動作を制御することにより、当該コンピュータ上でソフトウエアとハードウエアが協働した具体的な手段として実現することもできる。このコンピュータには、通信機能を有し、上記図形描画プログラムを実行することができる携帯電話や携帯情報端末も含まれる。なお、コンピュータ自体の構成及びその基本的な機能については、当業者が当該技術分野の技術常識に基づいて容易に認識できるものであり、本発明の本質に直接関わるものでないので詳細な記載を省略する。
【００１８】
図２は、この発明によるベジェ曲線の太線描画処理を説明するための図である。ここで、自装置６が搭載されたコンピュータのＣＰＵから入力されたベジェ曲線の情報として、制御点（図中の破線で結んだ各点）の座標（ｘ0，ｙ0）〜（ｘ3，ｙ3）、線幅Ｗが設定されたものとする。また、以降の説明では、図２中に実線で示した線幅０の曲線を骨格線と呼び、図２中に太線で示した骨格線からの距離がＷ／２となる点の軌跡を外形線（太線の輪郭線）と呼ぶこととする。
【００１９】
なお、骨格線上の点（図中に黒丸の記号で示した点）の座標は、上記式（１）、（２）で与えられる。外形線上の点（図中に白丸の記号で示した点）の座標Ｐ（ｔ）、Ｑ（ｔ）は、各点の座標を示しており、Ｐ（ｔ）に関しては（Ｘ1（ｔ），Ｙ1（ｔ））、Ｑ（ｔ）に関しては（Ｘ2（ｔ），Ｙ2（ｔ））と表記する。
【００２０】
次に動作について説明する。
図形描画装置６は、ＣＰＵから曲線の情報として４つの制御点の座標、線幅及び描画色等の情報が設定され、起動命令を受けることにより動作を開始する。起動命令を受けると、前処理部１が起動して微小線分の生成に必要な初期パラメータを算出する。具体的に説明すると、上記式（６）、（１０）、（１１）の関係を用いて、前進差分法の初期パラメータとしてΔｘ（０）、Δ2ｘ（０）、Δ3ｘ（０）を計算する。
【００２１】
また、前処理部１は、上記式（７）〜（９）のパラメータｔによる１階微分ｘ’（ｔ）の値も前進差分法により求める。これらの値は、接続法線決定部３による判定条件として利用される。ここで、上記式（３）〜（５）よりｘ’（ｔ）の前進差分を下記式（１２）〜（１４）に従って算出する。
ｘ’（ｔ）＝３ａｔ2＋２ｂｔ＋ｃ      ・・・（１２）
Δｘ’（ｔ）＝ｘ’（ｔ＋δ）−ｘ’（ｔ）
＝６ａδｔ＋（３ａδ2＋２ｂδ）      ・・・（１３）
Δ2ｘ’（ｔ）＝Δｘ’（ｔ＋δ）−Δｘ’（ｔ）＝６ａδ2      ・・・（１４）
【００２２】
各項の初期値は、上記式（１２）〜（１４）でｔ＝０とすることにより下記式（１５）、（１６）として求めることができる。なお、Δ2ｘ’（ｔ）はパラメータｔに依存しない定数である。
ｘ’（０）＝ｃ      ・・・（１５）
Δｘ’（０）＝３ａδ2＋２ｂδ      ・・・（１６）
【００２３】
前処理部１は、上記式（１４）〜（１６）の計算を行うことにより、前進差分法の初期パラメータを求める。なお、初期パラメータの計算は１度だけ行えばよい。また、前処理部１は、開始点（ｘ0，ｙ0）における法線上にあって、開始点からの距離がＷ／２となる点Ｐ（０）、Ｑ（０）の座標も求める。
【００２４】
曲線分割部２は、前処理部１が算出した初期パラメータを用いて、上記式（７）〜（９）による各演算を行い、ｔ＝ｔ＋δにおける骨格線上の点（ｘ（ｔ＋δ）、ｙ（ｔ＋δ））の座標を算出する。また、上記式（７）〜（９）のパラメータｔによる１階微分の値を求めるために下記式（１７）、（１８）による計算も行う。
ｘ’（ｔ＋δ）＝ｘ’（ｔ）＋Δｘ’（ｔ）      ・・・（１７）
Δｘ’（ｔ＋δ）＝Δｘ’（ｔ）＋Δ2ｘ’（ｔ）      ・・・（１８）
【００２５】
さらに、ｙ’（ｔ＋δ）、Δｙ’（ｔ＋δ）についても同様の計算により求める。このようにして、曲線分割部２は、上記式（７）〜（９）による加算をＸ座標とＹ座標のそれぞれについて３回の計６回、上記式（１７）、（１８）による加算をＸ座標とＹ座標のそれぞれについて２回の計４回、併せて合計１０回の加算を行う。このようにして、曲線分割部２は、前処理部１が求めた初期パラメータの値に基づいて微少量δだけ順次進んだ曲線の微小線分の各端点の座標を算出する。
【００２６】
接続法線決定部３は、曲線分割部２が算出した曲線上の点（図２中で黒丸記号で示した点）における法線上にあって、骨格線からの距離がＷ／２だけ離れた点（図２中で白丸記号で示した点）の座標を生成する。
【００２７】
太線生成部４では、接続法線決定部３で決定された各点の座標を元に太線を生成する。太線生成には２通りの方法がある。第１の方法では、随時パラメータｔ（０≦ｔ≦１−δ）の値に応じて、図２に示す点Ｐ（ｔ）、Ｑ（ｔ）、Ｐ（ｔ＋δ）、Ｑ（ｔ＋δ）の４点を結んで成る四角形を輪郭として特定し、この四角形の輪郭内の画素にベジェ曲線の情報で指定された描画色を設定して描画する。なお、この四角形は曲線上で直前に描画した四角形と一辺を共有する形で連続して描画する。
【００２８】
第２の方法は、図２に示す外形線を描画した後、ＣＰＵによりベジェ曲線の情報で指定された描画色により外形線内側の閉領域を塗りつぶすものである。いずれの方法でも微小線分の接続点において隙間やオーバーラップが生じることはない。しかし、第１の方法では、四角形の頂点座標の算出と四角形の描画処理とを並列処理することも可能であり、より効率的な描画を行うことができる。
【００２９】
次に実施の形態１による曲線の太線描画処理の詳細について説明する。
図３は、実施の形態１の図形描画装置による太線描画処理の流れを示すフローチャートであり、この図に沿って説明する。
先ず、前処理部１は、上述したように、パラメータｔを０とした後、開始点（ｘ0，ｙ0）における法線上にあって、開始点からの距離がＷ／２となる点Ｐ（０）、Ｑ（０）の座標を求める（ステップＳＴ１）。次に、曲線分割部２は、上述した関係式に従って、微少量δごとの微小線分について、前進差分法によりその骨格線上の点（ｘ（ｔ＋δ），ｙ（ｔ＋δ））の座標をそれぞれ求める（ステップＳＴ２）。
【００３０】
続いて、接続法線決定部３は、曲線分割部２によりそれぞれ求められた骨格線上の点（ｘ（ｔ＋δ），ｙ（ｔ＋δ））における法線（骨格線の微小線分に対する紙面に平行な法線）上にあって、点（ｘ（ｔ＋δ），ｙ（ｔ＋δ））からの距離がＷ／２となる点Ｐ（ｔ＋δ）及び点Ｑ（ｔ＋δ）の座標を求める（ステップＳＴ３）。
【００３１】
次に、太線生成部４は、点Ｐ（ｔ）、Ｑ（ｔ）、Ｑ（ｔ＋δ）、Ｐ（ｔ＋δ）から成る四角形を描画する（ステップＳＴ４）。このあと、太線生成部４は、パラメータｔの値から骨格線上の点（ｘ（ｔ＋δ）、ｙ（ｔ＋δ））が曲線の終了点（ｘ3、ｙ3）に達したか否かを判定する（ステップＳＴ５）。このとき、ｔ＝１−δならば描画処理を終了する。それ以外の時はｔ＝ｔ＋δとして、ステップＳＴ２の処理に戻る（ステップＳＴ６）。このようにして、次の微小線分について再びステップＳＴ２からステップＳＴ５までの処理を行う。
【００３２】
上記太線描画処理において、外形線上の点の座標は骨格線を構成する各点における法線上にあって、元の曲線からの距離がＷ／２となる点の軌跡となる。即ち、骨格線上の点を（ｘ（ｔ），ｙ（ｔ））、骨格線からの距離がＷ／２の点の軌跡を（Ｘ（ｔ），Ｙ（ｔ））とおくと、法線ベクトルの計算を行うことにより、外形線上の点（Ｘ（ｔ），Ｙ（ｔ））は、下記式（１９）で計算することができる。
【数１】
2006338541.tif 000003
【００３３】
しかしながら、上記式（１９）の計算には、平方根の演算及び乗算、除算が含まれており、骨格線上の点において毎回この計算を行うと計算量が膨大となる。
【００３４】
そこで、接続法線決定部３は、骨格線上の各点から外形線上の点を算出するにあたり、法線ベクトルの計算を行わず、予め用意しておいた法線パターンから実際の傾きに最も近い法線を近似することにより外形線上の点の座標を求める。なお、法線パターンは、図形描画装置６を具現化するコンピュータにメモリに電子情報として格納しておき、接続法線決定部３により適宜読み出されて外形線上の点の座標計算に用いられる。
【００３５】
図４は、法線パターンの一例を示す図である。図中に示す円の中心の黒丸印の点が骨格線上の点に相当し、白丸印の点が外形線上の点に相当する。なお、ここでは、Ｘ軸の正の方向を右向き、Ｙ軸の正の方向を下向きと仮定している。図４に示すように、外形線上の点（ｘ＋Ｗ／２，ｙ）から時計回りに０°、３０°、４５°、６０°、９０°、１２０°、１３５°、１５０°の８通りの傾きを持つ法線パターンの例を示している。
【００３６】
また、図５は、図４に示す法線パターンにおける法線の傾きに関連付けて外形線上の対応する点の座標をまとめたテーブルデータの内容を示す図である。図５に示した（√２Ｗ）及び（√３Ｗ）の値は、線幅Ｗにのみ依存する値であり、毎回計算を行う必要はなく、ベジェ曲線の情報として線幅Ｗを設定した際に前処理で最初に１度だけ計算しておけばよい。
【００３７】
このテーブルデータも、図形描画装置６を具現化するコンピュータにメモリに電子情報として格納しておき、接続法線決定部３により適宜読み出されて外形線上の点の座標計算に用いられる。これらの既設定の電子情報を用いることにより、外形線上の点の座標計算は、加減算とシフト演算のみで行うことができる。
【００３８】
さらに、前処理部１は、開始点からの距離がＷ／２となる点Ｐ（０）、Ｑ（０）の座標も図５のテーブルデータを利用することにより簡易な計算で求めることができる。また、法線パターン数を、図４に示した８通りからさらに増やせば、さらに精度の良い近似法線を得ることができる。実際にどの程度の法線パターン数を用意するかは、本発明の図形描画装置６を適用するシステムの要求性能に合わせて設定されることが望ましい。
【００３９】
次に、図４中の法線パターンから近似法線を決定する判定条件として法線の傾きを利用する方法について示す。先ず、骨格線上の点（ｘ（ｔ＋δ），ｙ（ｔ＋δ））における法線の傾きは、下記式（２０）で表すことができる。
ｎ＝−（ｘ’（ｔ＋δ）／ｙ’（ｔ＋δ））      ・・・（２０）
【００４０】
上記式（２０）の分子と分母の値は、曲線分割部２で前進差分法により求めた値を利用できる。上記式（２０）から正確な法線の傾きを算出するためには除算が必要となるが、本発明では上記式（２０）の分子と分母を比較することにより、実際の法線の傾きの範囲を定め、これに基づき近似法線を決定する。
【００４１】
図６は、微小線分ごとの近似法線を決定するための判定条件を示す図であり、骨格線上の点におけるｘ（ｔ＋δ）、ｙ（ｔ＋δ）のパラメータｔについての１階微分ｘ’（ｔ＋δ）、ｙ’（ｔ＋δ）の比率の絶対値が２m（ｍは整数）倍だけ異なる値となる箇所を、法線の傾きを変えるための閾値とした判定を行うものである。なお、ｎは、上記式（２０）で求められる値である。上記判定条件を用いると、上記式（２０）の除算が不要となり、上記式（２０）の分子及び分母の値を適宜シフトした値同士を比較することにより容易に判定を行うことができる。
【００４２】
図６において、直前の法線の傾きとは、骨格線上の点（ｘ（ｔ）、ｙ（ｔ））における法線の傾きであり、この値に応じて骨格線上の次の微小線分の端点（ｘ（ｔ＋δ）、ｙ（ｔ＋δ））における法線の傾き（次の法線の傾き）を変化させる。例えば、直前の接続点における法線の傾きが３０°であったとき、次の接続点におけるｎの値が、正の値であって判定条件｜ｎ｜＞１／２を満たす場合、次の接続点における法線の傾きは４５°となる。
【００４３】
このとき、本発明では、上記式（２０）に従ってｎの値を正確に算出して判定条件を満たすか否かを判定するのではなく、上記式（２０）の分子と分母の値からｎの正負を認識し、判定条件｜ｎ｜＞１／２を考える場合、２｜ｘ’（ｔ＋δ）｜＞｜ｙ’（ｔ＋δ）｜のようにして上記式（２０）の分子と分母の大小比較により判定処理を実行する。
【００４４】
なお、図６に示す判定条件は、直前の法線の傾きが０°又は９０°のとき、ｘ’（ｔ＋δ）、ｙ’（ｔ＋δ）の符号を考慮して法線の回転方向（直前の微小線分における端点の法線に対する次の微小線分における端点の法線を傾かせる方向）を定める。
【００４５】
つまり、図中の（※１）は、ｘ’（ｔ＋δ）、ｙ’（ｔ＋δ）が互いに異符号であるときにおける次の法線の傾きであり、（※２）は、ｘ’（ｔ＋δ）、ｙ’（ｔ＋δ）が互いに同符号であるときにおける次の法線の傾きである。なお、それ以外の場合には、直前までの法線の回転方向に応じていずれかの判定式に従って判定を行う。図６では、回転方向として時計回りの向きを正として示している。
【００４６】
このように、上記判定条件を用いると、上記式（２０）の分子又は分母の値の整数倍同士を比較するだけの単純な処理で接続点の形状を決定することができる。また、図６に示す判定条件は一例であり、法線の判定条件として他の条件を適用することも可能である。なお、このような判定条件データも、図形描画装置６を具現化するコンピュータにメモリに電子情報として格納しておき、接続法線決定部３により適宜読み出されて外形線上の点の座標計算に用いられる。
【００４７】
図７は、図４から図６までに示したデータを利用する接続法線の決定処理を示すフローチャートである。先ず、接続法線決定部３は、曲線分割部２が求めた微小線分ごとのｘ’（ｔ＋δ）、ｙ’（ｔ＋δ）に関する電子データを入力し、これらを用いて図６の判定条件により判定を行う（ステップＳＴ７）。次に、接続法線決定部３は、ｘ’（ｔ＋δ）、ｙ’（ｔ＋δ）が図６の判定条件にあてはまるか否かを判定する（ステップＳＴ８）。
【００４８】
このとき、ｘ’（ｔ＋δ）、ｙ’（ｔ＋δ）が、図６の判定条件にあてはまる場合、法線の傾きを図６に従って更新する（ステップＳＴ９）。ステップＳＴ６において法線の傾きを求めると、接続法線決定部３は、図５のテーブルデータの内容に従って外形線上の点の座標を求める（ステップＳＴ１０）。
【００４９】
一方、ｘ’（ｔ＋δ）、ｙ’（ｔ＋δ）が、図６に示すいずれの判定条件に当てはまらない場合、接続法線決定部３は、直前の法線の傾きと次の法線の傾きが平行になるように決定する。つまり、骨格線に沿って法線が平行移動させた形になるように、骨格線上の点の差分項を用いて、ｔ＝ｔ＋δにおける外形線上の点の座標を、Ｐ（ｔ＋δ）に関しては（Ｘ1（ｔ）＋Δｘ（ｔ），Ｙ1（ｔ）＋Δｙ（ｔ））とし、Ｑ（ｔ＋δ）に関しては（Ｘ2（ｔ）＋Δｘ（ｔ），Ｙ2（ｔ）＋Δｙ（ｔ））となるように定める（ステップＳＴ１１）。このように決定された接続法線に関する電子情報は、接続法線決定部３から太線生成部４に出力される。
【００５０】
図８は、本実施の形態１の図形描画装置によるベジェ曲線の線幅Ｗを有する太線の描画例であり、法線の傾きが変化する位置を太線の破線で示している。図８では、開始点（ｘ0，ｙ0）における法線の傾きは０°であり、これに続いて、３０°→４５°→６０°→９０°→１２０°→１３５°→１５０°と順に変化する様子を示している。
【００５１】
例えば、０°→３０°の破線が付された箇所までは、各微小線分の端点を通る法線が、それぞれ平行であり、これら法線に図４中の０°に相当する傾きを設定している。また、０°→３０°の破線が付された箇所から３０°→４５°の破線が付された箇所までは、各微小線分の端点を通る法線が、図４中の０°を基準に３０°回転した傾きがそれぞれ設定されている。以下同様に、図４中の０°を基準に４５°、６０°、９０°、１２０°、１３５°、１５０°が順に設定される。
【００５２】
図示の例において、直前の法線の傾きが４５°のときには、回転方向が正であるため、接続法線決定部３は、図６より｜ｎ｜＞２の判定条件にあてはまるか否かを判定する。実際には、｜ｘ’（ｔ＋δ）｜＞２｜ｙ’（ｔ＋δ）｜となるか否かを判定する。この判定条件を満たせば法線の傾きを図６に示す判定条件データに従って更新し、外形線上の点の座標を図５のテーブルデータの内容から求める。
【００５３】
また、判定条件を満たさない場合は、次の法線の傾きを直前の法線の傾きと同じ４５°のままとして、外形線上の点の座標は、骨格線上の点の差分項を用いて算出する。この方法を用いると、前進差分法の分割数が少ない場合でも、外形線の形状が比較的滑らかな曲線の太線を得ることが可能である。
【００５４】
図９は、開始点（ｘ0，ｙ0）と終了点（ｘ3，ｙ3）とを結ぶ直線を対称線とした場合に残りの２つの制御点（ｘ1，ｙ1）、（ｘ2，ｙ2）が当該対称線を境に対向する側に位置するベジェ曲線の例である。このようなベジェ曲線の線幅Ｗを有する太線を描画する場合、図中の点Ｏにおいて接続点における法線の傾きの変化方向が時計回りから反時計回りに変化するため、近似法線を決定する際の判定条件が複雑となる。
【００５５】
そこで、本実施の形態１では、図９のような曲線の場合、前処理部１が、点Ｏで予め曲線を２分割した後、上述した一連の描画処理を行うことで同様に扱うことができる。
【００５６】
以上のように、この実施の形態１では、ベジェ曲線を微小線分に分割して描画する際に、微小線分の接続点の形状を予め計算しておいた法線パターンで近似するので、法線ベクトルの計算が不要であり、計算量を大きく削減することができる。また、法線パターンから近似法線を決定するための判定条件として、前進差分法により求めた法線の傾きを利用するので、近似法線の判定も加減算とシフト演算という簡単な演算のみで行うことが可能である。従って、本実施の形態１による図形描画装置６のハードウェア化を行う場合でも回路規模を非常に小さく抑えることができる。
【００５７】
なお、上記実施の形態１では、３次ベジェ曲線の太線を描画する例を示したが、ベジェ曲線に限らずスプライン曲線など他の曲線であっても、前進差分法を利用することにより同様の効果を得ることができる。
【００５８】
また、上記実施の形態１では、前進差分法を利用してベジェ曲線の太線を描画する例を示したが、ベジェ曲線を再帰的に分割して描画する構成にしてもよい。この場合、上記実施の形態１で示した図１の構成で実現することができるが、曲線分割部２が、元のベジェ曲線の再帰的分割を行うことにより骨格線上の点の座標を求める。また、接続法線決定部３では、接続点を共有する各微小線分の傾きの差を法線パターン選択のための判定条件として予め保持しておき、これを適宜利用することにより近似法線を決定する。
【図面の簡単な説明】
【００５９】
【図１】この発明の実施の形態１による図形描画装置の構成を示すブロック図である。
【図２】ベジェ曲線の太線描画処理を説明するための図である。
【図３】実施の形態１による太線描画処理の流れを示すフローチャートである。
【図４】法線パターンの一例を示す図である。
【図５】法線の傾きと外形線上の点の座標をまとめたテーブルデータの内容を示す図である。
【図６】微小線分ごとの近似法線を決定するための判定条件を示す図である。
【図７】接続法線の決定処理を示すフローチャートである。
【図８】ベジェ曲線の太線描画の一例を示す図である。
【図９】ベジェ曲線の太線描画の他の例を示す図である。
【符号の説明】
【００６０】
１  前処理部、２  曲線分割部、３  接続法線決定部、４  太線生成部、５  フレームバッファ、６  図形描画装置。
【図１】
2006338541.tif 000004
【図２】
2006338541.tif 000005
【図３】
2006338541.tif 000006
【図４】
2006338541.tif 000007
【図５】
2006338541.tif 000008
【図６】
2006338541.tif 000009
【図７】
2006338541.tif 000010
【図８】
2006338541.tif 000011
【図９】
2006338541.tif 000012