The MeshTopoAlgorithm class provides several algorithms to manipulate a mesh. More...

#include <TopoAlgorithm.h>

Public Member Functions
	MeshTopoAlgorithm (MeshKernel &rclM)

virtual	~MeshTopoAlgorithm (void)

Topological Operations
bool	InsertVertex (unsigned long ulFacetPos, const Base::Vector3f &rclPoint)
	Inserts a new vertex in the given triangle so that is split into three triangles. More...

bool	InsertVertexAndSwapEdge (unsigned long ulFacetPos, const Base::Vector3f &rclPoint, float fMaxAngle)
	This method is provided for convenience. More...

void	SwapEdge (unsigned long ulFacetPos, unsigned long ulNeighbour)
	Swaps the common edge of two adjacent facets even if the operation might be illegal. More...

bool	SplitEdge (unsigned long ulFacetPos, unsigned long ulNeighbour, const Base::Vector3f &rP)
	Splits the common edge of the two adjacent facets with index ulFacetPos and ulNeighbour. More...

void	SplitOpenEdge (unsigned long ulFacetPos, unsigned short uSide, const Base::Vector3f &rP)
	Splits the facet with index ulFacetPos on the edge side uSide into two facets. More...

void	SplitFacet (unsigned long ulFacetPos, const Base::Vector3f &rP1, const Base::Vector3f &rP2)
	Splits the facet with index ulFacetPos into up to three facets. More...

bool	CollapseVertex (const VertexCollapse &vc)
	Collapse a vertex. More...

bool	IsCollapseEdgeLegal (const EdgeCollapse &ec) const
	Checks whether a collapse edge operation is legal, that is fulfilled if none of the adjacent facets flips its normal. More...

bool	CollapseEdge (unsigned long ulFacetPos, unsigned long ulNeighbour)
	Collapses the common edge of two adjacent facets. More...

bool	CollapseEdge (const EdgeCollapse &ec)
	Convenience function that passes already all needed information. More...

bool	CollapseFacet (unsigned long ulFacetPos)
	Removes the facet with index ulFacetPos and all its neighbour facets. More...

Topological Optimization
void	OptimizeTopology (float fMaxAngle)
	Tries to make a more beautiful mesh by swapping the common edge of two adjacent facets where needed. More...

void	OptimizeTopology ()

void	DelaunayFlip (float fMaxAngle)
	Tries to make a more beautiful mesh by swapping the common edge of two adjacent facets where needed. More...

int	DelaunayFlip ()
	Overloaded method DelaunayFlip that doesn't use ShouldSwapEdge to check for legal swap edge. More...

void	AdjustEdgesToCurvatureDirection ()
	Tries to adjust the edges to the curvature direction with the minimum absolute value of maximum and minimum curvature. More...

bool	SnapVertex (unsigned long ulFacetPos, const Base::Vector3f &rP)
	Creates a new triangle with neighbour facet ulFacetPos and the vertex rclPoint whereat it must lie outside the given facet. More...

bool	IsSwapEdgeLegal (unsigned long ulFacetPos, unsigned long ulNeighbour) const
	Checks whether a swap edge operation is legal, that is fulfilled if the two adjacent facets builds a convex polygon. More...

bool	ShouldSwapEdge (unsigned long ulFacetPos, unsigned long ulNeighbour, float fMaxAngle) const
	Checks whether the swap edge operation is legal and whether it makes sense. More...

float	SwapEdgeBenefit (unsigned long f, int e) const
	Computes a value for the benefit of swapping the edge. More...

void	Cleanup ()
	Removes all invalid marked elements from the mesh structure. More...

void	RemoveDegeneratedFacet (unsigned long index)
	Removes the degenerated facet at position index from the mesh structure. More...

void	RemoveCorruptedFacet (unsigned long index)
	Removes the corrupted facet at position index from the mesh structure. More...

void	FillupHoles (unsigned long length, int level, AbstractPolygonTriangulator &, std::list< std::vector< unsigned long > > &aFailed)
	Closes holes in the mesh that consists of up to length edges. More...

void	FillupHoles (int level, AbstractPolygonTriangulator &, const std::list< std::vector< unsigned long > > &aBorders, std::list< std::vector< unsigned long > > &aFailed)
	This is an overloaded method provided for convenience. More...

void	FindHoles (unsigned long length, std::list< std::vector< unsigned long > > &aBorders) const
	Find holes which consists of up to length edges. More...

