2D polyline/shape library for offsetting, combining, etc.

Overview

Summary

This project is a continuation of the C++ CavalierContours library rewritten in Rust with the goal of building out more functionality, better documentation, and creating a stable C FFI. This project is still in early development, with no APIs yet solidified, the code is not fully tested, and some functions still need to be ported from C++. For tracking progress and contributing checkout the project GitHub issues.

Why go to Rust?

  • All the same benefits of using C or C++ (great performance/optimizations, native compile, no garbage collection, no run time) for creating fast portable libraries with a C FFI
  • Great builtin tooling around builds and packages (cargo + crates)
  • Great builtin tooling for writing and maintaining tests
  • All of the great builtin tooling makes open source contribution and participation easier to facilitate
  • Borrow checker + lifetimes allow for more advanced memory allocation optimizations without the risk of memory errors/corruption bugs
  • Type system allows for leaning heavily on threads/concurrency without the risk of memory errors/corruption bugs
  • Discriminated unions and pattern matching as first class language features
  • Great tooling for targeting wasm

New to Rust but still want to contribute?

I recommend the official rust book here. Visual Studio Code + rust-analyzer extension work great for editing. If you're looking for something specific to work on check the project issues labeled good first issue.

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Comments
  • Incorrect combining result (using C)

    Incorrect combining result (using C)

    Hello! Ive created this test vector:

    "Vector, nodes 4, closed=1"
    "    Node 0 : X=155.575   Y=113.665   B=0"
    "    Node 1 : X=161.29   Y=113.665   B=1"
    "    Node 2 : X=161.29   Y=114.935   B=0"
    "    Node 3 : X=155.575   Y=114.935   B=1"
    "Vector, nodes 4, closed=1"
    "    Node 0 : X=161.29   Y=113.665   B=0"
    "    Node 1 : X=167.64   Y=113.665   B=1"
    "    Node 2 : X=167.64   Y=114.935   B=0"
    "    Node 3 : X=161.29   Y=114.935   B=1"
    

    Basically it is 2 horisontal lines: second one starts at same point, where first ends (X=161.290 Y=114.300)

    I use this C function:

    cavc_pline_boolean(scene[countur_in_scene_num], countur2, cavc_booleanOp_And, combine_options, &pos_list, &neg_list);
    

    Could you please take a look on it?

    opened by tredecimguttatus 26
  • [Bug]This polyline cannot be offset outside

    [Bug]This polyline cannot be offset outside

    https://user-images.githubusercontent.com/19372111/122493643-a4f24500-d01a-11eb-97f8-f2e26873c0cd.mp4

    This polyline cannot be offset outside

    
    {"vertexes":[[0,0,2.9239855509708432],[422.7001801508977,-2181.678349165927,0.21373279590439873],[1217.850643134374,-1733.2038795014323,4.472986753391631],[961.0754444813574,-155.87051634718955,0.22947158823257166]],"isClosed":true}
    
    
    bug 
    opened by FishOrBear 11
  • Add characteristic polylines and more benchmarks

    Add characteristic polylines and more benchmarks

    More benchmarks should be added for the core polyline functions:

    • Polyline path length
    • Polyline parallel offset
    • Polyline winding number These benchmarks can be added to cavalier_contours/benches/benches.rs.

    More polylines (capturing different characteristics, e.g. polyline with lots of lines, polyline with lots of arcs, polyline when offset that has many self intersects, polyline when offset that has very little self intersects, etc.) should be added and available for the benchmarks as well. These can be added to cavalier_contours/benches/test_polylines.rs.

    As things grow it may make sense to create another crate in the workspace that has all the characteristic polylines we want to add for testing so it may be accessed from the other crates (test_suite, etc.).

    help wanted good first issue 
    opened by jbuckmccready 4
  • Overlapping lines appear in the offset result

    Overlapping lines appear in the offset result

    {"vertexes":[[0,0,0],[0,-882.3073569599583,0.19403531582953024],[30.99567883971031,-942.6919889602286,0.1940353158226031],[0,-1003.0766209573267,0],[0,-1880,0],[4,-1880,0],[4,-1003.2606547873729,-0.19502429444774674],[34.00003211540752,-945.3840053746535,-0.19502429171847763],[64,-1003.2606547872638,0],[64,-1880,0],[68,-1880,0],[68,-1003.0766209572321,0.1940353134888888],[37.00432115854346,-942.6919889585697,0.194035313489369],[68,-882.3073569597691,0],[68,0,0],[64,0,0],[64,-882.1233231297883,-0.19502431066879408],[33.999968577962136,-939.9999731353018,-0.19502429444816094],[4,-882.1233231296792,0],[4,0,0]],"isClosed":true}
    

    If it can be improved better, it doesn't matter if it can't be improved

    opened by FishOrBear 3
  • Failing test case from the web version

    Failing test case from the web version

    Feel free to close immediately, I didn't search if the bug was already submitted.

    I just played with the web version of CavalierContours and found a failing test:

    (80.0, 90.0, 0.374794619217547),
    (231.5, -278.0, 0.0),
    (230.0, 0.0, 1.0),
    (320.0, 0.0, -0.5),
    (280.0, 0.0, 0.5),
    (390.0, 210.0, 0.0),
    (280.0, 120.0, 0.5)], 3.0) =>
                        [PlineProperties::new(11, 0.0, 1563.689560505266, 66.99239238371496, -273.0909692941639, 401.41586988912127, 205.22199935960901)]
    

    with mode Offset , Offset 3, Offset count 50, Handle Self Intersects activated.

    Thanks for offering this project!

    opened by galou 2
  • Improve intersect functions documentation

    Improve intersect functions documentation

    The functions in circle_circle_intersect.rs, line_circle_intersect.rs, line_line_intersect.rs, under cavalier_contours/core/math and cavalier_contours/polyline/pline_seg_intersect.rs need code examples added to their documentation. E.g. circle_circle_intr just has /// Finds the intersects between two circles.

    Add more documentation about their parameters, and add a basic code example similar to what is done for the functions in the cavalier_contours/polyline/pline_seg.rs module.

    documentation help wanted good first issue 
    opened by jbuckmccready 2
  • Finish implementing polyline parallel offset

    Finish implementing polyline parallel offset

    • Finish adding functions to handle open polylines and self intersecting polylines with dual offset slicing.
    • Finalize option structure for passing in epsilon values and any other parameters.
    opened by jbuckmccready 2
  • Fix pline intersect function to use pos_equal_eps

    Fix pline intersect function to use pos_equal_eps

    In case of segments not intersecting but close enough (in pos_equal_eps box) there will be incorrect behavior. If bound boxes isn't overlap but segments intrsects. For examle: 2 perpendicular segments * | | * ------- with distance between less than pos_equal_eps but greter than T::epsilon() In that case should be intersection but it won't

    opened by hhemul 1
  • Arc overlap intersect not detected

    Arc overlap intersect not detected

    It is possible for arc overlap intersection to not be detected but other intersections are, this causes problems in boolean operation between polylines.

    Original issue with test cases here: https://github.com/jbuckmccready/CavalierContours/issues/48

    bug 
    opened by jbuckmccready 1
  • How should epsilon/tolerance values be organized?

    How should epsilon/tolerance values be organized?

    How should epsilon/tolerance values be specified? There can be multiple epsilon values within an algorithm each of which may use different values (e.g. epsilon used or determining if two points overlap may be different than the epsilon used for fuzzy comparing in a distance check).

    Currently in C++ they are just hard coded constants but it would be good to have them as part of the API with easy to use sensible defaults.

    Currently I think all epsilon values should be explicitly passed to functions and have them be bundled inside of an options struct. The options struct then implements the Default trait with sensible default values, from the consuming side then specific epsilon values (or other option fields) could be changed from the default.

    design decision 
    opened by jbuckmccready 1
  • Review intersect functions to minimize error and maximize consistency

    Review intersect functions to minimize error and maximize consistency

    The main intersect functions line_line_intr, line_circle_intr, circle_circle_intr, and pline_seg_intr all use a fuzzy epsilon value for float comparisons. These functions should be reviewed for improvement in quality (reducing error) and consistency (they should agree in as many cases as possible when given the same epsilon value).

    Background:

    The epsilon value is used to prevent pathological problems (e.g., when two lines are almost parallel they should just be treated as parallel due to limited precision of floats), and also makes results fuzzy/sticky (e.g., if the end of a line segment very nearly touches a circle it should be treated as an intersect).

    This is required for geometric consistency in intersect detection within algorithms. E.g., if we parallel offset a line by x and then by -x and find intersects with the original input we expect the result to be overlapping (even the line may not be exactly the same due to error propagation through floating point arithmetic in the offset operation).

    Some recent commits that attempt to patch some issues relating to intersect consistency and errors: https://github.com/jbuckmccready/cavalier_contours/commit/e6a598ff5e0ef7ef418754b17c39cb96ba0c1b85 https://github.com/jbuckmccready/cavalier_contours/commit/1a40c08a2a23f18969e9b77c2976e244fea473d1 https://github.com/jbuckmccready/cavalier_contours/commit/f712458c6aa9fb13d6f7b01a13e159c0680f856a

    opened by jbuckmccready 1
  • Support polyline with multiple offsets

    Support polyline with multiple offsets

    I posted this question at the C++ issue tracker-- I'm not sure whether this or that place is the right place to post. Anyway feel free to close the one that is not relevant.

    The question is this: Is there any plan to support variable offsets? Something like NetTopologySuite VariableBuffer. Currently only uniform offset can be done throughout all the vertexes on the polylines.

    opened by WindingWinter 5
  • Add polyline offset option to choose whether to keep or discard overlapping results

    Add polyline offset option to choose whether to keep or discard overlapping results

    Currently all overlapping results are kept (purposefully) by the polyline offset function. There could be an option to toggle this behavior to discard them rather than keep them.

    enhancement 
    opened by jbuckmccready 0
  • Look into supporting bulge values greater than 1

    Look into supporting bulge values greater than 1

    Currently it's assumed all bulge values are between -1 and 1 (this ensures the chord is always the line between the vertexes). If an arc is greater than a half circle it must be split into two segments.

    The different polyline operations need to be reviewed for what the consequences would be to support larger bulge values. Original issue reporting bug: https://github.com/jbuckmccready/cavalier_contours/issues/13.

    enhancement 
    opened by jbuckmccready 0
  • Look into different offset join types

    Look into different offset join types

    Currently segments are always joined with an arc when needed (to maintain constant offset distance from original input).

    It's common in graphics libraries to offer other join types, e.g. see Microsoft documentation on the Shape.StrokeLineJoin Property here: https://docs.microsoft.com/en-us/dotnet/api/system.windows.shapes.shape.strokelinejoin?view=net-5.0

    It may be possible add a miter and/or bevel join option to the parallel offset algorithm, need to investigate if it conflicts with the way offset slice pruning is performed.

    enhancement 
    opened by jbuckmccready 0
