collector.hpp 12.1 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
* Copyright (C) 2009, IGG Team, LSIIT, University of Strasbourg                *
*                                                                              *
* This library is free software; you can redistribute it and/or modify it      *
* under the terms of the GNU Lesser General Public License as published by the *
* Free Software Foundation; either version 2.1 of the License, or (at your     *
* option) any later version.                                                   *
*                                                                              *
* This library is distributed in the hope that it will be useful, but WITHOUT  *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License  *
* for more details.                                                            *
*                                                                              *
* You should have received a copy of the GNU Lesser General Public License     *
* along with this library; if not, write to the Free Software Foundation,      *
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA.           *
*                                                                              *
20
* Web site: http://cgogn.unistra.fr/                                  *
Pierre Kraemer's avatar
Pierre Kraemer committed
21
22
23
24
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

25
26
27
#include "Topology/generic/traversor2.h"
#include "Algo/Geometry/intersection.h"

Pierre Kraemer's avatar
Pierre Kraemer committed
28
29
30
namespace CGoGN
{

31
32
33
namespace Algo
{

Pierre Kraemer's avatar
Pierre Kraemer committed
34
35
36
namespace Selection
{

37
38
39
40
/*********************************************************
 * Generic Collector
 *********************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
41
template <typename PFP>
Pierre Kraemer's avatar
Pierre Kraemer committed
42
Collector<PFP>::Collector(typename PFP::MAP& m) : map(m)
Pierre Kraemer's avatar
Pierre Kraemer committed
43
44
{}

45
template <typename PFP>
Pierre Kraemer's avatar
Pierre Kraemer committed
46
inline bool Collector<PFP>::applyOnInsideVertices(FunctorType& f)
47
48
49
50
51
52
53
{
	for(std::vector<Dart>::iterator iv = insideVertices.begin(); iv != insideVertices.end(); ++iv)
		if(f(*iv))
			return true ;
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
template <typename PFP>
inline bool Collector<PFP>::applyOnInsideEdges(FunctorType& f)
{
	for(std::vector<Dart>::iterator iv = insideEdges.begin(); iv != insideEdges.end(); ++iv)
		if(f(*iv))
			return true ;
	return false ;
}

template <typename PFP>
inline bool Collector<PFP>::applyOnInsideFaces(FunctorType& f)
{
	for(std::vector<Dart>::iterator iv = insideFaces.begin(); iv != insideFaces.end(); ++iv)
		if(f(*iv))
			return true ;
	return false ;
}

template <typename PFP>
inline bool Collector<PFP>::applyOnBorder(FunctorType& f)
{
	for(std::vector<Dart>::iterator iv = border.begin(); iv != border.end(); ++iv)
		if(f(*iv))
			return true ;
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
81
82
83
84
85
template <typename PPFP>
std::ostream& operator<<(std::ostream &out, const Collector<PPFP>& c)
{
    out << "Collector around " << c.centerDart << std::endl;
    out << "insideVertices (" << c.insideVertices.size() << ") = {";
Pierre Kraemer's avatar
Pierre Kraemer committed
86
    for (unsigned int i = 0; i< c.insideVertices.size(); ++i) out << c.insideVertices[i] << " ";
Pierre Kraemer's avatar
Pierre Kraemer committed
87
88
    out << "}" << std::endl ;
    out << "insideEdges (" << c.insideEdges.size() << ") = {";
Pierre Kraemer's avatar
Pierre Kraemer committed
89
    for (unsigned int i = 0; i< c.insideEdges.size(); ++i) out << c.insideEdges[i] << " ";
Pierre Kraemer's avatar
Pierre Kraemer committed
90
91
    out << "}" << std::endl ;
    out << "insideFaces (" << c.insideFaces.size() << ") = {";
Pierre Kraemer's avatar
Pierre Kraemer committed
92
    for (unsigned int i = 0; i< c.insideFaces.size(); ++i) out << c.insideFaces[i] << " ";
Pierre Kraemer's avatar
Pierre Kraemer committed
93
94
    out << "}" << std::endl ;
    out << "border (" << c.border.size() << ") = {";
Pierre Kraemer's avatar
Pierre Kraemer committed
95
    for (unsigned int i = 0; i< c.border.size(); ++i) out << c.border[i] << " ";
Pierre Kraemer's avatar
Pierre Kraemer committed
96
97
98
99
100
101
102
103
104
    out << "}" << std::endl;
    return out;
}

/*********************************************************
 * Collector One Ring
 *********************************************************/

template <typename PFP>
Pierre Kraemer's avatar
Pierre Kraemer committed
105
void Collector_OneRing<PFP>::collectAll(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
106
{
Pierre Kraemer's avatar
Pierre Kraemer committed
107
	this->init(d);
108
109
110
	this->insideEdges.reserve(16);
	this->insideFaces.reserve(16);
	this->border.reserve(16);
Pierre Kraemer's avatar
Pierre Kraemer committed
111

112
113
114
115
116
117
118
119
	this->insideVertices.push_back(this->centerDart);

	Traversor2VE<typename PFP::MAP> te(this->map, this->centerDart) ;
	for(Dart it = te.begin(); it != te.end(); it = te.next())
		this->insideEdges.push_back(it);

	Traversor2VF<typename PFP::MAP> tf(this->map, this->centerDart) ;
	for(Dart it = tf.begin(); it != tf.end(); it = tf.next())
Pierre Kraemer's avatar
Pierre Kraemer committed
120
	{
121
122
123
		this->insideFaces.push_back(it);
		this->border.push_back(this->map.phi1(it));
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
124
125
126
}

template <typename PFP>
Pierre Kraemer's avatar
Pierre Kraemer committed
127
void Collector_OneRing<PFP>::collectBorder(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
128
{
Pierre Kraemer's avatar
Pierre Kraemer committed
129
130
131
	this->init(d);
	this->border.reserve(12);

132
133
134
	Traversor2VF<typename PFP::MAP> t(this->map, this->centerDart) ;
	for(Dart it = t.begin(); it != t.end(); it = t.next())
		this->border.push_back(this->map.phi1(it));
Pierre Kraemer's avatar
Pierre Kraemer committed
135
136
}

Pierre Kraemer's avatar
Pierre Kraemer committed
137
138
139
140
/*********************************************************
 * Collector Within Sphere
 *********************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
141
template <typename PFP>
Pierre Kraemer's avatar
Pierre Kraemer committed
142
void Collector_WithinSphere<PFP>::collectAll(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
143
144
145
146
{
	typedef typename PFP::VEC3 VEC3;
	typedef typename PFP::REAL REAL;

Pierre Kraemer's avatar
Pierre Kraemer committed
147
	this->init(d);
148
149
150
	this->insideEdges.reserve(32);
	this->insideFaces.reserve(32);
	this->border.reserve(32);
Pierre Kraemer's avatar
Pierre Kraemer committed
151

152
153
154
	CellMarkerStore<VERTEX> vm(this->map);	// mark the collected inside-vertices
	CellMarkerStore<EDGE> em(this->map);	// mark the collected inside-edges + border-edges
	CellMarkerStore<FACE> fm(this->map);	// mark the collected inside-faces + border-faces
Pierre Kraemer's avatar
Pierre Kraemer committed
155
156
157
158

	this->insideVertices.push_back(this->centerDart);
	vm.mark(this->centerDart);

Pierre Kraemer's avatar
Pierre Kraemer committed
159
	VEC3 centerPosition = this->position[d];
Pierre Kraemer's avatar
Pierre Kraemer committed
160
	unsigned int i = 0;
161
//	for(std::vector<Dart>::iterator iv = this->insideVertices.begin(); iv != this->insideVertices.end(); ++iv)
Pierre Kraemer's avatar
Pierre Kraemer committed
162
163
164
165
166
167
168
169
170
171
172
	while (i < this->insideVertices.size())
	{
		Dart end = this->insideVertices[i];
		Dart e = end;
		do
		{
			if (! em.isMarked(e) || ! fm.isMarked(e)) // are both tests useful ?
			{
				const Dart f = this->map.phi1(e);
				const Dart g = this->map.phi1(f);

173
				if (! Geom::isPointInSphere(this->position[f], centerPosition, this->radius))
Pierre Kraemer's avatar
Pierre Kraemer committed
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
				{
					this->border.push_back(e); // add to border
					em.mark(e);
					fm.mark(e); // is it useful ?
				}
				else
				{
					if (! vm.isMarked(f))
					{
						this->insideVertices.push_back(f);
						vm.mark(f);
					}
					if (! em.isMarked(e))
					{
						this->insideEdges.push_back(e);
						em.mark(e);
					}
191
					if (! fm.isMarked(e) && Geom::isPointInSphere(this->position[g], centerPosition, this->radius))
Pierre Kraemer's avatar
Pierre Kraemer committed
192
193
194
195
196
197
					{
						this->insideFaces.push_back(e);
						fm.mark(e);
					}
				}
			}
198
			e = this->map.phi2_1(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
199
200
201
202
203
		} while (e != end);
		++i;
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
204
205
206
207
208
209
210
template <typename PFP>
void Collector_WithinSphere<PFP>::collectBorder(Dart d)
{
	typedef typename PFP::VEC3 VEC3;
	typedef typename PFP::REAL REAL;

	this->init(d);
211
212
	this->border.reserve(128);
	this->insideVertices.reserve(128);
Pierre Kraemer's avatar
Pierre Kraemer committed
213

214
215
	CellMarkerStore<VERTEX> vm(this->map);	// mark the collected inside-vertices
	CellMarkerStore<EDGE> em(this->map);	// mark the collected inside-edges + border-edges
216
217
218

	this->insideVertices.push_back(this->centerDart);
	vm.mark(this->centerDart);
Pierre Kraemer's avatar
Pierre Kraemer committed
219
220
221
222
223
224
225
226
227

	VEC3 centerPosition = this->position[d];
	unsigned int i = 0;
	while (i < this->insideVertices.size())
	{
		Dart end = this->insideVertices[i];
		Dart e = end;
		do
		{
228
			if ( ! em.isMarked(e) )
Pierre Kraemer's avatar
Pierre Kraemer committed
229
230
231
232
233
234
235
			{
				const Dart f = this->map.phi1(e);

				if (! Geom::isPointInSphere(this->position[f], centerPosition, this->radius))
				{
					this->border.push_back(e); // add to border
				}
236
237
238
239
240
241
242
243
244
				else
				{
					if (! vm.isMarked(f))
					{
						this->insideVertices.push_back(f);
						vm.mark(f);
					}
				}
				em.mark(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
245
			}
246
			e = this->map.phi2_1(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
247
248
249
		} while (e != end);
		++i;
	}
250
	this->insideVertices.clear();
Pierre Kraemer's avatar
Pierre Kraemer committed
251
252
}

Pierre Kraemer's avatar
Pierre Kraemer committed
253
254
255
template <typename PFP>
void Collector_WithinSphere<PFP>::computeArea()
{
Pierre Kraemer's avatar
Pierre Kraemer committed
256
257
258
	area = 0;
	typename PFP::VEC3 centerPosition = this->position[this->centerDart];

Pierre Kraemer's avatar
Pierre Kraemer committed
259
	for (std::vector<Dart>::const_iterator it = this->insideFaces.begin(); it != this->insideFaces.end(); ++it)
260
		area += Algo::Geometry::triangleArea<PFP>(this->map, *it, this->position);
Pierre Kraemer's avatar
Pierre Kraemer committed
261
262
263
264
265

	for (std::vector<Dart>::const_iterator it = this->border.begin(); it != this->border.end(); ++it)
	{
		const Dart f = this->map.phi1(*it); // we know that f is outside
		const Dart g = this->map.phi1(f);
266
		if (Geom::isPointInSphere(this->position[g], centerPosition, this->radius))
Pierre Kraemer's avatar
Pierre Kraemer committed
267
		{ // only f is outside
268
269
270
271
			typename PFP::REAL alpha, beta;
			Algo::Geometry::intersectionSphereEdge<PFP>(this->map, centerPosition, this->radius, *it, this->position, alpha);
			Algo::Geometry::intersectionSphereEdge<PFP>(this->map, centerPosition, this->radius, this->map.phi2(f), this->position, beta);
			area += (alpha+beta - alpha*beta) * Algo::Geometry::triangleArea<PFP>(this->map, *it, this->position);
Pierre Kraemer's avatar
Pierre Kraemer committed
272
273
274
		}
		else
		{ // f and g are outside
275
276
277
278
			typename PFP::REAL alpha, beta;
			Algo::Geometry::intersectionSphereEdge<PFP>(this->map, centerPosition, this->radius, *it, this->position, alpha);
			Algo::Geometry::intersectionSphereEdge<PFP>(this->map, centerPosition, this->radius, this->map.phi2(g), this->position, beta);
			area += alpha * beta * Algo::Geometry::triangleArea<PFP>(this->map, *it, this->position);
Pierre Kraemer's avatar
Pierre Kraemer committed
279
280
281
282
		}
	}
}

283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
/*********************************************************
 * Collector Normal Angle
 *********************************************************/

template <typename PFP>
void Collector_NormalAngle<PFP>::collectAll(Dart d)
{
	typedef typename PFP::VEC3 VEC3;
	typedef typename PFP::REAL REAL;

	this->init(d);
	this->insideEdges.reserve(32);
	this->insideFaces.reserve(32);
	this->border.reserve(32);

	CellMarkerStore<VERTEX> vm(this->map);	// mark the collected inside-vertices
	CellMarkerStore<EDGE> em(this->map);	// mark the collected inside-edges + border-edges
	CellMarkerStore<FACE> fm(this->map);	// mark the collected inside-faces + border-faces

	this->insideVertices.push_back(this->centerDart);
	vm.mark(this->centerDart);

	VEC3 centerNormal = this->normal[d];
	unsigned int i = 0;
	while (i < this->insideVertices.size())
	{
		Dart end = this->insideVertices[i];
		Dart e = end;
		do
		{
			if (! em.isMarked(e) || ! fm.isMarked(e)) // are both tests useful ?
			{
				const Dart f = this->map.phi1(e);
				const Dart g = this->map.phi1(f);

				REAL a = Geom::angle(centerNormal, this->normal[f]);

				if (a > angleThreshold)
				{
					this->border.push_back(e); // add to border
					em.mark(e);
					fm.mark(e); // is it useful ?
				}
				else
				{
					if (! vm.isMarked(f))
					{
						this->insideVertices.push_back(f);
						vm.mark(f);
					}
					if (! em.isMarked(e))
					{
						this->insideEdges.push_back(e);
						em.mark(e);
					}

					REAL b = Geom::angle(centerNormal, this->normal[g]);
					if (! fm.isMarked(e) && b < angleThreshold)
					{
						this->insideFaces.push_back(e);
						fm.mark(e);
					}
				}
			}
			e = this->map.phi2_1(e);
		} while (e != end);
		++i;
	}
}

template <typename PFP>
void Collector_NormalAngle<PFP>::collectBorder(Dart d)
{
	typedef typename PFP::VEC3 VEC3;
	typedef typename PFP::REAL REAL;

	this->init(d);
	this->border.reserve(128);
	this->insideVertices.reserve(128);

	CellMarkerStore<VERTEX> vm(this->map);	// mark the collected inside-vertices
	CellMarkerStore<EDGE> em(this->map);	// mark the collected inside-edges + border-edges

	this->insideVertices.push_back(this->centerDart);
	vm.mark(this->centerDart);

	VEC3 centerNormal = this->normal[d];
	unsigned int i = 0;
	while (i < this->insideVertices.size())
	{
		Dart end = this->insideVertices[i];
		Dart e = end;
		do
		{
			if ( ! em.isMarked(e) )
			{
				const Dart f = this->map.phi1(e);

				REAL a = Geom::angle(centerNormal, this->normal[f]);

				if (a > angleThreshold)
				{
					this->border.push_back(e); // add to border
				}
				else
				{
					if (! vm.isMarked(f))
					{
						this->insideVertices.push_back(f);
						vm.mark(f);
					}
				}
				em.mark(e);
			}
			e = this->map.phi2_1(e);
		} while (e != end);
		++i;
	}
	this->insideVertices.clear();
}

Pierre Kraemer's avatar
Pierre Kraemer committed
404
405
} // namespace Selection

406
407
} // namespace Algo

Pierre Kraemer's avatar
Pierre Kraemer committed
408
} // namespace CGoGN