[發(fā)明專利]一種基于B樣條的插值曲線或曲面的構(gòu)造方法及系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 201810390030.6
• 申請(qǐng)日: 2018-04-27
• 公開（公告）號(hào): CN108804391A
• 公開（公告）日: 2018-11-13
• 發(fā)明（設(shè)計(jì)）人: 蔣莉;王小卉
• 申請(qǐng)（專利權(quán)）人: 湖南農(nóng)業(yè)大學(xué)
• 主分類號(hào): G06F17/16
• 分類號(hào): G06F17/16
• 代理公司: 長沙新裕知識(shí)產(chǎn)權(quán)代理有限公司 43210
• 代理人: 周躍仁

1.一種基于B樣條的插值曲線或曲面的構(gòu)造系統(tǒng)，其特征在于，所述基于B樣條的插值曲線或曲面的構(gòu)造系統(tǒng)包括：

函數(shù)調(diào)配模塊，與伸縮平移模塊連接，用于選取調(diào)配函數(shù)，作連結(jié)各樣條小區(qū)間的兩個(gè)端點(diǎn)的直線以及連結(jié)以及對(duì)應(yīng)的兩相鄰deBoor控制頂點(diǎn)的直線，作各樣條小區(qū)間上的樣條曲線上的點(diǎn)與連結(jié)各樣條小區(qū)間的兩個(gè)端點(diǎn)的直線上的點(diǎn)的差得到增量向量；

伸縮平移模塊，與函數(shù)調(diào)配模塊、曲線生成模塊連接，用于將增量向量通過伸縮后平移到連結(jié)兩相鄰deBoor控制頂點(diǎn)的直線上就得到了各樣條小區(qū)間插值于deBoor控制頂點(diǎn)的插值曲線；

曲線生成模塊，與伸縮平移模塊、中央處理模塊連接，用于對(duì)于三次B樣條曲線，得到調(diào)配函數(shù)用Bézier形式的表示式，構(gòu)造的插值于控制頂點(diǎn)的曲線是三次B樣條插值曲線；對(duì)于四階四次B樣條曲線也可用增量伸縮平移方法，生成了相應(yīng)的插值曲線，其調(diào)配函數(shù)中含有一個(gè)自由參數(shù)，是一個(gè)四階四次B樣條多項(xiàng)式；

插值曲線的構(gòu)造方法包括：

在每個(gè)區(qū)間樣條子區(qū)間[t_i,t_i+1](i＝0,1,2,…,m-1)上，連接B樣條曲線段d(t)的兩個(gè)端點(diǎn)d(t_i)和d(t_i+1)的直線段記為l_i(t)，方程為：

l_i(t)＝(1-Φ_i(t))d(t_i)+Φ_i(t)d(t_i+1),t_i≤t≤t_i+1；

而連接兩相鄰de Boor點(diǎn)d_i和d_i+1的直線段記為L_i(t)，方程為：

l_i(t)＝(1-Φ_i(t))d(t_i)+Φ_i(t)d(t_i+1),t_i≤t≤t_i+1；

L_i(t)＝(1-Φ_i(t))d_i+Φ_i(t)d_i+1,t_i≤t≤t_i+1；

作曲線段d(t)與直線段l_i(t)在區(qū)間[t_i,t_i+1]上的差向量：

δ_i(t)＝d(t)-l_i(t),t_i≤t≤t_i+1；

差向量伸縮，即得αδ_i(t)，α＞0，將其平移，使其起點(diǎn)落在直線段上的對(duì)應(yīng)點(diǎn)處，即得：

d_I(t)＝L_i(t)+αδ_i(t),t_i≤t≤t_i+1,i＝0,1,2,…,m-1；

或?qū)憺椋?/p>

d_I(t)＝[(1-Φ_i(t))d_i+Φ_i(t)d_i+1]+α[d(t)-(1-Φ_i(t))d(t_i)-Φ_i(t)d(t_i+1)]；

t_i≤t≤t_i+1,i＝0,1,2,…,m-1；

函數(shù)Φ_i(t)滿足如下的條件：

Φ_i(t)在區(qū)間[t_i,t_i+1]上具有直到n-2階的連續(xù)導(dǎo)數(shù)；

Φ_i(t_i)＝0，Φ_i(t_i+1)＝1，

得：

Φ_i(t)在區(qū)間[t_i,t_i+1]為單調(diào)增函數(shù)，以避免直線段l_i(t)和L_i(t)出現(xiàn)重結(jié)點(diǎn)；

四階四次B樣條插值曲線的構(gòu)造方法包括：

給定區(qū)間[a,b]的一個(gè)擴(kuò)充分劃：

