### Dielectric breakdown model (DBM)
> [!NOTE]
> Related to [Diffusion-limited aggregation (DLA)](#diffusion-limited-aggregation-dla) and [Laplace equation](#laplace-equation).
_Image credit: Ellak Somfai - [Dielectric breakdown model in 3 dimensions](https://warwick.ac.uk/fac/cross_fac/complexity/study/msc_and_phd/miniprojects/archive/miniprojects2009/0670234-100209-miniproj08-somfai-dbm.pdf)._
Generalization of [DLA](#diffusion-limited-aggregation-dla) that models how an electrical discharge propagates through an insulating (dielectric) material, producing the branching patterns known as [Lichtenberg figures](https://en.wikipedia.org/wiki/Lichtenberg_figure) - the same kind of patterns seen in lightning, [fulgurites](https://en.wikipedia.org/wiki/Fulgurite) in sand, and burn marks left by high-voltage discharge.
Rather than growing a cluster from randomly-walking particles like DLA, DBM solves Laplace's equation for the electric potential around the growing cluster at every step, then extends growth from whichever boundary site has the strongest local field.
A single exponent, η (eta), controls how sharply growth concentrates at high-field points: at η = 1 the model is statistically equivalent to DLA, higher values produce sparser and more needle-like branches, and η = 0 produces smooth, non-fractal growth.
_Algorithm at a glance:_
_\* indicates a potential simulation parameter_
1. Seed growth with an initial charged point or shape, and hold a distant boundary\* at zero potential (fully "discharged").
2. Solve for the potential field filling the space around the cluster - either by repeatedly relaxing a grid (each free cell settles toward the average\* potential of its neighbors, over some number of iterations\*) until the field stabilizes, or by approximating it with a batch of random walkers\* launched from the boundary and recording where each one first touches the cluster.
3. For each empty cell touching the cluster (a "candidate" site), calculate its local field strength as how much its potential has dropped relative to the cluster's fixed potential.
4. Raise each candidate's field strength to the power of the growth exponent\* (η), normalize the results into probabilities, and randomly pick one (weighted by those probabilities) to add to the cluster.
5. Repeat, resolving the field again after each new addition.
_Key terms:_
* η (eta) - exponent controlling how strongly growth favors high-field regions; DLA is the η = 1 case of DBM.
* [Lichtenberg figure](https://en.wikipedia.org/wiki/Lichtenberg_figure) - branching discharge pattern that DBM was originally developed to explain.
* Rigid and elastic bond models - DBM variants used to study electrical and mechanical breakdown (fracture) networks.
_Articles:_
* [Dielectric breakdown model](https://en.wikipedia.org/wiki/Dielectric_breakdown_model) on Wikipedia
* [Lichtenberg figure](https://en.wikipedia.org/wiki/Lichtenberg_figure) on Wikipedia
* [Fractal Dimension of Dielectric Breakdown](https://ifisc.uib-csic.es/~tomas/MFCS/EdenDLA/dielectric_break.pdf) (PDF) by L. Niemeyer, L. Pietronero, and H. J. Wiesmann. The original 1984 paper introducing DBM as a generalization of DLA.
_Code projects:_
* [Lichtenberg-Figures](https://github.com/epa058/Lichtenberg-Figures) - DBM-based simulation of Lichtenberg figure formation, accounting for the stochastic nature of dielectric breakdown
---
### Diffusion-limited aggregation (DLA)
> [!NOTE]
> Related to [Dielectric breakdown model (DBM)](#dielectric-breakdown-model-dbm) and [Laplace equation](#laplace-equation).
Process in which particles of matter stick together (_aggregate_) as they chaotically move (_diffuse_) through a medium that provides some sort of resistive (_limiting_) force. As these particles clump together over time they form characteristic fractal branching structures known as [Brownian trees](https://medium.com/r/?url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBrownian_tree).
Very interesting macro-structures begin to emerge at around the 1-10 million particle range in 3D, but in order to get there you'll need to be smart about your rendering pipeline and make use of optimized code in a performant language or environment (C/C++, CUDA, GLSL shaders, Houdini, etc).
_Algorithm at a glance:_
1. Add initial point(s) or shapes to seed growth.
2. Add a number of walker particles.
3. In each tick of the simulation, do the following:
1. Move each walker a small amount in a random direction.
2. If any walker particle is colliding with a fixed/clustered particle, convert that walker particle into a fixed/clustered particle.
_Key terms:_
* Walker - randomly-moving particle not attached to any other particle
* Cluster - group of multiple particles stuck together
* [Brownian tree](https://en.wikipedia.org/wiki/Brownian_tree) - name of characteristic branching structure that emerges
_Articles:_
* [Diffusion-limited aggregation](https://en.wikipedia.org/wiki/Diffusion-limited_aggregation) on Wikipedia
* [Diffusion-Limited Aggregation, a Kinetic Critical Phenomenon](http://ancient.hydro.nsc.ru/MPP_Specourse/witten81.pdf) (1981) by Thomas Witten and Leonard Sander. The article that started it all! _Note: visit your local library or a university library and ask a librarian if they can help you get free access!_
* [Diffusion-limited aggregation: A kinetic critical phenomenon?](http://www.thp.uni-koeln.de/krug/teaching-Dateien/SS2012/Sander2000.pdf) (2000) by Leonard Sander. Follow-up to the original article.
* [Simulating 2D diffusion-limited aggregation (DLA) with JavaScript](https://medium.com/@jason.webb/simulating-dla-in-js-f1914eb04b1d) by Jason Webb
* [DLA - Diffusion Limited Aggregation](http://paulbourke.net/fractals/dla/) by Paul Bourke
* [Diffusion-Limited Aggregation](https://softologyblog.wordpress.com/tag/diffusion-limited-aggregation/) by Softology
* [Pushing 3D Diffusion-Limited Aggregation even further](https://softologyblog.wordpress.com/2017/05/22/pushing-3d-diffusion-limited-aggregation-even-further/) by Softology
_Code projects:_
* [dlaf](https://github.com/fogleman/dlaf) (C++ w/ Boost) by Michael Fogleman 
### Differential growth
Process that acts on continuous chains of nodes connected by lines using simple rules (attraction, repulsion, alignment; not unlike boids) in order to produce undulating, buckling forms that mimic or simulate meandering rivers, rippled surface textures of plants/seeds/fruits, space-filling behaviors of worms, snakes, intestines, and much more.
_Algorithm at a glance:_
2D:
1. Begin with a set of nodes connected in a chain-like fashion to form a path (or multiple paths). Each node should have a maximum of two neighbors (one preceding, one following).
2. In each tick of the simulation, for each node:
1. Move node towards it's connected neighbor nodes (attraction).
2. If node gets too close to _any_ nearby nodes (connected or not), move it away from them (repulsion).
3. Move node towards the midpoint of an imaginary line between it's preceding and following nodes (alignment). It wants to rest equidistance between them with as little deflection as possible.
3. In each tick of the simulation, evaluate the distances between each pair of connected nodes. If too great, insert a new node between them (adaptive subdivision).
4. At some interval, insert new nodes in the chain to over-constrain the system and induce growth. The bends and undulations that emerge are a result of the system trying to equalize the forces using the rules defined in step 2.
_Articles and discussions:_
* [Exploring 2D differential growth with JavaScript](https://medium.com/@jason.webb/2d-differential-growth-in-js-1843fd51b0ce) by Jason Webb
* [Differential line](https://inconvergent.net/generative/differential-line/) by Anders Hoff (inconvergent)
* [Sheparding Random Growth](https://inconvergent.net/2016/shepherding-random-growth/) by Anders Hoff (inconvergent)
* [Differential Mesh Growth discussion thread](https://forums.odforce.net/topic/25534-differential-curve-growth/) on od|force forums
* [Organic Labrynths and Mazes](http://www.dgp.toronto.edu/~karan/artexhibit/mazes.pdf) (PDF) paper by Hans Pederson and Karen Singh
_Code projects:_
* [2D differential growth experiments](https://jasonwebb.github.io/2d-differential-growth-experiments/) by Jason Webb ([Github repo](https://github.com/jasonwebb/2d-differential-growth-experiments))
* [Differential line growth with Processing](http://www.codeplastic.com/2017/07/22/differential-line-growth-with-processing/) by Alberto Giachino
* [Real-time differential growth in JavaScript](http://adrianton3.github.io/blog/art/differential-growth/differential-growth.html) by [Adrian Toncean](https://github.com/adrianton3)
* [Differential Line Growth](http://www.entagma.com/differential-line-growth/) by Maritz Schwind of Entagma
* [Differential Growth](https://codepen.io/MAKIO135/pen/EwYPmb) by Lionel Radisson
_Creative projects:_
* [Floraform - an exploration of differential growth](https://n-e-r-v-o-u-s.com/blog/?p=6721) by Nervous System
* [Floraform Chandelier at World Expo 2017 in Astana, Kazakhstan](https://n-e-r-v-o-u-s.com/blog/?p=7702) by Nervous System
---
### Eden growth model
_Image credit: Silvio Costa Ferraria et al - Figure 1 from [Pitfalls on the determination of the universality class of radial clusters](https://www.researchgate.net/figure/color-online-A-small-Eden-cluster-with-6000-particles-The-border-is-depicted-in-red_fig1_1858140)_
Created by Murray Eden in 1961 ([paper](https://projecteuclid.org/ebook/Download?urlId=bsmsp%2F1200512888&isFullBook=False&isResultClick=False) (PDF)), this is a type of surface fractal growth process where material randomly accumulates on the _boundary_ of clusters. Sort of like DLA but without all the empty space between branches. Thought to be a good way to model certain kinds of bacterial and lichen growth.
_Algorithm at a glance:_
_\* indicates a potential simulation parameter_
1. Seed growth with a single occupied cell (or shape).
2. Track the list of all empty cells touching the cluster - its "perimeter."
3. Pick one perimeter cell to fill in - either uniformly at random\*, or weighted by how many cluster cells it touches\* - and add it to the cluster.
4. Update the perimeter list: remove the cell just filled, and add any new empty cells it exposed.
5. Repeat.
_Key terms:_
* Perimeter / boundary sites - the empty cells adjacent to the cluster; the pool of candidates for the next growth step.
* Growth-site weighting - how a perimeter cell is chosen each step; picking uniformly among all perimeter cells produces a different texture than weighting by how many cluster neighbors a cell has.
* [Kardar–Parisi–Zhang (KPZ) universality class](https://en.wikipedia.org/wiki/Kardar%E2%80%93Parisi%E2%80%93Zhang_equation) - broad category of surface-growth models that share the same statistical scaling behavior; the Eden model is a classic example used to study it.
_Articles:_
* [Eden growth model](https://en.wikipedia.org/wiki/Eden_growth_model) on Wikipedia
* [A Two Dimensional Growth Process](https://projecteuclid.org/download/pdf_1/euclid.bsmsp/1200512888) by Murray Eden (original 1961 paper)
_Code projects:_
* [Eden_cluster_growthtests](https://github.com/Cup-cake-lover/Eden_cluster_growthtests) - Python implementation with a repulsion factor to model canopy shyness in trees
---
### Particle Life
> [!NOTE]
> Related to [Primordial Particle System](#primordial-particle-system) and [agent-based modelling](#agent-based-modelling).
_Image credit: detail of the example results from [Particle Life Simulation](https://github.com/hunar4321/particle-life) by Hunar Ahmad_
Family of particle systems in which every particle belongs to one of several _types_ (usually drawn as colors), and every ordered pair of types is assigned its own attraction or repulsion strength. Those strengths are held in a small matrix that can be filled randomly and then tuned by hand, which makes the system extremely easy to explore - each new matrix is effectively a new set of "physics" to play with.
Crucially, the matrix does not have to be symmetric: green can be attracted to red while red is repelled by green. That asymmetry is what lifts the results beyond simple clumping, producing cell-like clusters with membranes, wandering "creatures" that chase and flee each other, orbiting pairs, snaking chains, and blobs that pinch off copies of themselves - all within one parameter space.
Originally explored by Jeffrey Ventrella as _Clusters_ and later popularized under the name "Particle Life" by CodeParade in 2018, this is one of the most approachable emergent systems to implement, since the core is just a nested loop over pairs of particles.
Not to be confused with the [Primordial Particle System](#primordial-particle-system), which uses a single kind of particle steering by neighbor _counts_ - here the effects depend entirely on multiple types treating each other differently.
_Algorithm at a glance:_
_\* indicates a potential simulation parameter_
1. Randomly place a number\* of particles, assigning each one of `k`\* types (colors).
2. Build a `k × k` matrix\* of attraction values (commonly in the range `-1` to `1`), one for each ordered pair of types, where negative values mean repulsion. Random matrices are a good starting point, and the matrix need not be symmetric.
3. In each tick of the simulation, for each particle:
1. Find nearby particles within a maximum interaction radius\*.
2. For each neighbor, compute a force: strong repulsion when closer than some minimum distance\* (so particles cannot collapse into a single point), and beyond that, an attraction or repulsion scaled by the matrix value for the pair of types involved. The exact shape of the falloff curve varies between implementations and has a big impact on the results.
3. Add the summed forces to the particle's velocity, apply friction/damping\*, then move it.
4. Wrap or bounce particles at the edges of the world\*.
_Key terms:_
* Types (or families/colors) - the classes of particle whose interactions the matrix describes
* Attraction matrix - `k × k` table of per-pair attraction and repulsion strengths
* Minimum distance - radius inside which particles always repel each other
* Maximum radius - distance beyond which particles ignore each other, usually enforced with a [spatial index](#spatial-index)
* Friction - velocity damping, without which the system heats up and flies apart
_Articles:_
* [Clusters](https://www.ventrella.com/Clusters/) by Jeffrey Ventrella - the original system, along with an [introduction](https://www.ventrella.com/Clusters/intro.html) to the ideas behind it
* [Clusters and Particle Life](https://softologyblog.wordpress.com/2018/11/08/clusters-and-particle-life/) by Softology - traces the lineage from Clusters to Particle Life and walks through the parameters
_Videos:_
* [Particle Life - A Game of Life Made of Particles](https://www.youtube.com/watch?v=Z_zmZ23grXE) by CodeParade
* [Clusters: An Asymmetrical Particle System with Emergent Patterns](https://www.youtube.com/watch?v=h3U8jSUIjME) by Jeffrey Ventrella
* [Particle Life Simulation](https://youtu.be/0Kx4Y9TVMGg) by Hunar Ahmad - code walkthrough of an implementation that fits on a page
_Projects:_
* [Particle Life](https://particlelife.app/) by Veronica Lin, based on [particle-life-sim](https://github.com/veronicalynn0528/particle-life-sim).
* [Particle Life Simulation](https://github.com/hunar4321/particle-life) (C++, JavaScript, and Python) by Hunar Ahmad - includes browser demos in [2D](https://hunar4321.github.io/particle-life/particle_life.html) and [3D](https://hunar4321.github.io/particle-life/particle_life_3d.html)
* [Particle Life](https://particle-life.com/) (Java) by Tom Mohr - desktop app using parallel processing and spatial partitioning to handle large particle counts ([Github repo](https://github.com/tom-mohr/particle-life-app)), built on a reusable [framework](https://github.com/tom-mohr/particle-life)
* [Particle-Life](https://github.com/HackerPoet/Particle-Life) (C++) by CodeParade - the implementation from the video above
---
### Physarum
_Image credit: [Sage Jenson](https://www.sagejenson.com/physarum) ([@mxsage](https://www.instagram.com/mxsage/))_
Technique for modelling the observed behaviors of the slime mold [physarum polycephalum](https://en.wikipedia.org/wiki/Physarum_polycephalum) using [agent-based modelling](#agent-based-modelling). Originally described in 2010 paper by Jeff Jones, and more recently popularized by artist Sage Jensen (@mxsage), this algorithm produces highly dynamic and organic-looking webs that can seem very life-like and biological in nature.
_Algorithm at a glance:_
_\* indicates a potential simulation parameter_
1. Consider the simulation space as a grid, with each cell storing a number representing the combined strength of pheromones left by the agents who have passed through it.
* Pheromones in each cell diffuse at some rate\* to neighboring cells as they decay (at some rate\*) in each step of the simulation.
1. Add a set of points, each representing an autonomous [agent](#agent-based-modelling).
1. Each agent leaves a trail of decaying pheromones behind by adding a number\* to the cells it passes through.
1. Each agent senses the total phermone strength of cells in front of it defined by a distance\* and a field of view angle\*.
1. An agent will gradually adjust its direction\* to steer towards the cell(s) with the most pheromones.
1. Render the trails (not the agents) by mapping the pheromone strength number in each cell to a range or gradient of colors.
_Articles:_
* [Characteristics of Pattern Formation and Evolution in Approximations of Physarum Transport Networks](http://eprints.uwe.ac.uk/15260/1/artl.2010.16.2.pdf) (PDF) by Jeff Jones - original paper
* [Physarum Simulations](https://softologyblog.wordpress.com/2019/04/11/physarum-simulations/) by Softology
* [Physarum polycephalum](https://en.wikipedia.org/wiki/Physarum_polycephalum) on Wikipedia
* [Understanding the Physarum Simulation](https://denizbicer.com/202408-UnderstandingPhysarum.html) by Deniz Bicer ([breakdown thread](https://x.com/ojelibalon/status/1820839257793233164))
_Code projects:_
* [Simulating slime mold with WebGL](https://kaesve.nl/projects/mold/summary.html) by Ken Voskuil
* [physarum](https://github.com/nicoptere/physarum) (JavaScript with ThreeJS) by Nicolas Barradeau
* [Physarum](https://github.com/DenizBicer/Physarum) (Unity) by Deniz Bicer
* [Physarealm](https://github.com/maajor/Physarealm) (Rhino + Grasshopper) by Ma Yidong
* [Physarum](https://github.com/janivanecky/Physarum) (C++, with 2D and 3D implementations) by Jan Ivanecky
_Creative projects:_
* [physarum](https://sagejenson.com/physarum) by Sage Jenson (mxsage)
* [Slime mold](http://ch3.gr/2018/slime-mold/) by Georgios Cherouvim
---
### Primordial Particle System
> [!NOTE]
> Related to [Particle Life](#particle-life) and [agent-based modelling](#agent-based-modelling).
_Image credit: detail of [Figure 3G](https://www.nature.com/articles/srep37969/figures/3) from Schmickl, Stefanec & Crailsheim (2016)_
Described in 2016 by Thomas Schmickl, Martin Stefanec and Karl Crailsheim of the Artificial Life Lab in Graz, Austria, a Primordial Particle System (PPS) is a minimal [agent-based model](#agent-based-modelling) in which self-propelled particles move through continuous space while steering based only on how many neighbors they can see to their left and right - a motion law even simpler than [boids](#boids), with no cohesion, separation or alignment rules. It is a separate system from [Particle Life](#particle-life), where all of the behavior comes instead from multiple particle types with per-pair attraction rules.
Despite containing no notion of cells, membranes or reproduction, the system spontaneously produces cell-like structures with a dense interior surrounded by a ring-like membrane, and those structures go through a full life cycle: they feed on the surrounding "nutrient" field of free particles, grow, divide into daughter cells and spores, and die when starved. Left running, the population of cells levels off along a sigmoidal curve much like bacteria growing in a petri dish, making this one of the most striking demonstrations of how self-structuring, self-reproducing and self-sustaining behaviors can emerge from a single line of math.
_Motion law:_
$$\Delta\phi = \alpha + \beta \cdot N_{t,r} \cdot \text{sign}(R_{t,r} - L_{t,r})$$
Where $L$ and $R$ are the number of neighbors within radius $r$ in the semicircles to the particle's left and right, $N = L + R$ is the total number of neighbors, $\alpha$ is a fixed rotation, $\beta$ is a rotation proportional to local crowding, and a positive $\Delta\phi$ is a turn to the right.
_Algorithm at a glance:_
_\* indicates a potential simulation parameter_
1. Randomly distribute particles across the habitat with random headings, at a density\* of around 0.08 particles per square unit (the paper uses a 250x250 unit space that wraps around at the edges).
2. In each time step, visit every particle _once, in random order_, and for each one:
1. Count its neighbors within radius $r$\*, splitting them into those on its left ($L$) and those on its right ($R$).
2. Turn it by $\Delta\phi$ using the motion law above, with a fixed angle $\alpha$\* and a crowding-proportional angle $\beta$\*.
3. Move it forward by a constant velocity $v$\*.
3. Update particles _asynchronously_ - each particle senses and moves within the same loop, so it sees the already-updated positions of the particles visited before it in that time step. Updating everything simultaneously instead will not produce the same results.
4. Optionally color-code particles by local neighborhood size to make the structures legible (see below).
_Reference parameter set:_ $\text{PPS} = \langle r = 5, \alpha = 180°, \beta = 17°, v = 0.67 \rangle$
_Color coding (as used in the paper):_
* Green ($N \leq 13$) - free-floating "nutrient" particles
* Brown ($13 \leq N \leq 15$) - premature spores
* Magenta (more than 15 neighbors within a much smaller radius of 1.3) - mature spores
* Blue ($15 < N \leq 35$) - the bulk of cell structures, including their membranes
* Yellow ($N > 35$) - the densest interiors of cells
_Articles:_
* [How a life-like system emerges from a simple particle motion law](https://www.nature.com/articles/srep37969) by Thomas Schmickl, Martin Stefanec & Karl Crailsheim - original 2016 paper in Scientific Reports (open access, with pseudo-code in Figure 1).
* [Primordial Particle Systems](https://alife.uni-graz.at/projects/primordial-particle-systems/) research track page from the Artificial Life Laboratory in Graz, Austria.
* [A Primordial Particle System in three dimensions](https://arxiv.org/abs/1901.09293) by Thomas Schmickl & Martin Stefanec - extends the model into 3D, with pseudo-code and notes on what has to change.
* [Complexity](https://www.thomasschmickl.eu/complexity) by Thomas Schmickl - short plain-language introduction from one of the authors.
_Videos:_
* [How life emerges from a simple particle motion law: Introducing the Primordial Particle System](https://www.youtube.com/watch?v=makaJpLvbow) by the Artificial Life Lab Graz
_Projects:_
* [Primordial Particle System](https://nagualdesign.github.io/) (JavaScript, single-page HTML canvas) by nagualdesign ([Github repo](https://github.com/nagualdesign/Primordial-Particle-System))
* [emergence](https://github.com/blobject/emergence) (C++ with OpenGL and OpenCL) by blobject - PPS visualiser and processor with live parameter controls
* [pps](https://github.com/fzipp/pps) (Go, renders in the browser) by fzipp
* [PPS](https://github.com/adamnb/PPS) (Processing) by Adam Brown
* [pml_system](https://github.com/TimoLassmann/pml_system) (C) by Timo Lassmann
* [PrimordialParticleSystems_Public](https://gitlab.com/thomasschmickl/primordialparticlesystems_public) by Thomas Schmickl - implementations shared by one of the original authors
---
### Reaction-diffusion
> [!NOTE]
> Related to [convolution kernel](#convolution-kernel) and [Laplace equation](#laplace-equation).
Grid-based process that generates complex and dynamic patterns based the interactions of two chemicals as they _diffuse_ through a medium and _react_ with one another. At every location on the grid these chemicals (usually referred to as `A` and `B`) have a chance of causing a _reaction_ that converts chemicals of one type to another based on their relative concentrations at that location.
Throughout the simulation chemical `A` is added at a particular _feed rate_ (`f`) and chemical `B` is removed at a particular _kill rate_ (`k`) - adjusting these rates can result in wildly different emergent patterns.
_Equation (via [Karl Sims](https://www.karlsims.com/rd.html)):_
_Key terms:_
* Feed rate - rate at which chemical `A` is added to system
* Kill rate - rate at which chemical `B` is removed from the system
* Diffusion rate - rate at which each chemical spreads, which acts as a kind of scaler to a 3x3 [Laplacian transform](#laplace-transform)
* Reaction chance - probability that one `A` will be converted to a `B` when in the presence of two `B`s.
* Gray-Scott model
* [Pearson's classification](http://mrob.com/pub/comp/xmorphia/pearson-classes.html)
* [Turing patterns](https://en.wikipedia.org/wiki/Turing_pattern)
_Articles:_
* [Reaction-diffusion system](https://en.wikipedia.org/wiki/Reaction%E2%80%93diffusion_system) on Wikipedia
* [Reaction-Diffusion Tutorial](https://www.karlsims.com/rd.html) by Karl Sims
* [Reaction-Diffusion by the Gray-Scott Model: Pearson's Parametrization](https://mrob.com/pub/comp/xmorphia/) by Robert Munafo (mrob)
* [Reaction Diffusion: The Gray-Scott Algorithm](https://www.algosome.com/articles/reaction-diffusion-gray-scott.html) by Algosome
* [The Chemical Basis of Morphogenesis](http://www.dna.caltech.edu/courses/cs191/paperscs191/turing.pdf) (PDF) paper by Alan Turing (1952)
_Notable tools:_
* [Ready](https://github.com/GollyGang/ready)
_Code projects:_
* [Gray–Scott Reaction Diffusion](https://observablehq.com/@mbostock/gray-scott-reaction-diffusion) (JavaScript + WebGL) by Mike Bostock
* [Gray-Scott - JavaScript experiments](https://github.com/pmneila/jsexp) by @pmneila
* [simutils-0001: Gray-Scott reaction diffusion](http://toxiclibs.org/2010/02/simutils-grayscott/) by toxiclibs
* [ofxReactionDiffusion](https://github.com/matsune/ofxReactionDiffusion) add-on for openFrameworks by Yuma Matsune
* [ofxRD](https://github.com/aanrii/ofxRD) add-on for openFrameworks by aanri
* [Reaction Diffusion](https://www.redblobgames.com/x/1905-reaction-diffusion/) (JavaScript + WebGL) by Red Blob Games
* [Reaction Diffusion](https://kaesve.nl/projects/reaction-diffusion/readme.html) by Ken Voskuil (look in the DOM)
* [Reaction-Diffusion Playground](https://github.com/jasonwebb/reaction-diffusion-playground) (JavaScript, ThreeJS/WebGL, shaders) by Jason Webb
* [Reaction-Diffusion Simulation in Three.js](https://github.com/colejd/Reaction-Diffusion-ThreeJS) (JavaScript + ThreeJS) by Jonathan Cole
* [Reaction diffusion with C++ and SFML](https://github.com/Deedone/Small-projects/tree/master/Reaction-diffusion) by Deedone
* [Reaction-Diffusion simulation with C++, SFML, & Cuda](https://github.com/Solidsilver/PDEProj/tree/master/Numerics) by Luka Mattfield (@Solidsilver)
* [ReaDDy](https://readdy.github.io/) (C++ with Python bindings)
* [RDSystem](https://github.com/keijiro/RDSystem) (Unity) by Keijiro Takahashi
* [Multiscale Turing Patterns](https://github.com/rreusser/rreusser.github.io/tree/master/src/src/multiscale-turing-patterns) (JavaScript, GLSL, regl) by Ricky Reusser
* Read his [write-up](http://rreusser.github.io/multiscale-turing-pattern-gallery/) and try the [live version here](https://rreusser.github.io/multiscale-turing-patterns).
* [Available on Observable too](https://observablehq.com/@rreusser/multiscale-turing-patterns-in-webgl).
_Creative projects:_
* [Jonathan McCabe](http://www.jonathanmccabe.com/)'s multi-scale Turing pattern series. See [Diatomaceous](https://www.flickr.com/photos/jonathanmccabe/albums/72157623472782429), [Bone Music](https://www.flickr.com/photos/jonathanmccabe/albums/72157614896989696) [[2]](https://www.flickr.com/photos/jonathanmccabe/albums/72157624469963762) [[3]](https://www.flickr.com/photos/jonathanmccabe/albums/72157625117546281), [Multi-Scale Turing Patterns](https://www.flickr.com/photos/jonathanmccabe/albums/72157644907151060) and [others](https://www.flickr.com/photos/jonathanmccabe/albums)
* See his paper [Cyclic Symmetric Multi-Scale Turing Patterns](http://www.jonathanmccabe.com/Cyclic_Symmetric_Multi-Scale_Turing_Patterns.pdf) (PDF), and [this post from Softology](https://softologyblog.wordpress.com/2011/07/05/multi-scale-turing-patterns/) explaining it.
* [3D Printed Reaction Diffusion Patterns](https://www.instructables.com/id/3D-Printed-Reaction-Diffusion-Patterns/) Instructable by Reza Ali
* [Processing: Reaction Diffusion Halftone patterns](https://vimeo.com/233530691) by Ignazio Lucenti
* [Coral Cup](https://n-e-r-v-o-u-s.com/blog/?p=8222) by Nervous System
* [Reaction Lamps](https://n-e-r-v-o-u-s.com/projects/albums/reaction-products/) by Nervous System
* [Reaction Table](https://n-e-r-v-o-u-s.com/projects/albums/reaction-table/) and [reaction shelf](https://n-e-r-v-o-u-s.com/blog/?p=992) by Nervous System
* [Reaction-Diffusion Media Wall](http://www.karlsims.com/rd-exhibit.html) by Karl Sims
* [DIFFUSION](http://kouheinakama.com/diffusion/) by Kouhei Nakama
* [Reaction Diffusion](https://vimeo.com/267338427) using point clouds by David Grzesik. See his [write-up here](http://davidgrzesik.com/breakdown_docs/S17_V350_P1_GrzesikDavid_ReactionDiffusion.pdf) (PDF)
* [Grey Scott’s Reaction Diffusion - Houdini VEX](https://vimeo.com/104572358) by Ali Seiffouri
* [Healing series](http://www.blep.com/works/healing-series/) by Brian Knep
* [Silhouect](https://cacheflowe.com/code/installation/silhouect) by Justin Gitlin (@cacheflowe)
* [Reaction diffusion](https://vimeo.com/401715181) by Artur Żarejko
_Videos:_
* [Fun with Reaction-Diffusion in Houdini](https://www.youtube.com/watch?v=K_7TkoIkFhk) by Dan Willis at SIGGRAPH Asia 2019.
* Reaction Diffusion video series for Houdini by Entagma:
* [Part I: Theory](https://vimeo.com/170073061)
* [Part II: Implementation](https://vimeo.com/170073069)
* [Part III: Shaping Growth](https://vimeo.com/170073079)
* [Coding Challenge #13: Reaction Diffusion Algorithm in p5.js](https://www.youtube.com/watch?v=BV9ny785UNc) by Daniel Shiffman ([Github repo](https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_013_ReactionDiffusion) with both p5.js and Processing source code)
* [Reaction Diffusion: A Visual Explanation](https://www.youtube.com/watch?v=LMzYrsfTiEw) by Arsiliath
---
### Space colonization
Process for iteratively growing networks of branching lines based on the distribution of growth hormone sources (called "auxin" sources) to which the lines are attracted. Originally described by Adam Runions and collaborators at the [Algorithmic Botany group](http://algorithmicbotany.org/) at the University of Calgary, this system can be used to simulate the growth of leaf venation patterns and tree-like structures, as well as many other vein-like systems like Gorgonian sea fans, circulatory systems, root systems, and more.
The original algorithm describes methods for generating both "open" (as seen in the example GIF) and "closed" venation networks, referring to whether or not secondary or tertiary veins connect together to form loops (or _anastomoses_).
_Algorithm at a glance:_
For both the open and closed variants of this algorithm, begin by placing a set of points on the canvas representing sources of either the auxin growth hormone (as in leaves) or ambient nutrients (as in trees).
Open venation:
1. Associate each auxin source with the single closest vein segment within a pre-defined _attraction distance_.
2. For each vein segment that is associated with at least one auxin source, calculate the average direction towards them as a normalized vector and generate a new vein segment that extends in that direction at a pre-defined segment length (by scaling the normalized direction vector by that length).
3. Remove any auxin sources that have vein segments within a pre-defined _kill distance_ around it.
Closed venation:
1. Associate each auxin source with all of the vein segments that are both within a pre-defined _attraction distance_ and within the source's _relative neighborhood_.
2. For each vein segment that is associated with at least one auxin source, calculate the average direction towards them as a normalized vector and generate a new vein segment that extends in that direction at a pre-defined segment length (by scaling the normalized direction vector by that length).
3. Remove any auxin sources that have been reached by _all_ of their associated vein segments.
Auxin flux canalization:
1. Give each vein segment a uniform default thickness to start with.
2. Beginning at each terminal vein segment (that is, segments with no child segments), traverse "upwards" through each parent vein segment, adding their child vein segment thickness to their own until you reach a root vein segment (a segment with no parent segment).
_Key terms:_
* Auxin source = a discrete location towards which vein segments are attracted. In biology, auxin is a hormone found in plants that promotes growth.
* Auxin flux canalization = process by which veins become thicker as they grow longer. The longer a vein gets, the more auxin flows through it ("flux"), causing veins to progressively thicken from their tips to their roots. "Canalization" references the process by which "canals" of water form.
* [Relative neighborhood](https://en.wikipedia.org/wiki/Relative_neighborhood_graph) = point _P_ is a relative neighbor of a point _Q_ if there is no other point _R_ closer to _P_ and _Q_ than they are to each other.
_Articles and papers:_
* [Modeling and visualization of leaf venation patterns](http://algorithmicbotany.org/papers/venation.sig2005.pdf) (PDF) original 2005 paper by Adam Runions, Martin Fuhrer, Brendan Lane, Pavol Federl, Anne−Gaëlle Rolland−Lagan, and Przemyslaw Prusinkiewicz
* [Modeling Trees with a Space Colonization Algorithm](http://algorithmicbotany.org/papers/colonization.egwnp2007.large.pdf) (PDF) 2007 paper by Adam Runions, Brendan Lane, and Przemyslaw Prusinkiewicz
* [Modeling organic branching structures with the space colonization algorithm and JavaScript](https://medium.com/@jason.webb/space-colonization-algorithm-in-javascript-6f683b743dc5) by Jason Webb
* [Procedurally Generated Trees with Space Colonization Algorithm in XNA C#](http://www.jgallant.com/procedurally-generating-trees-with-space-colonization-algorithm-in-xna/) by Jon Gallant
* [Part 26: Trees](http://www.sea-of-memes.com/LetsCode26/LetsCode26.html) by Michael Goodfellow
* [Art-directing procedural vegetation in Houdini using a space colonization algorithm](https://pdfs.semanticscholar.org/b907/013067a5f669de7598845d7a8b45a41815f0.pdf?_ga=2.245171206.200415744.1583546111-797165566.1583546111) (PDF) by Marta Feriani
_Creative projects:_
* [Hyphae](https://n-e-r-v-o-u-s.com/shop/line.php?code=8) and [Xylem](https://n-e-r-v-o-u-s.com/shop/line.php?code=6) series by Nervous System
* Also see their [Xylem Experiments and Improvements](https://n-e-r-v-o-u-s.com/blog/?p=1218) write-up
* [Bromeliad](https://n-e-r-v-o-u-s.com/shop/product.php?code=286) and [Calyx](https://n-e-r-v-o-u-s.com/shop/product.php?code=285&search=download) lamps by Nervous System
_Code projects:_
* [ofxSpaceColoinzation](https://github.com/edap/ofxSpaceColonization) add-on for openFrameworks
* [space-colonization](https://github.com/nicknikolov/space-colonization) (JavaScript) by Nick Nikolov
* [Dendrite](https://github.com/mattatz/Dendrite) (Unity) by mattatz
* [Grower](https://github.com/joesfer/Grower) (Maya plugin) by Jose Esteve
* [Venation](https://github.com/nielmclaren/Venation) (Processing) by Niel McLaren
* [hyphae](https://github.com/jblondin/hyphae) (Julia) by Jamie Blondin
* [hyphae](https://github.com/inconvergent/hyphae) and [hyphae_ani](https://github.com/inconvergent/hyphae_ani) by Anders Hoff (inconvergent)
* [2d-space-colonizations-experiments](https://github.com/jasonwebb/2d-space-colonization-experiments) (JavaScript) by Jason Webb
_Videos:_
* [Coding Challenge #17: Fractal Trees - Space Colonization](https://www.youtube.com/watch?v=kKT0v3qhIQY) by Daniel Shiffman ([Github repo](https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_017_SpaceColonizer) with source code for p5.js and Processing)
---
### L-systems (Lindenmayer systems)
String rewriting system invented by biologist Aristid Lindenmayer in 1968 to model the growth processes of plant development and other organisms. L-systems use simple grammatical rules to iteratively expand a string of symbols, which can then be interpreted geometrically (e.g., using turtle graphics) to produce complex branching structures. Despite their simplicity, L-systems can generate remarkably naturalistic plant forms, fractals, and branching patterns.
The key insight is that local production rules (each symbol rewrites to a sequence of symbols) applied recursively across iterations can generate globally complex structures without explicitly encoding the final form. This makes L-systems particularly powerful for modeling hierarchical biological growth.
_Algorithm at a glance:_
_\* indicates a potential simulation parameter_
1. Define an axiom\* - the initial string (often just "F" or a single symbol).
2. Define production rules\* - for example, "F → FF" (each forward step becomes two forward steps).
3. Define a number of iterations\*.
4. For each iteration, replace every symbol in the string according to its production rule, simultaneously.
5. Interpret the final string geometrically:
- Common symbols: `F` (move forward and draw), `f` (move forward without drawing), `+` (turn left), `-` (turn right), `[` (push position/heading to stack), `]` (pop position/heading from stack)
6. Render the resulting path or tree structure.
_Example:_
| Description | Rendered Result |
|---|---|
| Axiom: `F`
|
_Key terms:_
* Axiom - the starting string
* Production rules - symbol-to-string mappings applied each iteration
* Turtle graphics - geometric interpretation of the L-system string using position, heading, and a drawing pen
* Stochastic L-systems - rules chosen probabilistically rather than deterministically, creating variation
* Parametric L-systems - rules can use parameters and conditions for more sophisticated generation
* Context-sensitive L-systems - rules depend on neighboring symbols, allowing more complex interactions
_Articles:_
* [L-system](https://en.wikipedia.org/wiki/L-system) on Wikipedia
* [Chapter 1: Plant Models](http://algorithmicbotany.org/papers/abop/abop-ch1.pdf) from Algorithmic Botany book - foundational reference
_Videos:_
* [Coding Challenge #16: Recursive Trees - Fractal Trees](https://www.youtube.com/watch?v=0jjeOYMjmQE) by Daniel Shiffman ([Github repo](https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_016_RecursiveTree) with p5.js and Processing code)
* [L-System Creature Evolution](https://www.youtube.com/watch?v=knmNML7Q8Fw) by Lenia
* [8.5: L-Systems](https://www.youtube.com/watch?v=f6ra024-ASY) from Daniel Shiffman's Nature of Code series
_Notable tools and libraries:_
* Blender
* [Sapling Tree Gen](https://docs.blender.org/manual/en/4.1/addons/add_curve/sapling.html) - add-on for procedural L-system-based tree generation
* Houdini
* [L-System Geometry node](https://www.sidefx.com/docs/houdini/nodes/sop/lsystem.html)
* TouchDesigner
* [LSystem SOP](https://docs.derivative.ca/LSystem_SOP)
* Unity
* [SpeedTree](https://speedtree.com/) - commercial procedural tree generator with L-system-based generation
* Unreal Engine
* [SpeedTree integration](https://docs.unrealengine.com/5.0/en-US/using-speedtree-in-unreal-engine/) - native support for SpeedTree models
---
### Spinodal decomposition
> [!NOTE]
> Related to [reaction-diffusion](#reaction-diffusion).
Physical process by which a homogeneous mixture (a molten alloy, polymer blend, glass, etc.) spontaneously separates into two distinct phases when rapidly cooled ("quenched") into an unstable region of its phase diagram. Unlike typical nucleation-based phase separation, no discrete starting sites or thermodynamic barrier are needed - tiny composition fluctuations grow everywhere in the material simultaneously.
The result is a characteristic pattern of intertwined, worm-like regions that grow and merge ("coarsen") over time while roughly maintaining the same overall proportions of each phase - visually similar to some [reaction-diffusion](#reaction-diffusion) patterns, though it arises from a different underlying process (phase-separation thermodynamics rather than a chemical feed/kill reaction). It's commonly modeled with the [Cahn-Hilliard equation](https://en.wikipedia.org/wiki/Cahn%E2%80%93Hilliard_equation), a PDE describing how the concentration of the two phases diffuses and separates over time.
_Algorithm at a glance:_
_\* indicates a potential simulation parameter_
1. Fill a grid with random noise\* representing the initial, unstable composition of the mixture.
2. At each step, for every cell, calculate how its concentration should change based on two competing effects: diffusion (smoothing out differences with its neighbors) and phase separation (pushing its value away from the mixed middle and toward one pure phase or the other).
3. Update every cell by combining these two effects, scaled by a diffusion rate\* and a phase-separation strength\*.
4. Repeat, letting separated regions grow and merge (coarsen) over time.
_Key terms:_
* [Cahn-Hilliard equation](https://en.wikipedia.org/wiki/Cahn%E2%80%93Hilliard_equation) - the PDE most commonly used to model spinodal decomposition.
* Quench - rapid cooling of a mixture into an unstable region of its phase diagram, triggering decomposition.
* Coarsening - the slow, ongoing growth and merging of separated regions over time.
* Nucleation - the barrier-driven alternative to spinodal decomposition, where phase separation starts at discrete sites rather than everywhere at once.
_Articles:_
* [Spinodal decomposition](https://en.wikipedia.org/wiki/Spinodal_decomposition) on Wikipedia
* [Cahn-Hilliard equation](https://en.wikipedia.org/wiki/Cahn%E2%80%93Hilliard_equation) on Wikipedia
* [Spinodal decomposition](https://www.reddit.com/r/generative/comments/g3spa0/spinodal_decomposition/) generative art post on r/generative - the post that inspired [this topic's request](https://github.com/jasonwebb/morphogenesis-resources/issues/18)
_Code projects:_
* [Spinodal-Decomposition](https://github.com/nsbalbi/Spinodal-Decomposition) (MATLAB) by Nicholas Balbi - simulates and renders the Cahn-Hilliard equation
### Archimedean solids
> [!NOTE]
> Related to [polyhedra](#polyhedra) and [Platonic solids](#platonic-solids).
Set of 13 semi-regular convex polyhedra composed of regular polygons meeting in identical vertices, excluding the 5 [Platonic solids](#platonic-solids) (which are composed of only one type of polygon) and excluding the prisms and antiprisms.
Each shape [can be constructed](https://en.wikipedia.org/wiki/Archimedean_solid#Construction_of_Archimedean_solids) by starting with one of the [Platonic solids](#platonic-solids) and truncating it's corners or edges in various ways.
_List of Archimedean solids:_
| Name | Faces | Edges | Vertices | Image |
|--- |--- |--- |--- |--- |
| Truncated tetrahedron | 4 triangles
|
| Cuboctahedron | 8 triangles
|
| Truncated cube | 8 triangles
|
| Truncated octahedron | 6 squares
|
| Rhombicuboctahedron | 8 triangles
|
| Truncated cuboctahedron | 12 squres
|
| Snub cube | 32 triangles
|
| Icosidodecahedron | 20 triangles
|
| Truncated dodecahedron | 20 triangles
|
| Truncated icosahedron | 12 pentagons
|
| Rhombicosidodecahedron | 20 triangles
|
| Truncated icosidodecahedron | 30 squares
|
| Snub dodecahedron | 80 triangles
|
_Articles:_
* [Archimedean solid](https://en.wikipedia.org/wiki/Archimedean_solid) on Wikipedia
* [Archimedean Solid](http://mathworld.wolfram.com/ArchimedeanSolid.html) on Wolfram MathWorld
* [Archimedean Polyhedra](https://www.georgehart.com/virtual-polyhedra/archimedean-info.html) by George Hart
_Videos:_
* [Platonic and Archimedean solids](https://www.youtube.com/watch?v=U3cTXqvW3XU) by Henry Segerman
---
### Cellular automata (CA)
> [!NOTE]
> Related to [convolution kernel](#convolution-kernel) and [neural cellular automata](#neural-cellular-automata-nca).
A regular grid of _cells_ with _states_ that are updated each iteration in according to _rules_. Developed by Stanislaw Ulam and John von Neumann at the Los Alamos National Laboratory in the 1940s, this system has been used to model physical, biological, and social phenomena with remarkable variety and accuracy.
_Key terms:_
* Cell - a discrete location on the grid
* State - the "value" of a cell. Many CAs just have two states (on/off), but others use many.
* Neighborhood - set of cells surrounding a given cell. Most common types are [Von Neumann](https://en.wikipedia.org/wiki/Von_Neumann_neighborhood) and [Moore](https://en.wikipedia.org/wiki/Moore_neighborhood), though others exist.
* Rule(s) - mathematical functions or if/else statement(s) that define what the next state of a cell should be based on various criteria like the states of that cell's neighbors. Sometimes called _transition rules_.
* Generation - result of one iteration of the system.
_Types:_
* [Asynchronous](https://en.wikipedia.org/wiki/Asynchronous_cellular_automaton) - automaton in which each cell is updated independantly of the others over time. Multiple [update schemes](https://en.wikipedia.org/wiki/Asynchronous_cellular_automaton#Update_Schemes) have been proposed by various researchers.
* [Block](https://en.wikipedia.org/wiki/Block_cellular_automaton) - automaton in which the grid of cells is divided into non-overlapping blocks, with rules being applied to entire blocks rather than individual cells. Also known as a partitioning cellular automaton.
* [Continuous](https://en.wikipedia.org/wiki/Continuous_automaton) - automaton in which each cell has a real number value instead of an integer state.
* [Continuous spatial](https://en.wikipedia.org/wiki/Continuous_spatial_automaton) - automaton in which the cell _locations_ are continuous.
* [Cyclic](https://en.wikipedia.org/wiki/Cyclic_cellular_automaton) - automaton in which cells are initialized with one of a number of states in a range, then can be "consumed" when a neighboring cell has a successor state, causing the cell's state to take on that successor state. In other words, if cells can take on a value in the range `[0,9]`, then a cell with value `2` can be "consumed" by a neighboring cell with value `3`, causing the cell to take on the value of `3`. When cells reach the state at the end of the range, they are reset to the state at the beginning of the range (wrapping around).
* Discrete - the "default" configuration for cellular automata, in which a grid of regular square cells and integer states are used.
* [Elementary](https://en.wikipedia.org/wiki/Elementary_cellular_automaton) - 1D cellular automata with two states and 256 possible rules. Thought to be the simplest possible cellular automaton.
* [Life-like](https://en.wikipedia.org/wiki/Life-like_cellular_automaton) - any 2D outer totalistic automaton that uses two states and a Moore neighborhood, and whose transition rule can be expressed as a function of the number of neighboring cells that are in the "alive" state. [Three standard rule notations](https://en.wikipedia.org/wiki/Life-like_cellular_automaton#Notation_for_rules) exist, and a large number of [rules have been identified and researched](https://en.wikipedia.org/wiki/Life-like_cellular_automaton#A_selection_of_Life-like_rules).
* [Neural](#neural-cellular-automata-nca) - automaton whose local transition rule is represented by a neural network, typically learned by optimizing for desired large-scale forms or behaviors. Often also continuous and stochastic.
* [Reversible](https://en.wikipedia.org/wiki/Reversible_cellular_automaton) - automaton in which past grid states can be determined using later grid states. In other words, if you know the state at time `t`, you can compute the state at `t - 1`.
* [Second-order](https://en.wikipedia.org/wiki/Second-order_cellular_automaton) - automaton in which cell states depend on their neighborhood in the last _two_ generations. In other words, the state at time `t` depends on the state at both `t - 1` and `t - 2`.
* [Stochastic](https://en.wikipedia.org/wiki/Stochastic_cellular_automaton) - automaton with a transition rule that incorporates a probability distribution or, in other words, some degree of randomness. Also known as probabilistic (PCA) or random cellular automata.
* [Totalistic](https://en.wikipedia.org/wiki/Cellular_automaton#Totalistic) - automaton in which the state of each cell is based on the sum of the values of its neighbor cells in the previous iteration. If it also depends on its own state in the previous iteration then the automaton can be called _outer totalistic_ or _semitotalistic_.
_Wolfram's classification:_
Stephan Wolfram defined four classes that can be used to describe any cellular automaton or other simple computational model based on their observed behaviors. These definitions are qualitative in nature, with some room for intepretation, but are nonetheless considered the most effective classification scheme that currently exists for cellular automata.
* Class 1: Uniformity - nearly all initial patterns evolve quickly into a stable, homogeneous state. Any randomness in the initial pattern disappears.
* Class 2: Repetition - nearly all initial patterns evolve quickly into stable or oscillating structures. Some of the randomness in the initial pattern may filter out, but some remains. Local changes to the initial pattern tend to remain local.
* Class 3: Random - nearly all initial patterns evolve in a pseudo-random or chaotic manner. Any stable structures that appear are quickly destroyed by the surrounding noise. Local changes to the initial pattern tend to spread indefinitely.
* Class 4: Complexity - nearly all initial patterns evolve into structures that interact in complex and interesting ways, with the formation of local structures that are able to survive for long periods of time.
_Well-known rules and rule families:_
* [Brian's Brain](https://en.wikipedia.org/wiki/Brian%27s_Brain) by Brian Silverman
* [Game of Life](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life) by John Conway
* [Generations](https://conwaylife.com/wiki/Generations)
* [Lenia](https://arxiv.org/abs/1812.05433) ([repo](https://github.com/Chakazul/Lenia)) by Bert Wang-Chak Chan
* [Langton's Ant](https://en.wikipedia.org/wiki/Langton%27s_ant) by Chris Langton
* [Larger than Life](https://www.conwaylife.com/wiki/Larger_than_Life) by Kellie Michele Evans
* [SmoothLife](https://arxiv.org/pdf/1111.1567.pdf) by Stephan Rafler (original paper, PDF)
* [Wireworld](http://mathworld.wolfram.com/WireWorld.html) by Brian Silverman
_Articles, books, and other writings:_
* [Building simulations with a Go cellular automata framework](https://medium.com/swlh/building-simulations-with-a-go-cellular-automata-framework-89b2bb1246d3) by Sau Sheong
* [Cellular automaton](https://en.wikipedia.org/wiki/Cellular_automaton) on Wikipedia
* [Cellular Automata rules lexicon](http://www.mirekw.com/ca/ca_rules.html) in the MCell documentation by Mirek Wojtowicz
* [Chapter 7. Cellular Automata](https://natureofcode.com/book/chapter-7-cellular-automata/) from Daniel Shiffman's Nature of Code book
* [Elementary Cellular Automaton](http://mathworld.wolfram.com/ElementaryCellularAutomaton.html) on Wolfram MathWorld
* [New Kind of Science](https://www.wolframscience.com/nks/) by Stephan Wolfram
* [Understanding Multiple Neighborhood Cellular Automata](https://slackermanz.com/understanding-multiple-neighborhood-cellular-automata) by Slackermanz
_Code projects:_
* [cellauto.js](http://sanojian.github.io/cellauto/) ([source](https://github.com/sanojian/cellauto)) by Jonas Olmstead (JavaScript)
* [cellularAutomata](https://github.com/bollu/cellularAutomata) by Siddharth Bhat (Haskell)
* [Cellular Automata Simulator (CAS)](https://github.com/ghjansen/cas) by Guilherme Humberto Jansen (Java)
* [cellpylib](https://github.com/lantunes/cellpylib) by Luis Antunes (Python)
* [Lifelike](https://lifelike.psychedelicio.us/) ([source](https://github.com/psychedelicious/lifelike)) by @psychedelicious
* [regl-smooth-life](https://github.com/rreusser/demos/tree/master/smooth-life) by Ricky Reusser (JavaScript, WebGL, GLSL)
* [sandspiel](https://sandspiel.club/) ([source](https://github.com/MaxBittker/sandspiel)) by Max Bittker (JavaScript)
* [SmoothLife](https://github.com/duckythescientist/SmoothLife) by Sean Murphy (Python)
* [SmoothLife](https://sourceforge.net/projects/smoothlife/) by ionreq (C++, Matlab, BASIC)
* [terra.js](https://rileyjshaw.com/terra/) ([source](https://github.com/rileyjshaw/terra)) by Riley Shaw (JavaScript)
* Various packages and projects by Kevin Chapelier:
* [cellular-automata](https://github.com/kchapelier/cellular-automata)
* [cellular-automata-gpu](https://github.com/kchapelier/cellular-automata-gpu)
* [cellular-automata-rule-parser](https://github.com/kchapelier/cellular-automata-rule-parser)
* [cellular-automata-voxel-shader](https://github.com/kchapelier/cellular-automata-voxel-shader)
_Creative projects:_
* [3D printed Game of Life shoes](https://www.dezeen.com/2014/09/26/francis-bitonti-3d-printed-molecule-shoes-adobe-stratasys/) by Francis Bitonti
* [KnitYak: Custom mathematical knit scarves](https://www.kickstarter.com/projects/fbz/knityak-custom-mathematical-knit-scarves) by Fabienne "fbz" Serriere
_Notable software:_
* [cubes.io: 3d cellular automata](http://cubes.io/) by Charlie Deck
* [Golly](http://golly.sourceforge.net/)
* [MCell](http://psoup.math.wisc.edu/mcell/) (Mirek's Cellebration) by Mirek Wojtowicz
* [Visions of Chaos](https://www.softology.com.au/voc.htm) by Jason Rampe
* [WebCA / Cellular Automata Laboratory (CelLab)](https://www.fourmilab.ch/cellab/webca/) by Rudy Rucker and John Walker
---
### Conway operators
> [!NOTE]
> Related to [polyhedra](#polyhedra), [Platonic solids](#platonic-solids), and [Archimedean solids](#archimedean-solids).
[Conway polyhedron notation](https://en.wikipedia.org/wiki/Conway_polyhedron_notation), invented by mathematician John Horton Conway and later extended by George W. Hart, is a compact system for describing complex polyhedra as a short chain of operators applied to a simple seed shape. Operators are single lowercase letters applied right-to-left, so `taC` means "start with a cube (`C`), apply ambo (`a`), then truncate (`t`)" - the same recipe that produces a truncated cuboctahedron. This turns a huge space of polyhedra into a small, composable vocabulary, which is why it's a popular basis for procedural polyhedron tools.
_Seeds:_
Starting shapes are abbreviated with a single capital letter: `T` (tetrahedron), `C` (cube), `O` (octahedron), `D` (dodecahedron), `I` (icosahedron), `P`_n_ (n-gonal prism), `A`_n_ (n-gonal antiprism), `Y`_n_ (n-gonal pyramid).
_Core operators:_
* `d` (dual) - swaps every face for a vertex and vice versa (e.g. `dC` = octahedron).
* `a` (ambo) - adds a vertex at the midpoint of every edge and connects them, producing the "rectified" Archimedean forms (e.g. `aC` = cuboctahedron).
* `t` (truncate) - slices off each vertex, turning it into a small new face.
* `k` (kis) - raises a pyramid on every face by adding a vertex at its center.
* `j` (join) - connects the centers of adjacent faces, replacing them with quadrilaterals.
* `e` (expand) - pushes each face outward along its normal and fills the resulting gaps with new faces.
* `s` (snub) - like expand, but with a twist added, producing a chiral form with extra triangular faces (e.g. `sC` = snub cube).
* `g` (gyro) - the dual of snub; introduces a chiral twist without adding triangles.
* `b` (bevel) - combines truncation and ambo.
* `o` (ortho) - subdivides each face into quadrilaterals around its center.
* `m` (meta) - combines kis and join.
George Hart later added `r` (reflect, mirrors a chiral form) and `p` (propellor), and modern implementations support dozens more (chamfer, needle, zip, loft, whirl, and others).
_Articles:_
* [Conway polyhedron notation](https://en.wikipedia.org/wiki/Conway_polyhedron_notation) on Wikipedia
* [Conway Notation for Polyhedra](https://www.georgehart.com/virtual-polyhedra/conway_notation.html) by George Hart - the original extended reference, with construction diagrams for each operator
_Notable tools:_
* [Polyhedronisme](https://levskaya.github.io/polyhedronisme/) by Anselm Levskaya - interactive web app for building polyhedra with Conway operators (see [Polyhedra](#polyhedra) for more)
* [Antiprism's `conway`](https://www.antiprism.com/programs/conway.html) by Adrian Rossiter and Roger Kaufman - command-line Conway notation processor, adapted from Hart's original implementation
---
### Convolution kernel
> [!NOTE]
> Related to [cellular automata](#cellular-automata-ca), [reaction-diffusion](#reaction-diffusion), [noise](#noise), and [image processing](https://en.wikipedia.org/wiki/Kernel_(image_processing)).
A convolution kernel is a small matrix of numbers that defines a weighted neighborhood operation. When applied to a grid (like an image, scalar field, or cellular grid), the kernel is placed over each location, its values are multiplied by the overlapping grid values, the products are summed, and the result is written to the center cell. This operation is the foundation for countless techniques across image processing, simulations, and signal analysis.
The kernel acts as a _filter_ that emphasizes or suppresses patterns in the data. A kernel of all ones computes the sum of a neighborhood. A kernel with larger values in the center and smaller values at the edges acts as a blur (weighted average). Kernels with opposing signs can detect edges. Different kernels solve different problems, but they all follow the same convolution process: slide, multiply, sum, repeat.
_Core concepts:_
* Kernel (filter) - the small matrix applied to each location. Kernels are typically square (3×3, 5×5) but can be any shape or size.
* Neighborhood - the set of grid values that overlap with the kernel at a given position.
* Convolution - the process of sliding the kernel across the grid, computing weighted sums, and producing an output grid.
* Boundary handling - strategies for dealing with edges where the kernel extends beyond the grid: zero-padding (pad with 0s), reflection, wrapping, or shrinking the output.
* Stride - the step size when sliding the kernel (1 means every position, 2 means every other position, etc.).
* Normalization - dividing the kernel result by the sum of the kernel values to preserve the magnitude of the output (especially important for averaging kernels).
_Applications across domains:_
* [Image processing](#kernel-based-image-processing) - blur, sharpen, edge detection, emboss, dilation/erosion (mathematical morphology), and many other filters.
* [Reaction-diffusion systems](#reaction-diffusion) - convolution kernels approximate the Laplacian operator, which governs how substances diffuse and interact across a spatial grid.
* [Cellular automata](#cellular-automata-ca) - rules based on the sum or pattern of a neighborhood are implicitly convolving with a kernel.
* [Fluid simulation](#fluid-simulation) - pressure solvers and advection schemes use convolution to distribute quantities across neighboring cells.
* [Noise generation](#noise) - blurring or interpolating noise through convolution creates coherent multi-scale patterns (basis for Perlin noise smoothing).
* Morphological operations - erosion and dilation kernels reshape binary regions (used in image segmentation and shape analysis).
* Smoothing and filtering - low-pass filters smooth noisy data; high-pass filters enhance detail and edges.
_Articles:_
* [All about convolutions, kernels, features in CNN](https://medium.com/@abhishekjainindore24/all-about-convolutions-kernels-features-in-cnn-c656616390a1) by Abhishek Jain
* [Kernel (image processing)](https://en.wikipedia.org/wiki/Kernel_(image_processing)) on Wikipedia
* [Convolution](https://en.wikipedia.org/wiki/Convolution) on Wikipedia
* [Filters and convolution](https://en.wikipedia.org/wiki/Digital_image_processing#Filtering) in digital image processing
* [Laplacian operator](https://en.wikipedia.org/wiki/Laplace_operator) on Wikipedia
_Videos:_
* [Image Kernels Explained Visually](https://setosa.io/ev/image-kernels/) - interactive visualization by Victor Powell
_Code projects and libraries:_
* [scikit-image](https://scikit-image.org/) (Python) - filters, morphology, edge detection
* [OpenCV](https://opencv.org/) (C++, Python, JavaScript) - extensive kernel-based filtering and image processing
* [PIL/Pillow](https://python-pillow.org/) (Python) - image filters with custom kernels
* [GIMP](https://www.gimp.org/) - manual convolution filter tool for artistic exploration
* [Three.js postprocessing](https://github.com/mrdoob/three.js/tree/dev/examples/jsm/postprocessing) (JavaScript) - GPU-based convolution for real-time effects
* [Shader-based convolution](https://www.khronos.org/opengl/wiki/Compute_Shader) - fragment shaders implement kernel operations efficiently on GPU
---
### Cymatics
> [!NOTE]
> Related to [Chladni plate](#chladni-plate)
Study of the visible effects of sound and vibration on physical media. Typically involves the vibration of a plate or membrane onto which fine powder or fluids have been placed, which subsequently arrange themselves into highly symmetrical, complex patterns based on the intensity of displacement of various regions of the vibrating plate. Areas that are moving a lot will "kick" material away from them while areas that are moving very little allow material to settle and accumulate. These areas of relatively little vibration are caused by destructive interference of waves as they propagate across the plate/membrane and become out of phase with one another, creating "dead zones" where these waves cancel each other out.
_Articles:_
* [Cymatics](https://en.wikipedia.org/wiki/Cymatics) on Wikipedia
* [Modal vibrational phenomena](https://en.wikipedia.org/wiki/Normal_mode) on Wikipedia
_Creative projects:_
* [CYMATICS: Science Vs. Music](https://vimeo.com/111593305) by Nigel Stanford
* [Cymatics](https://vimeo.com/74130357) by Susi Sie
* [The Essence of Sound](https://vimeo.com/89491724) by Susi Sie
---
### Delaunay triangulation and Voronoi diagrams
> [!NOTE]
> Related to [tiling / tessellation](#tiling--tessellation).
_Delaunay triangulation_ is a way of connecting a set of points to form a network of non-overlapping triangles. One of the key properties of Delaunay triangulations is that the [circumcircles](https://en.wikipedia.org/wiki/Circumscribed_circle) associated with each triangle contains no other points than their three triangle vertices. When extended into 3D, Delaunay triangulation is useful for creating meshes.
_Voronoi diagrams_ are the [dual](https://observablehq.com/@mbostock/the-delaunays-dual) of Delaunay triangulations. This means that once a Delaunay triangulation has been computed for a set of points, a Voronoi diagram can be drawn without any additional data - just draw lines connecting the centers of the circumcircles!
Voronoi diagrams are very useful for efficiently and organically partitioning (splitting up) both 2D and 3D space. They are especially good for accurately modelling the way soft bodies (like biological cells) get smushed together in constrained environments, like embryonic cells undergoing mitosis.
Voronoi diagrams are often used (perhaps overused) in digital fabrication applications, [especially 3D printing](https://www.google.com/search?q=voronoi+3d+printing&source=lnms&tbm=isch&sa=X&ved=0ahUKEwiQh-npy_HhAhUFSq0KHfBpClQQ_AUIDigB&biw=1920&bih=937), for their characteristic aesthetic style and their ability to reduce material usage while preserving overall form. Given their popularity among amateur 3D printing enthusiasts, this effect is probably best used sparingly in serious applications.
_Articles:_
* [Delaunay triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation) on Wikipedia
* [Voronoi diagram](https://en.wikipedia.org/wiki/Voronoi_diagram) on Wikipedia
---
### Fibonacci sequence
> [!NOTE]
> Related to [Golden ratio](#golden-ratio).
Sequence of numbers in which each number is the sum of it's two preceding numbers. [Binet's formula](https://en.wikipedia.org/wiki/Fibonacci_number#Binet's_formula) shows that the ratio of two consecutive numbers tends towards the [golden ratio](#golden-ratio) as the sequence progresses. Fibonacci numbers appear unexpectedly often in biology, having been observed in branching of trees, the arrangement of leaves on a stem, the fruit sprouts of a pineapple, the flowering of an artichoke, an uncurling fern and the arrangement of a pine cone's bracts.
_Formula:_
$$F_{0}=0,\quad F_{1}=1,$$
$$F_{n}=F_{n-1}+F_{n-2},$$
_Sequence begins with:_
$$(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \ldots$$
_Articles:_
* [Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_number) on Wikipedia
* [Fibonacci Sequence](https://www.mathsisfun.com/numbers/fibonacci-sequence.html) on Math Is Fun
* [Fibonacci Number](http://mathworld.wolfram.com/FibonacciNumber.html) on Wolfram MathWorld
---
### Fourier series
Series of sinusoidal wave functions that get added together to generate a different, more complex function. In the context of morphogenesis (form generation), any line drawing can be "deconstructed" into a series of arc segments which can in turn be represented by a series of circles whose radii and rotation speeds correspond to the radii and lengths of the arc segments.
Fourier series and Fourier transforms are deeply mathematical topics with applications and research far beyond the scope of this resource list. They are extremely useful in the field of digital signal processing for noise reduction, compression, audio analysis, and so much more. A very well-known algorithm known as the [fast Fourier transform (FFT)](https://en.wikipedia.org/wiki/Fast_Fourier_transform) enables extraction of waveforms from music for the purposes of audio visualization.
_Articles:_
* [Fourier series](https://en.wikipedia.org/wiki/Fourier_series) on Wikipedia
* [Fourier Series](http://mathworld.wolfram.com/FourierSeries.html) on Wolfram MathWorld
* [Fourier Series](https://www.mathsisfun.com/calculus/fourier-series.html) on Math Is Fun
_Videos:_
* [What is a Fourier Series? (Explained by drawing circles)](https://www.youtube.com/watch?v=ds0cmAV-Yek&vl=en) by Smarter Every Day
* [But what is the Fourier Transform? A visual introduction](https://www.youtube.com/watch?v=spUNpyF58BY) by 3Blue1Brown
* [Coding Challenge #125: Fourier Series](https://www.youtube.com/watch?v=Mm2eYfj0SgA) by Daniel Shiffman
* [Coding Challenge #130.1: Drawing with Fourier Transform and Epicycles](https://www.youtube.com/watch?v=MY4luNgGfms) by Daniel Shiffman
* [Coding Challenge #130.2: Fourier Transform User Drawing](https://www.youtube.com/watch?v=n9nfTxp_APM) by Daniel Shiffman
* [Coding Challenge #130.3: Fourier Transform Drawing with Complex Number Input](https://www.youtube.com/watch?v=7_vKzcgpfvU) by Daniel Shiffman
---
### Fractals
Infinitely complex patterns generated via [recursion](#recursion) that are self-similar across all scales. Thought to be found in abundance in nature, though "true" (infinite) fractals are not possible because nature uses physical matter, which has particular structures at the microscopic and smaller scales (molecules, atoms, elementary particles, etc).
Fractal features can be observed in nature in tree branching structures, leaf veins, terrain, surface textures, coastlines, rivers, succulents, snowflakes, rivers, lightning bolts, nautilus shells (both form and pattern), and so much more.
_Key terms:_
* [Fractal dimension](https://en.wikipedia.org/wiki/Fractal_dimension) - ratio providing a statistical index of complexity comparing how detail in a fractal changes with scale.
* [Self-similarity](https://en.wikipedia.org/wiki/Self-similarity) - when something is exactly or approximately similar to a part of itself.
_Notable fractals:_
* [Apollonian gasket](https://en.wikipedia.org/wiki/Apollonian_gasket) (a.k.a. curvilinear Sierpiński gasket)
* [Barnsley fern](https://en.wikipedia.org/wiki/Barnsley_fern)
* [Cantor set](https://en.wikipedia.org/wiki/Cantor_set)
* [Chaos game](https://en.wikipedia.org/wiki/Chaos_game)
* [Dragon curve](https://en.wikipedia.org/wiki/Dragon_curve)
* [Hilbert curve](https://en.wikipedia.org/wiki/Hilbert_curve)
* [Iterated function systems (IFS)](https://en.wikipedia.org/wiki/Iterated_function_system)
* [Lindenmayer systems (L-systems)](https://en.wikipedia.org/wiki/L-system)
* [Julia set](https://en.wikipedia.org/wiki/Julia_set)
* [Koch snowflake](https://en.wikipedia.org/wiki/Koch_snowflake)
* [Menger sponge](https://en.wikipedia.org/wiki/Menger_sponge)
* [Mandelbrot set](https://en.wikipedia.org/wiki/Mandelbrot_set) (related: [Mandelbulb](https://en.wikipedia.org/wiki/Mandelbulb) and [Buddhabrot](https://en.wikipedia.org/wiki/Buddhabrot))
* [Sierpiński triangle / gasket / sieve](https://en.wikipedia.org/wiki/Sierpi%C5%84ski_triangle) and [carpet](https://en.wikipedia.org/wiki/Sierpinski_carpet)
* [... and so much more](https://en.wikipedia.org/wiki/List_of_fractals_by_Hausdorff_dimension)
_Articles:_
* [Fractal](https://en.wikipedia.org/wiki/Fractal) on Wikipedia
* [List of fractals by Hausdorff dimension](https://en.wikipedia.org/wiki/List_of_fractals_by_Hausdorff_dimension) on Wikipedia
* [Fractals, Caos, Self-Similarity](http://paulbourke.net/fractals/) by Paul Bourke
* [Chapter 8. Fractals](https://natureofcode.com/book/chapter-8-fractals/) in Daniel Shiffman's Nature of Code book
_Notable software:_
* [glChAoS.P](https://github.com/BrutPitt/glChAoS.P) by Michele Morrone (BrutPitt)
---
### Geodesic
_Image credit: Vikash Mittal - [Geometric phase and its applications: topological phases, quantum walks and non-inertial quantum systems (FIGURE 2)](https://www.researchgate.net/publication/363501147_Geometric_phase_and_its_applications_topological_phases_quantum_walks_and_non-inertial_quantum_systems?_tp=eyJjb250ZXh0Ijp7ImZpcnN0UGFnZSI6Il9kaXJlY3QiLCJwYWdlIjoiX2RpcmVjdCJ9fQ)._
The shortest path between two points on a curved surface - a generalization of the concept of a "straight line" to curved geometry. On a flat plane a geodesic is just a straight line; on the surface of a sphere, geodesics are arcs of [great circles](https://en.wikipedia.org/wiki/Great_circle); on more complex curved surfaces they can bend and twist while still remaining locally "as straight as possible" at every point.
_Related terms:_
* [Great circle](https://en.wikipedia.org/wiki/Great_circle) - the specific case of a geodesic on the surface of a sphere, formed by a plane passing through the sphere's center.
* [Geodesic curvature](https://en.wikipedia.org/wiki/Geodesic_curvature) - measure of how far a curve on a surface deviates from being a geodesic.
* [Geodesic dome](#geodesic-dome) - structure whose triangulated struts approximate geodesic arcs across a sphere.
_Articles:_
* [Geodesic](https://en.wikipedia.org/wiki/Geodesic) on Wikipedia
* [Geodesic](https://mathworld.wolfram.com/Geodesic.html) on Wolfram MathWorld
---
### Geodesic dome
> [!NOTE]
> Related to [geodesics](#geodesic), [Platonic solids](#platonic-solids), and [polyhedra](#polyhedra).
Spherical shell structure of triangular struts whose vertices all lie on a circumscribed sphere. It's typically derived from a [Platonic solid](#platonic-solids) with triangular faces (usually an icosahedron) by subdividing each face some number of times (the dome's "frequency") and projecting the new vertices onto the sphere - higher frequencies mean more, smaller struts and a closer approximation of a sphere.
Named for the [geodesic](https://en.wikipedia.org/wiki/Geodesic) - the shortest path between two points on a curved surface - since its edges approximate great-circle arcs. The shell distributes structural stress evenly, giving it a high strength-to-weight ratio. Popularized (though not invented) by Buckminster Fuller, whose name was later borrowed for the similarly-shaped carbon molecules called [buckminsterfullerenes](https://en.wikipedia.org/wiki/Buckminsterfullerene).
_Key terms:_
* [Geodesic](https://en.wikipedia.org/wiki/Geodesic) - generalization of a straight line to curved surfaces; the shortest path between two points on the surface.
* [Geodesic polyhedron](https://en.wikipedia.org/wiki/Geodesic_polyhedron) - convex polyhedron made of triangles, usually derived from subdividing a Platonic or other simple polyhedron and projecting the vertices onto a sphere.
* Frequency - the number of times each face of the base polyhedron is subdivided before projection onto the sphere; written as `nV` (e.g. `3V`), where a higher number means smaller, more numerous struts.
* Strut - a single structural member (edge) connecting two vertices of the dome.
* [Chord factor](https://en.wikipedia.org/wiki/Geodesic_dome#Types) - ratio used to calculate the length of a given strut relative to the radius of the sphere.
_Articles:_
* [Geodesic Domes](https://www.bfi.org/about-fuller/geodesic-domes/) by the Buckminster Fuller Institute
* [Geodesic dome](https://en.wikipedia.org/wiki/Geodesic_dome) on Wikipedia
* [Geodesic polyhedron](https://en.wikipedia.org/wiki/Geodesic_polyhedron) on Wikipedia
* [Explaining Dome Frequency](http://www.domerama.com/dome-basics/explaining-dome-frequency/) by Domerama
* [Geodesic Dome](https://mathworld.wolfram.com/GeodesicDome.html) on Wolfram MathWorld
_Notable software:_
* [Domerama calculators](https://www.domerama.com/calculators/) - strut-length and cover-pattern calculators for domes of various frequencies
_Notable real-world geodesic domes:_
* [Climatron](https://en.wikipedia.org/wiki/Climatron) at the Missouri Botanical Garden in St. Louis, MO, USA. Diameter = 42m (138ft).
* [La Géode](https://en.wikipedia.org/wiki/La_G%C3%A9ode) at the City of Science and Industry in Paris, France. Diameter = 36m (118ft).
* Long Beach Cruise Terminal (formerly The Spruce Goose Dome) in Long Beach, CA, USA. Diameter = 122m (400ft).
* [Matrimandir](https://en.wikipedia.org/wiki/Matrimandir) in Bommayapalayam, India. The building structure is a geodesic dome covered in golden discs. Diameter = 36m (118ft).
* [Montreal Biosphere](https://en.wikipedia.org/wiki/Montreal_Biosphere) in Montreal, Québec, Canada. Designed by Buckminster Fuller himself in 1967. Diameter = 76m (249ft) .
* [Science World building](https://en.wikipedia.org/wiki/Science_World_%28Vancouver%29) in Vancouver, Canada.
* [Spaceship Earth](https://en.wikipedia.org/wiki/Spaceship_Earth_(Epcot)) in the EPCOT theme park at Walt Disney World in Orlando, FL, USA. Diameter = 50m (165ft).
* [The Eden Project](https://en.wikipedia.org/wiki/Eden_Project) in Cornwall, England. Features multiple domes merged together into large, multi-area buildings.
* [The Desert Dome](https://en.wikipedia.org/wiki/Omaha%27s_Henry_Doorly_Zoo_and_Aquarium#Desert_Dome) at the Henry Doorly Zoo and Aquarium in Omaha, NE, USA. Diameter = 70m (230 ft).
---
### Golden angle
> [!NOTE]
> Related to the [golden ratio](#golden-ratio) and [phyllotaxis](#phyllotaxis).
Radial version of the [golden ratio](#golden-ratio). It is the smaller of the two angles created by sectioning the circumference of a circle according to the golden ratio; that is, into two arcs such that the ratio of the length of the smaller arc to the length of the larger arc is the same as the ratio of the length of the larger arc to the full circumference of the circle.
In degrees the angle is approximately `137.5077640500 ...`, or just `137.5` for brevity.
_Articles:_
* [Golden angle](https://en.wikipedia.org/wiki/Golden_angle) on Wikipedia
* [The Golden Angle](http://gofiguremath.org/natures-favorite-math/the-golden-ratio/the-golden-angle/) by Go Figure
_Creative projects:_
* [Golden Angle](http://www.johnedmark.com/phi) sculpture series by John Edmark
---
### Golden ratio
> [!NOTE]
> Related to the [Fibonacci sequence](#fibonacci-sequence).
Also expressed as the Greek letter _phi_ (`φ`), this irrational number pops up when the ratio of two numbers is the same as the ratio of their sum to the largest of the two numbers. It has been observed in many fields of the natural sciences at every scale and is has become associated with aesthetic beauty, giving it a nearly mythic reputation for some.
| Expressed algebraicly | $\varphi = \frac{1 + \sqrt{5}}{2} = 1.6180339887\ldots$ |
| Expressed as line segments |  |
### Implicit surface
A surface defined by an equation in the form of 
. The surface itself is defined by the set of zeros of such a function. Implicit surfaces are infinitely scalable, and are much more smooth / "blobby" than surfaces defined explicitly by vertices and faces. However, they are more difficult and computationally expensive to render, requiring an algorithm like raymarching or [marching cubes](#marching-cubes) in order to represent the surface on a 2D screen.
_Examples of implicit surface equations:_
| Plane | $x+2y-3z+1=0$ |
| Sphere | $x^{2}+y^{2}+z^{2}-4=0$ |
| Torus | $(x^{2}+y^{2}+z^{2}+R^{2}-a^{2})^{2}-4R^{2}(x^{2}+y^{2})=0$ |
| Surface of genus 2 | $2y(y^{2}-3x^{2})(1-z^{2})+(x^{2}+y^{2})^{2}-(9z^{2}-1)(1-z^{2})=0$ |
| Surface of revolution | $x^{2}+y^{2}-(\ln(z+3.2))^{2}-0.02=0$ |
### Inverse and forward kinematics
Equations used to calaculate the positions of a series of rigidly-linked segments (called the _kinematic chain_) based on the location of the end effector, usually located at the tip of the last segment. Useful for robotic systems like drawing machines, robot arms, and more.
**Inverse** kinematics calculate the angles of each linked segment given the desired location of the end effector. Will give you the angles of each segment, which can in turn be converted into motor positions for a robot.
**Forward** kinematics calculate the location of the end effector given the angles and lengths of each linked segment.
_Articles:_
* [Kinematics](https://en.wikipedia.org/wiki/Kinematics) on Wikipedia
* [Inverse kinematics](https://en.wikipedia.org/wiki/Inverse_kinematics) on Wikipedia
* [Forward kinematics](https://en.wikipedia.org/wiki/Forward_kinematics) on Wikipedia
_Videos:_
* [Coding Challenge #64.1: Forward Kinematics](https://www.youtube.com/watch?v=xXjRlEr7AGk) by Daniel Shiffman
* [Coding Challenge #64.2: Inverse Kinematics](https://www.youtube.com/watch?v=hbgDqyy8bIw) b Daniel Shiffman
* [Coding Challenge #64.3: Inverse Kinematics - Fixed Point](https://www.youtube.com/watch?v=RTc6i-7N3ms) by Daniel Shiffman
* [Coding Challenge #64.4: Inverse Kinematics - Multiple](https://www.youtube.com/watch?v=10st01Z0jxc) by Daniel Shiffman
---
### Laplace equation
> [!NOTE]
> Related to [DLA](#diffusion-limited-aggregation-dla), [DBM](#dielectric-breakdown-model-dbm), [Saffman–Taylor instability](#saffmantaylor-instability), [reaction-diffusion](#reaction-diffusion), [minimal surface](#minimal-surface), [fluid simulation](#fluid-simulation), and [Laplace transform](#laplace-transform).
The Laplace equation, $\nabla^2 \varphi = 0$, says that a field's value at any point equals the average of its immediate surroundings - no interior point can be a local bump or dip. It shows up constantly in physics because it's simply the _steady-state_ form of diffusion, heat flow, and potential fields: whenever something free to spread out (heat, concentration, charge, pressure) has finished settling, its value obeys this equation. Solutions are called _harmonic functions_.
That abstractness is exactly why it matters for morphogenesis: several branching growth patterns already covered elsewhere in this list are, mathematically, the same equation wearing different clothes - a family of processes collectively known as **Laplacian growth**.
_Laplacian growth - from equation to organic form:_
Each of these solves the Laplace equation in the region _around_ a growing cluster, then advances the cluster's boundary fastest wherever the resulting field's gradient is steepest:
* [Diffusion-limited aggregation (DLA)](#diffusion-limited-aggregation-dla) - random walkers stick where they first touch the cluster. In the continuum limit, the probability of a walker arriving at any boundary point is proportional to the gradient of the harmonic concentration field around the cluster - DLA is the stochastic, particle-based way of sampling a Laplacian growth process.
* [Dielectric breakdown model (DBM)](#dielectric-breakdown-model-dbm) - solves the Laplace equation directly for an electric potential field around the growing discharge, then grows each boundary point in proportion to the local field gradient raised to a tunable power - the same idea as DLA, made explicit and continuous.
* [Saffman–Taylor instability](#saffmantaylor-instability) (viscous fingering) - inside a [Hele-Shaw cell](#hele-shaw-cell), the fluid pressure field obeys the Laplace equation (via Darcy's law), and the identical "grow fastest where the gradient is steepest" feedback produces the same branching, finger-like interface.
This is why DLA clusters, electrical discharge patterns, and viscous fingers all look so similar despite arising from unrelated physics - they're all boundaries growing into a harmonic field, differing only in their noise and boundary conditions.
_Key terms:_
* Laplacian operator ($\nabla^2$ or $\Delta$) - the divergence of the gradient; measures how much a point's value differs from the average of its immediate surroundings.
* Harmonic function - any solution to the Laplace equation; has no local maxima or minima except at the domain's boundary (the "mean value property").
* Poisson equation - the Laplace equation with a source term ($\nabla^2 \varphi = f$); used whenever the field being solved has "generators" (charge, heat sources, image gradients) rather than being purely diffusive.
* Boundary conditions - since the Laplace equation alone has infinitely many solutions, a specific field is picked out by fixing its values (Dirichlet) or its gradient (Neumann) on the domain's boundary - the growing cluster's surface, in Laplacian growth models.
* Laplacian growth - the general term for a growth process where the interface advances in proportion to the gradient of a harmonic field solved in the region ahead of it.
* Laplacian smoothing (mesh relaxation) - the discrete, iterative graphics technique of averaging each mesh vertex with its neighbors; converges toward a discrete solution of the Laplace equation.
_Articles:_
* [Laplace's equation](https://en.wikipedia.org/wiki/Laplace%27s_equation) on Wikipedia
* [Harmonic function](https://en.wikipedia.org/wiki/Harmonic_function) on Wikipedia
* [Laplacian smoothing](https://en.wikipedia.org/wiki/Laplacian_smoothing) on Wikipedia
* [Fast Simulation of Laplacian Growth](https://faculty.cc.gatech.edu/~turk/bio_sim/articles/laplacian_growth.pdf) (PDF) by Theodore Kim et al. Academic review connecting DLA, dielectric breakdown, and viscous fingering as a single family of processes
* [Discrete Differential Geometry: An Applied Introduction](https://brickisland.net/ddg-web/) by Keenan Crane - course notes covering the discrete Laplacian as "the Swiss army knife of geometry processing," including mesh smoothing
_Videos:_
* [Harmonic Functions](https://www.khanacademy.org/math/multivariable-calculus/multivariable-derivatives/laplacian/v/harmonic-functions) from Khan Academy - short, visual introduction to the Laplacian and harmonic functions
_Code projects:_
* [geometry-processing-smoothing](https://github.com/alecjacobson/geometry-processing-smoothing) by Alec Jacobson - reference implementation of Laplacian mesh smoothing from a geometry processing course
---
### Laplace transform
> [!NOTE]
> Related to [Laplace equation](#laplace-equation)
Mathematical transform that converts a function of time into a function of complex frequency, turning differential equations into algebraic ones that are often easier to solve. It is widely used in engineering, physics, and control theory to analyze dynamic systems and their stability, resonance, and response.
The Laplace transform maps a time-domain function $f(t)$ to a frequency-domain function $F(s)$. In this form, differentiation becomes multiplication and convolution becomes multiplication, making many system problems easier to analyze. Its inverse recovers the time-domain solution for applications such as growth dynamics, signal propagation, and feedback-driven behavior.
_Definition:_
$$F(s) = \mathcal{L}\{f(t)\} = \int_0^{\infty} e^{-st} f(t) \, dt$$
Where $s = \sigma + i\omega$ is a complex frequency variable, $t$ is time, and the integral converges for sufficiently large $\sigma$.
_Key properties:_
| Property | Formula | Description |
|---|---|---|
| Linearity | $\mathcal{L}\{af(t) + bg(t)\} = a\mathcal{L}\{f(t)\} + b\mathcal{L}\{g(t)\}$ | Sum transforms equal sum of transforms |
| Differentiation rule | $\mathcal{L}\{f'(t)\} = sF(s) - f(0)$ | Converts derivatives to algebraic operations |
| Integration rule | $\mathcal{L}\{\int_0^t f(\tau)\,d\tau\} = \frac{F(s)}{s}$ | Converts integrals to division by $s$ |
| Convolution theorem | $\mathcal{L}\{f(t) * g(t)\} = F(s)G(s)$ | Converts convolution to multiplication |
| Final value theorem | $\lim_{t \to \infty} f(t) = \lim_{s \to 0} sF(s)$ | Determines steady-state behavior |
| Initial value theorem | $f(0^+) = \lim_{s \to \infty} sF(s)$ | Determines initial conditions |
| Frequency shifting | $\mathcal{L}\{e^{at}f(t)\} = F(s-a)$ | Scaling exponential shifts frequency |
| Time shifting | $\mathcal{L}\{f(t-a)u(t-a)\} = e^{-as}F(s)$ | Delay in time domain multiplies by $e^{-as}$ |
_Key terms:_
* Region of convergence (ROC) - the set of complex $s$ values for which the Laplace integral converges
* Pole - a value of $s$ where $F(s)$ becomes infinite; poles determine system stability and response characteristics
* Zero - a value of $s$ where $F(s)$ equals zero
* Transfer function - the Laplace transform of a system's impulse response; describes how a system responds to inputs
* Inverse Laplace transform - converting from frequency domain back to time domain; often done via partial fraction decomposition
* Partial fraction decomposition - breaking a complex rational function into simpler fractions to facilitate inverse transformation
_Articles:_
* [Laplace transform](https://en.wikipedia.org/wiki/Laplace_transform) on Wikipedia
* [Laplace Transform](http://mathworld.wolfram.com/LaplaceTransform.html) on Wolfram MathWorld
* [Laplace Transform Tables and Properties](https://tutorial.math.lamar.edu/Classes/DE/Laplace_Transforms.aspx) by Paul's Online Math Notes
* [Introduction to the Laplace Transform](https://ocw.mit.edu/courses/18-03-differential-equations-spring-2010/) from MIT OpenCourseWare (differential equations course)
---
### Lissajous curves
Also known as Bowditch curves, these figures plot the trajectories of a point as it follows the path of two simultaneous sinusoidal motions.
Can be created using various physical systems including [oscilloscopes](https://www.youtube.com/watch?v=t6nGiBzGLD8), [harmonographs](https://en.wikipedia.org/wiki/Harmonograph), and more.
_Equations:_
$$x = a \sin t,\quad y = b \sin(nt + \varphi)$$
$$0 \leq \varphi \leq \frac{\pi}{2}, \quad n \geq 1$$
_Articles:_
* [Lissajous curve](https://en.wikipedia.org/wiki/Lissajous_curve) on Wikipedia
* [Lissajous curve](https://www.mathcurve.com/courbes2d.gb/lissajous/lissajous.shtml) from MathCurve
* [Lissajous Curves](http://datagenetics.com/blog/april22015/index.html) from DataGenetics
_Videos:_
* [Coding Challenge #116: Lissajous Curve Table](https://www.youtube.com/watch?v=--6eyLO78CY) by Daniel Shiffman ([Github repo](https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_116_Lissajous) with source code for p5.js and Processing)
* [#48: Basics of Lissajous Patterns on an Oscilloscope](https://www.youtube.com/watch?v=t6nGiBzGLD8) by w2aew
---
### Mass-spring system
> [!NOTE]
> Related to [soft-body physics](#soft-body-physics), [cloth simulation](#cloth-simulation), [Verlet physics](#verlet-physics), and [physics engines](#physics-engine).
A mass-spring system is a general mathematical model for deformable bodies: a graph of point masses connected by springs that obey [Hooke's law](https://en.wikipedia.org/wiki/Hooke%27s_law) (restoring force proportional to displacement from a rest length). It's one of the oldest and most widely reused abstractions in computational physics, showing up not just in computer graphics but in structural engineering (truss analysis), molecular dynamics (bond modeling), and biomechanics (tissue and muscle models). Its appeal is that a small number of local rules - distance constraints and simple forces - can produce believable global deformation without solving a full continuum mechanics problem.
In graphics and simulation, mass-spring systems are the conceptual backbone of [cloth simulation](#cloth-simulation), rope/hair simulation, and soft-body deformation, and are typically stepped forward with [Verlet integration](#verlet-physics) for stability. Real-time applications commonly layer three kinds of springs to control different deformation modes: structural springs (resist stretching), shear springs (resist skewing), and bend springs (resist folding).
_Algorithm at a glance:_
_\* indicates a potential simulation parameter_
1. Represent the body as a graph of point masses, each with position, velocity, and mass\*.
2. Connect masses with springs, each with a rest length and stiffness\*.
3. For each spring, compute the restoring force: `F = stiffness × (current_distance - rest_length)`.
4. Add a damping force proportional to relative velocity\*: `F_damping = damping × relative_velocity`.
5. Sum spring, damping, and external forces (gravity, wind, etc) on each mass.
6. Integrate mass positions forward, commonly with [Verlet integration](#verlet-physics).
7. Detect and resolve collisions with rigid bodies and self-collisions.
8. Repeat until the system settles or the simulation ends.
_Key terms:_
* [Hooke's law](https://en.wikipedia.org/wiki/Hooke%27s_law) - the restoring force in a spring is proportional to its displacement from rest length, scaled by a stiffness constant.
* Rest length - the preferred distance between two connected masses; springs pull toward this distance.
* Stiffness (spring constant) - how strongly a spring resists stretching; higher values resist deformation more.
* Damping - dissipative force proportional to velocity; prevents infinite oscillation and lets systems settle.
* Structural constraints - springs between nearest neighbors; define topology and resist stretching.
* Shear constraints - diagonal springs between diagonal neighbors; resist skewing.
* Bend constraints - springs between masses separated by one neighbor; resist folding/creasing.
_Articles:_
* [Mass-Spring Model](https://interactivecomputergraphics.github.io/physics-simulation/examples/spring_plot.html) - interactive visualization of spring-mass dynamics
* [Advanced Character Physics](https://www.gamedev.net/tutorials/programming/math-and-physics/advanced-character-physics-r3293/) by Thomas Jakobsen - the classic paper connecting Verlet integration to mass-spring constraint systems
* [Real Time Simulation of Soft Objects Using Mass-Spring System](https://www.cs.rpi.edu/~cutler/classes/advancedgraphics/S17/final_projects/haoxin_brandon.pdf) (PDF) - academic paper on soft-body simulation
_Code projects:_
* [Rope Simulation (CS184 Discussion)](https://github.com/cal-cs184/rope_simulation) - basic rope/cloth mass-spring implementation
* [Cloth Simulation](https://andrewdcampbell.github.io/clothsim/) - interactive cloth simulator demonstrating mass-spring constraints
* [Mass-Spring System for Soft-Body Simulation](https://github.com/YukunXia/Mass-Spring-System-for-Soft-Body-Simulation) - 3D soft-body physics implementation
_Videos:_
* [Coding Challenge #26: Spring Physics](https://www.youtube.com/watch?v=4hIUAoB2VVE) by The Coding Train - implementing mass-spring systems in p5.js
---
### Medial axis
The medial axis is sort of like the "skeleton" of a shape. It consists of a set of lines and curves upon which every point is equidistant between at least one closest point on the shape's boundary. In 2D this skeleton can also be thought of as a set of lines/curves whose points are the centers of circles that are tangent to at least two points on the shape's boundary.
Has applications in computer vision, pose estimation, 2D/3D character rigging, architecture, BIM (escape route optimization), and more.
_Related terms:_
* Medial-axis transform - medial axis together with the associated radius function of the maximally inscribed discs. Can be used to reconstruct a shape.
* [Topological Skeleton](https://en.wikipedia.org/wiki/Topological_skeleton)
* [Straight skeleton](https://en.wikipedia.org/wiki/Straight_skeleton) - similar to medial, except always is made up of straight line segments whereas medial axis may contain curves.
* [Scale Axis Transform](http://www.balintmiklos.com/scale-axis/theory_socg_2009.html) - generalization of medial axis transform
_Articles:_
* [Medial axis](https://en.wikipedia.org/wiki/Medial_axis) on Wikipedia
* ["A transformation for extracting new descriptors of shape"](http://pageperso.lif.univ-mrs.fr/~edouard.thiel/rech/1967-blum.pdf) by Henry Blum
_Notable Tools:_
* [Skeleton-Tracing](https://github.com/LingDong-/skeleton-tracing), a code library for computing topological skeletons as a set of polylines from binary images. Provides implementations in C, C++, Java, JavaScript, Python, Go, C#/Unity, Swift, Rust, Julia, Processing, and OpenFrameworks.
---
### Minimal surface
> [!NOTE]
> Related to [Laplace equation](#laplace-equation).
A [minimal surface](https://en.wikipedia.org/wiki/Minimal_surface) is a surface that locally minimizes area, which means it settles into the smallest possible shape for a given boundary while keeping its mean curvature equal to zero. Minimal surfaces show up in architecture, material design, geometry, and optimization, and they are useful whenever you want a smooth surface or membrane that uses as little area as possible.
A soap film stretched across a wire frame is the classic physical example: the film naturally relaxes into a shape that balances tension everywhere. Frei Otto's [soap-bubble experiments](https://www.metalocus.es/en/news/frei-otto-video-modeling-soap-films) were important for showing how these forms emerge in the real world.
_Equations:_
| Equation | Explanation |
| --- | --- |
| $H = (k_1 + k_2) / 2 = 0$
### Packing problems
Class of optimization problems that involve determining efficient ways to arrange (_pack_) objects into containers. Packing problems can be tackled using discrete mathematical methods, physics systems (as seen in Nervous System's [Kinematics](https://n-e-r-v-o-u-s.com/blog/?p=7162) series), and even genetic algorithms and machine learning.
Has major applications in digital fabrication, manufacturing, and shipping logistics where material and space usage is directly related to costs. In 2D, packing/nesting problem solutions are useful for minimizing waste material in sheet goods like plywood and sheet steel, even for hobbyists. In 3D these solutions are useful for fitting as many objects as possible into 3D printer build envelopes (see article from [Sculpteo](https://www.sculpteo.com/blog/2017/07/19/3d-printing-software-how-we-optimize-our-batch-using-our-nesting-tool/)).
_Related terms:_
* [Nesting (process)](https://en.wikipedia.org/wiki/Nesting_(process))
_Articles:_
* [Packing problems](https://en.wikipedia.org/wiki/Packing_problems) on Wikipedia
* [Random space filling of the plane](http://paulbourke.net/fractals/randomtile/) by Paul Bourke
* [Optimal Packing](http://datagenetics.com/blog/june32014/index.html) from Data Genetics
* [Circle Packing](http://mathworld.wolfram.com/CirclePacking.html) on Wolfram MathWorld
* [Bin packing problem](https://en.wikipedia.org/wiki/Bin_packing_problem) on Wikipedia
* [Sphere packing](https://en.wikipedia.org/wiki/Sphere_packing) on Wikipedia
* [Close-packing of equal spheres](https://en.wikipedia.org/wiki/Close-packing_of_equal_spheres) on Wikipedia
* [Packing Problems](https://www.ime.usp.br/~egbirgin/packing/) - collection of papers by Ernesto Birgin and collaborators
_Notable tools:_
* [RhinoNest](https://www.tdmsolutions.com/rhinonest/) (Rhino)
* [DeepNest](https://deepnest.io/) (Standalone)
* [SVGnest](https://svgnest.com/) (Web app)
_Videos:_
* [Coding Challenge #50.1: Animated Circle Packing - Part 1](https://www.youtube.com/watch?v=QHEQuoIKgNE) by Daniel Shiffman
---
### Percolation theory
Mathematical framework that studies the behavior of connected clusters in random networks. At its core, percolation explores the threshold at which a system transitions from isolated fragments to a connected network spanning the entire space - a critical phenomenon with applications in material science, epidemiology, network analysis, and growth simulation.
The classical model places sites or bonds randomly on a grid, each with some occupation probability $p$. As $p$ increases, small disconnected clusters begin to merge and grow. At a critical threshold $p_c$ (the _percolation threshold_), a “giant component” suddenly emerges that connects from one side of the system to the opposite side. Above the threshold, clusters merge rapidly; below it, they remain fragmented. This sharp transition is a classic example of a phase transition in physics.
_Key concepts:_
* Percolation threshold ($p_c$) - the occupation probability at which a spanning cluster first appears. The value depends on the lattice type: for square lattices $p_c \approx 0.593$ (bond) or $0.589$ (site), for triangular lattices $p_c \approx 0.5$ (bond), etc.
* Cluster - a connected group of occupied sites or bonds.
* Giant component - the largest, system-spanning cluster that emerges above the threshold.
* Lattice types - square, triangular, hexagonal, random graphs, and others; each has different percolation thresholds and scaling behavior.
* Major models:
* Bond (Bernoulli) percolation - bonds (edges) between fixed sites are randomly occupied; relates to fluid flow through porous media.
* Site percolation - individual sites (nodes) are randomly occupied; relates to disease spread or forest fire models.
* Mixed percolation - combines site and bond percolation in one model, requiring both the sites and the bonds connecting them to be open for a cluster to form.
* Bootstrap percolation - starting from a random set of occupied sites, empty sites are iteratively "infected" once they have at least $k$ occupied neighbors, repeating until no more sites change; models cascading activation like infection spread or social contagion.
* Inhomogeneous percolation - the occupation probability $p$ varies from site to site (or bond to bond) instead of being uniform, e.g. to model spatially-varying material properties.
* Long-range percolation - bonds can connect any two sites, not just nearest neighbors, with connection probability typically decaying with distance (often as a power law); can percolate via rare long "jumps" even below the classical threshold.
* Directed percolation (oriented percolation) - bonds/sites can only be traversed along a preferred direction (e.g. "downward" through time); models epidemic spreading and non-equilibrium phase transitions.
* Continuum percolation - occupation is defined over continuous space rather than a discrete lattice, e.g. overlapping disks or spheres; models material conductivity and wireless network coverage.
* Germ-grain model - general stochastic-geometry framework of "germs" (points) dressed with "grains" (shapes) that may be correlated with one another or their surroundings.
* Boolean model (Poisson Boolean model) - the germ-grain model's independent special case: germs scattered via a Poisson process, each dressed with an independent random grain; percolation occurs when grains overlap into a spanning cluster.
* Disk model (Gilbert disk model) - special case of the Boolean model where every grain is a disk of fixed or random radius; used for random geometric graphs and wireless/sensor network connectivity.
* Random-connection model - generalizes the Boolean/disk model into a random graph: any two points connect with a probability given by a distance-dependent "connection function," rather than by fixed-radius grain overlap.
* Invasion percolation - growth advances by always occupying the weakest/most accessible available site rather than a random one; models fluid displacement in porous media.
* First-passage percolation - instead of open/closed sites or bonds, each bond is assigned a random "passage time"; studies how quickly a fluid spreads from a source along the fastest weighted paths, producing random growth shapes.
* Random-cluster model (Fortuin–Kasteleyn model) - generalizes percolation with an extra parameter $q$ that continuously interpolates between percolation ($q=1$), the Ising model ($q=2$), and the Potts model ($q>2$).
* Critical exponents - power-law relationships describing cluster size distribution, correlation length, and other properties near $p_c$. These exponents are universal across many percolation models.
* Universality class - percolation models grouped by shared critical exponent values; a hallmark of statistical physics.
Percolation can model porous media (oil migration through rock), disease spread (how infections propagate through a population), forest fires (how rapidly fires spread through dense vegetation), and network robustness (how many nodes can fail before connectivity is lost). In the context of morphogenesis, percolation-based growth can generate branching patterns, fragmented structures, and networks with natural-looking interconnectivity.
_Articles:_
* [Percolation theory](https://en.wikipedia.org/wiki/Percolation_theory) on Wikipedia
* [Percolation](http://paulbourke.net/fractals/percolation/) by Paul Bourke
* [Percolation Threshold](http://mathworld.wolfram.com/PercolationThreshold.html) on Wolfram MathWorld
_Code projects and interactive tools:_
* [“Barista's Secret”: Percolation on a lattice](https://www.complexity-explorables.org/explorables/baristas-secret/) by Dirk Brockmann - interactive visualization of site percolation on a square lattice
* [Red Blob Games - Percolation](https://www.redblobgames.com/grids/hexagons/) - explores percolation on different grid types (mentions percolation effects in hexagonal grids)
---
### Phyllotaxis
> [!NOTE]
> Related topics include the [golden ratio](#golden-ratio), the [golden angle](#golden-angle), and the [Fibonacci sequence](#fibonacci-sequence).
Refers to the arrangement (_taxis_) of leaves (_phyllo_) on a plant stem. Also can refer to seed arrangements and succulent geometry.
_Types:_
* Opposite - two leaves arise from the stem at the same level on opposite sides of the stem
* Alternate - each leaf arises at a different point (node) on the stem
* [Whorled](https://en.wikipedia.org/wiki/Whorl_(botany)) - arrangement of leaves that radiate from a single point and surround or wrap around the stem, as seen in the thumbnail for this section.
* Distichous - special case of either opposite or alternate leaf arrangement where the leaves on a stem are arranged in two vertical columns on opposite sides of the stem
* Decussate - occurs when successsive pairs of leaves arranged in the opposite pattern are 90 degrees apart, as in [Aizoaceae](https://en.wikipedia.org/wiki/Aizoaceae) family
_Articles:_
* [Phyllotaxis](https://en.wikipedia.org/wiki/Phyllotaxis) on Wikipedia
* [Chapter 4: Phyllotaxis](http://algorithmicbotany.org/papers/abop/abop-ch4.pdf) from Algorithmic Botany book
* [Phyllotaxis](http://mathworld.wolfram.com/Phyllotaxis.html) on Wolfram MathWorld
_Code projects:_
* [ofxPhyllotaxis](https://github.com/edap/ofxPhyllotaxis) by Davide Prati (edap)
_Videos:_
* [Coding Challenge #30: Phyllotaxis](https://www.youtube.com/watch?v=KWoJgHFYWxY) by Daniel Shiffman
---
### Platonic solids
> [!NOTE]
> Related to [polyhedra](#polyhedra) and [Archimedean solids](#archimedean-solids).
Set of regular, convex polyhedra constructed using congruent, regular polygonal faces with the same number of faces meeting at each vertex. Euclid (and perhaps [Theaetetus](https://en.wikipedia.org/wiki/Theaetetus_(mathematician)) proved mathematically that there are only five shapes that fit this criteria (below).
| Name | Polygon type | Faces | Edges | Vertices | Image |
|--- |--- |--- |--- |--- |--- |
| Tetrahedron | Triangle | 4 | 6 | 4 | 
|
| Cube | Square | 6 | 12 | 8 | 
|
| Octahedron | Triangle | 8 | 12 | 6 | 
|
| Dodecahedron | Pentagon | 12 | 30 | 20 | 
|
| Icosahedron | Triangle | 20 | 30 | 12 | 
|
_Articles:_
* [Platonic solid](https://en.wikipedia.org/wiki/Platonic_solid) on Wikipedia
* [Platonic Solids](https://tutors.com/math-tutors/geometry-help/platonic-solids) on Tutors.com
_Videos:_
* [5 Platonic Solids](https://www.youtube.com/watch?v=gVzu1_12FUc) by Numberphile
---
### Polyhedra
> [!NOTE]
> Related to [Platonic solids](#platonic-solids), [Archimedean solids](#archimedean-solids), [geodesic domes](#geodesic-dome), and [Conway operators](#conway-operators).
A polyhedron is a solid bounded by flat polygonal faces, straight edges, and sharp vertices - the [Platonic](#platonic-solids) and [Archimedean solids](#archimedean-solids) are just the two best-known families in a much larger space of shapes. For generative artists, polyhedra are a useful design space precisely because they're so constrained: a handful of construction rules (regular faces, identical vertices, symmetric arrangements) generate a finite, well-catalogued set of "correct-looking" forms, which is why the same few solids keep reappearing as base meshes for subdivision, [geodesic domes](#geodesic-dome), and procedural modeling more broadly.
_Key concepts:_
* Convex vs. concave - convex polyhedra bulge outward everywhere with no self-intersections; concave ones have indentations or intersecting faces.
* Classes - groupings based on construction rules, e.g. Platonic, Archimedean, Catalan, Kepler-Poinsot, Johnson, prisms/antiprisms, and near-misses.
* Symmetry - when a shape can be rotated or reflected and still look exactly the same.
* Stellation and facetting - dual operations for making new polyhedra from old ones: stellation extends face planes outward; facetting cuts new faces from existing vertices.
_Major classes:_
* [Platonic solids](#platonic-solids) - the 5 regular convex polyhedra; one type of regular polygon face, identical arrangement at every vertex.
* [Archimedean solids](#archimedean-solids) - 13 semi-regular convex polyhedra with two or more types of regular polygon faces meeting identically at every vertex.
* [Catalan solids](https://en.wikipedia.org/wiki/Catalan_solid) - the 13 duals of the Archimedean solids; face-transitive rather than vertex-transitive, so their faces aren't regular polygons but their vertex figures are.
* [Kepler-Poinsot solids](https://en.wikipedia.org/wiki/Kepler%E2%80%93Poinsot_polyhedron) - the 4 regular star polyhedra (small/great stellated dodecahedron, great dodecahedron, great icosahedron); self-intersecting stellations or facettings of the dodecahedron and icosahedron.
* [Johnson solids](https://en.wikipedia.org/wiki/Johnson_solid) - the 92 remaining convex solids with regular polygon faces that aren't vertex-transitive (i.e. everything left once Platonic, Archimedean, prisms, and antiprisms are excluded).
* [Prisms and antiprisms](https://en.wikipedia.org/wiki/Prism_(geometry)) - two infinite families of uniform polyhedra: two parallel _n_-gon faces connected by a ring of squares (prism) or triangles (antiprism).
* Near-misses - convex solids with faces so close to regular that they read as "correct" at a glance (e.g. the soccer-ball-style truncated icosahedron variants used in geodesic-adjacent design); popular in architecture and fabrication because slightly irregular faces can simplify paneling or tiling.
_Symmetry:_
A shape has symmetry when it can be rotated or reflected and still look exactly the same - spin a cube 90° around an axis through two opposite faces and you can't tell it moved. The full set of ways a shape can do this is called its symmetry group, and the larger it is, the more interchangeable the shape's faces, edges, and vertices look.
Highly symmetric polyhedra fall into just three of these groups (doubled again with mirror reflections) - part of why the same few base shapes keep recurring in generative work:
* [Tetrahedral symmetry](https://en.wikipedia.org/wiki/Tetrahedral_symmetry) - 12 rotations (24 with reflections); the symmetry of the tetrahedron.
* [Octahedral symmetry](https://en.wikipedia.org/wiki/Point_groups_in_three_dimensions) - 24 rotations (48 with reflections); shared by the cube and octahedron since they're duals of each other.
* [Icosahedral symmetry](https://en.wikipedia.org/wiki/Icosahedral_symmetry) - 60 rotations (120 with reflections); shared by the dodecahedron and icosahedron, and the reason icosahedral subdivision is the standard approach for [geodesic domes](#geodesic-dome).
A polyhedron's symmetry group also determines whether every vertex looks like every other vertex (isogonal, true of the Platonic and Archimedean solids), every face looks like every other face (isohedral, true of the Platonic and Catalan solids), or every edge looks like every other edge (isotoxal).
_Stellation and facetting:_
These are dual, opposite operations for generating new polyhedra from existing ones:
* Stellation - extending a polyhedron's face planes outward until they intersect each other again, producing a larger, usually self-intersecting shape. The four Kepler-Poinsot solids are the only regular stellations of the dodecahedron and icosahedron, but a single seed shape (like the icosahedron) can have dozens of named stellations.
* Facetting - creating new faces using only a polyhedron's existing vertices, without adding any new ones - effectively "cutting into" the solid rather than extending outward.
_Key terms:_
* Face, edge, vertex - the three basic elements of a polyhedron.
* [Euler's formula](https://en.wikipedia.org/wiki/Euler%27s_formula) - `V - E + F = 2` for any simple convex polyhedron; a quick sanity check for procedurally generated meshes.
* [Dual polyhedron](https://en.wikipedia.org/wiki/Dual_polyhedron) - swapping faces and vertices produces a shape's dual (cube ↔ octahedron, dodecahedron ↔ icosahedron, tetrahedron ↔ itself).
* [Uniform polyhedron](https://en.wikipedia.org/wiki/Uniform_polyhedron) - vertex-transitive with regular polygon faces; covers the Platonic and Archimedean solids, prisms, antiprisms, and their non-convex "star" counterparts.
* [Schläfli symbol](https://en.wikipedia.org/wiki/Schl%C3%A4fli_symbol) - shorthand `{p, q}` describing a regular polyhedron by its face polygon (_p_-gon) and how many meet at each vertex (_q_); star polyhedra use fractions, e.g. `{5/2, 5}` for the small stellated dodecahedron.
* [Vertex figure](https://en.wikipedia.org/wiki/Vertex_figure) - the cross-section shape formed by slicing off a vertex; used to classify uniform polyhedra by which polygons meet there.
* [Convex hull](https://en.wikipedia.org/wiki/Convex_hull) - the smallest convex shape enclosing a set of points; a common generative technique for deriving a convex polyhedron from a symmetric point distribution.
_Articles:_
* [Polyhedron](https://en.wikipedia.org/wiki/Polyhedron) on Wikipedia
* [Point groups in three dimensions](https://en.wikipedia.org/wiki/Point_groups_in_three_dimensions) on Wikipedia - overview of the tetrahedral, octahedral, and icosahedral symmetry groups
* [Stellation](https://en.wikipedia.org/wiki/Stellation) on Wikipedia
* [Faceting](https://en.wikipedia.org/wiki/Faceting) on Wikipedia
* [Stellations](https://www.georgehart.com/virtual-polyhedra/stellations-info.html) by George Hart - short illustrated explanation of the stellation process
* [Visual Polyhedra](https://dmccooey.com/polyhedra/) by David McCooey - interactive 3D models organized by class (Platonic, Archimedean, Catalan, Kepler-Poinsot, Johnson, and more), with downloadable geometry data
* [Virtual Polyhedra: The Encyclopedia of Polyhedra](https://www.georgehart.com/virtual-polyhedra/vp.html) by George Hart
_Videos:_
* [Kepler-Poinsot Polyhedra](https://www.youtube.com/watch?v=Y8_Xx961_oI) - overview of the four regular star polyhedra
_Notable tools:_
* [Stella](https://www.software3d.com/Stella.php) by Robert Webb - dedicated polyhedra exploration software (Great Stella, Small Stella, Stella4D) supporting stellation, facetting, augmentation, dualization, convex hulls, and printable nets
* [Antiprism](https://www.antiprism.com/) by Adrian Rossiter - open-source command-line toolkit for generating, transforming, and converting polyhedra ([GitHub](https://github.com/antiprism/antiprism))
* [Polyhedronisme](https://levskaya.github.io/polyhedronisme/) by Anselm Levskaya - web app for building polyhedra from a seed shape using [Conway polyhedron notation](https://en.wikipedia.org/wiki/Conway_polyhedron_notation) operators
_Code projects:_
* [polyhedronisme](https://github.com/levskaya/polyhedronisme) - source code for the Conway-notation polyhedron builder above
* [PolyJS](https://matthewarcus.github.io/polyjs/) ([GitHub](https://github.com/matthewarcus/polyjs)) by Matthew Arcus - generates and animates uniform polyhedra and compounds in Three.js using the Wythoff construction
* [Polyhedra (Three.js)](https://stemkoski.github.io/Three.js/Polyhedra.html) by Lee Stemkoski - renders polyhedra using vertex/face data from George Hart's polyhedra encyclopedia
---
### Saffman-Taylor instability
> [!NOTE]
> Related to [DBM](#dielectric-breakdown-model-dbm), [DLA](#diffusion-limited-aggregation-dla), [differential growth](#differential-growth), [reaction-diffusion](#reaction-diffusion), [fluid simulation](#fluid-simulation), [Hele-Shaw cells](#hele-shaw-cell), and [Laplace equation](#laplace-equation)
Also known as viscous fingering, this is a fluid dynamics instability that occurs at the interface between two fluids of different viscosity when a less viscous fluid is pushed into a more viscous one - inside a narrow gap such as a [Hele-Shaw cell](#hele-shaw-cell), or through a porous medium. Rather than advancing as a flat front, the interface spontaneously breaks up into branching, finger-like intrusions.
The instability is a positive feedback loop: any small bump that forms on the interface sits in a region of lower flow resistance, so it advances faster than its surroundings, growing further ahead and widening into a finger; the same feedback then acts along the flanks of that finger, splitting its tip and producing a branching structure reminiscent of [diffusion-limited aggregation](#diffusion-limited-aggregation-dla) and the [dielectric breakdown model](#dielectric-breakdown-model-dbm). Interfacial tension between the two fluids counteracts this, damping out short-wavelength wrinkles and setting a characteristic finger width - the balance between the two effects selects the fairly regular finger spacing seen in real experiments.
_Key terms:_
* Viscous fingering - the common, descriptive name for the same phenomenon.
* Mobility ratio - ratio between the two fluids' viscosities (or, in a porous medium, permeabilities); the interface is unstable only when the injected fluid is less viscous than the fluid it displaces.
* [Hele-Shaw flow](https://en.wikipedia.org/wiki/Hele-Shaw_flow) - the mathematical description of flow through the thin gap of a [Hele-Shaw cell](#hele-shaw-cell), from which the instability was originally derived.
* Interfacial (surface) tension - force resisting curvature of the interface; suppresses high-frequency wrinkles and sets a preferred finger width/wavelength.
* Tip-splitting - the process by which a growing finger becomes unstable at its own tip and divides into two smaller fingers, driving the fractal branching seen in the radial configuration.
* Channel vs. radial geometry - the two most common experimental setups: injection along a straight channel typically produces one dominant "Saffman–Taylor finger," while injection from a central point (radial) produces repeated tip-splitting into many fingers.
_DIY experiments:_
Viscous fingering can be observed with everyday materials without specialized equipment. When two surfaces are slowly peeled or pulled apart with a thin viscous layer (honey, jam, corn syrup, or hand lotion) between them, the less viscous fluid (air) displaces the viscous layer, creating fingerlike flow patterns at the retreating interface. The same effect occurs in setups such as:
* Slowly peeling apart two wet pieces of paper
* Separating two wet glass plates or acrylic sheets
* Pulling apart plastic wrap or film from a surface coated with a viscous substance
* Lifting a glass plate from a table with a thin layer of honey, oil, or gel underneath
These "peeling" setups exhibit viscous fingering because the viscous fluid resists the air's advance, creating an unstable interface that spontaneously breaks into fingers. This is closely related to the [lifted Hele-Shaw cell](#hele-shaw-cell) concept—in both cases, viscous resistance shapes fluid interfaces during separation or displacement, revealing the same underlying physics.
_Articles:_
* [Saffman–Taylor instability](https://en.wikipedia.org/wiki/Saffman%E2%80%93Taylor_instability) on Wikipedia
* [The penetration of a fluid into a porous medium or Hele-Shaw cell containing a more viscous liquid](https://doi.org/10.1098/rspa.1958.0085) (1958) by Philip Saffman and G. I. Taylor. The original paper.
* [Viscous Fingering in Porous Media](https://doi.org/10.1146/annurev.fl.19.010187.001415) (1987) by G. M. Homsy. Widely-cited review of the phenomenon.
---
### Spherical harmonics
> [!NOTE]
> Related to [Fourier series](#fourier-series)
Spherical harmonics are a set of special functions defined on the surface of a sphere that form a complete, orthonormal basis - meaning any reasonably well-behaved function over the sphere (e.g. a bumpy radius, a lighting environment, a temperature field) can be reconstructed as a weighted sum of them, in the same way a [Fourier series](#fourier-series) reconstructs a periodic signal from sines and cosines. They arise naturally as the angular part of the solution to Laplace's equation in spherical coordinates, which is why they show up throughout physics wherever spherical symmetry is involved - gravitational and electric potentials, atomic orbitals, geodesy, and the cosmic microwave background.
Each spherical harmonic is indexed by a degree $l$ and an order $m$, and looks like a pattern of positive and negative lobes tiling the sphere; low-degree harmonics vary slowly across the surface (capturing broad, low-frequency features) while higher-degree harmonics oscillate more rapidly (capturing fine detail) - directly analogous to how low vs. high frequency terms behave in a Fourier series. This makes them a useful tool for morphogenesis and shape modeling: an arbitrary blob-like or organic 3D form can be approximated, generated, or smoothly deformed by manipulating just a handful of spherical harmonic coefficients instead of a dense mesh.
_Key terms:_
* Degree ($l$) and order ($m$) - indices identifying each spherical harmonic; the degree controls how many nodal lines (angular frequency) a harmonic has, while the order controls their orientation around the polar axis.
* [Legendre polynomials](https://en.wikipedia.org/wiki/Legendre_polynomials) (and associated Legendre functions) - the family of functions used to build the latitude (polar-angle) part of each spherical harmonic.
* Real vs. complex spherical harmonics - two equivalent bases for the same functions; real harmonics are more common in graphics and engineering, complex ones in quantum mechanics.
* [Multipole expansion](https://en.wikipedia.org/wiki/Multipole_expansion) - representing a field (gravitational, electric, etc.) as a sum of spherical harmonics weighted by coefficients, ordered from coarse (monopole/dipole) to fine detail.
* Precomputed radiance transfer (PRT) - computer graphics technique that stores lighting/shading information as a small set of spherical harmonic coefficients for fast, approximate real-time rendering.
* SPHARM (spherical harmonic shape description) - representing an arbitrary closed 3D surface, such as an organic blob or biological structure, as a set of spherical harmonic coefficients; used for shape analysis, comparison, and generative modeling.
_Articles:_
* [Spherical harmonics](https://en.wikipedia.org/wiki/Spherical_harmonics) on Wikipedia
* [Spherical Harmonics](http://paulbourke.net/geometry/sphericalh/) by Paul Bourke
_Code projects and tools:_
* [google/spherical-harmonics](https://github.com/google/spherical-harmonics) (C++) - graphics-oriented library for evaluating, projecting, and rotating spherical harmonic basis functions, including diffuse irradiance/environment lighting helpers.
* [SHTOOLS/SHTOOLS](https://github.com/SHTOOLS/SHTOOLS) (Fortran 95 / Python, `pyshtools`) - library for spherical harmonic transforms, spectral analysis, and working with gravity/magnetic/topography field data.
* [A Symphony of Spheres: Animating Spherical Harmonics in Blender with Python and Shape Keys](https://medium.com/@bldevries/a-symphony-of-spheres-animating-spherical-harmonics-in-blender-with-python-and-shape-keys-aa67b7ff3d93) by Ben de Vries
---
### Strange attractors
Trajectories of deterministic dynamical systems that exhibit chaotic behavior while remaining confined within a bounded region of space. Unlike ordinary attractors (fixed points or periodic cycles), strange attractors have a fractal structure with infinite detail and display sensitive dependence on initial conditions - tiny differences in starting state lead to wildly divergent outcomes. Despite their deterministic rules, the long-term behavior appears random or turbulent.
Strange attractors emerge in nonlinear systems where feedback loops create complex dynamics. They are "strange" because they combine order (the system never leaves a bounded region) with chaos (unpredictable behavior). They are "attractors" because trajectories from nearby initial conditions are pulled toward them over time. Their fractal dimension is typically non-integer, a hallmark of their geometric complexity.
Strange attractors have been observed in fluid dynamics (turbulence), weather systems (weather chaos), population dynamics, electronic circuits, and more. In generative art and morphogenesis, they are often used to create organic-looking, intricate patterns and forms that would be difficult or impossible to design by hand. The self-similar, fractal-like structures they produce can simulate natural phenomena like cloud formations, terrain, and biological branching patterns.
_Key terms:_
* Attractor - a set of states (points in phase space) toward which a dynamical system evolves, regardless of initial conditions. Non-strange attractors include fixed points and periodic orbits.
* Phase space - an abstract mathematical space where each point represents a possible state of the system; trajectories trace the system's evolution through this space.
* Chaos / Chaotic behavior - deterministic evolution that is sensitive to initial conditions; small perturbations grow exponentially, making long-term prediction impossible even though the system is not random.
* Sensitive dependence on initial conditions - the hallmark of chaos; trajectories starting arbitrarily close together diverge exponentially fast. Related to the concept of the [Lyapunov exponent](https://en.wikipedia.org/wiki/Lyapunov_exponent).
* Fractal structure - strange attractors typically have infinite detail at all scales, with a non-integer (fractal) dimension.
* Basin of attraction - the set of initial conditions from which trajectories are drawn to a particular attractor.
* Bifurcation - a qualitative change in system behavior as a parameter varies; can lead to onset of chaos or transition between different types of attractors.
_Notable attractors:_
* [Clifford attractor](http://paulbourke.net/fractals/clifford/)
* [Duffing attractor](http://paulbourke.net/fractals/duffing/)
* [Hénon attractor](https://en.wikipedia.org/wiki/H%C3%A9non_map)
* [Lorenz attractor](https://en.wikipedia.org/wiki/Lorenz_system)
* [Multiscroll attractor](https://en.wikipedia.org/wiki/Multiscroll_attractor) (a.k.a double-scroll attractor or Chua's attractor)
* [Rössler attractor](https://en.wikipedia.org/wiki/R%C3%B6ssler_attractor)
_Articles:_
* [Strange attractor](https://en.wikipedia.org/wiki/Attractor#Strange_attractor) section on Wikipedia article for [attractors](https://en.wikipedia.org/wiki/Attractor)
---
### Superellipse
Also known as the Lamé curve, this equation describes a closed curve that can generate shapes that look like pinched or inflated ellipses. At the extremes of the parameter space the shapes can range from an outline of a plus (`+`) symbol to a nearly rectangular shape with rounded corners.
_Equations:_
| General form | $\left|\frac{x}{a}\right|^{n} + \left|\frac{y}{b}\right|^{n} = 1$ |
| Parametric | $x(t)=\pm a\cos^{\frac{2}{n}}t,\quad y(t)=\pm b\sin^{\frac{2}{n}}t,\quad 0\leq t\leq\frac{\pi}{2}$ |
### Superformula
Generalized version of the superellipse formula proposed by Johan Giellis around 2000, capable of far more variety than the original superellipse. Unfortunately, Johan has patented use of the formula (via his company [Genicap](http://www.genicap.com/)) in both the US and the EU, which means you should avoid using it for any kind of commercial work, or work that could be commercialized in some way later.
The superformula can be used to generate both 2D and 3D forms. To create 2D forms, use the general form equation to obtain [polar coordinates](http://mathworld.wolfram.com/PolarCoordinates.html) that can be converted into Cartesian coordinates for drawing on a screen. To create 3D forms, compute the polar coordinates for _two_ 2D supershapes, then "mix" them together using the 3D equations below.
_Equations:_
| General form | $r(\varphi) = \left(\left|\frac{\cos(m_1\varphi/4)}{a}\right|^{n_2} + \left|\frac{\sin(m_2\varphi/4)}{b}\right|^{n_3}\right)^{-1/n_1}$ |
| 3D equations | $x=r_1(\theta)\cos\theta\cdot r_2(\varphi)\cos\varphi,\quad y=r_1(\theta)\sin\theta\cdot r_2(\varphi)\cos\varphi,\quad z=r_2(\varphi)\sin\varphi$ |
### Tiling / tessellation
> [!NOTE]
> Related to [polyhedra](#polyhedra), [Wave Function Collapse (WFC)](#wave-function-collapse-wfc), and [Delaunay triangulation and Voronoi diagrams](#delaunay-triangulation-and-voronoi-diagrams).
A tiling (or tessellation) is a covering of a plane, or other surface, by one or more shapes ("tiles") with no gaps and no overlaps. Like [polyhedra](#polyhedra), tilings are a design space defined by a small set of construction rules, which makes them a reliable source of "correct-looking" repeating patterns for generative art, procedural texture generation, and physical fabrication (laser-cut panels, tiled floors, quilting).
_Key concepts:_
* Periodic vs. aperiodic - periodic tilings repeat via simple translation, so a single finite patch can tile the whole plane; aperiodic tilings (like Penrose tilings) never repeat via translation alone, no matter how far you zoom out.
* Regular and semi-regular tilings - the 2D analog of [Platonic and Archimedean solids](#polyhedra): 3 regular tilings (one type of regular polygon) and 8 semi-regular tilings (2+ types), each with an identical arrangement of polygons at every vertex.
* Symmetry (wallpaper groups) - every repeating 2D pattern falls into one of exactly 17 [wallpaper groups](https://en.wikipedia.org/wiki/Wallpaper_group), based on which combination of translations, rotations, reflections, and glide reflections leave the pattern looking unchanged.
* Substitution tilings - built by repeatedly subdividing each tile into smaller copies of the same prototile set according to a fixed rule; many aperiodic tilings, including Penrose's, can be generated this way.
_Notable named tilings:_
* [Penrose tiling](https://en.wikipedia.org/wiki/Penrose_tiling) - the best-known aperiodic tiling, built from just two prototiles (kite & dart, or two rhombi) related by the golden ratio.
* [Wang tiles](https://en.wikipedia.org/wiki/Wang_tile) - square tiles with colored edges that must match their neighbors, with no rotation allowed in the original formalism; widely used in computer graphics for generating large, non-repetitive textures, height fields, and point distributions from a small tile set.
* [Truchet tiles](https://en.wikipedia.org/wiki/Truchet_tile) - simple square tiles (split diagonally, or decorated with quarter-circle arcs) that, placed in random orientations, produce intricate maze-like or flowing patterns; a long-running favorite in generative art, first described by Sébastien Truchet in 1704.
* [The Hat and Spectre](https://en.wikipedia.org/wiki/Einstein_problem) - the first known aperiodic _monotiles_ ("einsteins"), discovered in 2023 by David Smith, Craig Kaplan, Joseph Myers, and Chaim Goodman-Strauss. Each forces aperiodicity using a single tile shape and no matching rules, resolving a problem that had been open since the 1960s.
* [Isohedral (Escher-style) tilings](https://en.wikipedia.org/wiki/Isohedral_figure) - tilings where every tile is equivalent to every other tile under the pattern's symmetries; the class M.C. Escher's interlocking animal and figure tessellations belong to.
_Key terms:_
* Prototile - one of the shape(s) allowed in a tiling; a monotile is a tiling that uses just one.
* Edge-to-edge - a tiling where tiles only ever share a full edge with a neighbor, never a partial one.
* Vertex configuration - the cyclic sequence of polygon types meeting at a vertex, e.g. `3.6.3.6` for a triangle-hexagon-triangle-hexagon arrangement.
* Matching rules - markings or notches added to prototiles that forbid periodic arrangements; used by some, but not all, aperiodic tilings to enforce non-repetition.
_Articles:_
* [Tessellation](https://en.wikipedia.org/wiki/Tessellation) on Wikipedia
* [Wallpaper group](https://en.wikipedia.org/wiki/Wallpaper_group) on Wikipedia
* [Introductory Tiling Theory for Computer Graphics](https://www.gbv.de/dms/tib-ub-hannover/670618950.pdf) (PDF) by Craig S. Kaplan - concise academic introduction to tiling theory for a graphics/programming audience
* [An aperiodic monotile](https://arxiv.org/pdf/2303.10798) (PDF) by David Smith, Joseph Samuel Myers, Craig S. Kaplan, and Chaim Goodman-Strauss - the original "Hat" paper
* [The Hat and the Spectre](https://momath.org/the-hat/) from the National Museum of Mathematics - accessible overview of both 2023 discoveries
_Videos:_
* [5 and Penrose Tiling](https://www.youtube.com/watch?v=QTrM-UVcgBY) by Numberphile
* [Aperiodic monotile animation](https://www.youtube.com/watch?v=W-ECvtIA-5A) featuring the discoverers of "the Hat"
_Notable tools:_
* [Tactile.js](https://github.com/isohedral/tactile-js) by Craig Kaplan - JavaScript library for representing, manipulating, and drawing Escher-style isohedral tilings ([C++ version](https://github.com/isohedral/tactile))
* [Pattern Collider](https://aatishb.com/patterncollider/) by Aatish Bhatia - interactive web tool for exploring quasiperiodic tilings, including Penrose and the Hat/Spectre monotiles
* [Penrose](https://penrose.cs.cmu.edu/) by Carnegie Mellon University - web-based tool that creates images from text notation. ([Github repo](https://github.com/penrose/penrose))
_Code projects:_
* [Penrose.js](https://github.com/guinetik/penrose-js) - pure JavaScript library for generating Penrose tilings, rendered to canvas or bitmap
* [Pattern Collider](https://github.com/aatishb/patterncollider) - source code for the interactive tool above
---
### Travelling salesman problem (TSP)
Asks the question "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" This classic problem is computer science classrooms to teach algorithm design and optimization techniques.
Useful for creating single-line drawings for use with pen plotters, laser cutters, CNC machines, and more.
_Articles:_
* [Travelling salesman problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem) on Wikipedia
* [Traveling Salesman Problem](https://developers.google.com/optimization/routing/tsp) from Google OR-Tools
_Notable software:_
* [StippleGen](https://wiki.evilmadscientist.com/StippleGen) from Evil Mad Scientist Laboratories can [calculate TSP paths](https://wiki.evilmadscientist.com/StippleGen#Calculating_the_TSP_Path).
---
### Verlet physics
> [!NOTE]
> Related to [physics engines](#physics-engine) and [particle systems](#particle-system).
_Image credit: Matthew Fisher - [Cloth](https://graphics.stanford.edu/~mdfisher/cloth.html)_
Family of numerical integration methods for simulating motion that skip storing velocity explicitly, instead deriving it implicitly from a particle's current and previous position. Named after French physicist Loup Verlet, who used it for molecular dynamics simulations in the 1960s, though the technique dates back further.
At each step, a particle's next position is calculated from its current position, its previous position, and the acceleration currently acting on it:
```
newPosition = 2 * currentPosition - previousPosition + acceleration * timeStep^2
```
Because positions - not velocities - are what's being directly manipulated, distance constraints (like the fixed-length "sticks" connecting particles in a rope, cloth, or soft body) can be enforced by simply nudging connected particles toward or away from each other until the constraint is satisfied, without separately tracking or adjusting velocity. This makes Verlet integration especially popular for simulating chains, cloth, ragdolls, and other constraint-based systems in games, creative coding, and animation - and it forms the conceptual basis for the more general [Position Based Dynamics](https://www.researchgate.net/publication/223399772_Position_Based_Dynamics) approach used in many modern physics engines.
_Key terms:_
* Implicit velocity - since a particle's velocity is never stored directly, it can be recovered as the difference between its current and previous position.
* Distance constraint - a rule (often visualized as a "stick") requiring two particles to stay a certain distance apart; satisfied directly by moving positions rather than applying forces.
* [Position Based Dynamics (PBD)](https://www.researchgate.net/publication/223399772_Position_Based_Dynamics) - generalization of Verlet-style constraint solving into a broader framework for simulating cloth, rigid bodies, fluids, and more.
* Numerical stability - Verlet integration is more stable than simple Euler integration over long simulations, since it approximately conserves energy.
_Articles:_
* [Verlet integration](https://en.wikipedia.org/wiki/Verlet_integration) on Wikipedia
* [Advanced Character Physics](https://www.cs.cmu.edu/afs/cs/academic/class/15462-s13/www/lec_slides/Jakobsen.pdf) (PDF) by Thomas Jakobsen - classic, widely-cited article on using Verlet integration for constraint-based cloth and character simulation, developed for the game Hitman: Codename 47
* [Ten Minute Physics](https://matthias-research.github.io/pages/tenMinutePhysics/) by Matthias Müller - video tutorial series building from basic particle simulation up to Position Based Dynamics
* [Verlet Physics with Toxiclibs.js](https://natureofcode.com/book/chapter-5-physics-libraries/#verlet-physics-with-toxiclibsjs) chapter from Daniel Shiffman's Nature of Code book
_Videos:_
* [ToxicLibs Verlet Physics](https://thecodingtrain.com/tracks/physics-libraries/physics-libraries/toxiclibs/1-introduction/) video series by Daniel Shiffman (The Coding Train) - covers particles, springs, connected systems, and attraction behaviors in Processing with toxiclibs.js
_Notable tools:_
* [Vellum](https://www.sidefx.com/docs/houdini/vellum/overview.html) - Houdini's unified solver for cloth, hair, grains, and softbodies, built on an extended Position Based Dynamics approach
* [ChaosCloth](https://dev.epicgames.com/documentation/en-us/unreal-engine/API/Plugins/ChaosCloth) - Unreal Engine's built-in cloth solver, also based on Position Based Dynamics
* [Obi](https://obi.virtualmethodstudio.com/) (Unity asset) by Virtual Method - rope, cloth, softbody, and fluid simulation using an XPBD (Extended Position Based Dynamics) solver
_Code projects:_
* [toxiclibs VerletPhysics](https://github.com/postspectacular/toxiclibs/tree/master/src.physics) (Processing/Java addon) by Karsten Schmidt
* [toxiclibsjs](https://github.com/hapticdata/toxiclibsjs) (JavaScript/p5.js port of toxiclibs, including its VerletPhysics2D/3D package) by Kyle Phillips (hapticdata)
* [ofxMSAPhysics](https://github.com/memo/ofxMSAPhysics) (openFrameworks addon, C++) by Memo Akten - particle/constraint physics library explicitly modeled on the same approach described in Jakobsen's article above
* [Rope and Cloth Simulation](https://github.com/aryamancodes/Rope-and-Cloth-Simulation) (p5.js) by Aryaman - tearable rope/cloth demo with wind and collisions
.jpg "Wikipedia - File:Belousov Zhabotinsky reaction (3572095252).jpg")
### Belousov–Zhabotinsky (BZ) reaction
Oscillating chemical reaction that can produce complex, regularly-spaced shapes that intersect (combining or cancelling) in predictable ways. The actual chemical reaction is very complex and is thought to involve around 18 distinct steps; the original discoverers struggled to get their work published because of their difficulties in explaining the underlying mechanisms of this reaction!
It may be possible to simulate this reaction, at least superficially, using either [reaction-diffusion systems](#reaction-diffusion) or [cellular automata](#cellular-automata-ca) (see the Hodgepodge Machine specifically).
_Basic petri dish setup:_
1. Gather reactants: malonic acid, potassium bromate, sulfuric acid, and an indicator dye (typically ferroin, which shifts between blue and red).
2. Mix the reactants in specific proportions (see Nigel Baldwin's videos below for exact ratios).
3. Pour the mixed solution into a shallow petri dish or watch glass.
4. Leave undisturbed to allow the reaction to begin.
5. Within minutes, concentric rings or spiral waves of color will form and propagate across the dish.
6. Observe the patterns oscillating between blue and red states as the chemical reaction continues.
7. The reaction typically persists for 30 minutes to several hours depending on conditions and reagent concentrations.
For detailed preparation procedures and exact chemical ratios, consult the video references below - particularly Nigel Baldwin's two-part preparation series.
_Articles:_
* [Belousov–Zhabotinsky reaction](https://en.wikipedia.org/wiki/Belousov%E2%80%93Zhabotinsky_reaction) on Wikipedia
* [Belousov-Zhabotinsky reaction](http://www.scholarpedia.org/article/Belousov-Zhabotinsky_reaction) on Scholarpedia
* [The Belousov-Zhabotinsky Reaction and The Hodgepodge Machine](https://softologyblog.wordpress.com/2017/02/04/the-belousov-zhabotinsky-reaction-and-the-hodgepodge-machine/) by Softology
_Code projects:_
* [Simulating the Belousov-Zhabotinsky reaction](https://scipython.com/blog/simulating-the-belousov-zhabotinsky-reaction/) (Python) by Christian Hill
_Videos:_
* [Belousov-Zhabotinsky Reaction](https://www.youtube.com/watch?v=IBa4kgXI4Cg) by nater06
* [Recreating one of the weirdest reactions](https://www.youtube.com/watch?v=LL3kVtc-4vY) by NilesRed
* [Preparation of a Belousov--Zhabotinsky reaction for use in a Petri-dish Part 1](https://www.youtube.com/watch?v=1_Vtz1KG4gg) by Nigel Baldwin
* [Preparation of a Belousov--Zhabotinsky reaction for use in a Petri-dish Part 2](https://www.youtube.com/watch?v=EWmm9tgLgMc) by Nigel Baldwin
---
### Chladni plate
Apparatus consisting of a suspended metal plate covered in a light dusting of fine sand or powder, then vibrated by either a bow or a voice coil (speaker). Beautiful, consistent nodal patterns known as [Chladni figures](https://en.wikipedia.org/wiki/Ernst_Chladni#Chladni_figures) emerge based on the specific resonance characteristics of the plate and the frequency of vibration inducued in it. Different sizes, shapes, and thicknesses of plates create different patterns, as do different frequencies, vibration methods, and audio samples.
_Examples of Chladni figures:_
_Articles:_
* [Chladni figures](https://en.wikipedia.org/wiki/Ernst_Chladni#Chladni_figures) on Wikipedia
_DIY projects:_
* [Easy Chladni Plate](https://www.instructables.com/id/Easy-Chladni-Plate/) by Aron Hoekstra
* [Building a Chladni Plate](https://medium.com/@MarioTheMaker/building-a-chladni-plate-e46cdfce1807) by Mario Cruz (MarioTheMaker)
* [How to sculpt sound into Chladni figures](http://www.makery.info/en/2017/05/09/comment-sculpter-le-son-en-figures-de-chladni/) by Nicolas Barrial
* [Chladni Plate](https://makezine.com/projects/chladni-plate/) by Edwin Wise
_Products:_
Due to its popularity as a demonstration aid in science classrooms, good-quaity Chladni plate's are available from multiple dealers including:
* [Arbor Scientific](https://www.arborsci.com/products/chladni-plates-kit)
* [PASCO](https://www.pasco.com/prodCatalog/WA/WA-9607_chladni-plates-kit/index.cfm)
_Videos:_
* [Weekend Projects: Visualizing Sound with a Chladni Plate](https://www.youtube.com/watch?v=hKmPc0Q0kKg) by Make
* [Singing plates - Standing Waves on Chladni plates](https://www.youtube.com/watch?v=wYoxOJDrZzw) by Diana Cowern (Physics Girl)
* [Chladni Figures - random couscous snaps into beautiful patterns](https://www.youtube.com/watch?v=CR_XL192wXw) by Steve Mould
* [Resonance Experiment! (Full Version - With Tones)](https://www.youtube.com/watch?v=1yaqUI4b974) by brusspup
* [Moving Particles with Vibration, Making the Chladni Plate](https://www.youtube.com/watch?v=9po11qjCWxA) by Mehdi Sadaghdar (ElectroBOOM)
---
### Hele-Shaw cell
> [!NOTE]
> Related to [Saffman-Taylor instability](#saffmantaylor-instability).
Apparatus for demonstrating and studying a pheonmenon known as [viscous fingering](#saffman%E2%80%93taylor-instability) (a.k.a. Saffman-Taylor instability), which is defined as "the formation of patterns in a morphologically unstable interface between two fluids in a porous medium" [[1](https://en.wikipedia.org/wiki/Saffman%E2%80%93Taylor_instability)]. It occurs when a less viscous fluid is injected into a more viscous fluid, displacing it in a series of blobby, fractal-like fingers resembling (perhaps related to) the patterns formed by [diffusion-limited aggregation](#diffusion-limited-aggregation-dla) or [differential growth](#differential-growth).
_Setup:_
The Hele-Shaw cell typically consists of two plates, usually glass or plexiglass, separated by a very narrow gap (typically 0.5 to 2 mm). The small gap constrains fluid flow to approximately 2D motion, allowing viscous fingering patterns to emerge clearly.
_Procedure:_
1. Seal the edges of the two plates together, leaving injection points open.
2. Fill the cell with a viscous fluid such as glycerin or silicone oil.
3. Inject a less viscous fluid (such as colored water or dyed oil) through a hole in one of the plates or between the plates from the side.
4. As pressure builds from the injection, the less viscous fluid displaces the glycerin, but the viscous resistance creates an unstable interface.
5. Complex, branching finger-like patterns form and propagate across the gap between the fluids.
6. For better visualization, illuminate the cell from underneath, shining light through toward the viewer. The contrast between fluids makes the fingering patterns clearly visible.
_Lifted Hele-Shaw cells:_
A variant called a "lifted" or "tilted" Hele-Shaw cell involves rotating or lifting the cell at an angle during the experiment. This introduces gravitational and buoyancy effects that modify the viscous fingering patterns, creating asymmetrical or spiral-like flow patterns instead of the symmetric branching seen in vertical cells. This technique reveals how gravity influences fluid dynamics and pattern formation.
_Articles:_
* [Hele-Shaw flow](https://en.wikipedia.org/wiki/Hele-Shaw_flow) on Wikipedia
_Videos:_
* [Hele-Shaw cell experiments](https://vimeo.com/22212386) by Nervous System
* [Hele Shaw Cell](https://www.youtube.com/watch?v=yys3q_XBRI4) using ferrofluid and a magnet by manf1234
* [Viscous Fingering in Multiport Hele Shaw Cell for Controlled Shaping of Fluids](https://www.youtube.com/watch?v=wegYlxGXhW8) by Tanveer ul Islam and Prasanna S. Gandhi
_Images:_
* [Schlieren Imaging of Viscous Fingering and Buoyancy Driven Convection](https://art-csep.cnsi.ucsb.edu/gallery/schlieren-imaging-viscous-fingering-and-buoyancy-driven-convection) by Simone Stewart
---
### Schlieren imaging
Technique for visualizing density variations in transparent media, usually air. Essentially exaggerates the effects of refraction in different densities of air caused by heat (hot air expands, cool air contracts) or pressure (like ultrasonic transducers). Effect can be observed using just a few low-cost components:
1. Concave mirror with a long focal length (3-4ft or more) - spherical mirrors work best, but parabolic mirrors can work
2. Point light source - the brightest, smallest light source you can find/make. Lasers don't work well, but a simple LED with a pinhole cover or a strand of fiber optic will work. Doesn't need to be very bright.
3. Razor blade or color filter
4. Camera
_Diagram of typical setup:_
_Articles:_
* [Schlieren](https://en.wikipedia.org/wiki/Schlieren) on Wikipedia
* [Schlieren imaging](https://en.wikipedia.org/wiki/Schlieren_imaging) on Wikipedia
* [Schlieren photography](https://en.wikipedia.org/wiki/Schlieren_photography) on Wikipedia
* [Schielren Optics](https://sciencedemonstrations.fas.harvard.edu/presentations/schlieren-optics) by Harvard Natural Sciences Lecture Demonstrations
_DIY projects:_
* [Schlieren Imaging: How to See Air Flow!](https://www.instructables.com/id/Schlieren-Imaging-How-to-see-air-flow/) by Bryan Rolfe
* [DIY Schlieren Flow Visualization](https://www.instructables.com/id/DIY-Schlieren-Flow-Visualization/) by Jonathan Lansey (jlansey)
_Videos:_
* [Seeing the Invisible: SLOW MOTION Schlieren Imaging](https://www.youtube.com/watch?v=4tgOyU34D44) by Veritasium
* [Schlieren Imaging in Color!](https://www.youtube.com/watch?v=K7pQsR8WFSo) by Veritasium
* [How To: Build Your Own Schlieren Setup](https://www.youtube.com/watch?v=IZ0bYi9UFv8) by JoshTheEngineer
* [Visualizing Ultrasound with Schlieren Optics Part I](https://www.youtube.com/watch?v=MBPh410Gnes) [[Part II](https://www.youtube.com/watch?v=VrgyKFBPQW4)] [[Part III](https://www.youtube.com/watch?v=doxDOlwEblg)] by Harvard Natural Sciences Lecture Demonstrations
### Agent-based modelling
Methods for simulating the actions and interactions of autonomous entities and the complex emergent behavior they exhibit collectively. Used for simulating and analyzing collective social and biological phenomena like flocking animals (e.g. birds or fish), colony behaviors (e.g. ants and termites), crowd movement, and more.
This topic has a lot in common with the related topic of [multi-agent systems](https://en.wikipedia.org/wiki/Multi-agent_system), but with a different intent. Agent-based models tend to seek explanatory insight into the collective behavior of agents (often real-world organisms or systems), whereas multi-agent systems tend to be more focused on solving practical or engineering problems through optimization of the design of agents.
Insights from this topic can be directly applicable in large-scale kinetic art or LED installations, [swarm robotics research](https://en.wikipedia.org/wiki/Swarm_robotics), architecture, and city planning.
Characteristics of agent-based models relevant to biological modelling [[1](https://en.wikipedia.org/wiki/Agent-based_model_in_biology)]:
1. Modular structure: The behavior of an agent-based model is defined by the rules of its agents. Existing agent rules can be modified or new agents can be added without having to modify the entire model.
2. Emergent properties: Through the use of the individual agents that interact locally with rules of behavior, agent-based models result in a synergy that leads to a higher level whole with much more intricate behavior than those of each individual agent.
3. Abstraction: Either by excluding non-essential details or when details are not available, agent-based models can be constructed in the absence of complete knowledge of the system under study. This allows the model to be as simple and verifiable as possible.
4. Stochasticity: Biological systems exhibit behavior that appears to be random. The probability of a particular behavior can be determined for a system as a whole and then be translated into rules for the individual agents.
_Notables systems:_
* [Boids](#boids)
_Articles:_
* [Agent-based model](https://en.wikipedia.org/wiki/Agent-based_model) on Wikipedia
* [Multi-agent system](https://en.wikipedia.org/wiki/Multi-agent_system) on Wikipedia
* [Agent-based model in biology](https://en.wikipedia.org/wiki/Agent-based_model_in_biology) on Wikipedia
* [Emergence](https://en.wikipedia.org/wiki/Emergence) on Wikipedia
* [Swarm intelligence](https://en.wikipedia.org/wiki/Swarm_intelligence) on Wikipedia
---
### Boids
> [!NOTE]
> Related to [agent-based modelling](#agent-based-modelling).
Well-known type of [agent-based system](#agent-based-modelling) that realistically simulates the complex flocking behaviors of birds and fish using simple rules. Each "boid" is an autonomous agent that is only aware of its immediate neighbor boids, all following the same three rules:
1. Separation (collision avoidance): steer to avoid crowding local flockmates
2. Alignment (velocity matching): steer towards the average heading of local flockmates
* _Note:_ remember that a vector is a combination of a speed and a direction (heading)!
3. Cohesion (flock centering): steer to move towards the average position (center of mass) of local flockmates
And here is what those rules look like when applied to a set of agents (boids):
| Separation | Alignment | Cohesion |
|--- |--- |--- |
| 
| 
| 
|
Additional rules can be implemented to simulate specific behaviors like obstacle avoidance, predator-prey interactions, [bait balls](https://en.wikipedia.org/wiki/Bait_ball), and more.
_Articles:_
* [Flocks, Herds, and Schools: A Distributed Behavioral Model](https://team.inria.fr/imagine/files/2014/10/flocks-hers-and-schools.pdf) - original 1987 paper by Craig Reynolds
* [Boids](https://en.wikipedia.org/wiki/Boids) on Wikipedia
* [Chapter 6. Autonomous Agents](https://natureofcode.com/book/chapter-6-autonomous-agents/) from Nature of Code
* [Boids](https://www.red3d.com/cwr/boids/) by Craig Reynolds
_Code projects:_
* [Boids](https://lab.puga.com.br/boids/) ([source](https://github.com/lexicalgap/boids)) by [Marcio Puga](https://puga.com.br/) (JavaScript, PixiJS)
_Videos:_
* [Coding Challenge #124: Flocking Simulation](https://www.youtube.com/watch?v=mhjuuHl6qHM) by Daniel Shiffman ([Github repo](https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_124_Flocking_Boids) with source code for p5.js and Processing)
---
### Constructive solid geometry (CSG)
Technique for 3D solid modeling that allows for the creation of complex surfaces by using Boolean operators to combine simpler objects (usually primitives like cubes, spheres, cylinders, etc). Most CAD and 3D modeling applications (like Blender, Fusion, Rhino, and more) include CSG operations, sometimes even through parametric or procedural interfaces.
_Operations:_
| Name | Descriptionn | Illustration |
|--- |--- |--- |
| Union | Merger of two objects into one | 
|
| Difference | Subtraction of one object from another | 
|
| Intersection | Portion common to both objects | 
|
_Articles:_
* [Constructive solid geometry](https://en.wikipedia.org/wiki/Constructive_solid_geometry) on Wikipedia
_Code projects:_
* [csg.js](https://github.com/evanw/csg.js/) (JavaScript) by Evan Wallace
* [CGAL 4.14- 3D Boolean Operations on Nef Polyhedra](https://doc.cgal.org/latest/Nef_3/index.html) (C++)
---
### Cloth simulation
> [!NOTE]
> Related to [verlet physics](#verlet-physics), [particle systems](#particle-system), and [physics engines](#physics-engine).
_Image credit: Isabel Zhang - [Project 4: Cloth Simulator](https://www.isabelzhang.net/projects/cs184_proj4/)_
Real-time simulation of cloth dynamics - how fabric bends, stretches, folds, and interacts with collisions and external forces like wind and gravity. Most cloth solvers model cloth as a mesh of particles connected by distance constraints (springs), typically using [Verlet integration](#verlet-physics) or [Position Based Dynamics](#verlet-physics) for stability and speed. The mesh deforms and settles as constraint-based solvers iteratively push connected particles toward their rest distances, while collisions are handled by detecting and pushing cloth away from obstacles.
Cloth simulation is essential for character animation, VFX, and any scenario requiring realistic fabric behavior without pre-baked animation. It scales from interactive real-time performance in games to high-quality offline rendering in film and animation.
_Algorithm at a glance:_
_\* indicates a potential simulation parameter_
1. Create a mesh of particles (one per vertex), each with mass\*, position, and velocity.
2. Connect neighboring particles with distance constraints (structural, shear, and optionally bend constraints\*) representing fabric stiffness.
3. Each frame, apply forces\* (gravity, wind, damping) to all particles.
4. Update particle positions using [Verlet integration](#verlet-physics) or similar.
5. Repeatedly satisfy constraints: for each constraint, if the distance between two particles deviates from the rest length, nudge them toward the target distance.
6. Optionally, check each constraint against a breaking threshold\* (e.g., how much it can stretch before tearing); if exceeded, remove the constraint to simulate ripping or tearing.
7. Detect collisions with rigid bodies and other geometry, and reposition particles to prevent penetration.
8. Repeat until the cloth settles or the simulation ends.
_Key terms:_
* Structural constraint - distance constraint along the fabric's grid edges, prevents stretching.
* Shear constraint - diagonal distance constraint, prevents skewing and distortion.
* Bend constraint - constraint between particles separated by one edge, prevents unrealistic folding.
* Damping - friction-like force that slows particle motion over time, helps cloth settle faster.
* Self-collision - cloth colliding with itself; necessary for realistic folding and wrapping.
* Constraint breaking / tearing - removal of constraints when they exceed a strain threshold\*, allowing cloth to rip and tear when stretched too far; can also be triggered by collision impact.
_Articles:_
* [Cloth Modeling and Simulation: A Literature Survey](https://link.springer.com/chapter/10.1007/978-3-642-21799-9_35) in Springer's Computer Graphics and Geometric Modeling
* [Simulation of Clothing with Folds and Wrinkles](https://www.cs.ubc.ca/~rbridson/docs/cloth2003.pdf) (PDF) by R. Bridson, S. Marino, and R. Fedkiw - foundational paper introducing a physically-correct bending model and wrinkle pre-shaping
* [Robust Treatment of Collisions, Contact and Friction for Cloth Animation](https://physbam.stanford.edu/~fedkiw/papers/stanford2002-01.pdf) (PDF) by R. Bridson, R. Fedkiw, and J. Anderson - seminal paper on collision handling for cloth
* [Fast Simulation of Cloth Tearing](https://www.researchgate.net/publication/264457835_Fast_Simulation_of_Cloth_Tearing) - techniques for efficiently simulating constraint breaking and mesh splitting during cloth tearing
* [Simulation of Tearing Cloth with Frayed Edges](https://www.researchgate.net/publication/220505979_Simulation_of_Tearing_Cloth_with_Frayed_Edges) - methods for realistic fraying and edge detail in torn cloth
* [Breaking and Tearing](https://www.sidefx.com/docs/houdini/vellum/breaking_tearing.html) - Houdini Vellum documentation on implementing constraint breaking and artistic control over tearing guides
_Videos:_
* [Coding Challenge #63: Texturing and Cloth Simulation](https://thecodingtrain.com/challenges/63-texturing-cloth-simulation/) by Daniel Shiffman (The Coding Train) - combines toxiclibs Verlet physics with texture rendering for a waving flag
_Notable tools:_
* [Obi Cloth](https://assetstore.unity.com/packages/tools/physics/obi-cloth-81333) (Unity asset) by Virtual Method - high-quality cloth simulation with character clothing, two-way rigidbody interaction, and aerodynamics
* [Vellum](https://www.sidefx.com/docs/houdini/vellum/overview.html) (Houdini solver) by SideFX - unified cloth/hair/grain solver using Position Based Dynamics
_Code projects:_
* [Cloth Simulation](https://github.com/aryamancodes/Rope-and-Cloth-Simulation) (p5.js) by Aryaman - interactive tearable cloth demo with wind and collisions
---
### Collision detection
Computational methods for determining when two or more shapes are intersecting either statically (right now) or predictively (in the future). In technical terms, _a posterior_ and _a priori_ respectively. Detecting and reacting to collisions is extremely important in videos games and physical simulations, and takes quite a lot of brains and computational muscle to do effectively in real-time, especially in large-scale systems.
Building your own collision detection code is a fun and educational exercise, but is so complex and difficult to achieve in practice that it is generally a good idea to use an establisihed physics library or VFX/modelling application for performance. See the [Physics engine](#physics-engine) and [Tools](#tools) sections for options.
_Relevant topics:_
* Broad phase - class of algorithms that detect pairs of _potentially_ colliding shapes using fast but approximate methods, such as:
* [Axis-aligned bounding box](https://en.wikipedia.org/wiki/Minimum_bounding_box#Axis-aligned_minimum_bounding_box) (AABB)
* [Sort and sweep](https://en.wikipedia.org/wiki/Sweep_and_prune) (a.k.a. sweep and prune)
* [Bounding volume hierarchy](https://en.wikipedia.org/wiki/Bounding_volume_hierarchy) (BVH)
* Narrow phase - class of algorithms that determine if two shapes are definitely intersecting or not, and by how much.
* [Separating axis theorem](https://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem--gamedev-169) (SAT)
* [Gilbert-Johnson-Keerthi](https://en.wikipedia.org/wiki/Gilbert%E2%80%93Johnson%E2%80%93Keerthi_distance_algorithm) (GJK) algorithm
* Expanding Polytope Algorithm (EPA)
_Articles:_
* [Collision detection](https://en.wikipedia.org/wiki/Collision_detection) on Wikipedia
* [Video Game Physics Tutorial - Part II: Collision Detection for Solid Objects](https://www.toptal.com/game/video-game-physics-part-ii-collision-detection-for-solid-objects) by Nilson Souto
* [Let's talk about broad phase](http://podgorskiy.com/spblog/40/lets-talk-about-broad-phase) by Stanislav Pidhorskyi
_Books:_
* [Real-Time Collision Detection](https://smile.amazon.com/exec/obidos/tg/detail/-/1558607323/realtimecolli-20/?sa-no-redirect=1) by Christer Ericson
---
### Dithering
> [!NOTE]
> Related to [convolution kernel](#convolution-kernel).
In an image using a limited color palette, dithering can provide an illusion of a continuous gradient, or a field of color not in the palette. Using colors that are close to the target color, the technique applies a granular pattern of varying sizes and spacing of solid, single-color dots or lines. The human eye then interpolates between the colors at a larger scale.
Some techniques (like [halftones](https://en.wikipedia.org/wiki/Halftone)) predate modern digital technologies because of their usefulness in traditional printmaking and engraving processes. There are even relevant techniques in the fields of painting and drawing; see [stippling](https://en.wikipedia.org/wiki/Stippling) and [pointillism](https://en.wikipedia.org/wiki/Pointillism)! In digital imaging, modern palettes are usually comprehensive enough to reach a satisfactory visual fidelity for general purposes, but limits are still often reached in professional contexts.
Dithering is useful for realizing grayscale images with various digital fabrication equipment like laser cutters, pen plotters, CNC routers/mills, and more.
_Types of dithering:_
* Random
* Patterned
* Ordered
* Halftone ⭐
* Bayer matrix
* Blue noise matrix
* Error-diffusion
* Floyd-Steinberg ⭐
* Minimized average error
* Stucki
* Burkes
* Sierra
* Two-row Sierra
* Filter Lite
* Atkinson
* Gradient-based error-diffusion
_Articles:_
* [Dither](https://en.wikipedia.org/wiki/Dither#Digital_photography_and_image_processing) on Wikipedia
_Code projects:_
* [Atkinson Dithering, Live in Processing](https://www.evilmadscientist.com/2012/dithering/) by Windell Oskay of Evil Mad Scientist Laboratories
* [Coding Challenge #90: Floyd-Steinberg Dithering](https://www.youtube.com/watch?v=0L2n8Tg2FwI) by Daniel Shiffman ([Github repo](https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_090_dithering) with source code for p5.js and Processing)
* [Color Quantization and Dithering](http://www.imagemagick.org/Usage/quantize/) reference page for ImageMagick v6
* [Digital Halftoning](https://engineering.purdue.edu/~bouman/ece637/notes/pdf/Halftoning.pdf) by C. A. Bouman
* [#dithering-algorithms](https://github.com/topics/dithering-algorithms) on Github
* [Tramage](http://lesporteslogiques.net/tricot-machine/tramage/) ([source](https://github.com/lesporteslogiques/tricot-machine)) by Pierre Commenge - utility to dither small images and prepare machine knitting files. (p5.js and Processing)
---
### Flow field
> [!NOTE]
> Related to [fluid simulation](#fluid-simulation).
Also known as a vector field, this technique involves assigning a unique vector to each point in a 2D or 3D space describing the direction and magnitude of varying forces. Flow fields are often used together with [particle systems](#particle-system) to model complex, dynamic movement caused by wind, fluid flow, electromagnetism, and more.
Vector fields are often populated using data generated with [noise](#noise) or image data. Curiously, flow fields have also been [used in pathfinding](https://gamedevelopment.tutsplus.com/tutorials/understanding-goal-based-vector-field-pathfinding--gamedev-9007).
_Articles:_
* [Vector field](https://en.wikipedia.org/wiki/Vector_field) on Wikipedia
* [Flow Fields, Part I](https://medium.com/@bit101/flow-fields-part-i-3ebebc688fd8) by Keith Peters
* [Flow Fields, Part II](https://medium.com/@bit101/flow-fields-part-ii-f3c24c1b777d) by Keith Peters
_Code projects:_
* [ofxVectorField](https://github.com/mantissa/ofxVectorField) (openFrameworks add-on) by Jeremy Rotzstain (mantissa)
_Videos:_
* [Coding Challenge #24: Perlin Noise Flow Field](https://www.youtube.com/watch?v=BjoM9oKOAKY) by Daniel Shiffman ([Github repo](https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_024_PerlinNoiseFlowField) with source code for p5.js and Processing)
---
### Fluid simulation
> [!NOTE]
> Related to [convolution kernels](#convolution-kernel), [Laplace equation](#laplace-equation), and [Saffman–Taylor instability](#saffmantaylor-instability).
Simulates the highly complex and dynamic nature of flows in fluid volumes using computationally-efficient implementations of the [Navier-Stokes equations](https://en.wikipedia.org/wiki/Navier%E2%80%93Stokes_equations). Can be thought of as a 2D or 3D flow field that is constantly changing based on the velocity, viscocity, and density of the fluid at each point in space and its surrounding area. This flow field is made visible through the use of digital "dyes" (usually particles) that get distributed, diffused, sheared, and blended through the system by the flow forces.
To appear realistic it is necessary for these simulations to have high fidelity, which introduces significant computational challenges, especially if one wants to run the simulation in real-time. Luckily, there are several great code packages available, and many VFX, CAD, and game development tools like Blender, Houdini, Unity and Unreal include robust fluid simulation functionality built in or available through plugins.
Fluid simulation has many practical and visual applications across a variety of disciplines. Its used in the analysis of aerodynamic properties of objects, vehicles, and buildings, in weather simulation and prediction, engine and combustion analysis, industrial systems design and analysis (plumbing, HVAC, public utilities, etc), visual effects for TV, movies, and games, and more.
_Related terms:_
* FLIP (FLuid Simulation Using Implicit Particles) method
* PIC (Particle in Cell) method
* [Reynolds number](https://en.wikipedia.org/wiki/Reynolds_number) (Re) - dimensionless quantity used to predict fluid flow patterns. [Laminar](https://en.wikipedia.org/wiki/Laminar_flow) (smooth) flow occurs at low Re, while [turbulent](https://en.wikipedia.org/wiki/Turbulence) flow occurs at high Re.
* [Navier-Stokes equations](https://en.wikipedia.org/wiki/Navier%E2%80%93Stokes_equations) on Wikipedia
* [Lattice Boltzmann methods](https://en.wikipedia.org/wiki/Lattice_Boltzmann_methods) (LBM) on Wikipedia
* [Rheology](https://en.wikipedia.org/wiki/Rheology) - branch of physics which deals with the deformation and flow of materials, both solids and liquids
_Articles and papers:_
* [Fluid Simulation Using Implicit Particles](http://www.danenglesson.com/images/portfolio/FLIP/rapport.pdf) (PDF) by Dan Englesson, Joakim Kilby, and Joel Ek
* [Computational fluid dynamics](https://en.wikipedia.org/wiki/Computational_fluid_dynamics) (CFD) on Wikipedia
* [Fluid Simulation for Dummies](https://mikeash.com/pyblog/fluid-simulation-for-dummies.html) by Mike Ash
* [Real-Time Fluid Dynamics for Games](http://www.dgp.toronto.edu/people/stam/reality/Research/pdf/GDC03.pdf) (PDF) by Jos Stam
* [Chapter 38. Fast Fluid Dynamics Simulation on the GPU](http://developer.download.nvidia.com/books/HTML/gpugems/gpugems_ch38.html) from GPU Gems book
_Books:_
* [Fluid Simulation for Computer Graphics](https://smile.amazon.com/Simulation-Computer-Graphics-Robert-Bridson/dp/1482232839/ref=dp_ob_title_bk) by Robert Bridson
_Code projects:_
* [Lily Pad](https://github.com/weymouth/lily-pad) (Processing) by Dr. Gabriel David Weymouth
* [MSAFluid](https://www.memo.tv/msafluid/) by Memo Akten
* [ofxMSAFluid](https://github.com/memo/ofxMSAFluid) (openFrameworks)
* [p5-MSAFluid](https://github.com/memo/p5-MSAFluid) (Processing)
* [OpenFOAM](https://www.openfoam.com/)
* [mantaflow](http://mantaflow.com/index.html)
* [Fluidity](https://fluidityproject.github.io/)
_Notable tools:_
* [FLIP Solver](https://www.sidefx.com/docs/houdini/nodes/dop/flipsolver.html) (Houdini)
* [FLIP Fluids](https://github.com/rlguy/Blender-FLIP-Fluids) (Blender)
* [Obi Fluids](https://assetstore.unity.com/packages/tools/physics/obi-fluid-63067?aid=1011l34eQ&utm_source=aff) (Unity)
* [Butterfly](https://www.ladybug.tools/butterfly.html) (Grasshopper for Rhino)
* [RhinoCFD](http://rhinocfd.com/) (Rhino)
* [RealFlow](http://www.nextlimit.com/realflow/) (Standalone, or via plugins for 3ds Max, Maya, and Cinema4D)
_Videos:_
* [Coding Challenge #132: Fluid Simulation](https://www.youtube.com/watch?v=alhpH6ECFvQ) by Daniel Shiffman ([Github repo](https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_132_FluidSimulation) with source code for p5.js and Processing)
* [Why Laminar Flow is AWESOME - Smarter Every Day 208](https://www.youtube.com/watch?v=y7Hyc3MRKno&feature=youtu.be) by Smarter Every Day
---
### Kernel-based image processing
> [!NOTE]
> Related to [convolution kernel](#convolution-kernel).
_Image credit: Hrithik Patel - [Kernels and Their Usage in Convolutional Neural Networks (CNN)](https://medium.com/code-dementia/kernels-and-their-usage-in-convolutional-neural-networks-cnn-3074ab5e849f)._
Applying [convolution kernels](#convolution-kernel) to images for filtering and feature extraction. Each pixel's new value is computed as a weighted sum of its neighborhood, determined by the kernel matrix. This is one of the most practical and widely-used techniques in digital image processing.
_Common image processing effects:_
| Effect | Purpose | Kernel | Example |
|---|---|---|---|
| Edge detection (Sobel) | Detect boundaries between regions | |
 |
| Sharpen | Enhance edges and details | |
 |
| Box blur | Simple averaging blur | |
 |
| Gaussian blur | Smooth blur, weighted toward center | |
 |
| Unsharp mask | Enhance sharpness and clarity | |
 |
| Emboss | 3D relief effect | |
N/A |
### Lloyd's relaxation
> [!NOTE]
> Related to [voronoi diagrams](#delaunay-triangulation-and-voronoi-diagrams).
As [explained by Jason Davies](https://www.jasondavies.com/lloyd), Lloyd’s relaxation algorithm (named after Stuart P. Lloyd) generates a centroidal Voronoi tessellation, which is where the seed point for each Voronoi region is also its centroid.
The algorithm computes the Voronoi diagram for a set of points, moves each point towards the centroid of its Voronoi region, and repeats.
_Important concepts:_
* [Convergence](https://en.wikipedia.org/wiki/Lloyd's_algorithm#Convergence) - every point that is being "relaxed" is moving towards the center point of a Voronoi cell, but due to computational limits in numerical precision it may not ever perfectly reach it. Therefore it is a good idea to use some sort of preset distance threshold value that causes points to stop moving once they are close enough to their target point.
_Articles:_
* [Lloyd's algorithm](https://en.wikipedia.org/wiki/Lloyd's_algorithm) on Wikipedia
* [Voronoi relaxation (Lloyd's algorithm) in Processing](http://www.codeplastic.com/2017/12/30/voronoi-relaxation-lloyds-algorithm-in-processing/) by Alberto Giachino
_Code projects:_
* [Javascript implementation of Steven Fortune's algorithm to compute Voronoi diagrams - Demo 5: Lloyd's relaxation](http://www.raymondhill.net/voronoi/rhill-voronoi-demo5.html) by Raymond Hill (JavaScript) ([source repo](https://github.com/gorhill/Javascript-Voronoi))
* [Lloyd's Algorithm](https://observablehq.com/@mbostock/lloyds-algorithm) by Mike Bostock on Observable (JavaScript and D3.js)
* [Lloyd's Relaxation](https://bl.ocks.org/lsbardel/8f42b5664b25fe7134f216fea5220b86) by Luca Sbardella (JavaScript and D3.js)
* [Lloyd's Relaxation](https://www.jasondavies.com/lloyd) by Jason Davies (JavaScript, see DOM for source code)
---
### Marching squares
Method of generating contours for a 2D scalar field (a grid of individual numerical values), like turning elevation data into a banded topographical map. The scalar values get associated with vertices of the 2D grid, then lines are drawn across each cell in different ways based on the values of their four corner vertices.
There is only a finite number of lines possible, so they can be precomputed into a lookup table and referenced quickly later for faster performance. These lines can also be linearly interpolated to smoothly transition from cell to cell, resulting in very realistic blobby / fluid structures.
_Key terms:_
* Isoline - contour line tracing a single data level, or _isovalue_.
* Isoband - filled area between isolines.
_Illustration of algorithm:_
_Articles:_
* [Marching squares](https://en.wikipedia.org/wiki/Marching_squares) on Wikipedia
* [Metaballs and Marching Squares](http://jamie-wong.com/2014/08/19/metaballs-and-marching-squares/) by Jamie Wong
_Code projects:_
* [d3-contour](https://github.com/d3/d3-contour) - D3.js library
_Videos:_
* [Marching Squares](https://unity3d.com/learn/tutorials/projects/procedural-cave-generation-tutorial/marching-squares) for procedural cave generation in Unity by Sebastian Lague
---
### Marching cubes
3D version of [marching squares](#marching-squares). Whereas marching _squares_ uses lines and cells to trace the contours of a 2D scalar field, marching _cubes_ uses polygons and voxels to trace the contours of a 3D scalar field, resulting in a mesh. Marching cubes can be thought of as a mesh conversion algorithm that produces meshes based on 3D scalar fields.
Originally developed by William Lorensen and Harvey Cline of General Electric in 1987 (see original paper in _Articles_ section) for use in the medical imaging (MRI/CT) field, this algorithm has become widely used in many areas of computer graphics.
_Dual marching cubes:_
A variant called [dual marching cubes](https://www.cs.rice.edu/~jwarren/papers/dmc.pdf) (PDF) reverses the role of vertices and cells: instead of placing vertices on cube edges, it places vertices at voxel centers and connects them based on neighboring voxel values. This approach can reduce polygon count, better handle ambiguous cases at isovalue boundaries, and eliminate certain artifacts that appear in standard marching cubes. Dual marching cubes is particularly useful when a cleaner, more regular mesh is desired.
_Algorithm [[link](https://en.wikipedia.org/wiki/Marching_cubes#Algorithm_)]:_
The algorithm proceeds through the scalar field, taking eight neighbor locations at a time (thus forming an imaginary cube), then determining the polygon(s) needed to represent the part of the isosurface that passes through this cube. The individual polygons are then fused into the desired surface.
1. Choose a threshold (called an _isovalue_) to determine which level of values are considered inside or outside the mesh, thus setting where the mesh boundary is created.
2. Pre-compute an array of all 256 (`2^8`) possible polygon configurations within a cube, where each entry is a set of IDs associated with edges of the cube (see _Figure B_ below).
* Note that of these 256 configurations, only 15 are unique due to repetition and symmetry (see _Figure A_ below).
3. For each set of 8 scalar values (forming a cube), compute an 8-bit integer where each bit corresponds to a unique scalar value (corner of the cube).
* If the scalar value is higher than the isovalue (i.e. inside of mesh), set bit to 1
* If lower, set bit to 0
4. Generate polygons for each set of scalar values by drawing lines between the edges referenced in the polygon lookup table from step 2.
* To do this, parse the 8 bits from step 3 into an integer, then use that integer as an index in the lookup table.
* For example `00101001` = `41`. Therefore the list of edges to draw lines between can be found in `lookupTable[41]`.
5. Each vertex of the generated polygons is placed on the appropriate position along the cube's edge by linearly interpolating the two scalar values that are connected by that edge.
6. Calculate normals - TODO: how?
7. Perform boolean union with all polygon fragments to form a mesh
 |
 |
### Metaballs
> [!NOTE]
> Related to [implicit surfaces](#implicit-surface), [marching squares](#marching-squares) (2D) and [marching cubes](#marching-cubes) (3D).
Often confused with [marching cubes](#marching-cubes), this is more of a mathematical concept that describes a way to define the _values_ in 2D or 3D scalar fields based on distance to one or more points in space. They are a type of [implicit surface](#implicit-surface) that define blobby shapes as pure mathematical formulas rather than explicit polygons and vertices.
They can be visualized using the [marching squares](#marching-squares) (2D) or [marching cubes](#marching-cubes) (3D) rendering algorithms. Can be used for naive [fluid simulations](#fluid-simulation) by applying [physics](#physics-engine) to the metaball center points as if they were [particles](#particle-system). They can also be helpful in modelling soft bodies by adding elastic constraints between the center points.
A typical function chosen for metaballs is:
$$f(x,y,z) = \frac{1}{(x-x_0)^2 + (y-y_0)^2 + (z-z_0)^2}$$
Where $(x_0, y_0, z_0)$ is the center of the metaball.
_Articles:_
* [Metaballs](https://en.wikipedia.org/wiki/Metaballs) on Wikipedia
* [Metaballs (also known as: Blobs)](http://www.geisswerks.com/ryan/BLOBS/blobs.html) by Ryan Geiss
* [Exploring Metaballs and Isosurfaces in 2D](https://www.gamedev.net/articles/programming/graphics/exploring-metaballs-and-isosurfaces-in-2d-r2556) by Stephen Whitmore
_Videos:_
* [Coding Challenge #28: Metaballs](https://www.youtube.com/watch?v=ccYLb7cLB1I) by Daniel Shiffman ([Github repo](https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_028_MetaBalls) with source code for p5.js and Processing)
---
### Noise
> [!NOTE]
> Related to [convolution kernel](#convolution-kernel).
In the context of computer graphics, refers to pseudo-random functions useful for creating natural-looking textures and patterns. Often used to procedurally generate organic surface textures (bark, waves, rocks, etc) and to organically distribute objects across surfaces (like grass or barnacles).
Useful for adding fine details and smooth asymmetry to otherwise pristine objects - use it in displacement maps for subtle natural features.
Also helpful for creating looping animations because reproducable results can be achieved when using the same function inputs. Just iterate through a series of cyclical values (perhaps even based on frame count) and you'll end up with smoothly transitioning noise that can be mixed in with geometry, colors, and transformations that continuously loop.
The `noise()` function in many creative coding frameworks usually makes use of Perlin noise.
* [Curl noise](https://en.wikipedia.org/wiki/Simulation_noise#Curl_noise) - produces swirling, rotational motion patterns useful for simulating vortices, flowing fluids, and turbulent effects without the computational cost of a full physics simulation (see [Curl-Noise for Procedural Fluid Flow](https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph2007-curlnoise.pdf) (PDF) by Robert Bridson et al.)
* [Gradient noise](https://en.wikipedia.org/wiki/Gradient_noise) - created by interpolation of a lattice of pseudorandom gradients
* [Perlin noise](https://en.wikipedia.org/wiki/Perlin_noise) ⭐ - extremely influential type of gradient noise developed by Ken Perlin in 1983
* [Simplex noise](https://en.wikipedia.org/wiki/Simplex_noise) - method for constructing an n-dimensional noise function comparable to Perlin noise
* [Simuation noise](https://en.wikipedia.org/wiki/Simulation_noise) - function that creates a divergence-free field
* [Value noise](https://en.wikipedia.org/wiki/Value_noise) - created by interpolation of a lattice of pseudorandom values; differs from gradient noise
* [Wavelet noise](https://en.wikipedia.org/wiki/Wavelet_noise) - alternative to Perlin noise which reduces problems of aliasing and detail loss
* [Worley noise](https://en.wikipedia.org/wiki/Worley_noise) - noise function introduced by Steven Worley in 1996
_Articles:_
* [Noise](https://thebookofshaders.com/11/) chapter in The Book of Shaders by Patricio Gonzalez Vivo & Jen Lowe
_Videos:_
* [Coding Challenge #11: 3D Terrain Generation with Perlin Noise in Processing](https://www.youtube.com/watch?v=IKB1hWWedMk) by Daniel Shiffman ([Github repo](https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_011_PerlinNoiseTerrain) with source code for p5.js and Processing)
* [Coding Challenge #136.1: Polar Perlin Noise Loops](https://www.youtube.com/watch?v=ZI1dmHv3MeM) by Daniel Shiffman ([Github repo](https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_136_Polar_Noise_Loop_1) [[2]](https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_136_Polar_Noise_Loop_2) with source code for p5.js and Processing)
_Notable implementations:_
* Curl noise
* Houdini - [Curl Noise VOP](https://www.sidefx.com/docs/houdini/nodes/vop/curlnoise.html)
* Unreal Engine 5 - [Procedural content documentation](https://docs.unrealengine.com/5.0/en-US/procedural-content-generation-in-unreal-engine/)
* TouchDesigner - [Curl Noise in Noise MAT](https://docs.derivative.ca/Noise_MAT)
* GLSL - [Curl noise shader implementations](https://www.shadertoy.com/results?query=curl+noise)
* Bitangent noise - more computationally efficient alternative to curl noise for generating divergence-free vector fields ([paper](https://www.ivandewoolf.com/bitangent-noise) by Ivan DeWolf)
* Perlin noise
* Processing - built-in [`noise()`](https://processing.org/reference/noise_.html) function
* p5.js - [`noise()`](https://p5js.org/reference/#/p5/noise) function
* Three.js / WebGL - [SimplexNoise](https://threejs.org/examples/?q=perlin#webgl_geometry_terrain) in examples; [shader implementations](https://www.shadertoy.com/results?query=perlin)
* Houdini - [Noise VOP nodes](https://www.sidefx.com/docs/houdini/nodes/vop/noise.html) (Perlin, Fractal, etc)
* TouchDesigner - [Noise CHOP](https://docs.derivative.ca/Noise_CHOP) and [Noise MAT](https://docs.derivative.ca/Noise_MAT) operators
* vvvv - Noise nodes in [vvvv.js](https://vvvv.js.org/) and [vvvv gamma](https://vvvv.org/)
* Blender - [Noise texture node](https://docs.blender.org/manual/en/latest/render/shader_nodes/texture/noise.html) in Shader Editor
* Simplex noise
* GLSL - [Simplex noise shader implementations](https://github.com/ashima/webgl-noise) (Ashima Arts)
* p5.js - [`noise()`](https://p5js.org/reference/#/p5/noise) uses Simplex noise
* Houdini - [Simplex Noise VOP](https://www.sidefx.com/docs/houdini/nodes/vop/simplex.html)
* TouchDesigner - available in [Noise CHOP](https://docs.derivative.ca/Noise_CHOP)
* Blender - [Noise texture](https://docs.blender.org/manual/en/latest/render/shader_nodes/texture/noise.html) with Simplex option
* Worley noise / Voronoi
* GLSL - [Voronoi/Worley shader collections](https://www.shadertoy.com/results?query=voronoi)
* Houdini - [Worley Noise VOP](https://www.sidefx.com/docs/houdini/nodes/vop/worley.html)
* TouchDesigner - [Voronoi/Worley operators](https://docs.derivative.ca/Noise_CHOP)
* Blender - [Voronoi texture node](https://docs.blender.org/manual/en/latest/render/shader_nodes/texture/voronoi.html) in Shader Editor
* vvvv - Voronoi nodes in [vvvv.js](https://vvvv.js.org/) and [vvvv gamma](https://vvvv.org/)
_Code projects:_
* [FastNoise2](https://github.com/Auburn/FastNoise2) (C++, multiple language bindings) - high-performance noise library with SIMD optimization
* [libnoise](http://libnoise.sourceforge.net/) (C++) - procedural noise library with multiple noise types
* [Perlin Noise implementation collections](https://github.com/stegu/perlin-noise) (multiple languages)
---
### Particle system
Collection of independent objects (often points, shapes, images/sprites/textures, or meshes) called _particles_ that are manipulated using dynamic forces and constraints to simulate a wide variety of natural phenomenon like fire, smoke/fog/clouds, fluids, bubbles, and so much more. Often combined with clever visual effects like transparency, blending, and light emission to create the appearance of a coherent but ever-changing entity.
Particle systems are most useful when they can handle large quantities of particles, which means that performance and smart memory management is very important. Like [collision detection](#collision-detection), building your own particle system can be fun and educational, but if you need to achieve something complex at a large scale and/or with high framerates then it's definitely a good idea to leverage dedicated libraries and tools. Many [physics engines](#physics-engine) come with well-made particle systems out of necessity so be sure to consider them even if you don't need all the fun physics functionality.
_Articles:_
* [Particle system](https://en.wikipedia.org/wiki/Particle_system) on Wikipedia
* [Intro to particle systems](https://www.khanacademy.org/computing/computer-programming/programming-natural-simulations/programming-particle-systems/a/intro-to-particle-systems) lesson on Khan Academy
* [The physics of particle systems](https://www.khanacademy.org/partner-content/pixar/effects/particle-physics/a/start-here-fx)
* [Chapter 4. Particle Systems](https://natureofcode.com/book/chapter-4-particle-systems/) from Nature of Code
_Notable software:_
* [Unity's VFX Graph](https://unity.com/visual-effect-graph)
* [Blender's Particle System](https://docs.blender.org/manual/en/latest/physics/particles/index.html)
---
### Physics engine
> [!NOTE]
> Related topics include [collision detection](#collision-detection) and [particle systems](#particle-system).
Simulates the movements and reactions of objects using real-world concepts like mass, velocity, constraints, and forces (like drag, gravity, and friction). Makes use of extremely optimized algorithms for collision detection, physics calculations, geometry management, and more.
_Articles:_
* [Physics engine](https://en.wikipedia.org/wiki/Physics_engine) on Wikipedia
* [Chapter 5. Physics Libraries](https://natureofcode.com/book/chapter-5-physics-libraries/) from Daniel Shiffman's Nature of Code book
* [How to Create a Custom 2D Physics Engine: The Basics and Impulse Resolution](https://gamedevelopment.tutsplus.com/tutorials/how-to-create-a-custom-2d-physics-engine-the-basics-and-impulse-resolution--gamedev-6331) by Randy Gaul
_Notable open-source libraries:_
* [Box2D](https://github.com/erincatto/Box2D) (C++)
* [LiquidFun](http://google.github.io/liquidfun/) (C++) - adds rigid-body and fluid dynamics on top of Box2D
* [box2d.js](https://github.com/kripken/box2d.js) (JavaScript via Emscripten)
* [Planck.js](https://github.com/shakiba/planck.js) (JavaScript, manually ported)
* [Bullet](https://github.com/bulletphysics/bullet3) (C++)
* [ammo.js](https://github.com/kripken/ammo.js/) (direct JavaScript port using Emscripten)
* [Matter.js](http://brm.io/matter-js/) (JavaScript)
* [dyn4j](http://www.dyn4j.org/) (Java)
* [cannon.js](http://schteppe.github.io/cannon.js/) (JavaScript)
* [p2.js](https://github.com/schteppe/p2.js) (JavaScript)
* [ReactPhysics3D](https://www.reactphysics3d.com/) (C++)
* [Chrono](http://projectchrono.org/) (C++)
* [Open Dynamics Engine (ODE)](https://www.ode.org/) (C++)
_Commercial libraries:_
* [PhysX](https://en.wikipedia.org/wiki/PhysX) by Nvidia. Integrated into both Unity and Unreal. Technically open-source now, but oriented more towards commercial/industry applications.
* [Havok](https://www.havok.com/products/havok-physics/)
If you're looking to do physical-based simulations, also take a look at game development and VFX environments like [Unity](https://unity3d.com/learn/tutorials/s/physics?_ga=2.158332858.1012620598.1557960859-2002016059.1556146318), [Unreal](https://docs.unrealengine.com/en-us/Engine/Physics), and [Houdini](https://www.sidefx.com/products/houdini/) for their built-in physics engines.
---
### Polygon clipping
Effectively a Boolean intersection operation that "clips" (removes) parts of one polygon that are outside of another polygon. This can be useful when working with geospatial datasets and vector graphics (like SVGs), which in turn make this useful for plotter artists.
_Algorithms:_
* [Sutherland–Hodgman](https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm) ⭐
* [Greiner–Hormann](https://en.wikipedia.org/wiki/Greiner%E2%80%93Hormann_clipping_algorithm)
* [Vatti](https://en.wikipedia.org/wiki/Vatti_clipping_algorithm)
* [Weiler–Atherton](https://en.wikipedia.org/wiki/Weiler%E2%80%93Atherton_clipping_algorithm)
* [Martinez-Rueda-Feito](https://github.com/mfogel/polygon-clipping/blob/master/paper.pdf)
_Code projects:_
* [clipper-java](https://github.com/lightbringer/clipper-java) by Tobias Mahlmann (Java)
* [ofxClipper](https://github.com/bakercp/ofxClipper) by Christopher Baker (openFrameworks / C++)
* [polygon-clipping](https://github.com/mfogel/polygon-clipping) by Mike Fogel (JavaScript)
---
### Ray tracing
Rendering technique used to create photorealistic images of 3D scenes by tracing the path of individual light rays. Rather than simulate all light rays' journeys from every light source to the camera, only the light rays that actually reach the camera are simulated.
For each pixel of the screen, a ray is cast into the scene until it hits an object. Based on the scene's lighting and the material properties of the hit object, a color value is calculated for the corresponding screen pixel. Using the angle of the specific triangle that was hit along with material properties like surface roughness, refraction, diffusion, one can also determine what direction that light ray must have come from, tracing _that_ path and incorporating it's color information into the pixel color calculation.
The number of "bounces" examined can increase the photorealism of the resulting image, at the cost of computational resources / time.
This process is extremely computationally expensive, so it has historically only been used in pre-rendered applications like movies, animations, and still images. However, recent advancements in graphics card technology (like [NVIDIA's RTX series](https://en.wikipedia.org/wiki/Nvidia_RTX)) are beginning to make this technique available in real-time applications.
_Articles:_
* [Ray tracing (graphics)](https://en.wikipedia.org/wiki/Ray_tracing_(graphics)) on Wikipedia
_Code projects:_
* [appleseed](https://appleseedhq.net/)
* [Intel Embree](https://www.embree.org/)
* [Intel OSPRay](https://www.ospray.org/)
* [POV-Ray](http://www.povray.org/)
* [Mitsuba](https://www.mitsuba-renderer.org/)
---
### Recursion
> [!NOTE]
> Related to [recursion](#recursion).
Method of solving a problem where the solution depends on solutions to smaller instances of the same problem (as opposed to _iteration_). In programming terms, recursion is when a function calls itself during execution. Recursion is fundamentally connected to the concept of [fractals](#fractals).
_Example: computing factorial_
```
function factorialize(n) {
if(n < 0) {
return -1;
} else if(n == 0) {
return 1;
} else {
return n * factorialize(n - 1);
}
}
```
_Articles:_
* [Recursion](https://en.wikipedia.org/wiki/Recursion) on Wikipedia
* [Recursion (computer science)](https://en.wikipedia.org/wiki/Recursion_(computer_science)) on Wikipedia
* [Droste effect](https://en.wikipedia.org/wiki/Droste_effect) on Wikipedia
---
### Shaders
Shaders are programs that are run on the GPU when processing a certain unit of rendering, usually vertices or pixels/fragments; they allow rendering programmers to manipulate their rendering output in any way they see fit.
While shaders, as the name implies, were originally conceived to allow different kinds of lighting/shading calculations, today they're used for a variety of things from lighting calculation through stylized rendering to 2D compositing or post-processing, and even complex geometry manipulations and particle effects.
_Types of shaders:_
* [Compute](https://www.khronos.org/opengl/wiki/Compute_Shader)
* [Fragment](https://www.khronos.org/opengl/wiki/Fragment_Shader)
* [Geometry](https://www.khronos.org/opengl/wiki/Geometry_Shader)
* [Tessellation](https://www.khronos.org/opengl/wiki/Tessellation)
* [Vertex](https://www.khronos.org/opengl/wiki/Vertex_Shader)
_Key concepts:_
* [FBO (framebuffer object)](https://en.wikipedia.org/wiki/Framebuffer_object)
* [GPGPU (general-purpose computing on GPUs)](https://en.wikipedia.org/wiki/General-purpose_computing_on_graphics_processing_units) - the concept of using the GPU to perform computation
* [Ping pong]() - technique in which the output texture of one shader is fed to another shader as an input, sometimes cycling back and forth multiple times. The final texture gets sent to the display, then the shaders are swapped so that the most recent output becomes the input to the next iteration.
* [Render to texture (RTT)](http://www.opengl-tutorial.org/intermediate-tutorials/tutorial-14-render-to-texture/) - instead of rendering a scene to the screen, in this technique it is rendered to an "offscreen" texture that can be reused later.
* [Shading language](https://en.wikipedia.org/wiki/Shading_language)
* [Textures](https://www.khronos.org/opengl/wiki/Texture)
* [Uniform](https://www.khronos.org/opengl/wiki/Uniform_(GLSL)) - a [type qualifier](https://www.khronos.org/opengl/wiki/Type_Qualifier_(GLSL)) indicating a read-only variable passed to a shader from the CPU side of the program. These values will not change within a draw call, and are available to every shader that declares it.
* [Varying](https://www.lighthouse3d.com/tutorials/glsl-12-tutorial/varying-variables/) - a [type qualifier](https://www.khronos.org/opengl/wiki/Type_Qualifier_(GLSL)) indicating a variable that can change within the vertex shader, then passed to the fragment shader as a read-only value.
_Languages:_
* [Cg](https://en.wikipedia.org/wiki/Cg_(programming_language)) - shading language developed by Nvidia in close collaboration with Microsoft
* [CUDA](https://en.wikipedia.org/wiki/CUDA) - parallel computing API that makes it easier to use GPGPU for complicated tasks
* [GLSL (OpenGL Shading Language)](https://en.wikipedia.org/wiki/OpenGL_Shading_Language) - shading language used by OpenGL
* [HLSL (High-Level Shading Language)](https://en.wikipedia.org/wiki/High-Level_Shading_Language) - shading language used by DirectX
_Articles:_
* [The Book of Shaders](https://thebookofshaders.com/) by Patricio Gonzalez Vivo and Jen Lowe
* [Shaders](https://learnopengl.com/Getting-started/Shaders) by Learn OpenGL
* [GLSL Shaders](https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_on_the_web/GLSL_Shaders) on MDN web docs
* [Shaders](https://processing.org/tutorials/pshader/) (Processing) tutorial by Andres Colubi
* [Introducing Shaders](https://openframeworks.cc/ofBook/chapters/shaders.html) (openFrameworks) by Lucasz Karluk, Joshua Noble, Jordi Puig
* [Shader modules](https://vulkan-tutorial.com/Drawing_a_triangle/Graphics_pipeline_basics/Shader_modules) (Vulkan)
_Code tools:_
* [Bonzomatic](https://github.com/Gargaj/Bonzomatic)
* [glslsandbox](http://glslsandbox.com/)
* [RenderMonkey](https://gpuopen.com/archive/gamescgi/rendermonkey-toolsuite/)
* [Shadertoy](https://www.shadertoy.com/)
_Videos:_
* [Shader Coding seminar at Revision 2019](https://www.youtube.com/watch?v=uFFR31t1WMM)
---
### Signed distance function (SDFs)
> [!NOTE]
> Related to [implicit surfaces](#implicit-surface).
A function that returns the distance between a point in space to a mathematically/algorithmically defined surface (called an [implicit surface](#implicit-surface)). This allows algorithms like raymarching and [marching cubes](#marching-cubes) to efficiently render complex 3D surfaces in 2D.
SDFs are increasingly commonly used in computer art, where defining an SDF that describes a large 3D scene entirely in a single pixel [shader](#shaders) allows the code to be ran entirely on the GPU.
_Articles:_
* [Signed distance function](https://en.wikipedia.org/wiki/Signed_distance_function) on Wikipedia
* [Distance functions](http://iquilezles.org/www/articles/distfunctions/distfunctions.htm) (GLSL)
* [Ray Marching and Signed Distance Functions](http://jamie-wong.com/2016/07/15/ray-marching-signed-distance-functions/) by Jamie Wong
_Notable open-source libraries:_
* [hg_sdf](http://mercury.sexy/hg_sdf/) (GLSL)
_Videos:_
* [How to Create Content with Signed Distance Functions by Johann Korndörfer](https://www.youtube.com/watch?v=s8nFqwOho-s)
---
### Soft-body physics
> [!NOTE]
> Related to [mass-spring systems](#mass-spring-system), [cloth simulation](#cloth-simulation), [Verlet physics](#verlet-physics), and [physics engines](#physics-engine).
_Image credit: [CoppeliaSim docs - Physics engine differences](https://manual.coppeliarobotics.com/en/physicsEngineDifferences.htm)_
Soft-body physics is the applied, real-time counterpart to [mass-spring systems](#mass-spring-system): simulating volumetric objects - rubber, flesh, jelly, foam, organs - that deform under force and recover their shape rather than staying rigid. Unlike [cloth simulation](#cloth-simulation), which models thin 2D sheets, soft-body solvers operate on 3D volumes (tetrahedral meshes, voxel grids, or particle clouds) and must resist compression as well as stretching, giving deformable objects a sense of internal volume and squishiness.
Several families of techniques compete for this problem, each trading accuracy for speed differently:
* Mass-spring - the volumetric extension of [mass-spring systems](#mass-spring-system): tetrahedral or lattice structures of point masses connected by springs. Fast and simple, but prone to visible artifacts (bulging, asymmetric stretching) since spring networks don't perfectly capture rotational/volumetric behavior.
* [Finite Element Method (FEM)](https://en.wikipedia.org/wiki/Finite_element_method) - discretizes the body into tetrahedral elements and solves continuum-mechanics stress/strain equations directly, giving physically accurate results at higher computational cost. Common in engineering, biomechanics, and high-end VFX.
* Shape matching - a meshless technique that computes a "goal" rigid/deformed shape for a cluster of particles each frame and pulls particles toward it; cheap, stable, and popular in games.
* Position Based Dynamics (PBD) / XPBD - treats constraints (distance, volume, bending) as positional corrections solved iteratively rather than forces, which is unconditionally stable and easy to combine with cloth, rigid bodies, and fluids in one solver. XPBD adds proper stiffness independent of iteration count and time step.
_Key terms:_
* Tetrahedral mesh - the volumetric equivalent of a triangle mesh; most FEM and volumetric mass-spring solvers discretize a soft body into tetrahedra.
* Volume constraint - a constraint that resists compression/expansion of a tetrahedron or cell, preventing unrealistic "deflating" under stress.
* Stress and strain - core FEM quantities describing internal forces and deformation, related through a material's stiffness (its constitutive model).
* Shape matching - fitting a rigid or affine transform to a rest-shape point cluster each frame, then pulling particles toward the transformed goal positions.
* Corotational formulation - a technique used in FEM/mass-spring elasticity models to separate rotation from strain, avoiding ghost forces when elements rotate.
_Articles:_
* [Soft-body dynamics](https://en.wikipedia.org/wiki/Soft-body_dynamics) on Wikipedia
* [Meshless Deformations Based on Shape Matching](https://matthias-research.github.io/pages/publications/MeshlessDeformations_SIG05.pdf) (PDF) by Müller, Heidelberger, Teschner, and Gross - foundational shape-matching paper
* [Position Based Dynamics](https://matthias-research.github.io/pages/publications/posBasedDyn.pdf) (PDF) by Müller, Heidelberger, Hennix, and Ratcliff
* [XPBD: Position-Based Simulation of Compliant Constrained Dynamics](https://matthias-research.github.io/pages/publications/XPBD.pdf) (PDF) by Macklin, Müller, and Chentanez
* [FEM Simulation of 3D Deformable Solids: A Practitioner's Guide](https://www.physicsbasedanimation.com/2012/08/15/siggraph-course-fem-simulation-of-3d-deformable-solids-a-practitioners-guide-to-theory-discretization-and-model-reduction/) - SIGGRAPH course by Sifakis and Barbič covering FEM soft-body simulation from first principles
_Videos:_
* [Coding Challenge 177: Soft Body Physics](https://thecodingtrain.com/challenges/177-soft-body-character) by Daniel Shiffman (Coding Train)
* [Ten Minute Physics](https://www.youtube.com/c/TenMinutePhysics) by Matthias Müller - short tutorials covering shape matching, PBD, XPBD, and soft-body simulation from scratch
* [10 - Simple and unbreakable simulation of soft bodies](https://www.youtube.com/watch?v=uCaHXkS2cUg) by Ten Minute Physics
_Notable tools and libraries:_
* [PositionBasedDynamics](https://github.com/InteractiveComputerGraphics/PositionBasedDynamics) (C++) by Jan Bender - open-source PBD/XPBD library covering cloth, soft bodies, fluids, and rigid bodies
* [SOFA](https://www.sofa-framework.org/) - open-source framework for real-time multi-physics simulation, widely used in biomedical soft-tissue and soft-robotics research
* [PhysX 5](https://github.com/NVIDIA-Omniverse/PhysX) by NVIDIA - GPU-accelerated FEM-based soft body simulation, open-sourced from the former NVIDIA Flex library
* Unity
* [Obi Softbody](https://obi.virtualmethodstudio.com/manual/7.0/softbodysetup.html) by Virtual Method - particle-based soft body simulation
* Unreal
* [Chaos Flesh](https://dev.epicgames.com/documentation/unreal-engine/chaos-flesh-overview?lang=en-US)
* TouchDesigner
* [Flex](https://docs.derivative.ca/Flex) - GPU particle solver (Nvidia Flex) for particle-based soft materials and fluids
* Processing
* [toxiclibs](https://github.com/postspectacular/toxiclibs) - Verlet-based particle/spring physics library commonly used for soft-body and cloth-like simulations
* p5.js
* [p5-matter](https://github.com/pzp1997/p5-matter) - wraps Matter.js's soft-body composite meshes
* [toxiclibs.js](https://haptic-data.com/toxiclibsjs/examples/soft-body-square) - JavaScript port of toxiclibs
* Three.js
* [Ammo.js soft body volume demo](https://threejs.org/examples/physics_ammo_volume.html) (first-party) - official three.js example using the Bullet-based Ammo.js soft body solver
* React Three Fiber
* [use-ammojs](https://github.com/notrabs/use-ammojs) - Ammo.js/Bullet physics hooks with soft body
* Houdini
* [Vellum](https://www.sidefx.com/docs/houdini/vellum/overview.html) - unified PBD solver for cloth, hair, grains, and soft bodies
* Blender
* [Soft Body](https://docs.blender.org/manual/en/latest/physics/soft_body/index.html)- built-in mass-spring-based soft body physics
_Code projects:_
* [Ten Minute Physics - Soft Bodies](https://github.com/matthias-research/pages/blob/master/tenMinutePhysics/10-softBodies.html) by Matthias Müller - self-contained XPBD soft-body demo in vanilla JavaScript
* [ammo.js Soft Body Volume demo](https://github.com/kripken/ammo.js/blob/main/examples/webgl_demo_softbody_volume/index.html) - Bullet physics soft-body simulation ported to the web via three.js
* [Soft Body Character](https://thecodingtrain.com/challenges/177-soft-body-character/) by The Coding Train - p5.js soft-body character built with toxiclibs.js springs and particles
---
### Spatial index
Data structure (most commonly a binary tree) that enables fast and efficient storage, manipulation, and querying of large amounts of spatial data (points in space). Commonly used by [particle systems](#particle-system).
_Common types:_
* [Quadtree](https://en.wikipedia.org/wiki/Quadtree) - each node has exactly four children
* [Octree](https://en.wikipedia.org/wiki/Octree) - each node has exactly eight children
* [k-d tree](https://en.wikipedia.org/wiki/K-d_tree)
* [R-tree](https://en.wikipedia.org/wiki/R-tree)
_Related topics:_
* [k-nearest neighbhor (knn) search](https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm)
* [Spatial database](https://en.wikipedia.org/wiki/Spatial_database) on Wikipedia
* [Binary space partitioning](https://en.wikipedia.org/wiki/Binary_space_partitioning) on Wikipedia
_Articles:_
* [Spatial index](https://en.wikipedia.org/wiki/Spatial_database#Spatial_index) section on Wikipedia article for Spatial database
_Videos:_
* Coding Challenge #98: [Part 1](https://www.youtube.com/watch?v=OJxEcs0w_kE), [Part 2](https://www.youtube.com/watch?v=QQx_NmCIuCY), [Part 3](https://www.youtube.com/watch?v=z0YFFg_nBjw) by Daniel Shiffman
---
### Vectors
Vectors (specifically _Euclidean_ or _geometric_ vectors) are simple data structures that store spatial information representing discrete points, displacement, or forces. Understanding how to work with vectors is one of the most critical skills to learn when working with physically-based simulations and digital morphogenesis.
Vectors can be manipulated using familiar algebraic operations like addition, subtraction, multiplication, and division, which makes them extremely useful when simulating physically-based systems with objects (or agents) in motion. We can have one vector that represents a point in space and another that represents a force (like gravity or wind), then apply that force to the point by adding the two vectors together.
The term "vector" has slightly different meanings and uses in mathematics, physics, machine learning, biology, and more. In the context of digital morphogenesis, you'll most often encounter vectors as they are used in physics, representing discrete physical properties like position, displacement, velocity, direction, and more.
_Properties:_
* [Magnitude / length](https://natureofcode.com/book/chapter-1-vectors/#15-vector-magnitude) ($\|\mathbf{v}\|$) = the "size" of a vector obtained by taking the square root of the sum of the square of each of the vector's components (an abstraction of the Pythagorean Formula). Mathematically, $\|\mathbf{v}\| = \sqrt{v_x^2 + v_y^2 + v_z^2 + \ldots}$.
* Heading / direction / angle = the direction in which a vector is pointing. Applicable when using vectors to represent forces, but not so much when representing discrete points in space.
_Key concepts:_
* Unit vector = any vector with a magnitude (length) of exactly 1.
* [Normalization](https://natureofcode.com/book/chapter-1-vectors/#16-normalizing-vectors) = operation whereby a vector is divided by its own magnitude, resulting in a _unit vector_ with the same heading (direction) as the original vector.
_Algebraic operations:_
| Operation | Using two vectors | Using a vector and a scalar |
|---|---|---|
| Addition | $\mathbf{v}_1 + \mathbf{v}_2 = \{v_{1x} + v_{2x}, v_{1y} + v_{2y}, \ldots\}$ | $\mathbf{v} + 10 = \{v_x + 10, v_y + 10, \ldots\}$ |
| Subtraction | $\mathbf{v}_1 - \mathbf{v}_2 = \{v_{1x} - v_{2x}, v_{1y} - v_{2y}, \ldots\}$ | $\mathbf{v} - 10 = \{v_x - 10, v_y - 10, \ldots\}$ |
| Multiplication | $\mathbf{v}_1 \times \mathbf{v}_2 = \{v_{1x} \times v_{2x}, v_{1y} \times v_{2y}, \ldots\}$ | $\mathbf{v} \times 10 = \{v_x \times 10, v_y \times 10, \ldots\}$ |
| Division | $\mathbf{v}_1 / \mathbf{v}_2 = \{v_{1x} / v_{2x}, v_{1y} / v_{2y}, \ldots\}$ | $\mathbf{v} / 10 = \{v_x / 10, v_y / 10, \ldots\}$ |
| Dot product | $\mathbf{v}_1 \cdot \mathbf{v}_2 = (v_{1x} \times v_{2x}) + (v_{1y} \times v_{2y}) + \ldots$ (produces a single number) |
Not applicable. |
| Cross product | $\mathbf{v}_1 \times \mathbf{v}_2 = \|\mathbf{v}_1\| \|\mathbf{v}_2\| \sin(\theta) \mathbf{n}$ Where: $\theta$ = angle between $\mathbf{v}_1$ and $\mathbf{v}_2$; $\mathbf{n}$ = unit normal vector. Produces a vector. |
Not applicable. |
### VDBs
> [!NOTE]
> Related or similar to [spatial indices](#spatial-index) and [fluid simulations](#fluid-simulation)
_Image credit: Said Al Attrach - [VDB: A Deep Dive](https://jangafx.com/insights/vdb-a-deep-dive)_
Grid-based data structure designed for storing and manipulating sparse 3D volumetric data - grids of voxels (3D pixels). Unlike a naive 3D array where every voxel consumes memory regardless of content, VDBs use a [B-tree](#spatial-index)-like hierarchical structure that only stores voxels containing meaningful data, making them extremely memory-efficient for large, sparse volumes. Named for their characteristics (**V**olumetric, **D**ynamic, and **B**-tree-like), they approximate an "infinite" index space with fast O(1) random access, cache-coherent traversal, and support for dynamic topology changes.
VDBs are the industry standard in VFX and animation for representing volumetric data like smoke, fire, liquids, and distance fields. [OpenVDB](https://www.openvdb.org), an Academy Award-winning open-source library originally developed by DreamWorks Animation, has become the de facto standard format for volumetric data interchange in professional VFX pipelines.
_How they work at a glance:_
The VDB hierarchy typically has four levels: a root node (hash table), intermediate nodes, and leaf nodes (storing fixed blocks of voxels, usually 8×8×8). When accessing or inserting data, the tree is traversed from root to leaf, skipping branches that contain no data. This structure avoids allocating memory for empty space while maintaining fast random access patterns typical of dense grids.
_Articles:_
* [VDB: High-Resolution Sparse Volumes with Dynamic Topology](https://www.museth.org/Ken/Publications_files/Museth_TOG13.pdf) (PDF) by Ken Museth - the foundational 2013 ACM Transactions on Graphics paper introducing VDB at DreamWorks Animation
_Notable tools and libraries:_
* ⭐ OpenVDB (C++, Python bindings) by Academy Software Foundation
* [GitHub repo](https://github.com/AcademySoftwareFoundation/openvdb) - open-source, cross-platform library maintained by the VFX industry
* [Official docs](https://www.openvdb.org/documentation/) - API reference and guides
* Includes tools for data I/O, visualization (vdb_view), filtering, and mesh generation
* Blender
* [Volume objects](https://docs.blender.org/manual/en/latest/modeling/volumes/introduction.html) - native VDB/OpenVDB volume support
* [Import VDB](https://docs.blender.org/manual/en/latest/modeling/geometry_nodes/input/import/vdb.html) Geometry Node
* [EmberGen](https://jangafx.com/software/embergen/) - real-time volumetric fluid simulator using VDB-compatible formats for export
* Houdini
* [OpenVDB volumes](https://www.sidefx.com/docs/houdini/model/volumes.html#openvdb-volumes) - native VDB support
* Three.js
* [mjurczyk/openvdb](https://github.com/mjurczyk/openvdb) - adds `.vdb` format support with a VDBLoader as well as a `FogVolume` class for working with the data
_Code projects:_
* [fluid-engine-OpenVDB](https://github.com/yangfengzzz/fluid-engine-OpenVDB) (C++) - fluid simulation engine adapting algorithms from fluid-engine-dev to leverage OpenVDB's sparse structure for memory-efficient 3D grid-based physics
* [Liquid3D](https://github.com/Konodinger/Liquid3D) (C++) - IISPH (Implicit Incompressible SPH) fluid simulation that uses OpenVDB to mesh fluid particles for Blender import
* [OpenVDB_Visualizer](https://github.com/Elyg/OpenVDB_Visualizer) (C++) - volume rendering application using OpenGL and Qt5 to visualize and explore VDB files
---
### Wave Function Collapse (WFC)
> [!NOTE]
> Related to [Tiling / tessellation](#tiling--tessellation).
Method of procedurally generating textures and tilemaps that are similar to a single source image using ideas from quantum mechanics. Originally developed by Maxim Gumin, WFC learns local patterns and constraints from a source image, then iteratively generates new content by "collapsing" possibilities while respecting learned rules. The name references quantum superposition (many possible states simultaneously) and measurement (collapsing to a single outcome).
The algorithm works in two main steps: first, _extract patterns_ by scanning the source image and recording which local arrangements of pixels (or tiles) occur; second, _generate output_ by starting with all possibilities everywhere, then repeatedly choosing a location with minimum entropy (fewest valid options) and randomly collapsing it to one valid choice, then propagating constraints to neighbors to ensure the result remains compatible.
The key insight is that local compatibility - enforcing that neighboring regions respect learned patterns - naturally produces globally coherent, recognizable results even though the algorithm makes only local decisions. This approach produces remarkably human-like outputs and has become popular for game level design, texture synthesis, and procedural content generation.
_Algorithm outline:_
_\* indicates a potential simulation parameter_
1. Scan the source image to extract all $N \times N$\* local patterns (e.g., all 3×3 neighborhoods of pixels or tiles).
2. Initialize the output grid with all patterns marked as possible at every location.
3. In each iteration:
1. Find the location with minimum entropy (fewest valid patterns remaining).
2. If no location remains, generation is complete.
3. If a location has zero valid patterns (contradiction), backtrack or restart.
4. Randomly select one valid pattern from that location and collapse it (remove all other patterns).
5. Propagate constraints: for each neighbor, remove any patterns that would be incompatible with the collapsed pattern (based on learned adjacencies).
4. Repeat until the entire grid is determined.
_Key terms:_
* Pattern extraction - scanning the source image to find all valid local neighborhoods.
* Entropy - in this context, the number of valid choices remaining at a location; minimum entropy heuristic prioritizes constrained areas.
* Wave - the superposition of all possible patterns at each location before collapse.
* Collapse - randomly choosing one pattern and removing all alternatives.
* Constraint propagation - updating neighbors to eliminate patterns incompatible with a collapsed choice; ensures global coherence.
* Contradiction / backtracking - if all patterns are eliminated at some location, the algorithm has failed and must restart or undo recent decisions.
* Tile-based vs. pixel-based - the algorithm works on discrete units (tiles for maps, pixels for images) and can be adapted to 2D or 3D.
_Articles:_
* Original [WaveFunctionCollapse Github repo](https://github.com/mxgmn/WaveFunctionCollapse) by Maxim Gumin (mxgmn)
* [Generating Worlds With Wave Function Collapse](http://www.procjam.com/tutorials/wfc/) by Joseph Parker
* [Doodle Insights #19: Logic Data Generation (feat. WFC made easy)](https://trasevol.dog/2017/09/01/di19/) by Rémy Devaux (TRASEVOL_DOG)
_Code projects:_
* [ofxWFC3D](https://github.com/action-script/ofxWFC3D) (openFrameworks add-on) by Nuño de la Serna
* [ndwfc](https://github.com/LingDong-/ndwfc) (JavaScript, Node.js) by Lingdong Huang.
_Videos:_
* [WaveFunctionCollapse Supercharged with PDG for Level Generation](https://vimeo.com/400993662) talk by Paul Ambrosiussen at HOUDINI HIVE GAMEDEV
---
### Weighted Voronoi stippling
> [!NOTE]
> Related to [Delaunay triangulation and Voronoi diagrams](#delaunay-triangulation-and-voronoi-diagrams), [dithering](#dithering), and [Lloyd's relaxation](#lloyds-relaxation).
_Image credit: Windell Oskay (Evil Mad Scientist Laboratories) - [StippleGen: Weighted Voronoi stippling and TSP paths in Processing](https://www.evilmadscientist.com/2012/stipplegen-weighted-voronoi-stippling-and-tsp-paths-in-processing)._
Weighted variant of [Lloyd's relaxation](#lloyds-relaxation) that uses the darkness (or density) of an underlying image to bias where points settle, producing a stippled illustration made of dots whose size and/or spacing follows the image's tone - more and/or larger dots in darker regions, fewer/smaller dots in lighter ones. Because points are still spread evenly within their local Voronoi region even as they respect image density, the result reads as a convincingly hand-drawn stipple illustration rather than a mechanical dither pattern.
Frequently paired with [TSP](#travelling-salesman-problem-tsp) path-finding to connect the stippled points into a single continuous line, making it a popular technique for pen plotter art.
_Algorithm at a glance:_
1. Scatter an initial set of points across the image, with more points landing in darker regions (e.g. via rejection sampling against pixel brightness).
2. Compute the [Voronoi diagram](#delaunay-triangulation-and-voronoi-diagrams) for the current points.
3. For each Voronoi cell, compute its centroid using the underlying image as a density function - darker pixels pull the centroid more strongly - rather than treating every pixel in the cell equally, as in standard Lloyd's relaxation.
4. Move each point to its cell's weighted centroid.
5. Repeat for some number of iterations\*, or until points stop moving significantly.
6. Render each final point as a dot, optionally sized or oriented based on local density.
_\* indicates a potential simulation parameter_
_Key terms:_
* Density function - the underlying image data used to weight where points are pulled during relaxation; typically derived from pixel brightness/darkness.
* Weighted centroid - center of mass of a Voronoi cell computed using the density function, as opposed to the plain geometric centroid used in standard [Lloyd's relaxation](#lloyds-relaxation).
_Articles:_
* [Weighted Voronoi Stippling](https://www.cs.ubc.ca/labs/imager/tr/2002/secord2002b/secord.2002b.pdf) (PDF) by Adrian Secord. The original 2002 paper.
* [Weighted Voronoi Stippling](https://github.com/ReScience-Archives/Rougier-2017) by Nicolas Rougier - a peer-reviewed reproduction of Secord's algorithm published in ReScience (2017).
* [Creating Traveling Salesman Art With Weighted Voronoi Stippling](https://jxmo.io/posts/traveling-salesman-art) by Jack Morris
_Videos:_
* [Coding Challenge #181: Weighted Voronoi Stippling](https://thecodingtrain.com/challenges/181-image-stippling/) by Daniel Shiffman (p5.js and d3.js)
_Notable software:_
* [StippleGen](https://github.com/evil-mad/stipplegen) by Evil Mad Scientist Laboratories - Processing-based tool that generates weighted Voronoi stipple drawings, including [TSP path](#travelling-salesman-problem-tsp) art.
* [Voronoi Stippling Art Generator](https://www.cyber-consult.org/labs/dots/) by Joe Shenouda - browser-based tool for turning any photo into a stipple drawing
_Creative projects:_
_Code projects:_
* [Swingline](https://www.mattkeeter.com/projects/swingline/) by Matt Keeter - C implementation that runs up to 10-20x faster than StippleGen ([Github repo](https://github.com/mkeeter/Swingline))
* [Voronoi Stippling](https://observablehq.com/@mbostock/voronoi-stippling) by Mike Bostock on Observable (JavaScript and D3.js)
* [weighted-voronoi-stippling](https://github.com/amaurs/weighted-voronoi-stippling) by Amaury Sanchez (JavaScript) - straightforward reference implementation of Secord's algorithm
* [weighted-voronoi-stippling](https://github.com/jtompuri/weighted-voronoi-stippling) by Juha Tompuri (Python) - high-performance, Numba-accelerated implementation that exports PNG and TSP tour files
* [Stippling and TSP art](http://dahtah.github.io/imager/stippling.html) by Simon Barthelmé - tutorial with runnable code using the `imager` R package
| Application | Description | Cost |
|---|---|---|
| Houdini | Industry-level procedural VFX application with graphical node-based workflow. Excellent for creating high-quality renderings and animations based on generative algorithms. Allows for scripting with Python and VEX (proprietary language). |
|
| Rhino | NURBS-based CAD program popular with architects and industrial designers. Strong ecosystem of advanced computational design plugins built by highly skilled community. Less focus on rendering, animation, and interactivity; more for form-finding with fabrication in mind. Allows for scripting with Python, RhinoScript, and more.List of useful Rhino plugins
|
|
| Unity |
Full-featured game engine with tools for interactivity, physics, lighting, level/character design, and more. Allows for scripting with C#. Direct competitor of Unreal, with a reputation for being more focused on "user friendliness" and less on hyper-realism, though the gap is shrinking rapidly. Notable features
|
|
| Unreal | Full-featured game engine with very similar feature set to Unity (it's direct competitor). Has reputation for being more focused on hyper-realism, and thus is used more by high-end games studios. [?] |
Free with royalty on commercial products |
| Structure Synth | Application for generating surprising and complex fractal 3D structures using a design grammar. | Free |
| TouchDesigner | Visual node-based environment for real-time interactive multimedia content useful for performances, installations, and fixed media works. Has roots in Houdini 4 and is considered a spin-off optimized for real-time performance work (hence the company name, Derivative). |
|
| Cinema 4D | Four versions ranging from $995-$3695 |