TriangleManifold Class Reference

Utility for querying point containment against a closed triangulated surface mesh. More...

#include <TriangleManifold.h>

Public Member Functions
	TriangleManifold (MeshBase &mesh, const Real surface_tolerance)
	Build a manifold classifier from a prepared surface mesh. More...
bool	contains (const Point &point) const
const libMesh::BoundingBox &	boundingBox () const
std::size_t	numTriangles () const

Private Types
enum	RayIntersection { RayIntersection::Miss, RayIntersection::Hit, RayIntersection::Ambiguous }
	Result of intersecting the positive x-direction ray with a triangle. More...

Private Member Functions
void	finalize ()
	Complete post-parse validation and acceleration-structure setup. More...
void	buildCandidateGrid ()
	Build the yz-plane lookup grid used to accelerate +x ray queries. More...
bool	pointInsideBoundingBox (const Point &point) const
	Cheap global bounding-box rejection for containment queries. More...
bool	pointOnSurface (const Point &point) const
	Detect whether a query point lies on or extremely near the manifold surface. More...
RayIntersection	rayIntersectsTriangle (const Point &point, const libMesh::Elem &tri) const
	Intersect a positive x-direction ray with a single triangle. More...
bool	containsBySolidAngle (const Point &point) const
	Robust fallback containment query based on accumulated solid angle. More...
std::vector< dof_id_type >	rayCandidates (const Point &point) const
	Get the subset of triangles whose yz extents may intersect the query ray. More...

Private Attributes
std::size_t	_num_y_cells = 1
	Number of yz-grid bins in the y direction. More...
std::size_t	_num_z_cells = 1
	Number of yz-grid bins in the z direction. More...
Real	_y_min = 0.0
	Minimum global y coordinate used to map query points into yz-grid bins. More...
Real	_z_min = 0.0
	Minimum global z coordinate used to map query points into yz-grid bins. More...
Real	_y_cell_size = 1.0
	Width of one yz-grid cell in the y direction. More...
Real	_z_cell_size = 1.0
	Width of one yz-grid cell in the z direction. More...
std::unordered_map< dof_id_type, std::vector< dof_id_type > >	_ray_grid
	Lookup from packed yz-grid cell index to triangles that could intersect the +x query ray. More...
MeshBase &	_mesh
const Real	_surface_tolerance
	Absolute tolerance used throughout validation and geometric classification. More...
const libMesh::BoundingBox	_bounding_box
	Global bounding box of the transformed manifold. More...
const std::unique_ptr< libMesh::PointLocatorBase >	_point_locator
	Pre-built point locator for fast proximity-to-surface detection. More...

Detailed Description

Utility for querying point containment against a closed triangulated surface mesh.

The class takes ownership of a reference to a prepared 2D surface mesh, validates that it forms a closed 2-manifold (every triangle has exactly three neighbors, all elements are Tri3, and the mesh is consistently oriented), builds a lightweight yz-plane acceleration grid, and exposes contains() for point-in-solid queries.

Containment is resolved in three stages:

1. Cheap global bounding-box rejection.
2. Near-surface detection via a pre-built point locator (points within surface_tolerance of the mesh surface are treated as inside).
3. Odd/even parity counting on a fixed +x ray, with automatic fallback to a solid-angle accumulation test when the ray grazes a triangle edge or vertex.

The referenced mesh must outlive this object. Any geometric transforms (scale, rotation, translation) should be applied to the mesh before constructing a TriangleManifold.

Definition at line 44 of file TriangleManifold.h.

Member Enumeration Documentation

RayIntersection

enum TriangleManifold::RayIntersection

strongprivate

Result of intersecting the positive x-direction ray with a triangle.

Ambiguous is returned when the hit is too close to an edge, vertex, or the ray origin. In that case we abandon parity counting and fall back to the more expensive but robust solid-angle test.

Enumerator
Miss
Hit
Ambiguous

Definition at line 81 of file TriangleManifold.h.

  {
    Miss,
    Hit,
    Ambiguous
  };

Constructor & Destructor Documentation

TriangleManifold()

TriangleManifold::TriangleManifold	(	MeshBase &	mesh,
		const Real	surface_tolerance
	)

Build a manifold classifier from a prepared surface mesh.

Parameters

mesh	Serialized 2D surface mesh that defines the closed manifold. Must outlive this object. Any desired transforms should already be applied to the mesh.
surface_tolerance	Absolute tolerance used for manifold validation and near-surface classification. Choose this relative to the mesh length scale and expected coordinate noise from the export pipeline.

