Blender  V3.3
Classes | Functions | Variables
blender::robust_pred Namespace Reference

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
 
static double ccwerrboundA
 
static double ccwerrboundB
 
static double ccwerrboundC
 
static double o3derrboundA
 
static double o3derrboundB
 
static double o3derrboundC
 
static double iccerrboundA
 
static double iccerrboundB
 
static double iccerrboundC
 
static double isperrboundA
 
static double isperrboundB
 
static double isperrboundC
 

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()

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

Definition at line 585 of file math_boolean.cc.

References e.

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

◆ exactinit()

void blender::robust_pred::exactinit ( )

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.

Definition at line 416 of file math_boolean.cc.

References ccwerrboundA, ccwerrboundB, ccwerrboundC, ELEM, epsilon, iccerrboundA, iccerrboundB, iccerrboundC, isperrboundA, isperrboundB, isperrboundC, o3derrboundA, o3derrboundB, o3derrboundC, resulterrbound, and splitter.

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

◆ fast_expansion_sum_zeroelim()

static 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 465 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 1819 of file math_boolean.cc.

References Absolute, iccerrboundA, and incircleadapt().

Referenced by blender::incircle().

◆ incircleadapt()

static 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 1297 of file math_boolean.cc.

References Absolute, Freestyle::c, double(), 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 1269 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 2351 of file math_boolean.cc.

References Absolute, insphereadapt(), and isperrboundA.

Referenced by blender::insphere().

◆ insphereadapt()

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

◆ insphereexact()

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

◆ 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 1879 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 703 of file math_boolean.cc.

References ccwerrboundA, and orient2dadapt().

Referenced by blender::orient2d().

◆ orient2dadapt()

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

◆ 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 615 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 1211 of file math_boolean.cc.

References Absolute, o3derrboundA, and orient3dadapt().

Referenced by blender::orient3d().

◆ orient3dadapt()

static 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 783 of file math_boolean.cc.

References Absolute, Freestyle::c, double(), 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 758 of file math_boolean.cc.

Referenced by blender::orient3d_fast().

◆ scale_expansion_zeroelim()

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

Variable Documentation

◆ ccwerrboundA

double blender::robust_pred::ccwerrboundA
static

Definition at line 394 of file math_boolean.cc.

Referenced by exactinit(), and orient2d().

◆ ccwerrboundB

double blender::robust_pred::ccwerrboundB
static

Definition at line 394 of file math_boolean.cc.

Referenced by exactinit(), and orient2dadapt().

◆ ccwerrboundC

double blender::robust_pred::ccwerrboundC
static

Definition at line 394 of file math_boolean.cc.

Referenced by exactinit(), and orient2dadapt().

◆ epsilon

double blender::robust_pred::epsilon
static

Definition at line 391 of file math_boolean.cc.

