Enhancement: prevent wave propagation for the given edges

[vvoovv]

Sometimes it's desirable to prevent wave propagation for some edges.

Below are a couple of examples.

The red color is used mark the edges with no wave propagation.

[polarkernel]

Sometimes it's desirable to prevent wave propagation for some edges.
Do you think it would be possible to include the feature #9 to bpypolyskel?

No, I don't think so, I see no way.

[vvoovv]

If there are edges that don't emit waves, edge events for those edges can be omitted. However the other events must be calculated for those edges.

If there is straight skeleton edge with a loose end (like in the example below), then its intersection with an edge of the original polygon must be found.

[polarkernel]

If there are edges that don't emit waves, edge events for those edges can be omitted. However the other events must be calculated for those edges.

Unfortunately it is not that simple. Let me explain using an example. In the following rectangle, I removed the edge events of the edge at the right, while the vertexex remained valid (left image, click on images to magnify). When the edge event 0 is processed (middle image), it creates a new edge event 4 (blue dot), which finally, when processed, leads to the complete skeleton (right). The red lines show the list of active vertices (LAV).

If the vertexes of the edge not to be moved get invalidated (shown as red cross instead of dot), we get the desired result for this simple case. Again, the edge event 0 creates a new edge event 4, but this time it is invalid (blue cross):

But the LAV contains now invalid vertices, which should not be the case. Removing them lets the LAV collapse to a line. It worked for this simple case, but here is an example, where the process crashes:

I assume that in this case the reason was a split event that used one of the original edges as opposite edge. These edges (not the same as the edges we enter to skeletonize) don't get actualized for validity of vertexes.

[polarkernel]

Sometimes it's desirable to prevent wave propagation for some edges.

Could we eventually solve this using a postprocessing at the very end of polygonize(). At least for the simple cases it should easily be possible to identify the edge, as their indices ar the first two of the face, while the third is the node to be changed. Moving this node to the center of the edge while keeping its height should bring the desired result, a vertical face:

I do not yet understand your second example, the image is too blurry for my eyes. May I get the corresponding footprint?

[vvoovv]

I created a simplified version (no spikes and perfect alignment) of the desired result. I'll add the footprint later.

Below is "normal" version for the comparison:

[vvoovv]

May I get the corresponding footprint?

It's actually already available in the automated tests:
tests/test_3803883_salamanca_avenida_filiberto_villalobos.py

[vvoovv]

When the edge event 0 is processed (middle image), it creates a new edge event 4 (blue dot) ...

Maybe I don't understand something. I think the edge event 4 can't be created, since the rightmost edge doesn't emit a wavefront. And the triangle with red edges can't happen in this case since the the rightmost edge isn't available to form the triangle.

[vvoovv]

Could we eventually solve this using a postprocessing at the very end of polygonize().

It was my original idea. Yes, it would work for the triangles formed by the straight skeleton but not for more advanced cases like the one in Salamanca.

[polarkernel]

Maybe I don't understand something.

The first row of images is the example that follows your proposition

If there are edges that don't emit waves, edge events for those edges can be omitted. However the other events must be calculated for those edges.

