2

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.

klaytonme
  • 83
  • 8
  • doing this with concentric squares is easy, but concentric spheres are problem because if you render voxelized sphere of radius `r` and `r+1` they will most likely share some voxels (that have distances between `r` and `r+1` from center ... so iterating through radius is a problem as with increasing `r` the step will be finer and finer (much less then 1) so how to handle that? You might compute all the combinations of integer coordinate distances between `r` and `r+1` ... now how to deal with continuity of points between neighboring spheres ? zig zag order of layers? what patter you aim for? – Spektre Jan 06 '23 at 09:24
  • however putting all this together will be probably really slooooow without "huge" LUTs ... You might also round down or up the radiuses to ease up a bit however that would lead to holes in spheres which is not known if desired? – Spektre Jan 06 '23 at 09:25
  • I actually don't mind the overlap between shells as much because including those would be less of a waste of processing than trying to eliminate them. If I'm fine with the overlap, how would I iterate each spherical shell? – klaytonme Jan 07 '23 at 01:06
  • for example similar to [Drawing 3D sphere in C/C++](https://stackoverflow.com/a/25135125/2521214) you just iterate in single direction in order: `r = <0,???>, x=<-r,+r>, y=<-r,+r>` and compute `z = sqrt(r*r-x*x-y*y)` or discard if `x*x+y*y>r*r` and for each surface voxel `x,y,z` emit voxels `x,y,z` and `x,y,-z` spherical coordinates would just slow and mess things (in higher radiuses due rounding) up if you want to consequent voxels to be neighboring each other then just iterate in zig-zag pattern. If youre interested in such approach comment me and I would bust up something simple in C++ – Spektre Jan 07 '23 at 08:14
  • you need only to handle the edge case once you hit near circumference of XY plane circle where might be more voxels in the same line instead of just `x,y,+z` and `x,y,-z` detecting such case need some more thinking but the output is just line between those two points (so one for loop through `z`) – Spektre Jan 07 '23 at 08:20

1 Answers1

0

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.

Davis Herring
  • 36,443
  • 4
  • 48
  • 76