Quadtrees, Octrees, and more in Julia
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
examples
src
test
.gitignore
.travis.yml
LICENSE.md
REQUIRE
Readme.md

Readme.md

RegionTrees.jl: Quadtrees, Octrees, and their N-Dimensional Cousins

Build Status codecov

This Julia package is a lightweight framework for defining N-Dimensional region trees. In 2D, these are called region quadtrees, and in 3D they are typically referred to as octrees. A region tree is a simple data structure used to describe some kind of spatial data with varying resolution. Each element in the tree can be a leaf, representing an N-dimensional rectangle of space, or a node which is divided exactly in half along each axis into 2^N children. In addition, each element in a RegionTrees.jl tree can carry an arbitrary data payload. This makes it easy to use RegionTrees to approximate functions or describe other interesting spatial data.

Features

  • Lightweight code with few dependencies (only StaticArrays.jl and Iterators.jl are required)
  • Optimized for speed and for few memory allocations
    • Liberal use of @generated functions lets us unroll most loops and prevent allocating temporary arrays
  • Built-in support for general adaptive sampling techniques

Usage

See examples/demo.ipynb for a tour through the API. You can also check out:

[1] Frisken et al. "Adaptively Sampled Distance Fields: A General Representation of Shape for Computer Graphics". SIGGRAPH 2000.

Gallery

An adaptively sampled distance field, from examples/adaptive_distances.ipynb:

An adaptively sampled model-predictive control problem, from examples/adaptive_mpc.ipynb:

An adaptive distance field in 3D, from AdaptiveDistanceFields.jl:

Related Packages