Placeholder Image

Subtitles section Play video

  • (bell dings)

  • - Hello, welcome to a coding challenge.

  • I actually just finished this coding challenge,

  • and I'm coming back to re-record a little intro to it.

  • And what I made in this

  • coding challenge is a drawing machine.

  • Maybe let's call this a Fourier transform drawing machine.

  • There's a few more things we want to do with it.

  • There's going to be some followup videos.

  • But this very, very long video, if you can stand

  • to watch it, has, as part of it, at the end, this.

  • This is the end result.

  • I am using an algorithm called Fourier Transform

  • to take an arbitrary signal, in this case, a sequence of X's

  • and a sequence of Y's, the path of the Coding Train logo,

  • thank you to Tom Fevrier.

  • I will link to Tom Fevrier's Twitter, who provided

  • the path for this particular logo, to trace

  • the path of the logo through this sort of sequence

  • of rotating circles, sometimes referred to as epicycles.

  • Okay, so what's going on here?

  • So, first thing I should mention is this is

  • a continuation of my coding challenge Fourier Series.

  • And so, what I did in that particular coding challenge,

  • which was inspired by a Smarter Everyday video on the same

  • topic, was create the Fourier series for a square wave.

  • I don't know why I just had to write that.

  • But in this video, I'm going to do something different,

  • which is I'm going to use the Fourier transform algorithm.

  • And these are different concepts.

  • I somewhat conflated these in my previous video.

  • The idea of the Fourier transform.

  • Now, where I know this algorithm from, where I learned

  • about this algorithm first in like, learning about coding

  • and creative coding and new media and sound and video

  • is with the terminology FFT, and actually,

  • if you go into the p5 sound library, you'll see

  • there is a class or function called p5.FFT.

  • I don't remember exactly what it's called,

  • but something like that.

  • The F here stands for fast, Fast Fourier Transform.

  • The algorithm I'm going to implement,

  • by the way, is discrete Fourier transform.

  • Why is this FFT thing, where is it typically used?

  • Well, it's typically used in, it's in signal processing,

  • but a familiar place where you might find that

  • is in audio signal processing.

  • So let's say you have some arbitrary sound wave

  • that maybe looks like this, and it has a really

  • high-pitched, awful, screeching sound in it.

  • How would you filter that out?

  • Well, if you could take this sound wave pattern

  • and break it into a bunch of smaller sound waves,

  • a bunch of sound waves that have varying

  • amplitudes and frequencies, then you could take,

  • you could sort of remove the one that has

  • the high-pitched sound in it and then

  • add them all back together and get a new sound wave.

  • So the idea of a Fourier transform, I think I said this

  • in the Fourier Series, but it's unsmoothie-ing a smoothie.

  • If we could take a smoothie that's made with blueberry,

  • mango, and strawberries, and like, separate it out

  • and then put it back together without the strawberries,

  • this is essentially what happens in signal processing.

  • But in this video, what I'm going to do is

  • instead of the signal being an audio, it's going to be

  • a series of X values or a series of Y values,

  • and eventually, there actually a way to do that

  • with the X, Y values together that I will get to.

  • So, I am not going to go too deep into the math

  • in this particular video.

  • I'm not going to derive the Fourier Transform algorithm.

  • I'm not going to talk about Fast Fourier Transform.

  • I'm just going to use a very crude, discrete Fourier Transform

  • implementation just to get the thing working.

  • If you want to know more about the math, though,

  • let me reference a few really key references.

  • The 3blue1brown video, But what is the Fourier Transform?

  • will give you an infinitely better understanding

  • of what the Fourier Transform algorithm is

  • and what it does, and even how it works, way better than my

  • trying to ramble through that over on the whiteboard.

  • I would also highly recommend this GoldPlatedGoof video,

  • Fourier Analysis for the Rest of Us, which goes

  • through the details of the math in a much deeper way,

  • and then there's this wonderful video from Mathologer,

  • Epicycles, complex Fourier series and Homer Simpson's orbit,

  • which will give you the full story of everything

  • that I'm trying to do.

  • But hopefully, what's useful to you that's different

  • in my video than from these is I'm just going to sit here

  • and attempt to code the thing.

  • And I know that it's going to work, because I already did it,

  • and here is the result.

  • So enjoy.

  • This is a very long video.

  • I hope that if you watch it, you get the code,

  • you make your own variation of it, please share it with me.

  • You can go to thecodingtrain.com, to the particular

  • coding challenge page, and then there's instructions

  • on how to submit a user community variation thingy there.

  • Okay, goodbye, enjoy, or not, or whatever.

  • I am ready to start coding, finally.

  • Now, this is where I left off before in my Fourier Series

  • coding challenge, and the difference now is

  • what I want to do is be able to have an arbitrary signal

  • and then compute what all of these amplitudes

  • and frequencies and phases should be.

  • So, the way that I'm going to do that is,

  • so let's think about this.

  • This is really a bunch of Y values that I'm calculating.

  • So let's make an array called something like Y,

  • and this is going to be the signal, this is my signal.

  • This could be audio, it could be Y positions,

  • any arbitrary digital signal/array of numbers.

  • Then what I want to do is I want to have

  • like, the Fourier transform of that particular signal.

  • So I want to say, fourierY = fourierTransform, or maybe

  • like dft, discrete Fourier Transform, of the Y value.

  • So this is the idea.

  • The first thing that I need to do is compute

  • the discrete Fourier transform of an arbitrary signal.

  • Now I need some kind of signal.

  • So I think what I'm going to absurdly do

  • is hardcode the signal.

  • Let's actually make it the square wave,

  • and then we'll know if it kind of worked.

  • So what is the square wave?

  • Square wave would be something like 100, 100, 100,

  • - 100, -100, -100, and then like, do that a few times.

  • So this is going to be my arbitrary signal,

  • which I'm just hardcoding the square wave.

  • And we'll do some interesting things that we might,

  • maybe I'll try a Perlin noise signal

  • or just a sine wave signal.

  • We'll try different things,

  • random numbers, and see what that does.

  • So then, this actual code here can largely stay the same,

  • 'cause in theory, the difference is now,

  • instead of following the specific Fourier Series

  • for the square wave, I just need to take

  • the results of my discrete Fourier transform.

  • So this would be a loop that's going to

  • go through the length of that transform, how many

  • different wave patterns are there that I'm adding together,

  • and then this ultimately, I'm going to have to figure out.

  • So let's comment this out right now,

  • and there's a little bit of an issue where I have

  • this x and y as like, local variables here.

  • But let's, I think this will be okay.

  • So let's refresh this, and DFT is not fine.

  • Okay, step one, let's write

  • the discrete Fourier Transform algorithm.

  • So, I'm going to start by making a function called dft.

  • It's going to have some array of values, and now,

  • I need to, at the end, I need to return something.

  • (laughs)

  • The idea is that I will return

  • the discrete Fourier transform of those values.

  • So, a couple things.

  • One is I highly recommend, if you want to pause

  • this video right now and read this particular article

  • on the Algorithm Archive

  • by James Schloss or the LeIOS YouTube channel.

  • This is a really nice article about Fourier transforms

  • and the discrete Fourier Transform algorithm,

  • and this particular algorithm for FFT.

  • But what I'm going to do is I'm just going to follow

  • exactly what's here on the Wikipedia page.

  • So, my signal is x sub n, lowercase xn.

  • So what I need to do is basically,

  • and the transform is capital X sub k.

  • So I need to write a function that computes

  • this exact equation and returns it as an array,

  • and this is exactly what I'm going to do.

  • This is exciting.

  • Now, one thing I should mention is that

  • in order to work with Fourier transforms,

  • I need to understand something called a complex number.

  • Now, if I recall correctly, the last time a complex number

  • came up on this YouTube channel was probably in my

  • Mandelbrot set coding challenge, where I visualized

  • the famous Mandelbrot fractal, and I referenced something

  • called an imaginary number, and I was way too informal

  • and loosey goosey and jokey

  • about how I talked about imaginary numbers

  • being this pretend thing that doesn't exist,

  • which is absolutely incorrect.

  • The reason why the term imaginary is used

  • is because there is no real number solution

  • to the square root of negative one, but the square root

  • of negative one is referred to in mathematics as i.

  • I is a complex number.

  • A complex number is a number with both a real, a,

  • plus an imaginary component.

  • So it's two real values, a real value

  • and another real value kind of multiplied by i,

  • the square root of negative one.

  • So, this is the idea of a complex number, and by the way,

  • another way for me to refer to a complex number

  • is by its position on the complex plane.

  • So if this were the real axis,

  • and this were the imaginary axis, this would be a,

  • and this would be b, and this is a vector representation,

  • whoa, of this particular complex number.

  • So, why do I bring this up?

  • The reason why I bring this up is that the Fourier Transform

  • algorithm, even if I start with an array of real numbers,

  • single numbers, I'm going to apply the Fourier Transform

  • and get out a complex number.

  • What I'm going to return from that function

  • is both a's and b's, otherwise known as the real component,

  • which is often written in code as re,

  • and the imaginary component, which is often written as im.

  • So this is one bit that I really need to understand

  • before working with this formula.

  • So now is this moment, this moment that happens to you

  • in life, where you see one of these formulas

  • on a Wikipedia page or in a math textbook,

  • and you're a creative coder making some

  • kind of visualization thing, and you just want to stop.

  • But together, you and me, we're not going to stop.

  • We're going to figure out how to translate all this

  • notation and symbols and stuff into JavaScript code.

  • Now, again, it'll be super interesting to go down the rabbit

  • hole of deriving all these formulas and the background

  • for how Fourier transform works, but I'm not going to do that.

  • If you look in the video description,

  • there are several excellent videos and resources

  • linked to that will give you that background.

  • But I do want to mention one thing, which is quite important,

  • which is that this particular formula in the top here

  • for the discrete Fourier transform uses this symbol e,

  • Euler's number, or the base of natural law.

  • This is a very famous number in mathematics, much like pi,

  • but there's also a very well known formula

  • called Euler's formula, which looks like this:

  • e to the i, which, complex number i, x, equals

  • cosine of x plus i times sine of x.

  • Really interesting, kind of looks like polar

  • to Cartesian coordinate transformation.

  • All this stuff is interrelated, right?

  • But so, that is where, if I come back to here,

  • this is where we get the second line here, using

  • Euler's formula from the particular formula that's up top.

  • But this is the one that I want to implement,

  • and I have written the formula out right over here

  • so we can unpack it a little bit.

  • What are the components we need to understand?

  • Now, really, if this were a math lesson

  • about Fourier Transform, we wouldn't be using

  • summation; we would be using integration.

  • But because we're working on a computer,

  • and I need to write a loop, and I don't have infinity

  • as a tool that I can just use, I need to,

  • instead of doing integration, do summation, and that's

  • why also this is called discrete Fourier transform,

  • 'cause I'm doing it over this sort of like, discrete space.

  • Okay, so this means summation.

  • So this should give you clue that I can just do

  • like a for loop, going from zero all the way up to n.

  • And by the way, n is going to be the length,

  • the number of values I have in my signal,

  • so the length of that original array.

  • Oh, and then the other thing that's really important

  • is that basically what I get to do is separate out.

  • This is the real component,

  • and this is the imaginary component.

  • So even though this is all written as one formula,

  • I'm going to sum up all the real components

  • and all the imaginary components together.

  • And by the way, as Simon, who has been watching this live,

  • pointed out to me, there are only complex numbers.

  • The term imaginary, it's really too bad that it's called

  • imaginary, 'cause it's very misleading.

  • But a real number is just a complex number

  • with the imaginary component as zero.

  • Okay, so, I should be able

  • to start writing the code for this now, right?

  • This is my signal.

  • It's a little confusing that this is called X,

  • 'cause I called it Y, but this is just the values, the vals.

  • This n is vals.length in my code, and then, k,

  • we're going to have to work out what k is.

  • I know what cosine is, two pi, and all these things.

  • So we're going to work out what k is.

  • Oh, boy, I'm so silly.

  • What is k?

  • This should actually, this is, this is,

  • I completely forgot to write what is quite possibly

  • the most important part of this formula

  • (instructor laughs) over here,

  • which is capital X, big X, sub k equals.

  • So, this is what I'm trying to calculate.

  • I'm trying to create an array of k elements.

  • At each element k, I'm going

  • to sum up n from zero to the end.

  • So there's a little bit of a nested loop going on here.

  • I want to loop through every k, which is going

  • from zero all the way up to n, and then also sum up.

  • So k is going to stay constant within each one of these,

  • and k is actually really the frequency, we'll see that,

  • the frequency of the particular wave pattern in that slot.

  • Okay, all right, so let me write the code for this.

  • The first thing that I want to do is create an empty array.

  • This is where I'm going to store all of the results.

  • Then I need to write a loop, which is let k = 0; k < N; k++,

  • and then I'm going to be saying fourier[K] = something.

  • So, this, by the way, I mean, I could call this capital X

  • if I wanted to be, and maybe I will,

  • just to follow this notation exactly.

  • So this is capital X; this is lowercase x.

  • So let's actually, as silly as this might be,

  • let's change this to x so I can use

  • all the same notation as that formula.

  • So, I'm trying to calculate this.

  • Now, in order to do this, I need to,

  • for each one, go through N.

  • So this is where the nested loop comes in.

  • To calculate each element of capital X[k],

  • I need to sum up n going from zero to the n, okay?

  • And then, I'm going to start doing this formula, okay.

  • So, I need to sum up what?

  • I need to sum up both a real component

  • and an imaginary component.

  • So let's make a real component and an imaginary component.

  • The real component is going to go up by some amount,

  • and the imaginary component, ooh, I do not want to ask Siri.

  • Actually, Siri, please, could you help me

  • with this Fourier transform problem?

  • Just write the code for me.

  • So I'm going to sum up the real and imaginary components,

  • and then, I'm going to make some object,

  • which is basically just, what's that thing called

  • where, but I'm not going to worry about it right now,

  • the fancy ES6 way of making an object, if I'm doing this.

  • So then I'm going to make an object that has the real

  • and imaginary components, and I'm going to return it.

  • There we go.

  • So this is the process, whoo.

  • I could use, HollowBrian in the chat

  • is saying use a p vector.

  • I could certainly use a vector object,

  • but I'm going to write it this way.

  • Okay, so here we are, good, good, good, good, good.

  • That's my, I've got this and this.

  • Now I just need to add this stuff in there.

  • So let's do the real component first.

  • Now, one thing you might notice, this appears twice.

  • So if anything ever appears twice,

  • that might give you a hint to just put that in a variable.

  • So let's do that.

  • So let's say, I don't know what to call that.

  • I'm going to just call that something.

  • (instructor laughs)

  • Somebody give me an idea what to call it.

  • I'm going to say TWO-PI times k times n divided by n.

  • All right, so the chat's telling me to call it angle

  • or some angle name, but actually, phi is a good one,

  • 'cause it's the value that's going into cosine and sine,

  • which is like an angle, or a Greek letter phi is often used.

  • So I'm going to call it phi, and then I'm going to say,

  • the real component equals, and I'm looking over there

  • 'cause that's where my formula is written,

  • is going to say x[n] times cosine of phi.

  • Boy, this should look strangely

  • like a lot of code that I write a lot.

  • And then, x[n] times, and this should say cosine,

  • times sine of phi, but one thing you'll notice here

  • is that this, there is a minus here.

  • This minus here is not, is quite an important detail.

  • So, what I'm going to do is I don't know the best way

  • to handle this, but I could just say minus equals,

  • but maybe I'll, yeah, let's just say minus equals.

  • Let's do that, okay.

  • And then, this is called enhanced

  • object literals, thank you.

  • I can just say this.

  • So this will give me that, and there, okay.

  • So, (instructor laughs)

  • all of that explanation, wow, and here we are,

  • discrete Fourier transform.

  • All right, so thank you to the chat for asking

  • a couple key questions and for pointing out some errors.

  • For example, I forgot to actually define what n is,

  • which is x.length.

  • You know, I should probably get in the habit

  • of using the variable declaration const when I know it's

  • something that's going to stay a constant like this,

  • so I will attempt to use that here.

  • These cannot be const, because I'm adding them up together.

  • Now, another thing that is typically done

  • with discrete Fourier transform is to take the sum,

  • and then average its contribution over n.

  • So I would also say the real component equals

  • the real component divided by n.

  • The imaginary component is

  • the imaginary component divided by n.

  • So I'm going to add that in.

  • And then someone asked me, well, oh, but this is

  • another question that came in, which was

  • the question, oh, there's i here.

  • Why don't I see i in your formula, in your code?

  • Where is i in your code?

  • And so, i isn't explicitly in here,

  • but what I'm doing, I'm referencing i

  • by separating out the real and imaginary components.

  • So, the imaginary component is always paired with i,

  • and the real component is in the form a + bi.

  • So this is a, that's b, but I don't actually

  • have to put i in the equation itself.

  • So, let's save this.

  • Let's feel happy that we completed something.

  • I'm going to refresh, I'm going to go back to my code page.

  • So let's just see if that function dft does something,

  • it doesn't actually produce an error.

  • So I have the y array, which is my hardcoded square wave,

  • and if I call dft on y, here in the console,

  • we can see, I get, right, I had 12 values in my signal.

  • I get 12 complex numbers back,

  • each one with a real and an imaginary component.

  • So this looks good, in the sense

  • that there are numbers here.

  • I don't see an error, no red, no not a number.

  • So hopefully, we're in the right place.

  • Now, the question is, what, what, what do I do

  • with these real and imaginary components?

  • How do those things actually become circular epicycles?

  • For a circular epicycle, what do I need?

  • I need an amplitude, right.

  • That's basically the radius of that circle.

  • I need a frequency, which is how many cycles

  • through the circle does it rotate per unit of time,

  • and then I also need, this is what's called a phase.

  • And the phase, another way is think of it as an offset.

  • So where does the cycle begin?

  • Where does that circular wave pattern begin?

  • That's the phase.

  • So I need these three things.

  • So, somehow, what I need to be able to do is I need to be

  • able to say right here, well, the frequency is something,

  • the amplitude is something, and the phase is something.

  • And the secret to this lies in the fact that a complex

  • number is like a vector, and in fact, here we go.

  • The amplitude is the length of that vector,

  • and the phase, is the angle of that vector.

  • Well, so that's amplitude and phase, but what's frequency?

  • Well, guess what?

  • I don't know if there as a clue to this on that

  • Wikipedia page, but the frequency is actually just k.

  • Frequency, yeah, discrete frequency components.

  • So the whole point of doing this is to take the signal

  • and divide it into a bunch of discrete frequency components,

  • zero, one, two, three, four, et cetera.

  • So, here we go, frequency is k, and that's a little bit

  • redundant, but I might do something with sorting later,

  • so I'm going to need to keep track of that.

  • Amplitude is the square root of the real times real

  • plus imaginary times imaginary.

  • This is basically the magnitude of a vector,

  • the square root of each component squared.

  • This is Pythagorean's theorem at play.

  • And then the phase is that angle, which I can use the atan2,

  • and the y would be the imaginary?

  • I think it's this.

  • I'm going to just reference the code that I wrote before.

  • (instructor laughs) Yes, I got it right.

  • So this would be the phase.

  • So now, I can add frequency, amplitude, and phase here.

  • And I can refresh this page, I can say dft(y),

  • and let's take a look at any one of these,

  • and we can see all right, I've got an amplitude,

  • I've got a frequency, I've got a phase.

  • Whoo!

  • We are ready.

  • We are ready to start actually

  • now putting this into our code.

  • And the good news is, we have the code

  • for drawing these epicycles already.

  • I commented it out.

  • It was right here.

  • So, if, in fact, I have this fourierY array,

  • I have this code from before that

  • was drawing the results of those epicycles.

  • So, I can comment this all back in, but now,

  • it's not a specific Fourier series for the square wave;

  • it's whatever's come out of my Fourier transform.

  • And in this case, n is actually,

  • it's confusing that I'm using n here, but I'm actually

  • going to just call this frequency, is fourierY.freq,

  • and the radius is fourierY times amplitude,

  • and now, not times, is the amplitude.

  • So the frequency is the frequency,

  • the radius is the amplitude, and now I can say

  • multiply time times frequency plus that phase.

  • So, and I know I could have, I could get these things

  • out into a variable in like, one line,

  • but I'm just going to write this in here, phase.

  • So, all the code remains the same.

  • The difference is what I'm going to do.

  • Time is the that's moving forward, right?

  • It's the angle, and if the frequency is one, it takes

  • one unit of time for it to rotate a full rotation around.

  • Phase is the offset and radius is the amplitude.

  • So, one thing that I have to be very careful about here

  • is that I can't just arbitrarily have this 0.05 thing here.

  • What I need to do is I need to have like, the value dt.

  • What is the amount of time I move each frame of animation?

  • This would be TWO_PI being a full cycle

  • divided by how many frequency values I have.

  • So now, time goes up by this, and we should see now,

  • dare I say, (instructor laughs)

  • nothing?

  • (bell dings)

  • Oops, I have a terrible error here, ah!

  • I forgot to put index i here.

  • I've got to pull out, right, I'm getting the frequency,

  • amplitude, and phase of each element of the array fourierY.

  • Whoops, sorry about that.

  • There we go, all right.

  • So this looks kind of like maybe it's right,

  • but it doesn't look right at all.

  • Like, something's happening

  • that's pretty decent, but it's wrong.

  • So here's the one thing that's

  • a little bit unfortunate. (instructor laughs)

  • I'm off my 90 degrees here, I'm pretty sure.

  • So let's just add HALF_PI in here, because, and there we go.

  • Now, (instructor laughs)

  • this is actually correct!

  • This is sort of crazy, though, 'cause it's kind of like,

  • is this really, what we're doing?

  • The thing is I have so, I have so few values.

  • So it would make more sense for me to actually count,

  • to precompute some kind of more interesting signal.

  • So, let's forget about hardcoding the signal for a second,

  • and let's just say I'm going to have a signal with a hundred

  • values, and let's just make them all random numbers.

  • This is going to be a little bit insane, probably,

  • but let's pick a number between negative 100 and 100.

  • So you can see, look at this.

  • This, there it is!

  • This is the crazy set of epicycles

  • to draw these random numbers! (instructor shouts)

  • I could also now do Perlin noise instead,

  • and like, just have it increased by some arbitrary amount.

  • All right, so there we go.

  • I'm kind of doing nonsense here.

  • But the point is, any arbitrary signal that I have,

  • I can now compute the Fourier.

  • And you can see, by the way,

  • this is it cycling back to the beginning.

  • That's why it almost looks like this crazy heartbeat,

  • and there's this extra bit here of it,

  • like the first one not rotating at all,

  • just with this offset up, because the values itself

  • don't perfectly average a round zero.

  • But this is not the point.

  • This is not the point of what I want to do.

  • The point of what I want to do,

  • and let me just show you to be clear.

  • If I just made this like i, like a linear function,

  • you can see this, look at this.

  • These are all the epicycles for basically now,

  • I've got the triangle wave, 'cause it's going down and then

  • back up at the top and down repeating over and over again.

  • Okay, (instructor claps and laughs)

  • We are getting somewhere.

  • Okay, deep breath.

  • First thing is, in my excitement and exuberance over what

  • I've accomplished, I was calling this a triangle wave.

  • You know, there's kind of a triangle there.

  • This is a sawtooth wave,

  • which is what I've recreated right here.

  • But, I need to take a breath here

  • and talk about what the next step is going to be.

  • The idea now is what I want to do is I want

  • to be able to draw an arbitrary path, which,

  • in addition to having Y's, I want to have X's as well.

  • So I need to do the Fourier transform twice.

  • Now, ultimately, there's another way of doing this

  • where I do one Fourier transform on a set of complex numbers

  • where the real and imaginary components

  • are the X's and the Y's, but I'm going to stick

  • into this sort of like, simple place that I am right now,

  • and I am going to add two signals now, an X and a Y.

  • So I need the transform for both the X and the Y.

  • I'm just going to like, in a sort of silly way,

  • have the X's and the Y's be the same,

  • and then I'm going to apply the same exact

  • Fourier transform to both the X's and the Y's.

  • And now, here's the complicated part.

  • This loop here is visualizing the results

  • of the Fourier transform as a sequence

  • of rotating circles, epicycles.

  • So what I want to do though is, I think what's going to be good

  • is to refactor this, not later, but now.

  • (upbeat disco music)

  • ♪ I will refactor this later

  • - And put this in a function.

  • You know I will refactor this later

  • - Let's call it epicycle.

  • ♪ I will refactor this later

  • You know I will refactor this later

  • - So the idea is that maybe I would get an X and a Y.

  • Like, what's where it's going to start, and then,

  • I get the set of epicycles, and I draw them all.

  • So this is a generic fourier[1].

  • So in other words, the idea being that I could say,

  • and I'm going to get rid of this translate, and I'm going to say,

  • basically, what I want to be able to say

  • is like, draw, what did I call it?

  • Draw Fourier?

  • No, I called it epicycles.

  • Epicycles, like 100, comma, what's the size of this?

  • Windmill at 200, a fourierX, and the epicycles,

  • you know, 300, 200, fourierY.

  • So we should see both of these now.

  • Let's take a look.

  • Epicycles is not defined.

  • Oh, I don't know why I did this capital C.

  • That's probably unnecessary.

  • Okay, great.

  • So we can see, look.

  • So those are, and now, the epicycles are the same,

  • 'cause they have the same values.

  • Let's give them different values.

  • So let's actually, let's do something kind of goofy.

  • Let's make it draw a circle.

  • So this is going to be 100 times cosine of, this is

  • so silly, of an angle, and that angle is map(i),

  • which goes from zero to 100 to zero to TWO_PI.

  • This is just so I can have some kind of path to work

  • with that's like, very recognizable,

  • so I know whether it's working or not,

  • and then Y will be the sine of that.

  • So we can see, okay, this looks promising, right?

  • Now we can see here are the epicycle calculations

  • for the X's and the Y's.

  • Now, one thing that's off, though, is that,

  • remember how I had to like, I kind of like, glossed

  • over this, but I was like, had the thing on its side?

  • This HALF_PI is really like the rotation

  • of the whole thing, of how I want to display it.

  • So let's make that an argument here,

  • and we'll call that rotation.

  • And so the Y's, oh, that's when I, do I want it?

  • Yeah, I think I can just do that

  • when I draw it, that's fine.

  • Where is this now? (instructor laughs)

  • The Y's should be off by HALF_PI, and the X's should not be.

  • And so now look at this.

  • Okay, so in theory now, (instructor laughs)

  • we're getting somewhere, don't worry.

  • What I want to do, let's position this over here, and then

  • let's position this a little bit further over in here.

  • And now what I want to do is over there, where that

  • mouse pointer is, I want to take the Y from here

  • and take the X from there and draw the path.

  • So, instead of wave, I was drawing a wave pattern,

  • I now want an array that is the full path.

  • I want to basically get the end result.

  • So let's have this epicycles function return,

  • it should return a value which is a vector.

  • createVector with x and y.

  • So whatever the end result, like the last x and y point,

  • the end of that epicycle sequence, and then, so I have

  • vx is this, that's the vector for the X's,

  • and vy is that, and now I want to say, path.unshift.

  • Okay, so I want to create a new vector.

  • This is like, where I want

  • to draw the thing, I need a vector,

  • which is the x component of vx and the y component of vy,

  • and then I want to put that in the path, and then this,

  • let's get rid of this line for a second.

  • I'm going to, instead of drawing this wave,

  • I'm going to iterate over the path.

  • I don't know if I've, this is a little bit

  • of a strange refactoring of what I had before,

  • but I think it's going to make sense to you in a second.

  • Let's see.

  • I might have to come back and explain this.

  • (instructor laughs) Let's put this in here.

  • And wave is not defined, because it is path, path.

  • I'm not going to worry about this right now.

  • Let's kick that out.

  • All right, it's over there.

  • Oh, it's in the wrong spot. (instructor laughs)

  • So, this is actually correct.

  • I just put the, now I realize, like,

  • (bell dings)

  • this is correct; I just put these in weird places.

  • Like, I want the one that's doing the Y over here

  • and the one that's doing the X over there.

  • I don't know why it just like intuitively

  • didn't put them in the right place.

  • So this should be 400, 50, and this should be like, 50, 200.

  • This has nothing to do with Fourier transforms.

  • It's just the weird way.

  • There we go. (instructor laughs)

  • So, I wanted to see them like this.

  • So now you can see, those are the Fourier transforms

  • for this particular circle, and let's add

  • a line back in now, which is basically this thing.

  • So I also want to draw a line from the vx.vy,

  • oh, so, vx.x, vx.y, to v.x, v.y.

  • Like, I just want to draw these two lines,

  • and the the same thing from the y.x and the y.y.

  • Wow, my naming is wildly confusing here.

  • So this could definitely use some refactoring, but.

  • There we go.

  • Now we can see those lines.

  • So this is good.

  • Now, I don't like the way this is spaced out,

  • so let's, one way to fix that would just be to make this

  • thing smaller, and that sort of helps me a little bit.

  • But this can move over.

  • I don't know why I put it all the way over there.

  • Let's move this over to 300.

  • Okay, this is a little bit better.

  • Now, let's make something more interesting here,

  • which is, (instructor laughs)

  • let's start using Perlin noise again.

  • So I'm going to say noise and noise,

  • plus some arbitrary amount, and we can see, look at this.

  • So you can see that this works, and let's give it,

  • let's make the amplitude bigger, and let's give it like,

  • 500 values, whoops, and there's also no reason why.

  • This is very silly.

  • These should just be in one loop.

  • But let's give it more values, and let's just say,

  • you know, i divided by 50.

  • I'm just doing arbitrary stuff,

  • 'cause the whole point of this is to do a drawing.

  • All right, but we can see how this now will take

  • any arbitrary signal and compute the Fourier transform

  • for the X's and Y's and draw that path.

  • (instructor claps) Now, the nice thing about this

  • is I'm about to almost instantaneously

  • do something to make this much more interesting.

  • I am going to go and grab the Coding Train logo path.

  • The whole point of this is forget about computing a path.

  • I want to have a known path, a drawing.

  • (bell dings)

  • I am back, and I have brought in a JavaScript file

  • that just has a big array of X's and Y's,

  • all in a variable called drawing, which is

  • the continuous path of the Coding Train logo.

  • Thank you to, I'll link to Tom Fevrier on Twitter

  • for sending me this particular path.

  • So what I'm going to do now is if I go to the code,

  • we've done all of this work for this moment.

  • (instructor laughs) Oh boy, this better work.

  • I'm so excited.

  • I'm going to go here, right, and now, I'm going to say,

  • I mean, this is a little bit silly,

  • the way I'm doing this, by drawing.length, i++.

  • I'm going to go through, right?

  • Remember, this variable, drawing, is just an array of X's

  • and Y's, and I'm going to make the X's drawing[i].x,

  • and the Y's, drawing[i].y.

  • Now, here's the thing.

  • I happen to know that the complexity of that drawing

  • is way more detailed than I need,

  • and it's going to run very, very slow.

  • So I'm actually going to add a variable called skip,

  • and I'm going to like, skip every 10, and I'm going to say

  • += skip, and then I'm going to change this to push.

  • So I'm going to skip and only do

  • every five vertices of the drawing.

  • I'm doing this in advance, 'cause I already know,

  • looking at that, I don't need that many points.

  • So this should now give me all of the points,

  • all of the X's and Y's, from that particular drawing.

  • (instructor laughs)

  • (drum roll)

  • I'm about to go hit refresh, and hope that this works.

  • (instructor laughs) There it is!

  • (dramatic fanfare)

  • So there it is.

  • Now, this doesn't look as beautiful as it possibly could,

  • and there's a couple reasons for that.

  • Right now, one thing is, these look like these

  • weird alien creatures, by the way,

  • but it would be really nice to have the epicycles

  • render in order of amplitude.

  • So right now, they're rendering in order of frequency,

  • and it's like this strange machine,

  • almost like, drawing machine.

  • It would be amazing if someone could build this physically.

  • But what I'm going to do is sort them.

  • So, I'm going to say fourierX.sort, and fourierY.sort.

  • Now, the JavaScript sort function allows you

  • to pass in a callback, which is essentially a function

  • that tells you how to compare each element,

  • and I want to compare them by amplitude.

  • So I can actually say, any two arbitrary elements,

  • and I'm going to use ES6 syntax for this.

  • If you haven't watched my arrow syntax

  • or higher order array videos, this is something

  • that will give you background for this.

  • And then I can just say, I think a.amp - b.amp, right?

  • Because if I get a positive number,

  • it'll put one in front of the other.

  • If I get a negative number, it'll put the other one.

  • If they're equal, it'll leave them.

  • So this is sorting each one of those by amplitude,

  • and if I refresh this, oops, sorry,

  • the smallest one is, I sorted it in reverse order.

  • So let's put b there, b here, a here,

  • and let's also give myself, let's clean up some stuff here.

  • Let's make this 800 by 600.

  • Let's set the offsets to width divided by two, 100,

  • height divided by two, whoops, sorry, 100,

  • height divided by two.

  • Let's set these offset a little bit more.

  • Let's refresh, whoops, let's shrink this up,

  • and let's move this down a little bit.

  • Will this work? (instructor laughs)

  • All right!

  • (bell dings)

  • (train whistle toots)

  • This is the thing finished!

  • 72 hours later, there it is.

  • Oh, it's off the bottom.

  • Oh no, it's kind of sitting right there perfectly.

  • How did my math, that was totally accidental, by the way.

  • Now it's just going to draw it again over and over again.

  • But I want to do a couple other things.

  • One thing I want to do is if time does a full cycle,

  • then I want to set time back equal to zero,

  • and path, clear the path.

  • All right, this concludes this particular coding challenge,

  • where I took a discrete Fourier transform,

  • this particular math function, I applied it

  • to an arbitrary signal, two signals of X's and Y's.

  • Then I rendered those as rotating epicycles,

  • and I had to draw the path.

  • Whoo, I'm very excited that I accomplished this.

  • So, there are two things that I want to do, probably

  • more than two, and those are going to come in separate videos,

  • if you made it through this one.

  • I am going to, first, I'm going to take a break, and I'm going to

  • come back, and I'm going to make it so that the user draws

  • something, and then it computes the Fourier transform.

  • That really, by the way,

  • you should go do that yourself right now.

  • So take this code that I've released,

  • find the link in the video description,

  • and go make a version where the user draws something

  • and then do the Fourier transform.

  • That's a fun exercise.

  • I'm going to do that in the next video, and then,

  • I am going to rewrite this so that I have

  • the Fourier transform done with the X and Y's together

  • as a complex number, and I just have

  • one set of epicycles rendering the full path.

  • But I kind of like these two X and Y machine things.

  • It's kind of cool.

  • Oh, yes, and Melvin in the chat is saying,

  • oh, you could use the Quick, Draw dataset.

  • So I'm going to leave that to you, the viewer.

  • Please make this, share it widely.

  • Make a version of this that renders random drawings

  • from the Quick, Draw data set.

  • That would be super fun.

  • I would love to see that, okay?

  • If you make any of these exciting, fun, beautiful,

  • strange, ugly, whatever they are, variations

  • on this particular coding challenge, please go to the link

  • to codingtrain.com, look for the instructions

  • on how to submit your variation, and submit yours,

  • and if you have trouble doing that, file a GitHub issue

  • or something saying, I want to submit mine,

  • but I don't know how, and we will help, okay?

  • Goodbye, everybody.

  • (bell dings)

  • (train whistle toots)

  • And I will leave you with something

  • that really needs to happen to this code.

  • (upbeat disco music)

  • ♪ I will refactor this later

  • You know I will refactor this later

  • ♪ I will refactor

  • (upbeat pop music)

  • (bell dings)

(bell dings)

Subtitles and vocabulary

Click the word to look it up Click the word to find further inforamtion about it