lib/cpm/Algorithms/QuadEdge/MeshEulerOperatorJoinVertexFunction.hxx

   1 #ifndef __CPM__ALGORITHMS__QUADEDGE__MESHEULEROPERATORJOINVERTEXFUNCTION__HXX__
   2 #define __CPM__ALGORITHMS__QUADEDGE__MESHEULEROPERATORJOINVERTEXFUNCTION__HXX__
   3
   4 #include <cpm/Algorithms/QuadEdge/MeshZipFunction.h>
   5
   6 // -------------------------------------------------------------------------
   7 template< class M >
   8 typename
   9 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
  10 TOutput
  11 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
  12 Evaluate( const TInput& e )
  13 {
  14   TStack del_edges;
  15   this->m_EdgeStatus = this->CheckStatus( e, del_edges );
  16
  17   TOutput out;
  18   switch( this->m_EdgeStatus )
  19   {
  20   case Self::STANDARD_CONFIG:   out = this->Process( e ); break;
  21   case Self::QUADEDGE_ISOLATED: out = this->ProcessQuadEdge( e ); break;
  22   case Self::FACE_ISOLATED:     out = this->ProcessFace( e, del_edges ); break;
  23   default:                      out = NULL; break;
  24     /* TODO:
  25        case Self::EDGE_NULL:
  26        // this->m_Mesh == 0
  27        case Self::MESH_NULL:
  28        // e->IsIsolated( ) && e_sym->IsIsolated( )
  29        case Self::EDGE_ISOLATED:
  30        // more than 2 common vertices in 0-ring of org and dest respectively
  31        case Self::TOO_MANY_COMMON_VERTICES:
  32        // Tetrahedron case
  33        case Self::TETRAHEDRON_CONFIG:
  34        // Samosa case
  35        case Self::SAMOSA_CONFIG:
  36        // Eye case
  37        case Self::EYE_CONFIG:
  38        return( NULL );
  39        case Self::EDGE_JOINING_DIFFERENT_BORDERS:
  40        return( NULL );
  41     */
  42   } // hctiws
  43   return( out );
  44 }
  45
  46 // -------------------------------------------------------------------------
  47 template< class M >
  48 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
  49 MeshEulerOperatorJoinVertexFunction( )
  50   : Superclass( ),
  51     m_OldPointID( 0 ),
  52     m_EdgeStatus( Self::STANDARD_CONFIG )
  53 {
  54 }
  55
  56 // -------------------------------------------------------------------------
  57 template< class M >
  58 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
  59 ~MeshEulerOperatorJoinVertexFunction( )
  60 {
  61 }
  62
  63 // -------------------------------------------------------------------------
  64 template< class M >
  65 typename
  66 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
  67 TPointId
  68 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
  69 CommonVertexNeighboor( TEdge* e )
  70 {
  71   TEdge* qe = e;
  72   TEdge* e_it  = qe->GetOnext( );
  73
  74   typedef std::list< TPointId > TPointIdList;
  75   TPointIdList dir_list;
  76   TPointIdList sym_list;
  77   TPointIdList intersection_list;
  78
  79   TPointId id;
  80   do
  81   {
  82     id = e_it->GetDestination( );
  83     dir_list.push_back( id );
  84     e_it = e_it->GetOnext( );
  85   }
  86   while( e_it != qe );
  87
  88   qe = qe->GetSym( );
  89   e_it = qe;
  90
  91   do
  92   {
  93     id = e_it->GetDestination( );
  94     sym_list.push_back( id );
  95     e_it = e_it->GetOnext( );
  96   }
  97   while( e_it != qe );
  98
  99   dir_list.sort( );
 100   sym_list.sort( );
 101
 102   std::set_intersection(
 103     dir_list.begin( ), dir_list.end( ),
 104     sym_list.begin( ), sym_list.end( ),
 105     std::back_inserter( intersection_list )
 106     );
 107
 108   return( static_cast< TPointId >( intersection_list.size( ) ) );
 109 }
 110
 111 // -------------------------------------------------------------------------
 112 template< class M >
 113 bool
 114 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
 115 IsTetrahedron( TEdge* e )
 116 {
 117   typedef typename M::CellIdentifier _TCellId;
 118   if( true /* TODO: e->GetOrder( ) == 3 */ )
 119   {
 120     TEdge* e_sym = e->GetSym( );
 121     if( true /* TODO e_sym->GetOrder( ) == 3 */ )
 122     {
 123       if( true /* TODO e->GetLprev( )->GetOrder( ) == 3 */ )
 124       {
 125         if( true /* TODO e_sym->GetLprev( )->GetOrder( ) == 3 */ )
 126         {
 127           bool left_triangle; // TODO: = e->IsLnextOfTriangle( );
 128           bool right_triangle; // TODO: = e_sym->IsLnextOfTriangle( );
 129
 130           if( left_triangle && right_triangle )
 131           {
 132             _TCellId id_left_right_triangle;
 133             if( e->GetLprev( )->IsRightSet( ) )
 134               id_left_right_triangle = e->GetLprev( )->GetRight( );
 135             else
 136               return( false );
 137
 138             _TCellId id_left_left_triangle;
 139             if( e->GetLnext( )->IsRightSet( ) )
 140               id_left_left_triangle = e->GetLnext( )->GetRight( );
 141             else
 142               return( false );
 143
 144             _TCellId id_right_left_triangle;
 145             if( e_sym->GetLnext( )->IsRightSet( ) )
 146               id_right_left_triangle = e_sym->GetLnext( )->GetRight( );
 147             else
 148               return( false );
 149
 150             _TCellId id_right_right_triangle;
 151             if( e_sym->GetLprev( )->IsRightSet( ) )
 152               id_right_right_triangle = e_sym->GetLprev( )->GetRight( );
 153             else
 154               return( false );
 155
 156             return(
 157               ( id_left_right_triangle == id_right_left_triangle ) &&
 158               ( id_left_left_triangle == id_right_right_triangle )
 159               );
 160
 161           } // fi
 162
 163         } // fi
 164
 165       } // fi
 166
 167     } // fi
 168
 169   } // fi
 170   return( false );
 171 }
 172
 173 // -------------------------------------------------------------------------
 174 template< class M >
 175 bool
 176 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
 177 IsFaceIsolated( TEdge* e, bool iWasLeftFace, TStack& oToBeDeleted )
 178 {
 179   bool border;
 180   TEdge* e_sym = e->GetSym( );
 181
 182   // turn around the face( left or right one ) while edges are on the border
 183   // and push them into a stack( which will be used to delete properly all
 184   // elements )
 185   TEdge* temp =( iWasLeftFace == true )? e: e_sym;
 186   TEdge* e_it = temp;
 187
 188   oToBeDeleted.push( e_it );
 189   e_it = e_it->GetLnext( );
 190   do
 191   {
 192     oToBeDeleted.push( e_it );
 193     border = e_it->IsAtBorder( );
 194     e_it = e_it->GetLnext( );
 195   }
 196   while( ( e_it != temp ) && border );
 197
 198   return( border );
 199 }
 200
 201 // -------------------------------------------------------------------------
 202 template< class M >
 203 bool
 204 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
 205 IsSamosa( TEdge* e )
 206 {
 207   // TODO return( ( e->GetOrder( ) == 2 ) && ( e->GetSym( )->GetOrder( ) == 2 ) );
 208   return( false );
 209 }
 210
 211 // -------------------------------------------------------------------------
 212 template< class M >
 213 bool
 214 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
 215 IsEye( TEdge* e )
 216 {
 217   bool OriginOrderIsTwo; // TODO =( e->GetOrder( ) == 2 );
 218   bool DestinationOrderIsTwo; // TODO =( e->GetSym( )->GetOrder( ) == 2 );
 219
 220   return(
 221     (  OriginOrderIsTwo && !DestinationOrderIsTwo ) ||
 222     ( !OriginOrderIsTwo &&  DestinationOrderIsTwo )
 223     );
 224 }
 225
 226 // -------------------------------------------------------------------------
 227 template< class M >
 228 bool
 229 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
 230 IsEdgeLinkingTwoDifferentBorders( TEdge* e )
 231 {
 232   TEdge* t = e;
 233   TEdge* e_it = t;
 234   bool org_border;
 235
 236   do
 237   {
 238     org_border = e_it->IsAtBorder( );
 239     e_it = e_it->GetOnext( );
 240   }
 241   while( ( e_it != t ) &&( !org_border ) );
 242   if( org_border )
 243   {
 244     t = e->GetSym( );
 245     e_it = t;
 246     bool dest_border;
 247     do
 248     {
 249       dest_border = e_it->IsAtBorder( );
 250       e_it = e_it->GetOnext( );
 251     }
 252     while( ( e_it != t ) &&( !dest_border ) );
 253
 254     return( dest_border );
 255   }
 256   else
 257     return( false );
 258 }
 259
 260 // -------------------------------------------------------------------------
 261 template< class M >
 262 typename
 263 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
 264 TEdgeStatus
 265 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
 266 CheckStatus( TEdge* e, TStack& oToBeDeleted )
 267 {
 268   TEdge* e_sym = e->GetSym( );
 269
 270   bool IsEdgeIsolated = e->IsIsolated( );
 271   bool IsSymEdgeIsolated = e_sym->IsIsolated( );
 272   if( IsEdgeIsolated || IsSymEdgeIsolated )
 273   {
 274     if( IsEdgeIsolated && IsSymEdgeIsolated )
 275     {
 276       // We could shrink the edge to a point,
 277       // But we consider this case to be degenerated.
 278       itkDebugMacro( "Argument edge isolated." );
 279       return( Self::EDGE_ISOLATED );
 280
 281     } // fi
 282
 283     // One the endpoints( and only one ) of the incoming edge is isolated.
 284     // Instead of "shrinking" the edge it suffice to delete it. Note that
 285     // this also avoids trouble since the definition of leftZip or rightZip
 286     // would be improper in this case( in fact leftZip or rightZip would
 287     // in fact be e or e->GetSym( )...
 288     //
 289     // When e is adjacent to a face, we must retrieve the edge [ a, b ]
 290     // in order to rebuild the face after edge deletion. If the left face
 291     // of e is set then the right face is also set... since it is the same
 292     // face ! Here is the situation:
 293     //
 294     //        b----a----X
 295     //        |    |    |
 296     //        |    e    |
 297     //        |    |    |
 298     //        |         |
 299     //        X----X----X
 300     //
 301     // We are not yet sure of the orientation of e and which endpoint
 302     // of e is attached in a.
 303     return( Self::QUADEDGE_ISOLATED );
 304   }
 305
 306   TPointId number_common_vertices = this->CommonVertexNeighboor( e );
 307   if( number_common_vertices > 2 )
 308   {
 309     itkDebugMacro(
 310       "The 2 vertices have more than 2 common neighboor vertices."
 311       );
 312     return( Self::TOO_MANY_COMMON_VERTICES );
 313
 314   } // fi
 315
 316   if( number_common_vertices == 2 )
 317   {
 318     if( this->IsTetrahedron( e ) )
 319     {
 320       itkDebugMacro( "It forms a tetrahedron." );
 321       return( Self::TETRAHEDRON_CONFIG );
 322
 323     } // fi
 324
 325   } // fi
 326
 327   // General case
 328   bool wasLeftFace = e->IsLeftSet( );
 329   bool wasRightFace = e->IsRightSet( );
 330
 331   if( wasLeftFace && wasRightFace )
 332   {
 333     if( this->IsSamosa( e ) )
 334     {
 335       itkDebugMacro( "Self::SAMOSA_CONFIG." );
 336       return( Self::SAMOSA_CONFIG );
 337
 338     } // fi
 339     if( this->IsEye( e ) )
 340     {
 341       itkDebugMacro( "Self::EYE_CONFIG." );
 342       return( Self::EYE_CONFIG );
 343
 344     } // fi
 345     if( this->IsEdgeLinkingTwoDifferentBorders( e ) )
 346     {
 347       itkDebugMacro( "Self::EDGE_JOINING_DIFFERENT_BORDERS." );
 348       return( Self::EDGE_JOINING_DIFFERENT_BORDERS );
 349
 350     } // fi
 351   }
 352   else
 353   {
 354     if( wasLeftFace || wasRightFace )
 355     {
 356       if( this->IsFaceIsolated( e, wasLeftFace, oToBeDeleted ) )
 357       {
 358         itkDebugMacro( "Self::FACE_ISOLATED." );
 359         return( Self::FACE_ISOLATED );
 360
 361       } // fi
 362
 363     } // fi
 364
 365   } // fi
 366   return( Self::STANDARD_CONFIG );
 367 }
 368
 369 // -------------------------------------------------------------------------
 370 template< class M >
 371 typename
 372 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
 373 TEdge*
 374 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
 375 Process( TEdge* e )
 376 {
 377   TEdge* e_sym = e->GetSym( );
 378
 379   // General case
 380   bool wasLeftFace     = e->IsLeftSet( );
 381   bool wasRightFace     = e->IsRightSet( );
 382   bool wasLeftTriangle; // TODO = e->IsLnextOfTriangle( );
 383   bool wasRightTriangle; // TODO = e_sym->IsLnextOfTriangle( );
 384
 385   TPointId NewDest = e->GetDestination( );
 386   TPointId NewOrg  = e->GetOrigin( );
 387   TEdge* leftZip = e->GetLnext( );
 388   TEdge* rightZip = e->GetOprev( );
 389
 390   //
 391   //                    \   |   /                //
 392   //                     \  |  /                 //
 393   //                      \ | /                  //
 394   //     ------------------ b ------------- Y    //
 395   //                   ___/ |               |    //
 396   //      _<_leftZip__/     |               |    //
 397   //     /                  ^               |    //
 398   //    X      left         e     right     |    //
 399   //     \____________      |               |    //
 400   //                  \___  |               |    //
 401   //                      \ |               |    //
 402   //     ------------------ a -rightZip->-- Y    //
 403   //                      / | \                  //
 404   //                     /  |  \                 //
 405   //                    /   |   \                //
 406   //
 407   // TODO: this->m_Mesh->LightWeightDeleteEdge( e );
 408   // TODO: this->m_OldPointID = this->m_Mesh->Splice( leftZip, rightZip );
 409
 410   //
 411   //                            |      /       __Y  //
 412   //                            |     /     __/  |  //
 413   //       __<_leftZip___       |    /   __/     |  //
 414   //      /              \      |   / __/        |  //
 415   //     /                \__   |  / /           |  //
 416   //    X      NOFACE      __ [a = b]    NOFACE  |  //
 417   //     \                /  / / | \ \__         |  //
 418   //      \______________/ _/ /  |  \   \__      |  //
 419   //                    __/  /   |   \ rightZip  |  //
 420   //                 __/    /    |    \       \__|  //
 421   //                /      /     |     \         Y  //
 422   //
 423   // When the Lnext and/or the Rnext ring of the argument edge was originally
 424   // the one[s] of a triangle, the above edge deletion created the odd
 425   // situation of having two different edges adjacent to the same two
 426   // vertices( which is quite a bad thing ). This is was is depicted on
 427   // the above ascii-graph, the original left face was a triangle and
 428   // the resulting situation has two different edges adjacent to the
 429   // two vertices X and a. In order to clean up things, we can call the
 430   // Zip( MeshFunction ) algorithm which handles this case.
 431   // Once things are back to normal, we recreate faces when they were
 432   // originally present.
 433   //
 434
 435   typedef MeshZipFunction< M > _TZip;
 436   if( wasLeftTriangle )
 437   {
 438     typename _TZip::Pointer zip = _TZip::New( );
 439     zip->SetMesh( this->m_Mesh );
 440     if( TEdge::NoGeometry != zip->Evaluate( leftZip ) )
 441     {
 442       itkDebugMacro( "Zip must return NoPoint( left )." );
 443       return( NULL );
 444
 445     } // fi
 446   }
 447   else
 448   {
 449     /* TODO
 450        if( wasLeftFace )
 451        this->m_Mesh->AddFace( leftZip );
 452     */
 453   } // fi
 454
 455   // NewOrg = rightZip->GetOprev( )->GetDestination( );
 456   if( wasRightTriangle )
 457   {
 458     NewOrg = rightZip->GetDestination( );
 459     typename _TZip::Pointer zip = _TZip::New( );
 460     zip->SetMesh( this->m_Mesh );
 461     if( TEdge::NoGeometry != zip->Evaluate( rightZip ) )
 462     {
 463       itkDebugMacro( "Zip must return NoPoint( right )." );
 464       return( NULL );
 465
 466     } // fi
 467   }
 468   else
 469   {
 470     NewOrg = rightZip->GetLprev( )->GetOrigin( );
 471     /* TODO
 472        if( wasRightFace )
 473        this->m_Mesh->AddFace( rightZip );
 474     */
 475   } // fi
 476
 477   TOutput result = this->m_Mesh->FindEdge( NewOrg, NewDest );
 478   if( !result )
 479     result = this->m_Mesh->FindEdge( NewDest )->GetSym( );
 480   return( result );
 481 }
 482
 483 // -------------------------------------------------------------------------
 484 template< class M >
 485 typename
 486 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
 487 TEdge*
 488 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
 489 ProcessQuadEdge( TEdge* e )
 490 {
 491   TEdge* temp = ( e->IsIsolated( ) == true )? e->GetSym( ): e;
 492   TEdge* rebuildEdge = temp->GetOprev( );
 493
 494   this->m_OldPointID = temp->GetSym( )->GetOrigin( );
 495
 496   bool e_leftset = e->IsLeftSet( );
 497   // TODO: this->m_Mesh->LightWeightDeleteEdge( e );
 498   /* TODO:
 499      if( e_leftset )
 500      this->m_Mesh->AddFace( rebuildEdge );
 501   */
 502
 503   // this case has no symetric case in SPlitVertex
 504   // i.e. it is impossible to reconstruct such a pathological
 505   // case using SplitVertex. Thus the return value is
 506   // of less interest.
 507   // We return an edge whose dest is a, whichever.
 508   return( rebuildEdge );
 509 }
 510
 511 // -------------------------------------------------------------------------
 512 template< class M >
 513 typename
 514 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
 515 TEdge*
 516 cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
 517 ProcessFace( TEdge* e, TStack& EdgesToBeDeleted )
 518 {
 519   TPointId org = e->GetOrigin( );
 520   TPointId dest = e->GetDestination( );
 521
 522   // delete all elements
 523   while( !EdgesToBeDeleted.empty( ) )
 524   {
 525     // TODO: this->m_Mesh->LightWeightDeleteEdge( EdgesToBeDeleted.top( ) );
 526     EdgesToBeDeleted.pop( );
 527   }
 528
 529   // it now retuns one edge from NewDest or NewOrg if there are any
 530   // else NULL
 531   TEdge* temp = this->m_Mesh->FindEdge( dest );
 532   if( temp != NULL )
 533     return( temp );
 534   else
 535     return( this->m_Mesh->FindEdge( org ) );
 536 }
 537
 538 #endif
 539 // __CPM__ALGORITHMS__QUADEDGE__MESHEULEROPERATORJOINVERTEXFUNCTION__HXX__
 540
 541 // eof - $RCSfile$