raySelector.h 16.2 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1
2
3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2012, IGG Team, LSIIT, University of Strasbourg           *
Pierre Kraemer's avatar
Pierre Kraemer committed
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
*                                                                              *
* 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
25
26
27
28
29
30
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#ifndef RAYSELECTOR_H_
#define RAYSELECTOR_H_

#include <algorithm>
#include <vector>
#include "Algo/Selection/raySelectFunctor.hpp"
31
#include "Algo/Parallel/parallel_foreach.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
32
33
34
35
36
37
38
39
40

namespace CGoGN
{

namespace Algo
{

namespace Selection
{
41

Pierre Kraemer's avatar
Pierre Kraemer committed
42
43
44
45
/**
 * Function that does the selection of faces, returned darts are sorted from closest to farthest
 * @param map the map we want to test
 * @param good a dart selector
46
47
48
 * @param rayA first point of ray (user side)
 * @param rayAB direction of ray (directed to the scene)
 * @param vecFaces (out) vector to store the darts of intersected faces
Pierre Kraemer's avatar
Pierre Kraemer committed
49
50
 */
template<typename PFP>
51
void facesRaySelection(typename PFP::MAP& map, const VertexAttribute<typename PFP::VEC3>& position, const FunctorSelect& good, const typename PFP::VEC3& rayA, const typename PFP::VEC3& rayAB, std::vector<Dart>& vecFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
52
{
53
	std::vector<typename PFP::VEC3> iPoints;
Pierre Kraemer's avatar
Pierre Kraemer committed
54
55
56
57

	// get back intersected faces
	vecFaces.clear();
	Algo::Selection::FuncFaceInter<PFP> ffi(map, position, vecFaces, iPoints, rayA, rayAB);
Pierre Kraemer's avatar
Pierre Kraemer committed
58
	map.template foreach_orbit<FACE>(ffi, good);
Pierre Kraemer's avatar
Pierre Kraemer committed
59

60
	// compute all distances to observer for each intersected face
Pierre Kraemer's avatar
Pierre Kraemer committed
61
62
63
64
65
66
	// and put them in a vector for sorting
	typedef std::pair<typename PFP::REAL, Dart> DartDist;
	std::vector<DartDist> distndart;

	unsigned int nbi = vecFaces.size();
	distndart.resize(nbi);
67
	for (unsigned int i = 0; i < nbi; ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
68
69
70
	{
		distndart[i].second = vecFaces[i];
		typename PFP::VEC3 V = iPoints[i] - rayA;
71
		distndart[i].first = V.norm2();
Pierre Kraemer's avatar
Pierre Kraemer committed
72
73
74
75
76
77
	}

	// sort the vector of pair dist/dart
	std::sort(distndart.begin(), distndart.end(), distndartOrdering<PFP>);

	// store sorted darts in returned vector
78
	for (unsigned int i = 0; i < nbi; ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
79
80
81
82
83
84
85
86
87
		vecFaces[i] = distndart[i].second;
}

/**
 * Function that does the selection of edges, returned darts are sorted from closest to farthest
 * @param map the map we want to test
 * @param rayA first point of  ray (user side)
 * @param rayAB vector of ray (directed ot the scene)
 * @param vecEdges (out) vector to store dart of intersected edges
88
 * @param dist radius of the cylinder of selection
Pierre Kraemer's avatar
Pierre Kraemer committed
89
90
 */
template<typename PFP>
91
void edgesRaySelection(typename PFP::MAP& map, const VertexAttribute<typename PFP::VEC3>& position, const FunctorSelect& good, const typename PFP::VEC3& rayA, const typename PFP::VEC3& rayAB, std::vector<Dart>& vecEdges, float dist)
Pierre Kraemer's avatar
Pierre Kraemer committed
92
{
93
94
	typename PFP::REAL dist2 = dist * dist;
	typename PFP::REAL AB2 = rayAB * rayAB;
Pierre Kraemer's avatar
Pierre Kraemer committed
95
96
97
98

	// recuperation des aretes intersectees
	vecEdges.clear();
	Algo::Selection::FuncEdgeInter<PFP> ffi(map, position, vecEdges, rayA, rayAB, AB2, dist2);
Pierre Kraemer's avatar
Pierre Kraemer committed
99
	map.template foreach_orbit<EDGE>(ffi, good);
Pierre Kraemer's avatar
Pierre Kraemer committed
100
101
102
103
104
105
106

	typedef std::pair<typename PFP::REAL, Dart> DartDist;
	std::vector<DartDist> distndart;

	unsigned int nbi = vecEdges.size();
	distndart.resize(nbi);

107
	// compute all distances to observer for each middle of intersected edge
Pierre Kraemer's avatar
Pierre Kraemer committed
108
109
110
111
112
	// and put them in a vector for sorting
	for (unsigned int i = 0; i < nbi; ++i)
	{
		Dart d = vecEdges[i];
		distndart[i].second = d;
113
		typename PFP::VEC3 V = (position[d] + position[map.phi1(d)]) / typename PFP::REAL(2);
Pierre Kraemer's avatar
Pierre Kraemer committed
114
		V -= rayA;
115
		distndart[i].first = V.norm2();
Pierre Kraemer's avatar
Pierre Kraemer committed
116
117
118
119
120
121
	}

	// sort the vector of pair dist/dart
	std::sort(distndart.begin(), distndart.end(), distndartOrdering<PFP>);

	// store sorted darts in returned vector
122
	for (unsigned int i = 0; i < nbi; ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
123
124
125
126
127
128
129
130
		vecEdges[i] = distndart[i].second;
}

/**
 * Function that does the selection of vertices, returned darts are sorted from closest to farthest
 * @param map the map we want to test
 * @param rayA first point of  ray (user side)
 * @param rayAB vector of ray (directed ot the scene)
131
132
 * @param vecVertices (out) vector to store dart of intersected vertices
 * @param dist radius of the cylinder of selection
Pierre Kraemer's avatar
Pierre Kraemer committed
133
134
 */
template<typename PFP>
135
void verticesRaySelection(typename PFP::MAP& map, const VertexAttribute<typename PFP::VEC3>& position, const typename PFP::VEC3& rayA, const typename PFP::VEC3& rayAB, std::vector<Dart>& vecVertices, float dist, const FunctorSelect& good= allDarts)
Pierre Kraemer's avatar
Pierre Kraemer committed
136
{
137
138
139
	typename PFP::REAL dist2 = dist * dist;
	typename PFP::REAL AB2 = rayAB * rayAB;

Pierre Kraemer's avatar
Pierre Kraemer committed
140
141
142
	// recuperation des sommets intersectes
	vecVertices.clear();
	Algo::Selection::FuncVertexInter<PFP> ffi(map, position, vecVertices, rayA, rayAB, AB2, dist2);
Pierre Kraemer's avatar
Pierre Kraemer committed
143
	map.template foreach_orbit<VERTEX>(ffi, good);
Pierre Kraemer's avatar
Pierre Kraemer committed
144
145
146
147
148
149
150

	typedef std::pair<typename PFP::REAL, Dart> DartDist;
	std::vector<DartDist> distndart;

	unsigned int nbi = vecVertices.size();
	distndart.resize(nbi);

151
	// compute all distances to observer for each intersected vertex
Pierre Kraemer's avatar
Pierre Kraemer committed
152
153
154
155
156
157
	// and put them in a vector for sorting
	for (unsigned int i = 0; i < nbi; ++i)
	{
		Dart d = vecVertices[i];
		distndart[i].second = d;
		typename PFP::VEC3 V = position[d] - rayA;
158
		distndart[i].first = V.norm2();
Pierre Kraemer's avatar
Pierre Kraemer committed
159
160
161
162
163
164
	}

	// sort the vector of pair dist/dart
	std::sort(distndart.begin(), distndart.end(), distndartOrdering<PFP>);

	// store sorted darts in returned vector
165
	for (unsigned int i = 0; i < nbi; ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
166
167
168
		vecVertices[i] = distndart[i].second;
}

169
170
171
172
173
174
175
176

namespace Parallel
{

template<typename PFP>
void facesRaySelection(typename PFP::MAP& map, const VertexAttribute<typename PFP::VEC3>& position, const FunctorSelect& good, const typename PFP::VEC3& rayA, const typename PFP::VEC3& rayAB, std::vector<Dart>& vecFaces, unsigned int nbth=0, unsigned int current_thread=0)
{
	if (nbth==0)
177
178
//		nbth = Algo::Parallel::optimalNbThreads();
		nbth =2;	// seems to be optimal ?
179
180
181
182
183

	std::vector<FunctorMapThreaded<typename PFP::MAP>*> functs;
	for (unsigned int i=0; i < nbth; ++i)
		functs.push_back(new Parallel::FuncFaceInter<PFP>(map,position,rayA, rayAB));

184
	Algo::Parallel::foreach_cell<typename PFP::MAP,FACE>(map, functs, false, good, current_thread);
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216


	// compute total nb of intersection
	unsigned int nbtot=0;
	for (unsigned int i=0; i < nbth; ++i)
		nbtot += static_cast<Parallel::FuncFaceInter<PFP>*>(functs[i])->getFaceDistances().size();

	std::vector<std::pair<typename PFP::REAL, Dart> > distndart;
	distndart.reserve(nbtot);
	for (unsigned int i=0; i < nbth; ++i)
	{
		distndart.insert(distndart.end(),static_cast<Parallel::FuncFaceInter<PFP>*>(functs[i])->getFaceDistances().begin(), static_cast<Parallel::FuncFaceInter<PFP>*>(functs[i])->getFaceDistances().end() );
		delete functs[i];
	}

	// sort the vector of pair dist/dart
	std::sort(distndart.begin(), distndart.end(), distndartOrdering<PFP>);

	vecFaces.clear();
	vecFaces.reserve(nbtot);
	// store sorted darts in returned vector
	for (unsigned int i = 0; i < nbtot; ++i)
		vecFaces.push_back(distndart[i].second);
}

template<typename PFP>
void edgesRaySelection(typename PFP::MAP& map, const VertexAttribute<typename PFP::VEC3>& position, const FunctorSelect& good, const typename PFP::VEC3& rayA, const typename PFP::VEC3& rayAB, std::vector<Dart>& vecEdges, float dist, unsigned int nbth=0, unsigned int current_thread=0)
{
	typename PFP::REAL dist2 = dist * dist;
	typename PFP::REAL AB2 = rayAB * rayAB;

	if (nbth==0)
217
218
//		nbth = Algo::Parallel::optimalNbThreads();
		nbth =2;	// seems to be optimal ?
219
220
221
222
223

	std::vector<FunctorMapThreaded<typename PFP::MAP>*> functs;
	for (unsigned int i=0; i < nbth; ++i)
		functs.push_back(new Parallel::FuncEdgeInter<PFP>(map,position,rayA, rayAB, AB2, dist2));

224
	Algo::Parallel::foreach_cell<typename PFP::MAP,EDGE>(map, functs, false, good, current_thread);
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256

	// compute total nb of intersection
	unsigned int nbtot=0;
	for (unsigned int i=0; i < nbth; ++i)
		nbtot += static_cast<Parallel::FuncEdgeInter<PFP>*>(functs[i])->getEdgeDistances().size();

	std::vector<std::pair<typename PFP::REAL, Dart> > distndart;
	distndart.reserve(nbtot);
	for (unsigned int i=0; i < nbth; ++i)
	{
		distndart.insert(distndart.end(),static_cast<Parallel::FuncEdgeInter<PFP>*>(functs[i])->getEdgeDistances().begin(), static_cast<Parallel::FuncEdgeInter<PFP>*>(functs[i])->getEdgeDistances().end() );
		delete functs[i];
	}

	// sort the vector of pair dist/dart
	std::sort(distndart.begin(), distndart.end(), distndartOrdering<PFP>);

	// store sorted darts in returned vector
	vecEdges.clear();
	vecEdges.reserve(nbtot);
	for (unsigned int i = 0; i < nbtot; ++i)
		vecEdges.push_back(distndart[i].second);
}


template<typename PFP>
void verticesRaySelection(typename PFP::MAP& map, const VertexAttribute<typename PFP::VEC3>& position, const typename PFP::VEC3& rayA, const typename PFP::VEC3& rayAB, std::vector<Dart>& vecVertices, float dist, const FunctorSelect& good= allDarts, unsigned int nbth=0, unsigned int current_thread=0)
{
	typename PFP::REAL dist2 = dist * dist;
	typename PFP::REAL AB2 = rayAB * rayAB;

	if (nbth==0)
257
258
//		nbth = Algo::Parallel::optimalNbThreads();
		nbth =2;	// seems to be optimal ?
259
260
261
262
263

	std::vector<FunctorMapThreaded<typename PFP::MAP>*> functs;
	for (unsigned int i=0; i < nbth; ++i)
		functs.push_back(new Parallel::FuncVertexInter<PFP>(map,position,rayA, rayAB, AB2, dist2));

264
	Algo::Parallel::foreach_cell<typename PFP::MAP,VERTEX>(map, functs, false, good, current_thread);
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290

	// compute total nb of intersection
	unsigned int nbtot=0;
	for (unsigned int i=0; i < nbth; ++i)
		nbtot += static_cast<Parallel::FuncVertexInter<PFP>*>(functs[i])->getVertexDistances().size();

	std::vector<std::pair<typename PFP::REAL, Dart> > distndart;
	distndart.reserve(nbtot);
	for (unsigned int i=0; i < nbth; ++i)
	{
		distndart.insert(distndart.end(),static_cast<Parallel::FuncVertexInter<PFP>*>(functs[i])->getVertexDistances().begin(), static_cast<Parallel::FuncVertexInter<PFP>*>(functs[i])->getVertexDistances().end() );
		delete functs[i];
	}

	// sort the vector of pair dist/dart
	std::sort(distndart.begin(), distndart.end(), distndartOrdering<PFP>);

	// store sorted darts in returned vector
	vecVertices.clear();
	vecVertices.reserve(nbtot);
	for (unsigned int i = 0; i < nbtot; ++i)
		vecVertices.push_back(distndart[i].second);


}

291
292
293
294
295
296
template<typename PFP>
void vertexRaySelection(typename PFP::MAP& map, const VertexAttribute<typename PFP::VEC3>& position, const typename PFP::VEC3& rayA, const typename PFP::VEC3& rayAB, Dart& vertex, const FunctorSelect& good = allDarts, unsigned int nbth=0, unsigned int current_thread=0)
{
	std::vector<Dart> vecFaces;
	vecFaces.reserve(100);
	Parallel::facesRaySelection<PFP>(map, position, good, rayA, rayAB, vecFaces, nbth, current_thread);
297

298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
	if(vecFaces.size() > 0)
	{
		// recuperation du sommet le plus proche
		Dart d = vecFaces.front();
		Dart it = d;
		typename PFP::REAL minDist = (rayA - position[it]).norm2();
		vertex = it;
		it = map.phi1(it);
		while(it != d)
		{
			typename PFP::REAL dist = (rayA - position[it]).norm2();
			if(dist < minDist)
			{
				minDist = dist;
				vertex = it;
			}
			it = map.phi1(it);
		}
	}
	else
		vertex = NIL;
319
320
}

321
}
322

Pierre Kraemer's avatar
Pierre Kraemer committed
323
324
325
326
327
/**
 * Function that does the selection of one vertex
 * @param map the map we want to test
 * @param rayA first point of  ray (user side)
 * @param rayAB vector of ray (directed ot the scene)
Pierre Kraemer's avatar
Pierre Kraemer committed
328
 * @param vertex (out) dart of selected vertex (set to NIL if no vertex selected)
Pierre Kraemer's avatar
Pierre Kraemer committed
329
330
 */
template<typename PFP>
331
void vertexRaySelection(typename PFP::MAP& map, const VertexAttribute<typename PFP::VEC3>& position, const typename PFP::VEC3& rayA, const typename PFP::VEC3& rayAB, Dart& vertex, const FunctorSelect& good = allDarts)
Pierre Kraemer's avatar
Pierre Kraemer committed
332
{
333
334
335
	std::vector<Dart> vecFaces;
	std::vector<typename PFP::VEC3> iPoints;

Pierre Kraemer's avatar
Pierre Kraemer committed
336
	// recuperation des faces intersectes
337
	Algo::Selection::FuncFaceInter<PFP> ffi(map, position, vecFaces, iPoints, rayA, rayAB);
Pierre Kraemer's avatar
Pierre Kraemer committed
338
	map.template foreach_orbit<FACE>(ffi, good);
339

Pierre Kraemer's avatar
Pierre Kraemer committed
340
341
342
343
344
345
346
347
348
	if(vecFaces.size() > 0)
	{
		typedef std::pair<typename PFP::REAL, unsigned int> IndexedDist;
		std::vector<IndexedDist> distnint;

		unsigned int nbi = vecFaces.size();
		distnint.resize(nbi);
		for (unsigned int i = 0; i < nbi; ++i)
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
349
			distnint[i].first = (iPoints[i] - rayA).norm2();
Pierre Kraemer's avatar
Pierre Kraemer committed
350
351
352
353
354
355
			distnint[i].second = i;
		}

		// sort the vector of pair dist/dart
		std::sort(distnint.begin(), distnint.end(), distnintOrdering<PFP>);

356
		// recuperation du point d'intersection sur la face la plus proche
Pierre Kraemer's avatar
Pierre Kraemer committed
357
		unsigned int first = distnint[0].second;
358
359
		typename PFP::VEC3 ip = iPoints[first];

Pierre Kraemer's avatar
Pierre Kraemer committed
360
		// recuperation du sommet le plus proche du point d'intersection
361
362
363
		Dart d = vecFaces[first];
		Dart it = d;
		typename PFP::REAL minDist = (ip - position[it]).norm2();
Pierre Kraemer's avatar
Pierre Kraemer committed
364
		vertex = it;
365
366
		it = map.phi1(it);
		while(it != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
367
		{
368
			typename PFP::REAL dist = (ip - position[it]).norm2();
Pierre Kraemer's avatar
Pierre Kraemer committed
369
370
			if(dist < minDist)
			{
371
372
				minDist = dist;
				vertex = it;
Pierre Kraemer's avatar
Pierre Kraemer committed
373
			}
374
375
			it = map.phi1(it);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
376
377
	}
	else
Pierre Kraemer's avatar
Pierre Kraemer committed
378
		vertex = NIL;
Pierre Kraemer's avatar
Pierre Kraemer committed
379
380
381
}

/**
382
383
 * Fonction that do the selection of darts, returned darts are sorted from closest to farthest
 * Dart is here considered as a triangle formed by the 2 end vertices of the edge and the face centroid
Pierre Kraemer's avatar
Pierre Kraemer committed
384
385
386
387
388
389
 * @param map the map we want to test
 * @param rayA first point of  ray (user side)
 * @param rayAB vector of ray (directed ot the scene)
 * @param vecDarts (out) vector to store dart of intersected darts
 */
template<typename PFP>
390
void dartsRaySelection(typename PFP::MAP& map, const VertexAttribute<typename PFP::VEC3>& position, const typename PFP::VEC3& rayA, const typename PFP::VEC3& rayAB, std::vector<Dart>& vecDarts, const FunctorSelect& good = allDarts)
Pierre Kraemer's avatar
Pierre Kraemer committed
391
392
393
394
{
	// recuperation des brins intersectes
	vecDarts.clear();
	Algo::Selection::FuncDartMapD2Inter<PFP> ffi(map, position, vecDarts, rayA, rayAB);
Pierre Kraemer's avatar
Pierre Kraemer committed
395
	map.template foreach_orbit<FACE>(ffi, good);
Pierre Kraemer's avatar
Pierre Kraemer committed
396
397
398
399
400
401
402
403
404
405
406
407
408

	typedef std::pair<typename PFP::REAL, Dart> DartDist;
	std::vector<DartDist> distndart;

	unsigned int nbi = vecDarts.size();
	distndart.resize(nbi);

	// compute all distances to observer for each dart of middle of edge
	// and put them in a vector for sorting
	for (unsigned int i = 0; i < nbi; ++i)
	{
		Dart d = vecDarts[i];
		distndart[i].second = d;
409
		typename PFP::VEC3 V = (position[d] + position[map.phi1(d)]) / typename PFP::REAL(2);
Pierre Kraemer's avatar
Pierre Kraemer committed
410
		V -= rayA;
411
		distndart[i].first = V.norm2();
Pierre Kraemer's avatar
Pierre Kraemer committed
412
413
414
415
416
417
418
419
420
421
	}

	// sort the vector of pair dist/dart
	std::sort(distndart.begin(), distndart.end(), distndartOrdering<PFP>);

	// store sorted darts in returned vector
	for (unsigned int i=0; i< nbi; ++i)
		vecDarts[i] = distndart[i].second;
}

422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
template<typename PFP>
void facesPlanSelection(typename PFP::MAP& map, const VertexAttribute<typename PFP::VEC3>& position,
		const typename Geom::Plane3D<typename PFP::VEC3::DATA_TYPE>& plan, std::vector<Dart>& vecDarts,
		const FunctorSelect& good = allDarts)
{
	TraversorF<typename PFP::MAP> travF(map);

	for(Dart dit = travF.begin() ; dit != travF.end() ; dit = travF.next() )
	{
		if(Geom::intersectionTrianglePlan<typename PFP::VEC3>(position[dit], position[map.phi1(dit)], position[map.phi_1(dit)],plan.d(), plan.normal()) == Geom::FACE_INTERSECTION)
		{
			vecDarts.push_back(dit);
		}
	}

	std::cout << "nb faces = " << vecDarts.size() << std::endl;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
440
441
442
443
444
445
446
} //namespace Selection

} //namespace Algo

} //namespace CGoGN

#endif /* RAYSELECTOR_H_ */