PDA

View Full Version : Procedural road generation ?



Lowercase
01-09-2008, 04:39 PM
I would like to generate a random road map, thirst in 2D, then extrude on a 3d heightmap.

the main problem is, i can't find a satisfying algorithm, i tried perlin 1d and bezier curve... I searched without success on vterrain.org

Do someone know about that ?

I don't know if i'm in the right forum, if so, excuse me

Robert Kosek
01-09-2008, 07:17 PM
Okay, you have either one of two questions. One I can help you with, the other I can't.

You either want:
1) Procedural road texture generation
2) Procedural path (aka, road) generation

The difference being 1 is virtual and in memory only, and the other is a texture. I can't help with the texture, but I can give some advice about the procedural paths.

chronozphere
01-09-2008, 07:33 PM
Also very important. What do you want the road to look like??

Should it be a road with some smooth curves in it? Should it have sharp corners? Should it go up and down through the landscape? Any T-Junctions? Or do you want to generate a network of roads, or prehaps all the roads of a whole city?

We need more info. ;)

Lowercase
02-09-2008, 01:09 PM
i'm really sorry for the lack of information..

I was talking about a "network of roads" like Simcity or GTA.

many thanks for your interrest.

PS: I have just found an article on http://www.citygen.net/

chronozphere
02-09-2008, 03:11 PM
Ah.. In that case i have a suggestion. :)

You could use voronoi diagrams. Check:

http://en.wikipedia.org/wiki/Voronoi_tessellation

You can implement an algorithm (like the sweep line algo here):

http://en.wikipedia.org/wiki/Fortune%27s_Algorithm

It takes a set of center-points and divides the space into regions. Each region has one center. It creates nice mosaic patters. You may want to use this. You could let the regions be the building, parks or whatever and the borders between the regions could be the roads.

I would like to implement this myself one day.

Hope this is usefull. :)

Lowercase
03-09-2008, 08:11 AM
I'll give it a try, but there are at least 2 problems with it (if I understood correctly) :

* the diagram is open on it's edges
* the center of each region need tobe calculated before (so that there's no acute angle)

but it's a good start, thanks[/list]

chronozphere
03-09-2008, 01:58 PM
* the diagram is open on it's edges

I'm not sure what you mean. :?


* the center of each region need tobe calculated before (so that there's no acute angle)

I guess you can just pass a big array of points to the algorithm, without any extensive pre-processing. I can imagine you want to check the distances between the points and delete the close ones, so that the points are nicely distributed over the area.

Unfortunatly, i cant help you with the actual implementation. I think fortune's algo can be implemented without a lot of problems. You have to check if it's suitable for your purposes and if it can deliver the information you want. :)

Lowercase
03-09-2008, 02:51 PM
excuse me, i have a little english..

and i don't have the exacts words for geometry.

i was meaning that on the edges of the drawing, the lines are endless

Lowercase
03-09-2008, 08:18 PM
Well ... This is what I undestood :

1) Sort each point by X ascending
2) for each point, make a triangle with the point n, point n +1, point n+2 then calculate the barycentre of this triangle. So if other points are ouside the circle of center=barycentre and distance=barycentre to any edge of triangle then you're alowed to use this triangle.

It's more or less delaunay algorithm which is dual to voronoi

I still don't understand how to draw voronoi diagram.

Do someone has any documents on how-to contruct it ?

chronozphere
04-09-2008, 06:28 AM
Hmmm... just a guess:

1> First, generate a set of delaunay triangles by using an array of vertices (that will be centers of the regions in the vonoroi diagram)
2> Second, calculate center points for every triangle (by interpolating it's vertices).
3> Then, pass all these points to the algorithm again (points used in step 1 and the points calculated in step 2).
4> Delete all edges and triangles that connect to any of the vertices that were passed in step 1.

So what you have left, are the vertices and edges (conflict lines) that seperate the regions. And that's you voronoi diagram.

I could be wrong about step two; Instead of interpolating the three vertices of a triangle, you could also calculate the center of the triangle's circumscribing circle.

Again, it's just a guess so i cannot give you any guarantee it will work. As far as i can see it should work. I'm into computational geometry, that's why i can tell you this info. I would like to test this hypothesis and write a test app. Unfortunatly school occupies too much of my time, so i can't do that for now.

Hope you can get this working. :)

Lowercase
04-09-2008, 06:30 PM
I need to practise a little more... here is my result for delaunay's algorithm.
http://img152.imagevenue.com/loc890/th_53001_delaunay_122_890lo.JPG (http://img152.imagevenue.com/img.php?image=53001_delaunay_122_890lo.JPG)

Edit : I found my problem, my formula to compute the center of each triangles is wrong

that's a little better now
http://img41.imagevenue.com/loc695/th_60844_delaunay2_122_695lo.JPG (http://img41.imagevenue.com/img.php?image=60844_delaunay2_122_695lo.JPG)

chronozphere
04-09-2008, 08:57 PM
Ah looking good. :)

Are you using a sweepline approach now, or something else? I'm very interested in this stuff, and i would like to know more about your implementation and progress.

I still see one little glitch in your second image. One edge is missing (check the middle top of the image). And i see that your polygon is not convex. There are alot of caves who's vertices could be connected to form new triangles. This is no immediate problem, but i still like to know more about your implementation so i might be able to help you with that.

