当前位置：文江博客话题详情

盒子与球体碰撞

发布于 2024-10-19 04:37:51 字数 109 浏览 1 评论 0原文

我需要检查一个盒子是否与球体碰撞。我有一个用 x、y、z、宽度、高度、深度定义的 BoundingBox 类。我还有一个用 x、y、z、半径定义的 BoundingSphere 类。如何检查它们是否相交？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

何其悲哀 2024-10-26 04:37:51

首先要检查的是 BoundingSphere 的 BoundingBox 是否相交。这样做的原因是，这是一种非常简单的方法来排除所涉及的更复杂的数学。

下一步是获取边界框的六个平面（或十二个三角形）中的每一个，并对它们进行从点到多边形到球体中心的距离测试。如果其中之一小于球体的半径，那么您就成功了。

多边形到点距离的 Matlab 代码： http://www.mathworks.com/matlabcentral/fileexchange/12744-distance-from-a-point-to-polygon

回复收藏 0 原文

分开我的手 2024-10-26 04:37:51

有一种简单且廉价的方法来构造盒子上最接近球体中心的点的坐标（我将在下面讨论如何做到这一点）。如果到最近点的距离大于半径，则盒子和球相交。否则它们不相交。

设

r = 球体半径
c = (x_sphere, y_sphere, z_sphere) = 球体中心
b_min = (x_box, y_box, z_box) = 框“最小”点
b_max = (x_box + 宽度, y_box + 高度, z_box + 深度) =框“最大”点。
p = 盒子上距离球体中心最近的点（我们想要找到 p）

盒子上距离球体中心最近的点可以按组件构建（伪代码）：

for i=1,2,3:

if              c[i] < b_min[i]   then   p[i] = b_min[i]
if   b_min[i] < c[i] < b_max[i]   then   p[i] = c[i]
if   b_max[i] < c[i]              then   p[i] = b_max[i]

if (p[1]-c[1])^2 + (p[2]-c[2])^2 + (p[3]-c[3])^2 < r^2 
then the box intersects the ball. 

Otherwise the box doesn't intersect the ball

在 python 中，可以写如下：

import numpy as np

# r is a float, and c, b_min, b_max are numpy vectors
def box_intersects_ball(r, c, b_min, b_max):
    p = c.copy()
    p[c < b_min] = b_min[c < b_min]
    p[c > b_max] = b_max[c > b_max]
    return (np.linalg.norm(p - c) <= r)

请注意，这实际上是有效的对于任何维度空间中的盒子/球体，2d、3d、4d、100d 等等。

要了解为什么这给出了最近的点，令 p 为由上面所示方法定义的点，并令 q 为框中的任何其他点。如果 q 在第 i 个坐标中与 p 不同，则用 p[i] 替换 q[i] 将使 q 更接近 p，因为 |q[i]-c[i]|当 |q[j]-c[j]| 时变小对于所有其他不等于 i 的坐标 j 保持相同。换句话说，p 必须是框中距离 c 最近的点，因为框中的任何其他点都可以通过修改它来使其更接近 c。

注 1：这里我假设盒子的 x、y、z 坐标位于所有维度的最下角。

注2：我假设盒子和球体是“实心”而不是“空心”。

There is a simple and cheap way to construct the coordinates of the point on the box that is closest to the center of the sphere (I discuss how to do this below). If the distance to the closest point is bigger than the radius, then the box and the ball intersect. Otherwise they do not intersect.

Let

r = radius of sphere
c = (x_sphere, y_sphere, z_sphere) = center of sphere
b_min = (x_box, y_box, z_box) = box "min" point
b_max = (x_box + width, y_box + height, z_box + depth) = box "max" point.
p = closest point on box to center of the sphere (we want to find p)

The closest point on the box to the sphere center can be constructed componentwise (pseudocode):

for i=1,2,3:

if              c[i] < b_min[i]   then   p[i] = b_min[i]
if   b_min[i] < c[i] < b_max[i]   then   p[i] = c[i]
if   b_max[i] < c[i]              then   p[i] = b_max[i]

if (p[1]-c[1])^2 + (p[2]-c[2])^2 + (p[3]-c[3])^2 < r^2 
then the box intersects the ball. 

Otherwise the box doesn't intersect the ball

In python this can be written as follows:

import numpy as np

# r is a float, and c, b_min, b_max are numpy vectors
def box_intersects_ball(r, c, b_min, b_max):
    p = c.copy()
    p[c < b_min] = b_min[c < b_min]
    p[c > b_max] = b_max[c > b_max]
    return (np.linalg.norm(p - c) <= r)

Note that this actually works for boxes/spheres in any dimensional space, 2d, 3d, 4d, 100d, whatever.

To see why this gives the closest point, let p be the point defined by the method shown above, and let q be any other point in the box. If q differs from p in the i'th coordinate, replacing q[i] with p[i] will make q get closer to p, because |q[i]-c[i]| gets smaller while |q[j]-c[j]| remains the same for all other coordinates j not equal i. In other words, p must be the closest point in the box to c, because any other point in the box can be made closer to c by modifying it.

Note 1: here I am assuming that the x,y,z coordinates you have for the box are in the lowermost corner in all dimensions.

Note 2: I am assuming that the box and sphere are "solid" not "hollow".

回复收藏 0 原文

小帐篷 2024-10-26 04:37:51

如果您想将测试保持在您所描述的水平，您可以在球体周围放置一个边界框，其中宽度、高度和深度 = 2r。当然，这承认球体上“非极”或“非赤道”点发生碰撞的误报风险。为了解决这个问题，您可以考虑构建一系列分层边界框，以增加这些问题区域中命中测试的粒度。

您还可以从渲染级别解决问题。由于无法渲染球体，因此通常使用某种多边形网格。 2D（或 3D）多边形之间的命中测试是一项简单的练习。

回复收藏 0 原文

沫雨熙 2024-10-26 04:37:51

Jim Arvo 的 Graphics Gems 中有一个章节。

我猜上面的过时链接曾经指向他的代码，因为 URL 中有“arvo”。这个链接有效 - 至少现在是这样。

回复收藏 0 原文

末蓝 2024-10-26 04:37:51

您只需根据距球体中心的距离检查边界框的所有角即可。这是一些伪代码：

bool collidesWith(BoundingBox b, BoundingSphere s) {
  for(Vertex v in b) {
    if(distanceBetween(v, s.center) <= s.radius)
      return true;
  }
  return false;
}

You just have to check all the corners of the bounding box against the distance from the center of the sphere. Here's some pseudocode:

bool collidesWith(BoundingBox b, BoundingSphere s) {
  for(Vertex v in b) {
    if(distanceBetween(v, s.center) <= s.radius)
      return true;
  }
  return false;
}

回复收藏 0 原文

~没有更多了~