Functions to compute the distance between meshes, between a mesh and a point set and between a point set and a mesh.

Functions
template<class PointOutputIterator , class TriangleMesh , class NamedParameters >
PointOutputIterator	CGAL::Polygon_mesh_processing::sample_triangle_mesh (const TriangleMesh &tm, PointOutputIterator out, const NamedParameters &np)

template<class PointOutputIterator , class TriangleRange , class PointRange , class NamedParameters >
PointOutputIterator	CGAL::Polygon_mesh_processing::sample_triangle_soup (const PointRange &points, const TriangleRange &triangles, PointOutputIterator out, const NamedParameters &np)

template<class Concurrency_tag , class TriangleMesh , class NamedParameters1 , class NamedParameters2 >
double	CGAL::Polygon_mesh_processing::approximate_Hausdorff_distance (const TriangleMesh &tm1, const TriangleMesh &tm2, const NamedParameters1 &np1, const NamedParameters2 &np2)

template<class Concurrency_tag , class TriangleMesh , class NamedParameters1 , class NamedParameters2 >
double	CGAL::Polygon_mesh_processing::approximate_symmetric_Hausdorff_distance (const TriangleMesh &tm1, const TriangleMesh &tm2, const NamedParameters1 &np1, const NamedParameters2 &np2)

template<class Concurrency_tag , class TriangleMesh , class PointRange , class NamedParameters >
double	CGAL::Polygon_mesh_processing::max_distance_to_triangle_mesh (const PointRange &points, const TriangleMesh &tm, const NamedParameters &np)

template<class TriangleMesh , class PointRange , class NamedParameters >
double	CGAL::Polygon_mesh_processing::approximate_max_distance_to_point_set (const TriangleMesh &tm, const PointRange &points, const double precision, const NamedParameters &np)

Function Documentation

◆ approximate_Hausdorff_distance()

template<class Concurrency_tag , class TriangleMesh , class NamedParameters1 , class NamedParameters2 >

