Curv: A Language for making Art using Mathematics

twistor shreks_donut

What is Curv?

Curv is an open source 3D solid modelling language, oriented towards 3D printing, procedurally generated art, and mathematical visualization.

It's easy to use for beginners. It's incredibly powerful for experts. And it's fast: all rendering is performed by the GPU.

Curv is also a uniquely expressive file format for the exchange of 2D and 3D procedurally generated graphics.

Thesis

Ease of use:
For ease of use, the best choice is Constructive Solid Geometry (CSG) embedded in a simple, pure functional language.
Rendering Speed:
To quickly render a wide range of CSG primitives, the best choice is to render on a GPU, and to represent shapes using Signed Distance Fields (SDF) and Function Representation (F-Rep).
Expressive Power:
SDF/F-Rep is the best choice for CSG: A wider range of CSG primitives are available in Open Source than for competing representations.

Thesis (2)

To boost expressiveness, the Curv language permits experts to define new CSG primitives using F-Rep. (Therefore, Curv functions must be compilable into GPU code.)

F-Rep is the most expressive representation for controlling a 3D printer. It can describe 3D-printable objects that can't be modeled by competing representations.

Constructive Solid Geometry

In a Constructive Solid Geometry (CSG) system, there is a set of primitive shapes, and operations for constructing new shapes by transforming and combining simpler shapes.

The operations normally include boolean operations like union, intersection and difference, and affine transformations like translate, scale and rotate.

Constructive Solid Geometry (2)

Curv uses CSG as its high level geometry interface, and provides a rich set of predefined shapes and operations. Both 2D and 3D shapes are supported.

Curv is a pure functional language in which shapes are first class values, and CSG operations are functions that map shapes onto shapes.

Constructive Solid Geometry (3)

twistor:

torus (2,1)
  >> texture (i_radial 1, sRGB.hue)
  >> rotate {angle:tau/4, axis:Y_axis}
  >> twist (tau/3) >> lipschitz 2.2

Constructive Solid Geometry (4)

shreks_donut:

smooth .1 .intersection (
  torus (tau*4, tau*2),
  gyroid >> shell .2 >> lipschitz 2 >> bend (tau*12),
) >> colour (sRGB.HSV (1/3, 1, .5))

Function Representation

In Curv, Geometric shapes use Function Representation (F-Rep).

A shape contains functions that map every point (x,y,z) in 3D space onto the shape's properties, which may include spatial extent, colour, material.

Function Representation (2)

F-Rep is the most expressive geometric representation.

Instead of approximating a shape using many copies of a single geometric primitive (like polygons, spline curves, or pixels), or a fixed number of geometric primitives (vector representations), F-Rep represents shapes using mathematical equations.

This means that exact representations of a vast number of geometric primitives are available.

F-Rep is compact and resolution independent. Shapes can be infinitely detailed, or infinitely large.

Function Representation (3)

Curv provides a low level API for defining CSG primitives using F-Rep. Using this API, the entire CSG geometry API is defined using Curv code.

A circle primitive can be defined like this:

circle r = make_shape {
  dist(x,y,z,t) = sqrt(x^2 + y^2) - r,
  bbox = [[-r,-r,0], [r,r,0]],  // axis aligned bounding box
  is_2d = true,
}

Pure Functional Programming

Curv is a pure functional language, with both shapes and functions as first class values. Why?

Pure Functional Programming (2)

Curv can be considered a file format for representing arbitrary geometric shapes and distributing them across the internet.

One requirement for such a file format is security: when you open a shape file, you don't want the shape file to encrypt all of your files and display a ransom message.

Curv is not a general purpose programming language. It doesn't have side effects, it can only compute values. So it meets this requirement.

Pure Functional Programming (3)

Unique contribution of Curv: pure functional + CSG + F-Rep in one language.

Secret agenda: Pure functional programming for beginners, and for people who can't wrap their head around Haskell.

Competing Shape Representations

Explicit Modelling Implicit Modelling
Directly generate boundary points Answer questions about particular points

parametric equation (unit circle):

(x,y) = (cos t, sin t)

implicit equation (unit circle):

x^2 + y^2 - 1 = 0
Boundary Representations Volumetric Representations
parametric splines function representation
triangle mesh pixels (2D), voxels (3D)

Competing Shape Representations (2)

These two classes have different strengths and weaknesses. Certain operations that are cheap for one class are expensive for the other class (and vice versa).

Conversions between the two classes are non-trivial:

Competing Shape Representations (3)

Curv chooses F-Rep over B-Rep, but an engineering tradeoff is involved.

If you only know B-Rep procedural modelling, then learning F-Rep requires you to think different if you want to write efficient programs.

F-Rep > Meshes

Instead of triangular meshes (like OpenSCAD), Curv represents shapes as pure functions (Function Representation or F-Rep). Why?

F-Rep > Meshes (Expressiveness)

F-Rep is a more powerful and expressive representation than meshes.

Shapes can be infinitely detailed, infinitely large.

Any shape that can be described using mathematics can be represented exactly.

F-Rep > Meshes (Exactness)

Meshes are approximations, F-Rep is exact.

As you apply a chain of successive geometry operations to a mesh, approximation errors can pile up.

F-Rep > Meshes (Memory)

With a mesh, simulating a curved surface with high fidelity requires lots of triangles (and memory). There is a tradeoff between accuracy of representation and memory/processing costs.

F-Rep can represent curved surfaces exactly, at low cost.

F-Rep > Meshes (Speed)

The cost of mesh operations goes up, often non-linearly, with the number of triangles.

For example, this is true for union and intersection.

F-Rep can implement most common geometric operations, like union and intersection, in small constant time and space.

F-Rep > Meshes (Fractals)

With a mesh, complex shapes with a lot of fine detail require lots of triangles and are very expensive.

Examples are fractals, digital fabrics, metamaterials. OpenSCAD encounters these limits quite early. Many complex models that are 3D printable are out of reach.

F-Rep can represent infinite complexity for free.

F-Rep > Meshes (3D Printing)

Unlike subtractive manufacturing (eg, CNC milling), or moulding, where you only control the boundary of an object,

3D printing is an inherently volumetric manufacturing technology. 3D printers directly control the material placed at each voxel in a 3D volume.

There is a slogan for this: In 3D printing, complexity comes for free.

F-Rep > Meshes (3D Printing)

F-Rep is a volumetric representation, where functions map every point (x,y,z) in 3D space onto the properties of a shape. These properties include spatial extent, colour, material.

F-Rep is a better way to program a 3D printer.

F-Rep > Meshes (More CSG Operations)

Meshes: union and intersection are very hard to program, require an expert implementation like CGAL or Carve.

F-Rep: union and intersection are trivial.

Many more geometric operations available in open source, much easier to program.

The entire Curv geometry library can be written in Curv. Easier for users to define & distribute new CSG ops.

F-Rep > Meshes (GPU)

F-Rep is well suited to being directly rendered by a GPU.

Signed Distance Fields

Curv uses a specific type of F-Rep called Signed Distance Fields for representing the spatial extent of a shape.

A signed distance field is a function which maps each point in space onto the minimum distance from that point to the boundary of the shape.

An SDF is zero for points on the boundary of the shape, negative for points inside the shape, and positive for points outside of the shape.

Signed Distance Fields (2)

sdf1 sdf2

sdf3a sdf3b

Signed Distance Fields (3)

An SDF is continuous, and differentiable almost everywhere.

The singular points that occur inside a shape are called the (Topological) Skeleton or Medial Axis.

Isocurves and Isosurfaces

For a 2D SDF, the isocurve at C is the curve that comprises all points with the distance value C.

For a 3D SDF, the isosurface at C is the surface that comprises all points with the distance value C.

Isocurves and Isosurfaces (2)

