modify.cpp 74.3 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
#if defined(USE_MESH)

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

9 10
using namespace std;

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

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

	void Edge::SwapEnds()
	{
		Mesh * m = GetMeshLink();
		MarkerType hm = m->HideMarker();
36 37
		adj_type & lc = m->LowConn(GetHandle());
		if( m->Count(lc.data(),static_cast<enumerator>(lc.size()),hm) == 2 )
38 39
		{
			enumerator k1 = ENUMUNDEF, k2;
40 41 42 43 44 45 46 47
			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;
48 49
		}
	}
Kirill Terekhov's avatar
Kirill Terekhov committed
50
	
Kirill Terekhov's avatar
Kirill Terekhov committed
51
	void Element::Disconnect(bool del_upper) const
Kirill Terekhov's avatar
Kirill Terekhov committed
52
	{
53
		
Kirill Terekhov's avatar
Kirill Terekhov committed
54 55
		dynarray<adj_type::size_type,64> del;
		Mesh * m = GetMeshLink();
Kirill Terekhov's avatar
Kirill Terekhov committed
56 57 58 59
		//BEGIN NEW CODE - CHECK
		//Reorder face edges, so that they always apear in right direction
		if( GetElementType() == CELL ) //This is a cell
		{
60 61
			getAsCell()->SwapBackCell();
			/*
Kirill Terekhov's avatar
Kirill Terekhov committed
62
			MarkerType hm = m->HideMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
63
			adj_type & lc = m->LowConn(GetHandle());
64
			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
65
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
66
				adj_type & hc = m->HighConn(lc[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
67
				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
68
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
69 70
					enumerator k1 = ENUMUNDEF, k2;
					k1 = m->getNext(hc.data(),static_cast<enumerator>(hc.size()),k1,hm);
Kirill Terekhov's avatar
Kirill Terekhov committed
71
					if( hc[k1] == GetHandle() ) //the first cell is current
Kirill Terekhov's avatar
Kirill Terekhov committed
72
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
73
						k2 = m->getNext(hc.data(),static_cast<enumerator>(hc.size()),k1,hm);
Kirill Terekhov's avatar
Kirill Terekhov committed
74 75 76 77
						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
78 79 80
					}
				}
			}
81
			*/
Kirill Terekhov's avatar
Kirill Terekhov committed
82 83
		}
		//END NEW CODE - CHECK
Kirill Terekhov's avatar
Kirill Terekhov committed
84
		adj_type & hc = m->HighConn(GetHandle());
85
		adj_type::size_type i = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
86
		for( adj_type::size_type it = 0; it < hc.size(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
87 88
		{
			int flag = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
89 90 91
			adj_type & ilc = m->LowConn(hc[it]);
			adj_type::iterator jt = ilc.begin();
			while (jt != ilc.end())
Kirill Terekhov's avatar
Kirill Terekhov committed
92
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
93
				if(*jt == GetHandle())
Kirill Terekhov's avatar
Kirill Terekhov committed
94 95
				{
					flag = 1;
Kirill Terekhov's avatar
Kirill Terekhov committed
96
					jt = ilc.erase(jt);
Kirill Terekhov's avatar
Kirill Terekhov committed
97 98 99 100 101 102 103 104 105 106
				}
				else ++jt;
			}
			if( flag ) del.push_back(i);
			i++;
		}
		if( del_upper )
		{
			if( GetElementType() < CELL ) 
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
107 108 109
				if( Hidden() ) 
				{
					for(dynarray<adj_type::size_type,64>::iterator it = del.begin(); it != del.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
110
						if( m->GetMarker(hc[*it],m->HideMarker()) ) m->Delete(hc[*it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
111 112 113 114
				}
				else 
				{
					for(dynarray<adj_type::size_type,64>::iterator it = del.begin(); it != del.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
115
						m->Delete(hc[*it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
116
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
117 118
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
119 120 121
		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
122
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
123 124 125
			adj_type & ihc = m->HighConn(lc[it]);
			adj_type::iterator jt = ihc.begin();
			while (jt != ihc.end())
Kirill Terekhov's avatar
Kirill Terekhov committed
126
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
127
				if(*jt == GetHandle()) jt = ihc.erase(jt);
Kirill Terekhov's avatar
Kirill Terekhov committed
128 129 130
				else ++jt;
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
131
		lc.clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
132 133
	}
	
Kirill Terekhov's avatar
Kirill Terekhov committed
134
	Cell Cell::UniteCells(const ElementArray<Cell> & unite, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
135
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
136 137 138 139 140
		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
141
		bool doexit = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
142
		MarkerType hm = m->HideMarker();
143 144
		//Compute which faces of the provided cells lay on boundary (1 visit) and
		//inside of the set of cells (2 visits)
Kirill Terekhov's avatar
Kirill Terekhov committed
145
		for(ElementArray<Cell>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
146
		{
147 148
			if( unite[j]->GetMarker(del_protect) ) doexit = true;
			//access faces
Kirill Terekhov's avatar
Kirill Terekhov committed
149
			adj_type const & lc = m->LowConn(unite.at(j));
150 151
			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
152
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
153
		if( doexit ) return Cell(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
154
		MarkerType visited = m->CreateMarker(), rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
155 156
		dynarray<HandleType,64> edges;
		dynarray<HandleType,64> nodes;
157 158 159
		//gather boundary faces into set that will be used to create new cell
		//mark internal faces to be deleted. For internal faces find out
		//all internal edges that should be deleted as well.
Kirill Terekhov's avatar
Kirill Terekhov committed
160 161
		for(tiny_map<HandleType,int,64>::iterator it = face_visit.begin(); it != face_visit.end(); it++)
		{
162
			if( it->second == 1 ) //boundary faces, use for new cell
Kirill Terekhov's avatar
Kirill Terekhov committed
163
				faces.push_back(it->first);
164
			else //internal faces
Kirill Terekhov's avatar
Kirill Terekhov committed
165
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
166
				if( m->GetMarker(it->first,del_protect) ) doexit = true;
167
				//mark face to be deleted
Kirill Terekhov's avatar
Kirill Terekhov committed
168
				m->SetMarker(it->first,rem);
169
				//access edges of the face, gather into array
Kirill Terekhov's avatar
Kirill Terekhov committed
170 171 172
				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
173
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
174 175
						m->SetMarker(lc[jt],visited);
						edges.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
176
					}
177
				//gather internal faces
Kirill Terekhov's avatar
Kirill Terekhov committed
178 179
				inner_faces.push_back(it->first);
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
180
		}
181 182 183
		//for edges of internal faces gather their nodes,
		//for each edge check if all it's faces are to be deleted,
		//then the edge should be deleted, otherwise keep the edge
Kirill Terekhov's avatar
Kirill Terekhov committed
184
		for(dynarray<HandleType,64>::size_type i = 0; i < edges.size(); i++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
185
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
186
			m->RemMarker(edges[i],visited);
187
			//access nodes of the edge, gather into array
Kirill Terekhov's avatar
Kirill Terekhov committed
188 189
			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
190
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
191
				if( !m->GetMarker(lc[jt],visited) )
Kirill Terekhov's avatar
Kirill Terekhov committed
192
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
193 194
					m->SetMarker(lc[jt],visited);
					nodes.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
195 196
				}
			}
197 198
			//access faces of the edge, check is there any
			//face that would not be deleted
Kirill Terekhov's avatar
Kirill Terekhov committed
199 200 201 202 203 204
			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
			{
205
				//mark edge to be deleted
Kirill Terekhov's avatar
Kirill Terekhov committed
206 207 208
				m->SetMarker(edges[i],rem);
				if( m->GetMarker(edges[i],del_protect) ) doexit = true;
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
209
		}
210 211
		//for nodes of internal faces check is there any edges
		//that should not be deleted
Kirill Terekhov's avatar
Kirill Terekhov committed
212
		for(dynarray<HandleType,64>::size_type i = 0; i < nodes.size(); i++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
213
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
214
			m->RemMarker(nodes[i],visited);
215 216 217 218 219 220 221
			int nonzero = 0;
			//acces edges of the node, check is there any
			//edge that would not be deleted
			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 ) //all edges should be deleted, node to remove
Kirill Terekhov's avatar
Kirill Terekhov committed
222
			{
223 224 225
				//mark node to be deleted
				m->SetMarker(nodes[i],rem);
				if( m->GetMarker(nodes[i],del_protect) ) doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
226 227 228
			}
		}
		m->ReleaseMarker(visited);
229 230
		if( doexit )
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
231 232 233
			m->RemMarkerArray(inner_faces.data(),(enumerator)inner_faces.size(),rem);
			m->RemMarkerArray(edges.data(), (enumerator)edges.size(), rem);
			m->RemMarkerArray(nodes.data(), (enumerator)nodes.size(), rem);
234 235 236
			m->ReleaseMarker(rem);
			return Cell(m,InvalidHandle());
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
237
		//delete cells
Kirill Terekhov's avatar
Kirill Terekhov committed
238
		for(ElementArray<Cell>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
239
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
240 241
			if( m->GetMarker(unite.at(j),del_protect) )
				std::cout << __FUNCTION__ << " deleted protected cells, united " << unite.size() << " cells " << std::endl;
242 243 244 245
			if( m->HideMarker() )
				m->Hide(unite.at(j));
			else
				m->Delete(unite.at(j));
Kirill Terekhov's avatar
Kirill Terekhov committed
246 247
		}
		//delete inner faces
Kirill Terekhov's avatar
Kirill Terekhov committed
248
		for(dynarray<HandleType,64>::size_type j = 0; j < inner_faces.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
249
		{
250
			//std::cout << "delete face " << GetHandleID(inner_faces[j]) << std::endl;
251 252 253 254 255 256 257 258 259 260
			if( m->GetMarker(inner_faces[j],rem) )
			{
				m->RemMarker(inner_faces[j],rem);
				if( m->GetMarker(inner_faces[j],del_protect) )
					std::cout << __FUNCTION__ << " deleted protected faces, united " << unite.size() << " cells " << std::endl;
				if( m->HideMarker() )
					m->Hide(inner_faces[j]);
				else
					m->Delete(inner_faces[j]);
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
261
		}
262 263
		//delete unused edges
		for(dynarray<HandleType,64>::size_type j = 0; j < edges.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
264
		{
265
			if( m->GetMarker(edges[j],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
266
			{
267
				m->RemMarker(edges[j],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
268 269
				if( m->GetMarker(edges[j],del_protect) )
					std::cout << __FUNCTION__ << " deleted protected edge, united " << unite.size() << " cells " << std::endl;
270 271 272 273
				if( m->HideMarker() )
					m->Hide(edges[j]);
				else
					m->Delete(edges[j]);
Kirill Terekhov's avatar
Kirill Terekhov committed
274
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
275
		}
276 277
		//delete unused nodes
		for(dynarray<HandleType,64>::size_type j = 0; j < nodes.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
278 279
		{

280
			if( m->GetMarker(nodes[j],rem) ) //there are no edges that use this edge
Kirill Terekhov's avatar
Kirill Terekhov committed
281
			{
282
				m->RemMarker(nodes[j],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
283 284 285 286
				// 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;
287 288 289 290
				if( m->HideMarker() )
					m->Hide(nodes[j]);
				else
					m->Delete(nodes[j]);
Kirill Terekhov's avatar
Kirill Terekhov committed
291 292 293 294
				//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
295 296
					//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
297
					//{
Kirill Terekhov's avatar
Kirill Terekhov committed
298 299
					//	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
300 301
					//	{
					//		if( *jt == nodes[j] )
Kirill Terekhov's avatar
Kirill Terekhov committed
302
					//			jt = (*it)->HighConn().erase(jt); //erase link to node
Kirill Terekhov's avatar
Kirill Terekhov committed
303 304 305 306 307 308 309 310
					//		else ++jt;
					//	}
					//  ++it;
					//}
					//nodes[j]->Disconnect();
					//nodes[j]->Delete();
				//}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
311
		}
312
		m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
313
		//reconstruct cell by outer faces
Kirill Terekhov's avatar
Kirill Terekhov committed
314
		return m->CreateCell(faces).first;
Kirill Terekhov's avatar
Kirill Terekhov committed
315 316 317
	}
	
	
Kirill Terekhov's avatar
Kirill Terekhov committed
318
	bool Cell::TestUniteCells(const ElementArray<Cell> & unite, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
319
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
320 321 322
		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
323
		bool doexit = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
324 325
		MarkerType hm = m->HideMarker();			
		for(ElementArray<Cell>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
326
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
327 328 329 330
			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
331 332
		}
		if( doexit ) return false;
Kirill Terekhov's avatar
Kirill Terekhov committed
333
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
334 335 336 337
		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
338 339
			if( it->second != 1 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
340 341 342 343 344
				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
345
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
346 347
						m->SetMarker(lc[jt],rem);
						edges.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
348 349
					}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
350 351
		}
		for(dynarray<HandleType,64>::size_type i = 0; i < edges.size(); i++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
352
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
353 354 355
			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
356
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
357
				if( !m->GetMarker(lc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
358
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
359 360
					m->SetMarker(lc[jt],rem);
					nodes.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
361 362
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
363
			int nonzero = 0;
364 365
			//access faces of the edge, check is there any
			//that would not be deleted
Kirill Terekhov's avatar
Kirill Terekhov committed
366 367 368
			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
369 370 371
			//all faces should be deleted, edge to remove
			if( nonzero == 0 && m->GetMarker(edges[i],del_protect) )
				doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
372
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
373
		for(dynarray<HandleType,64>::size_type i = 0; i < nodes.size(); i++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
374
		{
375 376 377 378 379 380 381 382 383
			int nonzero = 0;
			//access edges of the node, check is there
			//any that would not be deleted
			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++;
			//all edges should be deleted, node to remove
			if( nonzero == 0 && m->GetMarker(edges[i],del_protect) )
				doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
384
		}
385
		for(tiny_map<HandleType,int,64>::iterator it = face_visit.begin(); it != face_visit.end(); it++) m->RemMarker(it->first,rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
386 387
		m->RemMarkerArray(edges.data(), (enumerator)edges.size(),rem);
		m->RemMarkerArray(nodes.data(), (enumerator)nodes.size(), rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
388 389 390 391 392 393
		m->ReleaseMarker(rem);
		if( doexit ) return false;
		return true;
	}
	
	
Kirill Terekhov's avatar
Kirill Terekhov committed
394
	Face Face::UniteFaces(const ElementArray<Face> & unite, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
395
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
396
		Mesh * m = const_cast<Mesh *>(unite.GetMeshLink());
397
		assert(m != NULL);
Kirill Terekhov's avatar
Kirill Terekhov committed
398
		if( unite.empty() ) return Face(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
399
		MarkerType hm = m->HideMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
400
		bool doexit = false, dothrow = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
401 402 403
		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());
404
		dynarray<HandleType,64> cells;
Kirill Terekhov's avatar
Kirill Terekhov committed
405 406
		MarkerType edge_set = m->CreateMarker();
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
407
		
408
		//gather cells adjacent to united faces
Kirill Terekhov's avatar
Kirill Terekhov committed
409 410 411 412 413 414
		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
415
				{
416
					cells.push_back(hc[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
417
					m->SetMarker(hc[it],edge_set);
Kirill Terekhov's avatar
Kirill Terekhov committed
418
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
419
			}
420
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
421
		m->RemMarkerArray(cells.data(), (enumerator)cells.size(), edge_set);
422 423 424 425
		assert(cells.size() <= 2);
		//check is there a topological problem
		//new face should be adjacent to no more then two cells
		if( m->GetTopologyCheck(TRIPLE_SHARED_FACE) && cells.size() > 2 )
Kirill Terekhov's avatar
Kirill Terekhov committed
426 427 428 429 430 431
		{
			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
432 433 434
		dynarray<HandleType,64> nodes;
		tiny_map<HandleType, int,64> edge_visit;
		ElementArray<Edge> edges(m);
435
		//compute how many times each edge is visited
Kirill Terekhov's avatar
Kirill Terekhov committed
436
		for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
437
		{
438
			//access edges of the face
Kirill Terekhov's avatar
Kirill Terekhov committed
439
			adj_type const & lc = m->LowConn(unite.at(j));
440 441
			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
442
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
443 444
		HandleType first = InvalidHandle(); //first edge
		HandleType prev = InvalidHandle(); //prev node
445 446 447
		//Mark all the edges on boundary to recreate the face,
		//assemble set of nodes
		int expect_q = 0; //used to test for consistency of the loop of edges
Kirill Terekhov's avatar
Kirill Terekhov committed
448
		for(tiny_map<HandleType,int,64>::iterator it = edge_visit.begin(); it != edge_visit.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
449 450 451
		{
			if( it->second == 1 )
			{
452
				expect_q++;
Kirill Terekhov's avatar
Kirill Terekhov committed
453 454
				m->SetMarker(it->first,edge_set);
				if( first == InvalidHandle() ) first = it->first;
Kirill Terekhov's avatar
Kirill Terekhov committed
455 456 457
			}
			else if( it->second == 2 )
			{
458 459 460
				//edge is protected
				if( m->GetMarker(it->first,del_protect) ) doexit = true;
				//mark edge to be deleted
Kirill Terekhov's avatar
Kirill Terekhov committed
461
				m->SetMarker(it->first,rem);
462
				//access nodes of the edge
Kirill Terekhov's avatar
Kirill Terekhov committed
463 464 465 466
				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
467
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
468 469
						m->SetMarker(lc[jt],edge_set);
						nodes.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
470
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
471
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
472 473 474 475 476 477 478
			}
			else 
			{
				doexit = true; //the faces we unite would not appear as one surface
				dothrow = true;
			}
		}
479
		//Find out set of nodes to be deleted
Kirill Terekhov's avatar
Kirill Terekhov committed
480
		for(dynarray<HandleType,64>::size_type j = 0; j < nodes.size(); j++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
481
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
482
			m->RemMarker(nodes[j],edge_set);
483 484 485 486 487 488 489
			int nonzero = 0;
			//access edges of the nodes, find out whether all
			//of them are deleted
			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
			if( nonzero == 0 ) //all edges are deleted but the node is protected
Kirill Terekhov's avatar
Kirill Terekhov committed
490
			{
491 492
				m->SetMarker(nodes[j],rem);
				if( m->GetMarker(nodes[j],del_protect) ) doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
493 494 495 496 497
			}
		}
			
		if( doexit )
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
498 499
			for(tiny_map<HandleType,int,64>::iterator it = edge_visit.begin(); it != edge_visit.end(); it++)
			{
500 501 502
				m->RemMarker(it->first,rem);
				m->RemMarker(it->first,edge_set);
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
503
			m->RemMarkerArray(nodes.data(), (enumerator)nodes.size(), rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
504 505
			m->ReleaseMarker(edge_set);
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
506 507
			assert( !dothrow ); //report the situation, because user need to debug the input
			return Face(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
508
		}
509
		//Order edges on the boundary of united faces into loop
Kirill Terekhov's avatar
Kirill Terekhov committed
510 511 512
		edges.push_back(first);
		edges.back()->RemMarker(edge_set);
		bool done = false;
513
		int q = 1;
Kirill Terekhov's avatar
Kirill Terekhov committed
514 515
		while( !done )
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
516
			enumerator k1 = ENUMUNDEF,k2;
517
			//access nodes of the last pushed edge
Kirill Terekhov's avatar
Kirill Terekhov committed
518
			adj_type const & lc = m->LowConn(edges.atback());
519
			//find out first node
Kirill Terekhov's avatar
Kirill Terekhov committed
520
			k1 = m->getNext(lc.data(),static_cast<enumerator>(lc.size()),k1,hm);
521
			//find out second node
Kirill Terekhov's avatar
Kirill Terekhov committed
522
			k2 = m->getNext(lc.data(),static_cast<enumerator>(lc.size()),k1,hm);
523 524
			//find out which of the nodes should connect to the next edge
			//at the begining we can select any of the two
Kirill Terekhov's avatar
Kirill Terekhov committed
525 526
			if( lc[k1] != prev ) 
				prev = lc[k1]; 
Kirill Terekhov's avatar
Kirill Terekhov committed
527
			else 
Kirill Terekhov's avatar
Kirill Terekhov committed
528
				prev = lc[k2];
529 530
			//find out the next edge connected to the privious node
			bool found = false; //detect that edge was found, otherwise there is no loop
Kirill Terekhov's avatar
Kirill Terekhov committed
531 532
			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
533
			{
534 535
				//we came back to the first edge, the loop is closed
				if( hc[it] == first && q != 1)
Kirill Terekhov's avatar
Kirill Terekhov committed
536 537 538 539
				{
					found = done = true;
					break;
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
540
				if( m->GetMarker(hc[it],edge_set) )
Kirill Terekhov's avatar
Kirill Terekhov committed
541 542 543
				{
					q++;
					found = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
544 545
					edges.push_back(hc[it]);
					m->RemMarker(hc[it],edge_set);
Kirill Terekhov's avatar
Kirill Terekhov committed
546 547 548
					break;
				}
			}
549
			assert(found); //there is no loop
Kirill Terekhov's avatar
Kirill Terekhov committed
550
			//if( !found ) throw Failure;
Kirill Terekhov's avatar
Kirill Terekhov committed
551 552 553
		}
		m->ReleaseMarker(edge_set);
		
554 555
		//number of edges collected matches number of edges expected
		assert(expect_q == q);
Kirill Terekhov's avatar
Kirill Terekhov committed
556 557 558 559
		

		
		
Kirill Terekhov's avatar
Kirill Terekhov committed
560 561
		if( !m->HideMarker() ) //we can't hide elements
		{
562 563 564
			unite.SetMarker(rem);
			//untie every face from the cell
			for(dynarray<HandleType,64>::size_type it = 0; it < cells.size(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
565
			{
566
				adj_type & lc = m->LowConn(cells[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
567 568 569 570
				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
571 572
					else jt++;
			}
573
			unite.RemMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
574
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
575
		
576
		//delete old faces
Kirill Terekhov's avatar
Kirill Terekhov committed
577
		if( m->HideMarker() )
578 579
			for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++)
				m->Hide(unite.at(j));
Kirill Terekhov's avatar
Kirill Terekhov committed
580
		else
Kirill Terekhov's avatar
Kirill Terekhov committed
581
		{
582 583
			// delete all faces
			for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
584
			{
585 586
				//untie cells from face
				m->HighConn(unite.at(j)).clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
587 588 589
				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
590 591
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
592 593

		for(tiny_map<HandleType,int,64>::iterator it = edge_visit.begin(); it != edge_visit.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
594 595
			if( it->second != 1 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
596 597 598 599
				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;
600 601 602 603
				if( m->HideMarker() )
					m->Hide(it->first);
				else
					m->Delete(it->first);
Kirill Terekhov's avatar
Kirill Terekhov committed
604 605
			}
			
606
		
Kirill Terekhov's avatar
Kirill Terekhov committed
607

Kirill Terekhov's avatar
Kirill Terekhov committed
608
		for(dynarray<HandleType,64>::size_type it = 0; it < nodes.size(); it++) //delete nodes inside the face
Kirill Terekhov's avatar
Kirill Terekhov committed
609
		{
610
			//adj_type const & hc = m->HighConn(nodes[it]);
611
			if( m->GetMarker(nodes[it],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
612
			{
613 614 615
				assert( m->HighConn(nodes[it]).empty() || m->Count(m->HighConn(nodes[it]).data(),static_cast<integer>(m->HighConn(nodes[it]).size()),hm) == 0 );
				m->RemMarker(nodes[it],rem);
				if( !m->HideMarker() )
Kirill Terekhov's avatar
Kirill Terekhov committed
616
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
617 618 619
					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
620
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
621 622 623
						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
624
						{
Kirill Terekhov's avatar
Kirill Terekhov committed
625 626
							if( *qt == nodes[it] ) 
								qt = ihc.erase(qt); //remove links from the cell to the node
Kirill Terekhov's avatar
Kirill Terekhov committed
627 628 629 630
							else ++qt;
						}
						++jt;
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
631 632 633 634
					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
635
				}
636
				else m->Hide(nodes[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
637 638
			}
		}
639 640
		
		m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
641
				
Kirill Terekhov's avatar
Kirill Terekhov committed
642
		Face ret = m->CreateFace(edges).first;
Kirill Terekhov's avatar
Kirill Terekhov committed
643
		
644
		
Kirill Terekhov's avatar
Kirill Terekhov committed
645
		assert( ret->GetGeometricType() != MultiLine );
Kirill Terekhov's avatar
Kirill Terekhov committed
646
		
647
		
Kirill Terekhov's avatar
Kirill Terekhov committed
648
		adj_type & hc = m->HighConn(ret->GetHandle());
649
		for(dynarray<HandleType,64>::size_type it = 0; it < cells.size(); it++)  //tie new face to old cells
Kirill Terekhov's avatar
Kirill Terekhov committed
650
		{
651 652
			hc.push_back(cells[it]); // connect new face to cells
			m->LowConn(cells[it]).push_back(ret.GetHandle()); // connect cells to new face
Kirill Terekhov's avatar
Kirill Terekhov committed
653 654
			
		}
655 656 657
		
		
		for(dynarray<HandleType,64>::size_type it = 0; it < cells.size(); it++)  //tie new face to old cells
Kirill Terekhov's avatar
Kirill Terekhov committed
658
		{
659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674
			assert(m->Count(m->LowConn(cells[it]).data(),m->LowConn(cells[it]).size(),hm) >= 4);
			//compute geometric data
			m->ComputeGeometricType(cells[it]);
			assert(m->GetGeometricType(cells[it]) != MultiPolygon);
			//change nodes of the cell according to ordering
			ElementArray<Node> nodes(m);
			m->RestoreCellNodes(cells[it],nodes);
			adj_type & hc = m->HighConn(cells[it]);
			assert(nodes.size() == m->Count(hc.data(),hc.size(),hm));
			//should keep hidden nodes of the cell
			//todo: think about how we should order them
			for(adj_type::size_type k = 0; k < hc.size(); ++k)
				if( m->Hidden(hc[k]) ) nodes.push_back(hc[k]);
			hc.replace(hc.begin(),hc.end(),nodes.begin(),nodes.end());
			//recompute geometric data
			m->RecomputeGeometricData(cells[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
675 676 677 678 679 680
		}
		
		return ret;
	}
	
	
Kirill Terekhov's avatar
Kirill Terekhov committed
681
	bool Face::TestUniteFaces(const ElementArray<Face> & unite, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
682
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
683
		Mesh * m = const_cast<Mesh *>(unite.GetMeshLink());
Kirill Terekhov's avatar
Kirill Terekhov committed
684
		if( unite.size() == 0 ) return false;
Kirill Terekhov's avatar
Kirill Terekhov committed
685
		bool doexit = false, dothrow = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
686 687
		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
688
		MarkerType hm = m->HideMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
689
		if( doexit ) return false;
690
		dynarray<HandleType,64> cells;
Kirill Terekhov's avatar
Kirill Terekhov committed
691
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
692 693 694 695 696
		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
697
				{
698
					cells.push_back(hc[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
699
					m->SetMarker(hc[it],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
700
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
701
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
702
		m->RemMarkerArray(cells.data(), (enumerator)cells.size(), rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
703 704 705
		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
706
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
707 708 709
			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
710
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
711
		for(tiny_map<HandleType,int,64>::iterator it = edge_visit.begin(); it != edge_visit.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
712 713 714
		{
			if( it->second == 2 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
715 716 717 718 719 720
				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
721
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
722 723
						m->SetMarker(lc[jt],rem);
						nodes.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
724
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
725
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
726 727 728 729 730 731 732
			}
			else if( it->second != 1 )
			{
				doexit = true;
				dothrow = true;
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
733
		for(dynarray<HandleType,64>::size_type j = 0; j < nodes.size(); j++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
734
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
735
			m->RemMarker(nodes[j],rem);
736 737 738 739 740 741
			int nonzero = 0;
			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
			//all edges are deleted but the node is protected
			if( nonzero == 0 && m->GetMarker(nodes[j],del_protect)) doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
742
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
743 744
		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
745 746 747
		m->ReleaseMarker(rem);
		if( doexit )
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
748 749
			assert(!dothrow);
			//if( dothrow ) throw Impossible; //something went the way it shouldn't, possibly bad input
Kirill Terekhov's avatar
Kirill Terekhov committed
750 751 752 753 754
			return false;
		}
		return true;
	}

Kirill Terekhov's avatar
Kirill Terekhov committed
755
	Edge Edge::UniteEdges(const ElementArray<Edge> & edges, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
756
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
757
		Mesh * m = const_cast<Mesh *>(edges.GetMeshLink());
Kirill Terekhov's avatar
Kirill Terekhov committed
758 759
		if( edges.size() == 0 ) return Edge(m,InvalidHandle());
		
Kirill Terekhov's avatar
Kirill Terekhov committed
760
		bool doexit = false, dothrow = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
761 762
		MarkerType hm = m->HideMarker();
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
763
		dynarray<HandleType,64> cells;
764
		dynarray<HandleType,64> faces;
Kirill Terekhov's avatar
Kirill Terekhov committed
765 766 767
		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
768
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
769
			if( m->GetMarker(edges.at(it),del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
770
				doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
771 772
			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
773
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
774
				if( !m->GetMarker(hc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
775
				{
776
					faces.push_back(hc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
777
					m->SetMarker(hc[jt],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
778 779
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
780 781 782
			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
783 784
		}
		
785
		for(dynarray<HandleType,64>::size_type it = 0; it < faces.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
786
		{
787 788
			m->RemMarker(faces[it],rem);
			adj_type const & hc = m->HighConn(faces[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
789 790 791
			for(adj_type::size_type jt = 0; jt < hc.size(); ++jt)
			{
				if( !m->GetMarker(hc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
792
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
793 794
					m->SetMarker(hc[jt],rem);
					cells.push_back(hc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
795
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
796
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
797
		}
798
		
Kirill Terekhov's avatar
Kirill Terekhov committed
799
		m->RemMarkerArray(cells.data(), (enumerator)cells.size(), rem);
800 801
		
		
Kirill Terekhov's avatar
Kirill Terekhov committed
802 803 804 805

		if( doexit )
		{
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
806
			return Edge(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
807 808
		}
		
Kirill Terekhov's avatar
Kirill Terekhov committed
809
		for(tiny_map<HandleType,int,64>::iterator it = nodes.begin(); it != nodes.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
810
		{
811
			
Kirill Terekhov's avatar
Kirill Terekhov committed
812 813 814 815
			if( it->second == 1 )
				build_nodes.push_back(it->first);
			else if( it->second == 2 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
816
				if( m->GetMarker(it->first,del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
817 818 819 820
					doexit = true;
			}
			else 
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
821
				doexit = true; //edges have some loop
Kirill Terekhov's avatar
Kirill Terekhov committed
822 823 824
				dothrow = true;
			}
		}
825 826 827
		
		
		assert(build_nodes.size() == 2);
Kirill Terekhov's avatar
Kirill Terekhov committed
828 829 830 831

		if( doexit )
		{
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
832 833 834
			assert(!dothrow);
			//if( dothrow ) throw Impossible; // bad input
			return Edge(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
835 836 837
		}


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

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

843
		for(dynarray<HandleType,64>::size_type it = 0; it < faces.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
844
		{
845 846
			adj_type const & lc = m->LowConn(faces[it]); //edges of face
			bool found_rem = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
847 848 849
			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
850 851
				{
					//all united edges should appear in consecutive order in deleted face
Kirill Terekhov's avatar
Kirill Terekhov committed
852
					/*
Kirill Terekhov's avatar
Kirill Terekhov committed
853
					adj_type::size_type sum = 0, j = k;
Kirill Terekhov's avatar
Kirill Terekhov committed
854
					while( j < lc.size() && !m->GetMarker(lc[j],hm) && m->GetMarker(lc[j],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
855 856 857
					{
						sum++; j++;
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
858
					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
859 860 861 862
					{
						doexit = true;
						dothrow = true;
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
863
					 */
Kirill Terekhov's avatar
Kirill Terekhov committed
864
					insert_pos.push_back(k);
865
					found_rem = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
866 867
					break;
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
868
			}
869 870 871 872 873
			if( !found_rem )
			{
				doexit = true;
				dothrow = true;
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
874
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
875 876 877

		if( doexit )
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
878
			m->RemMarkerArray(edges.data(), (enumerator)edges.size(), rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
879
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
880 881 882
			assert(!dothrow);
			//if( dothrow ) throw Impossible; // bad input
			return Edge(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
883 884
		}

Kirill Terekhov's avatar
Kirill Terekhov committed
885
		if( !m->HideMarker() ) //disconnect if cannot hide
Kirill Terekhov's avatar
Kirill Terekhov committed
886
		{
887
			for(dynarray<HandleType,64>::size_type it = 0; it < faces.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
888
			{
889
				adj_type & lc = m->LowConn(faces[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
890 891
				adj_iterator jt = lc.begin(); //iterate over edges of faces
				while( jt != lc.end())
Kirill Terekhov's avatar
Kirill Terekhov committed
892
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
893 894
					if( m->GetMarker(*jt,rem) )
						jt = lc.erase(jt);
Kirill Terekhov's avatar
Kirill Terekhov committed
895 896 897 898 899 900
					else ++jt;
				}
			}
		}


Kirill Terekhov's avatar
Kirill Terekhov committed
901
		for(ElementArray<Edge>::size_type it = 0; it < edges.size(); ++it)//delete edges
Kirill Terekhov's avatar
Kirill Terekhov committed
902
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
903 904
			m->RemMarker(edges.at(it),rem);
			if( !m->Hide(edges.at(it)) ) //cannot hide
Kirill Terekhov's avatar
Kirill Terekhov committed
905
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
906 907
				m->HighConn(edges.at(it)).clear(); //remove connection from edge to faces
				m->Destroy(edges.at(it));
Kirill Terekhov's avatar
Kirill Terekhov committed
908 909 910 911 912
			}
		}

		m->ReleaseMarker(rem);

Kirill Terekhov's avatar
Kirill Terekhov committed
913 914
		for(tiny_map<HandleType,int,64>::iterator it = nodes.begin(); it != nodes.end(); it++)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
915 916
			if( it->second != 1 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
917
				if( !m->Hide(it->first) ) //cannot hide, we have to untie cells from nodes
Kirill Terekhov's avatar
Kirill Terekhov committed
918
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
919 920
					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
921
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
922 923 924
						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
925 926
						{
							if( *jt == it->first )
927
							{
Kirill Terekhov's avatar
Kirill Terekhov committed
928
								jt = hc.erase(jt); //erase link to node
929
							}
Kirill Terekhov's avatar
Kirill Terekhov committed
930 931 932
							else ++jt;
						}
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
933
					m->Destroy(it->first);
Kirill Terekhov's avatar
Kirill Terekhov committed
934 935
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
936 937 938 939
		}
			
		Edge e = m->CreateEdge(build_nodes).first;
		adj_type & ehc = m->HighConn(e->GetHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
940

Kirill Terekhov's avatar
Kirill Terekhov committed
941
		for(dynarray<adj_type::size_type,64>::size_type k = 0; k < insert_pos.size(); k++)
Kirill Terekhov's avatar
Kirill Terekhov committed
942
		{
943
			adj_type & lc = m->LowConn(faces[k]);
Kirill Terekhov's avatar
Kirill Terekhov committed
944
			lc.insert(lc.begin()+insert_pos[k],e->GetHandle());
945 946 947
			ehc.push_back(faces[k]);
			m->ComputeGeometricType(faces[k]);
			m->RecomputeGeometricData(faces[k]);
Kirill Terekhov's avatar
Kirill Terekhov committed
948 949
		}

Kirill Terekhov's avatar
Kirill Terekhov committed
950
		for(dynarray<HandleType,64>::size_type it = 0; it < cells.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
951
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
952
			m->ComputeGeometricType(cells[it]);
953 954 955 956 957 958 959 960 961 962 963
			//change nodes of the cell according to ordering
			ElementArray<Node> nodes(m);
			m->RestoreCellNodes(cells[it],nodes);
			adj_type & hc = m->HighConn(cells[it]);
			assert(nodes.size() == m->Count(hc.data(),hc.size(),hm));
			//should keep hidden nodes of the cell
			//todo: think about how we should order them
			for(adj_type::size_type k = 0; k < hc.size(); ++k)
				if( m->Hidden(hc[k]) ) nodes.push_back(hc[k]);
			hc.replace(hc.begin(),hc.end(),nodes.begin(),nodes.end());
			//update centroid, volume, orientation, etc
Kirill Terekhov's avatar
Kirill Terekhov committed
964
			m->RecomputeGeometricData(cells[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
965
		}
966 967
		
		
Kirill Terekhov's avatar
Kirill Terekhov committed
968 969 970

		return e;
	}
Kirill Terekhov's avatar
Kirill Terekhov committed
971
	bool Edge::TestUniteEdges(const ElementArray<Edge> & edges, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
972
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
973 974
		if( edges.empty() ) return false;
		Mesh * m = edges.GetMeshLink();
Kirill Terekhov's avatar
Kirill Terekhov committed
975
		bool doexit = false, dothrow = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
976 977
		MarkerType hm = m->HideMarker();
		MarkerType rem = m->CreateMarker();
978
		dynarray<HandleType,64> faces;
Kirill Terekhov's avatar
Kirill Terekhov committed
979 980 981
		tiny_map<HandleType,int,64> nodes;

		for(ElementArray<Edge>::size_type it = 0; it < edges.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
982
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
983
			if( m->GetMarker(edges.at(it),del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
984
				doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
985 986
			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
987
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
988
				if( !m->GetMarker(hc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
989
				{
990
					faces.push_back(hc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
991
					m->SetMarker(hc[jt],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
992 993
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
994 995 996
			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
997 998
		}
		
999 1000
		for(dynarray<HandleType,64>::size_type it = 0; it < faces.size(); ++it)
			m->RemMarker(faces[it],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
1001 1002 1003 1004 1005 1006 1007

		if( doexit )
		{
			m->ReleaseMarker(rem);
			return false;
		}
		
Kirill Terekhov's avatar
Kirill Terekhov committed
1008
		for(tiny_map<HandleType,int,64>::iterator it = nodes.begin(); it != nodes.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
1009 1010 1011 1012 1013 1014 1015
		{
			if( it->second == 1 )
			{
//				build_nodes.push_back(it->first);
			}
			else if( it->second == 2 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
1016
				if( m->GetMarker(it->first,del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028
					doexit = true;
			}
			else 
			{
				doexit = true;
				dothrow = true;
			}
		}

		if( doexit )
		{
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
1029 1030
			assert(!dothrow); //inner loop in deleted edges
			//if( dothrow ) throw Impossible; // bad input
Kirill Terekhov's avatar
Kirill Terekhov committed
1031 1032 1033 1034 1035
			return false;
		}



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

1038
		for(dynarray<HandleType,64>::size_type it = 0; it < faces.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
1039
		{
1040 1041
			adj_type const & lc = m->LowConn(faces[it]);
			bool found_rem = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
1042 1043 1044
			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
1045
				{
1046
					/*
Kirill Terekhov's avatar
Kirill Terekhov committed
1047
					//all united edges should appear in consecutive order in deleted face
Kirill Terekhov's avatar
Kirill Terekhov committed
1048 1049
					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
1050 1051 1052
					{
						sum++; j++;
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
1053
					if( sum != static_cast<adj_type::size_type>(edges.size()) )
Kirill Terekhov's avatar
Kirill Terekhov committed
1054 1055 1056 1057
					{
						doexit = true;
						dothrow = true;
					}