Monday 27 June 2016

An Introduction to Procedures

As there is a huge amount to cover I'm going to spread it out over multiple posts.  The first few will describe the technology (engine) and after that I'll cover the tooling (editor).  This will by no means cover all the technical detail, but it should give you a good idea of how it works and what (I hope) it will be able to do.


Currently the engine allows building of procedural models; objects formed of triangles (and lines) and rendered in a 3D viewport.  These are expressed as 'procedures'; collections of modelling and calculation operations that feed into each other forming a network or graph.  The 'inputs' to this are various constant values within the graph and the output is a 'value' corresponding to the generated geometry.
A simple procedure and the resulting model
Each node is some form of fundamental operator (like add or subtract) implemented in code, or it can be another procedure, itself made from operators and procedures.  The term 'operator' will be used to mean either in the context of a procedures content as once placed down they can be treated in exactly the same way.
A multiplication operator feeding into a luminance procedure
Each operator generally has one or more inputs and one or more outputs, which can be connected up to other operators.  An input can only be connected to one output but an output can connect to multiple inputs.  There are several fundamental data types available for information to be passed between operators.  So far we have: Integer, Float, Bool, Colour, Vector, Matrix, String, Frame, and Model Segment.  These last two are explained more below.  Unconnected inputs are considered constants and the value can be explicitly specified.
Operator inputs of various data types
When creating a procedure, you get to define it's inputs and outputs, and their names and types, these then become available for connecting-to wherever an instance of the procedure is placed down.
Procedures represent blocks of functionality and can easily be used to encapsulate and re-use groups of operators.  For example you might build a colour blend procedure out of mathematical operators if a dedicated operator wasn't available or didn't meet your needs.
Bespoke colour blending procedure
The new blend procedure in use


There is a small library of built-in operators implemented already to build procedures from, these are roughly divided into:
  • Mathematical operations - all the usual maths functions.
  • Comparisons and conditional switching - test and flow control.
  • Conversion - e.g. changing type or break-out/re-combine (for multi-element types).
  • Constants - operator inputs are editable constants, but constant operators are useful for sharing values.
  • Modelling - create and manipulate primitives (cube, cylinder, paint, distort, etc).
  • Space defining - subdividing and specifying spaces to be used for containing objects (Frames).

Some of the operators available so far
There are hundreds more of these I need to support (something for a future post), but this is plenty for me to test and prove out the principals.  In fact this current limitation means I have to be inventive and really means I push the capabilities of the procedure system to see what I can achieve.


Currently there are only two triangle primitives (Cube and Cylinder) and two line primitives (Line and Grid).  The only reason I haven't written more yet is that I have managed to achieve a surprising amount with just these.  All the screenshots you can see so-far are mostly built with the cube operator and an occasional cylinder.  As we will see though they do provide a fair bit of control over how each can actually be used.
Once I got to the point where the geometry synthesis was basically working and I started building shapes I found that a large part of building up objects is actually splitting up the space it is going to occupy into smaller spaces.  This happens at many depths and in many different ways.  There are parallels here to laying out elements on a page or in a user interface, so many concepts like centring, distribution, and offsetting apply equally to 3D space. To facilitate this in Apparance I found a data type to describe an oriented cuboid in space was ideal for this.  These I call 'frames' and operations on them form a large part of the object construction process.
Space partitioning operators in use (highlighted yellow)
Starting with a frame describing the location, orientation, and dimensions of the object being created, you break it down into sub-frames until you reach a point where a single primitive fits exactly, at which point you feed the frame into it generating the geometry needed there.  This aspect of modelling needs a post to its self really :)
Geometry generated by a primitive operator is passed around the graph using a 'Model Segment' data type.  This rather esoteric type is just a way of remembering where in the modelling buffers the vertex and triangle information for that primitive has been put.  A 'combine' operator is available to merge two segments of geometry together so they can be treated as one.  All modelling should result in a single Model Segment output at the top level and it is the geometry enclosed within it that will be displayed.
Part of the appeal (to me at least) of procedural generation is parameterisation.  Anything we build this way can have any aspect of its form exposed as a tweakable parameter.  This may just be the desired size of the object, it might be the thickness of the frame on window, the colour of a building's roof tiles, or the probability of a wonky brick in a wall.  In order for a given parameter to affect the modelling process its value will usually need to be massaged into some other form by using mathematical, conditional, and logic operators.


The process of turning procedures into models that can be rendered it called 'synthesis'.  Starting with a root procedure to be viewed in a 3D scene the synthesis engine starts by instantiating it in memory with any input values needed and requests the geometry via the appropriate output.  This triggers instantiation of all the operators within and their interconnections.  Following the 'flow' of the data connections back from the required output and digging down into procedure within procedure all the functionality needed to produce it is executed.  Requests for output values from leaf operators, ones with actual code behind them causes that code to be executed.  Procedures and operators also call upon their inputs which then cause the evaluation to elevate back up to the level above and follow the connections already in place when the containing procedure was evaluated.
Evaluation tree for the table example
Because procedures are instantiated as they are needed, it can support recursion, i.e. a procedure can include instances of itself.  As long as there are 'exit conditions' defined to limit the recursion depth this turns out to be a really useful way to build a lot of structures.  I discovered early on that this can be used to implement arrays of objects by progressively subdividing until the required object size was reached.  I thought I would need array support explicitly but so far recursion has served well in its absence.
A recursive procedure called "Recursive" that includes itself.
Output of the recursion example
To help with scalability and performance, multiple synthesis runs can be performed in parallel on several separate synthesiser instances.
Four synthesisers running in parallel, busy building geometry
Each has its own pre-allocated chunk of memory as working buffer, used in a non-freeing manner and only reset at the end of each run.  This makes allocation of parameters, values, operator state, and any intermediate data extremely fast and all values effectively immutable, simplifying the operator graph evaluation logic.
A breakdown of how memory was allocated during synthesis


Quite a lot to absorb I'm sure.  I'm happy to answer any questions.  Next time I'll talk about the renderer, some of the less glamorous code supporting everything, and how the project is set up.

1 comment: