CGAL是一个优秀的几何处理库，对于三维网格采用半边格式存储。
其实对于网格而言，无外乎定义它的边，顶点，面，数据存储。
问题是用户可能会有不同的需求，比如做模型简化，需要对每个顶点加一个cost域，而对其它应用则不需要，
也许你会说可以给基本的定点数据结构加一个指针，用户自己定义其它的数据都由该指针指向，但这种设计并不好。
显然模板化处理是更好的方法，不要把顶点类型定死。
这样一来我们可以通过让一个网格类，拥有不同的顶点类型，边类型，面类型，具体类型由用户决定，用户可以通过
继承底层提供的基本类型，加入自己 的需要的属性，方法，生成新的类型，作为template参数，并传给网格类。从而实现
了网格的灵活设计。
CGAL就是采用了这一方法，但是它有大量的模板技巧，wrapper class 包装等等，从而对于想要了解底层具体实现的而言
显得比较复杂难于理解，虽然它的使用还是很简单方便的。 下面我将根据参考文献 Using Generic Programming for Designing a Data Structure for Polyhedral Surface
介绍其模板类设计的非常简洁的核心的思想，并给出代码实例，注意和实际CGAL实现代码是有出入的，这里做了简化
（比如CGAL对顶点，边，面数据结构进行了wrapper class封装，使得wrapper class没有任何模板参数)，但是思想是一致的。
这里为了简单，去掉面，仅仅考虑边和顶点，对于顶点我们要记录它的对应的半边信息，对于半边我们也要记录顶点信息，
问题是对于特定的item type，比如顶点，它不知道其相关联的其它item的具体类型,如半边的具体类型。
在CGAL的设计中，vertex顶点，通过一个placeholder来获得其它item的类型信息。(在下面的小程序演示中，HalfedgeDS作为那个placeholder,存储所有iterm的类型信息)
CGAL将所有的局部类型信息，如顶点，半边，面放在一个单一的模板参数Refs中。
在顶点中仅仅用到 Halfedge_handel作为对应的halfedge的引用。
其他如半边，面的设计类似。
对于整体的半边数据结构，它将会由如顶点，半边，面的类型来模板化，(parameterized with the item types)
但是item types如顶点，已经是 class template模板类了，所以我们需要 template as template arguments 即模板参数本身是模板类
这种方法还是很常见的，比如考虑二叉树的设计，允许二叉树类装配不同类型的节点，即节点是模板参数
而节点类本身允许有不同的存储数据类型，也就是说节点本身就是模板类。
可以采用下面的设计
二叉树节点类
template <typename ElemType>
class Node {
private:
ElemType m_data;
};
二叉树类
template <template<type Elem> class Node, typename U>
class BinaryTree {
private:
Node<U> *m_root;
};
具体使用
BinaryTree< Node, int> MyBinaryTree; 即可。
好回到CGAL中，这里的类型依赖构成了一个循环，半边数据结构需要vertex,halfedge类型参数的实化，而半边数据结构类halfedge ds知道 handle 类型，可以用做Refs 参数的实际类型， 尽管当前handles还没有被声明（vertex,halfedge同样需要半边数据结构类来实化)。声明和定义的不同使得这一切成为可能。
struct Edge;
struct Node {
Edge * edge;
// .... maybe more than one edge ....
};
struct Edge {
Node * source;
Node * dest;
};
//最简单的一个示例
template <class Graph> struct Node { typedef typename Graph::Edge Edge; Edge* edge; // .... maybe some more edges .... }; template <class Graph> struct Edge { typedef typename Graph::Node Node; Node* node; }; template < template <class G> class T_Node, template <class G> class T_Edge> struct Graph { typedef Graph< T_Node, T_Edge> Self; typedef T_Node<Self> Node; typedef T_Edge<Self> Edge; }; int main() { typedef Graph< Node, Edge> G; G::Node node; G::Edge edge; node.edge = &edge; edge.node = &node; }
template <class Graph> struct Colored_node : public Node<Graph> { int color; }; int main() { typedef Graph< Colored_node, Edge> G; G::Node node; G::Edge edge; node.edge = &edge; edge.node = &node; node.color = 3; }
注意上面代码用的是指针，本质上还是利用前置声明，如果改为Edge edge，就不行了，因为那样编译器需要知道Edge的定义，前置声明不行。
It is important to understand that these cyclic definitions work -- as for the C example -- because we can make use of a declared type to define pointers and references to this type before this type is defined itself. For example, we cannot change the pointer member Edge * edge of the node class to a value Edge edge.
好了，说了这么多看实际的代码吧。
我写了个小程序测试了一下，为了测试加入了显示PrintName的代码。
//simple_cgal.h
#include <list> #include <string> #include <iostream> using std::list; using std::string; using std::cout; using std::endl; template <typename Refs> struct Vertex { typedef typename Refs::Halfedge_handle Halfedge_handle; Vertex(string name = "vertex0") { m_name = name;}void PrintName() const {
cout << "This is " << m_name << endl;
}Halfedge_handle halfedge() const { return h; } void set_halfedge (Halfedge_handle g) { h = g; } private: Halfedge_handle h; string m_name; };template <typename Refs> struct Halfedge { typedef typename Refs::Vertex_handle Vertex_handle; Halfedge(string name = "halfedge0") { m_name = name;} void PrintName() const { cout << "This is " << m_name << endl;} Vertex_handle vertex() const { return v;} void set_vertex (Vertex_handle vv) { v = vv;} private: Vertex_handle v; string m_name; };template < template <typename Ref> class Vertex, template <typename Ref> class Halfedge> struct HalfedgeDS { typedef HalfedgeDS< Vertex, Halfedge> Self; typedef Vertex<Self> V; typedef Halfedge<Self> H; typedef list<V> Vlist; typedef list<H> Hlist; typedef typename Vlist::iterator Vertex_handle; typedef typename Hlist::iterator Halfedge_handle; };//test_simple_cgal.cc
#include "simple_cgal.h" #include <iostream> using namespace std; int main(int argc, char *argv[]) {
typedef HalfedgeDS< Vertex, Halfedge> HDS;
typedef HDS::V Vert;
typedef HDS::H HalfEdge;
typedef HDS::Vlist Vlist;
typedef HDS::Hlist Hlist;
Vert v("vertex a");
HalfEdge h("Halfedge b");
Vlist vlist;
Hlist hlist;
vlist.push_back(v);
hlist.push_back(h);
v.set_halfedge(hlist.begin());
h.set_vertex(vlist.begin());
v.halfedge()->PrintName();
h.vertex()->PrintName();
return 0;
}
运行结果：
This is Halfedge b
This is vertex a
CGAL中实际的定义对于顶点，边和面元素进行了封装，将他们放在同一个不带模板参数的类里面，类似下面代码模仿的HalfedgeDS_iems，
从而将他们集中到一起并且最外层去掉模板参数，里面通过wrapper将他们的定义包装。用户可以定义不同的顶点类，只要
在传给HalfedgeDS的HalfedgeItesms参数的类中typedef 自己定义的顶点类为Vertex即可。
//简单模拟vertex,halfedge wrapper用法演示
//simple_cgal2.h
#include <list> #include <string> #include <iostream> using std::list; using std::string; using std::cout; using std::endl; template <typename Refs> struct Vertex { typedef typename Refs::Halfedge_handle Halfedge_handle; Vertex(string name = "vertex0") { m_name = name;} void PrintName() const { cout << "This is " << m_name << endl;} Halfedge_handle halfedge() const { return h; } void set_halfedge (Halfedge_handle g) { h = g; } private: Halfedge_handle h; string m_name; }; template <typename Refs> struct Halfedge { typedef typename Refs::Vertex_handle Vertex_handle; Halfedge(string name = "halfedge0") { m_name = name;} void PrintName() const { cout << "This is " << m_name << endl;} Vertex_handle vertex() const { return v;} void set_vertex (Vertex_handle vv) { v = vv;} private: Vertex_handle v; string m_name; }; struct HalfedgeDS_iems { template <class Refs> struct Vertex_wrapper { typedef Vertex<Refs> Vertex;}; template <class Refs> struct Halfedge_wrapper { typedef Halfedge<Refs> Halfedge;};}; template < typename HalfedgeDSItems> struct HalfedgeDS { typedef HalfedgeDS< HalfedgeDSItems> Self; typedef HalfedgeDSItems Items; typedef typename Items::template Vertex_wrapper<Self> Vertex_wrapper;typedef typename Items::template Halfedge_wrapper<Self>Halfedge_wrapper;typedef typename Vertex_wrapper::Vertex Vertex;typedef typename Halfedge_wrapper::Halfedge Halfedge;typedef list<Vertex> Vlist;typedef list<Halfedge> Hlist;typedef typename Vlist::iterator Vertex_handle;typedef typename Hlist::iterator Halfedge_handle;};//test_simgple_cgal2.cc#include "simple_cgal2.h"
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
typedef HalfedgeDS<HalfedgeDS_iems