适用图形硬件的分格化算法与设计实现

The Algorithm and Design for Hardware Tessellator

曲面离散就是把一个曲面进行分格化,以产生一系列简单凸多边形的技术.分格化是曲面离散中的一个重要步骤,也是Direct3D11标准中的一个重要组成部分.针对分格化功能的硬件实现,提出一种对四边形和三角形面片的分格化处理优化算法,分为面片的内部区域、边界区域处理以及参数坐标生成3个部分.面片的内部区域处理通过对粗略分块和精细划分的配置达到计算量的平衡;面片边界区域处理实现内部和外部边界节点编号的交替增长;参数坐标生成模块将面片节点编号转换为该点所在域的参数坐标.该算法采用了定点数的加法和比较操作来实现,仅在初始化时才需要少量的乘除法操作;并采用时间和空间并行的体系结构进行了硬件设计.最后,通过仿真验证了算法的正确性以及所提出设计的高效性.

Surface tessellation is a technique that subdivides a patch of surface into convex polygons, which can be rendered using standard graphic routines. Tessellator is an important part of tessellation. It is also one stage of Direct3D 11 pipeline. This paper presents a novel and optimal algorithm for hardware tessellator, which can tessellate a quad or triangular primitive patch. The algorithm consists of inner subdivision, outer band subdivision and parametric coordinate generation. The inner subdivision can be configured to balance the computation quantity between block partitions and mesh subdivision. The outer band subdivision can realize alternate increment of node index on inner and outer edges. Parametric coordinate generation can translate node index into corresponding parametric coordinate in its domain. The algorithm can be implemented by fixed point addition and comparison operations. Multiplication and division are used only in the initialization of the algorithm. The paper also proposes a hardware implementation of the tessellator, which employs a fully pipelined and parallel architecture. The results of simulation validate the algorithm and show high performance of the design.