クリンプされた平行四辺形によるトライアングルテッセレーション

今日知られているようなハードウェアテッセルレーション（DirectX 11 スタイル）は、2005 年に発売された Xbox 360 を皮切りに発端を有します。時が経つのは早いですね。それは、映画品質のリアルタイムレンダリングへと進化するための自然的な一歩でした。畢竟、テッセルレーションは当初のパイアックス・レイズ（Pixar Reyes）論文 [7] の鍵となる構成要素だったからです。

さて、現在では 20 年以上もの歳月が経過し、アルゴリズムに対する経験も深まりましたが、ハードウェアテッセルレーションがこれらのユースケースに対する解決策にはなりませんでした。しかしながら、DirectX 11 スタイルのテッセルレーションにおける核心的なアイデアは依然として優れており、それらを独自の文脈で再検討する価値があります。indsight の恩恵を得た私たちは、そのアイデアを継承しつつ、道中に異なる判断を下すことができ、同じ制約を満たしつつ望ましい性質を備えたアルゴリズムへと到達できるかを見極めることができます。

最終的なアルゴリズムは、以下のような姿になります。これは、ヘッダー画像に含まれるすべてのパターンの間を飛びながらも（popping）、滑らかに遷移することを可能にします。

コードは JavaScript 形式で保存されており、ご自由に利用してください（MIT ライセンスです）。実質的には、私が既存の C++ コードを持ち、「ミスター・クロード、これを変えて JavaScript ビューアーにして」と申し上げたものであり、GLHF です。

DirectX 11 のテッセルレーションは、具体的にどのように機能しているのでしょうか？

三角形の各辺には「テッセルレーションファクター」と呼ばれる値が割り当てられており、これはおよそその辺が持つ区間（セグメント）の数を表しています。DirectX 11 では、この値は [1, 64] の範囲にあります。ここで重要な設計上の決定事項として挙げられるのは、各テッセルレーションファクターを浮動小数点数とみなし、任意の値の間で線形補間（lerp）を行っても可視的な飛び切り（pop）が発生しないということです。この観点から、テッセルレーションの問題を 2 つのサブ問題に分類できます：

与えられたテッセルレーションファクターに対し、辺を線区間に分割する。
その辺の区間を与えられた三角形の内側を分割する。

これについてはオンラインで解説記事が存在します [3][4][5] また、Faibian Giesen氏による DirectX 11 テッセルレーターの段階についての論文 [6] も参照可能です。しかしながら、今回の演習では、表面的な概要だけでなく、詳細な部分に深く入り込みながら、その都度その都度導出していく方針とします。

では、どのようにして線区間をテッセルレーションすべきでしょうか？最も直感的な解決策は、二分法を用いてそれぞれの辺を 2 のべき乗ごとに半分に分割することです（Subdivision）。

※注釈：DirectX 11 ではテッセルレーションファクターの範囲は [1, 64] ですが、ここでは計算式を簡潔にするために [0 から始まる範囲] を使用します。

これにより、2 のべき乗ごとに理想的なテッセルレーションレベルが得られます。テッセルレーションファクターが 8 や 16 の場合は非常に良く見えますが、値が 11 という場合どのように処理すべきでしょうか？単純に 8 から 16 へ跳ぶのではなく、一度にすべての点を導入するのではなく、一点ずつ追加していくアプローチを採用できます。概念的には、例えば値が 11 とする場合、最後に追加された点を「ピボット点」と考えてください。テッセルレーションファクターが 11 の時点で、前回の 2 のべき乗である 8 を取り込み、新たなスロットとして 3 つを追加し、残りは 5 つとなります。ご自身で導出することも可能ですが（あるいはコードをご参照ください）、結果は以下のようなものになります：

これは、raw subdivision と同様の点を扱っていますが、すべての点を 2 のべき乗ごとに一度に導入するのではなく、一点ずつ遷移させています。では、ポップ（pop）を伴うことなく平滑な遷移を実現するためにアルゴリズムをどのように修正すればよいでしょうか？答えは、点自体は変化せず、変化する唯一のものとしてピボット点があることです。例えば値が 10.3 とした場合、セグメント数は切り上げて 11 にします。前回の subdivision から固定される点は 8 つ（ロックされている点）で、既に遷移してきているのは 2 点分であり、最後の点については前の点から次への地点までの間で 30% の線形補間（lerp）を行います。

ここがさらに興味深くなる部分で、次の問題として「分布」があります。我々は均一に間隔を空けたテッセルレーションを望みますが、現在のイテレーションではピボットの下方には濃密な間隔、上方には疎らな間隔を持っています。DirectX 11 はこの問題を解決するために、スライドしている点以外のすべての点を同じ長さとする方法をとります。

この変更には長所と短所があります。良い点は、より均一に間隔を空けたテッセルレーションが得られることです。悪い点は、非常に多くの移動（movement）が生じるということです。以前はピボット点のみが移動していましたが、今ではすべての点が常に移動することになりました。

ここで一つ実用上の課題があります：「対称性」です。隣接する二つの三角形がある場合、テッセルレーションが逆向きに移動するとひび割れ（crack）が発生します。幸いにも、これは底面に対してテッセルレーションを鏡像（mirroring）することで解決できます。そしてこれにより、我々にとっての DirectX 11 の結果が得られます。

結論から言えば、これは AFAICT（As Far As I Can Tell）私の目で見れば、DirectX 11 で使用される「分数偶数テッセルレーション（fractional even tessellation）」のためのアルゴリズムです。我々は最初の問題（3 つのテッセルレーションファクターを与え、辺を分割する）を解決しました。次に求められているのは、これらのテッセルレーションファクターに従って三角形の内側を分割し、ポップ発生を回避するアルゴリズムを見つけることです。

最初のステップとして、元の三角形から始めて、それを 6 つのより小さな三角形に分割してみましょう。

内部のテッセルレーションファクターを用いて、通常の「三つ巴（triforce）」型のテッセルレーションを利用することで、6 つのテッセルレーションされた三角形領域を作成できます。

最も明白な問題は、これですべての 3 辺が全く同じテッセルレーションファクターを持っていることです。これは、単に最も外側の帯（strip）の三角形を破棄することで解決できます。

これからは、実際にポップが発生することなく、内部のテッセルレーションを外部のテッセルレーションと接続する必要があります。そのトリックは、元の 2 のべき乗という視点を持つことにあります。両テッセルレーションファクター以上かつ最小の 2 のべき乗を表す中間線（middle）を示し、左側（lhs）と右側（rhs）を中央に一致させます。ここでいう lhs テッセルレーションファクターは内部テッセルレーションであり、rhs テッセルレーションファクターはギャップの反対側に位置する辺テッセルレーションです。

その後、lhs から rhs へマッチングを行うことが可能になります。ただし、複数の_lhs_ の点が同じ_rhs_ の点を指し示す可能性があります。右側の各点について、逆方向に遡行して左側の点と接続することで逆側（reverse match）を見つけ出すことができます。

ギャップを三角形で埋めるには、lhs の各点について現在の rhs マッチと次の rhs マッチを見出し、rhs につながる三角形のファン（triangle fan）を追加し、さらに補完のために一つ追加された反転三角形を追加します。ただし、非常に最後の三角形はスキップすることを念頭に置いてください。青い三角形は、現在の_rhs_ マッチから次の_rhs_ マッチへの三角形ファンを示しており、赤い三角形はこのストリップを閉じるものです。

そして最後に、このマッチングアルゴリズムを使用して 6 つの三角形すべてのギャップを埋め込むことができます。

良い面と悪い面

このアルゴリズムにはいくつか非常に興味深い特性があります。このアプローチの主な利点は柔軟性です。辺のテッセルレーションファクターを計算する関数は任意に選択でき、それに応じてテッセルレーションが機能します。遷移が連続しているため、ポップが発生することなくスムーズな変化を実現できます。

反面、この柔軟性は理想的ではないパターンを生み出してしまうのです。したがって、それらについて見返し、クランプされた平行四辺形アプローチ（clamped parallelogram approach）を用いてどのように改善できるか検討しましょう。

多様なテッセルレーションファクター

