Geodesic line / Shortest path on brep

Hey,

is there a way to compute a geodesic line on a brep with multiple faces?

Thanks!

Hi Anna, here is a naive approach simply pulling a line onto the brep closest points. It’s not a geodesic, but could this work for you?

There are several plugins which provide components to create geodesics on meshes. Have a look on food4rhino

naive geodesic.gh (587.3 KB)

Thanks for the quick reply! But actually I wanted to avoid the meshing step.

Hallo Anna,
i have the same question. With Kiwi3D i have a Brep as a result of the formfinding and i am facing the same problem, did you find a suitable solution?
Thanks David

For any Brep (Solid or not) I would recommend the classic Dijkstra routing (option: from/to VS the from all/to).

Say fror a test Blob (done via TSplines) like this:

Get the Mesh representation (via MeshMachine or using some other app) and then do a Dijkstra (i.e. treat the Mesh as Graph, get the VV connectivity [adj Matrix] and then find the shortest path using vertices indices [from/to]). If the Mesh is refined enough then the route could be “almost” a Curve (or do a Curve via the path nodes or refine locally the Mesh and re-run Dijkstra).

Hey,
yes, I wrote a small piece of code. Unfortunately, I apparently deleted the respective userobject -.- Maybe I can recover it but the chances are small. I’ll try.
But in short (if I remember correctly): I provided an initial guess for the curve over the brep, divided the curve into points, computed an update (either by projecting the angle into the local plane of the surface and creating a direction or by drawing a new line through the midpoints of the curve segments) projected the update to the surface. All this iteratively repeated until the update was small.
Maybe this helps…

1 Like

Hallo Peter, that sounds like a very good approach, but like Anna, I want to prevent the Brep from being broken down into a mesh. Over the years I have come across your posts repeatedly and have been impressed with your grasshopper & programming skills :wink:

Hallo Anna, thanks for sharing your approach. today i won’t have enough time to work this out. In the case of my current project, I decided to do a simple projection in the Z direction. The sail is quite flat and in that case that is sufficient.!


Well … have in mind that “projecting” some start-up indicative guide route works only if the Topology is suitable and by no means is the Jack for all trades solution.

The general (and rather fast) take on that would be a D routing on a rough Mesh and then a recursive refining on the resulting “stripe” (i.e. a collection of neighbor to the path mesh faces > some subdivision > edges [as Graph] > adj Matrix > D re-run > repeat if required). For a subdivision of 2-4 and after 3-5 loops the path would look “like” a Curve anyway.

Hallo Peter, where can i find your Dijkstra routing?

no, it isn’t. It is also more like putting a cable onto a surface and stretching it.
My main application were membrane structures. So I knew where the cutting line should approximately be. And actually it was not necessary to find the shortest path but the respective geodesic line. Dijkstra will get you the shortest path between two points which is not necessarily the same.

The resulting curve has to be able to split the NURBS surface. So in the end, I will need this projection, even if I find it with a mesh. I think I projected the points of my segmented curve by ClosestPointOnBrep and did a geodesic line inbetween those points. The problem is then only the crossing of the edges. But these points can also be found. There might be small kinks between the subcurves.

But tensile membranes are approximated/solved - more or less - via Meshes (because of the Physics Engine on duty: like K2 and others). So in a way you do have (or had) a Mesh around. And indeed the DRP is not necessarily a geodesic path but if the Mesh is refined enough (via some recursive approach related with the candidate “stripe” per loop) the real-life difference is rather very hard to detect.

The C# shown is strictly internal to the practice. Is part of a 4 C# combo that deals with any Graph (including the paramount Island detection using a first pass VV connectivity). Then the adj Matrix (per Island) is calculated and then is time for Dijkstra (DRP) to cut the mustard.

See an abstract Demo (Rnd Prox Graph + Islands (per Color) + Dijkstra [ option: From/To instead of From All/To]):

There’s various publications on DRP around (GitHub/CodeProject etc) … but most are very slow for real-life usage. I think that there’s a GH add-on available for shortest path but I can’t recall the name and/or the source.

That said what is your game? C# or P?

Actually, I don’t need meshes for the form finding. I am using Kiwi3d which uses NURBS for the form finding…
And I meant something like this: https://upload.wikimedia.org/wikipedia/commons/thumb/9/91/2019-07-Helix.jpg/330px-2019-07-Helix.jpg This is not the shortest path but a geodesic line… But of course, this i also a special case.

@DavidduBellier : Your images did not load yesterday. In your case the lines are not crossing inner edges do they? Because there some commands in Rhino and Grasshopper in order to find geodesics on single surfaces. _ShortPath and Geodesic.

Hmm … you said membranes (my favorite domain in AEC) and I instantly assumed classic tensile membranes and classic relaxation Methods. That said I don’t care about pieces/manufacturing since this is Birdair/Taiyo Kogyo’s domain: I’m after the approximate fabric layout (via Meshes and Physics Engines the likes of K2) while I cover completely [1:1 details and the likes] the plate/masts/cables/tensioners design part [CATIA, SiemensNX etc]).

If you are looking for geodesics starting from an initial point with an initial direction, I can help. (but it seems like your geodesics are the curves determined by two end points)

Hey Anna,
yes the lines crossing inner edges, here you ca take a look…Membrane Example.3dm (10.9 MB) Soon in the Future i have to find a good solution. The Next project is very much 3-Dimensional.

Now i also understand why a geodesic not always has to be the shortest path. (spiralling around a cylinder)

Hallo Peter,

thanks very intresting. i’m a visual guy, love to use grashopper and unfortunately I’m still a beginner in programming. if i use c #, i would like to be able to do more, think it would save a lot of space and time…

You could also mesh the Brep and implement the approach I posted here (i.e. relax a polyline on the mesh):

Edit: Looking at your geometry, you can also use the Surface.ShortPath method on the underlying surfaces. This is what I implemented back here:

I can post a GHPython example when I’m on my laptop again.

Edit 2: I didn’t realise Surface.ShortPath method has been implemented as a standard Grasshopper component, so no scripting needed:


210409_GeodesicsOnSurface_00.gh (13.2 KB)

For context, I was recently attempting to trace the underlying algorithm/method it uses over here.