Based on this thread: ( Cleaning up Meshes Inside(?) & Potential Speedup Contest )
OK, I’ve been busy lately but here is the basic concept I’d like to speed up the total processing time to less than 10 sec, and if possible, down to 1 sec (I’m currently at ~20 sec on my old 6/12 core/thread i7 machine))
But first: The basic concept in the algorithm - A Pipe Organ pipe (!):
Fig 1. The basic Concept - Point Inclusion test using an “Organ Pipe” as the volume in which to detect points:
You won’t forget this concept. And the idea actually works (quite well), and it works like so:
-
The algorithm traverses all mesh vertices.
-
Starting from a vertex, It uses the Vertex Normals to orient an imagined “organ pipe” in the vertex normal direction, with the organ pipe’s bottom tip starting at that vertex.
-
It then moves (the tip of the organ pipe) a tine little distance away from the current vertex, only slightly in the normal direction, so as to not include that start vertex in the point-inclusion check.
-
Then checks if any other mesh vertices are located inside the straight pipe section, or inside the bottom “cone”.
-
If the “Organ Pipe” has any points inside, then mark the current Vertex
(at the bottom tip of the organ pipe) for later deletion. -
When all the vertices has been examined, only then the algorithm finally deletes the vertices which were marked for deletion (this is to avoid costly updating of the mesh while traversing each vertex).
-
Finally it has cleaned (removed) any “marrow”, inner surfaces and “tunnel walls” from the mesh while leaving disjoined “islands” on the top surface in place.
Fig 2. Illustrating how an “Organ Pipe” starts from a vertex inside the mesh (but we wouldn’t know that yet). But from the picture we can see that the organ pipe has points inside (the green ones), which means that we should delete the point we started from (at the bottom tip of the organ pipe):
For the test to succeed, the organ pipe being used must have a diameter a little larger than the average edge length. It also needs to be longer than than half the thickness/thickest part of the mesh. The cone length will more “aggressively” detecting point inclusion the shorter it is, but you may find that it’s being a little too aggressive around tunnel openings if too short. See also §8 far below for problematic overhangs.
In order to understand how the parameters work shaping the organ pipe, I have a special mode for that (processing one vertex index at the time, see the “DebugDisplay” and the two sliders on top, connect them and detect one vertex at the time (by index) and study the pipe and its point inclusions).
Fig 3. Current processing time ~20 sec for the internalized mesh.
CONDITIONS & REQUIREMENTS:
The following conditions and requirements were the guidelines I had for the solution I needed, and which I solved using this concept. So read these as “my” (Rolf’s) requirements for cleaning up very trashy open meshes.
-
Meshes can be open or closed.
-
Cleanup must handle open meshes (even trashy ones full of gaps & holes and inner surfaces)
-
Cleanup must not distort the original surface (the vertices, that is), it may only clean up the unwanted internal fragments (“marrow” and tunnels etc).
-
Cleanup must not remove disjoined “mesh islands” being part of the outermost “want-to-keep” surface.
-
Cleanup must be fast enough for user interaction. Preferably under a second, but up to 10 seconds is not unthinkable. More than 10 sec (my current solution is ~20 sec9 is in the “take-a-coffee-break”-kind of processing time.
[Edit: Clarifications]
-
- Also notice that the core algorithm doesn’t have to collect ALL points that reside inside the organ pipe (this is done in my component only for debug/display purposes), it suffice to find a first point inside, then mark the current start vertex index (at the start of the pipe ) for deletion, break the loop and advance to test the next mesh vertex to test, and so on.
.
- Also notice that the core algorithm doesn’t have to collect ALL points that reside inside the organ pipe (this is done in my component only for debug/display purposes), it suffice to find a first point inside, then mark the current start vertex index (at the start of the pipe ) for deletion, break the loop and advance to test the next mesh vertex to test, and so on.
-
- It should be obvious, but a pipe which has no point inclusions will with 99.9% certainty start from a vertex on the “top surface” which you want to keep. So the pipe will simply not intersect with anything and instead just point into the infinite expanse outside the mesh - unless… se §8:
.
- It should be obvious, but a pipe which has no point inclusions will with 99.9% certainty start from a vertex on the “top surface” which you want to keep. So the pipe will simply not intersect with anything and instead just point into the infinite expanse outside the mesh - unless… se §8:
-
- OVERHANG - (§7…) unless there is an overhang in the mesh! Solution: Refine the LENGTH of the Organ Pipe so it doesn’t protrude into the overhang, or alternatively, segment the mesh where the overhand is problematic, then clean up the segmented parts separately, and finally join them back together again.
And again, the primary goal is NOT a water tight mesh with this algorithm, the primary goal is instead only to clean out the internal “marrow”, any inner surfaces (pointing inwards) as well as any so called “tunnels”.
In the initial post on the topic (link at the top) I describe more about the special needs I had for the medical poor quality meshes that lead me to find this solution, but the short story is there really is a need also for cleanup algorithms that preserves the top surface (vertices) of original mesh, with or without ugly holes in the mesh.
The current Grasshopper solution, not optimized and it hasn’t been refactored since initial “proof of concept” hacking. I also want to give credit to @RadovanG for his Point-In-Cylinder-Inclusion algorithm which I use for testing the straight section of the “Organ Pipe”:
[Edit]:
Replaced MeshCleanByOrganPipe 2024 R7-1.6.2. Use this 1.7.0 instead, which has a a less confusing core implementation.
MeshCleanByOrganPipe 2024 R7-1.7.0.gh (1.8 MB)
CONTEST
So, who’s going to be first with an algorithm passing under 10 or - ideally - under 1 second?!
No need to use my code, because the concept is simple to grasp. Fast code solutions isn’t equally simple to write.
//Rolf
