// Copyright (c) 2003-2007 INRIA Sophia-Antipolis (France). // All rights reserved. // // This file is part of CGAL (www.cgal.org). // You can redistribute it and/or modify it under the terms of the GNU // General Public License as published by the Free Software Foundation, // either version 3 of the License, or (at your option) any later version. // // 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$ // $Id$ // // // Author(s) : Steve OUDOT, Laurent Rineau #ifndef CGAL_SURFACE_MESHER_POLYHEDRAL_ORACLE_H #define CGAL_SURFACE_MESHER_POLYHEDRAL_ORACLE_H #include #include // CGAL_DEPRECATED #include #include #include namespace CGAL { namespace Surface_mesher { template < class Surface, class Point_creator = Creator_uniform_3, class Visitor = Null_oracle_visitor, typename Has_edges_tag_ = typename Surface::Has_edges_tag, bool mesh_the_whole_bounding_box = false > class Polyhedral_oracle : Has_edges_tag_ { public: typedef typename Surface::Geom_traits GT; typedef GT Geom_traits; typedef typename GT::FT FT; typedef typename Geom_traits::Point_3 Point; typedef typename Surface::Subfacets_tree Subfacets_tree; typedef typename Surface::Subsegments_tree Subsegments_tree; typedef typename Subsegments_tree::Point_with_index Point_with_index; typedef typename Geom_traits::Segment_3 Segment_3; typedef typename Geom_traits::Ray_3 Ray_3; typedef typename Geom_traits::Line_3 Line_3; typedef typename Geom_traits::Triangle_3 Triangle_3; typedef Polyhedral_oracle Self; typedef Surface Surface_3; typedef Point Intersection_point; // Private members private: Visitor visitor; public: // Public members // Surface constructor Polyhedral_oracle(Visitor visitor_ = Visitor() ) : visitor(visitor_) { // is.seekg(0,std::ios::beg); // tr.clear(); // // The data structure for testing intersections is set // std::cerr << "Creating data structure for intersections detection... "; // data_struct.input(is, CGAL::Insert_iterator(tr)); // std::cerr << "done\n\n"; } // Finite_vertices_iterator finite_vertices_begin() // { // return tr.finite_vertices_begin(); // } // Finite_vertices_iterator finite_vertices_end() // { // return tr.finite_vertices_end(); // } class Intersect_3; friend class Intersect_3; class Intersect_3 { const Self& self; public: Intersect_3(const Self& self) : self(self) { } Object operator()(const Surface_3& surface, const Segment_3& s) const { #ifdef CGAL_SURFACE_MESHER_POLYHEDRAL_SURFACE_USE_PINPOLYHEDRON double pa[3], pb[3]; pa[0] = s[0].x(); pa[1] = s[0].y(); pa[2] = s[0].z(); pb[0] = s[1].x(); pb[1] = s[1].y(); pb[2] = s[1].z(); if(surface.pinpolyhedron_ptr->isPinPolyhedron(pa) == surface.pinpolyhedron_ptr->isPinPolyhedron(pb)) return Object(); #endif // CGAL_SURFACE_MESHER_POLYHEDRAL_SURFACE_USE_PINPOLYHEDRON #ifdef CGAL_SURFACE_MESHER_POLYHEDRAL_SURFACE_USE_OCTREE return self.intersect_segment_surface(*surface.subfacets_tree_ptr, s); #endif #ifdef CGAL_SURFACE_MESHER_POLYHEDRAL_SURFACE_USE_INTERSECTION_DATA_STRUCTURE return surface.subfacets_tree_ptr->intersection(s); #endif } Object operator()(const Surface_3& surface, const Ray_3& r) const { #ifdef CGAL_SURFACE_MESHER_POLYHEDRAL_SURFACE_USE_OCTREE return self.intersect_ray_surface(*surface.subfacets_tree_ptr, r); #endif return Object(); } Object operator()(const Surface_3& surface, const Line_3& l) const { #ifdef CGAL_SURFACE_MESHER_POLYHEDRAL_SURFACE_USE_OCTREE return self.intersect_line_surface(*surface.subfacets_tree_ptr, l); #endif return Object(); } }; Intersect_3 intersect_3_object() const { return Intersect_3(*this); } class Construct_initial_points; friend class Construct_initial_points; class Construct_initial_points { const Self& self; public: Construct_initial_points(const Self& self) : self(self) { } template OutputIteratorPoints operator() (const Surface_3& surface, OutputIteratorPoints out, int n = 20) const // WARNING: why 20? { for (typename Surface_3::Corner_vertices::const_iterator vit = surface.corner_vertices_ptr->begin(); vit != surface.corner_vertices_ptr->end(); ++vit) { Point p = (*vit)->point(); CGAL_assertion((*vit)->tag() >= 0); p.set_on_vertex((*vit)->tag()); self.visitor.new_point(p); *out++= p; } for (typename Surface_3::Edges_vertices::const_iterator vit = surface.edges_vertices_ptr->begin(); vit != surface.edges_vertices_ptr->end() && n > 0; ++vit, --n) { Point p = (*vit)->point(); CGAL_assertion((*vit)->tag() >= 0); p.set_on_curve((*vit)->tag()); self.visitor.new_point(p); *out++= p; } for (typename Surface_3::Input_vertices::const_iterator vit = surface.input_vertices_ptr->begin(); vit != surface.input_vertices_ptr->end() && n > 0; ++vit, --n) { Point p = (*vit)->point(); CGAL_assertion((*vit)->tag() >= 0); p.set_on_surface((*vit)->tag()); self.visitor.new_point(p); *out++= p; } return out; } }; Construct_initial_points construct_initial_points_object() const { return Construct_initial_points(*this); } template bool is_in_volume(const Surface_3& surface, const P& p) { if(mesh_the_whole_bounding_box) return CGAL::do_overlap(surface.bbox(),p.bbox()); #ifdef CGAL_SURFACE_MESHER_POLYHEDRAL_SURFACE_USE_PINPOLYHEDRON double point[3]; point[0] = p.x(); point[1] = p.y(); point[2] = p.z(); return surface.pinpolyhedron_ptr->isPinPolyhedron(point); #endif // CGAL_SURFACE_MESHER_POLYHEDRAL_SURFACE_USE_PINPOLYHEDRON typename CGAL::Random_points_on_sphere_3 random_point(FT(1)); typename Geom_traits::Construct_vector_3 vector = Geom_traits().construct_vector_3_object(); typename Geom_traits::Construct_segment_3 segment = Geom_traits().construct_segment_3_object(); typename Geom_traits::Construct_translated_point_3 translate = Geom_traits().construct_translated_point_3_object(); typename Geom_traits::Bounded_side_3 bounded_side = Geom_traits().bounded_side_3_object(); typename Geom_traits::Construct_scaled_vector_3 scale = Geom_traits().construct_scaled_vector_3_object(); const typename GT::Iso_cuboid_3& cuboid = surface.subfacets_tree_ptr->iso_cuboid(); if( bounded_side(cuboid, p) == ON_UNBOUNDED_SIDE ) return false; #ifdef CGAL_SURFACE_MESHER_DEBUG_INTERSECTION_DATA_STRUCTURE std::cerr << "(in volume) "; #endif std::pair result = std::make_pair(false, 0); // upper bound of the diameter of the bounding box const FT& diameter = 2*FT(surface.subfacets_tree_ptr->max_length()); while(! result.first) { result = surface.subfacets_tree_ptr-> number_of_intersections(segment(p, translate(p, scale(vector(ORIGIN, *random_point++), diameter)))); } return (result.second % 2) == 1; } Object intersect_curves_with_triangle(const Surface_3& surface, const Triangle_3& t) const { if(! surface.has_edges()) return Object(); const Object o = surface.subsegments_tree_ptr->intersection(t); if(const Point_with_index* pi = object_cast(&o)) { Point p = *pi; CGAL_assertion(pi->surface_index()>=0); p.set_on_curve(pi->surface_index()); visitor.new_point(p); return make_object(p); } else return Object(); } // // Basic intersection function for segments/rays/lines with the polyhedron // template // CGAL::Object intersect_with_surface (Octree data_struct, Elt e) { // typedef CGAL::Data_structure_using_tree_3 Octree; // for ( typename Octree::Constraint_map_iterator cit = data_struct.c_m.begin(); // cit != data_struct.c_m.end(); ++cit ) { // if (cit->second->does_intersect (e)) // return cit->second->intersection (e); // } // return CGAL::Object(); // } #ifdef CGAL_SURFACE_MESHER_POLYHEDRAL_SURFACE_USE_OCTREE CGAL::Object intersect_segment_surface(const Subfacets_tree& data_struct, const Segment_3& s) const { typename Geom_traits::Is_degenerate_3 is_degenerate; // debug: test if segment is degenerate // (can happen, because of rounding in circumcenter computations) if (is_degenerate(s)) { std::cerr << "Warning: degenerate segment (" << s << ")\n"; return CGAL::Object(); } // debug: for detecting whether Marie's code works // (we compare with our basic intersection function) // CGAL::Object oun, odeux; // Point p; // oun = data_struct.intersection(s.vertex(0), s.vertex(1)); // odeux = intersect_with_surface (s); // odeux = oun; // if ((assign(p, oun) && !assign(p,odeux)) || // !assign(p, oun) && assign(p,odeux)) // std::cout << "s " << s // << " " << (assign(p, odeux)) // << std::endl; const Object o = data_struct.intersection(s.vertex(0), s.vertex(1)); if(const Point_with_index* pi = object_cast(&o)) { Point p = *pi; CGAL_assertion(pi->surface_index()>=0); p.set_on_surface(pi->surface_index()); visitor.new_point(p); return make_object(p); } else return Object(); /* return intersect_with_surface (s); // basic intersection function */ /* return data_struct.intersection (s.vertex(0), s.vertex(1)); // Marie */ } CGAL::Object intersect_ray_surface(const Subfacets_tree& data_struct, const Ray_3 &r) const { typename Geom_traits::Is_degenerate_3 is_degenerate; // debug: test if segment is degenerate // (can happen, because of rounding in circumcenter computations) if (is_degenerate(r)) { std::cerr << "Warning: degenerate ray (" << r << ")\n"; return CGAL::Object(); } // debug: for detecting whether Marie's code works // (we compare with our basic intersection function) // CGAL::Object oun, odeux; // Point p; // oun = data_struct.intersection (r); // // odeux = intersect_with_surface (r); // odeux = oun; // if ((assign(p, oun) && !assign(p,odeux)) || // !assign(p, oun) && assign(p,odeux)) // std::cout << "r " << r // << " " << (assign(p, odeux)) // << std::endl; // return odeux; const Object o = data_struct.intersection (r); if(const Point_with_index* pi = object_cast(&o)) { Point p = *pi; CGAL_assertion(pi->surface_index()>=0); p.set_on_surface(pi->surface_index()); visitor.new_point(p); return make_object(p); } else return Object(); // return intersect_with_surface (r); // basic intersection function // return data_struct.intersection (r); // Marie's code } CGAL::Object intersect_line_surface(const Subfacets_tree&, const Line_3 &) const { CGAL_error(); return CGAL::Object(); } #endif // CGAL_SURFACE_MESHER_POLYHEDRAL_SURFACE_USE_OCTREE private: }; // end class Polyhedral_oracle template class CGAL_DEPRECATED Polyhedral : public Polyhedral_oracle { Polyhedral(Visitor visitor = Visitor()) : Polyhedral_oracle(visitor) { } }; } // end namespace Surface_mesher } // end namespace CGAL #endif // CGAL_SURFACE_MESHER_POLYHEDRAL_ORACLE_H