Handling of overlaping cut lines

[kroozo]

Hi,

When a flap slightly overlaps with the piece itself, like this:

Then the cut layer in the genrated SVG goes into the neighboring face:

It seems to be handled in the background (and thus in the pdf too), so it should be an easy fix :)

Keep up the good work!

[rodrigorc]

Hi!

I have a confession to make... actually I never compute overlaps!

In the UI view, the highlights are computing by using a graphics stencil buffer, that counts how many times a pixel is drawn. If it is more than one, then it is an overlap.

In the PDF/PNG view, I'm drawing the model by layers, first the flaps, then the faces. And they are white even when not using textures, so they effectively erase the overlapping lines.

But in the SVG cutting lines there is nothing to prevent them, so they are fully visible. I would need to remove the overlaps by using... maths! As of now, I don't know if that will be very easy or very difficult... Let me think a bit about it.

[rodrigorc]

Ok, I've been trying to face this algorithm generically, and I failed miserably. There are a lot of corner cases... I fix one and break the other...

But rethinking the issue and being less ambitious, fixing just your particular use case should be easier. That is, the case where the two sides of an edge are on the same piece and share a vertex. Then I can just limit the angle of the flap to that of the edge sides. Easy-peasy.

Naturally, if the flap overlaps with anything other part of the piece, or if the sides of the edge are not contiguous, then, it will do nothing. But something is better than nothing, I guess.

The result would be something like this:

And the SVG lines:

Not perfect, but maybe good enough? Note how the middle flaps are adjusted to the available space, but the top one is unchanged and still overlapping.

Would you mind testing the version and sharing your thoughts? The implememantation is in e20041a5f193203ef6cde52aff1843c52febe2ab, already in the main branch.

[kroozo]

Not perfect, but maybe good enough?