void	FindComponents (unsigned long count, std::vector< unsigned long > &aInds)
	Find topologic independent components with maximum count facets and returns an array of the indices. More...

void	RemoveComponents (unsigned long count)
	Removes topologic independent components with maximum count facets. More...

void	HarmonizeNormals (void)
	Harmonizes the normals. More...

void	FlipNormals (void)
	Flips the normals. More...

void	BeginCache ()
	Caching facility. More...

void	EndCache ()

Detailed Description

The MeshTopoAlgorithm class provides several algorithms to manipulate a mesh.

It supports various mesh operations like inserting a new vertex, swapping the common edge of two adjacent facets, split a facet, ...

Author: Werner Mayer

Constructor & Destructor Documentation

◆ MeshTopoAlgorithm()

MeshTopoAlgorithm::MeshTopoAlgorithm ( MeshKernel & rclM )

◆ ~MeshTopoAlgorithm()

MeshTopoAlgorithm::~MeshTopoAlgorithm ( void )

virtual

References Cleanup(), and EndCache().

Member Function Documentation

◆ AdjustEdgesToCurvatureDirection()

void MeshTopoAlgorithm::AdjustEdgesToCurvatureDirection ( )

Tries to adjust the edges to the curvature direction with the minimum absolute value of maximum and minimum curvature.

Note: This is a high-level operation and tries to optimize the mesh as a whole.

References Base::Distance(), MeshCore::MeshGeomFacet::GetNormal(), MeshCore::MeshPointIterator::Init(), MeshCore::MeshFacet::IsFlag(), IsSwapEdgeLegal(), MeshCore::MeshPointIterator::More(), MeshCore::MeshPointIterator::Next(), Base::Vector3< _Precision >::Normalize(), MeshCore::MeshFacetArray::ResetFlag(), MeshCore::MeshFacet::SetFlag(), MeshCore::MeshFacet::Side(), SwapEdge(), MeshCore::MeshFacet::VISIT, Base::Vector3< _Precision >::x, Base::Vector3< _Precision >::y, and Base::Vector3< _Precision >::z.

Referenced by Mesh::MeshObject::optimizeEdges().

◆ BeginCache()

void MeshTopoAlgorithm::BeginCache ( )

Caching facility.

◆ Cleanup()

void MeshTopoAlgorithm::Cleanup ( )

Removes all invalid marked elements from the mesh structure.

Referenced by MeshCore::MeshRemoveNeedles::Fixup(), MeshCore::MeshFixMergeFacets::Fixup(), MeshPart::MeshAlgos::offsetSpecial2(), Mesh::MeshObject::offsetSpecial2(), and ~MeshTopoAlgorithm().

◆ CollapseEdge() [1/2]

bool MeshTopoAlgorithm::CollapseEdge ( const EdgeCollapse & ec )

Convenience function that passes already all needed information.

References DraftVecUtils::find(), MeshCore::MeshFacet::ReplaceNeighbour(), MeshCore::MeshFacet::SetInvalid(), and MeshCore::MeshFacet::Transpose().

◆ CollapseEdge() [2/2]

bool MeshTopoAlgorithm::CollapseEdge	(	unsigned long	ulFacetPos,
		unsigned long	ulNeighbour
	)

Collapses the common edge of two adjacent facets.

This operation removes one common point of the collapsed edge and the facets ulFacetPos and ulNeighbour from the data structure.

Note: If ulNeighbour is the neighbour facet on the i-th side of ulFacetPos then the i-th point is removed whereas i is 0, 1 or 2. If the other common point should be removed then CollapseEdge() should be invoked with swapped arguments of ulFacetPos and ulNeighbour, i.e. CollapseEdge( ulNeighbour, ulFacetPos ).; The client programmer must make sure that this is a legal operation.; This method marks the facets and the point as 'invalid' but does not remove them from the mesh structure, i.e. the mesh structure gets into an inconsistent stage. To make the structure consistent again Cleanup() should be called. The reason why this cannot be done automatically is that it would become quite slow if a lot of edges should be collapsed.; While the mesh structure has invalid elements the client programmer must take care not to use such elements.

References MeshCore::MeshFacet::IsValid(), MeshCore::MeshFacet::SetInvalid(), MeshCore::MeshFacet::Side(), and MeshCore::MeshFacet::Transpose().

