(57)【特許請求の範囲】
【請求項１】
始点、通過点及び終点の３点で指定される円弧のデータから当該円弧を近似する複数の線分データを生成するための円弧補間処理方法において、
前記指定された３点のデータから前記円弧の中心点を算出する中心点算出ステップと、
前記３点のデータの少なくとも１つと前記算出された中心点とから前記円弧の半径に対応する値を算出して分割角を決定する分割角決定ステップと、
前記始点から前記通過点までのベクトルと前記通過点から前記終点までのベクトルとの外積を求め、その符号に基づいて前記分割角の回転方向を決定する回転方向決定ステップと、
前記円弧を前記決定された分割角毎に前記決定された回転方向に分割して線分データを順次生成すると共に、前記線分データの終点が前記円弧の終点を超えたときに前記線分データの生成を終了する線分データ生成ステップとを備え、
前記線分データ生成ステップは、前記線分データを生成する毎にその線分データの始点から前記円弧の終点へ延びるベクトルと前記線分データの終点から前記円弧の終点へ延びるベクトルとの内積を求め、その符号に基づいて前記線分データの生成を終了するステップである
ことを特徴とする円弧補間処理方法。
【請求項２】
前記分割角決定ステップは、前記３点のデータの少なくとも一つと前記中心点とから前記円弧の半径の２乗値を求め、この半径の２乗値に基づいて分割角を決定するステップである
ことを特徴とする請求項１記載の円弧補間処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、文字フォント等の曲線部を円弧データによって指定した場合の円弧補間処理方法に関する。
【０００２】
【従来の技術】
文字フォントデータの曲線部は、通常は２次ベジェ曲線や２次スプライン等によって指定されるが、より簡易で高速な方法として、曲線部を円弧データで指定する方法がある。この場合、円弧データは、始点、通過点及び終点で指定される。円弧データは、処理速度を高めるため通常はプロットする直前に線分データに分割される。分割された線分データは、例えば図８に示すように、実際の円弧に対して誤差を生じる。この誤差は、円弧の中心点から円弧の始点及び終点までの線分のなす角度をζとすると、
【０００３】
【数１】
誤差＝ｒ｛１−cos（ζ／２）｝
【０００４】
で表され、この誤差が所定の誤差ｅ以下となるように角度ζが選択される。この角度ζを分割角と呼ぶ。
【０００５】
従来、この分割角ζとその回転方向とを求めるため、次のような処理を行っていた。
即ち、図９に示すように、与えられた始点Ｐ1、通過点Ｐ2及び終点Ｐ3のデータから、円弧の中心点Ｐ0を求める。次に中心点Ｐ0と始点Ｐ1との距離を算出して円弧の半径ｒを求め、求められた半径ｒから分割角ζを求める。更に、中心点Ｐ0から始点Ｐ1、通過点Ｐ2及び終点Ｐ3にそれぞれ向かうベクトルとのなす角度θ1，θ2，θ3を求める。これらの角度θ1〜θ3から回転方向を決定し、分割角ζの符号を決定する。
【０００６】
【発明が解決しようとする課題】
しかし、上述した従来の円弧補間処理方法では、角度θ1〜θ3を算出する際に、アークタンジェント演算が必要になる。このアークタンジェント演算は、繰り返しが多いため、処理時間の増大を招くという問題がある。また、アークタンジェント演算をテーブルの参照によって行おうとしても、インデックスが０から無限大まで必要となるので、テーブルの作成も困難であるという問題がある。
【０００７】
この発明は、このような問題点に鑑みなされたもので、高速処理が可能な円弧補間処理方法を提供することを目的とする。
【０００８】
【課題を解決するための手段】
この発明に係る円弧補間処理方法は、始点、通過点及び終点の３点で指定される円弧のデータから当該円弧を近似する複数の線分データを生成するための円弧補間処理方法において、前記指定された３点のデータから前記円弧の中心点を算出する中心点算出ステップと、前記３点のデータの少なくとも１つと前記算出された中心点とから前記円弧の半径に対応する値を算出して分割角を決定する分割角決定ステップと、前記始点から前記通過点までのベクトルと前記通過点から前記終点までのベクトルとの外積を求め、その符号に基づいて前記分割角の回転方向を決定する回転方向決定ステップと、前記円弧を前記決定された分割角毎に前記決定された回転方向に分割して線分データを順次生成すると共に、前記線分データの終点が前記円弧の終点を超えたときに前記線分データの生成を終了する線分データ生成ステップとを備え、前記線分データ生成ステップは、線分データを生成する毎にその線分データの始点から円弧の終点へ延びるベクトルと線分データの終点から円弧の終点へ延びるベクトルとの内積を求め、その符号に基づいて線分データの生成を終了するステップであることを特徴とする。
【０００９】
この発明によれば、円弧のデータとして与えられた始点、通過点及び終点のデータのうち、始点から通過点までのベクトルと通過点から終点までのベクトルとの外積を求め、その符号に基づいて分割角の回転方向を決定するようにしているので、アークタンジェント演算を必要とせず、演算処理は単純な四則演算だけとなるので、処理速度が従来に比べて格段に高速になる。また、線分データを生成する毎にその線分データの始点から円弧の終点へ延びるベクトルと線分データの終点から円弧の終点へ延びるベクトルとの内積を求め、その符号に基づいて線分データの生成を終了するようにしているので、終了判定も単純な演算で行え、処理速度は更に向上する。
【００１０】
また、与えられた３点のデータの少なくとも一つと中心点とから円弧の半径の２乗値を求め、この半径の２乗値に基づいて分割角を決定するようにすると、平方根演算も不要となるので、処理速度は更に向上する。
【００１１】
【発明の実施の形態】
以下、図面を参照して、この発明の好ましい実施の形態を説明する。
図１は、この発明の実施例に係る円弧補間処理を実現するシステムの機能ブロック図である。
このシステムは、円弧補間処理部１、分割角決定テーブル２及び三角関数テーブルを備えて構成される。
【００１２】
上位システムから与えられた文字コードに基づいて、フォントテーブルから読み出されたフォントデータのうち、曲線の部分は、始点Ｐ1、通過点Ｐ2及び終点Ｐ3により特定される円弧データとなっており、これら３点のデータＰ1，Ｐ2，Ｐ3が円弧補間処理部１に供給されると、図２に示すような円弧補間処理が実行される。
【００１３】
この円弧補間処理は、与えられた３点のデータから中心座標Ｐ0を決定するステップ（Ｓ１）と、半径の２乗から分割角を決定するステップ（Ｓ２）と、回転方向を決定するステップ（Ｓ３）と、分割角毎に回転方向に沿って分割点列、即ち分割線分を求めるステップ（Ｓ４）と、線分分割を終了するための判定ステップ（Ｓ５）とから構成される。以下、各ステップについて説明する。
【００１４】
（１）中心座標Ｐ0の決定（Ｓ１）
図３に示すように、Ｐ0を中心とする円弧上に３点のデータＰ1，Ｐ2，Ｐ3が配置されているとして、中心点Ｐ0に対して円弧上の点Ｐ1と点対称の位置に第４の点Ｐ4を配置した場合、Ｐ1からＰ2へのベクトルＶ21と、Ｐ2からＰ4へのベクトルＶ42とのなす角度は９０°となり、同じくＰ1からＰ3へのベクトルＶ31と、Ｐ3からＰ4へのベクトルＶ43とのなす角度も９０°となる。従って、ベクトルＶ21，Ｖ42の内積とベクトルＶ31，Ｖ43の内積は共に０になる。即ち、Ｐ1，Ｐ2，Ｐ3，Ｐ4の座標をそれぞれ（ｘ1，ｙ1），（ｘ2，ｙ2），（ｘ3，ｙ3），（ｘ4，ｙ4）とすると、
【００１５】
【数２】
Ｖ21・Ｖ42
＝（ｘ2−Ｘ1）（ｘ4−ｘ2）＋（ｙ2−ｙ1）（ｙ4−ｙ2）
＝０
Ｖ31・Ｖ43
＝（ｘ3−Ｘ1）（ｘ4−ｘ3）＋（ｙ3−ｙ1）（ｙ4−ｙ3）
＝０
【００１６】
数２をｘ4及びｙ4について解くと、数３のようになる。
【００１７】
【数３】
0003913832.tif 000002
【００１８】
ここで変数Ｐ1，Ｐ2，Ｐ3を１６ビット精度とすると、数３のｘ4，ｙ4を求める式の分母及びｃ1，ｃ2を求める式は、３２ビット整数型で精度を維持することができる。Ｐ4は、１６ビット整数となる。ｘ4，ｙ4を求めるときの最終手順で乗算２回と、除算１回に浮動小数点演算を必要とする。数３より、円弧の中心座標Ｐ0＝（ｘ0，ｙ0）はＰ1，Ｐ4の中点として求められるが、切り捨て誤差を防ぐため、数４のように求められる。
【００１９】
【数４】
ｘ0＝（ｘ4＋ｘ1＋１）／２
ｙ0＝（ｙ4＋ｙ1＋１）／２
【００２０】
（２）分割角の決定（Ｓ２）
分割角ζは、数１に基づいて決定するのが理想的であるが、この場合、演算には高い処理能力が要求されるので、ここでは高速処理が可能な次のような手順で分割角を決定する。即ち、半径ｒの２乗値は、数５のように整数演算によって求められる。
【００２１】
【数５】
ｒ2＝（ｘ1−ｘ0）2＋（ｙ1−ｙ0）2
【００２２】
分割角決定テーブル２には、図４に示すような変換表が予め格納されており、数５で求められた半径の２乗値ｒ2をインデックスとして分割角決定テーブル２から分割角ζを決定する。ここでは誤差ｅを１３ドット程度に設定した。
この方式によれば、▲１▼半径算出のための平方根演算が不要であること、▲２▼逆コサイン変換が不要なこと、から処理時間を大幅に短縮することができる。
【００２３】
（３）回転方向の決定（Ｓ３）
円弧の回転方向は、図５に示すように、始点Ｐ1から通過点Ｐ2に延びるベクトルＶ21と、通過点Ｐ2から終点Ｐ3に延びるベクトルＶ32とのなす角度θが正であるか負であるかによって決定することができる。即ち、図５（ａ）のように、Ｖ21とＶ32とのなす角度θが正である場合には反時計回りであり、同図（ｂ）のように、Ｖ21とＶ32とのなす角度θが負である場合には時計回りである。２本のベクトルＶ21，Ｖ32の外積は、数６のように求められる。
【００２４】
【数６】
Ｖ21×Ｖ32
＝｜Ｖ21｜｜Ｖ32｜sinθ
＝（ｘ2−ｘ1）（ｙ3−ｙ2）−（ｙ2−ｙ1）（ｘ3−ｘ2）
【００２５】
この値の正負の符号をそのまま分割角ζの回転方向とする。この演算も整数処理のみで行える。
【００２６】
（４）線分への分割処理（Ｓ４）
円弧の中心点Ｐ0と符号付き分割角ζとが求まったら、図６に示すように、線分への分割処理を繰り返して、各分割点をＰd1，Ｐd2，…求めていく。これにより分割ベクトルＶd1，Ｖd2，…が求められる。いま、円弧の中心点Ｐ0から分割点Ｐdn-1，Ｐdnへ延びるベクトルをそれぞれＶrn-1，Ｖrnとすると、
【００２７】
【数７】
0003913832.tif 000003
【００２８】
で表せる。従って、ｎ番目の分割点Ｐdnの座標（ｘdn，ｙdn）は、次のように求められる。
【００２９】
【数８】
ｘdn＝（ｘdn-1−ｘ0）cosζ−（ｙdn-1−ｙ0）sinζ＋ｘ0
ｙdn＝（ｘdn-1−ｘ0）sinζ＋（ｙdn-1−ｙ0）cosζ＋ｙ0
【００３０】
このとき、sinζ及びcosζは、三角関数テーブル３を参照することにより求める。分割角としては０°から１８０°までを想定しておけば充分であるが、図４に示すような分割角決定テーブル２を用いた場合には、２°から１５°までの１４通りの配列を用意しておけば足りる。sinζ及びcosζは、線分分割時に一度求めておけば良く、数８の演算も単純であるから、高速処理が可能になる。
【００３１】
（５）分割終了判定（Ｓ５）
分割処理の終了は、分割点が円弧の終点Ｐ3を超えたかどうかにより判定する。
図７に示すように、分割点Ｐdn-1から終了点Ｐ3に延びるベクトルをＶ1とし、次の分割点Ｐdnから終了点Ｐ3に延びるベクトルをＶ2とすると、同図（ａ）のように、分割点Ｐdnが終了点Ｐ3の手前に存在する場合には、ベクトルＶ1とベクトルＶ2とのなす角度は９０°以下となるが、同図（ｂ）のように、分割点Ｐdnが終了点Ｐ3を超えた場合には、ベクトルＶ1とベクトルＶ2とのなす角度は９０°を超える。従って、ベクトルＶ１，Ｖ２の内積を求め、その符号が負になったことをもって分割点Pdnが終了点Ｐ3を超えたと判断することができる。即ち、
【００３２】
【数９】
Ｖ1・Ｖ2
＝（ｘ3−ｘdn-1）（ｘ3−ｘdn）＋（ｙ3−ｙdn-1）（ｙ3−ｙdn）≦０
【００３３】
を検出したら、分割線分Ｖdnは使用せずに、終点Ｐ3に至る線分Ｖ1を最終線分とする。
以上の処理により、円弧補間処理の速度を大幅に向上させることができる。
【００３４】
【発明の効果】
以上述べたように、この発明によれば、円弧のデータとして与えられた始点、通過点及び終点のデータのうち、始点から通過点までのベクトルと通過点から終点までのベクトルとの外積を求め、その符号に基づいて分割角の回転方向を決定するようにしているので、アークタンジェント演算を必要とせず、演算処理は四則演算だけとなるので、処理速度が従来に比べて格段に高速になるという効果を奏する。また、線分データを生成する毎にその線分データの始点から円弧の終点へ延びるベクトルと線分データの終点から円弧の終点へ延びるベクトルとの内積を求め、その符号に基づいて線分データの生成を終了するようにしているので、終了判定も単純な演算で行え、処理速度は更に向上するという効果を奏する。
【図面の簡単な説明】
【図１】  この発明の一実施例に係る円弧補間処理を実現するシステムの機能ブロック図である。
【図２】  同円弧補間処理のフローチャートである。
【図３】  同処理における円弧の中心点座標の算出手順を説明するための図である。
【図４】  同処理における分割角の決定手順に用いられる分割角決定テーブルの一例を示す図である。
【図５】  同処理における分割角の回転方向決定手順を説明するための図である。
【図６】  同処理における線分分割手順を説明するための図である。
【図７】  同処理における線分分割終了判定手順を説明するための図である。
【図８】  円弧の線分分割角度と誤差との関係を示す図である。
【図９】  従来の円弧補間処理方法を説明するための図である。
【符号の説明】
１…円弧補間処理部、２…分割角決定テーブル、３…三角関数テーブル。
【図１】
0003913832.tif 000004
【図３】
0003913832.tif 000005
【図２】
0003913832.tif 000006
【図４】
0003913832.tif 000007
【図５】
0003913832.tif 000008
【図６】
0003913832.tif 000009
【図７】
0003913832.tif 000010
【図８】
0003913832.tif 000011
【図９】
0003913832.tif 000012