Classes
class	RobustInitCaller

Functions
void	exactinit ()
double	orient2dfast (const double pa, const double pb, const double *pc)
double	orient2d (const double pa, const double pb, const double *pc)
double	orient3dfast (const double pa, const double pb, const double pc, const double pd)
double	orient3d (const double pa, const double pb, const double pc, const double pd)
double	incirclefast (const double pa, const double pb, const double pc, const double pd)
double	incircle (const double pa, const double pb, const double pc, const double pd)
double	inspherefast (const double pa, const double pb, const double pc, const double pd, const double *pe)
double	insphere (const double pa, const double pb, const double pc, const double pd, const double *pe)
static int	fast_expansion_sum_zeroelim (int elen, const double e, int flen, const double f, double *h)
static int	scale_expansion_zeroelim (int elen, const double e, double b, double h)
static double	estimate (int elen, const double *e)
static double	orient2dadapt (const double pa, const double pb, const double *pc, double detsum)
static double	orient3dadapt (const double pa, const double pb, const double pc, const double pd, double permanent)
static double	incircleadapt (const double pa, const double pb, const double pc, const double pd, double permanent)
static double	insphereexact (const double pa, const double pb, const double pc, const double pd, const double *pe)
static double	insphereadapt (const double pa, const double pb, const double pc, const double pd, const double *pe, double permanent)

Variables
static RobustInitCaller	init_caller
static double	splitter
static double	epsilon
static double	resulterrbound = (3.0 + 8.0 * epsilon) * epsilon
static double	ccwerrboundA = (3.0 + 16.0 * epsilon) * epsilon
static double	ccwerrboundB = (2.0 + 12.0 * epsilon) * epsilon
static double	ccwerrboundC = (9.0 + 64.0 * epsilon) * epsilon * epsilon
static double	o3derrboundA = (7.0 + 56.0 * epsilon) * epsilon
static double	o3derrboundB = (3.0 + 28.0 * epsilon) * epsilon
static double	o3derrboundC = (26.0 + 288.0 * epsilon) * epsilon * epsilon
static double	iccerrboundA = (10.0 + 96.0 * epsilon) * epsilon
static double	iccerrboundB = (4.0 + 48.0 * epsilon) * epsilon
static double	iccerrboundC = (44.0 + 576.0 * epsilon) * epsilon * epsilon
static double	isperrboundA = (16.0 + 224.0 * epsilon) * epsilon
static double	isperrboundB = (5.0 + 72.0 * epsilon) * epsilon
static double	isperrboundC = (71.0 + 1408.0 * epsilon) * epsilon * epsilon

Detailed Description

For double versions of orient and incircle functions, use robust predicates that give exact answers for double inputs. First, encapsulate functions from Jonathan Shewchuk's implementation. After this name-space, see the implementation of the double3 primitives.

Function Documentation

◆ estimate()

double blender::robust_pred::estimate	(	int	elen,
		const double *	e )

static

Definition at line 592 of file math_boolean.cc.

References e.

Referenced by incircleadapt(), insphereadapt(), orient2dadapt(), and orient3dadapt().

◆ exactinit()

void blender::robust_pred::exactinit ( )

Referenced by blender::robust_pred::RobustInitCaller::RobustInitCaller().

◆ fast_expansion_sum_zeroelim()

int blender::robust_pred::fast_expansion_sum_zeroelim	(	int	elen,
		const double *	e,
		int	flen,
		const double *	f,
		double *	h )

static

fast_expansion_sum_zeroelim() Sum two expansions, eliminating zero components from the output expansion.

Sets h = e + f. See the long version of my paper for details. h cannot be e or f.

Definition at line 464 of file math_boolean.cc.

References e, Fast_Two_Sum, INEXACT, and Two_Sum.

Referenced by incircleadapt(), insphereadapt(), insphereexact(), orient2dadapt(), and orient3dadapt().

◆ incircle()

double blender::robust_pred::incircle	(	const double *	pa,
		const double *	pb,
		const double *	pc,
		const double *	pd )

Definition at line 1828 of file math_boolean.cc.

References Absolute, iccerrboundA, and incircleadapt().

Referenced by blender::incircle().

◆ incircleadapt()

double blender::robust_pred::incircleadapt	(	const double *	pa,
		const double *	pb,
		const double *	pc,
		const double *	pd,
		double	permanent )

static

Note: since this code comes from an external source, prefer not to break it up to fix this clang-tidy warning.

