// Copyright (c) 2003-2004 INRIA Sophia-Antipolis (France).
// 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/Mesh_2/include/CGAL/Mesher_level.h,v $
// $Revision: 1.10 $ $Date: 2004/11/18 14:22:26 $
// $Name: $
//
// Author(s) : Laurent RINEAU
#ifndef CGAL_MESHER_LEVEL_H
#define CGAL_MESHER_LEVEL_H
#include <utility>
namespace CGAL {
struct Null_mesh_visitor {
const Null_mesh_visitor& previous_level() const { return *this; }
template <typename E, typename P>
void before_conflicts(E, P) const {}
template <typename E, typename P, typename Z>
void before_insertion(E, P, Z) const {}
template <typename V>
void after_insertion(V) const {}
template <typename E, typename P, typename Z>
void after_no_insertion(E, P, Z) const {}
};
struct Null_mesher_level {
template <typename Visitor>
void refine(Visitor) {}
template <typename P, typename Z>
std::pair<bool, bool> test_point_conflict_from_superior(P, Z)
{
return std::make_pair(true, true);
}
bool is_algorithm_done() const
{
return true;
}
template <typename Visitor>
bool try_to_insert_one_point(Visitor)
{
return true;
}
template <typename Visitor>
bool one_step(Visitor)
{
return true;
}
}; // end Null_mesher_level
template <
class Triangulation_traits, /**< Traits class that defines operations
from the trianguilation. */
class Derived, /**< Derived class, that implements methods */
class Element, /**< Type of elements that this level refines. */
class Previous = Null_mesher_level /**< Previous level type,
defaults to \c Null_level
*/
>
class Mesher_level
{
public:
/** Type of triangulation that is meshed. */
typedef typename Triangulation_traits::Triangulation Triangulation;
/** Type of point that are inserted into the triangulation. */
typedef typename Triangulation_traits::Point Point;
/** Type of vertex handles that are returns by insertions into the
triangulation. */
typedef typename Triangulation_traits::Vertex_handle Vertex_handle;
/** Type of the conflict zone for a point that can be inserted. */
typedef typename Triangulation_traits::Zone Zone;
typedef Element Element_type;
typedef Previous Previous_level;
private:
/** \name Private member functions */
/** Curiously recurring template pattern. */
//@{
Derived& derived()
{
return static_cast<Derived&>(*this);
}
const Derived& derived() const
{
return static_cast<const Derived&>(*this);
}
//@}
/** \name Private member datas */
Previous& previous_level; /**< The previous level of the refinement
process. */
public:
typedef Mesher_level<Triangulation_traits,
Derived,
Element,
Previous_level> Self;
/** \name CONSTRUCTORS */
Mesher_level(Previous_level& previous)
: previous_level(previous)
{
}
/** \name FUNCTIONS IMPLEMENTED IN THE CLASS \c Derived */
/** Access to the triangulation */
//@{
Triangulation& triangulation()
{
return derived().get_triangulation_ref();
}
const Triangulation& triangulation() const
{
return derived().get_triangulation_ref();
}
//@}
/** Access to the triangulation traits */
//@{
Triangulation_traits& triangulation_traits()
{
return derived().get_triangulation_traits();
}
const Triangulation_traits& triangulation_traits() const
{
return derived().get_triangulation_traits();
}
//@}
/** Called before the first refinement, to initialized the queue of
elements that should be refined. */
void scan_triangulation()
{
derived().do_scan_triangulation();
}
/** Tells if, as regards the elements of type \c Element, the refinement is
done. */
bool no_longer_element_to_refine()
{
return derived().is_no_longer_element_to_refine();
}
/** Retrieves the next element that could be refined. */
Element get_next_element()
{
return derived().do_get_next_element();
}
/** Remove from the list the next element that could be refined. */
void pop_next_element()
{
derived().do_pop_next_element();
}
/** Gives the point that should be inserted to refine the element \c e */
Point refinement_point(const Element& e)
{
return derived().get_refinement_point(e);
}
/** Actions before testing conflicts for point \c p and element \c e */
template <typename Mesh_visitor>
void before_conflicts(const Element& e, const Point& p,
Mesh_visitor& visitor)
{
visitor.before_conflicts(e, p);
derived().do_before_conflicts(e, p);
}
/** Tells if, as regards this level of the refinement process, if the
point conflicts with something, and do what is needed. The return
type is made of two booleans:
- the first one tells if the point can be inserted,
- in case of, the first one is \c false, the second one tells if
the tested element should be reconsidered latter.
*/
std::pair<bool, bool> private_test_point_conflict(const Point& p,
Zone& zone)
{
return derived().do_private_test_point_conflict(p, zone);
}
/** Tells if, as regards this level of the refinement process, if the
point conflicts with something, and do what is needed. The return
type is made of two booleans:
- the first one tells if the point can be inserted,
- in case of, the first one is \c false, the second one tells if
the tested element should be reconsidered latter.
This function is called by the superior level, if any.
*/
std::pair<bool, bool> test_point_conflict_from_superior(const Point& p,
Zone& zone)
{
return derived().do_test_point_conflict_from_superior(p, zone);
}
/**
* Actions before inserting the point \c p in order to refine the
* element \c e. The zone of conflicts is \c zone.
*/
template <class Mesh_visitor>
void before_insertion(Element& e, const Point& p, Zone& zone,
Mesh_visitor& visitor)
{
visitor.before_insertion(e, p, zone);
derived().do_before_insertion(e, p, zone);
}
/** Actions after having inserted the point.
* \param vh is the vertex handle of the inserted point,
* \param visitor is the visitor.
*/
template <class Mesh_visitor>
void after_insertion(Vertex_handle vh, Mesh_visitor& visitor)
{
derived().do_after_insertion(vh);
visitor.after_insertion(vh);
}
/** Actions after testing conflicts for point \c p and element \c e
* if no point is inserted. */
template <class Mesh_visitor>
void after_no_insertion(const Element& e, const Point& p, Zone& zone,
Mesh_visitor& visitor)
{
derived().do_after_no_insertion(e, p, zone);
visitor.after_no_insertion(e, p, zone);
}
/** DEFAULT IMPLEMENTATION FUNCTIONS
*
* This bunch of functions should be implemented in the derived class:
*
* Tr& get_triangulation_ref();
* const Tr& get_triangulation_ref();
*
* void do_scan_triangulation();
*
* bool is_no_longer_element_to_refine();
*
* Element do_get_next_element();
*
* void pop_next_element();
*
* Point get_refinement_point(Element);
*
*
* The next ones have default implementations that do nothing:
*
*/
// void do_before_conflicts(const Element&, const Point&)
// {
// }
// void do_after_no_insertion(Element, Point, Zone)
// {
// }
// std::pair<bool, bool>
// do_private_test_point_conflict(Point, Zone)
// {
// return std::make_pair(true, true);
// }
// std::pair<bool, bool>
// do_test_point_conflict_from_superior(Point, Zone)
// {
// return std::make_pair(true, true);
// }
// void do_before_insertion(Element, Point, Zone)
// {
// }
// void do_after_insertion(Vertex_handle)
// {
// }
/** \name MESHING PROCESS
*
* The following functions use the functions that are implemented in the
* derived classes.
*
*/
/**
* Tells it the algorithm is done, regarding elements of type \c Element
* or elements of previous levels.
*/
bool is_algorithm_done()
{
return ( previous_level.is_algorithm_done() &&
no_longer_element_to_refine() );
}
/** Refines elements of this level and previous levels. */
template <class Mesh_visitor>
void refine(Mesh_visitor& visitor)
{
while(! is_algorithm_done() )
{
previous_level.refine(visitor.previous_level());
if(! no_longer_element_to_refine() )
process_one_element(visitor);
}
}
/**
* This function takes one element from the queue, and try to refine
* it. It returns \c true if one point has been inserted.
* @todo Merge with try_to_refine_element().
*/
template <class Mesh_visitor>
bool process_one_element(Mesh_visitor& visitor)
{
Element e = get_next_element();
const std::pair<bool, bool> result = try_to_refine_element(e, visitor);
if(result.second)
pop_next_element();
return result.first;
}
template <class Mesh_visitor>
std::pair<bool, bool>
try_to_refine_element(Element e, Mesh_visitor& visitor)
{
const Point& p = refinement_point(e);
before_conflicts(e, p, visitor);
Zone zone =
triangulation_traits().get_conflicts_zone(triangulation(), p);
const std::pair<bool, bool> result = test_point_conflict(p, zone);
if(result.first)
{
before_insertion(e, p, zone, visitor);
Vertex_handle v = triangulation_traits().insert(triangulation(),
p, zone);
after_insertion(v, visitor);
return std::make_pair(true, true);
}
else
after_no_insertion(e, p, zone, visitor);
return result;
}
/** Return (can_split_the_element, drop_element). */
std::pair<bool, bool>
test_point_conflict(const Point& p, Zone& zone)
{
const std::pair<bool, bool> result =
previous_level.test_point_conflict_from_superior(p, zone);
if( result.first == false )
return result;
return private_test_point_conflict(p, zone);
}
/** \name STEP BY STEP FUNCTIONS */
/**
* Inserts exactly one point, if possible, and returns \c false if no
* point has been inserted because the algorithm is done.
*/
template <class Mesh_visitor>
bool try_to_insert_one_point(Mesh_visitor& visitor)
{
while(! is_algorithm_done() )
{
if( previous_level.try_to_insert_one_point(visitor.previous_level()) )
return true;
if(! no_longer_element_to_refine() )
if( process_one_element(visitor) )
return true;
}
return false;
}
/**
* Applies one step of the algorithm: tries to refine one element of
* previous level or one element of this level. Return \c false iff
* <tt> is_algorithm_done()==true </tt>.
*/
template <class Mesh_visitor>
bool one_step(Mesh_visitor& visitor)
{
if( ! previous_level.is_algorithm_done() )
previous_level.one_step(visitor.previous_level());
else
if( ! no_longer_element_to_refine() )
process_one_element(visitor);
return ! is_algorithm_done();
}
}; // end Mesher_level
} // end namespace CGAL
#endif // CGAL_MESHER_LEVEL_H
syntax highlighted by Code2HTML, v. 0.9.1