Fast image manipulation : the truth about it (I hope)

["D. Diederen" <D Diederen student ulg ac be>]

> De : SEGV <mlepage@cgocable.net>
> A : gnome-list@gnome.org
> Cc : George <jirka@5z.com>
> Objet : Re: Fast Image Manipulation?
> Date : mercredi 18 novembre 1998 14:58

[clip]

> Sorry, I realize I can't play with the actual display bits. In fact, they may
> not even be on this side of the earth. Although, I don't anticipate this
working
> on non-local displays. Really I'm using X because I'm lazy and don't feel the
> need to learn SVGALIB or something like that. I'll scale back my requirements
> quite a bit before investigating other avenues.
> 
> If I use gdk_draw_pixmap, I'll need to keep separate ones though, right? I
don't
> see how I can draw just a part of one. Is that much overhead, in practice?
I'd
> assume no more than a dozen or so bytes...

[clip]

> -- 
> SEGV    http://www.cgocable.net/~mlepage/
> 

Hello everybody,

As this is a subject that pops up quite often, It think I'll devote some time
to explain the whole thing (or at least what I'm understanding of it) ...

[ GENERAL INTRODUCTION ]

As Gtk/Gnome use gdk, which is basically a thin layer over X calls, the
reasoning in this document also applies to raw X programming. Il will list the
X equivalents to Gdk calls between brackets, e.g. gdk_draw_line()
[XDrawLine()]. The name of the function calls/structures may also be wrong,
since I'm not on my Linux machine to write this...

So, we will consider three things : the GdkImage [XImage], the GdkPixmap
[XPixmap] and another player, the GdkImlibImage [ImlibImage].

[ WHAT'S A GdkImage ? ]

A GdkImage is an image (as you should have guessed) that resides in the adress
space of your application. You can therefore manipulate it yourself. It has the
same byte/bit organization that the video memory of the graphic mode your X
server is currently using. That means you _must_ have your own manipulation
routines to be able to draw in it, for any mode the server may support (even
the _very_ exotic ones), or your app is basically broken.

Some people (read : game coders) therefore require that you put your server in
a particular mode (e.g. 8bpp) before running their apps because they were
unable to code the other modes (for speed or laziness reasons). But keep in
mind this is not possible for everyone, since a given mode is not even
guaranteed to exist on a particular platform.

Another problem with the GdkImage model is that at _any_ time you want to
update the screen, you _must_ transfer the (whole ?) image in the server's
adress space. When using X trough a network, or in the case of some old/broken
servers, this has to be done using TCP/IP (uck !). However most of the new X
servers support another way to transfer the image : it's the famous MITSHM
(M.I.T. shared memory) extension to the X server. Note that even in this case
your image has to be copied two times : first to the memory the two processes
share, and then in the video memory.

Games like XQuake or XDoom do use XImages to do their work (however restricting
you to a 8bpp server only - at least last time I checked), because their major
task is the rendering of the image. When the calculated image is ready, they
just have to flip it on the screen, and they're done.

[ WHAT'S A GdkPixmap ? ]

A GdkPixmap is a server side image. You _can't_ manipulate its byte/bits
directly since it is not in the adress space of your program (you _cannot_ get
a pointer to its data). These pixmaps are the main reason an X server can grow
fairly large memory-wise : it contains _every_ pixmap of _every_ X app in its
own memory. But don't be afraid, this is just displacing memory, since you no
longer need it in your app, so there's no waste.

The advantage is that since the X server owns the pixmaps, you can use any
gdk_draw_*() [XDraw*()] calls on them. The server may even cache some pixmaps
in video memory, and use the graphic board's accelerator to draw line/boxes on
them (1). When the times comes to update the screen, the server only has to do
one memory copy from the pixmap to the screen memory. If the pixmaps were
already in video memory, the server could even use the board's accelerator (1).


Platform games (or any game that contains sprites) should use the pixmap
approach: When starting, they transfer the sprites as pixmaps on the server,
and then they only have to use gdk_draw_pixmap() [XDrawPixmap()] calls to put
them on the screen. Also note that a pixmap using game should also perform very
well on a network (or a broken/old X server that doesn't support SHM), since
the only wire traffic consists in the X calls.

1) This is of course X server implementation dependant !

[ WHAT'S A GdkImlibImage ]

Well, this one has _nothing_ to do with the previous ones. It doesn't even 
even belong to gdk or X, but rather comes from the gdk_imlib [Imlib] library. A
GdkImlibImage basically stores an array of RGB triples describing an image (and
also some private things). You can load various image formats into them using
gdk_imlib, and you can render them to GdkPixmaps [XPixmaps] using gdk_imlib too
(the latter takes care of the pixmap format, as well as palette and dithering
issues).

Please don't even try to implement a game using GdkImlibImages ! While Raster's
(Imlib's author) scaling/rendering code is Great Stuff [TM], the GdkImlibImages
were not created for that purpose. Only imagine the CPU overhead of converting
your RGB data to a screen image (including two memory copies in the shared
memory's case - which is the better), using arbitrarily complex
conversion/dithering bit manipulations (you don't know on what server you're
running), the whole thing at 30+ fps !

Gdk version 1.1.2 ? and higher also contain gdk_rgb*() calls to draw a rgb
image on the screen. But it has to be used _only_ when other methods are not
possible (e.g. if the data comes from a RGB video source (1), you need to
convert it anyway, so chances are gdk_rgb functions are already optimized for
that).

1) Does such a thing exist ? Perhaps we'll need gdk_yuv*() calls ;).

[ YOUR VERY OWN CASE ]

In the case of a StarCr*ft-like game, I would suggest the following approach :

Say we are creating a new game, called Star Conquer. The two opposite camps are
be the humans and the fromens (I put a lot of imagination in that one ;). The
whole set of baground tiles is stored in a file (tiles.png). All the sprites
are stored in humans.png and fromens.png. Of course whe have a table describing
at which coordinates we can find any frame in any file.

The game startup looks like :

- Init everything.
- Load the three .png files in GdkImlibImages using gdk_imlib.
- Convert the three GdkImlibImages to GdkPixmaps using gdk_imlib.
- Destroy the three GdkImlibImages since we'll never need them again (you need
to take care of pixmap referencing if you want them not to be destroyed -
perhaps having a look at imlib's source code would help ?)
- Load all the sprite coordinate tables into appropriates structures - please
don't hardcode them in your program (1).
- Create a new GdkPixmap of the size of your game area. It will be your virtual
screen buffer.
- Create your main window, with a GdkDrawingArea of the size of the game area.

Ok, now what we need is the main game loop. It should look like the following
function: 

/* NOTE: this is pseudo-but-looks-like-real-code, 
   so cut'n'paste won't work :) */
void game_loop_do_one_iteration(void)
{
	/* tile the background */
	for(first_tile; last_tile; tile++) {
		tid = get_tile_from_map_at_coordinates(x, y);
		get_tile_coordinates_from_table(tid, tile_table, 
							  &tile_x, &tile_y);
		gdk_draw_pixmap(double_buffer, scr_x, scr_y, tile_pixmap, 	
				    tile_x, tile_y, TILE_WIDTH, TILE_HEIGHT);
	}
	/* draw the buddies */
	for(first_buddy; last_buddy; buddy++) {
		get_buddy_frame_from_table(buddy->type, buddy->frame++,
						   buddy->table, &buddy_x, &buddy_y,
						   &buddy_width, &buddy_height);
		/* of course, since buddies are not rectangular, there should
		   be a bit of masking, etc., but ... */
		gdk_draw_pixmap(double_buffer, buddy->pos_x, buddy->pos_y, 
				    buddy->pixmap, buddy_x, buddy_y,
				    buddy_width, buddy_height);
	}
 	/* update the screen */
	gdk_draw_pixmap(drawing_area->window, 0, 0, double_buffer, 0, 0,
			    game_area_width, game_area_height);
	/* this will be the trickier part */
	move_buddies_with_at_least_a_bit_of_AI();
}

Then you connect that function to a timeout, and you're done. The AI part is
left as an exercise to the reader :). There are some facts you should examine :
- Full resolution/bit depth independance : Thanks to Raster's code (the
oh-so-great Imlib), your game will run on _any_ X server Imlib can understand
(many if not all of them - you should examine the code).
- Without doing anything, you do the best thing to support hardware
acceleration. In the case of a great server running on great graphic hardware
(read: with a lot memory and clever acceleration), every pixmap would be
cached in the video card (as they're frequently used), and the server would
only have to issue 'blit' accel commands to the hardware (write some magic
numbers).

1) Since don't hardcoding them would save me a lot of work when converting your
game into a Kdemen/Gnomes wargame - hmm ... pleasing scenario, I would be ROTFL
:)

[ CONCLUSION ]

Well, I hope all this will be of use for somebody. Since these are questions
that pop up very often, I hope this document will enlighten some X/Gdk
'newbies' (1) :).

Of course the function/structure names in this document may be wrong, since I
don't do much X programming for now and I'm not in front of my Linux (2) box.
But hey man, man is your man.

Feel free to correct this and distribute at will - even commercially and
without releasing the source code (3) if you wish ... I'm also sorry for my bad
english, but I would be glad to hear of corrections - that's the way I learn !

Cu,
Damien.

1) Note that I'm one of them, I just collected pieces of information around.
2) Especially for RMS : read GNU/Linux :)
3) Oh my, I'm tired of these licence flamewars.

-- 
char *info[] = { 
  "Diederen Damien", 
  "D.Diederen@student.ulg.ac.be",
  "http://www.geocities.com/SiliconValley/Haven/6226/", 
};