改进的三维剪裁算法及其硬件设计

2013-10-17邓惠子韩俊刚

电子科技 2013年7期

邓惠子，韩俊刚，马超，杨婷，查理

(西安邮电大学专用集成电路中心，陕西西安 710061)

随着人类对视觉感受的无限追求，越来越多复杂细腻的图形图像出现在各类显示设备上，比如手机、平板电脑等［1］。在此背景下，将主处理器从繁重的图形计算任务中解放出来，设计一个专用的图形处理器变得越来越迫切［2］。图形处理器以处理复杂3D图形为主要任务［3］，也包含纹理贴图和光照显示［4］，同时实现对图像的裁剪功能。三维剪裁使用视景体对物体进行裁剪，保留 Cannonical View Volume(CVV)内的部分［5］。常用算法(Sutherland-Hodgman，S-H)在进行裁剪时较快捷［1］，但计算顶点属性时存在大量的冗余操作。三维裁剪的CVV存在6个固定的裁剪平面，依照S-H算法每次用一个裁剪面进行操作，完成后会对产生的新点进行属性插值，然后对由新点构成的图形进行新一轮裁剪。如果本次产生的新点在新一轮计算中被裁剪掉，则之前计算的属性不仅占用了存储资源还使系统进行了无用的操作。

针对常用算法中存在的问题，提出一种改进的裁剪算法以保证在进行插值属性时的点都在CVV内。同时，利用多边形的几何关系对双线性插值进行改进。最终利用硬件进行仿真，证明针对裁剪进行的改进是合理的。

1 改进算法介绍

三维剪裁模块使用规范视景体即单位立方体对点、线或三角形等图元进行裁剪，运用插值计算新点的各种属性，根据裁剪后的顶点数目完成图元的再装配。以下为三角形的插值计算方法，如图1所示。

图1 三角形插值计算

根据几何学可知三角形中任意一点与其3个顶点都有线性关系［6］，可知公式

成立，并且k1+k2+k3=1，可以使用三角形原始3个顶点的属性值，插值求得其内任意一点的属性值。如图 1 所示三角形顶点A(xa，ya，za，wa)、B(xb，yb，zb，wb)、C(xc，yc，zc，wc)，设点G(xg，yg，zg，wg)的坐标。根据上述插值思想可得

式中，k1、k2、k3为线性插值的系数，可得k1、k2、k3。当求出系数k1、k2、k3后，其内任意一点G的属性有

其中，k1+k2+k3=1。

2 硬件设计

2.1 三维剪裁的数据通路与接口

接受器接收到命令以后，如果命令是CMD_XUPT_SHAPE，然后根据命令中的图元类型选择是点、线还是三角形剪裁，选择不同的剪裁控制器;否则直接输出。

接收到CMD_XUPT_SHAPE后，点剪裁器启动使能信号，然后进行点剪裁，只需要简单判断点是否在单位立方体内，可以直接输出或不输出。

接收到CMD_XUPT_SHAPE后，线剪裁器启动使能信号，然后进行线的剪裁，采用Cohen_Sutherland算法，它已经在软件平台中得到验证。一般地，对于一条线，它裁剪后可能没有输出，输出一个点或一条线段。

接收到CMD_XUPT_SHAPE后，三角形剪裁器启动使能信号，然后进行三角形的剪裁，采用S-H算法计算交点，采用改进算法计算交点的属性。一般地，三角形裁剪后情况比较复杂，根据输出顶点的数目，对它进行判断:若是多边形，要把它装配成几个三角形后依次输出。或者没有输出，或者输出一条线段。对于如点、线和三角形3种图元，剪裁完毕后要将输出数据保存在寄存器R中，然根据剪裁结果重新编码后输出，如图2所示。顶层模块的接口信号，说明如表1所示。

图2 三维剪裁的数据通路

表1 总体接口信号说明

2.2 设三维剪裁的状态机实现

