快速球体与网格相交
给定一个 3D 网格、一个作为球体中心的 3d 点和一个半径，我想快速计算球体包含或相交的所有单元格。
目前，我采用球体的（网格对齐）边界框并计算该边界框的最小和最大点的两个单元格。然后，对于这两个单元格之间的每个单元格，我进行盒球相交测试。
如果有更有效的东西那就太好了
谢谢！
given a 3D grid, a 3d point as sphere center and a radius, i'd like to quickly calculate all cells contained or intersected by the sphere.
Currently i take the the (gridaligned) boundingbox of the sphere and calculate the two cells for the min anx max point of this boundingbox. then, for each cell between those two cells, i do a box-sphere intersection test.
would be great if there was something more efficient
thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
有一个用于绘制圆圈的 Bresenham 算法的版本。考虑 z=0 处的二维位置（假设球体现在位于 0,0,0），并仅查看网格点的 xy 平面。从 x= R, y=0 开始，遵循 Bresenham 算法直到 y = y_R, x=0，除了不绘图之外，您只需使用结果即可知道所有具有较低 x 坐标的网格点都在圆内，向下到 x=x_center。将它们放入列表中，计算它们或以其他方式记下。完成二维问题后，重复改变 z 并使用减小的半径 R(z) = sqrt(R^2-z^2) 代替 R，直到 z=R。
如果球体中心确实位于某个网格点上，您就知道球体右半部分内部或外部的每个网格点在左侧以及顶部/底部都有一个镜像伙伴，因此您可以进行一半的计数/每个维度的列表。您还可以仅将 Bresenham 运行到 45 度线，从而节省时间，因为相对于中心的任何 x,y 点都有一个伙伴 y,x。如果球体可以在任何地方，您将必须计算每个八分圆的结果。
There's a version of the Bresenham algorithm for drawing circles. Consider the two dimensional place at z=0 (assume the sphere is at 0,0,0 for now), and look at only the x-y plane of grid points. Starting at x= R, y=0, follow the Bresenham algorithm up to y = y_R, x=0, except instead of drawing, you just use the result to know that all grid points with lower x coordinates are inside the circle, down to x=x_center. Put those in a list, count them or otherwise make note of. When done with two dimensional problem, repeat with varying z and using a reduced radius R(z) = sqrt(R^2-z^2) in place of R, until z=R.
If the sphere center is indeed located on a grid point, you know that every grid point inside or outside the right half of the sphere has a mirror partner on the left side, and likewise top/bottom, so you can do half the counting/listing per dimension. You can also save time running Bresenham only to the 45 degree line, because any x,y point relative to the center has a partner y,x. If the sphere can be anywhere, you will have to compute results for each octant.
无论您计算球体内部或外部的单个单元的效率如何，您的算法将始终是 O(radius^3)，因为您必须标记那么多单元。 DarenW 对中点（又名 Bresenham）圆算法的建议可以提供恒定因子加速，就像可以使用平方半径简单地测试相交以避免 sqrt() 调用一样。
如果您想要比 O(r^3) 更好的性能，那么您可以使用 八叉树 而不是平面网格。树的每个节点都可以标记为完全在球体内部、完全在球体外部或部分在球体内部。对于部分内部节点，您可以沿树递归，直到到达最细粒度的单元格。这仍然需要标记 O(r^2 log r) 个节点 [边界上的 O(r^2) 个节点，O(log r) 遍历树到达每个节点]，因此可能不值得您的应用程序出现问题。
No matter how efficiently you calculate an individual cell being inside or outside the sphere, your algorithm will always be O(radius^3) because you have to mark that many cells. DarenW's suggestion of the midpoint (aka Bresenham) circle algorithm could give a constant factor speedup, as could simply testing for intersection using the squared radius to avoid the sqrt() call.
If you want better than O(r^3) performance, then you may be able to use an octree instead of a flat grid. Each node of the tree could be marked as being entirely inside, entirely outside, or partially inside the sphere. For partially inside nodes, you recurse down the tree until you get to the finest-grained cells. This will still require marking O(r^2 log r) nodes [O(r^2) nodes on the boundary, O(log r) steps through the tree to get to each of them], so it might not be worth the trouble in your application.