Lecture 9: Ray Tracing & Acceleration Structures (36)
christyquang
I was curious about the 3D DDA algorithm so I searched more about it online and found this article: https://www.scratchapixel.com/lessons/3d-basic-rendering/introduction-acceleration-structure/grid.html.
Essentially, the 3D-Digital Differential Analyzer algorithm starts with the coordinates of two endpoints of a line segment in 3D space. The differences are calculated between the x, y, z coordinates of the two endpoints. We determine the maximum difference among the differences (represents the number of steps needed to reach from one endpoint to the other on the longest axis). Calculate the increment values (divide differences by the number of steps), then draw the line by iterating over the number of steps. These steps are repeated for each line segment that needs to be drawn.
aidangarde
Is there another heuristic we could use to determine whether a line was close to a circle, rather than determining intersection with squares, then shapes? perhaps use some cap where we only check shapes within a certain bounding box of the line.
grafour
This wasn't very clear to me in the beginning so I thought I'd make a point in case anyone is confused. The heuristic is to determine how closely mapped we want to be to the ray (black line). The closer it is, the more memory we need, but the more accurate it is. But often times we don't need that much accuracy.
I was curious about the 3D DDA algorithm so I searched more about it online and found this article: https://www.scratchapixel.com/lessons/3d-basic-rendering/introduction-acceleration-structure/grid.html.
Essentially, the 3D-Digital Differential Analyzer algorithm starts with the coordinates of two endpoints of a line segment in 3D space. The differences are calculated between the x, y, z coordinates of the two endpoints. We determine the maximum difference among the differences (represents the number of steps needed to reach from one endpoint to the other on the longest axis). Calculate the increment values (divide differences by the number of steps), then draw the line by iterating over the number of steps. These steps are repeated for each line segment that needs to be drawn.
Is there another heuristic we could use to determine whether a line was close to a circle, rather than determining intersection with squares, then shapes? perhaps use some cap where we only check shapes within a certain bounding box of the line.
This wasn't very clear to me in the beginning so I thought I'd make a point in case anyone is confused. The heuristic is to determine how closely mapped we want to be to the ray (black line). The closer it is, the more memory we need, but the more accurate it is. But often times we don't need that much accuracy.