人体与流体的交互仿真中的内外体化素

倪雪飞　秦富春

【摘 要】体素化（Voxelization）模型是为了解决描述模型内部属性如材料、密度等信息时产生的，体素化则是将物体的几何信息转化成最接近物体的体数据（Volume Datas）。体素化后的模型不仅包含模型的表面信息，而且能描述模型内部的属性。体素是由一组三维的立方体格子组成。

【关键词】体素化；尺度空间理论；距离场

体素化模型根据各自的特点各有不同，文献[1]是根据法向量的函数作为标准将模型离散的体素模型，文献[2]根据尺度空间理论（Scale-space Theory）的反走样体素模型，文献[3]是根据距离场（Distance Fields）和距离变换（Distance Transform）的方法建立体素模型。

1 预处理过程

根据人体、流体在世界空间中的范围大小，设定网格模型的范围。方向与欧氏空间的，轴方向相同，体素空间是离散空间，坐标是整数坐标，每一个坐标序列对应模型唯一的体素网格。由于体素化存在精度的问题，网格范围不应该大于实际模型空间范围，不然一个模型顶点将对应多个网格。

在体素空间中存在拓扑关系，下面给出定义：

定义1 如果两个体素间存在一个公共顶点或一条公共边或一个公共面，则称两个体素是26-邻接的。

定义2 如果两个体素间存在一条公共边或一个公共面，则称两个体素是18-邻接的。

定义3 如果两个体素间存在一个公共面，则称两个体素是6-邻接的。

这3种邻接体素模型，约束力关系可以表示为：6-邻接<18-邻接<26-邻接。

从定义中可以看出，6-邻接体素模型只能表示体素网格周围6个面的邻接关系，18-邻接体素模型可以表示与体素网格12条棱相接的体素网格，而26-邻接体素模型则可以额外表示体素网格上8个顶点相接的体素网格。本文采用的是26-邻接的体素模型，在体素化过程中提高仿真精度，使仿真更接近真实物理特性。

2 八叉树数据结构

一般的八叉树仅对灰节点（gray）进行分解，在本文中，需要对所有的节点均进行分解操作，这样才能对人体与流体的交互信息进行判断。

我们只需要标识体素网格对应模型的实际属性，如果是-1则表示落在人体外面，不进行交互；如果是0则表示恰好落在人体边界，进行交互处理；由于精度问题，上一次探测失败的点有可能落在人体里面，表示为1，仍然进行交互处理。

3 线性编码及算法

体素网格的边界关系由顶点、边、面3种关系组成，在实际遍历的方便以及效率的考虑，我们建立一种索引机制来对应这种边界关系。

线性八叉树有很好的编码方案，如Meagher给出了线性八叉树编码方案。设定第个结点的编码为公式（1）。

根据公式（2），可以由八叉树的体素化坐标得到编码位的二进制组合。再根据公式（1）求得线性八叉树编码。对于不同的编码，按照建立的索引表中的对应关系找到对应的体素位置。

例如，三角形的体素化，由于三维物体大部分是由三角面片组成的，所以三角形具有代表性。

1）对于三角形面片的体素化，可以分为点、边、面的处理。三个顶点分别为。点的体素坐标则表示为：为体素空间的距离大小。根据公式（1）、公式（2），由体素空间坐标求得体素网格的索引编码，然后由索引编码可以得到体素位置。

2）在对点进行体素化后，接下来对边进行处理。一般位置的边不垂直和平行坐标面，处理这样的边时，相当于在边的一个顶点发出射线，指向边的另一个顶点，途中经过的所有网格均被标记。由于已经求得了顶点的体素编码，可以根据编码找到边的顶点与体素网格相交的方式是点、边或者是面，然后由得到的相交方式求得相邻的体素网格，依次递归下去。对于特殊边的体素处理，只需要将相应坐标忽略掉即可。如垂直于平面，其体素的分量只需要从第一个体素网格的开始递增或递减。这样就可以得到边所占据的所有体素网格的编号。

3）在处理三角面时，需要先将三角面投射到具有最大阴影面积的平面上，假设为平面，投射三角形为。已经找到三角形顶点和边的体素网格和索引，根据网格坐标分量、的范围来确定三角面的体素网格。具体做法是先在平面上找到满足条件的点集坐标，然后以点集的点为原点，垂直平面，方向朝向原平面的射线，相交于点，为轴分量，交点为体素网格的坐标。最后根据公式（1）、公式（2），求出八叉树编码，并对其进行标记，计算体素点在人体模型的位置信息。

4 纹理切片

按照上述内外体素化算法流程，可以对人体、流体所在的体素网格进行体素化。体素化后的信息是离散的，将数据存入三维数组，便可得到一组有标识位组成的信息。每一组二维数组对应一层纹理切片。

在计算出纹理切片信息后，需要遍历所有层，探测在每层中流体与固体接触的边界位置，从而得到交互信息。而探测方式则可遍历二维数组，根据相应的标识值来确定的。

当遍历遇到0标号的时候，标记进入人体内部，当再次遇到1的时候标记穿出人体内部。依次递归下去，即奇数次为0时为进入边界，偶数次为0时退出边界。遍历所有切片，找到需要交互的网格，然后根据网格信息计算出在世界坐标中的位置。假设网格坐标是c（i，j，k），对应的世界坐标有表达式（3）

5 结束语

本文采用的是一种基于八叉树的方法建立模型对应体素单元的索引，由于我们体素化后的目的是为了判断与人体模型交互的耦合面，所以不需要建立包含复杂信息的体素模型。我们采用一种相对简单、快捷的办法来建立体素模型。

【参考文献】

[1]Jian Huang， Roni Yagel， Fillipov V， et al. An accurat method to voxelize polygonal meshes[C]//.In：IEEE Volume Visualization98. Chapel Hill， North Carolina， USA，1998.119～126.

[2]Stijn Oomes， Peter Snoeren， Tjeerd Dijkstra. 3D shape representation： transforming polygons into voxels [C]//. In：Proceedings of the First International Conference on Scale-Space Theory in Computer Vision. Haar Romeny，B.ter，etal.（Ed.），Springer Verlag，1997.349～352.

[3]Kong T Y， Rosenfeld Y A. Digtial topology：introduction and survey[J]. Computer Vision，Graphics and Image Processing，1989，48：357～393.

[责任编辑：侯天宇]