Straight Skeleton "Implementation"


(Daniel Fink) #21

There is a modified implementation of Felkel & Obdrzalek’s algorithm ported from Java to C# here: 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…)

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

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

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

        //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;


        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:

        return faces.ToArray();