Computer Scientist Explains Fractals in 5 Levels of Difficulty

Computer scientist Keenan Crane, PhD, is asked to explain fractals to 5 different people; a child, a teen, a college student, a grad student, and an expert.

Video Transcript

KEENAN CRANE: Hi. I'm Keenan Crane. I'm a geometer and professor of computer science at Carnegie Mellon University. And today, I've been asked to explain fractals at five levels of increasing complexity. So fractals are a sort of strange kind of shape that have detail at all different levels.

Fractals appear all over nature. They rise naturally in computer graphics because we want to make beautiful images of the natural world. Fractals are also really interesting because they show how extremely simple descriptions can give rise to really complex shapes.

What's your name?

MYRA SINGH: Myra.

KEENAN CRANE: Have you heard of fractals before?

MYRA SINGH: No, absolutely not.

KEENAN CRANE: So a fractal is something that we see every day. But it's a little bit hard to describe. It's a shape that if you look at it really far away or you look at it really up close, it has kind of a similar appearance. And actually, that word fractal sounds a little bit like fraction, right?

MYRA SINGH: Yes.

KEENAN CRANE: So actually, fractals are, in some way, fractions but for shapes. Have you ever seen a movie called "Moana"?

MYRA SINGH: Yes.

KEENAN CRANE: Yeah? Moana lives on this beautiful Island, right?

MYRA SINGH: Yes.

KEENAN CRANE: This island has lots of trees on it. Some artist had to make all those trees. How do you think they do that?

MYRA SINGH: They try to find something similar to that on Google. And they try to picture it in their head saying, what would it look like if it was animated?

KEENAN CRANE: So somehow, they have to explain to the computer what a tree looks like, so that the computer can draw the tree for them.

MYRA SINGH: Yes.

KEENAN CRANE: And that's kind of what we're going to try out today. In fact, we're going to have you build a fractal. A tree is a really good example of a fractal. Because, if you look at the whole tree and then you break off a big branch of the tree, it almost looks like that branch that you broke off is itself another tree. So our rule is that every branch splits into two smaller branches.

MYRA SINGH: OK.

KEENAN CRANE: So your tree is totally beautiful. But it took a long time to make, right?

MYRA SINGH: Mm-hmm.

KEENAN CRANE: How would you feel if I said now you have to make 1,000 of those trees?

MYRA SINGH: I would be like, oh my, that's a lot of work.

KEENAN CRANE: Yeah. It's a ton of work. If you think about Moana's island, it has these tens and hundreds of thousands of trees on it. And that's why we need computers to help us out. Because computers are really good at taking these really simple rules like put two branches on every other branch and doing it really, really fast.

MYRA SINGH: I want to know how to draw a fractal.

KEENAN CRANE: On a computer, if you want to learn to draw fractals, then you might need to learn a little bit about programming.

MYRA SINGH: Programming?

KEENAN CRANE: Yeah.

MYRA SINGH: Like coding.

KEENAN CRANE: Like coding, exactly. That's what, actually, a lot of the artists for the movies are working with code rather than with a paintbrush. So in your own words, how would you describe a fractal to somebody?

MYRA SINGH: I would describe a fractal by saying that, when you see an object, if you zoom in closely, you'll see that it's broken down into pieces. So as you zoom in more closely, you'll keep seeing smaller and smaller pieces.

KEENAN CRANE: Definitely. That is totally what fractals are all about.

MYRA SINGH: Yes.

KEENAN CRANE: What are you studying in seventh grade these days?

JENNA EISENHAUER: I think we're doing geometry still.

KEENAN CRANE: What if I told you that there are shapes where you can't measure the length of the perimeter?

JENNA EISENHAUER: It's big. But all of the sides are kind of like so weird that they wouldn't be able to pinpoint anything specific to add together.

KEENAN CRANE: The shape is just super, super complicated. And so you can't actually measure the length. Right. Yeah. So that's already a really good idea of what a fractal is. It has some really, really interesting detail at all scales that makes it hard to talk about standard quantities like lengths and areas and volumes.

MYRA SINGH: Would a planet or an asteroid be a fractal?

KEENAN CRANE: Yeah. So if you look at the wrinkly surface of an asteroid, each one of those little wrinkles adds a little bit to the surface area. And so it's really hard to say, what is the area of an asteroid? Let's take a look at a little example of where fractals actually show up in nature.

