Subject: Mini Demo: A fluttering flag

From: Shlomi Fish <[email-masked]>
Date: Thu, 7 Feb 2002 03:48:01 +0200 (IST)

When my father bought our first CD-ROM drive, he bought a 10-CD pack that
contained various CDs. One of them was a CD that contained many demos,
animations and other goodies like that. I enjoyed the demos that were
there very much.

In one of demos (I think it was Unreal by the Future Crew, but it's
possibly one of the Electro-Motive Force (=EMF) demos), there was a
fluttering flag of Finland, on whose horizontal line, there were several
greetings displayed. I thought of a scheme to duplicate that effect and
, surely enough, after a small amount of QBasic hacking (I only knew C and
Basic back then) I managed to create a very similar effect. I eventually
converted it to C.

I misplaced the C program and the QBasic script, not to mention that the
former could only run on Turbo C++ and Borland C++. However, I
decided to spend this sleepless night, implementing a similar flag in SDL
(= Simple DirectMedia Layer). I first wanted it to be in Perl, but because
the examples tar file of SDL-Perl was corrupt, I decided to write it in C
instead.

The code is included here, for your reference, there's some extra
discussion below:
(compile with gcc -O2 -I/usr/include/SDL flag.c -lm -lSDL)

/************************************/
#include <stdio.h>
#include <math.h>

#include <SDL.h>

#define PI 3.14159265358

#if 1
#define putpixel(surface, x, y, pixel)  \
    {   \
        *(Uint8 *)(surface->pixels + (y) * surface->pitch + x) = pixel; \
    }

#else
/* This putpixel definition was ripped from the SDL doc project */

/*
 * Set the pixel at (x, y) to the given value
 * NOTE: The surface must be locked before calling this!
 */
void putpixel(SDL_Surface *surface, int x, int y, Uint32 pixel)
{
    int bpp = surface->format->BytesPerPixel;
    /* Here p is the address to the pixel we want to set */
    Uint8 *p = (Uint8 *)surface->pixels + y * surface->pitch + x * bpp;

    switch(bpp) {
    case 1:
        *p = pixel;
        break;

    case 2:
        *(Uint16 *)p = pixel;
        break;

    case 3:
        if(SDL_BYTEORDER == SDL_BIG_ENDIAN) {
            p[0] = (pixel >> 16) & 0xff;
            p[1] = (pixel >> 8) & 0xff;
            p[2] = pixel & 0xff;
        } else {
            p[0] = pixel & 0xff;
            p[1] = (pixel >> 8) & 0xff;
            p[2] = (pixel >> 16) & 0xff;
        }
        break;

    case 4:
        *(Uint32 *)p = pixel;
        break;
    }
}
#endif
/*
 * Linus Torvalds would kill me if he saw this, but who is John Galt?
 * (at least not Linus, I hope)
 * */
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

