Raycast detecting insides of meshes with collisions set to "PreciseConvexDecomposition" or "Default"

01_0101100 · October 4, 2022, 5:38pm

Hello!

I’ve recently been playing with raycasts to try to have an approximation of a mesh geometry but I keep running into an issue where the raycasts detect the inside of the mesh even if it is full.

I tried to find the cause and it looks like the way Roblox decomposes the collider as the raycasts would only detect the places where a collider starts/end.

Here is what I mean :

This is really annoying as it increases the time it takes to read the mesh, check the ovverlaping points and makes it harder to organize them.

COMPILATION ( A reproduction file containing all of the bugs can be found all the way at the bottom. The bugs are labeled and sorted in folders )

Briefing : Raycasts Detect the insides of meshes
Information : I noted that the hits occurs precisly at the limits of a collider chunk ( Colored Part ) as if it was a separate object. Due to this, the issue only occurs with the CollisionFidelity set to Default or PreciseConvexDecomposition as the other two are ( Hull and Box ) have a single chunk collision.

Observed Cause : The Roblox engine checks all sides of a collider chunk even if it is inside the mesh (normally inacessible) and is engulfed in other collider.
Reproduction : It contains two meshes from the toolbox with a script that raycasts until it reach the opposite side ( frontside ⇒ inside ⇒ backside ). Each mesh will have 2 copies of them, one with CollisionFidelity set to “Default” (Green) and the other set to “Hull” (Brown). An highlighted ball will appear at hit locations to make it easier to see and hit data will be logged in the console.

Briefing : Colliders sometimes appear to be overlapping between each other.
Information : This seems to only happen with Collision Fidelity set to PreciseConvexDecomposition. The overlaps can appear inside the mesh or outside (creating visual glitchs) but look to be more present inside than outside.

Observed Cause : Unknown
Reproduction : Three mesh where used (Two from the default mesh rig and one from the toolbox) and all experience this issue. All of the meshes have a copy of them above with CollisionFidelity set to Default which appears to remove the overlapping. To see the overlaps, I recommend to first turn on ShowGeometryDecomposition to see outside overlaps and after this also turn on WireFrame mode to see inner overlaps.

Briefing : The surface normal of the colliders don’t always match the real surface including when said surface is plane (made of a single triangle or multiple triangles but that have the same surface normal).
Information : This looks to happen on every CollisionFidelity except Box and Hull. The difference in normal is most of the times mininal (from -e5 to 0.0001~) but is still visible.
Observed Cause : Unknown
Reproduction : A single mesh with a relatively cubic shape was used to make it easier to see the effects. The bottom mesh has CollisionFidelity set to Default and the top one to PreciseConvexDecomposition. A script raycasts along the entire from surface of the mesh and then visualizes the hits with spheres. Each sphere is colored depending on a random color given to the normal (so (0, 1, 0) may be green etc). After running the game, you will be able to see that these sphere appear to be of different color even when on a flat surface. The mesh with CollisionFidelity set to PreciseConvexDecomposition has by far the glitchiest results of the two.

Briefing : Some shapes have voids in them when they shouldn’t.
Information : This happens when CollisionFidelity is set to PreciseConvexDecomposition or Default. The voids can range from just an air space in a mesh to complete emptiness or to holes leading outside but where there is geometry.
Observed Cause : Unknown
Reproduction : Two meshes where used ( a bed and a dominus from the toolbox ). They both have a copy of them above with CollisionFidelity set to PreciseConvexDecomposition. To see the effects, press Run and watch the highligted balls bounce inside. For the void types, both meshes with CollisionFidelity set to Default had air spaces and when set to PreciseConvexDecomposition the both had holes leading outside. To see the holes, I recommend to enable ShowGeometryDecomposition as the balls do not end up falling out of the mesh.

Reproduction File : raycast-bug.rbxl (192.8 KB)

I really hope this helps solving the issues and also!

Thanks!

Khanovich · October 4, 2022, 5:59pm

So PreciseConvexDecomposition mode is not perfect and not without bugs. The high level technical overview of how it works can be found here: A Search for Better Convex Decomposition | by Val Gorbunov | Khanovich | Medium

That being said, the two issues you highlighted I’m familiar with:

1. Hitting insides of the Convex Decomposition: When the convex decomposition process starts and attempts to create good collision geometry, the initial input is a raw TriangleMesh that matches the input visual geometry, with double-sided triangles. As the algorithm runs, it tries to combine nearby double-sided triangles (even ones that are non-parallel) into Convex Hulls. Sometimes, the algorithm finds the process impossible and may leave a few double-sided triangles inside of the shape in an attempt to make sure the outside of the final shape matches the input shape as best possible.

2. Voids: This sounds like a bug, I’ve seen it rarely in shapes with really degenerate triangles, but some input geometry examples would help. Is that in the repro level?

mrrblato · October 4, 2022, 7:20pm

Hi - a few additional points:

I noted that the hits occurs precisly at the limits of a collider chunk

This does seem to be a bug - perhaps a floating point precision issue in how the contact points are discovered (per convex of the decomposition) and how they are assembled into a contact manifold (the collection of contact points describing how to best resolve collision = move objects apart so they don’t interpenetrate anymore)

The Roblox engine checks all sides of a collider chunk even if it is inside the mesh (normally inacessible) and is engulfed in other collider

Related to the first observation. The collision contact points are found per convex of the decomposition, but nesting of convexes (as well as overlap) should be handled by contact manifold computation.

Colliders sometimes appear to be overlapping between each other…
Some shapes have voids in them when they shouldn’t

Unfortunately this is inevitable for Precise decomposition, since the algorithm we use for this (HACD) is not volumetric but surface based - specifically as @Khanovich describes in his link, the algorithm works by merging patches of triangles into convex hulls - but this (sometimes) results in a decomposition that “hugs” the surface in places (like a thick envelope of the mesh), and so might have some internal voids and/or overlapping convexes. On the other hand, note that voids should probably be absent from the result of Default algorithm - if they are present there, then this is probably a bug.

The surface normal of the colliders don’t always match the real surface

Both Default and Precise are approximate convex decomposition algorithms. (Exact decompositions usually produce impractical number of convexes, hence approximate decomps are usually used in practice.) As such they are expected to produce collision geometry that is slightly off (in terms of normals, for example) with respect to the original mesh. This usually occurs inside cavities in the mesh (especially if the cavity is small with respect to the rest of the mesh). But results could propagate outside of the cavities. However, in Precise decomposition, large flat (or convex) areas, or large concave areas of the mesh, should have collision geometry that is pretty close to the mesh itself.

01_0101100 · October 4, 2022, 11:33pm

Hi, yes the reproduction file contains two meshes with cavities in them. The first one is the dominus and the second is the Roblox Bloxy Award statue both on PreciseConvexDecomposition.