Home Cooking XML Page Civil War Letters Art

# Weaving

Today's adventure begins with a nice paper from the Bridges Archive about algorithms for creating weaving patterns from binary sequences. The basic idea is very simple: using one sequence to drive the pattern of light and dark for the first row, and another sequence to drive the evolution of that pattern vertically. The basic algorithm to fill the `WxH` matrix `M` is:

```Populate sequences X and Y to the appropriate lengths
Populate first row:
Randomly set M to 0 or 1
For j in 2 to W:
Set M[j] to (M[j-1] + X[j] + 1) mod 2
Populate subsequent rows:
For i in 2 to H
For j in 1 to W
Set M[i][j] to (M[i-1][j] + Y[i] + j) mod 2
```

You can then render this matrix pattern out. Ahmed does so by connecting dots with 1 by lines and then filling; I just render the points in the grid as boxes of the appropriate colour.

Since I'm working in XQuery, which has neither assignment nor 2D matrices, the implementation looks a little different, involving folds:

```(:
: Input: columns X rows, x and y sequences
:)
let \$r1 :=
fold-left(2 to \$columns, rand:bernoulli(50),
function(\$m as xs:integer*, \$c as xs:integer) as xs:integer* {
\$m,
(\$m[\$c - 1] + \$x[\$c] + 1) mod 2
}
)
return (
fold-left(2 to \$rows, \$r1,
function(\$m as xs:integer*, \$r as xs:integer) as xs:integer* {
\$m,
let \$last :=
\$m[position() > (\$r - 2) * \$columns and
position() <= (\$r - 1) * \$columns]
return
fold-left(1 to \$columns, (),
function(\$row as xs:integer*, \$c as xs:integer) as xs:integer* {
\$row,
(\$last[\$c] + \$y[\$r] + \$c) mod 2
}
)
}
)
)
```

rand:bernoulli(50) is one of my library functions, returning 1 50% of the time. See 20220124_random.html for more.

What sequences should we use? Random sequences produce random results, which aren't especially pleasing. Ahmed describes using the Thue-Morse sequence (A010060 in ), the Fibonacci word (A003849), and sequences based on mutually prime numbers.

The mutual prime sequence is based on division of one number by the other:

```for \$i in 1 to \$n
let \$dx := ((2*\$q - \$r) * \$i) mod (2*\$q)
return if (\$dx < \$q) then 0 else 1
```

The other thing you can do is do multilevel weavings, where you fill in each square of the weaving with a smaller scale version of the weaving, where the initial corner is coloured based on the larger scale weaving.

Here are a couple of weavings. One is created by crossing the Fibonacci word with itself (1 level) and the other with the mutual prime sequence based on 521 and 20 crossed with the Fibonacci word sequence (2 level). I colour the outlines of the boxes with the opposite colour, but only some percentage of the kind, which gives the pleasing naturalistic effect.  I already had the ability to create de Bruijn sequences, so I added those, and after falling into the wonderful rabbit hole[*] that is the Online Encyclopedia of Integer Sequences , I added a few more, with varying success.

This weaving is created using the first Feigenbaum symbolic sequence cross with a prime sequence based on 449 and 20 (2 level): ## Why Not More Than Than Two Colours?

Indeed, why not?

Ahmed is interested in patterns that are actually physically weavable but I am just interested in making interesting patterns. Some adjustments are required: basically everything that was mod 2 becomes mod k. The starting corner value is selected from 0 to k instead of being 0 or 1.

Weaving mod k:

```(:
: Input: columns X rows, x and y sequences, k number of colours
:)
let \$r1 :=
fold-left(2 to \$columns, rand:select-random(0 to \$k - 1),
function(\$m as xs:integer*, \$c as xs:integer) as xs:integer* {
\$m,
(\$m[\$c - 1] + \$x[\$c] + 1) mod \$k
}
)
return (
fold-left(2 to \$rows, \$r1,
function(\$m as xs:integer*, \$r as xs:integer) as xs:integer* {
\$m,
let \$last :=
\$m[position() > (\$r - 2) * \$columns and
position() <= (\$r - 1) * \$columns]
return
fold-left(1 to \$columns, (),
function(\$row as xs:integer*, \$c as xs:integer) as xs:integer* {
\$row,
(\$last[\$c] + \$y[\$r] + \$c) mod \$k
}
)
}
)
)
```

Prime sequence mod k:

```for \$i in 1 to \$n
let \$dx := ((\$k*\$q - \$r) * \$i) mod (\$k*\$q)
for \$i in 1 to \$k - 1
return if (\$dx < \$i*\$q) then \$i - 1 else (),
\$k
)
```

This now opens us up to using non-binary sequences. For example, we can use de Bruijn sequences over an alphabet of size k, or a generalized Thue-Morse sequence over an alphabet of size k. Since all the math is mod k anyway, there is no necessary relationship between the number of colours and the range of the driving sequences. The quality of the results may vary if the range and number of colours are well--chosen, however.

Here are some examples: A six-colour weaving of a 3-ply prime sequence of 271 over 16 crossed with 4-ply Thue-Morse sequence, a three-colour weaving of a binary Feigenbaum sequence crossed with a binary de Bruijn sequence, and a six-colour weaving of a 6-ply prime sequence of 457 over 23 with a 3-ply prime sequence of 139 over 17. The scaling has been randomized as well as the colouring.   As you see: using multiple colours over binary sequences works, but tends to produce muddled patterns, especially with prime-based sequences.

## Sequence-Driven Colouring

I talked a bit about a way to use de Bruijn sequences to drive colouring in 20220103_debruijn.html. We can use these other sequences to drive colour choices as well.

Here a Thue-Morse sequence is being used to bump the colour selections to provide a little bit of variation to the overall diagonal colour sweep: The effect is subtle, but softens the hard transitions a bit. If we scramble the gradient you can see what's happening more clearly: ## References and Notes

[*] Seriously, this is an amazing website, with information having been gathered since 1964. Every sequence has a unique code, with a detailed description of its definition, theorems related to it, related sequences, code snippets for generating it, the first few terms, a boatload of references to papers and descriptions. Just marvelous.