自己皇帝感

をください

TextMeshProにDepthOfFieldを正しくかける

2023.2.22f1 urp 16.0.6

動機

TMPオブジェクトがある状態でBokehポストプロセスを書けると、TMPオブジェクトの奥にあるオブジェクトの深度でボケがかかる

TMPエフェクトのかかり具合をTMPオブジェクトの深度を参照して意図通りかかるようにしたい

調査

そもそもTMPオブジェクトは透明扱いで深度が描かれない github.com

だからといって単にZWrite Onしてもボケが正しくかかるようにはならない

なぜならボケエフェクトはCameraDepthTextureを参照するので、意図通りのことをするには、CameraDepthTextureにTMPの深度を書かないといけない github.com

_CameraDepthTextureを作成しているのはDepthOnlyPassだったりDepthOnlyNormalPassだったりする。

DepthOnlyPass.cs:L133

DepthNormalOnlyPass.cs:L210

どちらのPassが実行されるかは複雑な条件によって決まる

UniversalRenderer.cs:L578

UniversalRenderer.cs:L630

UniversalRenderer.cs:L944

今回はDepthNormalPrepassが実行されていたので、TMPのシェーダーにDepthNormalsPassを追加する必要がある

TMPのシェーダーを改造し、Passを2つ用意して、一方のPassのLightMode="DepthNormals"にする

