如何高效实现轴对齐包围盒对三角形的反向裁剪及贴合包围盒生成

云上老周

2026-8-2

用三角形裁剪轴对齐包围盒生成贴合AABB的高效实现方法

问题背景

我多方查找未找到相关资料，希望实现用三角形裁剪轴对齐包围盒（AABB），生成贴合的新轴对齐包围盒——常见的是用AABB裁剪三角形，反向操作的资料却很少。我曾尝试先计算裁剪后的三角形再生成包围盒，但这种方法效率极低，且代码存在问题，想请教高效实现这种反向裁剪的方法。

当前做法说明

以下是我当前实现思路的示意图：
裁剪示意图1
裁剪示意图2
裁剪示意图3

当前实现代码

typedef uint8_t  u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t   s8;
typedef int16_t  s16;
typedef int32_t  s32;
typedef int64_t  s64;
typedef float    f32;
typedef double   f64;

struct Point
{
    union
    {
        f32 a[3];
        struct
        {
            f32 x;
            f32 y;
            f32 z;
        };
    };
};

struct BoundingBox3
{
    Point m_vMin = {FLT_MAX,FLT_MAX,FLT_MAX};
    Point m_vMax = {-FLT_MAX,-FLT_MAX,-FLT_MAX};
};

inline
s8 Classify( s8 sign, u8 axis, const Point *c_v, const Point *p_v )
{
    const f64 d = sign * ( p_v->a[axis] - c_v->a[axis] );
    if ( d > EPSILON )
    {
        return  1;
    }
    else if ( d < -EPSILON )
    {
        return -1;
    }
    return  0;
}

#define POINT_BUFFER_SIZE 9

inline
void Clip3D_plane( Point *pVerts, s8 sign, u8 axis, u8 *pdwNumVerts, const Point *pPointOnPlane )
{
    u8 dwNumVerts = ( *pdwNumVerts );
    if ( dwNumVerts == 0 )
    {
        return;
    }
    else if ( dwNumVerts == 1 )
    {
        *pdwNumVerts = 0;
        return;
    }

    Point vNewVerts[POINT_BUFFER_SIZE];
    u8 k = 0;
    bool b = true; // polygon is fully located on clipping plane

    Point v1 = pVerts[dwNumVerts - 1];
    s8 d1 = Classify( sign, axis, pPointOnPlane, &v1 );
    for ( u8 j = 0; j < dwNumVerts; ++j )
    {
        const Point &v2 = pVerts[j];
        s8 d2 = Classify( sign, axis, pPointOnPlane, &v2 );

        if ( d2 != 0 )
        {
            b = false;
            if ( ( 0x80 & ( d2 ^ d1 ) ) != 0 ) //if signs differ
            {
                const f32 fAlpha = ( v2.a[axis] - pPointOnPlane->a[axis] ) / ( v2.a[axis] - v1.a[axis] );
                Point_Lerp( &v2, &v1, fAlpha, &vNewVerts[k++] );
            }
            else if ( d1 == 0 && ( k == 0 || !Point_Equals( &vNewVerts[k - 1], &v1 ) ) )
            {
                vNewVerts[k++] = v1;
            }

            if ( d2 > 0 )
            {
                vNewVerts[k++] = v2;
            }
        }
        else
        {
            if ( d1 != 0 )
            {
                vNewVerts[k++] = v2;
            }
        }

        v1 = v2;
        d1 = d2;
    }

    if ( b )
    {
        return;
    }

    *pdwNumVerts = k;
    for ( u8 j = 0; j < k; ++j )
    {
        pVerts[j] = vNewVerts[j];
    }
}

inline void BoundingBox_Append( BoundingBox3 *pBB, const Point *pvPoint )
{
    pBB->m_vMin.x = min( pBB->m_vMin.x, pvPoint->x );
    pBB->m_vMin.y = min( pBB->m_vMin.y, pvPoint->y );
    pBB->m_vMin.z = min( pBB->m_vMin.z, pvPoint->z );
    pBB->m_vMax.x = max( pBB->m_vMax.x, pvPoint->x );
    pBB->m_vMax.y = max( pBB->m_vMax.y, pvPoint->y );
    pBB->m_vMax.z = max( pBB->m_vMax.z, pvPoint->z );
}

void BoundingBox_ClipAndAppendTri( BoundingBox3 *pBB3, Point *pVerts, u8 *phwNumVerts, const BoundingBox3 *pClipBox )
{
    for ( u8 axis = 0; axis < 3; ++axis )
    {
        Clip3D_plane( pVerts, 1, axis, phwNumVerts, &pClipBox->m_vMin );
        Clip3D_plane( pVerts, -1, axis, phwNumVerts, &pClipBox->m_vMax );
    }
    for ( u8 vert = 0; vert < *phwNumVerts; ++vert )
    {
        BoundingBox_Append( pBB3, &pVerts[vert] );
    }
}

高效实现方案

核心思路

跳过完整裁剪多边形的步骤，直接针对AABB的六个面，结合三角形的平面方程与重心坐标测试，计算被三角形约束后AABB在各轴上的极值：

快速筛选位置关系：用分离轴定理先排除完全在三角形外的AABB（直接返回无效盒），完全在三角形内的AABB直接返回原盒。
逐轴计算极值：对x、y、z三个轴，候选极值点包括：
- 原AABB中在三角形内部的顶点
- 三角形边与AABB面的交点（需在三角形内部）
- 三角形平面与AABB棱的交点（需在三角形内部）
从所有有效候选点中提取各轴的最大/最小值，组成贴合的新AABB。

关键优化点

避免生成中间裁剪多边形，减少内存操作与冗余计算
利用AABB轴对齐特性，将3D问题分解为三个独立的1D极值求解
预计算三角形平面方程，快速判断点的位置；用重心坐标法验证点是否在三角形内部

简化实现代码

#define EPSILON 1e-6f

struct Plane {
    f32 a, b, c, d;
};

// 从三角形生成平面方程（归一化）
Plane TriangleToPlane(const Point& v0, const Point& v1, const Point& v2) {
    Point e1 = {v1.x - v0.x, v1.y - v0.y, v1.z - v0.z};
    Point e2 = {v2.x - v0.x, v2.y - v0.y, v2.z - v0.z};
    Plane p;
    p.a = e1.y * e2.z - e1.z * e2.y;
    p.b = e1.z * e2.x - e1.x * e2.z;
    p.c = e1.x * e2.y - e1.y * e2.x;
    f32 len = sqrtf(p.a*p.a + p.b*p.b + p.c*p.c);
    p.a /= len; p.b /= len; p.c /= len;
    p.d = -(p.a*v0.x + p.b*v0.y + p.c*v0.z);
    return p;
}

// 重心坐标法判断点是否在三角形内部
bool PointInTriangle(const Point& p, const Point& v0, const Point& v1, const Point& v2) {
    Point v0v1 = {v1.x - v0.x, v1.y - v0.y, v1.z - v0.z};
    Point v0v2 = {v2.x - v0.x, v2.y - v0.y, v2.z - v0.z};
    Point v0p = {p.x - v0.x, p.y - v0.y, p.z - v0.z};
    
    f32 dot00 = v0v1.x*v0v1.x + v0v1.y*v0v1.y + v0v1.z*v0v1.z;
    f32 dot01 = v0v1.x*v0v2.x + v0v1.y*v0v2.y + v0v1.z*v0v2.z;
    f32 dot02 = v0v1.x*v0p.x + v0v1.y*v0p.y + v0v1.z*v0p.z;
    f32 dot11 = v0v2.x*v0v2.x + v0v2.y*v0v2.y + v0v2.z*v0v2.z;
    f32 dot12 = v0v2.x*v0p.x + v0v2.y*v0p.y + v0v2.z*v0p.z;
    
    f32 denom = dot00 * dot11 - dot01 * dot01;
    if (fabs(denom) < EPSILON) return false; // 三角形退化
    
    f32 u = (dot11 * dot02 - dot01 * dot12) / denom;
    f32 v = (dot00 * dot12 - dot01 * dot02) / denom;
    
    return (u >= -EPSILON) && (v >= -EPSILON) && (u + v <= 1.0f + EPSILON);
}

