Three.js Interpolant實現動畫插值

2023-02-12 06:00:11

Interpolant

這個類主要是用來實現插值，常用於動畫。

可以把這個類理解為是一個數學函數，給定一個自變數，要返回對應的函數值。只是，在我們定義函數的時候，是通過一些離散的點進行定義的。

舉個例子，加入我們要定義y = x^2這條曲線，我們需要定義兩個陣列（即取樣點和取樣的值）：x = [-2, -1, 0, 1, 2]，y = [4, 1 ,0, 1, 4]。通過這樣的定義方式，我們怎麼求不是取樣點中的函數值？例如上面的吱吱，我們怎麼求x = 0.5時的值？這就時我們要說的“插值”。

最常見也最簡單的插值方式就是線性插值，還拿上面的例子講，就是在“連點”畫圖象的時候，用直線把各點連起來。

我們現在要取x=0.5，通過(0,0)和(1,1)線性插值，即求出過這兩點的直線y=x，可以得到，y=0.5；同理，x=1.5時，通過(1,1)和(2,4)的直線為y=3x−2，可以得到，y=2.5。

我們使用three.js提供的線性插值驗證一下：

import * as THREE from 'three'
const x = [-2, -1, 0, 1, 2]
const y = [4, 1, 0, 1, 4]
const resultBuffer = new Float32Array(1)
const interpolant = new THREE.LinearInterpolant(x, y, 1, resultBuffer)
interpolant.evaluate(0.5)
// 0.5
console.log(resultBuffer[0])
interpolant.evaluate(1.5)
// 2.5
console.log(resultBuffer[0])

看不懂這段程式碼沒有關係，接下來會慢慢解釋。

通過離散的取樣點定義曲線

在Interpolant的構造器，需要以下這些引數：

parameterPositions：取樣的位置，類比成函數就是自變數的取值

sampleValues：取樣取的值，類比成函數就是自變數對應的函數值

sampleSize：每個取樣點的值，分量的個數。例：sampleValues可以表示一個三維空間的座標，有x, y, z三個分量，所以sampleSize就是三。

resultBuffer：用來獲取插值的結果，長度為sampleSize時，剛好夠用。

這幾個引數一般有著如下的數量關係：

通過上面這些引數，我們就可以大概表示一個函數的曲線，相當於在使用“描點法”畫圖象時，把一些離散地取樣點標註在座標系中。

有了這些離散的點，我們就可以通過插值，求出任意點的函數值。

插值的步驟

1. 尋找要插值的位置

還拿上面的例子來說，parameterPositions = [-2, -1, 0, 1, 2]，現在想要知道position = 1.5處的函數值，我們就需要在parameterPositions這個陣列中找到position應該介於那兩個元素之間。很顯然，在這個例子中，值在元素1，2之間，下標在3,4之間。

2. 根據找到的左右兩個點，進行插值

上面的例子中，我們找到的兩個點分別是(1,1)和(2,,4)。可以有多種插值的方式，這取決於你的需求，我們仍然拿線性插值舉例，通過(1,1)和(2,4)可以確定一條直線，然後把1.5帶入即可。

Interpolant原始碼

Interpolant採用了一種設計模式：模板方法模式。

在插值的整個流程中，對於不同的插值方法來說，尋找插值位置這一操作是一樣的，所以把這一個操作可以放在基礎類別中實現。

對於不同的插值型別，都派生自Interpolant，然後實現具體的插值方法，這個方法的引數就是上面尋找到的位置。

1. 構造器

constructor(parameterPositions, sampleValues, sampleSize, resultBuffer) {
    this.parameterPositions = parameterPositions;
    this._cachedIndex = 0;
    this.resultBuffer = resultBuffer !== undefined ?
        resultBuffer : new sampleValues.constructor(sampleSize);
    this.sampleValues = sampleValues;
    this.valueSize = sampleSize;
    this.settings = null;
    this.DefaultSettings_ = {};
}

基本上就是把引數中的變數進行賦值，對於resultBuffer來說，如果不在引數中傳遞，那麼就會在構造器中進行建立。

_cachedIndex放到後面解釋。

2. copySampleValue_()

如果，我們要插值的點，剛好是取樣點，就沒必要進行計算了，直接把取樣點的結果放到resultBuffer中即可，這個方法就是在做這件事，引數就是取樣點的下標。

copySampleValue_(index) {
    // copies a sample value to the result buffer
    const result = this.resultBuffer,
        values = this.sampleValues,
        stride = this.valueSize,
        offset = index * stride;
    for (let i = 0; i !== stride; ++i) {
        result[i] = values[offset + i];
    }
    return result;
}

3. interpolate_( /* i1, t0, t, t1 */ )

interpolate_( /* i1, t0, t, t1 */ ) {
    throw new Error( 'call to abstract method' );
    // implementations shall return this.resultBuffer
}

這個就是具體的插值方法，但是在基礎類別中並沒有給出實現。

4. evaluate()

接下來就是多外暴露的介面，通過這個方法計算插值的結果。

這段程式碼用了一個不常用的語法，類似C語言中的goto語句，可以給程式碼塊命名，然後通過break 程式碼塊名跳出程式碼塊。

這段程式碼就是實現了上面說的插值的過程：

尋找位置

插值（呼叫interpolate_()方法）

