Core Intersection Algorithms

List of intersection algorithms. More...

Collaboration diagram for Core Intersection Algorithms:

Functions
template<FaceConcept FaceType, PointConcept PointType>
bool	vcl::intersect (const FaceType &f, const Box< PointType > &box)
	Checks if a face intersects a box.
template<PointConcept PointType, FaceConcept FaceType>
bool	vcl::intersect (const Box< PointType > &box, const FaceType &f)
	Checks if a face intersects a box.
template<FaceConcept FaceType, PointConcept PointType, typename SScalar >
bool	vcl::intersect (const FaceType &f, const Sphere< SScalar > &sphere, PointType &witness, std::pair< SScalar, SScalar > &res)
	Compute the intersection between a sphere and a face, that may be also polygonal.
template<FaceConcept FaceType, typename SScalar >
bool	vcl::intersect (const FaceType &f, const Sphere< SScalar > &sphere)
	Compute the intersection between a sphere and a face, that may be also polygonal.
template<typename SScalar , FaceConcept FaceType>
bool	vcl::intersect (const Sphere< SScalar > &sphere, const FaceType &f)
	Compute the intersection between a sphere and a face, that may be also polygonal.
template<typename Obj1 , typename Obj2 >
auto	vcl::intersectFunction ()
	Return a proper intersect function between a Obj1 object and an Obj2 object.
template<PlaneConcept PlaneType, Box3Concept BoxType>
bool	vcl::intersect (const PlaneType &plane, const BoxType &box)
	Checks if a plane intersects with a box.
template<Box3Concept BoxType, PlaneConcept PlaneType>
bool	vcl::intersect (const BoxType &box, const PlaneType &p)
	Checks if a plane intersects with a box.
template<PlaneConcept PlaneType, Segment3Concept SegmentType>
bool	vcl::intersect (const PlaneType &plane, const SegmentType &segment)
	Checks if a plane intersects with a segment.
template<Segment3Concept SegmentType, PlaneConcept PlaneType>
bool	vcl::intersect (const SegmentType &segment, const PlaneType &plane)
	Checks if a plane intersects with a segment.
template<PlaneConcept PlaneType, Segment3Concept SegmentType>
std::optional< typename SegmentType::PointType >	vcl::intersection (const PlaneType &plane, const SegmentType &segment)
	Returns the intersection point between a plane and a segment, if it exists.
template<SphereConcept SphereType, Box3Concept BoxType>
bool	vcl::intersect (const SphereType &sphere, const BoxType &box)
	Checks if a sphere intersects with a 3D box.
template<Box3Concept BoxType, SphereConcept SphereType>
bool	vcl::intersect (const BoxType &box, const SphereType &sphere)
	Checks if a sphere intersects with a 3D box.
template<Triangle2Concept TriangleType, Point2Concept PointType>
bool	vcl::intersect (const TriangleType &triangle, const PointType &point)
	Checks if a 2D point intersects with/is inside a given 2D triangle having its points in counterclockwise order.
template<Point2Concept PointType, Triangle2Concept TriangleType>
bool	vcl::intersect (const PointType &point, const TriangleType &triangle)
	Checks if a 2D point intersects with/is inside a given 2D triangle having its points in counterclockwise order.
template<Triangle3Concept TriangleType, Box3Concept BoxType>
bool	vcl::intersect (const TriangleType &triangle, const BoxType &box)
	Checks if a triangle intersects with a box.
template<Box3Concept BoxType, Triangle3Concept TriangleType>
bool	vcl::intersect (const BoxType &box, const TriangleType &triangle)
	Checks if a triangle intersects with a box.
template<Triangle3Concept TriangleType, SphereConcept SphereType, Point3Concept PointType, typename ScalarType >
bool	vcl::intersect (const TriangleType &triangle, const SphereType &sphere, PointType &witness, std::pair< ScalarType, ScalarType > &res)
	Compute the intersection between a sphere and a triangle.
