4

我正在尝试栅格化并填充超球面。本质上，我有一个固定大小的 d 维网格和一个球体（中心、半径），并且想要找出网格的哪些单元格与球体重叠并存储它们的坐标。

我知道中点圆算法利用 8 向镜像并产生圆的外部单元格（边界）。我还更改了链接的维基百科代码以填充圆圈（即生成边界内所有单元格的坐标）。

但是我不知道任何更高维度的算法。例如在 4d 中，我一直在考虑通过生成所有可能的圆圈来实现，如下面的伪代码。基本思想是，由于 4d 球体是 (x-x0) 2 + (y-y0)**2 + (z-z0)**2 + (k-k0)**2 = r 2，所以等于到 (x-x0) 2 + (y-y0)**2 = r 2 - (z-z0)**2 - (k-k0)**2。因为我知道如何画一个圆圈，所以我只需要为 z 和 k 的所有可能值生成所有圆圈。

assume center=(x0,y0,z0,k0) and radius r

for all dimensions equal or higher than 2://this is z and k
  //make a list of possible values this dimension can take
  //from z0 to z0+radius with a step of 1
  all_lists.append([dim0,dim0+1,...,dim0+radius])

produce the product of all the lists in all_lists
//now i have a list [[z0,k0],[z0,k0+1],....,[z0+1,k0],[z0+1,k0+1],....,[z0+radius,k0],...[z0+radius,k0+radius]]

for every element l of the list, compute the radius of the circular "cut"
  l.append(r**2 - z**2 - k**2)

Now call the Midpoint Circle Algorithm, but for every (x,y) pair that it produces, we need to export 4 points, namely (x,y,±z,±k)

这个问题似乎很相关，但我不明白答案。

4

1 回答 1

3

好一段时间没有人回答，所以这是我的简单而明显的 C++ 解决方案：

//---------------------------------------------------------------------------
const int N=10;                     // number of dimensions
struct point { double a[N]; };      // N-dimensional point
#define color DWORD                 // type of your color property
//---------------------------------------------------------------------------
// N x nested for(a=a0;a<=a1;a+=da) return false if ended
// it could be optimized a lot but for clarity I leave it as is
// ix=-1 at start and N = number of dimensions / nested count
bool nested_for(double *a0,double *a,double *a1,double *da,int &ix,int N)
    {
    if (ix<0)
        {
        int i;
        if (N<1) return false;                          // N too low
        for (i=0;i<N;i++) a[i]=a0[i];
        for (i=0;i<N;i++) if (a[i]>a1[i]) return false; // a0>a1 for some i that is wrong !!!
        ix=N-1;
        return true;
        }
    for (;;)                                            // a+=da
        {
        a[ix]+=da[ix];
        if (a[ix]<=a1[ix]) break;
        if (!ix) return false;                          // end of nested for
        a[ix]=a0[ix];
        ix--;
        }
    ix=N-1;

    return true;
    }
//---------------------------------------------------------------------------
void draw_point(point &p,color c)
    {
    // draw your point ...
    }
//---------------------------------------------------------------------------
void fill_hypersphere(point &p0,double r,color c)
    {
    int i,ix;
    bool init;
    point a,b,a0,a1,da;
    double aa,rr=r*r;
    for (i=0;i<N;i++) a0.a[i]=-r;           // loop boundary for all axises <-r,+r>
    for (i=0;i<N;i++) a1.a[i]=+r;
    for (i=0;i<N;i++) da.a[i]=1.0;          // step between pixels
    for (ix=-1;nested_for(a0.a,a.a,a1.a,da.a,ix,N);) // N x nested for
        {
        aa=0.0;                             // aa = distance from zero ^ 2
        for (i=0;i<N;i++) aa+=a.a[i]*a.a[i];
        if (aa<=rr)                         // if it is inside sphere
            {                               // compute the translated point by p0 to b
            for (i=0;i<N;i++) b.a[i]=p0.a[i]+a.a[i];
            draw_point(b,c);                // and draw/fill it or whatever
            }
        }
    }
//---------------------------------------------------------------------------

这是可以使用 ray castig 加速的蛮力，请参阅：

这可以大大提高速度，尤其是在更高的维度上。

[Edit1] 只是做了一些测试

超球面填充

屏幕截图取自上述代码的测试应用程序输出。1D、2D、3D 和 4D 超球面的观察XY平面 ( z=0)。我不确定一维，但其余的都可以（不确定超空间是为一维定义的还是应该只是一个点）。

即使是像素数~体积看起来也很相似，所以算法和代码应该没问题。请注意，复杂性是其中O(N!)N 是维数，运行时间是常数时间、半径和维数。c0*(N!)*rc0rN

[Edit2] 现在如何可视化超过 3D？有两种常见的方法：

  1. 投影

    正交（如上图所示的平行光线）或透视（距离较远的东西更小）。后者揭示了隐藏的东西，例如 4D 轴对齐的 Tesseract 与正交投影到 3D 只是一个立方体，但使用透视法，它的立方体在更大的立方体内，所有 16 个角相互连接......

  2. 横截面

    您只需通过 N 维超平面切割 N 维空间，您的对象和超平面的任何交集都会给您 N-1 维对象。这可以递归地应用，直到达到 3D 并使用标准方法渲染。

