bpypolyskel.polygonize signature

[polarkernel]

The first part is here

bpypolyskel.polygonize(verts, firstVertIndex, numVerts, numVertsHoles=None, height=0., tan=0., faces=None, unitVectors=None)

verts

A list of vertices. Vertices that define the polygon and possibly its holes are located at the end of the verts list starting at the index firstVertIndex. Each vertex is an instance of mathutils.Vector with 3 coordinates. Z-coordinate is the same for all vertices of the polygon.

For the polygon without holes, there are numVerts vertices in the counter clockwise order.

For the polygon with holes there are:

• numVerts vertices in the counter clockwise order for the outer ring
• numVertsHoles[0] vertices in the clockwise order for the first hole
• numVertsHoles[1] vertices in the clockwise order for the second hole
• ...
• numVertsHoles[-1] vertices in the clockwise order for the last hole

Vertices of the straight skeleton are added to verts list.

firstVertIndex

The first index of vertices in the verts list that define the polygon and possibly its holes

numVerts

The number of vertices in the polygon for the one without holes.
The number of vertice in the outer ring of the polygon for the one with holes

numVertsHoles

A Python tuple or list. The elements define the number of the vertices in the related hole.

height

The maximum height of the hipped roof to be generated. If both height and tan are equal to zero, flat faces are generated. height takes precedence over tan if both have a non-zero value.

tan

It's desirable in many case to deal with roof pitch angle instead of maximum roof height. The tangent of the roof pitch angle can be supplied for that case. If both height and tan are equal to zero, flat faces are generated. height takes precedence over tan if both have a non-zero value.

faces

A Python list of the resulting faces formed by the straight skeleton. If it is given, the faces formed by the straight skeleton are appended to it and it is returned by bpypolyskel.polygonize(..). Otherwise a new Python list of faces is created and it is returned by bpypolyskel.polygonize(..).

unitVectors

A Python list of unit vectors along the polygon edges (including holes if they are present). The direction of the vectors corresponds to order of the vertices in the polygon and its holes. The order of the unit vectors in the unitVectors list corresponds to the order of vertices in the input Python list verts. The Python list unitVectors (if given) should be used inside the bpypolyskel.polygonize(..) function instead of calculating it once more. If the list is not given, the unit vectors should be calculated inside the bpypolyskel.polygonize(..) function.

Returned value

A list of the faces with the indices of vertices. The faces are formed by the straight skeleton. The order of faces in the list corresponds to the order of vertices in the input Python list verts.

For example, suppose one has

verts = [..., v1, v2, v3, ...]

Then in the return list on should have

faces = [
    ..,
    (index_of_v1, index_of_v2, ...),
    (index_of_v2, index_of_v3, ...),
    (index_of_v3, index_of_v4, ...),
    ...
]

[polarkernel]

The current definition of the signature of bpypolyskel provides the results in the function onFace as indices of the vertices from the verts list that define the face.

However, the algorithm by Botffy provides its results as vertices (resp. their coordinates), but not as indices. While the sources of the new arcs (the skeleton points) are all new, the sinks may be existing points of the polygon (or its holes) or other skeleton points. To construct the individual faces, all sinks have to be searched in the polygon, eventually in its holes or in the new skeleton points by their coordinates to get their indices in the verts list. This seems to me to be very inefficient.

I studied a way to keep the information about the original indices through the computation in bpypolyskel, but this makes then this computation quite inefficient.

Would it eventually be possible to return the vertices themselves instead of the their indices in onFace? This would be ways faster. The function would then have the following signature:

onFace(faceVertices, onFaceObj)

faceVertices: List of vertices that define the face.
onFaceObj: The parameter to the bpypolyskel.polygonize.

[vvoovv]

How do you construct faces out of source and sink vertices?

[polarkernel]

I have found an algorithm that constructs all faces out of the topology of the graph. Its input are all vertices (only as indices) and all edges of the polygon, the holes and the skeleton. The data for the polygon and the holes comes from the verts list while the skeleton data has to be extracted from the output of skeletonize. Similar algorithms seem to be quite rare.

And at this point I see that my proposition does not solve the issue I described. It remains a problem to link the sinks of polyskel to the input data. Maybe it would be better to rewrite polyskel to provide these links.

[vvoovv]

How about using a Python dictionary as a lookup table for vertex coordinates?

lookupTable = {}

if not (vert[0], vert[1]) in lookupTable:
    vertIndex = len(verts)
    verts.append(vert)
    lookupTable[ (vert[0], vert[1]) ] = vertIndex

[polarkernel]

Well, I decided to continue and to accept the issue described. Then we will see if the inefficiency is really relevant. Having a complete and already running project is always a good starting point for improvements and updates later.

[vvoovv]

@polarkernel

I implemented the straight skeleton and hipped roof generation for a quadrangle. The intention was to do it very fast for a quadrangle footprint since it is encountered quite often.

