r/GraphicsProgramming • • 5d 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.

10 Upvotes

4 comments sorted by

•

u/AutoModerator 5d ago

Recently updated rules. Please check that your post is in compliance with Rules 1, 4, 5, and 6 on the sidebar. TL;DR:

  • No showcases.

  • Disclose AI usage in post or project.

  • Present a topic to talk about, e.g. how something works.

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 5d ago edited 5d 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.

1

u/IRateBurritos 5d ago edited 5d ago

So, I think that's the confusion for me. Assuming the cells are arranged as

0 1 0' 1'

2 3 2' 3'

And the cell size is 1.5x the sphere radius, I don't see why the sqrt(2) scaling is necessary, especially considering they also scale the spheres by that amount. The 1.5 makes sense to me for removing the case where spheres are double counted: assuming that the spheres have radius r and the cells a size of q, and that the left border of my diagram above is 0, then the worst case scenario is having one sphere centered in cell 3 at q + r - delta, and one centered in cell 2' on the right at 2q+delta. Then the first sphere is barely overlapping cell 2 and the balls' centroids are separated by q-r + 2*delta. By setting q = 3r (1.5d), you make it impossible for the spheres to overlap. So I get where 1.5 comes from. But the sqrt(2) doesn't show up anywhere in that math. I can't think of a config that would place the spheres any closer while satisfying the conditions laid out in the article.

1

u/troyofearth 5d ago

Oh yeah sorry i got caught up there.

That's a slightly more simple counteraxample:

0 1

2 3

The sqrt(2) expansion of the bounds for marking, means that the spheres cant be marked exclusively in 0 and 3 and have a collision (on the original bounds) in 1.

To be clear they can still be in 0 and 3 and have collision in 1... but their radius is expanded so they will also have to BOTH touch either 0 and 3 for that case. 

You've eliminated that 'exclusively in 0 and 3' possibility. Artificially and its weird because it creates fake collisions that must be removed in narrowphase.

Sorry you were clear and i got caught up on the 1.5 lol.