The algorithm does not really work with wavefronts. There are only vertexes, which are used to compute new events. In this example (first row of images) I left the vertexes belonging to the static edge as unprocessed (or valid in Botffy's code), while I removed its events. Therefore, the vertexes are used to create the egde event 4.

In the second example (second row of images) I marked these vertexes as processed (invalid). Then the egde event 4 gets created, but is invalid because its vertexes are invalid. But in more complicated contours, also for Salamanca, this leads to crashes.

[vvoovv]

Ok, I see. That's because I haven't still studied the original algorithm.

I have still a note to the image below. The edge event happens in the intersection point of bisectors. However the bisector for the upper red vertex of the triangle with red edges isn't depicted correctly. Is my note correct?

[polarkernel]

I have still a note to the image below.

You are right, my images are not that clear. I use them during the debugging and the left one just shows me, where the event to be processed came from. Let me try to explain the process in detail, so that you hopefully get a clearer picture.

A Vertex consists of the position of a vertice, the previous and next edge, the bisector between these edges and links to the previous and next Vertex. Initially there have been four vertexes, one for every vertice of the rectangle. The intersection of the bisectors of the two vertexes on the left created the event 0 during initialization. Processing the event 0 goes through the following steps:

1. A new vertex is created at the position of the event.
2. The two vertexes of event 0 are removed from the circular list LAV, while the new vertex is inserted. The LAV is now the red line in the image.
3. The two vertexes that created event 0 are marked as invalid (processed).
4. Because the new vertex is not reflex, a new edge event 4 is created at the intersection of the bisector of the new vertex and the bisector of the previous vertex.
5. The same happens for the bisectors of the new and the next vertex, but this event 5 is not processed, because the remaining vertexes get invalidated when event 4 is processed.

What I depicted on the left part of the image was the LAV, before event 4 was processed, and the bisectors (dotted lines) that constructed the event 4 in step 4. The LAV is not used to for bisectors, it just remembers the ordering (previous and next) of the vertexes. All processing steps use always the original edges, which makes things sometimes so complicated, mainly for parallel edges.

[vvoovv]

4. Because the new vertex is not reflex, a new edge event 4 is created at the intersection of the bisector of the new vertex and the bisector of the previous vertex.

Just to make things even more clear. The previous vertex in the sentence above is the 90 degrees vertex of the original rectangle. Right?

[polarkernel]

Right?

Exactly! To find the previous vertex one follows the LAV (red) from the new vertex in clockwise direction.

[polarkernel]

I can't find a solution for this request. I tried a lot of ideas, but most of them failed already on paper. The skeletonize algorithm does not provide any handle to reach this goal. I even tried to move the vertices of the static edge to "infinity".

I think the only way would be to use another type of skeletonize algorithm. It seems that for instance a weighted straight skeleton could do this job by setting the weight of the static edge to zero. I read once also that a straight skeleton based on a motorscycle graph could do that, but I was no more able to retrieve this text.

[vvoovv]

It seems that for instance a weighted straight skeleton could do this job by setting the weight of the static edge to zero.

Or in the terms of the wavefront, setting the wavefront speed to V for all "normal" edges and to zero for the static edges.

[vvoovv]

By the way, found a very detailed explanation of the SLAV algorithm in Russian.

[polarkernel]

Or in the terms of the wavefront, setting the wavefront speed to V for all "normal" edges and to zero for the static edges.

Exactly. In literature about weighted straight skeletons, the terms speed, weight and angle (of the roof's slope) are used interchangebly. However, events do no more lie on bisector intersections and that's why our algorithm may not be adapted for this case.

[polarkernel]

By the way, found a very detailed explanation of the SLAV algorithm in Russian.

Interesting. These are excerpts of papers and presentations mainly by Felkel and Obdržálek, Tom Kelly, Stefan Huber and Martin Held, using their original figures. I found nothing new to me, I already have all these papers.

One amusing sentence, not from one of these papers: Ещё примеры не для слабонервных. ;-)

[vvoovv]

I read once also that a straight skeleton based on a motorscycle graph could do that, but I was no more able to retrieve this text.

I assume it was the paper by Stefan Huber. Here is the list of his papers with the download links:
https://www.sthu.org/research/publications/
There are quite a few of papers in the list.

[polarkernel]

I assume it was the paper by Stefan Huber.

Maybe. Martin Held, Stefan Huber and Peter Palfrader form a very active group researching around straight skeletons at the Department of Computer Science of the University of Salzburg in Austria. Martin Held is Director of the Computational Geometry and Applications Lab there. Stefan Huber is professor in this departement, while Peter Palfrader is postdoc research fellow, again in the same departement.

They do an excellent and very active research on straight skeletons and have written tons of papers around this subject. There main goal seems to be to crack the best big O values. They also provide two open source implementations, MONOS and SURFER2, based on CGAL. It is all written in C++ and it is absolutely impossible to incorporate CGAL to Blender.

Unfortunately, my skills to understand and transform their mathematical notations to code are quite limited.

[vvoovv]

I am more than happy with the current state of bpypolyskel!

[costika1234]

Guys, this library is an absolute jewel. I can't thank you enough for all the hard work you put into creating a developer friendly tool that handles so many roof-related edge cases!

[vvoovv]

Hi @costika1234

Thank you for your feedback.

May I know how you are using bpypolyskel?

[costika1234]

I used this library to build a SketchUp extension that generates a roof from a 2D plan. An existing SketchUp plugin (from 1001bit Tools) was unable to generate the correct geometry for a biscuit-like shape, but it looks like I can achieve this task via your amazing library.

That said, the correct geometry seems to depend on the position of the 2D polygon within the SketchUp canvas. Perhaps some precision errors are creeping in, but I can just translate the polygon a bit to arrive at the desired output. I will play a bit more with this example and will let you know if I find any library-related problems.

PS. Take a look at the PR I posted earlier today! 😉