8 ms·

A stochastic method to generate the Sierpinski triangle

110 points by wenderen 5y ago

ralferoo 5y ago
This isn't new. I first learned about Sierpinski triangles with this algortihm in the early 90s. Later, I learned how it can be generalised to IFS and opened my eyes to much more interesting examples. I think there's even an entire chapter on this specific algorithm in Barnsley's Fractals Everywhere book.
londons_explore 5y ago
Why it works: Imagine what would be required to put a dot in an area that ought to be blank... The previous point would have had to have been outside the triangle, or in another blank area at the previous step. Hence, it is impossible to draw in the blank areas.
- guimplen 5y ago
  I think your argument only shows that k-th point lies inside the k-th approximation of the Sierpinsky triangle, but says nothing abiut the fact that the final picture loooks like the Sierpisnsky triangle.
baliex 5y ago
You’ll find some more insight from Numberphile here, https://youtu.be/kbKtFN71Lfs https://youtu.be/kbKtFN71Lfs
- mathymathersenn 5y ago
  Great video on chaos games, you can do a lot of these just using turtles in python. The wiki for barnsley fern covers this more. https://en.wikipedia.org/wiki/Barnsley_fern#Computer_generation https://en.wikipedia.org/wiki/Barnsley_fern#Computer_generat... The wiki for chaos games has animated examples that make it pretty clear how it works for the sierpinski triangle: https://en.wikipedia.org/wiki/Chaos_game https://en.wikipedia.org/wiki/Chaos_game I enjoy that in Rule 90 of cellular automata approximate Sierpinski triangles are also generated as a mod-2 version of pascal's: https://en.wikipedia.org/wiki/Rule_90#Sierpiński_triangle https://en.wikipedia.org/wiki/Rule_90#Sierpiński_triangle Some other rules also result in the generation of sierpinski's triangle. Fun stuff.
user-the-name 5y ago
"Pick a random vertex of the triangle and find its midpoint with p" is actually "Take the whole triangle, and scale it down to half size, and place it so that it shares a random vertex". This is the basic structure of the Sierpinski triangle, so repeating this process creates the fractal shape of the Sierpinski.
- asxd 5y ago
  Thanks. I wasn't quite sure what "pick a random vertex of the triangle and find its midpoint with p" meant. What's the midpoint of a vertex?
  - kzrdude 5y ago
    It sounds like they mean the point (vertex + p) / 2.
    - asxd 5y ago
      D'oh. Seems obvious in the morning. The perils of late-night posting.
londons_explore 5y ago
This is what got me into programming... I had fiddled with Print "My Name Is Bob" in an infinite loop, and decided that there was nothing interesting programming could do... Then a relative wrote this algorithm in about 10 lines of qbasic. I was amazed that such simple code could do something so complex and unexpected. As a 5 yr old child, I spent hours trying to figure out how on earth this algorithm worked - even though it's blatantly obvious to adult me.
a_e_k 5y ago
I think this is basically the "chaos game." https://en.wikipedia.org/wiki/Chaos_game https://en.wikipedia.org/wiki/Chaos_game
- dsQTbR7Y5mRHnZv 5y ago
  Numberphile did a video on this: https://youtu.be/kbKtFN71Lfs https://youtu.be/kbKtFN71Lfs
