LabHub
学习 学习路径 课程

物理引擎的骨架

找出重叠的四种方法

在 LabHub 中继续学习

目标

AABB、圆、分离轴整理，判断重叠，以宽步数减少检查次数，打开光线和箱子的交界处。完成这个练习后，可以直接制作物理引擎的碰撞检测层。

为什么重要

如果物体有200个，那么一对就有19,900个。如果全部进行精确判断，在开始物理计算之前，框架就会结束。但是实际上重叠的对数不到300个。所以碰撞检测分为两层——一个非常便宜地过滤出不可能重叠的对，另一个精确地看到剩下的对。

狭义阶段的一般解是分离轴整理。如果两个凸轮体分离的话，一定存在一条将它们分开的直线，其方向与两个凸轮体边的其中一条相同。所以只投影到边法线方向就可以了。而且重叠时给出的最小重叠轴就是推出的最短方向，所以感知和反应在相同的计算中得出。

阶段

  1. /root/collide放在工具箱上。
  2. /root/collide/aabb.py— 轴对齐边界框。
  3. /root/collide/circle.py— 圆和圆。
  4. /root/collide/sat.py— 整理分离轴。
  5. /root/collide/out/sat.png—重叠的图形和最小移动向量。
  6. /root/collide/boxes.txt哇/root/collide/out/06-broad.txt— 全数检查对齐-扫描。
  7. /root/collide/ray.py哇/root/collide/out/07-ray.txt，ray.png— 光线和箱子。

参考

放上绘画工具盒

/root/collide/gfxlib.py如实保存，/root/collide/check.py画考试图案/root/collide/out/00-check.png请制作。图案是在64x64的黑色背景上，从(0,0)到(63,63)画一条白色(255,255,255)的对角线，然后在后面从(0,32)到(63,32)画一条红色(255,0,0)的横线。

从这个练习开始，不再重新创建PNG编码器。在第一个练习中，用工具下载与手工制作的代码相同——因为在这里要学到的不是文件格式。

练习板没有音量，所以前面的练习中制作的文件没有留下。所以每次练习都从重新放回工具箱开始。

Canvas(w, h, bg)制作并line(x0, y0, x1, y1, rgb)画两条线后write_png(path)请保存为**。以后画横线。交点（32,32）变成红色。

在这个练习中，用于绘制重叠的图形和最小移动向量。

轴对齐边界框

/root/collide/aabb.py在overlap(a, b)哇penetration(a, b)请制作。盒子是(minx, miny, maxx, maxy)是的，这是你的错误，边界完全相接的情况也视为重叠。penetration如果叠加银色的话，每种颜色叠加的宽度(dx, dy)如果不重叠的话(0.0, 0.0)还给你。

先使用不重叠的条件的比较短。

not (a[2] < b[0] or b[2] < a[0] or a[3] < b[1] or b[3] < a[1])

在不等号中插入等号还是不插入等号，即是“相交的情况”的判断。这个练习将相交视为重叠，所以像上式一样去掉等号。

重叠宽度是min(a[2], b[2]) - max(a[0], b[0])是。从两个盒子右端中左边的那个，减去左端中右边的那个的值。

请只在一个地方设置判断规则。如果在多个地方设置不同的规则，盒子就会从底部摇晃起来。

圆和圆

/root/collide/circle.py在circle_hit(c1, r1, c2, r2)请制作。只有当中心之间的距离比半径的和小时，才视为重叠。(True, 법선, 깊이)，或者(False, (0.0, 0.0), 0.0)还给。法线是指向1到2的单位矢量，深度是r1 + r2 - 거리是。如果两个中心完全相同的话，法线(1.0, 0.0)放在里面。

如果不单独处理距离为 0 的情况，就会被除以 0。实际上，两个物体在同一位置出生的情况比想象中更常见——比如在 Sponner 中一次性创建时。

如果只想比较的话，可以避免平方根，但在这里需要求深度，所以需要实际距离。

将法线的方向从1到2确定是很重要的。下面的模块的冲击量计算将完全遵守这一承诺。相反，两个物体会相互吸引。

分离轴整理

/root/collide/sat.py在sat_hit(a, b)请制作。a、b是逆时针方向写成的凸多边形（顶点列表），重叠的话(True, 축, 깊이)，或者(False, (0.0,0.0), 0.0)还给。轴是两个图形所有边法线中重叠最小的一条，在a的重心方向上调整符号，指向b的重心。

