CGAL users discussion list

[Andre Massing <>]

Hi again,

sorry for bothering again the cgal-ml, but this time I came up with a 
rather simple example, where the Simple_cartesian<double> kernel and 
Triangle_3_Tetrahedron_3_do_intersect.h might not work "properly". This 
time the intersection is a vertex point of both the triangle and the 
tetrahedron and gives again the exception (with debug code):

Triangle points:
Point 1: 0.2 0 0
lies on bounded side of tet: -1
Point 2: 0.2 0.1 0
lies on bounded side of tet: -1
Point 3: 0.3 0.1 0.1
lies on bounded side of tet: 0
Tetraeder points:
Point 1: 0.3 0 0
Point 2: 0.3 0 0.1
Point 3: 0.3 0.1 0.1
Point 4: 0.4 0.1 0.1
terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: k.bounded_side_3_object()(tet, tr[0]) == 
k.bounded_side_3_object()(tet, tr[2])
File: /home/andre/local/include/CGAL/Triangle_3_Tetrahedron_3_do_intersect.h
Line: 80


Therefore I like to reask, why the k.bounded_side_3_object()(,) is in 
fact not used for detecting these kinds of intersection?
I've already encountered many cases where the triangle and the 
tetrahedron intersect only on the boundary of the tetrahedron, which was 
*not* detected by the Triangle_3 - Triangle_3 intersection test, *but* 
could have been detected by comparing the k.bounded_side_3_object() results.
I understand that predicates of that kernel can not always compute the 
right result, but why are the k.bounded_side_3_object() results not 
taken into consideration while trying to detect the intesection?

Kind regards,
Andre


Andre Massing wrote:
> Hi Camille,   
>
> thanks for the detailed answer and the pointer to the paper!
>
> Camille Wormser wrote:
> > > 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.
>
> O.k. I formulated my question rather clumsy :), of course I don't expect 
> the detection to be watertight for arbitrary cases.
> So let me reformulate my question:
> One has a *possible* intersection, which could have been detected by
> comparing the results of the k.bounded_side_3_object()(,) function,
> but was not detected  by the triangle triangle intersection test. Both 
> functions can not give a correct detection for all cases using the 
> simple kernel. So is the triangle triangle intersection test in a 
> certain case more reliable than the point tetrahedron intersection 
> detection, that is advisable to throw an exception, if the mentioned 
> situation occurs? Or what is the criterion to choose the one method to 
> be superior to the other?
>
> > 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}
> > }
>
> Thanks, printed out and I will have a detailed look at it!
>
> > 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.
>
> Ah, ok, thanks for explanation. Is the reasoning also somehow related to 
> the way the detection is dealt with in the above case?
>
> > 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.
>
> Oh, good, that is why I asked, since I have unfortunately no clue which 
> kind of cases (and how they are) well balanced out in the code.
>
> > 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), 
>
> Great that you are looking at it!
>
> but we will not work on this new issue you are presenting: this
> > kind of problem is expected, and inherent to geometric computations.
>
> Kind regards,
> Andre
#include <CGAL/Bbox_3.h>
//#include <CGAL/Simple_cartesian.h> 

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

#include <iostream>

typedef CGAL::Simple_cartesian<double> K;
//typedef CGAL::Exact_predicates_inexact_constructions_kernel K;

typedef K::Point_3 Point_3;
typedef K::Segment_3 Segment_3;
typedef K::Triangle_3 Triangle_3;
typedef K::Tetrahedron_3 Tetrahedron_3;
typedef K::Iso_cuboid_3 Iso_cuboid_3;
typedef K::Ray_3 Ray_3;
typedef K::Line_3 Line_3;

typedef CGAL::Bbox_3 Bbox_3;

using std::cout;
using std::endl;

int main()
{
  Point_3 A(0.3,0.0,0.0);
  Point_3 B(0.3,0.0,0.1);
  Point_3 C(0.3,0.1,0.1);
  Point_3 D(0.4,0.1,0.1);

  Point_3 a(0.2,0.0,0.0);
  Point_3 b(0.2,0.1,0.0);
  Point_3 c(0.3,0.1,0.1);

  Triangle_3 tri_1(a,b,c);
  Tetrahedron_3 tet_2(A,B,C,D);

  if (CGAL::do_intersect(tet_2,tri_1))
      cout <<"Intersection of Tetraeder  with face triangle" << endl;
  else 
      cout <<"NO Intersection." << endl;

  return 0;
}