template<Triangle3Concept TriangleType, SphereConcept SphereType>
bool	vcl::intersect (const TriangleType &triangle, const SphereType &sphere)
	Compute the intersection between a sphere and a triangle.
template<SphereConcept SphereType, Triangle3Concept TriangleType>
bool	vcl::intersect (const SphereType &sphere, const TriangleType &t)
	Compute the intersection between a sphere and a triangle.

Detailed Description

List of intersection algorithms.

You can access these algorithms by including #include <vclib/algorithms/core/intersection.h>

Function Documentation

intersect() [1/18]

template<PointConcept PointType, FaceConcept FaceType>

bool vcl::intersect	(	const Box< PointType > &	box,
		const FaceType &	f
	)

Checks if a face intersects a box.

The function uses the separating axis theorem to test the overlap between a triangle and a box. If the face is a triangle, the function will use the intersect function between a triangle and a box. If the face is polygonal, the face is first triangulated using an earcut algorithm, and then for each triangle, the triangle-box intersection is computed.

See also

vcl::intersect(const TriangleWrapper<Scalar>&, const Box<PointType>&)

Template Parameters

FaceType	A type that satisfies the FaceConcept.
PointType	A type that satisfies the PointConcept.

Parameters

[in]	f	The input face.
[in]	box	The input box.

Returns

True if the face intersects the box, false otherwise.

intersect() [2/18]

template<Box3Concept BoxType, PlaneConcept PlaneType>

bool vcl::intersect	(	const BoxType &	box,
		const PlaneType &	p
	)

Checks if a plane intersects with a box.

Uses the algorithm from https://gdbooks.gitbooks.io/3dcollisions/content/Chapter2/static_aabb_plane.html

Template Parameters

PlaneType	The type of plane used in the intersection check.
BoxType	The type of box used in the intersection check.

Parameters

[in]	plane	The plane to check intersection with.
[in]	box	The box to check intersection with.

Returns

True if the plane intersects with the box, false otherwise.

intersect() [3/18]

template<Box3Concept BoxType, SphereConcept SphereType>

bool vcl::intersect	(	const BoxType &	box,
		const SphereType &	sphere
	)

Checks if a sphere intersects with a 3D box.

Template Parameters

SphereType	A type that satisfies the SphereConcept concept.
BoxType	A type that satisfies the Box3Concept concept.

Parameters

[in]	sphere	The sphere to check for intersection.
[in]	box	The box to check for intersection.

Returns

true if the sphere intersects with the box, false otherwise.

intersect() [4/18]

template<Box3Concept BoxType, Triangle3Concept TriangleType>

bool vcl::intersect	(	const BoxType &	box,
		const TriangleType &	triangle
	)

Checks if a triangle intersects with a box.

The function uses the separating axis theorem to test the overlap between a triangle and a box. It tests for overlap in the following directions: 1) the {x,y,z}-directions (actually, since we use the AABB of the triangle we do not even need to test these) 2) normal of the triangle 3) cross product(edge from tri, {x,y,z}-direction)

Template Parameters

TriangleType	A type that satisfies the Triangle3Concept concept.
BoxType	A type that satisfies the Box3Concept concept.

Parameters

[in]	triangle	The triangle to test for intersection.
[in]	box	The box to test for intersection with the triangle.

Returns

True if the box and triangle overlap, false otherwise.

https://gist.github.com/jflipts/fc68d4eeacfcc04fbdb2bf38e0911850

intersect() [5/18]

template<FaceConcept FaceType, PointConcept PointType>

bool vcl::intersect	(	const FaceType &	f,
		const Box< PointType > &	box
	)

Checks if a face intersects a box.

The function uses the separating axis theorem to test the overlap between a triangle and a box. If the face is a triangle, the function will use the intersect function between a triangle and a box. If the face is polygonal, the face is first triangulated using an earcut algorithm, and then for each triangle, the triangle-box intersection is computed.

See also

vcl::intersect(const TriangleWrapper<Scalar>&, const Box<PointType>&)