Definition at line 56 of file TriangleManifold.C.

  : _mesh(mesh),
    _surface_tolerance(surface_tolerance),
    _bounding_box(MeshTools::create_bounding_box(_mesh)),
    _point_locator(_mesh.sub_point_locator())
{
  mooseAssert(_surface_tolerance > 0.0, "surface_tolerance must be strictly positive.");
  mooseAssert(mesh.is_serial(), "Input manifold mesh must be serialized.");
  mooseAssert(mesh.mesh_dimension() == 2, "Manifold mesh must be a surface.");

  // Finish topology validation and acceleration-structure setup before queries are allowed.
  finalize();

  _point_locator->set_close_to_point_tol(_surface_tolerance);
}

Member Function Documentation

boundingBox()

const libMesh::BoundingBox& TriangleManifold::boundingBox ( ) const

inline

Returns

The manifold bounding box.

Definition at line 66 of file TriangleManifold.h.

Referenced by buildCandidateGrid(), pointInsideBoundingBox(), and rayCandidates().

{ return _bounding_box; };

buildCandidateGrid()

void TriangleManifold::buildCandidateGrid ( )

private

Build the yz-plane lookup grid used to accelerate +x ray queries.

Definition at line 128 of file TriangleManifold.C.

Referenced by finalize().

{
  // Since every containment ray travels in +x, only y and z are needed to choose candidate
  // triangles for the parity test.
  const auto extent_y =
      std::max(boundingBox().max()(1) - boundingBox().min()(1), _surface_tolerance);
  const auto extent_z =
      std::max(boundingBox().max()(2) - boundingBox().min()(2), _surface_tolerance);

  // Choose a roughly square yz grid scaled by aspect ratio so candidate lists stay short.
  const auto target_cells =
      std::max<dof_id_type>(1, static_cast<dof_id_type>(std::sqrt(numTriangles())));
  const auto aspect = std::sqrt(extent_y / extent_z);

  _num_y_cells = std::max<dof_id_type>(
      1, static_cast<dof_id_type>(std::lround(std::sqrt(target_cells) * aspect)));
  _num_z_cells = std::max<std::size_t>(
      1, static_cast<std::size_t>(std::ceil(static_cast<Real>(target_cells) / _num_y_cells)));

  _y_min = boundingBox().min()(1);
  _z_min = boundingBox().min()(2);
  _y_cell_size = extent_y / _num_y_cells;
  _z_cell_size = extent_z / _num_z_cells;

  for (const auto elem : _mesh.active_element_ptr_range())
  {
    const auto triangle_index = elem->id();
    const auto bbox = elem->loose_bounding_box();

    const auto y_start =
        TriangleManifoldUtils::cellIndex(bbox.min()(1), _y_min, _y_cell_size, _num_y_cells);
    const auto y_stop =
        TriangleManifoldUtils::cellIndex(bbox.max()(1), _y_min, _y_cell_size, _num_y_cells);
    const auto z_start =
        TriangleManifoldUtils::cellIndex(bbox.min()(2), _z_min, _z_cell_size, _num_z_cells);
    const auto z_stop =
        TriangleManifoldUtils::cellIndex(bbox.max()(2), _z_min, _z_cell_size, _num_z_cells);

    // Insert the triangle into every grid cell touched by its yz projection.
    for (const auto iy : make_range(y_start, y_stop + 1))
      for (const auto iz : make_range(z_start, z_stop + 1))
        _ray_grid[TriangleManifoldUtils::packCell(iy, iz)].push_back(triangle_index);
  }
}

contains()

bool TriangleManifold::contains

(

const Point &

point

)

const

Returns

True if the point is inside the manifold or lies on the surface.

Definition at line 73 of file TriangleManifold.C.

Referenced by ManifoldSubdomainGenerator::generate().

{
  // Most points are rejected here before we perform any per-triangle work.
  if (!pointInsideBoundingBox(point))
    return false;

  // By design, near-surface points count as inside for downstream subdomain tagging.
  if (pointOnSurface(point))
    return true;

  // Candidate filtering keeps the parity test from touching every triangle in large surfaces.
  const auto candidates = rayCandidates(point);
  unsigned int num_hits = 0;

  for (const auto triangle_index : candidates)
  {
    const auto tri = _mesh.elem_ptr(triangle_index);
    // Triangles wholly behind the ray origin cannot contribute to the parity count.
    if (tri->loose_bounding_box().max()(0) < point(0) - _surface_tolerance)
      continue;

    switch (rayIntersectsTriangle(point, *tri))
    {
      case RayIntersection::Miss:
        break;
      case RayIntersection::Hit:
        // Standard odd/even counting on a closed surface.
        ++num_hits;
        break;
      case RayIntersection::Ambiguous:
        // Edge and vertex grazing hits are exactly where parity counting becomes brittle.
        return containsBySolidAngle(point);
    }
  }

  return num_hits % 2;
}

