Straight Skeleton: Insets, Isoline Slices and Roof Models form Polygons

Inspired by the old “Inset Straight Skeleton” add-on I decided to implement my take on the problem.

I left the intermediate steps as separate operators as they might be useful for beveling, roofs of buildings (architecture), map isolines of mountains, etc.

Roof model comparison:


Inset comparison:

You will probably find some polygons which cause glitches, so please post them here and I can try to fix the code accordingly.

Download from GitHub:

20 Likes

Nice! I’ve dedicated a short BlenderNation article to it. It will be published soon.

Here’s the BlenderNation article:

1 Like

Thanks! :+1:

1 Like

Hi @lichtso,

Which algorithm is used to calculate the straight skeleton?

Does the addon support polygons with holes?

It uses the one of Stefan Huber and Martin Held.
Theoretically, the algorithm can handle holes and open polygons / line-strips as well,
but I haven’t implemented these features yet.

2 Likes

I haven’t seen any implementation of that algorithm in Python. I’d suggest to release it as a separate library (independent of Blender) and then use the library in the addon for Blender.

Nice job. I am the author of the old straight skeleton addon. It has some bugs, as you have discovered. But it does (usually) work with polygons with holes in them. The “testing” addon for AI / PDF / SVG uses the same algorithm to do an optional bevel.

1 Like

Other than the original implementation by the authors, which is closed source, I haven’t seen any other implementation. So I had to implement it from the paper and it is not complete. It also lacks the divide and conquer optimizations at the end which would make it fast for bigger polygons.

But yes, extracting it to its own library is a good idea.

2 Likes

If you want, I can send you the polygons so you can have a look why they misbehave.
And, what is this “testing” add-on you are talking about?

1 Like

At the moment I am too busy on other stuff to look at this. I remember trying to convert my algorithm into C, as a possible basis for a better inset in Blender, and ran into similar bugs, and they were hard to figure out. Maybe one day I’ll get back to this, and perhaps collaborate with you and use your code as basis for a good inset in Blender. It isn’t easy, however, because the current Blender inset works on non-planar regions.

By “testing”, I mean that it is in the addons_contrib repository, so it isn’t distributed with official releases of blender, though I think it is distributed with nightly builds - where it is available in the Addons Preferences by enabling the “Testing” tab.

1 Like

Great Addon… Only problem is that it does not work at all. I tried it with several OSM Models… Your addon only works with Quads.

Checked again: It seems that only the “straight skeleton” is broken. For “inset Straight Skeleton” it works much better.

1 Like

Would you mind sharing the files or at least the polygons, so I can look into it ?

Also does it produce wrong results or none at all, is there any error message?

1 Like

Hi,
just create any + shaped form. So like a quad with each edge extruded once.
Addon from Howardt seems to have the same problem. When the + shape is not so straight its working. Like randomizing all vertizes before.

ERROR: calculateVerticesFromIntersections() could not find the next current_line
ERROR: calculateVerticesFromIntersections() could not find the next current_line
ERROR: calculateVerticesFromIntersections() could not find the next current_line

It gets it in parts right. Some faces seems correct. Then i think there is some wrong face. and then some faces are missing.

1 Like

This implementation will succeed with + shapes, but no support for holes in polygons.

cross_skeleton

hey, that sounds cool! How did you get it to work in Blender? Could you send me the stuff?
As soon as it includes the necessary euclid3 i get the error:

error: option --python not recognized
The terminal process terminated with exit code: 1

Here is a compatible euclid,
you still must handle the polygon / line generation from output data structure.

euclid.py.zip (11.9 KB)

Not even a T-shape is working, when it is symmetrical :slight_smile: Im sure thats why you show that unsymmetrical T-shape in your screenshot? :wink:

Also its not allowed to have extra vertices, even on a quad, that don’t change any direction. So a quad with one side consisting of 2 straight edges will fail as well.

Are you planning to finish the Addon? Or is it as it is?

1 Like

According to his Github issues he has issues with symmetrical polygons in general as well :frowning:

1 Like

X shape is a true symmetrical x, T shape also symmetrical - both based on a box with sides extruded.

t_shape

This “symmetrical” issue is fixed.

The exact same implementation is part of archipack 2.x “roof draft” entity.

1 Like