【Unity云消散】理论基础：实现SDF的8SSEDT算法

距离元旦假期已经过去5天了（从31号算起！），接着开始学习！ 

游戏中的很多渲染效果都离不开SDF，那么SDF究竟是什么呢？到底是个怎么样的技术？为什么能解决那么多问题？

1 SDF

SDF，即signed distance field，有向距离场or带符号距离场（直译）。

1.1 记录了什么

SDF贴图，每个像素记录自己与距离自己最近的物体边界的距离。也就是说，SDF的贴图记录的竟然不是颜色信息，而是距离。 

图像的矢量表达

Signed Distance Field与Multi-channel signed distance field这篇文章更加直白的介绍了SDF——SDF本质上就是在一个光栅图里存了一个图像的矢量表达，说的太好了，真得就是这么一回事。

signed

所谓的signed体现在：像素点在物体内距离为负，刚好在物体边界边界上为0。但其实这个物体内距离是正是负、其实只是一个判断的问题？（不太清楚这样说正确与否）

直接举几个例子吧。

1（直接截图了Signed Distance Field的内容）

2 直接了当的展示了signed（直接截图了SDF(signed distance field)基础理论和计算）： 

3 这个表示方法更加形象理解“矢量”这个描述（直接截图了Signed Distance Field与Multi-channel signed distance field）：

1.2 能干什么

Ray Marching

首先，Ray Marching，202有学习过：Lecture5 Real-time Environment Mapping

卡渲的面部光照

其次，风格化卡通渲染的人物面部光照，很多文章都有介绍，例如卡通渲染之基于SDF生成面部阴影贴图的效果实现（URP）

SDF可以实现图像之间的平滑过渡，直接对两张SDF进行lerp插值就能得到视觉上的平滑过渡效果实际上是SDF贴图记录的距离之间的平滑过渡。 

其他的

除了RayMarching和面部光照，还有字体渲染（Unity中的TextMeshPro插件就是基于SDF的，还可以看看这篇文章）、做一些形变动画等等。

1.3 怎么做

8SSEDT算法（8-points Signed Sequential Euclidean Distance Transform），这是一种能在线性时间内计算出SDF的算法，基本上实现SDF都用的是8SSEDT吧。下面会着重学习一下这个算法是如何实现的。

2 8SSEDT算法

8ssedt其实是实现SDF的一种算法，还有其他方法，至于方法之间的对比以及简易程度这里我就略过啦！

2.1 算法核心：递推 

SDF的宗旨一直都是记录当前像素点离最近物体边界的距离。我们假设用0和1来表示当前像素点，0表示像素点值为空，1表示在物体，那么要找到距离当前点最近的目标像素点，就有以下两种情况：

  • 像素值为1：代表像素点自己就是目标点，距离为0
  • 像素值为0：代表当前像素点不是目标点，意味着向四周任意方向（上下左右/左上左下右上右下）都有可能是目标点

像素值为0时有以下两种情况： 

  • 上下左右的某个像素点的像素值为1
  • 左上左下右上右下的某个像素点的像素值为1

该像素点的SDF取值为：MinmumSDF(now.sdf, near.sdf + distance(now, near))，即附近像素点的SDF值+当前像素点到附近像素点的距离。

而公式里的near.sdf也同样需要用上述的式子计算，你会发现SDF图像记录的距离都是连续的，所以SDF算法的内核其实是递推，把复杂的问题拆解成了连续的简单问题。

伪代码

  1. now.sdf = 999999;// 初始为空，距离尽可能大
  2. if(now in object){// 
  3.     now.sdf = 0;// sdf距离为0
  4. }else{// 像素点值为0
  5.     foreach(near in nearPixel(now)){
  6.         now.sdf = min(now.sdf,near.sdf + distance(now,near));// 递推
  7.     }
  8. }

2.2 算法核心思路

STEP1 加载图片并创建2个Grid

