Here’s a little Venn diagram I made to explain (some of) the variety of multigrid methods:
Archive for October, 2015
I’d forgotten that I’d discovered that matlab has a built-in function for triangle mesh simplification:
reduce_patch. Here’s a little comparison between this method and the ones I’ve wrapped up in gptoolbox.
Given an input mesh with vertices
V and faces
F (this elephant has 14732 faces):
Built-in matlab reduce patch
We can decimate the mesh to 1000 faces using pure built-in matlab:
[mF,mV] = reducepatch(F,V,1000);
Notice that it’s a rather adaptive remeshing. There aren’t (m)any options for controlling
reducepatch, just the
'fast' flag, but in this case it will produce an identical output.
Libigl has a framework for edge-collapse decimation on manifold meshes and a default setting for regular meshing:
[iV,iF] = decimate_libigl(V,F,1000);
I have a wrapper for CGAL’s decimation algorithms. These can result in a regular remeshing with 1000 faces:
[c1V,c1F] = decimate_cgal(V,F,1000/size(F,1));
or an adaptive meshing:
[c2V,c2F] = decimate_cgal(V,F,1000/size(F,1),'Adaptive',true);
CGAL has a fairly general interface for an edge-collapser, but these are the only metrics provided by default from CGAL.
Suppose my original elephant had 3.7 million faces instead of just 14K, how do these methods measure up when reducing to 1000 faces:
|qslim||108.0s + 507.5s + 59.4s|
My qslim wrapper is currently very silly. It’s calling
qslim as an executable and then reading in the entire collapse log and conducting the collapse within matlab (the second time is for reading the log, the third for conducting the collapse).
None of these methods guarantee that the result is self-intersection free. I’ve noticed that qslim and matlab will create non-manifold meshes from manifold inputs. The current libigl implementation should not creative non-manifold output, but assumes the input is a closed surface. For casual decimation, it seems like matlab’s
reducepatch and libigl’s
decimate_libigl are the best bets for speedy adaptive and regular meshing respectively. Conveniently they also require the least in terms of dependencies.
I was asked to write an article in the Dissertation Impact series of IEEE Computer Graphics and Applications. In the first half of “Breathing Life into Shapes” I’ve tried to summarize my thesis for the general computer graphics audience. The second half is more exciting and contains my view of the future of real-time shape deformation research and the open problems I see ahead.
Abstract: Many tasks in geometry processing and physical simulation benefit from multiresolution hierarchies. One important characteristic across a variety of applications is that coarser layers strictly encage finer layers, nesting one another. Existing techniques such as surface mesh decimation, voxelization, or contouring distance level sets do not provide sufficient control over the quality of the output surfaces while maintaining strict nesting. We propose a solution that enables use of application-specific decimation and quality metrics. The method constructs each next-coarsest level of the hierarchy, using a sequence of decimation, flow, and contact-aware optimization steps. From coarse to fine, each layer then fully encages the next while retaining a snug fit. The method is applicable to a wide variety of shapes of complex geometry and topology. We demonstrate the effectiveness of our nested cages not only for multigrid solvers, but also for conservative collision detection, domain discretization for elastic simulation, and cage-based geometric modeling.