Tessellation Related

接下来介绍D3D11中引入的Tessellation功能，这是一个不可编程的管线Stage。不像GS的概念比较简单，只增加了一个Primitive的Shader，Tessellation的概念会相对复杂一些。

Tessellation的作用

Tessellation的中文翻译是曲面细分，其作用是将一个低面数的模型转化为一个高面数的模型，配合上一些其他的数据，在输入的低模mesh下得到高精度的建模效果，采用这种方案的好处是：

节省高精度模型占用与渲染消耗的内存与带宽
可以根据硬件设备实现可控的性能伸缩
可以实现更为可控的动态LOD效果

除此之外，在效果层面，也可以得到更为丰富的细节。

关于geometry tessellate的方式就有很多种，比如：

有多种不同的实现方式的Spline Patches方法
多种类型的Subdivision Surface方法
Displacement Mapping方法。

因此仅仅从Tessellation这个单词上，我们完全看不出GPU底层使用的具体方法，不过这个倒是不用过于深究。

为了描述tessellation的具体实现方式，后面会介绍到新的shader类型（对于D3D而言，这些shader类型为Hull Shader以及Domain Shader，而对于OpenGL 4.0而言，这些shader类型为Tessellation Control Shader以及Tessellation Evaluation Shader）。

基本介绍

这是[3]中对Tessellation在管线中的位置以及各个环节具体功能的描述。

上图是从[2]中引用的图片，与之相对应的，还有关于这张图片的解说：

结合上面两张图，这里做一个总结，整个Tessellation分为三个阶段：

Hull Shader（HS）：负责曲面细分前的准备工作，逐control point执行，多个control point的执行彼此之间是独立的，目的是输出曲面细分的相关计算参数如tessellation factor
Tessellator（TS）：曲面细分的主体部分，负责完成primitive的新增
Domain Shader（DS）：负责对新增的primitve执行对应的变换与计算逻辑，可以看成是tessellation版本的VS

1. Hull Shader

Hull shader阶段又可以分成两个独立的阶段，它们是并行执行的：

Control point处理阶段
Patch常量阶段

Control point处理阶段是per control points执行的, 这个阶段会对patch中的每个控制点进行处理，并输出对应的控制点。

所谓patch，简单理解就是带控制点的体元，比如一个三角形，它的三个顶点是控制点，那么这个三角形就是具有3个控制点的patch。
在Hull shader中，我们还可以对输入的控制点进行转化操作，生成新的控制点，比如输入的3个控制点，输出6个控制点。注意：输入或者输出的控制点数量是1~32。

Patch常量阶段中，HullShader会调用一个const data函数，这个函数主要用于计算得到tessellation factor，这些factor决定在TS阶段如何细分当前的patch。

HS的输入输出通常可以参考如下格式：

// HS的输入控制点信息
struct HullInputType
{
float3 position : POSITION;
float4 color : COLOR;
};

// 常量阶段输出的边与内部的Tessellation Factor信息，这些信息接下来会传给TS完成后续工作
struct ConstantOutputType
{
float edges[3] : SV_TessFactor;
float inside : SV_InsideTessFactor;
};

// HS输出的控制点信息，数目跟输入的控制点可以不同
struct HullOutputType
{
float3 position : POSITION;
float4 color : COLOR;
};

另外，在Hullshader阶段还会指定一些TS阶段使用的Tessellation模式，比如：

细分的patch是三角形(拓扑模式)还是四边形（quad）
partition mode(选择什么细分算法)是HS_PARTITION还是其他模式等

Tessellation主要两种类型的patch：

基于quad的patch
基于triangle的patch。

quad patch是使用两个正交坐标轴变量（用uv表示）定义的一个参数域，在这个参数域上可以构造成两个单参数基函数（one-parameter basis function)的张量积。

triangle batch则是使用三个坐标（uvw）的向量的质心坐标来表示（如 $u, v, w \ge 0, u + v + w = 1$ ）的。

