使用 3D 像素(体素)绘制球体 [英] Draw a sphere using 3D pixels (voxels)

问题描述

您能否提出一种算法，该算法可以仅使用基本的 plot(x,y,z) 基元(将绘制单个体素)在 3D 空间中绘制球体?

我希望有类似于 .

我想到的一种可能性是:

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

FWIW，我使用的是 .NET 微框架微处理器，所以编程是 C#，但我不需要答案就可以使用 C#.

解决方案

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

远非最佳，当然.但是在如图所示的 8x8x8 网格上，您需要对每个球体执行 512 次此操作.如果球心在网格上，并且它的半径是一个整数，你只需要整数数学.点积是 3 个乘法和 2 个加法.乘法很慢；假设他们每人接受 4 条指令.另外，您需要进行比较.加上负载和存储，假设每个体素花费 20 条指令.这是每个球体 10240 条指令.

以 16 MHz 运行的 Arduino 每秒可以推动 1562 个球体.除非你在做大量其他数学和 I/O，否则这个算法应该足够好了.

Can you suggest an algorithm that can draw a sphere in 3D space using only the basic plot(x,y,z) primitive (which would draw a single voxel)?

I was hoping for something similar to Bresenham's circle algorithm, but for 3D instead of 2D.

FYI, I'm working on a hardware project that is a low-res 3D display using a 3-dimensional matrix of LEDs, so I need to actually draw a sphere, not just a 2D projection (i.e. circle).

The project is very similar to this:

... or see it in action here.

One possibility I have in mind is this:

• calculate the Y coordinates of the poles (given the radius) (for a sphere centered in the origin, these would be -r and +r)
• slice the sphere: for each horizontal plane p_i between these coordinates, calculate the radius of the circle obtained by intersecting said plane with the sphere => r_i.
• draw the actual circle of radius r_i on plane p_i using Bresenham's algorithm.

FWIW, I'm using a .NET micro-framework microprocessor, so programming is C#, but I don't need answers to be in C#.

解决方案

The simple, brute force method is to loop over every voxel in the grid and calculate its distance from the sphere center. Then color the voxel if its distance is less than the sphere radius. You can save a lot of instructions by eliminating the square root and comparing the dot product to the radius squared.

Pretty far from optimal, sure. But on an 8x8x8 grid as shown, you'll need to do this operation 512 times per sphere. If the sphere center is on the grid, and its radius is an integer, you only need integer math. The dot product is 3 multiplies and 2 adds. Multiplies are slow; let's say they take 4 instructions each. Plus you need a comparison. Add in the loads and stores, let's say it costs 20 instructions per voxel. That's 10240 instructions per sphere.

An Arduino running at 16 MHz could push 1562 spheres per second. Unless you're doing tons of other math and I/O, this algorithm should be good enough.

这篇关于使用 3D 像素(体素)绘制球体的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！