I've noticed most collsion detection is done per frame (even mine...). Calc new pos, check for collision, move, repeat. But everything involved in the movement of most objects is based on a formula of some sort (gravity and momentum mainly) which (I assume) can be integrated and set equal to the equation of a plane to test for collisions only once. Has anybody here done this already? Granted this can only be applied to "dumb" objects that follow only the laws of physics, such as a bouncing ball. Even then, a new equation would have to be solved after every collision to determine the new trajectory and such.

It can be done, it has been done, and it's much more complicated than checking for collisions every frame. If the collision geometry is simple, then maybe it could be done without too much trouble. As the geometry and physics get more complicated and the number of objects increases, doing collision detection in this way becomes increasingly troublesome.

In the world of videogames and animation, where the exact time and order of collisions is almost always unimportant as long as it looks right, most games just use the simple and reliable method of checking for penetrating objects every frame.

Calculating the exact moment of pending collisions and dealing with them using a priority queue may be more appropriate for a high accuracy physics simulation.

I've done this. I tried it with a sphere and a plane. Works beautifully. Way tougher with most other stuff though. Basically you have a plane equation:

Ax + By + Cz + D = 0

And you have the equation of a point in motion in 3d space:

s(t) = s0 + v0t + 0.5at^2

where s, s0, v0, and a are vectors in terms of x,y,z

The contact point on a sphere will always be the position of the center of the sphere plus the radius of the sphere multiplied by the plane normal. So you can the use contact point as the point in equation 2.

You can sub in the contact point into eq.2 like this

s(t) = rN + s0 + v0t + 0.5at^2

where r and N are the radius of the sphere and the normal of the plane respectively.

You can then sub in the x,y,z values of s(t) into the plane equation like this:

A(rNx + s0x + v0xt + 0.5axt^2) + B(rNy + s0y + v0yt + 0.5ayt^2) + C(rNz + s0z + v0zt + 0.5azt^2)

This is a quadratic equation with t as an independent variable. You can solve for t by rearranging it like this:

(0.5Aax + 0.5Bay + 0.5 Caz)t^2 + (Av0x + Bv0y + Cv0z)t + (ArNx + BrNy + CrNz + As0x + Bs0y + Cs0z)

Solve for t by using the quadratic equation. Pick out the smallest real value of t that is is within your timestep. This value is time when your sphere collides with your plane. From this, you can find the velocity and position of your sphere at the collision point and apply an appropriate collision response scheme.


You may also want to google swept collision detection. This is a similar method. Hope all of that helped.

thanks, Erkokite. Great help! I got a small demo working in 2d (easier to troubleshoot) and it should be simple adding another dimension. Precalculated collisions is definetly the way to go! I've got stuff moving around with huge timesteps and extremely accurate collisions. Very effecient too- a single calculation for each collision rather than hundreds of calculations when doing per-frame.

Here's a demonstration. I would have something cooler, but my compy froze up on me and I had to redo the entire thing. Not too bad, considering it's in Basic4gl and quick coding, but still lost me a good 3 hours. Anyway, it's all 2D and has a bunch of points that bounce off walls. Each point has an individual position/velocity/acceleration and use the function p(t) = p0 + v0t + .5a0t^2 for movement. The only trouble I'm having is collisions with vertical walls- which means dividing by a very small number (innacurate results). I'm sure there's an easy workaround but I'm too busy right now to look into it (stupid homework...).

If you want to run this program, go download Basic4gl from www.basic4gl.net . Trust me, it's worth your while. Even though Basic4gl can't compete with c++ or other machine languages, nothing beats it for coding up a quick graphics demo program where speed isn't a major issue.


' Equation-based collision detection
' by Xenovacivus

' Press space bar to view trajectories

const BALLCOUNT = 50

struc sBall
dim pos# (1)
dim vel# (1)
dim acc# (1)

dim reflect# (1)
dim contact# (1)
dim slope# (1)
dim contactTime#
dim timer#
dim reflectSpeed#
dim currentSpeed#

dim color# (2)
endstruc

dim sBall ball (BALLCOUNT)
dim sBall &testBall

dim j
for j = 0 to BALLCOUNT
ball (j).pos# = vec2 (0, 0)
ball (j).vel# = vec2 ((j*50)/(BALLCOUNT*1.0), (j*25)/(BALLCOUNT*1.0))
ball (j).acc# = vec2 (0, -4.9) 'acceleration due to gravity: .5*gravity (here, g = -9.8m/s^2)
ball (j).color# = Normalize (vec3 (rnd () % 100 + 50, rnd () % 100 + 50, rnd () % 100 + 50))
next

struc sLine
dim vertex# (1)(1)
dim normal# (1)
dim scalar#

dim center# (1)
dim length#
endstruc

dim sLine line (10)

line (0).vertex# (0) = vec2 (-105, -80)
line (0).vertex# (1) = vec2 (-60, -70)
line (1).vertex# (1) = vec2 (-50, -50)
line (2).vertex# (1) = vec2 (-30, -60)
line (3).vertex# (1) = vec2 (20, -80)
line (4).vertex# (1) = vec2 (40, -70)
line (5).vertex# (1) = vec2 (90, -70)
line (6).vertex# (1) = vec2 (100, 80)
line (7).vertex# (1) = vec2 (10, 50)
line (8).vertex# (1) = vec2 (-40, 50)
line (9).vertex# (1) = vec2 (-100, -30)
line (10).vertex# (1) = line (0).vertex# (0)

