gpt4 book ai didi

geometry - 光栅化和填充超球面的算法?

转载 作者:行者123 更新时间:2023-12-01 14:24:12 26 4
gpt4 key购买 nike

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

我知道 Midpoint circle algorithm它利用 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)

question似乎相关,但我不明白答案。

最佳答案

一段时间没有人回答所以这里是我的简单而明显的 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 加速的蛮力,请参见:
  • Drawing 3D sphere in C/C++

  • 这可以显着提高速度,尤其是在更高维度上。
    [Edit1] 刚刚完成了一些测试
    Hypersphere fill
    屏幕截图取自上述代码的测试应用程序输出。查看 XY平面 ( z=0 ) 用于 1D、2D、3D 和 4D 超球面。我不确定一维,但其余的都可以(不确定超空间是为一维定义的还是应该只是一个点)。
    甚至像素数~体积看起来非常相似,所以算法和代码应该没问题。请注意,复杂性是 O(N!)其中 N 是维数,运行时间是 c0*(N!)*r哪里 c0是常数时间, r是半径和 N是维数。
    [Edit2] 现在如何可视化 3D 以上?有两种常用方法:
  • 投影
    正交(如上图所示的平行光线)或透视(moe 远处的东西较小)。后者揭示了隐藏的东西,例如 4D 轴对齐 Tesseract 与正交投影到 3D 只是一个立方体,但使用 Perspective,它的立方体位于更大的立方体内,所有 16 个角相互连接……
  • 横截面
    您只需通过 N 维超平面切割 N 维空间,您的对象和超平面的任何交集都会为您提供 N-1 维对象。这可以递归应用,直到命中 3D 并使用标准方法进行渲染。

  • 两种方法都可以结合使用(某些尺寸通过横截面减小,其他尺寸通过投影减小......)
    这里有更多 4D 超球面的例子(居中 (0,0,0,0) 和低多边形数量,所以它不是线框困惑):
    perspective vs. cross section
    这里更高的多边形计数超球体横截面(W = 0.3):
    more poly count
    正如您所看到的,与标准参数化球坐标生成的网格相比,有更多类似“网格”的特征。
    然而,横截面要求渲染对象由覆盖对象体积的单纯形定义(即使是表面对象也需要某种体积),否则实现会因边缘情况处理而变得令人讨厌。
    有关 4D 渲染的更多信息,请参阅:
  • how should i handle (morphing) 4D objects in opengl?

  • 回到超球面:
    根据 wiki n-sphere我们可以用参数方程来描述 n-sphere 的表面点:
    n-sphere
    除了最后一个角度之外的所有角度都在区间 <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 并进行渲染。
    还有另一种方法,那就是光线追踪。上述立场但通过光线追踪,我们可以使用对象的代数表示,因此我们不需要任何网格、流形或拓扑。只需计算超球面和射线(这只是一个点)的最近交点并相应地渲染......

    关于geometry - 光栅化和填充超球面的算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9046106/

    26 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com