Euclid.BVH

A Bounding Volume Hierarchy (BVH) for fast spatial queries on the Euclid geometry library. Like Euclid itself it also compiles to JavaScript and TypeScript via Fable.

Given thousands of static 3D lines with uneven spatial distribution, this library answers questions like "which pairs of lines are closest to each other?" in about O(n log n) instead of the O(n²) of a brute force scan.

Interactive nearest-neighbour demo

Try the nearest-neighbour visualisation to see the BVH in action. Step through each line's 1–10 closest neighbours, see which bounding rectangles the search tests, and compare BVH query times with a brute force scan. Adjust the line count and number of neighbours to explore how the search behaves.

For a closer look at how the tree subdivides 2D line segments, explore the tree-depth visualisation.

Why a BVH?

For finding pairs of closest lines among many static, unevenly distributed 3D lines a Bounding Volume Hierarchy over the lines' axis aligned bounding boxes is the best fit:

• Unlike a uniform grid or an octree it partitions the objects, not space, so it adapts automatically to uneven, clustered input. No tuning of cell sizes is needed.
• Unlike a k-d tree over points, it stores whole line segments. A line is in exactly one leaf, so no line has to be split or duplicated.
• Since the lines are static, the tree is built once (top-down median splits along the axis with the greatest spread of item centers, typically O(n log n)) and is then immutable and cheap to query.
• Distances between axis aligned bounding boxes (BBox) give cheap lower bounds for the distance between the lines inside them, which lets branch-and-bound queries skip most of the tree.

Usage

open Euclid

// thousands of static 3D lines:
let lines : Line3D[] = ...

// build once, typically O(n log n):
let bvh = BVHLine3D.create lines

// the closest line to a query line:
let index, distance = bvh.ClosestLine (Line3D (0., 0., 0., 1., 1., 1.))

// the nearest neighbor of a line that is itself in the tree (excluding itself):
let neighbor, dist = bvh.ClosestLine (lines.[42], 42)

// the globally closest pair of lines:
let pair = bvh.ClosestPair ()   // pair.IdxA, pair.IdxB, pair.Distance

// the nearest neighbor of every line:
let neighbors = bvh.NearestNeighbors ()

// all pairs of lines that are closer than 0.5 units to each other:
let closePairs = bvh.ClosePairs 0.5

// all lines near an axis aligned bounding box:
let hits = bvh.LinesInBox (BBox.createFromSeq [ Pnt (0., 0., 0.); Pnt (10., 10., 10.) ])

// point queries: the closest line to a 3D point, the closest point on any line,
// and all lines near a point:
let idx, dist = bvh.ClosestLine (Pnt (5., 5., 5.))
let closestPt = bvh.ClosestPoint (Pnt (5., 5., 5.))
let nearby = bvh.LinesNearPoint (Pnt (5., 5., 5.), 2.0)

// all lines from the closest to the farthest, as a lazy seq:
let tenNearest = bvh.LinesByDistance (Pnt (5., 5., 5.)) |> Seq.truncate 10 |> Seq.toArray

Generic usage

The tree itself is generic: BVH<'T> works with any item type, given a function that returns the bounding box of an item. It can also be built and queried with plain boxes.

open Euclid

// build directly from bounding boxes, the boxes are the items:
let boxes : BBox[] = ...
let bvh = BVH.createFromBoxes boxes

// the box closest to a query box (distance 0.0 if they overlap or touch):
let (index, distance) = bvh.ClosestBox queryBox

// all pairs of overlapping or touching boxes:
let overlaps = bvh.ClosePairs 0.0

// or build from any items with a box function:
type Ball = { Center: Pnt; Radius: float }
let balls : Ball[] = ...
let bvh = BVH.create (balls, fun b -> BBox.createFromCenter (b.Center, 2.*b.Radius, 2.*b.Radius, 2.*b.Radius))

// box based queries work as-is; for exact distances supply a squared distance function:
let sqDist a b = let d = max 0.0 (a.Center.DistanceTo b.Center - a.Radius - b.Radius) in d * d
let pair = bvh.ClosestPair sqDist                 // globally closest pair of balls
let touching = bvh.ClosePairs (0.1, sqDist)       // all pairs of balls closer than 0.1
let i, d = bvh.ClosestItem (queryBox, sqDist query)  // closest ball to a query ball

The bounding box distance is always a lower bound of the exact distance, so the tree can prune subtrees safely in both flavors of query.

2D usage

BVH2D<'T> provides the same generic queries for 2D items bounded by Euclid BRect values, with Pt point queries. BVHLine2D adds exact Line2D segment queries.

