math_boolean.cc File Reference

#include "BLI_math_boolean.hh"
#include "BLI_math_mpq.hh"
#include "BLI_math_vector_types.hh"
#include "BLI_utildefines.h"

Go to the source code of this file.

Classes
class	blender::robust_pred::RobustInitCaller

Namespaces
namespace	blender
namespace	blender::robust_pred

Macros
#define	INEXACT   /* Nothing */
#define	Absolute(a)
#define	Fast_Two_Sum_Tail(a, b, x, y)
#define	Fast_Two_Sum(a, b, x, y)
#define	Fast_Two_Diff_Tail(a, b, x, y)
#define	Fast_Two_Diff(a, b, x, y)
#define	Two_Sum_Tail(a, b, x, y)
#define	Two_Sum(a, b, x, y)
#define	Two_Diff_Tail(a, b, x, y)
#define	Two_Diff(a, b, x, y)
#define	Split(a, ahi, alo)
#define	Two_Product_Tail(a, b, x, y)
#define	Two_Product(a, b, x, y)
#define	Two_Product_Presplit(a, b, bhi, blo, x, y)
#define	Two_Product_2Presplit(a, ahi, alo, b, bhi, blo, x, y)
#define	Square_Tail(a, x, y)
#define	Square(a, x, y)
#define	Two_One_Sum(a1, a0, b, x2, x1, x0)
#define	Two_One_Diff(a1, a0, b, x2, x1, x0)
#define	Two_Two_Sum(a1, a0, b1, b0, x3, x2, x1, x0)
#define	Two_Two_Diff(a1, a0, b1, b0, x3, x2, x1, x0)
#define	Four_One_Sum(a3, a2, a1, a0, b, x4, x3, x2, x1, x0)
#define	Four_Two_Sum(a3, a2, a1, a0, b1, b0, x5, x4, x3, x2, x1, x0)
#define	Four_Four_Sum(a3, a2, a1, a0, b4, b3, b1, b0, x7, x6, x5, x4, x3, x2, x1, x0)
#define	Eight_One_Sum(a7, a6, a5, a4, a3, a2, a1, a0, b, x8, x7, x6, x5, x4, x3, x2, x1, x0)
#define	Eight_Two_Sum(a7, a6, a5, a4, a3, a2, a1, a0, b1, b0, x9, x8, x7, x6, x5, x4, x3, x2, x1, x0)
#define	Eight_Four_Sum(a7, a6, a5, a4, a3, a2, a1, a0, b4, b3, b1, b0, x11, x10, x9, x8, x7, x6, x5, x4, x3, x2, x1, x0)
#define	Two_One_Product(a1, a0, b, x3, x2, x1, x0)
#define	Four_One_Product(a3, a2, a1, a0, b, x7, x6, x5, x4, x3, x2, x1, x0)
#define	Two_Two_Product(a1, a0, b1, b0, x7, x6, x5, x4, x3, x2, x1, x0)
#define	Two_Square(a1, a0, x5, x4, x3, x2, x1, x0)

