CGAL 6.2 - 3D Point Set

Loading...
Searching...
No Matches
User Manual

Author
  Simon Giraudot

CGAL provides several algorithms for processing point sets, ranging from Shape Detection to Surface Reconstruction through standard Point Set Processing tools.

While these algorithms do not impose specific data structures to work on, this package provides a 3D point set structure to make it easier for the user to handle additional properties such as normal vectors, colors, labels, and to call CGAL algorithms on them.

# General Principle

`CGAL::Point_set_3<Point,Vector>` is a vector based data structure that contains a default property (named `point`) for the coordinates of the points.

Any property the user needs can be easily added, modified, and removed at runtime. A property is identified by a unique name and a type. Convenience methods are provided to handle the normal vectors (property named `normal`) that is a very common property on point sets.

To optimize memory allocation and deallocation, each point is associated an index. The removal of a point simply marks the index as removed. Internally, this avoids the property vectors to be modified at each removal, and allow insertion of new points to reuse indices of points marked as removed. In particular this implies that a point inserted after some removal was done might has a non default initialized property. If the user needs memory to be effectively deallocated, the element marked as removed can be actually deleted from memory using `Point_set_3::garbage_collect()`.

# Simple Usage

The data structure is designed to be easy to use despite its potential complexity when using properties. Several convenience methods are provided to handle points and normals without having to handle properties directly.

The following example shows how to fill a point set, add a normal property, set the normal values, add and remove a point.

Example: Point_set_3/point_set.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Point_set_3.h>
#include <fstream>
#include <limits>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::FT FT;
typedef Kernel::Point_3 Point;
typedef Kernel::Vector_3 Vector;
typedef CGAL::Point_set_3<Point> Point_set;
void print_point_set (const Point_set& point_set)
{
std::cerr << "Content of point set:" << std::endl;
for (Point_set::const_iterator it = point_set.begin();
it != point_set.end(); ++ it)
std::cerr << "* Point " << *it
<< ": " << point_set.point(*it) // or point_set[it]
<< " with normal " << point_set.normal(*it)
<< std::endl;
}
int main (int, char**)
{
Point_set point_set;
// Add points
point_set.insert (Point (0., 0., 0.));
point_set.insert (Point (0., 0., 1.));
point_set.insert (Point (0., 1., 0.));
point_set.add_normal_map();
print_point_set(point_set); // Normals have default values
// Change normal values
Point_set::iterator it = point_set.begin();
point_set.normal(*(it++)) = Vector (1., 0., 0.);
point_set.normal(*(it++)) = Vector (0., 1., 0.);
point_set.normal(*(it++)) = Vector (0., 0., 1.);
// Add point + normal
point_set.insert (Point (1., 2., 3.), Vector (4., 5., 6.));
print_point_set(point_set);
// Add new item
Point_set::iterator new_item = point_set.insert(Point (7., 8., 9.));
point_set.normal(*new_item) = Vector (10., 11., 12.);
print_point_set(point_set); // New item has default values
point_set.remove (point_set.begin() + 2,
point_set.begin() + 4);
print_point_set(point_set); // New item has default values
// Display information
std::cerr << "Number of removed points: " <<point_set.number_of_removed_points() << std::endl;
point_set.collect_garbage();
// Display information (garbage should be gone)
std::cerr << "After garbage collection: " <<point_set.number_of_removed_points() << std::endl;
return 0;
}
CGAL::Exact_predicates_inexact_constructions_kernel
CGAL::Point_set_3
A collection of points with dynamically associated properties.
Definition: Point_set_3.h:123
CGAL::Point_set_3::point
Point & point(const Index &index)
returns a reference to the point corresponding to index.
Definition: Point_set_3.h:556
Kernel::Point_3
Kernel::Vector_3
Kernel

# Using Additional Properties

Every information in the point set is a property. A raw point set comes only with a `point` property. As we saw in the previous example, the user can easily add a normal property. But this mechanism is generalized to any type of property.

The following example shows how to define a color property and an intensity property, and how to modify the point set according to this.

