ShMesh.hpp

Go to the documentation of this file.

// Sh: A GPU metaprogramming language.
//
// Copyright 2003-2005 Serious Hack Inc.
// 
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, 
// MA  02110-1301, USA
#ifndef SHUTIL_SHMESH_HPP
#define SHUTIL_SHMESH_HPP

#include <list>
#include <map>
#include <set>

#include "sh.hpp"

namespace ShUtil {

template<typename VertexType, typename FaceType, typename EdgeType>
struct ShMeshType {
  typedef VertexType Vertex;
  typedef FaceType Face;
  typedef EdgeType Edge;
};

template<typename M>
struct ShMeshVertex {
  typedef typename M::Edge Edge;
  Edge *edge; //< Edge that starts at this vertex 

  ShMeshVertex();

  ShMeshVertex(const ShMeshVertex<M> &other);
};

template<typename M>
struct ShMeshFace {
  typedef typename M::Edge Edge;
  Edge *edge; //< Edge in this face 

  ShMeshFace();

  ShMeshFace(const ShMeshFace<M> &other);
};

// A half-edge going from start to end that is part of face.
template<typename M>
struct ShMeshEdge {
  typedef typename M::Vertex Vertex;
  typedef typename M::Face Face;
  typedef typename M::Edge Edge;
  Vertex *start; //< Start vertex 
  Vertex *end;  //< End vertex
  Face *face; //< Face  
  Edge *sym; //< Edge paired with this edge.
  Edge *next; //< Next edge in the face 
  Edge *prev; //< Previous edge in the face

  ShMeshEdge();

  ShMeshEdge(const ShMeshEdge<M> &other);

  void setLinks(Vertex *s, Vertex *e, Face *f, 
      Edge *next, Edge *prev, Edge *sym);

  void setNext(Edge *n);

  void setPrev(Edge *p);

  void setSym(Edge *s);
};


template<typename M>
class ShMesh {
  public:
    typedef M MeshType; 
    typedef typename M::Vertex Vertex; 
    typedef typename M::Edge Edge; 
    typedef typename M::Face Face; 

    typedef std::set<Vertex*> VertexSet;
    typedef std::set<Edge*> EdgeSet;
    typedef std::set<Face*> FaceSet;
    typedef std::list<Vertex*> VertexList;

    ShMesh();

    ShMesh(const ShMesh<M>& other);

    ~ShMesh();

    ShMesh<M>& operator=(const ShMesh<M>& other); 

    void clear();

    Face* addFace(const VertexList &vl);

    void removeFace(Face *f);

    template<typename VertLess>
    void mergeVertices();

    void mergeEdges();

    bool earTriangulate();

    VertexSet verts;
    EdgeSet edges;
    FaceSet faces;

  protected:
    typedef std::map<Vertex*, Vertex*> VertexMap;
    typedef std::map<Edge*, Edge*> EdgeMap;
    typedef std::map<Face*, Face*> FaceMap;

    // TODO this is a real hack...figure out how to do removeHalfEdge(e) in log or 
    // constant time without the incidence map for weird meshes 
    // (e.g. with articulation points).
    
    // On certain meshes, all edges incident to a vertex v can be found
    // by traversing v.edge->sym pointers, but this is not always
    // the case.
    typedef std::multimap<Vertex*, Edge*> IncidenceMap;
    typedef typename IncidenceMap::value_type Incidence;
    typedef typename IncidenceMap::iterator IncidenceIterator;
    typedef std::pair<typename IncidenceMap::iterator, 
              typename IncidenceMap::iterator> IncidenceRange;

    IncidenceMap m_incidences; // m_incidences[v] holds all edges e with e.start = v

    void removeHalfEdge(Edge *e);

    void insertHalfEdge(Edge *e);
};


}

#include "ShMeshImpl.hpp"

#endif

---