假设我们拿到一张黑白图，加载图片后，遍历一遍黑白图，此时的原图里假设是白色为物体，黑色为空，建立两个Grid来记录网格像素数据，用以确定像素点是位于物体内部还是外部，如何建立如下：

  • 一个Grid用于计算物体外到物体的距离：那么从距离的角度来讲，我们可以标记白色像素距离为0，黑色像素距离为一个尽可能大的数（例如上面的now.sdf = 999999），这个Grid用于推导向外的距离场
  • 一个Grid用于计算物体内部点到物体外的距离：即黑色像素标记距离为0，白色像素标记为一个尽可能大的值，这个Grid用于推导向内的距离场

也就是一个Grid缓存内部为0，外部为无穷；一个Grid缓存内部为无穷，外部为0。

STEP2 计算距离

接下来干什么呢？让一个像素与周围的8个像素分别进行比较。

按照“从左往右，从上到下”（如果是引擎UV生成还要考虑方向，比如Unity的UV是从下往上）的顺序遍历所有的像素。

文章Signed Distance Field - 知乎 (zhihu.com)中把过程拆解成了两个PASS，每个Grid都经历一次PASS0和PASS1，具体过程可以直接戳这篇文章看就行！过程包括伪代码都写的很详细~

STEP3 两个Grid作差

grid1(pixel).sdf - grid2(pixel).sdf就行。

2.3 Excel直观理解算法

这里我简单实践一下帮助更好的理解，选择了一个笨蛋办法，在excel里进行：

STEP1 计算Grid1

第一个Grid原始值如下（用9直接替代∞）：

PASS0后：

PASS1后最终：

STEP2 计算Grid2

第二个Grid原始值如下（用9直接替代∞）：

PASS0和PASS1后最终：

STEP3 相减

对每个对应位置像素Grid1.sdf - Grid.sdf后，才算得到最终的signed结果：

这样得到的就是最后的SDF贴图每个像素点储存的距离了，当然这只是个简单的例子，得到真实的应该是类似于下图的样子（这张截图来自这篇文章，上面也有类似的例子展示）：

3 代码实现

学习的过程中我发现绝大部分文章的代码都来自于这篇文章：Signed Distance Fields (codersnotes.com)，Signed Distance Field中对过程做了解释，但是呢如果直接运行你会发现缺少一个SDL库。

3.1 SDL库

上述代码运行还需要添加SDL库，具体如何添加以及SDL库是什么可以直接看这篇文章：

SDL库的介绍与安装

捣鼓捣鼓你会发现，上述代码其实用的是SDL1.2版本（毕竟是2006年的文章了），有一些函数已经被替换/删除了，且64位的电脑上支持不了一些头文件，例如SDL_config.h就是SDL_config_win32.h

所以我们不仅要添入SDL库，还需要对比1.2和2.0的不同修改代码，修改的过程就不赘述了，后面的完整代码里我会写一些注释，这里简单列举一下我参考的一些文章：

SDL2常用函数&结构分析:SDL_Surface&SDL_GetWindowSurface&SDL_LoadBMP

SDL学习笔记(3)——窗口绘制 

3.2 最后的完整代码

