[FEATURE] - Add Concave cross-section triangulation

[DavidArayan]

Investigate a proper method to add cross-section triangulation for concave slices. Currently looking at EarClip Triangulation algorithm.

Since the silhouette (and direction) of triangles is known at runtime, it should simplify the triangulation process for concave objects. If a proper order of vertices can be built during the cutting process, the triangulation should be able to handle both concave object cuts and objects with holes. The Vertex winding order can be determined by the facing direction of the original triangle.

The EarClip Triangulation runs in O(n^2) complexity compared to O(nlog(n)) of the Monotone Chain. This means cutting concave objects will have a bit of a performance impact. There is also a scenario where a concave object slice can yield 3 or more "separate" objects. Weather that should be handled properly or not is up for debate, at the very least it does not seem to be a trivial problem to handle.

Will begin investigation once the threading framework is complete.

[mikebind]

This is the key feature for me! I have complex non-convex meshes that I want to make single plane cuts through. Performance is not a major issue for for me; it's OK if it takes a noticeable length of time to generate the new meshes. Do you have any estimate as to when this feature might become available? The current code is great and very easy to use for convex meshes. Thanks!

[DavidArayan]

Hello @mikebind,

Thank you for reaching out. I'm currently in a process of open-sourcing a Voxel based framework which i've been working on for a while. Since a-lot of work has gone into the Voxel framework, I'll be borrowing some of its code to solve the Concave triangulation problem.

In addition, I'll be looking into migrating the slicing and triangulation into the new Unity's Job system to make things run super fast!

In the meantime, feel free to do some pull requests or contribute some ideas on how to make the slicing framework better, I always take everything into account!

Cheers.

[mikebind]

Thanks, I'm pretty new to Unity and c#, so I don't have a lot to contribute at this point, but I'll keep an eye on this project to see if there is a way I could help. Thanks, Mike

…

On Thu, Nov 15, 2018, 3:16 PM David Arayan ***@***.***> wrote: Hello @mikebind <https://github.com/mikebind>, Thank you for reaching out. I'm currently in a process of open-sourcing a Voxel based framework which i've been working on for a while. Since a-lot of work has gone into the Voxel framework, I'll be borrowing some of its code to solve the Concave triangulation problem. In addition, I'll be looking into migrating the slicing and triangulation into the new Unity's Job system to make things run super fast! In the meantime, feel free to do some pull requests or contribute some ideas on how to make the slicing framework better, I always take everything into account! Cheers. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#8 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ADzB46hUCLEm8iCqO3wlLTMDUOFaojO9ks5uvfXcgaJpZM4R8Ooj> .

[vizgl]

Hello @mikebind,

Thank you for reaching out. I'm currently in a process of open-sourcing a Voxel based framework which i've been working on for a while. Since a-lot of work has gone into the Voxel framework, I'll be borrowing some of its code to solve the Concave triangulation problem.

In addition, I'll be looking into migrating the slicing and triangulation into the new Unity's Job system to make things run super fast!

In the meantime, feel free to do some pull requests or contribute some ideas on how to make the slicing framework better, I always take everything into account!

Cheers.

Do you still planning add support for concave meshes?

[DavidArayan]

Hello @vizgl,

Yes, unfortunately I haven't had the time to continue working on any of my open source projects, when you're working 8-10 hours a day at a paid job it's hard to come back home and do more coding!

At some point i'd like to complete all features and release this as a package in unity store for free (once i'm happy with everything).

[The-MAZZTer]

At the dawn of time someone made a model used for prerendering. It was like a billion polygons and never meant for such trivialities such as animation or real-time rendering.

Cut to recently and someone else decided that poor The MAZZTer should be tasked with dropping the 3gb model into Unity.

Then I was asked to make it change colors over time in response to external data, but that would be it. Fine.

Then I was asked to optimize it. I zoomed in to find every bolt, nut, screw, rivet, and holes for all of those were all individually painstakingly modeled. I hid them all to gain precious frames back. Then they wanted to hide and show different parts of it. Ok. Then they wanted part of it to go transparent. I can do that. Then they wanted it to sing and dance (animate). I did my best but I am no animator.

NOW they want me to carve it up like a turkey.

@DavidArayan you are a lifesaver. But of course the model is more concave than a modern art statue piece. So with the current inner-face generation algorithm it doesn't look quite right and this improvement would be nice to see.

[DavidArayan]

Unfortunately triangulating concave objects with holes, multiple segments or other edge cases is not trivial. I could get something up and running by creating some kind of editor that asks for manual user input to provide more data to the triangulation algorithm (like some other slicer examples i've seen) but that's not how I operate and would never be happy with the outcome.

I'm fundamentally slothful, everything should work without additional user input. Ideally a solution can be made that works the same way as convex slices where you slice and it all magically works!

This code was released sometime in 2017? 2018? I can't even remember. Regardless its starting to show its age. Perhaps the next big iteration would allow me to sit down and focus on how to solve these kinds of problems.

If I ever land some contract work that actually requires this or similar algorithm would be a good excuse to sit down and solve this problem properly. Maybe one of the game studios would be interested?

[iNakel]

I've tried a lot of assets and resources to solve this... so far I have found 2.

-PrimitivesPro (AssetStore).- it does support non convex mesh triangulation, but in some little cases it fails.
-ComputationalGeometry (https://github.com/Habrador/Computational-geometry).- not very fast and doesn't work with all the meshes.

The non trivial problem seems to be on the vertices arrangement... I hope those assets can help if you still want to improve your asset!

I'm also willing to donate and support the cause!

[DavidArayan]

hey @iNakel Thank you for reaching out!

I'm actively working on a new open-source game engine project with TypeScript/WebGL and have plans to port over this framework to Typescript. During the port i'll be looking into the concave issue aswell and hopefully can come up with an acceptable technique that works. If the TypeScript version performs well its likely i'll port it back into C#/Unity3D.