A class for managing curves on a 2-manifold (Curve on Manifold - CoM). More...

#include <curve_on_manifold.h>

Classes
class	EdgePointPred

struct	EdgePointSplit

class	Param
	Parameter class controlling the behavior of CoM algorithms. More...

Public Types
typedef MeshType::ScalarType	ScalarType

typedef MeshType::CoordType	CoordType

typedef MeshType::VertexType	VertexType

typedef MeshType::VertexPointer	VertexPointer

typedef MeshType::VertexIterator	VertexIterator

typedef MeshType::EdgeIterator	EdgeIterator

typedef MeshType::EdgeType	EdgeType

typedef MeshType::FaceType	FaceType

typedef MeshType::FacePointer	FacePointer

typedef MeshType::FaceIterator	FaceIterator

typedef Box3< ScalarType >	Box3Type

typedef Segment3< ScalarType >	Segment3Type

typedef vcg::GridStaticPtr< FaceType, ScalarType >	MeshGrid

typedef vcg::GridStaticPtr< EdgeType, ScalarType >	EdgeGrid

typedef face::Pos< FaceType >	PosType

typedef tri::UpdateTopology< MeshType >::PEdge	PEdge

Public Member Functions
	CoM (MeshType &_m)
	Constructor: initializes the CoM with a base mesh.

FaceType *	GetClosestFace (const CoordType &p)
	Get the closest face to a query point.

FaceType *	GetClosestFaceIP (const CoordType &p, CoordType &ip)
	Get the closest face and its barycentric coordinates.

FaceType *	GetClosestFaceIP (const CoordType &p, CoordType &ip, CoordType &in)
	Get the closest face, barycentric coordinates, and normal.

FaceType *	GetClosestFacePoint (const CoordType &p, CoordType &closestP)
	Get the closest face and the closest point on it.

bool	IsWellSnapped (const CoordType &ip)
	Test if a barycentric coordinate is well snapped.

bool	IsSnappedEdge (CoordType &ip, int &ei)
	Check if a barycentric coordinate is snapped to an edge.

bool	IsSnappedVertex (CoordType &ip, int &vi)
	Check if a barycentric coordinate is snapped to a vertex.

VertexPointer	FindVertexSnap (FacePointer fp, CoordType &ip)
	Find the vertex pointer for a vertex-snapped barycentric coordinate.

bool	TagFaceEdgeSelWithPolyLine (MeshType &poly, bool markFlag=true)
	Tag face edges of the base mesh that coincide with polyline edges.

ScalarType	MinDistOnEdge (CoordType samplePnt, EdgeGrid &edgeGrid, MeshType &poly, CoordType &closestPoint)
	Find the minimum distance from a sample point to the polyline.

bool	SnapPolyline (MeshType &poly)
	SnapPolyline snaps the vertexes of a polyline onto the base mesh.

void	SelectBoundaryVertex (MeshType &poly)

void	SelectUniformlyDistributed (MeshType &poly, int k)

void	DecomposeNonManifoldPolyline (MeshType &poly, bool singSplitFlag=true)

void	SplitMeshWithPolyline (MeshType &poly)
	Split the base mesh to make it conforming with the polyline.

void	Init ()
	Initialize the CoM data structures for processing.

void	SimplifyNullEdges (MeshType &poly)
	Remove duplicate/zero-length edges from a polyline.

void	SimplifyMidEdge (MeshType &poly)

void	SimplifyMidFace (MeshType &poly)
	SimplifyMidFace remove all the vertices that in the mid of a face and between two of the points snapped onto the edges of the same face.

void	Simplify (MeshType &poly)

void	EvaluateHausdorffDistance (MeshType &poly, Distribution< ScalarType > &dist)

bool	BarycentricSnap (CoordType &ip)
	Snap barycentric coordinates to 0 or 1 if within threshold.

bool	TestSplitSegWithMesh (VertexType v0, VertexType v1, CoordType &splitPt)
	TestSplitSegWithMesh Given a poly segment decide if it should be split along elements of base mesh.