Template Parameters

FaceType	A type that satisfies the FaceConcept.
PointType	A type that satisfies the PointConcept.

Parameters

[in]	f	The input face.
[in]	box	The input box.

Returns

True if the face intersects the box, false otherwise.

intersect() [6/18]

template<FaceConcept FaceType, typename SScalar >

bool vcl::intersect	(	const FaceType &	f,
		const Sphere< SScalar > &	sphere
	)

Compute the intersection between a sphere and a face, that may be also polygonal.

If the face is a triangle, the intersect function between triangle and sphere will be used. If the face is polygonal, the face is first triangulated using an earcut algorithm, and then for each triangle, the triangle-sphere intersection is computed.

Parameters

[in]	f	the input face
[in]	sphere	the input sphere

Returns

true iff there is an intersection between the sphere and the face

intersect() [7/18]

template<FaceConcept FaceType, PointConcept PointType, typename SScalar >

bool vcl::intersect	(	const FaceType &	f,
		const Sphere< SScalar > &	sphere,
		PointType &	witness,
		std::pair< SScalar, SScalar > &	res
	)

Compute the intersection between a sphere and a face, that may be also polygonal.

If the face is a triangle, the intersect function between triangle and sphere will be used. If the face is polygonal, the face is first triangulated using an earcut algorithm, and then for each triangle, the triangle-sphere intersection is computed.

Parameters