Releases(0.2.0)
Owner
Jedidiah Buck McCready
Jedidiah Buck McCready
A Rust library for calculating perceptual hash values of images

img_hash Now builds on stable Rust! (But needs nightly to bench.) A library for getting perceptual hash values of images. Thanks to Dr. Neal Krawetz f

Austin Bonander 264 Dec 9, 2022
A simple steganography library written in rust

steganography A stable steganography library written in rust Crates.io Usage Add the following to the Cargo.toml in your project: [dependencies] stega

Teodor Voinea 79 Dec 9, 2022
Face detection library for the Rust programming language

Rustface SeetaFace detection library for the Rust programming language Example of demo program output SEETAFACE C++ – Github repository for the origin

Andrei Tomashpolskiy 323 Dec 27, 2022
resvg is an SVG rendering library.

resvg can be used as a Rust library, a C library and as a CLI application to render SVG files based on a static SVG Full 1.1 subset.

Evgeniy Reizner 1.8k Dec 30, 2022
A Simple-to-use, cross-platform Rust Webcam Capture Library

Cross Platform Rust Library for powerful Webcam Capture and Virtual Webcams

null 246 Jan 8, 2023
A linear algebra and mathematics library for computer graphics.

cgmath-rs A linear algebra and mathematics library for computer graphics. The library provides: vectors: Vector2, Vector3, Vector4 square matrices: Ma

