Automatically generated, fast floating-point predicates
This pull request contains the first part of my GSoC 2020 project. This code is still work in progress and there might be changes to the interface before the end of GSoC.
The project aims to implement a number of facilities that allow easy creation of fast and robust geometric floating-point predicates, such as, for example, orientation tests (Boost.Geometry currently has a 2d orientation test in the side-strategy). As of writing this, the pull request contains templates to
- automatically derive error bounds for the approximate evaluation of such expressions
- build static, almost static and semi-static filters from these expressions
I intend to add
- generation of functions for the exact evaluation of arbitrary arithmetic floating-point expressions containing +, - and * using expansion arithmetic
- improvements for the error bound derivation
- an alternative method for error bound derivation
- some additional filters
- automatic detection of reusable interim results between filter stages
The usage of the various templates for the creation of geometric predicates is illustrated in the tests and the example.
This pull request depends on Boost.MP11, which depends on C++11 but has no additional dependencies. The code itself depends on C++14 because of certain constexpr features.
I have made the following changes to the PR:
- The template-based error bound calculation has been replaced by a constexpr based implementation. This improves compile-time, template instantiation depth and readability.
- I have tried to address all feedback (spaces after if, unused parameters, position of "const" in types"
- Staged predicates have been added.
The PR now includes a new test-case in https://github.com/BoostGSoC20/geometry/blob/feature/floating_point_filters/extensions/test/generic_robust_predicates/staged.cpp . It illustrates the intended use of the code in this PR.
For a given geometric predicate (in the example the side-predicate), an expression type needs to be constructed. Using the expression type and a floating-point calculation type (like double), filters can be constructed from the stage_* files. These filters can be combined into a staged_predicate for usage, for example, in a robust side strategy or any other strategy that can be computed as the sign of a polynomial of floating-point coordinates.
The remaining headers are not intended to be used directly and can be considered implementation details.