A collection of mesh (and polygon soup) processing functions. More...

#include <easy3d/algo_ext/surfacer.h>

Public Types
typedef std::vector< int >	Polygon
	A polygon represented by a list of vertex indices.

typedef std::vector< vec3 >	Polyline

Static Public Member Functions
Orientation and stitching
static int	stitch_borders (SurfaceMesh *mesh)
	Stitches together border halfedges in a polygon mesh. More...

static void	merge_reversible_connected_components (SurfaceMesh *mesh)
	Reverses the connected components having incompatible boundary cycles that could be merged if their orientation were made compatible, and stitches them. Connected components are examined by increasing number of faces. More...

static bool	orient_and_stitch_polygon_soup (SurfaceMesh *mesh)
	Tries to consistently orient and stitch a mesh (treated as a polygon soup). More...

static void	orient_closed_triangle_mesh (SurfaceMesh *mesh)
	Makes each connected component of a closed triangle surface mesh inward or outward oriented. More...

static bool	orient_and_stitch_polygon_soup (std::vector< vec3 > &points, std::vector< Polygon > &polygons)
	Tries to consistently orient and stitch a polygon soup. More...

static void	repair_polygon_soup (std::vector< vec3 > &points, std::vector< Polygon > &polygons)
	Repairs a given polygon soup through various repairing operations. More...

static void	repair_polygon_soup (SurfaceMesh *mesh)
	Repairs a given polygon mesh through various repairing operations. More...

Degenerate, overlapping, and duplicate faces removal
static unsigned int	remove_degenerate_faces (SurfaceMesh *mesh, float length_threshold=1e-5)
	Remove degenerate faces. More...

static void	detect_overlapping_faces (SurfaceMesh *mesh, std::vector< std::pair< SurfaceMesh::Face, SurfaceMesh::Face > > &duplicate_faces, std::vector< std::pair< SurfaceMesh::Face, SurfaceMesh::Face > > &folding_faces, double dist_threshold=1e-6)
	Detects duplicate faces and folding faces. More...

static unsigned int	remove_overlapping_faces (SurfaceMesh *mesh, bool folding_faces=false, double dist_threshold=1e-6)
	Removes duplicate faces and and folding faces. More...

Self intersections
static std::vector< std::pair< SurfaceMesh::Face, SurfaceMesh::Face > >	detect_self_intersections (SurfaceMesh *mesh)
	Collects all pairs of intersecting faces of a triangulated surface mesh. More...

static bool	remesh_self_intersections (SurfaceMesh *mesh, bool stitch=true)
	Detects and remesh the intersecting faces. More...

Clip, split, and slice
static bool	clip (SurfaceMesh *mesh, const Plane3 &plane, bool clip_volume=false)
	Clips a triangle mesh by keeping the part on the negative side of a plane (side opposite to its normal vector). More...

static void	split (SurfaceMesh *mesh, const Plane3 &plane)
	Split a triangle mesh by a plane. More...

static std::vector< Polyline >	slice (SurfaceMesh *mesh, const Plane3 &plane)
	Computes the intersection of a plane with a triangle surface mesh. More...

static std::vector< std::vector< Polyline > >	slice (SurfaceMesh *mesh, const std::vector< Plane3 > &planes)
	Computes the intersection of a set of planes with a triangle surface mesh. More...

Detailed Description

A collection of mesh (and polygon soup) processing functions.

This class collects some related algorithms implemented using CGAL. It allows (re)orientation, detecting and resolving topological issues (e.g., duplicate vertices/faces, self intersection), and clipping/splitting/slicing of a surface mesh.

See also: OverlappingFaces and SelfIntersection.

Member Typedef Documentation

◆ Polyline

typedef std::vector<vec3> Polyline

A polyline represented by a list of points. If a polyline is closed, its first and last points will be identical.

Member Function Documentation

◆ clip()

bool clip	(	SurfaceMesh *	mesh,
		const Plane3 &	plane,
		bool	clip_volume = `false`
	)

static

Clips a triangle mesh by keeping the part on the negative side of a plane (side opposite to its normal vector).

If mesh is closed, the clipped part can be closed too if the named parameter clip_volume is set to true.

Precondition: mesh.is_triangle_mesh(), !does_self_intersect(SurfaceMesh* mesh).

Parameters

mesh	The input triangle mesh.
plane	The clipping plane whose negative side defines the half-space to intersect `mesh` with.

Returns: true if the output surface mesh is manifold. If false is returned

mesh is only refined: by the intersection with plane.

◆ detect_overlapping_faces()

void detect_overlapping_faces	(	SurfaceMesh *	mesh,
		std::vector< std::pair< SurfaceMesh::Face, SurfaceMesh::Face > > &	duplicate_faces,
		std::vector< std::pair< SurfaceMesh::Face, SurfaceMesh::Face > > &	folding_faces,
		double	dist_threshold = `1e-6`
	)

static

Detects duplicate faces and folding faces.

