JPH04167082A - ベゼー曲線区間の多角形近似方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、ＣＡＤシステム等のコンピュータ図形処理
システムにおいて、曲線式で記述されている文字等の輪
郭部を多角形に近似する近似方式に関し、特に、少ない
頂点数で高い近似精度を得ることのできる曲線分割数の
決定方式に関する。

〔従来の技術〕

ＣＡＤシステム等のコンピュータ図形処理システムでは
、一般に文字等の輪郭部はベゼー（または、ベジェ：　
Ｂ５ｚｉｅｒ　）曲線等のｍ次元多項式曲線で記述され
ている。このため、これらの輪郭部を、プリンタで印字
したり、デイスプレィ画面上に描画したりする場合には
、輪郭部の各曲線区間を、ポリゴン（ｐｏｌｙｇｏｎ　
：多角形面）に近似してビットマツプに展開する必要が
ある。３次元ベゼー曲線を、ポリゴンに近似する場合、
各頂点座標は次のようにして求める。まず、３次元ベゼ
ー曲線は、第５図に示すように、始点をＰＧ、制御点を
Ｐｌ、Ｐ２、終点をＰａとすると、 Ｂ（ｔ）＝Ｐｏ（１ｔ）３＋３Ｐｔ（１−ｔ）”ｔ＋３
Ｆ’２　（１ｔ）ｔ”　＋Ｐ３　　ｔ’・・・■（０≦
ｔ≦１） で表される。これを一般の３次元多項式に変形すると、 Ｂ　（ｔ）　＝　Ｚ　（ｔ） ＝Ａ３　　ｔ’＋Ａ２　　ｔ”＋Ａｌ　　ｔ＋ＡＯ・・
・■（０≦ｔ≦１） ただし、 Ａａ　＝　（Ｐａ　−Ｐｏ　＋３　（Ｐｔ　−Ｐ２　）
　）Ａ２　＝　　３　（Ｐｔ　　Ｐａ　＋（Ｐｔ　　Ｐ
２　））Ａ１＝３　（Ｐｔ　　Ｐａ　） ＡＯ＝ＰＯ となる。

次いで、曲線区間の分割数をｎとし、かつ、ｔ＝ｉ／ｎ ｇａ＝Ａｓ／ｎ’ ｇ２°Ａ２／ｎ” ｇ１＝Ａｔ／ｎ ｇＯ°ＡＯ とおくと、 Ｚ　（ｔ）　＝　Ｇ　（ｉ） −ｇａ　ｉ’　十ｇ２ｉ２＋ｇｔ　ｉ＋ｇ。

＝（（ｇａ　　ｉ　＋ｇ２）ｉ十ｇｔ　）ｉ＋ｇｏ　　
・・・■（ｉ＝０．１＋２．・・・、ｎ） と変形できる。この式■によると、固定値ｇ３〜ｇｏの
計算は必要であるが、１つの頂点座標の演算は３回の掛
算と３回の加算とで済むため、一般式■に比べ、演算回
数を大幅に減らすことが出来る（特願平２−７６１４８
号参照）。

〔発明が解決しようとする課題〕

ところで、所定の曲線区間をポリゴンに近似して描画す
る場合、ポリゴンの分割数ｎの決定はポリゴンの生成速
度に大きく影響する。このため、キー操作に対する優れ
た即答性が要求される図形処理システムでは、分割数ｎ
の決定は極めて重要である。ところが、前述の従来例で
は、ポリゴンの頂点座標の高速演算方式については述べ
ているが、分割数ｎの算出については触れていない。

この発明は、文字等の輪郭部の曲線区間をポリゴンで近
イ以する場合、少ない頂点数で高い近似精度を得ること
のできる曲線分割数の決定方式を提供することを目的と
し、さらに、こうして得た分割数によって生成されるポ
リゴンの各頂点座標の演算速度の高速化を図ることを目
的とする。

〔課題を解決するための手段〕

この発明による曲線区間の多角形近似方式は、ｍ次元多
項式で表される所定の曲線区間を、複数区間に分割して
多角形で近似する際に、多角形の隣接する頂点Ｐ　（ｉ
）およびＰ　（ｉｌｌ）の弦Ｐ　（ｉ）・Ｐ（ｉｌｌ）
の中点から弧Ｐ　（ｉ）・Ｐ　（ｉｌｌ）の中点までの
距離が所定の近似精度となるように曲線区間の分割数を
決定する。

