Re: [Gnash-dev] invalidated bounds redesign - advice needed

[Martin Guy]

> The solution would be to have *multiple* invalidated bounds.

The algorithm, not the classes, is the hard bit since with many small
objects that don't overlap you risk creating many small
invalidated-bound objects, and comparing these for potential merges
gets at best linearly slower the more there are, at worst
exponentially.

An example of this is when the "bad" driver in Bozzetto's YesNo movie
empties the ashtray out of the car door, or the zoom out from the
traffic jam later in the same clip. Cairo responds to these events by
slowing to snail's pace and suddenly growing from 50 to 192 MB in
memory usage (while OGL and AGG currently keep steaming along at much
the same speed).
 Obviously for a real-time system like a movie player, constant speed
is more important than maximum average frame rate. The current
single-region algorithm is of this kind, and may turn out to be the
best. It certainly has simplicity on its side.

> What is the most efficient / elegant design for such a class?

Once you have a complexity-limited fast algorithm, the data structures
you require and methods to operate on them should drop out of that. If
you try to design the classes first, the algorithm you are forced to
use to work them will be inappropriately conditioned by the premature
choice.

Off the top of my head: partition the stage into N rectangles like a
coarse chessboard, and redraw a whole rectangle if anything in it
changes, then experiment with N to find a good value for simple and
for pathological cases.
Or something of that kind.
Anything that sounds like "try to find the nearest already-invalidated
region out of a list of already-invalidated regions" is probably a
loser unless you can find a way to be sure of limiting the number of
active regions, like setting a large minimum region size.
Mind u, without knowing how the redrawing happens in each renderer
it's hard to say what is most appropriate to each.

Personally I would concentrate on making the player work right at this
stage, not on trying to keep the cpu cool when not much is happening
on stage; the speed-critical case is when there is chaos happening all
over the screen.

   M