Slashdot Mirror

Our approach produces better-looking movement than the low-end physics packages. We don't have the "boink problem", where everything bounces as if it were very light. Heavy objects look heavy. Our physics has "ease in" and "ease out" in collisions, as animators put it, derived directly from the real physics. When we first did this, back in the 200MHz era, it was slow for real time (a two-player fighter was barely possible) but now, game physics can get better.

Take a look at our videos. Few if any other physics systems can even do the spinning top correctly, let alone the hard cases shown.

Years later, a somewhat similar verifier for Modula III was developed at DEC Western Research Labs, but it died with DEC.

Microsoft Research is now developing something called Spec#, an extension to C# for formal verification. Much of the effort there focuses on object consistency, and, for the first time, somebody is finally handling the consistency issues associated with object call-out and callback. (This is badly needed in the Microsoft world, where the GUIs call round and round and back in, without proper theory to support that.)

Some comments I've written:

• From a physics engine:

  // The contact force component is aligned with the vector between
  // the two closest points. The frictional force is in a plane
  // perpendicular to that vector and through the midpoint of pnt0-pnt1,
  // The frictional force vector is opposite the velocity vector
  // component in the friction plane.

  // Witness point checks.
  // All witness points must be on their polyhedron's side of the
  // separating plane.

  Here the purpose of the comments is to explain the math.

• From the control code for a DARPA Grand Challenge vehicle. Here's some code I wasn't happy with, so that's clearly noted.

  // constructPath2 -- reactive obstacle avoidance and path planning
  // - the hard cases
  //
  // Called when we have to do some obstacle avoidance
  //
  // Path is an output only.
  //
  // First pass tries to find some path that will work within the turning limits.
  // If that fails, we try "brake then steer" mode - look for the longest path
  // in any direction, regardless of dynamics limits, and slam on the brakes
  // while turning. The actual steering command will be limited later.
  // ***MAKE SURE THAT CHECK IS MADE***
  //
  // ***NEEDS WORK***
  // ***SEARCHING OUTSIDE LIMITS WILL ALWAYS FAIL***
  //

