Magnum::Math::Intersection namespace
#include <Magnum/Math/Intersection.h>

Functions for calculating intersections.

This library is built as part of Magnum by default. To use this library with CMake, find the Magnum package and link to the Magnum::Magnum target:

find_package(Magnum REQUIRED)

# ...
target_link_libraries(your-app PRIVATE Magnum::Magnum)

See Downloading and building and Usage with CMake for more information.

Functions

template<class T>
auto pointCircle(const Vector2<T>& point, const Vector2<T>& circleCenter, T circleRadius) -> bool new in Git master
Intersection of a point and a circle in 2D.
template<class T>
auto pointSphere(const Vector3<T>& point, const Vector3<T>& sphereCenter, T sphereRadius) -> bool new in Git master
Intersection of a point and a sphere in 3D.
template<class T>
auto lineSegmentLineSegment(const Vector2<T>& p, const Vector2<T>& r, const Vector2<T>& q, const Vector2<T>& s) -> Containers::Pair<T, T>
Intersection of two line segments in 2D.
template<class T>
auto lineSegmentLine(const Vector2<T>& p, const Vector2<T>& r, const Vector2<T>& q, const Vector2<T>& s) -> T
Intersection of line segment and line in 2D.
template<class T>
auto planeLine(const Vector4<T>& plane, const Vector3<T>& p, const Vector3<T>& r) -> T
Intersection of a plane and line.
template<class T>
auto pointFrustum(const Vector3<T>& point, const Frustum<T>& frustum) -> bool
Intersection of a point and a frustum.
template<class T>
auto rangeFrustum(const Range3D<T>& range, const Frustum<T>& frustum) -> bool
Intersection of a range and a frustum.
template<class T>
auto rayRange(const Vector3<T>& rayOrigin, const Vector3<T>& inverseRayDirection, const Range3D<T>& range) -> bool new in Git master
Intersection of a ray with a range.
template<class T>
auto aabbFrustum(const Vector3<T>& aabbCenter, const Vector3<T>& aabbExtents, const Frustum<T>& frustum) -> bool
Intersection of an axis-aligned box and a frustum.
template<class T>
auto sphereFrustum(const Vector3<T>& sphereCenter, T sphereRadius, const Frustum<T>& frustum) -> bool
Intersection of a sphere and a frustum.
template<class T>
auto pointCone(const Vector3<T>& point, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, Rad<T> coneAngle) -> bool
Intersection of a point and a cone.
template<class T>
auto pointCone(const Vector3<T>& point, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, T tanAngleSqPlusOne) -> bool
Intersection of a point and a cone using precomputed values.
template<class T>
auto pointDoubleCone(const Vector3<T>& point, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, Rad<T> coneAngle) -> bool
Intersection of a point and a double cone.
template<class T>
auto pointDoubleCone(const Vector3<T>& point, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, T tanAngleSqPlusOne) -> bool
Intersection of a point and a double cone using precomputed values.
template<class T>
auto sphereConeView(const Vector3<T>& sphereCenter, T sphereRadius, const Matrix4<T>& coneView, Rad<T> coneAngle) -> bool
Intersection of a sphere and a cone view.
template<class T>
auto sphereConeView(const Vector3<T>& sphereCenter, T sphereRadius, const Matrix4<T>& coneView, T sinAngle, T tanAngle) -> bool
Intersection of a sphere and a cone view.
template<class T>
auto sphereCone(const Vector3<T>& sphereCenter, T sphereRadius, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, Rad<T> coneAngle) -> bool
Intersection of a sphere and a cone.
template<class T>
auto sphereCone(const Vector3<T>& sphereCenter, T sphereRadius, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, T sinAngle, T tanAngleSqPlusOne) -> bool
Intersection of a sphere and a cone using precomputed values.
template<class T>
auto aabbCone(const Vector3<T>& aabbCenter, const Vector3<T>& aabbExtents, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, Rad<T> coneAngle) -> bool
Intersection of an axis aligned bounding box and a cone.
template<class T>
auto aabbCone(const Vector3<T>& aabbCenter, const Vector3<T>& aabbExtents, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, T tanAngleSqPlusOne) -> bool
Intersection of an axis aligned bounding box and a cone using precomputed values.
template<class T>
auto rangeCone(const Range3D<T>& range, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, const Rad<T> coneAngle) -> bool
Intersection of a range and a cone.
template<class T>
auto rangeCone(const Range3D<T>& range, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, const T tanAngleSqPlusOne) -> bool
Intersection of a range and a cone using precomputed values.

