Coding Challenge #130.1: Drawing with Fourier Transform and Epicycles

Coding Challenge #130.1: Drawing with Fourier Transform and Epicycles


(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

100 thoughts on “Coding Challenge #130.1: Drawing with Fourier Transform and Epicycles

  1. Although this video's sophistication only adds to its glory, I miss the time when your videos used to be based on p5.js and were so simple that I would start coding straight away!

  2. I'm watching Daniel's channel since about 50k subs, every time he creates some amazing project, but this is maybe the most amazing thing I've ever seen here 😀 I heard about FT long time ago, but I've never been interested until now. Great job 😉

  3. This is epic! How can you make it like that, but with only one set of circles? (3:28)
    If you had a link or something I have to search, that's more than enough.

  4. Jesus this is insane! I remember having to draw a image with piecewise functions in 10th grade and thought that was impressive.

  5. Sir,i am one of your subscriber please its my humble request to you that please make a video on how we give a birthday gift though we are programmer my friend birthday is on 26th of jan

  6. FFT if I remember correctly can be used to simulate sea waves in videogame graphics very efficiently

    Also, as a way to teach complex numbers, have you ever considered making a "complex number library"? You can then refer to it when you do videos like this that build on top of it.

  7. i love how well you can explain topics, especially complex topics such as Fourier Transform! you’re definitely able to explain them in a really simple, but effective manner. great video as always!

  8. You should do a video on the trapped knight sequence by numberphile. I think this would fit in a coding challenge. ( https://youtu.be/RGQe8waGJ4w )

  9. Hello Daniel,
    I'm now following your tutorial videos about Java, after i saw you making cool things i wanted to make my own sort of minigame. The thing is i want the bal to bounce back after that the ball hits the pedal, but the problem is i don't know how. Here is the thing i tried following the whole script.

    ellipse(x,y,24,24);
    if ((x==mouseX) && (y==300));{
    x+=9;
    }
    rect(mouseX, 300, 94, 24);

    float x=width/2;
    float y=height/2;
    float kleur1;
    float kleur2;
    float kleur3;
    int xspeed = 2;
    int yspeed = 2;

    boolean xgaan = false;
    boolean ygaan = false;
    boolean xwaar = false;
    boolean ywaar = false;

    void setup()
    {
    size (640,360,P2D);
    background(kleur1,kleur2,kleur3);
    }

    void draw() {

    background(kleur1,kleur2,kleur3);
    fill(0,255,0);
    ellipse(x,y,24,24);
    // if ((x==mouseX) && (y==300));{
    //x+=9;
    //}
    rect(mouseX, 300, 94, 24);

    kleur1 += 0.8;
    kleur2 += -0.8;
    kleur3 += 3;
    x += xspeed;

    if (x > width){
    xspeed *= -1;
    xwaar= true;
    }

    if (x < 0){
    xspeed *= -1;
    xwaar =false;
    }

    if(mousePressed == true) {
    xspeed = 0;
    }
    if(mousePressed==false){
    if(xwaar == false){
    xspeed=2;
    }
    }
    if(xwaar == true){
    xspeed=-2;
    }

    y += yspeed;
    if (y > height){
    yspeed *= -1;
    ywaar= true;
    }

    if (y < 0){
    yspeed *= -1;
    ywaar =false;
    }

    if(mousePressed == true) {
    yspeed = 0;
    }
    if(mousePressed==false){
    if(ywaar == false){
    yspeed=2;
    }

    if(ywaar == true){
    yspeed=-2;

    }

    }

    }

  10. What's your theme color please? I asked this question during the live (you were so great!) and some people answered Dracula but it does not seem to be this and I'd really like to have your theme color

  11. Tip: Don't use "const" when you know you don't want to change a variable – just always use "const" except when it's really not possible. You'll write different code that way because automatically you try to avoid "let" by using functions like .map() and stuff

  12. I tried making this and when I finished, wanted to try with different paths, but I cannot find any online. Do you know how can I find some?

  13. FFT must means FULL of FRUSTRATING TRANSFORMATION. i had to watch more videos about fourier transform to catch up your 1 hour video. and more time to ponder. but only got glimpse of it. I only could start actual coding after i stop to try understand everything mathmatically. it was shame but when I finally reconstructed a straight line with x,y sin waves in my own code I am so satisfied. all my struggle was not in vain. thank you!

  14. Hey Daniel! I'm a huge fan of your channel, and I always learn a lot from your videos. Although I do not do JavaScript or p5.js, by going through the algorithm step-by-step one can build and expand on the code in any modern language. More importantly, one can not only replicate the code, but also understand it! Combining math, code and graphics is so much fun! In fact, I've been interested in Fourier since ever, but the standard math has always daunting to me, a biologist without strong background in math. Your recent videos on FT are not only amusing, but also expanded the horizon of possibilities in my research. Keep up the GREAT work! Best!

  15. how would you do this with processing, due to the fact that Java arrays are different than javascript arrays? would you use an ArrayList?

  16. Hello, good morning. Is it possible to create more than one canvases on a single page? Like createCanvas(w,h) createCanvas(w,h) that could result two canvases. Please tell me how I can do this if it is possible.

  17. A crude attempt at reducing the number of points in the drawing (to 375 in this case) instead of skipping 7 out of 8 points which gives 625 points, while keeping most of the details of the original 5000 point drawing:

    function simplifyDrawing(drawing) {
    const maxHeadingDiff = 0.4;
    const maxStrokeLength = 16;
    let newDrawing = [];
    let headingDiff = 0;
    let strokeLength = 0;
    let prevVec = null;
    for (let i = 0; i < drawing.length -1; i++) {
    let vec = createVector(drawing[i+1].x – drawing[i].x, drawing[i+1].y – drawing[i].y);
    if (prevVec == null) {
    newDrawing.push(drawing[0]);
    } else {
    headingDiff += vec.heading() – prevVec.heading();
    if (abs(headingDiff) > maxHeadingDiff/8) {
    strokeLength += vec.mag();
    } else {
    strokeLength += vec.mag()/128;
    }
    if (headingDiff > maxHeadingDiff || headingDiff < -maxHeadingDiff || strokeLength > maxStrokeLength) {
    newDrawing.push(drawing[i+1]);
    headingDiff = 0;
    strokeLength = 0;
    }
    }
    prevVec = vec;
    }
    if (strokeLength > 0) {
    newDrawing.push(drawing[drawing.length-1]);
    }
    print('Simplified drawing from ' + drawing.length + ' to ' + newDrawing.length + ' points.');
    return newDrawing;
    }

  18. hey i'm trying to make the one where the person draws the shape so that it keeps tracing the path but as it continues to trace it the path disapears at the start so the shape keeps being drawn without the line overlaping at all.

  19. Great work. Only problem: it's wrong. Well sort of. It's hard to explain but:
    The reason it works is that you have dt set as 2*PI/N (or an integer multiple) and k going all the way to N, so what you're doing is essentially sampling the function every period which means that actually all you're doing is reparametrizing your drawing in polar coordinates dependent on time. If you try to have a smaller (or bigger) dt you'll see that what is actually happening is that the circles are actually going round at random and just coming back to the point when you sample with your dt.
    To have it work you need to have also negative frequencies (i.e. sum from -k to k), this way you'll see the actual Fourier transform (which incidentally is worse that what you have). This way you can also vary k as you please (number of circles = 2*k+1).
    I have made a code based on yours which I'll be happy to provide.
    Thanks and keep up the great work.

  20. So, I'm a bit late, but with this code, you can then simply concatenate the arrays of the fourier transforms, and then make a single epicycle draw the entire train, by drawing the trail of the tip !

    I did it here if anyone want to try
    https://github.com/GuillaumeClementPolytech/Code_Challenge_130_plus

  21. So, I use Processing exclusively, and when I downloaded the code fro the Coding Challenge site for this lesson, I get an error that the circle () function is not found. I am using Processing 3.4 . If I use the reference page off of the SW, that does not include a circle() function reference, but if I search for Processing Circle(), I can find a page. Any idea what I an missing?

  22. Your videos are good, but for me sometimes you act way beyond acceptable stupid, meaning is that you should consider stop being dumb piece of shit garbage and change narrative in those moments. Love

  23. If you have a set of x,y coordinates why you don´t just prints it? What you see if you print that set of numbers?

  24. Awesome ! Really awesome !
    But how did the guy to generate the logo ????

    I think he has "scanned" the logo with a vertical line, then, for all points intersecting that line, he has summed up their y coordinates returning him a value, a kind of signal value.
    Then he has processing that signal as any signal with an FFT giving him all the values needed for the drawing.

    Isn't there a more elegant way of writing the SUM function by taking advantage of Javascript ?

    I tried the something like the following but there's a little problem with passing parameters to the callback function for the real example of your video, I need help, but I tried this and it works fine :

    //this one is valid for ANY sum you want to implement
    const Sigma = (start, end, callback) => {
    sum=0;
    for (let n=start; n < end; n++)
    sum += callback(n);
    return sum;
    };

    //Then, write the callback function you want, like:
    const f = (n, obj = {"x" : -5}) => {
    return Math.cos(2*Math.PI*n) * obj.x;
    };

    //And call Sigma from the main code, passing it the f function.Well, roughly speaking of course…
    X = Sigma(0, N-1, f);

  25. ok, we dont get the fourier complex equation, let play with parametric equation instead
    https://en.wikipedia.org/wiki/Parametric_equation
    https://www.desmos.com/calculator
    copy/paste on the left
    Mr who signature: (cos t-(cos(2t)*sin(3t)),(2*sin(4t))-sin(5t)) ;Range of t: -30 0
    LoveYou: ((3*sin(pi t))-3cos(.4t),(tan.7t-3cos(8t)*sin(.3t))) ; t range -2.15 2.14
    Zorro: ((1.8*sin(t))-sin(12t),(cos.9t-cos(1.1t)*sin(4t))) ; -1.3 .5
    B: (cos2t-(cos(2t)*sin(4t)),(3*sin(2t))-sin(5t)) ; -33 -29
    A: ((1*cos(3t))-3cos(t),(sin t+sin(5t)*sin(3t))) ; -1.4 .5
    S: ((1.8*sin(t))-sin(12t),(cos.9t-cos(1.1t)*sin(6t))) ; -1 0
    Q: (cos.8t-(cos(.9t)*sin(4.3t)),(2*sin(2t))-sin(6t)) ; 0 2
    Tree: (cos t-(cos(22t)*sin(333t)),(2*sin(3t))-sin(5t)) ; -23 0

    NB:
    Asin(B+Ct) ; or A*sin(B+C*t)

    A = change amplitude
    B = change phase (B = -π)
    C =change frequency
    Horizontal mirror: minus in front

  26. Why is there a statement in the code that says "re = re / N" and "im = im / N"? Why is the average needed even if it was not obtained from the DFT equation?

    – me as a noob coder

Leave a Reply

Your email address will not be published. Required fields are marked *