namespace
#include <Magnum/Math/Intersection.h>
Intersection 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 intersects with a circle of a center and radius if the following holds:
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 intersects with a sphere of a center and radius if the following holds:
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 , on both lines:
- if the lines are collinear
- if the intersection is inside the line segment defined by and
- if the intersection is outside the line segment
- if the intersection is inside the line segment defined by and
- if the intersection is outside the line segment
- if the intersection doesn't exist (the 2D lines are parallel)
The two lines intersect if and exist such that:
Crossing both sides with (a perp-dot product), distributing the cross product and eliminating , then solving for and similarly for :
See also lineSegmentLine() which calculates only , useful if you don't need to test that the intersection lies inside line segment defined by and .
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 on the first line:
- if the lines are collinear
- if the intersection is inside the line segment defined by and
- if the intersection is outside the line segment
- if the intersection doesn't exist (the 2D lines are parallel)
Unlike lineSegmentLineSegment() calculates only .
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 on the line:
- if the line lies on the plane
- if the intersection is inside the line segment defined by and
- if the intersection is outside the line segment
- if the intersection doesn't exist
Using the plane equation with defined as and a line defined by and , value of is calculated as:
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::
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:
for plane normal and determinant .
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::
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 ( ) |
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 ( ) |
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 ( ) |
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 ( ) |
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 (with 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 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 ( ) |
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 are given by
with normal , cone origin , box center and box extents . 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 ( ) |
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);