Shade3D 公式

08 Bezier line 等分割 [ Shade Labo ]


#1

関連記事
  • 06 Bezier line 基礎
  • 07 Bezier line 長さ

08 - 1 長さを等分割


bezier line の長さを等分割するには、Shade script の関数 calculate_parameter( ) を用いるのが簡単です。

これは全長を 1 に規格化した距離パラメータ 0~1 に対応する bezier parameter を求める関数で、得られる parameter も全区間に対して 1 に規格化されています。

次の script では Shade 上で選択された線形状を 8 分割する点にポイントを追加します。


[ script 08 - 01 ]     Shade 上で線形状を選択して実行

import math

n = 8		#  分割数

scene = xshade.scene()
ob = scene.active_shape()
ob.copy_object(None)
ob2 = ob.bro	
	
k = ob2.number_of_control_points
if not ob2.closed :
	k = k - 1

p = []
for i in range(1, n) :
	t = i/float(n)
	t = ob2.calculate_parameter(t)*(k + i - 1)
	ob2.insert_control_point(t)
	p.append(math.ceil(t))		#  追加されたポイントの番号
	
ob2.activate()
ob2.active_vertex_indices = p	#  追加されたポイントを選択
scene.enter_modify_mode()

#2

08 - 2 Bezier line 諸量と bezier parameter


長さを N 分割、あるいは指定する長さ位置での bezier parameter を求めるのは calculate_parameter( ) を用いれば簡単にできます。

しかし、自由曲面上で求めた任意の線形状を対象とした場合、calculate_parameter( ) を実行するには、その線形状を一旦 Shade 上に作成しなければなりません。

また長さだけではなく、後述する 滑らかな掃引 を求める際には 曲がり具合の分割 という計算が必要とされます。


          [ fig 08 - 01 ]


ここでは 長さ や 曲がり具合 等の bezier line 諸量に対して、任意の量に対する bezier parameter を求める方法を紹介します。

大まかな流れは次のようになります。

  • 数値積分を求める labo.bezier_simpson( ) によって、bezier line 諸量を求める ( [ script 07 - 02 ] 参照 )
  • Newton 法により、所要の bezier line 諸量 を与える bezier parameter を求める

#3

08 - 3 Newton 法


関数 f(x) に対し、f(x) = 0 なる x の値を収束計算により求める数値解析手法の一つです。
1)最初に近似解 x を与えて f(x) を求める

2)f(x) が十分に 0 に近い値であれば x が求める解であるとみなす

3)そうでなければ、第二近似解を p, f(x) , f ‘(x) から求め、2)の判定に戻る

                    [ 式 08 - 01 ]

指定する精度を持った解が求まるまで 2)と3)を繰り返します。

無限ループに落ち込むのを防ぐため、反復計算の最大回数を指定しておき、最大回数計算しても収束しなければ、「 解が求まらない 」あるいは「 精度の落ちた解しか求まらなかった 」とみなします。


これを N 分割に適用すれば次のようになります。

  • x : 目標とする長さを与える bezier parameter

  • f(x) = 数値積分で得られた長さ - 目標とする長さ ( = 0 になればよい )

  • f(x) の導関数 f’(x) は数値積分での被積分関数


最初に与える近似解の選定が重要で、この選定を間違えれば収束しないこともあります。

距離パラメータから bezier parameterを求める場合、距離パラメータを最初の bezier parameter 近似解 とすれば、必ず解が求まります


#4

08 - 4 Newton 法により N 分割


次の script では、Shade 上で選択された線形状を 8 分割する点を追加します。

滑らかな掃引を求める際に曲線の曲がり具合を N 分割する bezier parameter を求める計算では、次の4つが異なりますが同じ手法が使われます。

  • 数値積分での最大分割数 simpsonN
  • Newton 法での収束判定しきい値
  • Newton 法での収束計算打ち切り回数
  • 被積分関数

[ script 08 - 02 ]     Shade 上で線形状を選択して実行
import math
import labo


