CGAL users discussion list

[Andreas Fabri <>]

In fact, my "hint" that a plane is represented by a point  and a normal is wrong.

It is represented as an equation

https://github.com/CGAL/cgal/blob/master/Cartesian_kernel/include/CGAL/Cartesian/Plane_3.h#L43

and the construction from three points is here:

https://github.com/CGAL/cgal/blob/master/Cartesian_kernel/include/CGAL/constructions/kernel_ftC3.h#L223

Best,

Andreas

On 5/18/21 12:43 PM, Marc Alexa ( via cgal-discuss Mailing List) wrote:

      I did look into the code briefly and here’s something weird. The
      plane is constructed from the 3rd point in the constructor.

The following _expression_ did, in my experiments, consistently evaluate to true:

    std::cerr << "V2 on plane (pedestrian)? "<< ((p.a()*V2[0]+p.b()*V2[1]+p.c()*V2[2]+p.d()) == K::FT(0.0)) << std::endl;

While this one doesn’t:

   std::cerr << "V2 on plane (CGAL)? " << p.has_on(V2) << std::endl;

Interestingly, the CGAL code (after some indirections) is this:

template <class FT >

        CGAL_KERNEL_LARGE_INLINE
        typename Same_uncertainty_nt<Oriented_side,
            FT>::type
        side_of_oriented_planeC3(const
          FT &a,  const
          FT &b,  const
          FT &c, const
          FT &d,
                      
                    const
          FT &px, const
          FT &py, const
          FT &pz)
        {
          return
          CGAL_NTS sign(a*px + b*py + c*pz + d);
        }

where a,…,d are the plane parameters, and px, … are the coordinates of the point. 

Since this code is from a CGAL header, it is compiled by the same compiler with the same settings.

The only difference I can see, is that the plane parameters are of type K::RT in the documentation and also returned as such by the operators .a(),… whereas in the function the above they are K::FT. So apparently there is a difference between casting them along the way of the call vs. asking for the products (and invoking a cast this way)?

Best,

Marc

On 18. May 2021, at 11:51, Marc Alexa <> wrote:

Sure. If the coordinates have exact representations in binary float (and their products and the sum of the products can be represented in the available digits) then it probably works just as one would naively expect. There are also other cases that are more convenient for the internal representation.
If, as Andreas hinted, the internal representation of a plane was indeed a point and a normal, the ‘has_on’ test still had a good chance to evaluate to true consistently. Let X,N be the representation of the plane. Construction from V0,V1,V2 could be implemented as X = V0, N = (V1-V0)x(V2-V0). Then <V0,N>-<X,N> = <V0,N> - <V0,N> would evaluate to zero in most(?) floating point implementations.

But the internal implementation is not point plus normal. Rather it is normal plus offset. And apparently the offset is not just <V0,N> or else I would expect that V0 is evaluated to be on the plane, despite inexact representation in floating points (as per the argument above).

So there seems to be more going on in the construction. (Probably cannot hold myself back from looking into it now…)

Best,
Marc

On 18. May 2021, at 11:20, Michael Hoffmann <> wrote:

Hi Marc,

the coordinates of your points look nice in decimal, but they (e.g., 1.1, 0.3, 0.7) get pretty ugly once converted to binary…

Best, Michael

On 18 May 2021, at 11:16, Marc Alexa <> wrote:

Hi Andreas,

Thanks for the quick answer.

I think I just now fully understood the consequences of “inexact constructions”. It does lead to some interesting results, I have to say. I put a minimal program together that generates such a result, which is of course unsurprising in general, but still a bit surprising to me for the ‘exact predicates’ statement.

Best,
Marc

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/intersections.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_3 Point;
typedef K::Line_3 Line;
typedef K::Plane_3 Plane;
typedef K::Triangle_3 Triangle;

int main()
{
  Point V0(1.0,0.3,0.7);
  Point V1(0.3,1.1,0.2);
  Point V2(3.3,4.7,5.1);

  Plane p(V0,V1,V2);

  std::cerr << "V0 on plane? " << p.has_on(V0) << std::endl;
  std::cerr << "V1 on plane? " << p.has_on(V1) << std::endl;
  std::cerr << "V2 on plane? " << p.has_on(V2) << std::endl;

  Triangle t(V0,V1,V2);

  std::cerr << "Triangle intersects plane? " << CGAL::do_intersect(p,t) << std::endl;
  Line l(V0,V1);
  std::cerr << "V0 on line? " << l.has_on(V0) << std::endl;
  std::cerr << "V1 on line? " << l.has_on(V1) << std::endl;

  std::cerr << "Triangle intersects line? " << CGAL::do_intersect(l,t) << std::endl;
  std::cerr << "Plane intersects line? " << CGAL::do_intersect(l,p) << std::endl;
  return 0;
}

On 17. May 2021, at 20:53, Andreas Fabri <> wrote:

Hi Marc,

As the plane is internally a point and a normal  this is a construction.
So if the point is slightly off the plane of the triangle and the normal
happens to be correct the plane and the triangle plane  are parallel.

Even if one takes a vertex of the triangle as base for the plane
there is no guarantee that the intersection is  the full triangle.

andreas

On 5/17/21 7:07 PM, Marc Alexa ( via cgal-discuss Mailing List) wrote:

Dear all,
I’m a checking the intersection between Triangle_3 and Plane_3 objects. If both are constructed from the same triple of points, the result is false for most triples, but sometimes true. I’m using the exact predicates / inexact constructions kernel. Is this the expected / desired behavior? I had hope because of the exact predicates that the result for such intersection tests is at least consistent (and actually consistently true).

Thanks!
-Marc

--
You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss

--
You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss

--
You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss

        -- 
        You are currently subscribed to cgal-discuss.
        To unsubscribe or access the archives, go to
        https://sympa.inria.fr/sympa/info/cgal-discuss