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();

    }
2 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)