(gimpprint.info.gz) What is perfect weaving?
Info Catalog
(gimpprint.info.gz) Weaving collisions
(gimpprint.info.gz) Weaving algorithms
(gimpprint.info.gz) Oversampling
What makes a "perfect" weave?
-----------------------------
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.
We can work out the greatest common divisor of a pair of natural
numbers using Euler's algorithm:
* Start with the two numbers: (e.g.) 9, 24
* Swap them if necessary so that the larger one comes first: 24, 9
* Subtract the second number from the first: 15, 9
* Repeat until the first number becomes smaller: 6, 9
* Swap the numbers again, so the larger one comes first: 9, 6
* Subtract again: 3, 6
* Swap: 6, 3
* Subtract: 3, 3
* And again: 0, 3
* When one of the numbers becomes 0, the other number is the GCD of
the two numbers you started with.
These repeated subtractions can be done with C's `%' operator, so we
can write this in C as follows:
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;
}
`gcd(S,J)' will feature quite prominently in our weaving algorithm.
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).)
S=8, J=6, G=2:
0 *-------*-------*-------*-------*-------*
1 *-------*-------*-------*-------*-------*
2 *-------*-------*-------*-------*-------*
3 *-------*-------*-------*-------*-------*
4 ^-------^-------^-------*-------*-------*
5 ^-------^-------^-------*-------*-------*
In this case, jets 0, 1 and 2 of pass p+4 collide with jets 3, 4 and
5 of pass 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:
0 *-------*-------* - - -
1 *-------*-------* - - -
2 *-------*-------* - - -
3 *-------*-------* - - -
4 *-------*-------* - - -
5 *-------*-------* - - -
If we left the paper advance alone, we'd get a sparse weave; only one
row can be printed every G rows:
0 *-------*-------* - - -
1 *-------*-------* - - -
2 *-------*-------* - - -
3 *-------*-------* - - -
4 *-------*-------* - - -
5 *-------*-------* - - -
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
These rows need filling in.
The rows that would have been printed by the jets we've now omitted
(shown as `-') are printed by other jets on later passes.
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).
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.
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.
Another example:
S=6, J=9, G=3, C=S/G=2:
0 *-----*-----*-----*-----*-----*-----*-----*-----*
1 *-----*-----*-----*-----*-----*-----*-----*-----*
2 ^-----^-----^-----^-----^-----^-----*-----*-----*
3 ^-----^-----^-----^-----^-----^-----*-----*-----*
4 ^-----^-----^-----^-----^-----^-----*-----
5 ^-----^-----^-----^-----^-----^--
^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^
These rows need filling in.
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.
S=9, J=6, G=3, C=3:
0 *--------*--------*--------*--------*--------*
1 *--------*--------*--------*--------*--------*
2 *--------*--------*--------*--------*--------*
3 ^--------^--------^--------^--------*--------*
4 ^--------^--------^--------^--------*--------*
5 ^--------^--------^--------^--------*--------*
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.
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.
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.
Looking back at an example of a perfect weave, we can divide it into
pass blocks:
S=7, J=2, G=1:
imaginary extra jet
|
0 *------* * <--start of pass block 0
1 *------* |
2 *------* |
3 *------*|
4 *-----|*
5 *---|--*
6 *-|----*
|
7 *------* <--start of pass block 1
8 *------*
9 *------*
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.
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.
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.
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.
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).
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).
This gives us a weave pattern looking like this:
S=6, J=9, G=3, B=2:
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)
S=9, J=6, G=3, B=3:
0 *--------*--------*--------*--------*--------*
1 *--------*--------*--------*--------*--------*
2 *--------*--------*--------*--------*--------*
3 *--------*--------*--------*--------*--------*
4 *--------*--------*--------*--------*--------*
5 *--------*--------*--------*--------*--------*
6 *--------*--------*--------*--------*---
7 *--------*--------*--------*------
8 *--------*--------*--------*
9 *--------*--------*-----
10 \---/ *--------*--------
11 small offset *--------*--
12 *----
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:
S=8, J=4, G=4, B=2:
0 *-------*-------*-------*
1 *-------*-------*-------*
2 *-------*-------*-------*
3 *-------*-------*-------*
4 *-------*-------*-------*
5 *-------*-------*-------*
6 *-------*-------*-------*
7 *-------*-------*-------*
8 *-------*-------*-------*
9 \/ *-------*-------*-------*
very small offset!
We can plot the offset against the subblock number as follows:
subblock number
| offset
| |
| 0123
0 *
1 *
2 *
3 *
0 *
1 *
2 *
3 *
The discontinuity in this plot results in the small offset between
passes.
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:
offset(b) = 2*b , if b < ceiling(G/2)
= 2*(G-b)-1 , otherwise
We can visualise this as follows, for G=10:
0123456789
0 *
1 *
2 *
3 *
4 *
5 *
6 *
7 *
8 *
9 *
0 *
1 *
2 *
3 *
4 *
5 *
6 *
7 *
8 *
9 *
and for G=11:
1
01234567890
0 *
1 *
2 *
3 *
4 *
5 *
6 *
7 *
8 *
9 *
10 *
0 *
1 *
2 *
3 *
4 *
5 *
6 *
7 *
8 *
9 *
10 *
This gives a weave looking like this:
S=12, J=6, G=6, B=2:
0 *-----------*-----------*-----------*-----------*-----------*
1 *-----------*-----------*-----------*-----------*-----------*
2 *-----------*-----------*-----------*-----------*-----------*
3 *-----------*-----------*-----------*-----------*---------
4 *-----------*-----------*-----------*-----------*-
5 *-----------*-----------*-----------*-------
6 *-----------*-----------*-----------*
7 *-----------*-----------*------
8 *-----------*-----------*--
9 *-----------*--------
10 *-----------*----
11 *----------
12 *-----
This method ensures that the offset between passes is always in the
range [J-2,J+2].
(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.
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.)
Finally, knowing the number of jets J and their separation S, we can
calculate the starting row of any given pass p as follows:
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
We can simplify this down to the following:
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
So the row number of jet j of pass p is
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
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:
subblocksperblock = gcd(S, J)
subblockoffset = r % subblocksperblock
pass = (r - subblockoffset) / J
If G==1, we can determine the pass number with this algorithm:
offset = r % J
pass = (r - offset) / J
while (offset % S != 0)
{
pass--
offset += J
}
jet = offset / S
Generalising, we come up with this algorithm. Given r, S and J:
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
Let's look at some examples of imperfect but correct weave patterns:
S=6, J=4, GCD=2,
passesperblock=S=6,
passespersubblock=S/G=6/2=3:
0 *-----*-----*-----*
1 *-----*-----*-----*
2 *-----*-----*-----*
3 *-----*-----*-----*
4 *-----*-----*-----*
5 *-----*-----*-----*
6 *-----*-----*-----*
7 *-----*-----*-----*
8 *-----*-----*-----*
9 *-----*-----*-----*
10 *-----*-----*-----*
11 *-----*-----*-----*
12 *-----*-----*-----*
13 *-----*-----*-----*
14 *-----*-----*-----*
15 *-----*-----*----
16 *-----*-----*
17 *-----*--
18 *-----
19 *-
S=8, J=6, G=2,
passesperblock=S=8,
passespersubblock=S/G=8/2=4:
0 *-------*-------*-------*-------*-------*
1 *-------*-------*-------*-------*-------*
2 *-------*-------*-------*-------*-------*
3 *-------*-------*-------*-------*-------*
4 *-------*-------*-------*-------*-------*
5 *-------*-------*-------*-------*-------*
6 *-------*-------*-------*-------*-------*
7 *-------*-------*-------*-------*--
8 *-------*-------*-------*-----
9 *-------*-------*-------
10 *-------*-------*-
11 *-------*---
12 *----
S=6, J=12, G=6,
passesperblock=S=6,
passespersubblock=S/G=6/6=1:
0 *-----*-----*-----*-----*-----*-----*-----*-----*-----*-----*-----*
1 *-----*-----*-----*-----*-----*-----*-----*-----*-----*-----*---
2 *-----*-----*-----*-----*-----*-----*-----*-----*-
3 *-----*-----*-----*-----*-----*-----*
4 *-----*-----*-----*-----*--
5 *-----*-----*----
6 *-----
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.
Info Catalog
(gimpprint.info.gz) Weaving collisions
(gimpprint.info.gz) Weaving algorithms
(gimpprint.info.gz) Oversampling
automatically generated byinfo2html