Mesh Traversal

[mariuszhermansdorfer]

I'm trying to gain a better understanding of how to navigate the mesh topology. Could you please point me in the right direction when it comes to the following operations?

1. Face/Edge/Vertex Selection Given a ray, how can I select the intersecting mesh element? The function below returns a MeshTriPoint, is there a way to retrieve the corresponding Face, Edge or Vertex? https://github.com/MeshInspector/MeshLib/blob/20f169ba31752bc00f7f7997c82e7ad4e7e0081f/source/MRMesh/MRMeshIntersect.h#L30-L31

2. Internal Face Selection Given a closed edge loop (cyan), select all internal faces (yellow):

3. Hole & Boundary Selection Given a single edge (cyan), select the entire edge loop forming the hole boundary (yellow). Same applies to external boundaries:

4. Expanding/Shrinking Selection Given an arbitrary amount of selected faces expand or shrink the selection to include the neighboring faces:

[Grantim]

Hello!

1. MeshTriPoint contains EdgeId e

   FaceId intersectionFace = mesh.topology.left( meshTriPoint.e ); // on this face ray intersects mesh
   std::optional<MeshEdgePoint> interEdge = meshTriPoint.onEdge( mesh.topology ); // if ray intersects mesh exactly on edge optional is not null
   VertId interVert = meshTriPoint.inVertex( mesh.topology ); // if ray intersects mesh exactly in vertex VertId is valid()

   

Basic navigation:

// left face
assert( mesh.topology.left( 0_e ) == 0_f  );
assert( mesh.topology.left( 2_e ) == 0_f  );
assert( mesh.topology.left( 4_e ) == 0_f  );

// change edge direction
assert( 0_e.sym() == 1_e && 1_e.sym() == 0_e );
assert( 2_e.sym() == 3_e && 3_e.sym() == 2_e );
assert( 4_e.sym() == 5_e && 5_e.sym() == 4_e );

// vertices
assert( mesh.topology.org( 0_e ) == 0_v ); 
assert( mesh.topology.org( 5_e ) == 0_v );
assert( mesh.topology.dest( 4_e ) == 0_v );
assert( mesh.topology.dest( 1_e ) == 0_v );

assert( mesh.topology.org( 2_e ) == 1_v );
assert( mesh.topology.org( 1_e ) == 1_v );
assert( mesh.topology.dest( 0_e ) == 1_v );
assert( mesh.topology.dest( 3_e ) == 1_v );

assert( mesh.topology.org( 4_e ) == 2_v );
assert( mesh.topology.org( 3_e ) == 2_v );
assert( mesh.topology.dest( 2_e ) == 2_v );
assert( mesh.topology.dest( 5_e ) == 2_v );

// edge rings
assert( mesh.topology.next( 0_e ) == 5_e );
assert( mesh.topology.next( 2_e ) == 1_e );
assert( mesh.topology.next( 4_e ) == 3_e );

assert( mesh.topology.prev( 1_e ) == 2_e );
assert( mesh.topology.prev( 3_e ) == 4_e );
assert( mesh.topology.prev( 5_e ) == 0_e );

Loops:

// to iterate over all edges with same origin vertex  as firstEdge (INCLUDING firstEdge)
// for ( Edge e : orgRing( topology, firstEdge ) ) ...
inline IteratorRange<OrgRingIterator> orgRing( const MeshTopology & topology, EdgeId edge )
    { return { OrgRingIterator( topology, edge, edge.valid() ), OrgRingIterator( topology, edge, false ) }; }
inline IteratorRange<OrgRingIterator> orgRing( const MeshTopology & topology, VertId v )
    { return orgRing( topology, topology.edgeWithOrg( v ) ); }

// to iterate over all edges with same origin vertex as firstEdge (EXCLUDING firstEdge)
// for ( Edge e : orgRing0( topology, firstEdge ) ) ...
inline IteratorRange<OrgRingIterator> orgRing0( const MeshTopology & topology, EdgeId edge )
    { return { ++OrgRingIterator( topology, edge, true ), OrgRingIterator( topology, edge, false ) }; }

// to iterate over all edges with same left face as firstEdge (INCLUDING firstEdge)
// for ( Edge e : leftRing( topology, firstEdge ) ) ...
inline IteratorRange<LeftRingIterator> leftRing( const MeshTopology & topology, EdgeId edge )
    { return { LeftRingIterator( topology, edge, edge.valid() ), LeftRingIterator( topology, edge, false ) }; }
inline IteratorRange<LeftRingIterator> leftRing( const MeshTopology & topology, FaceId f )
    { return leftRing( topology, topology.edgeWithLeft( f ) ); }

// to iterate over all edges with same left face as firstEdge (EXCLUDING firstEdge)
// for ( Edge e : leftRing0( topology, firstEdge ) ) ...
inline IteratorRange<LeftRingIterator> leftRing0( const MeshTopology & topology, EdgeId edge )
    { return { ++LeftRingIterator( topology, edge, true ), LeftRingIterator( topology, edge, false ) }; }

2. If cyan loop has yellow region to the left you can use:

   // fill region located to the left from given edges
   MRMESH_API FaceBitSet fillContourLeft( const MeshTopology & topology, const EdgePath & contour );
   MRMESH_API FaceBitSet fillContourLeft( const MeshTopology & topology, const std::vector<EdgePath> & contours );

   otherwise you need to reverse loop first

   /// reverses the order of edges and flips each edge orientation, thus
   /// making the opposite directed edge path
   MRMESH_API void reverse( EdgePath & path );
   /// reverse every path in the vector
   MRMESH_API void reverse( std::vector<EdgePath> & paths );

if your mehs has tonnel you can use

/**
 * \brief Fills region located to the left from given contour, by minimizing the sum of metric over the boundary
 * \ingroup MeshSegmentationGroup
 */
MRMESH_API FaceBitSet fillContourLeftByGraphCut( const MeshTopology & topology, const EdgePath & contour,
    const EdgeMetric & metric );

/**
 * \brief Fills region located to the left from given contours, by minimizing the sum of metric over the boundary
 * \ingroup MeshSegmentationGroup
 */
MRMESH_API FaceBitSet fillContourLeftByGraphCut( const MeshTopology & topology, const std::vector<EdgePath> & contours,
    const EdgeMetric & metric );

3. We have some functions for this:

   
   // MeshTopology:
   /// returns closed loop of boundary edges starting from given boundary edge, 
   /// which has region face to the right and does not have valid or in-region left face;
   /// unlike MR::trackRegionBoundaryLoop this method returns loops in opposite orientation
   [[deprecated( "use trackRightBoundaryLoop(...) instead" )]]
   [[nodiscard]] MRMESH_API EdgeLoop trackBoundaryLoop( EdgeId e0, const FaceBitSet * region = nullptr ) const;
   /// returns all boundary loops, where each edge has region face to the right and does not have valid or in-region left face;
   /// unlike MR::findRegionBoundary this method returns loops in opposite orientation
   [[deprecated( "use findRightBoundary(...) instead" )]]
   [[nodiscard]] MRMESH_API std::vector<EdgeLoop> findBoundary( const FaceBitSet * region = nullptr ) const;
   /// returns one edge with no valid left face for every boundary in the mesh
   [[nodiscard]] MRMESH_API std::vector<EdgeId> findHoleRepresentiveEdges() const;

// MRRegionBoundary.h: // returns closed loop of region boundary starting from given region boundary edge (region faces on the left, and not-region faces or holes on the right); // if more than two boundary edges connect in one vertex, then the function makes the most abrupt turn to right [[nodiscard]] MRMESH_API EdgeLoop trackLeftBoundaryLoop( const MeshTopology & topology, EdgeId e0, const FaceBitSet * region = nullptr ); [[nodiscard]] inline EdgeLoop trackLeftBoundaryLoop( const MeshTopology & topology, const FaceBitSet & region, EdgeId e0 ) { return trackLeftBoundaryLoop( topology, e0, &region ); }

