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

问题描述

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

我知道

这里有更高多边形数的超球体横截面(W=0.3):

如您所见，还有更多网格"；与标准参数化球坐标生成网格类似的特征.

但是，横截面要求渲染对象由覆盖对象体积的单纯形定义(即使是表面的也需要某种体积)，否则实现会因边缘情况处理而变得不等.

有关 4D 渲染的更多信息，请参阅:

• 除了最后一个角度之外，所有角度都在区间 <0,PI> 中，最后一个角度是 <0,2*PI>.这允许直接构造 n 球体流形/网格.在我的引擎中是这样的:

  //--------------------------------------------------------------------------void ND_mesh::set_HyperSphere (int N,double r)//尺寸，半径{//去做常量 int d1=12;常量 int d2=d1+d1;const double da1= M_PI/double(d1-1);常量双 da2=2.0*M_PI/double(d2);诠释我;重置(N)；如果 (n==2){诠释 i0, i1;int ia,ja;双a；pnt.add(0.0);pnt.add(0.0);对于 (ja=d2-1,ia=0,a=0.0;ia

  pnt[] 是点列表，_cube 添加一个由 5 个四面体构成的立方体，覆盖其体积.如您所见，这会创建 2D 圆盘、3D 球和 4D 球体(不是完整的体积，只是在多个相邻节点之间的层)表面".

  代码只是创建 n 球面网格点(具有恒定的角度增加)，然后使用 2、4 或 8 个相邻点(以及 2D/3D 的球心)将渲染图元添加到对象(三角形、四面体，立方体).

  然后渲染器只是将维度缩小到 3D 并渲染.

  还有另一种方法，那就是光线追踪.上述立场，但通过光线追踪，我们可以使用对象的代数表示，因此我们不需要任何网格、流形或拓扑.只需计算超球面和射线(只是一个点)的最近交点并进行相应的渲染...

  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 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
              }
          }
      }
  //---------------------------------------------------------------------------
  

  This is brute force that can be speeded up using ray castig see:

  • Drawing 3D sphere in C/C++

  which can boost speed considerably especially in higher dimensions.

  [Edit1] just some testing done

  screenshot is taken from 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 the algorithm and code should be OK. Be aware that complexity is O(N!) where N is number of dimensions and runtime is c0*(N!)*r where c0 is constant time, r is radius and N is number of dimensions.

  [Edit2] Now how to visualize more than 3D? There are 2 common approaches:

  1. projection

     either Orthographic (parallel rays as on images above) or Perspective (the moe distant stuff is smaller). The latter reveals the hidden stuff for example 4D axis aligned Tesseract with orthographic projection to 3D is just a cube, but with Perspective its cube inside bigger cube with all 16 corners interconnected connected...

  2. cross section

     You just cut N-dimensional space by a N-dimensional hyperplane and any intersection of your object and hyper plane will give you N-1 dimensional object. This can be applied recursively until hit 3D and render with standard methods.

  Both approaches can be combined (some dimensions are reduced by cross sections others with projection ...)

  Here some more examples of 4D hypersphere (centered (0,0,0,0) and low poly count so its not a wireframe mess):

  Here higher poly count hyper sphere cross-section (W=0.3):

  As you can see there are more "grid" like features than the standard parametrical spherical coordinates generated mesh.

  However cross section requires that that rendered objects are defined by simplexes covering the objects volume (even surface ones need some kind of volume) otherwise the implementation will get vary nasty filled with edge cases handling.

  For more info about 4D rendering see:

  • how should i handle (morphing) 4D objects in opengl?

  To get back to hypersphere:

  according to wiki n-sphere we can describe the surface points of n-sphere by parametric equations:

  Where all the angles except last are in interval <0,PI> and the last one is <0,2*PI>. This allows to construct n-sphere manifold/mesh directly. In my engine it looks like this:

  //---------------------------------------------------------------------------
  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
      }
  //---------------------------------------------------------------------------
  

  Where pnt[] is list of points and _cube adds a cube constructed from 5 tetrahedrons covering its volume. As you can see this creates 2D disc, 3D ball, and 4D sphere (not full volume just layer between manifold neighboring nodes) "surface".

  The code just creates n-sphere grid points (with constant angular increase) and then using the 2,4,or 8 neighboring points (and center of sphere for the 2D/3D) to add rendering primitive to object (triangle, tetrahedron, cube).

  The renderer then just reduce dimension to 3D and render.

  There is also one other approach for this and that is ray tracing. The above stand but with ray tracing we can use algebraic representation of object so we do not need any mesh nor manifolds nor topology. Simply compute closest intersection of a hypersphere and ray (which is just a point) and render accordingly ...

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