EXPLAIN EXTENDED

I'm spending this New Year holiday in sunny Florida.

One of its most beautiful places is the Everglades: the endless sea of grass, extending to the horizon, as far as the eye can see and beyond, and teeming with life.

There are all kinds of animals there. Herons, egrets, anhingas; fish, turtles, snakes; otters, skunks, small rodents; and of course, the king of Florida's wetlands, the American alligator.

The alligator is a well-oiled killing machine. It's motionless and extremely energy efficient when resting, but deadly fast when hunting. When the alligator is hunting, its eyes instantly track the faintest motion — and a fierce jump in any direction will follow immediately.

I was on a guided tour, and the tour guide mentioned that the alligators have binocular vision. The fields of view of their two eyes overlap, giving the predator the ability to estimate the direction and the distance to its prey more accurately.

We humans also have binocular vision. It allows us to see the world in three dimensions. When we are looking at an object with our two eyes, each eye sees it at a slightly different angle. The closer the thing is to us, the more the difference. This effect is called binocular parallax, and our brain can use it to estimate the distance to the object.

There are ways to trick the brain into believing something is 3D while it's not. To do this, we need a way to project a different image into each eye. There are lots of ways to do that: think holograms, polarized glasses, tilt cards, and many more.

Most of those methods require special equipment and materials, either to see or to produce the image. Maybe even both.

However, there is a way to see a three-dimensional image even on a simple piece of paper (or a plain LCD monitor without any 3D capabilities). It is technically called an autostereogram but most people know them as Magic Eye pictures.

A picture like this looks like repeating patterns of random dots or characters. The frequency of the patterns encodes the three-dimensional image: the close is the part of the image to the observer, the more frequent are the patterns.

It takes some effort to see the depth in what at first seems to be a random dot pattern. Not everyone can do that on the first try. There are lots of resources online which teach how to do that. The good thing is it's like riding a bicycle: once you got it right for the first time, there's no going back, it's always there with you.

Ever since I was a kid, I have been fascinated by the stereograms. So the moment I heard the words "binocular vision" from the tour guide, I instantly knew what would this New Year post be about.

Let's make a stereogram in PostgreSQL!

Stereogram theory

ASCII characters are almost as good as the color dots for the stereograms. All you have to do is combine them into repeating patterns. It does not matter if it's color dots or symbols. Ideally, they should be random and have different shapes within the pattern, but it's not necessary.

The go-to resource on ASCII stereograms is Gary Beene's page. There is a detailed description of the principles behind them, some examples, and even a code snippet in PowerBASIC to generate them. The only thing we need is translating it from PowerBASIC to SQL.

To create a stereogram, we first need an image to encode. Let's generate a simple depth mask: two overlapping rectangles. A larger number means closer to us.

WITH    parameters AS
        (
        SELECT  *
        FROM    (
                VALUES
                (112, 50)
                ) v (width, height)
        ),
        mask AS
        (
        SELECT  x, y,
                CASE
                WHEN x BETWEEN 40 AND 90 AND y BETWEEN 15 AND 35 THEN 4
                WHEN x BETWEEN 15 AND 65 AND y BETWEEN 10 AND 30 THEN 2
                ELSE 0 END AS depth
        FROM    parameters
        CROSS JOIN LATERAL
                GENERATE_SERIES(0, height - 1) y
        CROSS JOIN LATERAL
                GENERATE_SERIES(0, width - 1) x
        )
SELECT  STRING_AGG(COALESCE(depth::TEXT, ' '), '' ORDER BY x)
FROM    parameters
CROSS JOIN LATERAL
        GENERATE_SERIES(0, height - 1) y
CROSS JOIN LATERAL
        GENERATE_SERIES(0, width - 1) x
JOIN    mask
USING   (x, y)
GROUP BY
        y
ORDER BY
        y;

The depth map here is quite simple, and it's easy to see what's going on here: zero means the background level, two is closer to us, four is yet closer.

Random patterns

Now, let's generate a character map of random patterns. Every pattern will be 16 characters wide, and there will be 7 of them.

We will be seeding our random number generator with a constant value so that the random patterns will be the same between query invocations. In a short while, this will allow us to see what's happening with the 3D pictures. For now, we'll generate a plain background.

To do this, we will first generate our "lines" with a GENERATE_SERIES function and then, for each line, call another GENERATE_SERIES to generate a random pattern for each line.

Note that we are using 0 * y instead of just 0 as a first parameter to GENERATE_SERIES. It is because PostgreSQL optimizer is trying to be smart and will only invoke the lateral query once if it sees that it does not depend on the outermost query.

