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

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - Scale-Space Surface Reconstruction

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members | Public Types
CGAL::Scale_space_surface_reconstruction_3< Gt, FS, Sh, wA, Ct > Class Template Reference
Classes

`#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<DelaunayTriangulationTraits_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...
| Scale_space_surface_reconstruction_3 (FT sq_radius)
| 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 ()
| estimates the neighborhood radius. More...
FT | estimate_neighborhood_squared_radius (unsigned int neighbors, unsigned int samples)
| estimates the neighborhood radius based on a number of sample points. More...
void | set_neighborhood_squared_radius (const FT &sq_radius)
| sets the squared radius of the neighborhood. More...
FT | neighborhood_squared_radius () const
| gives the squared radius of the neighborhood. More...
bool | has_neighborhood_squared_radius () const
| 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

  sq_radius | is the squared radius of the neighborhood.

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 | ( | ) |  |

estimates the neighborhood 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
  the estimated neighborhood radius.

Note
  This method processes the point set at the current scale. The points can be set with `insert(begin, end)`.

Warning
  If the surface was already constructed, estimating the neighborhood radius will automatically adjust the surface.

See Also
  `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
  the estimated neighborhood radius.

Note
  This method processes the point set at the current scale. The points can be set with `insert(begin, end)`.

Warning
  If the surface was already constructed, estimating the neighborhood radius will automatically adjust the surface.

See Also
  `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.

See Also
  `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.

See Also
  `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.

See Also
  `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.

See Also
  `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.

See Also
  `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.

See Also
  `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.

See Also
  `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)`.

See Also
  `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.

See Also
  `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.

See Also
  `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

  sq_radius | is the squared radius of the neighborhood.

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
  If the surface was already constructed, changing the neighborhood radius will automatically adjust the surface.

See Also
  `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.