raySelector.h 15.3 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
177
178
179
180
181
182
183
184
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
217
218
219
220
221
222
223
224
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
257
258
259
260
261
262
263
264
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
291
292
293
294
295

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)
		nbth = Algo::Parallel::optimalNbThreads();

	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));

	Algo::Parallel::foreach_cell<typename PFP::MAP,FACE>(map, functs, nbth, false, good, current_thread);


	// 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)
		nbth = Algo::Parallel::optimalNbThreads();

	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));

	Algo::Parallel::foreach_cell<typename PFP::MAP,EDGE>(map, functs, nbth, false, good, current_thread);

	// 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)
		nbth = Algo::Parallel::optimalNbThreads();

	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));

	Algo::Parallel::foreach_cell<typename PFP::MAP,VERTEX>(map, functs, nbth, false, good, current_thread);

	// 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);




}




}


Pierre Kraemer's avatar
Pierre Kraemer committed
296
297
298
299
300
/**
 * 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
301
 * @param vertex (out) dart of selected vertex (set to NIL if no vertex selected)
Pierre Kraemer's avatar
Pierre Kraemer committed
302
303
 */
template<typename PFP>
304
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
305
{
306
307
308
	std::vector<Dart> vecFaces;
	std::vector<typename PFP::VEC3> iPoints;

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

Pierre Kraemer's avatar
Pierre Kraemer committed
313
314
315
316
317
318
319
320
321
	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
322
			distnint[i].first = (iPoints[i] - rayA).norm2();
Pierre Kraemer's avatar
Pierre Kraemer committed
323
324
325
326
327
328
			distnint[i].second = i;
		}

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
333
		// recuperation du sommet le plus proche du point d'intersection
334
335
336
		Dart d = vecFaces[first];
		Dart it = d;
		typename PFP::REAL minDist = (ip - position[it]).norm2();
Pierre Kraemer's avatar
Pierre Kraemer committed
337
		vertex = it;
338
339
		it = map.phi1(it);
		while(it != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
340
		{
341
			typename PFP::REAL dist = (ip - position[it]).norm2();
Pierre Kraemer's avatar
Pierre Kraemer committed
342
343
			if(dist < minDist)
			{
344
345
				minDist = dist;
				vertex = it;
Pierre Kraemer's avatar
Pierre Kraemer committed
346
			}
347
348
			it = map.phi1(it);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
349
350
	}
	else
Pierre Kraemer's avatar
Pierre Kraemer committed
351
		vertex = NIL;
Pierre Kraemer's avatar
Pierre Kraemer committed
352
353
354
}

/**
355
356
 * 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
357
358
359
360
361
362
 * @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>
363
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
364
365
366
367
{
	// recuperation des brins intersectes
	vecDarts.clear();
	Algo::Selection::FuncDartMapD2Inter<PFP> ffi(map, position, vecDarts, rayA, rayAB);
Pierre Kraemer's avatar
Pierre Kraemer committed
368
	map.template foreach_orbit<FACE>(ffi, good);
Pierre Kraemer's avatar
Pierre Kraemer committed
369
370
371
372
373
374
375
376
377
378
379
380
381

	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;
382
		typename PFP::VEC3 V = (position[d] + position[map.phi1(d)]) / typename PFP::REAL(2);
Pierre Kraemer's avatar
Pierre Kraemer committed
383
		V -= rayA;
384
		distndart[i].first = V.norm2();
Pierre Kraemer's avatar
Pierre Kraemer committed
385
386
387
388
389
390
391
392
393
394
	}

	// 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;
}

395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
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
413
414
415
416
417
418
419
} //namespace Selection

} //namespace Algo

} //namespace CGoGN

#endif /* RAYSELECTOR_H_ */