多边界框包含检测算法

Question

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

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

问题是：在单个AABB中容易测试包容，但是有一种情况是形状可以在多个AABB-s之间分割，甚至可以在多个AABB-s但是与球体的某些部分相交的情况下在外面。

Answer 1

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

按其顶部和底部“应用”（z坐标）对所有AABB进行排序。现在考虑一个水平平面，每次更新活动列表（即那些与平面相遇的方框）时，从一个面向下移动。一个方框进入其顶面的列表，并将其留在底面。

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

请注意，您还需要通过赤道（不会修改活动列表）停在飞机上，因为球体是那里的“最大”。

这样做，您将初始问题发送到一组带有矩形和圆形的2D包含子问题。

遵循相同的原则，您可以通过扫描线技术解决后者，通过其顶部/底部的纵坐标对矩形进行排序并移动活动列表。在每一步中，由iso-y线组成的部分定义了一组段，每个矩形一个，可能还有一个用于圆，并且通过对x上的边界进行排序可以很容易地证明包含。

换句话说，通过3D扫描过程，您可以分解棱柱板中的空间并与球体建立交叉点。通过2D扫描过程，您可以在矩形板中分解平面，并使用截面磁盘构建交叉点。

Answer 2

代数地，这个问题可以表达为对实际的约束满足问题。点(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

其中/\的意思是'和'，x0, x1, ..., z1是实数。

现在给出一个圆圈和几个边界框，问题是是否有约束列表

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

可以满足。如果是，则球体内部有一个点，但不在任何AABB内部。由于只有三个变量x,y,z和最多2个现有算法/库的多项式可以有效地解决这个问题。 （例如Z3，见此intro）。

Answer 3

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

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

• 球体的最大和最小z坐标（即z_center +/- radius）
• 所有方框的最大和最小z坐标
• 具有所有框面的球体的所有交叉圆/弧的最大和最小z坐标

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

main函数的实现可能如下所示：

# 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