Collection of algorithms of point set processing (smoothing, simplification, etc.).

Classes
struct	CGAL::pointmatcher::ICP_config
	The class `ICP_config` is designed to handle preparing and passing configurations to the registration methods `CGAL::pointmatcher::compute_registration_transformation()` and `CGAL::pointmatcher::register_point_sets()`. More...

class	CGAL::Point_set_with_structure< Kernel >
	A 3D point set with structure information based on a set of detected planes. More...

Functions
template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
double	CGAL::bilateral_smooth_point_set (PointRange &points, unsigned int k, const NamedParameters &np)

template<typename ConcurrencyTag , typename PointRange , typename CGAL_BGL_NP_TEMPLATE_PARAMETERS >
FT	CGAL::compute_average_spacing (const PointRange &points, unsigned int k, const CGAL_BGL_NP_CLASS &np)

template<typename ConcurrencyTag , typename PointRange , typename OutputIterator , typename NamedParameters >
OutputIterator	CGAL::edge_aware_upsample_point_set (const PointRange &points, OutputIterator output, const NamedParameters &np)

template<typename PointRange , typename QueryPointRange , typename OutputIterator , typename NamedParameters >
OutputIterator	CGAL::estimate_local_k_neighbor_scales (const PointRange &points, const QueryPointRange &queries, OutputIterator output, const NamedParameters &np)

template<typename PointRange , typename NamedParameters >
std::size_t	CGAL::estimate_global_k_neighbor_scale (const PointRange &points, const NamedParameters &np)

template<typename PointRange , typename QueryPointRange , typename OutputIterator , typename NamedParameters >
OutputIterator	CGAL::estimate_local_range_scales (const PointRange &points, const QueryPointRange &queries, OutputIterator output, const NamedParameters &np)

template<typename PointRange , typename NamedParameters >
FT	CGAL::estimate_global_range_scale (const PointRange &points, const NamedParameters &np)

template<typename PointRange , typename NamedParameters >
PointRange::iterator	CGAL::grid_simplify_point_set (PointRange &points, double epsilon, const NamedParameters &np)

template<typename PointRange , typename NamedParameters >
PointRange::iterator	CGAL::hierarchy_simplify_point_set (PointRange &points, const NamedParameters &np)

template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
void	CGAL::jet_estimate_normals (PointRange &points, unsigned int k, const NamedParameters &np)

template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
void	CGAL::jet_smooth_point_set (PointRange &points, unsigned int k, const NamedParameters &np)

template<typename PointRange , typename NamedParameters >
PointRange::iterator	CGAL::mst_orient_normals (PointRange &points, unsigned int k, const NamedParameters &np)

template<class PointRange1 , class PointRange2 , class NamedParameters1 , class NamedParameters2 >
std::pair< geom_traits::Aff_transformation_3, double >	CGAL::OpenGR::compute_registration_transformation (const PointRange1 &point_set_1, const PointRange2 &point_set_2, const NamedParameters1 &np1, const NamedParameters2 &np2)

template<class PointRange1 , class PointRange2 , class NamedParameters1 , class NamedParameters2 >
double	CGAL::OpenGR::register_point_sets (const PointRange1 &point_set_1, PointRange2 &point_set_2, const NamedParameters1 &np1, const NamedParameters2 &np2)

template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
void	CGAL::pca_estimate_normals (PointRange &points, unsigned int k, const NamedParameters &np)

template<class PointRange1 , class PointRange2 , class NamedParameters1 , class NamedParameters2 >
std::pair< geom_traits::Aff_transformation_3, bool >	CGAL::pointmatcher::compute_registration_transformation (const PointRange1 &point_set_1, const PointRange2 &point_set_2, const NamedParameters1 &np1, const NamedParameters2 &np2)

template<class PointRange1 , class PointRange2 , class NamedParameters1 , class NamedParameters2 >
bool	CGAL::pointmatcher::register_point_sets (const PointRange1 &point_set_1, PointRange2 &point_set_2, const NamedParameters1 &np1, const NamedParameters2 &np2)

template<typename PointRange >
PointRange::iterator	CGAL::random_simplify_point_set (PointRange &points, double removed_percentage)

template<typename PointRange , typename NamedParameters >
PointRange::iterator	CGAL::remove_outliers (PointRange &points, unsigned int k, const NamedParameters &np)

template<typename PointRange , typename PlaneRange , typename OutputIterator , typename NamedParameters >
OutputIterator	CGAL::structure_point_set (const PointRange &points, const PlaneRange &planes, OutputIterator output, double epsilon, const NamedParameters &np)

template<class FT , class VCMTraits >
bool	CGAL::vcm_is_on_feature_edge (std::array< FT, 6 > &cov, double threshold, VCMTraits)

template<typename PointRange , typename NamedParameters >
void	CGAL::compute_vcm (const PointRange &points, std::vector< std::array< double, 6 > > &ccov, double offset_radius, double convolution_radius, const NamedParameters &np)

template<typename PointRange , typename NamedParameters >
void	CGAL::vcm_estimate_normals (PointRange &points, double offset_radius, double convolution_radius, const NamedParameters &np)

template<typename PointRange , typename NamedParameters >
void	CGAL::vcm_estimate_normals (PointRange &points, double offset_radius, unsigned int k, const NamedParameters &np)

template<typename ConcurrencyTag , typename PointRange , typename OutputIterator , typename NamedParameters >
OutputIterator	CGAL::wlop_simplify_and_regularize_point_set (PointRange &points, OutputIterator output, const NamedParameters &np)

Function Documentation

◆ bilateral_smooth_point_set()

template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >

double CGAL::bilateral_smooth_point_set	(	PointRange &	points,
		unsigned int	k,
		const NamedParameters &	np
	)

#include <CGAL/bilateral_smooth_point_set.h>

This function smooths an input point set by iteratively projecting each point onto the implicit surface patch fitted over its nearest neighbors. Bilateral projection preserves sharp features according to the normal (gradient) information. Both point positions and normals will be modified. For more details, please see section 4 in [5].

A parallel version of this function 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.

Precondition: Normals must be unit vectors; k >= 2

Template Parameters

ConcurrencyTag	enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
PointRange	is a model of `Range`. The value type of its iterator is the key type of the named parameter `point_map`.

Parameters

