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.
@@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.
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!
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.
@@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
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)
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.
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
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 );
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
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.
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.
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.
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!
@@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.
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
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.
As a CS student, I really enjoyed this video. Well done!
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!
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.
This channel is going to explode!! Please keep up with the Computer Science content ❤️
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.
These videos are great. They remind me of videos created by the Coding Math channel here on TH-cam.
this is great, thank you! a thick line modification of this or line algorithm would be great too
Again a clear and concise explanation! Thank you for taking the time to make these videos and share them with us!
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
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 😂😂😂
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.
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
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.
9:17 thanks so much for explaining step by step. That way i can learn deeply. Also very interesting.
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 );
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
Good video!!!
Cringing hard at the camelCase in Python code 😖😛
Awesome vid though, always love seeing more CS content!
It can easily be generalized to line for zero-level set coverage finding
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.
Will you do antialiased drawing next?
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².
Can you do a video on how to draw a horizontal line by filling 0xFF in the middles and use bitshifts for 2 ends
nice
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.
Gen Z says this algorithm is very mid.
#circles with sin and cos.
Can you please continue this with the ellipse drawing algorithm
what is the adventage of this algorithme compare to Marching squares ?
Why not simply use 4p instead?
Very useful for Minecraft
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.
GG. 69 views!!!
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!
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.
Now do ellipses.
u can just solve y++, not x++, it is just 3 step.