近日，中國科學院軟件研究所計算機科學國家重點實驗室圖形圖像團隊在數字幾何處理與建模領域取得進展。該研究針對三維模型上葉狀結構的快速計算問題，提出使用多重網格法算法（multigrid），大幅提升了葉狀結構生成的計算速度，確保了生成計算的收斂性，這將很好地促進葉狀結構的實際應用。相關成果以A multigrid approach for generating harmonic measured foliations為題發表在三維數字建模領域國際會議 SMI 2021上，并獲會議最佳論文提名獎。該論文第一作者是博士生王少東，通訊作者是研究員王文成。 

　　葉狀結構（foliation）是三維曲面表達中的一種幾何結構，在模型參數化、四邊形網格化、曲面映射等領域有重要的應用需求，在數字幾何處理與建模領域中受到廣泛關注。當前，葉狀結構生成算法的計算速度緩慢，甚至在大規模或精細模型上的計算難以收斂，不能得到結果，妨礙了其實踐應用。 

　　為解決這一問題，該團隊提出使用多重網格法（multigrid）來加速葉狀結構的計算。多重網格法的基本思路是構建多分辨率模型層級，先在低分辨率模型上進行計算，再插值到高分辨率模型上，以逐層計算的方式來提高計算收斂速度。該研究針對葉狀結構計算的相關要求，創新性地提出構建特殊的Delaunay多重網格層級，并提出一系列新的插值方式，使得調和可測葉狀結構能基于多層網格法來生成。實驗結果表明，該算法大幅提升了葉狀結構的生成速度，最高可達200倍；對于數百萬面片的三角網格模型，該算法可以在幾分鐘內得到計算結果，而傳統算法在數小時后仍無法求解。因此,該算法的提出，將有力促進葉狀結構的實踐應用。 

　　SMI會議是三維數字建模領域的重要國際會議，從1997年以來已召開20余屆。在今年的線上會議中，邀請到了圖靈獎得主、皮克斯動畫公司的創始人Ed Catmull博士等幾何建模領域的專家參會報告。本屆會議共收錄論文19篇，并評選出了1篇最佳論文獎與2篇最佳論文提名獎。 

　　該論文也將在Computer & Graphics（Elsevier）期刊發表。相關研究得到國家自然科學基金的支持。 

　　論文鏈接 

　　本文算法的基本流程與主要實驗結果

　　SMI 2021會議最佳論文提名獎