- Update engine to allow arbitrary rotation matrices on objects. Hack collision system to ignore rotation for the time being. Goal: allow objects to have arbitrary position and orientation. -- KevinSeghetti: it already does this
Improving current physics
- Chain-of-execution problems. Excerpt from old email:
- * Objects can be pushed around, but geometry cannot be altered dynamically (you can push a box around, but you cannot deform the geometry of the box), but you could make an animation of a box getting deformed.
- * There are currently some chain of execution issues with pushing boxes around, if you push a box against an immovable wall, then push another box against the first box, then push on it, our physics system fails, because it thinks the box will move out of your way, and it can't. What we need to do is add the ability to have each object track what other objects they are in contact with, so that when they are pushed they can push on any objects they would hit and add that other objects mass to their own so that they push back on the player hard enough. BTW, there is nothing special about the player, any object can push any other, their mass controls how much of the momentum is transfered to each object. There are also "anchored" objects, which cannot move under any circumstances.
- Interpenetration. Currently (October 2002) objects still can interpenetrate sometimes, which causes the debug version to assert. This should never happen.
- * One possibility is to track this down and fix it in the engine.
- * Another possibility is to gracefully force the objects apart if this does happen, either through a penalty force or through simple projection (i.e. instantaneous movement of the penetrating object to the nearest non-penetrating position, which should be easy to calculate for AABBs, which is all that WorldFoundry currently uses for collision).
Claim: so-called "chain-of-execution" problems will always occur if collisions are only resolved one pair at a time. Or, put another way, it is very nearly impossible to avoid them in the most general case. Reason: collisions are always processed pair-wise. As long as collisions are only processed pair-wise, this is a local
solution to one part the global
problem (that no
objects intersect). Since we are just solving one part of the solution at a time, we must iterate over all pairs, in a "relaxation" type approach (similar to so-called cyclic coordinate descent solvers, which solve a set of simultaneous constraints by solving one constraint, then the next, then the next, and iterating over all until the solution is met, i.e. all constraints are in a valid state - CCD is a popular technique for IK solvers). The problem is that relaxation/CCD solvers may converge slowly, or may not converge to a solution at all (they may get stuck at local minima). So, it is nearly impossible to guarantee 100% of the time that no objects interpenetrate in a general setting. Solution: iterate a maximum number of times (can also be just 1). Apply penalty forces or use projective correction if penetration is still found after attempting to resolve collisions. The current WF solution, aborting or going into an infinite loop if penetrations occur, is too inflexible.
-- I know of one 100% certain way to prevent objects from interpenetrating: don't let them move (assuming they started in a good state). The approach I took with the physics system was exactly that, start with a known good state (enforced by the level converter), then each frame try to move, if a problem move less, down to not at all. So under this design the worst thing that should happen is paralysis. I wanted to get the physics to the point where this occured and they analyize the situation and try to design a cure. The physics never got to this point, there are clearly some bugs which allow it to get into an unallowed state (object interpenetrating). This even occasionally occurs in simple cases with only one moving object. (note the problem could be limited math precision). (MrLin
-- I agree, limited math precision is certainly a major problem area, since impulse-based simulation requires finding the "exact" time of impact.)
There are serveral problems with my design even if it was working properly:
- It doesn't handle chain of execution (although I do have some ideas)
- It doesn't allow for objects to change size
- It doesn't allow objects to rotate (in physics space)
I am not convinced that this strict prevention technique can't be made to work and expanded to handle these cases, but I don't have the time to do it, so our best bet is probably to replace it entirely with ODE.
- * MrLin - long term, yes, replacement is a good idea. Short term - patch the current system to use penalty forces and/or projective correction to recover gracefully from penetrating configurations. This will allow designers to make levels immediately. IMHO the WF physics is not all that bad - in some cases, simpler physics can make for better gameplay, easier tuning by designers, etc.
Switching to new physics
The fundamental question of "new physics"
The fundamental question to be answered is: should a new physics implementation in WF be a new kind of Mobility
for objects, which interacts with other mobility types including old-style physics, or should a new physics implementation be a replacement for the old "Physics"-Mobility
, meaning that it must implement exactly the same features and expose exactly the same interface?
Making it a new kind of mobility is easier, because it limits the interactions and dependencies with old-style physics (as described in BRAINSTORM section below), and it wouldn't need to match the old physics interface 100%. But, this is simultaneously its limitation - as a new, separate mobility type, new physics wouldn't support the exact interface with the engine, meaning scripts and the engine couldn't interact with new physics as flexibly as with old physics.
Long-term, a replacement
is probably the best idea. A new mobility type
is more of a hack to get new physics working quicky with ODE (indeed, as a "new mobility type", all it does is move objects in a new way).
Also note that making a replacement not only means duplicating the original physics interface, but also means extending
the physics interface in a logical way to allow for angular effects, adding new attributes to PhysicalAttributes
In the text below the distinction is not made explicitly between steps needed for a new mobility type and steps needed for a replacement physics implementation; the text below was written before this realization was made. Keep this in mind.
- General note - perhaps attempt to refactor current WF functionality into using the abstract interfaces from Nebula (see InterfacingNebulaDeviceAndWorldFoundry) instead of creating custom abstract interfaces. This can allow reuse of Nebula functionality.
- General note 2 - the first step is to make sure angular representations of physical state are possible (orientation and angular velocity as the state vector, and the first derivative of the state vector). Then angular effects (like tumbling) can be supported. Next step is to compute collisions on arbitrarily oriented objects and to return the appropriate collision normal. Last step is to use collision normal to generate a force and torque on the object to change its state vector (position, velocity, angular orientation, angular acceleration).
- Update WF object state to have mass distributions (inertia tensor), matrix- or quaternion-based angular orientation, and angular velocity. (QUESTION: should inertia tensor be part of PhysicalAttributes, or should it be OAD data? For instance the mass of an object does not appear in the PhysicalAttributes class - why not?) Currently WF uses Euler angles for angular orientation in physical attributes - get rid of them and replace them with quats or matrices. It should be possible to send an asteroid with an arbitrary mass distribution tumbling through space. Goal: incorporate inertia tensor and angular velocity into WF physical attributes. (It may not be possible at this point to actually have the object tumble through space, because that requires integration of the angular components. It would be possible to implement angular integration in the current WF physics, but this may defeat the purpose of using a separate physics engine. On the other hand, maybe it is a good goal in and of itself to extend WF's own physics engine to include angular effects.)
- * The question is how much state does the WF engine need to store itself, and how much state can be kept private to the physics engine. Maybe WF doesn't need to care about an object's angular velocity or acceleration, or torques. Maybe all this can be kept private to the physics engine.
- Update WF collision detection to allow collision between arbitrarily oriented objects (currently uses only AABB). Use the ODE collision detection routines (through an abstract interface). Maybe make this collision detection a "fine-grained" collision check just like a "slope" is currently implemented. Maybe start just with OBB-OBB collisions (i.e. don't try to do sphere, capsule, cylinder collisions at first, only try to add orientation to the collision). Goal: get fine-grained collision information, and understand how WF represents this information. At this point theoretically the old WF impulse-based physics should work with fine-grained collision (with all inherent difficulties like stacking boxes not working because this is an impulse based system not implementing resting contact properly, see AnalysisOfCurrentPhysicsSystem).
- Move the current physics code from the game directory into a seperate physics directory. Doing this will force all cross references to be dealt with, and make it easier to swap out physics systems (note that the collision system has already been seperated). See function ResolveCollisionEvent(), it does the meat of the physical, spatial collision resolution.
- Update WF world class to contain interface to both the old-style physics and a new-style ODE (Open Dynamics Engine, http://q12.org) world; link WF engine with ODE. Goal: interface WF with old physics through an abstract interface; use same interface to access ODE.
- * Declare new PhysicsSystem class
- * Refactor force accumulation: Change all force accumulation in current handlers (movement.cc) to use force accumulators in thePhysicsSystem
- * Refactor velocity manipulation: Somehow declare a hack-ish interface for directly manipulating velocity in thePhysicsSystem; try to change such cases to use forces instead
- * Refactor integration: Find out where Euler integration (forward timestep) is done, also delegate this to thePhysicsSystem
- * At this point thePhysicsSystem handles the force accumulation and forward timestep using WF physics and collision
- * OPEN QUESTION - how to handle interaction between NON-physics movement (paths, script-controlled objects) and physics movement? Can this also be encapsulated into the physics handler? Or into a separate abstract NonphysicsPhysicsInteractionHandler, to allow different implementations of the interactions between non-physics and physics objects? Or, should the interactions between non-physics and physics objects simply be hard-coded in the engine? See function ResolveCollisionEvent(), which makes sure that at least one actor is physically controlled, then handles the collision between physics-physics and physics-anchored or physics-path, etc.
- ** See TechnicalDetailsOfCollisionDetection; the collision interaction table determines how two objects of different classes will respond with one another. Possibly add new CI_ODEPHYSICS entries to collision interaction table.
- ** Note that a collision interaction pair (CI_PHYSICS,CI_PHYSICS) can exist even if the mobility attribute for the two objects is NOT physics. I.e. physical collision but path-controlled animation. (Only makes sense if one of the two colliding objects is physics-controlled; otherwise, no change in motion occurs.)
- * Then, try to swap thePhysicsSystem with an ODE-compatible one (applies force accumulators to rigid body objects, lets ODE do the integration to determine new positions) and collision as well
- * Probably need to subclass MovementHandler to do this, e.g. subclass ODEPhysicsHandler
- * Allow multiple physics handlers to coexist in same instance of game - so that both old-style and new-style physics can interact
- Create a test ODE world, a test ODE cube connected with a test WF object whose arbitrary position and orientation are determined by the ODE-controlled cube. Goal: prove that ODE can control dynamic behavior of one single WF object.
- Cleanly extend WF object class to allow ODE physics control of objects.
- Cleanly extend attribute editing system to allow specifying of ODE-relevant attributes.
- * Maybe a new OAS, "ODEPhysicsObject.oas" which is included by any other OAS which needs ODE physics
- ** Hrm, does iff2lvl need to be updated? If not, why not? What types of engine changes would require an update of iff2lvl code?
- Interaction between old physics and new physics
- * ODE handles new physics, and keeps angular physics information private to itself
- * ODE only returns new positions, orientations, and linear velocities for objects. Angular velocity is not returned.
- * New collision interaction type (CI_ODEPHYSICS, CI_ODEPHYSICS) means ODE handles both objects, and ODE worries about angular effects, torque, etc, and updates new positions of both objects
- * New collision interaction type (CI_PHYSICS, CI_ODEPHYSICS) means that the PHYSICS object interacts using old-style WF physics with the CI_ODEPHYSICS object, but using only the AABB of the ODEPHYSICS object. In other words the ODE angular information is discarded as far as the PHYSICS object is concerned. This is exactly how the WF engine currently works - it ignores angular orientation in its collision. The impulse that WF physics computes (in ResolveCollisionEvent) can be passed on to the ODEPHYSICS object, which then properly updates the ODEPHYSICS object's angular velocity as well.
- * In other words, the ODE subsystem is a subsystem which, from the point of view of WF, somehow changes the position and orientation of an object. WF needs to know nothing else about the ODE physics!
- ** A ODEPHYSICS cube colliding with an ODEPHYSICS cube would cause both cubes to tumble away
- ** A ODEPHYSICS cube colliding with a PHYSICS cube would collide sooner - as soon as the AABB of the ODEPHYSICS cube touches the AABB of the PHYSICS cube. At that point WF resolves the collision, calculates an impulse. The PHYSICS cube is linearly pushed away. The impulse is passed on to ODE for the ODEPHYSICS cube, where ODE handles it. The ODEPHYSICS cube is also linearly pushed away, but this can induce a torque depending on the exact point of impulse application (which needs to be estimated since actually no collision occurred, only a collision with the AABB). Result: the ODEPHYSICS cube likely tumbles/bounces away; the PHYSICS cube moves away linearly.
- * Question - how does WF apply forces to objects? Need to pass these values through to ODE.
- * Question/Goal - is it possible with this scheme to migrate completely to ODE physics? If everything were of type ODEPHYSICS, would there be any problems (e.g. information that cannot be specified, etc)?
- * Maybe need to eventually add torque application mailboxes to WF, even if WF doesn't know about the angular velocity of the object, it can apply a torque. Or maybe eventually WF does need to know about angular velocity and angular state. This is for the future.
= OPEN QUESTIONS =
- When to create how much of the dynamics world? Create it all at once? Dynamically add/remove objects to the world as the player moves from region to region? Gut feeling - dynamically add/remove. This requires saving rigid body state as you leave an area and restoring that state to ODE later as you re-enter the area. See how WF does this currently - what happens to a moving object which gets suspended in time? How/where is its velocity and other physics paramters saved and restored?
- * KevinSeghetti -- The current system keeps all objects in the entire level in existence at all times (but only runs objects in the 3 active rooms).
- * MrLin -- This certainly would be much easier from a dynamics point of view, but could lead to performance problems since the entire dynamics world has to be updated each frame (there is no way of updating only part of a world). There is a way of "deactivating" certain objects in the dynamics world; I haven't tested to see if disabled bodies really have zero performance impact. If disabled bodies cause no performance hit, then probably the best way to go is to create the entire dynamics world, and disable those bodies which are not in one of the three active rooms, and reactivate them when their rooms become active again. This can be theoretically problematic for long jointed/articulated structures (imagine a chain of links extending across four rooms), but we'll ignore the pathological cases at the beginning.
- Interfacing old and new physics systems. Suggestion - a checkbox, "rigid body". if not checked, old physics applies, no rotation allowed. If checked, rotation allowed, and new ODE physics applies. This implies old physics in NO WAY interact with new physics. This is not necessarily good. Need to think about this more, some sort of limited (collision) interaction would be good.
- * Old system uses "Handlers". This seems to mix AI-controlled-movement, path-controlled-movement, and physics-controlled-movement. How does path-controlled movement currently interact with old-style physics-controlled movement? Use this knowledge to figure out a way to cleanly interface old-physics with other sorts of movement, and to interface old-physics with new-physics, and new-physics with other sorts of movement.
- Replacing WF's collision detection with ODE's collision detection (since ODE has much more advanced box/box, box/sphere, box/triangle mesh, sphere/triangle mesh, capsule, and composite geometry collision detection, all with arbitrary rotation, it can easily subsume WF'S AABB collision). This might, as mentioned above, allow a limited form of interaction between old and new physics.
- Old handlers directly fiddle with velocity; this is not really permitted in a real physics system. Only forces are allowed in a real physics system. Maybe this is OK. Just expose an interface to directly manipulate velocity in the physics engine.
- How to handle jointed objects in ODE - two objects which are physically connected together. Handle as one or two WF objects? For a first attempt at ODE integration it is probably best to ignore joints.