我正在寻找一种算法，在小分辨率下绘制漂亮的3D球体。我找到了Bresenham圆算法，但它是用于2D绘图的。我只需要球体的边框（不需要填充）。我也搜索了问题的解决方案，但我没有找到任何有用的信息。这篇文章没能帮助我（什么是暴力算法？）。我不能使用任何OpenGL库，我需要原生C/C++解决方案。谢谢。
在C/C++中绘制3D球体
5
- Ezio_
12
2很抱歉，您所述的问题没有解决方案。C/C++并没有定义标准图形库。我也有些惊讶，您还没有决定使用哪种语言。 - David Heffernan
5圆形图画有什么问题吗？一个三维球体的边界就是一个圆。 - dari
1@DavidHeffernan 我正在使用C语言编程，但是两种语言之间并没有太大的区别，所以即使有人展示C++代码，重写成C也不难。其他语言也可以接受，我想找到这个想法！ - Ezio_
1你需要的是一个球体镶嵌算法，有很多相关的教程可以参考。你可以在建模程序的脚本语言中实现这样的算法；你不需要画任何东西。 - user1095108
2请不要因为这个人表达得不够完美就对他进行攻击，他只是在寻找一种独立于库的解决方案。显然，他的意思是要找到一种生成表示球体的像素数组的方法，而不使用库，以便他可以理解这个过程，然后使用标准的OpenGL库自己实现它。所以，请不要因为创作者没有完美地表达自己的想法而对这个有效的帖子进行贬低。 - Jack G
显示剩余7条评论
4个回答
7
如果我理解正确，您想渲染球体的所有表面 Voxels。
暴力方法是 O(R^3)。如果您只是从平面投射光线并计算第三个坐标，则可以得到O(R^2)，但要确保没有缺少Voxels，您必须从所有三个平面进行此投影，这仍然是 O(R^2)
它看起来像这样：
在 LED 立方体 16x16x16 模拟中。现在是算法：
compute visible bounding box
no need to render whole rendering space just the sphere so center +/- radius...
take one plane (XY for example)
Cast rays from all
x,ypoints inside bounding box which is just 2 for loops and compute thezcoordinates where the ray hits via sphere equation:(x-x0)^2 + (y-y0)^2 + (z-z0)^2 = R^2so
z=z0 +/- sqrt(R^2 - (x-x0)^2 - (y-y0)^2)and render the two voxels. The
int sqrt(int x)for limited size (like LED Cube/Screen or Voxel space) can be done via LUT lookup table to speed things up.do the step #2 for all planes (
xy,yz,xz)
C++代码如下：
//---------------------------------------------------------------------------
//--- LED cube class ver: 1.00 ----------------------------------------------
//---------------------------------------------------------------------------
#ifndef _LED_cube_h
#define _LED_cube_h
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
const int _LED_cube_size=16;
//---------------------------------------------------------------------------
class LED_cube
{
public:
int n,map[_LED_cube_size][_LED_cube_size][_LED_cube_size];
LED_cube() { n=_LED_cube_size; }
LED_cube(LED_cube& a) { *this=a; }
~LED_cube() { }
LED_cube* operator = (const LED_cube *a) { *this=*a; return this; }
//LED_cube* operator = (const LED_cube &a) { /*...copy...*/ return this; }
void cls(int col); // clear cube with col 0x00BBGGRR
void sphere(int x0,int y0,int z0,int r,int col); // draws sphere surface with col 0x00BBGGRR
void glDraw(); // render cube by OpenGL as 1x1x1 cube at 0,0,0
};
//---------------------------------------------------------------------------
void LED_cube::cls(int col)
{
int x,y,z;
for (x=0;x<n;x++)
for (y=0;y<n;y++)
for (z=0;z<n;z++)
map[x][y][z]=col;
}
//---------------------------------------------------------------------------
void LED_cube::sphere(int x0,int y0,int z0,int r,int col)
{
int x,y,z,xa,ya,za,xb,yb,zb,xr,yr,zr,xx,yy,zz,rr=r*r;
// bounding box
xa=x0-r; if (xa<0) xa=0; xb=x0+r; if (xb>n) xb=n;
ya=y0-r; if (ya<0) ya=0; yb=y0+r; if (yb>n) yb=n;
za=z0-r; if (za<0) za=0; zb=z0+r; if (zb>n) zb=n;
// project xy plane
for (x=xa,xr=x-x0,xx=xr*xr;x<xb;x++,xr++,xx=xr*xr)
for (y=ya,yr=y-y0,yy=yr*yr;y<yb;y++,yr++,yy=yr*yr)
{
zz=rr-xx-yy; if (zz<0) continue; zr=sqrt(zz);
z=z0-zr; if ((z>0)&&(z<n)) map[x][y][z]=col;
z=z0+zr; if ((z>0)&&(z<n)) map[x][y][z]=col;
}
// project xz plane
for (x=xa,xr=x-x0,xx=xr*xr;x<xb;x++,xr++,xx=xr*xr)
for (z=za,zr=z-z0,zz=zr*zr;z<zb;z++,zr++,zz=zr*zr)
{
yy=rr-xx-zz; if (yy<0) continue; yr=sqrt(yy);
y=y0-yr; if ((y>0)&&(y<n)) map[x][y][z]=col;
y=y0+yr; if ((y>0)&&(y<n)) map[x][y][z]=col;
}
// project yz plane
for (y=ya,yr=y-y0,yy=yr*yr;y<yb;y++,yr++,yy=yr*yr)
for (z=za,zr=z-z0,zz=zr*zr;z<zb;z++,zr++,zz=zr*zr)
{
xx=rr-zz-yy; if (xx<0) continue; xr=sqrt(xx);
x=x0-xr; if ((x>0)&&(x<n)) map[x][y][z]=col;
x=x0+xr; if ((x>0)&&(x<n)) map[x][y][z]=col;
}
}
//---------------------------------------------------------------------------
void LED_cube::glDraw()
{
#ifdef __gl_h_
int x,y,z;
float p[3],dp=1.0/float(n-1);
glEnable(GL_BLEND);
glBlendFunc(GL_ONE,GL_ONE);
glPointSize(2.0);
glBegin(GL_POINTS);
for (p[0]=-0.5,x=0;x<n;x++,p[0]+=dp)
for (p[1]=-0.5,y=0;y<n;y++,p[1]+=dp)
for (p[2]=-0.5,z=0;z<n;z++,p[2]+=dp)
{
glColor4ubv((BYTE*)(&map[x][y][z]));
glVertex3fv(p);
}
glEnd();
glDisable(GL_BLEND);
glPointSize(1.0);
#endif
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
类的用法:
LED_cube cube;
cube.cls(0x00202020); // clear space to dark gray color
int a=cube.n>>1; // just place sphere to middle and size almost the whole space
int r=a-3;
cube.sphere(a,a,a,r,0x00FFFFFF);
cube.glDraw(); // just for mine visualization you have to rewrite it to your rendering system
如果你只想使用C，那么需要将类分解为全局函数和变量，并将C++运算符
x ++，--，+ =，- =，* =，...翻译成C风格的x = x + 1，...。- Spektre
5
根据链接，看起来您更感兴趣的是关于球体的体素算法，而不是图形本身；类似this page的内容可以帮到您。您需要的不是一个实心球，而是只有表面的球体。
中点圆算法可用于绘制3D体素球体：将球体视为一堆切片，每个切片包含一个圆。
在实践中，您使用两个嵌套的中点圆，外部定义内部圆的半径。（尽管一个朴素的算法在互相叠加的圆上绘制圆可能会留下体素中的空洞，但中点圆算法利用对称性，如果正确实现，就不应该出现这种空洞。）
您可以同时构建六个顶部，就像将正方体雕刻成球体一样。由于每个顶部的表面倾斜度始终小于1，因此在顶部向外移动时，每个坐标最多只会改变1，因此不会出现空洞。
这种方法的问题在于复杂性：每个计算出的点可能会影响多达48个体素单元。（在每个顶点处，每个点都在一个八分之一球内计算，因此影响了八个单元。有六个顶点，6*8=48。）
我建议采用不同的方法。
以x0，y0，z0为中心，r半径的球面方程式为：
（x - x0）2 + （y - y0）2 + （z - z0）2 = r2 对于整数坐标，网格点很少正好在球面上，允许一定范围内的值：
随着网格大小的增加，您可以表示每个尺寸的球体的更多变体。
上述函数在微控制器上特别有用，因为您可以简单地循环遍历您的晶格，在每个点更新状态，如您所愿。此外，大多数微控制器的内存都很紧张，但具有非常快（单时钟）的加法、减法和乘法指令。（虽然16×16位乘法与32位结果通常需要两个或更多指令。）
典型的微控制器没有ROM/flash功能来存储足够有趣的体素模式，只有少数具有通过SPI从SD卡进行DMA的能力（因此您可以从microSD卡加载体素模式的“帧”），但像上面的函数一样可以产生具有少量输入的有趣形状-特别是您可以插值的输入。
上述函数还可以适应近似抗锯齿（通过将
在实践中，您使用两个嵌套的中点圆，外部定义内部圆的半径。（尽管一个朴素的算法在互相叠加的圆上绘制圆可能会留下体素中的空洞，但中点圆算法利用对称性，如果正确实现，就不应该出现这种空洞。）
您可以同时构建六个顶部，就像将正方体雕刻成球体一样。由于每个顶部的表面倾斜度始终小于1，因此在顶部向外移动时，每个坐标最多只会改变1，因此不会出现空洞。
这种方法的问题在于复杂性：每个计算出的点可能会影响多达48个体素单元。（在每个顶点处，每个点都在一个八分之一球内计算，因此影响了八个单元。有六个顶点，6*8=48。）
我建议采用不同的方法。
以x0，y0，z0为中心，r半径的球面方程式为：
（x - x0）2 + （y - y0）2 + （z - z0）2 = r2 对于整数坐标，网格点很少正好在球面上，允许一定范围内的值：
RRMIN ≤ (x - x0)2 + (y - y0)2 + (z - z0)2 ≤ RRMAX
其中，RRMIN和RRMAX是常数；具体来说，是到球形中心的最小和最大距离的平方。
我建议在一般情况下使用加倍坐标。这样可以选择球的中心是否位于坐标上（意味着奇数直径），或位于两个相邻坐标之间的中心（意味着偶数直径）。
如果您有一个大小为SIZE×SIZE×SIZE的像素格网（灯光、建筑块等），则
int sphere_surface(const char x, const char y, const char z,
const char size, const int rrmin, const int rrmax)
{
const int center = size - (size & 1); /* Size rounded down to even integer */
const int dx = center - x - x,
dy = center - y - y,
dz = center - z - z; /* Doubled coordinates */
const int rr = dx*dx + dy*dy + dz*dz; /* Distance squared */
return (rrmin <= rr) && (rr <= rrmax);
}
如果点(x,y,z)在以立方体为中心的球体表面区域内，返回1。(严格地说，它返回该点到大小为size的立方体中心的距离是否在sqrt(rrmin)/2和sqrt(rrmax)/2之间，包括两端值。)
rrmin和rrmax的“正确”值高度依赖于上下文环境。rrmax通常接近于size*size(记住，函数使用双倍坐标)，而rrmin略小。
例如，如果你有一个3×3×3的网格，你只想让每个面的六个中心单元满足条件；你可以用size=3，rrmin=1，rrmax=4来实现：
size=4、rrmin=11、rrmax=11来实现这一点。
使用5×5×5网格，我们可以看到上述算法的有趣副作用。
size=5，rrmin=8，rrmax=16会产生一个非常“角形”的球体，几乎是一个立在角落的立方体：
size=5，rrmin=12，rrmax=20 可得到我最喜欢的近似球体：
size=5, rrmin=16, rrmax=24可以生成一个圆角立方体（每个面都是一个3×3的平面）：
rrmin = 0也包括所有内部单元格，导致得到一个球而不仅仅是一个球体表面。随着网格大小的增加，您可以表示每个尺寸的球体的更多变体。
上述函数在微控制器上特别有用，因为您可以简单地循环遍历您的晶格，在每个点更新状态，如您所愿。此外，大多数微控制器的内存都很紧张，但具有非常快（单时钟）的加法、减法和乘法指令。（虽然16×16位乘法与32位结果通常需要两个或更多指令。）
典型的微控制器没有ROM/flash功能来存储足够有趣的体素模式，只有少数具有通过SPI从SD卡进行DMA的能力（因此您可以从microSD卡加载体素模式的“帧”），但像上面的函数一样可以产生具有少量输入的有趣形状-特别是您可以插值的输入。
上述函数还可以适应近似抗锯齿（通过将
rr与rrmin和rrmax进行比较），以防您的体素不仅仅是二进制，而是例如PWM控制的LED。
由于上述内容通常比较难以可视化，因此我使用了一个小技巧来生成上面的图片。当给定size、rrmin和rrmax作为命令行参数时，它将输出SVG图像到标准输出，以及ASCII切片到标准错误。
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define BORDER 2
#define XC(x,y,z) ((x)*16 + (y)*12)
#define YC(x,y,z) ((x)*6 - (y)*8 - (z)*17)
static int xt = 0;
static int yt = 0;
static void fcube(FILE *out, const int x, const int y, const int z, const int fill)
{
const int xc = xt + XC(x,y,z);
const int yc = yt + YC(x,y,z);
fprintf(out, "<path d=\"M%d,%dl16,6,12,-8,0,-17,-16,-6,-12,8z\" fill=\"#%06x\" stroke=\"#000\" />\n", xc, yc, fill & 0xFFFFFF);
fprintf(out, "<path d=\"M%d,%dl16,6,12,-8m-12,8l0,17\" fill=\"none\" stroke=\"#000\" />\n", xc, yc-17);
}
static unsigned long rrmin = 0UL;
static unsigned long rrmax = 0UL;
static int center = 0;
static int surface(const int x, const int y, const int z)
{
/* Doubled coordinates: */
const long dx = 2*x - center,
dy = 2*y - center,
dz = 2*z - center;
const unsigned long rr = dx*dx + dy*dy + dz*dz;
return (rrmin <= rr) && (rr <= rrmax);
}
int main(int argc, char *argv[])
{
int width, height;
int size, x, y, z;
char dummy;
if (argc != 4 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
fprintf(stderr, "\n");
fprintf(stderr, "Usage: %s SIZE RRMIN RRMAX\n", argv[0]);
fprintf(stderr, "Where\n");
fprintf(stderr, " SIZE is the size of the voxel cube\n");
fprintf(stderr, " RRMIN is the minimum distance squared, and\n");
fprintf(stderr, " RRMAX is the maximum distance squared,\n");
fprintf(stderr, " using doubled coordinates.\n");
fprintf(stderr, "\n");
fprintf(stderr, "Examples:\n");
fprintf(stderr, " %s 3 1 4\n", argv[0]);
fprintf(stderr, " %s 4 11 11\n", argv[0]);
fprintf(stderr, " %s 5 8 16\n", argv[0]);
fprintf(stderr, " %s 5 12 20\n", argv[0]);
fprintf(stderr, " %s 5 16 24\n", argv[0]);
fprintf(stderr, "\n");
return EXIT_FAILURE;
}
if (sscanf(argv[1], " %d %c", &size, &dummy) != 1 || size < 3) {
fprintf(stderr, "%s: Invalid size.\n", argv[1]);
return EXIT_FAILURE;
}
if (sscanf(argv[2], " %lu %c", &rrmin, &dummy) != 1) {
fprintf(stderr, "%s: Invalid rrmin.\n", argv[2]);
return EXIT_FAILURE;
}
if (sscanf(argv[3], " %lu %c", &rrmax, &dummy) != 1 || rrmax < rrmin) {
fprintf(stderr, "%s: Invalid rrmax.\n", argv[3]);
return EXIT_FAILURE;
}
/* Calculate coordinate range. */
{ int xmin = XC(0,0,0);
int ymin = YC(0,0,0);
int xmax = XC(0,0,0);
int ymax = YC(0,0,0);
for (z = 0; z <= size; z++)
for (y = 0; y <= size; y++)
for (x = 0; x <= size; x++) {
const int xc = XC(x,y,z);
const int yc = YC(x,y,z);
if (xc < xmin) xmin = xc;
if (xc > xmax) xmax = xc;
if (yc < ymin) ymin = yc;
if (yc > ymax) ymax = yc;
}
xt = BORDER - xmin;
width = xmax - xmin + 2*BORDER;
yt = BORDER - ymin;
height = ymax - ymin + 2*BORDER;
}
center = size - 1;
/* SVG preamble. */
printf("<?xml version=\"1.0\"?>\n");
printf("<svg xmlns=\"http://www.w3.org/2000/svg\" viewBox=\"0 0 %d %d\">\n", width, height);
printf("<path d=\"M%d,%dL%d,%d,%d,%d,%d,%d,%d,%d,%d,%dz\" fill=\"#f7f7f7\" stroke=\"#666666\"/>\n",
xt+XC( 0, 0, 0), yt+YC( 0, 0, 0),
xt+XC(size, 0, 0), yt+YC(size, 0, 0),
xt+XC(size,size, 0), yt+YC(size,size, 0),
xt+XC(size,size,size), yt+YC(size,size,size),
xt+XC(0, size,size), yt+YC( 0,size,size),
xt+XC(0, 0,size), yt+YC( 0, 0,size));
printf("<path d=\"M%d,%dL%d,%d,%d,%dM%d,%dL%d,%d\" fill=\"none\" stroke=\"#666666\"/>\n",
xt+XC( 0, 0, 0), yt+YC( 0, 0, 0),
xt+XC( 0,size, 0), yt+YC( 0,size, 0),
xt+XC(size,size, 0), yt+YC(size,size, 0),
xt+XC( 0,size, 0), yt+YC( 0,size, 0),
xt+XC( 0,size,size), yt+YC( 0,size,size));
for (z = 0; z < size; z++)
for (y = size - 1; y >= 0; y--)
for (x = 0; x < size; x++)
if (surface(x,y,z))
fcube(stdout, x, y, z, 0x00CCFF);
printf("</svg>\n");
for (z=0; z < size; z++) {
for (y = 0; y < size; y++) {
for (x = 0; x < size; x++)
fputc(surface(x,y,z) ? 'X' : '.', stderr);
fputs(" ", stderr);
for (x = 0; x < size; x++)
fputc(surface(x,z,y) ? 'X' : '.', stderr);
fputs(" ", stderr);
for (x = 0; x < size; x++)
fputc(surface(y,z,x) ? 'X' : '.', stderr);
fputc('\n', stderr);
}
fputc('\n', stderr);
}
return EXIT_SUCCESS;
}
我没有费心调整输出；您可以很容易地为每个面选择不同的颜色，也可以在背景平面上添加阴影等等。
上述图像是使用此程序创建的，然后使用GIMP转换为PNG格式，但我建议使用浏览器本地查看生成的文件。
有问题吗？
- Nominal Animal
-2
在这个领域中最常用的库是openGL，本幻灯片向您展示如何在IDE上配置库并从此处下载文件http://www.xmission.com/~nate/glut.html，然后将它们放入以下路径：glut32.dll -> C:\Windows\System32 glut32.lib -> C:\Program Files\Microsoft Visual Studio .NET\Vc7\PlatformSDK\lib glut.h -> C:\Program Files\Microsoft Visual Studio .NET\Vc7\PlatformSDK\Include\gl
《OpenGL超级宝典第四版》是一本了不起的教材，从基础到高级水平都有涉及。
- user3895374
1
3我无法使用任何OpenGL库。 - David Heffernan
-3
我不能使用任何OpenGL库，我需要纯C/C++解决方案。
这是否意味着完全没有图形库？在这种情况下，非常简单的答案是：你不行。C和C++都没有本地的图形渲染能力。你需要使用外部库和驱动程序才能接触操作系统的帧缓冲区和/或图形卡。
然而，对于我的非图形相关解决方案，这取决于：
我发现了Bresenham的圆算法，但它是用于2D绘图的。我只需要球体边界。
这是否意味着你只需要球体的边界？因为在这种情况下，你应该使用你已经拥有的2D绘图算法，因为它可以立即给出边界。
如果这意味着你想要球体的单个体素，那就有点复杂了，需要更多的数学知识，可能会导致软件渲染器在性能上受到打击，具体取决于球体有多少个体素和单个顶点。
我认为你想要的是游戏和物理引擎开发人员所称的“边界框”或“碰撞框”，有时也简称为“命中框”。所有需要做的就是绘制一个立方体（通常是线框），将整个球体包围起来，仅此而已（换句话说，假设我们正在使用X-Y-Z维度，只需绘制与球体相同宽度、高度和深度的立方体）。
这是否意味着完全没有图形库？在这种情况下，非常简单的答案是：你不行。C和C++都没有本地的图形渲染能力。你需要使用外部库和驱动程序才能接触操作系统的帧缓冲区和/或图形卡。
然而，对于我的非图形相关解决方案，这取决于：
我发现了Bresenham的圆算法，但它是用于2D绘图的。我只需要球体边界。
这是否意味着你只需要球体的边界？因为在这种情况下，你应该使用你已经拥有的2D绘图算法，因为它可以立即给出边界。
如果这意味着你想要球体的单个体素，那就有点复杂了，需要更多的数学知识，可能会导致软件渲染器在性能上受到打击，具体取决于球体有多少个体素和单个顶点。
我认为你想要的是游戏和物理引擎开发人员所称的“边界框”或“碰撞框”，有时也简称为“命中框”。所有需要做的就是绘制一个立方体（通常是线框），将整个球体包围起来，仅此而已（换句话说，假设我们正在使用X-Y-Z维度，只需绘制与球体相同宽度、高度和深度的立方体）。
- Mason Watmough
1
我不明白通过挑剔某人未能完美地表达自己的想法来激怒他们，如何能实现任何有益的成果。 - Jack G
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接