项目名称：    三维造型的几何计算理论研究

推荐单位：    信息产业部

项目简介：    　　本项目属于计算机科学技术领域。本项目系统地提出三维造型的几何计算理论，针对几何造型中的数字建模、几何形状编辑和装配等关键环节，研究曲线曲面造型的几何计算、曲面与实体编辑的几何算法、基于工程图的三维几何重建和三维几何约束求解等几何造型领域的公开问题和著名难题，取得了一系列有国际影响的成果，主要包括：

　　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