Sectored sphere: quarter hemisphere traversal.

[cgyurgyik]

Describe the feature request Allow the ray to traverse only in a quarter of the hemisphere. For example, the first quadrant of a sphere. This will eventually lead to the generalized of sectored sphere traversal.

Test(s) that the feature request must pass

    TEST(SphericalCoordinateTraversal, FirstQuadrantHit) {
        const BoundVec3 sphere_center(0.0, 0.0, 0.0);
        const double sphere_max_radius = 10.0;
        const std::size_t num_radial_sections = 4;
        const std::size_t num_polar_sections = 4;
        const std::size_t num_azimuthal_sections = 8;
        const svr::SphereBound max_bound = {.radial=sphere_max_radius, .polar=M_PI/2.0, .azimuthal=M_PI/2.0};
        const svr::SphericalVoxelGrid grid(MIN_BOUND, max_bound, num_radial_sections, num_polar_sections,
                                           num_azimuthal_sections, sphere_center);
        const double t_begin = 0.0;
        const double t_end = 30.0;
        const auto actual_voxels = walkSphericalVolume(Ray(BoundVec3(13.0, 13.0, 13.0), FreeVec3(-1.0, -1.0, -1.0)),
                                                       grid, t_begin, t_end);
        const std::vector<int> expected_radial_voxels = {1, 2, 3, 4};
        const std::vector<int> expected_theta_voxels = {0, 0, 0, 0};
        const std::vector<int> expected_phi_voxels = {0, 0, 0, 0};
        expectEqualVoxels(actual_voxels, expected_radial_voxels, expected_theta_voxels, expected_phi_voxels);
    }

    TEST(SphericalCoordinateTraversal, FirstQuadrantMiss) {
        const BoundVec3 sphere_center(0.0, 0.0, 0.0);
        const double sphere_max_radius = 10.0;
        const std::size_t num_radial_sections = 4;
        const std::size_t num_polar_sections = 4;
        const std::size_t num_azimuthal_sections = 8;
        const svr::SphereBound max_bound = {.radial=sphere_max_radius, .polar=M_PI/2.0, .azimuthal=M_PI/2.0};
        const svr::SphericalVoxelGrid grid(MIN_BOUND, max_bound, num_radial_sections, num_polar_sections,
                                           num_azimuthal_sections, sphere_center);
        const double t_begin = 0.0;
        const double t_end = 30.0;
        const auto actual_voxels = walkSphericalVolume(Ray(BoundVec3(13.0, -13.0, 13.0), FreeVec3(-1.0, 1.0, -1.0)),
                                                       grid, t_begin, t_end);
        EXPECT_EQ(actual_voxels.size(), 0);
    }

Expected behavior The ray should only traverse voxels within the quarter hemisphere. Once the ray exits the quarter hemisphere, the traversal algorithm ends and returns said voxels.

Screenshots N/A

Additional context This is in relation to the sectored sphere traversal discussed in #102.

Potential solutions (optional) I implemented this very simply using radial voxels as the limitation. For example, to traverse the first quadrant, I'd set the [min radial, max radial] bounds to [1, N] respectively. Then, the ray would traverse until radial voxel == N. A limitation of this is that we want the ray to traverse even when it is within the radial voxel N; it should only stop when it reaches the planes made by the X, Y, Z axes. We could calculate the time it takes for the ray to reach such a plane, but this would need to be generalized for any sectored sphere.

[ak-2485]

@cgyurgyik is this potential solution for maxing out on radial voxels included in the current version of the cpp code? I don't see it in the traversal.

[cgyurgyik]

Nope I ended up reverting it for now. It's an easy re-add. Right now I can get these test cases to pass by setting t = 0.5 since that means it'll travel exactly half the sphere

[ak-2485]

@cgyurgyik One question I have is, how costly is the grid initialization? I ask this because it seems like we can take two routes: (1) we break up the whole grid [0,2pi]^2 and [rmin,rmax] according to the max/min parameters and check for max out in the traversal. (2) the grid we traverse actually matches the min/mix parameters (i.e. is only a section of a sphere).

[ak-2485]

For the time fix: what if we have a ray whose direction and initial point are defined such that, at half of its traversal time, it is has crossed the line y=0?

[cgyurgyik]

Right now, I've implemented it in a way such that many calculations are done in grid initialization rather than each time a ray is sent through the grid. So while grid initialization is costly, as long as we send many rays through it, then its amortized.

I can't imagine either of those two routes being bad, I just would have to think about it, and am not as familiar with AMR as you and @matthewturk are. As for the second question, I'm not sure exactly what you're getting at.