Add a Bbox class with dimension as parameter #8258

afabri · 2024-06-05T09:10:41Z

Summary of Changes

For the upcoming Frechet Distance package we need a dD bounding box. We do not have that in Kernel_d, and there is such a class in ign's Distributed Delaunay Triangulation package to come (link). This PR copies it to the Kernel package (with the ok of @mbredif), but in the CGAL namespace.

This draft pull request is to get a discussion started.

In the initial version even the number type is a template parameter. Do we want to keep that?
Do we want to make Bbox_2/3 a typedef of this new class?
We have to go through the API and probably enrich it with what Bbox_2 offers additionally.
Do we have to add functions in Kernel_d?

TODO

Give feedback

create a small feature and get it approved
Options

Release Management

Affected package(s): Kernel_23
Feature/Small Feature (if any): tbd
Link to compiled documentation (obligatory for small feature) wrong link name to be changed
License and copyright ownership: LGPL , owned by IGN

afabri · 2024-06-12T14:19:33Z

@mglisse I am also wondering why there is no bounding box class in Epick_d etc. Apparently there is no need for it so far, but would you like to see it integrated? With functors etc.

mglisse · 2024-06-12T14:32:24Z

Kernel_23/include/CGAL/Bbox.h

+        CGAL_assertion(min_values.size() == 0 || min_values.size() == bbox.min_values.size());
+        int dim = bbox.min_values.size();
+        for(int i=0; i<dim; ++i)
+        {
+            if(min_values[i] > bbox.min_values[i]) min_values[i] = bbox.min_values[i];


The assertion allows min_values.size() == 0 and dim != 0, but then min_values[i] is read 😕

That's wrong indeed.
min_values.size()==0 happens for a default constructed Bbox with a dynamic dimension, which models an empty bbox. In this case, values should just be copied from bbox to this.

afabri · 2024-06-12T14:47:35Z

@mbredif do I have to make you collaborator, or is this already the case?

mglisse · 2024-06-12T15:09:16Z

@mglisse I am also wondering why there is no bounding box class in Epick_d etc.

I remember thinking about it, maybe discussing it, but I don't remember the content...

Apparently there is no need for it so far,

That may have played a big role 😉 (it doesn't seem to be part of the Kernel_d concept)

but would you like to see it integrated? With functors etc.

If you have a use for it, we probably should.
To be sure I understand: the current bbox_23 always use double, whatever the kernel, making them not really kernel objects. Is the plan the same for the new bbox, i.e. ignore the generality offered by the template parameter and only use it with double (otherwise it becomes Iso_rectangle_2/Iso_cuboid_3)?
It looks like the kernel integration can be done later in a separate PR (this one adds the class), which gives me a bit of time to think about how that fits with the design of NewKernel_d.

mglisse · 2024-06-12T15:15:33Z

Kernel_23/include/CGAL/Bbox.h

+        this->min_values.resize(d);
+        this->max_values.resize(d);


It seems a bit wasteful to use 2 containers of size d instead of one of size 2*d, but that's an implementation detail so it doesn't matter now.

afabri · 2024-06-20T12:18:24Z

Kernel_23/include/CGAL/Bbox.h

+{
+    int d = bbox.dimension();
+    for(int i=0; i<d; ++i)
+        out  << (bbox.min)(i) << "  " << (bbox.max)(i) << " ";


Bbox_2/3 first print lower left and then upper right.

Kernel_23/include/CGAL/Bbox.h

afabri · 2024-06-20T13:30:55Z

Kernel_23/include/CGAL/Bbox.h

+    enum { D = N };
+public:
+    inline constexpr int dimension() const { return D; }
+    Bbox(int d = 0          ) { assert(d==N || d==0); this->init(d       ); }


I find it surprising that for a Bbox with non-dynamic dimension I have to pass parameter d.

that was to offer a common API whatever the dimension dynamics

afabri · 2024-06-20T14:16:58Z

We also need a constructor taking an iterator range of coordinates. And maybe also for a range of pairs of coordinates.
The former is needed when constructing a bbox from a point with floating point coordinates. The latter when constructing
it from exact coordinates transformed to a std::pair<double,double> using CGAL::to_double().

I just realize that this would correspond more to what you do for the I/O operators. But do we want a constructor for a range of low and a second range for high? Seems not intuitive.

afabri · 2024-06-20T14:59:10Z

As Epick_d may have a dynamic and a static dimension, depending on a template parameter, the functor Epick_d::Construct_bbox_d() must return either a bbox type with dynamic and static dimension, respectively.

sloriot · 2024-07-09T13:35:30Z

Kernel_23 failing in CGAL-6.0-Ic-284

sloriot · 2024-07-25T08:31:51Z

Kernel_23 tests are failing in CGAL-6.0-Ic-295.
See for example here and there.

sloriot · 2024-08-19T14:39:36Z

NewKernel_d/include/CGAL/NewKernel_d/function_objects_cartesian.h

+};
+}
+
+CGAL_KD_DEFAULT_FUNCTOR(Construct_bbox_tag,(CartesianDKernelFunctors::Construct_bbox<K>),(Point_tag),(Construct_ttag<Point_cartesian_const_iterator_tag>));


@mglisse do you have any doc for the macro CGAL_KD_DEFAULT_FUNCTOR. I'm pretty sure this line is incorrect but I don't know how to fix it.

The line looks ok to me. You have the tag, the class, the required objects, the required other functors, that's it. Ah, maybe you are missing Point_dimension_tag in the last list (I am not sure this list is really used currently).

afabri · 2024-08-19T15:17:43Z

I am wondering if it is not just something missing in Lazy_cartesian.h as I now got it working for Epick_d.

mglisse · 2024-08-21T20:32:26Z

NewKernel_d/include/CGAL/NewKernel_d/functor_tags.h

@@ -201,6 +201,7 @@ namespace CGAL {
        CGAL_DECL_COMPUTE(Squared_distance);
        CGAL_DECL_COMPUTE(Squared_distance_to_origin);
        CGAL_DECL_COMPUTE(Squared_length);
+        CGAL_DECL_COMPUTE(Construct_bbox);


I think it makes more sense as CGAL_DECL_MISC. "Compute" is for things that return a Lazy_exact_nt in Epeck_d.
And then Lazy_cartesian needs something similar to Point_dimension_tag, assuming that the Bbox is supposed to be built from the approximate object (maybe merge the cases Point_dimension_tag, Vector_dimension_tag, and this new one in a partial specialization struct Functor<T,D,Misc_tag>?)

mglisse · 2024-08-21T20:41:51Z

NewKernel_d/include/CGAL/NewKernel_d/function_objects_cartesian.h

+};
+}
+
+CGAL_KD_DEFAULT_FUNCTOR(Construct_bbox_tag,(CartesianDKernelFunctors::Construct_bbox<K>),(Point_tag),(Construct_ttag<Point_cartesian_const_iterator_tag>));


