WebSVN – gelsvn – Diff – /branches/vc2005beta-branch/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. */
 
 
		/** Type used for the touch variables of halfedges, vertices, and faces.
				The touch variables are used to contain various data such as counters,
				indices, flags. In some cases it is useful to touch with the value
				of a pointer cast to an integer. However, this means that the 
				integer size must be the same as the pointer size. Using "intptr_t"
				ensures this. */
		typedef intptr_t TouchType;
 
		/** \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.
				TouchType 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.
				TouchType 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.
				TouchType 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;
		};
 
 
	typedef Face_template<Iters> Face;
	typedef HalfEdge_template<Iters> HalfEdge;
	typedef Vertex_template<Iters> Vertex;
 
	typedef Iters::FaceList FaceList;
	typedef Iters::HalfEdgeList HalfEdgeList;
	typedef Iters::VertexList VertexList;
 
	typedef Iters::FaceIter FaceIter;
	typedef Iters::HalfEdgeIter HalfEdgeIter;
	typedef Iters::VertexIter VertexIter;
 
 
 
 
 
	inline FaceIter get_null_face_iter()
			{
					static FaceList l;
					return l.end();
			}
 
	inline VertexIter get_null_vertex_iter()
			{
					static VertexList l;
					return l.end();
			}
 
 
	inline HalfEdgeIter get_null_halfedge_iter()
			{
					static HalfEdgeList l;
					return l.end();
			}
 
 
#define NULL_FACE_ITER HMesh::get_null_face_iter() 
#define NULL_HALFEDGE_ITER HMesh::get_null_halfedge_iter() 
#define NULL_VERTEX_ITER HMesh::get_null_vertex_iter()
 
 
}
#endif
 

Subversion Repositories gelsvn

(root)/branches/vc2005beta-branch/src/HMesh/templates.h – Rev 122 → 128

Rev 122		Rev 128
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		34
35	`/** Type used for the touch variables of halfedges, vertices, and faces.`	35	`/** Type used for the touch variables of halfedges, vertices, and faces.`
36	`The touch variables are used to contain various data such as counters,`	36	`The touch variables are used to contain various data such as counters,`
37	`indices, flags. In some cases it is useful to touch with the value`	37	`indices, flags. In some cases it is useful to touch with the value`
38	`of a pointer cast to an integer. However, this means that the`	38	`of a pointer cast to an integer. However, this means that the`
39	`integer size must be the same as the pointer size. Using "intptr_t"`	39	`integer size must be the same as the pointer size. Using "intptr_t"`
40	`ensures this. */`	40	`ensures this. */`
41	`typedef intptr_t TouchType;`	41	`typedef intptr_t TouchType;`
42		42
43	`/** \struct Vertex`	43	`/** \struct Vertex`
44	`*/`	44	`*/`
45	`template<class R>`	45	`template<class R>`
46	`struct Vertex_template`	46	`struct Vertex_template`
47	`{`	47	`{`
48	`typedef typename R::VertexIter VertexIter;`	48	`typedef typename R::VertexIter VertexIter;`
49	`typedef typename R::FaceIter FaceIter;`	49	`typedef typename R::FaceIter FaceIter;`
50	`typedef typename R::HalfEdgeIter HalfEdgeIter;`	50	`typedef typename R::HalfEdgeIter HalfEdgeIter;`
51		51
52	`/// Constructor, argument is vertex position`	52	`/// Constructor, argument is vertex position`
53	`Vertex_template(const CGLA::Vec3f&);`	53	`Vertex_template(const CGLA::Vec3f&);`
54		54
55	`/// Outgoing halfedge`	55	`/// Outgoing halfedge`
56	`HalfEdgeIter he;`	56	`HalfEdgeIter he;`
57		57
58	`/// Geometric vertex position`	58	`/// Geometric vertex position`
59	`CGLA::Vec3f pos;`	59	`CGLA::Vec3f pos;`
60		60
61	`/// General purpose integer. Normally used as index or flag.`	61	`/// General purpose integer. Normally used as index or flag.`
62	`TouchType touched;`	62	`TouchType touched;`
63	`};`	63	`};`
64		64
65	`template<class R>`	65	`template<class R>`
66	`struct HalfEdge_template`	66	`struct HalfEdge_template`
67	`{`	67	`{`
68	`typedef typename R::VertexIter VertexIter;`	68	`typedef typename R::VertexIter VertexIter;`
69	`typedef typename R::FaceIter FaceIter;`	69	`typedef typename R::FaceIter FaceIter;`
70	`typedef typename R::HalfEdgeIter HalfEdgeIter;`	70	`typedef typename R::HalfEdgeIter HalfEdgeIter;`
71		71
72	`/// Constructor`	72	`/// Constructor`
73	`HalfEdge_template();`	73	`HalfEdge_template();`
74		74
75	`/// Vertex pointed to by this halfedge.`	75	`/// Vertex pointed to by this halfedge.`
76	`VertexIter vert;`	76	`VertexIter vert;`
77		77
78	`/// Next halfedge in face loop.`	78	`/// Next halfedge in face loop.`
79	`HalfEdgeIter next;`	79	`HalfEdgeIter next;`
80		80
81	`/// Previous halfedge in face loop.`	81	`/// Previous halfedge in face loop.`
82	`HalfEdgeIter prev;`	82	`HalfEdgeIter prev;`
83		83
84	`/// Face owning this halfedge`	84	`/// Face owning this halfedge`
85	`FaceIter face;`	85	`FaceIter face;`
86		86
87	`/// Opposite halfedge`	87	`/// Opposite halfedge`
88	`HalfEdgeIter opp;`	88	`HalfEdgeIter opp;`
89		89
90	`/// General purpose integer. Normally used as index or flag.`	90	`/// General purpose integer. Normally used as index or flag.`
91	`TouchType touched;`	91	`TouchType touched;`
92		92
93	`};`	93	`};`
94		94
95	`template<class R>`	95	`template<class R>`
96	`struct Face_template`	96	`struct Face_template`
97	`{`	97	`{`
98	`typedef typename R::VertexIter VertexIter;`	98	`typedef typename R::VertexIter VertexIter;`
99	`typedef typename R::FaceIter FaceIter;`	99	`typedef typename R::FaceIter FaceIter;`
100	`typedef typename R::HalfEdgeIter HalfEdgeIter;`	100	`typedef typename R::HalfEdgeIter HalfEdgeIter;`
101		101
102	`/// Constructor`	102	`/// Constructor`
103	`Face_template();`	103	`Face_template();`
104		104
105	`/// Last is just some halfedge in the face loop.`	105	`/// Last is just some halfedge in the face loop.`
106	`HalfEdgeIter last;`	106	`HalfEdgeIter last;`
107		107
108	`/// General purpose integer. Normally used as index or flag.`	108	`/// General purpose integer. Normally used as index or flag.`
109	`TouchType touched;`	109	`TouchType touched;`
110	`};`	110	`};`
111		111
112	`struct Iters`	112	`struct Iters`
113	`{`	113	`{`
114	`typedef Vertex_template<Iters> V;`	114	`typedef Vertex_template<Iters> V;`
115	`typedef HalfEdge_template<Iters> HE;`	115	`typedef HalfEdge_template<Iters> HE;`
116	`typedef Face_template<Iters> F;`	116	`typedef Face_template<Iters> F;`
117		117
118	`typedef std::list<V> VertexList;`	118	`typedef std::list<V> VertexList;`
119	`typedef std::list<HE> HalfEdgeList;`	119	`typedef std::list<HE> HalfEdgeList;`
120	`typedef std::list<F> FaceList;`	120	`typedef std::list<F> FaceList;`
121		121
122	`typedef VertexList::iterator VertexIter;`	122	`typedef VertexList::iterator VertexIter;`
123	`typedef HalfEdgeList::iterator HalfEdgeIter;`	123	`typedef HalfEdgeList::iterator HalfEdgeIter;`
124	`typedef FaceList::iterator FaceIter;`	124	`typedef FaceList::iterator FaceIter;`
125	`};`	125	`};`
126		126
127		127
128	`typedef Face_template<Iters> Face;`	128	`typedef Face_template<Iters> Face;`
129	`typedef HalfEdge_template<Iters> HalfEdge;`	129	`typedef HalfEdge_template<Iters> HalfEdge;`
130	`typedef Vertex_template<Iters> Vertex;`	130	`typedef Vertex_template<Iters> Vertex;`
131		131
132	`typedef Iters::FaceList FaceList;`	132	`typedef Iters::FaceList FaceList;`
133	`typedef Iters::HalfEdgeList HalfEdgeList;`	133	`typedef Iters::HalfEdgeList HalfEdgeList;`
134	`typedef Iters::VertexList VertexList;`	134	`typedef Iters::VertexList VertexList;`
135		135
136	`typedef Iters::FaceIter FaceIter;`	136	`typedef Iters::FaceIter FaceIter;`
137	`typedef Iters::HalfEdgeIter HalfEdgeIter;`	137	`typedef Iters::HalfEdgeIter HalfEdgeIter;`
138	`typedef Iters::VertexIter VertexIter;`	138	`typedef Iters::VertexIter VertexIter;`
139		139
140	`FaceIter get_null_face_iter();`	-
141	`HalfEdgeIter get_null_halfedge_iter();`	-
142	`VertexIter get_null_vertex_iter();`	-
143		-
144	`inline FaceIter get_null_face_iter()`	140	`inline FaceIter get_null_face_iter()`
145	`{`	141	`{`
146	`static FaceList l;`	142	`static FaceList l;`
147	`return l.end();`	143	`return l.end();`
148	`}`	144	`}`
149		145
150	`inline VertexIter get_null_vertex_iter()`	146	`inline VertexIter get_null_vertex_iter()`
151	`{`	147	`{`
152	`static VertexList l;`	148	`static VertexList l;`
153	`return l.end();`	149	`return l.end();`
154	`}`	150	`}`
155		151
156		152
157	`inline HalfEdgeIter get_null_halfedge_iter()`	153	`inline HalfEdgeIter get_null_halfedge_iter()`
158	`{`	154	`{`
159	`static HalfEdgeList l;`	155	`static HalfEdgeList l;`
160	`return l.end();`	156	`return l.end();`
161	`}`	157	`}`
162		158
163		159
164	`#define NULL_FACE_ITER HMesh::get_null_face_iter()`	160	`#define NULL_FACE_ITER HMesh::get_null_face_iter()`
165	`#define NULL_HALFEDGE_ITER HMesh::get_null_halfedge_iter()`	161	`#define NULL_HALFEDGE_ITER HMesh::get_null_halfedge_iter()`
166	`#define NULL_VERTEX_ITER HMesh::get_null_vertex_iter()`	162	`#define NULL_VERTEX_ITER HMesh::get_null_vertex_iter()`
167		163
168		164
169	`}`	165	`}`
170	`#endif`	166	`#endif`
171		167