5 ms·

The article states the guy says when you have n objects you have n^2 possible collisions, if you're assuming just one on one interaction and an object cannot co

The article states the guy says when you have n objects you have n^2 possible collisions, if you're assuming just one on one interaction and an object cannot collide with itself shouldn't it be n*(n-1)? Am I missing something here?

mxwsn 9y ago
Since collisions between two objects are symmetric (object one colliding with object two is the same event as object two colliding with object one) there are n(n-1)/2 possible collisions. The guy's probably short handing this as O(n^2), which is the important relationship as he's motivating the example by the need to handle collisions between large numbers of particles in hair, and modeling hair with as large a number of separate elements as possible is probably the key to realistic simulation.
- oggyhead 9y ago
  I see what you mean. The symmetric part is noted. Thank you for the reply
- mishurov 9y ago
  It's definitely a shorthand since a typical solution for collision detection is a space partitioning recursive data structure which reduces collision tests to O(n log n)
  - ColinWright 9y ago
    That point is actually covered in the article: Merida's hair is made of 100,000 individual elements. "If you know any combinatorics, you know that if you have n objects, you have n² possible collisions," he says, or 10 billion. How can you render so many collisions quickly enough to be usable? You have to create a new spatial data structure that culls extraneous collisions without being too lossy. So he's saying that naively with n objects there are n² possible collisions, but they have to do clever things - such as you suggest, or even cleverer - to reduce that. Already there. In the article. But the GGP's point is that there aren't n² possible collisions, there are only n(n-1)/2 if you allow for the symmetries. But is still grows quadratically, and that's the point being made. Quadratic is too fast.
  - electricslpnsld 9y ago
    For rigid bodies, given reasonably temporally coherent motion between time steps, you can get it down to O(n) with sweep and prune approaches [1]. These might not be the best choice for hair simulation, though. [1] https://en.wikipedia.org/wiki/Sweep_and_prune https://en.wikipedia.org/wiki/Sweep_and_prune
- copperx 9y ago
  He's just thinking asymptotically. f(n) = n(n-1)/2 = O(n^2).
dahart 9y ago
As others have pointed out, it's order n^2, not meant to be interpreted as exactly n^2. I will add that, having done hair simulation for DreamWorks, it's likely that their collision simulations are done on guide hairs, rather than interpolated hairs. So n is usually more like 1k, not 100k. Complete accuracy of hair simulations in film isn't required, nobody will notice individual hairs crossing each other, but you might notice big clumps behaving badly.

mxwsn 9y ago

Since collisions between two objects are symmetric (object one colliding with object two is the same event as object two colliding with object one) there are n(n-1)/2 possible collisions. The guy's probably short handing this as O(n^2), which is the important relationship as he's motivating the example by the need to handle collisions between large numbers of particles in hair, and modeling hair with as large a number of separate elements as possible is probably the key to realistic simulation.

oggyhead 9y ago
I see what you mean. The symmetric part is noted. Thank you for the reply
mishurov 9y ago
It's definitely a shorthand since a typical solution for collision detection is a space partitioning recursive data structure which reduces collision tests to O(n log n)
- ColinWright 9y ago
  That point is actually covered in the article: Merida's hair is made of 100,000 individual elements. "If you know any combinatorics, you know that if you have n objects, you have n² possible collisions," he says, or 10 billion. How can you render so many collisions quickly enough to be usable? You have to create a new spatial data structure that culls extraneous collisions without being too lossy. So he's saying that naively with n objects there are n² possible collisions, but they have to do clever things - such as you suggest, or even cleverer - to reduce that. Already there. In the article. But the GGP's point is that there aren't n² possible collisions, there are only n(n-1)/2 if you allow for the symmetries. But is still grows quadratically, and that's the point being made. Quadratic is too fast.
- electricslpnsld 9y ago
  For rigid bodies, given reasonably temporally coherent motion between time steps, you can get it down to O(n) with sweep and prune approaches [1]. These might not be the best choice for hair simulation, though. [1] https://en.wikipedia.org/wiki/Sweep_and_prune https://en.wikipedia.org/wiki/Sweep_and_prune
copperx 9y ago
He's just thinking asymptotically. f(n) = n(n-1)/2 = O(n^2).

dahart 9y ago

As others have pointed out, it's order n^2, not meant to be interpreted as exactly n^2. I will add that, having done hair simulation for DreamWorks, it's likely that their collision simulations are done on guide hairs, rather than interpolated hairs. So n is usually more like 1k, not 100k. Complete accuracy of hair simulations in film isn't required, nobody will notice individual hairs crossing each other, but you might notice big clumps behaving badly.