|
| constexpr std::uint64_t | addCarry64 (std::uint64_t a, std::uint64_t b, std::uint64_t &carry) noexcept |
| | returns a + b + carry modulo 2^64, and replaces carry with the carry-out (0 or 1)
|
| constexpr std::uint64_t | subBorrow64 (std::uint64_t a, std::uint64_t b, std::uint64_t &borrow) noexcept |
| | returns a - b - borrow modulo 2^64, and replaces borrow with the borrow-out (0 or 1)
|
| constexpr std::uint64_t | signWord (std::uint64_t hi) noexcept |
| | all ones if the highest bit of the given word is set, and zeros otherwise
|
| template<std::size_t n, std::size_t m> |
| constexpr std::array< std::uint64_t, n+m > | mulWords (const std::array< std::uint64_t, n > &a, const std::array< std::uint64_t, m > &b) noexcept |
| | std::size_t and not int, to be deducible from std::array
|
| template<typename T> |
| constexpr auto | mulWordsOf (T v) noexcept |
| | the words of a multiplier of FastInt, sign-extended if it is signed
|
| double | doubleFromWords (const std::uint64_t *w, int n) noexcept |
| template<typename T> |
| auto | signStep (T x) |
| | +1 for positive x and -1 (all bits set) for negative x, as an unsigned integer of the same size as x
|
| template<typename T> |
| bool | nonzeroBelowMax (T x) |
| | whether 0 < |x| < max: then the closest values around x differ from it by one in the bits; one unsigned comparison of the bits
|
| MR_FORCE_INLINE FastInt128 | orient3dVolume (const Vector3i &a, const Vector3i &b, const Vector3i &c, const Vector3i &d) |
| template<int N = cMaxPerturbedPoints, bool Bounded = false> |
| MR_FORCE_INLINE int | getPointDegrees (const PreciseVertCoords *vs, const std::int64_t *radices, int n, PointDegree *res, std::int64_t *places=nullptr) |
| template<std::int64_t M> |
| VolumePoly< M > | orient3dPoly (const PointDegree &a, const PointDegree &b, const PointDegree &c, const PointDegree &d) |
| | the volume of tetrahedron abcd (see orient3dVolume) of the perturbed points as a polynomial of eps, without the terms of degrees above M
|
| std::vector< std::filesystem::path > | runCocoaFileDialog (const MR::FileDialog::Parameters ¶ms) |
| | Open Cocoa file dialog.
|
| bool | isPortalFileDialogSupported () |
| | Checks if XDG Desktop Portal file dialogs are supported.
|
| std::vector< std::filesystem::path > | runPortalFileDialog (const MR::FileDialog::Parameters ¶ms) |
| | Open XDG Desktop Portal file dialog.
|
|
| template<typename T> |
| constexpr bool | cFitsFastInt128 = std::is_integral_v<T> || std::is_same_v<T, FastInt128> |
| | the integer types that FastInt128 represents exactly, and which the classes below accept
|
| template<typename T> |
| constexpr int | cMulBits = std::is_same_v<T, FastInt128> || ( std::is_unsigned_v<T> && sizeof( T ) >= 8 ) ? 128 : 64 |
| constexpr int | cMaxPerturbedPoints = 16 |
| | the largest number of points of one predicate that getPointDegrees and PerturbationStages take by default
|
| constexpr std::int64_t | cMaxPolyDAll = std::numeric_limits<std::int64_t>::max() |
| | the largest degree that no term exceeds: a polynomial with it keeps all its terms
|
| constexpr std::int64_t | cMaxPolyDTriTri = 15'943'959 |
| constexpr std::int64_t | cMaxPolyDTriPlane = 430'486'893 |
| | segmentIntersectionOrder
|
for internal use: namespace detail is not bound to other languages
template<int N = cMaxPerturbedPoints, bool Bounded = false>
finds the degrees of the perturbation of points vs[0..n-1] and writes them in res[0..n-1]: sorted by ids, the points get the degrees 1, r_0, r_0 * r_1, ..., where r_k is the radix of the k-th id, given in radices[] of every point with that id, and points with equal ids get equal degrees; the smallest id moves most, as in orient3d, and the radix of a point must exceed its weight in every term of the polynomials of the predicate (the sum of 9, 3, 1 over its coordinates in the term), so that the degrees order the terms as the perturbation of orient3d does: by the weights of the points from the largest id down; returns the number of different ids, and writes their degrees in ascending order in places[] if it is not null; n is at most N; the caller makes the degrees fit in int64, unless Bounded: then only the first ids whose terms fit count, since the terms with the k-th id and smaller ones have degrees below r_0 * ... * r_k, and the points of the other ids get the degree 0, which leaves them unperturbed at every stage (see PerturbationStagesOf)
the degrees of the terms with this id do not fit: the ids before it count, and the points of the others stay unperturbed
skip to support triangles with shared vertices
template<std::size_t n, std::size_t m>
| std::array< std::uint64_t, n+m > MR::detail::mulWords |
( |
const std::array< std::uint64_t, n > & | a, |
|
|
const std::array< std::uint64_t, m > & | b ) |
|
nodiscardconstexprnoexcept |
std::size_t and not int, to be deducible from std::array
the exact product of two two's-complement values given by their 64-bit words, which always fits in the sum of their word counts; the only multiplication of this file
schoolbook multiplication of unsigned values
this row adds nothing: 0 * b[j] leaves every res[i + j] unchanged, and res[i + m] is still 0 (never written before this row), so the skipped res[i + m] = carry (carry stays 0 here) would be a no-op. Small-magnitude values keep their high words at 0, so this is the common fast path; negative operands are sign-extended to all-ones top words and are not skipped.
at most ( 2^64 - 1 )^2 + 2 * ( 2^64 - 1 ) < 2^128 here
never written before, since the loop above stops at i + m - 1
a negative argument was taken 2^(64*words) times larger than it is; both subtractions below end exactly at the end of res, so the borrow never leaves it
the volume of tetrahedron abcd (see orient3dVolume) of the perturbed points as a polynomial of eps, without the terms of degrees above M
every element of the matrix with the rows (a-d), (b-d), (c-d) is a polynomial: delta + eps^degP - eps^degD, whose terms are stored below (skipping zero delta and the terms of unperturbed points), the last term is -eps^degD if d is perturbed
the determinant is the sum over 6 permutations of the signed products of three elements, each product has up to 27 monomials; the product of the last terms of three elements (eps^(13*degD) with the sign of permutation) is excluded, since 6 of them cancel one another
all coefficients are not larger than 2^32 by absolute value, so the product of two of them fits in int64
| MR_FORCE_INLINE FastInt128 MR::detail::orient3dVolume |
( |
const Vector3i & | a, |
|
|
const Vector3i & | b, |
|
|
const Vector3i & | c, |
|
|
const Vector3i & | d ) |
|
nodiscard |
the building blocks of the precise predicates in MRPrecisePredicates3.h, shared with the other predicates that must agree with them: the exact volume of a tetrahedron, and its polynomial in eps when the points are perturbed by simulation-of-simplicity the exact signed volume of tetrahedron abcd times 6: dot( a - d, cross( b - d, c - d ) ), whose sign orient3d( a, b, c, d ) returns if it is not zero; 128 bits are enough for coordinates within the range of ConvertToIntVector
| std::int64_t MR::detail::cMaxPolyDTriTri = 15'943'959 |
|
constexpr |
the largest degrees of the polynomial terms that segmentIntersectionOrder and segmentIntersectionTriPlaneOrder consider first, found experimentally (the leading term of nom, or the leading term of at least one of two orient3d-polynomials for the segment's ends) in the tests and in a random sweep of degenerate inputs; the terms of higher degrees are not stored to save computation time, and if they are not enough to decide, the predicates repeat the computation with all terms (cMaxPolyDAll); the tests count the inputs above them, so they live here rather than in MRPrecisePredicates3.cpp