説明

曲線描出方法および装置

【目的】3次ベジェ曲線で表現された曲線データを比較的簡単な演算で補間近似して直線分列を得て、しかも誤差を的確に管理する。
【構成】標準形変換部12は、与えられたベジェ曲線データを標準形として最大距離算出部13に与える。最大距離算出部13はベースラインからの距離の最大値を求める。トレランス規定部15は近似誤差のトレランスを保持する。比較部14は、最大距離とトレランスとを比較する。分割点決定/ベースライン出力部16は、前記最大距離が前記トレランスを超えているときは、前記最大距離が得られたベジェ曲線上の点を分割点として分割処理部17に与え、前記最大距離が前記トレランス以下であるときは、そのときのベースラインに相当する直線分を近似直線分として出力処理部18に与える。分割処理部17はベジェ曲線を2分割して標準形変換部12に与える。

【発明の詳細な説明】
【0001】
【産業上の利用分野】本発明は、文字、図形のような曲線を含む情報を、例えばプロッタ、プリンタ、工作機械またはディスプレイのような出力装置を用いて出力するコンピュータ応用システムに係り、特に3次ベジェ曲線で表現されたアウトラインフォントまたはスプライン曲線のような曲線データを直線分列で補間近似して出力装置で描画出力させるのに好適な曲線描出方法および装置に関する。
【0002】
【従来の技術】CAD(computer-aided design)システムは、自由曲線、すなわちスプライン曲線を作成するための機能を備えている。CADシステムでは、このようなスプライン曲線を含む図形データを、種々の大きさでディスプレイに表示するだけでなく、プリンタおよびプロッタ等により種々の大きさで出力したり、この図形データに従って工作機械を作動させて材料を種々の大きさで加工したりする。また、ワードプロセシングシステムおよびDTP(desktop publishing)システムには、種々の字体の文字をアウトラインフォントを用いて種々の大きさで表現する機能を備えているものも少なくない。このようなアウトラインフォントにも多くの場合実質的にCADシステムにおけるスプライン曲線と同等の曲線が含まれる。上述のようなスプライン曲線およびそれと同等の曲線を表現する場合、近年では、ベジェ曲線特に3次ベジェ曲線が用いられることが多い。
【0003】このような3次ベジェ曲線として表現された曲線を、プロッタまたは工作機械のような出力装置で出力する場合は、3次ベジェ曲線を多数の直線分列で補間近似して描出することになる。また、このような3次ベジェ曲線として表現された曲線を、ディスプレイ、プリンタ、または、ラスタプロッタのような出力装置で出力する場合は、3次ベジェ曲線を多数の直線分列で補間近似し、さらにラスタ展開して描出することになる。ここで、ベジェ曲線および従来のシステムにおけるベジェ曲線の補間近似について説明する。ベジェ曲線とは、始点と終点の座標、および始点の接線ベクトルと終点の接線ベクトルを指定する曲線表現の一つである。例えば2次ベジェ曲線は数1のようにパラメータtについての2次式で表現される。
【0004】
【数1】
P(t) =(1−t)20 +2(1−t)tP1 +t22
【0005】ここで、0≦t≦1であり、P(t) 、P0 、P1 およびP2 は位置ベクトルを表している。数1の2次ベジェ曲線は、パラメータtを0から1まで変化させたときの軌跡として図23に示されるように、3個の制御点P0 、P1 およびP2 で定義される。また、3次ベジェ曲線は、数2のようにパラメータtについての3次式で表現され、パラメータtを0から1まで変化させたときの軌跡として図24に示されるように、4個の制御点P0 、P1 、P2 およびP3 で定義される。
【0006】
【数2】


【0007】ここで、0≦t≦1であり、P(t) 、P0 、P1 、P2 およびP3 は位置ベクトルを表している。図23からもわかるように2次ベジェ曲線では、始点の接線ベクトルと終点の接線ベクトルの大きさが一意的に決定されてしまうので、曲線表現の自由度がなく、上述のようなスプライン曲線等の表現に使用されることは少ない。これに対して、3次ベジェ曲線では、始終点ベクトルの大きさについてある程度の自由度があり、上述のようなスプライン曲線等の表現に広く使用されている。一般にn次ベジェ曲線は数3で表される。
【0008】
【数3】


