Search found 324 matches

by Erin Catto
Sat Mar 26, 2016 11:12 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Inequality constraints: clamping impulses
Replies: 2
Views: 4224

Re: Inequality constraints: clamping impulses

There is not a strong mathematical basis for how this is handled in Box2D. All I have is a chain of arguments. It is up to you to decide if this is valid. Maybe there is a rock solid mathematical solution out there. A velocity based solver computes reaction forces (impulses) using the velocity const...
by Erin Catto
Thu Jun 02, 2011 4:13 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Broad Phase Performance
Replies: 7
Views: 11388

Re: Broad Phase Performance

My problem with SAP is that it doesn't handle varying object sizes well. Your demo seems to use boxes between 3 and 7 units (not sure what you used in your benchmarks). Imagine you have object sizes between 1 and 100 units. Then the SAP will have to check large intervals on insertion and deletion. T...
by Erin Catto
Mon Feb 21, 2011 12:50 am
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: newton is open source now!
Replies: 5
Views: 8330

Re: newton is open source now!

I think the distinction should be between velocity versus acceleration constraints instead of impulses versus forces. In other words, does the engine try to solve acceleration constraints? Baraff showed that satisfaction of acceleration constraints can lead to infinite constraint forces. A typical p...
by Erin Catto
Sun Jul 18, 2010 7:02 am
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Convex hull tool
Replies: 2
Views: 2043

Re: Convex hull tool

qhull can compute the convex hull of a vertex cloud and also intersect half spaces to yield vertices.
by Erin Catto
Fri Jan 15, 2010 9:39 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Solving two contacts at once
Replies: 7
Views: 4697

Re: Solving two contacts at once

The block solver gives a big stability increase to Box2D. I have not implemented this in 3D, but I suspect you would need to solve all points (up to 4) in block form to get a similar benefit. This gets to be a bit expensive because 4 points has 16 permutations that must be tested and you need to sol...
by Erin Catto
Wed Jul 01, 2009 5:36 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Bullet's Voronoi Simplex Solver
Replies: 46
Views: 35257

Re: Bullet's Voronoi Simplex Solver

The implications of Gino's noisy search directions causes some further trouble. Essentially, this makes GJK non-convex. If the distance increases can we assume that the previous distance was the minimum? If not, then this hypothetical case is not solvable by GJK. If the previous distance was the min...
by Erin Catto
Sun Jun 28, 2009 9:33 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Bullet's Voronoi Simplex Solver
Replies: 46
Views: 35257

Re: Bullet's Voronoi Simplex Solver

Yeah, it picks the wrong support point and terminates prematurely. The simplex is just a line segment. I guess you could call that a needle.
by Erin Catto
Fri Jun 26, 2009 5:04 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Bullet's Voronoi Simplex Solver
Replies: 46
Views: 35257

Re: Bullet's Voronoi Simplex Solver

In my example, numerical error comes when interpolating on the line segment to find the closest point (via Cramer's rule and barycentric coordinates). The signs of the cross products are correct. I encourage you to write a test program using the numbers a I provided above. In 2D, computing the face ...
by Erin Catto
Thu Jun 25, 2009 4:54 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Bullet's Voronoi Simplex Solver
Replies: 46
Views: 35257

Re: Bullet's Voronoi Simplex Solver

For 2D, we can find the sign of the search direction by computing the sign of a cross product: cross(w2 - w1, w1) The sign tells us if the origin is to the left or right of the face. If the cross product is zero we can pick an arbitrary sign knowing that the distance won't decrease. You can view the...
by Erin Catto
Wed Jun 24, 2009 8:36 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Bullet's Voronoi Simplex Solver
Replies: 46
Views: 35257

Re: Bullet's Voronoi Simplex Solver

Thanks for your reply Gino. So we should ensure that distance decreases and that a CSO vertex is not re-visited. I like this better than using a tolerance. I've seen cases where the tolerance was too loose and GJK terminated prematurely. If we tighten the tolerance than we starting getting duplicate...
by Erin Catto
Fri Jun 19, 2009 4:55 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Bullet's Voronoi Simplex Solver
Replies: 46
Views: 35257

Re: Bullet's Voronoi Simplex Solver

Yes, Casey is using this technique to find the search direction.

It is still unresolved if we need to compute the closest point to converge the distance algorithm for polytopes. As Gino has pointed out, it may be enough to detect a repeated support point.
by Erin Catto
Thu Jun 18, 2009 10:15 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Bullet's Voronoi Simplex Solver
Replies: 46
Views: 35257

Re: Bullet's Voronoi Simplex Solver

I found another problem with my GJK implementation in Box2D. Say the current simplex is a line segment: w1 = [0.021119118, 79.584320] w2 = [0.020964622, -31.515678] Using Cramer's rule we get the barycentric coordinates of the closest point on the segment to the origin: alpha1 = 0.28366950 alpha2 = ...
by Erin Catto
Thu Jun 18, 2009 9:59 pm
Forum: Links, Papers, Libraries, Demos, Movies, Comparisons
Topic: C2A: CCD library for general polygon soup models
Replies: 1
Views: 4306

Re: C2A: CCD library for general polygon soup models

Conservative advancement is basically one-sided root finding. It has trouble with fast rotating objects that are close together. Advancement can be arbitrarily small. A typical example is a domino standing vertically on a plane. Imagine that the domino is knocked over. There is already a very close ...
by Erin Catto
Tue May 19, 2009 9:42 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Bullet's Voronoi Simplex Solver
Replies: 46
Views: 35257

Re: Bullet's Voronoi Simplex Solver

Dirk Gregorius wrote:Actually you can easily build the simplex in a way such that the winding order is known. Casey explains this in his video as well.
Would you care to elaborate?

It is quite easy to fix the winding by computing the signed volume of the tetrahedron and swapping two vertices if the sign is wrong.
by Erin Catto
Thu May 14, 2009 6:18 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Position correction tutorial
Replies: 13
Views: 6953

Re: Position correction tutorial

Yeah, J has to be the Jacobian of your position constraint. We want to solve: M * (v2 - v1) = J^T * lambda J * v2 + C = 0 Where C is the current position error. We set v1 = 0 because there is no momentum in position correction. Solve: v2 = inv(M) * J^T * lambda Substitute: J * inv(M) * J^T * lambda ...