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

[Udo Giacomozzi]

Hello Martin,

[sorry, my SPAM filter eat up your message]

Tuesday, February 13, 2007, 6:02:54 PM, you wrote:
>> The solution would be to have *multiple* invalidated bounds.
MG> The algorithm, not the classes, is the hard bit since with many small
MG> objects that don't overlap you risk creating many small
MG> invalidated-bound objects, and comparing these for potential merges
MG> gets at best linearly slower the more there are, at worst
MG> exponentially.

This can be solved by having "snapping" rectangles. Say, you have two
rectangles that do not intersect each other but are just 30 pixels
distant, then these will be merged nevertheless.

It's basically very similar to the "chessboard" approach - just that
the individual rectangles have no fixed position.

So, if you have 1000 sprites of 1x1 pixel size, all in the range of
100 pixels, you end up in approx. 4-6 rectangles, not 1000.

I'm observing this behaviour in the Flash player and I really miss it
in Gnash. I do my tests in difficult situations (800 MHz CPU or less,
full screen SVGA) so I can see very easily where Gnash performs badly.
And it is very bad when a 25 fps movie halts for about 200 ms (that's
loooong!) just because it has to update a single number in the top
left corner of the screen. So, this will end up playing movies more
smoothly.

The extreme is when playing Ninjai movies. AGG takes long scaling
bitmaps (don't know if there is potential for optimizations) and a
player is *very* inefficient when the whole scene is re-rendered just
because there is an additional 10x10 pixel animation in one corner of
the screen. The movie playback rate floats somewhere between 20 and 2
fps (!).


MG> An example of this is when the "bad" driver in Bozzetto's YesNo movie
MG> empties the ashtray out of the car door, or the zoom out from the
MG> traffic jam later in the same clip.

Can you please post the URL to this movie? Would like to see how Flash
performs in this case.


MG> Cairo responds to these events by
MG> slowing to snail's pace and suddenly growing from 50 to 192 MB in
MG> memory usage (while OGL and AGG currently keep steaming along at much
MG> the same speed).

Very strange! Do you have any idea why this happens? It's not related
to the invalidated bounds in this case after all...


MG>   Obviously for a real-time system like a movie player, constant speed
MG> is more important than maximum average frame rate.

Indeed. The constant speed is defined by the movie fps rate and the
player should give it's best to satisfy it.

Very simple example: Take a movie with a fullscreen scaled bitmap
(bicubic image transforms need much CPU) and put two tiny MCs in them,
at opposite corners. Let these MCs move both near the center.

The current design will start re-drawing the whole scene and shrink
the rectangle with each frame, meaning that the time to render the
frame will decrease logarithmically. On my test hardware this means
starting with 2 fps and approaching the nominal frame rate near the
end, which may be 50 fps.

With the new design the two MCs will be rendered separately requiring
very small (and constant!) clipping rectangles. The renderer will
probably be able to keep the nominal frame rate all the time!

Such situations are very frequent in real movies.


MG> The current
MG> single-region algorithm is of this kind, and may turn out to be the
MG> best. It certainly has simplicity on its side.

I like simplicity, but I can't agree that it's an overall advantage in
this case.


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

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

Can't agree. We already get a bunch of invalidated rectangles and the
current "algorithm" combines them on the fly. If you look at strk's
class prototype you'll see that it does not rely on any special
algorithm. In fact, you could re-build the current behaviour with the
same class interface (which would probably be a good idea anyway).


[...]

MG> Anything that sounds like "try to find the nearest already-invalidated
MG> region out of a list of already-invalidated regions" is probably a
MG> loser unless you can find a way to be sure of limiting the number of
MG> active regions, like setting a large minimum region size.

See my explanation above. I'd not limit the minimum region size,
though. Just the intersection *test* should compare rectangles grown
by some amount.


MG> Mind u, without knowing how the redrawing happens in each renderer
MG> it's hard to say what is most appropriate to each.

AGG supports only one clipping rectangle at a time but the renderer
could prepare vector data once (conversion between Gnash and AGG data
structures including transformations) and then do rendering for each
clipping rectangle.

Do the other renderers use clipping at all?


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

I admit I have a personal need to make the player faster. The
improvement would be somewhere between 0% and 2000% (depending on the
movie) and that seems reason enough to me... I know much about the
Gnash rendering process but can't help much with the ActionScript
part, at the moment (even if that will most probably become my prior
interest after the invalidated bounds and video support tasks).

It would also improve rendering of YouTube's (and alike) video player
since they are adding more and more Flash elements in their player.

Udo