Show HN: An algorithm for smoothly filling holes in 3D meshes

https://erkaman.github.io/posts/hole_filling.html

by erkaman • 8 years ago

104 18 8 years ago

erkaman.github.io

erkaman6• 8 years ago

A blog post from me about smoothly filling holes in a 3D mesh. Small demo application can be found here:

https://github.com/Erkaman/hole_fixer

lccarrasco• 8 years ago

really interesting, thanks for the post ^^

lettergram• 8 years ago

This honestly seems like a standard approach to smoothing for computer vision (not to say, this isn't different in a technical sense).

erkaman6• 8 years ago

Yeah, I think it's heavily inspired by that yes. Many techniques in geometry processing take heavy inspiration by image processing techniques.

i_am_nomad• 8 years ago

My first thought was, this will be great for fixing the annoying gaps created by bad STL exports.

lopmotr• 8 years ago

For visualization or maybe 3D printing, yea. But for finite element analysis, you don't want smooth filling at weird corners/etc. A flat surface is more efficient since it can have fewer mesh elements.

A weakness of this method is that it globally changes the entire mesh! That's bad. You might lose important detail elsewhere. I wonder if those refinement and unrefinement steps are really necessary or not?

erkaman6• 8 years ago

global refinement and unrefinement steps are unnecessary, yes. It just makes the implementation of the demo so much easier. It is possible to only refine the patch, and then fuse the patch with the original mesh, and then global refinement is not necessary. But this is actually surprisingly tricky to robustly implement in practice, and did not implement it mostly due to time restrictions, and to keep the demo code short and readable.

bhouston• 8 years ago

This is sort of neat but not really useful and not novel. The reason it isn't novel is that people have been smoothly filling holes via various polynomials and other smooth curves for the last twenty years. I wrote my first attempt in 1997 as an undergraduate.

In real life you have contradictory information given you to from a 3D scanner. there are multiple surfaces that seem to intersect and do not technically make sense and you have to make a smooth singular surface from this. Thus the real calculation is volumetric and best fit between surfaces all the while trying to maintain color/texture information.

Stuff like this:

http://sites.fas.harvard.edu/~cs277/papers/mlsSoup.pdf

https://members.loria.fr/Bruno.Levy/papers/VSDM_IMR_2011.pdf

Basically this solution is a toy solution for an idealized problem that is great for a thought experience for undergraduates. So it is great for that.

electricslpnsld• 8 years ago

This is sort of neat but not really useful and not novel.

Who said it had to be? It is a blog post, not a SIGGRAPH paper!

nicklaf• 8 years ago

Maybe it was not polite of him to dismiss the blog post (and maybe that wasn't his intention), but I do appreciate that he provided references to prior art, and also took the time to put them in context.

erkaman6• 8 years ago

I agree with you mostly. I just think that this is an interesting usage of variational calculus, which is not that well understood by other programmers, so I wanted to write this article about this, in order to introduce other programmers to the topic.

And also because I thought the literature about this out there wasn't really that readable, and I always think there is value in writing expository texts like this.

pducks32• 8 years ago

Yea I really liked your post because of that focus. I use variation all calculus quite a lot for non-programming stuff and it’s really allowed me to understand things like NNs way better and I think so many other programmers could benefit from a small bit of it.

mkl2• 8 years ago

3D scanners are not the only source of mesh data. 3D modelling, simulation, etc. can produce consistent meshes which you may still want to fill holes in. I agree this isn't novel, but it may be useful in some instances.

rsp1984• 8 years ago

I agree with you on the first part. However keep in mind that sometimes it's better to subdivide a problem and find better solutions for each sub-part.

The case you outlined can be subdivided into (non-dense / non-watertight) surface reconstruction followed by hole-filling on the extracted surface.

Also, the given algorithm could still be used for filling holes in the data of a single-frame of a 3D sensor, where you "only" deal with noise, but not with overlapping data "layers".

mkl2• 8 years ago

I did almost the same thing in a very different way as part of my PhD research: https://imgur.com/a/k6AQi

I did it by representing the surface implicitly with radial basis function approximations, which can't produce surfaces with holes (well, edges - a torus is fine).

erkaman6• 8 years ago

yeah, radial basis functions are awesome :)

FrankDixon• 8 years ago

Nice explanation. I think meshfix implements this too: https://github.com/MarcoAttene/MeshFix-V2.1

Show HN: An algorithm for smoothly filling holes in 3D meshes

Related Stories