一种网格拓扑关系的三角网切割算法
|
摘要
针对目前的三角网切割效率不高的问题,该文提出了一种网格拓扑关系搜索的三角网模型切割方法。利用三角网模型中三角形的索引和顶点索引,构建边的索引,从而构建点索引、边索引和三角形索引之间的拓扑关系,最终形成三维模型的"边-顶点-邻接三角形的拓扑关系"。根据当前屏幕范围,提取三维视景体内的三角形,利用GPU并行运算,快速获取离视点最近的三角形索引,从而获取到所有三角网中的第一层三角网,并根据拓扑关系提取边界三角形,再利用基于边的约束对边界三角形进行重新剖分。实验结果表明,该方法可以快速准确地完成离视点最近的三角网模型表面的切割。
To the problem of a triangular mesh model cutting efficiency,a triangular mesh model cutting method for grid topology search was proposed In this paper.By using the index and vertex index of triangles,the index of the edge was constructed and the topological relationship between the point index,edge index and triangle index was constructed,and the "edge vertex-adjacency triangle topology"of the 3 D model was finally formed.According to the current screen range,the triangle in the 3 Dscene was extracted,and the GPU parallel operation was used to quickly obtain the nearest triangle index from the view point,thus obtaining the first triangulation net in all the triangulation networks,extracting the boundary triangle according to the topological relation,and reconstructing the boundary triangle by the edge based constraint.Experimental results showed that the method could quickly and accurately cut the surface of the nearest triangulation model.
To the problem of a triangular mesh model cutting efficiency,a triangular mesh model cutting method for grid topology search was proposed In this paper.By using the index and vertex index of triangles,the index of the edge was constructed and the topological relationship between the point index,edge index and triangle index was constructed,and the "edge vertex-adjacency triangle topology"of the 3 D model was finally formed.According to the current screen range,the triangle in the 3 Dscene was extracted,and the GPU parallel operation was used to quickly obtain the nearest triangle index from the view point,thus obtaining the first triangulation net in all the triangulation networks,extracting the boundary triangle according to the topological relation,and reconstructing the boundary triangle by the edge based constraint.Experimental results showed that the method could quickly and accurately cut the surface of the nearest triangulation model.
引文
[1]杨洋.三维GIS表面模型切割算法研究[D].南京:南京师范大学,2012.(YANG Yang.3D GIS surfacemodel cutting algorithm research[D].Nanjing:NanjingNormal University,2012.)
[2]NIENHUYS H W,STAPPEN A F V D.A Delaunayapproach to interactive cutting in triangulated surfaces[R].Berlin:Springer Tracts in Advanced Robotics,2002,7:113-130.
[3]KALLMANN M,BIERI H,THALMANN D.Fullydynamic constrained delaunay triangulations[R].Berlin:Springer Berlin Heidelberg,2010:28-35.
[4]陈小桥,章虎,谢红生.三角网格模型的快速剖切方法[J].武汉理工大学学报,2010,32(21):119-122.(CHENXiaoqiao,ZHANG Hu,XIE Hongsheng.A fast cuttingmethod for triangular meshes[J].Journal of Wuhan Uni-versity of Technology,2010,32(21):119-122.)
[5]BATAGELO H C,COSTA I J,et al.Real time shadowgeneration using BSP trees and stencil buffers[C]∥Brazilian Symposium on Computer Graphics and ImageProcessing.Campinas.Brazil:IEEE,2012:93-102.
[6]CARR N A,HOBEROCK J,CRANE K.et al.FastGPU ray tracing of dynamic meshes using geometryimages[C]∥Proceedings of Graphics Interface.Toronto:[s.n.],2013:25-30.
[7]钱波,张李超,史玉升,等.基于STL模型的表面区域递归拾取算法[J].华中科技大学学报(自然科学版),2008,36(9):90-93.(QIAN Bo,ZHANG Lichao,SHIYusheng,et al.Surface region recurrence picking upalgorithm based on stereolithography model[J].Journalof Huazhong University of Science and Technology(Nature Science),2008,36(9):90-93.)
[8]徐鹏.海量三维点云数据的组织与可视化研究[D].南京:南京师范大学,2013.(XU Peng.Research onorganization and visualization of massive 3Dpoint clouddata[D].Nanjing:Nanjing Normal University,2013.)
[9]姚莉,高瞻,肖健,等.3D图形编程基础-基于DirectX11[M].北京:清华大学出版社,2012.(YAO Li,GAOZhan,XIAO Jian,et al.3D graphic programmingfoundation-based on DirectX11[M].Beijing:TsinghuaUniversity Press,2012.)
[10]WANG J CUI C,GAO J.An efficient algorithm forclipping operation based on trapezoidal meshes andsweep-line technique[J].Advances in EngineeringSoftware,2012,1(47):72-79.
[11]FBIN G,GERGL.Fast algorithm to split andreconstruct triangular meshes[C]∥Conference onMathematics and Computer Science,[S.l.:s.n.],2014:90.
[12]PUPYREV S,NACHMANSON L,BEREG S.Edgerouting with ordered bundles[C]∥InternationalSymposium on Graph Drawing.[S.l.:s.n.],2011:136-147.
[13]YAN D Y,WANG W,LVY B,et al.Efficient compu-tation of clipped Voronoi diagram for mesh generation[J].Computer-Aided Design,2013,45(4):843-852.
[14]BOLAOS G S,BEDI S,MANN S et al.A topological-free method for three-axis tool path planning for genera-lized radi used end milled cutting of a triangular meshsurface[J].International Journal of Advanced Manu-facturing Technology,2014,70(9/12):1813-1825.
[15]WANG B,KHOO B C,XIE Z Q,et al.Fast centroidalvoronoi Delaunay triangulation for unstructured meshgeneration[J].Journal of Computational &AppliedMathematics,2015,280(C):158-173.
[16]ZHOU Y F,ZHANG C M,BO P B.Efficient tetra-hedral mesh generation based on sampling optimization[J].Computer Animation &Virtual Worlds,2016,26(6):577-587.
[17]KOWALCZYK P.Complex root finding algorithmbased on Delaunay triangulation[J].ACM Tran-sactions on Mathematical Software,2015 41(3):1-13.
[18]LUNA F.Introduction to 3Dgame programming withdirect X11[M].Mercury Learning &Information.[S.l.:s.n.],2012.
[2]NIENHUYS H W,STAPPEN A F V D.A Delaunayapproach to interactive cutting in triangulated surfaces[R].Berlin:Springer Tracts in Advanced Robotics,2002,7:113-130.
[3]KALLMANN M,BIERI H,THALMANN D.Fullydynamic constrained delaunay triangulations[R].Berlin:Springer Berlin Heidelberg,2010:28-35.
[4]陈小桥,章虎,谢红生.三角网格模型的快速剖切方法[J].武汉理工大学学报,2010,32(21):119-122.(CHENXiaoqiao,ZHANG Hu,XIE Hongsheng.A fast cuttingmethod for triangular meshes[J].Journal of Wuhan Uni-versity of Technology,2010,32(21):119-122.)
[5]BATAGELO H C,COSTA I J,et al.Real time shadowgeneration using BSP trees and stencil buffers[C]∥Brazilian Symposium on Computer Graphics and ImageProcessing.Campinas.Brazil:IEEE,2012:93-102.
[6]CARR N A,HOBEROCK J,CRANE K.et al.FastGPU ray tracing of dynamic meshes using geometryimages[C]∥Proceedings of Graphics Interface.Toronto:[s.n.],2013:25-30.
[7]钱波,张李超,史玉升,等.基于STL模型的表面区域递归拾取算法[J].华中科技大学学报(自然科学版),2008,36(9):90-93.(QIAN Bo,ZHANG Lichao,SHIYusheng,et al.Surface region recurrence picking upalgorithm based on stereolithography model[J].Journalof Huazhong University of Science and Technology(Nature Science),2008,36(9):90-93.)
[8]徐鹏.海量三维点云数据的组织与可视化研究[D].南京:南京师范大学,2013.(XU Peng.Research onorganization and visualization of massive 3Dpoint clouddata[D].Nanjing:Nanjing Normal University,2013.)
[9]姚莉,高瞻,肖健,等.3D图形编程基础-基于DirectX11[M].北京:清华大学出版社,2012.(YAO Li,GAOZhan,XIAO Jian,et al.3D graphic programmingfoundation-based on DirectX11[M].Beijing:TsinghuaUniversity Press,2012.)
[10]WANG J CUI C,GAO J.An efficient algorithm forclipping operation based on trapezoidal meshes andsweep-line technique[J].Advances in EngineeringSoftware,2012,1(47):72-79.
[11]FBIN G,GERGL.Fast algorithm to split andreconstruct triangular meshes[C]∥Conference onMathematics and Computer Science,[S.l.:s.n.],2014:90.
[12]PUPYREV S,NACHMANSON L,BEREG S.Edgerouting with ordered bundles[C]∥InternationalSymposium on Graph Drawing.[S.l.:s.n.],2011:136-147.
[13]YAN D Y,WANG W,LVY B,et al.Efficient compu-tation of clipped Voronoi diagram for mesh generation[J].Computer-Aided Design,2013,45(4):843-852.
[14]BOLAOS G S,BEDI S,MANN S et al.A topological-free method for three-axis tool path planning for genera-lized radi used end milled cutting of a triangular meshsurface[J].International Journal of Advanced Manu-facturing Technology,2014,70(9/12):1813-1825.
[15]WANG B,KHOO B C,XIE Z Q,et al.Fast centroidalvoronoi Delaunay triangulation for unstructured meshgeneration[J].Journal of Computational &AppliedMathematics,2015,280(C):158-173.
[16]ZHOU Y F,ZHANG C M,BO P B.Efficient tetra-hedral mesh generation based on sampling optimization[J].Computer Animation &Virtual Worlds,2016,26(6):577-587.
[17]KOWALCZYK P.Complex root finding algorithmbased on Delaunay triangulation[J].ACM Tran-sactions on Mathematical Software,2015 41(3):1-13.
[18]LUNA F.Introduction to 3Dgame programming withdirect X11[M].Mercury Learning &Information.[S.l.:s.n.],2012.