bvh

Documentation

Overview

Package BVH implements an AABB-backed BVH tree.

Index

• type O
• type T
  • func New(o O) *T
  • func (t *T) BroadPhase(q hyperrectangle.R) []id.ID
  • func (t *T) IDs() []id.ID
  • func (t *T) Insert(x id.ID, aabb hyperrectangle.R) error
  • func (t *T) Query(f func(r hyperrectangle.R) bool) []id.ID
  • func (t *T) Raycast(q ray.R) []id.ID
  • func (t *T) Remove(x id.ID) error
  • func (t *T) SAH() float64
  • func (t *T) Update(x id.ID, aabb hyperrectangle.R) error

Types

type O

type O struct {
	K        vector.D
	LeafSize int

	// Tolerance specifies the bounding buffer width around leaf nodes as a
	// percentage of the volume of the AABB. This value must be greater than
	// one (as the resultant AABB must encapsulate the leaf).
	Tolerance float64
}

type T

type T struct {
	// contains filtered or unexported fields
}

func New

func New(o O) *T

func (*T) BroadPhase

func (t *T) BroadPhase(q hyperrectangle.R) []id.ID

BroadPhase finds all objects which intersect with the given input AABB.

func (*T) IDs

func (t *T) IDs() []id.ID

func (*T) Insert

func (t *T) Insert(x id.ID, aabb hyperrectangle.R) error

Insert adds a new AABB into the BVH. The specific data structure which tracks this AABB is managed by the user (external to this library). After the AABB is mutated (e.g. during a simulation tick), the user must call Update to ensure the tree remains valid.

Because the AABB must remain static inside the BVH, we will create a new copy of the input.

func (*T) Query

func (t *T) Query(f func(r hyperrectangle.R) bool) []id.ID

Query finds all objects which passes the input filtering function. BroadPhase and Raycast are special cases of the Query function. The input filter will be recursively applied; that is, the child of an internal BVH node will be searched only if the parent AABB also passes the filter.

func (*T) Raycast

func (t *T) Raycast(q ray.R) []id.ID

Raycast finds all objcets which intersects the given ray.

func (*T) Remove

func (t *T) Remove(x id.ID) error

func (*T) SAH

func (t *T) SAH() float64

SAH returns the surface area heuristic as defined by MacDonald and Booth 1990. The heuristic constants are set to the values specified in Aila et al.

func (*T) Update

func (t *T) Update(x id.ID, aabb hyperrectangle.R) error

Update will move a corresponding object. Depending on the BVH tolerance and how fast an object is moving, we would expect this function to filter out a large number of Delete and subsequent Insert calls.