bool	SnappedOnSameFace (FacePointer f0, CoordType i0, FacePointer f1, CoordType i1)
	SnappedOnSameFace Return true if the two points are snapped to a common face;.

bool	TestSplitSegWithMeshAdapt (VertexType v0, VertexType v1, CoordType &splitPt)
	TestSplitSegWithMesh Given a poly segment decide if it should be split along elements of base mesh.

bool	TestSplitSegWithMeshAdaptOld (VertexType v0, VertexType v1, CoordType &splitPt)

ScalarType	MaxSegDist (VertexType v0, VertexType v1, CoordType &farthestPointOnSurf, CoordType &farthestN, Distribution< ScalarType > *dist=0)

void	RefineCurveByDistance (MeshType &poly)
	RefineCurve.

void	RefineCurveByBaseMesh (MeshType &poly)
	RefineCurveByBaseMesh.

void	SmoothProject (MeshType &poly, int iterNum, ScalarType smoothWeight, ScalarType projectWeight)
	SmoothProject.

Static Public Member Functions
static ScalarType	MinDistOnEdge (VertexType v0, VertexType v1, EdgeGrid &edgeGrid, MeshType &poly, CoordType &closestPoint)
	Find the closest point on a mesh edge to the polyline (static version)

static void	ExtractVertex (const MeshType &srcMesh, const FaceType &f, int whichWedge, const MeshType &dstMesh, VertexType &v)
	Extract vertex attributes for seam processing.

static bool	CompareVertex (const MeshType &m, const VertexType &vA, const VertexType &vB)
	Compare two vertices for seam compatibility.

static CoordType	QLerp (VertexType v0, VertexType v1)
	Compute quality-weighted linear interpolation between two vertices.

Public Attributes
MeshType &	base
	Reference to the base triangulated surface mesh.

MeshGrid	uniformGrid
	Spatial acceleration structure for closest point queries.

Param	par
	Parameters controlling algorithm behavior.

Detailed Description

template<class MeshType>
class vcg::tri::CoM< MeshType >

A class for managing curves on a 2-manifold (Curve on Manifold - CoM).

This class is used to project, simplify, smooth, and snap polylines (represented as edge meshes) over a triangulated surface (the "base mesh").

Overview

The CoM class provides tools to:

Project polylines onto a surface
Snap polyline vertices to mesh vertices or edges
Refine polylines to follow surface features
Simplify polylines while maintaining surface fidelity
Split the base mesh along polylines for mesh cutting operations

Terminology

Base mesh: The triangulated surface mesh (stored in base)
Polyline/Curve: An edge mesh passed to the various methods (typically named poly in parameters)
Snapping: The process of aligning polyline vertices to mesh vertices or edges using barycentric thresholds

Requirements

The base mesh should be:

2-manifold
Have reasonable triangle quality
Have up-to-date topology (FaceFace adjacency)
Have bounding box correctly set

Usage Pattern

Initialize the class with a base mesh: CoM<MeshType> com(baseMesh);
Call Init() to build the spatial acceleration structures
Pass polylines (as edge meshes) to various methods for processing
Adjust parameters via the par member for fine control

Implementation Notes

The class uses barycentric coordinates to determine if a point of the polyline should snap to vertices or edges
All spatial queries use a uniform grid for acceleration
Many operations are iterative and may require multiple passes

Note: There is some naming inconsistency: methods use both "Curve" and "Polyline" interchangeably to refer to the edge mesh being processed.

Member Function Documentation

◆ BarycentricSnap()

template<class MeshType >

bool vcg::tri::CoM< MeshType >::BarycentricSnap ( CoordType & ip )

inline

Snap barycentric coordinates to 0 or 1 if within threshold.

Parameters

ip	Input/Output: barycentric coordinates (must sum to 1.0)

Returns: true if the point was snapped to a vertex or edge (at least one coord became 0)

This is one of the MOST IMPORTANT functions in the class - it's used throughout!

Given barycentric coordinates of a point in a triangle, this function decides whether it should be "snapped" to a vertex or edge based on the par.barycentricSnapThr threshold.

