CGAL users discussion list

[Rostislav Khlebnikov <>]

I will try that. Thank you, Sebastien!


On 21/07/2014 13:19, Sebastien Loriot (GeometryFactory) wrote:
> On 07/21/2014 02:07 PM, Rostislav Khlebnikov wrote:
> > Hello Sebastien
> >
> > thanks for the quick answer.
> > Yes, I looked into the code and it is indeed computed as you said. The
> > thing is, I don't intersect triangles directly - I just found two
> > triangles with incorrect result to make a minimal example.
> > I use AABB tree to get a section of mesh with a triangle representing a
> > viewport. I could use a plane query, but it's quite a bit slower
> > especially when the mesh is not intersected by the viewport at all.
> > Perhaps you could suggest some modification to
> > Triangle_3_Triangle_3_intersection.h that would make it more robust in
> > these cases (perhaps sacrificing some of the performance for that -
> > something like line direction vector normalization? It's just not quite
> > clear for me what causes the problem and that's why I decided to ask for
> > some advice from people more involved in CGAL.
>
> I suggest to use a different traits class for the AABB-tree where
> the Intersect_3 do the filtered construction I proposed.
>
> Sebastien.
>
> > Rostislav.
> >
> > On 21/07/2014 12:48, Sebastien Loriot (GeometryFactory) wrote:
> > > IIRC, the intersection of the supporting planes if first computed and
> > > the line is then intersected with one of the triangles.
> > > In this setting, I'm not surprised you didn't get the correct result.
> > > You could use some filtered construction when the intersection would be
> > > computed with EPECK and then converter back to the kernel with inexact
> > > construction.
> > >
> > > Sebastien.
> > >
> > > On 07/21/2014 01:31 PM, Rostislav Khlebnikov wrote:
> > > > Hi Sebastien,
> > > >
> > > > yes, if I use the exact stuff it works fine. Again, it just seems
> > > > strange that double is "not good enough" - it's not like one of
> > > > triangles is 10 million times larger than the other or the 
> > > > intersection
> > > > is almost nil (it is a segment with coordinates {6.791 3.52889 
> > > > 27.5591},
> > > > {6.791 6.82325 45.9274}).
> > > >
> > > > Rostislav.
> > > >
> > > > On 21/07/2014 06:46, Sebastien Loriot (GeometryFactory) wrote:
> > > > > What if you are using
> > > > > CGAL::Exact_predicates_exact_constructions_kernel?
> > > > >
> > > > > See also:
> > > > > http://www.cgal.org/FAQ.html#inexact_NT
> > > > >
> > > > > Sebastien.
> > > > >
> > > > > On 07/20/2014 08:22 PM, Rostislav Khlebnikov wrote:
> > > > > > Hello guys,
> > > > > >
> > > > > > I'm having the intersection procedure not returning correct results
> > > > > > for
> > > > > > triangle-triangle intersection in 3D. I have compile a minimal 
> > > > > > example
> > > > > > that shows the problem:
> > > > > >
> > > > > > -----------------------------------------------------------------
> > > > > > #include <CGAL/Simple_cartesian.h>
> > > > > >
> > > > > > typedef CGAL::Simple_cartesian<double> K;
> > > > > > typedef K::FT FT;
> > > > > > typedef K::Point_3 Point;
> > > > > > typedef K::Triangle_3 Triangle;
> > > > > > typedef K::Segment_3 Segment;
> > > > > >
> > > > > >
> > > > > > void main()
> > > > > > {
> > > > > >      Triangle tri1 (Point(6.7910000000, -1.09375, -0.900025),
> > > > > > Point(6.791, 18.9, -0.9), Point(6.791, -1.09375, 144.321));
> > > > > >      Triangle tri1a(Point(6.7910000001, -1.09375, -0.900025),
> > > > > > Point(6.791, 18.9, -0.9), Point(6.791, -1.09375, 144.321));
> > > > > >
> > > > > >      Triangle tri2(Point(7.8, 5.6, 6.7269), Point(5.9, 1.7, 45.955),
> > > > > > Point(7.9, 13.2, 45.893));
> > > > > >
> > > > > >      std::cout << CGAL::intersection(tri1, tri2) << " " <<
> > > > > > CGAL::intersection(tri1a, tri2);
> > > > > > }
> > > > > > -----------------------------------------------------------------
> > > > > >
> > > > > > The output of this code is "0 1" which is quite strange. Do you
> > > > > > think it
> > > > > > is a bug for some special case or is it the floating-point problem?
> > > > > > The
> > > > > > thing is - I don't feel like the values are big or small enough for
> > > > > > "double" to be insufficient. Is there anything I can do to fix this
> > > > > > problem without changing to
> > > > > > Exact_predicates_exact_constructions_kernel?
> > > > > > I would really like to avoid this - I need performance over 
> > > > > > accuracy -
> > > > > > but I feel that in this case the accuracy is far off what one would
> > > > > > expect. I could even detect this special case and add 1e-8 or
> > > > > > whateve to
> > > > > > one of the points - it just feels weird and looks like a bug to me.
> > > > > >
> > > > > > CGAL installation info:
> > > > > > Windows 8.1, MSVS 2013, x64
> > > > > > CGAL 4.4 installed with the CGAL-4.4-Setup.exe installer and then
> > > > > > built
> > > > > > with CMake and MSVS 2013.
> > > > > >
> > > > > > All best,
> > > > > >    Rostislav.