\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.11 - Polygon Mesh Processing
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages

Functions to triangulate faces, and to refine and fair regions of a polygon mesh.

Functions

template<typename VertexRange , typename TriangleMesh , typename NamedParameters >
void CGAL::Polygon_mesh_processing::random_perturbation (VertexRange vertices, TriangleMesh &tmesh, const double &perturbation_max_size, const NamedParameters &np)
 randomly perturbs the locations of vertices of a triangulated surface mesh. More...
 
template<typename TriangleMesh , typename NamedParameters >
void CGAL::Polygon_mesh_processing::random_perturbation (TriangleMesh &tmesh, const double &perturbation_max_size, const NamedParameters &np)
 same as above, but all non-border vertices of tmesh are perturbed.
 
template<typename TriangleMesh , typename FaceRange , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters >
std::pair< FaceOutputIterator,
VertexOutputIterator > 
CGAL::Polygon_mesh_processing::refine (TriangleMesh &tmesh, const FaceRange &faces, FaceOutputIterator faces_out, VertexOutputIterator vertices_out, const NamedParameters &np)
 refines a region of a triangle mesh More...
 
template<typename TriangleMesh , typename VertexRange , typename NamedParameters >
bool CGAL::Polygon_mesh_processing::fair (TriangleMesh &tmesh, const VertexRange &vertices, const NamedParameters &np)
 fairs a region on a triangle mesh. More...
 
template<typename PolygonMesh , typename FaceRange , typename NamedParameters >
void CGAL::Polygon_mesh_processing::isotropic_remeshing (const FaceRange &faces, const double &target_edge_length, PolygonMesh &pmesh, const NamedParameters &np)
 remeshes a triangulated region of a polygon mesh. More...
 
template<typename PolygonMesh , typename EdgeRange , typename NamedParameters >
void CGAL::Polygon_mesh_processing::split_long_edges (const EdgeRange &edges, const double &max_length, PolygonMesh &pmesh, const NamedParameters &np)
 splits the edges listed in edges into sub-edges that are not longer than the given threshold max_length. More...
 
template<typename PolygonMesh , typename NamedParameters >
bool CGAL::Polygon_mesh_processing::triangulate_face (typename boost::graph_traits< PolygonMesh >::face_descriptor f, PolygonMesh &pmesh, const NamedParameters &np)
 triangulates a single face of a polygon mesh. More...
 
template<typename FaceRange , typename PolygonMesh , typename NamedParameters >
bool CGAL::Polygon_mesh_processing::triangulate_faces (FaceRange face_range, PolygonMesh &pmesh, const NamedParameters &np)
 triangulates given faces of a polygon mesh. More...
 
template<typename PolygonMesh , typename NamedParameters >
bool CGAL::Polygon_mesh_processing::triangulate_faces (PolygonMesh &pmesh, const NamedParameters &np)
 triangulates all faces of a polygon mesh. More...
 

Function Documentation

template<typename TriangleMesh , typename VertexRange , typename NamedParameters >
bool CGAL::Polygon_mesh_processing::fair ( TriangleMesh &  tmesh,
const VertexRange &  vertices,
const NamedParameters &  np 
)

fairs a region on a triangle mesh.

The points of the selected vertices are relocated to yield an as-smooth-as-possible surface patch, based on solving a linear bi-Laplacian system with boundary constraints, described in [3]. The optional parameter fairing_continuity gives the ability to control the tangential continuity C n of the output mesh.

The region described by vertices might contain multiple disconnected components. Note that the mesh connectivity is not altered in any way, only vertex locations get updated.

Fairing might fail if fixed vertices, which are used as boundary conditions, do not suffice to solve constructed linear system.

Note that if the vertex range to which fairing is applied contains all the vertices of the triangle mesh, fairing does not fail, but the mesh gets shrinked to CGAL::ORIGIN.

