snc_simplify.h

来自「CGAL is a collaborative effort of severa」· C头文件 代码 · 共 662 行 · 第 1/2 页

// Copyright (c) 1997-2000  Max-Planck-Institute Saarbruecken (Germany).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $Source: /CVSROOT/CGAL/Packages/Nef_3/include/CGAL/Nef_3/SNC_simplify.h,v $
// $Revision: 1.10.2.2 $ $Date: 2004/12/08 19:30:59 $
// $Name:  $
//
// Author(s)     : Peter Hachenberger <[e-mail]>
//                 Michael Seel <[e-mail]>

#ifndef CGAL_SNC_SIMPLIFY_H
#define CGAL_SNC_SIMPLIFY_H

#include <CGAL/basic.h>
#include <CGAL/Nef_3/SNC_decorator.h>
#include <CGAL/Nef_S2/SM_decorator.h>
#ifdef CGAL_NEF_DEBUG
#include <CGAL/Nef_3/SNC_io_parser.h>
#endif

#undef CGAL_NEF_DEBUG
#define CGAL_NEF_DEBUG 41
#include <CGAL/Nef_2/debug.h>

CGAL_BEGIN_NAMESPACE

template<typename SNC_structure>
class SNC_simplify : public SNC_decorator<SNC_structure> {
  
  typedef CGAL::SNC_simplify<SNC_structure>             Self;
  typedef CGAL::SNC_decorator<SNC_structure>            SNC_decorator;
  typedef SNC_decorator                                 Base;
  typedef typename SNC_structure::Sphere_map            Sphere_map;
  typedef CGAL::SM_decorator<Sphere_map>                SM_decorator;
#ifdef CGAL_NEF_DEBUG
  typedef CGAL::SNC_io_parser<SNC_structure>            SNC_io_parser;
#endif
  typedef typename SNC_structure::Vertex_handle Vertex_handle;
  typedef typename SNC_structure::Halfedge_handle Halfedge_handle;
  typedef typename SNC_structure::Halffacet_handle Halffacet_handle;
  typedef typename SNC_structure::Volume_handle Volume_handle;
  typedef typename SNC_structure::SVertex_handle SVertex_handle;
  typedef typename SNC_structure::SHalfedge_handle SHalfedge_handle;
  typedef typename SNC_structure::SHalfloop_handle SHalfloop_handle;
  typedef typename SNC_structure::SFace_handle SFace_handle;

  typedef typename SNC_structure::Vertex_iterator Vertex_iterator;
  typedef typename SNC_structure::Halfedge_iterator Halfedge_iterator;
  typedef typename SNC_structure::Halffacet_iterator Halffacet_iterator; 
  typedef typename SNC_structure::Volume_iterator Volume_iterator;
  typedef typename SNC_structure::SVertex_iterator SVertex_iterator;  
  typedef typename SNC_structure::SHalfedge_iterator SHalfedge_iterator;
  typedef typename SNC_structure::SHalfloop_iterator SHalfloop_iterator;
  typedef typename SNC_structure::SFace_iterator SFace_iterator; 

  typedef typename SNC_structure::SHalfedge_around_facet_circulator 
                                  SHalfedge_around_facet_circulator;
  typedef typename SNC_structure::SHalfedge_around_svertex_circulator 
                                  SHalfedge_around_svertex_circulator;
  typedef typename SNC_structure::SHalfedge_around_sface_circulator 
                                  SHalfedge_around_sface_circulator;

  typedef typename SNC_structure::Halffacet_cycle_iterator 
                                  Halffacet_cycle_iterator;
  typedef typename SNC_structure::SFace_cycle_iterator 
                                  SFace_cycle_iterator;

  typedef typename Base::Sphere_kernel Sphere_kernel;
  typedef typename Base::Sphere_point Sphere_point;
  typedef typename Base::Sphere_segment Sphere_segment;
  typedef typename Base::Sphere_circle Sphere_circle;
  typedef typename Base::Sphere_direction Sphere_direction;

#ifdef CGAL_NEF_DEBUG
  SNC_io_parser *IO;
#endif

 public:
  SNC_simplify(SNC_structure& sncs) : Base(sncs), IO(NULL) {}

  char PSE(SHalfedge_handle h)
    /* prints a sphere segment */ {
    SNC_decorator D;
    SM_decorator SD;

    CGAL_NEF_TRACE(IO->index(h)<<" @ "<<IO->index(D.vertex(h))<<
	  " "<<D.point(D.vertex(h))<<
	  ", prev " <<IO->index(D.previous(h))<<
	  ", next " <<IO->index(D.next(h))<<
	  ", sprev "<<IO->index(SD.previous(h))<<
	  ", snext "<<IO->index(SD.next(h))<<
	  ", twin " <<IO->index(D.twin(h)));
    return ' ';
  }