rileyphone 5y ago
Also rule 90 tends to generate them from the nil seed - try clicking on the banner I made and set window size to something even and the seed to zero. https://rileystew.art/posts/banner https://rileystew.art/posts/banner
- hasmanean 5y ago
  When I was in high school my teacher told me a trick…take Pascal’s triangle and colour the even numbers black and the odd numbers white. You’ll end up with a Sierpinski triangle. Since Each row of Pascal’s triangle is generated from the row just above it… P(x,y) = P(x,y-1) + P(x-1,y-1) and since for any even or odd numbers … even+even=even, odd+odd=e, o+e=o so really you can compute the sign of any item in Pascal’s triangle by just checking the sign of the two numbers above it and xoring them. So you can compute each pixel S(x,y) = xor( S(x,y-1), S(x-1,y-1) Where the initial row is all 0 with a single 1 in it. I wrote a program on the Mac II in high school to compute this…it was quite a lot of fun. The process of going from integer to floating point to large integer to single bits was instructive.
arutar 5y ago
Here's a quick proof as to how it works. Suppose the triangle has endpoints (0,0), (1,0), and (1/2, sqrt(3)/2). Given a point (x,y), the three transformations then become f1(x,y) = (x/2, y/2) f2(x,y) = (x/2+1/2, y/2) f3(x,y) = (x/2 + 1/4, y/2 + sqrt(3)/4) which are precisely the maps in the Iterated Function System [1] which generate the Sierpinsky triangle! It's a very nice observation that the three maps have a concise representation in terms of taking the midpoint with the given point and the vertices of the triangle. [1] https://en.wikipedia.org/wiki/Iterated_function_system https://en.wikipedia.org/wiki/Iterated_function_system
- guimplen 5y ago
  Like it. The theory of the iterated function systems beautifully utilizes the Banach fixed-point theorem.
- codeflo 5y ago
  I'm sorry, but that gives me "draw the rest of the fucking owl" vibes. You're basically restating the algorithm's definition -- it's the rest of the proof that contains the interesting steps. Edit: In my view, to show that this draws the Sierpinsky triangle, one would need to show that (1) we only draw points that are in the Sierpinski triangle and (2) we draw all the points of the Sierpinski triangle. (1) is clearly false (we start with a random point), but the claim is of course only that we draw an “approximation”. What that means exactly would need to be defined. I assume a rigorous argument would involve 2D probability densities. Given that, (2) isn’t obvious to me as well, what’s the argument that all the parts of the Sierpinski shape correspond to areas with high probability density?
  - scotty79 5y ago
    I really don't see how any proof is necessary. Taking midpoint between a point and tringle vertex is a transformation that scales everything by 1/2 with this vertex as pivot. By choosing one of such three transformations randomly you are scaling the whole triangle into three smaller copies of itself that it cosists of. If you start with a point belonging to Sierpinski trinagle, you are adding more and more points belonging to that triangle. Fun thing is that you can use the same algorithm with different number and kind of transformations to get other fractals with such random walk. For exaple a fractal tree or fern leaf or Sierpinski carpet. Another interesting thing is you can start with a point not belonging to a fractal and it pretty quickly coverges. It's because fractals are attractors.
jankovicsandras 5y ago
Cool. Shameless plug: Sierpinski carpet L-system 677 bytes will render a Sierpinski carpet using an L-system to create a Z-order curve : https://github.com/jankovicsandras/misc https://github.com/jankovicsandras/misc
paol 5y ago
This is how I learned to draw the Sierpinsky triangle, I don't even know the analytical method. I got this method from fractint[0] I think, it had great docs explaining some of the fractal types. This was sometime in the mid 90's. [0] https://en.wikipedia.org/wiki/Fractint https://en.wikipedia.org/wiki/Fractint EDIT: Also, as a bonus this method is very easy to do with a pen and paper. I remember trying that, but it takes a lot of points before the structure starts to become visible.
- Sharlin 5y ago
  Well, the standard nonstochastic way is the obvious recursive subdivision: given a triangle, find the middle points of the edges to subdivide it into four smaller triangles, then continue recursively for the new triangles except the center one. Once you hit the recursion limit, simply draw a triangle.
RantyDave 5y ago
Could you write a function so that for point (x,y) it returns true if the point is "in" the spierpinski triangle? Yes, I am wondering if it could be expressed as a fragment shader :)
- Sharlin 5y ago
  You can exploit this nifty fact: in a pixel grid if you color a pixel at (x, y) based on whether (x & y) == y, you get a discrete, right-angled approximation of the Sierpinski triangle! Transform x and y appropriately to get the equilateral version. https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=a5a330e58597a62547621ee19b9c3adc https://play.rust-lang.org/?version=stable&mode=debug&editio... Edit: quick Shadertoy version: https://www.shadertoy.com/view/flVXDh https://www.shadertoy.com/view/flVXDh
  - RantyDave 5y ago
    OMG you've actually done it! That's outrageous!
