Thursday, April 30, 2009

MeshLab V1.2.0 Released!

After more than one year from version 1.1.1, the long, long waited MeshLab v.1.2.0 has
been released! Jump over the main page and download it.

A sincere thank-you to every contributor and, in particular, to Guido Ranzuglia
that has willingly taken the demanding and onerous task of coordinating
(e.g. actually performing) the whole release process.
Next release cycles, in particular for bug fixing releases, will be much
With respect to v1.1.1 the list of new features is very very long, now more than 100 different filtering actions are provided. In the next post I will spot some of the most interseting algorithm that have been added. In the meantime just download and try it!

Wednesday, April 29, 2009

MeshLab at Archeo-Foss (2)

Yet another non technical post :)
I have just returned from the Rome ArcheoFoss workshop. Being one of the organizers I can be proud of the success of the event, more than 150 people from the archeological field attended to the event crowding the main room of the CNR central building. I did not think that such a strictly focused event could attract such a wide audience; it seems that the intersection of people that have a genuine interest in Archeology, believe in open solutions, and live in Italy is a significant set :).
We (Guido Ranzuglia was the speaker) kept a short (40 min) tutorial on MeshLab, to a very interested, non computer scientist, audience; hopefully in a short time there should be a video available.
Pleasant discoveries: MeshLab is already well known in the field as a low cost alternative of the well known big names in 3D scanning processing tools. I also discovered that MeshLab was included in a ArcheoOS a linux distribution targeted to Archeological people.

Friday, April 24, 2009

MeshLab at Archeo-Foss

Just a short news about one of the many public presentation of MeshLab.
This time we will talk about MeshLab at the Archeo-Foss Workshop, the fourth Italian workshop on Free software, Open source and Open formats in the archaeological field. The workshop will be held in Rome on April 27-28, and it will be centered on the importance of open source sw and process in archaeology, not only considering the price issues, but also taking into account, long term sustainability and process documentation issues.

As you can imagine in this field MeshLab well cover the role of the open source alternative of the various high priced systems for 3D scanning data processing (most of them are priced in the 10k~30k $ range). In the Cultural Heritage environment budget resources are ofter very scarce and cost issues are seriously considered. Here source solutions play a very important role.

We often collaborate with many different CH institutions, working on wonderful ancient masterpieces. Something that often fully repay the effort done in the processing...

Below a few of the Lunigiana statue menhir that we recently acquired and processed (precisely he did most of the job, thanks Marco!).

Wednesday, April 15, 2009

How to remove internal faces with MeshLab

A very common situation that often arise the cleaning of a model with a detailed interior in which you are not interested in (and you want to remove it once for ever!). For example consider this nice LEGO model: 200k faces. Most of the faces are hidden inside the model, used to describe the internal pieces and pegs: not very useful in most cases. We can remove them with MeshLab.

After starting the filter color->vertex ambient occlusion over the mesh (and after waiting a few seconds) we have computed both a per-vertex gray color and stored for each vertex an attribute with a occlusion value. Side note: MeshLab has a general purpose per vertex and per face scalar quantity that are used and interchanged by many different algorithms with a variety of different semantic; we call this scalar quantity "quality" for no good reason (lazyness), it is a generic scalar quantity, it could be occlusion value (like in this case), a geodesic distance from border, gaussian curvature.

Second note: Ambient occlusion greatly enhance the perception of 3D shapes! Nowadays everyone recognizes it, but a few years ago not a lot of people was really aware of that (I am a proud user of AO since 2001 for nice renderings of Cultural Heritage stuff :) and, more recently, for nice renderings of molecules ).

Back to the topic of removal of internal faces.

We now can exploit this per-vertex occlusion value to select all the faces that have all their three vertices with a very low occlusion value. That means that we remove all the faces that has no visible vertices. This is not an perfect solution, there are easy counter-examples where this approach could remove visible faces (but with hidden vertices): in most cases it works wells but a bit of caution is always recommended.
In the side figure you can see the select by vertex quality filter in action with the all the selected internal faces: 130k faces out of 200k were totally internal and can be safely removed leaving just 70k faces.

Friday, April 10, 2009

On the computation of vertex normals

