Narrow and curvy facades, churches and cathedrals

[vvoovv]

I suggest to skip single narrow facades from the visibility and classification calculations.

A single narrow facades is the one surrounded by wide facades. It has a width below some threshold.

If narrow facades are introduced, the method for assigning the side facades must be changed.

Suppose we have a sequence: _FrontFacade, _NarrowFacade, _UnclassifiedFacade.

_UnclassifiedFacade should be classified as the side one.

[vvoovv]

I suggest adding one more value for FacadeClass:

class FacadeClass:
  ...
  narrow = 7

[polarkernel]

A single narrow facades is the one surrounded by wide facades. It has a width below some threshold.

I think this definition is not yet complete. For instance the narrow facades below (manhattan_01.osm, blue arrows) should not be excluded, I suppose:

I assume you think of narrow facades that are more or less perpendicular to the wide facades?

[polarkernel]

Maybe we could discuss some pattern matching. It is easy to implement, I already used it in the bpypolyskel project. Let me define an angle change from the predecessor facade to the current one as smooth, when it is small, say below 30°, or sharp, if it is more (there could also be more ranges, if required). The width of a facade is wide or narrow, using your definition. The combination of angle change and width of a facade can the be expressed by two characters of the following alphabet:

R: sharp right r: smooth right L: sharp left l: smooth left X: R or L or r or l w: wide n: narrow

As starting point, I already found the following patterns (bold and italic part), where ... means repeat previous character zero to N times:

-Xw-Rn-Xw- ==> narrow -Xw-Ln-Xw- ==> narrow -Xw-rn...rn-Xw- ==> curvy -Xw-ln...ln-Xw- ==> curvy

Maybe the complete character sequences of a building polygon could already provided by the class BldgPolygon, as the angles get already calculated there.

[vvoovv]

For instance the narrow facades below (_manhattan01.osm, blue arrows) should not be excluded, I suppose

Why?

I assume you think of narrow facades that are more or less perpendicular to the wide facades?

Not necessarily. A single narrow facade can have an arbitrary angle with a neighbor wide facade.

[vvoovv]

Maybe we could discuss some pattern matching.

I'll review it tomorrow.

[polarkernel]

Not necessarily. A single narrow facade can have an arbitrary angle with a neighbor wide facade.

OK, it seems that I misunderstood your intention. Then also forget about pattern matching, this can be solved using simpler ways. Am I right if I interpret your idea as follows?

All facades with a width below some threshold get classified as narrow. For the classification of side facades: Between a front facade and an unclassified facade, would any number of narrow facades be treated as if they wouldn't exist or does this idea only hold for one single narrow facade? A sequence of narrow facades connecting each other "smoothly" is interpreted as curvy, but does not get its own classification.

[vvoovv]

