search

meshpro / optimesh

:spider_web: Mesh optimization, mesh smoothing.
578 stars 56 forks source link

Laplacian smoothing calls flip_edge? #56

Closed krober10nd closed 2 years ago

krober10nd commented 4 years ago

A simple question: why does the Laplacian smoother flip edges until the triangulation is Delaunay? Laplacian smoothing can occur on all kinds of triangulations...Is there a rationale behind this?

nschloe commented 4 years ago

Why not?

krober10nd commented 4 years ago

Several reasons:

  1. It's slow O(N^2) at worst case scenario. Sometimes I have a Delaunay mesh I built in parallel and I want to do mesh optimization like Laplacian smoothing. The edge flipping takes longer than the entire execution of the parallel triangulation in the first place defeating the parallelization.

  2. It's not necessary. Laplacian smoothing is supposed to move the nodes to their arithmetic average of their neighbors, nothing more.

  3. I may have some fixed and constraints in the triangulation that are not Delaunay and this will destroy all the work I put in to constrain the edges.

nschloe commented 4 years ago

  1. It's slow, really? On all meshes I've seen it only takes a tiny fraction of the run time. Note that only very few edges are actually flipped, and checking the need for flips is O(n) I think. Feel free to append a mesh where you experience trouble, I'll be happy to stand corrected.

    1. I get those. The main idea behind optimesh is to, well, optimize a mesh. Laplacian smoothing is the worst of them all, but it's getting better with edge flips of course. On the other hand, without the flips it's just one step.

I think I'll add an option for disabling the flips.

krober10nd commented 4 years ago

I appreciate it @nschloe

  1. Yea, I am doing this with 500 million to 1 billion vertex meshes so slow is relative. Due to the pandemic, it'd be difficult to offload the mesh from our cluster haha.
  2. And yea, I realize that it's just I'm not willing to do dive into parallel mesh improvement just yet so the fastest way to improve the mesh would be in theory Laplacian smoothing. For now, if I have an edge constraint, I just could reject the new point position.
nschloe commented 4 years ago

relative

Relative to the cost of the rest of the algorithm, yes. And I think edge flips are a lot cheaper than the movement of the points. At least that's what I gather from my own measurements.

Feel free to append your mesh and I'll try it out.