ShMesh.hpp

Go to the documentation of this file.

// Sh: A GPU metaprogramming language.
//
// Copyright (c) 2003 University of Waterloo Computer Graphics Laboratory
// Project administrator: Michael D. McCool
// Authors: Zheng Qin, Stefanus Du Toit, Kevin Moule, Tiberiu S. Popa,
//          Michael D. McCool
// 
// This software is provided 'as-is', without any express or implied
// warranty. In no event will the authors be held liable for any damages
// arising from the use of this software.
// 
// Permission is granted to anyone to use this software for any purpose,
// including commercial applications, and to alter it and redistribute it
// freely, subject to the following restrictions:
// 
// 1. The origin of this software must not be misrepresented; you must
// not claim that you wrote the original software. If you use this
// software in a product, an acknowledgment in the product documentation
// would be appreciated but is not required.
// 
// 2. Altered source versions must be plainly marked as such, and must
// not be misrepresented as being the original software.
// 
// 3. This notice may not be removed or altered from any source
// distribution.
#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

---