I think so. Having one edge like this is something I see quite commonly when people don't want to separate a piece, and should be the majority of the cases. I think I've seen once a layout where a circular thing had something similar, never the one in your example (I assume because the internal flap would be unusable most of the time, like in the example.

Would you mind testing the version and sharing your thoughts? The implememantation is in https://github.com/rodrigorc/papercraft/commit/e20041a5f193203ef6cde52aff1843c52febe2ab, already in the main branch.

I've tried, but I failed to compile. It's highly likely that I messed up something with git submodules, I will take a closer look later.

$ cargo clean                                                                                                                                                                                                                                                                
Removed 2026 files, 881.1MiB total
$ cargo build                                                                                                                                                                                                                                                                      
   Compiling libc v0.2.154
   Compiling cfg-if v1.0.0
   Compiling once_cell v1.19.0
   Compiling pkg-config v0.3.30
   Compiling proc-macro2 v1.0.82
   Compiling unicode-ident v1.0.12
   Compiling bitflags v2.5.0
   Compiling autocfg v1.3.0
   Compiling libloading v0.8.3
   Compiling log v0.4.21
   Compiling version_check v0.9.4
   Compiling memchr v2.7.2
   Compiling rustix v0.38.34
   Compiling linux-raw-sys v0.4.13
   Compiling smallvec v1.13.2
   Compiling dlib v0.5.2
   Compiling typenum v1.17.0
   Compiling generic-array v0.14.7
   Compiling scoped-tls v1.0.1
   Compiling quote v1.0.36
   Compiling wayland-sys v0.31.1
   Compiling glob v0.3.1
   Compiling jobserver v0.1.31
   Compiling syn v2.0.62
   Compiling cc v1.0.97
   Compiling downcast-rs v1.2.1
   Compiling clang-sys v1.7.0
   Compiling quick-xml v0.31.0
   Compiling crc32fast v1.4.0
   Compiling simd-adler32 v0.3.7
   Compiling prettyplease v0.2.20
   Compiling khronos_api v3.1.0
   Compiling regex-syntax v0.8.3
   Compiling minimal-lexical v0.2.1
   Compiling either v1.11.0
   Compiling wayland-scanner v0.31.1
   Compiling adler v1.0.2
   Compiling miniz_oxide v0.7.2
   Compiling nom v7.1.3
   Compiling wayland-backend v0.3.3
   Compiling regex-automata v0.4.6
   Compiling bytemuck v1.15.0
   Compiling xml-rs v0.8.20
   Compiling cfg_aliases v0.1.1
   Compiling home v0.5.9
   Compiling bindgen v0.69.4
   Compiling which v4.4.2
   Compiling gl_generator v0.14.0
   Compiling aho-corasick v1.1.3
   Compiling regex v1.10.4
   Compiling cexpr v0.6.0
   Compiling flate2 v1.0.30
   Compiling itertools v0.12.1
   Compiling wayland-client v0.31.2
   Compiling slab v0.4.9
   Compiling num-traits v0.2.19
   Compiling lazy_static v1.4.0
   Compiling rustc-hash v1.1.0
   Compiling thiserror v1.0.60
   Compiling lazycell v1.3.0
   Compiling pin-project-lite v0.2.14
   Compiling shlex v1.3.0
   Compiling tracing-core v0.1.32
   Compiling tracing v0.1.40
   Compiling thiserror-impl v1.0.60
   Compiling crypto-common v0.1.6
   Compiling weezl v0.1.8
   Compiling xshell-macros v0.2.6
   Compiling xshell v0.2.6
   Compiling polling v3.7.0
   Compiling wayland-protocols v0.31.2
   Compiling x11-dl v2.21.0
   Compiling byteorder v1.5.0
   Compiling subtle v2.5.0
   Compiling zstd-sys v2.0.10+zstd.1.5.6
   Compiling calloop v0.12.4
   Compiling block-buffer v0.10.4
   Compiling fdeflate v0.3.4
   Compiling xcursor v0.3.5
   Compiling arrayref v0.3.7
   Compiling zune-core v0.4.12
   Compiling strict-num v0.1.1
   Compiling ttf-parser v0.21.1
   Compiling cursor-icon v1.1.0
   Compiling bitflags v1.3.2
   Compiling color_quant v1.1.0
   Compiling mint v0.5.9
   Compiling jpeg-decoder v0.3.1
   Compiling xkeysym v0.2.0
   Compiling smithay-client-toolkit v0.18.1
   Compiling gif v0.13.1
   Compiling tiff v0.9.1
   Compiling png v0.17.13
   Compiling owned_ttf_parser v0.21.0
   Compiling wayland-protocols-wlr v0.2.0
   Compiling zune-jpeg v0.4.11
   Compiling wayland-csd-frame v0.3.0
   Compiling tiny-skia-path v0.11.4
   Compiling calloop-wayland-source v0.2.0
   Compiling wayland-cursor v0.31.1
   Compiling digest v0.10.7
   Compiling glutin_glx_sys v0.5.0
   Compiling glutin_egl_sys v0.6.0
   Compiling memmap2 v0.9.4
   Compiling ahash v0.8.11
   Compiling lock_api v0.4.12
   Compiling cgmath v0.18.0
   Compiling utf8parse v0.2.1
   Compiling powerfmt v0.2.0
   Compiling paste v1.0.15
   Compiling cpufeatures v0.2.12
   Compiling itoa v1.0.11
   Compiling x11rb-protocol v0.13.1
   Compiling arrayvec v0.7.4
   Compiling parking_lot_core v0.9.10
   Compiling as-raw-xcb-connection v1.0.1
   Compiling ab_glyph_rasterizer v0.1.8
   Compiling deranged v0.3.11
   Compiling ab_glyph v0.2.26
   Compiling tiny-skia v0.11.4
   Compiling anstyle-parse v0.2.4
   Compiling image v0.25.1
   Compiling bstr v1.9.1
   Compiling approx v0.4.0
   Compiling winit v0.29.15
   Compiling easy-imgui-sys v0.4.0
   Compiling glutin v0.31.3
   Compiling bzip2-sys v0.1.11+1.0.8
   Compiling getrandom v0.2.15
   Compiling zerocopy v0.7.34
   Compiling num-conv v0.1.0
   Compiling anstyle v1.0.7
   Compiling raw-window-handle v0.5.2
   Compiling anstyle-query v1.0.3
   Compiling serde v1.0.201
   Compiling anyhow v1.0.83
   Compiling scopeguard v1.2.0
   Compiling colorchoice v1.0.1
   Compiling time-core v0.1.2
   Compiling zstd-safe v5.0.2+zstd.1.5.2
   Compiling is_terminal_polyfill v1.70.0
   Compiling anstream v0.6.14
   Compiling time v0.3.36
   Compiling sctk-adwaita v0.8.1
   Compiling wayland-protocols-plasma v0.2.0
   Compiling xkbcommon-dl v0.4.2
   Compiling serde_derive v1.0.201
   Compiling glutin-winit v0.4.2
   Compiling inout v0.1.3
   Compiling cstr v0.2.12
   Compiling percent-encoding v2.3.1
   Compiling smol_str v0.2.1
   Compiling raw-window-handle v0.6.1
   Compiling base64ct v1.6.0
   Compiling rand_core v0.6.4
   Compiling password-hash v0.4.2
   Compiling cipher v0.4.4
   Compiling parking_lot v0.12.2
   Compiling pom v3.4.0
   Compiling sha2 v0.10.8
   Compiling hmac v0.12.1
   Compiling slotmap v1.0.7
   Compiling memoffset v0.9.1
   Compiling encoding_rs v0.8.34
   Compiling signal-hook v0.3.17
   Compiling clap_lex v0.7.0
   Compiling serde_json v1.0.117
   Compiling glow v0.13.1
   Compiling ttf-parser v0.19.2
   Compiling strsim v0.11.1
   Compiling heck v0.5.0
   Compiling md5 v0.7.0
   Compiling linked-hash-map v0.5.6
   Compiling lopdf v0.31.0
   Compiling clap_derive v4.5.4
   Compiling owned_ttf_parser v0.19.0
   Compiling x11rb v0.13.1
   Compiling clap_builder v4.5.2
   Compiling easy-imgui v0.4.0
   Compiling env_filter v0.1.0
   Compiling pbkdf2 v0.11.0
   Compiling bzip2 v0.4.4
   Compiling zstd v0.11.2+zstd.1.5.2
   Compiling aes v0.8.4
   Compiling papercraft v2.5.0 (/home/kroozo/tmp/papercraft2/papercraft)
   Compiling easy-imgui-renderer v0.4.0
error[E0716]: temporary value dropped while borrowed
   --> /home/kroozo/.cargo/registry/src/index.crates.io-6f17d22bba15001f/easy-imgui-renderer-0.4.0/src/renderer.rs:260:22
    |
249 |            let (matrix, viewport_matrix) = match matrix {
    |  __________________________________________-
250 | |              None => {
251 | |                  let ImVec2 { x: left, y: top } = draw_data.DisplayPos;
252 | |                  let ImVec2 {
...   |
260 | |                      &Matrix3::new(
    | | ______________________^
261 | ||                         2.0 / width,
262 | ||                         0.0,
263 | ||                         0.0,
...   ||
269 | ||                         1.0,
270 | ||                     ),
    | ||_____________________^ creates a temporary value which is freed while still in use
...   |
273 | |              }
    | |              - temporary value is freed at the end of this statement
...   |
307 | |              }
308 | |          };
    | |__________- borrow later used here
    |
    = note: consider using a `let` binding to create a longer lived value

For more information about this error, try `rustc --explain E0716`.
error: could not compile `easy-imgui-renderer` (lib) due to 1 previous error
warning: build failed, waiting for other jobs to finish...

[rodrigorc]

I've tried, but I failed to compile. It's highly likely that I messed up something with git submodules, I will take a closer look later.

My bad! That easy-imgui is a dependency written by myself, that I just happened to update before this commit. But I accidentally used a Rust feature only available on the rustc-1.79 beta compiler.

I've updated that crate so all should be fine now. Just run cargo update and then recompile normally.

[rodrigorc]

I've have been devising an algorithm that I think it may solve any self-overlapping issue. In addition to the angle fix from before, It shortens any flap that overlaps with any solid surface of the same piece (If two flaps of the same piece overlap, that is not an issue.)

I think I've seen once a layout where a circular thing had something similar

Something like this? This is a piece of an eye I did once... and now with the new algorithm (WIP):

Yes, the closing flap is mostly unusable, and you could just remove it, but the math is beautiful!

And this is with my original example:

Note how the previously problematic flap is now just shorter enough to not overlap with the face. It looks like the flap goes below the piece a bit, but that's just the line width. Remember that the real cuts are in the inner edge of the drawn lines.

Anyway, there is sill some work to do before is it ready for production, but it looks promising...

[kroozo]

I've updated that crate so all should be fine now. Just run cargo update and then recompile normally. Yes, it does compile now, thanks!

It has fixed the issue, albeit it generates much slower. My model is a relatively simple one, 20 pieces, 64 flaps (3-6 face / piece). Looking at the stat of the first and last svg 2.5 renders the 6 pages around 300 ms, the current master takes about 45 s.

I've also tried to get some more overlaps. I couln't qucikly do one like your original, I managed to come up with this abomination: Now, this is obviously not something that I would do real life, I was just experimenting with the limits of what is happening. And based on what you said I would have expected the 2 overlaps I circle to be handled (but the top one at very least) I've removed the very overlaping end, it still looks the same:

Note, that the overlaping flaps at the bottom are bad on the background layer as well (i guess that's identical to the pdf?), the top one seems fine

Something like this? This is a piece of an eye I did once... and now with the new algorithm (WIP):

Yes, quite similar. I think it was a piece of a tail maybe. It had a bit of an angle, so it was more usable (more flap remaining)

[rodrigorc]

It has fixed the issue, albeit it generates much slower. That is probably because you are doing a debug build. Try recompiling with cargo build --release.

Anyways, I'm rewriting the flap shaping code. Later today I'll push a few commits that should improve the overall quality... I'll let you know here.

[kroozo]

That is probably because you are doing a debug build. Try recompiling with cargo build --release.

Ah, yes, sorry, my bad :)

[rodrigorc]

Ok, I've improved the code a lot, and removed some special cases, such as the rim flaps (those without and adjacent face), that now are computed the same as any other flap. I've also reworked the "memoization" structures, so that even if now there are more computations, the code should be even faster.

Also I've set up the image crate and a few others to compile in "release" mode even in debug builds, to avoid that terrible slowing down when loading and saving files.

Anyway, here are some samples of the result:

This pieces, with oversized flaps:

When put together into the same piece:

Look how the flaps are snugged into the available space, while respecting the size of the adjacent face, no overlaps anywhere!

However overlaps between flaps are not checked:

I think this case is less frequent, and easier for the user to solve: just move some flaps around. The thing is that, for the general case of overlapping flaps, I don't even know what the right solution would look like... it would even depend on the order in which I look at the flaps. And if your cutting machine cuts a corner of a flap, that's not a big deal, I guess...

Also if the piece intersects itself, everything breaks apart, but then the flaps are the least of your worries:

I've just pushed these latest changes. Can you please fetch, rebuild and test it?

[kroozo]

Look how the flaps are snugged into the available space, while respecting the size of the adjacent face, no overlaps anywhere!

Yes, it looks to handle even odd stuff nicely. :+1:

I think this case is less frequent, and easier for the user to solve: just move some flaps around. The thing is that, for the general case of overlapping flaps, I don't even know what the right solution would look like... it would even depend on the order in which I look at the flaps. And if your cutting machine cuts a corner of a flap, that's not a big deal, I guess...

I agree that this is much less of an issue. You can move flaps around, that will probably help unless you try something very dense. Also, all of this is still easily fixable in post-processing, if you really need to, so while I'm a big fan of not leaving manual steps in a pipeline, it just does not seem to worth the effort.

Also if the piece intersects itself, everything breaks apart, but then the flaps are the least of your worries:

I've considered that as a feature. It's just a nice indication that you're not done with your layout work.

[rodrigorc]

I think this is ready for showtime, then. I've just published v2.6 with this change and a few other improvements.

Thank you @kroozo for your input!