Stack overflow when using CGAL::Aff_transformation_2 to generate rotation matrix.

[Supranaturaler]

Issue Details

Stack overflow when using CGAL::Aff_transformation_2 to generate rotation matrix.

I know I could adjust stack size using /STACK option in windows. But in linux, there seems no way to change the stack size of std::thread. The only solution is to execute ulimit -s before starting the program. Please refer to https://stackoverflow.com/questions/13871763/how-to-set-the-stacksize-with-c11-stdthread. Is it possible no to use recursive in the construct of Aff_transformation_2 or can this be optimized?

Source Code

#include <thread>

#include "CGAL/Exact_predicates_exact_constructions_kernel.h"
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Vector_2 Vector_2;
typedef Kernel::Direction_2 Direction_2;

#include "CGAL/Aff_transformation_2.h"
typedef CGAL::Aff_transformation_2<Kernel> Transformation;

int main(int argc, char* argv[])
{
    auto testRotation = []() 
    {
        Point_2 startPoint(-31420.8, -256500);
        Point_2 endPoint(-31419, -171900);
        Vector_2 borderVector(startPoint, endPoint);
        Transformation rotate(CGAL::ROTATION, Direction_2(borderVector.x(), -borderVector.y()), 1, 1E16);
    };

    std::thread worker(testRotation);
    worker.join();

    return 0;
}

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): Windows 11 home basic 64 bits
• Compiler: MSVC-2019-Community
• Release or debug mode: debug
• Specific flags used (if any):
• CGAL version: CGAL5.2.2
• Boost version: boost_1_76_0
• Other libraries versions if used (Eigen, TBB, etc.):

[lrineau]

You asked for a precision of 1e-16, in the construction of the rotation matrix. The function called to create the transformation is rational_rotation_approximation: https://github.com/CGAL/cgal/blob/b26fa9b5ba72b7de8400614127b80676714a0e28/Kernel_23/include/CGAL/rational_rotation.h#L28-L134

That creates a huge construction graph for the exact numbers involved. Then you were hit by the same bug as #1118: the destruction of a CGAL::Lazy_exact_nt is recursive.

[Supranaturaler]

Bad luck. The old issue seems to be hanged up for years. The thing is I have no solution to adjust stack size using std::thread in linux. Is it possible to solve?

[afabri]

Is there really a need for you to do it with an exact arithmetic?

[Supranaturaler]

I'm afraid so. I need to rotate a polygon along one of its edge. If the length of the edge is too long, I need to guarantee the precision.

[mglisse]

ulimit -s 32768 works for me on linux.

The thread-safe Lazy may make things a bit worse in 5.4, and makes it significantly harder to handle things in a non-recursive manner.

You could create your Transformation using a different kernel (say Simple_cartesian<Exact_rational>) and then convert it.

[Supranaturaler]

ulimit -s 32768 works for me on linux.

The thread-safe Lazy may make things a bit worse in 5.4, and makes it significantly harder to handle things in a non-recursive manner.

You could create your Transformation using a different kernel (say Simple_cartesian<Exact_rational>) and then convert it.

I think it's a good idea to use a different kernel and then convert it back. I'll work on this way if no better solution found. There's another issue in Cartesian_converter.h. CGAL only provide convertion for Aff_transformation_3, but missed the convertion for Aff_transformation_2. I had to add the interface myself. Please check.

[mglisse]

That would make for a nice pull request :wink: (not sure why the 3d version builds an intermediate array t, but that's not your fault)

[afabri]

The mistake we make is that the rational_rotation_approximation() is computed with a lazy number which leads to the deep DAG. It should be constructed with Interval_nt, and in case of a later filter failure with an exact rational number so that is just a single node in the DAG.

[afabri]

@MaelRL do you agree with @lrineau that your PR solves this issue?

[MaelRL]

My PR is only addressing the comment:

There's another issue in Cartesian_converter.h. CGAL only provide convertion for Aff_transformation_3, but missed the convertion for Aff_transformation_2. I had to add the interface myself. Please check.

and not the main issue.