Shader "TextMeshPro/Distance Field ZWrite" {

Properties {
    _FaceTex            ("Face Texture", 2D) = "white" {}
    _FaceUVSpeedX       ("Face UV Speed X", Range(-5, 5)) = 0.0
    _FaceUVSpeedY       ("Face UV Speed Y", Range(-5, 5)) = 0.0
    _FaceColor          ("Face Color", Color) = (1,1,1,1)
    _FaceDilate         ("Face Dilate", Range(-1,1)) = 0

    _OutlineColor       ("Outline Color", Color) = (0,0,0,1)
    _OutlineTex         ("Outline Texture", 2D) = "white" {}
    _OutlineUVSpeedX    ("Outline UV Speed X", Range(-5, 5)) = 0.0
    _OutlineUVSpeedY    ("Outline UV Speed Y", Range(-5, 5)) = 0.0
    _OutlineWidth       ("Outline Thickness", Range(0, 1)) = 0
    _OutlineSoftness    ("Outline Softness", Range(0,1)) = 0

    _Bevel              ("Bevel", Range(0,1)) = 0.5
    _BevelOffset        ("Bevel Offset", Range(-0.5,0.5)) = 0
    _BevelWidth         ("Bevel Width", Range(-.5,0.5)) = 0
    _BevelClamp         ("Bevel Clamp", Range(0,1)) = 0
    _BevelRoundness     ("Bevel Roundness", Range(0,1)) = 0

    _LightAngle         ("Light Angle", Range(0.0, 6.2831853)) = 3.1416
    _SpecularColor      ("Specular", Color) = (1,1,1,1)
    _SpecularPower      ("Specular", Range(0,4)) = 2.0
    _Reflectivity       ("Reflectivity", Range(5.0,15.0)) = 10
    _Diffuse            ("Diffuse", Range(0,1)) = 0.5
    _Ambient            ("Ambient", Range(1,0)) = 0.5

    _BumpMap            ("Normal map", 2D) = "bump" {}
    _BumpOutline        ("Bump Outline", Range(0,1)) = 0
    _BumpFace           ("Bump Face", Range(0,1)) = 0

    _ReflectFaceColor   ("Reflection Color", Color) = (0,0,0,1)
    _ReflectOutlineColor("Reflection Color", Color) = (0,0,0,1)
    _Cube               ("Reflection Cubemap", Cube) = "black" { /* TexGen CubeReflect */ }
    _EnvMatrixRotation  ("Texture Rotation", vector) = (0, 0, 0, 0)


    _UnderlayColor      ("Border Color", Color) = (0,0,0, 0.5)
    _UnderlayOffsetX    ("Border OffsetX", Range(-1,1)) = 0
    _UnderlayOffsetY    ("Border OffsetY", Range(-1,1)) = 0
    _UnderlayDilate     ("Border Dilate", Range(-1,1)) = 0
    _UnderlaySoftness   ("Border Softness", Range(0,1)) = 0

    _GlowColor          ("Color", Color) = (0, 1, 0, 0.5)
    _GlowOffset         ("Offset", Range(-1,1)) = 0
    _GlowInner          ("Inner", Range(0,1)) = 0.05
    _GlowOuter          ("Outer", Range(0,1)) = 0.05
    _GlowPower          ("Falloff", Range(1, 0)) = 0.75

    _WeightNormal       ("Weight Normal", float) = 0
    _WeightBold         ("Weight Bold", float) = 0.5

    _ShaderFlags        ("Flags", float) = 0
    _ScaleRatioA        ("Scale RatioA", float) = 1
    _ScaleRatioB        ("Scale RatioB", float) = 1
    _ScaleRatioC        ("Scale RatioC", float) = 1

    _MainTex            ("Font Atlas", 2D) = "white" {}
    _TextureWidth       ("Texture Width", float) = 512
    _TextureHeight      ("Texture Height", float) = 512
    _GradientScale      ("Gradient Scale", float) = 5.0
    _ScaleX             ("Scale X", float) = 1.0
    _ScaleY             ("Scale Y", float) = 1.0
    _PerspectiveFilter  ("Perspective Correction", Range(0, 1)) = 0.875
    _Sharpness          ("Sharpness", Range(-1,1)) = 0

    _VertexOffsetX      ("Vertex OffsetX", float) = 0
    _VertexOffsetY      ("Vertex OffsetY", float) = 0

    _MaskCoord          ("Mask Coordinates", vector) = (0, 0, 32767, 32767)
    _ClipRect           ("Clip Rect", vector) = (-32767, -32767, 32767, 32767)
    _MaskSoftnessX      ("Mask SoftnessX", float) = 0
    _MaskSoftnessY      ("Mask SoftnessY", float) = 0

    _StencilComp        ("Stencil Comparison", Float) = 8
    _Stencil            ("Stencil ID", Float) = 0
    _StencilOp          ("Stencil Operation", Float) = 0
    _StencilWriteMask   ("Stencil Write Mask", Float) = 255
    _StencilReadMask    ("Stencil Read Mask", Float) = 255

    _CullMode           ("Cull Mode", Float) = 0
    _ColorMask          ("Color Mask", Float) = 15
}

SubShader {

    CGINCLUDE
    #pragma target 3.0
    #pragma shader_feature __ BEVEL_ON
    #pragma shader_feature __ UNDERLAY_ON UNDERLAY_INNER
    #pragma shader_feature __ GLOW_ON

    #pragma multi_compile __ UNITY_UI_CLIP_RECT
    #pragma multi_compile __ UNITY_UI_ALPHACLIP

    #include "UnityCG.cginc"
    #include "UnityUI.cginc"
    #include "../../TextMesh Pro/Resources/Shaders/TMPro_Properties.cginc"
    #include "../../TextMesh Pro/Resources/Shaders/TMPro.cginc"

    struct vertex_t
    {
        UNITY_VERTEX_INPUT_INSTANCE_ID
        float4  position        : POSITION;
        float3  normal          : NORMAL;
        fixed4  color           : COLOR;
        float4  texcoord0       : TEXCOORD0;
        float2  texcoord1       : TEXCOORD1;
    };

    struct pixel_t
    {
        UNITY_VERTEX_INPUT_INSTANCE_ID
        UNITY_VERTEX_OUTPUT_STEREO
        float4  position        : SV_POSITION;
        fixed4  color           : COLOR;
        float2  atlas           : TEXCOORD0;        // Atlas
        float4  param           : TEXCOORD1;        // alphaClip, scale, bias, weight
        float4  mask            : TEXCOORD2;        // Position in object space(xy), pixel Size(zw)
        float3  viewDir         : TEXCOORD3;

        #if (UNDERLAY_ON || UNDERLAY_INNER)
        float4  texcoord2       : TEXCOORD4;        // u,v, scale, bias
        fixed4  underlayColor   : COLOR1;
        #endif

        float4 textures         : TEXCOORD5;
    };

    // Used by Unity internally to handle Texture Tiling and Offset.
    float4 _FaceTex_ST;
    float4 _OutlineTex_ST;
    float _UIMaskSoftnessX;
    float _UIMaskSoftnessY;
    int _UIVertexColorAlwaysGammaSpace;

    pixel_t VertShader(vertex_t input)
    {
        pixel_t output;

        UNITY_INITIALIZE_OUTPUT(pixel_t, output);
        UNITY_SETUP_INSTANCE_ID(input);
        UNITY_TRANSFER_INSTANCE_ID(input,output);
        UNITY_INITIALIZE_VERTEX_OUTPUT_STEREO(output);

        float bold = step(input.texcoord0.w, 0);

        float4 vert = input.position;
        vert.x += _VertexOffsetX;
        vert.y += _VertexOffsetY;

        float4 vPosition = UnityObjectToClipPos(vert);

        float2 pixelSize = vPosition.w;
        pixelSize /= float2(_ScaleX, _ScaleY) * abs(mul((float2x2)UNITY_MATRIX_P, _ScreenParams.xy));
        float scale = rsqrt(dot(pixelSize, pixelSize));
        scale *= abs(input.texcoord0.w) * _GradientScale * (_Sharpness + 1);
        if (UNITY_MATRIX_P[3][3] == 0) scale = lerp(abs(scale) * (1 - _PerspectiveFilter), scale, abs(dot(UnityObjectToWorldNormal(input.normal.xyz), normalize(WorldSpaceViewDir(vert)))));

        float weight = lerp(_WeightNormal, _WeightBold, bold) / 4.0;
        weight = (weight + _FaceDilate) * _ScaleRatioA * 0.5;

        float bias =(.5 - weight) + (.5 / scale);

        float alphaClip = (1.0 - _OutlineWidth * _ScaleRatioA - _OutlineSoftness * _ScaleRatioA);

        #if GLOW_ON
        alphaClip = min(alphaClip, 1.0 - _GlowOffset * _ScaleRatioB - _GlowOuter * _ScaleRatioB);
        #endif

        alphaClip = alphaClip / 2.0 - ( .5 / scale) - weight;

        #if (UNDERLAY_ON || UNDERLAY_INNER)
        float4 underlayColor = _UnderlayColor;
        underlayColor.rgb *= underlayColor.a;

        float bScale = scale;
        bScale /= 1 + ((_UnderlaySoftness*_ScaleRatioC) * bScale);
        float bBias = (0.5 - weight) * bScale - 0.5 - ((_UnderlayDilate * _ScaleRatioC) * 0.5 * bScale);

        float x = -(_UnderlayOffsetX * _ScaleRatioC) * _GradientScale / _TextureWidth;
        float y = -(_UnderlayOffsetY * _ScaleRatioC) * _GradientScale / _TextureHeight;
        float2 bOffset = float2(x, y);
        #endif

        // Generate UV for the Masking Texture
        float4 clampedRect = clamp(_ClipRect, -2e10, 2e10);
        float2 maskUV = (vert.xy - clampedRect.xy) / (clampedRect.zw - clampedRect.xy);

        // Support for texture tiling and offset
        float2 textureUV = input.texcoord1;
        float2 faceUV = TRANSFORM_TEX(textureUV, _FaceTex);
        float2 outlineUV = TRANSFORM_TEX(textureUV, _OutlineTex);


        if (_UIVertexColorAlwaysGammaSpace && !IsGammaSpace())
        {
            input.color.rgb = UIGammaToLinear(input.color.rgb);
        }
        output.position = vPosition;
        output.color = input.color;
        output.atlas =  input.texcoord0;
        output.param =  float4(alphaClip, scale, bias, weight);
        const half2 maskSoftness = half2(max(_UIMaskSoftnessX, _MaskSoftnessX), max(_UIMaskSoftnessY, _MaskSoftnessY));
        output.mask = half4(vert.xy * 2 - clampedRect.xy - clampedRect.zw, 0.25 / (0.25 * maskSoftness + pixelSize.xy));
        output.viewDir =    mul((float3x3)_EnvMatrix, _WorldSpaceCameraPos.xyz - mul(unity_ObjectToWorld, vert).xyz);
        #if (UNDERLAY_ON || UNDERLAY_INNER)
        output.texcoord2 = float4(input.texcoord0 + bOffset, bScale, bBias);
        output.underlayColor =  underlayColor;
        #endif
        output.textures = float4(faceUV, outlineUV);

        return output;
    }


    fixed4 PixShader(pixel_t input) : SV_Target
    {
        UNITY_SETUP_INSTANCE_ID(input);

        float c = tex2D(_MainTex, input.atlas).a;

        #ifndef UNDERLAY_ON
        clip(c - input.param.x);
        #endif

        float   scale   = input.param.y;
        float   bias    = input.param.z;
        float   weight  = input.param.w;
        float   sd = (bias - c) * scale;

        float outline = (_OutlineWidth * _ScaleRatioA) * scale;
        float softness = (_OutlineSoftness * _ScaleRatioA) * scale;

        half4 faceColor = _FaceColor;
        half4 outlineColor = _OutlineColor;

        faceColor.rgb *= input.color.rgb;

        faceColor *= tex2D(_FaceTex, input.textures.xy + float2(_FaceUVSpeedX, _FaceUVSpeedY) * _Time.y);
        outlineColor *= tex2D(_OutlineTex, input.textures.zw + float2(_OutlineUVSpeedX, _OutlineUVSpeedY) * _Time.y);

        faceColor = GetColor(sd, faceColor, outlineColor, outline, softness);

        #if BEVEL_ON
        float3 dxy = float3(0.5 / _TextureWidth, 0.5 / _TextureHeight, 0);
        float3 n = GetSurfaceNormal(input.atlas, weight, dxy);

        float3 bump = UnpackNormal(tex2D(_BumpMap, input.textures.xy + float2(_FaceUVSpeedX, _FaceUVSpeedY) * _Time.y)).xyz;
        bump *= lerp(_BumpFace, _BumpOutline, saturate(sd + outline * 0.5));
        n = normalize(n- bump);

        float3 light = normalize(float3(sin(_LightAngle), cos(_LightAngle), -1.0));

        float3 col = GetSpecular(n, light);
        faceColor.rgb += col*faceColor.a;
        faceColor.rgb *= 1-(dot(n, light)*_Diffuse);
        faceColor.rgb *= lerp(_Ambient, 1, n.z*n.z);

        fixed4 reflcol = texCUBE(_Cube, reflect(input.viewDir, -n));
        faceColor.rgb += reflcol.rgb * lerp(_ReflectFaceColor.rgb, _ReflectOutlineColor.rgb, saturate(sd + outline * 0.5)) * faceColor.a;
        #endif

        #if UNDERLAY_ON
        float d = tex2D(_MainTex, input.texcoord2.xy).a * input.texcoord2.z;
        faceColor += input.underlayColor * saturate(d - input.texcoord2.w) * (1 - faceColor.a);
        #endif

        #if UNDERLAY_INNER
        float d = tex2D(_MainTex, input.texcoord2.xy).a * input.texcoord2.z;
        faceColor += input.underlayColor * (1 - saturate(d - input.texcoord2.w)) * saturate(1 - sd) * (1 - faceColor.a);
        #endif

        #if GLOW_ON
        float4 glowColor = GetGlowColor(sd, scale);
        faceColor.rgb += glowColor.rgb * glowColor.a;
        #endif

    // Alternative implementation to UnityGet2DClipping with support for softness.
        #if UNITY_UI_CLIP_RECT
        half2 m = saturate((_ClipRect.zw - _ClipRect.xy - abs(input.mask.xy)) * input.mask.zw);
        faceColor *= m.x * m.y;
        #endif

        clip(faceColor.a - 0.001);

        return faceColor * input.color.a;
    }
    ENDCG

    Tags
    {
        "Queue"="AlphaTest"
        "IgnoreProjector"="True"
        "RenderType"="TransparentCutout"
    }

    Stencil
    {
        Ref [_Stencil]
        Comp [_StencilComp]
        Pass [_StencilOp]
        ReadMask [_StencilReadMask]
        WriteMask [_StencilWriteMask]
    }

    Cull [_CullMode]
    ZWrite On
    Lighting Off
    Fog { Mode Global }
    ZTest LEqual
    ColorMask [_ColorMask]

    Pass {
        CGPROGRAM
        #pragma target 3.0
        #pragma vertex VertShader
        #pragma fragment PixShader
        ENDCG
    }


    Pass {

        Name "DepthNormals"
        Tags
        {
            "LightMode" = "DepthNormals"
        }
        CGPROGRAM
        #pragma target 3.0
        #pragma vertex VertShader
        #pragma fragment PixShader_Normal
        fixed4 PixShader_Normal(pixel_t input) : SV_Target
        {
            PixShader(input); //通常描画とほぼ同じ処理をしてclip判定を行わせる
            return fixed4(0, 0, 0, 1); //とりあえず法線を0にしておく
        }
        ENDCG
    }
}

Fallback "TextMeshPro/Mobile/Distance Field"
CustomEditor "TMPro.EditorUtilities.TMP_SDFShaderGUI"
}ca

