使用3D像素繪製球體（體素）

Question

您能否提出一種算法，只使用基本的plot(x,y,z)基元（可繪製單個體素）在3D空間中繪製球體？

我希望得到類似於Bresenham's circle algorithm的東西，但是對於3D而不是2D。我正在研究一個使用LED三維矩陣的低分辨率3D顯示器的硬件項目，所以我需要繪製一個球體，而不僅僅是一個2D投影（即圓形）。

的項目非常類似：

...或者看到它在行動here。

一種可能性我心目中是這樣的：

• 計算極點（給出的半徑）的Y座標（在原點爲中心的球體，這些將是-r和+r）
• 切割球體：對於每個水平面，在這些座標之間，計算通過使所述平面與球體相交而獲得的圓的半徑=>r 。
• 使用布氏算法繪製半徑r_我的實際圈上平面p_我。

FWIW，我使用的是.NET micro-framework microprocessor，所以編程是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

剛剛發現一個老q &一個有關生成球網，但頂部其實答案給你一段簡短的僞代碼來生成你的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))

檢查這種問答&一種細節:) procedurally generate a sphere mesh

Answer 4

我不相信運行的每個層上的中點畫圓算法，一旦你達到了極點會得到期望的結果，因爲你將不得不在表面差距在哪裏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個圓三個步驟）。最終得到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方法會有一致的計時而不管半徑如何，而當繪製大半徑球體時，該方法會減慢只會顯示一部分。然而，隨着顯示器立方體分辨率的提高，此算法時序將保持一致，而強力將增加。