_archon_ 5y ago
I thought I'd note that one of my favorite pages on the web pertains to exploring Sierpinski triangles [0] "The sierpinski triangle page to end most sierpinski triangle pages ™" [0]:http://www.oftenpaper.net/sierpinski.htm http://www.oftenpaper.net/sierpinski.htm
IngoBlechschmid 5y ago
Here is a version which can be played by up to three persons sharing a keyboard: https://www.speicherleck.de/iblech/stuff/chaosspiel-2015/chaosspiel.html https://www.speicherleck.de/iblech/stuff/chaosspiel-2015/cha... Developed as part of a mathematics day for children, the worksheet is available here: https://www.speicherleck.de/iblech/stuff/chaosspiel-2015/arbeitsblaetter.pdf https://www.speicherleck.de/iblech/stuff/chaosspiel-2015/arb...
ssm008 5y ago
How lovely! I thoroughly enjoyed this
ArtWomb 5y ago
Love comp prob & geom ;) Coolest part is the algo to generate uniform random points bounded within any triangle. I feel like its useful in loads of applications: FEM, monte carlo rendering, etc. https://blogs.sas.com/content/iml/2020/10/19/random-points-in-triangle.html https://blogs.sas.com/content/iml/2020/10/19/random-points-i...
Jyaif 5y ago
Kudos to whoever included it in the TI82's manual, it successfully tickled my curiosity when I was a kid in the 90s and played a part in me becoming a programmer. https://www.manualslib.com/manual/325928/Ti-Ti-82.html?page=202#manual https://www.manualslib.com/manual/325928/Ti-Ti-82.html?page=...
daneel_w 5y ago
The method presented by the author is the only method I've ever known. It was both simple enough for me to understand as a kid, and fast enough that I could plot the results within a minute using HiSoft BASIC on my Amiga 500. Just to add the curiosum, the method as it was explained to me as a kid: "Plot a pixel on any corner of the triangle. Pick a new corner on random and plot a pixel halfway between there and where your last pixel was, then just repeat."
- kragen 5y ago
  There are an astonishing number of ways to generate the Sierpinski triangle: 1. The Chaos Game, as described in this post. 2. Other ways of rendering the IFS; for example, iterating over the possibility tree of transforming a single point 10 times and plotting the 59049 leaves, or searching over the tree of inverse transformations from a given pixel to some depth like 6 and coloring the pixel with the length of the longest chain that doesn't blow up. It's a very well behaved IFS, so even methods that have trouble with some IFSs will do fine. 3. Coloring the odd numbers in Pascal's Triangle, aka Yang Hui's Triangle or the triangle from मेरु प्रस्तार. 4. As a generalization, plotting histories of an astonishingly wide range of 1-D cellular automata, starting with a single "live" cell. For example, the totalistic rule where a cell is live iff exactly 1 of itself and its neighbors were alive (rule 14). About a third of the 256 2-state neighborhood-3 CAs like this are some deformation of the Triangle IIRC. 5. A surprisingly large variety of L-systems also generate the Triangle. In http://canonical.org/~kragen/laserboot/cut-6 http://canonical.org/~kragen/laserboot/cut-6 I used, I think, F = !F!-F-!F!, where ! swaps left and right. An interesting thing about this curve in particular is that it avoids self-intersections, which is what makes it somewhat suitable for laser cutting. 6. And of course you can start with a solid triangle, cut a hole in its middle to make a triforce, and then recursively do the same for each of the resulting three remaining triangles. 7. For use as a calendar, http://canonical.org/~kragen/sw/dev3/siercal http://canonical.org/~kragen/sw/dev3/siercal I generated a tour of the triangle with a non-L-system method, just subdividing the triangle recursively. 8. It's also interesting to note that the state space of the Towers of Hanoi puzzle has the shape of the Sierpinski Triangle. So a suitable 2D graph layout algorithm (all edges equal length, maximizing total distance from the center) applied to the state space graph ought to generate it. This is a little handwavy, though. 9. I'd forgotten this, but as John D. Cook points out in https://www.johndcook.com/blog/2019/11/26/fractal-via-bit-twiddling/ https://www.johndcook.com/blog/2019/11/26/fractal-via-bit-tw..., the pixels where the bitwise AND of the X and Y coordinates is zero form a distorted Sierpinski Triangle. 10. Cook points out in https://www.johndcook.com/blog/2019/10/19/binary-surprise/ https://www.johndcook.com/blog/2019/10/19/binary-surprise/ that the numbers of sides in the regular n-gons constructible with compass and straightedge, when written down in binary, also form the Sierpinski Triangle.
klntsky 5y ago
I played with a similar approach a while ago. By changing the algorithm a bit it's possible to create various other beautiful images: https://drive.google.com/drive/folders/1TSgLRdO0tKIFUb6Oj8yNJgUeh2D_WA9-?usp=sharing https://drive.google.com/drive/folders/1TSgLRdO0tKIFUb6Oj8yN... Here's a link to my post (unfortunately, in Russian) describing the process: https://t.me/little_pieces/822?single https://t.me/little_pieces/822?single A quick translation: 1. We have a 2D space and a regular shape with N angles, where N is a parameter. 2. Choose a function f : R -> R (e.g. f(x) = x / 2 for Sierpinsky). 3. Choose a random "current" point 4. Choose a random angular point of the N-shape 5. Calculate the distance D between two points. Move the current point to the selected angle point by distance calculated as f(D). 6. Repeat steps 4-5, saving position of the current point on each step, until there is enough data to draw a density map Another person from gen-club[0] (Russian telegram chat dedicated to generative art) made a 3D-version of it[1][2]: [0] https://t.me/gen_c https://t.me/gen_c [1] https://t.me/mathimages/156 https://t.me/mathimages/156 [2] https://codepen.io/strangerintheq/full/ZEKXamr https://codepen.io/strangerintheq/full/ZEKXamr (zoom out at startup)
- hardmath123 5y ago
  Indeed, you can "learn" (by gradient descent) new parameters to this algorithm, to generate fractals in any target shape that you want! https://hardmath123.github.io/chaos-game-fractal-foliage.html https://hardmath123.github.io/chaos-game-fractal-foliage.htm...