Computing per-vertex normal is usually a rather neglected task. There is a very popular solution that is usually considered reasonable and good for all purposes, until you hit some nasty counter-examples... Short summary of the most common approaches:
  1. Compute an area weighted average of the normals of all the faces incident on the vertex. This is the classical approach, very handy, just because if you compute your face normals using a simple cross product between two edges of a triangle, you get for free a normal vector whose length is twice the triangle area. So just summing the un-normalized cross products gives you the right weights. Referred many many times as THE method for computing per vertex normals.
  2. Compute an angle weighted average of the normals of all the faces incident on the vertex. Probably first seen on [1]. Mathematically sound, in the sense that it catch the limit behavior of the surface in a local neighborhood of the vertex. Simple, but it requires some trigonometric computations, so it is usually neglected by hard core optimization fans.
  3. Use the "Mean Weighted by Sine and Edge Length Reciprocal" proposed by N. Max [2]. One of the many possible variations of smart weighting with the nice property of NOT using trigonometric computations.
Without going into gory details (that you can find in [3]), you should know that the classical approach can give rise to some VERY counter-intuitive normals. Below a practical example of the difference between the above three algorithms. Note how the direction of the normals on the top of the thin up-wedges is strongly biased by the underlying tessellation. Yes this is a rather badly triangulated nasty example, but this stuff happens.

Just for fun (and to overcome a bug in another algorithm) we have added the three explicit methods for computing normals in the latest beta of MeshLab. Personal, un-scientific, subjective feelings:
  1. simple but dangerous
  2. good
  3. almost good

[1] G. Thurmer, C. A. Wuthrich, "Computing vertex normals from polygonal facets"
Journal of Graphics Tools, 3 1998
[2] Nelson Max, "Weights for Computing Vertex Normals from Facet Normals", Journal of Graphics Tools, 4(2) (1999)
[3] S. Jin, R.R. Lewis, D. West, "A comparison of algorithms for vertex normal computations", The Visual Computer, 2005 - Springer

Tuesday, April 7, 2009

Creating Voronoi Sphere (2)

Second part of the description of how this voronoi sphere was created.

At the end of the previous post we ended with a thin surface representing a sphere holed with a voronoi pattern.

  1. convert the paper-thin surface to a solid structure.
    This can be done by exploiting the offsetting capabilities of MeshLab. The filter "Remeshing->Uniform Mesh Resampling". In this filter a mesh is re-sampled by building a uniform distance-field volumetric representation where each voxel contains the signed distance from the original surface. The surface is then reconstructed using the marching cube algorithm over this volume. Resolution of the volume obviously affects the resolution (and the processing time!) of the final mesh. The distance field representation allows to easily create offset surfaces. There are various options for building offset surfaces, I will discuss them deeply in another post, for now just set the "Precision" parameter to 1.0%, and the offset value to 53.0% and check the "Absolute Distance" flag. After a few tens of secs you should get something like the side figure.

  2. simplify a bit to get rid of the bad triangulation quality of a Marching Cube (there are a lot of thin bad shaped triangles around), a percentage reduction of .75 is usually enough to both reduce a bit the size of the mesh and to improve its quality without affecting in a significant way the precision of the result.

  3. Apply a few times the Filter Remeshing->Curvature flipping optimization, that improves how the triangles adapt to the shape of the curvature without increasing their number.

  4. Refine and smooth up to a mesh of approx 1.000.000 triangles.
    A rather overtessellated mesh is needed here to guarantee a good approximation of the geodesic distance.

  5. At this point we repeat no this dense mesh the same steps we did on the original sphere. E.g. all the steps described in the previous post:

    1. Generate 1000 poisson samples over the surface (it takes a bit of time this time...)

    2. Color the mesh according to the back distance from these samples (voronoi coloring filter)

    3. select the faces with quality in the range 0..epsilon

    4. invert selection and delete

    5. offset the thin surface to convert it into a watertight solid object. This final offsetting obviously require an higher precision (and higher processing times).

    6. Some iteration of simplify-optimize-refine-smooth just to beautify the final mesh.

And that's all! Varying a bit the parameters in the middle of the whole process greatly affect the final result. For example you can easily get a fat donut style by increasing the offsetting value. Below a high res snap done with meshlab with ambient occlusion, and thin antialiased wire frame lines. A real, touchable 3D print of the object can be obtained on Shapeways.