Kragen's Blog Thing

Sat, 26 Jan 2008 · A better recommendation system, and a "network" view that's less

#include <libart_lgpl/libart.h>
#include <SDL/SDL.h>
#include <sys/time.h>
#include <time.h>
#include <stdio.h>
#include <math.h>
// Makes pretty self-intersecting polygon shapes with libart and SDL.
// to compile: make libarthello CFLAGS="-Wall -g $(libart2-config --cflags) -O5" LDFLAGS="-lSDL $(libart2-config --libs)"

// Me trying to figure out how to use libart.  Somehow there is no
// documentation for it, and the header files, while generally
// adequate, lack any kind of overview.  It turns out there is a
// reasonable tutorial from 2001 online, and with some Makefile
// hacking it compiles and works (you want pkg-config ... gtk+-2.0
// libart-2.0 these days instead of gnome-config ... libart gtk).

// So here's the 400-word overview I wished I had when I started
// writing this program.

// libart supports a lot of different objects, but the most important
// ones are:
// - sorted vector paths or SVPs (art_svp.h --- ArtSVP, ArtSVPSeg)
//   which are made out of points (art_point.h --- ArtPoint).  Usually
//   you make them from ArtVpaths (see below).  Each SVP is one or
//   more segments, each of which is one (two?) or more points either
//   ascending or descending in Y.  The area it encloses is supposed
//   to be filled, so the whole SVP is supposed to be a closed path.
//   There are union, intersect, diff, and minus operations defined on
//   them in art_svp_ops.h, and an operation to tell if a point is
//   inside one in art_svp_point.h.
// - vector paths (art_vpath.h --- ArtVpath) which can be turned into
//   SVPs with art_svp_from_vpath or stroked into SVPs with
//   art_svp_vpath_stroke and art_svp_vpath_stroke_raw.  You can
//   create them point by point by hand, as is done in this program.
// - Bézier paths (art_bpath.h --- ArtBpath)
//   - which use ArtPathcodes (art_pathcode.h --- ART_MOVETO,
//     ART_LINETO, ART_CURVETO, etc.) so presumably they don't have to
//     be made of Bézier curves.
//   You can turn these into ArtVpaths with art_bez_path_to_vec.
// - pixel buffers of 8-bit-per-channel RGB or RGBA pixels.  There's
//   an ArtPixBuf object defined in art_pixbuf.h for these, but
//   basically everything just uses art_u8* arguments with some extra
//   metadata nearby.  The "pitch" or "rowstride" attribute associated
//   with these tells how many bytes to add to the address of one
//   pixel to get the next pixel down.
// - pixel values.  These may be represented as three or four separate
//   art_u8 arguments (R, G, B, and maybe alpha) or as a single
//   art_u32 or int argument ((R << 24) | (G << 16) | (B << 8) | A, or
//   (R << 16) | (G << 8) | B)
// There are also microtile arrays, which are kind of like super
// bounding boxes, affine transforms in 2-D, rectangles, gradients,
// image sources, alphagamma tables (you can generally use NULL
// instead), antialiased SVP rendering iterators, and so on.  But
// those are less important than SVPs, vector paths, Bézier paths,
// pixel buffers, and pixel values.

// Oh, and SVPs and Vpaths are supposed to go counterclockwise when
// they're enclosing a space.  Not clockwise.

#define WIDTH 512
#define HEIGHT 384

// Returns the number of seconds since 1969.
double getnow() {
  struct timeval now;
  gettimeofday(&now, 0);
  return now.tv_sec + now.tv_usec / 1000000.0;
}

// Set a point in an ArtVpath.
void set_point(ArtVpath *v, ArtPathcode code, double x, double y) {
  v->code = code;
  v->x = x;
  v->y = y;
}

// Dump the contents of a fucking SVP.
void dump_fucking_svp(ArtSVP *svp, FILE *fd) {
  fprintf(fd, "fucking svp at 0x%.8x {\n", (unsigned int)svp);
  fprintf(fd, "  %d fucking segments\n", svp->n_segs);
  int ii, jj;
  for (ii = 0; ii < svp->n_segs; ii++) {
    struct _ArtSVPSeg *seg = &svp->segs[ii];
    fprintf(fd, "  %d points %s (%g, %g) - (%g, %g) {\n", seg->n_points, 
            seg->dir ? "down" : "up", seg->bbox.x0, seg->bbox.y0,
            seg->bbox.x1, seg->bbox.y1);
    for (jj = 0; jj < seg->n_points; jj++) {
      fprintf(fd, "    (%g, %g)\n", seg->points[jj].x, seg->points[jj].y);
    }
    fprintf(fd, "  }\n");
  }
  fprintf(fd, "}\n");
}

// a callback for art_svp_render_aa that merely dumps out the values
// passed.
void dump_callback(void *callback_data, int y, int start, 
                    ArtSVPRenderAAStep *steps, int n_steps) {
  printf("y=%d start=%g n_steps=%d\n", y, start/65536.0, n_steps);
  int ii;
  for (ii = 0; ii < n_steps; ii++) {
    printf("  x=%d delta=%g\n", steps[ii].x, steps[ii].delta / 65536.0);
  }
}

