使用3D像素(体素)绘制球体

Question

你能建议一种只使用基本plot(x,y,z)图元(可以绘制单个体素)在3D空间中绘制球体的算法吗？

我希望类似于Bresenham的圆形算法,但是对于3D而不是2D.

仅供参考,我正在开发一个硬件项目,这是一个使用三维LED矩阵的低分辨率3D显示器,因此我需要实际绘制一个球体,而不仅仅是2D投影(即圆形).

该项目与此非常相似:

......或者在这里看到它.

我想到的一个可能性是:

• 计算极点的Y坐标(给定半径)(对于以原点为中心的球体,这些将是-r和+r)
• 切割球体:对于这些坐标之间的每个水平面p_i,计算通过使所述平面与球体相交得到的圆的半径=> r_i.
• 使用Bresenham算法在平面_i上绘制半径为r_i的实际圆.p

FWIW,我使用的是.NET微框架微处理器,因此编程是C#,但我不需要C#中的答案.

Answer 1

简单的强力方法是在网格中的每个体素上循环并计算它与球体中心的距离.如果体素的距离小于球体半径,则对体素着色.您可以通过消除平方根并将点积与半径平方进行比较来节省大量指令.

相当于最佳,肯定.但是如图所示,在8x8x8网格上,每个球体需要执行512次此操作.如果球体中心位于网格上,并且其半径是整数,则只需要整数数学.点积为3乘以2加.乘法很慢; 假设他们各自收到4条指令.另外,你需要进行比较.添加加载和存储,假设每个体素需要20条指令.这是每个球体10240条指令.

以16 MHz运行的Arduino每秒可以推动1562个球体.除非您正在进行大量其他数学和I/O,否则此算法应该足够好.

Answer 2

假设您已经有一个像您所说的绘图功能：

    public static void DrawSphere(double r, int lats, int longs)
    {
        int i, j;
        for (i = 0; i <= lats; i++)
        {
            double lat0 = Math.PI * (-0.5 + (double)(i - 1) / lats);
            double z0 = Math.Sin(lat0) * r;
            double zr0 = Math.Cos(lat0) * r;

            double lat1 = Math.PI * (-0.5 + (double)i / lats);
            double z1 = Math.Sin(lat1) * r;
            double zr1 = Math.Cos(lat1) * r;

            for (j = 0; j <= longs; j++)
            {
                double lng = 2 * Math.PI * (double)(j - 1) / longs;
                double x = Math.Cos(lng);
                double y = Math.Sin(lng);

                plot(x * zr0, y * zr0, z0);
                plot(x * zr1, y * zr1, z1);
            }
        }
    }

该函数应该以指定的纬度和经度分辨率在原点处绘制一个球体（根据您的多维数据集判断，您大概需要40或50左右的近似值）。虽然此算法不会“填充”球体，所以它只会提供轮廓，但是使用半径玩游戏应该可以填充内部，可能会降低拉特和长方体的分辨率。

Answer 3

我不相信一旦到达极点，就在每一层上运行中点圆算法将不会获得理想的结果，因为在LED不亮的表面上会有间隙。但是，这可能会提供您想要的结果，所以这取决于美学。这篇文章是基于使用中点圆算法确定穿过中间两个垂直八分圆点的层的半径，然后在绘制这些圆的每个圆时还设置了极性八分圆的点的。

我认为，根据@Nick Udall的评论和答案，使用圆算法来确定您的水平切片的半径，可以对我在他的答案的评论中提出的修改起作用。应该修改圆算法，以将初始误差作为输入，并且还要为极性八分圆画出额外的点。

• 在绘制标准圆算法点y0 + y1和y0 - y1：x0 +/- x, z0 +/- z, y0 +/- y1，x0 +/- z, z0 +/- x, y0 +/- y1，共16分。这形成了球体垂直的大部分。
• 另外绘制点x0 +/- y1, z0 +/- x, y0 +/- z和x0 +/- x, z0 +/- y1, y0 +/- z，总共16个点，这将形成球体的极帽。

通过将外部算法的误差传递到圆算法中，将允许对每个图层的圆进行亚体素调整。在不将误差传递给内部算法的情况下，圆的赤道将近似为圆柱，并且x，y和z轴上的每个近似球面将形成一个正方形。考虑到误差，给定足够大半径的每个面都将近似为实心圆。

以下代码是根据Wikipedia的中点圆算法修改的。该DrawCircle算法的命名法已更改为可在xz平面上运行，并添加了第三个初始点y0，y偏移量y1和初始误差error0。DrawSphere从同一个函数修改为第三个初始点y0并调用DrawCircle而不是DrawPixel

public static void DrawCircle(int x0, int y0, int z0, int y1, int radius, int error0)
{
  int x = radius, z = 0;
  int radiusError = error0; // Initial error state passed in, NOT 1-x

  while(x >= z)
  {
    // draw the 32 points here.
    z++;
    if(radiusError<0)
    {
      radiusError+=2*z+1;
    }
    else
    {
      x--;
      radiusError+=2*(z-x+1);
    }
  }
}

public static void DrawSphere(int x0, int y0, int z0, int radius)
{
  int x = radius, y = 0;
  int radiusError = 1-x;

  while(x >= y)
  {
    // pass in base point (x0,y0,z0), this algorithm's y as y1,
    // this algorithm's x as the radius, and pass along radius error.
    DrawCircle(x0, y0, z0, y, x, radiusError);
    y++;
    if(radiusError<0)
    {
      radiusError+=2*y+1;
    }
    else
    {
      x--;
      radiusError+=2*(y-x+1);
    }
  }
}

对于半径为4的球体（实际上需要9x9x9），这将运行DrawCircle例程的三个迭代，第一个绘制一个典型的半径为4的圆（三个步骤），第二个绘制一个半径为4的圆，初始误差为0（也三步），然后第三步绘制半径为3且初始误差为0的圆（也是三步）。最终得到9个计算点，每个点绘制32个像素。这使得32（每个圆点）×3（每个点的加法或减法运算）+ 6（每个迭代的加法，减法，移位运算）=每个计算点的102加法，减法或移位运算。在此示例中，每个圆为3点=每层306次操作。半径算法还在每层上添加了6个操作，并进行了3次迭代，因此306 + 6 * 3 = 936例如，半径为4的基本算术运算。这里的代价是您将重复设置一些像素，而无需进行其他条件检查（即x = 0，y = 0或z = 0），因此，如果I / O速度慢，添加条件检查可能会更好。假设所有LED在一开始就被清除，那么示例圆圈将设置288个LED，而由于重复设置，实际上要点亮的LED数量要少得多。

对于适用于8x8x8网格的所有球体，此方法看起来似乎比bruteforce方法的性能更好，但无论半径如何，bruteforce方法都将具有一致的时序，而当绘制仅包含一部分的大半径球体时，此方法会变慢显示。但是，随着显示立方体分辨率的提高，该算法的时序将保持一致，而蛮力将会增加。