Moka kernel
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
gmg-removal.cc
Go to the documentation of this file.
1 /*
2  * lib-gmapkernel : Un noyau de 3-G-cartes et des opérations.
3  * Copyright (C) 2004, Moka Team, Université de Poitiers, Laboratoire SIC
4  * http://www.sic.sp2mi.univ-poitiers.fr/
5  * Copyright (C) 2009, Guillaume Damiand, CNRS, LIRIS,
6  * guillaume.damiand@liris.cnrs.fr, http://liris.cnrs.fr/
7  *
8  * This file is part of lib-gmapkernel
9  *
10  * This program is free software: you can redistribute it and/or modify
11  * it under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation, either version 3 of the License, or
13  * (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU Lesser General Public License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this program. If not, see <http://www.gnu.org/licenses/>.
22  */
23 
24 //******************************************************************************
25 #include "g-map-generic.hh"
26 #include <deque>
27 #include <stack>
28 using namespace std;
29 using namespace GMap3d;
30 
31 #ifndef _WINDOWS
32 #include "chrono.hh"
33 #endif
34 //******************************************************************************
35 // Suppression d'une i-cellules incidente à un brin donné.
36 //
37 // dim == 2: suppression de face
38 // (pas de précondition)
39 // dim == 1: suppression d'arête
40 // (précondition : arête de degré inférieur local égal à 2)
41 // dim == 0: suppression de sommet
42 // (précondition : sommet de degré inférieur local égal à 2)
43 //
44 //******************************************************************************
45 bool CGMapGeneric::canRemove(CDart * ADart, int ADim)
46 {
47  assert(ADart!=NULL);
48  assert(ADim>=0 && ADim<=2);
49 
50  return isLocalDegreeTwoSup(ADart, ADim);
51 }
52 //******************************************************************************
53 void CGMapGeneric::remove(CDart * ADart, int ADim, bool ADeleteDarts)
54 {
55  assert(ADart!=NULL);
56  assert(ADim>=0 && ADim<=2);
57  assert(canRemove(ADart, ADim));
58 
59  int mark = getNewMark();
60  markOrbit(ADart, ORBIT_CELL[ADim], mark);
61 
62  CDart* current = NULL;
63  CDart* t2 = NULL;
64 
65  CCoverage * it = getStaticCoverage(ADart, ORBIT_CELL[ADim]);
66  while ( it->cont() )
67  {
68  current = alpha((*it)++, ADim);
69  if ( !isMarked(current, mark) )
70  {
71  t2 = alpha(current, ADim);
72  while ( isMarked(t2, mark) )
73  {
74  t2 = alpha(alpha(t2, ADim+1), ADim);
75  }
76 
77  if ( t2 != alpha(current, ADim) )
78  {
79  unsew(current, ADim);
80  if (!isFree(t2, ADim)) unsew(t2, ADim);
81  if (current!=t2) sew(current, t2, ADim);
82  }
83  }
84  }
85 
86  if (ADeleteDarts)
87  {
88  for (it->reinit(); it->cont(); )
89  delMapDart((*it)++);
90  }
91  else
92  {
93  unmarkOrbit(ADart, ORBIT_CELL[ADim], mark);
94  }
95 
96  // assert( isWholeMapUnmarked(mark) );
97 
98  freeMark(mark);
99 
100  delete it;
101 }
102 //******************************************************************************
103 int CGMapGeneric::removeMarkedCells( int AMarkNumber, int ADim,
104  bool ADeleteDarts )
105 {
106  assert(ADim>=0 && ADim<=2);
107 
108  int nbRemove = markIncidentCells(ORBIT_CELL[ADim], AMarkNumber);
109 
110  CDynamicCoverageAll cov(this);
111  for ( ; cov.cont(); ++cov )
112  {
113  if ( isMarked(*cov, AMarkNumber) )
114  {
115  if ( !canRemove(*cov, ADim) )
116  {
117  unmarkOrbit( *cov, ORBIT_CELL[ADim], AMarkNumber );
118  --nbRemove;
119  }
120  }
121  }
122 
123  CDart* current = NULL;
124  CDart* t2 = NULL;
125 
126  for ( cov.reinit(); cov.cont(); ++cov )
127  {
128  if ( !isMarked( *cov, AMarkNumber) &&
129  isMarked( alpha(*cov, ADim), AMarkNumber) )
130  {
131  current = *cov;
132  t2 = alpha(current, ADim);
133 
134  while (isMarked(t2, AMarkNumber))
135  {
136  t2 = alpha(alpha(t2, ADim+1), ADim);
137  }
138 
139  if ( t2 != alpha(current, ADim) )
140  {
141  unsew(current, ADim);
142  if ( !isFree(t2, ADim) ) unsew(t2, ADim);
143  if ( t2!=current ) sew(current, t2, ADim);
144  }
145  }
146  }
147 
148  if (ADeleteDarts)
149  {
150  for (cov.reinit(); cov.cont(); )
151  {
152  if ( isMarked(*cov, AMarkNumber) )
153  delMapDart(cov++);
154  else
155  ++cov;
156  }
157  }
158 
159  return nbRemove;
160 }
161 //******************************************************************************
162 int CGMapGeneric::removeMarkedVerticesWithFictiveEdgeShifting(int AMarkNumber)
163 {
164  int nbRemove = 0;
165  int toDelete = getNewMark();
166  int fictiveEdge = getNewMark();
167  int treated = getNewMark();
168  CDart* aDart = NULL;
169  CDart* current = NULL;
170 
171  // On propage les marques pour ne pas avoir de problèmes.
172  markIncidentCells(ORBIT_VERTEX, AMarkNumber);
173 
174  // On commence par marques les arêtes fictives
175  CDynamicCoverageAll cov(this);
176  while ( cov.cont() )
177  {
178  current = cov++;
179 
180  if ( !isMarked(current, treated) )
181  {
182  markOrbit( current, ORBIT_FACE, treated);
183  if ( !isFree2(current) &&
184  alpha1(current)!=alpha2(current) &&
185  alpha01(current)!=alpha02(current) &&
186  isSameOrbit(current, alpha2(current), ORBIT_FACE) )
187  {
188  assert( isFree3(current) );
189  markOrbit( current, ORBIT_EDGE, fictiveEdge);
190  }
191  }
192  }
193 
194  // On va supprimer les sommets en décallant les arêtes fictives.
195  cov.reinit();
196  while ( cov.cont() )
197  {
198  current = cov++;
199 
200  if ( isMarked(current, AMarkNumber) && !isMarked(current, toDelete) )
201  {
202  if ( findVertexType(current, &aDart, fictiveEdge)==2 )
203  {
204  shiftAllFictiveEdgesAroundEdge
205  /*shiftAllFictiveEdges*/( aDart, fictiveEdge );
206  assert ( canRemove(aDart, 0) );
207  {
208  markOrbit( aDart, ORBIT_VERTEX, toDelete);
209  remove( aDart, 0, false );
210  ++nbRemove;
211  }
212  }
213  }
214  }
215 
216  // On détruit les brins et enlève les marques.
217  for ( cov.reinit(); cov.cont(); )
218  {
219  unsetMark(*cov, fictiveEdge);
220  unsetMark(*cov, treated);
221 
222  if ( isMarked(*cov, toDelete) )
223  delMapDart(cov++);
224  else
225  ++cov;
226  }
227 
228  freeMark(toDelete);
229  freeMark(treated);
230  freeMark(fictiveEdge);
231 
232  return nbRemove;
233 }
234 //******************************************************************************
235 int CGMapGeneric::
236 removeMarkedEdgesWithoutDisconnectionForSurface(int AMarkNumber)
237 {
238  bool disconnect = false;
239  int toDelete = getNewMark();
240  int nbRemove = 0;
241  CDart* current = NULL;
242 
243  // On propage les marques pour ne pas avoir de problèmes.
244  markIncidentCells(ORBIT_EDGE, AMarkNumber);
245 
246  std::stack<CDart*> FToTreat;
247 
248  CDynamicCoverageAll cov(this);
249  while ( cov.cont() )
250  {
251  while ( ! FToTreat.empty() )
252  {
253  current = FToTreat.top();
254  FToTreat.pop();
255 
256  if ( isMarked(current, AMarkNumber) && !isMarked(current, toDelete) )
257  {
258  if ( (alpha1(current) !=alpha2(current) || // Si c'est pas
259  alpha01(current)!=alpha02(current)) && // une sphère.
260  alpha23(current)==alpha32(current) )
261  {
262  if ( alpha12(current)==alpha21(current) )
263  FToTreat.push(alpha1(current));
264 
265  if (alpha012(current)==alpha021(current) )
266  FToTreat.push(alpha01(current));
267 
268  remove(current, 1, false);
269  markOrbit(current, ORBIT_EDGE, toDelete);
270  ++nbRemove;
271  }
272  }
273  }
274 
275  current = cov++;
276  if ( isMarked(current, AMarkNumber) && !isMarked(current, toDelete) )
277  {
278  if ( alpha23(current)==alpha32(current) )
279  {
280  // Test de deconnexion
281  disconnect = false;
282  // Le cas de la sphère
283  if ( alpha1(current)==alpha2(current) &&
284  alpha01(current)==alpha02(current) )
285  {
286  disconnect = true;
287  }
288  // Le cas d'une arête pendante
289  else if ( alpha1(current) ==alpha2(current) ||
290  alpha01(current)==alpha02(current) )
291  {
292  disconnect = false;
293  }
294  // Le cas normal ou il faut tourner autour de la face
295  else
296  {
297  for(CDynamicCoverage01 it(this,current);
298  it.cont() && !disconnect; ++it)
299  if (*it==alpha2(current)) disconnect = true;
300  }
301 
302  if ( !disconnect )
303  {
304  if ( alpha12(current)==alpha21(current) )
305  FToTreat.push(alpha1(current));
306 
307  if (alpha012(current)==alpha021(current) )
308  FToTreat.push(alpha01(current));
309 
310  remove(current, 1, false);
311  markOrbit(current, ORBIT_EDGE, toDelete);
312  ++nbRemove;
313  }
314  }
315  }
316  }
317 
318  for ( cov.reinit(); cov.cont(); )
319  {
320  if ( isMarked(*cov, toDelete) )
321  delMapDart(cov++);
322  else
323  ++cov;
324  }
325 
326  freeMark(toDelete);
327 
328  return nbRemove;
329 }
330 //******************************************************************************
331 int CGMapGeneric::removeMarkedEdgesWithoutDisconnection( int AMarkNumber )
332 {
333 #ifndef _WINDOWS
334  CChrono c;
335  c.start();
336 #endif
337 
338  int toDelete = getNewMark();
339  int treated = getNewMark();
340  int nbRemove = 0;
341  CDart* current = NULL;
342  CDart* aDart = NULL;
343 
344  // On propage les marques pour ne pas avoir de problèmes.
345  markIncidentCells(ORBIT_EDGE, AMarkNumber);
346 
347  // We initialise one uf-tree for each face to detect efficiently if the degree of
348  // an edge is 1 or 2.
349  int index = getNewDirectInfo();
350  if ( index!=-1 ) initUnionFindTrees(index, ORBIT_FACE);
351  else std::cout<<"Not enough directInfo to use union-find trees."<<std::endl;
352 
353  CDynamicCoverageAll cov(this);
354 
355  // On commence par marquer les faces fictives et on en profite pour en
356  // même temps supprimer les arêtes de degré deux.
357  while ( cov.cont() )
358  {
359  current = cov++;
360 
361  // Si c'est une arête de degré deux et pas une sphère, on la supprime
362  if ( isMarked(current, AMarkNumber) &&
363  !isMarked(current, toDelete) &&
364  ( (alpha1(current) !=alpha2(current) ||
365  alpha01(current)!=alpha02(current)) &&
366  alpha23(current)==alpha32(current) ) &&
367  (index!=-1?(findUnionFindTrees(current, index)!=
368  findUnionFindTrees(alpha2(current),index)):
369  (!isSameOrbit(current, alpha2(current), ORBIT_FACE))) )
370  {
371  markOrbit(current, ORBIT_EDGE, toDelete);
372  remove(current, 1, false);
373  ++nbRemove;
374 
375  if ( index!=-1 )
376  mergeUnionFindTrees(current, alpha2(current), index);
377  }
378  else
379  if ( !isMarked(current, toDelete) && !isMarked(current, treated) )
380  // Ici on utilise la marque treated pour marquer les
381  // brins déjà traités.
382  {
383  markOrbit( current, ORBIT_FACE, treated);
384  }
385  }
386 
387  // On détruit les brins et enlève les marques.
388  for ( cov.reinit(); cov.cont(); )
389  {
390  unsetMark(*cov, treated);
391 
392  if ( isMarked(*cov, toDelete) ) delMapDart(cov++);
393  else ++cov;
394  }
395 
396  freeMark(toDelete);
397  freeMark(treated);
398 
399  if ( index!=-1 ) freeDirectInfo(index);
400 
401 #ifndef _WINDOWS
402  c.stop();
403  c.display("Temps de simplification");
404 #endif
405 
406  return nbRemove;
407 }
408 //******************************************************************************
409 int CGMapGeneric::
410 removeMarkedEdgesWithoutDisconnectionWithFaceShifting( int AMarkNumber )
411 {
412  int toDelete = getNewMark();
413  int treated = getNewMark();
414  int nbRemove = 0;
415  CDart* current = NULL;
416  CDart* aDart = NULL;
417  int fictiveFaces = getNewMark();
418  int markFace = getNewMark();
419  int res;
420  int nbDarts;
421  bool existFictiveDart;
422  bool generator;
423 
424  // On propage les marques pour ne pas avoir de problèmes.
425  markIncidentCells(ORBIT_EDGE, AMarkNumber);
426 
427  CDynamicCoverageAll cov(this);
428 
429  // On commence par marquer les faces fictives et on en profite pour en
430  // même temps supprimer les arêtes de degré deux.
431  while ( cov.cont() )
432  {
433  current = cov++;
434 
435  // Si c'est une arête de degré deux et pas une sphère, on la supprime
436  if ( isMarked(current, AMarkNumber) &&
437  !isMarked(current, toDelete) &&
438  ( (alpha1(current) !=alpha2(current) ||
439  alpha01(current)!=alpha02(current)) &&
440  alpha23(current)==alpha32(current) ) &&
441  !isSameOrbit(current, alpha2(current), ORBIT_FACE) )
442  {
443  markOrbit(current, ORBIT_EDGE, toDelete);
444  remove(current, 1, false);
445  ++nbRemove;
446  }
447  else
448  if ( !isMarked(current, toDelete) && !isMarked(current, treated) )
449  // Ici on utilise la marque toDelete pour marquer les
450  // brins déjà traités.
451  {
452  markOrbit( current, ORBIT_FACE, treated);
453  if ( !isFree3(current) &&
454  isSameOrbit(current, alpha3(current), ORBIT_VOLUME) )
455  markOrbit( current, ORBIT_FACE, fictiveFaces);
456  }
457  }
458 
459  // Maintenant on va traiter les arêtes
460  cov.reinit();
461  while ( cov.cont() )
462  {
463  current = cov++;
464 
465  if ( isMarked(current, AMarkNumber) && !isMarked(current, toDelete) )
466  {
467  if ( (res=findEdgeType(current, &aDart, fictiveFaces))==2 &&
468  canShiftAllFictiveFaces(aDart, fictiveFaces) )
469  {
470  shiftAllFictiveFaces(aDart, fictiveFaces, toDelete);
471  markOrbit(aDart, ORBIT_EDGE, toDelete);
472  remove(aDart, 1, false);
473  ++nbRemove;
474  // break;
475  }
476  else if ( res==1 )
477  {
478  if ( isMarked(alpha2(aDart), fictiveFaces) )
479  shiftOneFictiveFaceAlongDanglingEdge(aDart,
480  fictiveFaces,
481  toDelete);
482  markOrbit(aDart, ORBIT_EDGE, toDelete);
483  remove(aDart, 1, false);
484  ++nbRemove;
485  }
486  }
487  }
488 
489  // On va marquer les arêtes ayant un nombre impair de brins.
490  negateMaskMark(treated);
491 
492  cov.reinit();
493  while ( cov.cont() )
494  {
495  current = cov++;
496 
497  if ( !isMarked(current, toDelete) && !isMarked(current, treated) )
498  {
499  existFictiveDart = false;
500  generator = true;
501  for (CDynamicCoverageEdge it(this,current); it.cont(); ++it)
502  {
503  if ( !isMarked(*it, treated) )
504  {
505  setMark(*it, treated);
506  if ( isMarked(*it, fictiveFaces ) )
507  {
508  existFictiveDart = true;
509  nbDarts = 0;
510 
511  markOrbit(*it, ORBIT_FACE, markFace);
512 
513  for (CDynamicCoverageEdge it2(this,*it); it2.cont(); ++it2)
514  {
515  if ( isMarked(*it2, markFace) )
516  {
517  setMark(*it2, treated);
518  ++nbDarts;
519  }
520  }
521 
522  unmarkOrbit(*it, ORBIT_FACE, markFace);
523 
524  if ( (nbDarts/4)%2==1 ) // Si le nombre d'arête est pair
525  // Alors l'arête est un générateur H1
526  generator = false;
527  }
528  }
529  }
530 
531  if ( generator || !existFictiveDart )
532  markOrbit( current, ORBIT_EDGE, AMarkNumber);
533  else // sinon c'est le bord d'une face fictive
534  unmarkOrbit( current, ORBIT_EDGE, AMarkNumber);
535  }
536  }
537 
538  // On détruit les brins et enlève les marques.
539  for ( cov.reinit(); cov.cont(); )
540  {
541  unsetMark(*cov, fictiveFaces);
542  unsetMark(*cov, treated);
543  unsetMark(*cov, markFace);
544 
545  if ( isMarked(*cov, toDelete) )
546  delMapDart(cov++);
547  else
548  ++cov;
549  }
550 
551  freeMark(toDelete);
552  freeMark(treated);
553  freeMark(fictiveFaces);
554  freeMark(markFace);
555 
556  {
557  // temporaire pour tester la 0-suppression : TODO ajouter une
558  // entrée dans le menu
559  if ( nbRemove==0 )
560  {
561  treated=getNewMark();
562  negateMaskMark(treated);
563  nbRemove=removeMarkedVerticesWithFictiveEdgeShifting(treated);
564  negateMaskMark(treated);
565  freeMark(treated);
566  }
567  }
568 
569  return nbRemove;
570 }
571 //******************************************************************************
572 int CGMapGeneric::removeMarkedFacesButKeepBalls(int AMarkNumber)
573 {
574  int toDelete = getNewMark();
575  int treated = getNewMark();
576  int toTreat2 = getNewMark();
577  int nbRemove = 0;
578  CDart* current = NULL;
579  std::stack<CDart*> FToTreat;
580  bool dangling = false;
581 
582  // 1) On propage les marques pour ne pas avoir de problèmes.
583  markIncidentCells(ORBIT_FACE, AMarkNumber);
584 
585  // 2) On fait la simplification de toute les faces en conservant des sphères
586  // mais on autorise les déconnections.
587  CDynamicCoverageAll cov(this);
588  while ( cov.cont() )
589  {
590  if ( ! FToTreat.empty() )
591  {
592  current = FToTreat.top();
593  FToTreat.pop();
594  }
595  else
596  {
597  current = cov++;
598  }
599 
600  // On sauve la marque AMarkNumber dans toTreat2 pour la deuxième passe
601  // if ( isMarked(current, AMarkNumber) ) setMark( current, toTreat2 );
602 
603  // Est-ce que la face doit être supprimée ?
604  if ( isMarked(current, AMarkNumber) && !isFree3(current) &&
605  !isMarked(current, toDelete) && !isMarked(current, treated) )
606  {
607  // Ici on voudrait supprimer la face incidente à current.
608  // On doit vérifier si le volume reste une boule ou pas.
609 
610  // Pour ça on supprime les faces entre deux volumes distincts
611  // ou les faces pendantes (ATTENTION : def des faces pendantes ???)
612 
613  // Test sur la face pendante
614  dangling = false;
615  CDynamicCoverage01 itFace(this, current);
616  for ( ; itFace.cont(); ++itFace )
617  {
618  setMark( *itFace, treated );
619  setMark( alpha3(*itFace), treated );
620 
621  if ( alpha23(*itFace)==*itFace ) dangling = true;
622  }
623 
624  // Test si la face est entre deux volumes distincts
625  if ( dangling ||
626  !isSameOrbit(current, alpha3(current), ORBIT_VOLUME) )
627  {
628  // Il faut reconsidérer les faces adjacentes car elles sont
629  // susceptibles de pouvoir être supprimées.
630  for ( itFace.reinit(); itFace.cont(); ++itFace )
631  {
632  if ( alpha23(*itFace)!=*itFace )
633  {
634  if ( isMarked(alpha2(*itFace), treated) )
635  {
636  FToTreat.push(alpha2(*itFace));
637  unmarkOrbit(alpha2(*itFace), ORBIT_FACE, treated);
638  }
639  if ( isMarked(alpha32(*itFace), treated) )
640  {
641  FToTreat.push(alpha32(*itFace));
642  unmarkOrbit(alpha32(*itFace), ORBIT_FACE, treated);
643  }
644  }
645 
646  setMark( *itFace, toDelete );
647  setMark( alpha3(*itFace), toDelete );
648  }
649 
650  // La suppression proprement dite
651  remove(current, 2, false);
652  ++nbRemove;
653  }
654  }
655  }
656 
657  // 3) On démarque toutes les faces sauf les fictives
658  for ( cov.reinit(); cov.cont(); )
659  {
660  current = cov++;
661 
662  unsetMark( current, treated );
663 
664  if ( isMarked(current, AMarkNumber) && !isMarked(current, toDelete) &&
665  !isFree3(current) )
666  unmarkOrbit(current, ORBIT_FACE, AMarkNumber);
667  }
668 
669  // 4) On supprime les faces qui ont été conservées pour garder les sphères
670  // (elles ont servit uniquement pour marquer les arêtes de degré > 2)
671  /*
672  for ( cov.reinit(); cov.cont(); )
673  {
674  if ( ! FToTreat.empty() )
675  {
676  current = FToTreat.top();
677  FToTreat.pop();
678  }
679  else
680  {
681  current = cov++;
682  }
683 
684  if ( isMarked(current, toTreat2) && !isFree3(current) &&
685  !isMarked(current, toDelete) && !isMarked(current, treated) )
686  {
687  // Il faut reconsidérer les faces adjacentes car elles sont
688  // susceptibles de pouvoir être supprimées.
689  CDynamicCoverage01 itFace(this, current);
690  for ( itFace.reinit(); itFace.cont(); ++itFace )
691  {
692  if ( alpha23(*itFace)!=*itFace )
693  {
694  if ( isMarked(alpha2(*itFace), treated) )
695  {
696  FToTreat.push(alpha2(*itFace));
697  unmarkOrbit(alpha2(*itFace), ORBIT_FACE, treated);
698  }
699  if ( isMarked(alpha32(*itFace), treated) )
700  {
701  FToTreat.push(alpha32(*itFace));
702  unmarkOrbit(alpha32(*itFace), ORBIT_FACE, treated);
703  }
704  }
705  }
706 
707  // La suppression proprement dite
708  remove(current, 2, false);
709  markOrbit(current,ORBIT_FACE,toDelete);
710  ++nbRemove;
711  }
712  }
713  */
714 
715  // 5) On supprime tout les brins
716  for ( cov.reinit(); cov.cont(); )
717  {
718  current = cov++;
719 
720  unsetMark( current, treated );
721  // unsetMark( current, toTreat2 );
722 
723  if ( isMarked(current, toDelete) )
724  delMapDart(current);
725  }
726 
727  freeMark(toDelete);
728  freeMark(treated);
729  freeMark(toTreat2);
730 
731  return nbRemove;
732 }
733 //******************************************************************************