Giter VIP home page Giter VIP logo

dorianprill / stroke Goto Github PK

View Code? Open in Web Editor NEW
40.0 2.0 2.0 593 KB

A zero-allocation library providing const-generic implementations of Bézier curves, B-Spline curves and specialized implementations of up to cubic Bézier curves in N-dimensional euclidean space. It is intended for general/embedded/wasm use supporting #![no_std] environments written in 100% safe Rust with minimal dependencies.

License: MIT License

Rust 100.00%

stroke's Introduction

stroke

Rust crates.io

A zero-allocation library providing const-generic implementations of Bézier curves, B-Spline curves and specialized implementations of up to cubic Bézier curves in N-dimensional euclidean space. It is intended for general/embedded/wasm use supporting #![no_std] environments written in 100% safe Rust with minimal dependencies.

The library makes heavy use of const-generics and some related unstabilized features, so the nightly compiler is required.
It comes with a const-generic N-dimensional Point type so you can use the library without any other dependencies.
Should you want to integrate with types provided by another library, you are able to do so by implementing the small Point trait that the library relies upon (given it makes no distinction between a point and its position vector).

A Cubic Bézier Curve with Bounding Box and Convex Hull rendered by plotters.rs

made with plotters.rs

Right now, the generic versions don't implement all methods that the specialized versions do (as the algorithms get a bit more complicated) but should reach parity eventually.

Goals

  • Provide generic Bézier curves and B-Splines. Due to their frequent usage, further provide lines, quadratic and cubic Bézier curves
  • Support no-std for all targets
  • Extensive unit testing and code coverage
  • Integration tests for other generic math libraries (TBD - maybe optimath, aljabar, micromath, nalgebra) since Point types are replicated in many libraries

Non-Goals

  • Focus on use for rendering or highest performance (no GPU)

Features

These are the main supported features. Some further utility methods are exposed where useful.

Quadratic and Cubic Bézier Curves

  • evaluation (De Casteljau, direct)
  • split
  • derivative
  • arc length (linear approx.)
  • arc length (Legendre-Gauss)
  • curvature/radius (Frenet-Serret Frame)
  • bounding box
  • tight box

Generic Bézier Curves

  • evaluation (De Casteljau)
  • split
  • derivative
  • arc length (linear approx.)
  • arc length (Legendre-Gauss)
  • curvature/radius (Frenet-Serret Frame)
  • bounding box
  • tight box

Generic B-Splines

  • evaluation (De Boor)
  • split
  • derivative
  • arc length (linear approx.)
  • arc length (Legendre-Gauss)
  • curvature/radius (Frenet-Serret Frame)
  • bounding box
  • tight box

Related

If you're looking for a published crate for rendering with gpu support you should check out Lyon from which I draw some inspiration, it's really good. It features lines, quadratic and cubic Béziers, in addition to arcs, triangles, and other geometric objects but no general Bézier curves or B-Splines. It also does seem to support wasm.

Also, there's Twinklebear/bspline which is a very clean and useful library for just bsplines. However, it depends on std and its simple Interpolate trait defines no way to access the individual dimensions of the points and hence implements no derivatives in the library.

This clear online book A Primer on Bézier Curves helped me with a lot of the algorithms involved.

stroke's People

Contributors

dorianprill avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar

stroke's Issues

Bounding Box Support for Curves with Generic Degree

Goal

Implement bounding_box() method for the generic Bezier and BSpline curve types.

Problem

Computing the bounding box requires finding the extrema of a polynomial/curve of degree N, which translates to finding roots of a spline curve of degree N-1. For higher order curves (d > 4) this requires implementing the newton-raphson root finding algorithm.
This may be difficult to do generically for both curve types in a const generic setting because some instability around the Fn-family traits.

It is already implemented with tinyvec::ArrayVec for the specialized types QuadraticBezier and Cubic Bezier where N is fixed.

Better Arc Length Approximation

Goal

arclen() is currently implemented using linear approximation, which is fast and simple but not very accurate. Add an alternative method that uses a more advanced technique like legendre-gauss while keeping computational complexity reasonable, or at least configurable.

Problem

Various approaches exist, some established, some more recent. All have certain trade-offs. Raph Levien provides a very insightful analysis in his blog

Solution

Define a useful set of default parameters and/or make them configurable without complicating the API too much.
Implement on of the methods discussed by Raph and rename the current linear implementation to something like arclen_fast() or arclen_linear()

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.