91在线国产精品啪,久久日老版视频

作者：Jaewon Jung ? ? ?譯者：杰微刊兼職翻譯劉曉鵬 ?

英雄聯(lián)盟（lol）有125位以上的英雄，每位英雄擁有自己特有的動(dòng)畫(huà)屬性集。（我最喜歡的是哪個(gè)？Sion(英雄聯(lián)盟中的一個(gè)英雄) 的舞蹈，如下所示，僅僅是他38個(gè)動(dòng)畫(huà)效果中的一個(gè)）。這些動(dòng)作使得每個(gè)英雄栩栩如生：從堅(jiān)定的動(dòng)作到強(qiáng)大的魔法釋放到悲慘的死忙（我經(jīng)?？吹阶詈蟮哪且荒唬?。隨著我們不斷的引入和修訂英雄，動(dòng)畫(huà)數(shù)據(jù)的總量已經(jīng)成為資源的一個(gè)很大的負(fù)擔(dān)：如運(yùn)行時(shí)內(nèi)存、包大小及存儲(chǔ)空間。

除了動(dòng)畫(huà)數(shù)據(jù)，視覺(jué)數(shù)據(jù)還包括最近更新Summoner’s Rift的位置，這需要更多的內(nèi)存。為了獲得更好的視覺(jué)效果，更新采用了獨(dú)特紋理效果的方式，而不是原來(lái)的拼接方式。但是，這大大增加了紋理效果映射在內(nèi)存中的大小。

我們將重點(diǎn)放在繼續(xù)支持最大范圍玩家硬件層面上，以至于每個(gè)人可以享受可怕劍圣的不死之身。隨著新的動(dòng)畫(huà)效果及更新映射對(duì)內(nèi)存需求增長(zhǎng)，我們需要找到減少內(nèi)存使用的方法。通過(guò)調(diào)研，我們找到一條途徑：壓縮游戲中骨骼動(dòng)畫(huà)數(shù)據(jù)來(lái)減少內(nèi)存，但是要盡可能減少質(zhì)量損失，并且盡量不影響性能。

我們可能有很多種方式來(lái)壓縮動(dòng)畫(huà)數(shù)據(jù)。在這篇文章中，我將介紹兩種我們主要采用的技術(shù)：量化和曲線擬合。壓縮算法總需要在質(zhì)量損失和內(nèi)存占用之間進(jìn)行權(quán)衡，所以我將會(huì)討論在什么范圍內(nèi)是我們能夠接受的，同時(shí)我也會(huì)討論一下我們是如何組織數(shù)據(jù)以獲取最大的性能。我將會(huì)使用一些概念如四元組和樣條曲線，如果你不熟悉這些概念，我將在文章末尾處給出一些有用的資源列表。

我想指出的是，這里我提到的技術(shù)是全新的。這些技術(shù)是下列游戲開(kāi)發(fā)人員所分享的，使他們?cè)趯?shí)踐中所獲得的知識(shí)。我將他們放在游戲引擎開(kāi)發(fā)者BitSquid的博客中，這非常有用和值得一提的。

量化

量化是一個(gè)數(shù)值處理的過(guò)程，這些數(shù)值包含了連續(xù)可能性集合到相對(duì)較小的離散集合。骨骼動(dòng)畫(huà)包含位置、旋轉(zhuǎn)以及尺寸數(shù)據(jù)。我們能夠很容易量化3維向量，它通常用來(lái)表示位置、大小，并通過(guò)獲取最大/最小值來(lái)來(lái)在這個(gè)范圍內(nèi)均勻的分配。但是 lion 分享的骨骼動(dòng)畫(huà)數(shù)據(jù)通常來(lái)自于旋轉(zhuǎn)。

