Namespace GeometryHelper.Spatial

Classes

GeoBvh2

A bounding volume hierarchy over the edges of a shape in the plane, the counterpart of GeoBvh3 in space.

It is built over GeoEdge2, so one index serves a straight chain and a curved one alike: an arc is held as an arc and measured as an arc, and nothing is flattened to get it into the tree. Building costs a walk over the edges; after that, asking what is nearest a point, or where a segment crosses, stops looking at whole branches that cannot reach.

It is worth building when the same shape is asked many questions. For a handful of questions the plain methods on the shape are quicker, because they do not build anything.

GeoBvh3

A bounding volume hierarchy over a triangle mesh: a tree of nested axis-aligned boxes that makes queries against the mesh cost time in the logarithm of its size rather than in its size.

Every operation on a mesh without an index has to look at every triangle, because nothing rules any of them out in advance. A tree of boxes rules them out wholesale: a ray that misses a box misses everything inside it, and a box already farther away than the best answer so far cannot hold anything nearer. One traversal replaces the scan.

Building the tree costs a sort of the triangles, so it pays for itself over repeated queries rather than on the first one. Build it once and keep it for as long as the mesh does not change — which, since every geometry type here is immutable, is for as long as the mesh exists.

GeoPreparedSolid3

A body made ready to be asked many questions: its openings cut in once, its surface meshed and indexed once, its box kept.