Unity 学习笔记：Signed Distance Field 8SSEDT 算法

fwalker · 发表于 2022-5-28 17:07

Signed Distance Field (有向距离场) 技术在如今的图形渲染项目中有着广泛的运用，例如 Ray Marching、风格化卡通渲染的人物面部光照等等，如果我们想在线性的时间内，通过一张二值化的黑白图，生成一张 SDF 图，那么目前 8SSEDT (8-points Signed Sequential Euclidean Distance Transform) 算法是比较流行的解法。
8SSEDT 的核心就是递推算法——把复杂问题拆解成连续的简单问题。SDF 图记录的是当前像素到物体的距离，距离是连续的，也就是说我们可以通过临近像素的距离推到出当前像素的距离。
核心思路：

假设有一张黑白原图，观察其 9 个点的局部，其每个点的平方距离如下
Raw Data    Sqr Dist

[0][0][0] [ 2][ 1][ 1]
[0][1][1] [ 1][ 0][ 0]
[0][1][1] [ 1][ 0][-1]首先遍历一遍黑白原图，建立一个像素网格数据，标记出原图的黑白部分，白色像素标记距离0，黑色像素标记为一个尽可能的最大值，这组网格数据用于推到向外的距离场。再建立一个像素网格数据，反向标记，黑色像素标记距离0，白色像素标记为一个尽可能的最大值，用于推导向内的距离场。
#Data1    #Data2

