数控仿真中切削面计算的并行化研究＊

于 珊，王子牛，赵鹏阳

(贵州大学 大数据与信息工程学院，贵州 贵阳 550025)

数控加工仿真技术是利用计算机来模拟和验证数控加工的实际过程和结果，针对离散精度高的工件模型，为满足实时性显示要求，必须减少数控加工仿真过程的时间，提高仿真效率。通过查阅和研究大量文献发现目前大量的研究和成果都在传统CPU 上实现并改进几何算法和图形算法。但由于CPU 的串行性、计算速度和内存带宽的劣势，使得某些算法在CPU 上无法进行快速的计算，达不到实时性要求。本文根据文献［1］中提出的基于MC 算法的实体构造模型及其在数控仿真中的应用，采用GPU 代替传统的CPU 进行计算，利用GPU 的并行性、超大的内存带宽以及极高的运算速度等优势，通过并行方式处理刀具空间包围体与工件模型的切削计算加速切削面的显示。

1 GPU 并行计算模式

GPU 起初只负责图形渲染，随着计算机的发展，如今的GPU 架构是具有并行处理能力的架构，具有极强的并行计算能力，能够执行高强度的海量数据任务，数据规模已经达到TB 到PB 量级。在虚拟现实领域，人们对绘制场景也提出了更高要求，需要构建更加精细的场景，同时要求进行实时交互，因此需要快速计算在视角范围内的大量几何物体并绘制场景。

GPU 和CPU 在设计思路上存在很大差异:CPU为优化串行代码而设计，将大量的晶体管作为控制和缓存等非计算功能，注重低延迟地快速实现某个操作;GPU 则将大量的晶体管用作ALU 计算单元，适合高计算强度的应用。在协同并行计算时，CPU 和GPU 应各取所长，快速、高效协同地完成高性能计算任务［2］。CPU 负责管理GPU 的工作，为GPU 提供数据并接收GPU 传回的数据，由GPU 承担复杂而繁重的计算任务。

2 CUDA 编程技术

CUDA 是NVIDIA 推出的运算平台，指的是计算统一设备架构，CUDA 的推出破除传统GPU 硬件架构限制，可以充分地利用GPU 进行并行计算，使得CPU-GPU 协同计算成为可能且更加方便简单。在CUDA 架构下，程序分别在host(主机)和device(设备)上面执行，一个host 和多个device 组成一个CUDA 系统。host 指的是CPU，device 则是GPU，CUDA 一般通过Kernel 来控制GPU 进行计算。每一个Kernel 和CUDA 组织模型的网格Grid对应。多个Block 构成一个Grid，多个Thread 构成一个Block。Kernel 函数由大量GPU 线程并发执行，不同线程处理的数据却各不相同。众多GPU线程以块(Block)和网格(Grid)的层次化结构加以组织。线程块与网格的结构(维数和规模)由用户根据实际需求制定。此外，CUDA为GPU 线程提供了索引自身线程编号以及线程块编号的方法，因此在程序中可以令线程根据自身编号处理不同的数据。与GPU 线程的层次化结构相对应，CUDA提供的编程模型将CPU 中的存储器也加以层次化的组织，线程拥有各自的本地存储，其中存放每个线程的私有变量。线程块拥有各自的共享存储，其中存放块内线程均能够访问的数据。此外，CUDA还为所有线程提供了一个全局存储器(显存)。图1为CUDA 编程模型。CUDA 采用了SIMD 执行模型［3］，该模型可归纳为6 个步骤:

①数据类型初始化:变量的定义与声明。

②存储空间分配:为主机端和设备端变量分别分配存储空间，用来存储不同类型的数据。

③数据传递:从主机端将数据传输到设备端。

④并行执行:调用Kernel 函数，并分配设备端执行参数和函数参数，该函数将会被GPU 内分配到的所有线程分别执行1 次，从而实现单指令多数据的并行处理过程。

⑤结果返回:将设备端计算的结果传回主机端。

⑥释放显存:在GPU 端的全局存储器中回收空间。

图1 CUDA 编程模型

3 数控切削仿真模型

3.1 模型构造

MC 算法是三维数据场中对等值面进行构造的经典算法，由于其原理简单且容易实现，所以得到了广泛的应用。根据MC 算法的相关思想及实现原理，可将其应用到几何仿真中的三维实体模型构造和实体模型加工面的显示计算两个部分。规则三维数据场的构造是通过在某个三维空间区域内沿X，Y，Z 三个方向进行均匀采样，采样间距为Δx，Δy，Δz，那么在该区域内上下对应的8 个点所组成的立方体就构成1 个体素，组成体素的采样点称为体素的角点。图2为单位体素模型结构。

图2 单位体素模型结构

MC 算法主要是遍历数据场中的每个体素，根据体素顶点的标记状态进行组合和分类。每个体素包含8 个顶点，且各顶点均有可能处于等值面内或等值面外(角点位于等值面外则标记为“+”，角点位于等值面内则标记为“－”)，如果体素的某一条边和等值面发生相交，则该条边上两个角点的标记是相反的;反之，如果体素的任意一条边上两个角点的标记相同，那么等值面与该条边未发生相交，所以体素可能有256 种不同的状态［4］。虽然可能的状态有256 种，但很多状态的拓扑结构一样，这就是等值面的二义性。对于MC 算法的二义性问题，已有很多文献论述并提出了一些较好的解决方法这里就不再赘述。经过状态合并后得到最终的15 种基本状态［5］。

3.2 切削面显示

