modify.cpp 72.5 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"
3
#include <queue>
Kirill Terekhov's avatar
Kirill Terekhov committed
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
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#if defined(USE_PARALLEL_WRITE_TIME)
#define REPORT_MPI(x) {WriteTab(out_time) << "<MPI><![CDATA[" << #x << "]]></MPI>" << std::endl; x;}
#define REPORT_STR(x) {WriteTab(out_time) << "<TEXT><![CDATA[" << x << "]]></TEXT>" << std::endl;}
#define REPORT_VAL(str,x) {WriteTab(out_time) << "<VALUE name=\"" << str << "\"> <CONTENT><![CDATA[" << x << "]]></CONTENT> <CODE><![CDATA[" << #x << "]]></CODE></VALUE>" << std::endl;}
#define ENTER_FUNC() double all_time = Timer(); {WriteTab(out_time) << "<FUNCTION name=\"" << __FUNCTION__ << "\" id=\"func" << func_id++ << "\">" << std::endl; Enter();}
#define EXIT_FUNC() {WriteTab(out_time) << "<TIME>" << Timer() - all_time << "</TIME>" << std::endl; Exit(); WriteTab(out_time) << "</FUNCTION>" << std::endl;}
#define EXIT_FUNC_DIE() {WriteTab(out_time) << "<TIME>" << -1 << "</TIME>" << std::endl; Exit(); WriteTab(out_time) << "</FUNCTION>" << std::endl;}
#else
#define REPORT_MPI(x) x
#define REPORT_STR(x) {}
#define REPORT_VAL(str,x) {}
#define ENTER_FUNC() {}
#define EXIT_FUNC() {}
#define EXIT_FUNC_DIE()  {}
#endif

Kirill Terekhov's avatar
Kirill Terekhov committed
25
26
27

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

Kirill Terekhov's avatar
Kirill Terekhov committed
29
	
30

31
32

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

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

		
		
