[mxwsn]

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.

[copperx]

He's just thinking asymptotically. f(n) = n(n-1)/2 = O(n^2).

[mishurov]

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]

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]

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

[oggyhead]

I see what you mean. The symmetric part is noted. Thank you for the reply