Digital morphogenesis

Digital morphogenesis is the exploration of how shapes, forms, and patterns emerge in nature through the use of computational modeling and generative systems based on biological, chemical, and physical processes. It draws upon research from practically every area of the natural sciences and has applications in architecture, digital fabrication, art, engineering, biomedicine, and more.

With such a cross-disciplinary topic it can be hard to keep track of and correlate all the interesting bits of knowledge that one comes across, which is where this list comes in. The goal of this list is to succinctly catalog various growth algorithms and lab experiments along with relevant math, physics, and programming concepts in one place in order to (1) serve as a sort of “cheat sheet” reference for developers and computer artists, and (2) spark new insights by making it easier to see relationships between seemingly disparate topics.

Contributions are always welcome! If you’d like to add a description for any topic, or have some interesting and relevant links to share, or know of a topic that should be included somewhere in this document, please feel free to open an issue or a PR with your changes.

 

Table of contents
Growth algorithms [#]
Math and physics topics [#]
Natural phenomena

See Natural-phenomena.md

Lab experiments [#]
Useful code patterns and techniques [#]

Books, publications, and talks
Software

REF:Jason Webb

Growth algorithms

Dielectric breakdown model (DBM)

  • Rigid and elastic bond models

Articles: * Dielectric breakdown model on Wikipedia * Fractal Dimension of Dielectric Breakdown (PDF) by L. Niemeyer, L. Pietronero, and H. J. Wiesmann


Diffusion-limited aggregation (DLA)

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.

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 – name of characteristic branching structure that emerges

Articles: * Diffusion-limited aggregation on Wikipedia * Diffusion-Limited Aggregation, a Kinetic Critical Phenomenon (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? (2000) by Leonard Sander. Follow-up to the original article. * Simulating 2D diffusion-limited aggregation (DLA) with JavaScript by Jason Webb * DLA - Diffusion Limited Aggregation by Paul Bourke * Diffusion-Limited Aggregation by Softology * Pushing 3D Diffusion-Limited Aggregation even further by Softology

Code projects: * dlaf (C++ w/ Boost) by Michael Fogleman
Introduces a novel, super-efficient method of collision detection, described here. * 2D diffusion-limited aggregation (DLA) experiments in JavaScript (Github repo) by Jason Webb * simutils-0001: Diffusion limited aggregation by Karsten Schmidt (toxiclibs) * Simulate: Diffusion-Limited Aggregation from FORM+CODE book examples * Dendron Processing sketch by Golan Levin

Creative projects: * Aggregation series by Andy Lomas

Notable software: * Visions of Chaos * glChAoS.P by Michele Morrone (BrutPitt)

Videos: * Coding Challenge #34: Diffusion-Limited Aggregation by Daniel Shiffman (Github repo) * Coding Challenge #127: Brownian Tree Snowflake by Daniel Shiffman (Github repo) * VEX in Houdini: Diffusion Limited Aggregation (Plus Rendering In Mantra & Redshift) by Entagma


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 by Jason Webb * Differential line by Anders Hoff (inconvergent) * Sheparding Random Growth by Anders Hoff (inconvergent) * Differential Mesh Growth discussion thread on od|force forums * Organic Labrynths and Mazes (PDF) paper by Hans Pederson and Karen Singh

Code projects: * 2D differential growth experiments by Jason Webb (Github repo) * Differential line growth with Processing by Alberto Giachino * Real-time differential growth in JavaScript by Adrian Toncean * Differential Line Growth by Maritz Schwind of Entagma * Differential Growth by Lionel Radisson

Creative projects: * Floraform – an exploration of differential growth by Nervous System * Floraform Chandelier at World Expo 2017 in Astana, Kazakhstan by Nervous System


Eden growth model

Created by Murray Eden in 1961, 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.

Articles: * A Two Dimensional Growth Process by Murray Eden (original 1961 paper)


Physarum

Image credit to Sage Jenson ([@mxsage](https://www.instagram.com/mxsage/))

Technique for modelling the observed behaviors of the slime mold physarum polycephalum using a large-scale particle system and agent-based modelling. Originally described in 2010 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.

Algorithms at a glance:


Articles: * Characteristics of Pattern Formation and Evolution in Approximations of Physarum Transport Networks (PDF) by Jeff Jones – original paper * Physarum Simulations by Softology * Physarum polycephalum on Wikipedia

Code projects: * Simulating slime mold with WebGL by Ken Voskuil * physarum (JavaScript with ThreeJS) by Nicolas Barradeau * Physarum (Unity) by Deniz Bicer * Physarealm (Rhino + Grasshopper) by Ma Yidong * Physarum (C++, with 2D and 3D implementations) by Jan Ivanecky

Creative projects: * physarum by Sage Jenson (mxsage) * Slime mold by Georgios Cherouvim


Primordial Particle System


Articles: * Primordial Particle Systems from the Artificial Life Laboratory in Graz, Austria. * How a life-like system emerges from a simple particle motion law Thomas Schmickl, Martin Stefanec & Karl Crailsheim


Reaction-diffusion

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): Reaction-diffusion equation from Karl Sims

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 3×3 Laplacian transform * Reaction chance – probability that one A will be converted to a B when in the presence of two Bs. * Gray-Scott model * Pearson’s classification * Turing patterns

Articles: * Reaction-diffusion system on Wikipedia * Reaction-Diffusion Tutorial by Karl Sims * Reaction-Diffusion by the Gray-Scott Model: Pearson’s Parametrization by Robert Munafo (mrob) * Reaction Diffusion: The Gray-Scott Algorithm by Algosome * The Chemical Basis of Morphogenesis (PDF) paper by Alan Turing (1951)

Notable tools: * Ready

Code projects: * Gray–Scott Reaction Diffusion (JavaScript + WebGL) by Mike Bostock * Gray-Scott – JavaScript experiments by @pmneila * simutils-0001: Gray-Scott reaction diffusion by toxiclibs * ofxReactionDiffusion add-on for openFrameworks by Yuma Matsune * ofxRD add-on for openFrameworks by aanri * Reaction Diffusion (JavaScript + WebGL) by Red Blob Games * Reaction Diffusion by Ken Voskuil (look in the DOM) * Reaction-Diffusion Simulation in Three.js (JavaScript + ThreeJS) by Jonathan Cole * Reaction diffusion with C++ and SFML by Deedone * Reaction-Diffusion simulation with C++, SFML, & Cuda by Luka Mattfield (@Solidsilver) * ReaDDy (C++ with Python bindings) * RDSystem (Unity) by Keijiro Takahashi

Creative projects: * Jonathan McCabe‘s multi-scale Turing pattern series. See Diatomaceous, Bone Music [2] [3], Multi-Scale Turing Patterns and others * See his paper Cyclic Symmetric Multi-Scale Turing Patterns (PDF), and this post from Softology explaining it. * 3D Printed Reaction Diffusion Patterns Instructable by Reza Ali * Processing: Reaction Diffusion Halftone patterns by Ignazio Lucenti * Coral Cup by Nervous System * Reaction Lamps by Nervous System * Reaction Table and reaction shelf by Nervous System * Reaction-Diffusion Media Wall by Karl Sims * DIFFUSION by Kouhei Nakama * Reaction Diffusion using point clouds by David Grzesik. See his write-up here (PDF) * Grey Scott’s Reaction Diffusion – Houdini VEX by Ali Seiffouri

Videos: * Reaction Diffusion video series for Houdini by Entagma: * Part I: Theory * Part II: Implementation * Part III: Shaping Growth * Coding Challenge #13: Reaction Diffusion Algorithm in p5.js by Daniel Shiffman (Github repo with both p5.js and Processing source code) * Reaction Diffusion: A Visual Explanation 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 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 = 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 (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 (PDF) 2007 paper by Adam Runions, Brendan Lane, and Przemyslaw Prusinkiewicz * Modeling organic branching structures with the space colonization algorithm and JavaScript by Jason Webb * Procedurally Generated Trees with Space Colonization Algorithm in XNA C# by Jon Gallant * Part 26: Trees by Michael Goodfellow * Art-directing procedural vegetation in Houdini using a space colonization algorithm (PDF) by Marta Feriani

Creative projects: * Hyphae and Xylem series by Nervous System * Also see their Xylem Experiments and Improvements write-up * Bromeliad and Calyx lamps by Nervous System

Code projects: * ofxSpaceColoinzation add-on for openFrameworks * space-colonization (JavaScript) by Nick Nikolov * Dendrite (Unity) by mattatz * Grower (Maya plugin) by Jose Esteve * Venation (Processing) by Niel McLaren * hyphae (Julia) by Jamie Blondin * hyphae and hyphae_ani by Anders Hoff (inconvergent) * 2d-space-colonizations-experiments (JavaScript) by Jason Webb

Videos: * Coding Challenge #17: Fractal Trees – Space Colonization by Daniel Shiffman (Github repo with source code for p5.js and Processing)

 

Math and physics topics

Archimedean solids

Set of 13 semi-regular convex polyhedra composed of regular polygons meeting in identical vertices, excluding the 5 Platonic solids (which are composed of only one type of polygon) and excluding the prisms and antiprisms.

Each shape can be constructed by starting with one of the 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
4 hexagons
18 12
Cuboctahedron 8 triangles
6 squares
24 12
Truncated cube 8 triangles
6 octagons
36 24
Truncated octahedron 6 squares
8 hexagons
36 24
Rhombicuboctahedron 8 triangles
18 squares
48 24
Truncated cuboctahedron 12 squres
8 hexagons
6 octagons
72 48
Snub cube 32 triangles
6 squares
60 24
Icosidodecahedron 20 triangles
12 pentagons
60 30
Truncated dodecahedron 20 triangles
12 decagons
90 60
Truncated icosahedron 12 pentagons
20 hexagons
90 60
Rhombicosidodecahedron 20 triangles
30 squares
12 pentagons
120 60
Truncated icosidodecahedron 30 squares
20 hexagons
12 decagons
180 120
Snub dodecahedron 80 triangles
12 pentagons
150 60

Articles: * Archimedean solid on Wikipedia * Archimedean Solid on Wolfram MathWorld * Archimedean Polyhedra by George Hart

Videos: * Platonic and Archimedean solids by Henry Segerman


Cellular automata (CA)

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 and Moore, though others exist. * Rule(s) – 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. * Generation – result of one iteration of the system.

Well-known rules: * Brian’s Brain * Game of Life * Langton’s Ant * Wireworld

Articles: * Cellular automaton on Wikipedia * Elementary Cellular Automaton on Wolfram MathWorld * Chapter 7. Cellular Automata from Daniel Shiffman’s Nature of Code book

Creative projects: * KnitYak: Custom mathematical knit scarves by Fabienne “fbz” Serriere * 3D printed Game of Life shoes by Francis Bitonti

Notable software: * MCell (Mirek’s Cellebration) * Golly * Visions of Chaos


Collatz conjecture


Videos: * Coding in the Cabana 2: Collatz Conjecture by Daniel Shiffman (Github repo with code for p5.js and Processing)


Cymatics

See 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 on Wikipedia * Modal vibrational phenomena on Wikipedia

Creative projects: * CYMATICS: Science Vs. Music by Nigel Stanford * Cymatics by Susi Sie * The Essence of Sound by Susi Sie


Delaunay triangulation and Voronoi diagrams

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 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 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, 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 on Wikipedia * Voronoi diagram on Wikipedia


Fibonacci sequence

Related to 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 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

Sequence begins with:

Articles: * Fibonacci sequence on Wikipedia * Fibonacci Sequence on Math Is Fun * Fibonacci Number 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) enables extraction of waveforms from music for the purposes of audio visualization.

Articles: * Fourier series on Wikipedia * Fourier Series on Wolfram MathWorld * Fourier Series on Math Is Fun

Videos: * What is a Fourier Series? (Explained by drawing circles) by Smarter Every Day * But what is the Fourier Transform? A visual introduction by 3Blue1Brown * Coding Challenge #125: Fourier Series by Daniel Shiffman * Coding Challenge #130.1: Drawing with Fourier Transform and Epicycles by Daniel Shiffman * Coding Challenge #130.2: Fourier Transform User Drawing by Daniel Shiffman * Coding Challenge #130.3: Fourier Transform Drawing with Complex Number Input by Daniel Shiffman


Fractals

Infinitely complex patterns generated via 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 – ratio providing a statistical index of complexity comparing how detail in a fractal changes with scale. * Self-similarity – when something is exactly or approximately similar to a part of itself.

Notable fractals: * Apollonian gasket (a.k.a. curvilinear Sierpiński gasket) * Barnsley fern * Cantor set * Chaos game * Dragon curve * Hilbert curve * Iterated function systems (IFS) * Lindenmayer systems (L-systems) * Julia set * Koch snowflake * Menger sponge * Mandelbrot set (related: Mandelbulb and Buddhabrot) * Sierpiński triangle / gasket / sieve and carpet * … and so much more

Articles: * Fractal on Wikipedia * List of fractals by Hausdorff dimension on Wikipedia * Fractals, Caos, Self-Similarity by Paul Bourke * Chapter 8. Fractals in Daniel Shiffman’s Nature of Code book

Notable software: * glChAoS.P by Michele Morrone (BrutPitt)


Geodesic dome


Articles: * Geodesic dome on Wikipedia


Golden angle

Related to the golden ratio and phyllotaxis.

Radial version of the 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 on Wikipedia * The Golden Angle by Go Figure

Creative projects: * Golden Angle sculpture series by John Edmark


Golden ratio

Related to the 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:

Expressed as line segments:

Articles: * Golden ratio on Wikipedia * Golden Ratio on Math is Fun * Golden Ratio on Wolfram MathWorld


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 in order to represent the surface on a 2D screen.

Examples of implicit surface equations:

Surface Equation
Plane
Sphere
Torus
Surface of genus 2
Surface of revolution

Articles: * Implicit surface on Wikipedia * Implicit surfaces by Paul Bourke * Implicit surface a.k.a (signed) distance field: definition by Rodolphe Vaillant

Notable software: * K3DSurf


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 on Wikipedia * Inverse kinematics on Wikipedia * Forward kinematics on Wikipedia

Videos: * Coding Challenge #64.1: Forward Kinematics by Daniel Shiffman * Coding Challenge #64.2: Inverse Kinematics b Daniel Shiffman * Coding Challenge #64.3: Inverse Kinematics – Fixed Point by Daniel Shiffman * Coding Challenge #64.4: Inverse Kinematics – Multiple by Daniel Shiffman


Laplace transform



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, harmonographs, and more.

Equations:


Articles: * Lissajous curve on Wikipedia * Lissajous curve from MathCurve * Lissajous Curves from DataGenetics

Videos: * Coding Challenge #116: Lissajous Curve Table by Daniel Shiffman (Github repo with source code for p5.js and Processing) * #48: Basics of Lissajous Patterns on an Oscilloscope by w2aew


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 * Straight skeleton – similar to medial, except always is made up of straight line segments whereas medial axis may contain curves. * Scale Axis Transform – generalization of medial axis transform

Articles: * Medial axis on Wikipedia * “A transformation for extracting new descriptors of shape” by Henry Blum


Minimal surface


  • Soap experiments (see Frei Otto and Joseph Plateau’s experiments)
  • Mesh relaxation
  • CMC surface (same as minimal surface, or can be combined?)
  • Surface evolver – see Ken Brakke’s work. Is there an underlying algorithm that can be decoupled from his particular implementation?

Articles: * Minimal surface


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 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).

Related terms: * Nesting (process)

Articles: * Packing problems on Wikipedia * Random space filling of the plane by Paul Bourke * Optimal Packing from Data Genetics * Circle Packing on Wolfram MathWorld * Bin packing problem on Wikipedia * Sphere packing on Wikipedia * Close-packing of equal spheres on Wikipedia * Packing Problems – collection of papers by Ernesto Birgin and collaborators

Notable tools: * RhinoNest (Rhino) * DeepNest (Standalone) * SVGnest (Web app)

Videos: * Coding Challenge #50.1: Animated Circle Packing – Part 1 by Daniel Shiffman


Percolation theory


Articles: * Percolation theory on Wikipedia


Phyllotaxis

Related topics include the golden ratio, the golden angle, and the 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 – 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 family

Articles: * Phyllotaxis on Wikipedia * Chapter 4: Phyllotaxis from Algorithmic Botany book * Phyllotaxis on Wolfram MathWorld

Code projects: * ofxPhyllotaxis by Davide Prati (edap)

Videos: * Coding Challenge #30: Phyllotaxis by Daniel Shiffman


Platonic 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 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 on Wikipedia * Platonic Solids on Tutors.com

Videos: * 5 Platonic Solids by Numberphile


Saffman–Taylor instability

Related to the Hele-Shaw cell experiment.

Also known as viscous fingering.


Articless: * Saffman–Taylor instability on Wikipedia


Spherical harmonics


Articles: * Spherical harmonics on Wikipedia * Spherical Harmonics by Paul Bourke


Strange attractors


Notable attractors: * Clifford attractor * Duffing attractor * Hénon attractor * Lorenz attractor * Multiscroll attractor (a.k.a double-scroll attractor or Chua’s attractor) * Rössler attractor

Articles: * Strange attractor section on Wikipedia article for attractors


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
Parametric

Articles: * Superellipse on Wikipedia * Superellipse on Wolfram MathWorld * Supershapes (Superformula) by Paul Bourke

Videos: * Coding Challenge #23: 2D Supershapes by Daniel Shiffman (Github repo with Processing and p5.js code)


Screenshot from GLSL Supershapes by Softwave

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) 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 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

Where r is a radius and φ (phi) is an angle

3D equations

Where φ (latitude) varies between −π/2 and π/2 and θ (longitude) between −π and π.

Articles: * Superformula on Wikipedia * Supershapes / Superformula by Paul Bourke

Code projects: * SuperformulaSVG-for-web by Jason Webb (Javascript, p5.js) * SuperformulaSVG by Jason Webb (Processing) * Visualize: Superformula from FORM+CODE book * glsl-superformula by JC Leyba (Software) * supershape.js by Sebastian Sadowski (ahoiin)

Videos: * Coding Challenge #26: 3D Supershapes by Daniel Shiffman (Processing sketch on Github)


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 on Wikipedia * Traveling Salesman Problem from Google OR-Tools

Notable software: * StippleGen from Evil Mad Scientist Laboratories can calculate TSP paths.

 

Lab experiments

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 or cellular automata (see the Hodgepodge Machine specifically).

Is it possible to succinctly describe "recipe" for reliable BZ reaction in petri dish?

Articles: * Belousov–Zhabotinsky reaction on Wikipedia * Belousov-Zhabotinsky reaction on Scholarpedia * The Belousov-Zhabotinsky Reaction and The Hodgepodge Machine by Softology

Code projects: * Simulating the Belousov-Zhabotinsky reaction (Python) by Christian Hill

Videos: * Belousov-Zhabotinsky Reaction by nater06 * Recreating one of the weirdest reactions by NilesRed * Preparation of a Belousov–Zhabotinsky reaction for use in a Petri-dish Part 1 by Nigel Baldwin * Preparation of a Belousov–Zhabotinsky reaction for use in a Petri-dish Part 2 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 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 on Wikipedia

DIY projects: * Easy Chladni Plate by Aron Hoekstra * Building a Chladni Plate by Mario Cruz (MarioTheMaker) * How to sculpt sound into Chladni figures by Nicolas Barrial * 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 * PASCO

Videos: * Weekend Projects: Visualizing Sound with a Chladni Plate by Make * Singing plates – Standing Waves on Chladni plates by Diana Cowern (Physics Girl) * Chladni Figures – random couscous snaps into beautiful patterns by Steve Mould * Resonance Experiment! (Full Version – With Tones) by brusspup * Moving Particles with Vibration, Making the Chladni Plate by Mehdi Sadaghdar (ElectroBOOM)


Hele-Shaw cell experiment by Nervous System

Hele-Shaw cell

Related to Saffman-Taylor instability.

Apparatus for demonstrating and studying a pheonmenon known as viscous fingering (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]. 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 or differential growth.

Setup:

The Hele-Shaw cell typically consists of two plates, usually glass or plexiglass, separated by a very short distance (TODO: how short?). A viscous fluid such as glycerin is injected through a hole either in the center of one of the plates or between the plates from the side, followed by colored water. As the colored water is injected and pressure is built up, the glycerin partially resists it’s flow resulting in complex, wavy lines where the two liquids meet. For added effect, illuminate the cell by placing a light underneath, shining towards the viewer through the cell.



Articles: * Hele-Shaw flow on Wikipedia

Videos: * Hele-Shaw cell experiments by Nervous System * Hele Shaw Cell using ferrofluid and a magnet by manf1234 * Viscous Fingering in Multiport Hele Shaw Cell for Controlled Shaping of Fluids by Tanveer ul Islam and Prasanna S. Gandhi

Images: * Schlieren Imaging of 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 on Wikipedia * Schlieren imaging on Wikipedia * Schlieren photography on Wikipedia * Schielren Optics by Harvard Natural Sciences Lecture Demonstrations

DIY projects: * Schlieren Imaging: How to See Air Flow! by Bryan Rolfe * DIY Schlieren Flow Visualization by Jonathan Lansey (jlansey)

Videos: * Seeing the Invisible: SLOW MOTION Schlieren Imaging by Veritasium * Schlieren Imaging in Color! by Veritasium * How To: Build Your Own Schlieren Setup by JoshTheEngineer * Visualizing Ultrasound with Schlieren Optics Part I [Part II] [Part III] by Harvard Natural Sciences Lecture Demonstrations

 

Useful code patterns and techniques

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, 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, architecture, and city planning.

Characteristics of agent-based models relevant to biological modelling [1]: 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

Articles: * Agent-based model on Wikipedia * Multi-agent system on Wikipedia * Agent-based model in biology on Wikipedia * Emergence on Wikipedia * Swarm intelligence on Wikipedia


Boids

Related topics include agent-based modelling.

Well-known type of agent-based system 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

Additional rules can be implemented to simulate specific behaviors like obstacle avoidance, predator-prey interactions, bait balls, and more.

Articles: * Flocks, Herds, and Schools: A Distributed Behavioral Model – original 1987 paper by Craig Reynolds * Boids on Wikipedia * Chapter 6. Autonomous Agents from Nature of Code * Boids by Craig Reynolds

Videos: * Coding Challenge #124: Flocking Simulation by Daniel Shiffman (Github repo 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 on Wikipedia

Code projects: * csg.js (JavaScript) by Evan Wallace * CGAL 4.14- 3D Boolean Operations on Nef Polyhedra (C++)


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 and 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 (AABB) * Sort and sweep (a.k.a. sweep and prune) * Bounding volume hierarchy (BVH) * Narrow phase – class of algorithms that determine if two shapes are definately intersecting or not, and by how much. * Separating axis theorem (SAT) * Gilbert-Johnson-Keerthi (GJK) algorithm * Expanding Polytope Algorithm (EPA)

Articles: * Collision detection on Wikipedia * Video Game Physics Tutorial – Part II: Collision Detection for Solid Objects by Nilson Souto * Let’s talk about broad phase by Stanislav Pidhorskyi

Books: * Real-Time Collision Detection by Christer Ericson


Dithering

Creates the illusion of depth in an image using a limited color palette, most commonly by varying the spacing or sizes of solid, single-color dots or lines. Some techniques (like halftones) even 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 and pointillism!

Useful for realizing grayscale images with various digital fabrication equipment like laser cutters, pen plotters, CNC routers/mills, and more.

Types of dithering: * Threshold (a.k.a average) * 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 on Wikipedia

Code projects: * Coding Challenge #90: Floyd-Steinberg Dithering by Daniel Shiffman (Github repo with source code for p5.js and Processing) * Atkinson Dithering, Live in Processing by Windell Oskay of Evil Mad Scientist Laboratories * #dithering-algorithms on Github * Digital Halftoning by C. A. Bouman * Color Quantization and Dithering reference page for ImageMagick v6


Flow field

Related topics include 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 to model complex, dynamic movement caused by wind, fluid flow, electromagnetism, and more.

Vector fields are often populated using data generated with noise or image data. Curiously, flow fields have also been used in pathfinding.

Articles: * Vector field on Wikipedia * Flow Fields, Part I by Keith Peters * Flow Fields, Part II by Keith Peters

Code projects: * ofxVectorField (openFrameworks add-on) by Jeremy Rotzstain (mantissa)

Videos: * Coding Challenge #24: Perlin Noise Flow Field by Daniel Shiffman (Github repo with source code for p5.js and Processing)


Fluid simulation

Simulates the highly complex and dynamic nature of flows in fluid volumes using computationally-efficient implementations of the Navier-Stokes 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 (Re) – dimensionless quantity used to predict fluid flow patterns. Laminar (smooth) flow occurs at low Re, while turbulent flow occurs at high Re. * Navier-Stokes equations on Wikipedia * Lattice Boltzmann methods (LBM) on Wikipedia * 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 (PDF) by Dan Englesson, Joakim Kilby, and Joel Ek * Computational fluid dynamics (CFD) on Wikipedia * Fluid Simulation for Dummies by Mike Ash * Real-Time Fluid Dynamics for Games (PDF) by Jos Stam * Chapter 38. Fast Fluid Dynamics Simulation on the GPU from GPU Gems book

Books: * Fluid Simulation for Computer Graphics by Robert Bridson

Code projects: * Lily Pad (Processing) by Dr. Gabriel David Weymouth * MSAFluid by Memo Akten * ofxMSAFluid (openFrameworks) * p5-MSAFluid (Processing) * OpenFOAM * mantaflow * Fluidity

Notable tools: * FLIP Solver (Houdini) * FLIP Fluids (Blender) * Obi Fluids (Unity) * Butterfly (Grasshopper for Rhino) * RhinoCFD (Rhino) * RealFlow (Standalone, or via plugins for 3ds Max, Maya, and Cinema4D)

Videos: * Coding Challenge #132: Fluid Simulation by Daniel Shiffman (Github repo with source code for p5.js and Processing) * Why Laminar Flow is AWESOME – Smarter Every Day 208 by Smarter Every Day


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 on Wikipedia * Metaballs and Marching Squares by Jamie Wong

Code projects: * d3-contour – D3.js library

Videos: * Marching Squares for procedural cave generation in Unity by Sebastian Lague


Marching cubes

3D version of 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

add note on dual marching cubes

Algorithm [link]:

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

(Figure A) diagram of 15 possible polygon configurations based on vertex bit values

(Figure B) diagram of edge and vertex numbering

Key terms: * Isosurface – surface that represents points of a constant value within a volume of space

Articles: * Marching Cubes: A High-Resolution 3D Surface Construction Algorithm (PDF) – original paper by William Lorensen and Harvey Cline * Marching cubes on Wikipedia * Polygonising a scalar field by Paul Bourke * Voxel to Mesh Conversion: Marching Cube Algorithm by Smile Sikand

Videos: * Marching Cubes Animation by Algorithms Visualized


Metaballs

Related to implicit surfaces, marching squares (2D) and marching cubes (3D)

Often confused with marching cubes, this is more of a mathmematical 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 that define blobby shapes as pure mathematical formulas rather than explicit polygons and vertices.

They can be visualized using the marching squares (2D) or marching cubes (3D) rendering algorithms. Can be used for naive fluid simulations by applying physics to the metaball center points as if they were particles. They can also be helpful in modelling soft bodies by adding elastic constraints between the center points.

A typical function chosen for metaballs is:

Where is the center of the metaball.

Articles: * Metaballs on Wikipedia * Metaballs (also known as: Blobs) by Ryan Geiss * Exploring Metaballs and Isosurfaces in 2D by Stephen Whitmore

Videos: * Coding Challenge #28: Metaballs by Daniel Shiffman (Github repo with source code for p5.js and Processing)


Noise

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.

  • Gradient noise – created by interpolation of a lattice of pseudorandom gradients
  • Perlin noise ⭐ – extremely influential type of gradient noise developed by Ken Perlin in 1983
  • Simplex noise – method for constructing an n-dimensional noise function comparable to Perlin noise
  • Simuation noise – function that creates a divergence-free field
  • Value noise – created by interpolation of a lattice of pseudorandom values; differs from gradient noise
  • Wavelet noise – alternative to Perlin noise which reduces problems of aliasing and detail loss
  • Worley noise – noise function introduced by Steven Worley in 1996

Articles: * Noise chapter in The Book of Shaders by Patricio Gonzalez Vivo & Jen Lowe

Videos: * Coding Challenge #11: 3D Terrain Generation with Perlin Noise in Processing by Daniel Shiffman (Github repo with source code for p5.js and Processing) * Coding Challenge #136.1: Polar Perlin Noise Loops by Daniel Shiffman (Github repo [2] with source code for p5.js and Processing)

add note on curl noise

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, 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 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 on Wikipedia * Intro to particle systems lesson on Khan Academy * The physics of particle systems * Chapter 4. Particle Systems from Nature of Code

Notable software: * Unity’s VFX Graph * Blender’s Particle System


Physics engine

Related topics include collision detection and particle systems

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 on Wikipedia * 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 by Randy Gaul

Notable open-source libraries: * Box2D (C++) * LiquidFun (C++) – adds rigid-body and fluid dynamics on top of Box2D * box2d.js (JavaScript via Emscripten) * Planck.js (JavaScript, manually ported) * Bullet (C++) * ammo.js (direct JavaScript port using Emscripten) * Matter.js (JavaScript) * dyn4j (Java) * cannon.js (JavaScript) * p2.js (JavaScript) * ReactPhysics3D (C++) * Chrono (C++) * Open Dynamics Engine (ODE) (C++)

Commercial libraries: * PhysX by Nvidia. Integrated into both Unity and Unreal. Technically open-source now, but oriented more towards commercial/industry applications. * Havok

If you’re looking to do physical-based simulations, also take a look at game development and VFX environments like Unity, Unreal, and Houdini for their built-in physics engines.


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) are beginning to make this technique available in real-time applications.

Articles: * Ray tracing (graphics) on Wikipedia

Code projects: * appleseed * Intel Embree * Intel OSPRay * POV-Ray * Mitsuba


Recursion

See 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.

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 on Wikipedia * Recursion (computer science) on Wikipedia * 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 * Fragment * Geometry * Tessellation * Vertex

Key concepts: * FBO (framebuffer object) * GPGPU (general-purpose computing on GPUs) – 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) – 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 * Textures * Uniform – a type qualifier 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 – a type qualifier indicating a variable that can change within the vertex shader, then passed to the fragment shader as a read-only value.

Languages: * Cg – shading language developed by Nvidia in close collaboration with Microsoft * CUDA – parallel computing API that makes it easier to use GPGPU for complicated tasks * GLSL (OpenGL Shading Language) – shading language used by OpenGL * HLSL (High-Level Shading Language) – shading language used by DirectX

Articles: * The Book of Shaders by Patricio Gonzalez Vivo and Jen Lowe * Shaders by Learn OpenGL * GLSL Shaders on MDN web docs * Shaders (Processing) tutorial by Andres Colubi * Introducing Shaders (openFrameworks) by Lucasz Karluk, Joshua Noble, Jordi Puig * Shader modules (Vulkan)

Code tools: * Bonzomatic * glslsandbox * RenderMonkey * Shadertoy

Videos: * Shader Coding seminar at Revision 2019


Signed distance function (SDFs)

Related to implicit surfaces.

A function that returns the distance between a point in space to a mathematically/algorithmically defined surface (called an implicit surface). This allows algorithms like raymarching and 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 allows the code to be ran entirely on the GPU.

Articles: * Signed distance function on Wikipedia * Distance functions (GLSL) * Ray Marching and Signed Distance Functions by Jamie Wong

Notable open-source libraries: * hg_sdf (GLSL)

Videos: * How to Create Content with Signed Distance Functions by Johann Korndörfer


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.

Common types: * Quadtree – each node has exactly four children * Octree – each node has exactly eight children * k-d tree * R-tree

Related topics: * k-nearest neighbhor (knn) search * Spatial database on Wikipedia * Binary space partitioning on Wikipedia

Articles: * Spatial index section on Wikipedia article for Spatial database

Videos: * Coding Challenge #98: Part 1, Part 2, Part 3 by Daniel Shiffman


Wave Function Collapse (WFC)

Method of procedurally generating textures and tilemaps that are similar to a single source image using ideas from quantum mechanics.

add description of algorithm

Articles: * Original WaveFunctionCollapse Github repo by Maxim Gumin (mxgmn) * Generating Worlds With Wave Function Collapse by Joseph Parker * Doodle Insights #19: Logic Data Generation (feat. WFC made easy) by Rémy Devaux (TRASEVOL_DOG)

Code projects: * ofxWFC3D (openFrameworks add-on) by Nuño de la Serna

Videos: * WaveFunctionCollapse Supercharged with PDG for Level Generation talk by Paul Ambrosiussen at HOUDINI HIVE GAMEDEV

 

Books, publications, and talks

Books

Publications

Talks


 Entagma's Patreon series

 

Software

Tools

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).
  • Aprrentice – free for non-commercial users with watermarked renders
  • Indie – $269/yr for no watermarks for commercial <$100k annual profit
  • Thousands for commercial users, with complex pricing model
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
  • Grasshopper – extremely popular graphical node-based algorithm editor tightly integrated with Rhino’s 3D modeling tools. Highly recommended for digital morphogenesis work. Was a third-party plugin for many years, but is now a part of Rhino 6+.
  • Lunchbox – very powerful collection of utilities for generative geometry, math, data manipulation, and even machine learning.
  • Kangaroo – live physics engine for interactive simulation, form-finding, optimization and constraint solving.
  • Rhino 6 for Win – $995
  • Rhino 5 for Mac – $695
  • $195 for students (both platforms)
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
  • Personal – free for hobbyists
  • Plus – $35/mo or ~$25/mo for prepaid year
  • Pro – $125/mo
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).
  • Free for non-commercial projects
  • Educational – $300 for schools, educators, schools only
  • Commercial – $600
  • Pro – $2200
Cinema 4D Four versions ranging from $995-$3695

Languages and frameworks

Uncategorized