Nasty Mesh problem - finding the lowest depression

[RIL (Rolf)]

OK, this proved to be a tricky one. At least for me.

I have this bad mesh (and many others which are worse yet) and I want to automate finding the lowest path or depression along the bottom of the concave upper surface (se blue line), starting with only the mesh and the plane, as they are found in the attached file.

“Lowest” is here defined by the inclination of the nearby plane (never mind how I arrive at that plane) and not by the normal of the WorldXY Plane. Given is that the plane’s Y-axis is pointing upwards, and I want to find the blue line:

Viewed from the other direction (Edit: Hm, strange, the picture disappears…adding a new one):

Again, the plane’s Y-axis determines what is up and what is “downward” (down = anti-parallel to the Y-axis). And in this direction I want to find the bottom-most mesh vertices in the “valley” of the upper surface. The bottom-most vertice could form a polyline by following the mesh edges, but it can also be mesh vertices on both sides of such a polyline (the mesh can be pretty bad, so it’s ok to just collect whatever points on the surface which are not located in a hole or the alike.).

There can be several problems with the mesh, like holes, and trashy “splinters” inside the mesh, and some of this trash is not connected to the surface, while some of the crap is connected to the outer mesh surface. In any case, this trash cannot be removed by Disjoint etc, because it may destroy parts of the mesh where this “trash” still serves as a kind of “surface boundary” on really bad meshes.

The plane in this example is deliberately placed a bit off the deepest path, simply because it will never be exactly where the bottom line will end up anyway. The plane will only provide with an inclination vector (its Y-axis) and will never provide with any location hint regarding the geometry. This inclination vector will not detemine the “slope” of the blue line, only the "deepest depression along the “valley”.

In the second picture I have drawn the blue line zigzaging a little bit, which would represent how a polylinje would follow the edges of the deepest depression, but what I am after is a straight line, which if you had dropped a pen or a pipe in the depression, and it would then have rolled down and found a resting position at the “bottom” of the valley. This means for example that the nearest part of the blue line (say, the nearest 1/4:th of the blue line) should not influence where the “bottom line” should find its resting position.

In this particular case the line would probably end up in a position something like in the following picture. One could think of including vertices to a depth of e “pipe radius” so as to get more points indicating “bottom-most”:

The final line would be a Fit Line based on the bottom-most mesh vertices found. For some reason this particular case seems being trickier than I first thought, but if any of you guys already have solved something like this I’d be happy to learn your trick. Hint: Deformities and holes in the mesh can cause serious trouble.

Files:
line_in_groove_forum.3dm (1.1 MB)
line_in_groove_forum.gh (7.6 KB)

// Rolf

[PeterFotiadis (Pfotiad0)]

@RIL

never mind how I arrive at that plane

You mean that you have the plane on hand and you want to play connectivity games between faces (ccx with plane where the DotProduct of a given face normal [IF the bad mesh can yield “reliable” normals] … blah, blah), vertices and neighbor vertices? (indices List intersections etc). All that provited that the extracted connectivity has some reasonable meaning (because the mesh is bad by definition … meaning bananas on sight). Or you want to bounce recursively an indicative candidate plane (say: “left/right”) and for each loop to narrow the bounce domain?

And why you do bad meshes? Are you a bad boy?

[RIL (Rolf)]

@PeterFotiadis

You mean that you have the plane on hand

Yes, the Plane is a given. Its origin is long derived but not relevant to the problem other than the Y-axis direction pointing somewhat upwards. Its anti-parallel direction is what defines what i to be considered being the “bottom” of the valley (of death).

@PeterFotiadis

and you want to play connectivity games between faces (ccx with plane where the DotProduct of a given face normal [IF the bad mesh can yield “reliable” normals] … blah, blah),

No problem with the MeshFace normals, I can calculate them very fast from the connected edges of each vertice, no problem. I can also easily “project” any normal against the plane to determine it’s alignment with the plane, one dimension at the time. And so on. That will still not solve the problem though, since there are plenty of MeshFaces with the “correct” normal direction also far from the “bottom of the valley of death”, for example on top of the humps on both sides, and inside the mesh (all the crappy marrow splinters etc).

And a said, the location if the plane is in no way indicative of there the bottom line is located, not even its direction in the more horizontal plane. Only the Y-direction is useful from the Plane.

@PeterFotiadis

the mesh is bad by definition

