ワンダと巨像を遊んでいたら地形を作りたくなりました。

テッセレーション

https://msdn.microsoft.com/ja-jp/library/ee417841(v=vs.85).aspx
http://www.nvidia.co.jp/object/tessellation_jp.html

テッセレーションはシェーダーパイプラインのステージの一つで,パッチと呼ばれる1つの面を複数の面に分割します。頂点シェーダーの後,ピクセルシェーダーの前に実行されます。
例えば四角形のパッチを分割する場合,ハルシェーダーで4つエッジと,四角形の内部のXYについての分割数を指定して, テッセレーターが分割した結果をドメインシェーダーで加工してからピクセルシェーダーに渡します。

f:id:hikita12312:20180224194636p:plain:w400

テッセレーションを地形に使うことで,地形の詳細度を動的に計算して,必要な部分だけ三角形をたくさん生成することで, レンダリングの負荷を下げつつ,滑らかな地形を表現しようということです。

Height Map/Normal Map

まず,地形の元データーである,高さマップと法線マップを作成します。

Height Map	Normal Map

高さマップはパーリンノイズとフラクタルブラウン運動で作成しました。 http://mrl.nyu.edu/~perlin/noise/
https://thebookofshaders.com/13/

法線マップは高さマップから,隣接する高さの差分を利用して変分すれば作れます

${ \displaystyle \begin{eqnarray} \Delta_x y(x,z) &=& \frac{h(x+1, z) - h(x-1, z)}{2 \Delta x} \\ \Delta_z y(x,z) &=& \frac{h(x, z+1) - h(x, z-1)}{2 \Delta z} \\ {\bf u} &=& (1, \Delta_x y(x,z), 0) \\ {\bf v} &=& (0, \Delta_z y(x,z), 1) \\ {\bf n} &=& \frac{{\bf u}}{|{\bf u}|} \times \frac{{\bf v}}{|{\bf v}|} \end{eqnarray} }$

分割度マップ

先程のHeightMapで表される地形は,32x32個のパッチで表現される地形であるとします。それぞれのパッチの地形分割度に対応した値を格納した32x32サイズのテクスチャを地形分割度マップとして作成します。

まずは距離適応型のテッセレーションとして,単純にカメラから近い地形ほど分割度が増えるようにしてみます。

クリックで展開

// 適当に作ったスパースな平均サンプルパターン
// □□□□□□□□□□□
// □□■□□□□□□□□
// □□□□□□□□□■□
// □□□□□□■□□□□
// □□□■□□□□□□□
// □□□□□☆□□□□□
// □□□□□□□■□□□
// □□□□■□□□□□□
// □■□□□□□□□□□
// □□□□□□□□■□□
// □□□□□□□□□□□
static const uint s_MeanSampleNum = 8;
static const float2 s_aMeanSampleOffset[s_MeanSampleNum] =
{
    float2(1.0f,2.0f)/11.0f , float2(-1.0f,-2.0f)/ 11.0f, float2(2.0f,-1.0f)/ 11.0f, float2(-2.0f, 1.0f)/ 11.0f,
    float2(4.0f,3.0f)/ 11.0f, float2(3.0f,4.0f)/ 11.0f, float2(-3.0f,4.0f)/ 11.0f,  float2(-4.0f, 3.0f)/ 11.0f
};
    
float PS_Create(VS_OUT In) : SV_TARGET0
{
    const float2 uv = In.UV.xy;

    // HeightMap値のサンプリング
    float3 aSampleNormal[s_MeanSampleNum];
    // 高さはサンプリングの平均値を利用する
    float height = 0.0f;
    [unroll]
    for (uint i = 0; i < s_MeanSampleNum; ++i)
    {
        // RGB : normal, A : Height
        const float4 heightValue = SampleTextureLevel0(g_HeightMap, g_Sampler, uv + s_aMeanSampleOffset[i] * PIXEL_SIZE);
        height += heightValue.w;
        aSampleNormal[i] = heightValue.xyz;
    }
    height /= s_MeanSampleNum;

    // ワールド空間位置
    float3 worldPosition = float3(uv.x, height, uv.y);
    worldPosition.xz = CHUNK_POSTION_SCALE_XZ * worldPosition.xz + CHUNK_POSTION_OFFSET_XZ;
    // View空間位置
    const float3 viewPosition = Transform(VIEW_MATRIX, float4(worldPosition.xyz, 1.0f)).xyz;
    // カメラまでの距離
    const float d = length(viewPosition);
    // 分割数
    float tessFactor =　DISTANCE_FACTOR_SCALE * pow(d, DISTANCE_FACTOR_POWER);
    tessFactor = clamp(tessFactor, 1.0f, 63.0f);
    return tessFactor;
}