frob 5y ago
I believe this is also the algorithm included in the TI-83 (plus) manual: https://www.manualowl.com/m/Texas%20Instruments/TI-83-Plus/Manual/240607?page=573 https://www.manualowl.com/m/Texas%20Instruments/TI-83-Plus/M... I remember sitting on the floor of our living room programming this in character by character on that TI keyboard. It's the first BASIC program I ever wrote. Everything before that was js and html.
- mawise 5y ago
  I have fond memories of learning to program on the TI-83 and following that same example!
pfedak 5y ago
As others have pointed out, a generalization of this method (iterated function systems) can generate a large class of fractals. There's a some fun software for generating these ( see https://en.wikipedia.org/wiki/Fractal_flame https://en.wikipedia.org/wiki/Fractal_flame) which also adds coloring based on the sequence of function applications, resulting in a pattern that respects the fractal structure. Going a step further, changing the "functions" over time can create smoothly animated fractals. Electric Sheep (https://electricsheep.org/ https://electricsheep.org/) is a screensaver version of this which doubles as a distributed computing network to generate them. It also mixes in non-linear transformations which makes for some impressive, mesmerizing patterns.
punnerud 5y ago
Video with here: https://imgur.com/1Svgp0G https://imgur.com/1Svgp0G (From the repo)
richm44 5y ago
Here's a version of the same as a BBC Microbot tweet https://twitter.com/bbcmicrobot/status/1333542986588753921 https://twitter.com/bbcmicrobot/status/1333542986588753921
sizediterable 5y ago
I remember there being a section demonstrating this in the manual for my TI-83 calculator [0] It prompted me to learn a bit more about IFS and discover one of my favorite fractals ever. The word "chaos" where each stroke is made up of the word "chaos" [1]. I spent a bunch of time coding up the fractals on that site [2] on my calculator [0] http://manualsdump.com/en/manuals/texas_instruments-ti-83/132084/573 http://manualsdump.com/en/manuals/texas_instruments-ti-83/13... [1] http://paulbourke.net/fractals/ifs/chaos_1.gif http://paulbourke.net/fractals/ifs/chaos_1.gif [2] http://paulbourke.net/fractals/ifs/ http://paulbourke.net/fractals/ifs/
RonInDune 5y ago
The Sierpinski triangle was the first "complex" system I had managed to draw, using the Logo programming language in the 90s. I recently tried to do a vtk 3D extension (Sierpinski cube)[1] using the same process as in the OP, but it was surprisingly computationally expensive! [1] https://en.wikipedia.org/wiki/Menger_sponge https://en.wikipedia.org/wiki/Menger_sponge
arunchaganty 5y ago
The chaos game is one of my favorite things! I first came across it nearly 15 years ago from James Gleick's excellent book Chaos and in fact I learned how to program so that I could actually implement the chaos game. After spending many years idly reflecting on why the chaos game converged to the Sierpinski triangle, I'd like to share an illustrated proof of mine that might be enjoyed by this audience: https://arun.chagantys.org/technical/2020/04/28/chaos-game.html https://arun.chagantys.org/technical/2020/04/28/chaos-game.h...
Nydhal 5y ago
You can make it using Cellular Automata too. Python Code:https://nbviewer.org/github/Nydhal/Python-Notebooks/blob/master/Selmi_Impossible_Fractal.ipynb https://nbviewer.org/github/Nydhal/Python-Notebooks/blob/mas...
jventura 5y ago
I did the same thing, but in Python, some years ago [1]. Never understood how it works, but it's easy to implement.. [1] https://joaoventura.net/blog/2016/sierpinski-triangle/ https://joaoventura.net/blog/2016/sierpinski-triangle/
aimor 5y ago
It's funny, so each point is only guaranteed to be in that iteration of the triangle. So if you want a sierpinski triangle accurate to n levels deep you want to throw away the first n-1 points. If you want to plot a specific sierpinski triangle you have to re-run the algorithm from the beginning to get more points.

