运用边界状态约束的表面体素加密细分算法

刘晨燕，敬石开+，张 伟,2，赵芳垒

(1.北京理工大学 机械工程学院，北京 100081； 2.中国科学院 计算技术研究所，北京 100190)

0 引言

近年来，基于体素的3D模型在虚拟医学[1]、三维地质属性建模、机械加工仿真[2]、立体渲染、碰撞检测、空间分析等领域得到了广泛应用。体素化算法是模型全信息建模表达与可视化的重要算法，体素化方法一般分为表面体素化和内部体素化两个步骤，最终获得体素大小均一的体素模型[3]。为得到精确的体素化模型，在体素化的过程中一般采用较高的体素分辨率，而这会造成体素单元数量和体素化时间随着分辨率的提高呈指数型增长，存储占用也随着体素数量变得很大，因此内存和时间的限制极大地影响了体素化分辨率。

为了在时间和内存都尽量小的情况下提升体素模型分辨率。理想方法是采用多分辨率体素化：在模型内部使用较大体素单元，而模型表面体素则选用较小体素单元来满足体素模型精度表达需要。针对这一问题，现有解决方法是对低精度体素模型表面进行再切分的加密操作，在保持体素数量相对较少的同时使体素模型满足表面精度要求，避免过高精度模型的内存占用和减少体素化时间。

在体素游戏显示领域，Smith[4]提出一种体素加密策略，通过递归细分算子对显示区域内所有体素进行切分细化。朱厚盛等[5]针对模型降维的需要，提出一种实体模型的多分辨率中轴生成方法，对模型中需要细化的部分进行边界体素化。但是该方法的实验数据加密层级只有2级，当初始模型分辨率较低时，不能达到有效精度。Szucki[6]对体素模型的特征区域内的体素划分成N×N×N份，但该局部加密操作只有1次，即加密层级只有1级。Marko[1]先以粗糙分辨率进行体素化，然后将体素尺寸增加到目标分辨率，并计算每个粗糙体素内的表面内外的细化体素的比率，得到多分辨率体素模型。随着图形处理器(Graphics Processing Unit, GPU)硬件技术的发展，也有学者采用并行处理的方式进行多分辨率体素化。Huang[7]最先使用GPU进行体素化。Young[7]使用GPU创建和渲染多分辨率体素化模型，应用三角面模型表面的法向量的函数将多边形模型离散为体素模型，并且对细节部分的体素细分成N×N×N份进行加密。其中，Szucki[6]和Young[8]所提的方法都通过增大N解决了精度和体素总数平衡的问题，但过大的N会导致加密处模型细节过渡不平滑，并且体素数量同样会迅速增加。

综上所述，目前部分高分辨率的体素化算法只能实现加密层级数较小的情况，高分辨率的体素化结果是在较高的分辨率的均一体素化模型的基础上一次加密获得，导致体素单元数量依然巨大，无法同时兼顾体素数量和分辨率。部分算法因采用GPU运算而对硬件依赖，算法不具有通用性。

针对以上问题，本文提出一种采用CPU计算的基于边界状态约束的表面体素加密细分方法。该方法通过切分均一体素模型的边界体素，删除多余子体素，实现1级加密细化。再将表面体素与外部体素的邻接关系(即边界状态)层层向下层子体素传递。通过对子体素进行编码索引,实现多层级加密细分，获得多分辨率的体素模型，加密层级理论上可以达到9级以及以上。

1 加密细分算法

1.1 基本概念定义

为描述算法，定义如下相关概念：

定义1依附三角面。以STL/AMF格式的三角面模型为输入进行表面体素化，每个与体素相交的三角面都是该体素的依附三角面，一个体素可能有0个、1个或多个依附三角面。当一个体素的依附三角面数量不为0时，该体素被判定为表面体素。

在多分辨率体素化过程中，一个体素经过一级或多级切分细化后，该体素切分为若干子体素，这些子体素之间的依附三角面信息会有所不同。

