Subversion Repositories gelsvn

Rev

Rev 39 | Rev 89 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 39 Rev 62
Line 5... Line 5...
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 
	template<class R>
 34 
		template<class R>
35 
		struct Vertex_template
 35 
		struct Vertex_template
36 
		{
 36 
		{
37 
			typedef typename R::VertexIter VertexIter;
 37 
				typedef typename R::VertexIter VertexIter;
38 
			typedef typename R::FaceIter FaceIter;
 38 
				typedef typename R::FaceIter FaceIter;
39 
			typedef typename R::HalfEdgeIter HalfEdgeIter;
 39 
				typedef typename R::HalfEdgeIter HalfEdgeIter;
40 
 
 40 
 
41 
			HalfEdgeIter he;
 41 
				/// Constructor, argument is vertex position
42 
			CGLA::Vec3f pos;
 42 
				Vertex_template(const CGLA::Vec3f&);
43 
 
 43 
 
44 
			Vertex_template(const CGLA::Vec3f&);
 44 
				/// Outgoing halfedge
- 
 
 45 
				HalfEdgeIter he;
45 
 
 46 
 
46 
			bool is_boundary();
 47 
				/// Geometric vertex position
47 
			void check_boundary_consistency();
 48 
				CGLA::Vec3f pos;
48 
 
 49 
 
49 
			const CGLA::Vec3f& get_pos() const {return pos;}
 50 
				/// General purpose integer. Normally used as index or flag.
50 
			void set_pos(const CGLA::Vec3f& _pos) {pos=_pos;}
 - 
 
51 
 
 - 
 
52 
			int touched;
 51 
				int touched;
53 
		};
 52 
		};
54 
 
 53 
 
55 
	template<class R>
 54 
		template<class R>
56 
		struct HalfEdge_template
 55 
		struct HalfEdge_template
57 
		{
 56 
		{
58 
			typedef typename R::VertexIter VertexIter;
 57 
				typedef typename R::VertexIter VertexIter;
59 
			typedef typename R::FaceIter FaceIter;
 58 
				typedef typename R::FaceIter FaceIter;
60 
			typedef typename R::HalfEdgeIter HalfEdgeIter;
 59 
				typedef typename R::HalfEdgeIter HalfEdgeIter;
- 
 
 60 
 
- 
 
 61 
				/// Constructor
- 
 
 62 
				HalfEdge_template();
- 
 
 63 
 
- 
 
 64 
				/// Vertex pointed to by this halfedge.
- 
 
 65 
				VertexIter   vert;
- 
 
 66 
 
- 
 
 67 
				/// Next halfedge in face loop.
- 
 
 68 
				HalfEdgeIter next;
61 
 
 69 
 
62 
			VertexIter   vert;
 - 
 
63 
			HalfEdgeIter next;
 70 
				/// Previous halfedge in face loop.
64 
			HalfEdgeIter prev;
 71 
				HalfEdgeIter prev;
65 
 
 72 
 
66 
			FaceIter     face;
 73 
				/// Face owning this halfedge
67 
			HalfEdgeIter opp;
 74 
				FaceIter     face;
68 
 
 75 
 
- 
 
 76 
				/// Opposite halfedge
69 
			bool is_boundary();
 77 
				HalfEdgeIter opp;
- 
 
 78 
 
- 
 
 79 
				/// General purpose integer. Normally used as index or flag.
70 
			int touched;
 80 
				int touched;
71 
 
 81 
 
72 
			HalfEdge_template();
 - 
 
73 
		};
 82 
		};
74 
 
 83 
 
75 
	template<class R>
 84 
		template<class R>
76 
		struct Face_template
 85 
		struct Face_template
77 
		{
 86 
		{
78 
			typedef typename R::VertexIter VertexIter;
 87 
				typedef typename R::VertexIter VertexIter;
79 
			typedef typename R::FaceIter FaceIter;
 88 
				typedef typename R::FaceIter FaceIter;
80 
			typedef typename R::HalfEdgeIter HalfEdgeIter;
 89 
				typedef typename R::HalfEdgeIter HalfEdgeIter;
- 
 
 90 
 
- 
 
 91 
				/// Constructor
- 
 
 92 
				Face_template();
81 
 
 93 
 
- 
 
 94 
				/// Last is just some halfedge in the face loop.
82 
			HalfEdgeIter last;
 95 
				HalfEdgeIter last;
83 
			int touched;
 - 
 
84 
 
 96 
 
- 
 
 97 
				/// General purpose integer. Normally used as index or flag.
85 
			Face_template();
 98 
				int touched;
86 
		};
 99 
		};
87 
 
 100 
 
88 
	struct Iters
 101 
		struct Iters
89 
	{
 102 
		{
90 
		typedef Vertex_template<Iters> V;
 103 
				typedef Vertex_template<Iters> V;
91 
		typedef HalfEdge_template<Iters> HE;
 104 
				typedef HalfEdge_template<Iters> HE;
92 
		typedef Face_template<Iters> F;
 105 
				typedef Face_template<Iters> F;
93
106
94 
		typedef std::list<V> VertexList;
 107 
				typedef std::list<V> VertexList;
95 
		typedef std::list<HE> HalfEdgeList;
 108 
				typedef std::list<HE> HalfEdgeList;
96 
		typedef std::list<F> FaceList;
 109 
				typedef std::list<F> FaceList;
97 
 
 110 
 
98 
		typedef VertexList::iterator VertexIter;
 111 
				typedef VertexList::iterator VertexIter;
99 
		typedef HalfEdgeList::iterator HalfEdgeIter;
 112 
				typedef HalfEdgeList::iterator HalfEdgeIter;
100 
		typedef FaceList::iterator FaceIter;
 113 
				typedef FaceList::iterator FaceIter;
101 
	};
 114 
		};
102 
 
 115 
 
103 
 
 116 
 
104 
 
 117 
 
105 
}
 118 
}
106 
#endif
 119 
#endif