段伟伟，罗健欣，倪桂强，唐 斌

(解放军理工大学 指挥信息系统学院，江苏 南京 210007)



一种基于八叉树的快速体素化方法*

段伟伟，罗健欣，倪桂强，唐 斌

(解放军理工大学 指挥信息系统学院，江苏 南京 210007)

当前的体素化方法大都具有较高的复杂性，计算开销大，对硬件要求高。为了简单快速地实现3D模型的体素化，提出一种基于八叉树的快速体素化方法。首先在使用八叉树进行模型细分的基础上，得到模型表面数据。然后根据表面数据选择多个方向对模型进行逐行扫描。该方法能快速地区分出模型的外部数据和内部数据，最终实现模型的体素化。对不同分辨率下的多种模型的实验结果表明，文中提出的方法能有效地实现快速体素化，具有一定的应用价值。

体素化；八叉树；快速；多方向逐行扫描；模型细分

0 引言

近年来，基于体素(Voxel)的3D模型在众多领域(如立体渲染、虚拟现实、医学影像、机械零件制造、流体力学等)得到了广泛的应用。传统的3D模型表示方法(如扫描表示法、边界表示法等)只能表示物体的表面信息，难以描述其内部属性。体素化(Voxelization)能根据3D模型的表面几何信息，计算并获取模型的内部数据，产生描述完整3D模型的体数据集。目前，作为一个研究热点，关于体素化方法的研究成果越来越多，可以较好地将3D模型表面数据转换为能描述模型内部信息的体数据。然而，这些已有的方法一般具有较高的复杂性，计算开销大，对硬件要求高。为此，本文提出了一种简单的基于八叉树的快速体素化方法，在利用八叉树对3D模型进行细分的基础上，对模型的表面数据进行多方向逐行扫描，快速地区分出模型的外部数据与内部数据，有效地实现模型的体素化。

1 相关工作

1.1 八叉树

八叉树是一种空间分割的层次数据结构，它将其节点递归地分解为8个子节点，直至达到一定精度[1]。树的第一个节点是根节点，对应一个立方体，表示整个物体模型。每个节点有8个子节点或者没有子节点，这8个子节点是对父节点的一次2×2×2规则细分，其中没有子节点的节点叫做叶节点。在一个3D模型的八叉树结构中，那些包含了模型表面的节点被更细致地划分，而余下的空节点则成为叶节点。八叉树结构的每个维度上每细分一次，其分辨率都增大到原来的两倍。因此，要达到一个1283的分辨率，每个维度上均需要7层细分操作(log2128=7)。八叉树结构是表达三维模型的一种重要方法，能方便有效地进行三维模型的表示。

1.2 体素化

体素化也被称作三维扫描转换(3D Scan Conversion)，最早是由Kaufman在1987年提出[2]，其根据3D模型的表面数据，转换成指定精度的体素表示形式，以获得包含模型内部信息的体数据集。

体素化自出现以来，众多研究者提出了许多不同的体素化方法。Huang等[3]以基于模型表面的法向量函数为距离标准，将多边形模型离散为体素模型，可以选择实现6-邻域封闭或26-邻域封闭。Jones等[4]应用距离变换和距离场的方法生成体素模型，主要针对CT和MRI等产生的灰度体数据集体素模型，便于后续的可视化处理。Dachille等[5]提出一种增量式三角形的体素化方法。Haumont等[6]提出一种基于种子填充方式的实体体素化方法。Beckhaus等[7]提出了一种切面法，根据Z轴方向的分辨率设定一组裁剪面，依次绘制每个切片并保存在帧缓存中，所有的像素数据构成了最终的体素化数据。Thon等[8]运用四叉树结构对基于光线投射的体素化算法进行了改进。吴晓军等[9-10]利用八叉树编码的特性，提出一种产生整个三维模型的体素表示算法。Laine[11]研究了拓扑结构在体素化过程中的应用，提出一种基于拓扑结构的体素化方法。近些年随着图形处理器GPU的快速发展，一些研究者尝试将GPU技术应用到体素化方法研究中[12-13]。Martin等[14]提出一种基于GPU的核外(out-of-core)体素化方法，能有效处理高分辨率下的模型。这些方法虽然利用GPU的并行特性提高了算法性能，但是其算法的判断过程较为复杂，计算开销较大，对硬件要求较高。

2 基于八叉树的快速体素化方法

本文针对一般3D模型的体素化需求，提出了一种基于八叉树的快速体素化方法。该方法分为两个阶段：第一阶段，使用八叉树结构对初始的3D模型进行空间细分，直至达到指定的分辨率精度，得到在该精度下模型表面对应的体素数据；第二阶段，提出一种简单的多方向逐行扫描算法，能够根据3D模型的表面数据，快速地区分模型外部数据和内部数据，进而获得体数据集，实现模型的体素化。

