Cleaning up Meshes Inside(?) & Potential Speedup Contest

[RIL (Rolf)]

[Edit: Category → Grasshopper Dev]

Ok, so I’ve been thinking about this problem for a while - more specifically the problem with medical scans which typically are filled with mesh fragments and tunnels and… all kinds of crap - crap which you would typically like to get rid of.

In my case I had the need to get rid of “marrow” from the scans so that it would not affect many of the algorithms I had for making different measurements aso.

Q1: Does anyone have this problem with crap-filled meshes which Shrinkwrap doesn’t solve?

Although the Shrinkwrap concept came into existence while I was struggling with this problem, to this date I’ve not tried it out extensively, so I don’t know if it can fix all the problems we face with crap-filled meshes. But what I have tried is dozens, if not hundreds of approaches to cleaning them up, but none of them was very good at it, or were too slow or “involved” or just not very useful in practice.

Then one day it dawned on me. How to clean out the inside of meshes with one (conceptually) simple method.

I hacked something together and tried it, and long story short, it worked.

The method is predictable with simple to understand parameters to adjust how aggressive it performs its cleansing (like how much (width) of a tunnel-opening it would cut out etc). Only limitation I’ve found (depending on overall shape of the mesh) is overhangs, but if known minimum concave radii in the surface of the shapes is greater than half the thickest part of the mesh, then not even that is a problem. If not, one can segment the mesh (splitting out overhangs) and process them separately and re-join then again after. Since tunnels will be cut out, the algoritm will leave holes behind, when needs to be filled. No big deal, but needs to be pointed out (the algorithm cleans and cuts, it doesn’t “heal” so to speak).

Enough about that. The first question if of course - does anyone have this problem with crap-filled meshes which Shrinkwrap doesn’t solve?

Q2: Second question is: If Shrinkwrap doesn’t solve all problems, which problem(s) are those?

Q3: Putting it all together - is there any actual need in the community for an algo that does what I describe?

If there’s enough interest I would consider taking the time to make a description of the algorithm in more detail (the core idea can be illustrated with one simple picture) and the smartest C# programmers in the community could join in optimizing the code to make it perform even faster (I’ve not done any code-optimization whatsoever this far).

//Rolf

Examples of mesh scans full of “marrow”:
Glenoid:

Scapula:

[martinsiegrist]

Interesting. I’m usually checking my meshes in Artec Studio before I export them so there should be no crap inside and small fragments get deleted.

[RIL (Rolf)]

Fragments can be tricky. Although one can use SplitDisjointMeshes (or whatever the command name was) and then delete the disjoint fragments, you still often have (at least I have) cases where you definitely do not want to scrap all disjoint bits, like “island fragments” of the actual surface which you want to keep.

The of “do-not-delete-ALL-splinters”-case; The red little “box” inside you would like to get rid of, but not the “surface island”:

My algorithm would keep the green “island” but delete the red box inside.

//Rolf

[martinsiegrist]

Have you tried Shrinkwrap with a positive offset and then a second Shrinkwrap with the same distance negative offset yet?

[RIL (Rolf)]

@martinsiegrist

Have you tried Shrinkwrap with a positive offset and then a second Shrinkwrap with the same distance negative offset yet?

No, I haven’t tried it much at all. That’s why I’m asking if people have cases where it doesn’t solve all related problems.

I started struggling with the problem around 2016 something, and then came Shrinkwrap so perhaps Shrinkwrap makes my algo redundant.

The only thing I know that Shringwrap does which may be a problem at times, is that it actually replaces the original scan. My cleanup algo only cuts and deletes, it doesn’t change the topology (meaning, it doesn’t touch the vertices that are part of the surface to be kept)

//Rolf

[RIL (Rolf)]

WORKS ON OPEN MESHES

@RIL

The only thing I know that Shringwrap does which may be a problem at times, is that it actually replaces the original scan. My cleanup algo only cuts and deletes, it doesn’t change the topology (meaning, it doesn’t touch the vertices that are part of the surface to be kept)

Well, another problem I just recalled was that, with a very bad and non-closed mesh, full of crap in the holes and cavities, the Shrinkwrap method tends to dive into these holes and tries to make a surface down there… which typically ends up in tears. And long processing times to end up in a bad place.

In my cases I only wanted to get rid of the inner fragments (since they affected other algorithms while the trashy open surface still served well for measuring the overall geometry) I would not be helped by Shrinkwrap since it would tend to go bananas with the bad open meshes.

Perhaps I should have pointed that out - the algo doesn’t care about open or closed meshes, which may be important to some (it was essential to me).

Examples of what disastrous meshes I worked with where only the “marrow” was a problem for my measurement algoritms, while the broken “outer” surfaces was not a showstopper:

The point in the pictures is/was operation planning & research (comparing bone morphism before and after operation etc) where different measurements on the 3D mesh would be collected.

Terrible meshes but, the reason why so many medical meshes are bad, is that they try to limit radiation as much as possible when performing CT-scans. Good for the patient, but a nightmare for programmers trying to make (geometrical) sense of the scans…

//Rolf

PS: The markers (white bubbles with ID’s on them) are measurement points which you would find in various scientific papers.