For example, here's the SDF for a rectangle. Some isocurves are visible as contour lines:

images/rect_sdf.png

The isocurve at 0 for this SDF is just the boundary of the rectangle.

Isocurves and Isosurfaces (3)

images/rect_sdf.png

The isocurve at 1 is:

Isocurves and Isosurfaces (4)

images/rect_sdf.png

Similarly, isocurves or isosurfaces at negative values correspond to negative offsets, Minkowski difference, or erosion from Mathematical Morphology.

Exact, Approximate and Mitred SDFs

In an Exact SDF, the distance field stores the exact distance from each point to the closest boundary.

(This is also called a Euclidean SDF, since we are using the Euclidean distance metric, and some researchers use alternative metric spaces to construct SDFs.)

We've been discussing Exact SDFs up to this point.

Exact, Approximate and Mitred SDFs (2)

It turns out that it is sometimes difficult or expensive to construct Exact SDFs.

So, a distance function is permitted to underestimate the distance to the closest boundary, and the result is an Approximate SDF (aka a Distance Estimator (DE), or sometimes a Signed Distance Bound).

Exact, Approximate and Mitred SDFs (2)

The simplest and cheapest implementation of a rectangle has an Approximate SDF that looks like this:

images/rect_mitred_sdf.png

The positive isocurves of this SDF are also rectangles: they correspond to the "Mitred Offset" operation from CAD.

So I call this a Mitred SDF.

Exact, Approximate and Mitred SDFs (3)

According to John C. Hart, author of the original academic papers on SDFs,

the only restriction is that an SDF cannot overestimate the distance from each point to the closest boundary.

In math terms, an SDF must be Lipschitz Continuous, with a Lipschitz constant of 1.

It's a continuous function which is limited in how fast it can change.

For every pair of points in an SDF, the absolute value of the slope of the line connecting the points is not greater than 1.

Exact, Approximate and Mitred SDFs (4)

An approximate SDF does not have all of the nice properties of an exact SDF.

Exact, Approximate and Mitred SDFs (5)

A possible future direction is that shapes contain metadata which describes the properties of their SDF.

Shortcuts which rely on certain properties can be enabled if the property is present.

SDF History

Early F-Rep systems used a simple representation:

A geometry function f(p) indicates whether the point p is inside, on the boundary, or outside of the shape, by returning 3 different values (eg, a negative, zero or positive number).

This made it easy to write geometry functions.

Rendering was very expensive: It was done by blind sampling of points in a 3D grid (lots of function evaluations).

It wasn't accurate: if a small detail fell between grid points, it was lost.

SDF History (2)

This led to a period of experimentation, searching for an F-Rep with fast, accurate rendering.

SDF won over the competition because it is the simplest such F-Rep that works.

It's relatively simple to define, relatively cheap to compute, and doesn't require the distance field to have a derivative everywhere.

SDF Techniques

SDFs contain more information than inside/boundary/outside. Used for rendering:

SDF Techniques (2)

The SDF Community

Although SDFs are sometimes tricky to write, there is an army of people in the open source community who are designing new SDFs.

Curv benefits by using this popular F-Rep representation and sharing SDFs with the community, which includes:

SDF Applications

The Circle

One way to construct the SDF for a shape is to start with the shape's implicit equation, then algebraically transform it into a function with the same roots, but with a Lipschitz constant of 1.

The Circle (2)

Implicit equation for a circle of radius r:

x^2 + y^2 = r^2

The Circle (2)

If we rearrange this to:

x^2 + y^2 - r^2 = 0

then we have an implicit function that is zero on the boundary of the circle, negative inside the circle, and positive outside the circle.

Not an SDF: function value at p is the square of the distance from p to the origin, not the Euclidean distance.

The Circle (3)

We fix this by further transforming the equation:

sqrt(x^2 + y^2) = r
sqrt(x^2 + y^2) - r = 0

and now we have a proper Euclidean SDF.

The Circle (4)

A Curv circle implementation:

circle r = make_shape {
  dist(x,y,z,t) = sqrt(x^2 - y^2) - r,
  ...
}

The Circle (5)

Moral: Converting an implicit equation to an SDF requires care.

Typically, you will plot the candidate distance field, look for places where the gradient isn't 1, and construct an inverse transformation that maps 0 to 0 (leaving the boundary alone), but modifies the field at other points so that the gradient becomes 1.

Boolean Operations

There are 3 primitive boolean operations on SDFs: union, intersection, and complement.

(Others, like difference and symmetric_difference, can be defined in terms of the primitives.)

These operations are closed over approximate SDFs. However, they map exact SDFs to approximate SDFs.

Boolean Operations (Union)

The union of two shapes is the minimum of their distance fields:

union(s1,s2) = make_shape {
  dist p = min(s1.dist p, s2.dist p),
  ...
}
images/union1.png

Boolean Operations (Union)

images/union1.png

This SDF is exact for any points outside of the shape, or at the boundary.

But the SDF is approximate inside the shape, in this case within the region where the circle and square intersect.

Boolean Operations (Intersection)

Intersection is computed using max.

Boolean Operations (Complement)

The complement operation negates the distance field (and converts finite shapes into infinite ones).

The Square

In Curv, infinitely large shapes commonly have a simpler and cheaper representation than finite shapes.

A lot of finite shapes are constructed by intersecting two or more infinite shapes.

Most any shape with vertexes or straight line edges is probably built by intersection.

The Square (2)

Let's construct a square of size 2*r.

We begin with an infinite half-plane, parallel to the Y axis, which extends along the X axis from -infinity to +r:

dist(x,y) = x - r square1

The Square (3)

Now we will reflect the above half-plane through the Y axis, using the abs operator.

The result is an infinite ribbon that runs along the Y axis, bounded on the X axis between -r and +r:

dist(x,y) = abs(x) - r square2

The Square (4)

Now we will construct a similar ribbon that runs along the X axis:

dist2(x,y) = abs(y) - r square3

The Square (5)

Now we intersect these two ribbons, using the max operator:

dist(x,y) = max(abs(x) - r, abs(y) - r) square4

The Square (6)

Curv is an array language, in which all arithmetic operations are generalized to work on arrays.

This is important for GPU compilation, since vectorized operations run faster.

So we will "vectorize" the above equation:

dist(x,y) = max(abs(x,y) - r)

The Square (7)

Here's a square operator that constructs a square of size d:

square d = make_shape {
  dist(x,y,z,t) = max(abs(x,y) - d/2),
  ...
}

Transformations

A transformation warps or transforms a shape in some way, by warping or transforming the coordinate system in which it is embedded.

The affine transformations are the most familiar (translate, rotate, scale, etc)

But any coordinate transformation is possible (twist, taper, bend).

Transformations (2)

Translation:

translate (dx,dy,dz) S = make_shape {
  dist(x,y,z,t) = S.dist(x-dx,y-dy,z-dz,t),
  ...
}

To apply an affine transformation to a shape S, the transformation's distance function dist(p) performs the inverse of the transformation to the argument p before passing it to S.dist.

Transformations (3)

For distance-preserving or rigid transformations (translate, rotate and reflect), that's all you need.

Otherwise, for non-rigid transformations (like scale, shear or twist), the resulting distance field will be messed up, and needs to be fixed.

Transformations (4)

For isotropic scaling, fixing the distance field is easy:

isoscale k S = make_shape {
  dist(x,y,z,t) = S.dist(x/k, y/k, z/k, t) * k,
  ...
}

Transformations (5)

For anisotropic scaling, fixing the distance field requires an approximation:

scale(kx, ky, kz) S = make_shape {
  dist(x,y,z,t) = S.dist(x/kx, y/ky, z/kz, t) * min(kx, ky, kz),
  ...
}

Transformations (6)

Fixing the distance field can sometimes be tricky.

