c++ - 如何使用扩展的球形扇形(圆锥)来迭代坐标球？

Question

给定一个整数3D坐标系，一个中心点 P ，沿某个方向的 vector V 以及一个最大球体半径 R :
我想以 P 并沿 V 的方向开始直到仅到达最大半径 R 的方式仅迭代整数点。
然后，对于某个小 Angular T ，迭代 V 周围的圆锥体(或球面扇区)中的所有点。
逐步扩展 T ，直到T为pi / 2弧度，并且球体中的每个点都已迭代。
我需要使用O(1)空间复杂度来做到这一点。因此，点的顺序无法预先计算/排序，但必须自然地通过一些数学运算得出。

例:

// 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<Vector3> list;
for (double angle = 0; angle < piHalf; angle+= .1)
{
    int x = // confusion begins here
    int y = // ..
    int z = // ..
    list.push(Vector3(x, y, z));
}

请参阅此示例的图片
应该捕获的第一个坐标是:

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

然后，稍微扩展 Angular (橙色圆锥):

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

进一步扩大 Angular (绿锥):

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

我对接下来的猜测是:

L(1,0,2)，(-1,0,2)，(0,1,2)，(0，-1,2)

之后

M(2,0,3)会被击中


额外说明和观察:

如果 vector 垂直于轴并起源于整数点，则圆锥体将在其底部最多击中四个点。根据

的 Angular ，它也可能沿锥壁撞击点

我正在尝试使用c++

我知道如何通过将V和PX之间的 Angular 与T进行比较来检查点X是否在任何给定的圆锥或球面 vector 内，并且目前正在将此知识用于较小的解决方案。

这不是作业问题，我正在开发3D电子游戏〜

Answer 1

迭代您球体中的所有整数位置Q
简单的3x嵌套for在x,y,z范围内循环遍历<P-R,P+R>。只需检查球体内部即可

u=(x,y,z)-P;
dot(u,u) <= R*R

测试点Q是否完全在V上
只需通过按乘积检查PQ和V之间的 Angular 即可:

u = Q-P
u = u/|u|
v = V/|V|
if (dot(u,v)==1) point Q is on V

测试点是否恰好在“圆锥”的表面上
只需通过按乘积检查PQ和V之间的 Angular 即可:

u = Q-P
u = u/|u|
v = V/|V|
if (dot(u,v)==cos(T/2)) point Q is on "cone"

我假设T是完整的“圆锥”角而不是一半。

当心，您需要为此使用floats/double，并以一定的误差进行比较，例如:

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"