How do I determine whether two 2D circles are colliding or just in contact with each other? The thing is that my circle - circle collisions are unstable when there are many circle all close together. Such that when two circles should be just barely touching each other (without exchanging momentum) but instead their are constantly in collision mode and freely exchange what little momentum is left. When there are layers of balls resting on top of other balls (so that some balls are not touching a solid surface beyond the surfaces of its neighbouring circles) some of these balls will still be under the effect of gravity which adds feul to the fire and causes all the circles to vibrate like a bunch of jitter bugs.
Now how do I differentiate between colliding with an object and merely resting whilst in contact with it. Any ideas are appreciated.
Heres the collision routine as it is now. To run it you will need Jims ps2Yabasic emulator which can be found in the first post of this topic: http://dbfinteractive.com/index.php?topic=758.0
open window 640, 512
tolerence = 1.10
gravity = 0.20
friction = 0.80
bounce = 0.80
minmotion = 0.10
move = 0.0
balls = 26
dim posx(balls), posy(balls)
dim dirx(balls), diry(balls)
dim radi(balls)
label reset
for b = 0 to balls
dirx(b) = ran(move) - ran(move)
diry(b) = ran(move) - ran(move)
radi(b) = 32 // int(ran(8)) + 16
0: posx(b) = ran(640-radi(b)-radi(b)) + radi(b)
posy(b) = ran(512-radi(b)-radi(b)) + radi(b)
for a = 0 to b
if (a <> b) then
adj = abs(posx(a) - posx(b))
opp = abs(posy(a) - posy(b))
hyp = adj*adj + opp*opp
if (hyp <= (radi(a)+radi(b))*(radi(a)+radi(b))) goto 0
endif
next
next
wait 0.1
label main
wait 0.01
setdispbuf draw
draw = 1 - draw
setdrawbuf draw
clear window
setrgb 1, 016, 006, 006
setrgb 2, 016, 006, 006
setrgb 3, 255, 100, 100
gtriangle 0,0 to 640,0 to 640,512
setrgb 2, 255, 100, 100
gtriangle 0,0 to 0,512 to 640,512
for b = 0 to balls
setrgb 1, 016, 016, 128
fill circle posx(b), posy(b), radi(b) * tolerence
clear fill circle posx(b), posy(b), radi(b)
rgb = 20
for r = radi(b) to 8 step - 4
setrgb 1, 000, 000, rgb
fill circle posx(b), posy(b), r
rgb = rgb + 20
next
diry(b) = diry(b) + gravity
next
if (inkey$(0) <> "") then
goto reset
endif
for a = 0 to balls
if (dirx(a) <> 0.0) or (diry(a) <> 0.0) then
collision = 0
for b = a to balls
if (dirx(b) <> 0.0) or (diry(b) <> 0.0) then
if (a <> b) then
adj = posx(b) - posx(a)
opp = posy(b) - posy(a)
dist = adj^2 + opp^2
if (dist < (radi(a)+radi(b))*(radi(a)+radi(b))) then
dist = sqrt(dist)
nx = adj / dist
ny = opp / dist
cx = (posx(a) + posx(b))*0.5
cy = (posy(a) + posy(b))*0.5
posx(a) = cx - nx*radi(a)*tolerence
posy(a) = cy - ny*radi(a)*tolerence
posx(b) = cx + nx*radi(b)*tolerence
posy(b) = cy + ny*radi(b)*tolerence
product = (dirx(b)-dirx(a))*nx + (diry(b)-diry(a))*ny
dirx(a) = dirx(a) + nx * product * friction
diry(a) = diry(a) + ny * product * bounce
dirx(b) = dirx(b) - nx * product * friction
diry(b) = diry(b) - ny * product * bounce
if (posx(b) < radi(b)) posx(b) = radi(b)
if (posx(b) = radi(b)) dirx(b) =-dirx(b) * friction
if (posx(b) > 640-radi(b)) posx(b) = 640 - radi(b)
if (posx(b) = 640-radi(b)) dirx(b) =-dirx(b) * friction
if (posy(b) < radi(b)) posy(b) = radi(b)
if (posy(b) = radi(b)) diry(b) =-diry(b) * bounce
if (posy(b) > 512-radi(b)) posy(b) = 512-radi(b)
if (posy(b) = 512-radi(b)) diry(b) =-diry(b) * bounce
if (posx(a) < radi(a)) posx(a) = radi(a)
if (posx(a) = radi(a)) dirx(a) =-dirx(a) * friction
if (posx(a) > 640-radi(a)) posx(a) = 640 - radi(a)
if (posx(a) = 640-radi(a)) dirx(a) =-dirx(a) * friction
if (posy(a) < radi(a)) posy(a) = radi(a)
if (posy(a) = radi(a)) diry(a) =-diry(a) * bounce
if (posy(a) > 512-radi(a)) posy(a) = 512-radi(a)
if (posy(a) = 512-radi(a)) diry(a) =-diry(a) * bounce
collision = 1
fi
fi
endif
next
if (collision = 0) then
posx(a) = posx(a) + dirx(a)
posy(a) = posy(a) + diry(a)
if (posx(a) < radi(a)) then
posx(a) = radi(a)
dirx(a) =-dirx(a) * friction
elsif (posx(a) > 640-radi(a)) then
posx(a) = 640 - radi(a)
dirx(a) =-dirx(a) * friction
fi
if (posy(a) < radi(a)) then
posy(a) = radi(a)
diry(a) =-diry(a) * bounce
elsif (posy(a) > 512-radi(a)) then
posy(a) = 512-radi(a)
diry(a) =-diry(a) * bounce
fi
else
if (posx(a) < radi(a)) posx(a) = radi(a)
if (posx(a) = radi(a)) dirx(a) =-dirx(a) * friction
if (posx(a) > 640-radi(a)) posx(a) = 640 - radi(a)
if (posx(a) = 640-radi(a)) dirx(a) =-dirx(a) * friction
if (posy(a) < radi(a)) posy(a) = radi(a)
if (posy(a) = radi(a)) diry(a) =-diry(a) * bounce
if (posy(a) > 512-radi(a)) posy(a) = 512-radi(a)
if (posy(a) = 512-radi(a)) diry(a) =-diry(a) * bounce
endif
if (diry(a) >=-minmotion) and (diry(a) <= minmotion) then
diry(a) = 0.0
endif
if (dirx(a) >=-minmotion) and (dirx(a) <= minmotion) then
dirx(a) = 0.0
endif
endif
next
goto main
The way I dealt with this was to use the movement vectors of the circles and going through every possible pair of circles find which collide first and find the time (could be 0.0 to 1.0 from one frame to the next) at which they collide. Then recalculate the positions of all the circles at that time along with the new vectors of the circles that collided, repeat that until there are no more collisions and time=1.0 . I think I posted the code for it somewhere.
EDIT:
http://dbfinteractive.com/index.php?topic=1432.0
I will be having a good look through that. This situation is very similar to when the pool balls are racked up and they are all touching. Thanks Stonemonkey.
This stabilises it a little. Changed settings to this (a quick fix but still a little jumpy):
tolerence = 0.99
gravity = 0.20
friction = 0.98
bounce = 0.50
minmotion = 0.10
move = 0.0
Alternatively:
Tie the 'bounce' rate to the movement speed of the balls during runtime.
As the amount of bounce is usually dependant on the rate of travel.
At resting time, bounce would be 0. Therefor pushing only will result :)
I read somewhere that sleep states are the way to solve this. Basically a ball that is sleeping wont move and wont need physics until a ball that is awake comes along and smashes into it. This wakes up the sleeping ball and physics kicks in again. You cant simply check to see if the ball is barely moving to do this because a ball that is jumping will go to sleep at the peek of the jump (when gravity cancels out the upward motion) now in this situation you dont want to put the ball to sleep. It needs to be in contact with another surface but not colliding with that surface. That aint an easy state to check for in this situation because the upper balls will always have a motion vector due to gravity.
Maybe stonemonkeys solution is better because only one collision can take place each frame. With so many balls colliding with each other it should slow it all down to a crawl. Though when I calculate many collisions within one frame I will have to include a pipeline. All of those collision are due to take place within the same frame. it is more true to the order in which the collisions happen but it is not true to the timeline in which it all happens. I would imagine it would still appear perfectly natural though.
hi, my solution takes all the collisions that occur within a frame into account, including collisions that occur due to a change in direction caused by another collision within the same frame.
i take the time from one frame to the next as 0.0 to 1.0 and test for all possible collisions and calculate the time they occur. say there are 2 collisions detected, one at 0.3 and one at 0.6 then i move all the balls to where they should be at the time of the first collision (0.3) and do the calcs for that collision then re-test for all possible collisions and repeat until no more collisions within that frame are detected.
also, i use a fixed framerate for that independent of the screen refresh, maybe something like 50 or 100 fps.
I'm still not sure about my calcs for new vectors with ball-ball collisions but it seems to work pretty well.
rain-storm, did you figure it out ?
Not as of yet but I haven't given up. I am now looking at alternatives namely the separating axis theorem. It may very well be a small imperfection in the math. But I've looked at the code long and hard and I just can't see it. This algorithm was designed for a pool game so it must be my interpretation of the algorithm. At any rate the separating axis theorem has the potential of handling many sided polygons and not just circles which is the next logical step forward from here.
I had a similar problem with a program like this, although it uses rectangles not spheres.
But it may work for you.
The found that the bounce force (or deflection speed rather) in my demo was being multiplied by the
number of objects in the stack.
edit -
mmm, maybe not.
my bounce was set up very differently. I changed it and the demo fails
I see what you mean about the sleep state occuring when they reach the peak of bounce.
Not helpful at all. :-\
This is an interesting one. I'd like to know how to solve this too.
My demo does exactly the same thing rain.
I have another thought, what about dampening ?
Friction and bounce are suppose to control the dampening but experimenting with those values is useless I find. There is something else wrong. I think that because the circles are so close together there are alot of potential overlaps especially after a new position is plotted. After all I dont check to see if that new position is clear with the circles that have already been treated. Every pair gets treated to only once regardless of how many collisions have been detected. Maybe this is the flaw?
No idea if this will help rain, but here's a video of a similar program i made.
less than 1mb WMV video:
[link removed]
All the rectangles have no speed of their own, only gravity and forces applied.
This is running with sleep, but if you watch the demo closely, you will see
that when all the blocks have settled they continue to move under the
influence of gravity ?
Atleast that's what I thought... but even if I dissable the gravity on the sleeping
particles it continues. So I definately must have missed something, and didn't get around
to stabilizing it fully :-\
I made this simulation to create 'sand / salt' effect for example, as you can set the
offset speed which each block allows for pushing other particles away from each other.
update -
Latest Test !
[link removed]
Momentum was causing my problem.
Friction, gravity, bounce etc were all default.
Ok, here's a short version of the routine i used for the above program:
rem Sleep checking IPC
rem ==============
for i = 1 to objects
rem Inter particle collision
repeat
for j = 1 to objects
if j <> i then
if (j is touching but not intersecting i) and (j is slower than the speed tolerance) then
j is sleeping
goto skipcheck
fi
label retest
if (j is intersecting i and not touching) then rem a collision is detected
calculate Collision method of your choice between i and j :P
goto retest rem just to make sure your collision code worked (optional)
else
rem no collision found
fi
label skipcheck
fi
next
until (no collisions can be found)
next
I'm not a seasoned programmer rain, so i'm sure there's a better way of
writing this. But I hope you find something in the pseudo useful for your program.
It works for rectangles, so i'm sure it should work for circles.
edit - posted wrong video link.
I got it all working to a time-line now but I still have to hunt out a bug or two first. I think one is due to two or more collisions occuring simultaeniously, because they are moving by a unit length it does happen sometimes. I have 2 pairs of arrays that hold movement vectors one pair is the standard movement the other pair is post collision movement. Now if more than one collision happens at the same time. I have to keep track of the time of each collision and what the object was colliding with. Still workin out how to do this efficiently. But onto the point of this post.
I spotted something which I overlooked before. My previous code for conserving energy only took friction into consideration. It ignored mass and energy lost from heat, spin, sound, deformation etc. Now I have mass included in the equation as well as a constant value that represents all the rest of the lost energy. This has greatly improved the realism of the objects slowing down gradually. I will post the code once I have managed to get those darn missed collision detected. :P
Heres what i got but its runnin really slow with gravity <> 0.0 but without gravity it runs at a good pace. It needs some serious optimising to get the speed back up. It seems stable enough though. I think a little repulsive force that cancels out gravity is needed for objects that are at rest on a surface. which brings me back to how do you decide whether two objects are colliding or just in contact with each other. Well its definately more stable and looks better. Its just slower than I had hoped it would be.
open window 640, 512
window origin "cc"
gravity = 0.1
ed = 0.8 // energy NOT lost due to heat / deformation / sound
ew = 0.8 // same as ed but for circle to wall
bouncew = 0.8 // bounce with walls
frictionw = 0.98 // friction with walls
RT = 1.01 // radius tolerence must be above 1.0
polys = 8
dim mass(polys), radi(polys)
dim posX(polys), posY(polys)
dim dirX(polys), dirY(polys)
dim vecX(polys), vecY(polys)
for p = 0 to polys
mass(p) = 1.0
radi(p) = 30
posX(p) = ran(200)-ran(200)
posY(p) = ran(200)-ran(200)
dirX(p) = ran(10)-ran(10)
dirY(p) = ran(10)-ran(10)
next
walls = 3
dim x1(walls), y1(walls), x2(walls), y2(walls)
for w = 0 to walls
read x1(w), y1(w), x2(w), y2(w)
next
data -300,-230, 300,-230
data 300,-230, 300, 230
data 300, 230,-300, 230
data -300, 230,-300,-230
label main
wait 0.01
setdispbuf draw
draw = 1 - draw
setdrawbuf draw
clear window
setrgb 1, 255, 255, 255
T = TIME
text -300,-240, "TIME " + str$(TIME)
for p = 0 to polys
circle posX(p), posY(p), radi(p)
next
for w = 0 to walls
line x1(w),y1(w) to x2(w),y2(w)
next
ctrl = peek("port1")
if (and(ctrl, 16) <> 0) dirY(0) = dirY(0) - 1.0
if (and(ctrl, 32) <> 0) dirX(0) = dirX(0) + 1.0
if (and(ctrl, 64) <> 0) dirY(0) = dirY(0) + 1.0
if (and(ctrl,128) <> 0) dirX(0) = dirX(0) - 1.0
for p = 0 to polys
if (dirX(p) > -0.1) and (dirX(p) < 0.1) dirX(p) = 0.0
if (dirY(p) > -0.1) and (dirY(p) < 0.1) dirY(p) = 0.0
dirY(p) = dirY(p) + gravity
next
//repeat
TIME = 1.0
for p = 0 to polys
vecX(p) = dirX(p)
vecY(p) = dirY(p)
next
setrgb 1, 000, 000, 255
for A = 0 to polys
for w = 0 to walls
NEWTIME = circ2edgeDetect(A, x1(w),y1(w),x2(w),y2(w), 1.0)
if (NEWTIME < TIME) then
TIME = NEWTIME
CA = A
CW = w
CC = 1
endif
next
for B = A to polys
if (A <> B) then
NEWTIME = circ2circDetect(A, B, 1.0)
if (NEWTIME < TIME) then
TIME = NEWTIME
CA = A
CB = B
CC = 2
endif
endif
next
next
if (TIME < 1.0) then
if (CC = 1) circ2edgeRespond(CA, x1(CW),y1(CW),x2(CW),y2(CW), TIME)
if (CC = 2) circ2circRespond(CA, CB, TIME)
endif
for p = 0 to polys
posX(p) = posX(p) + TIME*dirX(p)
posY(p) = posY(p) + TIME*dirY(p)
next
if (TIME < 1.0) then
dirX(CA) = vecX(CA)
dirY(CA) = vecY(CA)
if (CC = 2) then
dirX(CB) = vecX(CB)
dirY(CB) = vecY(CB) - gravity
endif
if (CC = 1) then
dirY(CA) = dirY(CA) - gravity
endif
endif
//until (TIME = 1.0)
goto main
// Swept Circle <-> Static Line Segment
sub circ2edgeDetect(A, x1,y1,x2,y2, T)
// test for overlap at starting positions
local N, px,py,vx,vy,r, denom,numea,ua, xb,yb,d
N = T
px = posX(A)
py = posY(A)
vx = dirX(A)
vy = dirY(A)
r = radi(A)*RT
denom = (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)
numea = (px-x1)*(x2-x1) + (py-y1)*(y2-y1)
ua = numea / denom
if (ua < 0.0) then ua = 0.0
elsif (ua > 1.0) then ua = 1.0
endif
xb = x1 + ua*(x2-x1)
yb = y1 + ua*(y2-y1)
d = (px-xb)*(px-xb) + (py-yb)*(py-yb)
if (d < r*r) then
d = r / sqrt(d)
posX(A) = xb + (px-xb)*d
posY(A) = yb + (py-yb)*d
endif
// test for collision with vertices
local nx,ny, B,C,D, dx,dy,ax,ay,bx,by
r = radi(A)
nx = px + T*vx
ny = py + T*vy
B = (nx-px)*(nx-px) + (ny-py)*(ny-py)
if (B > 0.0) then
C = 2*((nx-px)*(px-x1) + (ny-py)*(py-y1))
D = C*C - 4*B*((px-x1)*(px-x1) + (py-y1)*(py-y1) - r*r)
if (D > 0.0) N = (-C - sqrt(D)) / (2*B)
if (N <= T) and (N > 0.0) T = N
C = 2*((nx-px)*(px-x2) + (ny-py)*(py-y2))
D = C*C - 4*B*((px-x2)*(px-x2) + (py-y2)*(py-y2) - r*r)
if (D > 0.0) N = (-C - sqrt(D)) / (2*B)
if (N <= T) and (N > 0.0) T = N
endif
// test for collision with line segment
B = r * sig((x1-px)*(y2-py) - (x2-px)*(y1-py)) / sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1))
C = B * (y2-y1)
D = B * (x2-x1)
ax = x1 - C
ay = y1 + D
bx = x2 - C
by = y2 + D
D = (by-ay)*(nx-px) - (bx-ax)*(ny-py)
if (D = 0.0) return T
D = 1 / D
C = ((nx-px)*(py-ay) - (ny-py)*(px-ax)) * D
if (C >= 0.0) and (C <= 1.0) then
N = ((bx-ax)*(py-ay) - (by-ay)*(px-ax)) * D
if (N <= T) and (N > 0.0) T = N
endif
return T
end sub
sub circ2edgeRespond(A, x1,y1,x2,y2, T)
local px,py,nx,ny,r, C,xi,yi
px = posX(A) + T*dirX(A)
py = posY(A) + T*dirY(A)
nx = px + dirX(A)
ny = py + dirY(A)
r = radi(A)
C = ((px-x1)*(x2-x1) + (py-y1)*(y2-y1)) / ((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1))
if (C < 0.0) C = 0.0
if (C > 1.0) C = 1.0
xi = x1 + C*(x2-x1)
yi = y1 + C*(y2-y1)
C = r / sqrt((xi-px)*(xi-px) + (yi-py)*(yi-py))
x1 = px - (yi-py)*C
y1 = py + (xi-px)*C
x2 = px + (yi-py)*C
y2 = py - (xi-px)*C
C = ((nx-x1)*(x2-x1) + (ny-y1)*(y2-y1)) / ((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1))
xi = x1 + C*(x2-x1)
yi = y1 + C*(y2-y1)
vecX(A) = ((xi-px)*frictionw - (nx-xi)*bouncew)*ew
vecY(A) = ((yi-py)*frictionw - (ny-yi)*bouncew)*ew
end sub
// Swept Circle <-> Swept Circle
sub circ2circDetect(A, B, T)
// test for overlap at starting positions
local N, adj,opp,hyp, vA,vB,vC,vD,vE,c, x,y,xi,yi,ix,iy
adj = posX(A) - posX(B)
opp = posY(A) - posY(B)
hyp = adj*adj + opp*opp
if (hyp < (radi(A)+radi(B))*(radi(A)+radi(B))) then
hyp = 1 / sqrt(hyp)
adj = adj*hyp
opp = opp*hyp
x = (posX(A) + posX(B))*0.5
y = (posY(A) + posY(B))*0.5
posX(A) = x + radi(A)*adj
posY(A) = y + radi(A)*opp
posX(B) = x - radi(B)*adj
posY(B) = y - radi(B)*opp
endif
// test that distance traveled is sufficient for collision
vA = sqrt((posX(B)-posX(A))*(posX(B)-posX(A)) + (posY(B)-posY(A))*(posY(B)-posY(A)))
vB = sqrt((dirX(A)-dirX(B))*(dirX(A)-dirX(B)) + (dirY(A)-dirY(B))*(dirY(A)-dirY(B)))
if (vB < vA-(radi(A)+radi(B))) return T
// test that vectors are moving towards each other
c = ((posX(B)-posX(A))*(dirX(A)-dirX(B)) + (posY(B)-posY(A))*(dirY(A)-dirY(B))) / ((dirX(A)-dirX(B))*(dirX(A)-dirX(B)) + (dirY(A)-dirY(B))*(dirY(A)-dirY(B)))
if (c <= 0.0) return T
// test that circles actually overlap at swept intersection
xi = posX(A) + c*(dirX(A)-dirX(B))
yi = posY(A) + c*(dirY(A)-dirY(B))
vC = sqrt((posX(B)-xi)*(posX(B)-xi) + (posY(B)-yi)*(posY(B)-yi))
if (vC > radi(A)+radi(B)) return T
// refine calculated time of collision
vD = sqrt((posX(A)-xi)*(posX(A)-xi) + (posY(A)-yi)*(posY(A)-yi))
vE = sqrt((radi(A)+radi(B))*(radi(A)+radi(B)) - vC*vC)
ix = xi - vE*(dirX(A)-dirX(B)) / vB
iy = yi - vE*(dirY(A)-dirY(B)) / vB
N = ((ix-posX(A))*(dirX(A)-dirX(B)) + (iy-posY(A))*(dirY(A)-dirY(B))) / ((dirX(A)-dirX(B))*(dirX(A)-dirX(B)) + (dirY(A)-dirY(B))*(dirY(A)-dirY(B)))
if (N <= 0.0) or (N > T) return T
return N
end sub
sub circ2circRespond(A, B, T)
// calculate positions at time of collision
local x1,y1,x2,y2,D,ax,ay, va1,vb1,va2,vb2,vaP1,vaP2
x1 = posX(A) + T*dirX(A)
y1 = posY(A) + T*dirY(A)
x2 = posX(B) + T*dirX(B)
y2 = posY(B) + T*dirY(B)
D = 1 / sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1))
ax = (x2-x1) * D
ay = (y2-y1) * D
va1 = dirX(A)*ax + dirY(A)*ay
vb1 =-dirX(A)*ay + dirY(A)*ax
va2 = dirX(B)*ax + dirY(B)*ay
vb2 =-dirX(B)*ay + dirY(B)*ax
vaP1 = va1 + (1+ed)*(va2-va1) / (1+mass(A)/mass(B))
vaP2 = va2 + (1+ed)*(va1-va2) / (1+mass(B)/mass(A))
vecX(A) = vaP1*ax - vb1*ay
vecY(A) = vaP1*ay + vb1*ax
vecX(B) = vaP2*ax - vb2*ay
vecY(B) = vaP2*ay + vb2*ax
end sub
Definately more stable :kewl:
Great!
Look real too. Although some times the balls seem to stick to each other, or the suddenly jump as if you pressed UP... not sure why.
I did get it two circles to intersect and cause flickering between them lol. That was because I was d-padding it hahaha.