# Nasty Mesh problem - finding the lowest depression

Hm. I started to think that perhaps a ConvexHull (polyline) around the faces found (for example those inside the yellow box) , could provide with an answer (not the only answer perhaps, since the “average height” of the upper faces would not all be included in a ConvexHull profile) .

But at least a ConvexHull would refuse to dive into holes, and where the direction of the (ConvexHull) polyline changes direction (as projected on the flat plane), there you would simply cut the polyline in both ends.

The blue line here is a 2D “ConvexHull”, and the red arrows is where it “changes direction”, and thus where to cut, and the red X means, scrap the part of the polyline between the two points of “direction change”

The remaining polyline and its segments, would then be the remaining subject to height-calculations to determine if it is indeed the lowest path in the valley.

Then also very step slopes at the ends could be filtered away, with a max tangent angle etc (to avoid the suspicious influence of steep slopes to the sides which can occur at both the start and ends of the bottom path of the valley).

Perhaps a combination of strategies would do.

What do you think?

// Rolf

Imagine 2 layers very close together. The upper has a hole and thus the RayShoot includes portions “visible” belonging to the 2nd layer. The convex thingy can’t cut the mustard on that … but a planar Brep out of the section polylines (including pockets) … maybe just maybe. Then you just test for inclusion in the BrepFace.

But here’s a convex hull that contains everything (no elimination of any kind active). But we need the big string plus the upper portions of the 2 small ones on the right.

Dot filtering:

RayShoot filtering (with the known “visibility” issues)

perhaps the Mesh-Plane intersection polyline, with gaps, could be used to detect distruptive changes in “elevation” (say, max tangent angle +/- 75 degrees or something), then one would know to jump that segment (bottom blue segments) and go for nearest segment with a line end with an acceptable tangent angle interval:

By jumping the abysses a reasonable path line is patched from any deeper holes and. Well, so on.

// Rolf

But if the z gaps are very small (layers close together AND big holes) … we are still in that rabbit hole (the rat hole in fact). Only classic connectivity (stripe to stripe so to speak) could cut the mustard on that rat-puzzle.

WAIT A MINUTE:

Did I made the mother of all mistakes with regard the RayShoot filtering? Yes I did it because I tested the faces - out of the section - PRIOR their final formation into separate stripes (on a mesh disjoint approach basis + Dot filtering). This means in plain English: if a given mesh (in the disjoint meshes list) has ANY face with RayShoot “upwards” issues (against mesh M) … then just forget the WHOLE @%@ mesh.

How The Lord (the Merciless King of Sardineland) did such a colossal/miopic mistake?

Answers to: The Lord, District 9, Apartment 666, North Pole.

BTW: Of course if the upper layer has normals that yield Dot < 0 (against the orientation Vector) this means that the Dot split (so to speak) fails and thus … back in the rat hole.

But a mistake is a mistake anyway.

Update:

Dot filtering (case: freaky meshes) is out: adios amigos (if the upper valley layer is heading south VS the orientation vector > bananas on hand).

Enter the double RayShoot filtering : any stripe against themself (thus the split is sure) … plus … the final RayShoot (stripe to stripe) as exposed above (sorting them as in V1C is rather a must).

But … assume that everything works and we arrive into that situation: the lower stripes could being discarded safely (in the V1D) … but what about the left stripe? what if it belongs to another layer under the top?

A two pass strategy perhaps can figure out some kind of slope angle and update that direction of the orientation vector? (rotating it to align to the slope only “on the plane”, so as to not tilt the plane itself)

Grandma is never going to give up. Never. But is that really a Ducati?

// Rolf

Hm. I don’t think that will be the case. In your image (at T = ~0.415) you have the special case of a Mesh being cut, which was … well, I don’t remember why I cut it (manually) at the bottom so close to the surface.

But in any case, no, disregard that thing. It probably won’t happen. And even if it would happen, the lowest top-surface in that area will still be at a lower elevation than in this mesh (but that area, with a drop in altitude, was cut off in this mesh. Sorry for that).

Also. whether the ConvexHull alone is to determine the final outcome (sum of Z:s), is the question.

I wonder if not the yellow parts (marked) of the actual surface are the most significant in determining the actual average elevation of the upper contour. That is, despite any bumps or “ups” at the end, the actual (yellow) contour would not be fooled - the hollow would not lie, instead it would indicate that we are now at a fairly low overall bottom path (only holes could fool us). But the ConvexHull contour would tend to think we are along a quite high path, despite the “true” cavity along the yellow part.

Edit: But then again, a ConvexHull stripe would actually be more in agreement with for example a pen being dropped and rolled down to a resting position in the valley. Hm. And that is probably the very path that I’m after.

That path could still be adjusted by sweeping a pipe of radius R around the line arrived at from the ConvexHull strategy, and in so doing, apply a more “statistically” smoothed FitLine. But that can be done AFTER the ConvexHull strategy is finnished. A kind of “two alternative solutions” thing.

// Rolf

BTW: I was ready to do a classic connectivity approach (never fails) … but your mess yields an invalid thingy after messMesh.Vertices.CombineIdentical(true,true); … meaning that I don’t’ trust the connectivity data.

But there’s good news as well : B6/7 weather this w/e + big south waves > sails from 5.2 to 6.0 > carbon this, carbon that > adios amigos.

The problem i fear the most is that of surface areas that really don’t direct us to a “cavity bottom”. Look at this picture for example. I drew (eyeballing) a FitLine through the top faces (blue line), and this is because what you see is no true “cavity”, you see only a continous slope to one side (red line).

And if such areas of the surface are included in the final bottom-of-valley FitLine, it will tend to attract that end of the final Line to the right side (in this picture).

This only means I will have to try to detect such “sloping areas” as well, and based on that shorten the intersection Plane (at both ends actually) so that that part of the mesh-plane intersection won’t affect the final Line.

On this particular Mesh the “slope” is due to the angle of the BoundingBox though, so it’s not a problem. But in one of the meshes I uploaded this problem is screamingly evident.

// Rolf

Wonder if a semi-auto approach could cut the mustard here (as Tom the Wise German would strongly suggest). I mean what if we eliminate (after the sorting [as in V1C] and the proper pre-elimination [as in V1D]) the stripes manually? (by index and/or interactively).

I mean that given a good dose of the proper Karma we could spend a life time by trying to predict messy Mesh Topological situations … only to discover that there’s another one in the next case.

For instance the rightmost small stripe could be due to another layer (no no) OR due to a vertical ripple in the same layer (yes). Of course smart connectivity checks (or ancestor based ones) could tell the truth … but what if connectivity data are bananas? (or half bananas due to a banana mesh).

And guess what? a proper clipping plane thingy could be far far far more useful in real-life (against freaky meshes) than 66 lines of super smart code (super stupid in fact).

In this case, no. I need 100% automation.

But what I CAN do is split the overall process into separate GH definitions, and at the end of each such definition (process-step) dump a Viewport Capture to disk, so that any insane results can be viewed and spotted occulary in hindsight, then set apart, and handled manually, and restart the process, for that mesh, from that process-step.

Not 100% sure, but I think I can use what has been achieved so far, including the ConvexHull strategy, and then do further analysis on that result, for example as mentioned earlier, combined with a cross-over validation to limit the plane’s “length” (along the valley) so as to avoid the sideways-slopes-areas at each end of the bottom-path, and off you go.

That would at least be a good start, and then leave it to manually fix those meshes which goes bananas in the automation.

Only one question - did you arrive at any recursive altgorithm (moving T and rotating the plane) that finds the “lowest” path based on the ConvexHull shown in the last picture?

If so I would definitely regard it as a useful start. I can always add more bells and whistles to that strategy later as I try more meshes.

I can also develop better strategies for how to cut out the mesh before applying the algorithm (these are only parts of bigger meshes). This “captured part meshes” is part of the overall strategy I use. It speeds things up, and sometimes you can “cut away” such problematic features which makes your algorithms go bananas, aso, aso.

// Rolf

That’s a HarleyDavidson (i.e. slower than a stationary tortoise) way. I’ll add a proper clipping capability (in sync with the clipping object/plane) in order to see what you are after in real-time. With this on hand maybe you’ll rethink the semi-auto Plan B (all in all way faster than splitting defs and doing this and doing that).

Always remember that the so called Parametric thingy is just another thingy. All that without counting the New Big Thingy (AI) that would change everything until the next big thingy arrives (or Armageddon) and so on.

Moral: The more things change the more stay the same.

I have an expert in AI/Machine Learning in the family (link). He would tell me that that before I have aggregated the capability to recognize the features I am after here, I would still have to feed the learning algorithm with perhaps ten times the number of meshes which I plan to apply this logic on. So, well yes, when applicable, AI/ML will be helpful. But in this case it will be too far fetched.