D3D11中，上述两种patch对应的术语为quad/tri domains。

除这两种常用的之外，还有isoline domain（等值线），这种domain表示的不是二维表面，而是一条或者多条一维曲线。

2. TS阶段

Tessellator是一个固定管线阶段，它的主要功能就是完成一个domain(三角形，四边形或线)的细分，从而得到更多的primitve。

Tessellator是per patch操作的，Hull shader阶段传入的Tess Factor决定细分多少次，而Hull shader阶段传入的partitioning则决定选用何种细分算法。Tessellator输出为u,v, {w}坐标以及细分后domain的拓扑信息。

在细分时，tessellator会在一个归一化的坐标系统中处理patch，比如输入是一个quad(四边形),但这个quad先要映射到一个单位为1的正方形上，然后tessellator会对这个正方形进行细分操作。对于triangle patch，这里就用等边三角形来表示，相关的标记如下面两图表示：

不论是正方形还是等边三角形，都有一种我们这里认为非常自然的tessellated方式，如下图所示，但是这里的结果跟实际运行的结果可能有一些差异：

这里是实际运行结果的表现:

可以看到，quad之间的差异比较小，但是triangle的表现则存在很大的差别。后面会仔细分析其中的原因，其实从实际tessellated的三角形的形状来看，应该是出于不同tessellated level之间的平滑过渡的考虑。

3. DS阶段

Domain Shader 阶段会根据TS阶段生成的u,v , {w}坐标以及HS阶段传入的控制点在patch中生成细分后顶点的位置（可以理解为针对细分后的点调用的VS，针对displacement map的采样计算就发生在这个阶段）。

Domain shader是per vertex的，对于TS中每个细分产生的顶点，它都要调用一次。它的输入参数除了u,v,{w}坐标及控制点以外，还有const data,比如Tess factor等。

Shder代码给出如下：

// HS输出的细分因子参数
struct ConstantOutputType
{
float edges[3] : SV_TessFactor;
float inside : SV_InsideTessFactor;
};

// HS输出的控制点参数
struct HullOutputType
{
float3 position : POSITION;
float4 color : COLOR;
};

// DS输出的计算结果
struct PixelInputType
{
float4 position : SV_POSITION;
float4 color : COLOR;
};

patch细分策略

如前所述，之所以会出现实际细分结果跟我们预测结果不一致的原因，是因为需要保持两个patch之间的平滑过渡。

如果只考虑一个三角形的tessellation的话很简单，使用哪种方式都可以，但是由于我们在实际使用中会需要考虑性价比，比如只在那些真正需要的地方才进行高强度的tessellation，其他地方维持不变，这就会导致相邻patch之间的衔接问题，而且我们希望做到一次性处理完成，不要再在后面通过补丁算法进行修正。

这里的做法就是硬件只针对当前patch做tessellation，不考虑相邻patch之间的吻合情况，而相邻patch在共享边上的一致性由shader来保证。因此在Domain Shader中需要十分注意相邻patch的衔接逻辑（参考文章）。

代码实施细节这里就不说了，直接介绍一下基本的原理吧。每个patch都有多个tessellation因子，这些因子都是在Hull Shader中计算的，比如在patch内部的因子可能是1或者2，而在edge上的因子可能需要在这个基础上+1。内部的因子可以根据自己的需要进行选取，而edge上的因子则需要考虑相邻patch在同一条edge上的因子以避免产生裂缝。如果shader处理的不好，那么硬件是不会进行修补的（出于执行效率的考虑），会完全按照shader的指令生成对应的结果。

为了达到无裂缝的结果，就需要设定一些参考的patch，为了方便说明，这次我们在每条边上设定不同的tessellation因子：

这里用颜色标出了各条边所影响的区域，其中白色的区域表示的是内部的不受edge影响的区域。各条边上的因子为（与这条边上的顶点数一致）：

u = 0 : 2 (yellow)

u = 1 : 4 (pink)

