3D 模型均匀细分算法及其GPU 实现方法研究

刘轩　黄海于

摘要：3D模型的细分是计算机图形学重要的研究内容，在对较为复杂的3D模型进行高精度细分时，需要进行大量的计算，CPU并不能很好地完成该任务，GPU具有并行架构，计算能力十分强大，因此选择使用GPU对细分算法进行加速，可以极大地提高模型细分的速度。文章设计了一种3D模型的均匀细分算法：扫描线-栅格填充法。对存储模型信息的文件进行预处理，提取出细分所需要的数据，把对模型的均匀细分转化为对三维空间中若干封闭图形的均匀细分，将整个填充区域栅格化，利用扫描线算法对每个栅格进行填充。文章讨论了该算法在GPU上的实现方法，展示了细分后的网格化3D模型，对比评估了该算法在CPU和GPU上的性能表现，探讨了如何在GPU上获得更好性能的方法。

关键词： 图形处理；模型细分；GPU并行处理；扫描线-栅格法；网格化模型

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2024）13-0027-04 开放科学（资源服务）标识码（OSID） ：

0 引言

随着科技的不断进步，三维建模技术在计算机模拟领域的作用也越来越重要[1]。在工业制造领域，利用三维建模技术对其进行仿真模拟，可以真实地反映切削加工过程，清晰呈现工件加工后的形态，提高了生产效率，保证了加工质量[2]。在模拟加工过程中，需要对刀具和工件之间的碰撞进行检测，涉及大量的运算[3]。若工件模型中三角面的大小各不相同，会严重影响模拟加工的速度，因此对工件模型按加工精细度进行均匀细分是非常必要的。

对3D模型进行均匀细分时，传统的扫描线法在填充较为复杂的图形时效果不佳[4]。文献[5]提出了基于栅格的任意复杂区域自动填充算法，但该算法的细分精度和效率无法满足工业加工的要求。本文结合扫描线和栅格填充算法，提出了一种扫描线-栅格的填充方法。将整个模型拆分为若干个三维空间中的超平面，将超平面转化为二维平面上的封闭多边形并使其所在区域栅格化，再利用扫描线算法对各栅格进行填充，实现图形的均匀细分。该算法在CPU上实现比较容易，但工业加工领域中所采用的模型都比较复杂，对精细度的要求非常高，CPU无法满足对处理速度的要求。GPU采用大规模并行处理架构[6]，能同时处理多个栅格，从而快速完成复杂模型的均匀细分。

1 扫描线-栅格算法

本文使用的3D模型以STL文件格式存储。STL 文件包含了模型中每个三角形的几何信息[7]。在进行3D模型细分前，先对模型文件进行预处理，将共面三角形合并为封闭多边形，然后将其转换到XY平面上。在细分时，求出封闭多边形的最小矩形包围框，按所给精细度将矩形包围框分为若干栅格；计算扫描线与图形的交点和所在栅格的序号；以相邻两栅格作为待填充区域进行填充。对所有封闭图形采用上述方法进行细分，就能实现对三维模型的均匀细分。

1.1 图形预处理

1.1.1 共面三角形的合并

利用从STL文件中得到的三角形邻接信息求共面三角形，使用种子生长法，需要用到一个代表当前平面号的整型变量numTri（初值为-1） 、记录各三角形所在平面号的数组sur和一个循环队列。算法如下：

1） 选择一个初始三角形作为种子，将其入队列并标记，使numTri的值加1，将数组sur中对应此三角形的元素值设为numTri；

2） 将种子三角形出队列，判断其邻接三角形是否未标记且与它共面，是则将这些三角形入队列并标记，并且把数组sur中对应这些三角形的元素值设为numTri，否则不对这些三角形和数组sur做任何处理；

3） 将队列中三角形依次出队列，判断其邻接三角形是否未标记且与它共面，是则将这些三角形入队列并标记，并且把数组sur中对应这些三角形的元素值设为numTri，否则不对这些三角形和数组sur做任何处理；

