Future City: Update 11 - Block Interfacing

Progress on Future City has been slowed by web-site and release preparation work at the moment.  I've split my time about 2:2:1 between Web site, Future City, and Alpha Release preparations.

January push towards Web Site, City demo, and Alpha Release.

This split in attention as well as the pressure of the approaching alpha release means blog posts have been slower forming.  Let's just squeeze out a quick update on the Future City progress...

Future City

At the moment I've been focusing on the support of variable elevation across the city, with each city block having its own height.

Example of blocks with shared connectivity but height discontinuities

This feature results in rather complicated requirements at the interfaces between blocks as well as complicating the process of sub-dividing up the space within them.  As such, it's been quite slow progress working out (a) exactly what is required, (b) how to perform this, and (c) how to implement this.

Requirements

Based on the previous connectivity work which sub-divided the city up into districts/zones and finally blocks, we have already decided on what the connectivity between each block looks like.

Now we need to decide on what the content of the block should be such that it is possible to guarantee that adjacent, separately generated content aligns properly, functions as a seamless transition, and looks plausible.

Inputs

We have the following information about each block boundary:

• Block location/bounds/size.
• Access along each side (left/right of opening within any barrier present).
• Follow the underlying landscape shape, or both share flat ground level at a given height.
• Connectivity via each side (to the outer most city sides).
• Variation seed to drive arbitrary design decisions.

Outputs

From this we need to populate the block with rectangular sub regions.  The main problem we are trying to solve here is to transition from a boundary with zero, one, or two accessibility transitions along each side into spaces for content to go that all have single accessibility along each side, these being simpler requirements to satisfy.  Thus the outputs are of the form of Content Spaces with the following properties:

• Bounds size, orientation and location
• Surface height within the space (or if we are to follow the landscape)
• Is it an interfacing piece, i.e. responsible for handling transition to neighbouring block interface? (Edge - one interface along block boundary, Corner - two interfaces along block boundary, Side - three interfaces along block boundary)
• If not an interface, then an interior piece, with same type all round (flat or landscape)
• For each boundary interface: Specific flat elevation or landscape following. Do we 'own' this side (are responsible for interfacing geometry). Is this a barrier, i.e. will access be blocked? Is there a barrier to the left/right that we may need to provide transition geometry for?

Test Rig

Since there are a lot of combinations to test in forming this system it is worth generating a set of 'unit tests' with clear visualisation of the inputs and outputs.  By creating a hierarchy of test procedures we can quickly generate tests for all the major side and access combinations.

• Ownership - all, none, adjacent, opposite
• Surfaces - all landscape, all flat, mixture
• Access - Closed corners, all open, all closed (bar one), some on left, some narrow, mixture

Unit tests for a lot of the block interfacing cases

For cases where a specific issue is being resolved there is the option to switch out all but one test scenario.

Example test rig showing corner results produced

Algorithms

I spent a lot of time in Excel playing with block boundary examples and possible approaches.

Playing with block algorithm ideas in Excel

From this I've come up with a lot of ideas, but they seem to be heading towards this sequence of calculations:

First pass at the content space and interfacing algorithm

There are bound to be some changes as implementation proceeds, but this is a good starting point.

Lists

Structured Data

The amount of structured information and variability in generated output finally became too much and I had to stop to add some functionality to help support this.  Previously where several properties about a single thing needed to be conveyed through several procedures it had to be passed individually, and explicitly.  This leads to this specific flavour of spaghetti:

A specific flavour of spaghetti: arrays of connections

The algorithms that were forming to perform the interfacing and content-space generation were heading towards an awful lot of this.  From the requirement analysis above we can see each block has at least seven properties that go together, and each potential output content space has at least six.

Traditionally these would be encapsulated in structures, where a single type is used to express an explicit collection of typed data.  This is something that Apparance will natively support in the future, but it's quite a lot of work, especially on the tooling side where composition/decomposition of structures needs to be handled elegantly.

Variable Quantities