// returns closed loop of region boundary starting from given region boundary edge (region faces on the right, and not-region faces or holes on the left); // if more than two boundary edges connect in one vertex, then the function makes the most abrupt turn to left [[nodiscard]] MRMESH_API EdgeLoop trackRightBoundaryLoop( const MeshTopology & topology, EdgeId e0, const FaceBitSet * region = nullptr ); [[nodiscard]] inline EdgeLoop trackRightBoundaryLoop( const MeshTopology & topology, const FaceBitSet & region, EdgeId e0 ) { return trackRightBoundaryLoop( topology, e0, &region ); }

// returns all region boundary loops; // every loop has region faces on the left, and not-region faces or holes on the right [[nodiscard]] MRMESH_API std::vector findLeftBoundary( const MeshTopology & topology, const FaceBitSet * region = nullptr ); [[nodiscard]] inline std::vector findLeftBoundary( const MeshTopology & topology, const FaceBitSet & region ) { return findLeftBoundary( topology, &region ); }

// returns all region boundary loops; // every loop has region faces on the right, and not-region faces or holes on the left [[nodiscard]] MRMESH_API std::vector findRightBoundary( const MeshTopology & topology, const FaceBitSet * region = nullptr ); [[nodiscard]] inline std::vector findRightBoundary( const MeshTopology & topology, const FaceBitSet & region ) { return findRightBoundary( topology, &region ); }