Definition at line 1305 of file math_boolean.cc.

References Absolute, estimate(), fast_expansion_sum_zeroelim(), iccerrboundB, iccerrboundC, INEXACT, resulterrbound, scale_expansion_zeroelim(), Square, Two_Diff_Tail, Two_Product, Two_Two_Diff, Two_Two_Sum, and v.

Referenced by incircle().

◆ incirclefast()

double blender::robust_pred::incirclefast	(	const double *	pa,
		const double *	pb,
		const double *	pc,
		const double *	pd )

incirclefast() Approximate 2D incircle test. Non-robust. incircle()

         Return a positive value if the point pd lies inside the
         circle passing through pa, pb, and pc; a negative value if
         it lies outside; and zero if the four points are co-circular.
         The points pa, pb, and pc must be in counterclockwise
         order, or the sign of the result will be reversed.

The second uses exact arithmetic to ensure a correct answer. The result returned is the determinant of a matrix. In incircle() only, this determinant is computed adaptively, in the sense that exact arithmetic is used only to the degree it is needed to ensure that the returned value has the correct sign. Hence, incircle() is usually quite fast, but will run more slowly when the input points are co-circular or nearly so.

Definition at line 1277 of file math_boolean.cc.

Referenced by blender::incircle_fast().

◆ insphere()

double blender::robust_pred::insphere	(	const double *	pa,
		const double *	pb,
		const double *	pc,
		const double *	pd,
		const double *	pe )

Definition at line 2361 of file math_boolean.cc.

References Absolute, insphereadapt(), and isperrboundA.

Referenced by blender::insphere().

◆ insphereadapt()

double blender::robust_pred::insphereadapt	(	const double *	pa,
		const double *	pb,
		const double *	pc,
		const double *	pd,
		const double *	pe,
		double	permanent )

static

Definition at line 2160 of file math_boolean.cc.

References Absolute, estimate(), fast_expansion_sum_zeroelim(), INEXACT, insphereexact(), isperrboundB, isperrboundC, resulterrbound, scale_expansion_zeroelim(), Two_Diff_Tail, Two_Product, and Two_Two_Diff.

Referenced by insphere().

◆ insphereexact()

double blender::robust_pred::insphereexact	(	const double *	pa,
		const double *	pb,
		const double *	pc,
		const double *	pd,
		const double *	pe )

static

Definition at line 1932 of file math_boolean.cc.

References fast_expansion_sum_zeroelim(), i, INEXACT, scale_expansion_zeroelim(), Two_Product, and Two_Two_Diff.

Referenced by insphereadapt().

◆ inspherefast()

double blender::robust_pred::inspherefast	(	const double *	pa,
		const double *	pb,
		const double *	pc,
		const double *	pd,
		const double *	pe )

inspherefast() Approximate 3D insphere test. Non-robust. insphere() Adaptive exact 3D insphere test. Robust.

         Return a positive value if the point pe lies inside the
         sphere passing through pa, pb, pc, and pd; a negative value
         if it lies outside; and zero if the five points are
         co-spherical.  The points pa, pb, pc, and pd must be ordered
         so that they have a positive orientation (as defined by
         orient3d()), or the sign of the result will be reversed.

The second uses exact arithmetic to ensure a correct answer. The result returned is the determinant of a matrix. In insphere() only, this determinant is computed adaptively, in the sense that exact arithmetic is used only to the degree it is needed to ensure that the returned value has the correct sign. Hence, insphere() is usually quite fast, but will run more slowly when the input points are co-spherical or nearly so.

Definition at line 1888 of file math_boolean.cc.

Referenced by blender::insphere_fast().

◆ orient2d()

double blender::robust_pred::orient2d	(	const double *	pa,
		const double *	pb,
		const double *	pc )

Definition at line 710 of file math_boolean.cc.

References ccwerrboundA, and orient2dadapt().

Referenced by blender::orient2d().

◆ orient2dadapt()

double blender::robust_pred::orient2dadapt	(	const double *	pa,
		const double *	pb,
		const double *	pc,
		double	detsum )

static

Definition at line 633 of file math_boolean.cc.

References Absolute, B, ccwerrboundB, ccwerrboundC, D, estimate(), fast_expansion_sum_zeroelim(), INEXACT, resulterrbound, Two_Diff_Tail, Two_Product, and Two_Two_Diff.

Referenced by orient2d().

◆ orient2dfast()