我們使用四元組來(lái)表示3D空間中的旋轉(zhuǎn)。量化旋轉(zhuǎn)數(shù)據(jù)的方式是利用四元組的特殊數(shù)學(xué)性質(zhì)來(lái)實(shí)現(xiàn)的。假定一個(gè)四元組單位中所有的元素都在[-1,1]范圍內(nèi)，首先，我們確定x,y,z,w中絕對(duì)值最大的元素，然后丟棄該元素并保存其他三個(gè)值。因?yàn)槲覀兛梢酝ㄟ^(guò)x2 + y2 + z2 + w2 = 1恒等式，很容易計(jì)算出刪除的元素。通過(guò)刪除最大的元素，我們可以將其他三個(gè)元素的范圍限制在[-1/sqrt(2), 1/sqrt(2)]之間——記住，在一個(gè)四元組單位里，如果我們沒(méi)有排除最大的元素，一定存在一個(gè)絕對(duì)值最大的元素在這個(gè)范圍之外。我們通過(guò)量化一個(gè)比[-1, 1]更小的范圍來(lái)最大化提高精度，[-1, 1]是在我們沒(méi)有排除最大元素時(shí)的范圍。這也避免了我們重新創(chuàng)建一個(gè)小值元素，這種創(chuàng)建容易引起錯(cuò)誤。

使用這種方法，我們?yōu)楸４娴娜齻€(gè)元素中每個(gè)元素分配15位的空間，用另外2位的空間來(lái)指定刪除的元素。因此每個(gè)四元組單元占48位(有1位沒(méi)用到)的空間，如上圖所示。相比之下，一個(gè)原生的四元組，需要為每個(gè)元素分配一個(gè)32位的浮點(diǎn)型數(shù)字，總共需要占用128位。從128位減少到48位，我們實(shí)現(xiàn)的壓縮比為0.375。

48位量化的四元組能保證的數(shù)值精度為0.000043。你能感覺(jué)到（如果你對(duì)浮點(diǎn)型數(shù)敏感的話）這應(yīng)該滿足大多數(shù)情況。事實(shí)上，當(dāng)我們將這種量化運(yùn)用到所有動(dòng)畫(huà)時(shí)，沒(méi)有動(dòng)畫(huà)繪制者能發(fā)現(xiàn)轉(zhuǎn)化后的質(zhì)量損失。此外，我們可以在加載的時(shí)候進(jìn)行這種轉(zhuǎn)換，而不是后續(xù)對(duì)其進(jìn)行批量轉(zhuǎn)換和修訂，因?yàn)榱炕且粋€(gè)非常輕量級(jí)的處理過(guò)程。

曲線擬合

為了進(jìn)一步壓縮，我們期望能通過(guò)曲線擬合來(lái)改變四元組中的數(shù)值。這個(gè)過(guò)程是通過(guò)構(gòu)造一條曲線或一個(gè)數(shù)學(xué)函數(shù)使其能夠最好的適應(yīng)一系列的數(shù)據(jù)點(diǎn)。我們專(zhuān)門(mén)使用了Catmull-Rom樣條，它可以通過(guò)一個(gè)三階多項(xiàng)式來(lái)表示。我們需要四個(gè)控制點(diǎn)來(lái)定義一段Catmull-Rom樣條，如下圖（來(lái)自維基百科）所示：

Source: Wikipedia ?來(lái)源：維基百科

在執(zhí)行實(shí)際的擬合過(guò)程中，我們使用一種迭代的方式來(lái)減少誤差。該過(guò)程最開(kāi)始只包含兩個(gè)關(guān)鍵幀，即動(dòng)畫(huà)的開(kāi)始和結(jié)束。我們迭代的增加更多的關(guān)鍵幀，以降低曲線的誤差到一個(gè)可以接受的范圍。每次迭代，先識(shí)別出最大誤差的關(guān)鍵幀之間的部分，然后在其中間點(diǎn)插入一個(gè)關(guān)鍵幀。在最大誤差部分中間插入關(guān)鍵幀的過(guò)程反復(fù)執(zhí)行，直到每部分的誤差低于給定的閾值。

你可以從上圖看到紅色擬合曲線到藍(lán)色的原始曲線的迭代過(guò)程。黃色的點(diǎn)代表每次迭代加入的新的關(guān)鍵幀。在這個(gè)案例中，我們通過(guò)88次迭代，將原來(lái)的661幀壓縮到90幀。

