A Fast Voxel Traversal Algorithm for Ray Tracing

By J. Amanatides, Andrew Woo. 1987

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Arun Mallya
2. Trevor Darrell
3. Jitendra Malik
4. Dacheng Tao
5. Ming-Yu Liu
6. Bo Li
7. Yoshua Bengio
8. Luc Van Gool

Citations in the corpus

• Ray tracing on programmable graphics hardware (2002, methodology): “It is possible to use a mailbox algorithm to prevent these extra intersection calculations [Amanatides and Woo 1987], but mailboxing is difficult to implement when multiple rays are traced in parallel.”
• 3D Convolutional Neural Networks for landing zone detection from LiDAR (2015, background): “2) Volumetric Convolutional Neural Nets: CNNs have three distinguishing features that make them useful for our scenario.”
• GANcraft: Unsupervised 3D Neural Rendering of Minecraft Worlds (2021, methodology): “We adopt a modified Bresenham method [5] for sampling valid points, which has a very low complexity of OpNq, where N is the longest dimension of the voxel grid.”
• Multi-level ray tracing algorithm (2005, unknown): “For those leaves some redundant intersection tests can be avoided by using a mailbox mechanism [Amanatides and Woo 1987].”
• Crowdsourcing in Computer Vision (2016, unknown): “This distance can be computed by incremental ray marching [3, 94, 53, 37], or by a technique called Woodcock tracking [22, 32, 112, 138], which was introduced to graphics by Raab et al.”
• Massively multi-robot simulation in stage (2008, background): “This was found empirically to be faster than the well-known floating-point alternative by Amanatides and Woo (1987).”
• OctoMap : A Probabilistic , Flexible , and Compact 3 D Map Representation for Robotic Systems (2010, methodology): “To efficiently determine the cells which need to be updated, a ray-casting operation is performed using a 3D variant of the Bresenham algorithm [1].”
• Ray Tracing on the Cell Processor (2006, methodology): “Efficient ray tracing requires the use of efficiency data structures, such as bounding volume hierarchies (BVHs) [22], Grids [2], or kd-trees [12].”
• OctoMap: an efficient probabilistic 3D mapping framework based on octrees (2013, methodology): “For efficiency, we use a 3D variant of the Bresenham algorithm to approximate the beam (Amanatides and Woo, 1987).”
• VoxNet: A 3D Convolutional Neural Network for real-time object recognition (2015, methodology): “Assuming an ideal beam sensor model, we use 3D ray tracing [32] to calculate the number of hits and pass-throughs for each voxel.”