dim i

for i = 1 to 10
line (i).vertex# (0) = line (i-1).vertex# (1)
next

for i = 0 to 10
line (i).normal# = MatrixRotateZ (90) * Normalize (line (i).vertex# (1) - line (i).vertex# (0))
line (i).scalar# = line (i).normal# * line (i).vertex# (0)
line (i).length# = Length (line (i).vertex# (0) - line (i).vertex# (1))
line (i).center# = (line (i).vertex# (0) + line (i).vertex# (1)) * .5
next
dim a#, b#, c#, time#, point# (1), shortestTime#
dim normal# (1)
goto start

CalcEq:
shortestTime# = -1
for i = 0 to 10
a# = line (i).normal# * testBall.acc#
b# = line (i).normal# * testBall.vel#
c# = line (i).normal# * testBall.pos# - line (i).scalar#

time# = ((-b# - sqrt (b#*b# - 4.0*a#*c#)) / (2*a#))

point# = testBall.pos# + testBall.vel# * time# + time#*time# * testBall.acc#
point# = testBall.pos# + time# * (testBall.vel# + time# * testBall.acc#)

' Check if point is actually on a line and within the vertices-
if abs (point# * line (i).normal# - line (i).scalar#) <= .001 then
if Length (Point# - line (i).center#) < (line (i).length# *.5) and time# > 0 then
if time# < shortestTime# or shortestTime# = -1 then
shortestTime# = time#
normal# = line(i).normal#
testBall.contact# = point#

endif
endif
endif

next

'// Calculate trajectory and info for next collision-
testBall.contactTime# = shortestTime#
testBall.slope# = -Normalize (testBall.acc# * shortestTime#*2 + testBall.vel#)
testBall.reflect# = -testBall.slope# + normal# * 2 * (normal# * testBall.slope#)
testBall.reflectSpeed# = length (ball (0).vel# + ball (0).acc# * 2*shortestTime#)

return


start:
TextMode (TEXT_OVERLAID)
glPointSize (5)

for j = 0 to BALLCOUNT
&testBall = &ball (j)
gosub CalcEq
next

dim firstTick
dim frames
firstTick = tickCount ()
dim averageTick#

while true
glClear (GL_COLOR_BUFFER_BIT or GL_DEPTH_BUFFER_BIT)
glLoadIdentity ()
cls
frames = frames + 1
averageTick# = (tickCount () - firstTick) / (frames*1.0)
printr "FPS "1000 / averageTick#

glTranslatef (0, 0, -150)


'// Draw lines-
glBegin (GL_LINES)
for i = 0 to 10
glColor3f (0, 1, 0)
glVertex2fv (line (i).vertex# (0))
glVertex2fv (line (i).vertex# (1))

glColor3f (0, 0, 1)
glVertex2fv (line (i).center#)
glVertex2fv (line (i).center# + line (i).normal#)
next
glEnd ()


'// Draw and calculate for balls-
for j = 0 to BALLCOUNT

'// Draw the ball-
glColor3fv (ball (j).color#)
glBegin (GL_POINTS)
time# = ball (j).timer#
point# = ball (j).pos# + time# * (ball (j).vel# + time# * ball (j).acc#)
glVertex2fv (point#)
glEnd ()

'// Draw trajectories if space bar is down-
if ScanKeyDown (VK_SPACE) then

'// Path-
glBegin (GL_LINE_STRIP)
for i = 0 to ball (j).contactTime# * 5
time# = i*.2
point# = ball (j).pos# + time# * (ball (j).vel# + time# * ball (j).acc#)
glVertex2fv (point#)
next
glEnd ()

'// Contact point, slope and reflection vector-
glBegin (GL_LINES)
glColor3fv (ball (j).color# * .9)
glVertex2fv (ball (j).contact#)
glVertex2fv (ball (j).contact# + ball (j).slope#*5)
glEnd ()

glBegin (GL_LINES)
glColor3fv (ball (j).color# * .7)
glVertex2fv (ball (j).contact#)
glVertex2fv (ball (j).contact# + ball (j).reflect# * ball (j).reflectSpeed#*.2)
glEnd ()

endif

'// Update the ball's position
ball (j).timer# = ball (j).timer# + averageTick#*.001
if ball (j).timer# + averageTick#*.001 > ball (j).contactTime# then
ball (j).timer# = 0
time# = ball (j).contactTime#
ball (j).pos# = ball (j).pos# + time# * (ball (j).vel# + time# * ball (j).acc#)
ball (j).vel# = ball (j).reflect#* length (ball (j).vel# + ball (j).acc# * 2*ball (j).contactTime#)
&testBall = &ball (j)
gosub CalcEq
endif

ball (j).currentSpeed# = length (ball (j).vel# + ball (j).acc# * 2*ball (j).timer#)
next

DrawText ()
SwapBuffers ()
wend
' end of code