Jump to content

  • Log In with Google      Sign In   
  • Create Account

Dirk Gregorius

Member Since 24 Apr 2002
Offline Last Active May 02 2016 04:45 PM

#5263048 Axis aligned boxes and rotations

Posted by Dirk Gregorius on 21 November 2015 - 04:18 PM

If you transform a mesh you need to recompute the AABB from its transformed vertices. This can be unnecessarily expensive for broaphase culling (e.g. in physics or visibility). A simple way to conservatively transform a given AABB is this:

rnVector3 TransformedCenter = Transform * Bounds.Center;
rnVector3 TransformedExtent = rnAbs( Transform.Rotation ) * Bounds.Extent;

Here the rotation part of the transform is a 3x3 matrix and rnAbs() builds the absolute value of each element of the matrix. This formula doesn't give you the best fit AABB like transforming each vertex, but it is conservative and will contain your transformed mesh (e.g. it can be larger than necessary and yield false positives). Note that I used the center/(half)extent form of the AABB here, but it is trivial to transform from/to the min/max form. I would also not worry about the performance if you need to transform between the two!


Conceptually this formula transforms the original AABB (which now becomes an OBB) and then builds its AABB.




#5256599 Contact points confuses me

Posted by Dirk Gregorius on 10 October 2015 - 06:35 PM

The reference face is not always on A! It is defined by the face that realizes the axis of minimum penetration. The contact solver solves:


dC/dt = ( v2 + w2 x r2 - v1 - w1 x r1 ) * n


It assumes that the contact normal is pointing away from body 1. So dC/dt computes the relative velocity as seen from body 1. If it is larger zero (that means in the direction of the normal) the bodies are separating. They are approaching/penetrating otherwise. So you need to make sure that your contact normal is properly oriented to work correctly with the solver.

#5256598 Contact points confuses me

Posted by Dirk Gregorius on 10 October 2015 - 06:21 PM

Contact point creation is an art. You want stable contact points which don't create artificial torques and give the correct dynamic response. For stability you want the contact points to be coherent between frames. Ideally the contact point have a very consistent application point so that the torques are stable and the solver can balance them. If the witness features would change every frame you potentially can get very different contact points. So you favor one face over the other. The line your are quoting doesn't use a direct floating point comparison, but asks if the face is significantly better so that it justifies the potential feature flip. That is all. The paper Randy is refering to can be found here:




Why does box2d lite use two clipping operations?

A face in 2D has two side planes. You need to clip against both side planes since otherwise contact points can be outside of the body. In 3D you clip against all side planes. Which is an arbitrary number of planes.


A game might have other requirements than the physics engine and maybe assumes that the contact points are always on the surface of either body. You can translate the contact points in such a case before reporting them.


I gave a talk on contact creation this year. Maybe it gives you some ideas. Note that the suggested solutions are based on my experience over the years what works best.


#5255373 Ghost collisions with speculative contacts in 2D

Posted by Dirk Gregorius on 03 October 2015 - 11:35 AM

Speculative contacts is a cheap version to prevent tunneling. If objects are too slow to tunnel you don't need speculative contacts, right? So how to we know if an object might potentially tunnel. Given the velocities of two rigid bodies, v1, v2, w1, and w2. And also the maximum leverarm r_max (this is the length of the aabb extent in your example) and the the min thickness (this is the minimum element of your aabb) r_min.


if ( ( v2 - v1 ) * n - |w1| * r1_max - |w2| * r2_max < - ( r1_min + r2_min ) / dt ) -> no tunnel


In other words, if the worst case relative velocity along the contact normal is less than the sum of the minimum thickness divided by the timestep the objects cannot tunnel. This is just an example to give you the idea and you can of course use any variation of this. The trick for the angular velocity is simply to take the length of the angular velocity times the maximum lever arm.


In general I advice against speculative contacts. It appears to be a simple solution for a very hard problem, but in reality it creates more problems then it solves. If I look at your example I don't see any need for speculative contacts or CCD. So my suggestion would be to use simple sequential impulses (e.g. maybe learning from Box2D light).





PS: I edited the formula. I am assuming that the relative velocity is penetrating along the normal if less than zero (assuming the normal points from 1 -> 2)

#5254648 Looking for help with aab/tri collision

Posted by Dirk Gregorius on 29 September 2015 - 12:20 PM

Yes, Source uses a special iterative algorithm for box casts developed by Jay Stelly many years ago (way before MPR actually!). It is the one I loosely refer to under 3).

#5254398 Looking for help with aab/tri collision

Posted by Dirk Gregorius on 28 September 2015 - 10:21 AM

Oops, deleted my post as it slipped under the wrong topic:


For your problem you can do a couple of things:

1) Conservative advancement (see B. Mirtich's thesis here: http://www.kuffner.org/james/software/dynamics/mirtich/index.html)

2) Bracketed advancement (an extension of CA presented by E. Catto here 2013: http://box2d.org/downloads/)

3) You run a GJK-SAT between the swept AABB and the triangle. And then use a raycast in the direction of the relative moment to find your way out of the Minknowski sum. The intersection is your TOI. This is similar to Minkowski Portal Refinement (MPR).


The SAT based approaches might work as well, but I would not go through the hassle. For linear sweeps (translation only) I use 1). For non-linear sweeps (translation + rotation) I use 2)

#5253885 conservation of momentum

Posted by Dirk Gregorius on 24 September 2015 - 03:17 PM

Yes thanks, I fixed this in my post above for completeness. And I am glad you could figure it out!


The work principles are little more abstract to grasp, so just give yourself some time. Here is an example I always liked. Imagine you are cleaning your house with a basket of water. When you lift the basket up you do work W = F * h where h is the height you lift it up. If you now move around you are not doing any work anymore since the force is orthogonal to the direction you are moving. 




