pbat::geometry::ClosestPointQueries Namespace Reference

This namespace contains functions to answer closest point queries. More...

Functions
template<mini::CMatrix TMatrixX, mini::CMatrix TMatrixP, mini::CMatrix TMatrixN>
PBAT_HOST_DEVICE auto	PointOnPlane (TMatrixX const &X, TMatrixP const &P, TMatrixN const &n) -> mini::SVector< typename TMatrixX::ScalarType, TMatrixX::kRows >
	Obtain the point on the plane (P,n) closest to the point X.
template<mini::CMatrix TMatrixX, mini::CMatrix TMatrixP, mini::CMatrix TMatrixQ>
PBAT_HOST_DEVICE auto	PointOnLineSegment (TMatrixX const &X, TMatrixP const &P, TMatrixQ const &Q) -> mini::SVector< typename TMatrixX::ScalarType, TMatrixX::kRows >
	Obtain the point on the line segment PQ closest to the point X.
template<mini::CMatrix TMatrixX, mini::CMatrix TMatrixL, mini::CMatrix TMatrixU>
PBAT_HOST_DEVICE auto	PointOnAxisAlignedBoundingBox (TMatrixX const &X, TMatrixL const &L, TMatrixU const &U) -> mini::SVector< typename TMatrixX::ScalarType, TMatrixX::kRows >
	Obtain the point on the axis-aligned bounding box (AABB) defined by the lower and upper corners closest to the point X.
template<mini::CMatrix TMatrixP, mini::CMatrix TMatrixA, mini::CMatrix TMatrixB, mini::CMatrix TMatrixC>
PBAT_HOST_DEVICE auto	UvwPointInTriangle (TMatrixP const &P, TMatrixA const &A, TMatrixB const &B, TMatrixC const &C) -> mini::SVector< typename TMatrixP::ScalarType, 3 >
	Obtain the point on the triangle ABC closest to the point P in barycentric coordinates.
template<mini::CMatrix TMatrixP, mini::CMatrix TMatrixA, mini::CMatrix TMatrixB, mini::CMatrix TMatrixC>
PBAT_HOST_DEVICE auto	PointInTriangle (TMatrixP const &P, TMatrixA const &A, TMatrixB const &B, TMatrixC const &C) -> mini::SVector< typename TMatrixP::ScalarType, TMatrixP::kRows >
	Obtain the point on the triangle ABC closest to the point P.
template<mini::CMatrix TMatrixP, mini::CMatrix TMatrixA, mini::CMatrix TMatrixB, mini::CMatrix TMatrixC, mini::CMatrix TMatrixD>
PBAT_HOST_DEVICE auto	PointInTetrahedron (TMatrixP const &P, TMatrixA const &A, TMatrixB const &B, TMatrixC const &C, TMatrixD const &D) -> mini::SVector< typename TMatrixP::ScalarType, TMatrixP::kRows >
	Obtain the point in the tetrahedron ABCD closest to the point P. The order of ABCD must be such that all faces ABC, ACD, ADB and BDC are oriented with outwards pointing normals when viewed from outside the tetrahedron.
template<mini::CMatrix TMatrixP1, mini::CMatrix TMatrixQ1, mini::CMatrix TMatrixP2, mini::CMatrix TMatrixQ2, class TScalar = typename TMatrixP1::ScalarType>
PBAT_HOST_DEVICE auto	Lines (TMatrixP1 const &P1, TMatrixQ1 const &Q1, TMatrixP2 const &P2, TMatrixQ2 const &Q2, TScalar eps=std::numeric_limits< TScalar >::min()) -> mini::SVector< TScalar, 2 >
	Find closest points on two lines defined by points P1, Q1 and P2, Q2.

Detailed Description

This namespace contains functions to answer closest point queries.

Function Documentation

Lines()

template<mini::CMatrix TMatrixP1, mini::CMatrix TMatrixQ1, mini::CMatrix TMatrixP2, mini::CMatrix TMatrixQ2, class TScalar = typename TMatrixP1::ScalarType>

PBAT_HOST_DEVICE auto pbat::geometry::ClosestPointQueries::Lines	(	TMatrixP1 const &	P1,
		TMatrixQ1 const &	Q1,
		TMatrixP2 const &	P2,
		TMatrixQ2 const &	Q2,
		TScalar	eps = std::numeric_limits<TScalar>::min() ) -> mini::SVector<TScalar, 2>

Find closest points on two lines defined by points P1, Q1 and P2, Q2.

We find closest points by minimizing

\[\begin{align*} f(\alpha, \beta) &= | (P1 + \alpha d_1) - (P2 + \beta d_2) |^2 \\ &= | (P1 - P2) + (\alpha d_1 - \beta d_2) |^2 , \end{align*} \]

where \( d_1 = Q1 - P1 \) and \( d_2 = Q2 - P2 \).

We can expand \( f \) to obtain

