Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Epick_d and Has_filtered_predicates_tag #8256

Open
afabri opened this issue Jun 5, 2024 · 12 comments · May be fixed by #8284
Open

Epick_d and Has_filtered_predicates_tag #8256

afabri opened this issue Jun 5, 2024 · 12 comments · May be fixed by #8284
Assignees

Comments

@afabri
Copy link
Member

afabri commented Jun 5, 2024

Issue Details

The upcoming Frechet distance package works in any dimension. Here we want to obtain K::Has_filtered_predicates_tag::value for the kernel, and we then want to access K::Exact_kernel.
@mglisse Can this be added to Epick_d without breaking its design?

@mglisse
Copy link
Member

mglisse commented Jun 5, 2024

We can probably do something, but can you explain what you are trying to achieve there (otherwise I may answer the wrong question)?
I see that you mostly ignore the input kernel and do some computations always with intervals, and keep a way to extract vertices as rational points, but that doesn't really give me a high level image of the goal and strategy.

@afabri
Copy link
Member Author

afabri commented Jun 5, 2024

The input points are transformed in points with interval arithmetic. In case of an uncertain exception we create a Sqrt_extension where we want to use the Exact_kernel::FT if available.
The table here shows also in which case we make a copy of the input.

@lrineau
Copy link
Member

lrineau commented Jun 12, 2024

@mglisse

Would the following patch be acceptable?

diff --git a/NewKernel_d/include/CGAL/NewKernel_d/Cartesian_filter_K.h b/NewKernel_d/include/CGAL/NewKernel_d/Cartesian_filter_K.h
index ef44403f9f5..bc7d88deefa 100644
--- a/NewKernel_d/include/CGAL/NewKernel_d/Cartesian_filter_K.h
+++ b/NewKernel_d/include/CGAL/NewKernel_d/Cartesian_filter_K.h
@@ -58,11 +58,15 @@ struct Cartesian_filter_K : public Base_
     typedef Base_ Kernel_base;
     typedef AK_ AK;
     typedef EK_ EK;
+    typedef EK Exact_kernel;
     typedef typename Store_kernel<AK_>::reference_type AK_rt;
     AK_rt approximate_kernel()const{return sak.kernel();}
     typedef typename Store_kernel<EK_>::reference_type EK_rt;
     EK_rt exact_kernel()const{return sek.kernel();}
 
+    enum { Has_filtered_predicates = true };
+    typedef Boolean_tag<Has_filtered_predicates> Has_filtered_predicates_tag;
+
     // MSVC is too dumb to perform the empty base optimization.
     typedef std::bool_constant<
       internal::Do_not_store_kernel<Kernel_base>::value &&

@lrineau
Copy link
Member

lrineau commented Jun 12, 2024

Plus the following:

diff --git a/NewKernel_d/test/NewKernel_d/Epick_d.cpp b/NewKernel_d/test/NewKernel_d/Epick_d.cpp
index 5693977869a..61fed477750 100644
--- a/NewKernel_d/test/NewKernel_d/Epick_d.cpp
+++ b/NewKernel_d/test/NewKernel_d/Epick_d.cpp
@@ -751,6 +751,9 @@ int main(){
   test2<Ker2>(); test2i<Ker2>();
   test3<Ker3>();
   test3<Kerd>();
+  static_assert(Ker2::Has_filtered_predicates_tag::value);
+  static_assert(Ker3::Has_filtered_predicates_tag::value);
+  static_assert(Kerd::Has_filtered_predicates_tag::value);

@mglisse
Copy link
Member

mglisse commented Jun 12, 2024

Would the following patch be acceptable?

Yes, but

  • can you put the 3 lines together with a comment saying that they are here for the sake of package XYZ? (so it doesn't look like unused cruft in need of cleanup)
  • should we have a corresponding "false" enum/typedef somewhere like Cartesian_base_d?
  • is that really sufficient?

The explanation was not super clear, it sounds vaguely like a Lazy_exact_nt<Sqrt_extension<Rat>> with a custom functor, but since I don't have a clear picture of what you are doing and why (is it the old idea that having 0 guarantee for the constructions in Epick is not good enough?), I can't comment.

@afabri
Copy link
Member Author

afabri commented Jun 12, 2024

I won't make a dedicated pull request, but it will go in PR #8284

@afabri afabri linked a pull request Jun 12, 2024 that will close this issue
1 task
@lrineau
Copy link
Member

lrineau commented Jun 12, 2024

Would the following patch be acceptable?

Yes, but

  • can you put the 3 lines together with a comment saying that they are here for the sake of package XYZ? (so it doesn't look like unused cruft in need of cleanup)

Right. We will do that.

But... to be honest, I have not the impression that the patch will decrease the readability of the code! 😃

// FIXME:
// - Uses_no_arithmetic predicates should not be filtered
// - Functors_without_division should be defined near/in the actual functors
template < typename Base_, typename AK_, typename EK_, typename Pred_list = typeset_all >
struct Cartesian_filter_K : public Base_
{
CGAL_NO_UNIQUE_ADDRESS Store_kernel<AK_> sak;
CGAL_NO_UNIQUE_ADDRESS Store_kernel<EK_> sek;
constexpr Cartesian_filter_K(){}
constexpr Cartesian_filter_K(int d):Base_(d){}
//FIXME: or do we want an instance of AK and EK belonging to this kernel,
//instead of a reference to external ones?
constexpr Cartesian_filter_K(AK_ const&a,EK_ const&b):Base_(),sak(a),sek(b){}
constexpr Cartesian_filter_K(int d,AK_ const&a,EK_ const&b):Base_(d),sak(a),sek(b){}
typedef Base_ Kernel_base;
typedef AK_ AK;
typedef EK_ EK;
typedef typename Store_kernel<AK_>::reference_type AK_rt;
AK_rt approximate_kernel()const{return sak.kernel();}
typedef typename Store_kernel<EK_>::reference_type EK_rt;
EK_rt exact_kernel()const{return sek.kernel();}
// MSVC is too dumb to perform the empty base optimization.
typedef std::bool_constant<
internal::Do_not_store_kernel<Kernel_base>::value &&
internal::Do_not_store_kernel<AK>::value &&
internal::Do_not_store_kernel<EK>::value > Do_not_store_kernel;
//TODO: C2A/C2E could be able to convert *this into this->kernel() or this->kernel2().
typedef KernelD_converter<Kernel_base,AK> C2A;
typedef KernelD_converter<Kernel_base,EK> C2E;
// fix the types
// TODO: only fix some types, based on some criterion?
template<class T> struct Type : Get_type<Kernel_base,T> {};
template<class T,class D,bool=Uses_no_arithmetic<typename Get_functor<Kernel_base,T,D>::type>::value> struct Pred_helper {
typedef typename Get_functor<AK, T>::type AP;
typedef typename Get_functor<EK, T>::type EP;
typedef Filtered_predicate2<Cartesian_filter_K,EP,AP,C2E,C2A> type;
};
// Less_cartesian_coordinate doesn't usually need filtering
// This fixes the predicate, as opposed to Inherit_functor which would leave it open (is that good?)
template<class T,class D> struct Pred_helper<T,D,true> :
Get_functor<Kernel_base,T,D> {};
template<class T,class D=void,class=typename Get_functor_category<Cartesian_filter_K,T>::type, bool=Pred_list::template contains<T>::value> struct Functor :
Inherit_functor<Kernel_base,T,D> {};
template<class T,class D> struct Functor<T,D,Predicate_tag,true> :
Pred_helper<T,D> {};
// TODO:
// template<class T> struct Functor<T,No_filter_tag,Predicate_tag> :
// Kernel_base::template Functor<T,No_filter_tag> {};
};

In my editor (VS Code), the TODO and FIXME are highlighted, there are.. a lot!

(click to see more...)

... and there are also several typedefs that are unused, and could now be replaced by decltype(auto), for example. See the screenshot:

Screenshot_20240612_163432

  • should we have a corresponding "false" enum/typedef somewhere like Cartesian_base_d?

Yes, probably. I will review Andreas's patch, once it is done.

  • is that really sufficient?

I am not completely sure. Andreas will test in #8284.

The explanation was not super clear, it sounds vaguely like a Lazy_exact_nt<Sqrt_extension<Rat>> with a custom functor, but since I don't have a clear picture of what you are doing and why (is it the old idea that having 0 guarantee for the constructions in Epick is not good enough?), I can't comment.

That is probably to construct kind of "filtered constructions", where the constructed objects are sometimes reconstructed using an exact kernel, if needed. I do not know the details.

See this example of a valid usage:

template < class K, bool UseFilteredPredicates=K::Has_filtered_predicates >
class Skin_surface_traits_3
: public Skin_surface_traits_base_3<K>
{
typedef Skin_surface_traits_base_3<K> Base;
public:
Skin_surface_traits_3() {}
Skin_surface_traits_3(typename Base::FT s) : Base(s) {}
enum { Has_filtered_predicates=false };
};
} //namespace CGAL
// Now specialize for Filtered_kernel<CK>, to get
// the filtered traits automatically.
#include <CGAL/Skin_surface_filtered_traits_3.h>
#include <CGAL/Filtered_kernel.h>
namespace CGAL {
// Just FK would be nicer, but VC 2005 messes it up with an "FK" in a base class when compiling degenerate_test.cpp
template < typename Sst3FK >
class Skin_surface_traits_3 < Sst3FK, true >
: public Skin_surface_filtered_traits_3 < Sst3FK >
{
typedef Skin_surface_filtered_traits_3 < Sst3FK > Base;
public:
typedef Sst3FK Kernel;
Skin_surface_traits_3() {}
Skin_surface_traits_3(typename Base::FT s) : Base(s) { }
};

@mglisse
Copy link
Member

mglisse commented Jun 12, 2024

But... to be honest, I have not the impression that the patch will decrease the readability of the code! 😃

If we want the probability of a cleanup to be non-zero, we should

  • avoid adding more things to clean up
  • mark clearly the things that should not be cleaned up (this was my point here)

(I completely agree the code is not pretty)

In my editor (VS Code), the TODO and FIXME are highlighted, there are.. a lot!

Comments (whether they are marked TODO/FIXME or not) are a completely different thing. They usually contain important information. And yes, there are a lot of things that I never did because they were not priorities.

That is probably to construct kind of "filtered constructions", where the constructed objects are sometimes reconstructed using an exact kernel, if needed. I do not know the details.

I had an Epack_d branch (it should still exist) to do filtered constructions in dD, but it didn't offer the option for each functor to use a different exact type (rational, sqrt-extension, etc).

See this example of a valid usage:

It looks like it would have been much simpler to add Side_of_mixed_cell_3 to the kernel.

@afabri
Copy link
Member Author

afabri commented Jun 14, 2024

In fact I also need a function object for constructing the filtered type and the exact type, In Epick this are the classes C2F and C2E.

@lrineau
Copy link
Member

lrineau commented Jun 14, 2024

But... to be honest, I have not the impression that the patch will decrease the readability of the code! 😃

If we want the probability of a cleanup to be non-zero, we should

  • avoid adding more things to clean up
  • mark clearly the things that should not be cleaned up (this was my point here)

You are right. And the comments are indeed very important for that (both TODO/FIXME and notes about why something has been added).

That is probably to construct kind of "filtered constructions", where the constructed objects are sometimes reconstructed using an exact kernel, if needed. I do not know the details.

I had an Epack_d branch (it should still exist) to do filtered constructions in dD, but it didn't offer the option for each functor to use a different exact type (rational, sqrt-extension, etc).

I was not able to retrieve the branch? Do you still have it? What is its name?

@mglisse
Copy link
Member

mglisse commented Jun 14, 2024

I had an Epack_d branch (it should still exist) to do filtered constructions in dD, but it didn't offer the option for each functor to use a different exact type (rational, sqrt-extension, etc).

I was not able to retrieve the branch? Do you still have it? What is its name?

https://github.com/mglisse/cgal/tree/NewKernel_d-Epack-glisse

afabri added a commit to anusser/cgal that referenced this issue Jun 14, 2024
@mglisse
Copy link
Member

mglisse commented Jun 14, 2024

In fact I also need a function object for constructing the filtered type and the exact type, In Epick this are the classes C2F and C2E.

There are typedefs C2A and C2E in Cartesian_filter_K.
But you will probably have other issues. Approximate_kernel and Exact_kernel probably don't satisfy the Kernel_d concept. Maybe using Kernel_d_interface<Exact_kernel> in your code would help, but since I have never tried something like that, there may be issues. Global functions like CGAL::squared_distance are also not supported.

Kernels were designed for a separation of concerns between algorithms and predicates/constructions. Handling filtering by hand for a specific algorithm may indeed be more efficient, but it is bound to be a bit awkward.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants