摘要：为了提高图形处理器中裁剪运算速率，我们提出一种并行化的思想，在得到正确结果的基础上，通过对单个处理机和多个处理机处理裁剪所用的时间进行比较，多个处理机同时工作可以在一定程度上减少运算时间。
关键词：裁剪算法；并行化
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）03-0606-04
平面裁剪是GPU（图形处理器）流水线结构中的重要一环。它是使用用户自定义的裁剪平面对图元进行裁剪。与每个观察体裁剪平面垂直于某个坐标轴不同，这些附加的裁剪平面可以有任意方向。最经典的裁剪算法cohen-Sutherland算法[1]和Sutherland-Hodgeman（SH）算法[2]。需要注意的是我们必须开启和禁用每一个裁剪平面，这里支持最多六个裁剪平面。
1 算法介绍
1.1 Sutherland-Hodgeman裁剪算法
该算法是图形处理中裁剪的经典算法，其中我们研究的是对点、线、三角形的裁剪，该文着重介绍线裁剪算法的并行实现[3]。
线的裁剪算法：用定义的裁剪面依次来裁剪多边形的每一条边，然后重新组合。假设当前处理的多边形的边为SP（S为前一点，P为当前点），边SP与裁剪线的位置关系要考虑下面四种情况：
1）若S、P均在内侧，则当前点P保存到新多边形中；
2）S在内侧且P在外侧，则交点t保存到新多边形中；
3）S、P均在外侧，则没有点被保存到新多边形中；
4）若S在外侧，P在内侧，则交点t、当前点P保存到新多边形中；
1.2 交点的计算以及线性插值的计算
我们根据线段的两个端点的位置信息判断线段与裁剪平面的四种位置关系，如果有交点，计算交点，然后用插值算法计算出交点的属性信息。这里用到了线性插值的算法，它是计算机图形学领域广泛使用的一种简单插值方法。
已知平面方程为[Ax+By+Cz+D=0]，法向量为[N=（A，B，C）]，因为[Pt]为直线与平面的交点，所以Pt也是平面上的点，[PPt]与[N]的点积为0，因为Pt同样满足平面方程[Ax+By+Cz+D=0]将Pt代入后得到：[A[x1+t（x2-x1）]+B[y1+t（y2-y1）]+C[z1+t（z2-z1）]+D=0]
进一步有：
至此平面剪裁的算法已经介绍完毕，但我们仅通过对算法的研究，完全看不出结论，所以需要用数据进行验证与说明。分别采用1个，4个，8个PE对线裁剪进行仿真验证，通过对其运算时间的比较说明并行结构能够更高效地实现裁剪。
2 设计与验证
裁剪模块需要处理的图元有点、线和三角形，该文以线裁剪算法为例说明如何使用多个处理器来实现该算法。假设启用六个裁剪平面，由于裁剪过程要用自定义的六个平面作为裁剪面，传统的串行裁剪算法需要循环6次完成这一操作，再对12个属性信息进行插值运算。
在并行系统中，对于线裁剪而言我们采用下面几种方法划分任务，使算法分别在1个，4个和8个处理器上运行，实现算法的并行化。其中每个处理单元（PE）的通信地址如下图：
第一种情况：单处理机上的线裁剪算法的描述：
设置两个端点的坐标、属性信息和裁剪平面的参数。映射到PE0的操作是：
1）计算6个平面参数与模型视图逆矩阵的乘积，即
（Ai`，Bi`，Ci`，Di`）=（Ai，Bi，Ci，Di）*M-1 （i=0，1，2，3，4，5）；
2）依次判断6个裁剪平面与直线的位置关系，得到新的直线L01L11；
3）利用直线插值公式计算L01L11的属性信息。
第二种情况：4个处理机上的线裁剪算法的描述：
1）将两个端点的坐标、属性信息以及裁剪平面的参数映射到PE0和PE1上
2）PE0和PE1分别完成三个平面的裁剪，裁剪后为L02和L12
3）通过端口3fe传递给PE2，PE2接到数据后再给PE3，这里PE2，PE3分别完成6
个属性的插值计算。
第三种情况：8个处理机上的线裁剪算法的描述：
配置两个端点的坐标、属性信息以及裁剪平面的参数。
1）映射到PE0、PE1、PE2、PE3、PE7、PE6上的操作相同，完成1个平面的裁剪，裁
剪后的结果传递给PE4和PE5；
2）PE4和PE5执行相同的操作，分别进行6个属性的插值计算
当8个PE都同时工作时，我们以工作耗费的时钟数为标准来测试流水线的工作效率，
这时统计每个PE的实际执行时间，时钟数最大的PE作为流水线的工作时间。
验证的平台为PAAG，该环境下目前只允许汇编语言的成功编译与运行。PAAG运行环
境如下图所示：
我们可以很清楚的看到，采用并行算法，我们达到所需的结果需要的时间在成倍数减少，这样大大地减少了运算的时间，从而提高了PE的使用效率。这对图形学的计算效率的提高具有十分重要的意义。
我们知道，在裁剪和其他一些GPU的常见算法中，用的较多的计算是矩阵乘和矩阵加，假如我们要对两个4*4的矩阵进行相乘的操作，如果用单核的处理器来实现的话，可能会很慢，而若用多个处理单元来实现的话，处理的速率就会很快。
3 总结
本文采用了并行的思想对GPU的平面裁剪算法进行了研究与验证，可以发现，通过采用并行化的结构，可以提高闲置PE的使用效率，很大程度上节省了运算的时间。仿真验证结果表明：在并行结构的验证平台上，能够正确有效地处理裁剪算法，同时能够提高设备的性能和使用效率。
参考文献：
[1] 王浩朋.二维图形的裁剪算法研究与改进[D].西安电子科技大学，2011.
[2] 查理.图形处理器中剪裁器的设计与实现[D].西安邮电大学，2012.
[3] 李涛，肖灵芝.面向图形和图像处理的轻核阵列机结构[J].西安邮电学院学报，2012.
相关专题：核心期刊论文发表 电商对传统商业的冲击