将MC 算法应用于五轴数控仿真中的切削面显示，提出了一种基于MC 算法等值面提取思想的实体模型构造方法，即MC 实体构造法。该实体构造法沿用了MC 算法中对三维规则数据场进行构建的相关原理，以体素作为构造实体模型的基本单元，并对体素中的8 个角点和12 条棱边信息进行存储，图3为单位体素模型的数据存储结构。在数控加工仿真切削计算中，串行依次计算X，Y，Z 三个方向的射线组分别与刀具包围体在对应方向上的交点的值(如:与X 方向射线组求交得到交点的X 方向坐标值)，求得的交点记录在切削体素内，最后遍历所有体素的状态对单位体素内各条边上存在的等值点进行连接，即采用三角面片来近似表达等值面，若离散的采样点越多，那么等值面显示精度也就越高。利用OpenGL 函数对重构的切削面进行显示。

图3 单位体素模型的数据存储结构

4 并行方式的数控仿真显示算法

并行线程处理的是规则三维离散数据场中的体素，而体素之间不存在相互影响的关系，即体素中的等值面片提取不受邻近体素等值面提取过程的影响。所以基于MC 算法的数控仿真切削面计算可以利用GPU 的SIMD 并行方式进行加速处理［6］。传统CPU 实现的数控加工仿真系统采用从三个方向引出的射线组成的射线组分别与刀具包围体进行求交计算得到等值点坐标，但在离散精度很高的情况下，由于使用射线组与刀具包围体求交的方法会带来更大的时间开销，而使用体素存储的边信息与刀具包围体求交点代替以前的求交方法所重建出来的结果能大量减少代数运算，从而减少重建的时间。

本文主要将MC 算法对等值面进行提取的相关计算原理与实现方法应用到数控仿真中切削面的显示，在基于CUDA 并行开发平台的基础上，采用图形处理器GPU 对等值面与边界体素的交点坐标及法向量进行计算［7］，在保证图像质量的前提下，加速数控仿真切削面的提取，从而提高三维图像的绘制速度。具体算法流程:

(1)初始化Grid 和Block，将Block 中的每个线程和三维离散数据空间中的体素一一对应，将线程m 的一维坐标index(index=0，l，…，maxVoxel-Size－l)转化为体素的三维坐标(i，j，k)(i=0，1，…，mCol－1;j=0，1，…，mRow－1;k=0，1，…，mVer－1)，并以该坐标作为体素的左下角点的坐标，然后沿三个方向上进行釆样，获取体素p 另外7 个邻近的角点的坐标，完成体素p 的构建。

(2)判断各角点在当前刀具包围体空间范围的内部还是外部，标记各角点的状态(若角点在刀具包围体内部，则表示该角点已被切削;若角点在刀具包围体外部，则表示该角点未被切削)，确定体素的拓扑结构，根据体素的拓扑结构查询构型索引表得到体素构型索引cubeIndex。

(3)求解刀具包围体与体素12 条边的交点坐标，存入到开辟的共享显存空间vertList［12］［32］数组中。

(4)根据体素的构型索引号cubeIndex 查询交点数目索引表numVertTable，确定体素的构型索引号cubeIndex 和刀具包围体与各体素的交点的个数numvertex。图4为体素角点状态及256 种构型索引表和交点数目表numVertTable。

图4 体素角点状态及256 种构型索引表和交点数目表numVertTable

(5)以numvertex为循环控制条件，每隔三个顶点进行一次循环。利用体素拓扑构型索引cubeIndex 查询三角形数组triTable［256］［16］。获取三角形三个顶点(即等值点)所在的边号el，e2，e3(e=0，1，…，11)。将el，e2，e3 作为索引查询vertList 数组，获取三角形三个顶点的空间几何坐标v0，v1，v2，利用向量叉乘法计算出三角形面片的法向量，最后将所有三角形的顶点坐标和法向量保存到显存中。

(6)从显存依次取出顶点和法向量进行三角形拟合，利用OpenGL 函数绘制切削面，实现3D 渲染。

以数控加工的五轴圆饼为例，通过测试本文提出的并行方式进行切削计算的时间与原来串行方式进行切削计算的时间进行对比:离散精度越高即切削点越多，切削计算的时间越长，并行与串行的切削计算耗时加速比越大，说明该方法有效地减少了切削计算耗时。表1为并行方式与串行方式切削计算耗时加速比。

表1 并行方式与串行方式切削计算耗时加速比

实验环境为:Visual Studio 2008、CUDA3.2;操作系统是windows7(32 位);GPU为NVIDIAGe-ForceGTX 570;显存为2G，CPU为i5－2300，其主频为2.80GHz;主存为4G。

5 结束语

针对传统CPU 实现的数控加工仿真系统，采用循环遍历体素数组对其进行求交计算和绘制，在工件模型构建离散精度较高时，这种遍历体素的方式相当费时，本文应用GPU 代替传统的CPU 进行数控加工仿真中的切削计算，减少了切削计算时间，并通过构建查找表的方式加快提取与之匹配的切削面的构型类型，从而提高了数控仿真的显示速度。

［1］李杨.基于MC 算法的数控加工过程三维实体仿真的研究与实现［D］.贵阳:贵州大学，2012.

［2］卢风顺，宋君强，银福康，等.CPU/GPU 协同并行计算研究综述［J］.计算机科学，2011，38(3):5－10.

［3］张庆科，杨波，王琳，等.基于GPU 的现代并行优化算法［J］.计算机科学，2012，39(4):304－311.

［4］黄明艳，王子牛.基于CUDA 的数控仿真加工面显示算法的研究［J］.贵州大学学报:自然科学版，2013，30(4):70－73.

［5］姜赟.基于面绘制的图像三维可视化算法研究［D］.成都:电子科技大学，2007.

［6］李晋舟.基于GPU 的移动立方体算法及其应用［D］.西安:西安电子科技大学，2010.

［7］程咏华.基于CUDA 的医学图像3D 可视化技术的研究［D］.成都:西南交通大学，2013.