dolfinx.geometry#

Methods for geometric searches and operations.

Functions

bb_tree(mesh, dim, *[, padding, entities])

Create a bounding box tree for use in collision detection.

compute_closest_entity(tree, midpoint_tree, ...)

Compute closest mesh entity to a point.

compute_colliding_cells(msh, candidates, x)

From a mesh, find which cells collide with a set of points.

compute_collisions_points(tree, x)

Compute collisions between points and leaf bounding boxes.

compute_collisions_trees(tree0, tree1)

Compute all collisions between two bounding box trees.

compute_distance_gjk(p, q)

Compute the distance between two convex bodies.

compute_distances_gjk(bodies, q, num_threads)

Compute the distance between a set of convex bodies.

create_midpoint_tree(mesh, dim, entities)

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

determine_point_ownership(mesh, points, padding)

Determine, for each point, the owning process of a containing cell.

squared_distance(mesh, dim, entities, points)

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

Classes

BoundingBoxTree(tree)

Bounding box trees used in collision detection.

PointOwnershipData(ownership_data)

Class for storing data related to the ownership of points.
class dolfinx.geometry.BoundingBoxTree(tree: BoundingBoxTree_float32 | BoundingBoxTree_float64)[source]#

Bases: Generic[Real]

Bounding box trees used in collision detection.

Wrap a C++ BoundingBoxTree.

Note

This initializer should not be used in user code. Use

bb_tree.

property bbox_coordinates: ndarray[tuple[Any, ...], dtype[Real]]#

Coordinates of lower and upper corners of bounding boxes.

Note

Rows 2*ibbox and 2*ibbox+1 correspond to the lower and upper corners of bounding box ibbox, respectively.

create_global_tree(comm: Comm) → BoundingBoxTree[Real][source]#

Create a global bounding box tree.

get_bbox(i: int) → ndarray[tuple[Any, ...], dtype[Real]][source]#

Get lower and upper corners of the ith bounding box.

Parameters:

i – Index of the box.

Returns:

The ‘lower’ and ‘upper’ points of the bounding box. Shape is (2, 3),

property num_bboxes: int#

Number of bounding boxes.

class dolfinx.geometry.PointOwnershipData(ownership_data: PointOwnershipData_float32 | PointOwnershipData_float64)[source]#

Bases: Generic[Real]

Class for storing data related to the ownership of points.

Wrap a C++ PointOwnershipData.

property dest_cells: ndarray[tuple[Any, ...], dtype[int32]]#

Cell indices where each entry of dest_points is located.

property dest_owner: ndarray[tuple[Any, ...], dtype[int32]]#

Ranks that sent dest_points to current process.

property dest_points: ndarray[tuple[Any, ...], dtype[Real]]#

Points owned by current rank.

property src_owner: ndarray[tuple[Any, ...], dtype[int32]]#

Ranks owning points sent into ownership determination.

dolfinx.geometry.bb_tree(mesh: Mesh[Real], dim: int, *, padding: float = 0.0, entities: npt.NDArray[np.int32] | None = None) → BoundingBoxTree[Real][source]#

Create a bounding box tree for use in collision detection.

Parameters:

  • mesh – The mesh.

  • dim – Dimension of the mesh entities to build bounding box for.

  • padding – Padding for each bounding box.

  • entities – List of entity indices (local to process). If not supplied, all owned and ghosted entities are used.

Returns:

Bounding box tree.

dolfinx.geometry.compute_closest_entity(tree: BoundingBoxTree[Real], midpoint_tree: BoundingBoxTree[Real], mesh: Mesh[Real], points: npt.NDArray[Real]) → npt.NDArray[np.int32][source]#

Compute closest mesh entity to a point.

Parameters:

  • tree – bounding box tree for the entities.

  • midpoint_tree – A bounding box tree with the midpoints of all the mesh entities. This is used to accelerate the search.

  • mesh – The mesh.

  • points – The points to check for collision, shape=(num_points,3).

Returns:

Mesh entity index for each point in points. Returns -1 for a point if the bounding box tree is empty.

