一、 概述 欢迎来到新一期的技术实践系列,今天我们来聊点轻松的。看到封面大家应该初见端倪了吧。我要声明我不是小黑子啊,我是带大家了解一个很简单的算法:MarchingSquare。网上搜索一下会发现这个算法讲解的人很少,其实它是MarchingCubes算法的简化版,游戏中常用于程序化地形生成。 这次的目标很简单:带你从零开始,借助Unity引擎去实现一个像素剪影风格效果。我会在第二章介绍MarchingSquare的核心原理,在第三章中,使用Unity和提到的核心原理,用一个简单脚本实现完整的功能。在第四章,我将给上面的功能添加一些额外的效果,让您可以成为一个合格小黑子。其余章节则是共同讨论关于这个算法的一些问题。大家可以根据需要,跳到对应的章节。 本次内容属于基础算法,只需要您有简单的数学几何基础和一点点的Unity经验即可。适合图形学新手。如果文中有什么错误或遗漏,欢迎指出;有任何疑问,请随时评论或私信告诉我。看在我拖更这么久的份上,大家点赞投币支持一下吧!没关注的也可以关注一下我哦!
二、 核心原理 MarchingSquare算法的核心思想是降采样的思想。想象一个连续的二维空间中,有着一片不规则区域,我们希望能通过一种方式直观的程序性的描述这片区域。因此我们先尝试将二维空间划分为均匀的正方形网格,逐个处理数据场中的方块(像素块),将划分后的方块顶点赋予0或1的值,表示当前顶点是否在区域内(0表示不在区域内,1表示在区域内部)。我们再引入一个等值面的概念,不规则区域的边界很明显就是一个等值面;细分到一个小方块内,四个顶点对应的16种情况(2^4)中,根据每种情况找到边线的插值得到一个等值面。 我找来一组图用于直观的解释,这是我提到的不规则区域: 尝试将二维空间划分为7*8的正方形网格区域: 顶点在图形内的标为红色,顶点在图形外的标为蓝色 将红色边界与蓝色蓝进行插值得到近似点 连接近似点,就得到了原始曲面的近似值 到此结束,是不是非常EZ,下面我们想想如何用伪代码来实现上面的思想:
1、 将二维平面栅格化,将栅格化的顶点存储下来,并为每个顶点赋随机值。 伪代码: Class MarchingPoint() { Vector2 pos; int value; } int size = Mathf.Sqrt(100); //存储全部划分出来的顶点 var pointList = new List<List<MarchingPoint>>(); for (int i = 0; i < size; i++) { var list = new List<Vector3>(); for (int j = 0; j < size; j++) { //得到划分后每个点的位置 Vector2 point = new Vector3((Screen.width/ size) *i, (Screen.height/size)*j); //随机赋0或1值 int color = Random.Range(0, 2); list.Add(point, color); } pointList.Add(llist); }
2、 栅格化后每个矩形有4个顶点,根据在内或在外的情况,将四个顶点标记为0或1,因此共有2^4 = 16中情况,将不同的情况进行插值连线,得到下图。聪明的小伙伴已经想到,我们可以用哈希将这十六种情况映射出来。 var square = pointList.GetSquareForeach(); int hash = square.a * 8 + square.b * 4 + square.c * 2 + square.d * 1; //两个顶点的中点表示插值等值面的端点 float offset = Vector3.Distance(pointList[0][0].pos, pointList[0][1].pos) / 2; var aa = pointList[i][j].pos + new Vector2(0, offset) var bb = pointList[i+1][j].pos + new Vector2(-offset, 0) var cc = pointList[i+1][j+1].pos + new Vector2(0, -offset) var dd = pointList[i][j+1].pos + new Vector2(offset, 0) //0和15的情况不用考虑 switch (hash) { case 1: DrawLine(aa, dd); break; case 2: DrawLine(cc, dd); break; case 3: ... }
三、 算法实践 来到Unity,让我们根据上面的伪代码实现一下吧!
四、 多一点细节 基本算法已经实现了,不过还是差点意思,我们丰富一下细节,做一个合格的小黑子。
五、MarchingCubes算法和性能问题 优势: ● 高精度表面重建能力 ● 实现难度适中 局限: ● 经典算法存在二义性问题 ● 生成网格存在锯齿状边缘 ● 大网格顶点的重复存储
六、总结 Marching Square算法是个很简单的基础算法,但是其中的思想大家可以借鉴:使用离散化的思想,将连续的图形拆分成可编程的逻辑单元。 基于此,大家也可以自己尝试实现一个MarchingCubes算法;或者如果您有尝试做像素风游戏的想法,也可以将这节课的内容融入进去;亦或者,如果您有AI领域相关的知识,也可以通过机器学习,将训练的点云通过这个算法拟合成mesh等等。这些都是我浅浅想到的可能的应用场景,如果能在某一天看到同学们做出自己的东西,我想应该是一件很不错的事情。感谢收看再见!
七、参考文献 https://www.cs.carleton.edu/cs_comps/0405/shape/marching_cubes.html https://paulbourke.net/geometry/polygonise/ https://urbanspr1nter.github.io/marchingsquares/