整個validate_interval程式碼塊，其實就是在找插值的位置。它的流程是：

線性查詢

根據上一次插值的位置，向陣列尾部的方向查詢兩個位置。（這裡就是構造器中_cachedIndex的作用，記錄上一次插值的位置）。如果到了陣列最後仍然沒找到，則到陣列頭部去找；如果沒有到陣列尾部，則直接跳出線性查詢，使用二分查詢。

二分查詢

為什麼要先在上一次插值的左右位置進行線性查詢呢？插值最常見的使用場景就是動畫，每次會把一個時間傳進來進行插值，而兩次插值的間隔通常很短，分佈在上一次插值的附近，可能是想通過線性查詢優化效能。

evaluate(t) {
    const pp = this.parameterPositions;
    let i1 = this._cachedIndex,
        t1 = pp[i1],
        t0 = pp[i1 - 1];
    validate_interval: {
        seek: {
            let right;
            // 先進性線性查詢
            linear_scan: {
                //- See http://jsperf.com/comparison-to-undefined/3
                //- slower code:
                //-
                //-                 if ( t >= t1 || t1 === undefined ) {
                forward_scan: if (!(t < t1)) {
                    // 只向後查詢兩次
                    for (let giveUpAt = i1 + 2; ;) {
                        // t1 === undefined，說明已經到了陣列的末尾
                        if (t1 === undefined) {
                            // t0是最後一個位置
                            // 如果t < t0
                            // 則說明向陣列末尾找，沒有找到
                            // 因此跳出這次尋找 接著用其他方法找
                            if (t < t0) break forward_scan;
                            // after end
                            // t >= t0
                            // 查詢的結果就是最後一個點 不需要進行插值
                            i1 = pp.length;
                            this._cachedIndex = i1;
                            return this.copySampleValue_(i1 - 1);
                        }
                        // 控制向尾部查詢的次數 僅查詢兩次
                        if (i1 === giveUpAt) break; // this loop
                        // 迭代自增
                        t0 = t1;
                        t1 = pp[++i1];
                        // t >= t0 && t < t1
                        // 找到了，t介於t0和t1之間
                        // 跳出尋找的程式碼塊
                        if (t < t1) {
                            // we have arrived at the sought interval
                            break seek;
                        }
                    }
                    // prepare binary search on the right side of the index
                    right = pp.length;
                    break linear_scan;
                }
                //- slower code:
                //-                    if ( t < t0 || t0 === undefined ) {
                if (!(t >= t0)) {
                    // looping?
                    // 上一次查詢到陣列末尾了
                    // 查詢陣列前兩個元素
                    const t1global = pp[1];
                    if (t < t1global) {
                        i1 = 2; // + 1, using the scan for the details
                        t0 = t1global;
                    }
                    // linear reverse scan
                    // 如果上一次查詢到陣列末尾
                    // i1就被設定成了2，查詢陣列前2個元素
                    for (let giveUpAt = i1 - 2; ;) {
                        // 找到頭了
                        // 插值的結果就是第一個取樣點的結果
                        if (t0 === undefined) {
                            // before start
                            this._cachedIndex = 0;
                            return this.copySampleValue_(0);
                        }
                        if (i1 === giveUpAt) break; // this loop
                        t1 = t0;
                        t0 = pp[--i1 - 1];
                        if (t >= t0) {
                            // we have arrived at the sought interval
                            break seek;
                        }
                    }
                    // prepare binary search on the left side of the index
                    right = i1;
                    i1 = 0;
                    break linear_scan;
                }
                // the interval is valid
                break validate_interval;
            } // linear scan
            // binary search
            while (i1 < right) {
                const mid = (i1 + right) >>> 1;
                if (t < pp[mid]) {
                    right = mid;
                } else {
                    i1 = mid + 1;
                }
            }
            t1 = pp[i1];
            t0 = pp[i1 - 1];
            // check boundary cases, again
            if (t0 === undefined) {
                this._cachedIndex = 0;
                return this.copySampleValue_(0);
            }
            if (t1 === undefined) {
                i1 = pp.length;
                this._cachedIndex = i1;
                return this.copySampleValue_(i1 - 1);
            }
        } // seek
        this._cachedIndex = i1;
        this.intervalChanged_(i1, t0, t1);
    } // validate_interval
    // 呼叫插值方法
    return this.interpolate_(i1, t0, t, t1);
}

上面的程式碼看著非常多，其實大量的程式碼都是在找位置。找到位置之後，呼叫子類實現的抽象方法。

5. LinearInterpolant實現interpolate_( /* i1, t0, t, t1 */ )方法

class LinearInterpolant extends Interpolant {
    constructor(parameterPositions, sampleValues, sampleSize, resultBuffer) {
        super(parameterPositions, sampleValues, sampleSize, resultBuffer);
    }
    interpolate_(i1, t0, t, t1) {
        const result = this.resultBuffer,
            values = this.sampleValues,
            stride = this.valueSize,
            offset1 = i1 * stride,
            offset0 = offset1 - stride,
            weight1 = (t - t0) / (t1 - t0),
            weight0 = 1 - weight1;
        for (let i = 0; i !== stride; ++i) {
            result[i] =
                values[offset0 + i] * weight0 +
                values[offset1 + i] * weight1;
        }
        return result;
    }
}