points	input point range.
k	size of the neighborhood for the implicit surface patch fitting. The larger the value is, the smoother the result will be.
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadWritePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadWritePropertyMap` with value type `geom_traits::Vector_3`.
neighbor_radius	spherical neighborhood radius. If provided, the neighborhood of a query point is computed with a fixed spherical radius instead of a fixed number of neighbors. In that case, the parameter `k` is used as a limit on the number of points returned by each spherical query (to avoid overly large number of points in high density areas). If no limit is wanted, use `k=0`.
sharpness_angle	controls the sharpness of the result.
callback	an instance of `std::function<bool(double)>`. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns `true`, then the algorithm continues its execution normally; if it returns `false`, the algorithm is stopped, all points are left unchanged and the function return `NaN`.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Returns: Average point movement error. It's a convergence criterium for the algorithm. This value can help the user to decide how many iterations are sufficient.

◆ compute_average_spacing()

template<typename ConcurrencyTag , typename PointRange , typename CGAL_BGL_NP_TEMPLATE_PARAMETERS >

FT CGAL::compute_average_spacing	(	const PointRange &	points,
		unsigned int	k,
		const CGAL_BGL_NP_CLASS &	np
	)

#include <CGAL/compute_average_spacing.h>

Computes average spacing from k nearest neighbors.

Precondition: k >= 2.

Template Parameters

ConcurrencyTag	enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
PointRange	is a model of `ConstRange`. The value type of its iterator is the key type of the named parameter `point_map`.

Parameters

points	input point range.
k	number of neighbors.
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
callback	an instance of `std::function<bool(double)>`. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns `true`, then the algorithm continues its execution normally; if it returns `false`, the algorithm is stopped and the average spacing value estimated on the processed subset is returned.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Returns: average spacing (scalar). The return type FT is a number type. It is either deduced from the geom_traits Named Parameters if provided, or the geometric traits class deduced from the point property map of points.

◆ compute_registration_transformation() [1/2]

template<class PointRange1 , class PointRange2 , class NamedParameters1 , class NamedParameters2 >

std::pair<geom_traits::Aff_transformation_3, double> CGAL::OpenGR::compute_registration_transformation	(	const PointRange1 &	point_set_1,
		const PointRange2 &	point_set_2,
		const NamedParameters1 &	np1,
		const NamedParameters2 &	np2
	)

#include <CGAL/OpenGR/compute_registration_transformation.h>

Computes the registration of point_set_2 with respect to point_set_1 and returns the corresponding affine transformation along with the registration score.

Registration is computed using the Super4PCS algorithm [9].

Note: This function requires the thirdpartyOpenGR library.

Warning: Although this may seem counter-intuitive, if one of the two point set matches only a small section of the other one, it is advised to use the small point set as reference instead of the big one. The reason is that the reference point set is used to construct a base that is sought after in the other point set: if the big point set is used as reference, chances are the constructed base will not be present in the small point set.

Template Parameters

PointRange1	is a model of `Range`. The value type of its iterator is the key type of the named parameter `point_map` in `NamedParameters1`.
PointRange2	is a model of `Range`. The value type of its iterator is the key type of the named parameter `point_map` in `NamedParameters2`.

Parameters

point_set_1	input point range used as reference.
point_set_2	input point range whose registration w.r.t. `point_set_1` will be computed.
np1	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange1` and whose value type is `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange1` and whose value type `geom_traits::Vector_3`.
number_of_samples	size of the subset of input points used to compute registration. Input clouds are sub-sampled prior exploration, to ensure fast computations. Super4PCS has a linear complexity w.r.t. the number of input samples, allowing to use larger values than 4PCS. Simple geometry with large overlap can be matched with only 200 samples. However, with Super4PCS, smaller details can be used during the process by using up to thousands of points. There is no theoretical limit to this parameter, however using too large values leads to very a large congruent set, which requires more time and memory to be explored. Using a large number of samples is recommended when: geometrical details are required to perform the matching, for instance to disambiguate between several similar configurations; the clouds have a very low overlap: using a too sparse sampling can prevent to have samples in the overlapping area, causing the algorithm to fail; the clouds are very noisy, and require a dense sampling. Note that Super4PCS is a global registration algorithm, which finds a good approximate of the rigid transformation aligning too clouds. Increasing the number of samples in order to get a fine registration is not optimal: it is usually faster to use less samples, and refine the transformation using a local algorithm, like the ICP, or its variant SparseICP.
maximum_normal_deviation	angle threshold (in degrees) used to filter pairs of points according to their normal consistency. Small values decrease computation time but may also decrease the quality if pairs of points that should match have a normal deviation higher than the threshold.
accuracy	registration accuracy (delta in the paper). Setting a small value means that the two clouds needs to be very close to be considered as well aligned. It is expressed in scene units. A simple way to understand its impact is to consider the computation of the Largest Common Pointset (LCP), the metric used to verify how much the clouds are aligned. For each transformation matrix produced by Super4PCS, we compute the LCP measure by considering a shell around the reference cloud, and count the percentage of points of the target cloud lying in the shell. The thickness of the shell is defined by the parameter delta.
overlap	ratio of expected overlap between the two point sets: it is ranging between 0 (no overlap) to 1 (100% overlap). The overlap parameter controls the size of the basis used for registration. Usually, the larger the overlap, the faster the algorithm. When the overlap is unknown, a simple way to set this parameter is to start from 100% overlap, and decrease the value until obtaining a good result. Using too small values will slow down the algorithm, and reduce the accuracy of the result.
maximum_running_time	maximum number of seconds after which the algorithm stops. Super4PCS explores the transformation space to align the two input clouds. Since the exploration is performed randomly, it is recommended to use a large time value to explore the whole space.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Parameters

