Robustness Questions

[a-day-old-bagel]

I wasn't sure if I should just keep talking in the other discussion I opened about my fork, but since this is a more general issue I'm running into, I thought I'd make a new discussion for it.

Anyway, were you mostly testing your algorithm with rectangular prism brushes, or did you try more exotic convex shapes, by any chance?

Specifically, I'm noticing that for a brush where more than three faces meet at the same point (or as close to the same point as floating point precision can allow), bad things happen.

At least, I believe I've narrowed down the cause to that case. If we look at rebuild_faces_and_box, we see:

if (try_make_vertex(facei, facej, facek, v) &&
    test(&v, brush) != RELATION_OUTSIDE)
        ...

But I think that test(&v, brush) is probably not catching the intended vertices as being outside the brush in the case where there are multiple 3-plane intersections all happening right on top of each other, or close enough to on top of each other to run afoul of the approx_equal in your point vs. face test.

So I'd be interested to know if you're able to reproduce these sorts of problems by trying to use brushes where more than three faces meet at a corner, but I understand if you don't have time to look into it right now. If you don't have any particular suggestion or comment, I might try adding vertex binning to your algorithm as a catch-all for "vertices on top of each other" sorts of problems.

Also I should have included some pictures, but it's kind of hard to decipher a screenshot of a malformed mesh when you don't also know what it's supposed to look like. But if it would help, I can probably get some pictures of simple repro cases.

EDIT: I realized I wasn't very specific about the "bad things," but basically the resulting meshes are coming out with what appear to be incorrectly flipped triangles in some places, and double-sided triangles in other places, and invisibly-skinny triangles glitching things out too. Some combination of all that stuff. Idk, it's hard to describe, and I should really get some screenshots.

[a-day-old-bagel]

To add: I think the reason that I've run into these cases is that I'm building an in-game editor that interfaces with the physics engine I'm using, and the workflow goes something like this:

1. User has a view of a convex hull that they can edit by dragging points, edges, or faces around.
2. Upon editing a convex hull, the physics engine provides me with the planes that define the hull.
3. Since the planes are derived from a set of points, it's common for more than three edges of the hull to meet at a single point
4. tiny_csg doesn't like these points where many faces meet

So there's a bit more context.
So far, I've had no problems at all with brushes that are formed such that only three faces meet at a convex hull point.

[a-day-old-bagel]

And one more comment now that I'm looking at the code again (sorry for writing walls of text):

I think this might be a problem inherent to one of the assumptions made in your algorithm (in combination with the usual terribleness of floating point), and if so, it might need a little bit of work to generalize the algorithm to this case. And I can attempt that work if need be.

But if it's not an algorithmic problem, and it's just a minor bug somewhere, I'd be happy to find that out too.

[laleksic]

I'd need some time to refresh my memory regarding how it all works. Haven't touched it in years. I have to say that since I've started programming for money, I enjoy it far less in my free time :).

Of course I do recall that there were millions of edge cases and precision issues. They mostly manifested in the way you describe. Faces missing where they're supposed to be, or not missing when they should be, etc. etc.

I thought I hunted them all down, and I'm pretty sure I tested with a cone shape at some point... hmmmm... Maybe not, though.

But I did only test with scaled/rotated/transformed versions of simple shapes, not with arbitrarily editable shapes.

I just took a quick peek at where you pointed me (where we construct the vertices by intersecting planes and push them into the plane polygons). Offhand, it seems in a case where more than three planes intersect in a point, then at least two different combos of 3 planes will produce this same point and it will be added twice to some polygons. This sounds like a disaster waiting to happen. Do I handle this case anywhere later on? Can't say I remember. Might point you in the right direction.

[a-day-old-bagel]

since I've started programming for money, I enjoy it far less in my free time

Yeah I feel that. It's the classic case of extrinsic motivation decreasing the enjoyment an activity that used to have intrinsic motivation.

Unfortunately, if you get paid to do something you like to do, you end up liking it less than before. Yet another flaw in our psychology.

Anyway, yes, I think you're describing the same case that I'm seeing, but I haven't found anywhere that your code is handling it as far as I can tell. I think there would have to be some further associativity going on between faces to allow them to share a vertex cleanly. I can see if some of my naive initial ideas of how to approach that end up working.

[laleksic]

Yeah I feel that. It's the classic case of extrinsic motivation decreasing the enjoyment an activity that used to have intrinsic motivation.

And there's the fact that I don't want to spend all day every day glued to the screen. So I give love to analogue hobbies :).

[a-day-old-bagel]

Gotcha.

Well good news about the "cone bug," though - I struggled around with it for a while before coming to a solution that finally solved it. I had to change the vertex_t struct, though. Before, the struct had an array of three face pointers. And since this solution necessitated getting rid of the assumption that a vertex can only be connected to three faces, that array has been replaced with a set.

I'm not sure if this will break anything in your demo, however, since I haven't actually built your demo.cpp before due to not wanting to fight with CMake and its persistent refusal to ever find the SDL2 library. I have CMake PTSD from the days when I wrote engine code in C++. I literally ended up building SDL2 from source (and other big libs) in my old C++ engine because of how much I despise CMake lol. And amazingly, I despise CMake less than I despise the other C++ build tools. They're all terrible. I'm so glad I found Zig.

Apart from that struct change, the only changes I made were to rebuild.cpp, and don't affect the API at all. I basically just had the vertices that are found by 3-plane intersections all get aggregated in a structure that groups the really close ones, and then after that pass, they're allotted out to the faces without any redundancy.

So that's (knock on wood again) fixed on the master branch of my fork.