發現幫助計算機繪製複雜的二維動畫

大約60年前，貝爾實驗室的計算機科學家露絲·韋斯發表了一種開創性的演算法，可以將三維物體從任何角度轉換為二維圖形。但她在描繪輪廓時遇到了問題——這個問題幾十年來一直是計算幾何學的一個謎。隨著當今計算機動畫的普及，“隱藏線問題”現在變得更加緊迫。

在計算機動畫的關鍵步驟中，渲染3D模型為2D，最棘手的部分是輪廓這個看似簡單的問題：3D物體的2D視覺輪廓。在理想的世界中，輪廓可以無限精確地描繪——但現實世界需要有限的值。因此，現代演算法首先用微小的三角形“瓦片”覆蓋整個3D模型，然後確定每個瓦片是面向觀看者還是背向觀看者。接下來，演算法使用這些瓦片構建作為輪廓的線段。但是，當在程式化的動畫中使用時，結果可能會產生錯誤的、閃爍的線條——研究人員不確定原因。

關於支援科學新聞報道

如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。透過購買訂閱，您正在幫助確保有關當今塑造我們世界的發現和思想的有影響力的故事的未來。

事實證明，生成足夠精細的三角形網格以避免每種此類錯誤是不可能的。正如 Meta Reality Labs 研究員 Stéphane Grabli（奧斯卡視覺效果獎提名者）解釋說，“感覺上，透過足夠細分，應該可以建立一個網格，從而可以對這些輪廓進行精確的可見性計算。事實證明這是錯誤的。” Grabli 補充說，由此產生的錯誤限制了非真實感插圖風格的複雜性。

現在，在ACM Transactions on Graphics中，不列顛哥倫比亞大學計算機科學家陳曦和她的同事提出了一種名為 ConTesse 的演算法解決方案，該方案專注於修復輪廓而不是網格。透過將演算法生成的輪廓放大 1,600 倍，Liu 發現了輪廓線錯誤地相互交叉的小扭曲——因此，瓦片無法始終如一地識別為面向或背向觀看者。“我用許多表面進行了實驗，發現該演算法在大多數表面上都失敗了，”她說。

研究人員的新演算法首先用線段追蹤 3D 形狀的邊緣，然後將這個近似輪廓壓縮到 2D，並嘗試用三角形平鋪其內部。在內部網格錯誤地自身交叉的任何地方，演算法都會修改輪廓的該部分，例如透過解開扭曲或新增更精細的線段。然後，該演算法使用修復後的輪廓重新生成網格，並將其全部投影回 3D 物件以進行最終的可見性檢查。

該團隊的創新之處在於意識到問題出在輪廓本身。Liu 說，以前不清楚這種無效輪廓甚至有可能存在，因此修復措施處理的是閃爍症狀，而不是原因。未參與這項新研究的 Grabli 對此表示贊同：“該論文證明了早期解決方案為何無法奏效。”