[∞][∞][∞] [0][0][0]
[∞][0][0] [0][∞][∞]
[∞][0][0] [0][∞][∞]推导过程则是一个像素分别和周边的 8 个像素进行比较
[#8][#7][#6]
[#1][ 0][#5]
[#2][#3][#4]unity 图像的的 UV 坐标的是从左下到右上的，针对第一组向外的网格数据，首先我们可以从左往右、从下到上推，对比当前像素到左边、左下，下边像素的距离。然后再从右往左、从下到上推，对比当前像素到右下、右边像素的距离
^ [ ][ ][ ] ^ [ ][ ][ ]
| [?][x][ ] | [ ][x][?]
| [?][?][ ] | [ ][ ][?]
- - - >       < - - - 再反方向和另外一边的像素再比较推导一遍，这样 8 个像素就无死角的比较完了。
< - - -       - - - >
[ ][?][?] | [?][ ][ ] |
[ ][x][?] | [?][x][ ] |
[ ][ ][ ] v [ ][ ][ ] v对第二组向内的网格数据重复上面的推导。最后两个合格数据合并在一起就可以得到完整的有向距离场了。

关于SDF贴图的颜色和尺寸的一些想法

已知通常最后是要把 SDF 信息存储到单通道 8 位的贴图上的，也就是说可用的黑白色阶只有 0~255 个，我们最后需要把距离换算到 256 的区间比例里，也就是说在记录距离上，不管你的贴图尺寸多大，其距离信息基本和长宽 256 的贴图等效，所以 SDF 贴图对尺寸并不敏感。在后期的贴图压缩上，可以选择对尺寸进行压缩，但最好不要对精度进行压缩。
最后是 8SSEDT 在 Unity 里实现的核心代码:

using UnityEngine;
using static UnityEngine.Mathf;

public class SDFGeneratorCore
{
private const int MaxDistance = 2147483647;

private enum Type
{
      Object,
      Empty,
}

private struct Pixel
{
      public Type type;
      public int dx, dy;
      public int sqrDistance;
      public Pixel(Type type, int dx, int dy)
      {
         this.type = type;
         this.dx = dx;
         this.dy = dy;
         sqrDistance = dx * dx + dy * dy;
      }
      public Pixel(Type type, int dx, int dy, int sqrDistance)
      {
         this.type = type;
         this.dx = dx;
         this.dy = dy;
         this.sqrDistance = sqrDistance;
      }
}

private struct TexData
{
      private int sizeX,sizeY;
      public Pixel[,] pixels;
      public TexData(int x, int y)
      {
         pixels = new Pixel[x,y];
         sizeX = x - 1;
         sizeY = y - 1;
      }

      public Pixel GetPixel(int x, int y)
      {
         if (x < 0 || x > sizeX || y < 0 || y > sizeY)
            return new Pixel(Type.Empty, 0, 0, MaxDistance);
         else
            return pixels[x, y];
      }
}

public Texture2D CreateSDFTex(Texture2D rawTex)
{
      int width = rawTex.width;
      int height = rawTex.height;
      TexData whiteSideData = new TexData(width, height);
      TexData blackSideData = new TexData(width, height);

      MarkRawData(ref whiteSideData, ref blackSideData, rawTex, width, height);
      GenerateSDF(ref whiteSideData, ref blackSideData, width, height);

      Texture2D newTex = new Texture2D(width, height);
      WriteTex(newTex, whiteSideData, blackSideData, width, height);
      return newTex;
}

void MarkRawData(ref TexData whiteSideData, ref TexData blackSideData, Texture2D tex, int width, int height)
{
      for (int y = 0; y < height; y++)
      {
         for (int x = 0; x < width; x++)
         {
            int value = (int)tex.GetPixel(x, y).r;
            if (value == 1)
            {
                  whiteSideData.pixels[x, y] = new Pixel(Type.Object, 0, 0, 0);
                  blackSideData.pixels[x, y] = new Pixel(Type.Empty, 0, 0, MaxDistance);
            }
            else
            {
                  whiteSideData.pixels[x, y] = new Pixel(Type.Empty, 0, 0, MaxDistance);
                  blackSideData.pixels[x, y] = new Pixel(Type.Object, 0, 0, 0);
            }
         }
      }
}

void ComparePixel(ref TexData data, int x, int y, int offsetX, int offsetY)
{
      Pixel other = data.GetPixel(x + offsetX, y + offsetY);
      if (other.sqrDistance == MaxDistance || other.sqrDistance >= data.pixels[x, y].sqrDistance)
         return;

      Pixel tmp = new Pixel(Type.Empty,other.dx + Abs(offsetX),other.dy + Abs(offsetY));
      if (data.pixels[x, y].sqrDistance > tmp.sqrDistance)
      {
         data.pixels[x, y] = tmp;
      }
}

void ComparePixels(ref TexData data, int x, int y, int ox0, int oy0, int ox1, int oy1)
{
      ComparePixel(ref data, x, y, ox0, oy0);
      ComparePixel(ref data, x, y, ox1, oy1);
}

void ComparePixels(ref TexData data, int x, int y, int ox0, int oy0, int ox1, int oy1, int ox2, int oy2)
{
      ComparePixel(ref data, x, y, ox0, oy0);
      ComparePixel(ref data, x, y, ox1, oy1);
      ComparePixel(ref data, x, y, ox2, oy2);
}

void GenerateSDF(ref TexData whiteSideData, ref TexData blackSideData, int width, int height)
{

      for (int y = 0; y < height; y++)
      {
         for (int x = 0; x < width; x++)
         {
            if (whiteSideData.pixels[x, y].type != Type.Object)
                  ComparePixels(ref whiteSideData, x, y, -1, 0, -1, -1, 0, -1);
            else
                  ComparePixels(ref blackSideData, x, y, -1, 0, -1, -1, 0, -1);
         }

         for (int x = width-1; x >= 0 ; x--)
         {
            if (whiteSideData.pixels[x, y].type != Type.Object)
                  ComparePixels(ref whiteSideData, x, y, 1, -1, 1, 0);
            else
                  ComparePixels(ref blackSideData, x, y, 1, -1, 1, 0);
         }
      }

      for (int y = height-1; y >= 0 ; y--)
      {
         for (int x = width-1; x >= 0 ; x--)
         {
            if (whiteSideData.pixels[x, y].type != Type.Object)
                  ComparePixels(ref whiteSideData, x, y, 1, 0, 1, 1, 0, 1);
            else
                  ComparePixels(ref blackSideData, x, y, 1, 0, 1, 1, 0, 1);
         }

         for (int x = 0; x < width; x++)
         {
            if (whiteSideData.pixels[x, y].type != Type.Object)
                  ComparePixels(ref whiteSideData, x, y, -1, 1, -1, 0);
            else
                  ComparePixels(ref blackSideData, x, y, -1, 1, -1, 0);
         }
      }
}

void WriteTex(Texture2D texture, TexData whiteSideDate, TexData blackSideData, int width, int height)
{
      float scale = height / 256f;
      for (int y = 0; y < height; y++)
      {
         for (int x = 0; x < width; x++)
         {
            float value1 = Sqrt(whiteSideDate.pixels[x, y].sqrDistance) / scale;
            float value2 = Sqrt(blackSideData.pixels[x, y].sqrDistance) / scale;
            float v = (value1 - value2 + 128f) / 256f;
            Color color = new Color(v, v, v);
            texture.SetPixel(x,y,color);
         }
      }
}
}

pc8888888 · 发表于 2022-5-28 17:11

[赞同]

NoiseFloor · 发表于 2022-5-28 17:16

[种草]

		自动登录	找回密码
密码			立即注册

Unity 学习笔记：Signed Distance Field 8SSEDT 算法

本帖子中包含更多资源