代码:
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;
public class MarchingSquare : MonoBehaviour
{
public int drawSize = 32;
public int eraseSize = 64;
public float count; // 总数
public int alpha; // 背景颜色
public RenderTexture renderTexture;
public GameObject pointPref; // 拖拽Hierarchy中的Dot到这里
public GameObject linePref;
public LineRenderer lineRenderer;
public Vector3 screenOffset;
private List<List<GameObject>> pointList = new List<List<GameObject>>();
private List<GameObject> lineList = new List<GameObject>();
private float offsetX;
private float offsetY;
private void Awake()
{
var size = Mathf.Sqrt(count);
for (int i = 0; i < size; i++)
{
var llist = new List<GameObject>();
for (int j = 0; j < size; j++)
{
var point = Instantiate(pointPref, transform);
RectTransform rect = point.GetComponent<RectTransform>();
rect.anchoredPosition = new Vector3((Screen.width/ size) *i, (Screen.height/size)*j, 0) + screenOffset;
//int color = Random.Range(0, 2);
//point.GetComponent<Image>().color = new Color(color, color, color, 1);
point.GetComponent<Image>().color = new Color(0, 0, 0, alpha);
llist.Add(point);
}
pointList.Add(llist);
}
offsetY = Vector3.Distance(pointList[0][0].GetComponent<RectTransform>().anchoredPosition, pointList[0][1].GetComponent<RectTransform>().anchoredPosition) / 2;
offsetX = Vector3.Distance(pointList[0][0].GetComponent<RectTransform>().anchoredPosition, pointList[1][0].GetComponent<RectTransform>().anchoredPosition) / 2;
}
/// <summary>
/// 从 RenderTexture 读取像素,并填充到 pointList 对应的 UI Image 上
/// </summary>
/// <param name="rt">要读取的 RenderTexture</param>
public void FillGridFromRenderTexture(RenderTexture rt)
{
// 1. 将 RenderTexture 激活到当前渲染缓冲
RenderTexture currentRT = RenderTexture.active;
RenderTexture.active = rt;
// 2. 创建一个 Texture2D 并读取像素
Texture2D tex = new Texture2D(rt.width, rt.height, TextureFormat.RGBA32, false);
tex.ReadPixels(new Rect(0, 0, rt.width, rt.height), 0, 0);
tex.Apply();
// 恢复原来的 RenderTexture
RenderTexture.active = currentRT;
// 3. 获取网格大小
int rows = pointList.Count;
if (rows == 0) return;
int cols = pointList[0].Count;
// 4. 遍历 pointList,把对应像素赋到每个 Image 上
// 注意:UI 坐标和纹理坐标 y 轴可能需要翻转
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
// 纹理中 x: i,y: j
// 如果画面上下颠倒,可以用 y = rt.height - 1 - j
int px = Mathf.FloorToInt((float)i / rows * rt.width);
int py = Mathf.FloorToInt((float)j / cols * rt.height);
Color c = tex.GetPixel(px, py);
if (c.r < 0.4f)
c = new Color(0, 0, 0, alpha);
else
c = new Color(1, 1, 1, alpha);
// 给 UI Image 上色
var img = pointList[i][j].GetComponent<Image>();
if (img != null)
img.color = c;
}
}
// 5. 清理临时 Texture2D(可选)
Destroy(tex);
}
public void Start()
{
MarchingSquareTest();
}
public void Update()
{
FillGridFromRenderTexture(renderTexture);
DeleteAllLine();
MarchingSquareTest();
if (Input.GetMouseButton(0))
{
var size = Mathf.Sqrt(count);
for (int i = 0; i < size; i++)
{
var llist = new List<GameObject>();
for (int j = 0; j < size; j++)
{
if (Vector3.Distance(Input.mousePosition, pointList[i][j].GetComponent<RectTransform>().anchoredPosition) < drawSize)
{
var point = pointList[i][j];
point.GetComponent<Image>().color = new Color(1, 1, 1, alpha);
}
}
}
DeleteAllLine();
MarchingSquareTest();
}
else if (Input.GetMouseButton(1))
{
var size = Mathf.Sqrt(count);
for (int i = 0; i < size; i++)
{
var llist = new List<GameObject>();
for (int j = 0; j < size; j++)
{
if (Vector3.Distance(Input.mousePosition, pointList[i][j].GetComponent<RectTransform>().anchoredPosition) < eraseSize)
{
var point = pointList[i][j];
point.GetComponent<Image>().color = new Color(0, 0, 0, alpha);
}
}
}
DeleteAllLine();
MarchingSquareTest();
}
}
public void MarchingSquareTest()
{
for (int i = 0; i < pointList.Count - 1; i++)
{
for (int j = 0; j < pointList[i].Count - 1; j++)
{
var aa = pointList[i][j].GetComponent<RectTransform>().anchoredPosition + new Vector2(0, offsetY);
var bb = pointList[i + 1][j].GetComponent<RectTransform>().anchoredPosition +new Vector2(-offsetX, 0);
var cc = pointList[i + 1][j + 1].GetComponent<RectTransform>().anchoredPosition +new Vector2(0, -offsetY);
var dd = pointList[i][j + 1].GetComponent<RectTransform>().anchoredPosition +new Vector2(offsetX, 0);
int a = (int)pointList[i][j].GetComponent<Image>().color.r;
int b = (int)pointList[i + 1][j].GetComponent<Image>().color.r;
int c = (int)pointList[i + 1][j + 1].GetComponent<Image>().color.r;
int d = (int)pointList[i][j + 1].GetComponent<Image>().color.r;
//pointList[i + 1][j].GetComponent<Image>().color.r;
//pointList[i + 1][j + 1].GetComponent<Image>().color.r;
//pointList[i][j + 1].GetComponent<Image>().color.r;
int hash = a * 8 + b * 4 + c * 2 + d * 1;
switch (hash)
{
case 1:
DrawLine(aa, dd);
break;
case 2:
DrawLine(cc, dd);
break;
case 3:
DrawLine(aa, cc);
break;
case 4:
DrawLine(bb, cc);
break;
case 5:
DrawLine(aa, dd);
DrawLine(bb, cc);
break;
case 6:
DrawLine(dd, bb);
break;
case 7:
DrawLine(aa, bb);
break;
case 8:
DrawLine(aa, bb);
break;
case 9:
DrawLine(bb, dd);
break;
case 10:
DrawLine(aa, dd);
DrawLine(bb, cc);
break;
case 11:
DrawLine(bb, cc);
break;
case 12:
DrawLine(aa, cc);
break;
case 13:
DrawLine(cc, dd);
break;
case 14:
DrawLine(aa, dd);
break;
}
}
}
}
public void DrawLine(Vector3 x, Vector3 y)
{
//lineRenderer.positionCount = 200;
//lineRenderer.useWorldSpace = false;
//lineRenderer.SetPosition(0, x);
//lineRenderer.SetPosition(1, y);
//lineRenderer.startWidth = 1f;
//lineRenderer.endWidth = 1f;
var line = Instantiate(linePref, transform);
Vector2 dir = y - x;
float length = dir.magnitude;
float angle = Mathf.Atan2(dir.y, dir.x) * Mathf.Rad2Deg;
// 设置位置、旋转和大小
line.GetComponent<RectTransform>().anchoredPosition = x; // 起点位置
line.GetComponent<RectTransform>().sizeDelta = new Vector2(length, 2); // 长度和宽度
line.GetComponent<RectTransform>().localEulerAngles = new Vector3(0, 0, angle); // 旋转角度
lineList.Add(line);
}
public void DeleteAllLine()
{
foreach (var line in lineList)
{
Destroy(line);
}
}
}
免责声明:本文系网络转载或改编,未找到原创作者,版权归原作者所有。如涉及版权,请联系删