// Render an antialiased polygon from an SVP with the simple dumb
// approach.  I'm surprised I can't find a function already in libart
// for this.

struct alpha_blending_shape_info {
  art_u8 *buffer;
  art_u8 r, g, b;  /* foreground! */
  int x0, x1;
  int rowstride;
  enum { even_odd_rule, art_rgb_svp_alpha_rule, interesting_rule } rule;
};

// callback for art_svp_render_aa for the antialiased polygon rendering
void alpha_blending_shape_callback(void *callback_data, int y, int start,
                                   ArtSVPRenderAAStep *steps, int n_steps) {
  struct alpha_blending_shape_info *info = callback_data;
  int value = start;
  int x = info->x0;
  int ii = 0;
  int new_x, alpha;
  for (;;) { // N + 1 fills for N steps
    new_x = (ii < n_steps) ? steps[ii].x : info->x1;
    switch (info->rule) {
    case even_odd_rule:
      alpha = 256 - abs((((unsigned)value >> 16) % 512) - 256);
      break;
    case art_rgb_svp_alpha_rule:
      // same coloring rule as art_rgb_svp_alpha, but with
      // antialiasing for both clockwise and counterclockwise borders.
      // if I were literate I would probably know what this coloring
      // rule is called.
      alpha = abs(value >> 16);
      if (alpha > 255) alpha = 255;
      break;
    case interesting_rule:
      // This shows more clearly what's going on under the covers with
      // value, and it's interesting to watch, but it isn't all that
      // pretty.
      alpha = value >> 18;
      break;
    default: abort();
    }
    if (alpha) {
      art_rgb_run_alpha(info->buffer + y * info->rowstride + x * 3, 
                        info->r, info->g, info->b, alpha, new_x - x);
    }
  if (ii >= n_steps) break;
    x = new_x;
    value += steps[ii].delta;
    ii++;
  }
}

// reimplementation of art_svp_render_aa to check my understanding of
// the interface; wish I had libart source handy
void svp_render_aa(ArtSVP *svp, 
                   int x0, int y0, int x1, int y1,
                   void (*callback) (void *callback_data,
                                     int y,
                                     int start,
                                     ArtSVPRenderAAStep *steps, int n_steps),
                   void *callback_data) {
  ArtSVPRenderAAIter *iter = art_svp_render_aa_iter(svp, x0, y0, x1, y1);
  int y;
  int start;
  ArtSVPRenderAAStep *steps;
  int n_steps;
  for (y = y0; y < y1; y++) {
    art_svp_render_aa_iter_step(iter, &start, &steps, &n_steps);
    callback(callback_data, y, start, steps, n_steps);
  }
  art_svp_render_aa_iter_done(iter);
}

void blit(SDL_Surface *src, SDL_Surface *dest) {
  SDL_BlitSurface(src, NULL, dest, NULL);
}

// gets called every frame to redraw the screen
void redraw_world(SDL_Surface *screen, int npoints, double d_theta) {
  int cx = WIDTH/2, cy = HEIGHT/2, r = HEIGHT/2, ii;
  double cos_d_theta = cos(d_theta), sin_d_theta = sin(d_theta);
  double cos_theta = 1, sin_theta = 0;

  ArtVpath *vec = art_new(ArtVpath, npoints+2);
  for (ii = 0; ii < npoints; ii++) {
    set_point(&vec[ii], (ii == 0) ? ART_MOVETO : ART_LINETO, 
              cx + r * sin_theta, cy - r * cos_theta);
    // avoid too many transcendental functions during screen redraws
    double nc = cos_theta * cos_d_theta - sin_theta * sin_d_theta;
    sin_theta = sin_theta * cos_d_theta + cos_theta * sin_d_theta;
    cos_theta = nc;
  }
  set_point(&vec[ii], ART_LINETO, vec[0].x, vec[0].y);
  set_point(&vec[ii+1], ART_END, 0, 0);
  ArtSVP *svp = art_svp_from_vpath(vec);
  art_free(vec);
  //dump_fucking_svp(svp, stderr);

  art_u8 *buffer = art_new(art_u8, WIDTH*HEIGHT*3);
  // set buffer to all black
  art_rgb_fill_run(buffer, 0, 0, 0, WIDTH*HEIGHT);

  // draw shape.

  // I thought this was the non-antialiased version for a long time,
  // so I commented it out.  (art_rgb_svp_aa does not do at all what
  // you would expect; it strokes the SVP instead of filling it.)  It
  // turns out that art_rgb_svp_alpha does actually do antialiasing,
  // but only if your SVP goes counterclockwise.  For clockwise SVPs
  // or parts of SVPs, it fails to antialias.

  //dump_fucking_svp(svp, stderr);

  /*
  art_rgb_svp_alpha(svp,
                    0, 0, WIDTH, HEIGHT, // x0 y0 x1 y1
                    0xff4040ff, // fg_color
                    buffer, WIDTH*3,
                    NULL // ArtAlphaGamma *alphagamma
                    );
  */

  struct alpha_blending_shape_info info;
  info.buffer = buffer;
  info.r = 255;
  info.g = info.b = 64;
  info.x0 = 0;
  info.x1 = WIDTH;
  info.rowstride = WIDTH * 3;
  info.rule = even_odd_rule;

  svp_render_aa(svp,
                // int x0, int y0, int x1, int y1,
                0, 0, WIDTH, HEIGHT,
                alpha_blending_shape_callback,
                &info);

  // now somehow we have to get this buffer onto the screen
  SDL_Surface *bufsurf = SDL_CreateRGBSurfaceFrom(
      buffer, WIDTH, HEIGHT, /*depth*/24,
      WIDTH*3,  /* length of each scanline in bytes */
      0x0000ff, /* red mask XXX little-endian */
      0x00ff00, /* green mask */
      0xff0000, /* blue mask */
      0); /* alpha mask */
  blit(bufsurf, screen);
  SDL_FreeSurface(bufsurf);
  art_free(buffer);
  art_svp_free(svp);
}

