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: [c516d836a7a40e19f2a4a8a622a497c0] 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): [image] 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. [image] 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. . 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

MeshCleanByOrganPipe 2024 R7-1.7.3-Gan.gh (1.8 MB) [image] Newer versions of .NET put it under 1s with Rhino 8. [image]

[image] inno: I think I’m missing something because start and end mesh look exactly identical 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. [image] //Rolf

[image] Rolf: the inward wrapping edges still is significantly on the “inside” of the mesh (disturbing measurement algorithms). It’s difficult to make meaningful hole-patches from these edges. 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: [image] //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: How to utilize Dendro. 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?

[image] Quan Li: 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. 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. [Edit]: 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… :sunglasses: //Rolf

Really suck at scripting. I have no idea. But seems Dendro is open source. [image] GitHub - ryein/dendro: volumetric modeling for grasshopper built on top of... volumetric modeling for grasshopper built on top of openvdb - ryein/dendro

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. MeshCleanByOrganPipe 2024 R7-1.7.1.gh (1.8 MB) Fairly straightforward code in this one with all the debug/display-stuff removed. [image] //Rolf

Repair Scanned Mesh Dendro v2 preview.gh (1.8 MB) I add description and preview. Now you can clearly see which parts are removed. [image]

[image] Quan Li: I add description and preview. Now you can clearly see which part is 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

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

[image] Keyu Gan: I just turned on optimization and didn’t modify the code. Wow! How do you turn on optimization? //Rolf

Cleaning up Inside Meshes - Speedup Contest

Grasshopper

gankeyu (Keyu Gan) April 10, 2024, 1:39pm 19

Topic		Replies	Views
GH: Mesh Masters: How trim away inner surface & "splinters"? Grasshopper rhino5	14	4689	June 21, 2017
Mesh Fill Holes - Best strategy? Grasshopper Developer	27	10571	October 3, 2018
C# Create a mesh with a hole inside Grasshopper Developer	31	6091	November 6, 2020
Shrinkwrapping complex geometry Grasshopper windows	29	6033	September 2, 2022
Super-super fast Point Inclusion test for Cylinder/Breps? Grasshopper Developer	70	9623	July 26, 2017

Cleaning up Inside Meshes - Speedup Contest

Related topics