近日，中國科學院軟體研究所計算機科學國家重點實驗室圖形影象團隊在數字幾何處理與建模領域取得進展。研究針對三維模型上葉狀結構的快速計算問題，提出使用多重網格法演算法（multigrid），大幅提升了葉狀結構生成的計算速度，確保了生成計算的收斂性，有助於葉狀結構的實際應用。
葉狀結構（foliation）是三維曲面表達中的一種幾何結構，在模型引數化、四邊形網格化、曲面對映等領域有重要應用需求，在數字幾何處理與建模領域中受到關注。當前，葉狀結構生成演算法的計算速度緩慢，甚至在大規模或精細模型上的計算難以收斂，不能得到結果，妨礙了其實踐應用。
為此，科研人員提出使用多重網格法（multigrid）來加速葉狀結構的計算。多重網格法的基本思路是構建多解析度模型層級，先在低解析度模型上進行計算，再插值到高解析度模型上，以逐層計算的方式提高計算收斂速度。該研究針對葉狀結構計算的相關要求，創新性地提出構建特殊的Delaunay多重網格層級，並提出一系列新的插值方式，使得調和可測葉狀結構能基於多層網格法來生成。實驗結果表明，該演算法大幅提升了葉狀結構的生成速度，最高可達200倍；對於數百萬面片的三角網格模型，該演算法可以在幾分鐘內得到計算結果，而傳統演算法在數小時後仍無法求解。因此，該演算法的提出將促進葉狀結構的實踐應用。
相關研究成果以A multigrid approach for generating harmonic measured foliations為題，發表在三維數字建模領域國際會議SMI 2021、期刊Computer & Graphics上，並獲SMI 2021會議最佳論文提名獎。研究工作得到國家自然科學基金的支援。
演算法的基本流程與主要實驗結果
SMI 2021會議最佳論文提名獎
來源：中國科學院軟體研究所