部分函数的使用我写了一些注释方便理解，修改后的最终代码如下：

  1.  
  2. #include 
  3. #include 
  4. #include 
  5.  
  6. #pragma comment(lib, "SDL2.lib")
  7. #pragma comment(lib, "SDL2main.lib")
  8.  
  9. #define SDL_MAIN_HANDLED
  10.  
  11. #define WIDTH  256
  12. #define HEIGHT 256
  13.  
  14. struct Point
  15. {
  16. 	//dx,dy表示对于当前点的偏移值
  17. 	int dx, dy;
  18.  
  19. 	int DistSq() const { return dx * dx + dy * dy; }
  20. };
  21.  
  22. struct Grid
  23. {
  24. 	Point grid[HEIGHT][WIDTH];
  25. };
  26.  
  27. Point inside = { 0, 0 };
  28. Point empty = { 9999, 9999 };
  29. Grid grid1, grid2;
  30.  
  31. Point Get(Grid& g, int x, int y)
  32. {
  33. 	// OPTIMIZATION: you can skip the edge check code if you make your grid 
  34. 	// have a 1-pixel gutter.
  35. 	if (x >= 0 && y >= 0 && x < WIDTH && y < HEIGHT)
  36. 		return g.grid[y][x];
  37. 	else
  38. 		return empty;
  39. }
  40.  
  41. void Put(Grid& g, int x, int y, const Point& p)
  42. {
  43. 	g.grid[y][x] = p;
  44. }
  45.  
  46. void Compare(Grid& g, Point& p, int x, int y, int offsetx, int offsety)
  47. {
  48. 	//获取当前点偏移后的点
  49. 	Point other = Get(g, x + offsetx, y + offsety);
  50. 	//给获取的点的dx和dy设置对应的偏移值
  51. 	other.dx += offsetx;
  52. 	other.dy += offsety;
  53.  
  54. 	if (other.DistSq() < p.DistSq())
  55. 		p = other;
  56. }
  57.  
  58. // Now all we have to do is run the propagation algorithm. See the paper for exactly what's happening here, 
  59. // but basically the idea is to see what the neighboring pixel has for it's dx/dy,
  60. //  then try adding it onto ours to see if it's better than what we already have.
  61. void GenerateSDF(Grid& g)
  62. {
  63. 	// Pass 0
  64. 	//遍历当前点以及左右、左下、右下、正下方的点，找到距离最短的点存储在网格对应位置处
  65. 	for (int y = 0; y < HEIGHT; y++)
  66. 	{
  67. 		for (int x = 0; x < WIDTH; x++)
  68. 		{
  69. 			Point p = Get(g, x, y);
  70. 			Compare(g, p, x, y, -1, 0);
  71. 			Compare(g, p, x, y, 0, -1);
  72. 			Compare(g, p, x, y, -1, -1);
  73. 			Compare(g, p, x, y, 1, -1);
  74. 			Put(g, x, y, p);
  75. 		}
  76.  
  77. 		for (int x = WIDTH - 1; x >= 0; x--)
  78. 		{
  79. 			Point p = Get(g, x, y);
  80. 			Compare(g, p, x, y, 1, 0);
  81. 			Put(g, x, y, p);
  82. 		}
  83. 	}
  84.  
  85. 	// Pass 1
  86. 	for (int y = HEIGHT - 1; y >= 0; y--)
  87. 	{
  88. 		for (int x = WIDTH - 1; x >= 0; x--)
  89. 		{
  90. 			Point p = Get(g, x, y);
  91. 			Compare(g, p, x, y, 1, 0);
  92. 			Compare(g, p, x, y, 0, 1);
  93. 			Compare(g, p, x, y, -1, 1);
  94. 			Compare(g, p, x, y, 1, 1);
  95. 			Put(g, x, y, p);
  96. 		}
  97.  
  98. 		for (int x = 0; x < WIDTH; x++)
  99. 		{
  100. 			Point p = Get(g, x, y);
  101. 			Compare(g, p, x, y, -1, 0);
  102. 			Put(g, x, y, p);
  103. 		}
  104. 	}
  105. }
  106.  
  107. int main(int argc, char* args[])
  108. {
  109.     // SDL_Init(SDL_INIT_VIDEO) -- 初始化视频子系统
  110. 	if (SDL_Init(SDL_INIT_VIDEO) == -1)
  111. 		return 1;
  112.  
  113. 	// 创建一个窗体
  114. 	SDL_Window* window = SDL_CreateWindow("W", SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, WIDTH, HEIGHT, 0);
  115. 	// 创建一个与窗体关联的surface，赋值给screen
  116. 	SDL_Surface* screen = SDL_GetWindowSurface(window);
  117. 	if (!screen)
  118. 		return 1;
  119.  
  120. 	// 加载位图文件
  121. 	// SDL_LoadBMP -- 加载指定的bmp文件，一定要是bmp图像的文件
  122. 	SDL_Surface* temp = SDL_LoadBMP("test.bmp");
  123.  
  124. 	// 调整窗口
  125. 	// SDL_ConvertSurface -- 图片被加载时对其以屏幕相同格式进行转化来保证投射过程中不再发生转化，以新的格式返回原来的surface
  126. 	temp = SDL_ConvertSurface(temp, screen->format, SDL_SWSURFACE);
  127.  
  128. 	SDL_LockSurface(temp);
  129. 	for (int y = 0; y < HEIGHT; y++)
  130. 	{
  131. 		for (int x = 0; x < WIDTH; x++)
  132. 		{
  133. 			Uint8 r, g, b;
  134. 			Uint32* src = ((Uint32*)((Uint8*)temp->pixels + y * temp->pitch)) + x;
  135. 			SDL_GetRGB(*src, temp->format, &r, &g, &b);
  136. 			// Points inside get marked with a dx/dy of zero.
  137. 			// Points outside get marked with an infinitely large distance.
  138. 			// 两个网格，一个内部设置成0，外部设置成正无穷，另一个网格相反。
  139. 			if (g < 128)
  140. 			{
  141. 				Put(grid1, x, y, inside);
  142. 				Put(grid2, x, y, empty);
  143. 			}
  144. 			else {
  145. 				Put(grid2, x, y, inside);
  146. 				Put(grid1, x, y, empty);
  147. 			}
  148. 		}
  149. 	}
  150. 	SDL_UnlockSurface(temp);
  151.  
  152. 	// Generate the SDF.
  153. 	GenerateSDF(grid1);
  154. 	GenerateSDF(grid2);
  155.  
  156. 	// Render out the results.
  157. 	SDL_LockSurface(screen);
  158. 	for (int y = 0; y < HEIGHT; y++)
  159. 	{
  160. 		for (int x = 0; x < WIDTH; x++)
  161. 		{
  162. 			// Calculate the actual distance from the dx/dy
  163. 			//计算偏移值的点距离当前点的距离
  164. 			int dist1 = (int)(sqrt((double)Get(grid1, x, y).DistSq()));
  165. 			int dist2 = (int)(sqrt((double)Get(grid2, x, y).DistSq()));
  166. 			int dist = dist1 - dist2;
  167.  
  168. 			// Clamp and scale it, just for display purposes.
  169. 			int c = dist * 3 + 128;
  170. 			if (c < 0) c = 0;
  171. 			if (c > 255) c = 255;
  172.  
  173. 			Uint32* dest = ((Uint32*)((Uint8*)screen->pixels + y * screen->pitch)) + x;
  174. 			*dest = SDL_MapRGB(screen->format, c, c, c);
  175. 		}
  176. 	}
  177. 	SDL_UnlockSurface(screen);
  178.  
  179. 	// Wait for a keypress
  180. 	SDL_Event event;
  181. 	while (true)
  182. 	{
  183. 		if (SDL_PollEvent(&event))
  184. 			switch (event.type)
  185. 			{
  186. 			case SDL_QUIT:
  187. 			case SDL_KEYDOWN:
  188. 				return true;
  189. 			}
  190. 		// 更新窗口，才能看到
  191. 		SDL_UpdateWindowSurface(window);
  192. 		// 保存成位图
  193. 		SDL_SaveBMP(screen, "save2.bmp");
  194. 	}
  195. 	
  196. 	
  197. 	return 0;
  198. }

3.3 运行展示

首先是一个基础的：

PS随便画了一张（需要保存成bmp格式）：

4 面部阴影(挖个坑)

SDF在风格化渲染中用的最多的地方其实是实现面部阴影，通常是美术绘制好特定光线角度时的面部阴影，通过SDF插值计算出中间的过程，将过程叠加到一张图上，通过简单的blur或者smooth操作实现平滑。

目前已经有大佬给出快速生成上述图的程序了：如何快速生成混合卡通光照图 - 知乎 (zhihu.com)

这里就简单的提一下吧，也是挖个坑（要学的好多！），等实现了天空盒之后就来继续学习面部阴影！！ 

参考

（其实参考了非常多的文章，但是后面写着写着忘记了都有哪些了，这里简单的罗列三个吧~）

【有趣的技术】Unity中的SDF(有向距离场) - 简书 (jianshu.com)

Signed Distance Field - 知乎 (zhihu.com)

Tech-Artist 学习笔记：Signed Distance Field 8SSEDT 算法 - 知乎 (zhihu.com)

注：本文转载自blog.csdn.net的九九345的文章"https://blog.csdn.net/qq_41835314/article/details/128548073"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！