Skip to content

PaulOlyslager/CollisionDetection.jl

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

94 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

CollisionDetection

A package for the log(N) retrieval of colliding objects

Build Status codecov

Contains an nd-tree data structure for the storage of objects of finite extent (i.e. not just points). Objects inserted in the tree will only descend as long as they fit the box they are assigned too. The main purpose of this tree is to enable logarithmic complexity collision detection. Applications are e.g. the implementation of graph algorithms, testing if a point is inside a boundary.

Usage

using CollisionDetection
using StaticArrays

n = 100
centers = 2 .* [rand(SVector{3,Float64}) for i in 1:n] .- 1
radii = [0.1*rand() for i in 1:n]

tree = Octree(centers, radii)

To detect colliding objects in a tree, both a bounding box and a collision predicate are required. The bounding box is given by a centre and half the size of the side of the box. The predicate takes an index and returns true or false depending on whether the i-th object stored in the tree collides with the target.

# Given an index, is the corresponding ball eligible?
pred(i) = all(centers[i].+radii[i] .> 0)
# Bounding box in the (center,halfside) format supplied for effiency
bb = @SVector[0.5, 0.5, 0.5], 0.5
# collect the iterator of admissible indices
ids = collect(searchtree(pred, tree, bb))

In this example ids will contain the indices of objects touching the (+,+,+) octant.

About

Tree data structure for log(N) collision testing

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Julia 100.0%