2.1 基于八叉树的模型细分

对于3D模型，首先使用八叉树对其进行空间细分，直至得到指定的分辨率。图1表示对模型节点从第l层到第l+1层的细分过程，相应的分辨率从2l提高到2l+1。在最高分辨率层，那些与模型表面相交的节点将被标记为模型表面点，而其余的节点被标记为非表面点。以此可以将所有空间数据划分为两类：第1类，模型表面点对应的体素数据，标示为1，即表示3D模型的表面数据；第2类，除第1类以外的所有体素数据，标示为0，包括3D模型内部的元素和模型外部的元素。在本阶段暂时不对模型的内部数据和外部数据进行区分。不同类型的元素划分如下：

(1)

图1 模型细分过程

2.2 多方向逐行扫描算法

在上一小节已经获得了3D模型的表面数据。在本节中，提出了一种简单的多方向逐行扫描算法。使用该算法，能根据3D模型的表面数据，快速地区分出模型的内部元素和外部元素，实现模型体素化。

为简单起见，首先给出多方向逐行扫描算法在2D空间中的描述。对于二维平面中的一个物体，在已知物体边界数据的情况下，如何区分其外部数据与内部数据。此处考虑依次选择不同方向，从空间边界开始逐行对物体进行扫描。一般地，由于模型空间边界的元素不在模型内部，因此在每一行的扫描过程中，将遇到的非物体边界元素标记为物体的外部元素，直至遇到物体边界元素时停止该行扫描。图2是分别从坐标平面的X、Y轴的正、负方向对物体进行逐行扫描判断的示意图。

图2 多方向逐行扫描的二维示意

在经过4个不同方向的逐行扫描遍历之后，所有的外部元素被区分出来。对于整个数据域而言，除去物体的边界元素和外部元素，其余的元素即为物体的内部数据。对内部数据进行赋值填充，即实现了物体内部数据的识别与判定，如图3所示。

图3 根据扫描结果，填充物体内部数据

将上述2D空间中的多方向逐行扫描算法推广到3D空间，将平面坐标轴的4个扫描方向扩展到空间坐标轴的6个扫描方向，即可快速实现对3D模型内部数据的识别与填充，完成3D模型的体素化。分别选择模型所在的空间坐标系的X、Y、Z轴的正、负方向，从边界开始对模型进行逐行扫描。首先选择一个扫描方向，比如Z轴正方向((0,0,0)→(0,0,z))，在选定的方向上，对每个元素进行如下判断：如果该元素值为0，即判定其为模型外部元素，将其值重新标示为-1；如果该元素值为1，说明遇到了模型表面，则停止该行的扫描，并开始下一行的扫描；如果元素为-1，说明遇到的是模型外部元素，不做任何处理，继续下一个元素的扫描判定。3D模型的多方向逐行扫描算法的伪代码如下所示：

select a scanning direction, such as (0,0,0) to (0,0,z);