np2	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange2` and whose value type is `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange2` and whose value type `geom_traits::Vector_3`.

Returns: a pair containing the affine transformation that should be applied to point_set_2 to make it registered w.r.t. point_set_1 and the registration score.

Examples: Point_set_processing_3/registration_with_OpenGR.cpp, and Point_set_processing_3/registration_with_opengr_pointmatcher_pipeline.cpp.

◆ compute_registration_transformation() [2/2]

template<class PointRange1 , class PointRange2 , class NamedParameters1 , class NamedParameters2 >

std::pair<geom_traits::Aff_transformation_3, bool> CGAL::pointmatcher::compute_registration_transformation	(	const PointRange1 &	point_set_1,
		const PointRange2 &	point_set_2,
		const NamedParameters1 &	np1,
		const NamedParameters2 &	np2
	)

#include <CGAL/pointmatcher/compute_registration_transformation.h>

Computes the registration of point_set_2 with respect to point_set_1 and returns the corresponding affine transformation. Registration is computed using the Iterative Closest Point (ICP) algorithm.

Note: This function requires the thirdpartylibpointmatcher library.

Template Parameters

PointRange1	is a model of `Range`. The value type of its iterator is the key type of the named parameter `point_map` in `NamedParameters1`.
PointRange2	is a model of `Range`. The value type of its iterator is the key type of the named parameter `point_map` in `NamedParameters2`.

Parameters

point_set_1 input point range used as reference.

point_set_2 input point range whose registration w.r.t. point_set_1 will be computed.

np1

optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange1` and whose value type is `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange1` and whose value type `geom_traits::Vector_3`.
point_set_filters	is a model of `Range`. The value type of its iterator is `ICP_config`. The chain of filters to be applied to the reference point cloud. The reference point cloud is processed into an intermediate point cloud with the given chain of filters to be used in the alignment procedure. The chain is organized with the forward traversal order of the point set filters range. The chain of point set filters are applied only once at the beginning of the ICP procedure, i.e., before the first iteration of the ICP algorithm. The filters can have several purposes, including but are not limited to i) removal of noisy points which render alignment of point clouds difficult, ii) removal of redundant points so as to speed up alignment, iii) addition of descriptive information to the points such as a surface normal vector, or the direction from the point to the sensor. Corresponds to `referenceDataPointsFilters` configuration module of thirdpartylibpointmatcher library. The filters should be chosen and set from possible components of the `referenceDataPointsFilters` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `RandomSamplingDataPointsFilter` is used.
matcher	is a model of `ICP_config`. The method used for matching (linking) the points from `point_set_2`, to the points in the reference cloud, `point_set_1`. Corresponds to `matcher` configuration module of thirdpartylibpointmatcher library. The matcher should be chosen and set from possible components of the `matcher` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `KDTreeMatcher` is used.
outlier_filters	is a model of `Range`. The value type of its iterator is `ICP_config`. The chain of filters to be applied to the matched (linked) point clouds after each processing iteration of the ICP algorithm to remove the links which do not correspond to true point correspondences. The outliers are rejected. Points with no link are ignored in the subsequent error minimization step. The chain is organized with the forward traversal order of the outlier filters range. Corresponds to `outlierFilters` configuration module of thirdpartylibpointmatcher library. The filters should be chosen and set from possible components of the `outlierFilters` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `TrimmedDistOutlierFilter` is used.
error_minimizer	is a model of `ICP_config`. The error minimizer that computes a transformation matrix such as to minimize the error between the point sets. Corresponds to `errorMinimizer` configuration module of thirdpartylibpointmatcher library. The error minimizer should be chosen and set from possible components of the `errorMinimizer` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `PointToPlaneErrorMinimizer` is used.
transformation_checkers	is a model of `Range`. The value type of its iterator is `ICP_config`. The chain of transformation checkers. A transformation checker can stop the iteration depending on the conditions it defines. The chain is organized with the forward traversal order of the transformation checkers range. Corresponds to `transformationCheckers` configuration module of thirdpartylibpointmatcher library. The transformation checkers should be chosen and set from possible components of the `transformationCheckers` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, the chain of `CounterTransformationChecker` and `DifferentialTransformationChecker` is used.
inspector	is a model of `ICP_config`. The inspector allows to log data at different steps for analysis. Inspectors typically provide deeper scrutiny than the logger. Corresponds to `inspector` configuration module of thirdpartylibpointmatcher library. The inspector should be chosen and set from possible components of the `inspector` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `NullInspector` is used.
logger	is a model of `ICP_config`. The method for logging information regarding the registration process outputted by thirdpartylibpointmatcher library. The logs generated by CGAL library does not get effected by this configuration. Corresponds to `logger` configuration module of thirdpartylibpointmatcher library. The logger should be chosen and set from possible components of the `logger` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `NullLogger` is used.
geom_traits	an instance of a geometric traits class, model of `Kernel`

np2

optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange2` and whose value type is `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange2` and whose value type `geom_traits::Vector_3`.
point_set_filters	is a model of `Range`. The value type of its iterator is `ICP_config`. The chain of filters to be applied to the point cloud, `point_set_2`. The point cloud is processed into an intermediate point cloud with the given chain of filters to be used in the alignment procedure. The chain is organized with the forward traversal order of the point set filters range. The chain of point set filters are applied only once at the beginning of the ICP procedure, i.e., before the first iteration of ICP algorithm. The filters can have several purposes, including but are not limited to i) removal of noisy points which render alignment of point clouds difficult, ii) removal of redundant points so as to speed up alignment, iii) addition of descriptive information to the points such as a surface normal vector, or the direction from the point to the sensor. Corresponds to `readingDataPointsFilters` configuration module of thirdpartylibpointmatcher library. The filters should be chosen and set from possible components of the `readingDataPointsFilters` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `SamplingSurfaceNormalDataPointsFilter` is used.
transformation	The affine transformation that is used as the initial transformation for `point_set_2`. If this parameter is omitted, identity transformation is used.

Returns: a pair containing the affine transformation that should be applied to point_set_2 to make it registered w.r.t. point_set_1 and the boolean value indicating if the registration converged. The second of the pair is true if converged, false otherwise. A log why it failed to converge is written to std::cerr if the registration cannot converge.

Examples: Point_set_processing_3/registration_with_pointmatcher.cpp.

◆ compute_vcm()

template<typename PointRange , typename NamedParameters >

void CGAL::compute_vcm	(	const PointRange &	points,
		std::vector< std::array< double, 6 > > &	ccov,
		double	offset_radius,
		double	convolution_radius,
		const NamedParameters &	np
	)

#include <CGAL/vcm_estimate_normals.h>

computes the Voronoi Covariance Measure (VCM) of a point cloud, a construction that can be used for normal estimation and sharp feature detection.

The VCM associates to each point the covariance matrix of its Voronoi cell intersected with the ball of radius offset_radius. In addition, if the second radius convolution_radius is positive, the covariance matrices are smoothed via a convolution process. More specifically, each covariance matrix is replaced by the average of the matrices of the points located at a distance at most convolution_radius. The choice for parameter offset_radius should refer to the geometry of the underlying surface while the choice for parameter convolution_radius should refer to the noise level in the point cloud. For example, if the point cloud is a uniform and noise-free sampling of a smooth surface, offset_radius should be set to the minimum local feature size of the surface, while convolution_radius can be set to zero.

The Voronoi covariance matrix of each vertex is stored in an array a of length 6 and is as follow:

\( \begin{bmatrix} a[0] & a[1] & a[2] \\ a[1] & a[3] & a[4] \\ a[2] & a[4] & a[5] \\ \end{bmatrix}\)

Template Parameters

PointRange is a model of Range. The value type of its iterator is the key type of the named parameter point_map.

Parameters

points	input point range.
ccov	output range of covariance matrices.
offset_radius	offset_radius.
convolution_radius	convolution_radius.
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
geom_traits	an instance of a geometric traits class, model of `Kernel`

See also: CGAL::vcm_is_on_feature_edge(); CGAL::vcm_estimate_normals()

Examples: Point_set_processing_3/edges_example.cpp.

◆ edge_aware_upsample_point_set()

template<typename ConcurrencyTag , typename PointRange , typename OutputIterator , typename NamedParameters >

OutputIterator CGAL::edge_aware_upsample_point_set	(	const PointRange &	points,
		OutputIterator	output,
		const NamedParameters &	np
	)

#include <CGAL/edge_aware_upsample_point_set.h>

This method progressively upsamples the point set while approaching the edge singularities (detected by normal variation), which generates a denser point set from an input point set. This has applications in point-based rendering, hole filling, and sparse surface reconstruction. Normals of points are required as input. For more details, please refer to [5].

Template Parameters

ConcurrencyTag	enables sequential versus parallel versions of `compute_average_spacing()` (called internally). Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
PointRange	is a model of `ConstRange`. The value type of its iterator is the key type of the named parameter `point_map`.
OutputIterator	Type of the output iterator. The type of the objects put in it is `std::pair<geom_traits::Point_3, geom_traits::Vector_3>`. Note that the user may use a function_output_iterator to match specific needs.

Parameters

points	input point range.
output	iterator where output points and normals are put.
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadablePropertyMap` with value type `geom_traits::Vector_3`.
sharpness_angle	controls the sharpness of the result.
edge_sensitivity	controls the priority of points inserted along sharp features. See section Parameter: edge_sensitivity for an example.
neighbor_radius	spherical neighborhood radius.
number_of_output_points	is the number of output points to generate.
geom_traits	an instance of a geometric traits class, model of `Kernel`