If you can put an upper bound D on the derivative of the broken distance field, then divide the distance field by D and that's probably good enough.

If there's no upper bound, you need a more complicated fix.

Symmetry and Space Folding

The union operator is slow.

The cost of a union is equal to slightly more than the sum of the costs of the argument shapes. So if you have a shape that takes 1ms to render, and you union together 1000 copies of this shape, well now it takes 1s to render.

Fortunately, Curv has repetition operators which union together an arbitrary number of copies of a shape together, or even an infinite number of copies, in constant time and space.

Symmetry and Space Folding (2)

Each repetition operator corresponds to a different mathematical symmetry. The most basic ones are:

Symmetry and Space Folding (3)

Here's an example of translational repetition:

sphere 1 >> repeat_xy (1,1)
images/sphere_repeat.png

Symmetry and Space Folding (4)

The repeat_xy operator is a coordinate transformation that uses the modulus operator to map coordinates in each cell onto the cell that is centered at the origin.

This has been called "space folding":

repeat_xy r shape = make_shape {
  dist(x,y,z,t) : shape.dist(
              mod(x + r[X], 2*r[X]) - r[X],
              mod(y + r[Y], 2*r[Y]) - r[Y],
              z, t),
  ...
}

Symmetry and Space Folding (5)

The use of symmetry to encode repetition is a key feature of Curv programming. This allows you to generate huge amounts of complexity very cheaply.

Time and Animation

In Curv, time is the fourth dimension. Time is an extra parameter to distance functions and colour field functions. An animation is a shape or colour field that varies in time.

Time is represented by a floating point number, measured in units of seconds, like in ShaderToy. The zero point is arbitrary, and is not tied to clock time. Eg, for a movie, the zero point is the beginning of the movie.

Animation is always "turned on". Individual shapes and colour fields can be animated, in a modular way, without complicating their ability to be included in larger assemblies. Like putting an animated GIF into a web page.

Time and Animation (2)

Time is relative. Since time is a coordinate, it can be transformed. You can apply temporal transformations to speed up or slow down the passage of time within a shape, loop over a specified time range, concatenate a sequence of fixed length animations, etc.

You can define transformations that mix up time and space:

Time and Animation (3)

Since time is a coordinate, animated 2D shapes are actually static objects in 3D space-time, and animated 3D shapes are static objects in 4D space-time.

I intend to include time in the bounding box, so we can represent fixed duration animations with a start and end time.

I considered making time a global variable, like in OpenSCAD or Newtonian physics, but this design is more awesome.

Time and Animation (4)

A future goal is to import and export animated GIFs and video files.

Morphing

Morphing from one shape to another is easy: linear interpolation between two distance fields.

images/morph.png

Blending

Blends smoothly join nearby objects. Here are two circles, combined using different blending factors:

images/blend.png

Blending (2)

One application is filleting:

smooth .3 .union (cube 1, cylinder(.5,2))
images/fillet.png

Blending (3)

Another application is "Skeleton Based Implicit Modelling", as illustrated by this image from the "Implicit Seafood" web site:

images/seahorse.gif

Generalized Blends

Blending operators are like generalized unions, but the same code (which I call a "blending kernel") can also be used to define generalized intersections.

A blended union takes two shapes, plus a "blending kernel", adding a "fillet" to interior corners created by the union.

A blended intersction takes two shapes plus a blending kernel, rounding away material from exterior corners created by the intersection.

There is also blended difference.

Generalized Blends (2)

Here are some blending kernels from MERCURY.sexy, a demoscene group:

Round:
uRound iRound

Generalized Blends (3)

Chamfer:
uChamfer iChamfer

Generalized Blends (4)

Stairs:
uStairs iStairs

Generalized Blends (5)

Columns:
uColumns iColumns

As you see, you can program a wide range of "decorative moulding" patterns.

Fractals

SDFs and the Sphere Tracing algorithm were first described by inventor John C Hart in 1989 as an efficient algorithm for ray tracing (and thus visualizing) 3D fractals. Today it is still the best technique.

