B*H

Bounding Interval and Bounding Volume Hierarchies for Node.js

Introduction

Bounding Interval Hierarchies (BIH) and Bounding Volume Hierarchies (BVH) are data structures that hierarchically divide a region of space in order to reduce the number of elements that must be considered when performing spatial queries.

Space partitioning structures such as these help to dramatically speed up the processes of finding all the elements within a region or finding the intersection between a ray and a set of elements.

Both B*H trees have exactly the same API and can be used interchangably.

The B*H is written to be agnostic to the number of dimensions. Though the trees should function in higher dimensions they have only been tested in the traditional 2-D and 3-D layouts.

All traversal algorithms are non-recursive. The tree building phase is performed using the "Surface Area Hueristic" that produces pretty good, though potentially unbalanced, trees.

Installation

Using npm, installation is straightforward:

npm install bxh

Usage

var BxH  = require('bxh'),
    BIH  = BxH.BIH,
    BVH  = BxH.BVH,
    AABB = BxH.AABB,
    Ray = BxH.Ray,
    IntersectInfo = BxH.IntersectInfo;

Examples

TODO

APIs

B*H

constructor (dimensions = 3, minimumLeafSize = 2, maximumLeafSize = 4)

dimensions the number of dimensions of space within the tree.

minimumLeafSize the minimum number of elements a leaf can contain.

maximumLeafSize the maximum number of elements a leaf can contain.

Constructs a new B*H element with the specified parameters.

buildFromArrayOfElements (arrayOfElements)

arrayOfElements a collection of elements from which to build the tree.

Builds the tree structure for an array of provided elements, calling element.getAABB() and element.getWeight() as necessary.

buildFromArrayOfElementsAsync (arrayOfElements, progressCallback = null, finishedCallback = null)

arrayOfElements a collection of elements from which to build the tree.

progressCallback an optional function to call, roughly every second, with progress information about the build process.

finishedCallback an optional function to call when the building process is completed.

Asynchronously builds the tree structure for an array of provided elements, calling element.getAABB() and element.getWeight() as necessary.

buildFromArrayOfNodes (arrayOfNodes)

arrayOfNodes a collection of nodes from which to build the tree.

Builds the tree structure for an array of provided nodes. Doesn't require either element.getAABB() nor element.getWeight() to be present.

buildFromArrayOfNodesAsync (arrayOfNodes, progressCallback = null, finishedCallback = null)

arrayOfNodes a collection of nodes from which to build the tree.

progressCallback an optional function to call, roughly every second, with progress information about the build process.

finishedCallback an optional function to call when the building process is completed.

Asynchronously builds the tree structure for an array of provided nodes. Doesn't require either element.getAABB() nor element.getWeight() to be present.

intersect (ray, intersectInfo)

ray an instance of BxH.Ray

intersectionInfo

Returns nothing. On a successful intersection, the provided intesectInfo element must be modified in-place by the intersection routine that each element possesses. The intersectInfo element helps guide the remaining tree traversal and it is critical that it's properties are set by an element's intersection routine if an intersection occurs.

overlaps (AABB, returnArray = [])

AABB the AABB element that defines a region of interest.

returnArray an optional array used to store the elements that meet the function's criteria.

Returns an array of all the elements that overlap the region defined in the AABB argument.

contains (AABB, returnArray = [])

AABB the AABB element that defines a region of interest.

returnArray an optional array used to store the elements that meet the function's criteria.

Returns an array of all the elements that are completely contained by the region defined in the AABB argument.

contained (AABB, returnArray = [])

AABB the AABB element that defines a region of interest.

returnArray an optional array used to store the elements that meet the function's criteria.

Returns an array of all the elements that completely contain the region defined in the AABB argument.

AABB

constructor (min = [0,0,0], max = [0,0,0])

min the minimum coordinates of the AABB. In a 2-D AABB in screen space, the coordinates for the upper-left corner.

max the maximum coordinates of the AABB. In a 2-D AABB in screen space, the coordinates for the lower-right corner.

Constructs a new AABB of dimensionality equal to min.length using the specified bounds.

NOTE The number of elements in min and max (ie. the dimensions) must be the same.

getLength (axis)

