The DDA Algorithm, explained interactively

Summary

The DDA Algorithm, explained interactively I've written a number of voxel raytracers, and all of them (all the good ones, at least) use the Digital Differential Analyzer Algorithm for raycasting. I've only ever "implemented" this algorithm once, by copying a reference somewhere. Since then, I've used and re-used that code. But I have something to admit: I've never really understood how it works. I've seen it explained well, explained poorly, explained on video, and still, I just don't get it. It's one of those geometric algorithms that's hard to wrap your head around, at least for me. But recently, I ran into some issues with a raytracer, and I decided to try to fully understand it. And I made this blog post, for others like me. All code in this article is editable. Examples will update as you modify them. DDA, in 2D, is an algorithm that iterates over all of the grid squares intersected by a ray. For those who haven't seen the algorithm, it looks like this: If you understand the above, have a nice day :) If not, this article has an explanation. 3Blue1Brown teaches us that a good way to to explain something is to derive it from scratch. So how would you derive this line drawing algorithm? First, we've got our arguments: the Ray Origin ro, and Ray Direction rd. RD has to be normalized. In this article, we calculate it using an angle, like this: Let's plot those on a grid. The first grid space we need to fill in is pretty simple–it's the grid space that ro is in. We can floor ro to get the exact integer space. Not super exciting, but an important step. Now, we have to figure out what the next grid space is. See if you can guess the answer: move the point and the arrow above and guess where the next grid space would be. At first glance, you might think it has something to do with rdAngle, like if the angle is facing up, then the grid space above the dot should be filled in, if the angle is facing to the right, the one to the right should be filled in, etc. But if you p...