So-net無料ブログ作成

太さの変わるBezier曲線の生成 - その10 [考え中 - 太さの変わるBezier曲線]

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

スプラインによる補間

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

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

1105eq70.png
で前後の区間とは
1105eq71.png
のようにつながっている。ここで
1105eq72.png
である。つまり、二つの区間のつなぎ目でなめらかにつながるようにする。それぞれのスプライン関数が例えば3次の多項式
1105eq73.png
なら2階微分までの値をつなぐ。3次のスプラインの場合、点の数がN+1として区間の数はN、決定する係数の数は4N個ある。中間の各点(xn,yn)で式が4つ(固定点(二つ)と1、2階微分)の方程式があり、両端((x0,y0)と(xN,yN))では2階微分が0になるとすると式の数は4(N-1)+2+2=4Nでちょうど係数の数と合うので一つに決められる。

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

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

1105fig16.png
これを3次のスプライン関数で補間してみると、図-17の曲線のようになる。
1105fig17.png
この高さが1付近を拡大してみたのが図-18である。
1105fig18.png
このようにオーバーシュート(行き過ぎ)があってそのあと振幅は小さくなりながらも、ずっと振動を続けている。 これを自然と見るか、不自然と見るかは感覚の違い(ワイル・E・コヨーテの目の前でロードランナーがびよよょょん、と止まる)もあるけど、データを補間するという意味では好ましくない挙動だと僕は思う。Mathematicaのマニュアルでもグラフ表示は「あえて補間しない」とどこかに書いてあったのはこういうことなのかもしれない。

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

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


nice!(0)  コメント(5)  トラックバック(0) 

nice! 0

コメント 5

うたひこ

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

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

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

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

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

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

decafish

コメントありがとうございます。おっしゃる通り「うまくオフセットする」ことができれば私の目的達成です。数学的に明快な形でどうするかに悩んでいます。紹介していただいた先のソフトは参考になります。私は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) 

decafish

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

うたひこ

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

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



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

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

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

トラックバック 0