Metal で 三角形を組み合わせて 2D の線を描く

# これまでの流れ

これまで、次の記事で UIScrollView と Metal の組み合わせで、２Ｄアプリの可能性を探ってきました。

#### Metal ＋ UIScrollView でズーム＆スクロール可能な２Dアプリに挑戦

http://qiita.com/codelynx/items/8c631e51d107ef71a44b

#### Metal ＋ UIScrollView でズーム＆スクロール可能な２Dアプリに挑戦 TAKE 2

http://qiita.com/codelynx/items/0434cdf453c8db6bc357

今回はこのシリーズの第3回で、２Ｄアプリの代表的な用途として、キャンバスや紙の上にペンなどを走らせるように、Metal を使って２Ｄの線を描く事に挑戦してみたいと思います。

# Metal の 2Dの線を描く

Metal で２Ｄの線を描くことは、簡単に思うかもしれませんが意外と大変です。Line Shader があるじゃないかとう人もいるかもしれません。ところが、Line Shader は線に太さをつける事ができません<sup>1</sup>)。

<img width="256" alt="Screen Shot 2016-12-24 at 21.21.31.png" src="https://qiita-image-store.s3.amazonaws.com/0/65634/bf0debfe-c094-db4c-3fd0-0cbfca211037.png">


他にやり方があるかもしれませんが、次の３つのやり方があると思います。

1. Point Shader を使い、連続したドットを少しづつ座標をずらして重ねうつ
2. Triangle Shader を使い、筆先ペン先などの Texture を少しづつ座標をずらして重ねうつ
3. 線を細かい三角形に分解して、Triangle Shader でレンダリングする

どちらも 点で打つか、三角形を組み合わせて打つかの違いだけで、基本原理は同じです。点をずらして打つというイメージができない方の為に、図を用意いたしました。点と点の間隔を小さくしていくと、どこかで一つの線のように見えてくるというわけです。

<img width="256" alt="Screen Shot 2016-12-24 at 21.20.48.png" src="https://qiita-image-store.s3.amazonaws.com/0/65634/6907eb89-6b8c-70e2-b775-e2d7cf321403.png">

<img width="256" alt="Screen Shot 2016-12-24 at 21.21.04.png" src="https://qiita-image-store.s3.amazonaws.com/0/65634/b6e9508d-b2d7-f7f5-eb0c-0003b755321e.png">


ちなみに、かの有名な Apple のサンプルコード GLPaint<sup>3</sup> は OpenGL ではありますが、2 のやり方です。また、1 の Point Shader を使う場合には、Point Size のサイズの制限があるので注意が必要です。例えば、ズーム可能にした場合、ある一定のところで、それ以上ズームしても線の太さが変わらなくなってしまう事になるからです。そんな場合にはズーム倍率を制限するなり、解像度を制限するなり何らかの対策が必要になるかもしれません。

| Resources | [iOS 10] iOS_GPUFamily1_v3 〜 iOS_GPUFamily3_v2 |
|:----------|-------------------|-------------------|-------------------|
| Maximum size of a point primitive | 511 |

<sup>2</sup> Metal Feature Sets

今回は上記の二つとは別の方法で線を実装するシェーダを書いてみたので紹介したいと思います。

# StrokeShader

作戦はこうです。A, B, C ... と続く有限の線分があったとします。この線分に太さを与える為に、必要な三角形を生成します。ここでは線の太さを W とします。

<img width="348" alt="Screen Shot 2016-12-24 at 21.43.00.png" src="https://qiita-image-store.s3.amazonaws.com/0/65634/444f6736-af9b-f00f-d723-f22ce04d95f6.png">

こんな形の線を Metal で描画する事をゴールとします。

# 幾何学的情報生成

あとで説明するある事情のため、CGPoint の class 版 CPoint を用意します。

```swift:CPoint
class CPoint: Hashable {
	var point: CGPoint
	
	var x: CGFloat { return point.x }
	var y: CGFloat { return point.y }
	
	init(_ point: CGPoint) {
		self.point = point
	}
	
	init(x: CGFloat, y: CGFloat) {
		self.point = CGPoint(x: x, y: y)
	}
	
	var hashValue: Int { return self.x.hashValue &- self.y.hashValue }
	
	static func == (lhs: CPoint, rhs: CPoint) -> Bool { // same value points should be different
		return lhs === rhs
	}
}

```