What we're going to try to do is we're going to try to say what the length of the coastline of Great Britain is. So we're going to start out with the blue ones, which are spaced further apart. We're going to ask you to connect the blue pins with a piece of string, so we can get a measurement of the coastline.

So we have our first measurement of the length of the coastline. And we're going to do it over again. But this time, we're going to use the white pins, which are spaced closer together. So we measured the coastline again. And what do you think happens?

MYRA SINGH: There's more in and out. Therefore, it probably takes more string for this one.

KEENAN CRANE: I think I agree with you. But I think to really validate our scientific experiment, we should probably compare the length of the string. A lot of extra slack in that pink string. So what we noticed with Great Britain is we were never able to measure its length. It just kept getting longer and longer.

This is called the coastline paradox where there's not really one definite number you can assign to the length of the coastline. But it depends on how you measure it. Like if we kept going to really get this to be accurate, we might have to like actually go down to the beach and start measuring these tiny little details along the coastline. But really, there's so much detail, we would probably never get a definite answer for how long the coastline is.

Fractals also give us a really nice language for talking about how smooth or rough some kind of shape is. And actually, a lot of people, engineers, and scientists use this idea of fractals and this language of fractals to compare different shapes not in terms of their size but in terms of their roughness. So based on everything we talked about today, how would you describe a fractal to somebody in your own words?

JENNA EISENHAUER: It's a shape that you can't describe as a shape.

KEENAN CRANE: Yeah, totally. Like it's a shape that you can't use sort of the ordinary language that we use to talk about shapes. You really need some other ideas or concepts to talk about it.

Do you play any video games?

AKHIL AGGARWAL: I really like "Hearthstone," "Minecraft."

KEENAN CRANE: What happens in "Minecraft" if you get really, really close to a shape?

AKHIL AGGARWAL: Well, it just looks like a block.

KEENAN CRANE: Yeah, it looks really blocky. And it's the same thing not only with shapes in games but also colors and textures. And this is an especially big problem in virtual reality because you have no control over where people are going to go, what they're going to look at, how close they're going to get to various objects.

So fractals, on the other hand, are these things that have infinitely nice detail as you get closer and closer and closer. And so this is something that can help us solve this problem in computer graphics of generating more detail. One of the reasons why fractals are really nice for computer graphics is because the algorithms that we use to draw images also have this kind of recursive flavor. What's recursion?

AKHIL AGGARWAL: Recursion is a function that uses itself or it calls itself in its definition. And basically, with that, you can figure out minute details, such as searching for a value in a binary tree. It's kind of like iterating through itself. But it's often more sophisticated, in that, it's easier to write.

KEENAN CRANE: They're easier for a computer to execute, right? It just has to run this recursive procedure over and over and over again. We can kind of get as much detail as we want or need. When I think about fractals and kind of what they've done for computer graphics, the example I think of is subdivision surfaces. Did you encounter subdivision surfaces in your graphics class at all?

AKHIL AGGARWAL: The name doesn't really ring a bell.

KEENAN CRANE: So subdivision surface is a way of describing a smooth shape on a computer rather than some complicated fractal shape. So meshes in computer graphics are usually made of these flat polygons with kind of sharp edges. And so the question is, how can I get something nice and round and smooth out of these sharp-looking polygons? What I can do is I can start cutting, one at a time, the corners of this paper off. It still looks very angular. I still have these really sharp points.

AKHIL AGGARWAL: Right. Why are we doing this?

KEENAN CRANE: Because I want to draw a smooth curve on the screen. But all my computer can do is draw straight lines. And that's actually true of GPUs. It's kind of interesting. GPUs are basically really fast machines that can only draw one thing and that's a flat triangle. And so we keep doing this with our paper. You kind of get, pretty quickly, the idea of what's going to happen.

AKHIL AGGARWAL: Mm-hmm.

KEENAN CRANE: So when you go to see a Pixar movie, for instance, every surface has been subdivided down, so you have tiny little triangles called micro polygons that are even smaller than the size of a pixel.

AKHIL AGGARWAL: How long does this process take?

KEENAN CRANE: Well, because people really need to use these subdivision surfaces for everything, people worked hard over the years to make this super, super fast. In fact, subdivision surfaces were invented basically at Pixar. There's this guy Ed Catmull. And he was partially responsible for one of the most famous kinds of subdivision surfaces called Catmull Clark subdivision surfaces. And, in fact, recently won the Turing Award for these subdivision surfaces.

AKHIL AGGARWAL: What do you think are the current shortcomings in, I guess, applying fractals to computer science right now? What is the cutting edge?

KEENAN CRANE: So we've talked a little bit about the positive features of fractals in procedural graphics, which is can write one simple recursive program. And the computer creates a lot of detail for you. So that's really nice, right? It's saving you a lot of work.

But the downside is you lose a lot of control. So because the only thing you're describing is this short little program, you don't have complete control over how this is going to end up. And so adding more controllability to procedural graphics is something people have been thinking about for many years. So how has our conversation changed your understanding of what fractals are all about?

AKHIL AGGARWAL: I think it's really interesting to see the different ways fractals will be not only useful but necessary in being able to render these games and these different programs that are interesting in the metaverse or different media to be really beautiful.

KEENAN CRANE: Hey. Thanks for joining us remotely.

HENRY STARMAN: Yeah, of course. It's a pleasure. I'm happy to be here.

KEENAN CRANE: Do you have any sense of how you would give a really precise mathematical definition to what is a fractal?

HENRY STARMAN: It would probably have to be some kind of recursive definition, like imaginary numbers. I know the Mandelbrot set will use those.

KEENAN CRANE: The Mandelbrot set or the Julia set, the idea is always, oh, I'm going to apply some polynomial over and over again, z squared plus c or something like that. When I think about fractals, I try to get away from these very specific examples and ask, what is it fundamentally that makes a fractal a fractal? And one thing that I think you can be precise about, even if you can't really say exactly what a fractal is, is you can talk about this idea of fractal dimension. Have you ever heard of that?

HENRY STARMAN: No. I have not, actually.

KEENAN CRANE: So if you look at this piece of paper, what would you say the dimension is?

HENRY STARMAN: Well, on the paper itself, I would say it's two dimensional. But the actual paper would be three dimensions because it has a very small thickness.

KEENAN CRANE: Yeah. Great. So the real physical paper has some amount of thickness. But when we model this mathematically, we might ignore the thickness and say, yeah, this is really just kind of a two-dimensional sheet of paper. And then you have your apple. How many dimensions is the apple?

HENRY STARMAN: I would also say three.

KEENAN CRANE: And why three?

HENRY STARMAN: Because it has the height and the width. And there's a depth to it as well, totally.

KEENAN CRANE: Now, as a little experiment, take your piece of paper and just crumple it into a ball. So what is it? Is the paper three dimensional? Or is it two dimensional?

HENRY STARMAN: It changed in dimensions, depending on how it is shaped.

KEENAN CRANE: So it's not quite as solid as the apple. But it's also not quite as two dimensional as the original sheet of paper. And so, for this reason, people associate this crumpled ball with a fractal dimension, maybe something like 2.5 dimensions instead of two or three.

There are a lot of different definitions, precise definitions of fractal dimension. But I think the one that's easiest to understand is this thing called box counting dimension. You have, let's say, an image. And you want to decide, what's the fractal dimension of this image?

So what you're going to do is you're going to count the number of boxes, or you can imagine big pixels of this image that cover the boundary of this shape. And you're going to see, how does that counting compare with how the counts work for just an ordinary shape? So if I have a straight line and I start out with one big box that covers the whole line and now I shrink my boxes by a factor of two, I just make boxes half as big, how many boxes will I need to cover that line?

HENRY STARMAN: Two.

KEENAN CRANE: And if I cut that box in half again, how many boxes do I need to cover the line?

HENRY STARMAN: Four.

KEENAN CRANE: But if you take a more interesting shape, some kind of fractal shape like let's say the coastline of Great Britain and you start doing this box-counting experiment, something really interesting happens. As you make these boxes smaller, the number of boxes you need to cover the coastline grows faster than it would for just a straight line.

HENRY STARMAN: Yeah. I've heard about that where if you change the amount of measurements for a coastline, you can actually change how much of the coast that there is. If you measure in mile lengths, you're going to get a much different estimate than if you measure it in one-inch increments.

