MetalでTessellation

# Tessellationとは
Tessellation（テッセレーション）は3Dの描画手法の一つで、一言で言うとGPUで動的にポリゴンを分割する機能のことです。

例えば三角形のポリゴンにTessellationを適用すると、こういった感じになります。

![適用前](https://qiita-image-store.s3.amazonaws.com/0/230873/0c778a96-fdbd-a10a-dd7a-f2541498dbfc.png "適用前")

↓↓↓　Tessellationを適用　↓↓↓

![適用後](https://qiita-image-store.s3.amazonaws.com/0/230873/cb2df519-c5ad-47d2-272a-cc3d8ce1fded.png "適用後")


適用前の三角形は頂点が3つだけでしたが、適用後は頂点が4つ増えて合計7つになっています。それに合わせて中の三角形（ポリゴン）が1つから6つへ分割されています。

この様にTessellationは単にポリゴンを分割するという単純な機能ですが、高品質な描画を効率良く実現するのに役立つ機能です。

## Tessellationのメリット
基本的に言って3Dモデルを描画する場合、ポリゴン数が多ければ多いほどより詳細で滑らかな描画となります。しかし、モデルのポリゴン数が増えると、当然ながら処理するデータ量が増え描画負荷が上がってしまいます。

そこでTessellationの出番となります。Tessellationには描画負荷を抑えつつポリゴン数を増やせるというメリットがあります。

### GPUで処理を行う
Tessellationでは、CPU側は少ないポリゴン数のモデルを使いGPU側でポリゴンを分割して詳細なモデルを生成します。これにより、CPUからGPUへのポリゴンデータの転送量（メモリの帯域幅）を抑えることができます。
また、分割後のポリゴンデータはGPUのメモリに格納されないので、GPUのメモリの使用量も減らすことができます。

例えば10万ポリゴン相当のモデルを描画したい場合、10分割のTessellationを使えばCPU側で必要なのは1万ポリゴンです。つまり、Tessellationを使わなかった場合と比べて、消費するメモリ量は1/10になります。

ただしデメリットとして、当然ながらGPUには分割処理という負荷が毎フレームかかる様になります。

### 動的にポリゴンを分割する
Tessellationでは、ポリゴンを何分割するかをプログラマブルに変更できます。

ポリゴン数を増やすとディテールは向上するとはいえ、モデルが遠くにあればあるほどポリゴン数を増やしても見た目は変わらなくなります。もし、描画対象のモデルに対して一律でポリゴン数を増やしてしまうと、遠くのモデルの増やしたポリゴン数は描画負荷を上げるだけの無駄になってしまいます。それで、ディテールを求められる近くのモデルはポリゴン数を増やし遠くのモデルは必要最低限のポリゴン数で描画するということができれば、描画品質を保ちつつ描画負荷を抑えることができます。

その点、Tessellationは動的にポリゴンの分割数を変更できるので、モデルの遠近に応じてポリゴン数を調整すると言ったことも容易です。

# Metalで利用する
## 対応状況
Metalでは、iOS10とmacOS10.12(Sierra)からTessellationをサポートしています。
*（iOS_GPUFamily3_v2 / OSX_GPUFamily1_v2からサポート）*

ただし、iOSはA9以降のチップを搭載しているデバイス（iPhone6S / SE以降）が必要です。macはOSのバージョンを満たしていれば、どの機種でも動作します。


## 描画の流れ
MetalでTessellationを使わずに描画する場合は、

1. VertexShaderで頂点データを処理
2. Rasterizer（固定機能）で変換処理
3. FragmentShaderでピクセルデータを処理

という3段階です。

Tessellationを利用して描画する場合は、以下の様に5段階になります。

![描画の流れ](https://qiita-image-store.s3.amazonaws.com/0/230873/1fc476c1-c5f8-85b1-c2ba-f35d4ca191a5.png "描画の流れ")

Tessellationを使わない場合との違いは、

- Tessellation KernelとTessellatorが増えている
- VertexShaderがPost-TessellationVertexShaderに変わっている
- 頂点データがパッチデータになっている

という点です。処理の流れは、

1. Tessellation KernelでTessellation Factorsを設定  
2. Tessellator（固定機能）で指定されたTessellation Factorsに基づきポリゴンを分割
3. Post-TessellationVertexShaderで分割された頂点を処理
4. Rasterizer（固定機能）で変換処理
5. FragmentShaderでピクセルデータを処理

となります。

元の流れと比べると1と2のポリゴンを分割する段階が増えただけのシンプルな構成になっています。

## 実装
前述の5段階のうち、プログラマ側で実装が必要なのは、1と３と５の部分です。
5は通常の描画時と変わらないので、1と3の特にTessellation固有の実装を説明します。

以降の説明は必要な箇所を抜粋しているので、ソース全体は[Gist](https://gist.github.com/mike-neko/2ecd87c48e9eb82e095eb4f9620717a0)を参照してください。
コードはXcode 9.2で動作確認をしています。

### Tessellation KernelでTessellation Factorsを設定
Tessellation Factorsは、ポリゴンを何分割するかやどの様に分割するかの設定です。
パッチデータが三角形の場合は、`MTLTriangleTessellationFactorsHalf`という構造体を使います。

```c++
typedef struct {
    uint16_t edgeTessellationFactor[3];
    uint16_t insideTessellationFactor;
} MTLTriangleTessellationFactorsHalf;

```

`edgeTessellationFactor`は三角形の各辺を何分割するか、`insideTessellationFactor`はどの様に分割するかを指定します。

注意点としては、この構造体のパラメータはそれぞれ`Uint16`が指定されていますが、実際の型は`half`（16bitの浮動小数点数）であるという点です。SwiftやObjCでは`half`が直接サポートされていない為こういった定義となっています。また、設定にはCompute Kernel(ComputeShader)を使います。

最初に`MTLTriangleTessellationFactorsHalf`を格納する為の`MTLBuffer`を確保します。

```swift
// tessellationFactorBuffer: MTLBuffer
tessellationFactorBuffer = device.makeBuffer(length: MemoryLayout<MTLTriangleTessellationFactorsHalf>.size,
                                             options: .storageModePrivate)
```

また、`Compute Kernel`の初期化処理も行います。

```swift
// commandQueue: MTLCommandQueue
// computePipeline: MTLComputePipelineState
let device = MTLCreateSystemDefaultDevice()!
commandQueue = device.makeCommandQueue()!
let library = device.makeDefaultLibrary()!
let kernel = library.makeFunction(name: "tessellationFactorsCompute")!
computePipeline = try! device.makeComputePipelineState(function: kernel)
```

次に、`MTLTriangleTessellationFactorsHalf`へ値を設定するCompute Kernelを実行します。

```swift
let commandBuffer = commandQueue.makeCommandBuffer()!
let computeCommandEncoder = commandBuffer.makeComputeCommandEncoder()!
computeCommandEncoder.setComputePipelineState(computePipeline)

var factor = float2(edgeFactor, insideFactor)
withUnsafePointer(to: &factor) {
    computeCommandEncoder.setBytes($0, length: MemoryLayout<float2>.size, index: 0)
}
computeCommandEncoder.setBuffer(tessellationFactorBuffer, offset: 0, index: 1)

computeCommandEncoder.dispatchThreadgroups(MTLSize(width: 1, height: 1, depth: 1),
                                           threadsPerThreadgroup: MTLSize(width: 1, height: 1, depth: 1))
computeCommandEncoder.endEncoding()
```

ポイントは`edgeFactor`と`insideFactor`に`MTLTriangleTessellationFactorsHalf`の`edgeTessellationFactor`と`insideTessellationFactor`に設定したい値を**Float**で設定するところです（ただし精度は16bitに切り捨てられます）。なお、0やNanが設定されると、描画されなくなるので注意が必要です。

シェーダ側の実装は以下の様に渡されてきた値を`MTLTriangleTessellationFactorsHalf`に設定しているだけです。

```c++:shader.metal
kernel void tessellationFactorsCompute(constant float2& factor [[ buffer(0) ]],
                                       device MTLTriangleTessellationFactorsHalf* factors [[ buffer(1) ]]) {
    factors[0].edgeTessellationFactor[0] = factor.x;
    factors[0].edgeTessellationFactor[1] = factor.x;
    factors[0].edgeTessellationFactor[2] = factor.x;
    factors[0].insideTessellationFactor = factor.y;
}
```

最後に、描画時に

```swift
// renderEncoder: MTLRenderCommandEncoder
renderEncoder.setTessellationFactorBuffer(tessellationFactorBuffer, offset: 0, instanceStride: 0)
```

としてTessellatorにTessellation Factorsを設定します。

なお、この処理は設定値に変更がなければ、毎フレーム実行する必要はありません。また、Compute Kernelを使わずに他の方法で設定することもできます。（実際には`half`を扱うのが面倒なのと、処理効率の観点からCompute Kernelを使う方が良いと思われます）

### Post-TessellationVertexShaderで頂点を処理する

Tessellationでは、頂点データの代わりにパッチデータという単位で描画します。パッチデータは三角形と四角形の2種類あり、制御点と呼ばれる各頂点の情報を持っています。それぞれの定義はシェーダ側で行います。

```c++:shader.metal
// Control-Point Data
struct ControlPoint {
    float4 position [[ attribute(0) ]];
};

// Patch Data
struct PatchIn {
    patch_control_point<ControlPoint> controlPoints;
};
```

`ControlPoint`はTessellationを使わない場合の頂点データと同等です。今回は`position`（位置情報）のみを定義していますが、必要に応じてテクスチャ座標や法線を追加します。

`PatchIn`はPost-TessellationVertexShaderへ渡されるパッチデータの定義です。`patch_control_point`は必須のパラメータで、genericで制御点として使う型（今回は`ControlPoint`）を指定します。この中には後述の修飾子で指定された数だけ制御点が格納されます。また、オプションとしてパッチデータ毎に必要な情報を追加できます。

このパッチデータを受け取るPost-TessellationVertexShaderの実装は以下になります。

```c++:shader.metal
[[ patch(triangle, 3) ]]
vertex VertexOut tessellationTriangleVertex(PatchIn patchIn [[ stage_in ]],
                                            float3 patchCoord [[ position_in_patch ]]) {
    auto u = patchCoord[0];
    auto v = patchCoord[1];
    auto w = patchCoord[2];
    auto position = u * patchIn.controlPoints[0].position
                  + v * patchIn.controlPoints[1].position
                  + w * patchIn.controlPoints[2].position;
    
    VertexOut out;
    out.position = float4(position);
    out.position.w = 1;
    return out;
}
```

関数の定義の前にある修飾子`[[ patch(triangle, 3) ]]`は、パッチのタイプ（三角形 or 四角形）と制御点の数を指定しています。

Post-TessellationVertexShaderの場合、`[[ stage_in ]]`にはパッチデータが渡されます。`[[ 
position_in_patch ]]`には、パッチ上での分割後の頂点の位置が渡されます。これはパッチが三角形の場合は`float3`のデータ型となります。

分割後の頂点座標は、この`patchIn`と`patchCoord`から計算する必要があります。先ほどのシェーダのコードの以下が該当部分です。

```c++
auto u = patchCoord[0];
auto v = patchCoord[1];
auto w = patchCoord[2];
auto position = u * patchIn.controlPoints[0].position
              + v * patchIn.controlPoints[1].position
              + w * patchIn.controlPoints[2].position;
```

`patchCoord`には三角形の各制御点に対応する位置が入っており、`patchIn`の`controlPoints`には制御点の情報が三角形なので3つ入っています。それぞれの制御点は対応しているので、パッチ上の位置とパッチデータの位置情報を掛け合わせることで、分割後の座標`position`を計算できます。Tessellationの場合は、ここまでしてようやく通常のVertexShaderが受け取る頂点座標と同じ座標を取得できます。

あとのシェーダ側の処理は通常のシェーダと同じです。
（サンプルは単純に座標を出力しているだけです）

### パッチの描画処理

#### MTLVertexDescriptorの設定
```swift
let vertexDescriptor = MTLVertexDescriptor()
vertexDescriptor.attributes[0].format = .float4
vertexDescriptor.attributes[0].offset = 0
vertexDescriptor.attributes[0].bufferIndex = 0
vertexDescriptor.layouts[0].stride = MemoryLayout<float4>.stride
vertexDescriptor.layouts[0].stepFunction = .perPatchControlPoint
```

Tessellationとして必要な設定は、最後の行の`.perPatchControlPoint`の部分です。それ以外は通常の設定と変わりません。

#### MTLRenderPipelineDescriptorの設定

設定項目が多いので、Tessellationに関係する部分だけを抜き出します。

```swift
let renderDescriptor = MTLRenderPipelineDescriptor()
// 省略
renderDescriptor.isTessellationFactorScaleEnabled = false
renderDescriptor.tessellationFactorFormat = .half
renderDescriptor.tessellationControlPointIndexType = .none
renderDescriptor.tessellationFactorStepFunction = .constant
renderDescriptor.tessellationOutputWindingOrder = .clockwise
renderDescriptor.tessellationPartitionMode = .fractionalEven
renderDescriptor.maxTessellationFactor = 16
```

各項目の設定値の詳細はリファレンスを参照して頂くとして、通常は上記の設定になるかと思います。
なお、`maxTessellationFactor`は最大分割数の設定ですが、iOSは16まで、macOSは64までとなっています。

#### パッチデータを準備する

パッチが三角形の場合、1つのパッチには制御点が3つあるので、パッチを1つ描画すると三角形のポリゴンが1つ描画されます。今回シェーダで指定した様に、制御点1つは`float4`の位置情報を持っているので、三角形のポリゴンを1つを描画する場合のデータは次の様になります。

```swift
let positions = [
    float4(arrayLiteral: -0.8, -0.8, 0.0, 1.0),
    float4(arrayLiteral:  0.0,  0.8, 0.0, 1.0),
    float4(arrayLiteral:  0.8, -0.8, 0.0, 1.0),
]
```

制御点のデータを準備したら、それをシェーダに渡す為に`MTLBuffer`へセットします。

```swift
// controlPointsBuffer: MTLBuffer
controlPointsBuffer = positions.withUnsafeBufferPointer {
    device.makeBuffer(bytes: $0.baseAddress!,
                      length: positions.count * MemoryLayout<float4>.size,
                      options: .storageModeShared)
}
```

描画時には、

```swift
// renderEncoder: MTLRenderCommandEncoder
renderEncoder.setVertexBuffer(controlPointsBuffer, offset: 0, index: 0)
```

として、通常の頂点データと同じ様にシェーダへ渡します。

#### パッチを描画する

通常の描画は`drawPrimitives`を使いますが、Tessellationでは`drawPatches`を使います。

```swift
// renderEncoder: MTLRenderCommandEncoder
renderEncoder.drawPatches(numberOfPatchControlPoints: 3,
                          patchStart: 0, patchCount: 1,
                          patchIndexBuffer: nil, 
                          patchIndexBufferOffset: 0, 
                          instanceCount: 1, baseInstance: 0)
```

インデックスバッファを使わずにシンプルにパッチを描画する場合は上記の様なパラメータとなります。ポイントとなる引数は以下の2つです。

- `numberOfPatchControlPoints`: 1つのパッチに含まれる制御点の数  
   シェーダの`[[ patch(triangle, 3) ]]`の箇所で指定した数と同じ
- `patchCount`: 描画するパッチの数

これでTessellationが適用できる三角形のポリゴンが一つ描画されます。

## DirectXとの違い

基本的な描画の流れ（パイプライン）は、DirectXもMetalも違いはありません。
（DirectXとOpenGLの主な違いはシェーダの名称部分なのでOpenGLについては省略します）

DirectXのTessellationは、
VertexShader → HullShader → Tessellator → DomainShader
という流れですが、各シェーダは以下の様にMetalと対応しています。

| DirectX | Metal |
|:-:|:-:|
| VertexShader + HullShader | Tessellation Kernel |
| Tessellator | （同一） |
| DomainShader | Post-TessellationVertexShader |

はっきりと違うのは、DirectXでは全てが描画パイプラインのシェーダ上で行われるのに対し、MetalではTessellation Kernel部分はComputeShader（GPGPU）上で行われる点です。これにより、描画パイプラインとは非同期で実行できたり、スレッド間（パッチ同士）で高速なメモリの共有ができたりします。
（WWDCのセッションではパフォーマンス重視で再設計された作りとのことでしたが、実際にどれくらい向上するのかは？です）

# まとめ

今回はTessellationの基礎部分についてまとめてみました。実際には、PhongTessellationやAdaptiveTessellation、ディスプレイスメントマップなどの形で応用して使うことになると思います。

かなり長くなってしまったので面倒な印象を受けますが、元々、Metalのコードの分量が多い（低レベルグラフィックAPIの宿命）のが原因で、実際のMetalのTessellation部分はシンプルな作りになっていると思います。
（個人的には、DirectXなどよりもこっちの方が好みです。最初は慣れずに戸惑いましたが・・・）

興味を持たれた方は、ちょっとソースが古いですが、こちらの[デモプロジェクト](https://github.com/mike-neko/MetalTessellation)も試してみてください。Xcode8.2以降で動作します。