Template Parameters
TriangleMesha model of FaceGraph and MutableFaceGraph
VertexRangea range of vertex descriptors of TriangleMesh, model of Range. Its iterator type is InputIterator.
NamedParametersa sequence of Named Parameters
Parameters
tmeshthe triangle mesh with patches to be faired
verticesthe vertices of the patches to be faired (the positions of only those vertices will be changed)
npoptional sequence of Named Parameters among the ones listed below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tmesh. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in TriangleMesh
fairing_continuitytangential continuity of the output surface patch. The larger fairing_continuity gets, the more fixed vertices are required
sparse_linear_solveran instance of the sparse linear solver used for fairing
Returns
true if fairing is successful, otherwise no vertices are relocated
Precondition
is_triangle_mesh(tmesh)
Warning
This function involves linear algebra, that is computed using a non-exact floating-point arithmetic.
Todo:
accuracy of solvers are not good, for example when there is no boundary condition pre_factor should fail, but it does not.

#include <CGAL/Polygon_mesh_processing/fair.h>

Examples:
Polygon_mesh_processing/refine_fair_example.cpp.
template<typename PolygonMesh , typename FaceRange , typename NamedParameters >
void CGAL::Polygon_mesh_processing::isotropic_remeshing ( const FaceRange &  faces,
const double &  target_edge_length,
PolygonMesh &  pmesh,
const NamedParameters &  np 
)

remeshes a triangulated region of a polygon mesh.

This operation sequentially performs edge splits, edge collapses, edge flips, tangential relaxation and projection to the initial surface to generate a smooth mesh with a prescribed edge length.

Template Parameters
PolygonMeshmodel of MutableFaceGraph. The descriptor types boost::graph_traits<PolygonMesh>::face_descriptor and boost::graph_traits<PolygonMesh>::halfedge_descriptor must be models of Hashable. If PolygonMesh has an internal property map for CGAL::face_index_t, and no face_index_map is given as a named parameter, then the internal one must be initialized
FaceRangerange of boost::graph_traits<PolygonMesh>::face_descriptor, model of Range. Its iterator type is ForwardIterator.
NamedParametersa sequence of Named Parameters
Parameters
pmesha polygon mesh with triangulated surface patches to be remeshed
facesthe range of triangular faces defining one or several surface patches to be remeshed
target_edge_lengththe edge length that is targeted in the remeshed patch. If 0 is passed then only the edge-flip, tangential relaxation, and projection steps will be done.
npoptional sequence of Named Parameters among the ones listed below
Precondition
if constraints protection is activated, the constrained edges should not be longer than 4/3*target_edge_length
Named Parameters
geom_traitsa geometric traits class instance, model of Kernel. Exact constructions kernels are not supported by this function.
vertex_point_mapthe property map with the points associated to the vertices of pmesh. Instance of a class model of ReadWritePropertyMap.
face_index_mapa property map containing the index of each face of pmesh
number_of_iterationsthe number of iterations for the sequence of atomic operations performed (listed in the above description)
edge_is_constrained_mapa property map containing the constrained-or-not status of each edge of pmesh. A constrained edge can be split or collapsed, but not flipped, nor its endpoints moved by smoothing. Note that patch boundary edges (i.e. incident to only one face in the range) are always considered as constrained edges.
vertex_is_constrained_mapa property map containing the constrained-or-not status of each vertex of pmesh. A constrained vertex cannot be modified at all during remeshing
protect_constraintsIf true, the edges set as constrained in edge_is_constrained_map (or by default the boundary edges) are not split nor collapsed during remeshing. Note that around constrained edges that have their length higher than twice target_edge_length, remeshing will fail to provide good quality results. It can even fail to terminate because of cascading vertex insertions.
face_patch_mapa property map with the patch id's associated to the faces of faces. Instance of a class model of ReadWritePropertyMap. It gets updated during the remeshing process while new faces are created.
number_of_relaxation_stepsthe number of iterations of tangential relaxation that are performed at each iteration of the remeshing process
relax_constraintsIf true, the end vertices of the edges set as constrained in edge_is_constrained_map and boundary edges move along the constrained polylines they belong to.
See Also
split_long_edges()
Todo:

add possibility to provide a functor that projects to a prescribed surface

Deal with exact constructions Kernel. The only thing that makes sense is to guarantee that the output vertices are exactly on the input surface. To do so, we can do every construction in double, and use an exact process for projection. For each vertex, the AABB_tree would be used in an inexact manner to find the triangle on which projection has to be done. Then, use CGAL::intersection(triangle, line) in the exact constructions kernel to get a point which is exactly on the surface.

#include <CGAL/Polygon_mesh_processing/remesh.h>

Examples:
Polygon_mesh_processing/corefinement_difference_remeshed.cpp, Polygon_mesh_processing/hausdorff_distance_remeshing_example.cpp, and Polygon_mesh_processing/isotropic_remeshing_example.cpp.
template<typename VertexRange , typename TriangleMesh , typename NamedParameters >
void CGAL::Polygon_mesh_processing::random_perturbation ( VertexRange  vertices,
TriangleMesh &  tmesh,
const double &  perturbation_max_size,
const NamedParameters &  np 
)

randomly perturbs the locations of vertices of a triangulated surface mesh.

By default, the vertices are re-projected onto the input surface after perturbation. Note that no geometric checks are done after the perturbation (face orientation might become incorrect and self-intersections might be introduced).

Template Parameters
VertexRangemodel of Range, holding vertices of type boost::graph_traits<TriangleMesh>::vertex_descriptor. Its iterator type is ForwardIterator.
TriangleMeshmodel of MutableFaceGraph.
NamedParametersa sequence of Named Parameters
Parameters
verticesthe range of vertices to be perturbed
tmeshthe triangulated surface mesh
perturbation_max_sizethe maximal length of moves that can be applied to vertices of tmesh.
npoptional sequence of Named Parameters among the ones listed below
Named Parameters
geom_traitsa geometric traits class instance, model of Kernel.
vertex_point_mapthe property map with the points associated to the vertices of tmesh. Instance of a class model of ReadWritePropertyMap.
vertex_is_constrained_mapa property map containing the constrained-or-not status of each vertex of tmesh. A constrained vertex cannot be modified at all during perturbation
do_projecta boolean that sets whether vertices should be reprojected on the input surface after their coordinates random perturbation
random_seeda non-negative integer value to seed the random number generator, and make the perturbation deterministic

#include <CGAL/Polygon_mesh_processing/random_perturbation.h>

template<typename TriangleMesh , typename FaceRange , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters >
std::pair<FaceOutputIterator, VertexOutputIterator> CGAL::Polygon_mesh_processing::refine ( TriangleMesh &  tmesh,
const FaceRange &  faces,
FaceOutputIterator  faces_out,
VertexOutputIterator  vertices_out,
const NamedParameters &  np 
)

refines a region of a triangle mesh

Template Parameters
TriangleMeshmodel of MutableFaceGraph
FaceRangerange of face descriptors, model of Range. Its iterator type is InputIterator.
FaceOutputIteratormodel of OutputIterator holding boost::graph_traits<TriangleMesh>::face_descriptor for patch faces
VertexOutputIteratormodel of OutputIterator holding boost::graph_traits<TriangleMesh>::vertex_descriptor for patch vertices
NamedParametersa sequence of Named Parameters
Parameters
tmeshtriangle mesh with patches to be refined
facesthe range of faces defining the patches to refine
faces_outoutput iterator into which descriptors of new faces are recorded
vertices_outoutput iterator into which descriptors of new vertices are recorded
npoptional sequence of Named Parameters among the ones listed below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tmesh Instance of a class model of ReadWritePropertyMap. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in TriangleMesh
density_control_factorfactor to control density of the output mesh, where larger values lead to denser refinements. The density of vertices of faces_out is this factor times higher than the vertices of faces.
Returns
pair of faces_out and vertices_out
Precondition
is_triangle_mesh(tmesh)
Todo:
current algorithm iterates 10 times at most, since (I guess) there is no termination proof.

