[streets] From Way-Sections to Triangles, Discussion

[polarkernel]

The discussion in this issue is related to the documentation From Way-Sections to Triangles in issue #39. Starting from way-sections, neighboring or otherwise relevant triangles have to be found to collect the required shapes for a realistic street rendering by the addon. In this issue, I like to discuss the problems that may arise in this process and their possible solutions.

[polarkernel]

It's not really clear to me yet how to finally render the streets and their immediate surroundings from the triangles obtained. I suppose the starting point will be the way-sections between the intersections. This would mean that from there we have to find the neighboring triangles.

It would be useful to have a rough sketch of the ideas for the rendering process. Knowing this would help to identify the issues in the triangulation process pipeline.

[polarkernel]

As described in the documentation, the subdivision of graph-cycles into tiles and, only sometimes, the subtraction of objects, both create new vertices. Some of these lie on way-segements and may be important as triangle vertices. How to efficiently check whether a new vertex is located on a way-segment of one of the way-sections that form the graph-cycle?

[polarkernel]

What to do with the ways that did not yet lead to triangles, the spurs and the solitaires? Probably two problems are to be solved for these:

• How to find the triangles that are intersected by these ways?
• Is it required that the intersected triangles have to be triangulated again or could they possibly be used directly?

[vvoovv]

It would be useful to have a rough sketch of the ideas for the rendering process. Knowing this would help to identify the issues in the triangulation process pipeline.

I've copied the content of my comment in the neighbor issue and updated it.

The triangulation should allow to find the borders of carriage ways and the borders of crossings between them, so that

• the carriage ways don't hit the neighbor buildings and other neighbor objects;
• the carriage ways don't hit the neighbor cycle ways, tram rails and footways if they are available;
• there is some space for sidewalks if footways aren't available.

The same applies to the cycle ways and tram rails if they are available.

The sidewalks occupy the rest of the space near the buildings.

---

Each carriage way between two crossings can be rendered as a mesh or as a Blender curve with a bevel object assigned to it.
Each crossing will be rendered as a mesh.

[vvoovv]

What do you think about the idea I posted in the neighbor issue:

Let's define an edgeKey for an edge with the coordinates of its vertices (x1,y1) and (x2,y2) as follows.

If x1 < x2, the edgeKey is a tuple ( (x1,y1), (x2,y2) )
If x1 > x2, the edgeKey is a tuple ( (x2,y2), (x1,y1) )
If x1 == x2 and y1 < y2, the edgeKey is a tuple ( (x1,y1), (x2,y2) )
If x1==x2 and y1 > y2, the edgeKey is a tuple ( (x2,y2), (x1,y1) )

A python dictionary edges is used to search for an edge entry through its edgeKey:

edge = edges[edgeKey]

edge in the expression above is an instance of some class Edge which keeps the references to some entities using the edge, namely

• way-segment
• one or two vectors that belong to graph-cycles (two vectors if the same edge is shared by two graph-cycles)
• one or two vectors that belong to triangles after the triangulation (two vectors if the same edge is shared by two triangles)

So for each PyGEOS polygon (including triangles) a companion polygon should be created that has a list of vectors.
The Vector class has at least two members:

• an instance of the Edge class
• a boolean variable direct. Its value is True if the direction of the vector is from the first vertex to the second one. The value is equal to False otherwise.

This way we can easily find a triangle that shares an edge with a particular way-segment.

[vvoovv]

How to efficiently check whether a new vertex is located on a way-segment of one of the way-sections that form the graph-cycle?

The approach with the Edge class described above can help to answer the question if a side of a tile is located on a way-section.

If it is the case then the edge in question is shared only by one vector that belongs to the tile.
It it is not the case then the edge in question is shared by two vectors that belong to the adjacent tiles.

[polarkernel]

I've copied the content of my comment in the neighbor issue and updated it.

I think this should currently be the most important part of the discussion, because it will determine the requirements for the triangles and the way to find them. I also don't mind questioning the method with graph-cycles and possibly even finding another solution.

Each carriage way between two crossings can be rendered as a mesh or as a Blender curve with a bevel object assigned to it. Each crossing will be rendered as a mesh.

This is clear to me. I suppose the widths of the carriage ways are determined by their category, number of lanes, etc. But will the mesh of a carriage way cut its border area similar to what you sketched here, or will it have to be subtracted from this area to get just the surrounding area?

The triangulation should allow to find the borders of carriage ways and the borders of crossings between them, so that
the carriage ways don't hit the neighbor buildings and other neighbor objects;

Does this mean that the width of the carriage ways is locally reduced when it would touch neighbor buildings and other neighbor objects? If yes, its base shape could be constructed by a logical union of the graph-cycle polygon with the carriage way's shape. In principle, this corrected shape could be triangulated to construct a mesh. I don't know how this would be realizable with Blender curves.

the carriage ways don't hit the neighbor cycle ways, tram rails and footways if they are available;

This is not clear to me. When the widths of the carriage ways are given (and I assume also those of the cycle ways, tram rails and footways), which one would have priority?

there is some space for sidewalks if footways aren't available.

Its width is to be defined.

The same applies to the cycle ways and tram rails if they are available.

All these are currently just treated as ways.

The sidewalks occupy the rest of the space near the buildings.

OK.

What I am not clear about: How can we use the triangles to share the space between ways? To illustrate the problem I have once constructed the triangles of a way-section of the Karl-Marx-Allee (located about in the center of the scene). In red the triangles that have at least one vertex common with the way-section, as you once proposed, the remaining triangles are in blue:

To the south of this way-section we get what we expected. The area ends more or less at the grass of the median strip. But to the north, the area extends to the footway that passes along the village-green. When I similarly construct the triangles for this footway, their area to the south is about the same as the northern area of the Karl-Marx-Allee lane:

So, the triangles are helpful to limit the space, when objects are present. But for cases like this, which part of the space will belong to the primary road and which one to the footway?

[vvoovv]

This is clear to me. I suppose the widths of the carriage ways are determined by their category, number of lanes, etc. But will the mesh of a carriage way cut its border area similar to what you sketched here, or will it have to be subtracted from this area to get just the surrounding area?

The width of a carriage way is determined by the configuration of way-segments that represent carriage ways, footways, cycle ways and buildings and other objects.

The number of lanes (if given) can be used to estimate the width of the carriage ways.

Geometry for carriage ways, cycle ways, footways and other items not covers by OSM objects is created out of triangles. This geometry and OSM objects cover the whole area of interest. They will be projected on the terrain and replace the terrain surface.

[vvoovv]

Does this mean that the width of the carriage ways is locally reduced when it would touch neighbor buildings and other neighbor objects? If yes, its base shape could be constructed by a logical union of the graph-cycle polygon with the carriage way's shape.

Yes.

In principle, this corrected shape could be triangulated to construct a mesh. I don't know how this would be realizable with Blender curves.

In the simplest case the shape of a carriage way is constructed by extruding the center line of the carriage way. The resulted object can be rendered in Blender by a curve with a bevel object.

[vvoovv]

This is not clear to me. When the widths of the carriage ways are given (and I assume also those of the cycle ways, tram rails and footways), which one would have priority?

I think the width of a cycle way and tram rails is fixed.

Then task is to estimate the width of the carriage ways to the given configuration of ways, buildings and other objects. Which number of lanes and the width of the carriage way fits the given configuration best of all?

[vvoovv]

So, the triangles are helpful to limit the space, when objects are present. But for cases like this, which part of the space will belong to the primary road and which one to the footway?

That's actually a cycle way rather than a footway. We can assume that a cycle way has always a fixed width.

But what would be if it were a footway? First, we need to find the width of the carriage way that does not allow the carriage way to hit the footway's center line. The rest will be used by the footway.

[polarkernel]

What do you think about the idea I posted in the neighbor issue:

I am sorry, I tried it many times but I am not able to get the idea of this proposition. Could you please sketch how the lookup procedure would look like to find the triangles that belong to a way-segment (or a way-section), using these structures?

[polarkernel]

How to efficiently check whether a new vertex is located on a way-segment of one of the way-sections that form the graph-cycle?
The approach with the Edge class described above can help to answer the question if a side of a tile is located on a way-section.

My question targeted another issue. When a polygon is tiled, two new vertices are created, that did not exist before. It is easy to find these vertices. The question now is, which edges of the polygon have been divided by these vertices? The only way I found is to check for all polygon edges, whether the vertex lies on the edge or not. I was searching for a more efficient algorithm.

Note that in one graph-cycle, an edge will be replaced by two new (shorter) edges, while for the neighbor cycle, that shares this edge, this will not be the case. So for the approach with the Edge class described above, all structures would habe to be updated. In addition, a new edge is created with each division, but it does not belong to a way-segment.

[polarkernel]

First, we need to find the width of the carriage way that does not allow the carriage way to hit the footway's center line. The rest will be used by the footway.

So an example solution could be to find the shortest distance between the polylines of the carriage way's center line and the the footway's center line and use this as maximum half-width of the carriage way? Such tests would then be required for all ways in the two graph-cycles that belong to the way-section of the carriage way and that do not intersect its way-section.

[vvoovv]

Could you please sketch how the lookup procedure would look like to find the triangles that belong to a way-segment (or a way-section), using these structures?

Suppose there are way-segments A and B and triangles CEA and DBE that have shared edge A and B.

Instance of the class Vector is created for all way-segments and sides of the triangle.

class Vector:
    def __init__(self, v1, v2, edgeGenerator, parent):
        self.edge, self.direct = edgeGenerator.getEdge(v1, v2)
        self.parent = parent
        self.edge.addVector(self)

parent is an object the vector belongs to (polygon, triangle, graph-cycles).

edgeGenerator is an instance of a class that has the members:

• the dictionary edges
• the method getEdge

In the method getEdge a key is calculated from v1 and v2 as described above. If the key is already contained in the dictionary edges, the related edge=self.edges[key] is used. Otherwise a new instance of the class Edge is created.

The class Edge has the members:

• graphCycles (zero, one or two vectors)
• polygonVectors (one or two vectors)
• triangleVectors (one or two vectors)

The vector is added to polygonVectors or triangleVectors depending on its parent in the method addVector.

Now we can easily solve the task of finding triangles that belong to a way-section.

For each vector that forms the way-section we get the related edge:

edge = vector.edge

Then we get the vectors of the triangle(s) that share this edge and the triangle objects.

triangleVectors = edge.triangleVectors
triangle1 = triangleVectors[0].parent
if len(triangleVectors) == 2:
    triangle2 = triangleVectors[1].parent

[polarkernel]

Suppose there are way-segments A and B and triangles CEA and DBE that have shared edge A and B.

Thank you for this clear explanation, that was much more than a sketch! I like this approach, but the task is a bit more complicated, so we will need to refine it. Let me use the same way-segments A and B (red) and a polyline object (for instance a building, blue). Now the edges of the triangles with DE and EF are no more common with one of the edges A or B. Maybe they even could belong to both, to A and to B. This situation happens quite often. The right image shows an (extreme) example.

The situation could even be more ambiguous, when the vertex between A and B is an intersection, as shown below. Then these triangles could belong even to different way-sections.

A similar ambiguity may arise, when the triangles are between two ways, as depicted below, then they may belong to two ways at the same time.

I am still not clear what the purpose of these triangles will be. We discussed carriage ways and their possible interference, but not yet the triangles. For me they are still a result of the discussion we started about here in October of last year. But I am not sure if this idea still holds.

[vvoovv]

