Crow's alg

CS 248: Introduction to Computer Graphics

Pat Hanrahan

The following is the corrected version of Crow's algorithm as it appeared in the lecture slides. Use this only as an aid in understandin the algorithm -- make sure you know what it does conceptually.


scany(vert v[], int n, int bot)
  li = ri = bot
  ly = ry = y = ceil(v[bot].y);
  for( rem=n ; rem > 0 ; ) {
    while( ly<=y && rem-->0 ) {
      i = li; li = mod(li-1,n); ly=ceil(v[li].y);
      if( ly > y )
        differencey(&v[i],&v[li],&l,&dl,y);
    }
    while( ry<=y && rem-->0 ) {
      i = ri; ri = mod(ri+1,n); ry=ceil(v[ri].y);
      if( ry > y )
        differencey(&v[i],&v[ri],&r,&dr,y);
    }
    for( ; y < ly && y < ry ; y++ ) {
      scanx(&l,&r,y);
      incrementy(&l,&dl);
      incrementy(&f,&dr);
    }


scanx(vert *l, vert *r, int y)
  lx = ceil(l->x);
  rx = ceil(r->x);
  if( lx < rx ) {
    differencex( l, r, &s, &ds, lx );
    for( x=lx ; x<rx ; x++) {
      point(x,y);
      incrementx(&s,&ds);
    }
  }

In these next two functions, s and ds represent some quantity that you are interpolating. The goal is that these functions set up the differences that the increment functions below will use to update the variables.

 

differencex(vert *l, vert *r, vert *s, vert *ds, int x)
  ds->v = (r->v - l->v) / (r->x - l->x);
   s->v = l->v + (x - l->x) * ds->v;


differencey(vert *b, vert *t, vert *s, vert *ds, int y)
  ds->v = (t->v - b->v) / (t->y - b->y);
   s->v = b->v + (y - b->y) * ds->v;


incrementx(vert *e, vert *de)
  e->v += de->v


incrementy(vert *e, vert *de)
  e->x += de->x
  e->v += de->v

hanrahan@cs.stanford.edu