実際に出来上がった分割度マップです。

f:id:hikita12312:20180224112208p:plain:w300

赤い色ほど,パッチの分割数が多い事を示しています。カメラに近い場所ほど赤色になり,カメラからは遠い場所は黒色になります。

地形のテッセレーション

なぜ,わざわざ分割度マップを別パスで作成したかというと,テッセレーションのパッチ間のエッジの切れ目を滑らかに接続するためです。単純に分割数を各パッチに割り当てるだけだと,隣接するパッチの分割数が異なるときに,その境界が正しく接続しません。
そこで,1パス目で分割度を計算してから,注目するパッチと隣接するパッチの分割度の平均値を,注目するパッチのエッジの分割度として指定します。こうすることで,隣接し合うパッチの境界の分割度は互いに一致するので,エッジの切れ目は作られないことになります。

f:id:hikita12312:20180224200410p:plain:w500

実際に分割してみます。テッセレーション部分のコードの概略は以下です。注目するパッチとその上下左右のパッチの分割度を取得するために,Gather命令を利用しているのが工夫ポイントです。

クリックで展開

// -------------------------------------------------------------------------------------------------------
// HS
HS_CONSTANT_OUT HS_Terrain_Constant(InputPatch<VS_OUT, INPUT_PATCH_SIZE> In)
{
    const float2 patchUV = (In[0].Position.xy + In[2].Position.xy) * 0.5f;

    // テッセレーションファクタの計算
    float center, top, bottom, right, left;
    {
        // 中央と上下左右のファクタを取得
        float3 vec = GatherTexture(g_TessFactorMap, g_PointSampler, patchUV - TESS_FACTOR_OFFSET).xyz;
        center = (vec.x);
        left = (vec.y);
        top = (vec.z);
        vec.yz = GatherTexture(g_TessFactorMap, g_PointSampler, patchUV + TESS_FACTOR_OFFSET).yz;
        bottom = (vec.y);
        right = (vec.z);
    }

    HS_CONSTANT_OUT Out = (HS_CONSTANT_OUT)0;
    Out.aEdgeFactor[0] = (center + left) * 0.5f;
    Out.aEdgeFactor[1] = (center + bottom) * 0.5f;
    Out.aEdgeFactor[2] = (center + right) * 0.5f;
    Out.aEdgeFactor[3] = (center + top) * 0.5f;
    Out.aInsideFactor[0] = center;
    Out.aInsideFactor[1] = Out.aInsideFactor[0];
    return Out;
}

[domain("quad")]
[partitioning("fractional_odd")]
[outputtopology("triangle_cw")]
[outputcontrolpoints(OUTPUT_PATCH_SIZE)]
[patchconstantfunc("HS_Terrain_Constant")]
VS_OUT HS_Terrain(InputPatch<VS_OUT, INPUT_PATCH_SIZE> In, uint pointId : SV_OutputControlPointID)
{
    VS_OUT Out = (VS_OUT)0;
    Out.Position = In[pointId].Position;
    return Out;
}

// -------------------------------------------------------------------------------------------------------
// DS

float2 LerpPosition(OutputPatch<VS_OUT, OUTPUT_PATCH_SIZE> outputPatch, float2 uv)
{
    const float2 left = lerp(outputPatch[0].Position, outputPatch[1].Position, uv.y);
    const float2 right = lerp(outputPatch[3].Position, outputPatch[2].Position, uv.y);
    return lerp(left, right, uv.x);
}

[domain("quad")]
DS_OUT DS_Terrain(HS_CONSTANT_OUT inputConstant, float2 uv : SV_DomainLocation, OutputPatch<VS_OUT, OUTPUT_PATCH_SIZE> outputPatch)
{
    const float tessFactor = inputConstant.aInsideFactor[0];
    const float2 fetchUV = LerpPosition(outputPatch, uv);
    const float4 heightMapValue = SampleTextureLevel0(g_HeightMap, g_LinearSampler, fetchUV).rgba;
    const float height = heightMapValue.w;
    float4 pos = float4(fetchUV.x, height, fetchUV.y, 1.0f);
    pos.xz = CHUNK_POSTION_SCALE * pos.xz + CHUNK_POSTION_OFFSET;
    pos = Transform(VIEW_PROJECTION_MATRIX, pos);

    DS_OUT Out = (DS_OUT)0;
    Out.Position = pos;
    // ...
    return Out;
}