It is a genuinely two dimensional tree with its own data structure: its nodes store a BRect, not a BBox with a zero Z range. So it needs a third less memory per node and does a third less arithmetic per distance test than the 3D BVH<'T>.

let rects : BRect[] = ...
let bvh = BVH2D.createFromRects rects
let index, distance = bvh.ClosestRect (Pt (5., 5.))
let nearby = bvh.ItemsInRect (BRect.createXY (0., 0., 10., 10.))

let lines : Line2D[] = ...
let lineBvh = BVHLine2D.create lines
let lineIndex, lineDistance = lineBvh.ClosestLine (Pt (5., 5.))

Nearest first enumeration

Where ClosestBox answers "which item is nearest?", the *ByDistance queries answer "and then which?". They return a lazy F# seq of every item, ordered from the closest bounding volume outwards to the farthest:

// the 10 boxes nearest to a point, closest first:
for (idx, dist) in bvh.BoxesByDistance (Pnt (5., 5., 5.)) |> Seq.truncate 10 do
    printfn $"box {idx} at {dist}"

// or take as many as needed, without knowing the count upfront:
let withinFive =
    bvh.BoxesByDistance queryBox
    |> Seq.takeWhile (fun (_, d) -> d < 5.0)
    |> Seq.toArray

// the same ordered by an exact distance function instead of by the bounding box:
let nearestBalls = bvh.ItemsByDistance (queryBox, sqDist query) |> Seq.truncate 3 |> Seq.toArray

The tree is walked best first: a min heap holds the subtrees and items seen so far, keyed by their distance to the query, and the closest entry is expanded next. So only the part of the tree that is closer than the last entry taken is ever visited. Taking a single entry costs about as much as ClosestBox, taking all of them sorts the whole tree. The sequence is re-enumerable, and each enumeration starts a new traversal.

BVH2D has RectsByDistance and ItemsByDistance, BVHLine3D and BVHLine2D have LinesByDistance, each with a query volume or a query point overload and an optional skipIdx to exclude an item that is itself in the tree.

Polyline self intersection

Opening Euclid also adds tryFindSelfIntersectionWithBvh to Euclid's Polyline2D and Polyline3D. It puts the segments of the polyline into a tree and tests only the pairs of segments whose bounding rectangles or boxes touch, in about O(n log n) instead of the O(n²) of testing every pair:

match Polyline2D.tryFindSelfIntersectionWithBvh polyline with
| Some (pt, i, j) -> printfn $"segments {i} and {j} intersect at {pt}"
| None -> printfn "no self intersection"

// in 3D two segments intersect if they come closer than the skew distance, 1e-6 by default:
let hit = Polyline3D.tryFindSelfIntersectionWithBvh (polyline3D, 0.01)

In 2D it returns the same result as Euclid's Polyline2D.tryFindSelfIntersectionWithBRect. Building the tree costs more than it saves on small polylines: on .NET it is faster than testing every pair of segments from about 200 points on in 2D and from about 50 points on in 3D. On Fable JavaScript the 2D crossover depends on what else the program runs. See the benchmark for the measurements.

Examples

Runnable examples for an F# script (.fsx) after #r "nuget: Euclid.BVH". The line based examples all use the bvh built in the first one.

Clash detection on piping

Find all pairs of pipe center lines that violate a minimum clearance:

open System
open Euclid

let rand = Random 42

// 10_000 random short lines clustered in a 100 x 100 x 100 volume:
let lines =
    Array.init 10_000 (fun _ ->
        let p = Pnt (rand.NextDouble() * 100., rand.NextDouble() * 100., rand.NextDouble() * 100.)
        let v = Vec (rand.NextDouble() - 0.5, rand.NextDouble() - 0.5, rand.NextDouble() - 0.5)
        Line3D.createFromPntAndVec (p, v))

let bvh = BVHLine3D.create lines

// all pairs of lines closer than 0.25 units to each other, via dual tree traversal:
let clashes = bvh.ClosePairs 0.25
for pair in clashes do
    printfn $"line {pair.IdxA} and line {pair.IdxB} are only {pair.Distance} apart"

// the single worst offender, the globally closest pair:
let worst = bvh.ClosestPair ()
printfn $"closest pair: {worst.IdxA} and {worst.IdxB} at distance {worst.Distance}"

Snapping a point to the nearest line

// where the user clicked:
let mousePt = Pnt (50., 50., 50.)

// index of and distance to the nearest line:
let idx, dist = bvh.ClosestLine mousePt

// the exact point on that line to snap to:
let snapPt = bvh.ClosestPoint mousePt
printfn $"snapped to line {idx} at {snapPt}, {dist} away"

Nearest neighbor statistics

// for every line the index of and distance to its nearest neighbor:
let neighbors = bvh.NearestNeighbors ()

let avgGap = neighbors |> Array.averageBy (fun p -> p.Distance)
let isolated = neighbors |> Array.filter (fun p -> p.Distance > 10. * avgGap)
printfn $"average gap {avgGap}, {isolated.Length} lines are isolated"

Region queries

// all lines whose bounding box touches a region of interest:
let region = BBox.createFromSeq [ Pnt (40., 40., 40.); Pnt (60., 60., 60.) ]
for idx in bvh.LinesInBox region do
    printfn $"line {idx} is inside or touches the region"

// all lines whose bounding box is within 2.0 units of a point:
for idx in bvh.LinesNearPoint (mousePt, 2.0) do
    printfn $"line {idx} is near the point"

Overlapping boxes with the generic tree

BVH<'T> can be used with plain boxes, for example as a broad phase for collision detection:

open System
open Euclid

let rand = Random 42

// 10_000 random boxes:
let boxes =
    Array.init 10_000 (fun _ ->
        let c = Pnt (rand.NextDouble() * 100., rand.NextDouble() * 100., rand.NextDouble() * 100.)
        BBox.createFromCenter (c, rand.NextDouble(), rand.NextDouble(), rand.NextDouble()))

let bvh = BVH.createFromBoxes boxes

// all pairs of boxes that overlap or touch:
let overlaps = bvh.ClosePairs 0.0

// all boxes within 1.5 units of a given box:
let query = BBox.createFromCenter (Pnt (50., 50., 50.), 4., 4., 4.)
let near = bvh.ItemsInBox (query, 1.5)

// the box closest to a 3D point:
let (closest, distance) = bvh.ClosestBox (Pnt (0., 0., 0.))

Custom item types

Any type works, given a bounding box function. Exact distances are supplied per query:

open System
open Euclid

type Ball = { Center: Pnt; Radius: float }

let rand = Random 42
let balls =
    Array.init 5_000 (fun _ ->
        { Center = Pnt (rand.NextDouble() * 100., rand.NextDouble() * 100., rand.NextDouble() * 100.)
          Radius = 0.1 + rand.NextDouble() })

let bvh = BVH.create (balls, fun b -> BBox.createFromCenter (b.Center, 2.*b.Radius, 2.*b.Radius, 2.*b.Radius))

// exact squared surface-to-surface distance between two balls:
let sqDist a b =
    let d = max 0.0 (a.Center.DistanceTo b.Center - a.Radius - b.Radius)
    d * d

// the pair of balls with the smallest gap between their surfaces:
let pair = bvh.ClosestPair sqDist

// all pairs of balls whose surfaces are closer than 0.1:
let touching = bvh.ClosePairs (0.1, sqDist)

API

The core type is the generic BVH<'T>:

Member	Description
BVH.create (items, getBox, ?leafSize)	Builds the immutable tree from any items and a bounding box function.
BVH.createFromBoxes (boxes, ?leafSize)	Builds the tree directly from BBox[], the boxes are the items.
bvh.ClosestBox (queryBox, ?skipIdx)	The item whose bounding box is closest to a query box.
bvh.ClosestBox (pt, ?skipIdx)	The item whose bounding box is closest to a 3D point.
bvh.ClosestItem (queryBox, sqDistanceTo, ?skipIdx)	The item closest to a query, measured with an exact squared distance function.
bvh.ClosestItem (pt, sqDistanceTo, ?skipIdx)	The item closest to a 3D point, measured with an exact squared distance function.
bvh.ClosestPair () / bvh.ClosestPair sqDistance	The globally closest pair, by box distance or exact distance.
bvh.NearestNeighbors () / bvh.NearestNeighbors sqDistance	The nearest neighbor of every item.
bvh.ClosePairs maxDistance / bvh.ClosePairs (maxDistance, sqDistance)	All pairs closer than maxDistance, found by dual tree traversal.
bvh.ItemsInBox (box, ?tolerance)	All items whose bounding box is within tolerance of a given BBox.
bvh.ItemsNearPoint (pt, ?tolerance)	All items whose bounding box is within tolerance of a given 3D point.
bvh.BoxesByDistance (queryBox, ?skipIdx) / bvh.BoxesByDistance (pt, ?skipIdx)	A lazy seq of all items ordered by the distance of their bounding box, closest first.
bvh.ItemsByDistance (queryBox, sqDistanceTo, ?skipIdx) / bvh.ItemsByDistance (pt, sqDistanceTo, ?skipIdx)	A lazy seq of all items ordered by an exact squared distance function, closest first.

BVH2D<'T> is the 2D equivalent, built on BRect instead of BBox. It has the same members, with Rect in place of Box and Pt in place of Pnt:

Member	Description
BVH2D.create (items, getRect, ?leafSize)	Builds an immutable 2D tree from any items and a BRect function.
BVH2D.createFromRects (rects, ?leafSize)	Builds a 2D tree directly from BRect[], the rectangles are the items.
bvh.ClosestRect (queryRect, ?skipIdx)	The item whose bounding rectangle is closest to a query rectangle.
bvh.ClosestRect (pt, ?skipIdx)	The item whose bounding rectangle is closest to a 2D point.
bvh.ClosestItem (queryRect, sqDistanceTo, ?skipIdx)	The item closest to a query, measured with an exact squared distance function.
bvh.ClosestItem (pt, sqDistanceTo, ?skipIdx)	The item closest to a 2D point, measured with an exact squared distance function.
bvh.ClosestPair () / bvh.ClosestPair sqDistance	The globally closest pair, by rectangle distance or exact distance.
bvh.NearestNeighbors () / bvh.NearestNeighbors sqDistance	The nearest neighbor of every item.
bvh.ClosePairs maxDistance / bvh.ClosePairs (maxDistance, sqDistance)	All pairs closer than maxDistance, found by dual tree traversal.
bvh.ItemsInRect (rect, ?tolerance)	All items whose bounding rectangle is within tolerance of a given BRect.
bvh.ItemsNearPoint (pt, ?tolerance)	All items whose bounding rectangle is within tolerance of a given 2D point.
bvh.RectsByDistance (queryRect, ?skipIdx) / bvh.RectsByDistance (pt, ?skipIdx)	A lazy seq of all items ordered by the distance of their bounding rectangle, closest first.
bvh.ItemsByDistance (queryRect, sqDistanceTo, ?skipIdx) / bvh.ItemsByDistance (pt, sqDistanceTo, ?skipIdx)	A lazy seq of all items ordered by an exact squared distance function, closest first.
bvh.Rectangle	The bounding rectangle around all items.

BVHLine3D is a thin wrapper over BVH<Line3D> that measures exact segment-to-segment distances:

Member	Description
BVHLine3D.create (lines, ?leafSize)	Builds the immutable tree from an array of Line3D.
bvh.ClosestLine (query, ?skipIdx)	The index of and distance to the line closest to a query line.
bvh.ClosestPair ()	The globally closest pair of lines.
bvh.NearestNeighbors ()	The nearest neighbor of every line.
bvh.ClosePairs maxDistance	All pairs of lines closer than maxDistance to each other, found by dual tree traversal.
bvh.LinesInBox (box, ?tolerance)	All lines whose bounding box is within tolerance of a given BBox.
bvh.ClosestLine (pt, ?skipIdx)	The index of and distance to the line closest to a 3D point.
bvh.ClosestPoint pt	The point on any line in the tree that is closest to a 3D point.
bvh.LinesNearPoint (pt, ?tolerance)	All lines whose bounding box is within tolerance of a given 3D point.
bvh.LinesByDistance (query, ?skipIdx) / bvh.LinesByDistance (pt, ?skipIdx)	A lazy seq of all lines ordered by their exact distance to a query line or point, closest first.
bvh.Tree	The underlying generic BVH<Line3D>.

BVHLine2D provides the corresponding Line2D API: ClosestLine, ClosestPoint, ClosestPair, NearestNeighbors, ClosePairs, LinesInRect, LinesNearPoint, and LinesByDistance.

Extension members on Euclid's polylines, available after open Euclid:

Member	Description
Polyline2D.tryFindSelfIntersectionWithBvh pl	The first self intersection of a 2D polyline, as the intersection point and the two segment indices, using a BVH2D over its segments.
Polyline3D.tryFindSelfIntersectionWithBvh (pl, ?maxSkewDistance)	The first self intersection of a 3D polyline, where two segments intersect if they come closer than maxSkewDistance, using a BVH over its segments.

Full API documentation: goswinr.github.io/Euclid.BVH

Build

dotnet build

Test

The test suite is written with Scriptorium, so the same tests run on .NET and on the Fable targets.

On .NET:

dotnet run --project Test/Test.fsproj

On JavaScript, plus a TypeScript compile check of the library:

cd Test
npm ci
npm test

The tests verify all queries against brute force implementations on randomized, clustered input.

Changelog

See CHANGELOG.md

License

MIT