Two triangle faces are said duplicate if they have the same geometry (vertices within a distance threshold). Two triangle faces are said folding if they are coplanar, share one edge (i.e., have the same edge geometry), and partially overlap.

Parameters

duplicate_faces	Returns the duplicate face pairs found.
folding_faces	Returns the folding face pairs found.
dist_threshold	Two vertices are considered coincident if there distance is smaller than it.

Precondition: mesh.is_triangle_mesh().

◆ detect_self_intersections()

std::vector< std::pair< SurfaceMesh::Face, SurfaceMesh::Face > > detect_self_intersections ( SurfaceMesh * mesh )

static

Collects all pairs of intersecting faces of a triangulated surface mesh.

Two faces are said to intersect if the corresponding triangles intersect and the intersection is not an edge nor a vertex incident to both faces.

Precondition: mesh.is_triangle_mesh().

Parameters

mesh	The triangle surface mesh to be checked.

Returns: All pairs of non-adjacent faces that intersect.

◆ merge_reversible_connected_components()

void merge_reversible_connected_components ( SurfaceMesh * mesh )

static

Reverses the connected components having incompatible boundary cycles that could be merged if their orientation were made compatible, and stitches them. Connected components are examined by increasing number of faces.

Attention: Stitching occurs only if incompatible boundary cycles exists and the corresponding connected components are reversible.

See also: stitch_borders()

◆ orient_and_stitch_polygon_soup() [1/2]

bool orient_and_stitch_polygon_soup	(	std::vector< vec3 > &	points,
		std::vector< Polygon > &	polygons
	)

static

Tries to consistently orient and stitch a polygon soup.

When it is not possible to produce a combinatorial manifold surface, some points are duplicated.

The algorithm is described in

A.Guéziec, et al. Cutting and stitching: Converting sets of polygons to manifold surfaces. TVCG 2001.

Parameters

points	Points of the soup of polygons. Some additional points might be pushed back to resolve non-manifoldness or non-orientability issues.
polygons	Each element describes a polygon represented by the index of its vertices in `points`. If needed the order of the indices of a polygon might be reversed.

Returns: true if the orientation operation succeeded. false if some points were duplicated, thus producing a self-intersecting polyhedron.

◆ orient_and_stitch_polygon_soup() [2/2]

bool orient_and_stitch_polygon_soup ( SurfaceMesh * mesh )

static

Tries to consistently orient and stitch a mesh (treated as a polygon soup).

Internally, it calls orient_and_stitch_polygon_soup(std::vector<vec3>& points, std::vector<Polygon>& polygons).

See also: merge_reversible_connected_components()

◆ orient_closed_triangle_mesh()

void orient_closed_triangle_mesh ( SurfaceMesh * mesh )

static

Makes each connected component of a closed triangle surface mesh inward or outward oriented.

Precondition: mesh.is_triangle_mesh(), mesh.is_closed()

Parameters

mesh	The input mesh.

◆ remesh_self_intersections()

bool remesh_self_intersections	(	SurfaceMesh *	mesh,
		bool	stitch = `true`
	)

static

Detects and remesh the intersecting faces.

Precondition: mesh.is_triangle_mesh().

Parameters

mesh	The input mesh. If self intersection exists, it carries the remeshed model. Otherwise it remains unchanged.
stitch	Stitch the borders

Returns: true if remesh actually occurred (i.e., self intersection was detected).

◆ remove_degenerate_faces()

unsigned int remove_degenerate_faces	(	SurfaceMesh *	mesh,
		float	length_threshold = `1e-5`
	)

static

Remove degenerate faces.

Any triangle with an edge length smaller than a given threshold is consider degenerate and will be removed by the edge collapse operation.

Parameters

length_threshold The edge length threshold.

Returns: The number of faces removed.

◆ remove_overlapping_faces()

unsigned int remove_overlapping_faces	(	SurfaceMesh *	mesh,
		bool	folding_faces = `false`,
		double	dist_threshold = `1e-6`
	)

static

Removes duplicate faces and and folding faces.

Two triangle faces are said duplicate if they have the same geometry (vertices within a distance threshold). Two triangle faces are said folding if they are coplanar, share one edge (i.e., have the same edge geometry), and partially overlap.

Parameters

folding_faces true also to remove folding faces.

Returns: The number of faces that have been deleted.

Precondition: mesh.is_triangle_mesh().

◆ repair_polygon_soup() [1/2]

void repair_polygon_soup	(	std::vector< vec3 > &	points,
		std::vector< Polygon > &	polygons
	)

static

Repairs a given polygon soup through various repairing operations.

This function carries out the following tasks, in the same order as they are listed:

merging of duplicate points, using CGAL::Polygon_mesh_processing::merge_duplicate_points_in_polygon_soup();
simplification of polygons to remove geometrically identical consecutive vertices;
splitting of "pinched" polygons, that is polygons in which a geometric position appears more than once. The splitting process results in multiple non-pinched polygons;
removal of invalid polygons, that is polygons with fewer than 2 vertices;
removal of duplicate polygons, using Polygon_mesh_processing::merge_duplicate_polygons_in_polygon_soup();
removal of isolated points, using Polygon_mesh_processing::remove_isolated_points_in_polygon_soup().
Note
The point and polygon containers will be modified by the repairing operations, and thus the indexation of the polygons will also be changed.