分割して,レンダリングをした結果が以下のものです。

f:id:hikita12312:20180224114028p:plain:w600

輪郭検出

単純に距離だけで分割度を決定すると,遠くの山の輪郭がカクカクとしたものになってしまいます。そこで,輪郭となりうる度合いも分割度マップの計算に取り入れてみます。

クリックで展開

static const uint s_MeanSampleNum = 8;
static const float2 s_aMeanSampleOffset[s_MeanSampleNum] =
{
    float2(1.0f,2.0f)/11.0f , float2(-1.0f,-2.0f)/ 11.0f, float2(2.0f,-1.0f)/ 11.0f, float2(-2.0f, 1.0f)/ 11.0f,
    float2(4.0f,3.0f)/ 11.0f, float2(3.0f,4.0f)/ 11.0f, float2(-3.0f,4.0f)/ 11.0f,  float2(-4.0f, 3.0f)/ 11.0f
};
    
float PS_Create(VS_OUT In) : SV_TARGET0
{
    const float2 uv = In.UV.xy;

    // HeightMap値のサンプリング
    float3 aSampleNormal[s_MeanSampleNum];
    // 高さはサンプリングの平均値を利用する
    float height = 0.0f;
    [unroll]
    for (uint i = 0; i < s_MeanSampleNum; ++i)
    {
        const float4 heightValue = SampleTextureLevel0(g_HeightMap, g_Sampler, uv + s_aMeanSampleOffset[i] * PIXEL_SIZE);
        height += heightValue.w;
        aSampleNormal[i] = heightValue.xyz;
    }
    height /= s_MeanSampleNum;

    // ワールド空間位置
    float3 worldPosition = float3(uv.x, height, uv.y);
    worldPosition.xz = CHUNK_POSTION_SCALE_XZ * worldPosition.xz + CHUNK_POSTION_OFFSET_XZ;
    // View空間位置
    const float3 viewPosition = Transform(VIEW_MATRIX, float4(worldPosition.xyz, 1.0f)).xyz;
    // カメラまでの距離
    const float d = length(viewPosition);
    // カメラ方向の単位ベクトル
    const float3 toCameraVec = -viewPosition / d;
    [unroll]
    for (uint i = 0; i < s_MeanSampleNum; ++i)
    {
        // カメラまでの方向と法線ベクトルの内積
        const float cos = dot(aSampleNormal[i], toCameraVec);
        // cos * cos
        cos2 = min(cos2, cos*cos);
    }

    // 法線ファクタ
    float normalFactor = (1.0f - cos2); // 0~90度を0.0~1.0で表す。実質sin^2
    // 60度のときの法線ファクタ sin^2(60 deg)
    const float NORMAL_FACTOR_THRESHOLD = 0.75f;
    // 法線ファクタを60度の閾値に合わせて60~90度で0~1とする
    normalFactor = max(normalFactor - NORMAL_FACTOR_THRESHOLD, 0.0f) / (1.0f - NORMAL_FACTOR_THRESHOLD);
    // 分割数
    float tessFactor = DISTANCE_FACTOR_SCALE * pow(d, DISTANCE_FACTOR_POWER) * (1.0f + NORMAL_FACTOR_SCALE*normalFactor);
    tessFactor = clamp(tessFactor, 1.0f, 63.0f);
}

サンプリング点の法線と,サンプリング点からカメラに向かうベクトルの内積を見て輪郭になりうるかの度合いを組み込んでいます。

輪郭検出なし	輪郭検出あり

輪郭検出なし	輪郭検出あり

輪郭検出をいれると,全体的に分割度が上昇するバイアスはかかりますが,カメラ方向に法線が向いているパッチの分割はそのままなのがわかります。

結果

輪郭検出も入れた結果です。

f:id:hikita12312:20180224115302p:plain:w600

輪郭検出の有りと無しの比較です

輪郭検出なし	輪郭検出あり

輪郭検出なし	輪郭検出あり

まあそれっぽい気がします。

視錐台カリング

画面に映っていないパッチに対してテッセレーションを行うことは無駄になります。
その為,透視投影をした時に幾何的に画面に表示されないパッチの分割処理をスキップするような処理を入れると多少高速化されます。 ...が実装はしたのですが,パッチのAABBが上手に計算できていないためか視錐台のnear平面あたりでイマイチ不安定なので現在は利用していません。そのうち修正します。