uniformOrientation.hpp 4.33 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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217

	cmf.markOrbit<FACE>(faceSeed);
	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);
				if (map.isBoundaryMarked2(e))
				{
					e = findOtherInCouplesOfDarts(couples,d);
					if (e!=NIL)
					{
						if (!cmf.isMarked(e))
						{
							propag_inv.push_back(e);
							face2invert.push_back(e);
							cmf.markOrbit<FACE>(e);
						}
						cmf.mark(map.phi2(e));// use cmf also to mark boudary cycle to invert
					}

				}
				else
				{
					if (!cmf.isMarked(e))
					{
						propag.push_back(e);
						cmf.markOrbit<FACE>(e);
					}
				}
				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);
				if (map.isBoundaryMarked2(e))
				{
					e = findOtherInCouplesOfDarts(couples,d);
					if (e!=NIL)
					{
						if (!cmf.isMarked(e))
						{
							propag.push_back(e);
							cmf.markOrbit<FACE>(e);
						}
						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);
						cmf.markOrbit<FACE>(e);
					}
				}
				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);
			cmf.unmarkOrbit<FACE>(e);
		}
	}

	// 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;
		map.sewFaces(d,e);
	}

}


} // namespace Topo

} // namespace Algo

} // namespace CGoGN