Ｅ作　用〕 この発明によれば、所定の曲線区間が、例えば３次元ベ
ゼー曲線で定義されているとすると、第３図に示すよう
に、ベゼー曲線１０をｎ分割した点をＰ　（ｉ）、　　
Ｐ　（ｉｌｌ）、　・・・、Ｎ　（＝２ｎ）分割した点
をＱ（２ｊ）、　Ｑ（２ｉ＋１）、　Ｑ（２ｉ＋２）、
・・・、ただし、Ｐ　（ｉ）　＝　Ｑ（２ｉ）　、　　
Ｐ　（ｉｌｌ）　＝　Ｑ　（２ｉ＋２）とすると、点Ｑ
　（２ｉ）と点Ｑ　（２ｉ＋２）とを結ぶ直線１１の中
点Ｍ　（２ｉ＋１）および点Ｑ（２ｉ÷１）の距離Ｅｒ
は次のように表される。

Ｅｒ　＝　ｌ　Ｑ（２ｉ＋１）−Ｍ（２ｉ＋１）　ｌ　
　　　　・・・■ここで、 Ｑ　（２ｉ＋１）＝　Ｇ　（２ｉ＋１）Ｍ（２ｉ＋１）
＝　　（Ｇ（２ｉ＋２）＋Ｇ（２ｉ））／　２であるか
ら、 Ｅｒ　＝　Ｉ　Ｑ（２ｉ＋１）　　Ｍ（２ｉ＋１）　ｌ
−Ｉ　Ｇ（２３＋１）　−（Ｇ（２ｊ＋２）＋Ｇ（２ｉ
））　／　２１・・・■ となる。

ところで、頂点座標Ｇ　（ｉ）を表す式■は、３次元多
項式であるから、第４図に示すように、Ｇ　（ｉ）　。

Ｆ　（ｉ）、　Ｅ　（ｉ）の３つの定数テーブルの層で
表すことが出来る。内容は次元毎の差分になっており、
例えば、Ｇ（４）の値はＣ；（３）（＝ｇａ）およびＦ
（３）の和から求められ、Ｆ（３）の値はＦ（２）　（
＝　ｆ　２　）およびＥ（２）の和から求められる。こ
の操作を順に続けて行けば、各頂点座標Ｇ　（ｉ）が求
まる。

テーブルＧ　（ｉ）は式■から、 Ｇ　（ｉ＋１）　−Ｇ　（ｉ） ＝ｇｓ　（（ｉ　＋１）’　−ｉ’） 十ｇ２（（ｉ＋１）”　−１ｚ） 十ｇ　ｓ　（（ｉ　＋１）−ｉ） ＝ｇｓ　　（３ｉ２＋３　ｉ＋１） 十ｇ２　（２ｉ＋１）十ｇｔ ＝３ｇａ　ｉ”　＋（３ｇｇ　＋２Ｈ）　ｉ＋　（ｇｓ
　＋ｇ２＋ｇｓ　） −ｆ２　　ｉ”　＋ｆ１　ｉ＋ｆｇ　＝Ｆ（ｉ）　　　
＝■となる。ただし、 ｆ２＝３ｇｇ ｆ　１＝３　ｇｇ　＋２　ｇｚ ｆｏ　＝ｇｓ　十ｇ２＋ｇｉ である。

テーブルＦ　（ｉ）は弐〇から、 Ｆ　（ｉ＋１）　−Ｆ　（ｉ） ＝　ｆ　２　　（（ｉ　＋１）”　　−ｉ”）＋　ｆ　
ｔ　　（（ｉ　＋１）−ｉ）＝　ｆ　２　　（（２ｉ＋
１）＋　ｆ　ｔ＝２ｆ２　ｉ＋ｆ２　　＋ｆ１ −ｅ１　　ｉ＋ｅｏ　＝Ｅ（ｉ）　　　　　　　　　　
−■となる。ただし、 ｅｌ　＝２　ｆ２＝６ｇａ ｅｏ　＝ｆ２＋ｆｔ　＝６ｇａ　＋２ｇ２である。

また、テーブルＥ　（ｉ）は式■から、Ｅ（ｉ＋１）　
−Ｅ（ｉ）＝　ｅ　ｓ　（（ｉ　＋１）−ｉ）−ｅ　ｔ
　・・・■となる。

