隐式曲面光滑拼接与数据场可视化
|
摘要
在计算机辅助几何设计(CAGD)领域中,熟知有两种定义曲面的方法,即参数形式与隐式形式。所谓隐式曲面,是指用实系数三元代数多项式的零点(f(x,y,z)=0)所定义的曲面,故也称其为代数曲面。参数形式的曲面以其构造简单计算容易等特点而流行于世并成为几何设计的主流。与参数形式的曲面相比,隐式形式有如下优点:隐式形式的曲面表示易于判别一个点是否在曲面上,易于表示封闭的形体,在几何操作下运算封闭;任何参数形式或隐式形式的曲面间的几何运算的结果均可表示成隐式形式。基于隐式形式的上述优点,光滑拼接隐式曲线曲面的研究显得具有重大的意义。
等值线和等值面作为一类常见的隐式曲线和曲面,其应用价值受到越来越多的关注。等值线和等值面技术在可视化中应用广泛,许多标量场中的可视化问题都归纳为等值线和等值面的抽取和绘制,Marching Cubes方法是目前应用最为广泛的等值面抽取方法之一。
本文阐述了MC算法的基本原理,讨论了其优缺点和产生这些优缺点的原因。算法在构造等值面的过程中,太依赖于直观的构造,构建体元状态模型时,对于对称,旋转等情况的处理缺乏全面考虑,忽视了立方体内部可能存在的环状结构和存在的临界点(等值面发生变化的点),直接使用求得的边界等值点,根据基本的体元状态模型,简单连接成三角片构成等值面,导致生成的等值面拓扑结构不一致,不能满足实际应用中的需求。
本文针对MC算法的缺点,将研究多元样条函数的光滑余因子方法引入到MC算法中,首先对数据场进行正方形或立方体剖分,得到MC算法需要的正方形单元或立方体体元。接着建立了单元和体元间光滑连接所应满足的协调条件,进而使求隐式曲线曲面光滑拼接等问题转化为求解协调方程的问题。通过构造插值适定结点组,进而完成了多元样条函数的插值问题,求得了各单元和体元内的具体样条函数表达式。继续利用MC方法对给定值的样条函数进行等值线或等值面的抽取,分别实现了正方形单元间二次隐式曲线段的C~1光滑拼接和三次隐式曲线段的C~1光滑拼接,进而实现了立方体体元间二次隐式曲面片的C~1光滑拼接和三次隐式曲面片的C~1光滑拼接,即抽取的等值线和等值面在整个数据场达到C~1连续。
In the field of the Computer Aided Geometric Design(CAGD),surfaces can be classified into two categories:parametric surfaces and implicit surfaces.An implicit surface refers to the surface that is defined by the set of solutions of a real coefficient algebraic polynomial equation(f(x,y,z)=0);therefore we also call it the algebraic surface.The parameter surfaces have been at the center of research in geometric design for a long time due to their highly desirable properties such as the simple structure and easy computation. Compares with the parameter surface,the implicit surface has the following advantages: easily to judge a point in the surface,and the closure property under some geometric operations;for a parametric surface and an implicit surface,all results under geometric operations are denoted to implicit surfaces.Based on these advantages of implicit surfaces,it is very significant to study smoothly blending implicit algebraic curves and surfaces.
Contour and iso-surface as common implicit algebraic curves and surfaces,its application value received more and more attention.Contour and iso-surface technology is widely used in visualization and many scalar field visualization problems can be solved by isosurfacing and rendering.Marching cubes algorithm is the most widely used iso-surface method till now.
This paper introduces the basic principle of marching cubes algorithm,then gives out the definition,the disadvantages and advantages of the algorithms and explains how these problems are brought about.In the process of isosurfacing,the algorithm doesn't deal with the complexity of iso-surface in the voxel,and takes the triangles as iso-surfaces.However,an iso-surface should change its shape at some critical points and loops.Therefore,the iso-surface algorithm may encounter many problems in topology,precision and efficiency and can not satisfy many applications.
In order to overcome the disadvantages of marching cubes algorithm,this paper incorporates spline function of smoothing cofactor into marching cubes algorithm.First,the data field is discretized into square or cube cells,and then the coordination conditions of element or voxel smooth connection are established.As a result,the smooth blending problems of implicit curves and surfaces are transformed into the problem to solve the coordination equations.By constructing a well-posed interpolation node group,the problem of multi-spline interpolation is successfully solved,and the specific expression of spline for unit element and voxel is obtained.And then using the marching cubes algorithm,the contour or iso-surface is extracted for a given value of the spline function.The C~1 smooth blending of quadratic implicit curve segments and the C~1 smooth blending of cubic implicit curve segments is achieved within element respectively,thereby the C~1 smooth blending of quadratic implicit surface patches and the C~1 smooth blending of cubic implicit surface patches is realized within voxel,which means that the contour and iso-surface reach the C~1 smooth continuous in the entire data fields.
等值线和等值面作为一类常见的隐式曲线和曲面,其应用价值受到越来越多的关注。等值线和等值面技术在可视化中应用广泛,许多标量场中的可视化问题都归纳为等值线和等值面的抽取和绘制,Marching Cubes方法是目前应用最为广泛的等值面抽取方法之一。
本文阐述了MC算法的基本原理,讨论了其优缺点和产生这些优缺点的原因。算法在构造等值面的过程中,太依赖于直观的构造,构建体元状态模型时,对于对称,旋转等情况的处理缺乏全面考虑,忽视了立方体内部可能存在的环状结构和存在的临界点(等值面发生变化的点),直接使用求得的边界等值点,根据基本的体元状态模型,简单连接成三角片构成等值面,导致生成的等值面拓扑结构不一致,不能满足实际应用中的需求。
本文针对MC算法的缺点,将研究多元样条函数的光滑余因子方法引入到MC算法中,首先对数据场进行正方形或立方体剖分,得到MC算法需要的正方形单元或立方体体元。接着建立了单元和体元间光滑连接所应满足的协调条件,进而使求隐式曲线曲面光滑拼接等问题转化为求解协调方程的问题。通过构造插值适定结点组,进而完成了多元样条函数的插值问题,求得了各单元和体元内的具体样条函数表达式。继续利用MC方法对给定值的样条函数进行等值线或等值面的抽取,分别实现了正方形单元间二次隐式曲线段的C~1光滑拼接和三次隐式曲线段的C~1光滑拼接,进而实现了立方体体元间二次隐式曲面片的C~1光滑拼接和三次隐式曲面片的C~1光滑拼接,即抽取的等值线和等值面在整个数据场达到C~1连续。
In the field of the Computer Aided Geometric Design(CAGD),surfaces can be classified into two categories:parametric surfaces and implicit surfaces.An implicit surface refers to the surface that is defined by the set of solutions of a real coefficient algebraic polynomial equation(f(x,y,z)=0);therefore we also call it the algebraic surface.The parameter surfaces have been at the center of research in geometric design for a long time due to their highly desirable properties such as the simple structure and easy computation. Compares with the parameter surface,the implicit surface has the following advantages: easily to judge a point in the surface,and the closure property under some geometric operations;for a parametric surface and an implicit surface,all results under geometric operations are denoted to implicit surfaces.Based on these advantages of implicit surfaces,it is very significant to study smoothly blending implicit algebraic curves and surfaces.
Contour and iso-surface as common implicit algebraic curves and surfaces,its application value received more and more attention.Contour and iso-surface technology is widely used in visualization and many scalar field visualization problems can be solved by isosurfacing and rendering.Marching cubes algorithm is the most widely used iso-surface method till now.
This paper introduces the basic principle of marching cubes algorithm,then gives out the definition,the disadvantages and advantages of the algorithms and explains how these problems are brought about.In the process of isosurfacing,the algorithm doesn't deal with the complexity of iso-surface in the voxel,and takes the triangles as iso-surfaces.However,an iso-surface should change its shape at some critical points and loops.Therefore,the iso-surface algorithm may encounter many problems in topology,precision and efficiency and can not satisfy many applications.
In order to overcome the disadvantages of marching cubes algorithm,this paper incorporates spline function of smoothing cofactor into marching cubes algorithm.First,the data field is discretized into square or cube cells,and then the coordination conditions of element or voxel smooth connection are established.As a result,the smooth blending problems of implicit curves and surfaces are transformed into the problem to solve the coordination equations.By constructing a well-posed interpolation node group,the problem of multi-spline interpolation is successfully solved,and the specific expression of spline for unit element and voxel is obtained.And then using the marching cubes algorithm,the contour or iso-surface is extracted for a given value of the spline function.The C~1 smooth blending of quadratic implicit curve segments and the C~1 smooth blending of cubic implicit curve segments is achieved within element respectively,thereby the C~1 smooth blending of quadratic implicit surface patches and the C~1 smooth blending of cubic implicit surface patches is realized within voxel,which means that the contour and iso-surface reach the C~1 smooth continuous in the entire data fields.
引文
[1]Buchberger B.Grobner bases:An algorithmic method in polynomial ideal theory.Multidimensional Systems Theory,1985:184-232. [2]吴文俊.初等几何判定问题与机械化证明.北京:中国科学出版社,1977:507-516. [3]Rossignac J R and Requicha A G.Constant-radius blending in solid modeling.Computer Mechanical Engineering,1984:65-73. [4]Rockwood A,Owen J,Farin G,ed al.Blending surfaces in solid modeling.Geometric Modeling,Philadephia:SIAM publications,1985:231-238. [5]Middleditch A and Sears K.Blending surfaces for set the oreticvolume modeling system.Computer Graphics,1985,19(3):161-170. [6]Hoffmann C and Hopcroft J.Quadratic blending surfaces.Computer Aided Design,1986:301-307. [7]Warren J.On Algebraic Surfaces Meeting with Geometric Continuity.Department of Computer Science,Cornell University,Ithaca,New York,1986. [8]Warren J.Blending algebraic surfaces.ACM Transactions Graphics,1989,8(4):263-278. [9]Li J,Hoschek J and Hartmann E.G~(n-1) functional splines for interpolation and approximation of curves,surfaces and solids.Computer Aided Geometric Design,1990:209-220. [10]Bajaj C and Ihm I.Algebraic Surfaces Design with Hermite Interpolation.ACM Transactions on Graphics,1992:61-91. [11]Wu Wen-Tsun.On Surface-Fitting Problem in CAGD,MM-Rer.Prepprints,1993:1-11. [12]Wu Tie-ru,GAO Wei-guo,Feng Guo-chen.Blending of Implicit Algebraic Surface,Proceedings of ASCM'95.Beijing,China,1995:125-131. [13]Wu Tie-ru.On blending of several quadratic algebraic surfaces.Computer Aided Geometric Design,2000:759-766. [14]Chen F L,Chen C S,Deng J S.Blending pipe surfaces with piecewise algebraic surfaces.Chinese Journal Computers,2000,23(9):911-916. [15]Hartmann E.Implicit blending of vertices.Computer Aided Geometric Design,2001:267-285. [16]娄文平,冯玉瑜,陈发来,邓建松.构造代数曲面的Grobner基方法.《计算机学报》,2002,第25卷599-605. [17]汤兴.代数曲面造型的研究:(博士学位论文).合肥:中国科学技术大学
,2002. [18]厉玉蓉.多个二次隐式曲面的最低次光滑拼接曲面的构造理论与算法:(博士学位论文).吉林:吉林大学,2003.
[19]解滨.三个二次曲面的光滑拼接及一类四次隐式代数曲面的参数化:(硕士学位论文).吉林:吉林大学,2004.
[20]张晖.三个二次曲面的隐式光滑拼接代数曲面的参数化:(硕士学位论文).吉林:吉林大学,2005.
[21]吕萌.三个二次曲面光滑拼接的算法实现:(硕士学位论文).吉林:吉林大学,2005.
[22]徐晨东.代数曲线曲面设计与造型的研究:(博士学位论文).合肥:中国科学技术大学,2006.
[23]王东明、杨路、李志斌、候晓荣、陈发来、夏壁灿、支丽红.符号计算选讲.北京:清华大学出版社,2003:150-192.
[24]吴文俊,王定康.CAGD中的代数曲面拟合问题.数学的实践与认识,1994,(3):26-31.
[25]Garrity T,Warren J.Geometric continuity.Computer Aided Geometric,1991:51-65.
[26]石教英,蔡文立.科学计算可视化算法与系统.北京:科学出版社,1996:116-124.
[27]唐泽圣.三维数据场可视化.北京:清华大学出版社,1999.
[28]田捷,包尚联,周明全.医学影像处理与分析.北京:电子工业出版社,2003.
[29]Lorensen W E,Cline H E.Marching cubes:A high resolution 3D surface construction algorithm.Computer Graphics,1987,21(4):163-169.
[30]Lorensen W E,Cline H E,Ludke S,et al.Two algorithms for the three-dimensional reconstruction of tomograms,Medical Physics,1988,15(3):320-327.
[31]Neilson G M,Hamann B.The Asymptotic Decider:Resolving the Ambiguity in Marching Cubes.Proceedings IEEE Visualization,1991:83-91.
[32]Doi A,Koide A.An Efficient Method of Triangulating Equi-Valued Surfaces by Using Tetrahedral Cells.IEICE Transactions,1992,74(1):214-224.
133]Chin-feng Lin,Don-Lin Yang,Yeh-ching Chung.A Marching Voxels Method for Surface Rendering of Volume Data.IEEE Transactions on Visualization and Computer Graphics,2001:306-313.
[34]Allen V G,Wilhelms J.Topological considerations in isosurface generation.ACM Transactions on Graphics,1994,13(4):337-375.
[35]Brodlie K,Wood J.Recent advances in volume visualization.Computer Graphics,2001,20(2):125-148.
[36]Durst M J.Additional reference to Marching Cubes.ACM Computer Graphics,1988,22(2):72-73.
[37]Natarajan B K.On generating topologically consistent isosurface from uniform Samples,The Visual Computer,1994,11(1):52-62.
[38]Nielson G,Hamann B.The asymptotic decider:resolving the ambiguity in marching cubes.Proceedings of Visualization'91,Los Alamitos CA,1991:83-91.
[39]Lopes A,Brodlie K.Improving the robustness and accuracy of the marching cubes algorithm for isosurfacing.IEEE Transactions on Visualization and Computer Graphics,2003,9(1):16-29.
[40]Cignoni P,Ganovelli F,Montani,et al.Reconstruction of topologically correct and adaptive trilinear surfaces.Computers and Graphics,2000,24(3):399-418.
[41]王仁宏.多元齿的结构与插值.数学学报,1975,18(2):91-106.
[42]王仁宏.任意剖分下的多元样条分析.中国科学.数学专辑Ⅰ,1979:215-226.
[43]王仁宏.任意剖分下的多元样条分析(Ⅱ)-空间形式.高等学校计算数学学报,1980,1:78-81.
[44]王仁宏,何天晓.拟贯穿剖分下多元样条空间基.中国科学.A辑,1986,1:19-25.
[45]王仁宏.关于多元样条空间的维数.科学通报.1988,6:473-474.
[46]Schumaker L L.Bounds on the dimension of spaces of multivariate piecewise polynomials.Rocky Mountain Journal Mathematics,1984,14:251-264.
[47]Chin C K,Wang R H.Multivariate spline spaces.Journal Mathematics Analyses Applications,1983,94:197-221.
[48]Farin G.Triangular Bernstein-Bezier patches.Computer Aided Geometric Design,1986,3:83-127.
[49]Curry H B,Schoenberg I J.On ploy frequency functions and their limits.Journal Analyses Mathematics,1966,17:71-107.
[50]Boor C D.Splines as linear combination of B-splines.In:Chui C K,ed.Approximation Theory Ⅱ.Academic Press,New York,1976:1-47.
[51]王仁宏,梁学章.多元函数逼近.北京:科学出版社,1988:121-153.
[52]王仁宏.数值逼近.北京:高等教育出版社,1999:244-246.
[53]张晓丹,堵秀凤等.Maple的图形动画技术.北京:北京航空航天大学出版社,2005.
,2002. [18]厉玉蓉.多个二次隐式曲面的最低次光滑拼接曲面的构造理论与算法:(博士学位论文).吉林:吉林大学,2003.
[19]解滨.三个二次曲面的光滑拼接及一类四次隐式代数曲面的参数化:(硕士学位论文).吉林:吉林大学,2004.
[20]张晖.三个二次曲面的隐式光滑拼接代数曲面的参数化:(硕士学位论文).吉林:吉林大学,2005.
[21]吕萌.三个二次曲面光滑拼接的算法实现:(硕士学位论文).吉林:吉林大学,2005.
[22]徐晨东.代数曲线曲面设计与造型的研究:(博士学位论文).合肥:中国科学技术大学,2006.
[23]王东明、杨路、李志斌、候晓荣、陈发来、夏壁灿、支丽红.符号计算选讲.北京:清华大学出版社,2003:150-192.
[24]吴文俊,王定康.CAGD中的代数曲面拟合问题.数学的实践与认识,1994,(3):26-31.
[25]Garrity T,Warren J.Geometric continuity.Computer Aided Geometric,1991:51-65.
[26]石教英,蔡文立.科学计算可视化算法与系统.北京:科学出版社,1996:116-124.
[27]唐泽圣.三维数据场可视化.北京:清华大学出版社,1999.
[28]田捷,包尚联,周明全.医学影像处理与分析.北京:电子工业出版社,2003.
[29]Lorensen W E,Cline H E.Marching cubes:A high resolution 3D surface construction algorithm.Computer Graphics,1987,21(4):163-169.
[30]Lorensen W E,Cline H E,Ludke S,et al.Two algorithms for the three-dimensional reconstruction of tomograms,Medical Physics,1988,15(3):320-327.
[31]Neilson G M,Hamann B.The Asymptotic Decider:Resolving the Ambiguity in Marching Cubes.Proceedings IEEE Visualization,1991:83-91.
[32]Doi A,Koide A.An Efficient Method of Triangulating Equi-Valued Surfaces by Using Tetrahedral Cells.IEICE Transactions,1992,74(1):214-224.
133]Chin-feng Lin,Don-Lin Yang,Yeh-ching Chung.A Marching Voxels Method for Surface Rendering of Volume Data.IEEE Transactions on Visualization and Computer Graphics,2001:306-313.
[34]Allen V G,Wilhelms J.Topological considerations in isosurface generation.ACM Transactions on Graphics,1994,13(4):337-375.
[35]Brodlie K,Wood J.Recent advances in volume visualization.Computer Graphics,2001,20(2):125-148.
[36]Durst M J.Additional reference to Marching Cubes.ACM Computer Graphics,1988,22(2):72-73.
[37]Natarajan B K.On generating topologically consistent isosurface from uniform Samples,The Visual Computer,1994,11(1):52-62.
[38]Nielson G,Hamann B.The asymptotic decider:resolving the ambiguity in marching cubes.Proceedings of Visualization'91,Los Alamitos CA,1991:83-91.
[39]Lopes A,Brodlie K.Improving the robustness and accuracy of the marching cubes algorithm for isosurfacing.IEEE Transactions on Visualization and Computer Graphics,2003,9(1):16-29.
[40]Cignoni P,Ganovelli F,Montani,et al.Reconstruction of topologically correct and adaptive trilinear surfaces.Computers and Graphics,2000,24(3):399-418.
[41]王仁宏.多元齿的结构与插值.数学学报,1975,18(2):91-106.
[42]王仁宏.任意剖分下的多元样条分析.中国科学.数学专辑Ⅰ,1979:215-226.
[43]王仁宏.任意剖分下的多元样条分析(Ⅱ)-空间形式.高等学校计算数学学报,1980,1:78-81.
[44]王仁宏,何天晓.拟贯穿剖分下多元样条空间基.中国科学.A辑,1986,1:19-25.
[45]王仁宏.关于多元样条空间的维数.科学通报.1988,6:473-474.
[46]Schumaker L L.Bounds on the dimension of spaces of multivariate piecewise polynomials.Rocky Mountain Journal Mathematics,1984,14:251-264.
[47]Chin C K,Wang R H.Multivariate spline spaces.Journal Mathematics Analyses Applications,1983,94:197-221.
[48]Farin G.Triangular Bernstein-Bezier patches.Computer Aided Geometric Design,1986,3:83-127.
[49]Curry H B,Schoenberg I J.On ploy frequency functions and their limits.Journal Analyses Mathematics,1966,17:71-107.
[50]Boor C D.Splines as linear combination of B-splines.In:Chui C K,ed.Approximation Theory Ⅱ.Academic Press,New York,1976:1-47.
[51]王仁宏,梁学章.多元函数逼近.北京:科学出版社,1988:121-153.
[52]王仁宏.数值逼近.北京:高等教育出版社,1999:244-246.
[53]张晓丹,堵秀凤等.Maple的图形动画技术.北京:北京航空航天大学出版社,2005.