CGAL users discussion list

[Andre Massing <>]

Dear all,

since we started to use CGAL in our mesh library part of our DOLFIN fem
library, I came across with another missing intersection detection, this
time in case of a Triangle_3 Tetrahedron_3 intersection, concerning the
Triangle_3_Tetrahedron_3_do_intersect.h file.

The following attached file illustrates the problem. Running the program 
throws an exception (I added also some debug code):

<debug code>------------------------------
Triangle points:
Point 1: 0.6666666666666666 0.6666666666666666 0.5
lies on bounded side of tet: -1
Point 2: 1 0.6666666666666666 0.5
lies on bounded side of tet: -1
Point 3: 1 1 1
lies on bounded side of tet: 0
Tetraeder points:
Point 1: 0.9037749551350623 0.9037749551350623 0.9037749551350623
Point 2: 1.096225044864938 0.9037749551350623 0.9037749551350623
Point 3: 1.096225044864938 0.9037749551350623 1.096225044864938
Point 4: 1.096225044864938 1.096225044864938 1.096225044864938
</debug code>---------------------------------
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

[andre-laptop:17840] *** Process received signal ***
[andre-laptop:17840] Signal: Aborted (6)
[andre-laptop:17840] Signal code:  (-6)
[andre-laptop:17840] [ 0] /lib/libpthread.so.0 [0x7f3fa4957190]
[andre-laptop:17840] [ 1] /lib/libc.so.6(gsignal+0x35) [0x7f3fa460c4b5]
[andre-laptop:17840] [ 2] /lib/libc.so.6(abort+0x180) [0x7f3fa460ff50]
[andre-laptop:17840] [ 3] 
/usr/lib/libstdc++.so.6(_ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x115) 
[0x7f3fa50c7cc5]
[andre-laptop:17840] [ 4] /usr/lib/libstdc++.so.6 [0x7f3fa50c60f6]
[andre-laptop:17840] [ 5] /usr/lib/libstdc++.so.6 [0x7f3fa50c6123]
[andre-laptop:17840] [ 6] /usr/lib/libstdc++.so.6 [0x7f3fa50c621e]
[andre-laptop:17840] [ 7] 
/home/andre/local/lib/libCGAL.so.4(_ZN4CGAL14assertion_failEPKcS1_iS1_+0x1fa) 
[0x7f3fac74a52a]
[andre-laptop:17840] [ 8] 
./failed_tetrahedron_triangle_intersection(_ZN4CGAL5CGALi12do_intersectINS_16Simple_cartesianIdEEEENT_7BooleanERKNS4_10Triangle_3ERKNS4_13Tetrahedron_3ERKS4_+0xc9a) 
[0x405f2a]
[andre-laptop:17840] [ 9] 
./failed_tetrahedron_triangle_intersection(main+0x166) [0x4027b6]
[andre-laptop:17840] [10] /lib/libc.so.6(__libc_start_main+0xfd) 
[0x7f3fa45f7abd]
[andre-laptop:17840] [11] ./failed_tetrahedron_triangle_intersection 
[0x402339]
[andre-laptop:17840] *** End of error message ***
Aborted (core dumped)

I had a look a the source code of Triangle_3_Tetrahedron_3_do_intersect.h
and the following question arises:

As the debug code indicates, Point 1 and 2 are detected *outside* the 
tetrahedron but Point 3 merely *on the boundary*. Therefore we get an 
exception because  the previous checks in 
Triangle_3_Tetrahedron_3_do_intersect.h  via the do_intersect function 
of Triangle_3_Triangle_3_do_intersect.h failed to detect the intersection.
Would it therefore not be better to check first whether the points of 
the triangle lie completely on one domain of the tetrahedron (via for 
example the has_on_bounded_side(Point_3<Kernel> p) member method and if 
not, use this to already detect the intersection, instead of throwing an 
exception after a wrongly not detected Triangle_3-Triangel_3 
intersection? At least I used such a approach in a similiar Tetrahedron 
Tetrahedron detection function.
But please tell me, if I got something conceptually wrong, I am just a 
computational geometry freeloader :)

Greetings,
Andre Massing






#include <CGAL/Bbox_3.h>
#include <CGAL/Simple_cartesian.h> 

#include <iostream>

typedef CGAL::Simple_cartesian<double> 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.9037749551350623, 0.9037749551350623, 0.9037749551350623);
  Point_3 B(1.096225044864938, 0.9037749551350623, 0.9037749551350623);
  Point_3 C(1.096225044864938, 0.9037749551350623,1.096225044864938);
  Point_3 D(1.096225044864938, 1.096225044864938, 1.096225044864938);

  Point_3 a(0.6666666666666666,0.6666666666666666,0.5);
  Point_3 b(1,0.6666666666666666,0.5);
  Point_3 c(1.0,1.0,1.0);

  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;
}