// 用三角形裁剪AABB，输出贴合的新AABB
void ClipAABBWithTriangle(BoundingBox3& outBB, const BoundingBox3& inBB, const Point tri[3]) {
    // 初始化输出为无效盒
    outBB.m_vMin = {FLT_MAX, FLT_MAX, FLT_MAX};
    outBB.m_vMax = {-FLT_MAX, -FLT_MAX, -FLT_MAX};
    
    Plane plane = TriangleToPlane(tri[0], tri[1], tri[2]);
    Point corners[8] = {
        {inBB.m_vMin.x, inBB.m_vMin.y, inBB.m_vMin.z},
        {inBB.m_vMax.x, inBB.m_vMin.y, inBB.m_vMin.z},
        {inBB.m_vMin.x, inBB.m_vMax.y, inBB.m_vMin.z},
        {inBB.m_vMax.x, inBB.m_vMax.y, inBB.m_vMin.z},
        {inBB.m_vMin.x, inBB.m_vMin.y, inBB.m_vMax.z},
        {inBB.m_vMax.x, inBB.m_vMin.y, inBB.m_vMax.z},
        {inBB.m_vMin.x, inBB.m_vMax.y, inBB.m_vMax.z},
        {inBB.m_vMax.x, inBB.m_vMax.y, inBB.m_vMax.z}
    };
    
    // 收集原AABB中在三角形内部的顶点
    for (int i = 0; i < 8; ++i) {
        f32 dist = plane.a * corners[i].x + plane.b * corners[i].y + plane.c * corners[i].z + plane.d;
        if (dist >= -EPSILON && PointInTriangle(corners[i], tri[0], tri[1], tri[2])) {
            BoundingBox_Append(&outBB, &corners[i]);
        }
    }
    
    // 收集三角形边与AABB面的交点
    const Point edges[3][2] = {{tri[0], tri[1]}, {tri[1], tri[2]}, {tri[2], tri[0]}};
    for (int e = 0; e < 3; ++e) {
        const Point& p0 = edges[e][0];
        const Point& p1 = edges[e][1];
        
        // 检查与x=min面的交点
        if ((p0.x <= inBB.m_vMin.x + EPSILON && p1.x >= inBB.m_vMin.x - EPSILON) || 
            (p1.x <= inBB.m_vMin.x + EPSILON && p0.x >= inBB.m_vMin.x - EPSILON)) {
            f32 t = (inBB.m_vMin.x - p0.x) / (p1.x - p0.x);
            if (t >= -EPSILON && t <= 1.0f + EPSILON) {
                Point intersect;
                intersect.x = inBB.m_vMin.x;
                intersect.y = p0.y + t * (p1.y - p0.y);
                intersect.z = p0.z + t * (p1.z - p0.z);
                if (intersect.y >= inBB.m_vMin.y - EPSILON && intersect.y <= inBB.m_vMax.y + EPSILON &&
                    intersect.z >= inBB.m_vMin.z - EPSILON && intersect.z <= inBB.m_vMax.z + EPSILON) {
                    if (PointInTriangle(intersect, tri[0], tri[1], tri[2])) {
                        BoundingBox_Append(&outBB, &intersect);
                    }
                }
            }
        }
        
        // 同理处理x=max、y=min、y=max、z=min、z=max面，逻辑与上述一致，此处省略
        // ...
    }
    
    // 收集三角形平面与AABB棱的交点
    // AABB共12条棱，每条棱取两个端点，判断是否跨平面，计算交点后验证是否在三角形内部，此处省略循环逻辑
    // ...
    
    // 若输出盒仍为无效状态，说明AABB完全在三角形外
}

注意事项

需根据浮点精度需求调整EPSILON的值
可提前加入分离轴定理的碰撞检测，快速跳过不相交的AABB与三角形组合，进一步提升效率

内容的提问来源于stack exchange，提问作者yosmo78

如何高效实现轴对齐包围盒对三角形的反向裁剪及贴合包围盒生成

问题背景 #

当前做法说明 #

当前实现代码 #

高效实现方案 #

核心思路 #

关键优化点 #

简化实现代码 #

注意事项 #