containsBySolidAngle()

bool TriangleManifold::containsBySolidAngle ( const Point &  point ) const

private

Robust fallback containment query based on accumulated solid angle.

Definition at line 241 of file TriangleManifold.C.

Referenced by contains().

{
  // For a closed oriented mesh, the total solid angle is approximately +-4\pi inside and 0
  // outside. Taking parity over components handles nested shells cleanly.
  Real total_angle = 0.0;
  for (const auto elem : _mesh.active_element_ptr_range())
    total_angle +=
        geom_utils::solidAngle(point, elem->node_ref(0), elem->node_ref(1), elem->node_ref(2));

  return std::abs(total_angle) > 2.0 * libMesh::pi;
}

finalize()

void TriangleManifold::finalize ( )

private

Complete post-parse validation and acceleration-structure setup.

Definition at line 112 of file TriangleManifold.C.

Referenced by TriangleManifold().

{
  // Validate that the mesh can be used as a manifold
  // We use the same logic as determining if the mesh can the tetrahedralized.
  auto umesh = dynamic_cast<UnstructuredMesh *>(&_mesh);
  TriangleManifoldUtils::SurfaceChecker checker(*umesh);
  auto msg = checker.improveAndValidate();
  if (!msg.empty())
    mooseError(
        "The inputted surface mesh cannot be treated as manifold for the following reasons:\n",
        msg);

  buildCandidateGrid();
}

numTriangles()

std::size_t TriangleManifold::numTriangles ( ) const

inline

Returns

The number of triangles in the loaded manifold.

Definition at line 71 of file TriangleManifold.h.

Referenced by buildCandidateGrid().

{ return _mesh.n_active_elem(); }

pointInsideBoundingBox()

bool TriangleManifold::pointInsideBoundingBox ( const Point &  point ) const

private

Cheap global bounding-box rejection for containment queries.

Definition at line 174 of file TriangleManifold.C.

Referenced by contains().

{
  // Inflate the global box by the tolerance so near-surface points are not rejected too early.
  return point(0) >= boundingBox().min()(0) - _surface_tolerance &&
         point(0) <= boundingBox().max()(0) + _surface_tolerance &&
         point(1) >= boundingBox().min()(1) - _surface_tolerance &&
         point(1) <= boundingBox().max()(1) + _surface_tolerance &&
         point(2) >= boundingBox().min()(2) - _surface_tolerance &&
         point(2) <= boundingBox().max()(2) + _surface_tolerance;
}

pointOnSurface()

bool TriangleManifold::pointOnSurface ( const Point &  point ) const

private

Detect whether a query point lies on or extremely near the manifold surface.

Definition at line 186 of file TriangleManifold.C.

Referenced by contains().

{
  return (*_point_locator)(point) != nullptr;
}

rayCandidates()

std::vector< dof_id_type > TriangleManifold::rayCandidates ( const Point &  point ) const

private

Get the subset of triangles whose yz extents may intersect the query ray.

Definition at line 254 of file TriangleManifold.C.

Referenced by contains().

{
  // If the query is outside the manifold's yz extent, the fixed +x ray cannot hit anything.
  if (point(1) < boundingBox().min()(1) - _surface_tolerance ||
      point(1) > boundingBox().max()(1) + _surface_tolerance ||
      point(2) < boundingBox().min()(2) - _surface_tolerance ||
      point(2) > boundingBox().max()(2) + _surface_tolerance)
    return {};

  const auto y_index =
      TriangleManifoldUtils::cellIndex(point(1), _y_min, _y_cell_size, _num_y_cells);
  const auto z_index =
      TriangleManifoldUtils::cellIndex(point(2), _z_min, _z_cell_size, _num_z_cells);
  const auto it = _ray_grid.find(TriangleManifoldUtils::packCell(y_index, z_index));
  if (it == _ray_grid.end())
    return {};

  // Return by value to keep the helper simple and avoid exposing internal storage.
  return it->second;
}

rayIntersectsTriangle()

TriangleManifold::RayIntersection TriangleManifold::rayIntersectsTriangle ( const Point &  point, const libMesh::Elem &  tri  ) const

private

Intersect a positive x-direction ray with a single triangle.

Definition at line 192 of file TriangleManifold.C.

Referenced by contains().

