Unity Marching Square 网格生成

Marching Squares

原理

• 输入点阵
• 划分Grid
• 计算16种组合
• 参考图
  
  

计算过程

• 计算16种组合的Mesh形态
• 生成Mesh的点，防止重复
• 顺时针生成Mesh
• 示意图
  
  
  
• 面数密度和输入纹理一致，有待优化

拓展

• Convex对比
• Metaball
• Dual Contouring

Marching Cubes

参考

• https://www.redblobgames.com/grids/hexagons/
• 程序化洞穴生成
  • 细胞自动机算法生成洞穴
  • https://blog.csdn.net/qq_33288536/article/details/81915537
• Marching Squares
  • Procedural Cave Generation
  • Procedural Cave Generation
  • 【Unity】Marching Squares 原理与应用
  • 【城镇叠叠乐】用Unity实现Townscaper
  • 小屋编程——Marching Squares
  • How Computers Draw Weird Shapes (Marching Squares)
• Marching Cubes
  • SebLague/Marching-Cubes
  • 【Unity】Marching Cubes 原理与应用
  • 【Unity】基于Marching Cubes的无尽世界生成
  • 图解marching cubes算法
  • How to do Marching Cubes
  • 气象数据可视化——等值面的 Marching Cube 算法

代码

• MarchingSquare.cs

  public class MarchingSquare
  {
      private class Quad
      {
          public readonly byte State;
          public float GuideOffset = 0.5f;
  
          public Quad(int a, int b, int c, int d)
          {
              State = (byte) (a | b << 1 | c << 2 | d << 3);
          }
  
      private class Point
      {
          public readonly uint Hash;
          public Vector3 Position;
  
          public Point(int x, int y, int index, Vector3 pos)
          {
              Hash = GetHash(x, y, index);
              Position = pos;
          }
  
          uint GetHash(int x, int y, int index)
          {
              // index 0-7
              // x remap
              if (index == 0 || index == 1 || index == 2)
              {
                  x = x * 2;
              }
              else if (index == 3 || index == 7)
              {
                  x = x * 2 + 1;
              }
              else if (index == 4 || index == 5 || index == 6)
              {
                  x = x * 2 + 2;
              }
  
              // y remap
              if (index == 0 || index == 7 || index == 6)
              {
                  y = y * 2;
              }
              else if (index == 1 || index == 5)
              {
                  y = y * 2 + 1;
              }
              else if (index == 2 || index == 3 || index == 4)
              {
                  y = y * 2 + 2;
              }
  
              return (uint) x << 16 | (uint) y;
          }
      }
  
      public float OriginPointGuide = 0.1f;
      public float QuadPointGuide = 0.1f;
      public float GuideOffset = 0.5f;
      public bool ShowGuide = false;
  
      private readonly Dictionary<uint, uint> m_points;
      private readonly List<Vector3> m_positions;
      private readonly List<Vector2> m_uvs;
      private readonly List<int> m_triangles;
      private int m_width;
      private int m_height;
  
      public MarchingSquare()
      {
          m_points = new Dictionary<uint, uint>(); // hash-index
          m_positions = new List<Vector3>();
          m_uvs = new List<Vector2>();
          m_triangles = new List<int>();
      }
  
      public int GetPointsCount()
      {
          return m_positions.Count;
      }
  
      public Mesh CreateMesh(int[,] map, Vector2 size, Vector2 center)
      {
          m_points.Clear();
          m_positions.Clear();
          m_uvs.Clear();
          m_triangles.Clear();
  
          m_width = map.GetLength(0);
          m_height = map.GetLength(1);
  
          float step = size.x / (m_width - 1);
          float minx = center.x - size.x / 2.0f;
          float miny = center.y - size.y / 2.0f;
  
          for (int i = 0; i < m_width - 1; i++)
          {
              for (int j = 0; j < m_height - 1; j++)
              {
                  int a = map[i, j];
                  int b = map[i + 1, j];
                  int c = map[i + 1, j + 1];
                  int d = map[i, j + 1];
  
                  var quad = new Quad(a, b, c, d);
                  Vector2 quadCenter = new Vector2(minx + step / 2 + i * step, miny + step / 2 + j * step);
  
                  ProcessQuadMesh(i, j, quad.State, quadCenter, step);
              }
          }
  
          Mesh mesh = new Mesh();
          mesh.vertices = m_positions.ToArray();
          mesh.uv = m_uvs.ToArray();
          mesh.SetIndices(m_triangles, MeshTopology.Triangles, 0);
          return mesh;
      }
  
      uint AddPoint(Point point)
      {
          uint pointHash = point.Hash;
          if (m_points.ContainsKey(pointHash))
          {
              return m_points[pointHash];
          }
          else
          {
              uint num = (uint) m_points.Count;
  
              float x = (pointHash >> 16) / 2.0f;
              float y = (pointHash & 0x0000FFFF) / 2.0f;
              Vector2 uv = new Vector2(x / (m_width - 1), y / (m_height - 1));
  
              m_points[pointHash] = num;
              m_positions.Add(point.Position);
              m_uvs.Add(uv);
              return num;
          }
      }
  
      void AddPolygon(params Point[] points)
      {
          int num = points.Length;
          if (num == 3)
          {
              m_triangles.Add((int) AddPoint(points[0]));
              m_triangles.Add((int) AddPoint(points[1]));
              m_triangles.Add((int) AddPoint(points[2]));
          }
          else if (num == 4)
          {
              // 1
              m_triangles.Add((int) AddPoint(points[0]));
              m_triangles.Add((int) AddPoint(points[1]));
              m_triangles.Add((int) AddPoint(points[2]));
              // 2
              m_triangles.Add((int) AddPoint(points[2]));
              m_triangles.Add((int) AddPoint(points[3]));
              m_triangles.Add((int) AddPoint(points[0]));
          }
          else if (num == 5)
          {
              // 1
              m_triangles.Add((int) AddPoint(points[0]));
              m_triangles.Add((int) AddPoint(points[1]));
              m_triangles.Add((int) AddPoint(points[2]));
              // 2
              m_triangles.Add((int) AddPoint(points[2]));
              m_triangles.Add((int) AddPoint(points[3]));
              m_triangles.Add((int) AddPoint(points[0]));
              // 3
              m_triangles.Add((int) AddPoint(points[3]));
              m_triangles.Add((int) AddPoint(points[4]));
              m_triangles.Add((int) AddPoint(points[0]));
          }
          else if (num == 6)
          {
              // 1
              m_triangles.Add((int) AddPoint(points[0]));
              m_triangles.Add((int) AddPoint(points[1]));
              m_triangles.Add((int) AddPoint(points[5]));
              // 2
              m_triangles.Add((int) AddPoint(points[1]));
              m_triangles.Add((int) AddPoint(points[2]));
              m_triangles.Add((int) AddPoint(points[5]));
              // 3
              m_triangles.Add((int) AddPoint(points[2]));
              m_triangles.Add((int) AddPoint(points[4]));
              m_triangles.Add((int) AddPoint(points[5]));
              // 4
              m_triangles.Add((int) AddPoint(points[2]));
              m_triangles.Add((int) AddPoint(points[3]));
              m_triangles.Add((int) AddPoint(points[4]));
          }
      }
  
      void AddPolygon(int x, int y, List<Vector2> positions, params int[] indices)
      {
          var points = new List<Point>();
          foreach (var index in indices)
          {
              var pos = positions[index];
              Point point = new Point(x, y, index, new Vector3(pos.x, 0, pos.y));
              points.Add(point);
          }
  
          AddPolygon(points.ToArray());
      }
  
      void ProcessQuadMesh(int x, int y, byte state, Vector2 center, float size)
      {
          var positions = new List<Vector2>()
          {
              new Vector2(center.x - size / 2, center.y - size / 2),
              new Vector2(center.x - size / 2, center.y),
              new Vector2(center.x - size / 2, center.y + size / 2),
              new Vector2(center.x, center.y + size / 2),
              new Vector2(center.x + size / 2, center.y + size / 2),
              new Vector2(center.x + size / 2, center.y),
              new Vector2(center.x + size / 2, center.y - size / 2),
              new Vector2(center.x, center.y - size / 2),
          };
  
          switch (state)
          {
              case 0b0000:
                  break;
              case 0b0001:
                  // line v1 v7
                  AddPolygon(x, y, positions, 0, 1, 7);
                  break;
              case 0b0010:
                  // line v5 v7
                  AddPolygon(x, y, positions, 6, 7, 5);
                  break;
              case 0b0011:
                  // line v1 v5
                  AddPolygon(x, y, positions, 0, 1, 5, 6);
                  break;
              case 0b0100:
                  // line v3 v5
                  AddPolygon(x, y, positions, 3, 4, 5);
                  break;
              case 0b0101:
                  // 6
                  // line v1 v3
                  // line v5 v7
                  AddPolygon(x, y, positions, 0, 1, 3, 4, 5, 7);
                  break;
              case 0b0110:
                  // line v3 v7
                  AddPolygon(x, y, positions, 6, 7, 3, 4);
                  break;
              case 0b0111:
                  // 7
                  // line v1 v3
                  AddPolygon(x, y, positions, 6, 0, 1, 3, 4);
                  break;
              case 0b1000:
                  // line v1 v3
                  AddPolygon(x, y, positions, 1, 2, 3);
                  break;
              case 0b1001:
                  // line v3 v7
                  AddPolygon(x, y, positions, 2, 3, 7, 0);
                  break;
              case 0b1010:
                  // 6
                  // line v1 v7
                  // line v3 v5
                  AddPolygon(x, y, positions, 2, 3, 5, 6, 7, 1);
                  break;
              case 0b1011:
                  // 7
                  // line v3 v5
                  AddPolygon(x, y, positions, 0, 2, 3, 5, 6);
                  break;
              case 0b1100:
                  // line v1 v5
                  AddPolygon(x, y, positions, 1, 2, 4, 5);
                  break;
              case 0b1101:
                  // 7
                  // line v5 v7
                  AddPolygon(x, y, positions, 2, 4, 5, 7, 0);
                  break;
              case 0b1110:
                  // 7
                  // line v1 v7
                  AddPolygon(x, y, positions, 4, 6, 7, 1, 2);
                  break;
              case 0b1111:
                  // 8
                  AddPolygon(x, y, positions, 0, 2, 4, 6);
                  break;
          }
      }
  }