卡內基梅隆大學的研究人員已經開發出一種有效的新方法，可以借用一種計算方法來快速分析復雜的幾何模型，從而使逼真的動畫電影成為可能。

傳感器技術的飛速發展已經產生了大量新的幾何信息，從古代建筑遺址的掃描到人體內部器官的掃描。但是分析大量數據，無論是確定建筑物在結構上是否健全，還是氧氣如何通過肺部流動，已經成為計算的瓶頸。

計算機科學和機器人學助理教授基南·克蘭恩（Keenan Crane）說：“數據已成為一種怪物。”“突然之間，您擁有的數據量超出了您可能分析甚至關心的范圍。”

Crane和Rohan Sawhney博士計算機科學系的一名學生正在使用所謂的蒙特卡洛方法來馴服怪物，以模擬粒子，熱量和其他事物如何通過復雜形狀或在復雜形狀內移動。通過此過程，無需將形狀精巧地劃分為網格-可以計算分析的小幾何元素的集合。研究人員將在SIGGRAPH 2020年計算機圖形和交互技術會議上介紹他們的方法，該會議將在7月舉行。

主要作者Sawhney說：“建立網格是可能出現錯誤的雷區”。“如果只變形一個元素，它可能會使整個計算中斷。對于許多行業來說，消除對網格的需求是非常巨大的。”

對于試圖在1990年代創建逼真的動畫的電影制片人來說，網格劃分也是一個難題。網格劃分不僅費力且緩慢，而且結果看起來也不自然。他們的解決方案是通過模擬可能圍繞場景反彈的光線來增加過程的隨機性。結果是產生了逼真的精美照明，而不是平坦的表面和塊狀陰影。

同樣，Crane和Sawhney在幾何分析中也采用了隨機性。他們沒有通過結構反射光線，而是使用蒙特卡洛方法來想象粒子，流體或熱量是如何隨機相互作用并在空間中移動的。蒙特卡洛方法最早是在1940年代和1950年代為美國核武器計劃開發的，是一類算法，該算法以有序方式使用隨機性來產生數值結果。

Crane和Sawhney的工作復興了一種很少使用的“在球上行走”算法，該算法可以模擬粒子在空間中的漫長而隨機的行走，而無需確定每個轉彎。取而代之的是，他們計算粒子周圍最大的空白區域的大小（例如，在肺中是支氣管的寬度），并確定每個球體的直徑。然后，程序可以從每個球體上的一個隨機點跳到下一個以模擬隨機游走。

雖然構建幾何空間的網格可能需要一天的時間，但CMU方法允許用戶在幾秒鐘內大致了解解決方案。然后可以通過進行越來越多的隨機游走來完善此預覽。

索恩尼說：“這意味著不必坐著等待分析完成才能得到最終答案。”“相反，分析是漸進式的，為工程師提供了立即的反饋。這意味著可以花更多的時間進行工作，而將更少的時間花在試圖理解分析為何不起作用的墻上。”

Sawhney和Crane正在與行業合作伙伴合作，以擴大可以使用其方法解決的問題的種類。美國國家科學基金會，帕卡德獎學金，斯隆基金會，Autodesk，Adobe，迪士尼和Facebook為這項工作提供了支持。