◆ estimate_global_k_neighbor_scale()

template<typename PointRange , typename NamedParameters >

std::size_t CGAL::estimate_global_k_neighbor_scale	(	const PointRange &	points,
		const NamedParameters &	np
	)

#include <CGAL/estimate_scale.h>

Estimates the global scale in a K nearest neighbors sense. The computed scale corresponds to the smallest scale such that the K subsets of points have the appearance of a surface in 3D or the appearance of a curve in 2D (see Automatic Scale Estimation).

Template Parameters

PointRange is a model of ConstRange. The value type of its iterator is the key type of the named parameter point_map.

Parameters

points	input point range.
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3` (or `geom_traits::Point_2`). If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` (or `CGAL::Identity_property_map<geom_traits::Point_2>`) is used.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Note: This function accepts both 2D and 3D points.

Returns: The estimated scale in the K nearest neighbors sense.

Examples: Point_set_processing_3/scale_estimation_example.cpp.

◆ estimate_global_range_scale()

template<typename PointRange , typename NamedParameters >

FT CGAL::estimate_global_range_scale	(	const PointRange &	points,
		const NamedParameters &	np
	)

#include <CGAL/estimate_scale.h>

Estimates the global scale in a range sense. The computed scale corresponds to the smallest scale such that the subsets of points inside the sphere range have the appearance of a surface in 3D or the appearance of a curve in 2D (see Automatic Scale Estimation).

Template Parameters

PointRange is a model of ConstRange. The value type of its iterator is the key type of the named parameter point_map.

Parameters

points	input point range.
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3` (or `geom_traits::Point_2`). If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` (or `CGAL::Identity_property_map<geom_traits::Point_2>`) is used.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Note: This function accepts both 2D and 3D points.

Returns: The estimated scale in the range sense. The return type FT is a number type. It is either deduced from the geom_traits Named Parameters if provided, or the geometric traits class deduced from the point property map of points.

Examples: Point_set_processing_3/scale_estimation_example.cpp.

◆ estimate_local_k_neighbor_scales()

template<typename PointRange , typename QueryPointRange , typename OutputIterator , typename NamedParameters >

OutputIterator CGAL::estimate_local_k_neighbor_scales	(	const PointRange &	points,
		const QueryPointRange &	queries,
		OutputIterator	output,
		const NamedParameters &	np
	)

#include <CGAL/estimate_scale.h>

Estimates the local scale in a K nearest neighbors sense on a set of user-defined query points. The computed scales correspond to the smallest scales such that the K subsets of points have the appearance of a surface in 3D or the appearance of a curve in 2D (see Automatic Scale Estimation).

Template Parameters

PointRange	is a model of `ConstRange`. The value type of its iterator is the key type of the named parameter `point_map`.
QueryPointRange	is a model of `ConstRange`. The value type of its iterator is the key type of the named parameter `query_point_map`.
OutputIterator	is used to store the computed scales. It accepts values of type `std::size_t`.

Parameters

points	input point range.
queries	range of locations where scale must be estimated
output	iterator to store the computed scales
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3` (or `geom_traits::Point_2`). If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` (or `CGAL::Identity_property_map<geom_traits::Point_2>`) is used.
query_point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3` (or `geom_traits::Point_2`). If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` (or `CGAL::Identity_property_map<geom_traits::Point_2>`) is used.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Note: This function accepts both 2D and 3D points, but sample points and query must have the same dimension.

Examples: Point_set_processing_3/scale_estimation_2d_example.cpp.

◆ estimate_local_range_scales()

template<typename PointRange , typename QueryPointRange , typename OutputIterator , typename NamedParameters >

OutputIterator CGAL::estimate_local_range_scales	(	const PointRange &	points,
		const QueryPointRange &	queries,
		OutputIterator	output,
		const NamedParameters &	np
	)

#include <CGAL/estimate_scale.h>

Estimates the local scale in a range sense on a set of user-defined query points. The computed scales correspond to the smallest scales such that the subsets of points included in the sphere range have the appearance of a surface in 3D or the appearance of a curve in 2D (see Automatic Scale Estimation).

Template Parameters

PointRange	is a model of `ConstRange`. The value type of its iterator is the key type of the named parameter `point_map`.
QueryPointRange	is a model of `ConstRange`. The value type of its iterator is the key type of the named parameter `query_point_map`.
OutputIterator	is used to store the computed scales. It accepts values of type `geom_traits::FT`.

Parameters

points	input point range.
queries	range of locations where scale must be estimated
output	iterator to store the computed scales
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3` (or `geom_traits::Point_2`). If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` (or `CGAL::Identity_property_map<geom_traits::Point_2>`) is used.
query_point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3` (or `geom_traits::Point_2`). If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` (or `CGAL::Identity_property_map<geom_traits::Point_2>`) is used.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Note: This function accepts both 2D and 3D points, but sample points and query must have the same dimension.

◆ grid_simplify_point_set()

template<typename PointRange , typename NamedParameters >

PointRange::iterator CGAL::grid_simplify_point_set	(	PointRange &	points,
		double	epsilon,
		const NamedParameters &	np
	)

#include <CGAL/grid_simplify_point_set.h>

Merges points which belong to the same cell of a grid of cell size = epsilon.

This method modifies the order of input points so as to pack all remaining points first, and returns an iterator over the first point to remove (see erase-remove idiom). For this reason it should not be called on sorted containers.

Precondition: epsilon > 0

Template Parameters

PointRange is a model of Range. The value type of its iterator is the key type of the named parameter point_map.

Parameters

points	input point range.
epsilon	tolerance value when merging 3D points.
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadWritePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
callback	an instance of `std::function<bool(double)>`. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns `true`, then the algorithm continues its execution normally; if it returns `false`, the algorithm is stopped and simplification stops with no guarantee on the output.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Returns: iterator over the first point to remove.

Examples: Point_set_processing_3/callback_example.cpp, Point_set_processing_3/grid_simplification_example.cpp, Point_set_processing_3/grid_simplify_indices.cpp, and Point_set_processing_3/scale_estimation_example.cpp.

◆ hierarchy_simplify_point_set()

template<typename PointRange , typename NamedParameters >

PointRange::iterator CGAL::hierarchy_simplify_point_set	(	PointRange &	points,
		const NamedParameters &	np
	)

#include <CGAL/hierarchy_simplify_point_set.h>

