dolfinx::geometry Namespace Reference

Geometry data structures and algorithms. More...

Classes
class	BoundingBoxTree
struct	PointOwnershipData
	Information on the ownership of points distributed across processes. More...

Functions
template<std::floating_point T, typename U = boost::multiprecision::cpp_bin_float_double_extended>
std::array< T, 3 >	compute_distance_gjk (std::span< const T > p0, std::span< const T > q0)
	Compute the distance between two convex bodies p0 and q0, each defined by a set of points.
template<std::floating_point T, typename U = boost::multiprecision::cpp_bin_float_double_extended>
std::vector< T >	compute_distances_gjk (const std::vector< std::span< const T > > &bodies, std::span< const T > q, int num_threads)
	Compute the distance between a sequence of convex bodies p0, ..., pN and q, each defined by a set of points.
template<std::floating_point T>
std::vector< T >	shortest_vector (const mesh::Mesh< T > &mesh, int dim, std::span< const std::int32_t > entities, std::span< const T > points)
	Compute the shortest vector from a mesh entity to a point.
template<std::floating_point T>
T	compute_squared_distance_bbox (std::span< const T, 6 > b, std::span< const T, 3 > x)
	Compute squared distance between point and bounding box.
template<std::floating_point T>
std::vector< T >	squared_distance (const mesh::Mesh< T > &mesh, int dim, std::span< const std::int32_t > entities, std::span< const T > points)
	Compute the squared distance between a point and a mesh entity.
template<std::floating_point T>
BoundingBoxTree< T >	create_midpoint_tree (const mesh::Mesh< T > &mesh, int tdim, std::span< const std::int32_t > entities)
	Create a bounding box tree for the midpoints of a subset of entities.
template<std::floating_point T>
std::vector< std::int32_t >	compute_collisions (const BoundingBoxTree< T > &tree0, const BoundingBoxTree< T > &tree1)
	Compute all collisions between two bounding box trees.
template<std::floating_point T>
graph::AdjacencyList< std::int32_t >	compute_collisions (const BoundingBoxTree< T > &tree, std::span< const T > points)
	Compute collisions between points and leaf bounding boxes.
template<std::floating_point T>
std::int32_t	compute_first_colliding_cell (const mesh::Mesh< T > &mesh, std::span< const std::int32_t > cells, std::array< T, 3 > point, T tol, std::span< T > coordinate_dofs)
	Given a set of cells, find the first one that collides with a point.
template<std::floating_point T>
std::vector< std::int32_t >	compute_closest_entity (const BoundingBoxTree< T > &tree, const BoundingBoxTree< T > &midpoint_tree, const mesh::Mesh< T > &mesh, std::span< const T > points)
	Compute closest mesh entity to a point.
template<std::floating_point T>
graph::AdjacencyList< std::int32_t >	compute_colliding_cells (const mesh::Mesh< T > &mesh, const graph::AdjacencyList< std::int32_t > &candidate_cells, std::span< const T > points)
	Compute which cells collide with a point.
template<std::floating_point T>
PointOwnershipData< T >	determine_point_ownership (const mesh::Mesh< T > &mesh, std::span< const T > points, T padding, std::optional< std::span< const std::int32_t > > cells, bool find_closest_cell=true)
	Determine, for a set of points, the owning process of the cell (if any) that contains each point.

Detailed Description

Geometry data structures and algorithms.

Tools for geometric data structures and operations, e.g. searching.

Function Documentation

compute_closest_entity()

template<std::floating_point T>

std::vector< std::int32_t > compute_closest_entity	(	const BoundingBoxTree< T > &	tree,
		const BoundingBoxTree< T > &	midpoint_tree,
		const mesh::Mesh< T > &	mesh,
		std::span< const T >	points )

Compute closest mesh entity to a point.

Note

Returns a vector filled with index -1 if the bounding box tree is empty.

Parameters

[in]	tree	The bounding box tree for the entities
[in]	midpoint_tree	A bounding box tree with the midpoints of all the mesh entities. This is used to accelerate the search.
[in]	mesh	The mesh
[in]	points	The set of points (shape=(num_points, 3)). Storage is row-major.

Returns

For each point, the index of the closest mesh entity.

compute_colliding_cells()

template<std::floating_point T>

graph::AdjacencyList< std::int32_t > compute_colliding_cells	(	const mesh::Mesh< T > &	mesh,
		const graph::AdjacencyList< std::int32_t > &	candidate_cells,
		std::span< const T >	points )

