CGAL Named Parameters 解析

一、CGAL官方手册解释：

Named Parameters

CGAL and the Boost Graph Library Reference

The algorithms of the Boost Graph Library (BGL) often have many parameters with default values that are appropriate for most cases.

In general, when no special treatment is applied, the values of such parameters are passed as a sequence. Deviating from the default for a certain parameter requires the user to explicitly pass values for all preceding parameters. The solution to this problem is to first write a tag and then the parameter, which for Dijkstra's shortest path algorithm might look as follows:

std::vector<vertex_descriptor> p(num_vertices(g));
std::vector<int> d(num_vertices(g));
vertex_descriptor s = vertex(A, g);
dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]));

In the BGL manual, this is called named parameters. The named parameters in the snippet use the tags predecessor_map and distance_map and they are concatenated using the dot operator.

A similar mechanism was introduced in CGAL, with the small difference that the named parameters tag live in the CGAL::parameters:: namespace and CGAL::parameters::default_values() can be used to indicate that default values of optional named parameters must be used. As in the BGL, named parameters in CGAL are also concatenated using the dot operator, and a typical usage is thus:

Graph g1, g2;

Vertex_point_map_2 vpm_2; // an hypothetical custom property map assigning a Point to the vertices of g2

// without any named parameter (default values are used)
CGAL::copy_face_graph(g1, g2);

// specifying named parameters for the second graph
CGAL::copy_face_graph(g1, g2,
CGAL::parameters::vertex_point_map(vpm) //parameter for g1
.vertex_to_vertex_map(v2v), //other parameter for g1
CGAL::parameters::default_values()); //parameter for g2

​

就是说使用Named Parameters传参与顺序有关，使用传统的方式，当参数多的时候就比较麻烦，容易忘记参数顺序，使用Named Parameters 可以简化传参，不用关注参数顺序，如CGAL::parameters::vertex_point_map(vpm) .vertex_to_vertex_map(v2v)，先传vpm，再传v2v，反过来写也一样，同时将多个参数打包成一个对象，简化了调用操作。

二、官方示例

举个例子，在CGAL-6.0.1\examples\Polygon_mesh_processing\hole_filling_example.cpp

int main(int argc, char* argv[])
{
  const std::string filename = (argc > 1) ? argv[1] : CGAL::data_file_path("meshes/mech-holes-shark.off");

  Mesh poly;
  if(!PMP::IO::read_polygon_mesh(filename, poly))
  {
    std::cerr << "Invalid input." << std::endl;
    return 1;
  }

  // Incrementally fill the holes
  unsigned int nb_holes = 0;
  for(Halfedge_handle h : halfedges(poly))
  {
    if(h->is_border())
    {
      std::vector<Facet_handle>  patch_facets;
      std::vector<Vertex_handle> patch_vertices;
      bool success = std::get<0>(PMP::triangulate_refine_and_fair_hole(poly,
                                                                       h,
                                                                       CGAL::parameters::face_output_iterator(std::back_inserter(patch_facets))
                                                                                        .vertex_output_iterator(std::back_inserter(patch_vertices))
                                                                                        .vertex_point_map(get(CGAL::vertex_point, poly))
                                                                                        .geom_traits(Kernel())));

      std::cout << " Number of facets in constructed patch: " << patch_facets.size() << std::endl;
      std::cout << " Number of vertices in constructed patch: " << patch_vertices.size() << std::endl;
      std::cout << " Fairing : " << (success ? "succeeded" : "failed") << std::endl;
      ++nb_holes;
    }
  }

  std::cout << std::endl;
  std::cout << nb_holes << " holes have been filled" << std::endl;

  std::ofstream out("filled.off");
  out.precision(17);
  out << poly << std::endl;

  return 0;
}

在main函数中，第20行，调用triangulate_refine_and_fair_hole时，使用CGAL::parameters连续传入patch_facets、patch_vertices、get(CGAL::vertex_point, poly)，Kernel()等参数。

在triangulate_hole的实现中，当需要获取参数时，使用get_parameter、choose_parameter函数

三、Named Parameters实现原理

（1）Named_params_impl类

每个参数都是继承Named_params_impl类，Named_params_impl的现如下：

template <typename T, typename Tag, typename Base>
struct Named_params_impl : Base
{
  typename std::conditional<std::is_copy_constructible<T>::value,
                            T, std::reference_wrapper<const T> >::type v; // copy of the parameter if copyable
  Named_params_impl(const T& v, const Base& b)
    : Base(b)
    , v(v)
  {}
};

// partial specialization for base class of the recursive nesting
template <typename T, typename Tag>
struct Named_params_impl<T, Tag, No_property>
{
  typename std::conditional<std::is_copy_constructible<T>::value,
                            T, std::reference_wrapper<const T> >::type v; // copy of the parameter if copyable
  Named_params_impl(const T& v)
    : v(v)
  {}
};

3个模板参数Named_params_impl类：

typename T ： 参数的类型，如int，double等

 typename Tag  : 参数的表示符，CGAL内部预设了很多参数，使用Tag标记

typename Base : 当前Named_params_impl的父类

2个模板参数Named_params_impl类，Base为空类，即：struct No_property {}

（2）Named_function_parameters类

Named_function_parameters继承自上面说的Named_params_impl类，每个参数都会创建一个Named_function_parameters类。

（3）宏定义CGAL_add_named_parameter

CGAL_add_named_parameter有多处定义，它的作用时创建Named_function_parameters类。

先看CGAL::parameters命名空间下的的定义：

如下：

