利用几何求交实现三角网格模型快速体素化  

Fast Voxelization of Triangulated Irregular Network Model Using Geometric Intersection Computation

作　　者：吴耕宇[1] 潘懋[1] 郭艳军[1] 

机构地区：[1]北京大学地球与空间科学学院造山带与地壳演化教育部重点实验室,北京100871

出　　处：《计算机辅助设计与图形学学报》2015年第11期2133-2141,共9页Journal of Computer-Aided Design & Computer Graphics

基　　金：国土资源部"十二五"重点项目(1212011220352;1212011087157)

摘　　要：为解决现有的三角网格模型体素化算法存在的体素寻找不全或者体素化效率不高的问题,提出一种快速的三角网格模型体素化算法.该算法分为表面体素化和内部体素化2个步骤:表面体素化使用几何求交方法快速寻找三角形与全部体素的相交多边形顶点,并将这些顶点和与三角形相交的体素一一对应,得到每一个三角形的相交体素,从而得到与三角网表面相交的全部体素;内部体素化使用同时填充内部和外部体素的扫描线种子填充算法,填充过程中使用变长队列,在保持算法的正确性和效率的同时大幅减小算法的空间复杂度.使用三角形数量较多的模型进行高分辨率体素化的实验结果表明,文中算法耗时短,在三角形数量较多时体素化效率显著提高.To solve the problems of the existing triangulated irregular network (TIN) model voxelization al-gorithms which could not find all required voxels or had a poor time efficiency in some cases, a fast TIN model voxelization algorithm was proposed. This algorithm has 2 steps: surface voxelization and solid vox-elization. In the surface voxelization step, all triangles are voxelized by using single triangle voxelization algorithm based on geometric intersection computation. The single triangle voxelization algorithm computes all vertices of the triangle-cross-voxel polygons, and corresponds the vertices to the voxels; In the solid voxelization step, the seed fill approach based on scan line and length-changeable queue structure is used to fill all voxels inside and outside the TIN model, which spends less memory. Experimental results show that this algorithm has a good time efficiency when voxelizing precise model and TIN model with more triangles.

关 键 词：不规则三角网 体素化 几何求交 种子填充 扫描线 队列结构 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]