Multi-Line Renderer with Redstone: Bresenham's Algorithm in Minecraft

[00:00:00]oh no where is it hi guys welcome back to another video if you're new to the channel welcome i'm matt and i usually make giant redstone games but today i want to spice things up a little bit one topic that's always been interesting to me is computer graphics i mean how does something like your gpu render video games shaders simulations and so many other cool things it's amazing how advanced everything's become and i really want to try doing some graphics in minecraft that just sounds so cool so what's the best way to start doing redstone graphics well in spirit of not getting too overwhelmed let's make a machine that can render just one type of geometry lines specifically we want to make a machine that takes any two coordinate points as input for example 3 4 and 20 50 and the machine draws a line between them while staying as straight as possible as much as i want to start building this is just not a project that i can build right away instead i need to do some research to find a good line drawing algorithm or a set of instructions that when given two points can just draw the line for us once we find a nice algorithm then we'll implement it into minecraft and if we do everything right we should be able to draw any line which is redstone okay after like 10 minutes of searching it seems like the most popular algorithm is brezzenham's algorithm according to this it was first developed back in 1962 so it must be pretty good if it's stuck around and it's still popular now i'm gonna go try to understand how it works i'll see you in a bit alright that went pretty well it's been a few hours and i think i have a decent understanding of it now let me explain to simplify things let's assume that you're plotting a line from the point x1 y1 to the point x2 y2 the line goes from left to right and bottom to top or in math terms x2 is bigger than x1 and y2 is bigger than y1 the slope of the line is between zero and one and we're only dealing with pixels that are on or off like redstone lamps so at a high level brezzenheim's algorithm looks like this for every single x value x1 through x2 figure out the y value that needs to go there and then draw the pixel okay simple enough and because of the assumptions i made determining the y value is simpler than you might think no matter what your line looks like when you go to draw the next pixel you only have two options you can either just continue drawing the line at the current y level like this or you can increase y by one and draw the next pixel up here and those are the only two options you have for drawing the next pixel alright let's update the code we still go through all the x's but now if we need to increment y we do it otherwise we don't and then we draw the pixel okay but how do we know when we should increment y well this is where bresenham's genius kicks in he figured out that if you keep track of the error or how far off the real line is compared to the drawn pixel you can use the error to tell you when you need to increase y it took me a while to understand what the error actually was when i was learning so let me give you a few examples to make things as clear as possible let's say this is the line we're trying to draw right here and we've determined that the gray shaded pixel is the pixel that should be drawn the error would then be the y value on the line minus the y value in the middle of the pixel so in this case 2.4 minus 2 gives us an error of 0.4 or if the drawn pixel is here the error is 2.8 minus 2 which is 0.8 okay now that we know what error is let's walk through bresenham's algorithm let's say i want to draw a line from 1 1 to 6 3. we start by drawing the initial point which is 1 1 and our error right now is 0 because the middle of the pixel we just drew and the point on the line are right on top of each other so far so good now here comes the looping part we move over an x by one and we need to fix our error because it's not zero anymore and that's actually pretty easy to do because you can just use the slope slope is how much y changes for every unit change in x so all we need to do to get the new error is add the slope which in this case is 0.4 so our new error is 0.4 now we have to decide whether to draw this pixel or this pixel so here's the critical part resinham notice that if the error is greater than one-half it's a better decision to draw the higher pixel and if the error is less than one-half it's a better decision to draw the lower pixel so in our case the error of 0.4 is less than one-half so we draw the next pixel here and now we repeat the process move over an x by one fix the error by adding the slope so now our error is 0.8 0.8 is greater than one half so plot the next pixel here also since our pixel got moved up we need to subtract one from the error to account for that and yeah that's pretty much it you repeat that process until you hit your end point which in our case is 6 3. it's honestly a really elegant algorithm and it's fun to watch too let's go back to the code back at the code this is what it looks like now start the error at zero just like in the animation calculate the slope because you're going to need it and draw your first pixel then for the loop you still go through every x x one through x two add the slope to the error to make the error correct and if the error is greater than or equal to one half increment y and decrease error by one to account for that now i think this code snippet right here is the absolute best way to understand the algorithm and it does work you can try it out yourself but unfortunately this is not exactly brezenham's algorithm you see calculating the real slope is expensive because division is a slow operation for computers so to make the algorithm work with just addition and subtraction which are lightning fast he changed some of these values around and don't worry if you don't get why he made these changes i'm actually not going to explain it in this video but i still have to talk about it because this is what we're implementing instead of adding slope he adds 2 times delta y which we'll just call a instead of subtracting 1 he subtracts 2 delta x which we'll call b he changed the start value of error to two delta y minus delta x and finally instead of comparing the error to one half he compares it to zero the math behind all those changes gets a little more complicated and if you're interested in that i've left some resources in the description but the point is after those small changes this is the final version of brezzenham's algorithm it doesn't involve any division and it still works just fine that's really cool honestly i think this will be good enough for redstone i mean it's not going to be as simple as like a door but i think i can manage it before we start building though it's probably a good idea to code it in python and actually get it to run that way we can use it as a reference if we need to debug the redstone later i'll be right back okay i spent some time making it in python and it should be fully done now oh and i added some redstone lamp screen code that i had lying around and now we can simulate what it's going to look like on the screen awesome oh man i'm really excited now this is gonna look amazing on the real screen there is one problem that i've been avoiding though this algorithm as it stands doesn't automatically work for all types of lines remember in the assumptions we're only dealing with lines that increase in x increase in y and have a slope between zero and one that's pretty restrictive and these types of lines only cover about an eighth of all the possible lines there are because if you start every line at the origin then only the ones in this octant or this eighth of space follow our assumptions if you label these 1 through 8 it turns out that only lines in octant 1 will work but i'm not too worried about this i have some ideas for how to handle it later for now let's just pretend this problem doesn't exist and finally start building as with any computational build you want to start by building one component at a time and then connect them all up later and for this build we're going to need quite a few different components let's start with i'll call it the initialization component something where we can input x1 y1 x2 and y2 and it'll generate the two constants we need a and b and we can also have it generate the starting value for error while we're at it in other words something that handles this part of the code i think x1 y1 x2 and y2 being six bits each is a good start i mean we can always change it later this is still big enough to plot to a 64 by 64 screen since six bits can hold 64 different numbers now to calculate a b and the starting error i'm going to use a carry cancel adder which is a popular type of binary outer for minecraft if you're interested in how these work i cover them in this video right here most of the operations are subtractions and not additions but you can actually use an adder as a subtractor really easily and i've explained how to do that in this video right here okay i made it into a subtractor and i also made it light blue so for example if we do five minus three we're gonna get two and this is actually already a way to calculate both a and b i mean a is two times y two minus y y1 right so let's say this column is y2 and this column is y1 y2 minus y1 gives us this and now to multiply it by 2 you just do that adding another 0 to the bottom just multiplies it by 2. so now if you think of this as y2 and y1 it'll calculate a and if you think about it as x2 and x1 it'll just calculate b so a and b are done and for starting error we can just use more subtractors doing more similar things i'll be back when the initialization component is finished alright initialization component done here we have the four inputs x1 x2 y1 and y2 and on the output we have a starting value of error and b let's try it out so i'll input one one as the first point and five four as the second point and this is correct a is six b is eight and the starting value of error is two very nice all right initialization component is done and this part of the code is taken care of let's move on to the loop to keep track of the loop we need a component to iterate from x1 to x2 which simulates this line of code right here to do that i'll start with a binary counter or a device that can count up in binary and modify it okay here's a binary counter i had in my schematics and i think we'll be able to use it when you press this button it just counts up in binary so one two three and so on so let's add some inputs behind it one for x1 and one for x2 and modify this so that it counts from x1 to x2 okay i've been working on it a little bit i think it's time to give it its first test let's say we want to iterate from one to four so x one is one x two is four press this button we should get one through four no just a one okay okay i changed some timings so let's try that again one two three four beautiful let's give it another test this time we'll go from i don't know 7 to 10 7 8 9 10 and stop that is amazing all right the iterator component or whatever you want to call it is done which takes care of this line of code now for the contents of the main loop this is gonna be a bit of a challenge we need to make a circuit that repeats this over and over again add a to error check to see if error is greater than zero if so increment y and subtract b the faster we can get this loop running the faster our line drawer will be because every cycle of the loop draws a pixel therefore the speed of this component is really really important so i'm going to try my best to find the most optimal way to do it i'll be back when i've got my first prototype all right i think i might have a working prototype of the main loop component if everything works this should simulate the contents of the loop the inputs are b starting error and a and in the real line drawer we'll feed in those values from the initialization component because that's what generates those for us the output comes out of the top right here it's a stream of the decisions so it's literally a binary stream where a one or a signal being on represents the error was greater than or equal to zero and a zero or a signal being off means it wasn't also i got the speed of the loop to be six ticks which i think is pretty good i mean i don't have anything to compare it to but it seems pretty fast anyways enough talking let's actually test this thing out i think a good first test would be the line from the walkthrough earlier so 1 1 to 6 3.

[00:09:55]let me go calculate what a b and starting errors should be for that line i'll be right back okay values are set up and now we can test it we're expecting to see an output of zero one zero one zero because those are the decisions of whether or not to increase y when you plot this line let's press the button and okay okay zero one zero one dude no way it actually worked i mean i was expecting this one to take the longest but it literally took less time than the stupid iterator thing i mean i still have to test it some more but after that case worked i'm pretty confident it'll just work for everything let's go dude all right at this point all the major components are built we have an initialization component that takes x1 y1 x2 and y2 and calculates the three values we need a b and starting error we have an iterator component which will iterate from x1 to x2 simulating this for loop and we have a main data loop which generates a stream of the decisions that tells us when to increment why while the loop is running this is really coming together well not literally because now we have to actually put it together it's time to start assembly we need to come up with a layout for this line drawer that fits all of our components together nicely so let's move some stuff around okay i think this is a good basic layout for the line drawer you have your initializer out front which feeds a b and starting error into the main loop you have the iterator component thing here which we're using for x and you also have a regular binary counter to hold y and we can plug the decision stream from this guy into here which will increment y at the correct times i'll be back when everything is hooked up okay everything is hooked up and ready to go this is starting to look pretty cool it's like a spaceship or something let's start with a super basic test a line from one one to seven seven if we did everything right we should see the points come out as one one two two three three etc and then it'll stop at seven seven here we go there's no way it's gonna work first try but i can hope and one two oh this one is not okay look like the one on the left is only staying at one that's an issue time for everyone's favorite debugging okay i've literally been debugging this thing for about six hours and it's uh it's it's really frustrating i'm not gonna lie each component on its own works just fine but as soon as they try to talk to each other everything keeps falling apart it'll work for one case and then not another and then it'll work for that case but not the first one it's like dude come on and this is especially annoying because even if i do get this to work it's still only going to be able to graph one-eighth of all the possible lines because in the beginning i said this line drawer only works for lines in octant 1.

