Editor freezes and crashes when editing CSG blocks (CSGCombiner issue)

[GaryParkin]

Godot version

4.0 rc4/rc5

System information

Windows 10 Pro, 16G RAM Build 19045 AMD Ryzen 5 1600 - NVIDA Geforce GTX 1070

Issue description

I was working with csg blocks. I created a csgCombiner, then another block. Duplicated the block, renamed it then moved it to another location. I tried to adjust the Transform of the block and Godot goes unresponsive. I don't see a log to send.
I tried this on RC5 then went back to RC4, crashes in the same spot.

Steps to reproduce

I was working with csg blocks. I created a csgCombiner, then another block. Duplicated the block, renamed it then moved it to another location. I tried to adjust the Transform of the block and Godot goes unresponsive. I don't see a log to send.
I tried this on RC5 then went back to RC4, crashes in the same spot.
With the uploaded project, try and duplicate the large csg wall, then move it to the opposite side of the floor, then fine adjust it to fit the edge. Godot will go unresponsive.

EDIT: I have been playing around with the csg blocks and haven't had another crash yet. I believe the cause is the csg combiner if that helps any.

Minimal reproduction project

Godot4FPCWorld.zip

[Calinou]

I can't reproduce this on 4.0.dev 31eccb5, both with the gizmos and using the Transform property in the inspector to move the CSG nodes.

On the other hand, I was able to reproduce freezes (not crashes) when doing something similar in #74260.

[YuriSizov]

I can't reproduce the issue with this MRP and instructions, but the description does fit #74343 and #74191, which are trivially reproduced. The editor does indeed freeze and not crash, though at some point it will reach an overflow and will crash, so the difference is not important.

This seems to be a regression from #36422. What happens is CSGBrushOperation::Build2DFaces::_find_edge_intersections gets stuck in an infinite loop due to some unclear fault in logic. Existing checks seem to be insufficient to successfully finish computing the faces, and loop continues until the very last line, where 1 existing face is removed and 2 new faces are added instead. Then the cycle repeats, and the same thing happens. Edge detection doesn't trigger, and a new face is generating. And so it goes on and on, generating thousands of the exact same face or faces, without ever reaching the end of the loop.

I've experimented as much as I could without deeper knowledge of the system and the math behind, but I can't find any obvious issues or typos. Our epsilon coefficient also seems to be large enough to handle possible imprecision. So I can only assume we are missing a condition to check for to prevent this from happening. cc @madmiraal

[GaryParkin]

I haven't tried it since but as soon as my workload is lighter I will.

[justinwash]

Hey all (@YuriSizov), playing with this as I got tired of running into this in a project i'm working on. I've managed to fix the infinite loop that causes the crash by keeping track of which edges we've already processed in the loop.

Changes can be seen here master...justinwash:godot:csg-loop-fix

Had some concern about the glitchy faces that appear in subtract mode, but that appears to also occur in the most recent master post- #74771 so I'm not sure they really need to be covered in this fix, or if its even related:

My branch working:
https://user-images.githubusercontent.com/6236852/234983317-df6c0734-25f3-4790-80c6-24844062dde8.mp4

Most recent Master branch crashing, also exhibiting similar geometry wonkiness:
https://user-images.githubusercontent.com/6236852/234984769-620a2f24-968e-4a08-9a56-f4cc383c6d27.mp4

I'm new to contributing to open source so I'm not sure what next-steps are here. Create a PR referencing this issue and try to get some critique I guess? I'm not exactly a graphics programmer and have touched very little C++ before the past few days of messing with this issue, so I expect some ...let's say 'constructive' feedback.

[YuriSizov]

I'm new to contributing to open source so I'm not sure what next-steps are here. Create a PR referencing this issue and try to get some feedback I guess?

Yes, feel free to open a PR and we'll try to review it. We don't have a dedicated maintainer for CSG, but we'll figure something out and poke correct people.

[justinwash]

Remade the PR after destroying the first one trying to squash and such. Off to read the git docs...