Referenced by Mesh::MeshObject::collapseEdge(), and MeshCore::MeshRemoveNeedles::Fixup().

◆ CollapseFacet()

bool MeshTopoAlgorithm::CollapseFacet ( unsigned long ulFacetPos )

Removes the facet with index ulFacetPos and all its neighbour facets.

The three vertices that are referenced by this facet are replaced by its gravity point.

Note: The client programmer must make sure that this is a legal operation.; This method marks the facets and the point as 'invalid' but does not remove them from the mesh structure, i.e. the mesh structure gets into an inconsistent stage. To make the structure consistent again Cleanup() should be called. The reason why this cannot be done automatically is that it would become quite slow if a lot of facets should be collapsed.; While the mesh structure has invalid elements the client programmer must take care not to use such elements.

References MeshCore::MeshFacet::IsValid(), MeshCore::MeshFacet::SetInvalid(), MeshCore::MeshFacet::Side(), and MeshCore::MeshFacet::Transpose().

Referenced by Mesh::MeshObject::collapseFacet(), Mesh::MeshObject::collapseFacets(), MeshPart::MeshAlgos::offsetSpecial2(), and Mesh::MeshObject::offsetSpecial2().

◆ CollapseVertex()

bool MeshTopoAlgorithm::CollapseVertex ( const VertexCollapse & vc )

Collapse a vertex.

At the moment only removing inner vertexes referenced by three facets is supposrted.

References DraftVecUtils::find(), MeshCore::MeshFacet::HasPoint(), MeshCore::MeshFacet::ReplaceNeighbour(), MeshCore::MeshFacet::SetInvalid(), and MeshCore::MeshFacet::Transpose().

Referenced by MeshCore::MeshFixMergeFacets::Fixup().

◆ DelaunayFlip() [1/2]

int MeshTopoAlgorithm::DelaunayFlip ( )

Overloaded method DelaunayFlip that doesn't use ShouldSwapEdge to check for legal swap edge.

References MeshCore::MeshGeomFacet::CenterOfCircumCircle(), Base::DistanceP2(), MeshCore::MeshFacet::IsFlag(), MeshCore::MeshFacet::SetFlag(), MeshCore::MeshFacet::Side(), SwapEdge(), and MeshCore::MeshFacet::TMP0.

◆ DelaunayFlip() [2/2]

void MeshTopoAlgorithm::DelaunayFlip ( float fMaxAngle )

Tries to make a more beautiful mesh by swapping the common edge of two adjacent facets where needed.

A swap is needed where two adjacent facets don't fulfill the Delaunay condition.

References Base::DistanceP2(), ShouldSwapEdge(), MeshCore::MeshFacet::Side(), and SwapEdge().

◆ EndCache()

void MeshTopoAlgorithm::EndCache ( )

Referenced by ~MeshTopoAlgorithm().

◆ FillupHoles() [1/2]

void MeshTopoAlgorithm::FillupHoles	(	int	level,
		AbstractPolygonTriangulator &	cTria,
		const std::list< std::vector< unsigned long > > &	aBorders,
		std::list< std::vector< unsigned long > > &	aFailed
	)

This is an overloaded method provided for convenience.

It takes as first argument the boundaries which must be filled up.

References Base::Console(), MeshCore::MeshAlgorithm::FillupHole(), Base::ConsoleSingleton::Log(), and MeshCore::AbstractPolygonTriangulator::NeedsReindexing().

◆ FillupHoles() [2/2]

void MeshTopoAlgorithm::FillupHoles	(	unsigned long	length,
		int	level,
		AbstractPolygonTriangulator &	cTria,
		std::list< std::vector< unsigned long > > &	aFailed
	)

Closes holes in the mesh that consists of up to length edges.

In case a fit needs to be done then the points of the neighbours of level rings will be used. Holes for which the triangulation failed are returned in aFailed.

References MeshCore::MeshAlgorithm::GetMeshBorders(), and MeshCore::MeshAlgorithm::SplitBoundaryLoops().

Referenced by Mesh::MeshObject::fillupHoles().

◆ FindComponents()

void MeshTopoAlgorithm::FindComponents	(	unsigned long	count,
		std::vector< unsigned long > &	aInds
	)

Find topologic independent components with maximum count facets and returns an array of the indices.

References MeshCore::MeshComponents::OverEdge, and MeshCore::MeshComponents::SearchForComponents().

Referenced by Mesh::MeshObject::removeComponents(), and RemoveComponents().

