Thursday, June 17, 2010

weighted straight skeleton source release


The straight skeleton shrinks in the boundary of a polygon, whilst tracing out the corners to create a roof-like structure. Thus is quite useful for building things like roofs or offset surfaces. I never did find an impelmentation that wasn't CGAL's, so here's a floating point implementation.

rect26802

The weighted skeleton allows the edges to move at different speeds. You could even assign negative weights to edges.



Instructions: (java webstart, binary code, run at your own risk).
  • Left drag the little orange squares at the corners of the cross
  • Right drag to move the view
  • To change the weights drag the big orange circles
  • Control-click to add corners
  • Shift-click to remove corners
  • There are known bugs (for example the polygons in the UI overlap, there will be cases where it doesn't tessellate).
  • Use alt-while-dragging to snap to grid
Google code project (java) is here.

Here's an example of how to skeleton a simple triangle. Points are defined counter clockwise. If you only want the 2d projection, discard the final (z) co-ordinate of the output-faces.

        Corner
        c1 = new Corner ( 0,0),
        c2 = new Corner (100,-100 ),
        c3 = new Corner (100,0 );
      
       Machine directionMachine = new Machine ();
      
       loop1.append(new Edge ( c1,c2 ) );
       loop1.append(new Edge ( c2, c3 ) );
       loop1.append(new Edge ( c3, c1 ) );
      
       for (Edge e : loop1)
        e.machine = directionMachine;
      
      
       Skeleton skel = new Skeleton (out, true);
       skel.skeleton();
      
       for ( Face face : skel.output.faces.values() )
       {
           System.out.println("face:");
           for (Loop  lp3 : face.points)
            for (Point3d pt : lp3)
             System.out.println(pt);
       }

12 comments:

  1. "public Skeleton( LoopL input, boolean javaGenericsAreABigPileOfShite );"

    Cool... and right!!! :D

    ReplyDelete
  2. Haha, yes it's true! Academic programming involves many late nights and much swearing - sometimes (often) this makes it into the code...

    ReplyDelete
  3. also, the system works better if you set the parameter to true ;)

    new Skeleton ( loopL, true );

    ReplyDelete
  4. Hi again! Could you help me with something... Imagine the input polygon is a building and the input edges are the walls. Then how can I get the input Edge(s) of each output face? I can retrieve only the SharedEdges, but they are just output objects with no relation to the originator Edges. Look at this example: http://store.picbg.net/pubpic/44/C5/e2be843f63eb44c5.png

    ReplyDelete
  5. Looks like I've found the solution - iteration over output.faces.definingCorners and getting nextL of each corner. This works for me by now. But it's strange in one situation - when you have more than 1 adjacent and colinear edges. Then it returns multiple faces as many as those colinear edges. I'll just filter the duplicated faces. What dou you think?

    P.S. Excellent algorithm and implementation! I like your way of structuring the data. It's strong like a CAD library.
    I don't have deep understanding of your algorithm, so could you explain me the notion of the Machine class.

    Regards!

    ReplyDelete
  6. Hi Севар,

    Each shared edge has a definingEdge defined within it (not sure if the field is public tho!). This is the same as the input (if Skeleton hasn't cloned the edge at the start).

    A Machine is a strange concept. The idea is allow a set of edges to behave in the same way (have the same gradient, or change gradients at a particular height). This concept is really for one one of my modelling projects that extend Machine's functionality.

    One day soon I hope to publish that project!

    Cheers, Tom

    ReplyDelete
  7. Anonymous09:02

    The project looks great, the demo is cool too!

    Could you give a very small example about how to use your library? For example, if I have a 2d polygon as a list of points, and want to get it's straight skeleton?

    Also, does your library handle polygons with holes?

    P.S. Again, very good work!

    ReplyDelete
  8. Here's some code for an unweighted skeleton. Points are defined counter-clockwise.

    Corner
    c1 = new Corner ( 0,0),
    c2 = new Corner (100,-100 ),
    c3 = new Corner (100,0 );

    Machine directionMachine = new Machine ();

    loop1.append(new Edge ( c1,c2 ) );
    loop1.append(new Edge ( c2, c3 ) );
    loop1.append(new Edge ( c3, c1 ) );

    for (Edge e : loop1)
    e.machine = directionMachine;


    Skeleton skel = new Skeleton (out, true);
    skel.skeleton();

    for ( Face face : skel.output.faces.values() )
    {
    System.out.println("face:");
    for (Loop lp3 : face.points)
    for (Point3d pt : lp3)
    System.out.println(pt);
    }

    ReplyDelete
  9. Hi again, Tom! I've done a lot of experiments with your algorithms but recently I faced a "wall" that I don't know how to work around. I can generate the roof and set the eave overhang, but is it possible to set different eave heights for different edges somehow? I need a way to deal just with the most simple cases like this: http://imageshack.us/photo/my-images/716/eaveheights.png/

    P.s. What happened to the project, is it still in progress?

    Good luck!

    ReplyDelete
  10. Duude, nice app!
    Can you postr the code for your 'snap to grid' bit while holding Ctrl?

    Thanks

    ReplyDelete
  11. Nevermind, I've just got the code to work. I simply ignored the warnings by Eclipse. Amazing!

    Now, I'm on my way to get the demo code above for non-ui usage working out.

    Regards,

    JLeandro

    ReplyDelete
  12. Good job! I imported your code as an Eclipse project and run the skeleton.debug.Main(). Simply amazing!
    I also had your example above working out, with the following output:
    face:
    (70.71067811865474, -29.289321881345245, 29.28932188134525)
    (0.0, 0.0, 0.0)
    (100.0, -100.0, 0.0)
    face:
    (70.71067811865474, -29.289321881345245, 29.28932188134525)
    (100.0, -100.0, 0.0)
    (100.0, 0.0, 0.0)
    face:
    (70.71067811865474, -29.289321881345245, 29.28932188134525)
    (100.0, 0.0, 0.0)
    (0.0, 0.0, 0.0)

    Now, I would like to get only the straight skeleton edges (inner ones) programmatically (no faces, neither the polygon contour). For example, I would like the output as a list of pairs of linked points, instead of the faces, as in your example above.

    However I'm having a hard time to figure out from your code how to get this output as described. Would you kindly give me a clue, please.

    Regards,

    JLeandro

    ReplyDelete