Metaballs using Marching Squares in Unity (Part I)

Arindam Bose 8:39 AM 1 Comment Edit

Keeping on the trend on simulating interesting things in Unity, this time I'm trying to get Metaballs working in Unity using the Marching Squares Algoritthm, SPOILER ALERT: This is how the final result looks like.

This "lava-lamp" like effect can be a achieved by using the Marching Squares algorithm to procedurally generate a Mesh from a regular grid of sampled scalars, to put it in simpler terms, the algorithm takes as input, a uniform 2D grid of floats, and generates from that grid, smooth closed curves that "wrap around" regions where the values are above/below a certain threshold.

Marching squares result with the threshold value set to 6, image shows two possible variations of curves which enclose regions where value of sampled scalar is >= 6.

Simulation and sampling

Doing this is fairly straightforward in Unity, I just set up a bunch of GameObjects with CircleCollider2D and RigidBody2D components set up as Triggers so that they pass through each other, and wrote some code inside FixedUpdate() so they bounced off some hard-coded world borders.

	// Update is called once per frame
	void FixedUpdate () {
	//World borders
	float halfWidth = VoxelSampleManager.width / 2;
	float halfHeight = VoxelSampleManager.height / 2;

	float xPos = transform.position.x;
	float yPos = transform.position.y;

	//Bounce off right side wall
	if ( xPos + radius > halfWidth)
	{
	_reflVelocity(Vector2.left);
	}

	//Bounce of left side wall
	if (xPos - radius < (-halfWidth))
	{
	_reflVelocity(Vector2.right);
	}

	//Bounce of top wall
	if (yPos + radius > halfHeight)
	{
	_reflVelocity(Vector2.down);
	}

	//Bounce off bottom wall
	if (yPos - radius < (-halfHeight))
	{
	_reflVelocity(Vector2.up);
	}
	}

	//Utility function to calculate reflected velocity
	void _reflVelocity(Vector2 normal)
	{
	Vector2 vel = _rbd2d.velocity;
	Vector2 reflVel = Vector2.Reflect(vel, normal);
	_rbd2d.velocity = reflVel;
	}

view raw CircularSampleable.cs hosted with ❤ by GitHub

I also started off each GameObject with a random velocity, so we get a bunch of circles bouncing inside an invisible box.

Now we need to get on with sampling a uniform grid of scalar values from these circles, for any circle with radius

$r$ and center

$(a,b)$ , a point

$(x,y)$ is inside the circle if:

$(x - a)^2 + (y - b)^2 \leq r^2$
Rearranging a bit we get,

$\frac{r^2}{(x - a)^2 + (y - b)^2} \ge 1$
We calculate the LHS of the above expression for each circle, and for each point in a grid inside our "invisible box".

To this I created a VoxelMapManager class, it stores the sampled values in a simple 2D array of floats, and is attached to an empty GameObject which is placed at the world origin.
I'll use the term "voxel" a lot in this project, its technically incorrect since a voxel is a cell in a 3D grid, but here we just have a 2D grid, but whatever.
I also added the function GetSampleAt(Vector2 pos) to the CircularSampleable class posted above to calculate samples for each circle. Its already attached to each circle for the physics sim.

	using UnityEngine;
	using System.Collections;
	using System.Collections.Generic;
	using System;

	public class VoxelSampleManager : MonoBehaviour {

	//Dimensions of the world
	public static float width = 15f;
	public static float height = 8f;

	//Size of each voxel in our grid
	public float voxelSize;
	public float threshold;

	//Center of the grid/world
	public Vector2 center;

	//Array which stores the samples
	public float[,] voxelSamples;

	private int numVoxelsX;
	private int numVoxelsY;

	public List<CircularSampleable> sampleableElements;

	void Awake()
	{
	//Calculate number of voxels in the grid based on size of map and size of each voxel
	numVoxelsX = Mathf.CeilToInt(width / voxelSize);
	numVoxelsY = Mathf.CeilToInt(height / voxelSize);

	voxelSamples = new float[numVoxelsY, numVoxelsX];

	}

	void Start()
	{

	}

	//Calculates the center of each voxel, given its (x,y) from the top - Left corner of the world.
	public Vector2 GetVoxelCenter(int x, int y)
	{
	Vector2 worldTopLeft = center - new Vector2(width / 2, -height / 2) + new Vector2(voxelSize / 2, -voxelSize / 2);
	return worldTopLeft + new Vector2(x * voxelSize, -y * voxelSize);

	}

	void SampleVoxels()
	{
	//For each grid point
	for (int y = 0; y < numVoxelsY; y++)
	{
	for (int x = 0; x < numVoxelsX; x++)
	{
	float total = 0f;
	//For each Circle
	foreach (CircularSampleable _circle in sampleableElements)
	{
	//Sum up the samples
	float sample = _circle.GetSampleAt(GetVoxelCenter(x, y));
	total += sample;
	}
	//Store it in the samples array
	voxelSamples[y, x] = total;
	}
	}
	}

	// Update is called once per frame
	void Update () {
	SampleVoxels();
	}
	}

