Meshlab’s auto-triangulation of OFF input files

An interesting note about the ubiquitous OFF file format (Object File Format) and a small problem one may find when using the famous Meshlab program to open files of this format.

Consider a very simple shape – a cube tube.

First, let’s look at it in OpenSCAD, a source-code based CAD program developed by Marius Kintel and Clifford Wolf.

difference()
{
  cube(10);
  translate([1,1]) cube([8,8,10]);
}

Screenshot from 2013-05-06 22:50:43

Not too complicated. It’s just one cube subtracted from another. The ‘subtracted’ part are the ‘green’ faces on the inside of the cube. OpenSCAD’s CGAL and OpenCSG engines can both ‘detect’ the faces that are results of subtractions and color them green.

Now, of course it is not simply faces that are stored in a computer when dealing with geometry, it is also vertexes and links between them (edges). Here is the basic structure of the CGAL Nef Polyhedron edges underlying the OpenSCAD shape:

Screenshot from 2013-05-06 22:57:27

Notice that the faces are just flat. Most of them have four edges. There are two special faces though, the ‘top’ and ‘bottom’ of the tube – where the ‘hole’ of the inner cube is created. It is sort of a square donut. It doesn’t have four edges, it has 8 edges. It doesn’t have 4 vertexes either, it has 8.

donut

That is interesting… because many other graphics system require faces to be triangles or quadrilaterals. For example, OpenGL requires everything to be Quads or Triangles. The STL format, which is used in many 3d-printers, requires only triangles. How do we get from these CGAL Nef Polyhedron shapes to simpler shapes like triangles?

Well, it’s called Tessellation. Actually, a lot of different things are called Tessellation so it can be a bit confusing when you do a google search. But for our purpose here, we are using the word Tessellation to refer to the, well, the ‘covering’ of a polygon on a computer by simpler shapes.

So. Let’s imagine for a minute that we ‘tessellate’ our square donut into simple shapes. In fact, let’s imagine that we use the Straight Skeleton method, from CGAL.

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html

Screenshot from 2013-05-06 23:07:01

See? It took the polygon with 8 sides and 8 vertexes and broke it down into 8 separate polygons, each with only four sides and four vertexes – none of which have holes. Is this the simplest breakdown? No. But is it a tessellation? Yes, yes it is!

Now. Imagine we export this to OFF Format, and tessellate each polygon of the cube-tube with the Straight Skeleton method. What do we get?

Let’s look at it in GeomView, a program that grew out of the Geometry Center at the University of Minnesota in the mid 1990s, which is now closed. You can read about this remarkable organization on wikipedia: http://en.wikipedia.org/wiki/The_Geometry_Center

Screenshot from 2013-05-06 21:41:30

See? There is our ‘square donut’, tessellated by the Skeleton algorithm. Also note that the ‘inside’ rectangles have also been skeleton-tessellated. The Skeleton Algorithm does that to rectangles. It’s just the way it works. If you actually look at enough Skeletons tessellations, they actually look like roofs of houses. You can read about this on the CGAL page linked above.

OK. Now for the point of the article. What happens when you view this same OFF file in Meshlab?

You get this:

Screenshot from 2013-05-06 21:47:17

You see what they did there? They took all our nice symmetrical Skeletonized faces and made them into triangles.

That’s just what Meshlab does when it imports OFF files. Now, the OFF file itself doesn’t say to do this. The OFF Format is quite clear on what it means by faces, vertices, edges, etc. OFF is perfectly capable of storing funky shapes like our square donut, above, or our Skeleton tessellated shapes too. That’s what GeomView shows.

But Meshlab seems to be triangulating everything that comes in through OFF. That’s a bit tricky!

Here’s why.

Imagine you want to do something with the mesh, like, say, Subdivision Surfaces, which are used in computer graphics programs to ‘smooth’ a surface. The algorithm that does the smoothing will have different results depending on the underlying meshes used….

even if the ‘shape’ defined by the various meshes is the same.

This can lead to different shapes being created, given the same starting shape and smoothing algorithm…. it can also lead to ‘artefacts’ of smoothing, like little lumps that one wouldn’t expect to be there.

A great explanation of this has been put on Youtube by the Guerilla CG project, here:

I will cover this more in my next blog post but this post, about meshlab auto-triangulating OFF format files, now must come to an end.

Advertisements

About donbright

don bright http://github.com/donbright
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s