Open dpapavas opened 2 years ago
Thank you for your bug report. The fix you refer to is in fact not really generic. It just fixes that one can include the measure header before the exact constructions header file.
Seing the generic version of exact(const T&)
here I thought we might just add a specialization of std::is_arithmetic
for Gmpq
but that is as good as adding the overload of exact(const Gmpq&)
, and it is probably not even allowed as the documentation of std::is_arithmetic
speaks about built-in types. And we would have to document in the measure function that we expect exact()
to be defined for the number type.
But what do we want to achieve here: That in case of a lazy type we do not end up with a deep DAG of the lazy kernel because the measure function sums up the area of the face range.
We could introduce a generic function with a highly specific name (privacy by obfuscation ?) which is the identity function for all types but for Lazy_exact_nt
. Is that better @lrineau @mglisse ?
We cannot specialize std::is_arithmetic
. That is documented:
The behavior of a program that adds specializations for
is_arithmetic
oris_arithmetic_v
is undefined.
But the main issue is that exact(FT)
is not part of any CGAL concept. PR #2663 was an error. We should use a dedicated function name, that would be a nop for all types by Lazy<AT,ET,E2A>
.
That was my suggestion at the end. Note that Lazy is not alone. It is the same for Core::Expr
, so it might still make sense to document the function. Note also that we are not interested in the result, but only in the side effect of collapsing the construction history.
I don't have a strong opinion. We could define exact for other number types. We could introduce another function for that, or reuse an existing one (simplify
looks like it could fit).
It does feel a bit sad to see a loop that repeats "create lazy sum" - "evaluate it", but if it isn't critical, it may not be worth changing it (alternatives could be to make the sums in a balanced binary tree, or to do the computation with a non-lazy type and only convert it to lazy at the end).
It does feel a bit sad to see a loop that repeats "create lazy sum" - "evaluate it", but if it isn't critical, it may not be worth changing it (alternatives could be to make the sums in a balanced binary tree, or to do the computation with a non-lazy type and only convert it to lazy at the end).
Would we create non-lazy versions of construction functors?
I would also love to see the API Get_functor<Kernel, Functor_tag, Option>
(from NewKernel_d) enter the Kernel_23 package. For Epeck, the non-lazy version of functors would then be obtained with a special third argument.
Would we create non-lazy versions of construction functors?
I was thinking something more ad hoc.
Non_lazy<FT> result = 0;
for(...){
result += exact(edge_length(...));
}
return result; // return FT(std::move(result));
Well, it still computes edge_length with a lazy type before evaluating it, so it would only save half of the overhead...
We might also ask who wants to compute the exact area of a triangle mesh.
We might also ask who wants to compute the exact area of a triangle mesh.
Well, @dpapavas did. That worked with older versions of CGAL, and then got broken (probably since CGAL-5.0).
So the Non_lazy
would call exact()
on every operation? And then we document that Non_lazy
is used, which enables users to provide a specialization for number types we do not take care of?
So the
Non_lazy
would callexact()
on every operation?
I was thinking: Non_lazy<Lazy_exact_nt<Gmpq>> == Gmpq
. In this example, the fact that edge_length is a lazy construction makes it not as nice, it still reduces the number of unnecessary Lazy nodes created, but for a function that is probably not critical anyway, so I guess we can forget that. Also, it still needs an exact
function that works on all types, so it doesn't solve the original problem.
From your comment, we could have a special wrapper type Non_lazy<FT>
such that Non_lazy<FT>+FT
calls exact
on the second argument if it is lazy, but that seems a bit too specific.
Having a version of exact
(with the same name or a different name like simplify
or other) that works on all types does seem simpler and more general.
I am wondering if the following could work inside the framework of Lazy numbers. A lazy number stores the operation that had produced it, so when we sum up a + b + c
this produces a node with (interval(a+b), add, a, b)
for the first two terms. When we make the next additon we could find out that the first term is as it is, and store, a,b,c
in a list of child nodes.
When making Lazy_exact_nt thread-safe, I said it made it slower, and that there would be various ways to improve things. I don't remember where I listed those possible improvements, but from the top of my head, they included
a*d-b*c
compute([](auto const&a, auto const&b, auto const&c, auto const&d){return a*d-b*c;},a,b,c,d)
and have it generate a single node. This is less work and more general than the previous option, but requires the user to write their code differently.The above is about static stuff, and not directly related to what you are suggesting, but I had to write it down to help myself see if it might interact with your suggestion.
You seem to suggest that we add some kind of variadic node "plus" that can take an arbitrary number of operands, and during an addition, we detect at runtime if one of the operands is of this type (the same way we already detect weighted points constructed from a point and a weight), and in that case build another "plus" node with one more argument (or more if both were already "plus" maybe). That seems doable, but it would require some thinking and care to avoid any quadratic behavior. It may be easier to restrict it to operator+=
with a lhs that is already a sum if we don't want to overload operator+
based on the value category of the arguments, and in any case we would check the number of references to ensure we don't create a node +(a,b,c) if the node +(a,b) it not going away. This looks a bit ad hoc, maybe adding a bit per element for a possible negation would be slightly more generic, but it would still only handle a rather restricted type of long chains of operations. Maybe that's enough to be useful, maybe not...
Is anyone is working on this issue?
The following program doesn't compile against the latest CGAL source:
It fails, because it cannot find a suitable overload for
exact()
:This is similar to #2654, which was fixed by 68cf051563d25c7842eda5a96f5f7c796c15ea9f, but the cause seems to be different. Perhaps the definition for
CGAL::exact(FT)
mentioned in the commit message got lost along the way. Uncommenting the definition in my test code, allows the program to compile and return the expected result. (I have also tested it with a non-empty mesh, but kept it short in the test code.)