The beauty of this algorithm is how efficient it is. Multiplication and division are slow processes, but multiplication by 2 is only a single bit shift. That is, the algorithm reduces line drawing to simple adds and shifts.
Extremely high quality! Thank you for putting so much effort into this video. People like you, who make educational, comprehensible videos, are truely the heroes of modern youtube
D is effectively tracking the cumulative error in the rounding being performed. When that error becomes greater than half a pixel (when D > 0), then a pixel's worth of difference (along the axis of the loop, so dx) is subtracted. Each step also accumulates the error (due to the movement perpendicular to the axis of the loop, so dy). It's a very concise way of avoiding the unnecessary calculations. The reason the delta's are always 2x, is because the value is being rounded so you need of offset it by half a pixel (what the initial -dx is for).
RU-vid recommends on point today, great presentation. I love how the algorithm emerges from shuffling some mathematical terms around, derived from common sense. I would've paid a lot more attention to math classes if I'd seen this a long time ago. Keep it up!
I have implemented this algorithm over 25 years ago in my own library. I was then able to understand almost everything except the origin of 2dy-dx initial value. Thanks alot for clarifing this. This is a very good explanation.
It took me a while to figure out what the Line Algo's goal was (since I've never heard of it before), but once I understood that, the video did a really great job explaining it. Well done!
Such a good video on the subject! The animations are on-point, the writing is easy to understand, the code also is etc.. The only thing that would've made this video perfect in my opinion is if there would've been a section giving us some visual intuition to what's happening with the derived code!
0:51 a start and end point are defined. So, if the screen was split in half, the RIGHT side could replace X0, Y0, X1, and Y1 with actual values. Then, dX and dY can also have values defined. Keeping abstract values to the LEFT lets you show the formula, and simplify it, while also showing result values.
THANK YOU!!! I got frustrated with this years ago because all the variables were just "d," and "p," which didn't make any sense. This breakdown was crystal clear!
I think you yourself make it sound more complicated than it should be. I programmed an "initiative counter" for a game I had, which turned out to be an N dimensional Bresenham algorithm I reinvented from scratch. It's really simple. You grab the longest delta, and in every step, you move in that direction. You also have a running tally, and if it's larger than some other lengths, you also take a step in that dimension too. Really simple, no need to even go too deep into the math, it's a visual explanation.
I was going to say the same thing. I needed raycasting in a game I was making in GameMaker studio years ago, and I specifically needed to know where the casted ray collided with objects. I wrote a very similar algorithm to this
I also reinvented this 20 years ago when I wrote a pathfinding algorithm for an RTS game. Not only the line calculation but all of the pathfinding didn't need a single multiplication or division. The Bresenham algorithm is the natural thing you come up with when you think about the problem.
You should cover DDA(Digital Differential Analyzer) next. It's a line drawing algorithm similar to Bresenham's, but works with floats rather than integers.
On what parts do you say? Cause Bresenham's algorithm works with floats on the slope and on sum of slope and e till e becomes 1 in order to move the minor axis
Bresenham's is probably the fastest but I recommend looking up Xiaolin Wu's line algorithm. It's nearly as fast and will give you better looking lines.
Ngl this helped me so much, I still don't quiet understand it as I'm not often used to algorithm. But It works on GDscript in my Godot project and I was able understand the calculation of the result in the function. It's still a bit magic to me, but I think I'll have to test things by myself to comprehend more. What I don't understand is how by logic did we made it to that. Like how the heck people thought of doing this all of this in the first place 'xD. But thanks for all the animation and visualisation! Much better than some videos where they just explained the math and not the coding part
Don't forget the intuition of the end product. X and Y are essentially fighting for their turn can you make a move and each gets to fight based on the magnitude of their slope. Every time you increment one, then the other gets to throw in their vote.
Thank you for this ive always wondered why it worked. I have implemented it in several languages including asm, but never really understood why it worked. Im going to still need to unravel the maths a bit, but its very good.
You could avoid the last code duplication by conditionally flipping around the y=x symmetry of the unit circle to transform for the last remaining sectors.
I really like this explanation, there's a detail that only now I understand well: At first, I didn't understand that the constant part of p was negligible. It wasn't that ovious to me. Also, would you consider making a similar video about bresenham's circle drawing algorithm?
As fast as this algorithm is (I wanted to implement it myself for a project) the results are suboptimal. Even in the current example, it draws the line as 2, 4, 4, 2 for a total of 12 pixels drawn. A proper line would be 3, 3, 3, 3. It looks much better and makes more sense as far as consistency is concerned. The reason it doesn't do that is because we are taking the coordinates from the center of the pixels instead of the farthest edges: - 11 long, 3 high based on center vs - 12 long, 4 high based on box edges There is literally no way to draw a n, n, n repeated for more than 2 terms using Bresenham's algorithm. I have a very crude implementation of a perfect aliased line generator I've created that also handles all quadrants but it is much slower. So, Bresenham's algorithm is fantastic for speed, but if you need perfect lines and can afford the slowdown, you'd have to create a different version and I don't know if you can avoid floating points. Pretty good video. Clearly explained and the few math tricks are really neat, especially where we omit the deltaX on the left side of the equation.
3:46 Hmm, something seems fishy, here. dx > 0 for the whole right half of the circle, right? And dy > 0 for the whole bottom half. That's a quadrant, not an octant, and m > 0 for all of it.
themost interesting part is that according to wiki at least this algorithm is still useful in hardware level for modern hardware. which is insane since the algorithm itself it almost as old as the first implementation of integrated circuits
I wonder how this translates to voxels, I needed it once, but the triangle density for the problem was high, and the vertices were enough. I preferred that to oversampling and activating voxels many times.
Funny, that there is this "2*dy" in the inner loop. Since dy never changes, there should be a dy2 = 2 * dy before the loop, so there can be p += dy2 in the loop. Same for 2*dx.
This is the sort of thing you'd expect a decent optimizer would do for you. But then I have little experience with python so I couldn't tell you whether that's a reasonable expectation.
Great video! However, I never understood why bresenhams should be used today. dont get me wrong, it was amazing for 1962 but since then some minor things changed. like the first GPU being sold in 1999. drawing a line is a graphics operation, so it only makes sense to use a _graphics_ processing unit for that. a GPU which is specifically designed in hardware to operate on floating point values in parallel. same equation, different data (SIMDI). perfect to calculate the line height at every x-pixel in parallel and then color in the entire line at once. 4k has a width of 3840 pixels and modern GPUs have more cores than that so it really needs only a single iteration compared to 3840 iterations in bresenhams. moreover, since bresenham has a conditional branch in an iterative main loop, it is literally the death of all GPUs. we would have to interrupt our graphics pipeline to send data from our gpu to our cpu, do some integer arithmetic there and then send the pixel buffer back to our gpu. anyone who knows a bit of gpu programming knows that sending data between cpu and gpu is always the bottleneck and veeery slow. so to conclude we have bresenham with: 1. iterative (slow), 2. conditional branching (slow), cannot run on the gpu (slow, clunky), unnecessary data transfer (slow), uses integers (hooray?) vs a modern GPU which existed now for over 20 years: 1. embarrassingly parallel, O(1) vs O(n) (very fast), 2. literally hardware designed for floating point operations (fast), 3. highly aligns with the underlying architecture (fast), 4. tight integration with the rest of the graphics pipeline (fast). what am i missing?
@@brentjackson6966 so for embedded systems which need to rasterize lines and only lines (because 3d geometry is too expensive then) but do not have dedicated hardware for rendering? 😅 that sounds like an ultra rare niche case and i couldnt think of a single case where this happens.
I was thinking about LCD displays for fridges and washing machines. That sorta stuff. But then on further reflection, they probably wouldn't be drawing anything beyond vertical or horizontal lines.
No, because the drawn line would then be mirrored around {1,1} unless you also swap the X,Y parameters to putPixel() - which wouldn't be difficult with another state variable rather than having two functions I guess
I was thinking the same but instead of using a fixed point addition, add (dy / dx * MAX_UINT_VALUE) to a counter each loop and then ADC y. (Increment Y if the counter overflowed). If will overflow every N steps where N is the number of X steps before Y increases by 1. So the inner loop would be something like; inc X add counter, step_value ADC Y plot_pixel X,Y
@@brentjackson6966 That's how I did it back in the 8 bit micro days, just having one fixed point addition per cycle is fast and you lose the branch. In practice I suspect that the setting the pixel value is so much slower than the calculation that it is usually irrelevant!
@EdFrench_UK You are undoubtedly right that drawing the pixels is the most expensive part. However if you're drawing lots of lines to an off-screen buffer, wicked optimisations such as yours were undoubtedly worth their weight in gold. I'm not writing code as much as I used to back in the day but there's still a little voice in my head which cares about shaving just a few more cycles out of an algorithm.
This explanation is really unnecessarily convoluted. A lot of the steps seem to come out of nowhere. It is not properly explained why some terms can just be left out, or why we're suddenly looking at "pInitial" and "pNext". No one unfamiliar with the subject is going to understand why a lot of these steps are justified (and I assume unfamiliar people are the target audience). This video does not achieve demystification. The mystery has just been shifted to how any of the introduced transformations are justified.