#    入力
n = 8				#  分割数
allow = 0.000001	#  Newton 法での収束判定しきい値	
maxN = 50			#  収束計算打ち切り回数



#	コントロールポイント座標 list bz で与えられる bezier 曲線の
#	パラメータ t における微分ベクトルの絶対値を返す
def bezier_abs_derivative(bz, t) :
	v = (-3*(1 - t)**2)*bz[0] + 3*(1 - t)*(1 - 3*t)*bz[1] + 3*t*(2 - 3*t)*bz[2] + (3*t**2)*bz[3]
	return v.abs()

	

scene = xshade.scene()		

#  線形状全データ取得			bZs = [bz, bz, bz, …]   bz = [vec3, vec3, vec3, vec3] transposed
bZs = labo.get_bezier(xshade, -1)

						
# total, brL, sL
total = 0	#  Bezier line 全長
bcL = []		#  各ブロック毎の線長
sL = [0]		#  全長を 1 に規格化した時の各ブロックまでの累積長さ
	
for bz in bZs :
	r = labo.bezier_simpson(bezier_abs_derivative, bz, 0, 1)	#  parameter 区間 0~1 で線長を求める
	total += r
	bcL.append(r)
	sL.append(total)
m = len(sL)
for i in range(m) :
	sL[i] /=total
		
		
#  dL : n 分割点の距離パラメーリスト
#  dL[i] = 2.36 ならば、bLs[2] の 距離 0.36 (各ブロック毎の規格化距離) の点が分割点
dL = []
k = 1
for i in range(1, n) :
	a = i/float(n)
	while a > sL[k] :
		k += 1
	else :
		dL.append((k - 1) + (a - sL[k - 1])/(sL[k] - sL[k - 1]))	
			
			
#  Newton 法により、距離パラメータリスト dL から bezier parameter リスト tL を求める	
tL = []					#  bezier parameter リスト
for d in dL :
	k = int(d)
	t = d - k
	bz = bZs[k]
	target = t*bcL[k]	#  bcL : 各ブロック毎の線長
	
	p = t				#  反復計算のための初期値
	calculated = target	#  反復計算のための初期値
	d = 1				#  反復計算のための初期値

	for i in range(maxN) :
		p = p + (target - calculated)/d
		calculated = labo.bezier_simpson(bezier_abs_derivative, bz, 0., p)	#  parameter 区間 0~p で線長を求める
		d = bezier_abs_derivative(bz, p)								#  parameter p における微分ベクトル
		if abs(target - calculated)/target < allow :
			break							

	tL.append(k + p)
		

#  parameter tL の場所に、ポイント追加
ob = scene.active_shape()
ob.copy_object(None)
ob = ob.bro
	
tL.reverse()				#   tLのリスト順を逆順に
	
prev_k = -1
for p in tL :
	k = int(p)
	t = p - k
		
	if k == prev_k :		#  前回追加したのと同一の区間 ( block_No ) においてポイントが追加される場合、	
		s = t/prev_t
	else :
		s = t
		prev_k = k			#  前回の追加区間として記憶	
	prev_t = t				#  前回の追加パラメータとして記憶
					
	ob.insert_control_point(k + s)
	
ob.activate()
scene.enter_modify_mode()

#5

08 - 5 bezier parameter による分割


[ script 08 - 02 ] での最後の部分 bezier parameter を格納した tL からポイントを追加する操作についての補足です。

一つの bezier line 区間に bezier parameter t = 0.2, t = 0.6 の二カ所にポイントを追加するとします。

最初に Shade script で insert_control_point( 0.2 ) としてポイントを追加した場合、次の追加ポイントの bezier parameter は簡単な比例配分で求められます。

          t = ( 0.6 - 0.2 ) / ( 1 - 0.2 ) = 0.5     [ 式 08 - 02 ]


          [ fig 08 - 02 ]


[ script 08 - 01 ] で使用した calculate_parameter( ) で得られた parameter を使用する場合とは異なっていることに注意して下さい。