CGAL users discussion list

["Laurent Rineau (CGAL/GeometryFactory)" <>]

Le jeudi 07 février 2013 15:31:03 Jeffrey Bush a écrit :
> Hi,
> 
> I am using AABB_tree to determine intersections between a plane (call it
> "h") and a polyhedron, resulting in a vector of segments ("segs"). However
> the following test fails:
> 
> h.has_on(*segs.begin())
> 
> 
> This shouldn't be. However doing research I realized the result may be
> because of using Cartesian instead of
> Exact_predicates_inexact_constructions_kernel, so I switched to that. But
> still the same problem!

With Exact_predicates_inexact_constructions_kernel, you can only construct an 
approximation of the intersection between your plane and your mesh. If after 
the computation you check that the computed approximation lie exactly on the 
plane, then that verification will fail in most cases.

> Running the debugger I get to this function:
> 
>   inline
>   Uncertain<Sign>
>   sign (const Interval_nt<Protected> & d)
>   {
>     if (d.inf() > 0.0) return POSITIVE;
>     if (d.sup() < 0.0) return NEGATIVE;
>     if (d.inf() == d.sup()) return ZERO;
>     return Uncertain<Sign>::indeterminate();
>   }
> 
> With the following value for d:
> 
> d = {
>   _inf=5.6843418860808015e-014,
>   _sup=5.6843418860808015e-014,
>   tester={...}
> }
> 
> It seems as though the d.inf() == d.sup() check should be first? It seems
> that if sup <= inf and inf > 0 or sup < 0, then the d.inf() == d.sup() can
> only be 0 == 0... (but I guess sup > inf - I don't understand exactly what
> this is all about).

In CGAL::Exact_predicates_inexact_constructions_kernel, all predicates have a 
filtering version, that compute an expression using an interval arithmetic 
(all values are computed twice, using first a rounding toward +infinity and 
then a rounding toward -infinity) and then tries to determine the sign of the 
expression using the computed interval. In that interval, by construction, 
sup()>=inf(). The sign of the expression is certified to be positive if 
inf()>0 and negative if sup()<0. In the very rare case when the interval is 
exactly the singleton [0,0], then the sign is certified to be zero. In all 
the 
other cases, the interval contains 0 and is not a singleton, and that means 
the sign of the expression cannot be determine using the interval.

That logic is exactly what is encoded in the function 
  sign(const Interval_nt<Protected>&)

-- 
Laurent Rineau, PhD
R&D Engineer at GeometryFactory           http://www.geometryfactory.com/
Release Manager of the CGAL Project       http://www.cgal.org/