Magnum::Math::Geometry::Intersection namespace

Function for calculating intersections.

Contents

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

find_package(Magnum REQUIRED)

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

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

Functions

template<class T>
auto lineSegmentLineSegment(const Vector2<T>& p, const Vector2<T>& r, const Vector2<T>& q, const Vector2<T>& s) -> std::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 Vector3<T>& planePosition, const Vector3<T>& planeNormal, 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 camera frustum.
template<class T>
auto boxFrustum(const Range3D<T>& box, const Frustum<T>& frustum) -> bool
Intersection of an axis-aligned box and a camera frustum.

Function documentation

template<class T>
std::pair<T, T> Magnum::Math::Geometry::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 first line segment
r Direction of first line segment
q Starting point of second line segment
s Direction of 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} $ , 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 s & = & (\boldsymbol q + u \boldsymbol s) \times s \\ t (\boldsymbol r \times s) & = & (\boldsymbol q - \boldsymbol p) \times s \\ t & = & \cfrac{(\boldsymbol q - \boldsymbol p) \times s}{\boldsymbol r \times \boldsymbol s} \\ u & = & \cfrac{(\boldsymbol q - \boldsymbol p) \times r}{\boldsymbol r \times \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::Geometry::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 first line segment
r Direction of first line segment
q Starting point of second line
s Direction of second line

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::Geometry::Intersection::planeLine(const Vector3<T>& planePosition, const Vector3<T>& planeNormal, const Vector3<T>& p, const Vector3<T>& r)

Intersection of a plane and line.

Parameters
planePosition Plane position
planeNormal Plane normal
p Starting point of the line
r Direction of the line

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

First the parameter $ f $ of parametric equation of the plane is calculated from plane normal $ \boldsymbol{n} $ and plane position:

\[ \begin{pmatrix} n_0 \\ n_1 \\ n_2 \end{pmatrix} \cdot \begin{pmatrix} x \\ y \\ z \end{pmatrix} - f = 0 \]

Using plane normal $ \boldsymbol{n} $ , parameter $ f $ and line defined by $ \boldsymbol{p} $ and $ \boldsymbol{r} $ , value of $ t $ is calculated and returned.

\[ \begin{array}{rcl} f & = & \boldsymbol n \cdot (\boldsymbol p + t \boldsymbol r) \\ \Rightarrow t & = & \cfrac{f - \boldsymbol n \cdot \boldsymbol p}{\boldsymbol n \cdot \boldsymbol r} \end{array} \]

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

Intersection of a point and a camera frustum.

Parameters
point Point
frustum Frustum planes with normals pointing outwards

Returns true if the point is on or inside the frustum.

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::Geometry::Intersection::boxFrustum(const Range3D<T>& box, const Frustum<T>& frustum)

Intersection of an axis-aligned box and a camera frustum.

Parameters
box Axis-aligned box
frustum Frustum planes with normals pointing outwards

Returns true if the box intersects with the camera frustum.

Counts for each plane of the frustum how many points of the box lie in front of the plane (outside of the frustum). If none, the box must lie entirely outside of the frustum and there is no intersection. Else, the box is considered as intersecting, even if it is merely corners of the box overlapping with corners of the frustum, since checking the corners is less efficient.