Algorithm:

If any coordinate is within barycentricSnapThr of 0, snap it to 0
If any coordinate is within barycentricSnapThr of 1, snap it to 1
Renormalize to ensure sum = 1.0
If sum is still not exactly 1.0 (due to floating point), adjust the non-snapped coordinate

Snapping Cases:

One coord = 1.0, others = 0 → Snapped to a vertex
One coord = 0, others > 0 → Snapped to an edge
All coords > 0 and < 1 → Interior point, NOT snapped

Return Value:

true: Point is on a vertex or edge (at least one coordinate is 0)
false: Point is in the interior of the triangle

Note: This function MODIFIES the input coordinates in-place!; The threshold par.barycentricSnapThr (default 0.05) controls snapping sensitivity

Warning: Side effect: modifies ip parameter! Consider renaming to BarycentricSnapInPlace()

See also: IsWellSnapped, IsSnappedVertex, IsSnappedEdge

◆ CompareVertex()

template<class MeshType >

static bool vcg::tri::CoM< MeshType >::CompareVertex	(	const MeshType &	m,
		const VertexType &	vA,
		const VertexType &	vB
	)

inlinestatic

Compare two vertices for seam compatibility.

Parameters

m	The mesh (unused but required by interface)
vA	First vertex
vB	Second vertex

Returns: true if vertices are compatible across a seam

This callback is used by the attribute_seam system to determine if two vertices can be considered the same across a seam boundary. Current implementation: Red and Blue colored vertices are considered incompatible.

Note: This is part of the mesh cutting/seam processing infrastructure.

◆ ExtractVertex()

template<class MeshType >

static void vcg::tri::CoM< MeshType >::ExtractVertex	(	const MeshType &	srcMesh,
		const FaceType &	f,
		int	whichWedge,
		const MeshType &	dstMesh,
		VertexType &	v
	)

inlinestatic

Extract vertex attributes for seam processing.

Parameters

srcMesh	Source mesh (unused but required by interface)
f	The face containing the vertex
whichWedge	Which vertex (0,1,2) of the face to extract
dstMesh	Destination mesh (unused but required by interface)
v	Output: vertex with copied attributes

This is a callback function used by the attribute_seam system. It copies all per-vertex properties and uses the face color.

Note: This is used when splitting the mesh along seams/polylines.

◆ FindVertexSnap()

template<class MeshType >

VertexPointer vcg::tri::CoM< MeshType >::FindVertexSnap	(	FacePointer	fp,
		CoordType &	ip
	)

inline

Find the vertex pointer for a vertex-snapped barycentric coordinate.

Parameters

fp	The face containing the point
ip	The barycentric coordinate (should be snapped to a vertex)

Returns: Pointer to the snapped vertex, or nullptr if not vertex-snapped

◆ GetClosestFace()

template<class MeshType >

FaceType * vcg::tri::CoM< MeshType >::GetClosestFace ( const CoordType & p )

inline

Get the closest face to a query point.

Parameters

p	The query point

Returns: Pointer to the closest face, or nullptr if none found within gridBailout distance

◆ GetClosestFaceIP() [1/2]

template<class MeshType >

FaceType * vcg::tri::CoM< MeshType >::GetClosestFaceIP	(	const CoordType &	p,
		CoordType &	ip
	)

inline

Get the closest face and its barycentric coordinates.

Parameters

p	The query point
ip	Output: barycentric coordinates of the closest point on the returned face

Returns: Pointer to the closest face

◆ GetClosestFaceIP() [2/2]

template<class MeshType >

FaceType * vcg::tri::CoM< MeshType >::GetClosestFaceIP	(	const CoordType &	p,
		CoordType &	ip,
		CoordType &	in
	)

inline

Get the closest face, barycentric coordinates, and normal.

Parameters

p	The query point
ip	Output: barycentric coordinates of the closest point on the returned face
in	Output: normal at the closest point

Returns: Pointer to the closest face

◆ GetClosestFacePoint()

template<class MeshType >

