// Copyright (c) 2009 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) : Stephane Tayeb // //****************************************************************************** // File Description : //****************************************************************************** #ifndef CGAL_MESH_3_TRIANGULATION_HELPERS_H #define CGAL_MESH_3_TRIANGULATION_HELPERS_H #include #include namespace CGAL { namespace Mesh_3 { template class Triangulation_helpers { typedef typename Tr::Geom_traits Gt; typedef typename Gt::Point_3 Point_3; typedef typename Tr::Vertex_handle Vertex_handle; typedef typename Tr::Cell_handle Cell_handle; typedef std::vector Cell_vector; /** * A functor to reset visited flag of each facet of a cell */ struct Reset_facet_visited { void operator()(const Cell_handle& c) const { for ( int i=0; i<4 ; ++i ) c->reset_visited(i); } }; /** * A functor to get the point of a vertex vh, but replacing * it by m_p when vh == m_vh */ struct Point_getter { /// When the requested will be about vh, the returned point will be p /// instead of vh->point() Point_getter(const Vertex_handle &vh, const Point_3&p) : m_vh(vh), m_p(p) {} const Point_3& operator()(const Vertex_handle &vh) const { return (vh == m_vh ? m_p : vh->point()); } private: const Vertex_handle m_vh; const Point_3 &m_p; }; public: /// Constructor / Destructor Triangulation_helpers() {} ~Triangulation_helpers() {} /** * Moves point from \c v to \c p. */ void move_point(Tr& tr, const Vertex_handle& v, const Point_3& p) const; /** * Returns true if moving \c v to \c p makes no topological * change in \c tr */ bool no_topological_change(const Tr& tr, const Vertex_handle& v, const Point_3& p, Cell_vector& cells_tos) const; bool no_topological_change__without_set_point( const Tr& tr, const Vertex_handle& v, const Point_3& p, Cell_vector& cells_tos) const; bool no_topological_change(const Tr& tr, const Vertex_handle& v, const Point_3& p) const; bool no_topological_change__without_set_point( const Tr& tr, const Vertex_handle& v, const Point_3& p) const; bool inside_protecting_balls(const Tr& tr, const Vertex_handle& v, const Point_3& p) const; private: /** * Returns true if \c v is well_oriented on each cell of \c cell_tos */ // For sequential version bool well_oriented(const Tr& tr, const Cell_vector& cell_tos) const; // For parallel version bool well_oriented(const Tr& tr, const Cell_vector& cell_tos, const Point_getter& pg) const; }; template void Triangulation_helpers:: move_point(Tr& tr, const Vertex_handle& v, const Point_3& p) const { if ( no_topological_change(tr, v, p) ) v->set_point(p); else { tr.insert(p); tr.remove(v); } } template bool Triangulation_helpers:: no_topological_change(const Tr& tr, const Vertex_handle& v0, const Point_3& p, Cell_vector& cells_tos) const { bool np = true; Point_3 fp = v0->point(); v0->set_point(p); if(!well_oriented(tr, cells_tos)) { // Reset (restore) v0 v0->set_point(fp); return false; } // Reset visited tags of facets std::for_each(cells_tos.begin(), cells_tos.end(), Reset_facet_visited()); for ( typename Cell_vector::iterator cit = cells_tos.begin() ; cit != cells_tos.end() ; ++cit ) { Cell_handle c = *cit; for(int j=0; j<4; j++) { // Treat each facet only once if(c->is_facet_visited(j)) continue; // Set facet and it's mirror's one visited Cell_handle cj = c->neighbor(j); int mj = tr.mirror_index(c, j); c->set_facet_visited(j); cj->set_facet_visited(mj); Vertex_handle v1 = c->vertex(j); if(tr.is_infinite(v1)) { if(tr.side_of_power_sphere(c, cj->vertex(mj)->point(), false) != CGAL::ON_UNBOUNDED_SIDE) { np = false; break; } } else { if(tr.side_of_power_sphere(cj, v1->point(), false) != CGAL::ON_UNBOUNDED_SIDE) { np = false; break; } } } } // Reset (restore) v0 v0->set_point(fp); return np; } template bool Triangulation_helpers:: no_topological_change__without_set_point( const Tr& tr, const Vertex_handle& v0, const Point_3& p, Cell_vector& cells_tos) const { bool np = true; Point_getter pg(v0, p); if(!well_oriented(tr, cells_tos, pg)) { return false; } // Reset visited tags of facets std::for_each(cells_tos.begin(), cells_tos.end(), Reset_facet_visited()); for ( typename Cell_vector::iterator cit = cells_tos.begin() ; cit != cells_tos.end() ; ++cit ) { Cell_handle c = *cit; for(int j=0; j<4; j++) { // Treat each facet only once if(c->is_facet_visited(j)) continue; // Set facet and it's mirror's one visited Cell_handle cj = c->neighbor(j); int mj = tr.mirror_index(c, j); c->set_facet_visited(j); cj->set_facet_visited(mj); Vertex_handle v1 = c->vertex(j); if(tr.is_infinite(v1)) { // Build a copy of c, and replace V0 by a temporary vertex (position "p") typename Cell_handle::value_type c_copy (*c); int i_v0; typename Vertex_handle::value_type v; if (c_copy.has_vertex(v0, i_v0)) { v.set_point(p); c_copy.set_vertex(i_v0, Tr::Triangulation_data_structure::Vertex_range::s_iterator_to(v)); } Cell_handle c_copy_h = Tr::Triangulation_data_structure::Cell_range::s_iterator_to(c_copy); if(tr.side_of_power_sphere(c_copy_h, pg(cj->vertex(mj)), false) != CGAL::ON_UNBOUNDED_SIDE) { np = false; break; } } else { // Build a copy of cj, and replace V0 by a temporary vertex (position "p") typename Cell_handle::value_type cj_copy (*cj); int i_v0; typename Vertex_handle::value_type v; if (cj_copy.has_vertex(v0, i_v0)) { v.set_point(p); cj_copy.set_vertex(i_v0, Tr::Triangulation_data_structure::Vertex_range::s_iterator_to(v)); } Cell_handle cj_copy_h = Tr::Triangulation_data_structure::Cell_range::s_iterator_to(cj_copy); if(tr.side_of_power_sphere(cj_copy_h, pg(v1), false) != CGAL::ON_UNBOUNDED_SIDE) { np = false; break; } } } } return np; } template bool Triangulation_helpers:: no_topological_change(const Tr& tr, const Vertex_handle& v0, const Point_3& p) const { Cell_vector cells_tos; cells_tos.reserve(64); tr.incident_cells(v0, std::back_inserter(cells_tos)); return no_topological_change(tr, v0, p, cells_tos); } template bool Triangulation_helpers:: no_topological_change__without_set_point( const Tr& tr, const Vertex_handle& v0, const Point_3& p) const { Cell_vector cells_tos; cells_tos.reserve(64); tr.incident_cells(v0, std::back_inserter(cells_tos)); return no_topological_change__without_set_point(tr, v0, p, cells_tos); } template bool Triangulation_helpers:: inside_protecting_balls(const Tr& tr, const Vertex_handle& v, const Point_3& p) const { Vertex_handle nv = tr.nearest_power_vertex(p, v->cell()); if(nv->point().weight() > 0) return CGAL::compare_squared_distance(p, nv->point(), nv->point().weight()) != CGAL::LARGER; return false; } /// This function well_oriented is called by no_topological_change after a /// v->set_point(p) template bool Triangulation_helpers:: well_oriented(const Tr& tr, const Cell_vector& cells_tos) const { typename Cell_vector::const_iterator it = cells_tos.begin(); for( ; it != cells_tos.end() ; ++it) { Cell_handle c = *it; if( tr.is_infinite(c) ) { int iv = c->index(tr.infinite_vertex()); Cell_handle cj = c->neighbor(iv); int mj = tr.mirror_index(c, iv); if(CGAL::orientation(cj->vertex(mj)->point(), c->vertex((iv+1)&3)->point(), c->vertex((iv+2)&3)->point(), c->vertex((iv+3)&3)->point()) != CGAL::NEGATIVE) return false; } else if(CGAL::orientation(c->vertex(0)->point(), c->vertex(1)->point(), c->vertex(2)->point(), c->vertex(3)->point()) != CGAL::POSITIVE) return false; } return true; } /// Another version for the parallel version /// Here, the set_point is not done before, but we use a Point_getter instance /// to get the point of a vertex. template bool Triangulation_helpers:: well_oriented(const Tr& tr, const Cell_vector& cells_tos, const Point_getter& pg) const { typename Cell_vector::const_iterator it = cells_tos.begin(); for( ; it != cells_tos.end() ; ++it) { Cell_handle c = *it; if( tr.is_infinite(c) ) { int iv = c->index(tr.infinite_vertex()); Cell_handle cj = c->neighbor(iv); int mj = tr.mirror_index(c, iv); if(CGAL::orientation(pg(cj->vertex(mj)), pg(c->vertex((iv+1)&3)), pg(c->vertex((iv+2)&3)), pg(c->vertex((iv+3)&3))) != CGAL::NEGATIVE) return false; } else if(CGAL::orientation(pg(c->vertex(0)), pg(c->vertex(1)), pg(c->vertex(2)), pg(c->vertex(3))) != CGAL::POSITIVE) return false; } return true; } } // end namespace Mesh_3 } //namespace CGAL #endif // CGAL_MESH_3_TRIANGULATION_HELPERS_H