Game Development Reference

In-Depth Information

This is known as the
implicit Euler method
. The distinction between the implicit

and explicit methods is that with the implicit methods, the right side includes

terms that are not yet known. Implicit Euler is a first-order implicit method—it is

possible to create higher-order methods just as we did for explicit methods.

Whereas explicit methods add energy to the system as they drift away from

the actual function, implicit methods remove energy from the system. So while

implicit methods still do not handle oscillating or stiff equations perfectly, they

do not end up oscillating out of control. Instead, the system will damp down

much faster than expected. The solution converges, which is not ideal, but does

maintain stability.

We do have the problem that
x
(
t
+
h
) is unknown. There are three possible

ways to solve this. One is to try to solve for an analytic solution. However,

as before, this is not always possible, and often we do not have an equation for

x
(
t
)—it is a function we call in our simulator that returns a numeric result. That

result could be computed from any number of combinations of other equations.

So, for both reasons, it is usually not practical to compute an explicit solution. In

this case, we have two choices.

The first is to compute
x
(
t
+
h
) using an explicit method and then use the

result to compute our implicit function. This is known as a predictor-corrector

method, as we predict a solution using the explicit equation and then correct for

errors using the implicit solution. An example of this is using the result of an

explicit Euler step in a modified implicit Euler solution:

x
i
+1

=
x
i
+
h
v
i
,

v
i
+1

=
v
i
+
h
F
(
t
i
,
x
i
,
v
i
)
/m,

=
x
i
+
h

x
i
+1

2
(
v
i
+1
+
v
i
)
,

=
v
i
+
h

2
(
F
(
t
i
+1
,
x
i
+1
,
v
i
+1
)+
F
(
t
i
,
x
i
,
v
i
))
/m.

v
i
+1

An alternative method for implicit Euler is to treat it as a linear equation and

solve for it. We can do this for a force dependent on position as follows:

=
x
i
+
h
i
x
i
+1
,

x
x
+1

x
i
+Δ
x
i

=
x
i
+
h
i
F
(
x
i
+Δ
x
i
)
,

h
i
F
(
x
i
+Δ
x
i
)
,

Δ
x
i

=

≈

h
i
(
F
(
x
i
)+
J
(
x
i
)Δ
x
i
)
,

Δ
x
i

1

h
i
E

J
(
x
i
)
−
1

Δ
x
i

≈

−

F
(
x
i
)
,