Collision response in a physics simulation

[Fingolfin]

Hi!

I need some help with my physics engine.

In my engine, i have two types of entities that can collide, "objects" and "boundaries". Objects are anything that moves (think bullets or players), boundaries are anything that's static (think walls). As far as collision goes, objects are represented by a radius, a position, and a height (origin is at the bottom of the "cylinder"). Boundaries are represented by a rect, maxZ, and minZ. These do not transform in any way depending on the orientation of the unit.

I have NO problem detecting wether two objects intersect. That is a piece of cake in any scenario. My problem is about what to do about it.

This is easy enough if you're dealing with spherical collision. The separating vector is ofcourse the vector between the two objects, and the minimum distance they can be from eachother is the sum of the two objects radii. The way i thought of making sure objects don't penetrate eachother, is to add a penalty force in the opposite direction strong enough to push the objects out of eachother. When an object hits a boundary, the whole force will be directed to the object. In object-object collisions, the penalty force will be divided between them based on the ratio of their mass. Pushing objects, instead of just setting their position to a certain coordinate, is good since it is more likely to solve situations where one object might push whatever is colliding with it straight into another object. A con is that it can make collision look jagged. Moving or pushing makes no difference for me.

However, when you are dealing with the kind of shapes i am, it is hard to figure out in which direction you want to push the object, and how hard. Imagine if you have an object dropping down on a roof (boundary). Once the object instersects, it will be colliding on all axes. How do i know which direction it came form? If i would be to start pushing it out on the X axis, then maybe landing in the middle of the roof would cause you to snap next to the house instead. But if i were to start correcting the Z axis, then units would be able to climb walls.

My VERY first sulotion was to not update the coordinates on a specific axis if i knew it would cause the object to collide. This produced nice sliding along walls and such, with no jaggedness, but a) it didn't work as well on the Z axis for some reason (units would get stuck inside eachother) and b) in the event that a unit does get within the bounds of another (like if dropping down on eachother) they would get stuck and start to jitter. I know this is not the solution most real physics engines use though (they use the penalty force method).

One way i thought of solving this would be to chech which axis would be closest to correct. That is, if i can get the character out of the way by either substracting the Y axis by 2, adding the X axis by 4, or adding the Z axis by 10, then the game would clearly chose to move it along the Y axis. and hence have the collision solved. When i tried this in practice though i ended up with units teleporting around and it was just generally not very satisfactory (might be me doing it wrong).

So my conclusion is, what is the best way to keep my objects from intersecting?

 

[gorillabull]

there is a pretty good physics engine here http://www.hiveworkshop.com/forums/...ine-2-4-a-142085/?prev=d=list&r=20&u=HINDYhat

as for yours its hard to say what you need without seeing the code

 

[rulerofiron99]

From what I gather, you are comfortable finding a point of intersection, and hence also an angle of intersection (line drawn between point of contact and origin of object).

You can use component forces here to get the direction and magnitude of the force that the wall will exert.

First, convert your object's velocity into x- y- and z-components.
Next, determine the magnitude of the force that will be going directly into the wall.
The force exerted by the wall onto the object will be exact opposite of this force, so then just add this to the object's current vector (vector/component addition), and you're done.

In object-object collision, you do pretty much the same thing.
Get the angle of the collision.
Get the magnitude of the force in that direction.
Add it to current component velocity.

The beauty of component form is that you can easily to into any number of dimensions.

 

[Fingolfin]

This is closer to the kind of answer i wanted. I have functions for calculating how deep the objects interpenetrate on each axis. As far as angle goes however, well.. i have no problem finding the vector between the centers of the objects but when it comes to "point of contact" between to cubes, which can be of different sizes, then there is usually an entire edge rather than a point that collides. A cube has 8 corners, and several of those can be colliding at the same time. I think you will have to clearify what point it is you're talking about.

This is how i detect collision:

Code

        static method update takes nothing returns nothing
            local object o = object.first
            local object t = object.first
            local boundary n = thistype.first
            //local boundary array parent
            //local boundary array child
            //local boolean isMoving = true
            local real a = 0
            local real b = 0
            local real c = 0
            
            loop
                exitwhen o == 0
                
                //COLLISION WITH UNITS:
                set t = object.first
                loop
                    exitwhen t == 0
                    
                    if t != o then
                    
                        set a = (o.class.radius+t.class.radius)*(o.class.radius+t.class.radius)
                        set b = (o.pos.xv-t.pos.xv)*(o.pos.xv-t.pos.xv)
                        set c = (o.pos.yv-t.pos.yv)*(o.pos.yv-t.pos.yv)
                        
                        if a > b and a > c then
                            if not(o.pos.zv+o.class.height<t.pos.zv and o.pos.zv>t.pos.zv+t.class.height) then
                                call collision.withObject(o, t)
                            endif
                        endif
                    
                    endif
                    
                    set t = t.next
                endloop
                
                //COLLISION WITH ENVIRONMENT
                if IsUnitInRegion(worldCollision, o.u) then

                    set n = boundary.first
                    loop
                        exitwhen n == 0
                        
                        if o.pos.xv+o.class.radius > GetRectMinX(n.r) and o.pos.xv-o.class.radius < GetRectMaxX(n.r) then
                            if o.pos.yv+o.class.radius > GetRectMinY(n.r) and o.pos.yv-o.class.radius < GetRectMaxY(n.r) then
                                if o.pos.zv < n.max_z and o.pos.zv+o.class.height > n.min_z then
                                    call collision.withBoundary(o, n)
                                else
                                endif
                            endif
                        endif
                        
                        set n = n.next
                    endloop
                    
                endif
                
                //END
                
                set o = o.next
            endloop
            
        endmethod

Since two objects colliding produces two collision structs, i also run a loop to clear out any doubles.
Finally, my current method for resolving the collisions looks like this:

Code

        method solve takes nothing returns nothing
        
            local real dx
            local real dy
            local real dz
            local real r1
            local real r2
            
            if .o then
            
                //This is in the event of object-object collision
            
            else
            
                //This is for object-boundary collisions
            
                call BJDebugMsg("Colliding")
            
                //Check which direction is the shortest way out of the bounds
                
                set r1 = (GetRectMinX(.b.r)-.o1.class.radius)-.o1.pos.xv
                set r2 = (GetRectMaxX(.b.r)+.o1.class.radius)-.o1.pos.xv
                
                if RAbsBJ(r1) < RAbsBJ(r2) then
                    set dx = r1
                else
                    set dx = r2
                endif
                
                set r1 = (GetRectMinY(.b.r)-.o1.class.radius)-.o1.pos.yv
                set r2 = (GetRectMaxY(.b.r)+.o1.class.radius)-.o1.pos.yv
                
                if RAbsBJ(r1) < RAbsBJ(r2) then
                    set dy = r1
                else
                    set dy = r2
                endif
                
                if .b.min_z-GetTerrainZ(.o1.pos.xv, .o1.pos.yv) < .o1.class.height then
                    set dz = (.b.max_z)-.o1.pos.zv
                else
                    set r1 = (.b.max_z)-.o1.pos.zv
                    set r2 = .b.min_z-(.o1.pos.zv+.o2.class.height)
                    
                    if RAbsBJ(r1) < RAbsBJ(r2) then
                        set dz = r1
                    else
                        set dz = r2
                    endif
                    
                endif
                
                if dx < dy and dx < dz then
                    call BJDebugMsg("Correct x")
                    set .o1.pos.xv = .o1.pos.xv+dx
                elseif dy < dx and dy < dz then
                    call BJDebugMsg("Correct y")
                    set .o1.pos.yv = .o1.pos.yv+dy
                else
                    set .o1.pos.zv = .o1.pos.zv+dz
                    call BJDebugMsg("Correct z")
                endif
            
            endif
            

            
            
            call .destroy()
        endmethod

    endstruct

 

[rulerofiron99]

Using depth, get the distance between the object centers, and offset the collision point by the ratio of the objects' sizes.

