Coupure prévue mardi 3 Août au matin pour maintenance du serveur. Nous faisons au mieux pour que celle-ci soit la plus brève possible.

uniformOrientation.hpp 4.44 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
namespace CGoGN
{

namespace Algo
{

namespace Topo
{

// private function
template <typename MAP>
void reverse2MapFaceKeepPhi2(MAP& map, Dart d)
{
	unsigned int first = map.template getEmbedding<VERTEX>(d);

	Dart e=d;
	do
	{
		Dart f=map.phi1(e);
		unsigned int emb = map.template getEmbedding<VERTEX>(f);
		map.template setDartEmbedding<VERTEX>(e,emb);
		e =f;
	}while (e!=d);
	map.template setDartEmbedding<VERTEX>(map.phi_1(d),first);

	map.reverseCycle(d);

}

// private function
inline Dart findOtherInCouplesOfDarts(const std::vector<Dart>& couples, Dart d)
{
	unsigned int nb = couples.size();
	for (unsigned int i=0; i<nb; ++i)
	{
		if (couples[i] == d)
		{
			if (i%2 == 0)
				return couples[i+1];
			//else
				return couples[i-1];
		}
	}
	return NIL;
}



template <typename MAP>
void uniformOrientationCC(MAP& map, Dart faceSeed)
{
	// first bufferize boundary edges
	std::vector<Dart> boundEdges;
	TraversorE<MAP> travEdge(map);
	for (Dart d=travEdge.begin(); d!= travEdge.end(); d = travEdge.next())
	{
		if (map.isBoundaryEdge(d))
			boundEdges.push_back(d);
	}

	// store couple of boundary edges the have same embedding
	std::vector<Dart> couples;
	int nb = boundEdges.size();
	int nbm = nb-1;
	for (int i=0; i< nbm; ++i)
	{
		if (boundEdges[i] != NIL)
		{
			for (int j=i+1; j< nb; ++j)
			{
				if (boundEdges[j] != NIL)
				{
					Dart d = boundEdges[i];
					Dart d1 = map.phi1(d);
					Dart e = boundEdges[j];
					Dart e1 = map.phi1(e);

					if ((map.template getEmbedding<VERTEX>(d) == map.template getEmbedding<VERTEX>(e)) && (map.template getEmbedding<VERTEX>(d1) == map.template getEmbedding<VERTEX>(e1)))
					{
						couples.push_back(d);
						couples.push_back(e);
						boundEdges[j] = NIL; // not using the dart again
						j=nb; // out of the loop
					}
				}
			}
		}
	}


	// vector of front propagation for good orientation
	std::vector<Dart> propag;
	boundEdges.clear();
	propag.swap(boundEdges);// reused memory of boundEdges


	// vector of front propagation for wrong orientation
	std::vector<Dart> propag_inv;

	//vector of faces to invert
	std::vector<Dart> face2invert;

	// optimize memory reserve
	propag_inv.reserve(1024);
	face2invert.reserve(1024);

Pierre Kraemer's avatar
Pierre Kraemer committed
107
	DartMarker<MAP> cmf(map);
108

Sylvain Thery's avatar
Sylvain Thery committed
109
	cmf.template markOrbit<FACE>(faceSeed);
110
111
112
113
114
115
116
117
118
119
120
121
122
	propag.push_back(faceSeed);

	while (!propag.empty() || !propag_inv.empty())
	{
		if (!propag.empty())
		{
			Dart f = propag.back();
			propag.pop_back();

			Dart d = f;
			do
			{
				Dart e = map.phi2(d);
Sylvain Thery's avatar
Sylvain Thery committed
123
				if (map.template isBoundaryMarked<2>(e))
124
125
126
127
128
129
130
131
				{
					e = findOtherInCouplesOfDarts(couples,d);
					if (e!=NIL)
					{
						if (!cmf.isMarked(e))
						{
							propag_inv.push_back(e);
							face2invert.push_back(e);
Sylvain Thery's avatar
Sylvain Thery committed
132
							cmf.template markOrbit<FACE>(e);
133
134
135
136
137
138
139
140
141
142
						}
						cmf.mark(map.phi2(e));// use cmf also to mark boudary cycle to invert
					}

				}
				else
				{
					if (!cmf.isMarked(e))
					{
						propag.push_back(e);
Sylvain Thery's avatar
Sylvain Thery committed
143
						cmf.template markOrbit<FACE>(e);
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
					}
				}
				d= map.phi1(d);

			} while (d!=f);
		}

		if (!propag_inv.empty())
		{
			Dart f = propag_inv.back();
			propag_inv.pop_back();

			Dart d = f;
			do
			{
				Dart e = map.phi2(d);
Sylvain Thery's avatar
Sylvain Thery committed
160
				if (map.template isBoundaryMarked<2>(e))
161
162
163
164
165
166
167
				{
					e = findOtherInCouplesOfDarts(couples,d);
					if (e!=NIL)
					{
						if (!cmf.isMarked(e))
						{
							propag.push_back(e);
Sylvain Thery's avatar
Sylvain Thery committed
168
							cmf.template markOrbit<FACE>(e);
169
170
171
172
173
174
175
176
177
178
						}
						cmf.mark(map.phi2(d));// use cmf also to mark boudary cycle to invert
					}
				}
				else
				{
					if (!cmf.isMarked(e))
					{
						propag_inv.push_back(e);
						face2invert.push_back(e);
Sylvain Thery's avatar
Sylvain Thery committed
179
						cmf.template markOrbit<FACE>(e);
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
					}
				}
				d= map.phi1(d); // traverse all edges of face
			} while (d!=f);
		}
	}

	// reverse all faces of the wrong orientation
	for (std::vector<Dart>::iterator id=face2invert.begin(); id!=face2invert.end(); ++id)
		reverse2MapFaceKeepPhi2<MAP>(map,*id);

	// reverse the boundary cycles that bound reverse faces
	for (std::vector<Dart>::iterator id=couples.begin(); id!=couples.end(); ++id)
	{
		Dart e =  map.phi2(*id);
		if (cmf.isMarked(e))	// check cmf for wrong orientation
		{
			reverse2MapFaceKeepPhi2<MAP>(map,e);
Sylvain Thery's avatar
Sylvain Thery committed
198
			cmf.template unmarkOrbit<FACE>(e);
199
200
201
202
203
204
205
206
		}
	}

	// sew the faces that correspond to couples of boundary edges
	for (std::vector<Dart>::iterator id=couples.begin(); id!=couples.end(); ++id)// second ++ inside !
	{
		Dart d = *id++;
		Dart e = *id;
Sylvain Thery's avatar
Sylvain Thery committed
207
208
		if (cmf.isMarked(d) || cmf.isMarked(e))
			map.sewFaces(d,e);
209
210
211
212
213
214
215
216
217
218
	}

}


} // namespace Topo

} // namespace Algo

} // namespace CGoGN