Organize Triangles of a Subdivided Quad?

Question

How can I efficiently reorder the triangles of a plane, on different levels of subdivision, in a list and have triangle pairs that constitute quads? I know that there is some sort of mathematical pattern but I can't, for the life of me, figure it out. To visually explain my question further I have an image below showing my desired result, on the first three levels of subdivision. The numbers on the triangles are intended to represent that triangle's index in the array/list of triangles.

alt text

The code I found for subdivision is below, it's just simple subdivision without shared vertices (however, I do plan on writing a script that will share vertices).

 function subdivide() {
  
     verts = mesh.vertices;
     trigs = mesh.triangles;
     uvs = mesh.uv;
     norms = mesh.normals;
  
     Debug.Log("enter subdividing: "+verts.length);
  
     var nv = new Array(verts);
     var nt = new Array();
     var nu = new Array(uvs);
     var nn = new Array(norms);
  
     for(var i : int = 2;i<trigs.length;i+=3) {
  
         var p0trigwho : int = trigs[i-2];
         var p1trigwho : int = trigs[i-1];
         var p2trigwho : int = trigs[i];
 
         var p0trigwhere : int = i-2;
         var p1trigwhere : int = i-1;
         var p2trigwhere : int = i;
 
         var p0 : Vector3 = verts[p0trigwho];
         var p1 : Vector3 = verts[p1trigwho];
         var p2 : Vector3 = verts[p2trigwho];
 
         var pn0 : Vector3 = norms[p0trigwho];
         var pn1 : Vector3 = norms[p1trigwho];
         var pn2 : Vector3 = norms[p2trigwho];
 
         var pu0 : Vector2 = uvs[p0trigwho];
         var pu1 : Vector2 = uvs[p1trigwho];
         var pu2 : Vector2 = uvs[p2trigwho];
 
         var p0mod : Vector3 = (p0+p1)/2;    
         var p1mod : Vector3 = (p1+p2)/2;
         var p2mod : Vector3 = (p0+p2)/2;
 
         var pn0mod : Vector3 = ((pn0+pn1)/2).normalized;    
         var pn1mod : Vector3 = ((pn1+pn2)/2).normalized;
         var pn2mod : Vector3 = ((pn0+pn2)/2).normalized;
 
         var pu0mod : Vector2 = (pu0+pu1)/2;    
         var pu1mod : Vector2 = (pu1+pu2)/2;
         var pu2mod : Vector2 = (pu0+pu2)/2;
 
         var p0modtrigwho = nv.length;
         var p1modtrigwho = nv.length+1;
         var p2modtrigwho = nv.length+2;
 
         nv.push(p0mod);
         nv.push(p1mod);
         nv.push(p2mod);
 
         nn.push(pn0mod);
         nn.push(pn1mod);
         nn.push(pn2mod);
 
         nu.push(pu0mod);
         nu.push(pu1mod);
         nu.push(pu2mod);
 
         nt.Add(p0trigwho);
         nt.Add(p0modtrigwho);
         nt.Add(p2modtrigwho);
         
         nt.Add(p0modtrigwho);
         nt.Add(p1modtrigwho);
         nt.Add(p2modtrigwho);
         
         nt.Add(p2modtrigwho);
         nt.Add(p1modtrigwho);
         nt.Add(p2trigwho);
         
         nt.Add(p0modtrigwho);
         nt.Add(p1trigwho);
         nt.Add(p1modtrigwho);
         
     }    
  
     verts = nv.ToBuiltin(Vector3);
     norms = nn.ToBuiltin(Vector3);
     uvs = nu.ToBuiltin(Vector2);
     trigs = nt.ToBuiltin(int);
  
     //applyuvs();
     applymesh();
     //mesh.RecalculateNormals();
  
     Debug.Log("exit subdividing: "+trigs.length);
 }

Answer 1

I made a sketch to understand your code

Now, as you see, the green triangles are the new ones and the green small numbers are in which order they get generated. so your subdiv level 1 image is wrong - the tri0 of subdiv0 is turned into tri0-3 like in my pattern.... Actually depending how the vert 0-2 are ordered, the tri 0,3,2 will also rotate inside subiv0.tri0, just tri1 stays in the middle no matter what.

At the moment the triangles of the next level are kinda continous, meaning they stay grouped in the same order as the tris were one level below, however, the verts are all over the place, because you only add the new verts(red) at the end, but leave all old verts where they were in the vert list. this means if you have a model with 300 verts, the new 300 verts of the new level will be afterwards in the list and of course every level also reuses the old levels verts

300 subdiv0 verts
300 new subdiv1 verts
600 new subdiv2 verts
1200 new subdiv3 verts ...

So the new triangles will have verts from all 4 lists... there is fractal order in it, but that's not what you want. Also, I think that may hurt performance somewhere, because you have no data locality, so you need to jump all over the place in memory to get the verts of the continous triangle list. This will trash the processors cache all the time.

You said you wanted to keep pairs of triangles that make up a quad together. This is what you have to do:

You can't process by single triangles, because as you see, the tris of the subquads can come from 2 triangles (0,1 and 6,7 in your drawing), so you need to process triangle pairs and then create the new quads however you need them.

The above is the only thing you have to do, but because of the data locality reason, it's highly recommended, that you also recreate the verts array completely and not just add to the end. Same goes of course for everything else that is verts-based like normals and uvs, but the good news is, this will make index calculations a lot easier.

Organize Triangles of a Subdivided Quad?

1 Reply

Your answer

Welcome to Unity Answers

Follow this Question

Related Questions