Parallel T3: locking the infinite vertex

[MaelRL]

Edit: this issue has been discussed between @lrineau and @MaelRL, see below https://github.com/CGAL/cgal/issues/4660#issuecomment-1579083092.

---

While working on a parallel triangulation (e.g. during a locate), we try to lock cells to ensure safe operations on this subset. This locking is done by blocking grid blocks. On the other hand, the triangulation has a vertex whose position is uninitialized: the infinite vertex. Those coordinates are uninitialized: Triangulation_vertex_base_3() : DSVb() {} (so not even default constructed). This was a problem for the new filtered exact kernel because it complains about uninitialized values.

When we lock a cell, we lock its four vertices, but nothing checks that the cell is infinite. The coordinates of the infinite vertex could be anything, so:

• it could be outside the grid and then it's pointless to call try_lock() on this point (?);
• it could be inside the grid and then it's locking grid blocks that shouldn't be locked.

Some questions:

• How does that even properly work since nothing guarantees that the position of the infinite vertex falls within the grid?
• I can't find any place where we would intentionally do try_lock_vertex(infinite_vertex->point()) (without going through try_lock_cell), is it indeed the case?
• Could we somehow replace the infinite vertex lock by a combinatorial lock? The issue is that the incident_cells() function requires itself a lock, so it's a bit of a tail-biting snake.

[sloriot]

The following test is failing, reveled by #7115 (@MaelRL could reproduce the error with master)

[MaelRL]

I was talking about a different error and source (https://github.com/CGAL/cgal/issues/7163)

[lrineau]

Code not thread-safe in Regular_triangulation_3.

Even after the pull-requests #7448 and #7496, this kind of code is still not safe: https://github.com/CGAL/cgal/blob/8cd8bc7b0604d03511bb318ab2dc4c050e214562/Triangulation_3/include/CGAL/Regular_triangulation_3.h#L1461-L1473

because the vertex m_rt.finite_vertices_begin() might be under destruction by another thread, and it is not locked. Thus, dereferencing it to access its points is a race-condition.

Proposal

The solution is to use infinite_vertex() instead, because that it the only vertex that is guaranteed to be kept. But there is an another issue with the locking of the infinite_vertex() (see below).

Locking of the infinite_vertex()

The locking of the infinite_vertex() is an undefined behavior (and a segfault with an exact kernel without filtering). The reason is that its point is not initialized.

• With Epick, we get an uninitialized point, with whatever double coordinates are in memory, and we might lock whatever cell of the spatial lock grid.
• With Epeck, the point is uninitialized as well. That means that its intervals are initialized by default, to [0, 1]. See: https://github.com/CGAL/cgal/blob/8cd8bc7b0604d03511bb318ab2dc4c050e214562/Number_types/include/CGAL/Interval_nt.h#L73-L83 And thus the to_double(point.x()) gives the center of that interval, 0.5, for all coordinates. The locking of the infinite vertex locks the cell around the point Point_3(.5, .5, .5).
• With an exact kernel without filtering, like Simple_cartesian<Exact_rational>, the coordinates of the point of the infinite vertex are uninitialized, and an attempt to lock it will result with an assertion or a segfault.

Proposal

The lock data structure should have a special function lock_infinite_vertex(). Its implementation in Spatial_lock_grid_3 could be the lock of an extra cell of index num_grid_cells_per_axis*num_grid_cells_per_axis*num_grid_cells_per_axis + 1 in the lock grid. An additional function must be added to Triangulation_3, to allow the locking of a regular vertex or of the infinite vertex. All call to try_lock_point must be check, to see if a vertex can be locked instead.