【1. Bezier 曲線をN分割する 】 †
1)曲線の全長 totalL を求める
2)N分割した長さ targetL = totalL/n を求める
3)曲線の始端から targetL の長さを与える bezier parameter を順次求める。
4)得られた bezier parameter に従って、N分割する anchor point を追加する。
《 1.1 bezier parameter の扱いについて 》 †
bezier 曲線は anchor point と anchor point に挟まれた一つの区間毎に bezier parameter t( 0 <= t <= 1 )によって定義されます。
プログラム上での bezier parameter の扱い方には、次の二通りを混在させます。 この方がプログラム上のデータハンドリグが楽になるためです。
-当該の曲線区間のみで有効な parameter t( 0 <= t <= 1 )
-全曲線( = 複数の区間で与えられる曲線の集合体 )
に対して定義される bezier parameter t*
曲線の始端の区間( 区間 No. 0 )では t* = t
次の区間( 区間 No. 1 )では t* = t + 1
次の区間( 区間 No. 2 )では t* = t + 2
‥‥‥‥‥‥‥‥‥‥‥‥
区間 No. k では t* = k + t
《 1.2 曲線の全長を求める 》 †
anchor point と anchor point に挟まれた一つの bezier 曲線の区間毎に長さを求めることができます。 曲線の全長を求めるには各区間毎に曲線長を求めてその和を求めます。
一つの区間の bezier 曲線長を求めるのには次の四つの制御点座標が必要です。
p(0)〜p(3):Bezier 制御点座標
p(0):anchor point i
p(1):out handle i
p(2):in handle i + 1
p(3):anchor point i + 1
一つの区間の全長ではなく、bezier parameter t1 〜 t2( 0 <= t1 < t2 <= 1 )で与えられる区間の長さを求めるには、次のように考えます。
区間 t1 〜 t2 の長さ = ( 区間 0 〜 t2 の長さ )-( 区間 0 〜 t1 の長さ )
BL_Length(p, t) ( 1.5項参照 )によって、bezier parameter 0 〜 t で与えられる区間の bezier 曲線長が得られます。
《 1.3 N分割する点の bezier parameter を求める 》 †
/////////////////////////////////////////////////// 曲線の始端から targetL = totalL/n の長さを与える bezier parameter t() を順次求める擬似コード ///////////////////////////////////////////////////
BL_Param(p0, p1, p2, p3, lineL, targetL) ( 1.6項参照 )によって、bezier 制御点座標 p0〜p3 で与える区間( 区間長 lineL )内で、始端から targetL の長さの位置を与える bezier parameter t が返されます。
dim n as integer // 分割数 dim nk as integer // 区間数( 0 基数 ) 開いた曲線:nk = アンカーポイント数 - 2 閉じた曲線:nk = アンカーポイント数 - 1 dim k as integer // 区間 No. を与える index( 0 基数 ) dim blockL(nk) as float // 区間 0〜nk の曲線長を格納 dim totalL as float // 曲線全長 totalL = Sum( blockL ) dim targetL as float // N分割長 targetL = totalL/n dim trgtL as float // 当該区間で N分割点を与える当該区間内での長さ dim p(nk, 3) as vec3 // 区間 k におけるbezier 制御点座標?を p(k, 0) 〜 p(k, 3) の二次元配列に格納 dim tt as float // 当該区間内で N分割点を与える bezier parameter t dim t(n - 2) as float // N分割を与える bezier parameter t* を格納( 最終的に求めるもの ) k = 0 trgtL = targetL for i = 0 to n - 2 if trgtL > blockL(k) then do trgtL = trgtL - blockL(k) k = k + 1 Loop until trgtL <= blockL(k) end if tt = BL_Param(p(k, 0), p(k, 1), p(k, 2), p(k, 3), blockL(k), trgtL) t(i) = k + tt trgtL = trgtL + targetL next
《 1.4 bezier parameter t() に従ってアンカーポイントを追加 》 †
Shade の script では bezier paramert t* を与えてアンカーポイントを追加することができます。
apple script の場合
insert control point at 2.3
によって、区間 2 の bezier parameter 0.3 の位置にアンカーポイントが追加されることになります。
複数のコントロールポイントを順次追加する場合、1.3 で求めた bezier parameter リスト t() の値をそのまま連続して使用することができないことに注意してください。
例えば、t(0) = 2.3, t(1) = 2.6 である場合、
insert control point at 2.3 insert control point at 3 + (2.6 - 2.3)/(1 - 0.3)
あるいは
insert control point at 2.6 insert control point at 2 + 0.3/0.6
としなければなりません。
後者のケースのように、bezier parameter の大きな方から順番にアンカーポイントを追加する方が式が簡単になります。
Reset_T(t() as float) as float() ( 下記参照 )によって、1.3 で求めた bezier parameter リスト t() の順番を逆順に並び替え、スクリプトでの連続追加に直接使用できる値に変換します。
tt = Reset_T(t)
これによって得られた tt() を用いて script command でアンカーポイントを追加します。
apple script の場合
repeat with t in tt insert control point at t end repeat
/////////////////////////////////////////////////// Reset _T(t() as float) as float() の擬似コード /////////////////////////////////////////////////// dim nt as integer // t() の配列サイズ( 0基数 ) dim k as integer // アンカーポイントが追加される区間?No. nt = Ubound(t) // 配列 t() のサイズを求める dim tt(nt) as float // 返り値 k = t(nt) + 1 for i = nt downto 0 if Floor(t(i)) = k then // Floor() は切り捨てを与える関数 tt(i) = k + (t(i) - k)/(t(i + 1) - k) else tt(i) = t(i) k = Floor(t(i)) end if next return tt
《 1.5 BL_Length(p, t) の擬似コード 》 †
BL_Length(p(), t) as float, as float は、制御点座標 p(0)〜p(3) なる bezier 曲線における bezier parameter 0〜t で与えられる区間の線長を返します。
線長を求める数値積分は Simpson の式を用いており、単純な区分求積法に比べて少ない分割数で高い精度の積分値を得ることができます。
Simpson の式の解説についてはここでは詳述しません。
なお、下記の擬似コードの中で、分割数 simpsonN は必要に応じて適当な数字を割り当てます。
一般に、simpsonN が大きくなるほど、より正確な線長が得られますが、計算時間も必要とされます。
むやみに大きな数字を割り当てるのではなく、小さな数から出発して徐々に値を大きくし、計算される線長がどのようなカーブで収束していくかを確認した上で、適当と判断される大きさを採用するといいでしょう。
なお 1.6 項で述べる 線長から bezier parameter を逆算する計算内からは、trial & error によって BL_Length() が繰り返し何度も呼び出されます。
このため simpsonN に不用意に大きな値を与えると、1.6 項の計算に長大な計算時間を要することになってしまいます。
1.6 項での計算における精度と simpsonN との間には関係があり、そのバランスに注意しなければなりませんが、このことについては 1.6 項の中で詳しく述べます。
また返り値として、線長の他に dsdt as float が返されていますが、これは 1.6 項での計算に必要とされるものであり、単に線長を求めるだけであるなら、dsdt を返す必要はありません。
引数
p(0)〜p(3):Bezier 制御点座標
p(0):anchor point i
p(1):out handle i
p(2):in handle i + 1
p(3):anchor point i + 1
t:bezier parameter( 0 <= t <= 1 )
返り値
length as float:bezier parameter 0〜t で与えられる区間の線長
dsdt as float:逆算に必要な係数
dim simpspnN as integer // simpson の式で用いる分割数 dim simpson2N as integer // 実質的な分割数( simpson2N = 2*simpsonN ) dim h as float dim aa, bb as float dim J0, J1, J2, J3 as float dim v as vec3 dim t as float dim length as float // 線長( 返り値 ) dim dsdt as float // 逆算に必要な係数( 返り値 ) simpsonN = ○○( 実験の上決定のこと ) simpson2N = 2*simpsonN h = t/simpson2N dim f(simpson2N) as float for i = 0 to simpson2N t = i*h J0 = -3*(1 - t)^2 J1 = 3(1 - t)^2 - 6*t*(1 - t) J2 = 6*t*(1 - t) - 3*t^2 J3 = 3*t^2 v.x = J0*p(0).x + J1*p(1).x + J2*p(2).x + J3*p(3).x v.y = J0*p(0).y + J1*p(1).y + J2*p(2).y + J3*p(3).y v.z = J0*p(0).z + J1*p(1).z + J2*p(2).z + J3*p(3).z f(i) = Sqrt(v.x^2 + v.y^2 + v.z^2) next aa = 0 for i = 1 to simpsonN aa = aa + f(2*i - 1) next aa = 4*aa bb = 0 for i = 1 to simpsonN - 1 bb = bb + f(2*i) next bb = 2*bb dsdt = f(simpson2N) length = (f(0) + f(simpson2N) + aa + bb)*h/3 return length, dsdt
《 1.6 BL_Param(p0, p1, p2, p3, lineL, targetL) の擬似コード 》 †
BL_Param(p0, p1, p2, p3, lineL, targetL) は、bezier 制御点座標 p0〜p3 で与える区間内で( 区間長 lineL )、始端から targetL の長さの位置を与える bezier parameter t を返します。
与えられた線長から bezier parameter t を逆算するには trial & error の反復計算を用います。
1)初期解 t を仮定し、区間 0 〜 t が与える線長を求める
2)計算された線長と目標とする始端からの線長 targetL との誤差を計算する
3)誤差が許容範囲 allow に収まっているなら、その時の t を答えとして返す
4)許容範囲を超えているなら、bezier parameter t に修正を加えて、再度線長を計算する
5)計算された線長が許容誤差範囲内に収まるまで、この計算を繰り返す
6)誤差が許容範囲内に収まったなら、その時の t を答えとして返す
7)安全のために、繰り返し計算回数に上限 maxN を設けておき、許容範囲内に収まらなくても、計算回数が maxN に達したなら、その時の t を答えとして返す
ここで、許容誤差範囲 allow, 最大繰り返し計算回数 maxN, さらに、このメソッド内から呼び出される BL_Length()( 1.5 項参照 )内で使用される simpsonN、この三つのパラメターは重要であり、その値はバランスがとれるように慎重に定めなければなりません。( 誤差 =|計算された線長 - 目標とする線長|/目標とする線長 と定義します )
一般に BL_Length() において、simpsonN を大きくすればより精度の高い線長が求まります。
一方、線長から bezier parameter を逆算するBL_Param() では、許容誤差 allow を小さくすればより精度は高まります。
このとき、最大繰り返し計算回数 maxN も allow の大きさに応じて調整しなければ意味をなしません。
maxN は無限回の計算ループに落ち込むのを防ぐための安全策ですが、いくら allow を小さくしても頻繁に計算回数が maxN に達してしまえば、それによって得られる解は許容誤差を満足しないものになってしまい、allow の大きさに見合った精度は得られません。
simpsonN を大きくし、allow を小さくして maxN を大きくすれば、理論的には精度の高い解が得られますが、次のことに留意してください。
1)反復計算なので計算時間が多く必要とされる
2)float の精度に起因する丸め誤差以上に、収束計算の仕組みそのものに起因する誤差を含むため解の収束は遅く、誤差を小さくしようとすると必要とされる計算時間が指数関数的に増大してしまう。
3)allow を小さく、maxN を大きく設定して、解の誤差を小さくしようとしても、BL_Length() の中で用いられる simpsonN が小さいと、誤差は大きなままに留まってしまい、場合によっては解が収束しない( 振動を起こす )。 逆に大きすぎれば、必要以上に余計な計算時間を費やすことになる。
このように simpsonN, allow, maxN の値の大きさはバランスよく選ばなければなりません。
実験を繰り返し、途中結果を記録して、各自で見つけて下さい。
そもそもロープ形状を作成するのに、どれくらいの精度があればいいのかを考えて下さい。
いきなり、むやみに高い精度を得ようとしてもなかなかうまくいきません。
最初は低い精度から始めて、バランスのとれた simpsonN, allow, maxN を求め、そこから所要の精度に達するまで、simpsonN, allow, maxN を調整していくというアプローチを採った方がいいでしょう。
引数
p0〜p3:Bezier 制御点座標
p0:anchor point i
p1:out handle i
p2:in handle i + 1
p3:anchor point i + 1
lineL:当該区間の bezier 曲線全長
targetL:始端からの線長( 0 <= targetL <= lineL )
返り値
始端からの線長 targetL の位置を与える bezier parameter t( 0 <= t <= 1)
dim p(3) as vec3 // Bezier 制御点座標 dim alow as float // 許容誤差 dim maxN as integer // 最大繰り返し計算回数 dim dsdt as float // 収束計算用の補正係数、BL_Length() により計算される dim calculatedL as float // bezier parameter 0 〜 t で与えれる区間の線長 BL_Length() により計算される dim t as float // bezier parameter( 返り値 ) p(0) = p0 p(1) = p1 p(2) = p2 p(3) = p3 dsdt = 1 t = targetL/lineL calculatedL = targetL for i = 0 to maxN t = t + (targetL - calculatedL)/dsdt // i = 0 のとき、t = targetL/lineL { calculatedL, dsdt } = BL_Length(p, t) // calculatedL, dsdt を求める if Abs((targetL - calculatedL)/targetL) < allow then return t // 誤差が許容範囲内であった end if next return t // 許容範囲内に収束しなかったが、ここで計算を打ち切る