Dynamic AABB trees in C++ with support for periodic systems.

Overview

AABB.cc

Copyright © 2016-2018 Lester Hedges

Build Status

Released under the Zlib license.

About

A C++ implementation of a dynamic bounding volume hierarchy (BVH) using axis-aligned bounding boxes (AABBs). The data structure provides an efficient way of detecting potential overlap between objects of arbitrary shape and size and is commonly used in computer game engines for collision detection and ray tracing.

Because of their speed and flexibility, AABB trees are also well suited to overlap detection in physics applications, such as molecular simulation. They are particularly helpful for systems where there is a large size disparity between particle species, or whenever the particle density is extremely inhomogeneous. In such situations, traditional neighbour finding tools, such as cell lists, can become extremely inefficient (both in terms of memory footprint, and search speed). A good overview of the pros and cons of various neighbour finding algorithms can be found here. (Note that this only discusses the cost of querying different data structures, not the additional overhead of building them, or maintaining them as objects move around.)

In statistical physics, a common means of approximating a bulk (infinite) system is through the use of periodic boundary conditions. Here, particles that are on opposite sides of the unit box can interact through its periodic image. This library supports periodic and non-periodic systems in an arbitrary number of dimensions (>= 2). Support is also provided for simulation boxes that are partially periodic, i.e. periodic along specific axes. At present, only orthorhombic simulation boxes are supported.

The code in this library was adapted from parts of the Box2D physics engine.

Installation

A Makefile is included for building and installing the AABB library.

To compile and install the library, documentation, python wrapper, and demos:

make build
make install

By default, the library installs to /usr/local. Therefore, you may need admin privileges for the final make install step above. An alternative is to change the install location:

make PREFIX=MY_INSTALL_DIR install

If you would rather use a header-only version of the library in your application, simply run:

make header-only

The resulting library header, header-only/AABB.hpp, can be directly included in your source code without the need for compiling and linking.

Further details on using the Makefile can be found by running make without a target, i.e.

make

Compiling and linking

To use the library with a C/C++ code first include the library header file in the code.

#include <aabb/AABB.h>

Then to compile, we can use something like the following:

g++ example.cc -laabb

This assumes that we have used the default install location /usr/local. If we specify an install location, we would use a command more like the following:

g++ example.cc -I/my/path/include -L/my/path/lib -laabb

Python wrapper

A python wrapper can be built using:

make python

You will require python2.7 (and the development files if your package manager separates them) and SWIG. To use the module you will need the python file aabb.py and the shared object _aabb.so from the python directory. If you wish to use a different version of python, simply override the PYTHON make variable on the command line, e.g.

make PYTHON=3.5 python

