Concave Brushes

[gildedhipbone]

I assume this happens because concave brushes are currently not supported. I'm curious about the implementation of concave brushes. Is it a matter of automatically converting a shape like the above to a set of convex brushes?

[Henry00IS]

Yes that's correct, and it could be treated identical to the 2D Shape Editor, that too converts a polygon or shape to multiple convex brushes. But it may be confusing to users if they end up with multiple (possibly oddly shaped) brushes or a ShapeEditorBrush.

I asked @sabresaurus whether we could just do this internally, hide it from the user that concave brushes are split into convex ones automatically but he pointed out that the shape of a bowl would essentially cause a brush for every polygon and that would slow things down significantly. So it may not be wise to do so even if it would give us full concave shape support.

If anything we have to wait for him to finish his game and have enough spare time to improve the CSG algorithm and add actual concave brush support to SabreCSG.

[gildedhipbone]

I see. I agree that the handling of such brushes should be done internally - to the average user (myself included) the most intuitive behavior would be to treat any shape as a "normal" brush. When I'm designing a level I'm not concerned with how things work under the hood.

Regarding the bowl example, are you saying things would slow down because of the sheer amount of brushes that the algorithm would have to handle? And/or is it a data structure issue?

[Henry00IS]

If we were to go ahead with splitting them into several convex brushes so that the current algorithm can handle concave shapes, that alone is a time intensive calculation but yes the sheer amount of brushes is worrying, some shapes will create a few, some may yield several hundred brushes. Building times could easily go up to several minutes. I experienced this first hand with initial tests of the 2D Shape Editor generating hundreds to thousands of brushes (triangulation, a brush for every triangle).

The current algorithm uses convex hulls to determine whether a point is inside or outside of another brush. I can't tell you any exact details because I have yet to fully understand all of the inner workings of the algorithm. The Sabresaurus has done research on concave brushes and was considering rewriting the core build code again with the idea of removing floating point operations completely (some initial experiments have been done already) and possibly changing some of the input representations to planes and indexed edges. Already there is working code for multi-threading in this version of SabreCSG that, if someone were to clean it up, could make all future build times complete in a fraction of a second. Who knows just how much else he was about to do but unfortunately SabreCSG never came close to supporting itself in terms of revenue and he ran out of money. Right now he doesn't have any spare time left. We will have to be patient and hope that he will have more time in the future to tinker with SabreCSG and update the core build code to officially support concave brushes without relying on our proposed "hack".

I took it upon myself to maintain the project during his absence to the best of my ability so that his inevitable return to the project is smooth with a clean code base. I also really didn't want to see SabreCSG fade away into obscurity because I love it so much. With the recent activity in this amazing community it appears I am not the only one that loves this project. 😁

[gildedhipbone]

Interesting! Thank you. I'm not an experienced programmer of any sort, but I enjoy this discussion at a conceptual level if nothing else.

If I've understood you (and other sources) correctly, the heart of the matter is not getting around the requirement that concave brushes are built from convex brushes, bur rather doing this in a way that is both fast and robust.

Couple of questions: 1) Re floating point operations - I assume this means incorporating fixed point operations, then? Are you leveraging one of the existing fixed point libraries for this (like https://github.com/asik/FixedMath.Net)? 2) Indexed edges - does SabreCSG use half-edge data structures? I've read that such structures are useful in CSG contexts, so I'm curious if SCSG uses them.

And you're definitely not alone in loving SabreCSG! While it's a shame that sabresaurus couldn't support himself on SCSG, I think it's a great boon to the Unity community that there's an open-source CSG editor with as strong a foundation as SCSG available.

By the way, is there a maintained SabreCSG thread on the Unity forums? sabresaurus understandably doesn't have time to update the old one. It might be a good idea to create a new thread, perhaps in a couple of version updates...

[Henry00IS]

1. Re floating point operations - I assume this means incorporating fixed point operations, then? Are you leveraging one of the existing fixed point libraries for this (like https://github.com/asik/FixedMath.Net)?

Yes, here is my version of the library modified for SabreCSG.

And here is the experimental version of SabreCSG using fixed point arithmetic, I can't say it works properly but it's just a proof of concept. I probably converted too much code into fixed point arithmetic (every single float I could find pretty much) breaking a couple things.

I assume the worst problem is brush placement and modifications in Unity, they use floats so the entire brush is corrupted, polygons are not aligned properly and there may be gaps between the brushes, not visibly but rather in the math when you have such precise numbers. It would require a lot more work than just replacing floats. Like having a fixed point representation of what a brush looks like and any float operations from Unity affect the fixed point representation accurately with some constraints i.e. without damaging it.

2. Indexed edges - does SabreCSG use half-edge data structures? I've read that such structures are useful in CSG contexts, so I'm curious if SCSG uses them.

As far as I know all the code currently revolves around polygons and convex hulls. Perhaps that's what he wanted to look into at the time. Please correct me if I'm wrong.

By the way, is there a maintained SabreCSG thread on the Unity forums? sabresaurus understandably doesn't have time to update the old one. It might be a good idea to create a new thread, perhaps in a couple of version updates...

I like that idea, perhaps we should wait a little longer and get even more features in before we do so. Make sure we have something that can overwhelm the competition. ;)

And you're definitely not alone in loving SabreCSG! While it's a shame that sabresaurus couldn't support himself on SCSG, I think it's a great boon to the Unity community that there's an open-source CSG editor with as strong a foundation as SCSG available.

❤️

[Henry00IS]

If I've understood you (and other sources) correctly, the heart of the matter is not getting around the requirement that concave brushes are built from convex brushes, bur rather doing this in a way that is both fast and robust.

There are algorithms that can handle concave shapes. But in general try finding any literature on CSG operations and you will end up with scientific research papers only the Sabresaurus can read. The only recent article explaining it is "Real Time Constructive Solid Geometry" in the book "Game Development Tools". But that was written by our competition, we can't take too much advice from it without getting into trouble! 😛

Edit: Not sure if they cover concave shapes, I doubt it, but I meant CSG operations/literature in general.

[Henry00IS]

I was extremely lucky yesterday and Sabresaurus was available to answer some questions, here's what he had to say on our idea:

Concave support through convex decomposition is definitely viable, my main concern is transparency. As long as the user understands what’s going on and that it’s a bad idea to build a bowl brush then it’ll work. So even if you have a single concave brush perhaps it should clearly mark the convex splits so that you understand the hidden complexity.

Showing additional wireframe lines in a separate color or some additional thickness should give a visual clue. So I guess we could go ahead and implement a prototype sometime in the near future.

[gildedhipbone]

That sounds like a sensible solution. Maybe throw a message if SCSG detects an abnormally long build time, suggesting the user dials down the use of concave brushes and/or splits the work into multiple CSG models.

Either way, concave support is a step in the right direction. :)