BoundingBoxUtils.hh File Reference

Utilities for bounding boxes. More...

#include <cmath>
#include "corecel/Assert.hh"
#include "corecel/cont/Range.hh"
#include "corecel/grid/GridTypes.hh"
#include "corecel/math/Algorithms.hh"
#include "geocel/BoundingBox.hh"
#include "OrangeTypes.hh"

Classes
class	celeritas::BoundingBoxBumper< T, U >
	Bump a bounding box outward and possibly convert to another type. More...

Functions
template<class T >
bool	celeritas::is_infinite (BoundingBox< T > const &bbox)
	Check if a bounding box spans (-inf, inf) in every direction.
template<class T >
bool	celeritas::is_finite (BoundingBox< T > const &bbox)
	Check if a bounding box has no infinities.
template<class T >
bool	celeritas::is_degenerate (BoundingBox< T > const &bbox)
	Check if a bounding box has zero length in any direction.
template<class T >
bool	celeritas::is_half_inf (BoundingBox< T > const &bbox)
	Whether any axis has an infinity on one bound but not the other.
template<class T >
Array< T, 3 >	celeritas::calc_center (BoundingBox< T > const &bbox)
	Calculate the center of a bounding box.
template<class T >
Array< T, 3 >	celeritas::calc_half_widths (BoundingBox< T > const &bbox)
	Calculate the half widths of the bounding box.
template<class T >
T	celeritas::calc_surface_area (BoundingBox< T > const &bbox)
	Calculate the surface area of a bounding box.
template<class T >
T	celeritas::calc_volume (BoundingBox< T > const &bbox)
	Calculate the volume of a bounding box.
template<class T >
constexpr BoundingBox< T >	celeritas::calc_union (BoundingBox< T > const &a, BoundingBox< T > const &b)
	Calculate the smallest bounding box enclosing two bounding boxes.
template<class T >
constexpr BoundingBox< T >	celeritas::calc_intersection (BoundingBox< T > const &a, BoundingBox< T > const &b)
	Calculate the intersection of two bounding boxes.
template<class T >
T	celeritas::calc_overlap_fraction (BoundingBox< T > const &a, BoundingBox< T > const &b)
	Calculate the overlap fraction.
template<class T >
bool	celeritas::encloses (BoundingBox< T > const &big, BoundingBox< T > const &small)
	Check if all points inside the small bbox are in the big bbox.
template<class T >
bool	celeritas::intersects_segment (BoundingBox< T > const &bbox, Array< T, 3 > const &pos, Array< T, 3 > const &dir, T distance)
	Check if a line segment may intersect a bounding box.
BBox	celeritas::calc_transform (Translation const &tr, BBox const &a)
	Calculate the bounding box of a translated box.
BBox	celeritas::calc_transform (Transformation const &tr, BBox const &a)
	Calculate the axis-aligned bounding box of a transformed box.

Detailed Description

Utilities for bounding boxes.

Function Documentation

calc_center()

template<class T >

Array< T, 3 > celeritas::calc_center ( BoundingBox< T > const &  bbox )

inline

Calculate the center of a bounding box.

Precondition

The bounding box cannot be null, or "semi-infinite" (i.e., it may not have a finite lower/upper value in a particular dimension, with a corresponding infinite upper/lower value).

calc_half_widths()

template<class T >

Array< T, 3 > celeritas::calc_half_widths ( BoundingBox< T > const &  bbox )

inline

Calculate the half widths of the bounding box.

Precondition

The bounding box cannot be null

calc_intersection()

template<class T >

constexpr BoundingBox< T > celeritas::calc_intersection ( BoundingBox< T > const &  a, BoundingBox< T > const &  b  )

inlineconstexpr

Calculate the intersection of two bounding boxes.

If there is no intersection, the result will be a null bounding box.

calc_overlap_fraction()

template<class T >

T celeritas::calc_overlap_fraction ( BoundingBox< T > const &  a, BoundingBox< T > const &  b  )

inline

Calculate the overlap fraction.

The overlap fraction is the ratio of the volume of the intersection bbox to the volume of the smaller bbox. The overlap fraction is not defined if both bboxes are infinite or either/both are degenerate.

calc_surface_area()

template<class T >

T celeritas::calc_surface_area ( BoundingBox< T > const &  bbox )

inline

Calculate the surface area of a bounding box.

Precondition

The bounding box cannot be null

calc_transform()

BBox celeritas::calc_transform	(	Transformation const &	tr,
		BBox const &	a
	)

Calculate the axis-aligned bounding box of a transformed box.

Transforming a box usually results in an oriented bounding box, but sometimes that OBB is also an AABB. This function implicitly creates the transformed bounding box and creates an AABB that encompasses that box.

The result returns an exactly transformed bounding box for axis-aligned rotations. To achieve exactness for semi-infinite bounding boxes, this method has a custom implementation of GEMV for applying exact rotations if the matrix representation simply switches vector entries or flips their sign. Without the complication, floating point arithmetic results in NaN from multiplying zeroes (in the matrix) by the infinite values.

calc_volume()

template<class T >

T celeritas::calc_volume ( BoundingBox< T > const &  bbox )

inline

Calculate the volume of a bounding box.

Precondition

The bounding box cannot be null

encloses()

template<class T >

bool celeritas::encloses ( BoundingBox< T > const &  big, BoundingBox< T > const &  small  )

inline

Check if all points inside the small bbox are in the big bbox.

All bounding boxes should enclose a "null" bounding box (there are no points in the null box, so no points are outside the big box). The null bounding box will enclose no real bounding boxes. Comparing two null bounding boxes is unspecified (forbidden for now).

intersects_segment()

template<class T >

bool celeritas::intersects_segment ( BoundingBox< T > const &  bbox, Array< T, 3 > const &  pos, Array< T, 3 > const &  dir, T  distance  )

inline

Check if a line segment may intersect a bounding box.

The line segment is defined from pos in direction dir with length distance. If the position is already inside the bounding box, the result is always true.

This uses a separating-axis test (see ericson-collision-2004 ). It translates the coordinate system to the center of the bbox and tests six axes (see Fig. 5.23, Table 5.1 in reference):

• the AABB face normals, and
• the cross products between the direction vector and face normals .

Modifications have been made from the original algorithm for robustness and GPU performance.

• Manual unrolling and unconditional evaluation of the off-axis tests lead to a 10% speedup in the along-step kernel and enable automatic vectorization when compiled with clang for aarch64.
• A relative rather than absolute tolerance is used to support large distances.
• Instead of using the midpoint of the line segment \( m \equiv x + d/2 - c \), we operate on the translated midpoint of the bbox \( c' \equiv c - x \) . This prevents the distance from being squared before subtraction in the cross-product directions, which can lead to machine-dependent catastrophic floating point errors for distances on the order of \( 1/\epsilon_\mathrm{machine} \) ).

Warning

Large segment lengths are allowed to support degenerate cases, but they may result in false positives (and result in slowing down a BVH search).

is_degenerate()

template<class T >

bool celeritas::is_degenerate ( BoundingBox< T > const &  bbox )

inline

Check if a bounding box has zero length in any direction.

Precondition

The bounding box cannot be null

is_finite()

template<class T >

bool celeritas::is_finite ( BoundingBox< T > const &  bbox )

inline

Check if a bounding box has no infinities.

Precondition

The bounding box cannot be null