Recursively split the point set in smaller clusters until the clusters have less than size elements or until their variation factor is below var_max.

This method modifies the order of input points so as to pack all remaining points first, and returns an iterator over the first point to remove (see erase-remove idiom). For this reason it should not be called on sorted containers.

Precondition: 0 < maximum_variation < 1/3; size > 0

Template Parameters

PointRange is a model of Range. The value type of its iterator is the key type of the named parameter point_map.

Parameters

points	input point range.
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadWritePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
size	maximum cluster size.
maximum_variation	maximum cluster variation value.
diagonalize_traits	a model of `DiagonalizeTraits`. It can be omitted: if Eigen 3 (or greater) is available and `CGAL_EIGEN3_ENABLED` is defined then an overload using `Eigen_diagonalize_traits` is provided. Otherwise, the internal implementation `CGAL::Diagonalize_traits` is used.
callback	an instance of `std::function<bool(double)>`. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns `true`, then the algorithm continues its execution normally; if it returns `false`, the algorithm is stopped and simplification stops with no guarantee on the output.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Returns: iterator over the first point to remove.

Examples: Point_set_processing_3/hierarchy_simplification_example.cpp.

◆ jet_estimate_normals()

template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >

void CGAL::jet_estimate_normals	(	PointRange &	points,
		unsigned int	k,
		const NamedParameters &	np
	)

#include <CGAL/jet_estimate_normals.h>

Estimates normal directions of the range of points using jet fitting on the nearest neighbors. The output normals are randomly oriented.

Precondition: k >= 2

Template Parameters

ConcurrencyTag	enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
PointRange	is a model of `Range`. The value type of its iterator is the key type of the named parameter `point_map`.

Parameters

points	input point range.
k	number of neighbors
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadWritePropertyMap` with value type `geom_traits::Vector_3`.
neighbor_radius	spherical neighborhood radius. If provided, the neighborhood of a query point is computed with a fixed spherical radius instead of a fixed number of neighbors. In that case, the parameter `k` is used as a limit on the number of points returned by each spherical query (to avoid overly large number of points in high density areas). If no limit is wanted, use `k=0`.
degree_fitting	degree of jet fitting.
svd_traits	template parameter for the class `Monge_via_jet_fitting`. If Eigen 3.2 (or greater) is available and `CGAL_EIGEN3_ENABLED` is defined, then `CGAL::Eigen_svd` is used.
callback	an instance of `std::function<bool(double)>`. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns `true`, then the algorithm continues its execution normally; if it returns `false`, the algorithm is stopped and the remaining normals are left unchanged.
geom_traits	an instance of a geometric traits class, model of `Kernel`

◆ jet_smooth_point_set()

template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >

void CGAL::jet_smooth_point_set	(	PointRange &	points,
		unsigned int	k,
		const NamedParameters &	np
	)

#include <CGAL/jet_smooth_point_set.h>

Smoothes the range of points using jet fitting on the nearest neighbors and reprojection onto the jet. As this method relocates the points, it should not be called on containers sorted w.r.t. point locations.

Precondition: k >= 2

Template Parameters

ConcurrencyTag	enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
PointRange	is a model of `Range`. The value type of its iterator is the key type of the named parameter `point_map`.

Parameters

points	input point range.
k	number of neighbors
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
neighbor_radius	spherical neighborhood radius. If provided, the neighborhood of a query point is computed with a fixed spherical radius instead of a fixed number of neighbors. In that case, the parameter `k` is used as a limit on the number of points returned by each spherical query (to avoid overly large number of points in high density areas). If no limit is wanted, use `k=0`.
degree_fitting	degree of jet fitting.
degree_monge	Monge degree.
svd_traits	template parameter for the class `Monge_via_jet_fitting`. If Eigen 3.2 (or greater) is available and `CGAL_EIGEN3_ENABLED` is defined, then `CGAL::Eigen_svd` is used.
callback	an instance of `std::function<bool(double)>`. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns `true`, then the algorithm continues its execution normally; if it returns `false`, the algorithm is stopped and the remaining points are left unchanged.
geom_traits	an instance of a geometric traits class, model of `Kernel`

◆ mst_orient_normals()

template<typename PointRange , typename NamedParameters >

PointRange::iterator CGAL::mst_orient_normals	(	PointRange &	points,
		unsigned int	k,
		const NamedParameters &	np
	)

#include <CGAL/mst_orient_normals.h>

Orients the normals of the range of points using the propagation of a seed orientation through a minimum spanning tree of the Riemannian graph. This method modifies the order of input points so as to pack all sucessfully oriented points first, and returns an iterator over the first point with an unoriented normal (see erase-remove idiom). For this reason it should not be called on sorted containers. It is based on [3].

Warning: This function may fail when Boost version 1.54 is used, because of the following bug: https://svn.boost.org/trac/boost/ticket/9012

Precondition: Normals must be unit vectors; k >= 2

Template Parameters

PointRange is a model of Range. The value type of its iterator is the key type of the named parameter point_map.

Parameters

points	input point range.
k	number of neighbors.
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadWritePropertyMap` with value type `geom_traits::Vector_3`.
neighbor_radius	spherical neighborhood radius. If provided, the neighborhood of a query point is computed with a fixed spherical radius instead of a fixed number of neighbors. In that case, the parameter `k` is used as a limit on the number of points returned by each spherical query (to avoid overly large number of points in high density areas). If no limit is wanted, use `k=0`.
point_is_constrained_map	a model of `ReadablePropertyMap` with value type `bool`. Points with a `true` value will be used as seed points: their normal will be considered as already oriented, it won't be altered and it will be propagated to its neighbors. If this parameter is omitted, the highest point (highest Z coordinate) will be used as the unique seed with an upward oriented normal
geom_traits	an instance of a geometric traits class, model of `Kernel`

Returns: iterator over the first point with an unoriented normal.

Examples: Point_set_processing_3/normals_example.cpp.

◆ pca_estimate_normals()

template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >

void CGAL::pca_estimate_normals	(	PointRange &	points,
		unsigned int	k,
		const NamedParameters &	np
	)

#include <CGAL/pca_estimate_normals.h>

Estimates normal directions of the range of points by linear least squares fitting of a plane over the nearest neighbors. The output normals are randomly oriented.

Precondition: k >= 2

Template Parameters

ConcurrencyTag	enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
PointRange	is a model of `Range`. The value type of its iterator is the key type of the named parameter `point_map`.

Parameters

points	input point range.
k	number of neighbors
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `WritablePropertyMap` with value type `geom_traits::Vector_3`.
neighbor_radius	spherical neighborhood radius. If provided, the neighborhood of a query point is computed with a fixed spherical radius instead of a fixed number of neighbors. In that case, the parameter `k` is used as a limit on the number of points returned by each spherical query (to avoid overly large number of points in high density areas). If no limit is wanted, use `k=0`.
callback	an instance of `std::function<bool(double)>`. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns `true`, then the algorithm continues its execution normally; if it returns `false`, the algorithm is stopped and the remaining normals are left unchanged.
geom_traits	an instance of a geometric traits class, model of `Kernel`