rustgd 998 Jan 2, 2023
😱 Dead fast thumbnail library for browser and NodeJs! Built with Rust 🦀 and WebAssembly 🕸

thumbo-core ?? Dead fast thumbnail library for browser and NodeJs Built with Rust ?? & WebAssembly ?? ?? About thumbo-core is a thubnail library for b

Victor Aremu 12 Dec 2, 2022
Rust library for fast image resizing with using of SIMD instructions.

fast_image_resize Rust library for fast image resizing with using of SIMD instructions. CHANGELOG Supported pixel formats and available optimisations:

Kirill Kuzminykh 115 Jan 5, 2023
PNG decoding and encoding library in pure Rust

PNG Decoder/Encoder PNG decoder/encoder in pure Rust. It contains all features required to handle the entirety of the PngSuite by Willem van Schack. p

image-rs 247 Dec 25, 2022
An advanced image processing library for Rust.

ImageProc Maintainers: @chyh1990 Note: this project is under active depvelopment, API may change! imageproc is a advanced image proccessing library fo

Chen Yuheng 97 Oct 18, 2022
Rust library to get image size and format without loading/decoding

imageinfo-rs Rust library to get image size and format without loading/decoding. The imageinfo don't get image format by file ext name, but infer by f

xiaozhuai, Weihang Ding 47 Dec 30, 2022
Image operation rust library

Image operation rust library

LongYinan 166 Dec 20, 2022
ePaperify: Framebuffer/image pre-processing library for e-Paper displays

ePaperify: Framebuffer/image pre-processing library for e-Paper displays

Jackson Ming Hu 5 Mar 15, 2022
Antialiased 2D vector drawing library in Rust for Android, Web, Desktop

nonaquad Vector anti-aliased graphics renderer for Android, WASM, Desktop in Rust, using miniquad. This library started as a port of NanoVG for miniqu

Nokola 33 Nov 14, 2022
Antialiased 2D vector drawing library written in Rust

femtovg Join the femtovg Discord channel Work in progress! Antialiased 2D vector drawing library written in Rust.

Tomasz Sterna 0 Aug 24, 2021
Screen-capturer: A cross-platform screenshots library for MacOS、Windows、Linux(X11).

Screen-capturer: A cross-platform screenshots library for MacOS、Windows、Linux(X11).

nashaofu 49 Dec 12, 2022
Easy c̵̰͠r̵̛̠ö̴̪s̶̩̒s̵̭̀-t̶̲͝h̶̯̚r̵̺͐e̷̖̽ḁ̴̍d̶̖̔ ȓ̵͙ė̶͎ḟ̴͙e̸̖͛r̶̖͗ë̶̱́ṉ̵̒ĉ̷̥e̷͚̍ s̷̹͌h̷̲̉a̵̭͋r̷̫̊ḭ̵̊n̷̬͂g̵̦̃ f̶̻̊ơ̵̜ṟ̸̈́ R̵̞̋ù̵̺s̷̖̅ţ̸͗!̸̼͋

Rust S̵̓i̸̓n̵̉ I̴n̴f̶e̸r̵n̷a̴l mutability! Howdy, friendly Rust developer! Ever had a value get m̵̯̅ð̶͊v̴̮̾ê̴̼͘d away right under your nose just when

null 294 Dec 23, 2022
Google Encoded Polyline encoding & decoding in Rust.

polyline Google Encoded Polyline encoding & decoding in Rust. A Note on Coordinate Order This crate uses Coordinate and LineString types from the geo-

GeoRust 14 Dec 11, 2022
Generic abstractions for combining and nesting reduction patterns for iterables.

reductor Generic abstractions for combining and nesting reduction patterns for iterables. Docs: https//docs.rs/reductor Before & After: Before fn proc

Yotam Ofek 2 Jul 9, 2022
A simple CLI for combining json and yaml files

A simple CLI for combining json and yaml files

Avencera 16 Jul 4, 2022