**0**

# Road graph generator

Started by Tannerd, Jul 09 2012 04:15 PM

4 replies to this topic

###
#1
Members - Reputation: **117**

Posted 09 July 2012 - 04:15 PM

I have a mesh representing the roads of a town and its texture is a png where the non road points have alpha = 0 and the road points have alpha = 1.

I have implemented PD control to move vehicles autonomously either following a line (this needs to be completed though, see below (*) ) or going towards a point.

I need to make a tool (not working in real time during the simulation) that takes the mesh representing the roads and generates a graph and / or lines representing the centre of the lanes of the roads, so that the PD control can follow them in order the vehicles to drive in the lanes and they can perform pathfinding as well.

So far it seems I need only one lane per way (small two ways roads)

Does anybody have any suggestions?

The first idea I had is to use the texture that I have been given to easy understand the segments of the triangles that are on the border of the roads: those sides of the triangles whose corresponding uv map points to pixels having at least one alpha = 0 pixel as neighbour are border sides.

Now that I know what segments are on the border of the roads I can shift them inward (imagine X axis orthogonal to the side of the triangle pointing towards the alpha = 1 region and the correct way is Z = X x Y) by a fixed amount (the half of the size of a lane) and then connect them with the nearest segments computed with the same method for adjacent triangles. I think the connection points will be just the intersection between the lines passing through the segments.

Could this work?

So far it seem that I do not need to implement multiple lanes per way, but how would you generate them? (roughly I am thinking that if there is space I just add a parallel segment but I would need the rules of driving to connect them properly in order to generate a graph that implements the rules of the roads)

(*) so far I compute the error using a line that is represented by a simple equation such as sin(x). I think I will need to compute the distance from a line represented by multiple consecutive segments. The first rough idea is to compute the distance from the lines passing through all of the segments (maybe with some optimizations, but currently this is not a big problem) and using the smaller as the error from the path.

I have implemented PD control to move vehicles autonomously either following a line (this needs to be completed though, see below (*) ) or going towards a point.

I need to make a tool (not working in real time during the simulation) that takes the mesh representing the roads and generates a graph and / or lines representing the centre of the lanes of the roads, so that the PD control can follow them in order the vehicles to drive in the lanes and they can perform pathfinding as well.

So far it seems I need only one lane per way (small two ways roads)

Does anybody have any suggestions?

The first idea I had is to use the texture that I have been given to easy understand the segments of the triangles that are on the border of the roads: those sides of the triangles whose corresponding uv map points to pixels having at least one alpha = 0 pixel as neighbour are border sides.

Now that I know what segments are on the border of the roads I can shift them inward (imagine X axis orthogonal to the side of the triangle pointing towards the alpha = 1 region and the correct way is Z = X x Y) by a fixed amount (the half of the size of a lane) and then connect them with the nearest segments computed with the same method for adjacent triangles. I think the connection points will be just the intersection between the lines passing through the segments.

Could this work?

So far it seem that I do not need to implement multiple lanes per way, but how would you generate them? (roughly I am thinking that if there is space I just add a parallel segment but I would need the rules of driving to connect them properly in order to generate a graph that implements the rules of the roads)

(*) so far I compute the error using a line that is represented by a simple equation such as sin(x). I think I will need to compute the distance from a line represented by multiple consecutive segments. The first rough idea is to compute the distance from the lines passing through all of the segments (maybe with some optimizations, but currently this is not a big problem) and using the smaller as the error from the path.

###
#2
Members - Reputation: **117**

Posted 10 July 2012 - 03:36 AM

At least the first problem seems to have been solved.

I am picking each side of each triangle and checking if there is any other triangle that have the same vertices as one of its side, if yes that side does not belong to the border of the road, otherwise I just add those two points to a list which contains couples of points representing the border of the roads.

Now I need to find out how to compute and save the segments of the lanes.

I am picking each side of each triangle and checking if there is any other triangle that have the same vertices as one of its side, if yes that side does not belong to the border of the road, otherwise I just add those two points to a list which contains couples of points representing the border of the roads.

Now I need to find out how to compute and save the segments of the lanes.

**Edited by Tannerd, 10 July 2012 - 05:58 AM.**

###
#4
Members - Reputation: **117**

Posted 11 July 2012 - 02:34 AM

I guess yes they are freeform approximated by the triangles of a mesh, those roads were modeled on top of a google map fragment. Should I choose a semi-automatic approach? That is once the graph is generated I build a simple GUI to edit the nodes, so that I can add and smooth curves or simplify unnecessary complexity and so forth...

I need also to understand if the graph should represent the actual lanes of the roads (that could be smoothed on run time by a path follower system) or if it should just be a sort of high level graph and then the agents will figure out what the lane to follow is.

I need also to understand if the graph should represent the actual lanes of the roads (that could be smoothed on run time by a path follower system) or if it should just be a sort of high level graph and then the agents will figure out what the lane to follow is.

**Edited by Tannerd, 11 July 2012 - 10:20 AM.**