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?

  • 1
    \$\begingroup\$ 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). \$\endgroup\$
    – Basic
    Dec 21 '21 at 0:47
  • 1
    \$\begingroup\$ You may be looking for interval trees \$\endgroup\$
    – DMGregory
    Dec 21 '21 at 1:24
  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – Theraot
    Dec 21 '21 at 4:17
  • \$\begingroup\$ "buffer lookups on the gpu turned out to be expensive" why are you doing buffer lookups at all? \$\endgroup\$
    – Jay
    Dec 22 '21 at 3:17
  • \$\begingroup\$ 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. \$\endgroup\$ Dec 22 '21 at 8:47

You must log in to answer this question.

Browse other questions tagged .