  char PFC(SHalfedge_handle e)
    /* prints a facet cycle */ {
    CGAL_NEF_TRACEN("--> Facet cycle begin");
    SHalfedge_around_facet_circulator c(e), cend(c);
    CGAL_For_all(c, cend) {
      CGAL_NEF_TRACEN(PSE(c));
    }
    CGAL_NEF_TRACE("--> Facet cycle end"); 
    return ' ';
  }

  char PFB(Halffacet_handle f)
    /* prints facet boundary entry points */ {
    Halffacet_cycle_iterator fc;
    CGAL_forall_facet_cycles_of(fc, f) {
      if(fc.is_shalfedge()) {
	SHalfedge_handle(e);
	CGAL_NEF_TRACE(' '<<IO->index(e)); }
      else if(fc.is_shalfloop()) {
	SHalfloop_handle l(fc);
	CGAL_NEF_TRACE(' '<<IO->index(l)<<"(sl)");
      }
    }
    return '.';
  }

  char PSFB(SFace_handle f)
    /* prints sphere face boundary entry points */ {
    SFace_cycle_iterator it;
    CGAL_forall_sface_cycles_of(it,f)
      if ( it.is_shalfedge() ) CGAL_NEF_TRACE(IO->index(SHalfedge_handle(it))<<' ');
    CGAL_NEF_TRACE(", ");
    CGAL_forall_sface_cycles_of(it,f)
      if ( it.is_svertex() ) CGAL_NEF_TRACE(IO->index(SVertex_handle(it))<<' ');
    CGAL_NEF_TRACE(", ");
    CGAL_forall_sface_cycles_of(it,f)
      if ( it.is_shalfloop() ) CGAL_NEF_TRACE(IO->index(SHalfloop_handle(it)));
    return '.';
  }

  typedef typename Union_find< Volume_handle>::handle UFH_volume;
  typedef typename Union_find< Halffacet_handle>::handle UFH_facet;
  typedef typename Union_find< SFace_handle>::handle UFH_sface;

  void remove_f_including_all_edge_uses_in_its_boundary_cycles
    ( Halffacet_handle f,
      Unique_hash_map< SFace_handle, UFH_sface>& hash,
      Union_find< SFace_handle>& uf )
    /* removes f and its boundary cycles, and merges up the sphere facets
       incident to them. */ {
    SNC_decorator D;
    Halffacet_cycle_iterator fc;
    CGAL_forall_facet_cycles_of(fc, f) {
      if(fc.is_shalfedge() ) {
	SHalfedge_handle e(fc);
	SHalfedge_around_facet_circulator u(e), eend(e);
	CGAL_For_all(u, eend) {
	  SFace_handle fu = D.sface(u), ftu = D.sface(D.twin(u));
	  CGAL_NEF_TRACEN("sfUNION of "<<IO->index(fu)<<" & "<<IO->index(ftu));
	  merge_sets( fu, ftu, hash, uf);
	  SM_decorator SD(&*D.vertex(u));
	  CGAL_NEF_TRACEN("removing "<<IO->index(u)<<" & "<<IO->index(SD.twin(u)));
	  Halfedge_handle src(SD.source(u)), tgt(SD.target(u));
	  if ( SD.is_closed_at_source(u) ) 
	    SD.set_face( src, fu);
	  if ( SD.is_closed_at_source( SD.twin(u)) ) 
 	    SD.set_face( tgt, fu);
	  /* TO VERIFY: does is_closed_at_source(u) imply is_isolated(src)?
	     if it is true, the svertex face update is not necesary. */
	  SD.delete_edge_pair(u); 
	  if( SD.is_isolated(src))
	    //	    SD.delete_vertex_only(src);
	    SD.set_face(src,fu);
	  SM_decorator SD2(&*D.vertex(tgt));
	  if( SD2.is_isolated(tgt))
	    // SD.delete_vertex_only(tgt);
	    SD2.set_face(tgt,fu);
	  /* TO VERIFY: can both svertices be isolated at the same time? */
      }
      }
      else if(fc.is_shalfloop()) {
	SHalfloop_handle l(fc);
	// this code is currenlty not used, but it is potentially need 
	// in the future, e.g for complex marks or a relative interior 
	// function 
	SFace_handle fu = D.sface(l), ftu = D.sface(D.twin(l));
	CGAL_NEF_TRACEN("UNION of "<<IO->index(fu)<<" & "<<IO->index(ftu));
	merge_sets( fu, ftu, hash, uf);
	SM_decorator SD(&*D.vertex(l));
	CGAL_NEF_TRACEN("removing "<<IO->index(l)<<" & "<<IO->index(SD.twin(l)));
	SD.delete_loop_only();
      }
    }
    CGAL_NEF_TRACEN("removing "<<IO->index(f)<<" & "<<IO->index(D.twin(f)));
    this->sncp()->delete_halffacet_pair(f);
    return;
  }

