trimesht.cc

penMesh is a generic and efficient data structure for representing and manipulating polygonal meshes

//=============================================================================
//
//                               OpenMesh
//      Copyright (C) 2001-2005 by Computer Graphics Group, RWTH Aachen
//                           www.openmesh.org
//
//-----------------------------------------------------------------------------
//
//                                License
//
//   This library is free software; you can redistribute it and/or modify it
//   under the terms of the GNU Library General Public License as published
//   by the Free Software Foundation, version 2.
//
//   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
//   Library General Public License for more details.
//
//   You should have received a copy of the GNU Library General Public
//   License along with this library; if not, write to the Free Software
//   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
//-----------------------------------------------------------------------------
//
//   $Revision: 1.6 $
//   $Date: 2005-12-21 13:51:50 $
//
//=============================================================================


//=============================================================================
//
//  CLASS TriMeshT - IMPLEMENTATION
//
//=============================================================================


#define OPENMESH_TRIMESH_C


//== INCLUDES =================================================================


#include <OpenMesh/Core/Mesh/TriMeshT.hh>
#include <OpenMesh/Core/System/omstream.hh>
#include <vector>


//== NAMESPACES ==============================================================


namespace OpenMesh {


//== IMPLEMENTATION ==========================================================


template <class Kernel>
typename TriMeshT<Kernel>::FaceHandle
TriMeshT<Kernel>::
add_face(const std::vector<VertexHandle>& _vertex_handles)
{
  unsigned int n_vertices(_vertex_handles.size());

  // need at least 3 vertices
  if (n_vertices < 3) return This::InvalidFaceHandle;

  /// face is triangle -> ok
  if (_vertex_handles.size() == 3)
    return PolyMesh::add_face(_vertex_handles);

  /// face is not a triangle -> triangulate
  else
  {
    omlog() << "triangulating " << n_vertices << "_gon\n";

    std::vector<VertexHandle>  vhandles(3);
    vhandles[0] = _vertex_handles[0];

    FaceHandle fh;
    unsigned int i(1);
    --n_vertices;

    while (i < n_vertices)
    {
      vhandles[1] = _vertex_handles[i];
      vhandles[2] = _vertex_handles[++i];
      fh = PolyMesh::add_face(vhandles);
    }

    return fh;
  }
}


//-----------------------------------------------------------------------------


template <class Kernel>
bool
TriMeshT<Kernel>::
is_collapse_ok(HalfedgeHandle v0v1)
{
  HalfedgeHandle  v1v0(opposite_halfedge_handle(v0v1));
  VertexHandle    v0(to_vertex_handle(v1v0));
  VertexHandle    v1(to_vertex_handle(v0v1));



  // are vertices already deleted ?
  if (status(v0).deleted() || status(v1).deleted())
    return false;


  VertexHandle    vl, vr;
  HalfedgeHandle  h1, h2;


  // the edges v1-vl and vl-v0 must not be both boundary edges
  if (!is_boundary(v0v1))
  {
    vl = to_vertex_handle(next_halfedge_handle(v0v1));

    h1 = next_halfedge_handle(v0v1);
    h2 = next_halfedge_handle(h1);
    if (is_boundary(opposite_halfedge_handle(h1)) &&
	is_boundary(opposite_halfedge_handle(h2)))
      return false;
  }


  // the edges v0-vr and vr-v1 must not be both boundary edges
  if (!is_boundary(v1v0))
  {
    vr = to_vertex_handle(next_halfedge_handle(v1v0));

    h1 = next_halfedge_handle(v1v0);
    h2 = next_halfedge_handle(h1);
    if (is_boundary(opposite_halfedge_handle(h1)) &&
	is_boundary(opposite_halfedge_handle(h2)))
      return false;
  }


  // if vl and vr are equal or both invalid -> fail
  if (vl == vr) return false;


  VertexVertexIter  vv_it;


  // test intersection of the one-rings of v0 and v1
  for (vv_it = vv_iter(v0); vv_it; ++vv_it)
    status(vv_it).set_tagged(false);

  for (vv_it = vv_iter(v1); vv_it; ++vv_it)
    status(vv_it).set_tagged(true);

  for (vv_it = vv_iter(v0); vv_it; ++vv_it)
    if (status(vv_it).tagged() && vv_it.handle() != vl && vv_it.handle() != vr)
      return false;



  // edge between two boundary vertices should be a boundary edge
  if ( is_boundary(v0) && is_boundary(v1) &&
       !is_boundary(v0v1) && !is_boundary(v1v0))
    return false;



  // passed all tests
  return true;
}


//-----------------------------------------------------------------------------


template <class Kernel>
void
TriMeshT<Kernel>::
collapse(HalfedgeHandle _hh)
{
  HalfedgeHandle h0 = _hh;
  HalfedgeHandle h1 = prev_halfedge_handle(h0);
  HalfedgeHandle o0 = opposite_halfedge_handle(h0);
  HalfedgeHandle o1 = next_halfedge_handle(o0);

  // remove edge
  remove_edge(h0);

  // remove loops
  if (next_halfedge_handle(next_halfedge_handle(h1)) == h1)
    remove_loop(h1);
  if (next_halfedge_handle(next_halfedge_handle(o1)) == o1)
    remove_loop(o1);
}


//-----------------------------------------------------------------------------


template <class Kernel>
void
TriMeshT<Kernel>::
remove_edge(HalfedgeHandle _hh)
{
  HalfedgeHandle  h  = _hh;
  HalfedgeHandle  hn = next_halfedge_handle(h);
  HalfedgeHandle  hp = prev_halfedge_handle(h);

  HalfedgeHandle  o  = opposite_halfedge_handle(h);
  HalfedgeHandle  on = next_halfedge_handle(o);
  HalfedgeHandle  op = prev_halfedge_handle(o);

  FaceHandle      fh = face_handle(h);
  FaceHandle      fo = face_handle(o);

  VertexHandle    vh = to_vertex_handle(h);
  VertexHandle    vo = to_vertex_handle(o);



  // halfedge -> vertex
  for (VertexIHalfedgeIter vih_it(vih_iter(vo)); vih_it; ++vih_it)
    set_vertex_handle(vih_it.handle(), vh);


  // halfedge -> halfedge
  set_next_halfedge_handle(hp, hn);
  set_next_halfedge_handle(op, on);


  // face -> halfedge
  if (fh.is_valid())  set_halfedge_handle(fh, hn);
  if (fo.is_valid())  set_halfedge_handle(fo, on);


  // vertex -> halfedge
  if (halfedge_handle(vh) == o)  set_halfedge_handle(vh, hn);
  adjust_outgoing_halfedge(vh);
  set_isolated(vo);


  // delete stuff
  status(edge_handle(h)).set_deleted(true);
  status(vo).set_deleted(true);
}


//-----------------------------------------------------------------------------


template <class Kernel>
void
TriMeshT<Kernel>::
remove_loop(HalfedgeHandle _hh)
{
  HalfedgeHandle  h0 = _hh;
  HalfedgeHandle  h1 = next_halfedge_handle(h0);

  HalfedgeHandle  o0 = opposite_halfedge_handle(h0);
  HalfedgeHandle  o1 = opposite_halfedge_handle(h1);

  VertexHandle    v0 = to_vertex_handle(h0);
  VertexHandle    v1 = to_vertex_handle(h1);

  FaceHandle      fh = face_handle(h0);
  FaceHandle      fo = face_handle(o0);



  // is it a loop ?
  assert ((next_halfedge_handle(h1) == h0) && (h1 != o0));


  // halfedge -> halfedge
  set_next_halfedge_handle(h1, next_halfedge_handle(o0));
  set_next_halfedge_handle(prev_halfedge_handle(o0), h1);


  // halfedge -> face
  set_face_handle(h1, fo);


  // vertex -> halfedge
  set_halfedge_handle(v0, h1);  adjust_outgoing_halfedge(v0);
  set_halfedge_handle(v1, o1);  adjust_outgoing_halfedge(v1);


  // face -> halfedge
  if (fo.is_valid() && halfedge_handle(fo) == o0)
    set_halfedge_handle(fo, h1);
  //set_halfedge_handle(fh, InvalidHalfedgeHandle);//Do we need that - it will be marked as deleted below?

  // delete stuff
  if (fh.is_valid())  status(fh).set_deleted(true);
  status(edge_handle(h0)).set_deleted(true);
}


//-----------------------------------------------------------------------------


template <class Kernel>
typename TriMeshT<Kernel>::HalfedgeHandle
TriMeshT<Kernel>::
vertex_split( VertexHandle  v0,
        VertexHandle  v1,
        VertexHandle  vl,
        VertexHandle  vr )
{
  HalfedgeHandle v1vl, vlv1, vrv1, v0v1;


  // build loop from halfedge v1->vl
  if (vl.is_valid())
  {
    v1vl = find_halfedge(v1, vl);
    assert(v1vl.is_valid());
    vlv1 = insert_loop(v1vl);
  }


  // build loop from halfedge vr->v1
  if (vr.is_valid())
  {
    vrv1 = find_halfedge(vr, v1);
    assert(vrv1.is_valid());
    insert_loop(vrv1);
  }