三维剪裁的实现采用数据驱动数据流的处理方式。三维裁剪模块通过一个状态机控制，并用握手信号与上下级进行通信。裁剪所要处理的对象是点、线和三角形，对每个图元操作结束后，插值计算顶点属性值，然后根据节点数目重新装配，再传送到下一级，如图3所示。

图3 三维剪裁的状态机实现

3 FPGA仿验证平台与仿真结果

3.1 验证平台的架构

搭建的验证平台输入激励用于产生待测数据，已经预先指定了测试功能点的命令顺序;对于数据位值的产生，激励产生器则采用给定确定值的方法来实现;Design Under Verification(DUV)是文中设计的硬件电路;其中参考模型是本文设计的行为模型，用于和DUV进行比较;输出响应为DUV运行的结果比较，用于比较参考模型和DUV运行的结果［7］，如图4所示。

图4 验证平台的结构框图

验证平台采用自动比较机制，由输入激励单元为DUV和参考模型提供相同的测试激励，比较DUV和参考模型运行的结果是否一致。若不一致，则报错，及时停止仿真;否则，说明DUV设计与参考模型完成的功能一致，从而进一步验证DUV功能的正确性。

3.2 仿真结果

针对三维剪裁器处理的3种图元，功能仿真按照点、线和三角形的顺序给出波形图，逐个分析其处理过程及其处理结果，最终，给出顶层模块的功能仿真:使用Mentor公司的QuestaSim 6.5工具，按照点、线和三角形的顺序逐一分析其处理过程，结合图形流水线其他各部分的RTL级实现将处理结果通过Java 1.6环境下的JFrame窗体显示，如图5所示。

图5 JFrame窗体显示的仿真结果

图5中视景体是规范视景体，激励输入:点(1.01，1.00，0.00，2.00)判断其在视景体里输出点;第一条线(2.2，1.0，1.0，3.5)，(2.2，6.0，1.0，3.5)被裁了 1/2，第二条线(5.6，1.0，1.0，8.0)，(7.2，1.0，1.0，8.0)在实景体里;三角形(9.2，3.0，1.0，3.5)，(9.9，3.0，1.0，3.5)，(9.5，5.0，1.0，3.5)，被裁剪为四边形。仿真证实硬件电路能够正确实现规范视景体对点、线和三角形的裁剪功能。

仿真结果如图6所示，当使能信号enP为高时，激励输入了一个点(0.5，0.2，0.0)以及它的颜色和法向量，因为它在单位立方体内，所以经过点裁剪后，将这个点的所有属性值输出，输出完毕后Pfinished置高。否则，如输入一个点(1.0，1.2，2.5)，因为它在立方体外面，所以最后没有输出，此时Pfinished也置高，状态返回初始状态INIT。

图6 点的剪裁

如图7所示，当使能信号enL为高时，激励输入了一条线段的两个端点(1.5，2.0，2.0)和(0.0，0.0，0.0)，它们的颜色值分别是(1.0，0.0，0.0)和(0.0，1.0，0.0)，经过线裁剪后，最终的线段被裁减为(0.75，1.0，1.0)和(0.0，0.0，0.0)的一条线段，他们的颜色值为(0.5，0.5，0.0)和(0.0，1.0，0.0)。

图7 线的剪裁

如图8所示，当使能信号enT为高时，激励输入了一个三角形的3个顶点坐标及颜色和法向量等，输入坐标分别为v0(-0.5，0.0)、v1(0.5，0.0)和v2(0.0，1.5)。经单位立方体剪裁后，原来的三角形变成了一个四边形，它的坐标分表为v0(-0.16667，1.0)、v1(-0.5，0.0)、v2(0.5，0.0)和v3(1.0，0.16667)，颜色经插值计算后是(0.333，0.0，0.667)，(1.0，0.0，0.0)，(0.0，1.0，0.0)，(0.0，0.333，0.667)，然后对这个四边形进行再装配，将其装配成两个三角形v0v1v2和v0v2v3，从图中可以看出输出两组三角形，共18个值。