?>
GTX0 NewestRepliesHottestMy Active
NIFE UpdatesRoadmapRequests | HelpDiscuss Game Worlds


XOR Fractals
Posted: Posted February 8th
Edited February 8th by Xhin

If you have some kind of image editor with layering, here's a fun trick for you.

1. Make a repeating horizontal black and white gradient.

2. On the next layer, make a repeating vertical black and white gradient.

3. Set the top layer to XOR the bottom layer.

You get this crazy thing:



I understand what XOR is and what it does but this kind of result is still really really unintuitive, so I've been playing with the math to try and understand it better.

Here's a summary of what XOR is:

XOR

the XOR operator is used somewhat like the + or * operators. You take two numbers, XOR them together and get a new number. The way this works comes down to binary values. For each bit, you do this function:

  • 0 XOR 0 = 0
  • 0 XOR 1 = 1
  • 1 XOR 0 = 1
  • 1 XOR 1 = 0

    Basically, XOR is true if both inputs are different, otherwise it's false. For numbers larger than one bit, you do this result on each bit and concatenate them together:

  • 01 XOR 10 = 11
  • 00 XOR 01 = 01
  • 10 XOR 11 = 01

    To try and figure out what was going on, I decided to make my own gradients using black, two shades of gray and white represented by the numbers 00, 01, 10 and 11 and then XOR them together. What i got was a similar fractal-kind of pattern, but more interestingly, I noticed some interesting patterns in my XOR chart itself:

    00 01 10 11
    00 00 01 10 11
    01 01 00 11 10
    10 10 11 00 01
    11 11 10 01 00


    Every single row contains the pattern [00,01,10,11] however the direction the pattern runs alternates left and right. Similarly, every single column contains the pattern [00,01,10,11] and the direction alternates left and right as well. I realize the rows and columns are the same thing, but seeing the chart like this is interesting because both axes are gradients.

    I thus did the next logical step and used my image editor to "paint" the chart:



    If you take the 16 biggest chunks to be the equivalent to the 16 values in the chart, you see the same exact patterns.. the all-black diagonal (00) crossing with the all-white diagonal (11), the alternating gradients in each row and column (made by averaging the details in each box, or with a good blur tool).



    So this is neat, it helps explain the overall structure. But why does it recurse infinitely like a fractal? Well, let's take the top-left quadrant of boxes:

    00 01
    00 00 01
    01 01 00


    If we wanted to add more "detail" to the gradient, say an extra two bits worth, then you would just use the same pattern from before, only apply it to each pre-existing gradient value... so [0000,0001, 0010, 0011, 0100, 0101, 0110, 0111] is a perfect gradient of the two values with the two extra bits. You would put that on both axes, and then XOR all the extra bits together..



    Sure enough, the value chart looks exactly like the picture, only now you have that extra 00 in front of it, so the colors are going to be darker overall but the pattern will still be there.

    Every time you add two more bits of detail, the pattern repeats itself on a deeper level. Bitmaps have 24 bits available per pixel so even with small image spaces you're going to get these wonderfully detailed fractals.

    This still isn't an intuitive result. I think the problem for me is that while any individual 16x16 grid makes sense, when seeing the whole thing you have these sharp edges everywhere. Somehow it "knows" to put up borders between sections. I started looking closer at the "borders" and I made another discovery:



    The middle box is yet another microcosm of the whole pattern. This is cool but what's interesting is it isn't some shifted version of the whole pattern with extra bits, it is the whole pattern. The values are exactly the same as they would be if it was blown up 200%%%%. These jarring borders are present because they were present in the original pattern, and the 2 white and 2 black boxes have extra alternating detail because they had extra alternating detail in the original pattern as well.

    But then I noticed something more about the "borders" -- everywhere there is a jarring "border", the values on either side are opposites of one another. 01 and 10 are opposites, 11 and 00 are opposites. So how are those two patterns connected? Well, 01 and 00 are opposites too, it's just a different bit that's negated.

    At this point I realized I was looking at this whole thing wrong, these aren't "gradients" that I'm looking at, they're alternating types of negation. If you look at the two middle columns you have the sequences:

  • [01,00,11,10] = A
  • [10,11,00,01] = B

    In sequence A to go from 01 to 00, you negate the right bit. next, you negate both bits, then you negate the right bit. Then to get back to the original 01, you negate both bits again.

    In sequence B, to go from 10 to 11, you negate the right bit. Then both bits, then the right bit again. Then to get back to the original 10, you negate both bits again.

    So instead of a gradient what you're really looking at is an alternating pattern of negating the right bit and negating both bits over and over:



    Here I've represented right-bit negation in red and both-bit negation in blue. If you expand these patterns out, you get some kind of checkerboard-like pattern:



    This means you're not looking at a gradient at all, you're looking at alternating squares. The consequences of blue squares are just a lot more jarring to look at.

    I felt like I understood the XOR fractals better, but I had a problem with the new pattern I've made -- where are all the left-negates? Why is the pattern so biased towards right-negating? Well it turns out both left-negating and no-negating are present in the pattern alongside right-negating and both-negating:



    Here, I've representing left-negating by yellow and no-negating by green. These form a nice checkerboard pattern of their own.

  • There are 6 Replies



    Did this with two conical gradients. Neat.

    Posted February 9th by nullfather

    I will have more to say about this later, but to summarize it looks like you've stumbled into some group theory. Particularly, Cayley tables, groups of the form \(Z_2 \times \dots \times Z_2\), and subgroups.

    Check these out in the meantime:

    https://en.wikipedia.org/wiki/Cayley_table

    https://en.wikipedia.org/wiki/Cyclic_group

    By the way, cool pictures.



    Edited February 9th by EN
    EN

    So, first a little primer on group theory. Nothing too advanced. As you discovered here, you encounter group theory all of the time without realizing it. A group is a set of elements together with some rule that tells you how to combine two elements to get a new one. The set and rule have to obey a few properties:

    1. Identity: There's an element that you can combine with any other element that doesn't change the second element. In your case, 00 acts like the identity. Combine 00 with any other bitpair and you get the second one back.

    2. Inverses: For any element you pick, there's another element that you can combine with it to get the identity as the answer. For example, the inverse of 01 is 01, since when you XOR them together you get 00, which is our identity.

    3. Associativity: This just means that if we have multiple chances to apply the rule, we can do so in any way we choose. So 01 XOR 11 XOR 10 can be performed as (01 XOR 11) XOR 10 or 01 XOR (11 XOR 10) and you'll get the same answer. In either case, you get 00.

    4. Closure: This just says that when you combine two elements in your set, the answer will also be in the set. In this case, it's saying that XORing two bitstrings will always give you another bitstring.

    So what you've noticed is that the set {00, 01, 10, 11} with the operation of XOR is a group. We say that it's a group of order four, since there are four elements in the set. One question you may have is, are there any other groups of order four? The answer is yes! Let's take a look. To do so, first let's talk about Cayley tables.

    A Cayley table is a way to record and visualize how elements of a group interact. You put the elements down a column and across a row in the same order, and then fill in a cell in the table based on how its row and column elements combine. One thing that you'll notice about Cayley tables is that they have that "sudoku" property where every element shows up exactly once in each row and each column. (Can you prove why this is using the group definitions?)

    Here's the Cayley table that you already made:

    00 01 10 11
    00 00 01 10 11
    01 01 00 11 10
    10 10 11 00 01
    11 11 10 01 00


    I'm going to keep the elements the same, but come up with a new rule to combine them that will produce a different table.

    00 01 10 11
    00 00 01 10 11
    01 01 10 11 00
    10 10 11 00 01
    11 11 00 01 10


    The tables look different, but how do we know that they represent different groups and not just rearrangement of the rows/columns of the first table? Well, in the first table every element was its own inverse. You can see this by seeing all of the 00 elements down the main diagonal. In the second table, only two of the elements are their own inverse (00 and 10). The other two are inverses of each other.

    The group denoted by the following Cayley table

    0 1
    0 0 1
    1 1 0


    is called \(Z_2\) (read as "zee two" or "zee mod two") by mathematicians.

    Just like whole numbers can be factored uniquely into primes, groups can be factored uniquely into smaller groups. The group of size four that you made the table for can be factored as \(Z_2 \times Z_2\). The second group of four elements that I made a Cayley table for is \(Z_4\) - there's no way to factor it further. The composition of \(Z_2 \times Z_2\) makes it have the "fractaly" substructures that you see in some of those pictures. These are called "subgroups" by mathematicians - basically, smaller groups that live inside of bigger groups.

    Bitstrings of length 4 combined with XOR will give you the group \(Z_2 \times Z_2 \times Z_2 \times Z_2\). In general, bitstrings of length \(n\) with XOR will give you the group that is \(n\) copies of \(Z_2\).

    \(Z_2 \times Z_2 \times Z_2 \times Z_2\), which is of size 16, has a subgroup of size 8 and a subgroup of size 4 and a subgroup of size 2, all equal to \(Z_2\) times itself the appropriate number of times (and actually, many "copies" of those subgroups).

    If you say that each pixel is made up of a 24-long bitstring, then the group represented by your fractal Cayley table is \(Z_2 \times Z_2 \times \dots \times Z_2\), with 24 instances of \(Z_2\). There are \(2^{24}\) elements in that group, and for every power of two less than 24, there's a subgroup with that size. Which helps explain the fractal grids within grids picture that you're seeing.

    That's enough group theory for now. I'll read more details and observations from your post and try to respond to them at some point.

    Edited February 9th by EN
    EN

    But then I noticed something more about the "borders" -- everywhere there is a jarring "border", the values on either side are opposites of one another. 01 and 10 are opposites, 11 and 00 are opposites.


    This part, and your last section about negating right and both bits, are a consequence of the ordering that you gave your table. If you change the order of your row/column headers in the Cayley table from {00, 01, 10, 11} to some other order, say {11, 01, 00, 10}, you wouldn't see the same patterns. Probably some different, similar ones though. The reason why it shows up that way in the gradient is because both gradient directions are ordered the same: from back to white, top to bottom and left to right. If you changed the direction of just one of those gradients, you again would get different patterns. Here black can be thought of as 00 and white 11.

    Posted February 9th by EN
    EN

    By the way, here's two spiral gradients XORed together. You see the same Cayley table grid, but now it's warped.



    Posted February 9th by EN
    EN

    I like these.

    Posted Tuesday by chiarizio
    Reply to: XOR Fractals
    Enter your message here

    Site Rules | Complaints Process | Give Feedback Facebook Page
    GTX0 © 2009-2019 Xhin GameTalk © 1999-2008 lives on