User Manual

Authors

Andreas Fabri and Laurent Saboret

A Short Introduction to the Boost Property Maps Library

The Boost Property Map Library consists mainly of interface specifications in the form of concepts. These interface specifications are intended for use by implementors of generic libraries in communicating requirements on template parameters to their users. In particular, the Boost Property Map concepts define a general purpose interface for mapping key objects to corresponding value objects, thereby hiding the details of how the mapping is implemented from algorithms. The implementation of types fulfilling the property map interface is up to the client of the algorithm to provide.

The Boost Property Map Library also contains a few adaptors that convert commonly used data-structures that implement a mapping operation, such as builtin arrays (pointers), iterators, and std::map, to have the property map interface.

Free functions get and put allow getting and putting information through a property map. The data themselves may be stored in the element, or they may be stored in an external data structure, or they may be computed on the fly. This is an "implementation detail" of the particular property map.

Property maps in the Boost manuals: https://www.boost.org/libs/property_map/doc/property_map.html

CGAL and Boost Property Maps

Some algorithms in CGAL take as input parameters iterator ranges and property maps to access information attached to elements of the sequence.

For example, the algorithms of chapters Point Set Processing and Poisson Surface Reconstruction take as input parameters iterator ranges and property maps to access each point's position and normal. Position and normal might be represented in various ways, e.g., as a class derived from the CGAL point class, or as a std::pair<Point_3<K>, Vector_3<K> >, or as a boost::tuple<..,Point_3<K>, ..., Vector_3<K> >.

This component provides property maps to support these cases:

• Identity_property_map<T>
• First_of_pair_property_map<Pair> and Second_of_pair_property_map<Pair>
• Nth_of_tuple_property_map<N, Tuple>
• Dereference_property_map<T>

Example with Identity_property_map

The following example reads a point set and removes 5% of the points. It uses Identity_property_map<Point_3> as position property map.
File Point_set_processing_3/remove_outliers_example.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

#include <CGAL/property_map.h>
#include <CGAL/compute_average_spacing.h>
#include <CGAL/remove_outliers.h>
#include <CGAL/IO/read_points.h>

#include <vector>
#include <fstream>
#include <iostream>

// types
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_3 Point;

int main(int argc, char*argv[])
{
  const std::string fname = (argc>1)?argv[1]:CGAL::data_file_path("points_3/oni.pwn");

  // Reads a point set file in points[].
  // The Identity_property_map property map can be omitted here as it is the default value.
  std::vector<Point> points;
  if(!CGAL::IO::read_points(fname, std::back_inserter(points),
                            CGAL::parameters::point_map(CGAL::Identity_property_map<Point>())))
  {
    std::cerr << "Error: cannot read file " << fname << std::endl;
    return EXIT_FAILURE;
  }

  // Removes outliers using erase-remove idiom.
  // The Identity_property_map property map can be omitted here as it is the default value.
  const int nb_neighbors = 24; // considers 24 nearest neighbor points

  // Estimate scale of the point set with average spacing
  const double average_spacing = CGAL::compute_average_spacing<CGAL::Sequential_tag>(points, nb_neighbors);

  // FIRST OPTION //
  // I don't know the ratio of outliers present in the point set
  std::vector<Point>::iterator first_to_remove
    = CGAL::remove_outliers<CGAL::Parallel_if_available_tag>
    (points,
     nb_neighbors,
     CGAL::parameters::threshold_percent (100.). // No limit on the number of outliers to remove
     threshold_distance (2. * average_spacing)); // Point with distance above 2*average_spacing are considered outliers

  std::cerr << (100. * std::distance(first_to_remove, points.end()) / static_cast<double>(points.size()))
            << "% of the points are considered outliers when using a distance threshold of "
            << 2. * average_spacing << std::endl;


  // SECOND OPTION //
  // I know the ratio of outliers present in the point set
  const double removed_percentage = 5.0; // percentage of points to remove

  points.erase(CGAL::remove_outliers<CGAL::Parallel_if_available_tag>
               (points,
                nb_neighbors,
                CGAL::parameters::threshold_percent(removed_percentage). // Minimum percentage to remove
                threshold_distance(0.)), // No distance threshold (can be omitted)
               points.end());

  // Optional: after erase(), use Scott Meyer's "swap trick" to trim excess capacity
  std::vector<Point>(points).swap(points);

  return EXIT_SUCCESS;
}

Example with Pairs

The following example reads a point set from an input file and writes it to a file, both in the xyz format. Position and normal are stored in pairs and accessed through property maps.
File Point_set_processing_3/read_write_xyz_point_set_example.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

#include <CGAL/property_map.h>
#include <CGAL/IO/read_xyz_points.h>
#include <CGAL/IO/write_xyz_points.h>

#include <utility> // defines std::pair
#include <vector>
#include <fstream>
#include <iostream>

// types
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_3 Point;
typedef Kernel::Vector_3 Vector;

// Point with normal vector stored as a std::pair.
typedef std::pair<Point, Vector> Pwn;

int main(int argc, char*argv[])
{
  const std::string fname = (argc>1) ? argv[1] : CGAL::data_file_path("points_3/oni.pwn");

  // Reads a .xyz point set file in points[].
  // Note: read_points() requires an output iterator
  // over points and as well as property maps to access each
  // point position and normal.
  std::vector<Pwn> points;
  if(!CGAL::IO::read_XYZ(fname,
                         std::back_inserter(points),
                         CGAL::parameters::point_map(CGAL::First_of_pair_property_map<Pwn>())
                                          .normal_map(CGAL::Second_of_pair_property_map<Pwn>())))
  {
    std::cerr << "Error: cannot read file " << fname << std::endl;
    return EXIT_FAILURE;
  }

  // Saves point set.
  // Note: write_XYZ() requires property maps to access each
  // point position and normal.
  if(!CGAL::IO::write_XYZ("oni_copy.xyz", points,
                          CGAL::parameters::point_map(CGAL::First_of_pair_property_map<Pwn>())
                                           .normal_map(CGAL::Second_of_pair_property_map<Pwn>())
                                           .stream_precision(17)))
    return EXIT_FAILURE;

  return EXIT_SUCCESS;
}

Example with Tuples

The following example reads a point set in the xyz format and computes the average spacing. Index, position and color are stored in a tuple and accessed through property maps.
File Point_set_processing_3/average_spacing_example.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/compute_average_spacing.h>
#include <CGAL/IO/read_points.h>

#include <vector>
#include <fstream>
#include <boost/tuple/tuple.hpp>

// Types
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::FT FT;
typedef Kernel::Point_3 Point;

// Data type := index, followed by the point, followed by three integers that
// define the Red Green Blue color of the point.
typedef boost::tuple<int, Point, int, int, int> IndexedPointWithColorTuple;

// Concurrency
typedef CGAL::Parallel_if_available_tag Concurrency_tag;

int main(int argc, char*argv[])
{
  const std::string fname = (argc>1)?argv[1]:CGAL::data_file_path("points_3/sphere_20k.xyz");

  // Reads a file in points.
  // As the point is the second element of the tuple (that is with index 1)
  // we use a property map that accesses the 1st element of the tuple.

  std::vector<IndexedPointWithColorTuple> points;
  if (!CGAL::IO::read_points(fname, std::back_inserter(points),
                             CGAL::parameters::point_map(CGAL::Nth_of_tuple_property_map<1, IndexedPointWithColorTuple>())))
  {
    std::cerr << "Error: cannot read file " << fname << std::endl;
    return EXIT_FAILURE;
  }

  // Initialize index and RGB color fields in tuple.
  // As the index and RGB color are respectively the first and third-fifth elements
  // of the tuple we use a get function from the property map that accesses the 0
  // and 2-4th elements of the tuple.
  for(unsigned int i = 0; i < points.size(); i++)
  {
    points[i].get<0>() = i; // set index value of tuple to i

    points[i].get<2>() = 0; // set RGB color to black
    points[i].get<3>() = 0;
    points[i].get<4>() = 0;
  }

  // Computes average spacing.
  const unsigned int nb_neighbors = 6; // 1 ring
  FT average_spacing = CGAL::compute_average_spacing<Concurrency_tag>(
                         points, nb_neighbors,
                         CGAL::parameters::point_map(CGAL::Nth_of_tuple_property_map<1,IndexedPointWithColorTuple>()));

  std::cout << "Average spacing: " << average_spacing << std::endl;

  return EXIT_SUCCESS;
}

Writing Custom Property Maps

Property maps are especially useful when using predefined data structures that are not part of the CGAL library: algorithms written with property maps can be called on these data structures provided the user writes the required property maps, without the need to create deep copies of potentially large data into CGAL formats.

