Future City: Update 5 - The Fencepost Problem

Fence-posts

A lot of structures have a regularity to them that is useful to emulate, whether it be fences, walls, windows, rows of houses, tree, or chimney pots.  As with the fence-post problem you can't implement them as a straight repeat of a single object though since you need one more post than fence panels.

The Fence-post Problem: N panels but N+1 posts.

Before we look at solving this however, we will start simpler; looking at how we can handle instancing of the more-straightforward repeating structures.

Example of a simple array of objects.

Recursion

Apparance doesn't yet support arrays as a data-type, arraying of objects, or any form of looping, but an effective alternative that is supported well is recursion.  Here we can break down a repeating problem into successive; sub-division, geometry instantiation, and recursion, until the space is filled.

Basic recursion used for repeating geometry.
The process of split+generate is invoked on the left split area each time until there is no more to split.

The process of sub-division can be improved somewhat in a couple of ways; first, instead of creating a chain of recursions, one-deeper-per-instance, we can tackle it with successive sub-division and two recursion paths instead.  This reduces the stack depth needed from N to log2 N (or thereabouts).

Improved recursion used for repeating geometry.
Recursion is applied to both parts of a central split until there is no more to split.

The other thing we can do is to wrap up the splitting calculations into helper procedures that make it easier to implement these arrays of objects.  The general problem here is that we need to be able to have our own geometry within the recursion process which is tricky to support.  Instead of having to support embedding of procedures (akin to passing function pointers in code) however, we can provide two procedures, with which we 'book-end' our own geometry generation.  These handle the Splitting Logic, and the Combining Logic needed to implement the array process. The general form for this is:

Layout of a procedure for arraying geometry using the two helper procedures to wrap the recursion and geometry instantiation.

NOTES: Any external parameters the procedure needs (to customise the generation have to be passed down to the recursion calls too.  The Control channel is used to select which of the three outputs are to be combined before returning to the outer procedure, this could be a pair of recursions, or some generated geometry.  A further improvement to this process might be to use all three at once when an odd number of elements are present since we can make the splitting even by immediately instantiating geometry for the centre region.s

Potential further improvement to recursion efficiency.

The Divider

These helper procedures I've named 'The Divider' as it divides up space in one direction into equal size pieces for our procedure to build geometry into.

Basic recursion helper procedure: The Divider (splitting part)

This is used in conjunction with a 'Merger' which handles aggregation of the elements.

Basic recursion helper procedure: The Divider (merge part)

This is a really useful tool to building and distributing content around the world.  For example, when a long thin strip of land is encountered in the business district, multiple buildings are placed in a row instead of a single long thin building.  Here we see the Divider and Merge stages in use in the Business Block procedure that handles this:

Divider approach used to create rows of buildings in the business district.

And here it is in action as the space available changes.

Array of buildings filling a narrow strip of land using the recursive Divider approach.

The Stacker

To tackle the fence-post problem, and some of the more sophisticated use-cases, a significantly more powerful version of the divider approach is needed.  Here are a couple of examples:

This piece of railing can be sectioned up in a couple of ways, either as the classic fence-post arrangement (circular design 'panels' between flower 'posts'), or by treating the flowers a separators between the circular parts and two end pieces connecting to the walls.

These railings can be divided up in a couple of ways.

This building facade can similarly be broken up in to ways, but these are a bit more involved:

This building facade can be divided up in a couple of ways.

Here, however we divide it up we have two end-caps (the corners of the building), but the way the wall/windows are divided up can be approached in two ways:

1. The window sections are wider and include a bit of wall.
2. The wall sections are much cleaner and are present between the end caps and the windows as well as between pairs of window sections.

These requirements can be generalised into the following (optional) sections with what I'm calling 'The Stacker':

1. Start cap
2. Multiple repetitions of:
1. Spacer
2. Object
3. Spacer
4. End cap

This can be constructed in a similar fashion to the Divider, but with more user supplied elements in between the helper procedures.  This happened to turn out to be the most complicated procedure I'd ever built!  I actually tried to tackle this problem a while ago, but decided that it would be impossible without the grouping and notation feature so I set about adding that instead.  I'm glad I did now as notes are used extensively to partition the logic and document the processing involved:

The most complex procedure I've created: 'The Stacker' (splitting part)

This isn't the most efficient implementation, nor the simplest, I'm sure.  But it works, and can be revisited later if it needs speeding up or reducing in size.  I could even be re-implemented in code as a build-in operator if needed.

As with the Divider, there is a corresponding re-combination procedure seen here:

Much simpler companion to The Stacker; the merge part.

As this was a very complicated procedure, and with many combinations of inputs and options it was imperative to have good test cases.  Here we see a large set of instances for most of the various configurations it supports.

Test cases for The Stacker.  Many combinations of the various configurations are tested in one place for easy visual inspection.

Examples

Now we have this powerful tool at our disposal I had a chance to explore what can be done with it.

Wall

A straightforward test case is a wall with regular support pillars and larger end columns.

The Stacker used to implement a wall with regular support and end detail.

Wrapping the different wall elements in a Stacker and corresponding combiner gives us this procedure:

Interesting brick wall structure implemented with the Stacker recursion helper procedures.

Which produces this satisfactory construction.

Wall design constant parameterisation.

Brick Wall procedure expanding to use the space available.

Steel Truss

One of the real test cases I wanted to try out was to build steel-work structures out of girders that can be used as support structures around many industrial components.

Steel structures of the kind I'd like to use in the industrial district of Future City.

More specifically, I want to re-create this configuration:

Example of steel beam configuration I want to produce.

This is made from steel I-Beam sections and has two stacking aspects to it, horizontally we have:

1. (optional) End upright
2. Set of cross-members
1. separated by uprights
3. (optional) End upright

Vertically the cross-members are stacked thus:

1. Cross-members
1. Separated by gaps

This was implemented with a pair of nested procedures, one for horizontal, one for vertical, all contained within a main entry-point procedure.

Nested horizontal and vertical stacking procedures to create steel-work side wall.

Here is a selection of constructs built using this set of procedures:

Random structure variation based around truss, tower, and side procedures.

Steel constructs based around a steel-work side section.

Truss or gantry built from girders.

Close of up construction detail.  As you get closer, the bolts are revealed.

Next

Next I should be able to start building some more interesting structures for the industrial district using all these new-found constructional powers.

Future City: Update 4 - Down To Business

This week I've been developing the business district layout a bit, dealing with a few bugs, experimenting with gradients, optimising the rendering, and adding a few features and fixes to help diagnose problems.  Oh, and it was my birthday too :)

Business

The business district is going to be lots of tall, close-packed skyscrapers with occasional open spaces amongst them.  With the area we are covering there are going to be a lot of buildings, and a lot of geometry.  To deal with this we have to introduce the buildings (and gradually higher detailed versions of them) progressively as we get closer.  Since a 'Manhattan skyline' area of a city tends to be visible from a long way off we are going to have to introduce buildings from quite a distance away.  We can do this gradually, and as long as there are some of the tallest ones appearing early on we should get a good impression of a distant city.

Distant 'Manhattan skyline' effect from larger buildings

At the moment we will just use a simple boxy model for the buildings, which should suffice for distant buildings, but will need to be replaced for the closer ones.  The detail testing/switching logic for the skyscraper uses the building height to judge which detail band they should go in.  I set it up to introduce the tallest ones in a large/distant range, the mid-height ones in the next one and the smallest ones in the closer range.  The small ones can be left until quite close before we even fade them in.  Once the viewpoint is within the city, most of what you should be able to see has been faded in.

Inner city, all building proxies faded in.

Most business district blocks are of a size suitable to house a single building.  If they are a bit long or large still we sub-divide a little more and instantiate a couple of similar buildings.

At the moment we will ignore the connectivity and access situation at the periphery of each block that we saw set up in previous posts.  It's not that we aren't going to use this information eventually, but barriers and division are probably not a big features in a business area.  To postpone this for now I added a periphery clearance space around the edge of each block.  This can be later be filled with open-space furniture (benches, water features, trees, etc).  These will carry the open space blocks in the city in amongst the buildings too.

Clearance around buildings connects with open areas.

Detail Comparison

It proved quite tricky to get my head around how to get the building reveal/distance calculations to work in such a way that it was clear what the effects of the control parameters were.  Sometimes it's very easy to set something up like this and then just 'give up' by randomly fiddling with values until it seems to be working well enough.  The first attempt was like this; the values were too arbitrary and I wasn't sure what effect they were actually having.  By stepping back, thinking about the problem in a slightly different way I ended up with a system that works.  The problem was that we have two values with different meanings to compare; the height of the building and the size of the block they are being instantiated into.  Instead of trying to massage one into the 'space' of the other it is easier to convert both into an intermediate, neutral range.  Turning both into a normalised 0 to 1 range and then comparing them seems easier to calculate and balance.

When should we introduce a distance building?

Since the block size are powers of two, it also seemed a good idea to changing them to a linear value for the purposes of comparison too.  This produced the following stages of building reveal.

Stages of distance skyscraper population, far to near.

Gradient Surfaces

Using a simple box for each building quickly blocked refinement as a geometry from a normal box primitive can't be sub-divided automatically.  This has been fixed before by using the generic rectangular patch procedure (see previous post) which sub-divides and adds some interesting extra surface detail.  Since this is a bit 'blocky' I decided to try to implement a smoother version.

Block vs. Smooth surface patch procedure

Until now, all modelling primitives have only supported painting in a single flat colour (all models use vertex colour to drive their diffuse appearance), so to introduce smoother, gradient based surfaces we need another primitive or paint operator.  I decided that a flat rectangular sheet primitive with corner colour inputs would serve best to keep the amount of pre-processing and complex painting around it in the procedure to a minimum.

Coloured Sheet primitive for creating smooth gradient surfaces

Similar to the generic patch, we will be introducing variations in the colouring as the sub-division happens to add detail.  This time however, it's a bit more complicated as the adjacent pieces need to share colours along their boundaries.  Also, we aren't going to vary a single colour, we are going to blend between two main colours as this helps keep the colours consistent as we divide deeper.  By carrying both a blend factor and a seed value with each corner vertex down through the sub-division process we can ensure that as each edge is divided up and perturbed by the same amount from each side.  We end up with a variation on the mid-point noise algorithm and build up a nice surface detail as we get close.

Increasing sub-divisions of smooth patch procedure (high contrast detail setting)

This provides us with a couple of nice features when applied to the buildings:

• More interesting surfaces (not just flat).
• Fewer edges visible, less blocky
• Even the lowest detail buildings have gentle gradients across them.

Smooth patch applied to low-detail skyscrapers in business district.

Summary

This gives us low-ish detail city buildings, which we will re-visit in the future to fully detail and flesh out.  For now though we are going to look at other district types and get them up to a similar level of detail.

This example demonstrates a couple of significant advantage of the procedural approach to modelling:

1. Re-visiting models to add detail later is a normal part of the process.
2. Upgrading fundamental elements used across your environment will automatically be applied everywhere it is used.
3. Building up your scene breadth first instead of having to work depth first means your scene builds up as a whole, and not piece by piece.
4. You get a working environment sooner, game-play and other disciplines can get to work earlier while the detail is added in parallel.

We shall see these points come up again and again.  They are some of the reasons I like this approach to content creation.

Next

I might do a side-post on the debugging and diagnosis issues I've had this week, but then it's on to the industrial zone!  ..which sounds like something from the Crystal Maze :D

P.S. Cake

Since it was my birthday I thought I'd build some procedural cakes to celebrate.  I'm quite pleased with the result of a day of 'baking'.

Procedural cakes to celebrate.

Future City: Update 3 - Blocks & Detail

Blocking Out

After digging down through the zones and district types, we have some large city regions set out.  We now want to break them down into city blocks so that we can start looking at where buildings will go.

The process is similar to the zone sub-division and uses most of the same process and procedures, but this time the design constants are dependent on the district type.  For example: residential and leisure areas are probably in smaller blocks than industrial and space-port blocks, with business somewhere in the middle.  We can experiment with other differences later on, say, favouring longer thinner leisure areas for parks or squarer business areas suitable for skyscrapers.

Block design constants, parameterised by district type

Whitebox

For testing purposes I added a simple cuboid as a placeholder building to each block.

Simple white-box building added to each block for test purposes

This is just a proportion of block size for now, with the height chosen randomly.  In reality a block may eventually have multiple buildings, but for now I just wanted to get a feel for how the city would look and investigate the detail levels at different distances.

View across 'white-box city'

Detail

Apparance is built around the premise of bands of detail extending out from the viewpoint, each higher detail one built based on re-synthesising the lower detail procedures.  As we start to build more detail into the city we need to begin setting up the integration with the detail management in the engine.  Since each re-synthesis is performed using sub-procedures with exactly the same input parameters, something else must provide the ability to change their behaviour as different detail results are required.

Re-synthesis of procedures for successive depths in the detail hierarchy.  How do they know what detail level to generate?

As the scene is progressively refined to give more detail, the blocks the world is divided up into get smaller.  It is this that a procedure can check to decide what level of detail to generate itself at.

For our city blocks we will switch between an extremely low detail (flat) rendition for far in the distance, to our normal block procedure as their size decreases.  This will have the effect of gradually populating the area with more buildings as we get closer.

Switching out the blocks in the distance for a simpler representation.
The normal blocks intercepted and replaced depending on our detail hierarchy block size.

The Distant Content procedure we are using will make use of a common modelling primitive; a rectangular patch with automatic detail improvement.  This also uses this detail switching to break down and subdivide its surface into smaller pieces to add detail and reveal intricacy as you view mode closely.  Here we see an example of it increasing in detail.

Successive refinements of a generic rectangular patch, introducing more detail and some variation.

Putting this all together and we get a rather satisfying reveal of detail as we move across the city.

Detail transitions and reveal testing across white-box city

Diagnostics

Setting up the detail management in a scene is quite tricky at the moment.  I am still exploring how it can best work and what can be done to improve the user experience.  To help understand what the engine and your procedures are doing a lot of diagnostics displays options are available.

Various diagnostics settings and statistics for a view-port and scene rendering.

These have been added gradually during the development of the engine and this week I've had to revisit them and add a few features to help fix problems with the detail tracking and blending system.  These features are going to be essential in debugging procedures and understanding what the engine is doing with them so it's worth having a look at them now.

Display Modes

There are several colourising modes to visualise various mesh rendering information.

Colourising of meshes to visualise state and show information spatially

The scene node hierarchy can be visualised; a progression of hues used to colour each depth level.

Visualisation of the scene node hierarchy, coloured by depth

The detail range bands and various transition boundaries can be shown to check where the blends are supposed to be happening.

Visualisation of the detail tier ranges, coloured by depth

Focusing

Most of these displays, as well as models and meshes can be selectively singled out using sliders to help close in on specific issues in the scene.  For example, information about, a particular model, in a particular node, in a particular tier of the scene hierarchy can be viewed:

Focusing in on a specific model in the hierarchy

Looking at the node diagnostics panel, we see that this model can't be refined any further because the procedures don't have any sub-procedures small enough to fit in the next scene node size down.

This model in this node can't be subdivided, so no more detail can be generated in this area.

For more information about the procedures in question and how the analysis for resynthesis worked out we can trigger a re-synthesis and analysis of a model which also allows us to see the evaluation tree (via an external GraphViz step).

Here we see the refinement capture analysis failing at our temporary content procedure.

Here it is clear that all the leaf procedures are un-refinable and need more work (which we knew as this is a test procedure of limited ability).

Debug Camera

Using the debug camera and some of these diagnostics overlays we can see the detail reveal effect 'from the outside'.  Here the details is added and revealed around the view-port after a scene reset.  As progressively more detailed versions of the scene are synthesised we can see the extent of each expanding.

Detail regeneration and reveal after scene reset as seen from external debug camera position.

Next

These recent posts have been fairly dry and focusing on dividing up spaces rather than the more interesting process of filling them with things.  We will start seeing some more exciting things soon, I promise :)

