我正在尝试创建一个球体，其外部有“方块”，就像在Minecraft中建造一样。 （我不知道圆形外部的术语是什么）。问题是，我无法弄清楚如何让类似于Midpoint Circle Algorithm的方程适用于球体。最好使用lua或java，以便我可以更轻松地阅读任何答案。我不想知道如何使用三角函数计算球面上的点，因为我已经知道如何做到这一点。
4个回答
4
我认为最简单的方法是使用Midpoint Circle算法，将其扩展到3D。
首先，让我们确定要填充哪些块。假设坐标系原点在方块(0,0,0)的中心，半径为R：
因此，很容易计算出满足以下条件的方块：1）在球内，2）具有z作为它们的最大坐标，3）具有最大可能的z值，即将z加1会导致一个方块在球外。此外，4）所有x、y、z的值都是正数。
然后可以以24种不同的方式反射这些方块的坐标，以生成球表面上的所有方块。这些是所有坐标的符号乘以所有三个轴中具有最大坐标的选择的8个组合。
以下是如何生成具有正x、y、z和最大z的点：
首先，让我们确定要填充哪些块。假设坐标系原点在方块(0,0,0)的中心，半径为R：
- 我们只想填充球内的方块。这些方块的坐标(x,y,z)满足x²+y²+z²<=R²；且
- 我们只想填充有面朝向外的方块。如果一个方块有面朝向外，则至少有一个相邻方块不在球内，因此：(|x|+1)²+y²+z²>R²或x²+(|y|+1)²+z²>R²或x²+y²+(|z|+1)²>R²
因此，很容易计算出满足以下条件的方块：1）在球内，2）具有z作为它们的最大坐标，3）具有最大可能的z值，即将z加1会导致一个方块在球外。此外，4）所有x、y、z的值都是正数。
然后可以以24种不同的方式反射这些方块的坐标，以生成球表面上的所有方块。这些是所有坐标的符号乘以所有三个轴中具有最大坐标的选择的8个组合。
以下是如何生成具有正x、y、z和最大z的点：
maxR2 = floor(R*R);
zx = floor(R);
for (x=0; ;++x)
{
//max z for this x value.
while(x*x+zx*zx > maxR2 && zx>=x)
--zx;
if (zx<x)
break; //with this x, z can't be largest
z=zx;
for(y=0; ;++y)
{
while(x*x+y*y+z*z > maxR2 && z>=x && z>=y)
--z;
if (z<x||z<y)
break; //with this x and y, z can't be largest
FILLBOX(x,y,z); //... and up to 23 reflections of it
}
}
注意：如果你关注的话，在计算反射时要小心，不要画两次同一个盒子，例如(0,y,z)和(-0,y,z)。同时，不要交换具有相同值的轴，因为这会再次绘制相同的盒子（例如，如果你有(1,5,5)，不要交换y和z并重新绘制）。
此外，请注意R不必是整数。如果添加0.5，效果会更好。
以下是一个考虑了以上所有因素的示例（需要支持webgl的浏览器）：https://jsfiddle.net/mtimmerm/ay2adpwb/
- Matt Timmermans
5
@Bedrockbreaker，请查看链接的jsfiddle中的反射代码--它非常酷。 - Matt Timmermans
嗨！你能帮我理解第5和6行吗？
“while(xx+zxzx > maxR2 && zx>=x)
--zx;”
我不太明白while条件中的数学表达式是如何从你在解释中描述的数学推导出来的。 - retrovius
1当我们开始迭代外部循环时，可以保证zx >= 正确值，因此在第5和第6行，我们只需要担心将其减少正确的量。 第一个条件，x * x + zx * zx > maxR2 意味着点（x，0，zx）在球体外部。 第二个条件会提前终止循环，如果第7和第8行的测试将停止整个算法。 - Matt Timmermans
谢谢！那帮了很大的忙！ - retrovius
1
你可以在嵌套循环中使用Midpoint Circle Algorithm或Bresenham's Circle Algorithm。外部循环确定圆的整数半径，该圆位于与原点距离不同的
z距离处；而内部循环计算组成球体截面（垂直于Z轴在位置z处）的圆的x和y元素。请保留HTML标签。- andand
2
这会在|z|的大值处留下间隙，在x-y平面中的半径可跳跃超过1。 - Matt Timmermans
Bresenham算法的链接已失效。这里提供了简洁的代码框架：http://members.chello.at/~easyfilter/bresenham.html。 - collapsar
0
这是用我自己的 MiniBasic 版本编写的。
10 REM Shaded textured sphere
20 INPUT width
30 INPUT height
40 INPUT bwidth
50 INPUT bheight
60 REM Sphere radius
70 LET r = 100
80 REM light direction
90 LET lx = 0
100 LET ly = 0.2
110 LET lz = -1
120 LET ambient = 0.1
130 REM camera z position
140 LET cz = -256
150 REM Sphere colour
160 LET red = 255
170 LET green =0
180 LET blue = 100
190 REM Normalize light
200 LET len = SQRT(lx*lx+ly*ly+lz*lz)
210 LET lx = -lx/len
220 LET ly = -ly/len
230 LET lz = -lz/len
240 FOR i = 0 TO height -1
250 FOR ii = 0 TO width -1
260 LET x = ii - width /2
270 LET y = i - height/2
280 LET dpx = x
290 LET dpy = y
300 LET dpz = -cz
310 LET a = dpx*dpx + dpy*dpy + dpz*dpz
320 LET b = 2 * ( dpz * cz)
330 LET c = cz * cz
340 LET c = c - r * r
350 LET bb4ac = b * b - 4 * a * c
360 IF ABS(a) < 0.001 OR bb4ac < 0 THEN 560
370 LET mu1 = (-b + SQRT(bb4ac)) / (2 * a)
380 LET mu2 = (-b - SQRT(bb4ac)) / (2 * a)
390 LET spx = mu1 * x 400 LET spy = mu1 * y
410 LET spz = mu1 * 256 - 256
420 LET nx = spx / r
430 LET ny = spy / r
440 LET nz = spz / r
450 LET costh = nx*lx + ny *ly + nz*lz
460 IF costh > 0 THEN 480
470 LET costh = 0
480 LET lum = ambient + (1 - ambient) * costh
490 LET v = ACOS(nz)/PI 495 LET nx = nx * 0.999
510 LET u = ACOS(nx * SIN(PI * v)) / PI
535 LET v = -ACOS(ny)/PI + 1.0
536 LET u = 1 - u
540 GETPIXELB u * bwidth, v * bheight, red, green, blue
550 SETPIXEL ii, i, red * lum, green *lum, blue *lum
560 NEXT ii
570 NEXT i
http://www.malcolmmclean.site11.com/www/UserPrograms.html#texsphere
- Malcolm McLean
0
这里是使用Matt Timmermans的示例的Python示例。如果使用numba jits函数和并行prange，这非常快速，如果您有多个球体。 svoxel是为任何起始坐标添加的。网格只是在一个3D网格中将1放置在球体像素处。还增加了一个可选的填充内部步骤。注意：这只对非负坐标起作用，所以球体需要在所有使用svoxels坐标的像素中占据正空间。
#/usr/bin/env python
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits import mplot3d
from numba.experimental import jitclass
from numba import types, njit, prange
spec = [
('radius', types.float64),
('svoxel', types.int64[:]),
('grid', types.b1[:,:,:])
]
@jitclass(spec)
class RasterizeSphere(object):
def __init__(self, svoxel, radius, grid):
self.grid = grid
self.svoxel = svoxel
self.radius = radius
R2 = np.floor(self.radius**2)
zx = np.int64(np.floor(self.radius))
x = 0
while True:
while x**2 + zx**2 > R2 and zx >= x:
zx -= 1
if zx < x:
break
z = zx
y = 0
while True:
while x**2 + y**2 + z**2 > R2 and z >= x and z >= y:
z -= 1
if z < x or z < y:
break
self.fill_all(x, y, z)
###### Optional fills the inside of sphere as well. #######
for nz in range(z):
self.fill_all(x, y, nz)
y += 1
x += 1
def fill_signs(self, x, y, z):
self.grid[x + self.svoxel[0], y + self.svoxel[1], z + self.svoxel[2]] = True
while True:
z = -z
if z >= 0:
y = -y
if y >= 0:
x = -x
if x >= 0:
break
self.grid[x + self.svoxel[0], y + self.svoxel[1], z + self.svoxel[2]] = True
def fill_all(self, x, y, z):
self.fill_signs(x, y, z)
if z > y:
self.fill_signs(x, z, y)
if z > x and z > y:
self.fill_signs(z, y, x)
@njit(parallel=True, cache=True)
def parallel_spheres(grid):
# prange just to show the insane speedup for large number of spheres disable visualization below if using large amount of prange.
for i in prange(2):
radius = 4.5
svoxel = np.array([5, 5, 5])
max = np.int64(np.ceil(radius**2))
rs = RasterizeSphere(svoxel, radius, grid)
points = np.where(rs.grid)
return np.array([*points])
def main():
# Make max large enough to hold the spheres.
max = 100
points = parallel_spheres(np.zeros((max, max, max), dtype=bool))
fig = plt.figure()
ax = plt.axes(projection='3d')
ax.scatter3D(*points)
plt.show()
if __name__ == '__main__':
main()
- Mitchell Walls
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
if语句和简单的迭代时，你得到了PI/4 = ~0.78的效率，这意味着只有约22%的迭代会浪费，这比Midpoint甚至Bresenham都要好。 - Spektre