For large or deeply iterated 3D fractals, SDFs still win over other representations like triangle meshes or voxels: they require too much memory, and performing CSG operations like union or intersection on these bulky representations is too time consuming.

For the 3D fractal art community, SDFs are the technology of choice, being the basis for popular tools like MandelBulber and MandelBulb3D.

deep zoom into a MandelBox fractal (MandelBulb3D)

images/holy_box_fractal.jpg

Fractals (3)

Because Curv uses the same internal representation (SDFs), the same model should be portable to Curv.

https://www.youtube.com/watch?v=OW5RnrlTeow

Fractal Noise

A noise function maps each point in 2D or 3D space onto a pseudo-random noise value in the range [0...1].

Fractal noise is a popular noise function, good for simulating natural phenomena like smoke, flames, clouds, mountains, and solid textures like marble or wood.

Fractal Noise (2)

Here's a 3D solid texture I hacked together in Curv using fractal noise:

images/smoke3.png

Fractal Noise (3)

Fractal Noise (4)

Fractal Noise (5)

Fractal Noise (6)

Many more noise functions have been invented.

Sphere Tracing

Sphere Tracing (sometimes called "ray marching") is the variant of ray tracing used to render SDFs on a graphics display.

It's efficient enough to support real time animation of an SDF using a GPU.

Sphere Tracing and the SDF representation were invented together, by John C Hart, to solve the problem of fast, flexible, accurate ray tracing for Function Representation.

Sphere Tracing (2)

  1. Construct a single SDF representing the entire scene, eg by unioning together multiple components.
  2. For each pixel on the viewport, cast a ray of sight into the scene. Using a GPU, multiple rays are cast in parallel.
  3. The Sphere Tracing algorithm is used to advance the ray through the SDF until the ray hits a surface boundary. The SDF is sampled at the initial point, giving a value D. This is a distance estimate: the surface is at least D units away, maybe more. Advance the ray by D units, then iterate. Once D is sufficiently close to zero, we have reached the surface.

Sphere Tracing (3)

images/sphere_tracing.jpg

Sphere Tracing (4)

Once the ray reaches the surface, we colour & light the pixel.

Hierarchical SDFs

Naive: cost (N-ary union) = sum of the costs of the N arguments. Too expensive for large N.

Smart: partition space into disjoint subspaces. Maybe use multiple levels or a tree structure. During SDF evaluation, first determine what subspace you are in (eg by walking the tree), then evaluate the SDF for that subspace.

Can be done manually, using F-Rep API, but nicer to do it automatically. Eg,

Dreams by Media Molecule https://www.youtube.com/watch?v=4j8Wp-sx5K0

Shape Values in Curv

In Curv, a shape value may be 2D, 3D, or both.

The dimensionality is used to choose whether the 2D or 3D viewer is used, and to determine if the shape is eligible for export to various graphic file formats.

There is a single distance function used by both the 2D and 3D cases.

Shape Values in Curv (2)

A shape value is represented by a record, with fields:

Shape Values in Curv (3)

In the future, I'd like to support multiple shape subclasses, with specialized CSG operations that work only on shape subtypes.

For example, I'd like to implement the Conway polyhedron operators (which transform one polyhedron into another). Polyhedrons will contain vertex/edge/face information.

Compiling Curv to GPU Code

The Shape Compiler translates a shape to GPU code for rendering that shape.

The shape's distance and colour functions are compiled into a fragment shader or compute kernel.

GPU compute kernels are written in a primitive subset of C which lacks recursive functions and memory allocation, and has limited support for pointers and global variables. If I target WebGL, there is only limited support for iteration.

Compiling Curv to GPU Code (2)

Here's how GPU code generation works:

Compiling Curv to GPU Code (3)

Compiling Curv to GPU Code (4)

As I extend the F-Rep API to make Curv faster and more powerful, the GL subset of Curv is growing to embed an increasingly larger subset of the GLSL shader language.