What is the meaning of "AabbTree.overlaps_aabb()" result ?

[manuel-koch]

Can somebody explain the result of AabbTree.overlaps_aabb() ?
I can't make any sense of the result, it looks different compared to the docstring where the result contains "pairs" and the numbers look strange:

from distance3d.aabb_tree import AabbTree

aabb1 = numpy.array([[0, 10], [0, 10], [0, 10]], dtype=numpy.float64)
aabb2 = numpy.array([[8, 12], [3, 4], [4, 5]], dtype=numpy.float64)
aabb3 = numpy.array([[20, 30], [0, 1], [0, 2]], dtype=numpy.float64)
aabb4 = numpy.array([[-50, 50], [-50, 50], [-50, 50]], dtype=numpy.float64)

aabb_tree = AabbTree()
aabb_tree.insert_aabb(aabb1, 1)
aabb_tree.insert_aabb(aabb2, 2)
aabb_tree.insert_aabb(aabb3, 3)

overlap_flag_1, overlaps_1 = aabb_tree.overlaps_aabb(aabb1)
print(overlap_flag_1, overlaps_1)

overlap_flag_4, overlaps_4 = aabb_tree.overlaps_aabb(aabb4)
print(overlap_flag_4, overlaps_4)

which prints

True [1 0]
True [3 1 0]

What is the meaning of second value of the returned tuple ?

• it is a flat list of entries - docstring uses term "pairs" - what is a pair then ?
• the external_data of the AABBs that overlap with the given aabb ? Why do I get 0 ? This is not any external_data I have used.
• an index for the AABBs that were inserted ? Why do I get 3 ? I only inserted 3 AABBs, expecting at max index 2.

[AlexanderFabisch]

@MaartenBehn can probably answer this question. Could you also correct the docstring?

[MaartenBehn]

You are right the docstring is not correct.
What is returned is the list of all the indices internal to the tree with are overlapping.
You can use these to index into the external data array.
This happens because the leaf node and branch nodes share one array (nodes array). And if you insert the leafs one by one there are branch nodes that are added between the leaf nodes. Hence the reason why and index of 3 is returned.
If you add all the aabbs in one big insert_aabbs call. All the branch nodes will be added after the leaf nodes and therefore the returned indices may match the insertion order.

Because this behavior is not really reliable. I will also add another list to the aabb tree which maps the insertion order to the internal indices.

aabb1 = np.array([[0, 10], [0, 10], [0, 10]], dtype=np.float64)
aabb2 = np.array([[8, 12], [3, 4], [4, 5]], dtype=np.float64)
aabb3 = np.array([[20, 30], [0, 1], [0, 2]], dtype=np.float64)
aabb4 = np.array([[-50, 50], [-50, 50], [-50, 50]], dtype=np.float64)

aabb_tree = AabbTree()
aabb_tree.insert_aabb(aabb1, 1)
aabb_tree.insert_aabb(aabb2, 2)
aabb_tree.insert_aabb(aabb3, 3)

overlap_flag_1, overlaps_1 = aabb_tree.overlaps_aabb(aabb1)
print(overlap_flag_1)
for overlap in overlaps_1:
    print(aabb_tree.external_data_list[overlap])

overlap_flag_4, overlaps_4 = aabb_tree.overlaps_aabb(aabb4)
print(overlap_flag_4)
for overlap in overlaps_4:
    print(aabb_tree.external_data_list[overlap])

[manuel-koch]

So your idea is to return the external-data-indices directly from aabb_tree.overlaps_aabb() and not return the internal indices ?
That is what I would expect from the API.

[MaartenBehn]

The function returns the internal indcies. They are the same for the external data list, the nodes array and the aabbs list.

I have also added a insert index list which also is accessable by the returned indices.

Check out this commit. This will be merged soon. 8dafa6a

[MaartenBehn]

The indcies just may differ from the insertion order. To be precise there may be indices corresponding to branch nodes in between and those are never returned.

[AlexanderFabisch]

@manuel-koch We were just discussing this issue. We currently don't really use AabbTree.insert_aabb anywhere and I'd rather like to delete it. Do you really need it at the moment? I would suggest to use AabbTree.insert_aabbs instead once in the beginning.

The AabbTree interface is very low-level and efficient. Don't expect any convenience at this level. Maybe the BoundingVolumeHierarchy is better in your case?

[manuel-koch]

@AlexanderFabisch It would be ok for my use case to use AabbTree.insert_aabbs - for now we are using rtree for our broad-phase.