Zero winding vs. even odd rule

For our scanfill algorithm, we have used the even odd rule which is appropriate for most polygons and easy to implement. However, PostScript and also SVG use the zero winding rule.

What is the difference. On a scan line, each crossing switches on and off with the even odd rule. With the zero winding rule, the direction of the crossing matters. If it the line goes up, 1 is added, if it goes down, 1 is substracted. Painting is on whenever the sum is not zero.

Both rules behave the same for a single convex polygon. If a path goes up, it must go down later when the path is closed.

However, with complex and multiple polygons, the paths are more expressive. With the zero-winding you can both paint over or cut out, depending on the direction. For a letter O, you make an outside circle in one direction and an inside circle in the other direction. We probably can also simplify the stroke algorithm which had problem with the even odd rule.

Can we modify the scanfill algorithm to enable the zero-winding rule? The algorithm uses an array of crossings for each line which is sorted numerically. Adding direction would create a second dimension to each crossing, which makes it more complicated to sort. But we can do a trick. Currently, we use real numbers for the crossings. We do not need the fractiona for the pixel. We can round down the values and then add 0.5 if it for crossing that go up. This will not interfere with sort and allow us to sort and both detect the direction.

Javascript Editor

scanFill = function (path, width, height, color, data) {
   const crossings = []; 
   const oversampling = Math.sqrt(data.length / width / height / 4); 
   const width2 = width * oversampling;
   const height2 = height * oversampling;
   for (let line of path) {
      var [type, x0, y0, x1, y1] = line;
      x0 *= oversampling;
      y0 *= oversampling;
      x1 *= oversampling;
      y1 *= oversampling;
      const dx = x1 - x0;
      const dy = y1 - y0;
      const up = (dy > 0) ? 0.5 : 0.0;
      if (dy) {
          if (y1 < y0) { 
              [y0, y1] = [y1, y0];
              [x0, x1] = [x1, x0];
          }
          const ex = dx / dy;
          const y0c = Math.ceil(y0);
          x = (x0 + ex * (y0c - y0));
          for (let y = y0c; y < y1; y++) {
              if (y >= 0 && y < height2) {
                 if (! crossings[y] ) crossings[y] = [];
                 crossings[y].push(Math.floor(x) + up);
              }
              x += ex;
          }
       }
    }

for (let y in crossings) {
       const arr = crossings[y];
       arr.sort(function (a, b) { return a - b; }); 
       var odd = 0;
       for (let i = 0; i < arr.length - 1; i++) {
          if (zerowind) {
              let up = 2 * (arr[i] - Math.floor(arr[i]));
              odd += up ? 1 : -1;
          } else {
              odd = 1 - odd;
          }
          if (odd) { 
          var xstart = Math.floor(arr[i]);
          var xend = Math.floor(arr[i + 1]);
          var offset = ((height2 - 1 - y) * width2 + xstart) * 4;
          for (let j = xstart; j < xend; j++) {
              // we must check bounds 0 <= j < width2
              if (j >= 0 && j < width2) {                 
                  // Da = C1a + C2a * (1 - C1a) 
                  const da = color[3]/255.0 + data[offset + 3]/255.0 * (1 -  color[3]/255.0);      
                  for (let c = 0; c < 3; c++) {
                      // D = C1 * C1a + C2 * C2a * (1 - C1a)
                      data[offset + c] = color[c] * color[3]/255.0 + data[offset + c] * data[offset + 3] / 255.0 * (1 - color[3]/255.0)  ;
                      if (da) data[offset + c] /= da;
                  }
                  data[offset + 3] = 255.0 * da;
              }
              offset += 4;
          }
          }
       } 
    }

return data;

};

We use here a global variable as switch to test the algorithm

Javascript Editor

And paint a pentagrams as well as two pairs of overlapping squares both in same and opposite direction.

Javascript Editor

This needed only minimal intervention. How are we going to implement it?
PostScript proposes eofill as alternate operator so we can switch both ways. SVG has an option for even odd, as well as Canvas. We can use the zerowind rule also to do the stroke algorithm the old way. We do this in the next chapter.

My Journey to PostScript