110 points by wenderen 5y ago

This isn't new. I first learned about Sierpinski triangles with this algortihm in the early 90s. Later, I learned how it can be generalised to IFS and opened my eyes to much more interesting examples. I think there's even an entire chapter on this specific algorithm in Barnsley's Fractals Everywhere book.

londons_explore 5y ago

Why it works: Imagine what would be required to put a dot in an area that ought to be blank... The previous point would have had to have been outside the triangle, or in another blank area at the previous step. Hence, it is impossible to draw in the blank areas.

guimplen 5y ago
I think your argument only shows that k-th point lies inside the k-th approximation of the Sierpinsky triangle, but says nothing abiut the fact that the final picture loooks like the Sierpisnsky triangle.

baliex 5y ago

You’ll find some more insight from Numberphile here, https://youtu.be/kbKtFN71Lfs https://youtu.be/kbKtFN71Lfs

mathymathersenn 5y ago
Great video on chaos games, you can do a lot of these just using turtles in python. The wiki for barnsley fern covers this more. https://en.wikipedia.org/wiki/Barnsley_fern#Computer_generation https://en.wikipedia.org/wiki/Barnsley_fern#Computer_generat... The wiki for chaos games has animated examples that make it pretty clear how it works for the sierpinski triangle: https://en.wikipedia.org/wiki/Chaos_game https://en.wikipedia.org/wiki/Chaos_game I enjoy that in Rule 90 of cellular automata approximate Sierpinski triangles are also generated as a mod-2 version of pascal's: https://en.wikipedia.org/wiki/Rule_90#Sierpiński_triangle https://en.wikipedia.org/wiki/Rule_90#Sierpiński_triangle Some other rules also result in the generation of sierpinski's triangle. Fun stuff.

user-the-name 5y ago

"Pick a random vertex of the triangle and find its midpoint with p" is actually "Take the whole triangle, and scale it down to half size, and place it so that it shares a random vertex". This is the basic structure of the Sierpinski triangle, so repeating this process creates the fractal shape of the Sierpinski.

asxd 5y ago
Thanks. I wasn't quite sure what "pick a random vertex of the triangle and find its midpoint with p" meant. What's the midpoint of a vertex?
- kzrdude 5y ago
  It sounds like they mean the point (vertex + p) / 2.
  - asxd 5y ago
    D'oh. Seems obvious in the morning. The perils of late-night posting.

londons_explore 5y ago

This is what got me into programming... I had fiddled with Print "My Name Is Bob" in an infinite loop, and decided that there was nothing interesting programming could do... Then a relative wrote this algorithm in about 10 lines of qbasic. I was amazed that such simple code could do something so complex and unexpected. As a 5 yr old child, I spent hours trying to figure out how on earth this algorithm worked - even though it's blatantly obvious to adult me.

a_e_k 5y ago

I think this is basically the "chaos game." https://en.wikipedia.org/wiki/Chaos_game https://en.wikipedia.org/wiki/Chaos_game

dsQTbR7Y5mRHnZv 5y ago
Numberphile did a video on this: https://youtu.be/kbKtFN71Lfs https://youtu.be/kbKtFN71Lfs

rileyphone 5y ago

Also rule 90 tends to generate them from the nil seed - try clicking on the banner I made and set window size to something even and the seed to zero. https://rileystew.art/posts/banner https://rileystew.art/posts/banner

hasmanean 5y ago
When I was in high school my teacher told me a trick…take Pascal’s triangle and colour the even numbers black and the odd numbers white. You’ll end up with a Sierpinski triangle. Since Each row of Pascal’s triangle is generated from the row just above it… P(x,y) = P(x,y-1) + P(x-1,y-1) and since for any even or odd numbers … even+even=even, odd+odd=e, o+e=o so really you can compute the sign of any item in Pascal’s triangle by just checking the sign of the two numbers above it and xoring them. So you can compute each pixel S(x,y) = xor( S(x,y-1), S(x-1,y-1) Where the initial row is all 0 with a single 1 in it. I wrote a program on the Mac II in high school to compute this…it was quite a lot of fun. The process of going from integer to floating point to large integer to single bits was instructive.

arutar 5y ago

Here's a quick proof as to how it works. Suppose the triangle has endpoints (0,0), (1,0), and (1/2, sqrt(3)/2). Given a point (x,y), the three transformations then become f1(x,y) = (x/2, y/2) f2(x,y) = (x/2+1/2, y/2) f3(x,y) = (x/2 + 1/4, y/2 + sqrt(3)/4) which are precisely the maps in the Iterated Function System [1] which generate the Sierpinsky triangle! It's a very nice observation that the three maps have a concise representation in terms of taking the midpoint with the given point and the vertices of the triangle. [1] https://en.wikipedia.org/wiki/Iterated_function_system https://en.wikipedia.org/wiki/Iterated_function_system

guimplen 5y ago
Like it. The theory of the iterated function systems beautifully utilizes the Banach fixed-point theorem.
codeflo 5y ago
I'm sorry, but that gives me "draw the rest of the fucking owl" vibes. You're basically restating the algorithm's definition -- it's the rest of the proof that contains the interesting steps. Edit: In my view, to show that this draws the Sierpinsky triangle, one would need to show that (1) we only draw points that are in the Sierpinski triangle and (2) we draw all the points of the Sierpinski triangle. (1) is clearly false (we start with a random point), but the claim is of course only that we draw an “approximation”. What that means exactly would need to be defined. I assume a rigorous argument would involve 2D probability densities. Given that, (2) isn’t obvious to me as well, what’s the argument that all the parts of the Sierpinski shape correspond to areas with high probability density?
- scotty79 5y ago
  I really don't see how any proof is necessary. Taking midpoint between a point and tringle vertex is a transformation that scales everything by 1/2 with this vertex as pivot. By choosing one of such three transformations randomly you are scaling the whole triangle into three smaller copies of itself that it cosists of. If you start with a point belonging to Sierpinski trinagle, you are adding more and more points belonging to that triangle. Fun thing is that you can use the same algorithm with different number and kind of transformations to get other fractals with such random walk. For exaple a fractal tree or fern leaf or Sierpinski carpet. Another interesting thing is you can start with a point not belonging to a fractal and it pretty quickly coverges. It's because fractals are attractors.

jankovicsandras 5y ago

Cool. Shameless plug: Sierpinski carpet L-system 677 bytes will render a Sierpinski carpet using an L-system to create a Z-order curve : https://github.com/jankovicsandras/misc https://github.com/jankovicsandras/misc

paol 5y ago

This is how I learned to draw the Sierpinsky triangle, I don't even know the analytical method. I got this method from fractint[0] I think, it had great docs explaining some of the fractal types. This was sometime in the mid 90's. [0] https://en.wikipedia.org/wiki/Fractint https://en.wikipedia.org/wiki/Fractint EDIT: Also, as a bonus this method is very easy to do with a pen and paper. I remember trying that, but it takes a lot of points before the structure starts to become visible.

Sharlin 5y ago
Well, the standard nonstochastic way is the obvious recursive subdivision: given a triangle, find the middle points of the edges to subdivide it into four smaller triangles, then continue recursively for the new triangles except the center one. Once you hit the recursion limit, simply draw a triangle.

RantyDave 5y ago

Could you write a function so that for point (x,y) it returns true if the point is "in" the spierpinski triangle? Yes, I am wondering if it could be expressed as a fragment shader :)

Sharlin 5y ago
You can exploit this nifty fact: in a pixel grid if you color a pixel at (x, y) based on whether (x & y) == y, you get a discrete, right-angled approximation of the Sierpinski triangle! Transform x and y appropriately to get the equilateral version. https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=a5a330e58597a62547621ee19b9c3adc https://play.rust-lang.org/?version=stable&mode=debug&editio... Edit: quick Shadertoy version: https://www.shadertoy.com/view/flVXDh https://www.shadertoy.com/view/flVXDh
- RantyDave 5y ago
  OMG you've actually done it! That's outrageous!

_archon_ 5y ago

I thought I'd note that one of my favorite pages on the web pertains to exploring Sierpinski triangles [0] "The sierpinski triangle page to end most sierpinski triangle pages ™" [0]:http://www.oftenpaper.net/sierpinski.htm http://www.oftenpaper.net/sierpinski.htm

IngoBlechschmid 5y ago

Here is a version which can be played by up to three persons sharing a keyboard: https://www.speicherleck.de/iblech/stuff/chaosspiel-2015/chaosspiel.html https://www.speicherleck.de/iblech/stuff/chaosspiel-2015/cha... Developed as part of a mathematics day for children, the worksheet is available here: https://www.speicherleck.de/iblech/stuff/chaosspiel-2015/arbeitsblaetter.pdf https://www.speicherleck.de/iblech/stuff/chaosspiel-2015/arb...

ssm008 5y ago

How lovely! I thoroughly enjoyed this

ArtWomb 5y ago

