Dynamically combine verticies that share the same space

Question

I want to create a simple editor tool that will:

1. Combine all selected meshes
2. Automatically weld/combine verticies that are within 0.0001f of one another
3. Optimise mesh for best performance
4. Save as prefab for use

I know how to achieve 1/3 and can probably figure out 4. But how can I weld/combine verticies?

Subantarctic

Answer 1

You must not share equal vertices when their uv or normals are different, what usually happens at the edges of different faces, or to “close” a curved surface. Consider the Unity cube: it has 24 vertices (4 per face) instead of just 8, because the normals (and uv, I guess) are different at the edges.

In order to do a safer vertex reduction, you should also compare uv and normals of equal vertices. To further complicate matters, there may exist other less popular properties associated to each vertex, like uv2, tangents and colors, which should be compared too for a 100% safe vertex reduction (take a look at the Mesh doc for a complete list).

NOTE: I would also replace the first foreach by a regular for (int k=0;…;…) - I have not found any .NET doc ensuring that the foreach sequence also starts at 0.

Jonajonah

Thank you for clarifying that for me. My intention was not to reduce the number of vertices for improved performance, but rather to remove certain visual artefacts that occur on some joins. In Blender the process of welding solves the problem. My scene is procedurally generated at design time.

– Subantarctic

Answer 2

I think the answer is that this is not feasible. I have worked out how to write this logic and have points 1/3/4 working great. Here is the code that I wrote for step 2.

Whilst this does in fact weld the verticies together, it screws up the UV coordinates because it seems that there can only be one UV coordinate pair for each vertex. This has had the effect of (properly mapped->mirrored->stretched->mirrored->properly mapped->…)

If anybody knows how to solve this problem then that would be fantastic. Still, here is the welding code that I wrote should it be of any use to anybody:

	private void AutoWeld(Mesh mesh, float threshold) {
		Vector3[] verts = mesh.vertices;
		
		// Build new vertex buffer and remove "duplicate" verticies
		// that are within the given threshold.
		List<Vector3> newVerts = new List<Vector3>();
		List<Vector2> newUVs = new List<Vector2>();
		
		int k = 0;
		
		foreach (Vector3 vert in verts) {
			// Has vertex already been added to newVerts list?
			foreach (Vector3 newVert in newVerts)
				if (Vector3.Distance(newVert, vert) <= threshold)
					goto skipToNext;
			
			// Accept new vertex!
			newVerts.Add(vert);
			newUVs.Add(mesh.uv[k]);
			
		skipToNext:;
			++k;
		}
		
		// Rebuild triangles using new verticies
		int[] tris = mesh.triangles;
		for (int i = 0; i < tris.Length; ++i) {
			// Find new vertex point from buffer
			for (int j = 0; j < newVerts.Count; ++j) {
				if (Vector3.Distance(newVerts[j], verts[ tris *]) <= threshold) {*

_ tris = j;_
* break;*
* }*
* }*
* }*

* // Update mesh!*
* mesh.Clear();*
* mesh.vertices = newVerts.ToArray();*
* mesh.triangles = tris;*
* mesh.uv = newUVs.ToArray();*
* mesh.RecalculateBounds();*
* }*

Subantarctic

That was useful to me, thanks (I don't need the UV coordinates anyway). However, mesh.vertices = newVerts.ToArray(); generates an error because Unity apparently checks the number of vertices in mesh.vertices against the number of vertices referenced in mesh.triangles. I suspect this check was not performed in previous versions of Unity, which is why the script used to work, but doesn't anymore. Anyway, the fix was simple, you just have to do mesh.triangles = tris; before mesh.vertices = newVerts.ToArray(); instead of after.

– Pandarus

I am not sure why this was not working for you, but according to the Unity documentation the order in my answer is still correct: http://docs.unity3d.com/Documentation/ScriptReference/Mesh.html

– Subantarctic

You may just need to clear the mesh, I have updated my answer accordingly :)

– Subantarctic

