CGAL users discussion list

[Efi Fogel <>]

The performance hit is due to the overhead handling of non-convex polygons.

When handling non-convex polygons this overhead becomes negligible.

So, the solution is to get rid of the overhead for convex polygons, and possibly optimize this overhead for non-convex polygons.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Wed, 17 Jan 2024 at 19:22, Andreas Fabri <> wrote:

Hi Valentin,

Are your polygons always convex?

Best,

Andreas

On 1/10/2024 10:27 PM, Valentin Pi ( via cgal-discuss Mailing List) wrote:

Hi Efi,

Thank you very much for taking the time. I am glad to seemingly have discovered some unnecessary overhead. I have tried the patch and your snippet, as well as averaged the runtime over 10000 samples. For some reason I now have ~400µs instead of 200µs for the first Minkowski sum, and then the runtime gets quickly down to about 10µs with a i5-1135G7 2.40GHz processor on my laptop. Since I suspected that this is due to caching or some other system effects, I have now randomized the triangles (and renamed them to triangles in the code, sorry for possible confusion) and introduced a delay between each step of the loop. This gives the following source for main.cpp.

#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_convex_decomposition_2.h>
#include <CGAL/Polygon_nop_decomposition_2.h>
#include <CGAL/Polygon_triangulation_decomposition_2.h>
#include <CGAL/minkowski_sum_2.h>
#include <CGAL/version_macros.h>

#include <chrono>
#include <iostream>
#include <random>
#include <thread>
#include <vector>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Point_2<Kernel> Point;
typedef CGAL::Polygon_2<Kernel> Polygon;
typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes;

using Container = std::vector<Point>;
using Arr_segment_traits = CGAL::Arr_segment_traits_2<Kernel>;
using Traits = CGAL::Gps_segment_traits_2<Kernel, Container, Arr_segment_traits>;

int main(int argc, char** argv) {
    using std::vector;
    using std::chrono::high_resolution_clock;
    using namespace std::chrono_literals;

    std::cout << CGAL_VERSION_STR << std::endl;

    std::default_random_engine gen;
    std::uniform_int_distribution<uint64_t> dist(0, 10000);
    auto rand_coord = std::bind(dist, gen);
    Traits traits;
    size_t acc = 0;
    size_t n = 1000;
    for (int i = 0; i < n; i++) {
        Polygon triangle_1;
        Polygon triangle_2;
        while (true) {
            vector triangle_1_points({Point(rand_coord(), rand_coord()), Point(rand_coord(), rand_coord()),
                                      Point(rand_coord(), rand_coord())});
            vector triangle_2_points({Point(rand_coord(), rand_coord()), Point(rand_coord(), rand_coord()),
                                      Point(rand_coord(), rand_coord())});
            triangle_1 = Polygon(triangle_1_points.begin(), triangle_1_points.end());
            triangle_2 = Polygon(triangle_2_points.begin(), triangle_2_points.end());
            if (triangle_1.is_clockwise_oriented()) {
                triangle_1.reverse_orientation();
            }
            if (triangle_2.is_clockwise_oriented()) {
                triangle_2.reverse_orientation();
            }
            if (triangle_1.is_simple() && triangle_2.is_simple()) {
                break;
            }
        }
        auto t1 = high_resolution_clock::now();
        Polygon_with_holes result =
            CGAL::minkowski_sum_2(triangle_1, triangle_2, CGAL::Polygon_nop_decomposition_2<Kernel>(), traits);
        auto t2 = high_resolution_clock::now();
        std::cout << std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count() << "µs" << std::endl;
        acc += std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
        if (i == 0) {
            std::cout << acc << "µs" << std::endl;
        }
        std::this_thread::sleep_for(1ms);
    }
    const size_t avg = acc / n;
    std::cout << avg << "µs" << std::endl;

    return EXIT_SUCCESS;
}

Running this, I get about 600µs for the first Minkowski sum on the most recent branch with the patch you provided me, as well as about 150µs on average for each Minkowski sum. In our main project we get about 300µs for each Minkowski sum. I suspect that allocations are slowing down the Minkowski sum significantly, but I cannot prove it.

Best
Valentin

Am 10.01.24 um 13:34 schrieb Efi Fogel ( via cgal-discuss Mailing List):

Hi Valentin,

I've decided to look into it, cause the timings seemed odd, and I found a few things.

I'm running an i7 core clocked at 2.20GHz:

cat /proc/cpuinfo  | grep 'name'| uniq
model name : Intel(R) Core(TM) i7-2720QM CPU @ 2.20GHz

I changed the single call to a loop and added the traits parameter.

I get ~20us on average on my machine per minkowski sum.

However, even with this I wasn't satisfied.

It turns out that there is some overhead that consumes some unexplained significant amount of time.

Attached is a patch that avoids (some of) the overhead.

It applies to 2 files:

modified:   Minkowski_sum_2/include/CGAL/Minkowski_sum_2/Minkowski_sum_decomp_2.h
modified:   Minkowski_sum_2/include/CGAL/minkowski_sum_2.h

It is based on the most recent version, so if the automatic application of the patch fails for you, apply it manually. It is rather simple.

Also, make sure to use the following snippet:

using Kernel = CGAL::Exact_predicates_exact_constructions_kernel;
using Point = CGAL::Point_2<Kernel>;
using Container = std::vector<Point>;
using Arr_segment_traits = CGAL::Arr_segment_traits_2<Kernel>;
using Traits = CGAL::Gps_segment_traits_2<Kernel, Container, Arr_segment_traits>;

using Nop = CGAL::Polygon_nop_decomposition_2<Kernel, Container>;

Traits traits;

