search

Yellow-Dog-Man / Resonite-Issues

Issue repository for Resonite.
https://resonite.com
141 stars 2 forks source link

Implement polygon triangulation algorithm #1523

Open Frooxius opened 8 months ago

Frooxius commented 8 months ago

Is your feature request related to a problem? Please describe.

FrooxEngine has a class for working with mesh data. This includes a number of methods to make mesh manipulation and generation simpler, on which a lot of the procedural meshes are made.

However one notable algorithm that is currently missing is a polygon triangulation algorithm, which given a loop of vertices, will generate triangles to properly fill this loop.

Describe the solution you'd like

Implement a good polygon triangulation algorithm. Here's more info for context: https://en.wikipedia.org/wiki/Polygon_triangulation

Describe alternatives you've considered

Integrating 3rd party libraries which includes this algorithm, but this would be needlessly heavy and make dependency on potentially big libraries.

Additional Context

Having this algorithm would allow for building a lot new procedural meshes and other functionality, such as procedural mesh text and be a building block for 3D modelling functionality in the future as well.

It will allow adding more procedural meshes too.

Requesters

No response

Banane9 commented 8 months ago

When importing models with polygons so far, they seemed to be handled fine - unless the polygons were concave. 🤔

JackTheFoxOtter commented 8 months ago

When importing models with polygons so far, they seemed to be handled fine - unless the polygons were concave. 🤔

This has nothing to do with importing, read the ticket again. It's a function useful for generating procedural meshes, specifically generating triangles to fill in polygons (vertex loops).

Frooxius commented 8 months ago

Assimp does have an algorithm that handles triangulation on import, but that's specifically that - importing existing meshes.

This issue is for stuff like in-engine procedural generation and mesh manipulation.

Banane9 commented 8 months ago

This has nothing to do with importing, read the ticket again. It's a function useful for generating procedural meshes, specifically generating triangles to fill in polygons (vertex loops).

Yes, I did read that, but since Froox was talking about implementing algorithms for it, I was wondering in which part that gets handled.

Assimp does have an algorithm that handles triangulation on import

Would it make sense to check if that could be used for meshes in general, or is it too specific?

Frooxius commented 8 months ago

The "Describe alternatives you've considered" section covers that. It's not a good fit for this purpose.

Banane9 commented 8 months ago

The "Describe alternatives you've considered" section covers that.

Well, not quite since there's already a dependency on Assimp anyways - using it for arbitrary triangulation would just be a bonus.

It's not a good fit for this purpose.

But if that applies to Assimp, implementing triangulation directly makes the most sense, I suppose.

Frooxius commented 8 months ago

The "Describe alternatives you've considered" section covers that.

Well, not quite since there's already a dependency on Assimp anyways - using it for arbitrary triangulation would just be a bonus.

1) Assimp doesn't expose this directly for usage, which would require modifications, interop and so on 2) I specify that it's also needlessly heavy in the section, not just the dependency part 3) Assimp is a native library, which would make this work only on platforms we compile it for (which adds to the heaviness), rather than quick in-line algorithm