C++ 创建最小包围盒子

最小包围盒子（bounding box）是一种能够包围物体或几何形状的盒子，通常用于计算机图形学、物理模拟、碰撞检测等领域。创建最小包围盒子的方法主要有以下几种：

1. 基于几何形状的包围盒子：对于一些简单的几何形状，如球体、立方体等，可以直接创建其对应的包围盒子。

2. 基于顶点的包围盒子：对于复杂的几何模型，可以计算其所有顶点的最小和最大值，从而得到一个包围盒子。

3. 基于包围盒子的包围盒子：对于一组物体或几何形状，可以先创建一个包围所有物体的大包围盒子，再在其中创建每个物体的小包围盒子。

4. 基于分治的包围盒子：将一个物体或几何形状分成多个小部分，对每个小部分分别创建包围盒子，再将这些小包围盒子合并成一个大包围盒子。

在实际应用中，根据需要选择不同的方法创建最小包围盒子，以提高计算效率和精度。

相关问题

NX二次开发 通过OBB算法实现最小包围盒，C++实现

OBB（Oriented Bounding Box）算法是一种用于计算物体包围盒的算法，它可以将一个物体用一个最小的矩形盒子包围起来。下面是一个使用C++实现OBB算法的示例代码。

首先，我们需要定义一个表示3D向量的结构体：

struct Vector3
{
    float x, y, z;

    Vector3() : x(0), y(0), z(0) {}
    Vector3(float x_, float y_, float z_) : x(x_), y(y_), z(z_) {}

    Vector3 operator+(const Vector3& other) const
    {
        return Vector3(x + other.x, y + other.y, z + other.z);
    }

    Vector3 operator*(float scalar) const
    {
        return Vector3(x * scalar, y * scalar, z * scalar);
    }

    Vector3 operator-(const Vector3& other) const
    {
        return Vector3(x - other.x, y - other.y, z - other.z);
    }

    // 计算向量的长度
    float Length() const
    {
        return sqrt(x * x + y * y + z * z);
    }

    // 计算向量的单位向量
    Vector3 Normalized() const
    {
        float len = Length();
        if (len > 0)
        {
            return Vector3(x / len, y / len, z / len);
        }
        else
        {
            return Vector3();
        }
    }
};

接下来，定义一个表示3D物体的结构体，包含物体的顶点和面信息：

struct Mesh
{
    std::vector<Vector3> vertices;
    std::vector<std::vector<int>> faces;

