The code for this is in the main Simple VGA github now: github.com/gfoot/simplevga6502/blob/main/src/piday2021.s Though I still need to update the schematics.
Very nice! The Midpoint circle algorithm is worth a look though. It does it all with nothing more than adds and subtracts and a few compares to generate an 8th of a circle and you do the rest with reflections.
You don't need square roots to draw a circle ;) Instead of comparing distances as square roots, you can just compare their squares equally well. Start with the implicit formula for the circle, x² + y² = r², move everything to one side, x² + y² - r² = 0, and this formula tells you whether you're on the circumference of the circle (when the result is 0), but it can also tell you if you're inside the circle (when the result is negative) or outside (when it is positive). So all you need now is to set up a loop that would increase the horizontal coordinate, square it, add it to the squared y coordinate (from an outer loop), subtract the squared radius (a constant/parameter calculated once for the entire circle), and see whether the result is negative, in which case you plot the pixel. Otherwise, you reset your x counter and move on to the next line. This can be improved even more by utilizing the octagonal symmetry, so that you could do the calculations just once and put 8 pixels at the same time in each of the eight octants, by just flipping the signs in each possible way in every coordinate. And squaring can also be made quite fast, with bit shifts and additions. Ask ancient Egyptians ;) Although if you're scanning the screen pixel by pixel, there should be a way to avoid calculating squares for each coordinate as well, because subsequent squares differ by subsequent odd numbers, so you could just add the required difference of squares to the last result, increase it by 2 to get the next odd number increment, and move on.
Yes you're right - Gordon Henderson pointed this out too, and I looked up the midpoint algorithm and changed the code, see here: github.com/gfoot/simplevga6502/blob/ea0669e293c5abc5ccbe272ff07787fa4e9dc84c/src/piday2021.s#L183 It doesn't require any multiplies or square roots now, only addition, increment, and decrement, which is a great fit for the 6502.
The code for this is in the main Simple VGA github now: github.com/gfoot/simplevga6502/blob/main/src/piday2021.s
Though I still need to update the schematics.
Very nice!
The Midpoint circle algorithm is worth a look though. It does it all with nothing more than adds and subtracts and a few compares to generate an 8th of a circle and you do the rest with reflections.
Nice! I'll have to check it out.
Wow, the Wikipedia page is abysmal, but I see how it works, it should be pretty simple to implement now
... and it works beautifully, thanks for that! I've updated the code in GitHub with that now.
Happy Pi Day!
Nice! Happy Pi Day!
You and Ben Eater should team up for a retro console build; not for games, but to complement each others work with an expanded DIY experience.
Haha, that would be awesome. I think he's quite capable without me though!
You don't need square roots to draw a circle ;) Instead of comparing distances as square roots, you can just compare their squares equally well. Start with the implicit formula for the circle, x² + y² = r², move everything to one side, x² + y² - r² = 0, and this formula tells you whether you're on the circumference of the circle (when the result is 0), but it can also tell you if you're inside the circle (when the result is negative) or outside (when it is positive). So all you need now is to set up a loop that would increase the horizontal coordinate, square it, add it to the squared y coordinate (from an outer loop), subtract the squared radius (a constant/parameter calculated once for the entire circle), and see whether the result is negative, in which case you plot the pixel. Otherwise, you reset your x counter and move on to the next line.
This can be improved even more by utilizing the octagonal symmetry, so that you could do the calculations just once and put 8 pixels at the same time in each of the eight octants, by just flipping the signs in each possible way in every coordinate.
And squaring can also be made quite fast, with bit shifts and additions. Ask ancient Egyptians ;) Although if you're scanning the screen pixel by pixel, there should be a way to avoid calculating squares for each coordinate as well, because subsequent squares differ by subsequent odd numbers, so you could just add the required difference of squares to the last result, increase it by 2 to get the next odd number increment, and move on.
Yes you're right - Gordon Henderson pointed this out too, and I looked up the midpoint algorithm and changed the code, see here: github.com/gfoot/simplevga6502/blob/ea0669e293c5abc5ccbe272ff07787fa4e9dc84c/src/piday2021.s#L183
It doesn't require any multiplies or square roots now, only addition, increment, and decrement, which is a great fit for the 6502.