view raw VoxelMapManager.cs hosted with ❤ by GitHub

Visual Debugging

This comes up super often when doing games/graphics related stuff, print's, logs and breakpoints help in very rare cases, it is always best to write a bunch of additional code to visualize the data you're debugging in the world, in this case we'll actually draw our voxels and their sample values at the positions their in the world, and we'll also color the voxels black if their sample value is above 1 (inside a circle)

OnDrawGizmos() and OnGUI() to the rescue!


	//Draws a cube at the center of each voxel.
	void _debugDrawVoxels()
	{
	for (int y = 0; y < numVoxelsY; y++)
	{
	for (int x = 0; x < numVoxelsX; x++)
	{
	Vector3 center = GetVoxelCenter(x,y);
	Vector3 size = new Vector3(voxelSize 0.5f , voxelSize0.5f, voxelSize*0.5f);
	Gizmos.color = Color.white;

	//Color is set to back if the voxel sample is above the threshold value
	if (voxelSamples[y, x] > threshold) Gizmos.color = Color.black;
	Gizmos.DrawCube(center, size);
	}
	}
	}

	//Draws the float values on top of the voxels
	void _debugDrawSamples()
	{
	for (int y = 0; y < numVoxelsY-1; y++)
	{
	for (int x = 0; x < numVoxelsX-1; x++)
	{
	Vector3 center = GetVoxelCenter(x, y);
	center.y *= -1;
	//Since OnGUI() worls in screenspace, translate world co-ordinates to screenspace.
	Vector2 labelPos = Camera.main.WorldToScreenPoint(center);
	GUI.Label(new Rect(labelPos.x - 20, labelPos.y, 100, 100), Math.Truncate(100 * voxelSamples[y, x]) / 100 + " ");
	}
	}
	}

	//Truncates the float values within a vector to two decimal places.
	string _truncStringify(Vector2 f)
	{
	float x = (float) Math.Truncate(100 * f.x)/100;
	float y = (float) Math.Truncate(100 * f.y)/100;
	return "{" + x + "," + y + "}";
	}

	//Draw the voxels
	void OnDrawGizmos()
	{
	if (DebugDraw)
	{
	_debugDrawVoxels();
	}

	}

	//Draw the sample values
	void OnGUI()
	{
	if (DebugDraw)
	{
	_debugDrawSamples();
	}
	}

view raw VoxelMapManager_Debug.cs hosted with ❤ by GitHub

Dump that code into VoxelMapManager with a DebugDraw flag you can set in the inspector. With a voxel size of 1, this is how the debug info should look.

Marching Squares

The high-level description of the Marching Squares Algorithm is pretty straightforward:

Construct a square by connecting four adjacent vertices.
Given the sample values at each vertex of the square, determine the mesh configuration from a lookup table (Picture below)
Calculate the position of the edge vertices using linear interpolation, this means that the edge vertex would lie at the point on the edge where the sample value would be equal to the threshold, assuming the samples are transitioning linearly between the voxels.
Mathematically, given point $P_1$ with sample value $s_1$ and point $P_2$ with sample value $s_2$ , point $P$ with a threshold value of $t$ would lie at:
$P = P_1 + \frac{t - s_1}{s_2 - s_1} * (P_2 - P_1)$
In our case $t=1$ .
According to the configuration from the table, add the vertices and triangles to the mesh.
March the square forward to the adjacent voxel and repeat the process.

Lookup Table Generation
I created a SquareMeshConfig class, instances of which represent each of the possible configurations shown in the image above. Each vertex is represented as an enum value such as TopLeft, TopRight, BottomCenter, etc. , and each instance contains a List of these types to represent which vertices need to be added. It also maintains a list of triangles, with a scheme identical to Unity's system(an array of vertex indices in clockwise order)

