线段和AABB包围盒求交
本文介绍线段和AABB包围盒相交计算的算法。
概念解释
AABB包围盒：AABB（Axis-Aligned Bounding Box，轴对齐包围盒）是一种常用于计算机图形学和物理模拟中的简单包围体。其边缘与坐标轴对齐，即它的面是平行于坐标轴的。这使得计算变得简单，因为你只需要考虑最小和最大坐标。通常一个AABB包围盒会用其最小坐标点和最大坐标点表示。
OBB包围盒：OBB（Oriented Bounding Box，定向包围盒）是一种更灵活的长方体包围盒，用于包围三维物体。与 AABB（轴对齐包围盒）不同，OBB 允许包围盒的面与坐标轴成任意角度。
平板法
算法思想
平板法来源自Cyrus-Beck的直线裁剪法。其中，《Real-Time Render》一书中对其进行了扩展，使其能够处理更加一般的OBB包围盒。同样地，这种方法也适用于AABB包围盒，因为AABB包围盒是一种OBB包围盒的一种特殊形式。一个OBB包围盒可以看作是有三个slab（由一组平行平面划分出的控件区域）组成的区域。
计算时，用线段起点O和线段方向D表示线段所在的射线。对于包围盒的每一个slab来说，利用线段所在的射线与slab的两个面进行求交计算。对于每一个slab来说，如果射线与slab的两个面相交，则有以下两个交点（如果平行，则认为t分别为正负无穷大）：
对于组成包围盒的三个slab来说，取所有tmin中的最大值为Tmin和tmax中的最小值为Tmax。如果Tmin<=Tmax则认为射线所在的直线与包围盒相交，反之则不相交。其中，Tmin表示的点为射线方向上的最近交点，Tmax表示的点为射线方向上的最远交点。进而，我们判断交点是否在线段上确定线段和包围盒的位置关系。算法思想在二维上的示意图如下所示：
说明：左侧展示了由两个slab构成的OBB包围盒，右侧表示了两条射线。其中，左侧射线满足Tmin<Tmax；右侧的射线不满足相交条件。
算法实现
对AABB包围盒和线段的定义如下：
struct Box{
vec3 max;
vec3 min;
};
struct Ray{
vec3 start;
vec3 dir;
vec3 inv_d; // 方向的倒数，注意方向分量为0时候的运算
float length;
};对平板法求交计算的实现如下：
enum class IntersectionType {
NONE,
INTERSECT,
INCLUDE,
};
// 注意平行时的交点t计算
IntersectionType intersect(Box& box, Ray& ray){
auto boxMax = box.max;
auto boxMin = box.min;
float tmin = (boxMin.x - ray.start.x) * ray.inv_d.x;
float tmax = (boxMax.x - ray.start.x) * ray.inv_d.x;
if(tmin > tmax){
std::swap(tmin, tmax);
}
float tymin = (boxMin.y - ray.start.y) * ray.inv_d.y;
float tymax = (boxMax.y - ray.start.y) * ray.inv_d.y;
if(tymin > tymax){
std::swap(tymin, tymax);
}
if((tmin > tymax) || (tymin > tmax)){
return IntersectionType::NONE;
}
tmin = std::fmax(tymin, tmin);
tmax = std::fmin(tymax, tmax);
float tzmin = (boxMin.z - ray.start().z) * ray.inv_d.z;
float tzmax = (boxMax.z - ray.start().z) * ray.inv_d.z;
if(tzmin > tzmax){
std::swap(tzmin, tzmax);
}
if((tmin > tzmax) || (tzmin > tmax)){
return IntersectionType::NONE;
}
// 记录交点,t表示交点到起始点的距离
tmin = std::fmax(tzmin, tmin);
tmax = std::fmin(tzmax, tmax);
auto inRange = [](float value, float left, float right){
return (value >= left) && (value <= right);
};
// 只要有一个点在线上就认为交中
if (inRange(tmin, 0.0f, ray.length) || inRange(tmax, 0.0f, ray.length)){
return IntersectionType::INTERSECT;
} else if(tmin < 0.0f && tmax > ray.length){
return IntersectionType::INCLUDE;
}
return IntersectionType::NONE;
}效果展示
使用OpenGL绘制AABB包围盒和线段进行测试，效果如下所示：
1.不相交：box显示为绿色；
2.相交：box显示为蓝色；
3.Box包含线段：box显示为红色；
可执行程序戳这里下载体验。
Comments | NOTHING