Re: Need some advice on multithreading
Re: Need some advice on multithreading
- Subject: Re: Need some advice on multithreading
- From: WT <email@hidden>
- Date: Mon, 24 Nov 2008 18:27:49 +0100
>> [...]
>>2. continuously running the simulation engine, at a rate that can
also
>>be changed dynamically by the user (for instance, in the bouncing
>>balls example, increasing gravity makes the balls move faster,
thereby
>>requiring the engine to run more often in order to preserve
accuracy
>>and to prevent anomalies such as the balls overlapping one
another);
This isn't normally how physics simulations are done (decreasing
step time based on number of objects). This is especially bad
because collision detection can go up exponentially with the number
of objects (so more math has to be done per step as it is).
I'm not decreasing the time step based on the number of objects. In
the example of the bouncing balls (which, by the way, is merely an
example I used to introduce my questions - the simulations I'm doing
are related to far more advanced physics than merely collisions), the
number of balls is constant. As far as collision detection, the growth
is actually not exponential but quadratic (simultaneous collisions
between more than 2 balls can safely be ignored), and there are a
variety of efficient data structures to handle collision detection
(quad-trees, range-trees, cell-based data structures, and others).
>While it may wind up making sense to put the simulation engine in
a separate thread, I would recommend _not_ trying to adjust the
simulation rate to account for the speed of the balls, precision,
etc. This sort of load-adjusting sounds good in theory, but it
ultimately fails because the performance characteristics of the
code changes according to the settings.
I'm afraid I'll have to disagree. My concern is not balancing the
CPU load, but getting accurate results. To use the bouncing balls
example again, if the balls move fast enough and if I don't
compensate by decreasing the time-interval through which I'm
advancing the motion, the balls WILL overlap and may do so
considerably. Even if they don't overlap in a way that's visible to
the human eye, overlaps may cause other anomalies, such as energy
non-conservation. These kinds of problems are typical of numerical
integration of differential equations and have nothing to do with
optimizing the CPU use.
Actually, this sounds more like a problem in the physics simulation
itself - no matter how small the time-step of the simulation,
collision will cause items to overlap. There are two approaches
that are common - recalculate with a smaller time step until the
items no longer overlap (basically a binary search to find the
impact time). The second is to use the math to figure out the exact
moment of collision - it's not too hard to figure out when two
spheres will intersect based on position, direction, and
acceleration (or sphere vs plane), but doing this for an arbitrary
shape that is also spinning (think rolling dice) becomes much harder.
That overlaps will happen is unavoidable and it's not due to the
physics simulation itself. It's due to the nature of floating point
calculations being of finite precision. It is possible to deal with
these overlaps, but it's generally a good idea not to have them happen
very often.
The way it is generally done is to basically have two loops - one
that is always executed on a regular basis (to advance, say, a
single frame) and then within that "update simulation 1 frame" it
can use one of the two basic options above to have multiple (and non-
regular) updates to advance the simulation.
Personally I'd recommend looking into how existing physics engines
work (I'm a fan of ODE), as well getting a copy of O'Reilly's
"Physics for Game Developers", and track down David Baraff's (of
Pixar) "Rigid Body Simulation" paper. Brent Dingle's "Rigid Body
Motion, An Introduction" is a good lead in to the Baraff paper as
well. In general, the trick is to figure out how to do as little
math as possible on a regular basis, even if it requires doing some
more sophisticated math on an occasional basis.
I appreciate the suggestions, but I'd like to say that the math, the
physics, and the simulation aren't the problem for me. I'm a physicist
by training with experience simulating physical phenomena and, as I
already mentioned, the bouncing balls are merely an example to
illustrate the general nature of the questions I had, which really
have to do with the best practices of using threads in a Cocoa
application.
I don't mean to sound ungrateful for people's efforts to help me, and
this isn't directed specifically to Glenn, but to everyone, but I'd
appreciate if people provided tips related to threads in Cocoa rather
than tips on how to simulate bouncing balls.
Thanks.
Wagner
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden