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, const BoundingBoxTree<T> &tree, const std::array<T, 3> &point)

Compute the cell 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.

Parameters:

  • mesh – [in] The mesh

  • tree – [in] The bounding box tree

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

Returns:

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

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>
std::tuple<std::vector<std::int32_t>, std::vector<std::int32_t>, std::vector<T>, std::vector<std::int32_t>> determine_point_ownership(const mesh::Mesh<T> &mesh, std::span<const T> points)

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

Parameters:

  • mesh – [in] The mesh

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

Returns:

Quadratuplet (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).

namespace impl

Functions

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

Check whether bounding box is a leaf node.

template<std::floating_point T>
constexpr 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>
constexpr 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