Few day's ago, i implemented delaunay triangulation using the "incremental" approach. :) Check this page:

http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c8901

I would like to know about other methods. I know there is a "Divide and conquer" method and maybe a sweepline method. Check the wikipedia page on delaunay triangulation. :)

Lowercase
05-09-2008, 05:33 PM
That's great !

I have a better result now !

http://img218.imagevenue.com/loc436/th_35513_delaunay3_122_436lo.JPG (http://img218.imagevenue.com/img.php?image=35513_delaunay3_122_436lo.JPG)

Thanks for the source, if only i was able to read a little much better C, it would be great.

I will be away for a couple of days, so I won't update until next week..

chronozphere
05-09-2008, 10:16 PM
Hi..

It's not about the C source. It's about the little piece of pseudo-code on that page. It gives you an idea how the algorithm works. I implemented incremental delaunay just with that pseudocode.

Good luck.

Lowercase
15-09-2008, 11:46 AM
here's another try..

http://img136.imagevenue.com/loc992/th_79050_voronoi_122_992lo.JPG (http://img136.imagevenue.com/img.php?image=79050_voronoi_122_992lo.JPG)

NecroDOME
17-09-2008, 10:03 AM
Looks nice. Looking forward to see more results.

Lowercase
20-09-2008, 01:45 PM
I still have problems computing a convex hull, so i'm trying to implement quick hull algorithm.

i think i have some problems with precision.

here's a screenshot :

http://img17.imagevenue.com/loc953/th_18198_qhull_122_953lo.JPG (http://img17.imagevenue.com/img.php?image=18198_qhull_122_953lo.JPG)

Lowercase
20-09-2008, 01:48 PM
I still have problems computing a convex hull, so i'm trying to implement quick hull algorithm.

i think i have some problems with precision.

here's a screenshot :

http://img17.imagevenue.com/loc953/th_18198_qhull_122_953lo.JPG (http://img17.imagevenue.com/img.php?image=18198_qhull_122_953lo.JPG)[/url]

chronozphere
20-09-2008, 03:37 PM
I've found this page on convex hulls:

http://geometryalgorithms.com/Archive/algorithm_0109/algorithm_0109.htm

There is a nice list of algorithm's listed, and some of them are explained. Hope this helps. :)

michalis
20-09-2008, 09:47 PM
You can take a look at my old implementation of the Jarvis algorithm for convex hull (https://vrmlengine.svn.sourceforge.net/svnroot/vrmlengine/trunk/kambi_vrml_game_engine/3dgraph/convexhullunit.pas). For description of Jarvis algorithm see e.g. http://en.wikipedia.org/wiki/Gift_wrapping_algorithm, it's probably the simplest and still quite good in many situations convex hull algorithm.

Lowercase
21-09-2008, 08:04 AM
the algorithm i used come's from this page :

http://www.cse.yorku.ca/~aaw/Hang/quick_hull/Algorithm.html

in pseudo code :


Input = a set S of n points
Assume that there are at least 2 points in the input set S of points

QuickHull (S)
{
// Find convex hull from the set S of n points

Convex Hull := {}
Find left and right most points, say A & B, and add A & B to convex hull
Segment AB divides the remaining (n-2) points into 2 groups S1 and S2
where S1 are points in S that are on the right side of the oriented line from A to B,
and S2 are points in S that are on the right side of the oriented line from B to A
FindHull (S1, A, B)
FindHull (S2, B, A)
}

FindHull (Sk, P, Q)
{
// Find points on convex hull from the set Sk of points
// that are on the right side of the oriented line from P to Q

If Sk has no point,
then return.
From the given set of points in Sk, find farthest point, say C, from segment PQ
Add point C to convex hull at the location between P and Q
Three points P, Q, and C partition the remaining points of Sk into 3 subsets: S0, S1, and S2
where S0 are points inside triangle PCQ, S1are points on the right side of the oriented
line from P to C, and S2 are points on the right side of the oriented line from C to Q.
FindHull(S1, P, C)
FindHull(S2, C, Q)
}

Output = convex hull

the result is not convex

http://img132.imagevenue.com/loc825/th_84121_qhull1_122_825lo.JPG (http://img132.imagevenue.com/img.php?image=84121_qhull1_122_825lo.JPG)

http://img212.imagevenue.com/loc383/th_84126_qhull2_122_383lo.JPG (http://img212.imagevenue.com/img.php?image=84126_qhull2_122_383lo.JPG)

chronozphere
21-09-2008, 11:39 AM
You should make a "step" function in your program so you can execute the algorithm step by step. I expirimented with that approach and it works pretty good when you are implementing algorithm's or developing them.

In your case, you might want to render some lines and debug info to your canvas, before the next "FindHull" call. You could make a "Draw" routine, which draws all points and lines (PQ) and is called at the end of the FindHull function. Then you could add a Sleep(1000) call, and run your app.

You will see your algorithm compute the convex hull, step by step. You could also let the user decide when to execute the next step (by pressing some key).

It can be hard to debug algo's like these, but with this debug trick, i'm sure it will be alot easier. ;)

Good luck.

Lowercase
21-09-2008, 01:23 PM
after a little nap here is the result of quickhull :

http://img139.imagevenue.com/loc945/th_15488_qhull_final_122_945lo.JPG (http://img139.imagevenue.com/img.php?image=15488_qhull_final_122_945lo.JPG)

it seems to work fine now