How can I iterate a coordinate sphere using an expanding spherical sector (cone)?

Question

Given an integer 3D coordinate system, a center point P, a vector in some direction V, and a max sphere radius R:

I want to iterate over only integer points in a fashion that starts at P and goes along direction V until reaching the max radius R.

Then, for some small angle T iterate all points within the cone (or spherical sector) around V.

Incrementally expand T until T is pi/2 radians and every point within the sphere has been iterated.

I need to do this with O(1) space complexity. So the order of the points can't be precomputed/sorted but must result naturally from some math.

Example:

// Vector3 represents coordinates x, y, z
// where (typically) x is left/right, y is up/down, z is depth
Vector3 center = Vector3(0, 0, 0); // could be anything
Vector3 direction = Vector3(0, 100, 0); // could be anything
int radius = 4;
double piHalf = acos(0.0); // half of pi

std::queue list;
for (double angle = 0; angle < piHalf; angle+= .1)
{
    int x = // confusion begins here
    int y = // ..
    int z = // ..
    list.push(Vector3(x, y, z));
}

See picture for this example

The first coordinates that should be caught are:

A(0,0,0), C(0,1,0), D(0,2,0), E(0,3,0), B(0,4,0)

Then, expanding the angle somewhat (orange cone):

K(-1,0,3), X(1,0,3), (0,1,3), (0,-1,3)

Expanding the angle a bit more (green cone):

F(1,1,3), (-1,-1,3), (1,-1,3) (-1,1,3)

My guess for what would be next is:

L(1,0,2), (-1,0,2), (0,1,2), (0,-1,2)
M(2,0,3) would be hit somewhat after

Extra notes and observations:

A cone will hit a max of four points at its base, if the vector is perpendicular to an axis and originates at an integer point. It may also hit points along the cone wall depending on the angle
I am trying to do this in c++
I am aware of how to check whether a point X is within any given cone or spherical vector by comparing the angle between V and PX with T and am currently using this knowledge for a lesser solution.
This is not a homework question, I am working on a 3D video game~

user_2521214 · Answer

iterate all integer positions Q in your sphere

simple 3x nested for loops through x,y,z in range will do. Just check inside sphere so
```
u=(x,y,z)-P;
dot(u,u) <= R*R
```
test if point Q is exactly on V

simply by checking angle between PQ and V by dot product:
```
u = Q-P
u = u/|u|
v = V/|V|
if (dot(u,v)==1) point Q is on V
```
test if points is exactly on surface of "cone"

simply by checking angle between PQ and V by dot product:
```
u = Q-P
u = u/|u|
v = V/|V|
if (dot(u,v)==cos(T/2)) point Q is on "cone"
```
where I assume T is full "cone" angle not the half one.

Beware you need to use floats/double for this and make the comparison with some margin for error like:

if (fabs(dot(u,v)-1.0     )<1e-6) point Q is on V
if (fabs(dot(u,v)-cos(T/2))<1e-6) point Q is on "cone"

How can I iterate a coordinate sphere using an expanding spherical sector (cone)?

1 Answers