double blender::robust_pred::orient2dfast	(	const double *	pa,
		const double *	pb,
		const double *	pc )

orient2dfast() Approximate 2D orientation test. Non-robust. orient2d() Adaptive exact 2D orientation test. Robust. Return a positive value if the points pa, pb, and pc occur in counterclockwise order; a negative value if they occur in clockwise order; and zero if they are co-linear. The result is also a rough approximation of twice the signed area of the triangle defined by the three points.

The second uses exact arithmetic to ensure a correct answer. The result returned is the determinant of a matrix. In orient2d() only, this determinant is computed adaptively, in the sense that exact arithmetic is used only to the degree it is needed to ensure that the returned value has the correct sign. Hence, orient2d() is usually quite fast, but will run more slowly when the input points are co-linear or nearly so.

Definition at line 622 of file math_boolean.cc.

Referenced by blender::orient2d_fast().

◆ orient3d()

double blender::robust_pred::orient3d	(	const double *	pa,
		const double *	pb,
		const double *	pc,
		const double *	pd )

Definition at line 1219 of file math_boolean.cc.

References Absolute, o3derrboundA, and orient3dadapt().

Referenced by blender::orient3d().

◆ orient3dadapt()

double blender::robust_pred::orient3dadapt	(	const double *	pa,
		const double *	pb,
		const double *	pc,
		const double *	pd,
		double	permanent )

static

Note: since this code comes from an external source, prefer not to break it up to fix this clang-tidy warning.

Definition at line 790 of file math_boolean.cc.

References Absolute, estimate(), fast_expansion_sum_zeroelim(), INEXACT, o3derrboundB, o3derrboundC, resulterrbound, scale_expansion_zeroelim(), Two_Diff_Tail, Two_One_Product, Two_Product, Two_Two_Diff, v, and w().

Referenced by orient3d().

◆ orient3dfast()

double blender::robust_pred::orient3dfast	(	const double *	pa,
		const double *	pb,
		const double *	pc,
		const double *	pd )

orient3dfast() Approximate 3D orientation test. Non-robust. orient3d() Adaptive exact 3D orientation test. Robust.

          Return a positive value if the point pd lies below the
          plane passing through pa, pb, and pc; "below" is defined so
          that pa, pb, and pc appear in counterclockwise order when
          viewed from above the plane.  Returns a negative value if
          pd lies above the plane.  Returns zero if the points are
          co-planar.  The result is also a rough approximation of six
          times the signed volume of the tetrahedron defined by the
          four points.

The second uses exact arithmetic to ensure a correct answer. The result returned is the determinant of a matrix. In orient3d() only, this determinant is computed adaptively, in the sense that exact arithmetic is used only to the degree it is needed to ensure that the returned value has the correct sign. Hence, orient3d() is usually quite fast, but will run more slowly when the input points are co-planar or nearly so.

Definition at line 765 of file math_boolean.cc.

Referenced by blender::orient3d_fast().

◆ scale_expansion_zeroelim()

int blender::robust_pred::scale_expansion_zeroelim	(	int	elen,
		const double *	e,
		double	b,
		double *	h )

static

Definition at line 552 of file math_boolean.cc.

References b, e, Fast_Two_Sum, INEXACT, Split, sum(), Two_Product_Presplit, and Two_Sum.

Referenced by incircleadapt(), insphereadapt(), insphereexact(), and orient3dadapt().

Variable Documentation

◆ ccwerrboundA

blender::robust_pred::ccwerrboundA = (3.0 + 16.0 * epsilon) * epsilon

static

Definition at line 394 of file math_boolean.cc.

Referenced by orient2d().

◆ ccwerrboundB

blender::robust_pred::ccwerrboundB = (2.0 + 12.0 * epsilon) * epsilon

static

Definition at line 394 of file math_boolean.cc.

Referenced by orient2dadapt().

◆ ccwerrboundC

blender::robust_pred::ccwerrboundC = (9.0 + 64.0 * epsilon) * epsilon * epsilon

static

Definition at line 394 of file math_boolean.cc.

Referenced by orient2dadapt().

◆ epsilon

double blender::robust_pred::epsilon

static

Definition at line 391 of file math_boolean.cc.

◆ iccerrboundA

blender::robust_pred::iccerrboundA = (10.0 + 96.0 * epsilon) * epsilon

static

Definition at line 396 of file math_boolean.cc.

Referenced by incircle().

