1 #ifndef __CPEXTENSIONS__DATASTRUCTURES__QUADEDGEMESH__HXX__
2 #define __CPEXTENSIONS__DATASTRUCTURES__QUADEDGEMESH__HXX__
4 // -------------------------------------------------------------------------
5 template< typename P, unsigned int D, typename T >
6 typename cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
7 TPrimalEdge* cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
8 FindEdge( const PointIdentifier& a ) const
10 if( a < this->m_OnextRings.size( ) )
11 return( this->m_OnextRings[ a ] );
16 // -------------------------------------------------------------------------
17 template< typename P, unsigned int D, typename T >
18 typename cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
19 TPrimalEdge* cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
20 FindEdge( const PointIdentifier& a, const PointIdentifier& b ) const
22 TPrimalEdge* found = NULL;
23 TPrimalEdge* e = this->FindEdge( a );
26 typename TPrimalEdge::Iterator eIt = e->BeginOnext( );
27 for( ; eIt != e->EndOnext( ) && found == NULL; eIt++ )
28 if( ( *eIt )->GetDestination( ) == b )
35 // -------------------------------------------------------------------------
36 template< typename P, unsigned int D, typename T >
37 typename cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
38 TPrimalEdge* cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
39 FindEntryEdge( const CellIdentifier& i ) const
41 if( i < this->GetNumberOfCells( ) )
44 this->GetCell( i, c );
46 TQuadEdgeCell* ec = dynamic_cast< TQuadEdgeCell* >( c.GetPointer( ) );
48 return( ec->GetEntryPrimalEdge( ) );
56 // -------------------------------------------------------------------------
57 template< typename P, unsigned int D, typename T >
58 const typename cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
59 CntNormals& cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
60 GetPointNormalsContainer( ) const
62 return( this->m_PointNormals );
65 // -------------------------------------------------------------------------
66 template< typename P, unsigned int D, typename T >
67 typename cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
68 NormalsIterator cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
69 BeginPointNormals( ) const
71 return( this->m_PointNormals.begin( ) );
74 // -------------------------------------------------------------------------
75 template< typename P, unsigned int D, typename T >
76 typename cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
77 NormalsIterator cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
78 EndPointNormals( ) const
80 return( this->m_PointNormals.end( ) );
83 // -------------------------------------------------------------------------
84 template< typename P, unsigned int D, typename T >
85 const typename cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
86 VectorType& cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
87 GetPointNormal( const PointIdentifier& id ) const
89 static const VectorType zero( TScalar( 0 ) );
90 if( id < this->m_PointNormals.size( ) )
91 return( this->m_PointNormals[ id ] );
96 // -------------------------------------------------------------------------
97 template< typename P, unsigned int D, typename T >
98 bool cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
99 RequestedRegionIsOutsideOfTheBufferedRegion( )
101 // Mesh regions don't have meaning with QuadEdges, this is important
102 // in order to guarantee correct pipeline execution
106 // -------------------------------------------------------------------------
107 template< typename P, unsigned int D, typename T >
108 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
109 SetPoints( PointsContainer* points )
111 this->_ReleaseQuadEdgeObjects( );
112 this->m_OnextRings.resize( points->Size( ), NULL );
113 this->m_PointNormals.resize(
114 points->Size( ), VectorType( TScalar( 0 ) )
116 this->Superclass::SetPoints( points );
119 // -------------------------------------------------------------------------
120 template< typename P, unsigned int D, typename T >
121 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
122 SetPoint( PointIdentifier id , PointType point )
124 // If the point is brand new, add some non-existent edges and normals
125 unsigned long N = this->GetNumberOfPoints( );
126 N = ( N < id + 1 )? id + 1: N;
127 if( this->m_OnextRings.size( ) < N )
129 this->m_OnextRings.resize( N, NULL );
130 this->m_PointNormals.resize( N, VectorType( TScalar( 0 ) ) );
135 this->Superclass::SetPoint( id, point );
138 // -------------------------------------------------------------------------
139 template< typename P, unsigned int D, typename T >
140 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
143 this->Superclass::Initialize( );
144 this->_ReleaseQuadEdgeObjects( );
147 // -------------------------------------------------------------------------
148 template< typename P, unsigned int D, typename T >
149 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
150 Graft( const itk::DataObject* data )
152 this->Superclass::Graft( data );
153 const Self* mesh = dynamic_cast< const Self* >( data );
156 this->_ReleaseQuadEdgeObjects( );
157 this->m_PrimalEdges = mesh->m_PrimalEdges;
158 this->m_DualEdges = mesh->m_DualEdges;
159 this->m_OnextRings = mesh->m_OnextRings;
160 this->m_PointNormals = mesh->m_PointNormals;
165 // -------------------------------------------------------------------------
166 template< typename P, unsigned int D, typename T >
167 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
168 SetCells( CellsContainer* cells )
171 if( this->GetCells( ) != NULL )
172 this->SetCells( CellsContainer::New( ) );
173 this->_ReleaseQuadEdgeObjects( );
174 this->m_OnextRings.resize( this->GetNumberOfPoints( ), NULL );
179 for( unsigned long cId = 0; cId < cells->Size( ); ++cId )
181 CellAutoPointer cell( cells->GetElement( cId ), false );
182 this->SetCell( cId, cell );
189 // -------------------------------------------------------------------------
190 template< typename P, unsigned int D, typename T >
191 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
192 SetCellData( CellDataContainer* data )
195 No need for CellData in initial application:
196 how should this be overridden?
200 // -------------------------------------------------------------------------
201 template< typename P, unsigned int D, typename T >
202 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
203 SetCell( CellIdentifier id, CellAutoPointer& ptr )
205 // Overwrite an existing cell?
206 if( id < this->GetNumberOfCells( ) )
209 << "TODO: What do I do here? Trying to overwrite a cell!"
214 // Do not allow to add vertices or edges as cells for the sake of
215 // correct mesh construction
216 if( ptr->GetNumberOfPoints( ) < 3 )
219 << "Face have less than 3 points ("
220 << ptr->GetNumberOfPoints( )
226 // Fill up geometrical prerrequisites
227 if( !( this->_CheckPoints( ptr ) ) )
229 itkExceptionMacro( << "Points missing in the mesh" );
233 // Get (or create) individual edges
235 this->_ConstructEdges( edges, ptr );
237 // Configure new face's geometry
238 edges[ 0 ]->SetLnextRingGeometry( id );
241 typename _TEdges::const_iterator eIt = edges.begin( );
242 for( ; eIt != edges.end( ); ++eIt )
243 this->m_PointNormals[ ( *eIt )->GetOrigin( ) ] =
244 this->_ComputePointNormal( *eIt );
247 TQuadEdgeCell* qcell = new TQuadEdgeCell( edges[ 0 ] );
248 CellAutoPointer cell;
249 cell.TakeOwnership( qcell );
250 this->Superclass::SetCell( id, cell );
253 // -------------------------------------------------------------------------
254 template< typename P, unsigned int D, typename T >
255 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
256 SetCellData( CellIdentifier id, CellPixelType data )
259 No need for CellData in initial application:
260 how should this be overridden?
264 // -------------------------------------------------------------------------
265 template< typename P, unsigned int D, typename T >
266 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
267 BuildCellLinks( ) const
269 // This is no longer required when using QuadEdges
272 // -------------------------------------------------------------------------
273 template< typename P, unsigned int D, typename T >
274 cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
278 this->_ReleaseQuadEdgeObjects( );
281 // -------------------------------------------------------------------------
282 template< typename P, unsigned int D, typename T >
283 cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
286 this->_ReleaseQuadEdgeObjects( );
289 // -------------------------------------------------------------------------
290 template< typename P, unsigned int D, typename T >
291 bool cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
292 _CheckPoints( const CellAutoPointer& ptr ) const
294 const typename Superclass::PointsContainer* pnts = this->GetPoints( );
296 bool all_exist = true;
297 typename CellType::PointIdConstIterator pIt = ptr->PointIdsBegin( );
298 for( ; pIt != ptr->PointIdsEnd( ) && all_exist; ++pIt )
299 all_exist &= pnts->IndexExists( *pIt );
303 // -------------------------------------------------------------------------
304 template< typename P, unsigned int D, typename T >
305 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
306 _DeletePoint( const PointIdentifier& pId )
308 PointIdentifier lastId = this->GetNumberOfPoints( ) - 1;
312 // Modify point container
313 PointType to_delete = this->GetPoint( pId );
314 PointType last = this->GetPoint( lastId );
315 this->Superclass::SetPoint( pId, last );
317 // Modify Onext ring and normals containers
318 this->m_OnextRings[ pId ] = this->m_OnextRings[ lastId ];
319 this->m_PointNormals[ pId ] = this->m_PointNormals[ lastId ];
320 this->m_OnextRings.pop_back( );
321 this->m_PointNormals.pop_back( );
324 typename TPrimalEdge::Iterator oIt =
325 this->m_OnextRings[ pId ]->BeginOnext( );
326 for( ; oIt != this->m_OnextRings[ pId ]->EndOnext( ); ++oIt )
327 ( *oIt )->SetOrigin( pId );
330 this->GetPoints( )->CastToSTLContainer( ).pop_back( );
333 // -------------------------------------------------------------------------
334 template< typename P, unsigned int D, typename T >
335 typename cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
336 TPrimalEdge* cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
337 _CreateQuadEdge( const PointIdentifier& a, const PointIdentifier& b )
339 // Create brand new object
340 typename TPrimalEdge::Pointer edge = TPrimalEdge::New( );
341 edge->CreateRings( );
343 // Configure geometry
344 edge->SetOrigin( a );
345 edge->SetDestination( b );
347 // Keep trace of all reserved memory
348 this->m_PrimalEdges.insert( edge );
349 this->m_PrimalEdges.insert( edge->GetSym( ) );
350 this->m_DualEdges.insert( edge->GetRot( ) );
351 this->m_DualEdges.insert( edge->GetInvRot( ) );
356 // -------------------------------------------------------------------------
357 template< typename P, unsigned int D, typename T >
358 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
359 _DeleteEdge( TPrimalEdge* edge )
361 this->m_DualEdges.erase( edge->GetInvRot( ) );
362 this->m_PrimalEdges.erase( edge->GetSym( ) );
363 this->m_DualEdges.erase( edge->GetRot( ) );
364 this->m_PrimalEdges.erase( edge );
367 // -------------------------------------------------------------------------
368 template< typename P, unsigned int D, typename T >
369 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
370 _DeleteFace( const CellIdentifier& f )
372 unsigned long cellId = this->GetNumberOfCells( ) - 1;
376 // Exchange desired face with last one
377 CellAutoPointer to_delete, last;
378 this->GetCell( f, to_delete );
379 this->GetCell( cellId, last );
380 this->Superclass::SetCell( f, last );
381 this->Superclass::SetCell( cellId, to_delete );
383 // This will delete cell's memory when to_delete is no longer used
384 to_delete.TakeOwnership( );
387 this->GetCells( )->CastToSTLContainer( ).pop_back( );
390 // -------------------------------------------------------------------------
391 template< typename P, unsigned int D, typename T >
392 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
393 _ConstructEdges( _TEdges& edges, const CellAutoPointer& ptr )
396 typename CellType::PointIdConstIterator pIt = ptr->PointIdsBegin( );
397 for( pIt = ptr->PointIdsBegin( ); pIt != ptr->PointIdsEnd( ); ++pIt )
399 typename CellType::PointIdConstIterator nIt = pIt;
401 if( nIt == ptr->PointIdsEnd( ) )
402 nIt = ptr->PointIdsBegin( );
404 TPrimalEdge* edge = this->FindEdge( *pIt, *nIt );
407 edge = this->_CreateQuadEdge( *pIt, *nIt );
408 if( this->m_OnextRings[ *pIt ] != NULL )
410 if( this->m_OnextRings[ *pIt ]->IsOriginInternal( ) )
414 << *pIt << ", " << *nIt << "] is already internal."
419 // Put edge in Onext ring
420 typename TPrimalEdge::Iterator eIt =
421 this->m_OnextRings[ *pIt ]->BeginOnext( );
422 while( eIt != this->m_OnextRings[ *pIt ]->EndOnext( ) )
424 if( !( ( *eIt )->IsLeftSet( ) ) )
426 TPrimalEdge::Splice( *eIt, edge );
427 eIt = this->m_OnextRings[ *pIt ]->EndOnext( );
435 this->m_OnextRings[ *pIt ] = edge;
439 if( edge->IsLeftSet( ) )
443 << edge->GetOrigin( ) << ", "
444 << edge->GetDestination( ) << "] already have a left face ("
446 << "). Face already exits (at least in part)."
452 edges.push_back( edge );
456 // Reorder Onext rings
457 typename _TEdges::iterator ecIt;
458 for( ecIt = edges.begin( ); ecIt != edges.end( ); ++ecIt )
460 TPrimalEdge* e = *ecIt;
462 if( ecIt != edges.begin( ) )
464 typename _TEdges::iterator eOprevIt = ecIt;
466 eOprev = ( *eOprevIt )->GetSym( );
469 eOprev = edges.back( )->GetSym( );
470 TPrimalEdge::ReorderOnextRing( e, eOprev );
475 // -------------------------------------------------------------------------
476 template< typename P, unsigned int D, typename T >
477 typename cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
478 VectorType cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
479 _ComputePointNormal( const TPrimalEdge* e ) const
481 VectorType n( TScalar( 0 ) );
482 if( Superclass::PointDimension == 3 )
484 PointType p0 = this->GetPoint( e->GetOrigin( ) );
485 typename TPrimalEdge::ConstIterator eIt = e->BeginOnext( );
486 unsigned int count = 0;
487 for( ; eIt != e->EndOnext( ); eIt++ )
489 if( ( *eIt )->IsLeftSet( ) )
491 typename TPrimalEdge::ConstIterator nIt = eIt;
493 if( nIt == e->EndOnext( ) )
494 nIt = e->BeginOnext( );
496 VectorType pe = this->GetPoint( ( *eIt )->GetDestination( ) ) - p0;
497 VectorType pn = this->GetPoint( ( *nIt )->GetDestination( ) ) - p0;
498 n[ 0 ] += ( pe[ 1 ] * pn[ 2 ] ) - ( pe[ 2 ] * pn[ 1 ] );
499 n[ 1 ] += ( pe[ 2 ] * pn[ 0 ] ) - ( pe[ 0 ] * pn[ 2 ] );
500 n[ 2 ] += ( pe[ 0 ] * pn[ 1 ] ) - ( pe[ 1 ] * pn[ 0 ] );
506 TScalar nn = n.GetNorm( );
507 if( nn > TScalar( 0 ) && count > 0 )
508 n /= nn * TScalar( count );
514 // -------------------------------------------------------------------------
515 template< typename P, unsigned int D, typename T >
516 void cpExtensions::DataStructures::QuadEdgeMesh< P, D, T >::
517 _ReleaseQuadEdgeObjects( )
519 this->m_PrimalEdges.clear( );
520 this->m_OnextRings.clear( );
521 this->m_DualEdges.clear( );
522 this->m_PointNormals.clear( );
525 #endif // __CPEXTENSIONS__DATASTRUCTURES__QUADEDGEMESH__HXX__