定义2外部面。一个体素共有6个表面，在一个边界体素中，将该体素与外部体素共用的面记作外部面。如图1中，若AB方向上6-邻接体素是外部体素，则AB方向上的面α为外部面。根据吴晓军[9]的定义，若两个体素间存在一个公共面，则称两个体素是6-邻接的。

定义集合Dir={z,y,x,-z,-y,-x}表示不同坐标轴方向。对任意一个外部面α，以αt的下标t表示外部面方向，其中t∈Dir，例如α-x表示该体素-x方向的外部面。αt=1表示体素的t方向的表面是外部面。

外部面是描述体素位置信息的一种方式，为了量化外部面随着体素删除而改变的过程，引入边界状态的概念。

定义3边界状态。表示一个体素中包含哪几个方向的外部面。因为位运算的高效性，本文将6种外部面αz，αy，αx，α-z，α-y，α-x映射到一个字节的低6位[10]来表示，将该字节称为边界状态，记为M，是一个二进制数。标记位按照z，y，x，-z，-y，-x的顺序排列如下：

00zyx-z-y-x

定义M(αt)为外部面αt的二进制形式，后面计算会用到。各个方向上外部面的二进制形式如表1所示。

表1 外部面二进制形式

与定义2对应，在6个标记位上，某位取1代表存在对应方向的外部面，取0代表该方向的外部面不存在。所有的边界体素都具有外部面，一个边界体素可存在多个外部面。一个不具备任何边界状态的体素，不是边界体素，它的边界状态M=0。

1.2 算法总流程

本文的算法流程如图2所示。

具体步骤如下：

步骤1均一体素模型生成。输入分辨率和模型，对模型进行表面和内部体素化，在表面体素化的过程中对每一个边界体素记录其依附三角面。初始化其边界状态。

步骤2边界加密细分。使用八分法平均切分边界体素，以八叉树结构存储。每一个初始边界体素都是一棵八叉树的根节点。在第1级加密中，根节点是父体素；在N级加密中，父体素是上一轮加密后的子体素。将父体素的边界状态传至子体素。遍历八叉树节点的体素，以分离轴定理计算每个子体素是否与自己的依附三角面相交。

步骤3检查每个子体素的三角面相交情况和边界状态。若子体素与任一依附三角面相交，则保留该体素；不满足相交条件的，检查体素的边界状态。若边界状态不符合要求，则删除体素，并传递边界状态至邻接体素中；否则保留。

步骤4多级加密和模型输出。若已达到模型加密层次要求，则输出体素模型，结束流程；否则针对边界体素重新执行步骤2。

1.3 预处理阶段

加密细分算法的对象是均一体素模型，因此需要先完成表面体素化和内部体素化，对应于流程图2中的步骤1。本文表面体素化是Akeninemöllser[11]所提的，他将Gottschalk[12]的分离轴定理用于碰撞检测进行表面体素化。但这一步不是本文重点，只需要注意在表面体素化的同时记录每个表面体素的三角面，构建体素—三角面的映射关系，为后续进行加密细分做基础准备。

若不从三角面模型开始，而是以均一体素模型为输入，可以执行一次表面体素化构建该映射关系。

表面体素化方法有很多，采取何种方式并不影响本文加密算法的实现。本文使用基于分离轴定理的碰撞检测[7]实现。分离轴定理实现表面体素化的原理是：对每个与三角面不相交的体素，总能找到一个方向，使得体素和三角面在这个方向的投影不重叠，满足条件gap>0，如图3所示。将与三角面相交的体素标记为表面体素，即完成表面体素化。

当分辨率较小、体素较大时，存在多个三角面位于同一体素内部的情况，如图4所示，该体素与多个三角面相交。

为了适应后续体素加密细分的需求，需要记录体素编号和三角面的映射关系，如式(1)所示：

f:voxel(i,j,k)→{triangle_ids}。

(1)

式(1)表示位于位置(i,j,k)的体素，有一个或多个三角面相交，记录这些三角面的集合，它保证了在体素模型的分辨率很小时，最大限度地保留原三角面模型的信息。

