多边界框包含检测算法

Question

有谁知道具有以下描述的多边界框包含检测算法（或实现参考）：

让我们收集轴对齐边界框，其中一些可能相交
和一个简单的 3D 形状，例如球体（或者它可以是另一个 AABB）。
我需要可以检测形状是否完全包含在 AABB-s 中的算法。换句话说，球体的任何部分都不在 AABB-s 之外。

问题是：在单个 AABB 中测试包容性很容易，但是存在形状可能在多个 AABB-s 之间分裂的情况，甚至可能与多个 AABB-s 相交的情况但球体的某些部分在外面。

Answer 1

从代数上讲，这个问题可以表示为实数上的约束满足问题。点(x,y,z)在圆心坐标(cx,cy,cz)、半径r的圆内的条件是：

C :=  (x-cx)^2 + (y-cy)^2 + (z-cz)^2 - r^2 <= 0

点在 AABB 内的条件是：

B :=  x0 <= x /\ x <= x1 /\ y0 <= x /\ y <= y1 /\ z0 <= z /\ z <= z1

其中 /\ 表示 'and' 和 x0, x1, ..., z1 是实数。

现在给定一个圆和几个边界框问题是约束列表是否

C /\ !(B1 \/ ... \/ Bn)

可以满意。如果是，则球体内部有一个点，但不在任何 AABB 内部。由于只有三个变量x,y,z，并且现有最多2次的多项式algorithms/libraries可以有效地解决这个问题。（例如 Z3, see this intro）。

Answer 2

IMO，你可以通过扫描平面方法来做到这一点。

按顶部和底部 "applicates"（z 坐标）对所有 AABB 进行排序。现在考虑一个从一个面到另一个面向下移动的水平面，每次更新一个活动列表（即那些与平面相交的框）。一个盒子在其顶面进入列表并在其底面离开。

平面的场景部分将由一组矩形和可能的圆形组成。在每一步中，圆都需要完全包含在矩形的并集中。

请注意，您还需要停在赤道平面（不会修改活动列表），因为球体是那里的"largest"。

这样做，您将初始问题转化为一组具有矩形和圆形的 2D 包含子问题。

遵循相同的原则，您可以通过扫描线技术解决后者，按矩形的 top/bottom 边的纵坐标排序并移动活动列表。在每一步中，等 y 线的截面定义了一组线段，每个矩形一个，可能一个圆，并且可以通过对 x 上的边界进行排序来轻松证明包含。

换句话说，通过 3D 扫描过程，您可以分解 space 棱柱板并构建与球体的交点。通过 2D 扫描过程，您将平面分解为矩形板，并与截面圆盘建立交点。

Answer 3

受 Yves 的递归扫描平面算法思想的启发，这里有一个更精细的版本，用于尝试在球体内找到未被任何给定框覆盖的点。

首先，我们必须找到所有的 z 坐标值，当沿 z 轴移动时，相应平面中的完全覆盖可能会发生变化。这可能发生在

球体的最大和最小 z 坐标（即 z_center +/- 半径）
所有框的最大和最小 z 坐标
球体与所有长方体面的所有交点 circles/arcs 的最大和最小 z 坐标

一旦这些 z 值被收集、排序并限制在球体的 z 范围内，我们就将球体的 z 范围划分为多个区间。我们在每个 z 间隔（例如中心）中选择一个 inside 的值来检查相应平面中的覆盖范围。每个 2D 切口都可以类似于 3D 问题来解决 - 从而将覆盖检查减少到一组 1D 问题。在一维情况下，我们有一个区间而不是球体或圆，我们也有区间而不是方框或矩形。因此球体对盒子的覆盖问题被简化为一个区间对一组区间的一组平凡的覆盖问题。

主要功能的实现可能如下所示：

# if the n-dimensional sphere is not fully covered by the boxes
# find a point inside the sphere but outside the boxes
# by a recursive sweep-plane algorithm.
# center: n-dimensional point
# radius: real value
# boxes: list of n-dimensional boxes (each box is a list of n intervals)
def getUncoveredSphereWitness(center, radius, boxes):
    sphereLimitsN = [center[-1]-radius, center[-1]+radius]
    if len(center) == 1: 
        # 1D case
        witness = getUncoveredIntervalWitness(sphereLimitsN, [box[0] for box in boxes])
        return [witness] if witness is not None else None

    boxLimitsN = sum([b[-1] for b in boxes], [])
    cutLimitsN = getCutLimitsN_boxes(center, radius, boxes)
    limitsN = list(set(sphereLimitsN + boxLimitsN + cutLimitsN))
    limitsN.sort()

    # get centers of relevant intervals
    coordNValsToCheck = []
    for b in limitsN:
        if b > sphereLimitsN[1]: break
        if b > sphereLimitsN[0]:
            coordNValsToCheck.append((bPrev+b)/2.)
        bPrev = b

    for z in coordNValsToCheck:
        # reduce to a problem of with 1 dimension less
        centerN1, radiusN1 = cutSphereN(center, radius, z)
        boxesN1 = cutBoxesN(boxes, z)
        witness = getUncoveredSphereWitness(centerN1, radiusN1, boxesN1)
        if witness is not None:
            return witness+[z] # lift witness to full dimension by appending coordinate

    return None

多边界框包含检测算法

Multiple Bounding Boxes containment detection algorithm

algorithm

geometry

collision-detection

computational-geometry

containment