modify.cpp 54.9 KB
Newer Older
Kirill Terekhov's avatar
Kirill Terekhov committed
1
#include "inmost.h"
Kirill Terekhov's avatar
Kirill Terekhov committed
2
#include "incident_matrix.hpp"
Kirill Terekhov's avatar
Kirill Terekhov committed
3
4
5
6
7
8
9
10
#if defined(USE_MESH)

//TODO:
// incident_matrix class should measure for minimal volume,
// possibly check and update from projects/OctreeCutcell/octgrid.cpp

namespace INMOST
{
Kirill Terekhov's avatar
Kirill Terekhov committed
11

Kirill Terekhov's avatar
Kirill Terekhov committed
12
	
Kirill Terekhov's avatar
Kirill Terekhov committed
13
	void Face::SwapCells() const
Kirill Terekhov's avatar
Kirill Terekhov committed
14
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
15
16
17
		Mesh * m = GetMeshLink();
		MarkerType hm = m->HideMarker();
		adj_type & hc = m->HighConn(GetHandle());
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
18
		if( m->Count(hc.data(),static_cast<enumerator>(hc.size()),hm) == 2 )
Kirill Terekhov's avatar
Kirill Terekhov committed
19
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
20
21
22
			enumerator k1 = ENUMUNDEF, k2;
			k1 = m->getNext(hc.data(),static_cast<enumerator>(hc.size()),k1,hm);
			k2 = m->getNext(hc.data(),static_cast<enumerator>(hc.size()),k1,hm);
Kirill Terekhov's avatar
Kirill Terekhov committed
23
24
25
			HandleType temp = hc[k1];
			hc[k1] = hc[k2];
			hc[k2] = temp;
Kirill Terekhov's avatar
Kirill Terekhov committed
26
			//FixNormalOrientation(); //maybe should change orientation?
Kirill Terekhov's avatar
Kirill Terekhov committed
27
28
		}
	}
29
30
31
32
33

	void Edge::SwapEnds()
	{
		Mesh * m = GetMeshLink();
		MarkerType hm = m->HideMarker();
34
35
		adj_type & lc = m->LowConn(GetHandle());
		if( m->Count(lc.data(),static_cast<enumerator>(lc.size()),hm) == 2 )
36
37
		{
			enumerator k1 = ENUMUNDEF, k2;
38
39
40
41
42
43
44
45
			k1 = m->getNext(lc.data(),static_cast<enumerator>(lc.size()),k1,hm);
			k2 = m->getNext(lc.data(),static_cast<enumerator>(lc.size()),k1,hm);
			//std::cout << "k " << k1 << " " << k2 << std::endl;
			//std::cout << "was " << lc[k1] << " " << lc[k2] << std::endl;
			HandleType temp = lc[k1];
			lc[k1] = lc[k2];
			lc[k2] = temp;
			//std::cout << "now " << lc[k1] << " " << lc[k2] << std::endl;
46
47
		}
	}
Kirill Terekhov's avatar
Kirill Terekhov committed
48
	
Kirill Terekhov's avatar
Kirill Terekhov committed
49
	void Element::Disconnect(bool del_upper) const
Kirill Terekhov's avatar
Kirill Terekhov committed
50
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
51
		
Kirill Terekhov's avatar
Kirill Terekhov committed
52
53
		dynarray<adj_type::size_type,64> del;
		Mesh * m = GetMeshLink();
Kirill Terekhov's avatar
Kirill Terekhov committed
54
55
56
57
		//BEGIN NEW CODE - CHECK
		//Reorder face edges, so that they always apear in right direction
		if( GetElementType() == CELL ) //This is a cell
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
58
59
			getAsCell()->SwapBackCell();
			/*
Kirill Terekhov's avatar
Kirill Terekhov committed
60
			MarkerType hm = m->HideMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
61
			adj_type & lc = m->LowConn(GetHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
62
			for( adj_type::size_type it = 0; it < lc.size(); it++) //if( !m->GetMarker(lc[it],hm) ) //iterator over unhidden faces
Kirill Terekhov's avatar
Kirill Terekhov committed
63
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
64
				adj_type & hc = m->HighConn(lc[it]);
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
65
				if( !hc.empty() && m->Count(hc.data(),static_cast<enumerator>(hc.size()),hm) == 2 ) //there are two cells connected to face
Kirill Terekhov's avatar
Kirill Terekhov committed
66
				{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
67
68
					enumerator k1 = ENUMUNDEF, k2;
					k1 = m->getNext(hc.data(),static_cast<enumerator>(hc.size()),k1,hm);
Kirill Terekhov's avatar
Kirill Terekhov committed
69
					if( hc[k1] == GetHandle() ) //the first cell is current
Kirill Terekhov's avatar
Kirill Terekhov committed
70
					{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
71
						k2 = m->getNext(hc.data(),static_cast<enumerator>(hc.size()),k1,hm);
Kirill Terekhov's avatar
Kirill Terekhov committed
72
73
74
75
						hc[k1] = hc[k2];
						//hc[k2] = GetHandle(); //cannot use the cell because virtualization table is already destroyed and FixNormalOrientation will do bad things
						hc.resize(1); //just remove element, we will do this anyway later
						Face(m,lc[it])->FixNormalOrientation(); //restore orientation
Kirill Terekhov's avatar
Kirill Terekhov committed
76
77
78
					}
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
79
			*/
Kirill Terekhov's avatar
Kirill Terekhov committed
80
81
		}
		//END NEW CODE - CHECK