[in]	f	the input face
[in]	sphere	the input sphere
[out]	witness	the point on the triangle nearest to the center of the sphere (even when there isn't intersection)
[out]	res	if not null, in the first item is stored the minimum distance between the face and the sphere, while in the second item is stored the penetration depth

Returns

true iff there is an intersection between the sphere and the face

intersect() [8/18]

template<PlaneConcept PlaneType, Box3Concept BoxType>

bool vcl::intersect	(	const PlaneType &	plane,
		const BoxType &	box
	)

Checks if a plane intersects with a box.

Uses the algorithm from https://gdbooks.gitbooks.io/3dcollisions/content/Chapter2/static_aabb_plane.html

Template Parameters

PlaneType	The type of plane used in the intersection check.
BoxType	The type of box used in the intersection check.

Parameters

[in]	plane	The plane to check intersection with.
[in]	box	The box to check intersection with.

Returns

True if the plane intersects with the box, false otherwise.

intersect() [9/18]

template<PlaneConcept PlaneType, Segment3Concept SegmentType>

bool vcl::intersect	(	const PlaneType &	plane,
		const SegmentType &	segment
	)

Checks if a plane intersects with a segment.

The function computes the projection of the segment endpoints onto the plane and checks if the endpoints are on opposite sides of the plane. If the endpoints are on opposite sides of the plane, the function returns true, indicating that an intersection exists.

Template Parameters

PlaneType	The type of plane used in the intersection check.
SegmentType	The type of segment used in the intersection check.

Parameters

[in]	plane	the plane to compute the intersection with.
[in]	segment	the 3D segment to compute the intersection with.

Returns

A boolean value indicating whether an intersection was found or not.

intersect() [10/18]

template<Point2Concept PointType, Triangle2Concept TriangleType>

bool vcl::intersect	(	const PointType &	point,
		const TriangleType &	triangle
	)

Checks if a 2D point intersects with/is inside a given 2D triangle having its points in counterclockwise order.

Checks if a 3D point intersects/is inside a 3D triangle having its points in counterclockwise order.

The function checks if a point lies within a given triangle using barycentric coordinates. It first calculates the area of the triangle, and then calculates the barycentric coordinates of the point with respect to the triangle. If the barycentric coordinates satisfy certain conditions, then the point is considered to intersect with the triangle.

Template Parameters

TriangleType	A type that satisfies the Triangle2Concept concept.
PointType	A type that satisfies the Point2Concept concept.

Parameters

[in]	triangle	The triangle to test for intersection.
[in]	point	The point to test for intersection with the triangle.

Returns

True if the point intersects with/is inside the triangle, false otherwise.

Template Parameters

TriangleType	A type that satisfies the Triangle3Concept concept.
PointType	A type that satisfies the Point3Concept concept.

Parameters

[in]	triangle	The triangle to test for intersection.
[in]	point	The point to test for intersection with the triangle.

Returns

True if the point intersects with/is inside the triangle, false otherwise.

intersect() [11/18]

template<Segment3Concept SegmentType, PlaneConcept PlaneType>

bool vcl::intersect	(	const SegmentType &	segment,
		const PlaneType &	plane
	)

Checks if a plane intersects with a segment.

The function computes the projection of the segment endpoints onto the plane and checks if the endpoints are on opposite sides of the plane. If the endpoints are on opposite sides of the plane, the function returns true, indicating that an intersection exists.

Template Parameters

PlaneType	The type of plane used in the intersection check.
SegmentType	The type of segment used in the intersection check.

Parameters

[in]	plane	the plane to compute the intersection with.
[in]	segment	the 3D segment to compute the intersection with.

Returns

A boolean value indicating whether an intersection was found or not.

intersect() [12/18]

template<typename SScalar , FaceConcept FaceType>

bool vcl::intersect	(	const Sphere< SScalar > &	sphere,
		const FaceType &	f
	)

Compute the intersection between a sphere and a face, that may be also polygonal.

If the face is a triangle, the intersect function between triangle and sphere will be used. If the face is polygonal, the face is first triangulated using an earcut algorithm, and then for each triangle, the triangle-sphere intersection is computed.

Parameters

[in]	f	the input face
[in]	sphere	the input sphere

Returns

true iff there is an intersection between the sphere and the face

intersect() [13/18]

template<SphereConcept SphereType, Box3Concept BoxType>

bool vcl::intersect	(	const SphereType &	sphere,
		const BoxType &	box
	)

Checks if a sphere intersects with a 3D box.

Template Parameters

SphereType	A type that satisfies the SphereConcept concept.
BoxType	A type that satisfies the Box3Concept concept.

Parameters

[in]	sphere	The sphere to check for intersection.
[in]	box	The box to check for intersection.

Returns

true if the sphere intersects with the box, false otherwise.

intersect() [14/18]

template<SphereConcept SphereType, Triangle3Concept TriangleType>

bool vcl::intersect	(	const SphereType &	sphere,
		const TriangleType &	t
	)

Compute the intersection between a sphere and a triangle.

Parameters

[in]	triangle	the 3D input triangle
[in]	sphere	the input sphere

Returns

true iff there is an intersection between the sphere and the triangle

intersect() [15/18]

template<Triangle3Concept TriangleType, Box3Concept BoxType>

bool vcl::intersect ( const TriangleType &  triangle, const BoxType &  box  )

private

Checks if a triangle intersects with a box.

The function uses the separating axis theorem to test the overlap between a triangle and a box. It tests for overlap in the following directions: 1) the {x,y,z}-directions (actually, since we use the AABB of the triangle we do not even need to test these) 2) normal of the triangle 3) cross product(edge from tri, {x,y,z}-direction)

Template Parameters

TriangleType	A type that satisfies the Triangle3Concept concept.
BoxType	A type that satisfies the Box3Concept concept.

Parameters

[in]	triangle	The triangle to test for intersection.
[in]	box	The box to test for intersection with the triangle.

Returns

True if the box and triangle overlap, false otherwise.

https://gist.github.com/jflipts/fc68d4eeacfcc04fbdb2bf38e0911850

intersect() [16/18]

template<Triangle2Concept TriangleType, Point2Concept PointType>

bool vcl::intersect	(	const TriangleType &	triangle,
		const PointType &	point
	)

Checks if a 2D point intersects with/is inside a given 2D triangle having its points in counterclockwise order.

Checks if a 3D point intersects/is inside a 3D triangle having its points in counterclockwise order.

