算法来栅格化并填充超球面？ [英] algorithm to rasterize and fill a hypersphere?

问题描述

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

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

然而，我并不知道任何更高维的算法。例如在4d中，我一直在考虑通过产生所有可能的圆来实现，如下面的伪代码。基本思想是由于4d球是（x-x0）2 +（y-y0）** 2 +（z-z0）** 2 +（k-k0）** 2 = r （x-x 0）2 +（y-y 0）** 2 = r 2-（z-z 0）** 2 - （k-k 0）** 2。既然我知道如何绘制一个圆，我只需要为所有可能的z和k值生成所有的圆。

 所有维度的中心=（x0，y0，z0，k0）和半径r 
 
等于或高于2：//这是z和k 
 //制作一个可能的值列表这个尺寸可以带
 //从z0到z0 +半径，步长为1 
 all_lists.append（[dim0，dim0 + 1，...，dim0 + radius]）
 
产生all_lists中所有列表的结果
 //现在我有一个列表[[ Z0，K0]，[Z0，K0 + 1]，...，[Z0 + 1，K0]，[Z0 + 1，K0 + 1]，...，[Z0 +半径，K0] ,. .. [z0 + radius，k0 + radius]] 
 
为列表中的每个元素l计算圆形cut的半径
 l.append（r ** 2  - z ** 2  -  k ** 2）
 
现在调用中点圆算法，但对于它生成的每个（x，y）对，我们需要导出4个点，即（x，y ，±z，±k）
  

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

解

 很好，没有人回答一段时间，所以这里是简单明显的C ++解决方案。 // ------------------------------------------------ --------------------------- 
 const int N = 10; //维数
 struct point {double a [N]; }; // N维点
 #define color DWORD //你的颜色属性的类型
 // ----------------------- -------------------------------------------------- -  
 // N x嵌套为（a = a0; a< = a1; a + = da）如果结束，返回false 
 //可以优化很多，但为了清晰起见， 
 // ix = -1，N =维数/嵌套计数
 bool nested_for（double * a0，double * a，double * a1，double * da，int& ix，int N）
 {
 if（ix <0）
 {
 int i; 
 if（N <1）返回false; // N太低
 for（i = 0; i  a1 [i]）返回false，则对于（i = 0; i ; // a0> a1对于某些我是错误的！ 
 ix = N-1; 
返回true; 
 
 for（;;）// a + = da 
 {
 a [ix] + = da [ix];如果（a [ix] <= a1 [ix]）中断，则
; 
 if（！ix）返回false; //为
 a [ix] = a0 [ix]; 
 ix--; 
} 
 ix = N-1; 
 
返回true; 
} 
 // --------------------------------------- ------------------------------------ 
 void draw_point（point& p，color c ）
 {
 //绘制点... 
} 
 // --------------------- -------------------------------------------------- ---- 
 void fill_hypersphere（point& p0，double r，color c）
 {
 int i，ix; 
 bool init; 
指向a，b，a0，a1，da; 
 double aa，rr = r * r; 
 for（i = 0; i  for（i = 0; i 。 //像素之间的步骤
 for（ix = -1; nested_for（a0.a，aa，a1.a，da.a，ix，N）;）// N x嵌套为
 {
 aa = 0.0; // aa =从零开始的距离^ 2 
（i = 0; i  if（aa< = rr）//如果它在球体内
 {//计算翻译点由p0到b 
（i = 0; i  draw_point（b，c）; //并绘制/填充它或任何
} 
} 
} 
 // -------------------- -------------------------------------------------- ----- 
  

[Edit1]只是一些测试完成

• 这是测试应用程序的输出，用于查看XY平面（z = 0）以上代码


• 
  
• 一维，二维，三维和四维超球体


• 我不确定一维是什么，但其余的都没问题（不知道超空间是否定义为1D或者应该只是一个点）


• 即使像素计数〜卷看起来非常相似，所以它应该是OK


• 要注意复杂性是O（N！），其中N是尺寸


• 和运行时间= c0 *（N！）* r其中c0是固定时间，r是半径，N是尺寸数量
  

I'm trying to rasterize and fill a hypersphere. In essence, I have a d-dimensional grid of fixed size and a sphere (center, radius) and want to find out which cells of the grid overlap with the sphere and store their coordinates.

I am aware of the Midpoint circle algorithm which takes advantage of 8-way mirroring and produces the outer cells (border) of a circle. I have also altered the linked wikipedia code so as to fill the circle (that is, to produce the coordinates of all cells inside the border).

However I am unaware of any algorithms for higher dimension. For example in 4d, I've been thinking of implementing by producing all possible circles like in the following pseudocode. The basic idea is that since a 4d sphere is (x-x0)2 + (y-y0)**2 + (z-z0)**2 + (k-k0)**2 = r2, this is equal to (x-x0)2 + (y-y0)**2 = r2 - (z-z0)**2 - (k-k0)**2. Since I know how to draw a circle, i just need to produce all circles for all possible values of z and 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)

This question seems relevant, but I don't understand the answer.

解决方案

well no one answers for some time so here is simple and obvious C++ solution of mine:

//---------------------------------------------------------------------------
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] just some testing done

• this is test app output for code above
• viewing XY plane (z=0)
• for 1D,2D,3D and 4D hyperspheres
• I am not sure about 1D but the rest is OK (not sure if hyperspace is defined for 1D or should be only a point instead)
• even the pixel count ~ Volume looks very similar so it should be OK
• be aware that complexity is O(N!) where N is number of dimensions
• and runtime = c0*(N!)*r where c0 is constant time, r is radius and N is number of dimensions

这篇关于算法来栅格化并填充超球面？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！