How to take a mesh of quad faces and return a mesh with triangle faces.
The principle of the algorithm is to look at each quad and split them into two triangles. It chooses the split by the shortest diagonal across the quad.
The code is written in C# for Rhino/Grasshopper, using the Rhino mesh structure. However, it can be easily adapted to any mesh application.
public Mesh Triangulate(Mesh x) { int facecount = x.Faces.Count; for (int i = 0; i < facecount; i++) { var mf = x.Faces[i]; if(mf.IsQuad) { double dist1 = x.Vertices[mf.A].DistanceTo(x.Vertices[mf.C]); double dist2 = x.Vertices[mf.B].DistanceTo(x.Vertices[mf.D]); if (dist1 > dist2) { x.Faces.AddFace(mf.A, mf.B, mf.D); x.Faces.AddFace(mf.B, mf.C, mf.D); } else { x.Faces.AddFace(mf.A, mf.B, mf.C); x.Faces.AddFace(mf.A, mf.C, mf.D); } } } var newfaces = new List<MeshFace>(); foreach (var mf in x.Faces) { if(mf.IsTriangle) newfaces.Add(mf); } x.Faces.Clear(); x.Faces.AddFaces(newfaces); return x; }
Before and after:
James
Thank you for sharing the algorithm! Does this triangulation works with non planar quads in Rhino too?
Thanks Yifan! Yes, it will work with non-planar quads too. Just be aware that the resultant mesh face won’t resemble a minimal surface since the face is split into only two triangles.
Hi James,
I am wondering if there might be a way to do the inverse – tri to quad mesh?
Thanks a lot!
Hi Tim,
It is possible – in fact there is already a component in Grasshopper which does this. It’s Quadrangulate, under the Mesh tab.
The algorithm for it is much more involved than going from quad to tri, however. I guess the main purpose of this post was not to demonstrate a quad-tri algorithm (because it’s so simple) but more to give a complete example on manipulating meshes in C#. I found a few interesting papers for tri-quad algorithms on StackOverflow here.