CGAL
Nef_3: Sphere map sizes
Summary of Changes
Within SNC_sphere_map the values for number_of_svertices / number_of_shalfedges / number_of_sfaces are calculated by calling the base class in Vertex.h which uses loops to calculate the number of vertices:
https://github.com/CGAL/cgal/blob/088f5c3e18b6a38510b6d457a34ba7d698903757/Nef_3/include/CGAL/Nef_3/Vertex.h#L214-L226
While this generally isn't an issue, at certain places in the code, a constant time O(1) lookup of the number of svertices/shalfedges/sfaces is useful instead of the current linear time O(n) lookup. In particular, allocating the size of the hashmaps Pitem, Vitem and linked in the SNC_SM_overlayer.h function simplify
Since the SNC_sphere_map has methods to new/delete these items, member variables can be added which are incremented on new, and decremented on delete. An additional method update_number_of_items is needed for SNC_io_parser which updates the start and end pointers of the SNC_sphere_map directly.
While profiling the hashmaps it was also discovered that the hashmap mark_of_right_sface within SNC_constructor (called before simplify) only ever seems to contain two items. Furthermore, the loop in which the values of the hashmap are set indexes the edges in the same order as the loop in which the hashmap is read. Therefore the hashmap can simply be replaced with a vector. (in theory, a 2-element array could be used but I don't want to make that assumption)
CGAL_assertions have been added to test assumptions in the above.
Release Management
- Affected package(s): Nef_3
- Issue(s) solved (if any): performance
- License and copyright ownership: CGAL authors
Benchmark results:
| version | time (ms) | version | time (ms) | |
|---|---|---|---|---|
| baseline: | 12429 | contender: | 12417 | |
| baseline: | 13017 | contender: | 12989 | |
| baseline: | 13359 | contender: | 12535 | |
| baseline: | 13598 | contender: | 13239 | |
| baseline: | 13490 | contender: | 13207 | |
| baseline: | 13455 | contender: | 12580 | |
| baseline: | 12933 | contender: | 13354 | |
| baseline: | 12938 | contender: | 13341 | |
| baseline: | 13556 | contender: | 13285 | |
| baseline: | 13710 | contender: | 13157 | |
| 13248.5 | 13010.4 | 1.80% |
There were some compilation issue like in tests and runtime errors especially on windows. See https://cgal.geometryfactory.com/CGAL/testsuite/results-5.6-Ic-180.shtml#Nef_3_Examples.
We can give it another try in the testsuite and see what remains after your fix.
@sloriot Looking at the errors they appear to all be due to the incorrect assertion code, which I have fixed. Please do try another test.