I am still not clear what the purpose of these triangles will be. We discussed carriage ways and their possible interference, but not yet the triangles. For me they are still a result of the discussion we started about herein October of last year. But I am not sure if this idea still holds.

Yes, the idea still holds. I thought the triangulation should help building the final polygons as you marked them here.

[vvoovv]

The situation could even be more ambiguous, when the vertex between A and B is an intersection, as shown below. Then these triangles could belong even to different way-sections.

Sorry I don't understand what is the problem with that ambiguity?

[polarkernel]

Sorry I don't understand what is the problem with that ambiguity?

Additional to the decision, whether a triangle belongs to a way-segment or not, a decision is required, to which way-section a triangle belongs. When the way category changes, its texture may change when rendered.

[polarkernel]

Yes, the idea still holds.

So this means that after the assignment of the triangles to way-segments or way-sections, the next step of the development will be to construct these polygons?

[vvoovv]

So this means that after the assignment of the triangles to way-segments or way-sections, the next step of the development will be to construct these polygons?

These polygons are definitely needed for carriage ways.

[polarkernel]

These polygons are definitely needed for carriage ways.

OK, then I suggest that I first figure out how to build these polygons properly. Only after that, when I know this procedure and its requirements, I will try to realize your proposal for the assignment of the triangles.

I still have questions I like to discuss about these polygons, so that I can better understand what the final result needs to be. In the following picture I have depicted a situation very schematically. Given four ways A,B,C and D as center lines and two polyline objects (gray) on top and bottom. These form three (colored) polygons 1,2 and 3.

What should now be the relations of these polygons to the ways? Shall the polygons 1 and 2 be related to way A and the polygons 2 and 3 be related to B? Or shall a part of the polygon 2 be related to way A and another part related to A? What about the ways C and D? Shall these polygon fill the space between the centerlines, as depicted above or shall they already be reduced by the widths of the carriage ways, as depicted below?

It would be helpful if we could agree on one of these attributions.

[vvoovv]

What should now be the relations of these polygons to the ways?

I don't see a purpose to assign these polygons to the neighboring ways.

Ways with the fixed widths

These are cycleways and tram rails.

Carriage ways

If a way represents a carriage way (primary, secondary, tertiary, residential, etc), then the task is to estimate the width of it.

The width of carriage way is calculated as the number of lanes plus some margin. We don't consider more complicated cases for now.

Check if the way has the tag lanes. If it has one, then use the value of the tag for the number of the lanes.

If the way does not have the tag lanes. If the way has the tag oneway, start from 1 lane, otherwise start from 2 lanes. Check if the way does not hit the neighbor ways or neighbor objects. Increase the number of lanes by one if there is the tag oneway or by two if there is no tag oneway. Check again if the does not hit the neighbor ways or neighbor objects. And so one.

[vvoovv]

The question is what to do with the width and shape of footways.

A possible solution would be to start from the fixed width of the footway. Then depending on the configuration of the neighbor objects (e.g. if there are close to the footway or far away), fill the remaining space between the footway and the neighbor objects OR expand the width of the footway OR keep the original width of the footway.

[polarkernel]

I don't see a purpose to assign these polygons to the neighboring ways.

It seems that I lost the track somewhere (which may happen in a remote team). The current result are triangles, placed everywhere in free space within graph-cycles, whereby ways are handled as centerlines only. Here an example depicted in red for the central region of the Karl-Marx-Allee:

Are the polygons built by these triangles already the final result? When they should be used to fill the space between (already expanded) ways, then these ways should be first subtracted from the graph-cycles, before the triangulation of the remaining space, a solution I proposed and implemented some months ago. I didn't care about the width of ways or their collisions since then, but this seems to get the main theme for now. However, I can't yet see the relationship to what I did until now.

I need some help on how I can continue my contribution. What shall I do next? It seems that I am thinking in a completely different direction than you and need a directional correction.

[vvoovv]