t_-6≤t_-4≤t_-2≤a＝t₀＜t₁＜…＜t_2i＜t_2i+1＜…＜t_2m-1＜t_2m＝b≤t_2(m+1)≤t_2(m+2)≤t_2(m+3)；

及de Boor控制頂點(diǎn)序列：

d_-1,d₀,d₁,d₂,…,d_m,d_m+1；

區(qū)間[a,b]上以：

{t_-6,t_-4,t_-2,t₀,t₂,…,t_2i,…,t_2(m-1),t_2m,t_2(m+1),t_2(m+2),t_2(m+3)}；

為樣條結(jié)點(diǎn)的四階四次B樣條曲線記為：

其中B樣條基函數(shù)Ω_j(t)的支集上的樣條結(jié)點(diǎn)為：

t_2(j-2),t_2(j-1),t_2j,t_2(j+1),t_2(j+2)，j＝-1,0,1,…,m+1；

在r(t)的基礎(chǔ)上，構(gòu)造一條四階四次B樣條插值曲線r_I(t)，使得它通過諸型值點(diǎn)列{d_k}，即滿足插值條件：

r_I(t_2k)＝d_k,k＝0,1,2,…,m；

連接曲線段r(t)兩端點(diǎn)r(t_2i)和r(t_2i+2)的直線段記為：

連接兩相鄰de Boor點(diǎn)d_i和d_i+1的直線段記為：

調(diào)配函數(shù)ψ_i(t)的表達(dá)式為：

其中e_i0是自由參數(shù)，

中央處理模塊，與曲線生成模塊、曲線平滑模塊、曲線擬合模塊、數(shù)據(jù)存儲(chǔ)模塊、顯示模塊連接，用于調(diào)度各個(gè)模塊正常工作；中央處理模塊的控制方法包括：

步驟一，根據(jù)待驗(yàn)證的程序，生成控制流圖CFG，給CFG中的結(jié)點(diǎn)添加3個(gè)屬性:R插值，S插值和E插值，R插值是結(jié)點(diǎn)可達(dá)的約束條件，判斷一個(gè)狀態(tài)的可達(dá)性；S插值和E插值對(duì)路徑進(jìn)行規(guī)約，加快程序的驗(yàn)證；給CFG的邊添加屬性W；一條邊的W值表示以該邊指向的結(jié)點(diǎn)為根結(jié)點(diǎn)的子圖中，還沒有被遍歷的分支的個(gè)數(shù)；

步驟二，根據(jù)生成的CFG，生成抽象可達(dá)圖ARG，如果沿著一條路徑生成一個(gè)新狀態(tài)s，如果s對(duì)應(yīng)的R插值被滿足，說明狀態(tài)s可達(dá)，繼續(xù)沿著狀態(tài)s遍歷該路徑；否則，狀態(tài)s不可達(dá)，則該路徑終止，遍歷其他路徑；對(duì)于一個(gè)可達(dá)的狀態(tài)s，如果狀態(tài)s對(duì)應(yīng)的E插值被該路徑對(duì)應(yīng)的路徑公式蘊(yùn)含，說明沿著該狀態(tài)存在一條到達(dá)目標(biāo)狀態(tài)的路徑，程序不安全；如果狀態(tài)s對(duì)應(yīng)的S插值被蘊(yùn)含，說明以狀態(tài)為起點(diǎn)的所有路徑都是安全的，不需要沿著狀態(tài)s探索程序；如果狀態(tài)s是可達(dá)的，且E插值和S插值都不被蘊(yùn)含，則繼續(xù)沿著狀態(tài)s遍歷該路徑；

步驟三，在生成ARG的過程中，發(fā)現(xiàn)一條反例路徑，到達(dá)目標(biāo)狀態(tài)，則需要進(jìn)一步判斷反例路徑是否虛假；不是虛假反例，則說明程序是不安全的；否則，根據(jù)虛假反例，細(xì)化模型，分別計(jì)算并更新對(duì)應(yīng)狀態(tài)的R插值，S插值和E插值，執(zhí)行重新生成ARG，直到找到一條真反例路徑或不存在反例路徑；

曲線平滑模塊，與中央處理模塊連接，用于獲取B樣條曲線的平滑曲線；

曲線擬合模塊，與中央處理模塊連接，用于利用RANSAC算法結(jié)合Plucker坐標(biāo)優(yōu)化擬合回轉(zhuǎn)軸空間方程，依賴回轉(zhuǎn)軸線方向?qū)⑷S輪廓點(diǎn)云映射至二維平面，并依據(jù)平方距離最小化法作為度量擬合B樣條母曲線；

數(shù)據(jù)存儲(chǔ)模塊，與中央處理模塊連接，用于存儲(chǔ)B樣條曲線數(shù)據(jù)；

顯示模塊，與中央處理模塊連接，用于顯示B樣條曲線。