Referenced by above(), Freestyle::SweepLine< T, Point >::add(), blender::math::almost_equal_relative(), BKE_bmbvh_new_ex(), BKE_gpencil_stroke_simplify_adaptive(), BKE_pchan_bbone_handles_compute(), BLI_bvhtree_new(), BLI_newton3d_solve(), BLI_quadric_optimize(), bm_isect_tri_tri(), bm_vert_pair_best_face_get(), BMBVH_EdgeVisible(), Freestyle::ViewMapBuilder::BuildViewMap(), bvhtree_build_from_cloth(), bvhtree_build_from_mvert(), bvhtree_CreatePyObject(), bvhtree_from_editmesh_edges(), bvhtree_from_editmesh_edges_create_tree(), bvhtree_from_editmesh_edges_ex(), bvhtree_from_editmesh_looptri(), bvhtree_from_editmesh_looptri_create_tree(), bvhtree_from_editmesh_looptri_ex(), bvhtree_from_editmesh_verts(), bvhtree_from_editmesh_verts_create_tree(), bvhtree_from_editmesh_verts_ex(), bvhtree_from_mesh_edges_create_tree(), bvhtree_from_mesh_edges_ex(), bvhtree_from_mesh_faces_create_tree(), bvhtree_from_mesh_looptri_create_tree(), bvhtree_from_mesh_looptri_ex(), bvhtree_from_mesh_verts_create_tree(), bvhtree_from_mesh_verts_ex(), C_BVHTree_FromBMesh(), C_BVHTree_FromObject(), C_BVHTree_FromPolygons(), blender::bke::curves::poly::calculate_normals_minimum(), calculate_normals_minimum(), blender::bke::curves::poly::calculate_normals_z_up(), calculate_normals_z_up(), blender::bke::curves::poly::calculate_tangents(), blender::meshintersect::CDT_state< T >::CDT_state(), clamp_nonzero(), cloth_selfcollision(), Freestyle::computeCumulativeVisibility(), Freestyle::ViewMapBuilder::ComputeCumulativeVisibility(), Freestyle::computeDetailedVisibility(), Freestyle::ViewMapBuilder::ComputeDetailedVisibility(), Freestyle::ViewMapBuilder::ComputeEdgesVisibility(), Freestyle::ViewMapBuilder::ComputeFastRayCastingVisibility(), Freestyle::computeFastVisibility(), Freestyle::ViewMapBuilder::ComputeIntersections(), IK_QJacobian::ComputeNullProjection(), Freestyle::ViewMapBuilder::ComputeRayCastingVisibility(), Freestyle::ViewMapBuilder::ComputeSweepLineIntersections(), Freestyle::ViewMapBuilder::ComputeVeryFastRayCastingVisibility(), Freestyle::computeVeryFastVisibility(), Freestyle::computeVisibility(), Freestyle::CulledOccluderSource::cullViewEdges(), Freestyle::ViewMapBuilder::CullViewEdges(), blender::bke::curves::poly::direction_bisect(), ED_vgroup_parray_remove_zero(), ED_view3d_quat_to_axis_view(), ED_view3d_quat_to_axis_view_and_reset_quat(), EEVEE_volumes_cache_object_add(), btDeformableLinearElasticityForce::elasticEnergyDensity(), exactinit(), Freestyle::GridHelpers::expandProscenium(), fill_crossdata_for_intersect(), Freestyle::findOccludee(), Freestyle::ViewMapBuilder::FindOccludee(), btDeformableLinearElasticityForce::firstPiola(), form_factor_visible_quad(), blender::nodes::node_fn_compare_cc::get_multi_function(), get_next_crossing_from_edge(), Freestyle::GeomUtils::intersect2dSeg2dSegParametric(), Freestyle::GeomUtils::intersectRayPlane(), Freestyle::GeomUtils::intersectRayTriangle(), invert_m3_ex(), invert_m3_m3_ex(), is_in_quadrant_v3(), isect_axial_line_segment_tri_v3(), isect_line_line_epsilon_v3(), isect_line_line_strict_v3(), isect_line_line_v3(), isect_line_segment_tri_epsilon_v3(), isect_ray_ray_epsilon_v3(), isect_ray_tri_epsilon_v3(), isect_ray_tri_v3(), knife_bvh_init(), Freestyle::less_SVertex2D::less_SVertex2D(), line_point_factor_v2_ex(), line_point_factor_v3_ex(), Freestyle::less_SVertex2D::operator()(), blender::compositor::DisplaceOperation::pixel_transform(), blender::compositor::MapUVOperation::pixel_transform(), position_tail_on_spline(), Freestyle::SweepLine< T, Point >::process(), pseudoinverse_m3_m3(), pseudoinverse_m4_m4(), quadric_to_tensor_m3_inverse(), ray_point_factor_v3_ex(), Freestyle::Geometry::Polygon3r::rayIntersect(), target_project_edge(), target_project_solve_point_tri(), target_project_tri_correct(), TEST(), Vector_richcmpr(), and vgroup_clean_subset().

◆ iccerrboundA

double blender::robust_pred::iccerrboundA
static

Definition at line 396 of file math_boolean.cc.

Referenced by exactinit(), and incircle().

◆ iccerrboundB

double blender::robust_pred::iccerrboundB
static

Definition at line 396 of file math_boolean.cc.

Referenced by exactinit(), and incircleadapt().

◆ iccerrboundC

double blender::robust_pred::iccerrboundC
static

Definition at line 396 of file math_boolean.cc.

Referenced by exactinit(), and incircleadapt().

◆ init_caller

RobustInitCaller blender::robust_pred::init_caller
static

Definition at line 115 of file math_boolean.cc.

◆ isperrboundA

double blender::robust_pred::isperrboundA
static

Definition at line 397 of file math_boolean.cc.

Referenced by exactinit(), and insphere().

◆ isperrboundB

double blender::robust_pred::isperrboundB
static

Definition at line 397 of file math_boolean.cc.

Referenced by exactinit(), and insphereadapt().

◆ isperrboundC

double blender::robust_pred::isperrboundC
static

Definition at line 397 of file math_boolean.cc.

Referenced by exactinit(), and insphereadapt().

◆ o3derrboundA

double blender::robust_pred::o3derrboundA
static

Definition at line 395 of file math_boolean.cc.

Referenced by exactinit(), and orient3d().

◆ o3derrboundB

double blender::robust_pred::o3derrboundB
static

Definition at line 395 of file math_boolean.cc.

Referenced by exactinit(), and orient3dadapt().

◆ o3derrboundC

double blender::robust_pred::o3derrboundC
static

Definition at line 395 of file math_boolean.cc.

Referenced by exactinit(), and orient3dadapt().

◆ resulterrbound

double blender::robust_pred::resulterrbound
static

◆ splitter

double blender::robust_pred::splitter
static

Definition at line 390 of file math_boolean.cc.

Referenced by exactinit().