Geometry (dolfinx::geometry)

namespace geometry

Geometry data structures and algorithms.

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

Functions

template<std::floating_point T>
std::array<T, 3> compute_distance_gjk(std::span<const T> p, std::span<const T> q)

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

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

Parameters:

  • p – [in] Body 1 list of points, shape (num_points, 3). Row-major storage.

  • q – [in] Body 2 list of points, shape (num_points, 3). Row-major storage.

Returns:

shortest vector between bodies

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:

  • mesh – [in] The mesh

  • dim – [in] Topological dimension of the mesh entity

  • entities – [in] List of entities

  • points – [in] 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.

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:

  • b – [in] Bounding box coordinates

  • x – [in] A point

Returns:

The shortest distance between the bounding box b and the point x. Returns zero if x is inside 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.

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.

Note

Uses a convex hull approximation of linearized geometry

Parameters:

  • mesh – [in] Mesh containing the entities

  • dim – [in] The topological dimension of the mesh entities

  • entities – [in] The indices of the mesh entities (local to process)

  • points – [in] 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]

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:

  • mesh – [in] The mesh

  • tdim – [in] The topological dimension of the entity

  • entities – [in] List of local entity indices

Returns:

Bounding box tree for midpoints 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.

Parameters:
Returns:

List of pairs of intersecting box indices from each tree, flattened as a vector of size num_intersections*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:

  • tree – [in] The bounding box tree

  • points – [in] The points (shape=(num_points, 3)). Storage is row-major.

Returns:

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

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)

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:

  • mesh – [in] The mesh.

  • cells – [in] Candidate cells.

  • point – [in] The point (shape=(3,)).

  • tol – [in] Tolerance for accepting a collision (in the squared distance).

Returns:

Local cell index, -1 if not found.

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:

  • tree – [in] The bounding box tree for the entities

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

  • mesh – [in] The mesh

  • points – [in] The set of points (shape=(num_points, 3)). Storage is row-major.

Returns:

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

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.

Note

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

Parameters:

  • mesh – [in] The mesh

  • candidate_cells – [in] List of candidate colliding cells for the ith point in points

  • points – [in] Points to check for collision (shape=(num_points, / 3)). Storage is row-major.

Returns:

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

template<std::floating_point T>
PointOwnershipData<T> determine_point_ownership(const mesh::Mesh<T> &mesh, std::span<const T> points, T padding)

Given a set of points, determine which process is colliding, using the GJK algorithm on cells to determine collisions.

Todo:

This docstring is unclear. Needs fixing.

Note

dest_owner is sorted

Note

Returns -1 if no colliding process is found

Note

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

Note

Only looks through cells owned by the process

Note

A large padding value can increase the runtime of the function by orders of magnitude, because for non-colliding cells one has to determine the closest cell among all processes with an intersecting bounding box, which is an expensive operation to perform.

Parameters:

  • mesh – [in] The mesh

  • points – [in] Points to check for collision (shape=(num_points, / 3)). Storage is row-major.

  • padding – [in] Amount of absolute padding of bounding boxes of the mesh. Each bounding box of the mesh is padded with this amount, to increase the number of candidates, avoiding rounding errors in determining the owner of a point if the point is on the surface of a cell in the mesh.

Returns:

Tuple (src_owner, dest_owner, dest_points, dest_cells), where src_owner is a list of ranks corresponding to the input points. dest_owner is a list of ranks corresponding to dest_points, the points that this process owns. dest_cells contains the corresponding cell for each entry in dest_points.

template<std::floating_point T>
class BoundingBoxTree
#include <BoundingBoxTree.h>

Axis-Aligned bounding box binary tree. It is used to find entities in a collection (often a mesh::Mesh).

template<std::floating_point T>
struct PointOwnershipData
#include <utils.h>

Information on the ownership of points distributed across processes.

Template Parameters:

T – Mesh geometry floating type.

namespace impl

Functions

bool is_leaf(std::array<int, 2> bbox)

Check whether bounding box is a leaf node.

template<std::floating_point T>
bool point_in_bbox(const std::array<T, 6> &b, std::span<const T, 3> x)

A point x is inside a bounding box b if each component of its coordinates lies within the range [b(0,i), b(1,i)] that defines the bounds of the bounding box, b(0,i) <= x[i] <= b(1,i) for i = 0, 1, 2

template<std::floating_point T>
bool bbox_in_bbox(std::span<const T, 6> a, std::span<const T, 6> b)

A bounding box “a” is contained inside another bounding box “b”, if each of its intervals [a(0,i), a(1,i)] is contained in [b(0,i), b(1,i)], a(0,i) <= b(1, i) and a(1,i) >= b(0, i)

namespace impl_bb

Functions

template<std::floating_point T>
std::array<T, 6> compute_bbox_of_entity(const mesh::Mesh<T> &mesh, int dim, std::int32_t index)
template<std::floating_point T>
std::array<T, 6> compute_bbox_of_bboxes(std::span<const std::pair<std::array<T, 6>, std::int32_t>> leaf_bboxes)
template<std::floating_point T>
std::pair<std::vector<std::int32_t>, std::vector<T>> build_from_leaf(std::vector<std::pair<std::array<T, 6>, std::int32_t>> &leaf_bboxes)
namespace impl_gjk

Functions

template<std::floating_point T>
std::pair<std::vector<T>, std::array<T, 3>> nearest_simplex(std::span<const T> s)

Find the resulting sub-simplex of the input simplex which is nearest to the origin. Also, return the shortest vector from the origin to the resulting simplex.

template<std::floating_point T>
std::array<T, 3> support(std::span<const T> bd, std::array<T, 3> v)

‘support’ function, finds point p in bd which maximises p.v