仮に、高めのテッセルレーションファクターを持つ二つの辺と、低めのテッセルレーションファクターを持つ一つの辺があった場合です。これは細い三角形では非常に一般的です。理想的には、左側と右側を直接接続できるテッセルレーションパターンが望ましいのですが、単一の内部テッセルレーションファクターしか持っていないため、または過少テッセルレーションか、過剰テッセルレーションかのどちらかになります。

代わりに、この問題を解決するために、二つの高テッセルレーションファクターの辺を直接接続するテッセルーションパターンを作成できます。

非効率的なパターン

三角形を 6 つの類似した三角形領域に分割することで、必要以上の三角形を使用しています。

一方、クランプされた平行四辺形アプローチでは、3 つのテッセルレーションファクターがすべて同じ場合、トポロジ的に三つ巴（triforce）テッセルレーションと同等となります。ただし、間隔は不均一になりますが、これはポップなしでテッセルレーションファクターを補間できるようにするために不可欠です。

曲がり

テッセルレーションをデフォーメーションに使用する場合（これはテッセルレーションの最も魅力的な用途の一つです）、得られるテッセルレーションされたメッシュで鋭い弯曲が生じないようにするため、直線エッジループを維持するのが一般的です。元のメッシュがクォッドであれば、左から右へ向かうクリーンなエッジループを望む必要があります。理論的には、DirectX 11 クォッドプリミティブテッセルレーションを使用することも可能ですが、これは Blender の「Suzanne」のような三角形/クォッドの混在メッシュ（非常に一般的な形状）に関連する一連の問題を引き起こすことになります。

その代わりに、クランプされた平行四辺形パターンは、清潔なエッジループを備えた規則的なクォッドを作り出します。テッセルレーションファクターが互いに乖離すると、徐々に劣化する様子が観察できます。

最小三角形数

Fractional even の場合、最小限のテッセルレーションとして 6 つの三角形が必要となり、「これをオンにする」だけでコストに急激な飛躍が生じます。

一方、クランプされた平行四辺形テッセルレーションでは、一つの三角形から完全に遷移することができます。

動き（Movement）

DirectX 11 パターンは非常に「バウンスする」性質を持っています。これは実際にディスペースメントマッピングに使用される場合、鋭いエッジによりテッセルレーションファクターが動くにつれて可視的な往復振動（wobbling）を引き起こします。新しい関数は不平等な分布の犠牲になりますが、大幅に安定性が向上しています。

簡略化のために、ここでは Fractional even に焦点を当てています。最小三角形数の問題を回避するには Fractional odd を使用できますが、それにより動きの量が大変増加し、曲がりや非効率的なパターンの変化は生じません。Fractional odd テッセルレーションの実装を持っていませんが、そのアルゴリズムの本質的には各辺の中点を除去し、中点から「滑り出す」はずだった点は逆に外部から「滑り込む」という仕組みです。

線区間のテッセルレーション

実際のパターンを改善する前に、まずは線区間のテッセルレーションについて再考してみましょう。DirectX 11 のアルゴリズムは、スライドしている点以外のすべての点を均一な間隔にします。理論上は有益そうですが、動きによって実用上の問題が生じます。

我々がまず行うことは、実際には一つ後退することです。一点ずつ加えて新しい点を補間する以前の subdivision アルゴリズムに戻ります。両者の比較を示します。「バウンス」した動きの量を実際に感じ取れるでしょう。

興味深い点として、DirectX 11 テッセルレーションは収束しません。特に、中央の点のパスに注目してください。テッセルレーション値が 4 の場合、中点は 0.5 です。しかしテッセルレーションが進むにつれ、次の 2 つの点が下方に滑り込み、中点を 0.6667 に押し上げます。次にその点の上方から次の 2 つの点が滑り込んできて、8 つの点を持つ時点で再び 0.5 に戻ります。2 のべき乗ごとの各遷移の間、この中央点は 0.5 から 0.667 へ、そしてまた 0.5 へと変化するだけで収束しません。以下のグラフは、この補間の範囲内におけるテッセルレーションパターンの様子を示しています：

こちらが復元されたバージョンです。点の分布は劣っていますが、安定性に対してそれだけの価値があります。これが我々の新しい出発点となります。