Function documentation

template<class T>
bool Magnum::Math::Intersection::pointCircle(const Vector2<T>& point, const Vector2<T>& circleCenter, T circleRadius) new in Git master

Intersection of a point and a circle in 2D.

Parameters
point Point
circleCenter Circle center
circleRadius Circle radius
Returns true if the the point intersects the sphere, false otherwise

Same as (circleCenter - point).dot() <= Math::pow<2>(circleRadius). A point $ \boldsymbol{p} $ intersects with a circle of a center $ \boldsymbol{c} $ and radius $ r $ if the following holds:

\[ \begin{array}{rcl} |\boldsymbol{c} - \boldsymbol{p}| & < & r \\ (\boldsymbol{c} - \boldsymbol{p}) \cdot (\boldsymbol{c} - \boldsymbol{p}) & < & r^2 \end{array} \]

template<class T>
bool Magnum::Math::Intersection::pointSphere(const Vector3<T>& point, const Vector3<T>& sphereCenter, T sphereRadius) new in Git master

Intersection of a point and a sphere in 3D.

Parameters
point Point
sphereCenter Sphere center
sphereRadius Sphere radius
Returns true if the the point intersects the sphere, false otherwise

Same as (sphereCenter - point).dot() <= Math::pow<2>(sphereRadius). A point $ \boldsymbol{p} $ intersects with a sphere of a center $ \boldsymbol{c} $ and radius $ r $ if the following holds:

\[ \begin{array}{rcl} |\boldsymbol{c} - \boldsymbol{p}| & < & r \\ (\boldsymbol{c} - \boldsymbol{p}) \cdot (\boldsymbol{c} - \boldsymbol{p}) & < & r^2 \end{array} \]

template<class T>
Containers::Pair<T, T> Magnum::Math::Intersection::lineSegmentLineSegment(const Vector2<T>& p, const Vector2<T>& r, const Vector2<T>& q, const Vector2<T>& s)

Intersection of two line segments in 2D.

Parameters
p Starting point of the first line segment
r Direction and length of the first line segment
q Starting point of the second line segment
s Direction and length of the second line segment

Returns intersection point positions $ t $ , $ u $ on both lines:

  • $ t, u = \mathrm{NaN} $ if the lines are collinear
  • $ t \in [ 0 ; 1 ] $ if the intersection is inside the line segment defined by $ \boldsymbol{p} $ and $ \boldsymbol{p} + \boldsymbol{r} $
  • $ t \notin [ 0 ; 1 ] $ if the intersection is outside the line segment
  • $ u \in [ 0 ; 1 ] $ if the intersection is inside the line segment defined by $ \boldsymbol{q} $ and $ \boldsymbol{q} + \boldsymbol{s} $
  • $ u \notin [ 0 ; 1 ] $ if the intersection is outside the line segment
  • $ t, u \in \{-\infty, \infty\} $ if the intersection doesn't exist (the 2D lines are parallel)

The two lines intersect if $ t $ and $ u $ exist such that:

\[ \boldsymbol{p} + t \boldsymbol{r} = \boldsymbol{q} + u \boldsymbol{s} \]

Crossing both sides with $ \boldsymbol{s} $ (a perp-dot product), distributing the cross product and eliminating $ \boldsymbol{s} \times \boldsymbol{s} = 0 $ , then solving for $ t $ and similarly for $ u $ :

