本发明属于计算机图形处理技术领域，具体涉及一种基于点灯法的三维模型精确体素化方法。
背景技术：
随着计算机图形/图像技术的发展，三维模型的设计建模在增材制造、虚拟现实、多媒体视频、影视动画等领域得到了广泛的应用。三维模型的造型方法多样且复杂，如何在满足越来越高的全面性建模要求的同时，利用一种通用快捷的建模方法去构造和存贮三维模型，成为三维建模领域的重要课题。
众多学者先后提出了基于体素化的模型建模方法，可将三维模型分解为等大小的正方体单元进行组合表示。但是这些体素化算法在对模型的处理中不可避免地存在着各种问题。在模型的棱边、顶点上常常会出现细微的划分漏洞，当模型外表面特征较为复杂时很难表征划分的完整性。划分的精细度由正方形单元即体素单元的大小而定，体素单元过大时模型划分不精细，体素单元过小会保证精度，但是会大大增加处理的计算量，使建模效率变得低下。
技术实现要素：
(一)解决的技术问题
本发明提供了一种应对性广、准确性强的三维实体模型体素化方法，以解决传统体素化算法中精确度不足，且容易出现边界划分漏洞的问题，大幅提高体素化处理的适应性和可操控性。
(二)技术方案
为实现上述目的，本发明提供如下技术方案：一种基于点灯法的三维模型精确体素化方法，主要包括以下步骤：
步骤1：导入三维模型文件，对原始模型进行四面体剖分处理，得到模型的拓扑信息数据组，计算模型的最小aabb'包围盒，划分体素单元，并记录包围盒内所有体素的顶点坐标信息；
步骤2：根据模型剖分得到的拓扑信息数据组，进行“搜寻点灯法”算法处理，对有用的体素单元用‘a’进行标记，得到体素化模型modela；
步骤3：根据模型剖分得到的拓扑信息数据组，进行“桁架构造法”算法处理，对有用的体素单元用‘b’进行标记，得到由所有四面体的边角所构成的架构体素化模型modelb；
步骤4：对“搜寻点灯法”得到的体素模型modela和“桁架构造法”得到的模型modelb进行合并，得到最终体素化的模型modelvoxel。
进一步的，所述步骤1进一步包括以下步骤：
步骤1.1：导入三维模型数据文件；
步骤1.2：对三维模型进行四面体网格剖分操作，得到模型的拓扑信息数据组；
步骤1.3：读取得到的拓扑信息数据组，通过建立集合p0包含模型内部所有的点信息，构建集合e0包含模型内部所有的四面体信息；
步骤1.4：根据集合p0中记录的所有点的坐标信息，建立模型的最小aabb包围盒；
步骤1.5：设置体素单元的径长l，对模型的最小aabb包围盒做取整化处理，得到模型的最小aabb'包围盒；
步骤1.6：对模型的aabb'包围盒进行体素化划分，设划分得到的体素单元的集合为d0，记录每个体素单元对应八个顶点的坐标，设所有体素顶点构成的集合为v0。
进一步的，所述步骤2具体包括以下步骤：
步骤2.1:开始“搜寻点灯法”，调出剖分得到的模型内部的各个四面体顶点的坐标信息；
步骤2.2：计算求解四面体单元e的最小取整包围盒aabb′e，对包围盒aabb′e进行体素单元划分。记录aabb′e包围盒内所有体素单元对应的顶点坐标；
步骤2.3：求解aabb′e包围盒内的所有点与四面体单元e的空间位置关系，根据每个不同的位置关系，返回不同的特征值进行记录；
步骤2.4：根据返回的特征值对点集ve内的各个对应点进行不同的操作：内部的点予以记录，表面的点和外部的点跳过不做处理；
步骤2.5：遍历模型内部的所有四面体单元，循环进行步骤2.3和步骤2.4的操作，将各个四面体单元的点集ve的顶点状态信息，整合到总点集v0中，根据各个体素顶点的状态再对各个体素自身的状态值进行判断，确认体素集d0中有用的体素单元；
步骤2.6：将所有被‘a’标记的体素进行整合和建模，导出三维模型modela。
进一步的，所述步骤3具体包括以下步骤：
步骤3.1：开始“桁架构造法”，依次调出模型内部各个四面体的顶点和边的空间结构信息；
步骤3.2：以边ab为例，按照笛卡尔坐标系x、y、z三个轴向，分三次进行处理,以x轴方向为例，首先判断ax和bx的大小；
步骤3.3：在获得线段的新起始点a'后，插值计算线段a'b中a'到b上的各个间断点,由间断点查找对应的体素单元用‘b’进行标记；
步骤3.4：按照y、z轴方向处理边ab，同x轴的处理方式一致,接着处理四面体单元e'的其它三个边bc、cd、ad；
步骤3.5：完成当前四面体单元e'的处理，进入下一个四面体单元的处理流程，对于已处理过的重复边不再重复处理；
步骤3.6：遍历完四面体集合d0后，统计在桁架构造法中所有被‘b’标记的体素，整合和建模，导出三维模型modelb。
(三)有益效果
本发明提供一种基于点灯法的三维模型精确体素化方法，本发明三维模型实体分区体素化方法具有极高的适应性和可操控性，大幅提高了体素化的效率，能有效应对多模型和复杂模型下的体素化漏洞问题。
附图说明
为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1是一种基于点灯法的三维模型精确体素化方法的流程图。
图2是金字塔模型经过搜寻点灯法处理得到的体素模型对比图：图a为优化前；图b为点灯法处理后。
图3是斯坦福兔子模型经过搜寻点灯法处理得到的体素模型剖面对比图：图a为优化前；图b为点灯法处理后。
图4为体素尺寸设置不够精细时，点灯法处理模型存在的表面漏洞示例对比图：图a为优化前；图b为点灯法处理后。
图5显示了普通体素化的弊端和本发明优化后的精确处理结果对比图：图a为传统体素化策略出现的问题；图b为本发明优化相同模型的输出结果。
图6是金字塔模型经过桁架构造法处理得到的体素模型对比图：图a为优化前；图b为桁架构造法处理后得到的体素模型。
图7是斯坦福兔子模型经过桁架构造法处理得到的体素模型剖面对比图：图a为优化前；图b为桁架构造法处理后得到的体素模型。
图8展示了金子塔模型的完整优化流程对比图：图a为原模型，图b为搜寻点灯法得到的体素模型，图c为桁架构造法得到的体素模型，图d为最终输出的体素化模型。
图9展示了锚钩模型的完整优化流程对比图：图a为原模型，图b为搜寻点灯法得到的体素模型，图c为桁架构造法得到的体素模型，图d为最终输出的体素化模型。
具体实施方式
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。
本发明提供一种技术方案：本发明基于网格划分建模思想，提出一种基于点灯法的三维模型体素化方法。以下将结合附图和实例，对本发明做进一步详尽说明。本发明所用的思路方法已通过计算机编程实现完整流程，技术流程图参见图1，一种基于点灯法的三维模型精确体素化方法，包括以下步骤：
步骤1：导入三维模型文件，对原始模型进行四面体剖分处理，得到模型的拓扑信息数据组，计算模型的最小aabb'包围盒，划分体素单元，并记录包围盒内所有体素的顶点坐标信息，具体包括以下步骤：
步骤1.1：导入三维模型数据文件；
步骤1.2：对三维模型进行四面体网格剖分操作，得到模型的拓扑信息数据组。
模型内部将加入若干数量的顶点，在顶点之构建成直线、面片、四面体，形成模型的拓扑信息数据组；
步骤1.3：读取得到的拓扑信息数据组，建立集合p0包含了模型内部所有的点信息，集合e0包含了模型内部所有的四面体信息；
步骤1.4：根据集合p0中记录的所有点的坐标信息，建立模型的最小aabb包围盒；
步骤1.5：设置体素单元的径长l，对模型的最小aabb包围盒做取整化处理，得到模型的最小aabb'包围盒；设置体素单元的边长l，即为模型体素化后每个体素单元的大小；为了使体素化模型的最小包围盒所包含的三维空间区域能悉数划分为体素单元区域，对aabb包围盒八个顶点的坐标进行调整，使每个相邻顶点的距离数值增大且相邻距离可以被l整除，记调整后的包围盒为模型的aabb'最小包围盒，为后续步骤体素化操作所用到的包围盒。
步骤1.6：对模型的aabb'包围盒进行体素化划分，设划分得到的体素单元的集合为d0，记录每个体素单元对应八个顶点的坐标，设所有体素顶点构成的集合为v0。
步骤2：根据模型剖分得到的拓扑信息数据组，进行“搜寻点灯法”算法处理，对有用的的体素单元用‘a’进行标记，得到体素化模型modela，具体包括以下步骤：
步骤2.1:开始“搜寻点灯法”，调出剖分得到的模型内部的各个四面体顶点的坐标信息；根据统计的集合p0和集合e0做第一部分的体素化处理流程，本发明命名为“搜寻点灯法”。对集合e0内的四面体单元依次遍历。设遍历到的四面体单元为e，根据模型拓扑信息找到对应的四个顶点的标号和坐标值，设四个顶点的坐标分别为c1(x1,y1,z1)、c2(x2,y2,z2)、c3(x3,y3,z3)、c4(x4,y4,z4)；
步骤2.2：计算求解四面体单元e的最小取整包围盒aabb′e，对包围盒aabb′e进行体素单元划分，记录aabb′e包围盒内所有体素单元对应的顶点坐标，与步骤1.6对三维模型求解取整包围盒aabb'不同的是，需要求解的四面体单元的取整包围盒aabb′e的四个顶点必须与aabb'包围盒内某个体素的顶点重合，设对包围盒aabb′e进行体素单元划分得到的体素单元的集合为de，则de与d0之间存在de∈d0的关系；记录包围盒内aabb′e每个体素单元的体素顶点构成的集合为ve。
步骤2.3：求解aabb′e包围盒内的所有点与四面体单元e的空间位置关系，根据每不同的位置关系，返回不同的特征值进行记录。对点集ve进行遍历，假设遍历到的点为ci(xi,yi,zi)，根据ci的坐标求解点ci与四面体单元e的空间关系：在四面体的内部、表面或是外部。根据四面体的四个顶点c1、c2、c3、c4的坐标值信息进行求解验证。
首先，计算四面体单元e四个面上的法向量n1、n2、n3、n4，以顶点c1、c2、c3构成的平面为例，公式如下：
n1和
接着，建立由需要验证的点ci到四个顶点的法向量，这里命名为n5、n6、n7、n8，示例如下：
nj＝(xk-xi,yk-yi,zk-zi),j∈[5,6,7,8],k∈[1,2,3,4](2)
求解平面法向量与各个射线向量间的叉积，配对方式为n1和n5、n2和n6、n3和n7、n4和n8
对求得的productn用符号函数sgn()进行求解：
sn＝sgn(productn),n∈[1,2,3,4](4)
对于求得的s1、s2、s3、s4进行比对，若其中任意一项值为0，说明点ci正好在这个四面体单元e的表面，返回特征值0；当s1、s2、s3、s4中没有0值且均为同号时，说明点ci在这个四面体单元e的内部，返回特征值1；否则，说明当前点在四面体单元e的外部，返回特征值-1。
步骤2.4：根据返回的特征值对点集ve内的各个对应点进行不同的操作：内部的点予以记录，表面的点和外部的点跳过不做处理。
对于不同的返回值，首先将返回值为1即在四面体单元内部的点予以标记和记录，对于返回值为0或-1的点，根据软杀死(softkill)的理念，这些点定义为不确定点，跳过不做处理，大部分点将在不同的四面体内进行多次验证和判断，此处施加定义准则，只要该点在其中的被予以标记过一次，则该点记为有用点，在点集ve中对该点用‘a’进行标记。
步骤2.5：遍历模型内部的所有四面体单元，循环进行步骤2.3和步骤2.4的操作。将各个四面体单元的点集ve的顶点状态信息，整合到总点集v0中。根据各个体素顶点的状态再对各个体素自身的状态值进行判断，确认体素集d0中有用的体素单元。
在遍历完模型内部的所有四面体后，进行整合统一，将各个四面体单元的点集ve的顶点状态信息，整合到总点集v0中。接着进展顶由点及体素的信息统一化操作。基于模型的拓扑结构信息，对模型的最小aabb'包围盒内的所有体素进行遍历，验证每个体素的八个对应的顶点的状态。若八个对应顶点中存在一个以上的顶点为已经在点集v0中被‘a’标记，说明该体素单元与模型在三维空间内有相交的部分，将该部分正方体体素用‘a’进行标记，此处命名为“点灯法”。到这里为止的第一步流程进行完毕，整体步骤2命名为“搜索点灯法”。
步骤2.6：将所有被‘a’标记的体素进行整合和建模，导出三维模型modela，输出的modela如图2(b)、图3(b)、图8(b)、图9(b)所示。
步骤3：根据模型剖分得到的拓扑信息数据组，进行“搜寻点灯法”算法处理，对有用的体素单元用‘b’进行标记，得到由所有四面体的边角所构成的架构体素化模型modelb。
“搜索点灯法”可以查找到模型体素化中的大部分体素区域。但是，当体素划分较大时，在模型的边角上会出现部分“点灯法”无法找到的区域部分。当顶点和体素相交或是模型的边经过体素的两种情况下，当体素的大小设定较大时，所显示出来的误差是较为明显的。如图4展示了体素过大的情况下“点灯法”存在的部分缺漏。为了对步骤2的“点灯法”的精密度进行补充优化，并得到模型的内部框架结构，进行“桁架构造法”的算法优化流程。
步骤3.1：开始“桁架构造法”，依次调出模型内部各个四面体的顶点和边的空间结构信息。对集合e0内的四面体进行遍历，以遍历到的四面体单元e'为例，设四面体四个顶点及它们的坐标为a(xa,ya,za)、b(xb,yb,zb)、c(xc,yc,zc)、d(xd,yd,zd)，四条边记为ab、bc、cd、ad。
步骤3.2：以边ab为例，按照笛卡尔坐标系x、y、z三个轴向，分三次进行处理。以x轴方向为例，首先判断ax和bx的大小。当ax＝bx即a和b两点在x方向上的坐标相等时，跳出当前步骤，进入下一步对y和z两个方向的处理。否则，继续进行计算，对ax和bx的大小进行排序，设ax＜bx。对x坐标较小点a进行判断，通过a的三个坐标ax、ay、az，判断点a是否在aabb'包围盒内划分的体素单元间的交界面上。当a的任一坐标在体素交界面上时，对a的坐标进行微量调整，设向量ab的单位矢量为k(kx,ky,kz)，设微调后得到的点及坐标为a'(x'a,y'a,z'a)，微量调整关系式为：
将得到的点a'替代点a作为线段的起始点，即a'b。这样做的好处在于，排除了在体素交界面上的点(又称为“模糊点”)带来的体素定义不明确的问题。在传统模型体素化的处理中，经常会遇到模型表面的点在体素交界面的情况，这种情况下，往往会导致最后的体素化结果在左表面或右表面、上表面或下表面中总有一层是多划分出来不符合实际要求的。如图5所示。
步骤3.3：在获得线段的新起始点a'后，根据插值计算线段a'b中a'到b上的各个间断点。由间断点查找对应的体素单元用‘b’进行标记。以体素的径长l为累加单位，从起始点a'进行三个坐标的累加，当满足x'a≥xb或y'a≥yb或z'a≥zb其中的一个时，停止累加。记录累加过程中获得的点的坐标信息，查找这些点分别在体素集d0中在哪个体素的空间范围内，对找到的体素用‘b’进行标记。
步骤3.4：按照y、z轴方向处理边ab，同x轴的处理方式一致。接着处理四面体单元e'的其它三个边bc、cd、ad。
步骤3.5：完成当前四面体单元e'的处理，进入下一个四面体单元的处理流程，对于已处理过的重复边不再重复处理。
因为预先已经设立了模型的拓扑关系，在其中每次对边的处理之后，都会对拓扑关系中对应的边用‘b’进行标记。在每次对边的处理之前检查边的容器里对应边是否已经被‘b’标记，处理过的边将不会再次被处理，从而减少浪费的计算量。
步骤3.6：遍历完四面体集合d0后，统计在桁架构造法中所有被‘b’标记的体素，整合和建模，导出三维模型modelb。到此第二个流程处理完成，整体步骤3命名为“桁架构造法”，得到的结果如图6(b)、图7(b)、图8(c)、图9(c)所示。
步骤4：对“搜寻点灯法”得到的体素模型modela和“桁架构造法”得到的模型modelb进行合并，得到最终体素化的模型modelvoxel。
对步骤3和步骤4得到的不同优化结果进行求并：对体素集合d0的a标记和b标记求并运算，在模型的拓扑结果信息上则体现为求或运算。只要体素单元被‘a’标记或‘b’标记，则为输出状态，否则不输出。
整合体素集合d0并建模，得到原始模型的体素化三维模型modelvoxel，最终输出的体素化模型如图8(d)、图9(d)所示。
在本说明书的描述中，参考术语“一个实施例”、“示例”、“具体示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。
以上公开的本发明优选实施例只是用于帮助阐述本发明。优选实施例并没有详尽叙述所有的细节，也不限制该发明仅为的具体实施方式。显然，根据本说明书的内容，可作很多的修改和变化。本说明书选取并具体描述这些实施例，是为了更好地解释本发明的原理和实际应用，从而使所属技术领域技术人员能很好地理解和利用本发明。本发明仅受权利要求书及其全部范围和等效物的限制。
1.一种基于点灯法的三维模型精确体素化方法，其特征在于，主要包括以下步骤：
步骤1：导入三维模型文件，对原始模型进行四面体剖分处理，得到模型的拓扑信息数据组，计算模型的最小aabb'包围盒，划分体素单元，并记录包围盒内所有体素的顶点坐标信息；
步骤2：根据模型剖分得到的拓扑信息数据组，进行“搜寻点灯法”算法处理，对有用的体素单元用‘a’进行标记，得到体素化模型modela；
步骤3：根据模型剖分得到的拓扑信息数据组，进行“桁架构造法”算法处理，对有用的体素单元用‘b’进行标记，得到由所有四面体的边角所构成的架构体素化模型modelb；
步骤4：对“搜寻点灯法”得到的体素模型modela和“桁架构造法”得到的模型modelb进行合并，得到最终体素化的模型modelvoxel。
2.根据权利要求1所述的一种用于点阵结构的三维模型精确体素化方法，其特征在于：所述步骤1具体包括以下步骤：
步骤1.1：导入三维模型数据文件；
步骤1.2：对三维模型进行四面体网格剖分操作，得到模型的拓扑信息数据组；
步骤1.3：读取得到的拓扑信息数据组，通过建立集合p0包含模型内部所有的点信息，构建集合e0包含模型内部所有的四面体信息；
步骤1.4：根据集合p0中记录的所有点的坐标信息，建立模型的最小aabb包围盒；
步骤1.5：设置体素单元的径长l，对模型的最小aabb包围盒做取整化处理，得到模型的最小aabb'包围盒；
步骤1.6：对模型的aabb'包围盒进行体素化划分，设划分得到的体素单元的集合为d0，记录每个体素单元对应八个顶点的坐标，设所有体素顶点构成的集合为v0。
3.根据权利要求1所述的一种基于点灯法的三维模型精确体素化方法，其特征在于：所述步骤2具体包括以下步骤：
步骤2.1:开始“搜寻点灯法”，调出剖分得到的模型内部的各个四面体顶点的坐标信息；
步骤2.2：计算求解四面体单元e的最小取整包围盒aabb′e，对包围盒aabb′e进行体素单元划分。记录aabb′e包围盒内所有体素单元对应的顶点坐标；
步骤2.3：求解aabb′e包围盒内的所有点与四面体单元e的空间位置关系，根据每个不同的位置关系，返回不同的特征值进行记录；
步骤2.4：根据返回的特征值对点集ve内的各个对应点进行不同的操作：内部的点予以记录，表面的点和外部的点跳过不做处理；
步骤2.5：遍历模型内部的所有四面体单元，循环进行步骤2.3和步骤2.4的操作，将各个四面体单元的点集ve的顶点状态信息，整合到总点集v0中，根据各个体素顶点的状态再对各个体素自身的状态值进行判断，确认体素集d0中有用的体素单元；
步骤2.6：将所有被‘a’标记的体素进行整合和建模，导出三维模型modela。
4.根据权利要求1所述的一种基于点灯法的三维模型精确体素化方法，其特征在于：所述步骤3具体包括以下步骤：
步骤3.1：开始“桁架构造法”，依次调出模型内部各个四面体的顶点和边的空间结构信息；
步骤3.2：以边ab为例，按照笛卡尔坐标系x、y、z三个轴向，分三次进行处理,以x轴方向为例，首先判断ax和bx的大小；
步骤3.3：在获得线段的新起始点a'后，插值计算线段a'b中a'到b上的各个间断点,由间断点查找对应的体素单元用‘b’进行标记；
步骤3.4：按照y、z轴方向处理边ab，同x轴的处理方式一致,接着处理四面体单元e'的其它三个边bc、cd、ad；
步骤3.5：完成当前四面体单元e'的处理，进入下一个四面体单元的处理流程，对于已处理过的重复边不再重复处理；
步骤3.6：遍历完四面体集合d0后，统计在桁架构造法中所有被‘b’标记的体素，整合和建模，导出三维模型modelb。
技术总结