◆ random_simplify_point_set()

template<typename PointRange >

PointRange::iterator CGAL::random_simplify_point_set	(	PointRange &	points,
		double	removed_percentage
	)

#include <CGAL/random_simplify_point_set.h>

Randomly deletes a user-specified fraction of the input points.

This method modifies the order of input points so as to pack all remaining points first, and returns an iterator over the first point to remove (see erase-remove idiom). For this reason it should not be called on sorted containers.

Template Parameters

PointRange is a model of Range.

Parameters

points	input point range.
removed_percentage	percentage of points to remove.

Returns: iterator over the first point to remove.

◆ register_point_sets() [1/2]

template<class PointRange1 , class PointRange2 , class NamedParameters1 , class NamedParameters2 >

double CGAL::OpenGR::register_point_sets	(	const PointRange1 &	point_set_1,
		PointRange2 &	point_set_2,
		const NamedParameters1 &	np1,
		const NamedParameters2 &	np2
	)

#include <CGAL/OpenGR/register_point_sets.h>

Computes the registration of point_set_2 with respect to point_set_1 and applies it.

Registration is computed using the Super4PCS algorithm [9]. Parameters documentation is copy-pasted from the official documentation of OpenGR. For more details on this method, please refer to it.

Note: This function requires the thirdpartyOpenGR library.

Warning: Although this may seem counter-intuitive, if one of the two point set matches only a small section of the other one, it is advised to use the small point set as reference instead of the big one. The reason is that the reference point set is used to construct a base that is sought after in the other point set: if the big point set is used as reference, chances are the constructed base will not be present in the small point set.

Template Parameters

PointRange1	is a model of `Range`. The value type of its iterator is the key type of the named parameter `point_map` in `NamedParameters1`.
PointRange2	is a model of `Range`. The value type of its iterator is the key type of the named parameter `point_map` in `NamedParameters2`.

Parameters

point_set_1	input point range used as reference.
point_set_2	input point range whose registration w.r.t. `point_set_1` will be computed.
np1	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange1` and whose value type is `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange1` and whose value type `geom_traits::Vector_3`.
number_of_samples	size of the subset of input points used to compute registration. Input clouds are sub-sampled prior exploration, to ensure fast computations. Super4PCS has a linear complexity w.r.t. the number of input samples, allowing to use larger values than 4PCS. Simple geometry with large overlap can be matched with only 200 samples. However, with Super4PCS, smaller details can be used during the process by using up to thousands of points. There is no theoretical limit to this parameter, however using too large values leads to very a large congruent set, which requires more time and memory to be explored. Using a large number of samples is recommended when: geometrical details are required to perform the matching, for instance to disambiguate between several similar configurations; the clouds have a very low overlap: using a too sparse sampling can prevent to have samples in the overlapping area, causing the algorithm to fail; the clouds are very noisy, and require a dense sampling. Note that Super4PCS is a global registration algorithm, which finds a good approximate of the rigid transformation aligning too clouds. Increasing the number of samples in order to get a fine registration is not optimal: it is usually faster to use less samples, and refine the transformation using a local algorithm, like the ICP, or its variant SparseICP.
accuracy	registration accuracy (delta in the paper). Setting a small value means that the two clouds needs to be very close to be considered as well aligned. It is expressed in scene units. A simple way to understand its impact is to consider the computation of the Largest Common Pointset (LCP), the metric used to verify how much the clouds are aligned. For each transformation matrix produced by Super4PCS, we compute the LCP measure by considering a shell around the reference cloud, and count the percentage of points of the target cloud lying in the shell. The thickness of the shell is defined by the parameter delta.
maximum_normal_deviation	angle threshold (in degrees) used to filter pairs of points according to their normal consistency. Small values decrease computation time but may also decrease the quality if pairs of points that should match have a normal deviation higher than the threshold.
overlap	ratio of expected overlap between the two point sets: it is ranging between 0 (no overlap) to 1 (100% overlap). The overlap parameter controls the size of the basis used for registration. Usually, the larger the overlap, the faster the algorithm. When the overlap is unknown, a simple way to set this parameter is to start from 100% overlap, and decrease the value until obtaining a good result. Using too small values will slow down the algorithm, and reduce the accuracy of the result.
maximum_running_time	maximum number of seconds after which the algorithm stops. Super4PCS explores the transformation space to align the two input clouds. Since the exploration is performed randomly, it is recommended to use a large time value to explore the whole space.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Parameters

np2	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange2` and whose value type is `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange2` and whose value type `geom_traits::Vector_3`.

Returns: the registration score.

Examples: Point_set_processing_3/registration_with_OpenGR.cpp.

◆ register_point_sets() [2/2]

template<class PointRange1 , class PointRange2 , class NamedParameters1 , class NamedParameters2 >

bool CGAL::pointmatcher::register_point_sets	(	const PointRange1 &	point_set_1,
		PointRange2 &	point_set_2,
		const NamedParameters1 &	np1,
		const NamedParameters2 &	np2
	)

#include <CGAL/pointmatcher/register_point_sets.h>

Computes the registration of point_set_2 with respect to point_set_1 and applies it.

Registration is computed using the Iterative Closest Point (ICP) algorithm.

Note: This function requires the thirdpartylibpointmatcher library.

Template Parameters

PointRange1	is a model of `Range`. The value type of its iterator is the key type of the named parameter `point_map` in `NamedParameters1`.
PointRange2	is a model of `Range`. The value type of its iterator is the key type of the named parameter `point_map` in `NamedParameters2`.

Parameters