    // 计算物体的最小包围盒
    void CalculateOBB(Vector3& center, Vector3& size, Vector3& axisX, Vector3& axisY, Vector3& axisZ) const
    {
        // 计算物体的中心点
        center = Vector3();
        for (int i = 0; i < vertices.size(); i++)
        {
            center = center + vertices[i];
        }
        center = center * (1.0f / vertices.size());

        // 计算协方差矩阵
        float cov[3][3] = { 0 };
        for (int i = 0; i < vertices.size(); i++)
        {
            Vector3 delta = vertices[i] - center;
            cov[0][0] += delta.x * delta.x;
            cov[0][1] += delta.x * delta.y;
            cov[0][2] += delta.x * delta.z;
            cov[1][0] += delta.y * delta.x;
            cov[1][1] += delta.y * delta.y;
            cov[1][2] += delta.y * delta.z;
            cov[2][0] += delta.z * delta.x;
            cov[2][1] += delta.z * delta.y;
            cov[2][2] += delta.z * delta.z;
        }

        // 计算协方差矩阵的特征向量和特征值
        float eigenvalues[3];
        float eigenvectors[3][3];
        diagonalize(cov, eigenvalues, eigenvectors);

        // 计算物体的大小以及三个轴的方向
        size = Vector3(sqrt(eigenvalues[0]), sqrt(eigenvalues[1]), sqrt(eigenvalues[2]));
        axisX = Vector3(eigenvectors[0][0], eigenvectors[1][0], eigenvectors[2][0]);
        axisY = Vector3(eigenvectors[0][1], eigenvectors[1][1], eigenvectors[2][1]);
        axisZ = Vector3(eigenvectors[0][2], eigenvectors[1][2], eigenvectors[2][2]);
    }

private:
    void diagonalize(float mat[3][3], float eigenvalues[3], float eigenvectors[3][3]) const
    {
        // 采用Jacobi迭代法求解特征向量和特征值
        constexpr int MAX_ITERATIONS = 100;
        constexpr float EPSILON = 1e-8f;

        float offdiag = 0.0f;
        float maxOffdiag = 0.0f;
        float diag[3] = { mat[0][0], mat[1][1], mat[2][2] };
        float off[3] = { mat[1][2], mat[0][2], mat[0][1] };
        float rot[3][3] = { 0 };
        for (int i = 0; i < MAX_ITERATIONS; i++)
        {
            int p, q;
            maxOffdiag = off[0];
            p = 0;
            q = 1;
            if (fabsf(off[1]) > fabsf(maxOffdiag))
            {
                maxOffdiag = off[1];
                p = 1;
                q = 2;
            }
            if (fabsf(off[2]) > fabsf(maxOffdiag))
            {
                maxOffdiag = off[2];
                p = 0;
                q = 2;
            }
            if (fabsf(maxOffdiag) < EPSILON)
            {
                break;
            }

            float theta = (diag[q] - diag[p]) / (2.0f * maxOffdiag);
            float s = (theta >= 0.0f) ? 1.0f : -1.0f;
            float t = s / (fabsf(theta) + sqrt(1.0f + theta * theta));
            float c = sqrt(1.0f - t * t);
            float tau = t / (1.0f + c);
            float tmp = s * maxOffdiag;
            diag[p] -= tmp;
            diag[q] += tmp;
            off[p] -= tmp;
            off[q] = 0.0f;
            for (int j = 0; j < 3; j++)
            {
                tmp = c * rot[j][p] - s * rot[j][q];
                rot[j][q] = s * rot[j][p] + c * rot[j][q];
                rot[j][p] = tmp;
            }
            for (int j = 0; j < 3; j++)
            {
                tmp = c * rot[p][j] - s * rot[q][j];
                rot[q][j] = s * rot[p][j] + c * rot[q][j];
                rot[p][j] = tmp;
            }
        }

        eigenvalues[0] = diag[0];
        eigenvalues[1] = diag[1];
        eigenvalues[2] = diag[2];
        eigenvectors[0][0] = rot[0][0];
        eigenvectors[0][1] = rot[0][1];
        eigenvectors[0][2] = rot[0][2];
        eigenvectors[1][0] = rot[1][0];
        eigenvectors[1][1] = rot[1][1];
        eigenvectors[1][2] = rot[1][2];
        eigenvectors[2][0] = rot[2][0];
        eigenvectors[2][1] = rot[2][1];
        eigenvectors[2][2] = rot[2][2];
    }
};

最后，我们可以通过以下代码来使用OBB算法计算物体的包围盒：

Mesh mesh;
// 加载物体的顶点和面信息
// ...

Vector3 center, size, axisX, axisY, axisZ;
mesh.CalculateOBB(center, size, axisX, axisY, axisZ);

这样，我们就可以获得物体的最小包围盒的中心点、大小以及三个轴的方向了。

NX二次开发,用C++ 写一个OBB算法来创建实体的最小包容盒

OBB（oriented bounding box）算法是一种用于计算三维物体包围盒的算法，它可以创建一个最小的、能够完全包含物体的矩形盒子。以下是使用C++语言编写OBB算法的基本步骤：

1. 定义点和向量结构体

struct Point {
    float x, y, z;
};

struct Vector {
    float x, y, z;
};

2. 计算物体的中心点

Point computeCenterPoint(Point* points, int numPoints) {
    Point center = { 0.0f, 0.0f, 0.0f };
    for (int i = 0; i < numPoints; i++) {
        center.x += points[i].x;
        center.y += points[i].y;
        center.z += points[i].z;
    }
    center.x /= numPoints;
    center.y /= numPoints;
    center.z /= numPoints;
    return center;
}

3. 计算物体的协方差矩阵

Matrix3x3 computeCovarianceMatrix(Point* points, int numPoints) {
    Point center = computeCenterPoint(points, numPoints);
    Matrix3x3 covarianceMatrix = { 0.0f };
    for (int i = 0; i < numPoints; i++) {
        Vector v = { points[i].x - center.x, points[i].y - center.y, points[i].z - center.z };
        covarianceMatrix.m11 += v.x * v.x;
        covarianceMatrix.m12 += v.x * v.y;
        covarianceMatrix.m13 += v.x * v.z;
        covarianceMatrix.m21 += v.y * v.x;
        covarianceMatrix.m22 += v.y * v.y;
        covarianceMatrix.m23 += v.y * v.z;
        covarianceMatrix.m31 += v.z * v.x;
        covarianceMatrix.m32 += v.z * v.y;
        covarianceMatrix.m33 += v.z * v.z;
    }
    covarianceMatrix.m11 /= numPoints;
    covarianceMatrix.m12 /= numPoints;
    covarianceMatrix.m13 /= numPoints;
    covarianceMatrix.m21 = covarianceMatrix.m12;
    covarianceMatrix.m22 /= numPoints;
    covarianceMatrix.m23 /= numPoints;
    covarianceMatrix.m31 = covarianceMatrix.m13;
    covarianceMatrix.m32 = covarianceMatrix.m23;
    covarianceMatrix.m33 /= numPoints;
    return covarianceMatrix;
}

