(changed subject, as this was much more about physics simulation than
about concurrency).
yes, this is a big long "personal history dump" type thing, please
ignore if you don't care.
On 4/3/2012 10:47 AM, Miles Fidelman wrote:
David Barbour wrote:
Control flow is a source of much implicit state and accidental
complexity.
A step processing approach at 20Hz isn't all bad, though, since at
least you can understand the behavior of each frame in terms of the
current graph of objects. The only problem with it is that this
technique doesn't scale. There are easily up to 15 orders of
magnitude in update frequency between slow-updating and fast-updating
data structures. Object graphs are similarly heterogeneous in many
other dimensions - trust and security policy, for example.
Hah. You've obviously never been involved in building a CGF simulator
(Computer Generated Forces) - absolute spaghetti code when you have to
have 4 main loops, touch 2000 objects (say 2000 tanks) every
simulation frame. Comparatively trivial if each tank is modeled as a
process or actor and you run asynchronously.
I have not encountered this term before, but does it have anything to do
with an RBDE (Rigid Body Dynamics Engine), or often called simply a
"physics engine".
this would be something like Havok or ODE or Bullet or similar.
I have written such an engine before, but my effort was single-threaded
(using a fixed-frequency virtual timer, with time-step subdivision to
deal with fast-moving objects).
probably would turn a bit messy though if it had to be made internally
multithreaded (it is bad enough just trying to deal with irregular
timesteps, blarg...).
however, it was originally considered to potentially run in a separate
thread from the main 3D engine, but I never really bothered as there
turned out to not be much point.
granted, one could likely still parallelize it while keeping everything
frame-locked though, like having the threads essentially just subdivide
the scene-graph and each work on a certain part of the scene, doing the
usual thing of all of them predicting/handling contacts within a single
time step, and then all updating positions in-sync, and preparing for
the next frame.
in the above scenario, the main cost would likely be how to best go
about efficiently dividing up work among the threads (the usual strategy
I use is work-queues, but I have doubts regarding their scalability).
side note:
in my own experience, simply naively handling/updating all objects
in-sequence doesn't tend to work out very well when mixed with things
like contact forces (example: check if object can make move, if so,
update position, move on to next object, ...). although, this does work
reasonably well for "Quake-style" physics (where objects merely update
positions linearly, and have no actual contact forces).
better seems to be:
for all moving objects, predict where the object wants to be in the next
frame;
determine which objects will collide with each other;
calculate contact forces and apply these to objects;
update movement predictions;
apply movement updates.
however, interpenetration is still not avoided (sufficient forces will
still essentially push objects into each other). theoretically, one can
disallow interpenetration (by doing like Quake-style physics and simply
disallow any post-contact updates which would result in subsequent
interpenetration), but in my prior attempts to enable such a feature,
the objects would often become "stuck" and seemingly entirely unable to
move, and were in-fact far more prone to violently explode (a pile of
objects will seemingly become stuck-together and immovable, maybe for
several seconds, until ultimately all of them will violently explode
outward at high velocities).
allowing objects to interpenetrate was thus seen as the "lesser evil",
since, even though objects were violating the basic assumption that
"rigid bodies aren't allowed to exist in the same place at the same
time", typically (assuming the collision-detection and force-calculation
functions are working correctly, itself easier said than done), this
will generally correct itself reasonably quickly (the contact forces
will push the objects back apart, until they reach a sort of
equilibrium), and with far less incidence of random "explosions".
sadly, the whole physics engine ended up a little "rubbery" as a result
of all of this, but it seemed reasonable, as I have also observed
similar behavior to some extent in Havok, and have figured out that I
could deal with matters well enough by using a simpler (Quake-style)
physics engine for most non-dynamic objects. IOW: things using AABBs
(Axis-Aligned Bounding-Box) and similar, and other related "solid
objects which can't undergo rotation", a very naive "check and update"
strategy works fairly well for objects which can only ever undergo
translational movement.
admittedly, I also never was able to get "constraints" to work all that
well:
like, "weld two objects together" or "try to connect them using hinges"
was prone to cause them to essentially go berserk. typically, the
constraints worked by interlocking points using "restorative forces".
for example, a simple "ball socket" constraint would only try to
interlock a single point, and this generally worked fairly well (could
make things like hanging/swinging chains of objects).
hinges were more problematic, often resulting in the object
destabilizing and spinning violently along the joint...
but, weld, it was just terrible... it was far more likely to result in
the welded objects going berserk than actually behave as if they were a
single object. again, Havok exhibited similar behavior sometimes, except
"weld" in Havok actually tended to work...
ultimately, I figured, although I could use ODE (since it is free,
unlike Havok), and generally works somewhat better, my own engine
generally works "well enough" (even if arguably "not very good at all"),
so it lives on (even if most of the actually "serious" or "important"
movements, like those of the player and AI-controlled NPCs, are being
done simply using naive sliding AABBs...).
note that, unlike ODE (and, ironically, Doom3), I never did implement a
system of persistent constraints, as contacts were only ever detected
and handled during a given frame, but were not retained between frames.
instead, I ended up devising the use of dynamically-built BSP trees
(partly split for both static/non-moving and for moving objects) to
speed up collision detection (this strategy was also later applied to my
3D renderer as well). (note: an object at rest will tend to stay at
rest... hence its movement need not be checked or updated, but moving
objects may check against it). performance held up ok for a few thousand
objects (after adding the BSP), so good enough (ironically, I would
later in-fact end up representing the scene to the physics engine *as* a
few thousand non-moving objects...).
note that the 3D engine doesn't bother with fancy (rotational) physics
in cases where only static objects and AABBs exist (since this eats up
time for no good effect). and also because I can run simple AABB physics
at 10 or 16 Hz, but need about 100Hz for rigid-body physics to be
stable, and 10x less updates is also 10x cheaper physics...
knowing what I know now, I could probably write a "better" physics
engine, but is it worth the hassle?... (it is, sadly, right up there
with finishing implementation of my new JIT: yes, I could do it, but is
it actually necessary?... sad for all the nifty things I could do if I
had an endless amount of time...).
or such...
_______________________________________________
fonc mailing list
[email protected]
http://vpri.org/mailman/listinfo/fonc