(Note that you'll also need to update the shebang at the top of hard_disc.py to reflect your changes in order for the python demo to work.)

Example

Let's consider a two-component system of hard discs in two dimensions, where one species is much larger than the other. Making use of AABB trees, we can efficiently search for potential overlaps between discs by decomposing the system into its two constituent species and constructing a tree for each one. To test overlaps for any given disc, we simply query the two trees independently in order to find candidates. This decomposition ensures that each AABB tree has a well defined length scale, making it simple to construct and quick to query.

The image below shows the example hard disc system (left) and the AABB tree structures for each species (middle and right). Each leaf node in a tree is the AABB of an individual disc. Moving up the tree, AABBs are grouped together into larger bounding volumes in a recursive fashion, leading to a single AABB enclosing all of the discs at the root. The box outline in the left-hand image shows the periodic boundary of the system.

AABBs for a binary hard disc system.

To query overlaps between discs we start at the root node and traverse the tree. At each node we test whether the current AABB overlaps the AABB of the chosen disc. If so, we add the two children of the node to the stack of nodes to test. Whenever we reach a leaf node with which an overlap is found we record a potential overlap with that disc (we know that the AABBs of the discs overlap, but we need still need to check that discs themselves actually overlap). The animation below shows an example of such a query. The disc of interest is highlighted in green and the boundary of the periodic simulation box is shown in orange. At each stage of the search the AABB of the current node in the tree is shown in white. Leaf nodes that overlap with the trial disc are highlighted green. Note that the green leaf node on the right-hand edge of the simulation box overlaps through the periodic boundary.

Querying an AABB tree for overlaps.

You may be wondering why the AABBs shown in the previous animation are not the minimum enclosing bounding box for each disc. This is a trick that is used to avoid frequent updates of the AABB tree during dynamics (movement of the discs). Whenever an AABB changes position we need to delete it from the tree then reinsert the new one (at the updated position). This can be a costly operation. By "fattening" the AABBs a small amount it is possible to make many displacements of the objects before an update is triggered, i.e. when one of the discs moves outside of its fattened AABB. During dynamics it is also possible for the tree to become unbalanced, leading to increasingly inefficient queries. Here trees are balanced using a surface area heuristic and active balancing is handled via tree rotations. The animation below shows an example of a hard disc simulation. Dynamic AABB trees were used to maintain a configuration of non-overlapping discs throughout the trajectory.

Dynamics using AABB trees for overlap tests.

The code used to create the above animation can be found at demos/hard_disc.cc. When the library is built, you can run the demo and use VMD to view the trajectory as follows:

./demos/hard_disc
vmd trajectory.xyz -e demos/vmd.tcl

A python version of the demo can be found at python/hard_disc.py. This provides an example of how to use the python wrapper module.

Usage

There are several steps that go into building and using an AABB tree. Below are some examples showing how to use the various objects within the library.

AABB

This should be the minimum enclosing axis-aligned bounding box for an object in your simulation box. There is no need to fatten the AABB; this will be done when an object is inserted into the AABB tree. For example, to create an AABB for a two-dimensional disc we could do the following:

// Particle radius.
double radius = 1.0;

// Set the particle position.
std::vector<double> position({10, 10});

// Compute lower and upper AABB bounds.
std::vector<double> lowerBound({position[0] - radius, position[1] - radius});
std::vector<double> upperBound({position[0] + radius, position[1] + radius});

// Create the AABB.
aabb::AABB aabb(lowerBound, upperBound);

(While we refer to particles in this example, in practice a particle could be any object, e.g. a sprite in a computer game.)

Tree

Initialising a tree

To instantiate dynamic AABB trees for a periodic two-component system in two dimensions:

// Fattening factor.
double fatten = 0.1;

// Periodicity of the simulation box.
std::vector<bool> periodicity({true, true});

// Size of the simulation box.
std::vector<double> boxSize({100, 100});

// Number of small discs.
unsigned int nSmall = 100;

// Number of large discs.
unsigned int nLarge = 10;

// Create the AABB trees.
aabb::Tree treeSmall(2, fatten, periodicity, boxSize, nSmall);
aabb::Tree treeLarge(2, fatten, periodicity, boxSize, nLarge);

Many of the arguments to the constructor of Tree are optional, see the Doxygen documentation for details.

Note that both the periodicity and box size can be changed on-the-fly, e.g. for changing the box volume during a constant pressure simulation. See the setPeriodicity and setBoxSize methods for details.

Inserting a particle

To insert a particle (object) into the tree:

// Particle radius.
double radius = 1.0;

// Particle index (key).
unsigned int index = 1;

// Set the particle position.
std::vector<double> position({10.0, 10.0});

// Compute lower and upper AABB bounds.
std::vector<double> lowerBound({position[0] - radius, position[1] - radius});
std::vector<double> upperBound({position[0] + radius, position[1] + radius});

// Insert particle into the tree.
tree.insertParticle(index, position, lowerBound, upperBound);

Here index is a key that is used to create a map between particles and nodes in the AABB tree. The key should be unique to the particle and can take any value between 0 and std::numeric_limits<unsigned int>::max() - 1.

For spherical objects, the insertion can be simplified to:

tree.insertParticle(index, position, radius);

Removing a particle

If you are performing simulations using the grand canonical ensemble you may wish to remove particles from the tree. To do so:

tree.removeParticle(index);

where index is the key for the particle to be removed. (You'll need to keep track of the keys).

Querying the tree

You can query the tree for overlaps with a specific particle, or for overlaps with an arbitrary AABB object. The query method returns a vector containing the indices of the AABBs that overlap. You'll then need to test the objects enclosed by these AABBs for actual overlap with the particle of interest. (using your own overlap code).

For a particle already in the tree:

// Query AABB overlaps for particle with key 10.
std::vector<unsigned int> particles = tree.query(10);

For an arbitrary AABB:

// Set the AABB bounds.
std::vector<double> lowerBound({5, 5}};
std::vector<double> upperBound({10, 10}};

// Create the AABB.
aabb::AABB aabb(lowerBound, upperBound);

// Query the tree for overlap with the AABB.
std::vector<unsigned int> particles = tree.query(aabb);

Tests

The AABB tree is self-testing if the library is compiled in development mode, i.e.

make devel

Disclaimer

Please be aware that this a working repository so the code should be used at your own risk.

It would be great to hear from you if this library was of use in your research.

Email bugs, comments, and suggestions to [email protected].

Issues
  • Python Wrapper Build Fail on OSX 10.12.2

    Python Wrapper Build Fail on OSX 10.12.2

    $ make PYTHON=3.4 python
    --> Building Python wrapper
    ../src/AABB.cc:172:41: error: no viable overloaded '='
            else                periodicity = {false, false, false};
                                ~~~~~~~~~~~ ^ ~~~~~~~~~~~~~~~~~~~~~
    /usr/include/c++/4.2.1/bits/stl_bvector.h:516:5: note: candidate function not
          viable: cannot convert initializer list argument to 'const std::vector<bool,
          std::allocator<bool> >'
        operator=(const vector& __x)
        ^
    ../src/AABB.cc:1105:13: warning: unused variable 'height' [-Wunused-variable]
            int height = 1 + std::max(height1, height2);
                ^
    1 warning and 1 error generated.
    error: command '/usr/bin/clang' failed with exit status 1
    make: *** [python] Error 1
    
    

    Let me know if I can provide anything else. Thanks.

    opened by joel-simon 8
  • Compute the cost  why Multiply 2?

    Compute the cost why Multiply 2?

    Compute the cost why Multiply 2?

    // Cost of creating a new parent for this node and the new leaf. double cost = 2.0 * combinedSurfaceArea;

    // Minimum cost of pushing the leaf further down the tree. double inheritanceCost = 2.0 * (combinedSurfaceArea - surfaceArea);

    but hree ( aabb.getSurfaceArea() ) not Multiply 2? if (nodes[left].isLeaf()) { AABB aabb; aabb.merge(leafAABB, nodes[left].aabb); costLeft = aabb.getSurfaceArea() + inheritanceCost; } else { AABB aabb; aabb.merge(leafAABB, nodes[left].aabb); double oldArea = nodes[left].aabb.getSurfaceArea(); double newArea = aabb.getSurfaceArea(); costLeft = (newArea - oldArea) + inheritanceCost; }

    opened by bellpo 4
  • custom query help !!

    custom query help !!

    I really loved your library, simple and easy to use, I was dying for months to make my own spatial partitioning, I was almost going to hang myself. from now I would love to make a query that sort all the particles in regard to the given index of current particle. (of course by the closest distance) I'm a little stuck. and thanks

    opened by EpicSpaces 3
  • Usage with volumetric data

    Usage with volumetric data

    Hello,

    i am interested in using BVH‘s to space partition volume data. How can i use this library for that use case? I could add the voxels as particles, but i am not sure how effect that‘d be. Any advice?

    Thanks

    help wanted question 
    opened by feliwir 3
  • example error

    example error

    I make lib on mac os x sierra by command make python, then I try to run example from repository and have an error

    <Swig Object of type 'std::vector< double > *' at 0x10f81cf48> Traceback (most recent call last): File "aabb_example.py", line 194, in treeLarge.insertParticle(i, position, radiusLarge) NotImplementedError: Wrong number or type of arguments for overloaded function 'Tree_insertParticle'. Possible C/C++ prototypes are: aabb::Tree::insertParticle(std::vector< double,std::allocator< double > > &,double) aabb::Tree::insertParticle(std::vector< double,std::allocator< double > > &,std::vector< double,std::allocator< double > > &)

    What im doing wrong? I use python 2.7

    opened by Ochita 3
  • Sphere and Ray overlaps

    Sphere and Ray overlaps

    Thanks for sharing - really useful stuff.

    Quick question - I wanted to support alternate queries using either sphere overlaps or casting a ray.

    Was planning to modify: std::vector<unsigned int> Tree::query(unsigned int particle, const AABB& aabb)

    to allow sphere or ray instead of aabb as query parameter.

    Then modify: if (aabb.overlaps(nodeAABB, touchIsOverlap))

    so that it does the appropriate sphere/aabb test or ray/aabb test

    Does that approach sound like it would work?

    opened by OptimisticMonkey 2
  • support for higher dimensional AABB trees

    support for higher dimensional AABB trees

    This pull request has 3 changes:

    • support for AABB trees for any number of dimensions >= 2 (previous code is limited to 2 or 3)
    • added a touchIsOverlap parameter to specify if touching boxes should be considered overlapping (default is true, which matches the existing implementation)
    • added a alwaysReinsert argument to updateParticle which forces the particle to always be removed and reinserted, rather than only doing this if the particle leaves its fattened AABB (default is false, which matches the existing implementation)
    opened by stanleybak 2
  • Null check wrong place

    Null check wrong place

    Hey, just a heads up that I think you want to be null checking before you access the elements https://github.com/lohedges/aabbcc/blob/master/src/AABB.cc#L620-L622

    opened by kujukuju 1
  • skinThickness depending on AABB size

    skinThickness depending on AABB size

    Any reason in particular why skinThickness depends on actual AABB size?

    I'm asking about this code:

            // Fatten the AABB.
            for (unsigned int i=0;i<dimension;i++)
            {
                nodes[node].aabb.lowerBound[i] -= skinThickness * size[i];
                nodes[node].aabb.upperBound[i] += skinThickness * size[i];
            }
    

    For instance, when we have skinThickness of 1 and we insert AABB of size 100x10, insertParticle will result in inserting AABB with size of 300x30.

    opened by Omegapol 1
  • Header-Only fix

    Header-Only fix

    Fixed the line cutoffs. In the original version, the closing bracket for the aabb namespace in the headerfile was cutoff and the definition of MAX_DIMENSIONS was cut out of the cc file as well.

    opened by LZaw 1
  • AABB::contains() check is incorrect

    AABB::contains() check is incorrect

    I created an AABB tree with some particles, and then called updateParticle() with the same exact data. I expected updateParticle() to return false, since it shouldn't reinsert the node if it doesn't move. To my surprise, it was always returning true. After some debugging, I think there's a mistake in the AABB::contains() code. The code is as follows:

    bool AABB::contains(const AABB& aabb) const
        {
            assert(aabb.lowerBound.size() == lowerBound.size());
    
            for (unsigned int i=0;i<lowerBound.size();i++)
            {
                if (lowerBound[i] < aabb.lowerBound[i]) return false;
                if (upperBound[i] > aabb.upperBound[i]) return false;
            }
    
            return true;
        }
    

    I believe the check is backwards here. The condition should be switched to aabb.lowerBound[i] < lowerBound[i]) and aabb.upperBound[i] > upperBound[i]. If the current object's lower bound is less than the aabb's lower bound that we're checking against, then it still contains the target aabb. I believe this should greatly improve performance, as right now it seemed to be reinserting particles every time updateParticle is called (it may even be incorrect if the AABB grew between updates to contain the original AABB).

    opened by stanleybak 1
  • Add CMake support

    Add CMake support

    • Creates aabbcc library
    • Creates Targets and Config file for easy usage by third party libraries using find_package(aabbcc)
    • Add option to build the demo/hard_disc

    Missing/TODO:

    • Add option to build python wrapping
    • Add target to create the header-only version
    opened by phcerdan 6
Owner
Lester Hedges
Research Software Engineer
Lester Hedges
nanoflann: a C++11 header-only library for Nearest Neighbor (NN) search with KD-trees

nanoflann 1. About nanoflann is a C++11 header-only library for building KD-Trees of datasets with different topologies: R2, R3 (point clouds), SO(2)

Jose Luis Blanco-Claraco 1.6k Aug 5, 2022
heuristically and dynamically sample (more) uniformly from large decision trees of unknown shape

PROBLEM STATEMENT When writing a randomized generator for some file format in a general-purpose programming language, we can view the resulting progra

John Regehr 4 Feb 15, 2022
Lightweight, Portable, Flexible Distributed/Mobile Deep Learning with Dynamic, Mutation-aware Dataflow Dep Scheduler; for Python, R, Julia, Scala, Go, Javascript and more

Apache MXNet (incubating) for Deep Learning Apache MXNet is a deep learning framework designed for both efficiency and flexibility. It allows you to m

The Apache Software Foundation 20k Aug 5, 2022
Tensors and Dynamic neural networks in Python with strong GPU acceleration

PyTorch is a Python package that provides two high-level features: Tensor computation (like NumPy) with strong GPU acceleration Deep neural networks b

null 57.8k Aug 8, 2022
DyNet: The Dynamic Neural Network Toolkit

The Dynamic Neural Network Toolkit General Installation C++ Python Getting Started Citing Releases and Contributing General DyNet is a neural network

Chris Dyer's lab @ LTI/CMU 3.3k Aug 4, 2022
InsNet Runs Instance-dependent Neural Networks with Padding-free Dynamic Batching.

InsNet documentation InsNet (documentation) is a powerful neural network library aiming at building instance-dependent computation graphs. It is desig

Chauncey Wang 58 Jun 9, 2022
Finds static ORB features in a video(excluding the dynamic objects), typically for a SLAM scenario

static-ORB-extractor : SORBE Finds static ORB features in a video(excluding the dynamic objects), typically for a SLAM scenario Requirements OpenCV 3

null 4 Feb 26, 2022
Anomaly Detection on Dynamic (time-evolving) Graphs in Real-time and Streaming manner

Anomaly Detection on Dynamic (time-evolving) Graphs in Real-time and Streaming manner. Detecting intrusions (DoS and DDoS attacks), frauds, fake rating anomalies.

Stream-AD 681 Aug 3, 2022
BladeDISC - BladeDISC is an end-to-end DynamIc Shape Compiler project for machine learning workloads.

BladeDISC Introduction Overview Features and Roadmap Frontend Framework Support Matrix Backend Support Matrix Deployment Solutions Numbers of Typical

Alibaba 404 Aug 12, 2022
A powerful and versatile dynamic instrumentation toolkit.

MIGI Migi(My Ideas Got Incepted) is a powerful and versatile dynamic instrumentation toolkit. How it works By injecting Python scripts into target hos

nomads 3 Jan 11, 2022
High dynamic range (HDR) image comparison tool for graphics people. With an emphasis on OpenEXR images.

tev — The EXR Viewer A high dynamic range (HDR) image comparison tool for graphics people. tev allows viewing images through various tonemapping opera

Thomas Müller 664 Aug 4, 2022
Implementation of "An Analytical Solution to the IMU Initialization Problem for Visual-Inertial Systems"

An Analytical Solution to the IMU Initialization Problem for Visual-Inertial Systems Implementation of "An Analytical Solution to the IMU Initializati

David Zuniga-Noel 89 Aug 10, 2022
Material for the UIBK Operating Systems Lab (2021)

UIBK Operating Systems Lab 2021 This repository contains material required to complete exercises for the OS lab in the 2021 summer semester, including

null 15 Jun 24, 2022
VNOpenAI 23 Jul 31, 2022
Codebase for "SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems"

Codebase for "SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems"

Beidi Chen 1k Jun 29, 2022
A C++ GPGPU OpenCL library for Android and Unix systems.

CLImage A Modern Approach to using OpenCL with C++ on Android and Unix. Fabio Riccardi Glass Imaging, Inc. [email protected] Introduction CLImag

Glass Imaging 5 Jul 12, 2022
A program developed using MPI for distributed computation of Histogram for large data and their performance anaysis on multi-core systems

mpi-histo A program developed using MPI for distributed computation of Histogram for large data and their performance anaysis on multi-core systems. T

Raj Shrestha 2 Dec 21, 2021
PaRSEC: the Parallel Runtime Scheduler and Execution Controller for micro-tasks on distributed heterogeneous systems.

PaRSEC is a generic framework for architecture aware scheduling and management of micro-tasks on distributed, GPU accelerated, many-core heterogeneous architectures. PaRSEC assigns computation threads to the cores, GPU accelerators, overlaps communications and computations and uses a dynamic, fully-distributed scheduler based on architectural features such as NUMA nodes and algorithmic features such as data reuse.

null 9 Jun 19, 2022