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.

File Point_set_3/point_set.cpp

#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;
}

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.

File Point_set_3/point_set_property.cpp

#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 CGAL::cpp11::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;
  boost::tie (color, boost::tuples::ignore) = point_set.property_map<Color>("color");
  FT_map intensity;
  boost::tie (intensity, boost::tuples::ignore) =  point_set.property_map<FT>("intensity");
  
  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 [" << (int)(color[*it][0])
              << " " << (int)(color[*it][1])
              << " " << (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;

  boost::tie (color, success) = point_set.add_property_map<Color> ("color", black);
  assert (success);

  FT_map intensity;
  boost::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 = {{ (unsigned char)(CGAL::get_default_random().get_int(0, 255)),
                   (unsigned char)(CGAL::get_default_random().get_int(0, 255)),
                   (unsigned char)(CGAL::get_default_random().get_int(0, 255)) }};
      color[*it] = c;
      intensity[*it] = rand() / (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;
}

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_3::Efficient_RANSAC

File Point_set_3/point_set_algo.cpp

#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_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::Random_points_on_sphere_3<Point> Point_generator;

typedef CGAL::Point_set_3<Point> Point_set;

typedef CGAL::Shape_detection_3::Shape_detection_traits
<Kernel, Point_set, Point_set::Point_map, Point_set::Vector_map> Traits;
typedef CGAL::Shape_detection_3::Efficient_RANSAC<Traits>        Efficient_ransac;
typedef CGAL::Shape_detection_3::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);
  
  BOOST_FOREACH(boost::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;
}

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.

File Point_set_3/point_set_read_xyz.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Point_set_3.h>
#include <CGAL/Point_set_3/IO.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] : "data/oni.xyz");

  Point_set point_set;

  // Reading input in XYZ format
  if (!f || !CGAL::read_xyz_point_set (f, 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
  std::ofstream out("normalized_normals.off");
  out.precision(17);
  if (!out || !CGAL::write_off_point_set (out, point_set))
    {
      return EXIT_FAILURE;
    }
    
  return EXIT_SUCCESS;
}

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_point_set() 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 boost::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 CGAL::cpp11::array for example).

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

File Point_set_3/point_set_read_ply.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Point_set_3.h>
#include <CGAL/Point_set_3/IO.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] : "data/example.ply");

  Point_set point_set;

  if (!f || !CGAL::read_ply_point_set (f, point_set))
    {
      std::cerr << "Can't read input file " << std::endl;
    }

  // 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
  Point_set::Property_map<boost::int32_t> label_prop;
  bool found = false;
  boost::tie (label_prop, found)  = point_set.property_map<boost::int32_t> ("label");
  
  if (found)
    {
      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;
    }

  std::ofstream out ("out.ply");
  out.precision(17);
  CGAL::write_ply_point_set (out, point_set);
  
  return 0;
}

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:

File Point_set_3/point_set_advanced.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Point_set_3.h>
#include <CGAL/IO/read_off_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)
{
  std::ifstream f (argc > 1 ? argv[1] : "data/camel.off");

  Point_set point_set;
  point_set.add_normal_map();
  // Reading input in OFF format
  if (!f || !CGAL::read_off_points
                   (f,
                    point_set.index_back_inserter(), // OutputIterator
                    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;
}

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.