【遊戲數學】內插法1 - 兩點間的內插

簡介

內插法是一種用離散的數據點產生連續變化的辦法。
它是遊戲中最常見的數學工具之一。可以說沒有它的話，遊戲根本做不成。

舉個例子，骨架動畫的關鍵影格。
在作動畫時，只要定義好關鍵影格的角色動作，程式就會自動幫我們產生出中間的動作。
事實上，兩個關鍵影格之間的動作就是內插出來的。

換句話說，假如不用內插法，我們就得手動設定每一幀所有骨頭的角度。
作過的人應該知道這是多麼星爆的一件事…

不只是動畫，甚至連軌跡曲線、圖片的旋轉等等都是用內插實現的。
你能想像一張圖片得存各種旋轉角度、各種尺寸的版本嗎？
因此內插法節省了我們很多工夫以及記憶體。
它讓我們在記錄一連串連續過程時，不需要紀錄所有的中間狀態，只要紀錄幾個關鍵資料點就好。

今天因為是系列的第一篇，就先來介紹最簡單的情況，也就是兩點間的內插。
為了方便，接下來也都會以「內插函數」代稱「兩點間的內插函數」。

內插函數的性質

試著把一個滑順的動畫慢動作撥放看看，會發現每個影格間變化的程度都不會太大。
「滑順」在數學上其實就是連續的意思。指在很短的時間變化內，狀態也不會有太大的變化。
尋找兩點間的內插，其實就是在找一個通過兩點的連續函數。

先來定義一些等等會用到的變數：
起始值：s
終止值：d
時刻：t，介於0到1之間。

所謂的內插函數，就是一個函數f(s, d, t)。
給定「起始值」，「終止值」以及之間的「時刻」，輸出對應的「內插值」。
其中要符合以下三個條件：

t=0時，輸出為s
t=1時，輸出為d
函數連續

內插法在遊戲裡最常見的應用，就是讓t在一段時間內從0變成1，這樣函數的輸出值就會從s逐漸變化成d。
這使我們可以讓遊戲中的物件從一個狀態順暢的變化成另一個狀態。
無論是位移、變形、淡入淡出還是變色，都是建立在「平滑變化」的基礎上。

內插函數介紹

內插函數的種類非常多，因為他有很多可以調的性質。
比如是頭、中、尾的部分是要加速還是減速，陡峭還是平穩，要不要抖動…等等。
就像有很多配菜，每個都可以選擇加或不加一樣，組合出來的種類就非常多。
基本上各種場合都有最適合的內插函數。
甚至有人做了一個內插函數大抄的網頁來展示各種內插函數的效果。

由於遊戲中的內插往往是每幀都要計算一次，遊戲中的內插函數通常都很簡單。
大多都是多項式或常見函數的組合。
如果是3D建模的軟體，可能就會考慮稍微複雜的函數來讓形狀好看點。
例如3D曲面有時會使用NURBS函數。
這邊先來介紹幾個簡單又常見的。

線性內插
$$f(s, d, t) = s + (d-s)*t$$

毫無反應，就是一條線。
因為計算簡單，這是最常用的內插函數。
但它最大的缺點就是開始和結束都很突然，因此不適合在某些場合使用。
例如，位移動畫就不太適合。因為人眼對速度的變化很敏感。
但顏色的變化就還好，因此淡入淡出常常都是用線性內插來實作。

加速內插
$$f(s, d, t) = s + (d-s)*t^N$$

其中N越大加速的幅度越大。
由於結束的瞬間會忽然停下，通常是用來當滑出畫面的動畫。

減速內插
$$f(s, d, t) = s + (d-s)*(1-(1-t)^N)$$

其中N越大減速的幅度越大。
可以看出來其實就是很偷懶的把加速內插的圖形轉180度。
由於開始的瞬間很突然，通常會拿來做滑進畫面的動畫。

先加速後減速內插
$$f(s, d, t) = s + (d-s) * \frac{1+cos(\pi*(1+t))}{2} $$

他的名字叫AccelerateDecelerateInterpolator，可以說是Android開發者的惡夢。
名字長到驚天地泣鬼神，完美的展現為什麼大家討厭Java。
(我甚至懶得打這一串，這是直接從Android的頁面複製過來的)
這個函數很常被用來作位移動畫，因為他起始和結束時，速度都是剛好為零。
因此整個變化過程不僅值是連續的，連速度都是連續的，做出來的動畫看上去就很舒服。

歸一化

有些人應該已經看出來了，這些不同的內插函數其實有著相同的形式：
$$f(s, d, t) = s + (d-s)*g(t)$$
g(t)是一個介於0和1的函數。
也就是說我們其實可以將相同的部分提出，只留下g(t)，這個動作稱為歸一化。
歸一化後的內插函數稱作歸一內插函數。

歸一化帶給我們很多好處。
首先輸入和輸出的範圍都變成了0到1，處理起來很方便，無論怎麼迭代範圍都會固定在0和1之間。
因此我們可以任意組合兩個歸一內插函數，來得到另一個歸一內插函數。
並且，只要經過任意的縮放和平移，就可以把歸一內插函數變成任兩個值之間的內插函數。

以下是上面提到的內插函數的歸一化版本：

線性內插：
$$g(t) = t$$

加速內插：
$$g(t) = t^N$$

減速內插：
$$g(t) = 1-(1-t)^N$$