これらの式から距ｌＥｒを求めると、弐〇から２　Ｅｒ
　＝　（Ｇ　（２ｉ＋２）　−Ｇ　（２ｉ＋１）　）−
（Ｇ　（２ｉ＋１）　−Ｇ　（２ｉ）　）となり、次い
で、弐〇から ２　Ｅｒ　＝　Ｆ　（２ｉ＋１）　−Ｆ　（２ｉ）−ｆ
　ｔ（４ｉ　＋１）　＋　ｆ　＋ ＝３ｇｚ（４ｉ＋’ｌ）＋３ｇｚ　＋２ｇｚ＝６　ｇ３
（２ｉ　＋　１　）　＋２　ｇｚとなる。ここで、ｇｙ
　＝Ａ３　／ｎ”　＋　　ｇｚ　＝Ａｚ　／ｎ”である
から、 Ｅｒ　＝　３　Ａ３（２ｉ　＋１）／　ｎ　３＋Ａｚ／
　ｎ　”となり、ｉ＝ｎのときの距離ＥｒをＥＩｌｌと
すると、Ｅｍ　＝３Ａ、（２ｎ＋１）／ｎ’　＋Ａ、／
ｎ２となる。ｎがある程度大きいと、 Ｅｍ　＝　（３Ａ３＋Ａｔ　）／ｎ”　　　　　−■と
なる。

従って、第３図に示す曲線１０を、多角形で近似する場
合、全曲線区間で距離Ｅｖ以下の精度で近似するには、
当該曲線区間の分割数ｎを、ｎ＝　（ｌ　３Ａ２　＋Ａ
ｔ　　ｌ　／　Ｅｗ＋　）　””　　−＠）となるよう
に定めればよいことになる。

次に、こうして得た分割数ｎによって求まるポリゴンの
各頂点座標Ｇ　（ｉ）の算出は、弐〇〜■から次のよう
に行う。まず、弐〇から、 Ｅ　（ｉ＋１）　＝　Ｅ（ｉ）＋　ｅ　１　　　　　　
　　−・・■ただし、 ｅｏ＝６ｇｇ ｅｌ　＝６　ｇｇ　＋２　［１ となる。これが定数テーブルの第１層となる。

次に、式■から、 Ｆ　（ｉ＋１）　＝　Ｆ　（ｉ）＋　Ｅ（ｉ）　　　　
　　　　・・・＠ただし、 ｆｏ　＝ｇｓ　＋ｇｔ　＋ｇｔ ｆ重＝３　ｇａ　＋２　ｇｚ １２″３ｇｓ となる。これが定数テーブルの第２層となる。

次に、弐〇から、 Ｇ　（ｉ＋１）　＝　Ｇ　（ｉ）　＋　Ｆ　（ｉ）　　
　　　　　　・・・＠ただし、 ｇｏ＝Ａ６ ｇ１°Ａ重／ｎ ｇ２＝Ａ２／ｎ” ｇａ＝Ａａ／ｎ” となる。これが定数テーブルの第３層となる。

従って、各頂点座標Ｇ（ｉ）は第１〜第３層の順に加算
して行くことにより、 Ｇ（ｉ＋３）　＝Ｇ（ｉ＋２）　＋Ｆ（ｉ÷２）＝Ｇ（
ｉ＋２）　＋Ｆ（ｉ＋１）　＋Ｅ（ｉ＋１）＝　Ｇ　（
ｉ＋２）　＋　Ｆ　（ｉ＋１）　＋　Ｅ（ｉ）＋　ｅ　
ｔとなり、１つの頂点座標の算出は３回の加算で済む。

従って、全頂点座標の算出は３ｎ回の加算で済み、演算
回数を大幅に減らすことが出来る。

〔実施例〕

第１図はこの発明をコンピュータ図形処理システムに適
用した場合のシステム構成図である。

第１図において、システムバス１上には、文字コードお
よび文字の輪郭の各区間の座標値が輪郭データとして格
納されている辞書２、中央処理装置（ＣＰＵ）および各
種のラッチ、レジスタ、メモリ等からなるマイクロ・コ
ンピュータ構成の処理部３、第１〜第３の定数テーブル
４ａ〜４Ｃ１出力文字コードや出力文字サイズを指定す
る入力装置としてのキーボード５、ポリゴン化した文字
の輪郭像を格納するビットマツプメモリ６、このビット
マツプメモリ６に格納した文字データを表示する出力装
置としてのデイスプレィ装置７がそれぞれ接続されてい
る。辞書２に格納されている輪郭データは、前述した曲
線１０が３次元ヘゼー曲線の場合、始点Ｐｏ、制御点Ｐ
１およびＦ２、終点Ｐ３の各座標値である。

次に、第２図に示すフローチャートを参照してｍ次元多
項式曲線の一つである３次元ベゼー曲線によって記述さ
れている文字の輪郭の各曲線区間を、ｎ分割して描画す
る場合の動作について説明する。

まず、キーボード５からある文字コードが入力されると
（ステップＳ１）、処理部３は辞書２からこの文字コー
ドに対応する文字の輪郭の各区間の輪郭データを順次読
み出し、内部メモリに書き込む（ステップ３２）。