• Finally, here's some Perl code, part of the code that runs Downside.

  #
  # extractsecurityclass -- extract class of a NASDAQ security
  #
  # Foreign and bank securities aren't filed with the SEC, so
  # we need to note this. There are also test and statistics items that
  # aren't real securities.
  #
  # Note that the test for "bank" is rather poor. NASDAQ used to
  # identify banks using a column in the table, but they no longer do so.
  #
  sub extractsecurityclass($)
  { my $vals = shift;
  ## Check for symbols that don't file with the SEC
  if (${$vals}{'test_issue'} ne 'N') { return('test'); } ## is test

  (We have to stop there; Slashdot's "lameness filter" rejects Perl code.)

All code should have well-written comments. As Wirth pointed out years ago, people who can't express themselves well in their native language are generally poor programmers.

There's no one key item that bottlenecks a rigid-body physics engine, and it's not a simple pipelining problem like graphics, so the main thing special-purpose hardware can provide there is parallelism. And plenty of double-precision floating point power. (In a single-precision system, you have to take great care to never try to do physics far from the origin.)

Collision detection is a minor CPU load if you do it right. If collision detection is using more than 10% of your physics time, you're doing it wrong. This may seem counterintutive, but the good algorithms are incredibly fast, even in complex environments. It's more of a data structure issue.

Deformation, i.e. finite element analysis, is more of an inner loop crunch problem than rigid body physics. Finite element analysis has been parallelized for decades in engineering applications, and the problem is well understood. It's localized; you can divide the problem up into cells. So I'll bet that's what they are focusing on.

You cannot, even in theory, predict how a human with arms and legs banging around will move in a complex crash. It's chaotic, in the formal mathematical sense of the world. That is, an arbitrarily small change in the initial conditions can create a large change in the outcome. In Falling Bodies, if you change the low order digit of a double precision number in the initial conditions for a fall down a staircase, the simulations will start to diverge after about a second, and the fall may end quite differently.

I had this discussion a few years ago with an Army officer who was trying to reduce accidents in parachute landings, and was considering using Falling Bodies. I talked him out of it.

Auto collisions can be simulated well because there's one big mass that dominates the simulation. So you get a deterministic result within some error limits. Multibody systems with joints and links are quite different.

Realistically, you can probably do a sound simulation which predicts how a passenger will bounce around from the beginning of the collision to the first passenger interior collision with the vehicle. Beyond that point, forget it.

Then Microsoft bought Softimage, and made them come out with an NT version. The first serious OpenGL graphics cards (DirectX was stil in the future) came from vendors like Fujitsu and Dynamic Pictures. They didn't work very well. Installation required direct cooperation with the board developers. But they did have the 4x4 matrix multiplier for geometric transforms and a hardware Z buffer, just like an SGI machine.

That's when the studios started gettting NT-based animation systems. They weren't standard desktop PCs at first, though. Intergraph sold "high end NT workstations", and it was worth it simply because they could make the graphics board play nice with the motherboard. Softimage on NT on the DEC Alpha had a following.

One real issue for a few years was that it was seen as "unprofessional" to be using a PC for animation. At one point I had a Pentium Pro in a black rackmount case, and industry people asked me where they could get one like that, so their shop would look "professional".

Then came mainstream motherboards with AGP slots, and finally, the graphics board had enough memory bandwidth to work right. Then serious graphics boards went mainstream, and it was all downhill for Silicon Graphics after that.

There are two main approaches to this - the "animation splicing" systems, where canned bits of motion are spliced together by a program, and the "behavior" systems, where control programs are trying to optimize some goal. The first major appearance of a good "splicing" system was the baby 'zillas in Godzilla 2000. That's what most feature films are using today.

Kinematic motion generation has been around for years, and that's what you see in games. It doesn't look real, but it works well enough for gameplay. The physics isn't realistic. That's why, from across the room, EA Football looks different from NFL football. Those jerky motions really pop out at you, especially when they're alternated with nice motion-captured moves.

Endorphin isn't as automated as it looks; much manual tweaking of the motion is necessary. Motion Factory has more automation, but it's kinematic. Automatic physically-realistic animation is hard, because you have to solve the robotic control problem. The animation community may yet do this. But they're not there yet.

(I've done some work on this.)

The classical problem with C was the failure to distinguish between a pointer and an array. (In the late 1970s, this was considered a feature. Now we know it's a bug.) This led to passing arrays around without size information, and to pointer arithmetic. C++ tries to paper over those issues with the STL, and it almost works. Almost.

"Smart pointers" don't work all that well in C++. The "auto_ptr" mess is instructive. After three published revisions, it still doesn't work well. And that's the simplest case. Reference-counted pointers have worse problems. Making an efficient, airtight smart pointer does not seem to be possible within C++. It needs some language support. Perl's strong and weak references (not Java's) are a good model here. With optimization and language support, the overhead of reference counting can be brought way down. But you can't do that at the template level.

(Incidentally, retrofitting garbage collection to C++ is probably a mistake. It's been tried. The interaction with destructor semantics is too ugly. Calling destructors at random times is not a good thing. And it leads to horrors like "re-animation" in Microsoft Managed C++).

The other huge area of trouble in C++ is threading. The language ignores the whole issue. Locking is considered a library issue. The compiler gives you no help in determining whether a program is free of race conditions.

Because C++ is unsafe, the usual advice is to be "very very careful". This has led to much talk of "patterns", rituals and taboos which supposedly keep bad things from happening. This helps a little, but it's more of a cult than a tool set.

So what we really have is C, with C++ cruft on top of that, then STL cruft on top of that, then "patterns" cruft on top of that. Not good.

And what is the committee doing? Adding more cruft, in the form of "generic programming". There's a way to abuse the template system into pretending to be a recursive term-rewriting engine which can be used to perform arbitrary computatations at compile time. This is being pursued as a foundation for a new generation of incomprehensible template libraries. (If you've ever had to debug someone else's template, you know how hard it is. Imagine something far worse. If you want to go beyond imagining it, go over to Boost, download something, and try to fix it. Suffer.)

I've written a bit on Strict C++. It's not impossible to fix this. It can almost be made backwards compatible. I don't claim to have all the answers. But at least I'm trying to improve safety and reliability. This is far more important than adding cool features.

When I was in high school, we didn't have computers. So I build built one out of surplus telephone relays.

Raibert did some great work in the Leg Lab's early days. Raibert's big insight was that balance is more important than gait, and he did work with one-legged machines with springy actuators to force the issue. In his day, the Leg Lab had one, two, and four-legged running machines. But he left MIT to do a startup, which seems to have ended his dynamics work. BDI does mostly kinematic models.

The next professor to head the Leg Lab was Gill Pratt, who was more of an actuator guy. He didn't accomplish too much, and is now at some lesser school. Under Pratt, the Leg Lab backed down from running machines to walking machines.

There was somebody after Pratt, but apparently the Leg Lab is now defunct. It's sad. They made so much progress under Raibert.

It's possible to go beyond walking and running on the flat. Legs are really for traction control. All the MIT work assumes that the "feet" don't slip. That doesn't work on real hills or slippery surfaces.

There's two phases to dealing with slip. First, you need to limit joint torques to below where the feet start to slip. Once you do this, you can climb some hills. (Video, 8MB .mov file). That work is ten years old, and still, nobody else seems to be handling leg slip at all.

The next step is to use the three joints of a leg to adjust the vector at which the normal force is applied to keep the ground contact inside the friction cone. Then you can climb more serious hills. Once you get this figured out, much of how humans move when dealing with terrain becomes clear. Leaning forward and bending the knees more when going uphill is all about slip control. Think about it.

Working on this diverted me off into physics engines, because everything that was available ten years ago sucked. So I did a physics engine that worked, which turned into a business. There are still very few physics engines good enough for legged locomotion work. Most physics engines, especially the Baraff-type impulse/constraint ones, don't do friction well. Since legged locomotion is all about managing foot-ground friction, you need a simulator that gets friction right. (Hint: if a simulator can't do a driving game without special-casing the wheel/ground contact, it won't work for legged work.)

All this is patented, of course.

Raibert did some great work in the Leg Lab's early days. Raibert's big insight was that balance is more important than gait, and he did work with one-legged machines with springy actuators to force the issue. In his day, the Leg Lab had one, two, and four-legged running machines. But he left MIT to do a startup, which seems to have ended his dynamics work. BDI does mostly kinematic models.

The next professor to head the Leg Lab was Gill Pratt, who was more of an actuator guy. He didn't accomplish too much, and is now at some lesser school. Under Pratt, the Leg Lab backed down from running machines to walking machines.

There was somebody after Pratt, but apparently the Leg Lab is now defunct. It's sad. They made so much progress under Raibert.

It's possible to go beyond walking and running on the flat. Legs are really for traction control. All the MIT work assumes that the "feet" don't slip. That doesn't work on real hills or slippery surfaces.

There's two phases to dealing with slip. First, you need to limit joint torques to below where the feet start to slip. Once you do this, you can climb some hills. (Video, 8MB .mov file). That work is ten years old, and still, nobody else seems to be handling leg slip at all.

The next step is to use the three joints of a leg to adjust the vector at which the normal force is applied to keep the ground contact inside the friction cone. Then you can climb more serious hills. Once you get this figured out, much of how humans move when dealing with terrain becomes clear. Leaning forward and bending the knees more when going uphill is all about slip control. Think about it.

Working on this diverted me off into physics engines, because everything that was available ten years ago sucked. So I did a physics engine that worked, which turned into a business. There are still very few physics engines good enough for legged locomotion work. Most physics engines, especially the Baraff-type impulse/constraint ones, don't do friction well. Since legged locomotion is all about managing foot-ground friction, you need a simulator that gets friction right. (Hint: if a simulator can't do a driving game without special-casing the wheel/ground contact, it won't work for legged work.)

All this is patented, of course.

Raibert did some great work in the Leg Lab's early days. Raibert's big insight was that balance is more important than gait, and he did work with one-legged machines with springy actuators to force the issue. In his day, the Leg Lab had one, two, and four-legged running machines. But he left MIT to do a startup, which seems to have ended his dynamics work. BDI does mostly kinematic models.

The next professor to head the Leg Lab was Gill Pratt, who was more of an actuator guy. He didn't accomplish too much, and is now at some lesser school. Under Pratt, the Leg Lab backed down from running machines to walking machines.

There was somebody after Pratt, but apparently the Leg Lab is now defunct. It's sad. They made so much progress under Raibert.

It's possible to go beyond walking and running on the flat. Legs are really for traction control. All the MIT work assumes that the "feet" don't slip. That doesn't work on real hills or slippery surfaces.

There's two phases to dealing with slip. First, you need to limit joint torques to below where the feet start to slip. Once you do this, you can climb some hills. (Video, 8MB .mov file). That work is ten years old, and still, nobody else seems to be handling leg slip at all.

The next step is to use the three joints of a leg to adjust the vector at which the normal force is applied to keep the ground contact inside the friction cone. Then you can climb more serious hills. Once you get this figured out, much of how humans move when dealing with terrain becomes clear. Leaning forward and bending the knees more when going uphill is all about slip control. Think about it.

Working on this diverted me off into physics engines, because everything that was available ten years ago sucked. So I did a physics engine that worked, which turned into a business. There are still very few physics engines good enough for legged locomotion work. Most physics engines, especially the Baraff-type impulse/constraint ones, don't do friction well. Since legged locomotion is all about managing foot-ground friction, you need a simulator that gets friction right. (Hint: if a simulator can't do a driving game without special-casing the wheel/ground contact, it won't work for legged work.)

All this is patented, of course.

Raibert did some great work in the Leg Lab's early days. Raibert's big insight was that balance is more important than gait, and he did work with one-legged machines with springy actuators to force the issue. In his day, the Leg Lab had one, two, and four-legged running machines. But he left MIT to do a startup, which seems to have ended his dynamics work. BDI does mostly kinematic models.

The next professor to head the Leg Lab was Gill Pratt, who was more of an actuator guy. He didn't accomplish too much, and is now at some lesser school. Under Pratt, the Leg Lab backed down from running machines to walking machines.

There was somebody after Pratt, but apparently the Leg Lab is now defunct. It's sad. They made so much progress under Raibert.

It's possible to go beyond walking and running on the flat. Legs are really for traction control. All the MIT work assumes that the "feet" don't slip. That doesn't work on real hills or slippery surfaces.

There's two phases to dealing with slip. First, you need to limit joint torques to below where the feet start to slip. Once you do this, you can climb some hills. (Video, 8MB .mov file). That work is ten years old, and still, nobody else seems to be handling leg slip at all.

The next step is to use the three joints of a leg to adjust the vector at which the normal force is applied to keep the ground contact inside the friction cone. Then you can climb more serious hills. Once you get this figured out, much of how humans move when dealing with terrain becomes clear. Leaning forward and bending the knees more when going uphill is all about slip control. Think about it.

Working on this diverted me off into physics engines, because everything that was available ten years ago sucked. So I did a physics engine that worked, which turned into a business. There are still very few physics engines good enough for legged locomotion work. Most physics engines, especially the Baraff-type impulse/constraint ones, don't do friction well. Since legged locomotion is all about managing foot-ground friction, you need a simulator that gets friction right. (Hint: if a simulator can't do a driving game without special-casing the wheel/ground contact, it won't work for legged work.)

All this is patented, of course.

Basic problem with building a game physics engine: if you do all the obvious stuff, it sort of works. If you're competent, you should be to that point in a few months. Getting from "sort of works" to "works" is about 5x to 10x as hard as the first step. There are really only a few game physics engines out there that really work.

You'll find out more about stiff systems of nonlinear differential equations than you ever wanted to know, if you don't give up first.

It's interesting that the book talks about the problems that occur when you take into account the propagation delay of gravity. Game physics engines, having rather large time steps, have some similar problems. I'll have to read this and see if I get any new insights applicable to game engines.

There's a related book, an ACM prizewinner, on the N-body problem. There's a clever numerical solution to the N-body problem that works for large N (millions), so you can simulate galaxies forming and such. The basic idea is that you can treat a group of bodies as a single body if they're near to each other and far away from the body being affected. This can be quantified and safe limits computed for grouping. It's thus a numerical solution with a proveable upper bound on the error, which bound can be made arbitrarily small at the cost of more computation. This is effectively as good as a closed-form solution, although some older mathematicians deride it as inelegant.

Brooks did some great insect-level AI. It's purely reactive, with no world model. That was good work, and a reasonable reaction to the logic-based planning crowd then running MIT AI. But then Brooks started going around saying that the reactive model was far more powerful, and started making human-level AI noises. From this came Cog.

When Brooks came by Stanford to talk about his plans for Cog, I asked him "Why don't you go for mouse-level AI", something that didn't seem totally out of reach. He said "Because I don't want to go down in history as the man who created the world's greatest robot mouse". As one of the grad students on the Cog project said, "It just sits there. That's what it does. That's all it does". And, years later, it still doesn't do very much.

The model-free approach is just too dumb. With no world model, you can't get beyond insect-level AI. That approach works mostly for creatures in environments where inertia doesn't matter much. For insects, banging a feeler into something is fine. For large animals, you get bruises or worse. As creatures get bigger, faster, and stronger, they need models with some predictive power, so they can avoid mistakes before damaging themselves. I tell people in academia that you need to be "less formal than Latoumbe (who formerly headed Stanford's robotics operation) and more formal than Brooks". The game development community has absorbed this lesson, but it's only starting to get through to the robotics community.

Raibert's work on legged locomotion was very impressive. I'm very familiar with that work; I've done some improvements on it. Raibert had one great insight - balance is more important than gait. People have been studying locomotion for a century, and almost all the studies center on gait. Raibert realized that balance was more important, and built a one-legged hopper to force the issue.

But, in fact, the way Raibert does locomotion is very simple. There are two controllers, both simple hand-tuned PID loops, and a state machine that swiches between them. This can handle simple locomotion on the flat, and some preprogrammed moves like flips, but it doesn't generalize. I'd expected the adaptive control people to pick up from where Raibert left off, but so far, nobody has really done that.

My insight there was that slip control is more important than balance. On the flat, traction control isn't a big deal, but on hills or rough terrain, traction control dominates balance control. That's what legs are really for. If you add automatic traction control to Raibert's approach, legged running on hills becomes possible. Otherwise, you slip out climbing hills.

Raibert himself left MIT and did a startup company, Boston Dynamics. But they ended up selling products to DoD which are game-like kinematic simulations. They don't seem to stress dynamics work any more.

The MIT Leg Lab was taken over by Gill Pratt, who was more of an actuator and controls guy. He didn't accomplish much. The next head of the Leg Lab was some guy who was into prosthetics. The Leg Lab now seems to be defunct. Their web site hasn't been updated since 1999.

The problem is that it's very, very easy to poison the prosecution of the beneficiary of spam. See Basics on JoeJobs Who's to say whether something like this came from you or not? :

Wild, h0t animation tool available!
See \/ar1ous polygons in full, sensual contact
FREE DEMO
CLICK HERE!!
sponge arrest carriboo spade
kumquat afredo distribution

How do you propose to demonstrate that you didn't pay someone to send it? Turn over all of your financial records to someone to show no payments to an unknown spammer in the Ukrane that runs a server or ten in China?

Trying to sue credit card companies and banks is pretty unreasonable as well. There's no easy way to verify every action that a merchant takes. Even if you suceeded in getting some kind of law to that effect passed, the cost would get handed right back to the consumers. Theoretically suing spammers could work because they are reasonably small operators with a small number of clients. When Visa has hundreds of millions of users, they can abuse them pretty freely.

If you have to handle the hard cases, like multiple simultaneous sliding contacts, the Baraff-type LCP solutions don't really work too well, or at least they didn't a few years ago. I realize there's been some progress. I prefer spring/damper simulators, because you can handle frictional contacts right and you don't have the zero-time bounces (the "boink problem") of impulse/constraint systems. The CPU load is higher, but that's less of a problem than it used to be.

A good test of a physics system is the spinning top. That's easy to set up. The base should roll around a little (it has a nonzero diameter), the top should precess, it should recover from small disturbing impacts, and over time, the speed of the top should slow. Just like a real top. If it doesn't behave like that, something is broken.

I'm the inventor of "ragdoll physics". More of my physics videos. Those are from work done in 1996-1998. (The videos are overcompressed; everybody had less bandwidth back then.)

The difference between "sort of works" and "works as well as that" is non-trivial. That's why I collect royalties on the technology.

I'm the inventor of "ragdoll physics". More of my physics videos. Those are from work done in 1996-1998. (The videos are overcompressed; everybody had less bandwidth back then.)

The difference between "sort of works" and "works as well as that" is non-trivial. That's why I collect royalties on the technology.

Good collision libraries are fun. I've written one, as part of Falling Bodies. I think I was the first, back in 1996-1997, to use axis-oriented bounding boxes with GJK, which is what SOLID, and everybody else, uses now.

Lin and Canny are the ones who really cracked this problem. Before Lin and Canny, algorithms for collisions in a space with N objects with M faces each were O(N^2) * O(M^2). They got that down to slightly worse than O(Nm), where Nm is the number of moving objects. Very clever.

I-Collide was the first generally available package for this. The original version was in LISP, which was translated to C, retaining much of the LISP style. They used axis-oriented bounding boxes with a linear programming package. This had some problems with numerical error, and the linear programming package was rather bulky. But it demonstrated, back in 1996, what was possible. Then everybody (well, the half dozen or so people into this stuff) went to work and built better systems.

Actually, collision detection is a pain to code, but well understood today. Collision response, the actual physics, is much harder.

The end result of all this is that games can now have really big worlds with working collision detection.

Perl has good reference-counting semantics, with strong and weak pointers. In structures with back-pointers, the back-pointers should be weak, which avoids cycles.

I've made some proposasl on this. But adding strictness to C++ isn't popular, which means another decade of buffer overflow exploits.

C++ itself is undergoing a revision. But the plans for it aren't that good.

The big problem with the C++ committee is that most of the members don't want to admit the language has major problems. Neither does Strostrup, who has written that only minor corrections are needed. If that was really true, we wouldn't need all those variants on C++ (Java, D, C#, Objective-C, Managed C++, etc.)

The committee is dominated by people who like doing cool things with templates. Most of the attention is focused on new features for extending the language via templates. It's possible to coerce the C++ template system into running programs at compile time (see Blitz). Painfully. LISP went down this dead end, where the language was taken over by people who wanted to extend the language with cool macros. (See the MIT Loop Macro.) We all know what happened to LISP.

What isn't happening is any serious attempt to make C++ a safer language. C++ is the the only major language that provides abstraction without memory safety. That's why it causes so much trouble. C++ objects must be handled very carefully, or they break the memory model. This usually results in bad pointers or buffer overflows. Java, etc. are protected against that. This is the basic reason that writing C++ is hard.

It's not fundamentally necessary to give up performance for memory safety. I've written a note on "strict mode" for C++, an attempt to deal with the problem. I'm proposing reference counts with compile-time optimization, rather than garbage collection. The model is close to that of Perl's runtime, which handles this well.

Garbage collection doesn't really fit well to a language with destructors, because the destructors are called at more or less random times. Microsoft's Managed C++ does that, and the semantics of destructors are painful. With reference counts, destructor behavior is repeatable and predictable, so you can allocate resources (open files, windows) in constructors and have things work. The main problem with reference counts is overhead, but with compiler optimization support and a way to take a safe non-reference-counted pointer from a reference counted object, you can get the overhead way down and reference count updates out of almost all inner loops.

C++ itself isn't that bad. The language could be fixed. But I don't see it happening. Microsoft has gone off in a different direction with C#. SGI, HP, DEC, Bell Labs, SCO, and Sun are defunct or in no position to drive standards any more.

What C++ needs is some hardass in a position to slam a fist on the table and say "Fix it so our software doesn't crash all the time". It doesn't have one.

The game development community used to take algorithms from other fields. Now they've gone beyond academia in graphics, physics simulation, and AI. Games are a tough, competitive market, and the stuff has to work, or you get trashed in reviews. That makes for real progress.

The basic idea is that everything is reference counted and subscript checked, but by doing some static analysis and type enforcement, most of the overhead for that is eliminated at compile time.

About 95% of subscript checks can be optimized out without too much effort. An optimizing compiler that can hoist expressions out of loops and strength-reduce them can move most subscript checks out of inner loops. Reference counts require more language support, but they, too, can be optimized.

As for pointer arithmetic, the solution is to use iterators, which are checkable, instead of pointers, which are not. Then optimize out the checks, as with subscript checks.

I proposed that there be a way to designate C++ code as "strict", turning on the enforcement. Privileged programs should be 100% strict; others need not be.

This is unlikely to happen, but it is technically possible.

On the other hand, most of the proposals for C++ "enhancements" are bad. Most of the "enhancement" proposals are from people who want to program at compile time by abusing the template mechanism. Then the end user is stuck debugging some gonzo template written by somebody who thinks they're l33t. This is not progress. We went through this with LISP, and it's one of the reasons LISP is a dead language.

But thinking that C++ is OK is a big mistake. The fundamental problem with C++ is that it has abstraction without safety. C has neither abstraction nor safety, so you can get in trouble easily but the problem is usually visible in the source code. Java has both abstraction and safety, but pays a performance penalty for it. C# offers the illusion of safety, with "managed objects", but doesn't really provide it, which is so Microsoft. Strostrup doesn't even mention "safety" as an issue. This is more of that "we're so l33t, we don't need a safe language" attitude that produces a few new buffer overrun vulnerabilties every week.

I'm being hard on Strostrup here. But we have far too many preventable bugs in code today. It doesn't have to be this way.

Two years ago, I proposed strict mode for C++. The basic idea is modelled on Perl's "strict mode"; you have to turn it on, but once it's on, the rules are tighter and there are some guarantees about the code not having certain common problems. I don't necessarily endorse that syntax, and I've had some later ideas on how to do this better. But increased safety is the way to go. As a retrofit, I admit it's tough.

There's way too much unnecessary low-level detail. Simulating subatomic particles adds many orders of magnitude to the compute load, with little payoff. There may be more levels of detail below subatomic particles, such as superstrings. There may be higher dimensions that collapsed out. These features mattered during the Big Bang, but as the universe cooled, they became mostly dead code. But they still seem to be there.

It's possible that the universe simulation cheats, and there's level-of-detail processing. Maybe full simulation detail isn't being computed when nobody is looking. The observer paradox points in that direction. But if the simulation cheats on a large scale, enough to knock the load down by many orders of magnitude, there will be artifacts and out-of-sync conditions.

Incidentally, the best book to read on this is Simulacron Three, which is the 1964 book behind "The Thirteenth Floor". The book is better. The premise of the book is that a simulated city has been constructed so that new advertising campaigns can be tested. The simulation isn't full-detail, and this creates problems.

Would somebody please put this in Linux?

I stick to working in simulation, but I do have some results in that area. See my papers. I've built wheeled robots, and worked with manipulators, but haven't used a physical legged robot yet. I'm hoping that the "Dr Robot" toy mentioned previously will be worth buying and reprogramming.

There are no truly dynamic non-planar walkers right now, and just adding sensors doesn't fix the problem; it's still extremely difficult.

The Honda walker is truly dynamic; it does get its CG outside its support polygon. Troody, at the MIT Leg Lab, is a non-planar dynamic walker, but may no longer be working. Dynamic walkers are few, but they exist.

The nice thing about a quadruped is that the walk doesn't necessarily need to be feedback based. (Oscillator designs are nice but they have yet to yield a practical 3d walker).

It's got to be feedback based to be any good. An open-loop locomotion system is roughly comparable to wheels.

I agree about oscillator designs. I spent some time playing with Randall Beer's oscillator-based insect simulation. That's cute, but a dead end.

Raibert's stuff, most of the later leg lab stuff, and Jessica Hodgins' animations, are basically state machines keying dumb PD controllers. That approach works for simple situations, but takes way too much manual tuning. If you think about it a bit, PD controllers are equivalent to spring/damper systems. So that approach is equivalent to setting the spring constant, damping constant, and zero point of the actuator to canned values. Different sets of canned values are keyed by the state machine. Seen in that light, those controllers are much simpler.

Real progress will require trajectory control. But that's more than I want to get into right now.

The main problem is still actuator strength (as postulated by the MIT leg lab), not really balance or sensors.

Gil Pratt (is he still at MIT?) was saying that for a while. He's into his "series elastic actuators", screw drives coupled to a stiff spring, which can be made to act like a less-stiff spring by feedback. This gives you the effect of a spring with an adjustable spring constant and zero point, which is what you want. It's inefficient, though; you don't recover much of the energy of a stride. (Muscles act like springs, storing energy from one landing to the next takeoff. Humans get about 60% of the energy back at a run; for horses, it's about 80%).

Linear motors looked promising for a while, as an alternative to pneumatics or hydraulics, but the best ones came from Aura, which tanked in a financial scandal. A friend of mine, who built a self-balancing unicycle, suggests firing a fuel charge in a cylinder as a linear actuator. Sandia actually does this for a new line of mobile land mines.

Here's my simulation of someone falling down a circular staircase. [.avi, 1.5MB]. Note that there's less "boink" than with impulse/constraint simulators; the bounces take several frames, rather than being instantaneous. That's because Falling Bodies is a spring/damper system, which produces better results. Takes more cycles, though.

Now everybody does falling downstairs as a demo for physics engines. I've created a cliche, like the old "teapot" graphics test.

More videos.

(Most of these videos are encoded with the Intel Indeo codec, which Intel discontinued, but you can still get it from Ligos. I should convert that material to another codec. What would you suggest that will work five years from now?)

Here's my simulation of someone falling down a circular staircase. [.avi, 1.5MB]. Note that there's less "boink" than with impulse/constraint simulators; the bounces take several frames, rather than being instantaneous. That's because Falling Bodies is a spring/damper system, which produces better results. Takes more cycles, though.

Now everybody does falling downstairs as a demo for physics engines. I've created a cliche, like the old "teapot" graphics test.

More videos.

(Most of these videos are encoded with the Intel Indeo codec, which Intel discontinued, but you can still get it from Ligos. I should convert that material to another codec. What would you suggest that will work five years from now?)

Another similar tool is the actual real stick figures which are about a foot high and feed into a modelling program. More of a frame by frame too, these have been used for a bunch of 3d fighting games.
Also if the only goal is to make people return to earth, there is a slashdotter's company Animats.

• The algorithm used requires that the length of the password be within configurable length limits, and that the password not have triplet statistics similar to those associated with words in the English language. This is an inversion of a technique used to find spelling errors without a full dictionary. No word in the UNIX spelling dictionary will pass this algorithm.

  Users should be advised to pick a password composed of random letters and numbers. Eight randomly chosen letters will pass the algorithm over 95% of the time. A word prefaced by a digit will not pass the algorithm, although a word with a digit in the middle usually will. Two words run together will often pass.

• A big advantage of object-oriented programming for numerical work is that there's a place to put all the bookkeeping information you need to carry along.
• Collection classes are a big help. Understand and use valarray. Write your code so that the size of the array is obtained from the array object, rather than passed as a separate parameter.
• C++ multidimensional array support is still inferior to that in Fortran.
• You can't create local temporary arrays of unknown size on the stack in C or C++, which can result in unnecessary memory allocation calls just to get workspace.
• Numerical Recipes in C is a transliteration of Numerical Recipes in Fortran, and it shows. They even use a hokey memory allocation scheme so they can count arrays from 1.
• Microsoft is sloppy about testing their compilers for correct numerical results in the "all optimizations on" mode. I know people at a large engineering company who run a sizable test suite on each new Microsoft compiler service pack and release, and don't use it until Microsoft fixes all the bugs. I can't speak for GCC.
• Use "inline" on small numeric functions.

Take a look at these QuickTime movies. (Note that Windows Media Player won't play them, because they were authored on a Mac. Windows Media Player grabs the .mov extension, but doesn't have a full set of QuickTime codecs. You'll need QuickTime.) Did those in 1994.

We'll see that kind of technology in games soon. At last, we have the MIPS.

As someone else pointed out, there's a straightforward way to approach game physics, based on what you learn in a first-year dynamics course, and it won't work. Free flight is easy. Contacts and collisions are hard.

Detecting contacts between objects is complicated, but well-understood. There are several free collision-detection engines available, and many research papers. The time bounds are quite good; only slightly worse than O(N) with the better algorithms. Writing a collision detection system is a big job, but the theory is tractible.

Taking appropriate action when you detect a contact is the hard part of the problem. Bouncing balls are easy. Multiple irregular objects with multiple contacts, slipping and sliding, are hard. Most current games simplify their collision geometry down to cubes or spheres and botch the hard cases ("But my sword went right through him and he didn't even notice!") The latest generation of games is just starting to get contact right. In another year, correct contact handling will be a "must-have" for commercial games.

If you simulate contacts between objects with a spring and a damper, you run into numerical stiffness during integration. Soft objects at slow speeds will bounce fine. In a hard collision, the forces become huge for short periods. The simple integration algorithms will result in huge errors, and the objects will go flying off into space.

If you simulate contacts between objects as impulses (an impulse is an infinite force applied for zero time, but with a finite energy transfer), two objects bouncing off each other will work great. More than one contact per object doesn't work too well. Resting contact doesn't work; objects may fall through each other. And everything bounces like it's a pool ball, because all collisions take zero time.

If you try to do everything with constraints, resting contact works. But combinations of sliding and resting contact result in wierd corner cases that are hard to get right. Trying to solve contact, rather than simulate it, leads to static indeterminacy. (Think of a table with four legs, slightly different in length. How the table behaves is very sensitive to small changes in leg length. Numerical solutions of multipoint contact problems become similarly sensitive). This is the approach Baraff preaches at SIGGRAPH, but few others have been able to implement it.

After a few years on the problem, I developed Falling Bodies, which successfully solves this problem well enough to simulate a human figure falling down a circular staircase. It can be done. I hammered through the spring-damper problem by using unusual and robust integration techniques. This is computationally expensive, but sound.

If you're developing a commercial game, and need working physics, go with the Havok engine. They have a rigid body engine, a soft-body system, and a specialized vehicle simulation engine. (Yes, vehicle physics in games typically has fake components. In most racing games, the tires are impossibly good and the vehicle CG is impossibly low. But you need a real physics engine to fake it properly.) It's not cheap, but you're not going to solve this problem in a few months. Major developers have blown years on this problem and failed. Trespasser, from Dreamworks, went down the drain that way.

Until domain names came along, few people bothered with supplemental registry trademarks, but because ICANN's rules respect even supplemental registry trademarks, it's worth doing.

I hold Downside(tm), downside.com, Animats(tm), and animats.com. Downside was accepted with no problems and is on the principal register, but Animats was initially rejected as a generic term for artificial animals, and I accepted a supplemental registration on that one.

I'd like to see Cyclone's kind of safety, but if you're going to require garbage collection and forbid pointer arithmetic, you may as well use Java.

I've proposed "Strict Mode" for C++, a compatible retrofit to C++ that uses reference counts like Perl, but with some optimizations to get the overhead down.

A basic decision is whether to have garbage collection. If you have garbage collection, C++ destructors don't fit well. (Java finalizers, called late, during garbage collection, can't be used for things like closing files and windows. Microsoft's C' has destructors, but the semantics are confusing and ugly, and we don't have much mileage yet on how well that will work.)

Reference counts work reasonably well. There's a problem with not releasing circular structures, but that doesn't keep Perl from being useful. Perl now has "weak" pointers (they won't keep something around, and turn to null when their target goes away), and if you use weak pointers for back pointers, most of the circularity problem goes away. True rings of peer objects are rare, and they're the main case where weak pointers won't solve the problem.

If you don't have garbage collection or reference counts, programs obsess on who owns what. A basic problem of C and C++ is that it's essential to track who owns which objects and when they're supposed to be released, yet the language offers no help whatsoever in doing so. This is the fundamental cause of most crashes in C and C++ programs. Almost every core dump, "bus error", or "general protection fault" comes from that problem. So it's worth fixing.

It's the right time to address this. We're in a period of consolidation, now that the dot-com boom has collapsed. Our task as programmers over the next few years is to make all the stuff that sort of works now work 100%.

With manual allocation or reference counts, you can have destructors that are called at some well-defined time. With garbage collection, you have Java-like finalizers that are called at some random time, maybe even from a separate thread. So, while you can use destructors to release various resources such as files and windows, finalizers can only be used to release memory.

Finalizers thus have very different semantics from destructors. And finalizers don't fit well with C++, although Microsoft, with their new "Managed Objects" system, is trying. ("Managed Objects for C++" have very wierd semantics, involving "resurrection" and multiple finalization. That's an indication of where finalization in C++ leads.)

Still, there's a growing consensus that memory management has to be automated. C and C++ program designs obsess on memory allocation, and usually get it wrong. Almost every new language announced in the last ten years has automated memory management. So there's a clear trend.

My own proposal in this area is Strict mode for C++. The idea is to retrofit C++ with safe reference-counted objects, and offer a mode that limits you to the safe subset. (The model here is "strict mode" in Perl.)

My old Obvious Password Detector requires that passwords have trigraph statistics not found in the English language. This can be validated with a tiny piece of code and a modest-sized bitmap. The bitmap of trigraphs was built from the UNIX spelling dictionary, so 100% of words in that dictionary will be rejected. But only about 20% of random letter sequences are rejected, so if you choose some junk character sequence, that's usually OK. There's thus no need for a dictionary or any complex code that might contain a leak in the Obvious Password Detector itself.

If this had been used from the mid-80s onward, brute-force password cracking would have been stopped before it started. And it's been free, open-source since 1984.

My obvious password detector from 1984 was one of the first attempts to deal with this problem. This tiny piece of code enforces a rule that passwords must have some 3-character sequences that don't occur in English words. With a small bitmapped table, this code knocks out every word in the UNIX dictionary, but only about 10% of randomly chosen strings. This is very old code, but it still works. Enjoy.

Gil Pratt took over the Leg Lab, and focused more on actuator design. Raibert's machines worked, but needed hydraulic, electrical, and pneumatic umbilicals. Better machine design has produced more compact robots.

The idea of springy joints has been around for a while. It's common to model muscles as springs and dampers for which the spring constant, neutral point, and damping factor are adjustable. It's well-known that in mammal running, most of the energy of each stride is stored as spring energy in muscles. (As I recall, about 80% of the energy is recycled for the next stride, so this is a big win.) There's been work at Stanford on flexible manipulators, although that's more related to arms. McGill has a small, high-efficiency hopping machine.

Unless you use pneumatic actuators, off the shelf components aren't well-matched for this approach motion control. That doesn't mean it can't be done, but you spend a lot of time on component development. That's what the Leg Lab has been focusing on under Pratt, and that's why the little dinosaur model was tough to build.

Rod Brooks from MIT also tried a robotic startup, IS Robotics, which produced a $100K robotic insect. Didn't sell. It's really hard to sell mobile robots; I've known several people with failed startups.

I work on this sort of thing for games and animation.

The first big insight on the problem was when Raibert figured out that balance is more important than gait. Locomotion researchers had been obsessing on gait all the way back to Muybridge, and never understood gaits beyond the walk. That's why Raibert did the one-legged hopper, which forced him to focus on balance. This provided the insight that cracked running. The basic concept is that in stance, the goal is to level the body, and in flight, the goal is to land with the foot at the "zero point" landing point which will maintain the current speed and direction. Displacing the landing point slightly from the zero point results in a turn or speed change, and that's how you steer. Very neat.

My big insight on this is that traction control is more important than balance. I figured out (and, of course, patented) how to do anti-slip control for legs. This is necessary to run on hills. One interesting result was that it finally became clear why legs have three joints, considering that two are sufficient to place the foot anywhere. The third (ankle on human, hock on the quadrupeds) joint gives the ability to control the direction of the contact force, which is a big win on non-flat surfaces. This is most true for animals like horses, which have hind legs with three sections of about equal length, but it's true for humans, too. Try climbing in rigid ski boots that lock the ankle joint.

Lots of people have built walkers. It's building a runner that makes it serious.

Did you see the claimed numerical performance for the new NVidia chip? 100 gigaflops. I can hardly wait until we have that kind of performance in the main CPU(s).

The purpose of that research group at Intel is to find new ways to use up CPU time. Really. I've been down to visit that group. I do physically-based animation myself, so I'm familar with that crowd.

Cloth is hard to simulate because cloth has hard tension limits. This makes the numerical problem stiff, and you can't just integrate the springs and dampers explicitly. You have to either use a constraint solver or an implicit integrator, both of which are slow. This class of problem (integration of stiff systems of differential equations) takes more numerical work than it seems it should. Work continues on speeding it up.

Animats wrote:

One has been found already; the hole in PGP discussed on Slashdot about two weeks ago. So it's a real problem.

An NSA-installed backdoor has not been "found already" in PGP. It was a bug. Not the first either (if you've followed PGP for the last 7 years or so). To conclude that NSA-installed backdoors are a "real problem" on the basis of that particluar bug is wrong.

The NSA backdoors may be a real problem, but don't conclude that from the occurrance of legitimate bugs in complex software.

Honda has the advantage of being an industrial company with a good mechanical engineering R&D operation. To build something like that, you need more technicians and machinists than researchers. Most robotics labs in the US are in computer science departments, and with the exception of the Field Robotics Center at CMU, aren't organized to build good machinery on a reasonable schedule. DoD isn't throwing money at this problem any more; they did in the 1970s and 1980s, and didn't see much for their money.

The hardware component state of the art is actually pretty good, which wasn't true a decade ago. Early robotics researchers wasted too much time on building radio links, motor controllers, encoders, and similar parts. Now you can buy all that stuff. Getting enough compute power onboard is now the easy part. Rate gyros and accelerometers are now stock, low-cost items. CCD TV cameras are easily available. Laser rangefinders are still big, clunky, and overpriced, but depth from stereo vision, after thirty years of work, now works well in real time.

Controlling a legged robot is a tough problem, but there's been a fair amount of work on balance. I have a patent in that area myself. Most of the work on legged locomotion is now going into animation and games, but the results will be useful in the real world.

Nobody makes money from mobile robots, though. A few companies have tried, notably Denning Robotics and HelpMate, but not with success. The basic problem is that robots compete with cheap people, and aren't much faster.

• 1929.com Interesting, but needs more material.
• WPA Writer's Project A Library of Congress collection. Good photos.
• Songs of the Great Depression Brother, can you spare a dime?
• Downside.com See the guy jump out the window, just like 1929. A service of Animats

I'm not sure their discussion mechanism actually works; I don't see any items other than the ones the OpenLaw staff posted, and at one point I got the message Warning: Uninitialized variable or array index or property (phorum-collapse-general) in home/httpd/html/msdoj/discuss/read.php3 on line 271. So they need to do some debugging.

Wavelet compression of video has been out for a while. Indeo 4 and 5 (but not Indeo 1,2, and 3) use wavelet compression. The Indeo 5 codec for .AVI files is a major improvement over Cinepak, the previous leader in .AVI codecs. Indeo 5 has far fewer annoying artifacts than Cinepak, even at higher compression ratios. Check out my Kick the Crooks Out, 15 seconds of Indeo 5 video.