Functions
void	blender::robust_pred::exactinit ()
double	blender::robust_pred::orient2dfast (const double *pa, const double *pb, const double *pc)
double	blender::robust_pred::orient2d (const double *pa, const double *pb, const double *pc)
double	blender::robust_pred::orient3dfast (const double *pa, const double *pb, const double *pc, const double *pd)
double	blender::robust_pred::orient3d (const double *pa, const double *pb, const double *pc, const double *pd)
double	blender::robust_pred::incirclefast (const double *pa, const double *pb, const double *pc, const double *pd)
double	blender::robust_pred::incircle (const double *pa, const double *pb, const double *pc, const double *pd)
double	blender::robust_pred::inspherefast (const double *pa, const double *pb, const double *pc, const double *pd, const double *pe)
double	blender::robust_pred::insphere (const double *pa, const double *pb, const double *pc, const double *pd, const double *pe)
static int	blender::robust_pred::fast_expansion_sum_zeroelim (int elen, const double *e, int flen, const double *f, double *h)
static int	blender::robust_pred::scale_expansion_zeroelim (int elen, const double *e, double b, double *h)
static double	blender::robust_pred::estimate (int elen, const double *e)
static double	blender::robust_pred::orient2dadapt (const double *pa, const double *pb, const double *pc, double detsum)
static double	blender::robust_pred::orient3dadapt (const double *pa, const double *pb, const double *pc, const double *pd, double permanent)
static double	blender::robust_pred::incircleadapt (const double *pa, const double *pb, const double *pc, const double *pd, double permanent)
static double	blender::robust_pred::insphereexact (const double *pa, const double *pb, const double *pc, const double *pd, const double *pe)
static double	blender::robust_pred::insphereadapt (const double *pa, const double *pb, const double *pc, const double *pd, const double *pe, double permanent)
static int	blender::sgn (double x)
int	blender::orient2d (const double2 &a, const double2 &b, const double2 &c)
int	blender::orient2d_fast (const double2 &a, const double2 &b, const double2 &c)
int	blender::incircle (const double2 &a, const double2 &b, const double2 &c, const double2 &d)
int	blender::incircle_fast (const double2 &a, const double2 &b, const double2 &c, const double2 &d)
int	blender::orient3d (const double3 &a, const double3 &b, const double3 &c, const double3 &d)
int	blender::orient3d_fast (const double3 &a, const double3 &b, const double3 &c, const double3 &d)
int	blender::insphere (const double3 &a, const double3 &b, const double3 &c, const double3 &d, const double3 &e)
int	blender::insphere_fast (const double3 &a, const double3 &b, const double3 &c, const double3 &d, const double3 &e)

Variables
static RobustInitCaller	blender::robust_pred::init_caller
static double	blender::robust_pred::splitter
static double	blender::robust_pred::epsilon
static double	blender::robust_pred::resulterrbound
static double	blender::robust_pred::ccwerrboundA
static double	blender::robust_pred::ccwerrboundB
static double	blender::robust_pred::ccwerrboundC
static double	blender::robust_pred::o3derrboundA
static double	blender::robust_pred::o3derrboundB
static double	blender::robust_pred::o3derrboundC
static double	blender::robust_pred::iccerrboundA
static double	blender::robust_pred::iccerrboundB
static double	blender::robust_pred::iccerrboundC
static double	blender::robust_pred::isperrboundA
static double	blender::robust_pred::isperrboundB
static double	blender::robust_pred::isperrboundC

Macro Definition Documentation

Absolute

#define Absolute

(

a

)

Value:

((a) >= 0.0 ? (a) : -(a))

Definition at line 174 of file math_boolean.cc.

Referenced by blender::robust_pred::incircle(), blender::robust_pred::incircleadapt(), blender::robust_pred::insphere(), blender::robust_pred::insphereadapt(), blender::robust_pred::orient2dadapt(), blender::robust_pred::orient3d(), and blender::robust_pred::orient3dadapt().

Eight_Four_Sum

#define Eight_Four_Sum	(		a7,
			a6,
			a5,
			a4,
			a3,
			a2,
			a1,
			a0,
			b4,
			b3,
			b1,
			b0,
			x11,
			x10,
			x9,
			x8,
			x7,
			x6,
			x5,
			x4,
			x3,
			x2,
			x1,
			x0 )

Value:

Eight_Two_Sum(a7, a6, a5, a4, a3, a2, a1, a0, b1, b0, _l, _6, _5, _4, _3, _2, _1, _0, x1, x0); \
Eight_Two_Sum(_l, _6, _5, _4, _3, _2, _1, _0, b4, b3, x11, x10, x9, x8, x7, x6, x5, x4, x3, x2)

Definition at line 309 of file math_boolean.cc.

Eight_One_Sum

#define Eight_One_Sum	(		a7,
			a6,
			a5,
			a4,
			a3,
			a2,
			a1,
			a0,
			b,
			x8,
			x7,
			x6,
			x5,
			x4,
			x3,
			x2,
			x1,
			x0 )

Value:

Four_One_Sum(a3, a2, a1, a0, b, _j, x3, x2, x1, x0); \
Four_One_Sum(a7, a6, a5, a4, _j, x8, x7, x6, x5, x4)

Definition at line 300 of file math_boolean.cc.

Eight_Two_Sum