在做曲線插補(bǔ)前，別玩了調(diào)整四元組的四個(gè)控制點(diǎn)。一個(gè)四元組Q和-Q表示相同的旋轉(zhuǎn)，但是如果不對(duì)旋轉(zhuǎn)結(jié)果做調(diào)整，可能會(huì)導(dǎo)致插補(bǔ)不是沿著最短路勁去進(jìn)行的。例如，一艘船頭朝北的船準(zhǔn)備向東旋轉(zhuǎn)。沒(méi)有適當(dāng)?shù)乃脑M調(diào)整，這艘船可能會(huì)逆時(shí)針旋轉(zhuǎn)270度，而不是順時(shí)針旋轉(zhuǎn)90度。

曲線擬合對(duì)量化結(jié)果做了進(jìn)一步的壓縮，壓縮比范圍在25%到70%之間。我們發(fā)現(xiàn)，對(duì)位置/旋轉(zhuǎn)/尺寸設(shè)置合適的誤差閾值，對(duì)實(shí)現(xiàn)高壓縮比、不顯著影響視覺(jué)效果是至關(guān)重要的。

我們也考慮通過(guò)節(jié)點(diǎn)參數(shù)化的樣條曲線來(lái)實(shí)現(xiàn)更好的壓縮。在動(dòng)畫(huà)數(shù)據(jù)的案例中，基于給定關(guān)鍵幀時(shí)間的參數(shù)化是最自然的方式。但是，正如下圖（同樣來(lái)自維基百科）所示，具有同樣四個(gè)控制點(diǎn)的曲線形狀依賴于我們使用的統(tǒng)一的，玄或向心的參數(shù)。

Source: Wikipedia? 來(lái)源：維基百科

這些技術(shù)也使得部分動(dòng)畫(huà)有明顯的質(zhì)量損失。我們可以使用更嚴(yán)格的誤差閾值來(lái)減少大部分損失，不過(guò)壓縮比會(huì)受到明顯的影響。因此，我們的動(dòng)畫(huà)設(shè)計(jì)師審查了每個(gè)案例來(lái)尋找質(zhì)量與壓縮比之間的平衡點(diǎn)。此外，與量化情況不同的是，加載時(shí)進(jìn)行轉(zhuǎn)換是不可選的，因?yàn)閿M合曲線的是一個(gè)重量級(jí)的計(jì)算過(guò)程，我們不得不預(yù)處理所有已存在的動(dòng)畫(huà)數(shù)據(jù)。

減少損失

最值得注意的問(wèn)題是由于壓縮導(dǎo)致作品腳部的滑動(dòng)，這是動(dòng)畫(huà)中最丑陋的部分，動(dòng)畫(huà)中角色的腳或者任何受動(dòng)器的端點(diǎn)應(yīng)該是固定不變的。

你可以很容易看到上面視頻中的本應(yīng)該固定不動(dòng)腳一直在滑動(dòng)。這是由于自然的骨骼層次結(jié)構(gòu)綁定在一個(gè)骨骼裝置中，這個(gè)地方產(chǎn)生了異常的累計(jì)，其來(lái)源跟連接點(diǎn)的動(dòng)畫(huà)效果。我們減少該問(wèn)題是使用了一種稱(chēng)之為“自適應(yīng)錯(cuò)誤率”的技術(shù)。這意味著如果連接點(diǎn)有更長(zhǎng)的子鏈，就會(huì)自動(dòng)縮小誤差閾值，而不是每個(gè)點(diǎn)采用相同的閾值。例如，一個(gè)受動(dòng)器終端使用一個(gè)給定的誤差值，但是它的的父連接點(diǎn)的誤差值為它的一半，而它的祖父連接點(diǎn)的誤差值只有它的三分之一等等。父連接點(diǎn)的誤差值縮緊會(huì)級(jí)聯(lián)影響其后續(xù)所有的連接點(diǎn)。