使用外部6-邻域Flooding算法进行实体体素化。使用基于广度优先搜索(BFS)算法[13]对位于模型外的体素进行标记，故未被标记的体素即为内部体素。经过以上步骤即获得均一体素模型。

1.4 对表面体素进行加密细分

本文的加密细分算法的总体思路是：在均一体素模型上，将每个表面体素细分为8个相同尺寸的子体素，将其与三角面进行相交检测，删除多余的子体素，再对保留的子体素进行下一级细分。

1.4.1 三角面和子体素的相交检测

加密细分操作中对三角面和体素的相交检测与表面体素化的方法一样，将父体素的依附三角面依次与子体素进行相交检测，若有至少一个依附三角面与该子体素相交，就保留该子体素；否则删除该子体素(即标记其为外部体素)。例如对于图5的子体素subv，分别从多个三角面投影，当投影为图中所示方向时，满足gapk>0，其中k对应映射关系(1)中三角面id，表明子体素subv不与任何三角面相交，故被判定为外部体素。

1.4.2 空洞问题—细分后子体素内外位置判定

若仅依据子体素与依附三角面相交情况进行删除操作，会导致某些体素被误删，如图6所示。在图6b中，体素1,2不与三角面相交，但因为该体素处于模型内部，删除后会产生内部“空洞”。造成模型内部出现孔隙，如图6a所示。因此，还需要获得子体素与三角面模型的内外关系，才能准确判断是否应该删除此体素。

为了解决这个问题，本文提出边界状态约束算法。

2 边界状态约束算法

边界状态约束算法以二进制运算的形式，通过初始化、继承、修改和传递边界状态信息，辅助判断体素的模型内外位置。

2.1 边界状态的使用和传递

2.1.1 边界状态初始化

使用八分法切分边界体素之前，该体素的边界状态可由其外部面信息确定。将每个边界体素的外部面信息整合至边界状态M。定义操作Add=M+M(αt)，表示在M的基础上新增外部面αt，M(αt)是外部面的二进制形式。

2.1.2 边界状态继承

初始化后仅有Root体素保存边界状态，在八分法切分表面体素时，子体素将继承父体素的边界状态。子体素所继承得到的边界状态取决于其位置编号，位置编号与坐标轴关系如图7所示。固定位置编号体素继承的外部面是固定的，如，对于位置编号为1的子体素，继承的边界状态所包含的外部面有αx、α-y、α-z(如图7)。

对于位置编号为p的体素，将会继承的外部面的二进制形式I(p)满足：

(2)

其中：p=x+2y+4z；≪是二进制移位符号，表示左移一位。

将外部面加入子体素边界状态M。对子体素执行多次Add=M+I(p)，即可完成子体素边界状态M的继承操作。

2.1.3 边界状态解决“空洞”问题

在流程图2的步骤3检测出三角面与体素不相交的基础上，进一步判断边界状态。若体素的边界状态M=0，则体素没有任何外部面，表示该体素位于模型内部，应当保留；若M≠0，表示该体素至少包含一个外部面，应当被删除。借由边界状态的判断，“空洞”问题得到解决，如图8所示。

2.2 加密体素编号索引

为了在八叉树中快速寻找体素的邻居节点，为体素模型的多级加密细分做准备，本文提出一种跨多棵八叉树之间寻找邻居节点的编号索引方法。现有的家谱法[14-15]只能在同一棵树内寻找邻居节点，一般用于基于八叉树的体素化算法中，要求所有体素对应节点都在同一棵八叉树下。加密算法中，每一个表面体素都是一个Root节点，相应地存在多棵八叉树。家谱法不适用于此情况，故设计了一套编号索引方案。

第二，今天我们强调现实题材创作，在习总书记的批示下做这部戏，是特别应该，特别及时。今年是改革开放40周年，改革开放40周年对中国的改变我不用重复了，而且刚才提到安徽小岗村，一个是农业改革，一个是工业改革，我觉得这两个是同一个级别的题材。

2.2.1 节点索引