次いで、処理部３は内部メモリに書き込んだ輪郭データ
の中から最初の曲線区間の輪郭データを読み出し、この
区間の曲線を、所定の要求精度に合わせて分割するため
の最小分割数ｎを求める（ステップ３３）。この分割数
ｎは、前述した式［相］から、 ｎ＝（１３Ａ！　＋Ａ！　　ｌ　／Ｅｓ＋　）””とな
る。ただし、 Ａｓ　＝　（Ｐａ　−Ｐａ　＋３　（ＰＩ　　Ｆ２　）
　）Ａ２　＝−３（Ｐｉ　　Ｐｏ　＋（Ｐ　ｔ　　Ｆ２
　）　）である。Ｅｓ＋は要求精度であり、２５６　Ｘ
２５６画素サイズの場合、０．１程度である。

次に、こうして得た分割数ｎによって得られるポリゴン
の各頂点座標Ｇ　（ｉ）を、前述した式■〜■によって
算出する（ステップＳ４）。このとき、各層における加
算結果を各層毎に設けた３つの定数テーブル４ａ〜４Ｃ
に順次格納し、次の頂点座標の算出のときに使用する（
ステップＳ５）。

次いで、求めた頂点座標をビットマツプメモリ６上に展
開しくステップＳ６）、ポリゴンによる輪郭像を形成す
る。そして、当該曲線区間の全頂点座標の算出が終了す
るまでステップ３４〜Ｓ６を繰り返し、全頂点座標の算
出が終了すると（ステップＳ７）、ステップＳ３に戻り
、次の曲線区間のポリゴン化を同様にして行う。そして
、全曲線区間のポリゴン化が終了すると（ステップＳ８
）、ビットマツプメモリ６上に展開した輪郭像をデイス
プレィ装置７に表示しくステップＳ９）、処理を終了す
る。

なお、前述の実施例において、表示する文字のサイズに
応じて近似精度を変更し、分割数ｎを変化させるように
してもよい。

また、２次元ベゼー曲線のポリゴン化も同様にして行う
ことができる。この場合、式［相］においてＡ８＝０と
置くことによって、分割数ｎは、ｎ＝　　（ｌ　　Ａ２
　１　／Ｅｍ　　）　　”！となる。なお、２次元ベゼ
ー曲線は、始点をＰＯ９制御点をＰ　１　＋　終点をＦ
２とすると、Ｂ（ｔ）’−Ｐｏ　（１ｔ）！＋２Ｐｔ　
（１ｔ）ｔ＋Ｐ２　ｔ”（０≦ｔ≦１） で表される。これを一般の３次元多項式に変形すると、 Ｂ（ｔ）＝　Ｚ（ｔ）＝Ａ２ｔ　”＋Ａ　ｔ　　ｔ　＋
Ａ。

（０≦Ｌ≦１） ただし、 Ａ２　＝Ｐ２　＋ＰＯ−２Ｐ１ Ａｓ　＝２　（Ｐｔ　−Ｐａ　） Ａｏ　＝Ｐ。

となる。

〔発明の効果〕

この発明によれば、文字等の輪郭部の曲線区間をポリゴ
ンで近似する場合、少ない頂点数で高い近似精度を得る
ことができ、また、こうして得た分割数によって生成す
るポリゴンの各頂点座標の演算回数を大幅に減らすこと
が可能となる。

【図面の簡単な説明】

第１図はこの発明を適用したコンピュータ図形処理シス
テムの構成図、 第２図は第１図の動作を説明するためのフローチャート
、 第３図は距離Ｅｒの算出方法の説明図、第４図は定数テ
ーブル、 第５図は１曲線区間の説明図である。 距離Ｅｒの算出 第３図 定数テーブル 第４図

Claims (2)

【特許請求の範囲】
1. （１）ｍ次元多項式で表される所定の曲線区間を、複数
   区間に分割して多角形で近似する際に、上記多角形の隣
   接する頂点Ｐ（ｉ）およびＰ（ｉ＋１）の弦Ｐ（ｉ）・
   Ｐ（ｉ＋１）の中点から弧Ｐ（ｉ）・Ｐ（ｉ＋１）の中
   点までの距離が所定の近似精度となるように上記曲線区
   間の分割数を決定することを特徴とする曲線区間の多角
   形近似方式。
2. （２）前記ｍ次元多項式に対応してｍ層の定数テーブル
   を備え、上記定数テーブルは前記多角形の頂点毎の差分
   により形成されており、下層の定数テーブルから上層の
   定数テーブルへと順次加算して行くことで上記頂点の座
   標を求めることを特徴とする請求項１記載の曲線区間の
   多角形近似方式。