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

こないだから考えてるタブレットでPhotoshopのブラシの線を描いたようなBezier曲線を生成するソフトを作りたいという話。ここんとこ仕事が忙しいながらも、とびとびの点列として得られたタブレットの位置を内挿したなめらかなBezier曲線をどうやって作り出すかということに悩んでいる。参考のためにスプライン補間を考えてみる。

スプラインによる補間

Bezier曲線は滑らかな曲線を表現するために使われることが多い。しかし折れ線を補間するためにはあまり使われず、普通はスプライン関数が使われる。最終的にBezier曲線で描画できないといけない（Cocoaで最も簡単なNSBezierPathが使えなくなってしまう）のでどっちみち普通のスプラインは使えないけど、アイデアは使えるかもしれないのでレビューしてみる。

スプライン関数は、 とびとびの点列x_nに対する値y_nが与えられたとき、x_nで区切られた区間I_n=[x_n,x_n+1]ごとの多項式

で前後の区間とは

のようにつながっている。ここで

である。つまり、二つの区間のつなぎ目でなめらかにつながるようにする。それぞれのスプライン関数が例えば3次の多項式

なら2階微分までの値をつなぐ。3次のスプラインの場合、点の数がN+1として区間の数はN、決定する係数の数は4N個ある。中間の各点(x_n,y_n)で式が4つ（固定点（二つ）と1、2階微分）の方程式があり、両端（(x₀,y₀)と(x_N,y_N)）では2階微分が0になるとすると式の数は4(N-1)+2+2=4Nでちょうど係数の数と合うので一つに決められる。

スプライン関数はとびとびの点をなめらかにつなぐけど、かならずしも「自然ななめらかさ」とは言えない場合がある。

例えば図-16のような最初が0で次から1の高さの点列を考える。

これを3次のスプライン関数で補間してみると、図-17の曲線のようになる。

この高さが1付近を拡大してみたのが図-18である。

このようにオーバーシュート（行き過ぎ）があってそのあと振幅は小さくなりながらも、ずっと振動を続けている。 これを自然と見るか、不自然と見るかは感覚の違い（ワイル・E・コヨーテの目の前でロードランナーがびよよょょん、と止まる）もあるけど、データを補間するという意味では好ましくない挙動だと僕は思う。Mathematicaのマニュアルでもグラフ表示は「あえて補間しない」とどこかに書いてあったのはこういうことなのかもしれない。

ひとつ目以外同じ値にすぎないのに、オーバーシュートや振動ははそれを見誤らせる。

ということで、今回のスムージングもこういう勝手なオーバーシュートや振動が続くような補間にはしたくないのでスプラインのように単純に微係数をつなぐだけのやり方はやっぱりやめることにするけど、この数学的な見通しの良さ、簡単さは見習いたい。さてどうするか。うーん、どないしょ．．．

コメント 5

はじめましてこんにちは。
グラフィックデザイナをしているうたひこです。

非常に興味深く拝見しました。
なぜなら僕も、windowsのvisualBasicという言語で
ドローソフトを作ってる最中でして、
ゆくゆくはdecafishさんの考えてらっしゃるような
ペンツールも実装したいと考え、
ちょこっとテストプログラムを書いたりしてたとこだったからです。

僕は高校数学がおろそかなので数式は苦手なんですが、
僕の開発環境の方では、スプラインを書くのに
それほど手間はかからず、
また、スプラインをベジェに変換するのも
それほど苦ではなかったり。

参考までに
http://mt.azimech.net/

（ベジェをうまくオフセットすればいいんじゃないですかね？
だめですかね。）

by うたひこ (2008-11-06 20:50) 

コメントありがとうございます。おっしゃる通り「うまくオフセットする」ことができれば私の目的達成です。数学的に明快な形でどうするかに悩んでいます。紹介していただいた先のソフトは参考になります。私はWindowsを持っていないので動作を確認できないのですが、最終結果がIllustratorで編集可能なベクトル線画が出力できるならまさしく私のやりたいことです。太さ編集モードを持つというのは面白いです。ところで「スプラインをベジェに変換する」というのはどうやるんでしょうか？
by decafish (2008-11-07 08:07) 

お返事ありがとうございます。

スプラインとベジェの変換は、
開発環境（ライブラリ）に依存する方法をとっており、
cocoaに応用できるであろう形での説明はできません。

具体的には、
まず図形の外形線を示すクラス
（http://msdn.microsoft.com/ja-jp/library/system.drawing.drawing2d.graphicspath(VS.80).aspxをご参照下さい）
に、スプライン図形データを追加するように命令します。

このクラスは内部で全ての図形データをベジェとして管理しているので、
スプライン図形の追加命令をした時点で、
内部でベジェに変換されます。

変換されたその情報を拾い出すことで、
スプラインとベジェの変換を行っています。

その様子についての画像を後ほどお目に掛けようと思います。
（decafishさんの数学力ならば、
　より具体的なアルゴリズムに
　辿り着けると踏んで。）


以下はアルゴリズムについて、
変換されたデータを見た限りの僕の分析です。
（イラレについてある程度の理解があることを前提で書きます）

・スプラインを描くために指定する複数の点座標が、
　そのままベジェのアンカーポイントになる。
・両方のハンドルは、同じ長さのスムースポイントになる。
・その長さは、スプラインを描く際の重み係数に比例する。
・その角度を求めるには、スプラインを描くアルゴリズムを
　よく理解しないとわからなそう
　（前後の二つの点座標と関わりのある多項式になりそう）
・高校数学がわからないので、これ以上はわからない

ざっとこんなところです。
by うたひこ (2008-11-07 17:51) 

丁寧なご回答ありがとうございます。つい、わからないことは知ってる人に訊いてしまおうと安易に考えてしまって、お手数をかけしてしまって申し訳ありません。
なんとなく方向性はわかりましたが、どうすればいいのかまだわかりません。じっくり自分で考えてみます。結果が出たら、またここにまとめます。これからも時々覗いてみてください。よろしくお願いします。
by decafish (2008-11-07 21:51) 

いえいえ、僕には数式を解く力がないので、具体的にコード化できる力をお持ちの方とお話できないか探していたのです。そういった面では、同じ課題に取り組んでいらっしゃることは大変心強いです。

（数式を解く以外で）協力できることがあれば、出来る限り協力しますよ。



また、僭越ながら、
〇ベジェ曲線同士の交点の取得方法
（ベジェ図形のブーリアン演算に必要）
〇ベジェ曲線内のX、Y座標の最大値の取得方法
（バウンディングボックスの取得に必要）
〇ベジェの（単純な）オフセットの方法

について、もし何かご存知でしたらお教え下さい。
（興味の方向が似ているかもしれないので、もしかしたらご存知かもと思い、お伺いしてみました(;^_^A）
by うたひこ (2008-11-07 23:44)