28. 线段，矩形，Liang-Barsky

3.24，继续研究 bump.lua 的算法。

AABB

local function rect_isIntersecting(x1, y1, w1, h1, x2, y2, w2, h2)
    return x1 < x2 + w2 and x2 < x1 + w1 and y1 < y2 + h2 and y2 < y1 + h1
end

Liang-Barsky

“把线段从 0~1 的参数时间裁剪，得到它在矩形内部那一段”。

一条线从 A 走到 B，问它有没有穿过矩形；如果穿过，给出“进入”和“离开”的百分比。

源码

local function rect_getSegmentIntersectionIndices(x, y, w, h, x1, y1, x2, y2, ti1, ti2)
    ti1, ti2 = ti1 or 0, ti2 or 1
    local dx, dy = x2 - x1, y2 - y1
    local nx, ny
    local nx1, ny1, nx2, ny2 = 0, 0, 0, 0
    local p, q, r

    for side = 1, 4 do
        if side == 1 then
            nx, ny = -1, 0
            p, q = -dx, x1 - x
        elseif side == 2 then
            nx, ny = 1, 0
            p, q = dx, x + w - x1
        elseif side == 3 then
            nx, ny = 0, -1
            p, q = -dy, y1 - y
        else
            nx, ny = 0, 1
            p, q = dy, y + h - y1
        end

        -- 平行
        if p == 0 then
            if q <= 0 then return nil end
        else
            r = q / p
            if p < 0 then  -- 进入边
                if r > ti2 then
                    return nil
                elseif r > ti1 then -- 更新 ti1
                    ti1, nx1, ny1 = r, nx, ny
                end
            else  -- 离开边
                if r < ti1 then
                    return nil
                elseif r < ti2 then -- 更新 ti2
                    ti2, nx2, ny2 = r, nx, ny
                end
            end
        end
    end

    return ti1, ti2, nx1, ny1, nx2, ny2
end

还是有点不懂

有一个矩形 (x, y, w, h)
有一条线段 (x1, y1) 到 (x2, y2)
求这条线段和矩形相交时，对应的参数区间 t

P(t) = (x1, y1) + t * (dx, dy)
dx = x2 - x1
dy = y2 - y1
t ∈ [0, 1]

x <= Px = x1 + t * (x2 - x1) <= x+w
y <= Py = y1 + t * (y2 - y1) <= y+h

t = 0 是起点
t = 1 是终点

返回 ti1,ti2, nx1,ny1, nx2,ny2
进入矩形的时刻 ti1
离开矩形的时刻 ti2
进入时碰到的边的法线 nx1, ny1
离开时碰到的边的法线 nx2, ny2

碰到左边界
x1 + dx*t = x
t = (x - x1) / dx
t = q / p

把四条边转成 4 个对 t 的不等式约束，求出所有约束的交集
pqr 标准计法，把每条边都写成 p * t <= q
p < 0，进入边
p > 0，离开边
再通过 r = q / p 得到边界上的 t

左边界
p, q = -dx, x1 - x
nx, ny = -1, 0

其他边界
nx,ny,p,q = 1, 0, dx, x + w - x1
nx,ny,p,q = 0, -1, -dy, y1 - y
nx,ny,p,q = 0, 1, dy, y + h - y1

ti1, ti2 = ti1 or 0, ti2 or 1 
默认考虑整条线段 t ∈ [0,1]
之后四条边会不断收紧这个区间

不用 pqr

local function rect_getSegmentIntersectionIndices(x, y, w, h, x1, y1, x2, y2)
  local dx = x2 - x1
  local dy = y2 - y1

  local txEnter, txExit
  local tyEnter, tyExit

  local nxEnter, nyEnter = 0, 0
  local nxExit, nyExit = 0, 0

  -- 处理 x 轴
  if dx == 0 then
    -- 线段在 x 方向不动，如果起点不在矩形水平范围内，就不可能相交
    if x1 < x or x1 > x + w then
      return nil
    end
    txEnter = -math.huge
    txExit = math.huge
  else
    local tx1 = (x - x1) / dx       -- 碰到左边，left=x=x1+t*dx
    local tx2 = (x + w - x1) / dx   -- 碰到右边，right=x+w

    txEnter = math.min(tx1, tx2)
    txExit  = math.max(tx1, tx2)

    if tx1 < tx2 then
      nxEnter, nyEnter = -1, 0
      nxExit, nyExit   = 1, 0
    else
      nxEnter, nyEnter = 1, 0
      nxExit, nyExit   = -1, 0
    end
  end

  -- 处理 y 轴
  if dy == 0 then
    -- 线段在 y 方向不动，如果起点不在矩形垂直范围内，就不可能相交
    if y1 < y or y1 > y + h then
      return nil
    end
    tyEnter = -math.huge
    tyExit = math.huge
  else
    local ty1 = (y - y1) / dy       -- 碰到上边
    local ty2 = (y + h - y1) / dy   -- 碰到下边

    tyEnter = math.min(ty1, ty2)
    tyExit  = math.max(ty1, ty2)
  end

  -- 总进入时间 = x/y 中较晚进入的那个
  local ti1 = math.max(txEnter, tyEnter)

  -- 总离开时间 = x/y 中较早离开的那个
  local ti2 = math.min(txExit, tyExit)

  -- 如果进入晚于离开，就没有交集
  if ti1 > ti2 then
    return nil
  end

  -- 如果真正的进入是由 y 轴决定的，进入法线改成 y 轴那条边
  if tyEnter > txEnter then
    if dy > 0 then
      nxEnter, nyEnter = 0, -1
    else
      nxEnter, nyEnter = 0, 1
    end
  end

  -- 离开法线也一样
  if tyExit < txExit then
    if dy > 0 then
      nxExit, nyExit = 0, 1
    else
      nxExit, nyExit = 0, -1
    end
  end

  -- 如果只想线段范围 [0,1]，还要再判断
  if ti2 < 0 or ti1 > 1 then
    return nil
  end

  -- 裁剪到 [0,1]
  ti1 = math.max(ti1, 0)
  ti2 = math.min(ti2, 1)

  return ti1, ti2, nxEnter, nyEnter, nxExit, nyExit
end