CGAL users discussion list

[Camille Wormser <>]

> Yes, that's right, but I started to narrow down the problem from the  
> AABB tree and according to their performance tests runs the  
> Simple_cartesian<double> 2.5 times faster then the  
> CGAL::Exact_predicates_inexact_constructions_kernel.
>
> So I was wondering, whether one could circumvent this problem for  
> former kernel typ by a slight change in the implementation.

Hi Andre,
The problem is the following: it will always be possible to construct  
cases where the Simple_cartesian<double> kernel fails. That's exactly  
the reason why Exact_predicates kernels have been created.

See the following paper for an introduction to these issues:

@article{kettner2008classroom,
  title={{Classroom examples of robustness problems in geometric  
computations}},
  author={Kettner, L. and Mehlhorn, K. and Pion, S. and Schirra, S.  
and Yap, C.},
  journal={Computational Geometry: Theory and Applications},
  volume={40},
  number={1},
  pages={61--78},
  year={2008},
  publisher={Elsevier}
}

We are working on your example of triangle-bbox intersection, because  
in that particular case, where the final intersection point is in fact  
an input point (in fact, it is a shared vertex of two input  
triangles), it is reasonnable to expect even the  
Simple_cartesian<double> kernel to detect it correctly. This is a very  
specific case, where tweaking the numerical code could make a  
difference, and allow the users to trade robustness for efficiency (at  
their own risk!) with the code failing less often.

On the other hand, in the new case you are presenting, you are in  
front of a very generic robustness issue, for which there is no other  
solution than using an Exact_predicates kernel. In other words,  
tweaking the computations may help detecting this particular  
degenerate case, but would create new failures for other such cases.

For this reason, we are working on improving the triangle-bbox test  
(and hopefully other similar ones) so that using an inexact kernel  
does not make them fail in the kind of special cases you presented  
(previous thread), but we will not work on this new issue you are  
presenting: this kind of problem is expected, and inherent to  
geometric computations.

Best,
--
Camille