《游戲編程精粹 7》介紹另一種稱(chēng)之為“減少骨骼動(dòng)畫(huà)累計(jì)誤差”的方法。我們內(nèi)部稱(chēng)之為“連接點(diǎn)樁”。對(duì)于一個(gè)固定的連接點(diǎn)（如腳），我們不使用源數(shù)據(jù)流，而是計(jì)算一新的局部轉(zhuǎn)換數(shù)據(jù)，該數(shù)據(jù)抵消了其祖先在壓縮過(guò)程中引入的誤差。這本書(shū)在該主題上包含了更多的資料。

緩存友好的數(shù)據(jù)組織

最后，我們討論一下我們是如何有效的實(shí)現(xiàn)迄今為止所說(shuō)的概念。當(dāng)我們開(kāi)發(fā)這些技術(shù)時(shí)，我們?nèi)匀魂P(guān)注著廣大玩家的硬件，非常謹(jǐn)慎的不引入任何性能問(wèn)題。我的團(tuán)隊(duì)關(guān)注的一件事情是實(shí)現(xiàn)數(shù)據(jù)組織的有好緩存。

其中關(guān)鍵的一步是我們將所有的關(guān)鍵幀（每個(gè)連接點(diǎn)的位置/旋轉(zhuǎn)/尺寸幀）放在一塊單獨(dú)、連續(xù)的內(nèi)存塊中。一種通用的做法是為每個(gè)渠道的每個(gè)連接點(diǎn)創(chuàng)建一個(gè)單獨(dú)的內(nèi)存塊，但是這種看似自然的組織方式，在給定時(shí)間內(nèi)計(jì)算一個(gè)完整的骨骼姿勢(shì)時(shí)，可能會(huì)觸發(fā)幾次緩存失效的情況。我們可以把數(shù)據(jù)放在一個(gè)塊中，因?yàn)樗星李?lèi)型的有效負(fù)載恰巧都為48位。正如我們前面所看到，我們量化四元組到48位，通過(guò)將3D向量的位置/尺寸中元素x,y,z賦值為16位，我們將3D向量的量化到相同大小。你可以查看實(shí)際代碼的結(jié)構(gòu)體，該結(jié)構(gòu)體用來(lái)表示一個(gè)壓縮的幀，代碼如下：

struct CompressedFrame

{? ??

// Normalized key time (0(0.0) - 65535(1.0))? ? uint16_t keyTime = 0;? ? uint16_t jointIndex = 0;? ?

?// Payload, which can be a quantized 3d vector or a quantized quaternion? ?

?// depending on what type of channel this data belongs to? ? uint16_t v[3];? ? ChannelType GetChannelType() const? ??

{? ? ? ?

?// Most significant two bits of this 16bit index contains channel type info.? ? ? ? return static_cast((jointIndex & (0xc000)) >> 14);? ?

?}? ??

void SetChannelType(ChannelType type)?

?? {? ? ? ? jointIndex |= (static_cast(type) << 14);

}

std::uint16_t GetJointIndex() const

{

return jointIndex & 0x3fff;m

}

};

這里，我們也將關(guān)鍵時(shí)間量化為16位。成員變量jointIndex指向本幀數(shù)據(jù)所屬的連接點(diǎn)。數(shù)組v包含了量化后的有效負(fù)載。區(qū)分是否是有效負(fù)載的位置，旋轉(zhuǎn)或尺寸是非常重要的，我們通過(guò)jointIndex中最重要的兩個(gè)位來(lái)完成該任務(wù)。用這種方式來(lái)使用這些位，可以將jointIndex限制在14位或總數(shù)為16384個(gè)連接點(diǎn)——肯定可以滿足lol的英雄，lol中英雄一般要求要少于100個(gè)連接點(diǎn)。

恰當(dāng)?shù)膶?duì)關(guān)鍵幀進(jìn)行排序是非常重要的，無(wú)論是連接點(diǎn)還是渠道類(lèi)型，都在同一個(gè)桶中。我們可以很簡(jiǎn)單的根據(jù)關(guān)鍵時(shí)間對(duì)它們排序（如上面的成員變量keyTime），但是很快就會(huì)出現(xiàn)問(wèn)題。我們想象一下運(yùn)行時(shí)動(dòng)畫(huà)執(zhí)行的內(nèi)容，可以通過(guò)下圖來(lái)幫助想象：

