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.
@vibaj164 күн бұрын
you mean 0.25
@IvanToshkov4 күн бұрын
@@vibaj16 Yes, my mistake.
@trinityy-74 күн бұрын
honestly annoying watching someone not rearrange formulas to make them more computationally efficient
@syrupthesaiyanturtle5 күн бұрын
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?
@akiel9415 күн бұрын
Really good idea ! And it would just need a multiplication by 4, which works nicely.
@MiguelEX3cutavel5 күн бұрын
@@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
@neovictorius4 күн бұрын
@@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
@vibaj164 күн бұрын
@@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.
@timnewsham13 күн бұрын
@@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.
@ConsciousHoney21135 күн бұрын
As a CS student, I really enjoyed this video. Well done!
@reyariassКүн бұрын
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!
@kanashisa04 күн бұрын
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.
@joaoguerreiro94034 күн бұрын
This channel is going to explode!! Please keep up with the Computer Science content ❤️
@noamrtd-g4f5 күн бұрын
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.
@kbsanders5 күн бұрын
These videos are great. They remind me of videos created by the Coding Math channel here on KZbin.
@aidennwitz2 күн бұрын
this is great, thank you! a thick line modification of this or line algorithm would be great too
@jacquev65 күн бұрын
Again a clear and concise explanation! Thank you for taking the time to make these videos and share them with us!
@Pengochan4 күн бұрын
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.
@supremedevice1311Күн бұрын
i think the problem is that the error accumulates on each iteration
@PengochanКүн бұрын
@@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
@tomasbernardo59725 күн бұрын
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)
@nobs_code5 күн бұрын
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.
@pandaszan93104 күн бұрын
@@nobs_code This was so wholesome I'm gonna subscribe 😂😂😂
@niceshotapps12332 күн бұрын
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 can also leave that job to the compiler and write more readable code.
@jimwinchester339Күн бұрын
@@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.
@ktbbb55 күн бұрын
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?
@nobs_code5 күн бұрын
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. 👍
@Starwort5 күн бұрын
@@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
@nobs_code5 күн бұрын
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?
@lbgstzockt84935 күн бұрын
@@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.
@besusbb5 күн бұрын
@@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
@jimwinchester339Күн бұрын
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.
@nand3kudasai4 күн бұрын
9:17 thanks so much for explaining step by step. That way i can learn deeply. Also very interesting.
@hagalloch4 күн бұрын
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
@vibaj164 күн бұрын
p>0 is a branch tho..
@hagalloch4 күн бұрын
@@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.
@vibaj164 күн бұрын
@@hagalloch "(int)(p>0)" is not gauranteed to be branchless. In fact, on some processors it's impossible without branching.
@hagalloch4 күн бұрын
@@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.
@vibaj163 күн бұрын
@@hagalloch they are not supported in every processor
@EaglePicking5 күн бұрын
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 );
@Hycord4 күн бұрын
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
@Wololo123abc5 күн бұрын
Good video!!!
@torrentailsКүн бұрын
Cringing hard at the camelCase in Python code 😖😛 Awesome vid though, always love seeing more CS content!
@art-creator6 сағат бұрын
It can easily be generalized to line for zero-level set coverage finding
@doublepinger5 күн бұрын
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.
@sashimanu4 күн бұрын
Will you do antialiased drawing next?
@mathmachine4266Күн бұрын
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².
@bleakaddict2 күн бұрын
Can you do a video on how to draw a horizontal line by filling 0xFF in the middles and use bitshifts for 2 ends
@rewixx694205 күн бұрын
nice
@danser_theplayer015 күн бұрын
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.
@mshonle3 күн бұрын
Gen Z says this algorithm is very mid.
@rodrigoqteixeira3 күн бұрын
#circles with sin and cos.
@Yashss46172 күн бұрын
Can you please continue this with the ellipse drawing algorithm
@vinceguemat37512 күн бұрын
what is the adventage of this algorithme compare to Marching squares ?
@milos_radovanovic4 күн бұрын
Why not simply use 4p instead?
@ytstolemyname4 күн бұрын
Very useful for Minecraft
@mono96132 күн бұрын
Is there some way to donate to you? Content of this quality can't stay unpayed
@AEF23C204 күн бұрын
тут нужен полный __целочисленный__ алгоритм п.с.: как стартовое объяснение - очень хорошо, но нужно продолжение в __целочисленный__ алгоритм
@igorlukyanov74345 күн бұрын
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.
@nobs_code5 күн бұрын
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.
@IsmeGenius3 күн бұрын
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.
@igorlukyanov74343 күн бұрын
@@IsmeGenius In this case that is the only way.
@Wololo123abc5 күн бұрын
GG. 69 views!!!
@jogloran5 күн бұрын
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!
@xPlay5r3 күн бұрын
This guy talks about optimization in python XD
@nobs_code3 күн бұрын
Obviously python is only used for pseudocode here. 😋
@xPlay5r3 күн бұрын
@@nobs_code Python is like scratch. He is perfect for simple tasks, not a low-programming.
@Omena03 күн бұрын
Python can be used for quite a lot. Not just "simple scripts." Optimization is important.
@xPlay5r2 күн бұрын
@@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.
@Omena02 күн бұрын
@@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.