# Geodesic line / Shortest path on brep

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

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.

1 Like

@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]).

1 Like

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.

If you are in the broad real-life AEC BIM market sector that’s the correct (and the only) walk to walk.

In the mean time here’s a challenge (usefull in real-life iin numerous occasions) for you: given a prox graph on a random pts collection in space do first the VV connectivity (that’s rather easy). But … the big thing is: can you detect the islands (if exist) using solely that VV Tree? Get a pencil and a piece of paper and mastermind some sort of strategy then post here your C# efforts.

BTW: For tensile membranes in most real-life cases do the abstract fabric layout in 3 steps: (1) define a flat Mesh (prior sending it to K2 subdivide accordingly) (2) define masts, rings (if any), fixed cables, variable cables [yellow(from)/red(to) lines in the pics below], cats and dogs (3) write a C# for the K2 relaxation having ALWAYS in mind to separate spring forces between clothed and naked (perimetric) edges (see the anchor plates posted above to see why).

BTW: For the real McCoy (anchor plates, tensioners and the likes) forget completely GH/R.

I found my script:
Shortest_Path.gh (42.7 KB)

It adapts the midpoint method that is described here https://cs. stanford .edu/people/ jbaek /18.821.paper2.pdf

It is by far not complete and not very fast. It worked for my application case. However, it will most probably fail with your example as your stripes are very narrow and there has to be a point in every face the line is crossing with the current code. But it might be of help for someone.

4 Likes

That’s neat Peter. Both theoretical and real world illustrations

Hello Anna,
I just saw your post. And i have to say WOW. What a precious piece of code!!! Thanks so much for sharing it !!! Ist very fast, i think (1.8s @ optimum with your example). I found it very interesting that a lower number of points increases the accuracy. In your example, the sweet spot appears to be 29. The optimum number of iterations seems to be 1015, after which it becomes less precise again. I will let you know what kind of experiences I will have with it in the future.
Shortest_Path 29.gh (48.9 KB)