Future City: Update 2 - Get Yourself Connected

This time we look at creating interesting boundaries and useful connectivity information between all our city zones.

We want a city with interesting connectivity between zones

Connections

It is as much the interconnections as the spaces in an environment that make a place interesting. Now the zones are laid out we need to look at how they are connected. As we have a number of limitations in how we implement this I'm going to use a fairly basic connection model similar to one I have used before which was based on having a single connection pathway between adjacent areas, like each side of a room having at most one door. The algorithm had the following rules (expressed in terms of rooms and doors):

1. For your starting 'room', specify a door on each side (as desired).
2. Decide where to split based on door positions (i.e. don't split down a doorway).
3. When you split an area into two, always add a door into the new wall.
4. Recurse (go-to step 2) for both sides.

This produces a map where all the four outer doors are guaranteed to be connected, and you can reach every generated room.

Previous connectivity test, all rooms remain connected, various in-fill rooms.

When is a door not a door?

For our city, the door/wall terminology is going to be used to mean something slightly different:

1. A door corresponds to a region of free travel between areas, be it pedestrian, or vehicular.  This can mean either both sharing the same flat height level at the boundary, or that they both guarantee to match some underlying landscape shape at the boundary.
2. A wall corresponds to a barrier between areas, this can take several forms and may or may not have some sort of minimum barrier height.  This could be a wall, fence, steep drop, ditch, or just allow the back of a building to sit along that edge.

Barrier 'wall' (red) and open 'door' (green) segments along the side of an area.

This has an important effect on the splitting constraints; in that I want to allow splitting the open part in two by a boundary.  This will introduce more interesting topologies and should create greater connectivity than the 'single path to exit' algorithm above.

Splitting the area in two but with splitting of an opening allowed.

This does come at a cost though as the calculations needed to maintain connectivity are in-fact more complicated.  I decided to try and track access back to the four starting sides more thoroughly this time so that when splitting, we can work out if we have the option not to add a door, again increasing the connection graph variety.

Also, remember, we are splitting the city up into zones at the moment, these are fairly high-level, and quite large.  The blocked boundaries aren't going to be massive long walls, but opportunities for the next stages of subdivision to use them in different ways to partition the city up into lots of interesting spaces.  Similarly, a long gap may not imply a continuous connection, only that there be some form of connection along the length of each area.  Different areas may decide to achieve this in different ways, be-it steps, a ramp, a wall with an archway, and so-on.

No Structures

A quick aside about structure support in Apparance.  At the moment there are only a handful of fundamental data types you can pass around.  It is feasible to support arbitrary collections of these wrapped up into custom data types (structures) that can be passed around together more easily using single connection points and wires.  This would make propagating things like the access parameters and connectivity information much, much easier and also allow us to modify and add to this information without the huge amount of rewiring it would otherwise need.  Unfortunately, as it stands, I can stretch what I have and make a few design compromises enough that proper structure support isn't enough of a priority.  Something I have mused over a lot, definitely elegantly implementable, and definitely a future feature.  For now though we will pack out information into existing types.

To door or not to door?

Access

The presence of an opening in an side is represented by two horizontal values, the position of the left edge and the position of the right edge.  The absence of an opening is represented by either it's left edge being past the right end of the side, or the right edge bring past the left end of the side.

Opening specified by position of left and right ends.  Fully blocked side specified by either both at the right end of the wall or both at the left end of the wall.

To pass this information around we'll pack it into a Vector3, one of the fundamental types that is used to represent a 3D vector.  It has three floating point values X, Y, and Z of which we use X and Y to be the left and right edges of the opening.  The Z value isn't used yet, but will be needed when we want to encode some height information into the opening.

Packing of edge connectivity into a Vector3

Each area (or room) consists of four sides, each potentially accessible via openings, and so we need to track and pass around four of these Vector3 access values.  As a convention, these are referred to as West, East, South, and North (or their initial), and in that order (lower X axis, upper X axis, lower Y axis, upper Y axis).

West, East, South, and North sides of an area.

Connectivity

We also need to track connectivity available via each side of an area as we sub-divide.  Since we only need to track whether we can reach each of the four outer sides when we only need four bool values, or four bits of data.  This is much simpler information and rather than passing round a value for each side we can pack the information needed into a single integer as a bit-field.

How we pack information about which side of our area can provide access to which side of the city into a 32 bit integer.  A bit value of '1' means yes, we can get to it, and '0' means no we can't.

We will need add a few new bit-wise operators to support the packing and unpacking logic.  These are bit shift, AND/OR, and maybe a bit test operator too.  We can then build packing/unpacking procedures from these.

Connectivity packing and unpacking procedures

NOTE: I've been playing with clearer labelling of some of the simpler operators.  They can now have either large text, or characters from the Symbol font.  This combined with blank IO names and title suppression produces some nice compact visual representations.  You'll see some more below.

Implementation

We are now ready to implement this new functionality on top of the work we did last time splitting our city into zones. To start with I factored out the splitting process into own procedure, this helps manage the complexity of the already fairly complicated procedure that decides whether we should split and which way.

The newly factored out Split procedure in place

Do the splits

New split point, side calculation, and access logic are all in their own procedure now. To make the splitting logic simpler we abstract away the orientation of the split by 'normalising' the incoming area information and then 'de-normalising' it back afterwards.  This allows us to implement the split logic once and be able to use it for both horizontal and vertical splits.  The four sides are termed Left, Right, Bottom, and Top instead of the W.E.S.N. directions we use normally, to help distinguish normalised from de-normalised.

The split operation.  Mostly consisting of the logic to help us treat either orientation of split the same way.

Where to split

The split itself is broken into two parts, where to split, and then how to split.

First we need to work out where across the area are we going to split.  Since we are allowing splits across openings this is technically only limited by the need to ensure we don't create any area too small (min zone size design parameter).

Neat & tidy, tidy & neat

At this point it would be nice to also limit the minimum feature size we create during a split.  Since an arbitrary split could be any distance from an arbitrary opening edge then we can create very tiny openings and short walls.  It would be good to reduce this effect and we can achieve it in two ways.  One is to snap to some overall grid spacing, and second to snap to the edges of the openings in the two walls we are intersecting. The Split Point procedure handles all this for us.

Deciding on where to split the area and generating access information for either side of the split.

When splitting an area into two halves, the connectivity is going to be affected by whether there is an opening in the new wall.  To decide on this we need to work out where each new area is already connected to and use this as the potential new connectivity across the new divide.  By checking to see if each side of the divide includes the opening from the two sides being intersected and combining their connectivity with the connectivity of the opposite wall we get a connectivity value from each side of the split.

How to split

Deciding on the dimensions of an opening in the new wall is fairly straightforward.   We do however need to check whether we need to force an opening though to maintain connectivity between the city outer walls.

Side splitting and connectivity update.

Results

This update was implemented in two stages, first the access generation (wall/door) for each area, then the connectivity calculation and sub-division side opening decision making.  Here is an example where you can clearly see areas that end up disconnected from each other due to no connectivity management.

Disconnected regions (highlighted) present before connectivity checks were implemented

Once the connectivity system was in place it all started working properly.  Here is a selection of city zone layouts with connectivity information diagnostics display enabled.

Examples of a fully connected city

Next

Next we will start breaking down each of our zones into city blocks.  The process is similar to before, but each district type may have different requirements as the layout of each should differ to keep things interesting.

We will also starting thinking about where significant buildings are going to be placed since we will soon require a skyline silhouette to appear as we approach the lower detail end of our city.  Development is a process of adding detail, top-down, exactly analogous to approaching the city gradually from a distance.  Think about what you expect to see, and when.