結果

TMPオブジェクトの深度を_CameraDepthTextureに渡せたのでボケが正しくきくようになった

蟻本 Face the Right Way

牛の前後 <-> オセロ駒の白黒 としてとらえた。
flipN は 「N番目の駒を左端にして範囲Kの領域の駒をひっくり返す」という操作を表す 駒列をすべて白にするとき、「黒が見つかり次第その黒を左端として範囲Kでflip」の繰り返しがなぜ最短手順になるか考えてみる

駒列の先頭が決まっているときに以下が主張できる

 P1B「黒...、のとき最短手順で先頭のflipを一つだけ含む」
    先頭を変えられるflipはflip1しかない。flip1の回数だけ先頭の駒の色が変わるので、全て白になったときflip1は奇数しかありえない
    flip列から同一flipを削除しても結果は変わらないので、最短手順ではflip1は1つだけ含まれる

 P1W「白...のとき、最短手順は先頭のflipを含まない」
    最短手順の中にflip1番がある場合、1番目の白を変えるには再度flip1が最短手順の中に含まれていないといけない
    最終的に1番目の白が白に戻るにはflip1番目が偶数個はいってないといけないが、同じflipが偶数個入っているものは最短手順になりえない
    よって最終手順の中にflip1番は存在しない

駒列の先頭2つが決まっているときに以下が主張できる

 P2B「白黒...の時、最短手順に1つめまでの白を左端とするflipは存在せず、K番目の黒を左端とするflipが1つだけ含まれる」
    a. 1番目が白なのでP1Wより、最短手順にflip1は含まれない
    b. よって最短手順の中で2番目の黒を変えているflipはflip2のみである
       最終的に2番目の黒が白になるにはflip2が奇数回おきる必要があり、最短手順ではflip2を1つだけ含む

 P2W「白白...の時、最短手順にこれら2つを左端とするflipは含まれない」
    a. 1番目が白なのでP1Wより、最短手順にflip1は含まれない
    b. 最短手順の中で2番目の白が1度以上変わると仮定したとき、最終的に2番目の白が白に戻るにはflip2は偶数回含まれなければならない
       同じflipが偶数個入っているものは最短手順になりえないので仮定が誤っていて、flip2は最終手順に含まれない
    c. a,bより2番目までの白のいずれかを左端とするflipは最短手順に含まれない