The reasons to introduce narrow facades is 1) to get some performance gain (visibility isn't calculated for the front facades) 2) more correct detection of side facades in the presence of narrow facades

Would any number of narrow facades be treated as if they wouldn't exist?

That wouldn't work for a sequence of the narrow facades. Let's consider a footprint below:

Suppose the edge at the bottom is classified as the front facade. If we skip the curvy parts, than the edge at the top should be classified as the side facade, but that would be incorrect.

Only single narrow facades should be skipped from the visibility calculation and classification.

[polarkernel]

OK, I think I got it.

Only single narrow facades should be skipped from the visibility calculation and classification.

Just to be sure: I assume this is meant only for their usage to classify side facades. Otherwise narrow facades just stay to be classified as narrow facades, not only single ones but also those that build curvy sequences.

Shall I start to implement this idea?

Would you mind if I add an attribute lengthSquared to the class BldgEdge? In frontOfInvisibleBuilding(), this value is also required for some edges to find the longest edge and could be reused there.

[vvoovv]

Just to be sure: I assume this is meant only for their usage to classify side facades. Otherwise narrow facades just stay to be classified as narrow facades, not only single ones but also those that build curvy sequences.

I suggest to classify curvy facades as curvy

Shall I start to implement this idea?

I want to understand how both narrow and curvy facades fit together before starting the implementation.

[vvoovv]

Example of a footprint without any wide facades and curvy sequences. Only narrow facades with sharp angles are present. Do you think it's possible to simplify that kind of footprint?

[polarkernel]

Do you think it's possible to simplify that kind of footprint?

Should be possible, but I have to do some tests to get some feeling of what the outcome could be.

[vvoovv]

Only narrow facades with sharp angles are present. Do you think it's possible to simplify that kind of footprint?

A building footprint can be completely covered by small elements. But typically there are significant spaces between the small elements like in the cathedrals in Bern:

[vvoovv]

Another example of small elements on the facades. The small elements form balconies in this case.

[vvoovv]

Another example of the small elements on the facades:

[polarkernel]

A building footprint can be completely covered by small elements. But typically there are significant spaces between the small elements like in the cathedrals in Bern:

By simplification, do you mean someting similar as proposed in this paper?

[vvoovv]

By simplification, do you mean something similar as proposed in this paper?

Yes, but I need to formulate more precisely what is needed for. I'll do it today.

[vvoovv]

The issue should be joined with #17

[vvoovv]

In addition to the existing processing (removal of the straight angles) of the building polygons I propose to include:

• pattern matching
• detection of curvy sequences

Churches and cathedrals require special processing.

Examples of the patterns:

A detected pattern is replaced with an edge for the visibility calculation and facade classification. Those proxy edges can be removed again in the second pass of the removal of the straight angles if they form straight angles with their neighbor edges.

It isn't yet clear what to do with the curvy sequences. A possible approach is to measure the length of the edge between the first and the last nodes of the curvy sequence. If the length of that edge is small compared to the building size, then the curvy sequence is skipped form the visibility calculation and the facade calculation. Otherwise it is simplified (like in the paper) and goes through he procedure of the facade classification.

If the whole building polygon is a curvy sequence (or it has only one straight segment) and it doesn't contain an entrance at OSM, then the curve sequence must be simplified (like in the paper) and must go through the procedure of the facade classification. The result of the facade classification must be somehow mapped back to the original curve sequence to find a place for an entrance.

[vvoovv]

I suggest to skip single narrow edges that are not part of the detect patterns from the the facade classification as proposed above.

[polarkernel]

Churches and cathedrals require special processing.

I propose to do the detection of the special parts using the original edges (straight angles already removed) as input and delivering back as output the detected objects (patterns, curvy sequences, maybe others), their position and the replacement proxy edges for visibility calculation and facade classification in one module. This could be computationally demanding. Eventually it could be useful to detect first by a simple test (number of edges?), whether the building is "complicated" and needs special processing, or not and special processing could be skipped.

Detecting patterns as the examples in your image is feasible. It would require the unit vector and the length for every edge. The same is required for curvy sequences detection. I propose to add these attributes to BlgEdge.

The result of the facade classification must be somehow mapped back to the original curve sequence to find a place for an entrance.

The most difficult part in my eyes is a smart embedding of this feature into the current architecture of the program. I do not yet have any idea about the "somehow".

[vvoovv]

Detecting patterns as the examples in your image is feasible. It would require the unit vector and the length for every edge. The same is required for curvy sequences detection. I propose to add these attributes to BlgEdge.

I added the property length to the class BldgEdge and the property unitVector to the class BldgVector.

[vvoovv]

I suggest to use another branch for testing the advanced processing.

[polarkernel]

I suggest to use another branch for testing the advanced processing.

New branch dev_patt created for testing the advanced processing.

[polarkernel]

I added the property length to the class BldgEdge and the property unitVector to the class BldgVector.

The function length() does not work. self.v1 and self.v2 are tuples and can't be subtracted. However, I also can't get your intention of what type they should be to have an attribute length in (self.v2 - self.v1).length.

[vvoovv]

I thought they are of the type mathutils.Vector. But they are seemingly not.

[vvoovv]

I'll convert them to either mathutils.Vector or numpy.array.

[vvoovv]

The function length() does not work.

It should work now. Sorry for the bug. It can be accessed as a property:

edge.length

[vvoovv]

I added the file sirius.osm to the _osmextracts. It contains a bunch of curvy buildings and curvy sequences:

[polarkernel]

It contains a bunch of curvy buildings and curvy sequences:

A first result:

The rule for this result was as follows:

• Find patterns of at least 4 consecutive angles between edges, that are in the range of 5° to 30°.

• Collect all edges, that have at least at one end such a low angle and compute the mean length of these edges. This gives an adaptive idea of the length of curvy edges for a building.

• Remove all edges from the sequences, that are longer than a factor (currently 1.5) times the mean length found before. These edges are always at the end(s) of a sequence.

• The remaining edges are curvy edges.

I made a new class FacadePatterns and a first method detectCurvyEdges(). Additionally, I introduced a command line argument --patterns that starts via a do() function this detection, similar to the existing modules. More detection functions will follow to enable for experiments. But the result gets plotted immediately at the end of the function and not yet in a renderer. All this is not yet committed to _devpatt.

I stuck now on how to transfer the detection results to the addon (and to the renderer). Add papttern type to BldgEdge?

[polarkernel]

A surprizing simple result on spike detection. The following simple algorithm works quite well for churches and cathedrals:

• Find patterns of at least 2 consecutive angles between edges, that are larger than 30° to the left, but are not classified as curvy.

• Collect all edges, that have at least at one end such a large angle and compute the mean length of these edges. This gives an adaptive idea of the length of spike edges for a building.

• Remove all edges from the sequences, that are longer than a factor (currently 2.0) times the mean length found before.

• The remaining edges are spike edges.

Unfortunately, this works only for buildings that have at least 50 edges. A simple rectangle would be classified immediately as spike. However, for instance for churches and cathedrals, it works perfectly. A promizing starting point in my opinion (red: curvy, blue: spike):

[polarkernel]

I commited a first version to the branch _devpatt that includes the detection of single narrow facades (I called them spikes) and curvy sequences. The code is not optimized at all and its own intention is to provide an experimental base for discussions. It will require a big refactoring finally. It can be switched on using the command line argument --patterns.

Processing of buildings is filtered by a primitive rule. Only buildings are processed when they have more short edges (< 5m) than long edges or when they have mor than 10 short edges. Currently, all processed buldings are processed as complete buildings, containing the full circular polygon, even if they have shared edges. Maybe buildings with shared edges should be excluded from processing.

The result is painted by a new renderer BuildingPatternRender, where curvy sequences are plotted in red and spikes in blue. It is possible that two patterns overlap, which is not vizualied in the plot. I just added a property pattern to the class BldgEdge to be able to transfer the result to the renderer. But this does not presuppose a future solution.

[vvoovv]

(manhattan_01.osm)

The spike is too large:

[vvoovv]

These edges are always at the end(s) of a sequence.

That statement isn't clear for me. Why are they always at an end of a sequence?

[vvoovv]

I stuck now on how to transfer the detection results to the addon (and to the renderer). Add pattern type to BldgEdge?

I was thinking about a class which instance contains all necessary information information about the sequence (the start and end edges of the sequence, etc). The instance of the class is assigned to the field sequence or pattern of a building edge (BldgEdge). The field is equal to None if the edge doesn't belong to any sequence.

[polarkernel]

That statement isn't clear for me. Why are they always at an end of a sequence?

If the length limit is not requested, there may be edges at the end of such a sequence, that have a length beyond the length limit. Finding this limit is a difficult task and not yet really solved. In the current implementation I have set it to a constant value of 5m. With this value, there still appear edges at the end, that get included to the pattern:

In the comitted code I added an additional rule for patterns that look like balconies:

The rule asks for a long edge (>5m) with an angle of >30° to the left on both ends, that is surrounded by two short edges (angle to left > 30°, short length), similar to the short edges in spikes.

The spike is too large:

This is an edge detected as balcony, as described above. It shows well the issues of a pattern matching approach. There may be unexpected places, that weren't thought for this case, but that match to a pattern.

[polarkernel]

I was thinking about a class which instance contains all necessary information information about the sequence (the start and end edges of the sequence, etc). The instance of the class is assigned to the field sequence or pattern of a building edge (BldgEdge). The field is equal to None if the edge doesn't belong to any sequence.

I am sorry, I do not yet understand your idea. When I look at the whole process, the following steps will be new:

1. A process, similar to what I already proposed, has to detect the small structures like spikes or "balconies". Everey such pattern has a start- and an end-edge.
2. These patterns have to be replaced by a new edge (or new edges?), that adequately may be used for visibility check and classification. The result is a simplified polygon, or a simplified building
3. The relation between the new edges and the original ones has to be stored. This is a n : 1 relation, it can't be stored in the BldgEdge class in my opinion.
4. The new buildings have to be processed for visibility and classification by presenting there a class similar to Building, but containing the simplified polygon.
5. At the end, all edges of this new polygon have a facade class.
6. The facade class of the edges that were replaced has to be transfered somehow to the original edges of the original polygon. The relation stored in 3. may be used for the replaced edges.

In _facadevisibility, the function edgeInfo() of the polygon is used to get the edges, while in _facadeclassification, the function getVectors() of polygon is used. Maybe the instance of polygon could be replaced.

[vvoovv]

The code is not optimized at all and its own intention is to provide an experimental base for discussions.

The tangent of the angle between the the edges is already calculated in BldgPolygon.processStraightAngles(..). The calculated tangent can be used later for the pattern detection.

[vvoovv]

These patterns have to be replaced by a new edge (or new edges?), that adequately may be used for visibility check and classification. The result is a simplified polygon, or a simplified building

(1) Patterns with sharp angles

If a pattern is just a small decorative facade element, it can be safely skipped from the visibility calculation.

Otherwise the pattern is replaced by an edge. The proxy edge with its neighbors can be replaced again by an edge if all of them form a straight angle. The resulting edge is classified and its class is propagated to the original edges

(2) Curvy sequences

If the total length of the curvy sequence is significantly smaller than the perimeter of the building polygon, it can be replaced by a single edge for the visibility calculation. If an entrance must be placed on the that sequence, it can be placed in the intersection point of the curvy sequence with a line originating from the proxy edge and perpendicular to the proxy edge.

If the total length of the curvy sequence is relatively large, then it is replaced by a sequence of edges sharing the nodes with the curvy sequence. If an entrance must be placed on the the curvy sequence, it can be done in a similar way as described above,

[vvoovv]

I am sorry, I do not yet understand your idea.

proxyEdge = BldgEdge(edge1.id1, edge1.v1, edge2.id2, edge2.v2)
proxyEdge.prev = edge1.prev
proxyEdge.next = edge2.next
edge1.prev.next = proxyEdge
edge2.next.prev = proxyEdge

sequence = CurvySequence(edge1, edge2, proxyEdge)

currentEdge = edge1
while True:
    currentEdge.sequence = sequence
    currentEdge.skip = PartOfSequence
    if currentEdge is edge2:
        break
    currentEdge = currentEdge.next

[vvoovv]

In the comitted code I added an additional rule for patterns that look like balconies

The structure can be also used for a staircase in a apartments building.

[vvoovv]

The whole code snippet below can be located in the constructor CurvySequence.__init__.

proxyEdge = BldgEdge(edge1.id1, edge1.v1, edge2.id2, edge2.v2)
proxyEdge.prev = edge1.prev
proxyEdge.next = edge2.next
edge1.prev.next = proxyEdge
edge2.next.prev = proxyEdge

sequence = CurvySequence(edge1, edge2, proxyEdge)

currentEdge = edge1
while True:
    currentEdge.sequence = sequence
    currentEdge.skip = PartOfSequence
    if currentEdge is edge2:
        break
    currentEdge = currentEdge.next

[polarkernel]

The whole code snippet below can be located in the constructor CurvySequence.init.

OK, I think I got the idea. But the code does not yet fit to me. BldgEdge has not attributes prev, next and skip. Did you mesan BldgVector? I assume that with edge1 and edge2 you mean the edges that are adjacent to the ends of the pattern's edges.

[polarkernel]

If a pattern is just a small decorative facade element, it can be safely skipped from the visibility calculation.

This must not let a gap between the adges. I assume by skip you mean that the edge before and after the element have to be connected together, without any proxy edge.

[vvoovv]

Did you mean BldgVector?

Yes. Sorry for the confusion.

I assume that with edge1 and edge2 you mean the edges that are adjacent to the ends of the pattern's edges.

vector1 should be instead of edge1, vector2 should be instead of edge2.

vector1 is the initial vector of a sequence. vector2 is located at the end of the sequence.

[vvoovv]

This must not let a gap between the adges. I assume by skip you mean that the edge before and after the element have to be connected together, without any proxy edge.

The vectors in the sequence are replaced by a proxy vector. The vectors in the sequence are marked as skipped.

[polarkernel]

Before I continue to write code, I like to study the problem in deeper detail and comment my observations and considerations in several posts, starting with this one.

_facadevisibility and _facadeclassification access the edges by the class BldgPolygon. Currently, this class stores the building's polygon by two data structures, an ordered tuple of vectors (which is self.vectors) and as a doubly linked circular list, by the links prev and next of the class BldgVector. This linked list has no anchor.

For visibility detection and classification, these vectors (or their edges) are iteratively accessed either by the methods getVectors() or by edgeInfo(), while the linked list is only used to find neighbors of an edge. Both, getVectors() and edgeInfo() are based on the tuple of vectors.

Inserting a proxy edge is best done using the linked list, as proposed above. But inserting a proxy edge in this list does not change the polygon's output, because the tuple does not get changed and getVectors() and edgeInfo() deliver the original polygon. It would also be costly to insert the new edge in the correct position of the tuple. Therefore I propose to base the polygon completely and only on the linked list and to remove the tuple of vectors.

[polarkernel]

A detected pattern is replaced with an edge for the visibility calculation and facade classification. Those proxy edges can be removed again in the second pass of the removal of the straight angles if they form straight angles with their neighbor edges.

In the current version, the removal of straight edges is handled by declaring them as skipped edges. After that, they never get "unskipped". Removal of proxy edges in the second pass of the removal of the straight angles may lead to complicated code. The whole process is depicted here for a simple detected pattern:

The simplification process including the second pass of the removal is described on the right. Once visibility and facade class are determined, the final edge has to be "unskipped", while the class information has to be transferred back to the original edges. This has only to be done for skipped edges that resulted from proxy edges. This solution is possible, but I doubt that it would be more efficient than to leave the proxy edge where it is for visibility detection and classification.

[polarkernel]

The tangent of the angle between the the edges is already calculated in BldgPolygon.processStraightAngles(..). The calculated tangent can be used later for the pattern detection.

I tried this, but unfortunately it does not work. For edges with sharp angles near 90°, their sign is required. to get the pattern. But the tangent has a discontinuity there, so that for an angle of 89° it is positive, while for an angle of 91° it is negative. The cross product of the unity vectors delivers the sine of the angle, which is continuous at 90°.

[polarkernel]

I commited a cleaned and refactorized version of the pattern detection for simplfication. The main changes are:

• Renamed the main class to FacadeSimplification (new in _facadesimplify.py).
• This class is set as first action (before FacadeVisibilityOther), if the command line argument --simplification is set.
• The result of the simplification (currently the detected patterns) gets visualized, when the command line argument --showPatterns is set.
• The methods detectCurvyEdges() and detectSmallPatterns() of the class FacadeSimplification deliver a list of tuples with the first and the last vector of the detected pattern. These vectors can directly be used for a replacement of the pattern.

[vvoovv]

Therefore I propose to base the polygon completely and only on the linked list and to remove the tuple of vectors.

The code from the list comprehension (function(value) for value in iterator) is significantly faster then iteration through the for cycle.

I'll measure the execution time for both variants.