円弧近似エンジン - GeoComputing.jp

本システムは、SVGファイルのパス中の3次ベジェ曲線部分をarc spline (連続した円弧)に近似置換するシステムです。

円弧近似エンジンに関して

1. ベジェ曲線から円弧(arc spline)への変換

カッティングマシンやCNC機械では、直線と円弧の入力を受け付けるものが多いですが、設計のツールでは円弧でなく3次ベジェ曲線などのパラメトリック曲線で設計されることも多々あります。それ故に、フォーマット変換の際に、パラメトリック曲線の円弧近似の変換が必要とされました。円弧近似の研究が進む前には、パラメトリック曲線をポリライン化した上で処理をしていましたが、データ量が増大することと、曲線の滑らかな接続が失われることがネックになっていました。

2. 効果的な変換手法の登場

90年代にD.S. Meek, D.J. Walton著の「Approximating smooth planar curves by arc splines」(Journal of Computational and Applied Mathematics 59 (1995) 221-231)にて、3次以上のベジェ曲線に対する円弧近似の効果的な変換手法が提示されました。

Meekの手法のおおまかな流れは以下のようなものです。

  1. ベジェ曲線を、連続し、変曲点がなく、曲率が単純増加する、つまり、螺旋曲線のパーツに分割する。
  2. 螺旋曲線の始点と終点における曲率半径を持つ2つの円弧で始点と終点を結んだ三日月型の領域に、その螺旋曲線とbiarcは内包されるので、そのbiarcと螺旋曲線の最大距離は必ず三日月型の領域の最大距離以下になる。(※ biarcの2つの円弧の接続箇所は適宜に決める。)
  3. 三日月型の領域の最大距離が許容範囲以上だった場合は、上記2の三日月型領域の最大距離が許容誤差以内になるまで、螺旋曲線を半分の長さで再度分割する。(三日月領域の最大距離が許容範囲内に収まるまでこの再帰を行う。)

Meekの論文では、螺旋曲線の分割箇所として、曲線の長さの半分の箇所と書いていますが、Aleksas Riškus著「APPROXIMATION OF A CUBIC BEZIER CURVE BY CIRCULAR ARCS AND VICE VERSA」では、ベジェ曲線の導関数の変数t [0.0 - 1.0]に対して、t=0.5を取る点で分割する手法が書かれており、本サービスでもt=0.5での分割を行っています。

また、biarcの2つの円弧の接続箇所に関しては、本サービスでもAleksasの論文同様に、螺旋の両端の2点と螺旋両端の接線の交点の3点で形成される三角形の内心点をbiarcの接続箇所としています。

螺旋曲線がどのようなパラメトリック曲線であれ、始点と終点で螺旋曲線と同じ接線を持つbiarcでは、biarcと螺旋曲線の最大誤差は三日月型領域の最大距離以下になるということの証明が、Meekの論文の最大のポイントです。(Meekの証明では、更に、最大誤差は三日月型の領域の最大距離の13.5分の1になると書かれています。)Meekの論文のこの証明を用いない場合、パラメトリック曲線とbiarcの最大誤差の計算のために、例えば、3次ベジェ曲線の場合、12次以上の多項式の求根プログラムを走らせる必要が出てきますが、この計算の計算コストが高すぎることがMeekの手法で最大誤差を代替することの大きな理由です。