一种三维模型体素化实体填充方法

摘要

本发明提供一种三维模型体素化实体填充方法，首先，输入边界体已经素化的三维模型，并选取三维模型边界的外接长方体以缩小填充空间；其次，选取外接长方体的角落点作为种子的填充点，然后对外接长方体空间中三维模型的外部体素化空间进行种子填充，得到三维模型的外部体素化空间；最后，提取外接长方体空间中未填充的空间，作为三维模型的内部实体空间，即为三维模型的实体体素化的目标填充对象；并对三维模型的内部实体空间进行填充。本发明三维模型体素化实体填充方法实用性强和适应性强，该三维模型体素化实体填充方法可有效避免因模型对象多和模型复杂而产生填充不完整和填充错误的问题，从而大大提高三维模型填充的效率和填充的准确性。

说明书

技术领域

本发明涉及计算机图形处理技术领域，更具体地说，涉及一种三维模型体素化实体填充方法。

背景技术

近年来，随着图形硬件技术和三维模型渲染技术的发展，计算机辅助设计(CAD)能利用计算机及其图形设计软件帮助设计人员快速设计。三维模型已成为了第四种多媒体数据类型，三维模型因其独特的空间特性，应用领域广泛，在工业制造、虚拟现实、医学成像、多媒体教学、影视动画和三维地理系统等领域中广泛应用。三维模型的建模方法复杂并且格式多样，针对不同的应用场景有不同存在的形式，而如何利用一种通用的建模方法去操作三维模型，成为了三维模型建模的基本问题，也是三维模型应用领域一个重要的研究课题。

目前多数三维模型建模费时费力和计算复杂度高，模型格式多样复杂。在三维模型的特征表达中通常要反映模型的空间结构信息，而常用的三角网格模型只能反映模型的外部结构信息，而点云模型通常结构散乱，点分布不均。现阶段，一种体素化的格式模型利用离散二值栅格表达三维模型，将三维模型实体化，包含了模型的内部结构信息。这样采用三维模型的内部结构信息可准确判断三维模型实体体素化的优劣情况。而在判断三维模型实体体素化的优劣情况时，体素化的速度和完整性是两个重要的因素。

因此，如何设计一种三维模型的体素化实体填充方法，以得到三维模型的内部结构信息来判断三维模型实体体素化的优劣情况，是现阶段三维模型建模领域中反映模型空间结构信息的重要手段之一。

发明内容

本发明的目的在于克服现有技术中的缺点与不足，提供一种实用性强和适应性强的三维模型体素化实体填充方法，该三维模型体素化实体填充方法可有效避免因模型对象多和模型复杂而产生填充不完整和填充错误的问题，从而大大提高三维模型填充的效率和填充的准确性。

为了达到上述目的，本发明通过下述技术方案予以实现：一种三维模型体素化实体填充方法，其特征在于：

首先，输入边界体已经素化的三维模型，并选取三维模型边界的外接长方体以缩小填充空间；

其次，选取外接长方体的角落点作为种子的填充点，然后对外接长方体空间中三维模型的外部体素化空间进行种子填充，得到三维模型的外部体素化空间；

最后，提取外接长方体空间中未填充的空间，作为三维模型的内部实体空间，即为三维模型的实体体素化的目标填充对象；并对三维模型的内部实体空间进行填充。

在上述方案中，本发明的三维模型体素化实体填充方法是采用对三维模型的外部体素化空间进行种子填充的填充模式，来得到内部实体空间的，从而避免了传统方法中直接采用在内部实体空间进行种子选取点导致不确定性的问题，本发明方法能够确定种子选取点一定在三维模型的外部体素化空间。通过对外部体素化空间进行种子填充方法则可得到已填充模型空间和未填充模型空间，这里的未填充模型空间即为目标填充模型，也为内部实体空间。该三维模型体素化实体填充方法可有效避免因模型对象多和模型复杂而产生填充不完整和填充错误的问题，从而大大提高三维模型填充的效率和填充的准确性。

具体地说，包括以下步骤：

步骤s101：在尺寸m的三维离散栅格空间G_m×m×m中，每个栅格为g_x,y,z，输入三维模型M的边界体素点集则三维模型的内部实体空间设置为D，故M＝BUD；其中，三维模型位于边界的体素点G_x,y,z按以下公式标记：

即栅格g_x,y,z位于三维模型的边界体素点时，该栅格g_x,y,z对应的体素点G_x,y,z标记为1，否则G_x,y,z标记为0；

步骤s102：选取三维模型边界的外接长方体：根据边界体素点集B，计算外接长方体的体素点G_x′_.y.z,x∈[x_min,x_max]∩y∈[y_min,y_max]∩z∈[z_min,z_max]，以缩小填充搜索空间；其中，

其中为点b^t对应的位置下标；

步骤s103：选取外接长方体的角落点作为种子的填充点，从外接长方体的八个角落点中选取其中一个角落点作为种子的填充点s(x_min,y_min,z_min)，则该填充点对应的栅格

步骤s104：对外接长方体空间中三维模型的外部体素化空间进行种子填充；种子填充的过程是在外接长方体空间内采用广度优先搜索方法从种子的填充点s(x_min,y_min,z_min)开始进行填充：当搜索至边界体素点或者超越外接长方体的空间时，停止搜索；将广度优先搜索过程中所经过栅格g′_x,y,z对应的体素点G′_x,y,z设置为-1，则体素点G′_x,y,z标记为-1的空间为外接长方体空间中三维模型的外部体素化空间；