两种方法都可以结合使用（某些尺寸通过横截面减小，另一些则通过投影...）

这里还有一些 4D 超球面的示例（居中(0,0,0,0)且多边形数量少，因此它不是线框混乱）：

透视图与横截面图

这里更高的多边形计数超球体横截面（W = 0.3）：

更多的聚计数

如您所见，与标准参数球面坐标生成的网格相比，有更多类似“网格”的特征。

然而，横截面要求渲染对象由覆盖对象体积的单纯形定义（即使表面对象也需要某种体积），否则实现将变得充满边缘情况处理。

有关 4D 渲染的更多信息，请参阅：

回到超球面：

根据wiki n-sphere，我们可以通过参数方程描述n-sphere的表面点：

n-球体

除了最后一个角度之外，所有角度都在区间<0,PI>中，最后一个角度是<0,2*PI>。这允许直接构造 n 球体流形/网格。在我的引擎中，它看起来像这样：

//---------------------------------------------------------------------------
void ND_mesh::set_HyperSphere     (int N,double r) // dimensions, radius
    {
    // ToDo
    const int d1=12;
    const int d2=d1+d1;
    const double da1=    M_PI/double(d1-1);
    const double da2=2.0*M_PI/double(d2);
    int i;
    reset(N);
    if (n==2)
        {
        int i0,i1;
        int ia,ja;
        double a;
        pnt.add(0.0);
        pnt.add(0.0);
        for (ja=d2-1,ia=0,a=0.0;ia<d2;ja=ia,ia++,a+=da2)
            {
            pnt.add(cos(a));
            pnt.add(sin(a));
            i0=ja+1;
            i1=ia+1;
            s3(i0,i1,0);
            }
        }
    if (n==3)
        {
        int i00,i01,i10,i11;
        int ia,ib,ja,jb;
        double a,b;
        pnt.add(0.0);
        pnt.add(0.0);
        pnt.add(0.0);
        for (ja=d1-1,ia=0,a=0.0;ia<d1;ja=ia,ia++,a+=da1)
         for (jb=d2-1,ib=0,b=0.0;ib<d2;jb=ib,ib++,b+=da2)
            {
            pnt.add(cos(a));
            pnt.add(sin(a)*cos(b));
            pnt.add(sin(a)*sin(b));
            i00=(ja*d2)+jb+1;
            i01=(ja*d2)+ib+1;
            i10=(ia*d2)+jb+1;
            i11=(ia*d2)+ib+1;
            s4(i00,i01,i11,0);
            s4(i00,i11,i10,0);
            }
        }
    if (n==4)
        {
        int i000,i001,i010,i011,i100,i101,i110,i111;
        int ia,ib,ic,ja,jb,jc;
        double a,b,c;
        pnt.add(0.0);
        pnt.add(0.0);
        pnt.add(0.0);
        pnt.add(0.0);
        for (ja=d1-1,ia=0,a=0.0;ia<d1;ja=ia,ia++,a+=da1)
         for (jb=d1-1,ib=0,b=0.0;ib<d1;jb=ib,ib++,b+=da1)
          for (jc=d2-1,ic=0,c=0.0;ic<d2;jc=ic,ic++,c+=da2)
            {
            pnt.add(cos(a));
            pnt.add(sin(a)*cos(b));
            pnt.add(sin(a)*sin(b)*cos(c));
            pnt.add(sin(a)*sin(b)*sin(c));
            i000=(ja*d1*d2)+(jb*d2)+jc+1;
            i001=(ja*d1*d2)+(jb*d2)+ic+1;
            i010=(ja*d1*d2)+(ib*d2)+jc+1;
            i011=(ja*d1*d2)+(ib*d2)+ic+1;
            i100=(ia*d1*d2)+(jb*d2)+jc+1;
            i101=(ia*d1*d2)+(jb*d2)+ic+1;
            i110=(ia*d1*d2)+(ib*d2)+jc+1;
            i111=(ia*d1*d2)+(ib*d2)+ic+1;
            _cube(i000,i001,i010,i011,i100,i101,i110,i111);
            }
        }

    for (i=0;i<pnt.num;i++) pnt.dat[i]*=r; // radius
    }
//---------------------------------------------------------------------------

pnt[]点列表在哪里，并_cube添加一个由 5 个四面体构成的立方体，覆盖其体积。如您所见，这会创建 2D 圆盘、3D 球和 4D 球体（不是完整体积，只是在多个相邻节点之间分层）“表面”。

该代码只是创建 n 球网格点（具有恒定的角度增加），然后使用 2、4 或 8 个相邻点（以及 2D/3D 的球心）向对象（三角形、四面体、立方体）添加渲染图元）。

渲染器然后只是将尺寸减小到 3D 并渲染。

还有另一种方法，那就是光线追踪。上述立场，但通过光线追踪，我们可以使用对象的代数表示，因此我们不需要任何网格、流形或拓扑。只需计算超球面和射线（这只是一个点）的最近交点并相应地渲染......

于 2014-02-05T10:46:22.977 回答