Creating convex collision from a mesh results in duplicate vertices

[jitspoe]

Godot version: 3.2.3 RC4

OS/device including version: Windows 8.1

Issue description: If you go to Mesh|Create Convex Collision Sibling, there are duplicate vertexes in the convex collision shape. For example, if you create a cube mesh, there will be 24 verts instead of 8.

Steps to reproduce:

• Click on a cube mesh.
• Click the mesh menu.
• Create single convex collision sibling
• Look at the collision shape and notice the array size is 24 instead of 8.

Minimal reproduction project:
convex_collision_too_many_verts.zip

Note: I'm working on a fix for this in 3.x, but the code is slightly different in the main branch because pool vectors were removed. It's just a matter of ignoring verts that are in the same location, because the mesh has duplicate vertices for faces with different normals/uvs/etc.

[mortarroad]

Is there any reason against just replacing quickhull with the convex hull algorithm from Bullet?
That one might be more stable?

[Calinou]

Is there any reason against just replacing quickhull with the convex hull algorithm from Bullet?
That one might be more stable?

Bullet may not always be compiled in Godot – in fact, it's planned to move it to a GDNative add-on in the future.

Therefore, we'd need to manually copy Bullet's convex hull algorithm to be able to use it even when Bullet is disabled.

[mortarroad]

Therefore, we'd need to manually copy Bullet's convex hull algorithm to be able to use it even when Bullet is disabled.

Is that not an option? Given that our current algorithm seems to be broken in multiple ways?

[Calinou]

Is that not an option? Given that our current algorithm seems to be broken in multiple ways?

It is an option, but adapting Bullet code to use Godot's datatypes may not be trivial.

[mortarroad]

@Calinou It seems that Bullet's convex hull algorithm is already ported and used in the "vhacd" module, but only used for convex decomposition.
Would it make sense if I adapt it, so it can be used in place of QuickHull?

It is there:
https://github.com/godotengine/godot/blob/cd05653e308c2263e23debd45211c48af134040d/thirdparty/vhacd/src/btConvexHullComputer.cpp

[Calinou]

Would it make sense if I adapt it, so it can be used in place of QuickHull?

Sure 🙂

Edit: Pull request opened: #47307

[mortarroad]

Turns out this issue is unrelated to QuickHull.
The collision shape simply stores all the vertices from the source mesh; the convex hull algorithm is only run at a later point in time.

[Zireael07]

@mortarroad: This doesn't make sense - why use QuickHull at all if the collision shape just skips past it?

[mortarroad]

QuickHull is only used in the physics server:

godot/servers/physics/shape_sw.cpp

Line 1152 in 3d649d3

Error err = QuickHull::build(p_vertices, mesh);

The resource itself does not apply QuickHull.

[jitspoe]

It might make sense to run the data through quickhull before storing it so unnecessary verts aren't kept. The fundamental quickhull algorithm is fine, but there's an issue with the way it tries to maintain edges for display purposes:

1. Unnecessary if only used for collision and the visual is unneeded.
2. Sometimes multiple triangles on the same plane bug it out and create errors: QuickHull generates bad hull sometimes when multiple triangles share the same plane. #45946

Simply replacing quickhull would mean something else would need to be used for generating the visuals to display the collision.

[mortarroad]

Simply replacing quickhull would mean something else would need to be used for generating the visuals to display the collision.

Well, I suppose we would use whatever we replaced QuickHull with... :P
Like in the PR I made: #47307

[jitspoe]

Simply replacing quickhull would mean something else would need to be used for generating the visuals to display the collision.

Well, I suppose we would use whatever we replaced QuickHull with... :P
Like in the PR I made: #47307

Ah, cool. Didn't realize that algorithm saved the edges. I do have concerns about it possibly being imprecise, though. Commented in the other thread, but the vhacd algorithm used by the mesh convex_decompose had issues, and I had to switch back to using QuickHull.

[jitspoe]

Just a note that #48533 superceeds the other quickhull replacement. I imagine it would probably be faster to remove duplicates before running the quickhull algorithm, though. I can submit a pull request for that (was hesitant to, since the data formats changed for 4.x, but it seems 3.x is still being actively updated).