# Straight Skeleton "Implementation"

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

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

3 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

There is a modified implementation of Felkel & Obdrzalek’s algorithm ported from Java to C# here: https://github.com/reinterpretcat/csharp-libs/tree/master/straight_skeleton. One thing to note is that a robust implementation of Straight Skeleton calculation is quite a complicated algorithm and has a lot of edge cases (as Tom Kelley (“twak”) demonstrates)

I’ve used the C# code in Rhino/GH by rebuilding Rhino Polylines into the library’s own geometry primitives – see code below. Because this algo isn’t as robust as CGAL/twak, moving it to the origin and scaling it up can sometimes give better results (trying to avoid accumulating roundoff errors…). Also – if the shape you are skeletonizing is very orthogonal (ie lots of only right-angled), there is a chance this algo will fail because it cannot handle so many degenerate cases (even though it does introduce multiple split/edge event handling…)
(see http://www.twak.co.uk/2009/05/engineering-weighted-straight-skeleton.html)
Code:

``````    public Polyline[] MakeStraightSkeleton(Brep brep)
{
// This must be performed near the origin and scaled up...

// Move to origin:
var duplicate = brep.DuplicateBrep();
var vertices = brep.DuplicateVertices();
var vector = new Vector3d(new BoundingBox(vertices).Center);

var translateFromOrigin = Transform.Translation(vector).Clone();
vector.Reverse();

var translateToOrigin = Transform.Translation(vector).Clone();
duplicate.Transform(translateToOrigin);

var scaleFactor = 1e4;
var scaleUp = Transform.Scale(Plane.WorldXY.Origin, scaleFactor);
var scaleDown = Transform.Scale(Plane.WorldXY.Origin, 1 / scaleFactor);
duplicate.Transform(scaleUp);

//Perform StraighSkeleton:
var innerLoops = new List<Polyline>();
Polyline boundary = null;
foreach (BrepLoop loop in duplicate.Loops)
{
Polyline loopPolyline;
var loopCurve = loop.To3dCurve().TryGetPolyline(out loopPolyline);
if (loop.LoopType == BrepLoopType.Outer)
{
boundary = loopPolyline;
}

else
{
}
}

var sskOuterLoop = new List<SskVector2d>();
foreach (Point3d pt in boundary)
{
var sskVect = new SskVector2d(pt.X, pt.Y);
}
sskOuterLoop.RemoveAt(sskOuterLoop.Count - 1);

var sskInnerLoops = new List<List<SskVector2d>>();
foreach (Polyline innerLoop in innerLoops)
{
var sskInnerLoop = new List<SskVector2d>();
foreach (Point3d pt in innerLoop)
{
var sskVect = new SskVector2d(pt.X, pt.Y);
}
sskInnerLoop.RemoveAt(sskInnerLoop.Count - 1);
}

var sk = SkeletonBuilder.Build(sskOuterLoop, sskInnerLoops);

var lineList = new List<Line>();
var dupPtList = new List<Point3d>();

var faces = new List<Polyline>();

foreach (EdgeResult edge in sk.Edges)
{
List<SskVector2d> points = edge.Polygon;
var facePtList = new List<Point3d>();

foreach (SskVector2d sskVector2d in points)
{
var rhinoPt = new Point3d(sskVector2d.X, sskVector2d.Y, 0);

// Check if rhinoPt == input Polygon pt:
int dupCount = 0;
for (int i = 0; i < boundary.Count; i++)
{
if (rhinoPt.X == boundary[i].X && rhinoPt.Y == boundary[i].Y && rhinoPt.Z == boundary[i].Z)
{
dupCount = dupCount + 1;
}
if (dupCount > 1)
{
}
}

}
var startPt = facePtList[0];
Polyline face = new Polyline(facePtList);

// Move back:
face.Transform(scaleDown);
face.Transform(translateFromOrigin);
}

return faces.ToArray();

}``````
4 Likes

Hi @daniel.fink,
Your move to origin and scaling solution solved some of the issues I had with ssk library! Brilliant!! Thank you!!!

However, in certain cases, one or two of the created faces are way too long. Do you have any other suggestion on how to tackle this issues?

Interestingly if the polyline is moved around the origin, at certain point everything works fine. But it is difficult for me to find the exact location of where it should be put.
ssk_example.3dm (209.0 KB)

Found this topic related to my floorplan perimeter zoning issue and took a few days crafting the code. I got some prototypes but, still a long way to go I guess. More puzzles are like: how to solve inner loops? what if edge-collapse and offset-split happen at the same time? …
Actually I just clip the inner skeletons with the polygon offsets to solve my perimeter zoning issue, and use the maximum distance (skeleton joints to original edges) as the upper limit. For that I don’t know how to weave those 2 thingies into iterations together, this can be a waste of computing resources. It seems offset thingy will lead to straight skeleton naturally. Hope someone could give me a hint about this.
Very useful tips @PeterFotiadis! Really appreciate and look forward to more details about how you solve skeleton puzzle with recursion (do edge collapse if not encounter with poly split when test the vertice back and forward?). I follow these 2 lines to do my poly offset puzzle:

1. During the shrinking procedure, check self-intersection of the offsets. The polygon incident to the overlapping area has reversed vertice sequence compared to the polygon before collision. These poly fractions need to be erased.
2. Any polygon fraction generated from self-intersection is also subject to antiparallel checking, throught which the child polygon containing antiparallel edge will be deleted.

Long way to go and I cannot bear my dumb code (with GHPython). Maybe I’ll share some when most of the nasty cases are covered. What is ccx thingy by the way?

Ccx is an “acronym” for Intersection events (LineLine or some other). That said the C# that does that is strictly internal (CNC routing blah, blah) … but I could check your stuff and provide (if required) some tips/hints: Oops: I can’t do that since you are in the P bandwagon (and there’s no auto translation possible to the right thing).

BTW: Since you are after that puzzle go for the general case: take into account holes as well. By doing so you should classify inner and outer Loops as clockwise/anti clockwise (or the inverse) - kinda trying to offest correctly Polylines/PolyCurves etc etc.

@LiquidSo Kindly, can you clarify how you got this result in the GIF. I think that your clarification will solve this problem.
Looking forward to hear from you.