This method is based on the concept of conservation of energy; real collisions are much more complex. I'm assuming this is fine for your needs, it being a warcraft map and all. However, if you need objects to collide in a way that takes into account their surfaces and such, you'll need to use moments (ie torque, angular force), which expands the definition of an object to include angular velocity (one for each of the dimensions).

 

[Fingolfin]

I don't need to take torque into account in this, thank god.
Can i get a code/math example of what you are saying? What is hardest for me to figure out is how strong the force must be in each direction in order to push the object out. Like i mentioned, with spheres, the distance is always the sum of their radii. With squares, the distance from the center to the edges (w/2 and h/2) is different from the distance to the corners (Sqrt((w/2)^2+(h/2)^2)). When you add a third dimention it just gets more confusing to me.

 

[Cokemonkey11]

How do i know which direction it came form?

Each moving object should have a http://en.wikipedia.org/wiki/Del velocity component stored in it. That should make it easy to calculate which direction the object is intersecting from, especially if your static boundaries are rects.

For objects meeting objects, you'll need to consider 2d/3d elastic collision http://en.wikipedia.org/wiki/Elastic_collision#Two-_and_three-dimensional

Good luck.

 

[Fingolfin]

That did honestly not help me very much.
I don't understand the purpouse or application of the Del(?), but i can easily calculate what direction the object is moving by simply normalizing the velocity vector, or optionally by saving the last position in a separate vector and then substracting the positions from eachother. My problem is how to distribute the "pushing" velocity over the axes.

This is the formula i found for 3d elastic collision between spheres:

I = (1+e)*N*(Vr • N) / (1/Ma + 1/Mb)

Va – = I * 1/Ma
Vb + = I * 1/Mb

Where:

e is the coefficient of restitution
N is the surface normal
Vr is the relative velocity
M is the mass
V is the new velocity
a and b are the two objects

Anyhow, maybe i am just unsure of how the entire function is supposed to look. I am guessing i'm supposed to just pick the one plane on the boundary box that the object has collided through, and then just do a normal vector reflection onto that or something. Is there any chance anyone could make a jass (or just metacode) example of how it is supposed to work? From my understanding it is just a few lines of code.

 

[Cokemonkey11]

I don't understand the purpouse or application of the Del(?)

Okay, let's start from the basics. Let's say we have a bullet traveling from (0,0) to (500,100), and we want it to travel at 500 game units per second.

The naïve approach to storing this bullet's data would be to store its angle and velocity, so we'd do something like this:

void create(vector2 initial, vector2 final, double velocity){
    angle=initial.angleTo(final)
    velocity=500
    list.add(angle,velocity)
}

