Logo Euclid.BVH

Euclid Namespace

Type Description

Bvh

Provides static functions to create Bvh trees without specifying the generic type argument.

Bvh<'T>

A generic static Bounding Volume Hierarchy (BVH) over any items,
 built from Euclid axis aligned bounding boxes (BBox).
 The tree is built once from an array of items plus a function that returns the bounding box
 of each item, and is then immutable.
 It is well suited to unevenly distributed input because the tree adapts to the actual
 bounding boxes of the items instead of subdividing space uniformly (as an octree or grid would).
 All queries come in two flavors: box based, where the distance between two items is measured
 as the distance between their bounding boxes, and exact, where a distance function for the
 actual items is supplied. The bounding box distance is always a valid lower bound of the
 exact distance, so it is used for branch and bound pruning in both cases.

Bvh2d

Provides static functions to create Bvh2d trees without specifying the generic type argument.

Bvh2d<'T>

A generic static Bounding Volume Hierarchy (BVH) over any 2D items,
 built from Euclid axis aligned bounding rectangles (BRect).
 The tree is built once from an array of items plus a function that returns the bounding rectangle
 of each item, and is then immutable.
 This is a genuinely two dimensional tree: nodes store a BRect, not a BBox with a zero Z range,
 so it needs a third less memory and does a third less work per distance test than the 3D Bvh.
 It is well suited to unevenly distributed input because the tree adapts to the actual
 bounding rectangles of the items instead of subdividing space uniformly (as a quadtree or grid would).
 All queries come in two flavors: rectangle based, where the distance between two items is measured
 as the distance between their bounding rectangles, and exact, where a distance function for the
 actual items is supplied. The bounding rectangle distance is always a valid lower bound of the
 exact distance, so it is used for branch and bound pruning in both cases.

BvhPair

A result of a closest pair search in a Bvh tree. Holds the indices of the two items (into the input array) and the distance between them.

LineBvh

A static Bounding Volume Hierarchy (BVH) over 3D lines built from Euclid axis aligned bounding boxes (BBox).
 A thin wrapper around the generic Bvh of Line3D that measures distances between
 the exact line segments via XLine3D.getSqDistance.
 The tree is built once from an array of Line3D and is then immutable.
 It is well suited to unevenly distributed input because the tree adapts to the actual
 bounding boxes of the lines instead of subdividing space uniformly (as an octree or grid would).
 Typical queries, such as finding the closest line or all pairs of lines closer than a tolerance,
 run in about O(log n) per line instead of O(n) for a brute force scan.

LineBvh2d

A static Bounding Volume Hierarchy (BVH) over 2D lines built from Euclid bounding rectangles (BRect).

LinePair

A result of a closest pair search in a LineBvh. Holds the indices of the two lines (into the input array) and the distance between them. An alias for BvhPair.

LinePair2d

A result of a closest pair search in a LineBvh2d.

Type something to start searching.