Triangulated Surface Mesh Approximation Reference

Pierre Alliez, David Cohen-Steiner, Lingjie Zhu

This package implements the Variational Shape Approximation method to approximate an input surface triangle mesh by a simpler surface triangle mesh. The algorithm proceeds by iterative clustering of triangles, the clustering process being seeded randomly, incrementally or hierarchically. While the default function runs an automated version of the algorithm, interactive control is possible via a class interface. The API is flexible and can be extended to user-defined proxies and error metrics.

Introduced in: CGAL 4.14
BibTeX: cgal:az-tsma-20b
Depends on: Eigen
License: GPL
Windows Demo: Polyhedron demo
Common Demo Dlls: dlls

Classified Reference Pages

Parameters

Optional parameters of the functions of this package are implemented as BGL named parameters. The page BGL Named Parameters describes their usage.

Concepts

• ErrorMetricProxy

Main Functions

• CGAL::Surface_mesh_approximation::approximate_triangle_mesh()

Classes

• CGAL::Surface_mesh_approximation::L21_metric_plane_proxy
• CGAL::Surface_mesh_approximation::L2_metric_plane_proxy

• CGAL::Variational_shape_approximation

  Todo:

  add option to enforce guarantee of 2-manifold and oriented output mesh

  add option to smooth frontiers of the partition

  add option to smooth and mutual tessellate frontiers of the partition

  add function in the class interface to optimize, after meshing, the anchor point locations to minimize a user-defined metric (two-sided L1, two-sided L2, Wasserstein distance, etc).

  add simulated annealing and combined operations to reach better minima.

Modules
	Concepts

Classes
class	CGAL::Surface_mesh_approximation::L21_metric_plane_proxy< TriangleMesh, VertexPointMap, GeomTraits >
	Approximation L21 metric of vector proxy. More...
class	CGAL::Surface_mesh_approximation::L2_metric_plane_proxy< TriangleMesh, VertexPointMap, GeomTraits >
	Approximation L2 metric of plane proxy. More...
class	CGAL::Variational_shape_approximation< TriangleMesh, VertexPointMap, ErrorMetricProxy, GeomTraits, Concurrency_tag >
	Main class for Variational Shape Approximation algorithm. It is based on [1]. For simple use cases, the function CGAL::Surface_mesh_approximation::approximate_mesh() might be sufficient. More...

Enumerations
enum	CGAL::Surface_mesh_approximation::Verbose_level { CGAL::Surface_mesh_approximation::SILENT, CGAL::Surface_mesh_approximation::MAIN_STEPS, CGAL::Surface_mesh_approximation::VERBOSE }
	Verbose level enumeration. More...
enum	CGAL::Surface_mesh_approximation::Seeding_method { CGAL::Surface_mesh_approximation::RANDOM, CGAL::Surface_mesh_approximation::INCREMENTAL, CGAL::Surface_mesh_approximation::HIERARCHICAL }
	Seeding method enumeration for Variational Shape Approximation algorithm. More...

Functions
template<typename TriangleMesh , typename NamedParameters >
bool	CGAL::Surface_mesh_approximation::approximate_triangle_mesh (const TriangleMesh &tm, const NamedParameters &np)
	approximates the input mesh with plane proxies. This function uses the Variational Shape Approximation algorithm described in [1] to approximate a triangle surface mesh, with indexed triangles as output. More...

Enumeration Type Documentation

Seeding_method

enum CGAL::Surface_mesh_approximation::Seeding_method

#include <CGAL/Variational_shape_approximation.h>

Seeding method enumeration for Variational Shape Approximation algorithm.

Enumerator
RANDOM	Random seeding.
INCREMENTAL	Incremental seeding.
HIERARCHICAL	Hierarchical seeding.

Verbose_level

enum CGAL::Surface_mesh_approximation::Verbose_level

#include <CGAL/Surface_mesh_approximation/approximate_triangle_mesh.h>

Verbose level enumeration.