これを続けていくと以下のように一般化できる
白K-1黒... は、白がK-1連続した後黒が続く、という意味

 PKB「白K-1黒...の時、最短手順にK個目までの白を左端とするflipは存在せず、K番目の黒を左端とするflipが1つだけ含まれる」
    a. 1~K-1番目が白なのでP1W~PK~1Wより、最短手順に1~K-1番目までの白のいずれかを左端とするflipは含まれない
    b. よって最短手順の中でK番目の黒を変えているflipはflipKのみである
       最終的にK番目の黒が白になるにはflipKが奇数回おきる必要があり、最短手順ではflipKを1つだけ含む

 PKW「白K-1白...の時、最短手順にこれら2つを左端とするflipは含まれない」
    a. 1~K-1番目が白なのでP1W~PK~1Wより、最短手順に1~K-1番目までの白のいずれかを左端とするflipは含まれない
    b. 最短手順の中でK番目の白が1度以上変わると仮定したとき、最終的にK番目の白が白に戻るにはflipKは偶数回含まれなければならない
       同じflipが偶数個入っているものは最短手順になりえないので仮定が誤っていて、flipKは最終手順に含まれない
    c. 1,2よりK番目までの白のいずれかを左端とするflipは最短手順に含まれない

結局駒列sにをすべて白にする手順が存在する場合、その最短手順Mについて

M(s0) = 1 + M(s1)   (s1はs0のうち最初に現れる黒を左端とするflipを行ったもの)
        = 1 + 1 + M(s2)  (s2はs1のうち以下略)
        = ...