#5253737 conservation of momentum

Posted by Dirk Gregorius on 23 September 2015 - 05:50 PM

To answer your question, one way to derive this equation would be something along the line like this. Given the masses m1, m2, the velocities before the collision v1, v2 and the collision normal n. We are looking for the post-velocities v1', v2' and the collision impulse j. 


Since momentum must be conserved (e.g. equal and opposite impulses) and we know that the impulse is acting in the direction of the collision normal n (d'Alembert) we can now relate incoming and outgoing momentum:


m1 * v1 + j * n = m1 * v1'  <=>  v1' = v1 + j / m1 * n

m2 * v2  - j * n = m2 * v2'  <=>  v2' = v2  - j / m2 * n


These are essentially Newton equations of motion in impulse form. We have two equations for three unknowns and we need one more equation that relates the incoming and outgoing velocity. We can use that both are related by the coefficient of restitution e:


e * (v2 - v1) * n =  (v2' - v1') * n


If you now substitute these equations you can solve for the impulse j. I leave this an exercise for you. (I marked vector quantities bold as a help and a little tip is that n * n = 1 since the collision normal is a unit vector). Your equations don't show any e so simply use e = 0 which simplifies the last equation to:


(v2' - v1') * = 0


Regarding your original question we are using two physical principles here. The first is conservation of momentum which means we are applying equal and opposite impulse (e.g. +j * n in equation 1 and -j * n in equation 2). It might be actually easier to think of Newton's 2nd law here (actio = reactio). The other one is d'Alemberts principle which states that constraint forces are not doing any work. Practically this means here that the impulse is acting in the direction of the contact normal e.g: P = j * n. The coefficient of restitution works essentially as a velocity constraint which relates the in and outgoing velocities.










#5253692 conservation of momentum

Posted by Dirk Gregorius on 23 September 2015 - 11:11 AM

Sorry, what you are writing doesn't make any sense at all:


Impulse is defined as P = m * v. But you write it is P = v / m. Then you write P = v / ( 1 / m ). How do expect to make sense of such a mess? The code snippet shows a scalar impulse and your derivation a vector impulse. Finally, if I get you correctly you want to compute a contact impulse, but there is no contact normal. This is all too 'hand-wavy' without any context and obviously you have no idea what you are doing (I don't mean that with any offense!). I recommend to study some basic mechanics and math. Here is some good reference (see the simulation section 'collision response' near the bottom for you specific question). 



To derive these equations you also need d'Alemberts principle. Funnily there was a very good article here on GameDev.net recently:




If you want to study those things I recommend some other books that might be more helpful to you: 




Both the physics and math tutorial have plenty of free material on this topic. You can find the math material in the link above and the physics material here:


#5253351 conservation of momentum

Posted by Dirk Gregorius on 21 September 2015 - 03:50 PM

You are applying equal and opposite impules. So when you make the momentum balance for the *whole* system it will not change. The momentum of individual particles can indeed change. But the sum will not.

#5252537 Realtime collision with dynamic concave meshes

Posted by Dirk Gregorius on 16 September 2015 - 10:57 AM

This is a very tough problem to solve and I am not aware of any solution for this in realtime. If I needed to solve this I would start from this paper using SDF:



The SDF are very intensive in memory (e.g. PhysX had an implementation of this called PMeshes for a while, but dropped it again because of the high memory usage) so you would need to come up with some kind of compression. I heard there has been some good experience with low band SDF in the FX field recently, but I have no practical experience. In games you usually take much simpler approaches. Dennis gave a presentation on this at GDC here:



There are some good SDF libraries out there which might be a good start. The authors of the libraries might be good initial contacts as well:



HTH and good luck!


#5251957 Problem implementing sequential impulse mass over 100Kg (solved, it was a mis...

Posted by Dirk Gregorius on 12 September 2015 - 06:55 PM

Did you disable position correction? I can be everything from wrong contact points, to wrong Jacobians, to wrong inertia. Whatever this is it is unrelated to the mass!


Is z your up axis?

And use temporaries! How do you expect that anyone can read this: vr.set(vr2.set(b2.rotation).cross(r2).add(b2.velocity)).sub(vr1.set(b1.rotation).cross(r1).add(b1.velocity));

#5251588 How to determine closest point on plane vs aabb

Posted by Dirk Gregorius on 10 September 2015 - 01:08 PM

I don't understand why you want to return the projected center in case the plane is axis aligned. The vertices should be equally good. Here is how I would break this up. Maybe it helps.

Vector3 ClosestPointOnPlane( Bounds3 aabb, Plane plane )
    Vector3 support = aabb->Support( -plane.m_Normal );
    return plane.Project( support );

Vector3 Bounds3::Support( Vector3 v )
    Vector support;
    support.x = v.x < 0 ? m_Min.x : m_Max.x;
    support.x = v.y < 0 ? m_Min.y : m_Max.y;
    support.x = v.z < 0 ? m_Min.z : m_Max.z;

    return support;

Vector Plane::Project( Vector3 p )
    float distance = dot( m_Normal, p ) - m_Offset;
    return p - distance * m_Normal;

#5251425 How to determine closest point on plane vs aabb

Posted by Dirk Gregorius on 09 September 2015 - 04:47 PM

Just get the support point on the box in the negative direction of the plane normal. This will give you both the closest point and penetration

#5250656 How can I implement warmstart?

Posted by Dirk Gregorius on 04 September 2015 - 11:07 PM

Base your engine on Box2d Lite and study all of the GDC presentations and you will be fine! :)