[ODE] Fixing the tunneling problem
Flavien Brebion
f.brebion at vrcontext.com
Mon Sep 1 09:37:01 2003
This is a multi-part message in MIME format.
------=_NextPart_000_0006_01C37095.69273100
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Hi,
In order to fix the "tunneling" problem previously mentionned,
i wanted to use a trick: with the previous frame's position and
velocity, cast a ray, then check if there's a collision "too
early" along this ray which would be missed after the next
tick.
Here's an algorithm idea:
- POS is the position of the object at the previous frame;
- VEL is the velocity of the object at the previous frame;
- T is the simulation timestep in seconds
- SIZE is the size of the object ( just an estimation, doesn't
have to be accurate)
- create ray at origin POS, with direction | VEL | and
length of R = | VEL | * T ( from now, R will be the travelled
distance for the next frame )
- if there's no collision, do ODE with timestep T as usual
- if there's a collision at a distance D:
- if D < SIZE or D > R - SIZE, do ODE with
timestep T as usual ( collisions at the beginning or the
end of the movement vector => will be handle with a
timestep of T anyway => use standard path )
- else, use a timestep of T' = T * (D - SIZE) / R, use ODE with
a timestep of T' ( this should place the object "near"
the collision point ), then recurse this algorithm with
the remaining timestep T'' = T - T'
Now the problems:
- will only detect a collision passing through the object's
center
- the ray uses the velocity at the previous frame to
determine the position at the next frame. BUT the velocity
at the next frame is updated BEFORE updating the
position at the next frame. In other words, the direction and
length of the ray is not correct for this algorithm to work..
any idea on how to improve it?
F. Brebion
PS.: I haven't implemented it yet, so i don't know if it
works or not.. I am assuming the ray cast passing
through the object's center only will be good enough to
stop tunneling bugs in 99, 99% of the cases..
------=_NextPart_000_0006_01C37095.69273100
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Diso-8859-1">
<META content=3D"MSHTML 6.00.2800.1106" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003>Hi,</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT> </DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>In=20
order to fix the "tunneling" problem previously =
mentionned,</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>i=20
wanted to use a trick: with the previous frame's position=20
and</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003>velocity, cast a ray, then check if there's a =
collision=20
"too</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>early"=20
along this ray which would be missed after the =
next</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003>tick.</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT> </DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>Here's=20
an algorithm idea:</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>- POS=20
is the position of the object at the previous frame;</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>- VEL=20
is the velocity of the object at the previous frame;</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>- T is=20
the simulation timestep in seconds</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>- SIZE=20
is the size of the object ( just an estimation, =
doesn't</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>have=20
to be accurate)</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT> </DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>-=20
create ray at origin POS, with direction | VEL | and</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>length=20
of R =3D | VEL | * T ( from now, R will be the =
travelled</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003>distance for the next frame =
)</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT> </DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>- if=20
there's no collision, do ODE with timestep T as =
usual</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT> </DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>- if=20
there's a collision at a distance D:</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003> - if D < SIZE or D =
> R -=20
SIZE, do ODE with</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003> timestep T as usual ( =
collisions at=20
the beginning or the</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003> end of the movement vector =
=3D>=20
will be handle with a</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003> timestep of T anyway =
=3D> use=20
standard path )</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003> - else, use a timestep of =
T' =3D T *=20
(D - SIZE) / R, use ODE with</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003> a timestep of T' ( this =
should place=20
the object "near"</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003> the collision point ), =
then recurse=20
this algorithm with</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003> the remaining timestep T'' =
=3D T -=20
T'</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT> </DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>Now=20
the problems:</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT> </DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>- will=20
only detect a collision passing through the object's</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003>center</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT> </DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT><FONT face=3DArial =
color=3D#0000ff=20
size=3D2><SPAN class=3D968421911-01092003>- the ray uses the velocity at =
the=20
previous frame to</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003>determine the position at the next frame. BUT =
the=20
velocity</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>at the=20
next frame is updated BEFORE updating the</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003>position at the next frame. In other words, =
the=20
direction and</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>length=20
of the ray is not correct for this algorithm to =
work..</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>any=20
idea on how to improve it?</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT> </DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>F.=20
Brebion</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT><FONT face=3DArial =
color=3D#0000ff=20
size=3D2><SPAN class=3D968421911-01092003></SPAN></FONT><FONT =
face=3DArial=20
color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003></SPAN></FONT><FONT=20
face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT> </DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>PS.: I=20
haven't implemented it yet, so i don't know if it</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>works=20
or not.. I am assuming the ray cast passing</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003>through the object's center only will be good =
enough=20
to</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN =
class=3D968421911-01092003>stop=20
tunneling bugs in 99, 99% of the cases..</SPAN></FONT></DIV>
<DIV><FONT face=3DArial color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT><FONT face=3DArial =
color=3D#0000ff=20
size=3D2><SPAN class=3D968421911-01092003></SPAN></FONT><FONT =
face=3DArial=20
color=3D#0000ff size=3D2><SPAN=20
class=3D968421911-01092003></SPAN></FONT> </DIV></BODY></HTML>
------=_NextPart_000_0006_01C37095.69273100--