0.7.0

Robustness

• Geometric curve-curve intersection has better handling for cases when the number of intersection candidates grows large (MAX_CANDIDATES == 64):
  • First tries to reduce the number of candidates by checking if the actual convex hulls of each segment in a candidate pair intersect. This is a much "finer" check than using the "blunt" bounding box check.
  • If the convex hull refinement fails, checks if the curves are coincident, i.e. different segments / parameterizations along the same algebraic curve. This is done by using the Curve.locate() function to try to project each of the four endpoints onto the other curve and then re-parameterizing each curve onto a common interval.

Data Structures

• Storing xy-points as columns (rather than rows). This was a very large and breaking change, started in b44af8c. See #51 for more information.

Python Changes

Non-Public API

• Requiring contiguous 1D arrays for Cython functions (9ede37d).

0.6.4

Python Changes

Surface Changes

• Stopped raising ValueError('At least one value outside of unit interval', s_val, t_val) or ValueError('outside of unit interval') when a curve-curve intersection falls barely outside of the parameter space [0, 1] (329a59a).

ABI Changes

Surface Changes

• Removed Status_WIGGLE_FAIL enum and re-numbered all larger Status enum values (by subtracting one)
• Changing "wiggle failure" in curve-curve intersection from a non-success status to be a dropped candidate for intersection

0.6.3

Python Changes

Surface Changes

• Changed RuntimeError('Unexpected number of edges', 11) to RuntimeError('Unknown error has occured.') in the speedup that does surface-surface intersection (35ab5d5). The old error message was a "copy-paste" artifact from the basic_interior_combine() Python helper.

Build

