I have recently written code to linearly subdivide a triangle to an arbitrary level, but I’m having trouble writing a version that doesn’t treat each triangle as independent.
In other words, I’d like to have a bit of code that can divide a triangle into four triangles and end up with no duplicated vertices. I’d like to be able to manipulate the vertices and not have any tearing, so all internal vertices need to be fully shared…
Anyone?
You can use Fattie’s method but you have to keep track of the newly generated vertices (unless you want just a Barycentric subdivision).
You can do this with a dictionary to store the new vertices along with the edge. Shared vertices means that two indices are referencing the same vertex. If two shared vertices build up an edge, the edge is shared as well. Usually you always have shared edges in a closed mesh. Since you insert a vertex in the middle of an edge, all triangles (usually 2) that share this edge have to use the same vertex.
Now it’s a good thing that Unity only supports 16 bit indices. You can just builld one unique 32 bit number from two indices to identify a certain edge. With a bitshift you can merge two indices into one number that is used in the dictionary. If another triangle wants to insert a new vertex in an edge, the function will check if this edge has already been processed. Note that an edge can be reversed so you have to test both cases. (If it’s a closed mesh the second triangle will always be reversed. Draw it on a piece of paper and you’ll see ;))
Here’s an example. Tested and works:
// C#
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class MeshHelper
{
static List<Vector3> vertices;
static List<Vector3> normals;
// [... all other vertex data arrays you need]
static List<int> indices;
static Dictionary<uint,int> newVectices;
static int GetNewVertex(int i1, int i2)
{
// We have to test both directions since the edge
// could be reversed in another triangle
uint t1 = ((uint)i1 << 16) | (uint)i2;
uint t2 = ((uint)i2 << 16) | (uint)i1;
if (newVectices.ContainsKey(t2))
return newVectices[t2];
if (newVectices.ContainsKey(t1))
return newVectices[t1];
// generate vertex:
int newIndex = vertices.Count;
newVectices.Add(t1,newIndex);
// calculate new vertex
vertices.Add((vertices[i1] + vertices[i2]) * 0.5f);
normals.Add((normals[i1] + normals[i2]).normalized);
// [... all other vertex data arrays]
return newIndex;
}
public static void Subdivide(Mesh mesh)
{
newVectices = new Dictionary<uint,int>();
vertices = new List<Vector3>(mesh.vertices);
normals = new List<Vector3>(mesh.normals);
// [... all other vertex data arrays]
indices = new List<int>();
int[] triangles = mesh.triangles;
for (int i = 0; i < triangles.Length; i += 3)
{
int i1 = triangles[i + 0];
int i2 = triangles[i + 1];
int i3 = triangles[i + 2];
int a = GetNewVertex(i1, i2);
int b = GetNewVertex(i2, i3);
int c = GetNewVertex(i3, i1);
indices.Add(i1); indices.Add(a); indices.Add(c);
indices.Add(i2); indices.Add(b); indices.Add(a);
indices.Add(i3); indices.Add(c); indices.Add(b);
indices.Add(a ); indices.Add(b); indices.Add(c); // center triangle
}
mesh.vertices = vertices.ToArray();
mesh.normals = normals.ToArray();
// [... all other vertex data arrays]
mesh.triangles = indices.ToArray();
// since this is a static function and it uses static variables
// we should erase the arrays to free them:
newVectices = null;
vertices = null;
normals = null;
// [... all other vertex data arrays]
indices = null;
}
}
Here’s the result:
Subdivided at runtime:
Also this function will manipulate the given mesh. You might want to create a new mesh and apply the changes to the new one. Also you propably need to call RecalculateBounds
edit
Keep in mind that a linear subdivide won’t improve the mesh in any way. It helps if you use vertex-lights to have more vertices, but the actual shape will stay the same. You would have to interpolate the new vertex based on the surface. You can move the new vertices along it’s normal based on the vertex normals / edge tangents of the neighbor vertices. A Cube mesh will always look like a cube, but a sphere for example could look a bit smoother if done correct.
If you want to improve your mesh i suggest to use a modelling software 
They have very complex and effective smoothing and optimisation algorithms.
second edit
Finally posted an advanced and more complete version of this helper on the UnifyCommunity (MeshHelper) (Pastebin backup)
Thanks for the code!
Here is one optimization for the edge lookup, so you don’t have to store the same edge twice.
uint t1 = ((uint)Mathf.Min(i1,i2) << 16) | (uint)Mathf.Max(i1,i2);
Cheers!