int main(int argc, char * argv[])
{
    int x_num_points = 20;
    int y_num_points = 10;
    int x_x_offset = 20;
    int x_y_offset = 0;
    int y_x_offset = 3;
    int y_y_offset = 10;
    double y_amplitude = 5.0;
    int y_amp_delta = 50;
    int x_amp_delta = 20;
    /* This is so it won't get out of the end of the screen */
    int y_abs_offset = 10;
    int x_abs_offset = 10;
    int sin_lookup[512];

    int x,y,t, prev_t;
    int prev_y_height;
    int this_y_height;
    int x_pos, y_pos;
    Uint32 black, white;

    SDL_Surface *screen;
    SDL_Rect * rects;
    SDL_Rect * the_rect;

    int a;

    for(a=0;a<512;a++)
    {
        sin_lookup[a] = (int)(sin((2*PI/512)*a)*y_amplitude);
    }

    /* Initialize the SDL library */
    if( SDL_Init(SDL_INIT_VIDEO) < 0 ) {
        fprintf(stderr,
                "Couldn't initialize SDL: %s\n", SDL_GetError());
        exit(1);
    }

    /* Clean up on exit */
    atexit(SDL_Quit);

    /*
     * Initialize the display in a 640x480 8-bit palettized mode,
     * requesting a software surface
     */
    screen = SDL_SetVideoMode(640, 480, 8, SDL_SWSURFACE);
    if ( screen == NULL ) {
        fprintf(stderr, "Couldn't set 640x480x8 video mode: %s\n",
                        SDL_GetError());
        exit(1);
    }

    black = SDL_MapRGB(screen->format, 0x00, 0x00, 0x00);
    white = SDL_MapRGB(screen->format, 0xFF, 0xFF, 0xFF);
    rects = (SDL_Rect *)malloc(sizeof(rects[0]) * x_num_points*y_num_points*2);
    for(a=0;a<x_num_points*y_num_points*2;a++)
    {
        rects[a].w = rects[a].h = 1;
    }

    printf("%i\n", SDL_MUSTLOCK(screen));

    prev_t = 0;
    for(t=1 ; ; t = (t+1)%512)
    {
        the_rect = rects;
        for(y=0;y<y_num_points;y++)
        {
            for(x=0;x<x_num_points;x++)
            {
#define degree(the_t) ((y_amp_delta*y+x_amp_delta*x+(the_t))%512)
                y_pos = y_abs_offset +
                    x_y_offset * x + y_y_offset * y;
                prev_y_height =  y_pos +
                    sin_lookup[degree(prev_t)]
                    ;
                this_y_height = y_pos +
                    sin_lookup[degree(t)]
                    ;

                x_pos = x_abs_offset + x_x_offset * x + y_x_offset * y;

                the_rect->x = x_pos;
                the_rect->y = prev_y_height;
                the_rect++;
                the_rect->x = x_pos;
                the_rect->y = this_y_height;
                the_rect++;

                /* I don't need to lock the screen, so I'm omitting it */
#if 0
                /* Lock the screen for direct access to the pixels */
                if ( SDL_MUSTLOCK(screen) ) {
                    if ( SDL_LockSurface(screen) < 0 ) {
                        fprintf(stderr, "Can't lock screen: %s\n", SDL_GetError());
                        return;
                    }
                }
#endif

                putpixel(
                    screen,
                    x_pos,
                    prev_y_height,
                    black
                    );

                putpixel(
                    screen,
                    x_pos,
                    this_y_height,
                    white
                    );

#if 0
                if ( SDL_MUSTLOCK(screen) ) {
                    SDL_UnlockSurface(screen);
                }
#endif

            }
        }

        SDL_UpdateRects(screen, x_num_points*y_num_points*2, rects);

#if 0
        SDL_UpdateRect(screen, x_pos, min(prev_y_height, this_y_height), 1, max(prev_y_height, this_y_height)-min(prev_y_height, this_y_height)+1);
#endif

        prev_t = t;
    }

    return 0;
}
/***********************************************/

The code is a bit rough, and there are many optimizations it still does
not contain, and many assumptions that may prove incorrect in the future
it makes. It still run pretty fast on my Pentium III 600, ML8.1 machine,
at least for the number of pixels I tried.

In any case, it took me time to make the effect fast enough. What turned
out to hold me back was the fact that SDL cannot effectively UpdateRect a
very large rectangle (a 640*480 pixel one in my case), or a large number
of small rectangles each with its own call to UpdateRect. What I did found
out can be done, is to call SDL_UpdateRects with a large number of small
rectangles and this seems to be fast enough.

The algorithm for displaying the graph is this:

Assume a matrix of points in the coordinate O + A * x + B * Y where O is
the origin vector and A and B are two vectors. Each point osscilates with
a phase of p1*x+p2*y+t where p1 and p2 are two phases and t is the time
constant. If we multiply the phase by a vector and add it to the
corresponding (x,y) point vector, we'll get the flag-like effect.

At the moment A*x+B*y and p1*x+p2*y are calculated for each point using
multiplication, although it can be calculated from (x-1,y) by adding A and
p1 respectively. I'm not through optimizing this demo, so relax.

While we can turn it into another cross-language case study, I believe
what makes this intersting is the various optimization that can be applied
to the algorithm to generate the flag at the various stages. This is
independant of the language that is used, and C is a better choice than
most.

Regards,

	Shlomi Fish

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"