Code Monkey home page Code Monkey logo

lyon's Introduction

Lyon

A path tessellation library written in rust for GPU-based 2D graphics rendering.

Project logo

crates.io Build Status documentation Gitter Chat

Motivation

For now the goal is to provide efficient SVG-compliant path tessellation tools to help with rendering vector graphics on the GPU. For now think of this library as a way to turn complex paths into triangles for use in your own rendering engine.

The intent is for this library to be useful in projects like Servo and games.

Example

extern crate lyon;
use lyon::math::point;
use lyon::path::Path;
use lyon::tessellation::*;
fn main() {
    // Build a Path.
    let mut builder = Path::builder();
    builder.begin(point(0.0, 0.0));
    builder.line_to(point(1.0, 0.0));
    builder.quadratic_bezier_to(point(2.0, 0.0), point(2.0, 1.0));
    builder.cubic_bezier_to(point(1.0, 1.0), point(0.0, 1.0), point(0.0, 0.0));
    builder.end(true);
    let path = builder.build();
    // Let's use our own custom vertex type instead of the default one.
    #[derive(Copy, Clone, Debug)]
    struct MyVertex { position: [f32; 2] }
    // Will contain the result of the tessellation.
    let mut geometry: VertexBuffers<MyVertex, u16> = VertexBuffers::new();
    let mut tessellator = FillTessellator::new();
    {
        // Compute the tessellation.
        tessellator.tessellate_path(
            &path,
            &FillOptions::default(),
            &mut BuffersBuilder::new(&mut geometry, |vertex: FillVertex| {
                MyVertex {
                    position: vertex.position().to_array(),
                }
            }),
        ).unwrap();
    }
    // The tessellated geometry is ready to be uploaded to the GPU.
    println!(" -- {} vertices {} indices",
        geometry.vertices.len(),
        geometry.indices.len()
    );
}

FAQ

In a nutshell, what is a tessellator?

Tessellators such as the ones provided by lyon take complex shapes as input and generate geometry made of triangles that can be easily consumed by graphics APIs such as OpenGL, Vulkan or D3D.

How do I render an SVG file with lyon?

Lyon is not an SVG renderer. For now lyon mainly provides primitives to tessellate complex path fills and strokes in a way that is convenient to use with GPU APIs such as gfx-rs, glium, OpenGL, D3D, etc. How the tessellated geometry is rendered is completely up to the user of this crate.

How do I render the output of the tessellators?

Although the format of the output of the tessellators is customizable, the algorithms are designed to generate a vertex and an index buffer. See the lyon::tessellation documentation for more details.

Is anti-aliasing supported?

There is currently no built-in support for antialiasing in the tessellators. Antialiasing can still be achieved by users of this crate using techniques commonly employed in video games (msaa, taa, fxaa, etc.).

I need help!

Don't hesitate to file an issue, ask questions on gitter, or contact @nical by e-mail.

How can I help?

See CONTRIBUTING.md.

License

Licensed under either of

at your option.

Dual MIT/Apache2 is strictly more permissive

Contribution

There is useful information for contributors in the contribution guidelines.

lyon's People

Contributors

atouchet avatar bnjbvr avatar darnuria avatar dd10-e avatar hadronized avatar halfvoxel avatar hardiesoft avatar hrydgard avatar kaedroho avatar kleintom avatar kuxv avatar luiswirth avatar martinfrances107 avatar mivik avatar nical avatar nivkner avatar notgull avatar nyurik avatar o0ignition0o avatar orhanbalci avatar pizzaiter avatar silentbyte avatar simbleau avatar striezel avatar tronical avatar vihdzp avatar wainwrightmark avatar whmountains avatar yoshierahuang3456 avatar yutannihilation 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  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  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 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

lyon's Issues

NaN produced in the conversion from arcs quadratic béziers.

When tessellating this path:

M134.2 767.22a.5.5 0 0 0-.2.05l-.06.07-.32.62-14.14 60.3-.05 1.17 1.1-1.2 8.65-36.94-6.37 33.34a.5.5 0 0 0 .43.6l.4-.43c-.06.24-.1.43-.13.66l13.44 16.1-18.3 32.6v.02c.17.27.33.53.48.8a.5.5 0 0 0 .17-.06l23.65-13.04-3.97 40.53a.5.5 0 0 0 0 .1l.33.38.58-.12a.5.5 0 0 0 .05-.08l16.6-33.63 3.27 28.74a.5.5 0 0 0 .2.33.5.5 0 0 0 .02.03c3.35-.73 6.35-.8 9.1-.27l6.94-.3a.5.5 0 0 0 .1.02l5.67 6.1 1.9 9.1c.23.8.45 1.65.65 2.53a.5.5 0 0 0 .24.1.5.5 0 0 0 .02 0l88.9 20.9-83.58 2.36a.5.5 0 0 0-.3.1l.1.3c.47.24.97.46 1.46.68l102.83 6.32c.4-.1.82-.23 1.22-.35l-.5-.75-16.92-8.47a.5.5 0 0 0-.05-.08l-.4.14-.04-.52-10.07-10.24-.02-.02a.5.5 0 0 0-.14-.4l-.18.3.07-.47-7.16-16.1.05-.4-.4.64.55-2 3.94-35.5a.5.5 0 0 0 0-.4l-.53.27-.07-.62-23.64-8.45-.28.17-.36.64a.5.5 0 0 0 .13.08l22.57 8.07-30.16 5.28-.4.74-.17-.68-.3.15-11.74 4.3-.83.85-.9-1.54-9.4-8.65-.43.2-.1-.5a.5.5 0 0 0-.02 0 .5.5 0 0 0-.05 0 .5.5 0 0 0-.07 0l.04-.12-12.05-7.44 9.07-5.6-.08-.38-.08-.12-1.94.6-8.03 4.97-.08.02-11.4-.88c-2.06.04-4.08-.07-6.2-.33l-12.35-.4-4.72-2.98-1.2-.26-.12.6 5.03 3.2-6.4 4.03-.1.48-.27-.13a.5.5 0 0 0-.02.03l-16.14 32.68 3.8-38.73-.5-.23-.1-.32a.5.5 0 0 0-.15.06l-22.97 12.65 17.64-31.47a.5.5 0 0 0 .02-.03l-.1-.34c1.3-1.9 2.78-3.77 4.35-5.6l9.98-13.95 3.44 1.06a.5.5 0 0 0 .13.02c.1-.08.2-.17.32-.25h.13a.5.5 0 0 0 .06-.2l.4-3.36 7.54 3.54h.85c.38.34.74.63 1.12.95l40.56 19.52 1.44.34-.1.38a.5.5 0 0 0 .04.04l2.96 3.32.14-.16.76-.25a.5.5 0 0 0-.1-.2l-2.2-2.46 8.13.7.37-.1.18-.53a.5.5 0 0 0-.1-.16l-5.32-6.8 10.67-8.74.42-1.25c-2 1.57-3.98 3.3-6.12 4.62l-5.78 4.74-14.98-4.22c-5.62-1.04-9.87-2.33-14.13-4.3l-17.15-5.78.1-4.54-.18-.1c-.6-1.93-1.1-3.5-1.47-4.84l-2.42-6.68 7.13-8.62 1.47-2.1.26-.1a.5.5 0 0 0-.03-.38l-7-12.53 19.13 9.2a.5.5 0 0 0 .04.02l.46-.15.2-.2a.5.5 0 0 0-.03-.34l-6.24-13.42-.4-.26-.4.1a.5.5 0 0 0-.1.58l5.65 12.17-19.26-9.26-.5.13-.23.5a.5.5 0 0 0 .02.05l6.75 12.07-9.12-6.17a.5.5 0 0 0-.27-.1l-.07.16-.03-.14a.5.5 0 0 0-.35.28l-3.68 7.77 2.25-14.06-.2-.7-.42-.24a.5.5 0 0 0-.25.2l-7.58 13.07.14-17.9-.43-.26.18-.2a.5.5 0 0 0-.74.3l-4.8 17.24-8.8-25.24a.5.5 0 0 0-.5-.34zm-.13 3.75l4.57 41.9-14.62 10.7 10.05-52.6zm1.13 1.06l7.82 22.45-3.6 16.37-4.22-38.82zm13.07 7.43l-.13 15.97.5.1c.35.45.6.73.93 1.13l4.45 2.56 1.78 5.03c1.08 1.57 1.52 2.86 1.55 4.77l1.63 7-2.7 1.76c0 .18-.03.3-.06.48-.65.28-1.24.5-1.8.72l-2.67 1.75-4.77.24-2.68-2.5c-.4-.2-.8-.38-1.22-.6-.17-.4-.3-.82-.45-1.22l-2.67-3.53 1.45-6.64c.33-3.9 1.36-7.8 2.35-12.06l.32.07 4.2-15.04zm7.98 3.94L153.9 798l-4.6-2.64 6.95-11.96zm3.43 5.13l9.5 6.44-14.07 3.23 4.58-9.67zm9.3 7.52l-7.7 9.3-5.9-6.2 13.6-3.1zm-13.3 4.86l4.66 4.93-2.72.58-1.95-5.5zm5.42 5.8l2.9 8-5.8-7.4 2.9-.6zm-2.68 2.5l5.9 7.54-4.36-.93-1.54-6.6zm-19.25 4.53l2.94 3.9-16 5.66 13.07-9.57zm20.28 3.18l3.85 4.17-5.94-2.8 2.1-1.36zm1.48.14l4.08.86-.06 3.46-4-4.32zm-18.13 1.4l3.3 3.08-8.68 19.04-13.03-15.6 18.4-6.53zm125.7.43l-.03.05v.02l.03.94 9.33 1.22.03-.06.08-.6-.03-.33-9.4-1.23zm-112.83.5l-.27 2.37-2.28-.7 2.55-1.67zm-4.63 2.4l-10.9 15.24L147 822l4.04-.2zm21.9 3.9l15.7 5.3a.5.5 0 0 0 .02 0l22.87 6.45-3.13 5.32-35.45-17.06zm39.4 12.33l4.48 5.7-7.43-.66 2.95-5.04zm-48.03 25.12l15.47.5 8 .6-28.9 2.32 5.44-3.42zm29.83 1.6l10.82 6.7-42.75-4.14 31.92-2.56zm-36.74 3.1l48.54 4.7-45.24 24.42-3.3-29.12zm105.55 4.65l-3.98 35.76-26.6-30.4 30.58-5.36zm-55.58.5l9.94 9.13-38.4 13.58 28.47-22.72zm-4.63 2.42l-26.57 21.2-13.8.6 40.37-21.8zm28.5 2.66l26.94 30.77-74.23-5.87 47.26-24.9h.03zm-7.12 2.6l-21.67 11.43 16-9.34 5.67-2.1zm-10.7 3.88l-31.17 18.17-5-5.37 36.16-12.8zm-30.5 19.5l76.22 20.23-74.04-9.76-2.18-10.46zm4.75.22l71.44 5.65 6.73 15.1-78.16-20.74zm6.95 12.52l71.75 9.45.05.1a.5.5 0 0 0 .1.15l9.2 9.35-81.1-19.05zm82.5 20.47v.02a.5.5 0 0 0 .14.1l15.3 7.65-91.44-5.62 76-2.15z

