At first I didn’t like you showing the steps to shorten the equation… but, I then realized it actually answered my usual question when viewing these equations which is “why are there hardcoded numbers?!”, this is great! Thank you!
You can simply your math computations by using this formula: A^2 - B^2 = (A - B)(A + B). Instead of removing the 0.25 we can instead multiply by 4 and compute q = 4 * p. We'll need to adjust the other two formulas as well, to compute the next value of q using the current one, but I don't think it's going to be very difficult.
@@aXe-km7pr its about minimising the number of execution cycles required, and at least for older CPUs, multiplication requires more execution cycles than addition, and division even more than that.
@@akiel941in this case two left shifts would do the job instead of multiplying Since multiplying by 2 is one left shifts, multiplying by four is just two left shifts which for the CPU is faster compared to multplication
@@MiguelEX3cutavel In languages such as C++ for example (and probably also all other programming languages, that compiles down to symbolic machine code), the compiler is actually allowed to do that exact conversion from a multiplication to a left shift. If the specific compiler does so or not is another matter entirely though
@@MiguelEX3cutavel Most CPUs can shift by more than 1 in one instruction, so it can just be a single left shift by 2. And as the person above mentioned, a multiplication by 4 would automatically get optimized to a left shift by any decent compiler.
@@vibaj16 true but on the cpus where every cycle counted and floating point math had to be avoided, like the 6502, you needed multiple shift instructions. the increased accuracy is probably not worth the extra cycles there. these days you'd just do the operations in the gpu and there are probably better algorithms to use to fit its capabilities.
The intermediate conclusion that 2x+1 predicts the next increment, is synonymous with what calculus shows as the slope of the curve x*2 + 2x + c. It's just the slope or derivative of the quadratic at a given value of x, which is not only helpful to realize, but definitely computationally leaner than just calculating points brute-force. Nice tutorial!
I saw a video of yours a few months ago and now this popped up, Your videos are amazing, not only for implementation but also for general understanding of those commonly used formulas.
I interviewed at IMVU back in... God, 2010? And the tech part of the interview was just "derive this algorithm". It was a lot of fun, but this video really would have helped!
The simple thick line algorithm would take two of these as the outer and inner edges, and then fill between on each row. I'm sure there are optimizations, but that will get you to a quick solution you can use now. So if you wanted a circle with radius 100 and a line thickness of 9, then you'd have two circles with radius 104 and 96. Fill the center just like you'd fill the center of a single circle, just make the beginning point the inside circle (or midline if the inside circle's minimum y value is greater than then y value of the starting point).
You can get rid of multiplication in the loop by observing that differences between subsequent squares are odd numbers. For example 0+1+3+5+7+9+11+13 = 49 Then you can just keep the amount you need to increase x and y in separate variables that increment by 2 after you add them to p.
@@dascandy You don't get to decide how smart your compiler is. Most code at this level is written in assembler anyway, in which case there is no 'p' variable at all: it's just a test of the carry flag.
YES! (I suggested this in the previous video, I'm now happy) (I'm not saying that NoBS Code made that just because I asked, it's kinda the next level of complexity and amazingness, algorithmwise)
I came up with a similar algorithm for drawing pixelated circles by hand. Starting at x=0 and y=-r, increment x and calculate the offset y given the known x offset and radius plugged into the Pythagorean theorem. Once you reach x=r/2, you can mirror the result 7 more times.
It would be great if you showed the difference between including or excluding the 0.25. Also, can't we multiply everything by four to get rid of the imprecision?
Yup we could multiply by 4. But if I'm not mistaken that would also require extra multiplications by 4 when we increase the p value inside the loop. My guess is most implementation don't do that because it would introduce more operations, while truncating 0.25 works fine. And definitely agree I should have shown the difference the approximation makes. That would have been a nice extra animation. 👍
@@nobs_codeyou're already multiplying by 2, multiplying by 8 (or shifting by 3) instead isn't an extra operation, and the constants can be baked to be 4x what they were previously
I did not realize that. Simply multiplying everything by 4 does seem like a great solution then. Any idea why that isn't usually done in the implementations I've seen?
@@nobs_code Did you look at any high-performance production implementations? I would bet they do such and much more advanced tricks. Maybe look into the Linux kernel, they probably have a hyper-optimized circle-drawing routine.
@@nobs_code not sure about specifically midpoint circle implementations, but this whole "shifting by some bits so you could work with integers" thing is called fixed point numbers. it used to be popular, made it ways into c libraries and theres games like doom that used fixed point for almost everything involving coordinates
@@supremedevice1311 No, the approximation happens only once for the initial value, and it always neglects 0.25. All differences are integer. The reason is, that you calculate the square of some midpoint in y direction plus the square of an integer in x direction: n²+(m+.5)² = n²+m²+m+.25
Very early in my programming experience we did this to draw Pacman, in C, for a programming class (Landtiger LPC1768). I spent a LOT of time tweaking it to draw correctly... and I don't remember one bit of it, but I wanted to watch anyways. It feels silly now, but getting something to work, refactoring, getting it to work again, refactoring... so... numbing. In the good way.
If this wasn't made by someone who writes C++ and OpenGL I would be shocked, the 0, 0 being the top left corner then centering the circle on it brought back weird like half memories
With a few modifications, you can also draw ellipses using the same general approach. It's important to mention, because in many cases the aspect ratio of the pixels is not 1:1, so your "circle" is actually drawn as an ellipse anyway.
You missed the opportunity to make it branchless, by computing the y increment dy as p>0 and then just y += dy and p+= 2x + dy*2y+1. Because dy is either 0 or 1 the multiplication should be very fast
@@vibaj16 it's not, it's an expression that evaluates to either 1 or 0. In the code provided by the video the processor needs to guess which branch is executed (the "if p>0: ..." and the "else: ...") and if the processor's prediction is wrong this code becomes slow, especially in GPU processors. Branchless means no guessing (in better terms no conditional jumping instructions). This can be done by promoting p>0 to a number so the code in a branchless version becomes dy = (int)(p>0) y += dy p += 2x + dy*2y + 1 because there aren't any if-else statements the code just runs faster (counting cumulative time for all pixels) and the output is still the same.
@@vibaj16 afaik CMP, MOV(from flags to gpr) and AND are the most basic way to implement it and they are support in any processor, even old ones. You can be fancier with SETcc which is still widely supported as per x86 since 80386. I can't see how a comparison alone must be branched.
Back in the nineties, on Turbo Pascal, I used to draw my own circles, but I always used a precalculated lookup table with sin and cos values and then a simple: for d := 0 to 359 do drawpixel( x+coslookup[d]*r, y+sinlookup[d]*r );
Wouldn’t that skip pixels if the circle had more than 360 pixels e.g a greater than ~64 radius? Also seems inefficient for smaller circles since you’d be overwriting the same pixels multiple times. If it worked fine for the application though then fair enough I guess.
@@MrMoon-hy6pn Sure it was kinda weak. I just wanted to point out that by using lookup tables, sin and cos could be used even when such calculations were too expensive.
9:00 The first decision is about which of the two pixels at X=1 to choose from. Yours makes this choice by testing the mid-point at X=0. You step correctly each time but the initial value error causes some wrong decisions, changing the look of the circle.
I did it the same way a long time ago, but instead of calculations I used the fact that the squares of consecutive natural numbers differ by consecutive odd numbers (which also comes out at 11:20), so all I had to do was add and subtract
If you use p = -4 * r +1 and increment it by either 8 * (x + y) + 4 or 8 * x + 4 you get the exact result as in the not-optimized version without paying any extra costs...
Optical instructions exist for monitors and tv. For example, Sonic Master System gameplay last level instructs the computer to speed up the fan, to prevent overheating. Just by watching the video, the level turns on the S5 power mode, when watching videos, the phone will be cold, and was hot before.
8:25 or you could change the > into >=, removing that slight difference. This is what I thought you were gonna do all along. Since yMid is always a half integer, and x is always an integer, the sum of their squares is always 1/4 greater than an integer. So if k+1/4>r², and both k and r² are integers, that's the same as saying k>=r².
Interesting, what if I want to draw a square-outwards-clockwise-single-line spiral on a grid of tiles, starting from a 1x1 point (1 tile)? I recently had to think about it hard, and several of my days have been filled with math. Oh and one of the reasons why it was hard is because I want it centered in the grid, ealisy divisible into 4 quadrants so I had to use a cartesian plane and start my spiral at 0,0. It's not on a base grid like your circle is, so I can't add to y to go down, sometimes I have to add and sometimes I have to subtract, and I need to know when, so that my spiral doesn't turn into a flat line or a thin rectangle or have a weird off shoot into some direction. And there is literally no midpoint possible, my "tiles" act as squares but I can't calculate fractions of them, a coordinate 3,5.14689 will default to 3,6. But that is irrelevant in for the shape I'm asking about. I already went through all this and made the algorithm, and I'm just asking for your version that would make the spiral I asked about. Currently I can already make any number of squares follow the spiral shape. I can access any one of them in constant time using coordinates; But I also can access any one of them in constant time, based on the order of insertion, independent of the size of the spiral, and without creating extra references to associate the index of the square (it's order of insertion) with it's coordinates. So.. yeah, a little head scratcher for you.
Why not calculate 4*p instead of p ? This will help to get rid of fractional numbers like 0.25 or 1.25 and convert everything into integers, while preserving the sign of p.
The slight difference you've noticed when truncating 0.25 appears because of using > instead of >=. For INTEGER values A and B, the inequality A + 0.25 > B is equivalent to A >= B. So in the code you need to replace the check "p > 0" with "p >= 0".
Is the optimization really necessary? You've basically replaced 3 multiplications with 1, and you still have 8 function calls to putPixel. Since calling functions is a much "heavier" operation than multiplication, I wonder if it even matters. Nonetheless, the idea behind the optimization is great, and I have no problems with it. Just wondering if it makes a difference.
The use of the putPixel() function is basically just an abstraction. In real code you would of course not want a function call for placing every single pixel, but directly access the pixels in memory instead. Otherwise, as you said, that would be super inefficient.
The only way to know if it makes the difference is to measure. Naturally, results may differ on different hardware and, potentially, with different inputs.
You didn't point out that the y is negative all the time in the "changing p" piece. Because increasing p by 2(x+y)+1 looks as if it's always increasing but it's not and that's the point, moreover, -y is always bigger than x by at least 1 so p's actually always decreased in that step.
0:43 I can think of simple ways of mirroring a quarter circle into a whole circle. doing it with 16ths would seem to be as hard as the original problem. or am I missing somthing
I love this series of videos for raster algorithms. Due to the time at which they were developed, most of the explanations are terse and uninformative. This is the complete opposite!
I like the video but it’s kinda strange when you choose to through all those steps with showing the binomials and taking 10 seconds just to get from 2x + 1 + y + y to 2(x + y) + 1 and then not explain the filling of the circle to the audience.
There's actually a lot more convenient way for drawing a circle. Saving the coordinates of the midpoint in an array of 2 dimensions and by using cos(theta) and sin(theta) from mathematics you can draw short lines from pixel to pixel say from {centerpoint[0] + cos(theta), centerpoint[1] + sin(theta)} to {centerpoint[0] + cos(theta+1), centerpoint[1] + sin(theta+1)} theta ranging from 0 to 359 degrees.
@@Omena0 You are right in some way. The most of people does their project in python. Python is slow programming language... But yeah, python have a bunch of different libraries in it.
@@xPlay5r Instagram's back-end is Python. Python is only slow if you A. Use normal CPython, and B. Have an inefficient implementation of whatever you're doing.
At first I didn’t like you showing the steps to shorten the equation… but, I then realized it actually answered my usual question when viewing these equations which is “why are there hardcoded numbers?!”, this is great! Thank you!
You can simply your math computations by using this formula: A^2 - B^2 = (A - B)(A + B).
Instead of removing the 0.25 we can instead multiply by 4 and compute q = 4 * p. We'll need to adjust the other two formulas as well, to compute the next value of q using the current one, but I don't think it's going to be very difficult.
you mean 0.25
@@vibaj16 Yes, my mistake.
honestly annoying watching someone not rearrange formulas to make them more computationally efficient
@@trinityy-7 this is computing not mental math
@@aXe-km7pr its about minimising the number of execution cycles required, and at least for older CPUs, multiplication requires more execution cycles than addition, and division even more than that.
this is something intuitive that i was able to implement it in desmos in about two minutes
Yo? Fellow Desmos coder? Post a video of it on your channel I wanna see
instead of truncating the float value, why not just multiply both sides of the equation and condition by a constant so it becomes an integer?
Really good idea ! And it would just need a multiplication by 4, which works nicely.
@@akiel941in this case two left shifts would do the job instead of multiplying
Since multiplying by 2 is one left shifts, multiplying by four is just two left shifts which for the CPU is faster compared to multplication
@@MiguelEX3cutavel In languages such as C++ for example (and probably also all other programming languages, that compiles down to symbolic machine code), the compiler is actually allowed to do that exact conversion from a multiplication to a left shift. If the specific compiler does so or not is another matter entirely though
@@MiguelEX3cutavel Most CPUs can shift by more than 1 in one instruction, so it can just be a single left shift by 2. And as the person above mentioned, a multiplication by 4 would automatically get optimized to a left shift by any decent compiler.
@@vibaj16 true but on the cpus where every cycle counted and floating point math had to be avoided, like the 6502, you needed multiple shift instructions. the increased accuracy is probably not worth the extra cycles there. these days you'd just do the operations in the gpu and there are probably better algorithms to use to fit its capabilities.
The intermediate conclusion that 2x+1 predicts the next increment, is synonymous with what calculus shows as the slope of the curve x*2 + 2x + c. It's just the slope or derivative of the quadratic at a given value of x, which is not only helpful to realize, but definitely computationally leaner than just calculating points brute-force. Nice tutorial!
Again a clear and concise explanation! Thank you for taking the time to make these videos and share them with us!
I saw a video of yours a few months ago and now this popped up,
Your videos are amazing, not only for implementation but also for general understanding of those commonly used formulas.
As a CS student, I really enjoyed this video. Well done!
This channel is going to explode!! Please keep up with the Computer Science content ❤️
These videos are great. They remind me of videos created by the Coding Math channel here on UA-cam.
years ago I have implemented this algorithm on ZX Spectrum in Z80 assembly, using only integers and with no multiplications. Boy, that was fast
This video would’ve saved me in university, keep it up 🫡
Great vid, i used this for a circle drawing function on the Gameboy advance but this helped me better understand how it actually works!
Whoever made this algorithm is a genius for me
I had this problem once I wanted to code generating a circle in minecraft. Thanks for the video!!
I interviewed at IMVU back in... God, 2010? And the tech part of the interview was just "derive this algorithm". It was a lot of fun, but this video really would have helped!
Uh I follow you on mastodon, I didn't expect to see you there but I'm not surprised either. Anyway, hi !
A very good video for intermediate leaners
this is great, thank you! a thick line modification of this or line algorithm would be great too
The simple thick line algorithm would take two of these as the outer and inner edges, and then fill between on each row. I'm sure there are optimizations, but that will get you to a quick solution you can use now. So if you wanted a circle with radius 100 and a line thickness of 9, then you'd have two circles with radius 104 and 96. Fill the center just like you'd fill the center of a single circle, just make the beginning point the inside circle (or midline if the inside circle's minimum y value is greater than then y value of the starting point).
You can get rid of multiplication in the loop by observing that differences between subsequent squares are odd numbers. For example 0+1+3+5+7+9+11+13 = 49
Then you can just keep the amount you need to increase x and y in separate variables that increment by 2 after you add them to p.
You can also leave that job to the compiler and write more readable code.
@@dascandy You don't get to decide how smart your compiler is. Most code at this level is written in assembler anyway, in which case there is no 'p' variable at all: it's just a test of the carry flag.
YES!
(I suggested this in the previous video, I'm now happy)
(I'm not saying that NoBS Code made that just because I asked, it's kinda the next level of complexity and amazingness, algorithmwise)
Haha, I did see that! Although I did plan on making this one next, but it's always nice to know what people want to see.
@@nobs_code This was so wholesome I'm gonna subscribe 😂😂😂
I suggested it too, although for some reason I thought it was called the bresenham circle-drawing algorithm
Super! What software are you using for creating these wonderful animations?
I came up with a similar algorithm for drawing pixelated circles by hand. Starting at x=0 and y=-r, increment x and calculate the offset y given the known x offset and radius plugged into the Pythagorean theorem. Once you reach x=r/2, you can mirror the result 7 more times.
9:17 thanks so much for explaining step by step. That way i can learn deeply. Also very interesting.
It would be great if you showed the difference between including or excluding the 0.25. Also, can't we multiply everything by four to get rid of the imprecision?
Yup we could multiply by 4. But if I'm not mistaken that would also require extra multiplications by 4 when we increase the p value inside the loop. My guess is most implementation don't do that because it would introduce more operations, while truncating 0.25 works fine.
And definitely agree I should have shown the difference the approximation makes. That would have been a nice extra animation. 👍
@@nobs_codeyou're already multiplying by 2, multiplying by 8 (or shifting by 3) instead isn't an extra operation, and the constants can be baked to be 4x what they were previously
I did not realize that. Simply multiplying everything by 4 does seem like a great solution then. Any idea why that isn't usually done in the implementations I've seen?
@@nobs_code Did you look at any high-performance production implementations? I would bet they do such and much more advanced tricks. Maybe look into the Linux kernel, they probably have a hyper-optimized circle-drawing routine.
@@nobs_code not sure about specifically midpoint circle implementations, but this whole "shifting by some bits so you could work with integers" thing is called fixed point numbers. it used to be popular, made it ways into c libraries and theres games like doom that used fixed point for almost everything involving coordinates
If I am not mistaken, you can also multiply p by four and you would get rid of the fractions, while still only checking for the sign of p, i.e., 4*p.
So you approximated p by subtracting 0.25, and you check p>0, when the "exact" check would be p+0.25>0.
But since p is integer: p+0.25>0 p>=0.
i think the problem is that the error accumulates on each iteration
@@supremedevice1311 No, the approximation happens only once for the initial value, and it always neglects 0.25. All differences are integer. The reason is, that you calculate the square of some midpoint in y direction plus the square of an integer in x direction: n²+(m+.5)² = n²+m²+m+.25
Very early in my programming experience we did this to draw Pacman, in C, for a programming class (Landtiger LPC1768). I spent a LOT of time tweaking it to draw correctly... and I don't remember one bit of it, but I wanted to watch anyways. It feels silly now, but getting something to work, refactoring, getting it to work again, refactoring... so... numbing. In the good way.
If this wasn't made by someone who writes C++ and OpenGL I would be shocked, the 0, 0 being the top left corner then centering the circle on it brought back weird like half memories
With a few modifications, you can also draw ellipses using the same general approach.
It's important to mention, because in many cases the aspect ratio of the pixels is not 1:1, so your "circle" is actually drawn as an ellipse anyway.
8:15 if r is also integer, we can just change the condition from p>0 to p>=0 to get the exact same result.
There is no way I had to solve this in an interview a few days ago and then I get this recommended…
Cringing hard at the camelCase in Python code 😖😛
Awesome vid though, always love seeing more CS content!
You missed the opportunity to make it branchless, by computing the y increment dy as p>0 and then just y += dy and p+= 2x + dy*2y+1. Because dy is either 0 or 1 the multiplication should be very fast
p>0 is a branch tho..
@@vibaj16 it's not, it's an expression that evaluates to either 1 or 0.
In the code provided by the video the processor needs to guess which branch is executed (the "if p>0: ..." and the "else: ...") and if the processor's prediction is wrong this code becomes slow, especially in GPU processors.
Branchless means no guessing (in better terms no conditional jumping instructions). This can be done by promoting p>0 to a number so the code in a branchless version becomes
dy = (int)(p>0)
y += dy
p += 2x + dy*2y + 1
because there aren't any if-else statements the code just runs faster (counting cumulative time for all pixels) and the output is still the same.
@@hagalloch "(int)(p>0)" is not gauranteed to be branchless. In fact, on some processors it's impossible without branching.
@@vibaj16 afaik CMP, MOV(from flags to gpr) and AND are the most basic way to implement it and they are support in any processor, even old ones. You can be fancier with SETcc which is still widely supported as per x86 since 80386. I can't see how a comparison alone must be branched.
@@hagalloch they are not supported in every processor
Back in the nineties, on Turbo Pascal, I used to draw my own circles, but I always used a precalculated lookup table with sin and cos values and then a simple:
for d := 0 to 359 do drawpixel( x+coslookup[d]*r, y+sinlookup[d]*r );
Wouldn’t that skip pixels if the circle had more than 360 pixels e.g a greater than ~64 radius? Also seems inefficient for smaller circles since you’d be overwriting the same pixels multiple times. If it worked fine for the application though then fair enough I guess.
@@MrMoon-hy6pn I never said it was good coding. I was 14 or so at the time.
@@EaglePicking I had a feeling so. Apologies if I sounded harsh. I just thought it was interesting to find the weaknesses of the approach.
@@MrMoon-hy6pn Sure it was kinda weak. I just wanted to point out that by using lookup tables, sin and cos could be used even when such calculations were too expensive.
Good video!!!
9:00 The first decision is about which of the two pixels at X=1 to choose from. Yours makes this choice by testing the mid-point at X=0. You step correctly each time but the initial value error causes some wrong decisions, changing the look of the circle.
I did it the same way a long time ago, but instead of calculations I used the fact that the squares of consecutive natural numbers differ by consecutive odd numbers (which also comes out at 11:20), so all I had to do was add and subtract
If you use p = -4 * r +1 and increment it by either 8 * (x + y) + 4 or 8 * x + 4 you get the exact result as in the not-optimized version without paying any extra costs...
Optical instructions exist for monitors and tv. For example, Sonic Master System gameplay last level instructs the computer to speed up the fan, to prevent overheating. Just by watching the video, the level turns on the S5 power mode, when watching videos, the phone will be cold, and was hot before.
8:25 or you could change the > into >=, removing that slight difference. This is what I thought you were gonna do all along. Since yMid is always a half integer, and x is always an integer, the sum of their squares is always 1/4 greater than an integer. So if k+1/4>r², and both k and r² are integers, that's the same as saying k>=r².
тут нужен полный __целочисленный__ алгоритм
п.с.: как стартовое объяснение - очень хорошо, но нужно продолжение в __целочисленный__ алгоритм
Will you do antialiased drawing next?
Interesting, what if I want to draw a square-outwards-clockwise-single-line spiral on a grid of tiles, starting from a 1x1 point (1 tile)? I recently had to think about it hard, and several of my days have been filled with math.
Oh and one of the reasons why it was hard is because I want it centered in the grid, ealisy divisible into 4 quadrants so I had to use a cartesian plane and start my spiral at 0,0.
It's not on a base grid like your circle is, so I can't add to y to go down, sometimes I have to add and sometimes I have to subtract, and I need to know when, so that my spiral doesn't turn into a flat line or a thin rectangle or have a weird off shoot into some direction.
And there is literally no midpoint possible, my "tiles" act as squares but I can't calculate fractions of them, a coordinate 3,5.14689 will default to 3,6. But that is irrelevant in for the shape I'm asking about.
I already went through all this and made the algorithm, and I'm just asking for your version that would make the spiral I asked about.
Currently I can already make any number of squares follow the spiral shape.
I can access any one of them in constant time using coordinates;
But I also can access any one of them in constant time, based on the order of insertion, independent of the size of the spiral, and without creating extra references to associate the index of the square (it's order of insertion) with it's coordinates.
So.. yeah, a little head scratcher for you.
It can easily be generalized to line for zero-level set coverage finding
its very cool and easy
Now do an algorithm for making a dome on a 3D grid system.
I love it!!!!
Can you do a video on how to draw a horizontal line by filling 0xFF in the middles and use bitshifts for 2 ends
Why not calculate 4*p instead of p ?
This will help to get rid of fractional numbers like 0.25 or 1.25 and convert everything into integers, while preserving the sign of p.
Indeed
The slight difference you've noticed when truncating 0.25 appears because of using > instead of >=. For INTEGER values A and B, the inequality A + 0.25 > B is equivalent to A >= B. So in the code you need to replace the check "p > 0" with "p >= 0".
Is there some way to donate to you? Content of this quality can't stay unpayed
Is the optimization really necessary? You've basically replaced 3 multiplications with 1, and you still have 8 function calls to putPixel. Since calling functions is a much "heavier" operation than multiplication, I wonder if it even matters.
Nonetheless, the idea behind the optimization is great, and I have no problems with it. Just wondering if it makes a difference.
The use of the putPixel() function is basically just an abstraction. In real code you would of course not want a function call for placing every single pixel, but directly access the pixels in memory instead. Otherwise, as you said, that would be super inefficient.
The only way to know if it makes the difference is to measure. Naturally, results may differ on different hardware and, potentially, with different inputs.
@@IsmeGenius In this case that is the only way.
And with elipses?
Circle algorithm not ellipse
I fuck up my mind 3 fukings day programing this, and find this is a relieve, because i belive I did everything wrong, but NOPE THX GOD
Very useful for Minecraft
I'm not into this stuff of optimizing but my idea is to calculate only every second step and filling the gap with DrawLine. Does it work?
nice
You didn't point out that the y is negative all the time in the "changing p" piece. Because increasing p by 2(x+y)+1 looks as if it's always increasing but it's not and that's the point, moreover, -y is always bigger than x by at least 1 so p's actually always decreased in that step.
0:43
I can think of simple ways of mirroring a quarter circle into a whole circle.
doing it with 16ths would seem to be as hard as the original problem. or am I missing somthing
Can you please continue this with the ellipse drawing algorithm
What tool you use to do this nice pixel animation?
0:40 if they are symmetrical, why 1/8? Why not 1/16? 1/32?
Awesome video!
what is the adventage of this algorithme compare to Marching squares ?
8:09 If we are checking if '-r + 0.25 > 0' then is there a way to check if ''-100 * r > -25' ?
Why not simply use 4p instead?
I love this series of videos for raster algorithms. Due to the time at which they were developed, most of the explanations are terse and uninformative. This is the complete opposite!
Now do ellipses.
Gen Z says this algorithm is very mid.
#circles with sin and cos.
I like the video but it’s kinda strange when you choose to through all those steps with showing the binomials and taking 10 seconds just to get from 2x + 1 + y + y to 2(x + y) + 1 and then not explain the filling of the circle to the audience.
Why did you build that circle?
Why not multiply every term by 4 to get p = 1 - 4r? Multiplication by 4 is quite cheap.
There's actually a lot more convenient way for drawing a circle. Saving the coordinates of the midpoint in an array of 2 dimensions and by using cos(theta) and sin(theta) from mathematics you can draw short lines from pixel to pixel say from {centerpoint[0] + cos(theta), centerpoint[1] + sin(theta)} to {centerpoint[0] + cos(theta+1), centerpoint[1] + sin(theta+1)} theta ranging from 0 to 359 degrees.
This algorithm ends up using a bitshift and some addition.. replacing that with sin and cos isn't "more convenient".
how add "stroke" to that?=)
he explained better than my computer graphics professor xD
can't you just use cosine and sine ?????????
having a line that spin and put a point in his end point
Python program for wafer Cp test equipment
Final optimization that should be layered on all these algorithms: memoization.
I dont see where is use p to draw
GG. 69 views!!!
u can just solve y++, not x++, it is just 3 step.
Why flipping coordinate system against mathematical standards? Want to sound important?
This was overly complex for such a simple thing..
Learners* damnit
You will never draw circle efficiently using these calculations, they are too complex.
All this can be calculated using integer arithmetics.
This guy talks about optimization in python XD
Obviously python is only used for pseudocode here. 😋
@@nobs_code Python is like scratch. He is perfect for simple tasks, not a low-programming.
Python can be used for quite a lot. Not just "simple scripts." Optimization is important.
@@Omena0 You are right in some way. The most of people does their project in python. Python is slow programming language... But yeah, python have a bunch of different libraries in it.
@@xPlay5r Instagram's back-end is Python. Python is only slow if you A. Use normal CPython, and B. Have an inefficient implementation of whatever you're doing.
The midpoint circle algorithm is used for processing.
Since python has many version. It's a WARNING/ CRITICAL to do graphical computer science or low programming in python.
😂 computers doesn't have circle 🤣 My whole life must be a lie