Jump to content
  • Advertisement
Sign in to follow this  
Stainless

Unity Line Creation Techniques

This topic is 713 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

 

Share this post


Link to post
Share on other sites
Advertisement

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Edited by Kylotan

Share this post


Link to post
Share on other sites

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,

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!