We end up with some NaNs in bézier curves converted from arcs. It appears that the NaN is produced in find_center when center_denom is equal to zero.

Add ellipses back to the basic_shapes tessellators

Having ellipses would be useful for ggez. The API should have the subdivision computed in function of a tolerance threshold like all of the other tessellators, and maybe have a rotation parameter (equivalent to the x_rotation in arcs).

[Meta] lyon 1.0

I would like to start thinking of what a 1.0 version should be like, what's missing and what planned features belong to a later 2.0 version.

The 1.0 version should be about selecting a set of key features and getting them to a point where:

  • Their API is polished and stable (-ish)
  • These features are fully implemented. For example some tessellators are currently missing or partially implemented (don't generate normals).

Lyon 1.0 features

Tessellators that work on flattened paths

  • FillTessellator.
    • even-odd fill rule
    • robust (fuzzed)
    • generate vertex normals
  • StrokeTessellator
    • butt line caps
    • square line caps
    • round line caps
    • miter line joins
    • miter clip line joins
    • round line joins
    • bevel line joins
  • stroke-to-fill conversion
  • variable stroke width

Implement circle stroke tessellation.

A function stroke_circle should be added in basic_shapes.rs. The interface would be similar to fill_circle, using a GeometryBuilder<StrokeVertex> for the output.

The other tessellation routines in the same file provide a good set of examples for how to tessellate specific shapes with the GeometryBuilder API.

Out of Memory Resize Issue

If you constantly resize the window of the example program for a while, it crashes with the following error message. This partially appears to be an issue with the glium library but I figured I would report it here as well.

radeon: Failed to allocate virtual address for buffer:
radeon:    size      : 57671680 bytes
radeon:    alignment : 131072 bytes
radeon:    domains   : 4
radeon:    va        : 0x00000001fce80000
radeon: Failed to allocate virtual address for buffer:
radeon:    size      : 62914560 bytes
radeon:    alignment : 131072 bytes
radeon:    domains   : 4
radeon:    va        : 0x00000001fce80000
radeon: Failed to allocate virtual address for buffer:
radeon:    size      : 62914560 bytes
radeon:    alignment : 131072 bytes
radeon:    domains   : 4
radeon:    va        : 0x00000001fce80000
radeon: Failed to allocate virtual address for buffer:
radeon:    size      : 62914560 bytes
radeon:    alignment : 131072 bytes
radeon:    domains   : 4
radeon:    va        : 0x00000001fce80000
radeon: Failed to allocate virtual address for buffer:
radeon:    size      : 62914560 bytes
radeon:    alignment : 131072 bytes
radeon:    domains   : 4
radeon:    va        : 0x00000001fce80000
Debug message with high or medium severity: `GL_OUT_OF_MEMORY in Resizing framebuffer`.
Please report this error: https://github.com/tomaka/glium/issues
Backtrace:
   1 - 0x55b12b71c365
         _ZN9backtrace9backtrace9libunwind5traceE at /home/mike/.cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.1.8/src/backtrace/libunwind.rs:54
         _ZN9backtrace9backtrace5traceE at /home/mike/.cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.1.8/src/backtrace/mod.rs:67
   2 - 0x55b12b5ea61d
         _ZN5glium7context22default_debug_callbackE at /home/mike/.cargo/registry/src/github.com-1ecc6299db9ec823/glium-0.14.0/src/context/mod.rs:843
   3 - 0x55b12b5ea6df
         _ZN156fn$LP$debug..Source$C$$u20$debug..MessageType$C$$u20$debug..Severity$C$$u20$u32$C$$u20$bool$C$$u20$$RF$str$RP$$u20$$u7b$context..default_debug_callback$u7d$21fn_pointer_shim.6389917h8520cec335b0afa7E at <unknown>:??
   4 - 0x55b12b65a3e8
         _ZN5glium7context19init_debug_callback16callback_wrapperE at /home/mike/.cargo/registry/src/github.com-1ecc6299db9ec823/glium-0.14.0/src/context/mod.rs:932
   5 - 0x7f5dd8d57d4c
         <unknown> at <unknown>:??
   6 - 0x7f5dd8dc7b93
         <unknown> at <unknown>:??
   7 - 0x7f5dd8eca51c
         <unknown> at <unknown>:??
   8 - 0x7f5dd8ecb87b
         <unknown> at <unknown>:??
   9 - 0x7f5dd8e6ce01
         <unknown> at <unknown>:??
  10 - 0x7f5dd8e753b2
         <unknown> at <unknown>:??
  11 - 0x55b12b68a1d0
         _ZN5glium2gl8{{impl}}5ClearE at /home/mike/Development/Rust/Cargo Projects/glutin-test/target/debug/build/glium-97205cf9eb2b0132/out/gl_bindings.rs:7791
  12 - 0x55b12b5b80c9
         _ZN5glium3ops5clear5clearE at /home/mike/.cargo/registry/src/github.com-1ecc6299db9ec823/glium-0.14.0/src/ops/clear.rs:121
  13 - 0x55b12b579052
         _ZN5glium8{{impl}}5clearE at /home/mike/.cargo/registry/src/github.com-1ecc6299db9ec823/glium-0.14.0/src/lib.rs:1128
  14 - 0x55b12b578efa
         _ZN5glium7Surface25clear_color<glium::Frame>E at /home/mike/.cargo/registry/src/github.com-1ecc6299db9ec823/glium-0.14.0/src/lib.rs:673
  15 - 0x55b12b52910e
         _ZN11glutin_test4mainE at /home/mike/Development/Rust/Cargo Projects/glutin-test/src/main.rs:224
  16 - 0x55b12b799bd8
         _ZN3std9panicking3try4call17h852b0d5f2eec25e4E at <unknown>:??
  17 - 0x55b12b7a1b7b
         __rust_try at <unknown>:??
  18 - 0x55b12b7a1b1e
         __rust_maybe_catch_panic at <unknown>:??
  19 - 0x55b12b79967e
         _ZN3std2rt10lang_start17hfe4efe1fc39e4a30E at <unknown>:??
  20 - 0x55b12b59c199
         main at <unknown>:??
  21 - 0x7f5dde34a740
         __libc_start_main at <unknown>:??
  22 - 0x55b12b525ea8
         _start at <unknown>:??
  23 - 0x0
         <unknown> at <unknown>:??

error: Process didn't exit successfully: `target/debug/glutin_test` (signal: 11, SIGSEGV: invalid memory reference)

Add a software triangle rasterizer

This would be very useful for reftests, and as a fallback when graphics drivers aren't working well.
It would also be interesting to see how close to a classic CPU path rasterizer we can get with something like this.
There's an empty function waiting to be implemented in extra/src/triangle_rasterizer.rs.

Experiment with a high level API on top of the tessellators

I've started working on this in the lyon_renderer crate. I haven't quite figured out the design and scope yet, but it should at least:

  • Work with gfx-rs.
  • Implement some basic patterns:
    • color
    • image
    • gradient
  • Optimize for animated scenes where the vertex geometry is mostly static (stays in GPU memory) but some properties like transform, width or color can change dynamically.
  • Handle batching and primitive sorting internally.
  • Most importantly, make it a lot easier to use lyon (at least with gfx-rs).

Implement UpToTwo::push

UpToTwo<T> is a simple stack allocated container that can contain zero, one or two elements. It is currently implemented in the bézier crate (see up_to_two.rs). It would be handy to have a method push (which would panic if the container already has two elements).

Cannot run the gfx_advanced example with_multisampling : thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: NoAvailablePixelFormat'

Tried to run the gfx_advanced example on my Arch linux laptop, and it crashed during the "gfx_window_glutin::init" call.

I've done a bit of heuristics since I was able to run the gfx_basic example, and it turns out I'm able to run the example as long as the ".with_multisampling(8)" part of the glutin::WindowBuilder::new() method is commented out :

` // Initialize glutin and gfx-rs (refer to gfx-rs examples for more details).

let glutin_builder = glutin::WindowBuilder::new()
    .with_dimensions(700, 700)
    .with_decorations(true)
    .with_title("tessellation".to_string())
    //.with_multisampling(8) // This line causes a crash
    .with_vsync();   `

Currently using my Intel graphics card "VGA compatible controller: Intel Corporation HD Graphics 530 (rev 06)" (I have no idea if it's any use).

Here is a report of the rust backtrace :

gfx_advanced git:(master) ✗ export RUST_BACKTRACE=1; cargo run Compiling gfx-rs advanced example v0.1.0 (file:///home/ignition/Documents/Projects/rust/lyon/examples/gfx_advanced) warning: unused import:DepthStencil`
--> src/main.rs:29:24
|
29 | use gfx_core::format::{DepthStencil, Rgba8};
| ^^^^^^^^^^^^
|
= note: #[warn(unused_imports)] on by default

Finished dev [unoptimized + debuginfo] target(s) in 3.48 secs
 Running `/home/ignition/Documents/Projects/rust/lyon/target/debug/gfx_advanced`

== gfx-rs example ==
Controls:
Arrow keys: scrolling
PgUp/PgDown: zoom in/out
w: toggle wireframe mode
p: toggle showing points
b: toggle drawing the background
a/z: increase/decrease the stroke width
-- fill: 460 vertices 1416 indices
-- stroke: 1292 vertices 3816 indices
thread 'main' panicked at 'called Result::unwrap() on an Err value: NoAvailablePixelFormat', /checkout/src/libcore/result.rs:859
stack backtrace:
0: std::sys::imp::backtrace::tracing::imp::unwind_backtrace
at /checkout/src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
1: std::sys_common::backtrace::_print
at /checkout/src/libstd/sys_common/backtrace.rs:71
2: std::panicking::default_hook::{{closure}}
at /checkout/src/libstd/sys_common/backtrace.rs:60
at /checkout/src/libstd/panicking.rs:355
3: std::panicking::default_hook
at /checkout/src/libstd/panicking.rs:371
4: std::panicking::rust_panic_with_hook
at /checkout/src/libstd/panicking.rs:549
5: std::panicking::begin_panic
at /checkout/src/libstd/panicking.rs:511
6: std::panicking::begin_panic_fmt
at /checkout/src/libstd/panicking.rs:495
7: rust_begin_unwind
at /checkout/src/libstd/panicking.rs:471
8: core::panicking::panic_fmt
at /checkout/src/libcore/panicking.rs:69
9: core::result::unwrap_failed
at /checkout/src/libcore/macros.rs:29
10: <core::result::Result<T, E>>::unwrap
at /checkout/src/libcore/result.rs:737
11: gfx_window_glutin::init_raw
at /home/ignition/.cargo/registry/src/github.com-1ecc6299db9ec823/gfx_window_glutin-0.14.0/src/lib.rs:101
12: gfx_window_glutin::init
at /home/ignition/.cargo/registry/src/github.com-1ecc6299db9ec823/gfx_window_glutin-0.14.0/src/lib.rs:53
13: gfx_advanced::main
at ./src/main.rs:257
14: __rust_maybe_catch_panic
at /checkout/src/libpanic_unwind/lib.rs:98
15: std::rt::lang_start
at /checkout/src/libstd/panicking.rs:433
at /checkout/src/libstd/panic.rs:361
at /checkout/src/libstd/rt.rs:57
16: main
17: __libc_start_main
18: _start
`
I'd love to dig into it a bit more, but I feel kind of lost ^^

Make the project more welcoming and appealing to contributors and users.

Some rust projects have done a stellar job at moving from being a one-person project into being owned and contributed to by a small community built around it. The gfx crate is a prime example of this.

I would very much like lyon to be more community-driven, so that the project advances faster and in a direction that is useful to more people, and have more people to brainstorm ideas with.

Some ideas off the top of my head:

  • Good documentation: a never ending endeavor, but there has been a lot of work in this area lately.
  • Make lyon easier to use: The tools provided like tessellators are (purposefully) quite low-level and it is a lot of work to use them in any project. Building higher level APIs on top of this could maybe help with being useful for more people? I am experimenting with higher level APIs currently (issue #17).
  • File more issues for newcomers to pick, advertise them in this-week-in-rust.
  • Make better issues (more detailed) to help contributors getting started.
  • Implement more functionalities: There is still a ton of things to do, perhaps some people are waiting for some key missing features to be implemented?
  • Make more interesting demos that show what lyon can offer.
  • Move the repository from my github account into a dedicated github organization.
  • Reduce the complexity of the code if possible.

Incorrect cubic bézier flattening near inflection points.

I wrongly assumed that we could get away with splitting curves at the inflection points without evaluating the linear approximation range around the inflections, but in some cases the flattening approximation runs into float precision issues due to from ctrl1 and ctrl2 being almost aligned produces a very small cross product that we use as divisor in no_inflection_flattening_step.

The following curve exhibits the problem when tessellated with a tolerance of 0.01:

    CubicBezierSegment {
        from: point(6.0, 400.0),
        ctrl1: point(150.0, 80.0),
        ctrl2: point(500.0, 400.0),
        to: point(695.0, 193.0),
    }

I'll have to bring back the inflection approximation range code.

Implement finding the intersections between two quadratic bezier curves

Given two y-monotone quadratic bezier curves, the function should return up to three intersections.

pub enum QuadraticBezierInteresction { None, One(f32), Two(f32, f32), Three(f32, f32, f32) };
pub fn monotone_quadratic_bezier_intersection(a: &QuadraticBezierSegment, b: &QuadraticBezierSegment) -> QuadraticBezierIntersection { ... }

In our case the curves are y-monotone (the control point's y coordinate is between the start and end points y coordinates, and the curve can be expressed as a function of y) which may simplify the problem.

flatten_cubic.rs find_cubic_bezier_inflection_points does not seem to return the inflections points correctly.

I was writing unit tests for #48 as I notices I don't get the correct number of Inflection points returned by the find_cubic_bezier_inflection_points function.

A unit test helped me isolate the bug :

`
#[test]
fn find_cubic_bezier_inflection_points_for_simple_segment() {
let a = CubicBezierSegment {
from: Point::new(0.0, 0.0),
ctrl1: Point::new(0.5, 1.0),
ctrl2: Point::new(1.5, -1.0),
to: Point::new(2.0, 0.0),
};

    let expected_inflections_count = 2;

    let actual_inflections_count = find_cubic_bezier_inflection_points(&a).len();

    assert!(expected_inflections_count == actual_inflections_count, "got {} inflection points", actual_inflections_count)
} 

`
which returns :

---- flatten_cubic::find_cubic_bezier_inflection_points_for_simple_segment stdout ---- thread 'flatten_cubic::find_cubic_bezier_inflection_points_for_simple_segment' panicked at 'got 1 inflection points', src/flatten_cubic.rs:270

I'm supposed to get Two inflection points, but I don't.

I don't know if I don't use the API as I'm expected to or not :/

Remove or Refactor the "normal" path events.

There are several path/event abstractions with varying capabilities:

  • Flattened paths work with absolutely positioned line segments only (no curves). This is what the tessellators operate on.
  • Quadratic paths work with absolutely positioned lines and quadratic bezier segments. In the long run the tessellators should operate on this.
  • "Normal" path events work with lines, quadratic beziers and cubic beziers (absolute positions only).
  • SVG paths provide all SVG 1.1 path functionalities (including relative positions).

The "normal" path abstraction isn't very useful. We should either remove it or make it an absolutely positioned version of SVG paths (in which case it should support arcs).

Document the lyon_path_iterator crate.

The path_iterator sub-crate needs some proper documentation (see TODO in path_iterator/src/lib.rs). The crate documentation need at least an Overview section and an Examples section.

Flattening certain cubic béziers does not work

Flattening this path results in a straight line:

m 11.71726,9.07143 c -9.827381,4.15774 6.425594,10.20536 6.425594,10.20536

Result:

img1

Segment: Relative MoveTo { x: 11.71726, y: 9.07143 }
Segment: Relative CurveTo { x1: -9.827381, y1: 4.15774, x2: 6.425594, y2: 10.20536, x: 6.425594, y: 10.20536 }
From (11.71726,9.07143) to (18.142855,19.27679) via (1.889879,13.22917) and (18.142855,19.27679)
 o 18.142855,19.27679

But when tweaking it just a little bit (e.g. changing the first value from 11.7... to 11.8...) it works:

m 11.81726,9.07143 c -9.827381,4.15774 6.425594,10.20536 6.425594,10.20536

img2

Segment: Relative MoveTo { x: 11.81726, y: 9.07143 }
Segment: Relative CurveTo { x1: -9.827381, y1: 4.15774, x2: 6.425594, y2: 10.20536, x: 6.425594, y: 10.20536 }
From (11.81726,9.07143) to (18.242853,19.27679) via (1.989879,13.22917) and (18.242853,19.27679)
 o 9.218064,10.766278
 o 8.6632,12.285181
 o 9.291998,13.824333
 o 11.29783,15.699478
 o 15.09445,17.905602
 o 18.242853,19.27679

The second control point and the end are equal, not sure if that causes an edge case.

Implement vertex anti-aliasing

The idea of vertex-aa is to extrude an 1px wide strip along the edge of a shape with a gradient. It should not be too hard to do for strokes, but trickier for fills especially in cases with self-intersections.

Explain CubicFlatteningIter tolerance

Hi. Great library, thanks a lot! :)

I used the Bézier part to do flattening of SVG paths. Could you maybe explain the tolerance value in the documentation in laymans terms? From my experiments, the lower the value the better the approximation. But what does the value actually mean? Does it have to do with the angle between two line segments?

(I should probably read the paper, but adding a short explanation to the docs would also help other people :))

Simplify the flattening code

The flattening algorithm is implemented both as a builder and an iterator. The iterator version is cleaner (although it might be a tad slower). It's worth measuring the performance impact of implementing the builder on top of the iterator to remove some quite nasty code.

Another thing to try is remove the approximation of the inflection points. Just getting rid of the inflection points by splitting the curve there and evaluating everything with no_inflection_flattening_step should yield almost identical results (at most one extra segment) and further simplify the code.

In gfx_advanced example, the logo can't show.

== gfx-rs example ==
Controls:
  Arrow keys: scrolling
  PgUp/PgDown: zoom in/out
  w: toggle wireframe mode
  p: toggle show points
  a/z: increase/decrease the stroke width
 -- fill: 557 vertices 1707 indices
 -- stroke: 1270 vertices 3810 indices

rustc 1.19.0-nightly (75b056812 2017-05-15)

macOS 10.12.4

Make the source code easier to unserstand and discover.

A followup issue from discussions in #32.

Relevant comment from @Drakulix:

[...] I have a hard time to figure out what parts of it can be used in combination and how they should fit together.

[...] I don't feel like I would know where to start without studying the examples in great detail at first (which was even more difficult, before you added the new simpler example).

This could most likely be resolved by some explanation and maybe some smaller examples in the giant meta-crate. That would be the place, I would expect a gentle introduction about how to start using this project.

Looks like we need at least:

  • A "getting started" section in the documentation of the meta-crate with examples.
  • More standalone examples preferably as simple and focused as possible.
  • More detailed explanations about which crates are useful for what, which crates are optional and how the crates interact with one another.

Add fuzz testing for the fill tesselator

Generating random paths and running the fill tessellator on them would help with finding bugs. There are also some good fuzzers out there (like afl) that could be useful.

Use a better respresentation for paths

Paths are currently implemented as an array of struct PointData { position: Vec2, point_type: PointType }.
This is convenient because we can easily find the previous and next of a point which the tesselator needs, and VertexIds end up matching with indices in the generated index buffer, but it isn't a flexible representation and could be made more compact.

Each path event would begin with a header, and the event parameters (positions, etc) would be stored immediately after that with a variable length. The header contains the information needed to iterate forward and backward, and VertexId becomes a byte offset in the buffer rather than an index in an array.

EventHeader {
event_type: EventType, // move_to, line_to, quadratic/cubic bezier, etc..
next_offset: u8,
previous_offset: u8,
}

Each sub-path would begin with another header, and the PathId would be the byte offset of this header in the array.

The path itself would have a descriptor that details the size and type of content in each vertex. The default would be a pair of f32 for the typical 2d path, but some other data could be added optionally such as a line width, a color, etc.

TODO: The way the VertexId lines up perfectly with an array offset is pretty convenient for the generation of the index buffer in the tesselator. We need some way to keep generating indices efficiently. This could probably be done by storing the index in the EventVector.

Figure out a good and stable API for the fill tessellator

Currently the tessellator takes a PathSlice as input and a VertexBufferBuilder as output parameter. The API does not take any options (such as enabling vertex-aa).

In order, to have the option to render quadratic curves on the GPU, we need a more elaborate output interface than VertexBufferBuilder, that would separate "interior" triangles and quadratic curve triangles. Vertices should have a normal vector when using vertex-aa.

As for the input type, it might be more efficient to have a separate FillTessEvents type (equivalent of the current private path_fill::Events struct) that is constructed either directly or from a path, and have the fill tessellator use it as input. This way we could skip allocating and building the Path if we build the FillTesselatorEvents representation directly.
We would build a FillTessEvents using something that implements path_builder::PrimitiveBuilder.

Implement 2d triangle vs triangle intersection test.

We need a function in core/src/math_utils.rs which would look like:

/// Returns true if the triangle t1 intersects t2.
pub fn triangle_intersection(t1: &[Point], t2: &[Point]) -> bool;

In case it helps, there is already a triangle_contains function to check if a triangle contains a point, and the function segment_intersection in math_utils.rs.

Implement finding whether a path has self intersections

The intersection test is about half of the time spent in the tessellator. FastUIDraw has a pre-pass where it detects whether a path has self intersections and runs a special fast-path tessellator if there is no intersections (which should be the common case).
I'd like to experiment with something like this.

Edit: actually FastUIDraw may not have this pre-pass not sure where I got that from.

[bikeshed] Should the bézier crate expose traits for the common methods of bezier curves?

Quadratic and cubic bézier curves have some APIs in common. Should we define traits exposing these methods generically? If so, should we have a single trait (say, Curve or BezierCurve, that has all of the common methods, or have several smaller traits (Sample, Split, BoundingRect, Flatten, etc.), or a mix of both (a set of small traits and a super trait that derives them all)?

I'd love to get some feedback on this. What are the use-cases, and what are the idiomatic practices for this?

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.