for (x=0;x

for (y=0; y

for (z=0; z

//(x,y,z) is outside of the model, set it as a outer voxel

if (voxel(x,y,z)==0)

voxel(x,y,z)=-1;

//(x,y,z) is on the model surface, stop scaning on this row

else (voxel (x,y,z)==1)

break;

}

在6个方向的扫描遍历完成以后，所有的体数据被分为三类：标示值为1的模型表面元素、标示值为0的模型内部元素，以及标示值为-1的模型外部元素。至此，得到了那些标示值为1和0的数据，即能完整描述3D模型表面及其内部的体数据。

(2)

图4 算法流程图

图4为整个方法的流程图。首先，载入3D模型，使用八叉树进行节点细分，得到指定分辨率的模型表面数据。然后，依次选择不同的扫描方向，对模型进行逐行遍历扫描，如果元素值为0，则将其标示为-1；如果值为1，则停止该行扫描，开始下一行扫描；如果值为-1，则不处理，继续下一个元素的扫描。最后，扫描结束得到模型内部数据，体素化完成。

3 实验结果

为了验证本文算法的有效性，对不同分辨率的多个3D模型进行了体素化测试。本文算法在Visual Studio 2010环境下调用OpenGL函数库实现，所有的实验结果均是在一台2.3 GHz Intel Core2 i7-4712处理器、4 GB内存、NVIDIA GeForce 840M显卡的笔记本电脑上测试获得。

表1给出了本文算法所使用的实验模型参数及其测试结果。图5是分辨率为1283的tank模型和lady模型的体素化效果图。

表1 模型参数及体素化测试结果

实验结果显示，本文算法在多个模型的不同分辨率需求下，均能在较快的时间内产生较好的体素化效果。

图5 3D模型体素化效果图

4 结论

本文提出了一种基于八叉树细分模型的多方向逐行扫描的体素化方法，首先在使用八叉树对3D模型进行细分的基础上，得到模型表面数据，然后根据表面数据进行多个方向的逐行扫描，快速地区分出模型的外部数据和内部数据，实现模型体素化。本文算法思路简单，易于实现，对硬件需求不高。在处理一般的3D模型体素化任务时，该算法具有较大的优势。实验结果表明，本文方法可以以较快的速度对不同分辨率下的多种模型实现体素化。但是，本文算法并不能很好地处理内部包含有空洞的3D模型，会将内部的封闭空洞误识别为模型的内部体数据。

下一步的工作将针对无法识别3D模型内部封闭空洞的问题，对多方向逐行扫描算法进行改进，期望可以正确地识别出模型的内部空洞，进一步提高算法的适用性，扩大应用范围。

[1] MEAGHER D. Geometric modeling using octree encoding[J]. Computer Graphics and Image Processing, 1982, 19(2):129-147.

[2] KAUFMAN A. Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes[J]. ACM Siggraph Computer Graphics, 1987, 21(4):171-179.

[3] HUANG J, YAGEL R, KURZION Y. An accurate method to voxelize polygonal meshes[C]. IEEE Symposium on Volume Visualization, 1998:119-126.

[4] JONES M W,SATHERLEY R. Voxelisation: modeling for volume graphics[C]. Conference on Vision Modeling and Visualization, 2000:319-326.

[5] DACHILLE F, KAUFMAN A. Incremental triangle voxelization[C].Proceeding of Graphics Interface, 2000:205-212.

[6] HAUMONT D, WARZEE N. Complete polygonal scene voxelization[J]. Journal of Graphics Tools, 2002, 7(3):27-41.

[7] BECKHAUS S, WIND J, Strothotte H. Hardware-based voxelization for 3D spatial analysis[C].Proceeding of the 5th International Conference on Computer Graphics and Imaging, 2002:15-20.

[8] THON S,GESQUIERE G, RAFFIN R. A low cost anti-aliased space filled voxelization of polygonal object[C].Proceeding of International Conference Graphics, 2004: 71-78.

[9] 吴晓军，刘伟军，王天然,等. 改进的基于欧式距离测度网格模型体素化算法[J]. 计算机辅助设计与图形学学报, 2004, 16(4): 592-597.

[10] 吴晓军，刘伟军，王天然,等. 基于八叉树的三维网格模型体素化方法[J]. 工程图学学报, 2005, 26(4):1-7.

[11] LAINE S. A topological approach to voxelization[J]. Computer Graphics Forum, 2013, 32(4):77-86.

[12] SCHWARZ M, SEIDEL H P. Fast parallel surface and solid voxelization on GPUs[J].ACM Transation on Graphics, 2010, 29(6): 179.

[13] CRASSIN C, GREEN S. Octree-based sparse voxelization using the GPU hardware rasterizer[M]. OpenGL Insights, 2012.

[14] MARTIN P, ANDREAS K. Grid-free out-of-core voxelization to sparse voxel octrees on GPU[C]. Conference on High-Performance Graphics, ACM, 2015:95-103.

A fast voxelization method based on octree

Duan Weiwei, Luo Jianxin, Ni Guiqiang, Tang Bin

(School of Command Information System, PLA University of Science and Technology, Nanjing 210007, China)

Current methods of voxelization almost have extraordinary complexity which need a high cost of calculation and hardware requirements. In order to achieve a simple and fast voxelization of 3D models, this paper presents a fast voxelization method based on octree. Firstly, subdividing the 3D models using octree structure to get the voxel data on the model surface. After selecting multi-directions to scan the model per row according to the surface data, it’s easy to judge that the voxels are inside of the model or outside of the model. Then the voxelization of 3D model is done. The experimental results of several models on different resolutions show that this method achieves a fast voxelization efficiently and is valuable in application.

voxelization; octree; fast; scanning per row of multi-directions; model subdividing

江苏省自然科学青年基金(BK20150722)

TP391.4

A

10.19358/j.issn.1674- 7720.2017.11.027

段伟伟，罗健欣，倪桂强，等.一种基于八叉树的快速体素化方法[J].微型机与应用，2017,36(11)：91-93，101.

2016-12-13)

段伟伟(1988-)，男，博士研究生，主要研究方向：计算机图形学，算法设计。

罗健欣(1984-)，男，博士，讲师，主要研究方向：计算机图形学，可视化，计算机网络。

倪桂强(1966-)，通信作者，男，博士，教授，主要研究方向：计算机网络，可视化，计算机图形学。E-mail:nigq1966@163.com。