0.8.0

New Features

• Adding support for surface-surface intersections that have coincident segments shared between each surface (cfa2b93, 0a9645c). See cases:

  • 4: 10Q-18Q
  • 5: 10Q-19Q
  • 43: 29Q-42Q
  • 44: 29Q-43Q
  • 45: 10Q-44Q
  • 46: 1Q-45Q
  • 47: 1Q-2C

• Adding support for curve-curve intersections that are also points of tangency. This was accomplished by five broad changes to the geometric intersection algorithm:

  • Checking if almost-linear curves have disjoint bounding boxes before intersecting the linearized segments (05f0343).

  • Adding a "full" Newton iteration for finding B1(s) = B2(t) when known to be near a solution. In particular, this has special handling for tangencies, which cause a singular Jacobian and make convergence drop from quadratic to linear and stalls out convergence early (13a5be5, 4bac61a).

  • Changing how "bad" linearized segments are handled. After subdividing to approximately linear curve segments, there were two problems which are now being handled in the same way. If the line segments connecting the subdivided curve endpoints

    • are parallel, then the algorithm failed with a PARALLEL status
    • intersect outside of the unit interval (for either s or t), the curve-curve candidate was rejected (a small amount, 0.5^{16}, of "wiggle" room was allowed outside of [0, 1]).

    Now both cases are handled in the same way. First, the subdivided curve segments will have a convex hull check applied (which is more strict than a bounding box check). If their convex hulls do collide, they are treated as a normal intersection of curved segments (4457f64, fe453c3).

  • Using the newly added "full" Newton's iteration for all intersections. Before, a single Newton step was applied after intersection the linearized segments (d06430f).

  • Changing how a candidate pair of s-t parameters is added. (c998445). In the previous implementation, a pair was considered a duplicate only if there was a difference of at most 1 ULP from an existing intersection (though this could be toggled via set_similar_ulps()). Now, the pair is "normalized" so that s and t are away from 0. For example, if s < 2^{-10} then we use 1 - s instead. (This is perfectly "appropriate" since evaluating a Bézier curve requires using both s and 1 - s, so both values are equally relevant.) Once normalized, a relative error threshold is used.

• Four curve-curve functional test cases have gone from failing to passing:

  • 11: 14-15
  • 31: 38-39
  • 43: 58-59
  • 44: 60-59

  and two surface-surface cases have as well:

  • 10: 20Q-21Q
  • 42: 41Q-21Q

  In order to support the aforementioned surface-surface cases, special support for "tangent corners" was added (12b0de4).

ABI Changes

Breaking Changes

• Removed BAD_TANGENT status enum (b89b2b1). The case where that failure was issued has now been handled as an acceptable TANGENT_BOTH classification for surface-surface intersection points. (See the classify_intersection() function for an example.)
• Adding BAD_INTERIOR status enum (6348dc6). (This is a breaking change rather than additive because it re-uses the enum value of 5 previously used by BAD_TANGENT.) This value is used by interior_combine() in the case that the curved polygon intersection(s) cannot be determined from the edge-edge intersections for a given surface-surface pair. See #101.
• Removed PARALLEL status enum (fe453c3). Now when doing geometric curve-curve intersection, parallel linearized segments are handled by checking if the convex hulls collide and then (if they do) using a modified Newton iteration to converge to a root.
• Adding BAD_MULTIPLICITY status enum (fe453c3). (This is a breaking change rather than additive because it re-uses the enum value of 1 previously used by PARALLEL.) This is used when Newton's method fails to converge to either a simple intersection or a tangent intersection. Such failures to converge, when already starting near an intersection, may be caused by one of:
  • The intersection was of multiplicity greater than 2
  • The curves don't actually intersect, though they come very close
  • Numerical issues caused the iteration to leave the region of convergence
• Removed ulps_away() (c998445).
• Removed set_similar_ulps() and get_similar_ulps() (c998445).

Surface Changes

• Added SINGULAR status enum for cases when a linear system can't be solved due to a singular matrix (4457f64).
• Adding status as a return value in newton_refine_curve_intersect(). This way, when the Jacobian is singular (which happens at points of tangency), the SINGULAR status can be returned (4457f64). The old behavior would've resulted in a division by zero.

Non-Public API

• Adding custom linear solver for the 2 x 2 case (a3fb476). This is modelled after dgesv from LAPACK.

Python Changes

• (Bug fix) The 0.7.0 release broke Surface.plot() and CurvedPolygon.plot() (when the nodes were transposed, the plotting helpers were not correctly updated). The add_patch() helper was fixed to account for the changes in data layout (80bfaaa).
• Added custom UnsupportedDegree exception to be used by routines that have implementations that are hard-coded for specific degrees (87a1f21). See #103.
• Removed ulps_away() (c998445).
• Removed set_similar_ulps() and get_similar_ulps() (c998445).

Non-Public API

• Returning coincident flag from curve-curve all_intersections (ebe6617).
• Adding a TANGENT_BOTH classification for surface-surface intersection points that are interior to both surfaces at the point of tangency (b89b2b1). This previously failed with a NotImplementedError.
• Added COINCIDENT classification for surface-surface intersection points that occur on a segment that is coincident on an edges of each surface (8b1c59d). Such points previously failed classification because they were interpreted as being tangent and having the same curvature (because the segments are identical).
• Added a COINCIDENT_UNUSED classification (cfa2b93) for cases where coincident segments are moving in opposite directions (i.e. the surfaces don't share a common interior). For example see case 44 (29Q-43Q).
• Adding custom linear solver for the 2 x 2 case (764e56d). This is modelled after dgesv from LAPACK.
• Adding some support for Bézier clipping algorithm (fbed62d, ada4ea3). See the original paper by Sederberg and Nishita for more information.