Compute which cells collide with a point.

Note

Uses the GJK algorithm, see geometry::compute_distance_gjk for details.

candidate_cells can for instance be found by using geometry::compute_collisions between a bounding box tree and the set of points.

Parameters

[in]	mesh	The mesh
[in]	candidate_cells	List of candidate colliding cells for the ith point in points
[in]	points	Points to check for collision (shape=(num_points, 3)). Storage is row-major.

Returns

For each point, the cells that collide with the point.

compute_collisions() [1/2]

template<std::floating_point T>

graph::AdjacencyList< std::int32_t > compute_collisions	(	const BoundingBoxTree< T > &	tree,
		std::span< const T >	points )

Compute collisions between points and leaf bounding boxes.

Bounding boxes can overlap, therefore points can collide with more than one box.

Parameters

[in]	tree	The bounding box tree
[in]	points	The points (shape=(num_points, 3)). Storage is row-major.

Returns

For each point, the bounding box leaves that collide with the point.

compute_collisions() [2/2]

template<std::floating_point T>

std::vector< std::int32_t > compute_collisions	(	const BoundingBoxTree< T > &	tree0,
		const BoundingBoxTree< T > &	tree1 )

Compute all collisions between two bounding box trees.

Parameters

[in]	tree0	First BoundingBoxTree
[in]	tree1	Second BoundingBoxTree

Returns

List of pairs of intersecting box indices from each tree, flattened as a vector of size num_intersections*2

compute_distance_gjk()

template<std::floating_point T, typename U = boost::multiprecision::cpp_bin_float_double_extended>

std::array< T, 3 > compute_distance_gjk	(	std::span< const T >	p0,
		std::span< const T >	q0 )

Compute the distance between two convex bodies p0 and q0, each defined by a set of points.

Uses the Gilbert–Johnson–Keerthi (GJK) distance algorithm.

Parameters

[in]	p0	Body 1 list of points, shape=(num_points, 3). Row-major storage.
[in]	q0	Body 2 list of points, shape=(num_points, 3). Row-major storage.

Template Parameters

T	Floating point type
U	Floating point type used for geometry computations internally, which should be higher precision than T, to maintain accuracy.

Returns

shortest vector between bodies

compute_distances_gjk()

template<std::floating_point T, typename U = boost::multiprecision::cpp_bin_float_double_extended>

std::vector< T > compute_distances_gjk	(	const std::vector< std::span< const T > > &	bodies,
		std::span< const T >	q,
		int	num_threads )

Compute the distance between a sequence of convex bodies p0, ..., pN and q, each defined by a set of points.

Uses the Gilbert–Johnson–Keerthi (GJK) distance algorithm.

Parameters

