皮克斯動畫里的數學

知識 03-10

作者 | 橘子老君

來源 | 橘子數學（ID：mathcrowd）

引言

當觀看皮克斯出品的動畫電影時，你是否被裡面製作精細的3D人物造型所驚艷到?那些豐富的細節到底是如何製作出來的呢？橘子老君將在本文中為你揭示其背後的數學奧秘：計算機圖形學(Computer Graphics)中幾何建模(Geometric Modeling)的基礎——曲線(面)細分(Subdivision)。

橘子老君將用高中生也能讀懂的方式來講解曲線細分技術，其中涉及如何用遞推數列及矩陣乘法描述細分的過程，以及如何用數學方法得到最終的光滑曲線，希望大家喜歡。

曲線(面)細分

——讓線條及表面變得更光滑

上面四張圖展示了《怪獸大學》中的一個畫面場景的製作流程，從最簡單的分鏡腳本(a)，到網格狀的原型(b)、再到平面著色的預覽圖(c)、最終得到具有更多紋理和陰影的極具真實感的畫面。

要完成一部動畫電影的製作，顯然是浩大的工程，涉及到很多專業技術，其中就包括我們今天要介紹的曲線(面)細分技術(以下簡稱細分技術)，這是一種通過不斷分割不斷調整的方式，使線條及表面變得更光滑的技術。

上圖是皮克斯在1997年製作的動畫短片《Geri"s Game》中主角的一隻手。實際上，在當時短片的製作過程中，是由該片的導演，恰好也是一位雕塑家，先雕刻出一個模型掃描進電腦(a)，然後再通過細分技術得到更真實的效果(b)。

本文為了簡單起見將重點介紹曲線細分，空間曲面細分所用的原理與思想方法與平面曲線大致是相同，但是實現起來就要複雜一點。

如下圖所示，不難想像一條連接正方形四個頂點的封閉曲線通過細分變為了一條光滑的類似內切圓的封閉曲線(實際上並不是內切圓)，而另一條不太規則的封閉曲線所圍成的多邊形通過細分變為了一條大致保留原來輪廓的光滑曲線。

下面橘子老君就來揭示上面所採用的細分技術的具體實施步驟(演算法)。

細分：分割與平均

如上面動畫所演示的，首先我們有一些點組成的有序列表(以下簡稱點列)，並用線段連接相鄰兩點，即得到一條初始曲線(為了迴避對曲線邊界情況的處理，本文僅討論封閉曲線的情況，即認為點列首尾相鄰)。然後不斷重複下述兩個步驟。

分割

作出原曲線上各條線段的中點插入到原有的點列,即完成對原曲線的分割。此時點列中點的個數變為原來的兩倍。

平均

計算點列中所有相近的一些點的加權平均，得到新的點列。比如計算所有相鄰兩個點的平均即中點，這些中點即組成新的點列。然後連結其中所有相鄰兩點得到調整後的新曲線。此時點列中點的個數並未發生改變，只是其中的點發生了改變(移動)。

當曲線完成一次分割、平均操作，也被稱為曲線完成了一次細分。

具體地，請看上面的示意圖，我們用藍色標記點列中的點。從上左圖到上右圖完成了分割，點列由原來正方形的四個端點變為八個點；從上右圖到左下圖完成了平均，點列中的點即上右圖中八個點相鄰兩點的中點。而右下圖是重複多次細分操作後所得的曲線，不難想像在經過無窮多次操作後即會得到一條光滑曲線(多邊形的邊長無限趨近於0)。

上述平均的操作被稱為「1-1法則」，另外還有「1-2-1法則」，即調整了參與加權平均操作點的個數及權重，變為由所有兩兩相鄰的3個點參與權重為1,2,1的加權平均。

細分與遞推數列

我們不妨把個點組成的原始點列記為，經過一次分割後，將中點插入後得到，經過一次平均後得到。

為了記號的簡潔，接下來我們使用以下點的加法和數乘運算，

現有點和點，我們定義:

顯然，點的加法和數乘運算同樣滿足實數中的運算性質。故我們可以得到點列、、間的遞推關係。

採用1-1法則，綜合兩式可得，

一般地，我們把經過次「分割-平均」後得到的曲線記作，則有

注意，當時代入上式會出現不存在的情況。由於本文討論的是閉合曲線，我們可以補充定義。一般地，我們可以補充定義，其中為點列中點的個數。

通過觀察與的遞推關係可知，中的點是對應曲線上所有線段的靠近兩端的兩個四等分點。由此，在所對應的曲線上，任意線段的中點都會落在內，在下文中我們會給出證明。

細分與矩陣乘法

為了記號的簡潔，我們把初始點列記作，經過一次平均後的點列記作，再經過一次分割後得到的點列記作。

相信看過markov系列文章的讀者，應該對類似遞推數列與矩陣乘法的關係比較熟悉1,為了幫助還不太熟悉矩陣乘法的讀者迅速發現其中的聯繫，我們列出一些分割操作中點列與點列的遞推式，

故得到

注意，這裡的矩陣並不是方陣，而是行列的矩陣。

同理可得，採取1-1法則，經過平均操作，點列與的關係。

利用矩陣乘法的結合律，得到與的遞推關係。

其中

無窮多次細分後的極限

之前我們提到在經過無窮多次細分後，我們會得到一條光滑曲線。當我們已知平均的規則後，其實並不需要利用計算機進行無窮多次遞推或矩陣乘法計算來得到光滑曲線，相反多次計算會造成很大的累計誤差。通過對矩陣的特徵值分析，我們得到矩陣次方，即遞推數列的通項，也就是最終光滑曲線的精確解。

橘子老君並不想在本文中對矩陣的特徵值和特徵向量展開，所以會在不影響總體理解的情況下於下文中儘可能迴避它們。

設、是曲線上某線段的兩個端點，那麼經過一次細分後，該線段上兩個四等分點、落在新曲線上，同時線段仍然在線段。經過次細分後，我們就能得到點列和。要證明、的中點落在極限位置，即要證明。

證明:由遞推關係，

兩式相加，得到

兩式相減，得到

故

由極限的運算性質解得，

得證。

其實我們研究一條線段上兩個點的變化即等價於我們研究矩陣前兩行、前兩列。顯然上面這個問題太過簡單，根本無法滿足讀者的胃口，所以我們再舉一個採用「1-2-1法則」細分曲線的例子。這次我們目標同樣是找到極限光滑曲線上的一點。如圖(a)我們來看曲線上一個由相鄰三點組成的局部，

如圖，經過一次分割得到、，而、、經過取加權平均得到，即

代換等式右邊的、得，其中。

而、、經過一次加權平均後仍然落在位置，同理也在平均後的曲線上。

此時即得到經過一次細分的曲線上的三點、、。重複上述操作可得、、。

故得到遞推關係如下，

利用特徵值分析，我們可以得到當時，

由

即得到，當時，

即是極限光滑曲線上的點。

我們也可以通過遞推關係代入計算驗證得到，

同理可得，

而由，即得到。

更多平均法則

實際上除了上述「1-1法則」和「1-2-1法則」兩種曲線細分方式還有很多其他選擇，只要稍微調整參與加權平均的點的個數及它們的權重，就可以得到一種新的細分方式，但是只有對求加權平均的這一操作進行精心的設計才能獲得比較好的效果(比如較好保留原來的輪廓並最終穩定在一條光滑曲線)。比如「1-3-3-1」、「1-4-6-4-1」法則，即帕斯卡三角上的組合數作為權重的平均操作就被認為效果不錯。但是「1-(-2)-3」就無法穩定在一條光滑曲線上,如下圖。