snc_const_decorator.h

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

// Copyright (c) 1997-2002  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_const_decorator.h,v $
// $Revision: 1.22.2.1 $ $Date: 2004/12/08 19:30:40 $
// $Name:  $
//
// Author(s)     : Michael Seel    <[e-mail]>
//                 Miguel Granados <[e-mail]>
//                 Susan Hert      <[e-mail]>
//                 Lutz Kettner    <[e-mail]>
//                 Peter Hachenberger <[e-mail]>
#ifndef CGAL_SNC_CONST_DECORATOR_H
#define CGAL_SNC_CONST_DECORATOR_H

#include <CGAL/basic.h>
#include <CGAL/Nef_S2/Normalizing.h>
#include <CGAL/Unique_hash_map.h>
#include <CGAL/Nef_3/SNC_iteration.h>
#include <CGAL/Nef_3/SNC_decorator_traits.h>
#include <CGAL/Nef_S2/SM_point_locator.h>
#include <list>

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

CGAL_BEGIN_NAMESPACE

template<typename S> class SM_const_decorator;

template <typename SNC_structure_>
class SNC_const_decorator { 
  typedef SNC_structure_                            Base;
  typedef SNC_structure_                            SNC_structure;
  typedef SNC_const_decorator<SNC_structure>        Self;
  typedef typename SNC_structure::Sphere_map        Sphere_map;
  typedef CGAL::SM_const_decorator<Sphere_map>      SM_const_decorator;
  const SNC_structure* sncp_;

  typedef typename SNC_structure::SHalfedge  SHalfedge;

public:
  typedef SNC_decorator_const_traits<SNC_structure>  Decorator_traits;

  typedef typename SNC_structure::Object_handle   Object_handle;
  typedef typename SNC_structure::Object_const_iterator Object_const_iterator;

  typedef typename SNC_structure::Vertex_const_handle Vertex_const_handle;
  typedef typename SNC_structure::Halfedge_const_handle Halfedge_const_handle;
  typedef typename SNC_structure::Halffacet_const_handle Halffacet_const_handle;
  typedef typename SNC_structure::Volume_handle Volume_handle;
  typedef typename SNC_structure::Volume_const_handle Volume_const_handle;
  typedef typename SNC_structure::SVertex_const_handle SVertex_const_handle;
  typedef typename SNC_structure::SHalfedge_const_handle SHalfedge_const_handle;
  typedef typename SNC_structure::SHalfloop_const_handle SHalfloop_const_handle;
  typedef typename SNC_structure::SFace_const_handle SFace_const_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::Vertex_const_iterator Vertex_const_iterator;
  typedef typename SNC_structure::Halfedge_const_iterator Halfedge_const_iterator;
  typedef typename SNC_structure::Halffacet_const_iterator Halffacet_const_iterator; 
  typedef typename SNC_structure::Volume_const_iterator Volume_const_iterator;
  typedef typename SNC_structure::SVertex_const_iterator SVertex_const_iterator;
  typedef typename SNC_structure::SHalfedge_const_iterator SHalfedge_const_iterator;
  typedef typename SNC_structure::SHalfloop_const_iterator SHalfloop_const_iterator;
  typedef typename SNC_structure::SFace_const_iterator SFace_const_iterator;

  typedef typename SNC_structure::SHalfedge_around_facet_const_circulator SHalfedge_around_facet_const_circulator;
  typedef typename SNC_structure::SFace_cycle_const_iterator SFace_cycle_const_iterator;
  typedef typename SNC_structure::Halffacet_cycle_const_iterator Halffacet_cycle_const_iterator;
  typedef typename SNC_structure::Shell_entry_const_iterator Shell_entry_const_iterator;

  typedef typename SNC_structure::Kernel Kernel;
  typedef typename SNC_structure::FT FT;
  typedef typename SNC_structure::RT RT;

  typedef typename SNC_structure::Point_3 Point_3;
  typedef typename SNC_structure::Segment_3 Segment_3;
  typedef typename SNC_structure::Ray_3 Ray_3;
  typedef typename SNC_structure::Line_3 Line_3;
  typedef typename SNC_structure::Plane_3 Plane_3;
  typedef typename SNC_structure::Vector_3 Vector_3;
  typedef typename SNC_structure::Aff_transformation_3 Aff_transformation_3;

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

  typedef typename SNC_structure::Size_type Size_type;
  typedef typename SNC_structure::Mark Mark;
  typedef typename SNC_structure::Infi_box Infi_box;

  typedef typename SM_const_decorator::SHalfedge_around_svertex_const_circulator 
                                       SHalfedge_around_svertex_const_circulator;
  typedef typename SM_const_decorator::SHalfedge_around_sface_const_circulator 
                                       SHalfedge_around_sface_const_circulator;

 public:
  typedef void* GenPtr;

  SNC_const_decorator() : sncp_(0) {}
  SNC_const_decorator(const SNC_structure& W) : sncp_(&W) {}
  SNC_const_decorator(const SNC_const_decorator& S) {
    sncp_ = S.sncp_;
  }