4） 当队列为空时，得到一个共面三角形的信息；

5） 返回第1步，重新寻找下一个种子三角形；

6） 重复第2～5步，直到所有三角形均被标记，算法结束，此时数组sur中的每个元素值就代表了各三角形所在的平面序号。

1.1.2 图形边缘的提取

将各三角形按所在平面序号加入所属的空间平面，就得到了若干封闭图形。这些图形包含内部边和边缘上的边，而扫描线算法只要求保留图形边缘。图形边缘上的三角形一定有一条边没有邻接三角形，通过三角形邻接信息求出所有符合条件的边，只保留这些边，就能得到图形的边缘。

1.1.3 坐标转换

在得到各空间平面上的封闭图形后，把每个封闭图形都转换到XY平面上，根据某封闭图形所在的空间平面上任意一点和法向量构建局部坐标系。

设P =（Px，Py，Pz，1） ，n =（nx，ny，nz，0） 为空间平面上一点和法向量（用作z 轴）相对于世界坐标系的齐次坐标，则任取一个与n 正交的向量u =（ux，uy，uz，0） 作为x轴，再用u 和n 的叉乘结果v =（vx，vy，vz，0） 作为y 轴。这样从局部坐标系至世界坐标系的坐标变换矩阵为：

初始状态下，封闭图形上所有点都用世界坐标系的坐标表示，要将它转换到XY平面上，使用W的逆矩阵对所有点进行坐标变换即可。

1.2 扫描线求交

将封闭多边形转换到XY平面后，计算它在x 轴和y 轴上的最大值和最小值，得到该图形的一个长方形包围框，将此包围框横向纵向按照所给精度均匀分为m 行n 列，使用m 条分别处于每行正中间且和x轴平行的直线作为扫描线。

设有一条扫描线y = ys，依次判断封闭图形各条边和它的相交情况并记录交点信息。设封闭图形中某条边的两个端点的坐标为（xi，yi） 和（xi+1，yi+1） ，则：

1） 当yi = yi+1，即该边与扫描线平行时，没有任何交点，直接略过该边。

2） 当（ys - yi）（ys - yi+1） < 0时，该边与扫描线有一个交点，由式（2） 得出它的横坐标：

3） 当ys = yi或ys = yi+1，此时会出现角点问题，针对这种情况，可对图形中各边采用上闭下开的原则[8]，在一条边的两个端点中，上端点采用闭区间，可计算此处与扫描线的交点；下端点采用开区间，不计算此处与扫描线的交点。此原则能保证每条扫描线上的交点个数为偶数，此时交点坐标已知，无须计算。

1.3 特殊情况的处理

各条扫描线的间距是固定的，在许多情况下，扫描线和图形中各边无法匹配，这会使某些扫描线和图形边界的交点数被误记为0。针对此类问题，需要做近似化处理，当某条非水平边有一个端点和某条扫描线的距离足够近时，就认为它们相交。图1（a） 是由共面三角形合并生成的一个封闭图形，图1（b） 为保留其边缘部分后得到的图形。在图1（c） 中，对该图形使用本算法进行均匀细分时产生了上述问题，图形上出现了空洞。在近似化处理后，如图1（d） 所示，模型上的空洞问题得到解决。

1.4 使用栅格进行图形均匀细分

本文将扫描线法与栅格法结合，将一条扫描线与一行栅格对应，从而使传统区域填充算法中对像素点的填充转变为对栅格的填充。

在得到了一条扫描线上与封闭图形的所有交点之后，按照横坐标值从小到大依次排列，将它们两两视为一组，作为一段待填充区域。对于一组交点，分别计算两个点所在的方格序号，其中行序号与扫描线所在行相同，列序号可由式（3） 求得：

其中，x 为交点横坐标值，left是封闭图形矩形包围框最左端的横坐标值，tessellation为给定的精细度，┌ ┐为向上取整符号。

