在C / C ++中绘制3D球体
我正在寻找一种算法,可以在小分辨率上绘制漂亮的3D球体。 我发现了Bresenham的圆形算法,但是它用于2D绘图。 我只需要球体边框(我不需要它填充)。 我也谷歌搜索问题的解决方案,但我没有找到任何东西。 这篇文章没有帮助(什么是暴力算法?)。 我不能使用任何OpenGL库,我需要vanilla C / C ++解决方案。 先感谢您。
如果我做对了你想要渲染球体的所有表面体素
蛮力是O(R^3)
。 如果你只是从平面投射光线并计算第3个坐标,那么你得到O(R^2)
但是为了确保没有体素丢失,你必须从所有3个平面进行投影,这仍然是O(R^2)
它看起来像这样:
在LED立方体16x16x16
模拟。 现在算法:
-
计算可见边界框
不需要渲染整个渲染空间只是球体所以中心+/-半径…
-
拿一个平面(例如XY)
从射线框内的所有
x,y
点投射光线x,y
这只是2个循环,并通过球面方程计算射线击中的z
坐标:(x-x0)^2 + (y-y0)^2 + (z-z0)^2 = R^2
所以
z=z0 +/- sqrt(R^2 - (x-x0)^2 - (y-y0)^2)
并渲染两个体素 。 有限大小的
int sqrt(int x)
(如LED Cube / Screen或Voxel空间)可以通过LUT查找表来完成,以加快速度。 -
为所有飞机执行步骤#2(
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;xn) 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;x0)&&(z0)&&(z0)&&(y0)&&(y0)&&(x0)&&(x
课程用法:
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,...
根据链接,看起来你对球体的体素算法更感兴趣,而不是图形本身; 说这样的页面有助于。 你不需要球,但只需要表面。
中点圆算法可用于绘制3D体素球:将球体视为切片堆叠,并且每个切片包含圆形。
在实践中,您使用两个嵌套的中点圆,外部定义内部圆的半径。 (虽然一个天真的算法绘制在彼此之上的圆圈可能会在体素中留下空洞,但是中点圆算法利用对称性,如果正确实现,则不会出现这样的洞。)
你可以串联制造六个帽子,比如将一个立方体雕刻成一个球体。 由于每个盖子上的表面斜率总是小于1,因此在盖子上向外移动最多会将每个坐标改变1,因此不会出现孔洞。
这种方法的问题在于复杂性:您计算的每个点可能会影响多达48个体素单元格。 (在每个上限,每个点在八分圆内计算,因此影响八个单元格。有六个上限,6 * 8 = 48。)
我建议采用不同的方法。
以x 0 , y 0 , z 0为中心的r-半球的表面方程为
( x – x 0 ) 2 +( y – y 0 ) 2 +( z – z 0 ) 2 = r 2
使用整数协调器,网格点很少精确地位于球体表面上,允许一系列值:
RRMIN≤ ( x – x 0 ) 2 +( y -y 0 ) 2 +( z – z 0 ) 2≤RRMAX
其中RR MIN和RR MAX是常数; 具体而言,最小和最大距离平方到球心。
对于一般情况,我建议使用加倍坐标。 这允许您选择球体的中心是以坐标为中心(意味着奇数直径),还是在两个相邻坐标之间居中(意味着直径均匀)。
如果你有一个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
来做到这一点:
如果你有一个4×4×4网格,你希望每个面上的四个中心单元满足条件(因此64个单元中总共有24个被认为是在球体表面上); 你可以用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
包括所有内部单元格,产生一个球而不仅仅是一个球体的表面。
随着网格尺寸的增加,您可以表示的每个尺寸球体的变体越多。
上述function在微控制器上特别有用,因为您可以简单地遍历晶格,根据需要更新每个点的状态。 此外,大多数微控制器的存储器都很紧凑,但具有非常快速(单时钟)的加法,减法和乘法指令。 (尽管带有32位结果的16×16位乘法通常需要两条或更多条指令。)
典型的微控制器没有ROM /闪存function来存储足够有趣的体素模式,只有少数具有通过SPI从SD卡获得DMAfunction(因此您只需从microSD卡加载体素模式的“帧”),但是像上面这样的函数可以用很少的输入产生有趣的形状 - 特别是你可以插入的输入。
如果您的体素不仅仅是二进制,而是例如PWM控制的LED,则上述函数也可以适用于近似的抗锯齿(通过比较rr
与rrmin
和rrmax
)。
由于可视化上述内容通常有点困难,这里是我用来生成上述图像的快速小黑客。 当给定size
, rrmin
和rrmax
作为命令行参数时, rrmin
SVG图像输出到标准输出,并将ASCII切片输出到标准误差。
#include #include #include #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, " \n", xc, yc, fill & 0xFFFFFF); fprintf(out, " \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("\n"); printf("\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,但我建议使用浏览器在本地查看生成的文件。
有问题吗?
这个领域中最常用的库是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 \包含\ GL
opengl-superbible-4th这本教科书令人惊叹,从头开始到高级
我不能使用任何OpenGL库,我需要vanilla C / C ++解决方案。
这是否意味着没有图形库? 在这种情况下,非常简单的答案是:你没有。 C和C ++都没有本机图形渲染能力。 您需要使用外部库和驱动程序才能与操作系统的帧缓冲区和/或图形卡取得联系。
但是,对于我的非图形相关解决方案,它取决于:
我发现了Bresenham的圆形算法,但是它用于2D绘图。 我只需要球体边界。
这是否意味着你只需要球体的边界? 因为在这种情况下,你应该只使用你已经拥有的2d绘图算法,因为它会为你提供当时和那里的边界。
如果它意味着你想要球体的各个体素,那就更复杂了,需要更多的数学运算,并且可能达到软件渲染器在性能方面要打得面对的程度,取决于您的球体有多少体素和单个顶点。
我认为你想要得到的是游戏和物理引擎开发人员称之为“边界框”或“碰撞框”,有时简称为“hitbox”。 所需要的只是绘制一个包围整个球体的立方体(通常是线框)而不是更多(换句话说,你只是绘制一个与球体具有相同宽度,高度和深度的立方体,假设我们正在使用XYZ维度)。