 protected:  
  void set_snc(const SNC_structure& W) {
    sncp_ = &W;
  }

 public:
  const SNC_structure* sncp() const { return sncp_; }
  
  /*
  static Vertex_const_handle vertex( Halfedge_const_handle e)
  { return e->center_vertex(); }
  static Halfedge_const_handle twin( Halfedge_const_handle e)
  { return e->twin(); }
  static Vertex_const_handle source( Halfedge_const_handle e)
  { return e->center_vertex(); }
  static Vertex_const_handle target( Halfedge_const_handle e)
  { return source(twin(e)); }  
  static SFace_const_handle sface( Halfedge_const_handle e)
  { return e->incident_sface(); }
  // SVertex queries

  static Vertex_const_handle vertex(SHalfedge_const_handle e)
  { return vertex(e->source()); }
  static SHalfedge_const_handle twin(SHalfedge_const_handle e)
  { return e->twin(); }
  static Vertex_const_handle source(SHalfedge_const_handle e)
  { return e->source()->center_vertex(); }
  static Vertex_const_handle source(SHalfedge e)
  { return e.source()->center_vertex(); }
  static Vertex_const_handle target(SHalfedge_const_handle e)
  { return e->twin()->source()->twin()->center_vertex(); }
  static SHalfedge_const_handle previous(SHalfedge_const_handle e)
  { return e->prev(); }
  static SHalfedge_const_handle next(SHalfedge_const_handle e)
  { return e->next(); }
  static Halffacet_const_handle facet(SHalfedge_const_handle e)
  { return e->facet(); }
  static SFace_const_handle sface(SHalfedge_const_handle e)
  { return e->incident_sface(); }
  static Halfedge_const_handle ssource(SHalfedge_const_handle e)
  { return e->source(); }
  static Halfedge_const_handle starget(SHalfedge_const_handle e)
  { return e->twin()->source(); }
  // SHalfedge queries

  static SHalfloop_const_handle twin( SHalfloop_const_handle l)
  { return l->twin(); }
  static Halffacet_const_handle facet( SHalfloop_const_handle l)
  { return l->facet(); }
  static Vertex_const_handle vertex( SHalfloop_const_handle l)
  { return l->incident_sface()->center_vertex(); }
  static SFace_const_handle sface( SHalfloop_const_handle l)
  { return l->incident_sface(); }
  // SHalfloop queries

  static Vertex_const_handle vertex(SFace_const_handle f)
  { return f->center_vertex(); }
  static Volume_const_handle volume(SFace_const_handle f)
  { return f->volume(); }
  // SFace queries 

  static Halffacet_const_handle twin(Halffacet_const_handle f)
  { return f->twin(); }
  static Volume_const_handle volume(Halffacet_const_handle f)
    { return f->incident_volume(); }
  // Halffacet queries
*/

  SFace_const_handle adjacent_sface(Halffacet_const_handle f) const {
    Halffacet_cycle_const_iterator fc(f->facet_cycles_begin());
    CGAL_assertion( fc != f->facet_cycles_end());

    if ( fc.is_shalfedge() ) { 
      SHalfedge_const_handle se(fc);
      CGAL_assertion( facet(se) == f);
      CGAL_assertion( sface(se) != SFace_const_handle());
      CGAL_assertion( volume(sface(twin(se))) == volume(f));
      return sface(twin(se));
    } 
    else 
      CGAL_assertion_msg( 0, "Facet outer cycle entry point"
			     "is not an SHalfedge? ");
    return SFace_const_handle(); // never reached
  }

  static const Point_3& point(Vertex_const_handle v)
  { return v->point(); }

  static Vector_3 vector(Halfedge_const_handle e)
  { return Vector_3(e->point()-CGAL::ORIGIN); }

  static Segment_3 segment(Halfedge_const_handle e)
  { return Segment_3(e->source()->point(),
		     e->twin()->source()->point()); }

  static const Plane_3 plane(Halffacet_const_handle f)
  { return f->plane(); }

  static const Mark& mark(Vertex_const_handle v)
  { return v->mark(); }
  static const Mark& mark(Halfedge_const_handle e)
  { return e->mark(); }
  static const Mark& mark(Halffacet_const_handle f)
  { return f->mark(); }
  static const Mark& mark(Volume_const_handle c)
  { return c->mark(); }

  template <typename Visitor>
  void visit_shell_objects(SFace_const_handle f, Visitor& V) const;

