RE: [Algorithms] XGDC conference

[Graham S. R. <gr...@se...>]

Here are a few of the references that I use:

"Computational Dynamics" by Ahmed Shabana is a decent book on, well,
computational rigid-body dynamics with full discussion on many many joint
constraints but not collision detection. It has a fair discussion of
numerical methods, but it does not analyze the error terms sufficiently.

"Computational Geometry: Algorithms and Applications" by M. de Berg et al.
This book has some decent discussions on the development of robust geometric
algorithms that handle degenerate cases well. Although I use the book as
background, I haven't really tested their algorithms.

One my favorite references on numerical methods is:

"Computational Fluid Mechanics and Heat Transfer" by Tannehill, Anderson,
and Pletcher. The order of the authors is random for each edition (there are
two so far). This will be one of my references for the papers I'll be
preparing.

I know this sounds like a strange reference, but it has one of the best
discussions I know of on the fundamental nature of numerical errors in
discrete integration schemes for differential equations. Chapters 2 and 3
are introductions to DE's (especially PDE's due to the nature of the
material of the topic of the book), and have nothing really to do with
fluids. Chapter 4 analyzes truncation error in a bit more detail, and
studies the stability issues of a laundry list of equations, using a variety
of different difference formulas.

There is some discussion in the book about how to deal with discontinuities.
In fluids, discontinuities are shock waves, contact surfaces (two regions of
fluid that move at different velocities at a common boundary in an inviscid
flow----such as the interface between water and air at the ocean). But some
of the rules apply elsewhere, including when you have cracks in a rigid or
nonrigid body, and when there are collisions in a dynamics problem. The
trick is detecting the discontinuities in an automated and robust manner.
Obviously, it is hard to detect collisions in a robust manner while keeping
time steps large enough for games. (Well, even without dealing with time
steps). In fluids, shock capture methods are pretty good at finding
discontinuities, but as with using penalty methods in dynamics there tends
to be a general mushiness/springiness with oscillations at the
discontinuity---second order accurate methods are required to come close to
tightly modeling the discontinuity. Shock fitting methods actually model the
geometry of the shock explicitly, and this is similar to restarting the
integration of a dynamics problem at the point of collision. Much nicer if
you can do it fast enough, harder to code. And you still have the problem of
intersecting the geometries. (In fluids, the geometry problem involves
moving the shock geometry until the flow properties on both sides satisfy
the "Rankine-Hugoniot" equations----required to satisfy the second law of
thermodynamics for physically consistent shocks. Enough of this tangent!)

Graham Rhodes

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of Jamie
> Fowlston
> Sent: Wednesday, August 16, 2000 4:55 AM
> To: gda...@li...
> Subject: Re: [Algorithms] XGDC conference
>
>
> Can you recommend any books on the topic? I avoided the numerical methods
> lectures while at university, and so far it's been the most
> useful thing I could
> have done there....
>
> Jamie
>
>
> "Graham S. Rhodes" wrote:
>
> > Wow,
> >
> > Lots of attendees here! I appreciate the feedback folks. Starting to get
> > excited. I'm planning to propose a talk on predicting and
> managing numerical
> > error for stable physics simulation for games. The XGDC topic list on
> > xgames3d.com has me listed with a title of "Advanced Physics
> Programming,"
> > but really the idea is to introduce formal techniques for analyzing the
> > errors introduced by numerical techniques, the way that the errors
> > propogate(sometimes leading to instability and blow-ups), and
> how to control
> > the errors by designing or selecting the right solution scheme.
> Sounds a bit
> > boring, but just about everything I've seen related to game physics
> > simulation has skipped over this, and it is essential to
> achieving the most
> > robust physics simulations.
> >
> > I'm also going to submit at least one proposal to GDC on a
> related matter.
> > By the time GDC rolls around hopefully I'll have some more interesting
> > examples, such as tricky collision detection examples.
> >
> > Graham Rhodes
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>