4. You can have a look at `MRExpandShrink.h`
```c++
// adds to the region all faces within given number of hops (stars) from the initial region boundary
MRMESH_API void expand( const MeshTopology & topology, FaceBitSet & region, int hops = 1 );
// returns the region of all faces within given number of hops (stars) from the initial face
[[nodiscard]] MRMESH_API FaceBitSet expand( const MeshTopology & topology, FaceId f, int hops );

// adds to the region all vertices within given number of hops (stars) from the initial region boundary
MRMESH_API void expand( const MeshTopology & topology, VertBitSet & region, int hops = 1 );
// returns the region of all vertices within given number of hops (stars) from the initial vertex
[[nodiscard]] MRMESH_API VertBitSet expand( const MeshTopology & topology, VertId v, int hops );

// removes from the region all faces within given number of hops (stars) from the initial region boundary
MRMESH_API void shrink( const MeshTopology & topology, FaceBitSet & region, int hops = 1 );
// removes from the region all vertices within given number of hops (stars) from the initial region boundary
MRMESH_API void shrink( const MeshTopology & topology, VertBitSet & region, int hops = 1 );

and MREdgePath.h

/// expands the region (of faces or vertices) on given metric value. returns false if callback also returns false
MRMESH_API bool dilateRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, FaceBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool dilateRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, VertBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool dilateRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, UndirectedEdgeBitSet& region, float dilation, ProgressCallback callback = {} );

/// shrinks the region (of faces or vertices) on given metric value. returns false if callback also returns false
MRMESH_API bool erodeRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, FaceBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool erodeRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, VertBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool erodeRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, UndirectedEdgeBitSet& region, float dilation, ProgressCallback callback = {} );

/// expands the region (of faces or vertices) on given value (in meters). returns false if callback also returns false
MRMESH_API bool dilateRegion( const Mesh& mesh, FaceBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool dilateRegion( const Mesh& mesh, VertBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool dilateRegion( const Mesh& mesh, UndirectedEdgeBitSet& region, float dilation, ProgressCallback callback = {} );

/// shrinks the region (of faces or vertices) on given value (in meters). returns false if callback also returns false
MRMESH_API bool erodeRegion( const Mesh& mesh, FaceBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool erodeRegion( const Mesh& mesh, VertBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool erodeRegion( const Mesh& mesh, UndirectedEdgeBitSet& region, float dilation, ProgressCallback callback = {} );

Hope it helps!

[mariuszhermansdorfer]

Thanks @Grantim, this is all super useful!

Quick question regarding:

MeshTriPoint contains EdgeId e

Which of the below edges would belong to the green hit point? Is it always the closest or a random assignment?

[Grantim]

It is not guaranteed to be closest, as far as MeshTriPoint also has

    /// barycentric coordinates
    /// \details a in [0,1], a=0 => point is on next( e ) edge, a=1 => point is in dest( e )
    /// b in [0,1], b=0 => point is on e edge, b=1 => point is in dest( next( e ) )
    /// a+b in [0,1], a+b=0 => point is in org( e ), a+b=1 => point is on prev( e.sym() ) edge
    TriPointf bary;

it can be represented by each of these edges.

P.S. There are two funcitons in MeshTopology that can be helpful:

    /// for all valid faces this vector contains an edge with that face at left
    [[nodiscard]] const Vector<EdgeId, FaceId> & edgePerFace() const { return edgePerFace_; }

    /// for all valid vertices this vector contains an edge with the origin there
    [[nodiscard]] const Vector<EdgeId, VertId> & edgePerVertex() const { return edgePerVertex_; }

[mariuszhermansdorfer]

/// expands the region (of faces or vertices) on given metric value. returns false if callback also returns false
MRMESH_API bool dilateRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, FaceBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool dilateRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, VertBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool dilateRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, UndirectedEdgeBitSet& region, float dilation, ProgressCallback callback = {} );

/// shrinks the region (of faces or vertices) on given metric value. returns false if callback also returns false
MRMESH_API bool erodeRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, FaceBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool erodeRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, VertBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool erodeRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, UndirectedEdgeBitSet& region, float dilation, ProgressCallback callback = {} );

/// expands the region (of faces or vertices) on given value (in meters). returns false if callback also returns false
MRMESH_API bool dilateRegion( const Mesh& mesh, FaceBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool dilateRegion( const Mesh& mesh, VertBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool dilateRegion( const Mesh& mesh, UndirectedEdgeBitSet& region, float dilation, ProgressCallback callback = {} );

/// shrinks the region (of faces or vertices) on given value (in meters). returns false if callback also returns false
MRMESH_API bool erodeRegion( const Mesh& mesh, FaceBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool erodeRegion( const Mesh& mesh, VertBitSet& region, float dilation, ProgressCallback callback = {} );
MRMESH_API bool erodeRegion( const Mesh& mesh, UndirectedEdgeBitSet& region, float dilation, ProgressCallback callback = {} );

One more question regarding these functions. What is the purpose of EdgeMetric? I can see its description in the header file but still don’t understand the use case:

https://github.com/MeshInspector/MeshLib/blob/18e2196a2ad61e347a1e29a519eb9e9c036cdba9/source/MRMesh/MREdgeMetric.h#L15-L16

[Grantim]

Basically EdgeMetric is needed to calculate distance on edge-based operation.

Example of

/// expands the region (of faces or vertices) on given metric value. returns false if callback also returns false
MRMESH_API bool dilateRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, VertBitSet& region, float dilation, ProgressCallback callback = {} );

lets assume that we start in red vertex: we use

/// returns edge's length as a metric
[[nodiscard]] MRMESH_API EdgeMetric edgeLengthMetric( const Mesh & mesh );

with dilation equal to green circle radius. In this case all green vertices will be added to region (red vertex initialy).

Otherwise if we use

/// metric returning 1 for every edge
[[nodiscard]] MRMESH_API EdgeMetric identityMetric();

with dilation equal to 1, we will get all green and black vertices added to region (red vertex initialy). (beacuse length (metric) of each edge is equal to 1 in this case).

So EdgeMetric allows you to control geometry properties of expansion and also in some other algorithms.

---

Another example:

/// builds shortest path in given metric from start to finish vertices; if no path can be found then empty path is returned
[[nodiscard]] MRMESH_API EdgePath buildSmallestMetricPath( const MeshTopology & topology, const EdgeMetric & metric,
    VertId start, VertId finish, float maxPathMetric = FLT_MAX );

If we use here edgeLengthMetric result will be path with the smallest length, if use identityMetric result will be path with minimum number of edges.

[mariuszhermansdorfer]

Makes sense. To make sure I understand it correctly:

MRMESH_API bool dilateRegion( const Mesh& mesh, VertBitSet& region, float dilation, ProgressCallback callback = {} );

is equivalent to this:

[[nodiscard]] MRMESH_API EdgeMetric edgeLengthMetric( const Mesh & mesh );
MRMESH_API bool dilateRegionByMetric( const MeshTopology& topology, const EdgeMetric& metric, VertBitSet& region, float dilation, ProgressCallback callback = {} );

[Grantim]

Yes it is right

bool dilateRegion( const Mesh& mesh, VertBitSet& region, float dilation, ProgressCallback callback )
{
    return dilateRegionByMetric( mesh.topology, edgeLengthMetric( mesh ), region, dilation, callback );
}

[mariuszhermansdorfer]

Awesome! Thanks a lot, now I have a much better understanding of how to navigate the mesh.

As a side note, I think there is a minor error in your first reply. Shouldn't this:

assert( mesh.topology.next( 0_e ) == 5_e );
assert( mesh.topology.next( 2_e ) == 1_e );
assert( mesh.topology.next( 4_e ) == 3_e );

be corrected to this?

assert( mesh.topology.next( 0_e ) == 2_e );
assert( mesh.topology.next( 2_e ) == 4_e );
assert( mesh.topology.next( 4_e ) == 0_e );

Maybe you could edit your post to keep it consistent for future reference?

[Grantim]

This is corerect: next operation is orgRing iterator step next edge is edge to the left from origin vertex (next is rotational operation)

assert( mesh.topology.next( 0_e ) == 5_e );
assert( mesh.topology.next( 2_e ) == 1_e );
assert( mesh.topology.next( 4_e ) == 3_e );

to get loop like 0_e -> 2_e -> 4_e one should use leftRing iterator

assert( mesh.topology.prev( 0_e.sym() ) == 2_e );
assert( mesh.topology.prev( 2_e.sym() ) == 4_e );
assert( mesh.topology.prev( 4_e.sym() ) == 0_e );

[mariuszhermansdorfer]

Gotcha. Thanks again for a clear explanation!

[Grantim]

Closing now, please feel free to reopen if needed

[mariuszhermansdorfer]

3. If cyan loop has yellow region to the left you can use:

// fill region located to the left from given edges
MRMESH_API FaceBitSet fillContourLeft( const MeshTopology & topology, const EdgePath & contour );
MRMESH_API FaceBitSet fillContourLeft( const MeshTopology & topology, const std::vector<EdgePath> & contours );

Is there a robust way of checking the direction of an EdgeLoop? I'm cutting holes in meshes with a polyline using the logic from #1294 and would like to make sure that I always delete the interior faces no matter the direction of the initial polyline. In the below video you can see how flipping its direction changes the output dramatically:

https://github.com/MeshInspector/MeshLib/assets/49192999/53aa8d22-a4c1-40af-ab63-2fbc80f36f2b

[Grantim]

One way is to calculate normal of contour and comare it with surface normal

const Vector3f cSurfaceNorm = Vector3f::plusZ();
Vector3f contourNormal;
for ( auto e : contour )
    contourNormal += cross( mesh.orgPnt( e ), mesh.destPnt( e ) );

if ( dot( contourNormal, cSurfaceNorm  ) < 0.0f )
    reverse( contour );

this method should work in most cases, but because it based on geometry (which can be degeneratre it can fail in some rare cases)

Other, more robust method:

auto insideRegion = fillContourLeft( mesh.topology, contour );
if ( ( mesh.topology.findBoundaryFaces() & insideRegion ).any() )
    insideRegion = mesh.topology.getValidFaces() - insideRegion;

---

Cannot say which method is faster, but second should always work (as long as internal is determined by cofiguration, e.g. contour is closed loop fully inside base mesh)

[mariuszhermansdorfer]

Thanks @Grantim, the first method is more suitable for my applications. It works like a charm!

[Grantim]

Closing this issue, if you have any related questions please reopen it

[xiaodongdong101]

if I have two contours, how should I delete the faces between the contours?

the face between two contours I found that the algorithm does not seem to be submitted to this problem

[Grantim]

You need these contours to be oriented this way so the area inside will be to left from both of them https://github.com/MeshInspector/MeshLib/blob/ae1704c02fca3c88361cd777af42cb7f01da5d9c/source/MRMesh/MRFillContour.h#L8-L10

mesh.topology.deleteFaces( fillContourLeft( mesh.topology, contours ) );
mesh.invalidateCaches(); // important to call after direct changing of `MeshTopology`

[xiaodongdong101]

Thanks a lot.