  Vertex_const_iterator   vertices_begin() const { 
    return this->sncp()->vertices_begin(); }
  Vertex_const_iterator   vertices_end()   const { 
    return this->sncp()->vertices_end(); }
  Halfedge_const_iterator halfedges_begin()const {
    return this->sncp()->halfedges_begin(); }
  Halfedge_const_iterator halfedges_end()  const { 
    return this->sncp()->halfedges_end(); }
  Halffacet_const_iterator halffacets_begin() const { 
    return this->sncp()->halffacets_begin(); }
  Halffacet_const_iterator halffacets_end() const { 
    return this->sncp()->halffacets_end(); }
  Volume_const_iterator   volumes_begin() const   { 
    return this->sncp()->volumes_begin(); }
  Volume_const_iterator   volumes_end()   const   { 
    return this->sncp()->volumes_end(); }

  Shell_entry_const_iterator shells_begin(Volume_const_handle c) const {
    return c->shells_begin();
  }
  Shell_entry_const_iterator shells_end(Volume_const_handle c) const {
    return c->shells_end();
  }

  Size_type number_of_vertices() const  
  { return this->sncp()->number_of_vertices(); }
  Size_type number_of_halfedges() const 
  { return this->sncp()->number_of_halfedges(); }
  Size_type number_of_edges() const     
  { return this->sncp()->number_of_edges(); }
  Size_type number_of_halffacets() const    
  { return this->sncp()->number_of_halffacets();}
  Size_type number_of_facets() const    
  { return this->sncp()->number_of_facets();}
  Size_type number_of_volumes() const   
  { return this->sncp()->number_of_volumes();}

  bool is_bounded() const {
    if(is_standard_kernel())
      return true;
    int i = 0;
    Halffacet_const_handle hf;
    CGAL_forall_facets(hf, *sncp()) {
      if(!Infi_box::is_standard(plane(hf)))
	++i;
    }
    CGAL_assertion(i>=6);
    return (i == 6);
  }

  static bool is_bounded(Halffacet_const_handle f) {
    Halffacet_cycle_const_iterator fc = f->facet_cycles_begin();
    CGAL_assertion(fc.is_shalfedge());
    SHalfedge_const_handle sh(fc);
    SHalfedge_around_facet_const_circulator fcc(sh), fend(fcc);
    CGAL_For_all(fcc,fend)
      if(!is_standard(fcc->source()->source()))
	return false;
    return true;
  }

  static bool is_standard(Vertex_const_handle v) {
    return Infi_box::is_standard(v->point());
  }
  static bool is_standard(Halffacet_const_handle f) {
    return Infi_box::is_standard(f->plane());
  }
  static bool is_standard_kernel() { return Infi_box::standard_kernel(); }
  static bool is_extended_kernel() { return Infi_box::extended_kernel(); }
  static void set_size_of_infimaximal_box(const typename Infi_box::NT& size) { 
    Infi_box::set_size_of_infimaximal_box(size); 
  }

  typedef SM_point_locator<SM_const_decorator>         SM_point_locator;

  Halffacet_const_handle get_visible_facet( const Vertex_const_handle v, 
				      const Ray_3& ray) const
    /*{\Mop when one shoot a ray |ray| in order to find the facet below to
      an object, and vertex |v| is hit, we need to choose one of the facets
      in the adjacency list of |v| such that it could be 'seen' from the
      piercing point of the |ray| on the sphere map on |v|.  We make it just
      locating the sphere facet |sf| pierced by |ray| and taking the adjacent 
      facet to one of the sphere segments on the boundary of |sf|.
      \precondition |ray| target is on |v| and the intersection between
      |ray| and the 2-skeleton incident to v is empty. }*/ {

    Halffacet_const_handle f_visible;
    CGAL_assertion( ray.source() != point(v));
    CGAL_assertion( ray.has_on(point(v)));
    Sphere_point sp(ray.source() - point(v));
    CGAL_NEF_TRACEN( "Locating "<<sp <<" in "<<point(v));
    CGAL_assertion(Infi_box::degree(sp.hx()) < 2 && 
		   Infi_box::degree(sp.hy()) < 2 && 
		   Infi_box::degree(sp.hz()) < 2 && 
		   Infi_box::degree(sp.hw()) == 0);
    sp = Infi_box::simplify(sp);
    CGAL_NEF_TRACEN( "Locating "<<sp <<" in "<<point(v));
    SM_point_locator L(&*v);
    Object_handle o = L.locate(sp);

    SFace_const_handle sf;
    if(!CGAL::assign( sf, o)) {
      CGAL_assertion_msg( 0, "it is not possible to decide which one is a visible facet (if any)");
      return Halffacet_const_handle();
    }
    /*    SM_decorator SD;
    if(this->sncp()->halfedges_begin() == this->sncp()->halfedges_end() || 
       SD.is_isolated(this->sncp()->halfedges_begin())) 
      return Halffacet_const_handle();  
    */

    SFace_cycle_const_iterator fc = sf->sface_cycles_begin(),
      fce = sf->sface_cycles_end();
    if( is_empty_range( fc, fce)) {
	CGAL_NEF_TRACEN( "no adjacent facet found.");
	f_visible =  Halffacet_const_handle();
    }
    else {
      SHalfedge_const_handle se; 
      SHalfloop_const_handle sl;
      SVertex_const_handle sv;