## Expand description

Fidget is a library of infrastructure and algorithms for function evaluation, with an emphasis on complex closed-form implicit surfaces.

An **implicit surface** is a function `f(x, y, z)`

, where `x`

, `y`

, and `z`

represent a position in 3D space. By convention, if `f(x, y, z) < 0`

, then
that position is *inside* the shape; if it’s `> 0`

, then that position is
*outside* the shape; otherwise, it’s on the boundary of the shape.

A **closed-form** implicit surface means that the function is given as a
fixed expression built from closed-form operations (addition, subtraction,
etc), with no mutable state. This is in contrast to
ShaderToy-style implicit surface functions,
which often include mutable state and make control-flow decisions at
runtime.

Finally, **complex** means that that the library scales to expressions with
thousands of clauses.

Details on overall project status are in the project’s README; the rest of this page is a quick tour through the library APIs.

## §Shape construction

A “shape” is a closed-form function of `(x, y, z)`

with a single output.
For example, a circle of radius `1`

could be expressed as
`sqrt(x*x + y*y) - 1`

.

Shapes are constructed within a
`fidget::context::Context`

. A context serves as
an arena-style allocator, doing local deduplication and other simple
optimizations (e.g. constant folding).

Shapes can be constructed manually, using functions on a context:

```
use fidget::context::Context;
let mut ctx = Context::new();
let x = ctx.x();
let y = ctx.y();
let sum = ctx.add(x, y)?;
```

This is efficient, but is awkward to write. It’s also possible to construct
shapes without a `Context`

using the `Tree`

type,
then import the tree into a context:

```
use fidget::context::{Context, Tree};
let t = Tree::x() + Tree::y();
let mut ctx = Context::new();
let sum = ctx.import(&t);
```

As a third alternative, Fidget includes bindings to Rhai,
a simple Rust-native scripting language, in the `fidget::rhai`

namespace. These bindings allow shapes to be constructed from
a script, adding flexibility:

```
let t = fidget::rhai::eval("x + y")?;
let mut ctx = Context::new();
let sum = ctx.import(&t);
```

## §Evaluation

The main operation performed on an implicit surface is **evaluation**, i.e.
passing it some position `(x, y, z)`

and getting back a result. This will
be done *a lot*, so it has to be fast.

Evaluation is deliberately agnostic to the specific details of how we go
from position to results. This abstraction is represented by the
`Function`

trait, which defines how to make both
**evaluators** and **tapes**.

An **evaluator** is an object which performs evaluation of some kind (point,
array, gradient, interval). It carries no persistent data, and would
typically be constructed on a per-thread basis.

A **tape** contains instructions for an evaluator.

At the moment, Fidget implements two kinds of functions:

`fidget::vm::VmFunction`

evaluates a list of opcodes using an interpreter. This is slower, but can run in more situations (e.g. in WebAssembly).`fidget::jit::JitFunction`

performs fast evaluation by compiling expressions down to native code.

The `Function`

trait requires four different kinds
of evaluation:

- Single-point evaluation
- Interval evaluation
- Evaluation on an array of points, returning
`f32`

values - Evaluation on an array of points, returning partial derivatives with respect to input variables

These evaluation flavors are used in rendering:

- Interval evaluation can conservatively prove large regions of space to be empty or full, at which point they don’t need to be considered further.
- Array-of-points evaluation speeds up calculating occupancy (inside / outside) when given a set of voxels, because dispatch overhead is amortized over many points.
- At the surface of the model, partial derivatives represent normals and can be used for shading.

## §Functions and shapes

The `Function`

trait supports arbitrary numbers of
variables; when using it for implicit surfaces, it’s common to wrap it in a
`Shape`

, which binds `(x, y, z)`

axes to specific
variables.

Here’s a simple example of multi-point evaluation, using a `VmShape`

to
evaluate the function `X + Y`

at four sample locations:

```
use fidget::{
context::Tree,
shape::{Shape, EzShape},
vm::VmShape
};
let tree = Tree::x() + Tree::y();
let shape = VmShape::from(tree);
let mut eval = VmShape::new_float_slice_eval();
let tape = shape.ez_float_slice_tape();
let out = eval.eval(
&tape,
&[0.0, 1.0, 2.0, 3.0], // X
&[2.0, 3.0, 4.0, 5.0], // Y
&[0.0, 0.0, 0.0, 0.0], // Z
)?;
assert_eq!(out, &[2.0, 4.0, 6.0, 8.0]);
```

## §Shape simplification

Interval evaluation serves two purposes. As we already mentioned, it can be
used to prove large regions empty or filled, which lets us do less work when
rendering. In addition, it can discover **sections of the tape** that are
always inactive in a particular spatial region.

