Fast Voxel Traversal Algorithm Over Spherical Grids

About

This project extends the yt open-source data analysis and visualization package, providing an enhanced, integrated user interface for data exploration and enabling the visualization of physical data that comes from non-cartesian grids. Currently, yt implements a fast voxel traversal over a cartesian coordinate grid. The objective is to develop a fast voxel traversal over a spherical coordinate grid, based on ideas from Amanatides and Woo’s seminal paper on fast voxel traversal for ray tracing.

Authors

Chris Gyurgyik (cpg49 at cornell.edu)
Ariel Kellison (ak2485 at cornell.edu)
Youhan Yuan (yy435 at cornell.edu)

Initial Benchmarks*

# Rays	# Voxels	CPU Mean (ms)	CPU Median (ms)	CPU Std Dev (ms)
128^2	64^3	103	103	1.1
256^2	64^3	407	406	1.3
512^2	64^3	1616	1613	2.3
128^2	128^3	201	201	0.8
256^2	128^3	796	794	2.4
512^2	128^3	3187	3180	8.3

^{*Run on (8 X 1400 MHz CPUs).}
^{CPU Caches:

L1 Data 32 KiB (x4), L1 Instruction 32 KiB (x4), L2 Unified 256 KiB (x4), L3 Unified 6144 KiB (x1)}

C++ Build Requirements

CMake 3.7 or later
C++11-standard-compliant compiler

To run the benchmarks:

Install CMake version 3.7 or higher (https://cmake.org/)

Clone the repository and build the benchmarks:

git clone https://github.com/spherical-volume-rendering/svr-algorithm.git && 
cd svr-algorithm/cpp/benchmarks && mkdir build && cd build && cmake .. && make

Run the benchmarks:
```
cd .. && ./bin/benchmark_svr
```

C++ Example

#include "spherical_volume_rendering_util.h"

const BoundVec3 sphere_center(0.0, 0.0, 0.0);
const double sphere_max_radius = 10.0;
const svr::SphereBound min_bound = { .radial=0.0, .polar=0.0, .azimuthal=0.0 };
const svr::SphereBound max_bound = { .radial=sphere_max_radius, .polar=2*M_PI, .azimuthal=2*M_PI };
const svr::SphericalVoxelGrid grid(min_bound, max_bound, 
                                   /*num_radial_sections=*/4, 
                                   /*num_polar_sections=*/4,
                                   /*num_azimuthal_sections=*/4, 
                                   sphere_center);
const BoundVec3 ray_origin(-13.0, -13.0, -13.0);
const FreeVec3 ray_direction(1.0, 1.0, 1.0);
const Ray ray(ray_origin, ray_direction);
const auto voxels = svr::walkSphericalVolume(ray, grid, /*t_begin=*/0.0, /*t_end=*/30.0);

Cython Build Requirements

Cython Example

#   Compile code before use:
#   python3 cython_SVR_setup.py build_ext --inplace

import cython_SVR
import numpy as np

ray_origin    = np.array([-13.0, -13.0, -13.0])
ray_direction = np.array([1.0, 1.0, 1.0])
sphere_center = np.array([0.0, 0.0, 0.0])
sphere_max_radius      = 10.0
num_radial_sections    =  4
num_polar_sections     =  4
num_azimuthal_sections =  4
min_bound = np.array([0.0, 0.0, 0.0])
max_bound = np.array([sphere_max_radius, 2 * np.pi, 2 * np.pi])
t_begin   = 0.0
t_end     = 30.0
voxels = cython_SVR.walk_spherical_volume(ray_origin, ray_direction, min_bound, max_bound, 
                                          num_radial_sections, num_polar_sections, 
                                          num_azimuthal_sections, sphere_center, t_begin, t_end)

# Expected voxels: [ [1, 2, 2], [2, 2, 2], [3, 2, 2], [4, 2, 2],
#                    [4, 0, 0], [3, 0, 0], [2, 0, 0], [1, 0, 0] ]

Project Links

References

John Amanatides and Andrew Woo. A fast voxel traversal algorithm for ray tracing. In Eurographics ’87, pages 3–10, 1987.
James Foley, Andries van Dam, Steven Feiner & John Hughes, "Clipping Lines" in Computer Graphics (3rd Edition) (2013)
Paul S. Heckbert, editor. Graphics Gems IV. Academic Press Professional, Inc., USA, 1994.
Donald. E. Knuth, 1998, Addison-Wesley Longman, Inc., ISBN 0-201-89684-2, Addison-Wesley Professional; 3rd edition.
Joseph O'Rourke, "Search and Intersection" in Computational Geometry in C (2nd Edition) (1998)

spherical-volume-rendering / svr-algorithm

readme