Example: Point_set_3/point_set_property.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Point_set_3.h>
#include <CGAL/Random.h>
#include <fstream>
#include <limits>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::FT FT;
typedef Kernel::Point_3 Point;
typedef Kernel::Vector_3 Vector;
typedef std::array<unsigned char, 3> Color;
typedef CGAL::Point_set_3<Point> Point_set;
typedef Point_set::Property_map<Color> Color_map;
typedef Point_set::Property_map<FT> FT_map;
void print_point_set (const Point_set& point_set)
{
Color_map color = point_set.property_map<Color>("color").value();
FT_map intensity = point_set.property_map<FT>("intensity").value();
std::cerr << "Content of point set:" << std::endl;
for (Point_set::const_iterator it = point_set.begin(); it != point_set.end(); ++ it)
{
std::cerr << "* Point " << point_set.point(*it) // or point_set[it]
<< " with color [" << static_cast<int>(color[*it][0])
<< " " << static_cast<int>(color[*it][1])
<< " " << static_cast<int>(color[*it][2])
<< "] and intensity " << intensity[*it]
<< std::endl;
}
}
int main (int, char**)
{
Point_set point_set;
Color black = {{ 0, 0, 0 }};
bool success = false;
Color_map color;
std::tie (color, success) = point_set.add_property_map<Color> ("color", black);
assert (success);
FT_map intensity;
std::tie (intensity, success) = point_set.add_property_map<FT> ("intensity", 0.);
assert (success);
point_set.reserve (10); // For memory optimization
for (std::size_t i = 0; i < 10; ++ i)
{
Point_set::iterator it = point_set.insert (Point (double(i), double(i), double(i)));
Color c = {{ static_cast<unsigned char>(CGAL::get_default_random().get_int(0, 255)),
static_cast<unsigned char>(CGAL::get_default_random().get_int(0, 255)),
static_cast<unsigned char>(CGAL::get_default_random().get_int(0, 255)) }};
color[*it] = c;
intensity[*it] = rand() / static_cast<double>(RAND_MAX);
}
print_point_set (point_set);
// Remove points with intensity less than 0.5
Point_set::iterator it = point_set.begin();
while (it != point_set.end())
{
if (intensity[*it] < 0.5)
point_set.remove(it);
else
++ it;
}
print_point_set (point_set); // point set is filtered
return 0;
}
CGAL::Point_set_3::property_map
std::optional< Property_map< T > > property_map(const std::string &name) const
returns the property name of type T.
Definition: Point_set_3.h:823

# Applying CGAL Algorithms

Most CGAL algorithms let the user free to choose an input data structure: the points and attributes are then accessed through ranges and property maps. The `CGAL::Point_set_3` class is a range that provides property maps: applying CGAL algorithms is straightforward.

As the Point Set Processing algorithms use Named Parameters to handle property maps, a method `CGAL::Point_set_3::parameters()` is provided: it returns a named parameter object with the right point and normal maps to read and write in the point set object.

In addition, all input/output functions of the package Point Set Processing are overloaded so that the user only has to call them with a `CGAL::Point_set_3` object as a parameter (see Input/Output).

## Point Set Processing

The following example shows how to apply some algorithms from the CGAL library using a point set object:

- generating a point set around a sphere
- estimating the normals with `CGAL::jet_estimate_normals()`
- simplifying the point set with `CGAL::grid_simplify_point_set()`
- detecting the sphere shape with `CGAL::Shape_detection::Efficient_RANSAC`

Example: Point_set_3/point_set_algo.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Point_set_3.h>
#include <CGAL/jet_estimate_normals.h>
#include <CGAL/grid_simplify_point_set.h>
#include <CGAL/point_generators_3.h>
#include <CGAL/Shape_detection/Efficient_RANSAC.h>
#include <fstream>
#include <limits>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::FT FT;
typedef Kernel::Point_3 Point;
typedef Kernel::Vector_3 Vector;
typedef CGAL::Random_points_on_sphere_3<Point> Point_generator;
typedef CGAL::Point_set_3<Point> Point_set;
typedef CGAL::Shape_detection::Efficient_RANSAC_traits
<Kernel, Point_set, Point_set::Point_map, Point_set::Vector_map> Traits;
typedef CGAL::Shape_detection::Efficient_RANSAC<Traits> Efficient_ransac;
typedef CGAL::Shape_detection::Sphere<Traits> Sphere;
int main (int, char**)
{
Point_set point_set;
// Generate points on a unit sphere
Point_generator generator(1.);
std::size_t nb_pts = 10000;
point_set.reserve (nb_pts);
for (std::size_t i = 0; i < nb_pts; ++ i)
point_set.insert (*(generator ++));
// Add normal property and estimate normal values
point_set.add_normal_map();
CGAL::jet_estimate_normals<CGAL::Sequential_tag>
(point_set,
12, // Number of neighbors
point_set.parameters(). // Named parameters provided by Point_set_3
degree_fitting(2)); // additional named parameter specific to jet_estimate_normals
// Simplify point set
CGAL::grid_simplify_point_set
(point_set,
0.1); // Size of grid cell
// point_set.parameters() can be omitted if no additional named parameter is needed
std::vector<std::string> properties = point_set.properties();
std::cerr << "Properties:" << std::endl;
for (std::size_t i = 0; i < properties.size(); ++ i)
std::cerr << " * " << properties[i] << std::endl;
// Detect sphere with RANSAC
Efficient_ransac ransac;
ransac.set_input(point_set,
point_set.point_map(), // Call built-in property map
point_set.normal_map()); // Call built-in property map
ransac.add_shape_factory<Sphere>();
Efficient_ransac::Parameters parameters;
parameters.probability = 0.05;
parameters.min_points = std::size_t(point_set.size() / 3);
parameters.epsilon = 0.01;
parameters.cluster_epsilon = 0.5;
parameters.normal_threshold = 0.9;
ransac.detect(parameters);
for(std::shared_ptr<Efficient_ransac::Shape> shape : ransac.shapes())
if (Sphere* sphere = dynamic_cast<Sphere*>(shape.get()))
std::cerr << "Detected sphere of center " << sphere->center() // Center should be approx 0, 0, 0
<< " and of radius " << sphere->radius() << std::endl; // Radius should be approx 1
return 0;
}
Efficient_RANSAC.h
CGAL::Shape_detection::Efficient_RANSAC
CGAL::Shape_detection::Sphere
CGAL::grid_simplify_point_set
PointRange::iterator grid_simplify_point_set(PointRange &points, double epsilon, const NamedParameters &np=parameters::default_values())
CGAL::Shape_detection::Efficient_RANSAC_traits

