Cleaning up Inside Meshes - Speedup Contest

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:

1. The algorithm traverses all mesh vertices.

2. 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.

3. 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.

4. Then checks if any other mesh vertices are located inside the straight pipe section, or inside the bottom “cone”.

5. If the “Organ Pipe” has any points inside, then mark the current Vertex
(at the bottom tip of the organ pipe) for later deletion.

6. 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).

7. 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.

1. Meshes can be open or closed.

2. Cleanup must handle open meshes (even trashy ones full of gaps & holes and inner surfaces)

3. Cleanup must not distort the original surface (the vertices, that is), it may only clean up the unwanted internal fragments (“marrow” and tunnels etc).

4. Cleanup must not remove disjoined “mesh islands” being part of the outermost “want-to-keep” surface.

5. 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.
.
• 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”:

:
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

1 Like

I also want to point out that the code implementation in the script component is bogged down with debug code, and alternative code paths for debug and illustration purposes which I need while I was developing the concept. Therefore there is I’d say 3 or 4 times more code in there than is needed for just doing what it’s supposed to do - clean up a mesh.

I have commented the logic, but the comments are spread out on the different variations of the code (the alternative code paths are all valid, but although the look similar, they do its thing in different ways, depending on the debug or display input-settings. A final version doesn’t need any of those variants.

//Rolf

Guess something is missing.

probably not a good idea to install random dlls

Ouch! I had actually put the code from the DLL-library locally into the script component, but forgot to remove the DLL-reference.

Here’s a version with the dependency removed:

Sorry for that glitch.

//Rolf

Repair Scanned Mesh Dendro v0.gh (40.4 KB)
A solution with voxel tool Dendro.
The mesh used in this definition is from here:

I think I’m missing something because start and end mesh look exactly identical

Hi again @Quan_Li, this solution is, of course, very interesting due to its incredible speed! Wow. Very impressing.

It’ll take some time for me to grasp what/how this GH definition works, since there are no comments or explanations nowhere to be found, no groups of functionality, and also the sliders doesn’t hint on what it affects if not already knowing what it does.

I’d appreciate very much if you could add some explanations for the overall concept, and comments on groups of components.

The first thing i notice is - except for the incredible speed (…!) - is that this algorithm, with the parameter settings you posted, leaves many “tunnels” in place (they need to be cut out as well), and also the edges where the inward pointing surfaces has been removed, still have their edges wrapped quite far inwards before cut off. This causes two problems, depending on the use case

1. the inward wrapping edges still is significantly on the “inside” of the mesh (disturbing measurement algorithms).

2. It’s difficult to make meaningful hole-patches from these edges.

But this seems to still be a very interesting approach, if I only knew how to tweak it to adress the mentioned problems. (Since I don’t really understand what the sliders do, I wouldn’t know if that can be fixed with other slider values)

// Rolf

Ah, it’s that “debug/display” thing that is spooking you. If you disable the “Collect Inclusions” button, then the “full algorithm” will run as expected.

//Rolf

1 Like

Here I show what I mean with the “wrapped/rounded” edges in tunnel openings. In my mesh the “tunnel walls” are cut out fairly aggressively, which is a must for my use cases:

//Rolf

I wrap the original mesh with a cloth, and calculate every face center to the cloth and remove the faces(marrow) not in the range.

Here I show what I mean with the “wrapped/rounded” edges in tunnel openings. In my mesh the “tunnel walls” are cut out fairly aggressively, which is a must for my use cases:

The definition will not deform the mesh a bit, but cull. It culls the inner mesh faces that have distance larger than X mm from the wrapper. The wrapper mesh is made by Dendro.

The logic is exactly same as the last one posted under your other thread, only that solution used K2 to make the wrapper mesh, but this time, it is Dendro, which is much faster.

So, the key points are:

1. How to utilize Dendro.
2. How to define the cull range.

I think @laurent_delrieu has a much better understanding of how to use Dendro. Maybe we can ask for his help. @laurent_delrieu Would tou please shine some lights on this matter in terms of how to make the cull mask more accurate?

1 Like

Ok, I understand. That also explains why the cloth follows the surface down the holes & tunnels a bit, leaving a bit too much of the rounded edge-slopes intact.

If the “cloth” could have a certain “tension” in it as to not dive to steeply into holes, then that problem would decrease. To make it near perfect I guess one would have to insert “islands” to fill out bigger holes before wrapping the whole thing with a “stiffer cloth” and then also the current rounded edge-slopes would be cut out with your current concept.

BTW, can Dendro be used by scripting it with C# code?

As for my current C# code algorithm, it can probably be optimized using “yield” at first occurence of a point inclusion, thus short cutting the algorithm as much as possible.

: I know @gankeyu would code the core algorithm much faster than me (I’ve seen that happen more than once), if we only could get him interested in the contest…

//Rolf

Really suck at scripting. I have no idea. But seems Dendro is open source.

SIMPLIFIED CODE
I replaced the originally posted version “MeshCleanByOrganPipe 2024 R7-1.6.2” with a new version (1.7.1), a refactored code-compacted new component containing only the less confusing core algorithm.

Fairly straightforward code in this one with all the debug/display-stuff removed.

//Rolf

I add description and preview. Now you can clearly see which parts are removed.

Thank you!

I think your solution is very much useful, also for me. It only doesn’t cover all my criteria. But in many cases your solution is sufficient. It’s a very nice and fast solution for what it does. very good!

I’ll study it more in detail and see if I can get it to cut out the tunnel/hole-walls as well. The speed is very valuable.

//Rolf

I just turned on optimization and didn’t modify the code.

1 Like

Wow! How do you turn on optimization?

//Rolf

I enabled optimization according to your instructions and it’s really a speed up of ~4x. Very nice.

But when I compiled the same code in VS2022 I’m back at ~20sec. Is there anything I can do to speed up the std VS2022 compiler?

(My own DLL Library is .NET Framework 4.8, and I’m still mainly using R7)

//Rolf