It can be much worse than waht you see pictured. For this reason I tend to use, not single vertice or Face Normals, but “average face normals” based on the connected vertices/edges from each vertice (it gives a kind of smoothing effect on the normals, which is perfectly OK for this case).

@PeterFotiadis

Or you want to bounce recursively an indicative candidate plane (say: “left/right”) and for each loop to narrow the bounce domain?

I didn’t really understand what this meant.

@PeterFotiadis

And why you do bad meshes? Are you a bad boy?

These are the source meshes I have sent to me. Medical scans (CT or MRI) of sometimes catastrophic bad quality. OTOH they were never meant for making beautiful renderings…

Trying to be a good boy while dealing with all the bad meshes is a strain though. It has trashed so many attempted strategies of me to find this bottom line of the valley of death. It stumped me that I didn’t solve it already. But here I am. Hat off. Humiliated.

// Rolf

[PeterFotiadis (Pfotiad0)]

@RIL

the valley of death.

I like dark things, death and the likes … meaning that I’ll try some ideas soon on that puzzle of yours.

[RIL (Rolf)]

@PeterFotiadis

I like dark things, death and the likes

Hm. Please stay away from the dark stuff. The valley of death, on the other hand, is the road most travelled, although not by choice…

Anyway, all ideas are welcome. perhaps some combination of ideas will hold all the way. As for me I grossly under estimated this problem (but bad meshes is worse than one might imagine before trying to outsmart them).

// Rolf

[gerryark]

I don’t have a solution but I would start :

a) transform the mesh from the world XYZ plane into a plane with Z axis parallel to the input Plane Y axis
and X axis parallel to the input plane X axis, this will simplify my routines since the lowest path will be simply the one with Z values “down”
b) at this point the path (IF THERE IS ANY) will be within 2 parallel planes X-Z
c) a Divide-and-conquer method could be the next step

m2c
gerry

[RIL (Rolf)]

@gerryark

the lowest path will be simply the one with Z values “down”

Rotating the whole thing to make the plane’s y-azis parallel to WorldXY’s normal (Z) axis can be done yes. The difficulty lays elsewhere though. Like the fact that a huge number of vertices in the mesh will have Z values way below the (upper) surface vertices which I’m interested in.

Sharp turn
The path will also tend to drop drastically at one end while at the same time turning away to one side, so one would have to detect where the path makes that drastic turn and skip that part of the mesh (see the blue zigzag path drawn in the middle picture above, where the path at the near end turns to the right while it drops).
The “elevation” of the vertices along the path doesn’t matter though, only its “sideways” deviation must not push the path away from the “bottom” location where you would put it if you picked it manually. A similar “sideways” problem is described next.

Cavity to te side
The path is also typically forming a “long curve” from one end to the other (the black curve pictured below). This means that any straight line tends to be attracted to one side and off the actual lowest path, where it would be located would you drop a pen and let it roll down to a resting position.

I tried to illustrate this in the picture here below: The black curve being the “true bottom curve”, and the blue straight line would be where a pen would find a resting position, and the white straight line represents how the blue line drifts off in the indicated direction due to the curvy (black) path (if only collecting vertices and draw a FitLine through them). So upon occular inspection the final line tends to end up being a bit “off” like the white line below:

Depending on strategy, different features of the mesh tends to pull your leg.

// Rolf

[RIL (Rolf)]

The problems described so far could indicate that perhaps only a collision strategy would avoid drifting away with the straight line.

// Rolf

[gerryark]

Hi
I am more a scripting guy so when I speak about transformation
I mean a Transform from one frame to another, its the same thing as a rotation at the end but conceptually speaking we are working in 2 different spaces.
After transforming Z values become the key values to base my path detection at the beginning.

so Maybe the next step would be working on the mesh edges , finding 2 opposite points
and last finding a path between these points , my guess would go to a geodesic path or similar approach

gerry

[Louis_Leblanc]

Just to be clear, would the final “pipe” line be in a plane parallel to your shown plane? Also, are all your meshes roughly saddle shaped?

To get your blue polyline, it seems like a rain fall simulation would get you there, especially once you rotate it as @gerryark suggested. But it sounds like getting that polyline may not be necessary if you’re really only after that straight line. If you’re dealing with a saddle shape and your pipe line is in a plane parallel to your initial plane, you just need to find the inflection point. IE the red point in this image:

[RIL (Rolf)]

@Louis_Leblanc

Just to be clear, would the final “pipe” line be in a plane parallel to your shown plane?