v = 0 : 3 (green)

v = 1 : 5 (cyan)

内部因子则相对简单，u方向上是3，v方向上是4（为什么不是4跟5？）。对于quad而言，tessellated后的mesh内部实际上是一个规整的grid，除了一头一尾的两行两列需要考虑相邻triangle之间的衔接。（如果某条边的因子为1，那么输出的mesh将（跟什么？）具有一样的结构，看起来就像是内部的uv因子都是2一样）。三角形的情况要复杂一点，奇数因子（怎么判断是否是奇数？）我们已经看到过了，对于因子为N的三角形，最终输出的mesh会包含 $\frac{N+1}{2}$ 个同心环，最内层对应的就是一个三角形（如上图所示）。对于偶数因子而言，我们输出的结果会包含 $\frac{N}{2}$ 个同心环，最中间的位置是一个单一的顶点，下面给出的是最简单的 $N = 2$ 的情况的结果。

最后，在对quads进行三角化的时候，quad上面的对角线永远都是按照从patch中心朝外指的方式设定（即都需要通过patch中心），这么做是为了保证旋转对称性，这样如果还有其他的自由度（extra degree of freedom）的话，还可以利用这一点来添加约束。

虽然有了上述的一些执行策略，在实际工作中，依然有可能导致相关的裂缝问题：

因为浮点精度问题，导致相邻控制点的位置存在偏差
因为双线性采样结果不连续导致DS执行之后得到的结果不一致而产生裂缝
叉乘计算结果由于不能交换而导致法线结果不连续

Fractional tessellation factors and overall pipeline flow

到目前为止，我们只讨论了整数因子的tessellation结果。在Integer以及Pow2划分方案中，tessellator只会接收到整数因子。但是如果shader生成了一个非整数的因子（或者非Pow2的因子），就会简单粗暴的通过四舍五入的方式归类到下一个可接受的因子数值上。除了这两类划分方案之外，剩下的两类划分方案为Fractional-odd以及Fractional-eve。跟前面两类划分方案中因子是离散的（可能会导致效果跳变）不同，这两种划分方案中新增顶点的起始位置为已有顶点的位置，之后根据因子的增加才逐渐的移动到下一个新的位置，整个过程是连续的。

tessellator的输出包含两块内容：

tessellated顶点在domain坐标系中的位置
连接信息，通常用index buffer表示

在有了固定函数的tessellator单元之后，我们下面来看下我们需要做些什么才能实现primitive的快速输出：

我们需要将由多个控制点组成的patch数据输入到Hull Shader中
Hull Shader会据此计算出输出的控制点位置，一些patch常量（这两个数据都会传递到后面的domain shader中），以及所有的tessellation因子。
运行固定函数的tessellator，输出一系列的Domain Position（用于运行Domain Shader），以及前面提到的index buffer
运行Domain Shader
进行新一轮的PA处理，并将组装好的primitive数据传递到后面的GS管线或者Viewporttransform，Clip & Cull阶段。

下面先来看下Hull Shader。

Hull Shader execution

跟Geometry Shaders一样，Hull Shader也是以完整的primitive作为输入的，因此会遇到因此而导致的所有input buffering的问题。而这些问题的严重程度则取决于patch的类型。如果我们使用的是类似cubic bezier之类的patch的话，那么每个patch我们就需要使用4x4=16个points作为输入，而输出则可能仅有一个quad（或者如果被cull掉的话，就一个也没有），这种情况很尴尬，shading效率也比较低。而另一方面，如果我们使用的是triangle patch的话，input buffering就会表现的十分驯服，不太可能会成为瓶颈。

更重要的是，HS的执行频率不像GS那么高，GS是每个primitive执行一次，而HS则是每个patch（包含多个primitive）执行一次，且只有那些需要执行tessellation'的patch才需要执行HS。换句话说，即使HS的输入数据是低效的，其表现也会比GS要好得多。

