AABB tree: add closest point location and primitive

[sloriot]

Summary of Changes

Add a function in the AABB-tree that in addition of the closest primitives can provide more information on where on the closest primitive the closest point is. For example in a triangle mesh, we would know if the closest point is on a vertex, an edge or inside a face of the mesh.

Release Management

• Affected package(s): AABB_tree, Kernel_23
• Feature/Small Feature (if any): TODO
• Replaces: #1855

[sloriot]

Current documentation issue: The function closest_point_location_and_primitive() requires an initialization of the hint. The way AABB_tree::Point_location is documented does not imposed anything on the return type of AABBTraits::Closest_point (for the second overload) but to be explicitly convertible to Point_3. For now the code set a dimension and a index members that are not documented. Also in AABB_traversal_traits.h, Projection_traits_point_and_location::intersection() the update of the closest primitive is also using these undocumented members.

[sloriot]

Code issue closest_point_and_primitive() uses a construction for getting the closest primitive in the traversal traits. If we want to guarantee that the primitive returned is the closest with a kernel with exact predicates only (even if the projection is approximated) we need to use a predicate that relies on an exact projection or that uses only the current closest primitive. This issue is not specific to this PR but since this PR introduces a new similar function, a solution should be found for both. Something to take into account is also to avoid penalizing a usage where an approximated closest primitive is fine (having several versions of the function?)

[sloriot]

Code issue: The functor Construct_projected_point_and_location_3 is a construction and require a kernel with exact constructions. It is used in the AABB_tree in the function closest_point_location_and_primitive() when using a CGAL Kernel, which in practice is always a kernel with exact predicates but inexact constructions. AABBB_polyhedron_facet_distance_example.cpp has been update to show the problem.

What would be nice is to update the code of Construct_projected_point_and_location_3 so that dimension and index are set correctly if we use exact predicates. The current version of the code for a triangle works as follow:

• compute the projection of the query point in the supporting plane
• check for each edge of the triangle if the projected point is on the side of the same side as the triangle wrt the edge (predicate_1)
  • if yes then the current is not the one closest to the query point
  • if not, we check whether the projected point is strictly between the lines perpendicular to the edge at its endpoint. This checks if the edge is the closest to the projected point. (predicate_2)
• if the projected point is not closer to an edge then we look for the closest vertex.

We can rewrite predicate_1 and predicate_2 so that they are using the query point rather than the projected point:

• predicate_1 is somehow equivalent to Compare_dihedral_angle(t0,t1,t2,query,0) for the edge (t0,t1) of the triangle t0t1t2 but the border cases need to be handle (basically when the query point is a vertex or on an edge of the triangle). We would need to write a new dedicated predicate IMO.
• predicate_2 can actually be written as the evaluation of the sign of two scalar products. This means also writing a new predicate.

[lrineau]

@afabri @sloriot:

That pull-request is related to what we discussed today, and the work seems stalled (nothing changed since mi-February).

[sloriot]

The purpose of the PR was to have a function to also get the location of the closest point but there are some problems that I listed above. The only relationship with what we discussed today is the sphere construction that is a side problem in this PR.

[lrineau]

@sloriot Maybe this PR could be revived...

[sloriot]

There is nothing new, I wrote a pretty complete summary of the situation but got no reaction.

[lrineau]

Right. The important message is https://github.com/CGAL/cgal/pull/1887#issuecomment-277954928.