变(x0,y0) -> (x1,y1)的法线是(ey, -ex)是规范化的（ex = x1-x0，ey = y1-y0).

在一条轴上的重叠是min(a1, b1) - max(a0, b0)如果这个值小于等于0，那么那个轴是分开两个图形的轴，**所以可以立即结束。**不需要看剩下的轴。

最后匹配祝贺符号的原因是，根据变法线是哪个多形的，方向可能会相反。dot(축, 무게중심b - 무게중심a) < 0如果是的话请翻过来。

两个正方形沿着x方向相距1.5时，轴是(1,0)，深度必须显示0.5。

画出重叠和推出的方向

/root/collide/draw.py罗/root/collide/out/sat.png请制作（256x256，黑色背景）。多边形A是[(-1,-1),(1,-1),(1,1),(-1,1)]用白色（255,255,255）边框，B是A(1.5, 0.5)把移动的面积画成黄色（255,220,60）边框，在B的重量中心축 * 깊이以红色（255,60,60）线绘制延伸到该程度的最小移动向量。屏幕坐标是sx = 128 + 40*x，sy = 128 - 40*y是。

多边形边框是按顺序连接顶点的线段，最后回到第一个点。gfxlib.Canvas的line请使用。

最小移动向量是sat_hit(A, B)这是乘以旋转后的直径和深度。如果将B推到这个程度，两个形状就会准确地重合——这就是“最小”一词的意思。

画的顺序是A、B、箭头。在重叠的位置，后面画的优先。

看图的话，两个正方形只在x方向稍微重叠，箭头指向右边。虽然y方向的重叠更深，但选择x的原因是“推出的最短方向”。

排好后扫一扫

/root/collide/gen_boxes.py如实保存并执行的话/root/collide/boxes.txt制作200个盒子。对这些盒子分别进行全局检查和排序-扫描。/root/collide/out/06-broad.txt在pairs_brute=，pairs_sweep=，checks_brute=，checks_sweep=请写四行。

全秀检查是i < j是看所有对的，检查次数是200*199/2 = 19,900。

排列-扫描是这样的。把盒子minx如果按顺序排列的话，可以与哪些箱子重叠的，是在排列顺序中后面的。minx去这个盒子的maxx只有不超过的那些东西。在那点内面的循环break请做。

checks_sweep是在内面的循环中实际判断重叠的次数（break没有被吸进去）。

**两种方法找到的对的数量必须相同。**宽度阶段不是改变答案，而是以便宜的价格获得相同的答案。如果不同的话break条件是错误的。

光线和箱子——拍打方法

/root/collide/ray.py在ray_aabb(o, d, box)制作后将五道光线装进盒子里(-1,-1,1,1)射进去，结果/root/collide/out/07-ray.txt在r1=hit,t或者r1=miss,0.000000请用格式写五行。还有/root/collide/out/ray.png在(256x256)上把盒子画成白色，照射到的光线画成绿色(60,255,120)，直到照射到的点，偏离的光线画成红色(255,80,80)，长度为6。画面坐标是sx = 128 + 30*x，sy = 128 - 30*y是。光线按顺序排列。o=(-3,0) d=(1,0)，o=(-3,3) d=(1,0)，o=(0,0) d=(1,0)，o=(-3,-3) d=(0.7071067811865476, 0.7071067811865476)，o=(3,0) d=(1,0)是。

拍打方法是每条轴上光线在该轴的两平面之间的区间。[t1, t2]是求出，将所有轴的区间缩小到交集。

t1 = (box.min - o) / d      # 방향이 음수면 t1 과 t2 가 뒤바뀐다
t2 = (box.max - o) / d
tmin = max(tmin, min(t1, t2))
tmax = min(tmax, max(t1, t2))

如果方向成分为0，则会发生除法。这时，只看原点是否在该轴的区间内，如果不在，则就偏离了。

最后的判断是tmax >= max(tmin, 0)是。放入0的原因是光线不会向后延伸。如果遗漏这个，就会显示光线后面的箱子也对了。第五个光线就是这种情况。

如果光线的出发点在盒子里的话t是0（第三条光线）。