太さの変わるBezier曲線の生成 - その19 [考え中 - 太さの変わるBezier曲線]
何ヶ月ぶりかの続き。前回はじつに正月明けだった。その後忘れていたわけではなく、「優雅な白鳥も水面下では一所懸命水をかいているように」地道に勉強していたのであった。
タブレットから得られる情報は、Viewの上での2次元の位置の配列だけである。この点列からなめらかな曲線をどううやって得るか、つまり補間するにはどうするか、ということを考える。
ずいぶん前にスプラインを使うことを考えたけど、結局振動が起こるのがいやで諦めた。
ではどうするか。曲率にもとづく考え方をもう少し進めようかとも思ったけど、どう考えても膨大な計算が必要になる。厳密な曲率ではなく、計算量の少ない曲率に近い量を定義してそれに基づくか、といろいろいじっていたがなかなかいいアイデアが浮かばない。
そうしているうちに、全く違うアプローチでBezier曲線で補間する方法を紹介しているサイトを見つけた。そのレビューをしてみる。
スプラインの改良
"Bezier", "interpolation"でググってみるといろんな人がいろんなことをやっていることがわかる。例えば、Cubic Bezier 4-point Interpolationのひとは中間の2点を通るBezier曲線を生成するアルゴリズムを作った。4点を与えると両端と中間2点を通る3次のBezier曲線を作る。未知数の数と式の数はあっているのでできそうな気もするけど簡単には解けない。どうやってるのかよく理解できない(Hermite曲線なるものを途中で使うらしいけどよくわからない)。
さらに「Spline with Tension」とか「Akima(秋間)Spline」とかいうのがヒットする。 ただし、これらは専門の雑誌に発表されているだけで、内容にアクセスするのが難しい。雑誌を購読するか、その方面の学科のある大学の図書館にでもいかないと手に入らない。
周辺情報からどうやらこれらも普通のSplineでは振動が起こるのを回避しようと言うもののようで、「Spline with Tension」はTension(張力)と言うパラメータを定義してSpline曲線の曲がり具合を調整するものらしい。また「Akima Spline」はふたつの点の間の補間曲線は、普通のSplineでは全部の点の影響を受けるが、それを局所的に決定する、というものらしい。どちらも詳細は論文の内容を見るしかないが、僕みたいな素人にはなかなかたどり着けない。もし知っている方がいたらコメントしてくれるとうれしい。
そういうのとは別に、素人でもわかる面白いのがあった。Interpolation with Bezier Curvesではとても簡単なアルゴリズムで与えられた点列を3次のBezier曲線でスムージングするというもの。
これは非常に不思議で、簡単でしかもいい加減なやり方なのに結構うまくいく。ちょっとこのアルゴリズムを見てみる。
AGG方式
このアルゴリズムはAnti-Grain Geometryというプロジェクトのうちのひとつらしいので、仮にAGG方式と呼ぶことにする。
まず与えられた点列のうち、ひとつの点に注目する。それを図-25のようにPとする。注目したその点の前後の点をそれぞれP-、P+とする。
このアルゴリズムではまず、図-26のようにそれぞれの点を結ぶ直線の中間点M-とM+を求める。次に、二つの中間点M-とM+を結ぶ線上で、元の点の距離L-とL+の比に按分する点Bを求める。
つまり、図-27にあるように となるように点Bを決める。それから点BがPと重なるようにM--B-M+を移動させる。このときM--M+の長さを適当にK倍してもよいとオリジナルサイトでは言っている。
このM-とM+の位置を端点Pの前後の3次Bezier曲線の隣の制御点とする。たったこれだけである。B点は案分点なので
ただし、ここでBやM-などはは点B、M-の2次元座標を表すとする。従って制御点C-とC+は
となる。ここで である。注目する点を次にP+へ移して同じことをしていけば内挿3次Bezier曲線がひとつ決まる。
式-95を見ればわかるようにこのアルゴリズムではPでの傾きはPの位置によらずP-とP+の相対位置だけで決まる。
M-とM+はどちらも中点なので、ベクトルM-→M+(=M+-M-)はベクトルP-→P+と平行で長さは半分である。
そう考えると不自由な感じがして、点列の並び方によっては不自然になって、そんなのダメだろ、と思えるけど、実際に描いて見るとあんがいそうでもない。
次回はもう少し具体的な話に。
AGGの「Interpolation with Bezier Curves」のリンクが間違っていました。
修正しました。
by decafish (2009-05-15 08:06)
さらに自己ダメ出し。式-94と式-95が間違ってました。足し算引き算の間違い。小学生以下。修正しました。
by decafish (2009-05-15 21:43)