柵格化和填充超球面的算法？

我想要柵格化並填充超球面。實質上，我有一個固定大小的d維網格和一個球體（中心，半徑），並且想要找出網格中的哪些單元與球體重疊並存儲它們的座標。柵格化和填充超球面的算法？

我知道Midpoint circle algorithm利用8路鏡像併產生一個圓的外部單元格（邊框）。我還修改了鏈接的維基百科代碼以填充圓圈（即，生成邊框內所有單元格的座標）。

但我不知道任何更高維的算法。例如在4d中，我一直在考慮通過產生所有可能的圓來實現，如下面的僞代碼。其基本思想是由於4d球體是（x-x0）2 +（y-y0）** 2 +（z-z0）** 2 +（k-k0）** 2 = r 2，等於（x-x 0）2 +（y-y 0）** 2 = r 2-（z-z 0）** 2 - （k-k 0）** 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似乎相關，但我不明白答案。

來源

2012-01-28 aeolist

更快的填充球體的方法很可能是bru te的方法繪製所有體素的距離中心小於或等於半徑。從那裏開始工作可能會有點棘手。我會建議檢查我的答案在這裏，看看如果你可以應用到n維：http://stackoverflow.com/questions/9683965/draw-a-sphere-surface-in-voxels-efficiently/9687311#9687311 – 2012-03-14 13:03:16

什麼是你的光柵化設備？你正在渲染N-D到？-D以及如何（填充/着色技術是什麼類型的投影）？什麼樣的決議，你需要什麼樣的FPS ...沒有這個信息是很難回答的。 – Spektre 2013-09-30 16:33:55

好一段時間，因此在這裏沒有一個答案是我的簡單而明顯的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 leve 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 
      } 
     } 
    } 
//---------------------------------------------------------------------------

[EDIT1]只是一些測試來完成

Hypersphere fill

這是以上代碼的測試應用程序輸出
查看XY平面（z = 0）
爲1D，2D，3D和4D超球面
我不知道1D但其餘的是OK（不知道超空間被定義爲一維或應該不是僅僅一個點）
即使像素數〜Volume看起來非常相似，所以它應該是OK
請注意，複雜度爲O（N！），其中N是維數
和runtime = c0 *（N！）* r其中c0是恆定時間，r是半徑，N是尺寸的數量

來源

2014-02-05 10:46:22 Spektre

柵格化和填充超球面的算法？

回答

相關問題