Love comp prob & geom ;) Coolest part is the algo to generate uniform random points bounded within any triangle. I feel like its useful in loads of applications: FEM, monte carlo rendering, etc. https://blogs.sas.com/content/iml/2020/10/19/random-points-in-triangle.html https://blogs.sas.com/content/iml/2020/10/19/random-points-i...

Jyaif 5y ago

Kudos to whoever included it in the TI82's manual, it successfully tickled my curiosity when I was a kid in the 90s and played a part in me becoming a programmer. https://www.manualslib.com/manual/325928/Ti-Ti-82.html?page=202#manual https://www.manualslib.com/manual/325928/Ti-Ti-82.html?page=...

daneel_w 5y ago

The method presented by the author is the only method I've ever known. It was both simple enough for me to understand as a kid, and fast enough that I could plot the results within a minute using HiSoft BASIC on my Amiga 500. Just to add the curiosum, the method as it was explained to me as a kid: "Plot a pixel on any corner of the triangle. Pick a new corner on random and plot a pixel halfway between there and where your last pixel was, then just repeat."

kragen 5y ago
There are an astonishing number of ways to generate the Sierpinski triangle: 1. The Chaos Game, as described in this post. 2. Other ways of rendering the IFS; for example, iterating over the possibility tree of transforming a single point 10 times and plotting the 59049 leaves, or searching over the tree of inverse transformations from a given pixel to some depth like 6 and coloring the pixel with the length of the longest chain that doesn't blow up. It's a very well behaved IFS, so even methods that have trouble with some IFSs will do fine. 3. Coloring the odd numbers in Pascal's Triangle, aka Yang Hui's Triangle or the triangle from मेरु प्रस्तार. 4. As a generalization, plotting histories of an astonishingly wide range of 1-D cellular automata, starting with a single "live" cell. For example, the totalistic rule where a cell is live iff exactly 1 of itself and its neighbors were alive (rule 14). About a third of the 256 2-state neighborhood-3 CAs like this are some deformation of the Triangle IIRC. 5. A surprisingly large variety of L-systems also generate the Triangle. In http://canonical.org/~kragen/laserboot/cut-6 http://canonical.org/~kragen/laserboot/cut-6 I used, I think, F = !F!-F-!F!, where ! swaps left and right. An interesting thing about this curve in particular is that it avoids self-intersections, which is what makes it somewhat suitable for laser cutting. 6. And of course you can start with a solid triangle, cut a hole in its middle to make a triforce, and then recursively do the same for each of the resulting three remaining triangles. 7. For use as a calendar, http://canonical.org/~kragen/sw/dev3/siercal http://canonical.org/~kragen/sw/dev3/siercal I generated a tour of the triangle with a non-L-system method, just subdividing the triangle recursively. 8. It's also interesting to note that the state space of the Towers of Hanoi puzzle has the shape of the Sierpinski Triangle. So a suitable 2D graph layout algorithm (all edges equal length, maximizing total distance from the center) applied to the state space graph ought to generate it. This is a little handwavy, though. 9. I'd forgotten this, but as John D. Cook points out in https://www.johndcook.com/blog/2019/11/26/fractal-via-bit-twiddling/ https://www.johndcook.com/blog/2019/11/26/fractal-via-bit-tw..., the pixels where the bitwise AND of the X and Y coordinates is zero form a distorted Sierpinski Triangle. 10. Cook points out in https://www.johndcook.com/blog/2019/10/19/binary-surprise/ https://www.johndcook.com/blog/2019/10/19/binary-surprise/ that the numbers of sides in the regular n-gons constructible with compass and straightedge, when written down in binary, also form the Sierpinski Triangle.

klntsky 5y ago

I played with a similar approach a while ago. By changing the algorithm a bit it's possible to create various other beautiful images: https://drive.google.com/drive/folders/1TSgLRdO0tKIFUb6Oj8yNJgUeh2D_WA9-?usp=sharing https://drive.google.com/drive/folders/1TSgLRdO0tKIFUb6Oj8yN... Here's a link to my post (unfortunately, in Russian) describing the process: https://t.me/little_pieces/822?single https://t.me/little_pieces/822?single A quick translation: 1. We have a 2D space and a regular shape with N angles, where N is a parameter. 2. Choose a function f : R -> R (e.g. f(x) = x / 2 for Sierpinsky). 3. Choose a random "current" point 4. Choose a random angular point of the N-shape 5. Calculate the distance D between two points. Move the current point to the selected angle point by distance calculated as f(D). 6. Repeat steps 4-5, saving position of the current point on each step, until there is enough data to draw a density map Another person from gen-club[0] (Russian telegram chat dedicated to generative art) made a 3D-version of it[1][2]: [0] https://t.me/gen_c https://t.me/gen_c [1] https://t.me/mathimages/156 https://t.me/mathimages/156 [2] https://codepen.io/strangerintheq/full/ZEKXamr https://codepen.io/strangerintheq/full/ZEKXamr (zoom out at startup)

