在 Python 中计算 3D 网格的包围球

Question

作为编写 3D 游戏库的一部分，我正在尝试实施视锥体剔除以避免渲染相机透视视锥体之外的对象。为此，我首先需要为每个网格计算边界球体，并查看它是否与视锥体的六个边中的任何一个发生碰撞。这是我目前（非常）天真的计算每个模型的边界球体的实现，如我的代码中 model.py 所写：

from pyorama.entity import Entity
from pyorama.math3d.vec3 import Vec3
from pyorama.math3d.mat4 import Mat4
from pyorama.physics.sphere import Sphere
import math
import numpy as np
import itertools as its

class Model(Entity):

    def __init__(self, mesh, texture, transform=Mat4.identity()):
        super(Model, self).__init__()
        self.mesh = mesh
        self.texture = texture
        self.transform = transform

    def compute_bounding_sphere(self):
        vertex_data = self.mesh.vertex_buffer.get_data()
        vertices = []
        for i in range(0, len(vertex_data), 3):
            vertex = Vec3(vertex_data[i: i+3])
            vertices.append(vertex)
        max_pair = None
        max_dist = 0
        for a, b in its.combinations(vertices, 2):
            dist = Vec3.square_distance(a, b)
            if dist > max_dist:
                max_pair = (a, b)
                max_dist = dist
        radius = math.sqrt(max_dist)/2.0
        center = Vec3.lerp(max_pair[0], max_pair[1], 0.5)
        return Sphere(center, radius)

我只是从我的网格中获取成对的点，并使用我找到的最大距离作为我的直径。在每帧 100 个简单的立方体测试模型上调用此方法非常慢，将我的帧速率从 120 fps 驱动到 1 fps！这并不奇怪，因为我假设这个成对代码的时间复杂度是 O(n^2)。

我的问题是，在给定网格中的一组 3D 点的情况下，哪种算法能够快速且相当简单地计算（至少）近似边界球体？我查看了 this 维基百科页面，看到有一个算法叫做 "Ritter's bounding sphere." 然而，这需要我在网格中选择一些随机点 x 并希望它是近似中心以便我得到一个合理的紧边界球体。有没有一种快速选择好的起点 x 的方法？任何帮助或建议将不胜感激！

更新：

根据@Aaron3468 的回答，这是我的库中用于计算边界框和相应边界球的代码：

from pyorama.entity import Entity
from pyorama.math3d.vec3 import Vec3
from pyorama.math3d.mat4 import Mat4
from pyorama.physics.sphere import Sphere
from pyorama.physics.box import Box
import math
import numpy as np
import itertools as its


class Model(Entity):

    def __init__(self, mesh, texture, transform=Mat4.identity()):
        super(Model, self).__init__()
        self.mesh = mesh
        self.texture = texture
        self.transform = transform

    def compute_bounding_sphere(self):
        box = self.compute_bounding_box()
        a, b = box.min_corner, box.max_corner
        radius = Vec3.distance(a, b)/2.0
        center = Vec3.lerp(a, b, 0.5)
        return Sphere(center, radius)

    def compute_bounding_box(self):
        vertex_data = self.mesh.vertex_buffer.get_data()
        max_corner = Vec3(vertex_data[0:3])
        min_corner = Vec3(vertex_data[0:3])
        for i in range(0, len(vertex_data), 3):
            vertex = Vec3(vertex_data[i: i+3])
            min_corner = Vec3.min_components(vertex, min_corner)
            max_corner = Vec3.max_components(vertex, max_corner)
        return Box(min_corner, max_corner)

Answer 1

遍历顶点一次并收集每个维度的最高值和最低值。这将创建一个由 Vec3(lowest.x, lowest.y, lowest.z) 和 Vec3(highest.x, highest.y, highest.z) 组成的边界框。

使用每个维度的最高值和最低值的中值。这会将框的中心创建为 Vec3((lowest.x + highest.x)/2, ...).

然后求出盒子的中心到8个角的每一个角的欧氏距离。使用最大距离和您找到的中心来制作边界圆。

您只迭代了一次数据集并且对边界圆有很好的近似！

以这种方式计算出的边界圆几乎肯定会比网格大。要缩小它，您可以将半径设置为沿最宽尺寸距离中心的距离。这种方法确实存在切掉角落里的脸的风险。

您可以反复缩小半径并检查所有点是否都在边界圆内，但这样您的性能会比您的原始算法差。

在 Python 中计算 3D 网格的包围球

Computing the Bounding Sphere for a 3D Mesh in Python

python

algorithm

3d

frustum

bounding-volume