The function checks if a point lies within a given triangle using barycentric coordinates. It first calculates the area of the triangle, and then calculates the barycentric coordinates of the point with respect to the triangle. If the barycentric coordinates satisfy certain conditions, then the point is considered to intersect with the triangle.

Template Parameters

TriangleType	A type that satisfies the Triangle2Concept concept.
PointType	A type that satisfies the Point2Concept concept.

Parameters

[in]	triangle	The triangle to test for intersection.
[in]	point	The point to test for intersection with the triangle.

Returns

True if the point intersects with/is inside the triangle, false otherwise.

Template Parameters

TriangleType	A type that satisfies the Triangle3Concept concept.
PointType	A type that satisfies the Point3Concept concept.

Parameters

[in]	triangle	The triangle to test for intersection.
[in]	point	The point to test for intersection with the triangle.

Returns

True if the point intersects with/is inside the triangle, false otherwise.

intersect() [17/18]

template<Triangle3Concept TriangleType, SphereConcept SphereType>

bool vcl::intersect	(	const TriangleType &	triangle,
		const SphereType &	sphere
	)

Compute the intersection between a sphere and a triangle.

Parameters

[in]	triangle	the 3D input triangle
[in]	sphere	the input sphere

Returns

true iff there is an intersection between the sphere and the triangle

intersect() [18/18]

template<Triangle3Concept TriangleType, SphereConcept SphereType, Point3Concept PointType, typename ScalarType >

bool vcl::intersect	(	const TriangleType &	triangle,
		const SphereType &	sphere,
		PointType &	witness,
		std::pair< ScalarType, ScalarType > &	res
	)

Compute the intersection between a sphere and a triangle.

Parameters

[in]	triangle	the 3D input triangle
[in]	sphere	the input sphere
[out]	witness	the point on the triangle nearest to the center of the sphere (even when there isn't intersection)
[out]	res	if not null, in the first item is stored the minimum distance between the triangle and the sphere, while in the second item is stored the penetration depth

Returns

true iff there is an intersection between the sphere and the triangle

intersectFunction()

template<typename Obj1 , typename Obj2 >

auto vcl::intersectFunction

(

)

Return a proper intersect function between a Obj1 object and an Obj2 object.

This function will return a function defined in a specialization of the struct IntersFunctionStruct.

The returned function is a std::function that takes in input two const references of the desired types and returns a boolean that tells if the two objects intersect.

If the intersection function for your types is not defined, you can write your own IntersFunctionStruct specialization that defines a proper static const inline object called intersFun of std::function type.

Note

The intersectFunction works only for non-pointer types. This means that you cannot ask for the intersect function between a vcl::Box3 and a vcl::Face*. If you are working with template types that you don't know if they are pointers or not, you can do the following:

// don't know if T1 and T2 are pointers or non-pointers
auto f = vcl::intersectFunction<vcl::RemoveCVRefAndPointer<T1>,
vcl::RemoveCVRefAndPointer<T2>>();
// obj1 is of type T1, obj2 is of type T2 (may be pointers or non-pointers)
bool theyIntersect = f(dereferencePtr(obj1), dereferencePtr(obj2));

intersection()

template<PlaneConcept PlaneType, Segment3Concept SegmentType>

std::optional< typename SegmentType::PointType > vcl::intersection	(	const PlaneType &	plane,
		const SegmentType &	segment
	)

Returns the intersection point between a plane and a segment, if it exists.

The function computes the projection of the segment endpoints onto the plane and checks if the endpoints are on opposite sides of the plane. If the endpoints are on opposite sides of the plane, the function computes and returns the intersection point between the plane and the segment.

If the endpoints are on the same side of the plane, or if the endpoints have the same projection onto the plane, the function returns an empty optional.

Template Parameters

PlaneType	The type of plane used in the intersection check.
SegmentType	The type of segment used in the intersection check.

Parameters

[in]	plane	the plane to compute the intersection with.
[in]	segment	the 3D segment to compute the intersection with.

Returns

An optional point that represents the intersection point between the plane and the box, if it exists.