項(xiàng)目名稱：    三維造型的幾何計(jì)算理論研究

推薦單位：    信息產(chǎn)業(yè)部

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

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

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

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

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

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

主要發(fā)現(xiàn)點(diǎn)：  　　本項(xiàng)目針對幾何造型中數(shù)字建模、幾何形狀編輯和裝配等關(guān)鍵環(huán)節(jié)，提出三維造型的幾何計(jì)算理論。主要的科學(xué)發(fā)現(xiàn)和創(chuàng)新點(diǎn)如下：

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

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

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

　　④ 自由體變形的直接操作是計(jì)算機(jī)動(dòng)畫中的經(jīng)典方法；我們首次給出了單點(diǎn)約束條件下FFD直接操作的顯式解，并發(fā)現(xiàn)FFD多點(diǎn)約束下的直接操作具有可分解性，從而可實(shí)現(xiàn)實(shí)時(shí)的變形控制 [見代表性論文4；學(xué)科分類為 計(jì)算機(jī)圖形學(xué)基礎(chǔ)理論]。

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

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

　�、呓o出了二次Bézier 曲線的G1圓弧樣條逼近的圓弧段數(shù)上界的估計(jì)，提出了基于圓弧段數(shù)的二分算法和基于參數(shù)區(qū)間的兩種二分算法，減少了所需的圓弧段數(shù)以及計(jì)算時(shí)間。同時(shí)，發(fā)現(xiàn)圓弧樣條的一個(gè)經(jīng)典公式的缺陷，并給出修正公式[見代表性論文7，8；學(xué)科分類為幾何造型理論]。

主要完成人：  1.   胡事民

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

2.   孫家廣

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

3.   雍俊海

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

4.   劉世霞

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

5.   張慧

在多點(diǎn)約束的FFD直接操作算法，以及FFD多點(diǎn)直接操作的可分解性方面，對本項(xiàng)目《主要發(fā)現(xiàn)點(diǎn)》的第四條作出了創(chuàng)造性貢獻(xiàn)。見代表性論文的[4]。張慧在本項(xiàng)目中承擔(dān)的工作量占本人工作量的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