The line looks ok to me. You have the tag, the class, the required objects, the required other functors, that's it. Ah, maybe you are missing Point_dimension_tag in the last list (I am not sure this list is really used currently).

mglisse · 2024-08-21T20:50:51Z

NewKernel_d/include/CGAL/NewKernel_d/function_objects_cartesian.h

+
+        typedef Bbox<Dimension,double> result_type;
+        typedef Point argument_type;
+        result_type operator()(Point const&a)const{


Out of curiosity, is it likely to stick to just this function, or do you expect to add overloads for Segment, Sphere, Iso_box, etc? I am asking because ideally (I stopped before making things consistent), overload resolution should happen in Kernel_d_interface, and dispatch to different non-overloaded functors like Bbox_from_point, Bbox_from_segment.

It would be natural to generalize. We started this only for the Frechet Distance submission, where we only deal with points.

mglisse · 2024-08-21T20:59:22Z

In fact there is the nested type Dimension

Yes, that's also what we use in Gudhi to access the compile-time dimension of a CGAL Kernel. It is even documented in the Kernel_d concept 🍀 .

afabri · 2024-08-22T07:25:20Z

@sloriot and I, we are blocked with getting Epick_d.cpp compiled. There is probably a specialization we have to add, but we have no idea what exactly,

mglisse · 2024-08-22T08:37:11Z

NewKernel_d/include/CGAL/NewKernel_d/functor_tags.h

@@ -260,6 +260,7 @@ namespace CGAL {
        CGAL_DECL_CONSTRUCT(Construct_circumcenter,Point);
        CGAL_DECL_CONSTRUCT(Point_drop_weight,Point);
        CGAL_DECL_CONSTRUCT(Power_center,Weighted_point);
+        CGAL_DECL_CONSTRUCT(Construct_bbox,Bbox);


I suggested MISC though, since this doesn't return a Lazy object in Epeck_d.

mglisse · 2024-08-22T08:43:30Z

@sloriot and I, we are blocked with getting Epick_d.cpp compiled. There is probably a specialization we have to add, but we have no idea what exactly,

I mentioned looking at Point_dimension_tag in Lazy_cartesian.h. Something like

--- a/NewKernel_d/include/CGAL/NewKernel_d/Lazy_cartesian.h
+++ b/NewKernel_d/include/CGAL/NewKernel_d/Lazy_cartesian.h
@@ -309,24 +309,15 @@ struct Lazy_cartesian :
     template<class T,class D> struct Functor<T,D,Construct_tag> {
             typedef Lazy_construction2<T,Kernel> type;
     };
-    template<class D> struct Functor<Point_dimension_tag,D,Misc_tag> {
-            typedef typename Get_functor<Approximate_kernel, Point_dimension_tag>::type FA;
-            struct type {
-              FA fa;
-              type(){}
-              type(Kernel const&k):fa(k.approximate_kernel()){}
-              template<class P>
-              int operator()(P const&p)const{return fa(CGAL::approx(p));}
-            };
-    };
-    template<class D> struct Functor<Vector_dimension_tag,D,Misc_tag> {
-            typedef typename Get_functor<Approximate_kernel, Vector_dimension_tag>::type FA;
+    template<class T,class D> struct Functor<T,D,Misc_tag> {
+            // By default (Point_dimension, Construct_bbox), apply to the approximate object
+            typedef typename Get_functor<Approximate_kernel, T>::type FA;
             struct type {
               FA fa;
               type(){}
               type(Kernel const&k):fa(k.approximate_kernel()){}
-              template<class V>
-              int operator()(V const&v)const{return fa(CGAL::approx(v));}
+              template<class P...>
+              decltype(auto) operator()(P&&...p)const{return fa(CGAL::approx(std::forward<P>(p))...);}
             };
     };
     template<class D> struct Functor<Linear_base_tag,D,Misc_tag> {

(completely untested)
If that still doesn't work, I'll checkout the branch to experiment, but not right now.

sloriot · 2024-08-22T08:54:22Z

@mglisse in the meantime I achieved to make it compile and run. Not sure if that's the right way to do it.

mglisse · 2024-08-22T10:33:58Z

@mglisse in the meantime I achieved to make it compile and run. Not sure if that's the right way to do it.

See https://github.com/mglisse/cgal/tree/Kernel_23-Bbox_d-ign, where I added commit mglisse@316ab90 .

sloriot · 2024-08-22T11:32:58Z

@mglisse in the meantime I achieved to make it compile and run. Not sure if that's the right way to do it.

See https://github.com/mglisse/cgal/tree/Kernel_23-Bbox_d-ign, where I added commit mglisse@316ab90 .

That's indeed much simpler. I did not see that MISC macro. Thanks!

sloriot · 2024-10-14T07:35:41Z

Successfully tested in CGAL-6.0.1-Ic-345

sloriot · 2024-10-14T07:35:51Z

Still a draft and small feature missing.

Kernel: Add a BBox class with dimension as parameter

ec56c66

lrineau changed the title ~~Kernel: Add a Bbox class with dimension as parameter~~ Kernel_23d: Add a Bbox class with dimension as parameter Jun 10, 2024

mglisse reviewed Jun 12, 2024

View reviewed changes

Fix +=; Add first tests

6638dec

afabri commented Jun 20, 2024

View reviewed changes

Kernel_23/include/CGAL/Bbox.h Outdated Show resolved Hide resolved

afabri commented Jun 20, 2024

View reviewed changes

afabri added 2 commits June 20, 2024 14:49

typo in Epick_d doc

cf6996b

typo in Epick_d doc

48d734c

Constructor from a range of pairs of numbers

4bc2770

sloriot added Under Testing Tests failing and removed Under Testing labels Jul 8, 2024

Add missing parameter; (std::min)

8ef1f72

sloriot added Under Testing and removed Tests failing labels Jul 23, 2024

sloriot added Tests failing and removed Under Testing labels Jul 25, 2024

MaelRL added Pkg::Kernel_23 Pkg::Kernel_d labels Aug 12, 2024

MaelRL changed the title ~~Kernel_23d: Add a Bbox class with dimension as parameter~~ Add a Bbox class with dimension as parameter Aug 12, 2024

Protect min/max for VC++

570433d

afabri and others added 3 commits August 19, 2024 13:27

Add top down

63dd907

use consistent naming

d2b1ea7

WIP: apply the functor

6650de8

sloriot reviewed Aug 19, 2024

View reviewed changes

got it working for Epick and #if 0 the block with Epeck as WIP

6d11389

mglisse reviewed Aug 21, 2024

View reviewed changes

functor is a construction and not a computation

7133b28

mglisse reviewed Aug 22, 2024

View reviewed changes

make it compile

7ab31a8

Clean up

316ab90

afabri added Ready to be tested and removed Tests failing labels Aug 22, 2024

Merge remote-tracking branch 'cgal/master' into Kernel_23-Bbox_d-ign

ab06574

sloriot added the Under Testing label Sep 16, 2024

CGAL_USE()

769906a

sloriot added this to the 6.1-beta milestone Oct 10, 2024

sloriot added Tested and removed Under Testing labels Oct 14, 2024

lrineau added Not yet approved The feature or pull-request has not yet been approved. TODO labels Oct 14, 2024

lrineau assigned afabri Oct 22, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add a Bbox class with dimension as parameter #8258

Add a Bbox class with dimension as parameter #8258

afabri commented Jun 5, 2024 •

edited by lrineau

Loading

TODO

afabri commented Jun 12, 2024

mglisse Jun 12, 2024

mbredif Jun 12, 2024

afabri commented Jun 12, 2024

mglisse commented Jun 12, 2024

mglisse Jun 12, 2024

afabri Jun 20, 2024

afabri Jun 20, 2024

mbredif Jun 20, 2024

afabri commented Jun 20, 2024 •

edited

Loading

afabri commented Jun 20, 2024

sloriot commented Jul 9, 2024

sloriot commented Jul 25, 2024 •

edited

Loading

sloriot Aug 19, 2024

mglisse Aug 21, 2024

afabri commented Aug 19, 2024

mglisse Aug 21, 2024

mglisse Aug 21, 2024

mglisse Aug 21, 2024

afabri Aug 22, 2024

mglisse commented Aug 21, 2024

afabri commented Aug 22, 2024

mglisse Aug 22, 2024

mglisse commented Aug 22, 2024 •

edited

Loading

sloriot commented Aug 22, 2024 •

edited

Loading

mglisse commented Aug 22, 2024

sloriot commented Aug 22, 2024

sloriot commented Oct 14, 2024

sloriot commented Oct 14, 2024

Add a Bbox class with dimension as parameter #8258

Are you sure you want to change the base?

Add a Bbox class with dimension as parameter #8258

Conversation

afabri commented Jun 5, 2024 • edited by lrineau Loading

Summary of Changes

TODO

Release Management

afabri commented Jun 12, 2024

Choose a reason for hiding this comment

Choose a reason for hiding this comment

afabri commented Jun 12, 2024

mglisse commented Jun 12, 2024

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

afabri commented Jun 20, 2024 • edited Loading

afabri commented Jun 20, 2024

sloriot commented Jul 9, 2024

sloriot commented Jul 25, 2024 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

afabri commented Aug 19, 2024

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

mglisse commented Aug 21, 2024

afabri commented Aug 22, 2024

Choose a reason for hiding this comment

mglisse commented Aug 22, 2024 • edited Loading

sloriot commented Aug 22, 2024 • edited Loading

mglisse commented Aug 22, 2024

sloriot commented Aug 22, 2024

sloriot commented Oct 14, 2024

sloriot commented Oct 14, 2024

afabri commented Jun 5, 2024 •

edited by lrineau

Loading

afabri commented Jun 20, 2024 •

edited

Loading

sloriot commented Jul 25, 2024 •

edited

Loading

mglisse commented Aug 22, 2024 •

edited

Loading

sloriot commented Aug 22, 2024 •

edited

Loading