別のアプローチを試してみましょう。一点ずつ点を追加するのではなく、偶数の点を追加する前にすべての奇数点を挿入します。辺の大きいの分布は同じですが、大小区と小区のバランスがより均一になります。

さらに改善するために、高いテッセルレーションをブロックに分割できます。例えば、64 から 128 に進むとき、新しい点が非常に速く追加されるため、技術的には連続的であってもポップのように見える場合があります。解決策は、領域をブロックに分割することで、各 2 のべき乗ごとに異なるトポロジーを持つ 4 つの領域を持つようにすることです。複数の点を同時に滑らせますが、動きはゆっくりしており、「ポップ」のように感じる急激な動きが発生する可能性は低くなります。

最後の調整として、単純な線区間からのテッセルレーションファクターから初期テッセルレーションファクターへの遷移をスムーズにしたいと考えています。テッセルレーションファクターを 1 から 2 へ遷移する場合、Fractional even は単に最小テッセルレーションファクター 2 にクリップされます。代わりに、両端点から中点で合うように滑り込んでくることができます。以下のスライダーを 1.0 と 2.0 の間に変更することで確認できます。

これにより、最終的な線テッセルレーションアルゴリズムが完成します。次は、内部の三角形テッセルレーションパターンに焦点を当てます。

ギャップとクランプされた平行四辺形

では、実際に三角形をどのようにテッセルレーションすべきでしょうか？この問題については多く時間を費やしましたが、最終的に到達した解決策は「クランプされた平行四辺形」でした。まず、底辺と左辺のテッセルレーションファクターを使用したバニラな平行四辺形から始めましょう。平行四辺形の各点について重心座標（barycentric coordinate）は以下の通りです：

float u = EdgeT(i, n0);
float v = EdgeT(j, n2);

実際にはかなり良く見えます。分布は直線的です。平行四辺形よりもより直線化することなどありません！しかし、平行四辺形は三角形ではありません。幸いなことに、この平行四辺形を三角形に変える簡単な方法があります：それらに「クリップ」を適用します。

float u = EdgeT(i, n0);
float v = EdgeT(j, n2);
u = min(u, 1 - v);

これで非常に直線的なパターンが得られ、それは三角形です（進展！）。しかし、左側と右側の辺は同じ値に拘束されています。このアルゴリズムを修正し、左右の辺に異なるテッセルレーションファクターを持たせる必要があります。

幸運なことに、DirectX 11 と同様のトリックを使用できます：ギャップをスキップして別々に処理します。ギャップは左辺と底辺のギャップの最大値として決定し、クリッピングラインを調整します。

float u = EdgeT(i, n0);
float v = EdgeT(j, n2);
u = min(u, 1 - (gap + v));

では、このギャップをどのようにマッチングすべきでしょうか？実は非常にシンプルです。以前と同じアルゴリズムを使用して_lhs_ から_rhs_ へマッチできます。ただし、頂部と底部を鏡像するのではなく、少し異なるバージョンを使用する必要があります。重要な洞察は、テッセルレーションファクターが増加するにつれて、新しい点が中央から滑り出すということです。下半分の場合、これは新しい点が上部から来ることを意味し、上半分の場合、新しい点が下部から来ることを意味します。lhs から_rhs_ へのマッチングでは、常に最初の三角形が_rhs_ 側を登るようにしたいので、三つ巴（triforce）テッセルレーションを作成できるためです。

そして最後に、これは同じマッチングパターンを三角形に変換したものです：

最後の詳細事項として、単純な三角形からこの新しいパターンへの遷移を扱う必要があります。最も簡単な方法は、内部点が v2 で始まるようにすることです。その後、テッセルレーションファクターが増加するにつれて、この点は v0/v1 の中点にスライドします。この遷移の間、パターンは基本的に三角形ファン（triangle fan）ですが、v2 における一つの例外があります。v2 上の三角形は重心点を触るべきではないため、三つ巴（triforce）テッセルレーションとシームレスに遷移できます。

したがって、ここでは三角形の 3 つの「タイプ」が存在します。Type 0 は単なる三角形です。Type 1 は三角形ファンであり、Type 2 はフルなテッセルレーションアルゴリズムです。

