CGAL
Improvement backports from CDT_3 branch (Follow-up to PR #8170)
Summary of Changes
In the PR #8170, merged for CGAL-6.0, there was several commits that I had to revert, because they broke the testsuite results:
- [x] commit 612d6e3f592a133a21d14a00e0ffe849b11e2b04, that modified the function
save_binary_file. That was no correct as regards to the C3t3 concept. It is now fixed by commit https://github.com/CGAL/cgal/pull/8273/commits/c10dcf7daf6ba7fa8b382043a220430618492a9b from this PR. - [ ] commit 1ca6c17a2a165dccb2204f01d38d6d3d903d11c9, that optimized the efficiency of
Polyline_constraint_hierarchy_2using an unordered map, instead of astd::map. The issue was that is broke the determinism of Mesh_2. See https://github.com/CGAL/cgal/pull/8273#discussion_r1638397885. - [ ] commit ac47f30cd8a0921e52e3bd2a88fb435092eef837, that introduced an experimental tuple protocol for
CGAL::Segment_3, for some CGAL kernels. - [x] commit df28ddc43ab3af1a54a2d9ad9587ab846707b752, that fixed a CMake warning about VTK-9.x. Now fixed by another PR (#8279).
This pull-request reintroduces those features, for CGAL-6.1.
Release Management
- Affected package(s):
- License and copyright ownership: maintenance by GeometryFactory
Order of the sequence of values from the range CGAL::Constrained_triangulation_plus_2<Tr>::subconstraints()
@janetournois @afabri
- The patch https://github.com/CGAL/cgal/pull/8273/commits/93fd96644c9e2a1aab33433880afada3e4eed02c makes the range
CGAL::Constrained_triangulation_plus_2<Tr>::subconstraints()non-deterministic: instead of astd::mapwith a customcomparefunctor, now the sub-constraints are in an unordered map, for efficiency reasons. Note that the range was never documented as sorted or deterministic. - As my patch had broken a test from Mesh_2 (the test
test_meshing), I had to fix that non-determinism. That was complicated to fix directly inConstrained_triangulation_plus_2orConstrained_triangulation_plus_2. Instead, I have chosen to fix the only place in CGAL where the order of that range mattered, inMesh_2/include/CGAL/Mesh_2/Refine_edges.h. See the commit https://github.com/CGAL/cgal/pull/8273/commits/82b53596fd6beaaf6c5accf2182cbdd3553b3365.
Is that correct? That is a sort of breaking change, but the ordering of Ctp_2::constraints() was never documented.
Order of the sequence of values from the range
CGAL::Constrained_triangulation_plus_2<Tr>::subconstraints()
Jane (IRL) suggested that:
- it is documented that there is a breaking change
- and add a Tag to
Constrained_triangulation_plus_2to allow users to fallback to the previous behavior.
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/8273/test_build_doc/Manual/index.html
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "Published by a pub.dev verified publisher"){kind=small}
boost 1.74 is requested but some test plateforms do not have it. Do you really need that minimal version?
Dump the requirement for Boost to 1.74 or later? (currently 1.72)
boost 1.74 is requested but some test plateforms do not have it. Do you really need that minimal version?
Short answer
Yes, I really need it.
Long answer
Actually no: I could use the ancient boost::iterator_facade from Boost.Iterator, but Boost.STLInterfaces is a lot nicer to use, and create real iterator types, even with proxy iterators like the one I wrote.
But platforms supported by CGAL-6.0 currently have also Boost 1.74 or later.
Details... (click to expand)
-
Fedora has Boost>=1.74 since Fedora 35, published 2021-11-02, and the previous version Fedora 34 is not supported since 2021-11-02 (the current version is Fedora 41, two versions per years).
-
Debian has Boost>=1.74 since its version
bullseyes, that is currently the "oldstable" version of Debian. And the version before,buster, is:- "EOL" since 2022-09-10,
- "EOL LTS" since 2024-06-30.
-
Ubuntu: since Ubuntu 22.04 LTS (aka Focal), and the previous supported version, 20.04 LTS, does not have Boost 1.72 anyway,
-
Same for Redhat Enterprise/CentOS/AlmaLinux: version 9 has 1.75, and the previous version had only Boost 1.66.
-
Conan has Boost 1.86, Conda has Boost 1.85, vcpkg has Boost 1.86, Homebrew has Boost 1.87... all package managers have very recent versions.
So...
- there is no supported versions of Linux that is currently supported by CGAL-6.0 and will not be by CGAL-6.1,
- all the package managers have Boost >= 1.85,
- and for Windows that is as easy to install any version of Boost as it is for version 1.72.
I saw that you changed it in ThirdParties.txt,. So all which remains to do is to ask Nicolas to upgrade the testsuite machines.
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/8273/doc/Manual/index.html
more errors:
35>C:\CGAL_ROOT\CGAL-6.1-Ic-73\include\CGAL/Constrained_Delaunay_triangulation_2.h(912): error C2244: 'CGAL::Constrained_Delaunay_triangulation_2<Gt,Tds_,Itag_>::virtual_insert': unable to match function definition to an existing declaration [C:\CGAL_ROOT\CGAL-6.1-Ic-73\cmake\platforms\MSVC2017-Release-64bits\test\Triangulation_2\issue_3447.vcxproj]
C:\CGAL_ROOT\CGAL-6.1-Ic-73\include\CGAL/Constrained_Delaunay_triangulation_2.h(907): note: see declaration of 'CGAL::Constrained_Delaunay_triangulation_2<Gt,Tds_,Itag_>::virtual_insert'
C:\CGAL_ROOT\CGAL-6.1-Ic-73\include\CGAL/Constrained_Delaunay_triangulation_2.h(912): note: definition
C:\CGAL_ROOT\CGAL-6.1-Ic-73\include\CGAL/Constrained_Delaunay_triangulation_2.h(912): note: 'Constrained_Delaunay_triangulation_2<Gt,Tds_,Itag_>::Vertex_handle CGAL::Constrained_Delaunay_triangulation_2<Gt,Tds_,Itag_>::virtual_insert(const Constrained_Delaunay_triangulation_2<Gt,Tds_,Itag_>::Geom_traits::Point_2
Meshing the triangulation with size 0...C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.16.27023\include\xtree(275) : Assertion failed: map/set iterators incompatible
/mnt/testsuite/include/CGAL/Triangulation_2/internal/Polyline_constraint_hierarchy_2.h:129:61: error: static assertion failed
129 | BOOST_STL_INTERFACES_STATIC_ASSERT_CONCEPT(Point_it, std::bidirectional_iterator);
include\CGAL/Base_with_time_stamp.h(23): error C2248: 'CGAL::Constrained_triangulation_face_base_2<K,CGAL::Triangulation_face_base_2<Gt,CGAL::Triangulation_ds_face_base_2<void>>>::Base': cannot access private typedef declared in class 'CGAL::Constrained_triangulation_face_base_2<K,CGAL::Triangulation_face_base_2<Gt,CGAL::Triangulation_ds_face_base_2<void>>>'
Meshing the triangulation with size 0...C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.16.27023\include\xtree(275) : Assertion failed: map/set iterators incompatible
The code was doing bad operations with value-initialized iterators. Fixed in d837dbde218d9c24727b65b8e533404651341954.
/mnt/testsuite/include/CGAL/Triangulation_2/internal/Polyline_constraint_hierarchy_2.h:129:61: error: static assertion failed 129 | BOOST_STL_INTERFACES_STATIC_ASSERT_CONCEPT(Point_it, std::bidirectional_iterator);
With C++20, the behavior of Boost.STLinterface was different. I have fixed, and tested with and without C++20. And I found a bug in the macro BOOST_STL_INTERFACES_STATIC_ASSERT_ITERATOR_TRAITS before Boost 1.83.0. That is fixed in 571c2ccadc440672917313d8540016894ae7fa78.
include\CGAL/Base_with_time_stamp.h(23): error C2248: 'CGAL::Constrained_triangulation_face_base_2<K,CGAL::Triangulation_face_base_2<Gt,CGAL::Triangulation_ds_face_base_2<void>>>::Base': cannot access private typedef declared in class 'CGAL::Constrained_triangulation_face_base_2<K,CGAL::Triangulation_face_base_2<Gt,CGAL::Triangulation_ds_face_base_2<void>>>'
A known issue with MSVC 2017 (see the repro). Fixed in 571c2ccadc440672917313d8540016894ae7fa78 as well (it should have been a distinct commit).
Note that it might come from the time_stamp PR.
@sloriot
Benchmarks
This PR got even bigger now. I had to:
- fix the error handling of WKT input functions (765744e8b2ea77a00b2ba99b42f5b7e6527601c7),
- change the CMake scripts to add
CGAL_with_benchmarksas a CMake options (050677f002f7478d95a61d75c30db7c5cf27263d), - and then add a benchmark file using https://github.com/google/benchmark/ (bc44c91536c1ba39172d252f9a9855261a2b9f95)
Results
Using CGAL::Polyline_simplification_2::simplify on a CDT constructed from the file Data/data/wkt/norway-MP.wkt, the execution from this PR is about 18% faster than the code from master.
The results can be seen at https://cgal.geometryfactory.com/~lrineau/simplify-bench.html and in this screenshot:
Details in text (click for more...)
Using the tool compare.py from Google Benchmark Tools...
...given that:
benchmark_simplify-AFTERis the filebenchmark_simplify.cppcompiled from this branch, and flags-msse3 -DNDEBUG -O3with gcc version 14.2.1,benchmark_simplify-BEFOREis the same file compiled from the branchmaster, and same flags and compiler.
the command line was:
compare.py benchmarks build/Release/benchmark/Polyline_simplification_2/benchmark_simplify-BEFORE build/Release/benchmark/Polyline_simplification_2/benchmark_simplify-AFTER Data/data/wkt/norway-MP.wkt --benchmark_repetitions=20 --benchmark_counters_tabular=true --benchmark_time_unit=s
The following results show that there is a speedup of about 15% (mean) or 18% (median)
RUNNING: build/Release/benchmark/Polyline_simplification_2/benchmark_simplify-BEFORE Data/data/wkt/norway-MP.wkt --benchmark_repetitions=20 --benchmark_counters_tabular=true --benchmark_time_unit=s --benchmark_out=/tmp/tmpvxyq_i24
2025-02-06T17:23:08+01:00
Running Data/data/wkt/norway-MP.wkt
Run on (16 X 800 MHz CPU s)
CPU Caches:
L1 Data 48 KiB (x8)
L1 Instruction 32 KiB (x8)
L2 Unified 1280 KiB (x8)
L3 Unified 24576 KiB (x1)
Load Average: 1.47, 2.07, 1.65
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations #points #polygons #polylines nb of constraints nb of sub-constraints nb of vertices
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
simplify file Data/data/wkt/norway-MP.wkt 0.067 s 0.067 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.066 s 0.066 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.065 s 0.065 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.073 s 0.072 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.066 s 0.066 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.064 s 0.064 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.067 s 0.066 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.071 s 0.071 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.064 s 0.064 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.064 s 0.064 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.074 s 0.074 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.066 s 0.066 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.075 s 0.074 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.074 s 0.074 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.076 s 0.076 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.078 s 0.078 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.074 s 0.074 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.067 s 0.067 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.064 s 0.064 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.069 s 0.069 s 12 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt_mean 0.069 s 0.069 s 20 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt_median 0.067 s 0.067 s 20 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt_stddev 0.005 s 0.005 s 20 0 0 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt_cv 6.73 % 6.68 % 20 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
RUNNING: build/Release/benchmark/Polyline_simplification_2/benchmark_simplify-AFTER Data/data/wkt/norway-MP.wkt --benchmark_repetitions=20 --benchmark_counters_tabular=true --benchmark_time_unit=s --benchmark_out=/tmp/tmp59ui0dsw
2025-02-06T17:29:26+01:00
Running Data/data/wkt/norway-MP.wkt
Run on (16 X 800.961 MHz CPU s)
CPU Caches:
L1 Data 48 KiB (x8)
L1 Instruction 32 KiB (x8)
L2 Unified 1280 KiB (x8)
L3 Unified 24576 KiB (x1)
Load Average: 1.61, 1.94, 1.73
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations #points #polygons #polylines nb of constraints nb of sub-constraints nb of vertices
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
simplify file Data/data/wkt/norway-MP.wkt 0.054 s 0.054 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.057 s 0.057 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.059 s 0.059 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.065 s 0.065 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.058 s 0.058 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.056 s 0.056 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.053 s 0.053 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.061 s 0.061 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.058 s 0.058 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.052 s 0.052 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.054 s 0.054 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.055 s 0.054 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.054 s 0.054 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.055 s 0.054 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.054 s 0.054 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.059 s 0.059 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.057 s 0.057 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.058 s 0.057 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.055 s 0.055 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt 0.059 s 0.059 s 13 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt_mean 0.057 s 0.057 s 20 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt_median 0.057 s 0.056 s 20 0 848 0 849 40.568k 40.565k
simplify file Data/data/wkt/norway-MP.wkt_stddev 0.003 s 0.003 s 20 0 0 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt_cv 5.37 % 5.32 % 20 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
Comparing build/Release/benchmark/Polyline_simplification_2/benchmark_simplify-BEFORE to build/Release/benchmark/Polyline_simplification_2/benchmark_simplify-AFTER
Benchmark Time CPU Time Old Time New CPU Old CPU New
-----------------------------------------------------------------------------------------------------------------------------------------------
simplify file Data/data/wkt/norway-MP.wkt -0.1941 -0.1942 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.1269 -0.1272 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.0900 -0.0918 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.1049 -0.1065 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.1204 -0.1206 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.1279 -0.1282 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.1962 -0.1961 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.1370 -0.1377 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.0951 -0.0962 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.1851 -0.1852 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.2720 -0.2716 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.1702 -0.1717 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.2700 -0.2703 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.2644 -0.2634 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.2861 -0.2856 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.2492 -0.2488 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.2310 -0.2301 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.1382 -0.1389 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.1401 -0.1406 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt -0.1464 -0.1467 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt_pvalue 0.0000 0.0000 U Test, Repetitions: 20 vs 20
simplify file Data/data/wkt/norway-MP.wkt_mean -0.1804 -0.1806 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt_median -0.1547 -0.1549 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt_stddev -0.3458 -0.3479 0 0 0 0
simplify file Data/data/wkt/norway-MP.wkt_cv -0.2018 -0.2041 0 0 0 0
OVERALL_GEOMEAN -0.1797 -0.1800 0 0 0 0
@lrineau could you please fix conflicts?
Done, with commit 8eefb7f173e320d9839048e727931e01bfdf3506.