geometry - 超球をラスタライズして塗りつぶすアルゴリズム?

Question

超球をラスタライズして塗りつぶそうとしています。本質的に、固定サイズの d 次元グリッドと球 (中心、半径) があり、グリッドのどのセルが球と重なっているかを調べ、それらの座標を保存したいと考えています。

8 方向のミラーリングを利用して円の外側のセル (境界線) を生成するMidpoint circle アルゴリズムを認識しています。また、リンクされたウィキペディアコードを変更して、円を塗りつぶします (つまり、境界内のすべてのセルの座標を生成します)。

ただし、高次元のアルゴリズムは知りません。たとえば 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)

この質問は関連しているようですが、答えがわかりません。

score 3 · Accepted Answer

しばらくの間誰も答えないので、ここに私のシンプルで明白な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 を使用して高速化できるブルートフォースです。

C/C++ での 3D 球体の描画

これにより、特に高次元で速度が大幅に向上します。

[編集1]いくつかのテストが行われました

超球フィル

スクリーンショットは、上記のコードのテストアプリの出力から取得されます。1D、2D、3D、および 4D 超球の表示XY平面 ( )。z=01Dについてはわかりませんが、残りは問題ありません（ハイパースペースが1Dに定義されているのか、代わりに点だけであるべきなのかわかりません）。

ピクセル数 ~ ボリュームも非常に似ているため、アルゴリズムとコードは問題ないはずです。複雑さはO(N!)N が次元数であり、ランタイムがc0*(N!)*r定数c0時間でrあり、半径が次元数であることに注意してくださいN。

[編集 2] では、3D 以上を視覚化する方法は? 2 つの一般的なアプローチがあります。

投影

Orthographic (上記の画像のように平行光線) または Perspective (mo 遠いものは小さい) のいずれかです。後者は、たとえば、3D への正射投影を使用した 4D 軸に位置合わせされた Tesseract は単なる立方体ですが、Perspective を使用すると、16 のコーナーすべてが相互接続された、より大きな立方体内の立方体が接続されています...
断面

N 次元の空間を N 次元の超平面で切り取るだけで、オブジェクトと超平面の交点から N-1 次元のオブジェクトが得られます。これは、3D にヒットし、標準的な方法でレンダリングされるまで、再帰的に適用できます。

両方のアプローチを組み合わせることができます (一部の寸法は断面によって縮小され、その他は投影されます ...)

4D ハイパースフィアの例をいくつか次に示します (中央(0,0,0,0)に配置され、ポリゴン数が少ないため、ワイヤフレームの混乱ではありません)。

ここでは、ポリゴン数が多い超球体の断面 (W=0.3):

ご覧のとおり、標準のパラメトリック球面座標生成メッシュよりも多くの「グリッド」のような機能があります。

ただし、断面では、オブジェクトのボリュームをカバーするシンプレックスによってレンダリングされたオブジェクトを定義する必要があります (サーフェスのものでも何らかのボリュームが必要です)。

4D レンダリングの詳細については、次を参照してください。

opengl で 4D オブジェクトをどのように処理 (モーフィング) する必要がありますか?

ハイパースフィアに戻るには:

wiki 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 に縮小してレンダリングします。

これにはもう 1 つのアプローチがあり、それはレイトレーシングです。上記のスタンドですが、レイトレーシングを使用すると、オブジェクトの代数表現を使用できるため、メッシュ、多様体、トポロジーは必要ありません。超球と光線 (単なる点) の最も近い交点を計算し、それに応じてレンダリングするだけです ...

geometry - 超球をラスタライズして塗りつぶすアルゴリズム?

1 に答える 1

Related

Reference