◆ iccerrboundB

blender::robust_pred::iccerrboundB = (4.0 + 48.0 * epsilon) * epsilon

static

Definition at line 396 of file math_boolean.cc.

Referenced by incircleadapt().

◆ iccerrboundC

blender::robust_pred::iccerrboundC = (44.0 + 576.0 * epsilon) * epsilon * epsilon

static

Definition at line 396 of file math_boolean.cc.

Referenced by incircleadapt().

◆ init_caller

RobustInitCaller blender::robust_pred::init_caller

static

Definition at line 115 of file math_boolean.cc.

◆ isperrboundA

blender::robust_pred::isperrboundA = (16.0 + 224.0 * epsilon) * epsilon

static

Definition at line 397 of file math_boolean.cc.

Referenced by insphere().

◆ isperrboundB

blender::robust_pred::isperrboundB = (5.0 + 72.0 * epsilon) * epsilon

static

Definition at line 397 of file math_boolean.cc.

Referenced by insphereadapt().

◆ isperrboundC

blender::robust_pred::isperrboundC = (71.0 + 1408.0 * epsilon) * epsilon * epsilon

static

Definition at line 397 of file math_boolean.cc.

Referenced by insphereadapt().

◆ o3derrboundA

blender::robust_pred::o3derrboundA = (7.0 + 56.0 * epsilon) * epsilon

static

Definition at line 395 of file math_boolean.cc.

Referenced by orient3d().

◆ o3derrboundB

blender::robust_pred::o3derrboundB = (3.0 + 28.0 * epsilon) * epsilon

static

Definition at line 395 of file math_boolean.cc.

Referenced by orient3dadapt().

◆ o3derrboundC

blender::robust_pred::o3derrboundC = (26.0 + 288.0 * epsilon) * epsilon * epsilon

static

Definition at line 395 of file math_boolean.cc.

Referenced by orient3dadapt().

◆ resulterrbound

blender::robust_pred::resulterrbound = (3.0 + 8.0 * epsilon) * epsilon

static

exactinit() Initialize the variables used for exact arithmetic.

epsilon' is the largest power of two such that 1.0 + epsilon = 1.0 in floating-point arithmetic. epsilon' bounds the relative round-off error. It is used for floating-point error analysis.

`splitter' is used to split floating-point numbers into two half-length significant for exact multiplication.

I imagine that a highly optimizing compiler might be too smart for its own good, and somehow cause this routine to fail, if it pretends that floating-point arithmetic is too much like real arithmetic.

Don't change this routine unless you fully understand it. */ void exactinit() { double half; double check, lastcheck; int every_other;

every_other = 1; half = 0.5; epsilon = 1.0; splitter = 1.0; check = 1.0; /* Repeatedly divide `epsilon' by two until it is too small to add to one without causing round-off. (Also check if the sum is equal to the previous sum, for machines that round up instead of using exact rounding. Not that this library will work on such machines anyway. */ do { lastcheck = check; epsilon *= half; if (every_other) { splitter *= 2.0; } every_other = !every_other; check = 1.0 + epsilon; } while (!ELEM(check, 1.0, lastcheck)); splitter += 1.0;

/* Error bounds for orientation and incircle tests.

Definition at line 393 of file math_boolean.cc.

Referenced by incircleadapt(), insphereadapt(), orient2dadapt(), and orient3dadapt().

◆ splitter

double blender::robust_pred::splitter

static

Definition at line 390 of file math_boolean.cc.

Classes

Functions

Variables

Detailed Description

Function Documentation

◆ estimate()

◆ exactinit()

◆ fast_expansion_sum_zeroelim()

◆ incircle()

◆ incircleadapt()

◆ incirclefast()

◆ insphere()

◆ insphereadapt()

◆ insphereexact()

◆ inspherefast()

◆ orient2d()

◆ orient2dadapt()

◆ orient2dfast()

◆ orient3d()

◆ orient3dadapt()

◆ orient3dfast()

◆ scale_expansion_zeroelim()

Variable Documentation

◆ ccwerrboundA

◆ ccwerrboundB

◆ ccwerrboundC

◆ epsilon

◆ iccerrboundA

◆ iccerrboundB

◆ iccerrboundC

◆ init_caller

◆ isperrboundA

◆ isperrboundB

◆ isperrboundC

◆ o3derrboundA

◆ o3derrboundB

◆ o3derrboundC

◆ resulterrbound

◆ splitter