[00:12:16]uh i'm going to go take a break pet my dog i'll be back when i have a plan for the rest of the video okay i'm back i feel better now and here's what i'm thinking making a line drawer that only works for 1 8 of all lines sucks i mean i did have a plan to fix it but i just think it's way too much work for what it's worth i'm thinking there's got to be like a more generalized version of brezzenham's algorithm something that would automatically work for all lines and i was right it was just a bit harder to find online but this is bresenham's algorithm for all octants you can input any start point and any endpoint and it'll just work the code gets a bit more complicated obviously but i think this is still manageable so i'm gonna scrap this which is kind of disappointing but this is one of those times where i think getting a fresh start will really help me out plus the new line drawer is gonna work for all lines so it's not for nothing and about eight hours or so of work later i think i finally have a working line drawer for any type of line i was going to dive into the details of this new line jar as i was building it but after realizing how long this video already is i decided not to but trust me i've been testing this thing thoroughly giving it a bunch of edge cases comparing it to the new code and i'm pretty sure we have a winner so now you can pick any two points and it should just work so let's try 2010 to 3263 pop and over here it just outputs all the points of that line it's really hard to read binary that fast i can't do that but i did check it tediously one point at a time and it does work those were all the correct points for the line i think it's time to start work on the screen so that we can see these points being plotted for real normally when i make screens i just make a single xy plotter which takes an x coordinate and a y coordinate as input as you can see if we input 3 5 and press right we get the pixel at three comma five well assuming that the origin or the point zero zero is in the bottom left this screen is great because you can plot any xy point you want pretty easily but it's also pretty limiting because you can only plot one point at a time which means that in our case we're only going to be able to draw one line at a time however recently i came across this video by jarvi which is a tutorial for how to make a pass-through screen which means a screen that can plot multiple points at the same time so how cool would it be if we took jarvis screen copied our line drawer a bunch of times and plotted a bunch of lines to the screen at the same time i think that would be really cool so i'm gonna go watch jarvis video and i'll be back when i have a working pass-through screen okay if i did everything right this should be a 64 by 64 pass-through screen down here we have four separate xy inputs which can all plot to the screen at the same time and four is not the limit or anything i just chose that i mean you can stack this module as many times as you want you'll be able to use all of them at once for example i can go onto this guy and plot two three and then go over here and plot two four and when we look at the screen both of them get plotted to the screen i think it's time to hook up some line drawers but before we go crazy with a bunch of line drawers let's just try one to make sure it works okay he's hooked up and ready to go i am so excited let's try something huge just full confidence i'll pick some point in the top left and then another point in the bottom right and we'll see what it does here we go oh no where is it look at this thing that's so fast that is so fast oh my god all of my hours of debugging were worth it for just that moment that's insane line drawer now we can just copy the line drawer a bunch of times and have them all draw to the screen at once i'll see you in the showcase [Music] if you enjoyed this video subscribe it really helps me out and let me know what you want to see next in the comments i hope you learned something i hope you enjoyed peace out guys