search

jbuckmccready / cavalier_contours

2D polyline/shape library for offsetting, combining, etc.
Apache License 2.0
144 stars 12 forks source link

Create abstracted Shape type #7

Open jbuckmccready opened 3 years ago

jbuckmccready commented 3 years ago

Create a Shape type which holds an indexed graph of closed polylines which represent positive and negative space. Then operations can be applied to the shape type similar to how they are done for single polylines for offsetting, boolean operations, area, etc.

There may be a way to generalize it to also support open polylines (not yet determined if feasible and how that may affect the algorithmic operations).

FishOrBear commented 3 years ago

This feature is very useful.

Shape{outline:Polyline,holes:Polyline[]}

Shape Boolean operation: Multiple Shape Union operation. Multiple Shape Difference Operation Multiple shape intersection operations

yaqwsx commented 1 year ago

Hi! I've seen that you started implementing this feature on the branch WIP_island_offsetting. I am wondering if you have any schedule for initial merge of this feature? Is there any way I can help you finish it?

I developed https://github.com/yaqwsx/KiKit - a tool for automatic panelization of PCBs. Internally, it use Shapely for polygon manipulation, but there are many problems with that. I really like your library, as it supports arcs, and I am considering using it for KiKit. I started implementing Python bindings for it (https://github.com/yaqwsx/py_cavalier_contours). I was considering implementing Shape in my wrapper; however, if you plan to support it natively, I prefer to support you instead of implementing it in the wrapper.

I think I can offer extensive testing on real-world examples.

jbuckmccready commented 1 year ago

Hey, I'm not sure when I'll have the time to dig into it more. I finished implementing the function in Rust on that branch WIP_island_offsetting but right now it just successfully compiles, I'm sure there are bugs to fix and I'm not sure about what the final API looks like.

As far as next steps:

  1. The web demo app I use for visual verification, testing and generating test cases needs to updated with a page for the island offsetting (calling the new functions from that WIP_island_offsetting branch). Web demo app repository is here. My thinking is to have the whole input set of closed polylines just encoded in the JSON input box in the UI.
  2. Once the web demo app is running the rust code the app can be used to debug the function and generate test cases.

That is quite a bit of work to dig into but if you want to work on it there is a lot of working example code - you can look at the existing pages in the demo app for the polyline offseting and boolean operations to see how it's wired up using typecript + vuejs and drawing to a canvas using PixiJS for the UI, and a Rust WASM FFI wrapper crate to expose the function calls to javascript.

To build and run the demo app using the WIP_island_offsetting branch and make local edits you can change the dependency of cavalier_contours to a local file path. Replacing cavalier_contours = {git = "https://github.com/jbuckmccready/cavalier_contours"} in the cavalier_contours_web_ffi/Cargo.toml with cavalier_contours = { path = "*LOCAL_PATH_TO_REPO*" } (see here for docs on this).

I'm willing to answer questions to help development, and I'm willing to fix the bugs that arise in the Rust implementation, so if you can get it wired into the web demo app I can probably fairly quickly finish it off.

I'm just not sure when I'll get around to updating the web demo app which is needed to actually test and get things finished. I do want to finish it, just have lots of other things going on.

And finally I'm not sure exactly on the algorithm for boolean operations between sets of closed polylines representing shapes - I want it to support holes inside of holes infinitely deep (e.g., donut inside of a donut hole, inside of a donut hole, etc. boolean operation with another similar overlapping shape) and I have an idea on how to make that work efficiently but it's not implemented at all.

jbuckmccready commented 1 year ago

Just an update on this issue: I have resumed working on it, getting it into the web demo and testing currently.

jbuckmccready commented 1 year ago

Got it at least breathing, still a bunch of work to do to clean it up and finish it, hope to spend some more time on it in the next few days, here's a teaser: image

yaqwsx commented 1 year ago

Hi! I love the work you did. Do you plan to add the shape support to FFI? When you do so, I will try to integrate it into KiKit, and I can provide you with feedback and extensive testing.

jbuckmccready commented 1 year ago

OK initial approach committed for this feature. I added a shape type and parallel offset to the shape type which has the multi/island polyline offset behavior.

Interactive demo here: https://jbuckmccready.github.io/cavalier_contours_web_demo_page/#/multi_pline_offset

I'm still not sure on the Rust API, it's kind of awkward needing to build the shape type when the polylines/spatial indexes may already exist and be laid out differently in other structures, which may lead to some extra copies/allocations when using it.

I haven't added the C FFI API or thought about how that should look either. I created an issue for tracking that (as well as what the Rust API should be) here: https://github.com/jbuckmccready/cavalier_contours/issues/34

Please report any issues you find.