modify.cpp 72 KB
Newer Older
Kirill Terekhov's avatar
Kirill Terekhov committed
1
2
3
4
5
6
7
8
9
10
#include "inmost.h"
#include <stack>
#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
Fixes    
Kirill Terekhov committed
12
	__INLINE void make_vec(const Storage::real p1[3], const Storage::real p2[3], Storage::real out[3])
Kirill Terekhov's avatar
Kirill Terekhov committed
13
14
15
16
17
18
	{
		out[0] = p1[0] - p2[0];
		out[1] = p1[1] - p2[1];
		out[2] = p1[2] - p2[2];
	}

Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
19
	__INLINE void cross_prod(const Storage::real v1[3],const Storage::real v2[3], Storage::real out[3])
Kirill Terekhov's avatar
Kirill Terekhov committed
20
21
22
23
24
25
	{
		out[0] = v1[1]*v2[2] - v1[2]*v2[1];
		out[1] = v1[2]*v2[0] - v1[0]*v2[2];
		out[2] = v1[0]*v2[1] - v1[1]*v2[0];
	}

Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
26
	__INLINE Storage::real __det3d(Storage::real a, Storage::real b, Storage::real c,
Kirill Terekhov's avatar
Kirill Terekhov committed
27
28
	                             Storage::real d, Storage::real e, Storage::real f,
	                             Storage::real g, Storage::real h, Storage::real i ) 
Kirill Terekhov's avatar
Kirill Terekhov committed
29
30
31
32
	{
		return a*e*i - c*e*g + b*f*g - a*f*h + c*d*h - b*d*i;
	}
	
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
33
	__INLINE Storage::real __det3v(const Storage::real * x,const Storage::real * y,const Storage::real * z) 
Kirill Terekhov's avatar
Kirill Terekhov committed
34
35
36
37
	{
		return __det3d(x[0], x[1], x[2],  y[0], y[1], y[2],  z[0], z[1], z[2]);
	}

Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
38
	__INLINE Storage::real dot_prod(const Storage::real v1[3],const Storage::real v2[3])
Kirill Terekhov's avatar
Kirill Terekhov committed
39
40
41
	{
		return v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2];
	}
Kirill Terekhov's avatar
Kirill Terekhov committed
42
43
44
	
	void Face::SwapCells()
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
45
46
47
		Mesh * m = GetMeshLink();
		MarkerType hm = m->HideMarker();
		adj_type & hc = m->HighConn(GetHandle());
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
48
		if( m->Count(hc.data(),static_cast<enumerator>(hc.size()),hm) == 2 )
Kirill Terekhov's avatar
Kirill Terekhov committed
49
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
50
51
52
			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
53
54
55
			HandleType temp = hc[k1];
			hc[k1] = hc[k2];
			hc[k2] = temp;
Kirill Terekhov's avatar
Kirill Terekhov committed
56
57
58
59
			FixNormalOrientation(); //maybe should change orientation?
		}
	}
	
Kirill Terekhov's avatar
Kirill Terekhov committed
60
	void Element::Disconnect(bool del_upper) const
Kirill Terekhov's avatar
Kirill Terekhov committed
61
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
62
63
64
		adj_type::size_type i = 0;
		dynarray<adj_type::size_type,64> del;
		Mesh * m = GetMeshLink();
Kirill Terekhov's avatar
Kirill Terekhov committed
65
66
67
68
		//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
69
			
Kirill Terekhov's avatar
Kirill Terekhov committed
70
			MarkerType hm = m->HideMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
71
72
			adj_type & lc = m->LowConn(GetHandle());
			for( adj_type::size_type it = 0; it < lc.size(); it++) //iterator over faces
Kirill Terekhov's avatar
Kirill Terekhov committed
73
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
74
				adj_type & hc = m->HighConn(lc[it]);
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
75
				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
