# Optimal data structure for managing AABBs to minimize collision check queries

Say I have thousands of 2D Axis-Aligned Bounding Boxes (AABBs), and a single point. I'm checking whether a point is inside a certain AABB before performing some expensive logic.

point = absolute(point - lower_bound)
normalized_bound = absolute(higher_bound - lower_bound)
if point.x < normalized_bound.x and point.y < normalized_bound.y
{ do stuff }


Even though this check is really simple and efficient, it still has to iterate over thousands of boxes. I thought this wouldn't be a problem, but, in fact, buffer lookups on the GPU turned out to be expensive, especially since this is being done per pixel.

So is there some sort of a structure that would minimize the number of boxes that have to be checked?

• How dynamic are the bounding boxes? If fairly static, you could steal a page from the database world and build a sparse index... Calculate which AABBs might intersect a point a (grid of x, y, z points with an appropriate step/spacing) and store that. When you need to query a point, look up the 8 surrounding indexed points and only checks those AABBs (ideally dedpued). Dec 21 '21 at 0:47
• You may be looking for interval trees Dec 21 '21 at 1:24
• Do these AABB have any ordering? Do you have to do the expensive operation for each AABB a point is inside, or only one will do? And when you say you are doing this per pixel, it is a different point for each pixel, correct? Dec 21 '21 at 4:17
• "buffer lookups on the gpu turned out to be expensive" why are you doing buffer lookups at all?
– Jay
Dec 22 '21 at 3:17
• If you're reading data that's also in-use for drawing back from the GPU to the CPU then it's always going to be expensive, even if you only read a single byte. If you need the data CPU-side as well then just store it in normal system memory as well. Dec 22 '21 at 8:47