I didn't care about the width of ways or their collisions since then, but this seems to get the main theme for now. However, I can't yet see the relationship to what I did until now.

I thought the triangles can help to avoid a collision with neighbor objects since the triangle share vertices with way-segments and neighbor objects.

[vvoovv]

I see the current task in finding the borders for carriage ways and crossings.

[vvoovv]

I see the current task in finding the borders for carriage ways and crossings.

Which approach do you see as the most optimal one to find the borders for carriage ways and crossings?

[polarkernel]

Which approach do you see as the most optimal one to find the borders for carriage ways and crossings?

I do not yet know. I propose that I first study the literature that we already collected on this subject in order to see, how others solved this problem. These are for instance OSM-Based Automatic Road Network Geometries Generation on Unity by Xingjiang Yu, Procedural Construction of Streets by Marco Zimmermann and maybe also the ideas of A/B Street about how to process intersections. Maybe I can find even more complementary projects and ideas about this. Finally I can already try to do some experiments, so that I will be able to make some propositions.

I have not yet an idea on what can be done with Blender curves and what the input is. Do you maybe know an interesting introduction video on this subject for beginners?

Did you already find some default widths that could be used for ways of different categories?

[vvoovv]

I propose that I first study the literature that we already collected on this subject in order to see, how others solved this problem.

Ok.

[vvoovv]

I have not yet an idea on what can be done with Blender curves and what the input is. Do you maybe know an interesting introduction video on this subject for beginners?

I have to withdraw the idea of using Blender curves to render carriage ways and cycleways. I don't see how to apply a texture to a curve correctly.

The only remaining way to render a street is to generate a mesh.

[polarkernel]

The only remaining way to render a street is to generate a mesh.

OK. Does your proposition for the data structure of ways still hold? Should the intersection areas be represented as triangulated polygons?

[vvoovv]

Did you already find some default widths that could be used for ways of different categories?

Lane width: 3.25 m
Margin width on each side of the carriage way: 1 m
Footway: 3 m
Cycleway: 1.8 m

[polarkernel]

Lane width: 3.25 m ...

Thanks!

[vvoovv]

Does your proposition for the data structure of ways still hold?

No. I'll post the updated data structure later.

Should the intersection areas be represented as triangulated polygons?

I think no triangulation is required for the intersections.

[vvoovv]

Some requirements to the data structure for the border of a carriage way.

It may be required to round the corners. The corners will be rounded also for the neighbor polygon (a side walk or a cycle way).

It may be required to round the corners of intersections. The corners will be rounded also for the neighbor polygons.

It may be required to extend the crossing area towards the neighbor carriage ways to create pedestrian crossing, stop lines, etc.:

[vvoovv]

Proposal for the data structure

Carriage ways, cycle ways and similar ways

A class ExtrudedCenterline derived from the class Polygon is passed to a renderer.

Since the class ExtrudedCenterline is derived from the class Polygon, it has the list vectors which represents the border of the extruded way. Each vector in the list has the reference to the related edge. The edge, as described above, holds references to all its vectors.

Using this structure, it's easy to get a reference to the neighbor objects (other extruded center lines or crossings).

The first vector in the list vectors should be located at the beginning of the related centerline to the right from it.

Intersections

Similarly, a class Intersection derived from the class Polygon is used for intersections.

[polarkernel]

Proposal for the data structure

Sounds quite complicated to me. After a first glimpse of literature, let me sketch my first idea on how to produce such structures. I have fairly respect for this task, as Dustin Carlino says:

Some of the things in A/B Street that seem the simplest have taken tremendous effort. Determining the shape of roads and intersections is one of those problems.

I see the starting point at the section network. From there it is easy to get the positions of the intersections and the way-sections that leave them. I would start with the construction of the intersection polygons (red area). These should get interfaces to the way-sections (green lines) and interface vertices at the position, where the centerline of the original way-segment intersects them (red dots):

