Fill Shape Generator Lab

This is not a game. This is a little experimental lab for generating/evolving a bunch of arbitrary 3D shapes to match an arbitrary target 3D shape. Maybe it is an abstract impressionist/brutalist sculpture generator too?

This little experimental lab was made for ProcJam 2018, a jam about making something that makes something. Source Code is included:

Source Code (Unity Project, in a BitBucket git repository)

In the demo lab, you can choose the target shape and the shapes to fill it with, as well as fiddle with a number of parameters and choose from several algorithms for generating the right configuration of shapes.

Generation Algorithms Explored

Genetic/Evolutionary:

This is an aggressive winner-take-all variation of the Genetic Algorithm (Survival of the Fittest). The algorithm initially creates a population of random fill configurations (placements of fill shapes). Each fill configuration is scored based on a fitness function, to find the best fill configuration. Mutated versions of the best fill configuration are used to populate the next generation of fill configurations, that replace the original fill configurations.

Three options for fitness scoring are available:

• Raycast: Invisible measuring lasers are projected from random positions outside of the target shape and directed inwards to find how far it takes to hit the target shape, and how far it takes to hit any fill shape. The more of a match between the distance to the target shape and distance to the fill shapes, the better the score.
• Volumetric: Random points in the space are checked to see if they are contained inside the target shape and whether they are contained inside any fill shape. The more of a match between the result of each check (both are inside, or both are outside), the better the score.
• Volumetric With Physics: Same scoring as above, but the fill shapes are now physics rigidbodies that can bump into each other and try not to overlap. For point checks that are not contained inside the target shape (points that are supposed to be empty), a temporary "pusher" sphere is added to push fill shapes away from them. You can turn on/off the pushers and see what happens.

In all of these, the higher the sample count is set to, the higher the accuracy, but the slower the simulation runs.

These genetic algorithms can take quite some time to reach a satisfactory solution. There is some simulated annealing, where the mutation rate decreases over time to allow for finer and finer tuning, but you can play around with the mutation rate multiplier to finesse it.

Recursive Block Fill:

This is a relatively dumb and simple algorithm. It repeatedly subdivides a block shaped search zone to see whether it should be filled or be recursively subdivided. To check if a zone is filled, it samples a bunch of random points within that zone to see what portion of them are filled. If it is greater than a certain threshold, then it is considered filled and a fill block is placed there  to match that zone's dimensions.

If it is not filled, then that zone is subdivided along the longest dimension into two smaller search zones and the search continues. If the maximum depth of subdivision is reached, or if the zone is too small, then that zone will not be subdivided any further, and will be filled with a real block if it meets a certain threshold.

Afterwards, similar adjacent blocks are combined together into larger blocks to reduce and simplify the total number of blocks.

Note: These algorithms make use of Unity's C#-job system for multithreading purposes. It may run very slowly on machines with fewer cores and/or without hyperthreading.

Third Party Attributions: Suzanne (Monkey Head Mesh) exported from Blender, Teapot mesh exported from Blender.