The Allegro Wiki is migrating to github at https://github.com/liballeg/allegro_wiki/wiki

NewAPI/Primitives/al draw line/Diamond Exit Rule

From Allegro Wiki
Jump to: navigation, search

The diamond exit rule is described nicely here: OpenGL spec.

A nice picture is here: pic.

The rule seems to be okay, except for a few degenerate cases. In these cases to adjoining lines will produce an overdraw (both lines will draw the same pixel) or a gap (both fail to draw a pixel between them). Lines don't need to be weirdly angled for this, both cases can use nearly parallel lines. Here are some illustrations:

Diamond cases.png

In the gap case, neither line intersects the diamond (I don't know if this is true, since the surrounding pixels should be hit). In the overdraw case, both intersect the diamond. These cases are very common in practice, meaning that diamond exit rule is a terrible rule if one wants to prevent those two faults. Nonetheless here's an implementation of a line drawer that respects this rule:

<highlightSyntax language="c"> static void line_stepper(uintptr_t state, shader_first first, shader_step step, shader_draw draw, ALLEGRO_VERTEX* vtx1, ALLEGRO_VERTEX* vtx2) {

  float x1, y1, x2, y2;
  float dx, dy;
  int end_x, end_y;
  float cx1, cy1, cx2, cy2;
  int in_diamond1, in_diamond2;
  int draw_first, draw_last;
  float num, denom, num2;
  x1 = vtx1->x;
  y1 = vtx1->y;
  x2 = vtx2->x;
  y2 = vtx2->y;  
  dx = x2 - x1;
  dy = y2 - y1;
  x1 -= 0.500001f;
  y1 -= 0.500001f;
  x2 -= 0.500001f;
  y2 -= 0.500001f; 
  cx1 = floorf(x1 + 0.5f);
  cy1 = floorf(y1 + 0.5f);
  cx2 = floorf(x2 + 0.5f);
  cy2 = floorf(y2 + 0.5f);
  in_diamond1 = (fabs(x1 - cx1) + fabs(y1 - cy1) <= 0.5f) ? 1 : 0;
  in_diamond2 = (fabs(x2 - cx2) + fabs(y2 - cy2) <= 0.5f) ? 1 : 0;
  #define COMPUTE_SIDE(xsign, ysign, vtxsign, vtxn)                                         \
  denom = vtxsign (xsign (dy)) + vtxsign (ysign (dx));                                      \
  num = vtxsign (ysign (dx)) + cpart;                                                       \
  num2 = xsign (ysign 0.5 - (y ## vtxn - cy ## vtxn)) - (ysign (x ## vtxn - cx ## vtxn ));
  /* Need to manually check whether we exit the diamond for at least one end */
  if(!in_diamond1) {
     /* Compute the hard intersection of the first diamond */
     const float cpart = (dy * (x1 - cx1) - dx * (y1 - cy1)) * 2;
     COMPUTE_SIDE(+, +, +, 1);
     if(denom != 0) {
        num /= denom;
        num2 /= denom;
        if(num >= 0 && num <= 1 && num2 >= 0 && num2 <= 1) {
           draw_first = 1;
           goto exit1;
        }
     }
     COMPUTE_SIDE(+, -, +, 1);
     if(denom != 0) {
        num /= denom;
        num2 /= denom;
        if(num >= 0 && num <= 1 && num2 >= 0 && num2 <= 1) {
           draw_first = 1;
           goto exit1;
        }
     }
     COMPUTE_SIDE(-, +, +, 1);
     if(denom != 0) {
        num /= denom;
        num2 /= denom;
        if(num >= 0 && num <= 1 && num2 >= 0 && num2 <= 1) {
           draw_first = 1;
           goto exit1;
        }
     }
     COMPUTE_SIDE(-, -, +, 1);
     if(denom != 0) {
        num /= denom;
        num2 /= denom;
        if(num >= 0 && num <= 1 && num2 >= 0 && num2 <= 1) {
           draw_first = 1;
           goto exit1;
        }
     }
     draw_first = 0;

exit1:;

  } else {
     draw_first = 1;
  }
  if(!in_diamond2) {
     /* Compute the hard intersection of the second diamond */
     const float cpart = -(dy * (x2 - cx2) - dx * (y2 - cy2)) * 2;
     COMPUTE_SIDE(+, +, -, 2);
     if(denom != 0) {
        num /= denom;
        num2 /= denom;
        if(num >= 0 && num <= 1 && num2 >= 0 && num2 <= 1) {
           draw_last = 1;
           goto exit2;
        }
     }
     COMPUTE_SIDE(+, -, -, 2);
     if(denom != 0) {
        num /= denom;
        num2 /= denom;
        if(num >= 0 && num <= 1 && num2 >= 0 && num2 <= 1) {
           draw_last = 1;
           goto exit2;
        }
     }
     COMPUTE_SIDE(-, +, -, 2);
     if(denom != 0) {
        num /= denom;
        num2 /= denom;
        if(num >= 0 && num <= 1 && num2 >= 0 && num2 <= 1) {
           draw_last = 1;
           goto exit2;
        }
     }
     COMPUTE_SIDE(-, -, -, 2);
     if(denom != 0) {
        num /= denom;
        num2 /= denom;
        if(num >= 0 && num <= 1 && num2 >= 0 && num2 <= 1) {
           draw_last = 1;
           goto exit2;
        }
     }
     draw_last = 0;

exit2:;

  } else {
     draw_last = 0;
  }
  if (y2 < y1) {
     float t1;
     int t2;
     t1 = y1; y1 = y2; y2 = t1;
     t1 = x1; x1 = x2; x2 = t1;
     dx = -dx;
     dy = -dy;
     t2 = draw_first; draw_first = draw_last; draw_last = t2;
     end_x = (int)cx1;
     end_y = (int)cy1;
  } else {
     end_x = (int)cx2;
     end_y = (int)cy2;
  }


  1. define FIRST \
  first(state, x, y, vtx1, vtx2);                                         \
  if(draw_first)                                                          \
     draw(state, x, y);
  
  1. define STEP \
  step(state, minor);                                                     \
  draw(state, x, y);
  
  1. define LAST \
  step(state, minor);                                                     \
  if(draw_last)                                                           \
     draw(state, x, y);
  
  
  1. define WORKER(var1, var2, comp, dvar1, dvar2, derr1, derr2, func) \
  {                                                                       \
     int minor = 1;                                                       \
     if(err comp)                                                         \
     {                                                                    \
        var1 += dvar1;                                                    \
        err += derr1;                                                     \
        minor = 0;                                                        \
     }                                                                    \
     \
     func                                                                 \
     \
     var2 += dvar2;                                                       \
     err += derr2;                                                        \
  }
  
  if (dx > 0) {
     if (dx > dy) {
        int x = floorf(x1 + 0.5f);
        int y = floorf(y1);
        
        float err = (y1 - (float)y) * dx - (x1 - (float)x) * dy;
        
        if (x <= end_x) {
           WORKER(y, x, > 0.5f * dx, 1, 1, -dx, dy, FIRST)
        }
        
        while (x < end_x) {
           WORKER(y, x, > 0.5f * dx, 1, 1, -dx, dy, STEP)
        }
        
        if (x <= end_x) {
           WORKER(y, x, > 0.5f * dx, 1, 1, -dx, dy, LAST)
           
        }
     } else {
        int x = floorf(x1);
        int y = floorf(y1 + 0.5f);
        
        float err = (x1 - (float)x) * dy - (y1 - (float)y) * dx;
        
        if (y <= end_y) {
           WORKER(x, y, > 0.5f * dy, 1, 1, -dy, dx, FIRST)
        }
        
        while (y < end_y) {
           WORKER(x, y, > 0.5f * dy, 1, 1, -dy, dx, STEP)
        }
        
        if (y <= end_y) {
           WORKER(x, y, > 0.5f * dy, 1, 1, -dy, dx, LAST)
        }
     }
  } else {
     if (-dx > dy) {
        int x = floorf(x1 + 0.5f);
        int y = floorf(y1);
        
        float err = (y1 - (float)y) * dx - (x1 - (float)x) * dy;
        
        if (x >= end_x) {
           WORKER(y, x, <= 0.5f * dx, 1, -1, -dx, -dy, FIRST)
        }
        
        while (x > end_x) {
           WORKER(y, x, <= 0.5f * dx, 1, -1, -dx, -dy, STEP)
        }
        
        if (x >= end_x) {
           WORKER(y, x, <= 0.5f * dx, 1, -1, -dx, -dy, LAST)
        }
     } else {
        int x = floorf(x1);
        int y = floorf(y1 + 0.5f);
        
        float err = (x1 - (float)x) * dy - (y1 - (float)y) * dx;
        
        /*
        This is the only correction that needs to be made in the opposite direction of dy (or dx)
        */
        if (err > 0.5f * dy) {
           x += 1;
           err -= dy;
        }
        
        if (y <= end_y) {
           WORKER(x, y, <= -0.5f * dy, -1, 1, dy, dx, FIRST)
        }
        
        while (y < end_y) {
           WORKER(x, y, <= -0.5f * dy, -1, 1, dy, dx, STEP)
        }
        
        if (y <= end_y) {
           WORKER(x, y, <= -0.5f * dy, -1, 1, dy, dx, LAST)
        }
     }
  }
  1. undef FIRST
  2. undef LAST
  3. undef STEP
  4. undef WORKER

} </highlightSyntax>