I think this would be the most complicated part. Then the centerlines of the way-sections are cut to end a the interface vertices and then be expanded without end caps. This could easiest be done by pyGEOS. These resulting way-polygons should now not intersect each other. To test for carriage way that covers for instance a cycle-way, all edges of the way-polygons could be tested for intersections using our famous Mehlhorn algorithm, which would point on issues to be corrected. I think this would be much faster than to scan each way-segment for neighbors that possibly intersect.

The expanded way-polygon could reference its NetSection class used in the network, which itself references all of its OSM-tags.

But as already mentioned, its just a first idea.

[vvoovv]

The expanded way-polygon could reference its NetSection class used in the network, which itself references all of its OSM-tags.

Did you mean the WaySection class?

[vvoovv]

Shouldn't the interface be located at the red line?

[vvoovv]

The intersections may have the following form (example from manhattan_01.osm):

[vvoovv]

Then the centerlines of the way-sections are cut to end a the interface vertices and then be expanded without end caps.

Isn't extruded a proper term?

[polarkernel]

Did you mean the WaySection class?

Yes. I renamed this class too often.

Shouldn't the interface be located at the red line?

Yes, sure. Badly plagiarized.

The intersections may have the following form (example from manhattan_01.osm):

This will be the most difficult part to solve. Many very complicated cases can be found on the A/B site.

Isn't extruded a proper term?

Why not, as the addon belongs to Blender, where this term is used. Buffered is another name used by pyGeos, Shapely and GIS .

One more addendum to my proposition: When we would start the pipeline with the proposed concept and would see, that cycles would still be required. these could easily constructed. Even dead-end ways (that resulted as spurs) would no more be a problem, as the inner polygon (green) would not degenerate when the streets have an area:

[vvoovv]

I guess PyGEOS is the obvious candidate to generate intersection polygons.

[polarkernel]

I guess PyGEOS is the obvious candidate to generate intersection polygons.

I don't know yet. Do you agree that I follow this new proposition and try first to find the areas of intersections in a reasonable way? If yes, should I better create a new repo, so that the approaches don't get mixed?

[vvoovv]

Do you agree that I follow this new proposition and try first to find the areas of intersections in a reasonable way?

Yes, let's do it.

[vvoovv]

If yes, should I better create a new repo, so that the approaches don't get mixed?

Yes, let's use a new repo.

It's also the time to clean up the list of branches.

I think dev_patt can be deleted. Its code is already contained in dev.

The branch streets contains the code that finds clusters. We can rename it to streets_clusters.

The branch streets_visibility can be renamed to streets_graph_cycles.

[polarkernel]

It's also the time to clean up the list of branches.

I agree. I propose the name for the new repo to streets_intersections and it should be based on streets_graph_cycles, as a lot of code from there could be reused, I think.

[vvoovv]

I've finished the cleanup of the list of branches. Please push the branch streets_graph_cycles.

[polarkernel]

Please push the branch streets_graph_cycles.

Done.

[vvoovv]

Do you think the problem of covering the whole area with contiguous polygons in accordance with OSM data can be solved in principle?

I thought about using predefined widths for streets and then using a kind of editor to adjust the widths of generates streets. The editor should be designed and developed in that scenario.

[polarkernel]

Do you think the problem of covering the whole area with contiguous polygons in accordance with OSM data can be solved in principle?

To the best of my current knowledge, yes. I did a lot of experiments and worked out a lot of first experiences with possible problems. I will present these in some new posts, probably tomorrow.

I thought about using predefined widths for streets and then using a kind of editor to adjust the widths of generates streets. The editor should be designed and developed in that scenario.

Do you think to use such an editor in Blender or offline? As far as I understand, for instance A/B Streets uses a separate offline application to generate the base data.

[vvoovv]

Do you think to use such an editor in Blender or offline? As far as I understand, for instance A/B Streets uses a separate offline application to generate the base data.

I thought about an editor right in Blender's 3D View.