CGAL::minkowski_sum_by_decomposition_2(square_1, square_2, nop, traits);

which knocks out almost ~2/3 of the computation time, and I get ~7us.

Naturally, I'll continue to investigate the issue and fix the code base.

Best,

Efi

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Tue, 9 Jan 2024 at 19:22, Valentin Pi <> wrote:

You are right, I didn't try that yet. This cuts about 25µs of the runtime to about 175µs.

Am 09.01.24 um 15:57 schrieb Efi Fogel ( via cgal-discuss Mailing List):

If so, then use the decomposition Minkowski-sum method, with a nop decomposition operation; see https://doc.cgal.org/latest/Minkowski_sum_2/classCGAL_1_1Polygon__nop__decomposition__2.html

Try something like this:

Polygon_with_holes result = CGAL::minkowski_sum_2(square_1, square_2, CGAL::Polygon_nop_decomposition_2<Kernel>());

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Tue, 9 Jan 2024 at 12:58, Valentin Pi <> wrote:

Yes, I just checked. Would be surprising to me if not, since there are unique coordinates for each triangle in the code.

Am 09.01.24 um 11:31 schrieb Efi Fogel ( via cgal-discuss Mailing List):

Do you have any guarantee about the input polygons being convex?

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Tue, 9 Jan 2024 at 10:41, Valentin Pi <> wrote:

Thanks for the quick reply.
1. I have now tried a couple of versions, but only from the header-only versions. Denoted with the tag names each, I give the following table of observed average times. The numbers I gave initially were with v5.6, as already said.

Release tag - Observed average runtime
6.0-dev [1] - 200µs
       v5.6 - 200µs
       v5.5 - 185µs
       v5.4 - 275µs
       v5.3 - 300µs
       v5.2 - 275µs
       v5.1 - 250µs

[1] The current version at commit a15af8ef645c414956640348d036609b9a0a5c38.

I do not detect a degradation with any particular version, except for a slight jump from 275µs to 185µs between v5.4 and v5.5. For the complexity of the problem anything over a couple of µs is too much for our application, so all of these times are problematic for us. I could try older versions if you think it would make a difference.
2. I have tried convolution (in v5.6) and it gives about the same time.

Am 09.01.24 um 08:10 schrieb Efi Fogel ( via cgal-discuss Mailing List):

1. Have you measured it with a different version? I mean, are you detecting a degradation?

2. Have you tried other implemented alg, or at least other decomposition methods?

The call without a decomposition method invokes the partial-convolution method, which is the most efficient in most cases:

CGAL::minkowski_sum_2(square_1, square_2);

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Tue, 9 Jan 2024 at 01:09, Valentin Pi <> wrote:

Hello everyone,

I hope this issue fits this list. In our current project we need to compute a lot of small Minkowski sums, and I wanted to ask if someone could please give me some help in speeding that process up. The following CGAL program computing the Minkowski sum of two small polygons demonstrates the problem.

main.cpp:

#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_convex_decomposition_2.h>
#include <CGAL/Polygon_triangulation_decomposition_2.h>
#include <CGAL/minkowski_sum_2.h>

#include <chrono>
#include <iostream>
#include <vector>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Point_2<Kernel> Point;
typedef CGAL::Polygon_2<Kernel> Polygon;
typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes;

int main(int argc, char** argv) {
    using std::vector;
    using std::chrono::high_resolution_clock;

    vector square_1_points({Point(0, 0), Point(4, 0), Point(4, 4)});
    vector square_2_points({Point(2, 1), Point(3, 1), Point(3, 2)});
    Polygon square_1(square_1_points.begin(), square_1_points.end());
    Polygon square_2(square_2_points.begin(), square_2_points.end());
    auto t1 = high_resolution_clock::now();
    Polygon_with_holes result =
        CGAL::minkowski_sum_2(square_1, square_2, CGAL::Hertel_Mehlhorn_convex_decomposition_2<Kernel>());
    auto t2 = high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count() << "µs" << std::endl;

    return EXIT_SUCCESS;
}

CMakeLists.txt:

cmake_minimum_required(VERSION 3.19.1)
# SotMS: "Slowness of the Minkowski Sum"
project(sotms)
find_package(CGAL 5.6 REQUIRED COMPONENTS Core)

add_compile_options(-O2)
set(CMAKE_BUILD_TYPE Release)

add_executable(sotms src/main.cpp)
target_link_libraries(sotms CGAL::CGAL_Core)

Compilation and execution (move the main.cpp in a folder named src and the CMakeLists.txt in a folder above before):

$ cd src
$ cmake ..
$ make -j
$ ./sotms

I have observed the following:
1. The execution times for CGAL::minkowski_sum_2 for the above program lie around 200µs. This gives room for about 5000 Minkowski sums per second, which is not a lot, given the complexity of the above problem.
2. In the main project we usually have runtimes of about 1500µs. In some executions of our main project program the runtime jumps to several seconds up to minutes, but I cannot reproduce that well yet.
3. Repeating the above code (by introducing a for loop wrapping around the lines 23-27) yields runtimes of about 20µs, but I think this is due to optimizations, but 20µs is still too much.
4. Disabling optimizations (-O0) gives runtimes of about 1000µs for the first Minkowski sum, which then upon repetition of the computation breaks down to about 200µs again for some reason.

I have already tried changing the kernel to an inexact kernel, which still gives poor performance and does not suit our use case, since it often crashes. I am on an Arch Linux (x64) laptop, CGAL is compiled with GMP and MPFR, everything is up to date. The CGAL version in the Arch repository is 5.6

Best
Valentin

--
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

--
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

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

-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

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