\( \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.6 - Scale-Space Surface Reconstruction
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
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
Gtis 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.
FSdetermines 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.
Shdetermines whether to collect the surface per shell. It must be a Boolean_tag type. The default value is Tag_true.
wAmust 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.
Ctindicates 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.

Types

typedef Gt::FT FT
 defines the field number type.
 
typedef Gt::Point_3 Point
 defines the point 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
neighborsis the number of neighbors a point's neighborhood should contain on average.
samplesis 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_radiusis 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
neighborsis the number of neighbors a point's neighborhood should contain on average, not counting the point itself.
samplesis 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
iterationsis 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
InputIteratoris an iterator over the point collection. The value type of the iterator must be a Point.
Parameters
beginis an iterator to the first point of the collection.
endis 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
pis 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
neighborsis 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
samplesis 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_radiusis 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
shellis 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
shellis 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
shellis 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
shellis 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.