dolfinx.geometry.compute_colliding_cells(msh: Mesh[Real], candidates: AdjacencyList, x: npt.NDArray[Real]) → AdjacencyList[source]#

From a mesh, find which cells collide with a set of points.

Parameters:

  • msh – The mesh.

  • candidates – Adjacency list of candidate colliding cells for the ith point in x.

  • x – Points to check for collision shape=(num_points, 3),

Returns:

Adjacency list where the ith node is the list of entities that collide with the ith point.

dolfinx.geometry.compute_collisions_points(tree: BoundingBoxTree[Real], x: ndarray[tuple[Any, ...], dtype[Real]]) → AdjacencyList[source]#

Compute collisions between points and leaf bounding boxes.

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

Parameters:

  • tree – Bounding box tree.

  • x – Points (shape=(num_points, 3)).

Returns:

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

dolfinx.geometry.compute_collisions_trees(tree0: BoundingBoxTree[Real], tree1: BoundingBoxTree[Real]) → ndarray[tuple[Any, ...], dtype[int32]][source]#

Compute all collisions between two bounding box trees.

Parameters:

  • tree0 – First bounding box tree.

  • tree1 – Second bounding box tree.

Returns:

List of pairs of intersecting box indices from each tree. Shape is (num_collisions, 2).

dolfinx.geometry.compute_distance_gjk(p: ndarray[tuple[Any, ...], dtype[Real]], q: ndarray[tuple[Any, ...], dtype[Real]]) → ndarray[tuple[Any, ...], dtype[Real]][source]#

Compute the distance between two convex bodies.

Each body is defined by a set of points. Uses the Gilbert-Johnson-Keerthi (GJK) distance algorithm.

Parameters:

  • p – Body 1 list of points (shape=(num_points, gdim)).

  • q – Body 2 list of points (shape=(num_points, gdim)).

Returns:

Shortest vector between the two bodies.

dolfinx.geometry.compute_distances_gjk(bodies: list[ndarray[tuple[Any, ...], dtype[Real]]], q: ndarray[tuple[Any, ...], dtype[Real]], num_threads: int) → ndarray[tuple[Any, ...], dtype[Real]][source]#

Compute the distance between a set of convex bodies.

For each convex body defined in bodies; (a set of 3D points for each body) find the shortest distance vector to the body q defined by another set of 3D points. The method uses the Gilbert-Johnson-Keerthi (GJK) distance algorithm.

Parameters:

  • bodies – List of bodies, where each body is an array of (shape=(num_points_i, 3, gdim)).

  • q – Body 2 list of points (shape=(num_points_2, 3)).

  • num_threads – Number of threads to use for GJK computation.

Returns:

Shortest vector between the two bodies.

dolfinx.geometry.create_midpoint_tree(mesh: Mesh[Real], dim: int, entities: npt.NDArray[np.int32]) → BoundingBoxTree[Real][source]#

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

Parameters:

  • mesh – The mesh.

  • dim – Topological dimension of the entities.

  • entities – Indices of mesh entities to include.

Returns:

Bounding box tree for midpoints of cell entities.

dolfinx.geometry.determine_point_ownership(mesh: Mesh, points: npt.NDArray[Real], padding: float, cells: npt.NDArray[np.int32] | None = None, find_closest_cell: bool = True) → PointOwnershipData[Real][source]#

Determine, for each point, the owning process of a containing cell.

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:

  • mesh – The mesh

  • points – Points to check for collision, shape=(num_points, gdim)

  • 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.

  • cells – Cells to check for ownership If None then all cells are considered.

  • 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).

With find_closest_cell set to True, a large padding

value will increase the run-time of the code by orders of magnitude. General advice is to use a padding on the scale of the cell size.

dolfinx.geometry.squared_distance(mesh: Mesh[Real], dim: int, entities: npt.NDArray[np.int32], points: npt.NDArray[Real]) → npt.NDArray[Real][source]#

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.

Parameters:

  • mesh – Mesh containing the entities.

  • dim – Topological dimension of the mesh entities.

  • entities – Indices of the mesh entities (local to process).

  • points – Points to compute the shortest distance from (shape=(num_points, 3)).

Returns:

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