The DDA Algorithm, explained interactively(aaaa.sh)
aaaa.sh
The DDA Algorithm, explained interactively
https://aaaa.sh/creatures/dda-algorithm-interactive
16 comments
This is great. You should add an og:image / social image using one of the interactive bits to help with sharing on other platforms / discord etc!
Really pretty outputs! And impressive that the code is shown so elegantly and also interactive.
This algorithm is one I use to demo some features in a language I'm making called calculang [0][1] I like the way you step through the logic.
My only suggestion would be to include a raycasted scene because you can really grab a wide(r) audience (and I'd love to see how you get to voxel scenes!).
Either way - thanks for adding a neat new resource for this algorithm and I'm definitely taking notes Re your clean presentation of the details!
[0] https://next-calculang-gallery.netlify.app/raycasting
[1] https://www.youtube.com/watch?v=hKVXRACCnqU
This algorithm is one I use to demo some features in a language I'm making called calculang [0][1] I like the way you step through the logic.
My only suggestion would be to include a raycasted scene because you can really grab a wide(r) audience (and I'd love to see how you get to voxel scenes!).
Either way - thanks for adding a neat new resource for this algorithm and I'm definitely taking notes Re your clean presentation of the details!
[0] https://next-calculang-gallery.netlify.app/raycasting
[1] https://www.youtube.com/watch?v=hKVXRACCnqU
Haha, I don't know why I didn't think to include a raycast scene, especially since that's what I was using the algorithm for!! Glad you liked it.
Great job, thanks for breaking it down the way you did
That's just really fantastic. Well done, indeed.
Having implemented DDA code a bunch of times, I find it easiest to think about it in lazy functional terms: it's like a takeWhile on a merge (or union) of infinite ordered streams of ray t-values.
In other words, decompose the problem into one of finding where the ray crosses the X grid lines and the Y grid lines, and the mental image is:
So let's say that we have a ray with origin (0.8, 0.2) and a direction of (0.5, 0.25). Then we get:
Obviously, there's some fiddliness when the direction has negative components or worse, zero, but it's not to hard to work out the adjustments for those cases. Likewise, you also want to be very careful about handling the case where the ray origin is exactly on a cell boundary. But again, focusing on just one dimension at a time helps when reasoning all that out.
Generalizing the concept to a DDA in 3D on a voxel grid isn't much harder, either: now you find the stream of Z-crossings as well and do a 3-way merge.
(If you ever want to vectorize grid traversal across multiple rays, there are some tricks to that in a 2006 SIGGRAPH paper that I worked on: https://www.sci.utah.edu/~wald/Publications/2006/CGT/grid.pd...)
In other words, decompose the problem into one of finding where the ray crosses the X grid lines and the Y grid lines, and the mental image is:
+-------+-------+-------+ | | | | -------------------------
| | | ^ | | | | ^ | ^
| | | / | | | | / | /
| | | / | | | | / | /
+-------+-------+-*-----+ | | | / | ------------------*------
| | |/ | | | |/ | /
| | * | | | * | /
| | /| | | | /| | /
+-------+-----*-+-------+ = | | / | | U --------------*----------
| | / | | | | / | | /
| | / | | | | / | | /
| | / | | | | / | | /
+-------+-*-----+-------+ | | / | | ----------*--------------
| |/ | | | |/ | | /
| * | | | * | | /
| o| | | | o| | | o
+-------+-------+-------+ | | | | -------------------------
x' = o.x + t * d.x
y' = o.y + t * d.y.
ceil(o.x) = x' = o.x + t * d.x
t = (ceil(o.x) - o.x) / d.x.
((ceil(o.x) - o.x)/d.x) + step * 1/d.x.
So let's say that we have a ray with origin (0.8, 0.2) and a direction of (0.5, 0.25). Then we get:
X-crossings = [0.4, 2.4, 4.4, 6.4, 8.4, 10.4, ...]
Y-crossings = [3.2, 7.2, 11.2, 15.2, ...]
[0.4, 2.4, 3.2, 4.4, 6.4, 7.2, 8.4, 10.4, 11.2, ...]
X X Y X X Y X X Y ...
Obviously, there's some fiddliness when the direction has negative components or worse, zero, but it's not to hard to work out the adjustments for those cases. Likewise, you also want to be very careful about handling the case where the ray origin is exactly on a cell boundary. But again, focusing on just one dimension at a time helps when reasoning all that out.
Generalizing the concept to a DDA in 3D on a voxel grid isn't much harder, either: now you find the stream of Z-crossings as well and do a 3-way merge.
(If you ever want to vectorize grid traversal across multiple rays, there are some tricks to that in a 2006 SIGGRAPH paper that I worked on: https://www.sci.utah.edu/~wald/Publications/2006/CGT/grid.pd...)
That's a really good way to think about it! (Bonus points for ASCII diagrams.) IIRC, I had some similar visualizations in the article but I cut them. And nice paper, interesting way to solve that problem.
Oh, this is DDA, not Bresenham, for lines.
An interesting point about Bresenham's algorithm is made by David Schmenk (dschmenk) on his "Bresen-Span" page:
"Take note that the algorithm can be viewed as the long division of delta-major/delta-minor. The error term is really the running remainder, and every step results in a pixel along the major axis until the division completes with a remainder. The division restarts by moving along the minor axis and adding the dividend back in to the running remainder (error term). This is a bit of a simplification, but the concept is that the long division will only result in two integral spans of pixels, depending on the value of the running remainder (error term). We will take this in to account to write a routine that outputs spans based on the two span lengths: a short-span and a long-span."
In other code, dschmenk does use DDA for anti-aliased lines.
https://github.com/dschmenk/Bresen-Span
An interesting point about Bresenham's algorithm is made by David Schmenk (dschmenk) on his "Bresen-Span" page:
"Take note that the algorithm can be viewed as the long division of delta-major/delta-minor. The error term is really the running remainder, and every step results in a pixel along the major axis until the division completes with a remainder. The division restarts by moving along the minor axis and adding the dividend back in to the running remainder (error term). This is a bit of a simplification, but the concept is that the long division will only result in two integral spans of pixels, depending on the value of the running remainder (error term). We will take this in to account to write a routine that outputs spans based on the two span lengths: a short-span and a long-span."
In other code, dschmenk does use DDA for anti-aliased lines.
https://github.com/dschmenk/Bresen-Span
Good website/visualization, but I think the implementation can be improved. If I remember correctly, one of the strengths of DDA is that it works out entirely with integer math. I think you get there by multiplying out the denominators. Seeing that this implementation involves sqrt(), it probably has room for improvement.
I used this algorithm to build my ray caster blocky world in C, now try doing it in a third dimension (height) :)
https://github.com/con-dog/chunked-z-level-raycaster
https://github.com/con-dog/chunked-z-level-raycaster
That's incredible timing, I just spent 2 days trying to implement DDA from first principles for my wolfenstein-like game in C.
Can't wait to see how you explain it.
Can't wait to see how you explain it.
What language is the sample written in? It is really hard to read for a C guy like me
JavaScript! It's not perfect, but it's the easiest language to run in the browser :)
Ok I see. Making it work in a browser sure is a benefit
The color scheme didn't help for me, some really low contrast colors like for parentheses.
But nice otherwise, interactivity is great.
But nice otherwise, interactivity is great.
Quick fact about the way the interactivity is done, all of the code for it is in this blogpost.js file: https://aaaa.sh/creatures/blogpost.js, which is only about 100 lines long. Each block has a list of scripts that it pulls from like so:
<div class="code-example" scripts="grid-sm 2d-vector-gfx-lib draw-grid full-algo-intro feather-canvas-edges"></div>
and then there's a set of script tags with those ids. I figured it was a nice solution!