步骤s105：提取外接长方体空间中未填充的空间，作为三维模型M的内部实体空间；体素点G′_x,y,z标记为0的空间则表示未填充的空间，即是所求的三维模型的内部实体空间D；

在内部实体空间D内的体素点的灰度值设置为统一数值，以实现三维模型内部实体空间D的填充。

在步骤s103中，所述外接长方体的角落点是指外接长方体的顶点。

在步骤s104中，采用广度优先搜索方法从种子的填充点s(x_min,y_min,z_min)开始进行填充是指：采用广度优先搜索方法从种子的填充点s(x_min,y_min,z_min)开始，对栅格的上、下、左、右、前和后六个搜索方向进行填充。

在上述步骤s104中，对外部体素化空间进行填充时，选取的种子是位于外接长方体的角落点来作为种子的填充点，从而使得种子的选取规则简单并且准确，不与模型的复杂度程度相关。而填充过程中，直接填充外接长方体中三维模型的外部体素化空间，一旦三维模型的外部体素化空间确定下来，则剩下未填充的空间则为三维模型的内部实体空间，既是目标填充模型。上述的广度优先搜索方法是现有的算法，而种子填充算法也是现有的算法。

与现有技术相比，本发明具有如下优点与有益效果：本发明三维模型体素化实体填充方法实用性强和适应性强，该三维模型体素化实体填充方法可有效避免因模型对象多和模型复杂而产生填充不完整和填充错误的问题，从而大大提高三维模型填充的效率和填充的准确性。

附图说明

图1是本发明三维模型体素化实体填充方法的流程图；

具体实施方式

下面结合附图与具体实施方式对本发明作进一步详细的描述。

实施例

如图1所示，本发明三维模型体素化实体填充方法是这样的：

首先，输入边界体已经素化的三维模型，并选取三维模型边界的外接长方体以缩小填充空间；

其次，选取外接长方体的角落点作为种子的填充点，然后对外接长方体空间中三维模型的外部体素化空间进行种子填充，得到三维模型的外部体素化空间；

最后，提取外接长方体空间中未填充的空间，作为三维模型的内部实体空间，即为三维模型的实体体素化的目标填充对象；并对三维模型的内部实体空间进行填充。

具体地说，包括以下步骤：

步骤s101：在尺寸m的三维离散栅格空间G_m×m×m中，每个栅格为g_x,y,z，输入三维模型M的边界体素点集则三维模型的内部实体空间设置为D，故M＝BUD；其中，三维模型位于边界的体素点G_x,y,z按以下公式标记：

即栅格g_x,y,z位于三维模型的边界体素点时，该栅格g_x,y,z对应的体素点G_x,y,z标记为1，否则G_x,y,z标记为0；

步骤s102：选取三维模型边界的外接长方体：根据边界体素点集B，计算外接长方体的体素点G′_x.y.z,x∈[x_min,x_max]∩y∈[y_min,y_max]∩z∈[z_min,z_max]，以缩小填充搜索空间；其中，

其中为点b^t对应的位置下标；

步骤s103：选取外接长方体的角落点作为种子的填充点，从外接长方体的八个角落点中选取其中一个角落点作为种子的填充点s(x_min,y_min,z_min)，则该填充点对应的栅格

步骤s104：对外接长方体空间中三维模型的外部体素化空间进行种子填充；种子填充的过程是在外接长方体空间内采用广度优先搜索方法从种子的填充点s(x_min,y_min,z_min)开始进行填充：当搜索至边界体素点或者超越外接长方体的空间时，停止搜索；将广度优先搜索过程中所经过栅格g′_x,y,z对应的体素点G′_x,y,z设置为-1，则体素点G′_x,y,z标记为-1的空间为外接长方体空间中三维模型的外部体素化空间；

步骤s105：提取外接长方体空间中未填充的空间，作为三维模型M的内部实体空间；体素点G′_x,y,z标记为0的空间则表示未填充的空间，即是所求的三维模型的内部实体空间D；

在内部实体空间D内的体素点的灰度值设置为统一数值，以实现三维模型内部实体空间D的填充。

其中，在步骤s103中，所述外接长方体的角落点是指外接长方体的顶点。

在步骤s104中，采用广度优先搜索方法从种子的填充点s(x_min,y_min,z_min)开始进行填充是指：采用广度优先搜索方法从种子的填充点s(x_min,y_min,z_min)开始，对栅格的上、下、左、右、前和后六个搜索方向进行填充。

在上述步骤s104中，对外部体素化空间进行填充时，选取的种子是位于外接长方体的角落点来作为种子的填充点，从而使得种子的选取规则简单并且准确，不与模型的复杂度程度相关。而填充过程中，直接填充外接长方体中三维模型的外部体素化空间，一旦三维模型的外部体素化空间确定下来，则剩下未填充的空间则为三维模型的内部实体空间，既是目标填充模型。

上述体素点G_x,y,z是包括外接长方体的体素点G′_x.y.z的，G_x,y,z标记为1则为边界体素点，G_x,y,z标记为0则不是边界体素点，G′_x.y.z标记为-1则为外部体素化空间的体素点，G′_x.y.z标记为0的则为内部实体空间体素点，即在模型的体素点G_x,y,z标记为0中，在外接长方体空间内标记为0的体素点G_x,y,z也就是标记为0的体素点G′_x.y.z。所以在步骤s105中不需要另外标记体素点G′_x.y.z为0，只需判断在外接矩形中哪些体素点G_x,y,z标记为0，则可知道标记为0的体素点G′_x.y.z，从而可判断外接长方体空间中未填充的空间。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。