• Removed a flag (-march=native) from the build process for the bezier._speedup extension module (e739429). Using the flag caused the manylinux wheels to be "broken" (see #98).

0.6.2

Python Changes

Documentation

• Converted CHANGELOG.md file into a releases docs page (0027cd7).

Non-Public API

• Collapsed all Cython-generated modules into a single bezier._speedup module (8bcb319).
  • This is the change that prompted the release.
  • Dropped the five bezier._HAS_*_SPEEDUP members for a single bezier._HAS_SPEEDUP (this was the previous approach before 0.6.0).
  • Renamed a few of the Cython helper functions to avoid name collision.
  • This was done to fix a bug and prevent future bugs. The issue was that a mutable Fortran global (MAX_CANDIDATES) was being included via an object file in separate extension modules. When one module updated the global, the other module never saw the update (because it was a different copy).

0.6.1

PyPI: https://pypi.org/project/bezier/0.6.1/
Docs: https://bezier.readthedocs.io/en/0.6.1/

Python Changes

Documentation

• Noting that Surface.intersect() can return a list of either CurvedPolygon or Surface instances (16e77d7).

Breaking Changes

• Removing IntersectionClassification enum from _status.pxd (4da969e).

Non-Public API

• Adding getters and setters for parameters used during curve-curve intersection (ef4ebc0):
  • bezier._geometric_intersection.set_max_candidates()
  • bezier._geometric_intersection.get_max_candidates()
  • bezier._geometric_intersection.set_similar_ulps()
  • bezier._geometric_intersection.get_similar_ulps()

ABI Changes

Surface Changes

• Switching from int to an actual enum for relevant functions with output values that are enums:
  • In surface_intersection.h::surface_intersections, contained is now a SurfaceContained (0a9c0c3) and status is now a Status (c356c32)
  • In curve_intersection.h::bbox_intersect, enum_ is now a BoxIntersectionType (ef856af)
  • In curve_intersection.h::curve_intersections, status is now a Status (ef856af)
• Adding getters and setters for parameters used during curve-curve intersection (ef4ebc0):
  • curve_intersection.h::set_max_candidates
  • curve_intersection.h::get_max_candidates
  • curve_intersection.h::set_similar_ulps
  • curve_intersection.h::get_similar_ulps

Breaking Changes

• Removing inputs curve_start / curve_end and outputs true_start / true_end in curve.h::specialize_curve (959c547)

0.6.0

PyPI: https://pypi.org/project/bezier/0.6.0/
Docs: https://bezier.readthedocs.io/en/0.6.0/

Performance Optimizations

• Added recommended performance flags for gfortran based on recommendations on fortran90.org (3877982).
  • Extensions can be compiled in debug mode by setting DEBUG=True ([b62460b][0.6.0-62]).
  • Setting BEZIER_NO_EXTENSIONS=True will build pure-Python modules only (3f6280c)
• Added [QUADPACK][0.6.0-86] to use in curve.f90::compute_length ([985a4c0][0.6.0-53]).
• Implemented curve-curve intersection completely in Fortran (e.g. [4a8f801][0.6.0-28]) which resulted in a 10x speedup when called from Python. Also implemented surface-surface intersection completely in Fortran, resulting in a 3x speedup.

Python Changes

New Features

• Added CurvedPolygon._metadata to track where edges originated, e.g. from a surface-surface intersection ([871d23d][0.6.0-45]). This is used for sanity checking in functional tests ([e253da2][0.6.0-78]).
• Made speedup checks specific to the module, not all four. I.e. bezier._HAS_SPEEDUP was dropped in favor of five members, e.g. _HAS_CURVE_SPEEDUP ([d798f66][0.6.0-73]).
• Added bezier.__author__ and [bezier.__version__][0.6.0-87] attributes.
• Added [bezier.get_dll()][0.6.0-88] for Windows ([699e39b][0.6.0-34]).
• Added bezier/__config__.py that adds libbezier to %PATH% on Windows ([8538af4][0.6.0-43]).
• Fortran / Cython speedups added:
  • _curve_speedup.pyx::subdivide_nodes
  • _curve_speedup.pyx::newton_refine
  • _curve_speedup.pyx::locate_point
  • _curve_speedup.pyx::elevate_nodes
  • _curve_speedup.pyx::get_curvature
  • _curve_speedup.pyx::reduce_pseudo_inverse
  • _curve_speedup.pyx::full_reduce
  • _curve_speedup.pyx::compute_length
  • _curve_intersection_speedup.pyx::all_intersections
  • _curve_intersection_speedup.pyx::free_curve_intersections_workspace
  • _helpers_speedup.pyx::contains_nd
  • _helpers_speedup.pyx::vector_close
  • _helpers_speedup.pyx::in_interval
  • _helpers_speedup.pyx::ulps_away
  • _surface_speedup.pyx::specialize_surface
  • _surface_speedup.pyx::subdivide_nodes
  • _surface_speedup.pyx::compute_edge_nodes
  • _surface_intersection_speedup.pyx::newton_refine
  • _surface_intersection_speedup.pyx::locate_point
  • _surface_intersection_speedup.pyx::surface_intersections
  • _surface_intersection_speedup.pyx::free_surface_intersections_workspace

Breaking Changes

• [Curve.intersect()][0.6.0-89] returns s-t parameters rather than x-y values ([c309998][0.6.0-68]).
• [Surface.intersect()][0.6.0-90] returns a list with a single Surface when one of the two surfaces is contained in the other (05b1fd9).
• [Surface.is_valid][0.6.0-91] will only return True if the map B(s, t) determined by the surface has everywhere positive Jacobian. Previously a negative Jacobian was also allowed (260fb51).
• Removed data members from Curve:
  • edge_index ([b969488][0.6.0-63])
  • next_edge (28619e8)
  • previous_edge (28619e8)
  • root ([db427f9][0.6.0-75])
  • start (39ee98b)
  • end (39ee98b)
• Removed data members from Surface:
  • base_x (dea75e3)
  • base_y (dea75e3)
  • width (dea75e3)
• Remove dimension argument in _curve_speedup.pyx::elevate_nodes since it can be inferred from nodes (06501c5).

ABI Changes

New Features

• Fully implemented curve-curve intersection (as curve_intersection.h::curve_intersections) and surface-surface intersection (as surface_intersection.h::surface_intersections) at the ABI level.
• Added the surface_intersection.h header file and implementations for the described functions ([fafd9ff][0.6.0-84]).
• Newly added functions
  • curve.h::subdivide_nodes_curve ([efb3ce6][0.6.0-82])
  • curve.h::newton_refine_curve (2257344)
  • curve.h::locate_point_curve (2121101, 32b0fa9)
  • curve.h::elevate_nodes_curve ([b03fc28][0.6.0-60])
  • curve.h::get_curvature ([69cb2f8][0.6.0-35])
  • curve.h::reduce_pseudo_inverse ([7c3db17][0.6.0-39])
  • curve.h::full_reduce ([4abd309][0.6.0-29])
  • curve.h::compute_length ([985a4c0][0.6.0-53], [7e71b20][0.6.0-40])
  • curve_intersection.h::curve_intersections ([c92f98d][0.6.0-96])
  • curve_intersection.h::free_curve_intersections_workspace ([c92f98d][0.6.0-96])
  • helpers.h::contains_nd (36f4b5e)
  • helpers.h::vector_close ([9f3716a][0.6.0-55])
  • helpers.h::in_interval (3c0af5d)
  • helpers.h::ulps_away (0197237)
  • surface.h::specialize_surface ([eb8693e][0.6.0-81], [fcd5bad][0.6.0-85])
  • surface.h::subdivide_nodes_surface ([6027210][0.6.0-32], [4fc5f2a][0.6.0-30], [8beb1ac][0.6.0-47], 0b2b1f3, [d27b86f][0.6.0-70], [88c302b][0.6.0-46])
  • surface.h::compute_edge_nodes (2d02590, [f86649a][0.6.0-83])
  • surface_intersection.h::newton_refine_surface ([93c288d][0.6.0-50])
  • surface_intersection.h::locate_point_surface (325ea47, [ca134e6][0.6.0-69], [bf69852][0.6.0-65])
  • surface_intersection.h::surface_intersections
  • surface_intersection.h::free_surface_intersections_workspace
• Added [status.h][0.6.0-97] with an enum for failure states. Each Fortran procedure that returns a status documents the possible values and if each value is set directly or by a called procedure ([9fc8575][0.6.0-56], [c2accf7][0.6.0-67]).

Breaking Changes

• Removed functions
  • curve.h::specialize_curve_generic ([d52453b][0.6.0-71])
  • curve.h::specialize_curve_quadratic ([d52453b][0.6.0-71])
  • curve_intersection.h::from_linearized ([d62e462][0.6.0-72])
  • curve_intersection.h::bbox_line_intersect ([72c0179][0.6.0-37])
  • curve_intersection.h::linearization_error ([4a3378b][0.6.0-27])
  • curve_intersection.h::segment_intersection (4060590)
  • curve_intersection.h::parallel_different ([df3e195][0.6.0-76])
• Renamed functions
  • curve.h::newton_refine to newton_refine_curve (194ce95)
  • curve.h::elevate_nodes to elevate_nodes_curve (194ce95)
  • curve_intersection.h::newton_refine_intersect to newton_refine_curve_intersect ([a055525][0.6.0-57])
• Replaced degree with num_nodes (== degree + 1) in functions that operate on curves:
  • curve.h::evaluate_curve_barycentric (13eacdd)
  • curve.h::evaluate_multi ([962c288][0.6.0-52])
  • curve.h::specialize_curve ([ac86233][0.6.0-59])
  • curve.h::evaluate_hodograph ([9170855][0.6.0-49])
  • curve_intersection.h::newton_refine_curve_intersect ([80ec491][0.6.0-42])

Miscellany

• Added documentation for "native extensions" in DEVELOPMENT ([2f9f2c4][0.6.0-92]).
• Overhauled [native-libraries doc][0.6.0-95] with subsections for OS X and Windows ([bfa75ee][0.6.0-66], [72005fb][0.6.0-94], etc.).
• Added Fortran unit tests ([758bdd1][0.6.0-38], [e8afba7][0.6.0-79], 3164365, etc.).
• Began testing in Mac OS X on Travis ([9ac5e8e][0.6.0-54], [85f7619][0.6.0-44], etc.).
• Added a workaround (include/bezier/_bool_patch.h) for the missing support for bool in old MSVC versions that are required to work with Python 2.7 ([5577178][0.6.0-93]).

0.5.0

PyPI: https://pypi.org/project/bezier/0.5.0/
Docs: https://bezier.readthedocs.io/en/0.5.0/

Performance Optimizations

• Change wiggle_interval to return success bool instead of raising an exception. This allows the implicitization approach to use it without having to use exceptions for flow-control. (Fixes #22.)
• Switching Fortran speedups from f2py to Cython (this is because f2py artificially limits the feature set of Fortran, i.e. user defined types)
• Moving some more code to Fortran (e.g. bbox_line_intersect() 3dcf640)

New Features

• Making Fortran features available outside of Python (see Native Libraries)
  • C headers for each Fortran module (via bezier.get_include())
  • Cython .pxd declarations for all Fortran modules
  • libbezier static library (via bezier.get_lib())
• Implementing bezier_roots() polynomial root solver for polynomials written in Bernstein basis. (0dd6369)

Miscellany

• Getting bezier published in the Journal of Open Source Science (JOSS). See review. (e6c4536 and 975ac6b)
• Updating error message for locate() methods and adding a note that locate() / evaluate*() are (essentially) inverses. H/T to @pdknsk #36
• Using Fortran-contiguous arrays in _check_non_simple(). (b06c78e)
• Moving most of Curve.subdivide() and Surface.subdivide() logic into helpers. This is part of an effort to make all helpers take low-level data types rather than Curves, Surfaces, etc. (34515bd and 1fc80e5)
• Split speedup.f90 into submodules curve.f90, surface.f90, etc. (75349b7, dfd6bba, 7096a9d, c326c00)
• Adding BEZIER_JOURNAL option to setup.py. This stores a record of compiler commands invoked during installation. See Native Libraries for more details. (3d832e7 and c64a97a)

0.4.0

PyPI: https://pypi.org/project/bezier/0.4.0/
Docs: https://bezier.readthedocs.io/en/0.4.0/

Performance Optimizations

• Adding Fortran speedups for many crucial computation helpers including
  • intersecting line segments
  • (vectorized) Horner's method for evaluating a Bézier curve at multiple parameters at once
  • (vectorized) Horner's method for evaluating a Bézier surface
  • computing "linearization error" (how close a curve is to a line)
  • specializing a Bézier curve to a sub-interval
  • using Newton's method to refine a curve-curve intersection
• Adding _verify switch to Surface.locate() and Curve.intersect() to selectively disable overly defensive value checking. (Making sure to use this switch during "internal" computation.)
• Making sure NumPy arrays are Fortran-contiguous as often as possible (e.g. snippets and source, via np.asfortranarray()). This is to avoid (and emphasize) a non-trivial overhead when passing a C-contiguous array to a Fortran function. (03a7242, 6064e4c, f1804f4)
• Using Horner's method in Curve.evaluate_multi() and Surface.evaluate_barycentric(), rather than inferior (sometimes non-vectorized) approaches (dee8181, 2611e64)
• Made surface-surface intersection more resilient / lenient for corner intersections. For "nearby" intersections, parameter values can be rounded to 0 or 1. (4a8458c)

New Features

• Adding optional strategy argument (one of geometric or algebraic) to Surface.intersect()
  • Added "algebraic" IntersectionStrategy via curve implicitization (reference)
• Adding Curve.reduce_() which acts as a partial inverse to Curve.elevate(). It is only a complete inverse when a curve is degree-elevated, otherwise it returns the "best" reduced form (in the least squares sense).

Interface Changes

• (Breaking change) Removing show keyword from Curve.plot(), Surface.plot() and CurvedPolygon.plot()
• Adding color keyword to Curve.plot()
• Adding alpha keyword to Curve.plot()
• (Breaking change) Splitting the Surface.evaluate_multi() method into Surface.evaluate_barycentric_multi() and Surface.evaluate_cartesian_multi()
• Adding __dict__ helpers on Curve, CurvedPolygon and Surface. These are @propertys intended only for REPL use, since classes with __slots__ no longer have a __dict__ attribute.

Miscellany

• Adding IntersectionClassification to docs (ref)
• Moving most plotting into a dedicated module. More importantly, importing plotting helpers at run-time rather at import time. So if computational code never plots, it won't eat the import cost of matplotlib. Removing matplotlib as a dependency.

0.3.0

PyPI: https://pypi.org/project/bezier/0.3.0/
Docs: http://bezier.readthedocs.io/en/0.3.0/

Performance Optimizations

• Adding __slots__ for all classes

• Removing all usage of @property calls from internal callers (to avoid function call overhead)

• Avoiding un-necessary data copying, e.g. nodes[[0], :] creates a copy but

  nodes[0, :].reshape((1, 2))

  does not (more details)

• Adding _verify switches to selectively disable overly defensive value checking. Added to CurvedPolygon constructor, Surface.evaluate_barycentric(), Surface.evaluate_cartesian(), Surface.evaluate_multi() and Surface.intersect(). Internal callers with already verified data now skip verification steps

• Bailing out early if surface bounding boxes are disjoint in Surface.intersect()

Breaking Changes

• Requiring degree in Curve and Surface constructors, but adding Curve.from_nodes() and Surface.from_nodes() factories to accept nodes only (computing the degree in the constructor every time is a waste of flops, especially if the caller knows the degree)
• Removing public Curve.copy() and Surface.copy()
• Removing custom equality checks for Curve and Surface objects. The previous implementation did not factor in all relevant values
• Returning 1xD arrays instead of flattened D-dimensional 1D arrays from Curve.evaluate(), Surface.evaluate_barycentric(), Surface.evaluate_cartesian(), and related helpers
• Renaming Intersection.left/right as first/second (They were poorly named originally, since "left" and "right" were in reference to where they were used in code, not geometry. This class is not part of the public interface, but it is documented.)

Bug Fixes

• Handling cases where one corner of a surface touches another but their interiors don't intersect (in Surface.intersect()). Adding ignored_corner classification to handle these curve-curve intersecions that don't contribute to a surface-surface intersection
• Throwing exception in Curve.locate() when the subdivided intervals are very far apart (#13)
• Improving Surface.is_valid by considering the signs of the Jacobian determinant at corner nodes (#12)

Miscellany

• Adding possible strategy to avoid linear convergence in newton_refine()
• Adding AppVeyor configuration to make sure there are no Windows issues, testing exclusively with conda install
• Updating generated images with matplotlib 2.0

0.2.1

PyPI: https://pypi.org/project/bezier/0.2.1/
Docs: http://bezier.readthedocs.io/en/0.2.1/

• Added Curve.locate() and _curve_helpers.newton_refine() helper
• Adding optional color to Surface.plot()
• Adding Surface.elevate() for degree elevation
• Fixing nodes defining the self-intersecting curve in curve-curve-intersection (no code in bezier was broken / fixed, just "bad" docs)
• Allow wiggle outside of [0, 1] when intersecting linearizations in from_linearized()
• Collapsing almost-same parameter values in intersect_one_round() (via from_linearized()). Previously checked for bitwise equality and relied on checking values at the boundary of a subdivided interval
• Adding non-public bezier._plot_helpers module