节点的索引即体素在均一体素模型下的位置。Root节点对应表面体素，其邻居节点较易寻找。若体素索引为v(i,j,k)，则其+x方向邻居节点为v(i+1,j,k)，如图9a所示。

每一个非Root的体素都有一个体素索引和位置编号，体素索引表示体素在八叉树中的位置；位置编号则包含子体素和父体素之间的联系，如图7所示。

对于体素v(i,j,k)的体素，其位置编号p(数值0～7)可以拆分为3个0-1二值数x,y,z，满足p=x+2y+4z，其中x,y,z∈{0,1}。子体素索引与位置编号关系如图9c所示，满足：

v(ip,jp,kp)=v(2i+x,2i+y,2i+z)。

(3)

通过式(3)，可以从Root节点开始，逐层索引所有体素。同时，父体素索引满足：

v(i,j,k)=v(ip/2,jp/2,kp/2)。

(4)

2.2.2 寻找邻居节点

寻找索引为vs(is,js,ks)的子体素在+x的邻居vsn，只需对子体素索引在该方向加减，即邻居节点索引为vsn(is+1,js,ks)。但索引需要配合子体素所在的加密层级depth，才能唯一确定节点vsn。这样即便不同八叉树的多级体素之间索引重复也完全不影响。

用式(4)对索引vs(is,js,ks)执行depth轮操作，即可得到Root节点的索引。根据索引获得目标Root体素后。将上述过程逆向，从目标Root体素以式(3)寻找，执行depth轮，可得到最终目标体素。

多分辨率体素化中，存在叶子节点高度不一致的情况。本文加密任务中只存在高depth节点，即尺寸更小的体素节点，向低depth节点传递边界状态的情况。此时，上述算法执行式(3)，直至找到叶子节点，无需执行depth轮。

因此，通过上述加密体素编号索引，可以在多个八叉树中准确地找到任一体素的邻接体素。

2.3 多级加密时边界状态传递

体素删除将影响坐标轴方向的其他体素。随着子体素的删除，其6-邻接体素的边界状态会发生变化，原本不与外界相邻的体素成为边界体素。因此，体素删除后，不同方向邻接体素的边界状态需要各自调整。

图10以二维xy平面为例解释说明边界状态传递的方向，体素3的体素被删除后，向内传递外部面αx和αy，体素2获得外部面αy，体素1获得外部面αx，其边界状态相应改变。对于被删除的体素5，除了向体素6传递外部面αx之外，还需要在+y和-y方向调整体素的边界状态，体素7和8分别获得外部面a-y和αy。

传递边界状态的时候需要快速寻找邻接体素。如2.2.1所述建立八叉树体素索引，如图11所示，右下角大体素的索引是v(i+1,j,k)，体素vt将会传递边界状态αx到vq，传递边界状态αy到vp，二者均可由编号获取相应的八叉树节点。使用2.2.2节方式结合depth寻找到目标节点，故可完成跨八叉树的体素加密。

通过传递外部面信息，更新相邻体素的边界状态，可以使边界状态延续，使基于边界状态的多级加密成为可能。

3 实验验证

本文方法在Intellij IDEA环境下以Java语言编写，处理器为Intel Core i7-4790 3.6 GHz，运行内存为8 GB。程序使用单线程运行，以OpenGL编写的C++程序为显示软件。使用Stanford模型数据库中的Bunny、Ball、Dragon、Bike等模型作为主要实验对象。

3.1 加密细分效果

本文算法理论上可以实现从1～9级的加密细分，本节选择比较有代表性的6级加密为例进行效果展示。图12展示了不同模型、83分辨率经过6级加密后的体素模型显示效果。以Ball，Bunny，Dragon模型为例，经过加密细分的模型表面精细度和5123分辨率的均一体素模型完全一致，而模型内部为更大尺寸体素，实现了多分辨率体素化。

图12a为5123分辨率的均一体素模型，图12b和图12c是以83为初始分辨率，经过6级加密获得5123精细度的多分辨率体素模型。

