使用JobSystem优化阶梯地形生成算法

发布时间: 2022年07月24日阅读数: 31

缘由

几年前玩过的一款游戏

，其中的实时可交互的地形算法让我印象十分深刻，

恰巧前一段时间看到了介绍该算法的博客.

然后根据文章中的算法实现了一波，效果如下：

![](https://res.lazyun.cn/typecho/2022/07/24/earth_terraced.jpg?x-oss-process=style/compress)

原理

原始算法大概流程：

  • 基于Height Map 生成Mesh
  • 遍历Mesh所有三角形
  • 将遍历到的三角形，按照Meandering Triangless算法进行基于高度分层切割
  • 将切割出来的新三角形添加到Mesh

上述算法涉及到大量计算，所有很自然的想到用多线程来优化性能，在Unity中自然就是JobSystem。

基于JobSystem的阶梯地形算法流程：

  • 构造数据对象
public struct QuadVertices
    {
        public int a;
        public int b;
        public int c;
        public int d;
    }
    
    public struct QuadFace
    {
        // vertex
        public Vector3 a;
        public Vector3 b;
        public Vector3 c;
        public Vector3 d;

        // uv
        public Vector2 u1;
        public Vector2 u2;
        public Vector2 u3;
        public Vector2 u4;
        
        // vertex color
        public Color32 c1;
        public Color32 c2;
        public Color32 c3;
        public Color32 c4;
    }
  • 从Height Map计算获得QuadVertices[], 其中存储了所有相邻四个顶点组成的2个三角形Mesh数据的顶点信息
  • 遍历所有QuadVertices[]
  • 对每个QuadVertices 做如下计算，其中ProcessTriangle 也是针对单个三角形使用Meandering Triangles 算法
var quad = quads[index];
    var a = vertices[quad.a];
    var b = vertices[quad.b];
    var c = vertices[quad.c];
    var d = vertices[quad.d];
    
    if (h_max - h_min < 1)
    {
    #if !DISABLE_TERRACE_MESH_WITH_COLOR
        var color_c = colors[Mathf.Abs(h_min + 10) % colors.Length];
    #endif
        quadFaces.AddNoResize(new QuadFace()
        {
            a = new Vector3(a.x, h_min, a.z), b = new Vector3(b.x, h_min, b.z),
            c = new Vector3(c.x, h_min, c.z), d = new Vector3(d.x, h_min, d.z),
            c1 = color_c, c2 = color_c, c3 = color_c, c4 = color_c,
            u1 = u1_c, u2 = u2_c, u3 = u3_c, u4 = u4_c
        });
        return;
    }
    
    
    // 处理 1/2/3 序号顶点组成的三角形
    ProcessTriangle(a, b, c);

    // 处理 1/2/4 序号顶点组成的三角形
    ProcessTriangle(a, c, d);
  • 根据NativeList<QuadFace> 中的数据构造成Mesh
var q = rawMeshData[i];
    var i4 = 4 * i;
    var i6 = 6 * i;
    vertices[i4 + 0] = q.a;
    vertices[i4 + 1] = q.b;
    vertices[i4 + 2] = q.c;
    vertices[i4 + 3] = q.d;

    uvs[i4 + 0] = q.u1;
    uvs[i4 + 1] = q.u2;
    uvs[i4 + 2] = q.u3;
    uvs[i4 + 3] = q.u4;

    colors[i4 + 0] = q.c1;
    colors[i4 + 1] = q.c2;
    colors[i4 + 2] = q.c3;
    colors[i4 + 3] = q.c4;

    triangles[i6 + 0] = i4;
    triangles[i6 + 1] = i4 + 1;
    triangles[i6 + 2] = i4 + 2;
    triangles[i6 + 3] = i4;
    triangles[i6 + 4] = i4 + 2;
    triangles[i6 + 5] = i4 + 3;

其他

  • 还可以通过分区的方式来降低运算量，具体可参考：https://github.com/mshandle/Terraced-Terrain
  • 基于四边形的算法在同一个QuadFace内，只有4个顶点，而三角形则有6个顶点，这也是个极大优势
  • 因为Meandering Triangles算法的特点，在计算的过程中会生成新的三角形数据，所以这里数据的长度未知就不能用NativeArray, 而需要使用NativeList
// 声明
    [WriteOnly] public NativeList<QuadFace>.ParallelWriter quadFaces;


    // 初始化，20000为List的最大长度
    quadFaces = new NativeList<QuadFace>(20000, Allocator.Persistent);
    
    
    // 传递数据到IJob
    quadFaces = data.quadFaces.AsParallelWriter(),

标签:

UnityJobSystem