[in]	bodies	List of the list of points that make up each of N bodies considered as body 1. shape=(num_bodies, (num_points_body_j, 3). Row-major storage.
[in]	q	Body 2 list of points, shape=(num_points, 3). Row-major storage.
[in]	num_threads	Number of threads to use. Must be >= 1.

Template Parameters

T	Floating point type
U	Floating point type used for geometry computations internally, which should be higher precision than T, to maintain accuracy.

Returns

For each body in p_j, return the shortest distance vector to body 2. Shape (num_points, 3).

compute_first_colliding_cell()

template<std::floating_point T>

std::int32_t compute_first_colliding_cell	(	const mesh::Mesh< T > &	mesh,
		std::span< const std::int32_t >	cells,
		std::array< T, 3 >	point,
		T	tol,
		std::span< T >	coordinate_dofs )

Given a set of cells, find the first one that collides with a point.

A point can collide with more than one cell. The first cell detected to collide with the point is returned. If no collision is detected, -1 is returned.

Note

cells can for instance be found by using geometry::compute_collisions between a bounding box tree for the cells of the mesh and the point.

Parameters

[in]	mesh	The mesh.
[in]	cells	Candidate cells.
[in]	point	The point (shape=(3,)).
[in]	tol	Tolerance for accepting a collision (in the squared distance).
[in,out]	coordinate_dofs	Scratch buffer, sized at least (number of nodes per cell) * 3, i.e. mesh.geometry().dofmaps().front().extent(1) * 3. A larger buffer is permitted (e.g. sized for the largest cell type in a mixed-topology mesh); only the first (number of nodes per cell) * 3 entries are used. Callers invoking this function once per point in a loop should hoist a single buffer outside the loop and pass it here to avoid a per-call allocation. Its contents on return are unspecified.

Returns

Local cell index, -1 if not found.

compute_squared_distance_bbox()

template<std::floating_point T>

T compute_squared_distance_bbox	(	std::span< const T, 6 >	b,
		std::span< const T, 3 >	x )

Compute squared distance between point and bounding box.

Parameters

[in]	b	Bounding box coordinates
[in]	x	A point

Returns

The shortest distance between the bounding box b and the point x. Returns zero if x is inside box.

create_midpoint_tree()

template<std::floating_point T>

BoundingBoxTree< T > create_midpoint_tree	(	const mesh::Mesh< T > &	mesh,
		int	tdim,
		std::span< const std::int32_t >	entities )

Create a bounding box tree for the midpoints of a subset of entities.

Parameters

[in]	mesh	The mesh
[in]	tdim	The topological dimension of the entity
[in]	entities	List of local entity indices

Returns

Bounding box tree for midpoints of entities

determine_point_ownership()

template<std::floating_point T>

PointOwnershipData< T > determine_point_ownership	(	const mesh::Mesh< T > &	mesh,
		std::span< const T >	points,
		T	padding,
		std::optional< std::span< const std::int32_t > >	cells,
		bool	find_closest_cell = true )

Determine, for a set of points, the owning process of the cell (if any) that contains each point.

A cell is a candidate for a point if the cell's bounding box, padded by padding, contains the point. Each candidate is then tested for actual containment of the point with the GJK algorithm. If no candidate actually contains a point, the point is either left unowned or, if find_closest_cell is true, assigned to the candidate cell closest to it (by GJK distance).

Parameters

[in]	mesh	The mesh
[in]	points	Points to check for collision (shape=(num_points, 3)). Storage is row-major.
[in]	padding	Amount of absolute padding applied to each cell's bounding box before searching for candidate cells/processes. Increasing padding increases the number of cells considered as candidates for a point; it does not by itself decide whether a point with no actually-containing cell is assigned an owner, which is controlled by find_closest_cell.
[in]	cells	Cells to check for ownership
[in]	find_closest_cell	If true (default), a point not actually contained in any candidate cell is instead assigned to the process owning the candidate cell closest to it. If false, such a point is left unowned.

Returns

Point ownership data.

Note

dest_owner is sorted

An entry of src_owner is -1 if the corresponding point was not contained in any candidate cell and, if find_closest_cell is true, had no candidate cell to fall back on either (e.g. because padding was too small).

dest_points is flattened row-major, shape (dest_owner.size(), 3)

With find_closest_cell set to true, a large padding value can increase the runtime of the function by orders of magnitude, since a point not contained in any candidate then requires a GJK distance computation against every candidate cell across all processes with an intersecting bounding box.

find_closest_cell must be the same on every rank of mesh.comm(): it gates collective MPI calls, so ranks disagreeing on its value will deadlock.

shortest_vector()

template<std::floating_point T>

std::vector< T > shortest_vector	(	const mesh::Mesh< T > &	mesh,
		int	dim,
		std::span< const std::int32_t >	entities,
		std::span< const T >	points )

Compute the shortest vector from a mesh entity to a point.

Parameters

[in]	mesh	The mesh
[in]	dim	Topological dimension of the mesh entity
[in]	entities	List of entities
[in]	points	Set of points (shape=(num_points, 3)), using row-major storage.

Returns

An array of vectors (shape=(num_points, 3)) where the ith row is the shortest vector between the ith entity and the ith point. Storage is row-major.

squared_distance()

template<std::floating_point T>

std::vector< T > squared_distance	(	const mesh::Mesh< T > &	mesh,
		int	dim,
		std::span< const std::int32_t >	entities,
		std::span< const T >	points )

Compute the squared distance between a point and a mesh entity.

The distance is computed between the ith input points and the ith input entity.

Note

Uses the GJK algorithm, see geometry::compute_distance_gjk for details.

Uses a convex hull approximation of linearized geometry

Parameters

[in]	mesh	Mesh containing the entities
[in]	dim	The topological dimension of the mesh entities
[in]	entities	The indices of the mesh entities (local to process)
[in]	points	The set points from which to computed the shortest (shape=(num_points, 3)). Storage is row-major.

Returns

Squared shortest distance from points[i] to entities[i]