3.4 曲線的弧長(zhǎng)參數(shù)化[3]

有了路徑，還需要能夠方便地在路徑上勻速運(yùn)動(dòng)，其他運(yùn)動(dòng)可以由勻速運(yùn)動(dòng)變化和復(fù)合得到。從樸素的需求角度出發(fā)，我們希望曲線的參數(shù)t與曲線的長(zhǎng)度L為線性關(guān)系：

此時(shí)，我們可以僅通過(guò)參數(shù)t的勻速變化得到點(diǎn)在曲線上的勻速移動(dòng)。顯而易見(jiàn)，這個(gè)關(guān)系只有直線自然成立。

對(duì)于大于一次的多項(xiàng)式曲線，這里采用如下處理方式。

設(shè)為連接點(diǎn)的曲線，其在間的長(zhǎng)度為L；另設(shè)參數(shù)u，建立和曲線長(zhǎng)度的線性關(guān)系：

即由參數(shù)u表達(dá)的曲線長(zhǎng)度計(jì)算函數(shù)；設(shè)一個(gè)參數(shù)u到參數(shù)t的變換t(u)，且滿足t(0)=0, t(1)=1。將變換帶入曲線參數(shù)方程中，可以得到一個(gè)新的曲線參數(shù)方程：

由于的長(zhǎng)度函數(shù)為，在此變換下對(duì)應(yīng)的長(zhǎng)度函數(shù)應(yīng)有

從而變換為

為得到變換，需要求出的反函數(shù)。

由于沒(méi)有解析解，這里采用最小二乘法進(jìn)行擬合求近似解。

（1）在[0,1]區(qū)間進(jìn)行等曲線長(zhǎng)度的劃分，得到n條等長(zhǎng)曲線段，對(duì)應(yīng)的參數(shù)區(qū)間為。

（2）對(duì)每一條曲線段，采樣m個(gè)在該區(qū)間的值，得到點(diǎn)集,…,，其中,。

（3）以長(zhǎng)度為自變量，用最小二乘法擬合滿足采樣點(diǎn)的多項(xiàng)式方程，得到在區(qū)間的近似解。

（4）在剩余的區(qū)間重復(fù)步驟2和步驟3，求出在所有區(qū)間的近似解，則組成的分段函數(shù)。

步驟1劃分等曲線長(zhǎng)度區(qū)間的目的是消除使用時(shí)查找分段函數(shù)表的遍歷操作。當(dāng)使用三次多項(xiàng)式作為擬合的基函數(shù)時(shí)，其系數(shù)可以用Vector4保存，則的分段函數(shù)可以保存為Vector4的數(shù)組Vector4[n]。對(duì)于給定的長(zhǎng)度l，在等曲線長(zhǎng)度的劃分下，其對(duì)應(yīng)的分段函數(shù)的系數(shù)索引為Clamp((int)((l/L)*n),0, n-1)。如果是其他形式的不滿足等曲線長(zhǎng)度的劃分，則需要額外記錄每個(gè)劃分的長(zhǎng)度，在使用時(shí)遍歷Vector4[n]找到l對(duì)應(yīng)的分段函數(shù)的系數(shù)。

在步驟1使用等曲線長(zhǎng)度區(qū)間劃分時(shí)，由于此時(shí)尚未求出，只能使用迭代法尋找等長(zhǎng)劃分點(diǎn)。這里使用Newton-Raphson法[4]來(lái)求解方程：

其迭代形式為

其中，A、B、C 參見(jiàn)“端點(diǎn)間二次樣條的構(gòu)建”。為嚴(yán)格單調(diào)函數(shù)，適合使用Newton-Raphson法。可以將同樣劃分?jǐn)?shù)量下同序號(hào)的等參間隔點(diǎn)作為迭代的初值t i(0)以加速收斂。

構(gòu)造的計(jì)算量分析如下：

（1）尋找等曲線長(zhǎng)度的劃分點(diǎn)，默認(rèn)最大迭代次數(shù)為10，在實(shí)際計(jì)算過(guò)程中到不了這個(gè)次數(shù)就會(huì)收斂。n個(gè)劃分需要求解n-1個(gè)劃分點(diǎn)，總迭代次數(shù)≤10(n-1)。

（2）對(duì)每條曲線段進(jìn)行m次的采樣，排除兩個(gè)已經(jīng)計(jì)算的端點(diǎn)，總的調(diào)用次數(shù)為n(m-2)。

（3）在最小二乘法擬合部分，設(shè)Kp為擬合多項(xiàng)式的階數(shù)，則構(gòu)造方程系數(shù)矩陣的復(fù)雜度為，用高斯消元法求解部分的復(fù)雜度為。

（4）的計(jì)算不受剛體變換的影響，不需要針對(duì)剛體變換重新計(jì)算。

項(xiàng)目中，n=20,m=11,，連接兩個(gè)路點(diǎn)的曲線需要用80個(gè)浮點(diǎn)數(shù)表示。如果需要運(yùn)行時(shí)動(dòng)態(tài)構(gòu)建曲線，為避免計(jì)算量過(guò)大造成卡頓，可以采用分幀計(jì)算的方法將計(jì)算量分?jǐn)偟蕉鄮?。注意到每段路徑之間沒(méi)有相互依賴(lài)，只共享路點(diǎn)信息，也可以采用多線程并行計(jì)算。另外，根據(jù)項(xiàng)目情況也可以適當(dāng)降低分段數(shù)目和采樣點(diǎn)數(shù)目。

將表示的帶入原曲線方程中，得到新的歸一化曲線方程：

其對(duì)應(yīng)的長(zhǎng)度計(jì)算為

對(duì)于使用弧長(zhǎng)參數(shù)化后的曲線方程gs(u)，其求值的計(jì)算比原始的曲線方程fs(t)多一次多項(xiàng)式求值的計(jì)算（具體而言，使用三次多項(xiàng)式擬合，多了3次加法、5次乘法、1次除法），但是對(duì)應(yīng)的長(zhǎng)度計(jì)算大幅簡(jiǎn)化，只需要1次乘法。

弧長(zhǎng)參數(shù)化后的曲線方程gs(u)與原始的曲線方程fs(t)在等參取點(diǎn)時(shí)的對(duì)比如圖3.3所示。

圖中上面的為原始曲線，下面的為弧長(zhǎng)參數(shù)化后的曲線，重參數(shù)化后，等參對(duì)應(yīng)曲線上的等距。