CGAL 4.7 - Scale-Space Surface Reconstruction
CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct > Class Template Reference

#include <CGAL/Scale_space_surface_reconstruction_3.h>

## Definition

### template<class Gt, class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag> class CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >

computes a triangulated surface mesh interpolating a point set.

This class stores several of the (intermediate) results. This makes it easier and more efficient to adjust the parameter settings based on preliminary results, or to further increase the scale to improve the results. The class stores the point set at the current scale and the reconstructed surface, possibly with iterators over the shells.

The class also stores the parameters for estimating the optimal neighborhood radius and either the lastest estimate or the manually set radius. This way, the radius can be estimated (again) whenever necessary. Also note that both increasing the scale and reconstructing the surface use this radius. By changing or re-estimating the radius between these operations, they can use separate parameter settings.

The surface can be constructed either for a fixed neighborhood radius, or for a dynamic radius. When constructing the surface for exactly one neighborhood radius, it is faster to set FS to Tag_true. If the correct neighborhood radius should be changed or estimated multiple times, it is faster to set FS to Tag_false.

It is undefined whether a surface with fixed radius may have its radius changed, but if so, this will likely require more computation time than changing the radius of a dynamic surface. In either case, it is possible to change the point set while maintaining the same radius.

The surface can be stored either as an unordered collection of triangles, or as a collection ordered by shells. A shell is a maximally connected component of the surface where connected facets are locally oriented towards the same side of the surface.

Template Parameters
 Gt is the geometric traits class. It must be a model of DelaunayTriangulationTraits_3. It must have a RealEmbeddable field number type. Generally, Exact_predicates_inexact_constructions_kernel is preferred. FS determines whether the surface is expected to be constructed for a fixed neighborhood radius. It must be a Boolean_tag type. The default value is Tag_true. Note that the value of this parameter does not change the result but only has an impact on the run-time. Sh determines whether to collect the surface per shell. It must be a Boolean_tag type. The default value is Tag_true. wA must be a model of WeightedPCAProjection_3 and determines how to approximate a weighted point set. If Eigen 3.1.2 (or greater) is available and CGAL_EIGEN3_ENABLED is defined, then Weighted_PCA_approximation_3 is used by default. Ct indicates whether to use concurrent processing. It must be either Sequential_tag or Parallel_tag (the default value).
Examples:
Scale_space_reconstruction_3/scale_space.cpp, and Scale_space_reconstruction_3/scale_space_incremental.cpp.

## Public Types

typedef Gt::Point_3 Point
defines the point type.

## Types

typedef Gt::FT FT
defines the field number type.

typedef unspecified_type Point_iterator
defines an iterator over the points.

typedef const unspecified_type Point_const_iterator
defines a constant iterator over the points.

typedef CGAL::cpp11::array
< unsigned int, 3 >
Triple
defines a triple of point indices indicating a triangle of the surface.

typedef unspecified_type Triple_iterator
defines an iterator over the triples.

typedef const unspecified_type Triple_const_iterator
defines a constant iterator over the triples.

## Constructors

Scale_space_surface_reconstruction_3 (unsigned int neighbors, unsigned int samples)
constructs a surface reconstructor that will automatically estimate the neighborhood radius. More...

constructs a surface reconstructor with a given neighborhood radius. More...

## Point Set Manipulation

template<class InputIterator >
void insert (InputIterator begin, InputIterator end)
inserts a collection of points into the scale-space at the current scale. More...

void insert (const Point &p)
inserts a point into the scale-space at the current scale. More...

void clear ()
clears the stored scale-space surface reconstruction data. More...

## Neighborhood Size Estimation

FT estimate_neighborhood_squared_radius (unsigned int neighbors, unsigned int samples)
estimates the neighborhood radius based on a number of sample points. More...

sets the squared radius of the neighborhood. More...

gives the squared radius of the neighborhood. More...

checks whether the neighborhood radius has been set. More...

## Neighborhood Size Estimation Parameters

unsigned int mean_number_of_neighbors () const
gives the mean number of neighbors an estimated neighborhood should contain. More...

unsigned int neighborhood_sample_size () const
gives the number of sample points the neighborhood estimation uses. More...

