I'm not quite sure the best way to articulate this question, but I am trying to find a relatively simple way programmatically (in Java ideally, though theory is welcome too) to iterate through voxels one at a time starting from a center point and radiating out spherically. The idea is that I can specify a final radius (r) and starting coordinate <x, y, z> and at any given point in the process, the code will have iterated through each point within a radius that grows from 0 to r over the course of the function.
To be clear, I know how to search every coordinate in a spherical volume using spherical coordinates, but I don't know how to do it in the right order (starting from the center and moving outward.) Also, because it's voxels, I don't want to waste a bunch of time rounding iterations in the center just so the resolution can be complete on the outer surface. Ideally, each iteration should cover a new voxel and each voxel should be iterated exactly once (although I am open to compromise if that isn't possible).
Thanks for your help, let me know if I need to specify any further.
This is an application for a priority queue with (squared) radius as the priority. Initialize it with the pair (0,(0,0,0)) and then, when dequeuing an element, consider each of its 3 neighbors with exactly one coordinate increased by 1. For each of those, compute its squared radius and insert it into the queue if that is no greater than r2. Some neighbor of some visited point must have the next smallest radius, so every point will be visited in order.
By symmetry, you can emit (±_i_,±_j_,±_k_) every time you dequeue a point (producing 1, 2, 4, or 8 values depending on how many coordinates are 0); you can also add (x,y,z) then. If you want to be even more sophisticated, you can require that i_≥_j_≥_k as you generate points and then additionally permute them on output, producing 48 points from (3,2,1).
If you break radius ties with the coordinates themselves, remembering the last value emitted is sufficient to discard duplicates even for multiple points with the same radius like (6,5,1) and (7,3,2). Each point is generated at most 3 times, so the number of duplicates is not excessive.