double CGAL::Polygon_mesh_processing::approximate_Hausdorff_distance	(	const TriangleMesh &	tm1,
		const TriangleMesh &	tm2,
		const NamedParameters1 &	np1,
		const NamedParameters2 &	np2
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

computes the approximate Hausdorff distance from tm1 to tm2 by returning the distance of the farthest point from tm2 amongst a sampling of tm1 generated with the function sample_triangle_mesh() with tm1 and np1 as parameter.

A parallel version is provided and requires the executable to be linked against the Intel TBB library. To control the number of threads used, the user may use the tbb::task_scheduler_init class. See the TBB documentation for more details.

Template Parameters

Concurrency_tag	enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
TriangleMesh	a model of the concepts `EdgeListGraph` and `FaceListGraph`
NamedParameters1	a sequence of Named Parameters for `tm1`
NamedParameters2	a sequence of Named Parameters for `tm2`

Parameters

tm1	the triangle mesh that will be sampled
tm2	the triangle mesh to compute the distance to
np1	optional sequence of Named Parameters for `tm1` passed to `sample_triangle_mesh()`.
np2	optional sequence of Named Parameters for `tm2` among the ones listed below

Named Parameters

vertex_point_map the property map with the points associated to the vertices of tm2 If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in TriangleMesh and in all places where vertex_point_map is used.

The function CGAL::parameters::all_default() can be used to indicate to use the default values for np1 and specify custom values for np2.

Examples: Polygon_mesh_processing/hausdorff_distance_remeshing_example.cpp.

◆ approximate_max_distance_to_point_set()

template<class TriangleMesh , class PointRange , class NamedParameters >

double CGAL::Polygon_mesh_processing::approximate_max_distance_to_point_set	(	const TriangleMesh &	tm,
		const PointRange &	points,
		const double	precision,
		const NamedParameters &	np
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

returns an approximation of the distance between points and the point lying on tm that is the farthest from points

Template Parameters

PointRange	a range of `Point_3`, model of `Range`.
TriangleMesh	a model of the concept `FaceListGraph`
NamedParameters	a sequence of Named Parameters

Parameters

tm	a triangle mesh
points	a range of points
precision	for each triangle of `tm`, the distance of its farthest point from `points` is bounded. A triangle is subdivided into sub-triangles so that the difference of its distance bounds is smaller than `precision`. `precision` must be strictly positive to avoid infinite loops.
np	an optional sequence of Named Parameters among the ones listed below

Named Parameters

vertex_point_map	the property map with the points associated to the vertices of `tm`. If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` must be available for the vertices of `tm`
geom_traits	an instance of a geometric traits class, model of `PMPDistanceTraits`.

Examples: Poisson_surface_reconstruction_3/poisson_reconstruction_example.cpp.

◆ approximate_symmetric_Hausdorff_distance()

template<class Concurrency_tag , class TriangleMesh , class NamedParameters1 , class NamedParameters2 >

double CGAL::Polygon_mesh_processing::approximate_symmetric_Hausdorff_distance	(	const TriangleMesh &	tm1,
		const TriangleMesh &	tm2,
		const NamedParameters1 &	np1,
		const NamedParameters2 &	np2
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

computes the approximate symmetric Hausdorff distance between tm1 and tm2. It returns the maximum of approximate_Hausdorff_distance(tm1, tm2, np1, np2) and approximate_Hausdorff_distance(tm2, tm1, np2, np1).

◆ max_distance_to_triangle_mesh()

template<class Concurrency_tag , class TriangleMesh , class PointRange , class NamedParameters >

double CGAL::Polygon_mesh_processing::max_distance_to_triangle_mesh	(	const PointRange &	points,
		const TriangleMesh &	tm,
		const NamedParameters &	np
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

returns the distance to tm of the point from points that is the furthest from tm.

Template Parameters

PointRange	a range of `Point_3`, model of `Range`. Its iterator type is `RandomAccessIterator`.
TriangleMesh	a model of the concepts `EdgeListGraph` and `FaceListGraph`
NamedParameters	a sequence of Named Parameters

Parameters

points	the range of points of interest
tm	the triangle mesh to compute the distance to
np	an optional sequence of Named Parameters among the ones listed below

Named Parameters

vertex_point_map	the property map with the points associated to the vertices of `tm`. If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` must be available for the vertices of `tm`
geom_traits	an instance of a geometric traits class, model of `PMPDistanceTraits`

◆ sample_triangle_mesh()

template<class PointOutputIterator , class TriangleMesh , class NamedParameters >

PointOutputIterator CGAL::Polygon_mesh_processing::sample_triangle_mesh	(	const TriangleMesh &	tm,
		PointOutputIterator	out,
		const NamedParameters &	np
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

generates points on tm and outputs them to out; the sampling method is selected using named parameters.

Template Parameters

TriangleMesh	a model of the concepts `EdgeListGraph` and `FaceListGraph`
PointOutputIterator	a model of `OutputIterator` holding objects of the same point type as the value type of the point type associated to the mesh `tm`, i.e. the value type of the vertex point map property map, if provided, or the value type of the internal point property map otherwise
NamedParameters	a sequence of Named Parameters

Parameters

tm	the triangle mesh to be sampled
out	output iterator to be filled with sample points
np	an optional sequence of Named Parameters among the ones listed below

Named Parameters

vertex_point_map	the property map with the points associated to the vertices of `tm`. If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` must be available for `TriangleMesh`.
geom_traits	a model of `PMPDistanceTraits`.
use_random_uniform_sampling	if `true` (default value), points are generated in a random and uniform way on the surface of `tm`, and/or on edges of `tm`. For faces, the number of sample points is the value passed to the named parameter `number_of_points_on_faces`. If not set, the value passed to the named parameter `number_of_points_per_area_unit` is multiplied by the area of `tm` to get the number of sample points. If none of these parameters is set, the number of points sampled is `num_vertices(tm)`. For edges, the number of the number of sample points is the value passed to the named parameter `number_of_points_on_edges`. If not set, the value passed to the named parameter `number_of_points_per_distance_unit` is multiplied by the sum of the length of edges of `tm` to get the number of sample points. If none of these parameters is set, the number of points sampled is `num_vertices(tm)`.
use_grid_sampling	if `true`, points are generated on a grid in each triangle, with a minimum of one point per triangle. The distance between two consecutive points in the grid is that of the length of the smallest non-null edge of `tm` or the value passed to the named parameter `grid_spacing`. Edges are also split using the same distance, if requested.
use_monte_carlo_sampling	if `true`, points are generated randomly in each triangle and/or on each edge. For faces, the number of points per triangle is the value passed to the named parameter `number_of_points_per_face`. If not set, the value passed to the named parameter `number_of_points_per_area_unit` is used to pick a number of points per face proportional to the triangle area with a minimum of one point per face. If none of these parameters is set, 2 divided by the square of the length of the smallest non-null edge of `tm` is used as if it was passed to `number_of_points_per_area_unit`. For edges, the number of points per edge is the value passed to the named parameter `number_of_points_per_edge`. If not set, the value passed to the named parameter `number_of_points_per_distance_unit` is used to pick a number of points per edge proportional to the length of the edge with a minimum of one point per face. If none of these parameters is set, 1 divided by the length of the smallest non-null edge of `tm` is used as if it was passed to `number_of_points_per_distance_unit`.
sample_vertices	if `true` (default value), vertices of `tm` are put into `out`.
sample_edges	if `true` (default value), edges of `tm` are sampled.
sample_faces	if `true` (default value), faces of `tm` are sampled.
grid_spacing	a double value used as the grid spacing for the grid sampling method.
number_of_points_on_edges	an unsigned integral value used for the random sampling method as the number of points to pick exclusively on edges.
number_of_points_on_faces	an unsigned integral value used for the random sampling method as the number of points to pick on the surface.
number_of_points_per_distance_unit	a double value used for the random sampling and the Monte Carlo sampling methods to repectively determine the total number of points on edges and the number of points per edge.
number_of_points_per_edge	an unsigned integral value used by the Monte-Carlo sampling method as the number of points per edge to pick.
number_of_points_per_face	an unsigned integral value used by the Monte-Carlo sampling method as the number of points per face to pick.
number_of_points_per_area_unit	a double value used for the random sampling and the Monte Carlo sampling methods to repectively determine the total number of points inside faces and the number of points per face.

See also: CGAL::Polygon_mesh_processing::sample_triangle_soup()

◆ sample_triangle_soup()

template<class PointOutputIterator , class TriangleRange , class PointRange , class NamedParameters >

PointOutputIterator CGAL::Polygon_mesh_processing::sample_triangle_soup	(	const PointRange &	points,
		const TriangleRange &	triangles,
		PointOutputIterator	out,
		const NamedParameters &	np
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

generates points on a triangle soup and puts them to out; the sampling method is selected using named parameters.

Template Parameters

PointRange	a model of the concept `RandomAccessContainer` whose value type is the point type.
TriangleRange	a model of the concept `RandomAccessContainer` whose value_type is itself a model of the concept `RandomAccessContainer` whose value_type is an unsigned integral value.
PointOutputIterator	a model of `OutputIterator` holding objects of the same type as `PointRange`'s value type
NamedParameters	a sequence of Named Parameters

Parameters

points	the points of the soup
triangles	a `TriangleRange` containing the triangles of the soup to be sampled
out	output iterator to be filled with sample points
np	an optional sequence of Named Parameters among the ones listed below

Named Parameters

geom_traits	a model of `PMPDistanceTraits`, whose `Point_3` type is the same as `PointRange`'s `value_type`.
use_random_uniform_sampling	if `true`, points are generated in a random and uniform way over the triangles of the soup. The number of sample points is the value passed to the named parameter `number_of_points_on_faces`. If not set, the value passed to the named parameter `number_of_points_per_area_unit` is multiplied by the area of the soup to get the number of sample points. If none of these parameters is set, the number of points sampled is `points.size()`. Default is `true`.
use_grid_sampling	if `true`, points are generated on a grid in each triangle, with a minimum of one point per triangle. The distance between two consecutive points in the grid is that of the length of the smallest non-null edge of the soup, or the value passed to the named parameter `grid_spacing`. Default is `false`.
use_monte_carlo_sampling	if `true`, points are generated randomly in each triangle. The number of points per triangle is the value passed to the named parameter `number_of_points_per_face`. If not set, the value passed to the named parameter `number_of_points_per_area_unit` is used to pick a number of points per face proportional to the triangle area with a minimum of one point per face. If none of these parameters is set, the number of points per area unit is set to 2 divided by the square of the length of the smallest non-null edge of the soup. Default is `false`.
sample_vertices	if `true`, the points of `points` are put into `out`. Default is `true`.
grid_spacing	a double value used as the grid spacing for the grid sampling method.
number_of_points_on_faces	an unsigned integral value used for the random sampling method as the number of points to pick on the surface.
number_of_points_per_face	an unsigned integral value used by the Monte-Carlo sampling method as the number of points per triangle to pick.
number_of_points_per_area_unit	a double value used for the random sampling and the Monte Carlo sampling methods to repectively determine the total number of points inside triangles and the number of points per triangle.

Attention: Contrary to sample_triangle_mesh(), this method does not allow to sample edges.

See also: CGAL::Polygon_mesh_processing::sample_triangle_mesh()