- Home /
Does anyone have any code to subdivide a mesh and keep vertices shared?
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?
Hi!
I'm working on almsot same issue, but I'm using C#. Yesterday I've created a script for making icosahedron. Today I wanted to take care about subdividing each triangle, hovewer I met a problem. Let's say I've got a mesh of 12 vertices created by hand
$$anonymous$$esh meshgrid = new $$anonymous$$esh();
meshgrid.vertices = new Vector3[] {
new Vector3(-1, t, 0)*size,
new Vector3( 1, t, 0)*size,
new Vector3(-1, -t, 0)*size,
new Vector3( 1, -t, 0)*size,
new Vector3( 0, -1, t)*size,
new Vector3( 0, 1, t)*size,
new Vector3( 0, -1, -t)*size,
new Vector3( 0, 1, -t)*size,
new Vector3( t, 0, -1)*size,
new Vector3( t, 0, 1)*size,
new Vector3(-t, 0, -1)*size,
new Vector3(-t, 0, 1)*size
};
I'm also defining a triangles and other stuff. That works flawlessy. Now, during subdivision I have to add more verts to the meshgrid.vertices array. But how can I do it, while arrays in C# are static? I've already tried Dictionary, ArrayList, but, without success.
It's funny you should mention that, $$anonymous$$adman07, that is exactly what I am doing...
[Editing this down for clarity to the answer that worked] I have a post in the WIP forum that has links to three (so far) evolutionary stages of my planetary globe project. Interested parties should have no problem finding the post
Answer by Bunny83 · May 29, 2012 at 12:04 PM
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:
Don't forget that's just an example. You should add all the arrays you might need as well like UV / tangent / color ...
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)
Ok it might be a bit too advanced but i try to explain it a bit more in detail:
A mesh can have shared edges. A closed mesh actually have all it's edges shared with another triangle, otherwise it wouldn't be closed.
As seen in the image, you have to insert 3 new vertices (a,b,c) into each of the triangles edges which actually split the edge at this point in two edges. If the edge (the two vertices 2 and 3) is shared by another triangle, both triangles should use the same vertex. So the new vertex "b" and "d" should be shared.
I used the dictionary to store the edge itself (which is identified by it's two vertices). The newly generated vertex index (appended at the end of the list so the new index is the current count) is now stored in the dictionary along with it's edge. If another triangle wants now to insert the same vertex (between "2" and "3") it will find the edge in the dictionary and can directly use the stored index.
The direction of the edge is usually reversed in the other triangle (as long as they face the same direction). So triangle T1 uses the edge 2-3 and triangle T2 uses 3-2 so i test both versions in the dictionary.
Hopefully that wasn't too long-winded ;)
btw: i've also created a version that divides into 9 triangles. I will put in on the unify community when it's ready ;)
@Tasarran: To use it you just have to call the Subdivide function with your mesh ;)
My test script looks like this:
public MeshFilter MF;
void Start()
{
Mesh m = MF.mesh;
MeshHelper.Subdivide(m);
MeshHelper.Subdivide(m); // two times :D
MF.mesh = m;
}
Just drag any gameobject with a meshfilter onto the variable and the mesh will get subdivided at start.
It works PERFECTLY.
You are my new official hero, Bunny!
And may I say, you are a GENIUS!
[EDIT: and it is FAST! It can subdivide seven times in less than a second! (it hits the vertex limit at 8 times, but that's to be expected, and my use shouldn't require more than 5...) And thanks for putting the comments about where to add the other arrays, I've already adapted it to subdivide the uvs as well.
You know Bunn, after all these years I am still mystified by this one!
To be clear:
(1) You're using a dictionary with the (EXTRE$$anonymous$$ELY) ingenious trick of putting the two 16 bit numbers together.
But the incredible question for me on this is:
Why?
What possible reason would you want to do this?
Why not just use normal program$$anonymous$$g? (Like "an array" say! :) )
I don't get it. It's just a totally boring, everyday program$$anonymous$$g problem, like "rendering text" or some accounting guys using SQL you know.
I lose sleep over this one :)
Let me reiterate (joke!!) that this is an EXTRE$$anonymous$$ELY ingenious trick, but I don't get why (you're much younger than me - it's not 1960 anymore - there is no performance program$$anonymous$$g. if you look up "program$$anonymous$$g" in a dictionary it just says "maintainability", there is nothing else, it is a one-note universe)
@Fattie:
Well ;) That's simply because for each edge (two indices) we need to add a new vertex. However an adjacent triangle (which shares the same edge) need to find the correct new generated vertex for this particular edge. Since the edge would be reverted for an adjacent triangle triangle i have to test both cases A--B and B--A. As lookup table i used a dictionary to lookup a certain edge. Since the edge can be inverted i test for both veriants.
Do you have a simpler way to match a new index to an edge (two indices pair)?
Your answer
Follow this Question
Related Questions
Terrain Triangle Generation 1 Answer
How can I ADD vertices and faces to a mesh? 1 Answer
Weird triangle indexing problem 1 Answer
Render mesh by specifying color of triangle 1 Answer
Iterate pixels of texture exactly once 0 Answers