そして、 CPoint と CGPoint のどちらもベクターで演算しやすいように、extension を仕込んでおきます。

```swift:CPoint
extension CPoint {

	static func - (lhs: CPoint, rhs: CPoint) -> CPoint {
		return CPoint(x: lhs.x - rhs.x, y: lhs.y - rhs.y)
	}

	static func + (lhs: CPoint, rhs: CPoint) -> CPoint {
		return CPoint(x: lhs.x + rhs.x, y: lhs.y + rhs.y)
	}

	static func * (lhs: CPoint, rhs: CGFloat) -> CPoint {
		return CPoint(x: lhs.x * rhs, y: lhs.y * rhs)
	}

	static func / (lhs: CPoint, rhs: CGFloat) -> CPoint {
		return CPoint(x: lhs.x / rhs, y: lhs.y / rhs)
	}
	
	static func * (lhs: CPoint, rhs: CPoint) -> CGFloat { // dot product
		return lhs.x * rhs.x + lhs.y * rhs.y
	}

	static func ⨯ (lhs: CPoint, rhs: CPoint) -> CGFloat { // cross product
		return lhs.x * rhs.y - lhs.y * rhs.x
	}

	static func × (lhs: CPoint, rhs: CPoint) -> CGFloat { // cross product
		return lhs.x * rhs.y - lhs.y * rhs.x
	}
	
	var length²: CGFloat {
		return (x * x) + (y * y)
	}

	var length: CGFloat {
		return sqrt(self.length²)
	}

	var normalized: CPoint {
		let length = self.length
		return CPoint(x: x/length, y: y/length)
	}

}
```

```swift:CGPoint
extension CGPoint {

	static func - (lhs: CGPoint, rhs: CGPoint) -> CGPoint {
		return CGPoint(x: lhs.x - rhs.x, y: lhs.y - rhs.y)
	}

	static func + (lhs: CGPoint, rhs: CGPoint) -> CGPoint {
		return CGPoint(x: lhs.x + rhs.x, y: lhs.y + rhs.y)
	}

	static func * (lhs: CGPoint, rhs: CGFloat) -> CGPoint {
		return CGPoint(x: lhs.x * rhs, y: lhs.y * rhs)
	}

	static func / (lhs: CGPoint, rhs: CGFloat) -> CGPoint {
		return CGPoint(x: lhs.x / rhs, y: lhs.y / rhs)
	}
	
	static func * (lhs: CGPoint, rhs: CGPoint) -> CGFloat { // dot product
		return lhs.x * rhs.x + lhs.y * rhs.y
	}

	static func ⨯ (lhs: CGPoint, rhs: CGPoint) -> CGFloat { // cross product
		return lhs.x * rhs.y - lhs.y * rhs.x
	}

	static func × (lhs: CGPoint, rhs: CGPoint) -> CGFloat { // cross product
		return lhs.x * rhs.y - lhs.y * rhs.x
	}
	
	var length²: CGFloat {
		return (x * x) + (y * y)
	}

	var length: CGFloat {
		return sqrt(self.length²)
	}

	var normalized: CGPoint {
		let length = self.length
		return CGPoint(x: x/length, y: y/length)
	}

}
```

そして、点と点を結ぶ Line を定義します。線と線の交点を調べる関数なども入っています。

```swift:Line
struct Line {

	var from: CPoint
	var to: CPoint
	
	init(from: CPoint, to: CPoint) {
		self.from = from
		self.to = to
	}
	
	var vector: CPoint { return to - from }
	var length: CGFloat { return (to - from).length }

	static func intersection(_ line1: Line, _ line2: Line, _ segment: Bool) -> CPoint? {
		let v = line2.from - line1.from
		let v1 = line1.to - line1.from
		let v2 = line2.to - line2.from
		let cp = v1 × v2
		if cp == 0 { return nil }

		let cp1 = v × v1 // cross product
		let cp2 = v × v2 // cross product
		
		let t1 = cp2 / cp
		let t2 = cp1 / cp
		let ε = CGFloat(0).nextUp
		if segment {
			if t1 + ε < 0 || t1 - ε > 1 || t2 + ε < 0 || t2 - ε > 1 { return nil }
		}
		return line1.from + v1 * t1
	}

	static func angle(_ line1: Line, _ line2: Line) -> CGFloat {
		let a = line1.to - line1.from
		let b = line2.to - line2.from
		return atan2(b.y - a.y, b.x - a.x)
	}

}
```