The related code is here and some definitions are here.

[polarkernel]

Thanks! This comes at a perfect time, as I am already able to extract the faces. The only remaining step is to compute the z-values of the skeleton nodes.

I am using actually an external version of mathutils so that I may develop out of Blender, which makes it easier to me. I will then try to create a demo addon. Do you maybe have any template available to ease this last step?

[vvoovv]

The templates are available in the Blender Text editor menu:

A basic template for the addon is located in the very first item Addon add object.

[vvoovv]

The only remaining step is to compute the z-values of the skeleton nodes.

I created a ticket #4 to describe hipped roof height calculation.

[polarkernel]

Thanks for the help. Once I have the first solution ready, I will commit the code, first without the Blender demo addon. Maybe you like already to test it in your environment. The addon will then follow.

[polarkernel]

I found a possible issue in the signature of the function bpypolyskel.polygonize(). As a test I tried to plot the faces using the function onFace(), called within polygonize(). It seems that the skeleton nodes appended to verts get not updated until this function returns. In the function onFace, they were not yet available. I don't know what your idea for the usage of onFace is, but this may be an issue. Would it eventually be better to return a list of the vertices-lists for every face?

[vvoovv]

Do you mean the Python list verts isn't updated until the function bpypolyskel.polygonize(..) returns?

Could you please push the code?

[vvoovv]

The idea of using the onFace callback function is to avoid creating a list of lists or tuples with indices each time when bpypolyskel.polygonize(..) is called, i.e. to save some memory.

[vvoovv]

I introduced a new parameter tan to bpypolyskel.polygonize(..).
I also introduced a new parameter contourIndex to onFace(..).

Descriptions are in the first message of this ticket.

[vvoovv]

Are unit vectors for each polygon edge calculated inside bpypolyskel.polygonize(..)?

Those unit vectors are also needed to assign UV-coordinates to the faces of the hipped roof. Normalizing a vector is a costly operation because of the square root.

[polarkernel]

I found a possible issue in the signature of the function bpypolyskel.polygonize(). .....

This issue does not exist, fortunately. It was produced by a last minute bug from my side that is fixed now. Sorry for the confusion.

[polarkernel]

I introduced a new parameter tan to bpypolyskel.polygonize(..).
I also introduced a new parameter contourIndex to onFace(..).

OK, but shouldn't the arguments with default values be moved to the end of the argument list?

bpypolyskel.polygonize(verts, firstVertIndex, numVerts, onFace, onFaceObj, numVertsHoles=None, height=0., tan=0.)

contourIndex: Actually I excluded the contours of the polygon and the holes from the face list. Do you expect them to be included in the calls to onFace? Or do you mean the membership of the first edge of a face, which belongs either to the polygon or to a hole?

[polarkernel]

Are unit vectors for each polygon edge calculated inside bpypolyskel.polygonize(..)?

No, not i my code. But in Botffy's code for skeletonize() there are a lot of calls to normalize() for vectors. Maybe it would be possible to save their results somehow.

[vvoovv]

I think that idea with the onFace callback function is too cumbersome.

I suggest to return a Python list of faces. The order of faces in the list corresponds to the order of vertices in the input Python list verts.

For example, suppose one has

verts = [..., v1, v2, v3, ...]

Then in the return list on should have

faces = [
    ..,
    (index_of_v1, index_of_v2, ...),
    (index_of_v2, index_of_v3, ...),
    (index_of_v3, index_of_v4, ...),
    ...
]

Also I suggest to introduce one more input parameter, a Python list faces. If it is given, the faces formed by the straight skeleton are appended to it and it is returned by bpypolyskel.polygonize(..). Otherwise a new Python list of faces is created and it is returned by bpypolyskel.polygonize(..).

[vvoovv]

I update the first and the previous messages

[vvoovv]

Are unit vectors for each polygon edge calculated inside bpypolyskel.polygonize(..)?

No, not i my code. But in Botffy's code for skeletonize() there are a lot of calls to normalize() for vectors. Maybe it would be possible to save their results somehow.

That's curtainly inefficient two calculate lengths of the polygon edges and the unit vectors along the polygon edges twice.
I suggest to have an additional input Python list to cache those calculations.

[polarkernel]

Are unit vectors for each polygon edge calculated inside bpypolyskel.polygonize(..)?

No, not i my code. But in Botffy's code for skeletonize() there are a lot of calls to normalize() for vectors. Maybe it would be possible to save their results somehow.

That's curtainly inefficient two calculate lengths of the polygon edges and the unit vectors along the polygon edges twice.
I suggest to have an additional input Python list to cache those calculations.

I will study this proposition. First, I will commit a solution including all changes up to here. It will be ready in a few hours. Then we may start to optimize it, I suppose there will be potential for plenty other optimizations.

[polarkernel]

... The addon will then follow.
A demo-addon has just been committed.