使用3D像素（体素）绘制球形

Question

你能否提供一种算法，仅使用基本的plot(x,y,z)原始函数（用于绘制单个体素），在3D空间中绘制一个球体？

我希望能得到类似于Bresenham圆弧算法的东西，但是针对的是3D而不是2D。

顺便说一下，我的硬件项目是一个低分辨率的3D显示器，使用LED的三维矩阵，因此我需要实际绘制一个球体，而不仅仅是一个2D投影（即圆形）。

该项目与以下项目非常相似：

... 或者在这里查看它的运行情况。

我心中有一个可能的算法：

• 计算两极（半径已知）的Y坐标（对于以原点为中心的球体，这些坐标将是-r和+r）
• 切片球体：对于两极之间的每个水平面p_i，计算与球体相交得到的圆的半径=> r_i。
• 使用Bresenham算法在平面p_i上绘制实际半径为r_i的圆。

顺便说一下，我正在使用.NET微型框架微处理器进行编程，因此编程语言是C#，但我不需要答案是用C＃编写的。

- Cristian Diaconescu

---

从LED球来看，我们是否应该假设您需要以某种方式绘制球体的内部？ - NominSim

@NominSim 我不这么认为。在这种情况下，他不会谈论Bresenham圆形光栅化，而可以直接使用japreiss的暴力解决方案。 - Christian Rau

@Christian 实际上，我想两个选项都要。 - Cristian Diaconescu

在这种情况下，我建议使用暴力算法生成实体版本，然后使用形态学操作获取表面。Solid - Erode(Solid)应该可以解决问题。 - japreiss

我不确定，但是我可能在这里用类似Bresenham算法的球面算法回答了你的问题：http://stackoverflow.com/questions/9683965/draw-a-sphere-surface-in-voxels-efficiently/9687311#9687311 - Nick Udell

Answer 1

简单而暴力的方法是循环遍历网格中的每个体素，并计算其与球心的距离。然后，如果体素的距离小于球半径，则对其进行着色。通过消除平方根并将点积与半径的平方进行比较，可以节省大量指令。

这确实远非最优解。但在如图所示的8x8x8网格上，每个球需要执行512次此操作。如果球心位于网格上且其半径为整数，则只需要进行整数运算。点积需要3次乘法和2次加法。乘法很慢；假设它们每个需要4条指令。再加上比较、读取和存储，每个体素的成本约为20条指令。这意味着每个球需执行10240条指令。

在16 MHz的Arduino上，每秒可以处理1562个球。除非您还在进行大量其他数学和I/O操作，否则该算法应该足够好用。

- japreiss

---

问题在于他似乎不想要一个实心的球体。在这种情况下，你面临着经典的光栅化问题，需要防止球体表面出现孔洞和肿胀。尽管如此，他仍然可以使用你的解决方案，并通过检查其6个邻居来进行第二次遍历并删除所有内部体素。 - Christian Rau

没错，对于内部体素的移除，你不需要第二次遍历，因为对象是隐式定义的。但在这种情况下，你平均每个体素需要进行超过1次的距离计算。 - Christian Rau

是的，起初我以为在演示视频中填充了它，但仔细检查后发现只是外壳。我同意你的第一条评论，执行形态学操作会最简单。 - japreiss

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左右的分辨率）。这个算法不能“填充”球体，所以它只提供了一个轮廓，但通过调整半径应该可以填充内部，不过沿途纬线和经线的分辨率可能会逐渐降低。

- NominSim

---

你不需要在绘图调用中将坐标乘以r吗？因为r未使用，这意味着它将始终绘制半径为1的球体。 - Cedric Mamo

为什么要2个图？有什么区别？ - John T

Answer 3

我不相信在每个层上运行中点圆算法会产生期望的结果，因为当你到达极点时，表面上会有未点亮的LED间隙。这可能会产生您想要的结果，但这取决于美学。本帖子基于使用中点圆算法通过中间的两个垂直八分之一确定层的半径，然后在绘制每个圆时还设置了两极八分之一的点。