\[ \begin{array}{rcl} (\boldsymbol{p} + t \boldsymbol{r}) \times \boldsymbol{s} & = & (\boldsymbol{q} + u \boldsymbol{s}) \times \boldsymbol{s} \\ t (\boldsymbol{r} \times \boldsymbol{s}) & = & (\boldsymbol{q} - \boldsymbol{p}) \times \boldsymbol{s} \\ t & = & \cfrac{(\boldsymbol{q} - \boldsymbol{p}) \times \boldsymbol{s}}{\boldsymbol{r} \times \boldsymbol{s}} = \cfrac{(\boldsymbol{q} - \boldsymbol{p})_\bot \cdot \boldsymbol{s}}{\boldsymbol{r}_\bot \cdot \boldsymbol{s}} \\ u & = & \cfrac{(\boldsymbol{q} - \boldsymbol{p}) \times \boldsymbol{r}}{\boldsymbol{r} \times \boldsymbol{s}} = \cfrac{(\boldsymbol{q} - \boldsymbol{p})_\bot \cdot \boldsymbol{r}}{\boldsymbol{r}_\bot \cdot \boldsymbol{s}} \end{array} \]

See also lineSegmentLine() which calculates only $ t $ , useful if you don't need to test that the intersection lies inside line segment defined by $ \boldsymbol{q} $ and $ \boldsymbol{q} + \boldsymbol{s} $ .

template<class T>
T Magnum::Math::Intersection::lineSegmentLine(const Vector2<T>& p, const Vector2<T>& r, const Vector2<T>& q, const Vector2<T>& s)

Intersection of line segment and line in 2D.

Parameters
p Starting point of the first line segment
r Direction and length of first line segment
q Starting point of the second line
s Direction of the second line. Doesn't need to be normalized.

Returns intersection point position $ t $ on the first line:

  • $ t = \mathrm{NaN} $ if the lines are collinear
  • $ t \in [ 0 ; 1 ] $ if the intersection is inside the line segment defined by $ \boldsymbol{p} $ and $ \boldsymbol{p} + \boldsymbol{r} $
  • $ t \notin [ 0 ; 1 ] $ if the intersection is outside the line segment
  • $ t \in \{-\infty, \infty\} $ if the intersection doesn't exist (the 2D lines are parallel)

Unlike lineSegmentLineSegment() calculates only $ t $ .

template<class T>
T Magnum::Math::Intersection::planeLine(const Vector4<T>& plane, const Vector3<T>& p, const Vector3<T>& r)

Intersection of a plane and line.

Parameters
plane Plane equation
p Starting point of the line
r Direction of the line. Doesn't need to be normalized.

Returns intersection point position $ t $ on the line:

  • $ t = \mathrm{NaN} $ if the line lies on the plane
  • $ t \in [ 0 ; 1 ] $ if the intersection is inside the line segment defined by $ \boldsymbol{p} $ and $ \boldsymbol{p} + \boldsymbol{r} $
  • $ t \notin [ 0 ; 1 ] $ if the intersection is outside the line segment
  • $ t \in \{-\infty, \infty\} $ if the intersection doesn't exist

Using the plane equation $ ax + by + cz + d = 0 $ with $ \boldsymbol{n} $ defined as $ \boldsymbol{n} = (a, b, c)^T $ and a line defined by $ \boldsymbol{p} $ and $ \boldsymbol{r} $ , value of $ t $ is calculated as:

\[ t = \cfrac{-d - \boldsymbol{n} \cdot \boldsymbol{p}}{\boldsymbol{n} \cdot \boldsymbol{r}} \]

template<class T>
bool Magnum::Math::Intersection::pointFrustum(const Vector3<T>& point, const Frustum<T>& frustum)

Intersection of a point and a frustum.

Parameters
point Point
frustum Frustum planes with normals pointing outwards
Returns true if the point is on or inside the frustum, false otherwise