と出来て、skはkが増えるたびに先頭から続く白の個数が多くなっていいき、ある回数mでsm=すべての駒が白 となりM(sm) = 0 で計算が止まる

蟻本 最長共通部分列 漸化式考察

問題: 蟻本56p

dp[i+1][j+1] = dp[i][j] + 1 (si+1 = ti+1) or max(dp[i+1][j],dp[i][j+1])

maxをとる方がなぜこれでよいのか、よくある説明では理解しにくかった。 自分はこう考えた。

2つの文字列の最後尾が違う文字のケースを考える dp[i+1][j+1]=mとおく

  1. dp[i][j+1]とdp[i+1][j]のどちらもmかm-1である
  2. dp[i]j+1]とdp[i+1][j]が両方ともm-1なケースはない
  3. 1,2よりmax(dp[i+1][j],dp[i][j+1]) = m が恒等的に成り立つ
  4. 前提よりdp[i+1][j+1]=の関係があるので、3を置き換えて、max(dp[i+1][j],dp[i][j+1]) = dp[i+1][j+1]

#1

あとでかく

#2

dp[i][j+1] = m-1 の場合を考える。この場合「s1~i+1とt1~j+1の文字列のLCS群はすべてsi+1を使っている」が以下のように言える。

s1~i+1とt1~j+1の文字列のLCS群(長さm)の中にsi+1を使っていないものがあると仮定する
その文字列はs1~iとt1~j+1においてもLCSである。つまりdp[i][j+1] = mである
これはdp[i][j+1] = m-1 に反し矛盾する
よって仮定を否定し、「s1~i+1とt1~j+1の文字列のLCS群はすべてsi+1を使っている」がいえる

dp[i+1][j] = m-1 の場合も同様に「s1~i+1とt1~j+1の文字列のLCS群はすべてtj+1を使っている」が言える

dp[i][j+1] = m-1 && dp[i+1][j] = m-1 を仮定すると、

  1. 「s1~i+1とt1~j+1の文字列のLCS群はすべてsi+1を使っている」  
  2. 「s1~i+1とt1~j+1の文字列のLCS群はすべてtj+1を使っている」

が両方言えてしまうがが、今はsi+1とtj+1が異なるという前提なので、このケースは不適

したがってあり得るパターンは

  1. dp[i][j+1] = m と dp[i+1][j] = m
  2. dp[i][j+1] = m-1と dp[i+1][j] = m
  3. dp[i][j+1] = m と dp[i+1][j] = m-1

#3

#2により、どのケースにおいても
max(dp[i+1][j],dp[i][j+1]) = m が成り立つ

蟻本Fence Repair 解法の妥当性考察

問題: 蟻本49p

多分以下の流れで妥当性が言える

注意

「サブ問題」の言葉の定義があいまいである。Lmin1とLmin2でない板の合算についての問題も考えられるので、「メイン問題からどの板を合算したか」の情報をサブ問題に入れるべ木だと思う。しかし最終的なプログラムの解法としてLmin1とLmin2の合算を考えたサブ問題しか考えないので自分の理解しやすさ優先で書いた。

考察の流れ

  • #1 板の切断ごとに分岐を考えることで2分木で表現できる。(以降、切断木)。
  • #2 切断の合計コストは「Σ(Ln x この木におけるLnのノードの深さ)」である (深さは0スタートとする)
  • #3 木の構造を変えずに、葉ノードをほかの葉ノードと入れ替えて枝ノードを適切に張り替えれば、切断を表す木としてvalidである(木の構造は異なっても実質切断順が変わっただけものになる可能性はある)
  • #4 与えられた問題(以降、メイン問題)の最小コストとなる切断木の集合の中には、「L1~Lnの板の中で短い順に並べたもの2つ(以降、Lmin1、Lmin2)が最深部で葉ノードとして隣接している木」が含まれる
  • #5 #4で言及した木から、Lmin1とLmin2を消した木は「メイン問題で与えられた板群から、最短となる板2つをその合計を持つ1つの板に置き換えて作った板群についてのサブ問題」に対する切断木として考えられ、その切断のコストはサブ切断木の集合の中で最小である
  • #6. P0: メイン問題, Pn: Pn-1のサブ問題 と定義したとき、 「Pnの最小コスト = Pn板群の最短長板2つの合計長 + Pn+1の最小コスト となり、最終的に板数が1の小さい問題」に分割できる。
  • #7 P0の板群に対し、 「ソート済み板に対し、短いやつ2つを合計し解として加算」「その2つを繋げた板に置き換えて再度板群をソート」を繰り替えして、ループが止まったときFenceRepairの解が求まっている

例や補足

#1

例えば、欲しい板の長さをL1~L6として、以下のような分割をする

L1+L2+L3+L4+L5+L6 -> L1+L3,とL6+L4+L2+L5 に分割
L1+L3 -> L1とL3に分割
L2+L4+L5+L6 -> L2+L4+L6とL5に分割
L2+L4+L6 -> L4+L6とL2に分割
L4+L6 -> L2に分割

この切断は以下のような木に対応する

#2

#1において、 切断の合計コストは Cost = L1x2 + L3x2 + L4x4 + L6x4 + L2x3 + L5x2

#3

#1について、L3とL4のノードを入れ替えた
道中のラベルは末端ノードが決まれば一意に決まる

#4

一般に、

 A<B , X<Y について  
AxY + BxX < AxX + BxY 