No. The plane’s horizontal axes can be very much off. Only the “upward” direction (and it follows, downward direction) is determined by the plane. Nothing else. The plane’s location and (horizontal) rotation can be very much off.

@Louis_Leblanc

Also, are all your meshes roughly saddle shaped?

Only in the best case. Don’t count on that. As @PeterFotiadis use to say; The road can be hilly.

At the end of the (desired) path you would typically find that the shape is saddle-like on one sida, while steep down on the other side. Which means that that part of the mesh should not be considered since it makes the path make a turn to the ide while dropping downwards.
(See an example of that at the “near end” of the blue zigzag curve I drew in the second pic in the first post).

@Louis_Leblanc

To get your blue polyline, it seems like a rain fall simulation would get you there

Except for the holes, and the “sideways” problems mentioned, which makes the final FitLine drift off.

@Louis_Leblanc

But it sounds like getting that polyline may not be necessary if you’re really only after that straight line.

True, finding that path would only be a tool in one strategy. A strategy which tends to end up in lots of trouble (the sideways drifting tendencies mentioned).

@Louis_Leblanc

If you’re dealing with a saddle shape and your pipe line is in a plane parallel to your initial plane, you just need to find the inflection point. IE the red point in this image:

A point is not sufficient. I need a line, along the cavity. That will later be used as a direction, which is why a single point is not enough.

So, a “bumpy” or a “hilly” saddle is what the meshes will provide, at best. Non-saddle like parts to be identified and pruned off, if that strategy should be used at all.

Tricky this, but thanks for all the suggestions. It makes the problem more clearly defined.
(I told you, I was stumped by the difficulties I discovered as I tried different strategies)

// Rolf

[PeterFotiadis (Pfotiad0)]

@RIL

Please stay away from the dark stuff.

Hmm … advising the Lord of Darkness NOT to like the darkness is kinda selling a tuned Harley Davidson to a Ducatista.

Anyway (if we forget for the moment the more or less static nature of the section plane) … is this indicative setup (again: just a setup) a starting point for finding the truth out there?

Note: no further tricks are done in the affected mesh faces nor any classification/filtering etc etc.

Note: since a given plane yields the sectioned mesh faces (thus you can extract anything out of them) if we establish some rules … is the whole issue just about how to control the section plane?

Mesh_ValleyOfDeath_V1.3dm (305.6 KB)
Mesh_ValleyOfDeath_V1.gh (116.2 KB)

BTW: For what a recursive bounce could mean: just play with a given T value (+/-) and imagine narrowing the domain for each step.

[RIL (Rolf)]

Edit: Spelling (sigh).

@PeterFotiadis

is this indicative setup (again: just a setu p) a starting point for finding the truth out there?

It could be. Some benefits with this approach:

1. Only MeshFaces located along a straight line are now candidates for further processing. That is a good thing.
2. The Plane could now iteratively move sideways (T) but also rotate about the up axis to find the direction of the cavity. Q: How to determine that?
3. I’m trying to decide if this approach actually would be insensitive to the bottom-path turning away to one side at the end of the path, or if that part of the mesh would tend to rotate also this plane off the center of the “obvious cavity”, so to speak. This mesh perhaps is a bit “too ideal” in that respect.

Potential problems (but you may have solutions for that) are such faces which do not belong to the “uppermost surface”.

I say “uppermost” surface because if there are holes in the mesh and you find a MeshFace located on a splinter inside the mesh instead, which is also facing upwards, then it might not be trivial to determine if that MeshFace belongs to the group of interesting ones (faces in the “upper surface cavity”, that is).

The approach is interesting however, and it is one strategy which I actually have not tried.

Either this strategy, with some iterative moves sideways (T) in combination with rotating the plane to align it with the cavity’s direction, or an outright collision strategy (like dropping a pen and let it roll down into the cavity into a resting position) may give the desired straight line.

In any case, this strategy looks interesting for sure. Trying any strategy on the mesh I attached may send you into the dark, though.

Edit: The marked part of the mesh would perhaps tend to “attract” also your Plane to rotate towards the steep slope, if applying an iterative approach trying to find the direction in which the intersected faces sums up to the lowest Z-values. I talk more about these “sideways” tendencies in earlier posts.

// Rolf

[PeterFotiadis (Pfotiad0)]

@RIL

Trying any strategy on the mesh I attached may send you into the dark

Well … that’s a R6 file and R5 can’t read a thing (or two). But I guess that you could do a R5 version.