補足として、インデックスの順序について言及しておく必要があります。このアルゴリズムは WebGPU を対象としているため、SV_PrimitiveID サポートは保証されておらず、メッシュシェーダーは実用できません。そのため、一貫したプロバッキング vertex（誘発頂点）が必要です。これは内部点を倍にする必要があることを意味しますが、ギャップの両側の頂点は一度ずつしか使用されません。図では、濃い色のエッジがプロバッキング vertex です。

これにより、最終アルゴリズムが得られます：

クォッドとエッジループ

クォッドについては特別なケースも作れます。ソースプリミティブがクォッドの場合、それを 2 つの三角形に分割する必要があります。その後、各三角形の 3 辺すべてのテッセルレーションファクターを選択して自由にテッセルレーションできます。ただし、ソースがクォッドであることが分かっている場合、対角線が二つの辺の一つと同じテッセルレーションファクターを持つように「チート」することも可能です。この場合、対角線のテッセルレーションファクターは左側のエッジに強制されます。

対角線と左のエッジが同じテッセルレーションファクターであるため、水平なエッジループは直線的に保たれます。ほとんどの水平線は対角線を通過しても直線的に残り、垂直な線も概ね直線的です。

回転対称性

DirectX 11 テッセルレーションのもう一つの実質的に失われる特性が回転対称性です。DirectX 11 では、三角形を v0/v1/v2 から v1/v2/v0 に切り替えてもパターンは同一に見えます。しかし、クランプされた平行四辺形は常に v0/v1 と v0/v2 のエッジに沿っており、ギャップは常に v1/v2 を向いているため、この特性は失われます。最も単純なアプローチは、常に最小のエッジが v0/v2 であるように工夫することです。

インプリメンテーション

この記事全体で使用されている 2 つの対話型ビューアは、自立した HTML ページです。これらは直接開くことができ、見て、変更し、自由に利用できます。コードは MIT ライセンスで許可的ライセンスされています。

```
tess_visualizer.html
```
: 線テッセルレーションモードと Fractional even ビューアー
```
tess_patch_v18.html
```
: クランプされた平行四辺形ビューアーとマッチングモード

線

線を単純化するために、範囲を「トークン」に分割できます。テッセルレーションファクターが [1, 256] に変化しても、それを 25 つの具体的な範囲（トークン）に分割できます。浮動小数点数のテッセルレーションファクターはトークン ID と補間係数（lerp factor）に変換されます。その後、各トークンごとにポイントの開始値と終了値をテーブルに格納できます。これは非常に効率的にパッキングでき、開始点と終了点は 1 バイトで収まります。全体のテーブルサイズは 4k を超えません。

内部行

内部三角形の場合、直接平行四辺形をクリップすると半分近くが退化三角形（degenerate triangles）となります。したがって、各 e0/e2 のペアのトークンに対して、可能な最小のギャップ値と各行が持つことができる最大列数を決定できます。これらをテーブルに格納し、各行について最大列数と前和（prefix sum）を保存します。

逆引き検索

ギャップについては、e0 と e1 の各ペアに対してトポロジーを事前計算できます。トポロジーはギャップに沿って遡行して作られ、新しい三角形を左または右に追加することで生成されます。理論的には、三角形ごとに 1 ビットで保存することもできます。ただし、逆引き検索（reverse lookup）を行うことを望みます。代わりに、16 つの三角形の情報を 32 ビットにパッキングします。最初の 16 ビットは一方の側の三角形数を格納し、残りの 16 ビットはこのシーケンス用のビットマスクを格納します。その後、各三角形について_lhs_ の下インデックス、rhs の下インデックス、そして次の頂点が左にあるか右にあるかを抽出できます。

// One entry per (token1 * NT + token0) pair. NT = 25.
struct GapInfo {
    uint16_t m_gapStart;             // offset into m_gapData (u32-strided)
    uint16_t m_gapPrims;             // strip length = n0 + n1 - 1
    uint16_t m_rhsPrimLookupStart;
    uint16_t m_rhsPrimLookupNum;     // = n1
    uint16_t m_lhsPrimLookupStart;
    uint16_t m_lhsPrimLookupNum;     // = n0 - 1
    int8_t   m_lhsLastPrim;
};
extern GapInfo  g_gapInfo[NT * NT];
extern uint32_t g_gapData[];         // packed: hi16 = prefix sum, lo16 = bitmap

