3 ms·

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

• 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