I am writing a flight simulation game, and as you all know, this is a massive task for a single person to take on.

So I have had to make some hard decisions to make. One of them was the terrain system.

It would have been nice to have an open world , whole planet, terrain system, but with one coder that would have killed the project. So I have decided to use maps from a modding community (with their permission of course).

The maps have a fairly simple format. One bitmap defines the terrain heights. Another the terrain type and other files contain locations and objects.

The types map uses 5 bits for the actual terrain type, and index into a texture array basically. The other three bits are HasMajorRoad, HasMinorRoad, and HasRailway.

These are the bits I need some help with.

I don't want to do a Lego style system for the roads. Basically you look at all the cells around the current one to create an index into an array and drop in the road section that matches. This would mean all roads exit a terrain cell at the same points and would make everything very unnatural.

So I scanned the bitmap and extracted all the cells with roads, collecting them into point lists. I then used a modified version of the Potrace algorithm to convert the point lists into line lists.

At first glance that seemed to work.

[attachment=32808:roads_1.png]

It is only when I zoomed in I realized I had a problem.

[attachment=32809:roads_3.png]

It seems the Potrace algo actually traces around the point list rather than along the point list.

It's even worse when I add minor roads and rail ways

[attachment=32810:roads_4.png]

Has anyone seen any good ways or converting a point list into a line list?

I don't have time to re-invent the wheel.

Cheers guys.

As I understand it, the Potrace algorithm isn't (from what I can see) designed to output points but vectors, and if you're extracting points out of that file then you may well find that the lines in the file don't match the points. Not all types of splines pass through their control points - Catmull Rom splines do, Bezier curves do not.

But therein probably lies the solution for you - if you're sure that the points you have are accurate, then you want to generate splines that pass through them, and Catmull-Rom splines are one approach. I'm not sure of a general purpose solution for a set of points rather than for a list of them but if you can generate a graph from the points by checking for adjacency, you can isolate individual routes from that graph, and generate splines from each route.

After the first pass of my code I have some 600 "lines"

These lines are actually a list of points which are connected and therefore can be classed as part of the line.

This is the same thing as vanilla potrace does.

After that I want to convert this list of points into a set of splines or straight line segments that pass through the centre of these points.

The reason is I want to use the data not just for map drawing. I also want the same data to be used to generate geometry in the in the 3D engine.

If I use the output above, I end up with all my roads and railways being one pixel wide, which in game terms is 200 M

I don't know many roads 200M wide, and certainly none in 1940. :)

The solution is going to be selecting parts of the point list and converting them into splines.

However trying to convert the whole point list into a single spline won't work.

So it's some technique for working out which parts of the point list can be converted into a spline I am looking for.

If the issue is determining which bits are individual splines, I'm sure there's a graph theory algorithm for that, but that's not my area of expertise. If you have a raster representation then you can assume each road point with only 1 adjacent road point on the grid is the end of a road, with 2 adjacent roads is a regular road section, and if there are 3 or more adjacent roads, it's a junction. I imagine a slow algorithm for solving this would be:

1) Find all unconnected subgraphs

2) For each subgraph, start with a junction or end point, perform a depth first search to fill the whole graph, adding points to a list as you traverse them, and setting that list aside as a 'route' whenever you reach another junction or end point - each list will be a junction/end, 0...N regular sections, then another junction/end.

3) All these routes are your points for each spline - and you can have special cases for the end points if you need.

To generate 2D road geometry from a 1D line, I'd just create 2 extra lines parallel to the original line, one either side, spaced a road's width apart. The area between those lines is your road. You probably want to generate parallel lines for each segment, remove the extra points at the segment joins by replacing the points with a new averaged point, and then you have 2 new splines for the whole road which can be triangulated.

Generating 3D geometry from the spline is trivial, I already have code for that.

I really don't want to go down the route of generating road sections on a per grid basis. It's simple, and works, but looks rubbish. I just set a bit in a byte for each sector adjacent to the current one. This gives me an index into an array of prefabs I can just drop onto the world.

It just looks like exactly what it is. A 1990's solution.

Graph theory is a good idea, I'll do some reading in that area and see if anything pops,

Okay, I think I understand what you mean now. The Potrace algorithm is for finding objects which means it creates lines that delineate a 2D region, rather than creating 1D lines.

What you probably want is a skeletonization or thinning algorithm - that is designed for extracting lines from a raster image. If you provide a grid where each square is road or not-road, the skeletonisation should be able to return a list of points from that, which you can then create geometry from. Sadly I don't have a great recommendation of a library or tool to use for that.