Monday, March 23, 2009

On the subtle art of mesh cleaning


Most mesh processing algorithms usually require nice two-manifold, watertight, intersection free, well-shaped, clean meshes. Obviously in the real world this does not happen with a great frequency (apart in scientific papers). Common meshes are the most horrible mix of all the possible almost catastrophic degenerate situations.

MeshLab can help the tedious tasks of cleaning meshes in a variety of ways. Let's start with some simple examples involving vertices.
  1. Unreferenced Vertices. Very common issue. Your mesh has some vertices that are not referenced by any triangle. A variety of cause can create these situations (algorithms deleting faces in a non careful way can create them). This situation can be more dangerous than it seems, because they can bring in trash uninitialized data in algorithms that initialize vertex data performing face-based traversal (e.g. normals computations...).
    An easy way to look at the presence of these vertices is simply switching to a point based rendering mode (evenually turning the lighting off, because, by default, unreferenced vertices have null normals). As always happens, sometime this situation is not an error but could be a feature (think to point clouds).
  2. Duplicated vertices. Adjacent triangles does not share the vertices with the same coordinates. Sometimes it is an issue that come directly from some file formats (STL for example store triangles duplicating each vertex). This situation is easy to be detected:
    1. Smooth shading is the same of flat shading: the duplicated vertices do not allow the averagin of normals between adjacent faces that is necessary for smooth shading.
    2. Poor man version of Euler Characteristic does not work: instead of having:
      [face number] ~ 2 * [vertex number]
      you have:
      [face number] ~ 1/3 * [vertex number]
    Again this could be a feature and not an error. Sometimes, duplicating vertices can be used to impose sharp angles when you do not have simple techniques to store multiple normals for the same vertex.
The above cases can be cured, if necessary, by invoking in MeshLab the two filters, Remove Unreferenced Vertices and Remove Duplicated Vertices in the menu named: Filters->Cleaning and Repairing.

4 comments:

Mark said...

Hello, I really enjoy your blog and I'm wondering if you could help point me in the right direction on a Meshlab project that I'm playing with.

I've been using the process described at http://binarymillenium.com/2008/08/photosynth-export-process-tutorial.html to extract point clouds from Photosynth projects.

Here's the basic process that I'm following:
• Photograph a subject
• Importing the photos into Photosynth (ex http://photosynth.net/view.aspx?cid=c1beba97-da25-4bdf-9e54-0dca8ebd79a4 )
• Extract point clouds bin files from Photosynth with Wireshark
• Export the 3D bin data to a ascii file (using python script)
• Then I use a php script to convert those into a Stanford Polygon (.ply)
• Finally, I bring that into Meshlab.

What I'm hoping to do is convert the PLY into a fairly detailed 3D mesh of my Photosynth scene. I realize the 3D model will only be as good as that created by Photosynth. Frankly, the point clouds that I'm creating look horrible and distorted after I run "Build Surface from Points". Is there a tutorial or manual that might help walk me through the point cloud to 3D model process? I'm fairly familiar with all things 3D.

As an archaeologist, I see some scientific and preservation potential for using Photosynth and Meshlab together. Having the ability to quickly document some archaeological phenomena would be excellent. We often work with bulldozers at our back and with untrained volunteers. Being able to quickly, cheaply, and accurately preserve some information about these sites would be a real asset.

Any help you can provide would be great!

Mark

ALoopingIcon said...

Yes, building a surface from the point clouds generated by photosynth (or by bundler that is the open source reconstruction sw behind the first version of Photosynth) is not that easy.

Mostly because the point cloud is noisy and not very dense.

I will post on this subject soon, so stay tuned. In the meantime a few suggestions and link.

- build surface from points use the ball-pivoting algorithm that work well when you have no noise.

- Poisson surface reconstruction is much better but it requires good normal estimations.

- there are other 3d from photo sequence systems, notably I warmly suggest you to test Arc3D that outputs much denser point clouds, and whose output format is natively supported by MeshLab. With a bit of effort, experience and luck you can get result like this one.

cheers

declan said...

Hi,

I am EXTREMELY interested in learning the Tri to Quad conversion (and Quad Simplification). I'd like to bring .stl's into Tsplines via a well-organized .obj file. The Easter Island Head video is perfect, but I can't figure out how to operate the filter. Tri to Quad Filter > SaveAs *.obj results in a tri-based .obj. ??

Franklin7 Seo said...

Your website is really cool and this is a great inspiring article.
Städhjälp i Stockholm