本文算法还适用于一个体素中存在不封闭多重曲面的情况，可以处理具备复杂结构的机械模型。如图13所示，Bike模型在83分辨率下，整个体素模型效果粗糙。随着加密层级升高，可以逐步将Bike的支架轮毂等结构刻画出来。由于边界状态能够跨八叉树传递，当体素被删除时，对其周围体素边界状态的影响都会被记录下来。模型细节信息在加密过程不会损失。

3.2 实验数据

本算法的各级加密详细数据如表2所示。本文按三角面片数量级递增的顺序，列举出Ball，Bunny，Dragon共3个模型的测试数据。在加密后最外层分辨率相同(即最小体素的尺寸相同)时，在不同初始分辨率和不同加密层级下，比较总体素数量和算法运行时间。

表2 多级加密体素化计算时间/s及体素数量

续表2

表2中，层级0级加密对应均一体素模型(见每个模型的第一行数据)，从表中得出如下结论：

(1)对低分辨率体素模型加密，相比相同最外层分辨率的均一体素模型，用时更少，如图14所示。

对不同数量级的三角面模型，加密用时表现优于均一体素化算法，并存在一个用时最少的低分辨率和加密层次的组合。故可以通过合理选取初始分辨率和加密层次，实现最优的时间效率。

(2)经过加密后的低分辨率模型，总体素数量相比相同最外层分辨率的均一模型更少。对比如图15，例如，横坐标为0级对应分辨率为5123的均一体素模型，横坐标4级对应初始分辨率为323，加密4级之后的多分辨率体素模型。

Young[8]提出了一种体素模型细化方法：在均一体素模型的基础上,将每一个边界体素切分成N×N×N个同样大小的子体素,从而实现多分辨率体素化。在相同硬件条件下，将本文算法与文献[8]的体素细化方法进行模型体素总数量的对比，结果如表3所示。

表3 本文算法与文献[8]的体素数量对比

从表中可以看出，本文算法的体素数量远远小于文献[8]方法，而且细化层级越高，体素数量差距越大。若将初始分辨率323的体素模型加密细化为最外层分辨率2563的模型,文献[8]的算法需要将每一个边界体素切分成8×8×8个。本文在体素细化过程中使用八叉树结构，如图16所示，减少了不必要体素的切分,而且由于本文能实现层级很深的加密细化，而低初始分辨率又可以避免模型内部较大尺寸体素的切分,故体素数量随加密层级增加而减少。

4 结束语

针对现有多分辨率体素化方法加密层级很低，体素模型体素数量巨大的问题，本文提出一种体素模型加密细化方法，该算法将八叉树结构用于加密任务中。均一体素模型表面体素中包含体素与模型的内外位置关系，通过设计边界状态约束算法，充分利用了这种位置信息。最后，本文采用多种模型对加密细化方法进行了验证。算例结果表明，通过合理选取初始分辨率和加密层次，能够在获得同样精细度的体素模型的同时，减少体素数量，缩短算法运行时间。在不同加密层级的结果对比上，本文算法相比文献[8]方法，模型体素总数量平均减少71.53%，表明本文算法在加密体素数量上优于现有算法。

本文方法具有以下两方面的意义：

(1)提出一种利用边界状态约束，辅助判断体素位置的方案。体素与模型的位置关系可以通过边界状态来间接表示，通过在每个子体素内维护边界状态信息，加密过程可快速确定体素内外位置，无需复杂的几何计算，具有较高的实用价值。

(2)提出一种跨八叉树邻居搜索方法。从加密Root节点开始，用编码索引和八叉树深度结合的方式，快速准确地查找邻居节点，使多级加密成为可能。在本文硬件条件下，加密算法最多实现了9级加密，且加密细分后的模型效果和29倍的高分辨率模型完全一致。

下一步的研究方向主要集中在如何根据不同模型的三维结构特点，识别模型空间结构相对复杂的区域，并对局部区域进行加密细分。在保持体素模型细分效果的基础上减少参与加密的体素，从而进一步减少模型的体素数量。