News for hackers. Stuff that matters.
Re:CoffeePhysics: A JS/CS Physics Engine by ricardobeat on Wednesday February 29, 2012 @10:11AM (#3648071)
The cloth simulation runs incredibly smooth, while the attraction demo is terribly slow (Chrome 17 OSX). Strange?
Re:CoffeePhysics: A JS/CS Physics Engine by TheBurningOr on Wednesday February 29, 2012 @10:55AM (#3648258)
The attraction and collision demos are both doing collision detection, which means N! calculations (for each particle check the location of all the other particles that have not been checked relative to this one). Whereas the chain, cloth and I can't recall the name of the third one, are on the order of N calculations (constant interaction with only a fixed number of other particles).
Re:CoffeePhysics: A JS/CS Physics Engine by HardyLeung on Wednesday February 29, 2012 @10:59AM (#3648283)
You mean N^2, not N!
Re:CoffeePhysics: A JS/CS Physics Engine by nlogn on Wednesday February 29, 2012 @11:16AM (#3648346)
He's right actually if the code is written sensibly. Well it should really be (N-1)! but close enough. Think about it in terms of 3 balls. I check ball1 against ball2 and ball3 then move to ball2. It gains me nothing to re-check ball2 against ball1 so I just check it against ball3. When I reach ball3, I have already checked everything and I'm done.

The loop should look like this:

  for (i = 0; i < n; ++i)
      for (j = i + 1; j < n; ++j)
Re:CoffeePhysics: A JS/CS Physics Engine by dmvaldman on Wednesday February 29, 2012 @11:24AM (#3648382)
That's N*(N+1)/2 steps, or order N^2. Best to visualize as the number of entries on the upper triangle of an NxN matrix.
Re:CoffeePhysics: A JS/CS Physics Engine by HardyLeung on Wednesday February 29, 2012 @12:47PM (#3648807)
I think you need to revisit your understand of complexity. It is O(N^2). If you want the exact count, it is N(N-1)/2. N! is an exceedingly large number even for very small N.
Re:CoffeePhysics: A JS/CS Physics Engine by nlogn on Wednesday February 29, 2012 @09:58PM (#3650736)
Yep I'm wrong. Mixed up factorial just like mistercow said. Thanks for the corrections. And here I was worrying that someone would complain that my loop wouldn't address the issues of collision response necessitating more checks, thus making a recursive solution necessary.
Re:CoffeePhysics: A JS/CS Physics Engine by mistercow on Wednesday February 29, 2012 @01:03PM (#3648887)
That's not N! . N! is (N)(N-1)(N-2)... What you have there is (N)+(N-1)+(N-2)..., which is O(N²)
Re:CoffeePhysics: A JS/CS Physics Engine by mistercow on Wednesday February 29, 2012 @01:01PM (#3648878)
It should be very easy to implement geometric hashing in CoffeeScript, which can greatly improve collision performance.