diff options
Diffstat (limited to 'doc/developer/reference-html/x1734.html')
| -rw-r--r-- | doc/developer/reference-html/x1734.html | 1922 |
1 files changed, 1922 insertions, 0 deletions
diff --git a/doc/developer/reference-html/x1734.html b/doc/developer/reference-html/x1734.html new file mode 100644 index 0000000..8c52bfd --- /dev/null +++ b/doc/developer/reference-html/x1734.html @@ -0,0 +1,1922 @@ +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN""http://www.w3.org/TR/html4/loose.dtd"> +<HTML +><HEAD +><TITLE +>Weaving algorithms</TITLE +><META +NAME="GENERATOR" +CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK +REL="HOME" +TITLE="The Developer's Guide to Gutenprint" +HREF="index.html"><LINK +REL="UP" +TITLE="Weaving for inkjet printers" +HREF="c1717.html"><LINK +REL="PREVIOUS" +TITLE="Weaving for inkjet printers" +HREF="c1717.html"><LINK +REL="NEXT" +TITLE="Dithering" +HREF="c1968.html"></HEAD +><BODY +CLASS="sect1" +BGCOLOR="#FFFFFF" +TEXT="#000000" +LINK="#0000FF" +VLINK="#840084" +ALINK="#0000FF" +><DIV +CLASS="NAVHEADER" +><TABLE +SUMMARY="Header navigation table" +WIDTH="100%" +BORDER="0" +CELLPADDING="0" +CELLSPACING="0" +><TR +><TH +COLSPAN="3" +ALIGN="center" +>The Developer's Guide to Gutenprint</TH +></TR +><TR +><TD +WIDTH="10%" +ALIGN="left" +VALIGN="bottom" +><A +HREF="c1717.html" +ACCESSKEY="P" +>Prev</A +></TD +><TD +WIDTH="80%" +ALIGN="center" +VALIGN="bottom" +>Chapter 6. Weaving for inkjet printers</TD +><TD +WIDTH="10%" +ALIGN="right" +VALIGN="bottom" +><A +HREF="c1968.html" +ACCESSKEY="N" +>Next</A +></TD +></TR +></TABLE +><HR +ALIGN="LEFT" +WIDTH="100%"></DIV +><DIV +CLASS="sect1" +><H1 +CLASS="sect1" +><A +NAME="AEN1734" +>6.2. Weaving algorithms</A +></H1 +><P +> I considered a few algorithms to perform the weave. The first + one I devised let me use only (jets − + distance_between_jets + 1) nozzles, or 25. This is OK in + principle, but it's slower than using all nozzles. By playing + around with it some more, I came up with an algorithm that lets + me use all of the nozzles, except near the top and bottom of the + page. + </P +><P +> This still produces some banding, though. Even better quality + can be achieved by using multiple nozzles on the same line. How + do we do this? In 1440×720 mode, we're printing two + output lines at the same vertical position. However, if we want + four passes, we have to effectively print each line twice. + Actually doing this would increase the density, so what we do is + print half the dots on each pass. This produces near-perfect + output, and it's far faster than using (pseudo) + “MicroWeave”. + </P +><P +> Yet another complication is how to get near the top and bottom + of the page. This algorithm lets us print to within one head + width of the top of the page, and a bit more than one head width + from the bottom. That leaves a lot of blank space. Doing the + weave properly outside of this region is increasingly difficult + as we get closer to the edge of the paper; in the interior + region, any nozzle can print any line, but near the top and + bottom edges, only some nozzles can print. We originally + handled this by using the naive way mentioned above near the + borders, and switching over to the high quality method in the + interior. Unfortunately, this meant that the quality is quite + visibly degraded near the top and bottom of the page. We have + since devised better algorithms that allow printing to the + extreme top and bottom of the region that can physically be + printed, with only minimal loss of quality. + </P +><P +> Epson does not advertise that the printers can print at the very + top of the page, although in practice most of them can. The + quality is degraded to some degree, and we have observed that in + some cases not all of the dots get printed. Epson may have + decided that the degradation in quality is sufficient that + printing in that region should not be allowed. That is a valid + decision, although we have taken another approach. + </P +><DIV +CLASS="sect2" +><H2 +CLASS="sect2" +><A +NAME="AEN1740" +>6.2.1. Simple weaving algorithms</A +></H2 +><P +> The initial problem is to calculate the starting position of + each pass; the row number of the printer's top jet when + printing that pass. Since we assume the paper cannot be + reverse-fed, the print head must, for each pass, start + either further down the page than the previous pass or at + the same position. Each pass's start point is therefore at + a non-negative offset from the previous pass's start point. + </P +><P +> Once we have a formula for the starting row of each pass, we + then turn that “inside out” to get a formula for + the pass number containing each row. + </P +><P +> First, let's define how our printer works. We measure + vertical position on the paper in “rows”; the + resolution with which the printer can position the paper + vertically. The print head contains J ink jets, which are + spaced S rows apart. + </P +><P +> Consider a very simple case: we want to print a page as + quickly as possible, and we mostly don't care how sparse the + printing is, so long as it's fairly even. + </P +><P +> It's pretty obvious how to do this. We make one pass with + the print head, printing J lines of data, each line S rows + after the previous one. We then advance the paper by S + × J rows and print the next row. For example, if J = + 7 and S = 4, this method can be illustrated like this: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1747" +></A +><PRE +CLASS="screen" +>pass number +| row number-------> +| | 111111111122222222223333333333444444444455555555556666666666 +| 0123456789012345678901234567890123456789012345678901234567890123456789 +0 *---*---*---*---*---*---* +1 *---*---*---*---*---*---* +2 \-----------------------/ *---*---*---*---*---*- + 7 jets \---/ + 4 rows offset from one jet to the next +\---------------------------/ + 7*4=28 rows offset from one pass to the next</PRE +><P +></P +></DIV +><P +> In these examples, the vertical axis can be thought of as the + time axis, with the pass number shown at the left margin, + while the row number runs horizontally. A + <SAMP +CLASS="computeroutput" +>*</SAMP +> shows each row printed by a + pass, and a row of <SAMP +CLASS="computeroutput" +>-</SAMP +> is used + to link together the rows printed by one pass of the print + head. The first pass is numbered + <SAMP +CLASS="computeroutput" +>0</SAMP +> and starts at row 0. Each + subsequent pass p starts at row p × S × J. Each + pass prints J lines, each line being S rows after the previous + one. (For ease of viewing this file on a standard terminal, + I'm clipping the examples at column 80.) + </P +><P +> This method covers the whole page with lines printed evenly + S rows apart. However, we want to fill in all the other + rows with printing to get a full-density page (we're + ignoring oversampling at this stage). Where we have + previously printed a single pass, we'll now print a + “pass block”: we print extra passes to fill in + the empty rows. A naive implementation might look like + this: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1754" +></A +><PRE +CLASS="screen" +>0 *---*---*---*---*---*---* +1 *---*---*---*---*---*---* +2 *---*---*---*---*---*---* +3 *---*---*---*---*---*---* +4 *---*---*---*---*---*---* +5 *---*---*---*---*---*---* +6 *---*---*---*---*---*---* +7 *---*---*---*---*---*---* +8 *---*---*---*---*---*- +9 *---*---*---*---*---* +10 *---*---*---*---*--- +11 *---*---*---*---*--</PRE +><P +></P +></DIV +><P +> (Now you can see why this process is called + “weaving”!) + </P +></DIV +><DIV +CLASS="sect2" +><H2 +CLASS="sect2" +><A +NAME="AEN1757" +>6.2.2. Perfect weaving</A +></H2 +><P +> This simple weave pattern prints every row, but will give + conspicuous banding patterns for the reasons discussed + above. + </P +><P +> Let's start improving this for our simple case. We can + reduce banding by making sure that any given jet never + prints a row too close to another row printed by the same + jet. This means we want to space the rows printed by a + given jet evenly down the page. In turn, this implies we + want to advance the paper by as nearly an equal amount after + each pass as possible. + </P +><P +> Each pass block prints S × J lines in S passes. The + first line printed in each pass block is S × J rows + lower on the page than the first line printed in the + previous pass block. Therefore, if we advance the paper by + J rows between each pass, we can print the right number of + passes in each block and advance the paper perfectly evenly. + </P +><P +> Here's what this “perfect” weave looks like: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1763" +></A +><PRE +CLASS="screen" +> start of full weave + | +0 *---*---*---*---*---*---* +1 *---*---*---*---*---*---* +2 *---*---*---*---*---*---* +3 *---*---*---*---*---*---* +4 *---*---*---*---*---*---* +5 *---*---*---*---*---*---* +6 *---*---*---*---*---*---* +7 *---*---*---*---*---*---* +8 *---*---*---*---*---*- +9 *---*---*---*-- +10 *---*--- +11 *</PRE +><P +></P +></DIV +><P +> You'll notice that, for the first few rows, this weave is + too sparse. It is not until the row marked “start of + full weave” that every subsequent row is printed. We + can calculate this start position as follows: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1766" +></A +><PRE +CLASS="screen" +>start = (S − 1) × (J − 1)</PRE +><P +></P +></DIV +><P +> For the moment, we will ignore this problem with the weave. + We'll consider later how to fill in the missing rows. + </P +><P +> Let's look at a few more examples of perfect weaves: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1770" +></A +><P +> S = 2, J = 7, start = (2−1) × (7−1) = 6: + </P +><PRE +CLASS="screen" +> starting row of full weave + | +0 *-*-*-*-*-*-* +1 *-*-*-*-*-*-* +2 *-*-*-*-*-*-* +3 *-*-*-*-*-*-* +4 *-*-*-*-*-*-* +5 *-*-*-*-*-*-* +6 *-*-*-*-*-*-* +7 *-*-*-*-*-*-*</PRE +><P +></P +></DIV +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1773" +></A +><P +> S = 7, J = 2, start = 6: + </P +><PRE +CLASS="screen" +> start + | +0 *------* +1 *------* +2 *------* +3 *------* +4 *------* +5 *------* +6 *------* +7 *------* +8 *------* +9 *------*</PRE +><P +></P +></DIV +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1776" +></A +><P +> S = 4, J = 13, start = 36: + </P +><PRE +CLASS="screen" +> start + | +0 *---*---*---*---*---*---*---*---*---*---*---*---* +1 *---*---*---*---*---*---*---*---*---*---*---*---* +2 *---*---*---*---*---*---*---*---*---*---*---*---* +3 *---*---*---*---*---*---*---*---*---*-- +4 *---*---*---*---*---*---*- +5 *---*---*---*</PRE +><P +></P +></DIV +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1779" +></A +><P +> S = 13, J = 4, start = 36: + </P +><PRE +CLASS="screen" +> start + | +0 *------------*------------*------------* +1 *------------*------------*------------* +2 *------------*------------*------------* +3 *------------*------------*------------* +4 *------------*------------*------------* +5 *------------*------------*------------* +6 *------------*------------*------------* +7 *------------*------------*------------* +8 *------------*------------*------------* +9 *------------*------------*------------* +10 *------------*------------*----------- +11 *------------*------------*------- +12 *------------*------------*--- +13 *------------*------------ +14 *------------*-------- +15 *------------*---- +16 *------------* +17 *--------- +18 *----- +19 *-</PRE +><P +></P +></DIV +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1782" +></A +><P +> S = 8, J = 5, start = 28: + </P +><PRE +CLASS="screen" +> start + | +0 *-------*-------*-------*-------* +1 *-------*-------*-------*-------* +2 *-------*-------*-------*-------* +3 *-------*-------*-------*-------* +4 *-------*-------*-------*-------* +5 *-------*-------*-------*-------* +6 *-------*-------*-------*-------* +7 *-------*-------*-------*-------* +8 *-------*-------*-------*-------* +9 *-------*-------*-------*-------* +10 *-------*-------*-------*--- +11 *-------*-------*------ +12 *-------*-------*- +13 *-------*---- +14 *------- +15 *--</PRE +><P +></P +></DIV +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1785" +></A +><P +> S = 9, J = 5, start = 32: + </P +><PRE +CLASS="screen" +> start + | +0 *--------*--------*--------*--------* +1 *--------*--------*--------*--------* +2 *--------*--------*--------*--------* +3 *--------*--------*--------*--------* +4 *--------*--------*--------*--------* +5 *--------*--------*--------*--------* +6 *--------*--------*--------*--------* +7 *--------*--------*--------*--------* +8 *--------*--------*--------*--------* +9 *--------*--------*--------*----- +10 *--------*--------*--------* +11 *--------*--------*---- +12 *--------*-------- +13 *--------*--- +14 *------- +15 *--</PRE +><P +></P +></DIV +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1788" +></A +><P +> S = 6, J = 7, start = 30: + </P +><PRE +CLASS="screen" +> start + | +0 *-----*-----*-----*-----*-----*-----* +1 *-----*-----*-----*-----*-----*-----* +2 *-----*-----*-----*-----*-----*-----* +3 *-----*-----*-----*-----*-----*-----* +4 *-----*-----*-----*-----*-----*-----* +5 *-----*-----*-----*-----*-----*-----* +6 *-----*-----*-----*-----*-----*----- +7 *-----*-----*-----*-----*---- +8 *-----*-----*-----*--- +9 *-----*-----*-- +10 *-----*- +11 *</PRE +><P +></P +></DIV +></DIV +><DIV +CLASS="sect2" +><H2 +CLASS="sect2" +><A +NAME="AEN1791" +>6.2.3. Weaving collisions</A +></H2 +><P +> A perfect weave is not possible in all cases. Let's look at + another example: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1794" +></A +><P +> S = 6, J = 4: + </P +><PRE +CLASS="screen" +>0 *-----*-----*-----* +1 *-----*-----*-----* +2 *-----*-----*-----* +3 *-----*-----*-----* +4 ^ *-^---*-----*-----* +5 | ^ | *-^---*-----*-----* + OUCH! ^ | ^ + | |</PRE +><P +></P +></DIV +><P +> Here we have a collision. Some lines printed in later + passes overprint lines printed by earlier passes. We can + see why by considering which row number is printed by a + given jet number j (numbered from 0) of a given pass, p: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1798" +></A +><PRE +CLASS="screen" +>row(p, j) = (p × J) + (j × S)</PRE +><P +></P +></DIV +><P +> Because J = 4 and S = 6 have a common factor of 2, jet 2 of + pass 0 prints the same row as jet 0 of pass 3: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1801" +></A +><PRE +CLASS="screen" +>row(0, 2) = (0 × 4) + (2 × 6) = 12 +row(3, 0) = (3 × 4) + (0 × 6) = 12</PRE +><P +></P +></DIV +><P +> In fact, with this particular weave pattern, jets 0 and 1 of + pass p + 3 always overprint jets 2 and 3 of pass p. We'll + represent overprinting rows by a + <SAMP +CLASS="computeroutput" +>^</SAMP +> in our diagrams, and + correct rows by <SAMP +CLASS="computeroutput" +>*</SAMP +>: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1806" +></A +><P +> S = 6, J = 4: + </P +><PRE +CLASS="screen" +>0 *-----*-----*-----* +1 *-----*-----*-----* +2 *-----*-----*-----* +3 ^-----^-----*-----* +4 ^-----^-----*-----* +5 ^-----^-----*-----*</PRE +><P +></P +></DIV +></DIV +><DIV +CLASS="sect2" +><H2 +CLASS="sect2" +><A +NAME="AEN1809" +>6.2.4. What makes a “perfect” weave?</A +></H2 +><P +> So what causes the perfect weave cases to be perfect, and + the other cases not to be? In all the perfect cases above, + S and J are relatively prime (i.e. their greatest common + divisor (GCD) is 1). As we mentioned above, S = 6 and J = 4 + have a common factor, which causes the overprinting. Where + S and J have a GCD of 1, they have no common factor other + than 1 and, as a result, no overprinting occurs. If S and J + are not relatively prime, their common factor will cause + overprinting. + </P +><P +> We can work out the greatest common divisor of a pair of + natural numbers using Euler's algorithm: + </P +><P +></P +><OL +TYPE="1" +><LI +><P +> Start with the two numbers: (e.g.) 9, 24 + </P +></LI +><LI +><P +> Swap them if necessary so that the larger one comes + first: 24, 9 + </P +></LI +><LI +><P +> Subtract the second number from the first: 15, 9 + </P +></LI +><LI +><P +> Repeat until the first number becomes smaller: 6, 9 + </P +></LI +><LI +><P +> Swap the numbers again, so the larger one comes first: + 9, 6 + </P +></LI +><LI +><P +> Subtract again: 3, 6 + </P +></LI +><LI +><P +> Swap: 6, 3 + </P +></LI +><LI +><P +> Subtract: 3, 3 + </P +></LI +><LI +><P +> And again: 0, 3 + </P +></LI +><LI +><P +> When one of the numbers becomes 0, the other number is + the GCD of the two numbers you started with. + </P +></LI +></OL +><P +> These repeated subtractions can be done with C's <TT +CLASS="literal" +>%</TT +> + operator, so we can write this in C as follows: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1836" +></A +><PRE +CLASS="programlisting" +>unsigned int +gcd(unsigned int x, unsigned int y) +{ + if (y == 0) + return x; + while (x != 0) { + if (y > x) + swap (&x, &y); + x %= y; + } + return y; +}</PRE +><P +></P +></DIV +><P +> <TT +CLASS="literal" +>gcd(S,J)</TT +> will feature quite prominently in our + weaving algorithm. + </P +><P +> If 0 ≤ j < J, there should only be a single pair (p, j) + for any given row number. If S and J are not relatively + prime, this assumption breaks down. (For conciseness, let G + = GCD(S,J).) + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1841" +></A +><P +> S = 8, J = 6, G = 2: + </P +><PRE +CLASS="screen" +>0 *-------*-------*-------*-------*-------* +1 *-------*-------*-------*-------*-------* +2 *-------*-------*-------*-------*-------* +3 *-------*-------*-------*-------*-------* +4 ^-------^-------^-------*-------*-------* +5 ^-------^-------^-------*-------*-------*</PRE +><P +></P +></DIV +><P +> In this case, jets 0, 1 and 2 of pass p + 4 collide with + jets 3, 4 and 5 of pass p. + </P +><P +> How can we calculate these numbers? Suppose we were to + print using fewer jets, say J / G jets. The greatest common + divisor of J / G and S is 1, enabling a perfect weave. But + to get a perfect weave, we also have to advance the paper by + a factor of G less: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1846" +></A +><PRE +CLASS="screen" +>0 *-------*-------* - - - +1 *-------*-------* - - - +2 *-------*-------* - - - +3 *-------*-------* - - - +4 *-------*-------* - - - +5 *-------*-------* - - -</PRE +><P +></P +></DIV +><P +> If we left the paper advance alone, we'd get a sparse weave; + only one row can be printed every G rows: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1849" +></A +><PRE +CLASS="screen" +>0 *-------*-------* - - - +1 *-------*-------* - - - +2 *-------*-------* - - - +3 *-------*-------* - - - +4 *-------*-------* - - - +5 *-------*-------* - - - + ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ + These rows need filling in.</PRE +><P +></P +></DIV +><P +> The rows that would have been printed by the jets we've now + omitted (shown as <SAMP +CLASS="computeroutput" +>-</SAMP +>) are + printed by other jets on later passes. + </P +><P +> Let's analyse this. Consider how a pass p could collide + with pass 0. Pass p starts at offset p × J. Pass 0 + prints at rows which are multiples of S. If p × J is + exactly divisible by S, a collision has occurred, unless (p + ×J) ≥ J × S (which will happen when we + finish a pass block). + </P +><P +> So, we want to find p and q such that p × J = q + × S and p is minimised. Then p is the number of rows + before a collision, and q is the number of jets in pass 0 + which are not involved in the collision. To do this, we + find the lowest common multiple of J and S, which is L = (J + × S) / G. L / J is the number of rows before a + collision, and L / S is the number of jets in the first pass + not involved in the collision. + </P +><P +> Thus, we see that the first J / G rows printed by a given + pass are not overprinted by any later pass. However, the + rest of the rows printed by pass p are overprinted by the + first J − (J / G) jets of pass p + (S / G). We will + use C to refer to S / G, the number of rows after which a + collision occurs. + </P +><P +> Another example: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1857" +></A +><P +> S = 6, J = 9, G = 3, C = S / G = 2: + </P +><PRE +CLASS="screen" +>0 *-----*-----*-----*-----*-----*-----*-----*-----* +1 *-----*-----*-----*-----*-----*-----*-----*-----* +2 ^-----^-----^-----^-----^-----^-----*-----*-----* +3 ^-----^-----^-----^-----^-----^-----*-----*-----* +4 ^-----^-----^-----^-----^-----^-----*----- +5 ^-----^-----^-----^-----^-----^-- + ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ + These rows need filling in.</PRE +><P +></P +></DIV +><P +> In this case, the first J − (J / G) = 9 − (9 / + 3) = 6 jets of pass p + (6 / 3) = p + 2 collide with the + last 6 jets of pass p. Only one row in every G = 2 rows is + printed by this weave. + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1861" +></A +><P +> S = 9, J = 6, G = 3, C = 3: + </P +><PRE +CLASS="screen" +> 0 *--------*--------*--------*--------*--------* +1 *--------*--------*--------*--------*--------* +2 *--------*--------*--------*--------*--------* +3 ^--------^--------^--------^--------*--------* +4 ^--------^--------^--------^--------*--------* +5 ^--------^--------^--------^--------*--------*</PRE +><P +> Here, the first J - (J / G) = 6 - (6 / 3) = 4 jets of pass + p + (9 / 3) = p + 3 collide with the last 4 jets of pass + p. + </P +><P +> Note that, in these overprinting cases, only rows + divisible by G are ever printed. The other rows, those + not divisible by G, are not touched by this weave. + </P +><P +> We can modify our weave pattern to avoid overprinting any + rows and simultaneously fill in the missing rows. Instead + of using J alone to determine the start of each pass from + the previous pass, we adjust the starting position of some + passes. As mentioned before, we will divide the page into + pass blocks, with S passes in each block. This ensures + that the first jet of the first pass in a block prints the + row which the Jth jet of the first pass of the previous + block would have printed, if the print head had one extra + jet. + </P +><P +> Looking back at an example of a perfect weave, we can + divide it into pass blocks: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1868" +></A +><P +> S = 7, J = 2, G = 1: + </P +><PRE +CLASS="screen" +> imaginary extra jet + | +0 *------* * <--start of pass block 0 +1 *------* | +2 *------* | +3 *------*| +4 *-----|* +5 *---|--* +6 *-|----* + | +7 *------* <--start of pass block 1 +8 *------* +9 *------*</PRE +><P +></P +></DIV +><P +> We can now calculate the start of a given pass by + reference to its pass block. The first pass of pass block + b always starts at row (b × S × J). The start + row of each of the other passes in the block are + calculated using offsets from this row. + </P +><P +> For the example above, there are 7 passes in each pass + block, and their offsets are 0, 2, 4, 6, 8, 10 and 12. + The next pass block is offset S × J = 14 rows from + the start of the current pass block. + </P +><P +> The simplest way to modify the “perfect” weave + pattern to give a correct weave in cases where G ≠ 1 + is to simply change any offsets which would result in a + collision, until the collision disappears. Every printed + row in the weave, as we have shown it up to now, is + separated from each of its neighbouring printed rows by G + blank rows. We will add an extra offset to each colliding + pass in such a way that we push the pass onto these + otherwise blank rows. + </P +><P +> We have seen that, unless G = 1, the plain weave pattern + results in each pass colliding with the pass S / G passes + before. We will now subdivide our pass block into + subblocks, each consisting of B = S / G passes. There are + therefore G subblocks in a pass block. + </P +><P +> For each subblock, the passes in that subblock have a + constant offset added to them. The offset is different + for each subblock in a block. There are many ways we can + choose the offsets, but the simplest is to make the offset + equal to the subblock number (starting from 0). + </P +><P +> Thus, the passes in the first subblock in each pass block + remain at the offsets we've already calculated from J. + The passes in the second subblock each have 1 added to + their offset, the passes in the third subblock have 2 + added, and so on. Thus, the offset of pass p (numbered + relative to the start of its pass block) is p × J + + floor(p / B). + </P +><P +> This gives us a weave pattern looking like this: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1878" +></A +><P +> S = 6, J = 9, G = 3, B = 2: + </P +><PRE +CLASS="screen" +>0 *-----*-----*-----*-----*-----*-----*-----*-----* +1 ^ *-----*-----*-----*-----*-----*-----*-----*-----* +2 | +-> *-----*-----*-----*-----*-----*-----*-----*-----* +3 | | *-----*-----*-----*-----*-----*-----*-----*-----* +4 | | +-> *-----*-----*-----*-----*-----*-----*--- +5 | | | *-----*-----*-----*-----*-----* +6 | | | +-> *-----*-----*-----*----- +7 | | | | *-----*-----*-- + | | | start of pass block 1 + | | | (offset returns to 0) + | | start of subblock 2 (offset 2 rows) + | start of subblock 1 (following passes offset by 1 row) +start of passblock 0, subblock 0 (pass start calculated as p*J)</PRE +><P +></P +></DIV +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1881" +></A +><P +> S = 9, J = 6, G = 3, B = 3: + </P +><PRE +CLASS="screen" +>0 *--------*--------*--------*--------*--------* +1 *--------*--------*--------*--------*--------* +2 *--------*--------*--------*--------*--------* +3 *--------*--------*--------*--------*--------* +4 *--------*--------*--------*--------*--------* +5 *--------*--------*--------*--------*--------* +6 *--------*--------*--------*--------*--- +7 *--------*--------*--------*------ +8 *--------*--------*--------* +9 *--------*--------*----- +10 \---/ *--------*-------- +11 small offset *--------*-- +12 *----</PRE +><P +></P +></DIV +><P +> This method of choosing offsets for subblocks can result + in an occasional small offset (as shown above) between one + pass and the next, particularly when G is large compared + to J. For example: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1885" +></A +><P +> S = 8, J = 4, G = 4, B = 2: + </P +><PRE +CLASS="screen" +>0 *-------*-------*-------* +1 *-------*-------*-------* +2 *-------*-------*-------* +3 *-------*-------*-------* +4 *-------*-------*-------* +5 *-------*-------*-------* +6 *-------*-------*-------* +7 *-------*-------*-------* +8 *-------*-------*-------* +9 \/ *-------*-------*-------* + very small offset!</PRE +><P +></P +></DIV +><P +> We can plot the offset against the subblock number as + follows: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1889" +></A +><PRE +CLASS="screen" +>subblock number +| offset +| | +| 0123 +0 * +1 * +2 * +3 * +0 * +1 * +2 * +3 *</PRE +><P +></P +></DIV +><P +> The discontinuity in this plot results in the small offset + between passes. + </P +><P +> As we said at the beginning, we want the offsets from each + pass to the next to be as similar as possible. We can fix + this by calculating the offset for a given subblock b as + follows: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1893" +></A +><PRE +CLASS="screen" +>offset(b) = 2*b , if b < ceiling(G/2) + = 2*(G-b)-1 , otherwise</PRE +><P +></P +></DIV +><P +> We can visualise this as follows, for G = 10: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1896" +></A +><PRE +CLASS="screen" +>0123456789 +0 * +1 * +2 * +3 * +4 * +5 * +6 * +7 * +8 * +9 * +0 * +1 * +2 * +3 * +4 * +5 * +6 * +7 * +8 * +9 *</PRE +><P +></P +></DIV +><P +> and for G = 11: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1899" +></A +><PRE +CLASS="screen" +> 1 + 01234567890 + 0 * + 1 * + 2 * + 3 * + 4 * + 5 * + 6 * + 7 * + 8 * + 9 * +10 * + 0 * + 1 * + 2 * + 3 * + 4 * + 5 * + 6 * + 7 * + 8 * + 9 * +10 *</PRE +><P +></P +></DIV +><P +> This gives a weave looking like this: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1902" +></A +><P +> S = 12, J = 6, G = 6, B = 2: + </P +><PRE +CLASS="screen" +>0 *-----------*-----------*-----------*-----------*-----------* +1 *-----------*-----------*-----------*-----------*-----------* +2 *-----------*-----------*-----------*-----------*-----------* +3 *-----------*-----------*-----------*-----------*--------- +4 *-----------*-----------*-----------*-----------*- +5 *-----------*-----------*-----------*------- +6 *-----------*-----------*-----------* +7 *-----------*-----------*------ +8 *-----------*-----------*-- +9 *-----------*-------- +10 *-----------*---- +11 *---------- +12 *-----</PRE +><P +></P +></DIV +><P +> This method ensures that the offset between passes is + always in the range [J - 2, J + 2]. + </P +><P +> (This might seem odd, but it occurs to me that a good + weave pattern might also make a good score for bell + ringers. When church bells are rung, a list of + “changes” are used. For example, if 8 bells + are being used, they will, at first, be rung in order: + 12345678. If the first change is for bells 5 and 6, the + bells will then be rung in the order 12346578. If the + second change is 1 and 2, the next notes are 21346578. + After a long list of changes, the order the bells are rung + in can become quite complex. + </P +><P +> For a group of bell-ringers to change the order of the + notes, they must each either delay their bell's next ring, + hasten it, or keep it the same as the time it takes to + ring all the bells once. The length of time between each + ring of a given bell can only be changed a little each + time, though; with an ink-jet weave pattern, we want the + same to apply to the distance between passes.) + </P +><P +> Finally, knowing the number of jets J and their separation + S, we can calculate the starting row of any given pass p + as follows: + <DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1909" +></A +><PRE +CLASS="screen" +>passesperblock = S +passblock = floor(p / passesperblock) +offsetinpassblock = p - passblock * passesperblock +subblocksperblock = gcd(S, J) +passespersubblock = S / subblocksperblock +subpassblock = floor(offsetinpassblock / passespersubblock) +if subpassblock < ceiling(subblocksperblock/2) + subblockoffset = 2*subpassblock +else + subblockoffset = 2*(subblocksperblock-subpassblock)-1 +startingrow = passblock * S * J + offsetinpassblock * J + subblockoffset</PRE +><P +></P +></DIV +> + </P +><P +> We can simplify this down to the following: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1912" +></A +><PRE +CLASS="screen" +>subblocksperblock = gcd(S, J) +subpassblock = floor((p % S) * subblocksperblock / S) +if subpassblock * 2 < subblocksperblock + subblockoffset = 2*subpassblock +else + subblockoffset = 2*(subblocksperblock-subpassblock)-1 +startingrow = p * J + subblockoffset</PRE +><P +></P +></DIV +><P +> So the row number of jet j of pass p is + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1915" +></A +><PRE +CLASS="screen" +>subblocksperblock = gcd(S, J) + +subblockoffset(p) + = 2*subpassblock , if subpassblock * 2 < subblocksperblock + = 2*(subblocksperblock-subpassblock)-1 , otherwise + where + subpassblock = floor((p % S) * subblocksperblock / S) + +row(j, p) = p * J + subblockoffset(p) + j * S</PRE +><P +></P +></DIV +><P +> Together with the inequality 0 ≤ j < J, we can use + this definition in reverse to calculate the pass number + containing a given row, r. Working out the inverse + definition involves a little guesswork, but one possible + result is as follows. Given a row, r, which is known to + be the first row of a pass, we can calculate the pass + number as follows: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1918" +></A +><PRE +CLASS="screen" +>subblocksperblock = gcd(S, J) +subblockoffset = r % subblocksperblock +pass = (r - subblockoffset) / J</PRE +><P +></P +></DIV +><P +> If G = 1, we can determine the pass number with this + algorithm: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1921" +></A +><PRE +CLASS="screen" +>offset = r % J +pass = (r - offset) / J +while (offset % S != 0) +{ +pass-- +offset += J +} +jet = offset / S</PRE +><P +></P +></DIV +><P +> Generalising, we come up with this algorithm. Given r, S + and J: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1924" +></A +><PRE +CLASS="screen" +>G = gcd(S, J) +passespersubblock = S/G +subblockoffset = r % G +subpassblock = subblockoffset / 2 , if subblockoffset % 2 == 0 + = G - (subblockoffset+1)/2 , otherwise +baserow = r - subblockoffset - (subpassblock * passespersubblock * J) +offset = baserow % J +pass = (baserow - offset) / J +while (offset % S != 0) +{ +offset += J +pass -= 1 +} +subblockretreat = floor(pass / passespersubblock) % G +pass -= subblockretreat * passespersubblock +pass += subpassblock * passespersubblock +jet = (r - subblockoffset - pass * J) / S</PRE +><P +></P +></DIV +><P +> Let's look at some examples of imperfect but correct weave + patterns: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1927" +></A +><P +> S = 6, J = 4, GCD = 2, + passesperblock = S = 6, + passespersubblock = S / G = 6 / 2 = 3: + </P +><PRE +CLASS="screen" +>0 *-----*-----*-----* +1 *-----*-----*-----* +2 *-----*-----*-----* +3 *-----*-----*-----* +4 *-----*-----*-----* +5 *-----*-----*-----* +6 *-----*-----*-----* +7 *-----*-----*-----* +8 *-----*-----*-----* +9 *-----*-----*-----* +10 *-----*-----*-----* +11 *-----*-----*-----* +12 *-----*-----*-----* +13 *-----*-----*-----* +14 *-----*-----*-----* +15 *-----*-----*---- +16 *-----*-----* +17 *-----*-- +18 *----- +19 *-</PRE +><P +></P +></DIV +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1930" +></A +><P +> S = 8, J = 6, G = 2, + passesperblock = S = 8, + passespersubblock= S / G = 8 / 2 = 4: + </P +><PRE +CLASS="screen" +>0 *-------*-------*-------*-------*-------* +1 *-------*-------*-------*-------*-------* +2 *-------*-------*-------*-------*-------* +3 *-------*-------*-------*-------*-------* +4 *-------*-------*-------*-------*-------* +5 *-------*-------*-------*-------*-------* +6 *-------*-------*-------*-------*-------* +7 *-------*-------*-------*-------*-- +8 *-------*-------*-------*----- +9 *-------*-------*------- +10 *-------*-------*- +11 *-------*--- +12 *----</PRE +><P +></P +></DIV +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1933" +></A +><P +> S = 6, J = 12, G = 6, + passesperblock = S = 6, + passespersubblock= S / G = 6 / 6 = 1: + </P +><PRE +CLASS="screen" +>0 *-----*-----*-----*-----*-----*-----*-----*-----*-----*-----*-----* +1 *-----*-----*-----*-----*-----*-----*-----*-----*-----*-----*--- +2 *-----*-----*-----*-----*-----*-----*-----*-----*- +3 *-----*-----*-----*-----*-----*-----* +4 *-----*-----*-----*-----*-- +5 *-----*-----*---- +6 *-----</PRE +><P +></P +></DIV +><P +> We have now solved the basic weaving problem. There are + two further refinements we need to consider: oversampling, + and filling in the missing rows at the start of the weave. + </P +><P +></P +></DIV +></DIV +><DIV +CLASS="sect2" +><H2 +CLASS="sect2" +><A +NAME="AEN1937" +>6.2.5. Oversampling</A +></H2 +><P +> By oversampling, we mean printing on the same row more than + once. There are two reasons for oversampling: to increase + the horizontal resolution of the printout and to reduce + banding. + </P +><P +> Oversampling to increase horizontal resolution is necessary + because, although the printer might be able to position an + ink drop to, for example, 1/1440" horizontally, it may not + be able to lay down two such drops 1/1440" apart. If it can + print two drops 1/720" apart, 2x oversampling will be + necessary to get a 1/1440" horizontal resolution. If it can + only print two drops 1/360" apart, 4x oversampling will be + necessary for a 1/1440" horizontal resolution. The printer + enforces this “drop spacing” by only accepting + raster passes with a horizontal resolution matching the + spacing with which it can print dots, so we must print + passes at different horizontal positions if we are to obtain + a higher horizontal resolution. (Another reason it does + this may be to reduce the amount of memory needed in the + printer.) + </P +><P +> Oversampling can also be done to decrease the banding + apparent in an image. By splitting a row into two or more + sets of dots (“lines”) and printing each line on + the same row, but with a different nozzle for each line, we + can get a smoother print. + </P +><P +> To quantify these two kinds of oversampling, we'll introduce + two new constants: H shows how many different horizontal + offsets we want to print at (the “horizontal + oversampling”) while O shows how many times we want to + print each row, over and above the number of times necessary + for horizontal oversampling (the “extra + oversampling”). + </P +><P +> It is necessary for all the lines printed by a given pass to + have the same horizontal offset, but there need not be any + relation between them in terms of extra oversampling. For + the moment, however, we will treat all oversampling as + potentially requiring this alignment; all lines in one pass + must be derived from the original row data in the same way. + Thus, we'll assume O = 1 for now. + </P +><P +> So, how do we do this oversampling? In fact, it can be done + easily: advance the paper by a factor of H less between each + pass. We'll define a new variable, A, to show how much we + advance the paper between passes. Previously, we'd have + defined A = J; we now let A = J / H. This also affects our + pass blocks. Printing one pass block used to involve + advancing the paper S × J rows; it now advances the + paper (S×J) / H rows. We therefore name a group of H + pass blocks a “band”. Printing one band + involves advancing the paper S×J rows, as a pass + block did before. + </P +><P +> To keep our weave pattern working correctly, so that + overprinting does not occur within a pass block, we also + have to redefine G as GCD(S,A). Here's an example of an + oversampled weave pattern: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1946" +></A +><P +> S = 4, J = 10, H = 2, A = J/H = 10/2 = 5, + G= GCD(4,5) = 1, + passesperblock = S = 4, + passespersubblock = S/G = 4/1 = 4: + </P +><PRE +CLASS="screen" +>0 *---*---*---*---*---*---*---*---*---* +1 *---*---*---*---*---*---*---*---*---* +2 *---*---*---*---*---*---*---*---*---* +3 *---*---*---*---*---*---*---*---*---* +4 *---*---*---*---*---*---*---*---*---* +5 *---*---*---*---*---*---*---*---*---* +6 *---*---*---*---*---*---*---*---*---* +7 *---*---*---*---*---*---*---*---*---* +8 *---*---*---*---*---*---*---*---*---* +9 *---*---*---*---*---*---*---*---* +10 *---*---*---*---*---*---*--- +11 *---*---*---*---*---*-- +12 *---*---*---*---*- +13 *---*---*---* +14 *---*--- +15 *--</PRE +><P +></P +></DIV +><P +> Now we have to determine which line is printed by each jet on + each pass. If we number each line generated as we split up a + row, we can use these numbers. We'll number the lines in our + diagram by replacing the <SAMP +CLASS="computeroutput" +>*</SAMP +>s + with integers in the range [0…H−1]. + </P +><P +> Overprinting occurs once per pass block, so we can simply + print pass block 0 with line 0, pass block 1 with line 1, + pass block 2 with line 2, etc, wrapping to 0 when we've run + out of lines: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1952" +></A +><PRE +CLASS="screen" +>0 0---0---0---0---0---0---0---0---0---0 +1 0---0---0---0---0---0---0---0---0---0 +2 0---0---0---0---0---0---0---0---0---0 +3 0---0---0---0---0---0---0---0---0---0 +4 1---1---1---1---1---1---1---1---1---1 +5 1---1---1---1---1---1---1---1---1---1 +6 1---1---1---1---1---1---1---1---1---1 +7 1---1---1---1---1---1---1---1---1---1 +8 0---0---0---0---0---0---0---0---0---0 +9 0---0---0---0---0---0---0---0---0 +10 0---0---0---0---0---0---0--- +11 0---0---0---0---0---0-- +12 1---1---1---1---1- +13 1---1---1---1 +14 1---1--- +15 1--</PRE +><P +></P +></DIV +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1954" +></A +><P +> S = 4, J = 12, H = 2, A = J/H = 12/2 = 6, + G= GCD(4,6) = 2, + passesperblock= S = 4, + passespersubblock= S/G = 4/2 = 2: + </P +><PRE +CLASS="screen" +>0 0---0---0---0---0---0---0---0---0---0---0---0 +1 0---0---0---0---0---0---0---0---0---0---0---0 +2 0---0---0---0---0---0---0---0---0---0---0---0 +3 0---0---0---0---0---0---0---0---0---0---0---0 +4 1---1---1---1---1---1---1---1---1---1---1---1 +5 1---1---1---1---1---1---1---1---1---1---1---1 +6 1---1---1---1---1---1---1---1---1---1---1 +7 1---1---1---1---1---1---1---1---1-- +8 0---0---0---0---0---0---0---0- +9 0---0---0---0---0---0--- +10 0---0---0---0---0 +11 0---0---0-- +12 1---1-</PRE +><P +></P +></DIV +><P +> But what do we do if J is not an exact multiple of H? This + is a difficult problem, which I struggled with for quite a + few days before giving in and taking the easy (but less + elegant) way out. The easy solution is to round J / H down, + then add on the accumulated error at the end of each band. + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1958" +></A +><P +> S = 4, J = 11, H = 2, A = floor(J/H) = floor(11/2) = 5, + G = GCD(4,5) = 1, + passesperblock = S = 4, + passespersubblock = S/G = 4/1 = 4 + </P +><PRE +CLASS="screen" +>Band 0: +0 0---0---0---0---0---0---0---0---0---0---0 +1 0---0---0---0---0---0---0---0---0---0---0 +2 0---0---0---0---0---0---0---0---0---0---0 +3 0---0---0---0---0---0---0---0---0---0---0 +4 1---1---1---1---1---1---1---1---1---1---1 +5 1---1---1---1---1---1---1---1---1---1---1 +6 1---1---1---1---1---1---1---1---1---1---1 +7 1---1---1---1---1---1---1---1---1---1--- + +Band 1: +8 | 0---0---0---0---0---0---0---0---0- +9 \-----------------------------------------/ 0---0---0---0---0---0---0---0 +10 S*J rows 0---0---0---0---0---0--- +11 0---0---0---0---0-- +12 1---1---1---1- +13 1---1---1 +14 1---</PRE +><P +></P +></DIV +><P +> We can calculate the starting row and subpass number of a + given pass in this scheme as follows: + </P +><DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1962" +></A +><PRE +CLASS="screen" +>A = floor(J / H) +subblocksperblock = gcd(S, A) +subpassblock = floor((p % S) * subblocksperblock / S) +if subpassblock * 2 < subblocksperblock + subblockoffset = 2*subpassblock +else + subblockoffset = 2*(subblocksperblock-subpassblock)-1 +band = floor(P / (S * H)) +passinband = P % (S * H) +startingrow = band * S * J + passinband * A + subblockoffset +subpass = passinband / S</PRE +><P +></P +></DIV +><P +> So the row number of jet j of pass p is + <DIV +CLASS="informalexample" +><P +></P +><A +NAME="AEN1965" +></A +><PRE +CLASS="screen" +>A = floor(J / H) +subblocksperblock = gcd(S, A) + +subblockoffset(p) + = 2*subpassblock , if subpassblock * 2 < subblocksperblock + = 2*(subblocksperblock-subpassblock)-1 , otherwise + where + subpassblock = floor((p % S) * subblocksperblock / S) + +band(p) = floor(p / (S * H)) +passinband(p) = p % (S * H) + +row(j, p) = band(p) * S * J + passinband(p) * A + subblockoffset(p) + j * S +row(j, p) = p * J + subblockoffset(p) + j * S</PRE +><P +> To be continued… + </P +><P +></P +></DIV +> + </P +></DIV +></DIV +><DIV +CLASS="NAVFOOTER" +><HR +ALIGN="LEFT" +WIDTH="100%"><TABLE +SUMMARY="Footer navigation table" +WIDTH="100%" +BORDER="0" +CELLPADDING="0" +CELLSPACING="0" +><TR +><TD +WIDTH="33%" +ALIGN="left" +VALIGN="top" +><A +HREF="c1717.html" +ACCESSKEY="P" +>Prev</A +></TD +><TD +WIDTH="34%" +ALIGN="center" +VALIGN="top" +><A +HREF="index.html" +ACCESSKEY="H" +>Home</A +></TD +><TD +WIDTH="33%" +ALIGN="right" +VALIGN="top" +><A +HREF="c1968.html" +ACCESSKEY="N" +>Next</A +></TD +></TR +><TR +><TD +WIDTH="33%" +ALIGN="left" +VALIGN="top" +>Weaving for inkjet printers</TD +><TD +WIDTH="34%" +ALIGN="center" +VALIGN="top" +><A +HREF="c1717.html" +ACCESSKEY="U" +>Up</A +></TD +><TD +WIDTH="33%" +ALIGN="right" +VALIGN="top" +>Dithering</TD +></TR +></TABLE +></DIV +></BODY +></HTML +>
\ No newline at end of file |