Portals: Unexpected room bounds generated

[timothyqiu]

Godot version

3.x (0403cb8)

System information

macOS 11.5.1

Issue description

One corner of the generated room bounds of my room is at an unexpected place. The room should be a cube shape.

The corner will be at the expected place after deleting the large portal in the front.

Steps to reproduce

Open the MRP in the editor and click "Convert Rooms" to see the green bounds.

Minimal reproduction project

QuickHull.zip

[lawnjelly]

Somewhat surprisingly, this is actually expected to happen in some circumstances. If you drop the Room Simplify value in the RoomManager from 0.5 to 0.4 or lower you will see the 'correct' corner point is chosen. You can also override the simplify value in each room.

Simplification error

What is happening is that the simplification value is used as an epsilon when running QuickHull. It determines the degree of difference in a point to create a new plane, and is subject to a certain amount of float / accuracy error. This is currently a trade off, the current default (0.5) can result in some cutting of corners, but it also reduces the worst cases when using bounds generated from e.g. curved surfaces like spheres. Without simplification, such curved rooms would contain far too many planes to be usable. We could possibly change the default to somewhere more around 0.4, I'll keep an eye on this.

As well as tweaking the simplification value you can also edit the points manually in such cases using the gizmo.

Does it cause problems

The other thing to note is that while this looks unsightly, in 99% of cases it doesn't seem to matter in practice. Aside from e.g. autoplace, the room bound is used to determine which room the camera / players are in. Most of these will have a radius of some kind, and use physics, so the centre will never reach this disputed corner region.

Different convex hull algorithms

My long term goal is I'm rewriting a new type of quickhull that works better for these (and a number of other) situations, it's mostly done but not ready for primetime yet, it is a surprisingly difficult problem. I've also evaluated the bullet convex hull generator and the other one in Godot which splits concave meshes. It's something I'm sure we can improve with time. Another option is to use a decimate algorithm on the mesh prior to running quickhull, or to use various combinations of running quickhull multiple times (it is already run twice).

TLDR

It's a problem I'm actively working on to improve, hopefully aside from looking unsightly it shouldn't be causing problems in practice.