我认为根据@Nick Udall的评论和答案here，使用圆算法来确定水平切片的半径将与我在他的答案评论中提出的修改一起使用。圆算法应该被修改为将初始误差作为输入，并且还应为两极八分之一绘制附加点。

• 在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轴上的每个近似球面将形成一个正方形。包含误差后，给定足够大的半径，每个面都将近似为填充的圆形。

---

以下代码修改自维基百科的Midpoint circle algorithm。 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的圆形（三个步骤），第二次绘制初始误差为0的半径为4的圆形（同样是三个步骤），然后第三次绘制初始误差为0的半径为3的圆形（同样是三个步骤）。这最终将计算出九个点，每个点绘制32个像素。 这使得每个计算点需要执行32（每个圆的点数）x 3（每个点的加或减操作数）+ 6（每次迭代的加、减、移位操作数）= 102次基本算术运算。在这个例子中，每个圆有3个点 = 每层306个操作。半径算法还会增加每层6个操作，并迭代3次，因此对于半径为4的示例，总共需要 306 + 6 * 3 = 936 基本算术运算。 这里的成本是您将重复设置一些像素而无需进行其他条件检查（即x = 0、y = 0或z = 0），因此如果您的I/O速度较慢，则最好添加条件检查。假设所有LED都在开始时被清除，则示例圆将设置288个LED，而实际上由于重复设置而实际点亮的LED要少得多。

看起来这种方法在适合8x8x8网格中的所有球体上都比暴力方法表现更好，但暴力方法的时间始终保持一致，而这种方法在绘制大半径球体时会变慢，因为只有部分会显示。然而，随着显示立方体分辨率的增加，这种算法的计时将保持一致，而暴力方法将增加。

- rjp

---

我不明白哪里是绘制图形的实际部分。 - John T

Answer 4

刚刚发现了一个关于生成球体网格的旧问答，但是最佳答案实际上给出了一小段伪代码来生成你的X、Y和Z：

(x, y, z) = (sin(Pi * m/M) cos(2Pi * n/N), sin(Pi * m/M) sin(2Pi * n/N), cos(Pi * m/M))

查看此问答以获取详细信息 :) 程序化生成球体网格

- Kotch

---

这不就是NominSim的解决方案吗？ - Christian Rau

Answer 5

我的解决方案使用浮点数运算而不是整数运算，虽然不是理想的选择，但它可以工作。

private static void DrawSphere(float radius, int posX, int poxY, int posZ)
{
    // determines how far apart the pixels are
    float density = 1;

    for (float i = 0; i < 90; i += density)
    {
        float x1 = radius * Math.Cos(i * Math.PI / 180);
        float y1 = radius * Math.Sin(i * Math.PI / 180);

        for (float j = 0; j < 45; j += density)
        {
            float x2 = x1 * Math.Cos(j * Math.PI / 180);
            float y2 = x1 * Math.Sin(j * Math.PI / 180);
            
            int x = (int)Math.Round(x2) + posX;
            int y = (int)Math.Round(y1) + posY;
            int z = (int)Math.Round(y2) + posZ;

            DrawPixel(x, y, z);
            DrawPixel(x, y, -z);
            DrawPixel(-x, y, z);
            DrawPixel(-x, y, -z);

            DrawPixel(z, y, x);
            DrawPixel(z, y, -x);
            DrawPixel(-z, y, x);
            DrawPixel(-z, y, -x);

            DrawPixel(x, -y, z);
            DrawPixel(x, -y, -z);
            DrawPixel(-x, -y, z);
            DrawPixel(-x, -y, -z);

            DrawPixel(z, -y, x);
            DrawPixel(z, -y, -x);
            DrawPixel(-z, -y, x);
            DrawPixel(-z, -y, -x);
        }
    }
}

- Oogamar