### 4 releases (2 breaking)

0.4.0 | Jun 14, 2023 |
---|---|

0.3.1 | Sep 24, 2021 |

0.3.0 | Sep 18, 2021 |

0.2.0 | Sep 15, 2021 |

#**135** in Science

**33** downloads per month

**GPL-3.0**license

88KB

2K
SLoC

Note: this is a subject of ongoing research, no stability guarantees are made.

You can read this paper for introduction:
Paul Bourke - Random space filling of the plane (2011).

However, the provided search algorithm for the next location is inefficient,
and offers very limited control over the distribution^{[1]}.
In this work, I present two solvers for the following equation:

**sdf _{n}** are signed distance functions (primitives), by aggregate minima forming together a complex distance field - further denoted

**"SDF"**.

The goal of algorithm lies in finding a safe domain, guaranteed to not intersect with any shapes. A generic and parallel interface was implemented. Currently supported:

- User-defined distributions (including fractal and random)
- Any shapes which can be represented with SDF: curves, regular polygons, non-convex and disjoint areas, fractals or any sets with non-integer hausdorff dimension (as long as the distance can be approximated).

### Argmax2D

SDF is stored as a discrete bitmap, with memory layout reminiscent of z-order curve. Solver is guaranteed to always find **global maxima**, but increasing precision requires quadratic memory.

### GD-ADF

A paper "Adaptively Sampled Distance Fields" (doi:10.1145/344779.344899) offered an idea of reducing memory consumption, however it was very elaborate to not include *any* hints for a practical implementation. The only one being - using polynomial approximations for every node of the k-d tree; however, current work takes a different path - by storing function primitives themselves in each node (bucket). Redundant primitive elimination within a bucket was performed using interior-point method.

ADF itself implements SDF trait, allowing for complex fields composed of millions of primitives to be sampled efficiently — as opposed to computing it directly — with quadratic complexity in nature.

However, primitive elimination is not yet perfect. An elimination algorithm which is both precise and fast enough will be a subject of further theoretical research.

Once the representation is obtained, the role of optimizer takes place. For practical purposes, gradient descent with exponential convergence has been chosen — making GD-ADF a **local maxima** algorithm; as described by following equation:

Since by definition, first order derivative of distance field is constant, only direction of the gradient is considered — eliminating a number of issues with both GD/IPM; and as a bonus, rendering them to be no longer dependent on the field magnitude directly.

Unlike Argmax2D, GD-ADF offers 10-100x memory reduction, as well as continuous, exact field representation. Various speed tradeoffs are provided, including both single and double float precision.

## Examples

You can run examples with following command:

`cargo`` run --release --features "drawing" --example <example name>`

You can add

`-``-` `-`C target`-`cpu`=`native

at the command end to further improve the speed.`01_fractal_distribution`

Each subsequent circle is inserted at the maxima of distance field.

`02_random_distribution`

Given

of the maxima, a new random circle is inserted within a domain of radius `(`xy`,` magnitude`)`

and center `magnitude`

.`xy`

`03_embedded`

A distribution embedded in a distribution.

`04_polymorphic`

Showcasing:

- Dynamic dispatch interface;
- Random distribution of mixed shapes;
- Random color and texture fill style;
- Parallel generation and drawing.

`05_image_dataset`

Display over 100'000 images.

Run with `cargo`` run --release --features "drawing" --example image_dataset --`

`-C target-cpu=native``"`<image folder>`"``06_custom_primitive`

A user-defined primitive.

## Past work

In

you can find numeruos algorithms which are worth re-exploring, including quadtree and GPU implementations.`src /legacy`

## Future work

- Add more sample SDFs, and generic draw trait
- Extend to support precision below 2
^{-16}(gigapixel resolution) - Rework traits
- Generalize to N dimensions

Once above are done, I will use this library for my next project "Gallery of Babel".

#### Footnotes

: J. Shier, "A Million-Circle Fractal": https://www.d.umn.edu/~ddunham/circlepat.html

«...Run time was 14.7 hours.»

#### Dependencies

~2.4–5.5MB

~66K SLoC