资源描述：
《基于八叉树的三维网格模型体素化方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2005年工程图学学报2005第4期JOURNALOFENGINEERINGGRAPHICSNo.4基于八叉树的三维网格模型体素化方法吴晓军，刘伟军，王天然(中国科学院沈阳自动化研究所先进制造实验室，沈阳110016)摘要：利用八叉树结构的编码特性，提出一种将三维多边形网格模型离散成体素表示。进而产生整个模型的体素表示的算法，提出利用多边形网格轮廓体素和模型内、外体素序列的标志位特性，将三维网格模型内部体素化，纠正了Flooding算法在处理内部封闭空腔时产生的错误。算法可在PC平台上实现。通过证明和实验可知，本算法能产生准确的2
2、6-邻接体素模型，并且具有较高的执行效率，能取得较好的效果。关键词：计算机应用；八叉树；空间剖分；多边形网格模型；体素化中图分类号：TP391.4;TP301文献标识码：A文章编号：1003-0158(2005)04-0001-07迄今为止，计算机辅助设计技术还没有文献[6]应用一个到实体表面的法向矢量的函数突破传统CAD设计系统的局限，只能利用数作为距离标准将多边形模型离散为体素模型。文字化方法来描述零件的表面信息，仅限于单献[7]应用尺度空间理论(Scale-spaceTheory)来获一的均质材料零件的描述。传统三维实体表得
3、点、线、三角面的反走样体素模型。文献[8]示方法如构造实体几何法(CSG)、边界表示法应用距离场(DistanceFields)和距离变换(Distance(B-rep)、扫描表示法等，只能表示出物体的Transform)方法生成体素模型，主要对CT和MRI外表面信息，内部作为均质材料来处理。当等产生的灰度（gray-scale）体数据集分割成体素要描述模型内部属性如密度、材料等时用传模型，便于后续的可视化处理。这些方法都具有统CAD模型将显得无能为力。较快的速度和较好的精度，但一般都在图形工作体素模型为解决这一问题提供了很好的站
4、上实现，硬件要求高，作者的方法在微机平台解决办法，体素化(Voxelization)是将物体的表面上就可以实现，具有较快的速度，能产生准确的几何形式表示转换成最接近该物体的体素表示26-邻接体素模型。形式，产生体数据集(VolumeDatasets)，其不仅包含模型的表面信息，而且能描述模型内部属1数据预处理性。体素(Voxel)可以理解为二维像素在三维空间[1]初始时求出网格模型顶点表中最大、最小值的推广，它们是一组分布在正交网格中心的立方体单元。基于体素的三维模型有诸多应用，例顶点(xmax,ymax,zmax)和(xmin,
5、ymin,zmin)。以这两点为对角顶点构成一包围盒。包围盒沿x，y，z轴的如，医学影像、流体力学、碰撞检测、CSG、地形造型(Terrainmodeling)和机械零件造型和制造长度分别为：Lx=xmax-xmin;Ly=ymax-ymin;等领域[2]~[5]。体素化有很多方法，各有优缺点，Lz=zmax-zmin。在顶点(xmin,ymin,zmin)上固定一坐收稿日期：2004-03-11基金项目：国家“863”高技术研究发展计划资助项目（2001AA421160）作者简介：吴晓军（1975-），男，甘肃张掖人，博士，主要
6、研究领域为计算机图形学，快速成型等。·T2·T工程图学学报2005年标系，方向与欧氏空间的x，y，z方向相同，坐标vl,ul∈(0，1)。在体素空间中体素坐标(i,j,k)为为整数坐标，构成一空间，称为体素空间Z3。体n−1n−2n−li=u×2+u×2+L+u×212l素空间是一3D离散空间，是三维欧氏空间的子j=v×2n−1+v×2n−2+L+v×2n−l（1）12l空间（Z3⊂R3），每一整数组合序列(i,j,k)能唯n−1n−2n−lk=w×2+w×2+L+w×212l一确定一体素。与三维欧氏空间类似，在体素空相反地，若已
7、知某一八叉树结点的体素坐[9]间中也存在拓补关系，下面给出3个定义：标，则可推导出其线性八叉树结点编码,由公式(1)定义1如果两个体素间存在一个公共顶点求出每个编码位的二进制组合wl,vl,ul，由式(2)求或一条公共边或一个公共面，则称两个体素是出每个编码位，得到该节点的编码。26-邻接的。q=wvu=4w+2v+ul=,1,0L,n（2）lllllll定义2如果两个体素间存在一条公共边或1.3数据结构及节点生成一个公共面，则称两个体素是18-邻接的。八叉树结点数据结构类型定义如下：定义3如果两个体素间存在一个公共面，typed
8、efstructstructOctree则称两个体素是6-邻接的。{在体素的3种邻接关系中，6-邻接是约束最charorderstr;//节点编码强的，其次是18-邻接，约束最弱的是26-邻接，三者的关系可以表示为6-邻接⊂18-邻接⊂26-uns
