Tuesday, December 22, 2009

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)

12 comments:

Luigi said...

Salve mi scuso se vi contatto in questa forma tutt'altro che ufficiale, ma non sono riuscito a trovare un form di contatto.

MI chiamo Luigi Giaccari, ormai da poco ex studente in ingegneria meccanica dell'università degli studi dell'Aquila.

Ho notato che meshlab ha tools di:
-riparazione
-re-meshing
-hole filling
-rendering
-etc...

Manca il motore... il meshing tool.
Ho ormai una discreta esperienza nel settore "Surface reconstruction", se esiste la possibilità di finanziare un progetto di ricerca potrei dotare meshlab di tutti i migliori algoritmi di surface reconstruction presenti in letteratura, più alcuni miei inediti.

Alcuni li ho pubblicati in versione ridotta, digitate si google:
"Luigi Giaccari surface reconstruction"

Posso darvi informazioni più dettagliate se mi contattate tramite e-mail: giaccariluigi@msn.com

intanto vi mostro questo video:
http://www.youtube.com/watch?v=up6Ak-3jSMU
Mi scuso se vi spedisco questo testo più di una volta, voglio essere sicuro che vi arrivi.
Grazie per l’attenzione cordiali saluti,
Luigi

isculpt said...

This is great. When will it be available in Mesh Lab? I'm writing a book and have included mesh lab in the book and this would be great to mention. Please respond asap.

Luigi said...

Correzzione al mio precedente commento,

Non riesco a far girare meshlab sul mio PC, ma ho appena visto che avete implemetato il ball pivoting, poisson, ed il Crust...
Saluti

ALoopingIcon said...

@luigi
1) English please ;)
2) I have seen your stuff on recon based on 2.5 Delaunay triangulation, but i have not understood if it relies on matlab or is portable c++ code.
3) What kind of problems have you encountered?
4) use the sourceforge forums and tracking services for generic meshlab problems...

ALoopingIcon said...

@ isculpt
About the availability of the quad stuff: in the next beta there should be the basic tri to quad conversion techniques and in the next one (mid feb approx.) the quad simplification algs.

isculpt said...

Great I'll add it to the book then. If you have any further information please feel free to get a hold of me. bridgette ( the at sign) creativesculpture.com

Also would a couple of your people be available for a podcast that we are doing on 3d? very informal and prerecorded

Bracchesimo said...

OH Sorry,

I thought the developing team was Italian.

I wanted to ask you if you can be interested embedding this algorithm into MeshLab.

I actually thought you had no surface reconstruction algorithm, but on a second deeper view I realized you have The Power Crust, Ball pivoting, and Poisson.

Unfortunately I can not use meshlab on my pc because it always crashes when I try to import points.

Delaunay2_5D is 100% C++ code (portable I hope). I am not a software developer, I am a mechanical engineer with passion for algorithms. I started with matlab (http://www.mathworks.com/matlabcentral/fileexchange/authors/31779).

I just graduated in December and I was looking for some job opportunity.

The algorithm is very simple therefore terribly fast, as you can see in the demo!

If you can be interested you can contact me at my e-mail giaccariluigi@msn.com and we will discuss about details.

In a couple of week I should be able to complete a demo that i will give people to run tests.

Magnus said...

Is there a ETA of the release including this quadrangulation solution ?!
Thanks in advance for adding this, if it works well it will be a great addition.

Durandal said...

Hi, congratulations for the great work MeshLab it's just amazing.

I've downloaded the last version( 1.3, August 2010) but can't find how to use the Practical Quad mesh simplification.

it is still unavailable?

peter said...
This comment has been removed by a blog administrator.
Middnight said...

I would love to have the quad mesh simplification available in meshlab.

Meshlab is a very nice program and has proven to be very useful.

briansharpe said...

Hi There

I'm very interested in your Practical Quad Mesh Simplification algorithm.

Did you manage to get it into MeshLab at all?

If not, are there any open source implementations in existence? It could make a great maya plugin...

Thanks!
Brian