KEENAN CRANE: And so what this box counting is getting at is saying, well, I still can never decide what the length of the coastline is. But what I can do is I can see, how quick does the number of boxes grow relative to how it would grow just for an ordinary one-dimensional curve, like a line or a circle?

HENRY STARMAN: Is there any other interesting applications of fractals?

KEENAN CRANE: So procedural computer graphics, which kind of came out of thinking about fractals, is one answer to this question about, how do you add more detail without, for instance, consuming tons of memory or requiring artists to paint ultra detailed textures? So if you can, instead, describe at least some aspect of what you're looking at in a procedural or recursive way, then you can add as much detail as you need when you get close to objects.

HENRY STARMAN: Oh, you mean like Perlin noise.

KEENAN CRANE: Yeah, like Perlin noise is a great example. Perlin noise was one of the early ways of synthesizing additional texture at any level of detail that you needed to make things look natural and realistic.

HENRY STARMAN: I have a random question. Do you know how the research into fractals began?

KEENAN CRANE: You can look pretty far back in history to see kind of glimmers of this idea of fractals in science. In the 19th century, people were trying to look for examples of things in mathematics that were very unnatural. So there was, for instance, this guy named George Cantor, who was showing that you can have these sets with really strange properties, or you can have functions with really strange properties, this thing called the devil's staircase and so on.

And it wasn't until about a century later where someone named Mandelbrot said, oh, actually, this strange mathematics that was meant to show how unnatural things can happen is actually a perfect description of things that really do happen in nature. And from there, people really ran with it and said, oh, OK, well, if these fractal descriptions are good for nature, we can also use that for creating really realistic and believable pictures in computer graphics.

KEN PERLIN: I can say that when you reached out to me and I first learned about this program, I immediately went to my computer. And I implemented yet another version of like zooming into the Mandelbrot set just because I was so excited. So that the thing is that it took me maybe 30 minutes. A kid at home who's like 13 and 14 who just starts playing around with a simple computer program can make incredibly beautiful fractals.

KEENAN CRANE: Yeah, for sure.

KEN PERLIN: And I think that's one of the things that's exciting about it.

KEENAN CRANE: Or you don't even need computers. Like I remember when I was a kid, I played electric guitar. And I had all these guitar pedals with different effects. And, oh, what happens if you put the output back in the input and just run it through itself? You're going to start hearing this kind of fractal sound, right?

So today, we've been telling people fractals are things that are somehow self-similar. They have detail at all scales. Are there other ways you might introduce fractals to somebody? Or are there other things you might say, this is what a fractal is?

KEN PERLIN: I think you could get to the reasons. Why does a coastline look like a coastline at all different scales? It's because the forces of nature tend to work similarly at all different scales. And it's those forces that are doing very, very simple things over and over and over again that are constantly creating the sense of detail.

KEENAN CRANE: I think about the scale and variance of different physical equations. Like Navier Stokes is kind of scale invariant. You have this Reynolds number that tells you how viscous things are. But you can have the same kind of fluid behavior at all different scales. And that's why you get turbulence at all different scales.

KEN PERLIN: I actually remember the moment when I finally figured out how to make turbulence in computer graphics. I was working for this company Magi. And Disney was working on a movie. I think it was "Weird Science," where they wanted to have a marble vase.

And then about 3:00 in the morning, I was at a diner nearby. And I was pouring the cream into the coffee. And I was watching it. And I started watching it swirl around.

And I realized that what was happening was really simple. You had this line of cream. And then it hits the cup, and it folds. And then the folds get caught up. And then that folds again. And it's a really simple process of folding within folding.

And I just went to the computer and did that. And things looked like marble and looked like flame. And they looked like clouds. And they looked like-- you just keep using those simple techniques.

KEENAN CRANE: Yeah. And I think it's really cool that this kind of fractal description of geometry or physics is also kind of baked into the nature of computation. Computation is recursive kind of by its nature. And so it's kind of a match made in heaven that we happen to build these machines that also behave the way that nature does.

KEN PERLIN: You just have to understand recursion.

KEENAN CRANE: Exactly.

KEN PERLIN: Somebody once told me that in order to understand recursion, you just have to understand recursion.

KEENAN CRANE: There you go.

KEN PERLIN: And then you get it all.

KEENAN CRANE: Yeah.

