Point-in-cell query

The point-in-cell query is particularly useful with high-order meshes. It takes a 2D quad or 3D hex mesh and locates a query point in that mesh, reporting both the cell containing the point and the isoparametric coordinates of the query point within the cell.


If a query point lies on the boundary in more than one cell, the point-in-cell query will return the cell with the lowest index.

If the point lies outside of any cell, the query returns the special value quest::PointInCellTraits<mesh_tag>::NO_CELL or using the MeshTraits typedef, MeshTraits::NO_CELL.


Fig. 28 Point-in-cell query, identifying the cell that contains a physical point and finding the point’s isoparametric coordinates within the cell.

The point-in-cell query is currently implemented using MFEM, so to use this query Axom must be compiled with MFEM as a dependency. The following example (from <axom>/src/tests/quest_point_in_cell_mfem.cpp) shows the use of the query, beginning with inclusion of required header files.

#include "axom/quest/PointInCell.hpp"

  #include "axom/quest/detail/PointInCellMeshWrapper_mfem.hpp"
  #error "Quest's PointInCell tests on mfem meshes requires mfem library."

We use typedefs for the sake of brevity. The class is templated on a struct (provided by Quest, referred to as mesh_tag) that is used to select MFEM as the backend implementation for point location. To implement a new backend, a developer must declare a new (empty) struct and provide a specialization of the PointInCellTraits and PointInCellMeshWrapper templated on the new struct that fulfill the interface documented for those classes.

  using mesh_tag = axom::quest::quest_point_in_cell_mfem_tag;
  using PointInCellType = axom::quest::PointInCell<mesh_tag, ExecSpace>;
  using MeshTraits = typename PointInCellType::MeshTraits;
  using IndexType = typename PointInCellType::IndexType;

Instantiate the object using an MFEM mesh and a spatial index 25 bins on a side.

    PointInCellType spatialIndex(m_mesh, GridCell(25).data(), m_EPS, m_allocatorID);

Test a query point. Here idx receives the ID of the cell that contains queryPoint and isoPar is a primal::Point that receives the isoparametric coordinates of queryPoint within cell idx.

    spatialIndex.locatePoints(pts, outCellIds.data(), outIsopar.data());

From cell ID and isoparametric coordinates, reconstruct the input physical coordinates.

        SpacePt untransformPt;
        spatialIndex.reconstructPoint(idx, isoPar.data(), untransformPt.data());

The destructor of the index object cleans up resources used (in this case, when the variable spatialIndex goes out of scope).