Straight Skeleton "Implementation"

Hi, lately I been searching for a way of generate the Straight Skeleton of a polygon, but I haven’t been able to find any examples on how to implemented, for what I been able to find it appears to be fairly difficult, because of the amount of conditions and special cases. I know there is a C# Wrapper for CGAL StraightSkeleton, but Installing CGAL and all its dependencies, just for it, seems a bit crazy.

I was able to use pySkeIeton, but is slow and fails from time to time, I was wondering if someone has any advice or examples on how to implemented in C#. Thanks!!

CGAL = https://github.com/martindevans/CGAL_StraightSkeleton_Wrapper
pySkeleton = http://vision.mas.ecp.fr/Personnel/teboul/pySkeleton.php

What is a straight skeleton of a polygon?

have you seen this:

1 Like

Yes, Gijs, that implementation works only with convex polygons with no holes, I believe someone had link it in the old grasshopper forum, and it tended to fail by a continuos deformation of the base polygon.

I believe that definition is somewhere in here

http://www.grasshopper3d.com/forum/topics/connect-offset-pattern-points-inside-polyline

It is not a complete answer but could help as it is c#

1 Like

To my knowledge this the most comprehensive attempt to explain the algorithm out there

https://www.sthu.org/research/publications/files/phdthesis.pdf

Well Antonio if you want to do that with C# (BTW 1 to 10 what is your experience ?) … your first task is to master inwards (or outwards [holes]) the polyline offset puzzle. Hint: for a given Brep Face make inner Loops (holes) clockwise and outer Loops counterclockwise (Or the inverse). Finally you get stuff like this:

Then using some Methods from above it’s a matter of recursion (from a given node go back and forward etc etc). I can give you some hints on that matter after you have fixed the poly offset challenge:

1 Like

What would be an approach for solid meshes?

Why to use meshes? (you mean joining the BrepFace [base] with the inner planar BrepFaces [loops/cirquits/whatever] - if some Z is provided)

Or you mean some “variant” of this?

no, about medial axis, of 3d solids.
I was searching for this issue. But it seems there is no simple example.
It did usually include implicit contraction of mesh vertices, or fitting circles to pointclouds which is slow.
And it is for me complex regarding geometry processing.

I do understand that there is no such thing as medial axis for 3d objects, it must go through some sort of abstraction in order to have polyline representation I was wondering if you know even a starting point for this:

I also read that it is possible to approach this problem through voxels by gradually removing boundary voxels:

1 Like

See this:

https://3d.bk.tudelft.nl/projects/3dsm/

You surely know that but as it is the closest to 3d medial axis
http://www.grasshopper3d.com/m/blogpost?id=2985220%3ABlogPost%3A1018778

@PeterFotiadis I’m really curious how you get the polylines to offset into multiple curves once they become smaller. I’ve never found Offset to be very reliable and sensitive to where you pick the offsetpoint. I’ve tried the different Offset methods (both with and without a directional point) but offsetting always stops when it would run into multiple offsets.

1 Like

Yep, maybe a 6 being 10 the dog, but recursion makes me want to die in a repeat it fashion. Yes clipper offset solves with collapse events, but I’m not sure if you can access them. Thanks

  1. Control the orientation of your polys (clock or counter clock).
  2. Work solely with poly nodes (forget the offset Method) and compute the candidate offset node (the end of the yellow line in the images attached). This may (or may NOT) be a valid offset node.
  3. For each candidate node go back and forward in order to find valid offset ccx points: there’s several checks required but the main is if the resulting segment pairs (polyline segment VS candidate offset polyline segment) are antiparallel (red tubes for clarity in the images attached). For instance and for, say, node 0 go back until a [prev, prev-1] node pair yield a non antiparallel combo (sample all nodes from 0 to prev as not valid). Do the same forward and associate node 0 with the ccx event between the valid offset segments (also sample all nodes from 0 to next as not valid).

Unfortunatelly the C# that does this is internal (also the straight skeleton one) but I could post an indicative demo that gives you some hints for solving the puzzle.

1 Like

@PeterFotiadis: interesting challenge, I’m not a programmer so please bear with me… This is what I came up with so far. While making the intersection points it seemed this is already starting to look like a skeleton as well. Still long way to go I guess?
vector_based_offset_01.gh (12.8 KB)

Well … for a start let’s forget inner loops (holes). Other than that indeed the path is long (and hilly).

2 Likes

Level 6 is OK for that thing (skeleton and offset and this and that).

Let’s deal with the polyline offset thingy first (far more important than the straight skeleton thingy).

  1. Orient the poly and calculate the candidate offset nodes (the ones with ?). D is the offset distance (obviously you should use basic trigo etc etc).
  2. For a given node, say, 0 go backwards in steps of 1: Is the pair 0-N, 0?-N? antiparallel? Yes they are. Go back. Is the pair N-N-1, N?-N-1? antiparallel? No they are not, So Line N?-N-1? is the right previous Line for the ccx thingy.
  3. For the same node go forward: Is the pair 0-1, 0?-1? antiparallel? No they are not, So Line 0?-1? is the right next Line for the ccx thingy.
  4. So for the node 0 the center of the red circle is the offset Node with regard the node 0.

Next lesson: Either do some stuff more OR get a poly from above as it is (propably self intersecting) and make the right islands (maybe invide some inner polys [holes] to the party: see below).

For the other thingy and speaking about dogs:

1 Like