KEN PERLIN: But I think it's this point that that point with the coffee is important because the forces were operating at one scale. They're operating at the scale of the coffee cup. But, over time, they kept making details smaller and smaller. Process at one scale plus time, you get fractals.

KEENAN CRANE: I think that's also what's so beautiful about fractals is that, if you think about the history of geometry as well, Felix Klein was looking at geometry by saying, well, geometry is all about invariants. I have some group of transformations. And I look at objects that are sort of invariant with respect to these transformations.

So if you just look at translations, OK, what kinds of shapes remain the same under translations? Well, you get tiling. You get wallpaper. And if you start asking that same question, well, what if I allow scaling in my transformations? Then boom. You have fractals--

KEN PERLIN: Immediately.

KEENAN CRANE: --just come out of nowhere.

KEN PERLIN: I mean, everybody understands scaling. Scaling is a simple thing.

KEENAN CRANE: Yeah. Now you work on the future of virtual reality and augmented reality and extended reality. But it's kind of interesting because I think if I think about exploring these infinite fractal landscapes, in some way, they still feel a little bit lonely. Or they feel a little bit poor of the kind of richness that we have in the real world.

KEN PERLIN: This is where machine learning starts coming in. Because you can start saying, OK, this is a very, very rich virtual world. But it's informed by my favorite mountains that I saw in Italy once. So you can start training these fractal worlds on things about the real world that have particular emotional resonance for us.

KEENAN CRANE: People outside of computer graphics and engineering and science and so forth have also thought a lot about and used fractals as a language for talking about nature, for characterizing shapes and behaviors and so forth, tissue, or friction, or all sorts of really important phenomena. Do you think that computer graphics has kind of dropped the ball in terms of saying, this is not something that's exciting anymore to work on procedural descriptions, and we're moving on from that?

KEN PERLIN: Well, I mean, if you look at any Hollywood movie or you look at any of the game worlds that people are spending all their time in, they're highly procedural. They have to be. And they have to make use of fractal techniques because it's basically a way to get enormous complexity without having to explicitly store the complexity. And because they're able to use these relatively simple fractal techniques to make very complex looking natural things.

KEENAN CRANE: Right. Lazy evaluation. We love being lazy in computer graphics.

KEN PERLIN: Well, it's also it's not even possible to explore, to store an entire world in your computer.

KEENAN CRANE: Absolutely.

KEN PERLIN: You want to be able to generate it on the fly. I'm looking forward to things getting better. We're not there yet.

KEENAN CRANE: So one of the things, I guess, that touches on is this question about controllability or the ease with which everybody can create these worlds, not just people, not just mathematicians, not just trained computer scientists. One thing when I think about Ken Musgraves work about this program Bryce, this one, I felt like I could really use. What do you think we still need to do in terms of putting these kinds of tools in people's hands, making it easier for people to use proceduralism, machine learning to build these kind of worlds?

KEN PERLIN: I think, in that case, it came down to the fact that Ken, in particular, had a mission to make accessible tools for people without sacrificing the power and the richness of making beautiful things. I mean, in a sense, he was kind of the computer graphic Bob Ross.

KEENAN CRANE: Mm-hmm.

KEN PERLIN: You know? So you too can do this.

KEENAN CRANE: Yeah, he made the land of happy little trees. Yeah.

KEN PERLIN: Yeah. Which, I mean, when you think about the techniques of somebody like a Bob Ross, they're fractal.

KEENAN CRANE: Yeah. And I think this is what's so beautiful also about Mandelbrot's work is him saying it's not really about these exotic examples. Like even the Mandelbrot set or Julia sets or whatever, yeah, they're like really interesting mathematical curiosities. But they get at this idea that fractals are kind of inevitable. And Bob Ross probably never, as far as I know, never sat down and thought about recursive descriptions of trees or anything like that. But it's just something that naturally comes to you as an artist.

KEN PERLIN: Well, I mean, you can go back to all the classic artists. da Vinci's notebooks were just full of this thing looks like that thing at completely different scales. So he didn't have a fancy word for it. But he completely understood it.

KEENAN CRANE: Yeah. It's really part of human nature or human's connection to nature.

KEN PERLIN: Yeah.

KEENAN CRANE: Hopefully our discussion today has helped you see the world in a different way and also see how mathematics and art can come together to make beautiful images. I hope it's inspired you to look at the world around you in a different way.