你可以看見(jiàn)四個(gè)關(guān)鍵幀（根據(jù)關(guān)鍵時(shí)間進(jìn)行排序）和一個(gè)指向當(dāng)前時(shí)間執(zhí)行的位置的時(shí)間游標(biāo)。你需要的信息有Tn, Tn+1, Tn+2, 和 Tn+3，因?yàn)橛?jì)算一個(gè)樣條需要四個(gè)控制點(diǎn)。給定游標(biāo)的當(dāng)前位置已經(jīng)過(guò)了Tn和Tn+1，游標(biāo)應(yīng)該已經(jīng)知道這兩個(gè)點(diǎn)。但是Tn+2和Tn+3，哪個(gè)點(diǎn)是游標(biāo)將要經(jīng)過(guò)的呢？你可能認(rèn)為可以快速的掃描它們，因?yàn)檫@兩幀緊跟在后面。

但是，這種方式不是最佳方式。我們稱(chēng)Ts為位置幀。如果動(dòng)畫(huà)大部分是通過(guò)旋轉(zhuǎn)來(lái)完成，則在相鄰的位置幀之間可能存在很多旋轉(zhuǎn)幀（正如你在這個(gè)例子中看到的）。結(jié)果是要掃描從當(dāng)前位置到一個(gè)桶中的所有的幀，因此這種通過(guò)線性掃描來(lái)查找Tn+2和Tn+3的方式可能是低效的。

讓動(dòng)畫(huà)的播放發(fā)生在一個(gè)單一的線性掃描中（和通過(guò)緩存獲取最大利益），其技巧在于要根據(jù)所需時(shí)間來(lái)排序幀，而不是關(guān)鍵時(shí)間。一旦游標(biāo)經(jīng)過(guò)了Tn的關(guān)鍵時(shí)間，我們就需要Tn+2的信息；因此，我們應(yīng)該根據(jù)Tn的關(guān)鍵時(shí)間來(lái)對(duì)Tn+2進(jìn)行排序。通過(guò)這種排序方式，任何時(shí)間點(diǎn)，游標(biāo)都能獲取到當(dāng)前計(jì)算所需要的信息，所以緩存失效也可以最小化。下圖闡述了一個(gè)由四個(gè)位置幀和9個(gè)旋轉(zhuǎn)幀組成的動(dòng)畫(huà)的排序方式：

希望這次深入了解我們壓縮的實(shí)現(xiàn)能夠幫助任何遇到類(lèi)似問(wèn)題的人。

結(jié)論

總而言之，這篇文章中我討論了通過(guò)量化技術(shù)將英雄聯(lián)盟的英雄對(duì)內(nèi)存的要求減少了一半。我們還討論了應(yīng)用曲線擬合技術(shù)的過(guò)程，雖然要求預(yù)處理所有的數(shù)據(jù)，但是早期的結(jié)果表明，這種方式可以實(shí)現(xiàn)進(jìn)一步50%的壓縮，也就是意味著堆內(nèi)存的要求下降到原來(lái)的25%。對(duì)于這個(gè)結(jié)果我非常高興，并且這次改進(jìn)所有玩家的任何硬件類(lèi)型都是有效的。

我們可以進(jìn)一步探索更多的方向，如32位（代替48位）的四元組量化，曲線擬合的不同節(jié)點(diǎn)參數(shù)化，最小二乘法代替迭代法，更優(yōu)的選擇如何在迭代中增加關(guān)鍵幀等等。壓縮是一個(gè)廣泛而又深入的話題，在這篇文章中，我們也僅僅是淺嘗輒止。但是，我還是希望你在處理動(dòng)畫(huà)壓縮時(shí)能發(fā)現(xiàn)本文的有用之處。我在下面的參考文獻(xiàn)部分鏈接了一些相關(guān)的文章。祝你好運(yùn)！