2024.6.20

libbezzier Changes

Packaging

• Stop building with -static on Windows (#311). This is entirely enabled by the amazing delvewheel project (non-static dependencies can now easily be packaged into a built wheel for Python).

Python Changes

Packaging

• Added support for Python 3.12 (#315).
• Dropped support for Python 3.8 (#310) and Python 3.9 (#315).

Documentation

• Add DEVELOPMENT.rst section about configuring a shell and compilers for Windows development (#311). This had been a hodge podge of local and remote (CI) development for the last 5+ years, so this a big milestone!

2023.7.28

Robustness

• Fall back to de Casteljau algorithm for evaluation on high degree curves (#264). Fixed #263. The more efficient evaluate_multi_vs() function relies on the ability to compute binomial coefficients (n C k) but after (55 C 26) these values cannot be computed in floating point without roundoff and for very large degrees these values overflow.

Python Changes

Packaging

• Switched to delvewheel for repairing Windows wheels (#307). This is similar to how Linux and macOS packaging already work. This is vastly superior to the homegrown approach previously used with extra-dll.
• Dropped support for Python 3.7 and added support for Python 3.10 and 3.11 (#271, #302).
• Add strict check for Python version on source installs. Fixed #278.
• Make missing BEZIER_INSTALL_PREFIX error message more helpful. In particular, add a suggestion to set BEZIER_NO_EXTENSION for a source only install if BEZIER_INSTALL_PREFIX cannot be set. Fixed #277.
• Use cibuildwheel to automate building wheels as part of release (#308).

Bug Fixes

• Allow the extra DLL directory to be absent on Windows. For binary wheel installs, this directory contains the libbezier DLL (e.g. bezier.libs\bezier-2a44d276.dll). For pure Python installs, the bezier.libs directory will be absent. (#307, #255). Fixed #254.
• Bug fix for clip_range() (doc). Intersections with the t=0 / t=1 sides of the fat line were not taken into account and a value for s_max could be accidentally left unset if the intersections occurred in an order where the s-value decreased throughout (#259).

Breaking Changes

• Removing Surface alias for the Triangle type (#252). The Surface type was deprecated (and converted to an alias) in the 2020.1.14 release.

Additive Changes

• Renaming all "private" _verify args to verify (#251). For example, in Curve.intersect() (doc)
• Adding provisional support for self-intersection checks in planar curves (#265, #267). Fixed #165 and #171. Supported via Curve.self_intersections() method.
• Added alpha argument to Triangle.plot() and CurvedPolygon.plot() methods (#296).

Documentation

• Making all docs pages import external packages at least once (#257). Fixed #210.

2021.2.12

Python Changes

Packaging

• Dropped support for Python 3.6 and added support for Python 3.9 (#246).

Breaking Changes

• Moved non-public / experimental bezier._clipping module to bezier.hazmat.clipping (#225).

2020.5.19

Python Changes

Bug Fixes

• Using importlib.metadata to locate extra-dll on Windows, caused by the behavior of the conda-supplied setuptools in Python 3.8 (#208, fixed #206).

Breaking Changes

• Created bezier.hazmat subpackage (fixed #170).
  • Moved non-public bezier._py_helpers module to bezier.hazmat.helpers (#201).
  • Moved non-public bezier._algebraic_intersection module to bezier.hazmat.algebraic_intersection (#216).
  • Moved non-public bezier._py_curve_helpers module to bezier.hazmat.curve_helpers (#218).
  • Moved non-public bezier._py_triangle_intersection module to bezier.hazmat.triangle_intersection (#219).
  • Moved non-public bezier._py_triangle_helpers module to bezier.hazmat.triangle_helpers (#220).
  • Moved non-public bezier._py_intersection_helpers module to bezier.hazmat.intersection_helpers (#222).
  • Moved non-public bezier._py_geometric_intersection module to bezier.hazmat.geometric_intersection (#223).

Documentation

• Updated binary-extension doc to refer to bezier.libs (#211). This is based on a change to auditwheel from the 3.1.0 release.
• Removed algorithms/algebraic-helpers document since the bezier.hazmat.algebraic_intersection module is now fully documented (#216).
• Updated from https://docs.scipy.org/doc/numpy to https://numpy.org for references to the NumPy documentation (#221).
• Removed algorithms/geometric-helpers document since the functions and classes there are now fully documented in bezier.hazmat (#223).

2020.2.3

ABI Changes

Packaging

• Introduced first-class build and install support for libbezier via CMake. Achieved with the following PRs

  • Added CMakeLists.txt files to enable building libbezier with CMake (#175).
  • Added -DTARGET_NATIVE_ARCH:BOOL=OFF flag to enable portable release builds (#182).

  and closed the following issues

  • Use a shared library (rather than a static library) for libbezier (#54).
  • Enable Python installs to be "hybrid-editable" (#56). (This means that the Python files reference the source tree but the built components, i.e. libbezier and _speedup.so, are already built and utilize caching of CMake.)
  • Use build system other than Python / distutils / setuptools (#62).
  • Add ability to disable -march=native flag to make release builds portable across compatible operating systems (#181).

Python Changes

Additive Changes

• Exposing Curve.evaluate_hodograph() method as part of the public API (#191). Fixed #138.

Packaging

• Removed build dependency on gfortran and other heavyweight tools (and hacks) such as numpy.distutils. Now, libbezier must be built before the Python package can be installed and the install location must be provided via the BEZIER_INSTALL_PREFIX environment variable. Achieved with the following PRs
  • Requiring prebuilt libbezier when building bezier._speedup Python binary extension (#176).
  • Support building of wheels on all platforms that depend on libbezier (#182).
• Switch from manylinux1 to manylinux2010 for built wheels (#178).
• Delaying imports of pkg_resources, scipy and sympy until actually needed (if ever) (#194, #195, 38602d8).
• Adding matplotlib to pip install bezier[full] (8beb036).
• Avoiding bezier.dll name collision on Windows in wheels distributed on PyPI (#190). Fixed #189.

Breaking Changes

• Removed bezier.get_dll() helper (#184).

Documentation

• Changed "Read the Docs" landing page to point to .../stable/ documentation (i.e. the last published release) instead of .../latest documentation (i.e. the last merged commit).
• Making sure CMake installed trees (on Linux, macOS and Windows) are verified in doctest as part of CI (48e4166).
• Making sure example_*.c ABI examples are compiled and run (on Linux and macOS) in doctest as part of CI (ffdcdf7, 9551495, 0766649).
• Converting (untested, potentially stale) console codeblocks to doctest (that get run in CI) for Linux sections of binary extension documentation (#188). Fixed #74.

2020.1.14

Breaking Changes

• Rename Surface to Triangle (#172). Fixed #132.

Documentation

• Make sure all ABI example_*.c blocks get run with doctest (#174). Fixed #173.

Packaging

• Switched from semantic versioning to calendar versioning.

0.11.0

Python Changes

Packaging

• Explicit support for Python 3.8 has been added (#161). On Windows this required using the os.add_dll_directory() function to load bezier.dll (in earlier Python versions, the DLL directory was added by modifying %PATH%).

New Features

• Loosened type constraints in Curve constructor and Surface constructor; now any sequence type is accepted rather than only NumPy arrays (68f7dc7, a8c68a3, f5c7869). Fixed #146.
• Added copy and verify arguments to Curve constructor and Surface constructor (#163). Fixed #158.
• Added SymPy-based helpers for "exact" representations (#164). Fixed #157.
  • Curve.implicitize() function
  • Curve.to_symbolic() function
  • Surface.implicitize() function
  • Surface.to_symbolic() function

Internals

• Re-factored non-public modules so that algorithms implemented in pure Python only invoke other algorithms written in pure Python (#160). Previously these algorithms invoked the equivalent Fortran speedup if present for a given function. Fixed #159.

Miscellany

• Moved *.f90 Fortran files out of Python source tree (#152).

ABI Changes

Breaking Changes

• Added BEZ_ prefix for exported ABI names (#167). Fixed #166.

Additive Changes

• Changed all [in] arguments in C headers to const pointers (#169). Fixed #168.

Bug Fixes

• Explicitly handle length 0 curves (with an error) in the compute_length() Fortran subroutine that is used by the Curve.length property (a24368f). Fixed #148.
• Fixed high-degree error in the Curve.evaluate() method, via the evaluate_curve_barycentric() Fortran subroutine (5768824). Fixed #156. The code uses (n C (k + 1)) = (n - k) / (k + 1) (n C k) to update the value and (30 - 14) (30 C 14) overflows a 32-bit signed integer.

Documentation

• Updated install instructions to show how to disable the binary extension via BEZIER_NO_EXTENSION (6262594, 00c1e61). Fixed #147.
• Added "Citation" section to landing page (9885063). Fixed #150.

0.10.0

Python Changes

Breaking Changes

• Support for Python 2.7 has been dropped. With the impending EOL of Python 2.7 on January 1, 2020 many of the bezier dependencies such as numpy, scipy and pytest have dropped support for Python 2.7 in their latest releases. Some changes related to this include:
  • Removing support for Python 2.7 (3eaa5aa).
  • Updating all PyPy usage to be Python 3 only (1e3037f).
  • Removing _bool_patch.h (4ccc559).

Build

• Integrating black code formatter into the nox --session lint session to ensure consistent formatting (e659532).
• Fully automating the building of wheels in the bezier-wheels project (recent commits). Built wheels are uploaded to a Google Cloud Storage bucket.
• Using the same set of optimal flags for Fortran 77 code (i.e. .f files) that are used for Fortran 90 code (i.e. .f90 files) (e7eb56e).
• Unify requirements.txt files and add notes about why each dependency is required (230814d, 1ae147f, e710ee6).
• Changing imp usage to importlib due to deprecation of the former (9231d92). Fixed #137.
• Ditching the --check-archs flag in the macOS script for building wheels since we can no longer support 32-bit on macOS due to NumPy (37be384).
• Improved dev experience with Docker image used on CircleCI by adding a .dockerignore file for faster builds, suggesting --workdir and flag during local dev, setting WHEELHOUSE environment variable directly in the container (rather than in the CircleCI settings) and allowing "default" locations for pre-built wheels at /wheelhouse and ${HOME}/wheelhouse (08be336, 26acc38, 7634779, f9a8fcf).

Miscellany

• Make some functional test cases more lenient so that they pass on 32-bit CentOS 5, which is used for manylinux (e7eb56e). This was part of a large effort to fully automate the building of wheels in the bezier-wheels project.
• Replacing pypy with pypy3 in testing as the only non-CPython "unofficially supported" runtime. (This is part of the drop in support for Python 2.7.) Unfortunately the currently (as of August 2019) released versions of pypy3 are not currently working with numpy >= 1.16 (see numpy/numpy#12740) so the numpy == 1.15.4 version is a pinned dependency.
  • Specifying the NumPy version in setup.py based on implementation_name (7e9046d).
  • Add _pypy_speedup.c built with Cython 0.29.11 because the latest Cython (0.29.13 as of August 2019) corresponds to the versions of NumPy that are incompatible with PyPy (7813e41).
  • Pinning to numpy==1.15.4 and scipy==1.2.0 in wheelhouse for pre-built Docker container (7634779).
• Added nox --session validate_functional_test_cases session to ensure that functional test cases always adhere to the JSON schema.
  • Added nox session and fixed some schema file bugs (618653a).
  • Fixed curve intersections that did not adhere to schema (35b158a).
  • Transposed nodes schema for curved polygon (8c3ca89).
  • Enable the nox session to run in CircleCI (5a0a343).
• Updated @slow marker for pytest because it used a deprecated API (46f8b57).

Documentation

• Changing all references to Mac OS X to macOS (b10c2fc, c1c2c6b, 131d17b). As of 10.12, the operating system has changed its name.
• Splitting up algorithms/helpers. The pre-amble has been moved into the algorithms landing page and the geometric and algebraic helpers have been moved into separate docs. (889c913).

0.9.0

Documentation

• Documenting the C ABI libbezier (4608364). Fixed #63. This documentation contains a page for each "module" which corresponds to the underlying Fortran module. Each module documents the routines in the corresponding header file, e.g. the surface document corresponds to the bezier/surface.h header. Fully working C examples have been added for each routine in bezier/curve.h and for the enum in bezier/status.h.
• Adding section about environment variables to development document (5186e24). Fixed #78.
• Remove dependency on rawgit.com (04d0f8d). The website is being turned down. Fixed #130.
• Renaming the "Native Libraries" document as "Binary Extension" (f99db20). In the process, changed most references to the "native" Python extension to instead call it a "binary" extension.
• Added a "Cython .pxd Declarations" document (f99db20). Fixed #122.
• Moving all Python specific documentation under a specific URL path (3db483b). In particular, moving
  • /reference/... to /python/reference/...
  • /python-binary-extension.html to /python/binary-extension.html
  • /pxd/... to /python/pxd/....
• Moving all algorithm specific documentation under a specific URL path (6e9c825). In particular, moving
  • /algorithm-helpers.html to /algorithms/helpers.html
  • /curve-curve-intersection.html to /algorithms/curve-curve-intersection.html

ABI Changes

New Features

• Added surface.h::compute_area helper that can be used to compute the area of both a surface and a curved polygon (d4d7249).

Breaking Changes

• Removing getters and setters for parameters used during curve-curve intersection (2fda3ae):
  • curve_intersection.h::set_max_candidates
  • curve_intersection.h::get_max_candidates
• Removing dimension from curve.h::get_curvature (1e39c0c).

Python Changes

New Features

• Added implementation for Surface.area property and CurvedPolygon.area property (eb6077e).

Non-Public API

• Removing getters and setters for parameters used during curve-curve intersection (2fda3ae):
  • bezier._geometric_intersection.set_max_candidates()
  • bezier._geometric_intersection.get_max_candidates()
• Removing cached values for Curve.length property, Surface.area property and Surface.is_valid property (34d48d6).

Build

• Renaming libbezier.dll shared library to bezier.dll on Windows (d17a9bc). This follows the correct convention on Windows.
• Adding Python 3.7 support and making it the default version used for testing (e368e9f).
• Dropping support for Python 3.5 (f99db20).
• Adding back -march=native for non-wheel builds (1566019). This way, when installing from source (either via a local checkout or from the source distribution on PyPI) the most optimal machine instructions will be produced. Fixed #99.
• Removing all traces of 32-bit support for OS X (d7620ad). This was driven by a decision from the NumPy maintainers.

Miscellany

• Adopted black code formatter (f21b52d).
• Adding project URLs and keywords for PyPI (cfb070d).
• Added 20 new surface-surface functional tests (9fd9c1e). See #121 for more information.
• Removed time and memory benchmarks due to flakiness and lack of an environment that could be used for benchmarking (6a30dc2). See #125 to follow discussion on re-enabling such benchmarks.
• Using DEBUG=True environment variable when running unit tests and other related tests (d84dffb).

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](8b1c59d2b48281d38275a...