HS相对于GS的另一项优势则在于，其输出的数据尺寸是固定的。输出数据中包含了固定数目的控制点，每个控制点包含固定的属性数据以及固定数目的patch常量。所有这些输出数据是在编译的时候就已经知道了的。如果我们同时进行16个hull的shade操作，我们会明确的知道每个hull shader的输出的具体位置。虽然对于大部分的GS而言，我们是能够静态的知道其输出的顶点的数目（比如如果所有导致的控制流指令都能够被静态评估的话），对于这些情况而言，将可以保证每个GS输出的最大的顶点数目，但是依然需要额外的分析。对于HS而言，我们是可以明确的知道每个HS输出的数据的位置的，不需要任何的额外分析处理。简而言之，在HS上我们可以直接对输出buffer进行管理，除了一点，考虑到不同的primitive类型，我们可能需要大量的输出buffer空间，这个可能会限制HS并行执行的数量。

最后，HS在D3D11中的编译方式也很特别。所有的其他shader类型看起来就像是一大块代码（其中可能会包含一些subroutines），而HS则会被展开成多个phase，每个phase则是由多个独立的线程组成。其中的细节我们这里就不展开了，只需要知道基本上所有的HS其实都是按照某个程度并行结构组织起来的。看起来微软是被GS搞怕了。

总而言之，HS会为每个patch生成一片输出数据，大部分的数据会一直传输下去直到Domain Shader执行为止，除了Tessellate因子只会传输到tessellator unit。如果Tessellate因子是小于等于0或者等于NaN的话，这个patch就会被认为是无效的，会被直接cull掉，相应的控制点数据以及patch常量数据则会被悄无声息的移除。否则tessellator unit就会开始接管，读取shaded过的patch数据并开始生产domain point position以及triangle index数据，之后就准备进入DS执行。

Domain Shaders

跟 Vertex Shading 一样，我们需要将多个domain顶点数据整合成一个batch，并进行统一的shading处理，之后传递给PA。固定函数tessellator会完成这个工作。

从输入输出来看，DS是非常简单的：其唯一需要的可变的输入是domain point的uv坐标（在有些时候可能还会有第三维w，不过不需要从其他地方传入：u+v+w=1）。其他的数据要么是patch常量，控制点（对于一个patch而言，这些数据是恒定的），要么是常量buffer。DS的输出则跟VS的输出一样。

简而言之，由于DS与VS的相似性极高，因此D3D11的tessellation管线比GS管线的执行效率要高得多，同时用于buffering的内存大小也比GS的要低，shader units的利用效率也更高。

Final remarks

Tessellator的实现带有某种程度上的对称性以及精度要求；对于顶点domain positions，可以确认不同厂家的输出结果肯定是相同的，因为D3D11在这个上面做了限制，而D3D11没有刻意限制的内容则是顶点或者triangle输出的顺序，不过各个厂家需要保证其执行的过程是稳定的可重复的（即同样的输入刻意得到同样的输出）。除此之外还有很多比较细微的约束，比如tessellator输出的所有的domain positions都需要使用浮点数来表示uv；还有一系列类似的条件用以保证Domain shader输出的结果是无缝隙的（这条规则非常重要，因为如果不满足的话，会导致某条被两个patch所共享的边AB上存在衔接问题）。

DS的编写要十分的谨慎，做的不好就可能导致edge上的裂缝。另外，tessellator输出的triangle的绕行顺序是由app决定的，可以支持CCW以及CW。

最后，因为tessellation管线是可以继续传递给GS的，因此这里有个问题是是否可以在tessellation中生成邻接信息。对于patch的内部而言，这个看起来是可行的（只需要tessellator unit生成更多的索引数据就可以了），但是一旦讨论到edge上的问题，这个情况就会变得很糟糕。因为跨patch的邻接信息需要知道全局mesh的相关信息，而这是tessellation阶段所极力避免的，因此简而言之，这个问题的答案是不行，tessellator不能也不应该为GS生成邻接信息。