#include <CGAL/Polygon_mesh_processing/refine.h>

Examples:
Polygon_mesh_processing/refine_fair_example.cpp.
template<typename PolygonMesh , typename EdgeRange , typename NamedParameters >
void CGAL::Polygon_mesh_processing::split_long_edges ( const EdgeRange &  edges,
const double &  max_length,
PolygonMesh &  pmesh,
const NamedParameters &  np 
)

splits the edges listed in edges into sub-edges that are not longer than the given threshold max_length.

Note this function is useful to split constrained edges before calling isotropic_remeshing() with protection of constraints activated (to match the constrained edge length required by the remeshing algorithm to be guaranteed to terminate)

Template Parameters
PolygonMeshmodel of MutableFaceGraph that has an internal property map for CGAL::vertex_point_t.
EdgeRangerange of boost::graph_traits<PolygonMesh>::edge_descriptor, model of Range. Its iterator type is InputIterator.
NamedParametersa sequence of Named Parameters
Parameters
pmesha polygon mesh
edgesthe range of edges to be split if they are longer than given threshold
max_lengththe edge length above which an edge from edges is split into to sub-edges
npoptional Named Parameters described below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of pmesh. Instance of a class model of ReadWritePropertyMap.
See Also
isotropic_remeshing()

#include <CGAL/Polygon_mesh_processing/remesh.h>

Examples:
Polygon_mesh_processing/isotropic_remeshing_example.cpp.
template<typename PolygonMesh , typename NamedParameters >
bool CGAL::Polygon_mesh_processing::triangulate_face ( typename boost::graph_traits< PolygonMesh >::face_descriptor  f,
PolygonMesh &  pmesh,
const NamedParameters &  np 
)

triangulates a single face of a polygon mesh.

This function depends on the package 2D Triangulation

Template Parameters
PolygonMesha model of FaceListGraph and MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
fface to be triangulated
pmeshthe polygon mesh to which the face to be triangulated belongs
npoptional sequence of Named Parameters among the ones listed below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of pmesh. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in PolygonMesh
geom_traitsa geometric traits class instance
Returns
true if the face has been triangulated.

#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>

template<typename FaceRange , typename PolygonMesh , typename NamedParameters >
bool CGAL::Polygon_mesh_processing::triangulate_faces ( FaceRange  face_range,
PolygonMesh &  pmesh,
const NamedParameters &  np 
)

triangulates given faces of a polygon mesh.

This function depends on the package 2D Triangulation

Template Parameters
FaceRangerange of boost::graph_traits<PolygonMesh>::face_descriptor, model of Range. Its iterator type is InputIterator.
PolygonMesha model of FaceListGraph and MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
face_rangethe range of faces to be triangulated
pmeshthe polygon mesh to be triangulated
npoptional sequence of Named Parameters among the ones listed below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of pmesh. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in PolygonMesh
geom_traitsa geometric traits class instance
Returns
true if all the faces have been triangulated.
See Also
triangulate_face()

#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>

Examples:
Polygon_mesh_processing/triangulate_faces_example.cpp.
template<typename PolygonMesh , typename NamedParameters >
bool CGAL::Polygon_mesh_processing::triangulate_faces ( PolygonMesh &  pmesh,
const NamedParameters &  np 
)

triangulates all faces of a polygon mesh.

This function depends on the package 2D Triangulation

Template Parameters
PolygonMesha model of FaceListGraph and MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
pmeshthe polygon mesh to be triangulated
npoptional sequence of Named Parameters among the ones listed below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of pmesh. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in PolygonMesh
geom_traitsa geometric traits class instance
Returns
true if all the faces have been triangulated.
See Also
triangulate_face()

#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>