void iteration(){
    for(obj : list){
        obj.moveOffset(obj.velocity*CLOCK_PERIOD*Cos(obj.angle),obj.velocity*CLOCK_PERIOD*Sin(obj.angle)
    }
}

But the issue with this method is that for every object in every iteration, we have to execute an (expensive) cosine and sine calculation. Instead, let's store the gradient (aka the del of the velocity vector) in each object like so:

void create(vector2 initial, vector2 final, double velocity){
    angle=initial.angleTo(final)
    velocity=500
    list.add(velocity*CLOCK_PERIOD*Cos(angle),velocity*CLOCK_PERIOD*Sin(angle))
}

void iteration(){
    for(obj : list){
        obj.moveOffset(obj.delX,obj.delY)
    }
}

but i can easily calculate what direction the object is moving by simply normalizing the velocity vector, or optionally by saving the last position in a separate vector and then substracting the positions from eachother.

You should't have to normalize a velocity vector, because you should be storing the velocity components in the object (unless your projectile has variable velocity, in which case you can still calculate the gradient of the velocity vector) (saving the last position in another vector is an even worse idea)

My problem is how to distribute the "pushing" velocity over the axes.

The velocities of the objects after a collision are give in the wikipedia article I linked:

http://upload.wikimedia.org/math/8/8/5/885d12d86c36d22325d5afd7fdb4064b.png

(And the angle between them is always orthogonal)

Anyhow, maybe i am just unsure of how the entire function is supposed to look. I am guessing i'm supposed to just pick the one plane on the boundary box that the object has collided through, and then just do a normal vector reflection onto that or something. Is there any chance anyone could make a jass (or just metacode) example of how it is supposed to work? From my understanding it is just a few lines of code.

void collision(object a, object b){
    theta=a.angleTo(b)
    deflectionA=Atan2(b.mass*sin(theta),a.mass+b.mass*cos(theta))
    deflectionB=(pi-theta)/2
    velNewA=a.velocity*Sqrt(a.mass*a.mass+b.mass*b.mass+2*a.mass*b.mass*cos(theta))/(a.mass+b.mass)
    velNewB=a.velocity*2*a.mass/(a.mass+b.mass)*sin(theta/2)

    a.updateVelocity(velNewA,deflectionA)
    b.updateVelocity(velNewB,deflectionB)
}

Everything I've used is from http://en.wikipedia.org/wiki/Elastic_collision#Two-_and_three-dimensional


Edit: forgot to mention, this example takes the assumption that object a is colliding with an object which is originally stationary. For collisions with two moving objects, just calculate relative velocity http://en.wikipedia.org/wiki/Relative_velocity of one object in relation to some fictionally stationary perspective object.

 

[Fingolfin]

You use a lot more trigonometric functions than you need to in your code.
I store the orientation of each object as a quaternion, and the velocity of each object as a vector. What i meant by normalizing, is that i can make a copy of the velocity vector and normalize it to have a vector representation of the angle in which the object is moving. In my system, the velocity vector is the sum of all forces impacting on the object, and is added to the position every loop to make the object move. Note the difference between the orientation of the unit and the direction in which it is moving.

The only situation where i ever use sine or cosine is when i convert the euler angles of each objects orientation into quaternion form. Velocity, however, never uses euler angles at all, only vectors (if, for example, i want to apply a force from an explosion, i can just use the vector between the source and the object, normalize it, scale it, and then add it to the velocity). For this reason, the expensive sine and cosine operations are nothing that i am concerned with.

I am sure your deflection formula is correct, but i still think you haven't understood what i am asking for. From what i can judge, your formula is also based on the premise that the distance between the objects is always the radii of a sphere. This is not the case - the objects have cyllindrical, or sometimes cubic collision. My problem is not how to calculate bounces, or how to conserve momentum in a collision, but simply how to prevent the two cubes (or cylinders) from penetrating eachother.

Since the distance to the edge of a cube is not always as consistent as the distance to the edge of a sphere, you will instead have to choose which plane the object is intersecting with and how much force it will take to push them apart on that axis. By plane, i mean like the top, bottom, left, right, front or back of the cube.

So to summarise, i want to know:

how to calculate which [plane of the bounding box] the object is colliding with,

and

how to calculate the magnitude of the force needed for pushing them apart, to keep them from intersecting.

 

[muzzel]

Hello.

As far as i understand you are looking for a way to prevent objects of different shapes from intersecting each other. There are basically two approaches to do this:
1. You calculate the shape of the intersection. This requires you to write down the formula for the intersection shape of every possible combination of two objects. Here are the most important intersection shapes listed:
http://www.realtimerendering.com/intersections.html
Note that these calculations can be quite intense, for a warcraft 3 map i'd recomment not using them.
2. You simplify the objects by assuming they are polygons or circles/sets of circles. Then you start a loop and calculate + adjust the intersection of every single polygon-point/circle multiple times. The more often you do this, the better is your solution (but slower computation). This works great with rectangles since they are very simple polygons.
Another cool thing about this technique is: if you have lots of objects close to each other and to solve one intersection you move one object, this might create a new intersection. If you simply run this several times you make sure to solve most of these new intersections too.

However, what is the best solution depends on what you wanna do with it. If you have very few large and complex objects then you need a more exact solution than with lots of small and simply objects.

For normal intersection of two circles i have an example code from my physics engine. It doesnt know collisions yet but the maths is pretty much the same as DistanceConstraints. https://github.com/muzzel/Momentum/blob/master/wurst/MConstraint.wurst