  bool is_part_of_volume(Vertex_handle v) 
    /* determines if a vertex v is part of a volume, cheking if its local
       graph is trivial (only one sface with no boundary). */  {
    SM_decorator SD(&*v);
    CGAL_assertion( !is_empty_range( SD.sfaces_begin(), SD.sfaces_end()));
    if( is_empty_range( SD.svertices_begin(), SD.svertices_end()) &&
	is_empty_range( SD.shalfedges_begin(), SD.shalfedges_end()) &&
	!SD.has_shalfloop())
      return true;
    return false;
  }

  bool is_part_of_facet(Vertex_handle v) 
    /* determines if a vertex v is part of a the relative interior of a 
       facet, checking if its local graph consists just of a sloop and
       two incident sfaces. */ {
    SM_decorator SD(&*v);
    CGAL_assertion( !is_empty_range( SD.svertices_begin(),
					  SD.svertices_end()) ||
			 is_empty_range( SD.shalfedges_begin(),
					 SD.shalfedges_end()));
    return( SD.has_shalfloop() &&
	    is_empty_range( SD.svertices_begin(), SD.svertices_end()));
  }

  bool is_part_of_edge(Vertex_handle v) {
    /* determines if a vertex v is part of a edge, checking at its local 
       graph for exactly two antipodal vertices  */

    SM_decorator SD(&*v);
    if(SD.has_shalfloop())
      return false;
    if(SD.svertices_begin() == SD.svertices_end())
      return false;
    if(++(SD.svertices_begin()) == SD.svertices_end())
      return false;
    
    CGAL_NEF_TRACE(SNC_decorator(*this->sncp()).point(v)<<" is in edge interior? ");
    SVertex_iterator sv(SD.svertices_begin());
    SVertex_handle p1(sv++), p2(sv++);
    if( sv != SD.svertices_end())
      return false;
    
    CGAL_NEF_TRACE("has two svertices ");
    Sphere_point sp1(SD.point(p1)), sp2(SD.point(p2));
    return (sp1 == sp2.antipode());
  }

  bool vertex_simplification(bool snc_computed = true) {
    bool simplified = false;

#ifdef CGAL_NEF_DEBUG
    delete IO;
    IO = new SNC_io_parser(std::cerr, *this->sncp());
#endif

    SNC_decorator D(*this->sncp());

    Vertex_iterator v = (*this->sncp()).vertices_begin();
    while( v != (*this->sncp()).vertices_end()) {
      SM_decorator SD(&*v);
      Vertex_iterator v_next(v);
      v_next++;
      if( is_part_of_volume(v)) {
	CGAL_NEF_TRACEN("mark("<<IO->index(v)<<")="<<D.mark(v)<<", "<<
	       "mark("<<IO->index(D.volume(SD.sfaces_begin()))<<")="<<
	       SD.mark(SD.sfaces_begin()));
	if(D.mark(v) == SD.mark(SD.sfaces_begin())) {
	  CGAL_NEF_TRACEN("removing isolated vertex "<<IO->index(v));
	  this->sncp()->delete_vertex(v);
	  simplified = true;
	}
      }
      else if( is_part_of_facet(v)) {
	if( D.mark(v) == SD.mark(SD.shalfloop())) {
	  CGAL_NEF_TRACEN("removing "<<IO->index(v)<<
		 " on facet ");
	  this->sncp()->delete_vertex(v);
	  simplified = true;
	}
      }
      else if( is_part_of_edge(v)) {
	SVertex_iterator sv(SD.svertices_begin());
	Halfedge_handle e1(sv++), e2(sv++);
	CGAL_assertion( sv == SD.svertices_end());
	if( D.mark(e1) == D.mark(v) && D.mark(v) == D.mark(e2)) {
	  CGAL_NEF_TRACEN("merging "<<IO->index(e1)<<" & "<<IO->index(e2)<<
		 " in "<<IO->index(v));
	  if(snc_computed)
	    merge_halfedge_pairs( e1, e2);
	  else
	    this->sncp()->delete_vertex(v);
	  simplified = true;
	}
      }
      v = v_next;
    }
    return simplified;
  }
  
  bool simplify() {

    bool update_facets  =  false;
    bool update_sfaces  =  false;
    bool update_volumes =  false;

    CGAL_NEF_TRACEN(">>> simplifying");
    SNC_decorator D(*this->sncp());

#ifdef CGAL_NEF_DEBUG
    delete IO;
    IO = new SNC_io_parser(std::cerr, *this->sncp());
#endif
    
    Unique_hash_map< Volume_handle, UFH_volume> hash_volume;
    Unique_hash_map< Halffacet_handle, UFH_facet> hash_facet;
    Unique_hash_map< SFace_handle, UFH_sface> hash_sface;
    Union_find< Volume_handle> uf_volume;
    Union_find< Halffacet_handle> uf_facet;
    Union_find< SFace_handle> uf_sface;

    /* We discard  the information about boundary entry points, first
       on volumes, facets on sfacets.  Since during the volumes simplification
       is required the remotion of facet cycles, the information about those
       cycles is keep until the this simplification step is performed. */

    this->sncp()->clear_boundary();