算法：将超球体渲染并填充成栅格？

Question

我试图栅格化并填充一个超球体。实质上，我有一个固定大小的d维网格和一个球（中心，半径），想找出哪些网格单元与球相交并存储它们的坐标。

我知道Midpoint circle algorithm，它利用8方向镜像，并产生圆的外部单元（边框）。我还修改了链接的维基百科代码，以便填充圆（也就是生成所有边框内部单元的坐标）。

然而，我不知道任何高维算法。例如，在4D中，我一直在考虑通过生成所有可能的圆来实现以下伪代码。基本思想是，由于4D球体是(x-x0)2 + (y-y0)**2 + (z-z0)**2 + (k-k0)**2 = r2，这等于(x-x0)2 + (y-y0)**2 = r2 - (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)

这个问题似乎很相关，但是我不理解答案。

- aeolist

---

填充球体的更快方法很可能是通过绘制所有距离中心小于或等于半径的体素的蛮力方法。从那里开始计算表面可能有点棘手。我建议检查我的答案，看看是否可以将其应用到n个维度：http://stackoverflow.com/questions/9683965/draw-a-sphere-surface-in-voxels-efficiently/9687311#9687311 - Nick Udell

你的光栅化设备是什么？你正在将 N-D 渲染到 ?-D，使用什么类型的投影方式？你使用什么填充/着色技术？你需要什么分辨率和帧率...没有这些信息很难回答。 - Spektre

@aeolist 我添加了[edit2]，包括一些新的信息、代码和截图。 - Spektre

Answer 1

由于一段时间内没有人回答，所以我提供了一个简单明显的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
            }
        }
    }
//---------------------------------------------------------------------------

这是一种暴力算法，可以使用射线投射进行加速，参见:

• 用C/C++绘制3D球体

这可以显著提高速度，尤其是在更高的维度下。

[编辑1] 只是做了一些测试

截图是上述代码的测试应用程序输出。查看 1D、2D、3D 和 4D 超球体的 XY 平面（z=0）。我不确定 1D，但其余部分都没问题（不确定 1D 是否定义为超空间或者只应该是一个点）。

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

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

1. 投影

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

2. 剖面

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

两种方法都可以结合使用（某些维度通过截面减少，其他维度通过投影减少...）

这里还有一些4D超球体的例子（位于(0,0,0,0)中心，低多边形计数，因此不会成为线框混乱）：

这里是高细分数量的超球截面（W=0.3）：

正如您所看到的，与生成标准参数化球坐标网格相比，这里有更多“网格”类似的特征。

然而，交叉部分要求渲染对象由简单覆盖对象体积的单纯形定义（即使是表面对象也需要某种体积），否则实现将变得非常麻烦，需要处理边缘情况。

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

• 我应该如何在OpenGL中处理（变形）4D对象？

回到超球体：

根据维基n-球体，我们可以通过参数方程式描述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 添加了一个由五个四面体构成的立方体来覆盖其体积。正如您所看到的，这创建了2D圆盘，3D球和4D球（不是完整的体积，只是流形相邻节点之间的层面）“表面”。

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

然后渲染器将维度降低到3D并进行渲染。

还有一种方法可以实现这一点，那就是射线跟踪。上述内容保持不变，但使用射线跟踪，我们可以使用对象的代数表示，因此我们不需要任何网格，流形或拓扑。只需计算超球体与射线（即点）的最近交点，并相应地进行渲染...

- Spektre