hardmath123 5y ago
Indeed, you can "learn" (by gradient descent) new parameters to this algorithm, to generate fractals in any target shape that you want! https://hardmath123.github.io/chaos-game-fractal-foliage.html https://hardmath123.github.io/chaos-game-fractal-foliage.htm...

frob 5y ago

I believe this is also the algorithm included in the TI-83 (plus) manual: https://www.manualowl.com/m/Texas%20Instruments/TI-83-Plus/Manual/240607?page=573 https://www.manualowl.com/m/Texas%20Instruments/TI-83-Plus/M... I remember sitting on the floor of our living room programming this in character by character on that TI keyboard. It's the first BASIC program I ever wrote. Everything before that was js and html.

mawise 5y ago
I have fond memories of learning to program on the TI-83 and following that same example!

pfedak 5y ago

As others have pointed out, a generalization of this method (iterated function systems) can generate a large class of fractals. There's a some fun software for generating these ( see https://en.wikipedia.org/wiki/Fractal_flame https://en.wikipedia.org/wiki/Fractal_flame) which also adds coloring based on the sequence of function applications, resulting in a pattern that respects the fractal structure. Going a step further, changing the "functions" over time can create smoothly animated fractals. Electric Sheep (https://electricsheep.org/ https://electricsheep.org/) is a screensaver version of this which doubles as a distributed computing network to generate them. It also mixes in non-linear transformations which makes for some impressive, mesmerizing patterns.

punnerud 5y ago

Video with here: https://imgur.com/1Svgp0G https://imgur.com/1Svgp0G (From the repo)

richm44 5y ago

Here's a version of the same as a BBC Microbot tweet https://twitter.com/bbcmicrobot/status/1333542986588753921 https://twitter.com/bbcmicrobot/status/1333542986588753921

sizediterable 5y ago

I remember there being a section demonstrating this in the manual for my TI-83 calculator [0] It prompted me to learn a bit more about IFS and discover one of my favorite fractals ever. The word "chaos" where each stroke is made up of the word "chaos" [1]. I spent a bunch of time coding up the fractals on that site [2] on my calculator [0] http://manualsdump.com/en/manuals/texas_instruments-ti-83/132084/573 http://manualsdump.com/en/manuals/texas_instruments-ti-83/13... [1] http://paulbourke.net/fractals/ifs/chaos_1.gif http://paulbourke.net/fractals/ifs/chaos_1.gif [2] http://paulbourke.net/fractals/ifs/ http://paulbourke.net/fractals/ifs/

RonInDune 5y ago

The Sierpinski triangle was the first "complex" system I had managed to draw, using the Logo programming language in the 90s. I recently tried to do a vtk 3D extension (Sierpinski cube)[1] using the same process as in the OP, but it was surprisingly computationally expensive! [1] https://en.wikipedia.org/wiki/Menger_sponge https://en.wikipedia.org/wiki/Menger_sponge

arunchaganty 5y ago

The chaos game is one of my favorite things! I first came across it nearly 15 years ago from James Gleick's excellent book Chaos and in fact I learned how to program so that I could actually implement the chaos game. After spending many years idly reflecting on why the chaos game converged to the Sierpinski triangle, I'd like to share an illustrated proof of mine that might be enjoyed by this audience: https://arun.chagantys.org/technical/2020/04/28/chaos-game.html https://arun.chagantys.org/technical/2020/04/28/chaos-game.h...

Nydhal 5y ago

You can make it using Cellular Automata too. Python Code:https://nbviewer.org/github/Nydhal/Python-Notebooks/blob/master/Selmi_Impossible_Fractal.ipynb https://nbviewer.org/github/Nydhal/Python-Notebooks/blob/mas...

jventura 5y ago

I did the same thing, but in Python, some years ago [1]. Never understood how it works, but it's easy to implement.. [1] https://joaoventura.net/blog/2016/sierpinski-triangle/ https://joaoventura.net/blog/2016/sierpinski-triangle/

aimor 5y ago

It's funny, so each point is only guaranteed to be in that iteration of the triangle. So if you want a sierpinski triangle accurate to n levels deep you want to throw away the first n-1 points. If you want to plot a specific sierpinski triangle you have to re-run the algorithm from the beginning to get more points.