void set_mean_number_of_neighbors (unsigned int neighbors)
sets the mean number of neighbors an estimated neighborhood should contain. More...

void set_neighborhood_sample_size (unsigned int samples)
sets the number of sample points the neighborhood estimation uses. More...

## Scale-Space Manipulation

void increase_scale (unsigned int iterations=1)
increases the scale by a number of iterations. More...

## Surface Reconstruction

void reconstruct_surface ()
constructs a triangle mesh from the point set at a fixed scale. More...

std::size_t number_of_triangles () const
gives the number of triangles of the surface.

std::size_t number_of_points () const
gives the number of points of the surface.

std::size_t number_of_shells () const
gives the number of shells of the surface.

## Iterators

Point_const_iterator points_begin () const
gives an iterator to the first point at the current scale.

Point_iterator points_begin ()
gives an iterator to the first point at the current scale. More...

Point_const_iterator points_end () const
gives a past-the-end iterator of the points at the current scale.

Point_iterator points_end ()
gives a past-the-end iterator of the points at the current scale. More...

Triple_const_iterator surface_begin () const
gives an iterator to the first triple in the surface.

Triple_iterator surface_begin ()
gives an iterator to the first triple in the surface. More...

Triple_const_iterator surface_end () const
gives a past-the-end iterator of the triples in the surface.

Triple_iterator surface_end ()
gives a past-the-end iterator of the triples in the surface. More...

Triple_const_iterator shell_begin (std::size_t shell) const
gives an iterator to the first triple in a given shell. More...

Triple_iterator shell_begin (std::size_t shell)
gives an iterator to the first triple in a given shell. More...

Triple_const_iterator shell_end (std::size_t shell) const
gives a past-the-end iterator of the triples in a given shell. More...

Triple_iterator shell_end (std::size_t shell)
gives a past-the-end iterator of the triples in a given shell. More...

## Constructor & Destructor Documentation

template<class Gt , class FS , class Sh , class wA , class Ct >
 CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::Scale_space_surface_reconstruction_3 ( unsigned int neighbors, unsigned int samples )

constructs a surface reconstructor that will automatically estimate the neighborhood radius.

Parameters
 neighbors is the number of neighbors a point's neighborhood should contain on average. samples is the number of points sampled to estimate the neighborhood radius.
template<class Gt , class FS , class Sh , class wA , class Ct >
 CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::Scale_space_surface_reconstruction_3 ( FT sq_radius)

constructs a surface reconstructor with a given neighborhood radius.

Parameters
Precondition
sq_radius is not negative.

## Member Function Documentation

template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 void CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::clear ( )

clears the stored scale-space surface reconstruction data.

This includes discarding the surface, the scale-space and all its points, and any estimation of the neighborhood radius.

Methods called after this point may have to re-estimate the neighborhood radius. This method does not discard the parameters for estimating this radius (the mean number of neighbors and the sample size).

template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 FT CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::estimate_neighborhood_squared_radius ( )

This method is equivalent to running estimate_neighborhood_squared_radius( mean_number_of_neighbors(), neighborhood_sample_size() ).

This method can be called by the scale-space and surface construction methods if the neighborhood radius is not set when they are called.

Returns
Note
This method processes the point set at the current scale. The points can be set with insert(begin, end).
Warning
set_mean_number_of_neighbors(unsigned int neighbors).
set_neighborhood_sample_size(unsigned int samples).
estimate_neighborhood_squared_radius(unsigned int neighbors, unsigned int samples).
increase_scale(unsigned int iterations).
reconstruct_surface().
template<class Gt , class FS , class Sh , class wA , class Ct >
 Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::FT CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::estimate_neighborhood_squared_radius ( unsigned int neighbors, unsigned int samples )

estimates the neighborhood radius based on a number of sample points.

The neighborhood radius is expressed as the radius of the smallest ball centered on a point such that the ball contains at least a specified number of points, not counting the point itself.

The neighborhood radius is set to the mean of these radii, taken over a number of point samples.

Parameters
 neighbors is the number of neighbors a point's neighborhood should contain on average, not counting the point itself. samples is the number of points sampled to estimate the neighborhood radius.