#define Eight_Two_Sum	(		a7,
			a6,
			a5,
			a4,
			a3,
			a2,
			a1,
			a0,
			b1,
			b0,
			x9,
			x8,
			x7,
			x6,
			x5,
			x4,
			x3,
			x2,
			x1,
			x0 )

Value:

Eight_One_Sum(a7, a6, a5, a4, a3, a2, a1, a0, b0, _k, _6, _5, _4, _3, _2, _1, _0, x0); \
Eight_One_Sum(_k, _6, _5, _4, _3, _2, _1, _0, b1, x9, x8, x7, x6, x5, x4, x3, x2, x1)

Definition at line 304 of file math_boolean.cc.

Fast_Two_Diff

#define Fast_Two_Diff	(		a,
			b,
			x,
			y )

Value:

x = double(a - b); \
Fast_Two_Diff_Tail(a, b, x, y)

Definition at line 203 of file math_boolean.cc.

Fast_Two_Diff_Tail

#define Fast_Two_Diff_Tail	(		a,
			b,
			x,
			y )

Value:

bvirt = a - x; \
y = bvirt - b

Definition at line 199 of file math_boolean.cc.

Fast_Two_Sum

#define Fast_Two_Sum	(		a,
			b,
			x,
			y )

Value:

x = double(a + b); \
Fast_Two_Sum_Tail(a, b, x, y)

Definition at line 195 of file math_boolean.cc.

Referenced by blender::robust_pred::fast_expansion_sum_zeroelim(), and blender::robust_pred::scale_expansion_zeroelim().

Fast_Two_Sum_Tail

#define Fast_Two_Sum_Tail	(		a,
			b,
			x,
			y )

Value:

bvirt = x - a; \
y = b - bvirt

Definition at line 191 of file math_boolean.cc.

Four_Four_Sum

#define Four_Four_Sum	(		a3,
			a2,
			a1,
			a0,
			b4,
			b3,
			b1,
			b0,
			x7,
			x6,
			x5,
			x4,
			x3,
			x2,
			x1,
			x0 )

Value:

Four_Two_Sum(a3, a2, a1, a0, b1, b0, _l, _2, _1, _0, x1, x0); \
Four_Two_Sum(_l, _2, _1, _0, b4, b3, x7, x6, x5, x4, x3, x2)

Definition at line 296 of file math_boolean.cc.

Four_One_Product

#define Four_One_Product	(		a3,
			a2,
			a1,
			a0,
			b,
			x7,
			x6,
			x5,
			x4,
			x3,
			x2,
			x1,
			x0 )

Value:

Split(b, bhi, blo); \
Two_Product_Presplit(a0, b, bhi, blo, _i, x0); \
Two_Product_Presplit(a1, b, bhi, blo, _j, _0); \
Two_Sum(_i, _0, _k, x1); \
Fast_Two_Sum(_j, _k, _i, x2); \
Two_Product_Presplit(a2, b, bhi, blo, _j, _0); \
Two_Sum(_i, _0, _k, x3); \
Fast_Two_Sum(_j, _k, _i, x4); \
Two_Product_Presplit(a3, b, bhi, blo, _j, _0); \
Two_Sum(_i, _0, _k, x5); \
Fast_Two_Sum(_j, _k, x7, x6)

Definition at line 343 of file math_boolean.cc.

Four_One_Sum

#define Four_One_Sum	(		a3,
			a2,
			a1,
			a0,
			b,
			x4,
			x3,
			x2,
			x1,
			x0 )

Value:

Two_One_Sum(a1, a0, b, _j, x1, x0); \
Two_One_Sum(a3, a2, _j, x4, x3, x2)

Definition at line 288 of file math_boolean.cc.

Four_Two_Sum

#define Four_Two_Sum	(		a3,
			a2,
			a1,
			a0,
			b1,
			b0,
			x5,
			x4,
			x3,
			x2,
			x1,
			x0 )

Value:

Four_One_Sum(a3, a2, a1, a0, b0, _k, _2, _1, _0, x0); \
Four_One_Sum(_k, _2, _1, _0, b1, x5, x4, x3, x2, x1)

Definition at line 292 of file math_boolean.cc.

