Two trivial overlapping boxes trigger assertion in gjk

[manuel-koch]

I'm struggling with an issue when calculating the distance between two overlapping boxes, i.e. one tall box overlaps another box largely. The following snippet triggers an assertion:

import numpy
from distance3d import colliders
from distance3d import gjk

if __name__ == "__main__":
    vertices_a = numpy.array(
        [
            [-119.5, -120.5, -119.5],
            [-119.5, -119.5, -119.5],
            [-119.5, -120.5, -120.5],
            [-119.5, -119.5, -120.5],
            [-89.5, -120.5, -119.5],
            [-89.5, -119.5, -119.5],
            [-89.5, -120.5, -120.5],
            [-89.5, -119.5, -120.5],
        ],
        dtype=numpy.float64,
    )
    vertices_b = numpy.array(
        [
            [-90.0, -120.14644661, -120.85355335],
            [-90.0, -120.85355339, -120.14644656],
            [-90.70710679, -119.64644658, -120.35355338],
            [-90.70710679, -120.35355336, -119.64644659],
            [-89.29289321, -119.64644664, -120.35355341],
            [-89.29289321, -120.35355342, -119.64644662],
            [-90.0, -119.14644661, -119.85355344],
            [-90.0, -119.85355339, -119.14644665],
        ],
        dtype=numpy.float64,
    )

    collider_a = colliders.ConvexHullVertices(vertices_a)
    collider_b = colliders.ConvexHullVertices(vertices_b)
    distance, closest_point_a, closest_point_b, simplex = gjk.gjk(collider_a, collider_b)
    print(distance, closest_point_a, closest_point_b, simplex)

Traceback (most recent call last):
  File "distance3d_sandboy.py", line 42, in <module>
    distance, closest_point_a, closest_point_b, simplex = gjk.gjk(collider_a, collider_b)
  File "python/site-packages/distance3d/gjk/_gjk_jolt.py", line 213, in gjk_distance_jolt
    assert abs(np.dot(search_direction, search_direction) - v_len_sq) < EPSILON
AssertionError

Debugger shows values: search_direction=[-5.95073547e-17, -2.07708528e-08, -2.07708527e-08] v_len_sq=0.0

Any idea how to avoid such assertion ?

My environment is

• MacOS Ventura 13.3.1 (22E261) arm64
• Python 3.10.6
• distance3d 0.7.1
• numba 0.57.0
• numpy 1.24.3

[AlexanderFabisch]

Hi @manuel-koch ,

thanks for reporting. Unfortunately, I don't have any issue in my environment:

• Python 3.9.13 (conda)
• distance3d latest master
• numba 0.57.0
• numpy 1.23.5

Did you install distance3d via pip or from source code? (I'd suggest to install the latest master branch.) Could you try numpy 1.23.5?

If all that does not work, could you try to debug this case? What are the values of the variables before this assert is reached, etc.?

[manuel-koch]

I installed distance3d via pip. Retried with numpy==1.23.5 with same assertion error.

Will try to debug next week...

[AlexanderFabisch]

Please test it with the latest commit from master. It contains this commit:

https://github.com/AlexanderFabisch/distance3d/commit/488db39578d7b8d4da7251527083ede721cbd622

I found the assert to be too strict.

[manuel-koch]

Thanks for the hint, I patched the installed python code and the assertion is gone :-) Any plans to do a new release on PyPi for this issue ?

[AlexanderFabisch]

I should do it as soon as possible. You can keep the issue open to remind me.

[manuel-koch]

While adapting to the latest commit, I noticed that functionality moved / API changed.

Could you make this aabb check a public method (again) ?

My former code looked like

# collider_a: colliders.ConvexCollider, collider_b: colliders.ConvexCollider
aabb_a: = collider_a.aabb()
aabb_b = collider_b.aabb()
if not aabb_a.overlaps(aabb_b):
    return False

and now I'm using this protected/internal method instead

from distance3d.aabb_tree import _aabb_overlap

# collider_a: colliders.ConvexCollider, collider_b: colliders.ConvexCollider
aabb_a: = collider_a.aabb()
aabb_b = collider_b.aabb()
if not _aabb_overlap(aabb_a, aabb_b):
    return False

[AlexanderFabisch]

Previously, we used an external library for aabbtrees. Now we switched to our own implementation in numba.

@MaartenBehn is there any good reason why we did not make the function public? If not, I think we can just remove the underscore.

[MaartenBehn]

_aabb_overlap, _sort_aabbs, _merge_aabb, _aabb_volume, _aabb_x_size, _aabb_y_size, _aabb_z_size are all pure helper function used by the aabb_tree code. They don't have any side effects and could be made public if that is prefered.

[AlexanderFabisch]

Thanks. I will only expose aabb_overlap though. YAGNI.

I've pushed these changes to the master branch and I will now make a new release.

[AlexanderFabisch]

... and I just released 0.8.0.