The following example shows how to write a readable point map and a read-write normal map to run CGAL normal estimation and orientation algorithm on raw double arrays:
File Property_map/custom_property_map.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/point_generators_3.h>
#include <CGAL/jet_estimate_normals.h>
#include <CGAL/mst_orient_normals.h>

using Kernel = CGAL::Exact_predicates_inexact_constructions_kernel;
using Point_3 = Kernel::Point_3;
using Vector_3 = Kernel::Vector_3;
using Generator = CGAL::Random_points_on_sphere_3<Point_3>;

// Example of readable property map to get CGAL::Point_3 objects from
// 3 coordinate arrays
struct Custom_point_map
{
  using key_type = std::size_t; // The iterator's value type is an index
  using value_type = Point_3;   // The object manipulated by the algorithm is a Point_3
  using reference = Point_3;    // The object does not exist in memory, so there's no reference
  using category = boost::readable_property_map_tag; // The property map is only used for reading

  double *x, *y, *z;

  Custom_point_map (double* x = nullptr, double* y = nullptr, double* z = nullptr)
    : x(x), y(y), z(z) { }

  // The get() function returns the object expected by the algorithm (here, Point_3)
  friend Point_3 get (const Custom_point_map& map, std::size_t idx)
  {
    return Point_3 (map.x[idx], map.y[idx], map.z[idx]);
  }
};

// Example of read-write property map to get CGAL::Vector_3 objects from
// a buffer array and put CGAL::Vector_3 values in this buffer
struct Custom_normal_map
{
  using key_type = std::size_t; // The iterator's value type is an index
  using value_type = Vector_3;  // The object manipulated by the algorithm is a Vector_3
  using reference = Vector_3;   // The object does not exist in memory, so there's no reference
  using category = boost::read_write_property_map_tag; // The property map is used both
                                                       // for reading and writing data
  double *buffer;

  Custom_normal_map (double* buffer = nullptr)
    : buffer (buffer) { }

  // The get() function returns the object expected by the algorithm (here, Vector_3)
  friend Vector_3 get (const Custom_normal_map& map, std::size_t idx)
  {
    return Vector_3 (map.buffer[idx * 3    ],
                     map.buffer[idx * 3 + 1],
                     map.buffer[idx * 3 + 2]);
  }

  // The put() function updated the user's data structure from the
  // object handled by the algorithm (here Vector_3)
  friend void put (const Custom_normal_map& map, std::size_t idx, const Vector_3& vector_3)
  {
    map.buffer[idx * 3    ] = vector_3.x();
    map.buffer[idx * 3 + 1] = vector_3.y();
    map.buffer[idx * 3 + 2] = vector_3.z();
  }
};


int main()
{
  constexpr std::size_t nb_points = 1000;

  // in this example, points are stored as separate coordinate arrays
  double x[nb_points];
  double y[nb_points];
  double z[nb_points];

  // generate random points
  Generator generator;
  for (std::size_t i = 0; i < nb_points; ++ i)
  {
    Point_3 p = *(generator ++ );
    x[i] = p.x();
    y[i] = p.y();
    z[i] = p.z();
  }

  // normals are stored as a contiguous double array
  double normals[3 *nb_points];

  // we use a vector of indices to access arrays
  std::vector<std::size_t> indices;
  indices.reserve (nb_points);
  for (std::size_t i = 0; i < nb_points; ++ i)
    indices.push_back(i);

  // estimate and orient normals using directly user's data structure
  // instead of creating deep copies using Point_3 and Vector_3
  CGAL::jet_estimate_normals<CGAL::Sequential_tag>
    (indices, 12,
     CGAL::parameters::point_map (Custom_point_map(x,y,z)).
     normal_map (Custom_normal_map(normals)));

  CGAL::mst_orient_normals
    (indices, 12,
     CGAL::parameters::point_map (Custom_point_map(x,y,z)).
     normal_map (Custom_normal_map(normals)));

  // Display first 10 points+normals
  for (std::size_t i = 0; i < 10; ++ i)
    std::cerr << "Point(" << i << ") = " << x[i] << " " << y[i] << " " << z[i]
              << "\tNormal(" << i << ") = "
              << normals[3*i] << " " << normals[3*i+1] << " " << normals[3*i+2] << std::endl;

  return EXIT_SUCCESS;
}