∵
左辺 - 右辺 = Ax(Y-X) + Bx(X-Y) = (Y-X)(A-B) < 0

なので、「深いノードに長い板」と「浅いノードに短い板」がある場合、それらを交換した木はコストが低くなる。
これを利用して、例えば3の切断木において、L1とL2が最短長板2つであるとき、最深部のノード(L3,L6)と交換することで、切断木のコストを小さくできる

L1,L2,L3,L6についてのコストに注目すると、

#3 の木では、 L1x2 + L3x4 + L6x4 + L2x2
#4 入れ替えた方の木では、 L3x2 + L1x4 + L2x4 + L6x2
上-下 = (L3-L1)2 + (L6-L2)2 > 0
なので、下の方が安い

したがって、切断コスト最小となる木においては、「深いノードに長い板」と「浅いノードに短い板」のような関係がないはずなので、Lmin1とLmin2に当たる木は最深部にいるはずである
また、同一深度のノードは入れ替えてもコストは変わらないので、切断コストが最小な木を1つとってきたとき最深部にいるはずのLmin1とLmin2が隣接するように並べ替えても、それは切断コストが最小な木である

#5

たとえば#4 の木から、L1とL2の板のノードを合体したものは、その2つを(L1+L2)の長さを持つ板に置き換えたサブ問題の切断をあらわす

この木は、#4からコストがL1+L2分だけ安いことがわかる。つまり、サブ切断木のコストはメイン切断木から結合した板の合計分だけ安くなる。

これを利用し、「メイン問題のコスト最小の切断木において、Lmin1とLmin2を結合した木は、サブ問題におけるコスト最小の切断木の1つである」ことが以下のように言える

メイン問題の最小コスト切断木T(コストC)のうち、Lmin1とLmin2が最深部で隣接しているものをとる  
この木のLmin1とLmin2を結合した木をサブ切断木Tsubとして考えたとき、そのコストはCsub = C-(L1+L2)である

このサブ切断木がサブ問題における最小コストの切断木であることを背理法で示す。
* サブ問題の切断木の集合の中に、コストがCsub2 < Csub であるようなサブ切断木Tsub2があると仮定する
* Tのうち、(L1+L2)を合算して作ったノードを分解した木はメイン問題における切断木の1つであり、そのコストはCsub2+(L1+L2) < Csub+(L1+L2) = C である
* メイン問題における切断木のコストの最小がCであることに矛盾
* 「仮定が間違っている<=>サブ問題においてTsubよりコストの小さい切断木は存在しない」ので、Tsubがサブ問題の最小コストの切断木の1つである

#6,#7

メイン問題の最小コスト切断木はサブ問題の最小コスト切断木が求まればわかる
サブ問題の最小コスト切断機はサブサブ問題の...

というように再帰的にとけることが分かった

心のよりどころなくなった

自作えっちゲームの宣伝のfavが1000を超えた。
学生のころからえっちゲーム制作をしてみたいと思っていて、まずは1000本売り上げようとおもい、既存の作品でそのラインにのっているのはfavが1000以上あるものだったので、まずはそれを目標にしていた。
いつかそっちで飯がくえたらいいなあと漠然と考えつつ大学とか仕事とか人生を過ごしていた。


自分は思った以上にメンタルが弱く結構気持ちが苦しくなることがある。
仕事は周りの方が全然優秀だし、人生設計もしっかりしているし、自立している。
自分は(すごい怠けていたというわけではないが)今の自分ができる範囲で頑張ろう、それでだめならしょうがない、
「まぁ今の手札が全部だめになったら、ゲーム制作する時間がとれるしいっか」と考えることで、苦しみを和らげていた。
急場な時は多少抗不安薬が必要なぐらいメンタルがつらい時もあったが、それでもこの券のことを考えていれば最悪ではなかった。
自分にとってゲーム制作は手札とは関係ない「次の試合への参加券」だった。これを持っている限り、自分の心は安泰だった。


そういう考えで過ごし始めてから10年、ゲーム制作という夢の、最初の目標が今日達成された。
めちゃくちゃ嬉しい。だけどその瞬間から動機が止まらない。今までにない恐怖が襲ってきた。
自分の書いた糞な卒論を発表しないといけなかった日を同じぐらい苦しい。でも原因がわからない。
30分寝ても解決しない。友人に褒めてもらっても(嬉しいけど)心が休まらない。気をそらしたくて何時間もyoutubeやtwitterを見てしまった。
かえって体がどんどん重くなって、動けなくなりそうだった。


ネットの情報を遮断するため銭湯にいって、頭を整理することにした。


現実の恐怖が苦しいとき、ゲーム制作のことについて考えると和らげることができた。でも今日、夢の最初の目標を達成したことで、労力とリターンの計算が現実味を帯びてきて、その輪郭がはっきりしてきた。
そうして「次の試合への参加券」は、今持っている手札と同じ形であることに気づいてしまった。


言語化できたことで幾分は楽になった。それでもこれからの絶望は計り知れない。
自分は今から、10年間なぁなぁで切ってきたこの手札に、真正面から向き合わなければならない。その恐怖に耐えきれるだろうか。






もう一つの券も学生のころから持っている。使いたくなくて見ないようにしていたけど、今後恐怖に負けた時はこれに頼らざるをえないかもしれない。
「北欧に健康な人間でも安楽死させてくれる組織があるらしい」。

UnityVFXで極座標ノイズをつくる