FaceType * vcg::tri::CoM< MeshType >::GetClosestFacePoint	(	const CoordType &	p,
		CoordType &	closestP
	)

inline

Get the closest face and the closest point on it.

Parameters

p	The query point
closestP	Output: the 3D coordinates of the closest point on the surface

Returns: Pointer to the closest face

◆ Init()

template<class MeshType >

void vcg::tri::CoM< MeshType >::Init ( )

inline

Initialize the CoM data structures for processing.

This must be called after construction and whenever the base mesh is modified. It performs:

Face normal computation
Face-Face topology update
Spatial acceleration structure (uniform grid) construction

Note: Call this before using any polyline processing methods.

Warning: If the base mesh topology changes, call Init() again.

◆ IsSnappedEdge()

template<class MeshType >

bool vcg::tri::CoM< MeshType >::IsSnappedEdge	(	CoordType &	ip,
		int &	ei
	)

inline

Check if a barycentric coordinate is snapped to an edge.

Parameters

ip	The barycentric coordinate (must be snapped)
ei	Output: index (0,1,2) of the edge opposite to the zero coordinate

Returns: true if snapped to an edge (exactly one coordinate is 0, other two are positive)

Edge snapping means the point lies on one of the three edges of the triangle. Edge i is the edge from vertex i to vertex (i+1)%3, opposite to vertex (i+2)%3.

◆ IsSnappedVertex()

template<class MeshType >

bool vcg::tri::CoM< MeshType >::IsSnappedVertex	(	CoordType &	ip,
		int &	vi
	)

inline

Check if a barycentric coordinate is snapped to a vertex.

Parameters

ip	The barycentric coordinate (must be snapped)
vi	Output: index (0,1,2) of the vertex with coordinate == 1.0

Returns: true if snapped to a vertex (one coordinate is 1.0, others are 0.0)

◆ IsWellSnapped()

template<class MeshType >

bool vcg::tri::CoM< MeshType >::IsWellSnapped ( const CoordType & ip )

inline

Test if a barycentric coordinate is well snapped.

Parameters

ip	The barycentric coordinate to test (must sum to 1.0)

Returns: true if no snapping is needed (all coords are either 0, 1, or far from boundaries)

A barycentric coordinate is "well snapped" if each component is either:

Exactly 0.0 or 1.0, OR
Far enough from 0 and 1 (outside the barycentricSnapThr threshold)

This indicates the point doesn't need further snapping adjustment.

◆ MinDistOnEdge() [1/2]

template<class MeshType >

ScalarType vcg::tri::CoM< MeshType >::MinDistOnEdge	(	CoordType	samplePnt,
		EdgeGrid &	edgeGrid,
		MeshType &	poly,
		CoordType &	closestPoint
	)

inline

Find the minimum distance from a sample point to the polyline.

Parameters

samplePnt	The point to measure distance from
edgeGrid	Spatial acceleration grid for the polyline edges
poly	The polyline (as edge mesh)
closestPoint	Output: the closest point on the polyline

Returns: The minimum distance from samplePnt to the polyline

◆ MinDistOnEdge() [2/2]

template<class MeshType >

static ScalarType vcg::tri::CoM< MeshType >::MinDistOnEdge	(	VertexType *	v0,
		VertexType *	v1,
		EdgeGrid &	edgeGrid,
		MeshType &	poly,
		CoordType &	closestPoint
	)

inlinestatic

Find the closest point on a mesh edge to the polyline (static version)

Parameters

v0	First vertex of the mesh edge
v1	Second vertex of the mesh edge
edgeGrid	Spatial acceleration grid for the polyline edges
poly	The polyline (as edge mesh)
closestPoint	Output: the point on the edge [v0,v1] closest to the polyline

Returns: The minimum distance from the edge to the polyline

This samples the edge [v0,v1] uniformly and finds which sample is closest to the polyline.

◆ QLerp()

template<class MeshType >

static CoordType vcg::tri::CoM< MeshType >::QLerp	(	VertexType *	v0,
		VertexType *	v1
	)

inlinestatic

