WebSVN – gelsvn – Diff – /branches/MPC/src/HMesh/templates.h


#ifndef __ITERS_H
#define __ITERS_H
 
#include "CGLA/Vec3f.h"
#include <list>
 
 
namespace HMesh
{
		/* A nasty template trick:
 
		The halfedge data structure is based on pointers. Thus, for instance,
		a halfedge contains pointers to several other halfedges, a face, and
		a vertex. However, the entities (faces, edges, vertices) are stored in
		linked lists. This enables easy insertion and removal, but we would
		like to be able to take the halfedge pointer stored in, say, a 
		halfedge and find the position in the linked list in order to remove the
		halfedge from the list. This is not possible since the list is implemented
		using STL and what we need is really an iterator to the list element
		containing the halfedge.
 
		The solution is, of course, to store iterators instead of pointers, but
		that solution is problematic because we cannot define an iterator to a 
		list of halfedges in the definition of the halfedge class. The solution
		is to let a template argument define the halfedge iterator type.
		 
		Thus the Iters class instantiates HalfEdge_template with itself while it 
		also defines the required iterators etc. Strange but legal C++.
 
		This is the best solution I could come up with - since I really wanted 
		to use STL to store the elements. The solution is similar to what is 
		used in CGAL and OpenMesh both of which provided inspiration. */
 
		/** \struct Vertex
		 */
		template<class R>
		struct Vertex_template
		{
				typedef typename R::VertexIter VertexIter;
				typedef typename R::FaceIter FaceIter;
				typedef typename R::HalfEdgeIter HalfEdgeIter;
 
				/// Constructor, argument is vertex position
				Vertex_template(const CGLA::Vec3f&);
 
				/// Outgoing halfedge
				HalfEdgeIter he;
 
				/// Geometric vertex position
				CGLA::Vec3f pos;
 
				/// General purpose integer. Normally used as index or flag.
				int touched;
		};
 
		template<class R>
		struct HalfEdge_template
		{
				typedef typename R::VertexIter VertexIter;
				typedef typename R::FaceIter FaceIter;
				typedef typename R::HalfEdgeIter HalfEdgeIter;
 
				/// Constructor
				HalfEdge_template();
 
				/// Vertex pointed to by this halfedge.
				VertexIter   vert;
 
				/// Next halfedge in face loop.
				HalfEdgeIter next;
 
				/// Previous halfedge in face loop.
				HalfEdgeIter prev;
 
				/// Face owning this halfedge
				FaceIter     face;
 
				/// Opposite halfedge
				HalfEdgeIter opp;
 
				/// General purpose integer. Normally used as index or flag.
				int touched;
 
		};
 
		template<class R>
		struct Face_template
		{
				typedef typename R::VertexIter VertexIter;
				typedef typename R::FaceIter FaceIter;
				typedef typename R::HalfEdgeIter HalfEdgeIter;
 
				/// Constructor
				Face_template();
 
				/// Last is just some halfedge in the face loop.
				HalfEdgeIter last;
 
				/// General purpose integer. Normally used as index or flag.
				int touched;
		};
 
		struct Iters
		{
				typedef Vertex_template<Iters> V;
				typedef HalfEdge_template<Iters> HE;
				typedef Face_template<Iters> F;
	
				typedef std::list<V> VertexList;
				typedef std::list<HE> HalfEdgeList;
				typedef std::list<F> FaceList;
 
				typedef VertexList::iterator VertexIter;
				typedef HalfEdgeList::iterator HalfEdgeIter;
				typedef FaceList::iterator FaceIter;
		};
 
 
 
}
#endif
 

