How do I sort axis aligned bounding boxes along a ray where each AABB is guaranteed to intersect the ray?

I have tried to sort the centroid's be that doesn't work well. So is there another alternative?

CodePudding user response：

You should sort by perpendicular distance from ray_start in ray_direction direction. That can be computed using simple dot product.

1. If the AABB do not intersect you can sort by

   dot(BBOX_center-ray_start,ray_direction)
   

2. If AABB intersect

   then you can use all the points of BBOX instead of center and chose the one with smallest dot result for sorting so sort by:

   min(
      dot(BBOX_p0-ray_start,ray_direction),
      dot(BBOX_p1-ray_start,ray_direction),
      dot(BBOX_p2-ray_start,ray_direction),
      dot(BBOX_p3-ray_start,ray_direction),
      dot(BBOX_p4-ray_start,ray_direction),
      dot(BBOX_p5-ray_start,ray_direction),
      dot(BBOX_p6-ray_start,ray_direction),
      dot(BBOX_p7-ray_start,ray_direction),
      )
   

   However putting AABB BBOXes in order does not mean objects will be hit in the same order! Also this sorts by first "hit" if you want the last hit then sort by max instead ...

   You might keep both (min,max) orders and use O(n^2) test for overlaps discrepances in order between the 2 sorts as majority of order should be the same just the intersecting BBOXes might have different local order where n is number of locally intersected BBOXes which is probably much smaller than the total number of BBOXes ...