Extrudable not implemented for Polygons

[AnjanaYEAH]

Hi,

Beginner Rust and Bevy developer here!

I don't see why RegularPolygons are extrudable and Polygons are not extrudable https://docs.rs/bevy/latest/bevy/render/mesh/trait.Extrudable.html

The code below does not work with the following error message:

the trait From<bevy::prelude::Extrusion<bevy::prelude::Polygon<_>>> is not implemented for bevy::prelude::Mesh, which is required by bevy::prelude::Extrusion<bevy::prelude::Polygon<_>>: Into<bevy::prelude::Mesh>

fn spawn_polygon(
    mut commands: Commands,
    mut materials: ResMut<Assets<StandardMaterial>>,
    mut meshes: ResMut<Assets<Mesh>>,
) {
    let points2d = vec!
        [
            vec2(-6., 2.),
            vec2(-2., 4.),
            vec2(-3., 5.)
        ];
    let p = Polygon::new(points2d);
    let e = Extrusion::new(p, 2.0);
    let mesh_handle: Handle<Mesh> = meshes.add(e);

    commands.spawn((
        PbrBundle {
            mesh: mesh_handle,
            material: materials.add(StandardMaterial {
               base_color: Srgba::hex("#ffd891").unwrap().into(), 
                ..default()
            }),
            ..default()
        },
        Cube,
    ));
}

I want to be able to create custom polygons and extrude them, not sure why this is not possible at the moment? Happy to help implement this with some guidance :)

[alice-i-cecile]

Yep, feel free to implement this :) @mweatherley and possibly @IQuick143 or @tychedelia may have advice on the exact implementation.

[IQuick143]

I believe the issue is related to us not even implementing Meshing for Polygons, the reason being you can have Polygons represent various ugly concave or even self-intersecting shapes.

Extrusion is one step after that.

Meshing for concave polygons is not an impossible problem, I could draft up some algorithm, although I give no guarantees about how the topology of the mesh will look.

As for self-intersecting polygons... idk.

[lynn-lumen]

If we are fine with adding another dependency, we could give libraries like earcutr a try. In my experience, they work very well :)

[IQuick143]

I'm not sure if we should introduce a dependency for such a relatively niche feature, but the ear-clipping algorithm looks pretty much exactly like what we want if we implement this.

[alice-i-cecile]

Yeah, I'm loathe to add a dependency for a very optional feature.

[lynn-lumen]

We should also consider how we handle self intersecting polygons. We could either

• apply a fill rule, e.g. non-zero or even-odd, or
• error.

I would personally prefer to use fill rules, but that would require dividing the polygon into simple polygons if it is not already simple, which may be more expensive, as it would add another O(n log n) operation. This will likely already be done by the triangulation algorithm though, so that may be fine :)

Fill rules, (the even-odd rule in particular), would imply an additional complexity when considering using the shape for maths purposes like ray-casting, or testing whether a point is inside the polygon though. So at the very least, we would need to make clear, that they are for rendering purposes only, and do not affect / cannot be used with the primitive in other contexts.

[IQuick143]

I'd mention that meshing a self-intersecting polygons can give you up to O(N^2) vertices, if your polygon is highly self-intersecting. And I'm not sure if this means that you can't avoid an O(N^2) algorithm, which checks all pairs of edges for intersections.

Example: A regular polygon (with a prime number > 5 of vertices), but the edges connect opposite instead of adjacent vertices.

[IQuick143]

Example visualisation from Desmos:

[lynn-lumen]

I'd mention that meshing a self-intersecting polygons can give you up to O(N^2) vertices, if your polygon is highly self-intersecting. And I'm not sure if this means that you can't avoid an O(N^2) algorithm, which checks all pairs of edges for intersections.

You can perform intersection tests in O(n log n) and mesh the polygon in O(n log n) aswell. Theoretically O(n) is possible for triangulation but that algorithm (Chazzele) is hardly attainable due to its complexity.

[NailxSharipov]

Hi all. I believe this issue aligns closely with the problems my libraries are designed to solve.

iOverlay – A robust 2D polygon Boolean library that also supports buffering (offsetting), and self-intersection resolution.

iTriangle – A general-purpose triangulation library for all kinds of polygons (even with holes, steiner points or self-intersections). It builds on iOverlay internally and reexports it for convenience.

And I made a small video how it's working with example in this topic.

I will be glad if you try it! and hope you enjoy it.