snc_simplify.h

很多二维 三维几何计算算法 C++ 类库

// 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.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Nef_3/include/CGAL/Nef_3/SNC_simplify.h $
// $Id: SNC_simplify.h 37558 2007-03-27 12:09:05Z hachenb $
//
//
// Author(s)     : Peter Hachenberger <[e-mail]>
//                 Micahel 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>

#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_base : public SNC_decorator<SNC_structure> {
  
  typedef CGAL::SNC_simplify_base<SNC_structure>        Self;
  typedef CGAL::SNC_decorator<SNC_structure>            SNC_decorator;
  typedef typename SNC_structure::Sphere_map            Sphere_map;
  typedef CGAL::SM_decorator<Sphere_map>                SM_decorator;
  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 SNC_decorator::Sphere_kernel Sphere_kernel;
  typedef typename SNC_decorator::Sphere_point Sphere_point;
  typedef typename SNC_decorator::Sphere_segment Sphere_segment;
  typedef typename SNC_decorator::Sphere_circle Sphere_circle;
  typedef typename SNC_decorator::Sphere_direction Sphere_direction;

  bool simplified;

 public:
  SNC_simplify_base(SNC_structure& sncs) : SNC_decorator(sncs), simplified(false) {}
  virtual ~SNC_simplify_base() {}

  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. */ {
    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) {
	for ( bool _circ_loop_flag = ! ::CGAL::is_empty_range( u, eend);
	      _circ_loop_flag;				\
	      _circ_loop_flag = ( u != eend )
	      ) {

	  SFace_handle fu = u->incident_sface(), ftu = u->twin()->incident_sface();
	  //	  CGAL_NEF_TRACEN("sfUNION of "<<IO->index(fu)<<" & "<<IO->index(ftu));
	  merge_sets( fu, ftu, hash, uf);
	  SM_decorator SD(&*u->source()->source());
	  //	  CGAL_NEF_TRACEN("removing "<<IO->index(u)<<" & "<<IO->index(u->twin()));
	  Halfedge_handle src(u->source()), tgt(u->target());
	  if ( SD.is_closed_at_source(u) ) 
	    SD.set_face( src, fu);
	  if ( SD.is_closed_at_source( u->twin()) ) 
 	    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. */

	  SHalfedge_around_facet_circulator next = u;
	  ++next;
	  SD.delete_edge_pair(u); 
	  if( SD.is_isolated(src))
	    SD.set_face(src,fu);
	  SM_decorator SD2(&*tgt->source());
	  if( SD2.is_isolated(tgt))
	    SD2.set_face(tgt,fu);
	  u = next;
	  /* 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 = l->incident_sface(), ftu = l->twin()->incident_sface();
	//	CGAL_NEF_TRACEN("UNION of "<<IO->index(fu)<<" & "<<IO->index(ftu));
	merge_sets( fu, ftu, hash, uf);
	SM_decorator SD(&*l->incident_sface()->center_vertex());
	//	CGAL_NEF_TRACEN("removing "<<IO->index(l)<<" & "<<IO->index(l->twin()));
	SD.delete_loop_only();
      }
    }
    //    CGAL_NEF_TRACEN("removing "<<IO->index(f)<<" & "<<IO->index(f->twin()));
    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(v->point()<<" 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(p1->point()), sp2(p2->point());
    return (sp1 == sp2.antipode());
  }

  bool simplify_redundant_vertex_in_volume(Vertex_handle v) {
    if(is_part_of_volume(v)) {
      //      CGAL_NEF_TRACEN("mark("<<IO->index(v)<<")="<<v->mark()<<", "<<
      //		      "mark("<<IO->index(v->sfaces_begin()->volume())<<")="<<
      //		      v->sfaces_begin()->mark());
      if(v->mark() == v->sfaces_begin()->mark()) {
	//	CGAL_NEF_TRACEN("removing isolated vertex "<<IO->index(v));
	this->sncp()->delete_vertex(v);
	simplified = true;
      }
      return true;
    }
    return false;
  }

  bool simplify_redundant_vertex_on_facet(Vertex_handle v) {
    if( is_part_of_facet(v)) {
      if( v->mark() == v->shalfloop()->mark()) {
	//	CGAL_NEF_TRACEN("removing "<<IO->index(v)<<
	//			", " << v->point() << " on facet ");
	this->sncp()->delete_vertex(v);
	simplified = true;
      }
      return true;
    }
    return false;
  }

  bool simplify_redundant_vertex_on_edge(Vertex_handle v, bool snc_computed) {
    if( is_part_of_edge(v)) {
      SVertex_iterator sv(v->svertices_begin());
      Halfedge_handle e1(sv++), e2(sv++);
      CGAL_assertion( sv == v->svertices_end());
      if( e1->mark() == v->mark() && v->mark() == e2->mark()) {
	//	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;
      }
      return true;
    }
    return false;
  }

  bool simplify_redundant_vertex_on_edgeI(Vertex_handle v) {
    if( is_part_of_edge(v)) {
      SVertex_iterator sv(v->svertices_begin());
      Halfedge_handle e1(sv++), e2(sv++);
      CGAL_assertion( sv == v->svertices_end());
      if( e1->mark() == v->mark() && v->mark() == e2->mark()) {
	SHalfedge_around_svertex_circulator 
	  sec(e1->out_sedge()), send(sec);
	CGAL_For_all(sec,send) {
	  sec->next()->prev() = sec->prev();
	  sec->prev()->next() = sec->next();
	  sec->twin()->next()->prev() = sec->twin()->prev();
	  sec->twin()->prev()->next() = sec->twin()->next();
	}
	if(e2->get_index() < e1->get_index())
	  e1->twin()->set_index(e2->twin()->get_index());
	else
	  e2->twin()->set_index(e1->twin()->get_index());	
	e1->twin()->twin() = e2->twin();
	e2->twin()->twin() = e1->twin();
	this->sncp()->delete_vertex(v);
      }
      return true;
    }
    return false;
  }

  bool vertex_in_volume_simplification() {
    simplified = false;

    Vertex_iterator v = (*this->sncp()).vertices_begin();
    while( v != (*this->sncp()).vertices_end()) {
      Vertex_iterator v_next(v);
      ++v_next;
      simplify_redundant_vertex_in_volume(v);
      v = v_next;
    }
    return simplified;
  }

  bool vertex_on_facet_simplification() {
    simplified = false;

    Vertex_iterator v = (*this->sncp()).vertices_begin();
    while( v != (*this->sncp()).vertices_end()) {
      Vertex_iterator v_next(v);
      ++v_next;
      simplify_redundant_vertex_on_facet(v);
      v = v_next;
    }
    return simplified;
  }

  bool vertex_on_edge_simplification() {
    simplified = false;

    Vertex_iterator v = (*this->sncp()).vertices_begin();
    while( v != (*this->sncp()).vertices_end()) {
      Vertex_iterator v_next(v);
      ++v_next;
      simplify_redundant_vertex_on_edge(v);
      v = v_next;
    }
    return simplified;
  }

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

    Vertex_iterator v = (*this->sncp()).vertices_begin();
    while( v != (*this->sncp()).vertices_end()) {
      Vertex_iterator v_next(v);
      ++v_next;
      if(!simplify_redundant_vertex_in_volume(v))
	if(!simplify_redundant_vertex_on_facet(v))
	  simplify_redundant_vertex_on_edge(v, snc_computed);
      v = v_next;
    }
    return simplified;
  }

  void vertex_simplificationI() {
    simplified = false;

    Vertex_iterator v = (*this->sncp()).vertices_begin();
    while( v != (*this->sncp()).vertices_end()) {
      Vertex_iterator v_next(v);
      ++v_next;
      if(!simplify_redundant_vertex_in_volume(v))
	if(!simplify_redundant_vertex_on_facet(v))
	  simplify_redundant_vertex_on_edgeI(v);
      v = v_next;
    }
  }
  
  bool simplify() {

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

    CGAL_NEF_TRACEN(">>> simplifying");
    SNC_decorator D(*this->sncp());
    
    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();

    Volume_iterator c;
    CGAL_forall_volumes( c, *this->sncp()) {
      hash_volume[c] = uf_volume.make_set(c);
      this->sncp()->reset_object_list(c->shell_entry_objects());
    }
    SFace_iterator sf;
    CGAL_forall_sfaces( sf, *this->sncp()) {
      hash_sface[sf] = uf_sface.make_set(sf);
      this->sncp()->reset_sm_object_list(sf->boundary_entry_objects());
    }

    /* 
     * Volumes simplification 
     */

    Halffacet_handle f(D.halffacets_begin());
    while( f != D.halffacets_end() && f->is_twin())
      f++;
    while( f != D.halffacets_end()) {
      CGAL_assertion( !f->is_twin());
      Halffacet_iterator f_next(f);
      do
	++f_next;