INEXACT

#define INEXACT   /* Nothing */

Definition at line 164 of file math_boolean.cc.

Referenced by blender::robust_pred::fast_expansion_sum_zeroelim(), blender::robust_pred::incircleadapt(), blender::robust_pred::insphereadapt(), blender::robust_pred::insphereexact(), blender::robust_pred::orient2dadapt(), blender::robust_pred::orient3dadapt(), and blender::robust_pred::scale_expansion_zeroelim().

Split

#define Split	(		a,
			ahi,
			alo )

Value:

c = double(splitter * a); \
abig = double(c - a); \
ahi = c - abig; \
alo = a - ahi

Definition at line 229 of file math_boolean.cc.

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

Square

#define Square	(		a,
			x,
			y )

Value:

x = double(a * a); \
Square_Tail(a, x, y)

Definition at line 268 of file math_boolean.cc.

Referenced by blender::robust_pred::incircleadapt(), libmv::MeanAndVarianceAlongRows(), libmv::SampsonDistance(), libmv::SelectKeyframesBasedOnGRICAndVariance(), and libmv::SymmetricEpipolarDistance().

Square_Tail

#define Square_Tail	(		a,
			x,
			y )

Value:

Split(a, ahi, alo); \
err1 = x - (ahi * ahi); \
err3 = err1 - ((ahi + ahi) * alo); \
y = (alo * alo) - err3

Definition at line 262 of file math_boolean.cc.

Two_Diff

#define Two_Diff	(		a,
			b,
			x,
			y )

Value:

x = double(a - b); \
Two_Diff_Tail(a, b, x, y)

Definition at line 225 of file math_boolean.cc.

Two_Diff_Tail

#define Two_Diff_Tail	(		a,
			b,
			x,
			y )

Value:

bvirt = double(a - x); \
avirt = x + bvirt; \
bround = bvirt - b; \
around = a - avirt; \
y = around + bround

Definition at line 218 of file math_boolean.cc.

Referenced by blender::robust_pred::incircleadapt(), blender::robust_pred::insphereadapt(), blender::robust_pred::orient2dadapt(), and blender::robust_pred::orient3dadapt().

Two_One_Diff

#define Two_One_Diff	(		a1,
			a0,
			b,
			x2,
			x1,
			x0 )

Value:

Two_Diff(a0, b, _i, x0); \
Two_Sum(a1, _i, x2, x1)

Definition at line 276 of file math_boolean.cc.

Two_One_Product

#define Two_One_Product	(		a1,
			a0,
			b,
			x3,
			x2,
			x1,
			x0 )

Value:

Split(b, bhi, blo); \
Two_Product_Presplit(a0, b, bhi, blo, _i, x0); \
Two_Product_Presplit(a1, b, bhi, blo, _j, _0); \
Two_Sum(_i, _0, _k, x1); \
Fast_Two_Sum(_j, _k, x3, x2)

Definition at line 336 of file math_boolean.cc.

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

Two_One_Sum

#define Two_One_Sum	(		a1,
			a0,
			b,
			x2,
			x1,
			x0 )

Value:

Two_Sum(a0, b, _i, x0); \
Two_Sum(a1, _i, x2, x1)

Definition at line 272 of file math_boolean.cc.

Two_Product

#define Two_Product	(		a,
			b,
			x,
			y )

Value:

x = double(a * b); \
Two_Product_Tail(a, b, x, y)

Definition at line 243 of file math_boolean.cc.

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

Two_Product_2Presplit

#define Two_Product_2Presplit	(		a,
			ahi,
			alo,
			b,
			bhi,
			blo,
			x,
			y )

Value:

x = double(a * b); \
err1 = x - (ahi * bhi); \
err2 = err1 - (alo * bhi); \
err3 = err2 - (ahi * blo); \
y = (alo * blo) - err3

Definition at line 255 of file math_boolean.cc.

Two_Product_Presplit

#define Two_Product_Presplit	(		a,
			b,
			bhi,
			blo,
			x,
			y )

Value:

x = double(a * b); \
Split(a, ahi, alo); \
err1 = x - (ahi * bhi); \
err2 = err1 - (alo * bhi); \
err3 = err2 - (ahi * blo); \
y = (alo * blo) - err3

