3
$\begingroup$

Suppose I have a complicated structure given in 2 or 3 dimensions as a polygon mesh. For example, this could represent a "cave" or an assembly of irreguar shaped particles or a tree, whatever. Now I'd like to "smoothen" this structure to end up with a finer and smoother polygon mesh.

It's not just about refining the mesh and it's also not just about some sort of rastering and then anti-aliasing filtering, it's really about getting from a coarse edgy polygonization/mesh to a fine, more smoothly curved polygonization/mesh.

I'm looking for some ideas on how to do it: Books, papers, search terms. (I do not even know the name of the problem...)

(It will be living in the realm of nano particles if that plays a role.)

$\endgroup$
6
$\begingroup$

To complement the two answers from Daniel Shapero and Nicoguaro: Basically, there are two ways of smoothing a mesh, subdivision (generate new vertices) and smoothing (move the points in such a way that the obtained shape is smoother).

Subdivision

To grasp the intuition, imagine you want to "smoothen" a 2D square. The 2D square is not smooth because it has corners, so let's cut the corners out, then you obtain an octagon (a "stop sign"), it has more corners, but they are wider (smoother). If you do that again, you obtain a polygon with 16 sides, that is a reasonably good approximation of a circle (do that an additional couple of times if it's not smooth enough). Now there are some theoretic results, telling you how to cut the corners in such a way that if you do that an infinite number of times, you will get a smooth (tangent continous) shape.

When can I use subdivision ?

To use subdivision, you need a mesh that is rather coarse, with well shaped elements. You need also to know that there are subdivision methods for meshes composed of quads (e.g., Catmull-Clark, Doo-Sabin) and subdivision methods for meshes composed of triangles (e.g. Butterfly, Loop, sqrt(3)). You will obtain best results with squares, but you need a very nice input mesh (e.g., a mesh designed by a computer graphics artist). If your mesh does not have a nice quad-like structure, you may try to use our "anisotropic polygonal remeshing" method cited in the other answers (disclosure: I'm a co-author of this article).

Further reading on subdivision: see Zorin et.al's SIGGRAPH course notes [1]

Smoothing

The other idea to smooth a mesh is to move the vertices in such a way that the obtained mesh is smoother. Here is some intuition about the idea: a flat mesh, where each vertex is exactly at the barycenter of its neighbors, is perfectly smooth. So one possible idea is to iteratively move all the vertices towards the center of their neighbors in interleaved loops:

(1) compute the barycenters of the neigbors
(2) move the points to the barycenter
(3) goto 1

If you do that, it works quite well, but you will observe that the mesh shrinks more and more, so you can do that with a correction phase, making the volume of the mesh constant (clearly, you need a closed mesh to do that):

(1) compute the barycenters of the neigbors
(2) move the points to the barycenter
(3) compute the volume of the mesh
(4) scale all point coordinates by the cubic root of the ratio between the new volume and the initial volume
(3) goto 1

Now, instead of correcting the volume a-posteriori, why not directly compute a volume-preserving smoothing ? This is (roughly) what Desbrun's "curvature flow" method cited in Shapero's answer does, by exploiting a relation between the curvature at a point and the volume.

Now imagine that you have some points of the mesh that need to keep their original locations, like "control nodes" that will be "locked" while all the other points are free to move. A possibility to do that, still saying that making each point as near as possible to the barycenter of its neighbors, is using least-squares: you minimize the squared distance between each point and the barycenter of its neighbors subject to the constrained points. This is called Discrete Smooth Interpolation [2],[3] (method invented by Mallet, my Ph.D. thesis advisor). It also corresponds to Laplacian smoothing (see the PMP book [4] that we wrote with colleagues, cited also in the other answers, in particular chapter 3)

So which method should I use ?

Mainly depends where the mesh comes from. Subdivision is very cheap, but only works for nice designed meshes. Curvature flow is reasonably simple, and will quite easily remove the high frequency noise from a scanned mesh. Least-squares smoothing / Laplacian smoothing needs to solve a least-squares problem (boils down to solving a linear system), which is more involved. This is the price to pay if you need to introduce constraints / control points / handles.

For the sake of completeness, I also mention spectral methods, that do a Fourier-like decomposition of the shape, see my articles and SIGGRAPH course notes on the topic [5,6], but it is extremely costly (solve eigenproblem), it's overkill in most situations (but the math. is interesting).

[1] http://mrl.nyu.edu/publications/subdiv-course2000/

[2] Discrete Smooth Interpolation, Mallet, ACM Transactions on Graphics, 1989

[3] http://alice.loria.fr/index.php/publications.html?redirect=0&Paper=smoothing@1999

[4] Polygon Mesh Processing, CRC press, Botsch, Kobbelt, Alliez, Levy, http://www.pmp-book.org/

[5] Laplacian Eigenfunctions, towards an algorithm that understands geometry, Levy, SMI 2006 invited talk

[6] Manifold Harmonics, Vallet and Levy, Eurographics / Computer Graphics Forum, 2008

[7] Spectral Geometry Processing, Levy and Zhang, SIGGRAPH and SIGGRAPH ASIA course (first given in 2010)

$\endgroup$
5
$\begingroup$

As mentioned in the answer by @DanielShapero, you can follow an approach based on local approximations of the curvature for your nodes. In the post he suggest, there is an article by Desbrun. I would suggest to check another article by him: Anisotropic Polygonal Remeshing [1].

Another option that comes to my mind is to use Catmull-Clark subdivision algorithm [2]. Where you start with a mesh and add new points in the middle of the original face (split step) and then you move the original points using a weighted average of their closest (newly created) points (average step). Khan-Academy has an interactive version of it in this link: https://www.khanacademy.org/partner-content/pixar/modeling-character/modeling-subdivision/p/interactive-subdivision-in-3d, so you can check if that helps you.

References

[1] Pierre Alliez, David Cohen-Steiner, Olivier Devillers, Bruno Levy, Mathieu Desbrun. Anisotropic Polygonal Remeshing. [Research Report] RR-4808, INRIA. 2003.

[2] Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design 10 (6): 350. doi:10.1016/0010-4485(78)90110-0.

$\endgroup$
4
$\begingroup$

For just mesh smoothing, you can start by looking at Laplacian smoothing and some of the references therein. The idea is to update the position of every vertex in the interior of the mesh by replacing it with the average of its neighbors. There are loads of more sophisticated ways of doing this by using different operators.

If you're doing both surface mesh refinement and smoothing at the same time, you can do better than just adding more points to every triangle by computing estimates of local mesh curvature; this answer might give you some inspiration. More generally, you can construct a local spline approximation of the surface and use this to decide where to add new points.

Polygon Mesh Processing by Botsch, while a little thin on some of the details, covers the general ideas pretty well and will at least give you the terms needed to describe your problem.

$\endgroup$
3
$\begingroup$

Surprisingly, Lloyd smoothing hasn't come up here yet.

Check out

Du, Qiang; Faber, Vance; Gunzburger, Max (1999), "Centroidal Voronoi tessellations: applications and algorithms", SIAM Review, 41 (4): 637–676

(and perhaps voropy, a small project of mine, if you're interested to see Lloyd smoothing in action).

enter image description here

$\endgroup$
  • $\begingroup$ Nico -- you should disclose that you are the author of voropy if you recommend it. It looks excellent by the way! $\endgroup$ – Daniel Shapero Feb 24 '17 at 5:08
  • $\begingroup$ @DanielShapero, thanks for the hint. Did just that. $\endgroup$ – Nico Schlömer Feb 24 '17 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.