Enumerator
SILENT	Silent.
MAIN_STEPS	Main steps.
VERBOSE	Verbose.

Function Documentation

approximate_triangle_mesh()

template<typename TriangleMesh , typename NamedParameters >

bool CGAL::Surface_mesh_approximation::approximate_triangle_mesh	(	const TriangleMesh &	tm,
		const NamedParameters &	np
	)

#include <CGAL/Surface_mesh_approximation/approximate_triangle_mesh.h>

approximates the input mesh with plane proxies. This function uses the Variational Shape Approximation algorithm described in [1] to approximate a triangle surface mesh, with indexed triangles as output.

Template Parameters

TriangleMesh	model of FaceListGraph
NamedParameters	a sequence of BGL Named Parameters

Parameters

tm	triangle surface mesh to be approximated
np	an optional sequence of Named Parameters among the ones listed below

Returns

true if the indexed triangles represent a 2-manifold, oriented surface mesh, and false otherwise.

Approximation Named Parameters

geom_traits an instance of a geometric traits class Type: a model of Kernel Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits Extra: Exact constructions kernels are not supported by this function.
vertex_point_map a property map associating points to the vertices of tm Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, tm) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in TriangleMesh.
verbose_level the verbose level Type: CGAL::Surface_mesh_approximation::Verbose_level Default: CGAL::Surface_mesh_approximation::SILENT
seeding_method the selection of seeding method Type: CGAL::Surface_mesh_approximation::Seeding_method Default: CGAL::Surface_mesh_approximation::HIERARCHICAL
max_number_of_proxies the maximum number of proxies used to approximate the input mesh Type: std::size_t Default: num_faces(tm) / 3, used when min_error_drop is also not provided
min_error_drop the minimum error drop of the approximation, expressed as the ratio between two iterations of proxy addition Type: geom_traits::FT Default: 0.1, used when max_number_of_proxies is also not provided
number_of_relaxations the number of relaxation iterations interleaved within seeding Type: std::size_t Default: 5
number_of_iterations the number of partitioning and fitting iterations after seeding Type: std::size_t Default: std::min(std::max(number_of_faces / max_number_of_proxies, 20), 60)

Meshing Named Parameters

subdivision_ratio the chord subdivision ratio threshold to the chord length or average edge length Type: geom_traits::FT Default: 5.0
relative_to_chord If true, the subdivision_ratio is the ratio of the furthest vertex distance to the chord length, otherwise is the average edge length Type: Boolean Default: false
with_dihedral_angle If true, the subdivision_ratio is weighted by dihedral angle Type: Boolean Default: false
optimize_anchor_location If true, optimize the anchor locations Type: Boolean Default: true
pca_plane If true, use PCA plane fitting, otherwise use the default area averaged plane parameters Type: Boolean Default: false

Output Named Parameters

face_proxy_map a property map to output the proxy index of each face of the input polygon mesh Type: a model of WritablePropertyMap with boost::graph_traits<TriangleMesh>::face_descriptor as key and std::size_t as value type Default: no output operation is performed Extra: A proxy is a set of connected faces which are placed under the same proxy patch (see fig__iterations) Extra: The proxy-ids are contiguous in range [0, number_of_proxies - 1]
proxies an OutputIterator to put proxies in Type: a class model of OutputIterator with CGAL::Surface_mesh_approximation::L21_metric_vector_proxy_no_area_weighting::Proxy value type Default: no output operation is performed
anchors an OutputIterator to put anchor points in Type: a class model of OutputIterator with geom_traits::Point_3 value type Default: no output operation is performed
triangles an OutputIterator to put indexed triangles in Type: a class model of OutputIterator with std::array<std::size_t, 3> value type Default: no output operation is performed

Examples

Surface_mesh_approximation/vsa_approximation_2_example.cpp, Surface_mesh_approximation/vsa_approximation_example.cpp, Surface_mesh_approximation/vsa_segmentation_example.cpp, and Surface_mesh_approximation/vsa_simple_approximation_example.cpp.