項目名稱：    三維造型的幾何計算理論研究

推薦單位：    信息產業部

項目簡介：    　　本項目屬于計算機科學技術領域。本項目系統地提出三維造型的幾何計算理論，針對幾何造型中的數字建模、幾何形狀編輯和裝配等關鍵環節，研究曲線曲面造型的幾何計算、曲面與實體編輯的幾何算法、基于工程圖的三維幾何重建和三維幾何約束求解等幾何造型領域的公開問題和著名難題，取得了一系列有國際影響的成果，主要包括：

　　1. 提出了基于離散系數范數的約束優化方法，解決著名國際刊物Computer Aided Geometric Design（Elsevier, 以后簡稱CAGD）已故主編Hoschek提出的"近似合并"的公開問題，以及Ball、B樣條曲線的降階逼近問題；給出了二次Bézier 曲線的G1圓弧樣條逼近的段數上界估計和兩種二分算法；發現圓弧樣條的一個經典公式的缺陷，并給出修正公式。

　　2. 提出多點多法向約束和曲線約束下的曲面編輯修改算法，使NURBS曲面精確滿足指定的幾何約束；給出了單點約束條件下FFD直接操作的顯式解，并發現FFD多點約束下的直接操作具有可分解性，從而可實現實時的變形控制。

　　3. 提出可以重建任意二次曲面體的三維形體重建方法，擴大了三維重建算法的覆蓋域，并提高了算法的效率，使得基于工程圖三維形體重建這一實體造型中的著名難題取得突破性進展。

　　4. 提出可以對幾何約束系統進行最大分解的遞歸算法，與Owen教授等提出的其他方法相比，新方法拓廣了幾何約束分解與求解器的適應性范圍，提高了三維造型中的裝配和工程圖求解的能力。

　　以上成果在三維造型的關鍵問題上取得突破，形成了完整的理論體系。該項目發表論文40篇，其中SCI收錄22篇，EI收錄31篇，12篇論文刊登在代表國際CAD最高學術水平的Computer Aided Design（Elsevier, 以后簡稱CAD）雜志上；論文共被他引318次，其中SCI他引78次；10篇代表論文被他引164次，其中SCI他引53次。以上成果還被應用于清華大學自主研發的幾何造型系統GEMS中，在企業中得到廣泛應用。

主要發現點：  　　本項目針對幾何造型中數字建模、幾何形狀編輯和裝配等關鍵環節，提出三維造型的幾何計算理論。主要的科學發現和創新點如下：

　　① 提出了基于離散系數范數的約束優化方法，解決了著名國際刊物CAGD已故主編Hoschek于1987年提出的"近似合并"的公開問題，以及Ball、Bézier、B樣條曲線的降階逼近問題 [見代表性論文1，2，10；學科分類為 幾何造型理論]。

　　② 基于工程圖的三維形體重建是實體造型中的著名難題。提出的三維形體重建方法，通過推導曲線邊直接生成的幾何理論和改進面環搜索策略，實現了任意二次曲面體的三維重建。而前人的算法只能重建多面體和對主軸方向有嚴格限制的二次曲面體，這是目前國際上最好的結果 [見代表性論文5；學科分類為 幾何造型理論]。

　　③ 提出了多點多法向約束和曲線約束下的曲面編輯修改算法，利用約束優化理論求解變形后的控制頂點，使NURBS曲面精確滿足指定的幾何約束。[見代表性論文3；學科分類為 幾何造型理論]。

　　④ 自由體變形的直接操作是計算機動畫中的經典方法；我們首次給出了單點約束條件下FFD直接操作的顯式解，并發現FFD多點約束下的直接操作具有可分解性，從而可實現實時的變形控制 [見代表性論文4；學科分類為 計算機圖形學基礎理論]。

　　⑤ 利用二分圖匹配和有向圖的連通性分析等技術，給出了分解約束系統的遞歸算法，并證明了分解約束系統的遞歸算法可以對幾何約束系統進行最大分解。給出了利用啟發式規則加虛約束的算法，發現并證明：轉化后約束系統的秩不大于原來的5倍[見代表性論文6；學科分類為幾何造型理論]。

　　⑥ 基于重新參數化技術和Bézier曲面的算子表示，提出了三角Bézier曲面到退化、非退化張量積 Bézier曲面轉化的遞歸算法，揭示了兩類Bézier曲面的內在聯系。[見代表性論文9，及主要論文12；學科分類為 幾何造型理論]。

　　⑦給出了二次Bézier 曲線的G1圓弧樣條逼近的圓弧段數上界的估計，提出了基于圓弧段數的二分算法和基于參數區間的兩種二分算法，減少了所需的圓弧段數以及計算時間。同時，發現圓弧樣條的一個經典公式的缺陷，并給出修正公式[見代表性論文7，8；學科分類為幾何造型理論]。

主要完成人：  1.   胡事民

在曲線曲面的近似合并與降階逼近算法、NURBS曲面編輯修改算法、FFD直接操作的顯式解、樣條曲面延伸算法和幾何約束分解等方面，對本項目《主要發現點》的第一、三、四、五、六條作出了創造性貢獻。見代表性論文的[1,2,3,4,6,9,10]。胡事民在本項目中承擔的工作量占本人工作量的80％。

2.   孫家廣

在三維形體重建的環搜索算法、幾何約束求解的啟發式規則、FFD直接操作的交換群性質和近似合并的誤差控制等方面，對本項目《主要發現點》的第一、二、四、五條作出了創造性貢獻。見代表性論文的[1,2,3,4,5,6]。孫家廣在本項目中承擔的工作量占本人工作量的50％。

3.   雍俊海

在基于廣義B差商和離散系數范數的B－樣條降階逼近算法和二次Bezier曲線圓弧樣條逼近算法方面，對本項目《主要發現點》的第一、七條作出了創造性貢獻。見代表性論文的[1,2,7,8]。雍俊海在本項目中承擔的工作量占本人工作量的50％。

4.   劉世霞

在基于工程圖三維形體重建的曲線邊直接生成理論和用于候選面生成的最小轉角法方面，對本項目《主要發現點》的第二條作出了創造性貢獻。見代表性論文的[5]。劉世霞在本項目中承擔的工作量占本人工作量的30％。

5.   張慧

在多點約束的FFD直接操作算法，以及FFD多點直接操作的可分解性方面，對本項目《主要發現點》的第四條作出了創造性貢獻。見代表性論文的[4]。張慧在本項目中承擔的工作量占本人工作量的30％。

10篇代表性論文：  1.   Approximate merging of a pair of Bezier curves/ Computer-Aided Design

2.   Degree reduction of B-spline curves/ Computer Aided Geometric Design

3.   Modifying the shape of NURBS surfaces with geometric constraints/ Computer-Aided Design

4.   Direct manipulation of FFD: efficient explicit solutions and decomposible multiple point constraints/ VISUAL COMPUTER

5.   Reconstruction of curved solids from engineering drawings/ Computer-Aided Design

6.   A constructive approach to solving 3-D geometric constraint systems using dependence analysis/ Computer-Aided Design

7.   Bisection algorithms for approximating quadratic Bezier curves by G(1) are splines/ Computer-Aided Design

8.   A note on approximation of discrete data by G(1) arc splines/ Computer-Aided Design

9.   Conversion of a triangular Bezier patch into three rectangular Bezier patches/ Computer Aided Geometric Design

10.  Properties of two types of generalized Ball curves/ Computer-Aided Design