商务合作:179001057@qq.com

CGAL几何库 半边网格数据结构 模板类 设计核心思想

技术2022-05-12  7


某平台价值19860元的编程课程资料免费领取【点我领取】


原文链接: http://www.cnblogs.com/rocketfan/archive/2009/07/05/1517200.html

      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> HDS; typedef HDS::Vertex Vert; typedef HDS::Halfedge 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; } 运行结果和上面程序一致。 多了一个HalfedgeDS_iems包装的一个好处是由于HalfedgeDS_iems没有模板参数,所以下面的定义是可能的,CGAL中 定义有Polyhedron它的一个模板参数是HDS,即半边结构,考虑上面没有封装到HalfedgeItesms的方案, template < template <typename Ref> class Vertex, template <typename Ref> class Halfedge> struct HalfedgeDS HalfedgeDS的定义已经有两级模板参数了,如果再被传递会有三级模板参数,C++是不允许这样的,所以HalfedgeDS_iems 方法不失为一种绕过的技巧。 template < class Traits, class Items = Items_default, template < class, class> calss HDS = HalfedgeDS_default> struct Polyhedron { typedef Polyhedron_items<Items> Deerived_items; typedef HDS< Traits, Derived_items> HDS; typedef typename HDS::Vertex Vertex; typedef typename HDS::Halfedge Halfedge; typedef typename HDS::Face Face; ..... }; 关于Polyhedron_items<Items>下面给予介绍。 先看一个用户自己扩充面的例子,完全继承已有的边和顶点,用户当然也可以全部扩充,总之通过wrapper是很灵活的。 template <class Refs, class Triats> class My_facet : public CGAL_HalfedgeDS_facet_base<Refs> { int face_cost; // we need to sore addtional info public: typename Traits::Vector_3 normal; }; struct My_items : public CGAL_Polyhedron_items_3 { template <class Refs, class Traits> struct Face_wrapper { typedef My_facet< Refs, Traits> Facet; }; }; typedef CGAL_Polyhedron_3<Traits, My_items> Polyhedron; OK,用户使用起来就是这么简单,这样我们的Polyhedron就是应用用户定义的facet了同时保留了CGAL_Polyhedron_items_3中 定义的facet的所以属性函数,如set_handle.由于用户没有定义Vertex和Halfedge所以它们完全用CGAL_Polyhedron_items_3中 提供的Vertex和Halfege不加任何扩充。 //CGAL源代码 class Polyhedron_items_3 { public: template < class Refs, class Traits> struct Vertex_wrapper { typedef typename Traits::Point_3 Point; typedef HalfedgeDS_vertex_base< Refs, Tag_true, Point> Vertex; }; template < class Refs, class Traits> struct Halfedge_wrapper { typedef HalfedgeDS_halfedge_base< Refs> Halfedge; }; template < class Refs, class Traits> struct Face_wrapper { typedef typename Traits::Plane_3 Plane; typedef HalfedgeDS_face_base< Refs, Tag_true, Plane> Face; }; }; template < class Refs > class HalfedgeDS_face_base< Refs, Tag_true, Tag_false> { public: typedef Refs HalfedgeDS; typedef HalfedgeDS_face_base< Refs, Tag_true, Tag_false> Base; typedef Tag_true Supports_face_halfedge; typedef typename Refs::Vertex_handle Vertex_handle; typedef typename Refs::Vertex_const_handle Vertex_const_handle; typedef typename Refs::Halfedge_handle Halfedge_handle; typedef typename Refs::Halfedge_const_handle Halfedge_const_handle; typedef typename Refs::Face_handle Face_handle; typedef typename Refs::Face_const_handle Face_const_handle; typedef typename Refs::Vertex Vertex; typedef typename Refs::Halfedge Halfedge; // Additional tags required by Polyhedron. typedef Tag_false Supports_face_plane; struct Plane_not_supported {}; typedef Plane_not_supported Plane; // No longer required. //typedef Tag_false Supports_face_normal; private: Halfedge_handle hdg; public: Halfedge_handle halfedge() { return hdg; } Halfedge_const_handle halfedge() const { return hdg; } void set_halfedge( Halfedge_handle h) { hdg = h; } }; 这里面实现还是有另外的技巧,原文章中又以vertex举例了,就按照vertex继续吧。 用户自定义的Items,Vetex会被当作模板参数传递如下。 template <class Vertex_base> struct Polyhedron_vertex : public Vertex_base { typedef Vertex_base Base; private: void set_halfedge(typename Base::Halfedge_handle g) { Base::set_halfedge(g); } }; template <class Items> struct Polyhderon_items { template <class Refs, class Traits> struct Vertex_wrapper { typedef typename Items::Vertex_wrapper<Refs, Traits> Wrapper; typedef typename Wrapper::Vertex Vertex_base; typedef Polyhedron_vertex<Vertex_base> Vertex; }; //similar for facet and halfedge }; template < class Traits, class Items = Items_default, template < class, class> calss HDS = HalfedgeDS_default> struct Polyhedron { typedef Polyhedron_items<Items> Deerived_items; typedef HDS< Traits, Derived_items> HDS; typedef typename HDS::Vertex Vertex; typedef typename HDS::Halfedge Halfedge; typedef typename HDS::Face Face; ..... }; 也就是说最后实际用的是Polyhedron_items<Items> 中定义的Vertex Polyhedron_vertex<Vertex_base> 而 Items即为用户定义并传递的点面边数据类型类。Vertex_base是用户定义的Vertex类型。 下面看一下CGAL实际的代码,这里的I_Polyhedron_vertex其实就是上面的Polyhedron_vertex。 template <class VertexBase> class I_Polyhedron_vertex : public VertexBase { public: typedef VertexBase Base; //typedef typename Base::HalfedgeDS HDS; typedef typename Base::Point Point; typedef Point Point_3; // Handles have to explicitly repeated, although they are derived typedef typename Base::Vertex_handle Vertex_handle; typedef typename Base::Halfedge_handle Halfedge_handle; typedef typename Base::Face_handle Face_handle; typedef typename Base::Face_handle Facet_handle; typedef typename Base::Vertex_const_handle Vertex_const_handle; typedef typename Base::Halfedge_const_handle Halfedge_const_handle; typedef typename Base::Face_const_handle Face_const_handle; typedef typename Base::Face_const_handle Facet_const_handle; typedef typename Base::Halfedge Halfedge; typedef typename Base::Face Face; typedef typename Base::Face Facet; // Supported options by HDS. typedef typename Base::Supports_vertex_halfedge Supports_vertex_halfedge; typedef typename Base::Supports_vertex_point Supports_vertex_point; // Circulator category. typedef typename Halfedge::Supports_halfedge_prev Supports_prev; public: // Circulator category. typedef HalfedgeDS_circulator_traits<Supports_prev> Ctr; typedef typename Ctr::iterator_category circulator_category; // Circulators around a vertex and around a facet. typedef I_HalfedgeDS_facet_circ< Halfedge_handle, circulator_category> Halfedge_around_facet_circulator; typedef I_HalfedgeDS_vertex_circ< Halfedge_handle, circulator_category> Halfedge_around_vertex_circulator; typedef I_HalfedgeDS_facet_circ< Halfedge_const_handle, circulator_category> Halfedge_around_facet_const_circulator; typedef I_HalfedgeDS_vertex_circ< Halfedge_const_handle, circulator_category> Halfedge_around_vertex_const_circulator; typedef typename Halfedge_around_vertex_circulator::size_type size_type; typedef typename Halfedge_around_vertex_circulator::difference_type difference_type; public: // We need to repeat the constructors here. I_Polyhedron_vertex() {} I_Polyhedron_vertex( const VertexBase& b) : VertexBase(b) {} I_Polyhedron_vertex( const Point_3& p) : VertexBase(p) {} // New Access Functions (not provided in VertexBase). Halfedge_around_vertex_circulator vertex_begin() { // a circulator of halfedges around the vertex (clockwise). return Halfedge_around_vertex_circulator( this->halfedge()); } Halfedge_around_vertex_const_circulator vertex_begin() const { // a circulator of halfedges around the vertex (clockwise). return Halfedge_around_vertex_const_circulator( this->halfedge()); } // the degree of the vertex, i.e., edges emanating from this vertex std::size_t vertex_degree() const { return this->halfedge()->vertex_degree(); } size_type degree() const { return vertex_degree(); } //backwards compatible // returns true if the vertex has exactly two incident edges bool is_bivalent() const { return this->halfedge()->is_bivalent(); } // returns true if the vertex has exactly three incident edges bool is_trivalent() const { return this->halfedge()->is_trivalent(); } // No longer hidden. Now the restricted version with precondition. // sets incident halfedge to h. Precondition: h is incident, i.e., // h->vertex() == v. void set_halfedge( Halfedge_handle hh) { CGAL_assertion( &*(hh->vertex()) == this); Base::set_halfedge(hh); } }; //所有这些内容对应的具体CGAL源代码参照 /usr/local/include/CGAL Polyhedron_3.h HalfedgeDS_vector.h //vecotor和list思路一致不过是采用不同的内部数据组织,vector或者list HalfedgeDS_list.h Polyhedron_items_3.h HalfedgeDS_halfedge_base.h

最新回复(0)