◆ repair_polygon_soup() [2/2]

void repair_polygon_soup ( SurfaceMesh * mesh )

static

Repairs a given polygon mesh through various repairing operations.

This function carries out the following tasks, in the same order as they are listed:

merging of duplicate points;
simplification of faces to remove geometrically identical consecutive vertices;
splitting of "pinched" faces, that is face in which a geometric position appears more than once. The splitting process results in multiple non-pinched faces;
removal of invalid faces, that is faces with fewer than 2 vertices;
removal of duplicate faces;
removal of isolated points. This function treats the input mesh as a polygon soup. Internally, it calls clean_polygon_soup(std::vector<vec3>& points, std::vector<Polygon>& polygons).
Note
The point and face containers will be modified by the repairing operations, and thus the indexation of the polygons will also be changed.

◆ slice() [1/2]

std::vector< Surfacer::Polyline > slice	(	SurfaceMesh *	mesh,
		const Plane3 &	plane
	)

static

Computes the intersection of a plane with a triangle surface mesh.

Precondition: mesh.is_triangle_mesh(), !does_self_intersect(SurfaceMesh* mesh).

Parameters

mesh	The input triangle mesh.
plane	The plane to intersect the triangle surface mesh with.

Returns: The intersecting polylines. Each resulting polyline P is oriented such that for two consecutive points p and q in P, the normal vector of the face(s) containing the segment pq, the vector pq, and the normal of plane is a direct orthogonal basis. The normal vector of each face is chosen to point on the side of the face where its sequence of vertices is seen counterclockwise.

Note: An edge shared by two faces included in plane will not be reported. For example, if plane passes though one face of a cube, only one closed polyline will be reported (the boundary of the face).

See also: slice(SurfaceMesh *mesh, const std::vector<Plane3> &planes).

◆ slice() [2/2]

std::vector< std::vector< Surfacer::Polyline > > slice	(	SurfaceMesh *	mesh,
		const std::vector< Plane3 > &	planes
	)

static

Computes the intersection of a set of planes with a triangle surface mesh.

Precondition: mesh.is_triangle_mesh(), !does_self_intersect(SurfaceMesh* mesh).

Parameters

mesh	The input triangle mesh.
planes	The set of planes to intersect the triangle surface mesh with.

Returns: The intersecting polylines by all the planes. The i_th entry denotes the polylines created by the i_th plane. Each resulting polyline P is oriented such that for two consecutive points p and q in P, the normal vector of the face(s) containing the segment pq, the vector pq, and the normal of plane is a direct orthogonal basis. The normal vector of each face is chosen to point on the side of the face where its sequence of vertices is seen counterclockwise.

Note: An edge shared by two faces included in plane will not be reported. For example, if plane passes though one face of a cube, only one closed polyline will be reported (the boundary of the face).

See also: slice(SurfaceMesh *mesh, const Plane3 &plane).

◆ split()

void split	(	SurfaceMesh *	mesh,
		const Plane3 &	plane
	)

static

Split a triangle mesh by a plane.

It adds intersection edges of mesh and plane in mesh and duplicates those edges.

Precondition: mesh.is_triangle_mesh(), !does_self_intersect(SurfaceMesh* mesh).

Parameters

mesh	The input triangle mesh.
plane	The plane that will be used to split `mesh`.

◆ stitch_borders()

int stitch_borders ( SurfaceMesh * mesh )

static

Stitches together border halfedges in a polygon mesh.

The pairs of halfedges to be stitched are automatically found amongst all border halfedges. Two border halfedges h1 and h2 can be stitched if the points associated to the source and target vertices of h1 are the same as those of the target and source vertices of h2 respectively.

Returns: The number of pairs of halfedges that were stitched.

See also: merge_reversible_connected_components

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

/Users/lnan/Documents/Projects/Easy3D/easy3d/algo_ext/surfacer.h
/Users/lnan/Documents/Projects/Easy3D/easy3d/algo_ext/surfacer.cpp

Public Types

Static Public Member Functions

Detailed Description

Member Typedef Documentation

◆ Polyline

Member Function Documentation

◆ clip()

◆ detect_overlapping_faces()

◆ detect_self_intersections()

◆ merge_reversible_connected_components()

◆ orient_and_stitch_polygon_soup() [1/2]

◆ orient_and_stitch_polygon_soup() [2/2]

◆ orient_closed_triangle_mesh()

◆ remesh_self_intersections()

◆ remove_degenerate_faces()

◆ remove_overlapping_faces()

◆ repair_polygon_soup() [1/2]

◆ repair_polygon_soup() [2/2]

◆ slice() [1/2]

◆ slice() [2/2]

◆ split()

◆ stitch_borders()