Straight Skeleton "Implementation"

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
            {
                innerLoops.Add(loopPolyline);
            }
        }

        var sskOuterLoop = new List<SskVector2d>();
        foreach (Point3d pt in boundary)
        {
            var sskVect = new SskVector2d(pt.X, pt.Y);
            sskOuterLoop.Add(sskVect);
        }
        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.Add(sskVect);
            }
            sskInnerLoop.RemoveAt(sskInnerLoop.Count - 1);
            sskInnerLoops.Add(sskInnerLoop);
        }

        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)
                    {
                        dupPtList.Add(rhinoPt);
                    }
                }

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


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

        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.




Can I get this project from you ,I am really trapped by this problem recently . And as I am totally new in C# , i am pretty confused about how it works , a reference will help me a lot .

Er … hmm … that’s kinda asking how to go to Moon (in just 666 easy steps). After spending several years (5 - 10++) walking the walk ask me again.

On the other hand some users discover the C# available as component and MAY think that this is the holly grail: just put some (?) lines there and … by miracle … open Sesame … blah, blah.

Other than that all my things related with that matter are strictly internal.

But Laurent D likes that sort of challenge: he provides - from time to time - various C# solutions (I’m sure that all work 100% OK). Do some search for posts where he’s involved (one has a funny name: old town roofs).

Thanks for your wise guidance and reply , as well as Laurent D , it really helps a lot !!!