// define free functions and Boost_parameter_compatibility_wrapper for named parameters
#define CGAL_add_named_parameter(X, Y, Z)        \
  template <typename K>                        \
  Named_function_parameters<K, internal_np::X>                  \
  Z(const K& p)                                \
  {                                            \
    typedef Named_function_parameters<K, internal_np::X> Params;\
    return Params(p);                          \
  }

该宏创建一个 CGAL::parameters命名空间的一个全局函数，创建一个Named_function_parameters类，使用两个参数的模板类，其父类为struct No_property类型，并通过构造函数保存用户参数值K p。

再看在CGAL::Named_function_parameters内部的定义：

template <typename T, typename Tag, typename Base>
struct Named_function_parameters
  : internal_np::Named_params_impl<T, Tag, Base>
{
  typedef internal_np::Named_params_impl<T, Tag, Base> base;
  typedef Named_function_parameters<T, Tag, Base> self;

  Named_function_parameters() : base(T()) {}
  Named_function_parameters(const T& v) : base(v) {}
  Named_function_parameters(const T& v, const Base& b) : base(v, b) {}

// create the functions for new named parameters and the one imported boost
// used to concatenate several parameters
#define CGAL_add_named_parameter(X, Y, Z)                             \
  template<typename K>                                                \
  Named_function_parameters<K, internal_np::X, self>                  \
  Z(const K& k) const                                                 \
  {                                                                   \
    typedef Named_function_parameters<K, internal_np::X, self> Params;\
    return Params(k, *this);                                          \
  }

    //其他代码省略***
}

该宏在Named_function_parameters类内部创建一个成员函数，该函数返回一个Named_function_parameters的新类，使用3个参数的模板类，其父类为创建者，并通过构造函数保存新的用户参数值K p。

总结：CGAL_add_named_parameter宏的作用是创建Named_function_parameters类 ，在CGAL::parameters空间下使用全局函数创建时，其父类为空类；使用当前Named_function_parameters类的成员函数创建新的Named_function_parameters类时，其父类为旧的Named_function_parameters类，这个原理实现了链式传递，即第一个参数的父类为空，后面的参数依次为前一个参数的派生类，最后传入的为最底层的一个派生类。

在CGAL/STL_Extension/internal/parameters_interface.h中预设了很多类型的参数：

// List of named parameters that we use in CGAL
CGAL_add_named_parameter(vertex_point_t, vertex_point, vertex_point_map)
CGAL_add_named_parameter(halfedge_index_t, halfedge_index, halfedge_index_map)
CGAL_add_named_parameter(edge_index_t, edge_index, edge_index_map)
CGAL_add_named_parameter(face_index_t, face_index, face_index_map)
CGAL_add_named_parameter(vertex_index_t, vertex_index, vertex_index_map)
CGAL_add_named_parameter(visitor_t, visitor, visitor)

四、CGAL Named Parameters获取参数

choose_parameter和get_parameter函数

参数封装好之后，使用下面的方法获取参数：

    using parameters::choose_parameter;
    using parameters::get_parameter;
    using parameters::get_parameter_reference;

    CGAL_precondition(is_valid_halfedge_descriptor(border_halfedge, pmesh));

    typedef typename internal_np::Lookup_named_param_def<internal_np::face_output_iterator_t,
                                                         CGAL_NP_CLASS,
                                                         Emptyset_iterator>::type Face_output_iterator;

    Face_output_iterator face_out = choose_parameter<Emptyset_iterator>(get_parameter(np, internal_np::face_output_iterator));

    typedef typename internal_np::Lookup_named_param_def<internal_np::vertex_output_iterator_t,
                                                         CGAL_NP_CLASS,
                                                         Emptyset_iterator>::type Vertex_output_iterator;

    Vertex_output_iterator vertex_out = choose_parameter<Emptyset_iterator>(get_parameter(np, internal_np::vertex_output_iterator));

    std::vector<typename boost::graph_traits<PolygonMesh>::vertex_descriptor> patch;
    face_out = triangulate_and_refine_hole
      (pmesh, border_halfedge, np.face_output_iterator(face_out).vertex_output_iterator(std::back_inserter(patch))).first;

get_parameter匹配参数类型，若没匹配到则返回一个空类

// helper function to extract the value from a named parameter pack given a query tag
template <typename T, typename Tag, typename Base>
typename std::conditional<std::is_copy_constructible<T>::value,
                          T, std::reference_wrapper<const T> >::type
get_parameter_impl(const Named_params_impl<T, Tag, Base>& np, Tag)
{
  return np.v;
}

template< typename T, typename Tag, typename Query_tag>
Param_not_found get_parameter_impl(const Named_params_impl<T, Tag, No_property>&, Query_tag)
{
  return Param_not_found();
}

choose_parameter判断目标类是否为空，不为空时获取参数值，为空时使用默认构造函数构造一个

// single parameter so that we can avoid a default construction
template <typename D>
D choose_parameter(const internal_np::Param_not_found&)
{
  return D();
}

template <typename D, typename T>
const T& choose_parameter(const T& t)
{
  return t;
}

五、总结

CGAL Named Parameters 使用模板编程，核心原理时利用C++向上类型转换（Upcasting），可通过链式连接传递多个参数，同时可通过对象向上转换高效的获取任意传入的参数。

向上类型转换是将派生类对象的指针或引用转换为基类类型的指针或引用。它是自动、安全的，不需要显式的类型转换操作。

#include <iostream>
 
class Base {
public:
    virtual void show() { 
        std::cout << "Base class" << std::endl; 
    }
};
 
class Derived : public Base {
public:
    void show() override { 
        std::cout << "Derived class" << std::endl; 
    }
};
 
int main() {
    Derived d;
    Base* basePtr = &d;  // 向上类型转换，自动进行
    basePtr->show();     // 返回 "Derived class" 因为 Base 的 show() 是虚函数
    return 0;
}