Rev 67	Rev 94
1	`#ifndef __ITERS_H`	1	`#ifndef __ITERS_H`
2	`#define __ITERS_H`	2	`#define __ITERS_H`
3		3
4	`#include "CGLA/Vec3f.h"`	4	`#include "CGLA/Vec3f.h"`
5	`#include <list>`	5	`#include <list>`
6		6
7		7
8	`namespace HMesh`	8	`namespace HMesh`
9	`{`	9	`{`
10	`/* A nasty template trick:`	10	`/* A nasty template trick:`
11		11
12	`The halfedge data structure is based on pointers. Thus, for instance,`	12	`The halfedge data structure is based on pointers. Thus, for instance,`
13	`a halfedge contains pointers to several other halfedges, a face, and`	13	`a halfedge contains pointers to several other halfedges, a face, and`
14	`a vertex. However, the entities (faces, edges, vertices) are stored in`	14	`a vertex. However, the entities (faces, edges, vertices) are stored in`
15	`linked lists. This enables easy insertion and removal, but we would`	15	`linked lists. This enables easy insertion and removal, but we would`
16	`like to be able to take the halfedge pointer stored in, say, a`	16	`like to be able to take the halfedge pointer stored in, say, a`
17	`halfedge and find the position in the linked list in order to remove the`	17	`halfedge and find the position in the linked list in order to remove the`
18	`halfedge from the list. This is not possible since the list is implemented`	18	`halfedge from the list. This is not possible since the list is implemented`
19	`using STL and what we need is really an iterator to the list element`	19	`using STL and what we need is really an iterator to the list element`
20	`containing the halfedge.`	20	`containing the halfedge.`
21		21
22	`The solution is, of course, to store iterators instead of pointers, but`	22	`The solution is, of course, to store iterators instead of pointers, but`
23	`that solution is problematic because we cannot define an iterator to a`	23	`that solution is problematic because we cannot define an iterator to a`
24	`list of halfedges in the definition of the halfedge class. The solution`	24	`list of halfedges in the definition of the halfedge class. The solution`
25	`is to let a template argument define the halfedge iterator type.`	25	`is to let a template argument define the halfedge iterator type.`
26		26
27	`Thus the Iters class instantiates HalfEdge_template with itself while it`	27	`Thus the Iters class instantiates HalfEdge_template with itself while it`
28	`also defines the required iterators etc. Strange but legal C++.`	28	`also defines the required iterators etc. Strange but legal C++.`
29		29
30	`This is the best solution I could come up with - since I really wanted`	30	`This is the best solution I could come up with - since I really wanted`
31	`to use STL to store the elements. The solution is similar to what is`	31	`to use STL to store the elements. The solution is similar to what is`
32	`used in CGAL and OpenMesh both of which provided inspiration. */`	32	`used in CGAL and OpenMesh both of which provided inspiration. */`
33		33
-		34	`/** \struct Vertex`
-		35	`*/`
34	`template<class R>`	36	`template<class R>`
35	`struct Vertex_template`	37	`struct Vertex_template`
36	`{`	38	`{`
37	`typedef typename R::VertexIter VertexIter;`	39	`typedef typename R::VertexIter VertexIter;`
38	`typedef typename R::FaceIter FaceIter;`	40	`typedef typename R::FaceIter FaceIter;`
39	`typedef typename R::HalfEdgeIter HalfEdgeIter;`	41	`typedef typename R::HalfEdgeIter HalfEdgeIter;`
40		42
41	`/// Constructor, argument is vertex position`	43	`/// Constructor, argument is vertex position`
42	`Vertex_template(const CGLA::Vec3f&);`	44	`Vertex_template(const CGLA::Vec3f&);`
43		45
44	`/// Outgoing halfedge`	46	`/// Outgoing halfedge`
45	`HalfEdgeIter he;`	47	`HalfEdgeIter he;`
46		48
47	`/// Geometric vertex position`	49	`/// Geometric vertex position`
48	`CGLA::Vec3f pos;`	50	`CGLA::Vec3f pos;`
49		51
50	`/// General purpose integer. Normally used as index or flag.`	52	`/// General purpose integer. Normally used as index or flag.`
51	`int touched;`	53	`int touched;`
52	`};`	54	`};`
53		55
54	`template<class R>`	56	`template<class R>`
55	`struct HalfEdge_template`	57	`struct HalfEdge_template`
56	`{`	58	`{`
57	`typedef typename R::VertexIter VertexIter;`	59	`typedef typename R::VertexIter VertexIter;`
58	`typedef typename R::FaceIter FaceIter;`	60	`typedef typename R::FaceIter FaceIter;`
59	`typedef typename R::HalfEdgeIter HalfEdgeIter;`	61	`typedef typename R::HalfEdgeIter HalfEdgeIter;`
60		62
61	`/// Constructor`	63	`/// Constructor`
62	`HalfEdge_template();`	64	`HalfEdge_template();`
63		65
64	`/// Vertex pointed to by this halfedge.`	66	`/// Vertex pointed to by this halfedge.`
65	`VertexIter vert;`	67	`VertexIter vert;`
66		68
67	`/// Next halfedge in face loop.`	69	`/// Next halfedge in face loop.`
68	`HalfEdgeIter next;`	70	`HalfEdgeIter next;`
69		71
70	`/// Previous halfedge in face loop.`	72	`/// Previous halfedge in face loop.`
71	`HalfEdgeIter prev;`	73	`HalfEdgeIter prev;`
72		74
73	`/// Face owning this halfedge`	75	`/// Face owning this halfedge`
74	`FaceIter face;`	76	`FaceIter face;`
75		77
76	`/// Opposite halfedge`	78	`/// Opposite halfedge`
77	`HalfEdgeIter opp;`	79	`HalfEdgeIter opp;`
78		80
79	`/// General purpose integer. Normally used as index or flag.`	81	`/// General purpose integer. Normally used as index or flag.`
80	`int touched;`	82	`int touched;`
81		83
82	`};`	84	`};`
83		85
84	`template<class R>`	86	`template<class R>`
85	`struct Face_template`	87	`struct Face_template`
86	`{`	88	`{`
87	`typedef typename R::VertexIter VertexIter;`	89	`typedef typename R::VertexIter VertexIter;`
88	`typedef typename R::FaceIter FaceIter;`	90	`typedef typename R::FaceIter FaceIter;`
89	`typedef typename R::HalfEdgeIter HalfEdgeIter;`	91	`typedef typename R::HalfEdgeIter HalfEdgeIter;`
90		92
91	`/// Constructor`	93	`/// Constructor`
92	`Face_template();`	94	`Face_template();`
93		95
94	`/// Last is just some halfedge in the face loop.`	96	`/// Last is just some halfedge in the face loop.`
95	`HalfEdgeIter last;`	97	`HalfEdgeIter last;`
96		98
97	`/// General purpose integer. Normally used as index or flag.`	99	`/// General purpose integer. Normally used as index or flag.`
98	`int touched;`	100	`int touched;`
99	`};`	101	`};`
100		102
101	`struct Iters`	103	`struct Iters`
102	`{`	104	`{`
103	`typedef Vertex_template<Iters> V;`	105	`typedef Vertex_template<Iters> V;`
104	`typedef HalfEdge_template<Iters> HE;`	106	`typedef HalfEdge_template<Iters> HE;`
105	`typedef Face_template<Iters> F;`	107	`typedef Face_template<Iters> F;`
106		108
107	`typedef std::list<V> VertexList;`	109	`typedef std::list<V> VertexList;`
108	`typedef std::list<HE> HalfEdgeList;`	110	`typedef std::list<HE> HalfEdgeList;`
109	`typedef std::list<F> FaceList;`	111	`typedef std::list<F> FaceList;`
110		112
111	`typedef VertexList::iterator VertexIter;`	113	`typedef VertexList::iterator VertexIter;`
112	`typedef HalfEdgeList::iterator HalfEdgeIter;`	114	`typedef HalfEdgeList::iterator HalfEdgeIter;`
113	`typedef FaceList::iterator FaceIter;`	115	`typedef FaceList::iterator FaceIter;`
114	`};`	116	`};`
115		117
116		118
117		119
118	`}`	120	`}`
119	`#endif`	121	`#endif`
120		122

Subversion Repositories gelsvn

(root)/branches/MPC/src/HMesh/templates.h – Rev 67 → 94