【0009】ベジェ曲線は始点と終点の座標値および始点の接線と終点の接線を与えて多項式で定義しているので、直線との結合やベジェ曲線同士を連続的に結合することができるので多く利用されている。数3より数4が得られる。
【0010】
【数4】
dP(t) /dt=−n(1−t)P0 +Σ ni (1−t)n-i i i
【0011】また、数3および数4より数5が得られる。
【0012】
【数5】P(0) =P0P(1) =PnP′(0) =n(P1 −P0
P′(1) =n(Pn −Pn-1
【0013】数5により、始点がP0 、終点がPn 、始点の接線方向がP1 −P0 、終点の接線方向がPn −Pn-1 となることを確認することができる。ベジェ曲線は、アフィン変換に対して不変であるという特徴を持っている。このことは係数の和が1になることによって確認することができる。この結果、曲線を回転させ、あるいは平行移動するにはベジェ曲線を定義している制御点について回転、あるいは平行移動をすればよい。この他にもベジェ曲線には様々な特徴がある。
【0014】上述したように、3次ベジェ曲線はスプライン曲線等の表現に多用されるが、数2のような3次ベジェ曲線を多数の直線分列で補間近似するためには、従来次の(a) または(b) のような操作を行っていた。
(a) パラメータtの値を予め固定的に、例えばt= 0,0.01,0.02,…,0.99,1として、定めておき、これらのtの値を数2に逐次代入して、それぞれのtの値に対応する3次ベジェ曲線P(t) 上の点を求め、これら各点を直線で結ぶ。
(b) ベジェ多角形の周長、すなわち図24に示される、4個の制御点P0 、P1 、P2 およびP3 を結ぶP0 −P1 −P2 −P3 の長さLを求め、それに基づいてtの値を固定的に、t= 0,1/L ,2/L ,…,(L-1)/L ,1として、定めて、これらのtの値を数2に逐次代入して、それぞれのtの値に対応する3次ベジェ曲線P(t) 上の点を求め、これら各点を直線で結ぶ。
【0015】
【発明が解決しようとする課題】上述したように従来のシステムにおいては、3次ベジェ曲線の補間近似による直線分列への展開に際して、パラメータtの値に固定値または単にP0 −P1 −P2 −P3 の長さLに基づいて固定的に求めた値を代入していた。すなわち、3次ベジェ曲線の補間近似による直線分列への変換に際し、(a) の方法では、tの値が固定されてしまい且つこのtの値は求められる直線分とベジェ曲線との誤差に直接的には対応していないため、直線分とベジェ曲線との誤差を少なくするにはtの値をむやみに細かくとらねばならず、簡単な(例えば直線に近いあるいは全長が非常に短い等)曲線に対しても必要以上に多数の点を求めることになり、非常に効率の悪い演算を行うことになる。もちろん、tの値を粗くとれば演算は簡単になるが複雑な(すなわち曲率が大きくまたは全長が長い等)曲線に対して誤差が大きくなる。また、(b) の方法では、tの値をP0 −P1 −P2 −P3 の長さLに応じた数とすることができるが、このtの値も求められる直線分とベジェ曲線との誤差に直接的には対応していないため、例えば直線に近い曲線に対しても長さLが長いと、必要以上に多数の点を求めることになり、非常に効率の悪い演算を行うことになる。もちろん、長さLが短い場合には、演算は簡単になるが、曲率が大きな曲線に対しては誤差が大きくなる。
【0016】このように、従来の3次ベジェ曲線の補間近似による直線分列への展開の方法は、誤差を所定の許容値以下に抑えることができないか、非常に効率の悪い演算を行うことになるか、あるいはこれら両方の欠点を持っている。本発明は、このような事情に鑑みてなされたもので、3次ベジェ曲線で表現された曲線データを補間近似して直線分列を得るのに、比較的簡単な演算で済み、しかも誤差を的確に管理することを可能とする曲線描出方法および装置を提供することを目的としている。
【0017】
【課題を解決するための手段】本発明に係る曲線描出方法は、ベジェ関数で表された曲線情報を一連の直線分群で補間近似して出力するにあたり、ベジェ関数で表されたベジェ曲線データを格納する曲線格納ステップと、ベジェ関数で表されたベジェ曲線データを読み出す曲線読み出しステップと、読み出されたベジェ曲線データに基づいてベジェ曲線を定義するベジェ多角形の底辺から曲線までの距離の最大値を求める最遠点算出ステップと、前記最遠点算出ステップで求められた距離の最大値が所定の許容値以下か否かを判定する判定ステップと、前記判定ステップで前記許容値以下でないと判定された場合に前記ベジェ曲線を2分割する分割ステップと、前記分割ステップで2分割された結果得られる各曲線部分の各々について前記最遠点算出ステップからの処理を繰り返し実行させる繰り返しステップと、前記判定ステップで前記許容値以下であると判定された場合に、その曲線部分を、そのときのベジェ多角形の底辺に相当する直線分に置き換える直線置換ステップと、前記曲線読み出しステップで読み出されたベジェ曲線の全ての部分が前記直線置換ステップにより直線分に置換された後に、置換された一連の直線分群のデータを前記ベジェ曲線を補間近似する直線分群として出力する出力ステップとを有することを特徴としている。
【0018】本発明に係る曲線描出装置は、ベジェ関数で表された曲線情報を一連の直線分群で補間近似して出力する曲線描出装置において、ベジェ関数で表されたベジェ曲線データを格納するための曲線格納手段と、前記曲線格納手段から読み出されたベジェ曲線データおよび与えられたベジェ曲線データに基づいてベジェ曲線を定義するベジェ多角形の底辺から曲線までの距離の最大値を求めるための最遠点算出手段と、前記最遠点算出手段で求められた距離の最大値が所定の許容値以下か否かを判定するための判定手段と、前記判定手段で前記許容値以下でないと判定された場合にそのベジェ曲線を2分割するとともに分割の結果得られる各曲線部分の各々のベジェ曲線データを前記最遠点算出手段に与えるための分割手段と、前記判定ステップで前記許容値以下であると判定された曲線部分を、そのときのベジェ多角形の底辺に相当する直線分に置き換えるための直線置換手段と、前記曲線格納手段に格納されたベジェ曲線の全ての部分が前記直線置換手段により直線分に置換された一連の直線分群のデータを前記ベジェ曲線を補間近似する直線分群として出力するための出力手段とを有することを特徴としている。
【0019】
【作用】本発明の曲線描出方法および装置は、ベジェ関数で表された曲線情報を一連の直線分群で補間近似して出力するにあたり、ベジェ関数で表されたベジェ曲線データに基づいてベジェ曲線を定義するベジェ多角形の底辺から曲線までの距離の最大値を求め、前記距離の最大値が所定の許容値以下か否かを判定し、前記許容値以下でないと判定された場合に前記ベジェ曲線を2分割して、分割された結果得られる各曲線部分の各々について、前記ベジェ多角形の底辺から曲線までの距離の最大値を求めその距離の最大値が許容値以下でないかぎりそのベジェ曲線の2分割を繰り返すとともに、前記許容値以下であると判定された曲線部分を、そのときのベジェ多角形の底辺に相当する直線分に置き換えて、前記ベジェ曲線の全ての部分が置換された一連の直線分群のデータを前記ベジェ曲線を補間近似する直線分群として出力するので、3次ベジェ曲線で表現された曲線データを補間近似して直線分列を得るのに、比較的簡単な演算で済みしかも誤差を的確に管理することが可能となる。
【0020】
【実施例】本発明の実施例の説明に先立ち、まず、本発明において3次ベジェ曲線で表現された曲線データを補間近似して直線分列を得るために用いる基本的な原理を説明する。
【0021】《補間アルゴリズム》本発明における補間アルゴリズムは、主として、ベースラインとベジェ曲線との間の距離を求めるアルゴリズムと、ベジェ曲線を2つのベジェ曲線へ分割するアルゴリズムとから構成されている。すなわち、この補間アルゴリズムでは、図24に示されたような3次ベジェ曲線が与えられたとすると、図8に示すように、ベースラインP0 −P3 からベジェ曲線P(t) の頂点までの距離、すなわちベースラインP0 −P3 からベジェ曲線P(t) までの最大距離dを求める。この距離dが与えられたトレランス(許容値)δ以下であれば、ベースラインP0 −P3 はベジェ曲線P(t) を補間近似する直線分そのものである。もしも、距離dがトレランスδを超えていれば、図9のようにベジェ曲線P(t) を2分割する点とベジェ曲線P(t) の始点P0 および終点P3 とをそれぞれ結ぶ2本の直線分で近似する。こうすれば、ベースライン1本よりもよい近似が行える。次に、図10のように、これら2本の直線分とベジェ曲線P(t) との間の最大距離d1およびd2をそれぞれ求め、これらがトレランスδ以下であれば補間近似処理を終了とする。最大距離d1およびd2がトレランスδを超えていれば、図11に示すようにさらに2本の直線分で補間する。このような処理を近似直線分とベジェ曲線P(t) との間の最大距離がすべてトレランスδ以下になるまで繰り返し行う。このようにして、補間近似処理が完了すると、例えば図12に示すようになる。
【0022】次に、上述におけるベースライン(直線分)とベジェ曲線との間の最大距離の求め方およびド・カステリョ(de Casteljau)のアルゴリズムを用いたベジェ曲線の分割について述べる。
【0023】《ベースラインとの距離(2次ベジェ曲線の場合)》ここでは、3次ベジェ曲線について検討する前に、2次ベジェ曲線におけるベースラインからの距離について考察する。2次ベジェ曲線は、先に述べた数1であらわされ、一般的には例えば図13に示されるような形となる。ここで、3個の制御点P0 、P1 およびP2 のうちの制御点P0 を原点(0,0)とし、制御点P2 をX軸上の点(X2 ,0)として、2次ベジェ曲線のベースラインがX軸に一致するようにする。この条件では、数1は数6のようにあらわすことができる。なお、制御点P1 は(X1 ,Y1 )であらわされる。
【0024】
【数6】X(t) =2(1−t)tX1 +t22Y(t) =2(1−t)tY1
【0025】この数6であらわされる2次ベジェ曲線は図14のようになる。図14においてベースライン(X軸)から最も離れている点は、次の数7を満足する。
【0026】
【数7】dY/dX=0
【0027】dX/dt=dY/dt=0となることはないので、数7より数8が得られる。
【0028】
【数8】(dY/dt)/(dX/dt)=0すなわちdY/dt=0
【0029】数6より、数9となる。
【0030】
【数9】dY/dt=(2−4t)Y1 =0t=1/2
【0031】したがって、t=0.5のときにベジェ曲線はベースラインから最も離れる。この場合のベースラインからベジェ曲線までの距離は、そのときのYの値であって、t=0.5を数6に代入することによって求めることができ、数10であらわされる。
【0032】
【数10】d=Y(0.5)=0.5Y1
【0033】すなわち、ベースラインから制御点P1 までの距離の半分がベースラインからベジェ曲線までの最大距離となる(この点について図14は必ずしも正しく描かれていない)。以上の計算は、数6であらわされる図14のような2次ベジェ曲線に対して有効である。数1のような一般形のベジェ曲線は、ベジェ曲線がアフィン変換に対して不変であるという特徴を利用して、制御点P0 、P1 およびP2 の3点を曲線とベースラインとの間の距離を変えることなく標準形へ変換すればよい。ここで、図14の標準形の条件を示す。制御点P0 は原点であり、制御点P2 はX軸上の点であり、距離d=0.5Y1 は正であるので、数11〜数13が得られる。
【0034】
【数11】X0 =Y0 =0
【0035】
【数12】Y2 =0
【0036】
【数13】Y1 >0
【0037】以上の数11〜数13の条件を満たすように制御点P0 、P1 およびP2 の3点を平行移動、回転、およびミラー演算する。次に、図15に示すように、一般形をした2次ベジェ曲線を定義する制御点P0 =(X0 ,Y0 )、P1 =(X1 ,Y1 )およびP2 =(X2 ,Y2 )からそれらを共通に平行移動および回転した標準形のベジェ曲線の制御点Q0 =(U0,V0 )、Q1 =(U1 ,V1 )およびQ2 =(U2 ,V2 )を求める手順を説明する。数11から数14および数15が求められる。
【0038】
【数14】U0 =0
【0039】
【数15】V0 =0
【0040】数12と図15から数16および数17が求められる。
【0041】
【数16】
2 =√{(X2 −X02 +(Y2 −Y02
【0042】
【数17】V2 =0
【0043】制御点Q1 は、制御点P1 を、制御点P0 から制御点Q0 (原点)への移動と同様に平行移動し、さらに原点を中心として、線分P02 とX軸とがなす角だけ時計回りに回転して得られる。したがって、数18が得られる。
【0044】
【数18】


【0045】すなわち、数19および数20が得られる。
【0046】
【数19】


【0047】
【数20】


【0048】結局、2次ベジェ曲線のベースラインからの最大距離dは数21であらわされる。
【0049】
【数21】


【0050】《ベースラインとの距離(3次ベジェ曲線・凸閉包の場合)》3次ベジェ曲線についてのベースラインからの距離についても、上述の2次ベジェ曲線で用いた方法を利用して計算することができる。先に述べた数2であらわされる3次ベジェ曲線の標準形は、図16に示され、その条件は数22〜数26であらわされる。
【0051】
【数22】X0 =Y0 =0
【0052】
【数23】X3 >0
【0053】
【数24】Y3 =0
【0054】
【数25】Y1 >0
【0055】
【数26】|Y1 |≧|Y2
【0056】これらの条件のうちの数22および数24を数2に代入して、数27が得られる。
【0057】
【数27】
Y(t) =3(1−t)2 tY1 +3(1−t)t22 =3{(Y1 −Y2 )t3 −(2Y1 −Y2 )t2 +Y1 t}
【0058】数27の両辺をtで微分して数28を得る。
【0059】
【数28】
dY/dt=3{3(Y1 −Y2 )t2 −2(2Y1 −Y2 )t+Y1
【0060】図16において曲線がベースラインから最も離れるときのtの値は、数29より数30を解くことにより数31として与えられる。
【0061】
【数29】dY/dX=0
【0062】
【数30】


【0063】
【数31】


【0064】ここで、図16のベジェ曲線上の点については0≦t≦1の区間に限定すると、数25および数26の条件から数32が得られる。
【0065】
【数32】


【0066】このときのベースラインからの距離dは数32で得られるtの値をτとすると、これを数27に代入して数33を求めることができる。
【0067】
【数33】


【0068】以上の方法は、数27すなわち図16のような標準形の3次ベジェ曲線に対して有効である。一般形の3次ベジェ曲線は、2次ベジェ曲線の場合と同様、図17に示されるような平行移動、回転およびミラー演算によって最大距離dを変化させることなく標準形に変換することができる。
【0069】次に、図17に示すように、制御点P0 =(X0 ,Y0 )、P1 =(X1 ,Y1 )、P2 =(X2 ,Y2 )およびP3 =(X3 ,Y3 )で定義される一般形の3次ベジェ曲線を、制御点Q0 =(U0 ,V0 )、Q1 =(U1 ,V1 )、Q2=(U2 ,V2 )およびQ3 =(U3 ,V3 )で定義される標準形のベジェ曲線に変換する手順を検討する。2次ベジェ曲線の場合と同様に数22および数24から数34〜数37が得られる。
【0070】
【数34】U0 =0
【0071】
【数35】V0 =0
【0072】
【数36】
3 =√{(X3 −X02 +(Y3 −Y02
【0073】
【数37】V3 =0
【0074】ここでベースラインとX軸とのなす角度θは、数38および数39であらわされる。
【0075】
【数38】


【0076】
【数39】


【0077】したがって、数40が得られる。
【0078】
【数40】


【0079】ここで、もしも|V1 |<|V2 |であるならば、U1 とU2 とを交換し、且つV1 とV2 とを交換する(あるいは、数31における2乗根の前の符号として+を採用する)。さらに、V1 <0であれば、V1 の符号とV2 の符号とをそれぞれ正負逆にする。このようにすれば、3次ベジェ曲線を標準形に変換することができ、上述の数32および数33より、ベースラインからベジェ曲線までの距離の最大値を求めることができる。
【0080】《3次ベジェ曲線の分割》次に、上述のようにして求めた距離dが所定のトレランスδを超えていた場合に、ベジェ曲線を分割して、2本の線分(直線分)で補間近似する方法について説明する。一般に、ベジェ曲線を分割するには、ド・カステリョ(de Casteljau)の方法があり、本発明においてもド・カステリョの方法を利用する。図18にド・カステリョの方法を用いた3次ベジェ曲線の分割の過程の概略を模式的に示す。制御点P0 、P1 、P2 およびP3 で定義される3次ベジェ曲線(以下、「制御点P0 、P1 、P2 およびP3 で定義される3次ベジェ曲線」は単に「3次ベジェ曲線P0 −P1 −P2 −P3 」と称する)は、次のようにしてt=τで2つのベジェ曲線に分割する。
【0081】(1) 3本の線分P1 −P0 、P2 −P1 およびP3 −P2 をそれぞれτ:1−τに内分し、それら内分点をそれぞれP10、P11およびP12とする。
(2) 線分P11−P10およびP12−P11をそれぞれτ:1−τに内分し、それら内分点をそれぞれP20およびP21とする。
(3) 線分P20−P21をτ:1−τに内分し、その内分点をP30とする。
(4) このようにして3次ベジェ曲線P0 −P1 −P2 −P3 は2つの3次ベジェ曲線P0 −P10−P20−P30とP30−P21−P12−P3 に分割することができる。
以上に述べたように、3次ベジェ曲線を補間近似するには、ベースラインからの最大距離を求め、そのベースラインからの最遠点で2分割を繰り返し行うことにより、所定のトレランス以内の誤差で直線列に分割補間することができる。
【0082】《凸閉包以外の3次ベジェ曲線の場合》以上に述べた3次ベジェ曲線は、その制御多角形が凸閉包であることを前提としていた。しかし、3次ベジェ曲線には図19に示すような凸閉包でない3次ベジェ曲線も存在し得る。これらの場合においても、図20に示すように、上述と同様の方法で、補間近似することができる。例外的な3次ベジェ曲線として、図21に示すように始終点P0 とP3 が一致した3次ベジェ曲線がある。このような3次ベジェ曲線の場合には、線分P1 −P2 がX軸と平行になるように変換して、X軸からの最遠点で分割すればよい(図22参照)。以上のような原理により、3次ベジェ曲線で表現された曲線データを、比較的簡単な演算で所定の誤差範囲内に管理しつつ補間近似して直線分列を得ることができる。このような原理によりベジェ曲線−直線列変換を行って曲線描出装置を構成することができる。
【0083】上述の原理に基づく本発明の実施例を、以下、図面を参照して説明する。図1は、本発明の一実施例に係る曲線描出装置の概略的な構成を示している。本実施例の曲線描出装置では、3次ベジェ曲線で表現された曲線データを補間近似するにあたり、ベジェ曲線を必要に応じて変換し標準形のベジェ曲線として、ベジェ曲線を定義するベジェ多角形の底辺から曲線までの距離の最大値を求め、前記最大値が所定の許容値以下でない場合に前記ベジェ曲線を2分割して、分割された結果得られる各曲線部分の各々について、さらにベジェ多角形の底辺から曲線までの距離の最大値を求め、その距離の最大値が許容値以下でないかぎりベジェ曲線の2分割を繰り返すとともに、前記距離の最大値が許容値以下の曲線部分を、そのときのベジェ多角形の底辺に相当する直線分に置き換えて、もとの曲線データを補間近似する一連の直線分群のデータを出力することができる。
【0084】図1に示す曲線描出装置は、曲線−直線列変換処理部10および記憶装置20を有している。曲線−直線列変換処理部10は、典型的にはCPU(中央処理装置)を含み主としてソフトウェアにより所定のごとく機能するように構成される。もちろん、この曲線描出処理部10の一部または全部は、各機能要素に相当するハードウェアにより構成するようにしてもよい。記憶装置20は、例えばメモリおよびハードディスク装置のようなディスク装置等の少なくともいずれかを備え、直線列に変換されるべき原ベジェ曲線データが予め格納されるとともに、曲線−直線列変換処理に関連する座標、曲線および直線データ、ならびに曲線−直線列変換処理により得られる直線列データを含むデータが適宜必要に応じて格納される。この記憶装置20は、本実施例による曲線描出装置が組み込まれるシステムの記憶装置の一部を利用してもよい。
【0085】曲線−直線列変換処理部10は、原データ読出し部11、標準形変換部12、最大距離算出部13、比較部14、トレランス規定部15、分割点決定/ベースライン出力部16、分割処理部17、および出力処理部18を備えている。原データ読出し部11は、予め記憶装置20に格納されているベジェ曲線の原データを読出して曲線−直線列変換処理のため標準形変換部12に与える。標準形変換部12は、与えられたベジェ曲線データが、先に述べたような標準形のベジェ曲線であるときはそのまま最大距離算出部13に与え、前記ベジェ曲線データが標準形でないときは、そのデータを標準形に変換して最大距離算出部13に与える。最大距離算出部13は、与えられた標準形のベジェ曲線データについてベースラインからの距離の最大値すなわち最大距離を求める。トレランス規定部15は、ベジェ曲線に対する直線列の近似誤差の所要の許容値すなわちトレランスを保持規定する。このトレランスは、例えば外部操作に基づく設定入力により所要の条件に合わせて設定されるものとする。
【0086】比較部14は、最大距離算出部13で得られた最大距離とトレランス規定部15で規定されたトレランスとを比較し、その比較結果を分割点決定/ベースライン出力部16に与える。分割点決定/ベースライン出力部16は、比較部14の比較結果に応じて異なる2つの機能を有する。すなわち、前記最大距離が前記トレランスを超えているときは、分割点決定/ベースライン出力部16はこの場合前記最大距離が得られたベジェ曲線上の点を、もとのベジェ曲線の分割点として決定し分割処理部17に与える。また、前記最大距離が前記トレランス以下であるときは、分割点決定/ベースライン出力部16は、そのときのベースラインに相当する直線分を、そのベジェ曲線の近似直線分として出力処理部18に与える。
【0087】分割処理部17は、分割点決定/ベースライン出力部16より与えられる分割点でもとのデータを2分割し、2分割の結果得られる各ベジェ曲線データを標準形変換部12に与える。標準形変換部12は、分割処理部17から与えられたベジェ曲線データについても、原データの場合と同様、標準形のベジェ曲線であるときはそのまま最大距離算出部13に与え、前記ベジェ曲線データが標準形でないときは、そのデータを標準形に変換して最大距離算出部13に与える。出力処理部18は、分割点決定/ベースライン出力部16より与えられる直線分列を原データ読出し部11で読出された原ベジェ曲線データが変換された近似直線分列として出力する。次に、このような構成の曲線描出装置における特に本発明のベジェ補間による曲線−直線列変換に係る動作を図2〜図5に示すフローチャートを参照して詳細に説明する。
【0088】図2はベジェ補間による曲線−直線列変換の全体の処理を示している。まず、与えられた3次元ベジェ曲線データについて、ベースラインからベジェ曲線までの最大距離dを求める(ステップS1)。次に、このようにして求められた最大距離dを予め設定されたトレランスδと比較する(ステップS2)。前記最大距離dがトレランスδを超えているとき(d>δ)は、前記与えられた3次元ベジェ曲線データを前記最大距離dを与える点で2分割し、第1および第2の3次ベジェ曲線を得る(ステップS3)。このステップS3で求められた第1のベジェ曲線について図2のベジェ補間処理を再帰的に呼び出す(ステップS4)。前記このステップS3で求められた第2のベジェ曲線について図2のベジェ補間処理を再帰的に呼び出す(ステップS5)。
【0089】ステップS5の処理後はステップS2へ戻る。また、ステップS2で、前記最大距離dがトレランスδ以下である(d≦δ)と判定されたときは、そのときのベースラインに相当する直線分を出力する(ステップS6)。図3に、図2のステップS1における3次ベジェ曲線のベースラインからの距離計算の詳細な処理を示す。図3の処理では、3次ベジェ曲線のベースラインから3次ベジェ曲線上の最遠点までの距離、すなわちベースラインから3次ベジェ曲線までの最大距離およびその最遠点を与えるtを求める。まず、ベジェ多角形P0 −P1 −P2 −P3 を制御点P0 が原点(0,0)となるように平行移動する(ステップS11)。すなわち、P0 、P1 、P2 およびP3 のX座標をそれぞれP0x、P1x、P2xおよびP3xとし、P0 、P1 、P2 およびP3 のY座標をそれぞれP0y、P1y、P2yおよびP3yとすると、数41で示される変換を行う。
【0090】
【数41】P1x=P1x−P0x2x=P2x−P0x3x=P3x−P0x0x=0P1y=P1y−P0y2y=P2y−P0y3y=P3y−P0y0y=0
【0091】次に、ベースラインがX軸に一致するようにベジェ多角形を回転させて(ステップS12)、制御点P1 およびP2 のY座標P1yおよびP2yを求める(ステップS13)。制御点P2 のほうが制御点P1 よりもベースラインから遠いか否か、すなわちP1 のY座標P1yの絶対値|P1y|がP2 のY座標P2yの絶対値|P2y|を超えているか否かを判定する(ステップS14)。ステップS14で、制御点P2 のほうが制御点P1 よりもベースラインから遠ければ(P1 のY座標P1yの絶対値|P1y|がP2 のY座標P2yの絶対値|P2y|を超えていれば)、P1yとP2yとを入れ替えてから(ステップS15)、ステップS16へ移行する。ステップS14で、制御点P2 のほうが制御点P1 よりもベースラインから遠くなければ(P1 のY座標P1yの絶対値|P1y|がP2 のY座標P2yの絶対値|P2y|以下であれば)、そのままステップS16へ移行する。
【0092】ステップS16では、制御点P1 のY座標P1yが負か否かを調べ、P1yが負でなければそのままステップS18へ移行し、P1yが負ならば、P1 およびP2 のY座標P1yおよびP2yの符号を逆にしてから(ステップS17)、ステップS18へ移行する。ステップS18では、ベースラインからベジェ曲線の最遠点までの距離dおよび該最遠点を与えるt=τを求め(ステップS18)、図2のメインルーチンへ戻る。図4に、図2のステップS3における3次ベジェ曲線の2分割の詳細な処理を示す。図4の処理は、図3のステップS18で求められたベースラインから最遠点までの距離dが所定のトレランスを超えているときに実行され、この図4の処理では、3次ベジェ曲線を図3のステップS18で求められたt=τに基づいて3次ベジェ曲線を前記最遠点にて2つの3次ベジェ曲線に分割する。
【0093】まず、ベジェ多角形P0 −P1 −P2 −P3 の3辺P0 −P1 、P1 −P2 およびP2 −P3 をそれぞれτ:1−τに内分する(ステップS21)。すなわち、ステップS21では、P0 −P1 をP0 −P10:P10−P1 に内分し、P1 −P2 をP1 −P11:P11−P2 に内分し、P2 −P3 をP2 −P12:P12−P3 に内分する。次に、ステップS21における内分点P10、P11およびP12相互間を結ぶ線分P11−P10およびP12−P11をそれぞれτ:1−τに内分する(ステップS22)。すなわち、ステップS22では、P10−P11をP10−P20:P20−P11に内分し、P11−P12をP11−P21:P21−P12に内分する。さらに、ステップS22における内分点P20とP21とを結ぶ線分P20−P21をτ:1−τに内分する(ステップS23)。すなわち、ステップS23では、P20−P21をP20−P30:P30−P21に内分する。
【0094】ステップS21〜S23の結果より、2つの3次ベジェ曲線P0 −P10−P20−P30とP30−P21−P12−P3 とを得る。図5に、図2のステップS6におけるベースライン直線出力の処理内容を示す。図5の処理は、図3のステップS18で求められたベースラインから最遠点までの距離dが所定のトレランスを満たしているときに実行され、この図5の処理では、そのベジェ曲線のベースラインP0 −P3 を作図するための情報を出力する(ステップS31)。このように、図2の処理は、図2のステップS4およびS5で再帰的に用いられるので、プログラム自体を再帰的呼び出し可能とすることにより、プログラム全体を小規模に作ることができる。もちろん、ベジェ曲線の分割の繰り返し回数の最大値を適宜制限すれば、再帰的呼び出しを用いずにプログラムを構成することもできる。
【0095】上述のような、曲線描出装置は、3次ベジェ曲線を近似直線分列に変換するために種々の形態で用いることができる。例えば、ホストコンピュータにおけるベジェ曲線を近似直線分列としてプロッタにより描画出力する場合には、図6のように、図1に示したような曲線−直線列変換部10をホストコンピュータ30内に設け、ホストコンピュータ30内で、ベジェ曲線から直線列への変換を行い、ホストコンピュータ30から直線列データをプロッタ40に与えるようにすればよい。このようにすれば、曲線−直線列変換処理をホストコンピュータ30のCPUにより行うことができる。また、同様に、ホストコンピュータにおけるベジェ曲線を近似直線分列としてプロッタにより描画出力する場合に、図7のように曲線−直線列変換部10をプロッタ41内に設け、プロッタ41内で、ベジェ曲線から直線列への変換を行うようにすることもできる。この場合、プロッタ41内のCPUで曲線−直線列変換処理を行うことになるが、ホストコンピュータ31からプロッタ41に与えるデータはベジェ曲線データのままでよく、ホストコンピュータ31側の処理を軽減させることができる。
【0096】なお、上述の実施例では、ベースラインからの最遠点でベジェ曲線を分割するようにしたが、ベースラインからの最大距離が所定のトレランスを超えている場合に、必ずしも最遠点で分割しなくてもよく、例えばt=0.5等の固定のtの値に対応する個所でベジェ曲線を分割するようにしたり、その他の適宜なる点でベジェ曲線を分割するようにしたりしてもよい。また、ベジェ曲線を直線分列に変換した後、プロッタまたは工作機械に与えて曲線の描画または曲線加工を行うばかりでなく、ベジェ曲線を直線分列に変換した後、さらにラスタ展開して、ディスプレイまたはいわゆるラスタプロッタに与えるようにすることにより、ディスプレイまたはいわゆるラスタプロッタに曲線を描画する際にも本発明を有効に用いることができる。
【0097】
【発明の効果】以上述べたように、本発明によれば、ベジェ関数で表された曲線情報を一連の直線分群で補間近似して出力するにあたり、ベジェ関数で表されたベジェ曲線データに基づいてベジェ曲線を定義するベジェ多角形の底辺から曲線までの距離の最大値を求め、前記距離の最大値が所定の許容値以下か否かを判定し、前記許容値以下でないと判定された場合に前記ベジェ曲線を2分割して、分割された結果得られる各曲線部分の各々について、前記ベジェ多角形の底辺から曲線までの距離の最大値を求めその距離の最大値が許容値以下でないかぎりそのベジェ曲線の2分割を繰り返すとともに、前記許容値以下であると判定された曲線部分を、そのときのベジェ多角形の底辺に相当する直線分に置き換えて、前記ベジェ曲線の全ての部分が置換された一連の直線分群のデータを前記ベジェ曲線を補間近似する直線分群として出力するようにして、比較的簡単な構成によって、3次ベジェ曲線データを補間近似して直線分列を得ることができ、しかも誤差を的確に管理することを可能とする曲線描出方法および装置を提供することができる。
【図面の簡単な説明】
【図1】 本発明の一実施例に係る曲線描出装置の概略的な構成を示すブロック図である。
【図2】 図1の曲線描出装置のベジェ補間による曲線−直線列変換の全体の概略的な処理を説明するためのフローチャートである。
【図3】 図2における3次ベジェ曲線のベースラインからの距離計算の詳細な処理を説明するためのフローチャートである。
【図4】 図2における3次ベジェ曲線の2分割の詳細な処理を説明するためのフローチャートである。
【図5】 図2におけるベースライン直線出力の詳細な処理を説明するためのフローチャートである。
【図6】 図1の曲線描出装置を用いたシステムの一例の構成を模式的に示すブロック図である。
【図7】 図1の曲線描出装置を用いたシステムの他の一例の構成を模式的に示すブロック図である。
【図8】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、ベースラインからベジェ曲線までの距離を説明するための図である。
【図9】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、2本の直線分によるベジェ曲線の近似を説明するための図である。
【図10】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、近似線分とベジェ曲線との間の距離を説明するための図である。
【図11】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、再度の補間近似を説明するための図である。
【図12】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、補間近似の終了状態を説明するための図である。
【図13】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、2次ベジェ曲線の一般形を説明するための図である。
【図14】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、2次ベジェ曲線の標準形を説明するための図である。
【図15】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、一般形の2次ベジェ曲線の標準形への変換を説明するための図である。
【図16】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、3次ベジェ曲線の標準形を説明するための図である。
【図17】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、一般形の3次ベジェ曲線の標準形への変換を説明するための図である。
【図18】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、ド・カステリョの方法による3次ベジェ曲線の分割を模式的に説明するための図である。
【図19】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、凸閉包でない3次ベジェ曲線の異なる2つの例を示す図である。
【図20】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、凸閉包でない3次ベジェ曲線の異なる2つの例における曲線−直線列変換を模式的に説明するための図である。
【図21】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、始終点の一致した3次ベジェ曲線の一例を示す図である。
【図22】 本発明の一実施例に用いるベジェ補間による曲線−直線列変換の原理説明において、始終点の一致した3次ベジェ曲線の一例における曲線−直線列変換を模式的に説明するための図である。
【図23】 2次ベジェ曲線の一例を示す図である。
【図24】 3次ベジェ曲線の一例を示す図である。
【符号の説明】
10…曲線−直線列変換処理部、11…原データ読出し部、12…標準形変換部、13…最大距離算出部、14…比較部、15…トレランス規定部、16…分割点決定/ベースライン出力部、17…分割処理部、18…出力処理部、20…記憶装置、30,31…ホストコンピュータ、40,41…プロッタ。

【特許請求の範囲】
【請求項1】 ベジェ関数で表された曲線情報を一連の直線分群で補間近似して出力するにあたり、ベジェ関数で表されたベジェ曲線データを格納する曲線格納ステップと、ベジェ関数で表されたベジェ曲線データを読み出す曲線読み出しステップと、読み出されたベジェ曲線データに基づいてベジェ曲線を定義するベジェ多角形の底辺から曲線までの距離の最大値を求める最遠点算出ステップと、前記最遠点算出ステップで求められた距離の最大値が所定の許容値以下か否かを判定する判定ステップと、前記判定ステップで前記許容値以下でないと判定された場合に前記ベジェ曲線を2分割する分割ステップと、前記分割ステップで2分割された結果得られる各曲線部分の各々について前記最遠点算出ステップからの処理を繰り返し実行させる繰り返しステップと、前記判定ステップで前記許容値以下であると判定された場合に、その曲線部分を、そのときのベジェ多角形の底辺に相当する直線分に置き換える直線置換ステップと、前記曲線読み出しステップで読み出されたベジェ曲線の全ての部分が前記直線置換ステップにより直線分に置換された後に、置換された一連の直線分群のデータを前記ベジェ曲線を補間近似する直線分群として出力する出力ステップとを有することを特徴とする曲線描出方法。
【請求項2】 分割ステップは、最遠点算出ステップで算出された最遠点をとる点でベジェ曲線を分割するステップを含むことを特徴とする請求項1に記載の曲線描出方法。
【請求項3】 分割ステップは、ベジェ曲線の中間部の適宜なる点でベジェ曲線を分割するステップを含むことを特徴とする請求項1に記載の曲線描出方法。
【請求項4】 最遠点算出ステップは、ベジェ曲線を標準型に変換するステップを含むことを特徴とする請求項1〜3のいずれか1項に記載の曲線描出方法。
【請求項5】 出力ステップは、得られた直線分群をラスタ展開するステップを含むことを特徴とする請求項1〜4のいずれか1項に記載の曲線描出方法。
【請求項6】 ベジェ関数で表された曲線情報を一連の直線分群で補間近似して出力する曲線描出装置において、ベジェ関数で表されたベジェ曲線データを格納するための曲線格納手段と、前記曲線格納手段から読み出されたベジェ曲線データおよび与えられたベジェ曲線データに基づいてベジェ曲線を定義するベジェ多角形の底辺から曲線までの距離の最大値を求めるための最遠点算出手段と、前記最遠点算出手段で求められた距離の最大値が所定の許容値以下か否かを判定するための判定手段と、前記判定手段で前記許容値以下でないと判定された場合にそのベジェ曲線を2分割するとともに分割の結果得られる各曲線部分の各々のベジェ曲線データを前記最遠点算出手段に与えるための分割手段と、前記判定ステップで前記許容値以下であると判定された曲線部分を、そのときのベジェ多角形の底辺に相当する直線分に置き換えるための直線置換手段と、前記曲線格納手段に格納されたベジェ曲線の全ての部分が前記直線置換手段により直線分に置換された一連の直線分群のデータを前記ベジェ曲線を補間近似する直線分群として出力するための出力手段とを有することを特徴とする曲線描出装置。
【請求項7】 分割手段は、最遠点算出手段で算出された最遠点をとる点でベジェ曲線を分割するための手段を含むことを特徴とする請求項6に記載の曲線描出装置。
【請求項8】 分割手段は、ベジェ曲線の中間部の適宜なる点でベジェ曲線を分割するための手段を含むことを特徴とする請求項6に記載の曲線描出装置。
【請求項9】 最遠点算出手段は、ベジェ曲線を標準型に変換するための手段を含むことを特徴とする請求項6〜8のいずれか1項に記載の曲線描出装置。
【請求項10】 出力手段は、得られた直線分群をラスタ展開するための手段を含むことを特徴とする請求項6〜9のいずれか1項に記載の曲線描出装置。
【請求項11】 出力手段は、得られた直線分群を描画するプロッタであることを特徴とする請求項6〜10のいずれか1項に記載の曲線描出装置。

【図5】
image rotate


【図6】
image rotate


【図8】
image rotate


【図11】
image rotate


【図1】
image rotate


【図10】
image rotate


【図12】
image rotate


【図21】
image rotate


【図2】
image rotate


【図3】
image rotate


【図4】
image rotate


【図9】
image rotate


【図20】
image rotate


【図7】
image rotate


【図13】
image rotate


【図14】
image rotate


【図15】
image rotate


【図16】
image rotate


【図17】
image rotate


【図18】
image rotate


【図19】
image rotate


【図22】
image rotate


【図23】
image rotate


【図24】
image rotate