多包围盒包容检测算法

在我看来,你可以用扫描平面的方法。

按顶部和底部“应用程序”(Z坐标)对所有AABB进行排序。现在考虑一个水平面,它从一个面向下移动,每次更新一个活动列表(即那些与该平面相交的框)。一个框在其顶面进入列表,在其底面离开列表。

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

请注意,您还需要在赤道附近的平面处停下来(赤道不会修改活动列表),因为那里的球体是“最大的”。

这样做,您将初始问题发展为一组具有矩形和圆形的二维包含子问题。

遵循同样的原则,您可以通过扫描线技术来处理后者,根据矩形的顶部/底部的坐标对矩形进行排序,并移动活动列表。在每一步中,由iso-y线组成的部分定义一组线段,每个矩形一个线段,圆也可能有一个线段,通过对x上的边界进行排序,很容易证明包含性。

换句话说,通过三维扫描过程,可以分解棱柱体板中的空间并构建与球体的交点。通过二维扫描过程,将平面分解为矩形板,并与截面圆盘建立交点。

在代数上,这个问题可以表示为实域上的一个约束满足问题。一个点的条件 (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 )

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

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

• 球体的最大和最小Z坐标(即Z_中心+/-半径)
• 所有盒子的最大和最小z坐标
• 球面与所有长方体面的所有相交圆/弧的最大和最小z坐标

一旦这些z值被收集、排序并限制在球体的z范围内,我们就可以将球体的z范围划分为区间。我们选择一个值 里面 每个z间隔(例如中心)检查对应平面的覆盖范围。每个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