axis the zero-based array index representing a particular axis. By convention, 0 = x, 1 = y, 2 = z, and so on.

Returns the length of the AABB along the side defined by axis.

getLengths ()

Returns an array containing the lengths of all sides of the AABB.

expandByAABB (otherAABB)

Expand this to contain otherAABB.

expandToContainElements (elements, startAt = 0)

elements an array of elements.

startAt offset into the elments which to start at.

Expand this to contain all elements.

makeToContainElements (elements)

elements an array of elements.

Return a new AABB that contains the bounds of all elements.

overlaps (otherAABB)

Returns true if this and otherAABB overlap each other.

contains (otherAABB)

Returns true if this completely contains otherAABB.

contained (otherAABB)

Returns true if this is completely contained by otherAABB.

getSurfaceArea ()

Returns the surface area of the AABB. In the 2 dimension case, this is the AABB's perimeter.

getVolume ()

Returns the volume of the AABB. In the 2 dimension case, this is the AABB's area.

clone ()

Returns a clone of this.

intersectWithRay (ray)

ray a ray to test against.

Returns false is no intersection is possible. Otherwise, returns the portion of the ray (a ray segment) that results from the intersection of the ray with the AABB.

intersectWithSegment (rs)

rs - a ray segment to test against.

Returns false is no intersection is possible. Otherwise, returns the portion of the ray segment that results from the intersection of the ray segment with the AABB.

Ray

constructor (position = [0,0,0], direction = [0,0,0], dimensions = 3)

position point of origin of the ray.

direction a vector that represents the direction of the ray.

Constructs a ray originating at position in direction direction with minT equal to 0 and maxT equal to 2**53.

toIntervals ()

Returns a ray segment for this ray that spans from this.minT to this.maxT.

getMajorAxis ()

Returns the 0-based axis that represent the component of vector this.direction with the greatest magnitude.

IntersectInfo

constructor ()

Constructs an empty IntersectInfo structure. Intersection routines are expected to fill out the IntersectInfo structure's this.isHit and this.position with true and the position of the nearest intersection on a successful intersect test.

Appendix

Definitions

AABB

Axis aligned bounding box.

BIH

Bounding Interval Hierarchy. A tree that recursively splits space along two potentially overlapping planes.

BVH

Bounding Volume Hierarchy. A tree that recursively splits space into volumes (AABBs in this implementation) The volumes minimally bound their contents.

Element

What the tree contains. A JavaScript object that provides a minimum set of required functions and can therefore be inserted into the tree directly.

The required functions are:

getAABB() Return an AABB bounding the element.

getWeight() Return a positive number representing the complexity of the element (ie. cost of performing the tests below).

intersect(ray, intersectInfo) Performs an intersection test against ray. Only required if you wish to run B*H.intersect.

overlaps(AABB) Return true if and only if the element overlaps or is contained by the region defined by AABB. Only required if you wish to run B*H.overlaps.

contains(AABB) Return true if and only if the element completely contains the region defined by AABB. Required if you wish to run B*H.contains or B*H.contained.

contained(AABB) Return true if and only if the element is completely contained by the region defined by AABB. Required if you wish to run B*H.contains or B*H.contained.

NOTE If you want to insert objects into the tree that don't contain these functions you can manually construct Nodes for your JavaScript objects that have the format specified below and then create the tree them using the buildFromArrayOfNodes* functions.

Node

A JavaScript object that contains the following properties:

i The AABB for the contained element

w The weight of the contained element

o The element itself.

iFn A function to use for intersecting element o.

oFn A function to use for performing the overlaps test on element o.

csFn A function to use for performing the contains test on element o.

cdFn A function to use for performing the contained test on element o.

Ray

A line segment defined by a starting point, position, a direction vector, direction, and two sets of parameters minT and maxT that define where along the ray the line segment begins and ends. More info.

Ray Segment

Used internally by B*H, a ray segment is a line segment defined by starting and end points. A ray segment is an array with an object for each dimension.

Each object (one per dimension) has the format of:

{a: starting position, b: ending position}

Weight

The relative cost associated with searching for an element. Most of the time the tree will contain only one type of element so their weights will all be the same value.