Search found 324 matches

by Erin Catto
Wed Apr 23, 2008 6:24 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: EPA
Replies: 20
Views: 7846

Re: EPA

Thanks for the code John.

Here's a bug fix for line 258:

Code: Select all

if (bad_vertex < 4)
{
	y[bad_vertex - 1] = y[4];
	p[bad_vertex - 1] = p[4];
	q[bad_vertex - 1] = q[4];
}
Should be:

Code: Select all

if (bad_vertex < 3)
{
	y[bad_vertex - 1] = y[3];
	p[bad_vertex - 1] = p[3];
	q[bad_vertex - 1] = q[3];
}
by Erin Catto
Wed Apr 23, 2008 6:12 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Convex-Convex collision detection issues
Replies: 34
Views: 15999

Re: Convex-Convex collision detection issues

Ok, I quickly tried the crossing-edges test and I got mixed results. It seems to work, but only if I disable the optimization above. However, without this optimization, the code is not as fast as before. For some reason it seems I can't mix the two optimizations. Not sure why, no time to really inv...
by Erin Catto
Tue Apr 22, 2008 5:22 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Convex-Convex collision detection issues
Replies: 34
Views: 15999

Re: Convex-Convex collision detection issues

I don't care much about the separation -distance-. I only care about the separation -direction-. Can it be computed as well? Yeah, it is just the edge-edge cross product. Getting the sign is tricky. I chose the sign according to the vector connecting the two centroids. So the edge-edge test is O(1)...
by Erin Catto
Mon Apr 21, 2008 6:13 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Convex-Convex collision detection issues
Replies: 34
Views: 15999

Re: Convex-Convex collision detection issues

Pierre, thanks for you contribution. This is a very interesting and important topic for game physics development. I noticed with your demo much of the performance gains are due to multiple parallel axes being collapsed into a single test. This makes the gain much higher than it would be for more gen...
by Erin Catto
Thu Apr 17, 2008 11:52 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: A new PGS solver
Replies: 19
Views: 9847

Re: A new PGS solver

Are we discussing this paper: "An Algorithm for the Fast Solution of Linear Complementarity Problems"? The paper does not talk about using a simple block solver. The same linear algebra solver, namely PARDISO, is employed to solve the linear systems arising in Algorithm 3.1 and the interior-point me...
by Erin Catto
Thu Apr 17, 2008 8:50 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: A new PGS solver
Replies: 19
Views: 9847

Re: A new PGS solver

ODE has a direct solver based on Dantzig. Inside the Dantzig solver it has to do some LU factorizations of a big matrix. The matrix has dimensions equal to the number of active constraints. It would be nice if we could factor that big matrix by just solving small blocks, but this is not possible in ...
by Erin Catto
Thu Apr 17, 2008 5:23 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: A new PGS solver
Replies: 19
Views: 9847

Re: A new PGS solver

You can't apply a simple 6x6 block solver for the direct part because there may be kinematic loops. They are using some sort of sparse Cholesky solver on the full matrix.

In other words they need to solve the big matrix problem exactly (non-iteratively).
by Erin Catto
Tue Apr 15, 2008 6:38 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: A new PGS solver
Replies: 19
Views: 9847

Re: A new PGS solver

Hmm, this seems to require some direct solvers. It doesn't look practical for games.
by Erin Catto
Fri Apr 11, 2008 9:18 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Friction and LCP
Replies: 23
Views: 11039

Re: Friction and LCP

Several people realized that PGS and sequential impulse methods are essentially the same. Erin's contribution is mainly distributing existing knowledge to a wider audience through his excellent game developers conference slides/papers. Thanks Erwin. I agree with this mostly, except that you make it...
by Erin Catto
Fri Apr 11, 2008 5:43 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Friction and LCP
Replies: 23
Views: 11039

Re: Friction and LCP

Correct, I did not invent PGS or SI. I just kind of merged the two and tried to present the hybrid algorithm in a digestible form along with some simple code to demonstrate the theory. Also, I did not come up with the idea of the equivalence of PGS and SI, I just made it work in some publicly availa...
by Erin Catto
Wed Apr 09, 2008 10:32 pm
Forum: Career Opportunities
Topic: Game Physics/Collision Programmer - Next-Gen MMO
Replies: 0
Views: 5141

Game Physics/Collision Programmer - Next-Gen MMO

Blizzard is seeking a physics programmer to work on a Next-Gen MMO. You can find more details here:

http://jobs.blizzard.com/us/jobopp/prog ... ysics.html

Feel free to send me a PM if you have any questions about this position.

Cheers,
Erin
by Erin Catto
Mon Apr 07, 2008 5:56 am
Forum: Links, Papers, Libraries, Demos, Movies, Comparisons
Topic: Minkowski Portal Refinement (MPR) for 2D
Replies: 17
Views: 22765

Re: Minkowski Portal Refinement (MPR) for 2D

raigan: The issues you state illustrate a big problem with position based systems. You have to allow the system to violate the position constraint before you can apply any correction. Correct me if I'm wrong, but you can't prevent penetration, you can only try to measure it without missing something...
by Erin Catto
Sat Mar 29, 2008 5:23 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Comparing Box2D and 'Rigid bodies with stacking'
Replies: 6
Views: 3776

Re: Comparing Box2D and 'Rigid bodies with stacking'

So just solving all the velocity constraints enough times 'should' resolve all penetration.. No, but it helps to prevent the penetrations from becoming larger. I see.. I guess I over simplified things a bit. What then is the real difference between collision and contact solving? and where does rein...
by Erin Catto
Sat Mar 29, 2008 4:09 am
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Comparing Box2D and 'Rigid bodies with stacking'
Replies: 6
Views: 3776

Re: Comparing Box2D and 'Rigid bodies with stacking'

How do they battle position drift then? If you happen to know.. How can it be done without some sort of stabilization/projection ? You can run without position stabilization, you will just get a little penetration. The amount of penetrations depends on the time step and the number of iterations in ...
by Erin Catto
Fri Mar 28, 2008 8:04 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Comparing Box2D and 'Rigid bodies with stacking'
Replies: 6
Views: 3776

Re: Comparing Box2D and 'Rigid bodies with stacking'

I haven't implemented the NCRBWS algorithm, but my understanding is that they have no position correction.

Box2D combines collision and contact by using a velocity bias for restitution. Box2D also does not use shock propagation. Finally, Box2D clamps the accumulated impulse, which NCRBWS does not.