Checks for each plane of the frustum whether the point is behind the plane (the points distance from the plane is negative) using Distance::pointPlaneScaled().

template<class T>
bool Magnum::Math::Intersection::rangeFrustum(const Range3D<T>& range, const Frustum<T>& frustum)

Intersection of a range and a frustum.

Parameters
range Range
frustum Frustum planes with normals pointing outwards
Returns true if the box intersects with the frustum, false otherwise

Uses the "p/n-vertex" approach: First converts the Range3D into a representation using center and extent which allows using the following condition for whether the plane is intersecting the box:

\[ \begin{array}{rcl} d & = & \boldsymbol c \cdot \boldsymbol n \\ r & = & \boldsymbol c \cdot \text{abs}(\boldsymbol n) \\ d + r & < & -w \end{array} \]

for plane normal $ \boldsymbol n $ and determinant $ w $ .

template<class T>
bool Magnum::Math::Intersection::rayRange(const Vector3<T>& rayOrigin, const Vector3<T>& inverseRayDirection, const Range3D<T>& range) new in Git master

Intersection of a ray with a range.

Parameters
rayOrigin Origin of the ray
inverseRayDirection Component-wise inverse of the ray direction
range Range
Returns true if the the ray intersects the range, false otherwise

Note that you need to pass the inverse ray direction and not the ray direction. The purpose for this is to reduce the number of times you have to compute a ray inverse, when doing multiple ray / range intersections (for example when traversing an AABB tree). The algorithm implemented is a version of the classical slabs algorithm, see Listing 1 in Majercik et al..

template<class T>
bool Magnum::Math::Intersection::aabbFrustum(const Vector3<T>& aabbCenter, const Vector3<T>& aabbExtents, const Frustum<T>& frustum)

Intersection of an axis-aligned box and a frustum.

Parameters
aabbCenter Center of the AABB
aabbExtents (Half-)extents of the AABB
frustum Frustum planes with normals pointing outwards
Returns true if the box intersects with the frustum, false otherwise

Uses the same method as rangeFrustum(), but does not need to convert to center/extents representation.

template<class T>
bool Magnum::Math::Intersection::sphereFrustum(const Vector3<T>& sphereCenter, T sphereRadius, const Frustum<T>& frustum)

Intersection of a sphere and a frustum.

Parameters
sphereCenter Sphere center
sphereRadius Sphere radius
frustum Frustum planes with normals pointing outwards
Returns true if the sphere intersects the frustum, false otherwise