そして、始点、または終点を表す LineCap を用意します。このクラスは始点(p1)と終点(p2)、そして線幅(width)を指定すれば、三角形の元となる座標が(a, b, c, d, e)の形で得られます。

```swift
class LineCap {

	//		    c
	//	   b+---+---+d
	//		|		|
	//	   a+	o	+e
	//		|	|	|
	//		|	|	|

	var a: CPoint
	var b: CPoint
	var c: CPoint
	var d: CPoint
	var e: CPoint

	init(from p1: CPoint, to p2: CPoint, width: CGFloat) {
		let radius = width / 2
		let v = (p2 - p1)
		let halfPi = CGFloat.pi / 2
		let quarterPi = CGFloat.pi / 4
		let sqrt2 = CGFloat(sqrt(2))
		let θ = angle(p1, p2)
		self.a = CPoint(x: cos(θ - halfPi) * radius + p2.x, y: sin(θ - halfPi) * radius + p2.y)
		self.b = CPoint(x: cos(θ - quarterPi) * radius * sqrt2 + p2.x, y: sin(θ - quarterPi) * radius * sqrt2 + p2.y)
		self.c = p2 + v.normalized * radius
		self.d = CPoint(x: cos(θ + quarterPi) * radius * sqrt2 + p2.x, y: sin(θ + quarterPi) * radius * sqrt2 + p2.y)
		self.e = CPoint(x: cos(θ + halfPi) * radius + p2.x, y: sin(θ + halfPi) * radius + p2.y)
	}
}
```

ネーミングはイマイチですが、太さを持った線分の座標(a, b, c, d)を求める LineBody を用意します。

```swift:LineBody
class LineBody {

	//			p2
	//	   b+---o---+c
	//		|	|	|
	//		|	|	|
	//		|	|	|
	//	   a+---o---+d
	//			p1
	
	var a: CPoint
	var b: CPoint
	var c: CPoint
	var d: CPoint

	init(p1: CPoint, w1: CGFloat, p2: CPoint, w2: CGFloat) {
		let r1 = w1 / 2
		let r2 = w2 / 2
		let halfPi = CGFloat.pi / 2
		let θ = angle(p1, p2)
		self.a = CPoint(x: cos(θ - halfPi) * r1 + p1.x, y: sin(θ - halfPi) * r1 + p1.y)
		self.b = CPoint(x: cos(θ - halfPi) * r2 + p2.x, y: sin(θ - halfPi) * r2 + p2.y)
		self.c = CPoint(x: cos(θ + halfPi) * r2 + p2.x, y: sin(θ + halfPi) * r2 + p2.y)
		self.d = CPoint(x: cos(θ + halfPi) * r1 + p1.x, y: sin(θ + halfPi) * r1 + p1.y)
	}

}
```

これで、幾何学的な情報を計算する道具は揃いました。では実際に線分を三角形で組み立てていきましょう。ここで問題となるのが線分と線分の交わる角度です。線分に太さがあるときは、次の線分の終点が内回り（緑）になる場合と、外回り（青）になる場合があります。LineBody の値を使うと、うまく座標が拾えません。

<div>
<img width="300" alt="Screen Shot 2016-12-24 at 22.43.02.png" src="https://qiita-image-store.s3.amazonaws.com/0/65634/08c30ccf-44c8-7864-75c8-6f58393d0249.png" />

<img width="300" alt="Screen Shot 2016-12-24 at 22.49.30.png" src="https://qiita-image-store.s3.amazonaws.com/0/65634/3517af5e-cd21-49e2-1555-6aa8c3140f18.png" />
</div>

そこで、LineBody 青の左手側(a, b) と、緑の右手側(d, c)の線分が実際に交点を持つか否かで、ひろう座標と三角形の組み合わせが異なってきます。図では座標の (q, r) をつなぐ為にさらなる三角形を追加する必要があります。わかりやすいように三角形を拾い出して、色分けしてみましょう。

