MeshLab JS 16.01 Tutorial

A new release of MeshLabJS, the javascript version of meshlab is out.

Obviously being a totally client based, run-in-browser application it is sufficient to open its web page to get the latest version. :). For a mesh processing system that runs inside your browser a new version is just the deploy of the html+js code on the server.

Now a very simple tutorial of what you can do with MeshLabJS v16.01: Remeshing, Comparing two meshes and showing the results.

Start it by simply opening the following web page:

http://www.meshlabjs.net

Press CTRL+f (or ⌘+f on OSX) to jump to the find box and type 'torus'. While you type the long list of available filters will reduce to only the ones matching with the typed text (in this case just one).

Click on the 'Create Torus' filter box and it will open to reveal the parameters. Just increase the 'Subdivision' parameter to 64 and press the '▶︎' (apply filter) button and you should see a torus appear on the right.


Click on the Rendering tab and you access to all the different rendering modes. Click on the wireframe icon to enable, for the current layer, the display of the edges of the mesh. In the space below you should see the parameters of the wireframe rendering (color, thickness etc).


Now press CTRL+f (⌘+f on OSX) again and type 'remesh', open the parameters of the 'Voronoi Remeshing' filter, raise to 2 the 'Refine Step' param, and turn off the 'Voronoi Coloring' option; press the apply filter '▶︎' button.  After one sec you should see a new layer appear in the list of the meshes, named something like 'Voronoi Remeshing of Torus'.  There are two meshes superimposed on the right, to see clearly both of them just click on the 'eye' icon to disable/enable the visualization of each layer.  The new mesh is a remeshing done using a simple sampling plus relaxation strategy followed by a Delaunay triangulation of these samples
done in the geodesic metric. The result is a base mesh that is refined and adapted over the original mesh. Enable wireframe for this mesh too and switch between the two layers to see the difference in meshing.

Now we want just to compute the difference between these two mesh. As it is well known basic differnce between 3D surfaces is well captured by Hausdorff Distance. So again  CTRL+f /⌘+f and type 'diff' , in the filter list should appear 'Compute Hausdorff Distance', open the parameter list and set: target mesh as voronoi remeshing of Torus', sample Num as 1.000.000, and check the 'Save Sample' flag'. Then just start the filter ( ▶︎) in a few secs (two secs on my laptop) you will have the (one sided) Hausdorff distance computed. In the lower left log window you should see numerical info about the computed distance, something like:

Hausdorff Distance computed
     Sampled 1008192 pts (rng: 0)  on Torus searched closest on Voronoi Remeshing of Torus 
     min : 0.000000   max 0.005136   mean : 0.001373   RMS : 0.001600 
Values w.r.t. BBox Diag (3.464102)
     min : 0.000000   max 0.001483   mean : 0.000396   RMS : 0.000462

You will notice also that there is another layer 'Haudorff Samples': a 1M point cloud with all the samples computed. For all these samples also the computed distance is stored as a scalar value, called for lazy traditional reasons, quality.

Lets color this point cloud according it with the distance computed.

 CTRL+f /⌘+f and type 'quality' , in the filter list should appear 'Generate Color from Vertex Quality'; apply it to the Hausdorff Samples layer, switch to the rendering tab and access to the parameter of the point rendering (just click on the small down arrow ▾ below the point rendering icon): Choose 'Per Vertex' as 'Color Source' and 'Flat' as 'Shading'. Now you have your nicely colored samples showing the difference between the original torus and the remeshed one.


Finally click on the histogram icon to get some insight on the distribution of the error and a more precise meaning of the color mapping used.

MeshLab in javascript

We are proud to present the first beta, experimental, buggy, incomplete version of MeshLabJS, the client-side, run-in-browser port of MeshLab. 
Yes, a version of MeshLab that runs directly inside the browser.

http://www.meshlabjs.net/

