CGAL/cgal

static thread_local variables in remove/move functions of `CGAL::Delaunay_triangulation_2`

Closed this issue · 0 comments

lrineau commented

Issue Details

The class template CGAL::Delaunay_triangulation_2 has four member functions using the same pattern:

  • remove(Vertex_handle v)
  • remove_and_give_new_faces(Vertex_handle v, OutputItFaces fit),
  • move_if_no_collision(Vertex_handle v, const Point &p), and
  • move_if_no_collision_and_give_new_faces(Vertex_handle v, const Point &p, OutputItFaces oif).

In these four functions, the following lines of code appear:

    CGAL_STATIC_THREAD_LOCAL_VARIABLE(int, maxd,30);
    CGAL_STATIC_THREAD_LOCAL_VARIABLE(std::vector<Face_handle>, f, maxd);
    CGAL_STATIC_THREAD_LOCAL_VARIABLE(std::vector<int>, i, maxd);
    CGAL_STATIC_THREAD_LOCAL_VARIABLE(std::vector<Vertex_handle>, w, maxd);

    int d;
    remove_degree_init(v,f,w,i,d,maxd);
    if(d == 0) return; //  dim is going down     (OPTIONAL LINE)
    remove_degree_triangulate(v,f,w,i,d);

The private member function remove_degree_init fills the vectors f, i, and w with data
related to the removal of the vertex v.

  • The integer d is set to the degree of v,
  • f is the sequence of faces incident to v before the removal,
  • i is the sequence of indices of v in these faces,
  • w is the sequence of vertices incident to v before the removal.

The integer maxd is a static thread-local variable initialized to 30, and is always the capacity
of the vectors f, i, and w. maxd is also the size of these vectors, where only the d first
elements of the vectors are used.

The code, since the work of Olivier Devillers in 2009 1, then has special code to retriangulate
after the removal of v if d is between 3 and 7, and call a general code otherwise. That is the
role of the function remove_degree_triangulate:

cgal/Triangulation_2/include/CGAL/Delaunay_triangulation_2.h

Lines 1120 to 1142 in 1dabf3b

template < class Gt, class Tds >
void
Delaunay_triangulation_2<Gt,Tds>::
remove_degree_triangulate(Vertex_handle v,
std::vector<Face_handle> &f,
std::vector<Vertex_handle> &w,
std::vector<int> &i,int d)
{
switch (d) {
case 3:
remove_degree3(v,f,w,i); break;
case 4:
remove_degree4(v,f,w,i); break;
case 5:
remove_degree5(v,f,w,i); break;
case 6:
remove_degree6(v,f,w,i); break;
case 7:
remove_degree7(v,f,w,i); break;
default:
remove_degree_d(v,f,w,i,d); break;
}
}

The call remove_degree_d(v,f,w,i,d) is the general code, and actually ignores the variable d and
the vectors f, w, and i.

That means that, if d is greater than 7, the vectors f, w, and i are filled with data that is not used
at all. The same happens if the removal of v will trigger a decrase of the dimension, but in these
cases the functions apply a special code that does not use these vectors at all, return after the
call to remove_degree_init.

The variables maxd, f, i, and w are static thread-local to avoid memory allocation of
new vectors for each call to these functions. This is a good idea.

But those vectors are only used if the degree d of the vertex v is between 3 and 7. That means
those functions could be modified to avoid std::vector and use std::array instead, with a fixed
size of 7.

Note

CGAL::Periodic_2_Delaunay_triangulation_2 has the same sort of implementation to modified. That is tracked by issue #9059.

Steps to-do

  • Change the definitions of the variables.
  • The private function remove_degree_init will be modified to abort and return with d=8 as soon as it detects that the degree of v is more than 7.
  • The private functions remove_degree_triangulate, remove_degree3, remove_degree4, remove_degree5, remove_degree6, remove_degree7, and remove_degree_d will have to be changed to replace std::vector by std::array.
  • Same for CGAL::Periodic_2_Delaunay_triangulation_2.

Environment

  • CGAL version: all supported CGAL versions

Footnotes

  1. Olivier Devillers. Vertex Removal in Two Dimensional Delaunay Triangulation: Asymptotic Complexity is Pointless. [Research Report] RR-7104, INRIA. 2009, pp.15. ↩