<img width="250" alt="Screen Shot 2016-12-24 at 23.07.10.png" src="https://qiita-image-store.s3.amazonaws.com/0/65634/27b9df8e-b21c-046f-3265-58f8dde3833b.png"/>

これを、単色で塗りつぶしたり、Fragment Shader で線分からの距離に応じて、alpha 値を変えてあげれば、綺麗な曲線になるはずです。後述するサンプルはそこまでやっていません。また線自体が交差する場合は、考慮が必要な場合があるかもしれません。

<img width="200" alt="Screen Shot 2016-12-24 at 23.12.42.png" src="https://qiita-image-store.s3.amazonaws.com/0/65634/1f240566-d822-a665-94a2-5632c537930f.png"/>

# 頂点情報

さて、出来上がった三角形の集合から、VertexBuffer を作る際には一つ問題があります。頂点情報が多すぎる事になる可能です。そもそも、同じ座標の頂点を数個の三角形で利用されている場合もあります。この問題を解決するには、

* triangleStrip を使う
* Index ベースで描く

そもそも、線を描くので、triangleStrip などは本当は向いていると思うのですが、この外回りのイレギュラーな形を幾何学的に綺麗に三角形にマッピングできるか自信がなかったので、今回は、次の Index ベースで試してみました。

Index ベースの方法では、頂点情報とインデックス情報を別々のバッファに書き出して、頂点情報のｎ番目ｍ番目という具合に三角形を指定します。インデックスは UInt16 とかを使ったりもできるんので、GPU に送る情報をグっと小さくする事ができます。

そこで、頂点のインデックスを作るにあたっては、座標がたまたま同じだから、同じ頂点とみなすでは不十分な場合もあるので（後述します）、CGPoint のオブジェクト版 CPoint を使い、そもそも値が同じだからではなく、そもそも同じオブジェクトかどうかでインデックスを作ります。

```swift:MTLRenderCommandEncoder
func drawIndexedPrimitives(type primitiveType: MTLPrimitiveType, indexCount: Int, indexType: MTLIndexType, indexBuffer: MTLBuffer, indexBufferOffset: Int, instanceCount: Int, baseVertex: Int, baseInstance: Int)
```

線分の元となる座標は３つのみから作られる、頂点情報とインデックスの例です。これを MTLBuffer にセットして、レンダリングを行います。

<img width="160" alt="Screen Shot 2016-12-25 at 0.02.51.png" src="https://qiita-image-store.s3.amazonaws.com/0/65634/228256e5-5005-4d82-dfb2-f118076478f4.png">

［頂点情報］

| n | vertex |
|:--|--------|
| 0 | (100.0, 100.0)  |
| 1 | (71.3783, 85.6892)  |
| 2 | (85.6892, 57.0675)  |
| 3 | (114.311, 71.3783)  |
| 4 | (57.0675, 114.311)  |
| 5 | (85.6892, 128.622)  |
| 6 | (342.932, 185.689)  |
| 7 | (342.932, 214.311)  |
| 8 | (300.0, 200.0)  |
| 9 | (228.446, 200.0)  |
| 10 | (100.0, 300.0)  |
| 11 | (114.311, 328.622)  |
| 12 | (85.6892, 271.378)  |
| 13 | (71.3783, 314.311)  |
| 14 | (57.0675, 285.689)  |
| 15 | (85.6892, 342.932)  |

［インデックス情報］

```
[ 0, 1, 2, 0, 2, 3, 0, 4, 1, 0, 5, 4, 6, 7, 8, 6, 0, 3, 6, 8, 0, 5, 0, 8, 8, 5, 9, 8, 10, 7, 11, 10, 7, 9, 8, 10, 9, 10, 12, 10, 13, 14, 10, 14, 12, 10, 15, 13, 10, 11, 15 ]
```

### 頂点の座標が同じでも、異なる頂点として扱わなければならない場合

頂点情報は多くの場合、色や uv 情報が含まれています。例えば、(a,b,e,d)の青の部分と (b,c,f,e) の黄色の部分のある描画を行いたいと思ったとします。下図の左にあたります。問題は b と e に何色を指定しますか？という問題がです。b と e に 青を指定すると、右の図のように (b,c,f,e)の部分に青が浸潤してしまいます。同様に、b と e に黄色を指定すると、(a,b,e,d)の部分に黄色が浸潤してしまいます。

