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.

Note

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.

../../../../_images/pic.png

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"

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

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.

  typedef axom::primal::Point<int, DIM> GridCell;

  typedef axom::quest::quest_point_in_cell_mfem_tag mesh_tag;
  typedef axom::quest::PointInCellTraits<mesh_tag> MeshTraits;

  typedef axom::quest::PointInCell<mesh_tag> PointInCellType;

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

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

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.

      int idx = spatialIndex.locatePoint(queryPoint.data(), isoPar.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).