Rigid Bodies
Rigid-body dynamics has been slow going. I did some work on changing over from a GLUT-based application to my DirectX-based framework; I want to start making it into a real little game, and my DirectX framework gives me smoother animation updates, full keyboard and mouse control, and minimizes CPU usage (which makes it play nice with other running applications). It's a pain to switch from OpenGL to Direct3D. They're both decent APIs now but OpenGL (when paired with GLUT) just takes a lot less coding overhead for quick-and-dirty programs. It's much easier to think in OpenGL, at least for me. I've been using both for a decade, so it's not really a matter of familiarity with one over the other.
I could keep OpenGL as the rendering API and use DirectInput by itself for keyboard and mouse input. Some games do this, and it works all right. Microsoft has made sure that OpenGL never works quite as nicely as Direct3D for games, though. It's been years since I've done professional games programming in OpenGL on Windows, so maybe I'm all wrong, but back when I was doing it, you had to use an undocumented interface to get full-screen access with OpenGL, and when you did, all the other windows on the desktop got moved down to the lower-right corner of the screen. You may remember playing PC games like Quake 2 that had this effect. You'd exit your game and find all your windows huddled down in the corner.
Aligned Strings
When I was in high school in the early 90s I worked in a group that made an operating system. The OS had been originally written in PL/1 and semi-automatically translated to C shortly before I signed on.
In the C family of languages #include dependency management is a continual struggle, although the same problems apply to some extent to any large system written in a modular language. During development (i.e. all the time) the interfaces between modules are in flux; functions move about. Before IDE assistance it was tedious to figure out which header files to include. Moreover, over time source files end up including more header files than necessary, which slows down compilation.
Precompiled header files address this problem in one way. You essentially have one giant header file with every declaration, and every source file includes it. The gimmick is that that header file is pre-parsed so it loads more quickly.
We put together a different solution that was used for a decade or so. The idea was to scan all the source files and create a database of global symbol declarations. A second scan for uses of global symbols allowed the tool to fabricate a custom header file for each source module containing just the global declarations it needed. Each source file included exactly one header file, so compilation was quick.
The key to this was being able to understand the C code enough to extract global symbol declarations, and to identify global symbol usages. In C if you stay away from tricky use of the macro preprocessor it's not too hard to do. I wrote a parser for the subset of the C grammar dealing with global definitions. In theory we would have had to understand more of the language in order to recognize global symbol usages; we fudged on that by simply including declarations for global symbols whenever we saw their identifiers, regardless of whether the identifier was really a global symbol usage.
This brings me to the subject of parsing. In my tests at the time something like 80% of the time was spent breaking the input into tokens. It takes a lot of time simply to traverse all that text. It turned out that a lot of that time was being spent in string comparisons, looking up identifiers to see if they were reserved words.
To speed up string comparisons we came up with aligned strings. The idea is to treat strings as sequences of 32-bit (or 64-bit) words instead of as sequences of 8-bit characters. The string is kept aligned on a word boundary, and the end is padded with zeros to fill an integral number of words. Then, string comparisons can be done four times (or eight times) faster.
There's a small amount of memory overhead required due to the padding (1.5 bytes per string on average, if you're using 32-bit words), and you have to copy characters out of the input stream into aligned strings before comparing them against other aligned strings.
The only other downside I can think of off-hand is that strings don't necessarily sort in alphabetical order. On a big-endian architecture they do, since the character lowest in memory compares first, then the next. On a little-endian architecture the effective character comparison order is: 3, 2, 1, 0, 7, 6, 5, 4, and so on.
If the specific string ordering is not important, though, I think aligned strings are hard to beat. I'm surprised there hasn't been a string class with this behavior. Maybe there are some other downsides I haven't thought of. It worked great for us all those years ago, though.
Monday, July 30, 2007
Monday, July 23, 2007
Rigid body dynamics, part 5
Not much to report this week as I haven't done any coding. I've continued to think about friction.
My current model is to integrate gravity's effects, then iteratively fix up interpenetrations, adjusting position and/or velocity if objects are colliding. Because the position fixup moves objects apart along their minimum separating axis this can cause unintended sliding:
I remember seeing this in a prerelease version of the original Quake (I don't remember if it made it into the shipping version). If you stood on a ramp you would slowly slide down it.
I don't mind if, when an object first collides, the interpenetration fixup moves it sideways from where it ought to be. People don't notice a small one-time offset like that. It's when an object is supposed to be resting on a surface but doesn't stay put that the problem is very noticeable.
Friction is conceptually a force, which means it is applied over time. My model up to now has been that only gravity is applied over time; collisions are resolved instantaneously. This means that objects are never pressed against each other for a duration of time, so they wouldn't ever have friction. Obviously it ought to be possible to convert the concept of friction into impulses that are applied instantaneously each frame, but I haven't quite seen clearly how to do that in a way that interacts correctly with the collisions.
A bit more Googling turned up some promising leads:
Continuous Physics seems to be a place where the cool kids of game physics hang out. One of them is Erin Catto who has developed a library called Box2D that does almost exactly what I've been developing these past few weeks. Erin has presented at the last few Game Developer Conferences as well. I'm looking over these materials now. Thank you, Erin!
One of the ideas I got from Erin's code is to integrate velocity, then apply fixups to velocity, before integrating position. This should enable me to get around the creeping problem; nonpenetration constraints would cancel the acceleration into the ground, and friction would cancel the tangential acceleration.
Another library I've started looking at is JigLib, by Danny Chapman.
Both of these libraries use a technique called split impulses to correct interpenetration, which seems at first blush very similar to my approach of fixing up positions directly. They generate per-frame fixup velocities which are not added to the object's overall momentum; so far as I can see this ought to do the same thing as just fixing up the positions directly. I'll continue to dig into it, though. The Box2D library, in particular, is simple enough to be readily digested.
My current model is to integrate gravity's effects, then iteratively fix up interpenetrations, adjusting position and/or velocity if objects are colliding. Because the position fixup moves objects apart along their minimum separating axis this can cause unintended sliding:
I remember seeing this in a prerelease version of the original Quake (I don't remember if it made it into the shipping version). If you stood on a ramp you would slowly slide down it.
I don't mind if, when an object first collides, the interpenetration fixup moves it sideways from where it ought to be. People don't notice a small one-time offset like that. It's when an object is supposed to be resting on a surface but doesn't stay put that the problem is very noticeable.
Friction is conceptually a force, which means it is applied over time. My model up to now has been that only gravity is applied over time; collisions are resolved instantaneously. This means that objects are never pressed against each other for a duration of time, so they wouldn't ever have friction. Obviously it ought to be possible to convert the concept of friction into impulses that are applied instantaneously each frame, but I haven't quite seen clearly how to do that in a way that interacts correctly with the collisions.
A bit more Googling turned up some promising leads:
Continuous Physics seems to be a place where the cool kids of game physics hang out. One of them is Erin Catto who has developed a library called Box2D that does almost exactly what I've been developing these past few weeks. Erin has presented at the last few Game Developer Conferences as well. I'm looking over these materials now. Thank you, Erin!
One of the ideas I got from Erin's code is to integrate velocity, then apply fixups to velocity, before integrating position. This should enable me to get around the creeping problem; nonpenetration constraints would cancel the acceleration into the ground, and friction would cancel the tangential acceleration.
Another library I've started looking at is JigLib, by Danny Chapman.
Both of these libraries use a technique called split impulses to correct interpenetration, which seems at first blush very similar to my approach of fixing up positions directly. They generate per-frame fixup velocities which are not added to the object's overall momentum; so far as I can see this ought to do the same thing as just fixing up the positions directly. I'll continue to dig into it, though. The Box2D library, in particular, is simple enough to be readily digested.
Monday, July 16, 2007
64 KB Demos: Replacing the CRT heap
Every so often I visit Pouet.net to see what the demo scene is up to. I've been looking in on the scene for ten years or so, and it's generally inspiring. My current favorite category is 64KB Windows intros (the executable cannot exceed 64 kilobytes in size). Heaven Seven is a good example (disregard the quasi-profundity), although there are some other good ones. The Farbrausch group produces many of the best.
A few years ago I finally decided to see what I could do in 64 KB. I managed to get the basics of a first-person shooter up and running in around 16 KB, and I'll share a few of the things I learned along the way.
I wrote a framework in assembly language but I don't think that's necessarily required. What is necessary is to examine the assembly output of your compiler so you know where the bytes are going. Also, grab an executable compressor. I used UPX but I also recently found out about Crinkler.
One of the big space users when you're coding in C/C++ is the C Runtime Library, a set of commonly-used functions that are statically linked into every executable. Getting rid of this saves a big chunk of executable size.
The primary thing the C Runtime Library provides is a heap manager. Fortunately, the Windows API also provides a heap manager, so all that's necessary to replace it is to write a few glue functions to hook up C++ to the Windows heap. Here's my header file win32_new.h:
And the corresponding source file, win32_new.cpp:
The C++ new and delete operators are overridden to call the appropriate Win32 functions. I also provided definitions for a few other functions.
A few years ago I finally decided to see what I could do in 64 KB. I managed to get the basics of a first-person shooter up and running in around 16 KB, and I'll share a few of the things I learned along the way.
I wrote a framework in assembly language but I don't think that's necessarily required. What is necessary is to examine the assembly output of your compiler so you know where the bytes are going. Also, grab an executable compressor. I used UPX but I also recently found out about Crinkler.
One of the big space users when you're coding in C/C++ is the C Runtime Library, a set of commonly-used functions that are statically linked into every executable. Getting rid of this saves a big chunk of executable size.
The primary thing the C Runtime Library provides is a heap manager. Fortunately, the Windows API also provides a heap manager, so all that's necessary to replace it is to write a few glue functions to hook up C++ to the Windows heap. Here's my header file win32_new.h:
#include <new>
#include <exception>
// Overload global heap allocation functions
void* __cdecl operator new (size_t num_bytes);
void* __cdecl operator new[](size_t num_bytes);
void __cdecl operator delete (void* memory);
void __cdecl operator delete[](void* memory);
inline void __cdecl std::_Throw(const std::exception &)
{
error_exit("std::_Throw called.");
}
And the corresponding source file, win32_new.cpp:
#include "win32_new.h"
#include <windows.h>
#include <string>
typedef unsigned short wchar_t;
void* __cdecl operator new(size_t num_bytes)
{
return HeapAlloc(GetProcessHeap(), 0, num_bytes);
}
void* __cdecl operator new[](size_t num_bytes)
{
return HeapAlloc(GetProcessHeap(), 0, num_bytes);
}
void __cdecl operator delete(void* memory)
{
HeapFree(GetProcessHeap(), 0, memory);
}
void __cdecl operator delete[](void* memory)
{
HeapFree(GetProcessHeap(), 0, memory);
}
void __stdcall raise_handler(const std::exception &)
{
error_exit("raise_handler called.");
}
void (__stdcall* std::_Raise_handler)(const std::exception &) = raise_handler;
void* __cdecl memmove(void *dest, const void *src, size_t count)
{
return wmemmove(reinterpret_cast<wchar_t *> (dest), reinterpret_cast<const wchar_t *>(src), count);
}
void std::_String_base::_Xlen() const // report a length_error
{
error_exit("std::_String_base::_Xlen called.");
}
void std::_String_base::_Xran() const // report an out_of_range error
{
error_exit("std::_String_base::_Xran called.");
}
The C++ new and delete operators are overridden to call the appropriate Win32 functions. I also provided definitions for a few other functions.
Heinlein's Juvenile Novels
I've been reading through Robert Heinlein's juveniles the last three weeks. I had read Rocket Ship Galileo and Podkayne of Mars previously, and was able to get most of the rest through the King County Library system. So far I've read:
Rocket Ship Galileo
Red Planet
Farmer in the Sky
The Rolling Stones
Tunnel in the Sky
Citizen of the Galaxy
Have Space Suit, Will Travel
Podkayne of Mars
It's not a juvenile, but I also read The Moon Is a Harsh Mistress recently. I've got Starman Jones and Time for the Stars left in my pile.
Heinlein's great enthusiasm shows through in all his books. His future is optimistic with regards to the relationship between humans and their technology. I don't think I've ever read a dystopia from him. He tries to educate people about how the world works, and to think carefully about how it might work in the future. Heinlein doesn't limit himself to thinking about how technology might evolve; he is also keenly interested in how societies and their customs might evolve as well.
These juveniles were all written prior to the moon landings. Nevertheless, Heinlein knows enough about space, orbital mechanics, pressure suits, and rocket engines to make things pretty plausible; certainly far more plausible than a lot of modern “realistic” space fiction. I remember reading a novel a year or two ago featuring your typical Star Trek-inspired space battleships with people sitting around and verbally relaying orders. The author seemed to think that his ships could “take the high ground” in a solar system by orbiting around its sun faster and faster; they were then able to strike more readily whenever and wherever a threat appeared. Completely ridiculous!
Computer games have the potential to give players visceral understanding of complicated concepts. It would be neat to have a fun game that gives people an intuitive grasp of orbital mechanics and the dimensions of our Solar System. This would, if nothing else, give authors of generic sci-fi better mental pictures of how things work, so they can avoid the dumber mistakes. When the kids of the 40s and 50s grew up to make real rockets, they had in mind the pictures planted there by Heinlein and other authors.
Rocket Ship Galileo
Red Planet
Farmer in the Sky
The Rolling Stones
Tunnel in the Sky
Citizen of the Galaxy
Have Space Suit, Will Travel
Podkayne of Mars
It's not a juvenile, but I also read The Moon Is a Harsh Mistress recently. I've got Starman Jones and Time for the Stars left in my pile.
Heinlein's great enthusiasm shows through in all his books. His future is optimistic with regards to the relationship between humans and their technology. I don't think I've ever read a dystopia from him. He tries to educate people about how the world works, and to think carefully about how it might work in the future. Heinlein doesn't limit himself to thinking about how technology might evolve; he is also keenly interested in how societies and their customs might evolve as well.
These juveniles were all written prior to the moon landings. Nevertheless, Heinlein knows enough about space, orbital mechanics, pressure suits, and rocket engines to make things pretty plausible; certainly far more plausible than a lot of modern “realistic” space fiction. I remember reading a novel a year or two ago featuring your typical Star Trek-inspired space battleships with people sitting around and verbally relaying orders. The author seemed to think that his ships could “take the high ground” in a solar system by orbiting around its sun faster and faster; they were then able to strike more readily whenever and wherever a threat appeared. Completely ridiculous!
Computer games have the potential to give players visceral understanding of complicated concepts. It would be neat to have a fun game that gives people an intuitive grasp of orbital mechanics and the dimensions of our Solar System. This would, if nothing else, give authors of generic sci-fi better mental pictures of how things work, so they can avoid the dumber mistakes. When the kids of the 40s and 50s grew up to make real rockets, they had in mind the pictures planted there by Heinlein and other authors.
New Computer, O/S, Compiler
I got my first notebook computer recently, as my wife was getting tired of sharing our desktop PC. (She will tell you that it's because she is trying to cut down on the number of hours a day I sit at a desk.) It's a ThinkPad, and it came with Windows Vista. As a result, I've been spending my time doing the busy-work you have to do whenever you change anything, in order to be able to get back to doing real work.
The version of Developer Studio that I've been using is pretty old by now, so I also decided to try out Visual C++ Express, the free version that's available now. Unfortunately free means it's not as easy to get running, but without too much trouble I got the Platform and DirectX SDKs installed, and I'm able to compile my DirectX applications. Getting GLUT working was relatively simple, after I figured out how to get around Microsoft's new protections on the Program Files directory subtree. My ATL/WTL apps are still not quite compiling; I'll have to figure that out later. MFC is also not included by default, although it appears to be in the Platform SDK so there's probably some voodoo I can do to get it working. I don't use it any more but some of my old programs were written using it.
Windows Vista is slightly hostile to software developers; by trying to make life harder for malicious software developers they ended up making it harder for all legitimate ones, too. Every time I launch Developer Studio I have to click through a dialog. As we all know, making people click through dialogs is a sure way to get them to pay attention.
The Program Files directory subtree is now read-only, although that fact is not made visible in the file or directory attributes. You can open a file from there in Notepad, edit it (as the Dev Studio Express directions tell you to), but when you try to save you get a very non-obvious error message. I wound up copying the files I needed to edit out to a different directory, then copying them back in once I'd made the changes.
I can't seem to double-click on a solution to launch Developer Studio; I don't know if that's related to the security stuff in Vista. Also, the new version of Developer Studio no longer allows me to drag files onto it for editing. Maybe that's a way of crippling the free version. I miss it a lot.
I'm considering switching to Jam for making projects instead of using Developer Studio's built-in system. It is extraordinarily tedious to make new projects using Developer Studio. For some incredibly dumb reason they use GUIDs in their project files, which means you can't just copy and modify an existing project file to create a new one (without editing all the GUIDs as well). We had a giant situation with that at work where half our project files all had the same GUIDs.
I've used Jam before. On the plus side, it's incredibly fast and the source code is freely available. It's the tool of choice for the Boost project. On the minus side, its syntax is about as idiosyncratic as that of most other make tools, and it doesn't seem like it gets really wide use. I still haven't determined if the new version of Developer Studio is faster than the last one I was using, which took about a second to determine that there was nothing to build in a project. When you have a solution consisting of 20-30 projects, that sucks a lot of time out of your day.
The computer itself seems reasonable. ThinkPads are tough; I was grateful for that when my baby girl stood on the closed computer within minutes after it was unpacked. LCD manufacturers are forcing notebook computers to go with widescreen aspect ratios; I'm guessing this is so they can manufacture the same LCD screens for HDTVs and computers. Resolution is one area that I have been making backward progress in over the years. I used to have a nice 21-inch CRT with 1600x1200. Then I switched to a 19-inch LCD monitor that could only do 1280x1024. Now I'm on a notebook computer with only 1440x990. The number of lines of code that I can see at once is a lot less.
The version of Developer Studio that I've been using is pretty old by now, so I also decided to try out Visual C++ Express, the free version that's available now. Unfortunately free means it's not as easy to get running, but without too much trouble I got the Platform and DirectX SDKs installed, and I'm able to compile my DirectX applications. Getting GLUT working was relatively simple, after I figured out how to get around Microsoft's new protections on the Program Files directory subtree. My ATL/WTL apps are still not quite compiling; I'll have to figure that out later. MFC is also not included by default, although it appears to be in the Platform SDK so there's probably some voodoo I can do to get it working. I don't use it any more but some of my old programs were written using it.
Windows Vista is slightly hostile to software developers; by trying to make life harder for malicious software developers they ended up making it harder for all legitimate ones, too. Every time I launch Developer Studio I have to click through a dialog. As we all know, making people click through dialogs is a sure way to get them to pay attention.
The Program Files directory subtree is now read-only, although that fact is not made visible in the file or directory attributes. You can open a file from there in Notepad, edit it (as the Dev Studio Express directions tell you to), but when you try to save you get a very non-obvious error message. I wound up copying the files I needed to edit out to a different directory, then copying them back in once I'd made the changes.
I can't seem to double-click on a solution to launch Developer Studio; I don't know if that's related to the security stuff in Vista. Also, the new version of Developer Studio no longer allows me to drag files onto it for editing. Maybe that's a way of crippling the free version. I miss it a lot.
I'm considering switching to Jam for making projects instead of using Developer Studio's built-in system. It is extraordinarily tedious to make new projects using Developer Studio. For some incredibly dumb reason they use GUIDs in their project files, which means you can't just copy and modify an existing project file to create a new one (without editing all the GUIDs as well). We had a giant situation with that at work where half our project files all had the same GUIDs.
I've used Jam before. On the plus side, it's incredibly fast and the source code is freely available. It's the tool of choice for the Boost project. On the minus side, its syntax is about as idiosyncratic as that of most other make tools, and it doesn't seem like it gets really wide use. I still haven't determined if the new version of Developer Studio is faster than the last one I was using, which took about a second to determine that there was nothing to build in a project. When you have a solution consisting of 20-30 projects, that sucks a lot of time out of your day.
The computer itself seems reasonable. ThinkPads are tough; I was grateful for that when my baby girl stood on the closed computer within minutes after it was unpacked. LCD manufacturers are forcing notebook computers to go with widescreen aspect ratios; I'm guessing this is so they can manufacture the same LCD screens for HDTVs and computers. Resolution is one area that I have been making backward progress in over the years. I used to have a nice 21-inch CRT with 1600x1200. Then I switched to a 19-inch LCD monitor that could only do 1280x1024. Now I'm on a notebook computer with only 1440x990. The number of lines of code that I can see at once is a lot less.
Friday, July 13, 2007
Guns, Cars, and Sports
I watched most of Sony's E3 presentation the other day. They were showing previews of their games lineup for the coming year. If you like guns, cars, or sports, Sony's got you covered. Especially if you like guns.
Presentations like this always give me a sinking feeling. There is a huge, huge gap between the kinds of games that could get made and the ones that do get made.
Presentations like this always give me a sinking feeling. There is a huge, huge gap between the kinds of games that could get made and the ones that do get made.
Monday, July 9, 2007
Rigid Body Dynamics: Friction
Friction is tricky. It's generally formulated as a force, integrated over time. In my program as it stands now, only gravity is integrated; the rest of the simulation is handled via impulses between frames.
Numerical integration methods make simplifying assumptions about how forces will behave over the frame duration. The simplest is to assume forces won't change. For a uniform gravity field this is not a bad assumption. For friction, though, it's not a good assumption. Friction forces should never cause objects to reverse direction, which is entirely possible if you assume the friction doesn't change during a frame.
I am going to try and work friction into my impulse model. Brian Mirtich's thesis covers this in quite a lot of detail. Basically I will assume that friction doesn't change during a frame, but clamp it so that it never reverses object directions or adds energy.
This week I did a tiny step toward that. When a collision happens, I compute an impulse that cancels all relative motion at the collision point. This is equivalent to a completely inelastic collision (because motion in the normal direction is canceled) combined with infinite static friction (because all motion in the tangential direction is canceled). I decided to try this out because it's sort of the maximum friction possible; sliding friction and bouncing will involve reducing it somehow.
To come up with the proper impulse, I wrote an expression for how the relative velocity changes as a function of the (unknown) impulse, then set it equal to the negative of the relative velocity to be canceled:
In the equation p is the unknown impulse. The r constants are the positions of the contact point with respect to the two bodies' centers of mass, but turned 90 degrees counterclockwise. I put the little T symbol on them to indicate that. Basically, these are the direction vectors for affecting the objects' rotational velocity. They scale up as the contact point gets further from the center of mass, since you get better leverage the further out you get. The M and I constants are the mass and rotational inertia tensor, respectively; in 2D they're both scalars.
This is a vector equation, so it works out to two scalar equations in two unknowns (the components of p). I used Cramer's Rule to solve the system of equations for the impulse.
With this friction, wheels roll, but they can never skid. I think I'll start to put together a vehicle this week. This will involve making some constraints to hold the wheels and the body together. I'll solve these the same way I solve nonpenetration constraints; by fixing up after integration.
Numerical integration methods make simplifying assumptions about how forces will behave over the frame duration. The simplest is to assume forces won't change. For a uniform gravity field this is not a bad assumption. For friction, though, it's not a good assumption. Friction forces should never cause objects to reverse direction, which is entirely possible if you assume the friction doesn't change during a frame.
I am going to try and work friction into my impulse model. Brian Mirtich's thesis covers this in quite a lot of detail. Basically I will assume that friction doesn't change during a frame, but clamp it so that it never reverses object directions or adds energy.
This week I did a tiny step toward that. When a collision happens, I compute an impulse that cancels all relative motion at the collision point. This is equivalent to a completely inelastic collision (because motion in the normal direction is canceled) combined with infinite static friction (because all motion in the tangential direction is canceled). I decided to try this out because it's sort of the maximum friction possible; sliding friction and bouncing will involve reducing it somehow.
To come up with the proper impulse, I wrote an expression for how the relative velocity changes as a function of the (unknown) impulse, then set it equal to the negative of the relative velocity to be canceled:
In the equation p is the unknown impulse. The r constants are the positions of the contact point with respect to the two bodies' centers of mass, but turned 90 degrees counterclockwise. I put the little T symbol on them to indicate that. Basically, these are the direction vectors for affecting the objects' rotational velocity. They scale up as the contact point gets further from the center of mass, since you get better leverage the further out you get. The M and I constants are the mass and rotational inertia tensor, respectively; in 2D they're both scalars.
This is a vector equation, so it works out to two scalar equations in two unknowns (the components of p). I used Cramer's Rule to solve the system of equations for the impulse.
With this friction, wheels roll, but they can never skid. I think I'll start to put together a vehicle this week. This will involve making some constraints to hold the wheels and the body together. I'll solve these the same way I solve nonpenetration constraints; by fixing up after integration.
Monday, July 2, 2007
Rigid Body Dynamics, part 3
(Part 1 and part 2 here.)
Flat-shaded discs aren't very good for seeing rotation, so I gave them a radial pattern:
Immediately, I saw something odd: occasionally a colliding disc would start spinning, sometimes at high speed. Since collisions are currently frictionless, this should not happen.
After poking at it for an hour I pinpointed the problem. I was collecting all contacts in a list before handling any of them. However, the collision handler moves objects apart when they are interpenetrating. The contact record stores a world-space contact position, which is incorrect if the objects in question have been moved by an earlier contact resolution. In frictionless disc collisions, the collision impulse should always be aimed through the center of the disc, but due to prior movement of the disc it would sometimes be off-center, which imparted a spin to the disc.
For the moment, then, I am back to finding and handling collisions one at a time.
I'm still daunted a bit by the quadratic programming espoused by some of the papers I've been reading. I've turned up a few newer papers, and it seems like people are going in the direction I have, which is to say: integrate without worrying about constraints, then iteratively fix up problems, rather than trying to come up with a giant system of equations (or inequalities) and solve them wholesale. I don't know if that's because it's better or just easier, though.
I'm currently trying to see if I can add friction to my current model, without going to the giant-system-of-equations approach. I need friction in order to implement things like wheels. Friction is usually modeled as two different kinds: resistance to motion while in motion (dynamic friction), and resistance to motion while stationary (static friction). A rolling wheel makes use of static friction since the part touching the ground is stationary with respect to it. A skidding wheel experiences dynamic friction instead.
Flat-shaded discs aren't very good for seeing rotation, so I gave them a radial pattern:
Immediately, I saw something odd: occasionally a colliding disc would start spinning, sometimes at high speed. Since collisions are currently frictionless, this should not happen.
After poking at it for an hour I pinpointed the problem. I was collecting all contacts in a list before handling any of them. However, the collision handler moves objects apart when they are interpenetrating. The contact record stores a world-space contact position, which is incorrect if the objects in question have been moved by an earlier contact resolution. In frictionless disc collisions, the collision impulse should always be aimed through the center of the disc, but due to prior movement of the disc it would sometimes be off-center, which imparted a spin to the disc.
For the moment, then, I am back to finding and handling collisions one at a time.
I'm still daunted a bit by the quadratic programming espoused by some of the papers I've been reading. I've turned up a few newer papers, and it seems like people are going in the direction I have, which is to say: integrate without worrying about constraints, then iteratively fix up problems, rather than trying to come up with a giant system of equations (or inequalities) and solve them wholesale. I don't know if that's because it's better or just easier, though.
I'm currently trying to see if I can add friction to my current model, without going to the giant-system-of-equations approach. I need friction in order to implement things like wheels. Friction is usually modeled as two different kinds: resistance to motion while in motion (dynamic friction), and resistance to motion while stationary (static friction). A rolling wheel makes use of static friction since the part touching the ground is stationary with respect to it. A skidding wheel experiences dynamic friction instead.
Subscribe to:
Posts (Atom)