I then used a static size 16 array for the lookup table and one-time initialized it with the instance at each index representing the configuration from the image above.

	using UnityEngine;
	using System;
	using System.Collections;
	using System.Collections.Generic;

	//Types of vertices in each square
	public enum SquareVertexType
	{
	TopLeft,
	TopRight,
	BottomRight,
	BottomLeft,
	TopCenter,
	RightCenter,
	BottomCenter,
	LeftCenter
	}

	//Utility Triangle class
	public class Triangle
	{
	public int v1;
	public int v2;
	public int v3;
	}

	public class SquareMeshConfig {




	//The static lookup table
	private static SquareMeshConfig[] configMap;

	//List of vertices
	public List<SquareVertexType> vertices;
	//Temp dictionary used to make adding triangles to a config less manual
	Dictionary<SquareVertexType, int> vertexIndices;
	//List of triangles
	public List<Triangle> triangles;


	public SquareMeshConfig()
	{
	vertices = new List<SquareVertexType>(6);
	vertexIndices = new Dictionary<SquareVertexType, int>();
	triangles = new List<Triangle>();

	}

	public static void InitConfigMap()
	{
	configMap = new SquareMeshConfig[16];

	for (int i = 0; i < 16; i++)
	{
	configMap[i] = SquareMeshConfig.CreateMeshConfig(i);
	}
	}

	public static SquareMeshConfig GetMeshConfig(int squareIndex)
	{
	if (configMap == null)
	{
	SquareMeshConfig.InitConfigMap();
	}

	return configMap[squareIndex];
	}

	//Creates a mesh config for a specified index
	private static SquareMeshConfig CreateMeshConfig(int squareIndex)
	{
	SquareMeshConfig config = new SquareMeshConfig();

	//Add three vertexTypes to create a triangle
	//AddTriangle automatically keeps track of dulicates using the temp dictionary and creates vertex indices accordingly
	switch (squareIndex)
	{
	case 1:
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.TopCenter,
	SquareVertexType.LeftCenter
	);
	break;
	case 2:
	config.AddTriangle(
	SquareVertexType.TopCenter,
	SquareVertexType.TopRight,
	SquareVertexType.RightCenter
	);
	break;
	case 3:
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.RightCenter,
	SquareVertexType.LeftCenter
	);
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.TopRight,
	SquareVertexType.RightCenter
	);
	break;
	case 4:
	config.AddTriangle(
	SquareVertexType.BottomCenter,
	SquareVertexType.RightCenter,
	SquareVertexType.BottomRight
	);
	break;
	case 5:
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.TopCenter,
	SquareVertexType.RightCenter
	);
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.RightCenter,
	SquareVertexType.BottomRight
	);
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.BottomRight,
	SquareVertexType.BottomCenter
	);
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.BottomCenter,
	SquareVertexType.LeftCenter
	);
	break;
	case 6:
	config.AddTriangle(
	SquareVertexType.TopCenter,
	SquareVertexType.BottomRight,
	SquareVertexType.BottomCenter
	);
	config.AddTriangle(
	SquareVertexType.TopCenter,
	SquareVertexType.TopRight,
	SquareVertexType.BottomRight
	);
	break;
	case 7:
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.BottomRight,
	SquareVertexType.BottomCenter
	);
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.BottomCenter,
	SquareVertexType.LeftCenter
	);
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.TopRight,
	SquareVertexType.BottomRight
	);
	break;
	case 8:
	config.AddTriangle(
	SquareVertexType.LeftCenter,
	SquareVertexType.BottomCenter,
	SquareVertexType.BottomLeft
	);
	break;
	case 9:
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.BottomCenter,
	SquareVertexType.BottomLeft
	);
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.TopCenter,
	SquareVertexType.BottomCenter
	);
	break;
	case 10:
	config.AddTriangle(
	SquareVertexType.LeftCenter,
	SquareVertexType.TopCenter,
	SquareVertexType.BottomLeft
	);
	config.AddTriangle(
	SquareVertexType.BottomLeft,
	SquareVertexType.TopCenter,
	SquareVertexType.TopRight
	);
	config.AddTriangle(
	SquareVertexType.BottomLeft,
	SquareVertexType.TopRight,
	SquareVertexType.BottomCenter
	);
	config.AddTriangle(
	SquareVertexType.BottomCenter,
	SquareVertexType.TopRight,
	SquareVertexType.RightCenter
	);
	break;
	case 11:
	config.AddTriangle(
	SquareVertexType.BottomLeft,
	SquareVertexType.TopLeft,
	SquareVertexType.TopRight
	);
	config.AddTriangle(
	SquareVertexType.BottomLeft,
	SquareVertexType.TopRight,
	SquareVertexType.BottomCenter
	);
	config.AddTriangle(
	SquareVertexType.BottomCenter,
	SquareVertexType.TopRight,
	SquareVertexType.RightCenter
	);
	break;
	case 12:
	config.AddTriangle(
	SquareVertexType.BottomLeft,
	SquareVertexType.LeftCenter,
	SquareVertexType.BottomRight
	);
	config.AddTriangle(
	SquareVertexType.LeftCenter,
	SquareVertexType.RightCenter,
	SquareVertexType.BottomRight
	);
	break;
	case 13:
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.BottomRight,
	SquareVertexType.BottomLeft
	);
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.TopCenter,
	SquareVertexType.BottomRight
	);
	config.AddTriangle(
	SquareVertexType.TopCenter,
	SquareVertexType.RightCenter,
	SquareVertexType.BottomRight
	);
	break;
	case 14:
	config.AddTriangle(
	SquareVertexType.LeftCenter,
	SquareVertexType.TopCenter,
	SquareVertexType.BottomLeft
	);
	config.AddTriangle(
	SquareVertexType.BottomLeft,
	SquareVertexType.TopCenter,
	SquareVertexType.TopRight
	);
	config.AddTriangle(
	SquareVertexType.TopRight,
	SquareVertexType.BottomRight,
	SquareVertexType.BottomLeft
	);
	break;
	case 15:
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.BottomRight,
	SquareVertexType.BottomLeft
	);
	config.AddTriangle(
	SquareVertexType.TopLeft,
	SquareVertexType.TopRight,
	SquareVertexType.BottomRight
	);
	break;
	default: break;
	}

	return config;
	}


	public void AddTriangle(SquareVertexType _v1, SquareVertexType _v2, SquareVertexType _v3)
	{
	//Initial vertex indices
	int v1_i = -1;
	int v2_i = -1;
	int v3_i = -1;

	//Check id specifed vertex is already added to Config
	bool v1Found = vertexIndices.TryGetValue(_v1, out v1_i);
	bool v2Found = vertexIndices.TryGetValue(_v2, out v2_i);
	bool v3Found = vertexIndices.TryGetValue(_v3, out v3_i);

	//If any vertex is already added then use its index from the dictionary, else append it to the end of the vertices array and update that new index into the temp dictionary.

	if ( !v1Found)
	{

	v1_i = vertices.Count;
	vertices.Add(_v1);
	vertexIndices.Add(_v1, v1_i);
	}

	if ( !v2Found)
	{
	v2_i = vertices.Count;
	vertices.Add(_v2);
	vertexIndices.Add(_v2, v2_i);
	}

	if ( !v3Found)
	{
	v3_i = vertices.Count;
	vertices.Add(_v3);
	vertexIndices.Add(_v3, v3_i);
	}

	triangles.Add(new Triangle{
	v1 = v1_i,
	v2 = v2_i,
	v3 = v3_i
	});
	}

	public override string ToString()
	{
	string toRet = "{ vertices: [\n";
	foreach (SquareVertexType vert in vertices)
	{
	toRet += vert.ToString() + ",\n";
	}
	toRet += "] , triangles : [ \n";
	foreach (Triangle tri in triangles)
	{
	toRet += string.Format(" [{0}, {1} , {2}] ,", tri.v1, tri.v2, tri.v3);
	}
	toRet += "]}";
	return toRet;
	}


	public static void Test()
	{

	for (int i = 0; i < 16; i++)
	{
	Debug.Log(SquareMeshConfig.GetMeshConfig(i));
	}
	}
	}

