kip-hart / aabbtree Goto Github PK

Hey,

Is is possible to return the corners of the bounding box for each leaf? I would like to use the decomposition of an input point set in another algorithm.

Thanks!

Hi! Is there any method to actually get the boundaries or of the overlapping boxes inside a tree?
Now I can use the "does_overlap(aabb_obj)" method of the AABBTree to check for overlaps but it says nothing about the exact box which overlaps given aabb_obj, only "yes/no" answer.

Or maybe return the AABBTree object with an overlapping box as a root of subtree would be a nice solution.

Thanks.

Hi. I'm working in a project and I need to verify if two irregular (nonconvex) meshes are overlapping or not. I create an python function that subdivide the mesh in boxes and I add those boxes to the tree. I do this for both meshes. My question is: There is a way to verify overlap between two trees?

Thanks for your help in adding an option for boundary intersection detection, which is quite essential in my project. In fact, I also have another request for adding an option for the return value of the overlap_values() method.

I can understand that you add the following function

def _unique_pairs(pairs):    
      boxes, _ = zip(*pairs)    
      u_pairs = [p for i, p in enumerate(pairs) if p[0] not in boxes[:I]]    
      return u_pair

to avoid duplication boxes and keep the output succinct as much as possible. But, it seems not consistent with the return of overlap_values().
For example,

from aabbtree import AABB
from aabbtree import AABBTree 
tree = AABBTree()
aabb1 = AABB([(0, 1)])
aabb2 = AABB([(0, 1)])
aabb3 = AABB([(0, 1)])
tree.add(aabb1, 'box 1')
tree.add(aabb2, 'box 2')
tree.overlap_values(aabb3)
>>>['box 1']

In this scenario, we take the AABBtree as a dictionary to retrieve, sort of like a key-value dictionary. Those 3 boxes are identical in terms of geometrical coordinates, but, they are not identical in terms of value. Thus, logically, they are different. And if we want to know which boxes have an intersection with the target box, it is going to be expected to return all of them in some cases. Besides, if we only return one ['box 1'], it is not fair for 'box 2'.

Could you add an optional flag to specify whether it will return one or all boxes, something similar things like that?

Thanks!

Hello,

I have some questions:

• Is this implementation able to detect polygon intersection?
• Is ray casting supported?

Thanks

Hi, thanks for providing such a great project, it really helped me a lot. But I recently found in some cases, the return value of the overlap_values have some problems for me. Mainly for the value of the 'object type', a copy of it is returned instead of the original value I passed in.

For example:

if __name__ == '__main__':
    tree = AABBTree()
    foo_list = [Foo() for i in range(5)]

    for foo in foo_list:
        tree.add(AABB([(0, 1), (0, 1)]), value=foo)

    new_foo_list = tree.overlap_values(AABB([(0, 1), (0, 1)]), unique=False)

    print(foo_list)
    print(new_foo_list)

the output is:

[<__main__.Foo object at 0x10f30d5e0>, <__main__.Foo object at 0x10f33de80>, <__main__.Foo object at 0x10f3fc820>, <__main__.Foo object at 0x10f3fca00>, <__main__.Foo object at 0x10f3fc970>]
[<__main__.Foo object at 0x10f448e50>, <__main__.Foo object at 0x10f453250>, <__main__.Foo object at 0x10f4535b0>, <__main__.Foo object at 0x10f453910>, <__main__.Foo object at 0x10f3fc970>]

It seems cause by the deepcopy in add function:

        elif self.is_leaf:
            self.left = copy.deepcopy(self)

AND

            if branch_cost < left_cost and branch_cost < right_cost:
                self.left = copy.deepcopy(self)

I have done some workarounds in my project and it seems to work, I think the deepcopy here may not be necessary(and may have additional overhead for large value objects or deep branch), just create a new AABBTree here and simply move all the properties to the new one, then assign it to self.left may work as well

Hi, I am working on a project about polyhedra intersection detection. Your AABBTree module is quite helpful and essential for my project. The open box intersection detection looks good most time, however, it seems a little blurry when it is working on closed box (including the boundaries) intersection detection. For example, the following code only works for open box intersection detection, but it does not work for closed box, otherwise, it should return ['box1', 'box 2']

from aabbtree import AABB
from aabbtree import AABBTree 
tree = AABBTree()
aabb1 = AABB([(0, 0)])
aabb2 = AABB([(-1, 0)])
tree.add(aabb1, 'box 1')
tree.add(aabb2, 'box 2')
tree.overlap_values(aabb2)
>>>['box 2']

Could you add an argument to indicate whether it is overlapping in terms of open or closed boxes in the overlap_values() method?