先加速後減速內插
$$g(t) = \frac{1+cos(\pi*(1+t))}{2} $$
(這個東西就算歸一化還是很醜)

程式實作

這邊以一個遊戲中最常碰到的內插動畫：「將物體從A點順暢的移到B點」
來示範Unity如何實作兩點內插函數，以及各個內插函數的使用效果。

Unity自己有實作未歸一化的線性內插函數，也就是有名的Mathf.Lerp。
他的形式如下：
$$Lerp(s, d, t) = s + (d-s)*t$$

這個形式感覺很熟悉…我們回頭看看剛才的「內插函數共通形式」
$$f(s, d, t) = s + (d-s)*g(t)$$
唯一的差別就只有t變成了g(t)。
事實上，只要把指定的歸一化內插函數g(t)塞進t的位置，它就變成原本的內插函數f(t)了。

因此實作兩點內插函數的方法，就是先實作各種歸一化內插函數，然後塞進Lerp裡就成了。
那麼我們就來實作剛剛提過的各種歸一化內插函數吧。

public static class Interpolator{
    // 線性內插函數
    public static float Linear(float t){
        return t;
    }	
    // 加速內插函數
    public static float Accel(float t){
        return Mathf.Pow(t, 4);
    }	
    // 減速內插函數
    public static float Decel(float t){
        return 1-Mathf.Pow(1-t, 4);
    }	
    // 先加速後減速內插函數
    public static float AccelDecel(float t){
        return (1+Mathf.Cos(Mathf.PI*(1+t)))*0.5f;
    }
}

接下來來實作內插動畫的函數。
用程式產生動畫，自然少不了coroutine。
這邊的實作方式是在指定的時間內，每個frame都計算目前時間對應到的內插值，再用內插值來更新物件狀態。
結束的時候再更新一次狀態，以確保結束的狀態正確。

public static class Interpolation
{
    public static IEnumerator Transition(float src, float dst, float duration, Func<float, float> interpolator, Action<float> onUpdate) {
        float time = 0;
        while (time < duration)
        {
            float t = interpolator(time/duration);
            float current = Mathf.Lerp(src, dst, t);
            onUpdate(current);
            time += Time.deltaTime;
            yield return null;
        }
        onUpdate(dst);
    }
}

src是初始值，dst是結束值，duration是動畫的長度。
這個函式會在給定的時間內使一個數值從src變化成dst。

這邊最重要的就是interpolator跟onUpdate兩個參數。
interpolator是我們想指定的歸一化內插函數。把它餵給Lerp後，就變成了任意兩個值之間的內插函數。
而onUpdate則負責更新遊戲物件的狀態，它會取得該時刻的內插值，再根據內插值來設定物件的狀態。

這邊補充一下，剛接觸C#的人可能看不太懂這兩個參數的型別。
這兩個參數實際上都是「函數」。
Action代表「參數是一個float的函數，沒有回傳值的函數」。
Func<float, float>代表「輸入是一個float，回傳值也是float函數」。

這邊之所以要大費周章的把函數從外面傳進來，而不是寫在內插動畫裡，是為了能重複利用Transition這個函數。
要是我們哪天不想作位移動畫了，而是想要做變色的動畫，
我們就只需要把onUpdate改成一個設定顏色的函數就好了，完全不用改Transition。
Action和Func都屬於Delegate的概念，以後有機會會在其他文章補充。

以下則是實際呼叫動畫函數的腳本。這個物件會在遊戲開始時，會從指定的起始位置移動到結束位置。

public class Player : MonoBehaviour {
    [SerializeField] private float _srcX;
    [SerializeField] private float _dstX;
    [SerializeField] private float _duration;

    void Start () {
        StartCoroutine(Interpolation.Transition(_srcX, _dstX, _duration, Interpolator.Linear, UpdatePosX));
    }
	
    private void UpdatePosX(float x)
    {
        Vector3 pos = transform.position;
        pos.x = x;
        transform.position = pos;
    }
}

為了方便，起始位置、結束位置和時間長都可以在編輯器裡設定。

這邊展示一下各個內插函數的移動效果。

線性內插：

加速內插：

減速內插：

先加速後減速內插：

進階補充：Delegate小技巧

如果你希望能設定加速和減速的幅度呢？
這邊可以寫成兩個變數。

public static float Accel(float t, float rate){
    return Mathf.Pow(t, rate);
}	

public static float Decel(float t, float rate){
    return 1-Mathf.Pow(1-t, rate);
}

但問題來了：interpolator參數的型別是Func<float, float>，不能塞兩個參數的函數。
這時我們可以用lambda包裝它

1	t => Accel(t, rate)

最後就變成：

public static float Accel(float t, float rate){
    return Mathf.Pow(t, rate);
}	

public static Func<float, float> Accel(float rate){
    return t => Accel(t, rate);
}	

public static float Decel(float t, float rate){
    return 1-Mathf.Pow(1-t, rate);
}	

public static Func<float, float> Decel(float rate){
    return t => Decel(t, rate);
}

使用上大概會是這樣：

1
2
3

void Start(){
    StartCoroutine(Transition(startPoint, endPoint, 3, Interpolator.Accel(3), UpdatePosX));
}

這裡代表使用了加速程度是3的加速內插函數。

補充

內插函數生成器：http://www.timotheegroleau.com/Flash/experiments/easing_function_generator.htm