Usually, it's a good thing, but in this case, we do need the engine to invoke that RANDOM for each separate value of y, and that's how we introduce that external dependency (which does not do that much as it's a multiplication by zero).

Here's what our background looks like:

SELECT  SETSEED(0.20191231);

WITH    RECURSIVE
        parameters AS
        (
        SELECT  *
        FROM    (
                VALUES
                (16, 7, 50)
                ) v (pattern_length, pattern_count, height)
        CROSS JOIN LATERAL
                (
                SELECT  pattern_length * pattern_count AS width
                ) q
        ),
        patterns AS
        (
        SELECT  y, pattern
        FROM    parameters
        CROSS JOIN LATERAL
                GENERATE_SERIES(0, height - 1) y
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(CHR(FLOOR(RANDOM() * 94)::INT + 33), '')
                FROM    GENERATE_SERIES(0 * y, pattern_length - 1) x
                ) q (pattern)
        )
SELECT  REPEAT(pattern, pattern_count) AS line
FROM    patterns
CROSS JOIN
        parameters
ORDER BY
        y;

At first glance, it looks completely random, but if you look close enough, you see that the patterns are repeating horizontally every 16 characters.

Adding depth

Now, the fun part. On the background plane, our patterns are 16 characters long. We need them to have a shorter period where the depth map value is larger than 0. It means that they have to be 14 characters long on the background rectangle (which has the depth of 2) and 12 characters long on the foreground rectangle (which has the depth of 4).

The algorithm on Gary's page describes how to do that.

We will have to convert our query to a recursive one so that we can keep track of the pattern string for each line as we build it.

On each step, we will calculate the period of our pattern (according to the value of the depth map at this point), then we will take N'th character from the end of the string we've built so far (where N is the current value of the period) and append it to the end of the line.

The pattern will stay periodic as long as the depth remains the same.

When the depth increases, the pattern will lose some of its symbols (just in the right place).

When the depth decreases, the pattern will take the extra symbols from its beginning.

It will not be the original pattern anymore, of course, but it was random in the first place, so it does not matter much, as long as it's still periodic.

To have a better look at this algorithm, let's replace our random characters with hexadecimal digits and see what's going on here:

SELECT  SETSEED(0.20191231);

WITH    RECURSIVE
        parameters AS
        (
        SELECT  *
        FROM    (
                VALUES
                (16, 7, 50)
                ) v (pattern_length, pattern_count, height)
        CROSS JOIN LATERAL
                (
                SELECT  pattern_length * pattern_count AS width
                ) q
        ),
        patterns AS
        (
        SELECT  y, pattern
        FROM    parameters
        CROSS JOIN LATERAL
                GENERATE_SERIES(0, height - 1) y
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(CHR(CASE WHEN x < 10 THEN x + 48 ELSE x + 55 END), '')
                FROM    GENERATE_SERIES(0 * y, pattern_length - 1) x
                ) q (pattern)
        ),
        mask AS
        (
        SELECT  x, y,
                CASE
                WHEN x BETWEEN 40 AND 90 AND y BETWEEN 15 AND 35 THEN 4
                WHEN x BETWEEN 15 AND 65 AND y BETWEEN 10 AND 30 THEN 2
                ELSE 0 END AS depth
        FROM    parameters
        CROSS JOIN LATERAL
                GENERATE_SERIES(0, height - 1) y
        CROSS JOIN LATERAL
                GENERATE_SERIES(0, width - 1) x
        ),
        lines AS
        (
        SELECT  0 AS x, y, pattern AS line
        FROM    patterns
        CROSS JOIN
                parameters
        UNION ALL
        SELECT  x + 1, y, line || LEFT(RIGHT(line, pattern_length - depth), 1)
        FROM    lines
        JOIN    mask
        USING   (x, y)
        CROSS JOIN
                parameters
        WHERE   x < width
        )
SELECT  SUBSTR(line, pattern_length + 1, width) AS line
FROM    lines
CROSS JOIN
        parameters
WHERE   x = width
ORDER BY
        y;

The first ten lines are perfectly periodic from 0 to F.

On line 11 and below, however, something weird is happening: starting from the very first period, the F and the 0 vanish from the pattern.

It goes on for some time from 1 to E (with a period of 14), and then it makes recovery of sorts and gets its original length of 16 back.

However, it's not that beautiful series of consecutive digits anymore. The 0 and the F are gone forever, and 8 and 9 are inserted back into the pattern instead. It is the artifact of the algorithm. However, if we go back to the random sequences of characters, it does not matter much.

You have probably noticed that the shapes of the rectangles are discernible in the picture above. It is because it already is a complete, functioning stereogram!

But the fact that the patterns are repeating vertically, as well as horizontally, confuses the brain. The picture works much better with a random pattern of dots for every line.

Final result

Let's combine the last two queries and see the result:

SELECT  SETSEED(0.20191231);

WITH    RECURSIVE
        parameters AS
        (
        SELECT  *
        FROM    (
                VALUES
                (16, 7, 50)
                ) v (pattern_length, pattern_count, height)
        CROSS JOIN LATERAL
                (
                SELECT  pattern_length * pattern_count AS width
                ) q
        ),
        patterns AS
        (
        SELECT  y, pattern
        FROM    parameters
        CROSS JOIN LATERAL
                GENERATE_SERIES(0, height - 1) y
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(CHR(FLOOR(RANDOM() * 94)::INT + 33), '')
                FROM    GENERATE_SERIES(0 * y, pattern_length - 1) x
                ) q (pattern)
        ),
        mask AS
        (
        SELECT  x, y,
                CASE
                WHEN x BETWEEN 40 AND 90 AND y BETWEEN 15 AND 35 THEN 4
                WHEN x BETWEEN 15 AND 65 AND y BETWEEN 10 AND 30 THEN 2
                ELSE 0 END AS depth
        FROM    parameters
        CROSS JOIN LATERAL
                GENERATE_SERIES(0, height - 1) y
        CROSS JOIN LATERAL
                GENERATE_SERIES(0, width - 1) x
        ),
        lines AS
        (
        SELECT  0 AS x, y, pattern AS line
        FROM    patterns
        CROSS JOIN
                parameters
        UNION ALL
        SELECT  x + 1, y, line || LEFT(RIGHT(line, pattern_length - depth), 1)
        FROM    lines
        JOIN    mask
        USING   (x, y)
        CROSS JOIN
                parameters
        WHERE   x < width
        )
SELECT  SUBSTR(line, pattern_length + 1, width) AS line
FROM    lines
CROSS JOIN
        parameters
WHERE   x = width
ORDER BY
        y;

If you're still having problems seeing the 3D image, move the mouse cursor over the picture and back to highlight the differences between the original background and the stereogram.

Hidden message

I've made one more stereogram, with a hidden message. Can you see what it is?

SELECT  SETSEED(0.20191231);

WITH    RECURSIVE
        parameters AS
        (
        SELECT  *
        FROM    (
                VALUES
                (16, 7, 50)
                ) v (pattern_length, pattern_count, height)
        CROSS JOIN LATERAL
                (
                SELECT  pattern_length * pattern_count AS width
                ) q
        ),
        patterns AS
        (
        SELECT  y, pattern
        FROM    parameters
        CROSS JOIN LATERAL
                GENERATE_SERIES(0, height - 1) y
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(CHR(FLOOR(RANDOM() * 94)::INT + 33), '')
                FROM    GENERATE_SERIES(0 * y, pattern_length - 1) x
                ) q (pattern)
        ),
        mask AS
        (
        SELECT  x, y,
                CASE
                WHEN y > 4
                     AND SUBSTRING(SPLIT_PART(banner, E'\n',
                                   FLOOR(y / 4)::INT), FLOOR(x / 12)::INT, 1) = '*'
                THEN 2
                ELSE 0
                END depth
        FROM    parameters
        CROSS JOIN
                (
                SELECT  CONVERT_FROM(DECODE('
                KioqICoqKgogICogKiAqCioqKiAqICoK
                KiAgICogKgoqKiogKioqCgoqKiogKioqCiAgKiAqICoK
                KioqICogKgoqICAgKiAqCioqKiAqKioK',
                'BASE64'), 'UTF8') AS banner
                ) q
        CROSS JOIN LATERAL
                GENERATE_SERIES(0, height - 1) y
        CROSS JOIN LATERAL
                GENERATE_SERIES(0, width - 1) x
        ),
        lines AS
        (
        SELECT  0 AS x, y, pattern AS line
        FROM    patterns
        CROSS JOIN
                parameters
        UNION ALL
        SELECT  x + 1, y, line || LEFT(RIGHT(line, pattern_length - depth), 1)
        FROM    lines
        JOIN    mask
        USING   (x, y)
        CROSS JOIN
                parameters
        WHERE   x < width
        )
SELECT  SUBSTR(line, pattern_length + 1, width) AS line
FROM    lines
CROSS JOIN
        parameters
WHERE   x = width
ORDER BY
        y;

You can view the queries here: https://github.com/quassnoi/explain-extended-2020

Let your life in this New Year be full and solid!

Previous New Year posts:

• Happy New 2010 Year!
• Happy New 2011 Year!
• Happy New 2012 Year!
• Happy New 2013 Year!
• Happy New 2014 Year!
• Happy New 2015 Year!
• Happy New 2016 Year!
• Happy New 2017 Year!
• Happy New 2018 Year!
• Happy New 2019 Year!