Kirill Terekhov's avatar
Kirill Terekhov committed
82
		adj_type & hc = m->HighConn(GetHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
83
		adj_type::size_type i = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
84
		for( adj_type::size_type it = 0; it < hc.size(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
85
86
		{
			int flag = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
87
88
89
			adj_type & ilc = m->LowConn(hc[it]);
			adj_type::iterator jt = ilc.begin();
			while (jt != ilc.end())
Kirill Terekhov's avatar
Kirill Terekhov committed
90
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
91
				if(*jt == GetHandle())
Kirill Terekhov's avatar
Kirill Terekhov committed
92
93
				{
					flag = 1;
Kirill Terekhov's avatar
Kirill Terekhov committed
94
					jt = ilc.erase(jt);
Kirill Terekhov's avatar
Kirill Terekhov committed
95
96
97
98
99
100
101
102
103
104
				}
				else ++jt;
			}
			if( flag ) del.push_back(i);
			i++;
		}
		if( del_upper )
		{
			if( GetElementType() < CELL ) 
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
105
106
107
				if( Hidden() ) 
				{
					for(dynarray<adj_type::size_type,64>::iterator it = del.begin(); it != del.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
108
						if( m->GetMarker(hc[*it],m->HideMarker()) ) m->Delete(hc[*it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
109
110
111
112
				}
				else 
				{
					for(dynarray<adj_type::size_type,64>::iterator it = del.begin(); it != del.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
113
						m->Delete(hc[*it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
114
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
115
116
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
117
118
119
		hc.clear();
		adj_type & lc = m->LowConn(GetHandle());
		for(adj_type::size_type it = 0; it < lc.size(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
120
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
121
122
123
			adj_type & ihc = m->HighConn(lc[it]);
			adj_type::iterator jt = ihc.begin();
			while (jt != ihc.end())
Kirill Terekhov's avatar
Kirill Terekhov committed
124
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
125
				if(*jt == GetHandle()) jt = ihc.erase(jt);
Kirill Terekhov's avatar
Kirill Terekhov committed
126
127
128
				else ++jt;
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
129
		lc.clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
130
131
	}
	
Kirill Terekhov's avatar
Kirill Terekhov committed
132
	Cell Cell::UniteCells(ElementArray<Cell> & unite, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
133
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
134
135
136
137
138
		Mesh * m = unite.GetMeshLink();
		if( unite.empty() ) return Cell(m,InvalidHandle());
		tiny_map<HandleType, int, 64> face_visit; // we check all edges of faces, inner edges are visited several times, outer - once
		ElementArray<Face> faces(m); 
		dynarray<HandleType,64> inner_faces;
Kirill Terekhov's avatar
Kirill Terekhov committed
139
		bool doexit = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
140
		MarkerType hm = m->HideMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
141
		for(ElementArray<Cell>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
142
143
		{
			if( unite[j]->GetMarker(del_protect) ) doexit = true; 
Kirill Terekhov's avatar
Kirill Terekhov committed
144
145
146
			adj_type const & lc = m->LowConn(unite.at(j));
			for(adj_type::size_type it = 0; it < lc.size(); it++) if( !m->GetMarker(lc[it],hm) )
				face_visit[lc[it]]++;
Kirill Terekhov's avatar
Kirill Terekhov committed
147
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
148
		if( doexit ) return Cell(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
149
		MarkerType visited = m->CreateMarker(), rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
150
151
152
153
		dynarray<HandleType,64> edges;
		dynarray<HandleType,64> nodes;
		for(tiny_map<HandleType,int,64>::iterator it = face_visit.begin(); it != face_visit.end(); it++)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
154
155
156
157
			if( it->second == 1 )
				faces.push_back(it->first);
			else
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
158
159
160
161
162
				if( m->GetMarker(it->first,del_protect) ) doexit = true;
				m->SetMarker(it->first,rem);
				adj_type const & lc = m->LowConn(it->first);
				for(adj_type::size_type jt = 0; jt < lc.size(); jt++) if( !m->GetMarker(lc[jt],hm) )
					if( !m->GetMarker(lc[jt],visited) )
Kirill Terekhov's avatar
Kirill Terekhov committed
163
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
164
165
						m->SetMarker(lc[jt],visited);
						edges.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
166
167
168
					}
				inner_faces.push_back(it->first);
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
169
170
		}
		for(dynarray<HandleType,64>::size_type i = 0; i < edges.size(); i++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
171
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
172
173
174
			m->RemMarker(edges[i],visited);
			adj_type const & lc = m->LowConn(edges[i]);
			for(adj_type::size_type jt = 0; jt < lc.size(); jt++) if( !m->GetMarker(lc[jt],hm) )
Kirill Terekhov's avatar
Kirill Terekhov committed
175
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
176
				if( !m->GetMarker(lc[jt],visited) )
Kirill Terekhov's avatar
Kirill Terekhov committed
177
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
178
179
					m->SetMarker(lc[jt],visited);
					nodes.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
180
181
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
182
183
184
185
186
187
188
189
190
			int nonzero = 0;
			adj_type const & hc = m->HighConn(edges[i]);
			for(adj_type::size_type jt = 0; jt < hc.size(); jt++) if( !m->GetMarker(hc[jt],hm) )//iterate over faces
				if( !m->GetMarker(hc[jt],rem) ) nonzero++; // check if it is not deleted
			if( nonzero == 0 ) //all faces should be deleted, edge to remove
			{
				m->SetMarker(edges[i],rem);
				if( m->GetMarker(edges[i],del_protect) ) doexit = true;
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
191
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
192
		for(dynarray<HandleType,64>::size_type i = 0; i < nodes.size(); i++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
193
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
194
			m->RemMarker(nodes[i],visited);
Kirill Terekhov's avatar
Kirill Terekhov committed
195
			
Kirill Terekhov's avatar
Kirill Terekhov committed
196
			if( m->GetMarker(nodes[i],del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
197
198
			{
				int nonzero = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
199
200
201
				adj_type const & hc = m->HighConn(nodes[i]);
				for(adj_type::size_type jt = 0; jt < hc.size(); jt++) if( !m->GetMarker(hc[jt],hm) )
					if( !m->GetMarker(hc[jt],rem) ) nonzero++;
Kirill Terekhov's avatar
Kirill Terekhov committed
202
203
204
205
206
207
				if( nonzero == 0 )
					doexit = true;
				
			}
		}
		m->ReleaseMarker(visited);
Kirill Terekhov's avatar
Kirill Terekhov committed
208
209
210
211
		for(dynarray<HandleType,64>::size_type it = 0; it < inner_faces.size(); it++)
			m->RemMarker(inner_faces[it],rem);
		for(dynarray<HandleType,64>::size_type i = 0; i < edges.size(); i++)  
			m->RemMarker(edges[i],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
212
		m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
213
		if( doexit ) return Cell(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
214
		//delete cells
Kirill Terekhov's avatar
Kirill Terekhov committed
215
		for(ElementArray<Cell>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
216
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
217
218
219
			if( m->GetMarker(unite.at(j),del_protect) )
				std::cout << __FUNCTION__ << " deleted protected cells, united " << unite.size() << " cells " << std::endl;
			m->Delete(unite.at(j));
Kirill Terekhov's avatar
Kirill Terekhov committed
220
221
		}
		//delete inner faces
Kirill Terekhov's avatar
Kirill Terekhov committed
222
		for(dynarray<HandleType,64>::size_type j = 0; j < inner_faces.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
223
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
224
225
226
			if( m->GetMarker(inner_faces[j],del_protect) )
				std::cout << __FUNCTION__ << " deleted protected faces, united " << unite.size() << " cells " << std::endl;
			m->Delete(inner_faces[j]);
Kirill Terekhov's avatar
Kirill Terekhov committed
227
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
228
229
230
231
		for(dynarray<HandleType,64>::size_type j = 0; j < edges.size(); j++) //delete unused edges
		{
			adj_type const & hc = m->HighConn(edges[j]);
			if( hc.empty() || m->Count(hc.data(),static_cast<integer>(hc.size()),hm) == 0 ) //there are no faces that use this edge
Kirill Terekhov's avatar
Kirill Terekhov committed
232
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
233
234
235
				if( m->GetMarker(edges[j],del_protect) )
					std::cout << __FUNCTION__ << " deleted protected edge, united " << unite.size() << " cells " << std::endl;
				m->Delete(edges[j]);
Kirill Terekhov's avatar
Kirill Terekhov committed
236
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
237
238
239
240
241
242
		}
		for(dynarray<HandleType,64>::size_type j = 0; j < nodes.size(); j++) //delete unused nodes
		{

			adj_type const & hc = m->HighConn(nodes[j]);
			if( hc.empty() || m->Count(hc.data(),static_cast<integer>(hc.size()),hm) == 0 ) //there are no edges that use this edge
Kirill Terekhov's avatar
Kirill Terekhov committed
243
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
244
245
246
247
248
				// there must be no cells that use this node
				assert( m->LowConn(nodes[j]).empty() || m->Count(m->LowConn(nodes[j]).data(),static_cast<integer>(m->LowConn(nodes[j]).size()),hm) == 0 );
				if( m->GetMarker(nodes[j],del_protect) )
					std::cout << __FUNCTION__ << " deleted protected node, united " << unite.size() << " cells " << std::endl;
				m->Delete(nodes[j]);
Kirill Terekhov's avatar
Kirill Terekhov committed
249
250
251
252
				//disconnect node from cell
				//we don't need this algorithm, because all dependent cells should be deleted
				//if( !nodes[j]->Hide() )
				//{					
Kirill Terekhov's avatar
Kirill Terekhov committed
253
254
					//adj_iterator it = nodes[j]->LowConn().begin();
					//while(it != nodes[j]->LowConn().end()) if( !(*it)->GetMarker(hm) ) //iterate through cells of the node
Kirill Terekhov's avatar
Kirill Terekhov committed
255
					//{
Kirill Terekhov's avatar
Kirill Terekhov committed
256
257
					//	adj_iterator jt =(*it)->HighConn().begin();
					//	while(jt != (*it)->HighConn().end() ) if( !(*jt)->GetMarker(hm) ) // iterate through nodes of the cell
Kirill Terekhov's avatar
Kirill Terekhov committed
258
259
					//	{
					//		if( *jt == nodes[j] )
Kirill Terekhov's avatar
Kirill Terekhov committed
260
					//			jt = (*it)->HighConn().erase(jt); //erase link to node
Kirill Terekhov's avatar
Kirill Terekhov committed
261
262
263
264
265
266
267
268
					//		else ++jt;
					//	}
					//  ++it;
					//}
					//nodes[j]->Disconnect();
					//nodes[j]->Delete();
				//}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
269
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
270
		//reconstruct cell by outer faces
Kirill Terekhov's avatar
Kirill Terekhov committed
271
		return m->CreateCell(faces).first;
Kirill Terekhov's avatar
Kirill Terekhov committed
272
273
274
	}
	
	
Kirill Terekhov's avatar
Kirill Terekhov committed
275
	bool Cell::TestUniteCells(const ElementArray<Cell> & unite, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
276
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
277
278
279
		if( unite.empty() ) return false;
		Mesh * m = unite.GetMeshLink();
		tiny_map<HandleType,int,64> face_visit; // we check all edges of faces, inner edges are visited several times, outer - once
Kirill Terekhov's avatar
Kirill Terekhov committed
280
		bool doexit = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
281
282
		MarkerType hm = m->HideMarker();			
		for(ElementArray<Cell>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
283
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
284
285
286
287
			if( m->GetMarker(unite.at(j),del_protect) ) doexit = true; 
			adj_type const & lc = m->LowConn(unite.at(j));
			for(adj_type::size_type it = 0; it < lc.size(); it++) if( !m->GetMarker(lc[it],hm) )
				face_visit[lc[it]]++;
Kirill Terekhov's avatar
Kirill Terekhov committed
288
289
		}
		if( doexit ) return false;
Kirill Terekhov's avatar
Kirill Terekhov committed
290
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
291
292
293
294
		dynarray<HandleType,64> edges;
		dynarray<HandleType,64> nodes;		
		for(tiny_map<HandleType,int,64>::iterator it = face_visit.begin(); it != face_visit.end(); it++)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
295
296
			if( it->second != 1 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
297
298
299
300
301
				if( m->GetMarker(it->first,del_protect) ) doexit = true;
				m->SetMarker(it->first,rem);
				adj_type const & lc = m->LowConn(it->first);
				for(adj_type::size_type jt = 0; jt < lc.size(); jt++) if( !m->GetMarker(lc[jt],hm) )
					if( !m->GetMarker(lc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
302
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
303
304
						m->SetMarker(lc[jt],rem);
						edges.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
305
306
					}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
307
308
		}
		for(dynarray<HandleType,64>::size_type i = 0; i < edges.size(); i++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
309
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
310
311
312
			m->RemMarker(edges[i],rem);
			adj_type const & lc = m->LowConn(edges[i]);
			for(adj_type::size_type jt = 0; jt < lc.size(); jt++) if( !m->GetMarker(lc[jt],hm) )
Kirill Terekhov's avatar
Kirill Terekhov committed
313
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
314
				if( !m->GetMarker(lc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
315
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
316
317
					m->SetMarker(lc[jt],rem);
					nodes.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
318
319
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
320
321
322
323
324
325
326
327
328
			int nonzero = 0;
			adj_type const & hc = m->HighConn(edges[i]);
			for(adj_type::size_type jt = 0; jt < hc.size(); jt++) if( !m->GetMarker(hc[jt],hm) ) //iterate over faces
				if( !m->GetMarker(hc[jt],rem) ) nonzero++; // check if it is not deleted
			if( nonzero == 0 ) //all faces should be deleted, edge to remove
			{
				m->SetMarker(edges[i],rem);
				if( m->GetMarker(edges[i],del_protect) ) doexit = true;
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
329
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
330
		for(dynarray<HandleType,64>::size_type i = 0; i < nodes.size(); i++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
331
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
332
333
			m->RemMarker(nodes[i],rem);
			if( m->GetMarker(nodes[i],del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
334
335
			{
				int nonzero = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
336
337
338
339
				adj_type const & hc = m->HighConn(nodes[i]);
				for(adj_type::size_type jt = 0; jt < hc.size(); jt++) if( !m->GetMarker(hc[jt],hm) )
					if( !m->GetMarker(hc[jt],rem) ) nonzero++;
				if( nonzero == 0 ) doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
340
341
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
342
343
344
		for(tiny_map<HandleType,int,64>::iterator it = face_visit.begin(); it != face_visit.end(); it++)
				if( it->second != 1 ) m->RemMarker(it->first,rem);
		for(dynarray<HandleType,64>::size_type i = 0; i < edges.size(); i++)  m->RemMarker(edges[i],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
345
346
347
348
349
350
		m->ReleaseMarker(rem);
		if( doexit ) return false;
		return true;
	}
	
	
Kirill Terekhov's avatar
Kirill Terekhov committed
351
	Face Face::UniteFaces(ElementArray<Face> & unite, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
352
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
353
354
		Mesh * m = unite.GetMeshLink();
		if( unite.empty() ) return Face(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
355
		MarkerType hm = m->HideMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
356
		bool doexit = false, dothrow = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
357
358
359
360
		for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++)
			if( m->GetMarker(unite.at(j),del_protect) ) doexit = true;
		if( doexit ) return Face(m,InvalidHandle());
		dynarray<HandleType,64> high_conn_set;
Kirill Terekhov's avatar
Kirill Terekhov committed
361
362
		MarkerType edge_set = m->CreateMarker();
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
363
364
		
		
Kirill Terekhov's avatar
Kirill Terekhov committed
365
366
367
368
369
370
		for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++)
		{
			adj_type const & hc = m->HighConn(unite.at(j));
			for(adj_type::size_type it = 0; it < hc.size(); it++) if( !m->GetMarker(hc[it],hm) )
			{
				if( !m->GetMarker(hc[it],edge_set) )
Kirill Terekhov's avatar
Kirill Terekhov committed
371
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
372
373
					high_conn_set.push_back(hc[it]);
					m->SetMarker(hc[it],edge_set);
Kirill Terekhov's avatar
Kirill Terekhov committed
374
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
375
376
			}
		}		
Kirill Terekhov's avatar
Kirill Terekhov committed
377
378
		
		
Kirill Terekhov's avatar
Kirill Terekhov committed
379
380
		for(dynarray<HandleType,64>::size_type j = 0; j < high_conn_set.size(); j++)
			m->RemMarker(high_conn_set[j],edge_set);
Kirill Terekhov's avatar
Kirill Terekhov committed
381
382
383
384
385
386
387
388
389
		
		
		if( m->GetTopologyCheck(TRIPLE_SHARED_FACE) && high_conn_set.size() > 2 )
		{
			m->SetTopologyError(TRIPLE_SHARED_FACE);
			if( m->GetTopologyCheck(PRINT_NOTIFY) ) std::cerr << TopologyCheckNotifyString(TRIPLE_SHARED_FACE) << std::endl;
			if( m->GetTopologyCheck(THROW_EXCEPTION) ) throw TopologyCheckError;
		}
		
Kirill Terekhov's avatar
Kirill Terekhov committed
390
391
392
393
		dynarray<HandleType,64> nodes;
		tiny_map<HandleType, int,64> edge_visit;
		ElementArray<Edge> edges(m);
		for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
394
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
395
396
397
			adj_type const & lc = m->LowConn(unite.at(j));
			for(adj_type::size_type it = 0; it < lc.size(); it++) if( !m->GetMarker(lc[it],hm) )
				edge_visit[lc[it]]++;
Kirill Terekhov's avatar
Kirill Terekhov committed
398
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
399
400
401
		HandleType first = InvalidHandle(); //first edge
		HandleType prev = InvalidHandle(); //prev node
		for(tiny_map<HandleType,int,64>::iterator it = edge_visit.begin(); it != edge_visit.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
402
403
404
		{
			if( it->second == 1 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
405
406
				m->SetMarker(it->first,edge_set);
				if( first == InvalidHandle() ) first = it->first;
Kirill Terekhov's avatar
Kirill Terekhov committed
407
408
409
			}
			else if( it->second == 2 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
410
411
412
413
414
415
				if( m->GetMarker(it->first,del_protect) ) doexit = true; // edge is protected
				m->SetMarker(it->first,rem);
				adj_type const & lc = m->LowConn(it->first);
				for(adj_type::size_type jt = 0; jt < lc.size(); jt++) if( !m->GetMarker(lc[jt],hm) )
				{
					if( !m->GetMarker(lc[jt],edge_set) )
Kirill Terekhov's avatar
Kirill Terekhov committed
416
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
417
418
						m->SetMarker(lc[jt],edge_set);
						nodes.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
419
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
420
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
421
422
423
424
425
426
427
428
			}
			else 
			{
				doexit = true; //the faces we unite would not appear as one surface
				dothrow = true;
			}
		}
		
Kirill Terekhov's avatar
Kirill Terekhov committed
429
		for(dynarray<HandleType,64>::size_type j = 0; j < nodes.size(); j++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
430
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
431
432
			m->RemMarker(nodes[j],edge_set);
			if( m->GetMarker(nodes[j],del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
433
434
			{
				int nonzero = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
435
436
437
				adj_type const & hc = m->HighConn(nodes[j]);
				for(adj_type::size_type it = 0; it < hc.size(); it++) if( !m->GetMarker(hc[it],hm) ) //iterate through edges of the node
					if( !m->GetMarker(hc[it],rem) ) nonzero++; // check if edge should not be deleted
Kirill Terekhov's avatar
Kirill Terekhov committed
438
439
440
441
442
443
444
				if( nonzero == 0 ) //all edges are deleted but the node is protected
					doexit = true;
			}
		}
			
		if( doexit )
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
445
446
447
448
449
			for(tiny_map<HandleType,int,64>::iterator it = edge_visit.begin(); it != edge_visit.end(); it++)
			{
				if( it->second != 1 ) m->RemMarker(it->first,rem);
				else m->RemMarker(it->first,edge_set);
			}	
Kirill Terekhov's avatar
Kirill Terekhov committed
450
451
			m->ReleaseMarker(edge_set);
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
452
453
			assert( !dothrow ); //report the situation, because user need to debug the input
			return Face(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
454
455
456
457
458
459
460
		}
		edges.push_back(first);
		edges.back()->RemMarker(edge_set);
		bool done = false;
		int q = 0;
		while( !done )
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
461
			enumerator k1 = ENUMUNDEF,k2;
Kirill Terekhov's avatar
Kirill Terekhov committed
462
			adj_type const & lc = m->LowConn(edges.atback());
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
463
464
			k1 = m->getNext(lc.data(),static_cast<enumerator>(lc.size()),k1,hm);
			k2 = m->getNext(lc.data(),static_cast<enumerator>(lc.size()),k1,hm);
Kirill Terekhov's avatar
Kirill Terekhov committed
465
466
			if( lc[k1] != prev ) 
				prev = lc[k1]; 
Kirill Terekhov's avatar
Kirill Terekhov committed
467
			else 
Kirill Terekhov's avatar
Kirill Terekhov committed
468
				prev = lc[k2];
Kirill Terekhov's avatar
Kirill Terekhov committed
469
			bool found = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
470
471
			adj_type const & hc = m->HighConn(prev);
			for(adj_type::size_type it = 0; it < hc.size(); ++it) if( !m->GetMarker(hc[it],hm) )
Kirill Terekhov's avatar
Kirill Terekhov committed
472
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
473
				if( hc[it] == first && q != 0)
Kirill Terekhov's avatar
Kirill Terekhov committed
474
475
476
477
				{
					found = done = true;
					break;
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
478
				if( m->GetMarker(hc[it],edge_set) )
Kirill Terekhov's avatar
Kirill Terekhov committed
479
480
481
				{
					q++;
					found = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
482
483
					edges.push_back(hc[it]);
					m->RemMarker(hc[it],edge_set);
Kirill Terekhov's avatar
Kirill Terekhov committed
484
485
486
					break;
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
487
488
			assert(found);
			//if( !found ) throw Failure;
Kirill Terekhov's avatar
Kirill Terekhov committed
489
490
491
492
493
494
		}
		m->ReleaseMarker(edge_set);
		
		

		
Kirill Terekhov's avatar
Kirill Terekhov committed
495
496
		for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++)
			m->SetMarker(unite.at(j),rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
497
		
Kirill Terekhov's avatar
Kirill Terekhov committed
498
499
500
		if( !m->HideMarker() ) //we can't hide elements
		{
			for(dynarray<HandleType,64>::size_type it = 0; it < high_conn_set.size(); it++) //untie every face from cell
Kirill Terekhov's avatar
Kirill Terekhov committed
501
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
502
503
504
505
506
				adj_type & lc = m->LowConn(high_conn_set[it]);
				adj_type::iterator jt = lc.begin();
				while( jt != lc.end()) //don't need to check is it hidden
					if( m->GetMarker(*jt,rem) )
						jt = lc.erase(jt);
Kirill Terekhov's avatar
Kirill Terekhov committed
507
508
					else jt++;
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
509
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
510
		
Kirill Terekhov's avatar
Kirill Terekhov committed
511
512
513
		if( m->HideMarker() )
			for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++) m->Hide(unite.at(j));
		else
Kirill Terekhov's avatar
Kirill Terekhov committed
514
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
515
			for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++) // delete all faces
Kirill Terekhov's avatar
Kirill Terekhov committed
516
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
517
518
519
520
				m->HighConn(unite.at(j)).clear(); //untie cells from face
				if( m->GetMarker(unite.at(j),del_protect) )
					std::cout << __FUNCTION__ << " deleted protected face, united " << unite.size() << " faces " << std::endl;
				m->Delete(unite.at(j)); 
Kirill Terekhov's avatar
Kirill Terekhov committed
521
522
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
523
524

		for(tiny_map<HandleType,int,64>::iterator it = edge_visit.begin(); it != edge_visit.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
525
526
			if( it->second != 1 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
527
528
529
530
531
				m->RemMarker(it->first,rem);
				assert( m->HighConn(it->first).empty() || m->Count(m->HighConn(it->first).data(),static_cast<integer>(m->HighConn(it->first).size()),hm) == 0 ); //it's connected to face somewhere
				if( m->GetMarker(it->first,del_protect) )
					std::cout << __FUNCTION__ << " deleted protected edge, united " << unite.size() << " faces " << std::endl;
				m->Delete(it->first);
Kirill Terekhov's avatar
Kirill Terekhov committed
532
533
534
535
			}
			
		m->ReleaseMarker(rem);

Kirill Terekhov's avatar
Kirill Terekhov committed
536
		for(dynarray<HandleType,64>::size_type it = 0; it < nodes.size(); it++) //delete nodes inside the face
Kirill Terekhov's avatar
Kirill Terekhov committed
537
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
538
539
			adj_type const & hc = m->HighConn(nodes[it]);
			if( hc.empty() || m->Count(hc.data(),static_cast<integer>(hc.size()),hm) == 0 )
Kirill Terekhov's avatar
Kirill Terekhov committed
540
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
541
				if( !m->Hide(nodes[it]) )
Kirill Terekhov's avatar
Kirill Terekhov committed
542
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
543
544
545
					adj_type & lc = m->LowConn(nodes[it]);
					adj_type::iterator jt = lc.begin();
					while(jt != lc.end() ) // iterate through cells of the node
Kirill Terekhov's avatar
Kirill Terekhov committed
546
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
547
548
549
						adj_type & ihc = m->HighConn(*jt);
						adj_type::iterator qt = ihc.begin(); //iterate through nodes of the cell
						while( qt != ihc.end() )
Kirill Terekhov's avatar
Kirill Terekhov committed
550
						{
Kirill Terekhov's avatar
Kirill Terekhov committed
551
552
							if( *qt == nodes[it] ) 
								qt = ihc.erase(qt); //remove links from the cell to the node
Kirill Terekhov's avatar
Kirill Terekhov committed
553
554
555
556
							else ++qt;
						}
						++jt;
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
557
558
559
560
					lc.clear(); // remove links to cells
					if( m->GetMarker(nodes[it],del_protect) )
						std::cout << __FUNCTION__ << " deleted protected node, united " << unite.size() << " faces " << std::endl;
					m->Destroy(nodes[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
561
562
563
564
				}
			}
		}
				
Kirill Terekhov's avatar
Kirill Terekhov committed
565
		Face ret = m->CreateFace(edges).first;
Kirill Terekhov's avatar
Kirill Terekhov committed
566
		
Kirill Terekhov's avatar
Kirill Terekhov committed
567
		assert( ret->GetGeometricType() != MultiLine );
Kirill Terekhov's avatar
Kirill Terekhov committed
568
		
Kirill Terekhov's avatar
Kirill Terekhov committed
569
570
		adj_type & hc = m->HighConn(ret->GetHandle());
		for(dynarray<HandleType,64>::size_type it = 0; it < high_conn_set.size(); it++)  //tie new face to old cells
Kirill Terekhov's avatar
Kirill Terekhov committed
571
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
572
573
			hc.push_back(high_conn_set[it]); // connect new face to cells
			m->LowConn(high_conn_set[it]).push_back(ret.GetHandle()); // connect cells to new face
Kirill Terekhov's avatar
Kirill Terekhov committed
574
575
			
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
576
		for(dynarray<HandleType,64>::size_type it = 0; it < high_conn_set.size(); it++)  //tie new face to old cells
Kirill Terekhov's avatar
Kirill Terekhov committed
577
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
578
579
			m->ComputeGeometricType(high_conn_set[it]);
			m->RecomputeGeometricData(high_conn_set[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
580
581
582
583
584
585
		}
		
		return ret;
	}
	
	
Kirill Terekhov's avatar
Kirill Terekhov committed
586
	bool Face::TestUniteFaces(const ElementArray<Face> & unite, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
587
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
588
589
		Mesh * m = unite.GetMeshLink();
		if( unite.size() == 0 ) return false;
Kirill Terekhov's avatar
Kirill Terekhov committed
590
		bool doexit = false, dothrow = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
591
592
		for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++)
			if( m->GetMarker(unite.at(j),del_protect) ) doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
593
		MarkerType hm = m->HideMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
594
		if( doexit ) return false;
Kirill Terekhov's avatar
Kirill Terekhov committed
595
		dynarray<HandleType,64> high_conn_set;
Kirill Terekhov's avatar
Kirill Terekhov committed
596
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
597
598
599
600
601
		for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++)
		{
			adj_type const & hc = m->HighConn(unite.at(j));
			for(adj_type::size_type it = 0; it < hc.size(); it++) if( !m->GetMarker(hc[it],hm) )
				if( !m->GetMarker(hc[it],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
602
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
603
604
					high_conn_set.push_back(hc[it]);
					m->SetMarker(hc[it],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
605
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
606
607
608
609
610
611
		}
		for(dynarray<HandleType,64>::size_type j = 0; j < high_conn_set.size(); j++) 
			m->RemMarker(high_conn_set[j],rem);
		dynarray<HandleType,64> nodes;
		tiny_map<HandleType, int,64> edge_visit;
		for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
612
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
613
614
615
			adj_type const & lc = m->LowConn(unite.at(j));
			for(adj_type::size_type it = 0; it < lc.size(); it++) if( !m->GetMarker(lc[it],hm) )
				edge_visit[lc[it]]++;
Kirill Terekhov's avatar
Kirill Terekhov committed
616
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
617
		for(tiny_map<HandleType,int,64>::iterator it = edge_visit.begin(); it != edge_visit.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
618
619
620
		{
			if( it->second == 2 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
621
622
623
624
625
626
				if( m->GetMarker(it->first,del_protect) ) doexit = true; // edge is protected
				m->SetMarker(it->first,rem);
				adj_type const & lc = m->LowConn(it->first);
				for(adj_type::size_type jt = 0; jt < lc.size(); jt++) if( !m->GetMarker(lc[jt],hm) )
				{
					if( !m->GetMarker(lc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
627
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
628
629
						m->SetMarker(lc[jt],rem);
						nodes.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
630
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
631
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
632
633
634
635
636
637
638
			}
			else if( it->second != 1 )
			{
				doexit = true;
				dothrow = true;
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
639
		for(dynarray<HandleType,64>::size_type j = 0; j < nodes.size(); j++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
640
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
641
642
			m->RemMarker(nodes[j],rem);
			if( m->GetMarker(nodes[j],del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
643
644
			{
				int nonzero = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
645
646
647
				adj_type const & hc = m->HighConn(nodes[j]);
				for(adj_type::size_type it = 0; it < hc.size(); it++) if( !m->GetMarker(hc[it],hm) )//iterate through edges of the node
					if( !m->GetMarker(hc[it],rem) ) nonzero++; // check if edge should not be deleted
Kirill Terekhov's avatar
Kirill Terekhov committed
648
649
650
651
				if( nonzero == 0 ) //all edges are deleted but the node is protected
					doexit = true;
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
652
653
		for(tiny_map<HandleType,int,64>::iterator it = edge_visit.begin(); it != edge_visit.end(); it++)
			if( it->second != 1 ) m->RemMarker(it->first,rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
654
655
656
		m->ReleaseMarker(rem);
		if( doexit )
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
657
658
			assert(!dothrow);
			//if( dothrow ) throw Impossible; //something went the way it shouldn't, possibly bad input
Kirill Terekhov's avatar
Kirill Terekhov committed
659
660
661
662
663
			return false;
		}
		return true;
	}

Kirill Terekhov's avatar
Kirill Terekhov committed
664
	Edge Edge::UniteEdges(ElementArray<Edge> & edges, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
665
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
666
667
668
		Mesh * m = edges.GetMeshLink();
		if( edges.size() == 0 ) return Edge(m,InvalidHandle());
		
Kirill Terekhov's avatar
Kirill Terekhov committed
669
		bool doexit = false, dothrow = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
670
671
		MarkerType hm = m->HideMarker();
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
672
673
674
675
676
		dynarray<HandleType,64> cells;
		dynarray<HandleType,64> high_conn_faces;
		tiny_map<HandleType,int,64> nodes;
		ElementArray<Node> build_nodes(m);
		for(ElementArray<Edge>::size_type it = 0; it < edges.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
677
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
678
			if( m->GetMarker(edges.at(it),del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
679
				doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
680
681
			adj_type const & hc = m->HighConn(edges.at(it));
			for(adj_type::size_type jt = 0; jt != hc.size(); ++jt) if( !m->GetMarker(hc[jt],hm) )
Kirill Terekhov's avatar
Kirill Terekhov committed
682
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
683
				if( !m->GetMarker(hc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
684
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
685
686
					high_conn_faces.push_back(hc[jt]);
					m->SetMarker(hc[jt],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
687
688
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
689
690
691
			adj_type const & lc = m->LowConn(edges.at(it));
			for(adj_type::size_type jt = 0; jt < lc.size(); ++jt) if( !m->GetMarker(lc[jt],hm) )
				nodes[lc[jt]]++;
Kirill Terekhov's avatar
Kirill Terekhov committed
692
693
		}
		
Kirill Terekhov's avatar
Kirill Terekhov committed
694
		for(dynarray<HandleType,64>::size_type it = 0; it < high_conn_faces.size(); ++it) 
Kirill Terekhov's avatar
Kirill Terekhov committed
695
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
696
697
698
699
700
			m->RemMarker(high_conn_faces[it],rem);
			adj_type const & hc = m->HighConn(high_conn_faces[it]);
			for(adj_type::size_type jt = 0; jt < hc.size(); ++jt)
			{
				if( !m->GetMarker(hc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
701
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
702
703
					m->SetMarker(hc[jt],rem);
					cells.push_back(hc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
704
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
705
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
706
707
708
709
710
		}

		if( doexit )
		{
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
711
			return Edge(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
712
713
		}
		
Kirill Terekhov's avatar
Kirill Terekhov committed
714
		for(tiny_map<HandleType,int,64>::iterator it = nodes.begin(); it != nodes.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
715
716
717
718
719
		{
			if( it->second == 1 )
				build_nodes.push_back(it->first);
			else if( it->second == 2 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
720
				if( m->GetMarker(it->first,del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
721
722
723
724
					doexit = true;
			}
			else 
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
725
				doexit = true; //edges have some loop
Kirill Terekhov's avatar
Kirill Terekhov committed
726
727
728
729
730
731
732
				dothrow = true;
			}
		}

		if( doexit )
		{
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
733
734
735
			assert(!dothrow);
			//if( dothrow ) throw Impossible; // bad input
			return Edge(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
736
737
738
		}


Kirill Terekhov's avatar
Kirill Terekhov committed
739
		dynarray<adj_type::size_type,64> insert_pos; //position where we insert new edge
Kirill Terekhov's avatar
Kirill Terekhov committed
740

Kirill Terekhov's avatar
Kirill Terekhov committed
741
		for(ElementArray<Edge>::size_type it = 0; it < edges.size(); ++it) m->SetMarker(edges.at(it),rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
742

Kirill Terekhov's avatar
Kirill Terekhov committed
743
744
745
746
747
748
		for(dynarray<HandleType,64>::size_type it = 0; it < high_conn_faces.size(); ++it)
		{
			adj_type const & lc = m->LowConn(high_conn_faces[it]); //edges of face
			for(adj_type::size_type k = 0; k < lc.size(); k++) //insert new edge to the first position where we delete old edge
			{
				if( m->GetMarker(lc[k],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
749
750
				{
					//all united edges should appear in consecutive order in deleted face
Kirill Terekhov's avatar
Kirill Terekhov committed
751
					/*
Kirill Terekhov's avatar
Kirill Terekhov committed
752
					adj_type::size_type sum = 0, j = k;
Kirill Terekhov's avatar
Kirill Terekhov committed
753
					while( j < lc.size() && !m->GetMarker(lc[j],hm) && m->GetMarker(lc[j],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
754
755
756
					{
						sum++; j++;
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
757
					if( sum != static_cast<adj_type::size_type>(edges.size()) ) //not all edges belong to current face - face will be broken!
Kirill Terekhov's avatar
Kirill Terekhov committed
758
759
760
761
					{
						doexit = true;
						dothrow = true;
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
762
					 */
Kirill Terekhov's avatar
Kirill Terekhov committed
763
764
765
					insert_pos.push_back(k);
					break;
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
766
767
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
768
769
770

		if( doexit )
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
771
			for(ElementArray<Edge>::size_type it = 0; it < edges.size(); ++it) m->RemMarker(edges.at(it),rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
772
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
773
774
775
			assert(!dothrow);
			//if( dothrow ) throw Impossible; // bad input
			return Edge(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
776
777
		}

Kirill Terekhov's avatar
Kirill Terekhov committed
778
		if( !m->HideMarker() ) //disconnect if cannot hide
Kirill Terekhov's avatar
Kirill Terekhov committed
779
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
780
			for(dynarray<HandleType,64>::size_type it = 0; it < high_conn_faces.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
781
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
782
783
784
				adj_type & lc = m->LowConn(high_conn_faces[it]);
				adj_iterator jt = lc.begin(); //iterate over edges of faces
				while( jt != lc.end())
Kirill Terekhov's avatar
Kirill Terekhov committed
785
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
786
787
					if( m->GetMarker(*jt,rem) )
						jt = lc.erase(jt);
Kirill Terekhov's avatar
Kirill Terekhov committed
788
789
790
791
792
793
					else ++jt;
				}
			}
		}


Kirill Terekhov's avatar
Kirill Terekhov committed
794
		for(ElementArray<Edge>::size_type it = 0; it < edges.size(); ++it)//delete edges
Kirill Terekhov's avatar
Kirill Terekhov committed
795
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
796
797
			m->RemMarker(edges.at(it),rem);
			if( !m->Hide(edges.at(it)) ) //cannot hide
Kirill Terekhov's avatar
Kirill Terekhov committed
798
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
799
800
				m->HighConn(edges.at(it)).clear(); //remove connection from edge to faces
				m->Destroy(edges.at(it));
Kirill Terekhov's avatar
Kirill Terekhov committed
801
802
803
804
805
			}
		}

		m->ReleaseMarker(rem);

Kirill Terekhov's avatar
Kirill Terekhov committed
806
807
		for(tiny_map<HandleType,int,64>::iterator it = nodes.begin(); it != nodes.end(); it++)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
808
809
			if( it->second != 1 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
810
				if( !m->Hide(it->first) ) //cannot hide, we have to untie cells from nodes
Kirill Terekhov's avatar
Kirill Terekhov committed
811
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
812
813
					adj_type & lc = m->LowConn(it->first);
					for(adj_type::size_type qt = 0; qt < lc.size(); ++qt) //iterate through cells of the node
Kirill Terekhov's avatar
Kirill Terekhov committed
814
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
815
816
817
						adj_type & hc = m->HighConn(lc[qt]);
						adj_iterator jt = hc.begin();
						while(jt != hc.end() ) // iterate through nodes of the cell
Kirill Terekhov's avatar
Kirill Terekhov committed
818
819
						{
							if( *jt == it->first )
Kirill Terekhov's avatar
Kirill Terekhov committed
820
								jt = hc.erase(jt); //erase link to node
Kirill Terekhov's avatar
Kirill Terekhov committed
821
822
823
							else ++jt;
						}
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
824
					m->Destroy(it->first);
Kirill Terekhov's avatar
Kirill Terekhov committed
825
826
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
827
828
829
830
		}
			
		Edge e = m->CreateEdge(build_nodes).first;
		adj_type & ehc = m->HighConn(e->GetHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
831

Kirill Terekhov's avatar
Kirill Terekhov committed
832
		for(dynarray<adj_type::size_type,64>::size_type k = 0; k < insert_pos.size(); k++)
Kirill Terekhov's avatar
Kirill Terekhov committed
833
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
834
835
836
837
			adj_type & lc = m->LowConn(high_conn_faces[k]);
			lc.insert(lc.begin()+insert_pos[k],e->GetHandle());
			ehc.push_back(high_conn_faces[k]);
			m->ComputeGeometricType(high_conn_faces[k]);
Kirill Terekhov's avatar
Kirill Terekhov committed
838
839
840
			m->RecomputeGeometricData(high_conn_faces[k]);
		}

Kirill Terekhov's avatar
Kirill Terekhov committed
841
		for(dynarray<HandleType,64>::size_type it = 0; it < cells.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
842
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
843
844
			m->ComputeGeometricType(cells[it]);
			m->RecomputeGeometricData(cells[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
845
846
847
848
849
		}


		return e;
	}
Kirill Terekhov's avatar
Kirill Terekhov committed
850
	bool Edge::TestUniteEdges(const ElementArray<Edge> & edges, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
851
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
852
853
		if( edges.empty() ) return false;
		Mesh * m = edges.GetMeshLink();
Kirill Terekhov's avatar
Kirill Terekhov committed
854
		bool doexit = false, dothrow = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
855
856
		MarkerType hm = m->HideMarker();
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
857
858
859
860
		dynarray<HandleType,64> high_conn_faces;
		tiny_map<HandleType,int,64> nodes;

		for(ElementArray<Edge>::size_type it = 0; it < edges.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
861
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
862
			if( m->GetMarker(edges.at(it),del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
863
				doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
864
865
			adj_type const & hc = m->HighConn(edges.at(it));
			for(adj_type::size_type jt = 0; jt < hc.size(); ++jt) if( !m->GetMarker(hc[jt],hm) )
Kirill Terekhov's avatar
Kirill Terekhov committed
866
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
867
				if( !m->GetMarker(hc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
868
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
869
870
					high_conn_faces.push_back(hc[jt]);
					m->SetMarker(hc[jt],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
871
872
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
873
874
875
			adj_type const & lc = m->LowConn(edges.at(it));
			for(adj_type::size_type jt = 0; jt < lc.size(); ++jt) if( !m->GetMarker(lc[jt],hm) )
				nodes[lc[jt]]++;
Kirill Terekhov's avatar
Kirill Terekhov committed
876
877
		}
		
Kirill Terekhov's avatar
Kirill Terekhov committed
878
879
		for(dynarray<HandleType,64>::size_type it = 0; it < high_conn_faces.size(); ++it) 
			m->RemMarker(high_conn_faces[it],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
880
881
882
883
884
885
886

		if( doexit )
		{
			m->ReleaseMarker(rem);
			return false;
		}
		
Kirill Terekhov's avatar
Kirill Terekhov committed
887
		for(tiny_map<HandleType,int,64>::iterator it = nodes.begin(); it != nodes.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
888
889
890
891
892
893
894
		{
			if( it->second == 1 )
			{
//				build_nodes.push_back(it->first);
			}
			else if( it->second == 2 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
895
				if( m->GetMarker(it->first,del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
896
897
898
899
900
901
902
903
904
905
906
907
					doexit = true;
			}
			else 
			{
				doexit = true;
				dothrow = true;
			}
		}

		if( doexit )
		{
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
908
909
			assert(!dothrow); //inner loop in deleted edges
			//if( dothrow ) throw Impossible; // bad input
Kirill Terekhov's avatar
Kirill Terekhov committed
910
911
912
913
914
			return false;
		}



Kirill Terekhov's avatar
Kirill Terekhov committed
915
		for(ElementArray<Edge>::size_type it = 0; it < edges.size(); ++it) m->SetMarker(edges.at(it),rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
916

Kirill Terekhov's avatar
Kirill Terekhov committed
917
918
919
920
921
922
		for(dynarray<HandleType,64>::size_type it = 0; it < high_conn_faces.size(); ++it)
		{
			adj_type const & lc = m->LowConn(high_conn_faces[it]);
			for(adj_type::size_type k = 0; k < lc.size(); k++) //insert new edge to the first position where we delete old edge
			{
				if( m->GetMarker(lc[k],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
923
924
				{
					//all united edges should appear in consecutive order in deleted face
Kirill Terekhov's avatar
Kirill Terekhov committed
925
926
					adj_type::size_type sum = 0, j = k;
					while( !m->GetMarker(lc[j],hm) && m->GetMarker(lc[j],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
927
928
929
					{
						sum++; j++;
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
930
					if( sum != static_cast<adj_type::size_type>(edges.size()) )
Kirill Terekhov's avatar
Kirill Terekhov committed
931
932
933
934
935
936
					{
						doexit = true;
						dothrow = true;
					}
					break;
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
937
938
939
			}
		}
		for(ElementArray<Edge>::size_type it = 0; it < edges.size(); ++it) m->RemMarker(edges.at(it),rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
940
941
942
943

		if( doexit )
		{
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
944
945
			assert(!dothrow);
			//if( dothrow ) throw Impossible; // bad input
Kirill Terekhov's avatar
Kirill Terekhov committed
946
947
948
949
950
951
952
			return false;
		}

		return true;
	}


Kirill Terekhov's avatar
Kirill Terekhov committed
953
	ElementArray<Edge> Edge::SplitEdge(Edge e, const ElementArray<Node> & nodes, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
954
955
	{
		Mesh * m = e->GetMeshLink();
Kirill Terekhov's avatar
Kirill Terekhov committed
956
957
958
959
960
961
		ElementArray<Edge> ret(m);
		dynarray<HandleType,64> faces;
		dynarray<HandleType,128> cells;
		HandleType n[2];
		if( e->GetMarker(del_protect) || nodes.empty() ) return ret;
		ret.reserve(nodes.size()+1);
Kirill Terekhov's avatar
Kirill Terekhov committed
962
963
		MarkerType hm = m->HideMarker();
		MarkerType dup = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
964
965
966
		adj_type & hc = m->HighConn(e->GetHandle());
		
		for(adj_type::size_type it = 0; it < hc.size(); ++it) if( !m->GetMarker(hc[it],hm) )
Kirill Terekhov's avatar
Kirill Terekhov committed
967
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
968
969
970
971
972
			faces.push_back(hc[it]);
			adj_type const & ihc = m->HighConn(hc[it]);
			for(adj_type::size_type jt = 0; jt < ihc.size(); ++jt) if( !m->GetMarker(ihc[jt],hm) )
			{
				if( !m->GetMarker(ihc[jt],dup) )
Kirill Terekhov's avatar
Kirill Terekhov committed
973
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
974
975
					cells.push_back(ihc[jt]);
					m->SetMarker(ihc[jt],dup);
Kirill Terekhov's avatar
Kirill Terekhov committed
976
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
977
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
978
979
		}

Kirill Terekhov's avatar
Kirill Terekhov committed
980
981
		for(dynarray<HandleType,128>::size_type it = 0; it < cells.size(); ++it)
			m->RemMarker(cells[it],dup);