Compute quality-weighted linear interpolation between two vertices.

Parameters

v0	First vertex
v1	Second vertex

Returns: Interpolated position weighted by inverse quality values

Points with higher quality (larger absolute value) contribute less to the result. This is useful for adaptive refinement based on error metrics stored in quality.

◆ RefineCurveByBaseMesh()

template<class MeshType >

void vcg::tri::CoM< MeshType >::RefineCurveByBaseMesh ( MeshType & poly )

inline

RefineCurveByBaseMesh.

Parameters

poly

◆ RefineCurveByDistance()

template<class MeshType >

void vcg::tri::CoM< MeshType >::RefineCurveByDistance ( MeshType & poly )

inline

RefineCurve.

Parameters

poly	the curve to be refined
uniformFlag

Make one pass of refinement for all the edges of the curve that are distant from the basemesh uses two parameters:

par.minRefEdgeLen
par.surfDistThr

◆ SimplifyMidFace()

template<class MeshType >

void vcg::tri::CoM< MeshType >::SimplifyMidFace ( MeshType & poly )

inline

SimplifyMidFace remove all the vertices that in the mid of a face and between two of the points snapped onto the edges of the same face.

Parameters

poly

It assumes that the mesh has been snapped and refined by the BaseMesh

◆ SimplifyNullEdges()

template<class MeshType >

void vcg::tri::CoM< MeshType >::SimplifyNullEdges ( MeshType & poly )

inline

Remove duplicate/zero-length edges from a polyline.

Parameters

poly	The polyline to simplify

Removes vertices that have collapsed to the same position.

◆ SmoothProject()

template<class MeshType >

void vcg::tri::CoM< MeshType >::SmoothProject	(	MeshType &	poly,
		int	iterNum,
		ScalarType	smoothWeight,
		ScalarType	projectWeight
	)

inline

SmoothProject.

Parameters

poly
iterNum
smoothWeight	[0..1] range;
projectWeight	[0..1] range;

The very important function to adapt a polyline onto the base mesh The projection process must be done slowly to guarantee some empirical convergence... For each iteration it choose a new position of each vertex of the polyline. The new position is a blend between the smoothed position, the closest point on the surface and the original position. You need a good balance... after each iteration the polyline is refined and simplified.

◆ SnappedOnSameFace()

template<class MeshType >

bool vcg::tri::CoM< MeshType >::SnappedOnSameFace	(	FacePointer	f0,
		CoordType	i0,
		FacePointer	f1,
		CoordType	i1
	)

inline

SnappedOnSameFace Return true if the two points are snapped to a common face;.

Parameters

f0
i0
f1
i0

Returns

Require FFAdj. se assume that both SNAPPED. Three cases:

Edge Edge - true iff the two edges belongs to a common face.
Vert Edge - true iff there is one of the two snapped edge faces has the vert as non-edge face;
Vert Vert

◆ SnapPolyline()

template<class MeshType >

bool vcg::tri::CoM< MeshType >::SnapPolyline ( MeshType & poly )

inline

SnapPolyline snaps the vertexes of a polyline onto the base mesh.

Parameters

poly
newVertVec	the vector of the indexes of the snapped vertices

Returns: true if it has modified the polyline

Polyline vertices can be snapped either on vertexes or on edges. Usually the only points that we should allow to not be snapped are the endpoints and non manifold points. Vertexes are colored according to their snapping state

◆ SplitMeshWithPolyline()

template<class MeshType >

void vcg::tri::CoM< MeshType >::SplitMeshWithPolyline ( MeshType & poly )

inline

Split the base mesh to make it conforming with the polyline.

Parameters

poly	The polyline to integrate into the base mesh

This is a complex two-phase algorithm:

Phase 1: Vertex Insertion

Finds all polyline vertices that are NOT snapped to mesh vertices/edges
Inserts them into the base mesh using 1-to-3 face splits
This creates new vertices in the mesh at polyline vertex positions

Phase 2: Edge Splitting (iterative)

Identifies mesh edges that are crossed by polyline edges
Splits those edges at the intersection points
Repeats until no more edges need splitting