I have tried implementing this, but it turned out as unacceptably slow. In the end I used a kd-tree to store and search the vertices, which, in my case, was 50x faster (that's not an exaggeration).

– Alanealanine

@Subantarctic Thanks so much for this! I'm actively trying to use this function but I am not exactly certain how threshold and bucketStep work together. For example, if I've both = .03 I can reduce a 12k vertice mesh to 1.7k vertices. If I change bucketStep to .04, the result is 1.4k vertices. And again if I change bucketStep to .01, the result is 1.7k. So you can see my confusion as changing the value in both directions doesn't seem to make sense. I want to adjust these values to keep more vertices depending on the size of my models. Please respond and advise. Thanks!

– Wye

Answer 3

Numberkruncher I modified your code to use uniform spatial partitioning. Now it should be like 100 times faster on large meshes. Hope this can help someone.

  public static void AutoWeld (Mesh mesh, float threshold, float bucketStep) {
    Vector3[] oldVertices = mesh.vertices;
    Vector3[] newVertices = new Vector3[oldVertices.Length];
    int[] old2new = new int[oldVertices.Length];
    int newSize = 0;

    // Find AABB
    Vector3 min = new Vector3 (float.MaxValue, float.MaxValue, float.MaxValue);
    Vector3 max = new Vector3 (float.MinValue, float.MinValue, float.MinValue);
    for (int i = 0; i < oldVertices.Length; i++) {
      if (oldVertices_.x < min.x) min.x = oldVertices*.x;*_

if (oldVertices_.y < min.y) min.y = oldVertices*.y;
if (oldVertices.z < min.z) min.z = oldVertices.z;
if (oldVertices.x > max.x) max.x = oldVertices.x;
if (oldVertices.y > max.y) max.y = oldVertices.y;
if (oldVertices.z > max.z) max.z = oldVertices.z;
}*_

// Make cubic buckets, each with dimensions “bucketStep”
int bucketSizeX = Mathf.FloorToInt ((max.x - min.x) / bucketStep) + 1;
int bucketSizeY = Mathf.FloorToInt ((max.y - min.y) / bucketStep) + 1;
int bucketSizeZ = Mathf.FloorToInt ((max.z - min.z) / bucketStep) + 1;
List[,] buckets = new List[bucketSizeX, bucketSizeY, bucketSizeZ];

// Make new vertices
for (int i = 0; i < oldVertices.Length; i++) {
// Determine which bucket it belongs to
int x = Mathf.FloorToInt ((oldVertices*.x - min.x) / bucketStep);*
int y = Mathf.FloorToInt ((oldVertices*.y - min.y) / bucketStep);*
int z = Mathf.FloorToInt ((oldVertices*.z - min.z) / bucketStep);*

// Check to see if it’s already been added
if (buckets[x, y, z] == null)
buckets[x, y, z] = new List (); // Make buckets lazily

for (int j = 0; j < buckets[x, y, z].Count; j++) {
Vector3 to = newVertices[buckets[x, y, z][j]] - oldVertices*;*
if (Vector3.SqrMagnitude (to) < threshold) {
old2new = buckets[x, y, z][j];
goto skip; // Skip to next old vertex if this one is already there
}
}

// Add new vertex
newVertices[newSize] = oldVertices*;*
buckets[x, y, z].Add (newSize);
old2new = newSize;
newSize++;

skip:;
}

// Make new triangles
int[] oldTris = mesh.triangles;
int[] newTris = new int[oldTris.Length];
for (int i = 0; i < oldTris.Length; i++) {
newTris = old2new[oldTris*];*
}

Vector3[] finalVertices = new Vector3[newSize];
for (int i = 0; i < newSize; i++)
finalVertices = newVertices*;*

mesh.Clear();
mesh.vertices = finalVertices;
mesh.triangles = newTris;
mesh.RecalculateNormals ();
mesh.Optimize ();
}

Kristoferkristoffer

this is really useful. thanks! i plugged it into my experimental marching cubes engine. any idea how i can stop it removing verts on the edge of chunks?

– Elwandaelwee

come to think of it.. i really need a solution that matches the normals up across the separate meshes where vertices are shared. this will only work across a single mesh i guess.

– Elwandaelwee

boxiness you code works really well. Would be great if you could provide code with possibility to update uv's as well.

– Bunion

what should be the values for threshold and bucketstep?

– Romeoromeon

@Subantarctic Thanks so much for this! I'm actively trying to use this function but I am not exactly certain how threshold and bucketStep work together. For example, if I've both = .03 I can reduce a 12k vertice mesh to 1.7k vertices. If I change bucketStep to .04, the result is 1.4k vertices. And again if I change bucketStep to .01, the result is 1.7k. So you can see my confusion as changing the value in both directions doesn't seem to make sense. I want to adjust these values to keep more vertices depending on the size of my models. Please respond and advise. Thanks!

– Wye

Answer 4

is Uv destroy for my try
but vertex working

Hyperthermia

Answer 5

@Subantarctic Thanks so much for this! I’m actively trying to use this function but I am not exactly certain how threshold and bucketStep work together. For example, if I’ve both = .03 I can reduce a 12k vertice mesh to 1.7k vertices. If I change bucketStep to .04, the result is 1.4k vertices. And again if I change bucketStep to .01, the result is 1.7k. So you can see my confusion as changing the value in both directions doesn’t seem to make sense. I want to adjust these values to keep more vertices depending on the size of my models. Please respond and advise. Thanks!

Wye

Answer 6

I found this tool, the Oasis Mesh Editor, that can Split Vertices and Merge Vertices back together, Oasis Mesh Editor | Modeling | Unity Asset Store

The Merge Verts tool also has a Max Tolerance setting so that only verts that are closer than this distance will be merged.

Hope this helps anyone looking =)

Poriferous