计算出两个交点所在的方格序号后，对它们之间的每个方格使用两个大小相同的三角形进行填充即可。对整个封闭图形完成填充后，就实现了对该图形的均匀细分。

2 算法在GPU 中的实现

机械加工过程中所涉及的模型比较复杂，对精细度的要求也比较高，导致填充过程中涉及大量的计算。GPU适合处理计算密集型任务[9]，将填充任务交给GPU来执行，可以大大提高细分的速度。

2.1 在GPU 上的实现过程

对于每组交点，前面的算法已分别求出它们所在栅格单元号。GPU将对两栅格和它们之间的栅格进行填充，每次向GPU传送一对栅格信息，经GPU处理后将目标区域中的栅格填充并输出。

绘制时每次的输入是扫描行上的一对栅格信息，输出是对应区间内的若干三角形构成的栅格。因此，将填充任务交给GPU端的几何着色器（GS） 完成，GS 能够接收完整的图元（如单个点、线段的两个点、三角形的三个点），处理后可以输出指定的图元，适合处理本文中的栅格填充操作。

为了向GPU中的GS传送待填充的栅格信息，设计合适的数据结构十分重要。栅格信息除了所在列号和行号外，还应包含所在封闭图形平面的法向量、细分精细度，以及二维到三维空间的转换矩阵信息等。本文在Direct3D 12环境下进行图形程序开发，向GPU传输数据时，要将它们包装为4个一组的向量形式，由于每对相邻的栅格都在同一平面上，它们除了列号之外的信息均相同，因此每次使用一个结构体变量表示一对栅格，结构体定义如下：

其中DirectX：：XMFLOAT4为DirectX中的一种向量类型，可存储4个float类型的分量数据。Pos存储第一个栅格列号、第二个栅格列号、栅格行号和细分精细度；Nor存储栅格所在平面的法向量；Matrix0、Ma? trix1、Matrix2、Matrix3分别存储4x4的转换矩阵每一行的数据。

将模型各超平面上的所有栅格对求出来之后，把它们依次按上述格式封装并传输至GPU。一对栅格数据被GS接收后，判断它们所在的列号是否相同，若相同则只计算填充一个栅格所需的两个三角形的顶点信息；若不同，则计算填充两个栅格之间所有栅格的若干三角形顶点信息。此时，各顶点还处于XY平面上，要将各顶点用转换矩阵W进行变换，使其回到原位置。最后，将各顶点以三角形带的形式输出，即可完成对一块目标区域的填充。

GS每次处理一对栅格，输入为一个代表栅格对的pieceVertex类型变量gin，输出为填充栅格区域的三角形顶点集合triStream。上述算法的伪代码如下：

输入：待填充的栅格对信息gin

输出：用于填充栅格区域的三角形集合triStream

1） function GS<（gin，triStream）

2）column1<-gin.Pos[0];

3）column2<-gin.Pos[1];

4）y<-gin.Pos[2];

5）tes<-gin.Pos[3];

6）nor<-gin.Nor;

7）trans<-（gin.Matrix0，gin.Matrix1，gin.Matrix2，gin.Matrix3）

8）for column<-column 1 to column 2 do //填充一个或若干栅格

9）v[0]<-（column*tes，y+0.5*tes，0，1）//计算此栅格的四个顶点位置

10）v[1]<-（（column+1）*tes，y+0.5*tes，0，1）

11）v[2]<-（column*tes，y-0.5*tes，0，1）

12）v[3]<-（（column+1）*tes，y-0.5*tes，0，1）

13）for i<- 0 to 3 do

14）v[i]<- mul（v[i]，trans）//将顶点位置转换回三维空间

15）triStream<-（v[0]，v[2]，v[1]）//将两个三角形加入结果集中

16） triStream <- （v[1]， v[2]， v[3]）

17） end function

2.2 在GPU 上获得更好的性能

