Method BoundingBoxTree

cpp/dolfinx/geometry/BoundingBoxTree.h:234–284

Constructor @param[in] mesh Mesh for building the bounding box tree. @param[in] tdim Topological dimension of the mesh entities to build the bounding box tree for. @param[in] padding Value to pad (extend) the the bounding box of each entity by. @param[in] entities List of entity indices (local to process) to compute the bounding box for. If `std::nullopt`, the bounding box tree is computed for all

  /// compute the bounding box for. If `std::nullopt`, the bounding box tree is
  /// computed for all local entities (including ghosts) of the given `tdim`.
  BoundingBoxTree(const mesh::Mesh<T>& mesh, int tdim, double padding,
                  std::optional<std::span<const std::int32_t>> entities
                  = std::nullopt)
      : _tdim(tdim)
  {
    // Initialize entities of given dimension if they don't exist
    mesh.topology_mutable()->create_entities(tdim);

    // Get input entities. If not provided, get all local entities of the given
    // dimension (including ghosts)
    std::span<const std::int32_t> entities_span;
    std::optional<std::vector<std::int32_t>> local_range(std::nullopt);
    if (entities)
      entities_span = entities.value();
    else
    {
      local_range.emplace(range(*mesh.topology_mutable(), tdim));
      entities_span = std::span<const std::int32_t>(local_range->data(),
                                                    local_range->size());
    }

    if (tdim < 0 or tdim > mesh.topology()->dim())
    {
      throw std::runtime_error(
          "Dimension must be non-negative and less than or "
          "equal to the topological dimension of the mesh");
    }

    mesh.topology_mutable()->create_connectivity(tdim, mesh.topology()->dim());

    // Create bounding boxes for all mesh entities (leaves)
    std::vector<std::pair<std::array<T, 6>, std::int32_t>> leaf_bboxes;
    leaf_bboxes.reserve(entities_span.size());
    for (std::int32_t e : entities_span)
    {
      std::array<T, 6> b = impl_bb::compute_bbox_of_entity(mesh, tdim, e);
      std::transform(b.cbegin(), std::next(b.cbegin(), 3), b.begin(),
                     [padding](auto x) { return x - padding; });
      std::transform(std::next(b.begin(), 3), b.end(), std::next(b.begin(), 3),
                     [padding](auto x) { return x + padding; });
      leaf_bboxes.emplace_back(b, e);
    }

    // Recursively build the bounding box tree from the leaves
    if (!leaf_bboxes.empty())
      std::tie(_bboxes, _bbox_coordinates)
          = impl_bb::build_from_leaf(leaf_bboxes);

    spdlog::info("Computed bounding box tree with {} nodes for {} entities",
                 num_bboxes(), entities_span.size());
  }

  /// Constructor
  /// @param[in] points Cloud of points, with associated