C++ 球体—立方体重叠：无、部分或全部

为了用八进制树表示球体，我需要确定球体和轴对齐立方体之间的重叠.具体而言，有三种情况:

• 立方体完全在球体内部.我们把它标记为满.
• 立方体完全在球体之外.我们把它标记为空.
• 立方体部分位于球体内部.我们将其细分并递归.

以下是我目前对如何做到这一点的最佳猜测.

I'm asking here to know if there are any simpler ways (meaning lesser complexity / fewer operations)

感谢this previous question的答案，我找到了this algorithm来检测任何重叠.然而，它不能区分立方体是完全在球体内，还是只是部分在球体内.

根据这里给出的建议，我首先通过判断立方体的最远角是否在球体内部来判断总重叠.如果不是，那么我们使用Jim Arvo的算法来确定是否有任何重叠.

以下是我的结论:(使用c23)

#include <OpenGL/OpenGL.h>
#include <math.h>

/* A 3D point with type-punning to access coordinates by name or index */
typedef union point_3d {
    struct {
        GLdouble x, y, z;
    } coord;

    GLdouble t[ 3 ];
} point_3d;

/* An axis-aligned cube */
typedef struct cube {
    /* corner with smallest coordinates */
    point_3d p_min;

    /* side length */
    GLdouble len;
} cube_t;

typedef struct sphere {
    unsigned int radius;
    point_3d center;
} sphere_t;

/* Clearly defined values for our result */
typedef enum overlap {
    no_overlap = -1,
    partial_overlap = 0,
    total_overlap = 1,
} overlap_t;

static inline GLdouble sq( GLdouble val ) {
    return val * val;
}

static bool point_in_sphere( point_3d p, struct sphere s ) {
    GLdouble dx = p.t[ 0 ] - s.center.t[ 0 ];
    GLdouble dy = p.t[ 1 ] - s.center.t[ 1 ];
    GLdouble dz = p.t[ 2 ] - s.center.t[ 2 ];
    return sq( s.radius ) >= sq( dx ) + sq( dy ) + sq( dz );
}

overlap_t cube_overlaps_sphere( cube_t c, sphere_t s ) {
    point_3d p_min = c.p_min;
    point_3d p_max = { .t= {
        p_min.t[0] + c.taille,
        p_min.t[1] + c.taille,
        p_min.t[2] + c.taille,
    } };
    point_3d c_centre = { .t = { 
        p_min.t[0] + c.taille / 2,
        p_min.t[1] + c.taille / 2, 
        p_min.t[2] + c.taille / 2,
    } };
    point_3d v = { .t = {
        c_centre.t[ 0 ] - s.centre.t[ 0 ],
        c_centre.t[ 1 ] - s.centre.t[ 1 ],
        c_centre.t[ 2 ] - s.centre.t[ 2 ],}
    };
    point_3d far_corner = { .t = { 
        v.t[ 0 ] < 0 ? p_min.t[ 0 ] : p_max.t[ 0 ],
        v.t[ 1 ] < 0 ? p_min.t[ 1 ] : p_max.t[ 1 ],
        v.t[ 2 ] < 0 ? p_min.t[ 2 ] : p_max.t[ 2 ],
    } };

    if ( point_in_sphere( far_corner, s ) ) {
        return total_overlap;
    }

    /* 算法rithm by Jim Arvo */
    GLdouble dmin = 0;
    for ( unsigned int i = 0; i < 3; i++ ) {
        if ( s.center.t[ i ] < p_min.t[ i ] ) {
            dmin += pow( s.center.t[ i ] - p_min.t[ i ], 2 );
        } else if ( s.center.t[ i ] > p_max.t[ i ] ) {
            dmin += pow( s.center.t[ i ] - p_max.t[ i ], 2 );
        }
    }
    if ( dmin <= pow( s.radius, 2 ) ) {
        return partial_overlap;
    } else {
        return no_overlap;
    }
}