Subject: [Fenics] New mesh intersection functionality in DOLFIN

From: Andre Massing <[email-masked]>
Date: Sun, 06 Dec 2009 10:33:47 +0100

Hi,

some new mesh intersection functionality made it into the DOLFIN 
development trunk. Basically the old GTS based interface was replaced by 
an extended interface, which relies on the Computational Geometry 
Algorithms Library (CGAL, http://www.cgal.org ). The decision for the 
change was founded on the fact, that CGAL provides a lot more 
functionality and sophisticated algorithms, an extensive documentation 
and a big and active development community, so that we hope, that the 
mesh related parts of DOLFIN will benefit from CGAL.

The changes can be summarized as follows:

1. The already existing intersection detection for mesh and points (2d, 
3d) and the intersection detection of a 2d mesh with a 1d mesh was replaced.

2. The following intersection detection functionality was added:
- Point - Mesh: 1d (yes, this was missing :)
- Mesh - Mesh: 2d-2d, 3d-2d, and 3d-3d (computes all cell ids for one 
mesh, now *uniquely* collected in a std:set)

There exists a python demo in demo/mesh/intersection/3D/python/
which illustrates the intersection of a UnitCube with the boundary a of 
UnitSphere.

Also the existing 2d has been updated in demo/mesh/intersection/2D/
(cpp and python version)

The C++ interface in the Mesh class now contains the following functions 
(with counterparts in python)

///Compute all id of all cells which are intersects by a point.
///The ids of the intersected entities are saved in a set for efficiency
///reasons, to avoid to sort out duplicates later on.
void all_intersected_entities(const Point & point, uint_set & 
ids_result) const;

///Compute all id of all cells which are intersects any point in points.
void all_intersected_entities(const std::vector<Point> & points, 
uint_set & ids_result) const;

///Compute all id of all cells which are intersects by the given mesh 
///another_mesh;
void all_intersected_entities(const Mesh & another_mesh, uint_set & 
ids_result) const;

///Computes only the first id  of the entity, which contains the point. 
Returns -1 if no cell is intersected.
int any_intersected_entity(const Point & point) const;

The implementation is mainly done in the new IntersectionOperator class 
(opposed to the old IntersectionDetector class).

///Reference to the intersection operator, which implements the actual 
///intersection functionality
IntersectionOperator& intersection_operator();

It would be nice to receive  as many comments, suggestions, criticism 
and  bug reports as possible before the next DOLFIN release, so please 
try out and torture the examples/code :)

So far the old GTS based IntersectorDetector class is still available 
for testing, comparison and debugging purposes, but will likely be 
removed in the future.

Happy intersecting,
Andre