1

I recently did an AABB (Axes Aligned Bounding Box) Intersection implementation on 2D and 3D objects for which I came up with such a short (and very fast) solution as follows.

The demonstration below is for 2D rectangles, nevertheless the algorithm promises extension to 3D, and nD spaces as well, with no additional effort.

AABB has been a standard part of many small and huge computational geometry packages in order to speed up intersection and collision detection, for years. For me, not fan of large complicated libraries, I preferred however to do it myself with no consultation with any of them.

With the above introduction, it is quite possible that I might have missed some situations on those the following simplistic algorithm might fail. If there was no such failure this algorithm looks like the fastest intersection test for AABB and the most easy-to-extend to nD as well as it requires only few simple numeric comparison.

Introduction:

An AABB is usually defined by two points as (mins,maxs), e.g., in 2D (0,0,1,1) where (0,0) are the minimums for X and Y axes, and (1,1) are the maximums for X and Y axes respectively. Similarly for nD it could be as follows.

P = (x1,y1,z1,...,x2,y2,z2,...)

Let's P and Q be two AABB:

P(mins,maxs)                  % e.g., in 2D (0,0,1,1)
Q(mins,maxs)                  % e.g., in 2D (0.1,-1,3,2)

Intersection between the two P and Q happens only if:

P(mins) <= Q(maxs) & Q(mins) <= P(maxs)

So for the 2D example given above, P(mins) = (0,0) and P(maxs) = (1,1) and for Q: Q(mins) = (0.1,-1) and Q(maxs) = (3,2) Now if we check the conditions mentioned above: (0,0) <= (3,2) i.e., (0 <= 3) and (0 <= 2) and (0.1,-1) <= (1,1) i.e., (0.1 <= 1) and (-1 <= 1), we see that all conditions satisfy which means the two AABB P and Q intersect.

Therefore the algorithm requires only few simple comparisons which can be implemented in various forms efficiently. Furthermore, the algorithm can easily be extended into nD.

I wonder if this such simple algorithm is the fastest, the most elegant and extendable to nD for finding intersection between AABBs?

Any comment about potential shortcoming or any discussion or share of experiences would be helpful.

AABB Intersection Tests - Algorithm - (c) 2017 Developer

AABB Intersection Tests - Implementation - (c) 2017 Developer

  • 2
    It seems like you are seeking a code review without providing any code. Have you tried the Code Review Stack Exchange? – PolyGeo Mar 31 '17 at 6:46
  • 1
    @PolyGeo Here I would like only to learn your experiences and to benefit from your knowledge as this question is important in GIS community. For a case in which I have used this technique I have a post on Code Review for a complete source code at here. – Developer Mar 31 '17 at 7:43
  • @PolyGeo BTW, cannot we anymore put figures inline with the question? – Developer Mar 31 '17 at 7:46
  • Do you mean like I just moved your pictures? – PolyGeo Mar 31 '17 at 7:50
  • 1
    Your title and body ask different questions, neither of which can be answered with the information provided. – Vince Mar 31 '17 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.