How to fit/clip an axis aligned bounding box around a portion of a triangle

Question

I have looked and looked and cannot find any resources on. I want to clip an axis aligned bounding box against a triangle in a way that creates a new tight fitting axis aligned bounding box around or in the triangle (I have seen the reverse a lot, a triangle clipped against an axis alinged bounding, but never seen the reverse case). I tried computing the clipped tiangle then building a bounding box from it. But it is grossly inefficent and I don't think my code is correct. Does anyone know how to clip a bounding box against a triangle efficently?

Here is pictures describing what I currently do

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] );
    }
}

Answer 1

In general you can't escape computing intersection points between the sides of the triangle and those of the box. To get a correct result, you need to compute the intersection of the two shapes, for instance using the Sutherland-Hodgman algorithm, that you can specialize for the case of a triangle and a rectangle. If I am right, in the worst case you get an heptagon.

Then getting the AABB is no big deal.

---

Alternatively, you can implement a line-segment clipping algorithm against a poygonal (triangular or rectangular) window. A specialization to an AA window is the Cohen-Sutherland algorithm. Then clip all triangle sides against the rectangle and all rectangle sides against the triangle.