使用ComputeShader加速生成Voronoi Texture(JFA)

Unity

Background

Voronoi Texture是游戏美术素材制作中常用的一种噪声贴图(Worley Noise)。

数学定义：a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects.

通常情况，这里的objects是指有限的点(seeds),每个区域则是按照不同的衡量方式进行划分。Blender的Voronoi Node

Applications

几个常见的应用

  • Volumetric Clouds
  • Ghibli style procedural shading
  • Water splash FX

JumpFlooding Algorithm

一般给定二维平面中的一组种子，最简单的方式即是贴图上每个像素遍历所有种子找最近的种子。显然，这种方法会导致性能随着种子数量的增加变差。为了保持高性能，常见的方法如将二维平面划分成子网格，每个Cell中只生成一个种子，每个像素只遍历其邻接的8个Cell中的种子（In-cell seed generation）。

在采用真正随机生成的种子，或者种子并非静止的情况，则可以通过Jump Flooding Algorithm在GPU上并行生成Voronoi Diagram。

基于Unity Compute Shader的实现

  • Inputs
    • pixels: RenderTexture(需要设置为非归一化带符号的格式, eg. ARGBHalf)
    • seeds: 种子数组(Vector2/3 array)
    • numSeeds: 种子的数量
    • resolution: RenderTexture的分辨率
    • step: JFA每步的步长
    • minMax: 二维数组，用于在ComputeShader中记录全局最小/大距离
  • Kernels
    • Clear Kernel: 清除pixels中的所有最近种子信息
    • Init Kernel: 把种子的信息初始化到pixels中
    • JFA Kernel: JFA的一个substep，以当前的步长扩散最近的种子信息
    • GlobalMinMax Kernel: 统计全局的最小/大数据，更新到minMax[]中
    • Normalize: 根据minMax[]，渲染最后的贴图

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Find Kernel
int clearKernel = voronoiCS.FindKernel("Clear");
int initKernel = voronoiCS.FindKernel("InitSeeds");
int solverKernel = voronoiCS.FindKernel("JFA");
int minMaxKernel = voronoiCS.FindKernel("GlobalMinMax");
int normalizeKernel = voronoiCS.FindKernel("Normalize");

// 初始化pixels
RenderTexture pixels = new RenderTexture(resolution, resolution, 0, RenderTextureFormat.ARGBHalf, 0)
{
    enableRandomWrite = true,
    dimension = UnityEngine.Rendering.TextureDimension.Tex2D,
    wrapMode = TextureWrapMode.Repeat,
    filterMode = FilterMode.Point
};
pixels.Create();
// 将pixels给所有需要用到的kernel
voronoiCS.SetTexture(clearKernel, "pixels", pixels);
voronoiCS.SetTexture(initKernel, "pixels", pixels);
voronoiCS.SetTexture(solverKernel, "pixels", pixels);

// 初始化种子
seeds = SeedGenerator.GenerateCompleteRandom2DSeed(seedNum);
ComputeBuffer seedBuffer = new ComputeBuffer(seeds.Length, Marshal.SizeOf(typeof(Vector2)));
seedBuffer.SetData(seeds);
voronoiCS.SetBuffer(initKernel, "seeds", seedBuffer);
voronoiCS.SetBuffer(solverKernel, "seeds", seedBuffer);

// 初始化minMax数组
int[] minMax = { int.MaxValue, 0 };
ComputeBuffer minMaxBuffer = new ComputeBuffer(minMax.Length, sizeof(int));
minMaxBuffer.SetData(minMax);
voronoiCS.SetBuffer(minMaxKernel, "minMax", minMaxBuffer);
voronoiCS.SetBuffer(normalizeKernel, "minMax", minMaxBuffer);

JFA

初始的步长设置为 $ {{res} } $。算法过程为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Clear Kernel
voronoiCS.Dispatch(clearKernel, numGroupsTex, numGroupsTex, 1);
// Init Kernel
voronoiCS.Dispatch(initKernel, numGroupsInit, 1, 1);
// JFA
while(true)
{
    voronoiCS.SetInt("step", step);
    voronoiCS.Dispatch(solverKernel, numGroupsTex, numGroupsTex, 1);
    if (step / 2.0f < 1)
        break;
    else
        step = Mathf.CeilToInt(step / 2.0f);
}
// Global Min/Max kernel
voronoiCS.Dispatch(minMaxKernel, numGroupNormalize, numGroupNormalize, 1);
// Normalize Kernel
voronoiCS.Dispatch(normalizeKernel, numGroupNormalize, numGroupNormalize, 1);

3D的voronoi生成方式类似，只需将RenderTexture的dimension设置为Tex3D，对应Kernel的numthread和seeds的数据类型同步修改即可。

Seamless Voronoi

上述方法生成的结果作为贴图使用时，一旦对贴图进行缩放，则会有明显的接缝。为解决这一问题，我们需要将分辨率扩大三倍，即创建8个和当前分辨率相同的邻接区域，并同时将种子也平移复制。即在生成阶段，我们生成一个3倍大小的贴图，但最后只取中间的区域。

采用In-Cell方式生成无缝的voronoi时则相对简单。假设像素所处的Cell索引为,总Cell的数量为则其所采样的邻接Cell的索引为

Results

2D Seamless Voronoi 3D Seamless Voronoi
-w256 -w256

Performance