Definition at line 247 of file math_boolean.cc.

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

Two_Product_Tail

#define Two_Product_Tail	(		a,
			b,
			x,
			y )

Value:

Split(a, ahi, alo); \
Split(b, bhi, blo); \
err1 = x - (ahi * bhi); \
err2 = err1 - (alo * bhi); \
err3 = err2 - (ahi * blo); \
y = (alo * blo) - err3

Definition at line 235 of file math_boolean.cc.

Two_Square

#define Two_Square	(		a1,
			a0,
			x5,
			x4,
			x3,
			x2,
			x1,
			x0 )

Value:

Square(a0, _j, x0); \
_0 = a0 + a0; \
Two_Product(a1, _0, _k, _1); \
Two_One_Sum(_k, _1, _j, _l, _2, x1); \
Square(a1, _j, _1); \
Two_Two_Sum(_j, _1, _l, _2, x5, x4, x3, x2)

Definition at line 382 of file math_boolean.cc.

Two_Sum

#define Two_Sum	(		a,
			b,
			x,
			y )

Value:

x = double(a + b); \
Two_Sum_Tail(a, b, x, y)

Definition at line 214 of file math_boolean.cc.

Referenced by blender::robust_pred::fast_expansion_sum_zeroelim(), and blender::robust_pred::scale_expansion_zeroelim().

Two_Sum_Tail

#define Two_Sum_Tail	(		a,
			b,
			x,
			y )

Value:

bvirt = double(x - a); \
avirt = x - bvirt; \
bround = b - bvirt; \
around = a - avirt; \
y = around + bround

Definition at line 207 of file math_boolean.cc.

Two_Two_Diff

#define Two_Two_Diff	(		a1,
			a0,
			b1,
			b0,
			x3,
			x2,
			x1,
			x0 )

Value:

Two_One_Diff(a1, a0, b0, _j, _0, x0); \
Two_One_Diff(_j, _0, b1, x3, x2, x1)

Definition at line 284 of file math_boolean.cc.

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

Two_Two_Product

#define Two_Two_Product	(		a1,
			a0,
			b1,
			b0,
			x7,
			x6,
			x5,
			x4,
			x3,
			x2,
			x1,
			x0 )

Value:

Split(a0, a0hi, a0lo); \
Split(b0, bhi, blo); \
Two_Product_2Presplit(a0, a0hi, a0lo, b0, bhi, blo, _i, x0); \
Split(a1, a1hi, a1lo); \
Two_Product_2Presplit(a1, a1hi, a1lo, b0, bhi, blo, _j, _0); \
Two_Sum(_i, _0, _k, _1); \
Fast_Two_Sum(_j, _k, _l, _2); \
Split(b1, bhi, blo); \
Two_Product_2Presplit(a0, a0hi, a0lo, b1, bhi, blo, _i, _0); \
Two_Sum(_1, _0, _k, x1); \
Two_Sum(_2, _k, _j, _1); \
Two_Sum(_l, _j, _m, _2); \
Two_Product_2Presplit(a1, a1hi, a1lo, b1, bhi, blo, _j, _0); \
Two_Sum(_i, _0, _n, _0); \
Two_Sum(_1, _0, _i, x2); \
Two_Sum(_2, _i, _k, _1); \
Two_Sum(_m, _k, _l, _2); \
Two_Sum(_j, _n, _k, _0); \
Two_Sum(_1, _0, _j, x3); \
Two_Sum(_2, _j, _i, _1); \
Two_Sum(_l, _i, _m, _2); \
Two_Sum(_1, _k, _i, x4); \
Two_Sum(_2, _i, _k, x5); \
Two_Sum(_m, _k, x7, x6)

Definition at line 356 of file math_boolean.cc.

Two_Two_Sum

#define Two_Two_Sum	(		a1,
			a0,
			b1,
			b0,
			x3,
			x2,
			x1,
			x0 )

Value:

Two_One_Sum(a1, a0, b0, _j, _0, x0); \
Two_One_Sum(_j, _0, b1, x3, x2, x1)

Definition at line 280 of file math_boolean.cc.

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