基于缺陷曲面的CAD数据修复
摘要
CAGD技术经过了三十多年的发展，已经比较成熟。样条逐渐取代了先后出现的各种曲面等而占主导地位。绝大多数商品化CAD软件也都是以样条为 基础的。作为一种描述方法，样条是相当成功的。但作为造型手段，传统的样条方法还存在许多不足，主要体现在设计人员使用不方便。尤其是在汽车覆盖件，家用电器等外观需要艺术造型的创造性设计中，设计师们往往花费了很大的精力，而效果却不一定理想。在以样条作为描述手段的前提下，寻找新的更便于完成复杂型面产品设计的造型方法日益成为国内外CAD界关注的焦点。在此背景下，三角域造型、N边域造型、偏微分方程造型、变形造型、数学规划(能量法)造型等等新的方法不断涌现。其中数学规划(能量法)造型在众多新技术中是比较引人注目的。
在实际工程中，一个几何模型一般都是由数千个曲面片组成的，通常是分段多项式样条曲面。复杂的模型CAD 数据经常出现的错误，例如曲面间的裂缝，曲面的坍塌，曲面的搭接，曲面内部出现的孔洞，都是由不精确的计算，模型之间的转换，程序运行的结果，也经常包含由不一致的模型修改或者不同设计者在设计同一个模型时没有采用相同标准而产生的错误所造成的。正是这些错误导致不能进行进一步的CAD数据处理。如网格的自动生成等，有限元的分析，快速建模等等。
整个论文中，我提出了一个自动修复实体CAD数据的方法。首先判断曲面片的拓扑结构，就是找到每个曲面片的相邻曲面片。纠正模型中每个曲面片所有边的连通性和可以看见的不连续处，即判断曲面间是否存在缝隙和搭接现象的出现。当邻近的两个曲面间出现裂缝时，在裂缝处利用邻近边最小对的中点，插值为一条样条曲线，将这条样条曲线代替存在缝隙的两条邻
近边，与原有的三条边界插值为一个coons曲面，并转化为样条曲面。通过这个步骤可以改变利用外部条件约束下的能量法只能在同一个参数域条件下进行。在新生成的样条曲面上，选取若干个控制点以及求取这些控制点在新曲面上的法向量，利用点法式作直线，并求取这些直线在原有曲面的交点，并求得两点之间的距离，选取距离最远的一对点，利用能量法的点的约束条件，可用于交互地设计和修改样条曲面的形状。首先给出曲面内部变形能量的近似计算公式；然后将曲面形状修改所需满足的点约束条件转化为相应的外部能量约束项，并附加在曲面的内部能量项之上；求解出我们所需要的能量函数。最后通过求解一个使曲面能量的变化量为最小的无约束优化问题。得到变形后的控制点，利用控制点得到调整后的样条曲面，使曲面总能量近似为最小。同时，通过调整coons曲面边界上的跨界切矢和四个角点的扭矢，这种方法还可以协调曲面的局部变形操作与保持曲面整体光顺性之间的矛盾，从而使变形后的曲面自动保持光顺。本文中给出了一个简单的算例，得出这个方法的可行性。
曲线光顺处理的方法主要有选点修改法和优化方法，而Kjellander的方
法是最常用的选点修改法之一。在本文中提出一种选点修改法——局部能量最优法，该方法在非均匀参数曲线光顺问题上进一步改进了Kjellander方法，具有更好的光顺效果。同时对三次样条曲面给出了一个与此相关的曲面光顺方法。本文首先介绍了曲线和曲面的选点修改法的一般方法，然后提出了一种新的曲线选点修改法——局部能量最优法和其光顺的原理。即在Kjellander算法的基础上，用坏点处个邻近点位矢，代替原算法中两个邻近点的值，用切矢信息以这些条件连同未知点可写出插值曲线的表达式，这种算法计算后的结果将对参数样条曲线有更精确的表达。将改后的型值点列重新插值，可得到修改后的
样条曲线。并以数值例子表现了其具有的良好光顺效果。同时，在非均匀三次样条曲线的基础上，给出了相应的非均匀三次样条曲面的光顺条件，并给出了相应的样条曲面的光顺方法。
The technology of CAGD has been mature during thirty years’ development. B-spline has replaces all kinds of curves that is popular in the world. Most of the commercial CAD softwares are based on B-spline。B-spline is successful as a kind of descriptive way, but as the constructive way, many people are not satisfied with the traditional method of B-spline. For example, the traditional method isn’t convenient for the designer. Especially, the designers expend more energy on the artistic construction of the appliance, but the result of construction isn’t perfect. So searching the new constructive method based on B-spline of finishing the complicated geometry’s design is becoming the focus. Many new methods appeared on this kind of background such as N-side, morpbing, energy, the method of energy is more noticeable in many new technology.
Typically, a complicated real-world geometry is defined in terms of thousand of patches, usually piecewise polynomial (or even rational) B-spline patches. We describe an algorithm of repairing polyhedral CAD models that have errors. Errors like cracks, degeneracies, duplication, holes and overlaps are usually introduced in solid models due to imprecise arithmetic, modle transformations, and designer’s fault, programming bugs. Complicated models often contain errors due to inconsistent model modifications of various designers working on the same model without necessarily enforcing consistency checks and enforcement. Such errors often hamper further processing like finite element analysis, rapid prototyping and generation of mesh.
In this paper, I present a new method about CAD data repairing. First,
judging the topological structure of the surfaces, viz, searching adjacent surfaces of every surface. Verify the connectivity along all the edges of each patch and visualize the errors (discontinuities) in the model, viz, judging the
crack and overlap between the surfaces. When there is the crack between two neighbor patches, we compute the midpoints of the resulting closest point pairs in the crack and interpolate the midpoints by an interpolating cubic B-spline. Then the new B-spline replace the neighbor boundary curves, so each approximating surface patch is constructed by specifying four boundary curves(original three boundary curves, new B-spline curve), computing a coons patch interpolating the four curves and convert the coons surface to B-spline surface. The purpose of this step is that solving the problem of energy method with external conditions in the same parameter region. Selecting some controlling points on the new B-spline surface and compute the normal vector of these points. Getting the line by the point and its normal vector and computing the intersection points of these lines in the new B-spline. Getting the distance of intersection points and controlling points and searching the pair points with the long distance. Taking this point in the original surface as external energy constraints, calculate the internal energy and external energy of the surface and get the function of energy; calculate the new controlling points with the optimization approach. New controlling points generate the B-spline surface with the minimal energy. By the adjusting the conditions of coons surface, the continuous surface will be generated. A simple example is given to prove the algorithms feasible.
Curve fairing methods mainly consist of revising selected points and global optimization. Kjellanders algorithm is one of the most common methods in revision of selected points. We present a local energy optimization approach .In the case of uniformly parameterized cubic splines, LEO improves Kjellander’s algorithm and gets better fairing effect. In the paper, the common method of selecting points is introduced at first, then a local energy optimization approach based on the Kjellander’s algorithm is presented, the main steps is that, searching the bad point in the curve, selecting some adjacent points around the bad point, the number of the points is ,,the new
par
在实际工程中，一个几何模型一般都是由数千个曲面片组成的，通常是分段多项式样条曲面。复杂的模型CAD 数据经常出现的错误，例如曲面间的裂缝，曲面的坍塌，曲面的搭接，曲面内部出现的孔洞，都是由不精确的计算，模型之间的转换，程序运行的结果，也经常包含由不一致的模型修改或者不同设计者在设计同一个模型时没有采用相同标准而产生的错误所造成的。正是这些错误导致不能进行进一步的CAD数据处理。如网格的自动生成等，有限元的分析，快速建模等等。
整个论文中，我提出了一个自动修复实体CAD数据的方法。首先判断曲面片的拓扑结构，就是找到每个曲面片的相邻曲面片。纠正模型中每个曲面片所有边的连通性和可以看见的不连续处，即判断曲面间是否存在缝隙和搭接现象的出现。当邻近的两个曲面间出现裂缝时，在裂缝处利用邻近边最小对的中点，插值为一条样条曲线，将这条样条曲线代替存在缝隙的两条邻
近边，与原有的三条边界插值为一个coons曲面，并转化为样条曲面。通过这个步骤可以改变利用外部条件约束下的能量法只能在同一个参数域条件下进行。在新生成的样条曲面上，选取若干个控制点以及求取这些控制点在新曲面上的法向量，利用点法式作直线，并求取这些直线在原有曲面的交点，并求得两点之间的距离，选取距离最远的一对点，利用能量法的点的约束条件，可用于交互地设计和修改样条曲面的形状。首先给出曲面内部变形能量的近似计算公式；然后将曲面形状修改所需满足的点约束条件转化为相应的外部能量约束项，并附加在曲面的内部能量项之上；求解出我们所需要的能量函数。最后通过求解一个使曲面能量的变化量为最小的无约束优化问题。得到变形后的控制点，利用控制点得到调整后的样条曲面，使曲面总能量近似为最小。同时，通过调整coons曲面边界上的跨界切矢和四个角点的扭矢，这种方法还可以协调曲面的局部变形操作与保持曲面整体光顺性之间的矛盾，从而使变形后的曲面自动保持光顺。本文中给出了一个简单的算例，得出这个方法的可行性。
曲线光顺处理的方法主要有选点修改法和优化方法，而Kjellander的方
法是最常用的选点修改法之一。在本文中提出一种选点修改法——局部能量最优法，该方法在非均匀参数曲线光顺问题上进一步改进了Kjellander方法，具有更好的光顺效果。同时对三次样条曲面给出了一个与此相关的曲面光顺方法。本文首先介绍了曲线和曲面的选点修改法的一般方法，然后提出了一种新的曲线选点修改法——局部能量最优法和其光顺的原理。即在Kjellander算法的基础上，用坏点处个邻近点位矢，代替原算法中两个邻近点的值，用切矢信息以这些条件连同未知点可写出插值曲线的表达式，这种算法计算后的结果将对参数样条曲线有更精确的表达。将改后的型值点列重新插值，可得到修改后的
样条曲线。并以数值例子表现了其具有的良好光顺效果。同时，在非均匀三次样条曲线的基础上，给出了相应的非均匀三次样条曲面的光顺条件，并给出了相应的样条曲面的光顺方法。
The technology of CAGD has been mature during thirty years’ development. B-spline has replaces all kinds of curves that is popular in the world. Most of the commercial CAD softwares are based on B-spline。B-spline is successful as a kind of descriptive way, but as the constructive way, many people are not satisfied with the traditional method of B-spline. For example, the traditional method isn’t convenient for the designer. Especially, the designers expend more energy on the artistic construction of the appliance, but the result of construction isn’t perfect. So searching the new constructive method based on B-spline of finishing the complicated geometry’s design is becoming the focus. Many new methods appeared on this kind of background such as N-side, morpbing, energy, the method of energy is more noticeable in many new technology.
Typically, a complicated real-world geometry is defined in terms of thousand of patches, usually piecewise polynomial (or even rational) B-spline patches. We describe an algorithm of repairing polyhedral CAD models that have errors. Errors like cracks, degeneracies, duplication, holes and overlaps are usually introduced in solid models due to imprecise arithmetic, modle transformations, and designer’s fault, programming bugs. Complicated models often contain errors due to inconsistent model modifications of various designers working on the same model without necessarily enforcing consistency checks and enforcement. Such errors often hamper further processing like finite element analysis, rapid prototyping and generation of mesh.
In this paper, I present a new method about CAD data repairing. First,
judging the topological structure of the surfaces, viz, searching adjacent surfaces of every surface. Verify the connectivity along all the edges of each patch and visualize the errors (discontinuities) in the model, viz, judging the
crack and overlap between the surfaces. When there is the crack between two neighbor patches, we compute the midpoints of the resulting closest point pairs in the crack and interpolate the midpoints by an interpolating cubic B-spline. Then the new B-spline replace the neighbor boundary curves, so each approximating surface patch is constructed by specifying four boundary curves(original three boundary curves, new B-spline curve), computing a coons patch interpolating the four curves and convert the coons surface to B-spline surface. The purpose of this step is that solving the problem of energy method with external conditions in the same parameter region. Selecting some controlling points on the new B-spline surface and compute the normal vector of these points. Getting the line by the point and its normal vector and computing the intersection points of these lines in the new B-spline. Getting the distance of intersection points and controlling points and searching the pair points with the long distance. Taking this point in the original surface as external energy constraints, calculate the internal energy and external energy of the surface and get the function of energy; calculate the new controlling points with the optimization approach. New controlling points generate the B-spline surface with the minimal energy. By the adjusting the conditions of coons surface, the continuous surface will be generated. A simple example is given to prove the algorithms feasible.
Curve fairing methods mainly consist of revising selected points and global optimization. Kjellanders algorithm is one of the most common methods in revision of selected points. We present a local energy optimization approach .In the case of uniformly parameterized cubic splines, LEO improves Kjellander’s algorithm and gets better fairing effect. In the paper, the common method of selecting points is introduced at first, then a local energy optimization approach based on the Kjellander’s algorithm is presented, the main steps is that, searching the bad point in the curve, selecting some adjacent points around the bad point, the number of the points is ,,the new
par
引文
[1] 朱心雄，张鲜。CAD/CAM中自由曲面造型技术的发展与问题。工程图学学报，1994(2)：28～36
[2] Farin G. (1997), Curves and Surfaces for Computer Aided Geometric Design -- A Practical Guide, 4th ed., Academic Press, Boston, Massachusetts.
[3] Bartels, R. H., Beatty, J. C. and Barsky, B. A. (1987), An Introduction to Splines for Use in Computer Graphics and Geometric Modeling, Morgan Kaufman Publishers, Inc., Los Altos, California.
[4] Boehm, W. and Prautzsch, H. (1994), Geometric Concepts for Geometric Design, A K Peters, Wellesley, Massachusetts.
[5] de Boor, C. (1978), A Practical Guide to Splines, Applied Mathematical Sciences, Vol. 27,Springer-Verlag, New York, New York.
[6] Hamann, B. (1994), Construction of B-spline approximations for use in numerical grid generation, Applied Mathematics and Computation 65(1--2), pp. 295--314.
[7] Hoschek, J. and Lasser, D. (1993), Fundamentals of Computer Aided Geometric Design, A K Peters, Ltd., Wellesley, Massachusetts.
[8] Piegl, L. A. and Tiller, W. (1996), The NURBS Book, 2nd edition, Springer-Verlag, New York., New York.
[9] Sharir .M and Barequet Piecewise-linear interpolation between polygorhron slices Technical Report 275/1993 Department of Computer Science, Tel Aviv University
[10] G. Barequet and M. Sharir. Filling gaps in the boundary of a polyhedron.
Computer Aided Geometric Design,12(2):207–229, 1995.
[11] 张丽艳，潘小林，安鲁豫，网格曲面中孔洞的光滑填充算法的研究 工程图学学报 2002（4）113～119
[12] S.M. Morvan and G.M. Fadel. IVECS: An interactive virtual environment for the correction of .STL files。In Conference on Virtual Design, U. California, Irvine, August 1996.
[13] G. Turk and M. Levoy. Zippered polygon meshes from range images In Proceedings of ACM SIGGRAPH, pages 311–318, 1994.
[14] S. J. Rock and M. J. Wozny. Generating topological information from a ’bucket
of facets’. In H.L. Marcus et al., editor, Proc. Solid Freeform Fabrication Symposium, pages 251–259, U. Texas, Austin, Texas USA, August 1992.
[15] J.H. B?hn and M.J. Wozny. Automatic cad-model repair: Shell-closure. In H.L. Marcus et al., editor, Proc.Solid Freeform Fabrication Symposium, pages 86–94,U. Texas, Austin, Texas USA, August 1992.
[16] J.H. B?hn and M.J. Wozny. A topology-based approach for shell-closure. In P.R. Wilson et al., editor, Geometric Modeling for Product Realization, pages
297–319. North-Holland, 1993.
[17] I. M¨akel¨a and A. Dolenc. Some efficient procedures for correcting triangulated models. In H.L. Marcus et al., editor, Proc. Solid Freeform Fabrication Symposium, pages 126–134, U. Texas, Austin, Texas USA,August 1993.
[18] S.M. Morvan and G.M. Fadel. IVECS, interactive correction of .STL files in a virtual environment. In Proc.Solid Freeform Fabrication Symposium, U. Texas,
Austin, Texas USA, August 1996.
[19] T. Murali and T. Funk Houser. Consistent solid and boundary representations from arbitrary polygonal data. In Symposium on Interactive 3D Graphics, pages
155–162, Providence, RI, 1997.
[20] 朱心雄 自由曲线曲面造型技术 科学出版社
[21] 施法中 计算机辅助几何设计与非均匀有理B样条 北京航空航天大学出版社
[22] 王国谨，汪国昭，郑建民 计算机辅助几何设计 高等教育出版社 施普林格出版社
[23] RC Veltkamp, W Wesselink. Modeling 3D curves of minimal energy. Computer Graphics Forum, 1995 , 13(3)：98-110
[24] G Greiner, J Loos, W Wesselink. Data dependent thin plate energy and its use in interactive surface design. Computer Graphics Forum, 1996,15(3): 175-185
[25] ZhuXiang, HuShimin, SunJiaguang. Shape modification of surface via external energy constraints [J]. Journal of Computer-Aided Design &Computer Graphics, 2000,12(9) :651～655 (in Chinese) (朱 翔，胡事民，孙家广。基于外部能量约束的曲面形状修改[J]。计算机辅助设计与图形学学报，2000，12(9)：651～655)
[26] 龙小平 局部能量最优法与曲线曲面的光顺 计算机辅助设计与图形学学报 Vol.14, No.12 Dec., 2002 1109～1112。
[27] Antonio E. Uva, Giuseppe Monno, Bernd Hamann, A New Method for the Repair of CAD Data with Discontinuities, CIPIC
[28] Geoffrey Butlin and Clive Stops ，CAD Data Repair， FEGS Ltd。
[29] Gill Barequet Subodh Kumar ，Repairing CAD Models ，Johns Hopkins University
[30] Ernst H. Huber, Intersecting General Parametric Surface Using Bounding Volumes, Vienna University Of Technology
[2] Farin G. (1997), Curves and Surfaces for Computer Aided Geometric Design -- A Practical Guide, 4th ed., Academic Press, Boston, Massachusetts.
[3] Bartels, R. H., Beatty, J. C. and Barsky, B. A. (1987), An Introduction to Splines for Use in Computer Graphics and Geometric Modeling, Morgan Kaufman Publishers, Inc., Los Altos, California.
[4] Boehm, W. and Prautzsch, H. (1994), Geometric Concepts for Geometric Design, A K Peters, Wellesley, Massachusetts.
[5] de Boor, C. (1978), A Practical Guide to Splines, Applied Mathematical Sciences, Vol. 27,Springer-Verlag, New York, New York.
[6] Hamann, B. (1994), Construction of B-spline approximations for use in numerical grid generation, Applied Mathematics and Computation 65(1--2), pp. 295--314.
[7] Hoschek, J. and Lasser, D. (1993), Fundamentals of Computer Aided Geometric Design, A K Peters, Ltd., Wellesley, Massachusetts.
[8] Piegl, L. A. and Tiller, W. (1996), The NURBS Book, 2nd edition, Springer-Verlag, New York., New York.
[9] Sharir .M and Barequet Piecewise-linear interpolation between polygorhron slices Technical Report 275/1993 Department of Computer Science, Tel Aviv University
[10] G. Barequet and M. Sharir. Filling gaps in the boundary of a polyhedron.
Computer Aided Geometric Design,12(2):207–229, 1995.
[11] 张丽艳，潘小林，安鲁豫，网格曲面中孔洞的光滑填充算法的研究 工程图学学报 2002（4）113～119
[12] S.M. Morvan and G.M. Fadel. IVECS: An interactive virtual environment for the correction of .STL files。In Conference on Virtual Design, U. California, Irvine, August 1996.
[13] G. Turk and M. Levoy. Zippered polygon meshes from range images In Proceedings of ACM SIGGRAPH, pages 311–318, 1994.
[14] S. J. Rock and M. J. Wozny. Generating topological information from a ’bucket
of facets’. In H.L. Marcus et al., editor, Proc. Solid Freeform Fabrication Symposium, pages 251–259, U. Texas, Austin, Texas USA, August 1992.
[15] J.H. B?hn and M.J. Wozny. Automatic cad-model repair: Shell-closure. In H.L. Marcus et al., editor, Proc.Solid Freeform Fabrication Symposium, pages 86–94,U. Texas, Austin, Texas USA, August 1992.
[16] J.H. B?hn and M.J. Wozny. A topology-based approach for shell-closure. In P.R. Wilson et al., editor, Geometric Modeling for Product Realization, pages
297–319. North-Holland, 1993.
[17] I. M¨akel¨a and A. Dolenc. Some efficient procedures for correcting triangulated models. In H.L. Marcus et al., editor, Proc. Solid Freeform Fabrication Symposium, pages 126–134, U. Texas, Austin, Texas USA,August 1993.
[18] S.M. Morvan and G.M. Fadel. IVECS, interactive correction of .STL files in a virtual environment. In Proc.Solid Freeform Fabrication Symposium, U. Texas,
Austin, Texas USA, August 1996.
[19] T. Murali and T. Funk Houser. Consistent solid and boundary representations from arbitrary polygonal data. In Symposium on Interactive 3D Graphics, pages
155–162, Providence, RI, 1997.
[20] 朱心雄 自由曲线曲面造型技术 科学出版社
[21] 施法中 计算机辅助几何设计与非均匀有理B样条 北京航空航天大学出版社
[22] 王国谨，汪国昭，郑建民 计算机辅助几何设计 高等教育出版社 施普林格出版社
[23] RC Veltkamp, W Wesselink. Modeling 3D curves of minimal energy. Computer Graphics Forum, 1995 , 13(3)：98-110
[24] G Greiner, J Loos, W Wesselink. Data dependent thin plate energy and its use in interactive surface design. Computer Graphics Forum, 1996,15(3): 175-185
[25] ZhuXiang, HuShimin, SunJiaguang. Shape modification of surface via external energy constraints [J]. Journal of Computer-Aided Design &Computer Graphics, 2000,12(9) :651～655 (in Chinese) (朱 翔，胡事民，孙家广。基于外部能量约束的曲面形状修改[J]。计算机辅助设计与图形学学报，2000，12(9)：651～655)
[26] 龙小平 局部能量最优法与曲线曲面的光顺 计算机辅助设计与图形学学报 Vol.14, No.12 Dec., 2002 1109～1112。
[27] Antonio E. Uva, Giuseppe Monno, Bernd Hamann, A New Method for the Repair of CAD Data with Discontinuities, CIPIC
[28] Geoffrey Butlin and Clive Stops ，CAD Data Repair， FEGS Ltd。
[29] Gill Barequet Subodh Kumar ，Repairing CAD Models ，Johns Hopkins University
[30] Ernst H. Huber, Intersecting General Parametric Surface Using Bounding Volumes, Vienna University Of Technology