Saturday, August 13, 2011

Found a very impressive blog: "Procedural World"

Despite experimenting with procedural worlds for years I only recently came across an excellent blog that I would heartily recommend anyone interested in this area takes a look at:

"Procedural World"

http://procworld.blogspot.com/


"Following one man's task of building a virtual world from the comfort of his pajamas. Discusses Procedural Terrain, Vegetation and Architecture generation. Also OpenCL, Voxels and Computer Graphics in general."

The breadth of task undertaken, the undeniable quality of the results and the fact that it's very much live and in progress make this one to watch for me.

Building Placement Revisited

Although the building lot generation system I described in my earlier post did produce results, the quality of those results was far from ideal. Despite the time spent on it and the various techniques tried the lots it produced were neither very well distributed, controllable in formation nor very practically shaped. Rather than soldier on into procedural architecture generation with such ill suited foundations I decided to have one more attempt at cracking the problem, and I'm very glad I did.

Looking at it after a break of a few weeks not working on the project gave me a valuable fresh perspective and I realised that maybe the whole chart subdivision plan was flawed, maybe there was a better way. Rather than abandon charts altogether though I came up with a new way to use them - rather than splitting them up to try and make lots I thought it might be interesting to start with tiny "seed" lots placed in locations and with orientations I already knew to be sensible then apply some sort of iterative growth algorithm to let them fight it out in a sort of survival of the fittest manner.

The best starting position for this free-for-all seemed to be placing a seed lot half way along any chart edge longer than some minimum threshold. This not only ensured the lots would follow the roads exactly but also made it easy to determine the building front side. Each seed lot is a small square only a couple of metres in size, their initial placements in my test city can be seen here:

Seed points for lot generation
With these seed positions set the system then repeatedly iterates over each in turn attempting to grow them a small amount in each of the three directions not adjacent to the road. By growing each only slightly each time the lots all expand pretty evenly to fill the available space. Growth in a particular direction only stops when that edge of the lot hits another lot, an edge of the chart that contains it or if it has grown too far beyond the length of the chart edge that created it. Lots also stop growing in depth if it would cause them to be too much deeper than they are wide as it's rare to find many buildings significantly deeper than they are wide - the actual aspect ratio limitation can of course be tweaked.

Should a lot run out of space before it reaches the minimum size threshold required to place a building on it the lot is flagged as invalid and other lots allowed to grow into it's space if required. Once all lots have grown as much as possible the process is complete.

After a dozen iteration the above seed lot layout produces this completed result:

After 12 iterations no more lot growth is possible
It's immediately obvious that this new system produces a far more ordered and sensibly laid out set of building lots. They are all nice and rectangular, are oriented neatly along the roads while also using up most of the available space.

The image below illustrates where the invalid lots that didn't survive the cut were located:

Lots in red are too small for buildings and are discarded
Although all were rejected because they weren't large enough to put buildings on, you can see a couple have had their space partially used by other valid lots to maximise their own area.

One final check that is also performed is that building lots larger than a certain size are subdivided along their width into a number of sub-lots that meet the size criteria.  This maximum size is a function of the distance from the population centre so building lots nearer the centre of the city are allowed to be larger than those in the suburbs.  In the next image lots in blue are the result of subdivision in this way:

Lots in blue are the result of subdivision of larger lots
I'm not sure whether to keep this step or not, I think it depends on the variety of building that the architecture system will be able to produce - if believable large suburban buildings can be generated (shopping malls or sports centres perhaps, possibly large mansion type houses) then it would make sense to keep some large plots for their placement.  For now though I am keeping things aimed at houses in the 'burbs.

Placing my simple building place-holder object on these new lots and giving them heights based upon their distance from the population centre gives what I think is a fairly decent looking impression of a city for such a graphically simple representation:




Adding some road geometry with a number of lanes based upon the generation number of the road in the road network generation system and some basic pavements gives some other pleasing results:



Overall I'm quite happy with the new system and am definitely much happier about moving on to look at procedural architecture with this better foundation.  It shows if nothing else that if your instincts are telling you that a system is not up to the job, it's often best to listen to them!

A Note on Texture Filtering

This is just a short note to highlight the visual impact that mip map generation and texture filtering methods can have on a final rendered result. It's not rocket science and will be common knowledge to many, but I felt this was a nice clear example of how significant the effects can be and worth sharing.

I've recently been playing around with procedural city and road generation which has of course led to rendering of road surfaces for which I am using a trivially simple programmer art texture:

Source Road Lines Texture
Even though I knew that find detail on textures viewed at extreme angles are always troublesome, feeding this through the normal mip map generation code with the existing trilinear texture filtering however produced a surprisingly disappointing result:

Uniform Weight Mip Maps, Trilinear Filtering
As you can see, the white lines in the road vanish very quickly with distance as their light coloured texels are swamped by the dark road surface around them during mip map down sampling - not at all realistic and bad enough for me to take a second look. The first thing was to look at the mip map generation code to see if it could be persuaded to keep more of the detail that I cared about. Current each mip map level was being generated using a naive 2x2 box filter with uniform weights:

lower_mip_texel = (higher_mip_texel1+higher_mip_texel2+higher_mip_texel3+higher_mip_texel4)/4;

very easy, very fast but also very bad at keeping detail. There are many better filters out there with varying quality/performance tradeoffs but I thought it worth trying a quick and simple change to weight the pixels by their approximate luminosity, calculated by simply averaging each source texel's red, green and blue channels clamped to a chosen range:

higher_mip_texel_weight = Clamp((higher_mip_texel_red+higher_mip_texel_green+higher_mip_texel_blue)/3, 50, 255)
lower_mip_texel = (
    (higher_mip_texel1*higher_mip_texel_weight1)+
    (higher_mip_texel2*higher_mip_texel_weight2)+
    (higher_mip_texel3*higher_mip_texel_weight3)+
    (higher_mip_texel4*higher_mip_texel_weight4)/
        (higher_mip_texel_weight1+higher_mip_texel_weight2+
         higher_mip_texel_weight3+higher_mip_texel_weight4);

This then favours brighter texels which will be more visible in the final render. Using this code to generate the mip maps instead of the uniformly weighted filter produced immediately better results:

Luminosity Biased Mip Maps, Trilinear Filtering
While the white lines are now visible far more into the distance they become disproportionately fat as the lower mip level texels cover more and more screen space. There's not much that can be done about this as however we filter the texture when making the mip maps we are either going to end up with no white lines or bit fat ones.

The next step then is to stop using trilinear filtering at runtime and instead switch to anisotropic filtering where the filter kernel shape effectively changes with the aspect of the textured surface on screen so the GPU can for example filter a wider area of the texture in the 'u' axis than it does in the 'v' and has more information for choosing the mip level to read each filter sample from. Returning to the original uniformly weighted mip maps where the lines disappeared so early but switching to anisotropic filtering produces noticible better results than either attempt so far:

Uniform Weight Mip Maps, Anisotropic Filtering
and finally for good measure using the weighted mip maps with anisotropic filtering:

Luminosity Biased Mip Maps, Anisotropic Filtering
Not as dramatic effect as when switching to weighted mips with trilinear filtering but still an improvement and the best result of all.

So why not use anisotropic filtering all the time? well it comes down to compatibility and performance, not all legacy GPUs can support it although most modern cards can and even on cards that do there is a performance cost as the GPU is having to do significantly more work - the effects speak for themselves though and going forward I expect it will become the default setting for most games to avoid over-blurry textures as objects move away from the near plane.

A Tale of Two Thousand Cities

Last post I talked about the perhaps not so interesting topic of data generation and caching, not a subject many people can get very excited about, but this time I want to talk about something I think is far more interesting.  City Generation.

I’ve been interested in procedural landscape/planet generation for at least ten years, and over that time have seen at least dozens if not hundreds of landscape projects produced by other people out there who share this interest.  One thing many of these projects have in common however is their landscapes however pretty tend to be fairly devoid of human infrastructure.  One reason is it’s generally easier due to their inherent fractal nature to generate decent looking mountains, valleys and even trees and grass than it is to produce realistic roads, railways, towns and cities.  Heightfield generation for landscapes is also a well covered topic with many professional and amateur research papers and articles on the subject – not so much on infrastructure simulation.

I’m as guilty of this as anyone else – none of the several landscape projects I’ve created in the past could boast anything particularly man made, no roads, no bridges, no buildings or at least none that were arranged in a manner more sophisticated than randomly dotted around on flat bits of ground.

So I thought it about time I got stuck in to what I consider to be a very interesting problem – that of procedural city generation.  A tricky problem to be sure but that is of course what makes it interesting.


References

As with embarking upon any other problem, Google is your friend and after a little digging and reading I turned up a number of resources full of ideas on how cities can be generated.  I’ve listed a few here that I have found interesting here which should provide an introduction to anyone wishing to take this subject further:
There are also various commercial, open source and experimental projects to be found on the net, probably the best known commercial product is the heavyweight City Engine (http://www.procedural.com/cityengine/features.html) while independent projects such as  http://www.synekism.com are also worth a look (a city simulation video game focused on dynamically generated content. The project was started is currently maintained by three university students in Canada)

First Things First

Of course before a city can be generated I need to know where to put it in the world – I do have an entire planet to play with here.  Eventually I would like to have a system something along the lines of:
  • Select a number of random points on the planet’s landmasses that are at least a given distance from each other
  • Group clumps of nearby city points into political entities – these will form the countries
  • Create Voronoi cells around these point groups – add a little noise and hopefully we have political boundaries for countries
  • Use A* or other pathing algorithm to form primary road routes between each city point and it’s neighbours
  • Generate cities
However that’s all still on the drawing board so for now I’m just picking points at random that aren’t too close to each other and not too close to water.  Simples.

Laying Out The City

The approach I'm taking is to first generate a road network for the city, then to find all the bounded areas enclosed by the roads (I am calling these "charts") before subdividing these charts into convex "lots" each of which will ultimately receive a building type chosen based upon city parameters and lot placement.

The road network is made up of two types of entity, "road segments" and "junctions".  The starting point for generation is a set of one or more junctions placed randomly within the central area of the city, each of which has between two and five connection points onto which road segments can be added.  A loop then continually looks at any junctions in the road network that have connection points without roads attached and tries to add a road segments onto each of them.  In addition to adding road segments onto junctions it also looks at any road segments that are only connected at one end - either to a junction or to a preceding road segment - and tries to add another road segment or junction on to that segment.

Make sense?  Effectively each iteration of the loop causes the road network to grow by one step, each step either adding a road segment onto a previous one, adding a junction onto a previous road segment or adding a road segment onto a previous junction.  Each road segment is given a "generation" number, the ones created from the initially placed junctions are generation zero and then every time a junction is added on to the end of a road segment which then spawns further road segments that aren't continuations of the original road these child segments are given a higher generation number, 1, 2, 3, etc.  This generation number can then be used later when deciding on the type of road geometry to create - generation #0 could be dual carriageway for example, generation #1 main roads and generation #2 narrower secondary streets.

Proximity constraints are applied at each step to prevent roads being created that would be too close to existing roads or junctions, and connection tests are made to see if an open road end is close enough to a junction with an open connection point to allow the two to be connected.  The amount of variation in road heading also changes with generation and distance from the centre of the city - so low generation roads tend to be straighter while high generation (i.e. minor roads) tend to wriggle around more creating the suburbs.  The amount of variation also increases as roads are further from the city centre.

To illustrate the process, these three images are sequential representations of the generation of one city's road network:




In these images the Green roads are generation zero, Yellow is one, Blue is two, Magenta is three and Red is four.  You will see that at certain points it appears to skip a generation (a red road directly from a blue one for example) - this is a result of a road segment from the intermediate generation being created then removed due to a proximity constraint violation but then the cause of the violation in turn being later removed due to a violation of it's own allowing a new road of a later generation to replace the original.

Once no more roads or junctions can be created due to proximity constraints or distance from city centre checks the process terminates.

Charting it up

Once the entire road network has been created the next step is to find all the enclosed areas (which I call "charts") which will eventually provide the lots for buildings to be placed on.  To do this I first use Andrew's Monotone Chain Algorithm to find the convex hull that encloses the entire road network, tracing around from any exterior road vertex with this then produces one big chart enclosing the outskirts of the city.  Tracing around from all other uncharted vertices in turn then adds a number of additional charts each representing an enclosed area of the city.

The charts produced from the above road network look like this:


As you can see each chart represents a connected area of the city entirely enclosed by roads or the city boundary.  They are pretty much all concave though and hard to work with further due to this complexity, so the next step is to break these charts down into convex "lots" onto which individual buildings can be placed.  There are several ways this can be done, and I tried a few of them to see which worked best.

First I tried combining "ears" of the charts into convex regions.  Ear clipping is a common algorithm for triangulating complex polygons and involves finding sets of three adjacent vertices where the vector between the first and third vertex doesn't cross any other edge of the polygon, effectively forming a corner or "ear" - you keep doing this until you have no polygon left which as long as there aren't any holes is guaranteed to occur.  The downside of this approach is that you end up with all sorts of random shapes many of which are narrow slivers or shards not very well suited to building lot usage.

Next I tried finding pairs of vertices in the polygon that were as diametrically opposite as possible while having a vector between them that didn't intersect any other polygon edge.  The thought was that this would continually chop the polygon roughly in half producing more even lot distribution but in practice the shapes produced were no more regular and still not suitable.

Finally the solution I settled on was to find the convex hull of each chart (again using Andrew's Monotone Chain) and from this find the vector representing the hull's longest axis.  This was done by summing the length of each edge into buckets each representing an angle range (10 degrees in my case) then taking the angle from the bucket with the longest total edge length accumulated.  The chart was then rotated by this angle to align this longest axis with the Y axis before finally clipping the chart into two pieces across the middle in the X axis to form two new charts.  Repeatedly doing this until the individual charts are small enough to count as lots produces a set of output charts many but not all of which are convex - I decided to classify the convex ones as building lots and the remaining concave ones as greenfield lots for parks, car parks or other non-building purposes.

The results of this lot subdivision on the above city looks like this:


Here the green lots are suitable for building, the red lots are concave and thus classified for parks or similar and the blue lots are isolated from the road network and not suitable for use at all.  Removing the isolated lots and tweaking the colours produces this:


Here the grey charts are suitable for building with the green ones representing parks - the red charts have been classified as being too small to be considered further - in practice these would probably end up being simple tarmac areas suitable for street furniture.  Although it's far from perfect I'm not too unhappy with the result - it could be better, I would like to see more consistently useful lot shapes for example but it may be good enough to be getting on with.

The final step is taking the road network and lots and generating renderable geometry from them, after that's it's building selection and construction which I haven't got to yet.  This is how the road and lot network looks in the engine for now anyway:


And that's it as it stands.  The city generator is deterministic and seeded from the city's world position (and in the future it's physical/political parameters) so I've many cities all around my planet of varying sizes and complexity, the next step is building generation and placement.  Procedural architectural generation is a whole new bag, so it's back to Google for me...