void flip(SDL_Surface *screen) {
  // introduced in a failed attempt to persuade gprof to account for
  // SDL_Flip separately
  SDL_Flip(screen);
}

// Notes on speed, because this is dramatically slower than the
// non-antialiased version I wrote in half an hour in Python.

// In 1024x768:
// With the whole thing, I get 6.8 7.0 7.0 fps (143ms)
// With flip, blit, svp_render_aa, and clearing the buffer commented
// out, I get 13.1kfps 13.7kfps 12.2kfps (76 us).
// With just flip uncommented, I get 28 27 27 fps (37ms).
// With just blit uncommented, I get 11.9 11.7 12.6 fps (84ms).
// With just svp_render_aa uncommented, I get 77 68 65 fps (15ms).
//   all but 2ms of which is inside the call to art_rgb_run_alpha
// With just clearing the buffer uncommented, I get 63 72 72 fps (14ms).
// 37ms + 84ms + 15ms + 14ms = 150ms, which is about right.
// So, how could this be sped up?

// Presumably the "flip" is actually a blit (I've seen tearing, so I
// don't think it's actually page-flipping at the vertical refresh),
// and maybe it's so much faster than the other blit because it
// doesn't have to convert pixel formats.  The extra blit could be
// avoided by working directly in the screen buffer, in the right
// pixel format; nothing in the art_svp_render_aa_* interface has
// anything to do with pixel buffers or pixel formats.  (My display is
// 16 bits deep.)  That's entirely the job of the callback.

// Now, most of the pixels drawn (for opaque polygons --- assuming
// you're not using interesting_rule) are either entirely transparent
// or entirely opaque, and those two cases don't actually require any
// alpha-blending; but the pixels along the edges need a bit of bit
// twiddling and multiplication to look right.  But there are few
// enough of them that this ought to be OK.

// So probably the cost of "flip" is unavoidable if we're going to use
// SDL (and not get hardware double-buffering working), and it's
// likely that most of the cost of svp_render_aa is unavoidable too
// --- I doubt Raph's implementation of art_rgb_run_alpha is
// detectably suboptimal.  (Maybe it'll be a little faster if it only
// has to touch two thirds as much data.)  That suggests that the best
// we can do is probably about 37ms + (2/3) * 14ms + (2/3) * 15ms =
// 56ms, or about 18fps.  The weird part about this is that the
// non-antialiased Python version, using pygame.draw.polygon, runs at
// 22fps, which is 45ms per frame.  So it's only using 7ms to clear
// the screen and render the polygon, I guess?

int main(int argc, char **argv) {
  double d_d_theta = M_PI / 70;
  double d_theta = 0;
  int npoints = 3;
  SDL_Init(SDL_INIT_EVERYTHING);
  SDL_Surface *screen = SDL_SetVideoMode(WIDTH, HEIGHT, 0, SDL_FULLSCREEN);
  double start = getnow();
  int frames = 0;
  for (;;) {
    SDL_Event ev;
    int events = SDL_PollEvent(&ev);
    if (events) {
      if (ev.type == SDL_MOUSEBUTTONDOWN || ev.type == SDL_QUIT) break;
    } else {
      redraw_world(screen, npoints, d_theta);
      flip(screen);
      frames++;
      d_theta += d_d_theta / npoints;
      if (d_theta > 2*M_PI) {
        d_theta -= 2*M_PI;
        npoints++;
      }
    }
  }
  double end = getnow();
  SDL_Quit();
  printf("%.2f seconds, %.2f fps\n", end - start, frames / (end - start));
  return 0;
}

←January →
Sun	Mon	Tue	Wed	Thu	Fri	Sat
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31