Another aspect of the block interfacing implementation problem is that there are several places where we need to pass a variable number of structures.  At the moment there is no concept of this and we would have to pass a fixed (maximum) number of structures (as individual properties) along with an additional flag expressing whether it was in use.  This forms a very, very unwieldy situation where all sorts of operations, such as combining two variable sized collections, become incredibly complicated, expensive and error prone.  We really need some form of list or array to handle this.

Solution

Both these prospects are really going to cause too much of a headache to work on the already complex problem, so we need support to help this.

Looking at other language for inspiration, we find that both these problems can be addressed by using lists of dynamically typed objects.  If a list happens to contain all the same type, then it is effectively a traditional list or array, i.e. a variable sized collection.  If a list happens to contain a fixed number, of different typed elements then it can be used as a structure.  Adding support for lists as just another base data-type to Apparance is fairly straight-forward and then means we can have lists of lists, or put another way, lists of structures.

Implementation

The List data type was added along with an initial set of basic operators to support what we would need, as follows:

• Append - take a list and add another element (any type).
• Get - index a list, returning the element value (any type).
• Set - replace a value at a specific index with a new value (any type).
• Count - query how many elements are in the list.

Part of the implementation that took a bit of effort was that I wanted type information to be maintained with them as the lists are constructed.  With this, a lot of validation can be performed during synthesis that would catch problems that would otherwise be very difficult to diagnose and have potential to crash the engine.

Whilst a bit tricky to implement, lists are proving very useful so far and make a lot of the block interfacing problem much more pleasant to work with.

Passing structures and collections around as lists

I am even now using them in the web site building procedures for all sorts of things.

Progress

I'm about half way through the Block Boundary -to- Content Space processing system and have promising results so far.

Some of the content space generation results so far

I'll post more results as I progress.  In the mean-time I have an Alpha Release to get out!

Future City: Update 9 - Apartment Construction

Apartments

I've been thinking about how to build interesting residential apartment buildings, that look more futuristic than just boxes with windows.  A few ideas come to mind:

• Surface objects  - balconies, air-con units, ducting, etc.
• Surface projections - bits that stick out, and in-turn have windows/etc.
• Multi-part buildings - intersecting parts in a cluster, at different heights.
• Non-right-angle intersections - should be do-able.
• Buildings on buildings - large rooftops can recursively have smaller/similar buildings on top.
• Styling - design seed can keep same style among a cluster but different between

We'll see how far this gets us.

Building Units

I started on the apartment buildings by properly subdividing a building block into obvious parts: windows, faces, friezes, separators, corners, parapets, roof, etc.

Procedure injection points on a general building structure.

This can later have a variety of proper alternatives and parts switched in and out to give them their final look.  I wanted the buildings to support intersection, so I added 'opening' parameters on each side, spending some time getting the various combinations of opening needed working.

Rig to test support for openings in the sides of buildings. 'Unit testing for procedures' in a way.

Two main ways to intersect building faces occurred to me:

1. Clipping - Intersect, working out where the join is and just filling each part with the usual facade (window grid, etc), making some changes to the edges to fit better.
2. Culling - Intersect, but this time just cull any windows that would become split where the join should bee (replacing them with basic wall).

Clipping has the limitation that you need to intersect at quantised positions otherwise the windows beside and above the intersecting building won't line up, but Culling means you will get areas with no windows.

I thought I'd try clipping first, and with some calculation I was able to get the intersection working.

The clipping approach in action.  Windows scale to fit space.

To support arbitrary angle intersections though the quantising requirement is going to be really hard to meet, so I also implemented the culling approach for comparison.

The culling approach in action.  Windows are removed when not enough space.

Seeing these in operation show's up the main pro's and con's.

The main differences between the clipping and culling approaches to building intersection.

On balance I think the culling approach will be less messy, especially with proper surface materials and objects.

Proper Facade

Switching the placeholder geometry for more interesting design produced some promising results:

Basic design variation examples

Next

 Now I need to look at arranging these together in interesting ways for use in the city:

• Generating building clusters to fill the city blocks.
• Populating the surfaces with proper features.
• Adding some LOD support for full city use.

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.