rulest.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.3 $
//   $Date: 2005-12-21 13:58:54 $
//                                                                            
//=============================================================================

/** \file RulesT.cc
    
 */

//=============================================================================
//
//  Rules - IMPLEMENTATION
//
//=============================================================================


#define OPENMESH_SUBDIVIDER_ADAPTIVE_RULEST_CC


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

#include <OpenMesh/Core/System/config.hh>
#include <OpenMesh/Core/IO/MeshIO.hh>
#include "RulesT.hh"
// --------------------
#if defined(OM_CC_MIPS)
#  include <math.h>
#else
#  include <cmath>
#endif

#if defined(OM_CC_MSVC)
#  pragma warning(disable:4244)
#endif

//== NAMESPACE ================================================================

namespace OpenMesh   { // BEGIN_NS_OPENMESH
namespace Subdivider { // BEGIN_NS_DECIMATER
namespace Adaptive   { // BEGIN_NS_UNIFORM


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

#define MOBJ Inherited::mesh_.deref
#define FH face_handle
#define VH vertex_handle
#define EH edge_handle
#define HEH halfedge_handle
#define NHEH next_halfedge_handle
#define PHEH prev_halfedge_handle
#define OHEH opposite_halfedge_handle
#define TVH  to_vertex_handle
#define FVH  from_vertex_handle

// ------------------------------------------------------------------ Tvv3 ----


template<class M>
void
Tvv3<M>::raise(typename M::FaceHandle& _fh, state_t _target_state) 
{
  if (MOBJ(_fh).state() < _target_state) 
  {
    update(_fh, _target_state);

    typename M::VertexVertexIter          vv_it;
    typename M::FaceVertexIter            fv_it;
    typename M::VertexHandle              vh;
    typename M::Point                     position(0.0, 0.0, 0.0);
    typename M::Point                     face_position;
    const typename M::Point               zero_point(0.0, 0.0, 0.0);
    std::vector<typename M::VertexHandle> vertex_vector;
    int                                      valence(0);

    // raise all adjacent vertices to level x-1
    for (fv_it = Inherited::mesh_.fv_iter(_fh); fv_it; ++fv_it) {

      vertex_vector.push_back(fv_it.handle());
    }

    while(!vertex_vector.empty()) {

      vh = vertex_vector.back();
      vertex_vector.pop_back();

      if (_target_state > 1)
	Inherited::prev_rule()->raise(vh, _target_state - 1);
    }

    face_position = MOBJ(_fh).position(_target_state - 1);
    
    typename M::EdgeHandle               eh;
    std::vector<typename M::EdgeHandle>  edge_vector;

    // interior face
    if (!Inherited::mesh_.is_boundary(_fh) || MOBJ(_fh).final()) { 

      // insert new vertex
      vh = Inherited::mesh_.new_vertex();

      Inherited::mesh_.split(_fh, vh);

      // calculate display position for new vertex
      for (vv_it = Inherited::mesh_.vv_iter(vh); vv_it; ++vv_it) 
      {
        position += Inherited::mesh_.point(vv_it.handle());
        ++valence;
      }

      position /= valence;

      // set attributes for new vertex
      Inherited::mesh_.set_point(vh, position);
      MOBJ(vh).set_position(_target_state, zero_point);
      MOBJ(vh).set_state(_target_state);
      MOBJ(vh).set_not_final();

      typename M::VertexOHalfedgeIter      voh_it;
      // check for edge flipping
      for (voh_it = Inherited::mesh_.voh_iter(vh); voh_it; ++voh_it) {
      
	if (Inherited::mesh_.FH(voh_it.handle()).is_valid()) {

	  MOBJ(Inherited::mesh_.FH(voh_it.handle())).set_state(_target_state);
	  MOBJ(Inherited::mesh_.FH(voh_it.handle())).set_not_final();
	  MOBJ(Inherited::mesh_.FH(voh_it.handle())).set_position(_target_state - 1, face_position);
      

	  for (state_t j = 0; j < _target_state; ++j) {
	    MOBJ(Inherited::mesh_.FH(voh_it.handle())).set_position(j, MOBJ(_fh).position(j));
	  }
      
	  if (Inherited::mesh_.FH(Inherited::mesh_.OHEH(Inherited::mesh_.NHEH(voh_it.handle()))).is_valid()) {

	    if (MOBJ(Inherited::mesh_.FH(Inherited::mesh_.OHEH(Inherited::mesh_.NHEH(voh_it.handle())))).state() == _target_state) {

	      if (Inherited::mesh_.is_flip_ok(Inherited::mesh_.EH(Inherited::mesh_.NHEH(voh_it.handle())))) {

		edge_vector.push_back(Inherited::mesh_.EH(Inherited::mesh_.NHEH(voh_it.handle())));
	      }
	    }
	  }
	}
      }
    }
    
    // boundary face
    else { 

      typename M::VertexHandle vh1 = Inherited::mesh_.new_vertex(),
	                          vh2 = Inherited::mesh_.new_vertex();
      
      typename M::HalfedgeHandle hh2 = Inherited::mesh_.HEH(_fh),
                                    hh1, hh3;
      
      while (!Inherited::mesh_.is_boundary(Inherited::mesh_.OHEH(hh2)))
	hh2 = Inherited::mesh_.NHEH(hh2);
      
      eh = Inherited::mesh_.EH(hh2);
      
      hh2 = Inherited::mesh_.NHEH(hh2);
      hh1 = Inherited::mesh_.NHEH(hh2);
      
      assert(Inherited::mesh_.is_boundary(eh));

      Inherited::mesh_.split(eh, vh1);

      eh = Inherited::mesh_.EH(Inherited::mesh_.PHEH(hh2));

      assert(Inherited::mesh_.is_boundary(eh));

      Inherited::mesh_.split(eh, vh2);

      hh3 = Inherited::mesh_.NHEH(Inherited::mesh_.OHEH(Inherited::mesh_.PHEH(hh1)));

      typename M::VertexHandle   vh0(Inherited::mesh_.TVH(hh1)),
	                            vh3(Inherited::mesh_.FVH(hh2));

      // set display position and attributes for new vertices
      Inherited::mesh_.set_point(vh1, (Inherited::mesh_.point(vh0) * 2.0 + Inherited::mesh_.point(vh3)) / 3.0);

      MOBJ(vh1).set_position(_target_state, zero_point);
      MOBJ(vh1).set_state(_target_state);
      MOBJ(vh1).set_not_final();

      MOBJ(vh0).set_position(_target_state, MOBJ(vh0).position(_target_state - 1) * 3.0);
      MOBJ(vh0).set_state(_target_state);
      MOBJ(vh0).set_not_final();

      // set display position and attributes for old vertices
      Inherited::mesh_.set_point(vh2, (Inherited::mesh_.point(vh3) * 2.0 + Inherited::mesh_.point(vh0)) / 3.0);
      MOBJ(vh2).set_position(_target_state, zero_point);
      MOBJ(vh2).set_state(_target_state);
      MOBJ(vh2).set_not_final();

      MOBJ(vh3).set_position(_target_state, MOBJ(vh3).position(_target_state - 1) * 3.0);
      MOBJ(vh3).set_state(_target_state);
      MOBJ(vh3).set_not_final();

      // init 3 faces
      MOBJ(Inherited::mesh_.FH(hh1)).set_state(_target_state);
      MOBJ(Inherited::mesh_.FH(hh1)).set_not_final();
      MOBJ(Inherited::mesh_.FH(hh1)).set_position(_target_state - 1, face_position);
      
      MOBJ(Inherited::mesh_.FH(hh2)).set_state(_target_state);
      MOBJ(Inherited::mesh_.FH(hh2)).set_not_final();
      MOBJ(Inherited::mesh_.FH(hh2)).set_position(_target_state - 1, face_position);

      MOBJ(Inherited::mesh_.FH(hh3)).set_state(_target_state);
      MOBJ(Inherited::mesh_.FH(hh3)).set_final();
      MOBJ(Inherited::mesh_.FH(hh3)).set_position(_target_state - 1, face_position);
      

      for (state_t j = 0; j < _target_state; ++j) {
	MOBJ(Inherited::mesh_.FH(hh1)).set_position(j, MOBJ(_fh).position(j));
      }
      
      for (state_t j = 0; j < _target_state; ++j) {

	MOBJ(Inherited::mesh_.FH(hh2)).set_position(j, MOBJ(_fh).position(j));
      }
      
      for (state_t j = 0; j < _target_state; ++j) {

	MOBJ(Inherited::mesh_.FH(hh3)).set_position(j, MOBJ(_fh).position(j));
      }
      
      // check for edge flipping
      if (Inherited::mesh_.FH(Inherited::mesh_.OHEH(hh1)).is_valid()) {

	if (MOBJ(Inherited::mesh_.FH(Inherited::mesh_.OHEH(hh1))).state() == _target_state) {

	  if (Inherited::mesh_.is_flip_ok(Inherited::mesh_.EH(hh1))) {

	    edge_vector.push_back(Inherited::mesh_.EH(hh1));
	  }
	}
      }

      if (Inherited::mesh_.FH(Inherited::mesh_.OHEH(hh2)).is_valid()) {

	if (MOBJ(Inherited::mesh_.FH(Inherited::mesh_.OHEH(hh2))).state() == _target_state) {

	  if (Inherited::mesh_.is_flip_ok(Inherited::mesh_.EH(hh2))) {

	    edge_vector.push_back(Inherited::mesh_.EH(hh2));
	  }
	}
      }
    }
  
    // flip edges
    while (!edge_vector.empty()) {

      eh = edge_vector.back();
      edge_vector.pop_back();
      
      assert(Inherited::mesh_.is_flip_ok(eh));

      Inherited::mesh_.flip(eh);

      MOBJ(Inherited::mesh_.FH(Inherited::mesh_.HEH(eh, 0))).set_final();
      MOBJ(Inherited::mesh_.FH(Inherited::mesh_.HEH(eh, 1))).set_final();

      MOBJ(Inherited::mesh_.FH(Inherited::mesh_.HEH(eh, 0))).set_state(_target_state);
      MOBJ(Inherited::mesh_.FH(Inherited::mesh_.HEH(eh, 1))).set_state(_target_state);

      MOBJ(Inherited::mesh_.FH(Inherited::mesh_.HEH(eh, 0))).set_position(_target_state, face_position);
      MOBJ(Inherited::mesh_.FH(Inherited::mesh_.HEH(eh, 1))).set_position(_target_state, face_position);
    }
  }
}


template<class M>
void Tvv3<M>::raise(typename M::VertexHandle& _vh, state_t _target_state) {

  if (MOBJ(_vh).state() < _target_state) {

    update(_vh, _target_state);

    // multiply old position by 3
    MOBJ(_vh).set_position(_target_state, MOBJ(_vh).position(_target_state - 1) * 3.0);

    MOBJ(_vh).inc_state();

    assert(MOBJ(_vh).state() == _target_state);
  }
}


// ------------------------------------------------------------------ Tvv4 ----


template<class M>
void
Tvv4<M>::raise(typename M::FaceHandle& _fh, state_t _target_state) 
{

  if (MOBJ(_fh).state() < _target_state) {

    update(_fh, _target_state);

    typename M::FaceVertexIter              fv_it;
    typename M::VertexHandle                temp_vh;
    typename M::Point                       face_position;
    const typename M::Point                 zero_point(0.0, 0.0, 0.0);
    std::vector<typename M::VertexHandle>   vertex_vector;
    std::vector<typename M::HalfedgeHandle> halfedge_vector;

    // raise all adjacent vertices to level x-1
    for (fv_it = Inherited::mesh_.fv_iter(_fh); fv_it; ++fv_it) {

      vertex_vector.push_back(fv_it.handle());
    }

    while(!vertex_vector.empty()) {

      temp_vh = vertex_vector.back();
      vertex_vector.pop_back();

      if (_target_state > 1) {

	Inherited::prev_rule()->raise(temp_vh, _target_state - 1);
      }
    }

    face_position = MOBJ(_fh).position(_target_state - 1);

    typename M::HalfedgeHandle hh[3];
    typename M::VertexHandle   vh[3];
    typename M::VertexHandle   new_vh[3];
    typename M::FaceHandle     fh[4];
    typename M::EdgeHandle     eh;
    typename M::HalfedgeHandle temp_hh;

    // normal (final) face
    if (MOBJ(_fh).final()) {

      // define three halfedge handles around the face
      hh[0] = Inherited::mesh_.HEH(_fh);
      hh[1] = Inherited::mesh_.NHEH(hh[0]);
      hh[2] = Inherited::mesh_.NHEH(hh[1]);

      assert(hh[0] == Inherited::mesh_.NHEH(hh[2]));

      vh[0] = Inherited::mesh_.TVH(hh[0]);
      vh[1] = Inherited::mesh_.TVH(hh[1]);
      vh[2] = Inherited::mesh_.TVH(hh[2]);
      
      new_vh[0] = Inherited::mesh_.add_vertex(zero_point);
      new_vh[1] = Inherited::mesh_.add_vertex(zero_point);
      new_vh[2] = Inherited::mesh_.add_vertex(zero_point);

      // split three edges
      split_edge(hh[0], new_vh[0], _target_state);
      eh = Inherited::mesh_.EH(Inherited::mesh_.PHEH(hh[2]));
      split_edge(hh[1], new_vh[1], _target_state);
      split_edge(hh[2], new_vh[2], _target_state);

      assert(Inherited::mesh_.FVH(hh[2]) == vh[1]);
      assert(Inherited::mesh_.FVH(hh[1]) == vh[0]);
      assert(Inherited::mesh_.FVH(hh[0]) == vh[2]);

      if (Inherited::mesh_.FH(Inherited::mesh_.OHEH(hh[0])).is_valid()) {

	temp_hh = Inherited::mesh_.OHEH(Inherited::mesh_.PHEH(Inherited::mesh_.OHEH(hh[0])));
	if (MOBJ(Inherited::mesh_.FH(temp_hh)).red_halfedge() != temp_hh)
	  halfedge_vector.push_back(temp_hh);
      }

      if (Inherited::mesh_.FH(Inherited::mesh_.OHEH(hh[1])).is_valid()) {

	temp_hh = Inherited::mesh_.OHEH(Inherited::mesh_.PHEH(Inherited::mesh_.OHEH(hh[1])));
	if (MOBJ(Inherited::mesh_.FH(temp_hh)).red_halfedge() != temp_hh)
	  halfedge_vector.push_back(temp_hh);
      }

      if (Inherited::mesh_.FH(Inherited::mesh_.OHEH(hh[2])).is_valid()) {

	temp_hh = Inherited::mesh_.OHEH(Inherited::mesh_.PHEH(Inherited::mesh_.OHEH(hh[2])));
	if (MOBJ(Inherited::mesh_.FH(temp_hh)).red_halfedge() != temp_hh)
	  halfedge_vector.push_back(temp_hh);
      }
    }
    
    // splitted face, check for type
    else {

      // define red halfedge handle
      typename M::HalfedgeHandle red_hh(MOBJ(_fh).red_halfedge());

      if (Inherited::mesh_.FH(Inherited::mesh_.OHEH(Inherited::mesh_.PHEH(red_hh))).is_valid() 
	  && Inherited::mesh_.FH(Inherited::mesh_.OHEH(Inherited::mesh_.NHEH(Inherited::mesh_.OHEH(red_hh)))).is_valid() 
	  && MOBJ(Inherited::mesh_.FH(Inherited::mesh_.OHEH(Inherited::mesh_.PHEH(red_hh)))).red_halfedge() == red_hh 
	  && MOBJ(Inherited::mesh_.FH(Inherited::mesh_.OHEH(Inherited::mesh_.NHEH(Inherited::mesh_.OHEH(red_hh))))).red_halfedge() == red_hh) {

	// three times divided face
	vh[0] = Inherited::mesh_.TVH(Inherited::mesh_.NHEH(Inherited::mesh_.OHEH(Inherited::mesh_.NHEH(Inherited::mesh_.OHEH(red_hh)))));
	vh[1] = Inherited::mesh_.TVH(red_hh);
	vh[2] = Inherited::mesh_.TVH(Inherited::mesh_.NHEH(Inherited::mesh_.OHEH(Inherited::mesh_.PHEH(red_hh))));
      
	new_vh[0] = Inherited::mesh_.FVH(red_hh);
	new_vh[1] = Inherited::mesh_.TVH(Inherited::mesh_.NHEH(Inherited::mesh_.OHEH(red_hh)));
	new_vh[2] = Inherited::mesh_.TVH(Inherited::mesh_.NHEH(red_hh));

	hh[0] = Inherited::mesh_.PHEH(Inherited::mesh_.OHEH(Inherited::mesh_.PHEH(red_hh)));
	hh[1] = Inherited::mesh_.PHEH(Inherited::mesh_.OHEH(Inherited::mesh_.NHEH(Inherited::mesh_.OHEH(red_hh))));
	hh[2] = Inherited::mesh_.NHEH(red_hh);

	eh = Inherited::mesh_.EH(red_hh);
      }
      
      else {