   Finding the axis-aligned cells of a capsule
I'm trying to find all of the cells of an axis-aligned grid that a moving sphere test falls onto. The grid can be random-accessed, so it's possible to jump straight to a cell, given any coordinate within it. Typically, movement is small (1x1 or 2x2 cells), so I just use the bounding box of the moving sphere and look through all 1-5 cells. But movement can sometimes be very long, such as when testing a path-finding trajectory across an entire hallway. For these situations, I'm wanting to minimize the number of cells checked for collision, and a diagonal moving sphere across a decent sized hallway can generate an AABB that overlaps the entire map.Any suggestions on how I could go about doing this? I've done this before with rays by using something similar to a line-drawing algorithm, but I think this is a little different.My first half-baked idea is to find the bounding box cells and test their distance to the capsule line to see if they are within radius. But that seems a little harsh.My second half-baked idea is to turn the capsule into a normal ray by expanding all of the cells by its radius. But then I would have some weird overlapping cell map that can't be interesected with a typical line-drawing routine.Any advice?   
  If what you're looking for is a "quick" way to reduce the number of cells you test....  rather than a 100% accurate "you only need to test these cells"..Start with your AABB elimination thenTest the capsule against the bounding sphere (Circle?) of each cell.ie. Calculate the distance of a point (the centre of the cell)from the line segment (start to end of sphere motion)If that's   > CapsuleRadius + (CellDiagonal / 2)then that cell does NOT intersect the capsule.That will quickly eliminate almost all the cells you don't need to test.1 or 2 might "slip though" but NONE would in the diagram you gave.Also, because the cell centres lie on a fixed grid, you should find that the distance to the line (rather than segment) will vary predictably as you move from one cell to the next, and 1 row to the next..So with a little "up front prep"... calculating the distance for the next cell becomes a simple addition / subtraction, rather than having to go through the "full" distance calculation each time.HTHPS. It feels like there's an equation (Quadratic probably) that you could solve for each row, which would yield the first and last cell "hit" on that row....  but I'll have to think about that further...PPS. If you can reduce the problem to 2D, it becomes VERY simple (and fast) to solve.. in a different way.[Edited by - daftasbrush on March 8, 2008 7:34:49 AM];Quote:Original post by daftasbrushIf what you're looking for is a "quick" way to reduce the number of cells you test....  rather than a 100% accurate "you only need to test these cells"..There's no danger in checking a few extra cells, as long as all that overlap are checked.The routine to reduce the number of cells checked needs to be pretty fast. If I were to completely avoid optimizing it, it would only result in extra object bounding box checks (not polygon collision, etc). The cell reduction method needs to be able to confirm or dismiss a single cell faster than about 2-4 3D AABB vs AABB checks, or I won't gain anything.I was hoping to find a method that can "travel" through the grid, in order to completely avoid iterating and dismissing cells that don't get touched by the sphere path.Quote:Start with your AABB elimination thenTest the capsule against the bounding sphere (Circle?) of each cell.That was what I tried to describe in my first idea in the original post. It may improve speed a little, but not as much as I would like. There are typically only about 1-5 objects in a single cell to be AABB checked.Quote:Also, because the cell centres lie on a fixed grid, you should find that the distance to the line (rather than segment) will vary predictably as you move from one cell to the next, and 1 row to the next..So with a little "up front prep"... calculating the distance for the next cell becomes a simple addition / subtraction, rather than having to go through the "full" distance calculation each time.I'm not sure I can pull that off myself. Any chance you could help me understand how to go about doing this?   ;  Ok, have changed my mind a little....The method I'm now advocating... works "fantastically" in 2D, and can probably be extended to 3d very simply (and efficiently)But it takes a bit of explaining... so I'll stick with the 2D case initially.Essentially, for each row of cells, you compute the AABB of the part of the capsule that falls within that row.What that gets you, is.. the first and last "hit" cell on that row.In 2d this is relatively simple, and after some initial computation, each successive row takes only minimal calculations.Assuming that each cell is 1x1For any capsule the values D,S and R (see image) can be easily calculated, from the normalised direction vector and the capsule radius.D = "The extent of the Capsule in X" = Radius / Abs(Direction.y)S = "The Shift in X from Row to Row" = "Gradient" of Line =  Direction.x / Direction.yR = "The Width of the AABB in X" = (2*D) + SAll you need now is the position of the "box"You can get this by essentially solving either the parameterised line equation or something in the form (y = mx+c).Either way, what you want to calculate is the X coordinate, of the capsule centre line, at the mid-point (in Y) of the "first" cell.I ended up with....MidPointX = (0.5 - pStart.y) * S + pStart.xThat gets you the X coordinate of the capsule centre line at the middle of row 0 (Y = 0.5) To adjust that to the first "row of interest" (the first inside your "overall" AABB)MidPointX = MidPointX + Min.y * SWhere Min.y is the lower bound (in Y) of the "overall" AABB of the capsule Min.y is Rounded down to be exactly on the cell boundary.. 1 in the image aboveYour AABB limits for that row are thenLeft = MidPointX - R / 2Right= MidPointX + R / 2These will be "non-integer" values but the integer part is the "position" of the first and last cell on this row that hit the capsule.So for this row, you only need to test cells in those columns.Now... here's the trick.Left and Right now hold the extact start and end positions for the first rowto get the positions for the next row... Simply add S to each. (S is signed)then take the integer parts again, to get first and last cell numbers.So once you got the initial stuff worked out..the calculation of first and last cell for each row becomes 2 additions and 2 Ints and thats it.There are 2 degenerate cases... where you would just test all the cells.i) Either of the extents of your "overall" AABB is 1ii) direction.y = 0The approach isn't taking account of the capsule ends... but provided Radius ~< 1 cell it won't matter that much.See if you can can your head around the above, I'll post again in a bit with thoughts on optimization and extending it to 3D.   ;  I'm sorry I haven't replied sooner. I've been a little sidetracked by another problem. I've looked over your concept, and it definitely looks like something I would want to use. The concept of finding the width of the capsule within a single row of the plane of the grid didn't even occur to me. I still need to look at it in more detail, though. I'll reply again soon.   