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

こないだから考えてるタブレットでPhotoshopのブラシの線を描いたようなBezier曲線を生成するソフトを作りたいという話に対して、こないだもらった宿題を考えている。今回は

• ベジェ曲線内のX、Y座標の最大値の取得方法

を考えることにする。そのまえに前回やり残したBezier曲線と直線との交点について。

3次Bezier曲線と直線との交点

Bezier Clipping法では凸包の共通部分にあるBezier曲線の一部を切り出す必要がある。このとき曲線と凸包の境界線との交点を求めなければいけない。

一般的なn次Bezier曲線に対しては、また繰り返しによる収束法を使わなければいけない。しかし、一番よく使われている3次Bezier曲線の場合は3次方程式になるので直接求めることができる。

直線の式を

とする。

この式にP(t)を代入して

をtに関して解けばよい。これは3次Bezier曲線の場合、tに関する3次方程式なので解の公式がある。 P(t)の4つの制御点を(x₀,y₀) ．．． (x₃,y₃)とすると式-74は具体的には

となる。 うるさいけどこれは確実。解の公式で3つの解を求める。これは実数係数の方程式なので少なくともひとつは実数解があるが、その3つの解の中から

1. 実数である
2. 0 ≤ t ≤ 1の範囲にある

ものを選ぶ。その解に対応する位置が交点である。

解の公式が面倒だけどこれは繰り返しの収束の心配をする必要が無く、割り算さえ気をつければ数値的にも安定で一番安全。しかも繰り返しのつまらないバグを呼び込むことがないので結局手っ取り早い。

凸包とAABB

前回描いた曲線の制御点の凸包とAABBの違いを見てみる。前回の制御点列のひとつ

を使って制御点も含めて描いたのが図-21である。

図中赤い領域が制御点による凸包で、青い領域がAABBである。AABBは長方形で曲線をちょうど外接している。ふたつの曲線が交点を持つ可能性があるか、それとも確実に無いかを判定するにはAABBの方が効率的なのは明らかである。

Bezier曲線のAABB

AABBの境界のそれぞれの辺は座標軸に平行なので、Bezier曲線の上で座標軸に沿った方向に極値を見つけ、その中から最大値と最小値を求めればいい。極値はBezier曲線の上で座標軸に平行になる位置を探せばいいので、例えばx軸方向に極値をとるパラメータt_mは

を満たす。つまり直交する方の軸に平行になったところがもとの軸の極値に対応する。3次Bezier曲線の場合に書き下してしまうと、制御点列を

とするBezier曲線P(t)の座標軸に沿った方向の極値は

を解いて、tが実数でかつ0 ≤ t ≤ 1の範囲にあるものを選べばよい。2次方程式なので最大で合計4つの点が求まる。これらの点と端点t=0とt=1が、AABBの境界の候補である。

これらの点のパラメータの値をt_nとしてそれに対応する座標を(x_n,y_n)

とするとAABBに対応するそれぞれの座標の区間I_x、I_yを

とすればよい。

本来なら、極値の候補を求めたとき直交する方向の微係数が0になっていないことを確認しておく必要がある。つまり、例えばxの方向の極値として

でなければならない。これは、両方の微係数が同時に0になるところは単に線素dsの長さが0になっているだけで極値とは限らないからである。でも面倒なのでこのチェックをせずに候補に含めてしまってもかまわない。最大最小をとるので最終的にはこの点は取り除かれる。

これでAABBが求まったことになる。

AABBの計算例

最初に出したS字型のBezier曲線のAABBを具体的に計算してみる。 制御点をもう一度書くと

で、式-78と79は

となる。最初の式は意味が無い（y軸の方向には極値はない）ので2番目の式から解は

のふたつとなる。両端を含めて候補の座標は

となる。 それぞれの座標の最大値最小値を求めるとAABBの区間は

となる。

ふう、なんとかなったか。つぎは一番重い曲線のオフセットについて。

コメント 5

こんにちは。

おー！

まさかここまでやっていただけるとは思いませんでした！

大まかな考え方は理解できますが、数学的にきっちりと理解するのに、僕はまだ力が足らないので、勉強せねば。



ところで、オフセットについては、実は多少、情報は持っておりますので（まさかここまでやっていただけると思わなかったので、言いませんでした。）以下に掲載いたします（思考の妨げになるようであれば見ないで下さい。）











〇アンカーポイントは、単純に多角形としてオフセットした位置。
〇ハンドルはオフセットする前の状態と平行。


☆オフセットする前の状態の曲線上から任意の数の任意の点を選択し、その地点の角度に対してオフセットする。
〇ハンドルを伸ばしたり縮めたりして、☆で求めた地点に沿うように調節する。〇何回やってもうまくいかない時は、オフセットする前のやつを二つに分割してやってみる。



自分の言葉で書くとこんな感じです。
by うたひこ (2008-11-12 21:05) 

コメントありがとうございます。内容があまり整理されていないのでわかりにくいようでしたら突っ込んでください。オフセットの問題は結局「Bezierで表現できない曲線をどうやって近似するか」という問題に帰着することがわかってきました。けっこう難しそうです。コメントの内容参考にさせていただきます。ありがとうございます。
by decafish (2008-11-13 08:07) 

ご無沙汰しております。

質問なのですが、
この記事の(78)、(79)はどのようにして解くのでしょうか？
公式があるのならば、その名前だけでもうかがいたいです。

僕がお伺いしたもののうち、
一番簡単に解決できそうなこの記事を
コーディングしてみようと思ったのですが、
やっぱり微積分がネックです(^^;A

考え方自体は記事から（何となく）理解できました。
ありがとうございます。
by うたひこ (2008-12-06 13:09) 

内容が整理されていなくて、冗長だったり舌足らずだったりしてわかりにくくなってしまって申し訳ありません。別記事で導きかたを整理しますので後ほど見てください。まだ全部宿題が終わってないのでもう少しがんばります。
by decafish (2008-12-07 22:52) 

沒有醫生的處方
american pharmacy cialis http://cialisyoues.com/ Sialis
by Buy generic cialis (2018-04-14 06:10)