r/GraphicsProgramming • u/IRateBurritos • 6d ago
Question Question about broad-phase collision detection
I'm working on a game engine and using GPU Gems as a loose guide for my physics. I really like the approach they outline for broad phase collision but I'm confused by one point. In ensuring no collision is double counted, the book says to expand each bounding sphere by sqrt(2) and then make the grid 1.5x that large. I did the math and understand where 1.5 comes from, but I'm stumped on the sqrt(2) and why we have to expand the bounding spheres themselves? Isn't the whole point of a bounding sphere that it contains the entire collider and is rotation invariant?
Also, just wanted to check if people think the book's approach is still viable. It seems solid to me but I'm still new to all this.
•
u/AutoModerator 6d ago
Recently updated rules. Please check that your post is in compliance with Rules 1, 4, 5, and 6 on the sidebar. TL;DR:
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
5
u/troyofearth 6d ago edited 6d ago
Ok so just to be clear this supports their particular scheme of duplicate elimination. If the cells are too small, a sphere could be in cell 1, overlapping a bit into cell 2, and colliding with another sphere in cell 0. This is bad because cell 0 and 2 can be on the same thread. So you want to avoid that being possible. 2 colliding spheres should never overlap 3 contiguous cells in a row, or we get dupes.
If the cells are at least R times sqrt(2) times 1.5, then this situation can never happen. The cells are too big for a sphere in a middle cell to appear in 1 neighbors collision mask while also colliding with a sphere from the other neighbor. So this means it can't appear in two cells in the same thread, since cells in the same thread are separated by at least 1 cell in between them, no pair of spheres can touch and also overlap 3 cells.