[martinsiegrist]

Oh wow this is interesting stuff!

[Quan_Li]

Please upload the mesh.

[RIL (Rolf)]

@Quan_Li

Please upload the mesh.

??

This isn’t about my meshes, it’s about an algorithm. And about a question if other people have #1. open meshes with #2. inner fragments which cannot be fully cleaned up using Shrinkwrap.

//Rolf

[Quan_Li]

I might know the solution, but without mesh there is no way to verify.

[RIL (Rolf)]

You could try on the following scapula. The humeral head is already cleaned. As you can see, the scapula is full of “bone marrow”:

I had to zip it down to make it small enough to upload:

Humerus-Scapula Isotropic trashy.zip (4.1 MB)

//Rolf

[Quan_Li]

Wrap Back v0.gh (11.9 MB)
The idea is simple. Get the overall shape, then shrink it and wrap the the original. There are many ways to implement this idea, this is certainly not the best.

Tri or quad remesh doesn’t matter at all.
Higher in remesh, higher in detail.

[RIL (Rolf)]

DEFINITELY INTERESTING
Thank you for the suggested solution. I will examine it more in detail asap.

At a first quick look it definitely looks interesting for some aspects, since it covers holes etc. and therefore it may be useful for some cases or for aspects of cases. But the solution, with the parameters as posted, also distorts some aspects of the final surface (which perhaps can be corrected with the parameters(?), but I haven’t had the time to try to figure out how all parts of it works as of yet).

One reason why “too much smoothing” of a bumpy surface can be a problem (in my cases) is for example when creating guides for drilling or cutting, the guides may “land” on the surface very differently if the real bone and the CAD-version of the bone differ significantly.

Think of a small plastic drilling guide as a three legged “moon-lander” to be pressed against the bone during an operation.

Think of a spine vertebrae for example. A guided drill direction can become catastrophically off if one or more legs of the guide lands on a bit of surface that has been raised or evened out (“smoothed”) and so you are at risk of drilling into the central nerve canal… (this happened to my dad, resulting in a “clump foot” for the rest of his life). You get the idea.

For this (the above) reason, you sometimes simply do not want to replace the original mesh, only clean it up, removing any unwanted vertices while leaving every original vertice (being part of the surface you want to keep) in its original location after cleaning, as I described in earlier posts.

That being said, this kind of solution may still be useful for some (other) aspects of the analysis of the bones (for example rough probing of topological features of the “want-to-keep” surface) and then finetuning locations to the original mesh surface at the finalizing stages etc.

But as said, I’ll study your solution in more detail to have a better understanding of its potential for my cases.

SUMMARY OF REQUIREMENT

I should perhaps clarify the main requirements I’ve had to meet:

1. Cleanup must handle open meshes (trashy, full of gaps & holes)
2. Cleanup must not distort the original surface, only clean up the unwanted internal fragments,
3. Cleanup must not remove “islands” being part of the outermost “want-to-keep” surface.
4. Cleanup must be fast enough for user interaction. Preferably under a second, but 5-10 seconds is not unthinkable. > 10 sec is in the “take-a-coffee-break”-kindof processing time.

I would also like to clarify that the (my) primary goal is not a water tight mesh, instead it is a mesh (open or closed) which doesn’t distort any measurements or true surface topology for making operation guides AND - this is also important - is accurate enough to compare different scans of the same bones scanned at different points in time.

Comparisons, before, immediately after and 2 or more years after an operation, will reveal how bone tissue reacts to the operation.
If you for example transplant a piece of bone tissue and place it even a little distance off a location in which it was supposed to be subject to stress (in a joint for example), then the non-stressed bone transplant will regress like a sugar-cube melting a way in a cup of hot coffee. Just like muscle tissue, also bone tissue is preserved or even strengthened only under a minimum amount of stress. If not being subject to that minimum amount of stress it will simply disappear over time. This is why “too much smoothing” isn’t going to tell you the truth about whether a transplanted piece of bone where successfully placed or not, when comparing scans taken years apart.

Sorry for the long explanations, but I really mean it when I say that there’s need also for cleanup algorithms that preserves the original mesh’s top surface, with or without holes in the mesh.

// Rolf

[edit: Spelling & clarifications]

[Quan_Li]

I suggest you make a post under category of grasshopper. This is an interesting case.

[RIL (Rolf)]

@Quan_Li

I suggest you make a post under category of grasshopper. This is an interesting case.

I originally put it under the Grasshopper category, but changed it for now so that my question would reach also other users than us Gh geeks.

I really wanted to know if also other users had a similar problem before putting too much effort into perfecting a potential solution.

But yes, if it is of enough interest to dive deeper into a solution, we can start a new thread. I’ll be very busy for a couple of days though. I’ll be back on this later.

//Rolf

[Quan_Li]

Repair Scanned Mesh Dendro v0.gh (40.4 KB)

Faster.

Repairer scanned mesh/remove inner faces

[RIL (Rolf)]

@Quan_Li

Faster.

Very interesting!

But, would you like to move this answer to the other thread so we can keep a discussion about solutions together in one place? → (Cleaning up Inside Meshes - Speedup Contest)

I would comment further in the other thread.

// Rolf