view raw SquareMeshConfig.cs hosted with ❤ by GitHub

Mesh Generation
To start off with the mesh generation we need to map the set of four adjacent sample values to one of the configurations in the lookup table. Generating the index is actually fairly simple, you can generate a 4-bit number where each bit represents a sample corner in a square, its set to 1 if the sample value is above threshold, its 0 otherwise. The top left sample corresponds to the LSB and we go in a clockwise order with the bottom left corner corresponding to the MSB.

I've created a simple Square struct that stores the sample values for each corner, and provides properties to access the positions of each corner, it even calculates the LERP'ed positions for the edge vertices based on the sample values, and lastly, uses the bit mapping logic to create the lookup index.

	using UnityEngine;
	using System.Collections;

	public struct Square
	{
	//Corner sample values
	public float TopLeftSample { get; private set; }
	public float TopRightSample { get; private set; }
	public float BtmLeftSample { get; private set; }
	public float BtmRightSample { get; private set; }

	//Corner positions
	public Vector2 TopLeftPos { get; private set; }
	public Vector2 TopRightPos { get; private set; }
	public Vector2 BtmLeftPos { get; private set; }
	public Vector2 BtmRightPos { get; private set; }

	//Edge point positions
	public Vector2 LeftEdgePos
	{
	get
	{
	return getLerpEdgePt(TopLeftPos, TopLeftSample, BtmLeftPos, BtmLeftSample);
	}
	}
	public Vector2 TopEdgePos
	{
	get
	{
	return getLerpEdgePt(TopLeftPos, TopLeftSample, TopRightPos, TopRightSample);
	}
	}
	public Vector2 RightEdgePos
	{
	get
	{
	return getLerpEdgePt(TopRightPos, TopRightSample, BtmRightPos, BtmRightSample);
	}
	}
	public Vector2 BtmEdgePos
	{
	get
	{
	return getLerpEdgePt(BtmLeftPos, BtmLeftSample, BtmRightPos, BtmRightSample);
	}
	}

	public Vector2 Center
	{
	get
	{
	return (TopLeftPos + TopRightPos + BtmLeftPos + BtmRightPos) / 4.0f;
	}
	}



	public Square(int x, int y, VoxelSampleManager map)
	{

	float[,] grid = map.voxelSamples;
	int width = grid.GetLength(1);
	int height = grid.GetLength(0);

	if (x == width \|\| y == height) Debug.LogError("You cannot get a square at the edge of the voxel map");
	//store samples
	this.TopLeftSample = grid[y, x];
	this.TopRightSample = grid[y, x + 1];
	this.BtmLeftSample = grid[y + 1, x];
	this.BtmRightSample = grid[y + 1, x + 1];

	//store corner positions from the map
	this.TopLeftPos = map.GetVoxelCenter(x, y);
	this.TopRightPos = map.GetVoxelCenter(x + 1, y);
	this.BtmLeftPos = map.GetVoxelCenter(x, y + 1);
	this.BtmRightPos = map.GetVoxelCenter(x + 1, y + 1);
	}

	//Bit-masking logic which generates the index to reference to the appripriate SquareMeshCOnfig
	public int GetSquareIndex(float threshold)
	{
	int topLeftVal = (TopLeftSample > threshold) ? 1 : 0;
	int topRightVal = (TopRightSample > threshold) ? (1 << 1) : 0;
	int btmRightVal = (BtmRightSample > threshold) ? (1 << 2) : 0;
	int btmLeftVal = (BtmLeftSample > threshold) ? (1 << 3) : 0;

	return topLeftVal \| topRightVal \| btmRightVal \| btmLeftVal;
	}

	public void DebugDraw()
	{
	Debug.DrawLine(this.TopLeftPos, this.TopRightPos, Color.green);
	Debug.DrawLine(this.TopRightPos, this.BtmRightPos, Color.green);
	Debug.DrawLine(this.BtmRightPos, this.BtmLeftPos, Color.green);
	Debug.DrawLine(this.BtmLeftPos, this.TopLeftPos, Color.green);
	}

	//Calculates linearly interpolated edge points.
	private Vector2 getLerpEdgePt(Vector2 v1, float s1, Vector2 v2, float s2)
	{
	float fracFromv1 = (1.0f - s1) / (s2 - s1);
	return v1 + (v2 - v1) * fracFromv1;
	}



	}

view raw Square.cs hosted with ❤ by GitHub

Now all thats left is wiring the two classes together by looking up the appropriate SquareMeshConfig for a specific Square and parsing it to add the appropriate data to to Unity's vertex and triangle buffers.
I implemented all of this inside a MarchingSquaresMeshGenerator class, it also provides a bunch of lifecycle methods that can clear the buffers at the start of each frame, generating the mesh data from Square instances and copy the buffers over to Unity's Mesh API for rendering once all the squares are added.

	using UnityEngine;
	using System;
	using System.Collections;
	using System.Collections.Generic;

	public class MarchingSquaresMeshGenerator {

	//the generated mesh object
	Mesh _generatedMesh;

	//Veretx and triangle buffers
	Vector3[] vertices;
	int[] triangles;

	int vertexCount = 0;
	int triCount = 0;

	public MarchingSquaresMeshGenerator(){
	_generatedMesh = new Mesh();
	vertices = new Vector3[5000];
	triangles = new int[3*5000];
	Reset();
	}

	//Clear the buffers and reset counters, use this at the start of teh frame
	public void Reset()
	{
	_generatedMesh.Clear();
	Array.Clear(vertices, 0, vertexCount);
	Array.Clear(triangles,0, triCount);
	vertexCount = 0;
	triCount = 0;
	}

	//Use this once all the squares have been parsed to copy the buffers over for rendering
	public void Generate(MeshFilter mf)
	{
	_generatedMesh.vertices = vertices;
	_generatedMesh.triangles = triangles;
	mf.mesh = _generatedMesh;
	}

	//Add a square to the mesh, this method looks up the configuration and calls the utility parser function
	public void AddSquareToMesh(Square square, float threshold)
	{
	SquareMeshConfig sqConfig = SquareMeshConfig.GetMeshConfig(square.GetSquareIndex(threshold));
	parseConfig(square, sqConfig, threshold);
	}

	//Utility function to add a triangle
	private void addTriangle(int v1, int v2, int v3)
	{
	triangles[triCount] = v1;
	triCount++;

	triangles[triCount] = v2;
	triCount++;

	triangles[triCount] = v3;
	triCount++;
	}

	//Utility function to add a vertex
	private void addVertex(Vector3 v)
	{
	vertices[vertexCount] = v;
	vertexCount++;
	}

	//This parses the config and generates the vertices
	private void parseConfig(Square square, SquareMeshConfig sqConfig, float threshold)
	{
	List<SquareVertexType> sqVertices = sqConfig.vertices;

	//Since each SquareMeshConfig contains vertex indices for each square in isolation, we use the current vertex count to offset the indices.
	int initVertOffset = vertexCount;
	for (int vert_i = 0; vert_i < sqVertices.Count; vert_i++)
	{
	SquareVertexType sqVert = sqVertices[vert_i];

	Vector3 vertPos = Vector3.zero;

	//Maps a SquareVertexType to a position from the Square
	switch (sqVert)
	{
	case SquareVertexType.TopLeft :
	vertPos = square.TopLeftPos;
	break;
	case SquareVertexType.TopRight:
	vertPos = square.TopRightPos;
	break;
	case SquareVertexType.BottomRight:
	vertPos = square.BtmRightPos;
	break;
	case SquareVertexType.BottomLeft:
	vertPos = square.BtmLeftPos;
	break;
	case SquareVertexType.TopCenter:
	vertPos = square.TopEdgePos;
	break;
	case SquareVertexType.RightCenter:
	vertPos = square.RightEdgePos;
	break;
	case SquareVertexType.BottomCenter:
	vertPos = square.BtmEdgePos;
	break;
	case SquareVertexType.LeftCenter:
	vertPos = square.LeftEdgePos;
	break;
	default: break;
	}

	addVertex(vertPos);

	}


	List<Triangle> sqTris = sqConfig.triangles;
	for (int tri_i = 0; tri_i < sqTris.Count; tri_i++)
	{
	Triangle sqTri = sqTris[tri_i];

	addTriangle(
	initVertOffset + sqTri.v1,
	initVertOffset + sqTri.v2,
	initVertOffset + sqTri.v3
	);
	}
	}
	}

view raw MarchingSquaresMeshGenerator.cs hosted with ❤ by GitHub

Using a MonoBehavior script as a controller for an instance of the above class and passing in the appropriate squares gives you this cool result.

Issues

While everything looks correct, a quick peak at the Stats panel shows us that our Vertex count hovers around 1.7k and peaking at about 2k vertices. Yikes!

This happens because we process each square independently and generate a completely new set of vertices, but in reality each Square shares vertices with adjacent squares

The same value for the central vertex in red gets added to the vertex buffer four times, the blue edge vertices which are shared between two squares get added twice.

We can eliminate this by caching vertex indices from the adjacent squares during our generation loop.

There's also the fact that the sampling and generation loops are quite slow because of the sheer number of samples needed.

Since this is C# theres also a lot of GC being invoked as the Mesh data gets copied from my bufers to Unity's Mesh API buffers.

But these are issues I will (attempt) to deal with in Part II!

Pixel Hacking

Metaballs using Marching Squares in Unity (Part I)

Simulation and sampling

Marching Squares

Issues

Share this:

CONVERSATION

1 comments :