4. 计算物体的主轴

void computePrincipalAxis(Matrix3x3 covarianceMatrix, Vector* axis) {
    float eigenvalues[3];
    Vector eigenvectors[3];
    diagonalize(covarianceMatrix, eigenvalues, eigenvectors);
    int maxEigenvalueIndex = 0;
    float maxEigenvalue = eigenvalues[0];
    for (int i = 1; i < 3; i++) {
        if (eigenvalues[i] > maxEigenvalue) {
            maxEigenvalueIndex = i;
            maxEigenvalue = eigenvalues[i];
        }
    }
    axis->x = eigenvectors[maxEigenvalueIndex].x;
    axis->y = eigenvectors[maxEigenvalueIndex].y;
    axis->z = eigenvectors[maxEigenvalueIndex].z;
}

5. 计算物体的OBB

void computeOBB(Point* points, int numPoints, Point* obbCenter, Vector* obbAxis, Vector* obbExtent) {
    Matrix3x3 covarianceMatrix = computeCovarianceMatrix(points, numPoints);
    computePrincipalAxis(covarianceMatrix, obbAxis);
    Point center = computeCenterPoint(points, numPoints);
    obbCenter->x = center.x + obbAxis->x * dotProduct(points[0], *obbAxis);
    obbCenter->y = center.y + obbAxis->y * dotProduct(points[0], *obbAxis);
    obbCenter->z = center.z + obbAxis->z * dotProduct(points[0], *obbAxis);
    float minX, minY, minZ, maxX, maxY, maxZ;
    minX = minY = minZ = FLT_MAX;
    maxX = maxY = maxZ = -FLT_MAX;
    for (int i = 0; i < numPoints; i++) {
        Vector p = { points[i].x - obbCenter->x, points[i].y - obbCenter->y, points[i].z - obbCenter->z };
        Vector e = { obbAxis->x * dotProduct(p, *obbAxis), obbAxis->y * dotProduct(p, *obbAxis), obbAxis->z * dotProduct(p, *obbAxis) };
        if (e.x < minX) minX = e.x;
        if (e.y < minY) minY = e.y;
        if (e.z < minZ) minZ = e.z;
        if (e.x > maxX) maxX = e.x;
        if (e.y > maxY) maxY = e.y;
        if (e.z > maxZ) maxZ = e.z;
    }
    obbExtent->x = (maxX - minX) * 0.5f;
    obbExtent->y = (maxY - minY) * 0.5f;
    obbExtent->z = (maxZ - minZ) * 0.5f;
}

6. 计算两个OBB之间的距离

float computeOBBDistance(Point* obb1Center, Vector* obb1Axis, Vector* obb1Extent, Point* obb2Center, Vector* obb2Axis, Vector* obb2Extent) {
    Vector d = { obb2Center->x - obb1Center->x, obb2Center->y - obb1Center->y, obb2Center->z - obb1Center->z };
    float distance = fabs(dotProduct(d, *obb1Axis));
    distance -= fabs(dotProduct(d, *obb2Axis));
    Vector crossProduct = cross(*obb1Axis, *obb2Axis);
    distance += fabs(dotProduct(d, crossProduct));
    for (int i = 0; i < 3; i++) {
        distance -= fabs(dotProduct(crossProduct, Vector{ obb2Extent->x * obb2Axis->x, obb2Extent->y * obb2Axis->y, obb2Extent->z * obb2Axis->z }));
        crossProduct = cross(*obb1Axis, Vector{ obb2Axis->x, obb2Axis->y, obb2Axis->z });
        distance += fabs(dotProduct(d, crossProduct));
    }
    return distance;
}

以上是使用C++语言编写OBB算法的基本步骤，你可以根据自己的需求进行调整。