\[\begin{align*} f(\alpha,\beta) &= |P1-P2|^2 + 2 (P1-P2)^T (\alpha d_1 - \beta d_2) + | (\alpha d_1 - \beta d_2) |^2 \\ &= |P1-P2|^2 + 2 (P1-P2)^T (\alpha d_1 - \beta d_2) + \alpha^2 |d_1|^2 - 2 \alpha \beta d_1^T d_2 + \beta^2 |d_2|^2 . \end{align*} \]

The gradients are thus

\[\begin{align*} \frac{\partial f}{\partial \alpha} &= 2 (P1-P2)^T d_1 + 2 \alpha |d_1|^2 - 2 \beta d_1^T d_2 \\ \frac{\partial f}{\partial \beta} &= -2 (P1-P2)^T d_2 - 2 \alpha d_1^T d_2 + 2 \beta |d_2|^2 \end{align*} \]

Setting the gradients to zero, we obtain the following equations

\[\begin{align*} \beta &= \frac{(P1-P2)^T d_2 + \alpha d_1^T d_2}{|d_2|^2} \\ &= \frac{(P1-P2+\alpha d_1)^T d_2}{|d_2|^2} \\ \alpha &= \frac{\beta d_1^T d_2 - (P1-P2)^T d_1}{|d_1|^2} . \end{align*} \]

Injecting the first equation into the second, we obtain

\[\begin{align*} \alpha &= \frac{-(P1-P2)^T d_1}{|d_1|^2} + \frac{(P1-P2)^T d_2 + \alpha d_1^T d_2}{|d_1|^2 |d_2|^2} d_1^T d_2 \\ \alpha &= \frac{-(P1-P2)^T d_1}{|d_1|^2} + \frac{(P1-P2)^T d_2}{|d_1|^2 |d_2|^2} d_1^T d_2 + \alpha \frac{(d_1^T d_2)^2}{|d_1|^2 |d_2|^2} \\ (1 - \frac{(d_1^T d_2)^2}{|d_1|^2 |d_2|^2}) \alpha &= \frac{-(P1-P2)^T d_1}{|d_1|^2} + \frac{(P1-P2)^T d_2}{|d_1|^2 |d_2|^2} d_1^T d_2 \\ (1 - \frac{(d_1^T d_2)^2}{|d_1|^2 |d_2|^2}) \alpha &= \frac{(P1-P2)^T (d_2 d_1^T d_2 - |d_2|^2 d_1)}{|d_1|^2 |d_2|^2} \\ (|d_1|^2 |d_2|^2 - (d_1^T d_2)^2) \alpha &= (P1-P2)^T (d_2 d_1^T d_2 - |d_2|^2 d_1) . \end{align*} \]

which allows solving for \( \alpha \) first, then \( \beta \).

Note that if the lines are parallel, then by definition,

\[\begin{align*} d_1^T d_2 &= |d_1| |d_2| \cos(\theta) \\ &= |d_1| |d_2| \\ (d_1^T d_2)^2 &= |d_1|^2 |d_2|^2 \\ |d_1|^2 |d_2|^2 - (d_1^T d_2)^2 &= 0 . \end{align*} \]

In that case, we choose \( \alpha = 0 \) and return the corresponding \( \beta \). If any line \( d_i = 0 \), it is degenerated into a point. In that case, we choose the closest point on the other line. If both lines are degenerated into points, the solution is \( \alpha, \beta = 0 \).

Template Parameters

TMatrixP1	Type of the input matrix P1
TMatrixQ1	Type of the input matrix Q1
TMatrixP2	Type of the input matrix P2
TMatrixQ2	Type of the input matrix Q2
TScalar	Type of the scalar

Parameters

P1	Point 1 on line 1
Q1	Point 2 on line 1
P2	Point 1 on line 2
Q2	Point 2 on line 2
eps	Numerical error tolerance for zero checks

Returns

2-vector \( (\alpha, \beta) \) such that the closest points are \( P1 + \alpha * (Q1 - P1) \) and \( P2 + \beta * (Q2 - P2) \)

Precondition

eps >= 0

PointInTetrahedron()

template<mini::CMatrix TMatrixP, mini::CMatrix TMatrixA, mini::CMatrix TMatrixB, mini::CMatrix TMatrixC, mini::CMatrix TMatrixD>

PBAT_HOST_DEVICE auto pbat::geometry::ClosestPointQueries::PointInTetrahedron	(	TMatrixP const &	P,
		TMatrixA const &	A,
		TMatrixB const &	B,
		TMatrixC const &	C,
		TMatrixD const &	D ) -> mini::SVector<typename TMatrixP::ScalarType, TMatrixP::kRows>

Obtain the point in the tetrahedron ABCD closest to the point P. The order of ABCD must be such that all faces ABC, ACD, ADB and BDC are oriented with outwards pointing normals when viewed from outside the tetrahedron.

Template Parameters