It is still rudimental, very minimal, but yet it is a nice example of how current browsers are able to run C++ code compiled into a javascript (thanks to emscripten) at a pretty decent speed. WebGL (via three.js) is used for the rendering. 
Just to clarify it totally runs inside your browser, no 3D data is transferred to a server for processing, all the computation are done (in javascript) locally. Your data is safe as in a classical desktop app. 
It is a bit more than an experiment, there are only a few tens of filters (more to come!), and no fancy tools, but some classics like the renowned quadric simplifier and radiance scaling rendering mode, are available.

As usual everything is opensource, this time on github. If you like it star it on github and if you need some specific meshlab filter, just ask for it on the github issue page.

Mean Curvature, Cavity Map, ZBrush and nice tricks for enhancing surface shading

There are many many techniques for enhancing the look of a surface by mean of smart shaders. Without touching Non photo-realistic rendering techniques there are many tricks that can helps the perception of the features and the fine details of the surface of an object. ZBrush has popularized one of these techniques with the name of cavity mapping. The main idea is that you detect 'pits' on the surface and you make them of a different color and, very important, very dull. In practice it simulates in a rough way all those materials where in low accessibility regions dust/rust/oxide accumulates while in the most exposed parts the use make them shiny. You can do such effects in MeshLab and they can be very useful for making quick nice renderings of scanned objects; let make a
a practical example using a 3D scanned model of ancient statuette of the Assyrian demon Pazuzu (courtesy of Denis Pitzalis C2RMF/Louvre). The plain model (shown on the right) is rather dull and not very readable and at a first glance you cannot appreciate the scale of the scanned details.

You can improve it a bit by adding a bit of ambient occlusion. In MeshLab you can do it in a couple of ways, either computing an actual ambient occlusion term (e.g. a steradian denoting the portion of sky that you can see from a given point) for each vertex (Filter->Color->Vertex ambient occlusion) or just resort to a quick and dirty Screen Space Ambient Occlusion (SSAO) approximation (render->Screen Space Ambient Occlusion).In the first case as a bonus you are able to tweak the computed value as you want (by playing with the quality mapping tools), in the second you have just an approximation, but the nice fact is that it is a decoration e.g. it is blended over the current frame buffer and therefore it mix up with whatever rendering you have. In the two pictures  per vertex AO vs SSAO.

Not enough. Lets try to find out and enhance the pits. Mean Curvature is what you need, you can think it as the divergence of the normals over the surface and it captures well the concept of characterizing local variation of the surface. There is a vast literature on computing curvatures on discrete triangulated surface and MeshLab exposed a few different methods (and it has also a couple of methods for computing them on Point Clouds). The fastest one (a bit resilient on the quality of the mesh) is filter->color->Discrete Curvature. On the right you can see the result of such filter mapped into a red-green-blu colormap.
if you want expmeriment you can try the various options under filter->normal->compute curvature principal direction (be careful some of these filters can be VERY SLOW).

Now the final step is just to use this value for the shading. Just start the shader called ZBrush and play a bit with the parameters and then, hopefully, you can get the desired result. Some notes. It happens that curvature has some outliers so clamping the quality values before starting the filter can be a good idea (filter->quality->clamp). Similarly the range can be very large so playing with the "transition_speed" parameter of the shader can be a quite useful. To vary the amount of "pits" use the "transition center" slider.

Measuring the difference between two meshes

Computing the geometric difference between two 3D models is a quite common task in mesh processing. In our lab, many years ago (11 !), we developed and freely distributed the standard tool for such task, Metro, whose paper has been cited more than 500 times . While Metro is still a small open source standalone command line program available at our web site, its functionality have been integrated into MeshLab in the filter Sampling->Hausdorff Distance, and they can be used in a variety of ways.
So here is a short basic tutorial.

