Geometry (dolfinx::geometry)

namespace geometry

Geometry data structures and algorithms.

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

Functions

std::array<double, 3> compute_distance_gjk(const std::span<const double> &p, const std::span<const double> &q)

Calculate the distance between two convex bodies p and q, each defined by a set of points, using 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

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

Create a bounding box tree for a subset of entities (local to process) based on the entity midpoints.

Parameters
  • mesh[in] The mesh

  • tdim[in] The topological dimension of the entity

  • entity_indices[in] List of local entity indices

Returns

Bounding box tree for midpoints of mesh entities

std::vector<std::array<int, 2>> compute_collisions(const BoundingBoxTree &tree0, const BoundingBoxTree &tree1)

Compute all collisions between two BoundingBoxTrees (local to process)

Parameters
Returns

List of pairs of intersecting box indices from each tree

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

Compute all collisions between bounding boxes and for a set of points.

Parameters
  • tree[in] The bounding box tree

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

Returns

An adjacency list where the ith node corresponds to the bounding box leaves that contain the ith point

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

Compute closest mesh entity to a point.

Note

Returns 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

Index of the closest mesh entity to a point. The ith entry is the index of the closest entity to the ith input point.

double compute_squared_distance_bbox(const std::array<std::array<double, 3>, 2> &b, const std::array<double, 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.

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

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

Parameters
  • mesh[in] The mesh

  • dim[in] The topological dimension of the mesh entity

  • entities[in] The list of entities (local to process)

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

std::vector<double> squared_distance(const mesh::Mesh &mesh, int dim, const std::span<const std::int32_t> &entities, const std::span<const double> &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]

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

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

Note

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

Note

There may be nodes with no entries in the adjacency list

Parameters
  • mesh[in] The mesh

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

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

Returns

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

class BoundingBoxTree
#include <BoundingBoxTree.h>

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