作为编写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帧/秒提高到1帧/秒！这并不奇怪，因为我假设这个成对代码的时间复杂度是O(n^2)。
我的问题是，在网格中给定一组3D点的情况下，哪种算法实现起来既快又简单，可以计算(至少)近似边界球体？我看了维基百科的这个页面，发现有一个算法叫做"里特边界球"。然而，这需要我在网格中选择一些随机点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)
在顶点上迭代一次，并收集每个维度的最高值和最低值。这将创建一个由Vec3(最低.x、最低.y、最低.z)和Vec3(最高.x、最高.y、最高.z)组成的边界框。
对每个尺寸标注使用最高值和最低值的中间值。这会将框的中心创建为Vec3((最低.x+最高.x)/2，…)。
然后得到中心和盒子的8个角之间的欧氏距离。使用最大距离和找到的中心来创建一个边界圆。
您只在数据集中迭代过一次，并且对边界圆有很好的近似！
以这种方式计算的边界圆几乎肯定会比网格大。若要收缩它，可以将半径设置为距离中心最宽尺寸的距离。这种方法确实有可能剪掉角落里的面孔。
您可以迭代地缩小半径并检查所有点是否都在边界圆中，但这样会使性能比原始算法差。