After completion, the polyline edges should coincide with base mesh edges, allowing subsequent operations like mesh cutting or constrained triangulation.

Note: This modifies the base mesh topology!; Calls Init() internally to rebuild spatial structures; Calls SnapPolyline() to update polyline after mesh modifications

Warning: This can significantly increase mesh complexity

See also: TagFaceEdgeSelWithPolyLine, SnapPolyline

◆ TagFaceEdgeSelWithPolyLine()

template<class MeshType >

bool vcg::tri::CoM< MeshType >::TagFaceEdgeSelWithPolyLine	(	MeshType &	poly,
		bool	markFlag = `true`
	)

inline

Tag face edges of the base mesh that coincide with polyline edges.

Parameters

poly	The polyline (as edge mesh) to use for tagging
markFlag	If true, clears all FaceEdgeS flags before tagging (default: true)

Returns: true if ALL edges of the polyline are fully snapped onto mesh edges

This function marks edges in the base mesh (using FaceEdgeS flag) where they coincide with edges from the polyline. The polyline edges must be snapped to mesh vertices at both endpoints for this to work.

Note: This is typically used as a preparation step before cutting the mesh along the polyline using CutMeshAlongCrease or similar functions.

Warning: Returns false if any polyline edge is not properly snapped, or if the snapped vertices don't form an edge in the base mesh.

See also: SplitMeshWithPolyline, CutMeshAlongCrease

◆ TestSplitSegWithMesh()

template<class MeshType >

bool vcg::tri::CoM< MeshType >::TestSplitSegWithMesh	(	VertexType *	v0,
		VertexType *	v1,
		CoordType &	splitPt
	)

inline

TestSplitSegWithMesh Given a poly segment decide if it should be split along elements of base mesh.

Parameters

v0
v1
splitPt

Returns: true if it should be split

We make a few samples onto the edge and if some of them snaps onto a an edge we use it. In case there are more than one candidate we choose the sample closeset to its snapping point. We explicitly avoid snapping twice on the same edge by checking the starting and ending edges.

Two cases:

poly edge pass near a vertex of the mesh
poly edge cross one or more edges

Note that we have to check the case where

◆ TestSplitSegWithMeshAdapt()

template<class MeshType >

bool vcg::tri::CoM< MeshType >::TestSplitSegWithMeshAdapt	(	VertexType *	v0,
		VertexType *	v1,
		CoordType &	splitPt
	)

inline

TestSplitSegWithMesh Given a poly segment decide if it should be split along elements of base mesh.

Parameters

v0
v1
splitPt

Returns: true if it should be split

We make a few samples onto the edge and if some of them snaps onto a an edge we use it. In case there are more than one candidate we choose the sample closeset to its snapping point. We explicitly avoid snapping twice on the same edge by checking the starting and ending edges.

Two cases:

poly edge pass near a vertex of the mesh
poly edge cross one or more edges

Note that we have to check the case where

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

vcg/complex/algorithms/curve_on_manifold.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Detailed Description

Member Function Documentation

◆ BarycentricSnap()

◆ CompareVertex()

◆ ExtractVertex()

◆ FindVertexSnap()

◆ GetClosestFace()

◆ GetClosestFaceIP() [1/2]

◆ GetClosestFaceIP() [2/2]

◆ GetClosestFacePoint()

◆ Init()

◆ IsSnappedEdge()

◆ IsSnappedVertex()

◆ IsWellSnapped()

◆ MinDistOnEdge() [1/2]

◆ MinDistOnEdge() [2/2]

◆ QLerp()

◆ RefineCurveByBaseMesh()

◆ RefineCurveByDistance()

◆ SimplifyMidFace()

◆ SimplifyNullEdges()

◆ SmoothProject()

◆ SnappedOnSameFace()

◆ SnapPolyline()

◆ SplitMeshWithPolyline()

◆ TagFaceEdgeSelWithPolyLine()

◆ TestSplitSegWithMesh()

◆ TestSplitSegWithMeshAdapt()