太さの変わるBezier曲線の生成 - その20

先日突然思い出したかのように再開したタブレットによるBezier曲線の生成。前回からAnti-Grain Geometryというプロジェクトの産物のアルゴリズムをレビューしている。その2回目。

このアルゴリズムは非常にシンプルで、微分や積分などの数学的な手続きを使うこともない。ただし、前回見たようにある点での傾きがその点の位置には無関係で、その前後の点の位置だけで決まってしまうという、かなり決め打ち型のアルゴリズムなので、最初はうまくいくとはとても思えなかった。

オリジナルのサイトの例はすべて閉じた点列に対してスムージングが行われている。これは端のある点列ではその両端の２点に対してこのアルゴリズムが適用できない（線分の中間点が必要だから）ためだと思われる。

閉じてない点列に対しては、端点の隣の制御点は端点と一致しているとすればスプラインの端点の処理(d²y/dx²=0）と同じになるのでそれで問題ないだろう。

図-29にこのアルゴリズムを使って、ランダムに与えた点をBezier曲線で補間した例を示す（これはMathematicaで描いた）。

赤い点が乱数を発生させて作った点で、緑がこのアルゴリズムで生成した制御点、結ぶ曲線がこれらの点を端点と制御点としたbezier曲線である。制御点間の距離の比Kの値は1にしてある。

それほど不自然でもなく、大きな破綻なくスムージングができていることがわかる。単純なアルゴリズムで比較的安定なので、こういうのは悪くない。

この方法でさっきのスプラインでやった例を比較してみる。図-30に図-24とおなじ点列を補間して比べた結果を示す。

青い線がスプラインで赤い線がAGG方式のBezier曲線である。赤い線の方がオーバーシュートはちょっと大きいけれど振動はまったくない。オーバーシュートの形がやっぱり不自然に感じるけど振動しないのはいい。

3次スプラインの振動はある点での微係数の値が全部の点の位置の影響を受けているためで、AGG方式のような前後の2点だけから曲線の形状が決まる局所的なアルゴリズムだと発生しにくい。

もちろん弱点もある。それを指摘する前に、アルゴリズムが簡単なのでちょっと実装の話に突っ込んでみる。NSBezierPathとの相性を見てみよう。