Moka libraries
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
precodes-l.icc
Go to the documentation of this file.
1 /*
2  * lib-extraction-images : Extraction de cartes à partir d'images 2D et 3D.
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-extraction-images
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 "image-3d.hh"
26 #include "pixel-step.hh"
27 
28 namespace GMap3d
29 {
30 //******************************************************************************
31 // Les précodes "volumes" utilisés pour extraire la carte de niveau 1
32 
33 INLINE
34 void CExtractionImage::precodeL1( CDart* &last, CDart* up, CDart* behind, const CVertex & AVertex )
35 {
36 #ifdef DEBUG_EXTRACT_IMAGE
37  cout<<"CExtractionImage::precodeL1...";cout.flush();
38 #endif
39 
40  CDart* lastc=createCubeForExtract3d(AVertex);
41 
42  FMap->topoSew3(up,FMap->alpha012(lastc));
43  FMap->topoSew3(behind,FMap->alpha21012(lastc));
44  FMap->topoSew3(last,FMap->alpha1012101(lastc));
45  last = FMap->alpha32(behind);
46 
47 #ifdef DEBUG_EXTRACT_IMAGE
48  cout<<"OK\n";
49 #endif
50 
51 }
52 
53 //******************************************************************************
54 // Quelques méthodes de base utilisées dans les méthodes de précode
55 INLINE
56 CDart* CExtractionImage::newEdge()
57 {
58  CDart *V1 = FMap->addMapDart();
59  CDart *V2 = FMap->addMapDart();
60  FMap->linkAlpha0(V1, V2); // FMap->sew the two vertices
61  return V1;
62 }
63 
64 INLINE
65 void CExtractionImage::closeFace( CDart* d1, CDart* d2,CDart* d3 )
66 {
67  CDart* tmp=newEdge();
68 
69  FMap->linkAlpha1(FMap->alpha0(d1),d2);
70  FMap->linkAlpha1(FMap->alpha0(d2),d3);
71  FMap->linkAlpha1(FMap->alpha0(d3),tmp);
72  FMap->linkAlpha1(FMap->alpha0(tmp),d1);
73 }
74 
75 INLINE
76 void CExtractionImage::closeFace( CDart* d1, CDart* d2 )
77 { closeFace(newEdge(),d1,d2); }
78 
79 INLINE
80 void CExtractionImage::closeFace( CDart* d )
81 { closeFace(newEdge(),newEdge(),d); }
82 
83 //******************************************************************************
84 // Méthode générique utilisée par les précodes v2, v3 et v4
85 INLINE
86 CDart* CExtractionImage::oneSameNeighboorV( CDart* d1, CDart* fo1, CDart* fo2, const CVertex & AVertex )
87 {
88  CDart *d2,*d3,*d4;
89  d2=FMap->alpha01(d1);
90  d3=FMap->alpha01(d2);
91  d4=FMap->alpha01(d3);
92  CDart* newFace=createFaceForExtract3d( AVertex );
93  closeFace(d1);
94  closeFace(d2);
95  closeFace(d3);
96  closeFace(d4);
97  FMap->topoSew2(FMap->alpha01(d1),FMap->alpha1(d2));
98  FMap->topoSew2(FMap->alpha01(d2),FMap->alpha1(d3));
99  FMap->topoSew2(FMap->alpha01(d3),FMap->alpha1(d4));
100  FMap->topoSew2(FMap->alpha01(d4),FMap->alpha1(d1));
101  FMap->topoSew2(FMap->alpha0101(d1),FMap->alpha010(newFace));
102  FMap->topoSew2(FMap->alpha1010(d2),FMap->alpha101(newFace));
103  FMap->topoSew2(FMap->alpha0101(d3),FMap->alpha1(newFace));
104  FMap->topoSew2(FMap->alpha101(d4),newFace);
105  FMap->topoSew3(FMap->alpha0(d1),fo1);
106  FMap->topoSew3(FMap->alpha0(d2),fo2);
107  return newFace;
108 }
109 
110 
111 INLINE
112 void CExtractionImage::precodeL2( CDart* &last, CDart* up, CDart* behind, const CVertex & AVertex )
113 {
114 #ifdef DEBUG_EXTRACT_IMAGE
115  cout<<"CExtractionImage::precodeL2...";cout.flush();
116 #endif
117 
118  last = FMap->alpha101(oneSameNeighboorV( FMap->alpha010(last), FMap->alpha010(up), FMap->alpha101(behind), AVertex));
119 
120 #ifdef DEBUG_EXTRACT_IMAGE
121  cout<<"OK\n";
122 #endif
123 }
124 
125 INLINE
126 void CExtractionImage::precodeL3( CDart* &last, CDart* up, CDart* behind, const CVertex & AVertex )
127 {
128 #ifdef DEBUG_EXTRACT_IMAGE
129  cout<<"CExtractionImage::precodeL3...";cout.flush();
130 #endif
131 
132  last = FMap->alpha201(oneSameNeighboorV( FMap->alpha101(up), FMap->alpha010(behind), FMap->alpha010(last), AVertex));
133 
134 #ifdef DEBUG_EXTRACT_IMAGE
135  cout<<"OK\n";
136 #endif
137 }
138 
139 INLINE
140 void CExtractionImage::precodeL4( CDart* &last, CDart* up, CDart* behind, const CVertex & AVertex )
141 {
142 #ifdef DEBUG_EXTRACT_IMAGE
143  cout<<"CExtractionImage::precodeL4...";cout.flush();
144 #endif
145 
146  last = FMap->alpha12101(oneSameNeighboorV( FMap->alpha101(behind), FMap->alpha0(last), FMap->alpha101(up), AVertex));
147 
148 #ifdef DEBUG_EXTRACT_IMAGE
149  cout<<"OK\n";
150 #endif
151 }
152 
153 //******************************************************************************
154 // Méthode générique utilisée pour les précodes v5, v6 et v7
155 // c'est à dire lorsqu'il y FMap->alpha deux fusions de volumes à faire
156 INLINE
157 CDart* CExtractionImage::twoSameNeighboorV( CDart* d1, CDart* d5, CDart* fo, const CVertex & AVertex )
158 {
159  CDart *d2,*d3,*d4,*d6,*d7,*d8, *t1, *t2;
160 
161  d2=FMap->alpha01(d1);
162  d3=FMap->alpha01(d2);
163  d4=FMap->alpha01(d3);
164  d6=FMap->alpha01(d5);
165  d7=FMap->alpha01(d6);
166  d8=FMap->alpha01(d7);
167 
168  if (FMap->alpha2(d1) != FMap->alpha0(d5))
169  {
170  t1 = FMap->alpha2(d1);
171  t2 = FMap->alpha2(d5);
172 
173  FMap->unsew2(d1);
174  FMap->unsew2(d5);
175 
176  FMap->sew2(t1,FMap->alpha0(t2));
177  }
178 
179  FMap->unsew1(d1);
180  FMap->unsew1(d2);
181  FMap->unsew1(d5);
182  FMap->unsew1(d6);
183 
184  closeFace(d4,d6);
185  closeFace(d3);
186  closeFace(d8,d2);
187  closeFace(d7);
188 
189  FMap->delMapDart(FMap->alpha0(d1));
190  FMap->delMapDart(FMap->alpha0(d5));
191  FMap->delMapDart(d1);
192  FMap->delMapDart(d5);
193 
194  FMap->topoSew2(FMap->alpha01(d6),FMap->alpha1(d7));
195  FMap->topoSew2(FMap->alpha1(d4),FMap->alpha01(d3));
196  FMap->topoSew2(FMap->alpha01(d7),FMap->alpha1(d8));
197  FMap->topoSew2(FMap->alpha101(d7),FMap->alpha1010(d3));
198  FMap->topoSew2(FMap->alpha01(d2),FMap->alpha1(d3));
199 
200  FMap->topoSew3(FMap->alpha0(fo),d4);
201 
202  FMap->setVertex(FMap->alpha010(d7),
203  new CAttributeVertex(AVertex.getX()*STEP3D_X,
204  AVertex.getY()*STEP3D_Y,
205  AVertex.getZ()*STEP3D_Z));
206 
207  return d7;
208 }
209 
210 
211 INLINE
212 void CExtractionImage::precodeL5( CDart* &last, CDart* up, CDart* behind, const CVertex & AVertex )
213 
214 {
215 #ifdef DEBUG_EXTRACT_IMAGE
216  cout<<"CExtractionImage::precodeL5...";cout.flush();
217 #endif
218 
219  last = FMap->alpha0(twoSameNeighboorV(FMap->alpha0(last), FMap->alpha101(behind), FMap->alpha010(up), AVertex));
220 
221 #ifdef DEBUG_EXTRACT_IMAGE
222  cout<<"OK\n";
223 #endif
224 }
225 
226 
227 INLINE
228 void CExtractionImage::precodeL6( CDart* &last, CDart* up, CDart* behind, const CVertex & AVertex )
229 {
230 #ifdef DEBUG_EXTRACT_IMAGE
231  cout<<"CExtractionImage::precodeL6...";cout.flush();
232 #endif
233 
234  last = FMap->alpha10121(twoSameNeighboorV(FMap->alpha010(up), FMap->alpha010(last), FMap->alpha010(behind), AVertex));
235 
236 #ifdef DEBUG_EXTRACT_IMAGE
237  cout<<"OK\n";
238 #endif
239 }
240 
241 
242 INLINE
243 void CExtractionImage::precodeL7( CDart* &last, CDart* up, CDart* behind, const CVertex & AVertex )
244 
245 {
246 #ifdef DEBUG_EXTRACT_IMAGE
247  cout<<"CExtractionImage::precodeL7...";cout.flush();
248 #endif
249 
250  last = FMap->alpha0102101(twoSameNeighboorV(FMap->alpha010(behind), FMap->alpha101(up), FMap->alpha0(last), AVertex));
251 
252 #ifdef DEBUG_EXTRACT_IMAGE
253  cout<<"OK\n";
254 #endif
255 }
256 
257 
258 INLINE
259 void CExtractionImage::precodeL8( CDart* &last, CDart* up, CDart* behind, const CVertex & AVertex )
260 {
261 
262 #ifdef DEBUG_EXTRACT_IMAGE
263  cout<<"CExtractionImage::precodeL8...";cout.flush();
264 #endif
265 
266  CDart *d1,*d2,*d3,*d4,*d5,*d6, *s1, *s2, *t1, *t2, *t3, *t4 ,*t5, *t6;
267 
268  d1=FMap->alpha1(last);
269  d2=FMap->alpha01(d1);
270  d3=FMap->alpha0(up);
271  d4=FMap->alpha01(d3);
272  d5=FMap->alpha0(behind);
273  d6=FMap->alpha01(d5);
274 
275 //******************************************************************************
276  if (FMap->alpha12(d1) != FMap->alpha01(d6))
277  {
278  s1 = FMap->alpha12(d1);
279  s2 = FMap->alpha012(d6);
280 
281  FMap->unsew2(FMap->alpha1(d1));
282  FMap->unsew2(FMap->alpha010(d6));
283  FMap->sew2(s1,s2);
284  }
285 
286  if (FMap->alpha012(d2) != FMap->alpha1(d3))
287  {
288  s1 = FMap->alpha012(d2);
289  s2 = FMap->alpha12(d3);
290 
291  FMap->unsew2(FMap->alpha01(d2));
292  FMap->unsew2(FMap->alpha10(d3));
293  FMap->sew2(s1,s2);
294  }
295 
296  if (FMap->alpha12(d5) != FMap->alpha01(d4))
297  {
298  s1 = FMap->alpha12(d5);
299  s2 = FMap->alpha012(d4);
300 
301  FMap->unsew2(FMap->alpha10(d5));
302  FMap->unsew2(FMap->alpha01(d4));
303  FMap->sew2(s1,s2);
304  }
305 
306  t1 = FMap->alpha01(d2);
307  t2 = FMap->alpha01(t1);
308  t3 = FMap->alpha01(d4);
309  t4 = FMap->alpha01(t3);
310  t5 = FMap->alpha01(d6);
311  t6 = FMap->alpha01(t5);
312  FMap->unsew1(d1);
313  FMap->unsew1(d5);
314  FMap->unsew1(FMap->alpha0(d6));
315  FMap->unsew1(FMap->alpha0(d4));
316  FMap->unsew1(FMap->alpha0(d2));
317  FMap->unsew1(FMap->alpha10(d4));
318 
319  closeFace(d2,d3);
320  closeFace(d6,d1);
321  closeFace(d4,d5);
322 
323  FMap->topoSew2(FMap->alpha01(d1),FMap->alpha1(d2));
324  FMap->topoSew2(FMap->alpha01(d3),FMap->alpha1(d4));
325  FMap->topoSew2(FMap->alpha01(d5),FMap->alpha1(d6));
326 
327  FMap->setVertex(FMap->alpha010(d5),new CAttributeVertex(AVertex.getX()*STEP3D_X,
328  AVertex.getY()*STEP3D_Y,
329  AVertex.getZ()*STEP3D_Z));
330 
331  FMap->delMapDart(FMap->alpha0(t2));
332  FMap->delMapDart(t2);
333  FMap->delMapDart(FMap->alpha0(t1));
334  FMap->delMapDart(t1);
335  FMap->delMapDart(FMap->alpha0(t4));
336  FMap->delMapDart(t4);
337  FMap->delMapDart(FMap->alpha0(t3));
338  FMap->delMapDart(t3);
339  FMap->delMapDart(FMap->alpha0(t6));
340  FMap->delMapDart(t6);
341  FMap->delMapDart(FMap->alpha0(t5));
342  FMap->delMapDart(t5);
343 
344  last = FMap->alpha0(d5);
345 
346 #ifdef DEBUG_EXTRACT_IMAGE
347  cout<<"OK precode8\n";
348 #endif
349 }
350 
351 // Les méthodes subcasePrecodeLi sont appelées par l'algorithme principal.
352 // Elles peuvent ensuite suivant "level" appeler directement une methode de
353 // précode volume, ou appeler une methode subcasePrecodeFci.
354 INLINE
355 void CExtractionImage::subcasePrecodeL1( CImage3d & image, unsigned int x, unsigned int y,
356  CDart* &last, CDart* up, CDart* behind,
357  int level, const CVertex & AVertex, int FictiveMark,
358  bool keepFictiveEdges, bool shiftFictiveEdges )
359 {
360  precodeL1(last,up,behind,AVertex);
361 }
362 
363 INLINE
364 void CExtractionImage::subcasePrecodeL2( CImage3d & image,
365  unsigned int x, unsigned int y,
366  CDart* &last, CDart* up, CDart* behind,
367  int level, const CVertex & AVertex, int FictiveMark,
368  bool keepFictiveEdges, bool shiftFictiveEdges )
369 {
370  if (level==1)
371  precodeL2(last,up,behind,AVertex);
372  else
373  {
374  if ( image.sameVoxelBehindLeft(x,y) )
375  if ( image.sameVoxelUpLeft(x,y) )
376  subcasePrecodeFc7(image,x,y,last,up,behind,level,AVertex,FictiveMark,
377  keepFictiveEdges, shiftFictiveEdges);
378  else
379  subcasePrecodeFc1(image,x,y,last,up,behind,level,AVertex,FictiveMark,
380  keepFictiveEdges, shiftFictiveEdges);
381  else
382  if ( image.sameVoxelUpLeft(x,y) )
383  subcasePrecodeFc4(image,x,y,last,up,behind,level,AVertex,FictiveMark,
384  keepFictiveEdges, shiftFictiveEdges);
385  else
386  precodeL2(last,up,behind,AVertex);
387  }
388 }
389 
390 INLINE
391 void CExtractionImage::subcasePrecodeL3( CImage3d & image,
392  unsigned int x, unsigned int y,
393  CDart* &last, CDart* up, CDart* behind,
394  int level, const CVertex & AVertex, int FictiveMark,
395  bool keepFictiveEdges, bool shiftFictiveEdges )
396 {
397  if (level==1)
398  precodeL3(last,up,behind,AVertex);
399  else
400  {
401  if ( image.sameVoxelLeftUp(x,y) )
402  if ( image.sameVoxelBehindUp(x,y) )
403  subcasePrecodeFc8(image,x,y,last,up,behind,level,AVertex,FictiveMark,
404  keepFictiveEdges, shiftFictiveEdges);
405  else
406  subcasePrecodeFc2(image,x,y,last,up,behind,level,AVertex,FictiveMark,
407  keepFictiveEdges, shiftFictiveEdges);
408  else
409  if ( image.sameVoxelBehindUp(x,y) )
410  subcasePrecodeFc5(image,x,y,last,up,behind,level,AVertex,FictiveMark,
411  keepFictiveEdges, shiftFictiveEdges);
412  else
413  precodeL3(last,up,behind,AVertex);
414  }
415 }
416 
417 INLINE
418 void CExtractionImage::subcasePrecodeL4( CImage3d & image,
419  unsigned int x, unsigned int y,
420  CDart* &last, CDart* up, CDart* behind,
421  int level, const CVertex & AVertex, int FictiveMark,
422  bool keepFictiveEdges, bool shiftFictiveEdges )
423 {
424  if (level==1)
425  precodeL4(last,up,behind,AVertex);
426  else
427  {
428  if ( image.sameVoxelUpBehind(x,y) )
429  if ( image.sameVoxelLeftBehind(x,y) )
430  subcasePrecodeFc9(image,x,y,last,up,behind,level,AVertex,FictiveMark,
431  keepFictiveEdges, shiftFictiveEdges);
432  else
433  subcasePrecodeFc3(image,x,y,last,up,behind,level,AVertex,FictiveMark,
434  keepFictiveEdges, shiftFictiveEdges);
435  else
436  if ( image.sameVoxelLeftBehind(x,y) )
437  subcasePrecodeFc6(image,x,y,last,up,behind,level,AVertex,FictiveMark,
438  keepFictiveEdges, shiftFictiveEdges);
439  else
440  precodeL4(last,up,behind,AVertex);
441  }
442 }
443 
444 INLINE
445 void CExtractionImage::subcasePrecodeL5( CImage3d & image,
446  unsigned int x, unsigned int y,
447  CDart* &last, CDart* up, CDart* behind,
448  int level, const CVertex & AVertex, int FictiveMark,
449  bool keepFictiveEdges, bool shiftFictiveEdges )
450 {
451  if (level==1)
452  precodeL5(last,up,behind,AVertex);
453  else
454  {
455  if ( image.sameVoxelUpBehind(x,y) )
456  if ( image.sameVoxelUpLeft(x,y) )
457  subcasePrecodeFc16(image,x,y,last,up,behind,level,AVertex,FictiveMark,
458  keepFictiveEdges, shiftFictiveEdges);
459  else
460  subcasePrecodeFc10(image,x,y,last,up,behind,level,AVertex,FictiveMark,
461  keepFictiveEdges, shiftFictiveEdges);
462  else
463  if ( image.sameVoxelUpLeft(x,y) )
464  subcasePrecodeFc13(image,x,y,last,up,behind,level,AVertex,FictiveMark,
465  keepFictiveEdges, shiftFictiveEdges);
466  else
467  precodeL5(last,up,behind,AVertex);
468  }
469 }
470 
471 INLINE
472 void CExtractionImage::subcasePrecodeL6( CImage3d & image,
473  unsigned int x, unsigned int y,
474  CDart* &last, CDart* up, CDart* behind,
475  int level, const CVertex & AVertex, int FictiveMark,
476  bool keepFictiveEdges, bool shiftFictiveEdges )
477 {
478  if (level==1)
479  precodeL6(last,up,behind,AVertex);
480  else
481  {
482  if ( image.sameVoxelBehindLeft(x,y) )
483  if ( image.sameVoxelBehindUp(x,y) )
484  subcasePrecodeFc17(image,x,y,last,up,behind,level,AVertex,FictiveMark,
485  keepFictiveEdges, shiftFictiveEdges);
486  else
487  subcasePrecodeFc11(image,x,y,last,up,behind,level,AVertex,FictiveMark,
488  keepFictiveEdges, shiftFictiveEdges);
489  else
490  if ( image.sameVoxelBehindUp(x,y) )
491  subcasePrecodeFc14(image,x,y,last,up,behind,level,AVertex,FictiveMark,
492  keepFictiveEdges, shiftFictiveEdges);
493  else
494  precodeL6(last,up,behind,AVertex);
495  }
496 }
497 
498 INLINE
499 void CExtractionImage::subcasePrecodeL7( CImage3d & image,
500  unsigned int x, unsigned int y,
501  CDart* &last, CDart* up, CDart* behind,
502  int level, const CVertex & AVertex, int FictiveMark,
503  bool keepFictiveEdges, bool shiftFictiveEdges )
504 {
505  if (level==1)
506  precodeL7(last,up,behind,AVertex);
507  else
508  {
509  if ( image.sameVoxelLeftUp(x,y) )
510  if ( image.sameVoxelLeftBehind(x,y) )
511  subcasePrecodeFc18(image,x,y,last,up,behind,level,AVertex,FictiveMark,
512  keepFictiveEdges, shiftFictiveEdges);
513  else
514  subcasePrecodeFc12(image,x,y,last,up,behind,level,AVertex,FictiveMark,
515  keepFictiveEdges, shiftFictiveEdges);
516  else
517  if ( image.sameVoxelLeftBehind(x,y) )
518  subcasePrecodeFc15(image,x,y,last,up,behind,level,AVertex,FictiveMark,
519  keepFictiveEdges, shiftFictiveEdges);
520  else
521  precodeL7(last,up,behind,AVertex);
522  }
523 }
524 
525 INLINE
526 void CExtractionImage::subcasePrecodeL8( CImage3d & image,
527  unsigned int x, unsigned int y,
528  CDart* &last, CDart* up, CDart* behind,
529  int level, const CVertex & AVertex, int FictiveMark,
530  bool keepFictiveEdges, bool shiftFictiveEdges )
531 {
532  if (level<3)
533  precodeL8(last,up,behind,AVertex);
534  else
535  {
536  if ( image.sameVoxelLeftUp(x,y) )
537  {
538  if ( image.sameVoxelBehindLeft(x,y) )
539  {
540  if ( image.sameVoxelUpbehindLeft(x,y) &&
541  !image.sameVoxelBehindUp(x,y) )
542  {
543  subcasePrecodeF27(image,x,y,last,up,behind,level,AVertex,
544  FictiveMark,keepFictiveEdges,shiftFictiveEdges);
545  }
546  else
547  precodeL8(last,up,behind,AVertex);
548  }
549  else
550  {
551  if ( image.sameVoxelBehindUp(x,y) &&
552  image.sameVoxelLeftbehindUp(x,y) )
553  {
554  subcasePrecodeF25(image,x,y,last,up,behind,level,AVertex,
555  FictiveMark,keepFictiveEdges, shiftFictiveEdges);
556  }
557  else
558  precodeL8(last,up,behind,AVertex);
559  }
560  }
561  else
562  {
563  if ( image.sameVoxelLeftBehind(x,y) &&
564  image.sameVoxelUpBehind(x,y) &&
565  image.sameVoxelLeftupBehind(x,y) )
566  {
567  subcasePrecodeF26(image,x,y,last,up,behind,level,AVertex,
568  FictiveMark,keepFictiveEdges, shiftFictiveEdges);
569  }
570  else
571  precodeL8(last,up,behind,AVertex);
572  }
573  }
574 }
575 
576 } // namespace GMap3d