◆ FindHoles()

void MeshTopoAlgorithm::FindHoles	(	unsigned long	length,
		std::list< std::vector< unsigned long > > &	aBorders
	)		const

Find holes which consists of up to length edges.

References MeshCore::MeshAlgorithm::GetMeshBorders().

◆ FlipNormals()

void MeshTopoAlgorithm::FlipNormals ( void )

Flips the normals.

Referenced by Mesh::MeshObject::flipNormals().

◆ HarmonizeNormals()

void MeshTopoAlgorithm::HarmonizeNormals ( void )

Harmonizes the normals.

References MeshCore::MeshEvalOrientation::GetIndices().

Referenced by MeshCore::MeshFixOrientation::Fixup(), and Mesh::MeshObject::harmonizeNormals().

◆ InsertVertex()

bool MeshTopoAlgorithm::InsertVertex	(	unsigned long	ulFacetPos,
		const Base::Vector3f &	rclPoint
	)

Inserts a new vertex in the given triangle so that is split into three triangles.

The given point must lie inside the triangle not outside or on an edge.

References MeshCore::MeshFacet::ReplaceNeighbour().

Referenced by Mesh::MeshObject::insertVertex(), and InsertVertexAndSwapEdge().

◆ InsertVertexAndSwapEdge()

bool MeshTopoAlgorithm::InsertVertexAndSwapEdge	(	unsigned long	ulFacetPos,
		const Base::Vector3f &	rclPoint,
		float	fMaxAngle
	)

This method is provided for convenience.

It inserts a new vertex to the mesh and tries to swap the common edges of the newly created facets with their neighbours. Just inserting a new vertex leads to very acute-angled triangles which might be problematic for some algorithms. This method tries to swap the edges to build more well-formed triangles.

See also: InsertVertex(), ShouldSwapEdge(), SwapEdge().

References InsertVertex(), ShouldSwapEdge(), and SwapEdge().

Referenced by Mesh::MeshObject::refine().

◆ IsCollapseEdgeLegal()

bool MeshTopoAlgorithm::IsCollapseEdgeLegal ( const EdgeCollapse & ec ) const

Checks whether a collapse edge operation is legal, that is fulfilled if none of the adjacent facets flips its normal.

If this operation is legal true is returned, false is returned if this operation is illegal.

References MeshCore::MeshGeomFacet::GetNormal().

Referenced by MeshCore::MeshRemoveNeedles::Fixup().

◆ IsSwapEdgeLegal()

bool MeshTopoAlgorithm::IsSwapEdgeLegal	(	unsigned long	ulFacetPos,
		unsigned long	ulNeighbour
	)		const

Checks whether a swap edge operation is legal, that is fulfilled if the two adjacent facets builds a convex polygon.

If this operation is legal true is returned, false is returned if this operation is illegal or if ulFacetPos and ulNeighbour are not adjacent facets.

References MeshCore::MeshGeomFacet::IsDegenerated(), and MeshCore::MeshFacet::Side().

Referenced by AdjustEdgesToCurvatureDirection(), and ShouldSwapEdge().

◆ OptimizeTopology() [1/2]

void MeshTopoAlgorithm::OptimizeTopology ( )

References SwapEdge(), and SwapEdgeBenefit().

◆ OptimizeTopology() [2/2]

void MeshTopoAlgorithm::OptimizeTopology ( float fMaxAngle )

Tries to make a more beautiful mesh by swapping the common edge of two adjacent facets where needed.

fMaxAngle is the maximum allowed angle between the normals of two adjacent facets to allow swapping the common edge. A too high value might result into folds on the surface.

Note: This is a high-level operation and tries to optimize the mesh as a whole.

References ShouldSwapEdge(), MeshCore::MeshFacet::Side(), and SwapEdge().

Referenced by Mesh::MeshObject::optimizeTopology().

◆ RemoveComponents()

void MeshTopoAlgorithm::RemoveComponents ( unsigned long count )

Removes topologic independent components with maximum count facets.

References FindComponents().

◆ RemoveCorruptedFacet()

void MeshTopoAlgorithm::RemoveCorruptedFacet ( unsigned long index )

Removes the corrupted facet at position index from the mesh structure.

A facet is corrupted if the indices of its corner points are not all different.

References MeshCore::MeshFacet::ReplaceNeighbour().

Referenced by MeshCore::MeshFixCorruptedFacets::Fixup().