## Input/Output

The following example shows how to read a point set in the XYZ format, normalize and invert the normal vectors, and write the result in the OFF format.

Example: Point_set_3/point_set_read_xyz.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Point_set_3.h>
#include <fstream>
#include <limits>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::FT FT;
typedef Kernel::Point_3 Point;
typedef Kernel::Vector_3 Vector;
typedef CGAL::Point_set_3<Point> Point_set;
int main (int argc, char** argv)
{
const std::string fname = argc > 1 ? argv[1] : CGAL::data_file_path("points_3/oni.pwn");
// Reading input
Point_set point_set;
if(!CGAL::IO::read_XYZ(fname, point_set))
{
std::cerr << "Can't read input file " << std::endl;
return EXIT_FAILURE;
}
if (point_set.has_normal_map())
{
// Normalization + inversion of normal vectors
for (Point_set::iterator it = point_set.begin(); it != point_set.end(); ++ it)
{
Vector n = point_set.normal(*it);
n = - n / std::sqrt (n * n);
point_set.normal(*it) = n;
}
}
// Writing result in OFF format
if(!CGAL::IO::write_OFF("normalized_normals.off", point_set, CGAL::parameters::stream_precision(17)))
return EXIT_FAILURE;
return EXIT_SUCCESS;
}
CGAL::IO::write_OFF
bool write_OFF(std::ostream &os, const PointRange &points, const PolygonRange &polygons, const NamedParameters &np=parameters::default_values())
CGAL::IO::read_XYZ
bool read_XYZ(std::istream &is, OutputIterator output, const NamedParameters &np=parameters::default_values())

The PLY format is the usual choice when storing an arbitrary number of additional properties of points is needed. CGAL provides a function `read_PLY()` that allows the user to recover any PLY property wanted, provided the adapted PLY interpreter is implemented.

A `CGAL::Point_set_3` object can be filled with all readable properties of a PLY input. Each PLY property is read and stored into as a property with similar name and type.

For example, if the following line is found in the PLY header:

> ‍property uchar red

Then a property named `red` and with type `std::uint8_t` (`boost` types are used because of their fixed memory size) will be instantiated in the point set and filled with the corresponding values.

Points and normals are recovered as properties with specific class types (namely the template types `Point` and `Vector`). Other non-1D properties are stored with simple number types. For example, if a color is given with integer red, green and blue values, 3 integer properties `red`, `green` and `blue` will be created. A user-defined interpreter must be implemented if such properties should be stored all together (a unique property `color` of type `std::array` for example).

The following example shows how to use this interpreter and how to access a specific property afterwards:

Example: Point_set_3/point_set_read_ply.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Point_set_3.h>
#include <fstream>
#include <limits>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::FT FT;
typedef Kernel::Point_3 Point;
typedef Kernel::Vector_3 Vector;
typedef CGAL::Point_set_3<Point> Point_set;
int main (int argc, char** argv)
{
std::ifstream f(argc > 1 ? argv[1] : CGAL::data_file_path("points_3/example.ply"),
std::ios_base::binary); // Mandatory on Windows if input is binary PLY
Point_set point_set;
if(!CGAL::IO::read_PLY(f, point_set)) // same as `f >> point_set`
{
std::cerr << "Can't read input file " << std::endl;
return EXIT_FAILURE;
}
// Shows which properties are defined
std::vector<std::string> properties = point_set.properties();
std::cerr << "Properties:" << std::endl;
for(std::size_t i = 0; i < properties.size(); ++ i)
std::cerr << " * " << properties[i] << std::endl;
// Recover "label" property of type int
std::optional<Point_set::Property_map<std::int32_t>> label_prop = point_set.property_map<std::int32_t> ("label");
if(label_prop.has_value())
{
std::cerr << "Point set has an integer \"label\" property with values:" << std::endl;
for (Point_set::iterator it = point_set.begin(); it != point_set.end(); ++ it)
std::cerr << " * " << (*label_prop)[*it] << std::endl;
}
if(argc > 2 && strcmp (argv[2], "-b") == 0) // Optional binary output
{
CGAL::IO::write_PLY("out.ply", point_set, CGAL::parameters::stream_precision(17));
}
else // ASCII output
{
CGAL::IO::write_PLY("out.ply", point_set, CGAL::parameters::stream_precision(17)
.use_binary_mode(false));
}
return 0;
}
CGAL::IO::read_PLY
bool read_PLY(std::istream &is, PointRange &points, PolygonRange &polygons, std::string &comments, const NamedParameters &np=parameters::default_values())
CGAL::IO::write_PLY
bool write_PLY(std::ostream &out, const PointRange &points, const PolygonRange &polygons, const NamedParameters &np=parameters::default_values())

## Advanced Usage

Using functions of CGAL to read files requires a slightly different behavior because internally the properties of a point are defined before this point is inserted into the point set (which is not possible with `CGAL::Point_set_3`). Although using the provided overloads presented in the previous subsection should cover most usages, we document the specific back inserters and property maps that are used internally:

- `CGAL::Point_set_3::index_back_inserter()` is used as an output iterator that creates new points.
- `CGAL::Point_set_3::point_push_map()` is a property map for setting the coordinates of a point. It will first insert the point create in the structure if it has not been created first (by `index_back_inserter()` for example).
- `CGAL::Point_set_3::normal_push_map()` works similarly but for normal vectors.

Such push property maps are also available for other user-defined properties (see `CGAL::Point_set_3::push_property_map()`).

The following example shows how to read OFF point without using the overload provided for `CGAL::Point_set_3`:

Example: Point_set_3/point_set_advanced.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Point_set_3.h>
#include <CGAL/IO/read_points.h>
#include <fstream>
#include <limits>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::FT FT;
typedef Kernel::Point_3 Point;
typedef Kernel::Vector_3 Vector;
typedef CGAL::Point_set_3<Point> Point_set;
int main (int argc, char** argv)
{
const std::string filename = argc > 1 ? argv[1] : CGAL::data_file_path("meshes/camel.off");
Point_set point_set;
point_set.add_normal_map();
// Reading input in OFF format
if(!CGAL::IO::read_points(filename, point_set.index_back_inserter(),
CGAL::parameters::point_map(point_set.point_push_map())
.normal_map(point_set.normal_push_map())))
{
std::cerr << "Can't read input file " << std::endl;
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}
CGAL::IO::read_points
bool read_points(const std::string &fname, PointOutputIterator output, const NamedParameters &np=parameters::default_values())

## Draw a Point Set

A 3D point set can be visualized by calling the CGAL::draw<PS>() function as shown in the following example. This function opens a new window showing the given point set. A call to this function is blocking, that is the program continues as soon as the user closes the window.

Example: Point_set_3/draw_point_set_3.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Point_set_3.h>
#include <CGAL/draw_point_set_3.h>
#include <fstream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::FT FT;
typedef Kernel::Point_3 Point;
typedef Kernel::Vector_3 Vector;
typedef CGAL::Point_set_3<Point> Point_set;
int main (int argc, char** argv)
{
const std::string filename = argc > 1 ? argv[1] : CGAL::data_file_path("points_3/oni.pwn");
Point_set point_set;
if(!CGAL::IO::read_point_set(filename, point_set))
{
std::cerr << "Can't read input file " << filename << std::endl;
return EXIT_FAILURE;
}
CGAL::draw(point_set);
return EXIT_SUCCESS;
}
CGAL::draw
void draw(const PS &ps, const GSOptions &gso)
opens a new window and draws a point set.
CGAL::IO::read_point_set
bool read_point_set(const std::string &fname, CGAL::Point_set_3< Point, Vector > &ps, const NamedParameters &np=parameters::default_values())
reads the point set from an input file.
Definition: IO.h:122

This function requires `CGAL_Qt6`, and is only available if the macro `CGAL_USE_BASIC_VIEWER` is defined. Linking with the cmake target `CGAL::CGAL_Basic_viewer` will link with `CGAL_Qt6` and add the definition `CGAL_USE_BASIC_VIEWER`.

Figure 92.1 Result of the run of the draw_point_set_3 program. A window shows the 3D points and allows to navigate through the 3D scene.

# History

This package has been created to fill the need for a practical data structure that handles points with a user-defined set of properties. A property mechanism was already implemented in the Surface Mesh package: all the classes dedicated to the management of properties were extracted so that they can be used in this package. `CGAL::Surface_mesh<Point>` and `CGAL::Point_set_3<Point,Vector>` now follow a similar API for property management.