Returns
Note
This method processes the point set at the current scale. The points can be set with insert(begin, end).
Warning
estimate_neighborhood_squared_radius().
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 bool CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::has_neighborhood_squared_radius ( ) const

checks whether the neighborhood radius has been set.

The radius can be set manually, or estimated automatically.

Returns
true iff the radius has been either set manually or estimated.
set_neighborhood_squared_radius().
estimate_neighborhood_squared_radius().
template<class Gt , class FS , class Sh , class wA , class Ct >
 void CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::increase_scale ( unsigned int iterations = 1)

increases the scale by a number of iterations.

Each iteration the scale is increased, the points set at a higher scale is computed. At a higher scale, the points set is smoother.

If the neighborhood radius has not been set before, it is automatically estimated using estimate_neighborhood_squared_radius().

Parameters
 iterations is the number of iterations to perform. If iterations is 0, nothing happens.
Note
This method processes the point set at the current scale. The points can be set with insert(begin, end).
If the surface was already constructed, increasing the scale will not automatically adjust the surface.
estimate_neighborhood_squared_radius().
reconstruct_surface().
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
template<class InputIterator >
 void CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::insert ( InputIterator begin, InputIterator end )

inserts a collection of points into the scale-space at the current scale.

Template Parameters
 InputIterator is an iterator over the point collection. The value type of the iterator must be a Point.
Parameters
 begin is an iterator to the first point of the collection. end is a past-the-end iterator for the point collection.
Note
Inserting the points does not automatically construct or update the surface.
In order to construct the surface, call reconstruct_surface() after inserting the points.
Warning
Inserting new points may invalidate the neighborhood radius if it was previously estimated.
insert(const Point& p).
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 void CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::insert ( const Point & p)

inserts a point into the scale-space at the current scale.

Parameters
 p is the point to insert.
Note
Inserting the point does not automatically construct or update the surface.
In order to construct the surface, call reconstruct_surface().
Warning
Inserting a new point may invalidate the neighborhood radius if it was previously estimated.
insert(InputIterator begin, InputIterator end).
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 unsigned int CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::mean_number_of_neighbors ( ) const

gives the mean number of neighbors an estimated neighborhood should contain.

This number is only used if the neighborhood radius has not been set manually.

When the neighborhood radius is estimated, it should on average contain this many neighbors, not counting the neighborhood center.

Returns
the number of neighbors a neighborhood ball centered on a point should contain on average when the radius is estimated, not counting the point itself.
set_mean_number_of_neighbors(unsigned int neighbors).
has_neighborhood_squared_radius().
neighborhood_sample_size().
estimate_neighborhood_squared_radius().
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 unsigned int CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::neighborhood_sample_size ( ) const

gives the number of sample points the neighborhood estimation uses.

This number is only used if the neighborhood radius has not been set manually.

If the number of samples is larger than the point cloud, every point is used and the optimal neighborhood radius is computed exactly instead of estimated.

Returns
the number of points sampled for neighborhood estimation.
set_neighborhood_sample_size(unsigned int samples).
has_neighborhood_squared_radius().
mean_number_of_neighbors().
estimate_neighborhood_squared_radius().
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 FT CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::neighborhood_squared_radius ( ) const

gives the squared radius of the neighborhood.

The neighborhood radius is used by increase_scale() to compute the point set at the desired scale and by reconstruct_surface() to construct a surface from the point set at the current scale.

Returns
the squared radius of the neighborhood, or -1 if the neighborhood radius has not yet been set.
increase_scale(unsigned int iterations).
reconstruct_surface().
Examples:
Scale_space_reconstruction_3/scale_space.cpp.
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 Point_iterator CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::points_begin ( )

gives an iterator to the first point at the current scale.

Warning
Changes to the scale-space do not cause an automatic update to the surface.
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 Point_iterator CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::points_end ( )

gives a past-the-end iterator of the points at the current scale.

Warning
Changes to the scale-space do not cause an automatic update to the surface.
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 void CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::reconstruct_surface ( )

constructs a triangle mesh from the point set at a fixed scale.

The order of the points at the current scale is the same as the order at the original scale, meaning that the surface can interpolate the point set at the original scale by applying the indices of the surface triangles to the original point set.

After construction, the triangles of the surface can be iterated using surface_begin() and surface_end().

If the neighborhood radius has not been set before, it is automatically estimated using estimate_neighborhood_squared_radius().

Note
This method processes the point set at the current scale. The points can be set with insert(begin, end).
estimate_neighborhood_squared_radius().
increase_scale(unsigned int iterations).
Examples:
Scale_space_reconstruction_3/scale_space.cpp.
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 void CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::set_mean_number_of_neighbors ( unsigned int neighbors)

sets the mean number of neighbors an estimated neighborhood should contain.

This number is only used if the neighborhood radius has not been set manually.

When the neighborhood radius is estimated, it should on average contain this many neighbors, not counting the neighborhood center.

Parameters
 neighbors is the number of neighbors a neighborhood ball centered on a point should contain on average when the radius is estimated, not counting the point itself.
Note
This does not start the estimation process.
mean_number_of_neighbors().
has_neighborhood_squared_radius().
set_neighborhood_sample_size(unsigned int samples).
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 void CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::set_neighborhood_sample_size ( unsigned int samples)

sets the number of sample points the neighborhood estimation uses.

This number is only used if the neighborhood radius has not been set manually.

If the number of samples is larger than the point cloud, every point is used and the optimal neighborhood radius is computed exactly instead of estimated.

Parameters
 samples is the number of points to sample for neighborhood estimation.
Note
This does not start the estimation process.
neighborhood_sample_size().
has_neighborhood_squared_radius().
set_mean_number_of_neighbors(unsigned int neighbors).
estimate_neighborhood_squared_radius().
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 void CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::set_neighborhood_squared_radius ( const FT & sq_radius)

sets the squared radius of the neighborhood.

The neighborhood radius is used by #[increase_scale() to compute the point set at the desired scale and by reconstruct_surface() to construct a surface from the point set at the current scale.

Parameters
Note
If the neighborhood squared radius is negative when the point set is smoothed or when the surface is computed, the neighborhood radius will be computed automatically.
Warning
neighborhood_squared_radius().
has_neighborhood_squared_radius().
increase_scale(unsigned int iterations).
reconstruct_surface().
template<class Gt , class FS , class Sh , class wA , class Ct >
 Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::Triple_const_iterator CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::shell_begin ( std::size_t shell) const

gives an iterator to the first triple in a given shell.

Parameters
 shell is the index of the shell to access.
Precondition
shell is in the range [ 0, number_of_shells() ).
Examples:
Scale_space_reconstruction_3/scale_space.cpp.
template<class Gt , class FS , class Sh , class wA , class Ct >
 Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::Triple_iterator CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::shell_begin ( std::size_t shell)

gives an iterator to the first triple in a given shell.

Parameters
 shell is the index of the shell to access.
Precondition
shell is in the range [ 0, number_of_shells() ).
Warning
Changes to a shell may invalidate the topology of the surface.
template<class Gt , class FS , class Sh , class wA , class Ct >
 Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::Triple_const_iterator CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::shell_end ( std::size_t shell) const

gives a past-the-end iterator of the triples in a given shell.

Parameters
 shell is the index of the shell to access.
Precondition
shell is in the range [ 0, number_of_shells() ).
Examples:
Scale_space_reconstruction_3/scale_space.cpp.
template<class Gt , class FS , class Sh , class wA , class Ct >
 Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::Triple_iterator CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::shell_end ( std::size_t shell)

gives a past-the-end iterator of the triples in a given shell.

Parameters
 shell is the index of the shell to access.
Precondition
shell is in the range [ 0, number_of_shells() ).
Warning
Changes to a shell may invalidate the topology of the surface.
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 Triple_iterator CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::surface_begin ( )

gives an iterator to the first triple in the surface.

Warning
Changes to the surface may change its topology.
template<class Gt , class FS = Tag_true, class Sh = Tag_true, class wA = Default, class Ct = Parallel_tag>
 Triple_iterator CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct >::surface_end ( )

gives a past-the-end iterator of the triples in the surface.

Warning
Changes to the surface may change its topology.