Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Mesh Traversal #1377

Closed
mariuszhermansdorfer opened this issue Jun 29, 2023 · 18 comments
Closed

Mesh Traversal #1377

mariuszhermansdorfer opened this issue Jun 29, 2023 · 18 comments

Comments

@mariuszhermansdorfer
Copy link

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?

    MRMESH_API std::optional<MeshIntersectionResult> rayMeshIntersect( const MeshPart& meshPart, const Line3f& line,
    float rayStart = 0.0f, float rayEnd = FLT_MAX, const IntersectionPrecomputes<float>* prec = nullptr, bool closestIntersect = true );

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

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

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

@Grantim
Copy link
Contributor

Grantim commented Jun 29, 2023

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()

image
image

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 ) }; }
  1. 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
image
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 );
  1. 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<EdgeLoop> findLeftBoundary( const MeshTopology & topology, const FaceBitSet * region = nullptr );
[[nodiscard]] inline std::vector<EdgeLoop> 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<EdgeLoop> findRightBoundary( const MeshTopology & topology, const FaceBitSet * region = nullptr );
[[nodiscard]] inline std::vector<EdgeLoop> findRightBoundary( const MeshTopology & topology, const FaceBitSet & region )
    { return findRightBoundary( topology, &region ); }
  1. You can have a look at MRExpandShrink.h
// 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
Copy link
Author

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?

image

@Grantim
Copy link
Contributor

Grantim commented Jun 29, 2023

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
Copy link
Author

/// 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:

/// a function that maps an edge to a floating-point value
using EdgeMetric = std::function<float( EdgeId )>;

@Grantim
Copy link
Contributor

Grantim commented Jun 30, 2023

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 = {} );

image

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
Copy link
Author

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
Copy link
Contributor

Grantim commented Jun 30, 2023

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
Copy link
Author

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
Copy link
Contributor

Grantim commented Jun 30, 2023

image
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
Copy link
Author

Gotcha. Thanks again for a clear explanation!

@Grantim Grantim pinned this issue Jul 4, 2023
@Grantim Grantim closed this as completed Jul 4, 2023
@Grantim
Copy link
Contributor

Grantim commented Jul 4, 2023

Closing now, please feel free to reopen if needed

@mariuszhermansdorfer
Copy link
Author

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:

2023-07-09.11-08-10.mp4

@Fedr Fedr reopened this Jul 9, 2023
@Grantim
Copy link
Contributor

Grantim commented Jul 9, 2023

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
Copy link
Author

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

@Grantim
Copy link
Contributor

Grantim commented Jul 11, 2023

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

@Grantim Grantim closed this as completed Jul 11, 2023
@xiaodongdong101
Copy link

if I have two contours, how should I delete the faces between the contours?
7e6c6043142dcff3b56828a0d0188ac
the face between two contours
I found that the algorithm does not seem to be submitted to this problem

@Grantim
Copy link
Contributor

Grantim commented Aug 25, 2023

You need these contours to be oriented this way
image
so the area inside will be to left from both of them

// 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 );

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

@xiaodongdong101
Copy link

Thanks a lot.

@oitel oitel unpinned this issue Jan 23, 2024
@Fedr Fedr pinned this issue Jan 30, 2024
@egrebenchenko egrebenchenko unpinned this issue Apr 9, 2024
@Grantim Grantim pinned this issue Apr 24, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants