Main Page   Class Hierarchy   Compound List   File List   Compound Members  

geMeshWingedEdge.h

00001 //////////////////////////////////////////////////////////////////////
00002 // Copyright (c) 2002-2003 David Pritchard <drpritch@alumni.uwaterloo.ca>
00003 // 
00004 // This program is free software; you can redistribute it and/or
00005 // modify it under the terms of the GNU Lesser General Public License
00006 // as published by the Free Software Foundation; either
00007 // version 2 of the License, or (at your option) any later
00008 // version.
00009 // 
00010 // This program is distributed in the hope that it will be useful,
00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013 // GNU Lesser General Public License for more details.
00014 // 
00015 // You should have received a copy of the GNU Lesser General Public License
00016 // along with this program; if not, write to the Free Software
00017 // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00018 
00019 #ifndef freecloth_geom_geMeshWingedEdge_h
00020 #define freecloth_geom_geMeshWingedEdge_h
00021 
00022 #ifndef freecloth_geom_package_h
00023 #include <freecloth/geom/package.h>
00024 #endif
00025 
00026 #ifndef freecloth_geom_geMesh_h
00027 #include <freecloth/geom/geMesh.h>
00028 #endif
00029 
00030 #ifndef freecloth_resmgt_rcBase_h
00031 #include <freecloth/resmgt/rcBase.h>
00032 #endif
00033 
00034 #ifndef freecloth_resmgt_rcShdPtr_h
00035 #include <freecloth/resmgt/rcShdPtr.h>
00036 #endif
00037 
00038 #ifndef freecloth_base_vector
00039 #include <freecloth/base/vector>
00040 #endif
00041 
00042 FREECLOTH_NAMESPACE_START
00043 
00044 ////////////////////////////////////////////////////////////////////////////////
00045 // FORWARD DECLARATIONS
00046 
00047 template <class T> class RCShdPtr;
00048 
00049 ////////////////////////////////////////////////////////////////////////////////
00050 /*!
00051  * \class GeMeshWingedEdge freecloth/geom/geMeshWingedEdge.h
00052  * \brief Add-on for GeMesh class to store winged-edge data structure.
00053  *
00054  * Allows more general traversal of a mesh. The winged-edge representation
00055  * focuses on an entity known as the "half edge," where each edge separating
00056  * two faces of the mesh is represented by two independent twinned half-edges,
00057  * one associated with each face. Each half edge points from an "origin" vertex
00058  * to a "tip" vertex, in a counter-clockwise direction within the face.
00059  *
00060  * In computational geometry, the "planar subdivision" data structure operates
00061  * in a similar manner in two dimensions, but adds a special face for the
00062  * outside world beyond the mesh. We do not have any such outside face, and
00063  * there may yet be some bugs in the code due to this limitation.
00064  *
00065  * This approach can only handle a limited set of topologies. Disc and
00066  * sphere topology should be fine. Only one component is allowed, and faces
00067  * must all point in the same direction. There aren't much of any assertions to
00068  * enforce this.
00069  *
00070  * Using the winged-edge data structure, we can easily
00071  * - retrieve edges associated with a vertex or face
00072  * - retrieve faces associated with an edge
00073  *
00074  * We allow iteration over both half-edges and "edges". Edge iteration
00075  * still iterates over half-edge objects; it just changes the iteration
00076  * metaphor to only include one of each pair of twinned half-edges.
00077  *
00078  * The winged edge data structure extends the standard mesh data structure,
00079  * and we hence keep a pointer to the source mesh. The winged edge data is only
00080  * dependent upon the mesh topology, which is immutable after construction.
00081  *
00082  * Wrapper/ConstIterator classes are direct rips of
00083  * GeMesh::FaceWrapper / ConstIterator. Some day, I should try to make a
00084  * general-purpose class to do this stuff...
00085  */
00086 
00087 // FIXME: should we just derive off of GeMesh, and allow GeMeshBuilder to
00088 // construct one or the other off the bat?
00089 // RCBase must be first parent. See GeMesh.
00090 class GeMeshWingedEdge : public RCBase, public GeMeshTypes
00091 {
00092 public:
00093 
00094     // ----- classes -----
00095     //! Half edge facade class
00096     class HalfEdgeWrapper;
00097     //! Iterator for edges/halfedges.
00098     template <bool HALF> class EdgeIteratorBase;
00099     //! Iterator for edges/halfedges incident on vertex.
00100     template <bool HALF> class VertexEdgeIteratorBase;
00101     //! Iterator for faces touching vertex.
00102     class VertexFaceIterator;
00103 
00104     // All are const iterators.
00105     //! Half edge iterator class.
00106     typedef EdgeIteratorBase<true> HalfEdgeIterator;
00107     //! Edge iterator class.
00108     typedef EdgeIteratorBase<false> EdgeIterator;
00109     //! Iterator for halfedges incident on vertex
00110     typedef VertexEdgeIteratorBase<true> VertexHalfEdgeIterator;
00111     //! Iterator for edges incident on vertex
00112     typedef VertexEdgeIteratorBase<false> VertexEdgeIterator;
00113 
00114     // ----- types and enumerations -----
00115 
00116     //! Half edge index
00117     typedef UInt32          HalfEdgeId;
00118     //! Half edge facade class
00119     typedef HalfEdgeWrapper HalfEdgeType;
00120 
00121     // ----- member functions -----
00122     explicit GeMeshWingedEdge( const RCShdPtr<GeMesh>& );
00123 
00124     UInt32 getNbHalfEdges() const;
00125     HalfEdgeType getHalfEdge( HalfEdgeId ) const;
00126 
00127     HalfEdgeIterator beginHalfEdge() const;
00128     HalfEdgeIterator endHalfEdge() const;
00129     EdgeIterator beginEdge() const;
00130     EdgeIterator endEdge() const;
00131 
00132     //! Iterate over half-edges whose origin is vertexId. Note that this may
00133     //! not include all edges - any vertex that lies on the boundary will
00134     //! have two edges w/o twins, and one of these will not be included.
00135     VertexHalfEdgeIterator beginVertexHalfEdge( VertexId ) const;
00136     VertexHalfEdgeIterator endVertexHalfEdge( VertexId ) const;
00137 
00138     //!! Iterate over all edges that touch vertexId. This will only iterate once
00139     // over each half-edge pair.
00140     VertexEdgeIterator beginVertexEdge( VertexId ) const;
00141     VertexEdgeIterator endVertexEdge( VertexId ) const;
00142 
00143     VertexFaceIterator beginVertexFace( VertexId ) const;
00144     VertexFaceIterator endVertexFace( VertexId ) const;
00145 
00146     //HalfEdgeId getHalfEdgeFromVertexId( VertexId ) const;
00147     HalfEdgeId getHalfEdgeFromFaceId( FaceId ) const;
00148 
00149     const RCShdPtr<GeMesh>& getMeshPtr() const;
00150     const GeMesh& getMesh() const;
00151 
00152 private:
00153 
00154     // ----- classes -----
00155     class HalfEdge;
00156     typedef std::vector< HalfEdge > HalfEdgeContainer;
00157 
00158     // ----- friends -----
00159     friend class HalfEdgeWrapper;
00160 #ifdef HAVE_TEMPLATE_FRIENDS
00161     template <bool HALF> friend class VertexEdgeIteratorBase;
00162 #else
00163     friend class VertexEdgeIteratorBase<false>;
00164     friend class VertexEdgeIteratorBase<true>;
00165 #endif
00166     friend class VertexFaceIterator;
00167 
00168     // ----- member functions -----
00169     //! Construction-time function to fill data members.
00170     void build( const GeMesh& );
00171 
00172     // ----- data members -----
00173     RCShdPtr<GeMesh> _mesh;
00174     HalfEdgeContainer   _halfEdges;
00175     //! Array containing the index of one half-edge for each vertex.
00176     std::vector< HalfEdgeId > _vertexHalfEdgeIds;
00177     //! Array containing the index of one half-edge for each face.
00178     std::vector< HalfEdgeId > _faceHalfEdgeIds;
00179 };
00180 
00181 
00182 ////////////////////////////////////////////////////////////////////////////////
00183 /*!
00184  * \class GeMeshWingedEdge::HalfEdge freecloth/geom/geMeshWingedEdge.h
00185  * \brief Half-edge data structure.
00186  * This is a private class, only used for data storage. The HalfEdgeWrapper
00187  * class is a facade that is exposed to clients.
00188  */
00189 class GeMeshWingedEdge::HalfEdge {
00190 public:
00191     // ----- types and enumerations -----
00192     enum { ID_INVALID = ~0U };
00193 
00194     // ----- member functions -----
00195     HalfEdge();
00196     HalfEdge(
00197         VertexId origin,
00198         HalfEdgeId twin,
00199         FaceId face,
00200         HalfEdgeId next
00201     );
00202     // Default copy constructor is fine.
00203     // Default assignment operator is fine.
00204 
00205     VertexId getOriginVertexId() const;
00206     HalfEdgeId getTwinHalfEdgeId() const;
00207     FaceId getFaceId() const;
00208     HalfEdgeId getNextHalfEdgeId() const;
00209 
00210     bool hasTwin() const;
00211 
00212 private:
00213 
00214     // ----- friends -----
00215     friend class GeMeshWingedEdge;
00216 
00217     // ----- data members -----
00218     VertexId _origin;
00219     HalfEdgeId _twin;
00220     FaceId _face;
00221     HalfEdgeId _next;
00222     // No need for a previous edge member - since all faces are triangular,
00223     // this can be easily found.
00224 };
00225 
00226 
00227 ////////////////////////////////////////////////////////////////////////////////
00228 /*!
00229  * \class GeMeshWingedEdge::HalfEdgeWrapper freecloth/geom/geMeshWingedEdge.h
00230  * \brief Facade class for access to half edge data, while drawing on
00231  * information from the vertex and texture vertex arrays.
00232  *
00233  * Each face contains indices into the vertex and texture vertex arrays.
00234  * From the vertices, other information can be calculated.
00235  *
00236  * At present, all faces are triangular.
00237  *
00238  * \pattern Facade
00239  */
00240 class GeMeshWingedEdge::HalfEdgeWrapper : public GeMeshTypes
00241 {
00242 public:
00243     // ----- member functions -----
00244     HalfEdgeWrapper( const GeMeshWingedEdge&, HalfEdgeId );
00245     // Default copy constructor is fine.
00246 
00247     HalfEdgeId getHalfEdgeId() const;
00248 
00249     //! Get id of vertex at origin of this half-edge
00250     VertexId getOriginVertexId() const;
00251     const VertexType& getOriginVertex() const;
00252     //! Get id of vertex at tip of this half-edge
00253     VertexId getTipVertexId() const;
00254     const VertexType& getTipVertex() const;
00255     //! Get id of vertex opposite this half-edge
00256     VertexId getOppositeVertexId() const;
00257     const VertexType& getOppositeVertex() const;
00258 
00259     HalfEdgeId getTwinHalfEdgeId() const;
00260     HalfEdgeWrapper getTwinHalfEdge() const;
00261     FaceId getFaceId() const;
00262     GeMesh::FaceWrapper getFace() const;
00263     HalfEdgeId getNextHalfEdgeId() const;
00264     HalfEdgeWrapper getNextHalfEdge() const;
00265     HalfEdgeId getPrevHalfEdgeId() const;
00266     HalfEdgeWrapper getPrevHalfEdge() const;
00267 
00268     bool hasTwin() const;
00269 
00270 private:
00271     // ----- friends -----
00272 #ifdef HAVE_TEMPLATE_FRIENDS
00273     template <bool HALF> friend class GeMeshWingedEdge::EdgeIteratorBase;
00274     template <bool HALF> friend class GeMeshWingedEdge::VertexEdgeIteratorBase;
00275 #else
00276     friend class GeMeshWingedEdge::EdgeIteratorBase<false>;
00277     friend class GeMeshWingedEdge::EdgeIteratorBase<true>;
00278     friend class GeMeshWingedEdge::VertexEdgeIteratorBase<false>;
00279     friend class GeMeshWingedEdge::VertexEdgeIteratorBase<true>;
00280 #endif
00281     friend class VertexFaceIterator;
00282 
00283     // ----- member functions -----
00284 
00285     //! For use by iterator - only it can construct an invalid wrapper.
00286     HalfEdgeWrapper();
00287     HalfEdgeWrapper( const GeMeshWingedEdge*, HalfEdgeId );
00288     bool isValid() const;
00289     const GeMeshWingedEdge& getMeshWE() const;
00290     const GeMesh& getMesh() const;
00291 
00292     // ----- data members -----
00293 
00294     //! This must be a pointer to allow modification by the iterator classes.
00295     const GeMeshWingedEdge* _meshwe;
00296     HalfEdgeId              _halfEdgeId;
00297 };
00298 
00299 
00300 ////////////////////////////////////////////////////////////////////////////////
00301 /*!
00302  * \class GeMeshWingedEdge::EdgeIteratorBase freecloth/geom/geMeshWingedEdge.h
00303  * \brief Class for both edge and halfedge iterators.
00304  *
00305  * Template parameter HALF is true for halfedge iterator, false for edge
00306  * iterator.
00307  * 
00308  * \pattern Iterator
00309  *
00310  */
00311 template <bool HALF>
00312 class GeMeshWingedEdge::EdgeIteratorBase : public GeMeshTypes {
00313 
00314 public:
00315     // ----- static member functions -----
00316     //! Named constructor
00317     //! @{
00318     static EdgeIteratorBase begin( const GeMeshWingedEdge& );
00319     static EdgeIteratorBase end( const GeMeshWingedEdge& );
00320     //! @}
00321 
00322     // ----- member functions -----
00323     EdgeIteratorBase();
00324     EdgeIteratorBase( const GeMeshWingedEdge&, HalfEdgeId );
00325     // Default copy constructor is fine.
00326     // Default assignment operator is fine.
00327 
00328     EdgeIteratorBase& operator++();
00329     EdgeIteratorBase operator++( int );
00330 
00331     bool operator==( const EdgeIteratorBase& ) const;
00332     bool operator!=( const EdgeIteratorBase& ) const;
00333 
00334     const HalfEdgeWrapper& operator*() const;
00335     const HalfEdgeWrapper* operator->() const;
00336 
00337 private:
00338     // ----- member functions -----
00339     explicit EdgeIteratorBase( const HalfEdgeWrapper& );
00340 
00341     // ----- data members -----
00342     GeMeshWingedEdge::HalfEdgeWrapper _wrapper;
00343 };
00344 
00345 
00346 ////////////////////////////////////////////////////////////////////////////////
00347 /*!
00348  * \class GeMeshWingedEdge::VertexEdgeIteratorBase freecloth/geom/geMeshWingedEdge.h
00349  * \brief Class for both edge and halfedge iterators touching a vertex.
00350  *
00351  * Template parameter HALF is true for halfedge iterator, false for edge
00352  * iterator.
00353  *
00354  * \pattern Iterator
00355  */
00356 template <bool HALF>
00357 class GeMeshWingedEdge::VertexEdgeIteratorBase : public GeMeshTypes {
00358 
00359 public:
00360     // ----- static member functions -----
00361     //! Named constructor
00362     //! @{
00363     static VertexEdgeIteratorBase begin(
00364         const GeMeshWingedEdge&,
00365         VertexId vertexId
00366     );
00367     static VertexEdgeIteratorBase end(
00368         const GeMeshWingedEdge&,
00369         VertexId vertexId
00370     );
00371     //! @}
00372 
00373     // ----- member functions -----
00374     VertexEdgeIteratorBase();
00375     VertexEdgeIteratorBase(
00376         const GeMeshWingedEdge&,
00377         VertexId vertexId,
00378         HalfEdgeId halfEdgeId
00379     );
00380     // Default copy constructor is fine.
00381     // Default assignment operator is fine.
00382 
00383     VertexEdgeIteratorBase& operator++();
00384     VertexEdgeIteratorBase operator++( int );
00385 
00386     bool operator==( const VertexEdgeIteratorBase& ) const;
00387     bool operator!=( const VertexEdgeIteratorBase& ) const;
00388 
00389     const HalfEdgeWrapper& operator*() const;
00390     const HalfEdgeWrapper* operator->() const;
00391 
00392 private:
00393     // ----- types and enumerations-----
00394     enum {
00395         ID_INVALID = GeMeshWingedEdge::HalfEdge::ID_INVALID
00396     };
00397 
00398     // ----- member functions -----
00399     VertexEdgeIteratorBase( const HalfEdgeWrapper&, VertexId );
00400 
00401     // ----- data members -----
00402     GeMeshWingedEdge::HalfEdgeWrapper _wrapper;
00403     VertexId _vertexId;
00404 };
00405 
00406 
00407 ////////////////////////////////////////////////////////////////////////////////
00408 /*!
00409  * \class GeMeshWingedEdge::VertexFaceIterator freecloth/geom/geMeshWingedEdge.h
00410  * \brief Class for iterating over faces touching a vertex.
00411  *
00412  * \pattern Iterator
00413  */
00414 class GeMeshWingedEdge::VertexFaceIterator : public GeMeshTypes {
00415 
00416 public:
00417     // ----- static member functions -----
00418     // Named constructors
00419     static VertexFaceIterator begin(
00420         const GeMeshWingedEdge&,
00421         VertexId vertexId
00422     );
00423     static VertexFaceIterator end(
00424         const GeMeshWingedEdge&,
00425         VertexId vertexId
00426     );
00427 
00428     // ----- member functions -----
00429     VertexFaceIterator();
00430     VertexFaceIterator(
00431         const GeMeshWingedEdge&,
00432         VertexId vertexId,
00433         HalfEdgeId halfEdgeId
00434     );
00435     // Default copy constructor is fine.
00436     // Default assignment operator is fine.
00437 
00438     VertexFaceIterator& operator++();
00439     VertexFaceIterator operator++( int );
00440 
00441     bool operator==( const VertexFaceIterator& ) const;
00442     bool operator!=( const VertexFaceIterator& ) const;
00443 
00444     const GeMesh::FaceWrapper& operator*() const;
00445     const GeMesh::FaceWrapper* operator->() const;
00446 
00447 private:
00448     // ----- types and enumerations-----
00449     enum {
00450         ID_INVALID = GeMeshWingedEdge::HalfEdge::ID_INVALID
00451     };
00452 
00453     // ----- member functions -----
00454     VertexFaceIterator( const HalfEdgeWrapper&, VertexId );
00455 
00456     // ----- data members -----
00457     GeMeshWingedEdge::HalfEdgeWrapper _wrapper;
00458     VertexId _vertexId;
00459     GeMesh::FaceWrapper _faceWrapper;
00460 };
00461 
00462 
00463 ////////////////////////////////////////////////////////////////////////////////
00464 // GLOBAL FUNCTIONS
00465 //
00466 
00467 std::ostream& operator<<( std::ostream&, const GeMeshWingedEdge& );
00468 std::ostream& operator<<(
00469     std::ostream&,
00470     const GeMeshWingedEdge::HalfEdgeWrapper&
00471 );
00472 
00473 FREECLOTH_NAMESPACE_END
00474 
00475 #include <freecloth/geom/geMeshWingedEdge.inline.h>
00476 
00477 #endif

Generated on Fri May 2 16:51:12 2003 for Freecloth by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002