TMatrixP	Query point matrix type
TMatrixA	Vertex A of the tetrahedron matrix type
TMatrixB	Vertex B of the tetrahedron matrix type
TMatrixC	Vertex C of the tetrahedron matrix type
TMatrixD	Vertex D of the tetrahedron matrix type

Parameters

P	Query point
A	Vertex A of the tetrahedron
B	Vertex B of the tetrahedron
C	Vertex C of the tetrahedron
D	Vertex D of the tetrahedron

Returns

Point in the tetrahedron closest to P

See [5] section 5.16

PointInTriangle()

template<mini::CMatrix TMatrixP, mini::CMatrix TMatrixA, mini::CMatrix TMatrixB, mini::CMatrix TMatrixC>

PBAT_HOST_DEVICE auto pbat::geometry::ClosestPointQueries::PointInTriangle	(	TMatrixP const &	P,
		TMatrixA const &	A,
		TMatrixB const &	B,
		TMatrixC const &	C ) -> mini::SVector<typename TMatrixP::ScalarType, TMatrixP::kRows>

Obtain the point on the triangle ABC closest to the point P.

Template Parameters

TMatrixP	Query point matrix type
TMatrixA	Vertex A of the triangle matrix type
TMatrixB	Vertex B of the triangle matrix type
TMatrixC	Vertex C of the triangle matrix type

Parameters

P	Query point
A	Vertex A of the triangle
B	Vertex B of the triangle
C	Vertex C of the triangle

Returns

Point in the triangle closest to P

PointOnAxisAlignedBoundingBox()

template<mini::CMatrix TMatrixX, mini::CMatrix TMatrixL, mini::CMatrix TMatrixU>

PBAT_HOST_DEVICE auto pbat::geometry::ClosestPointQueries::PointOnAxisAlignedBoundingBox	(	TMatrixX const &	X,
		TMatrixL const &	L,
		TMatrixU const &	U ) -> mini::SVector<typename TMatrixX::ScalarType, TMatrixX::kRows>

Obtain the point on the axis-aligned bounding box (AABB) defined by the lower and upper corners closest to the point X.

Template Parameters

TMatrixX	Query point matrix type
TMatrixL	Lower corner of the AABB matrix type
TMatrixU	Upper corner of the AABB matrix type

Parameters

X	Query point
L	Lower corner of the AABB
U	Upper corner of the AABB

Returns

Point on the AABB closest to X

See [5] section 5.13

PointOnLineSegment()

template<mini::CMatrix TMatrixX, mini::CMatrix TMatrixP, mini::CMatrix TMatrixQ>

PBAT_HOST_DEVICE auto pbat::geometry::ClosestPointQueries::PointOnLineSegment	(	TMatrixX const &	X,
		TMatrixP const &	P,
		TMatrixQ const &	Q ) -> mini::SVector<typename TMatrixX::ScalarType, TMatrixX::kRows>

Obtain the point on the line segment PQ closest to the point X.

Template Parameters

TMatrixX	Query point matrix type
TMatrixP	Start point of the line segment matrix type
TMatrixQ	End point of the line segment matrix type

Parameters

X	Query point
P	Start point of the line segment
Q	End point of the line segment

Returns

Point on the line segment closest to X

See [5] section 5.12

PointOnPlane()

template<mini::CMatrix TMatrixX, mini::CMatrix TMatrixP, mini::CMatrix TMatrixN>

PBAT_HOST_DEVICE auto pbat::geometry::ClosestPointQueries::PointOnPlane	(	TMatrixX const &	X,
		TMatrixP const &	P,
		TMatrixN const &	n ) -> mini::SVector<typename TMatrixX::ScalarType, TMatrixX::kRows>

Obtain the point on the plane (P,n) closest to the point X.

Template Parameters

TMatrixX	Query point matrix type
TMatrixP	Point on the plane matrix type
TMatrixN	Normal of the plane matrix type

Parameters

X	Query point
P	Point on the plane
n	Normal of the plane

Returns

Point on the plane closest to X

See [5] section 5.11

UvwPointInTriangle()

template<mini::CMatrix TMatrixP, mini::CMatrix TMatrixA, mini::CMatrix TMatrixB, mini::CMatrix TMatrixC>

PBAT_HOST_DEVICE auto pbat::geometry::ClosestPointQueries::UvwPointInTriangle	(	TMatrixP const &	P,
		TMatrixA const &	A,
		TMatrixB const &	B,
		TMatrixC const &	C ) -> mini::SVector<typename TMatrixP::ScalarType, 3>

Obtain the point on the triangle ABC closest to the point P in barycentric coordinates.

Template Parameters

TMatrixP	Query point matrix type
TMatrixA	Vertex A of the triangle matrix type
TMatrixB	Vertex B of the triangle matrix type
TMatrixC	Vertex C of the triangle matrix type

Parameters

P	Query point
A	Vertex A of the triangle
B	Vertex B of the triangle
C	Vertex C of the triangle

Returns

Barycentric coordinates of the point in the triangle closest to P

See [5] section 5.15