Kirill Terekhov's avatar
Kirill Terekhov committed
543
544
		if( !m->HideMarker() ) //we can't hide elements
		{
545
546
547
			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
548
			{
549
				adj_type & lc = m->LowConn(cells[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
550
551
552
553
				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
554
555
					else jt++;
			}
556
			unite.RemMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
557
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
558
		
559
		//delete old faces
Kirill Terekhov's avatar
Kirill Terekhov committed
560
		if( m->HideMarker() )
561
562
			for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++)
				m->Hide(unite.at(j));
Kirill Terekhov's avatar
Kirill Terekhov committed
563
		else
Kirill Terekhov's avatar
Kirill Terekhov committed
564
		{
565
566
			// delete all faces
			for(ElementArray<Face>::size_type j = 0; j < unite.size(); j++)
Kirill Terekhov's avatar
Kirill Terekhov committed
567
			{
568
569
				//untie cells from face
				m->HighConn(unite.at(j)).clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
570
571
572
				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
573
574
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
575
576

		for(tiny_map<HandleType,int,64>::iterator it = edge_visit.begin(); it != edge_visit.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
577
578
			if( it->second != 1 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
579
580
581
582
				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;
583
584
585
586
				if( m->HideMarker() )
					m->Hide(it->first);
				else
					m->Delete(it->first);
Kirill Terekhov's avatar
Kirill Terekhov committed
587
588
			}
			
589
		
Kirill Terekhov's avatar
Kirill Terekhov committed
590

Kirill Terekhov's avatar
Kirill Terekhov committed
591
		for(dynarray<HandleType,64>::size_type it = 0; it < nodes.size(); it++) //delete nodes inside the face
Kirill Terekhov's avatar
Kirill Terekhov committed
592
		{
593
			//adj_type const & hc = m->HighConn(nodes[it]);
594
			if( m->GetMarker(nodes[it],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
595
			{
596
597
598
				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
599
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
600
601
602
					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
603
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
604
605
606
						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
607
						{
Kirill Terekhov's avatar
Kirill Terekhov committed
608
609
							if( *qt == nodes[it] ) 
								qt = ihc.erase(qt); //remove links from the cell to the node
Kirill Terekhov's avatar
Kirill Terekhov committed
610
611
612
613
							else ++qt;
						}
						++jt;
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
614
615
616
617
					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
618
				}
619
				else m->Hide(nodes[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
620
621
			}
		}
622
623
		
		m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
624
				
Kirill Terekhov's avatar
Kirill Terekhov committed
625
		Face ret = m->CreateFace(edges).first;
Kirill Terekhov's avatar
Kirill Terekhov committed
626
		
627
		
Kirill Terekhov's avatar
Kirill Terekhov committed
628
		assert( ret->GetGeometricType() != MultiLine );
Kirill Terekhov's avatar
Kirill Terekhov committed
629
		
630
		
Kirill Terekhov's avatar
Kirill Terekhov committed
631
		adj_type & hc = m->HighConn(ret->GetHandle());
632
		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
633
		{
634
635
			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
636
637
			
		}
638
639
640
		
		
		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
641
		{
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
			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
658
659
660
661
662
663
		}
		
		return ret;
	}
	
	
Kirill Terekhov's avatar
Kirill Terekhov committed
664
	bool Face::TestUniteFaces(const ElementArray<Face> & unite, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
665
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
666
		Mesh * m = const_cast<Mesh *>(unite.GetMeshLink());
Kirill Terekhov's avatar
Kirill Terekhov committed
667
		if( unite.size() == 0 ) return false;
Kirill Terekhov's avatar
Kirill Terekhov committed
668
		bool doexit = false, dothrow = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
669
670
		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
671
		MarkerType hm = m->HideMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
672
		if( doexit ) return false;
673
		dynarray<HandleType,64> cells;
Kirill Terekhov's avatar
Kirill Terekhov committed
674
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
675
676
677
678
679
		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
680
				{
681
					cells.push_back(hc[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
682
					m->SetMarker(hc[it],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
683
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
684
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
685
		m->RemMarkerArray(cells.data(), (enumerator)cells.size(), rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
686
687
688
		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
689
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
690
691
692
			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
693
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
694
		for(tiny_map<HandleType,int,64>::iterator it = edge_visit.begin(); it != edge_visit.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
695
696
697
		{
			if( it->second == 2 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
698
699
700
701
702
703
				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
704
					{
Kirill Terekhov's avatar
Kirill Terekhov committed
705
706
						m->SetMarker(lc[jt],rem);
						nodes.push_back(lc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
707
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
708
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
709
710
711
712
713
714
715
			}
			else if( it->second != 1 )
			{
				doexit = true;
				dothrow = true;
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
716
		for(dynarray<HandleType,64>::size_type j = 0; j < nodes.size(); j++) 
Kirill Terekhov's avatar
Kirill Terekhov committed
717
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
718
			m->RemMarker(nodes[j],rem);
719
720
721
722
723
724
			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
725
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
726
727
		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
728
729
730
		m->ReleaseMarker(rem);
		if( doexit )
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
731
732
			assert(!dothrow);
			//if( dothrow ) throw Impossible; //something went the way it shouldn't, possibly bad input
Kirill Terekhov's avatar
Kirill Terekhov committed
733
734
735
736
737
			return false;
		}
		return true;
	}

Kirill Terekhov's avatar
Kirill Terekhov committed
738
	Edge Edge::UniteEdges(const ElementArray<Edge> & edges, MarkerType del_protect)
Kirill Terekhov's avatar
Kirill Terekhov committed
739
	{
Kirill Terekhov's avatar
Kirill Terekhov committed
740
		Mesh * m = const_cast<Mesh *>(edges.GetMeshLink());
Kirill Terekhov's avatar
Kirill Terekhov committed
741
742
		if( edges.size() == 0 ) return Edge(m,InvalidHandle());
		
Kirill Terekhov's avatar
Kirill Terekhov committed
743
		bool doexit = false, dothrow = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
744
745
		MarkerType hm = m->HideMarker();
		MarkerType rem = m->CreateMarker();
Kirill Terekhov's avatar
Kirill Terekhov committed
746
		dynarray<HandleType,64> cells;
747
		dynarray<HandleType,64> faces;
Kirill Terekhov's avatar
Kirill Terekhov committed
748
749
750
		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
751
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
752
			if( m->GetMarker(edges.at(it),del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
753
				doexit = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
754
755
			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
756
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
757
				if( !m->GetMarker(hc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
758
				{
759
					faces.push_back(hc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
760
					m->SetMarker(hc[jt],rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
761
762
				}
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
763
764
765
			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
766
767
		}
		
768
		for(dynarray<HandleType,64>::size_type it = 0; it < faces.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
769
		{
770
771
			m->RemMarker(faces[it],rem);
			adj_type const & hc = m->HighConn(faces[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
772
773
774
			for(adj_type::size_type jt = 0; jt < hc.size(); ++jt)
			{
				if( !m->GetMarker(hc[jt],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
775
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
776
777
					m->SetMarker(hc[jt],rem);
					cells.push_back(hc[jt]);
Kirill Terekhov's avatar
Kirill Terekhov committed
778
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
779
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
780
		}
781
		
Kirill Terekhov's avatar
Kirill Terekhov committed
782
		m->RemMarkerArray(cells.data(), (enumerator)cells.size(), rem);
783
784
		
		
Kirill Terekhov's avatar
Kirill Terekhov committed
785
786
787
788

		if( doexit )
		{
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
789
			return Edge(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
790
791
		}
		
Kirill Terekhov's avatar
Kirill Terekhov committed
792
		for(tiny_map<HandleType,int,64>::iterator it = nodes.begin(); it != nodes.end(); it++)
Kirill Terekhov's avatar
Kirill Terekhov committed
793
		{
794
			
Kirill Terekhov's avatar
Kirill Terekhov committed
795
796
797
798
			if( it->second == 1 )
				build_nodes.push_back(it->first);
			else if( it->second == 2 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
799
				if( m->GetMarker(it->first,del_protect) )
Kirill Terekhov's avatar
Kirill Terekhov committed
800
801
802
803
					doexit = true;
			}
			else 
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
804
				doexit = true; //edges have some loop
Kirill Terekhov's avatar
Kirill Terekhov committed
805
806
807
				dothrow = true;
			}
		}
808
809
810
		
		
		assert(build_nodes.size() == 2);
Kirill Terekhov's avatar
Kirill Terekhov committed
811
812
813
814

		if( doexit )
		{
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
815
816
817
			assert(!dothrow);
			//if( dothrow ) throw Impossible; // bad input
			return Edge(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
818
819
820
		}


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

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

826
		for(dynarray<HandleType,64>::size_type it = 0; it < faces.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
827
		{
828
829
			adj_type const & lc = m->LowConn(faces[it]); //edges of face
			bool found_rem = false;
Kirill Terekhov's avatar
Kirill Terekhov committed
830
831
832
			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
833
834
				{
					//all united edges should appear in consecutive order in deleted face
Kirill Terekhov's avatar
Kirill Terekhov committed
835
					/*
Kirill Terekhov's avatar
Kirill Terekhov committed
836
					adj_type::size_type sum = 0, j = k;
Kirill Terekhov's avatar
Kirill Terekhov committed
837
					while( j < lc.size() && !m->GetMarker(lc[j],hm) && m->GetMarker(lc[j],rem) )
Kirill Terekhov's avatar
Kirill Terekhov committed
838
839
840
					{
						sum++; j++;
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
841
					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
842
843
844
845
					{
						doexit = true;
						dothrow = true;
					}
Kirill Terekhov's avatar
Kirill Terekhov committed
846
					 */
Kirill Terekhov's avatar
Kirill Terekhov committed
847
					insert_pos.push_back(k);
848
					found_rem = true;
Kirill Terekhov's avatar
Kirill Terekhov committed
849
850
					break;
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
851
			}
852
853
854
855
856
			if( !found_rem )
			{
				doexit = true;
				dothrow = true;
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
857
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
858
859
860

		if( doexit )
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
861
			m->RemMarkerArray(edges.data(), (enumerator)edges.size(), rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
862
			m->ReleaseMarker(rem);
Kirill Terekhov's avatar
Kirill Terekhov committed
863
864
865
			assert(!dothrow);
			//if( dothrow ) throw Impossible; // bad input
			return Edge(m,InvalidHandle());
Kirill Terekhov's avatar
Kirill Terekhov committed
866
867
		}

Kirill Terekhov's avatar
Kirill Terekhov committed
868
		if( !m->HideMarker() ) //disconnect if cannot hide
Kirill Terekhov's avatar
Kirill Terekhov committed
869
		{
870
			for(dynarray<HandleType,64>::size_type it = 0; it < faces.size(); ++it)
Kirill Terekhov's avatar
Kirill Terekhov committed
871
			{
872
				adj_type & lc = m->LowConn(faces[it]);
Kirill Terekhov's avatar
Kirill Terekhov committed
873
874
				adj_iterator jt = lc.begin(); //iterate over edges of faces
				while( jt != lc.end())
Kirill Terekhov's avatar
Kirill Terekhov committed
875
				{
Kirill Terekhov's avatar
Kirill Terekhov committed
876
877
					if( m->GetMarker(*jt,rem) )
						jt = lc.erase(jt);
Kirill Terekhov's avatar
Kirill Terekhov committed
878
879
880
881
882
883
					else ++jt;
				}
			}
		}


Kirill Terekhov's avatar
Kirill Terekhov committed
884
		for(ElementArray<Edge>::size_type it = 0; it < edges.size(); ++it)//delete edges
Kirill Terekhov's avatar
Kirill Terekhov committed
885
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
886
887
			m->RemMarker(edges.at(it),rem);