Checks for each plane of the frustum whether the sphere is behind the plane (the points distance larger than the sphere's radius) using Distance::pointPlaneScaled().

template<class T>
bool Magnum::Math::Intersection::pointCone(const Vector3<T>& point, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, Rad<T> coneAngle)

Intersection of a point and a cone.

Parameters
point The point
coneOrigin Cone origin
coneNormal Cone normal
coneAngle Apex angle of the cone ( $ 0 < \Theta < \pi $ )
Returns true if the point is inside the cone, false otherwise

Precomputes a portion of the intersection equation from coneAngle and calls pointCone(const Vector3&, const Vector3&, const Vector3&, T).

template<class T>
bool Magnum::Math::Intersection::pointCone(const Vector3<T>& point, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, T tanAngleSqPlusOne)

Intersection of a point and a cone using precomputed values.

Parameters
point The point
coneOrigin Cone origin
coneNormal Cone normal
tanAngleSqPlusOne Precomputed portion of the cone intersection equation
Returns true if the point is inside the cone, false otherwise

The tanAngleSqPlusOne parameter can be precomputed like this:

T tanAngleSqPlusOne = Math::pow<2>(Math::tan(angle*T(0.5))) + T(1);

template<class T>
bool Magnum::Math::Intersection::pointDoubleCone(const Vector3<T>& point, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, Rad<T> coneAngle)

Intersection of a point and a double cone.

Parameters
point The point
coneOrigin Cone origin
coneNormal Cone normal
coneAngle Apex angle of the cone ( $ 0 < \Theta < \pi $ )
Returns true if the point is inside the double cone, false otherwise

Precomputes a portion of the intersection equation from coneAngle and calls pointDoubleCone(const Vector3&, const Vector3&, const Vector3&, T).

template<class T>
bool Magnum::Math::Intersection::pointDoubleCone(const Vector3<T>& point, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, T tanAngleSqPlusOne)

Intersection of a point and a double cone using precomputed values.

Parameters
point The point
coneOrigin Cone origin
coneNormal Cone normal
tanAngleSqPlusOne Precomputed portion of the cone intersection equation
Returns true if the point is inside the double cone, false otherwise

The tanAngleSqPlusOne parameter can be precomputed like this:

T tanAngleSqPlusOne = Math::pow<2>(Math::tan(angle*T(0.5))) + T(1);

template<class T>
bool Magnum::Math::Intersection::sphereConeView(const Vector3<T>& sphereCenter, T sphereRadius, const Matrix4<T>& coneView, Rad<T> coneAngle)

Intersection of a sphere and a cone view.

Parameters
sphereCenter Center of the sphere
sphereRadius Radius of the sphere
coneView View matrix with translation and rotation of the cone
coneAngle Apex angle of the cone ( $ 0 < \Theta < \pi $ )
Returns true if the sphere intersects the cone, false otherwise

Precomputes a portion of the intersection equation from coneAngle and calls sphereConeView(const Vector3<T>&, T, const Matrix4<T>&, T, T).

template<class T>
bool Magnum::Math::Intersection::sphereConeView(const Vector3<T>& sphereCenter, T sphereRadius, const Matrix4<T>& coneView, T sinAngle, T tanAngle)

Intersection of a sphere and a cone view.

Parameters
sphereCenter Sphere center
sphereRadius Sphere radius
coneView View matrix with translation and rotation of the cone
sinAngle Precomputed sine of half the cone's opening angle
tanAngle Precomputed tangent of half the cone's opening angle
Returns true if the sphere intersects the cone, false otherwise

Transforms the sphere center into cone space (using the cone view matrix) and performs sphere-cone intersection with the zero-origin -Z axis-aligned cone. The sinAngle and tanAngle can be precomputed like this:

T sinAngle = Math::sin(angle*T(0.5));
T tanAngle = Math::tan(angle*T(0.5));

template<class T>
bool Magnum::Math::Intersection::sphereCone(const Vector3<T>& sphereCenter, T sphereRadius, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, Rad<T> coneAngle)

Intersection of a sphere and a cone.

Parameters
sphereCenter Sphere center
sphereRadius Sphere radius
coneOrigin Cone origin
coneNormal Cone normal
coneAngle Apex angle of the cone ( $ 0 < \Theta < \pi $ )
Returns true if the sphere intersects with the cone, false otherwise

Precomputes a portion of the intersection equation from coneAngle and calls sphereCone(const Vector3<T>& sphereCenter, T, const Vector3<T>&, const Vector3<T>&, T, T).

template<class T>
bool Magnum::Math::Intersection::sphereCone(const Vector3<T>& sphereCenter, T sphereRadius, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, T sinAngle, T tanAngleSqPlusOne)

Intersection of a sphere and a cone using precomputed values.

Parameters
sphereCenter Sphere center
sphereRadius Sphere radius
coneOrigin Cone origin
coneNormal Cone normal
sinAngle Precomputed sine of half the cone's opening angle
tanAngleSqPlusOne Precomputed portion of the cone intersection equation
Returns true if the sphere intersects with the cone, false otherwise

Offsets the cone plane by $ -r\sin{\frac{\Theta}{2}} \cdot \boldsymbol n $ (with $ \Theta $ being the cone apex angle) which separates two half-spaces: In front of the plane, in which the sphere cone intersection test is equivalent to testing the sphere's center against a similarly offset cone (which is equivalent the cone with surface expanded by $ r $ in surface normal direction), and behind the plane, where the test is equivalent to testing whether the origin of the original cone intersects the sphere. The sinAngle and tanAngleSqPlusOne parameters can be precomputed like this:

T sinAngle = Math::sin(angle*T(0.5));
T tanAngleSqPlusOne = Math::pow<2>(Math::tan(angle*T(0.5))) + T(1);

template<class T>
bool Magnum::Math::Intersection::aabbCone(const Vector3<T>& aabbCenter, const Vector3<T>& aabbExtents, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, Rad<T> coneAngle)

Intersection of an axis aligned bounding box and a cone.

Parameters
aabbCenter Center of the AABB
aabbExtents (Half-)extents of the AABB
coneOrigin Cone origin
coneNormal Cone normal
coneAngle Apex angle of the cone ( $ 0 < \Theta < \pi $ )
Returns true if the box intersects the cone, false otherwise

Precomputes a portion of the intersection equation from coneAngle and calls aabbCone(const Vector3<T>&, const Vector3<T>&, const Vector3<T>&, const Vector3<T>&, T).

template<class T>
bool Magnum::Math::Intersection::aabbCone(const Vector3<T>& aabbCenter, const Vector3<T>& aabbExtents, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, T tanAngleSqPlusOne)

Intersection of an axis aligned bounding box and a cone using precomputed values.

Parameters
aabbCenter Center of the AABB
aabbExtents (Half-)extents of the AABB
coneOrigin Cone origin
coneNormal Cone normal
tanAngleSqPlusOne Precomputed portion of the cone intersection equation
Returns true if the box intersects the cone, false otherwise

On each axis finds the intersection points of the cone's axis with infinite planes obtained by extending the two faces of the box that are perpendicular to that axis. The intersection points on the planes perpendicular to axis $ a \in \{ 0, 1, 2 \} $ are given by

\[ \boldsymbol i = \boldsymbol n \cdot \frac{(\boldsymbol c_a - \boldsymbol o_a) \pm \boldsymbol e_a}{\boldsymbol n_a} \]

with normal $ \boldsymbol n $ , cone origin $ \boldsymbol o $ , box center $ \boldsymbol c $ and box extents $ \boldsymbol e $ . The points on the faces that are closest to this intersection point are the closest to the cone's axis and are tested for intersection with the cone using pointCone(). As soon as an intersecting point is found, the function returns true. If all points lie outside of the cone, it will return false.

The tanAngleSqPlusOne parameter can be precomputed like this:

T tanAngleSqPlusOne = Math::pow<2>(Math::tan(angle*T(0.5))) + T(1);

template<class T>
bool Magnum::Math::Intersection::rangeCone(const Range3D<T>& range, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, const Rad<T> coneAngle)

Intersection of a range and a cone.

Parameters
range Range
coneOrigin Cone origin
coneNormal Cone normal
coneAngle Apex angle of the cone ( $ 0 < \Theta < \pi $ )
Returns true if the range intersects the cone, false otherwise

Precomputes a portion of the intersection equation from coneAngle and calls rangeCone(const Range3D<T>&, const Vector3<T>&, const Vector3<T>&, T).

template<class T>
bool Magnum::Math::Intersection::rangeCone(const Range3D<T>& range, const Vector3<T>& coneOrigin, const Vector3<T>& coneNormal, const T tanAngleSqPlusOne)

Intersection of a range and a cone using precomputed values.

Parameters
range Range
coneOrigin Cone origin
coneNormal Cone normal
tanAngleSqPlusOne Precomputed portion of the cone intersection equation
Returns true if the range intersects the cone, false otherwise

Converts the range into center/extents representation and passes it on to aabbCone(). The tanAngleSqPlusOne parameter can be precomputed like this:

T tanAngleSqPlusOne = Math::pow<2>(Math::tan(angle*T(0.5))) + T(1);