{
  // This is a fixed-direction Moller-Trumbore style ray/triangle intersection test.
  static const Point direction(1.0, 0.0, 0.0);

  const Point edge1 = tri.node_ref(1) - tri.node_ref(0);
  const Point edge2 = tri.node_ref(2) - tri.node_ref(0);
  const Point h = direction.cross(edge2);
  const Real determinant = edge1 * h;
  const Real characteristic_length = std::max(edge1.norm(), edge2.norm());

  if (std::abs(determinant) <= _surface_tolerance * characteristic_length)
    // Nearly parallel triangles are ignored because they do not provide a stable parity event.
    return RayIntersection::Miss;

  const Real inv_determinant = 1.0 / determinant;
  const Point s = point - tri.node_ref(0);
  const Real u = inv_determinant * (s * h);
  if (u < 0.0 || u > 1.0)
    return RayIntersection::Miss;

  const Point q = s.cross(edge1);
  const Real v = inv_determinant * (direction * q);
  if (v < 0.0 || u + v > 1.0)
    return RayIntersection::Miss;

  const Real t = inv_determinant * (edge2 * q);
  if (t < 0.0)
    // Intersections behind the ray origin do not contribute to +x parity counting.
    return RayIntersection::Miss;
  if (t <= _surface_tolerance)
    // Hits too close to the ray origin are treated as ambiguous boundary situations.
    return RayIntersection::Ambiguous;

  const Point intersection = point + t * direction;
  const auto tolerance_sq = _surface_tolerance * _surface_tolerance;
  if (geom_utils::pointSegmentDistanceSq(intersection, tri.node_ref(0), tri.node_ref(1)) <=
          tolerance_sq ||
      geom_utils::pointSegmentDistanceSq(intersection, tri.node_ref(1), tri.node_ref(2)) <=
          tolerance_sq ||
      geom_utils::pointSegmentDistanceSq(intersection, tri.node_ref(2), tri.node_ref(0)) <=
          tolerance_sq)
    // Edge and vertex hits are where odd/even parity counting is the least reliable.
    return RayIntersection::Ambiguous;

  return RayIntersection::Hit;
}

Member Data Documentation

_bounding_box

const libMesh::BoundingBox TriangleManifold::_bounding_box

private

Global bounding box of the transformed manifold.

Definition at line 136 of file TriangleManifold.h.

Referenced by boundingBox().

_mesh

MeshBase& TriangleManifold::_mesh

private

Definition at line 130 of file TriangleManifold.h.

Referenced by buildCandidateGrid(), contains(), containsBySolidAngle(), finalize(), and numTriangles().

_num_y_cells

std::size_t TriangleManifold::_num_y_cells = 1

private

Number of yz-grid bins in the y direction.

Definition at line 110 of file TriangleManifold.h.

Referenced by buildCandidateGrid(), and rayCandidates().

_num_z_cells

std::size_t TriangleManifold::_num_z_cells = 1

private

Number of yz-grid bins in the z direction.

Definition at line 113 of file TriangleManifold.h.

Referenced by buildCandidateGrid(), and rayCandidates().

_point_locator

const std::unique_ptr<libMesh::PointLocatorBase> TriangleManifold::_point_locator

private

Pre-built point locator for fast proximity-to-surface detection.

Definition at line 139 of file TriangleManifold.h.

Referenced by pointOnSurface(), and TriangleManifold().

_ray_grid

std::unordered_map<dof_id_type, std::vector<dof_id_type> > TriangleManifold::_ray_grid

private

Lookup from packed yz-grid cell index to triangles that could intersect the +x query ray.

Definition at line 128 of file TriangleManifold.h.

Referenced by buildCandidateGrid(), and rayCandidates().

_surface_tolerance

const Real TriangleManifold::_surface_tolerance

private

Absolute tolerance used throughout validation and geometric classification.

Definition at line 133 of file TriangleManifold.h.

Referenced by buildCandidateGrid(), contains(), pointInsideBoundingBox(), rayCandidates(), rayIntersectsTriangle(), and TriangleManifold().

_y_cell_size

Real TriangleManifold::_y_cell_size = 1.0

private

Width of one yz-grid cell in the y direction.

Definition at line 122 of file TriangleManifold.h.

Referenced by buildCandidateGrid(), and rayCandidates().

_y_min

Real TriangleManifold::_y_min = 0.0

private

Minimum global y coordinate used to map query points into yz-grid bins.

Definition at line 116 of file TriangleManifold.h.

Referenced by buildCandidateGrid(), and rayCandidates().

_z_cell_size

Real TriangleManifold::_z_cell_size = 1.0

private

Width of one yz-grid cell in the z direction.

Definition at line 125 of file TriangleManifold.h.

Referenced by buildCandidateGrid(), and rayCandidates().

_z_min

Real TriangleManifold::_z_min = 0.0

private

Minimum global z coordinate used to map query points into yz-grid bins.

Definition at line 119 of file TriangleManifold.h.

Referenced by buildCandidateGrid(), and rayCandidates().

---

The documentation for this class was generated from the following files:

• include/utils/TriangleManifold.h
• src/utils/TriangleManifold.C