WebGL でテッセレーションして、曲面パッチ間が滑らかに繋がった物体を表示（１）

## WebGL テッセレーション ビューワ

「独自の高次元曲面パッチデータを WebGL 上でリアルタイムにテッセレーションし、ウェブブラウザに表示する 3Dモデルビューワ」を作ってみました。

と、突然言われても意味が分からないと思われるので、下記にデモのリンクを貼りました。（Netlify を使用）
リンクをクリックすると、デモの 3Dモデルビューワが開きます。
<a href="https://beziex.netlify.com/beziex_we/">
Beziex_We : (https://beziex.netlify.com/beziex_we/)</a>

キャッシュが無い時の起動は遅いかもしれませんが、気長に待っていただけると助かります。ちなみにスクリーンショットは、こんな感じです。（元データは <a href="https://twitter.com/thecoolmuseum/status/785896516422471681">クールなびじゅつかん館長さんのツイート</a> を使わせていただきました。CC0 1.0 です）
<img alt="overview.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/482181/d6985e76-992d-b082-b813-c2d04e5b03b5.png">
左が Windows 上、右が Android 上（縦向きのみ対応）で、どちらも Chrome で動いてます。Mac や iPhone 等では確かめてないので、動かなかったらゴメナンサイ。
WebGL2 は敢えて避け、「無印の WebGL」 + 「拡張機能いくつか」で実装したので、動く環境は多いと思うのですが。。

なおデモの使い方は、下記リンクをご覧ください。<a href="https://github.com/beziex/Beziex_We/blob/master/README.md#demo--usage--%E3%83%87%E3%83%A2%E3%81%A8%E4%BD%BF%E3%81%84%E6%96%B9">
デモと使い方 : (beziex/Beziex_We [github] のところの README.md 内)</a>

またソースコードも github で公開してます。（MIT ライセンスです）
<a href="https://github.com/beziex/Beziex_We">beziex/Beziex_We [github] :  (https://github.com/beziex/Beziex_We)</a>

それでは、デモで少し感じを掴んでもらったところで、技術的な説明に入りたいと思います。少しボリュームがありそうなので、記事を2回に分けて載せる予定です。


## 曲面パッチとテッセレーション

私はあんまりゲームはしないんですが、TV でゲームの CM とかを見てると、

1. PS4 等の、とてつもなく緻密なキャラの 3DCG ゲーム
2. スマホゲーム等にありがちな、とんでもなくローポリな 3DCG ゲーム

の両者間の落差が大きくて、驚愕してしまいます。もちろん 1. の方が綺麗なのですが、2. がローポリであるのも理由があったりするわけです。

このローポリとしなければならなかった理由として、GPU の能力不足、メモリ不足、ネット速度から来る制限、等が考えられるでしょう。この中で「GPU の能力不足」と「メモリ不足」はそのうち解決しそうですが、「ネット速度」は 5G になっても辛そう、という気がしてます。
なおテクスチャの容量等も当然ネット速度に影響しますが、ここでは敢えて触れません。

ところで、OpenGL 等にはテッセレーションシェーダというものがあります（古いバージョンを除く）。正確には2種類のシェーダから成り立っているのですが、ここではまとめて考えます。
なおこのシェーダは現時点では、まだ残念ながらディスプレイスメントマッピングぐらいにしか使われていないようです。しかし本当は、曲面パッチを細かなポリゴンに分割するのにとっても有効な代物なんです。ちなみに曲面パッチとは、ベジェ曲面やグレゴリーパッチ等のことを言います。

この曲面パッチはポリゴンよりも多くの情報を必要とするため、曲面パッチとポリゴンそれぞれ 1個をデータサイズで比較すると、当然曲面パッチの方が大きいです。しかし曲面パッチは、任意の細かさでポリゴンに分割（これをテッセレーションという）できるので、"ある程度の細かさ" まで分割すると、

- 「曲面パッチモデルで分割後の複数のポリゴン」と同数のポリゴンを持つポリゴンモデルの物体は、曲面パッチモデルの物体よりデータサイズが大きくなる。

という逆転現象が起きます。すなわちこれは、

- ハイポリゴン（小さなポリゴンがたくさん有る）レベルの物体であれば、曲面パッチの方がデータサイズが小さくなる可能性がある。
- そして曲面パッチの方は、さらに細かく分割可能

ということを意味します。
このような利点があるのですが、ゲーム界では残念ながら曲面パッチは使われていません。それにはいくつか理由があるのですが、これについては次回で述べる予定です。

なお本技術は「曲面パッチをテッセレーションする」のが目的なので、OpenGL / DirectX / Vulkan 等々、種別を問わず汎用的に考えています。
WebGL も目的達成に使えそうな技術であり、しかも「ユーザーの方がインストールやビルドをしなくても結果を見てもらえる」というところが、大きなメリットです。

しかし現状の WebGL にはテッセレーションシェーダが無い、という重大な問題がありました。つまりこのままでは目的を果たせなくなります。でも色々なサイトの力を借りて何とか実装！ ということで、この場で発表させていただいた次第です。

ちなみにここまで「本技術はネットゲームに使えるかも！？」という観点から、そのメリットについて述べてきましたが、github の README.md の方では LOD ( Level of Detail ) に使用した場合のメリットを記載しています。<a href="https://github.com/beziex/Beziex_We/blob/master/README.md#why-do-we-need-it--%E3%81%AA%E3%81%9C-beziex_we-%E3%81%8C%E5%BF%85%E8%A6%81">
なぜ Beziex_We が必要？ : (beziex/Beziex_We [github] のところの README.md 内)</a>


## 高次元曲面パッチ

本ビューワで読み込んでいる 3Dデータは、独自の高次元曲面パッチを使っています。具体的には、高次グレゴリーパッチを変形したもので、32個のコントロールポイントを持ちます。（ちなみに 3次ベジェ曲面は 16個）
またこのパッチは、

- ポリゴン → 独自拡張の Catmull–Clark サブディビジョン → 高次元曲面パッチ

という順番で変換したものとなっています。（まだ未公開のコンバータを使用）
すなわちサブディビジョンに近似したパッチとなっているわけですが、変換アルゴリズム等は今後、コンバータの公開と同時に発表したいと考えています。ただ高次元曲面パッチの式については、次回で書く予定です。


## 曲面パッチと法線の関連性

ポリゴンモデルの場合、法線データも位置データ同様に事前に用意しておいて、実行時に読み込ませる方法が一般的です。法線を自動計算させることも可能ですが、思い通りの向きにするのは難しいと思います。

次に曲面パッチモデルの場合を考えてみましょう。この場合、テッセレーション後のポリゴン頂点に対して、法線データを事前に用意する必要はありません。それは正確に自動計算出来るからで、曲面の u方向と v方向の接線（微分値）の外積が法線になるからです。

ただし PNトライアングル（「改良 PNトライアングル」を含む）のように、法線データ（法線専用コントロールポイントも含む）を持つ曲面パッチもあります。
確かに「改良 PNトライアングル」では、隣接する 2曲面パッチの境界曲線は一致していて、クラックと呼ばれる裂け目は出来ません。しかし境界曲線上のある点において、2曲面の（自動計算から得られる）法線は異なることが多いのです。これは PNトライアングルのアルゴリズム上、仕方がありません。

このように「境界曲線は一致しているものの、法線が一致しない」タイプの曲面接続を、C0接続と呼びます。
C0接続では、法線が一致しない状況を補うため、2曲面で共通する偽の法線を入れ込んでやります。これが法線データも必要となる理由です。しかしあくまでも偽の法線なので、物体の輪郭部分を見ると折れ曲がっているように見える場合があります。（実際、折れ曲がっている）

それに対し、本プログラムで採用している高次元曲面パッチは、「境界曲線は当然一致していて、法線も一致している」タイプです。このタイプの曲面接続を G1接続と呼びます。つまり「曲面パッチ間が滑らかに繋がる」わけで、これが本稿の題名の由来となっているのです。
なお G1接続では法線データを用意する必要が無いので、その分データ量が減ります。（32個もコントロールポイントがあったらデータ量多いだろう、というツッコミは無しで。。）


## シェーダ内での法線の計算

曲面パッチモデルでは法線を自動計算しますが、CPU で計算するとリアルタイムには表示できないので、シェーダ内にコードを記述して、GPU で計算させます。また処理を行うシェーダは、本来であればテッセレーションシェーダであるべきです。しかし WebGL にはテッセレーションシェーダが無いので、バーテックスシェーダ内で行うことにします。

なお 32個のコントロールポイントを使って、「テッセレーション後のポリゴン頂点」の "位置" を計算するのは難しくありません。各コントロールポイントの値を数式に当てはめるシェーダコードを実装するだけだからです。

それに対し法線の場合は、まず u方向と v方向の微分値を求めなければなりません。そのためには「u方向の微分値を求める数式」と「v方向の微分値を求める数式」にパラメータを埋め込む必要がありますが、問題はこのパラメータが「32個のコントロールポイントとは異なる」ということです。
ただし本パラメータは、32個のコントロールポイントから変換可能です。しかしこの変換処理は少々重たいので、もし「テッセレーション後のポリゴン頂点」毎に GPU 内で計算すると、遅くなってしまいます。

ちなみにコントロールポイントはその物体が変形しない限り、値は変化しません。つまり微分値用のパラメータも毎回計算する必要は無く、最初に一回だけ行えば良いことになります。すなわち

1. 微分値用のパラメータを、CPU で事前に計算しておく。
2. コントロールポイントに加え、微分値用のパラメータも GPU に送る。

とするわけです。なお実際にはコントロールポイントもそのまま送るのではなく、GPU処理の軽減のため組み直しています。


## コントロールポイント組み直し＆微分値用パラメータ生成の処理

本プログラムでは下記 `BxGlShader` クラスの `getPosDiff` 関数で、コントロールポイント組み直しと微分値用パラメータ生成を行っています。

```typescript:BxGlShader.getPosDiff
private getPosDiff(patch: BxCmSeparatePatch_Object, surfaceNo: number): {
    hPosBez0: BxBezier3Line3|null, hPosBez1: BxBezier6Line3|null, hPosBez2: BxBezier6Line3|null, hPosBez3: BxBezier3Line3|null,
    vPosBez0: BxBezier3Line3|null, vPosBez1: BxBezier6Line3|null, vPosBez2: BxBezier6Line3|null, vPosBez3: BxBezier3Line3|null,
    hDiffBez0: BxBezier2Line3|null, hDiffBez1: BxBezier5Line3|null, hDiffBez2: BxBezier5Line3|null, hDiffBez3: BxBezier2Line3|null,
    vDiffBez0: BxBezier2Line3|null, vDiffBez1: BxBezier5Line3|null, vDiffBez2: BxBezier5Line3|null, vDiffBez3: BxBezier2Line3|null}
{
    const {hPosBez0, hPosBez1, hPosBez2, hPosBez3} = this.getPosBezierH(patch, surfaceNo);
    const {vPosBez0, vPosBez1, vPosBez2, vPosBez3} = this.getPosBezierV(patch, surfaceNo);
    const {hDiffBez0, hDiffBez1, hDiffBez2, hDiffBez3} = this.getDiffBezierH(patch, surfaceNo);
    const {vDiffBez0, vDiffBez1, vDiffBez2, vDiffBez3} = this.getDiffBezierV(patch, surfaceNo);

    return {
        hPosBez0: hPosBez0, hPosBez1: hPosBez1, hPosBez2: hPosBez2, hPosBez3: hPosBez3, vPosBez0: vPosBez0, vPosBez1: vPosBez1, vPosBez2: vPosBez2,
        vPosBez3: vPosBez3, hDiffBez0: hDiffBez0, hDiffBez1: hDiffBez1, hDiffBez2: hDiffBez2, hDiffBez3: hDiffBez3, vDiffBez0: vDiffBez0,
        vDiffBez1: vDiffBez1, vDiffBez2: vDiffBez2, vDiffBez3: vDiffBez3
    }
}
```

ということで、やっとソースコードが出てきました。ちなみに本プログラムは（サードパーティ OSS 以外）すべて、TypeScript で実装されています。（GLSL は除く）
JavaScript では組みたくなかったので、頑張りました！！

なおこの関数によって生成される変換後の値は、1パッチ辺り「ベクトル値ベースで 80個」になります。すなわち 32個から 80個に増えたわけです。
ちなみにこの 80個の値は、上記コードにある「複数のオブジェクト」の形では無く、配列としなければなりません。これを行っているのが、同じく `BxGlShader` クラスの`convVtfInfo` 関数です。（`vtfInfo` という配列に入れている）

```typescript:BxGlShader.convVtfInfo
private convVtfInfo(hPosBez0: BxBezier3Line3|null, hPosBez1: BxBezier6Line3|null, hPosBez2: BxBezier6Line3|null, hPosBez3: BxBezier3Line3|null,
    vPosBez0: BxBezier3Line3|null, vPosBez1: BxBezier6Line3|null, vPosBez2: BxBezier6Line3|null, vPosBez3: BxBezier3Line3|null,
    hDiffBez0: BxBezier2Line3|null, hDiffBez1: BxBezier5Line3|null, hDiffBez2: BxBezier5Line3|null, hDiffBez3: BxBezier2Line3|null,
    vDiffBez0: BxBezier2Line3|null, vDiffBez1: BxBezier5Line3|null, vDiffBez2: BxBezier5Line3|null, vDiffBez3: BxBezier2Line3|null,
    surfaceOfs: number, vtfInfo: number[]): void {

    this.fromBezier3(<BxBezier3Line3>hPosBez0,  surfaceOfs,  0, vtfInfo);
    this.fromBezier6(<BxBezier6Line3>hPosBez1,  surfaceOfs,  4, vtfInfo);
    this.fromBezier6(<BxBezier6Line3>hPosBez2,  surfaceOfs, 11, vtfInfo);
    this.fromBezier3(<BxBezier3Line3>hPosBez3,  surfaceOfs, 18, vtfInfo);

    this.fromBezier3(<BxBezier3Line3>vPosBez0,  surfaceOfs, 22, vtfInfo);
    this.fromBezier6(<BxBezier6Line3>vPosBez1,  surfaceOfs, 26, vtfInfo);
    this.fromBezier6(<BxBezier6Line3>vPosBez2,  surfaceOfs, 33, vtfInfo);
    this.fromBezier3(<BxBezier3Line3>vPosBez3,  surfaceOfs, 40, vtfInfo);

    this.fromBezier2(<BxBezier2Line3>hDiffBez0, surfaceOfs, 44, vtfInfo);
    this.fromBezier5(<BxBezier5Line3>hDiffBez1, surfaceOfs, 47, vtfInfo);
    this.fromBezier5(<BxBezier5Line3>hDiffBez2, surfaceOfs, 53, vtfInfo);
    this.fromBezier2(<BxBezier2Line3>hDiffBez3, surfaceOfs, 59, vtfInfo);

    this.fromBezier2(<BxBezier2Line3>vDiffBez0, surfaceOfs, 62, vtfInfo);
    this.fromBezier5(<BxBezier5Line3>vDiffBez1, surfaceOfs, 65, vtfInfo);
    this.fromBezier5(<BxBezier5Line3>vDiffBez2, surfaceOfs, 71, vtfInfo);
    this.fromBezier2(<BxBezier2Line3>vDiffBez3, surfaceOfs, 77, vtfInfo);
}
```


## バーテックスシェーダでテッセレーションっぽいことをするためには

次に前項の `vtfInfo` を GPU に送り込んで、バーテックスシェーダで処理しなければなりませんが、どうすれば良いのでしょうか？
テッセレーションシェーダが存在すれば、`gl.bufferData` で送れば良いのですが。。 ちなみに（テッセレーションシェーダに対し）1パッチ辺り最大 32個までのコントロールポイントしか送れない、と思っている方もおられますが、間違いです。少なくとも、GTX 970M では 1パッチ 80個（ベクトル値ベース）でも大丈夫でしたよ。（ただしテクニックが必要）

話を戻します。バーテックスシェーダで処理するために結局、先人の知恵をお借りしました。
<a href="https://qiita.com/takahito-tejima/items/cace1f8bb564bfe7de2f">
[WebGL] GPU でベジェ曲面をものすごい勢いで描く</a>
（以後、「GPU でベジェ曲面...」と略）

こちらはベジェ曲面ですが、本プログラムも基本的に同じ手法です。<a href="https://qiita.com/takahito-tejima">@takahito-tejima</a> さん、ありがとうございました。


## パッチ パラメータ テクスチャ

さて前々項の `vtfInfo` を GPU に送り込む方法ですが、具体的には「GPU でベジェ曲面...」にあるコントロールポイントテクスチャを流用しました。ただし送るのはコントロールポイントだけでは無いので、「パッチパラメータテクスチャ」と呼ぶことにします。<a href="https://qiita.com/takahito-tejima/items/cace1f8bb564bfe7de2f#%E3%82%B3%E3%83%B3%E3%83%88%E3%83%AD%E3%83%BC%E3%83%AB%E3%83%9D%E3%82%A4%E3%83%B3%E3%83%88%E3%83%86%E3%82%AF%E3%82%B9%E3%83%81%E3%83%A3%E4%BD%9C%E6%88%90">
コントロールポイントテクスチャ作成</a><a href="https://qiita.com/takahito-tejima/items/cace1f8bb564bfe7de2f#%E3%82%A4%E3%83%B3%E3%82%B9%E3%82%BF%E3%83%B3%E3%82%B9%E6%8F%8F%E7%94%BB">
インスタンス描画</a>

また <a href="https://qiita.com/emadurandal">@emadurandal</a> さんが書かれた、下記も参考にしています。（ただし 無印WebGL で実装したので、gl_InstanceID は使ってません）</a><a href="https://qiita.com/emadurandal/items/1812198d562bd1216c70#%E3%82%A2%E3%83%97%E3%83%AD%E3%83%BC%E3%83%81%EF%BC%93%E3%82%A4%E3%83%B3%E3%82%B9%E3%82%BF%E3%83%B3%E3%82%B9%E6%AF%8E%E3%83%87%E3%83%BC%E3%82%BF%E3%82%92%E3%83%86%E3%82%AF%E3%82%B9%E3%83%81%E3%83%A3%E3%81%A7%E7%94%A8%E6%84%8F%E3%81%97%E3%81%A6glsl%E3%81%AEgl_instanceid%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E5%A4%89%E6%95%B0%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%E3%82%A2%E3%82%AF%E3%82%BB%E3%82%B9%E8%A6%81webgl2">
アプローチ３：インスタンス毎データをテクスチャで用意して、GLSLのgl_InstanceID組み込み変数を使ってアクセス（要WebGL2）</a>

そして実装したのが同じく `BxGlShader` クラスの`initVtf_Post` 関数で、この中でテクスチャを生成しています。

```typescript:BxGlShader.initVtf_Post
private initVtf_Post(width: number, height: number, vtfAry: number[]): void {
    this.gl_.activeTexture(this.gl_.TEXTURE0);
    this.texture_[0] = this.gl_.createTexture();
    this.gl_.bindTexture(this.gl_.TEXTURE_2D, this.texture_[0]);
    this.gl_.pixelStorei(this.gl_.UNPACK_ALIGNMENT, 1);
    this.gl_.texImage2D(this.gl_.TEXTURE_2D, 0, this.gl_.RGBA, width, height, 0, this.gl_.RGBA, this.gl_.FLOAT, new Float32Array(vtfAry));

    this.gl_.texParameteri(this.gl_.TEXTURE_2D, this.gl_.TEXTURE_MAG_FILTER, this.gl_.NEAREST);
    this.gl_.texParameteri(this.gl_.TEXTURE_2D, this.gl_.TEXTURE_MIN_FILTER, this.gl_.NEAREST);
    this.gl_.texParameteri(this.gl_.TEXTURE_2D, this.gl_.TEXTURE_WRAP_S, this.gl_.CLAMP_TO_EDGE);
    this.gl_.texParameteri(this.gl_.TEXTURE_2D, this.gl_.TEXTURE_WRAP_T, this.gl_.CLAMP_TO_EDGE);

    this.gl_.bindTexture(this.gl_.TEXTURE_2D, null);
}
```

ちなみに `vtfInfo` は 1個のパッチの情報でしたが、ここでは `vtfAry` という名のすべてのパッチの情報を持つ配列となっています。


## リファインメントパターン（VBO）

「GPU でベジェ曲面...」によると、リファインメントパターンとは「テッセレーションする密度のトポロジーのメッシュ」のことらしいですが、要は VBO（Vertex buffer object）に xyz値では無く、uv値を入れるのが肝のようです。
ちなみに「GPU でベジェ曲面...」の下記の場所を参考にしました。<a href="https://qiita.com/takahito-tejima/items/cace1f8bb564bfe7de2f#%E3%83%AA%E3%83%95%E3%82%A1%E3%82%A4%E3%83%B3%E3%83%A1%E3%83%B3%E3%83%88%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3uv%E3%83%A1%E3%83%83%E3%82%B7%E3%83%A5%E7%94%9F%E6%88%90">
リファインメントパターン（UVメッシュ）生成</a>

なお「GPU でベジェ曲面...」では最終的な uv値（つまり 0～1 の値）を入れていますが、本プログラムでは整数値、すなわち「0 ～ 最大分割数」を入れています。この最大分割数は今のところ 32 としているので、(0 ～ 32) の整数値が入ることになります。
また「GPU でベジェ曲面...」では、テッセレーション分割数を変更する毎に VBO（後述する IBO も）を作り直す形ですが、本プログラムでは最大分割数（32）のモノを一回作って終わりです。

このようにしたのは独自の改良を加えたためですが、それについては <a href="#drawelementsinstancedangle%E5%BF%9C%E7%94%A8">drawElementsInstancedANGLE（応用）</a>で説明します。

というわけで実装してみたのが、`BxGlShader` クラスの`genVertexAry` 関数です。

```typescript:BxGlShader.genVertexAry
private genVertexAry(): vec3[] {
    const numTessMaxP = this.KNumTessMax + 1;

    const vertexAry: vec3[] = new Array<vec3>(numTessMaxP * numTessMaxP);
    for (let v=0; v<numTessMaxP; v++) {
        for (let u=0; u<numTessMaxP; u++) {
            const n = v * numTessMaxP + u;

            vertexAry[n] = vec3.fromValues(u, v, 0.0);
        }
    }

    return vertexAry;
}
```


## リファインメントパターン（IBO）

VBO に uv値を置いただけではトポロジーにはならないので、IBO（Index buffer object）に頂点インデックスを入れて、「テッセレーションする密度のトポロジーのメッシュ」を作ってやります。
なお Solid（シェーディング面表示）と Wire（ワイヤーフレーム表示）ではトポロジーが異なりますが、ここでは Solid についてのみ説明します。図にすると、こんな感じです。（分割数 4 の時の図。実際には最大分割数 32 なので、もっと多くのポリゴンになる）
<img alt="refinement-pattern.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/482181/6077b45c-94de-958e-1b47-e189411f3867.png">

この Solid の場合の IBO は、本プログラムでは `BxGlShader_Face` クラスの `genIndexAry` 関数で作成しています。

```typescript:BxGlShader_Face.genIndexAry
protected genIndexAry(): number[] {
    const indexAry = new Array<number>(this.KNumTessMax * this.KNumTessMax * 3 * 2);

    let   start = 0;
    const numTessMaxP = this.KNumTessMax + 1;

    for (let i=0; i<this.KNumTessMax; i++) {
        for (let u=0; u<i; u++) {
            this.genIndexAryMain(indexAry, numTessMaxP, start, u, i);
            start += 6;
        }

        for(let v=0; v<i; v++) {
            this.genIndexAryMain(indexAry, numTessMaxP, start, i, v);
            start += 6;
        }

        this.genIndexAryMain(indexAry, numTessMaxP, start, i, i);
        start += 6;
    }

    return indexAry;
}

private genIndexAryMain(indexAry: number[], numTessP: number, start: number, u: number, v: number): void {
    const vNo0 = (v + 0) * numTessP + (u + 0);
    const vNo1 = (v + 0) * numTessP + (u + 1);
    const vNo2 = (v + 1) * numTessP + (u + 1);
    const vNo3 = (v + 1) * numTessP + (u + 0);

    indexAry[start + 0] = vNo0;
    indexAry[start + 1] = vNo1;
    indexAry[start + 2] = vNo2;

    indexAry[start + 3] = vNo2;
    indexAry[start + 4] = vNo3;
    indexAry[start + 5] = vNo0;
}
```

これを見ると、「GPU でベジェ曲面...」と比べ、ちょっと複雑な処理になっていることが分かります。
それについては、下図をご覧ください。上の方の図はトポロジー、下の方はIBO の一次元配列（`indexAry`）を模したものです。（同じく分割数 4 の時の図）
<img alt="BxGlShader_Face.genIndexAry.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/482181/db1d37ec-1484-9b87-457c-030aa24152a0.png">

この 2つの図は同色の箇所が対応するようになっているのですが、`indexAry` 配列の先頭から「青エリア情報の後ろに黄エリア情報」「黄エリア情報の後ろに赤エリア情報」「赤エリア情報の後ろに緑エリア情報」という順番に並んでいるのが分かります。（実際にはこれを最大分割数の 32回繰り返している）

なぜこのようになっているのでしょうか？
それは <a href="#drawelementsinstancedangle%E5%BF%9C%E7%94%A8">drawElementsInstancedANGLE（応用）</a>で。


## drawElementsInstancedANGLE（基本）

前項までで、VBO と IBO を使ってリファインメントパターンを作成しましたが、この VBO/IBO 内のデータはすべての曲面パッチで同一です。
なぜなら曲面パッチはすべて 4本の境界曲線から成り、また分割数やトポロジーも同じだからです。つまり全曲面パッチの同じ分割位置には、同じ uv値を置いても良いことになります。

そうであれば、同じ情報をパッチ数の分だけ作るのは無駄だと思いませんか？ GPU に送るデータ量も増えますし。
実はジオメトリインスタンシングという方法で、これを解決することが出来ます。この方法は、

- 例えば「1個の曲面パッチ分の VBO/IBO」を作っておき、それを "何個表示" するか指定できる

という代物なのです。もちろん例えば「VBO に XYZ座標が書いてあって、それをそのまま出力したら同じ場所に表示されてしまう」ということになりかねないので、そこはシェーダプログラムに頑張ってもらいます。

このジオメトリインスタンシングについて、本プログラムでは `drawElementsInstancedANGLE` 関数を使いました。具体的には、`BxGlShader_Face` クラスの `drawMain_NonPreDiv` 関数内で使用しています。

```typescript:BxGlShader_Face.drawMain_NonPreDiv
protected drawMain_NonPreDiv(): void {
    if (this.numSurface_NonPreDiv_ == 0)
        return;

    this.setUniform(0, 1);

    const instancedAry = <ANGLE_instanced_arrays>(this.buf.glExt.instancedAry);

    const m = this.tessLevel * this.tessLevel * 3 * 2;
    instancedAry.drawElementsInstancedANGLE(this.gl_.TRIANGLES, m, this.gl_.UNSIGNED_INT, 0, this.numSurface_NonPreDiv_);
}
```

なお `BxGlShader_Face.drawMain_PreDiv` 関数でも使っており、それぞれ意味があるのですが、ここでは説明を省略します。

話を戻して、上記ソースコードの一番下の方に `drawElementsInstancedANGLE` 関数があると思いますが、その第 5 引数の `this.numSurface_NonPreDiv_` をご覧ください。
（正確には違いますが）この変数が曲面パッチの個数なので、この個数分だけ表示されることになるわけです。


## drawElementsInstancedANGLE（応用）

もう一度 `BxGlShader_Face.drawMain_NonPreDiv` 関数を見てみましょう。

```typescript:BxGlShader_Face.drawMain_NonPreDiv（抜粋）
protected drawMain_NonPreDiv(): void {
                :
    const m = this.tessLevel * this.tessLevel * 3 * 2;
    instancedAry.drawElementsInstancedANGLE(this.gl_.TRIANGLES, m, this.gl_.UNSIGNED_INT, 0, this.numSurface_NonPreDiv_);
}
```

`drawElementsInstancedANGLE` 関数の第 2 引数に `m` という変数がありますが、これは IBO のデータサイズを表しています。すなわちこの場合は、1個の曲面パッチ分の IBO です。

しかし分割数が変われば、1個の曲面パッチのデータサイズも変わります。現在 IBO には最大分割数（32）のデータが入っているはずですが、ここで敢えて `m` に IBO データサイズより小さい値を入れてやるとどうなるでしょう。
具体的には、現在設定されている分割数に必要な分だけのサイズを指定するわけです。

実はこのようにすると、IBO の先頭から指定サイズだけを使います。この時に重要なのが、前述した下図です。
<img alt="IBO.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/482181/2b5d6d80-9039-6d58-db2c-871a97ab257d.png">
これを見てみると、「分割数 1 の時は、青の情報だけが必要」「分割数 2 の時は、青と黄色の情報だけが必要」「分割数 3 の時は、青と黄色と赤の情報だけが必要」... というように、"分割数ごとに先頭から必要な分だけデータが並んでいる" ことが分かります。
すなわちこんな感じになるように、あらかじめ並べて置いたというわけです。それにより CPU は、

- 最大分割数（32）分の VBO/IBO を最初に一回だけ GPU に送っておく。
- 分割数が変わる度に、`drawElementsInstancedANGLE` 関数を実行する。

というふうに、GPU への送信量を最小限に抑えることが出来るのです。

また VBO の uv値に 0～1 では無く整数値を設定したのも、これに対処するためです。
それにはまず、現在の分割数 `tessLevel` を下記のように GPU に送っておきます。（分割数が変わる度に送り直す）

```typescript:BxGlShaderBase.setTessLevel
private setTessLevel(): void {
    const programObj    = <BxGlProgramBase>this.programObj_;
    const shaderProgram = <WebGLProgram>programObj.shaderProgram();

    const tessLevelLocation = this.gl_.getUniformLocation(shaderProgram, "tessLevel");
    this.gl_.uniform1f(tessLevelLocation, this.tessLevel);
}
```

その上で、下図をご覧ください。青エリアの右下端に、A という名の赤点があることが分かります。
<img alt="color-topo.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/482181/37dc3480-e69f-8f00-0cfd-669d6fecc231.png">

なお VBO にも A 点に対応する場所があって、何らかの固定値が書かれているはずです。

まず分割数に関わらず、図の左上端を (0, 0) とします。この時、分割数を 1 とすると青エリアだけを使うので、A 点は (1, 1) となります。しかし分割数 2 では青と黄色を使うことになり、よって A 点は (0.5, 0.5) でなければなりません。

しかし前述の通り「A 点の VBO での対応場所」に書かれているのは固定値なので、分割数によって値を変えることは出来ません。
そこで、A 点を整数値で (u, v) = (1, 1) と書くことにしたのです。これであれば、あらかじめ GPU に送っておいた `tessLevel` を使い、シェーダ側で (u/tessLevel, v/tessLevel) とすれば良いことになります。それにより例えば、分割数 2 の時は (1/2, 1/2) となるので、最終的な uv 値（0～1）が正しく生成できます。


## 次回

次回（後編）は、あと少し CPU 側のコードに触れた後、シェーダ側のプログラムについて説明します。またシェーダ側コード内に書かれている、独自高次元曲面パッチの式についても述べる予定です。

<a href="https://qiita.com/beziex/items/d913102ca03266996a0e">［後編］: WebGL でテッセレーションして、曲面パッチ間が滑らかに繋がった物体を表示（２）</a> →