Start with a mesh (in the following the well known Stanford Happy Buddha (1087716 triangles). Aggressively simplify it in a significant way to just 50k tris (e.g. 1/20 of the original size). Reload the original mesh as a new layer. At this point you should have two approximation of the same shape well aligned in the same space. Toggling the visibility on and off of each mesh you should easily see the difference between the two meshes (tip: ctrl+click over the eye icon in the layers window turn off all the other layers).

Now you are ready to start the Hausdorff distance filter.  First of all remember that the Hausdorff Distance between two meshes is a the maximum between the two so-called one-sided Hausdorff distances (technically not they are not a distance):

These two measures are not symmetric (e.g. the results depends on what mesh you set as X or Y).
In the Hausdorff filters MeshLab computes only the one-sided version

leaving the task of getting the maximum of the two to the user.

Now on the practical side. MeshLab uses a sampling approach to compute the above formula taking a bunch of points over a mesh X and searching for each x the closest point y on a mesh Y. That means that the result is strongly affected on how many points do you take over X and there are a lot of option on for that. A common very simple approach is just to use the vertexes of the highest density mesh as sampling points (e.g. the original Buddha vertexes): to do this simply leave checked only the "vertex sampling" option in the filter dialog and be sure that the number of samples is greater or equal than the vertex number. After a few secs the filter ends writing down in the layers log windows the collected info. Something like:

: Hausdorff Distance computed

: Sample 543652

: min : 0.000000 max 0.001862

: mean : 0.000029 RMS : 0.000083

: Values w.r.t. BBox Diag (0.229031)

: min : 0.000000 max 0.008128

: mean : 0.000126 RMS : 0.000361

For sake of human readability the filter reports the values in the mesh units (whatever they are) and with respect to the diagonal of the bounding box of the mesh that is something you are always able to understand without knowing anything about the model units. For example in this case you can see that the maximum error between the two mesh is approximately 1% of the bbox diag, but on the average the two meshes are almost in the 1/10000 range.

The filter save in the all-purpose quality field of the vertexes of the sampled mesh the computed distance values. To better visualize the error you can simply convert these values (for the high resolution mesh) into colors using the Color->Colorize by quality filter that maps them in to a rather red-green-blue colormap. Usually given the non uniform distribution of the values you have to play a bit with the filter parameters clamping the mapping range to something meaningful (only a few points have the maximum so with a linear mapping of the values over the whole range will result into a almost uniform red mesh. Note that it is a red-green-blu map, so red is min and blue is max, so in our case red means zero error (good) and blue high error (bad).
The next image sequence report just a small detail of the one of the points with higher error. During the simplification we removed some topological noise, (the thin tubes connecting the two side of the hole)  from a Hausdorff point of view it is a rather large error: the points in the middle of the thin tubes has nothing in the simplified mesh that is close to them; so they bring up the maximum error significantly. Luckily enough they represent only a small portion of the whole mesh so the average error remains low.

Note that if you measure the other one-sided Hausdorff distance, that specific mesh portion will not denote any particular error, because in that case you sample the simplified mesh and for each point of the simplified mesh there are points of the original mesh that are quite close to them. In other words, in this case the simplified mesh is close to the original one, but the original one is not close to the simplified one.

Next post will discuss some remaining issues including the sampling of the surface, looking at all the taken samples and the found closest points and how to colorize the low resolution mesh...
Second part of the tutorial here.

Practical Quad Mesh Simplification

Just a shameless plug to our last EG paper that will find is way inside MeshLab:

Marco Tarini, Nico Pietroni, Paolo Cignoni, Daniele Panozzo, Enrico Puppo
Practical Quad Mesh Simplification
Computer Graphics Forum, Volume 29, Number 2, EuroGraphics 2010

In our community it is well know the old religious war between quad vs. triangle meshes, each approach has its own merits and I not discuss them here.
Moving back and forth between the two approaches is often useful but the issue of getting a good quad mesh from a highly irregular tri mesh is a tough one.

In the above paper we present a novel approach to the problem of quad mesh simplification, striving to use practical local operations, while maintaining the same goal to maximize tessellation quality. We aim to progressively generate a mesh made of convex, right-angled, flat, equally sided quads, with a uniform distribution of vertices (or, depending on the application, a controlled/adaptive sample density) having regular valency wherever appropriate.

In simple words we start from a tri mesh, we convert into a dense quad mesh using a new Triangle-to-Quad conversion algorithm and then we simplify it using a new progressive quad simplification algorithm. The nice side is that the quad simplification algorithm actually improves the quality of the quad mesh. Below a small example.

We are currently adding this stuff inside MeshLab. The first things that will appear are the triangle to quad conversion algorithms and some functions for measuring the quality of a quad mesh according to some metrics. More info in the next posts....


(2/1/10 edit: if the above link for the paper does not work try this:  Practical Quad Mesh Simplification)

3D scanning and unrolling an ancient seal

A few lines on an interesting recent project I participated and that exploited MeshLab processing abilities.
The project whose results are now shown in a exhibition at the Louvre involved the scanning with non traditional technologies of the very small and wonderful ancient Cylinder Seal of Ibni-Sharrum (photo © CRMF / D. Pitzalis), a precious antique mesopotamic artifact that is considered one of the absolute masterpieces of glyptic art.

This small seal was digitally acquired at CRMF at a very high resolution and with a variety of 3D scanning techniques (microprofilometry, x-ray Tomography, photogrammetric techniques) and, obviously, the results were processed and integrated entirely with MeshLab.

Among the nice things that we did inside MeshLab was the virtual unrolling of the seal, e.g. getting the inverse shape that you get when you roll the seal over a soft substance like clay or wax.  It was quite easy from a technical point of view, but very appreciated by the restorers that disregard invasive plaster based techniques that often can leave small residuals over the precious artifacts.  You can find more details on the whole acquisition and processing of the seal on this VAST conference paper.

 

On the side you can see a couple of renderings of the 2-million of triangle model of the unrolled seal; the renderings were done inside MeshLab, the first one is a simple flat shaded rendering, while the second one exploit a nice shader that I have recently added to the MeshLab shading arsenal, it mimics in a shameless way the ZBrush technique of varying shininess and color according to the "cavities" of the geometric model (they use it for the famous zbrush wax and bronze materials).  It is nice to see how the shading vastly improve the shape perception of the 3D model.
I have not seen many correct discussion on how to perform these kind of shading, so expects a post on that...


A massive physical reproduction (4 meters long!) of the unrolled seal is at the center of "OnLab" a thematic exhibition of Michel Paysant, that will open in the next days at Louvre, Denis Pitzalis worked a lot on this project and you can find  more details and photos in his blog.

Meshing Point Clouds

One of the most requested tasks when managing 3D scanning data is the conversion of point clouds into more practical triangular meshes. Here is a step-by-step guide for transforming a raw point cloud into a colored mesh.

Let's start from a colored point cloud (typical output of many 3D scanning devices), each point has just color and no normal information. The example dataset that we will use is a medium sized dataset of 9 millions of points. Typical issues of such a dataset dataset: it is non uniform (comes from an integration of different datasets), has some strongly biased error (alignment error, some problem during data integration), it comes without normals (hard to be shaded).

1. Subsampling
   
   
   
   As a first step we reduce a bit the dataset in order to have amore manageable dataset. Many different options here. Having a nicely spaced subsampling is a good way to make some computation in a faster way. The Sampling->Poisson Disk Sampling filter is a good option. While it was designed to create Poisson disk samples over a mesh, it is able to also compute Poisson disk subsampling of a given point cloud (remember to check the 'subsampling' boolean flag). For the curious ones, it uses an algorithm very similar to the dart throwing paper presented at EGSR2009 (except that we have released code for such an algorith long before the publication of this article :) ). In the invisible side figure a Poisson disk subsampling of just 66k vertices.
2. Normal Reconstruction
   
   
   
   Currently inside MeshLab the construction of normals for a point cloud is not particularly optimized (I would not apply it over 9M point cloud) so starting from smaller mesh can give better, faster results. You can use this small point cloud to issue a fast surface reconstruction (using Remeshing->Poisson surface reconstruction) and then transfer the normals of this small rough surface to the original point cloud. Obviously in this way the full point cloud will have a normal field that is by far smoother than necessary, but this is not an issue for most surface reconstruction algorithms (but it is an issue if you want to use these normals for shading!).
3. Surface reconstruction
   
   
   
   Once rough normals are available Poisson surface reconstruction is a good choice. Using the original point cloud with the computed normals we build a surface at the highest resolution (recursion level 11). Roughly clean it removing large faces filter, and eventually simplify it a bit (remove 30% of the faces) using classical Remeshing->Quadric edge collapse simplification filter (many implicit surface filters rely on marching cube like algorithms and leave useless tiny triangles).
4. Recovering original color
   
   
   
   Here we have two options, recovering color as a texture or recovering color as per-vertex color. Here we go for the latter, leaving the former to a next post where we will go in more details on the new automatic parametrization stuff that we are adding in MeshLab. Obviously if you store color onto vertexes you need to have a very dense mesh, more or less of the same magnitudo of the original point cloud, so probably refining large faces a bit could be useful. After refining the mesh you simply transfer the color attribute from the original point cloud to the reconstructed surface using the vertex attribute transfer filter.
   
   
5. Cleaning up and assessing
   
   
   
   The vertex attribute transfer filter uses a simple closest point heuristic to match the points between the two meshes. As a side product it can store (in the all-purpose per-vertex scalar quality) the distance of the matching points. Now just selecting the faces having vertices whose distance is larger than a given threshold we can easily remove the redundant faces created by the Poisson Surface Reconstruction.

This pipeline is only one of the many possible way of ending up into a nice mesh. For example different choices could have been done for step 2/3. There are reconstruction algorithms that do not need surface normals, like for example the "Voronoi Filtering" that is an interpolating reconstruction algorithm (e.g. it build up only triangles on the given input points) but usually these filters works better on very clean datasets, without noise or alignment errors. Otherwise on noisy datasets it is easy that they create a lot of non manifold situations. Final thanks to Denis Pitzalis for providing me this nice dataset of a Cypriot theater.

Computation & Cultural Heritage Siggraph Course

Shameless linking of the Computation & Cultural Heritage Siggraph Course where, a week ago, I gave my contribution. The course surveyed several practical CG techniques for applications in cultural heritage, archeology, and art history. Topics include: efficient/advanced/cheap techniques for 2D/3D digital capture of heritage objects, appropriate uses in the heritage field, an end-to-end pipeline for processing archeological reconstructions (with special attention to incorporating archeological data and review throughout the process), how digital techniques are actually used in cultural heritage projects, and an honest evaluation of progress and challenges in this field.

Specifically to this blog in my first presentation I described a free photo to 3D pipeline that relies on the free web-based service Arc3D (developed during the Epoch EU project by Visic of KUL) for Structure-from-Motion reconstruction and (obviously) on MeshLab for the processing of the generated 3D range maps. In practice it is a pipeline that allows to cheaply reconstruct nice accurate 3D models from just a set of high resolution photos. Obviously not all the subject fit with this kind of approaches (forget moving subjects and glassy, shiny, fluffy, iridescent stuff), but for stable, dull, textured objects, it works surprisingly well, giving results with a quality not far from traditional laser based 3D scanning. More info on the process in the slides (and eventually in other posts here). In the top right picture a typical example of the results that you can obtain when starting from a reasonable set of photos of a detail of a weathered stone romanesque high relief (Monasterio de Santa María de Ripoll). The model is untextured, with just a bit of ambient occlusion: all you see is geometry.

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.

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

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.