In general this puzzle (in “auto” mode) is a classic trial and error problem:

First (and here’s why I posted that as a “startup”) we must know approx the response time: is a given solution of that type fast enough? Or it takes a year and a half to finish? If is slow shop elsewhere.

If is speedy …

… then start from some plane and depending on the results (and some strategy) do corrections towards some desired goal (by narrowing continuesly the domain of the possible solutions: hence the “bounce” moniker). Classic recursion, that is. That said finding the mesh face with the lowest Z is a matter of milliseconds (something to start anyway). Equally finding the average … er … of whatever out of the red mesh faces in the C# is also a matter of milliseconds.

But what if there’s more death valleys around? What if the mesh is a first class mess? What if we run out of espresso? (or Vodka).

[RIL (Rolf)]

@PeterFotiadis

Well … that’s a R6 file and R5 can’t read a thing (or two). But I guess that you could do a R5 version.

Absolutely:
line_in_groove_forum.3dm (1.2 MB)

@PeterFotiadis

is a given solution of that type fast enough? Or it takes a year and a half to finish? If is slow shop elswhere.

Speed is definitely of concern, but it doesn’t matter at all if I don’t get my line in the right place. So yes, I would actually have applied a Galapagos/Cylinder collisions approach if I could control start and stop of th Galapagos component. Terribly slow, yes, but slow is better than nothing.

Speed matters because of the fact that I have hundreds of these meshes to process.

And yes, running out of Java would definitely be a very serious problem.

But if you look at my last exaggerated illustration of the sideways slope; If that deviation from an “average” direction of the groove can be identified, and thus oen could chop off the mesh where my red arrow starts go downwards (as part of the iterative logic), then that part of the mesh could no longer influence the recursive algorithm.

I think that -generally speaking - a simple algorithm is worth preserving, if it can be preserved by removing subject data which tends to deceive it into bad habits. So I still find your basic approach interesting. Not sure though how to identify that nasty slope, which would probably ruin a simpler algoritm based on finding the lowest sum of face.Z values.

// Rolf

Edit: Let me also make clear, as one of the rules, that the given Plane can be moved back and fourth “sideways” (that is, parallel and anti-parallel to its Normal. And that it may freely be rotated about it’s “up” direction (Y-axis in this case). Like so:

[PeterFotiadis (Pfotiad0)]

Well for a recursive trial and error approach speed is what color is for a proper Ducati.

I’ll test (armed with just arrived cigars and other spiritual aids) some things using your mess … I mean mesh (that said I hate meshes).

[RIL (Rolf)]

I have no doubts that speed will be good enough based on your approach, since there’s not very many faces to deal with after the intersection with the plane. Moving and swirling the Plane around for a second or two would be totally acceptable, if only the line lands where it should.

I’m holding my breath.

// Rolf

[PeterFotiadis (Pfotiad0)]

That said you don’t need to rely on that plane for everything: just having some startup route to follow … for the rest you may (or may not) use other type of stuff: for instance in this C# you choose randomly mesh faces as source of water and then you calculate where all that water goes. Recursion and 41 milliseconds for that one. A similar addicional technique could be used in your case (not sure up to what extend, mind).

[PeterFotiadis (Pfotiad0)]

BTW: Your thing is not only pig ugly but is invalid as well (after combining vertices and doing other mysterious things). Not sure what this means with regard reliable connectivity data.

[PeterFotiadis (Pfotiad0)]

@RIL

I’m holding my breath.

Under the proper influence of proper spirits (frozen Stoli Elite) here’s the best solution:

1. “Scan” the ugly thing either in auto or in manual mode (i.e. make a plane and get the red mesh faces). This also defines the reference Vector (i.e. what is “up”). That said the manual mode is way better because I can think at least 666 cases where you can’t clearly define a death valley (or you need a lot of code to do a thing that you can resolve using your eyes/brain in a millisecond).
2. Get the face that has the top-most (with regard the “up”) center.
3. Do some drainage type of solution (note: if connectivity is not correct > bananas on hand) and mastermind a clevel condition to stop the recursion (that’s the 99.99% of the whole thing) from looping until the end of time. This also means: restrict the recursion only to the up most (obviously inter-connected) red faces.
4. Or do the 3 for every proper (facing “up”) face from 1 and combine the results (but why?).
5. Having the faces on hand do whatever suits you next.

Some entry level tests on all that soon.