point_set_1	input point range used as reference.
point_set_2	input point range whose registration w.r.t. `point_set_1` will be computed.
np1	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange1` and whose value type is `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange1` and whose value type `geom_traits::Vector_3`.
point_set_filters	is a model of `Range`. The value type of its iterator is `ICP_config`. The chain of filters to be applied to the reference point cloud. The reference point cloud is processed into an intermediate point cloud with the given chain of filters to be used in the alignment procedure. The chain is organized with the forward traversal order of the point set filters range. The chain of point set filters are applied only once at the beginning of the ICP procedure, i.e., before the first iteration of the ICP algorithm. The filters can have several purposes, including but are not limited to i) removal of noisy points which render alignment of point clouds difficult, ii) removal of redundant points so as to speed up alignment, iii) addition of descriptive information to the points such as a surface normal vector, or the direction from the point to the sensor. Corresponds to `referenceDataPointsFilters` configuration module of thirdpartylibpointmatcher library. The filters should be chosen and set from possible components of the `referenceDataPointsFilters` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `RandomSamplingDataPointsFilter` is used.
matcher	is a model of `ICP_config`. The method used for matching (linking) the points from `point_set_2`, to the points in the reference cloud, `point_set_1`. Corresponds to `matcher` configuration module of thirdpartylibpointmatcher library. The matcher should be chosen and set from possible components of the `matcher` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `KDTreeMatcher` is used.
outlier_filters	is a model of `Range`. The value type of its iterator is `ICP_config`. The chain of filters to be applied to the matched (linked) point clouds after each processing iteration of the ICP algorithm to remove the links which do not correspond to true point correspondences. The outliers are rejected. Points with no link are ignored in the subsequent error minimization step. The chain is organized with the forward traversal order of the outlier filters range. Corresponds to `outlierFilters` configuration module of thirdpartylibpointmatcher library. The filters should be chosen and set from possible components of the `outlierFilters` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `TrimmedDistOutlierFilter` is used.
error_minimizer	is a model of `ICP_config`. The error minimizer that computes a transformation matrix such as to minimize the error between the point sets. Corresponds to `errorMinimizer` configuration module of thirdpartylibpointmatcher library. The error minimizer should be chosen and set from possible components of the `errorMinimizer` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `PointToPlaneErrorMinimizer` is used.
transformation_checkers	is a model of `Range`. The value type of its iterator is `ICP_config`. The chain of transformation checkers. A transformation checker can stop the iteration depending on the conditions it defines. The chain is organized with the forward traversal order of the transformation checkers range. Corresponds to `transformationCheckers` configuration module of thirdpartylibpointmatcher library. The transformation checkers should be chosen and set from possible components of the `transformationCheckers` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, the chain of `CounterTransformationChecker` and `DifferentialTransformationChecker` is used.
inspector	is a model of `ICP_config`. The inspector allows to log data at different steps for analysis. Inspectors typically provide deeper scrutiny than the logger. Corresponds to `inspector` configuration module of thirdpartylibpointmatcher library. The inspector should be chosen and set from possible components of the `inspector` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `NullInspector` is used.
logger	is a model of `ICP_config`. The method for logging information regarding the registration process outputted by thirdpartylibpointmatcher library. The logs generated by CGAL library does not get effected by this configuration. Corresponds to `logger` configuration module of thirdpartylibpointmatcher library. The logger should be chosen and set from possible components of the `logger` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `NullLogger` is used.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Parameters

np2

optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange2` and whose value type is `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadablePropertyMap` whose key type is the value type of the iterator of `PointRange2` and whose value type `geom_traits::Vector_3`.
point_set_filters	is a model of `Range`. The value type of its iterator is `ICP_config`. The chain of filters to be applied to the point cloud, `point_set_2`. The point cloud is processed into an intermediate point cloud with the given chain of filters to be used in the alignment procedure. The chain is organized with the forward traversal order of the point set filters range. The chain of point set filters are applied only once at the beginning of the ICP procedure, i.e., before the first iteration of ICP algorithm. The filters can have several purposes, including but are not limited to i) removal of noisy points which render alignment of point clouds difficult, ii) removal of redundant points so as to speed up alignment, iii) addition of descriptive information to the points such as a surface normal vector, or the direction from the point to the sensor. Corresponds to `readingDataPointsFilters` configuration module of thirdpartylibpointmatcher library. The filters should be chosen and set from possible components of the `readingDataPointsFilters` configuration module. See libpointmatcher documentation for possible configurations. If this parameter is omitted, `SamplingSurfaceNormalDataPointsFilter` is used.
transformation	The affine transformation that is used as the initial transformation for `point_set_2`. If this parameter is omitted, identity transformation is used.

Returns: true if registration is converged, false otherwise. A log why it failed to converge is written to std::cerr if the registration cannot converge.

Examples: Point_set_processing_3/registration_with_opengr_pointmatcher_pipeline.cpp, and Point_set_processing_3/registration_with_pointmatcher.cpp.

◆ remove_outliers()

template<typename PointRange , typename NamedParameters >

PointRange::iterator CGAL::remove_outliers	(	PointRange &	points,
		unsigned int	k,
		const NamedParameters &	np
	)

#include <CGAL/remove_outliers.h>

Removes outliers:

computes average squared distance to the nearest neighbors,
and sorts the points in increasing order of average distance.

This method modifies the order of input points so as to pack all remaining points first, and returns an iterator over the first point to remove (see erase-remove idiom). For this reason it should not be called on sorted containers.

Precondition: k >= 2

Template Parameters

PointRange is a model of Range. The value type of its iterator is the key type of the named parameter point_map.

Parameters

points	input point range.
k	number of neighbors
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
neighbor_radius	spherical neighborhood radius. If provided, the neighborhood of a query point is computed with a fixed spherical radius instead of a fixed number of neighbors. In that case, the parameter `k` is used as a limit on the number of points returned by each spherical query (to avoid overly large number of points in high density areas). If no limit is wanted, use `k=0`.
threshold_percent	maximum percentage of points to remove.
threshold_distance	minimum distance for a point to be considered as outlier (distance here is the square root of the average squared distance to K nearest neighbors).
callback	an instance of `std::function<bool(double)>`. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns `true`, then the algorithm continues its execution normally; if it returns `false`, the algorithm is stopped, all points are left unchanged and the function return `points.end()`.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Returns: iterator over the first point to remove.

Note: There are two thresholds that can be used: threshold_percent and threshold_distance. This function returns the smallest number of outliers such that at least one of these threshold is fulfilled. This means that if threshold_percent=100, only threshold_distance is taken into account; if threshold_distance=0 only threshold_percent is taken into account.

Examples: Point_set_processing_3/remove_outliers_example.cpp.

◆ structure_point_set()

template<typename PointRange , typename PlaneRange , typename OutputIterator , typename NamedParameters >

OutputIterator CGAL::structure_point_set	(	const PointRange &	points,
		const PlaneRange &	planes,
		OutputIterator	output,
		double	epsilon,
		const NamedParameters &	np
	)

#include <CGAL/structure_point_set.h>

This is an implementation of the Point Set Structuring algorithm. This algorithm takes advantage of a set of detected planes: it detects adjacency relationships between planes and resamples the detected planes, edges and corners to produce a structured point set.

The size parameter epsilon is used both for detecting adjacencies and for setting the sampling density of the structured point set.

For more details, please refer to [7].

Template Parameters

PointRange	is a model of `ConstRange`. The value type of its iterator is the key type of the named parameter `point_map`.
PlaneRange	is a model of `ConstRange`. The value type of its iterator is the key type of the named parameter `plane_map`.
OutputIterator	Type of the output iterator. The type of the objects put in it is `std::pair<Kernel::Point_3, Kernel::Vector_3>`. Note that the user may use a function_output_iterator to match specific needs.

Parameters

points	input point range.
planes	input plane range.
output	output iterator where output points are written
epsilon	size parameter.
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadablePropertyMap` with value type `geom_traits::Vector_3`.
plane_index_map	a model of `ReadablePropertyMap` with value type `int`. Associates the index of a point in the input range to the index of plane (-1 if point does is not assigned to a plane).
plane_map	a model of `ReadablePropertyMap` with value type `geom_traits::Plane_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Plane_3>` is used.
attraction_factor	multiple of `epsilon` used to connect simplices.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Examples: Point_set_processing_3/structuring_example.cpp.

◆ vcm_estimate_normals() [1/2]

template<typename PointRange , typename NamedParameters >

void CGAL::vcm_estimate_normals	(	PointRange &	points,
		double	offset_radius,
		double	convolution_radius,
		const NamedParameters &	np
	)

#include <CGAL/vcm_estimate_normals.h>

Estimates normal directions of the range of points using the Voronoi Covariance Measure with a radius for the convolution. The output normals are randomly oriented.

See compute_vcm() for a detailed description of the parameters offset_radius and convolution_radius and of the Voronoi Covariance Measure.

Template Parameters

PointRange is a model of Range. The value type of its iterator is the key type of the named parameter point_map.

Parameters

points	input point range.
offset_radius	offset_radius.
convolution_radius	convolution_radius.
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `WritablePropertyMap` with value type `geom_traits::Vector_3`.
diagonalize_traits	a model of `DiagonalizeTraits`. It can be omitted: if Eigen 3 (or greater) is available and `CGAL_EIGEN3_ENABLED` is defined then an overload using `Eigen_diagonalize_traits` is provided. Otherwise, the internal implementation `CGAL::Diagonalize_traits` is used.
geom_traits	an instance of a geometric traits class, model of `Kernel`

◆ vcm_estimate_normals() [2/2]

template<typename PointRange , typename NamedParameters >

void CGAL::vcm_estimate_normals	(	PointRange &	points,
		double	offset_radius,
		unsigned int	k,
		const NamedParameters &	np
	)

#include <CGAL/vcm_estimate_normals.h>

Estimates normal directions of the range of points using the Voronoi Covariance Measure with a number of neighbors for the convolution. The output normals are randomly oriented.

See compute_vcm() for a detailed description of the parameter offset_radius and of the Voronoi Covariance Measure.

Template Parameters

PointRange is a model of Range. The value type of its iterator is the key type of the named parameter point_map.

Parameters

points	input point range.
offset_radius	offset_radius.
k	number of neighbor points used for convolution.
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadablePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `WritablePropertyMap` with value type `geom_traits::Vector_3`.
diagonalize_traits	a model of `DiagonalizeTraits`. It can be omitted: if Eigen 3 (or greater) is available and `CGAL_EIGEN3_ENABLED` is defined then an overload using `Eigen_diagonalize_traits` is provided. Otherwise, the internal implementation `CGAL::Diagonalize_traits` is used.
geom_traits	an instance of a geometric traits class, model of `Kernel`

◆ vcm_is_on_feature_edge()

template<class FT , class VCMTraits >

bool CGAL::vcm_is_on_feature_edge	(	std::array< FT, 6 > &	cov,
		double	threshold,
		VCMTraits
	)

#include <CGAL/vcm_estimate_edges.h>

determines if a point is on a sharp feature edge from a point set for which the Voronoi covariance Measures have been computed.

The sharpness of the edge, specified by parameter threshold, is used to filtered points according to the external angle around a sharp feature.

A point is considered to be on a sharp feature if the external angle alpha at the edge is such that alpha >= 2 / sqrt(3) * sqrt(threshold). In particular this means that if the input contains sharp features with different external angles, the one with the smallest external angle should be considered, which however would result in selecting more points on sharper regions. More details are provided in [10].

Template Parameters

VCMTraits is a model of DiagonalizeTraits. It can be omitted: if Eigen 3 (or greater) is available and CGAL_EIGEN3_ENABLED is defined then an overload using Eigen_diagonalize_traits is provided. Otherwise, the internal implementation Diagonalize_traits is used.

See also: CGAL::compute_vcm()`

Examples: Point_set_processing_3/edges_example.cpp.

◆ wlop_simplify_and_regularize_point_set()

template<typename ConcurrencyTag , typename PointRange , typename OutputIterator , typename NamedParameters >

OutputIterator CGAL::wlop_simplify_and_regularize_point_set	(	PointRange &	points,
		OutputIterator	output,
		const NamedParameters &	np
	)

#include <CGAL/wlop_simplify_and_regularize_point_set.h>

This is an implementation of the Weighted Locally Optimal Projection (WLOP) simplification algorithm. The WLOP simplification algorithm can produce a set of denoised, outlier-free and evenly distributed particles over the original dense point cloud. The core of the algorithm is a Weighted Locally Optimal Projection operator with a density uniformization term. For more details, please refer to [4].

A parallel version of WLOP 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

ConcurrencyTag	enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
PointRange	is a model of `Range`. The value type of its iterator is the key type of the named parameter `point_map`.
OutputIterator	Type of the output iterator. It must accept objects of type `geom_traits::Point_3`.

Parameters

points	input point range.
output	iterator where output points are put.
np	optional sequence of Named Parameters among the ones listed below.

Named Parameters

point_map	a model of `ReadWritePropertyMap` with value type `geom_traits::Point_3`. If this parameter is omitted, `CGAL::Identity_property_map<geom_traits::Point_3>` is used.
normal_map	a model of `ReadWritePropertyMap` with value type `geom_traits::Vector_3`.
select_percentage	percentage of points to retain. The default value is set to 5 (%).
neighbor_radius	spherical neighborhood radius. This is a key parameter that needs to be finely tuned. The result will be irregular if too small, but a larger value will impact the runtime. In practice, choosing a radius such that the neighborhood of each sample point includes at least two rings of neighboring sample points gives satisfactory result. If this parameter is not provided, it is automatically set to 8 times the average spacing of the point set.
number_of_iterations	number of iterations to solve the optimsation problem. The default value is 35. More iterations give a more regular result but increase the runtime.
require_uniform_sampling	an optional preprocessing, which will give better result if the distribution of the input points is highly non-uniform. The default value is `false`.
callback	an instance of `std::function<bool(double)>`. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns `true`, then the algorithm continues its execution normally; if it returns `false`, the algorithm is stopped, no output points are generated.
geom_traits	an instance of a geometric traits class, model of `Kernel`

Classes

Functions

Function Documentation

◆ bilateral_smooth_point_set()

◆ compute_average_spacing()

◆ compute_registration_transformation() [1/2]

◆ compute_registration_transformation() [2/2]

◆ compute_vcm()

◆ edge_aware_upsample_point_set()

◆ estimate_global_k_neighbor_scale()

◆ estimate_global_range_scale()

◆ estimate_local_k_neighbor_scales()

◆ estimate_local_range_scales()

◆ grid_simplify_point_set()

◆ hierarchy_simplify_point_set()

◆ jet_estimate_normals()

◆ jet_smooth_point_set()

◆ mst_orient_normals()

◆ pca_estimate_normals()

◆ random_simplify_point_set()

◆ register_point_sets() [1/2]

◆ register_point_sets() [2/2]

◆ remove_outliers()

◆ structure_point_set()

◆ vcm_estimate_normals() [1/2]

◆ vcm_estimate_normals() [2/2]

◆ vcm_is_on_feature_edge()

◆ wlop_simplify_and_regularize_point_set()