一对栅格之间的栅格数是不确定的，二者的距离和细分的精细度都会影响这个数量。而GPU出于对GS性能方面的考量，限制了GS每次能输出的标量数，此个数为每次输出元素的顶点数量和输出元素个数的乘积。每个栅格包括2个三角形，每个三角形有3 个顶点，因此每输出一个栅格时标量数为6。GS每次输出的标量数在大于40时，性能就会开始下降，考虑到该项限制，本文选择将最大输出标量数定为84，每次最多填充并输出14个连续的栅格。需要在向GPU 传输前进行判断，若一对栅格间的栅格数不超过14，则直接传输；若大于14，则要将这对栅格进行分割，使分割后的每个子段中需要填充的栅格数不超过14。

将每对栅格经过上述的检查处理后，在不超过GS 规定的情况下尽可能每次填充一行上较多的栅格，在后续的具体实验中得到了较好的效果。

3 实验结果与分析

3.1 细分结果分析

对一个STL模型使用本文算法进行均匀细分，将细分的精细度分别设置为1、0.5、0.2，单位均为cm，如图2所示。结果表明，精细度越高，网格越密集，细分效果越好。

3.2 细分效率分析

为测试该算法在GPU中的优势，对2个STL文件大小（单位：KB） 不同的模型使用不同精度（单位：cm） 进行均匀细分，对比它们在CPU和GPU中进行细分任务时所花费的时间（单位：s） ，结果见图3（a） 。结果表明，本文算法在GPU上的性能表现远远超过了在CPU 上的版本。在模型越复杂、精细度越高时，GPU中的算法优势越大。

为测试GPU中的算法在处理不同模型时的效率表现，对3个STL文件大小（单位：KB） 不同的模型使用多种精细度（单位：cm） 进行均匀细分，对比它们在GPU中进行细分任务时所花费的时间（单位：s） ，结果见图3（b） 。结果表明，在精度要求较低时，模型的文件大小对GPU中算法的处理速度几乎没有影响，这是因为GPU中对数据的处理和运算是并发进行的，在精细度情况下，不同模型对应的计算量的差距不是非常大，因此在GPU中经过并行处理所耗费的时间也相差不大；在模型间的复杂度差距很大或要求使用较高的精细度时，GPU中的处理时间才会有明显差距。

4 结束语

针对传统细分方法无法均匀细分模型的问题，提出了一种基于扫描线算法和栅格的均匀细分模型的算法。通过从模型STL文件中得到的信息，将对模型的每个三维空间面的处理转化为对二维平面上封闭图形的处理，对每个图形用栅格作为单位进行区域填充，实现对整个模型的均匀细分，最后将填充任务交由GPU处理。经过测试，该方法可以正确地将模型按精细度均匀细分，得益于GPU强大的计算能力，算法效率有较大的提升。

参考文献：

[1] 栾悉道，应龙，谢毓湘，等. 三维建模技术研究进展[J]. 计算机科学，2008，35（2）：208-210，229.

[2] 李志鹏. 论三维建模技术在机械产品设计中的应用[J]. 内燃机与配件，2021（21）：216-218.

[3] 项立富. 信息时代背景下数控加工仿真技术与软件的开发路径[J]. 南方农机，2019，50（22）：194.

[4] 石燕.浅析区域填充算法[J]. 计算机光盘软件与应用，2014，17（9）：131-132.

[5] 邱国清. 基于栅格的任意复杂区域自动填充算法[J]. 图学学报，2018，39（3）：419-423.

[6] 董荦，葛万成，陈康力. CUDA并行计算的应用研究[J]. 信息技术，2010，34（4）：11-15.

[7] 朱虎，杨忠凤，张伟. STL文件的应用与研究进展[J]. 机床与液压，2009，37（6）：186-189.

[8] 李慧贤，马创新，马良. 增材制造中GPU并行扫描线填充算法[J]. 热加工工艺，2023（13）：100-104，113.

[9] 田卫明，刘富强，谢鑫，等. 基于GPU粗细粒度和混合精度的SAR后向投影算法的并行加速研究[J]. 信号处理，2023，39（12）：2213-2224.

【通联编辑：光文玲】