76
				{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
77
78
					enumerator k1 = ENUMUNDEF, k2;
					k1 = m->getNext(hc.data(),static_cast<enumerator>(hc.size()),k1,hm);
Kirill Terekhov's avatar
Kirill Terekhov committed
79
					if( hc[k1] == GetHandle() ) //the first cell is current
Kirill Terekhov's avatar
Kirill Terekhov committed
80
					{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
81
						k2 = m->getNext(hc.data(),static_cast<enumerator>(hc.size()),k1,hm);
Kirill Terekhov's avatar
Kirill Terekhov committed
82
83
84
85
						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
86
87
88
89
90
					}
				}
			}
		}
		//END NEW CODE - CHECK
Kirill Terekhov's avatar
Kirill Terekhov committed
91
92
		adj_type & hc = m->HighConn(GetHandle());
		for( adj_type::size_type it = 0; it < hc.size(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
93
94
		{
			int flag = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
95
96
97
			adj_type & ilc = m->LowConn(hc[it]);
			adj_type::iterator jt = ilc.begin();
			while (jt != ilc.end())
Kirill Terekhov's avatar
Kirill Terekhov committed
98
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
99
				if(*jt == GetHandle())
Kirill Terekhov's avatar
Kirill Terekhov committed
100
101
				{
					flag = 1;
Kirill Terekhov's avatar
Kirill Terekhov committed
102
					jt = ilc.erase(jt);
Kirill Terekhov's avatar
Kirill Terekhov committed
103
104
105
106
107
108
109
110
111
112
				}
				else ++jt;
			}
			if( flag ) del.push_back(i);
			i++;
		}
		if( del_upper )
		{
			if( GetElementType() < CELL ) 
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
113
114
115
				if( Hidden() ) 
				{
					for(dynarray<adj_type::size_type,64>::iterator it = del.begin(); it != del.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
116
						if( m->GetMarker(hc[*it],m->HideMarker()) ) m->Delete(hc[*it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
117
118
119
120
				}
				else 
				{
					for(dynarray<adj_type::size_type,64>::iterator it = del.begin(); it != del.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
121
						m->Delete(hc[*it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
122
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
123
124
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
125
126
127
		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
128
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
129
130
131
			adj_type & ihc = m->HighConn(lc[it]);
			adj_type::iterator jt = ihc.begin();
			while (jt != ihc.end())
Kirill Terekhov's avatar
Kirill Terekhov committed
132
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
133
				if(*jt == GetHandle()) jt = ihc.erase(jt);
Kirill Terekhov's avatar
Kirill Terekhov committed
134
135
136
				else ++jt;
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
137
		lc.clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
138
139
	}
	
Kirill Terekhov's avatar
Kirill Terekhov committed
140
	Cell Cell::UniteCells(ElementArray<Cell> & unite, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
141
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
142
143
144
145
146
		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
147
		bool doexit = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
148
		MarkerType hm = m->HideMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
149
		for(ElementArray<Cell>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
150
151
		{
			if( unite[j]->GetMarker(del_protect) ) doexit = true; 
Kirill Terekhov's avatar
Kirill Terekhov committed
152
153
154
			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
155
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
156
		if( doexit ) return Cell(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
157
		MarkerType visited = m->CreateMarker(), rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
158
159
160
161
		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
162
163
164
165
			if( it->second == 1 )
				faces.push_back(it->first);
			else
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
166
167
168
169
170
				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
171
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
172
173
						m->SetMarker(lc[jt],visited);
						edges.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
174
175
176
					}
				inner_faces.push_back(it->first);
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
177
178
		}
		for(dynarray<HandleType,64>::size_type i = 0; i < edges.size(); i++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
179
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
180
181
182
			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
183
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
184
				if( !m->GetMarker(lc[jt],visited) )
Kirill Terekhov's avatar
Kirill Terekhov committed
185
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
186
187
					m->SetMarker(lc[jt],visited);
					nodes.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
188
189
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
190
191
192
193
194
195
196
197
198
			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
199
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
200
		for(dynarray<HandleType,64>::size_type i = 0; i < nodes.size(); i++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
201
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
202
			m->RemMarker(nodes[i],visited);
Kirill Terekhov's avatar
Kirill Terekhov committed
203
			
Kirill Terekhov's avatar
Kirill Terekhov committed
204
			if( m->GetMarker(nodes[i],del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
205
206
			{
				int nonzero = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
207
208
209
				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
210
211
212
213
214
215
				if( nonzero == 0 )
					doexit = true;
				
			}
		}
		m->ReleaseMarker(visited);
Kirill Terekhov's avatar
Kirill Terekhov committed
216
217
218
219
		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
220
		m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
221
		if( doexit ) return Cell(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
222
		//delete cells
Kirill Terekhov's avatar
Kirill Terekhov committed
223
		for(ElementArray<Cell>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
224
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
225
226
227
			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
228
229
		}
		//delete inner faces
Kirill Terekhov's avatar
Kirill Terekhov committed
230
		for(dynarray<HandleType,64>::size_type j = 0; j < inner_faces.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
231
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
232
233
234
			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
235
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
236
237
238
239
		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
240
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
241
242
243
				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
244
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
245
246
247
248
249
250
		}
		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
251
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
252
253
254
255
256
				// 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
257
258
259
260
				//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
261
262
					//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
263
					//{
Kirill Terekhov's avatar
Kirill Terekhov committed
264
265
					//	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
266
267
					//	{
					//		if( *jt == nodes[j] )
Kirill Terekhov's avatar
Kirill Terekhov committed
268
					//			jt = (*it)->HighConn().erase(jt); //erase link to node
Kirill Terekhov's avatar
Kirill Terekhov committed
269
270
271
272
273
274
275
276
					//		else ++jt;
					//	}
					//  ++it;
					//}
					//nodes[j]->Disconnect();
					//nodes[j]->Delete();
				//}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
277
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
278
		//reconstruct cell by outer faces
Kirill Terekhov's avatar
Kirill Terekhov committed
279
		return m->CreateCell(faces).first;
Kirill Terekhov's avatar
Kirill Terekhov committed
280
281
282
	}
	
	
Kirill Terekhov's avatar
Kirill Terekhov committed
283
	bool Cell::TestUniteCells(const ElementArray<Cell> & unite, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
284
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
285
286
287
		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
288
		bool doexit = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
289
290
		MarkerType hm = m->HideMarker();			
		for(ElementArray<Cell>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
291
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
292
293
294
295
			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
296
297
		}
		if( doexit ) return false;
Kirill Terekhov's avatar
Kirill Terekhov committed
298
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
299
300
301
302
		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
303
304
			if( it->second != 1 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
305
306
307
308
309
				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
310
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
311
312
						m->SetMarker(lc[jt],rem);
						edges.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
313
314
					}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
315
316
		}
		for(dynarray<HandleType,64>::size_type i = 0; i < edges.size(); i++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
317
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
318
319
320
			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
321
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
322
				if( !m->GetMarker(lc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
323
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
324
325
					m->SetMarker(lc[jt],rem);
					nodes.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
326
327
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
328
329
330
331
332
333
334
335
336
			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
337
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
338
		for(dynarray<HandleType,64>::size_type i = 0; i < nodes.size(); i++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
339
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
340
341
			m->RemMarker(nodes[i],rem);
			if( m->GetMarker(nodes[i],del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
342
343
			{
				int nonzero = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
344
345
346
347
				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
348
349
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
350
351
352
		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
353
354
355
356
357
358
		m->ReleaseMarker(rem);
		if( doexit ) return false;
		return true;
	}
	
	
Kirill Terekhov's avatar
Kirill Terekhov committed
359
	Face Face::UniteFaces(ElementArray<Face> & unite, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
360
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
361
362
		Mesh * m = unite.GetMeshLink();
		if( unite.empty() ) return Face(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
363
		MarkerType hm = m->HideMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
364
		bool doexit = false, dothrow = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
365
366
367
368
		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
369
370
		MarkerType edge_set = m->CreateMarker();
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
371
372
		
		
Kirill Terekhov's avatar
Kirill Terekhov committed
373
374
375
376
377
378
		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
379
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
380
381
					high_conn_set.push_back(hc[it]);
					m->SetMarker(hc[it],edge_set);
Kirill Terekhov's avatar
Kirill Terekhov committed
382
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
383
384
			}
		}		
Kirill Terekhov's avatar
Kirill Terekhov committed
385
386
		
		
Kirill Terekhov's avatar
Kirill Terekhov committed
387
388
		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
389
390
391
392
393
394
395
396
397
		
		
		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
398
399
400
401
		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
402
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
403
404
405
			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
406
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
407
408
409
		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
410
411
412
		{
			if( it->second == 1 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
413
414
				m->SetMarker(it->first,edge_set);
				if( first == InvalidHandle() ) first = it->first;
Kirill Terekhov's avatar
Kirill Terekhov committed
415
416
417
			}
			else if( it->second == 2 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
418
419
420
421
422
423
				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
424
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
425
426
						m->SetMarker(lc[jt],edge_set);
						nodes.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
427
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
428
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
429
430
431
432
433
434
435
436
			}
			else 
			{
				doexit = true; //the faces we unite would not appear as one surface
				dothrow = true;
			}
		}
		
Kirill Terekhov's avatar
Kirill Terekhov committed
437
		for(dynarray<HandleType,64>::size_type j = 0; j < nodes.size(); j++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
438
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
439
440
			m->RemMarker(nodes[j],edge_set);
			if( m->GetMarker(nodes[j],del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
441
442
			{
				int nonzero = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
443
444
445
				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
446
447
448
449
450
451
452
				if( nonzero == 0 ) //all edges are deleted but the node is protected
					doexit = true;
			}
		}
			
		if( doexit )
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
453
454
455
456
457
			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
458
459
			m->ReleaseMarker(edge_set);
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
460
461
			assert( !dothrow ); //report the situation, because user need to debug the input
			return Face(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
462
463
464
465
466
467
468
		}
		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
469
			enumerator k1 = ENUMUNDEF,k2;
Kirill Terekhov's avatar
Kirill Terekhov committed
470
			adj_type const & lc = m->LowConn(edges.atback());
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
471
472
			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
473
474
			if( lc[k1] != prev ) 
				prev = lc[k1]; 
Kirill Terekhov's avatar
Kirill Terekhov committed
475
			else 
Kirill Terekhov's avatar
Kirill Terekhov committed
476
				prev = lc[k2];
Kirill Terekhov's avatar
Kirill Terekhov committed
477
			bool found = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
478
479
			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
480
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
481
				if( hc[it] == first && q != 0)
Kirill Terekhov's avatar
Kirill Terekhov committed
482
483
484
485
				{
					found = done = true;
					break;
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
486
				if( m->GetMarker(hc[it],edge_set) )
Kirill Terekhov's avatar
Kirill Terekhov committed
487
488
489
				{
					q++;
					found = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
490
491
					edges.push_back(hc[it]);
					m->RemMarker(hc[it],edge_set);
Kirill Terekhov's avatar
Kirill Terekhov committed
492
493
494
					break;
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
495
496
			assert(found);
			//if( !found ) throw Failure;
Kirill Terekhov's avatar
Kirill Terekhov committed
497
498
499
500
501
502
		}
		m->ReleaseMarker(edge_set);
		
		

		
Kirill Terekhov's avatar
Kirill Terekhov committed
503
504
		for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++)
			m->SetMarker(unite.at(j),rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
505
		
Kirill Terekhov's avatar
Kirill Terekhov committed
506
507
508
		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
509
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
510
511
512
513
514
				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
515
516
					else jt++;
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
517
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
518
		
Kirill Terekhov's avatar
Kirill Terekhov committed
519
520
521
		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
522
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
523
			for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++) // delete all faces
Kirill Terekhov's avatar
Kirill Terekhov committed
524
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
525
526
527
528
				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
529
530
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
531
532

		for(tiny_map<HandleType,int,64>::iterator it = edge_visit.begin(); it != edge_visit.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
533
534
			if( it->second != 1 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
535
536
537
538
539
				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
540
541
542
543
			}
			
		m->ReleaseMarker(rem);

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

Kirill Terekhov's avatar
Kirill Terekhov committed
672
	Edge Edge::UniteEdges(ElementArray<Edge> & edges, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
673
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
674
675
676
		Mesh * m = edges.GetMeshLink();
		if( edges.size() == 0 ) return Edge(m,InvalidHandle());
		
Kirill Terekhov's avatar
Kirill Terekhov committed
677
		bool doexit = false, dothrow = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
678
679
		MarkerType hm = m->HideMarker();
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
680
681
682
683
684
		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
685
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
686
			if( m->GetMarker(edges.at(it),del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
687
				doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
688
689
			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
690
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
691
				if( !m->GetMarker(hc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
692
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
693
694
					high_conn_faces.push_back(hc[jt]);
					m->SetMarker(hc[jt],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
695
696
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
697
698
699
			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
700
701
		}
		
Kirill Terekhov's avatar
Kirill Terekhov committed
702
		for(dynarray<HandleType,64>::size_type it = 0; it < high_conn_faces.size(); ++it) 
Kirill Terekhov's avatar
Kirill Terekhov committed
703
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
704
705
706
707
708
			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
709
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
710
711
					m->SetMarker(hc[jt],rem);
					cells.push_back(hc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
712
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
713
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
714
715
716
717
718
		}

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

		if( doexit )
		{
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
741
742
743
			assert(!dothrow);
			//if( dothrow ) throw Impossible; // bad input
			return Edge(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
744
745
746
		}


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

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

Kirill Terekhov's avatar
Kirill Terekhov committed
751
752
753
754
755
756
		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
757
758
				{
					//all united edges should appear in consecutive order in deleted face
Kirill Terekhov's avatar
Kirill Terekhov committed
759
760
					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
761
762
763
					{
						sum++; j++;
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
764
					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
765
766
767
768
769
770
771
					{
						doexit = true;
						dothrow = true;
					}
					insert_pos.push_back(k);
					break;
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
772
773
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
774
775
776

		if( doexit )
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
777
			for(ElementArray<Edge>::size_type it = 0; it < edges.size(); ++it) m->RemMarker(edges.at(it),rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
778
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
779
780
781
			assert(!dothrow);
			//if( dothrow ) throw Impossible; // bad input
			return Edge(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
782
783
		}

Kirill Terekhov's avatar
Kirill Terekhov committed
784
		if( !m->HideMarker() ) //disconnect if cannot hide
Kirill Terekhov's avatar
Kirill Terekhov committed
785
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
786
			for(dynarray<HandleType,64>::size_type it = 0; it < high_conn_faces.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
787
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
788
789
790
				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
791
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
792
793
					if( m->GetMarker(*jt,rem) )
						jt = lc.erase(jt);
Kirill Terekhov's avatar
Kirill Terekhov committed
794
795
796
797
798
799
					else ++jt;
				}
			}
		}


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

		m->ReleaseMarker(rem);

Kirill Terekhov's avatar
Kirill Terekhov committed
812
813
		for(tiny_map<HandleType,int,64>::iterator it = nodes.begin(); it != nodes.end(); it++)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
814
815
			if( it->second != 1 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
816
				if( !m->Hide(it->first) ) //cannot hide, we have to untie cells from nodes
Kirill Terekhov's avatar
Kirill Terekhov committed
817
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
818
819
					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
820
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
821
822
823
						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
824
825
						{
							if( *jt == it->first )
Kirill Terekhov's avatar
Kirill Terekhov committed
826
								jt = hc.erase(jt); //erase link to node
Kirill Terekhov's avatar
Kirill Terekhov committed
827
828
829
							else ++jt;
						}
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
830
					m->Destroy(it->first);
Kirill Terekhov's avatar
Kirill Terekhov committed
831
832
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
833
834
835
836
		}
			
		Edge e = m->CreateEdge(build_nodes).first;
		adj_type & ehc = m->HighConn(e->GetHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
837

Kirill Terekhov's avatar
Kirill Terekhov committed
838
		for(dynarray<adj_type::size_type,64>::size_type k = 0; k < insert_pos.size(); k++)
Kirill Terekhov's avatar
Kirill Terekhov committed
839
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
840
841
842
843
			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
844
845
846
			m->RecomputeGeometricData(high_conn_faces[k]);
		}

Kirill Terekhov's avatar
Kirill Terekhov committed
847
		for(dynarray<HandleType,64>::size_type it = 0; it < cells.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
848
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
849
850
			m->ComputeGeometricType(cells[it]);
			m->RecomputeGeometricData(cells[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
851
852
853
854
855
		}


		return e;
	}
Kirill Terekhov's avatar
Kirill Terekhov committed
856
	bool Edge::TestUniteEdges(const ElementArray<Edge> & edges, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
857
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
858
859
		if( edges.empty() ) return false;
		Mesh * m = edges.GetMeshLink();
Kirill Terekhov's avatar
Kirill Terekhov committed
860
		bool doexit = false, dothrow = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
861
862
		MarkerType hm = m->HideMarker();
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
863
864
865
866
		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
867
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
868
			if( m->GetMarker(edges.at(it),del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
869
				doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
870
871
			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
872
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
873
				if( !m->GetMarker(hc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
874
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
875
876
					high_conn_faces.push_back(hc[jt]);
					m->SetMarker(hc[jt],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
877
878
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
879
880
881
			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
882
883
		}
		
Kirill Terekhov's avatar
Kirill Terekhov committed
884
885
		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
886
887
888
889
890
891
892

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

		if( doexit )
		{
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
914
915
			assert(!dothrow); //inner loop in deleted edges
			//if( dothrow ) throw Impossible; // bad input
Kirill Terekhov's avatar
Kirill Terekhov committed
916
917
918
919
920
			return false;
		}



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

Kirill Terekhov's avatar
Kirill Terekhov committed
923
924
925
926
927
928
		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
929
930
				{
					//all united edges should appear in consecutive order in deleted face
Kirill Terekhov's avatar
Kirill Terekhov committed
931
932
					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
933
934
935
					{
						sum++; j++;
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
936
					if( sum != static_cast<adj_type::size_type>(edges.size()) )
Kirill Terekhov's avatar
Kirill Terekhov committed
937
938
939
940
941
942
					{
						doexit = true;
						dothrow = true;
					}
					break;
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
943
944
945
			}
		}
		for(ElementArray<Edge>::size_type it = 0; it < edges.size(); ++it) m->RemMarker(edges.at(it),rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
946
947
948
949

		if( doexit )
		{
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
950
951
			assert(!dothrow);
			//if( dothrow ) throw Impossible; // bad input
Kirill Terekhov's avatar
Kirill Terekhov committed
952
953
954
955
956
957
958
			return false;
		}

		return true;
	}


Kirill Terekhov's avatar
Kirill Terekhov committed
959
	ElementArray<Edge> Edge::SplitEdge(Edge e, const ElementArray<Node> & nodes, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
960
961
	{
		Mesh * m = e->GetMeshLink();
Kirill Terekhov's avatar
Kirill Terekhov committed
962
963
964
965
966
967
		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
968
969
		MarkerType hm = m->HideMarker();
		MarkerType dup = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
970
971
972
		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
973
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
974
975
976
977
978
			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
979
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
980
981
					cells.push_back(ihc[jt]);
					m->SetMarker(ihc[jt],dup);
Kirill Terekhov's avatar
Kirill Terekhov committed
982
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
983
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
984
985
		}

Kirill Terekhov's avatar
Kirill Terekhov committed
986
987
		for(dynarray<HandleType,128>::size_type it = 0; it < cells.size(); ++it)
			m->RemMarker(cells[it],dup);
Kirill Terekhov's avatar
Kirill Terekhov committed
988
989
990
991
992

		m->ReleaseMarker(dup);

		int k = 0;

Kirill Terekhov's avatar
Kirill Terekhov committed
993
994
995
996
997
		adj_type const & lc = m->LowConn(e->GetHandle());