BTW, I tried using a component I made for filtering Outliers based on statitsics. In this case I feed the component with the face centers (could use plain Z values instead). The first picture shows what FitLine gives with standard IQR factor (1.5) and how the outliers are excluded at IQR 0.40 (picture far below.

Yellow dots indicate points fed into the FitLine component (that is, not excluded buy the StatsOutlier component:

Here the filter is choked down to IQR factor = 0.40

For what it’s worth. If you use VS (it’s compiled) and you want a copy, send me a PM and I send you the .cs file.

AI/ML is the next thing for sure., But not the current thing.

// Rolf

When AI arrives to the masses start digging a BIG rabbit hole (or change planet). If you combine that thing with Nanotech and Genetics change galaxy. The human history is full of things that arrived with applause … then … other things happened (In fact always other things happen).

Anyway a clipping thingy is rather a must for the type of nightmare that you are after. Shown at sync with the section plane (but that’s just an option out of many).

Look like wild fires sweeping over California.

I’m not sure of how to benefit from the ClippingPlane. Does it yield some useful info which wasn’t provided by the Mesh/Plane intersection?

// Rolf

Well before walking the walk you should first inspect the walk. It’s impossible to mastermind a Jack for all trades before having the joy to see the rabbit hole itself (and make rules that are subject to change until the next rabbit hole).

If I was you: I would fit the section Lines into the smallest rectangle (there’s lot’s of algos doing that - but you can do it … er … hmm… manually as well) and then I would sort the stripes accordingly using the proper rectangle site as the refAxis (V1C sorts them “using” the orientation vector: that’s not good enough) and pick the top most manually. See for instance this combo that is “inclined” towards box x … meaning that the orientation vector (0,0,1) is not the proper reference for the sort (green stripes).

The big anathema of our Times is automation (and what comes after that).

BTW: For the rightmost portion of the big section … what would be the rule of acceptance? Take what part exactly?

Any rules of coruse depends on what strategy/algoritm is being used.

Early on I mentioned that I was considering a collision strategy. Which means something like dropping a pen (horizontally) and let it find a resting position in the “valley”. That would illustrate pretty well the end goal, a straight line at the bottom-most path of the cavity (however, even small peaks or irregularities could push the pen, or cylinder, to the side, and therefore it can be better to include points to a certain depth around such a pen. Alternatively just follow the surface faces which has been the main idea in this thread so far)

But if calculating this "bottom-most path from the Z values of vertices or face center (or whatever intersecting that probing plane), and if traversing the red faces to both sides from the topmost face in the picture, then I would cook up a set of rules to exclude irrelevant mesh faces by,

• excluding any line segment (mesh intersection polyline segment) located lower than, say, 20º or max 25º below the direction (slope inclination) of the last visited faces (starting from one face, adding up to say 10 of the last visited faces and calculate the a current slope orientation based on those face centers).

• Any “last face” (as a variable in pseudo code) must not advance until it finds a face above the mentioned constraint angle.

• But when it advances, it connects a “bridge segment” to that next polyline segment.

• Continue loop until no further line segments are found.

Such a loop would probably shorten the bottom-most path at both ends of the path, due to the steeper slopes at the ends. Which is fine, because they tend to be part if “sideways” slopes anyway. By exloduing them, the major part of the path will remain in the middle/bottom-most grove, less affected by the side-ways slopes at the ends (which drags down the Z values, although not due to being in the middle of the valley, only by being part of a slope irrelevant to the mid-valley path we are after.

These are the same rules and same line of thought I have repeated in the thread. But I know from my own experience that the significance of these rules (how they affect the final line) can easily be overlooked until actually displaying a FitLine on screen based on the result of any experimental code. Then it is become obvious to the naked eye how, and why, the FitLine tends to drift off to the sides if not carefully avoiding the end slopes.

Bridging gaps between segments (at holes in the mesh) is equally important if traversing the mesh like this, or alternatively, skip sections with holes altogether (see angle rule above) and divide the Z totals with the total length of the fewer accepted top-segments (otherwise the gaps/holes would tend to give a certain path a too low Z total, or whatshallmecallit).

There are people writing PhD thesises about problems like this (like ConvexHull, ConcaveHull, bridging gaps, patching holes, aso).

Any problem can be solved, and I have my own slogan about the fact, which goes like this: “There’s always a solution”. Which I think is true. It’s only a matter about how much time and effort needs to be spent. But as for me I’m a newbie in geometry, so it takes some time before I have become familiar with the best algorithms for the most common problems.

// Rolf

Indeed … but the simplest and fastest is simply combining you and the stupid (for the moment) part: that computer. See what the manual mode (sort and take) has to say to all the PhD fellas who try hard NOT to attempt a double forward (that’s windsurf stuff - don’t try it at home).

1 Like

I’m not sure I really follow what you do there, but it looks good!

I struggle with the question about whether the most stupid part is my computer or me.

It must be something in the terminlogy which made me slide off the wagon at some point. Can you explain in more detail what you do in the pictures?

// Rolf

I’m moments before going out there (to meet the big waves [and that @%@\$*&& forward]). When back I’ll post the V1D that does all that: in theory you can automate the process … but chances are that the exact moment that the C# is finished … another freaky mesh would render the thing obsolete (rule of real-life N666: there’s no such thing as the Jack for all trades ).

1 Like