基于离散化的复杂曲面建筑网格划分方法
|
摘要
为实现存在裁剪、孔洞的复杂自由曲面建筑网格划分,提出了一种基于离散的、以均匀性为目标的划分方法.将复杂曲面离散并缝合,形成由大量面片组成的离散曲面,作为多个参数曲面的一体化表示.采用改进的误差扩散算法,在离散曲面上按一定的密度进行初始布点.采用基于空间距离的粒子动力松弛算法对点云进行初步均匀化,并应用基于曲面距离的k均值算法进行再次均匀化.对均匀的点云求曲面距离的Voronoi图,并获得相应网格.对网格进行拓扑优化和光顺优化.算例表明,本文算法可有效处理存在裁剪、孔洞的复杂自由曲面,并得到均匀光顺的三角网格.
A grid generation method for complicated multiple surfaces with trimmings and holes is presented. This method is based on the discretization and concentrates on the aim of homogeneity. The multiple surfaces are discretized separately and seamed together to achieve a discrete surface. The points are distributed on the discrete surface according to the density applying improved error-diffusion method. The points are homogenized by particle dynamics method with Euclid distance and then homogenized once more by k-means algorithm with surface distance. The Voronoi diagram with surface distance is delivered on the discrete surface to obtain the grids. The topological and smooth relaxations are applied on the grids. Eventually, the case study indicates that this method can solve the problem of grid generation for complicated multiple surfaces effectively and achieve the homogeneous and smooth grids.
A grid generation method for complicated multiple surfaces with trimmings and holes is presented. This method is based on the discretization and concentrates on the aim of homogeneity. The multiple surfaces are discretized separately and seamed together to achieve a discrete surface. The points are distributed on the discrete surface according to the density applying improved error-diffusion method. The points are homogenized by particle dynamics method with Euclid distance and then homogenized once more by k-means algorithm with surface distance. The Voronoi diagram with surface distance is delivered on the discrete surface to obtain the grids. The topological and smooth relaxations are applied on the grids. Eventually, the case study indicates that this method can solve the problem of grid generation for complicated multiple surfaces effectively and achieve the homogeneous and smooth grids.
引文
[1]PIEGLL L,TILLER W.The NURBS Book[M].2nd ed.Berlin Heidelberg:Springer-Verlag,1997.
[2]王磊,杨彬,张其林.非均匀有理B样条曲面形状优化方法[J].湖南大学学报(自然科学版),2012,39(7):14—19.WANG L,YANG B,ZHANG Q L.Shape optimization of nonuniform rational B-spline surface[J].Journal of Hunan University(Natural Sciences),2012,39(7):14—19.(In Chinese)
[3]SEDERBERG T W,ZHENG J,BAKENOV A,et al.T-splines and T-NURCCs[J].ACM Transactions on Graphics,2003,22(3):477—484.
[4]OWEN S.A survey of unstructured mesh generation[C]//International Meshing Roundtable.Dearborn,USA:IMR,1998:239—267.
[5]L O HNER R.Progress in grid generation via the advancing front technique[J].Engineering with Computers,1996,12(3):186—210.
[6]BOROUCHAKI H,HECHT F,SALTEL E,et al.Reasonably efficient Delaunay based mesh generator in 3 dimensions[C]//International Meshing Roundtable.South Lake Tahoe,USA:IMR,1999:3—14.
[7]COOK W A,OAKES W R.Mapping method for generating threedimensional meshes:past and present[C]//International Computer Engineering Conference.San Diego,USA:ASME,1982.
[8]熊英,胡于进,赵建军.基于映射法和Delaunay方法的曲面三角网格划分算法[J].计算机辅助设计与图形学学报,2002,14(1):56—60.XIONG Y,HU Y J,ZHAO J J.An algorithm of surface triangulation based on mapping and Delaunay method[J].Journal of Computer-Aided Design&Computer Graphics,2002,14(1):56—60.(In Chinese)
[9]江存,高博青.基于自定义单元法的自由曲面网格划分研究[J].建筑结构,2015,45(5):44—48.JIANG C,GAO B Q.Research on free-form surface meshing based on self-defined element method[J].Building Structure,2015,45(5):44—48.(In Chinese)
[10]SU L,ZHU S,XIAO N,et al.An automatic grid generation approach over free-form surface for architectural design[J].Journal of Central South University,2014,21(6):2444—2453.
[11]危大结,舒赣平.自由曲面网格的划分与优化方法[J].建筑结构,2013,43(19):48—53.WEI D J,SHU G P.Mesh generation and optimization method for free-form surface grid[J].Building Structure,2013,43(19):48—53.(In Chinese)
[12]潘炜,吴慧,李铁瑞,等.基于曲面展开的自由曲面网格划分[J].浙江大学学报(工学版),2016,50(10):1973—1979.PAN W,WU H,LI T R,et al.Grid generation on free-form surface based on surface flattening[J].Journal of Zhejiang University(Engineering Science),2016,50(10):1973—1979.(In Chinese)
[13]SCHALL O,SAMOZINO M,FALCIDIENO B,et al.Surface from scattered points:a brief survey of recent developments[C]//Proccedings of the first international workshop towards Semantic Virtual Environments.Villars,Switzerland:SVE,2005:138—147.
[14]FLOYD R W,STEINBERG L.Adaptive algorithm for spatial greyscale[C]//Proceeding SID.New York,USA:SID,1976:75—77.
[15]ULICHNEY R.Digital halftoning[M].Cambrige,MA:MIT Press,1987:12—13.
[16]VELHO L,GOMES J D M.Digital halftoning with space filling curves[J].ACM SIGGRAPH Computer Graphics,1991,25(4):81—90.
[17]FAN Z.Set of easily implementable coefficients in error diffusion with reduced worm artifacts[C]//Proceeding SPIE.San Jose,USA:SPIE,1996:222—225.
[18]OSTROMOUKHOV V.A simple and efficient error-diffusion algorithm[C]//Proceeding SIGGRAPH.Los Angeles,USA:ACM,2001:567—572.
[19]BRONSON J R,LEVINE J A,WHITAKER R T.Particle systems for adaptive,isotropic meshing of CAD models[J].Engineering with Computers,2012,28(4):331—344.
[20]LLOYD S.Least squares quantization in PCM[J].IEEE Transactions on Information Theory,1982,28(2):129—137.
[21]MACQUEEN J.Some METHODS for classification and analysis of multi variate observations[C]//Proceedings of Berkeley Symposium on Mathematical Statistics and Probability.Oakland,USA:University of California Press,1967:281—297.
[22]MACKAY D.Information theory,inference,and learning algorithms[M].Cambridge,UK:Cambridge University Press,2003:640.
[23]DU Q,FABER V,GUNZBURGER M.Centroidal Voronoi tessellations:applications and algorithms[J].Siam Review,1999,41(4):637—676.
[24]周炎涛,吴正国,易兴东.基于网格带有参考参数的扩展聚类算法[J].湖南大学学报(自然科学版),2009,36(2):48—52.ZHOU Y T,WU Z G,YI X D.Extended grid-based clustering algorithm with referential parameters[J].Journal of Hunan University(Natural Sciences),2009,36(2):48—52.(In Chinese)
[25]FREY W H,FIELD D A.Mesh relaxation:a new technique for improving triangulations[J].International Journal for Numerical Methods in Engineering,1991,31(6):1121—1133.
[26]李基拓,陆国栋.基于边折叠和质点-弹簧模型的网格简化优化算法[J].计算机辅助设计与图形学学报,2006,18(3):426—432.LI J T,LU G D.Mesh simplification and optimization with edge collapse and mass-spring model[J].Journal of Computer-Aided Design&Computer Graphics,2006,18(3):426—432.(In Chinese)
[2]王磊,杨彬,张其林.非均匀有理B样条曲面形状优化方法[J].湖南大学学报(自然科学版),2012,39(7):14—19.WANG L,YANG B,ZHANG Q L.Shape optimization of nonuniform rational B-spline surface[J].Journal of Hunan University(Natural Sciences),2012,39(7):14—19.(In Chinese)
[3]SEDERBERG T W,ZHENG J,BAKENOV A,et al.T-splines and T-NURCCs[J].ACM Transactions on Graphics,2003,22(3):477—484.
[4]OWEN S.A survey of unstructured mesh generation[C]//International Meshing Roundtable.Dearborn,USA:IMR,1998:239—267.
[5]L O HNER R.Progress in grid generation via the advancing front technique[J].Engineering with Computers,1996,12(3):186—210.
[6]BOROUCHAKI H,HECHT F,SALTEL E,et al.Reasonably efficient Delaunay based mesh generator in 3 dimensions[C]//International Meshing Roundtable.South Lake Tahoe,USA:IMR,1999:3—14.
[7]COOK W A,OAKES W R.Mapping method for generating threedimensional meshes:past and present[C]//International Computer Engineering Conference.San Diego,USA:ASME,1982.
[8]熊英,胡于进,赵建军.基于映射法和Delaunay方法的曲面三角网格划分算法[J].计算机辅助设计与图形学学报,2002,14(1):56—60.XIONG Y,HU Y J,ZHAO J J.An algorithm of surface triangulation based on mapping and Delaunay method[J].Journal of Computer-Aided Design&Computer Graphics,2002,14(1):56—60.(In Chinese)
[9]江存,高博青.基于自定义单元法的自由曲面网格划分研究[J].建筑结构,2015,45(5):44—48.JIANG C,GAO B Q.Research on free-form surface meshing based on self-defined element method[J].Building Structure,2015,45(5):44—48.(In Chinese)
[10]SU L,ZHU S,XIAO N,et al.An automatic grid generation approach over free-form surface for architectural design[J].Journal of Central South University,2014,21(6):2444—2453.
[11]危大结,舒赣平.自由曲面网格的划分与优化方法[J].建筑结构,2013,43(19):48—53.WEI D J,SHU G P.Mesh generation and optimization method for free-form surface grid[J].Building Structure,2013,43(19):48—53.(In Chinese)
[12]潘炜,吴慧,李铁瑞,等.基于曲面展开的自由曲面网格划分[J].浙江大学学报(工学版),2016,50(10):1973—1979.PAN W,WU H,LI T R,et al.Grid generation on free-form surface based on surface flattening[J].Journal of Zhejiang University(Engineering Science),2016,50(10):1973—1979.(In Chinese)
[13]SCHALL O,SAMOZINO M,FALCIDIENO B,et al.Surface from scattered points:a brief survey of recent developments[C]//Proccedings of the first international workshop towards Semantic Virtual Environments.Villars,Switzerland:SVE,2005:138—147.
[14]FLOYD R W,STEINBERG L.Adaptive algorithm for spatial greyscale[C]//Proceeding SID.New York,USA:SID,1976:75—77.
[15]ULICHNEY R.Digital halftoning[M].Cambrige,MA:MIT Press,1987:12—13.
[16]VELHO L,GOMES J D M.Digital halftoning with space filling curves[J].ACM SIGGRAPH Computer Graphics,1991,25(4):81—90.
[17]FAN Z.Set of easily implementable coefficients in error diffusion with reduced worm artifacts[C]//Proceeding SPIE.San Jose,USA:SPIE,1996:222—225.
[18]OSTROMOUKHOV V.A simple and efficient error-diffusion algorithm[C]//Proceeding SIGGRAPH.Los Angeles,USA:ACM,2001:567—572.
[19]BRONSON J R,LEVINE J A,WHITAKER R T.Particle systems for adaptive,isotropic meshing of CAD models[J].Engineering with Computers,2012,28(4):331—344.
[20]LLOYD S.Least squares quantization in PCM[J].IEEE Transactions on Information Theory,1982,28(2):129—137.
[21]MACQUEEN J.Some METHODS for classification and analysis of multi variate observations[C]//Proceedings of Berkeley Symposium on Mathematical Statistics and Probability.Oakland,USA:University of California Press,1967:281—297.
[22]MACKAY D.Information theory,inference,and learning algorithms[M].Cambridge,UK:Cambridge University Press,2003:640.
[23]DU Q,FABER V,GUNZBURGER M.Centroidal Voronoi tessellations:applications and algorithms[J].Siam Review,1999,41(4):637—676.
[24]周炎涛,吴正国,易兴东.基于网格带有参考参数的扩展聚类算法[J].湖南大学学报(自然科学版),2009,36(2):48—52.ZHOU Y T,WU Z G,YI X D.Extended grid-based clustering algorithm with referential parameters[J].Journal of Hunan University(Natural Sciences),2009,36(2):48—52.(In Chinese)
[25]FREY W H,FIELD D A.Mesh relaxation:a new technique for improving triangulations[J].International Journal for Numerical Methods in Engineering,1991,31(6):1121—1133.
[26]李基拓,陆国栋.基于边折叠和质点-弹簧模型的网格简化优化算法[J].计算机辅助设计与图形学学报,2006,18(3):426—432.LI J T,LU G D.Mesh simplification and optimization with edge collapse and mass-spring model[J].Journal of Computer-Aided Design&Computer Graphics,2006,18(3):426—432.(In Chinese)