Debian Codegraph @

plugins/core/Standard/qFacets/include/facetsClassifier.h

raw
1 //##########################################################################
2 //# #
3 //# CLOUDCOMPARE PLUGIN: qFacets #
4 //# #
5 //# This program is free software; you can redistribute it and/or modify #
6 //# it under the terms of the GNU General Public License as published by #
7 //# the Free Software Foundation; version 2 or later of the License. #
8 //# #
9 //# This program is distributed in the hope that it will be useful, #
10 //# but WITHOUT ANY WARRANTY; without even the implied warranty of #
11 //# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the #
12 //# GNU General Public License for more details. #
13 //# #
14 //# COPYRIGHT: Thomas Dewez, BRGM #
15 //# #
16 //##########################################################################
17
18 #ifndef QFACET_FACETS_CLASSIFIER_HEADER
19 #define QFACET_FACETS_CLASSIFIER_HEADER
20
21 //Qt
22 #include <QProgressDialog>
23 #include <QApplication>
24
25 //qCC_db
26 #include "ccFacet.h"
27 #include "ccPointCloud.h"
28 #include "ccPolyline.h"
29
30 static const QString s_OriFamilyKey = "orientation.family.index";
31 static const QString s_OriFamilyNameKey = "orientation.family.name";
32 static const QString s_OriSubFamilyKey = "orientation.subfamily.index";
33
34 // default ratio for the 'dark' version of a color
35 const double c_darkColorRatio = 0.25;
36
37 class FacetsClassifier
38 {
39 public:
40
41 //! Set of facets (pointers to)
42 typedef std::vector<ccFacet*> FacetSet;
43
44 //! Computes minimal 'orthogonal' distance between two facets
45 static PointCoordinateType CommputeHDistBetweenFacets(const ccFacet* f1, const ccFacet* f2)
46 {
47 CCVector3 AB = f1->getCenter() - f2->getCenter();
48 return std::min(std::abs(AB.dot(f1->getNormal())), std::abs(AB.dot(f2->getNormal())));
49 }
50
51 //! Generates a given sub-family color
52 static void GenerateSubfamilyColor(ccColor::Rgb& col,
53 double dip,
54 double dipDir,
55 unsigned subFamilyIndex,
56 unsigned subFamilyCount,
57 ccColor::Rgb* darkCol = 0)
58 {
59 //convert dip & dip dir. to HSV
60 double H = dipDir;
61 if (H == 360.0) //H is in [0;360[
62 H = 0;
63 double S = dip / 90.0; //S is in [0;1]
64 double L = 0.5;
65
66 if (subFamilyCount > 1)
67 {
68 assert(subFamilyIndex >= 1);
69 //FIXME: how could we do this?!
70 //V = 0.5 + 0.5 * static_cast<double>(subFamilyIndex-1)/static_cast<double>(subFamilyCount-1);
71 }
72
73 col = ccColor::Convert::hsl2rgb(H, S, L);
74 if (darkCol)
75 {
76 *darkCol = ccColor::Convert::hsl2rgb(H, S, c_darkColorRatio);
77 }
78 }
79
80 static void GetFamilyIndexes(ccFacet* facet,
81 unsigned dSteps,
82 unsigned ddSteps,
83 double angularStep_deg,
84 unsigned& iDip,
85 unsigned& iDipDir)
86 {
87 assert(facet);
88 CCVector3 N = facet->getNormal();
89
90 PointCoordinateType dipDir = 0, dip = 0;
91 ccNormalVectors::ConvertNormalToDipAndDipDir(N, dip, dipDir);
92
93 iDip = static_cast<unsigned>(dip / angularStep_deg); //static_cast is equivalent to floor if value >= 0
94 if (iDip == dSteps)
95 iDip--;
96 iDipDir = static_cast<unsigned>(dipDir / angularStep_deg); //static_cast is equivalent to floor if value >= 0
97 if (iDipDir == ddSteps)
98 iDipDir--;
99 }
100
101 static inline QString GetFamilyName(double dip, double dipDir, double angularStep_deg)
102 {
103 //return QString("(%1+/-%2) / (%3+/-%4)").arg(dip).arg(angularStep_deg/2).arg(dipDir).arg(angularStep_deg/2);
104 return QString("%1_%2").arg(dipDir).arg(dip);
105 }
106
107 static inline QString GetSubFamilyName(int subFamilyIndex)
108 {
109 return QString("f%1").arg(subFamilyIndex, 4, 10, QChar('0'));
110 }
111
112 //! Subdivides a set of facets with similar orientation
113 static bool ProcessFamiliy(ccHObject* parent,
114 FacetSet& family,
115 unsigned familyIndex,
116 unsigned iDip,
117 unsigned iDipDir,
118 double angularStep_deg,
119 double maxDist)
120 {
121 size_t count = family.size();
122 if (count == 0)
123 return true;
124
125 double dip = (iDip + 0.5) * angularStep_deg;
126 double dipDir = (iDipDir + 0.5) * angularStep_deg;
127
128 QString familyName = GetFamilyName(dip, dipDir, angularStep_deg);
129
130 //create family group
131 ccHObject* familyGroup = new ccHObject(QString("F%1_").arg(familyIndex, 2, 10, QChar('0')) + familyName);
132 if (parent)
133 parent->addChild(familyGroup);
134
135 //tag all facets consequently
136 for (FacetSet::iterator it = family.begin(); it != family.end(); ++it)
137 {
138 (*it)->setMetaData(s_OriFamilyKey, QVariant(static_cast<uint>(familyIndex)));
139 (*it)->setMetaData(s_OriFamilyNameKey, QVariant(familyName));
140 }
141
142 //now we are going to regroup the facets in sub-families
143 unsigned subFamilyIndex = 0;
144
145 if (count == 1 || count == 2)
146 {
147 //1 or 2 subsets at most!
148 family[0]->setMetaData(s_OriSubFamilyKey, QVariant(static_cast<uint>(++subFamilyIndex)));
149 ccHObject* subFamilyGroup = new ccHObject(GetSubFamilyName(subFamilyIndex));
150 familyGroup->addChild(subFamilyGroup);
151 assert(family[0]->getParent() == 0);
152 subFamilyGroup->addChild(family[0]);
153
154 if (count == 2)
155 {
156 PointCoordinateType dist = CommputeHDistBetweenFacets(family[0], family[1]);
157 if (dist <= maxDist)
158 {
159 //same sub-family as #1
160 family[1]->setMetaData(s_OriSubFamilyKey, QVariant(static_cast<uint>(subFamilyIndex)));
161 assert(family[1]->getParent() == 0);
162 subFamilyGroup->addChild(family[1]);
163 }
164 else
165 {
166 //new sub-family
167 family[1]->setMetaData(s_OriSubFamilyKey, QVariant(static_cast<uint>(++subFamilyIndex)));
168 ccHObject* subFamilyGroup2 = new ccHObject(GetSubFamilyName(subFamilyIndex));
169 familyGroup->addChild(subFamilyGroup2);
170 assert(family[1]->getParent() == 0);
171 subFamilyGroup2->addChild(family[1]);
172 }
173 }
174 }
175 else
176 {
177 //create relative distance matrix
178 CCCoreLib::SquareMatrixf distMat(static_cast<unsigned>(count));
179 if (distMat.isValid())
180 {
181 for (unsigned it1 = 0; it1 + 1 != count; ++it1)
182 {
183 for (unsigned it2 = it1 + 1; it2 != count; ++it2)
184 {
185 PointCoordinateType dist = CommputeHDistBetweenFacets(family.at(it1), family.at(it2));
186 distMat.setValue(it1, it2, static_cast<float>(dist));
187 distMat.setValue(it2, it1, static_cast<float>(dist));
188 }
189 }
190
191 //regroup elements
192 while (true)
193 {
194 //we look for the two nearest facets
195 std::pair<unsigned, unsigned> bestCouple(0, 0);
196 PointCoordinateType bestCoupleDist = -1;
197 for (unsigned i = 0; i + 1 < count; ++i)
198 {
199 if (distMat.getValue(i, i) == 0) //not already assigned
200 {
201 for (unsigned j = i + 1; j < count; ++j)
202 {
203 if (distMat.getValue(j, j) == 0) //not already assigned
204 {
205 if (bestCoupleDist < 0 || bestCoupleDist > distMat.getValue(i, j))
206 {
207 bestCouple.first = i;
208 bestCouple.second = j;
209 bestCoupleDist = distMat.getValue(i, j);
210 }
211 }
212 }
213 }
214 }
215
216 if (bestCoupleDist < 0 || bestCoupleDist > maxDist)
217 break; //no more available couples!
218
219 //othrewise we push this couple in the new family set
220 std::vector<unsigned> subFamily(2);
221 subFamily[0] = bestCouple.first;
222 subFamily[1] = bestCouple.second;
223 //flag them as 'assigned'
224 distMat.setValue(bestCouple.first, bestCouple.first, -1);
225 distMat.setValue(bestCouple.second, bestCouple.second, -1);
226
227 //now look for other available facets for this sub-family
228 while (true)
229 {
230 PointCoordinateType bestDist = -1;
231 unsigned bestIndex = 0;
232 for (unsigned i = 0; i < count; ++i)
233 {
234 if (distMat.getValue(i, i) == 0) //not already assigned
235 {
236 PointCoordinateType minDist = -1;
237 for (unsigned j = 0; j < subFamily.size(); ++j)
238 {
239 const PointCoordinateType& dist = distMat.getValue(i, subFamily[j]);
240 if (dist < maxDist)
241 {
242 //still elligible?
243 if (minDist < 0 || dist < minDist)
244 minDist = dist;
245 }
246 else
247 {
248 minDist = -1;
249 break;
250 }
251 } //end of sub-family test
252
253 if (minDist >= 0 && (bestDist < 0 || minDist < bestDist))
254 {
255 bestDist = minDist;
256 bestIndex = i;
257 }
258 }
259 }
260
261 if (bestDist >= 0)
262 {
263 //add candidate to sub-family
264 subFamily.push_back(bestIndex);
265 //flag it as 'assigned'
266 distMat.setValue(bestIndex, bestIndex, -1);
267 }
268 else
269 {
270 break;
271 }
272 }
273 //end of sub-family
274
275 //we can set the class for all the sub-family elements
276 {
277 ++subFamilyIndex;
278 ccHObject* subFamilyGroup = new ccHObject(GetSubFamilyName(subFamilyIndex));
279 familyGroup->addChild(subFamilyGroup);
280 for (unsigned j = 0; j < subFamily.size(); ++j)
281 {
282 ccFacet* facet = family.at(subFamily[j]);
283 facet->setMetaData(s_OriSubFamilyKey, QVariant(static_cast<uint>(subFamilyIndex)));
284 assert(facet->getParent() == 0);
285 subFamilyGroup->addChild(facet);
286 }
287 }
288 }
289 // no more sub-families
290
291 //don't forget to set the class for the remaining isolated elements
292 {
293 for (unsigned i = 0; i < count; ++i)
294 {
295 if (distMat.getValue(i, i) == 0) //not already assigned
296 {
297 ccFacet* facet = family[i];
298 assert(facet->getParent() == 0);
299 facet->setMetaData(s_OriSubFamilyKey, QVariant(static_cast<uint>(++subFamilyIndex)));
300 ccHObject* subFamilyGroup = new ccHObject(GetSubFamilyName(subFamilyIndex));
301 familyGroup->addChild(subFamilyGroup);
302 subFamilyGroup->addChild(facet);
303 }
304 }
305 }
306
307 }
308 else
309 {
310 //not enough memory
311 for (unsigned i = 0; i < count; ++i)
312 familyGroup->addChild(family[i]);
313 return false;
314 }
315 }
316
317 //eventually we set the right colors for each facet
318 unsigned subFamilyCount = subFamilyIndex;
319 if (subFamilyCount)
320 {
321 assert(subFamilyCount > 0);
322 ccColor::Rgb col, darkCol;
323 for (unsigned i = 0; i < count; ++i)
324 {
325 ccFacet* facet = family.at(i);
326 subFamilyIndex = facet->getMetaData(s_OriSubFamilyKey).toUInt();
327 GenerateSubfamilyColor(col, dip, dipDir, subFamilyIndex, subFamilyCount, &darkCol);
328 facet->setColor(col);
329 if (facet->getContour())
330 {
331 facet->getContour()->setColor(darkCol);
332 facet->getContour()->setWidth(2);
333 }
334 }
335 }
336
337 return true;
338 }
339
340 //! Classifies the facets based on their orientation
341 static bool ByOrientation(ccHObject* facetGroup, double angularStep_deg, double maxDist)
342 {
343 assert(facetGroup && angularStep_deg > 0 && maxDist >= 0);
344
345 ccHObject::Container facets;
346 if (facetGroup)
347 facetGroup->filterChildren(facets, true, CC_TYPES::FACET);
348
349 size_t facetCount = facets.size();
350 if (facetCount == 0)
351 {
352 //nothing to do
353 return true;
354 }
355
356 //remove all facets from the group first (without deleting them!)
357 {
358 for (size_t i = 0; i < facetCount; ++i)
359 {
360 ccFacet* facet = static_cast<ccFacet*>(facets[i]);
361 assert(facet && facet->getParent());
362 facet->getParent()->removeDependencyWith(facet);
363 facet->getParent()->removeChild(facet);
364 }
365 //and remove all remaining children from the input group!
366 facetGroup->removeAllChildren();
367 }
368
369 //dip steps (dip in [0,90])
370 unsigned dSteps = static_cast<unsigned>(ceil(90.0 / angularStep_deg));
371 //dip direction steps (dip dir. in [0,360])
372 unsigned ddSteps = static_cast<unsigned>(ceil(360.0 / angularStep_deg));
373
374 bool error = false;
375 if (facetCount == 1)
376 {
377 ccFacet* facet = static_cast<ccFacet*>(facets.front());
378
379 //unique facet = unique family
380 FacetSet family(1, facet);
381
382 unsigned iDip = 0, iDipDir = 0;
383 GetFamilyIndexes(facet, dSteps, ddSteps, angularStep_deg, iDip, iDipDir);
384
385 error = !ProcessFamiliy(facetGroup, family, 1, iDip, iDipDir, angularStep_deg, maxDist);
386 }
387 else
388 {
389 unsigned gridSize = dSteps * ddSteps;
390
391 //grid to store all orientation 'families'
392 FacetSet** grid = new FacetSet*[gridSize];
393 if (!grid)
394 {
395 //not enough memory
396 error = true;
397 }
398 else
399 {
400 memset(grid, 0, sizeof(FacetSet*)*gridSize);
401
402 QProgressDialog pDlg(QObject::tr("Families classification"), QString(), 0, static_cast<int>(facetCount));
403 pDlg.show();
404 QApplication::processEvents();
405
406 //project each facet in grid
407 unsigned setCount = 0;
408 for (size_t i = 0; i < facetCount; ++i)
409 {
410 ccFacet* facet = static_cast<ccFacet*>(facets[i]);
411
412 unsigned iDip = 0, iDipDir = 0;
413 GetFamilyIndexes(facet, dSteps, ddSteps, angularStep_deg, iDip, iDipDir);
414
415 unsigned facetIndex = iDipDir + iDip * ddSteps;
416 assert(facetIndex < gridSize);
417 FacetSet* set = grid[facetIndex];
418 if (!set)
419 {
420 set = new FacetSet;
421 if (!set)
422 {
423 //not enough memory
424 error = true;
425 break;
426 }
427 grid[iDipDir + iDip * ddSteps] = set;
428 ++setCount;
429 }
430
431 try
432 {
433 set->push_back(facet);
434 }
435 catch (const std::bad_alloc&)
436 {
437 //not enough memory
438 error = true;
439 break;
440 }
441
442 pDlg.setValue(static_cast<int>(i));
443 }
444
445 if (!error)
446 {
447 unsigned familyIndex = 0;
448
449 QProgressDialog pDlg(QObject::tr("Sub-families classification"), QString(), 0, static_cast<int>(setCount));
450 pDlg.show();
451 QApplication::processEvents();
452
453 //now scan the grid and tag all 'families'
454 FacetSet** set = grid;
455 int progress = 0;
456 for (unsigned j = 0; j < dSteps; ++j)
457 {
458 for (unsigned i = 0; i < ddSteps; ++i, ++set)
459 {
460 //new family?
461 if (*set)
462 {
463 error = !ProcessFamiliy(facetGroup, **set, ++familyIndex, j, i, angularStep_deg, maxDist);
464 if (error)
465 {
466 //stop the process
467 //i = ddSteps;
468 j = dSteps;
469 break;
470 }
471
472 pDlg.setValue(++progress);
473 }
474 }
475 }
476 }
477 }
478
479 //release grid
480 {
481 for (unsigned i = 0; i < gridSize; ++i)
482 if (grid[i])
483 delete grid[i];
484 delete[] grid;
485 grid = 0;
486 }
487 }
488
489 //check that no parent-less facets remain!
490 {
491 for (size_t i = 0; i < facetCount; ++i)
492 {
493 ccFacet* facet = static_cast<ccFacet*>(facets[i]);
494 assert(facet->getParent() || error);
495 if (!facet->getParent())
496 facetGroup->addChild(facet);
497 }
498 }
499
500 //update associated display to all children as the whole structure may have changed!
501 facetGroup->setDisplay_recursive(facetGroup->getDisplay());
502
503 return !error;
504 }
505 };
506
507 #endif //QFACET_FACETS_CLASSIFIER_HEADER