こんな場合は、b と e は偶然同じ座標だっただけで、b1, b2 そして e1, e2 と色情報を含む頂点情報はそれぞれの所属ごとに分ける必要性があります。

<img width="461" alt="Screen Shot 2016-12-25 at 0.34.37.png" src="https://qiita-image-store.s3.amazonaws.com/0/65634/30188e91-2421-b95b-76e1-bf60191ee506.png">

# 疑問

[1] 例えば手書きの場合、いつ手を離すかわからないので、Vertex のサイズをどのくらいにすればいいか、わかりません。よって場合によっては、MTLBuffer を拡張してあげないといけない場合があると思うのですが、新しいの作ってコピーして入れ替えるしかないのでしょうかね。MTLHeap とか使ってうまくできないですかね。

# Metal2DScroll

これまでに解説してきた内容は、GitHub で公開している Metal2DScrollable に含まれています。「StrokeRenderable, StrokeRenderer, StrokeShaders, StrokeShape」あたりが参考になるはずです。

### Metal2DScrollable
https://github.com/codelynx/Metal2DScrollable

![Screen Shot 2016-12-25 at 1.02.56 AM.png](https://qiita-image-store.s3.amazonaws.com/0/65634/3aa734e3-4579-2cb7-9ff3-2d0034e8860b.png)

* UIScrollView + Metal でスクロール＆ズーム可能なサンプルコードです
* 指で画面をなぞると、StrokeShader で線を描く事ができます
* スクロールは二本指です
* 最後の３ストーロークのみ保持しています
* さらに最後の１ストロークは、どのような三角形が作られているか視覚化できるようになっています
* シェーダー内のコードは色指定可能になっていますが、頂点情報を作るところで赤固定にしています
* フラグメントシェーダーでのスムージングはやっていません
* たくさんのテストができていないので、ストロークが長いとクラッシュする可能性があります
* ストロークは保存されません
* 回転させると、座標の計算に不具合がある場合があります
* Touch から線を組み立てると、三角形をプログレッシブに生成する必要があり、上記の説明よりも技巧的な実装になっています

# まとめ

その昔、OpenGL ES 1.1 の時代に手書きの draw アプリの開発を行いました。ES 1.1 なのでシェーダーではなく固定パイプラインでした。GLPaint を参考に高速な描画を心がけていました。その当時は、Point Shader で線を描いていました。これだと超高速で描画できるのですが、ズームされるとそれ以上太くできない線が出てきてあれこれ思案していました。

http://www.appbank.net/2010/10/17/iphone-application/178275.php

そのうち、こんなような議論があり、三角形ベースのストロークシェーダーにチャレンジしてみました。

https://forum.libcinder.org/topic/smooth-thick-lines-using-geometry-shader

ここから、ペンにテクスチャを貼り付けて、uv マップ考えたり、フラグメントシェーダーでラインのスムージングを行うのは正直大変だなと思いました。

あと、iOS 10 + A9以降で使える tessellation を使えば、Bezier パスなんかもできそうかなと思いましたが、このトライアングル型ストロークで燃え尽きてしまった感があります。

この Metal の Advent Calendar に堤さんに召喚された時は、正直「ヤバイ」と思いました。それは去年の年末、今年の年始頃に、同じようなテーマに挑んで自分のあまり線形代数力に沈没していたからです（例えるならルービックキューブを適当に回して揃うのを待つみたいな）。今回の Advent Calendar ので召喚され、奮起して再度立ち上がり、同じ課題に取り組みました。結果、Metal + UIScrollView で普通のアプリっぽい事ができるようになる素地ができたと思っているので、自分的には本当に良かったと思っています。召喚していただいた堤さんありがとうございました。そのうちステーキでも食べながら語りましょう。

では、皆さん Merry Christmas & Happy New Year!! 🎉 🎉 🎉


---

<sup>1</sup> http://stackoverflow.com/questions/15276454/is-it-possible-to-draw-line-thickness-in-a-fragment-shader
<sup>2</sup> https://developer.apple.com/metal/limits/
<sup>3</sup> https://developer.apple.com/library/content/samplecode/GLPaint/Introduction/Intro.html