◆ RemoveDegeneratedFacet()

void MeshTopoAlgorithm::RemoveDegeneratedFacet ( unsigned long index )

Removes the degenerated facet at position index from the mesh structure.

A facet is degenerated if its corner points are collinear.

References MeshCore::MeshFacet::ReplaceNeighbour(), and MeshCore::MeshFacet::Side().

Referenced by MeshCore::MeshFixDegeneratedFacets::Fixup().

◆ ShouldSwapEdge()

bool MeshTopoAlgorithm::ShouldSwapEdge	(	unsigned long	ulFacetPos,
		unsigned long	ulNeighbour,
		float	fMaxAngle
	)		const

Checks whether the swap edge operation is legal and whether it makes sense.

This operation only makes sense if the maximum angle of both facets is decreased and if the angle between the facet normals does not exceed fMaxAngle.

References Base::Vector3< _Precision >::GetAngle(), MeshCore::MeshGeomFacet::GetNormal(), IsSwapEdgeLegal(), MeshCore::MeshGeomFacet::MaximumAngle(), and MeshCore::MeshFacet::Side().

Referenced by DelaunayFlip(), MeshCore::MeshFixDeformedFacets::Fixup(), InsertVertexAndSwapEdge(), and OptimizeTopology().

◆ SnapVertex()

bool MeshTopoAlgorithm::SnapVertex	(	unsigned long	ulFacetPos,
		const Base::Vector3f &	rP
	)

Creates a new triangle with neighbour facet ulFacetPos and the vertex rclPoint whereat it must lie outside the given facet.

Note: The vertex rclPoint doesn't necessarily need to be a new vertex it can already be part of another triangle but the client programmer must make sure that no overlaps are created.; This operation might be useful to close gaps in a mesh.

References Base::DistanceP2(), MeshCore::MeshFacet::HasOpenEdge(), Base::Vector3< _Precision >::Length(), and SplitOpenEdge().

Referenced by Mesh::MeshObject::snapVertex().

◆ SplitEdge()

bool MeshTopoAlgorithm::SplitEdge	(	unsigned long	ulFacetPos,
		unsigned long	ulNeighbour,
		const Base::Vector3f &	rP
	)

Splits the common edge of the two adjacent facets with index ulFacetPos and ulNeighbour.

The point rP must lie inside of one the given facets are on the common edge. The two facets get broken into four facets, i.e. that two new facets get created. If rP is coincident with a corner point nothing happens.

References MeshCore::MeshFacet::Side().

Referenced by Mesh::MeshObject::splitEdge(), Mesh::MeshObject::splitEdges(), and SplitFacet().

◆ SplitFacet()

void MeshTopoAlgorithm::SplitFacet	(	unsigned long	ulFacetPos,
		const Base::Vector3f &	rP1,
		const Base::Vector3f &	rP2
	)

Splits the facet with index ulFacetPos into up to three facets.

FIXME: Implement.

The points rP1 and rP2 should lie on two different edges of the facet. This method splits up the both neighbour facets as well. If either rP1 or rP2 (probably due to a previous call of SplitFacet()) is coincident with a corner point then the facet is split into two facets. If both points are coincident with corner points of this facet nothing is done.

References Base::Distance(), Base::Vector3< _Precision >::DistanceToLine(), SplitEdge(), and SplitOpenEdge().

Referenced by MeshPart::MeshAlgos::cutByCurve(), and Mesh::MeshObject::splitFacet().

◆ SplitOpenEdge()

void MeshTopoAlgorithm::SplitOpenEdge	(	unsigned long	ulFacetPos,
		unsigned short	uSide,
		const Base::Vector3f &	rP
	)

Splits the facet with index ulFacetPos on the edge side uSide into two facets.

This side must be an open edge otherwise nothing is done. The point rP must be near to this edge and must not be coincident with any corner vertices of the facet.

Referenced by SnapVertex(), and SplitFacet().

◆ SwapEdge()

void MeshTopoAlgorithm::SwapEdge	(	unsigned long	ulFacetPos,
		unsigned long	ulNeighbour
	)

Swaps the common edge of two adjacent facets even if the operation might be illegal.

To be sure that this operation is legal, check either with IsSwapEdgeLegal() or ShouldSwapEdge() before. An illegal swap edge operation can produce non-manifolds, degenerated facets or it might create a fold on the surface, i.e. geometric overlaps of several triangles.