MeshLib C++ Docs
Loading...
Searching...
No Matches

for internal use: namespace detail is not bound to other languages More...

Namespaces

namespace  AffineXf3f
namespace  Units

Classes

class  FuncCallHelper
struct  HashMapSlots
 phmap has no public access to a slot of a hash table by its index: take its protected iterator_at() via a member pointer More...
struct  MakeScopeGuard
struct  NoInitIterator
 random-access iterator over a range of not-initialized T for std::vector::insert More...
class  PerturbationStagesOf
 segmentIntersectionTriPlaneOrder: it reaches the polynomial path with all three largest ids in the plane More...
struct  PointDegree
 a point with the degree of its perturbation: its coordinates z, y, x get eps^d, eps^(3*d), eps^(9*d) More...
class  ScopeGuard

Typedefs

using PerturbationStages = PerturbationStagesOf<cMaxPerturbedPoints, false>
 the stages of at most cMaxPerturbedPoints points, whose degrees the caller makes fit in int64
template<std::int64_t M>
using VolumePoly = SparsePolynomial<FastInt128, std::int64_t, M>

Functions

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 &params)
 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 &params)
 Open XDG Desktop Portal file dialog.

Variables

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

Detailed Description

for internal use: namespace detail is not bound to other languages

Typedef Documentation

◆ PerturbationStages

the stages of at most cMaxPerturbedPoints points, whose degrees the caller makes fit in int64

◆ VolumePoly

template<std::int64_t M>
using MR::detail::VolumePoly = SparsePolynomial<FastInt128, std::int64_t, M>

128 bits are enough to store all coefficients of one orient3d-polynomial (products of three coordinate differences), while the products of two such polynomials are computed in 256 bits, see signOfProductsDiff<Int128Mul256>

Function Documentation

◆ addCarry64()

std::uint64_t MR::detail::addCarry64 ( std::uint64_t a,
std::uint64_t b,
std::uint64_t & carry )
inlinenodiscardconstexprnoexcept

returns a + b + carry modulo 2^64, and replaces carry with the carry-out (0 or 1)

the two functions below are spelled via FastUInt128, where the carry-out is simply the higher word, as in mulWords below

◆ doubleFromWords()

double MR::detail::doubleFromWords ( const std::uint64_t * w,
int n )
nodiscardnoexcept

the nearest double to the two's-complement value in the n words at w, least significant first; see toDouble below for the guarantees, which this function alone provides for the whole family

◆ getPointDegrees()

template<int N = cMaxPerturbedPoints, bool Bounded = false>
MR_FORCE_INLINE int MR::detail::getPointDegrees ( const PreciseVertCoords * vs,
const std::int64_t * radices,
int n,
PointDegree * res,
std::int64_t * places = nullptr )

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

◆ isPortalFileDialogSupported()

bool MR::detail::isPortalFileDialogSupported ( )

Checks if XDG Desktop Portal file dialogs are supported.

◆ mulWords()

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

◆ mulWordsOf()

template<typename T>
auto MR::detail::mulWordsOf ( T v)
nodiscardconstexprnoexcept

the words of a multiplier of FastInt, sign-extended if it is signed

◆ orient3dPoly()

template<std::int64_t M>
VolumePoly< M > MR::detail::orient3dPoly ( const PointDegree & a,
const PointDegree & b,
const PointDegree & c,
const PointDegree & d )
nodiscard

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

◆ orient3dVolume()

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

◆ runCocoaFileDialog()

std::vector< std::filesystem::path > MR::detail::runCocoaFileDialog ( const MR::FileDialog::Parameters & params)

Open Cocoa file dialog.

◆ runPortalFileDialog()

std::vector< std::filesystem::path > MR::detail::runPortalFileDialog ( const MR::FileDialog::Parameters & params)

Open XDG Desktop Portal file dialog.

◆ signWord()

std::uint64_t MR::detail::signWord ( std::uint64_t hi)
inlinenodiscardconstexprnoexcept

all ones if the highest bit of the given word is set, and zeros otherwise

◆ subBorrow64()

std::uint64_t MR::detail::subBorrow64 ( std::uint64_t a,
std::uint64_t b,
std::uint64_t & borrow )
inlinenodiscardconstexprnoexcept

returns a - b - borrow modulo 2^64, and replaces borrow with the borrow-out (0 or 1)

Variable Documentation

◆ cFitsFastInt128

template<typename T>
bool MR::detail::cFitsFastInt128 = std::is_integral_v<T> || std::is_same_v<T, FastInt128>
constexpr

the integer types that FastInt128 represents exactly, and which the classes below accept

◆ cMaxPerturbedPoints

int MR::detail::cMaxPerturbedPoints = 16
constexpr

the largest number of points of one predicate that getPointDegrees and PerturbationStages take by default

◆ cMaxPolyDAll

std::int64_t MR::detail::cMaxPolyDAll = std::numeric_limits<std::int64_t>::max()
constexpr

the largest degree that no term exceeds: a polynomial with it keeps all its terms

◆ cMaxPolyDTriPlane

std::int64_t MR::detail::cMaxPolyDTriPlane = 430'486'893
constexpr

segmentIntersectionOrder

◆ cMaxPolyDTriTri

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

◆ cMulBits

template<typename T>
int MR::detail::cMulBits = std::is_same_v<T, FastInt128> || ( std::is_unsigned_v<T> && sizeof( T ) >= 8 ) ? 128 : 64
constexpr

the number of bits a multiplier of FastInt occupies: 128 for FastInt128 and for an unsigned 64-bit integer, both of which need two words, and 64 for anything signed or narrower