struct MatchData {
    uint16_t numBelowRhs;            // # RHS-advancing prims strictly below `prim`
    uint16_t numBelowLhs;            // # LHS-advancing prims strictly below `prim`
    bool     isRhs;                  // true  => new point on the RIGHT
                                     // false => new point on the LEFT
};

// O(1): one u32 load, two bit ops, one popcount.
MatchData LookupMatchData(Token tok0, Token tok1, uint32_t prim)
{
    const GapInfo& gi = g_gapInfo[tok1.m_table * NT + tok0.m_table];

    // 16 prim bits per u32 word.
    uint32_t word = g_gapData[gi.m_gapStart + (prim >> 4)];
    uint32_t bit  = prim & 0xF;

    uint32_t bitmap = word & 0xFFFFu;       // 1 = RHS-advancing prim
    uint32_t prefix = word >> 16;           // # RHS prims in earlier words

    uint32_t mask    = ~((1u << (16 - bit)) - 1u) & 0xFFFFu;
    uint32_t inGroup = popcount(bitmap & mask);

    MatchData md;
    md.numBelowRhs = uint16_t(prefix + inGroup);
    md.numBelowLhs = uint16_t(prim   - md.numBelowRhs);
    md.isRhs       = (word & (1u << (15 - bit))) != 0;
    return md;
}

逆引きトポロジー

内部ポイントのインデックスを見つけるために、逆引き検索（reverse lookup）が必要です。目的の三角形がどの行にあるか計算する必要があります。これには同じ基本プリミティブ（未満 16 ビットとマスク 16 ビット）を使用し、三角形情報と重心座標行情報を緊密にパッキングします。

パッチ内のグローバルプライムインデックスから、どの内部ストリップに属するかを見つけることができます。各ストリップの最後のプライムは 1 ビットでマークされ、前和が以下に格納されます。これらは合計約 637K です。

struct InteriorInfo {
    // ... other fields ...
    uint16_t m_reverseStripPackedStart;
    uint16_t m_reverseStripPackedNum;
    uint16_t m_reverseRowBaryStart;
    uint16_t m_reverseRowBaryNum;
};
extern InteriorInfo g_interiorInfo[NT * NT];

// hi16 = prefix sum (# strip-end bits in earlier words)
// lo16 = bitmap (1 bit per prim, '1' marks the last prim of a strip)
extern uint32_t g_interiorReverseStripPackedData[];

uint32_t GetStripIndexForPrim(Token tok0, Token tok2, uint32_t prim)
{
    const InteriorInfo& ii = g_interiorInfo[tok2.m_table * NT + tok0.m_table];

    uint32_t word   = g_interiorReverseStripPackedData[ii.m_reverseStripPackedStart + (prim >> 4)];
    uint32_t bit    = prim & 0xF;
    uint32_t bitmap = word & 0xFFFFu;
    uint32_t prefix = word >> 16;

    // Count strip-end bits at or before this prim within the current word.
    uint32_t mask = ~((1u << (16 - bit)) - 1u) & 0xFFFFu;
    return prefix + popcount(bitmap & mask);
}

重心座標は同様のレイアウトを使用し、各行の内部頂点ごとに 1 が設定されます。このデータは約 314K にパッキングされます。

// hi16 = prefix sum (# row-end bits in earlier words)
// lo16 = bitmap (1 bit per interior vertex, '1' marks the last vertex of a row)
extern uint32_t g_interiorReverseBaryPackedData[];

uint32_t GetRowIndexForBary(Token tok0, Token tok2, uint32_t bary)
{
    const InteriorInfo& ii = g_interiorInfo[tok2.m_table * NT + tok0.m_table];

    uint32_t word   = g_interiorReverseBaryPackedData[ii.m_reverseRowBaryStart + (bary >> 4)];
    uint32_t bit    = bary & 0xF;
    uint32_t bitmap = word & 0xFFFFu;
    uint32_t prefix = word >> 16;

    uint32_t mask = ~((1u << (16 - bit)) - 1u) & 0xFFFFu;
    return prefix + popcount(bitmap & mask);
}

これらのルックアップテーブルを使用することで、フルな逆引き検索のためのテーブルを 1.4MB 未満で保存し、最大テッセルレーションファクターとして 256 をサポートできます。もし低い最大テッセルレーションファクター（例：DirectX 11 ハードウェアテッセルレーションの 64 の値）を受け入れる場合、それはさらに小さくなります。

その他のアプローチ

いくつかの他のリアルタイムテッセルレーションアプローチについても言及しておく価値があります。UE5 では、Nanite テッセルレーションは整数テッセルレーションファクターを持つパターンの使用を採用しています。詳細については Brian Karis のブログ [1] をご参照ください。それは小さなテッセルレーションファクターに対してテーブルを保存し、大きなテッセルレーションファクターに対して反復的分割アプローチ（recursive splitting approach）を使用します。

Nanite テッセルレーションは整数テッセルレーションファクターを使用しており、テッセルレーションファクターの任意の変化によってポップが発生します。これに対し、DirectX 11 とクランプされた平行四辺形テッセルレーションはポップレスです。この要件が必要かどうかはあなた次第です。すべての物事と同様に、それは状況によります。Nanite の基本的な前提は、あなたの GPU がサブピクセル誤差でレンダリングできるほど高速であることを想定しています。Nanite テッセルレーションはテッセルレーションファクターが変更されるとポップしますが、小さな三角形であれば誤差は無視できます。これは映画業界で古くから続く考え方であり、当初の Reyes 論文 [7] にまで遡ります。

別の近年のリアルタイムアプローチとして、「Concurrent Binary Trees (CBTs)」[2]があります。CBT アルゴリズムは「最長辺二分法（longest edge bisection）」の上に構築されており、三角形を最も長い辺を半分に分けることで分割します。辺ごとにテッセルレーションファクターを適用するのではなく、最長辺二分法では再帰的な分割が必要であり、辺情報は単一のテッセルレーションファクターに還元できません。さらに、高いテッセルレーションファクターを持つ一つの三角形を分割する場合、T 接合（T-junction）を避けるために隣接する三角形のカスケード状の分割が必要になります。

結局のところ、Nanite テッセルレーションと CBTs の双方は興味深いアルゴリズムであり、それぞれのドメインに関連していますが、どちらもポップレス遷移を使用する浮動小数点数テッセルレーションファクターという自らの制限を満たしていません。

結論

クランプされた平行四辺形テッセルレーションは、連続的なポップレス三角形テッセルレーションアルゴリズムです。形状間の遷移中、エッジループを概ね直線的に保つことはできますが、追加の複雑性を犠牲にする必要があります。これらの利点が欠点に値するかどうかはあなた次第です。その問いについてさらに深く掘り下げたのは、次の投稿でこのアルゴリズムを使用して WebGPU でコキュートシェーダー（compute shaders）を使って実際にメッシュをテッセルレーションする際に扱われることになります。

参考文献

[1] How to Tessellate, Brian Karis (https://graphicrants.blogspot.com/2026/02/how-to-tessellate.html)
[2] Concurrent Binary Trees (with application to longest edge bisection), Jonathan Dupuy (https://onrendering.com/data/papers/cbt/ConcurrentBinaryTrees.pdf)
[3] Tessellation Stages, Microsoft (https://learn.microsoft.com/en-us/windows/win32/direct3d11/direct3d-11-advanced-stages-tessellation)
[4] DirectX 11 Terrain Tessellation, Iain Cantlay, NVIDIA (https://developer.download.nvidia.com/assets/gamedev/files/sdk/11/TerrainTessellation_WhitePaper.pdf)
[5] Tessellation Modes Quick Reference, Nathan Reed (https://www.reedbeta.com/blog/tess-quick-ref/)
[6] A Trip Through the Graphics Pipeline 2011, Part 12, Fabian Giesen (https://fgiesen.wordpress.com/2011/09/06/a-trip-through-the-graphics-pipeline-2011-part-12/)
[7] The Reyes Image Rendering Architecture, Robert L. Cook, Loren Carpenter, and Edwin Catmull (https://history.siggraph.org/learning/the-reyes-image-rendering-architecture-by-cook-carpenter-and-catmull/)