追記: これでいいじゃん 


youtu.be
ノイズテクスチャに極座標ノードを付けて同心円状のノイズを作っているのを見た。
VFXの勉強がてらこれをやってみた

動画ではノイズテクスチャをつっていたが、面倒だったのでノイズノードを使おうとした。
テクスチャの代わりにノイズノードにつけたが、画面下半分に縦線が入る

縦線の右側がuv.y=0.5、左側がuv.y=-0.5になっている

この縦線をまたいでもきれいにつながってほしい。
つまりノイズの方を常に「noise(y)=noise(y+1)」というなるようなものを作れば、極座標ノードにつけてもきれいに渦巻っぽいノイズになるはず

単に「周期1で繰り返す」ノイズではだめで、切れ目ができてしまう

そこで周期2のノイズを用意(noise_2と呼ぶ、y=2->0の時に切れ目がある)し、

output = lerp ( (noise_2(y+1) , noise_2(y), t) (ただし t=abs(-mod(y,2)+1))

y=0のとき、t=1, noise_2(y+1) = noise_2(1) の比重がおおきいので切れ目がない
y=1のとき、t=0, noise_2(y) = noise_2(1) の比重がおおきいので切れ目がない
y=2のとき、t=1, noise_2(y+1) = noise_2(1) の比重がおおきいので切れ目がない
という風に、切れ目のないほうの比重が大きくなるようにできる

modの部分はmoduloにしたかったが、負の数をいい感じにしてくれないので代わりにperiodicていうサブグラフ作った


こうして、「y方向に周期1できれいにつながるノイズ」がでいたので、YLoopNoiseと名付けて、極座標ノードにつけてみた

予想どおりノイズ下半分の縦線がなくなった

Unity 2Dレンダラで3Dオブジェクトをライティングする

qiita.com
ノーマルマップがないモデルだといい感じにライティングされなかったからこれ多分モデルにノーマルマップがあるときの事例だと思う(未検証)

頂点のノーマルだけで事足りる場合もあるのでちょっと改変した

〜
shader "Universal Render Pipeline/2D/Sprite-Lit-3D"
{
    Properties
    {
        [MainTexture] _MainTex("Diffuse", 2D) = "white" {}
        [MainColor] _BaseColor("Color", Color) = (1,1,1,1)
        [HDR] _EmissionColor("Emission", Color) = (0,0,0,0)
        _MaskTex("Mask", 2D) = "white" {}
        _NormalMap("Normal Map", 2D) = "bump" {}

        // Legacy properties. They're here so that materials using this shader can gracefully fallback to the legacy sprite shader.
        [HideInInspector] _Color("Tint", Color) = (1,1,1,1)
        [HideInInspector] _RendererColor("RendererColor", Color) = (1,1,1,1)
        [HideInInspector] _Flip("Flip", Vector) = (1,1,1,1)
        [HideInInspector] _AlphaTex("External Alpha", 2D) = "white" {}
        [HideInInspector] _EnableExternalAlpha("Enable External Alpha", Float) = 0
    }

    HLSLINCLUDE
    #include "Packages/com.unity.render-pipelines.universal/ShaderLibrary/Core.hlsl"
    ENDHLSL

    SubShader
    {
        Tags {"Queue" = "Geometry" "RenderType" = "Opacue" "RenderPipeline" = "UniversalPipeline" }

        Blend SrcAlpha OneMinusSrcAlpha
        Cull Back
        ZWrite On

        Pass
        {
            Tags { "LightMode" = "Universal2D" }
            HLSLPROGRAM
            #pragma prefer_hlslcc gles
            #pragma vertex CombinedShapeLightVertex
            #pragma fragment CombinedShapeLightFragment
            #pragma multi_compile USE_SHAPE_LIGHT_TYPE_0 __
            #pragma multi_compile USE_SHAPE_LIGHT_TYPE_1 __
            #pragma multi_compile USE_SHAPE_LIGHT_TYPE_2 __
            #pragma multi_compile USE_SHAPE_LIGHT_TYPE_3 __

            struct Attributes
            {
                float3 positionOS   : POSITION;
                float4 color        : COLOR;
                float2  uv           : TEXCOORD0;
            };

            struct Varyings
            {
                float4  positionCS  : SV_POSITION;
                float4  color       : COLOR;
                float2  uv          : TEXCOORD0;
                float2  lightingUV  : TEXCOORD1;
            };

            #include "Packages/com.unity.render-pipelines.universal/Shaders/2D/Include/LightingUtility.hlsl"

            TEXTURE2D(_MainTex);
            SAMPLER(sampler_MainTex);
            TEXTURE2D(_MaskTex);
            SAMPLER(sampler_MaskTex);
            TEXTURE2D(_NormalMap);
            SAMPLER(sampler_NormalMap);
            half4 _MainTex_ST;
            half4 _NormalMap_ST;
            half4 _BaseColor;
            half4 _EmissionColor;

            #if USE_SHAPE_LIGHT_TYPE_0
            SHAPE_LIGHT(0)
            #endif

            #if USE_SHAPE_LIGHT_TYPE_1
            SHAPE_LIGHT(1)
            #endif

            #if USE_SHAPE_LIGHT_TYPE_2
            SHAPE_LIGHT(2)
            #endif

            #if USE_SHAPE_LIGHT_TYPE_3
            SHAPE_LIGHT(3)
            #endif

            Varyings CombinedShapeLightVertex(Attributes v)
            {
                Varyings o = (Varyings)0;

                o.positionCS = TransformObjectToHClip(v.positionOS);
                o.uv = TRANSFORM_TEX(v.uv, _MainTex);
                float4 clipVertex = o.positionCS / o.positionCS.w;
                o.lightingUV = ComputeScreenPos(clipVertex).xy;
                o.color = v.color * _BaseColor;
                return o;
            }

            #include "Packages/com.unity.render-pipelines.universal/Shaders/2D/Include/CombinedShapeLightShared.hlsl"

            half4 CombinedShapeLightFragment(Varyings i) : SV_Target
            {
                half4 main = i.color * SAMPLE_TEXTURE2D(_MainTex, sampler_MainTex, i.uv);
                half4 mask = SAMPLE_TEXTURE2D(_MaskTex, sampler_MaskTex, i.uv);

                return CombinedShapeLightShared(main, mask, i.lightingUV)+main*_EmissionColor;
            }
            ENDHLSL
        }

        Pass
        {
            Tags { "LightMode" = "NormalsRendering"}
            HLSLPROGRAM
            #pragma prefer_hlslcc gles
            #pragma vertex NormalsRenderingVertex
            #pragma fragment NormalsRenderingFragment

            struct Attributes
            {
                float3 positionOS   : POSITION;
                float3 normalOS     : NORMAL;//ここで頂点の法線を取得
                float4 color        : COLOR;
                float2 uv           : TEXCOORD0;
                float4 tangent      : TANGENT;
            };

            struct Varyings
            {
                float4  positionCS      : SV_POSITION;
                float4  color           : COLOR;
                float2  uv              : TEXCOORD0;
                float3  normalWS        : TEXCOORD1;
                float3  tangentWS       : TEXCOORD2;
                float3  bitangentWS     : TEXCOORD3;
            };

            TEXTURE2D(_MainTex);
            SAMPLER(sampler_MainTex);
            TEXTURE2D(_NormalMap);
            SAMPLER(sampler_NormalMap);
            float4 _NormalMap_ST;  // Is this the right way to do this?

            Varyings NormalsRenderingVertex(Attributes attributes)
            {
                Varyings o = (Varyings)0;

                o.positionCS = TransformObjectToHClip(attributes.positionOS);
                o.uv = TRANSFORM_TEX(attributes.uv, _NormalMap);
                o.uv = attributes.uv;
                o.color = attributes.color;
                o.normalWS = TransformObjectToWorldDir(attributes.normalOS);
                o.tangentWS = TransformObjectToWorldDir(attributes.tangent.xyz);
                o.bitangentWS = cross(o.normalWS, o.tangentWS) * attributes.tangent.w;
                return o;
            }

            #include "Packages/com.unity.render-pipelines.universal/Shaders/2D/Include/NormalsRenderingShared.hlsl"

            float4 NormalsRenderingFragment(Varyings i) : SV_Target
            {
                float4 mainTex = i.color * SAMPLE_TEXTURE2D(_MainTex, sampler_MainTex, i.uv);
                float3 normalTS = UnpackNormal(SAMPLE_TEXTURE2D(_NormalMap, sampler_NormalMap, i.uv));
                //return NormalsRenderingShared(mainTex, normalTS, i.tangentWS.xyz, i.bitangentWS.xyz, i.normalWS.xyz);
                half3 normalVS = TransformWorldToViewDir(i.normalWS.xyz);//頂点の法線情報をそのまま使う
                half4 normalColor;
                    
                normalColor.rgb = 0.5 * ((normalVS)+1);
                normalColor.a = i.color.a;  // used for blending

                return normalColor;
            }
            ENDHLSL
        }
        Pass
        {
            Tags { "LightMode" = "UniversalForward" "Queue"="Geometry" "RenderType"="Opacue"}

            HLSLPROGRAM
            #pragma prefer_hlslcc gles
            #pragma vertex UnlitVertex
            #pragma fragment UnlitFragment

            struct Attributes
            {
                float3 positionOS   : POSITION;
                float4 color        : COLOR;
                float2 uv           : TEXCOORD0;
            };

            struct Varyings
            {
                float4  positionCS      : SV_POSITION;
                float4  color           : COLOR;
                float2  uv              : TEXCOORD0;
            };

            TEXTURE2D(_MainTex);
            SAMPLER(sampler_MainTex);
            float4 _MainTex_ST;

            Varyings UnlitVertex(Attributes attributes)
            {
                Varyings o = (Varyings)0;

                o.positionCS = TransformObjectToHClip(attributes.positionOS);
                o.uv = TRANSFORM_TEX(attributes.uv, _MainTex);
                o.uv = attributes.uv;
                o.color = attributes.color;
                return o;
            }

            float4 UnlitFragment(Varyings i) : SV_Target
            {
                float4 mainTex = i.color * SAMPLE_TEXTURE2D(_MainTex, sampler_MainTex, i.uv);
                return mainTex;
            }
            ENDHLSL
        }
    }

    FallBack "Universal Render Pipeline/Unlit"
}
〜

Tags { "LightMode" = "NormalsRendering"}
のPassで
頂点シェーダで法線情報をもらって
NormalsRenderingFragmentでそのままつかっただけ

f:id:stalagmite:20210829170155p:plain

白いCubeは3dモデルだけど松明のLight2D(PointLight)の光を受けている