Consider evaluating `f(x, y, z) = max(x, y)`

with `x = [0, 1]`

and
`y = [2, 3]`

:

```
use fidget::{
context::Tree,
shape::EzShape,
vm::VmShape
};
let tree = Tree::x().min(Tree::y());
let shape = VmShape::from(tree);
let mut interval_eval = VmShape::new_interval_eval();
let tape = shape.ez_interval_tape();
let (out, trace) = interval_eval.eval(
&tape,
[0.0, 1.0], // X
[2.0, 3.0], // Y
[0.0, 0.0], // Z
)?;
assert_eq!(out, [0.0, 1.0].into());
```

In the evaluation region `x = [0, 1]; y = [2, 3]`

, `x`

is **strictly less
than** `y`

in the `min(x, y)`

clause. This means that we can simplify the
tape from `min(x, y) → x`

.

Interval evaluation is a kind of
tracing evaluation, which returns a tuple
of `(value, trace)`

. The trace can be used to simplify the original shape:

```
assert_eq!(shape.size(), 4); // min, X, Y, output
// (same code as above)
let new_shape = shape.ez_simplify(trace.unwrap())?;
assert_eq!(new_shape.size(), 2); // just the X term, then the output
```

Remember that this simplified tape is only valid for points (or intervals)
within the interval region `x = [0, 1]; y = [2, 3]`

. It’s up to you to make
sure this is upheld!

## §Rasterization

Fidget implements both 2D and 3D rasterization of implicit surfaces,
implemented in the `fidget::render`

module.

Here’s a quick example:

```
use fidget::{
context::{Tree, Context},
render::{BitRenderMode, RenderConfig},
vm::VmShape,
};
let x = Tree::x();
let y = Tree::y();
let tree = (x.square() + y.square()).sqrt() - 1.0;
let cfg = RenderConfig::<2> {
image_size: 32,
..RenderConfig::default()
};
let shape = VmShape::from(tree);
let out = cfg.run::<_, BitRenderMode>(shape)?;
let mut iter = out.iter();
for y in 0..cfg.image_size {
for x in 0..cfg.image_size {
if *iter.next().unwrap() {
print!("XX");
} else {
print!(" ");
}
}
println!();
}
// This will print
// XXXXXXXXXX
// XXXXXXXXXXXXXXXXXX
// XXXXXXXXXXXXXXXXXXXXXX
// XXXXXXXXXXXXXXXXXXXXXXXXXX
// XXXXXXXXXXXXXXXXXXXXXXXXXX
// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
// XXXXXXXXXXXXXXXXXXXXXXXXXX
// XXXXXXXXXXXXXXXXXXXXXXXXXX
// XXXXXXXXXXXXXXXXXXXXXX
// XXXXXXXXXXXXXXXXXX
// XXXXXXXXXX
```

## §Meshing

Fidget implements Manifold Dual Contouring, which converts from implicit surfaces to triangle meshes.

This is documented in the `fidget::mesh`

module.

## §Feature flags

`jit`

*(enabled by default)*— Enables fast evaluation via a JIT compiler. This is exposed in the`fidget::jit`

module, and is supported on macOS, Linux, and Windows (i.e. all supported platforms except WebAssembly). There’s no way to disable the feature on specific platforms (Cargo issue); users will have to disable it manually via`default-features = false`

.`rhai`

*(enabled by default)*— Enable Rhai bindings, in the`fidget::rhai`

module`render`

*(enabled by default)*— Enable 2D and 3D rendering, in the`fidget::render`

module`mesh`

*(enabled by default)*— Enable 3D meshing, in the`fidget::mesh`

module`solver`

*(enabled by default)*— Enable a system-of-equations solver, in the`fidget::solver`

module— Enable`eval-tests`

`eval-tests`

if you’re writing your own evaluators and want to unit-test them. When enabled, the crate exports a set of macros to test each evaluator type, e.g.`float_slice_tests!(...)`

.

## Modules§

- Compiler infrastructure
- Infrastructure for representing math expressions as trees and graphs
- Traits and data structures for function evaluation
- Compilation down to native machine code
- Octree construction and meshing
- 2D and 3D rendering
- Rhai bindings to Fidget
- Data structures for shape evaluation
- Solver for systems of equations expressed as sets of
`Function`

s - Custom types used during evaluation
- Input variables to math expressions
- Simple virtual machine for shape evaluation

## Structs§

- A
`Context`

holds a set of deduplicated constants, variables, and operations.

## Enums§

- Universal error type for Fidget